Part-based shape retrieval

ABSTRACT

This paper introduces a measure for computing the dissimilarity between multiple polylines and a polygon based on the turning function, and describes a part-based retrieval system using that dissimilarity measure. This dissimilarity can be efficiently computed in time O(kmn log mn), where m denotes the number of vertices in the polygon, and n is the total number of vertices in the k polylines that are matched against the polygon. This dissimilarity measure identifies similarities even when a significant portion of one shape is different from the other, for example because the shape is articulated, or because of occlusion or distortion. The effectiveness of the dissimilarity measure in demonstrated in a part-based shape retrieval system. Quantitative experimental verification is performed with a known ground-truth, the MPEG-7 Core Experiment test set, in a comparison with the Curvature Scale Space method, and a global turning angle function method.

REFERENCES

• 1: Esther M. Arkin , L. Paul Chew , Daniel P. Huttenlocher , Klara Kedem , Joseph S. B. Mitchell, An Efficiently Computable Metric for Comparing Polygonal Shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.3, p.209-216, March 1991 [doi>10.1109/34.75509]
• 2: Scott D. Cohen , Leonidas J. Guibas, Partial matching of planar polylines under similarity transformations, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.777-786, January 05-07, 1997, New Orleans, Louisiana, United States
• 3: D.H. Douglas and T.K. Peucker. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. The Canadian Cartographer, 10(2):112--122, 1973.
• 4: D. P. Huttenlocher , G. A. Klanderman , W. A. Rucklidge, Comparing Images Using the Hausdorff Distance, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.9, p.850-863, September 1993 [doi>10.1109/34.232073]
• 5: IBM. Technical summary of turning angle shape descriptors proposed by IBM. Technical report, IBM, 1999. TR ISO/IEC JTC 1/SC 29/WG 11/ P162.
• 6: S. Jeannin and M. Bober. Description of core experiments for MPEG-7 motion/shape. Technical Report ISO/IEC JTC 1/SC 29/WG 11 MPEG99/N2690, March 1999.
• 7: L. J. Latecki, R. Lakämper, and D. Wolter. Shape similarity and visual parts. In Proceedings of the International Conference on Discrete Geometry for Computer Imagery (DGCI), pages 34--51, 2003.
• 8: H.-C. Liu , M. D. Srinath, Partial Shape Classification Using Contour Matching in Distance Transformation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.11, p.1072-1079, November 1990 [doi>10.1109/34.61706]
• 9: F. Mokhtarian, S. Abbasi, and J. Kittler. Efficient and robust retrieval by shape content through curvature scale space. In Workshop on Image DataBases and MultiMedia Search, pages 35--42, 1996.
• 10: J.-R. Ohm and K. Müller. Results of MPEG-7 Core Experiment Shape-1. Technical Report ISO/IEC JTC1/SC29/WG11 MPEG98/M4740, July 1999.
• 11: Ender Ozcan , Chilukuri K. Mohan, Partial shape matching using genetic algorithms, Pattern Recognition Letters, v.18 n.10, p.987-992, Oct. 1997 [doi>10.1016/S0167-8655(97)00123-2]
• 12: Kaleem Siddiqi , Ali Shokoufandeh , Sven J. Dickinson , Steven W. Zucker, Shock Graphs and Shape Matching, International Journal of Computer Vision, v.35 n.1, p.13-32, Nov. 1999 [doi>10.1023/A:1008102926703]
• 13: Mirela Tanase. Shape Decomposition and Retrieval. PhD thesis, Utrecht University, Department of Computer Science, 2005.
• 14: Mirela Tanase, Remco C. Veltkamp, and Herman Haverkort. Multiple polyline to polygon matchingütrecht University TR UU-CS-2005-017, path'http://ftp.cs.uu.nl/pub/RUU/CS/techreps/'. Accepted for ISAAC05.
• 15: 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:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

General Terms:
Algorithms

Keywords:
retrieval, shape matching