Распознавание образов

При построении интеллектуального мобильного робота с высокой степенью интеллектуальности необходима такая система распознавания образов, которая позволила бы не только распознавать известные ей образы, но и обучаться новым.

При построении такой системы кроме задачи распознавания образов в реальном масштабе времени необходимо решить следующие задачи:

• организации базы данных образов с возможностью ее дополнения и модификации;
• построения системы поиска заданного образа на видеоизображении;
• построения системы слежения за заданным образом и вычисления его координат.

Для решения непосредственно задачи распознавания образов был разработан специальный алгоритм. В ее основу разработанной системы было положено понятие образа.

Под образом будем понимать замкнутую область на оконтуренном изображении, обладающую определенными свойствами.

Рассмотрим свойства образа.

1. Идентификатор образа. Все образы обладают числовым идентификатором, который заменяет название образа, и назначается при обучении.

2. Форма. Форма образа задается бинарной матрицей nxn. Причем n должно быть достаточно небольшим, в противном случае на распознавание образа будет сильно влиять его ориентация. В данной работе будем рассматривать образы со значением n=4. Различные формы, заданные таким образом, представлены на Рис. 1 (а).

3. Цвет. Различить на видеоизображении абсолютно точный цвет объекта при различных уровнях освещенности не удается. Можно лишь оценить преобладающий цвет. Поэтому для черно-белого изображения цвет должен состоять из двух градаций (1 бит): темный и светлый.

4. Соотношение вертикального и горизонтального размера. Диапазон значений соотношения размеров не следует делать достаточно большим. Рекомендуемый диапазон от 0.25 до 4. Такой диапазон был выбран из эмпирических соображений о том, что объекты с отношением сторон больших 4 человеческим восприятием воспринимаются, как достаточно вытянутыми в высоту, а объекты с соотношением сторон меньше 0.25 - как достаточно вытянутыми в длину.

5. Размер. Определяется по большей стороне.

В разработанном методе используется два типа образов: экранные образы и ассоциативные образы.

Экранные образы формируются в результате преобразования видеоизображения в образы. Они содержат все рассмотренные свойства, кроме идентификатора. Свойства экранного образа дополнены данными об его экранных координатах и координатах в плоскости пола.

Ассоциативные образы являются элементом базы данных образов и образуются в результате обучения. Все их свойства (кроме идентификатора и формы) являются не значениями, а множествами значений.

На рис. 1 (б) представлена структурная схема разработанной системы для распознавания образов.

Рис. 1. Примеры форм образов (а), структура системы распознавания объектов среды (б)

Она состоит из четырех основных модулей:

• Модуль преобразования изображения в образы. Данный модуль производит преобразование исходного и оконтуренного изображения в список экранных образов. Процесс этого преобразования описан далее.
• База данных образов. Этот модуль предназначен для хранения списка ассоциативных образов. По команде системы управления поведением этот модуль добавляет в базу данных или удаляет из нее образ, находящийся в указанных координатах.
• Модуль поиска образов. Данный модуль по команде системы управления поведением извлекает из базы данных образов ассоциативные образы с указанным идентификатором. После чего ищет эти образы в списке экранных образов и возвращает общее число совпадений.
• Модуль слежения за образом. В отличие от предыдущего модуля, модуль слежения за образом находит только один экранный образ и начинает слежение за ним. Если в процессе слежения объект был потерян или нераспознан, то модуль продолжает ожидать его повторное появление в некоторой окрестности в течение какого-то времени. Если объект не появился снова, то модуль перестраивается на слежение за другим объектом (если таковой имеется) с тем же идентификатором.

Рассмотрим основные алгоритмы работы системы.

Алгоритм преобразования изображения в экранные образы.

Модуль преобразования изображения в образы использует следующий алгоритм работы.

