Check out my
new book!
HTML5 Games book
Genetic algorithms, Mona Lisa and JavaScript + Canvas About a month ago, there was an interesting article about using genetic algorithms to "evolve" images. Roger Alsing had made a small program and put it to the test by letting it make a very good approximation of the Mona Lisa with 50 layered, semi-transparent polygons. I figured I'd try to do something similar with JavaScript and Canvas.

Genetic algorithms

So, the basic idea of genetic algorithms is that you have a population of individuals, each carrying a DNA string representing a possible solution to the problem (in this case, the polygonal likeness of Mona Lisa). The initial population is assigned random DNA and subsequent generations are then created by mixing the DNA of the fittest individuals of the current population. In order to ensure diversity in the population, there's a small chance of mutation where a DNA value is randomly changed. However, Roger Alsing's project actually uses a population of only one parent, making it more like a hill climbing algorithm where the current solution is altered slightly and if it's a better fit, the old one is discarded.

I tried to go for a more proper genetic algorithm approach with an adjustable population size, selection, DNA mixing and everything. Now, Roger used just short of a million generations to get to his result (which was very accurate). It took 3 hours for his (compiled) program to generate the resulting image, and of course, even if JS engines are getting faster, it's going to take a bit more time than that to get as nice a result as his using JavaScript. Still, even after a few hundred generations/a few minutes in my demo, with the default parameters, you should see the shape of Mona Lisa starting to take form. I'm unfortunately not very patient, so I'm not sure if my experiment can even create as good an approximation, given the necessary time.

There are also a few other images you can play with. I've made the images pretty small (100x100) so that evolution would be as speedy as possible. The fitness function actually uses an even smaller (50%) version.

Options

Some of the parameters can be changed before starting the evolution. They are:
  • Number of polygons: The number of polygons used to in the image approximation.
  • Polygon complexity: The number of vertices in each polygon.
  • Difference squared: If checked, the squared differences of the RGB values are used when calculated fitness, otherwise simply the absolute difference.
  • Population size: The number of different candidates in each generation.
  • Succesful parents cutoff: The percentage of candidates selected for breeding the next generation, eg. 0.25 = the fittest 25% of the current population.
  • Mutation chance: The chance that a value will mutate when breeding new candidates, for example 0.02 = 2% chance of mutation.
  • Mutation amount: The amount the mutated value will be changed, for example 0.01 = 1% means a random change between -1% and 1%.
  • Uniform crossover: If checked, values are mixed at random one by one from each parent, otherwise a single random cut in the DNA string is made and one part from each parent is used.
  • Kill parents: If checked, the new generation will consist entirely of the children of the old generation. If not checked, the parents are left alive and will compete against their offspring.

If the parents are not carried over to the new generation, you will notice that the best fitness value in the new generation might actually be worse than the previous one. On the other hand, that could make it easier to avoid dead ends and premature converging towards local optima.

Note that changing the parameters won't have any effect until the evolution is restarted.

A few results

Here are a few quick runs, showing the results.


Mona Lisa after 25 minutes


Firefox logo after 25 minutes


Opera logo after 40 minutes


Mondrian after 14 minutes


Microbe after 9 minutes

Browsers

Since we're using canvas there's no support for IE. Furthermore, we're using the getImageData method, so only Firefox, Opera 9.5+ and WebKit nightlies will work. I suggest using either the latest Firefox beta/preview or a recent WebKit nightly as they seem to yield the best performance.

One last note

Only now, after I'd been playing around with this, have I noticed that someone had already done a JavaScript/canvas version of Alsing's program (where you can even use your own images) back when the original article was published, and for some reason I missed it. That version stays closer to what Alsing was doing, though, where mine differs in a lot of ways.

I think my approach gets to something resembling the target image faster, but it seems to have problems getting the details in place after that. I haven't had the patience to let it run for more than a couple of hours and it's quite possible that the other techniques are able to get a better approximation in the long run.

Play with it here

⇓ 30 comments Unknown

Very interesting.

It kinda failed for me, but anything with canvas seems to fail for me lately. Only horizontally did the image appear (which looks quite strange).

January 9, 2009 at 8:13 AM
Jacob Seidelin

Odd. I just got that exact problem as well, but only once. After a page reload it went away again.

January 9, 2009 at 8:22 AM
Jacob Seidelin

Ok, think I got it now.

January 9, 2009 at 8:41 AM
shevy

I <3 the pictures

More of them, please! How about a cartoon... or a sports pic... or a logo of another company, or pictures which are known to be very difficult for recognition

