Polygon decomposition based on the straight line skeleton

ABSTRACT

We propose a novel type of decomposition for polygonal shapes. It is thought that, for the task of object recognition, the human visual system uses a part-based representation. Decompositions based on skeletons have been previously proposed in computer vision. Our method is the first one, however, based on the straight line skeleton. Compared to the medial axis, the straight line skeleton has a few advantages: it contains only straight segments and has a lower combinatorial complexity. The skeletal nodes and the way they are generated are the basis for our decomposition, which has two stages that result in a decomposition into (possibly overlapping) parts. First, a number of visually striking parts are identified, then their boundaries are successively simplified, by locally removing detail. Our method runs in time ((n+r₁+r₂²)log² n), after the skeleton construction, where n is the number of vertices in the polygon, r₁ the number of split events, and r₂ the number of reflex edge annihilations. The decomposition is invariant to rigid motions and uniform scalings. We present results indicating that it provides plausible decompositions for a variety of shapes. This makes it attractive for partial shape matching in content-based image retrieval.

REFERENCES

• 1: Hoffman, D., Richards, W.: Parts of Recognition. Cognition 18 (1984) 65--96.
• 2: Blum, H.: A Transformation for Extracting New Descriptors of Shape. Symposium Models for Speech and Visual Form. ed: W. Wathen-Dunn. MIT Press (1967) 362--381.
• 3: Brady, M., Asada, H.: Smoothed Local Symmetries and their Implementation. The International Journal of Robotics Research 3(3) (1984) 36--61.
• 4: Oswin Aichholzer , Franz Aurenhammer, Straight Skeletons for General Polygonal Figures in the Plane, Proceedings of the Second Annual International Conference on Computing and Combinatorics, p.117-126, June 17-19, 1996
• 5: 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]
• 6: Ogniewicz, R. L., Kubler, O.: Hierarchic Voronoi Skeletons. Pattern Recognition 28(3) (1995) 343--359.
• 7: Simmons, M., Séquin,C. H.: 2D Shape Decomposition and the Automatic Generation of Hierarchical Representations. International Journal of Shape Modeling 4 (1998) 63--78.
• 8: Kaleem Siddiqi , Benjamin B. Kimia, Parts of Visual Form: Computational Aspects, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.3, p.239-251, March 1995 [doi>10.1109/34.368189]
• 9: Benjamin B. Kimia , Allen R. Tannenbaum , Steven W. Zucker, Shapes, shocks, and deformations I: the components of two-dimensional shape and the reaction-diffusion space, International Journal of Computer Vision, v.15 n.3, p.189-224, July 1995 [doi>10.1007/BF01451741]
• 10: 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]
• 11: Longin Jan Latecki , Rolf Lakämper, Convexity rule for shape decomposition based on discrete contour evolution, Computer Vision and Image Understanding, v.73 n.3, p.441-454, March 1999 [doi>10.1006/cviu.1998.0738]
• 12: Keil, J.M.: Polygon Decomposition In: J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry. Elsevier (1999) 491--518.
• 13: Eppstein, D., Erickson, J.: Raising Roofs, Crashing Cycles, and playing Pool: Applications of a Data Structure for Finding Pairwise Interactions. Discrete and Computational Geometry 22(4) (1999) 569--592.
• 14: Chin, F., Snoeyink, J., Wang, C.-A.: Finding the Medial Axis of a Simple Polygon in Linear Time. Discrete Computational Geometry 21(3) (1999) 405--420.
• 15: Siu-Wing Cheng , Antoine Vigneron, Motorcycle graphs and straight skeletons, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.156-165, January 06-08, 2002, San Francisco, California
• 16: Michael T. Goodrich , Roberto Tamassia, Dynamic ray shooting and shortest paths in planar subdivisions via balanced geodesic triangulations, Journal of Algorithms, v.23 n.1, p.51-73, April 1997 [doi>10.1006/jagm.1995.0797]
• 17: Felkel, P., Obdrzalek, A¿.: Straight Skeleton Implementation. In: Proc. of Spring Conference on Computer Graphics, Budmerice, Slovakia (1998) 210--218.
• 18: The Computational Geometry Algorithms Library. http://www.cgal.org/'.
• 19: SQUID database. http://www.ee.surrey.ac.uk/Research/VSSP/imagedb/demo.html'.
• 20: Douglas, D.H., Peucker, T.K.: Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or its Caricature. The Canadian Cartographer 10(2) (1973) 112--122.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
polygonal decomposition, straight line skeleton