UNIVERSITY of CALIFORNIA Santa Barbara Computational Methods for Automatic Image Registration A dissertation submitted in partial satisfaction of the requirements for the degree Doctor of Philosophy in Electrical and Computer Engineering by Marco Zuliani Committee in charge: Professor B. Manjunath, Chair Professor S. Hespanha December 2006 UMI Number: 3245929 Copyright 2006 by Zuliani, Marco All rights reserved. UMI Microform 3245929 Copyright 2007 by ProQuest Information and Learning Company.
All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code. ProQuest Information and Learning Company 300 North Zeeb Road P. Box 1346 Ann Arbor, MI 48106-1346 The dissertation of Marco Zuliani is approved.
Manjunath, Committee Chair October 2006 Computational Methods for Automatic Image Registration Copyright c 2006 by Marco Zuliani iii To my family, and to the memory of my grandmother, Anna Pia. iv Acknowledgements Completing my graduate studies has been an extremely enriching and reward- ing experience both under a scientific and a human point of view. My doctorate is a team achievement, and in the next paragraphs I want to thank the people that contributed to this accomplishment. First I want to thank prof.
Manjunath for giving me the chance of joining his research group (I told you. I’ll be back!), for directing my research leaving me a lot of freedom, for the constant confidence he placed in me and for all his support, at all levels. I am extremely grateful to my doctoral committee members: to prof. Chan- drasekaran for the uncountable discussions I had with him, to prof.
Fusiello for sharing with me his expertise and rigor in many different fields of computer vision, to prof. Hespana for his interest in my research, to prof. Kenney for his informal, didactic, provoking, original and enthusiast attitude. I would like to thank the Office of Naval Research (grant #N00014-04-1-0121) for supporting the work presented in this dissertation.
The suggestions and directions of prof. Rhodes and prof. Rose have been extremely valuable in completing this work. Thanks also to prof.
Beghi and prof. Frezza who made it possible for me to start this experience. I am grate- ful to Dr. Bober for his guidance and support during my staying at the Mitsubishi Electric Visual Information Laboratory.
I have been honored to share the lab with great researchers and wonderful people: their support, acceptance, help and friendship have been a fundamen- tal part of this experience. Anyndia, Baris, Dmitry, Emily, Ibrahim, Jelena, v Jiyun, Kaushal, Laura, Luca, Mike, Ken, Nhat, Pratim, Shawn, Sitaram, Thomas, Zhiqiang, Xinding, thank you all and to everybody else who has been a part of our research group! I also want to thank Guylene, John, Ken, Richard, Val who made my life as a grad student much easier and smooth. During these years I shared countless wonderful moments and enriching expe- riences outside the lab with people that eventually became my “extended family”: Marcelo (my agelong apt-mate who introduced me to cachaça) & Emily, the “sa- cred pint” man Gabriel, Rogerio, all the other members and co-funders of the V., Ramesh, Vittorio, the family guys Jessica & Fernando, Francine & Hugo, Mylene & Marcelo, Luchino, Ibra, Dima, Max, An- toine, Sara S., N{a,e}da, Sandra, Jannelle, Nat, Sarah, Rimma, Elison, Desiree, Natalie, Daniel. My sincere gratitude goes to Fr.
Joe and Fr. Paul for their friendship, guidance and support. Thanks also to all the international (actually mostly Italian. ) visiting students or researchers that I met in the past few years: Ruggio, Stefano C.
Members), Antonio, Enrico, Mari- etto, Marina S., Raffi, Corrado, Anna, Paola, Blandina, Gaia. All my friends from the glorious days in Padova also deserve to be acknowledged here: Cesco Da Fogo, Dry & Titti, Marco M., the Curto, Siro, Soa & Soetto, Luca & Silvana, Fabio, Ennio, Padu, Emilio, Luca M., Marina, mami Balla, papi Baretz, Poje, Angela, Ale & Stefano, Matteo, Lupo, Sara M., Eva, Regina, Mandrea, Emi- rasta, Lorenzo, Ruben, Paolo B., Davide Reds, Davide B. You guys paved the way for this achievement. Thanks also to Carlos, Giovanni and Raquel who made my staying in UK more pleasant and to David for his friendship throughout the years, since first grade.
vi I am forever indebted to my brother Francesco for his continuous support and encouragement (you are always able to make me smile), to my parents Luciana & Pierino for their teachings, guidance, patience and support to ensure I could have the best possible education. Thanks to my grandmothers Anna Pia & Nilde for being always present in my life and to my godfather, my godmother and all my close relatives for their caring support. A special thanks to Elisa for her courage, her strength, her faith, her patience, her smile and her love. Bright, unique and special gifts you shared with me: grazie cuore mio.
Finally thank You, for Your gifts, for Your mysterious ways, for Your love. vii Curriculum Vitæ Marco Zuliani July 2001 Laurea in Ingegneria Informatica Department of Information Engineering Università degli studi di Padova, Padova, Italy July 2003 Master of Science Department of Electrical and Computer Engineering University of California, Santa Barbara October 2006 Doctor of Philosophy Department of Electrical and Computer Engineering University of California, Santa Barbara Fields of Study Image analysis and pattern recognition. Experience 2002-2006 Research Assistant 2005 Internship Mitsubishi Electric, Guildford, UK 2001-2006 Teaching assistant University of California, Santa Barbara 2002 Summer Internship FriulROBOT S.l, Udine, Italy Publications M. Manjunath, “Condition The- ory for Point Neighborhood Characteristic Structure Detec- tion,” IEEE Transactions on Pattern Analysis and Machine Intelligence, In revision.
Manjunath, “Drums, Curve Descriptors and Affine In- variant Region Matching,” Image and Vision Computing, Accepted for publication. Manjunath, “The Multi- RANSAC algorithm and its application to detect planar ho- mographies,” In IEEE International Conference on Image Processing, Genova, Italy, September 2005. Manjunath, “An axiomatic approach to corner detection,” In Proc. of IEEE Conference on Computer Vision and Pattern Recognition, pages 191– 197, San Diego, California, June 2005.
Manjunath, “Affine-invariant curve matching,” In IEEE International Conference on Image Processing, October 2004. Manjunath, “Drums and curve descriptors,” In British Machine Vision Conference, Kingston-upon-Thames, UK, September 2004. “A mathemat- ical comparison of point detectors,” In Proc. of the 2nd IEEE Workshop on Image and Video Registration, Wash- ington DC, June 2004.
Van Nevel, “A condition number for point matching with applica- tion to registration and post-registration error estimation,” IEEE Transactions on Pattern Analysis and Machine Intel- ligence, 25(11):1437–1454, November 2003. ix Abstract Computational Methods for Automatic Image Registration by Marco Zuliani Image registration is the process of establishing correspondences between two or more images taken at different times, from different viewpoints, under different lighting conditions, and/or by different sensors, and aligning them with respect to a coordinate system that is coherent with the three dimensional structure of the scene. Once feature correspondences have been established and the geometric alignment has been performed, the images are combined to provide a representa- tion of the scene that is both geometrically and photometrically consistent. This last process is known as image mosaicking.
The primary contribution of this research is the development of computational frameworks that tackle in a general and principled way the problems arising in the construction of an image registration and mosaicking system. Specifically, we present a general theory to detect image point features that are suitable for matching. Our theory generalizes and extends much of the previous work on de- tecting feature locations. We introduce a novel, physically motivated curve/region descriptor suitable to establish image correspondences in a geometrically invariant fashion.
New methods to estimate robustly the image transformation parameters in presence of large quantities of outliers and of multiple models are also presented. Finally we present a fully automated registration and mosaicking system that can x produce seamless mosaics from image pairs. Extensive experimental results with biological images, satellite images and consumer photographs are presented. xi Contents List of Tables xvii List of Figures xviii 1 Introduction 1 1.2 Thesis Organization and Contributions .1 Chapter 2: Point Feature Detectors: Theory .2 Chapter 3: Point Feature Detectors: Experiments .3 Chapter 4: Drums, Curve Descriptors and Affine Invariant Region Matching .4 Chapter 5: RANSAC Stabilization.
10 2 Point Feature Detectors: Theory 11 2.1 The Gradient Matrix .2 Condition Theory: A Brief Introduction .3 The Generalized Gradient Matrix: an Optical Flow Perspective .1 Optical Flow for Single Channel Images .3 Optical Flow for Multichannel Generalized Images .4 Optical Flow for Arbitrary Motion Models .4 The Generalized Gradient Matrix: a Region Sensitivity Perspective 30 2.1 Condition Theory for Region Sensitivity .2 Condition Theory for Local Transformation Estimation .5 Generalized Corner Detector Functions .1 The Generalized Gradient Matrix: Recapitulation. 40 On the Invariance of the Generalized Gradient Matrix .2 Generalized Corner Detectors Basics. 49 Detector Equivalence Relations .3 Properties of the Generalized Corner Detectors .6 Specialization for 2-Dimensional Single Channel Images. 76 Generalized Detectors Specialization.
81 3 Point Feature Detectors: Experiments 82 3.3 The Experimental Setup .1 Average Percentage of Corresponding Points .2 Repeatability for Geometric and Photometric Distortions .3 Repeatability Rate of Variation .5 Prolegomena for the Design of SGCDFs. 94 4 Drums, Curve Descriptors and Affine Invariant Region Matching109 4.1 The Helmholtz Equation .4 Comparing the Descriptors .3 Achieving Affine Invariance .2 Non Uniform Case .3 Coupling the Normalization Procedure with the Helmholtz Descriptor .1 Performance Evaluation on a Semi-Synthetic Data Set .2 Performance Evaluation on Real Images .5 Conclusions and Future Work .1 The Problem of the Noise Scale. 146 How many iterations?. 146 Constructing the MSSs and Calculating q .2 The Distance Between Two Models .3 The Robustification Procedure .1 Step 1: The MSS Voting Procedure.
151 Thresholding the Histogram .2 Step 2: The Relationship Matrix. 155 Identifying the Histogram Valley. 158 Grouping Equivalent Models .3 Step 3: Parameter Estimation via Robust Statistics Methods 164 5.4 The Robustification Procedure for Generic Models .1 Robustification for Complex Models .2 Handling Multiple Models .1 Line Detection Experiment .2 Line Intersection Experiment .3 Multiple Homographies Experiment .6 Conclusions and Future Work .1 Point Neighborhood Characteristic Structure Detection .1 Detecting the Characteristic Structure. 189 Some Numerical and Computational Considerations.
191 The Algorithm: Design Issues and Practical Implementation 192 6. 196 xiv Real Imagery Experiments .2 Image Registration and Mosaicking .1 Estimating the Transformation Between Images. 204 Establishing Tentative Correspondences. 205 Refining the Correspondences .2 Robust Image Equalization.
217 Constructing the Stitching Curves. 223 Improving the Stitching: Wavelet Based Blending .4 Registration and Mosaic Examples. 227 7 Conclusions and Future Work 233 7.1 Low Level Open Problems. 234 Condition Theory for Other Image Analysis Tasks.
234 Feature Point Localization. 236 Non Rigid Registration .2 System Level Open Problems. 237 Registration Refinement Procedures. 238 Local Photometric Compensation.
238 Constructing Minimum Distortion Panoramas. 240 Automatic Quality Assessment of Registration. 240 A Some Useful Analytical Results 242 A.1 Some Useful Inequalities .2 Some Linear Algebra Facts .2 Spectral Properties of Symmetric Matrices .3 Interlacing Properties of the Singular Values .4 Fast Diagonalization of Symmetric 2 × 2 Matrices .3 Some Optimization Facts. 246 B Condition Theory for Curve Landmarks Detection 249 B.
251 xv C Some Analytical Properties of the Helmholtz Equation 254 List of Acronyms 257 Bibliography 259 xvi List of Tables 2.1 Summary of the fundamental properties of the SGCDFs.1 Summary of the parameters used to implement the detectors de- scribed in Section 2.1 Summary of the parameters used to implement the descriptors used in the SIFT framework and described in Section 6.2 Summary of the RANSAC parameters to identify the point corre- spondences satisfying an homographic transformation. 211 xvii List of Figures 1.1 Some examples of registered image pairs.2 Overview of an image registration system.1 Overview of the framework used to study the generalized corner detector functions.2 Neighborhood transformation example.3 Neighborhood sensitivity example.4 Detector response map.5 Affinely transformed image pair.7 Condition number curves.8 Harris-Stephens detector response.9 Relation between α and φ.11 Spatial projection example.12 Intensity projection example.