1. Производится сканирование оконтуренного изображения, и для каждой белой точки выполняется п.2 (Рис. 2, б).
2. Используя рекурсивную процедуру, производится "растекание" по всей области белого цвета, ограниченной черным контуром, из точки, определенной в п.1. При этом точки оконтуренного изображения, которые были "посещены" рекурсивной процедурой, окрашиваются в светло-серый цвет (Рис. 2.16, в). Светло-серый цвет на оконтуренном изображении является признаком использования данной точки. Целью рекурсии является определение размеров замкнутой области. По завершению рекурсии в глобальных переменных формируются экранные координаты прямоугольной области, ограничивающей замкнутую область изображения (на Рис. 2.16 (в) эта область обведена прямоугольником).
3. Проверяются размеры полученной области. Если эти размеры не меньше и не больше определенных пороговых величин, то выполняется шаг 4.
4. Используя другую рекурсивную процедуру, производится "растекание" по всей области светло-серого цвета, ограниченной черным контуром, из точки, определенной в п. 1. "Посещенные" рекурсивной процедурой точки оконтуренного изображения окрашиваются в темно-серый цвет, который является признаком использования данной точки. Целью рекурсии является:
   • Определение цвета объекта, покрытого данной областью. Цвет определяется, как среднее арифметическое значение цветов соответствующих пикселей исходного изображения (здесь именно исходного, а не оконтуренного).
   • Определение формы области. Для определения формы составляется матрица nxn. Прямоугольная область, определенная в п. 2, разбивается на n частей по горизонтали и n частей по вертикали. За каждым элементом матрицы закрепляется соответствующая зона, полученная в результате разбиения прямоугольной области на части (Рис. 2, г). Рекурсивная процедура в каждом элементе этой матрицы считает общее число попаданий в закрепленную за элементом зону (Рис. 2). По окончанию рекурсии, если в элементе матрицы образовалось число, значение которого меньшее, чем половина площади зоны, то в соответствующий элемент бинарной матрицы формы записывается 0, иначе 1.
5. Для заданной фигуры определяется соотношение вертикального и горизонтального размера и общий размер. А также по принципу ровного пола вычисляются координаты X,Y объекта в плоскости пола.

Рис. 2. Процесс распознавания образа: а) исходное изображение; б) поиск на оконтуренном изображении белой точки; в) рекурсивная "заливка" замкнутой области с целью определения ее размеров; г) определение формы.

Рис. 3. Иллюстрация процесса определения формы.

В результате работы алгоритма образуется список всех экранных образов. Важно отметить, что мелкие объекты (вроде гаек, винтов, мелких надписей и т.п. (для наземного робота), окон и дверей домов листьев деревьев и т.п. (для БЛА)) в список образов не попадают, т.к. имеют малые размеры. Большие же объекты (стена, пол и т.п.) также не попадают в список из-за их больших размеров.

Алгоритмы обучения базы данных образов

База данных образов содержит список ассоциативных образов, образованных путем ее прямого редактирования или в результате обучения. Обучение предполагает два режима: режим добавления нового образа и режим удаления образа.

При добавлении образа необходимо сформировать идентификатор нового образа (ID) и экранные координаты точки (X, Y), находящейся внутри образа.

По запросу на добавление образа модуль базы данных выполняет пп. 2-5, рассмотренного выше алгоритма преобразования изображения в образы. В качестве исходной точки для "растекания" используется точка (X, Y). Если в указанных координатах образ не найден, то на выходе модуля базы данных формируется сигнал с кодом ошибки.

Если экранный образ найден в указанных координатах, то по рассмотренному выше алгоритму определяется его форма (Form), цвет (Color), соотношение вертикального и горизонтального размера (Ratio) и наибольший размер (Size).

Далее в базе данных ассоциативных образов производится поиск ассоциативного образа с идентификатором ID и формой Form. Если такой образ отсутствует в списке, то в базе данных формируется новый ассоциативный образ. Ему присваивается идентификатор ID, форма Form и цвет Color. В качестве соотношения размеров новый образ использует множество в окрестности значения Ratio. В качестве размера используются множество всех возможных размеров.

Если образ с формой Form и идентификатором ID уже присутствует в базе данных, то множество цветов этого образа пополняется цветом Color. Множество соотношений размеров пополняется множеством в окрестности значения Ratio. Множество размеров пополняется множеством размеров в окрестности Size.

При удалении образа из базы данных производится не удаление, а сокращение множеств параметров ассоциативного образа.

Для удаления образа необходимо сформировать экранные координаты (X, Y) точки, находящиеся внутри образа, идентификатор образа (ID), а также сигнал с кодом причины удаления (Reason). Причины удаления, а также их код сведены в Табл. 1.

