Representation and self-similarity of shapes

Davi Geiger, Tyng Luh Liu, Robert V. Kohn

Research output: Contribution to journalArticlepeer-review


Representing shapes in a compact and informative form is a significant problem for vision systems that must recognize or classify objects. We describe a compact representation model for two-dimensional (2D) shapes by investigating their self-similarities and constructing their shape axis trees (SA-trees). Our approach can be formulated as a variational one (or, equivalently, as MAP estimation of a Markov random field). We start with a 2D shape, its boundary contour, and two different parameterizations for the contour (one parameterization is oriented counterclockwise and the other clockwise). To measure its self-similarity, the two parameterizations are matched to derive the best set of one-to-one point-to-point correspondences along the contour. The cost functional used in the matching may vary and is determined by the adopted self-similarity criteria, e.g., cocircularity, distance variation, parallelism, and region homogeneity. The loci of middle points of the pairing contour points yield the shape axis and they can be grouped into a unique free tree structure, the SA-tree. By implicitly encoding the (local and global) shape information into an SA-tree, a variety of vision tasks, e.g., shape recognition, comparison, and retrieval, can be performed in a more robust and efficient way via various tree-based algorithms. A dynamic programming algorithm gives the optimal solution in O(N4), where N is the size of the contour.

Original languageEnglish (US)
Pages (from-to)86-99
Number of pages14
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Issue number1
StatePublished - Jan 2003


  • Dynamic programming
  • MRF
  • Self-similarity
  • Shape representation
  • Variational matching

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Computational Theory and Mathematics
  • Artificial Intelligence
  • Applied Mathematics


Dive into the research topics of 'Representation and self-similarity of shapes'. Together they form a unique fingerprint.

Cite this