Одномерный цифровой медианный фильтр с трехотсчетным окном. Недостатки медианных фильтров

1. Техническое задание

Гауссов шум - ‘gaussian’

Исходное изображение.

Принцип фильтрации.

Медианы давно использовались и изучались в статистике как альтернатива средним арифметическим значениям отсчетов в оценке выборочных средних значений. Медианой числовой последовательности х 1 , х 2 , … , х n при нечетном n является средний по значению член ряда, получающегося при упорядочивании этой последовательности по возрастанию (или убыванию). Для четных n медиану обычно определяют как среднее арифметическое двух средних отсчетов упорядоченной последовательности.

Медианный фильтр представляет собой оконный фильтр, последовательно скользящий по массиву сигнала, и возвращающий на каждом шаге один из элементов, попавших в окно (апертуру) фильтра. Выходной сигнал y k скользящего медианного фильтра шириной 2n+1 для текущего отсчета k формируется из входного временного ряда …, x k -1 , x k , x k +1 ,… в соответствии с формулой:

y k = med(x k - n , x k - n+1 ,…, x k -1 , x k , x k +1 ,…, x k + n-1 , x k + n),

где med(x 1 , …, x m , …, x 2n+1) = x n+1 , x m – элементы вариационного ряда, т.е. ранжированные в порядке возрастания значений x m: x 1 = min(x 1 , x 2 ,…, x 2n+1) ≤ x (2) ≤ x (3) ≤ … ≤ x 2n+1 = max(x 1 , x 2 ,…, x 2n+1).

Таким образом, медианная фильтрация осуществляет замену значений отсчетов в центре апертуры медианным значением исходных отсчетов внутри апертуры фильтра. На практике апертура фильтра для упрощения алгоритмов обработки данных, как правило, устанавливается с нечетным числом отсчетов, что и будет приниматься при рассмотрении в дальнейшем без дополнительных пояснений.

Импульсные и точечные шумы

При регистрации, обработке и обмене данными в современных измерительно-вычислительных и информационных системах потоки сигналов кроме полезного сигнала s(t-t 0) и флуктуационных шумов q(t) содержат, как правило, импульсные потоки g(t)= d(t-t k) различной интенсивности с регулярной или хаотической структурой:

x(t) = s(t-t 0) + g(t) + q(t).

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

Допустим, что шум q(t) представляет собой статистический процесс с нулевым математическим ожиданием, полезный сигнал s(t-t 0) имеет неизвестное временное положение t 0 Î , а поток шумовых импульсов g(t) имеет вид:

g(t) = e k a k g(t-t k),

где a k - амплитуда импульсов в потоке, t k - неизвестное временное положение импульсов, e k =1 с вероятностью p k и e k =0 с вероятностью 1-p k . Такое задание импульсной помехи соответствует потоку Бернулли.

При применении к потоку x(t) скользящей медианной фильтрации с окном N отсчетов (N – нечетное) медианный фильтр полностью устраняет одиночные импульсы, удаленные друг от друга минимум на половину апертуры фильтра, и подавляет импульсные помехи, если количество импульсов в пределах апертуры не превосходит (N-1)/2. В этом случае, при p k = p для всех импульсов помехи, вероятность подавления помех может быть определена по выражению /3i/:

R(p) = p m (1-p) N- p .

На рис.1 приведены результаты расчетов вероятности подавления импульсной помехи медианным фильтром. При p<0.5 результаты статистического моделирования процесса показывают хорошее соответствие расчетным значениям. Для интенсивных импульсных шумовых потоков при p>0.5 медианная фильтрация становится мало эффективной, т.к. происходит не подавление, а усиление и трансформация его в поток импульсов другой структуры (со случайной длительностью).

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

Перепад плюс шум.

Рассмотрим фильтрацию перепадов при наличии аддитивного белого шума, т. е. фильтрацию последовательностей, или изображений, с

