Обобщение медианного фильтра

    Аннотация


    В данной статье рассказывается об уникальном фильтре, статья о котором появилась в 1990 году: Маслов А.М., Сергеев В.В. Идентификация линейной искажающей системы с использованием ранговой обработки сигналов // Компьютерная оптика. — М., 1990. — Вып.6. — С.97-102. Данный алгоритм получил название «Алгоритм ранговой обработки» и по факту является обобщением медианного фильтра.
    Применение данного фильтра оправдано в двух случая — для подавления шума и для уменьшения смаза.
    image
    Рисунок 1 — исходное изображение, 2 — смазанное и зашумленное солью.


    Алгоритм ранговой обработки сигнала — экстремальный фильтр


    Алгоритм заключается в обработке изображения локальным окном с записью результата обработки в новое изображение:
    1. Пусть мы находимся в точке изображения с координатами (I,J) - текущий отсчет
    2. Вокруг текущего отсчета рассматривается локальная окрестность размера NxN
    3. По значениям точек в лоальной окрестности строится вариационный ряд, который обозначим p. Размер данного ряда N*N.
    4. В результирующем изображении текущий отсчет принимает значение по следующему правилу:

    image
    где k — параметр алгоритма, N — нечетное число, Im1 — исходное изображение, Im2 — результирующее изображение.
    Если k = (N^2+1)/2 — то есть центр вариационного ряда — данный фильтр становится известным медианным фильтром. В дальнейшем этот параметр будем называть отступом.

    Свойства экстремального фильтра


    Свойства данного фильтр очень полезны на практике, так как фильтр позволяет компенсировать не только шум но устранять (частично) последствия смаза изображения. Предельным случаем этого фильтра при k = (N^2+1)/2 мы имеем медианный фильтр, который только устраняет шум, но не трогает границы, и если изображение смазанное, то смаз так и останется.

    При k < (N^2+1)/2 шум фильтруется несколько хуже, зато повышается резкость изображения, а при k = 0 шум и вовсе не фильтруется, но смаз устранятся самым сильным образом.

    Дабы не утруждать читателей элементарной реализацией данного алгоритма, я приведу здесь код на Matlab.
    Тестирующий скрипт будет читать изображение, смазывать его, и добавлять шум. Затем изображение восстанавливается данным экстремальным фильтров.
    1. I1 = imread('coins.png');
    2. h = ones(3,3) / 9;
    3. I2 = imfilter(I1,h) ;
    4. I3 = imnoise(I2,'salt & pepper',0.02);
    5. I4 = im2_rang_filter (I3, 1, 2);
    6.  
    7. figure; imagesc(I1);
    8. colormap gray;
    9. figure; imagesc(I3);
    10. colormap gray;
    11. figure; imagesc(I4)
    12. colormap gray;
    * This source code was highlighted with Source Code Highlighter.


    Код функции фильтра im2_rang_filter:
    1. function outImage= im2_rang_filter (aImage, aHalfWindowSize, aOtsup)
    2. [ver,hor] = size(aImage);
    3. wsize = (aHalfWindowSize*2+1)^2;
    4. result = zeros(ver,hor);
    5. for i = aHalfWindowSize+1 : (ver - aHalfWindowSize)
    6.   for j = aHalfWindowSize+1 : (hor - aHalfWindowSize)
    7.     
    8.     wind = aImage((i-aHalfWindowSize) : (i + aHalfWindowSize), (j-aHalfWindowSize) : (j + aHalfWindowSize));
    9.     vec = reshape(wind,1,wsize);
    10.     vec = sort(vec);
    11.     
    12.     if (abs(vec(aOtsup+1) - aImage(i,j)) < abs(vec(wsize - aOtsup) - aImage(i,j)) )
    13.       result(i,j) = vec(aOtsup+1);
    14.     else result(i,j) = vec(wsize - aOtsup);
    15.     end;
    16.     
    17.   end;
    18. end;
    19. outImage = result;
    * This source code was highlighted with Source Code Highlighter.

    Экперименты


    Ниже показаны результаты фильтрации окном 3 на 3 при варьировании параметра k = 1,2,5. Первый рисунок — исходное изображение, второй рисунок — искаженное, далее друг за другом идут отфильтрованные при k=1, 2, 5:
    Исходное:
    image
    Искаженное:
    image
    Восстановленное при k=1:
    image
    Восстановленное при k=2:
    image
    Восстановленное при k=5:
    image

    Мне этот фильтр очень нравится и я активно использую его на практике. Интересно мнение читателей об это фильтре.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 45

      +2
      Ну, трудно сказать. Идея интересная, я такую раньше не слышал. А чему у Вас N равно? Сдается мне, что оно большое какое-то. Я бы ставил N или 3 или 5, не больше.

      Давайте разделим задачу на две части:
      а) убрать соль с минимальными последствиями для картинки. Есть спец. алгоритмы для этого, но пусть будет просто median3x3 — но не больше! Иначе уже начнет изменять сама картинка, даже если там нет частички соли.

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

      Потому что устранение соли здесь, имхо, не принципиальный вопрос. Он, как бы, идет довеском. Но задача устранения «соли» очень частная и простая, на ней нет смысла фокусироваться. Интересно обсудить, я думаю, именно такой способ делать sharpening.
        +1
        Ну, все очень и очень зависит от качества изображения и от шумов. Видел я оверсемплированные системы, в которых N=30..50 очень даже оправданно.
        0
        Данные картинки сделаны при N=3, при k=5 мы и получаем медианный фильтр. Тип шума тут особо роли не играет, можно любой поставить эффект будет такой же. При малых k убирается смаз, при больших убирается шум. Согласен. нужно бы посравнивать.
          0
          Интересно…
          А если сравнить этот метод с bilateral filter? Тоже, вроде бы, «смаз» немного убираться должен (где-то в той же пропорции, что и в описанном методе).

          Насчет применения его на картинке с «солью» я не уверен, все-таки уж больно специфический вариант шума. Хотя тоже сработает как-то, конечно.
          А вот на просто зашумленной картинке можно попробовать сравнить.
            0
            Я видел такой способ, что из рабочего окна сначала выкидывают самое большое и самое маленькое значение, а потом уже начинают работать с остатком (делать какой-нибудь denoising).

            Это тоже, идеологически, вариант предложенной техники.
              0
              Да, верно, так и есть. Расскажите поподробнее где такую идеологию еще видели? Насчет сравнения с bilateral filter, думаю сделаю, отпишусь в дополнении к статье.
                0
                У меня такая проблема, что большинство хороших алгоритмов, которые я видел — это конфиденциальная информация((
                Понимаю, звучит как «халявная отмазка», но к сожалению это правда.
                  0
                  Мда это действительно проблема, не только у вас :)
            +7
            Вижу характерные артефакты восстановления. Я их видел в некоторых «восстановленных» (любителями) VHS-лентах и хочу сказать, что оно отвратительно. Возможно, для задач распознавания изображения это и неплохо, но для восстановления изображения для человеческого глаза шумы лучше, чем общая потеря гладкости контура. Этот фильтр сжирает очень много тонких градиентов, которые несут в себе для глаза много информации. С точки зрения компьютера уровень градиентов сравним с уровнем шума, однако, глаз человека таки шум отфильтровывает (в основном по хронологическим данным — предыдущим и последующим кадрам), так что после применения фильтра исчезает больше подробностей, чем шума.
              +1
              На прктике этот алгоритм был примене при идентификации искажающих систем, вот ссылка. Хотя я не замечаю потерю тонких градиентов.
                0
                Статья, кстати, очень интересная. И идет намного дальше. Собственно говоря, ее заявленная цель — определения смазывающего фильтра (а вовсе не восстановление изображения!)
                И уже после того, как смазывающий фильтр определен, оказывается возможным его инвертировать и восстановить, в какой-то степени, исходный сигнал.

                Таким образом это попытка сделать алгоритм blind deconvolution в начале 90х, что имхо очень достойно.
                  0
                  Да, приятно, что вы прочитали эту статью. В этом журнале вообще много всего интересно можно найти, особенно за 90-е года.
                    0
                    У нас здесь, кажется, не понимание по существу. Насколько я понял, предложенный в статье фильтр НЕ используется для очистки картинки от шума! Он используется для определения PSF, с которым был размазана исходная картинка. С тем, чтобы потом сделать обратное преобразование с inv(PSF) и убрать смазывание.

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

                    Или я не правильно понял?
                      +1
                      С пониманием все норм. :) Я не предлагаю использовать этот фильтр для очистки изображения. Я говорю что он обобщает медианный фильтр и потенциально может для этого служить. Даже в статье написано «Разумеется, точно восстановить входной сигнал с помощью экстремального фильтра в реальных ситуациях невозможно». Для определения PSF нужно входное изображение, которое неизвестно. И вместо входного будем подсовывать обработанное этим фильтров, в надежде что дальнейшие регуляризирущие методы позволят вытащить параметры смаза.
                0
                Поддержу автора. Вы видимо сравниваете самую первую картинку с последней. Сравнивать же надо вторую, смазанную и зашумленную, с последней. Потери тонких градиентов лично я не вижу. Шум ушел — это плюс. Но, к сожалению, компенсации смаза тоже не видно…
                  0
                  Компенсация смаза — есть, ее сложно заметить, однако, если взять две картинки и «поморгать» туда-сюда ими, то будет видно, что на восстановленной картинке границы плавные градиенты на границах монетки отступили.
                  +1
                  Вообще-то, такие фильтры по устранению шума необходимы для роботов в системах computer vision.
                  И то, что хорошо для человека, отвратительно для робота.
                  0
                  На исходном изображении градиент фона просматривается, хоть и не идеальный. А вот на результирующем уже смазанные пастели какие-то.

                  Фон промежуточного изображения куда лучше результирующего, за исключением мусора.

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

                      Есть куда более неприятные дефекты, которые действительно надо исправлять — это дрожание кадра, мерцание, плохая контрастность.

                      А мусор, особенно аналоговый (то есть белый шум) совсем не мешает. Точнее, среди всех дефектов, он наименее нарушающий восприятие.
                      +2
                      медианный фильтр плох тем, что мылит, после него надо проходить каким-нибудь син-косом.
                        +1
                        Медианный фильтр наиболее эффективен, если шум на изображении имеет импульсный характер и представляет собой ограниченный набор пиковых значений на фоне нулей. В результате применения медианного фильтра наклонные участки и резкие перепады значений яркости на изображениях не изменяются. Это очень полезное свойство именно для изображений, на которых контуры несут основную информацию. Так что, во многих случаях, правильно подобранная апертура фильтра и его маска, не потребует последующего дополнительного прохода каким-либо фильтром.
                          0
                          проблема в том что «правильно подобраная» может быть сделана только на глаз человеком отдельно для каждого конкретного изображения. Поэтому обычно довольно широкая маска и потом улучшайзинг.
                            0
                            Не совсем так! На практике работают с изображениями полученными с одного устройства — например камера ну или спутник, и параметры искажений которые они вносят на изображение предварительно вычисляются и оцениваются.
                            Ширина смаза — количество отсчетов в КИХ характеристики можно оценить достаточно просто — использовать метод Слепиана, вроде так называется, там с кепстром мудрости премудрости различные.
                            Нужно пользоваться принципом — вся информация об устройстве должна быть учтена в реализации алгоритмов компенсации искажений. Тогда затраты на «улучшайзинг» не понадобятся.
                              0
                              увы, это в вышей узкоспециализированной области. В моей практике всё как раз наоборот. Картинки бывают от идеальных, до ужасных, а обработать надо одинаково хорошо.
                        +2
                        В 2007 году на турнире по программированию давал такую задачку:
                        zcontest.ru/2007.02/zdip.php

                        Лучшие решения на картинках можно посмотреть здесь:
                        zcontest.ru/2007.02/zdip_bestsol.php

                        Так отработало решение победителя на тестовых данных (реальные данные закрыты):
                        zcontest.ru/2007.02/zdip_bestsol_01.php

                        Потом в английской версии задачи народ нашел ещё более качественные решения:
                        www.spoj.pl/ranks/DIP/

                        Можете сравнить свой подход с решениями других людей, отправив свое решение здесь:
                        www.spoj.pl/problems/DIP/
                          0
                          Спасибо, посмотрел. Смутило одно — критерий качества — как я понял классическое СКО? Беда лишь в том, что критерий качества по СКО имеет мало общего с критерием визуального восприятия.
                            0
                            Да. А есть какие-то автоматические и более приближенные к реальности способы сравнить картинки?
                              0
                              Есть, очень много критериев качества было придумано. Поскольку ваши задачки на фильтрацию шума были, то можно взять критерий «линейное разрешение», но для этого нужно картинки генерировать специальные для обработки — если интересно могу подробнее.
                                0
                                Если есть ссылка, то было бы интересно почитать.
                                  0
                                  Порыскал сейчас, ссылки нет, и это очень странно. Про линейное разрешение на на лекциях еще рассказывали и как его высчитать по картинке — так как на книжку ссылаться бесполезно, все равно ее нет в свободном доступе, то поищу методичку какую-нибудь, на след неделе дам вам ссылку.
                          0
                          Интересно, а плагин для AviSynth есть?
                            0
                            Уверен, что этот фильтр не реализован в виде плагина. Да и вообще, возможно это первое упоминание о нем после статьи 1990 года.
                            +1
                            Попробовал почистить вашу «соль» стандартным медианным фильтром GIMPа (режим «адаптивный+рекурсивный», радиус 1, уровень чёрного 0, уровень белого 255). Сравнил. Гимповский лучше — он тоже полностью вычистил весь шум, но тронул всё остальное (градиенты etc) гораздо, гораздо слабее.

                            Также пробовал режим «радиус 3», без адаптивности и рекурсивности, границы те же. Всё равно лучше приведённого в статье.
                              0
                              А можете показать результат?
                                +3
                                GIMP, фильтр «удаление пятен» с параметрами адаптивный, рекурсивный, радиус 1, чёрный 0, белый 255

                                (тоже разновидность медианного фильтра. Если убрать адаптивный и рекурсивный, сделать чёрный -1 и белый 256, то совпадает с фотошоповской «медианой»)

                                Разница для GIMP:


                                Разница вашего k5 из статьи:

                                  0
                                  На третьей картинки я вижу, что контура монеток так же поправились — если вы поле ошибок контрастируете то это будет еще заметнее. — Обратите внимание на фантомные окружности еле заметные на черном фоне — это и есть результат того, что контура поправились.
                                    0
                                    Я тоже сразу вспомнил про despeckle filter.
                                    Только у меня при адаптивном, рекурсивном, 1, 0, 255 оставляет соль. С 1, 0, 254 — нормально.
                                  0
                                  Дело в том что этот фильтр при k=5 и есть медианный фильтр, так что видимо в GIMP иная реализация медианного фильтра. Покажите картинки?
                                • UFO just landed and posted this here
                                    –1
                                    такой шум проще и быстрее заливкой устранять
                                      0
                                      «Проще и быстрее» и заливкой — это как?
                                        –1
                                        шум очень легко детектируется, т.к. он контрастнее остальной картинки. заливаются детекируемые области цветом границ. медиана это конечно хорошо, но если если артефакты будут больше размером, радиус маски будет расти, соответсвенно и время обработки. а в случае с заливкой, время обработки будем зависит от размера изображения.
                                          0
                                          Очень странный алгоритм, первый раз слышу и плохо понимаю. Если есть желание — расскажите о нем поподробнее, с примерами.
                                            –1
                                            двигаясь по очереди по каждому пикселю, проверяем подходит ли он под шум, если да, то проверяем окрестность на шум(и помечаем как области в которых мы уже были, чтоб не проверять ещё раз), при этом заливая участок цветом который был перед участком(так же можно модифицировать заливку, чтоб она двигалась по границе, тем самым брать пограничные цвета), тогда большой участок «шума» будет не так сильно выделяться.

                                    Only users with full accounts can post comments. Log in, please.