Алгоритм распознавания объемных образов на базе модифицированного метода максимальной клики

, ,

Алгоритм распознавания объемных образов на базе модифицированного метода максимальной клики[1]

Аннотация

В статье рассматривается метод распознавания инвариантных к аффинным преобразованиям специальных классов трехмерных объектов, базирующийся на алгоритме поиска наибольшей максимальной клики графа соответствия распознаваемого объекта и эталона. В статье приведены примеры реализации метода.

1. Введение

В настоящее время актуальными при управлении сложными системами являются задачи распознавания трехмерных объектов. Рассматриваемую задачу распознавания можно разделить на три этапа:

1.1.  Формирование и ввод изображений в ЭВМ

Будем считать, что формирование изображений базируется на использовании одной камеры и структурированного освещения объекта.

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

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

1.2.  Обработка бинарных изображений

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

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

  Выделения связных областей.

  Прослеживания контура каждой из областей с попутным вычислением признаков.

  Получения компактного представления с помощью операций сжатия или скелетизации.

Вопросы формирования и ввода изображений в ЭВМ и их обработки подробно изложены в [1-3] и в данной статье не рассматриваются.

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

1.3. Распознавание объектов и интерпретация сцен

В большинстве случаев целью работы системы технического зрения является опознание заданных объектов среди множества других (распознавание) и интерпретация сцены (определение координат и ориентации объектов сцены).

Основной целью данной статьи является описание, разработанного авторами, метода распознавания.

Существует большое количество методов распознавания объектов по их изображениям [1-10]. Методы разнятся между собой по сложности и степени универсальности. Наиболее простые из них предназначены для распознавания небольшого количества изолированных объектов, имеющих значительные различия по форме и размерам, а самые совершенные методы способны различать перекрывающиеся объекты.

Наиболее прямолинейный подход к распознаванию заключается в непосредственном сопоставлении двух необработанных изображений. Однако вычислительные затраты этого метода велики. Второй подход предполагает выделение из изображения характерных признаков, по которым выполняется распознавание. Одним из алгоритмов, использующих этот подход, является алгоритм распознавания по вектору признаков, который эффективен главным образом при условии, что наблюдаемые объекты изолированы, а уровень помех не слишком высок. В противном случае помимо данных о типе и количественных характеристиках требуется информация о пространственных отношениях между признаками. Существует группа методов, учитывающих информацию о пространственных отношениях между признаками [2,3]. Эти методы называются реляционными.

Среди реляционных методов наибольшей универсальностью обладает метод, основанный на выделении максимальной клики на графе соответствия признаков эталона и образа [3]. Этот метод дает хорошие результаты при распознавании сильно зашумленных объектов.

Исследования, проведенные в Массачусетском технологическом институте по распознаванию зашумленных или перекрывающихся объектов, показали высокие быстродействие и надежность распознавания двухмерных объектов при использовании метода максимальной клики [2].

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

2.  Модифицированный метод максимальной клики

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

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

Однако, метод можно использовать и для других объектов, имеющих гладкие поверхности.

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

Пусть системе предъявлен для распознавания объект - многогранник. На первом этапе распознавания необходимо сравнить число граней эталона n и объекта m. В случае, если n=m, то переходим к сопоставлению ортогональных проекций эталона и объекта. Причем необходимо сопоставить все проекции эталона и объекта. В результате распознавания находим величину M=minMi, где Mi - наибольшая мощность максимальных клик графов соответствий i - х пар проекций эталона и изображения, если M, где - порог распознавания, то считаем, что изображение идентично эталону, иначе для распознавания требуются дополнительные исследования.

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

Пусть даны векторы признаков эталона

Yi=(yi1, yi 2,yi3,yi4), i=1,2,...,n.

и объекта (1)

Zj=(zj1,zj2,zj3,zj4), j=1,2,...,m, где

yi1, zj1 - типы признаков эталона и объекта соответственно (yi1= 0, zj1= 0 - признаки типа “угол”; yi1=1, zj1=1 - признаки типа “линия”);

yi2, zj2 - величина угла в градусах (длина линии в метрах) эталона и объекта соответственно;

yi3,yi4, zj3,zj4 - номера смежных признаков (zj3,zj4 - могут отсутствовать);

n, m - число признаков эталона и объекта соответственно.