где s - детерминированный сигнал, равный 0 по одну сторону or перепада и h - по другую, a z - случайные значения белого шума. Предположим, что случайные значения шума z распределены по нормальному закону N(0, s). Для начала рассмотрим одномерную фильтрацию и будем считать, что перепад происходит в точке i = 1, таким образом, что для i£0 величина x i есть N(0, s), а для i≥1 величина х i есть N(h, s).

На рис. 2 показана последовательность значений математического ожидания медиан и скользящего среднего вблизи перепада высотой h = 5 при N = 3. Значения скользящего среднего следуют по наклонной линии, что свидетельствует о смазывании перепада. Поведение математического ожидания значений медианы также свидетельствует о некотором смазывании, хотя в гораздо меньше, чем для скользящего среднего.

Если воспользоваться мерой среднеквадратичной ошибки (СКО), усредненной по N точкам вблизи перепада, и вычислить значения СКО в зависимости от значений h, то нетрудно зафиксировать, что при малых значениях h<2 СКО для скользящего среднего немного меньше, чем для медианы, но при h>3 СКО медианы значительно меньше, чем СКО среднего. Этот результат показывает, что скользящая медиана значительно лучше, чем скользящее среднее, для перепадов большой высоты. Похожие результаты можно получить и для апертуры N=5, и для двумерной фильтрации с апертурами 3x3 и 5x5. Таким образом, математические ожидания медианы для малых h близки к математическим ожиданиям для соответствующих средних, но для больших h они асимптотически ограничены. Объясняется это тем, что при больших h (скажем, h>4) переменные х со средним значением 0 (для данного примера) будут резко отделены от переменных х со средним h.

Использованная мера точности может характеризовать только резкость поперек перепада и ничего не говорит о гладкости фильтрованного изображения вдоль перепада. Скользящее усреднение дает сигналы, гладкие вдоль перепада, тогда как при обработке с помощью медианным фильтром протяженные перепады оказываются слегка изрезанными.

Фильтрация Винера

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

Спектральная плотность сигнала определяется соотношением:

где – автокорреляционная функция.

Взаимная спектральная плотность сигнала определяется соотношением:

, (14)

где – функция взаимной корреляции.

При построении фильтра Винера ставится задача минимизации среднеквадратического отклонения обработанного изображения от предмета:

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

Дальнейший анализ показывает, что восстановление изображения, формирование которого описывается выражением должно осуществляться с использованием следующего ОПФ восстанавливающего преобразователя:

Если шума на изображении нет, то спектральная плотность функции шума равна 0 и выражение, которое называют фильтром Винера, превращается в обычный обратный фильтр.

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

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

ОПФ Фильтры Винера

Инверсные фильтры

Рис. 3. Примеры фильтров

Фильтрация изображений.

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

Рис.4

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

Под изображением перепада понимаем изображение, в котором точки по одну сторону от некоторой линии имеют одинаковое значение а , а все точки по другую сторону от этой линии - значение b , b ¹a . Если апертура фильтра симметрична относительно начала координат, то медианный фильтр сохраняет любое изображение перепада. Это выполняются для всех апертур с нечетным количеством отсчетов, т.е. кроме апертур (квадратные рамки, кольца), которые не содержат начала координат. Тем не менее квадратные рамки и кольца будут лишь незначительно изменять перепад.

Для упрощения дальнейшего рассмотрения ограничимся примером фильтра с квадратной маской размером N × N, при N=3. Скользящий фильтр просматривает отсчеты изображения слева-направо и сверху-вниз, при этом входную двумерную последовательность также представим в виде последовательного числового ряда отсчетов {x(n)} слева-направо сверху-вниз. Из этой последовательности в каждой текущей точке маска фильтра выделяет массив w(n), как W-элементный вектор, который в данном случае содержит все элементы из окна 3×3, центрированные вокруг x(n), и сам центральный элемент, если это предусмотрено типом маски:

w(n) = .

В этом случае значения x i соответствует отображению слева-направо и сверху-вниз окна 3×3 в одномерный вектор.

Элементы данного вектора, как и для одномерного медианного фильтра, также могут быть упорядочены в ряд по возрастанию или убыванию своих значений:

