Opdracht 2: Beeldcompressie

Inleiding

In een serie van innovatieve papers uit 1991-92 liet de Amerkaanse informaticus en video-artiest Karl Sims zien, dat het mogelijk is om complexe images te genereren door middel van genetisch geëvolueerde S-expressies. Sims maakte enkele video's van dit proces. In deze opdracht ga je door middel van genetisch programmeren een compressieformulie vinden voor een gegeven target image.

Globale omschrijving

Vind, door middel van genetisch programmeren, een goede compressieformule voor een gegeven target image.

Probleemstelling

Fig. 1. Een image.

Deze sectie legt uit wat het probleem is. In principe is het niet nodig om deze sectie helemaal te lezen of te begrijpen, maar het geeft je misschien wel wat meer inzicht in de opdracht. Alles wat hieronder is geformuleerd is al geïmplementeerd in de uitgereikte Netlogo source. Het enige wat gevraagd wordt is om een genetisch algoritme te implementeren.

Een image in ons model is opgebouwd uit 30x30 pixels (Fig. 1). De hoek linksboven wordt beschouwd als het punt (-1,1) en de hoek rechtsonder als het punt (1,-1). Een compressie is een functie f(x,y) die voor elke x uit het interval [-1,1] en voor elke y uit het interval [-1,1] een reëel getal teruggeeft wat de kleur van het punt (x,y) bepaalt. Omdat een image uit een eindig aantal pixels bestaat (in ons geval 30x30), wordt de functie slechts aangeroepen voor de x en y coordinaat van elke pixel. Deze wordt bepaalt door het middelpunt te nemen van de desbetreffende pixel.

Vervolgens moet voor elke pixel uit het resultaat van de functie f(x,y) een kleur worden bepaald. Eerst wordt voor elke pixel de pixel-value bepaald, wat een getal is uit het interval [-1,1]. Dit wordt berekend door middel van de volgende functie, waarbij gegeven een pixel p, de getallen p_x en p_y respectievelijk de x en y coordinaat van deze pixel zijn:

De fout kan uiteindelijk bepaald worden door voor elke pixel p uit de totale set van pixels P de afstand tussen de pixel-value(p) en de target value voor p (verkregen uit de target-image), gedenoteerd door target-value(p), te bepalen, en dit bij elkaar op te tellen. In formule:

Randvoorwaarden

Hier staat wat moet. Bij afwijking van randvoorwaarden worden punten in mindering gebracht.

