Genetic Algorithm for Image Approximation with Overlaid Image Instance

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

Put that way it is simply a search problem, and a hopeless one, since the space of possible arrangements is far larger than anything we could enumerate. Biology’s answer to a space that size is a great many attempts and no sentiment whatever about which of them continue.

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.

An enormous starling murmuration wheeling over a marsh at sunset, painted in the old-master manner — As a pictorial example, one likes to imagine something up there is deciding the shape. Nothing is. In some sense, each bird only watches its nearest set of neighbours, and the figure over the marsh is what a few thousand local decisions look like from the ground in aggregate; point is, a population of two hundred and sixty candidate images behaves not much differently.

Results

Below is what all that bookkeeping looks like after a hundred and twenty thousand rounds of it.

Mona Lisa after 120'000 generations approximated with 260 individuals.

GitHub Repository with the code

Cite this article

If this was of any use, the kindest citation is telling someone about it; the entry below covers the less kind occasions.

@article{serifovic2016genetic,
  author  = {Serifovic, Muriz},
  title   = {Genetic Algorithm for Image Approximation with Overlaid Image Instance},
  journal = {muriz.ch},
  year    = {2016},
  month   = {October},
  note    = {https://muriz.ch/blog/genetic-algorithm.html},
}

Moths, Caterpillars & Pupa · The Naturalist’s Library, vol. XXXIII