Aineopintojen harjoitustyö: AI Odyssey 2012 : Challenge I

Challenge I: ASCII Art - deadline 12.11.  10:00 am

Update: First challenge is over, see the images produced here.

You are given a picture, and your task is to draw on image that is as similar to the original one as possible using ascii letters. Unlike in regular ascii art, however, you are given much more freedom with the letters: you may freely choose the color, location and size of each letter.

Example of an ascii art picture produced this way:

To be more specific, for each letter you draw, you must specify:
  • The letter to be drawn, a-z or A-Z.
  • The position of the letter.
  • The rotation of the letter.
  • The size of the letter.
  • The color of the letter, including alpha.
The result is judged by drawing the letters into a new image, and comparing each pixel of the new image and the old image. If a pixel of the original picture has RGB value (Ro,Go,Bo) and the new picture has pixel value (Rn,Gn,Bn), you get penalty of sqrt((Rn-Ro)^2+(Gn-Go)^2+(Bn-Bo)^2). Your goal is to minimize the total penalty over all pixels.
All the letters are drawn using the font.ttf provided in the archive below with point size 20.
 

Output format

Return text file with one line for each letter. The format of the line is:
letter x y rotation scale red green blue alpha
  • The position (x,y) denotes the left down corner of the letter at the baseline.
  • Rotation is clockwise radians around the point (x,y).
  • Color components range from 0 to 255.
  • Before drawing any letters, the image is completely white.
  • Letters are drawn in the order they are in the file. Colors are blended using the formula: new_color = (1-alpha)*old_color + alpha*draw_color
  • For exact details on how the penalty value is calculated, see the evaluation code at the archive below.

 

Example output

For the following line, we output letter 'a' with position (50,50), rotation 1.5708 (=pi/2 = 90°), size scale 2 and RGBA color (1,0,0,1) (=red).

a 50 50 1.5708 2 1 0 0 1

 

Sample code

The following archive contains Java code for evaluating solutions. You may use it to test your solution and it may also be helpful in solving the problem too.
 

Data

You have to generate ascii art for the following images:

http://www.cs.helsinki.fi/u/sysikask/ai2012/exactum.png ; 40 letters; must get less than 13842645

http://www.cs.helsinki.fi/u/sysikask/ai2012/ronsu.png ; 60 letters; must get less than 16559260

http://www.cs.helsinki.fi/u/sysikask/ai2012/tux.png ; 30 letters; must get less than 6035508

http://www.cs.helsinki.fi/u/sysikask/ai2012/ukkonen.png ; 50 letters; must get less than 27692717

Note: limits where fixed on Oct 30. In particular, the limit for ukkonen.png was decreased a lot, while others where increased a bit.

 

Submitting solutions

Send your results to sysikask@cs.helsinki.fi. Your submission must contain:

  • One text file for each image in the format specified above.
  • Code you used to generate the output.
  • A document describing briefly how you solved the challenge (~1 page).

Make sure to test your solutions using the evaluator in the archive and see that they get lower penalty score than those stated above.

 

Material

Book: Clever Algorithms (there's a free PDF!)
Buzzwords: Greedy Algorithm, Hill climbimg, Simulated Annealing, Genetic Algorithm

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

Printer-friendly versionPrinter-friendly version