Если ваше инженерное образование похоже на мое, тогда вы наверняка много знаете о различных типах линейных фильтров, основная задача которых, пропустить сигнал в одном диапазоне частот и задержать сигналы в остальных диапазонах. Эти фильтры, конечно, незаменимы для многих типов шумов. Однако в реальном мире встраиваемых систем требуется немного времени, чтобы понять, что классические линейные фильтры бесполезны против импульсного шума (burst noise, popcorn noise).
Импульсные шумы обычно возникает от псевдо случайных событий. Например, рядом с вашим устройством может переключаться двухполосный радиоприемник или может произойти какой-нибудь статический разряд. Всякий раз когда это происходит, входной сигнал может временно искажаться.
Например, в результате аналогово-цифрового преобразования мы получаем такой ряд значений: 385, 389, 912, 388, 387. Значение 912 предположительно аномальное и его нужно отклонить. Если вы попробуете использовать классический линейный фильтр, то заметите, что значение 912 будет оказывать значительное влияние на выходной результат. Лучшим решением в этом случае будет использование медианного фильтра .
Несмотря на очевидность такого подхода, мой опыт говорит, что медианные фильтры используются во встраиваемых системах удивительно редко. Возможно это связано с недостатком знаний об их существовании и трудностью с реализацией. Надеюсь мой пост в некоторой степени устранит эти препятствия.
Идея медианного фильтра проста. Он выбирает из группы входных значений среднее и выдает на выход. Причем обычно группа имеет нечетное количество значений, поэтому проблемы с выбором не возникает
До недавнего времени я выделял три класса медианных фильтров, отличающихся количеством используемых значений:
Фильтр использующий 3 значения (наименьший возможный фильтр),
- фильтр использующий 5, 7 или 9 значений (наиболее используемые),
- фильтр использующий 11 или больше значений.
Сейчас я придерживаюсь более простой классификации:
Фильтр использующий 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, я предлагаю вам использовать алгоритм, описанный Филом Экстромом в ноябрьском номере журнала 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 */
...
Использование медианных фильтров связанно с определенными затратами. Очевидно, что медианные фильтры добавляют задержку ступенчато меняющимся значениям. Также медианные фильтры могут полностью затирать частотную информацию в сигнале. Конечно, если вас интересуют только постоянные значения, то это не проблема.
С учетом этих оговорок, я все-таки настоятельно рекомендую вам использовать в своих разработках медианные фильтры.
В настоящее время методы цифровой обработки сигналов получили широкое распространение в телевидении, радиотехнике, системах связи, управления и контроля. Одной из самых распространённых операций при такой обработке является цифровая фильтрация сигналов.
Медианная фильтрация была предложена Тьюки в качестве инструмента сглаживания временных рядов, встречающихся в экономических исследованиях , а в дальнейшем она стала широко применяться при обработке изображений, речевых сигналов и т. п. Медианная фильтрация осуществляется посредством движения некоторой апертуры вдоль последовательности дискретных отсчётов и замены значения в центре апертуры медианой исходных отсчётов внутри апертуры.
Cущность медианной фильтрации с трехотсчётным окном иллюстрируется на рис. 1, где “1” - непрозрачная пластина с тремя отверстиями А, В и С; 2 - лента с наносимыми на ней отсчётами и располагаемыми с шагом, равным расстоянию между отверстиями. Лента протягивается дискретно на один шаг за один такт. В отверстиях одновременно наблюдаются три отсчёта, из которых выбирается средний. Не среднее арифметическое значение, не отсчёт в среднем отверстии, а среднее значение из трёх упорядоченно расположенных отсчётов. Так, упорядочив отсчёты, показанные на рис. 1, мы имеем значения 24, 27, 29, то есть средним является отсчёт 27 в отверстии А.
В общем случае медианой
последовательности y1, y2, ... , ym (m - нечётное) является средний по значению член ряда, получаемый после упорядочения последовательности по возрастанию. Для чётного m медиана определяется как среднее арифметическое двух средних членов. В литературе можно найти и другие определения, но они мало отличаются друг от друга, а в подавляющем большинстве случаев принимают m нечётным .
Хотя структура одномерного цифрового медианного фильтра с трехотсчётным окном известна , здесь она рассматривается как пример инженерного проектирования
цифрового устройства с простым и легко понятным алгоритмом работы, выполненного с применением комбинационных узлов, описанных в предыдущих статьях учебного цикла .
В цифровой системе функции отверстий А, В и С (рис. 1) выполняют три регистра А, В и С (рис. 2). Регистр А является регистром данных какого-либо устройства, работающего в условиях сильных промышленных помех, например, преобразователя температуры в цифру. Все эти регистры имеют единую систему синхронизации, обеспечивающую запись данных в регистр А, загрузку содержимого регистра А в регистр В и содержимого регистра В в регистр С. Перед началом процедуры фильтрации все регистры обнуляются. Началом процедуры является момент появления первого отсчёта в регистре А. Так, например, если входная последовательность имеет вид 22, 29, 24, 27, 31, 40, 28, 32, 29,... (22 - первый отсчёт), то в первом такте будем иметь следующие значения отсчётов: А = 22, В = 0, С = 0, откуда следует, что средний отсчёт равен 0. Во втором такте будем иметь А = 29, В = 22, С = 0, откуда следует, что средний отсчёт равен 22 и т. д. Итак, выходная последовательность будет иметь вид: 0, 22, 24, 27, 27, 31, 31, 32, 29,... .
Очевидно, что медианный фильтр с трехотсчётным окном осуществляет задержку выходной последовательности на один такт по отношению к входной.
Кроме указанных регистров аппаратная реализация такого фильтра должна включать в себя n-разрядный мультиплексор MS 4->1, в котором будут использоваться только три информационных входа (n - число двоичных разрядов цифрового отсчёта), и три цифровых компаратора, обеспечивающих сравнение каждого отсчёта с каждым, что можно рассматривать как замену процедуры упорядочения. Это позволяет снизить аппаратные затраты и время вычисления медианы. Напомним, что упорядочение требует выполнения операций сравнения и перестановки отсчётов.
Отметим прежде всего, что нет необходимости учитывать отношения равенства отсчётов, так как при равенстве двух или трёх отсчётов любой из них может рассматриваться как средний. Выберем соотношения A > B, A > C, B > C, обозначив соответствующие сигналы с выходов трёх цифровых компараторов переменными x2, x1 и x0. Примем, что если указанные соотношения выполняются, то соответствующие выходные сигналы компараторов принимают значение “1”, если не выполняются, то - “0”. Итак, задача проектирования нашего фильтра сводится к выявлению структуры комбинационной схемы (КС), реализующей адресные переменные а1 и а0 мультиплексора MS 4->1, обеспечивающего автоматическую передачу среднего отсчёта из трёх, поступивших на его информационные входы.
Оформим таблицу, в которой представлены: № набора - десятичный эквивалент двоичного набора трёх переменных x2, x1 и x0; комментарий - это условная гистограмма из трёх отсчётов А, В и С, качественно соответствующая ситуации, отражённой одним из восьми наборов переменных x2, x1 и x0; в столбце “средний отсчёт” указывается средний отсчёт, выявленный из соответствующей гистограммы. Так, в первой строке имеем набор x2x1x0 = 000, из которого следует, что A < B, A < C, B < C. Эта ситуация качественно показана в столбце “комментарий”, из которого следует, что в данном случае средним является отсчёт В. Так как на рис. 2 отсчёт В поступает на вход D1 MS 4->1, то в этой строке указываем значения а1 = 0, а0 = 1 (первый вариант кодирования адресных переменных в таблице). При наборе x2x1x0 = 001 имеем ситуацию A < B, A < C, B > C, которая отражена соответствую-щей гистограммой, а из послед-ней следует, что средним отсчётом в данном случае является отсчёт С. Соответственно устанавливаем а1 = 1, а0 = 0.
| № наб. | х2 А>В |
х1 А>С |
х0 В>С |
Средний отсчет | 1 вариант | 2 вариант | ||
| а1 | а0 | а1 | а0 | |||||
| 0 | 0 | 0 | 0 | В | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | С | 1 | 0 | 1 | 0 |
| 2 | 0 | 1 | 0 | - | х | х | х | х |
| 3 | 0 | 1 | 1 | А | 0 | 0 | 0 | 1 |
| 4 | 1 | 0 | 0 | А | 0 | 0 | 0 | 1 |
| 5 | 1 | 0 | 1 | - | х | х | х | х |
| 6 | 1 | 1 | 0 | С | 1 | 0 | 1 | 0 |
| 7 | 1 | 1 | 1 | В | 0 | 1 | 0 | 0 |
Набор x2x1x0 = 010 никогда не будет появляться на выходах цифровых компараторов, так как он соответствует невозможной ситуации A < B, A > C, B < C, поэтому в соответствующей строке таблицы адресные переменные а1 и а0 обозначены крестиком как безразличные значения. Аналогично заполняются все строки таблицы. Рассматривая а1 и а0 как функции алгебры логики от переменных x2, x1 и x0 и используя для их минимизации карты Карно (рис. 3) , получаем
Попытаемся устранить инвертор, необходимый для реализации x2 или x0 в формуле (2). Для этого перекодируем адресные переменные а1 и а0, приняв, что отсчёт А подаётся на вход D1, а В - на вход D0 MS 4®1 (второй вариант в таблице). На рис. 4 приведены карты Карно для второго варианта кодирования адресных переменных а1 и а0, из которых следует:
 |
 |
