Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 72

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

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

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

Ценность этого метода подтверждается известным рисунком, принадлежащим Аттннву '), который построен в соответст- ВИН С ОПИСаННЫМ ПраВИЛОМ (рИС. 9.7). Рис. 9.7. Пример Аттнива (нв Мало кто не узнает здесь спящую кош- книги Аттнива 1964). ку. С математической точки зрения такой подход связан с так называемым естественным уравнением кривой. Естественное уравнение кривой ') определяет ее кривизну как функцию длины дуги.

Следовательно, обсуждаемый метод, по существу, эквивалентен заданию естественного уравнения кривой ее экстремальными точками. (Мы оставили без внимания некоторые математические трудности, связанные с определением кривизны в точке пересечения двух прямых линий.) ') Р. А11пеаче, «5огпе 1п1оппацопа1 авресы о1 ч!впа! регсерцоп», Рвусйо!. )?ео., 61, 183 — 193 (!954). «) В отечественной литературе принят термин «уравнение в естественных координатах».— Прим. перев. Гя. 9.

Описания линии и формы 9.2.5. ЦЕПНОЕ КОДИРОВАНИЕ Весьма удобный метод представления произвольной кривой известен под названием цепного кодирования. Ради простоты мы будем считать, что кривая первоначально задана в виде двухградационного изображения на неквантованной плоскости и что мы хотим каким-то образом представить ее в цифровой форме. Вместо того чтобы дискретизировать все изображение обычным путем, мы Рнс. 9,8. Цепное кодирование. наносим сетку на аналоговую картинку и фиксируем точки, в которых кривая пересекает линии сетки. Для представления кривой отбираются узлы сетки, ближайшие к каждому пересечению. Рис.

9.8, а показывает выделенные узлы для данной кривой. Затем мы кодируем последовательность узлов восьмеричными числами, обозначая направления от одного узла к другому в соответствии с кодами, показанными на рис. 9.8, б. Так, например, цепное кодирование данной кривой начиная с крайней нижней точки дает последовательность 1, 1, 2, 1, О. Заметим, что такая схема может рассматриваться как дискретный вариант естественного уравнения кривой. Код определяет угол (в другом варианте — изменение угла) как функцию длины дуги с учетом того, что диагональные отрезки в )Г2 раз длинней, чем вертикальные и горизонтальные.

Цепное кодирование особенно удобно при сравнении формы двух кривых. Предположим для простоты, что мы хотим измерить сходство между двумя кривыми одинаковой длины и ориентации. Обозначим цепи через а=а„..., а„и о=оп..., о„. Определим цепную взаимно-корреляционную функцию С,„двух йривых с по- 9.3. Оиисоиие формы о!ощью выражения Сои = — ~, а!Ь!, !=! где а;Ь! =сов(.~ а! —./ Ь!). Заметим, что, если две кривые идентичны, нх цепная функция взаимной корреляции достигает своего максимального значения, равного 1.

В более общем случае две цепи имеют разную длину, и нам будет нужно двигать одну цепь относительно другой с тем, чтобы найти наилучшее соответствие. В связи с этим мы обобщим определение цепной функции взаимной корреляции следующим образом: 1ч С,„()) = — ~ а!Ь|,„ !=! где й — длина общего участка двух последовательностей. Таким образом, наилучшее соответствие достигается вычислением величины С,о Ц) для всех значений сдвига ) и выбором максимальной из них.

Главное ограничение эффективности цепной функции взаимной корреляции связано с тем, что обе кривые должны иметь одинаковый масштаб и ориентацию. Если хотя бы одно из этих условий нарушается, то либо следует отвергнуть этот метод, либо нужно повернуть на плоскости одну из последовательностей и (или) изменить ее масштаб относительно другой. 9.3. ОПИСАНИЕ ФОРМЫ Займемся теперь проблемой описания формы объекта. Как обычно, будем полагать, что объект отделен от фона; следовательно, как и в случае описания линий, задача заключается в том, чтобы охарактеризовать некоторые подмножества плоскости (квантованной, возможно, с помощью прямоугольной сетки).

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

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

Вообще говоря, наш выбор зависит от того, насколько «информативные» описания мы хотим получать. Чем ннформативней описание, тем меньше множеств удовлетворяет этому описанию. Затратив некоторые усилия, мы можем легко формализовать смысл слов «одно описание более информативно, чем другое». Мы будем говорить, что описание Р, более информативно, чем другое описание Р„если множество обьектов, описываемых посредством Р„при-. надлежит множеству объектов, описываемых посредством Р,. Если включение направлено в противоположную сторону, то Р, — более информативное описание.

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

Другие часто применяемые классы эквивалентности представляют собой множества, полученные вращением и растяжением данного объекта. В общем случае мы говорим об описаниях, которые инвариантны по отношению к некоторым группам преобразований. Цель всех усилий состоит в том, чтобы найти описания, которые были бы инвариантиымн по отношению к преобразованиям, вызывающим «несущественные» изменения объектов, и в то же время чувствительными к преобразованиям, изменяющим объекты «существенным» образом. 9.3. Описание ЕЗормы 367 9.3.1, ТОПОЛОГИЧЕСКИЕ СВОЙСТВА Фундаментальный способ описания подмножества плоскости заключается в том, чтобы указать некоторые топологические свойства множества.

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

9.9. Объект, состояшяя яз двух связных компонент. Резинообразное искажение плоскости называется тонологическим отображением плоскости на себя или гомеоморфизмом. Формально гомеоморфизм определяется как взаимно однозначное непрерывное отображение, причем обратное отображение также непрерывно. Заметим, что топологические свойства множеств не могут основываться на каком бы то ни было понятии расстояния, поскольку расстояния искажаются при топологическом отображении. Точно так же они не могут вовлекать какие-либо свойства, основанные в конечном счете на понятии расстояния, такие, как площадь множества, параллельность между двумя кривыми, перпендикулярность двух прямых и т.

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

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