The first step in my AI journey!

One of the first tasks I was given was to work on a circle detection method thought up by one of my supervisors Alex. Circle detection because your iris is a circle, so if we can detect partially occluded (covered) circles, then we have are first step to detecting an eye.

I first had to decipher a document he had written in 2002. He didn’t quite remember what was in it, and it had a few errors, so it was quite a challenge, but I eventually managed it. The basic idea was to find the gradient field (pointing from light to dark), and then at each pixel I would follow the gradient vector at that point, and draw a little grey leaf shape. For general background, the leaves are just scattered around, but in a circle we have loads of leaves all in the same place, which add up to a very dark area. So the circles end up very dark, whilst the rest of the image is somewhat grey. This is achieved with lots of complex number tricks, and done so as to be somewhat scalable (a simple relationship between different sizes of circle/image).

This is all brilliant! But it requires us to loop through every pixel, and for each pixel loop through every other pixel. That is potentially a LOT of loops!! So , with careful choice of the functions that make the leaf shapes we can transform this sum of sums into a sum of just a few convolutions. So what? We can use Fourier Fast Transforms (FFT), coupled with the convolution theorem (http://en.wikipedia.org/wiki/Convolution_theorem) allows us to compute these very efficiently! (by turning the convolution into a simple multiplication). So for a picture of 500 x 500 pixels, we have gone from 500 x 500 x 500 x 500 loops to around 4 loops of a convolution. Brilliant!

I then had to implement the method in c++, as I don’t yet have matlab. I also didn’t have any FFT software, so I had to do the loops the long way. I failed miserably, and the resulting program takes a LONG time to run, and the output is not right either.

Read the rest of this entry »