Исследование систем управления манипулятором MR-999Е

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

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

Параллельно с определением точек контура проводятся вычисления периметра, площади и моментов площади первого порядка [16].

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 1.4 - Описание контура простой формы

Таблица 1.2 - Номера и значения цепочки

Номер элемента цепочки	Значение элемента цепочки
-1	-2
-2	-2
-3	-2
-4	-8
-5	-1
-6	-2
-7	-8
-8	-8
-9	-8
-10	-8
-11	-6
-12	-6
-13	-6
-14	-6
-15	-5
-16	-5
-17	-4
-18	-4
-19	-3
-20	-4

По мере нахождения новой точки контура в зависимости от того, каким было направление последнего вектора, увеличивается на единицу значение одной из переменных - EVENPERIM или ODDPERIM. В конце процедуры вычисляется и округляется до ближайшего целого значение периметра:

PERIMETER = EVENPERIM + ODDPERIM

Вычисление площади. Площадь, ограниченная контуром, вычисляется как сумма площадей, ограниченных элементарным вектором, вертикалями, проведенными через его концы, и подходящей горизонтальной линией (ей приписывают значение Y = 0). С учетом нумерации направлений векторов получается, что элементарные векторы с уменьшающейся компонентной х (-5, --4, --3) вносят в общую сумму положительные значения, а векторы с увеличивающейся компонентой х (--7, --8, --1) -- отрицательные (из рис. 1.4 видно, что Y имеет отрицательные значения). При таких условиях площадь, ограниченная контуром, прослеживаемым против часовой стрелки, будет иметь положительное значение.

На рис. 1.6 показан простой пример. Во избежание лишних манипуляций с коэффициентом 1/2 процедура EDGETRACE накапливает удвоенное значение площади (AREA2) и в конце вычислений делит его пополам.

Определение первых моментов площади и центроидов. Аналогичный метод используется для вычисления моментов ограниченной площади первого порядка относительно осей х и у. На рис. 1.7 показаны восемь элементарных векторов и первые моменты для площадей, заключенных между векторами и осью х (AW_X). Сумма всех компонент ДЛ/_Х для контура даст отрицательное целое число, которое после деления на значение ограниченной площади даст координату ее центра по оси у.

Выражение для АМ_Х в случае векторов с направлениями, имеющими нечетные номера, содержит постоянный член 1/6 или -1/6. В замкнутом контуре, состоящем из большого числа элементарных векторов, можно считать количества векторов всех направлений приблизительно одинаковым. Это приводит к взаимному уничтожению постоянных членов. Кроме того, постоянный член достаточно мал по сравнению с Y² и с площадью, особенно в том случае, когда объект рассматривается вблизи и его образ занимает большую часть поля зрения [17]. Поэтому можно упростить вычисления, пренебрегая постоянным членом.



Рисунок 1.5 - Приращения, вносимые элементарными векторами в значение площади, ограниченной контуром [8]

Таблица 1.3 - Значение площадей и приращений

Направление вектора	Приращение площади	Удвоенное приращение
-8	Y	2Y
-7	Y-1/2	2Y-1
-6	0	0
-5	(Y-1/2)(-1)	-2Y+1
-4	Y(-1)	-2Y
-3	(Y+1/2)(-1)	-2Y-1
-2	0	0
-1	Y+1/2	2Y+1

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 1.6 - Вычисление площади, ограниченной контуром

Таблица 1.4 - Нахождение суммарной площади

Номер элемента цепочки	Значение элемента цепочки	Удвоенное приращение	Удвоенная площадь
-1	-2	0	0
-2	-2	0	0
-3	-2	0	0
-4	-8	-8	-8
-5	-1	-7	-15
-6	-2	0	-15
-7	-8	-4	-19
-8	-8	-4	-23
-9	-8	-4	-31
-10	-8	0	-31
-11	-6	0	-31
-12	-6	0	-31
-13	-6	0	-31
-14	-6	+13	-31
-15	-5	+15	-18
-16	-5	+15	-3
-17	-4	+16	+13
-18	-4	+16	+29
-19	-3	+15	+44
-20	-4	+14	+58
Суммарная площадь = 29

