Программно - алгоритмический комплекс распознавания образов многогранных объектов

, ,

,

Программно - алгоритмический комплекс распознавания образов многогранных объектов.1

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

Введение

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

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

-оптические;

-тепловые;

-радиолокационные.

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

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

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

Обработка изображения имеет две стадии: предварительная и основная.

Предварительная обработка изображения может включать следующие операции: фильтрация (подавление шумов) и выделение контура изображения. Основная обработка предназначена для получения векторов признаков изображения объекта, которые используются при его распознавании.

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

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

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

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

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

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

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

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

Существует группа методов, учитывающих информацию о пространственных отношениях между признаками. Эти методы называются реляционными.

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

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

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

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

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

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

Yi=(yi1, yi2, 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 - номера смежных признаков;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим назначения (Yi, Zj) и (Yk, Zl). Они будут несовместны, если

i=k или j=l. (4)

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

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

Рассмотрим два признака эталона Yi, Yk.

Они будут смежны, если

yi3=k или yi4 =k. (5)

Признаки Yi и Yk не будут смежны, если

yi3k и yi4 k. (6)

Пример. i=2, k=3: признаки Y2 и Y3 смежны (см. условие 5).

Рассмотрим назначения (Yi, Zj) и (Yk, Zl) .Отношения не совместны, если Yi и Yk смежны, а Zj и Z l не смежны или, если Yi и Yk не смежны, а Zj и Zl смежны.

Признаки Zj и Zl будут смежны, если

z j3=l или z j4=l. (7)

Признаки Z j и Z l не будут смежны, если

z j3l и z j4l. (8)

Вернемся к примеру. Пусть i=2, k=3 и имеется назначение (Y2, Zn); l=n-1 и имеется назначение (Y3, Zn-1). Назначения совместны. Рассмотрим пару назначений (Y3, Zn-1) и (Y2, Z4). Они не совместны.

Следовательно, назначения (Yi, Zj) и (Yk, Zl) не совместны, если выполняются условия (4), (5) и (8). Назначения (Yi, Zj) и (Yk, Zl) не совместны также, если выполняются условия (4), (6) и (7).

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

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

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

4. Поиск мощности наибольшей максимальной клики графа

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

Число вершин графа, входящих в наибольшее независимое, множество называется числом независимости этого графа и обозначается через .

Задача отыскания величины М графа сводится к задаче нахождения величины дополнительного графа.

Отметим, что большинство из известных алгоритмов поиска наибольшей клики (наибольшего независимого множества) данного графа [13-19] применимо лишь при небольшом числе клик (для малых графов).

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

В [12] авторами предложена его модификация для распознавания многогранных объектов.

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

5. Распознавание многоугольников

Докажем, что для любого эталона-многоугольника и зашумленного объекта в графе соответствия существует одна МК или несколько МК с одинаковыми мощностями и поиск величины М существенно упрощается.

1. Рассмотрим эталон многоугольника, приведенный на рис.1. Пусть объект является слабо зашумленным и содержит как и эталон n признаков (рис.2). Пусть также все однотипные признаки эталона существенно отличаются друг от друга по величине и для пар признаков эталона и объекта (Yi, Zi), i=1,2,...,n выполняются условия (2), (3). Тогда пары (Yi, Zi),

Рис.1 Рис.2

 

i=1,2,...,n являются назначениями. Проверка совместимости назначений дает положительный результат и граф соответствия (рис. 3) будет полным и совпадающим с МК мощностью М=n. Граф содержит вершины V1(1,1),..., Vn(n, n).

2. В случае, если для k пар признаков условие (3) не будет выполняться, то граф останется полным, а мощность МК будет определяться по формуле М=n - k (рис. 4).

3. Пусть эталон и объект содержат близкие признаки, например, Y1, Y3 и Z1, Z3. Это приводит к появлению дополнительных назначений (Y1, Z3) и (Y3, Z1), которые соответствуют новым вершинам графа V n+1(1, 3), V n+2(3, 1). Появляются несовместные пары назначений (Y1, Z1 ), (Y1, Z 3); (Y1, Z1 ), (Y3, Z1 ); (Y3, Z1 ), (Y3, Z3); (Y3, Z3), (Y1, Z3). Следовательно, пары вершин (V1, V n+1); (V1, V n+2); (V3, V n+1) и (V3, V n+2) не будут соединены ребрами (рис.5). Новый граф не будет полным, но его МК будет совпадать с графом, соответствующим случаю 1 и приведенным на рис. 3 (М=n).

4. В случае сильно искаженного объекта в результате фильтрации и оконтуривания появляются дополнительные признаки при исчезновении исходных (9). Например, пусть у объекта (рис. 2) отсутствует угол Zn и части сторон Z1, Z n-1. У нового объекта (рис. 6) появляются новые признаки Zn+1 (сторона) и Z n+2 (угол). Угол Z n принимает новое значение.

Пусть для пар признаков (Y1, Z1),..., (Yn, Z n ) выполняется условие (3). Тогда перечисленные пары являются назначениями, которым соответствуют вершины графа V1,..., Vn. Все назначения являются совместными, а граф - полным и совпадает с его МК мощностью М=n.

Пусть для пары (Yn-1, Zn-1) не выполняется (3). Тогда список назначений не содержит эту пару и список вершин не содержит вершину Vn-1, следовательно, М = n - 1.

Аналогичная картина наблюдается, если (3) не выполняется для пары (Y1, Z1) или для пары (Yn, Z n), тогда М=n - 1.

В случае, если (3) не соблюдается для k назначений, то

М=n - k.

 

Рис.4

 

Рис.5

 

Рис.6

Необходимо также провести сравнение нового признака объекта Zn+1 с однотипными признаками эталона Y1, Y3,...,Y n-1 и признака Zn+2 с признаками Y2, Y4,..., Yn.

Пусть, например, для пары признаков (Y1, Zn+1) выполняется условие (3), что приводит к появлению нового назначения

несовместного с назначением (Y1, Z1). Это не приводит к изменению исходной клики, содержащей вершины V1,..., Vn.

Аналогичная картина наблюдается и в общем случае при появлении назначений (Yi, Zn+1), i=1,3,…, n-1 и (Yi, Zn+2), i=2,4,…, n.

Следовательно, для многоугольников

М=n - k, (11)

где k - количество признаков, для которых не выполняется условие (3).

6. Распознавание многогранников

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

Таким образом, теперь М i - мощность МК графа соответствия i-й пары проекций эталона и объекта.

Следовательно, процесс распознавания многогранников на первом этапе сводится к сравнению числа граней эталона n и объекта m. В случае, если n= m, то переходим к сопоставлению ортогональных проекций эталона и объекта. В результате этого сравнения получаем множество Мi, i=1,...,p, где p - число пар проекций. Например, для треугольной пирамиды n=4 и m=4, а p=16.

Таким образом, распознавание объекта- многогранника сводится к последовательному сопоставлению его граней (многоугольников) с гранями эталона и вычислению множества Мi. Очевидно, что на каждом этапе распознавания будет возникать одна МК или несколько МК одинаковой мощности и алгоритм распознавания существенно упрощается и сводится к последовательному использованию формулы (11) для нахождения величин Мi, которые в (11) обозначены как М. После нахождения множества Мi, где i =1,...,p необходимо найти

М*= min (Мi) (12)

и осуществить сравнение М* с порогом распознавания . В случае, если М*, то считаем, что объект идентичен эталону, иначе для распознавания потребуются дополнительные исследования.

7. Программный комплекс распознавания.

Авторами разработан программный продукт 2D IMAGEPRO 1.0, реализующий алгоритм распознавания образов на базе модифицированного метода максимальной клики.

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

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

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

За ввод изображения отвечает функция Open1Click. Она выполняет следующие операции:

1.  Открывает диалог, позволяющий пользователю выбрать изображение для обработки.

2.  Создает оконную форму.

3.  Переносит изображение из выбранного файла на оконную форму.

4.  Вызывает выполнение основной программы MainFunction.

5.  Выполняет переключение режимов работы программы с режима обработки эталона в режим обработки объекта с помощью функции Compare1Click.

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

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

Две линии соединены между собой в центральной точке CenterPos и движутся по контуру фигуры, причем все три точки 1, CenterPos и 2 всегда лежат на контуре фигуры. Для начала движения необходимо найти эти три точки. Для этой цели служат функции LinesCenter и LinesCoordinates.

Функция LinesCenter находит координату самой верхней точки контура фигуры – точку старта движения отрезков линий. Ей соответствует CenterPos.».

Функция LinesCoordinates находит координаты концов отрезков 1 и 2.

Функция LineMove обеспечивает движение отрезков по контуру.

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

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

На этом функция RecognizeObject завершает свою работу, передавая в основную программу MainFunction найденную матрицу признаков эталона.

Поиск максимальной клики графа и вывод результата выполняет функция NumOfIndependence. Выходным параметром является значение мощности максимальной клики графа MaxClique.

Интерфейс программы выполнен в виде окна, находящегося вверху экрана с соответствующими информативными полями и вкладками задания и изменения режимов (см. рис.12-15).При начале работы пользователь должен открыть окно выбора необходимого изображения эталона. Об этом напоминает соответствующая надпись Mode: identification (режим идентификации). Для того, чтобы получить изображение эталона, необходимо выбрать вкладку File \ Open. При этом откроется диалоговое окно, в котором можно выбрать требуемое изображение. В окне есть возможность просмотра изображения. При выборе необходимого изображения диалоговое окно закроется и откроется окно с выбранным изображением. Сразу же запустится основная программа. Изображение будет обработано (вычислены стороны и углы многоугольника).

Сразу после окончания распознавания программа переключится в режим Compare (сравнения). При этом на информационной панели появится надпись Mode:Compare. Программа готова к открытию файла с изображением объекта. Пользователь открывает диалоговое окно предыдущим образом (File/Open) и выбирает изображение для сравнения. После того, как оно выбрано, произойдет его сравнение с эталоном. В результате сравнения на информационной панели появится значение мощности клики графа (см. рис.16). Далее пользователь может открыть диалоговое окно для ввода следующего изображения объекта для сравнения с изображением эталона.

Для того чтобы поменять эталон, необходимо выбрать вкладку Mode: Set Original. Программа готова для ввода эталона. Если необходимо поменять объект, то нужно выбрать вкладку Mode:Compare. Программа будет готова к вводу объекта для сравнения. В разработанной программе существует два режима распознавания: для качественных изображений (с ровными сторонами и четкими углами) и ”грубых” изображений объектов (с нечеткими углами и неровными сторонами).

Для того, чтобы распознавать качественные изображения, необходимо выбрать вкладку Image: Fine. Для того, чтобы распознавать ”грубые” изображения, необходимо выбрать вкладку Image: Rough.

Выход из программы осуществляется при нажатии вкладки File:Exit. На рис.17 приведена блок-схема программного комплекса.

8. Пример распознавания многогранников

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

Пусть имеются изображения трех эталонов, которые отличаются высотой (h=3, 4, 5 см) и изображение объекта, для которого выполняется условие (3) при сравнении его граней с гранями изображения первого эталона. Проведем сравнение граней объекта, которые не лежат в основании пирамиды, с аналогичными гранями первого эталона.

Сравним изображение первой грани эталона с изображением первой грани объекта. Получаем в соответствии с (11) М=M1=6. Такие же результаты будут и при сравнении изображения первой грани эталона с изображениями второй и третьей граней эталона. При сравнении изображений второй и третьей граней эталона с изображениями всех трех граней объекта получаем тот же результат (M1 = … = M9). Таким образом, в результате сравнения объекта с первым эталоном получаем в соответствии с (12) величину M*=6.

Проведем сравнение объекта со вторым эталоном. В этом случае условие (3) не выполняется при сравнении одного угла грани объекта с соответствующим углом грани эталона. В этом случае имеем M*=5.

 

Проведем сравнение объекта с третьим эталоном. В этом случае условие (3) не выполняется при сравнении двух сторон и угла между ними граней объекта с соответствующими признаками граней эталона. В этом случае имеем M*=3.

Таким образом, подтверждается то, что изображение наиболее похоже на первый эталон.

Выводы

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

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

1. Системы технического зрения (принципиальные основы, аппаратное и математическое обеспечение) / , , и др.; Под общ. ред. , . – Л.: Машиностроение, 1988.

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

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

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

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

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

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

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

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

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

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

12. , , Герасимов распознавания объёмных образов на базе модифициро - ванного метода максимальной клики: Сборник трудов Института системного анализа Российской академии наук/ Под ред. Д. т.н. проф. М.: Эдиториал УРСС, 2002.

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

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

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

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

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

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

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

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

Рис. 12

Рис.13

Рис.14

Рис.15

Рис.16