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

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

Описание алгоритма

Основная идея медианного фильтра состоит в том, чтобы просмотреть запись сигнала за записью, заменяя каждую запись медианой записи и соседних записей. Идея очень похожа на фильтр скользящего среднего , который заменяет каждую запись средним арифметическим значением записи и ее соседей. Шаблон соседей называется «окном», которое скользит, запись за записью, по всему сигналу. Для одномерных сигналов наиболее очевидным окном являются только первые несколько предшествующих и последующих записей, тогда как для двумерных (или многомерных) данных окно должно включать все записи в пределах заданного радиуса, эллипсоидной или прямоугольной области (т. е. , медианный фильтр не является сепарабельным фильтром ). ^{[ нужна ссылка ]}

Проработанный одномерный пример

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

х = (2, 3, 80, 6, 2, 3).

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

y ₀ = med(0, 2, 3) = 2, (граничное значение принимается равным 0)

y ₁ = med(2, 3, 80) = 3, (уже 2, 3 и 80 расположены в порядке возрастания, поэтому расставлять их не нужно)

y ₂ = med(3, 80, 6) = med(3, 6, 80) = 6, (3, 80 и 6 переставляются, чтобы найти медиану)

у ₃ = мед(80, 6, 2) = мед(2, 6, 80) = 6,

у ₄ = мед(6, 2, 3) = мед(2, 3, 6) = 3,

у ₅ = мед(2, 3, 0) = мед(0, 2, 3) = 2,

то есть

у = (2, 3, 6, 6, 3, 2).

Видно, что всплеск шума практически устранен (и сигнал немного сглажен). Результатом фильтра скользящего среднего с той же шириной окна в том же наборе данных будет y = (1,7, 28,3, 29,7, 29,3, 3,7, 1,7). Видно, что всплеск шума заразил соседние элементы сигнала скользящего среднего и что медианный фильтр работает намного лучше (для этого типа импульсного шума). Медианная фильтрация хорошо работает как для положительных импульсов (всплески), так и для отрицательных импульсов (выпадения), при условии, что окно можно выбрать так, чтобы количество записей, зараженных импульсным шумом, (почти) всегда было меньше половины размера окна.

Пограничные вопросы

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

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

Псевдокод двумерного медианного фильтра

Код простого алгоритма двумерного медианного фильтра может выглядеть так:

1. allocate outputPixelValue[image width][image height]
2. allocate window[window width × window height]
3. edgex := (window width / 2) rounded down
4. edgey := (window height / 2) rounded down

    for x from edgex to image width - edgex do
    for y from edgey to image height - edgey do
        i = 0
        for fx from 0 to window width do
            for fy from 0 to window height do
                window[i] := inputPixelValue[x + fx - edgex][y + fy - edgey]
                i := i + 1
        sort entries in window[]
        outputPixelValue[x][y] := window[window width * window height / 2]

Этот алгоритм:

Обрабатывает только один цветовой канал,
Применяет подход «не обрабатывать границы» (см. обсуждение проблем границ выше).

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

Проблемы реализации алгоритма

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

Проработанный двумерный пример

Медианный фильтр работает, рассматривая локальное окно (также известное как ядро) вокруг каждого пикселя изображения. Шаги по применению медианного фильтра следующие:

Выбор окна :
- Выберите окно определенного размера (например, 3x3, 5x5) с центром вокруг пикселя, подлежащего фильтрации.
- В нашем примере возьмем окно размером 3х3.
Соберите значения пикселей :
- Соберите значения пикселей в окне.
- Для центрального пикселя у нас есть следующие значения:
  - Окно: ${\begin{bmatrix}1&2&3\\4&8&6\\7&5&9\end{bmatrix}}$
  - Центральный пиксель: 8
Отсортируйте значения :
- Отсортируйте собранные значения пикселей в порядке возрастания.
- Для центрального пикселя отсортированные значения: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Выберите медианное значение :
- Медианное значение — это среднее значение в отсортированном списке.
- В нашем случае медианное значение равно 5.
Замените центральный пиксель :
- Замените исходное значение центрального пикселя (8) на медианное значение (5).
Повторите для всех пикселей :
- Повторите шаги 2–5 для всех пикселей изображения.

