Courses/CS 461/Winter 2006/Rick Strom/Week Eight
From CSWiki
[edit] GA to solve changing problems
One of my first thoughts after the GA lecture is that GA is well suited for solving problems where the problem itself is changing as it is being solved. For example, automatic tracking of identifiable and distinguishable objects in real-time. As the object being located in an image space moves, a genetic algorithm would provide solutions that adapt as the problem changes (i.e. as the object relocates). Solving this problem requires a fast method of zeroing in on a solution (in particular, a fast means of determining the fitness of a solution), and an algorithm that adapts to the changing world.
[edit] Pattern Matching with GA
This is the start of a pattern matching application in C++ (this may or may not end up being the project I commit to, but I did spend all week on it):
[http://img2a.glowfoto.com/images/2006/03/03-2159414737T.jpg]
In the above screenshot, the large image is the "haystack" image, and the top right image is the "needle" image. The program attempts to locate the best match for the needle in the haystack. The current best match is displayed in the lower right corner. The current population of solutions is displayed as green boxes overlaying the haystack, with the current best solution displayed in red.
Solutions are defined by two points, (x1,y1) and (x2,y2) which represent the upper left and lower right of a subregion of the haystack.
Fitness of solutions is determined by scanning the subregion of the haystack defined by the solution rectangle and comparing that region, pixel by pixel, to the needle. Each solution is stretched to the same dimensions of the needle before comparing pixels.
New generations of solutions are created by combining coordinates of the two parents. For example, for parents A and B with regions:
A = {(Ax1, Ay1), (Ax2, Ay2)}
B = {(Bx1, By1), (Bx2, By2)}
One child might be:
C = {(Ax1, Ay1), (Bx2, By2)}
The most-fit solution is the one with the lowest score, where the score is determined by summing the differences in red, green and blue values for each pixel.
This, according to the research I've done, is best done using wavelets. One particular method involves a Haar wavelet transformation of the images, and a comparison of the largest 20% of coefficients in each wavelet. I have not reached this point yet.
