Approximate tree matching and shape similarity

Tyng Luh Liu, Davi Geiger

Research output: Contribution to journalConference articlepeer-review


We present a framework for 2D shape contour (silhouette) comparison that can account for stretchings, occlusions and region information. Topological changes due to the original 3D scenarios and articulations are also addressed. To compare the degree of similarity between any two shapes, our approach is to represent each shape contour with a free tree structure derived from a shape axis (SA) model, which we have recently proposed. We then use a tree matching scheme to find the best approximate match and the matching cost. To deal with articulations, stretchings and occlusions, three local tree matching operations, merge, cut, and merge-and-cut, are introduced to yield optimally approximate matches, which can accommodate not only one-to-one but many-to-many mappings. The optimization process gives guaranteed globally optimal match efficiently. Experimental results on a variety of shape contours are provided.

Original languageEnglish (US)
Pages (from-to)456-462
Number of pages7
JournalProceedings of the IEEE International Conference on Computer Vision
StatePublished - 1999
EventProceedings of the 1999 7th IEEE International Conference on Computer Vision (ICCV'99) - Kerkyra, Greece
Duration: Sep 20 1999Sep 27 1999

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition


Dive into the research topics of 'Approximate tree matching and shape similarity'. Together they form a unique fingerprint.

Cite this