Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 77
Текст из файла (страница 77)
9.22. Скелет вблизи угла границы. Попробуем вникнуть немного глубже в смысл понятия скорости распространения вдоль ребра. Предположим, у нас есть часть границы объекта, как это показано на рис.9.22, где две прямые линии пересекаются под углом 20. Скелет в этой области объекта делит угол пополам. Поскольку г/(х)=з(з!п 0), мы сразу же получим, что Щ/пэ)-г=1/з!п 0. Таким образом, чем больше угол между двумя сторонами границы, тем меньше скорость распространения вдоль этой части скелета.
Две крайние скорости равны единице и бесконечности, и достигаются они соответственно, когда угол либо вырожда- Рис. 9.23. Пример скелета. Рис. 9.24. Скелет, обработанный с порогом 1,25. Рис. 9.25. Скелет, обработанный с порогом 1,5. У.д. Олисани«формы ется в прямую линию, либо, постепенно уменьшаясь, превращается в две параллельные линии (как для ребра е на рис. 9.20).
Таким образом, игнорирование ребер скелета с.низкой скоростью распространенна сводится, грубо говоря, к игнорированию слабых изгибов «почти прямых» линий. Более сложный пример показан на рис. 9.23 — 9.25'), где изображен многоугольный объект с одной дырой. Рис. 9.23 показывает его полный скелет. Существует интересная теорема, утверждающая, что скелет любого многоугольника составлен из частей, которые суть либо прямые линии, либо дуги парабол. Фундаментальная причина заключается в том, что геометрическое место точек, равноудаленных от двух прямых линий, есть прямая (биссектриса угла), а геометрическое место точек, равноудаленных от точки и прямой, есть парабола.
На рис. 9.24 показан скелет, на котором стерты все части, имеющие скорость распространения меньше чем 1,25. Единственное изменение наблюдается внизу слева, где стерты ветви, связанные с тупыми углами границы. Если бы объект был восстановлен по этому скелету, его нижний левый угол представлял бы собой четверть круга. На рис. 9.25 порог был повышен до 1,5. Здесь один только скелет (т. е. взятый без функции гашения) весьма близко соответствует тому, что можно считать аппроксимацией объекта «внутренними» линиями. Наше обсуждение до сих пор касалось только объектов, заданных в аналоговой форме. В дискретном случае ситуация в основном та же самая, за исключением того, что здесь трудней использовать евклидову метрику.
Обычно используются приближения к евклидовой метрике, основанные на разного рода изощренных приемах. Кроме того, различные (но эквивалентные) определения скелета могут приводить к более эффективным последовательным реализациям этого существенно параллельного преобразования. Обсуждение этих вопросов увело бы иас несколько в сторону от наших основных интересов, связанных с описанием формы, и мы отсылаем читателя к литературе, приведенной в конце главы.
9.3.6. АНАЛИТИЧЕСКИЕ ОПИСАНИЯ ФОРМЫ Досих пор мы рассмотрели несколько способов, с помощью которых произвольный объект может быть, по крайней мере в принципе, представлен точно. Наиболее прямое из таких представлений просто указывает для каждой точки на плоскости изображения принадлежит ли эта точка объекту. Такое представление называется характеристической функцией объекта; характеристическая функция равна нулю в точках вне объекта и единице в точках внутри него. Очевидно, что характеристическая функция представляет собой обычную з) Во«прон»асхат«я с разрешения Уго Монтанарн. Гл. 9. Описания линии и Формы функцию интенсивности у(х, у), принимающую значения только нуль или единица.
Другой вариант точного представления объекта может быть основан на его естественном уравнении А=й(з), которое задает кривизну границы й как функцию длины дуги з, измеряемой от некоторой произвольной граничной точки. Эти полные описания объекта противоречат нашему замечанию о том, что описание должно быть проще, чем сам описываемый объект. Однако можно использовать различные математические методы, чтобы как-то аппроксимировать эти полные описания и таким путем получить более простые их формы. Обычный подход заключается в разложении точного представления в ряд и в последукпцем использовании только нескольких первых членов ряда. Коэффициенты при этих членах и составляют описание объекта.
Укажем сразу же один возможный вариант описания, который не работает. Мы можем по наивности разложить характеристическую функцию объекта д(х, у) в ряд Тейлора в некоторой точке (х„у,). К сожалению, ряд не сходится к функции д(х, у). В самом деле, для всех точек (х, у) величина разложения должна быть либо нуль, либо единица в зависимости от того, находится точка (х„у,) внутри объекта или снаружи. Вся беда в том, что характеристическая функция существенно разрывна на границе объекта.
В следующих разделах мы будем обсуждать два метода, позволяющие обойти эту трудность. Первый основан на разложении в ряд естественной функции ') объекта; второй тесно связан с ее спектром Фурье. 9.3.6.1. Разложение естеапеенной функции Оперируя с естественной функцией объекта, мы неявно принимаем, что объект не имеет дыр и состоит только из одной связной компоненты. Если объект содержит более чем одну компоненту, мы используем столько естественных функций, сколько имеется компонент. Все дыры объекта игнорируются (хотя мы можем использовать естественную функцию границы дыры).
В данный момент важным для наших целей свойством естественной функции й(з) любого объекта является ее периодичность. Начиная с произвольной граничной точки, функция й(з) определяет кривизну границы в зависимости от длины дуги '). Если длина границы объекта равна Е, легко видеть, что равенство Й(з)=й(з+Е) всегда имеет место независимо от выбора начальной точки, Следовательно, удобной формой представления естественной функции является ряд Фурье. Л имен- з) Этот термин также ооозначает зависимость кривизны от данны дуги.— Прим. нерее.
е) Напомним, что кривизна есть скорость изменения угла по длине дуги. 9.8. Описание формы но мы можем записать функцию я(з) в виде Й(а) = ~', с„ехр ~и — 'зг, зп) ) л=-и визны, то даже несколько членов ряда Фурье обеспечивают хорошую аппроксимацию, и, следовательно, эти коэффициенты оказываются весьма информативными. Отвлечемся на короткое время и рассмотрим потенци- ( 9 альные трудности, связанные с применением естественной 9 функции.
Если в некоторой л".1 ~г-~, точке граница мгновенно изменяет направление, то кривизна в этой точке не определена. Для прямоугольника, например, естественная функ- (,1 ция тождественно равна нулю ~ Я всюду, кроме четырех точек; в Рис. 9.хб. Аппроксимация с помощью ряда Фурье. а) — исходные объекты. б) — пять гармоник, в) — десять гармоник, г) — пятнадцать гармоник (нз книги Брилла, 1969; воспроизводится с разрещения автора). в этих точках функция принимает бесконечное значение. Чтобы избавиться от этого, мы определим новую «естественную функцию» как интеграл от старой; это значит, что мы описываем объект функцией, которая задает тангенс угла наклона границы в зависимости от длины дуги.
Формальным определением новой функции О(з) служит выражение О (з) = ) й (ь) с(ь.) о При этом, однако, возникает новая трудность: функция О(з) непериодическая, поскольку О(з+Е)=О(з)+2зт. Нетрудно, однако, пока. где коэффициенты ся определяются формулой 1 Г зн) с„= — ~ л (з) ехр ~ — и — з ~ с(з. о Для произвольного заданного объекта можно вычислить несколько первых коэффициентов разложения. Эти коэффициенты и составят описание объекта.
Если граница не содержит резких разрывов кри- Гл. р. Описания яииии и формы зать, что функция 0(я) — 2пя|Е периодическая с периодом Е, и поэтому ее можно разложить в ряд Фурье. Мы можем записать еще одну модификацию нашей функции. Заметим, что среднее значение величины 0(я) — 2пя/Е зависит от выбора начальной точки границы. Следовательно, естественно ликвидировать эту зависимость вычитанием среднего. В соответствии с этим мы определим угловую естественную функцию 0(я) выражением б (я) = 0 (я) — — "' — )«, где Эффект от аппроксимация угловой естественной функции усеченным рядом Фурье иллюстрируется рис. 9.26, а — 9.26, г '). На рнс. 9.26, а показан набор нз пяти цифр.
На рнс. 9.26, б — 9.26, г показаны границы, полученные после аппроксимации угловой естественной функции посредством соответственно 5, 10 н 15 членов ряда Фурье. Ясно, что для описания границ с приемлемой точностью достаточно даже небольшого числа членов ряда. 9.3.6.2, Аппроксимация посредством моменпюв Пусть дана произвольная функция интенсивности д(х, у); тогда момент тр«порядка (р, г)) функции у определяется формулой тр« — — )) хну«у(х, у)с(хду, р, г) =О, 1, 2, .... Ф (Поскольку мы определили моменты для произвольных функций интенсивности, то все последующее тем более справедливо для характеристической функции обьекта.) Если функция интенсивности у является достаточно «хорошей» с математической точки зрения, что справедливо для всех физически реализуемых функций интенсивности, то множество моментов тр«обладает свойством фундаментальной важности: моменты определяют единственным образом функцию интенсивности у и единственным образом определяются ею.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
