Техническое зрение роботов

Техническое зрение роботов

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_ix+b. Точность расположения этих точек на одной прямой зависит от числа разбиений плоскости аb. Отметим, что, если мы разбиваем ось а на К частей, тогда для каждой точки (x_k, у_k) мы получаем К значений b, соответствующих К возможным значениям а. Поскольку имеется п точек образа, процесс состоит из пК вычислительных операций. Поэтому приведенная выше процедура линейна относительно п и имеет меньшее число вычислительных операций, чем процедура, описанная выше, если К<= п.

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

xcosq+ysinq=b.            

Это представление  для построения таблицы собирающих элементов используется так же, как  метод, изложенный выше, но вместо прямых линий мы имеем синусоидальные кривые в плоскости qr. Как и прежде, М точек, лежащих на прямой xcosq_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, получаем, что оптимальный порог удовлетворяет уравнению