Evolution of Mona Lisa in JavaScript & Canvas | Hacker News Reader

Evolution of Mona Lisa in JavaScript & Canvas

alteredqualia.com

85 pointsbd40 comments

I reimplemented the algorithm from [1] in JavaScript using canvas.getImageData for fitness computation.

It's far from perfect, but it seems to work. So far I'm at around 1/30th of the original iterations (took ~1 hour) and it already looks a bit like Mona Lisa :).

I'll be updating the page with more evolved images.

Note: it works only in few browsers: so far I'm aware of Firefox 3.0.4 and Opera 9.61. Firefox is significantly faster.

[1] http://news.ycombinator.com/item?id=389727

You should have it automatically upload images so everyone doesn't have to start at nothing.

Very cool. I'm running WebKit nightly 49090 and it's blazingly fast -- 1683965 fitness in 30 minutes

I envy you :).

You may try to run it on different images, I just added new experimental feature: you can set your own target image.

This does crash JavaScript sometimes on some images (for unknown reasons). If this happens, just reload the page.

I was trying to do that by saving locally, but FireFox refuses to allow getImageData on an image loaded from the filesystem by a web page loaded from the filesystem, with an NS_ERROR_DOM_SECURITY_ERR

Anyway, I will now try with your set-your-own-image version.

You can run it locally if it is on your local webserver (http://localhost) instead of just filesystem (file://).

That's how I work on it (XAMPP).

http://en.wikipedia.org/wiki/Xampp

That would be 39090. I'm sure 49090 would be even more faster, in a year or so =)

Oops! Yes =)

Didn't know an .getImageData() existed! (Sometime I need to look at the bleeding edge APIs.) Very cool hack!

From the description, your algorithm sounds like it would hit this case very quickly:

A polygon overlaps another polygon and improves fitness by N. It gets mutated and fitness goes down, so that is not kept. The polygon stays in a local maxima position, when one mutation lowering fitness might allow much better fitness in future.

Yet the images look like that doesn't happen - have you deliberately avoided it, or isn't it a problem in practise?

I don't do anything smart. These are just brute force mutations, always the same.

The only parameter tuning I did was to try several numbers of vertices per polygon for about 15 minutes and from there on I just used the one (6 vertices) that produced image I liked the most.

10 vertices produced too much noise, 4 vertices was kind of rough.

I started coding with possible variable number of vertices (that seems to be the case in the original algorithm), but it was just too slow in JavaScript.

Anyway, optimization can eventually collapse vertices, so basically I just hardcoded an upper bound.

And mutations are kind of soft, always just one element (R,G,B,A,X,Y).

I guess there is some place for improvement, for example by using HSV comparision for fitness. Though this may be slow. Raw canvas image data are RGBA.

Ah yes, I remember also that at the beginning it didn't want to converge at all when starting with random colors. It works when it can gradually build up from a blank slate.

for example by using HSV comparision for fitness

I tried with HSB. It didn't produce good results. The image was always too dark.

In HSB, colors that are far apart in our perception can have close distance. For example two colors with the same Brightness, Saturation but a different Hue.

Using HSB in the DNA was perfect. It's hard to mutate a RGB color in the right direction. You have to get 3 composants right. In HSB a single modification can change everything.

BTW, I coded a Java version after seeing the original. It works, but first, it doesn't converge very fast, second, it's stuck at: http://i33.tinypic.com/2yycdc8.jpg

On the bright side, I can easily switch the population size to 50. Java is very good at this. I piggy back on automatic hardware acceleration for rendering.

How did you get yours to converge sooo fast?!

Mine is nothing, try the original program from Robert Alsing. He already released the source code and binaries:

http://rogeralsing.com/2008/12/11/genetic-programming-mona-l...

From what I have seen, he is doing extra type of mutations that I was too lazy to implement: move polygons in the stack (in addition to changing colors and moving points around).

