Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-02T23:05:57.099Z Has data issue: false hasContentIssue false

9 - Condition theory for image registration and post-registration error estimation

from PART III - Feature Matching and Strategies for Image Registration

Published online by Cambridge University Press:  03 May 2011

By
C. S. Kenney ,
B. S. Manjunath ,
M. Zuliani  and
K. Solanki
Edited by
Jacqueline Le Moigne ,
Nathan S. Netanyahu  and
Roger D. Eastman
C. S. Kenney
Affiliation:
University of California, California
B. S. Manjunath
Affiliation:
University of California, California
M. Zuliani
Affiliation:
University of California, California
K. Solanki
Affiliation:
University of California, California
Jacqueline Le Moigne
Affiliation:
NASA-Goddard Space Flight Center
Nathan S. Netanyahu
Affiliation:
Bar-Ilan University, Israel and University of Maryland, College Park
Roger D. Eastman
Affiliation:
Loyola University Maryland
Get access

Summary

Abstract

We present in this chapter applications of condition theory for image registration problems in a general framework that is easily adapted to a variety of image processing tasks. After summarizing the history and foundations of condition theory, a short analysis is given of computational sensitivity for point correspondence between images with respect to translation, rotation-scale-translation (RST), and affine pixel transforms. Several surprising results follow from this analysis, including the principal result that increasing transform complexity is mirrored by increasing computational sensitivity, i.e., KTrans ≤ KRST ≤ KAffine. The utility of condition-based corner detectors is also seen in the demonstrated equivalence between the translational condition number and the commonly used Shi-Tomasi corner function. These results are supplemented by a short discussion of sensitivity estimation for the computed transform parameters and any resulting registration misalignment.

Introduction

The central issue in image registration is the problem of establishing correspondence between image features, whether they are point features (e.g., corner locations) or extended features (e.g., level sets). Corresponding features then act as input for the process of computing a low-dimensional pixel map between images. The success of this approach depends on the accuracy of the feature correspondence, in the sense that mismatched features can lead to completely erroneous transform estimates. Mismatches may be due to computational constraints that limit the complexity of the feature-matching algorithm or may be intrinsic to the image pair as is the case with identical local features, such as windows in an office building.

