Genetic Programming: Evolution of Mona Lisa

http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/

by bdfh42 • 18 years ago

111 26 18 years ago

patio11• 18 years ago

Now that is just a cool hack.

Sadly I don't think there is too much commercial value in extraordinarily CPU-intensive lossy image compression but it sure beats the heck out of 99.5% of what I saw in undergraduate AI/algorithms-type courses as a demo.

Incidentally, I think from a marketing perspective that is a great test case to use for it. If you had picked, I don't know, some portrait by an unknown artist it would have been no less technically impressive but it wouldn't spread NEARLY as far. (This is one reason why I managed to work the KJV Bible and the US Constitution into my test corpora for almost every natural language processing project I've ever done.)

henning2• 18 years ago

Most of the papers one sees about serious, potentially lucrative applications of biologically inspired optimization metaheuristics (algorithms like the one in the OP) are engineering-oriented.

For example, NASA used evolutionary computation to design a little antenna thing, and it went into space, and it was human-competitive (as good or better than anything a human could design in a reasonable amount of time). http://ti.arc.nasa.gov/projects/esg/research/antenna.htm

Most of the applications, in other words, have little to do with the kind of highly data-driven web applications with rapidly changing requirements that seems to occupy a lot of the time of the users on this site. :( Still, excellent candidate for spare-time/weekend hacking.

Finally, one basic thing to observe about most of these heuristics is that they are embarrassingly parallel, which means they really could make good use of a 16-core machine.

yters4• 18 years ago

Koza's a pretty big name in that space:

http://www.genetic-programming.org/

apgwoz2• 18 years ago

But, with some pre-processing before the genetic action starts, it might make for an interesting effect for Hollywood, or to show off to your friends.

henning2• 18 years ago

Related techniques could be utilized for creating non-photorealistic/stylized renderings of an existing/reference image. There has been some work on this.

randomwalker4• 18 years ago

"Sadly I don't think there is too much commercial value in extraordinarily CPU-intensive lossy image compression"

First, as commenters on that post pointed out, this is horribly inefficient. It's not even a GA, it's a blind hill climber! Hint: you need crossover; calling something "DNA" is not sufficient.

Second, even if it's a large image, and takes say 10 minutes on a laptop-class computer, that's 1 cent on EC2. Computing power has gotten ridiculously cheap.

Third, here is at least one killer app: mobile. B/W still sucks, and rendering speed could use some help as well. I can certainly imagine large websites benefitting from this. This is basically a raster to vector converter. You could start using this right now in SVG enabled environments.

Finally, I just thought of something truly sick. Note that you can draw arbitrary polygons using javascript. http://www.uselesspickles.com/triangles/demo.html Put these two together, and... dear God, I don't even want to think about it.

nihilocrat• 18 years ago

Plus, the algorithm could always use some optimization. I figure implementing a true genetic algorithm (several 'painters' working at once, recombining their DNA instead of overwriting) would get to a 'good enough' result more quickly.

It makes me wonder whether there is some demoscener who has already done something like this to fit the Mona Lisa (or probably something geekier, like a picture of Clive Sinclair) into their 4k demo.

shaunxcode2• 18 years ago

a frame by frame video of that would be awesome (and I assume incredibly long - 904314 frames to be exact?) Assuming that it takes 24 frames for one second of film I guess it would be (904314/24)/60 = 627 hours of film so maybe it ought to be a little bit time lapsed.. Seriously though I could imagine such cool film/game effects.

gdee• 18 years ago

You forgot a div there. Those are 627 minutes. So more like 10.26 hours. Your conclusions stand though :)

shaunxcode2• 18 years ago

hah good call

bd4• 18 years ago

If somebody is interest in seeing this process in real-time, I implemented the algorithm in JavaScript:

http://news.ycombinator.com/item?id=392036

huhtenberg• 18 years ago

This is exceptionally cool. It is actually on par and along the lines of the fractal compression ideas.

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

bd4• 18 years ago

If we want to be more precise, this type of optimization is called simulated annealing (population = 1, no cross-over, just mutations):

"At each step, the SA heuristic considers some neighbour s' of the current state s, and probabilistically decides between moving the system to state s' or staying in state s. The probabilities are chosen so that the system ultimately tends to move to states of lower energy. Typically this step is repeated until the system reaches a state that is good enough for the application, or until a given computation budget has been exhausted."

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

randomwalker4• 18 years ago

Unfortunately, it's not even that! Simulated annealing needs a cooling heuristic, which makes the algorithm smarter as it gets closer to the optimum. What this is is some combination of hill climbing and random state space search. Not sure if it has a name.

Want evidence? Look at the iteration counts. With SA, you'd see the differences between the successive pictures be roughly constant or even decrease (I can't prove it, but I've implemented it, and you usually end up choosing a cooling heuristic that roughly matches the human intuition for "closeness").

As it is, the algorithm that's implemented finds it exponentially harder to get close to optimum. You start off with a gap of 100 iterations between optima, and you end up at 300,000.

Which is exactly why I think this is even more amazing -- it's just about the dumbest algorithm you can think of, and it still manages to vectorize an arbitrary raster image. If an actual GA or SA version were built, it could have some real potential. (See my comment below.)

globalrev• 18 years ago

I just did this because I got inspired. What does it count as, genetic programming? It uses naive mutation and crossover(don't know if they qualfiy as real crossover and mutation) and a simple fitness function. It is fairly pointless since all it does is find a list with ones but it does so in just around 400 generations while random guessing takes forever.

  from __future__ import division
  import matplotlib.mlab as M
  import matplotlib.pyplot as plt
  import random as R
  
  def crossover(a, b):
      new = []
      for x,y in zip(a,b):
          if R.random() > 0.5:
              new.append(x)
          else:
              new.append(y)
      return new

  def mutate(xs):
      xs[int(R.uniform(0, len(xs)))] = int(R.uniform(1, 10))
      return xs

  def fitness(xs, goal):
      summa = 0
      for x,y in zip(xs, goal):
          summa += abs(x-y)
      return summa, xs, True if summa == 0 else False

  def nFittest(xs, goal, n=2):
      fittest = sorted(fitness(x, goal) for x in xs)[:n]
      if fittest[0][2] :
          return fittest[0]
      elif fittest[1][2]:
          return fittest[1]
      else:
          return fittest

  def init(fields, n):
      return [[int(R.uniform(1,10)) for x in     xrange(fields)] for y in xrange(n)]

  def newGen(a,b,n):
      next = [crossover(a,b) for x in xrange(n)]
      mutated = []
      for x in next:
          if R.random() > 0.9: mutated.append(mutate(x))
          else: mutated.append(x)
      return mutated

  def run(printing=True):
      n = 0
      first = init(15, 10)
      while n < 1000000:
          n += 1
          next = nFittest(first,   [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], 2)
          if type(next) == tuple: break
          first = newGen(next[0][1],next[1][1], 10)
      if printing:
          print "Nbr of generations: ", n
          print next
      return n, next

  def plot():
      trials = [run(False)[0] for x in range(100)]
      print "Done trials"
       averages = [sum(trials[:x]) / len(trials[:x])\
                  for x in xrange(1,len(trials)+1)]
      print "Done averages"
      plt.plot([x for x in xrange(len(averages))],   averages, 'ro')
      plt.axis([1, 100, 0, 1000])
      plt.show()

  def test():
      goal = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
      c=0
      while 1:
          c += 1
          x = [int(R.uniform(1,10)) for y in range(15)]
          if sum(x) == 15: break
          if c % 10000 == 0: print c
      print x

bd4• 18 years ago

Ah yes, you are right. I also didn't realize it's not even genetic programming as DNA seems to be just polygon data, not polygon-drawing programs.

BTW your comment was eponysterical :)

http://mssv.net/wiki.cgi?Eponysterical

yters4• 18 years ago

Since it has a neighborhood function, i.e. doesn't select from the global population, I'd say it's a form of tabu search.

bemmu• 18 years ago

Here's something I'd like to see someone try.

Take pictures of a 3D object from say 100 different angles, remembering which angles they were. Now, use this mona lisa algorithm to put 3D polygons inside a box of sufficient size, keep those that most look like the original object when looked at from all those angles.

Will you get a compressed 3D representation of an object this way?

rw• 18 years ago

That is a really exciting application. Keep in mind that "compressed" normally implies a lossless representation, not lossy, like you are proposing.

lkozma• 18 years ago

Usually these type of inverse problems are severely ill-defined. There can be many 3D configurations that give the 2D images, and you need to use some knowledge of the world (or some regularization) to select which one is the most plausible.

A typical application is when they measure brain signals at the surface of the brain and then try to reconstruct what happens inside. Have people thought of using genetic algorithms and other stochastic methods ? Probably yes.

Genetic Programming: Evolution of Mona Lisa

Related Stories