6.4. Алгоритм быстрой медианной фильтрации

Интересный и эффективный алгоритм двумерной медианной фильтрации с произвольной апертурой был предложен Хуангом и другими [6.4]. Используется тот факт, что при смещении на один отсчет убирается только часть отсчетов, содержащихся в апертуре, и столько же отсчетов добавляется. Этот раздел основывается на [6.4].

Хотя алгоритм работает для произвольных апертур, мы используем в качестве примера прямоугольную апертуру где — число столбцов. Предполагается, что апертура перемещается слева направо по горизонтали и возвращается назад при переходе к следующей строке. Пограничные точки не рассматриваются; их можно обрабатывать, уменьшая размеры апертуры, как и в одномерном случае. Изображение квантовано, скажем, на 256 уровней. Тогда для элементов изображения первого (начального) положения апертуры вычисляются и с каждым следующим шагом вправо корректируются: 1) ГИСТ — гистограмма распределения значений; 2) МДН - медиана, 3) МЧМ — число элементов изображения, значения которых меньше МДН.

При движении апертуры направо на один шаг каждый элемент изображения левого крайнего столбца предыдущей апертуры убирается; гистограмма и счетчик, корректируются следующим образом:

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

После этого ГИСТ дает гистограмму для текущего положения апертуры, а счетчик МЧМ будет содержать число элементов в данной

ной апертуре, имеющих значения, меньшие, чем медиана при предыдущем положении апертуры.

Затем медиана в данном положении апертуры находится путем уменьшения (или увеличения) МДН в зависимости от того, превышает МЧМ отношение , которое мы обозначим через П, или нет. Сначала

Возможны такие случаи.

Случай что указывает на то, что МДН больше медианы в данном положении апертуры. Тогда вводим коррекцию

пока не получим

Случай 2. МЧМЛ, что указывает на то, что МДН меньше или равна медиане в данном положении апертуры. Проверим неравенство

Если оно не справедливо, то МДН точно является требуемой медианой. Если оно справедливо, что свидетельствует о том, что все еще меньше или равна требуемой медиане, то вводим коррекцию

и возвращаемся к (6.10).

Очевидно, каждая из операций (6.6) и (6.7) требует сравнений. Пусть равна медиане на предыдущей апертуре. Для случая и (6.9) требуют сравнений; для случая и (6.10) требуют ( сравнений. Пусть Тогда математическое ожидание будет равно

где — среднее значение Считая, что имеем . В [6.4] отмечено, что обычно мало, и экспериментальные результаты показывают, что оно меньше 10. Поскольку мало, возможна значительная экономия времени вычислений даже при малых . При увеличении размеров апертуры преимущества этого алгоритма по сравнению с теми, которые не используют общности элементов в рассматриваемой апертуре с предшествующим элементом, становится все более заметными.