Abstract
This contribution is devoted to the application of iterated local search to image registration, a very complex, real-world problem in the field of image processing. To do so, we first re-define this parameter estimation problem as a combinatorial optimization problem, then analyze the use of image-specific information to guide the search in the form of an heuristic function, and finally propose its solution by iterated local search.
Our algorithm is tested by comparing its performance to that of two different baseline algorithms: iterative closest point, a well-known, image registration technique, a hybrid algorithm including the latter technique within a simulated annealing approach, a multi-start local search procedure, that allows us to check the influence of the search scheme considered in the problem solving, and a real coded genetic algorithm. Four different problem instances are tackled in the experimental study, resulting from two images and two transformations applied on them. Three parameter settings are analyzed in our approach in order to check three heuristic information scenarios where the heuristic is not used at all, is partially used or almost completely guides the search process, as well as two different number of iterations in the algorithms outer-inner loops.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
T. Bäck. (1996). Evolutionary Algorithms in Theory and Practice. Oxford University Press.
Bardinet, E., S. Fernández-Vidal, S. Damas, G. Malandain, and N. Pérez de la Blanca. (2000). “Structural Object Matching.” In Proceedings of the 2nd International Symposium on Advanced Concepts for Intelligent Vision Systems (ACIVS 2000) 2, Germany: Baden-Baden, pp. 73–77.
Besl, P.J. and N.D. McKay. (1992). “A Method for Registration of 3-D Shapes.” IEEE Transactions on Pattern Analysis and Machine Intelligence 14, 239–256.
C. Blum and A. Roli. (2003). “Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison.” ACM Computing Surveys 35(3), 268–308.
Brown, L.G. (1992). “A Survey of Image Registration Techniques.” ACM Computing Surveys 24(4), 325–376,
C. K. Chow, Tsui, H.T. and T. Lee. (2004). “Surface Registration Using a Dynamic Genetic Algorithm.” Pattern Recognition 37, 105–117.
Cordón, O., S. Damas, and J. Santamaría. (2003). “A CHC Evolutionary Algorithm for 3D Image Registration.” In T. Bilgic, B.D. Baets, and O. Bogazici, (eds.), Lecture Notes in Artificial Intelligence 2715, Springer, pp. 404–411.
Dorigo, M. and T. Stützle. (2003). “The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances.” In F. y Glover, G. Kochenberger, (eds.), Handbook of Metaheuristics, Kluwer Academic Publishers, pp. 251–285.
Feldmar, J. and N. Ayache. (1996). “Rigid, Affine and Locally Affine Registration of Free-Form Surfaces.” International Journal of Computer Vision 18(2), 99–119.
S. Fernández-Vidal, E. Bardinet, S. Damas, G. Malandain, and N. Pérez de la Blanca. (2000). “Object Representation and Comparison Inferred From Its Medial Axis.” In Proceedings of the International Conference on Pattern Recognition (ICPR 00) Spain: Barcelona, 1, pp. 712–715.
F. Glover and G. Kochenberger. (2003). Handbook of Metaheuristics. Kluwer Academic Publishers.
Han, K.P., K.W. Song, E.Y. Chung, S.J. Cho, and Y.H. Ha. (2001). “Stereo Matching Using Genetic Algorithm With Adaptive Chromosomes.” Pattern Recognition 32, 1729–1740,
He, R. and P.A. Narayana. (2002). “Global Optimization of Mutual Information: Application to Three-Dimensional Retrospective Registration of Magnetic Resonance Images.” Computerized Medical Imaging and Graphics 26, 277–292.
Laguna, M. and R. Martí. (2003). Scatter Search: Methodology and Implementations in C. Kluwer Academic.
Liu, Y. (2004). “Improving ICP With Easy Implementation for Free Form Surface Matching.” Pattern Recognition 37(2), 211–226.
H. R. Lourenço, O.C. Martin, and T. Stützle. (2003). “Iterated Local Search.” In F. Glover and G. Kochenberger, (eds.), Handbook of Metaheuristics, Kluwer Academic Publishers, pp. 321–353.
J. Luck, C. Little, and W. Hoff (2000). “Registration of Range Data Using a Hybrid Simulated Annealing and Iterative Closest Point Algorithm. In Proceedings of the IEEE Intl. Conf. on Rob. and Auto., San Francisco, USA, pp. 3739–3744.
R. Martí. (2003). “Multi Start Methods.” In F. Glover and G. Kochenberger (eds.), Handbook of Metaheuristics, Kluwer Academic Publishers, pp. 355–368.
O. Monga, S. Benayoun, and O.D. Faugeras. (1992). “Using Partial Derivatives of 3D Images to Extract Typical Surface Features.” In Proceedings of the IEEE Computer Vision and Pattern Recognition (CVPR 92), Illinois (USA): Urbana Champaign, pp. 354–359.
Simunic, K. and S. Loncaric. (1998). “A Genetic Search-Based Partial Image Matching.” Proceedings of the 2nd IEEE International Conference on Intelligent Processing Systems (ICIPS 98), Australia: Gold Coast, pp. 119–122.
J. P. Thirion and A. Gourdon. (1996). “The 3-D Marching Lines Algorithm: New Results and Proofs.” Graphical Models and Image Processing 58(6), 503–509.
S.M. Yamany, Ahmed, M.N. and A.A. Farag. (1999). “A New Genetic-Based Technique for Matching 3D Curves and Surfaces.” Pattern Recognition 32, 1817–1820.
Z. Zhang. (1994). “Iterative Point Matching for Registration of Free-Form Curves and Surfaces.” International Journal of Computer Vision 13(2), 119–152.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was partially supported by the Spanish Ministerio de Ciencia y Tecnología under project TIC2003-00877 (including FEDER fundings) and under Network HEUR TIC2002-10866-E.
Rights and permissions
About this article
Cite this article
Cordón, O., Damas, S. Image registration with iterated local search. J Heuristics 12, 73–94 (2006). https://doi.org/10.1007/s10732-006-4983-4
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10732-006-4983-4