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!

Advertisements

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.

A* algorithm in c++!

This is not an algorithm to get you an A* in your GCSE’s. Don’t be so silly. A* (Astar) is a path finding algorithm used to find…. paths.
It is very similar to Dijkstra’s algorithm, if you know what that is. I found a great explanation here: http://www.policyalmanac.org/games/aStarTutorial.htm , so I’m not just going to recreate that in a lesser form without diagrams. If you want to understand it, go check that out.

The following source code  makes no attempt at clarity or efficiency. Nor does it claim to make good use of spelling. It does, however, work. It also has no formatting thanks to wordpress. But perhaps if you cut and paste it into a c++ program, it might get sorted for you. Who knows.

It first randomly generates a small world, which is filled with walls (0’s) and empty space ( ). This is seeded the same everytime, but could be changed with a call to time(0) (#include<time.h> I *think*). The A* algorithm is the called to find a route from the top left to the bottom right.

Next, the end of the A* is printed. Start in the bottom right, and just go in the direction indicated (u for up, r for right, l for left, d for down). Keep doing this until you reach the starting position. Or not if it has failed, which is possible!

Lastly I get the computer to compute the route, and print it out with little @ symbols. Lovely.

SOURCE CODE:

Astar– This is a word document!

FIRST POST!!!!1111

Claiming the first post like a youtube noob.