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

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

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

Возвращаясь к первоначальной теме — описанию объекта через экстремумы его границы, — мы приведем несколько примеров, чтобы дать читателю возможность почувствовать «вкус» этого метода. Читатель может сам убедиться, что знак плюс и круг имеют идентичные описания в терминах экстремумов, хотя нх дефициты выпукласти совершенно различны. С другой стороны, знак плюс в обычной ориентации и знак плюс, повернутый на 45', имеют совершенно различные описания экстремумов. Если знак плюс повернут на 45, Гл. й. Окисикии ликии и фоямы описание через экстремумы близко совпадает с описанием через точки высокой кривизны. Это не так в случае, когда знак плюс имеет свою обычную ориентацию. Ясно, что в общем случае на описание через экстремумы влияет ориентация объекта относительно координатных осей.

9.3.5. СКЕЛЕТ ОБЪЕКТА Наиболее интригующий способ описания объекта основан на применении преобразования к средним осям, или так называемого метода степного пожара. Цель такого преобразования заключается в том, чтобы выделить из исходного объекта его штриховое представление, метко названное скелетом. Более того, преобразование выделяет также дополнительную информацию, которая вместе со скелетом позволяет восстановить исходный объект.

Для простоты мы ограничим обсуждение преобразования к средним осям объектами, заданными в аналоговой форме и состоящими из одной компоненты. Существует много эквивалентных определений скелета объекта, По-видимому, наиболее близко к интуитивным представлениям следующее определение. Представим себе, что внутренняя часть объекта покрыта сухой травой, а его окрестность (т. е, фон) — негорючей сырой травой. Предположим, что огонь возник одновременно во всех точках на границе объекта. Огонь будет распространяться с неизменной скоростью по направлению к центру объекта.

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

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

Линия продвижения огня сначала также имеет прямоугольную форму, н прилегающие стороны гасят друг друга, образуя ребра скелета а, Ь, с и И. В некоторый момент эти ребра заканчиваются, короткие стороны огненного прямоугольника становятся равными нулю, а две оставшиеся длинные стороны гасят друг друга, образуя ребро е скелета.