Для решения задачи распознавания необходимо сопоставить признаки объекта и эталона. Результаты сопоставления называются назначениями, которым соответствуют вершины графа соответствий. Далее необходимо проверить совместимость назначений. В случае, если пара назначений совместима, то соответствующие вершины графа соединяются ребрами. На заключительном этапе распознавания следует найти мощность наибольшей максимальной клики графа соответствий.

Рассмотрим теперь перечисленные этапы решения задачи распознавания.

2.1. Составление назначений

Составление назначений содержит следующие два этапа.

1. Сравнение признаков по типу

Проверка условий yi1 = zj1 , i=1,2,...,n; j=1,2,...,m (2)

2. Проверка условия (yi 2 - zj2 ) / yi 2 < e, (3)

где е - малая положительная величина.

Выполнение условий (2), (3) говорит о том, что данные признаки эталона и объекта однотипные и слабо отличаются друг от друга.

При выполнении условий (2), (3) составляется список назначений (Yi, Zj), где i, j=1,2,... соответствующий списку вершин графа соответствий. Вершины графа vi удобно обозначать в соответствии с индексами назначений, например, v1(1,1); v2(2,4).

2.2. Проверка совместимости назначений

Проверка совместимости назначений содержит два следующих этапа.

1. Проверка отсутствия противоречий

Два назначения несовместны, если их 1- е или 2 - е индексы совпадают; это означает, что один признак эталона назначается двум признакам объекта или один признак объекта назначается двум признакам эталона, что невозможно.

2. Проверка соблюдения отношений смежности

Два назначения несовместны, если признаки эталона смежны, а соответствующие признаки объекта несмежны. Два назначения также несовместны, если признаки объекта смежны, а соответствующие признаки эталона не смежны.

Отношения смежности не соблюдаются, если yi3=yi4+1, а zj3=zj4+1 или yi3=yi4+1, а zj3=zj4+1.

В случаях, описанных в п. п. 1, 2, вершины графа vi и vj, соответствующие этим назначениям, не соединяются ребрами. В остальных случаях вершины соединяются ребрами.

2.3. Формирование матрицы смежности VМ

Cоответствующие парам вершин vi и vj элементы v ij матрицы смежности графа будут нулевыми. В остальных случаях v ij =1. Диагональные элементы матрицы будут нулевыми.

2.4. Поиск максимальной клики графа назначений G

2.4.1. Определения и основные свойства клик графа G

Напомним (см., например, [11-13]), что

  Кликой K в графе G(V, E), где V - непустое множество вершин графа, EVV - множество ребер (дуг) G, называется такое подмножество его вершин, что для любых v1,v2K ребро (v1,v2)E.

  Клика Км называется максимальной, если она не содержится в клике с большим числом вершин и наибольшей, если число вершин в ней наибольшее среди всех клик.

  Число вершин в наибольшей клике графа G называется его плотностью, мощностью или кликовым числом и обозначается через (G) или M. Отметим, что мощность наибольшей максимальной клики графа назначений G характеризует степень соответствия распознаваемого объекта эталону.

Напомним также (см. [11-13]), что

  Множество вершин S графа G называется независимым, если никакие две вершины из этого множества несмежны (иными словами, если SV и S независимо в графе G, то порожденный подграф G(S) является пустым).

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

  Наибольшее по мощности (числу вершин) независимое множество называется просто наибольшим, а число вершин графа G, входящих в наибольшее независимое множество называется числом независимости этого графа и обозначается через (G).

Связь между множествами клик и независимыми множествами графа G устанавливает следующая

Теорема [11-13]

1. Подмножество вершин графа G является кликой тогда и только тогда, когда оно независимо в дополнительном графе G (т. е. в графе G, дополняющем G до полного графа).

2. Для величин (G) и (G) справедливо соотношение

(G)= (G).

Утверждения 1,2 теоремы показывают, что задача отыскания величины (G) графа G может быть сведена к задаче нахождения величины(G) дополнительного графа G.

Заметим, однако, что обе эти задачи относятся к классу NP- сложных переборных задач [14] и очень трудны для алгоритмического решения. Отметим также, что большинство из известных алгоритмов поиска наибольшей клики (наибольшего независимого множества) данного графа [14-17] требует формирования списка всех клик (независимых множеств) данного графа исходя из списка всех клик возрастающей последовательности его подграфов и поэтому применимы лишь при небольшом числе клик, т. е. только для малых графов.