Операций с коэффициентом 1/2 избегают так же, как при вычислении площади, - вычисляя значение 2 ДМ_Х. Это значение вычисляется удвоенной длины XMOMENT процедурой SUMXMOMENT.

При завершении процедуры EDGETRACE XMOMENT делится на значение AREA2. Округляя результат до ближайшего целого, получаем координату Y центра площади -- YCENTROID.

Точно так же, суммируя моменты площади относительно оси у получаем значение XCENTROID. На рис. 1.8 показаны значения, вносимые векторами различных направлений в суммарный момент.

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

Рисунок 1.7 - Моменты первого порядка относительно оси Х [8]

Таблица 1.5 - Значение моментов относительно оси Х

Направление вектора	Приращение площади	Удвоенное приращение
-8	Y2/2	Y2
-7	Y2/2- Y/2+1/6	Y(Y-1)
-6	0	0
-5	-Y2/2+ Y/2-1/6	Y(-Y+1)
-4	-Y2/2	Y2
-3	-Y2/2+ Y/2-1/6	Y(-Y+1)
-2	0	0
-1	Y2/2- Y/2+1/6	Y(Y-1)

Рисунок 1.8 - Моменты первого порядка относительно оси Y [8]

Таблица 1.6 - Значение моментов относительно оси Y

Направление вектора	Приращение площади	Удвоенное приращение
-8	0	0
-7	X2/2+X/2+1/6	X(X+1)
-6	X2/2	X2
-5	X2/2- X/2+1/6	X(X-1)
-4	0	0
-3	-X2/2+ X/2-1/6	X(-X+1)
-2	-X2/2	-X2
-1	-X2/2+ X/2-1/6	X(-X-1)

Матрица образа после процедуры EDGETRACE. Описанный алгоритм прослеживания границ, обрабатывая дифференцированную матрицу, обнуляет все просмотренные точки, но это не означает, что будут просмотрены и обнулены все точки контура. Оставшиеся в матрице единичные точки обычно не составляют полного контура и при последующих операциях выступают как "шумовые". Для минимизации их влияния должны предприниматься специальные меры. На рис. 1.9 показан вид матрицы образа FRAME после того, как процедура EDGETRACE обработала оба контура. Видны оставшиеся шумовые точки.

Идентификация отверстий - процедура INSIDE. Процедура INSIDE определяет, внутри или снаружи определенного контура лежит некоторая точка, принадлежащая матрице образа FRAME [18].

Предполагается, что контур, выделенный процедурой EDGETRACE, хранится в виде массива CHAIN и переменная CHAINCOUNT определяет его длину. Начальная точка цепочки задается целыми переменными PARTXSTART и PARTYSTART.



Рисунок 1.9 - Матрица изображения после прослеживания обоих границ [8]

Рисунок 1.10 - К теореме о пересечении прямой и замкнутой линии [8]

Координаты проверяемой точки вводятся в переменные STARTX и STARTY и вызывается логическая процедура-функция INSIDE. Она вырабатывает значение "истина", если проверяемая точка лежит внутри контура. При этом никакие значения в памяти не меняются.

Используемый алгоритм основан на следующей справедливой для плоскости теореме: если точка Р, лежащая вне замкнутой кривой S, соединена отрезком прямой с точкой Q, то точка Q тоже лежит вне кривой S тогда и только тогда, когда отрезок PQ пересекает кривую S четное число раз. Если PQ пересекает кривую S нечетное число раз, точка Q лежит внутри замкнутой кривой S (рис. 1.10). Доказательство приводится Курантом и Роббинсом.

В процедуре INSIDE упомянутый отрезок прямой проводится из проверяемой точки до края матрицы FRAME параллельно оси х, т.е. представляет собой часть луча Y = STARTY, X > STARTX. Пара локальных переменных (XCOORD и YCOORD) первоначально устанавливаются равными координатам начала хранимого контура. Из массива CHAIN последовательно считываются элементарные векторы. В зависимости от их значения модифицируются XCOORD и YCOORD (процедура UNCHAIN). Таким образом, XCOORD и YCOORD последовательно принимают значения координат всех точек, прослеженных в исходном контуре [19].

