Применение преобразования Хафа требует дискретизации пространства параметров. Оно разбивается на аккумулирующие (суммирующие) ячейки подходящего размера. Внесение значений в эти ячейки выполняется в ходе анализа соответствующего пикселя пространства изображений. Пиксель соотносится с кривой в пространстве параметров (она представляет все прямые, проходящие через рассматриваемый пиксель в пространстве изображений). В дальнейшем инкрементируются значения тех аккумулирующих ячеек, через которые проходит кривая. Выполняя указанные действия для всех отмеченных пикселей пространства изображений, можно заметить, что некоторые из аккумулирующих ячеек получают значительные приращения (т.е. за них отдано много “голосов”), а другие – нет. Количество голосов в позициях, где наблюдаются максимумы, можно рассматривать как подтверждение того, что в пространстве изображений имеется прямая линия. Формируемая прямая имеет бесконечную протяженность. Алгоритм можно модифицировать так, чтобы пиксели пространства изображений, которые внесли вклад в обнаружение прямой (т.е. обеспечили формирование пика в пространстве параметров), запоминались. Тогда “формирующие элементы” прямой линии из пространства изображений будут известны, что позволит установить конечные точки прямой.
Рассмотрим пример обнаружения кругов на изображении. Будем опять анализировать два пространства: пространство изображений и пространство параметров, которое в данном случае трехмерное (рисунок 10.23). Уравнение окружности в пространстве изображений имеет вид:
(x1 xc)2 (y1 yc)2 r2.
В этом случае точке (x1, y1) пространства изображений соответствует коническая поверхность в пространстве параметров. Каждая из точек конической поверхности представляет набор параметров, которые определяют круг с центром в соответствующей точке пространства изображений. И наоборот, если рассматривается некоторый круг в пространстве изображений, то он соответствует точке с координатами (xc1,yc1,r1) в пространстве параметров. Дискретизация пространства параметров выполняется аналогично случаю обнаружения прямых линий.
Необходимо отметить, что в вычислительном отношении преобразование Хафа весьма затратное для случая обнаружения кругов. Если дополнительно определять направление градиента в каждой точке пространства изображений, то можно получить более эффективный алгоритм. Это позволяет ограничить число аккумулирующих ячеек в пространстве параметров, которые требуют модификации.
Компьютерное зрение
581
Рисунок 10.23 – Обнаружение кругов с помощью преобразования Хафа
Можно спросить, действительно ли преобразование Хафа помогает воссоздавать сложные структуры по примитивным элементам? Ответ - да. Но способ, которым это выполняется, в корне отличается от биологического подхода. Принципы перцептивного группирования – параллелизм, геометрическая близость, коллинеарность – не играют никакой роли при выполнении преобразования Хафа. Напротив, преобразование Хафа опирается на общее математическое описание, в котором участвуют все точки, принадлежащие некоторой линии. При выполнении преобразования Хафа необходимо указать для какой кривой оно применяется. В то же время система зрения человека не нуждается в подобной информации, чтобы выполнить группировку элементов.
10.5.2.Поиск при выделении контурных сегментов
В1976г. А. Мартелли рассмотрел применение методов поиска на графах к обнаружению контурных сегментов [78]. По существу, был предложен оптимизационный подход.
Предполагается, что функция градиента вычисляется для каждого пикселя заранее. Основываясь на этой информации, необходимо найти “оптимальный“ контур. Мартелли предложил использовать для этого A*- алгоритм поиска на графах. Как отмечалось ранее, A*- алгоритм – это алгоритм поиска в пространстве состояний, который начинает поиск со стартовой вершины и выбирает наилучший (самый дешевый) путь, ведущий в целевую вершину. Управление в алгоритме осуществляется с помощью оценочной функции, содержащей две составляющие: затраты от стартовой вершины до промежуточной вершины текущего пути; прогнозируемые затраты от промежуточной вершины до целевой вершины. Сформу-
582
Глава 10
лировать подходящую оценочную функцию бывает весьма трудно, особенно её вторую часть.
Поэтому оценочная функция Мартелли содержит только оценку затрат на пути из стартовой вершины в вершину N, т.е. gˆ(N), и не включает
затраты на пути из вершины N в целевую вершины – hˆ(N). Полагая hˆ(N)=0, получаем тривиальную версию A*-алгоритма – алгоритм равных цен, свойства которого подобны алгоритму поиска в ширину. Причины, по которым трудно сформулировать нетривиальную эвристическую функциюhˆ(N), следующие. Во-первых, выбранная функция оценки накопленных затрат gˆ(N) содержит два слагаемых, одно их которых зависит от силы границы (больше сила границы – ниже затраты), а другое – от кривизны контура (выше степень кривизны – больше затраты). Так как заранее ничего не известно о той области изображения, которую предстоит просмотреть на пути к целевой вершине, то трудно оценить предстоящие затраты каким-либо значением, отличным от нуля. Во-вторых, определение стартовой и целевой вершин также затруднительно. Возможность указанная Мартелли: каждый пиксель в первой строке изображения может быть использован как стартовая вершина, а каждый из пикселей в последней строке – как целевая вершина. Дополнительная возможность: в качестве стартовой вершины можно использовать пиксель с максимальным абсолютным значением градиента; в качестве конечной вершины используют тот же самый пиксель, но при достижении его с другой стороны. Данная возможность, конечно, применима только для замкнутых контуров.
Из-за этих трудностей, на практике предпочтение отдают методам с локальными эвристиками, которые, конечно, не могут гарантировать глобальной оптимальности построенного контура. Примером является подход, который использовался П.Руммелем и В. Бойтелем в системе распознавания объектов на основе полутоновых изображений в промышленных условиях [83]. Граничные пиксели непосредственно прослеживаются на изображении с помощью линии-указателя, управляемой направлением градиента. Пиксели результирующего контура представляют последовательность граничных точек, каждая из которых характеризуется позицией и направлением. Стартовая точка контура находится с помощью изотропного оператора Собела. Как только выходное значение оператора (абсолютное значение градиента) превысит некоторый порог, начинается эвристический поиск. С этого момента контур наращивается пиксель за пикселем, посредством тех пикселей, которые не приводят к слишком большому увеличению кривизны. Кроме этого, абсолютное значение градиента в позиции следующего пикселя должно быть выше некоторого порога. Данный метод использует неявные допущения о том, что контуры должны быть относительно гладкими. Если допущения не выполняются, то это оз-
Компьютерное зрение
583
начает, что разрешающая способность изображения недостаточна. Наращивание контура прекращается, когда условия, указанные выше, не выполняются (например, если объект и фон имеют приблизительно равную интенсивность), или когда текущий контур совпадает с контуром, найденным ранее, или границей изображения.
10.5.3. Активные контурные модели
Современной версией метода глобальной оптимизации выделяемого контура является так называемый метод активных контуров, или “снейков” (англ. snake – змейка, боновое заграждение в виде змейки). Активный контур представляет собой кривую на изображении, которая может менять свою форму под воздействием внутренних сил, обусловленных свойствами самой кривой, и внешних сил, направляемых данными изображения. Внешние и внутренние силы определяются так, чтобы форма активного контура соответствовала границам выделяемого объекта. Активные контурные модели (“снейки”) являются виртуальными кривыми r(s). С каждой такой кривой связывают значение “энергии”. Поиск оптимального контура рассматривается как задача минимизации энергии Esnake на множестве кривых:
1 1 1
Esnake Eint(r(s))ds Eimage(r(s))ds Eext(r(s))ds.
0 0 0
Первый интеграл учитывает длину и плавность кривой; второй имеет малые значения, когда выделяемый контур проходит через области изображения с большими градиентами. Эти два интеграла, по существу, представляют дальнейшее развитие первой составляющей оценочной функции Мартелли. Наличие третьего интеграла позволяет учесть влияние элементов изображения, находящихся геометрически вне “снейка”. В интерактивном режиме пользователь может оказывать влияние на выбор желаемой формы восстанавливаемого контура. В не интерактивном режиме система может учитывать цели более высокого порядка (предположения, гипотезы). “Снейки“ могут представляться в виде сплайнов. Минимизация энергии выполняется итерационно и является весьма затратной. Узким местом метода активного контурного моделирования является инициализация.
Методы поиска контуров с глобальной оценочной функцией более устойчивы к шумам изображения по сравнению с методами, использующими локальную оценочную функцию. Первые в определенной степени могут соединять разрывы контуров. Для изображений с явными границами и низким уровнем шумов (что часто имеет место в системах техниче-
584
Глава 10
ского зрения роботов) обычно применяют более эффективные локальные методы.
10.6. Выделение областей изображения
Подходы, основанные на выделении областей изображения, являются дуальными по отношению к подходам, основанным на выделении контуров: контуры ограничивают области, а соприкосновения различных областей между собой создают контуры. Области являются потенциально важными для интерпретации изображений. Отдельные пиксели могут играть роль исходных точек в процессе генерации областей. Пиксель добавляется к области, когда его специфические свойства не слишком отличаются от свойств пикселей, которые уже образуют область, и когда он соседствует с областью. Это довольно неточное определение позволяет выделенные области, т.е. области, в которых интенсивность изменяется плавно, рассматривать как одну. Данный процесс, называемый “слиянием”, начинается с уровня пикселей и продолжается до тех пор, пока выполняются следующие условия:
-каждая область представляет собой связное множество пикселей изображения;
-области являются непересекающимися, и вместе они охватывают всё изображение;
-каждая область удовлетворяет некоторому предикату однородности, это касается значений интенсивности, цветов, текстуры, глубины, движения, математического описания поверхности или других свойств;
-если области Ri и Rj являются смежными, то Ri Rj не удовлетво-
ряет предикату однородности.
Противоположным по отношению к процессу “слияния” является процесс “разделения”, который начинается с анализа всего изображения и, после проверки однородности некоторой области, выполняется рекурсивно до тех пор, пока это необходимо. Затем смежные области, удовлетворяющие предикату однородности, объединяются.
Рекомендуется использовать такой процесс “разделения и слияния“, при котором изображение произвольно разделяется на области среднего размера. Затем области тестируются (с помощью предиката однородности) как с целью выяснения возможности их дальнейшего разделения, так и пригодности для слияния.
Сегментацию изображения на области можно улучшить сопоставлением получаемых результатов с результатами процесса восстановления границ, выполняемого параллельно, и дальнейшей их адекватной адапта-
Компьютерное зрение
585
цией. Такой гибридный процесс реализуется в системе машинного зрения
VISIONS.
Гибридная технология сегментации также хорошо подходит для диапазонных изображений. Граничные элементы обычно обнаруживаются при поиске пикселей в окрестностях, которые характеризуются большим диапазоном отличий (разрывы в виде скачка). Другой вид разрывов соответствует неравномерностям скорости нарастания значения (разрывы в виде крыши). Пиксели, приходящиеся на разрыв любого вида, могут объединяться в линии с помощью методов, подобных тем, которые были описаны выше для изображений, представляемых матрицей интенсивности.
Элементы, соответствующие наращиваемой области изображения, обнаруживаются, начиная с некоторых исходных точек, расставляемых регулярно или рассеиваемых беспорядочно с соответствующей плотностью по диапазонному изображению. Исходные точки – маленькие зоны, составленные из нескольких смежных диапазонных пикселей. Такие зоны могут расширяться во все стороны, пока пиксели в зоне удовлетворяют некоторому математическому описанию. В зависимости от характера диапазонной сцены, даже самое простое математическое описание (уравнения плоскостей в 3D пространстве) может приводить к очень интересным результатам. Соответствующий пример будет рассмотрен при описании системы технического зрения робота.
10.7. Интерпретация контурных рисунков
Рассмотрим метод интерпретации трехмерной сцены по двумерному контурному рисунку. Это классический метод искусственного интеллекта, который был разработан независимо Хаффманом и Клоузом (1971) и расширен Вальцом (1975).
В этом случае можно говорить о том, что речь идет о системе компьютерного зрения, однако, по общему признанию, довольно неполной. Вся низкоуровневая часть системы здесь не рассматривается, но предполагается, что она формирует соответствующие признаки, на основе которых выполняются необходимые выводы. Эти признаки (линии) представляются совместно с геометрическими отношениями в форме контурных рисунков.
Чтобы выполнить интерпретацию контурного рисунка, необходимо, с одной стороны, обладать знаниями об окружающей среде и об объектах, присутствующих в ней, а с другой – учитывать весьма сильные ограничения:
-используемые контурные рисунки должны быть корректны (отсутствие разрывов линий, отсутствие свободных концов линий);
586
Глава 10
- объекты на рисунках должны быть видимы с общих позиций, т.е. малые изменения положения объекта или камеры не должны приводить к качественным изменениям сцены;
-объекты должны быть многогранниками, в каждом углу объекта пересекаются 3 плоскости.
Задача решается методом распространения ограничений. Необходимо строго различать элементы, принадлежащие двумерному изображению, и элементы соответствующей трехмерной сцены. Элементами 2Dизображения являются: линия, соединение, область. К элементам 3Dизображения относятся: край (ребро), вершина, поверхность.
На первом шаге анализа изображения выполняется предварительная классификация линий и соединений в соответствии с их графической формой. Выделяют следующие виды двумерных элементов (рисунок
10.24):
-линия – имеет вид отрезка прямой;
-L-соединение –пересечение двух линий;
-стрелка –пересечение трех линий, наибольший угол между двумя линиями превышает1800;
-вилка –пересечение трех линий, угол между любыми двумя линиями меньше 1800;
-Т-соединение – пересечение трех линий, один угол равен 1800.
Рисунок 10.24 Виды двумерных соединений
На втором шаге осуществляется возможная интерпретация линий и соединений в трехмерном пространстве.
3D-интерпретация линий на рисунке. С целью интерпретации кон-
турных рисунков вводятся следующие метки:
-выпуклые ребра маркируются знаком “+” (поверхности пересекаются так, что ребра образуют угол меньше 1800 со стороны объекта);
-вогнутые ребра маркируются знаком “-” (поверхности пересекаются так, что ребра образуют угол больше 1800 со стороны объекта);
-закрывающие ребра маркируются знаком ““ (поверхности по обе стороны ребра не являются смежными в трехмерном пространстве, направление стрелки может быть выбрано таким, чтобы закрывающая поверхность находилась справа, а частично закрытая поверхность – слева от стрелки).
Компьютерное зрение
587
3D-интерпретация соединений на рисунке. Учитывая сказанное,
можно выделить только четыре типа вершин в соответствии их пространственным расположением. Все они могут быть представлены с помощью определенным образом расположенных прямоугольных блоков (рисунок 10.25). Вершины каждого из четырех типов отмечены на рисунке точкой.
Рисунок 10.25 – Виды вершин
Множество интерпретаций соединений можно получить, исходя из четырех типов пространственного размещения блоков, рассматриваемых под разным углом зрения. Возможные виды интерпретируемых соединений показаны на рисунке 10.26. Чтобы получить интерпретации, изображенные в последней строке рисунка, необходимо наличие второго (закрывающего) объекта.
Рисунок 10.26 Виды интерпретируемых соединений
После такой предварительной подготовки можно попытаться выполнить интерпретацию конкретного рисунка, который не должен содержать ошибок (разрывов, свободных концов и т.п.). 3D-интерпретация соединений, присутствующих на рисунке, не может выполняться локально. В начале необходимо для каждого типа соединений (например, для вилки) допустить всевозможные 3D-интерпретации и представить их в форме множества меток. Интерпретация рисунка непротиворечива в том случае, когда линия, связывающая два соединения, имеет одну и ту же метку с ка-
588
Глава 10
ждой из своих сторон. Хаффман и Клоуз нашли способ непротиворечивой разметки контурных рисунков путем полного перечисления всех возможных комбинаций меток и проверкой совместимости каждого случая. Если непротиворечивая разметка не может быть найдена, то либо не выполняются предварительные условия, либо объект физически не осуществим.
Легко заметить, что проблема разметки соответствует проблеме распространения ограничений. Повысить эффективность поиска можно путем усечения дерева поиска. Это уточнение было предложено Вальцем (1975). Разметка может выполняться последовательно или параллельно. В соответствии с последовательным подходом рассматривается одно соединение за другим. При этом каждый раз исследуется непротиворечивость соседних наборов меток. Рисунок анализируется несколько раз до тех пор, пока не прекратятся замены меток. В случае параллельного алгоритма каждому соединению может быть назначен процессор, который исследует непротиворечивость наборов соседних меток и удаляет недопустимые метки.
Если поиск непротиворечивой разметки заканчивается неудачей, т.е. если алгоритм назначает две различных метки для одной и той же линии, то объект является нереальным (бессмысленным). Также установлено, что не все контурные рисунки, для которых описанным выше методом найдена непротиворечивая разметка, являются реализуемыми.
Полнее извлечь информацию из контурных рисунков можно на основе подхода, разработанного K. Сугихарой [90]. Данный подход позволяет различать реализуемые и не реализуемые объекты.
Сформулируем выводы. Несмотря на сложность, желательно, чтобы методы могли выделять объекты с криволинейными поверхностями. В этом направлении выполняются современные исследования. Проблема состоит в том, что, в отличие от мира многогранников Вальца, имеются закрывающие линии, которые не соответствуют граням тел. Эти закрывающие линии появляются, когда взгляд идет по касательной к изогнутой поверхности.
Дополнительные проблемы возникают, когда используются неполные рисунки или рисунки с ошибками.
Если обнаружена непротиворечивая глобальная разметка контурного рисунка, то это означает, что найдена интерпретация только видимой части сцены, представленной рисунком. Рассмотренный процесс интерпретации не позволяет достичь более глубокого понимания рисунка.
Человек обычно продвигается намного глубже и дополняет полученные результаты предсказанием невидимых частей сцены. При этом он обычно вводит дальнейшие предположения и принципы, например, симметрию и непрерывность.
Компьютерное зрение
589
Таким образом, интерпретация контурных рисунков – все еще актуальная область исследований компьютерного зрения и ИИ.
10.8. Распознавание объектов в системах зрения роботов
10.8.1 Системы зрения роботов и компьютерное зрение
Системы зрения промышленных роботов являются подклассом систем компьютерного зрения, но приоритеты в этом случае расставляются по иному. Ориентация на промышленное применение предопределяет следующие требования к системам технического зрения роботов:
-низкая стоимость оборудования и программного обеспечения;
-высокая скорость распознавания объектов, обеспечивающая синхронность распознавания с технологическим процессом, в который интегрирована система зрения робота (наблюдается расширение этой тенденции);
-высокая надежность распознавания объектов, их позиций и ориентации;
-высокая робастность по отношению к изменениям формы объектов, позиции и ориентации.
Сдругой стороны, системы зрения роботов характеризуются некоторыми упрощениями:
-малое количество распознаваемых объектов и их моделей, хранящихся в памяти (примерно от 10 до 100);
-модели объектов могут быть заданы довольно точно на основе обучения и/или на основе данных САПР;
-часто объекты имеют простую форму, которая определяется прямыми линиями, плоскими поверхностями и т.п.;
-локальные признаки, которые являются полезными для распознавания, свойственны не только одному объекту, например, просверленные отверстия;
-освещение и фон можно настроить так, чтобы упростить распознавание;
-часто объекты и/или фон могут быть окрашены или помечены;
-предъявлением объектов можно в значительной степени управлять, например, объекты могут отбираться простыми механическими устройствами, что упрощает распознавание.
Системы технического зрения роботов играют все возрастающую роль в следующих производственных задачах:
