Evolving an image, part I - genome generation

This will be the first post in a series on a simple evolutionary algorithm. The inspiration comes from several blog posts, but primarily from Roger Johansson and Chris Cummins. I haven't really dug through this code, but just started replicating what they wrote and the images they generated.

Credits to Pierre Lindenbaum for this image.

The plan right now is separated in this rough outline. This is the first instalment, with a focus on generating the data structures that represent a generated image.

1. Make a generator for the genome.
2. Translate genome to a rendered image.
3. Score the rendered image and compare for evolution.
4. (Optional) Possible optimizations.

For starters, let's generate random polygons. They have a shape, and a colour. I've decided for now on sticking to just one kind of polygon, the triangle. Perhaps in a later version there could be polygons with more edges, but I'm curious how good generated images could turn out with just triangles.

After some previous tinkering, I made some decisions about my implementation. For one, if triangles are only allowed to be drawn within the specified area, it's very hard to get a nice edge covering in the rendered image. As a solution the triangles will be generated using a normal distribution. This allows some parts of the triangle to stretch out beyond the edges of the rendered image, and thus makes them reach the edges.

Secondly, a choice on the colours. In the initial stages of this project I allowed any colour on the colour spectrum, including alpha channels, to be possible (256^4 or 4.294.967.296 colours). This made the chance that a newly generated colour in a new generation wasn't an improvement larger than desired. Instead the colours will be one of a reduced palette of choices (16^4 or 65.536 colours)

And lastly, although not an explicit choice, is the method of rendering. From the very start the triangles had a degree of transparency. They also could have been solids. With solids, the order of rendering becomes significant. My implicit choice was a genome where the order of items wasn't significant, and thus ended up with a need for an insignificant rendering order. Triangle colours are blended when they overlap, and the order doesn't matter.

Let's look at some code then.

python; genomeGenerator.py

#! /usr/bin/env python3

import random
import math

num_polygons = 50
width = 100
height = 100

def genCoord():
    x = random.normalvariate(0.5,0.5)*width
    y = random.normalvariate(0.5,0.5)*height
    return (x,y)

def genColor():
    col = math.floor(random.random()*16)*17
    return col 

def genRandomShape():
    p0 = genCoord(); p1 = genCoord(); p2 = genCoord()
    r = genColor(); g = genColor(); b = genColor(); a = genColor()
    return [p0, p1, p2, r, g, b, a]

def genRandomGenome():
    return[genRandomShape() for polys in range(num_polygons)]

The function genCoord() generates one tuple of x, y coordinates. The library used for the rendering of the image, python Pillow, uses tuples for coordinates, so this would be the most logical choice.

As said earlier, the coordinates are generated with a probability factor based on a normal distribution. The function random.normalvariate makes this easy, with as input parameters a mean and a standard deviation. It's easy to make a distribution that covers the domain [0, 1] by choosing the mean right in between (0,5). The standard deviation determines the spread of the distribution. With a standard distribution of 0,5, roughly 68% of the points is expected to lie between the domain [0, 1] of one standard distribution in each direction (The 68–95–99.7 rule). 95% Of the points is expected to lie between [-0,5 1,5], providing a decent chance that some vertices won't be in the rendered window, and as such will provide nice edge filling.

What's nice is that the domain for generated coordinates can be easily scaled by multiplying with the intended pixel width and height of th generated image. In this example I chose 100 pixels in both directions, but later on these values will become dynamic, based on the input image.

The colour function genColor() returns one of 16 numbers between 0 and 255 (0 17, 34, 51, 68, 85, 102, 119, 136, 153, 170, 187, 204, 221, 238, 255), to keep the colour complexity down.

One random shape, a polygon with three vertices and four colour values is made with the genRandomShape() function and returns a list with three tuples and four integers. If I'd want more vertices per polygon, this would be the place to generate those shapes.

Just one shape isn't enough to make a representation, so to tie it all together the function genRandomGenome combines multiple lists of shapes into a lists of lists, which I call the genome of a generated image. Changes in the genome result in different renderings, which will be the starting point for the evolutionary part of this story.

I'm going to end with an example of a generated image with 50 polygons. There is no intelligence to this image, just a totally random cloud of polygons. My next post on this topic will detail how this image was rendered.