January 9, 2009 at 10:31 AM
Anonymous

Hey, great little web app. Thanks for making it available!

One suggestion: Add a field for "Total elapsed time for run", or some such to the output. That would make it easier to compare runs for different combinations of settings.

Wishlist:
- Upload your own (small!) images
- Save settings combinations to local machine (cookie?)

Good fun! Thanks again.

January 9, 2009 at 10:35 AM
Anonymous

Would Google's ExplorerCanvas not allow this to work on Internet Explorer?
( http://google-code-updates.blogspot.com/2006/03/new-project-explorercanvas.html )

January 9, 2009 at 11:23 AM
Jacob Seidelin

@Dan: I'm not sure what time you're looking for, iIt already prints the total time since the beginning of the evolution?
Maybe (just maybe) I'll take a look at the other things during the weekend.

@anon: No, unfortunately ExplorerCanvas doesn't have the image data access required for this to work.

January 9, 2009 at 12:20 PM
Evan Senter

That's really neat, I had a couple questions about your implementation:

1. How do you structure the chromosome to ensure that during crossover polygons from similar regions are combined in the offspring? Is the chromosome represented as a collection of vertices and the fill color, sorted in some fashion?

2. It looks like you're using some transparency, is the fitness function checking the color of the pixel considering all layered polygons at that point?

Anyways, really neat stuff, I think you've inspired me to do something similar in Ruby :)

January 9, 2009 at 12:38 PM
Jacob Seidelin

@Evan: Nothing fancy happens, really. It's a list of polygons, each consisting of 4 RGBA values and 2*n coordinate values, where n is the number of vertices. In the strictly GA part, it is simply a list of values from 0-1. It can't tell color components from x and y coordinates but is told to make cuts at intervals of 4+2*n. It either makes a single cut in each parents DNA and combines them to form a child - or each polygon is taken at random from one of the parents. Since the order of the polygons isn't touched, it eventually settles on what you see.

Yes, the polygons have transparency as well. When fitness is calculated, the image has been flattened and only the final pixel color is considered. The fitness function doesn't know what created the candidate image.

Glad you liked it :)

January 9, 2009 at 1:00 PM
Anonymous

Jacob, you always post interesting stuff but last experiments are CPU intensive and I think you should consider to learn some JavaScript "best performance practice" to try to perform as fast as possible and probably being able to do even more complicated computations :-)

What am I talking about?
- push does not make sense used once for each value, data.push(Math.random(), Math.random(), Math.random(), Math.random(), Math.random()); is 4 time faster than data.push(Math.random()); data.push(Math.random()) ... for 5 times

- if there is only one push, it is faster to use the length property instead of call the function: data[data.length] = value is 1.5 faster than data.push(value);

- if you are copying an array like object, you do not need a loop but a slice call:
testData = Array.prototype.slice.call(arrayLikeObject, 0); is N times faster than a for loop (Note: in your case I do not even know if you truly need to copy that array, I think you should simply assign it to the last canvas.getWhatever)

- to obtain best performances with common Math operations, it is usually better to cache those functions: var random = Math.random, max = Math.max, min = Math.min; and use them whenever you need as random() instead of Math.random() (the same for the slice prototype, cache it as var slice = Array.prototype.slice)

- paseInt(num, 10) is a function call while num >> .5 is a bitwise operation over an implicit cast, it performs better (limits are with big integers because of the right shift, it should not be a problem at all with your code)

- because of plus sign ambiguity (String concatenation) the parseFloat / parseInt operation is necessary only if you are using a + operation, every other mathematical operator will cast automatically the number: "123.5" / 2 === 61.75 so I suppose you can safely remove some explicit integer/float cast in your code

Sorry if this post is boring, I simply thought you would like to know more about this stuff since you used for example a do while with --i instead of a while(i--) that performs faster as well, is it any interesting?

Best Regards :-)

-

January 10, 2009 at 7:30 AM
Jacob Seidelin

Andrea, thanks for your comments.

The majority of the CPU time is spent drawing and accessing canvas data, so I didn't really bother looking at the other things. Your input is valued just the same, though. Thanks.

January 10, 2009 at 8:05 AM
Anonymous

Well, this is the typical case where 9 minutes instead of 10 could make the difference, specially for those people like us that do not deal that well with "patience" word, am I wrong? :D

Cheers ( ... and I gonna test with Opera now ... )

January 10, 2009 at 8:31 AM
Jacob Seidelin