В работе [18] американскими математиками Броном и Кербошем был разработан алгоритм поиска максимально независимых множеств (МНМ), существенно упрощающий процедуру перебора вершин графа G. В этом алгоритме не нужно запоминать генерируемые независимые множества для проверки их на максимальность путем сравнения с ранее сформированными множествами. Этот алгоритм был опробован для большого числа графов и было установлено, что время необходимое для построения МНМ почти постоянно и не зависит от величины графа. Все это говорит о том, что данный алгоритм является одним из наиболее эффективных.

В следующем разделе приведем краткое описание этого алгоритма.

2.4.2. Алгоритм Брона-Кербоша нахождения наибольшего максимального независимого множества графа G

Начальная установка.

Шаг 1. Пусть S0=Q-0=, Q+0=V, k=0.

Прямой шаг.

Шаг 2. Выбрать вершину vik Q+k и сформировать множества

Sk+1=Sk(vik);

Q-k+1=Q-k\Г(vik);

Q+k+1=Q+k\(Г(vik)(vik));

оставляя Q-k и Q+k нетронутыми. Положить k=k+1.

Проверка.

Шаг 3. Если удовлетворяется условие:

vQ-k такая, что Г(v)Q+k=,

то перейти к шагу 5, иначе к шагу 4.

Шаг 4. Если Q+k=Q-k=, то напечатать максимальное независимое множество (МНМ) Sk и перейти к шагу 5. Иначе перейти к шагу 2.

Шаг возвращения.

Шаг 5. Положить k=k-1. Удалить vik из Sk+1, чтобы получить Sk. Исправить Q-k и Q+k, удалив вершину vik из Q+k добавив ее к Q-k. Если k=0 и Q+0=, то остановиться. (К этому моменту будут напечатаны все МНМ). Иначе перейти к шагу 3.

В алгоритме использованы следующие обозначения:

Sk - независимое множество вершин графа G на этапе k;

Q-k - подмножество вершин графа G, которые уже использовались в процессе поиска для расширения множества;

Q+k - подмножество вершин графа G, которые еще не использовались для расширения;

Г(v) - множество вершин графа G, смежных с вершиной v.

В ряде случаев, некоторые из которых будут рассмотрены ниже, граф G является полным и для него М(G)=n, где n-число вершин графа.

В заключение раздела 2 отметим, что векторы признаков объекта инвариантны к его аффинным преобразованиям и величина M также инвариантна к аффинным преобразованиям объекта.

3. Примеры распознавания

Рассмотрим распознавание треугольной пирамиды (см. рис.1). Будем считать, что эталон пирамиды содержит три треугольника. Пусть системе для распознавания предъявлен некоторый объект (многогранник). Для получения его изображений осуществляется съемка граней. Съемка ведется одной камерой и направление съемки перпендикулярно граням. Пусть в результате предварительной обработки мы получаем три изображения в виде контуров треугольников, в которых из-за помех возможно отсутствие угла и частей, прилегающих к нему сторон и количественные характеристики признаков объекта и эталона отличаются.

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

На рис.2, 3 приведены соответственно эталон и объект, которые характеризуются векторами признаков (1), где n=m=6.

Пример1

Пусть условие (3) выполняется только для случая i=j, что справедливо, если количественные характеристики однотипных признаков эталона существенно различны. Тогда получаем список назначений (Yi, Zi), i=1,2,...,6. Этому списку соответствует

 

 

список вершин v1, v2,...,v6 графа G. На рис. 4 внутри вершин графа указаны индексы соответствующих назначений.

Далее проверим совместимость назначений. В соответствии с п. п. 1 и 2 все назначения совместимы, следовательно, все вершины графа G соединены ребрами (см. рис. 4). Таким образом, граф является полным и множество вершин (v1,v2,...,v6) является наибольшей максимальной кликой с мощностью M=6.

Пример 2

Пусть условие (3) не выполняется для стороны Z6 (см. рис. 3). При этом не производится назначение (Y6,Z6) и граф G (см. рис.5) содержит вершины (v1,v2,...,v5). Все назначения совместимы и все его вершины соединены между собой ребрами. Таким образом, множество вершин (v1,v2,...,v5) является наибольшей максимальной кликой с мощностью M1=5.

Идентичные графы получаются в случае, если условие (3) не выполняется для любого признака Zj.

В случае, если условие (3) не выполняется для любых двух признаков объекта, то получаем M2=4 (см. рис. 6). В общем случае M=6 - k, где k - число признаков, для которых не выполняется условие (3).

 