Also how you do mutations matters: it seems smaller deltas are better, though they shouldn't be too small.

Simulated annealing moves to locations with lower fitness with some probability each iteration, with the probability of moving to a lower fitness location changing with time and the size of the moves changing with time. My understanding was that the size of the changes and the probability of moving to lower fitness fitness levels did not decrease uniformly but moved down then up then down and up in a humped-shaped pattern, but the wikipedia page disagrees with me.

What a timesink :)

I've created a number of variations on this, including a black&white one which does a good job of Darwin.

The biggest improvement I've made is in limiting the size of the mutation. Now I have a 1 in 50 chance of executing your mutation code, else the changes are limited to within about 10% of their existing value. This gave me a very nice Velociraptor.

I'm also playing with triangles instead of polygons, but I'm impatient and trying to run them all simultaneously. Time to upgrade...

How do you compute the similarity, pixel by pixel?

Yes, I try to do it as cheaply as possible.

  abs(r1-r2) + abs(g1-g2) + abs(b1-b2)

Typically, distance between multiple samples of stuff uses the minimize-the-sum-of-squares technique, maybe it applies here too?

Now we just need "someone" to implement a real GA algorithm with a real pool of possibilities and real crossover of some kind, and you can get a visual sense of which is faster.

"Someone."

All this (very clever by the way) reminds me of an idea I had a while back that plays to the internet's true strengths:

Create a rendering algorithm such as this but with the fitness function calculated by presenting a set of the output images to web visitors and having them choose the one(s) that they like the most.

My thesis is that with enough iterations/visitors you'd eventually generate a load of highly tuned pornography.

Gags about hot-or-not go here... :-)

You might want to chuck a copyright on that code, in case some fellow hackers want to take the idea and run with it. (That assumes you want other folks messing with it!)

Yup, that was the idea.

I just added MIT License [1] to the source.

Everything is in one self-contained HTML file (sans images). Feel free to improve it :).

[1] http://en.wikipedia.org/wiki/Mit_license

Hi there! First of all, thanks a lot for the nice webpage and code. I have uploaded a modified version at http://www.breidt.net/Image_evolution.htm with an additional button to produce SVG (http://de.wikipedia.org/wiki/Scalable_Vector_Graphics) from the current polygon data.

Martin

Awesome. I merged your code into the latest version of the page and pushed it online.

I've tried to play build the idea cubicle67 mentioned to use relative mutations instead of absolute ones. What I've implemented is a function that does not limit the change at all, but simple makes it more likely to be small and less likely to be large.

The new value becomes either (MAX - current) * P or current * P (50% chance on each), where P is the product of two random variables between [-1, 1]. I'm not sure how that is distributed (been a while since that statistics course), but it obviously favors numbers closer to 0.

This optimization looks rather efficient, as the same image seems to get about 67% more beneficient mutations in the same interval of generations.

