Abstract
Image registration is an elementary task in Computer Vision, which geometrically aligns multiple images of a scene, captured at different times, from various viewpoints, or by heterogeneous sensors. The optimisation strategy we employ for achieving the optimal set of transformation vectors is a major factor that determines the success and effectiveness of an automatic registration procedure. This paper discusses a scheme to modify the conventional Particle Swarm Optimisation (PSO) algorithm for better search space exploration and for faster convergence. While PSO is running, after half of the total number of iterations, find the particle which is in worst position in space, then reposition that particle by mean value of its current position and the global solution. It is observed that re-positioning the worst particle in space helps that particle from premature convergence to a local optimum solution and motivates the particle to generate unique search directions, which increased the possibility of finding the globally best solution. An image registration algorithm using this modified PSO method is also presented. From the experimental results presented here, it is visible that the proposed algorithm guarantees superior results in terms of registration accuracy and reduced execution time, even in the case of large deformations between the reference and float images.
You have full access to this open access chapter, Download conference paper PDF
Similar content being viewed by others
Keywords
1 Introduction
In a typical problem instance, an image registration system considers two images: a reference image, denoted by \(I_R\) and a float image, denoted by \(I_F\). The outcome of the registration algorithm is a transformation T such that when this geometrical transformation is applied on the float image, the reference image \(I_R\) and the transformed float image T(\(I_F\)) are in perfect alignment with each other [18]. Thus the aim is to find a transformation \(T^{*}\) such that \(T^{*}\) gives maximum similarity between the reference image and the float image, with proper guidance from an optimisation technique. A prominent category of algorithms fall within the class of automatic or global registration methods, which use the full image data to derive an appropriate transformation for aligning the input images.
In an automatic framework, the registration process is formulated as a mathematical problem by constructing a cost function defined over the similarity or dissimilarity between the input images. Then search for a single transformation, \(T^{*}\), imposed on the whole image, which maximizes or minimizes the cost function by searching the parameter space of all allowable transformations. A more robust approach is to register images using feature points identified on both the images. A mapping is found based on these control points which is directly used for achieving correspondence between the reference and the float images.
From an operational point of view, image registration methods choose an intelligent combination of the following four coupled components [8, 18].
-
1.
Feature detection: Salient features in the input images are manually marked or automatically detected.
-
2.
Feature matching: A mapping between the features detected in the float image and those detected in the reference image is determined.
-
3.
Transform model estimation: The attributes of the mapping functions are estimated in order to align the float image with the reference image.
-
4.
Image resampling and transformation: The float image is transformed using the mapping functions and the intensity values at non-integer coordinates are estimated by some interpolation technique.
The registration problem can be reduced to determining parameters of the transformation in the search space that provides the highest similarity. This is an optimisation problem in multidimensional space. The number of parameters in the transformation model is the dimensional size of this problem. Hence, it is necessary to keep the number of parameters in the model as small as possible for a faster registration process. The number of sub-processes involved makes the whole process of image registration very complex and poses many challenges in the registration of digital images. In general, image registration has huge computational cost and the overall performance of a registration algorithm rely upon the stability of the optimisation strategy. Although considerable research has gone into developing efficient optimisation techniques, more attention has to be paid to formulate improved strategies for finding the optimal match between the reference and the float images.
2 Review of Literature
The word registration was first coined by Becker in the year 1900 in a US patent [4]. In the literature, several reports on image registration methods can be found. Probably, the most comprehensive survey of the universal image registration methods was published by Brown in 1992 [5]. She provided a framework for understanding the existing registration techniques and also a methodology for supporting the selection of appropriate technology for a particular registration problem. Comprehensive surveys of classic image registration methods were tabled by Zitova [18] in 2003.
The optimisation technique used for obtaining optimal transformation parameters has a pivotal role in determining the success and effectiveness of any registration method. Swarm intelligence, Tabu Search, Simulated Annealing, Genetic Algorithms, SVMs and ANNs are well-known examples of intelligent algorithms that use clever simplifications and methods to solve computationally complex problems [14]. These global optimisation methods guarantee improved performance when applied on standard problems such as Traveling Salesmen Problem, Knapsack Problem, Searching and Sorting etc.
Seixas et al. [15] makes use of genetic algorithm to address image registration based on point matching. The approach uses nearest neighbor point matching and mapping was performed using affine transformation. Due to the use of genetic algorithm, pre-alignment between images are not required to guarantee good results. However, accuracy depends on the random choice of initial population. In many cases, the hybrid particle swarm technique provided better registration performances than the evolutionary techniques providing comparable convergence. It is observed that hybrid approach employing crossover operator improves accuracy. However, in few cases convergence was adversely affected due to the prevention of particle from moving to global optimum.
Valsecchi et al. [16] reported a real-coded genetic algorithm based image registration approach using intensity-based technique. Genetic Algorithm (GA) makes use of cross-over and random mutation. Registration is performed through multiple stages following a multi-resolution strategy, where complexity increases with stages, and incorporation of provisions for restart of optimisation. The restart procedure improved reliability. The authors report that the convergence issues experienced was properly addressed after the initial investigation stage. Chen et al. [6] proposed particle swarm optimisation for medical image registration. Rigid transformation is used for global transformation of image and non-rigid for local transformation of images by cubic B-spline curves.
Another PSO-based technique is proposed in [12]. Here, a hybrid particle swarm optimisation is developed for multi modal 3D medical image registration, by including sub-population and crossover from GA techniques into traditional PSO. A dynamic brain image registration is proposed by Li et al. in [11]. The algorithm combines PSO and inheritance idea. The algorithm inherits information from reference image to guide registration process. The algorithm has a complexity of \(\mathcal {O}(n*m*t)\), where t is the time taken to compute fitness value of a particle, m denotes the population size, and n is the number of iterations.
Yet another PSO based registration approach is that by Wachowiak et al. [17] for multimodal images. Here, a single slice 3D biomedial image registration is done using PSO. A new hybrid PSO approach incorporating initial user guidance is employed. Performance of the optimisation approach was compared with mutual information metric under different evolutionary strategies. Another work is the non-rigid approach of registration for medical images proposed by Anna et al. [3] to enhance the quality of registration using DTCWT (Dual-Tree Complex Wavelet Transform) and Niche PSO (NPSO). The approach employs multi-scale key-points as features, and DCTWT is used to detect features, and Hausdorff distance metric is employed as the metric to compute image similarity. NPSO is used to compute optimal affine parameters. The authors claim better robustness and accuracy in noisy images. Krusienski and Jenkins raise many suggestions and solutions for overcoming the limitations of the conventional PSO [9]. There are modifications of the conventional PSO which assert conditions either on convergence time or on search capacity of the algorithm.
The literature survey carried out reveals that a major issue in automatic image registration is the need for efficient and faster optimisation algorithms for determining the parameters of registration. Exhaustive or brute force approaches are computationally impractical. Simulated Annealing (SA), Particle Swarm optimisation (PSO) and Genetic algorithm (GA) are some of the popular global search algorithms employing heuristics to arrive at faster solutions. It is also observed that when applied to image registration, these algorithms can offer some clever formulations which minimize the overall computational overhead. Research in this area continues to be motivated by the need to exploit new mechanisms and principles to boost the performance of the conventional PSO for a variety of problems in practice, including image registration.
3 Single Swarm PSO with Refined Search Space Exploration
Swarm Intelligence is the emergent collective intelligence of groups of social organisms called swarms. Swarms consist of large number of individuals coordinated by indirect communication, self-organization and decentralized control. Each individual is named a particle of the population. Computational swarm intelligence analyses the behavior of natural swarms, such as fish schools, bird flocks and ant colonies, and translates the learned theories into an algorithm. When a solution to a problem is desired, the population of individuals iteratively evolve by combined efforts and competition among the individuals. Particle Swarm Optimisation (PSO) is introduced by Kennedy and Eberhart, which is a population-based metaheuristic [7].
In the iterative PSO algorithm, each particle is initialized with uniform random values in the given D-dimensional search space S. Particle’s motion is based on its velocity and current position and these values are updated at each iteration. The \(i^{th}\) particle of the group is defined by a velocity vector \(v^{i}\)=(\(v^{i1}\), \(v^{i2}\),...\(v^{id}\),...\(v^{iD}\)) and a position vector \(x^{i}\)=(\(x^{i1}\), \(x^{i2}\),...\(x^{id}\),...\(x^{iD}\)) in the D-dimensional search space S. In the \(n^{th}\) iteration, each particle i has a position \(x^{id}_{n}\) in the search space S and moves with a velocity \(v^{id}_{n}\). The velocity of a particle is updated in every iteration according to Eq. 1.
Subsequently, the new particle position can be determined in terms of Eq. 2.
In these equations, N stands for the total number of iterations and n =1,2,3... N. \(c_{1}\) and \(c_{2}\) are the acceleration coefficients known as the cognitive learning rate and the social learning rate, respectively. \(r_{1}\) and \(r_{2}\) are random numbers between 0 and 1. w is the inertia coefficient which will vary according to the Eq. 3.
The velocity of particles should be in the range of [\(-V_{max}\), \(V_{max}\)] to ensure that the particle does not exit from the allowed search space. The particles accelerate toward the other particles which have better fitness values. To establish the local and global attractor, the fitness or objective function f : S \(\subseteq \) \(R^{n}\) \(\rightarrow \) R is used. The velocity and position adaptation is done iteratively for all particles of the swarm until a specified termination criterion is reached. Once all the particles find their best solution, \(p_{best^{n}}^{id}\), i=1, 2, ..... N, the best solution is again calculated from these N values. The best found position by the swarm is the result and thereby the return value of the algorithm. This best value is globally accepted as the final solution, which is represented as \(g_{bestn}\).
We propose the following modification to the conventional PSO algorithm as a tool to solve image registration problem to arrive at faster solutions. The proposal is to re-position the worst particle in space to help that particle from premature convergence to a local optimum solution. The re-randomization is performed after half of the iterations. This motivates the stray particles to generate unique search directions, which increases their possibility of faster convergence to the global solution.
3.1 Validation Using Benchmark Functions
The optimization ability of the proposed technique is validated using a set of standard benchmark functions [10]. There are unimodal and multimodal functions. A function with only one local minimum is called unimodal function, whereas a multimodal function has more than one local minima. As the dimension of the function increases, the number of local minima will also increase. Parameters for the experiment include dimension of the optimization function D, number of particles M, total number of iterations N, inertia coefficient \(\omega \) and acceleration coefficients \(c_{1}\) and \(c_{2}\). The proposed PSO algorithm was run for various dimensions D = 2, 3, 4, 5 and 10. The inertia coefficient \(\omega \) is set to 0.2 and both the acceleration coefficients \(c_{1}\) and \(c_{2}\) are set to 2.0. The other important parameters number of particles M, total number of iterations N are set to 200 and 5000 respectively.
Table 1 reports the best parameter setting of the proposed PSO, for each of these functions, to converge to the global optimum value. This table was prepared after the proposed algorithm was tested for 30 independent runs. NFE is the number of function evaluations, which is the most important characteristic of an optimisation algorithm.
4 Results and Discussion
The problem under consideration is the global, rigid registration of two 2D images. A rigid-body transformation in two dimensions is defined by four parameters: two translations in x and y directions and two rotations in x an y directions. The objective function to be maximized is the Mutual Information (MI) between the input images. MI [13] is the most celebrated similarity measure employed for image registration. The experiment environment is Intel Core i5 (1.3 GHz) processor with 4GB primary memory and the algorithm is run on 64-bit Mac OSX Yosemite system. The proposed technique is implemented using MATLAB v7.10. The first set of experiments use images from CMU House sequence [1]. The CMU house data set contains 111 two dimensional gray scale images of a toy house. Each image is of size 480 \(\times \) 512 and is taken at different angles of camera position. Next set of experiment uses NewYork Data set [2], where the images are taken by a rotating camera. This data set contains 35 images of 512 \(\times \) 512 size. Figure 1 is a set of sample images from these data sets.
4.1 Translation
As the first step, the modified PSO is tested using CMU House Sequence. Here the first image is taken and is translated by various levels. The reference image is translated by various units, in x and y directions, to create the set of float images. A total of M = 20 particles are initialized uniformally in the search space. The parameters c1 and c2 are set to 2. Mutual Information (MI) between the input image is used as the cost function. Registration is performed using both the traditional PSO and the proposed PSO algorithms. In order to analyze the registration accuracy, Root Mean Square Error (RMSE) between the reference image \(I_R(x, y)\) and the registered float image \(I_F(T(x,y))\) is calculated using Eq. 4.
Table 2 summarizes the results for both these algorithms over 20 independent runs for the given set of input images. Total number of iterations for both the algorithms are set to N = 200.
4.2 Rotation
The second set of experiments were designed to analyze the effectiveness of the modified PSO for images with varying degrees of rotations. Images from NewYork data set are utilized for this. The first image in this dataset is fixed as the reference image and the remaining 34 images are used to create the float image set. Registration is performed using both the traditional PSO and the modified PSO. 20 independent runs were carried out for each input image set and the best values are selected. Here for images from 1 to 10, the parameter setting for the experiments was the following. A total of M = 20 particles are initialized uniformally in the search space, c1 and c2 are set to 2, N = 200. Mutual Information (MI) between the input images is used as the cost function. Preliminary results are included in Fig. 2 and the results are summarized in Table 3.
4.3 Translation and Rotation
The final set of experiments were designed to analyze the effectiveness of the modified PSO for images with varying degrees of translations and rotations using images from NewYork data set. Float images are created by translating each image by +5, +10 and +15 units in both x and y directions. Relevant parts of the results are compiled in Table 4.
5 Summary
It is quite visible that the proposed PSO algorithm could optimize the benchmark functions for different dimensions. Various experiments were designed to demonstrate the efficiency of the modified PSO in achieving maximum similarity between the reference and float images; thus achieving registered images. The proposed PSO algorithm shows better average RMSE value and it acquired better similarity between the input images. It is evident from the convergence characteristics that the improved PSO attains better MI in fewer iterations and the best values for transformation parameters are sought in the remaining iterations. Generally area-based image registration methods mostly survive when the distortion between the input images is small. Here, the proposed algorithm guarantees highly acceptable solutions even in the case of large deformations between the reference and float images.
References
CMU House Sequence. http://vasc.ri.cmu.edu/idb/html/motion. Accessed Dec 2018
Oxford Dataset. http://www.robots.ox.ac.uk/~vgg/research/affine/. Accessed Dec 2018
Anna, W., Tingjun, W., Jinjin, Z., Silin, X.: A novel method of medical image registration based on DTCWT and NPSO. In: 2009 Fifth International Conference on Natural Computation, vol. 5, pp. 23–27, August 2009
Becker, J.: Focusing-camera, 4 April 1916. http://www.google.co.in/patents/ US1178475
Brown, L.G.: A survey of image registration techniques. ACM Comput. Surv. 24, 325–376 (1992)
Chen, Y.W., Lin, C.L., Mimori, A.: Multimodal medical image registration using particle swarm optimization. In: 2008 Eighth International Conference on Intelligent Systems Design and Applications, vol. 3, pp. 127–131, November 2008. https://doi.org/10.1109/ISDA.2008.321
Eberhart, R., Kennedy, J.: A new optimizer using particle swarm theory. In: 1995 Proceedings of the Sixth International Symposium on Micro Machine and Human Science, MHS 1995, pp. 39–43. IEEE (1995)
Goshtasby, A.A.: 2DD and 3-D Image Registration: For Medical, Remote Sensing, and Industrial Applications. Wiley-Interscience, Hoboken (2005)
Krusienski, D.J., Jenkins, W.K.: A modified particle swarm optimization algorithm for adaptive filtering. In: 2006 IEEE International Symposium on Circuits and Systems, pp. 4–140, May 2006. https://doi.org/10.1109/ISCAS.2006.1692541
Li, X., Tang, K., Omidvar, M.N., Yang, Z., Qin, K.: Benchmark functions for the CEC’2013 special session and competition on large-scale global optimization, January 2013
Li, Y., Lai, H., Lu, L., Gao, Y., Wang, P.: Dynamic brain magnetic resonance image registration based on inheritance idea and PSO. In: 2011 4th International Conference on Biomedical Engineering and Informatics (BMEI), vol. 1, pp. 263–267, October 2011. https://doi.org/10.1109/BMEI.2011.6098345
Lin, C.L., Mimori, A., Chen, Y.W.: Hybrid particle swarm optimization and its application to multimodal 3d medical image registration. Intell. Neurosci. 2012, 6:6 (2012). https://doi.org/10.1155/2012/561406
Maes, F., Collignon, A., Vandermeulen, D., Marchal, G., Suetens, P.: Multimodality image registration by maximization of mutual information. IEEE Trans. Med. Imag. 16(2), 187–198 (1997)
Pham, D., Karaboga, D.: Intelligent Optimisation Techniques: Genetic Algorithms, Tabu Search. Simulated Annealing and Neural Networks. Springer, Heidelberg (2012)
Seixas, F.L., Ochi, L.S., Conci, A., Saade, D.M.: Image registration using genetic algorithms. In: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, pp. 1145–1146. ACM (2008)
Valsecchi, A., Damas, S., Santamaría, J., Marrakchi-Kacem, L.: Genetic algorithms for voxel-based medical image registration. In: 2013 Fourth International Workshop on Computational Intelligence in Medical Imaging (CIMI), pp. 22–29 (2013)
Wachowiak, M.P., Smolikova, R., Zheng, Y., Zurada, J.M., Elmaghraby, A.S.: An approach to multimodal biomedical image registration utilizing particle swarm optimization. IEEE Trans. Evol. Comput. 8(3), 289–301 (2004). https://doi.org/10.1109/TEVC.2004.826068
Zitova, B., Flusser, J.: Image registration methods: a survey. Image Vis. Comput. 21(11), 977–1000 (2003)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Maddaiah, P.N., Pournami, P.N. (2019). Image Registration Using Single Swarm PSO with Refined Search Space Exploration. In: Deka, B., Maji, P., Mitra, S., Bhattacharyya, D., Bora, P., Pal, S. (eds) Pattern Recognition and Machine Intelligence. PReMI 2019. Lecture Notes in Computer Science(), vol 11941. Springer, Cham. https://doi.org/10.1007/978-3-030-34869-4_37
Download citation
DOI: https://doi.org/10.1007/978-3-030-34869-4_37
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-34868-7
Online ISBN: 978-3-030-34869-4
eBook Packages: Computer ScienceComputer Science (R0)