You are of course quite right, every optimization helps :-) Although I'm pretty sure some of your suggestions (like changing the few parseInt's) won't matter much.

January 10, 2009 at 8:43 AM
Anonymous

193 ms against 76 ms in my old centrino. I know it could sound maniac but as you said every optimization is a must ;-)

for(var i = 0, t1 = new Date; i < 100000; i++)
parseInt(i);
t1 = new Date - t1;

for(var i = 0, t2 = new Date; i < 100000; i++)
i >> 0;
t2 = new Date - t2;

alert([t1, t2].join("\n"));

January 10, 2009 at 11:48 AM
Jacob Seidelin

No, I didn't mean that a >> wouldn't be faster than parseInt, just that it's only used a few times in the beginning (before the actual work starts) so the actual impact of changing it would be hard to notice.

January 10, 2009 at 12:00 PM
Anonymous

Jacob, I tested some optimization removing a couple of push and as you said the stressful operation is canvas.whatever, but if you read my comment it is about your last experiments and code I saw before this one (this one included). It was probably a not that useful suggestion/improvement in this case but when we have to deal with arrays and number we should consider these kind of optimizations and once we write code using them we will be sure we did everything possible to make JS fast, the rest is about engines, operations, etc. Sorry if it was superflous, take my comments as "readers hint" :-)
Regards

January 10, 2009 at 1:51 PM
Anonymous

good work..keep it up!

February 27, 2009 at 8:58 PM
Anonymous

i think it would be quite useful if u try it with a cartoon character..in a cartoon charater finer details and face expressions are not so explicit..so it may be a good thing to experiment .

February 27, 2009 at 9:01 PM
Anonymous

the cartoon character may be a mickey mouse.

February 27, 2009 at 9:01 PM
Unknown

THAT PROGRAM IS NOT GENETIC ALGORITHMS OR PROGRAMMING!!! If you actually read through his source code, it is completely random. he starts with one that is random, then says make another random one, then says if the new one is better then replace the older one. then he just keeps looping this. NO GENETIC ALGORITHM AT ALL!!!

March 16, 2009 at 8:56 PM
Unknown

Roger Alsing's that is... this guy has some good code, sorry for saying that i didn't actually read the post i just saw the same program and had to warn ppl that this isn't genetic algorithms but the new Javascript program you have worked on is definatly GA

March 16, 2009 at 9:00 PM
Prince_Porter

That's an awesome effect, I'd love to do this to a few pictures of myself. Thanks for sharing, bookmarked.

October 26, 2009 at 8:05 PM
Anonymous

Good Application. have you tried Cuckoo search or ACO?

March 13, 2012 at 2:52 AM
Unknown

Awesome project, awesome blog, awesome site!

Implemented a couple of different iterations of this a few years back in php/phpGD, and the thing that still irks me is that I never thought to include mutation rates (chances of mutation and amount of change) in the DNA. When a human is conceived, it's not like there is some outside source regulating the rate of random mutation. It's all contained in the DNA of the parents.

My assumption is that the optimal mutation rate will be much higher at the start of the process than at the end. Offspring created with a high rate/amount of change will likely die off in an already fairly fit population, whereas a high rate/amount of mutation might be advantageous in the beginning.

April 27, 2012 at 6:59 AM
Anonymous

Awesome!!!!

August 31, 2012 at 11:02 AM
MS

Very nice application. I will show this to my AI students when covering GAs. Just one question. What do you mean that the individual is encoded as a bit string? As I understand it each polygon as 4 RGB values and n x-coordinate values and n y-coordinate values. Do you mean that each individual is a bit string with x and y & R,G,B values in binary (for example 2 would be 10)?

March 5, 2013 at 9:53 PM
Unknown

Any chance this is on GitHub?

May 5, 2013 at 12:35 PM
Fernandub

This is fantastic! Any plans to open source the code?

May 7, 2013 at 9:30 AM
Chris Cummins

This is so awesome, it inspired me to make my own version: http://chriscummins.cc/genetics/ . Thanks a lot!

May 21, 2013 at 12:49 PM
Prerna Chikersal

Hey! In http://www.nihilogic.dk/labs/evolving-images/genetics.js
Why did u write this:
else {
var parent = candidates[0];
var child = new Candidate(parent.dna, parent.dna);
if (child.fitness < candidates[0].fitness) {
candidates = [child];
}
shouldn't it be child.fitness > candidates[0].fitness ?
That is, the child becomes the new generation only if it fitter than the parent?

February 15, 2014 at 10:48 AM
Post a Comment