Applied Mechanics and Materials Online: 2012-10-26

ISSN: 1662-7482, Vol. 203, pp 88-93

doi:10.4028/www.scientific.net/AMM.203.88
© 2012 Trans Tech Publications, Switzerland

Image Matching Using a Bat Algorithm with Mutation

Jiawei Zhang1,a and Gaige Wang2,3,b,*
1
School of Mathematics, Jilin University, Changchun 130012, China;
2
Changchun Institute of Optics, Fine Mechanics and Physics, Chinese Academy of Sciences,
Changchun 130033, China;
3
Graduate School of Chinese Academy of Sciences, Beijing 100039, China
a
zhangjw90@yahoo.com.cn, bggw0122@163.com

Keywords: image matching; differential evolution (DE); bat algorithm (BA)

Abstract. Due to shortcoming of traditional image matching for computing the fitness for every
pixel in the searching space, a new bat algorithm with mutation (BAM) is proposed to solve image
matching problem, and a modification is applied to mutate between bats during the process of the
new solutions updating. This new approach can accelerate the global convergence speed while
preserving the strong robustness of the basic BA. The realization procedure for this improved
meta-heuristic approach BAM is also presented. To prove the performance of this proposed
meta-heuristic method, BAM is compared with BA and other population-based optimization
methods, DE and SGA. The experiment shows that the proposed approach is more effective and
feasible in image matching than the other model.

Introduction
As a way of getting a measure of similarity between images, image matching, or comparing images
is an important computer vision problem in many applications, such as object recognition and
tracking, image retrieval and registration, texture classification, image fusion and so on[1].
Nowadays, there are a significant number of different approaches for image matching. However,
there are two main trends for image matching in gray scale images [2]: methods based on greyscale
correlation and methods based on feature. The former often uses sliding template to attain matching,
and different matching algorithms may use different templates or correlation criterions. The
approach based on image greyscale usually gets high matching rate, however, it is so
time-consuming to compute that it cannot satisfy the demands of real-time application. The latter
often uses the interest point, edge or region extracted from the image as basic units for image
matching, so finding a relationship between images is performed using only this information. This
drastically reduces the required computation time. However, the matching rate almost depends on
the features extracted. The latter method has also computational demands if it wants to reach high
matching rate. To reduce the computational time and improve matching rate, various algorithms are
proposed to tackle the image matching problem. Chen used genetic algorithm (GA) to obtain the
optimal translation and rotation parameters for superimposing one image onto another after their
similarity between these two images is evaluated by calculating the dissimilarity area of their binary
images using logical operators [3]. Salomon used differential evolution (DE) to implement medical
image registration [4]. Liu proposed a novel Chaotic Quantum-behaved Particle Swarm
Optimization based on Lateral Inhibition (LI-CQPSO) to solve complicated image matching
problems. To overcome the main drawbacks of computational complexity and premature
convergence of PSO, the proposed LI-CQPSO combines advantages of chaos theory, quantum and
lateral inhibition to better performance [5].

All rights reserved. No part of contents of this paper may be reproduced or transmitted in any form or by any means without the written permission of Trans
Tech Publications, www.ttp.net. (ID: 130.203.136.75, Pennsylvania State University, University Park, USA-09/05/16,12:15:33)
 Applied Mechanics and Materials Vol. 203 89

In 1995, Storn and Price firstly proposed a novel evolutionary algorithm (EA): differential
evolution (DE) [6, 7], which is a new heuristic approach for minimizing possibly nonlinear and
non-differentiable continuous space functions. It converges faster and with more certainty than
many other acclaimed global population-based optimization methods. This new method requires
few control variables, which makes DE more robust, easy to use, and lends itself very well to
parallel computation.
Firstly presented in [8], the bat-inspired algorithm or bat algorithm (BA) is a meta-heuristic
search algorithm, inspired by the echolocation behavior of bats with varying pulse rates of emission
and loudness [9]. The primary purpose for a bat's echolocation is to act as a signal system to sense
distance. A comprehensive review about BA is carried out by Parpinelli and Lopes [10]. A further
improvement is the development of an evolving bat algorithm (EBA) with better efficiency [11].
However, in the field of image matching, no application of BA algorithm exists yet. In this
paper, we use an original BA and an improved modified BA algorithm to solve image matching
problem. Here, we add mutation operation in DE between bats to propose a new meta-heuristic
algorithm according to the principle of BA, and then an improved BA algorithm is used to search
the optimal or sub-optimal matching between these two images. To investigate the feasibility and
effectiveness of our proposed approach, it is compared with BA and other population-based
optimization methods, DE and SGA. The simulation experiments show that the proposed method
has higher speed and more comparable matching precision than the other method based on the
greyscale.

