One of the filters that is mostly used in computer vision is an edge detector. I could write here an edge detection function but I thought it would be more fun if we could build our own detectors.

How does an edge detector kernel work? A kernel is a small filter that convolves with a image in a horizontal and vertical direction. It is a relatively inexpensive computation so it can find edges really fast.

Wikipedia states:

In simple terms, the operator calculates the gradient of the image intensity at each point, giving the direction of the largest possible increase from light to dark and the rate of change in that direction. The result therefore shows how “abruptly” or “smoothly” the image changes at that point, and therefore how likely it is that that part of the image represents an edge, as well as how that edge is likely to be oriented. In practice, the magnitude (likelihood of an edge) calculation is more reliable and easier to interpret than the direction calculation.

Couldn’t have said it any better 🙂

Let’s do a simple one manually. This will show you how easy it is. The example is taken from my online A.I. Class I’m taking at Stanford.

There are several out there like the Sobel and Prewitt kernels that produce excellent results.

Here is for example the Sobel Operator:

And here the Prewitt ones:

Wouldn’t it be fun to try to find other such kernels?

In this tutorial we’re going to build a program where we can build our own edge detection kernels!

Let’s get started.

First we want to convert our picture to a 2 dimensional table of gray pixels. We’ve seen some good grayscale functions before, but for this tutorial I’m going to do a very fast but dirty one. I’m going to take the green value of a pixel and say this is the gray value. In a real application you should use proper grayscaling.

So as parameters we’ve got our picture, our XKernel an YKernel table with our masks in en just to make it easy for the rest of the algorithm we also give it the width and height of the kernels.

So in short we’ll convert our picture to a tabel, run our sweep over it and then convert the table back to a picture.

Function DoConvultion2D2Kernels(srcPic as picture, xkernel(,) as double ,ykernel(,) as double, kernelwidth as integer, kernelHeight as integer ) As Picture dim SrcRGB as RGBSurface dim tgtRGB as RGBSurface dim tgtPic as Picture tgtPic = NewPicture(SrcPic.Width, SrcPic.Height, 32) SrcRGB = SrcPic.RGBSurface tgtRGB = tgtPic.RGBSurface dim x,y as integer dim SrcTab(-1,-1) as Double dim tgtTab(-1,-1) as Double redim SrcTab(SrcPic.Width - 1, SrcPic.Height - 1) for x = 0 to SrcPic.Width - 1 for y = 0 to SrcPic.Height - 1 SrcTab(x,y) = SrcRGB.Pixel(x,y).Green next next tgtTab = convolution2D2Kernels(SrcTab, SrcPic.Width - 1, SrcPic.Height - 1, xkernel, ykernel, kernelwidth, kernelHeight) dim v as integer for x = 0 to SrcPic.Width - kernelwidth for y = 0 to SrcPic.Height - kernelHeight v = tgtTab(x,y) if v > 255 then tgtRGB.Pixel(x,y) = &cFFFFFF elseif v < 0 then tgtRGB.Pixel(x,y) = &c000000 else tgtRGB.Pixel(x,y) = rgb(v,v,v) end if next next Return tgtPic End Function

For every pixel in our picture we want to sweep our kernel over it. We’ll have an X and an Y kernel so we have to do it twice. Then we have to convert them both to one value and this can be simply done by taken the square root of the sum of X and Y squared: sqrt(x²+y²)

Private Function convolution2D2Kernels(input(,) as double, width as integer, height as integer, xKernel(,) as double, yKernel(,) as double, kernelWidth as integer, kernelHeight as integer ) As double(,) dim smallWidth as integer = width - kernelWidth + 1 dim smallHeight as integer = height - kernelHeight + 1 dim output(-1,-1) as Double redim output(smallWidth, smallHeight) dim x,y as Double for i as integer = 0 to smallWidth - 1 for j as Integer = 0 to smallHeight - 1 x = singlePixelConvolution(input, i, j, xKernel, kernelWidth, kernelHeight) y = singlePixelConvolution(input, i, j, yKernel, kernelWidth, kernelHeight) output(i,j) = sqrt(x*x + y*y) next next Return output End Function

Our final part is the function that can do a sweep of our kernel over 1 pixel in the picture.

Private Function singlePixelConvolution(input(,) as double, x as integer, y as integer, Kernel(,) as double, kernelWidth as integer, kernelHeight as integer) As double dim output as Double ' for every pixel in our kernel for i as integer = 0 to kernelWidth - 1 for every line in our kernel for j as integer = 0 to kernelHeight - 1 output = output + input(x+j, y+i) * Kernel(j,i) next next Return output End Function

Done! the rest of the project is setting up the interface, but this you can find in the project you can download.

Here are some other examples of the program with other kernels:

Now it is time for you to search for some new kernels to find edges. If you found a great one, please send me a message and I’ll post your result on the blog. And maybe one day we all use kernels that carry your name!

The project code:

http://www.gorgeousapps.com/Tut11.zip

Click here to if you like my work

December 15th, 2011 at 12:20

These are excellent tutorials – have you considered putting them together with others and making a Real Studio ebook out of them?

December 15th, 2011 at 23:51

Thank you. I’ve only started the blog a couple of months ago so I have not really thought about a book. But who knows 🙂