Главная > Моделирование, обработка сигналов > Быстрые алгоритмы в цифровой обработке изображений
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

6.3. Стабильные точки двумерных медианных фильтров

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

и пропадает один старый. Следовательно, многообразие структур стабильных точек одномерных медианных фильтров сильно ограничено. Хотя мы не знаем всех свойств стабильных точек второго типа и не знаем, как их получить и еще меньше нам известно о рекуррентных точках обобщенных медианных фильтров, мы высказали весьма полезные соображения относительно их общих характеристик. Кроме того, когда апертура двумерного медианного фильтра) которая не вырождается в линейный сегмент) сдвигается на один шаг, то вводится или пропадает более одного отсчета. Интуитивно ясно, что это расширяет наши возможности и стабильные точки двумерных медианных фильтров будут значительно сложнее или менее структурированы, чем их одномерные аналоги. Примеры стабильных точек показывают, что они могут сильно напоминать стабильные точки второго типа в одной области, оставаясь локально-монотонными в другой; для одномерного случая это неверно. Мы еще вернемся к этому.

В гл. 5 показано, что изображения с перепадами сохраняются после двумерной медианной фильтрации, если апертура симметрична и имеет центр. Благодаря своей практической важности ранее рассматривались только апертуры этого типа, и именно такие апертуры будут подразумеваться в этой главе. Изображение перепада напоминает ступенчатую функцию в одномерном случае; в обоих случаях это простейшие монотонные функции. Как указано в начале разд. 6.1, локальной монотонности достаточно, чтобы сделать последовательность стабильной точкой. По аналогии можно ожидать, что изображение будет инвариантно медианной фильтрации с апертурой А до тех пор, пока оно остается монотонным в пределах апертуры, когда ее центр передвигается от одного элемента изображения к другому. Необходимо точное определение монотонности, которое будет дано позднее. Следуя гипотезе, изложенной в [6.10], мы сначала разложим двумерную апертуру на строки и предположим, что то, что требуется от всей апертуры, истинно также для каждой строки. Будем считать, что апертура содержит начало координат (0,0) и симметрична относительно него.

Лемма 6.2. Пусть А — апертура и — произвольная линия в . Если

для всех проходящих через начало координат, то медиана

Доказательство. Из предположения, что А включает начало координат (0,0) и симметрична относительно него, имеем, что должна содержать нечетное число точек и, чтобы выполнялось (6.5), половина отсчетов, не считая должна быть больше или равна а другая половина — меньше или равна . Так как все линии, проходящие через начало координат, не пересекаются нигде, кроме начала координат, то, исключая точку (0,0), половина

на отсчетов в А должна быть больше или равна а другая — меньше или равна

Будем говорить, что для апертуры А изображение локально-монотонно по отношению к А, если для всех сдвигов изображения относительно апертуры и для всех линий которые проходят через точку (0,0), центр апертуры, монотонна в пределах отрезков линий, попадающих в апертуру.

Лемма 6.3. Если изображение является локально-монотонным по отношению к апертуре А, то оно является стабильной точкой медианного фильтра с апертурой, равной А или являющейся подмножеством А.

Доказательство. Предположим, что для любого монотонно на для всех проходящих через начало координат; следовательно,

Тогда доказательство следует просто из леммы 6.2.

Для ослабления требования локальной монотонности в приведенной лемме мы можем рассмотреть следующий класс апертур.

Определение. Апертура А является -симметричной, если в дополнение к тому, что она содержит начало координат и симметрична относительно него, она содержит все точки пересечения 2,2 и конечного линейного сегмента для всех в А, где — линейный сегмент, соединяющий точки и

Теперь допустим, что является произвольной линией в - симметричная апертура. Тогда точки, содержащиеся в будут расположены периодически. Для точки на обозначим через число точек, содержащихся в где означает апертуру А, смещенную так, что ее центр находится в точке . В результате периодичности число не зависит от выбранного и является нечетным вследствие симметричности апертуры А. На самом деле, все линии в параллельные имеют одно и то же Теорема которая распространяет теорему 6.1 на двумерный случай, является обобщением результата, полученного в [6.10] путем использования идеи локально-монотонных последовательностей.

Теорема 6.8. Пусть А является -симметричной апертурой, а — изображение. Если для каждой линии отсчеты на ней локально-монотонны на длине то инвариантно к медианной фильтрации с -симметричной апертурой, равной А или являющейся подмножеством А.

Доказательство. Так как отсчеты на линии проходящей через произвольную точку локально-монотонны на длине то по теореме 6.1 они инвариантны к одномерной медианной фильтрации с апертурой, размер которой меньше или равен Для любой -симметричной апертуры В, аналогичной апертуре А или являющейся ее подмножеством, а