На каждом шаге проверяется, не лежит ли точка контура на луче У = STARTY, х > STARTX. Количество пересечений контура с этим лучом подсчитывается в целой переменной CROSSCOUNT. Множественные пересечения, когда линия контура совпадает с тестовым лучом в нескольких смежных точках, не учитываются. В момент вхождения линии контура в тестовый луч в переменной STRIKEDIRN записывается индекс направления вектора, входящего в луч. Для последующих точек, лежащих на луче, никаких действий не предпринимается. Когда очередной вектор контура выходит из тестового луча, текущее направление сравнивается со значением, записанным в STRIKEDIRN для проверки: был ли пересечен контуром тестовый луч (CROSSCOUNT увеличивается на единицу) или контур прошел касательно к лучу (CROSSCOUNT не меняется).

Когда все точки хранимого контура будут восстановлены, и проверены, проверяется значение CROSSCOUNT и процедура завершается с соответствующим результатом. Неоднозначные предельные случаи, когда проверяемые точки лежат на самом контуре, исключаются, т.к. в процессе прослеживания границы все такие точки обнулены.

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

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

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

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

Выделение особенностей контура. Модель контура представляет собой список -- цепочку векторов. Но сравнивать представленную такой моделью входную информацию с образцом, как это делает, например, Фримен, сложно и долго. Основная трудность заключается в том, что начальная точка цепочки, представляющей контур объекта, расположена на нем случайным образом. Ее конкретное положение зависит от ориентации объекта и направления сканирования при просмотре. Сравниваемые цепочки приходится циклически смещать относительно друг друга до совпадения. К сожалению, описание контура цепочкой векторов не слишком удобно для выполнения операции поворота на угол, не кратный 45 . Установление соответствия еще более затрудняется тем, что эталон и входная цепочка в общем случае состоят из различного числа элементарных векторов.

Разработан ряд методов сглаживания цепных списков и нормализации их длин, обеспечивающих возможность сравнения. Зах и Монтанари описали методы получения аппроксимаций с помощью прямых минимальной длины, снижающие объем данных, подлежащих обработке. Но эти методы слишком сложны для использования в системе автоматической сборки. В такой системе основное требование - не обеспечить 100%-ное совпадение, при сравнении модели контуров, выделенных из входного изображения, с эталонами, а подтвердить результаты пробных проверок и определить ориентацию объекта.

Требуется модель, которая позволит наиболее быстро и легко определять ориентацию объекта. Наиболее подходящим для такой модели может оказаться подход, основанный на выделении особенностей очеркового контура. Многие методы распознавания символов, например по Хоскингу, используют повторяющиеся особенности структуры штрихов, составляющих символ. Такими особенностями являются концы штрихов, точки их соединения или излома, петли. Аналогичными особенностями, характерными для материальных объектов, могут служить резкие изменения направления контура (углы) и точки, максимально и минимально удаленные от центра площади фигуры. К сожалению, отсутствие ограничений на форму деталей, с которыми приходится иметь дело роботу-сборщику, ограничивает ценность методов, использующих заранее составленный набор стандартных особенностей.

Модель с использованием окружностей. Угловые координаты радиус-векторов максимальной и минимальной длины могут служить удобным критерием распознавания объекта и средством определения его ориентации. Их значение выводится непосредственно из информации, генерируемой процедурой EDGETRACE. Но если в окрестности точки, экстремально удаленной от центра площади, длина радиус-вектора меняется мало (рис. 18), координаты R_MAX и R_MIN будут ненадежны. Из этого вытекает, что более целесообразно во время настройки системы задавать такие значения длины радиус-вектора R, для которых соответствующая позиция конечной точки может быть четко определена. По сути дела, это сводится к наложению на образ окружности заданного радиуса, центр которой совпадает с центром площади объекта. Точки пересечения этой окружности с контуром объекта используются как его особенности. На рис. 19 особые точки определяются параметрами R, 0,, в₂, в₃, в₄. Разности углов составляют инвариантный к ориентации набор параметров для распознавания, а их абсолютные значения могут использоваться для определения ориентации объекта.

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

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