r(n) = ,

определено значение медианы y(n) = med(r(n)), и центральный отсчет маски заменен значением медианы. Если по типу маски центральный отсчет не входит в число ряда 8, то медианное значение находится в виде среднего значения двух центральных отсчетов ряда 9.

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

Медианная фильтрация может выполняться и в рекурсивном варианте, при котором значения сверху и слева от центрального отсчета в маске (в данном случае x 1 (n)-x 4 (n) на рис. 9) в ряде 8 заменяются на уже вычисленные в предыдущих циклах значения y 1 (n)-y 4 (n).

Результаты обработки

Наложение шумов на оригинальное изображение

Gaussian Salt & Paper Speckle

Результат обработки Медианным фильтром

MedFilter_Gaussian MedFilter_Salt & Paper MedFilter_Speckle

Результат обработки фильтром Винера

WinFilter_Gaussian WinFilter_ Salt & Paper WinFilter_ Speckle

Результат подсчета среднеквадратическогоотклонения отфильтрованных изображенийот оригинала.

ВЫВОД

На графике видно, что медианный фильтр хорошо подавляет одиночные импульсные помехи и случайные шумовые выбросы отсчетов (CKOSaPeMed) и по графику видно, что это лучший метод по устранению данного вида зашумления.

Фильтр Винера (CKOSaPeWin),в отличии от медианного фильтра, при увеличении коэффициента зашумленности изображения, удалялся от оригинала в несколько раз.

Подавление белого и гауссового шума,в случае медианного фильтра, менее эффективно (CKOGausMed, CKOSpecMed), чем у фильтра Винера (CKOGausWin, CKOSpecWin). Слабая эффективность наблюдается также при фильтрации флюктуационного шума. При увеличении размеров окна Медиального фильтра происходит размытие изображения.

Список Литературы

1. Цифровая обработка цветных изображений. Шлихт Г.Ю. М., Издательство ЭКОМ, 2007. – 336 с.

2. http://prodav.narod.ru/dsp/index.html

3. Введение в цифровую обработку изображений. Ярославский Л.П. М.: Сов. радио, 2007. – 312 с.

4. http://matlab.exponenta.ru/

5. Цифровая обработка изображений в среде MATLAB. Р. Гонсалес, Р. Вудс, С. Эддинс, М.: Техносфера, 2006.

6. http://www.chipinfo.ru/literature/chipnews/199908/29.html

1.Техническое задание....................................................................... 2

2.Анализ технического задания.................................................... 3

2.1. Медианный фильтр. Медианная фильтрация................... 4

2.1.1 Достоинства и недостатки медианных фильтров.............................. 6

2.2 Принцип фильтрации..................................................................... 7

2.3 Подавление статистических шумов.................................... 8

2.4 Импульсные и точечные шумы................................................ 9

2.5 Перепад плюс шум........................................................................ 11

2.6 Фильтрация Винера....................................................................... 13

2.7. Фильтрация изображений......................................................... 15

2.7.1 Использование адаптивной фильтрации..................... 17

2.7.2 Использование медианной фильтрации....................... 17

3. ПРОЕКТИРОВАНИЕ ВСПОМОГАТЕЛЬНОЙ ФУНКЦИИ MATLAB. 18

3.1. Считывание изображения и создание его копии............................... 18

3.2. Добавление шумов к копии исходного изображения................... 18

3.3. Обработка зашумленной копии при помощи медианного фильтра. 18

3.4. Обработка зашумленной копии при помощи фильтра Винера....... 20

3.5. Расчет СКО между фильтрованным изображением и оригиналом. 21

4.Результаты обработки.................................................................... 23

Список Литературы............................................................................. 26

1. Техническое задание

Сравнение эффективности медианного и усредняющего фильтров

1. Создать копию исходного изображения.

2. Добавить шум к копии исходного изображения.

Гауссов шум - ‘gaussian’

Импульсный шум - ‘salt&pepper’

Мультипликативный шум - ‘speckle’

4. Одну из зашумлённых копий обработать при помощи фильтра.

