Abstract
This paper presents a mutual-information based optimization algorithm for improving piecewise-linear (PWL) image registration. PWL-registration techniques, which are well-suited for registering images of the same scene with relative local distortions, divide the images in conjugate triangular patches that are individually mapped through affine transformations. For this process to be accurate, each pair of corresponding image triangles must be the projections of a planar surface in space; otherwise, the registration incurs in errors that appear in the resultant registered image as local distortions (distorted shapes, broken lines, etc.). Given an initial triangular mesh onto the images, we propose an optimization algorithm that, by swapping edges, modifies the mesh topology looking for an improvement in the registration. For detecting the edges to be swapped we employ a cost function based on the mutual information (MI), a metric for registration consistency more robust to image radiometric differences than other well-known metrics such as normalized cross correlation (NCC). The proposed method has been successfully tested with different sets of test images, both synthetic and real, acquired from different angles and lighting conditions.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
González, J., Ambrosio, G., Arévalo, V.: Automatic urban change detection from the IRS-1D PAN. In: IEEE-ISPRS Joint Workshop on Remote Sensing and Data Fusion over Urban Areas, Rome, Italy, 2001, pp. 320–323
Bookstein, F.: Principal warps: Thin-plate-splines and the decomposition of deformations. IEEE Trans. Pattern Anal. Mach. Intell. 11(6), 567–585 (1989)
Goshtasby, A.: Piecewise linear mapping functions for image registration. Pattern Recogn. 19(6), 459–466 (1986)
Goshtasby, A.: Piecewise cubic mapping functions for image registration. Pattern Recogn. 20(5), 525–533 (1987)
Ehlers, M., Fogel, D.: High-precision geometric correction of airborne remote sensing revisited: The multiquadric interpolation. In: Image and Signal Processing for Remote Sensing, vol. 2315, pp. 814–824. SPIE, Bellingham (1994)
Kybic, J., Unser, M.: Fast parametric elastic image registration. IEEE Trans. Image Process. 12(11), 1427–1442 (2003)
Zitová, B., Flusser, J.: Image registration methods: A survey. Image Vis. Comput. 21(11), 977–1000 (2003)
The Mathworks: http://www.mathworks.com
Image Fusion Systems Research: Transformation functions for image registration. IFSR Technical Report (2003). http://www.imgfsr.com/ifsr_tf.pdf. Accessed 27/04/2007
ITT Visual Information Solutions: http://www.ittvis.com/envi
Leica Geosystems: http://gi.leica-geosystems.com
Shewchuk, J.: Lecture notes on Delaunay mesh generation. Tech. Rep. 3, University of California at Berkeley (1999)
Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)
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)
Viola, P., Wells, W.: Alignment by maximization of mutual information. Int. J. Comput. Vis. 24(2), 137–154 (1997)
Perrier, J., Agin, G., Cohen, P.: Image-based view synthesis for enhanced perception in teleoperation. In: Enhanced and Synthetic Vision, vol. 4023, pp. 332–338. SPIE, Bellingham (2000)
Morris, D., Kanade, T.: Image-consistent surface triangulation. In: IEEE International Conference on Computer Vision and Pattern Recognition (CVPR’00), Hilton Head, SC, USA, 2000, pp. 332–338
Lehner, B., Umlauf, G., Hamann, B.: Image compression using data-dependent triangulations. In: 3rd International Symposium on Visual Computing (ISVC’07), Part I 4841, pp. 351–362 (2007)
Yu, X., Bryan, B., Sederberg, T.: Image reconstruction using data-dependent triangulation. Comput. Graph. Appl. 21(3), 62–68 (2001)
Nakatuji, A., Sugaya, Y., Kanatani, K.: Mesh optimization using an inconsistency detection template. In: IEEE International Conference on Computer Vision (ICCV’05), vol. 2, Beijing, China. 2005, pp. 1148–1153
Servais, M., Vlachos, T., Davies, T.: Bi-directional affine motion compensation using a content-based, non-connected, triangular mesh. In: European Conference on Visual Media Production (CVMP’04), London, UK, 2004, pp. 49–58
Yip, B., Jin, J.: Image registration using triangular mesh. Adv. Multimed. Inf. Process. 3331, 298–303 (2004)
Schlesinger, D., Flach, B., Shekhovtsov, A.: A higher order MRF-model for stereo-reconstruction. Pattern Recogn. 3175, 440–446 (2004)
Matuszewski, B., Shen, J., Shark, L.: Elastic image matching with embedded rigid structures using spring-mass system. In: IEEE International Conference on Image Processing, vol. 2, pp. 937–940 (2003)
Hoppe, H.: Progressive meshes. Comput. Graph. 30, 99–108 (1996) (Annual Conference Series)
Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., Stuetzle, W.: Mesh optimization. Comput. Graph. 27, 19–26 (1993) (Annual Conference Series)
de Bruin, P., van Meeteren, P., Vos, F., Vossepoel, A., Post, F.: Accurate and high quality triangle models from 3D grey scale images. In: Medical Image Computing and Computer-Assisted Intervention (MICCAI’02), Part II 2489, pp. 348–355 (2002)
Vogiatzis, G., Torr, P., Cipolla, R.: Bayesian stochastic mesh optimisation for 3D reconstruction. In: British Conference on Machine Vision (BMVC’03), Norwich, UK, 2003, pp. 711–718
Surazhsky, V., Gotsman, C.: High quality compatible triangulations. In: Proceedings of 11th International Meshing Roundtable, pp. 183–192 (2002)
Surazhsky, V., Gotsman, C.: High quality compatible triangulations. Eng. Comput. 20(2), 147–156 (2004)
Wang, Y., Wang, C.C.L., Yuen, M.M.F.: Duplicate-skins for compatible mesh modelling. In: SPM ’06: Proceedings of the 2006 ACM Symposium on Solid and Physical Modeling, pp. 207–217. ACM, New York (2006)
Battiato, S., Gallo, G., Messina, G.: SVG rendering of real images using data dependent triangulation. In: Computer Graphics (SCCG’04), 20th Spring Conference on, pp. 185–192. ACM, New York (2004)
Schumaker, L.: Computing optimal triangulations using simulated annealing. Comput. Aided Geom. Des. 10(3–4), 329–345 (1993)
National Library of Medicine Insight Segmentation and Registration Toolkit: http://www.itk.org
Cole-Rhodes, A., Johnson, K., LeMoigne, J., Zavorin, I.: Multiresolution registration of remote sensing imagery by optimization of mutual information using a stochastic gradient. IEEE Trans. Image Process. 12(12), 1495–1511 (2003)
Chen, H., Varshney, P., Arora, M.: Performance of mutual information similarity measure for registration of multitemporal remote sensing images. IEEE Trans. Geosci. Remote Sens. 41(11), 2445–2454 (2003)
Xie, H., Pierce, L., Ulaby, F.: Mutual information based registration of SAR images. In: IEEE International Conference on Geoscience and Remote Sensing Symposium (IGARSS’03), vol. 6, pp. 4028–4031 (2003)
Inglada, J., Giros, A.: On the possibility of automatic multisensor image registration. IEEE Trans. Geosci. Remote Sens. 42(10), 2104–2120 (2004)
Kern, J., Pattichis, M.: Robust multispectral image registration using mutual-information models. IEEE Trans. Geosci. Remote Sens. 45(5), 1494–1505 (2007)
Xu, G., Zhang, Z.: Epipolar geometry in stereo, motion, and object recognition: A unified approach, 1st edn. Kluwer Academic, Norwell (1996)
Hartley, R., Zisserman, A.: Multiple View Geometry in Computer Vision, 2nd edn. Cambridge University Press, Cambridge (2004)
Spanier, E.: Algebraic Topology, 1st edn. McGraw-Hill, New York (1966)
Cover, T., Thomas, J.: Elements of Information Theory, 1st edn. Wiley, New York (1991)
Strang, G.: Introduction to Applied Mathematics, 1st edn. Wellesley-Cambridge Press, Wellesley (1986)
Arévalo, V., Gonzalez, J.: An experimental evaluation of non-rigid registration techniques on QuickBird satellite imagery. Int. J. Remote Sens. 29(2), 513–527 (2008)
Geusebroek, J., Burghouts, G., Smeulders, A.: The Amsterdam library of object images. Int. J. Comput. Vis. 61(1), 103–112 (2005)
Harris, C., Stephens, M.: A combined corner and edge detector. In: Alvey Vision Conference, vol. 4, Manchester, UK, 1988, pp. 147–151
Bouguet, J.: Pyramidal implementation of the Lucas-Kanade feature tracker. Description of the algorithm. Tech. rep., Intel Corporation, Microprocessor Research Labs (1999). http://robots.stanford.edu/cs223b04/algo_tracking.pdf. Accessed 26/06/2006
Torr, P.: A structure and motion toolkit in Matlab: Interactive adventures in S and M. Tech. Rep. MSR-TR-2002-56, Microsoft Research (2002). ftp://ftp.research.microsoft.com/pub/TR/TR-2002-56.ps. Accessed 27/03/2007
Author information
Authors and Affiliations
Corresponding author
Additional information
This work is supported by the Spanish Government under the research contracts CICYT DPI-2008-03527 and 2008-TEP-4016.
Rights and permissions
About this article
Cite this article
González, J., Arévalo, V. Mesh Topological Optimization for Improving Piecewise-Linear Image Registration. J Math Imaging Vis 37, 166–182 (2010). https://doi.org/10.1007/s10851-010-0199-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10851-010-0199-1