- точки пересечения должны однозначно определять ориентацию объекта;

- количество точек пересечения не должно быть слишком большим (например, не больше восьми);

- для повышения точности измерений радиус должен быть по возможности большим;

- малые изменения длины радиуса не должны сильно влиять на угловые координаты точек пересечения;

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

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

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

Сравнение значений измеренных углов необходимо выполнять только в случае полного совпадения списков обозначений радиусов. Это упрощает процедуру сравнения. Когда установлено соответствие обоих списков, могут быть вычислены разности абсолютных угловых координат для каждой пары смежных точек пересечения. Эти шесть значений предназначены для определения ориентации одного объекта относительно другого. Еще одним свойством модели, использующей окружности, является возможность фиксировать случай, когда деталь лежит обратной стороной вверх. Таким образом, модель с использованием окружностей представляет собой мощное средство определения особых точек на очерковом контуре объекта произвольной формы. Эти точки могут использоваться при распознавании и определении ориентации. Размер памяти, используемой для хранения модели-эталона составляет всего два слова на каждую точку пересечения, а необходимые данные о сканируемой детали могут быть получены из информации, генерируемой процедурой EDGETRACE. В сочетании с моделью, использующей отверстия, она использовалась на низшем уровне распознавания и определения ориентации деталей в управляющей системе робота-сборщика.

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

2. МЕТОДЫ ИДЕНТИФИКАЦИИ ОБЪЕКТОВ В РОБОТИЗИРОВАННЫХ СИСТЕМАХ

2.1 Метод сравнения с эталоном

Идентификация объектов в СТЗ чаще всего производится методами сравнения с эталоном. При этом, как правило, СТЗ решают одну из двух задач. Первая задача заключается в получении изображения одного объекта и сравнении со всеми эталонами заданного класса. По совпадению выбирается наилучший эталон и осуществляется идентификация объекта, а затем при необходимости находятся параметры его положения и ориентации [20].

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

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

- эталон должен иметь правильный размер, иначе необходимо изготовить множество эталонов, отличающихся друг от друга лишь масштабным увеличением;

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

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

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

Брагин и Войлов [17] дают такую трактовку этого метода. Если обозначить исходное изображение объекта F(i, j), эталон Е (j, i), а вычисленное различие T, то процедуру сравнения можно формально записать как

; (2.1)

. (2.2)

Здесь индексы i и j характеризуют положение элементов в дискретном цифровом изображении.

Совпадение эталона с объектом проверяется по правилу

D?T, (2.3)

где D -- заданное пороговое различие.

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

Покажем особенности метода сравнения с эталонами при использовании некоторых систем признаков. Если в качестве признаков выбраны площадь и периметр изображения, размеры вписанных и описанных фигур, момент инерции и подобные геометрические свойства, то следует учесть масштабирование и на этапе предварительной обработки нормировать изображения по какому-либо параметру. Например, площадь описанного прямоугольника или окружности нормируется квадратом периметра изображения, а периметр -- значением корня квадратного из площади изображения [21].

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

Нередко полезно рассматривать три типа изображений аккумулятивной разности: абсолютное, положительное и отрицательное.

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

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

2.2 Методы теории графов и распознавание

При определении краев и контуров изображений применяют методы графов. Рассмотрим глобальный подход, основанный на представлении сегментов контура в виде графа и поиске на графе пути наименьшей стоимости, который соответствует значимым контурам, описанный в книге Брагина и Войлова [20] . Этот подход представляет приближенный метод, эффективный при наличии шума. Как и следует ожидать, эта процедура значительно сложнее и требует больше времени обработки, чем методы, изложенные выше.

Сначала дадим несколько простых определений. Граф G = (N, А) представляет собой конечное, непустое множество вершин N вместе с множеством А неупорядоченных пар различных элементов из N. Каждая пара из А называется дугой.

