Part 2
Some time ago, i was experimenting with Image Processing. So I created a small library of image processing functions / filters, which i decided tom make publicly available. Most of the filters i have written, are convolution ones like Gaussian Smoothing, Sharpen, Motion Blur etc… The implementation of this library is by no means the most efficient or fast and the primary purpose of this post is to help people understand what happens behind the scenes when they use a Blurring filter in Photoshop for example. Most probably this will be a series of 2 or 3 posts during the next couple of weeks.
Convolution
OK, lets get started. The most important part of these filters is the convolution operation. I will not get into much mathematical details about convolution, just what is important to show you how it works. To perform convolution on a pixel of the image we require a convolution kernel (i’ll use the term Filter Matrix for the rest of the post), which typically is a 3x3, 5x5 or 7x7 matrix. Convolution is basically a weighted summation. The value of the output pixel is determined by the values of that and some surrounding pixels. Each of these pixels contribute to the output value with a weight, specified in the Filter Matrix. You will understand it better if you take a look at the example in the image below.
For the rest of the post, i’ll be writing points as [y,x] instead of [x,y] just because that’s the way the matrices are declared/used in the library. So, if we apply the convolution operation on a pixel (y,x) of the input image I, the resulting pixel in the output image O will be:
where L is the Filter Matrix size,
and F is the Filter Matrix. The filter F should be normalized (sum of all weights equals 1), otherwise we need to divide O[y,x] with a devisor D so that the pixels are in the 0-255 zone. D is usually the sum of all coefficients in the Filter Matrix. Some filters, like edge-detections ones, have a coefficients’ sum of 0. In those cases we need to avoid division by D = 0. Finally, sometimes we also add a constant value (Offset) to the result O[y,x] so that the output pixel is in [0, 255] range. We will see a couple of those filters in the next post.
So, in general, we can say that the formula for computing a pixel at (y,x) is:
As you see, the value of the output pixel at (y,x) is not only affected by the corresponding pixel in the original image, but from the ones near it as well. Each of the pixels has a weight that is specified in F. If we apply this process to every pixel, we get the filtered image. So, the only thing that changes for various filters is the Filter Matrix.
Here is an example of an image, while we apply a Sharpening filter to pixel at (4,2). The pixel has a value of 53 and you can see the values of the surrounding pixels. The value of output pixel O[4,2], according to the formula above, is:
Someone might ask, what values we use when computing the convolution for pixels on the edges. If we tried to apply the above filter for pixel at (1,0), we would try to get the value I[-1,0], I[-1,1], I[-1,2] that would lead to an error in our potential program. There are a few solutions used for pixels on edges:
- Use the same value as the first neighbor pixel in image.
- Use a value of 0 (black).
- Don’t apply the convolution to pixels on the edges. If the Filter Matrix has a width/height of 3 for example, you can apply the filter in image starting from [1,1] – That’s what i’ve implemented in this library.
First lets declare the Filter Matrix class (named ConvMatrix) that is used by the function that applies the filter:
The Offset, is the constant value that sometimes needs to be added as we discussed earlier. Factor is the normalizing factor (the divisor) and as you see it’s by default computed to the sum of the Filter Matrix coefficients.
We have a default size of 5x5 for the matrix, without any Offset and Factor = 1. Filter matrices of size 1x1, 3x3, 5x5 and 7x7 are allowed in the implementation but that can easily change. The default matrix, leaves the image unchanged. So, lets see a first implementation of the function that performs convolution to every pixel in the image. It uses the functions Bitmap.GetPixel() and Bitmap.SetPixel() of the System.Drawing namespace.
As you can see, we apply the filter to the pixels in the range ([s,s], [Height-s, Width-s]) to avoid the problem I described earlier. Notice that we use the convolution operation 3 times on each pixel, one for each color channel (R, G, B). On the last part, before setting the new value of the pixel, we divide with the normalizing factor (Factor), add the constant value (Offset) and filter out any values outside the (0, 255) range.
You now have almost all the code you need to test a filter on an image. We just need to declare a function for a filter (let’s use the sharpening filter of the example):
Here are a couple of sample images where you can see the results of filtering:
Sharpening Filter
Emboss Filter
The SafeImageConvolution() function works fine but it’s really slow because of the calls to GetPixel() and SetPixel(). On the next post, we will see a much faster implementation of the Convolution function, using pointers to iterate through the image. Also, i’ll post the Filter Matrices for the rest of the filters (smooth, emboss, edge-detection, motion blur, etc) and upload the complete source code and a sample WinForms project that uses the library. In the meantime you can see this library in action here: http://mzervos.xelixis.net/ImageFilters/