Page 48 - Fister jr., Iztok, and Andrej Brodnik (eds.). StuCoSReC. Proceedings of the 2015 2nd Student Computer Science Research Conference. Koper: University of Primorska Press, 2015
P. 48
iance. For a bilevel thresholding problem is this formally r1, r2 and r3. indexes are mutually different and differ-
defined as: ent from i. They are selected uniformly within the range
{1, 2, ..., N p}. The scale factor F is defined within the range
σB2 (t∗) = max σB2 (t), (1) [0, 2]. The mutant vector mi is obtained by adding a scaled
vector difference to a third vector.
1≤t≤L
The trial vector ti is then generated using the crossover rate
where Cr and a corresponding vector xi from the population as:
σB2 = ω0ω1(µ1 − µ0)2, (2)
with ω0 and ω1 being probabilities of class occurrence and
µ0 and µ1 the mean values of each class.
This problem is easily expandable to a multilevel problem ti,j = mi,j if rand(0, 1) ≤ Cr or j = jrand, (8)
as: xi,j otherwise.
σB2 (t1∗, t∗2 , ..., t∗n−1 ) = max σB2 (t1, t2, ..., tn) As can be seen from Eq. 8, the crossover rate Cr is defined
at the interval [0, 1] and it defines the probability of creating
1≤t1 ble for the trial vector to contain at least one value from the
(3) mutant vector. After crossover, some values of the vector
may fall out of bounds, which means that these values must
4. EVOLUTIONARY ALGORITHM be mapped back to the defined search space.
An evolutionary algorithm is a generic population-based op- The next step in the evolutionary process is the selection of
timization algorithm. It uses mechanisms which are inspired the fittest individuals. During the selection process the trial
by biological evolution, such as reproduction, mutation, re- vector ui, competes with vector xi from the population. The
combination, and selection. The solutions for the optimiza- one with the better fitness value survives and is transfered
tion problems are the individuals in the population, and the to the next generation.
fitness function provides a metric for measuring the qual-
ity of the solutions. In this paper an EA called differential 5. RESULTS
evolution (DE) has been used for optimal multilevel thresh-
olding. Hereinafter the DE algorithm will be described in In this section, the obtained results are presented, and also
detail. the experimental environment is described.
4.1 Differential Evolution 5.1 Experimental environment
Differential evolution (DE) [6] is a population based opti- For the purpose of this study 4 gray scale standard test
mization algorithm used for global optimization. It is sim- images were taken form literature. All images are of same
ple, yet very effective in solving various real life problems. size (512 × 512 pixels) and in uncompressed format. All
The idea of DE is a simple mathematical model, which is images are presented in Figure 1. For evaluating the quality
based on vector differences. of the results during the evolution, the Otsu criterion for
multilevel thresholding has been used (see Section 3).
The population of the DE algorithm consists of N p individ-
uals xi, where i = 1, 2, ..., N p, and each vector consists of All experiments were conducted with the following number
D-dimensional floating-point encoded values xi = {xi,1, xi,2, of thresholds: 5, 8, 10, 12, and 15. The algorithm was coded
xi,1, ..., xi,D}. In the evolutionary process, individuals are in C++.
evolved using crossover, mutation and selection operators,
which are controled by a scale factor F and crossover rate 5.2 Image quality assessment
Cr. The following mutation strategies were considered in
this paper: For evaluating the segmentation quality the well established
peak-signal-to-noise ratio metric has been used. It gives the
• ”rand/1”: similarity of an image against a reference image based on
the MSE of each pixel. It is defined as follows:
vgi = xrg1 + F (xrg2 − xgr3) (4)
(5)
• ”best/1” : (6)
(7)
vgi = xbgest + F (xgr1 − xrg2)
• ”current to best/1” : 2552 (9)
vgi = xig + F (xgbest − xig) + F (xgr1 − xgr2) P SN R = 10 log10 M SE
• ”rand to best/1” : MSE = 1 MN (10)
vgi = xgr1 + F (xbgest − xrg1) + F (xrg2 − xrg3) MN
[I(i, j)) − J(i, j)]2
i=1 j=1
For the creation of a mutant vector mi, three random vec- where I and J are the original and segmented images respec-
tors from the population are selected, defined by indexes tively.
StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference 48
Ljubljana, Slovenia, 6 October
defined as: ent from i. They are selected uniformly within the range
{1, 2, ..., N p}. The scale factor F is defined within the range
σB2 (t∗) = max σB2 (t), (1) [0, 2]. The mutant vector mi is obtained by adding a scaled
vector difference to a third vector.
1≤t≤L
The trial vector ti is then generated using the crossover rate
where Cr and a corresponding vector xi from the population as:
σB2 = ω0ω1(µ1 − µ0)2, (2)
with ω0 and ω1 being probabilities of class occurrence and
µ0 and µ1 the mean values of each class.
This problem is easily expandable to a multilevel problem ti,j = mi,j if rand(0, 1) ≤ Cr or j = jrand, (8)
as: xi,j otherwise.
σB2 (t1∗, t∗2 , ..., t∗n−1 ) = max σB2 (t1, t2, ..., tn) As can be seen from Eq. 8, the crossover rate Cr is defined
at the interval [0, 1] and it defines the probability of creating
1≤t1
(3) mutant vector. After crossover, some values of the vector
may fall out of bounds, which means that these values must
4. EVOLUTIONARY ALGORITHM be mapped back to the defined search space.
An evolutionary algorithm is a generic population-based op- The next step in the evolutionary process is the selection of
timization algorithm. It uses mechanisms which are inspired the fittest individuals. During the selection process the trial
by biological evolution, such as reproduction, mutation, re- vector ui, competes with vector xi from the population. The
combination, and selection. The solutions for the optimiza- one with the better fitness value survives and is transfered
tion problems are the individuals in the population, and the to the next generation.
fitness function provides a metric for measuring the qual-
ity of the solutions. In this paper an EA called differential 5. RESULTS
evolution (DE) has been used for optimal multilevel thresh-
olding. Hereinafter the DE algorithm will be described in In this section, the obtained results are presented, and also
detail. the experimental environment is described.
4.1 Differential Evolution 5.1 Experimental environment
Differential evolution (DE) [6] is a population based opti- For the purpose of this study 4 gray scale standard test
mization algorithm used for global optimization. It is sim- images were taken form literature. All images are of same
ple, yet very effective in solving various real life problems. size (512 × 512 pixels) and in uncompressed format. All
The idea of DE is a simple mathematical model, which is images are presented in Figure 1. For evaluating the quality
based on vector differences. of the results during the evolution, the Otsu criterion for
multilevel thresholding has been used (see Section 3).
The population of the DE algorithm consists of N p individ-
uals xi, where i = 1, 2, ..., N p, and each vector consists of All experiments were conducted with the following number
D-dimensional floating-point encoded values xi = {xi,1, xi,2, of thresholds: 5, 8, 10, 12, and 15. The algorithm was coded
xi,1, ..., xi,D}. In the evolutionary process, individuals are in C++.
evolved using crossover, mutation and selection operators,
which are controled by a scale factor F and crossover rate 5.2 Image quality assessment
Cr. The following mutation strategies were considered in
this paper: For evaluating the segmentation quality the well established
peak-signal-to-noise ratio metric has been used. It gives the
• ”rand/1”: similarity of an image against a reference image based on
the MSE of each pixel. It is defined as follows:
vgi = xrg1 + F (xrg2 − xgr3) (4)
(5)
• ”best/1” : (6)
(7)
vgi = xbgest + F (xgr1 − xrg2)
• ”current to best/1” : 2552 (9)
vgi = xig + F (xgbest − xig) + F (xgr1 − xgr2) P SN R = 10 log10 M SE
• ”rand to best/1” : MSE = 1 MN (10)
vgi = xgr1 + F (xbgest − xrg1) + F (xrg2 − xrg3) MN
[I(i, j)) − J(i, j)]2
i=1 j=1
For the creation of a mutant vector mi, three random vec- where I and J are the original and segmented images respec-
tors from the population are selected, defined by indexes tively.
StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference 48
Ljubljana, Slovenia, 6 October