пересечение будет под сегментом из последовательно расположенных точек на с центром в Следовательно,

В силу леммы 6.2 теорема доказана.

Аналогично теореме 6.4 для данной теоремы также существует обратная. Доказательство ее не отличается от доказательства теоремы 6.4 и потому опускается.

Теорема 6.9. Если изображение инвариантно к любой медианной фильтрации с -симметричной апертурой, которая аналогична А или является ее подмножеством, где А -симметрична, то отсчеты на любой линии локально-монотонны на длине

Если изображение инвариантно к любой медианной фильтрации с -симметричной апертурой, то согласно теореме 6.9 ее пересечение с любой линией из должно быть монотонным. Изображения, обладающие этим свойством, называются монотонными во всех направлениях [6.10] и, как оказывается, имеют простую структуру. Юстуссоном был обнаружен следующий результат [6.10].

Если монотонно во всех направлениях, то существует наклон такой, что для всех или для всех В случае неравенство заменяется более простым неравенством Наклон единствен, если только не является константой.

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

Рис. 6.1. Некоторые двумерные апертуры и соответствующие им стабильные точки

Достаточные условия, приведенные в лемме 6.3 или в теореме 6.8, обычно трудно выполнить, особенно для больших апертур. На рис. 6.1 показаны некоторые двоичные изображения, которые для нескольких -симметричных апертур удовлетворяют достаточному условию теоремы 6.8 (оно является менее жестким, чем условие леммы 6.3). Эти двоичные изображения могут рассматриваться либо как однородные объекты на однородном белом фоне, либо как выходные сигналы функций уровня Они строятся следующим образом.

Для каждой апертуры изучим те направленные линейные сегменты (спицы), которые начинаются в центре (основании) и кончаются в точке на границе (верхушке). Каждый из этих линейных сегментов можно определить, задав его угол с сегментом, соединяющим центр, допустим, точку (0,0) и точку (1,0). Тогда можно легко увидеть, что каждый объект имеет границу, которая является кусочно-линейной и образована этими линейными сегментами, расположенными в порядке возрастания или уменьшения 0, причем основание каждого связано с верхушкой предыдущего. Поэтому объект является выпуклой группой в с указанной границей. Не все двоичные изображения, полученные этим способом, являются локально-монотонными в смысле теоремы 6.8. Например, если используемая апертура имеет форму креста, состоящего из пяти точек (0,0) и , где то объект, построенный таким образом, имеет граничные точки и локальная монотонность в смысле теоремы 6.8 в центре объекта не сохраняется. Однако она, по-видимому, сохраняется, если апертура А удовлетворяет следующему условию:

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

Возвращаясь к рис. 6.1, можно сделать следующие наблюдения. Во-первых, ни одна из апертур не является вырожденной. Во-вторых, каждый объект является наименьшим конечным выпуклым объектом, который сохраняется при медианной фильтрации с соответствующей апертурой. Даже несмотря на поставленное ограничение, что каждая линия должна быть локально-монотонной и инвариантной к , оказывается, что в случае конечного выпуклого объекта достаточное условие теоремы 6.8 является также необходимым для того, чтобы объект сохранялся при медианной фильтрации. Наконец, по аналогии с тем, как мы построили границу каждого выпуклого объекта, можно было бы предположить, что, в общем, для того, чтобы двоичное изображение гладких объектов на равномерном фоне было инвариантным к медианной фильтрации с невырожденной -симметричной апертурой, будет необходимым и достаточным следующее условие: выпуклая часть границ объектов или фона должна складываться из хорд длиной, большей или равной размерам апертуры, и соответствующие хорды любых двух связанных сегментов контуров должны также являться смежными хордами апертуры. Это наложило бы некоторые ограничения на контуры сохраняемых изображений. К сожалению, такое условие не является ни необходимым, ни достаточным. В самом деле, определение таких понятий, как граница или линейные сегменты границы для двоичных изображений общего вида, является достаточно широким.

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

Рис. 6.2. Примеры стабильных точек для квадратной апертуры

кроме масштаба, и все три инвариантны к медианному фильтру с квадратной апертурой , обозначенной через А. Если о гладкости судить по локальной монотонности в квадратной апертуре (см. определение после леммы 6.2), то а и б нигде не являются локально-монотонными по отношению к А. Изображение локальномонотонно по отношению к А везде, кроме тех седловых точек типа где это неверно. При еще меньшем масштабе изображение, которое остается стабильней точкой медианного фильтра с апертурой А, становится более гладким; однако указанные седловые точки также сохраняются. Следовательно, изображение на рис. 6.2.5 можно рассматривать как стабильную точку смешанного тина.

<< Предыдущий параграф Следующий параграф >>
Оглавление