A survey of image registration techniques

ABSTRACT

Registration is a fundamental task in image processing used to match two or more pictures taken, for example, at different times, from different sensors, or from different viewpoints. Virtually all large systems which evaluate images require the registration of images, or a closely related operation, as an intermediate step. Specific examples of systems where image registration is a significant component include matching a target with a real-time image of a scene for target recognition, monitoring global land usage using satellite images, matching stereo images to recover shape for autonomous navigation, and aligning images from different medical modalities for diagnosis. Over the years, a broad range of techniques has been developed for various types of data and problems. These techniques have been independently studied for several different applications, resulting in a large body of research. This paper organizes this material by establishing the relationship between the variations in the images and the type of registration techniques which can most appropriately be applied. Three major types of variations are distinguished. The first type are the variations due to the differences in acquisition which cause the images to be misaligned. To register images, a spatial transformation is found which will remove these variations. The class of transformations which must be searched to find the optimal transformation is determined by knowledge about the variations of this type. The transformation class in turn influences the general technique that should be taken. The second type of variations are those which are also due to differences in acquisition, but cannot be modeled easily such as lighting and atmospheric conditions. This type usually effects intensity values, but they may also be spatial, such as perspective distortions. The third type of variations are differences in the images that are of interest such as object movements, growths, or other scene changes. Variations of the second and third type are not directly removed by registration, but they make registration more difficult since an exact match is no longer possible. In particular, it is critical that variations of the third type are not removed. Knowledge about the characteristics of each type of variation effect the choice of feature space, similarity measure, search space, and search strategy which will make up the final technique. All registration techniques can be viewed as different combinations of these choices. This framework is useful for understanding the merits and relationships between the wide variety of existing techniques and for assisting in the selection of the most suitable technique for a specific problem.

REFERENCES

