Медианная фильтрация - метод нелинейной обработки сигналов, разработанный Тьюки . Этот метод оказывается полезным при подавлении шума на изображении. Одномерный медианный фильтр представляет собой скользящее окно, охватывающее нечетное число элементов, изображения. Центральный элемент заменяется медианой всех элементов изображения в окне. Медианой дискретной последовательности для нечетного является тот ее элемент, для которого существуют элементов, меньших или равных ему по величине, и элементов, больших или равных ему по величине. Пусть в окно попали элементы изображения с уровнями 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. Образцы изображений, обработанных одномерным медианным фильтром с целью подавления гауссова шума.

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

Для уменьшения уровня шума . Медианный фильтр является нелинейным КИХ-фильтром .

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

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

Примеры

Пример 1

Ниже рассматривается пример применения медианного фильтра для одномерного сигнала с окном размером в три отсчёта ко входному массиву x (искусственно введённые продублированные значения показаны полужирно ):

• y = медиана[2 2 80] = 2
• y = медиана = медиана = 6
• y = медиана = медиана = 6
• y = медиана = медиана = 3

и в итоге:

y = - выход медианного фильтра

Пример 2

Медианный фильтр $M$ из входящего сигнала $C$, создаёт медианный образ сигнала $\backslash widetilde\{C\}$. Входящий сигнал $C$, подаётся на медианный фильтр $M:C\; \backslash rightarrow\; \backslash widetilde\{C\}$.
В медианном фильтре сначала производится выбор значений попавших в окно фильтра при нахождении окна в точке $x$, $\backslash hat\{O\}(x):C\; \backslash rightarrow\; O$.
Далее производится сортировка значений окна $O$, функцией сравнения значений $\backslash Phi$, и строится упорядоченное множество $$, а после выбирается медианное значение (медиана ): $$ и записывается в $\backslash widetilde\{C\}(x)=\; o\_\{m\}$.

Таким образом медианный фильтр $M:C\; \backslash rightarrow\; \backslash widetilde\{C\}$, является последовательностью трёх действий:

1. Выбор значений попавших в окно фильтра $\backslash hat\{O\}(x):C\; \backslash rightarrow\; O$.
2. Сортировка значений окна $\backslash Phi(O)\; \backslash rightarrow\; \backslash widetilde\{O\}$.
3. Выбора из $\backslash widetilde\{O\}$ медианного значения $m(\backslash widetilde\{O\})\; \backslash rightarrow\; o\_\{m\}$ и запись его в медианный образ сигнала $\backslash widetilde\{C\}$ в точку с координатой $x$, $\backslash widetilde\{C\}(x)\; =\; o\_\{m\}$.

Данные действия повторяются для каждой точки входящего сигнала.

2D Медианный фильтр (псевдокод)

Алгоритм примитивного 2D Медианного фильтра выглядит примерно так:

Allocate outputPixelValue edgex:= (window width / 2) rounded down edgey:= (window height / 2) rounded down for x from edgex to image width - edgex for y from edgey to image height - edgey allocate colorArray for fx from 0 to window width for fy from 0 to window height colorArray := inputPixelValue sort all entries in colorArray outputPixelValue[x][y] := colorArray

Особенности этого алгоритма:

• Применяется лишь к одному цветовому каналу,
• Не применяется к крайним пикселям.

См. также

Напишите отзыв о статье "Медианный фильтр"

Ссылки

• (англ.)

Отрывок, характеризующий Медианный фильтр

– Как что? – заговорил князь Андрей, останавливаясь от волнения. – Да ты пойми, что мы, или офицеры, которые служим своему царю и отечеству и радуемся общему успеху и печалимся об общей неудаче, или мы лакеи, которым дела нет до господского дела. Quarante milles hommes massacres et l"ario mee de nos allies detruite, et vous trouvez la le mot pour rire, – сказал он, как будто этою французскою фразой закрепляя свое мнение. – C"est bien pour un garcon de rien, comme cet individu, dont vous avez fait un ami, mais pas pour vous, pas pour vous. [Сорок тысяч человек погибло и союзная нам армия уничтожена, а вы можете при этом шутить. Это простительно ничтожному мальчишке, как вот этот господин, которого вы сделали себе другом, но не вам, не вам.] Мальчишкам только можно так забавляться, – сказал князь Андрей по русски, выговаривая это слово с французским акцентом, заметив, что Жерков мог еще слышать его.
Он подождал, не ответит ли что корнет. Но корнет повернулся и вышел из коридора.

