Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Introduction Read chapter Read first chapter

2012 | OriginalPaper | Chapter

9. Transformation Functions

Author : Prof. A. Ardeshir Goshtasby

Published in: Image Registration

Publisher: Springer London

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The problem of image warping or image transformation for the purpose of aligning/overlaying images is discussed. First, global transformations, such as rigid, similarity, affine, projective, cylindrical, and spherical mapping are reviewed. Then, adaptive transformations including explicit, implicit, and parametric functions are reviewed. Properties of various transformations are explored and a guide to their selection is provided. Finally, performances of ten popular adaptive transformation functions in the registration of various types of images are determined and compared. The transformations tested are multiquadric, thin-plate (surface) spline, compactly supported radial basis functions, local weighted mean, moving least squares, piecewise linear, Loop’s subdivision, parametric Shepard, weighted linear, and interpolating implicit methods.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Robust Parameter Estimation
next chapter Image Resampling and Compositing
Literature
1.
Adamson, A., Alexa, M.: On normals and projection operators for surfaces defined by point sets. In: Eurographics Symposium on Point-based Graphics, pp. 149–155 (2004)
2.
Akima, H.: A method of bivariate interpolation and smooth surface fitting for irregularly distributed data points. ACM Trans. Math. Softw. 4, 148–159 (1978) MATHCrossRef
3.
Arge, E., Dæhlen, M., Tveito, A.: Approximation of scattered data using smooth grid functions. J. Comput. Appl. Math. 59, 191–205 (1995) MathSciNetMATHCrossRef
4.
Belytschko, T., Krongauz, Y., Organ, D., Fleming, M., Krysl, P.: Meshless methods: An overview and recent developments. Comput. Methods Appl. Mech. Eng. 139, 3–47 (1996) MATHCrossRef
5.
Bertram, M., Barnes, J.C., Hamann, B., Joy, K.I., Pottmann, H., Wushour, D.: Piecewise optimal triangulation for the approximation of scattered data in the plane. Comput. Aided Geom. Des. 17, 767–787 (2000) MathSciNetMATHCrossRef
6.
Bookstein, F.L.: Principal warps: Thin-plate splines and the decomposition of deformations. IEEE Trans. Pattern Anal. Mach. Intell. 11(6), 567–585 (1989) MATHCrossRef
7.
Bozzini, M., Lenarduzzi, L., Rossini, M.: Polyharmonic splines: An approximation method for noisy scattered data of extra-large size. Appl. Math. Comput. 216, 317–331 (2010) MathSciNetMATHCrossRef
8.
Brown, J.L.: Vertex based data dependent triangulations. Comput. Aided Geom. Des. 8, 239–251 (1991) CrossRef
9.
Buhmann, M.D.: A new class of radial basis functions with compact support. Math. Comput. 70(233), 307–318 (2000) MathSciNetCrossRef
10.
11.
Carr, J.C., Beatson, R.K., Cherrie, J.B., Mitchell, T.J., Fright, W.R., McCallum, B.C., Evans, T.R.: Reconstruction and representation of 3D objects with radial basis functions. In: Proc. SIGGRAPH ’01 Conf., pp. 67–76 (2001) CrossRef
12.
Chang, L.H.T., Said, H.B.: A C 2 triangular patch for the interpolation of functional scattered data. Comput. Aided Des. 29(6), 407–412 (1997) CrossRef
13.
Choi, Y.-L., Yoo, K.-W., Cho, N.-I., Lee, J.-H.: Line based image matching method. US Patent 9,884,079, Filed 20 Jun. 2001, Patented 29 Aug. 2002
14.
Chui, C.K., Lai, M.-J.: Filling polygonal holes using C 1 cubic triangular spline patches. Comput. Aided Geom. Des. 17, 297–307 (2000) MathSciNetMATHCrossRef
15.
Constantini, P., Manni, C.: On a class of polynomial triangular macro-elements. Comput. Appl. Math. 73, 45–64 (1996) MathSciNetCrossRef
16.
Dahmen, W., Meyling, R.H.J.G., Ursem, J.H.M.: Scattered data interpolation by bivariate C 1-piecewise quadratic functions. Approx. Theory Appl. 6(3), 6–29 (1990) MathSciNetMATH
17.
Davydov, O., Schumaker, L.L.: Stable approximation and interpolation with C1 quartic bivariate splines. SIAM J. Numer. Anal. 39(5), 1732–1748 (2002) MathSciNetMATHCrossRef
18.
Doo, D.W.H.: A subdivision algorithm for smoothing down irregular shaped polyhedrons. In: Proc. Interactive Techniques in Computer Aided Design, vol. 1, pp. 157–165 (1978)
19.
Doo, D., Sabin, M.: Behavior of recursive division surfaces near extraordinary points. In: Computer Aided Design, pp. 356–360 (1978)
20.
Duchon, J.: Splines minimizing rotation-invariant seminorms in Sobolov spaces. In: Constructive Theory of Functions of Several Variables. Lecture Notes in Math., vol. 571, pp. 85–100. Springer, Berlin (1977) CrossRef
21.
Dyn, N., Levin, D., Rippa, S.: Algorithms for the construction of data dependent triangulation. In: Mason, J.S., Cox, M.G. (eds.) Algorithms for Approximation II, pp. 185–192. Chapman and Hall, New York (1988)
22.
Dyn, N., Levin, D., Gregory, J.A.: A butterfly subdivision scheme for surface interpolation with tension control. ACM Trans. Graph. 9(2), 160–169 (1990) MATHCrossRef
23.
Floater, M.S., Iske, A.: Multistep scattered data interpolation using compactly supported radial basis functions. J. Comput. Appl. Math. 73, 65–78 (1996) MathSciNetMATHCrossRef
24.
Fornefett, M., Rohr, K., Stiehl, H.S.: Radial basis functions with compact support for elastic registration of medical images. Image Vis. Comput. 19, 87–96 (2001) CrossRef
25.
Franke, R.: Scattered data interpolation: Tests of some methods. Math. Comput. 38(157), 181–200 (1982) MathSciNetMATH
26.
27.
28.
Franke, R., Schumaker, L.L.: A bibliography of multivariate approximation. In: Chui, C., Schumaker, L., Utrerus, F. (eds.) Topics in Multivariate Approximation, pp. 79–98. Academic Press, San Diego (1987)
29.
Franke, R., Hagen, H., Nielson, G.M.: Least squares surface approximation to scattered data using multiquadric functions. Adv. Comput. Math. 2, 81–99 (1994) MathSciNetMATHCrossRef
30.
Goodman, T.N.T., Said, H.B., Chang, L.H.T.: Local derivative estimation for scattered data interpolation. Appl. Math. Comput. 68, 41–50 (1995) MathSciNetMATHCrossRef
31.
Goshtasby, A.: Piecewise linear mapping functions for image registration. Pattern Recognit. 19(6), 459–466 (1986) CrossRef
32.
Goshtasby, A.: Piecewise cubic mapping functions for image registration. Pattern Recognit. 20(5), 525–533 (1987) CrossRef
33.
Goshtasby, A.: Registration of image with geometric distortion. IEEE Trans. Geosci. Remote Sens. 26(1), 60–64 (1988) CrossRef
34.
Goshtasby, A.: A weighted linear method for approximation of irregularly spaced data. In: Lucian, M.M., Neamtu, M. (eds.) Geometric Modeling and Computing, pp. 285–294. Nashboro Press, Brentwood (2004)
35.
Goshtasby, A.: Surface approximation to scattered lines. Comput-Aided Des. Appl. 4(1–4), 277–286 (2007)
36.
Goshtasby, A.: Registration of multi-view images. In: LeMoigne, J., Netanyahoo, N.S., Eastman, R.D. (eds.) Image Registration for Remote Sensing, pp. 153–178. Cambridge University Press, Cambridge (2011) CrossRef
37.
Goshtasby, A.: Design and recovery of 2-D and 3-D shapes using rational Gaussian curves and surfaces. Int. J. Comput. Vis. 10(3), 233–256 (1993) MathSciNetCrossRef
38.
39.
Greiner, G., Kolb, A., Riepl, A.: Scattered data interpolation using data dependent optimization techniques. Graph. Models 64, 1–18 (2002) MATHCrossRef
40.
Grosse, E.: A catalogue of algorithms for approximation. In: Mason, J., Cox, M. (eds.) Algorithms for Approximation II, pp. 479–514. Chapman and Hall, London (1990)
41.
Harder, R.L., Desmarais, R.N.: Interpolation using surface splines. J. Aircr. 9(2), 189–191 (1972) CrossRef
42.
Hardy, R.L.: Multiquadric equations of topography and other irregular surfaces. J. Geophys. Res. 76(8), 1905–1915 (1971) CrossRef
43.
Hardy, R.L.: Theory and applications of the multiquadric-biharmonic method—20 years of discovery—1969–1988. Comput. Math. Appl. 19(8/9), 163–208 (1990) MathSciNetMATHCrossRef
44.
Hoppe, H., DeRose, T., Duchamp, T., Halstead, M., Jin, H., McDonald, J., Schweitzer, J., Stuetzle, W.: Piecewise smooth surface reconstruction. In: SIGGRAPH’94: Proc. 21st Annual Conference on Computer Graphics and Interactive Techniques, pp. 295–302 (1994) CrossRef
45.
46.
Kamgar-Parsi, B., Kamgar-Parsi, B.: Algorithms for matching 3D line sets. IEEE Trans. Pattern Anal. Mach. Intell. 26(5), 582–593 (2004) CrossRef
47.
Kansa, E.J., Carlson, R.E.: Improved accuracy of multiquadric interpolation using variable shape parameters. Comput. Math. Appl. 24, 99–120 (1992) MathSciNetMATHCrossRef
48.
Klucewicz, I.M.: A piecewise C 1 interpolant to arbitrarily spaced data. Comput. Graph. Image Process. 8, 92–112 (1978) CrossRef
49.
Lai, M.-J.: Convex preserving scattered data interpolation using bivariate C 1 cubic spline. J. Comput. Appl. Math. 119, 249–258 (2000) MathSciNetMATHCrossRef
50.
Lai, M.-J., Wenston, P.: L 1 spline methods for scattered data interpolation and approximation. Adv. Comput. Math. 21, 293–315 (2004) MathSciNetMATHCrossRef
51.
Lancaster, P.: Moving weighted least-squares methods. In: Sahney, B.N. (ed.) Polynomial and Spline Approximation, pp. 103–120 (1979)
52.
Lancaster, P., Šalkauskas, K.: Surfaces generated by moving least squares methods. Math. Comput. 37(155), 141–158 (1981) MATHCrossRef
53.
Lancaster, P., Šalkauskas, K.: Curve and Surface Fitting: An Introduction. Academic Press, San Diego (1986), pp. 55–62, 225–244 MATH
54.
Lawson, C.L.: Software for C 1 surface interpolation. In: Rice, J.R. (ed.) Mathematical Software III, pp. 161–194. Academic Press, San Diego (1977)
55.
Lazzaro, D., Montefusco, L.B.: Radial basis functions for the multivariate interpolation of large scattered data sets. J. Comput. Appl. Math. 140, 521–536 (2002) MathSciNetMATHCrossRef
56.
Lee, D.T., Schachter, B.J.: Two algorithms for constructing a Delaunay triangulation. Int. J. Comput. Inf. Sci. 9, 219–242 (1980) MathSciNetMATHCrossRef
57.
Lee, S., Wolberg, G., Shin, S.Y.: Scattered data interpolation with multilevel B-splines. IEEE Trans. Vis. Comput. Graph. 3(3), 228–244 (1997) CrossRef
58.
Levin, D.: The approximation power of moving least-squares. Math. Comput. 67(224), 1517–1531 (1998) MATHCrossRef
59.
60.
Loop, C.: Smooth subdivision surfaces based on triangles. Master’s thesis, Department of Mathematics, University of Utah (1987)
61.
Lorensen, W.E., Cline, H.E.: Marching cubes: A high resolution 3D surface construction algorithm. In: Proc. SIGGRAPH, pp. 71–78. ACM Press/ACM SIGGRAPH, New York (1992)
62.
Lu, H., Schumaker, L.L.: Monotone surfaces to scattered data using C 1 piecewise cubics. SIAM J. Numer. Anal. 34(2), 569–585 (1997) MathSciNetMATHCrossRef
63.
Luo, Z., Peng, X.: A C 1-rational spline in range restricted interpolation of scattered data. J. Comput. Appl. Math. 194, 255–266 (2006) MathSciNetMATHCrossRef
64.
Maillot, J., Stam, J.: A unified subdivision scheme for polygonal modeling. In: Chalmers, A., Rhyne, T.-M. (eds.) EUROGRAPHICS, vol. 20(3) (2001)
65.
Marinov, M., Kobbelt, L.: Optimization methods for scattered data approximation with subdivision surfaces. Graph. Models 67, 452–473 (2005) CrossRef
66.
67.
68.
Meijering, E.: A chronology of interpolation: From ancient astronomy to modern signal and image processing. Proc. IEEE 90(3), 319–342 (2002) CrossRef
69.
Meinguet, J.: An intrinsic approach to multivariate spline interpolation at arbitrary points. In: Sahney, B.N. (ed.) Polynomial and Spline Approximation, pp. 163–190. Reidel, Dordrecht (1979)
70.
Nejhum, S.M.S., Chi, Y.-T., Yang, M.-H.: Higher-dimensional affine registration and vision applications. IEEE Trans. Pattern Anal. Mach. Intell. 33(7), 1324–1338 (2011) CrossRef
71.
Nielson, G.M.: Dual marching cubes. In: Proc. IEEE Visualization, pp. 489–496 (2004)
72.
Ohtake, Y., Belyaev, A., Seidel, H.-P.: 3D scattered data interpolation and approximation with multilevel compactly supported RBFs. Graph. Models 67, 150–165 (2005) MATHCrossRef
73.
74.
Peters, J., Reif, U.: The simplest subdivision scheme for smoothing polyhedra. ACM Trans. Graph. 16(4), 420–431 (1997) CrossRef
75.
Powell, M.J.D.: Radial basis functions for multivariate interpolation: A review. In: Mason, J.C., Cox, M.G. (eds.) Algorithms for Approximation, pp. 143–167. Clarendon Press, Oxford (1987)
76.
77.
Qu, R., Agarwal, R.P.: Smooth surface interpolation to scattered data using interpolatory subdivision algorithms. Comput. Math. Appl. 32(3), 93–110 (1996) MathSciNetMATHCrossRef
78.
79.
Renka, R.J.: Algorithm 833: CSRFPAXK—Interpolation of scattered data with a C 1 convexity-preserving surface. ACM Trans. Math. Softw. 30(2), 200–211 (2004) MathSciNetMATHCrossRef
80.
Renka, R.J., Brown, R.: Algorithm 790: CSHEP2D: Cubic Shepard method for bivariate interpolation of scattered data. ACM Trans. Math. Softw. 25(1), 70–73 (1999) MATHCrossRef
81.
Renka, R.J., Brown, R.: Algorithm 791: TSHEP2D: Cosine series Shepard method for bivariate interpolation of scattered data. ACM Trans. Math. Softw. 25(1), 74–77 (1999) MATHCrossRef
82.
Renka, R.J., Brown, R.: Algorithm 792: Accuracy tests of ACM algorithms for interpolation of scattered data in the plane. ACM Trans. Math. Softw. 25(1), 78–94 (1999) MATHCrossRef
83.
Rippa, S.: Scattered data interpolation using minimum energy Powell-Sabin elements and data dependent triangulations. Numer. Algorithms 5, 577–587 (1993) MathSciNetMATHCrossRef
84.
Rivlin, T.J.: Least-squares approximation. In: An Introduction to the Approximation of Functions, pp. 48–61. Dover, New York (1969)
85.
Rohr, K., Stiehl, H.S., Sprengel, R., Buzug, T.M., Weese, J., Kuhn, M.H.: Landmark-based elastic registration using approximating thin-plate splines. IEEE Trans. Med. Imaging 20(6), 526–534 (2001) CrossRef
86.
Savchenko, V.V., Pasko, A.A., Okunev, O.G., Kunii, T.L.: Function representation of solids reconstructed from scattered surface points and contours. Comput. Graph. Forum 14(4), 181–188 (1995) CrossRef
87.
Schagen, I.P.: The use of stochastic processes in interpolation and approximation. Int. J. Comput. Math., Sect. B 8, 63–76 (1980) MathSciNetMATHCrossRef
88.
Scheib, V., Haber, J., Lin, M.C., Seidel, H.-P.: Efficient fitting and rendering of large scattered data sets using subdivision surfaces. Eurographics 21(3), 353–362 (2002)
89.
Schmidt, J.W.: Scattered data interpolation applying regional C 1 splines on refined triangulations. Math. Mech. 80(1), 27–33 (2000) MathSciNetMATH
90.
Schröder, P., Zorin, D.: Subdivision for modeling and animation. SIGGRAPH Course No. 36 Notes (1998)
91.
Schumaker, L.L.: Triangulation methods. In: Chui, C.K., Schumaker, L.L., Utreras, F. (eds.) Topics in Multivariate Approximation, pp. 219–232. Academic Press, San Diego (1987)
92.
93.
Schumaker, L.L.: Multivariate spline bibliography. In: Chui, C., Neamtu, M., Schumaker, L.L. (eds.) Approximation Theory XI: Gatlinburg. Nashboro Press, Brentwood (2005)
94.
Schumaker, L.L., Speleers, H.: Nonnegativity preserving macro-element interpolation of scattered data. Comput. Aided Geom. Des. 27(3), 245–261 (2010) MathSciNetMATHCrossRef
95.
Schweitzer, J.E.: Analysis and application of subdivision surfaces. Ph.D. Dissertation, University of Washington, Seattle (1996)
96.
Shepard, D.: A two-dimensional interpolation function for irregularly spaced data. In: Proc. 23rd Nat’l Conf. ACM, pp. 517–524 (1968)
97.
Shirman, L.A., Sequin, C.H.: Local surface interpolation with shape parameters between adjoining Gregory patches. Comput. Aided Geom. Des. 7, 375–388 (1990) MathSciNetMATHCrossRef
98.
Stam, J.: On subdivision schemes generalizing uniform B-spline surfaces of arbitrary degree. Comput. Aided Geom. Des. 18, 383–396 (2001) MathSciNetMATHCrossRef
99.
100.
Turk, G., O’Brien, J.F.: Modeling with implicit surfaces that interpolate. ACM Trans. Graph. 21(4), 855–873 (2002) CrossRef
101.
Wang, L., Neumann, U., You, S.: Image matching using line signature. US Patent 12,486,506, Filed 17 Jun. 2009, Patented 23 Dec. 2010
102.
Wendland, H.: Piecewise polynomial, positive definite and compactly supported radial functions of minimal degree. Adv. Comput. Math. 4, 389–396 (1995) MathSciNetMATHCrossRef
103.
Zorin, D.: Subdivision and multiresolution surface representations. Ph.D. Dissertation, Caltech, Pasadena (1997)
104.
Zorin, D., Schröder, P., Sweldens, W.: Interpolating subdivision for meshes with arbitrary topology. In: Computer Graphics Proceedings (SIGGRAPH 96), pp. 189–192 (1996)
Metadata
Title
Transformation Functions
Author
Prof. A. Ardeshir Goshtasby
Copyright Year
2012
Publisher
Springer London
Book
Image Registration

Print ISBN: 978-1-4471-2457-3

Electronic ISBN: 978-1-4471-2458-0

Copyright Year: 2012

DOI
https://doi.org/10.1007/978-1-4471-2458-0_9

Premium Partner

    Image Credits