Bat Algorithm with Mutation (BAM)

Bat algorithm (BA). The bat algorithm is a new swarm intelligence optimization method, in which
the search algorithm is inspired by social behavior of bats and the phenomenon of echolocation to
sense distance. In BA, each bat is defined by its position xit , velocity vit , frequency fi, loudness
Ait and the emission pulse rate rit in a d-dimensional search space. The new solutions xit and
velocities vit at time step t are given by
fi = f min + ( f max − f min ) β (1)

vti =vti -1 + (xti -x* ) fi (2)

xti =xti -1 + vti (3)

where β∈ [0, 1] is a random vector drawn from a uniform distribution. Here x∗ is the current
global best location (solution) which is located after comparing all the solutions among all the n
bats.
For the local search part, once a solution is selected among the current best solutions, a new
solution for each bat is generated locally using random walk
xnew = xold + εAt (4)
where ε∈ [−1, 1] is a scaling factor which is a random number, while At =< Ait > is the average
loudness of all the bats at time step t.
Furthermore, the loudness Ai and the rate ri of pulse emission update accordingly as the
iterations proceed show as Eq. 5.
Ait +1 = α Ait , rit +1 = ri0 [1 − exp(−γ t )] (5)
90 Review of Modern Engineering Solutions for the Industry

Where α and γ are constants. In essence, α is similar to the cooling factor of a cooling schedule in
the simulated annealing (SA) [12]. For simplicity, we set α = γ = 0.9 in this work.

Bat algorithm with mutation (BAM).The differential evolution (DE) algorithm, proposed by
Storn and Price [6, 7], is a simple evolutionary algorithm (EA) which generates new candidate
solutions by combining the parent individual and a few other individuals of the same population. A
candidate substitutes the parent only if it has better fitness. This is a rather greedy selection scheme
which often overtakes traditional EAs. Advantages of DE are easy implementation, simple structure,
speed and robustness.
For bat algorithm, as the search relies entirely on random walks, a fast convergence cannot be
guaranteed. Described here for the first time, a main modification of adding mutation operator is
made to the BA, including two minor modifications, which are made with the aim of speeding up
convergence, thus making the method more practical for a wider range of applications but without
losing the attractive features of the original method.
The first modification is that we use fixed frequency f and loudness A instead of various
frequency fi and Ait . Similar to BA, in BAM, each bat is defined by its position xit , velocity vit , the
emission pulse rate rit and the fixed frequency f, loudness A in a d-dimensional search space. The
new solutions xit and velocities vit at time step t are given by
vti =vti -1 + (xti -x* ) f (6)

xti =xti -1 + vti (7)

Where x∗ is the current global best location (solution) which is located after comparing all the
solutions among all the n bats. In our experiments, we make f = 0.5.
The second modification is to add mutation operator in an attempt to increase diversity of the
population to improve the search efficiency and speed up the convergence to optima. For the local
search part, once a solution is selected among the current best solutions, a new solution for each bat
is generated locally using random walk by Eq. 4 when ξ is larger than pulse rate r, i.e., ξ>r, where ξ
∈ [0, 1] is a random real number drawn from a uniform distribution; while when ξ ≤ r, we use
mutation operator in DE updating the new solution to increase diversity of the population to
improve the search efficiency by Eq. 8.
xnew = xrt1 + F ( xrt2 − xrt3 ) (8)

Where F is the mutation weighting factor, while r1, r2, r3 are uniformly distributed random integer
numbers between 1 and NP.

Image Matching Using Bat algorithm with mutation (BAM)