Граф, в котором дуги являются направленными, называется направленным графом. Если дуга выходит из вершины n_i, к вершине n_j, тогда n_j называется преемником вершины n_i. В этом случае вершина n_i называется предшественником вершины n_j. Процесс идентификации преемников каждой вершины называется расширением этой вершины. В каждом графе определяются уровни таким образом, чтобы нулевой уровень состоял из единственной вершины, называемой начальной, а последний уровень--из вершин, называемых целевыми. Каждой дуге (n_i n_j) приписывается стоимость c(n_i n_j). Последовательность вершин n₁, n₂, ..., n_k, где каждая вершина n_i является преемником вершины r_i-1, называется путем от n_i к n_k, а стоимость пути определяется формулой

. (2.4)

Элемент контура мы определим как границу между двумя пикселями р и q. В данном контексте под контуром понимается последовательность элементов контура.

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

Граф (или дерево) распознавания по геометрическим признакам представлен на рис….. Цифрами I, II, …, X обозначены возможные решения -- номера распознаваемых объектов. Буквы A, B, …, Q в вершинах графа обозначают операторы, выделяющие определенные признаки изображения. Например, оператор А проводит классификацию изображения по длине и высоте описанного прямоугольника, операторы В и С -- по площади, DEFG могут быть операторами, проводящими классификацию по числу углов, H и Q -- по отстоянию углов друг от друга. Граф может иметь больше или меньше уровней, и содержание операторов может быть различным.



Рисунок 2.1 - Дерево распознавания

2.3 Корреляционный метод

Модификацией метода сравнения с эталоном является корреляционный метод, основанный на вычислении взаимокорреляционной функции между эталоном и изображением.

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

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

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

Классификация изображений проводится по результату: чем больше значение функции взаимной корреляции, тем с большей вероятностью эталон совпадает с изображением. Используя обозначения, принятые в выражении, формулу для вычисления взаимокорреляционной функции К можно представить в виде

. (2.5)

Максимальное значение взаимокорреляционной функции равно,

(2.6)

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

, (2.7)

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

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

2.4 Распознавание через связь шаблонов

2.4.1 Поиск объектов указанием связей между шаблонами

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

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

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

Рассматриваемая тема не настолько хорошо изучена, чтобы к ней выработался какой-либо стандартный подход. В то же время основной вопрос достаточно очевиден -- как закодировать набор связей между шаблонами в форму, с которой легко работать. В данной главе изучается ряд различных подходов к данной задаче. Во-первых, каждый шаблон может указывать на объекты, которые он может представлять, а затем каким-то образом считается число указателей. Если построить некоторую явную вероятностную модель, для описания деталей пространственных отношений можно использовать больше весовых коэффициентов. Данную модель можно получить из функций правдоподобия; по сути, нужна функция распределения вероятностей, дающая большое значение, когда конфигурация компонентов подобна объекту, и малое -- в противном случае. Тогда поиск объектов превращается в поиск шаблонов, которые при подстановке в вероятностную модель дают большие значения. Нужно отметить, что следует внимательно относиться к сокращению поиска. Сложность этого подхода заключается в том, что даже при сокращении поиск может быть дорогим. Как утверждают Форсайт и Понс, в то же время при определенном классе вероятностных моделей можно провести эффективный поиск [21].

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

2.4.2 Описание фрагментов изображения

Небольшие фрагменты изображения могут иметь достаточно характерный вид, если имеют много ненулевых производных (например, в углах). Авторы [16] искали углы на изображении, часто именуемые точками интереса. Далее оценивался набор производных функции яркости в этих углах и набор производных, инвариантных относительно вращения, трансляции, определенного изменения масштаба и изменения освещения. Данные признаки назывались инвариантными локальными особенностями (invariant local jets).

Далее будем предполагать, что фрагменты изображения можно разбить на несколько классов. Представители каждого класса могут быть получены использованием нескольких изображений каждого объекта -- как правило, соответствующие фрагменты будут относиться к одному классу, но, возможно, вследствие шума иметь несколько отличающиеся инвариантные локальные потоки. Подходящий набор классов можно определить либо посредством ручной классификации фрагментов, либо посредством кластеризации фрагментов-образцов (несколько лучший метод). Теперь требуется определить, когда два набора инвариантных локальных потоков представляют один класс фрагментов изображения. Шмид (Schmid) и Mop (Mohr) для проверки использовали расстояние Махаланобиса (Mahalanobis distance) между векторами признаков тестируемого фрагмента и фрагмента-образца; если замер был меньше некоторого порога, тестируемый фрагмент считался идентичным образцу.

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

