Genetic Algorithm for Self-Referential Image Approximation
Muriz Serifovic
2016-10-14
Introduction
We propose an approach to solve the image matching problem with some stochastic
optimization approach, in which the search for the optimal solution involves randomness in some constructive way.
If $\mathcal{S}$ denotes the (finite) set of all possible solutions, the task we consider is to maximize or minimize the objective function $f : \mathcal{S} \rightarrow \mathbb{R}$.
In the case of maximization, on which we focus here, the problem is to find a configuration $x_{o p t} \in \mathcal{S}$ which satisfies
$$
f\left(x_{o p t}\right) \geq f(x) \text { for all } x \in \mathcal{S}.
$$
Genetic Algorithm
Genetic algorithms operate on a set of individuals (solutions) which form a population for a determined generation, then either two individuals are selected and combined in a crossover operation or each individual is mutated.
We might refer to an approximate solution as a "candidate", or the solution's "DNA".
A genetic algorithm tries to solve the image matching problem by starting with a random population of 260 sets of DNA consisting in form of genes with a length of 5. A fitness function is used to identify the best and worst DNA. To get a measure of how similar two images are, we calculate the root-mean-square error (RMSE) value of the difference between the images. If the images are exactly identical, this value is zero.
RMSE is defined as
$$
\mathrm{RMSE}=\sqrt{\frac{1}{n} \sum_{j=1}^{n}\left(y_{j}-\hat{y}_{j}\right)^{2}}.
$$
Crossover and mutations are randomly performed in order to generate new solutions. Then, based on a selection criterion, the strongest individuals (those with the best value of a performance metric) survive and remain for the next generation.
The process is repeated until some stopping conditions are fulfilled. In order to perform the selection of the individuals in the GA a fitness value needs to be defined. This fitness value measures the quality of the individuals and enables them to be compared.
Results
Left: Cropped version of Leonardo da Vinci, Mona Lisa, c. 1503-19, oil on panel 30-1/4 x 21″ (Musée du Louvre); Right: Approximation with the genetic algorithm.
Mona Lisa after 120'000 generations approximated with 260 individuals.