Гусарский Павлоградский полк стоял в двух милях от Браунау. Эскадрон, в котором юнкером служил Николай Ростов, расположен был в немецкой деревне Зальценек. Эскадронному командиру, ротмистру Денисову, известному всей кавалерийской дивизии под именем Васьки Денисова, была отведена лучшая квартира в деревне. Юнкер Ростов с тех самых пор, как он догнал полк в Польше, жил вместе с эскадронным командиром.
11 октября, в тот самый день, когда в главной квартире всё было поднято на ноги известием о поражении Мака, в штабе эскадрона походная жизнь спокойно шла по старому. Денисов, проигравший всю ночь в карты, еще не приходил домой, когда Ростов, рано утром, верхом, вернулся с фуражировки. Ростов в юнкерском мундире подъехал к крыльцу, толконув лошадь, гибким, молодым жестом скинул ногу, постоял на стремени, как будто не желая расстаться с лошадью, наконец, спрыгнул и крикнул вестового.
– А, Бондаренко, друг сердечный, – проговорил он бросившемуся стремглав к его лошади гусару. – Выводи, дружок, – сказал он с тою братскою, веселою нежностию, с которою обращаются со всеми хорошие молодые люди, когда они счастливы.
– Слушаю, ваше сиятельство, – отвечал хохол, встряхивая весело головой.
– Смотри же, выводи хорошенько!
Другой гусар бросился тоже к лошади, но Бондаренко уже перекинул поводья трензеля. Видно было, что юнкер давал хорошо на водку, и что услужить ему было выгодно. Ростов погладил лошадь по шее, потом по крупу и остановился на крыльце.
«Славно! Такая будет лошадь!» сказал он сам себе и, улыбаясь и придерживая саблю, взбежал на крыльцо, погромыхивая шпорами. Хозяин немец, в фуфайке и колпаке, с вилами, которыми он вычищал навоз, выглянул из коровника. Лицо немца вдруг просветлело, как только он увидал Ростова. Он весело улыбнулся и подмигнул: «Schon, gut Morgen! Schon, gut Morgen!» [Прекрасно, доброго утра!] повторял он, видимо, находя удовольствие в приветствии молодого человека.
– Schon fleissig! [Уже за работой!] – сказал Ростов всё с тою же радостною, братскою улыбкой, какая не сходила с его оживленного лица. – Hoch Oestreicher! Hoch Russen! Kaiser Alexander hoch! [Ура Австрийцы! Ура Русские! Император Александр ура!] – обратился он к немцу, повторяя слова, говоренные часто немцем хозяином.

Если ваше инженерное образование похоже на мое, тогда вы наверняка много знаете о различных типах линейных фильтров, основная задача которых, пропустить сигнал в одном диапазоне частот и задержать сигналы в остальных диапазонах. Эти фильтры, конечно, незаменимы для многих типов шумов. Однако в реальном мире встраиваемых систем требуется немного времени, чтобы понять, что классические линейные фильтры бесполезны против импульсного шума (burst noise, popcorn noise).

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

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

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

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

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

Фильтр использующий 3 значения (наименьший возможный фильтр),
- фильтр использующий 5, 7 или 9 значений (наиболее используемые),
- фильтр использующий 11 или больше значений.

Сейчас я придерживаюсь более простой классификации:

Фильтр использующий 3 значения,
- фильтр использующий больше 3 значений.

Медианный фильтр на 3

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

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

Для фильтра размером больше 3, я предлагаю вам использовать алгоритм, описанный Филом Экстромом в ноябрьском номере журнала Embedded Systems Programming за 2000 год. Экстром использует связный список. Этот подход хорош тем, что когда массив отсортирован, удаление старого значения и добавление нового не вносит в массив существенный беспорядок. Поэтому этот подход хорошо работает с фильтрами больших размеров.