2.4.3 Указание признаков и простая порождающая модель

Пусть дано изображение, в котором находяться интересующие нас точки и в каждой точке изображения классифицируется фрагмент изображения. Возникает следующий вопрос: какие образы находятся в изображении? Для ответа на этот вопрос можно построить соответствие между фрагментами изображения и образами. Предположим, что всего на изображении имеется N_i фрагментов. Более того, предположим, что на изображении либо присутствует один образ из данной коллекции, либо ни одного. Отдельный фрагмент может порождаться либо единственным присутствующим образом, либо шумом. Впрочем, образы, как правило, содержат фрагменты не всех классов. Это означает, что утверждение о присутствии определенного образа равнозначно утверждению о том, что некоторые фрагменты изображения порождены шумом (поскольку может присутствовать только один образ, а имеются фрагменты изображения, которые принадлежат классам, не содержащимся в текущем образе).

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

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

2.4.4 Вероятностные модели для указания

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

Р{фрагмент i-гo типа есть на изображении | присутствует j-й образ} = p_ij

Р{фрагмент i-го типа | нет образа} = р_ix.

В простейшей модели предполагается, что для каждого образа j, p_ij = µ, если образ может породить данный фрагмент, и 0 -- в противном случае. Более того, предполагается, что р_ix = л < µ для всех i. Наконец, предполагается, что каждый наблюдаемый фрагмент на изображении может порождаться либо отдельным образом, либо шумом. Всего на изображении n_i фрагментов. При таких допущениях для вычисления функции правдоподобия нужно знать только, какие фрагменты порождены образом, а какие -- шумом. В частности, если взять функцию правдоподобия изображения при данном образе и предположить, что n_p фрагментов порождены данным образом, а n_p - n_i фрагментов порождены шумом, можно записать:

Р(интерпретация | образ) = , (2.8)

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

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

2.4.5 Доработка порождающей модели

Относительно просто учитывать все вышесказанное и соответствующим образом усовершенствовать простейшую модель (фрагменты появляются независимо при условии наличия образа). Предположим, что имеется N различных типов фрагментов. Форсайт и Понс [16] пишут, что фрагменты каждого типа генерируются со своей вероятностью всеми изображениями и шумом. Теперь предположим, что на изображении присутствует n_il экземпляров фрагментов l-го типа. Более того, n_k из них генерируется образом, а остальные -- шумом. Теперь поскольку фрагменты возникают независимо при данном образе и шум не зависит от образа, правдоподобие равно

Р(фрагменты порождены образом | j-й образ)

Р(фрагментов порождено шумом). (2.9)

Первый член равен

Р(тип 1 | j-й образ)"¹ Р(тип 2 | j-й образ)"² … (2.10)

Р(тип N | j-й образ)ⁿ_N^,Р(шум), (2.11)

что можно оценить как

(2.12)

Теперь предположим, что фрагменты порождаются шумом независимо друг от друга. Это означает, что шумовую составляющую можно записать следующим образом:

(2.13)

что можно оценить как

(2.14)

Это означает, что правдоподобие можно записать как

(2.15)

Для каждого типа фрагментов k возможны два случая: если p_kj > p_kx , то максимум достигается при n_k = n_ik; в противном случае максимум достигается при n_k = 0. Обозначим через р_i априорную вероятность того, что содержит j-й образ, а через р₀ -- априорную вероятность того, что оно не содержит ни одного объекта. Это означает, что для каждого типа образов j максимальное значение апостериорной вероятности запишется следующим образом:

(2.16)

где индекс m служит для подсчета значений признаков, для которых p_mj > р_mх, а l -- для подсчета значений признаков, для которых р_lj < p_lx. Данная величина формируется для каждого объекта, а затем выбирается та из них, которая имеет наибольшее апостериорное значение. Обратите внимание, что данная модель является реляционной, хотя в действительности мы не вычисляем геометрические признаки, связывающие образы. Это объясняется тем, что фрагменты связываются условными вероятностями их появления при данном образе, которые отличаются для разных образов.