5. Другую копию обработать при помощи фильтра 2.

7. Построить графики зависимости СКО отфильтрованного изображения от параметра шума (в одних осях для разных фильтров).

Исходное изображение.

2. Анализ технического задания

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

Медианный фильтр. Медианная фильтрация

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

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

Медиа́нный фи́льтр - один из видов цифровых фильтров, широко используемый в цифровой обработке сигналов и изображений для уменьшения уровня шума. Медианный фильтр является нелинейным КИХ-фильтром.

Значения отсчётов внутри окна фильтра сортируются в порядке возрастания (убывания); и значение, находящееся в середине упорядоченного списка, поступает на выход фильтра. В случае четного числа отсчетов в окне выходное значение фильтра равно среднему значению двух отсчетов в середине упорядоченного списка. Окно перемещается вдоль фильтруемого сигнала и вычисления повторяются.

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

Медианная фильтрация.

Медианная фильтрация осуществляет замену значений отсчетов в центре апертуры медианным значением исходных отсчетов внутри апертуры фильтра. На практике апертура фильтра для упрощения алгоритмов обработки данных, как правило, устанавливается с нечетным числом отсчетов, что и будет приниматься при рассмотрении в дальнейшем без дополнительных пояснений.

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

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

Недавно пришлось столкнуться с необходимостью программной фильтрации данных АЦП. Гугление и курение (различной документации) привело меня к двум технологиям: Фильтр низких частот (ФНЧ) и Медианный фильтр. Про ФНЧ есть весьма подробная статья в сообществе Easyelectronics , поэтому далее речь пойдёт про медианный фильтр.

Дисклеймер (отмазка): Эта статья по большей частью является практически дословным переводом статьи с сайта embeddedgurus . Однако, переводчик (я) тоже использовал приведенные алгоритмы в работе, нашёл их полезными, и, возможно, представляющими интерес для этого сообщества.

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

Этот тип шума обычно возникает от какого-либо случайного события, такого, как электростатический разряд, сработавший рядом с прибором брелок сигнализации и прочее. При этом входной сигнал может принять заведомо невозможное значение. Например, с АЦП поступили данные: 385, 389, 388, 388, 912, 388, 387. Очевидно, что значение 912 тут ложное, и должно быть отброшено. При использовании классического фильтра, почти наверняка это большое число повлияет на выходное значение очень сильно. Очевидным решением тут будет применение медианного фильтра.

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

Отличия медианы от среднего арифметического

Предположим, что в одной комнате оказалось 19 бедняков и один миллиардер. Каждый кладёт на стол деньги - бедняки из кармана, а миллиардер - из чемодана. По $5 кладёт каждый бедняк, а миллиардер - $1 млрд (109). В сумме получается $1 000 000 095. Если мы разделим деньги равными долями на 20 человек, то получим $50 000 004,75. Это будет среднее арифметическое значение суммы наличных, которая была у всех 20 человек в этой комнате.

Медиана в этом случае будет равна $5 (полусумма десятого и одиннадцатого, срединных значений ранжированного ряда). Можно интерпретировать это следующим образом. Разделив нашу компанию на две равные группы по 10 человек, мы можем утверждать, что в первой группе каждый положил на стол не больше $5, во второй же не меньше $5. В общем случае можно сказать, что медиана это то, сколько принёс с собой средний человек. Наоборот, среднее арифметическое - неподходящая характеристика, так как оно значительно превышает сумму наличных, имеющуюся у среднего человека.
ru.wikipedia.org/wiki/Медиана_ (статистика)

По размеру этого множества разделим фильтры на два типа:
Размерность = 3
Размерность > 3

Фильтр размерностью 3

Размерность три - наименьшая из возможных. Вычислить среднее значение возможно, использовав лишь несколько операций IF. Ниже приведён код, реализующий этот фильтр:

Uint16_t middle_of_3(uint16_t a, uint16_t b, uint16_t c) { uint16_t middle; if ((a <= b) && (a <= c)) { middle = (b <= c) ? b: c; } else if ((b <= a) && (b <= c)) { middle = (a <= c) ? a: c; } else { middle = (a <= b) ? a: b; } return middle; }

