| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
An Efficiently Computable Metric for Comparing Polygonal Shapes
March 1991 (vol. 13 no. 3)
pp. 209-216
A method for comparing polygons that is a metric, invariant under translation, rotation, and change of scale, reasonably easy to compute, and intuitive is presented. The method is based on the L/sub 2/ distance between the turning functions of the two polygons. It works for both convex and nonconvex polygons and runs in time O(mn log mn), where m is the number of vertices in one polygon and n is the number of vertices in the other. Some examples showing that the method produces answers that are intuitively reasonable are presented.
[1] 209D. Avis and H. ElGindy, "A combinatorial approach to polygon similarity,"IEEE Trans. Inform. Theory, vol. 29, 1983.[2] D. H. Ballard and C. M. Brown,Computer Vision. Englewood Cliffs, NJ: Prentice-Hall, 1982.[3] P. Cox, H. Maitre, M. Minoux, and C. Ribeiro, "Optimal matching of convex polygons,"Pattern Recognition Lett., vol. 9, pp. 327-334, 1989.[4] D. P. Huttenlocher and K. Kedem, "Computing the minimum Hausdorff distance for point sets under translation," inProc. ACM Symp. Computational Geometry, 1990, pp. 340-349.[5] J. Hong and X. Tan, "The similarity between shapes under affine transformation," inProc. Second Int. Conf. Computer Vision. Washington, DC: IEEE Comput. Soc. Press, 1988, pp. 489-493.[6] J. Hong and H. J. Wolfson, "An improved model-based matching method using footprints," inProc. Ninth Int. Conf. Pattern Recognition, Rome, Italy, Nov. 14-18, 1988.[7] D. Mumford, "The problem of robust shape descriptors," inProc. First Int. Conf. Computer Vision. Washington, DC: IEEE Comput. Soc. Press, 1987, pp. 602-606.[8] J. O'Rourke and R. Washington, "Curve similarity via signatures," inComputational Geometry, G. Toussaint, Ed. Amsterdam, The Netherlands: North-Holland, 1985, pp. 295-318.[9] H. L. Royden,Real Analysis. New York: Macmillan, 1968.[10] L.G. Shapiro and R. M. Haralick, "Organization of relational models for scene analysis,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-4, no. 6 pp. 595-602, 1982.[11] J. T. Schwartz and M. Sharir, "Some remarks on robot vision," New York Univ., Courant Inst. Math. Sci., Tech. Rep. 119, Robotics Rep. 25, Apr. 1984.[12] J. T. Schwartz and M. Sharir, "Identification of objects in two and three dimensions by matching noisy characteristic curves,"Int. J. Robotics Res., vol. 6, no. 2, pp. 29-44, 1987.[13] J. J. Stoker,Differential Geometry. New York: Wiley, 1969.[14] H. Wolfson, "On curve matching," inProc. IEEE Workshop Computer Vision, Miami Beach, FL, Nov. 30-Dec. 2, 1987.
Index Terms:
computer vision; computational geometry; polygonal shapes; L/sub 2/ distance; turning functions; convex; nonconvex; computational geometry; computer vision
Citation:
E.M. Arkin, L.P. Chew, D.P. Huttenlocher, K. Kedem, J.S.B. Mitchell, "An Efficiently Computable Metric for Comparing Polygonal Shapes," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13, no. 3, pp. 209-216, Mar. 1991, doi:10.1109/34.75509
