Joe's blog about AI things!

## Tag: Circle

### A New and Exciting Method. The Isophote.

Some few of you may recall one of my previous posts (Success! Joe’s new method.) I outlined and implemented a technique to detect circles. My idea was to consider pairs of adjacent pixels, and calculate where their gradients intersected, thus giving an approximate centre for any dark circles they lay on. Well, I was reading a paper recently, and it outlined a very similar method, but instead of considering two pixels, you considered only one (something that I had assumed was possible, but had no idea how to do).

First the paper introduced the concept of an isophote. This is simply an area of constant darkness/intensity. So if our image is described by a function f(x,y), then we have an isophote at (x,y) where f(x,y) = f0 (f0 is constant). This is essentially describing contours. It then goes on to use the curvature of each pixel, assuming it is on an isophote, to estimate the radius of the circle it is on. Curvature is the second derivative of y with respect to x, and a formula for this can be derived from the definition of an isophote using total derivatives (as f = a constant, we have y(x), so we must use the total derivative, paying attention to the chain rule). The radius of the circle that it is on is given by 1/curvature, which is very convenient. To convince yourself of this, try plugging the values x = 0, y = r into the definition of curvature, and you should get 1/r. Easy. So now we have the distance to the centre. The direction to the centre is given by the gradient at that point. All it takes is a little trigonometry, and we have an estimate!

So here is a pretty picture of it at work:

### The slowness of a Joelet.

Remember before when I commented on how slow it would be to draw a large “bump” onto an image at every estimate? Well I did even if you don’t. It seems that Gaussian blur (again discussed in an earlier post) offers a perfect solution. If I draw every estimate on as a single dot, and then blur nearby dots into eachother, then Boom! Estimates are grouped in a fast and efficient manner.

I have also altered the shape of the Gaussian function to more of an oval shape to accommodate eye shapes. This could be good, this could be bad. I have not tested it yet. The following is using an oval shape. I have also noticed that the picture gets darker with more spread out Gaussian functions…. I think I need to moderate the height so as to have a constant area under the function. Integration awaits me!

Original image:

And now after processing, the left is using the original “Joelet” method, the right is using Gaussian blur:

A little different, but I think the average number of eyes detected would be the same.

Great! This would make detecting bigger eyes much more efficient. Although I am still relying on the user inputting an approximate eye size, when I find a fairly optimum Gaussian function shape I think I could probably do away with that.

### Alex’s method 3, and some tasty paper.

Just thought I would share a little failure with regard to Alex’s method. I just tried to implement it using FFT to solve some convolutions, which is a LOT faster – even without me trying to streamline it. It does, however, result in every pixel having a negative colour. Which is bad. Very bad.

The worst part is that I’ve seen *I MY CHAIR JUST DISINTEGRATED UNDERNEATH ME!!* Alex’s method implemented in matlab code, but I such a matlab noob, I have a lot of trouble following it. In the near future I might just sit down and try extremely hard to make it work, using the matlab code and everything.

In other news, I have been trying to do a literature review on circle finding techniques (my first ever lit review!). It seems to me there are a few main techniques.

1. Hough Transform. This is originally used for detecting straight lines, but has been modified to detect any number of shapes, including circles.
2. Wavelets. Wavelets are the basis for how jpegs works, and are very powerful tools for looking at a picture in different resolutions. In particular, there have been modifications to “circlets” which can be used to track down circles.
3. Other, misc. Lots of them similar to mine, in which some estimate is made of the centre of each pixel or group of pixels.

I also read n interesting paper about the relationship between head pose and eye gaze, and in particular, how to tell if someone is surprised by something they looked at, or whether they always intended to look at it. Essentially it showed that if a person looks with their eyes, and then turns their head, they are startled. But if they move their head a bit before their eyes, then they intended to look over there.

Fascinating stuff.

### Gaussian Blur!

Hi everyone!

Previously (see Success!) I implemented a method of my own design, but noted a limitation: I needed to either input the approximate eye radius, or have massive computing power to deal with very large accidental lengths. Inspired by a paper that my supervisor sent to me, in which they use a Gaussian blur effect to turn lots of estimates of a point into one estimate. In fact, it is not truly  “inspired” by the paper, but more taken from the paper. Exactly.

So Gaussian blur (as far as I can make out) works by convolving the Gaussian function (essentially a single hump) with the image. This smooths out the image.

I have attempted to apply this to my method. But first I need a FFT library. The following are my installation woes:

OpenCV (http://opencv.willowgarage.com/wiki/) and FFTW (http://www.fftw.org/) are C++ libraries. OpenCV is for image processing, and FFTW is used to perform Fourier Fast Transforms. They would be great, and really complement my project. However it turns out that its somewhat impossible to install and use them with any windows program. I have literally wasted days of my life trying to get them to work with either Microsoft Visual C++ 2010 or Netbeans. In the end I gave up.

In the end I gave up.

If anyone knows of any good (simple!) tutorials, could they possibly let me know? I think I will have to build OpenCV from the source code, but I really don’t know how I would go about that. FFTW requires me to use some lib.exe program from Visual C++ to add the libraries. But it seems to crash every time I run it.

In the mean time I am using a C program for FFT I found at http://www.tech.dmu.ac.uk/~eg/tensiometer/fft/. It appears to work… However their are some interesting results when I use it to perform a Guassian Blur.

### Revenge of Alex’s Method

Previously I described an attempted to implement Alex’s method. I tried again, to even worse effect. I thought I would include a failure picture to help everyone else feel good about themselves…

As you can see… not quite what I had in mind. Although looking closely at this, it seems to be outlining white lines quite a lot. I should investigate that….

Nope! switching the black to white makes no noticeable difference. There must be a (quite large) bug somewhere in the program. Perhaps one day I will find it. I can but hope.

### Success! Joe’s new method.

Success! Although not in implementing Alex’s circle/eye detection method (see  last post). I grew tired and frustrated by silly C++, so I decided to make my own, much simpler method that (hopefully) would not require convolutions and FFT’s to fun at a fair speed. It was inspired by the idea of circular wavelets, or circlets, however it is actually nothing to do with them mathematically.

Very simply each pixel considers its own gradient the gradient of the 4 pixels next to it one at a time. The intersection is found between the line made by the gradient of the current pixel, and the line made by the gradient of each adjacent pixel. So we have 4 intersection points. If the intersection points lie on the picture, then we draw a little pyramid of darkness (lets call them Joelets, because its cool!). These pyramids all add up to form some interesting blurry shapes.

How does this detect circles? Well if we are on the edge of a circle, then each gradient will tend to point towards the centre of a circle, so the intersection points will be around the centre. If we are not on the edge of a circle, then the intersection points will just be scattered randomly. Hopefully the little pyramids should all add up near the eyes and cause a massive dark bump. Boom. Eyes detected.

One more issue to consider. How big should the Joelets be? And by big I mean radius wise, as heights are all relative. If they are too big, then everything will just blur together. But if we make them too small, then all we will have is a load of scattered intersection points. I propose that it should be approximately the radius of the eye. I haven’t done any maths to check this, I am only guessing, but it seems to work! That is all well and good, but it relies on us know the eye radius. what if we don’t?? Well we could take the radius of the Joelet to be the distance from the parent pixel to the intersection point. That would be approximately the radius of the circle. It would be brilliant if it was EXTREMELY slow, as some intersection points are on the other side of the image. For now I have just guessed the eye radius, but a task for the future is finding a way to use some kind of variable eye radius. Maybe with a convolution?

Here are my results!

### First attempt at Alex’s method! 10th June 2012 ish.

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.