Фильтр размерностью >3

Для фильтра размерностью больше трёх предлагаю воспользоваться алгоритмом, предложенным Филом Экстормом (Phil Ekstrom) в Ноябрьском номере журнала «Embedded Systems», и переписанного с Dynamic C на стандартный С Найджелом Джонсом (Nigel Jones). Алгоритм использует односвязный список, и использует тот факт, что когда массив отсортирован, удаление самого старого значения, и добавление нового не нарушает сортировку.

#define STOPPER 0 /* Smaller than any datum */ #define MEDIAN_FILTER_SIZE (13) uint16_t median_filter(uint16_t datum) { struct pair { struct pair *point; /* Pointers forming list linked in sorted order */ uint16_t value; /* Values to sort */ }; static struct pair buffer = {0}; /* Buffer of nwidth pairs */ static struct pair *datpoint = buffer; /* Pointer into circular buffer of data */ static struct pair small = {NULL, STOPPER}; /* Chain stopper */ static struct pair big = {&small, 0}; /* Pointer to head (largest) of linked list.*/ struct pair *successor; /* Pointer to successor of replaced data item */ struct pair *scan; /* Pointer used to scan down the sorted list */ struct pair *scanold; /* Previous value of scan */ struct pair *median; /* Pointer to median */ uint16_t i; if (datum == STOPPER) { datum = STOPPER + 1; /* No stoppers allowed. */ } if ((++datpoint - buffer) >= MEDIAN_FILTER_SIZE) { datpoint = buffer; /* Increment and wrap data in pointer.*/ } datpoint->value = datum; /* Copy in new datum */ successor = datpoint->point; /* Save pointer to old value"s successor */ median = &big; /* Median initially to first in chain */ scanold = NULL; /* Scanold initially null. */ scan = &big; /* Points to pointer to first (largest) datum in chain */ /* Handle chain-out of first item in chain as special case */ if (scan->point == datpoint) { scan->point = successor; } scanold = scan; /* Save this pointer and */ scan = scan->point ; /* step down chain */ /* Loop through the chain, normal loop exit via break. */ for (i = 0 ; i < MEDIAN_FILTER_SIZE; ++i) { /* Handle odd-numbered item in chain */ if (scan->point == datpoint) { scan->point = successor; /* Chain out the old datum.*/ } if (scan->value < datum) /* If datum is larger than scanned value,*/ { datpoint->point = scanold->point; /* Chain it in here. */ scanold->point = datpoint; /* Mark it chained in. */ datum = STOPPER; }; /* Step median pointer down chain after doing odd-numbered element */ median = median->point; /* Step median pointer. */ if (scan == &small) { break; /* Break at end of chain */ } scanold = scan; /* Save this pointer and */ scan = scan->point; /* step down chain */ /* Handle even-numbered item in chain. */ if (scan->point == datpoint) { scan->point = successor; } if (scan->value < datum) { datpoint->point = scanold->point; scanold->point = datpoint; datum = STOPPER; } if (scan == &small) { break; } scanold = scan; scan = scan->point; } return median->value; }
Чтобы воспользоваться этим кодом, просто вызываем функцию каждый раз, когда появляется новое значение. Она вернёт медианное из последних MEDIAN_FILTER_SIZE измерений.
Этот подход требует довольно много RAM, т.к. приходится хранить и значения, и указатели. Однако он довольно быстрый (58мкс на 40МГц PIC18).

Выводы

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

