In: Paparoditis N., Pierrot-Deseilligny M.. Mallet C.. Tournaire O. (Eds). 1APRS. Vol. XXXVIII. Part 3A - Saint-Mandé, France. September 1-3. 2010 
289 
A 
(c) (d) 
Figure 2: 1826-th image of CD3 sequence, (a) Original image, 
(b) Red colour-extraction image, (c) Edge-extraction image, (d) 
Distance transform image of image (b). 
This error measure must match ever}' point of {5} with clos 
est point of {D}. Fitzgibbon in (Fitzgibbon. 2003) proposes a 
method to improve the ICP algorithm. This algorithm is an iter 
ative method to calculate the new configuration using a Newton- 
Gauss algorithm. For a deformable template P defined as a set of 
points, we define, with respect to a configuration vector a and an 
image I composed by a class Iq, the error function : 
after 30 iterations 
after 1 iteration 
after 40 iterations 
Figure 3: Different steps of ICP algorithm. In blue, initial posi 
tion of the triangle template, in red the different position of the 
template after 1, 30 et 40 iterations. 
mean square optimization can then be written as : 
N 
/(a) = (*K a ’ Xi ) ~ y*) 2 ( 9 ) 
?.=i 
Back indicates that the general scheme of an evolutionary algo 
rithm for an initial population Po is : 
• Initialize a population Po(0) = {ai (0),..., a M (0)} 
• Evaluate Po(0) w.r.t its environment 
E(PP a)= £ 
pePa 
min 
3€/o 
lk-p|| 2 
Dj2 (p) 
p€Pa 
(6) 
Fitzgibbon shows that the new configuration a + da minimizes 
this error function and gives the relation : 
da = — (J # J) _1 J # e (7) 
Where J represents Jacobian matrix of the residuals vector equal 
toe(/,P.a) = (P;(pi(a))...D/(piv(a))) i . The calculation 
time to estimate Jacobian matrix would be prohibitive even if we 
are not interested in real time processing. However, Fitzgibbon 
describes a method to improve the Jacobian matrix calculation in 
image processing which is based on Distance Transform. 
j = {■>«} 
(8) 
See (Fitzgibbon. 2003) for full details. Figure 3 shows an exam 
ple of the convergence step. 
3.5 Evolutionary algorithm 
Evolutionary algorithms represent several families of algorithms 
such evolution strategy (ES), genetic algorithms (GA) and differ 
ential evolution algorithms. A reference application is often cited 
when we deal with EA : the travelling salesman problem con 
sists in finding the shorter path we have to follow in the case we 
have to pass through N knots. However, Thomas Bäck reminds 
us in (Bäck. 1996) that the EA is primarily an algorithm used in 
optimization problems and proposes a simple example : let con 
sider a parameters vector a e R n , an observable set of points 
{{rri, t/i),..., (xn, Vn)}, and assume the existance of estima 
tor y(a,x) to describe the relation between and x % - The least 
• While i (Po(t)) 7^ true do : 
1. Recombine a new population from previous one 
2. Mutate the population 
3. Evaluate every individual 
4. Select best individuals 
5. t «- t + 1 
We see here that t function is a termination criterion. Generally, 
this condition is based on the evaluation function which gives ev 
ery individual a kind of adaptability score with respect to the en 
vironment. We note the analogy with the previous ICP algorithm 
in research of minimizing error on every iteration. 
4 HYBRID ALGORITHM 
Considering (Siarry, 2007), (Mignotte et al., 2000) or (De La Es 
calera et al.. 2004), we can see that biological metaheuristics are 
efficient for shape recognition in image processing. We here pro 
pose a fusion of an ES and deterministic approach based on a 
local ICP algorithm, along with the combination of two different 
primitives, colour and edge, to improve the quality of conver 
gence. The deterministic approach improves quality and conver 
gence speed, while ES helps avoiding local minima. 
4.1 Termination criterion 
The termination criterion is based on a maximum number of iter 
ation and on a score which represents the quality of an individual 
w.r.t a configuration in an image. As shown in (Siarry, 2007), the 
edge-based score is more discriminating than the region-based