Week 9 - Convolution Matrixes

This entry will be looking at how to manipulate images with generic filters, using what is known as a convolution matrix.

---

Convolution Matrix

A convolution matrix is a grid of number values. When applying a convolution matrix to a given pixel, the result will depend on the values in the matrix. This is in essence all a matrix looks like:

The center is a different color in this as it's the center of the matrix, which concerns itself with the current pixel the matrix is being applied to. In this case the matrix loosely means "take 100% of the value of the center pixel and apply it to the current pixel", which means this matrix would do absolutely nothing if applied to an image.

Consider a bitmap as a series of values on a grid, with each value representing a pixel. For the purposes of demonstrating what a convolution matrix does I'll use a 5x5 grid of pixels which will be grayscale for simplicity.

For the purposes of this entry, 10 will be the maximum value (white) and 0 the minimum (black). This is for simplicity, as in a real bitmap considerably more values are used represent grayscale images (255 or more).

---

Blurring

Consider the following example bitmap:

Now, let's consider we're to apply the following matrix to it:

This matrix translates roughly to "take the values of the center pixel and all pixels in the immediate vicinity and apply it to the center pixel. So let's apply it to the above bitmap, starting with the top-left pixel and see what happens.

Now this one only has 3 pixels to work with, so the entire matrix can't be applied to it. However we can still take the below, below right and right pixels. 

center = 0

below = 10

below_right = 0

right = 10

new_pixel = center + below + below_right + right

new_pixel = 0 + 10 + 0 + 10

new_pixel = 20

Well that isn't right. The limit is 10 so the pixel would just cap out at 10, or white in this case. Apply this to every pixel in the image and the result would be the same, they'd all turn white. There is an extra step we have to take here and that is to divide by the number of entries in the sum, or normalise it. 

new_pixel = (center + below + below_right + right) / 4

new_pixel = 20 / 4

new_pixel = 5

 It turned grey! This is because the white pixels essentially bled into it as their values influenced the center pixel when the matrix was applied to it. If we then apply it to the next pixel...

new_pixel = (center + left + below_left + below + below_right + right) / 6

new_pixel = (10 + 5 + 10 + 0 + 10 + 10) / 6

new_pixel = (45) / 6

new_pixel =  7.5

The black pixel has bled a little into the white in return! Of course, this is a bitmap that can only be made up of values between 1-10 as solid numbers only. As a result in this instance we would round that up to 8. Continuing on to apply this to the rest of the image.

The above was manually worked out and it doesn't look entirely right to me. I'm going to chalk that up to human error either in the calculation of any given pixel (which would screw up the rest) or possibly a rounding error on my part. Regardless, I can check by just applying the above matrix to an actual 5x5 bitmap with nothing but a diagonal black line using GIMP. This gives me the following result, naturally scaled up for visibility:

Much tidier than my attempt. Although like mine, the corner pixels ended up the darkest. The rough result is however the same, the values of the pixels have essentially bled into their neighbouring pixels, resulting in a blurring effect.

Let's apply this to an actual image. For this we'll use the example image given for the lab.

Once we apply the matrix used in this section to it:

Sure enough, the image is blurred. Re-applying this filter multiple times would increase the blurring effect.

---

Convolution Matrix Filter in GIMP

The convolution matrix can be found in the filter menu under "Generic Filters". The path to it is pictured in the below screenshot.

Clicking on that will take you to the following screen. 

Note that I've highlighted the Normalise checkbox in green. There is a reason for this, you need to make sure that it's checked. If you don't, observe the result of the earlier blur matrix.

This proves what I said earlier, that failing to normalise will cause the pixels to become white.

---

Edge Detect

So we blurred the bitmap earlier, let's try to get that edge back. This can be sort of achieved with the following matrix:

Here we have negative values, which means we take the negative of those pixels (if the value were 255 it would now be -255 in the sum). Applying this to our earlier result in the actual bitmap gives us the following result:

The edge is a little better defined. Repeating the filter again gives the following result:

This is as close to the original edge as this filter will give us. This is thicker than the original edge, but it is inarguably an edge. This filter was pretty well designed to find a diagonal edge like this however. If we use a slightly different edge-detecting matrix:

Like above, this was repeated twice for consistency. Interestingly in this case it's actually flipped the line. Finally, let's use a convolution matrix better suited to straight lines and see what it does.

Nothing like the original edge. 

The conclusion to take away from this section would appear to be that you will need to figure out which edge-detecting matrix will produce the best results for your image. 

---

Conclusion

Digital images can be manipulated in a number of ways through mathematics. Blurring, sharpening, edge detecting and embossing can be achieved by applying a convolution matrix to each pixel.

Image processing programming:

http://archive.gamedev.net/archive/reference/programming/features/imageproc/page2.html

Gimp Manual on the convolution matrix:

http://gimp.open-source-solution.org/manual/plug-in-convmatrix.html