Рис. 5

 

Рис. 6

 

Рис. 7

Z6

Z5

 

Рис. 8 Рис. 9

На рис. 7 и 8 приведены графы для случаев k=3 и k=4 соответственно (M3=3 и M4=2). В этих случаях распознавание объекта невозможно.

Пример 3

Пусть у распознаваемого объекта из-за помех отсутствует угол Z1 и части сторон Z2 и Z6 (см. рис.9), но для признаков Z2,Z3,...,Z6 выполняется условие (3). Тогда имеем список назначений (Yi, Zi), где i=2,3,...,6, получаем граф, приведенный на рис.5, и имеем M6=5.

Пример 4

Пусть в примере 3 стороны эталона Y6 и Y4 слабо отличаются друг от друга, как и отрезки Z6 и Z4 объекта. Тогда возникают дополнительные назначения (Y6,Z4), (Y4,Z6) и среди общего списка назначений появляются несовместимые пары: (Y4, Z4), (Y4, Z6); (Y4, Z4), (Y6, Z4); (Y6, Z6), (Y4, Z6); (Y6, Z6), (Y6, Z4): одной стороне эталона не может назначаться две стороны объекта и наоборот. На рис. 10 приведен граф для данного примера. Назначениям (Y6, Z4) и (Y4, Z6) соответствуют вершины (v6; 6,4) и (v7; 4,6). Для решения задач такого типа необходимо определить матрицу смежности дополнительного графа и использовать алгоритм поиска наибольшего максимального независимого множества. Число независимости этого множества будет равно мощности наибольшей максимальной клики исходного графа. Применяя вышеизложенный алгоритм, находим, что мощность наибольшей максимальной клики равна пяти. Наибольшая максимальная клика содержит вершины (v1,v2,...,v5).

Таким образом, примеры 3 и 4 показывают, что даже в случае сильно искаженного изображения (отсутствует угол и части двух сторон) мы получаем значение М близкое к максимальному (М=6) и можем успешно распознать объект.

4. Заключение

Таким образом, в статье предложен метод раcпознавания инвариантных к аффинным преобразованиям объемных объектов, основанный на алгоритме поиска наибольшей максимальной клики графа соответствий распознаваемого объекта и эталона, в статье приведены примеры реализации алгоритма, и предложен эффективный метод вычисления кликового числа графа соответствий.

 

Рис. 10

5. Список литературы

1. Хорн роботов: Пер. с англ.- М.: Мир, 1989.

2. Техническое зрение роботов/ Под ред. А. Пью.- М.: Машиностроение, 1987.

3. Логинов технического зрения.- М.:МИРЭА, 1991.

4. Вычислительная геометрия: Пер. с англ.- М.: Мир, 1982.

5. Фоли Дж. , А. вэн Дэм. Основы интерактивной машинной графики: Пер. с англ.- М.: Мир, 1985.

6. Алгоритмические основы машинной графики: Пер. с англ.- М.: Мир, 1989.

7. , Батраков компьютерная графика.- М.: Радио и связь, 1995.

8. Машинная графика и вычислительная геометрия в задачах машиностроения/ Под ред. .- М.: НС по КП “Кибернетика” при АН СССР, 1989.

9. Развитие безбумажной технологии в организационных системах/ Под ред. и .-М.: Эдиториал УРСС, 1999.

10. Методы и средства работы с документами/ Под ред. и .- М.: Эдиториал УРСС, 2000.

11. Теория графов.-М.: Наука, 1980.

12. Теория графов. Алгоритмический подход.- М.: Мир, 1978.

13. и др. Лекции по теории графов.- М.: Наука,1990.

14. Евстигнеев теории графов в программировании.- М. Наука,1985.

15. Weisman J. Boolean algebra, map coloring and interconnections //Amer. Math. Monthly. 1962. Vol 69. P. 7-9.

16. , , Фрицнович максимальных клик графа //Автоматика и вычислительная техника. 1970. №3. С. 93-96.

17. Зыков теории графов. - М. Наука, 1987.

18. Bron C., Kerbosh J. (1973), Algorithm 457 - Finding all cliques of an undirected graph, Comm. of ACM, 16, p. 575.

[1] Работа выполнена в рамках комплексной программы научных исследований Президиума РАН “Интеллектуальные компьютерные системы” (проект №4.3) и поддержана Российским фондом фундаментальных исследований (проект №).