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.
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
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
tgtRGB.Pixel(x,y) = rgb(v,v,v)
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)
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)
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:
Click here to if you like my work