Преобразованное изображение

После применения медианного фильтра ко всем пикселям преобразованное изображение становится: ${\begin{bmatrix}2&3&3\\4&5&6\\7&7&8\end{bmatrix}}$ Это отфильтрованное изображение эффективно удаляет зашумленные пиксели, сохраняя при этом важные характеристики. Помните, что мы предполагали, что виртуальные строки и столбцы с повторяющимися значениями граничных пикселей будут обрабатывать краевые пиксели.

Свойства сохранения кромок

Медианная фильтрация — это один из методов сглаживания, как и линейная фильтрация Гаусса . Все методы сглаживания эффективны для удаления шума в гладких участках или гладких областях сигнала, но отрицательно влияют на края. Однако часто одновременно с уменьшением шума в сигнале важно сохранить края. Например, края имеют решающее значение для внешнего вида изображений. Для небольших и умеренных уровней гауссовского шума медианный фильтр явно лучше, чем размытие по Гауссу , удаляет шум, сохраняя при этом края для заданного фиксированного размера окна. ^[2] Однако его производительность не намного лучше, чем размытие по Гауссу, для высоких уровней шума, тогда как для спекл-шума и шума типа «соль и перец » (импульсивный шум) оно особенно эффективно. ^[3] Из-за этого медианная фильтрация очень широко используется при цифровой обработке изображений .

См. также

Ссылки

^ Хуанг, Томас С.; Ян, Джордж Дж.; Тан, Грегори Ю. (февраль 1979 г.). «Быстрый алгоритм двумерной медианной фильтрации» (PDF) . Транзакции IEEE по акустике, речи и обработке сигналов . 27 (1): 13–18. дои : 10.1109/ТАССП.1979.1163188 .
^ Ариас-Кастро, Эри; Донохо, Дэвид Л. (июнь 2009 г.). «Действительно ли медианная фильтрация сохраняет края лучше, чем линейная фильтрация?» . Анналы статистики . 37 (3): 1172–2009. arXiv : math/0612422 . Бибкод : 2006math.....12422A . дои : 10.1214/08-AOS604 . МР 2509071 . Збл 1160.62086 .
^ Арсе, Гонсало Р. (2005). Нелинейная обработка сигналов: статистический подход . Нью-Джерси, США: Уайли. ISBN 0-471-67624-1 .

Внешние ссылки

Быстрая реализация одномерного медианного фильтра MATLAB
Функция Mathematica MedianFilter
Медианный фильтр
Быстрый двумерный медианный фильтр
Реализация двумерного медианного фильтра в постоянное время (лицензия GPL) – время работы на пиксель этого алгоритма пропорционально количеству элементов в гистограмме (обычно это $2^{n}$ , где n — количество бит на канал), хотя оно, в свою очередь, является константой.
Реализация, написанная на разных языках программирования (на Rosetta Code ).
Статья доктора Доббса
В 100+ раз быстрее взвешенный медианный фильтр
Медианный фильтр по кругу Медианный фильтр для данных с круговыми значениями, таких как изображения фазы или ориентации (C++/Matlab)

[huang79-1] Хуанг, Томас С.; Ян, Джордж Дж.; Тан, Грегори Ю. (февраль 1979 г.). «Быстрый алгоритм двумерной медианной фильтрации» (PDF) . Транзакции IEEE по акустике, речи и обработке сигналов . 27 (1): 13–18. дои : 10.1109/ТАССП.1979.1163188 .

[ariascastro09-2] Ариас-Кастро, Эри; Донохо, Дэвид Л. (июнь 2009 г.). «Действительно ли медианная фильтрация сохраняет края лучше, чем линейная фильтрация?» . Анналы статистики . 37 (3): 1172–2009. arXiv : math/0612422 . Бибкод : 2006math.....12422A . дои : 10.1214/08-AOS604 . МР 2509071 . Збл 1160.62086 .

[arce05-3] Арсе, Гонсало Р. (2005). Нелинейная обработка сигналов: статистический подход . Нью-Джерси, США: Уайли. ISBN 0-471-67624-1 .

[1]

[2]

[3]