Probabilistic matching and resemblance evaluation of shapes in trademark images

ABSTRACT

We present a novel matching and similarity evaluation method for planar geometric shapes represented by sets of polygonal curves. Given two shapes, the matching algorithm randomly generates a point sample from each shape and records a vote for a transformation which maps one sample to the other. The experiment is repeated many times. Clusters of votes in the transformation space indicate good candidate transformations for matching the two shapes. Unlike most voting schemes, though, the samples taken in one random experiment are extended as much as possible and the vote is weighted depending on the samples. The best clusters are those with a large total weight. The second part of the method is a resemblance evaluation of the two matched shapes. The definition of our resemblance function incorporates the proximity of line segments as well as the similarity of their slopes. The system is evaluated using the MPEG-7 shape silhouette database and a collection of 10 745 trade mark images. The experiments demonstrate a high performance of our algorithms for contour shapes as well as for trademark images.

REFERENCES

• 1: P. K. Agarwal and M. Sharir. Davenport-Schinzel sequences and their geometric applications. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 1--47. Elsevier Science Publishers B. V. North-Holland, Amsterdam, 2000.
• 2: A. S. Aguado, E. Montiel, and M. S. Nixon. Invariant characterisation of the hough transform for pose estimation of arbitrary shapes. Pattern Recognition, 35:1083--1097, 2002.
• 3: H. Alt, L. Scharf, and S. Scholz. Probabilistic matching of sets of polygonal curves. In Proceedings of the 22nd European Workshop on Computational Geometry (EWCG), pages 107--110, Delphi, Greece, March 2006.
• 4: E. Attalla and P. Siy. Robust shape similarity retrieval based on contour segmentation polygonal multiresolution and elastic matching. Pattern Recognition, 38(12):2229--2241, December 2005.
• 5: F. Attneave. Some informational aspects of visual perception. Psychological Review, 61(3):183--193, 1954.
• 6: K. L. Clarkson. Nearest-neighbor searching and metric space dimensions. In G. Shakhnarovich, T. Darrell, and P. Indyk, editors, Nearest-Neighbor Methods for Learning and Vision: Theory and Practice, pages 15--59. MIT Press, 2006.
• 7: D. Douglas and T. Peuker. Algorithms for the reduction of the number of points required to represent a digitised line or its caricature. In The Canadian Cartographer, volume 10, pages 112--122, 1973.
• 8: John P. Eakins , Jago M. Boardman , Margaret E. Graham, Similarity Retrieval of Trademark Images, IEEE MultiMedia, v.5 n.2, p.53-63, April 1998 [doi>10.1109/93.682526]
• 9: Hui Jiang , Chong-Wah Ngo , Hung-Khoon Tan, Gestalt-based feature similarity measure in trademark database, Pattern Recognition, v.39 n.5, p.988-1001, May, 2006 [doi>10.1016/j.patcog.2005.08.012]
• 10: Martin A. Fischler , Robert C. Bolles, Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography, Communications of the ACM, v.24 n.6, p.381-395, June 1981 [doi>10.1145/358669.358692]
• 11: S. Moss and E. R. Hancock. Pose clustering with density estimation and structural constraints. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition, volume 2, pages 2085--2091, 1999.
• 12: Clark F. Olson, Efficient Pose Clustering Using a Randomized Algorithm, International Journal of Computer Vision, v.23 n.2, p.131-147, June 1997 [doi>10.1023/A:1007906812782]
• 13: A. Pinz, M. Prantl, and H. Ganster. A robust affine matching algorithm using an exponentially decreasing distance function. Journal of Universal Computer Science, 1(8):614--631, 1995.
• 14: George Stockman, Object recognition and localization via pose clustering, Computer Vision, Graphics, and Image Processing, v.40 n.3, p.361-387, December 1, 1987 [doi>10.1016/S0734-189X(87)80147-0]
• 15: R. C. Veltkamp. Multimedia retrieval algorithmics. In SOFSEM2007: Theory and Practice of Computer Science, LNCS 4362, pages 138--154, 2007.
• 16: Haim J. Wolfson , Isidore Rigoutsos, Geometric Hashing: An Overview, IEEE Computational Science & Engineering, v.4 n.4, p.10-21, October 1997 [doi>10.1109/99.641604]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

General Terms:
Algorithms, Experimentation

Keywords:
probabilistic algorithms, shape matching, shape similarity, trademark image retrieval