Image filtering by convolution

The author of this topic is Habrayuzer Popik, who himself can not post this topic for astral reasons.

Introduction

Probably, the majority of the HF community knows firsthand about image processing filters, such as blurring, sharpening, edge detection, embossing, and so on. Some worked more closely with them, some used them for granted. However, do they all know how exactly the image is filtered, and what is common between the listed filters? In this topic, I will try in general terms to describe the algorithm by which all this is done, as well as give its implementation.

A bit of theory.

So, the filters that have been listed, as well as many others, are based on convolution . What is convolution? A convolution is an operation that shows the “similarity” of one function to a reflected and shifted copy of another. The concept of convolution is generalized for functions defined on groups, as well as measures. A bit complicated definition, isn't it? Those who are interested in the mathematical theoretical part can look at the link to Wikipedia , and, perhaps, learn something useful for themselves.
')
I will try to give my definition-explanation of the convolution “on the fingers” only for the case of image processing, which may not be as clever and accurate as in the scientific literature, but it seems to me that allows us to understand the essence of this process.

So, convolution is the operation of calculating the new value of the selected pixel, taking into account the values ​​of the surrounding pixels. A matrix called convolution kernel is used to calculate the value. Usually, the convolution kernel is a square matrix n * n, where n is odd, but nothing prevents to make the matrix rectangular. During the computation of the new value of the selected pixel, the convolution kernel is “applied” by its center (the oddness of the matrix size is important here) to this pixel. The surrounding pixels are also covered by the core. Next, the sum is calculated, where the items are the product of the pixel values ​​and the cell values ​​of the core that covered the pixel. The sum is divided by the sum of all elements of the convolution kernel. The resulting value is just the new value of the selected pixel. If we apply convolution to each pixel of the image, the result will be some effect depending on the selected convolution kernel.

This concludes the theory and proceeds to the examples and the implementation of this algorithm. Is the brain still alive? :)

A few examples.

The implementation of the algorithm.

I will give only the main part of the C # code, the complete source code for the convolution and a small program for visual testing can be downloaded from the link at the end of the article. I will make a reservation in advance that the code was not written as something very optimal, and there is still a field for optimizations. For example, you can increase the speed using pre-calculated pixel values, but this is not the point.

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 .

Download program sample

That's all. I hope that this material was useful and gave you something new. If you are interested in this topic, I can write more about the basic methods of forming convolution kernels, as well as about optimizing this algorithm. Thanks for attention!