Image matching could be described as following: given two greyscale image, one is original
image with M1*N1 pixels and the other is object image with M2*N2 pixels. As an example, Fig.
2(a) and 2(b) shows an original image and object image with 512*512 and 32*32 pixels
respectively, while Fig. 2(c) shows the final matched image using BAM.
 Applied Mechanics and Materials Vol. 203 91

Begin
Step 1: Initialization. Set the generation counter t = 1; Initialize the population of NP bats P
randomly and each bat corresponding to a potential solution to the given problem;
define pulse frequency Q; set loudness Ai, the initial velocities vi and pulse rate ri(i =
1,2,⋯,NP); set weighting factor F.
Step 2: Evaluate the fitness for each bat in P by Eq. 9
Step 3: while The halting criteria is not satisfied or t < MaxGeneration do
Sort the population of bats P from best to worst by order of fitness for each bat;
for i=1:NP (all bats) do
Select uniform randomly r1≠r2≠r3≠i
r4 =  N P * rand 
v it = v it −1 + ( v it − x* ) × Q
x it = x it −1 + v it
if (rand > r) then
x ut = x* + α ε t
else
x ut = x rt1 + F ( x rt2 − x rt3 )
end if
t
Evaluate the fitness for the offsprings x ut , x it , x r4
Select the offspring x kt with the best fitness among the offsprings
x ut , x it , x rt4
if (rand < A) then
x rt4 = x kt ;
end if
end for i
Evaluate the threat cost for each bat in P by Eq. 9.
Sort the population of bats P from best to worst by fitness order for each bat;
t = t+1;
Step 4: end while
Step 5: Inversely transform the coordinates in final optimal path into the original coordinate,
and output
End.

Fig. 1 Algorithm of BAM for image matching

As humans being, it is easy to discover the very position of the object image in the original image.
However, using a computer to solve the problem in fast manner is a highly challenging task.
Generally it can compare the original image and object image one by one pixel to get the fitness for
every pixel as Eq. 9:
M2 N2
fitness ( x, y ) = ∑∑ (| I1 (i + x − 1, j + y − 1) − I 2 (i, j ) |) (9)
i =1 j =1

Where (x, y) represents the position in the original image, I1 and I2 are the pixel values for the
original image and object image, respectively. Among many definitions for fitness(x, y), the best
fitness (the minimum fitness) is the matching point. For convenient implementation, it needs to
calculate (M1-M2+1)*(N1-N2+1) fitness values and it is so time-consuming to compute that it
cannot satisfy real-time application. Therefore, the paper uses bat algorithm with mutation (BAM)
to accelerate searching speed. And the mainframe of the method in this paper is shown in Fig. 1.
92 Review of Modern Engineering Solutions for the Industry

Simulation Experiments
In this section, we look at the performance of BAM as compared with BA, DE and SGA. A
stud genetic algorithm (SGA) [13] is a GA that uses the best individual at each generation for
crossover. To allow a fair comparison of running times, all the experiments were performed on a PC
with a Pentium IV processor running at 1.8 GHz, 512 MB of RAM and a hard drive of 160 Gbytes.
Our implementation was compiled using MATLAB R2011b (7.13) running under Windows XP
SP3. No commercial BAM tools or other population-based optimization tools were used in the
following experiments. In the following experiments, we set population size to 30 and the number
of maximum iteration is 200.
To compare the different effects, we ran 100 Monte Carlo simulations of each algorithm on the
image matching problem to get representative performances. The results are recorded in Table 1
after 100 Monte Carlo runs. In the Table, consuming CPU time, the average, the best and the worst
of 100 runs are reported. We must point Time1 and Time2 denote total time and time reaching
convergence respectively in Table 1.
As seen from Table 1, the BAM algorithm is more successful than the BA, DE and SGA for
image matching problem. In addition, the simulation results show that the matching found by BAM
is far better than the matching found by BA, DE and SGA for most of the 100 independent runs
which are started with the random initialization.

Table 1. Image matching results for BA, DE, BAM and SGA

BA DE BAM SGA
Best 11957 2373 2373 2373
Worst 43087 37849 35976 39272
Mean 37474 27303 16826 29299
Time1(sec) 54.64 57.34 107.02 32.00
Time2(sec) 54.64 42.43 7.50 15.2