Type
Chapter
Information
Image Registration for Remote Sensing , pp. 200 - 214
Publisher: Cambridge University Press
Print publication year: 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Barron, J. L., Fleet, D. J., and Beauchemin, S. (1994). Performance of optical flow techniques. International Journal of Computer Vision, 12, 43–77.CrossRefGoogle Scholar
Beauchemin, S. S. and Barron, J. L. (1996). The computation of optical flow. ACM Computing Surveys, 27, 433–467.CrossRefGoogle Scholar
Bergen, J., Anandan, P., Hanna, K., and Hingorani, R. (1992). Hierarchical model-based motion estimation. In Proceedings of the Second European Conference on Computer Vision. New York: Springer-Verlag, pp. 237–252.Google Scholar
Björck, A. and Hammarling, S. (1983). A Schur method for the square root of a matrix. Linear Algebra and its Applications, 52–53, 127–140.CrossRefGoogle Scholar
Brooks, M., Chojnacki, W., Gaeley, D., and Hengel, A. (2001). What value covariance information in estimating vision parameters? In Proceedings of the Eighth IEEE International Conference on Computer Vision, Vancouver, Canada, pp. 302–308.
Cline, A., Moler, C., Stewart, G., and Wilkinson, J. (1979). An estimate for the condition number of a matrix. SIAM Journal on Numerical Analysis, 16, 368–375.CrossRefGoogle Scholar
Demmel, J. (1987). On condition numbers and the distance to the nearest ill-posed problem. Numerische Mathematik, 51, 251–289.CrossRefGoogle Scholar
Demmel, J. (1988). The probability that a numerical analysis problem is difficult. Mathematics of Computation, 50, 449–480.CrossRefGoogle Scholar
Demmel, J., Diament, B., and Malajovich, G. (2001). On the complexity of computing error bounds. Foundations of Computational Mathematics, 1, 101–125.CrossRefGoogle Scholar
Fischler, M. A. and Bolles, R. C. (1981). Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 24, 381–395.CrossRefGoogle Scholar
Golub, G. H. and Loan, C. F. V. (1989). Matrix Computations. Baltimore, MD: John Hopkins University Press.Google Scholar
Harris, C. and Stephens, M. (1988). A combined corner and edge detector. In Proceedings of the Fourth Alvey Vision Conference, Manchester, UK, pp. 147–151.CrossRef
Hewer, G. A. and Kenney, C. S. (1988). The sensitivity of the stable Lyapunov equation. SIAM Journal on Control and Optimization, 26, 321–344.CrossRefGoogle Scholar
Hewer, G. A., Kenney, C. S., and Kuo, W. (1994). A survey of optical flow methods for tracking problems. In Proceedings of the SPIE Conference on Wavelet Applications, Orlando, FL, Vol. 2242, pp. 561–572.
Hildreth, E. C. (1984). Computations underlying the measurement of visual motion. Artificial Intelligence, 23, 309–354.CrossRefGoogle Scholar
Hinrichsen, D. and Pritchard, A. J. (1986). Stability radii of linear systems. Systems and Control Letters, 7, 1–10.CrossRefGoogle Scholar
Horn, B. K. P. (1986). Robot Vision. Cambridge, MA: MIT Press.Google Scholar
Horn, B. K. P. and Schunck, B. (1981). Determining optical flow. Artificial Intelligence, 17, 185–203.CrossRefGoogle Scholar
Horn, R. A. and Johnson, C. R. (1991). Topics in Matrix Analysis. Cambridge: Cambridge University Press.CrossRefGoogle Scholar
Irani, M., Rousso, B., and Peleg, S. (1994). Computing occluding and transparent motion. International Journal of Computer Vision, 12, 5–16.CrossRefGoogle Scholar
Kanazawa, Y. and Kanatani, K. (2001). Do we really have to consider covariance matrices for image features? In Proceedings of the Eighth IEEE International Conference on Computer Vision, Vancouver, Canada, pp. 301–306.
Kearney, J. K., Thompson, W. B., and Boley, D. L. (1987). Optical flow estimation: An error analysis of gradient-based methods with local optimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 9, 229–244.CrossRefGoogle ScholarPubMed
Kenney, C. S. and Hewer, G. A. (1990). The sensitivity of the algebraic and differential Riccati equations. SIAM Journal on Control and Optimization, 28, 50–69.CrossRefGoogle Scholar
Kenney, C. S. and Laub, A. J. (1989). Condition estimates for matrix functions. Matrix Analysis and Applications, 10, 191–209.CrossRefGoogle Scholar
Kenney, C. S. and Laub, A. J. (1994). Small-sample statistical condition estimates for general matrix functions. SIAM Journal on Scientific Computing, 15, 36–61.CrossRefGoogle Scholar
Kenney, C. S., Manjunath, B. S., Zuliani, M., Hewer, G. A., and Nevel, A. V. (2003). A condition number for point matching with application to registration and post-registration error estimation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25, 1437–14541.CrossRefGoogle Scholar
Kenney, C. S., Zuliani, M., and Manjunath, B. (2005). An axiomatic approach to corner detection. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, San Diego, CA, pp. 191–197.CrossRef
Li, H., Manjunath, B., and Mitra, S. (1995). A contour based approach to multisensor image registration. IEEE Transactions on Image Processing, 4, 320–334.CrossRefGoogle ScholarPubMed
Loan, C. V. (1985). How near is a stable matrix to an unstable matrix?Contemporary Mathematics, 47, 465–477.CrossRefGoogle Scholar
Lucas, B. and Kanade, T. (1981). An iterative image registration technique with an application to stereo vision. In Proceedings of the DARPA Image Understanding Workshop, Washington, DC, pp. 121–130.
Moler, C. B. and Loan, C. F. V. (1978). Nineteen dubious ways to compute the exponential of a matrix. SIAM Review, 20, 801–836.CrossRefGoogle Scholar
Rice, J. R. (1966). A theory of condition. SIAM Journal on Numerical Analysis, 3, 287–310.CrossRefGoogle Scholar
Schmidt, C., Mohr, R., and Baukhage, C. (2000). Evaluation of interest point detectors. International Journal of Computer Vision, 27, 151–172.CrossRefGoogle Scholar
Shi, J. and Tomasi, C. (1994). Good features to track. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Seattle, WA, pp. 593–600.
Stewart, G. W. (1973). Error and perturbation bounds for subspaces associated with certain eigenvalue problems. SIAM Review, 15, 727–764.CrossRefGoogle Scholar
Sundareswaran, V. and Mallat, S. (1992). Multiscale optical flow computation with wavelets. Preprint, Courant Institute of Mathematical Sciences, New York University.
Tanner, J. and Mead, C. (1989). Optical motion sensor. In C. Mead, ed., Analog VLSI and Neural Systems. Reading, MA: Addision-Wesley, pp. 229–255.
Tommasini, T., Fusiello, A., Trucco, E., and Roberto, V. (1998). Making good features track better. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Santa Barbara, CA, pp. 178–183.CrossRef
Trucco, E. and Verri, A. (1998). Introductory Techniques for 3-D Computer Vision. New Jersey: Prentice Hall.Google Scholar
Ward, R. C. (1977). Numerical computation of the matrix exponential with accuracy estimate. SIAM Journal on Numerical Analysis, 14, 600–614.CrossRefGoogle Scholar
Wildes, R., Horvonen, D., Hsu, S., Kumar, R., Lehman, W., Matei, B., and Zhao, W. (2001). Video georegistration: Algorithm and quantitative evaluation. In Proceedings of the Eighth IEEE International Conference on Computer Vision, Vancouver, Canada, pp. 343–350.CrossRef
Wilkinson, J. H. (1961). Error analysis of direct methods of matrix inversion. Journal of the ACM, 8, 281–330.CrossRefGoogle Scholar
Wilkinson, J. H. (1965). The Algebraic Eigenvalue Problem. Oxford: Clarendon Press.Google Scholar
Zheng, Q. and Chellappa, R. (1993). A computational vision approach to image registration. IEEE Transactions on Image Processing, 2, 311–326.CrossRefGoogle ScholarPubMed
Zuliani, M., Kenney, C. S., and Manjunath, B. S. (2004). A mathematical comparison of point detectors. In Proceedings of the Second IEEE Workshop on Image and Video Registration, Washington, DC, p. 172.CrossRef

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×