Робототехника.Фу, Ли, Гонсалес (962794), страница 74

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 74)

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

8.30,б, то эта форма будет соответствовать многоугольнику минимального периметра, удовлетворяющего геометрии полосы элементов. Когда элементы расположены таким образом, что внутри каждого элемента находится только одна точка границы, то для каждого элемента максимальная ошибка между исходной границей и ее аппроксимацией резиновой лентой составит ЪУ2 с(, где и* — расстояние между пикселами. Эту ошибку можно в 2 раза уменьшить, расположив пикселы в центрах соответствующих элементов. В задаче аппроксимации многоугольниками применяются методы объединения, основанные на ошибке или других критериях.

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

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

Если это имеет место, наиболее дальняя точка становится вершиной, разделяя, таким образом, исходный сегмент на два подсегмента, Этот метод обладает тем преимуществом, что он адаптирован к наиболее подходящим точкам изгиба. Для замкнутой границы наилучшей начальной парой точек обычно являются точки, наиболее удаленные от границы, Соответствующий пример приведен на рис. 8.31. На рис. 8.31, а показана граница объекта, а на рис. 8.3!,б — разбиение этой границы (сплошная линия) по наиболее удаленным точкам. В точке с перпендикуляр из вершины сегмента к линии аЬ имеет наибольшую длину, Аналогично точка и' наиболее удалена от нимщего сегмента.

На рис. 8.31,г показан результат применения процедуры разбиения с пороговым уровнем, равным 0,25 длины линии аЬ. Поскольку длина перпендикуляра, опущенного из любой точки новых сегментов границы до соответствующей прямой линии, не превышает выбранной величины порогового 436 уровня, то результатом работы процедуры является многоугольник, приведенный на рис. 8.3!,г. Отметим, что имеется большое число работ, посвященных комбинации методов объединения и разбиения, Обзор этих методов приведен в рабате [232]. Индексы формы. Граница, закодированная с помощью цепного кода, имеет несколько первых разностей, зависящих от начальной точки, Индекс формы такой границы, основанный на с Рис, 8.31.

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

8.32 приведены все возможные формы 4ъ 6- и 8-го порядков вместе с их цепными кодами, первыми разностями и индексами формы, Отметим, что при вычислении первых разностей цепные коды рассматривались как замкнутые последовательности. Хотя первая разность цешюго кода не зависит от вращения, закодированная граница, вообще говоря, будет зависеть от ориентации решетки кода, показанной на рис. 8.27,а. Одни из путей нормирования ориентации решетки следующий: болыиой осью границы является отрезок прямой линии, соединяющий две наиболее удаленные друг от 437 д-сс «арлдак Кеннан«ад ООЗЗгг11 Р!та«агата ЗОЗОЗОЗО этай«с дмриаг Оэ Оз Оз аз озозгг гг ЭЗ1ЗЗ ОЗО Озоззг Эз Ооозгг г 1 ЭООЗЗООЗ ООЭЗОО ЗЗ 438 д руга точки. Малой осою является перпендикуляр, восстановленный к большой оси и имеющий длину, достаточную для построения прямоугольника, описанного вокруг границы.

Отношение большой оси к малой называется эксз(енгрисигетам границы, а упомянутый выше прямоугольник — базовым прямоогальником, Во многих случаях при совмещении решетки цепного кода со сторонами базового прямоугольника получается только один индекс формы, В работе [85) приведен алгоритм построения базового прямоугольника для замкнутой кривой, а-й кар«Век О-йкарлдам йгеккай кот озг г оозгг т Разнес«та 0 3 3 З ЗОЗЗаз Эукдакс дмузлгат Э ЗЗЗ оэз оз з Рис. 8.32, Все формы 4-, б- и 8-го порядков. Направления определяются согласно рис. 8.26, и точка в левом верхнем углу указывает начальную точку. закодированной с помощью цепного кода.

Задавая желаемый порядок формы границы области, мы получаем прямоугольник порядка и, эксцентриситет которого наилучшим образом соответствует эксцентриситету базового прямоугольника для установления размеров решетки. Например, если п = 12, то всеми прямоугольниками 12-го порядка (т. е. периметр которых равен 12) являются следующие: 2 Х4, 3;з4 3 и 1;зч 5.

Если для данной границы эксцеитриситет прямоугольника 2 дс'4 наиболее близок к эксцентриситегу базового прямоугольника, выбирается решетка 2)ч',4, центр которой совпадает с центром базового пря. моугольника, п для получения цепного кода применяется изложенная выше процедура, Индексы формы получаются из первых разностей этого кода с помощью только что приведенного метода. Хотя порядок полученного индекса формы обычно равен и (что определяется способом выбора размеров ячеек решетки) для границ, имеющих выемки, размеры которых сравнимы с размерами ячеек решетки, порядок индекса формы иногда будет больше и. В этом случае выбирается прямоуголь- ник более низкого порядка и вся процедура повторяется, пока индекс формы, полученный в результате ее работы, не достигнет величины и. Пример.

Предположим, что для границы, показанной на рис. 8.33, а мы задали порядок п = 18. Для получения индекса формы такого порядка воспользуемся только что изложенной процедурой. Сначала мы находим базовый прямоугольник, как цен«ай «ад О О О 0 З 0 0 Э Л 20 222 Гг Г1 гг Раэнасага ЗОВОЭ10ЭЗО!Эоодтдо агнде«с озаРиез 000 з 10зэ01эооз гзоэ Рис, 8.33. Шаги генерации индекса формы. показано на рис. 8.33, б. Ближайшим прямоугольником 18-го п р орядка является прямоугольник Зк,'6, поэтому базовый прямо- м готьник разбивается так, как показано на рис. 8.33,в, прнче и.

направления цепного кода совпадают с направлениями решетк . Затем мы определяем цепной код и его первую разность, по кото ой вычисляется индекс формы (рис, 8.33,г), д ескрипторы Фурье. Дискретное одномерное преобразование Фурье, определяемое уравнением (7.6-4), часто можно исполь- 439 зовать для описания двумерной границы.

Предположим, что граница состоит из М точек. Если рассматривать границу па комплексной плоскости (рис. 8.34), каждая точка (х, у) двумерной границы соответствует комплексному числу х+ [у. Последовав' тельность точек границы можно представить в виде функции, имеющей преобразование Фурье Т(и), и=О, 1, 2, ..., М вЂ” !. Если М является целым числом (степенью 2), Т(и) можно вычислить с помошью алгоритма быстрого преобрасг зования Фурье (алгоритма БПФ), рассмотренного в равд.

7.6.1. Этот метод выбран потому, что для идентификации сушественно разных форм обычно требуется только нерио. 3.34. Представлеиие границы оп- сколько первых компонент ласти аа коиплексиой плоскости. Р(и). Например, объ ектьп при- веденные на рис. 8.35, можно различить, используя менее 10 % элементов полного и б ния Ф ье о прео разова- ния урье их границ Преобразование Фурье легко нормируется для размера, поворота и начальной точки границы. Для изме- Рис. 3.35. две фориьь которые легко различить с пои Фурье [2341. с помоптью дескрипторов пения размера контура достаточно умножить компоненты образования Фурье на константу. В силу линейности преобра- нт презования Фурье это эквивалентно умножению г а границы на один н тот же множитель (масштабирование).

Пов ворот на угол 0 осуществляется умножением элементов Т(и) на ехр (10). Окон- 440 чательно можно показать, что изменение начальной точки контура в пространственной области соответствует умножению й-й компоненты Т(и) на ехр([йТ), где Т лежит в интервале [О, 2Н). Поскольку значения Т изменяются в пределах от 0 до 2п, начальная точка обходит весь контур только один раз.

Эту информацию можно использовать как основу для нормирования '(104) . 8.3.2. Дескрипторы области Область, представляюшую интерес, можно описать формой ее границы (равд, 8.3.1) или же путем задания ее характеристик, как показано ниже. Важно отметить, что методы, рассмотренные в обоих разделах, применяются для описания областей. Некоторые простые дескрипторы. Сушествуюшие системы технического зрения основываются на довольно простых дескрипторах области, что делает их более привлекательными с вычислительной точки зрения.

Характеристики

Список файлов книги