• 1: S Alliney , C Morandi, Digital image registration using projections, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.2, p.222-233, March 1986 [doi>10.1109/TPAMI.1986.4767775]
• 2: BA.JSCY. R., AND BROIT, C. 1982 Matching of deformed images. In The 6th International Conference on Pattern Recognition. pp. 351-353.
• 3: Ruzena Bajcsy , Stane Kovačič, Multiresolution elastic matching, Computer Vision, Graphics, and Image Processing, v.46 n.1, p.1-21, April 1989 [doi>10.1016/S0734-189X(89)80014-3]
• 4: Henry S. Baird, Model-based image matching using location, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 5: BALLARD, D. H. 1981. Generalizing the Hough Transform to detect arbitrary shapes. Part. Recog. 13, 2, 111-122.
• 6: Stephen T. Barnard , Martin A. Fischler, Computational Stereo, ACM Computing Surveys (CSUR), v.14 n.4, p.553-572, Dec. 1982 [doi>10.1145/356893.356896]
• 7: BARNEA, D. I., AND SmVERMAN, H. F. 1972. A class of algorithms for fast digital registration. IEEE Trans. Comput. C-21, 179-186.
• 8: BARROW, H. G., TENENBAUM, J. M., BOLLES, R. C., AND WOLF, a. C. 1977. Parametric correspondence and chamfer matching: Two new techtuques for image matching. In Proceedings' of the International Joint Conference ill Artt/)'clal Intelhgence. pp. 659-663.
• 9: BERGSTt~0M, M.,'ETHIUS, B. J., ERIKSSON, L., GREITZ, T., RIBBE, T., AND WI~EN, L. 1981. Head fixation device for reproducible position alignment in transmission CT and positron emission tomography. J. Comput. Assisted Tomogr. 5, (Feb.), 136-141.
• 10: BERNSTEIN, R. 1976. Digital image processing of Earth observation sensor data. IBM J. Res. Devel. 20, (Jan.), 40-67.
• 11: BERNSTEIN, R., AND SILVERMAN. H. 1971. Digital techniques for Earth resource image data processing. In Proceedings of the American Institute of Aeronauttcs and Astronauttcs 8th Annual Meeting, vol. 21. AIAA.
• 12: BtESZK, J. A., AND FRAM, I. 1987. Automatic elastic image registration. In Proceedings of Computers in Cardiology (Leuven, Belgium, Sept.). pp. 3-5.
• 13: BOHM, C., AND GREITZ, T. 1989. The construction of a functional brain atlas--Elimination of bias from anatomical varmtions at PET by reforming 3-D data into a standardized anatomy. In Visualization of Brain Functtons, D. Ottoson and W l~o~t~r~6~ Eet~. Wonlaer C~ren In{~ernational Symposium Series, vol. 53. pp. 137-140.
• 14: BOHM, C., GREITZ, T., KINGSLEY, D., BERGGREN, B. M., AND OLSSON, L. 1983. Adjustable computerized stereotaxic brain atlas for transmission and emission tomography. Amer. J. Neuroradtol. 4, (Mar.), 731 733.
• 15: BRESLER, Y., AND MERttAV, S. J. 1987. Recursive image registratiofi with application to motion estimation. IEEE 7kans. Acoust. Speech Stgnal Proc. ASSP-35, I (Jan.), 70 85.
• 16: BRan', C. 1981. Optimal registrations of deformed images. Ph.D. Dissertation, Univ. of Pennsylvania.
• 17: BUNKE, H., AND SANFELIU, A., EDS. 1990. Syntacttc and Structural Pattern Recognition, Theory and Apphcations. World Ckientific, Teaneck, N.J.
• 18: BURR, D. J. 1981. A dynamic model for image registration. Comput. Graphics Image Proc. 15, 102 112.
• 19: CLOUGH, R. W., AND TOCHER, J. L. 1965. Finite element stiffness matrices for analysis of plates in bending. In Proceeclings of the Conference on Matrix Methods tn Structural Mechanics (Wright-Patterson A.F.B., Ohio). pp. 515-545.
• 20: DANN, R., HOFORD, J., KOVACIC, S., REIVICH, M., AND BAJCSY, R. 1989. Evaluation of elastic matching system for anatomic (CT, MR) and functional (PET) cerebral images, J. Comput. Assi,sted Tomogr. 13, (July/Aug.), 603-611.
• 21: DAVIS, L. S. 1982. Hierarchical Generalized Hough Transform and line segment based Generalized Hough Transforms. F'att. Recog. 15, 277-285.
• 22: E. De Castro , C. Morandi, Registration of translated and rotated images using finite Fourier transforms, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.9 n.5, p.700-703, Sept. 1987 [doi>10.1109/TPAMI.1987.4767966]
• 23: DEGUCHI, K., 1986. R%qstration techniques for partially covered image sequence. In Proceedlngs of the 8th Inter, e, tional Conference on Pattern Recognition (Paris, Oct.). IEEE, New York, pp. 1186 1189.
• 24: DENGLER, J. 1986. Local motion estimation with the dynamic pyramid. In The 8th Internattonal Conference on Pattern Recognition (Paris). pp. 1289-1292.
• 25: DHOND, U. R., AND AGGAP~WAL, J. K. 1989. Structure from stereo A rewew. IEEE Trans. Syst. Man Cybernetics 19, 6 (Nov./Dec.), 1489 1510.
• 26: DUDA, R. O., AND HART, P. E. 1973. Pattern Classtfication and Scene Analysis. John Wiley & Sons, New York.
• 27: EvANs, A. C., BELL, C., MARRETT, S., THOMPSON, C. J., AND HAKIM, A. 1988. Anatomical-functional correlation using an adjustable MRI- based region of interest atlas with positron emission tomography. J. Cerebral Blood Flow Metabol. 8, 513 530.
• 28: FAUGERAS, O., AND PRICE, K. 1981. Semantic deaeriptlon of aa~ia} images usln~ s~ochas~le labeling. IEEE Trans. Patt. Anal. Machine Intell. PAMI-3, (Nov.), 638-642.
• 29: Jan Flusser, An adaptive method for image registration, Pattern Recognition, v.25 n.1, p.45-54, Jan. 1992 [doi>10.1016/0031-3203(92)90005-4]
• 30: George E. Forsythe , Michael A. Malcolm , Cleve B. Moler, Computer Methods for Mathematical Computations, Prentice Hall Professional Technical Reference, 1977
• 31: Fox, P. T., PERLMU'rrER, J. S., AND RAICHLE, M. E. 1985. Stereotactic method of anatomicallocalization for positron emission tomography. J. Comput. Asststed Tomogr. 9, 141 153.
• 32: Fr~NKE, R. 1979. A critical comparison of some methods for interpolation of scattered data. Tech. Rep. NPS-53-79-003, Naval Postgraduate School.
• 33: K. S. Fu , T. Ichikawa, Special Computer Architectures for Pattern Processing, Franklin Book Company, Incorporated, 1982
• 34: GERLOT, P., AND BIZAIS, Y. 1987. Image registration: A review and a strategy for medical applications. In Proceedings of the lOth Internattonal Conference on Informatton Processing in Medical Imaging (Utretcht, Netherlands). pp. 81-89.
• 35: GMUR, E., AND BUNKU, H. 1990. 3-D object recognition based on subgraph matching in polynomial time. In Structural Pattern Analysts. World Scientific, Teaneck, N.J.
• 36: Rafael C. Gonzales , Paul Wintz, Digital image processing (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 37: Ardeshir Goshtasby, Image registration by local approximation methods, Image and Vision Computing, v.6 n.4, p.255-261, November 1988 [doi>10.1016/0262-8856(88)90016-9]
• 38: A. Goshtasby, Piecewise cubic mapping functions for image registration, Pattern Recognition, v.20 n.5, p.525-533, 1987 [doi>10.1016/0031-3203(87)90079-3]
• 39: GOSHTASBY, A. 1986. Piecewise linear mapping functions for image registration. Patt. Recog. 19, 6, 459 466
• 40: GOSHTASBY, A. 1985. Template matching in rotated images. IEEE Trans. Part. Anal. Machine Intell. 7, 3 (May), 338-344.
• 41: GOSHTASBY, A., AND STOCKMAN, G. C. 1985. Point pattern matching using convex hull edges. IEEE Trans. Syst. Man Cybernetics SMC-15, 5 (Sept./Oct.t, 631 637.
• 42: GOSHTASBY, A.. STOCKMAN. G. C., AND PAGE, C. V. 1986. A region-based approach to digital image registration with subpixel accuracy. IEEE Trans. Geoscz. Remote Sensing 24, 3, 390-399
• 43: C~UILLOLIX. Y I.E 1.Q86 A matching algorithm for horizontal motion, application to tracking, in Proceedings of the 8th International IEEE Conference on Pattern Recognttion (Paris, Oct.). IEEE, New York, pp. 1190-1192.
• 44: HALL, E. L. 1979 Computer Image Processtng and Recognitlo,. Academic Press, New York.
• 45: HARALICK, R. M. 1979. Automatic remote sensor image registration. In Toptcs zn Applied Phystcs. Vot. 11, Digital Picture Analysts, A. Rosenfeld, Ed. Springer-Verlag, New York, pp. 5-63.
• 46: M. Herbin , A. Venot , J. Y. Devaux , E. Walter , J. F. Lebruchec, Automated registration of dissimilar images: application to medical imagery, Computer Vision, Graphics, and Image Processing, v.47 n.1, p.77-88, July 1989 [doi>10.1016/0734-189X(89)90055-8]
• 47: HORN, B. K. P. 1989.Robot V~sion. MIT Press, Cambridge, Mass.
• 48: HUMMEL, R., AND ZUCKER, S 1983. On the foundations of relaxation labeling processes. IEEE Trans. Patt. Anal. Machtne Intell. 5, (May), 267 287.
• 49: John R. Jensen, Introductory Digital Image Processing: A Remote Sensing Perspective, Prentice Hall PTR, Upper Saddle River, NJ, 1995
• 50: KANAL, L. N., LAMBIRD, B. A., LAVINE, D., AND STOCKMAN, G. C. 1981. Digital registration of images from similar and dissimilar sensors. In Proceedtngs of the International Conference on Cybernetzcs and Society. pp. 347-351.
• 51: KATURI, R., AND JAIN, R. C 1991. Computer V~ston: Principles. IEEE Computer Society Press, Los Alamitos, Calif.
• 52: KIREMIDJIAN, G. 1987. Issues in image registration. In IEEE Procee&ngs of SPIE: Image Understandtng and the Man-Machine Interface, vol. 758. IEEE, New York, pp 80-87
• 53: KUGHN, C. D., AND HINES, D. C. 1975. The phase correlation image alignment method. In Proceedings of the IEEE 1975 International Conference on Cybernettcs and Society (Sept.). IEEE, New York, pp. 163-165.
• 54: KUHL, F. P., AND GIARDINA, C. R. 1982. Elliptic Fourier features of a closed contour. Comput. Graph. Image Process. 18,236 258.
• 55: LEE, D. J., KRILE, T. F., AND MITRA, S. 1987. Digital registration techniques for sequential Fundus images. In IEEE Procee&ngs of SPIE: Appltcattons of Digital Image Processing X, vo}. 829. IEEE, New York, pp. 293 300.
• 56: MAGHSOODI, R., AND REZAIE, B. 1987. Image registration using a fast adaptive algorithm. In IEEE Proceedmgs of SPIE: Methods of Handling and Processing Imagery, vol. 757. IEEE, New York, pp. 58-63.
• 57: MAGUIRE, G. Q., JR., Noz, M. E., LEE, E. M., AND SHIMPF, J. H. 1985. Correlation methods for tomographic images using two and three dimensional techniques. In Proceedzngs of the 9th Conference of Inl%rraat~on Processing ~n Medical Imaging (Washington, D.C., June 10-14). pp 266-279.
• 58: MAGUIRE, G. Q., JR., NOZ, M. E., AND RUSINEK, H. 1990. Software tools to standardize and automate the correlation of images with and between diagnostic modalities. IEEE Comput. Graph. Appl.
• 59: Henri Maître , Yifeng Wu, Improving dynamic programming to solve image registration, Pattern Recognition, v.20 n.4, p.443-461, 1987 [doi>10.1016/0031-3203(87)90071-9]
• 60: MEDIONI, G., AND NEVATIA, R. 1984. Matching images using linear features. IEEE Trans. Patt. Anal. Machine Intell. PAMI-6, 675-685.
• 61: Michael Merickel, 3D reconstruction: the registration problem, Computer Vision, Graphics, and Image Processing, v.42 n.2, p.206-219, May, 1988 [doi>10.1016/0734-189X(88)90164-8]
• 62: Evangelos E. Milios, Shape matching using curvature processes, Computer Vision, Graphics, and Image Processing, v.47 n.2, p.203-226, August 1989 [doi>10.1016/S0734-189X(89)80007-6]
• 63: MITICHE, A., AND AGGARWAL, J. K. 1983. Contour registration by shape-specific points fbr shape matching. Comput. Vision Graph. Image Process. 22,296-408.
• 64: MOHR, R., PAVLIDIS, T., AND SANFELm, A. 1990. Structural Pattern Analysis. World Scientific, Teaneck, N.J.
• 65: MOr~VEC, H. 1981. Rover visual obstacle avoidance. In Proceedings of the 7th International Conference on Arttficial Intelligence (Vancouver, B.C., Canada, Aug.). pp. 785-790.
• 66: MORT, M. S., AND SRINATH, M. n. 1988. Maximum likelihood image registration with subpixel accuracy. In IEEE Proceedings of SPIE: Applications of Digital Image Processing, vol. 974. IEEE, New York, pp. 38-43.
• 67: NACK, M. L. 1977. Rectification and registration of digital images and the effect of cloud detection. In Proceedings of Machine Processing' of Remotely Sensed Data. pp. 12-23.
• 68: C Nahmias , E S Garnett, Correlation between CT, NMR and PT. Findings in the brain, Proceedings of the NATO Advanced Study Institute (NATO ASI Series) on Pictorial information systems in medicine, p.507-514, February 1986, Braulage, Germany
• 69: Noz, M. E., AND MAC;UmE, G. Q., JR. 1988. QSH: A minimal but highly portable image display and processing Toolkit. Comput. Methods Program. Biomed. 27, 11 (Nov. 1988), 229 240.
• 70: OHTA, Y., TAKANO, K., AND IKEDA, K. 1987. A highspeed stereo matching system based on dynamic programming. In Proceedings of the International Conference in Computer Vision (London, England). pp. 335-342.
• 71: PAAR, G., AND KROPATSCH, W. G. 1990. Hierarchical cooperation between numerical and symbolic image representations. In Structural Pattern Analysts. World Scientific, Teaneck, N.J.
• 72: M. Parizeau , R. Plamondon, A Comparative Analysis of Regional Correlation, Dynamic Time Warping, and Skeletal Tree Matching for Signature Verification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.7, p.710-717, July 1990 [doi>10.1109/34.56215]
• 73: PAVLiDIS, T. 1978. Survey: A review of algorithms for shape analysis. Comput. Graph. Image Process. 7, 243 258.
• 74: William K. Pratt, Digital image processing, John Wiley & Sons, Inc., New York, NY, 1978
• 75: PEL~, E. ET AL. 1987. Feature-based registration of retinal images. IEEE Trans. Med. Imaging MI-6, 3 (Sept.), 272-278.
• 76: PELIZARRI, C. A., CHEN, G. T. Y., SPELBRING, D. R., WEICHSELBAUM, R. R., AND CHEN. C. T. 1989. Accurate three-dimensional registration of CT, PET and/or MR images of the brain. J. Cornput. Assisted Tomogr. 13, (Jan./Feb.), 20 26.
• 77: PRmE, K. E. 1985. Relaxation matching techniques A comparison. IEEE Trans. Patt. Anal. Machine Intell. 7, 5 (Sept.), 617 623.
• 78: RANADE, S., AND ROSENFELD, A. 1980. Point pattern matching by relaxation. Patt. Recog. 12, 269-275.
• 79: RATIB, O., BIDAUT, L., SCtJELBERT, H. R., AND PHELPS, M. E. 1988. A new technique for elastic registration of tomographic images. In IEEE Proceedings of SPIE: Medical Imaging H, vol. 914. IEEE, New York, pp. 452-455.
• 80: Azriel Rosenfeld , Avinash C. Kak, Digital Picture Processing, Academic Press, Inc., Orlando, FL, 1982
• 81: SANFELm, A. 1990. Matching complex structures: The cyclic-tree representation scheme. In Structural Pattern Analysis. World Scientific, Teaneck, N.J.
• 82: SHAPIRO, L. G., AND HARArICK, R. M. 1990. Matching relational structures using discrete relaxation. In Syntactic and Structural Pattern Recognition, Theory and Apphcattons. World cientific, Teaneck, N.J.
• 83: SINGH,-M., FREI, W., SHIBATA, T., HUTH, G. C., AND TELFER, N. E. 1979. A digital technique for accurate change detection in nuclear medical images With application to myocardial perfusion studies using Thallium-201. IEEE Trans. Nuclear Sci. NS-26, 1 (Feb.).
• 84: SLAME, C. C., ED. 1980. Manual of Photogrammetry, 4th ed. American Society of PhotogTammetry, Falls Church, Va.
• 85: F. Solina , R. Bajcsy, Recovery of Parametric Models from Range Images: The Case for Superquadrics with Global Deformations, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.2, p.131-147, February 1990 [doi>10.1109/34.44401]
• 86: STOCKMAN, G. C., KOPSTEIN, S., AND BENETT, S. 1982. Matching images to models for registration and object detection via clustering. IEEE Trans. Patt. Anal. Machine Intell. 4, 229-241.
• 87: M. R. Stytz , G. Frieder , O. Frieder, Three-dimensional medical imaging: algorithms and computer systems, ACM Computing Surveys (CSUR), v.23 n.4, p.421-499, Dec. 1991 [doi>10.1145/125137.125155]
• 88: Paul Suetens , Pascal Fua , Andrew J. Hanson, Computational strategies for object recognition, ACM Computing Surveys (CSUR), v.24 n.1, p.5-62, March 1992 [doi>10.1145/128762.128763]
• 89: SVEDLOW, M., McGILLEM, C. D., AND ANUTA, P. E. 1976. Experimental examination of mmilarity measures and preprocessing methods used for image registration. In The Symposium on Machine Processing of Remotely Sensed Data (Westville, Ind., June). pp. 4A-9.
• 90: TERZOPOULOS, D., WITKIN, A., AND KASS, M. 1987. Energy constraints on deformable models: Recovering shape and non-rigid motion. In Proceedtngs AAAI 87 (July), voI. 2. AAAI, Menlo Park, Calif., pp. 755 760.
• 91: THOMAS, I. L., BENNING, V. M., AND CHING, N. P. 1986. Classzficatzon of Remotely Sensed Images. Adam Hilger, Bristol, England.
• 92: TON, J., AND JAIN, A. K. 1989. Registering Landsat images by point matching. IEEE Trans. Geosc~. Remote Sensing 27, (Sept.), 642 651.
• 93: VAN DEN ELSEN, P A., POL, E.-I. D., AND VIERGEVER, M. A. 1992. Medical image matching' A review with classification. IEEE Eng. Med. Brol , in press.
• 94: VAN WIE, P, AND STEIN, M. 1977 A LANDSAT digStal image rectification system. IEEE Trans. Geoscr. Electr. GE-15, 3 (July), 130 137.
• 95: A Venot , J F. Lebruchec , J C. Roucayrol, A new class of similarity measures for robust image registration, Computer Vision, Graphics, and Image Processing, v.28 n.3, p.176-184, Nov. 1984 [doi>10.1016/S0734-189X(84)80020-1]
• 96: W~DROW, B. 1973. The rubber mask technique, Part I and II. Putt Recog. 5, 3, 175-211.
• 97: George Wolberg, Digital Image Warping, IEEE Computer Society Press, Los Alamitos, CA, 1994
• 98: G. Wolberg , T. E. Boult, Separable image warping with spatial lookup tables, Proceedings of the 16th annual conference on Computer graphics and interactive techniques, p.369-378, July 1989
• 99: WONG, A. K. C., AND YOU, M. 1985. Entropy and distance of random graphs with application to structural pattern recogmtion. IEEE Trans'. Port Anal. Machine Intell. PAMI-7, 5 (Sept.), 599 609.
• 100: WONG, R. Y. 1977. Sensor transformations. IEEE Trans. Syst. Man CyberTzetzes SMC-7, 12 (Dec.), 836-840.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.3 Enhancement
          Subjects: Registration

Additional Classification:
  A. General Literature

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.8 Scene Analysis
          Subjects: Sensor fusion
  I.5 PATTERN RECOGNITION

General Terms:
Algorithms, Design, Measurement, Performance

Keywords:
image registration, image warping, rectification, template matching