Фильтрация изображений методом свертки

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

    Введение.


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


    Немного теории.


         Итак, фильтры, которые были перечислены, а так же множество других основаны на свертке. Что же такое свертка? Свертка (англ. convolution) — это операция, показывающая «схожесть» одной функции с отражённой и сдвинутой копией другой. Понятие свёртки обобщается для функций, определённых на группах, а также мер. Несколько сложноватое определение, не так ли? Те, кому интересна математическая теоретическая часть, могут заглянуть по ссылке на Википедию, и, возможно, почерпнуть для себя что нибудь полезное.

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

         Итак, свертка – это операция вычисления нового значения выбранного пикселя, учитывающая значения окружающих его пикселей. Для вычисления значения используется матрица, называемая ядром свертки. Обычно ядро свертки является квадратной матрицей n*n, где n — нечетное, однако ничто не мешает сделать матрицу прямоугольной. Во время вычисления нового значения выбранного пикселя ядро свертки как бы «прикладывается» своим центром (именно тут важна нечетность размера матрицы) к данному пикселю. Окружающие пиксели так же накрываются ядром. Далее высчитывается сумма, где слагаемыми являются произведения значений пикселей на значения ячейки ядра, накрывшей данный пиксель. Сумма делится на сумму всех элементов ядра свертки. Полученное значение как раз и является новым значением выбранного пикселя. Если применить свертку к каждому пикселю изображения, то в результате получится некий эффект, зависящий от выбранного ядра свертки.

         На этом мы закончим с теорией, и перейдем к примерам и реализации данного алгоритма. Мозг еще жив? :)

    Несколько примеров.







    Реализация алгоритма.


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

    public static class Convolution
      {
        public static Bitmap Apply(Bitmap input, double[,] kernel)
        {
          //Получаем байты изображения
          byte[] inputBytes = BitmapBytes.GetBytes(input);
          byte[] outputBytes = new byte[inputBytes.Length];

          int width = input.Width;
          int height = input.Height;

          int kernelWidth = kernel.GetLength(0);
          int kernelHeight = kernel.GetLength(1);

          //Производим вычисления
          for (int x = 0; x < width; x++)
          {
            for (int y = 0; y < height; y++)
            {
              double rSum = 0, gSum = 0, bSum = 0, kSum = 0;

              for (int i = 0; i < kernelWidth; i++)
              {
                for (int j = 0; j < kernelHeight; j++)
                {
                  int pixelPosX = x + (i - (kernelWidth / 2));
                  int pixelPosY = y + (j - (kernelHeight / 2));
                  if ((pixelPosX < 0) ||
                    (pixelPosX >= width) ||
                    (pixelPosY < 0) ||
                    (pixelPosY >= height)) continue;

                  byte r = inputBytes[3 * (width * pixelPosY + pixelPosX) + 0];
                  byte g = inputBytes[3 * (width * pixelPosY + pixelPosX) + 1];
                  byte b = inputBytes[3 * (width * pixelPosY + pixelPosX) + 2];

                  double kernelVal = kernel[i, j];

                  rSum += r * kernelVal;
                  gSum += g * kernelVal;
                  bSum += b * kernelVal;

                  kSum += kernelVal;
                }
              }

              if (kSum <= 0) kSum = 1;

              //Контролируем переполнения переменных
              rSum /= kSum;
              if (rSum < 0) rSum = 0;
              if (rSum > 255) rSum = 255;

              gSum /= kSum;
              if (gSum < 0) gSum = 0;
              if (gSum > 255) gSum = 255;

              bSum /= kSum;
              if (bSum < 0) bSum = 0;
              if (bSum > 255) bSum = 255;

              //Записываем значения в результирующее изображение
              outputBytes[3 * (width * y + x) + 0] = (byte)rSum;
              outputBytes[3 * (width * y + x) + 1] = (byte)gSum;
              outputBytes[3 * (width * y + x) + 2] = (byte)bSum;
            }
          }
          //Возвращаем отфильтрованное изображение
          return BitmapBytes.GetBitmap(outputBytes, width, height);
        }
      }

    * This source code was highlighted with Source Code Highlighter.


    Скачать программу пример

    Вот и все. Надеюсь что данный материал был полезен и преподнес вам что-то новое. Если данная тема вас заинтересовала, то могу написать еще про базовые методы формирования ядер свертки, а так же про оптимизации данного алгоритма. Спасибо за внимание!
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 63

      +1
      Если интересно, то в java присутствует стандартный класс — ColorTransform, который позволяет обработать данное изображение указываемой матрицей.

      И как-то вы с оригинальным определением завернули сложно. Применительно к обработке изображений это определение заставляет мозг сделать лоботомию изнутри, особенно сейчас, после работы :) Хорошо, что расшифровали потом :)
        0
        Вы не путаете случайно с другим типом матричного преобразования? В том же .NET есть такая вещь как ColorMatrix — матрица 4x4, которая преобразует цвета — аналог того, что в Фотошопе называется Channel Mixer кажется. Так это немного другое.
          0
          Вроде бы нет. ColorMatrix в .NET оперирует в цветовом пространстве, а не в пространстве координат изображения. Хотя насчет названия ColorTransform я уже не уверен :)
          +1
          В java для этого — ConvolveOp
          java.sun.com/javase/6/docs/api/java/awt/image/ConvolveOp.html
        +1
        А можно где-нибудь посмотреть какие еще бывают ядра и понять почему то или иное ядро работает именно так?
          +5
          Хороший вопрос.
          Посоветовать ресурс, где есть все и сразу, не смогу, так как сам искал и не нашел.
          Если постараться ответить кратко, то понять, почему ядро работает именно так, можно прочитав алгоритм и посмотрев на матрицу ядра. Например Box Blur — это вычисление среднего арифметического цветов пикселей, окружающих данный пиксель (берем их все с коэффициентом 1). Gaussian blur — среднее арифметическое с коэффициентами, поэтому размытие получается более мягким.
          Нахождение краев и повышение резкости — по сути дифференцирование.
          Хотя конечно вот так быстро и на пальцах не все объяснишь, да и нет смысла. Постараюсь в ближайшее время написать более подробно отдельный топик про это.
            +1
            И тем не менее, вашего ответа вполне достаточно для понятия сути :) По крайней мере я понял.

            Спасибо :)
            +4
            Есть хорошая книга «Р. Гонсалес, Р. Вудс, Цифровая Обработка Изображений».

            Все ядра получены чисто из эвристических соображений. И если понять как работает алгоритм «применения ядра свертки», то становится понятно почему само ядро имеет такой вид. Для простоты можно рассмотреть черно-белое изображение где каждый пиксель имеет один параметр — яркость(от 0 до 255). Взяв, например, черный квадрат на белом фоне, можно применить к нему ядро выделения вертикальных границ(как в топике). Тогда понятно, что белый фон(яркость 255) это ядро перекрасит в черный(яркость станет 0), потому что 1*255+1*255+1*255+0*255+0*255+0*255 -1*255 -1*255 -1*255 = 0. Тоже самое будет и с черным фоном -останется яркость 0. А вот на границе черного и белого(вертикальные стороны) будет 1*255+1*255+1*255+0*255+0*255+0*255 -1*0 -1*0 -1*0= 255 * 3 =253 (mod 256) то есть примерно белый. Что и требовалось. :)
              +1
              О, у меня же эта книжка на работе стоит. Я про нее и забыл совсем :)
              +2
              Смотрите любой курс по цифровой обработке сигналов (например, книжку Гонсалес, Вудс). Ядро свертки — это коэффициенты фильтра с конечным временем отклика (FIR-фильтр), применяемого к изображению. Коэффициенты свертки получаются путем применения обратного преобразования Фурье к передаточной функции фильтра. (Для изображений, передаточная функция фильтра — это матрица, в которой задаются коэффициенты усиления для разных частот сигналов, составляющих изображение).
              При этом высокие частоты соответствуют границам объектов, а низкие частоты — фону и плавным переходам.
              Сглаживание — это фильтр, который убирает высокие частоты из изображения. Выделение границ — это фильтр, который убирает низкие частоты из изображения. Повышение резкости — это фильтр, который усиливает высокие частоты, а низкие частоты оставляет без изменений.
                0
                на самом деле это частный случай. есть ещё нелинейная фильтрация используемая для обработки изображений
                  0
                  на самом деле это частный случай. есть ещё нелинейная фильтрация используемая для обработки изображений
                +2
                Не могли бы вы более ясно продемонстрировать сходство между свёрткой по ссылке в Википедии (которая для функций — интеграл) и той, что применяется к изображениям? Скажем, такой вопрос: где в Википедийных свёртках ядро?
                  +1
                  Ядро — одна из функций в свертках на википедии. Она необязательно должна быть дискретной как в примере с обработкой изображений.
                    +3
                    Двухуровневый цикл — это фактически и есть интеграл, который считается для дискретных переменных x и y. В дискретном пространстве интеграл становится суммой.
                    +17
                    А Вы специально для сверки в .NET использовали изображения ПИНГВИНОВ?
                      +3
                      Сначала я взял изображение из стандартных картинок в винде и лишь потом понял весь глубинный смысл =)
                        +5
                        судя по всему, у автора есть подсознательное желание переписать программу на Mono )))
                        –2
                        Где кнопочка сохранить? :)
                          +5
                          К вопросу о блоге — я подумал, что это первый из нового ряда топиков блога «Алгоритмы».
                            +1
                            Такой фильтр также есть в фотошопе Filter>Other>Custom…
                              0
                              Что-то он немного не так работает: попробовал примеры из статьи.
                                0
                                видимо дело в том по какому значению нормируются значения
                              –3
                              У кого-нибудь есть реализация консольного варианта для увеличения резкости? Или php?
                              0
                              В институте свертку называли аппертурой, blur низкочастотным фильтром, а повышение резкости высокочастотной фильтрацией :)
                                0
                                а ядро откликом :)
                                  0
                                  а у нас в универе свертку светкой называли )
                                +1
                                Я думаю, топику самое место в «Алгоритмах». Тем более там уже есть один по машинной графике и обработки изображений, опять-таки с исходником на шарпе. А вообще странно разделять алгоритмы по языку реализации ;)
                                  +1
                                  Еще одно такое же мнение… и топик отправляется в Алгоритмы :)
                                0
                                > if (kSum <= 0) kSum = 1;

                                в исходнике есть, в описании — нет. У многих по описанию и примерам возникнут вопросы о делении на 0…
                                  –10
                                  Хватит ныть по поводу кармы!
                                    +1
                                    Статья хорошая. Но надо бы более формально раскрыть связть свертки из статьи со сверткой как понятия мат. анализа. А так же показать связь между сверкой и фурье-разложением изображения — это сразу подсказывает как выбирать хорошие ядра для задач.
                                      0
                                      Только сегодня защитил диплом связанный с обработкой изображений. Тема топика прям родная xD
                                        +1
                                        Поздравляю, коллега! =)
                                        У меня грядет защита диплома по facial recognition & identification в сентябре
                                          +1
                                          Спасибо) Удачи на защите!
                                          0
                                          Там было описано лишь как пользоваться. Без описания алгоритма.
                                          0
                                          у меня есть реализация линейных методов фильтрации (– низькочастотна фільтрація;
                                          – полосова фільтрація;– режекторна фільтрація) реализовано на SciLab(типа Matlab). Кому интересно могу навоять статью.
                                            0
                                            Есть такая книжка «Д. Форсайт, Ж. Понс. Компьютерное зрение. Современный подход». Отличное пособие по практически всем областям, связанным с компьютерным представлением изображений. Очень рекомендую всем, кто хочет познакомиться с программной обработкой картинок и видеопотока поближе.
                                              0
                                              Я бы в свою очередь посоветовал
                                              Гонсалес Р., Вудс Р. Цифровая обработка изображений
                                              +3
                                              поиграться с фильтром в браузере можно тут
                                              sakri.net/technology/flash/flex/convolution_filter/ConvolutionFilterExplorer.html
                                                0
                                                В последние годы математики полюбили показывать возможности вейвлетов (всплесков) на примерах, аналогичных вашим.
                                                  0
                                                  о ужОс, кто ж так пишет(особенно алгориты которые не должны работать долго), куча повторяющихся вычислений, создание переменных в циклах…

                                                  не подавай плохой пример, а то ж на копипастят…
                                                    +1
                                                    Создание переменных в цикле не понижает производительности, можете проверить, а читаемость повышает.
                                                    А то что я не использовал предвычисленные таблицы — это умышленно, иначе алгоритм стал бы нечитаем для непосвященных.
                                                      0
                                                      так чтоб в разы не понижает, но когда работаешь с графикой миллисекунды важны!

                                                      что сложного в том чтобы понять такую вещь как
                                                      a = 3 * (width * y + x);
                                                      и последующее использование

                                                      >это умышленно, иначе алгоритм стал бы нечитаем для непосвященных

                                                      приводишь довод достойный первоклассника.

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

                                                      если приводишь алгоритм, сделай его хорошо, потому что многие просто скопируют без оптимизации!

                                                      ЗЫ. и в шарпе надо это делать в unsafe. (:
                                                        +2
                                                        да алгоритм как раз привели как положено.
                                                        А реализация/оптимизация алгоритма — это уже отдельная статья.
                                                        По-моему должно быть очевидно, что реализация алгоритма в лоб (как в данном примере) далеко не самая эффективная.
                                                          0
                                                          >А реализация/оптимизация алгоритма — это уже отдельная статья.

                                                          если реализация отдельная статья, зачем код?

                                                          > что реализация алгоритма в лоб (как в данном примере) далеко не самая эффективная

                                                          зачем нужна неэффективная реализация алгоритма?! (в стопяцотпервый раз — на плодят же дофига, не обязательно этот, но наплодят)
                                                          +3
                                                          Алгоритм нормально приведён! Пример нормальный!!!
                                                          Кто просто копипастит, тот и будет пкопипастить! Он не будет вникать в оптимизацию, поэтому оно того не стоит. А чтобы объяснить само действие алгоритма самое то!
                                                          А вот те, кому правда интересно, те алгоритм поймут и уже перепишут как им надо! Так что не в пирожках мясо!
                                                            0
                                                            >Кто просто копипастит, тот и будет пкопипастить! Он не будет вникать в оптимизацию, поэтому оно того не
                                                            >стоит. А чтобы объяснить само действие алгоритма самое то!

                                                            дык и будут в том то и дело, не лучше ли чтоб копипастили что то хорошее?!

                                                            > Так что не в пирожках мясо!

                                                            а жаль, щас бы пирожок… (:
                                                              0
                                                              соглашусь с вами только в том, что данный алгоритм можно было бы привести в некоем псевокоде. Но автор выбрал конкретный язык, чтобы не было недопонимания.
                                                              Копипастить будут максимум школьники-студенты для курсовых — пусть делают это наздоровье, оценку им поставят, т.к. специалистами они видимо стать при этом не хотят.
                                                      0
                                                      афтор, покури на досуге более православный вариант: FFT( FFT(изображение) * FFT(раздутая маска_оператор_ядро)) = профит в скорости.

                                                      FFT — естественно быстрое преобразование фурье
                                                        0
                                                        Писал курсовую по этой тема на C++ с интерфейсом на Qt4…
                                                          +2
                                                          Конечно да. Решил таки написать на питончике этот скрипт просто по описанному вами алгоритму — не получилось до конца, пришлось таки текст программы читать. Чего именно не хватало:

                                                          1. Что делать на границе? Первый же пиксель (0, 0) и я в ступоре. Оказалось что пиксели изображения недостающие надо пропускать (это еще очевидно), но неочевидным оказалось то, что сумму сетки тоже надо брать только ту, что на пиксели наложена (тоесть не учитывать некоторое на границе как и в случае с изображением).
                                                          2. Деление на ноль (а как по коду оказалось — если меньше нуля то тоже надо единицу ставить)
                                                          if (kSum <= 0) kSum = 1;

                                                          А в целом — спасибо огромное, куча позитива и все такое). Вот, собственно, программка: dpaste.com/hold/59566/ (привентил прогресс-бар на всякий случай, брать его здесь code.google.com/p/python-progressbar/)
                                                            +1
                                                            Рад что вам понравилось =)

                                                            Насчет граничных случаев в большинстве описаний алгоритма ничего не сказано. Каждый реализует это так, как считает нужным. В инете находил достаточно много решений, таких как «заворачивание» изображений (если координата пикселя отрицательная, то берется пиксель с другого края картинки), игнорирование несуществующих пикселей с делением на полную сумму ядра и прочие методы. Однако приведенный мной метод показался мне наиболее логичным и дающим самый приличный результат на краях.
                                                            Насчет деления на ноль ситуация такая же. Я посчитал что в случае отрицательной или нулевой суммы делить на 1 — самое безобидное.
                                                              0
                                                              в коде эти пиксели пропускаются, тоесть центр рамки начинает с координат 1,1 и доходит до предпоследнего.

                                                              if ((pixelPosX < 0) || (pixelPosX >= width) || (pixelPosY < 0) || (pixelPosY >= height)) continue;
                                                                +1
                                                                не, центр рамки начинает с координаты 0,0. Вы не правильно поняли), pixelPosX и pixelPosY- это не центр рамки а координата текущего пикселя изображения относительно наложенной рамки (тоесть пропускаются, к примеру, пять пикселей (левые и верхние — 0,0, 0,1, 0,2, 1,0, 2,0) рамки при наложении к пикселю 0,0, так как они указывают на отрицательные координаты).
                                                                0
                                                                позор позор s/привентил/привинтил/
                                                                0
                                                                Лет десять назад я писал дипломную программу по этой теме, ничего не зная о фильтрах.
                                                                У меня была только методичка и желание заработать :)
                                                                • UFO just landed and posted this here

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