2.4.6 Указание связей

Для улучшения простой стратегии указания можно использовать геометрические связи. Фрагмент сопоставляется с объектом, только когда с объектом сопоставлены соседние фрагменты и все эти фрагменты образуют подходящую конфигурацию. Термин "подходящая конфигурация" может быть источником сложностей, но предположим пока, что объекты сопоставлены с точностью до плоского вращения, трансляции и масштаба (это предположение разумно, например, для лиц анфас). Предположим теперь, что дан фрагмент, соответствующий некоторому объекту. Далее берем р ближайших фрагментов и проверяем, согласуется ли более 50% их с тем же объектом и совпадают ли углы между тройками согласованных фрагментов с соответствующими углами объекта -- все это называется полулокальными условиями. Если эти две проверки пройдены, указатель на объект, поданный этим фрагментом, регистрируется. Отметим, что вероятностную интерпретацию данного подхода построить довольно трудно -- вероятности появления фрагментов теперь зависят от того, где они расположены в образе, а также от того, какой образ их генерирует.

2.4.7 Указание на трехмерные объекты

Хотя подход Шмида и Мора был описан с позиции двумерных образов, его относительно просто расширить на распознавание трехмерных объектов. Для этого каждый набор проекций объекта Форсайт и Понс [16] рассматривают как иной двумерный образ. При наличии достаточного числа проекций этот подход работает, поскольку небольшие изменения в двумерном изображении, вызванные малыми изменениями угла наблюдения, будут компенсироваться разрешенным уровнем ошибок процесса согласования инвариантных локальных потоков и углов.

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

2.5 Искусственные нейронные сети и их использование при идентификации изображений

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

ИНС представляют собой систему соединённых и взаимодействующих между собой простых процессоров (искусственных нейронов). Такие процессоры обычно довольно просты, особенно в сравнении с процессорами, используемыми в персональных компьютерах. Каждый процессор подобной сети имеет дело только с сигналами, которые он периодически получает, и сигналами, которые он периодически посылает другим процессорам. И тем не менее, будучи соединёнными в достаточно большую сеть с управляемым взаимодействием, такие локально простые процессоры вместе способны выполнять довольно сложные задачи. Простая искусственная нейронная сеть представлена на рис. 2.2.

Рисунок 2.2 - Простая нейронная сеть

С точки зрения машинного обучения, нейронная сеть представляет собой частный случай методов распознавания образов, дискриминантного анализа, методов кластеризации и т. п. С математической точки зрения, обучение нейронных сетей -- это многопараметрическая задача нелинейной оптимизации. С точки зрения кибернетики, нейронная сеть используется в задачах адаптивного управления и как алгоритмы для робототехники. С точки зрения развития вычислительной техники и программирования, нейронная сеть -- способ решения проблемы эффективного параллелизма. А с точки зрения искусственного интеллекта, ИНС является основой философского течения коннективизма и основным направлением в структурном подходе по изучению возможности построения (моделирования) естественного интеллекта с помощью компьютерных алгоритмов.

Нейронные сети не программируются в привычном смысле этого слова, они обучаются. Возможность обучения -- одно из главных преимуществ нейронных сетей перед традиционными алгоритмами. Технически обучение заключается в нахождении коэффициентов связей между нейронами. В процессе обучения нейронная сеть способна выявлять сложные зависимости между входными данными и выходными, а также выполнять обобщение. Это значит, что в случае успешного обучения сеть сможет вернуть верный результат на основании данных, которые отсутствовали в обучающей выборке, а также неполных и/или «зашумленных», частично искаженных данных.

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

Топология такой сети характеризуется тем, что количество нейронов в выходном слое, как правило, равно количеству определяемых классов. При этом устанавливается соответствие между выходом нейронной сети и классом, который он представляет. Когда сети предъявляется некий образ, на одном из её выходов должен появиться признак того, что образ принадлежит этому классу. В то же время на других выходах должен быть признак того, что образ данному классу не принадлежит. Если на двух или более выходах есть признак принадлежности к классу, считается что сеть «не уверена» в своём ответе [22].

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

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

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