1. Zorg dat je programma beschikt over een geschikte BNF. In deze opdracht is het, zoals reeds eerder vermeld, de bedoeling om een functie te vinden in termen van x en y. Echter, er zijn nog verdere restricties aan deze formule; de verzameling van alle mogelijke formule's die we in deze opdracht beschouwen kan inductief gedefinieerd worden als volgt:

   • Elk element uit de set

     \{x,y\}\cup\{n/100\mid n\in \{-99,-98,\dots,89.99\}\}
     is een formule.

   • Als φ en ψ formules zijn, dan zijn (φ + ψ), (φ − ψ), (φ * ψ) en (φ % ψ) het ook.

   Met andere woorden, de terminale symbolen zijn x, y en elk getal in het interval (-1,1) wat met maximaal 2 decimalen geschreven kan worden. De functiesymbolen zijn +, - * en %. De functie % is, zoals gedefinieerd in het boek "Genetic Programming" van Koza, de safe division. Deze functie zorgt ervoor dat je programma geen fout genereert als er wordt gedeeld door 0, en kan gedefinieerd worden als volgt:
   \%(n,d)=\left\{\begin{array}{ll} n/d & \mbox{if } d\neq 0 \\ 1 & \mbox{anders}. \end{array}\right.
   Let erop dat deze functie niet "infix" aangeroepen mag worden zoals bijvoorbeeld + en -. Correct is dus om bijvoorbeeld te schrijven (% x y) en niet (x % y). De BNF die je uiteindelijk maakt moet elke mogelijke formule zoals hierboven gedefinieerd kunnen genereren.
   
   Hieronder nog een aantal voorbeelden van correcte formules die je BNF moet kunnen genereren:
   • ((% (((y - x) * x) - (y * y)) 0.07) * x)
   • (% (x + y) 0.5)
   • (% (x * y) (0.5 * 0.01))
2. Zorg dat je programma beschikt over een geschikt genetisch algoritme, die met behulp van je geschreven BNF taal een populatie aanmaakt en kan kruisen. Materiaal aangeboden op het college bevat flowcharts waarop de globale werking van een genetisch algoritme wordt gespecificeerd.
3. Zorg dat parameters voor het genetisch algoritme instelbaar zijn voor de gebruiker. Denk aan de populatie-grootte, het aantal generaties, en de kruisingskansen. Zorg ook dat het beste programma wordt onthouden en dat deze kan uitgevoerd worden als de gebruiker daar om vraagt. Bedenk hoe je bijvoorbeeld fout-proportionele selectie (in plaats van fitness-proportionele selectie) kan uitvoeren.
4. Zorg dat je programma aan het einde van elke generatie de tot-dan-toe gevonden beste formule laat zien op het scherm.
5. De documentatie is erg belangrijk. Leg goed uit wat het programma doet, hoe het werkt, wat geschikte parameters zijn en hoe het verbeterd kan worden.
6. In het netlogo bestand staat aangegeven welke code niet mag worden veranderd. Doe dit ook niet.
7. Er mag niet afgeweken worden van de JGE extensie.

Extra

Extra punten kunnen worden verdiend door het implementeren en documenteren van de volgende features.

1. Werking. Je model moet in de allereerste plaats goed werken. Hoe laat je dat zien? Dat kan door eerst een goed gedocumenteerde en duidelijk geoperationaliseerde definitie (maat) voor de effectiviteit van adaptatie op te stellen. Maak grafieken (zoals een plot van de fout van het beste individu tot dan toe).
2. Overzichtelijkheid. Zorg dat je programma eenvoudig en overzichtelijk is. Probeer je programma niet te ingewikkeld te maken.
3. Optimaliteit. Een programma wat goede oplossingen vindt in weinig tijd wordt beter gewaardeerd.

Aanpak

Een mogelijke werkwijze is de volgende.

1. Begin met het maken van een BNF. Het image-compressie bestand bevat 3 voorbeelden, hieruit kan je afleiden wat je BNF moet kunnen genererenn.
2. Probeer in NetLogo met de JGE extensie een populatie van willekeurige genotypen te laten maken, en probeer deze ook om te zetten naar fenotypen met behulp van de gemaakte BNF.
3. Maak een functie die van een willekeurig genotype bepaalt wat de fout is:
   1. Zet het genotype om naar een fenotype door middel van de BNF.
   2. Plug de gegenereerde formule in simulate, bijvoorbeeld: 'simulate "(x + y)" true' plugt het programma "(x + y)" en laat het zien op het scherm. Nog een voorbeeld is 'simulate "(x * 0.5)" false' wat het programma "(x * 0.5)" verborgen uitvoert (maar wel de fout bepaalt).
   3. Vervolgens kun je uit de globale variabele fout aflezen wat de fout van de formule was.

Benodigdheden

1. Hoofdstuk 2 Grammatical Evolution, pp. 9-24, uit: I. Dempsey et al. (2009). Foundations in Grammatical Evolution for Dynamic Environments, SCI 194. Springer-Verlag. Dit is verplicht materiaal.
2. NetLogo 4.1.
3. Het NetLogo "image compressie" bestand.
4. jGE NetLogo extension v2.0 (inclusief documentatie).

Verdere tips

1. Voor velen blijkt Fig. 2.2 uit Dempsey et al.'s hoofdstuk zeer verhelderend.
2. De documentatie van de JGE extensie bevat een voorbeeldprogramma waarin enkele functies van de library worden gedemonstreerd.
3. Het aanroepen van to simulate [prog visible] is het hoofdingrediënt voor het bepalen van de fout van een individu. Bekijk de voorbeelden in het netlogo bestand.
4. De JGE extensie is spatiegevoelig als het gaat om genereren van een programma uit een genotype met behulp van het BNF. NetLogo heeft hier over het algemeen geen problemen mee.