Имейте ввиду, в оригинальном опубликованном коде были некоторые баги, которые Экстром потом исправил. Учитывая, что на embedded.com сейчас сложно что-то найти, я решил опубликовать свою реализацию его кода. Изначально код был написан на Dynamic C, но для этого поста был портирован на стандартный Си. Код предположительно рабочий, но его полная проверка остается на вашей совести.

#define NULL 0
#define STOPPER 0 /* Smaller than any datum */
#define MEDIAN_FILTER_SIZE 5

uint16_t MedianFilter(uint16_t datum)
{

struct pair{
struct pair *point; /* Pointers forming list linked in sorted order */
uint16_t value; /* Values to sort */
};

/* Buffer of nwidth pairs */
static struct pair buffer = {0};
/* Pointer into circular buffer of data */
static struct pair *datpoint = buffer;
/* Chain stopper */
static struct pair small = {NULL, STOPPER};
/* Pointer to head (largest) of linked list.*/
static struct pair big = {&small, 0};

/* Pointer to successor of replaced data item */
struct pair *successor;
/* Pointer used to scan down the sorted list */
struct pair *scan;
/* Previous value of scan */
struct pair *scanold;
/* Pointer to median */
struct pair *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;
}

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.

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

Медианная фильтрация на базе сортировки

В старой версии этой статьи для медианных фильтров размером 5, 7 или 9, я поддерживал подход на основе алгоритмов сортировки. Сейчас я изменил свою мнение. Однако, если вы хотите использовать их, я предоставляю вам базовый код:

if (ADC_Buffer_Full){

Uint_fast16_t adc_copy;
uint_fast16_t filtered_cnts;

/* Copy the data */
memcpy(adc_copy, ADC_Counts, sizeof(adc_copy));

/* Sort it */
shell_sort(adc_copy, MEDIAN_FILTER_SIZE);

/* Take the middle value */
filtered_cnts = adc_copy[(MEDIAN_FILTER_SIZE - 1U) / 2U];

/* Convert to engineering units */
...

Заключение

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

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

Медианный фильтр реализует нелинейную процедуру подавления шумов. Медианный фильтр представляет собой скользящее по полю изображения окно W, охватывающее нечетное число отсчетов. Центральный отсчет заменяется медианой всех элементов изображения, попавших в окно. Медианой дискретной последовательности x1, x2, ..., xL для нечетного L называют такой ее элемент, для которого существуют (L ? 1)/2 элементов, меньших или равных ему по величине, и (L ? 1)/2 элементов, больших или равных ему по величине. Другими словами, медианой является средний по порядку член ряда, получающегося при упорядочении исходной последовательности.

Например, med(20, 10, 3, 7, 7) = 7.

Двумерный медианный фильтр с окном W определим следующим образом:

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

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

Среди медианных фильтров с окном 3х3 наиболее распространены следующие:

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

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

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

Медиану также можно определить формулой:

где W - множество пикселей, среди которых ищется медиана, а fi - значения яркостей этих пикселей.

Для цветных изображений используется векторный медианный фильтр (VMF):

где Fi - значения пикселей в трехмерном цветовом пространстве, а d - произвольная метрика (например, евклидова).

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

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

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

(8.10)

т.е. результат фильтрации есть медианное значение пикселей окрестности 1 Медианой набора чисел является число из набора, не меньшее половины чисел набора и не большее другой половины чисел набора. , форма которой выбирается произвольно. В разделе 8.2 мы рассмотрели шумоподавление при помощи сглаживающих фильтров. Шум с нулевым математическим ожиданием, добавленный к исходному сигналу, является только одним из видов помех. Медианная фильтрация способна эффективно справляться с помехами в более общем случае, когда помехи независимо воздействуют на отдельные пиксели.Например, такими помехами являются "битые" и "горячие" пиксели при цифровой съемке, "снеговой" шум, когда часть пикселей заменяется на пиксели с максимальной интенсивностью, и т.п. Преимущество медианной фильтрации перед линейной сглаживающей фильтрацией заключается в том, что "горячий" пиксель на темном фоне будет заменен на темный, а не "размазан" по окрестности (рис. 8.6).

Последней парой фильтров, которые мы рассмотрим в этом разделе, являются фильтры минимум и максимум, которые определяются по правилам

(8.11)

(8.12)

т.е. результат фильтрации есть минимальное и максимальное значения пикселей окрестности.