Stereo matching using genetic algorithm

Question

I have been reading a few papers (paper1, paper2) on stereo matching using genetic algorithms. I understand how genetic algorithms work in general and how stereo matching works, but I do not understand how genetic algorithms are used in stereo matching.

The first paper by Han et al says that "1) individual is a disparity set, 2) a chromosome has a 2D structure for handling image signals efficiently, and 3) a fitness function is composed of certain constraints which are commonly used in stereo matching".

Does it mean that an individual is a disparity map with random numbers? Then a chromosome is a block within the individual's disparity map. The constraint used for fitness function could be the famous epipolar line.

I dont seem to understand how this works and even WHY you should use genetic algorithm on an algorithm that at its simplest form uses 5 for loops, for example, like in here.

Answer 1

Do not understand how genetic algorithms are used in stereo matching.

The first paper referenced in the question is Stereo matching using genetic algorithm with adaptive chromosomes, Kyu-Phil Han, Kun-Woen Song, Eui-Yoon Chung, Seok-Je Cho, Yeong-HoHac, 2000. It summarizes an approach this way.

1. An individual is a disparity set,

2. A chromosome has a 2D structure for handling image signals efficiently, and

3. A fitness function is composed of certain constraints which are commonly used in stereo matching.

The paper also states, "Genetic algorithms are efficient search methods based on principles of population genetics, i.e. mating, chromosome crossover, gene mutation, and natural selection." The extension to genetic algorithm purity is contained in this statement in the paper.

To improve the convergence, an informed generation, that a higher selected possibility is assigned to the chromosome including a smaller intensity difference, is adopted. The informed generation uses several random generations plus a selection. In a random generation, only a value is randomly generated. Yet, the informed generation of the proposed algorithm selects the gene which has the minimum intensity difference among the randomly generated genes.

The question inquires along a few lines.

Does it mean that an individual is a disparity map with random numbers?

The goal is to produce order from chaos through successive mutations, combinations, and tests, arriving at genetic code that represents distances of objects that correspond to a left region of pixels and a right region of pixels. Those two regions are identified through alignment of brightness categories, with some permissible sprinkling of outliers.

An individual in this context is a simulation of a sample from a population with a particular aggregation of genetic codes. The codes indicate disparity between matching image features in the left and right images, measured in horizontal pixels.

[Don't] understand how this works and even WHY you should use genetic algorithm on an algorithm that at its simplest form uses 5 for loops.

The five loops referenced in the question, in the source at github.com/davechristian/Simple-SSD-Stereo, are as follows.

for y in range(kernel_half, h - kernel_half):
    for x in range(kernel_half, w - kernel_half):
        for offset in range(max_offset):
            for v in range(-kernel_half, kernel_half):
                for u in range(-kernel_half, kernel_half):

This exhaustive search has gross shortcomings in relation to the genetic algorithm with informed generation.

• The simulation of meiosis in genetic algorithms is essentially a search for hybrids where the best genetic sequences of two parents are preserved in the offspring.

• Genetic algorithms are easy to scale across computer clusters without developing specialized hardware acceleration.

• Components of failed compositions are not eliminated in an exhaustive search, so there is considerable redundancy in trials.

The second paper referenced in the question is Genetic Stereo Matching Algorithm with Fuzzy Fitness, Haythem Ghazouani, 2014. It proposes, "To get around [convergence speed] limitations, we propose a new encoding for individuals, more compact than binary encoding and requiring much less space. This approach and the use of three lightness classes is shared with the methodology of the first paper.

This second paper introduces fuzzy matching and the use of the Sobel gradient norms to penalize (dismiss) pixels which project onto uniform regions, [and are therefore] less significant pixels. This paper also provides some comparison results with Han's, Dong's, and Nguyen's algorithms as define in the second paper's bibliography.

Answer 2

This is what I understood so far from the paper in arxiv named "Genetic Stereo Matching Algorithm with Fuzzy Fitness":

Let's say we have 2 images (left and right taken by a stereo camera) of size 28x28. The images are in grey scale.

The individual becomes a disparity map. Let's say, we look at the pixel at row 2, column 3 and it has a number 5. That means that the pixel at (2,3) on the left image (reference image) corresponds to the pixel at (2, 8) on the right image (target image).

The author of the paper created three classes black, average, and white pixels classes where they take the 0, 127.5, and 255 values respectively in the grey image scale.

Then the author calculates the likelikehood of each pixel on both left and right images belonging to the same class by calculating the mean and standard deviation of the class in consideration.

The matching possibility metric is calculated by choosing the max likelikehood of both images belonging to the same class.

Author also added Sobel gradient normalization to the fitness value.

Genetic operators seem to work in an easy way where you just swap some parts of the individual (disparity map) with another disparity map to create new individuals and the mutation is just randomly changing the number in the disparity map.