Робототехника.Фу, Ли, Гонсалес (962794), страница 73
Текст из файла (страница 73)
Рассмотрим следующую процедуру генерации эталонного образа. Предположим, что мы рассматриваем первый образ последовательности в качестве эталонного. Когда нестационарная компонента полностью вышла из своего положения в эталонном кадре, соответствующий фон в данном кадре может быть перенесен в положение, первоначально занимаемое объектом в эталонном кадре. Когда все движущиеся объекты полностью покинули свои псрвоначальныс положения, в результате этой операции воссоздается эталонный образ, содержащий только стационарные компоненты. Перемещение объекта можно определить с помощью операции расширения положительного изображения аккумулятивной разности.
Пример. Иллюстрация описанного выше подхода приведена иа рис. 8.24 и 8.25. На рис. 8.24 показаны два кадра изображс- Г, 8.3. ОПИСАНИВ 481 пня перекрестка. Первое изображение рассматривается в качестве эталонного, а второе воспроизводит эту же сцену в некоторый более поздний момент времени. Основными движущимися деталями являются автомобиль, движущийся слева направо, и пешеход, пересекающий улицу в нижней левой части картины.
Рис. 8.25. Пзобрапсенне, н котором устранен аатомобиаь и сохранен фон (а), и изобрангение, з котором устранен пешсход н сохранен фон. Последнее изображение можно использовать как зталонное (135). Устранение движущегося автомобиля показано на рис. 8.25,а, а устранение пешехода — на рис. 8.25,б. В системах технического зрения проблемой описания называется выделение свойств (деталей) объек~а с целью распознавания. В идеальном случае дескрипторы не должны зависеть от размеров, расположения и ориентации объекта, но должны содержать достаточное количество информации для надежной идентификации объектов.
Описание является основным результатом при конструировании систем технического зрения в том смысле, что дескрипторы должны влиять не только на сложность алгоритмов распознавания, но также и на их работу. В равд. 8,3.1, 8.3.2 в 8.4 мы рассмо~рим три основные категории дескрипторов: дескрипторы границы, дескрипторы области и дескрипторы для описания трехмерных структур.
8.3.1, Дескрипторы границы Цепные коды. Цепные коды применяются для представления границы в виде последовательности отрезков прямых линий определенной длины и направления. Обычно в основе этого представления лежит 4- или 8-связная прямоугольная решетка (рпс, 8.26). Длина каждого отрезка определяется разрешением решетки, а направления задаются выбранным кодом. Отметим, 4)0 Рис. 8.26. 4-напрааленный пенной код (а) и 8 направленный пепной код (б). б Кепкой )Ы гт у о" и 0 1 1 о о о Ю 1 д . ° * Рис. 8.27, Этапы получении цепного кода. что для представления всех направлений в 4-направленном цепном коде достаточно 2 бит, а для 8-направленного цепного кода требуется 3 бит.
Конечно, можно определить цепные коды с ббльшим числом направлений, но на практике наиболее часто используются коды, приведенные на рис. 8.26. Для порождения цепного кода заданной границы сначала выбирается решетка (рис. 8.27,а). Тогда, если площадь ячейки, расположенной внутри границы, больше определенного числа (обычно 50 о7о), ей присваивается значение 1; в противном случае этой ячейке присваивается значение О. Данный процесс иллюстрируется рис. 8.27,б, где ячейки со значением ! отмечены темными линиями. Окончательно мы кодируем границу между двумя областями, используя направления, заданные решеткой на рис. 8.26, а. Результат кодирования в направлении по часовой стрелке с началом в месте, помеченном точкой, приведен на рнс, 8.27, в, Альтернативная процедура состоит в разбиении границы на участки равной длины (каждый участок имеет одно 4308222! 1 и то же число пикселов) и соединении граничных точек Рис.
8,28. Генерация цепного кода с каждого участка прямой липомощью разбиения границы. нией, а затем присваивания каждой линии направления, ближайшего к одному из допустимых направлений цепного кода. Пример такого подхода, использующего четыре направления, приведен на рис. 8.28. Важно отметить, что цепной код данной границы зависит от начальной точки.
Однако можно нормировать код с помощью простой процедуры. Для создания цепного кода начальная точка на решетке выбирается произвольным образом. Рассматривая цепной код как замкнутую последовательность индексов направлений, мы вновь выбираем начальную точку таким образом, чтобы результирующая последовательность индексов была целым числом, имеющим минимальную величину. Также можно нормировать повороты, если вместо цепного кода рассматривать его первую разность. Первая разность вычисляется в результате отсчитывания (в направлении против часовой стрелки) числа направлений, разделяющих два соседних элемента кода. Например, первая разность для цепного кода с 4 направлениями !0103322 есть 3133030.
Если рассматривать код как замкнутую последовательность, тогда первый элемент разности 482 можно вычислить, используя переход между последним и первым компонентами цепи. В данном примере результатом является 33133030. Нормирование можно осуществить путем разбиения всех границ объекта на одинаковое число равных сегментов и последующей подгонкой длин сегментов кода с целью их соответствия этому разбиению, как показано на рис, 8.28.
Изложенные методы нормирования являются точными только в том случае, когда сами границы инвариантны к повороту и изменению масштаба. Этот случай редко встречается на практике. Например, один и тот же объект, разбитый на элементы в двух различных направлениях. как правило, имеет разную хг л Пл' х Хк Ззг гхг хп' зг х" Зн л. Хкззг Пг Хг г+ УТ4 в е В+ 4гР а Рис, 8,29, Две простые формы границы и их сигнатуры как функции угла.
форму границы, причем степень различия пропорциональна раз. решакицей способности изображения. Этот эффект можно уменьшить, если выбирать длины элементов цепи ббльшими, чем расстояния ме кгу пикселами дискретного образа, или же выбирать ориентацию решетки (рис. 8.27) вдоль главных осей кодируемого объекта, Этот вопрос рассматривается ниже в разделе, посвященном индексам формы, Сигнатуры. Сигнатурой называется одномерное функциональное представление границы. Известно несколько способов создания сигнатур, Одним из наиболее простых является построение отрезка из центра к границе как функции угла (рис.
8.29). Очевидно, что такие сигнатуры зависят от периметра области и начальной точки. Нормирование периметра можно осуществить, пронормировав кривую г(0) максимальным значением. Проблему выбора начальной точки можно решить определив сначала цепной код границы, а затем применив метод, изложенный в предыдущем разделе. Конечно, расстояние, зависящее от угла, не является единственным способом определения сигнатуры. Например, можно провести через границу прямую линию и определить угол между касательной к гарнице и этой линией как функцию 483 к [т„(а) = 2 (а, — т)" р (а ), (8.3-1) где т =- 2„агр(а,). (8.3-2) положения вдоль границы [4].
Полученная сигнатура, хотя и отличается от кривой г(9), несет информацию об основных характеристиках формы границы. Например, горизонтальные участки кривой соответствовали бы прямым линиям вдоль границы, поскольку угол касательной здесь постоянен. Один из вариантов этого метода в качестве сигнатуры использует так называемую 4ункцию плотности наклона [206]. Эта функция представляет собой гистограмму значений угла касательной. Поскольку гистограмма является мерой концентрации величин, функция плотности наклона строго соответствует участкам границы с постоянными углами касательной (прямые или почти прямые участки) и имеет глубокие провалы для участков, соответствующих быстрому изменению углов (выступы или другие виды изгибов). После получения сигнатуры мы должны ее описать таким образом, чтобы можно было различать сигнатуры, соответствующие различным формам границы. Как правило, эта проблема решается просто, поскольку теперь мы имеем дело с одномерными функциями.
Метод, часто применяемый для определения отличительных признаков сигнатуры, состоит в определении ее моментов, Пусть а — дискретная случайная величина, означающая отклонения амплитуды сигнатуры, и пусть р(аг), = 1, 2...,, К вЂ” соответствующие значения гистограммы, где К вЂ” число дискретных приращений амплитуды а. Тогда а-й момент р от а относительно его среднего значения определяется выражением Величина т является средним значением а, а [гэ — его дисперсией, Для установления различия между сигнатурами явно непохожих форм границы обычно требуется только несколько первых моментов. Аппроксимация многоугольниками. Дискретную границу с произвольной точностью можно аппроксимировать многоугольниками. Для замкнутой кривой аппроксимация является точной, когда число сегментов в многоугольнике равно числу точек границы, так что каждая пара соседних точек определяет сегмент многоугольника.
На практике целью аппроксимации многоугольниками является качественное определение формы границы с помощью минимального числа многоугольных сегментов. Хотя обычно эта проблема нетривиальна и довольно быстро сводится к итеративному поиску, требующему больших временных чзч затрат, имеется ряд методов аппроксимации многоугольниками, относительная простота которых и требования к обработке данных делают их пригодными для приложений в области технического зрения роботов. В этом разделе рассмотрено несколько таких методов. Вначале рассмотрим метод, предложенный в работе [269], для определения .многоугольников, имеющих минимальный пе- Рис, 8.30 ["ранила обьеита, эаилюченная в элементы (а), и миогоугольннн минимального периметра (б), риметр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
