ng
9).
ch
Zhaobao Zheng
points known as a population in order to maximize some desirable criterion. Also, the GA, as a stochastic random
search technique, is known to use the accumu lating information to prune the search space, while a purely random search
ignores information about the environment.
The GA is an iterative procedure with a parallel test-and-go technique, which maintains a finite set of representations
for solving a given problem. During each iteration step, known as generation, each individual is evaluated and
recombined with others on the basis of its overall quality or fitness. Each individual is represented as a chromosome
encoded as a string of genes which may take one of several values or alleles.
Some recent attempts in applying the genetic dgorithms for machine vision problems(B.Bhanu/1989, G.Roth and
M.D.Levine/1991) such as image segmentation, primitive extraction, scene recognition and image interpretation are
reported in the literature. Bhanu, Lee and Ming proposed a learning technique for the image segmentation using the GA.
The algorithm allows the segmentation process to adapt to image characteristics affected by the variable environmental
conditions such as time of day, clouds, rain, etc. Also in handling uncertainty in pattern analysis, Pal reported a
necessity of a fuzzy fitness function.
Recently, research of GA has focused on three operators such as reproduction, crossover and mutation. Reproduction is
a process in which individual strings are copied according to their objective function as some measure of goodness we
want to maximize. The crossover involves exchanging elements from mating of two parent chromosomes to create one
or nore child chrompsomes. The crossover is implemented by randomly choosing a point in the string called the
crossover point and exchanging the segments. There are various crossover mechanisms that have been developed to be
efficiently applied to applications, for instance, cycle crossover, order crossover, position based crossover, partially
mapped crossover and so on. The mutation process creates new individuals by modifying one or more bit strings. The
operator increases the variability of the population and prevents premature convergence to a poor local minimum. One
of the interesting aspects in designing a genetic algorithm is to invent operators that construct the new potential
solutions.
In this paper we apply the GA to search optimal parameters of the MRF for image classification. To do so, we design
the crossover and the mutation mechanism for solving MRF parameters, as well as an encoding scheme of the
chromosome for representing the mask. However, the basic procedure of GA is based on the Simple Genetic Algorithm
(SGA). We describe the detailed mechanism in next sections.
2.2 The Genetic Algorithm for the Decision of the Optimal Parameters in MRF
MRF is an important statistic model to analyze textures. It regards texture as the reflection of statistic features of pixel
gray value. In the MRF, each pixel is named a texture primitive. Different statistic regulations of texture primitives
reflects different texture features. These statistic regulations can be described by MRF parameters whose values reflect
the relation between the neighbor and its central pixel(Zhaobao Zheng /1997). The relation can be expressed as
(Kashhyep R.L /1981 ):
y(s)= > br* y(s+ r)+n(s) (1)
reh
Where y(s) is the gray of a central pixel ,Gis the set of neighbors of the central pixel; y(s+r) is the gray of a neighbor
pixel of y (s); ris the distance radius ; b, is a MRF parameter ;v(s) is Gaussian noise or called residuals ; s U , Uis the
size of a textured image, and the average of y(s) is zero. Eq.1 can be transformed as following error equation:
-n(s)s W bet ys *r)-»() (2)
reh
For a five-order MRF which is shown in Fig.1, there are 24 neighbor pixels around a center pixel. As a result, there are
24 unknown parameters in Eq.2.
Lil ge led
International Archives of Photogrammetry and Remote Sensing. Vol, XXXIII, Part B3. Amsterdam 2000. 1049