Abstract
We present a new pattern similarity measure that behaves well under affine transformations. Our similarity measure is useful for pattern matching since it is defined on patterns with multiple components, satisfies the metric properties, is invariant under affine transformations, and is robust with respect to perturbation and occlusion. We give an algorithm, based on hierarchical subdivision of transformation space, which minimises our measure under the group of affine transformations, given two patterns. In addition, we present results obtained using an implementation of this algorithm.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Alt, H., Behrends, B., and Blömer, J. 1991. Approximate matching of polygonal shapes. In Proc. 7th Annual ACM Symp. on Computational Geometry, pp. 186–193.
Alt, H., Fuchs, U., Rote, G., and Weber, G. 1996. Matching convex shapes with respect to the symmetric difference. In Algorithms ESA' 96, Proc. 4th Annual European Symp. on Algorithms, Barcelona, Spain, September' 96, Springer, vol. LNCS 1136, pp. 320–333.
Alt, H. and Godeau, M. 1995. Computing the Frùchet distance between two polygonal curves. Int. J. of Computational Geometry & Applications, 5:75–91.
Alt, H., Mehlhorn, K., Wagener, H., and Welzl, E. 1988. Congruence, similarity, and symmetries of geometric objects. Discrete and Computational Geometry, 3:237–256.
Ayache, N. and Faverjon, B. 1987. Efficient registration of stereo by matching graph descriptors of edge segments. Int. J. of Computer Vision, 107–131.
Chen, J. and Stockman, G.C. 1996. Determining pose of 3d objects with curved surfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(1):52–57.
de Berg, M., Devillers, O., van Kreveld, M., Schwarzkopf, O., and Teillaud, M. 1996. Computing the maximum overlap of two convex polygons under translation. In Proc. 7th Annu. Internat. Symp. Algorithms Computing.
de Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O. 1997. Computational Geometry: Algorithms and Applications. Springer-Verlag.
Efrat, A. and Itai, A. 1996. Improvements on bottleneck matching and related problems using geometry. In Proc. 12th Symp. on Computational Geometry, pp. 301–310.
Efrat, A. and Katz, M.J. 1996. Computing fair and bottleneck matchings in geometric graphs. In Proc. 7th Int. Symp. on Algorithms and Computation, pp. 115–125.
Gardner, W.F. and Lawton, D.T. 1996. Interactive model-based vehicle tracking. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(11):1115–1121.
Hagedoorn, M. and Veltkamp, R.C. 1997. A general method for partial point set matching. In Proc. 13th Annual ACM Symp. Computational Geometry, J. D. Boissonnat (Eds.), ACM Press, pp. 406–408.
Hagedoorn, M. and Veltkamp, R.C. 1999. Measuring resemblance of complex patterns. In Discrete Geometry for Computer Imagery.
Huttenlocher, D.P., Kedem, K., and Kleinberg, J.M. 1992. On dynamic Voronoi diagrams and the minimum Hausdorff distance for point sets under Euclidean motion in the plane. In Proc. 8th Annual ACM Symp. Computational Geometry, pp. 110–120.
Huttenlocher, D.P., Kedem, K., and Sharir, M. 1993. The upper envelope of Voronoi surfaces and its applications. Discrete and Computational Geometry, 9:267–291.
Mehrotra, R. and Gary, J. 1995. Similar-shape retrieval in shape data management. IEEE Computer, 28: 9, 55–62.
Montgomery, D. and Zippin, L. 1964. Topological Transformation Groups. Interscience tracts in pure and applied mathematics. Interscience Publishers, Inc.
Mori, S., Suen, C., and Yamamato, K. 1992. Historical review of ocr research and developement. In IEEE Proceedings, pp. 1029–1058.
Mount, D.M. and Wu, A.Y. 1996. On the area of overlap of translated polygons. Computer Vision and Image Understanding, 64:53–61.
Rucklidge, W. 1996. Efficient Visual Recognition Using the Hausdorff Distance. Lecture Notes in Computer Science. Springer-Verlag.
Small, C.G. 1996. The Statistical Theory of Shapes. Springer Series in Statistics. Springer.
Sprinzak, J. and Werman, M. 1994. Affine point matching. Pattern Recognition Letters. 15:337–339.
Wolfson, H.J. 1990. Model based object recognition by ‘geometric hashing'. In Proc. 1st European Conference on Computer Vision, pp. 526–536.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Hagedoorn, M., Veltkamp, R.C. Reliable and Efficient Pattern Matching Using an Affine Invariant Metric. International Journal of Computer Vision 31, 203–225 (1999). https://doi.org/10.1023/A:1008022116857
Issue Date:
DOI: https://doi.org/10.1023/A:1008022116857