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.
graph spectra object recognition shock graphs structural indexing