Рис. 3 |
Рис. 4 |
Очевидно, что второй вариант кодирования предпочтительнее. Итак, комбинационная схема (КС), структуру которой мы определили, представляет из себя два элемента “сумма по mod2”.
Убедимся в справедливости отмеченного выше замечания о том, что нет необходимости учитывать соотношения равенства. Рассмотрим следующие ситуации:
Если на выходах цифровых компараторов используются соотношения “больше или равно”, то будем иметь:
Достоинства и недостатки медианных фильтровДостоинства
Недостатки
|
Проведённый анализ подтверждает то, что при проектировании структуры комбинационной схемы КС можно использовать на выходах цифровых компараторов любые комбинации соотношений “больше”, “больше или равно”, “меньше”, “меньше или равно”.
Литература
Величина является порогом фильтрации .В приложениях используется еще целый ряд простейших нелинейных фильтров. Например, модуль изображения, содержащего пиксели с отрицательным значением, или фильтр, обнуляющий все значения пикселей, меньше данного порога.
Более сложным фильтром, задействующим в вычислениях окрестность пикселя, является медиана. Медианная фильтрация определяется следующим образом:
| (8.10) |
т.е. результат фильтрации есть медианное значение пикселей окрестности 1 Медианой набора чисел является число из набора, не меньшее половины чисел набора и не большее другой половины чисел набора. , форма которой выбирается произвольно. В разделе 8.2 мы рассмотрели шумоподавление при помощи сглаживающих фильтров. Шум с нулевым математическим ожиданием, добавленный к исходному сигналу, является только одним из видов помех. Медианная фильтрация способна эффективно справляться с помехами в более общем случае, когда помехи независимо воздействуют на отдельные пиксели.Например, такими помехами являются "битые" и "горячие" пиксели при цифровой съемке, "снеговой" шум, когда часть пикселей заменяется на пиксели с максимальной интенсивностью, и т.п. Преимущество медианной фильтрации перед линейной сглаживающей фильтрацией заключается в том, что "горячий" пиксель на темном фоне будет заменен на темный, а не "размазан" по окрестности (рис. 8.6).
Последней парой фильтров, которые мы рассмотрим в этом разделе, являются фильтры минимум и максимум, которые определяются по правилам
| (8.11) |
| (8.12) |
т.е. результат фильтрации есть минимальное и максимальное значения пикселей окрестности.
ВВЕДЕНИЕ
Лекция 16. МЕДИАННЫЕ ФИЛЬТРЫ
Медианные фильтры достаточно часто применяются на практике как средство предварительной обработки цифровых данных. Специфической особенностью фильтров является слабая реакция на отсчеты, резко выделяющиеся на фоне соседних. Это свойство позволяет применять медианную фильтрацию для устранения аномальных значений в массивах данных, уменьшения импульсных помех. Характерной особенностью медианного фильтра является его нелинейность. Во многих случаях применение медианного фильтра оказывается более эффективным по сравнению с линейными фильтрами, поскольку процедуры линейной обработки являются оптимальными при равномерном или гауссовом распределении помех, что в реальных сигналах может быть далеко не так. В случаях, когда перепады значений сигналов велики по сравнению с дисперсией аддитивного белого шума, медианный фильтр дает меньшее значение среднеквадратической ошибки по сравнению с оптимальными линейными фильтрами. Особенно эффективным медианный фильтр оказывается при очистке сигналов от импульсных шумов при обработке изображений, акустических сигналов, передаче кодовых сигналов и т.п. Однако детальные исследования свойств медианных фильтров как средства фильтрации сигналов различного типа являются довольно редкими.
Принцип фильтрации. Медианный фильтр представляет собой оконный фильтр, последовательно скользящий по массиву сигнала, и возвращающий на каждом шаге один из элементов, попавших в окно (апертуру) фильтра. Выходной сигнал y k скользящего медианного фильтра шириной 2n+1 для текущего отсчета k формируется из входного временного ряда …, x k -1 , x k , x k +1 ,… в соответствии с формулой:
y k = Me(x k - n , x k - n +1 ,…, x k -1 , x k , x k +1 ,…, x k + n -1 , x k + n), (16.1.1)
где Me(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).
Одномерные фильтры. Медианная фильтрация реализуется в виде процедуры локальной обработки отсчетов в скользящем окне, которое включает определенное число отсчетов сигнала. Для каждого положения окна выделенные в нем отсчеты ранжируются по возрастанию или убыванию значений. Средний по своему положению отчет в ранжированном списке называется медианой рассматриваемой группы отсчетов. Этим отсчетом заменяется центральный отсчет в окне для обрабатываемого сигнала.
Алгоритм медианной фильтрации обладает явно выраженной избирательностью к элементам массива с немонотонной составляющей последовательности чисел в пределах апертуры и наиболее эффективно исключает из сигналов одиночные выбросы, отрицательные и положительные, попадающие на края ранжированного списка. С учетом ранжирования в списке медианные фильтры хорошо подавляют шумы и помехи, протяженность которых составляет менее половины окна. Монотонные составляющие сигналов медианный фильтр оставляет без изменений.
| Рис. 16.1.1. |
Благодаря этой особенности, медианные фильтры при оптимально выбранной апертуре могут сохранять без искажений резкие границы объектов, подавляя некоррелированные и слабо коррелированные помехи и малоразмерные детали. При аналогичных условиях алгоритмы линейной фильтрации неизбежно «смазывает» резкие границы и контуры объектов. На рис. 16.1.1 приведен пример обработки сигнала с импульсными шумами медианным и треугольным фильтрами с одинаковыми размерами окна N=3. Преимущество медианного фильтра очевидно.
Окно медианного фильтра, как правило, устанавливается нечетным. В общем случае окно может быть и четным, при этом медиана устанавливается, как среднее арифметическое двух средних отсчетов. В качестве начальных и конечных условий фильтрации обычно принимаются концевые значения сигналов, либо медиана находится только для тех точек, которые вписываются в пределы апертуры.
Рис. 16.1.2.
|
На рис. 16.1.2 приведен пример медианной фильтрации модельного сигнала a k , составленного из детерминированного сигнала s k в сумме со случайным сигналом q k , имеющим равномерное распределение с одиночными импульсными выбросами. Окно фильтра равно 5. Результат фильтрации – отсчеты b k .
Двумерные фильтры. Основную информацию в изображениях несут контуры объектов. При фильтрации зашумленных изображений степень сглаживания контуров объектов напрямую зависит от размеров апертуры фильтра. При малых размерах апертуры лучше сохраняются контрастные детали изображения, но в меньшей степени подавляется импульсные шумы. При больших размерах апертуры наблюдается обратная картина. Это противоречие в некоторой степени сглаживается при применении фильтров с адаптацией размеров апертуры под характер изображения. В адаптивных фильтрах большие апертуры используются в монотонных областях обрабатываемого сигнала (лучшее подавление шумов), а малые – вблизи неоднородностей, сохраняя их.
Рис. 16.1.3.
|
Кроме размеров окна эффективность фильтра в зависимости от характера изображения и параметров статистики шумов существенно зависит от формы маски выборки отсчетов. Примеры формы масок с минимальной апертурой приведены на рис. 16.1.3. Оптимальный выбор формы сглаживающей апертуры зависит от специфики решаемой задачи и формы объектов.
На рис. 16.1.4 приведен пример очистки зашумленного изображения медианным фильтром Черненко /2i/. Зашумление изображения по площади составляло 15%, для очистки фильтр применен последовательно 3 раза.
 
Рис. 16.1.4.
|
Достоинства медианных фильтров.
Недостатки медианных фильтров.
Недостатки метода можно уменьшить, если применять медианную фильтрацию с адаптивным изменением размера окна фильтра в зависимости от динамики сигнала и характера шумов (адаптивная медианная фильтрация). В качестве критерия размера окна можно использовать, например, величину отклонения значений соседних отсчетов относительно яркости центрального ранжированного отсчета /1i/. При уменьшении этой величины ниже определенного порога размер окна увеличивается.
Медианный фильтр реализует нелинейную процедуру подавления шумов. Медианный фильтр представляет собой скользящее по полю изображения окно 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 - произвольная метрика (например, евклидова).
Однако в чистом виде медианный фильтр размывает мелкие детали, величина которых меньше размера окна для поиска медианы, поэтому на практике практически не используется.
