Реферат: Техническое зрение роботов

--PAGE_BREAK--2.1.2.Глобальный анализ с помощью преобразования Хоуга.
Рас­смотрим метод соединения граничных точек путем определения их расположения на кривой специального вида. Первоначально предполагая, что на плоскости ху образа дано п точек, требуется найти подпоследовательности точек, лежащих на прямых линиях. Одно из возможных решений состоит в построении всех линий, проходящих через каждую пару точек, а затем в нахож­дении всех подпоследовательностей точек, близких к определен­ным линиям. Задача, связанная с этой процедурой, заключается в нахождении п(п— 1)/2 ~ п2 линий и затем в осуществлении п[п(п—1)]/2 ~ п3сравнений каждой точки со всеми линиями. Этот процесс трудоемок с вычислительной точки зрения за ис­ключением самых простых приложений.

Данную задачу можно решить по-другому, применяя подход, предложенный Хоугом и называемый преобразованием Хоуга.Рассмотрим точку (хiyi) и общее уравнение прямой ли­нии у:= аxi+bi.Имеется бесконечное число линий, проходящихчерез точку(хiyi),но все они удовлетворяют уравнению у:= аxi+biпри различных значениях а и b. Однако, если мы за­пишем это уравнение в видеb = -хiа+yiи рассмотрим пло­скость а
b (пространство параметров), тогда мы имеем уравне­ние одной линии для фиксированной пары чисел (хiyi).Более того, вторая точка (хj,у
j)также имеет в пространстве пара­метров связанную с ней линию, которая пересекает другую ли­нию, связанную с точкой (хiyi) в точке (а',b’), где значения а' иb’—параметры линии, на которой расположены точки(хiyi)и (хj,уj)в плоскости ху. Фактически все точки, расположен­ные на этой линии, в пространстве параметров будут иметь ли­нии пересечения в точке (а',b’).

Вычислительная привлекательность преобразования Хоуга заключается в разделении пространства параметров на так на­зываемые собирающие элементы , где (aмакс, амин) и (bмакс, bмин)—допустимые величины параметров линий. Собирающий элементA (i, j)соответствует площади, связанной с ко­ординатами пространства параметров (аi,bj). Вначале эти элементы считаются равными нулю. Тогда для каждой точки(xk, уk) вплоскости образа мы полагаем параметр а равным каж­дому из допустимых значений на оси а и вычисляем соответст­вующее b,используя уравнение b= -хk+ykПолученное значение bзатем округляется до ближайшего допустимого зна­чения на оси b. Если выбор aр приводит к вычислению bq,мы полагаем А(р,q)==А(р,q)+ 1.После завершения этой про­цедуры значение М в элементеA (i, j)соответствует М точкам в плоскости xy, лежащим на линииy=
aix+b.Точность рас­положения этих точек на одной прямой зависит от числа раз­биений плоскости аb. Отметим, что, если мы разбиваем ось а на К частей, тогда для каждой точ­ки(xk, уk)мы получаем К зна­чений b, соответствующих К воз­можным значениям а. Посколь­ку имеется п точек образа, про­цесс состоит из пК вычислитель­ных операций. Поэтому приве­денная выше процедура линейна относительно п и имеет меньшее число вычислительных опера­ций, чем процедура, описанная выше, если К<= п.

Проблема, связанная с пред­ставлением прямой линии урав­нением у= ах+ b, состоит в том, что оба параметра а и b стремятся к бесконечности, если линия принимает вертикаль­ное положение. Для устранения этой трудности используется нормальное представление прямой линии в виде

xcos
q
+ysin
q
=b.            

Это представление для построения таблицы собирающих элементов используется так же, как метод, изложенный выше, но вместо прямых линий мы имеем синусоидальные кривые в плоскости q
r. Как и прежде, М точек, лежащих на прямойxcosqi+уsinqi==ri,соответствуют М синусоидальным кривым, кото­рые пересекаются в точке(q
i,ri)пространства параметров. Если используется метод возрастанияqи нахождения для него соот­ветствующего r, процедура дает М точек в собирающий элемент А(i, j), связанный с точкой (qi,ri).


2.1.3.Глобальный анализ с помощью методов теории графов.

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

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

Граф, в котором дуги являются направленными, называется на­правленным графом. Если дуга выходит из вершины ni,к вер­шине пj,тогда пjназывается преемником вершины ni. В этом случае вершинаn
iназывается предшественником вершины пj. Процесс идентификации преемников каждой вершины назы­вается расширением этой вершины. В каждом графе опреде­ляются уровни таким образом, чтобы нулевой уровень состоял из единственной вершины, называемой начальной, а последний уровень—из вершин, называемых целевыми. Каждой дуге (niпj)приписывается стоимостьc(niпj).Последовательность вер­шин п1,
n2,...,
nk,где каждая вершинаniявляется преемником вершиныri
-1,называется путем отn
iк пk,а стоимость пути определяется формулой

<img width=«120» height=«45» src=«ref-1_694657805-379.coolpic» v:shapes="_x0000_i1030">.

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


    продолжение
--PAGE_BREAK--2.2.Определение порогового уровня
Понятие порогового уровня (порога) тест вида


Т=Т [х, у, р (х, у),
f(х, у)],           

гдеf(x,у)—интенсивность в точке (х, у), р(х, у)—некоторое локальное свойство, определяемое в окрестности этой точки. Пороговое изображение дается следующим выражением:
<img width=«185» height=«48» src=«ref-1_694658184-572.coolpic» v:shapes="_x0000_i1031">

так что пикселы вg(x,у),имеющие значение1, соответствуют объектам, а пикселы, имеющие значение0, соответствуют фону. В уравнении предполагается, что интенсивность объек­тов больше интенсивности фона. Противоположное условие по­лучается путем изменения знаков в неравенствах.
2.2.1.Глобальные и локальные пороги.
Если значение Т в уравне­ниизависит только отf(x,у), то,  порог называется глобальным. Если значение Т зависит как отf(x,у), так и отр(х,у), порог называется локальным. Если, кроме того, Т зависит от пространственных координат х а у, в этом случае он называется динамическим порогом.

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

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

 2.2.2.Выбор оптимального порога.

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

p(z)=P1p1(z)+P2p2(z),             

где интенсивность z—случайная переменная величина,p1(z)и p2(z)—функции плотности вероятности,a P1иP2 –априорные вероятности. В данном случае априорные вероятности означают появление двух видов уровней интенсивности на образе. Полная гистограмма может быть аппроксимирована суммой двух функций плотности вероятности. Если известно, что объект состоит из светлых пиксе­лов и они занимают20 % площади образа, тоPi==
0,2.Необхо­димо, чтобы

Р1+Рг=1.                    

В данном случае это означает, что на остальную часть образа приходится80 % пикселов фона. Введем две следующие функции отz:


d1(z)=P1p1(z),

d2(z)=P1p1(z).

Из теории принятия решений известно, что средняя ошибка определения пиксела объекта в качестве фона (и на­оборот) минимизируется с помощью следующего правила: рас­сматривая пиксел со значением интенсивностиz, мы подстав­ляем это значениеz в уравнения(8.2-13) и(8.2-14). Затем мы определяем пиксел как пиксел объекта, еслиd1(z)>d2(z),или как пиксел фона, еслиd2(2) > d1(z). Тогда оптимальный порог определяется величинойz, для которойd1{z)=d2(z).Таким образом, полагая в уравненияхz=T,полу­чаем, что оптимальный порог удовлетворяет уравнению

P1р1(T)=P2p2(T).
<img width=«391» height=«223» src=«ref-1_694658756-16526.coolpic» v:shapes="_x0000_i1032">

рис. Гистограмма интенсивности (а) и ее аппроксимация в виде •суммы двух функций плотности вероятности (б).


Итак, если известны функциональные зависимостиp1(z)и р2(г),. это уравнение можно использовать для нахождения оптималь­ного порога, который отделяет объекты от фона. Если этот порог известен, уравнениеможет быть использовано для сегментации данного образа.
2.2.3.Определение порогового уровня на основе характеристик границы.
Одним из наиболее важных аспектов при выборе по­рогового уровня является возможность надежно идентифициро­вать модовые пики для данной гистограммы. Это важно при автоматическом выборе порогового уровня в ситуациях, когда характеристики образа меняются вследствие большого разброса интенсивности. Из изложенного выше очевидно, что возможность выбора «хорошего» порогового уровня может быть существенно увеличена в случае, если пики гистограмм являются высокими, узкими, симметричными и разделены глубокими провалами.

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

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

ГрадиентG[f(x,y)]любой точки образа и лапласианL[f{x,у)].Эти два свойства можно использовать для фор­мирования трехуровнего образа:
<img width=«309» height=«99» src=«ref-1_694675282-875.coolpic» v:shapes="_x0000_i1033">
(где символы0, +, - представляют три различных уровня осве­щенности, а Т—пороговый уровень. Предположим, что темный объект располагается на светлом фоне, тогда применение уравнения дает образs(x,у), в котором все пикселы, не лежащие на контуре (для них значе­ниеG[f(х, у)] меньше Т, помечены0, все пикселы на темной стороне контура помечены+ и все пикселы на светлой стороне контура помечены—. Для светлого объекта на темном фоне символы+ и— в уравнении(8.2-24) меняются местами.

Только что изложенная процедура может применяться для создания сегментированного, бинарного образа, в котором1 со­ответствует объектам, представляющим интерес, и0—фону. Отметим, что перемещение (вдоль горизонтальных или вер­тикальных линий сканирования) от светлого фона к темному объекту должно характеризоваться заменой знака- фона на -1- объектаs(x,у). Внутренняя область объекта состоит из пикселов, помеченных либолибо+. Окончательно перемещение от объекта к фону характеризуется заменой знака+ на —. Таким образом, горизонтальные или вертикальные линии сканирования, содержащие части объекта, имеют следующую структуру:

(...)(-,+)(0 или+)(+, -)(•••),

где(...) является произвольной комбинацией+, - или0. Остальные скобки содержат точки объекта и помечены1. Вседругие пикселы вдоль той же линии сканирования помечаются , за исключением всех последовательностей из(0 или+), огра­ниченных(-, +) и(+, -).
    продолжение
--PAGE_BREAK--2.2.4.Определение порогового уровня, основанное на нескольких переменных.
Изложенные выше методы связаны с определением порогового уровня для единст­венного переменного значения интенсивности. В некоторых приложениях можно исполь­зовать более одной перемен­ной для характеристики каждо­го пиксела образа, увеличивая таким образом не только сте­пень различия между объек­том и фоном, но и между сами­ми объектами. Одним из наи­более значимых примеров явля­ется цветное зрение, где исполь­зуются красные, зеленые и голубые компоненты (КЗГ) для формирования составно­го цветного образа. В этом случае каждый пиксел характеризуется тремя переменными и это позволяет строить трехмерную гистограмму. Основнаяпроцедура та же, что и для одной переменной. Пусть, например, даны три 16-уровневых изображения, соответствующие КЗГ компонентам датчика цвета. Сформируем кубическую решетку 16х16х16 и поместим в каждый элемент пикселы, КЗГ ком­поненты которых имеют интенсивности, соответствующие коор­динатам, определяющим положение этого элемента. Число то­чек в каждом элементе решетки может быть затем разделено на общее число пикселов образа для формирования нормированной гистограммы.

Теперь выбор порога заключается в нахождении групп точек в трехмерном пространстве, где каждая «компактная» группа аналогична основной моде гистограммы одной переменной. На­пример, предположим, что мы ищем две значимые группы точек данной гистограммы, где одна группа соответствует объекту, а другая—фону. Принимая во внимание, что теперь каждый пик­сел имеет три компоненты и может быть рассмотрен как точка трехмерного пространства, можно сегментировать образ с по­мощью следующей процедуры. Для каждого пиксела образа вычисляется расстояние между этим пикселом и центром каж­дой группы. Тогда, если пиксел располагается рядом с центром группы точек объекта, мы помечаем его1; в противном случае мы помечаем его0. Это понятие легко распространить на боль­шую часть компонентов пиксела и соответственно на большую часть групп. Основная сложность состоит в том, что определение значимых групп, как правило, приводит к довольно сложной задаче, поскольку число переменных возрастает.


2.3.Областно-ориентированная сегментация 2.3.1.Основные определения.
Целью сегментации является разде­ление образа на области. Рассмотрим методы сегмен­тации, основанные на прямом нахождении областей.

ПустьR—область образа. Рассмотрим сегментацию как процесс разбиенияR на nподобластейR1, R2,...,
Rn,так что

1.       <img width=«67» height=«43» src=«ref-1_694676157-293.coolpic» v:shapes="_x0000_i1034">

2.
       Pi—связная область,i=1, 2, ...,п,

3.       Ri <img width=«12» height=«45» src=«ref-1_694676450-180.coolpic» v:shapes="_x0000_i1035"> Ri=<img width=«17» height=«19» src=«ref-1_694676630-210.coolpic» v:shapes="_x0000_i1036"> для всехiиj,i
<img width=«15» height=«15» src=«ref-1_694676840-190.coolpic» v:shapes="_x0000_i1037"> j,

4.       P(Ri)есть ИСТИНА дляi=1, 2, ...,n;

5.       P(Ri U Ri)есть ЛОЖЬ дляi <img width=«15» height=«15» src=«ref-1_694676840-190.coolpic» v:shapes="_x0000_i1038">j,гдеP(Ri)— логический предикат, определенный на точках из множестваRi,и<img width=«17» height=«19» src=«ref-1_694676630-210.coolpic» v:shapes="_x0000_i1039"> -пу­стое множество.

Условие1 означает, что сегментация должна быть полной, т. е. каждый пиксел должен находиться в образе. Второе усло­вие требует, чтобы точки в области были связными. Условие3 указывает на то, что области не должны пересекать­ся. Условие4 определяет свойства, которым должны удовлетво­рять пикселы в сегментированной области. Простой пример: Р
(Ri) = ИСТИНА, если все пикселы вRiимеют одинаковую интенсивность. Условие5 означает, что областиRi иRi разли­чаются по предикату Р.

2.3.2.Расширение области за счет объединения пикселов.

Расшире­ние области сводится к процедуре группирования пикселов или подобластей в большие объединения. Простейшей из них яв­ляется агрегирование пикселов. Процесс начинается с выбора множества узловых точек, с которых происходит расширение области в результате присоединения к узловым точкам сосед­них пикселов с похожими характеристиками (интенсивность, текстура или цвет). Пусть цифры внутри ячеек указывают интенсивность. Пусть точки с координатами(3, 2) и (3, 4) используются как узловые. Выбор двух начальных точек приведет к сегментации образа на две области: областиR1, свя­занной с узлом(3, 2), и областиR2, связанной с узлом(3, 4). Свойство Р, которое мы будем использовать для того, чтобы от­нести пиксел к той или иной области, состоит в том, что модуль разности между интенсивностями пиксела и узловой точки не превышает пороговый уровень Т. Любой пиксел, удовлетворяю­щий этому свойству одновременно для обоих узлов, произвольно попадает в областьRi. В этом случае сегментация проводится для двух областей, причем точки вR1 обозначаются буквой а, точки вR
2 буквой b.Необходимо отметить, что независимо от того, в какой из этих двух областей будет взята начальная точка, окончательный результат будет один и тот же. Если, с другой сто­роны выбрать Т=8, была бы получена единственная область

Предыдущий пример, не­смотря на его простоту, иллюстрирует некоторые важные проблемы расширения области.Двумя очевидными проблема­ми являются: выбор начальных узлов для правильного представления областей, представляющих интерес, и опреде­ление подходящих свойств для  включения точек в различные области в процессе расшире­ния. Выбор множества, состоя­щего из одной или нескольких начальных точек, следует из по­становки задачи. Например, в военных приложениях объек­ты, представляющие интерес, имеют более высокую темпера­туру, чем фон, и поэтому про­являются более ярко. Выбор наиболее ярких пикселов явля­ется естественным начальным шагом в алгоритме процесса расширения области. При от­сутствии априорной информа­ции можно начать с вычисле­ния для каждого пиксела на­бора свойств, который навер­няка будет использован при установлении соответствия пик­села той или иной области в процессе расширения. Если ре­зультатом вычислений являют­ся группы точек (кластеры), тогда в качестве узловых бе­рутся те пикселы, свойства ко­торых близки к свойствам центроидов этих групп. Так, в примере, приведенном выше, гистограмма интенсивностей показала бы, что точки с интен­сивностью от одного до семи являются доминирующими.Выбор критерия подобия зависит не только от задачи, но также от вида имеющихся данных об образе. Например, анализинформации, полученной со спутников, существенно зависит от использования цвета. Задача анализа значительно усложнится при использовании только монохроматических образов. К сожа­лению, в промышленном техническом зрении возможность полу­чения мультиспектральных и других дополнительных данных об образе является скорее исключением, чем правилом. Обычно анализ области должен осуществляться с помощью набора дес­крипторов, включающих интенсивность и пространственные ха­рактеристики (моменты, текстуру) одного источника изображе­ния. Отметим, что применение только одних дескрипторов может приводить к неправильным результатам, если не используется информация об условиях связи в процессе расширения области. Это легко продемонстрировать при рассмотрении случайного рас­положения пикселов с тремя различными значениями интенсив­ности. Объединение пикселов в «область» на основе признака одинаковой интенсивности без учета условий связи приведет к бессмысленному результату при сегментаци.

Другой важной проблемой при расширении области является формулировка условия окончания процесса. Обычно процесс расширения области заканчивается, если больше не существует пикселов, удовлетворяющих критерию принадлежности к той или иной области. Выше упоминались такие критерии, как интен­сивность, текстура и цвет, которые являются локальными по своей природе и не учитывают «историю» процесса расширения области. Дополнительный критерий, повышающий мощность алгоритма расширения области, включает понятие размера, схо­жести между пикселом-кандидатом и только что созданными пикселами (сравнение интенсивности кандидата и средней ин­тенсивности области), а также формы области, подлежащей расширению. Использование этих типов дескрипторов основано на предположении, что имеется неполная информация об ожи­даемых результатах.
    продолжение
--PAGE_BREAK--2.3.2.Разбиение и объединение области.
Изложенная выше про­цедура расширения области начинает работу с заданного мно­жества узловых точек. Однако можно сначала разбить образ на ряд произвольных непересекающихся областей и затем объ­единять и/или разбивать эти области с целью удовлетворения условий. Итеративные алгоритмы разбиения и объединения, работа которых направле­на на выполнение этих ограничений, могут быть изложены сле­дующим образом.

ПустьRявляется полной областью образа, на которой опре­делен предикат Р. Один из способов сегментацииR состоит в успешном разбиении площади образа на все меньшие квадрат­ные области, так что для каждой областиRi
, P(Ri)=ИСТИНА. Процедура начинает работу с рассмотрения всей области R
. Если Р(R)=ЛОЖЬ, область разбивается на квадранты. Если для какого-либо квадранта Р принимает значение ЛОЖЬ, этот квадрант разбивается на подквадранты и т. д. Этот метод разбиения обычно представляется в виде так называемого квадродерева (дерева, у которого каждая вершина имеет только че­тыре потомка). Отметим, что корень дерева соответствует всему образу, а каждая вершина— разбиению. В данном случае только R4подлежит дальнейшему разбиению. Если применять только опе­рацию разбиения, можно ожидать, что в результате окончатель­ного разбиения всей площади образа на подобласти последние будут иметь одинаковые свойства. Это можно устранить допу­стимым объединением так же, как и разбиением. Для того чтобы удовлетворить условиям сегментации, введенным выше, необ­ходимо объединять только те соседние области, пикселы которых удовлетворяют предикату Р, таким образом, две соседние обла­стиRiиRkобъединяются только в том случае, если P(RiURk) =ИСТИНА.

Изложенное выше можно представить в виде процедуры, где на каждом шаге выполняются следующие операции:

1.       Разбиение областиRi,для которой Р{Ri)=ЛОЖЬ, на четыре непересекающихся квадранта.

2.       Объединение соседних областейRiиRk, для которых Р(Ri URk) = ИСТИНА.

3.       Выход на останов, когда дальнейшее объединение илиразбиение невозможно.

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


2.4. Применение движения
Движение представляет собой мощное средство, которое ис­пользуется человеком и животными для выделения интересую­щих их объектов из фона. В системах технического зрения ро­ботов движение используется при выполнении различных операций на конвейере, при перемещении руки, оснащенной дат­чиком, более редко при перемещении всей робототехнической системы.
2.4.1.Основной подход.
Один из наиболее простых подходов для определения изменений между двумя кадрами изображения (образами)f(x,у,
ti)иf(x,у,
t,),взятыми соответственно в моменты времениti иtj,основывается на сравнении соответ­ствующих пикселов этих двух образов. Для этого применяется процедура, заключающаяся в формировании так называемой разности образов.

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

Разность между двумя кадрами изображения, взятыми в мо­менты времениti иtj,можно определить следующим образом:
dij(x,y) = <img width=«227» height=«48» src=«ref-1_694677430-643.coolpic» v:shapes="_x0000_i1040">       (*)
гдеq—значение порогового уровня. Отметим, чтоdij(x,у)при­нимает значение1 для пространственных координат (х, у) только в том случае, если два образа в точке с этими координа­тами существенно различаются по интенсивности, что опреде­ляется значением порогового уровняq.

При анализе движущегося образа все пикселы изображений разностиdij(x,у),имеющие значение1, рассматриваются как результат движения объекта. Этот подход приметим только в том случае, если два образа зарегистрированы и освещен­ность имеет относительно постоянную величину в пределах границ, устанавливаемых пороговым уровнемq.На практике записи вdij(x,у),имеющие значение1, часто появляются в ре­зультате действия шума. Обычно на разности двух кадров изо­бражения такие значения выглядят как изолированные точки. Для их устранения применяется простой подход, заключающийся в формировании4- или 8-связных областей из единиц вdij(x,у), и затем пренебрегают любой областью с числом записей, мень­шим заранее заданного. При этом можно не распознать малые и/или медленно движущиеся объекты, но это увеличивает ве­роятность того, что остающиеся записи в разности двух кадров изображения действительно соответствуют движению.
    продолжение
--PAGE_BREAK--2.4.2.Аккумулятивная разность.
Как говорилось выше, разность кадров благодаря шуму часто содержит изолированные записи. Несмотря на то что число таких записей может быть сокращено или полностью ликвидировано в результате анализа связности пороговых уровней, этот процесс может также привести к по­тере изображений малых или медленно движущихся объектов. Ниже излагается подход для решения этой проблемы путем рассмотрения изменения в расположении пикселов на несколь­ких кадрах, т. е. в процесс вводится «память». Основная идея заключается в пренебрежении теми изменениями, которые воз­никают случайно в последовательности кадров и, таким образом, могут быть отнесены к случайному шуму.

Рассмотрим   последовательность   кадров   изображения f
(x,y,t1),
f(x,у,t2), ...,
f(x,у,
tn)и допустим, чтоf(x,у,
t1) является эталонным образом. Изображение аккумулятивной разности формируется в результате сравнения эталонного об­раза с каждым образом в данной последовательности. В процедуре построения изображения аккумулятивной разности имеется счетчик, предназначенный для учета расположения пик­селов. Его значение увеличивается каждый раз, когда возникает различие в расположении соответствующих пикселов эталон­ного образа и образа из рассматриваемой последовательности. Таким образом, когдаk-йкадр сравнивается с эталонным, запись в данном пикселе аккумулятивней разности означает, во сколько раз интенсивность пикселаk-го кадра отличается от ин­тенсивности пиксела эталонного образа. Различия устанавли­ваются, например, с помощью уравнения(*).

Приведенные выше рассуждения иллюстрируются рисунке. На рисунке а—д приведены образы прямоугольного объекта (обозначенного нулями), движущегося вправо с постоянной ско­ростью1 пиксел/кадр. Эти образы приведены в моменты вре­мени, соответствующие одному перемещению пиксела. На рис. (а) изображен кадр эталонного образа, на рис.(г) со 2-го по 4-й кадры последовательности, а на рис. (д)— 11-й кадр. Рис.(е— и) соответствуют изображениям аккумулятив­ной разности, которые можно объяснить следующим образом. На рис.(е) левая колонка из1 обусловлена различием между объектом на рис.(а), и фоном на рис.(б). Правая колонка из1 вызвана различием между фоном эталонного образа и пе­редним контуром движущегося объекта. Ко времени появления4-го кадра (рис.г), первый ненулевой столбец изображе­ния аккумулятивной разности указывает на три отсчета, что со­ответствует трем основным различиям между этим столбцом в эталонном образе и соответствующим столбцом в последующихкадрах. На рис.и показано общее число из10 (представ­ленных «A» в шестнадцатеричной системе счисления) изменений этого положения. Остальные записи на этом рисунке объясня­ются аналогично.

Нередко полезно рассматривать три типа изображений акку­мулятивной разности: абсолютное, положительное и отрица­тельное. Последние два получаются из уравнения(*), вкотором нет модуля, а вместоf(x,у,
ti)подставляется значение эталонного кадра. Предполагая, что числовые значения интен­сивности объекта превышают значения фона в случае, когда разность положительна, она сравнивается с положительным значением порогового уровня; если отрицательна, сравнение выполняется с отрицательным значением порогового уровня. Это определение заменяется на противоположное, если интенсив­ность объекта меньше фона.

Рис.Кадр эталонного образа (а), б—д соответственно2-, 3-, 4- и11-й кадры, е—и—изображения аккумулятивной разности для2-, 3-, 4- и 11-го кадров.



9













10

00000000











11

00000000











12

00000000









a

13

00000000











14

00000000











15

00000000











16













9



9









10

00000000

10

1

1





11

00000000

11

1

1





12

00000000

12

1

1

е

б

13

00000000

13

1

1





14

00000000

14

1

1





15

00000000

15

1

1





16



16









9



9









10

00000000

10

21

21





11

0000000C

11

21

21



в

12

0000000C

12

21

21

ж



 13

0000000C

13

21

21





14

00000000

14

21

21





15

00000000

15

21

21





16



16









9



9









10

00000000

10

321

321





11

00000000

11

321

321



г

12

00000000

12

321

321

з



13

00000000

13

321

321





14

00000000

14

321

321





15

00000000

15

321

321





16



16









9



9









10

0000000

10

A9876

5438887654321





11

00000000

11

A9876

5438887654321





12

00000000

12

A9876

5438887654321



д

13

00000000

13

A9876

5438887654321

и



14

00000000

14

A9876

5438887654321





15

00000000

15

A9876

543888.7654321





16



16








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

На практике не всегда можно получить эталонный образ, имеющий только стационарные элементы, и это приводит к не­обходимости построения эталона из набора образов, содержа­щих один или более движущихся объектов. Это особенно харак­терно для ситуаций, описывающих сцены со многими быстро­меняющимися объектами или в случаях, когда возникают частые изменения сцен. Рассмотрим следующую процедуру гене­рации эталонного образа. Предположим, что мы рассматриваем первый образ последовательности в качестве эталонного. Когда нестационарная компонента полностью вышла из своего положе­ния в эталонном кадре, соответствующий фон в данном кадре может быть перенесен в положение, первоначально занимаемое объектом в эталонном кадре. Когда все движущиеся объекты полностью покинули свои первоначальные положения, в резуль­тате этой операции воссоздается эталонный образ, содержащий только стационарные компоненты. Перемещение объекта можно определить с помощью операции расширения положительного изображения аккумулятивной разности.
3.ОПИСАНИЕ
В системах технического зрения проблемой описания назы­вается выделение свойств (деталей) объекта с целью распозна­вания. В идеальном случае дескрипторы не должны зависеть от размеров, расположения и ориентации объекта, но должны содержать достаточное количество информации для надежной идентификации объектов. Описание является основным резуль­татом при конструировании систем технического зрения в том смысле, что дескрипторы должны влиять не только на слож­ность алгоритмов распознавания, но также и на их работу. рассмотрим три основные катего­рии дескрипторов: дескрипторы границы, дескрипторы области и дескрипторы для описания трехмерных структур.
3.1.Дескрипторы границы. 3.1.1.Цепные коды.
Цепные коды применяются для представления границы в виде последовательности отрезков прямых линий определенной длины и направления. Обычно в основе этого представления лежит4- или 8-связная прямоугольная решетка. Длина каждого отрезка определяется разрешением решетки, а направления задаются выбранным кодом. Отметимчто для представления всех направлений в 4-направленном цеп­ном коде достаточно2 бит, а для 8-направленного цепного кода требуется3 бит. Для порождения цепного кода заданной границы сначала выбирается решетка. Тогда, если площадь ячейки, расположенной внутри границы, больше определенного числа (обычно50%), ей присваивается значение1; в противном слу­чае этой ячейке присваивается значение0. Окон­чательно мы кодируем грани­цу между двумя областями, используя направления.Результат кодирования в на­правлении по часовой стрелке с началом в месте, помеченном точкой. Альтернативная    процедура состоит в разбиении границы на участки равной длины (каждый участок имеет одно и то же число пикселов) и соединении   граничных  точек

каждого участка прямой линией,а затем присваивания каждой линии направления, ближайшего к одному из допустимых направлений цепного кода. Важно отметить, что цепной код данной границы зависит от начальной точки. Однако можно нормировать код с помощью простой процедуры. Для создания цепного кода начальная точка на решетке выбирается произвольным образом. Рассмат­ривая цепной код как замкнутую последовательность индексов направлений, мы вновь выбираем начальную точку таким обра­зом, чтобы результирующая последовательность индексов была целым числом, имеющим минимальную величину. Также можно нормировать повороты, если вместо цепного кода рассматри­вать его первую разность. Первая разность вычисляется в ре­зультате отсчитывания (в направлении против часовой стрелки)' числа направлений, разделяющих два соседних элемента кода. Например, первая разность для цепного кода с4 направле­ниями10103322 есть3133030. Если рассматривать код как зам­кнутую последовательность, тогда первый элемент разности можно вычислить, используя переход между последним и пер­вым компонентами цепи. В данном примере результатом яв­ляется33133030. Нормирование можно осуществить путем раз­биения всех границ объекта на одинаковое число равных сег­ментов и последующей подгонкой длин сегментов кода с целью их соответствия этому разбиению.

Изложенные методы нормирования являются точными толь­ко в том случае, когда сами границы инвариантны к повороту и изменению масштаба. Этот случай редко встречается на прак­тике. Например, один и тот же объект, разбитый на элементы в двух различных направлениях, как правило, имеет разную форму границы, причем степень различия пропорциональна раз­решающей способности изображения. Этот эффект можно умень­шить, если выбирать длины элементов цепи большими, чем рас­стояния между пикселами дискретного образа, или же выбирать ориентацию решетки  вдоль главных осей кодируе­мого объекта.
3.1.2.Сигнатуры.
Сигнатурой называется одномерное функциональ­ное представление границы. Известно несколько способов соз­дания сигнатур. Одним из наиболее простых является построе­ние отрезка из центра к границе как функции угла. Очевидно, что такие сигнатуры зависят от периметра области и начальной точки. Нормирование периметра можно осуществить, пронормировав кривую r(q) максимальным значением. Пробле­му выбора начальной точки можно решить, определив сначала цепной код границы, а затем применив метод, изложенный в пре­дыдущем разделе. Конечно, расстояние, зависящее от угла, не является единственным способом определения сигнатуры. Напри­мер, можно провести через границу прямую линию и определить угол между касательной к границе и этой линией как функциюположения вдоль границы. Полученная сигнатура, хотя и от­личается от кривойr(q), несет информацию об основных харак­теристиках формы границы. Например, горизонтальные участки кривой соответствовали бы прямым линиям вдоль границы, по­скольку угол касательной здесь постоянен. Один из вариантов этого метода в качестве сигнатуры использует так называемую функцию плотности наклона. Эта функция представляет со­бой гистограмму значений угла касательной. Поскольку гисто­грамма является мерой концентрации величин, функция плотно­сти наклона строго соответствует участкам границы с постоян­ными углами касательной (прямые или почти прямые участки и имеет глубокие провалы для участков, соответствующих быст­рому изменению углов (выступы или другие виды изгибов).
    продолжение
--PAGE_BREAK--3.1.3.Аппроксимация многоугольниками.
Дискретную границу с произвольной точностью можно аппроксимировать многоуголь­никами. Для замкнутой кривой аппроксимация является точ­ной, когда число сегментов в многоугольнике равно числу точек границы, так что каждая пара соседних точек определяет сег­мент многоугольника. На практике целью аппроксимации мно­гоугольниками является качественное определение формы гра­ницы с помощью минимального числа многоугольных сегментов. Хотя обычно эта проблема нетривиальна и довольно быстро сво­дится к итеративному поиску, требующему больших временных затрат, имеется ряд методов аппроксимации многоугольниками, относительная простота которых и требования к обработке дан­ных делают их пригодными для приложений в области техниче­ского зрения роботов.

В задаче аппроксимации многоугольниками применяются м
етоды объединения, основанные на ошибке или других крите­риях. Один из подходов состоит в соединении точек границы линией по методу наименьших квадратов. Линия проводится до тех пор, пока ошибка аппроксимации не превысит ранее задан­ный порог. Когда порог превышается, параметры линии зано­сятся в память, ошибка полагается равной нулю и процедура повторяется; новые точки границы соединяются до тех пор, пока ошибка снова не превысит порог. В конце процедуры образу­ются вершины многоугольника в результате пересечения сосед­них линий. Одна из основных трудностей, связанная с этим под­ходом, состоит в том, что эти вершины обычно не соответствуют изгибам границы (таким, как углы), поскольку новая линия начинается только тогда, когда ошибка превысит порог. Если, например, длинная прямая линия пересекает угол, то числом (зависящим от порога) точек, построенных после пересечения, можно пренебречь ранее, чем будет превышено значение поро­гового уровня. Однако для устранения этой трудности наряду с методами объединения можно использовать методы разбиения.

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

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

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

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

Связнойназывается область, в которой любая пара точек может быть соединена кривой, полностью лежащей в этой об­ласти. Для множества связных областей (некоторые из них имеют отверстия) в качестве дескриптора полезно использовать число Эйлера, которое определяется как разность между числом связных областей и числом отверстий. Например, числа Эйлера для букв А и В соответственно равныи—1. Другие дескрип­торы области рассматриваются ниже.
3.2.2.Текстура.
Во многих случаях идентификацию объектов или областей образа можно осуществить, используя дескрипторы текстуры. Хотя не существует формального определения тек­стуры, интуитивно этот дескриптор можно рассматривать как описание свойств поверхности (однородность, шероховатость, ре­гулярность). Двумя основными подходами для описания текстуры являются стати­стический и структурный. Статистические методы дают такие характеристики текстуры, как однородность, шероховатость, зер­нистость и т. д. Структурные методы устанавливают взаимное расположение элементарных частей образа, как, например, опи­сание текстуры, основанной на регулярном расположении па­раллельных линий.
3.2.3.Скелет области.
Важным подходом для описания вида струк­туры плоской области является ее представление в виде графа. Во многих случаях для этого определяется схема (скелет) об­ласти с помощью так называемых прореживающих (или же сокращающих) алгоритмов. Прореживающие процедуры иг­рают основную роль в широком диапазоне задач компьютерного зрения— от автоматической проверки печатных плат до под­счета асбестовых волокон в воздушных фильтрах. Скелет об­ласти можно определить через преобразование средних осей (ПСО), предложенное в работе. ПСО областиRс грани­цей В определяется следующим образом. Для каждой точки р изR мы определяем ближайшую к ней точку, лежащую на В. Если р имеет больше одной такой точки, тогда о ней говорится, что она располагается на средней оси (скелете) областиR. Важно отметить, что понятие «ближайшая точка» зависит от определения расстояния, и поэтому на результаты операции ПСО будет влиять выбор метрики. Хотя ПСО дает довольно удовлетворительный скелет обла­сти, его прямое применение затруднительно с вычислительной точки зрения, поскольку требуется определение расстояния между каждой точкой области и границы. Был предложен ряд алгоритмов построения средних осей, обладающих большей вычислительной эффективностью. Обычно это алгоритмы про­реживания, которые итеративно устраняют из рассмотрения точки контура области так, чтобы выполнялись следующие ограничения:

1)       не устранять крайние точки;

2)       не приводить к нарушению связности;

3)                 не вызывать чрезмерного размывания области.


    продолжение
--PAGE_BREAK--