title: Indexing hierarchical structures using graph spectra.
abstract: 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.
authors: Department of Computer Science, College of Enegineering, 3141 Chestnut St., Philadelphia, PA 19104, USA. ashokouf@cs.drexel.edu
authors: Ali
authors: A
authors: Shokoufandeh
authors: Diego
authors: D
authors: Macrini
authors: Sven
authors: S
authors: Dickinson
authors: Kaleem
authors: K
authors: Siddiqi
authors: Steven W
authors: SW
authors: Zucker
mesh_terms: 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