Hevolisa

hevolisaHevolisa is an application that tries to approximate a bitmap image with colored polygons. It draws a set of random polygons which are changed/mutated in small random steps. There is an error function that compares the bitmap created from the polygons with the original image. If the error between the images is smaller than before then the new image replaces the old. This is done over and over again.

Here is the basic algorithm:

  1. Get the current drawing (polygons)
  2. Mutate the polygons in a random way (add, remove points)
  3. Create a bitmap of the polygons in memory
  4. Compare the bitmap with the comparison image using the error function
  5. If the error is smaller then replace the old drawing with the new drawing, else keep the old
  6. Repeat from 1.

The algorithm is not an example of a genetic algorithm. Instead it is a hill-climbing algorithm.

Hevolisa is a Haskell port of the EvoLisa program which can be found here:
http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa
[Genetic Programming: Evolution of Mona Lisa - Roger Alsing Weblog].
The original source code (C#) can be found in the FAQ section.

Implementation:

The Haskell implementation supports the functional paradigm. A drawing is composed from four distinct data objects called shapes:

  1. A single point
  2. A brush for different color values
  3. A polygon is a list of points with a brush for color
  4. A drawing is a list of polygons

All four shapes can be mutated, e. g. changed in a random way. There is a typeclass called Mutable which supports this operation. The typeclass RandomInit supports the initialisation of each shape with random values (in a given range).

The next step is to render/rasterize the polygons to a bitmap in memory. The rendering is done with Cairo. The gtk2hs library supports the access of the GTK Cairo library. The polygons drawing is rendered to a Cairo Surface.

The error function computes the error between the rendered image and the original image. The error function is a function of the color values in each pixel of the images. The error function is the sum of the squared differnces.

Error function:
f (r1,g1,b1) (r2,g2,b2) = (r1 – r2)^2 + (g1 – g2)^2 + (b1 – b2)^2

The color values are extraced from the Cairo Surface type. Here is the transformation of types from rendering to the result of the error function.

DnaDrawing -> Render -> Surface -> ByteString -> [Word8] -> [Integer] -> Integer

PNG files can be written at a defined interval of mutations. For an interval of 100 the following files will be created: 0.png 100.png 200.png 300.png …

Profiling/Optimisation

After the basic function worked as hoped I started to do some profiling with GHC 6.10.1. The program spent the most of its time in the error function. For the image which is 200×200 pixels it is executed 400.000 times (sequentially). At this point I thought about using Data Parallel Haskell.

Data Parallel Haskell

Data Parallel Haskell supports parallel execution of a function on mutliple data objects (Single Instruction Multiple Data – SIMD, also known as vectorisation). This is ideal for the error function which is a single function that operates on the color values of the whole image. I measured a speedup of 27% with DPH (the bottleneck is now the conversion from Surface to a ByteString to a list).

There are two branches of Hevolisa at the moment:

  • master: The conventional implementation of the error function
  • vector: Implementation with Data Parallel Haskell

The vector branch contains the DPH implementation. The impact of the error function could be reduced significantly. However the conversion function fromList ([a] -> PArray a) is now dominant.

Git repository on github:

http://github.com/dneun/hevolisa/tree/master

Download Cabal package from Hackage:
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hevolisa-0.0
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hevolisa-dph-0.0

Eine Antwort to “Hevolisa”

  1. Harald Korneliussen Says:

    Your error function is the square of the distance, rather than the distance. This means that getting one pixel just right is much better than getting two pixels almost right. In my experience, this leads to worse pictures.

    One trick I tried to speed up things in my Java version was to not compare the entire bitmap, but just a random sample of points. This didn’t work very well, unfortunately: Things weren’t significantly speeded up, and it did not converge on as good pictures.

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ photo

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s


Folgen

Erhalte jeden neuen Beitrag in deinen Posteingang.

%d Bloggern gefällt das: