# IMAGE_MATCH_GENETIC Approximate an Image Using a Genetic Algorithm

IMAGE_MATCH_GENETIC, a MATLAB program which approximates a 256x256 JPG image by blending just 32 rectangles of arbitrary position and color, using ideas from genetic algorithms, based on an example by Nick Berry.

In Nick Berry's example, he started with a 256x256 RGB image of himself. He considered the problem of reconstructing this image using 32 rectangles, each having an RGB color, and each having an arbitrary location. Thus, an attempt to approximate the original image can be described by 32 pieces of information, each of which involves 7 data items, namely 3 colors, and 4 coordinate values, that is, the locations of the lower left and upper right corners of the rectangle.

Because the X and Y ranges of our image are 0 to 255, and our RGB ranges are also 0 to 255, each of our 7 data items can be described by an 8 bit binary integer. So we can imagine that we can describe an approximate solution using 32 x 7 * 8 bits of information.

We might refer to an approximate solution as a "candidate", or the solution's "DNA". We might refer to the information describing a single rectangle as a "chromosome", and the 7 data items as "genes". Then the 8 bits in a gene are the fundamental items of genetic information.

A genetic algorithm tries to solve the image matching problem by starting with a random population of 10 sets of DNA. A fitness function is used to identify the best and worst DNA. In our case, this fitness function might simply be the sum of the differences between the original and approximate RGB images.

We then modify our population by:

• death, the two worst candidates are discarded;
• mutations, one of the intermediate candidates has a single genetic bit flipped.
• crossover, the two best candidates are crossed, creating two children whose DNA is a mix of that of the two parents's.
The new population is evaluated for fitness, and the modification process is repeated many times, in the hope that approximations of increasing fitness will be discovered.

### Languages:

IMAGE_MATCH_GENETIC is available in a MATLAB version.

### Related Data and Programs:

• IMAGE_BOUNDARY, a MATLAB library which reports the pixels which form the boundary between the black and white regions of a simple image.
• IMAGE_COMPONENTS, a MATLAB library which seeks the connected "nonzero" or "nonblack" components of an image or integer vector, array or 3D block.

IMAGE_CONTRAST, a MATLAB program which applies image processing techniques to increase the contrast in an image.

IMAGE_DECIMATE, a MATLAB library which compresses an image by dropping the even rows and columns of data.

IMAGE_DENOISE, MATLAB programs which apply image processing techniques to remove noise from an image.

IMAGE_DIFFUSE, a MATLAB library which uses diffusion to smooth out an image.

IMAGE_DOUBLE, a MATLAB library which doubles the height and width of an image by repeating each row and column.

IMAGE_EDGE, a MATLAB library which demonstrates a simple procedure for edge detection in images.

IMAGE_QUANTIZATION, a MATLAB library which demonstrates how the KMEANS algorithm can be used to reduce the number of colors or shades of gray in an image.

IMAGE_RGB_TO_GRAY, MATLAB programs which makes a grayscale version of an RGB image.

IMAGE_THRESHOLD, MATLAB programs which make a black and white version of a grayscale image by setting all pixels below or above a threshold value to black or white.

SIMPLE_GA, a C++ program which a simple example of a genetic algorithm, by Dennis Cormier and Sita Raghavan.

### Reference:

1. Nick Berry,
A "Practical" Use for Genetic Programming,
http://www.datagenetics.com/blog.html
2. Zbigniew Michalewicz,
Genetic Algorithms + Data Structures = Evolution Programs,
Third Edition,
Springer, 1996,
ISBN: 3-540-60676-9,
LC: QA76.618.M53.

### Source Code:

Last revised on 24 January 2013.