1.ВВЕДЕНИЕ

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

Эти системы можно отнести к классу «интеллектуальных» машин, если они обладают следующими признаками (призна­ками интеллектуального поведения):

1) возможностью выделения существенной информации из множества независимых признаков;

2) способностью к обучению на примерах и обобщению этих знаний с целью их применения в новых ситуациях;

3) возможностью восстановления событий по неполной ин­формации;

4) способностью определять цели и формулировать планы для достижения этих целей.

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

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

2.СЕГМЕНТАЦИЯ

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

2.1.Проведение контуров и определение границы

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

2.1.1.Локальный анализ.

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

При таком анализе для установления подобия пикселов кон­тура необходимо определить:

1 ) величину градиента, требуемого для построения контурного пиксела,

2) направление градиен­та.

Первая характеристика обозначается величинойG{f(x, у)] .

Таким образом, пиксел контура с координатами (х', у') подобен по величине в определенной ранее окрестности (х, у) пикселу с координатами (х, у), если справедливо неравенство

где Т — пороговое значение.

Направление градиента устанавливается по углу вектора градиента, определенного в уравнении

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

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

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

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

2.1.2.Глобальный анализ с помощью преобразования Хоуга.

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

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

Вычислительная привлекательность преобразования Хоуга заключается в разделении пространства параметров на так на­зываемые собирающие элементы , где (a_макс , а_мин ) и (b_макс , b_{м ин} )—допустимые величины параметров линий. Собирающий элементA (i, j) соответствует площади, связанной с ко­ординатами пространства параметров (а _i , b_j ). Вначале эти эле менты считаются равными нулю. Тогда для каждой точки (x_k , у _k ) в плоскости образа мы полагаем параметр а равным каж­дому из допустимых значений на оси а и вычисляем соответст­вующее b, используя уравнение b = - х _k + y _k Полученное значение b затем округляется до ближайшего допустимого зна­чения на оси b. Если выбор a_р приводит к вычислению b _q , мы полагаем А( р, q) == А( р, q) + 1. После завершения этой про­цедуры значение М в элементеA (i, j) соответствует М точкам в плоскости xy, лежащим на линииy= a_i x+b. Точность рас­положения этих точек на одной прямой зависит от числа раз­биений плоскости аb. Отметим, что, если мы разбиваем ось а на К частей, тогда для каждой точ­ки(x_k , у _k ) мы получаем К зна­чений b, соответствующих К воз­можным значениям а. Посколь­ку имеется п точек образа, про­цесс состоит из пК вычислитель­ных операций. Поэтому приве­денная выше процедура линейна относительно п и имеет меньшее число вычислительных опера­ций, чем процедура, описанная выше, если К<= п.

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

xc os q +y sin q = b .

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

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

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

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

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

.

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

2.2.Определение порогового уровня

Понятие порогового уровня (порога) тест вида

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

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

так что пикселы в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). Затем мы определяем пиксел как п иксел объекта, еслиd₁ ( z) >d ₂ (z ), или как пиксел фона, если d₂ (2) > d ₁ (z). Тогда оптимальный порог определяется величиной z, для которойd₁ { z)= d₂ (z ). Таким образом, полагая в уравнениях z=T, полу­чаем, что оптимальный порог удовлетворяет уравнению

P1 р1( T)= P2 p2(T).

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

Итак, если известны функциональные зависимости p₁ (z) и р ₂ (г),. это уравнение можно использовать для нахождения оптималь­ного порога, который отделяет объекты от фона. Если этот по рог известен, уравнение может быть использовано для сегментации данного образа.

2.2.3.Определение порогового уровня на основе характеристик границы.

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

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

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

ГрадиентG [f( x,y)] любой точки образа и лапласианL[f{ x, у)] . Эти два свойства можно использовать для фор­ мирования трехуровнего образа:

(где символы 0, +, - представляют три различных уровня осве­щенности, а Т— пороговый уровень. Предположим, что темный объект располагается на светлом фоне, тогда применение уравнения дает образs(x, у), в котором все пикселы, не лежащие на контуре (для них значе­ние G[f (х, у)] меньше Т, помечены 0, все пикселы на темной стороне контура помечены + и все пикселы на светлой стороне контура помечены —. Для светлого объекта на темном фоне символы + и- в уравнении (8.2-24) меняются местами.

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

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

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

2.2.4.Определение порогового уровня, основанное на нескольких переменных.

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


29-04-2015, 04:16