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

7. Point Pattern Matching

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

Various point pattern matching algorithms are reviewed and compared. Among the matching algorithms discussed are random sample and consensus (RANSAC), graph-based, feature-based, clustering-based, invariance-based, axis of minimum inertia-based, relaxation-based, and spectral graph theory-based algorithms. To speed up the matching process, the coarse-to-fine search strategy is also discussed and its use in matching of point patterns with nonlinear geometric differences is demonstrated. Also included in this chapter are detailed matching algorithms and methods to determine their performances.

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 Feature Selection and Heterogeneous Descriptors
next chapter Robust Parameter Estimation
Literature
1.
Ahuja, N.: Dot pattern processing using Voronoi neighborhoods. IEEE Trans. Pattern Anal. Mach. Intell. 4(3), 336–343 (1982) MathSciNetCrossRef
2.
Bolles, R.C.: Robust feature matching through maximal cliques. In: SPIE Conf. Imaging Applications for Automated Industrial Inspection and Assembly, vol. 182, pp. 140–149 (1979) CrossRef
3.
4.
Bron, C., Kerbosch, J.: Algorithm 547: Finding all cliques of an undirected graph. Commun. ACM 16(9), 575–577 (1973) MATHCrossRef
5.
Capel, D.: An effective bail-out test for RANSAC consensus scoring. In: Proc. British Machine Vision Conf., pp. 629–638 (2005)
6.
Carcassoni, M., Hancock, E.R.: Point pattern matching with robust spectral correspondence. In: IEEE Conf. Computer Vision and Pattern Recognition, vol. 1, pp. 649–655 (2000)
7.
Carcassoni, M., Hancock, E.R.: Spectral correspondence for point pattern matching. Pattern Recognit. 36, 193–204 (2003) MATHCrossRef
8.
Chang, S.-H., Cheng, F.-H., Hsu, W.-H., Wu, G.-Z.: Fast algorithm for point pattern matching: Invariant to translations, rotations, and scale changes. Pattern Recognit. 30(2), 311–320 (1997) CrossRef
9.
Cheng, F.-H.: Point pattern matching algorithm invariant to geometrical transformation and distortion. Pattern Recognit. Lett. 17, 1429–1435 (1996) MATHCrossRef
10.
Choi, O., Kweon, I.S.: Robust feature point matching by preserving local geometric consistency. Comput. Vis. Image Underst. 113, 726–742 (2009) CrossRef
11.
Chum, O., Matas, J.: Matching with PROSAC–progressive sample consensus. In: Proc. Computer Vision and Pattern Recognition, vol. 1, pp. 220–226 (2005)
12.
Chum, O., Matas, J.: Optimal randomized RANSAC. IEEE Trans. Pattern Anal. Mach. Intell. 30(8), 1472–1482 (2008) CrossRef
13.
Chung, F.R.K.: Spectral Graph Theory, 2nd edn., pp. 1–22. Am. Math. Soc., Providence (1997) MATH
14.
Coelho, C., Heller, A., Mundy, J.L., Forsyth, D.A., Zisserman, A.: An experimental evaluation of projective invariants. In: Mundy, J.L., Zisserman, A. (eds.) Geometric Invariance in Computer Vision, pp. 87–104. The MIT Press, Cambridge (1992)
15.
Denton, J.A., Beveridge, J.R.: An algorithm for projective point matching in the presence of spurious points. Pattern Recognit. 40, 586–595 (2007) MATHCrossRef
16.
17.
Fang, T.J., Huang, Z.H., Kanal, L.N., Lavine, B.D., Stockman, G., Xiong, F.L.: Three-dimensional object recognition using a transform clustering technique. In: Proc. 6th Int’l Conf. Pattern Recognition, pp. 678–681 (1982)
18.
Fischler, M.A., Bolles, R.C.: Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 24(6), 381–395 (1981) MathSciNetCrossRef
19.
Forsyth, D., Ponce, J.: Computer Vision: A Modern Approach. Prentice Hall, New York (2002)
20.
Goshtasby, A., Page, C.V.: Image matching by a probabilistic relaxation labeling process. In: Proc. 7th Int’l Conf. Pattern Recognition, vol. 1, pp. 307–309 (1984)
21.
Goshtasby, A., Stockman, G.C.: Point pattern matching using convex hull edges. IEEE Trans. Syst. Man Cybern. 15(5), 631–637 (1985) CrossRef
22.
Grimson, W.E.L., Huttenlocher, D.P.: On the sensitivity of geometric hashing. In: Proc. 3rd Int’l Conf. Computer Vision, pp. 334–338 (1990)
23.
Hong, J., Tan, X.: A new approach to point pattern matching. In: Proc. 9th Int’l Conf. Pattern Recognition, vol. 1, pp. 82–84 (1988)
24.
Hsiao, E., Collet, A., Hebert, M.: Making specific features less discriminative to improve point-based 3D object recognition. In: Int’l Conf. Computer Vision and Pattern Recognition, pp. 2653–2660 (2010)
25.
Kuhn, H.W.: The Hungarian method for the assignment problem. Nav. Res. Logist. Q. 2, 83–97 (1955) CrossRef
26.
Lamdan, Y., Wolfson, H.J.: Geometric hashing: A general and efficient model-based recognition scheme. In: Proc. 2nd Int’l Conf. Computer Vision, pp. 238–249 (1988)
27.
Lamdan, Y., Wolfson, H.J.: On the error analysis of geometric hashing. In: Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 22–27 (1991)
28.
Lavine, D., Lambird, B.A., Kanal, L.N.: Recognition of spatial point patterns. Pattern Recognit. 16(3), 289–295 (1983) MATHCrossRef
29.
Lee, J.-H., Won, C.-H.: Topology preserving relaxation labeling for nonrigid point matching. IEEE Trans. Pattern Anal. Mach. Intell. 33(2), 427–432 (2011) CrossRef
30.
Leordeanu, M., Hebert, M.: A spectral technique for correspondence problems using pairwise constraints. In: Proc. Int’l Conf. Computer Vision, vol. 2, pp. 1482–1489 (2005)
31.
Matas, J., Chum, O.: Randomized RANSAC with Td:d test. Image Vis. Comput. 22(10), 837–842 (2004) CrossRef
32.
Mundy, J.L., Zisserman, A.: Geometric Invariance in Computer Vision. The MIT Press, Cambridge (1992)
33.
Nister, D.: Preemptive RANSAC for live structure and motion estimation. In: Proc. Int’l Conf. Computer Vision, Oct., vol. 1, pp. 199–206 (2003) CrossRef
34.
Ogawa, H.: Labeled point pattern matching by fuzzy relaxation. Pattern Recognit. 17(5), 569–573 (1984) CrossRef
35.
Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs (1982) MATH
36.
Pilu, M.: A direct method for stereo correspondence based on singular value decomposition. In: IEEE Conf. Computer Vision and Pattern Recognition, pp. 261–266 (1997)
37.
Rabin, J., Delon, J., Gousseau, Y.: A statistical approach to the matching of local features. SIAM J. Imaging Sci. 2(3), 931–958 (2008) MathSciNetCrossRef
38.
Ranade, S., Rosenfeld, A.: Point pattern matching by relaxation. Pattern Recognit. 12(4), 269–275 (1980) CrossRef
39.
Rosenfeld, A., Hummel, R.A., Zucker, S.W.: Scene labeling by relaxation operations. IEEE Trans. Syst. Man Cybern. 6(6), 420–433 (1976) MathSciNetMATHCrossRef
40.
Sclaroff, S., Pentland, A.P.: Model matching for correspondence and recognition. IEEE Trans. Pattern Anal. Mach. Intell. 17(6), 545–561 (1995) CrossRef
41.
Scott, G.L., Longuet-Higgins, H.C.: An algorithm for associating the features of two images. Proc. R. Soc. Lond. B 244, 21–26 (1991) CrossRef
42.
Serradell, E., Özuysal, M., Lepetit, V., Fua, P., Moreno-Noguer, F.: Combining geometric and appearance priors for robust homography estimation. In: Proc. European Conf. Computer Vision (2010)
43.
Shapiro, L.S., Brady, J.M.: Feature-based correspondence: An eigenvector approach. Image Vis. Comput. 10(5), 283–288 (1992) CrossRef
44.
45.
Stockman, G.: Object recognition and localization via pose clustering. Comput. Vis. Graph. Image Process. 40, 361–387 (1987) CrossRef
46.
Stockman, G., Esteva, J.C.: Use of geometrical constraints and clustering to determine 3-D object pose. In: Proc. 7th Int’l Conf. Pattern Recognition, vol. 2, pp. 742–744 (1984)
47.
Stockman, G., Kopstein, S., Benett, S.: Matching images to models for registration and object detection via clustering. IEEE Trans. Pattern Anal. Mach. Intell. 4(3), 229–241 (1982) CrossRef
48.
Tordoff, B., Murray, D.W.: Guided sampling and consensus for motion estimation. In: Proc. European Conf. Computer Vision, pp. 82–98 (2002)
49.
Torr, P., Zisserman, A.: MLESAC: A new robust estimator with application to estimating image geometry. In: Computer Vision and Image Understanding, pp. 138–156 (2000)
50.
Umeyama, S.: An eigendecomposition approach to weighted graph matching problems. IEEE Trans. Pattern Anal. Mach. Intell. 10(5), 695–703 (1988) MATHCrossRef
51.
van Wamelen, P.B., Li, Z., Iyengar, S.S.: A fast expected time algorithm for the 2-D point pattern matching problem. Pattern Recognit. 37, 1699–1711 (2004) CrossRef
52.
Wang, W.-H., Chen, Y.-C.: Point pattern matching by line segments and labels. Electron. Lett. 33(6), 478–479 (1997) CrossRef
53.
Wang, H., Hancock, E.R.: A kernel view of spectral point pattern matching. In: Proc. IAPR Int’l Workshop Structural, Syntactic, and Statistical Pattern Recognition, pp. 361–369 (2004) CrossRef
54.
Wolfson, H.J., Rigoutsos, I.: Geometric hashing: An overview. In: IEEE Computational Science & Engineering, Oct.–Dec., pp. 10–21 (1997)
55.
Wu, Z., Goshtasby, A.: A subdivision approach to image registration. Technical Report, Intelligent Systems Laboratory, Department of Computer Science and Engineering, Wright State University, January 2011
56.
Zhan, C.T. Jr.: An algorithm for noisy template matching. In: Information Processing 74, pp. 698–701. North-Holland, Amsterdam (1974)
57.
Zhang, W., Kos̆ecká, J.: Generalized RANSAC framework for relaxed correspondence problems. In: Proc. Int’l Sym. 3D Data Processing, Visualization, and Transmission (2006)
58.
Zhao, Z., Liu, H.: Searching for interacting features. In: Proc. Int’l J. Conf. Artificial Intelligence (IJCAI), January (2007)
59.
Zhao, J., Zhou, S., Sun, J., Li, Z.: Point pattern matching using relative shape context and relaxation labeling. In: Proc. 2nd Int’l Conf. Advanced Computer Control (ICACC), vol. 5, pp. 516–520 (2010)
Metadata
Title
Point Pattern Matching
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_7

Premium Partner

    Image Credits