To observe the development of the best solutions for the algorithms through the iterations
Fig.2 is shown. Fig.2 (a) shows the original image with 512*512. Fig. 2(b) shows the object image
with 32*32. Fig. 2(c) shows the final optimum position with minimum fitness.

Fig. 2(a) Original image Fig. 2(b) Object image Fig. 2(c) Matching result
 Applied Mechanics and Materials Vol. 203 93

Conclusion
Bat algorithm with mutation is a simple but effective method used in image processing. When it is
used in image matching, it can reduce the number of candidate position of matching, and
accordingly reduce the time complexity of the method. Further working is intent to compare lots of
optimization algorithms and combine them to further reduce the computation time of image
matching.

References
[1] Information on http://www.cim.mcgill.ca/~dparks/CornerDetector/index.htm
[2] Y.S. Zhu and C.M. Guo: The Research of correlation Matching Algorithm Based on
Correlation Coefficient. Signal Process. Vol. 19 (2003), p. 531-534
[3] T.H. Chen, J. Hung and F.J. Shiou: A GA-based image alignment approach for tissue image
matching. Sci. Res. Essays Vol. 6 (2005), p. 304–309
[4] M. Salomon, G.R. Perrin and F. Heitz: Differential Evolution for Medial Image Registration.
in: International Conference on Artificial Intelligence, Las Vegas, USA, 2001, pp. 201–207.
[5] F. Liu, H.B. Duan and Y.M Deng: A chaotic quantum-behaved particle swarm optimization
based on lateral. Optik, (2012) in press.
[6] R. Storn, K. Price, Differential evolution - a simple and efficient adaptive scheme for global
optimization over continuous space, Technical Report, International Computer Science
Institute, Berkley, 1995.
[7] R. Storn, K. Price, Differential evolution-a simple and efficient heuristic for global
optimization over continuous spaces, Journal of Global Optimization 11 (4) (1997) 341–359.
[8] X.S. Yang, A new metaheuristic bat-inspired algorithm, in: Nature Inspired Cooperative
Strategies for Optimization (NISCO 2010), Studies in Computational Intelligence, Vol. 284,
2010, pp.65-74, Springer Berlin.
[9] J.D. Altringham, Bats: Biology and Behaviour, Oxford Univesity Press, Oxford, 1996.
[10] R.S. Parpinelli, H.S. Lopes, New inspirations in swarm intelligence: a survey, Int. J.
Bio-Inspired Computation, 3(2011)1-16.
[11] P.W. Tsai, J.S. Pan, B.Y. Liao, M.J. Tsai, V. Istanda, Bat algorithm inspired algorithm for
solving numerical optimization problems, Applied Mechanics and Materials, 148-149(2012)
134-137.
[12] S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi, Optimization by simulated annealing, Science,
220(1983) 671–680.
[13] W. Khatib, P. Fleming, The stud GA: a mini revolution?, in Parallel Problem Solving from
Nature, A. Eiben, T. Back, M. Schoenauer, H. Schwefel, Springer, New York, 1998.
Review of Modern Engineering Solutions for the Industry
10.4028/www.scientific.net/AMM.203

Image Matching Using a Bat Algorithm with Mutation

10.4028/www.scientific.net/AMM.203.88

DOI References
[5] F. Liu, H.B. Duan and Y. M Deng: A chaotic quantum-behaved particle swarm optimization based on
lateral. Optik, (2012) in press.
10.1016/j.ijleo.2011.09.052
[7] R. Storn, K. Price, Differential evolution-a simple and efficient heuristic for global optimization over
continuous spaces, Journal of Global Optimization 11 (4) (1997) 341–359.
10.1023/A:1008202821328
[10] R.S. Parpinelli, H.S. Lopes, New inspirations in swarm intelligence: a survey, Int. J. Bio-Inspired
Computation, 3(2011)1-16.
10.1504/IJBIC.2011.038700
[13] W. Khatib, P. Fleming, The stud GA: a mini revolution?, in Parallel Problem Solving from Nature, A.
Eiben, T. Back, M. Schoenauer, H. Schwefel, Springer, New York, (1998).
10.1007/BFb0056910