Медианная фильтрация - метод нелинейной обработки сигналов, разработанный Тьюки . Этот метод оказывается полезным при подавлении шума на изображении. Одномерный медианный фильтр представляет собой скользящее окно, охватывающее нечетное число элементов, изображения. Центральный элемент заменяется медианой всех элементов изображения в окне. Медианой дискретной последовательности для нечетного является тот ее элемент, для которого существуют элементов, меньших или равных ему по величине, и элементов, больших или равных ему по величине. Пусть в окно попали элементы изображения с уровнями 80, 90, 200, 110 и 120; в этом случае центральный элемент следует заменить значением 110, которое является медианой упорядоченной последовательности 80, 90, 110, 120, 200. Если в этом примере значение 200 является шумовым выбросом в монотонно возрастающей последовательности, то медианная фильтрация обеспечит существенное улучшение. Напротив, если значение 200 соответствует полезному импульсу сигнала (при использовании широкополосных датчиков), то обработка приведет к потере четкости воспроизводимого изображения. Таким образом, медианный фильтр в одних случаях обеспечивает подавление шума, в других - вызывает нежелательное подавление сигнала.

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

Рис. 12.6.1. Примеры медианной фильтрации простейших дискретных сигналов, .

а - ступенчатый переход: б - пилообразный переход; в - одиночный импульс; е - сдвоенный импульс; д - строенный импульс; е - треугольный сигнал.

Возможности анализа действия медианного фильтра ограничены. Можно показать, что медиана произведения постоянной и последовательности равна

Кроме того,

Однако медиана суммы двух произвольных последовательностей и не равна сумме их медиан:

Это неравенство можно проверить на примере последовательностей 80, 90, 100, 110, 120 и 80, 90, 100, 90, 80.

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

Концепцию медианного фильтра легко обобщить на два измерения, применяя двумерное окно желаемой формы, например прямоугольное или близкое к круговому. Очевидно, что двумерный медианный фильтр с окном размера обеспечивает более эффективное подавление шума, чем последовательно примененные горизонтальный и вертикальный одномерные медианные фильтры с окном размера ; двумерная обработка, однако, приводит к более существенному ослаблению сигнала. На рис. 12.6.2 показано влияние двумерной медианной фильтрации на пространственный импульсный сигнал. Использовались фильтры с окнами двух типов: квадратным размера и крестообразным размера . Как видно, медианный фильтр с квадратным окном разрушил углы изображенного квадрата, а фильтр с крестообразным окном оставил его без изменения.

Рис. 12.6.2. Примеры двумерной медианной фильтрации

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

Рис. 12.6.3. Образцы изображений, обработанных одномерным медианным фильтром с целью подавления импульсных помех.

а - исходное изображение с импульсными помехами (15 искаженных элементов в каждой строке); б - результат медианной фильтрации при ; в - результат медианной фильтрации при ; г - результат медианной фильтрации при .

Рис. 12.6.4. Образцы изображений, обработанных одномерным медианным фильтром с целью подавления гауссова шума.

а - исходное изображение с гауссовым шумом ; б - результат медианной фильтрации при ; в - результат медианной фильтрации при ; г - результат медианной фильтрации при .

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

Многие нелинейные и ЛПНИ-фильтры для реставрации изображений описаны в . В гл. 5 предыдущего тома, посвященного линейным фильтрам , были описаны калма-новские ЛПНИ-фильтры, используемые для подавления шума при реставрации изображений. В гл. 5 и 6 этого тома рассмотрена особая нелинейная процедура - медианная фильтрация. Обнаружено, что применение медианных фильтров эффективно для подавления некоторых видов шума и периодических помех без одновременного искажения сигнала . Такие фильтры стали весьма популярны в обработке изображений и речевых сигналов.

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

Глава 6 посвящена детерминированным свойствам медианных фильтров. Особенно интересными представляются результаты, относящиеся к так называемым стабильным точкам медианных фильтров. Стабильной точкой является последовательность (в одномерном случае) или массив (в двумерном случае), которые не изменяются при медианной фильтрации. В гл. 6 Тян показал, что в одномерном случае стабильными точками медианных фильтров являются «локально-монотонные» последовательности. Исключение составляют некоторые периодические двоичные последовательности. В последнее время Галлагер и Вайс сумели устранить это исключение, ограничив длину последовательностей.

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

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

