Genetic Programming Based Morphological Image Analysis Algorithm
1 Definition
By giving an original image and a learning target--- goal image, this algorithm is designed to use a GP approach to automatically produce a sequence of mathematic morphological operations, which are applied to the original image to obtain result close to the goal. In this algorithm, a chromosome is an individual, which is composed by a sequence of genes.
This algorithm initiates 1024 chromosomes at the beginning which are all single genes, and evolves for 300 generations to output the best individual. One single gene is a primitive unit of morphological operation accompanied with logical operations.
The number of genes in each chromosome may be different while each gene has a fixed length, and the max length is limited to 20 genes. Two processing sequences are kept in each chromosome, which are mutually affected by logical operations. The objective fitness function is the correlation coefficient between a processed image and the goal.
The direct/difference flag means to choose the morphological operation result directly or the arithmetic difference between it with the input as the current output. The storage flag means whether the result of this gene should be stored or not. The logical operator flag represents which logical operation will be applied to the current gene. Four logical operations are defined in this algorithm, AND, OR, NOT and XOR. Some logical operations need two operands. One operand is the current morphological operation result, and the other one is the storage mentioned above.
A new operation switch is brought forward. If the switch flag is true, the input of the current gene is substituted by the backup one. By the combination of switch and store, two operation processes are expressed in one chromosome.
Only basic morphological operations erosion and dilation are used in this algorithm, which depend on the pattern of structuring element (SE). Three sizes of SEs are defined as 3 x 3, 5 x 5 and 7 x 7 in this algorithm. Each size has two styles, regular--- SEs are symmetrical and irregular--- asymmetrical, and each style has 16 patterns.
2 Evolution strategy
A structural evolution strategy is brought forward:
Structural mutation--- a gene is divided into three parts, flow control, logical operation and morphological operation, which are mutated separately, and the mutation position is well-distributed;
Structural crossover --- the basic unit of crossover is a gene, and a crossover in the middle of a gene is not allowed.
3 Experiment on binary images
We use an artificial data set composed by four features: squares, circles, rings and stars, and use this algorithm to obtain valid objects.
This algorithm was trained on a small area of source image, and four operation sequences were produced to extract the four features separately.
The heavy computation load of Quintana's algorithm needed a cluster with 23 nodes in his experiments, while our algorithm finished the work on a PC workstation in a few minutes.
Executing these sequences on the whole image, the average fitness values of obtained features were compared with Quintana's.
This algorithm was also applied to an OCR music sheet, which had been used by Yoda to extract the four features: heads, hooks, staff lines and stems.
In the training progress of heads detection, Yoda got the final fitness value of 0.963, and our algorithm got a more accurate value of 0.966.
4 Experiment on gray scale images
This algorithm was applied to the enhancement of gray scale image on a dataset which had more than 2000 low quality finger vein images.
Four images were chosen from the data set randomly as learning samples, and the corresponding feature images were calibrated manually as learning goals.
This algorithm run with the learning sets and produced four operation sequences. An uniform threshold and a thinning method were adopted to get the skeleton feature results of the gray scale image. Results are shown in figure: (a) four learning samples; (b) corresponding goals; (c) learning results with a threshold and thinning; (d) threshold and thinning results of (a).
The images of the dataset were processed with combination of different numbers and orders of obtained operation sequences. The effect of the enhancement was measured by testing the false acceptance rate (FAR) of the identity authentication. Group 1 is the FAR result of the contrastive method, and the others are results of combinations of operation sequences. The Group 2 shows the best performance, which reduces the FAR by about 8%.
