Region-based hierarchical image matching

Sinisa Todorovic, Narendra Ahuja

Research output: Contribution to journalArticlepeer-review


This paper presents an approach to region-based hierarchical image matching, where, given two images, the goal is to identify the largest part in image 1 and its match in image 2 having the maximum similarity measure defined in terms of geometric and photometric properties of regions (e.g., area, boundary shape, and color), as well as region topology (e.g., recursive embedding of regions). To this end, each image is represented by a tree of recursively embedded regions, obtained by a multiscale segmentation algorithm. This allows us to pose image matching as the tree matching problem. To overcome imaging noise, one-to-one, many-to-one, and many-to-many node correspondences are allowed. The trees are first augmented with new nodes generated by merging adjacent sibling nodes, which produces directed acyclic graphs (DAGs). Then, transitive closures of the DAGs are constructed, and the tree matching problem reformulated as finding a bijection between the two transitive closures on DAGs, while preserving the connectivity and ancestor-descendant relationships of the original trees. The proposed approach is validated on real images showing similar objects, captured under different types of noise, including differences in lighting conditions, scales, or viewpoints, amidst limited occlusion and clutter.

Original languageEnglish (US)
Pages (from-to)47-66
Number of pages20
JournalInternational Journal of Computer Vision
Issue number1
StatePublished - Jun 2008


  • Association graphs
  • Edit-distance graph matching
  • Image matching
  • Many-to-many matching
  • Maximum subtree isomorphism
  • Maximum weight cliques
  • Segmentation trees
  • Transitive closures

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence


Dive into the research topics of 'Region-based hierarchical image matching'. Together they form a unique fingerprint.

Cite this