Another change I would like to implement (but haven't yet) is a low chance of changing multiple values at once, which may eventually escape from a "dead end".

The best improvement of all would be to allow users to airbrush "priority" onto different regions, which then get weighted in the fitness score. If I'm generating a portrait, I care a lot more about the eyes than the background, for example.

I will try your function in my code this evening. Another strategy I thought about is to have a small chance of replacing a polygon with a random new polygon. It seems that it would help get out of dead end situations.

Ok, I tried it and it converges much faster. My dna data is all integers so the update function is something like constrained update( int existing_value, int limit ) { new_value = random( limit ) constraining_value = random_float difference = ( new_value - existing value ) * ( constraining_value * constraining value ) return difference ( apologize if code doesn't format correctly).

I also tried randomly replacing a poly with a new random shape and color poly 5% of the time to get away from local minima... didn't seem to help. I'm still doing a bit on this in my spare time if anyone is interested.

Later.

I prefer Facemaker: http://facemaker.redshiftmedia.com/

The genetic algorithm technique is often used to solve a problem just because it's cool, and not necessarily because it is the best way to solve the problem.

Is this the case with this "Mona Lisa" problem? Is there an alternative algorithm for finding the polygons that would be more efficient and give better results?

It's likely that there is a better way. There already exist deterministic bitmap rasterizers which might yield decent results, and almost instantly. A greedy algorithm that tries to place the "most necessary" polygon first would almost certainly find a reasonable solution in a very short amount of time. Even a hybrid approach -- where the algorithm randomly picks a solution parameter and does a line search for the best value -- would converge faster than random hill-climbing alone.

Thanks so much for making your code available. I've reimplemented your app in java with the idea of improving the speed. Unfortunately java2d rendering speed is not so hot - I'm getting about 2k iterations/minute on a 2ghz p4m with 90% of the time being spent rendering polygons. As for optimizations, I am going to experiment with some of the mutations from Mr. Alsings code -- I'm also thinking about adding multiple worker threads or possibly distributing to multiple machines.

Is there any C++ code for this? There's something interesting I would like to try, but JS is not my beast. If there is none, I'll port, but perhaps someone already has written this in C or C++, saving me some trouble.

Has anyone every gotten an outside image to work? I've linked to several different images to no avail.

Yes, but it's hit and miss. Sometimes it counts but does nothing sometimes I can see the shapes flickering, but it never picks any as "best", and sometimes it looks like it's still working on the mona lisa or on a different size canvas.

None that I've found on Flickr have worked.

I googled for "200x200" and found the Firefox logo in that size, and it's evolving that... fitness has just crossed under 1,000,000 after about 15 minutes, but it isn't recognisable yet...

Another half hour, and it's just above 900,000 after 43,000 steps - it still looks nothing like the FF logo though.

That is, it looks nothing like it. It has, for example, no dark blue, orange, yellow or white - and only a smidgen of pale blue in completely the wrong place. The whole square is shades of hessian brown/pale green/caucasian artificial limb with a blotch of pink.

Yep, cartoon images seem to be tough for this particular algorithm to optimize.

The first velociraptor I tried was a stop sign from XKCD and it failed miserably.

Though you never know, I also thought black&white Darwin image was hopeless, and it did managed to start converging eventually.

I've gotten a very firefoxy logo in under 2,000 beneficial mutations (about 45K steps).

6 50 0 0 0 0.000 31 99 27 154 36 0 59 165 184 185 188 92 0 0 0 0.000 77 92 74 102 16 11 61 156 190 133 13 196 0 0 0 0.000 25 16 39 176 197 38 199 69 155 166 146 111 0 0 0 0.000 139 72 37 71 167 67 28 143 179 106 1 24 0 0 0 0.000 187 186 157 31 138 128 175 127 24 56 183 76 0 0 0 0.000 11 15 39 61 123 170 92 46 38 195 54 5 98 36 151 0.754 28 210 7 172 214 269 260 225 252 254 13 208 0 8 106 0.329 242 184 159 80 100 82 54 261 126 80 123 89 242 207 116 0.754 29 226 172 283 89 41 192 281 298 192 266 193 94 44 48 0.202 253 195 104 131 39 37 41 178 242 269 266 164 104 223 207 0.313 87 46 115 46 162 82 103 115 186 293 80 203 204 150 0 0.622 161 294 284 210 6 172 10 118 26 82 19 195 245 65 15 0.991 87 277 94 265 234 229 180 107 34 53 178 138 0 225 53 0.083 188 244 155 215 243 122 162 119 137 8 187 146 251 91 8 0.417 203 89 145 276 238 258 288 120 273 58 85 125 0 0 0 0.000 188 183 68 11 43 129 122 187 27 22 125 39 251 0 0 0.963 85 115 23 91 135 38 35 191 171 284 254 162 0 0 0 0.000 95 23 180 89 166 138 102 95 41 19 148 13 0 0 0 0.000 20 116 80 40 34 108 192 189 22 199 179 17 230 252 37 0.041 243 57 16 201 141 85 112 17 138 68 82 287 0 0 0 0.000 163 35 186 186 168 76 103 141 71 136 66 30 0 0 0 0.000 21 24 23 99 93 148 79 185 90 134 156 161 60 145 137 0.990 155 92 222 156 22 82 97 69 104 280 74 136 0 115 137 0.459 1 206 192 10 101 17 224 60 251 84 112 71 46 0 11 0.167 120 298 26 224 7 182 105 168 134 5 34 49 0 0 0 0.000 77 27 142 134 63 67 183 31 102 88 157 3 105 240 100 0.110 124 100 145 27 139 262 219 120 113 48 96 49 207 21 0 0.945 22 93 24 112 198 225 134 288 55 249 6 175 138 11 13 0.203 54 168 139 299 182 234 115 258 52 245 24 231 0 0 0 0.000 44 129 134 91 112 45 172 17 106 19 193 185 0 0 0 0.000 108 49 17 11 119 118 54 166 42 31 165 21 0 0 0 0.000 20 127 170 142 141 52 155 64 57 73 113 50 0 0 0 0.000 135 33 28 182 70 11 31 30 116 28 16 74 0 0 0 0.000 168 170 189 25 108 30 110 155 91 83 74 196 0 0 0 0.000 158 174 112 197 4 98 134 23 18 63 152 106 245 205 0 0.929 20 173 15 91 270 175 292 121 243 45 269 242 112 60 0 0.051 264 243 35 198 277 53 6 99 95 294 199 289 0 163 227 0.392 215 39 177 7 109 13 37 52 31 50 164 104 69 8 21 0.246 170 77 170 195 49 249 33 106 180 163 97 235 175 52 1 0.706 50 172 101 282 52 249 68 229 20 68 71 37 0 0 0 0.000 117 49 127 153 88 156 92 130 44 156 145 43 0 76 147 0.991 73 30 30 82 66 98 160 126 225 70 154 223 0 0 0 0.000 4 54 53 118 82 194 51 120 67 88 19 144 0 0 0 0.000 44 14 36 5 130 142 91 76 187 174 124 101 245 170 0 0.709 132 15 31 237 272 65 234 267 26 35 30 141 247 108 24 0.609 189 161 91 62 41 113 218 103 49 231 222 202 232 121 15 0.974 180 86 96 68 122 131 159 284 68 266 24 52 0 0 0 0.000 17 35 125 152 56 70 80 158 90 139 105 20 0 97 0 0.041 135 84 136 97 170 63 102 24 178 111 94 6 233 242 176 0.111 26 119 40 233 21 220 169 121 188 169 92 78 244 170 0 0.553 289 124 206 17 205 73 216 274 8 184 291 195 0 0 0 0.000 33 187 43 130 83 266 68 90 146 157 134 61 34 168 241 0.500 258 290 184 101 191 221 254 63 125 143 188 113 0 0 0 0.000 220 166 264 162 201 288 169 71 55 74 42 16 0 0 0 0.000 76 74 172 214 158 142 36 62 5 264 153 158 0 0 0 0.000 299 284 162 278 213 201 98 122 153 193 158 21 0 0 0 0.000 155 241 1 275 204 80 30 267 113 132 210 83 0 0 0 0.000 101 211 256 8 222 32 133 68 220 258 250 234 0 0 0 0.000 178 277 298 62 264 190 241 205 230 17 196 190 0 0 0 0.000 199 284 131 194 255 271 83 17 205 28 50 60 0 0 0 0.000 74 270 205 122 2 231 190 174 63 10 70 212 232 0 0 0.391 101 183 14 192 23 45 61 266 223 283 263 112 53 210 238 0.253 131 3 279 122 103 8 177 214 178 223 246 110 0 0 0 0.000 54 62 272 174 5 268 66 84 160 223 77 47 0 0 0 0.000 114 44 77 82 263 39 175 125 116 31 200 107 30 62 34 0.628 111 216 174 34 175 224 225 50 244 47 182 9 135 22 0 0.314 19 200 65 275 179 296 220 262 110 231 179 109 0 0 0 0.000 108 179 164 191 32 236 38 68 270 150 40 258 0 0 0 0.000 276 157 126 212 61 13 206 4 184 127 57 217 182 0 0 0.985 2 152 80 275 51 238 77 112 137 295 70 258 0 0 0 0.000 127 135 202 143 52 31 35 276 239 226 91 183 3 171 206 0.364 150 3 102 190 25 247 0 269 240 69 20 50 70 0 76 0.010 10 226 139 49 13 93 134 145 280 60 157 240 0 0 0 0.000 18 149 143 291 8 203 92 56 300 120 163 246 13 63 180 0.936 231 134 228 186 193 186 74 133 244 165 161 219 0 0 0 0.000 135 37 163 291 97 64 269 251 107 225 19 7 251 221 0 0.345 221 53 284 109 10 206 238 280 288 163 263 51 223 83 0 0.277 144 101 76 109 215 104 93 80 3 152 202 293 0 0 0 0.000 56 116 274 147 18 257 85 37 207 256 47 37 0 5 58 0.918 271 208 74 221 200 159 247 126 186 225 210 212 231 251 253 0.121 106 21 163 164 203 79 23 276 42 243 277 25 62 206 255 0.450 198 48 100 1 276 117 69 187 173 61 161 55 0 0 0 0.000 113 73 206 45 243 140 100 143 118 183 10 80 242 119 0 0.713 51 250 13 104 10 157 76 61 139 249 271 195 0 0 0 0.000 119 46 222 181 241 261 255 41 176 219 41 114 0 11 83 0.583 214 176 213 65 89 190 153 125 120 48 199 226 69 12 0 0.071 194 168 91 289 217 284 215 94 215 147 7 271 0 4 45 0.171 107 225 175 159 214 59 274 115 266 129 281 103 0 0 0 0.000 286 149 68 159 97 140 38 11 236 172 223 60 0 0 0 0.000 235 114 282 286 55 159 98 4 17 170 44 208 0 0 0 0.000 2 211 127 21 292 254 41 65 29 214 123 199 0 206 0 0.013 61 28 279 100 194 61 261 275 243 217 22 245 0 0 0 0.000 123 42 278 31 254 290 26 229 219 209 233 36 0 0 0 0.000 41 217 170 260 229 42 118 10 225 248 181 58 55 56 78 0.010 277 144 27 76 28 185 34 250 131 280 157 204 0 0 0 0.000 115 82 8 9 100 219 245 290 59 128 180 64 0 0 0 0.000 12 185 119 136 143 63 138 300 57 121 117 212 0 11 49 0.035 55 177 200 173 264 102 151 113 183 210 55 66 0 0 0 0.006 212 204 39 196 48 263 72 136 177 188 181 81 0 0 0 0.000 104 266 201 20 13 230 101 236 120 126 209 282

for this iamge http://www.spreadfirefox.com/files/images/TMlogo-300x300.jpg

I know about this problem, just I'm getting too tired to be able to debug it. It's almost 5am here.

If it does something weird, just reset it by forced reload (Ctrl-F5).

Stay tuned tomorrow for DNA import/export, it's like 80% done.

[Edit] DNA import/export is done. Just please be gentle with it, for the moment it's very fragile (e.g. whitespace matters).

If somebody wants to play with it, DNA format is very simple (all INTs except for ALPHA which is FLOAT):

  NUMBER_OF_VERTICES NUMBER_OF_POLYGONS R G B ALPHA X0 Y0 X1 Y1 ... XN YN ... R G B ALPHA X0 Y0 X1 Y1 ... XN YN ...

Reply on news.ycombinator.com