Indexing hierarchical structures using graph spectra.
Hierarchical image structures are abundant in computer vision and have been used to encode part structure, scale spaces, and a variety of multiresolution features. In this paper, we describe a framework for indexing such representations that embeds the topological structure of a directed acyclic graph (DAG) into a low-dimensional vector space. Based on a novel spectral characterization of a DAG, this topological signature allows us to efficiently retrieve a promising set of candidates from a database of models using a simple nearest-neighbor search. We establish the insensitivity of the signature to minor perturbation of graph structure due to noise, occlusion, or node split/merge. To accommodate large-scale occlusion, the DAG rooted at each nonleaf node of the query "votes" for model objects that share that "part," effectively accumulating local evidence in a model DAG's topological subspaces. We demonstrate the approach with a series of indexing experiments in the domain of view-based 3D object recognition using shock graphs.
Shokoufandeh
Ali
A
Department of Computer Science, College of Enegineering, 3141 Chestnut St., Philadelphia, PA 19104, USA. ashokouf@cs.drexel.edu
Macrini
Diego
D
Dickinson
Sven
S
Siddiqi
Kaleem
K
Zucker
Steven W
SW
D000465:Algorithms; D001185:Artificial Intelligence; D016000:Cluster Analysis; D003198:Computer Simulation; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D016247:Information Storage and Retrieval / Q000379:methods*; D015233:Models, Statistical; D009716:Numerical Analysis, Computer-Assisted; D010363:Pattern Recognition, Automated / Q000379:methods*; D012815:Signal Processing, Computer-Assisted