Часто бывает удобным определить понятие скелета в терминах расстояний, не пользуясь представлением о взаимно подавляющих фронтах огня. Чтобы выполнить это, мы должны уточнить понятие расстояния от данной точки до множества точек. В соответствии с этим мы определим расстояние от точки х до множества А как рас- Э.З. Описание ФОРмы стояние от х до ближайшей точки множества А. Формально величина и'(х, А) для данной метрики и' определяется выражением с((х, А) = 1п((с((х, у):уб А), где символ 1п1' обозначает нижнюю грань. Если нам задан произвольный объект с границей В, мы можем для каждой точки объекта подсчитать ее расстояние до множества В.

Прн этом, однако, мы заметим, что для некоторых точек это расстояние вычисляется не единственным образом. Для каждой такой точки х мы найдем по крайней мере две граничные точки, например у и х, такие, что с((х, В)=а (х, у)=-а(х, х). Эти еособенные» точки определяют скелет. Гранина адьента Аннан араддниеная пеня Ркс. 9,Ю. Скелет пряиоугольккка.

Интуитивно ясно, что это определение скелета эквивалентно предыдущечу. Поскольку огонь распространяется с постоянной скоростью, точки гашения должны быть эквидистантны по крайней мередвум отдельным точкам границы, которые в свою очередь должны быть ближе к точке гашения, чем все другие граничные точки. Ясно, что для круглого объекта только центр удовлетворяет этому условию. На рис. 9.20 ребра а, Ь, с и с( эквндистантны одной длинной и одной короткой стороне прямоугольника, а ребро е эквидистантно двум длинным сторонам.

Это определение делает очевидной зависимость скелета от выбора метрики с(. Здесь мы молчаливо приняли евклидову метрику и будем продолжать ее использовать. Метрическая интерпретация понятия скелета дает естественное средство для построения более полного описания объекта. Свяжем с каждой точкой х скелета объекта, имеющего границу В, величину Ч(х), определяемую равенством д(х)=с((х, В). Функция д(х) называется функцией гашения скелета, Очевидно, что она представляет собой просто расстояние от данной точки скелета до границы объекта.

(Мы можем также заметить, что величина Гл. З. Оиасаняя яикяи и формы д(х) пропорциональна времени, в течение которого огонь достигает точки х.) Для каждого объекта, имеющего скелет 5 и функцию гашеная д, мы назовем пару (5, д) скелетной парой объекта.

Наибольший интерес представляет тотфакт, что исходный объект может быть восстановлен по его скелетной паре. Восстановление выполняетея просто; каждую точку х скелета мы делаем центром диска с радиусом д(х). Объединение всех таких дисков точно соответствует исходному объекту. Таким образом, скелетная пара в некотором смысле представляет собой естественное расширение описания круга на произвольные множества. Рассмотрим несколько подробнее утверждение, что скелетная пара содержит всю информацию, необходимую для восстановления исходного объекта. Чтобы установить истинность этого утверждения, мы должны показать, что множество Ь' точек объекта идентично объединению У дисков.

Мы покажем это неформально, обычным способом — продемонстрировав, что каждое из множеств содержится в другом. Сначала предположим, что точка у принадлежит множеству У. Тогда у принадлежит по крайней мере одному из дисков. Но по определению каждый диск содержится в множестве Ь', так как радиус ~)(х) любого диска представляет собой расстояние от центра диска х до границы Р. Следовательно, у принадлежит Р. С другой стороны, предположим, что нам дана точка у„принадлежащая Ь'. Чтобы показать, что у принадлежит также У, достаточно найти один диск, содержащий у. Мы можем найти такой диск следующим образом.

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

Основная идея заключается в том, чтобы исключить части скелета, вдоль которых огонь распространяется медленно. Проверим эту идею с помощью рис. 9.20. Предположим сначала, что огонь распространяется по нормали к своему фронту с единичной скоростью. Тогда каждое из ребер а, Ь, с и д делит пополам соответствующий ему прямой угол, что можно видеть непосредственно из обоих определений скелета. Нетрудно установить, наконец, что каждая из точек Л, В, С и 1У движется вдоль соответствующего ребра со скоростью $' 2. С другой стороны, вдоль ребра е огонь распространяется с бесконечной скоростью, так как это ребро формируется полностью в один момент времени. Мы можем тогда принять решение исключить из скелета все ребра, для которых скорость распространения, меньше чем 1,5, Ззб 9.3.

Олисаиие 4онлы Эта операция сведет скелет к единственному ребру е. Если мы восстановим объект, используя только это ребро вместе со связанной с ним величиной д(х), тогда получим то, что показано на рис. 9.21. В простом примере рис. 9.20 скорость распространения вдоль любого ребра постоянна. В общем случае скорость распространения в произвольной точке х скелета равна Щг(з)-, где з — рас- Г 1 стояние до точки х вдоль скелета. В этом проще всего убедиться, рассматривая величи- ! ну г)(х) не как расстояние от точки х до границы, а как время, в течение которого огонь достигает точки гашения х.

1 (Поскольку скорость огня пос- ! тоянна в направлении нор- 1 мали к его фронту, оба значения отличаются только пос- Рнс. 9.2!. Восстановление объекта но скетоянным множителем.) Таким лету, сосгоангену нз одного ребра. образом, величина Щ/с(з)-' представляет собой расстояние с(з вдоль скелета, поделенное на время Щ требуемое для прохождения фронтом огня этого расстояния. Читатель, знакомый с распространением плоских волн, узнает в этой величине просто фазовую скорость плоской волны вдоль касательной к скелету в точке х. йз слега Рнс.

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

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