Медианные фильтры особенно удобны для борьбы с импульсным (точечным) шумом. Этот факт иллюстрируется на рис. 1.2. На рис. 1.2, а показан результат передачи изображения 1.1, а по двоичному симметричному каналу с шумом при использовании импульсно-кодовой модуляции. В этом случае на изображении появляется импульсный шум. Применение медианного фильтра позволяет подавить большую часть шумовых выбросов (рис. 1.2, б),

(кликните для просмотра скана)

в то время как линейное сглаживание оказывается совершенно неэффективным (рис. 1.2, в).

Хотя в гл. 5 и 6 обсуждаются двумерные (пространственные) фильтры, очевидно, что к движущимся изображениям, таким, как телевизионные, могут применяться трехмерные медианные фильтры (пространственно-временные), т. е. апертура фильтра может быть трехмерной. Медианная временная фильтрация особенно удобна для подавления пачек шумовых выбросов, включая выпадение строк. Кроме того, она намного лучше, чем временное усреднение (линейное сглаживание), сохраняет движение. В описано несколько экспериментов по временной фильтрации (включая фильтрацию с компенсацией движения). В одном из экспериментов по фильтрации последовательность кадров панорамирования, содержащая белый гауссовский шум и случайные выпадения строк, подвергалась медианной фильтрации и линейному сглаживанию. Кадровая частота последовательности составляла 30 кадров/с, каждый кадр содержал примерно 200 строк по 256 элементов в каждой с 8 бит/отсчет. Панорамирование проводилось горизонтально со скоростью примерно 5 элементов изо бражения на кадр. Результаты по одному кадру показаны на рис. 1.3: зашумленный исходный кадр (а), тот же кадр после линейного сглаживания (б) и кадр, обработанный медианным фильтром (в). Необходимо отметить, что медианный фильтр дает

Рис. 1.3. (см. скан) Временная фильтрация последовательности кадров панорамирования: а - зашумленный оригинал; б - линейное сглаживание по трем кадрам; в - медианная фильтрация по трем кадрам

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

Хотя и медианная фильтрация и линейное сглаживание используются для улучшения субъективного качества изображения, пока не ясно, способствуют ли они дальнейшему машинному анализу изображений - распознаванию образов или измерениям на изображении. Были проведены тщательные исследования влияния линейной и медианной фильтрации на эффективность выделения контуров, анализ формы и текстурный анализ. Некоторые результаты приведены в .

Медианная фильтрация – метод нелинейной обработки сигналов, разработанный Тьюки. Этот метод оказывается полезным при подавлении шума на изображении. Одномерный медианный фильтр представляет собой скользящее окно, охватывающее нечетное число элементов изображения. Центральный элемент заменяется медианой всех элементов в окне. Медианой дискретной последовательности для нечетного N является тот ее элемент, для которого существуют элементов, меньших или равных ему по величине, и элементов, больших или равных ему по величине.

Пусть в окно попали элементы изображения с уровнями 80, 90, 200, 110 и 120; в этом случае центральный элемент следует заменить значением 110, которое является медианой упорядоченной последовательности 80, 90, 110, 200. Если в этом примере значение 200 является шумовым выбросом в монотонно возрастающей последовательности, то медианная фильтрация обеспечит существенное улучшение. Напротив, если значение 200 соответствует полезному импульсу сигнала (при использовании широкополосных датчиков), то обработка приведет к потере четкости воспроизводимого изображения. Таким образом, медианный фильтр в одних случаях обеспечивает подавление шума, в других вызывает нежелательное подавление сигнала.

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

составляет менее половины ширины окна. Фильтр также вызывает уплощение вершины треугольной функции.

Возможности анализа действия медианного фильтра ограничены. Можно показать, что медиана произведения постоянной и последовательности равна:

кроме того,

Однако медиана суммы двух произвольных последовательностей и не равна сумме их медиан:

Это неравенство можно проверить на примере последовательностей 80, 90, 100, 110, 120 и 80, 90, 100, 90, 80.

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

Другая возможность состоит в осуществлении каскадной медианной фильтрации сигнала с использованием фиксированной или изменяемой ширины окна. В общем слу

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

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