A True Genetic Algorithm for Image Recreation — Painting the Mona Lisa
How I used Python to create a genetic algorithm that recreates a target image. Previous attempts at this problem either result in grainy/pixelated results [1], lack an initial population to qualify as a true genetic algorithm [2], or generate results that are highly abstracted with no details of the target image [3].
Implemented in Python, my algorithm is able to recreate a relatively faithful representation of the target image with an aesthetic characteristic to it [4].
Overview of Genetic Algorithms
A genetic algorithm is an optimization tool inspired by Darwin’s theory of evolution. The algorithm mimics the process of natural selection, which chooses the fittest individuals from a population to create offspring and populate future generations.
A genetic algorithm consists of several components:
- Initial population
- Fitness function
- Selection Criteria
- Crossover
- Mutation
Initial Population
The genetic algorithm starts with a group of individuals, referred to as the initial population. Each individual is a potential solution for the target we are optimizing for. Typically, the individuals of the initial population are created randomly, assuming no prior knowledge of the solution. As a result, they are generally poor solutions. This is not an issue because their purpose is to serve as the building blocks for future generations.
Fitness Function
Once an initial population is created, the individuals are evaluated based on a fitness function. The fitness function is a metric that evaluates how good an individual is in terms of what we are optimizing for. In the classic genetic algorithm example of binary strings, the task is to produce the same binary string as the target. An adequate fitness function might count how many bits in a given string have the same value as the target. In this case, a higher fitness function is a string that is “more fit” and closer to the optimal value.
Selection Criteria
The selection criteria determines which individuals from the population are chosen to be parents for the next generation. Typically, we want to select individuals with stronger fitness. However, if we only select individuals with the best fitness, we will lose biodiversity over time. We want to maintain a certain level of “stochasticity” within each population to avoid falling into local minima. To do this, the classic approach to selecting parents is via tournament selection. In essence, X individuals are selected at random from the total population and the most fit individual from those X tournament participants is chosen to be the parent. We can see that the lower X is, the more stochasticity and biodiversity we introduce into our selection of parents.
Finding the optimal balance between selecting generally more fit individuals while also maintaining a diverse set of parents is one of the challenging but fun aspects of genetic algorithms.
Crossover
The crossover methods determines how offspring are created once we have selected parents. Typically two parents are chosen to create offspring. The crossover function aims to combine attributes of both parents in a way that creates a child with a better fitness. A popular method is to simply to take the first half of parent(1) and combine it with the second half of parent(2). A random “crossover point” can also be used, meaning that parent(1)’s genes are used until the crossover point and then parent(2)’s genes are used after the crossover point. Regardless of how crossover is implemented, the hope is that the child will incorporate elements of both parents and have a higher fitness.
Mutations
Mutations are relatively low probability operations that slightly alter an offspring. The purpose of mutations are to introduce stochasticity, which can help combat local optima.
Given these components, a genetic algorithm seeds an initial population and then uses selection criteria to select higher fitness parents which will crossover and potentially mutate into the next generation. We can repeat the process of creating future generations for a set number of generations or until an optimal solution is achieved.
Now that we have introduced a genetic algorithm, we can dive into my genetic algorithm that seeks to recreate an image!
Initial Population
My target is an image, so my initial population consists of randomly generated images. However, how you create “random images” is critical to how your population will develop.
Previous Research
Previous attempts have used random RGB values for every single pixel but result in highly pixelated outputs [1]. The example below illustrates the results of this approach. The source code can be found here.
My Approach
To deviate away from this pixelated effect, I seeded my initial population with images using the following qualities:
- Random background color
- Random number of polygons each with random color
Here is an example of what some of the individuals in my initial population look like.
By creating my initial population like this, I provide enough stochasticity without overdoing it. I believe that the previous approach using pure noise results in an output looking like a highly pixelated version of the target. Remember, your final output will be some amalgamation of what was in your initial population. Therefore, starting with pure noise will result in some combination of pure noise at the end. However, by starting with relatively “solid images,” I hope to provide a foundational canvas for my genetic algorithm to work with.
Fitness Function
With the purpose of approximating an image, our fitness function will evaluate pixel-wise similarity between the current individual and the target. I tested 2 main ways to calculate pixel-wise similarly between two images.
Fitness Function Approach 1 — Euclidean Distance
To me, the most obvious approach would be to compare the pixel-wise RGB value difference between the current image and the target image. We can think of RGB as a 3 dimensional space (one for each color channel). Therefore, this approach calculates the euclidean distance two pixels. Whether to take the total sum or the average across the entire image given each pixel’s difference gave me pretty similar results during my experimentation.
In some of my experiments, I was getting individuals that mostly resembled the target but contained certain subsections that were way off. In an effort to reduce this effect, I used the square of the euclidean distance to exponentially punish pixels that are way off but this didn’t seem to help overall.
Although this is a straightforward and relatively robust fitness function, I realized that there was one major flaw with this fitness function as I continued my experimentation. The difference in color measured by Euclidean distance is not an accurate portrayal of how our eyes perceive the difference between two colors!
It turns out, how to measure color difference in a way that reflects human optical perception has been rigorously researched! By taking a foray into this research field, I landed upon my second fitness function.
Fitness Function Approach 2 — Delta E
The second approach I implemented leverages Delta E, a color difference metric that models the human eye, and is considered the standard measurement tool. It was devised by the International Commission on Illumination in the late 1900s. For an interesting read on how it works and further information, refer here. My results using Delta E significantly outperformed Euclidean distance from a visual perspective. Both were able to create results that resembled the target image, but Delta E’s results had less subsections of the image that were wildly off.
There is a Python library called Colour that can compute the Delta E distance between the pixels from two images, which is what I used in my implementation.
Selection
I implemented selection through a tournament. I tested various tournament sizes, randomly sampling between 3%-10% of the total population to participate in each tournament. The winner of each tournament was the individual with the best fitness.
There is a trade-off between increasing the size of the tournament and the diversity of parents chosen for reproduction.
The larger the tournament, the higher the likelihood of selecting one of the most fit individuals in the population. However, future tournaments will likely include the most fit individuals over and over, which decreases the diversity of the parents for future generations. On the other hand, if our tournament size is too small, then the winners of the tournament may be “weak” and not reflect the strongest individuals in the population.
In my experiments, a tournament size of 8% of the total population seemed to perform best.
Crossover
I implemented 3 unique crossover functions and incorporated a probabilistic blend of all 3 into my final genetic algorithm. Below, I describe each crossover function and give an example.
Crossover Function Approach 1 — Blend
In this approach, we assign opacity x to parent(1) and assign opacity 1-x to parent(2). Then we overlay both of them to create the child. If is x is 0, a copy of parent(1) is produced. If x is 1, a copy of parent(2) is produced.
To determine x, I sample a uniform distribution with lower bound 0 and upper bound 1. One advantage of not fixing x = 0.5 is that this introduces stochasticity to the crossover function and can produce different children given the same parents.
Crossover Function Approach 2— Crossover Point
In this approach, we select a random row or column to be a crossover point. Everything up until that row or column is from Parent(1) and everything including and after that row or column is from Parent(2). Once again, this row or column is selected from a uniform distribution.
I assigned an equal chance for Crossover 2 to be done horizontally or vertically. It would be interesting to test diagonal crossover lines but for my experiments, I only used horizontal or vertical crossovers.
Crossover Function Approach 3 — Pixel-wise
In this approach, each pixel in the child is selected randomly from either parent(1) or parent(2). This technique performs well but ends up creating images that look granulated. As a result, I used this crossover function with a very low probability in my final genetic algorithm.
Combined Approach
In the runs that performed the best, I utilized a probabilistic combination of the previous 3 crossover functions. My experiments seem to indicate the following breakdown to perform best:
- 60% chance for crossover 1 (Blend)
- 35% chance for crossover 2 (Crossover Point)
- 5% chance for crossover 3 (Pixel-wise)
Mutation
I created 2 separate mutation functions to slightly modify a child individual.
Mutation Approach 1 — Adding a random shape of random color
To perform this mutation, I superimpose a random shape of random color onto the original child
Mutation Approach 2 — Adding a constant to a subset of pixels
To perform this mutation, I randomly select a subset of X pixels and add a random constant to each of those selected pixels. The effects of this mutation function tend to be more subtle than the first.
Combined Approach
I typically assigned a mutation with a probability of around 5%. Within that 5%, I split it about even between whether mutation 1 or mutation 2 would be used.
Experimentation
Putting all the elements described above, we have a functioning genetic algorithm. What remained is to experiment with different hyperparameters. Particularly, here are the variables that I tested:
- Initial Population
- Size of the initial population
- The lower and upper bound on the number of random shapes - Fitness Function
- Visually comparing the results from both types - Selection
- Altering the size of a tournament - Crossover
- Different probabilistic combinations - Mutation
- Varying the probability of a mutation occurring
- Changing the probability of using mutation 1 versus mutation 2
Access my GitHub repository to see the full code and experiment with images of your own!
Results
I was quite pleased with the level of detail I was able to achieve with my genetic algorithm. It is almost possible to see some details in the left eye of my output image. Although this output has the semblances of the target image, it is not quite perfect.
By graphing the average Delta_E vs. generation, it seems that my genetic algorithm has an asymptote around 15.5. Because I am using the Delta_E fitness function, which has a range of 0 to 100.
Unfortunately, my genetic algorithm seems to reach an asymptote around a fitness of 15.5. Ideally we would like the genetic algorithm to reach a fitness of 0 in the long run. However, we were still able to achieve a result that visually resembles a target image!
References
[1] https://heartbeat.comet.ml/reproducing-images-using-a-genetic-algorithm-with-python-91fc701ff84
[2] https://github.com/TyperOfCode/image_algorithm
[3] https://cosmiccoding.com.au/tutorials/genetic_part_two/
[4] https://github.com/SebastianCharmot/Genetic-Algorithm-Image-Recreation
