Pull to refresh

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

Algorithms *
Автором данного топика является хабраюзер 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.


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

Вот и все. Надеюсь что данный материал был полезен и преподнес вам что-то новое. Если данная тема вас заинтересовала, то могу написать еще про базовые методы формирования ядер свертки, а так же про оптимизации данного алгоритма. Спасибо за внимание!
Tags:
Hubs:
Total votes 93: ↑89 and ↓4 +85
Views 75K
Comments Comments 63