При этом модуль базы данных выполняет пп. 2-5, рассмотренного выше алгоритма преобразования изображения в образы. В качестве исходной точки для "растекания" используется точка (X,Y). Если в указанных координатах образ не найден, то на выходе модуля базы данных формируется сигнал с кодом ошибки.

Если образ найден в указанных координатах, то по рассмотренному выше алгоритму определяется его форма (Form), цвет (Color), соотношение горизонтального и вертикального размера (Ratio) и размер образа (Size).

Модуль базы данных подсчитывает количество Cnt ассоциативных образов с идентификатором ID, хранящихся в базе данных. В базе данных может храниться несколько таких образов, различающихся формой.

Затем в списке ассоциативных образов производится поиск такого ассоциативного образа, идентификатор которого совпадает с идентификатором ID, форма совпадает с Form, множество цветов включает цвет Color, множество соотношений сторон включает параметр Ratio, а множество размеров включает параметр Size. Если такой образ отсутствует в списке, то формируется сигнал ошибки.

Если требуемый ассоциативный образ присутствует в базе данных, то с ним производятся следующие действия.

Если Reason = 3 (см. Табл. 1) или Reason = 2 и величина Cnt больше трех, то производится удаление найденного ассоциативного образа.

Если Reason = 7 или Reason = 2 и Ratio сравнительно большое, то у ассоциативного образа из множества соотношений размеров вычитается множество соотношений размеров в окрестности значения Ratio.

Аналогично, если Reason = 8 или Reason = 2 и Ratio сравнительно малое, то у ассоциативного образа из множества соотношений размеров вычитается множество соотношений размеров в окрестности значения Ratio.

Аналогично с большим и малым размером объекта.

Если сигнал Reason = 4, то из множества цветов ассоциативного образа вычитается цвет экранного образа. Автоматически причина "не тот цвет" не обнаруживается.

Если Reason = 2, и причина не определена, то на выходе модуль формирует определенный код ошибки. Подразумевается, что данный код ошибки будет воспринят системой управления поведением для организации дополнительного диалога с пользователем с целью выяснения причины.

Экспериментальные исследования системы распознования образов

Исследование алгоритма перевода изображения в экранные образы

Поставим перед телекамерой робота несколько предметов (Рис. 3). Убедимся, что эти предметы правильно преобразуются в список экранных образов (Рис. 3, б).

Рис. 3. Преобразование видеоизображения в экранные образы: а) видеоизображение с телекамеры; б) оконтуренное изображение с наложенным на него изображением экранных образов

Заметим, что мелкие объекты на видеоизображении распознаются не достаточно четко и однозначно. Это объясняется динамически изменяемыми цифровыми помехами на изображении. Передвижения средних и больших по величине предметов не приводят к потере их образа.

Обучение базы данных образов и проверка алгоритмов поиска и слежения за образами

На момент проведения эксперимента в базе данных образов умышленно не было заложено образа в виде круга.

Используя систему управления поведением, оператор проводит с роботом диалог на естественном языке и предлагает роботу обучиться новому образу, указав координаты белого круга на экране (Рис. 3, б).

При этом система управления поведением посылает на модуль базы данных образов запрос на добавление нового объекта с указанием его координат и идентификатора (идентификатор был сгенерирован системой управления поведением и равнялся 1971692432).

На этот запрос модуль базы данных образов должен сформировать в базе данных новый образ или выдать код ошибки. В данном случае модуль базы данных успешно сформировал новый образ. Фрагмент базы данных с автоматически сформированным образом представлен на Рис. 4.

Рис. 4. Фрагмент базы данных образов после обучения кругу

Для того чтобы проверить, что система обучена новому образу, оператор в диалоге с роботом предлагает ему следить за кругом.

Система управления поведением формирует идентификатор объекта "круг" (1971692432) для модуля слежения за образами. Модуль слежения за образами захватывает объект "круг" и следит за его местоположением. При этом на изображении экранных образов захваченный объект обводится зеленой рамкой, а на локальной карте местности формируется отметка дальности до захваченного объекта (Рис. 5).

Рис. 5. Слежение за образами: а) г) видеоизображение; б) д) оконтуренное изображение с наложенным изображением образов; в) е) локальная карта местности с отметкой дальности до захваченного объекта