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

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

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

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

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

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

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

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

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

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

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

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

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, но для этого поста был портирован на стандартный Си. Код предположительно рабочий, но его полная проверка остается на вашей совести.

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, я поддерживал подход на основе алгоритмов сортировки. Сейчас я изменил свою мнение. Однако, если вы хотите использовать их, я предоставляю вам базовый код:

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 */
...

Заключение

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

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

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

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

y k = Me(x k-(n-1)/2 ,…, x k ,…,x k+(n-1)/2 ) ,

где Me(x 1 ,…,x n ) = x ((n+1)/2) – элементы вариационного ряда, т.е. ранжированные в порядке возрастания значений x 1 = min (x 1 ,…, x n ) ≤ x (2) ≤ x (3) ≤ … ≤ x n = max (x 1 ,…, x n ) . Ширина медианного фильтра выбирается с учетом того, что он способен подавить импульс шириной (n-1)/2 отсчетов, при условии, что n – нечетное число.

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

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

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

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

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

Фильтр хорошо подавляет одиночные импульсные помехи и случайные шумовые выбросы отсчетов.

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

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

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

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

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

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

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

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

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

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

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

Медианный фильтр реализует нелинейную процедуру подавления шумов. Медианный фильтр представляет собой скользящее по полю изображения окно 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 - произвольная метрика (например, евклидова).

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

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

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

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

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

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

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

. (3.48)

Рассмотрим пример. Предположим, что выборка имеет вид: , а элемент 250, расположенный в ее центре, соответствует текущей точке фильтрации (рис. 3.10). Большое значение яркости в этой точке кадра может быть результатом воздействия импульсной (точечной) помехи. Упорядоченная по возрастанию выборка имеет при этом вид {45,55,75,99,104,110,136,158,250}, следовательно, в соответствии с процедурой (3.48), получаем . Видим, что влияние “соседей” на результат фильтрации в текущей точке привело к “игнорированию” импульсного выброса яркости, что следует рассматривать как эффект фильтрации. Если импульсная помеха не является точечной, а покрывает некоторую локальную область, то она также может быть подавлена. Это произойдет, если размер этой локальной области будет меньше, чем половина размера апертуры МФ. Поэтому для подавления импульсных помех, поражающих локальные участки изображения, следует увеличивать размеры апертуры МФ.

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

Результаты экспериментов, иллюстрирующие работу МФ, приведены на рис. 3.11. В экспериментах применялся МФ, имеющий квадратную апертуру со

стороной равной 3. В левом ряду представлены изображения, искаженные помехой, в правом - результаты их медианной фильтрации. На рис. 3.11.а и рис. 3.11.в показано исходное изображение, искаженное импульсной помехой. При ее наложении использовался датчик случайных чисел с равномерным на интервале законом распределения, вырабатывающий во всех точках кадра независимые случайные числа. Интенсивность помехи задавалась вероятностью ее возникновения в каждой точке. Если для случайного числа , сформированного в точке , выполнялось условие , то яркость изображения в этой точке замещалась числом 255, соответствующим максимальной яркости (уровню белого). На рис. 3.11.а действием импульсной помехи искажено 5 % (=0.05), а на рис. 3.11.в - 10 % элементов изображения. Результаты обработки говорят о практически полном подавлении помехи в первом случае и о ее значительном ослаблении во втором.

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

Табл.3.1. Сравнение эффективности подавления шума при фильтрации изображений, дБ

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

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