Indexing and Matching for View-Based 3-D Object Recognition Using Shock Graphs

A shock graph is a shape abstraction that decomposes a shape into hierarchically organized primitive parts [55]. In this thesis, we propose a novel shock graph computation algorithm that yields stable graphs under noise and shape deformation due to viewpoint changes. Next, we extend the indexing and matching framework for hierarchical structures introduced by Shokoufandeh et al. [54], and apply it to the problem of matching shock graphs representing views of 3-D objects. The indexing performance is improved by a vote accumulation algorithm that efficiently solves a multiple one-to-one assignment of votes. In turn, the matching algorithm is extended by ensuring the satisfaction of all the hierarchical constraints encoded in the graphs. We show that the proposed integrated framework is effective in recognizing object shapes and in estimating the pose of their corresponding 3-D object models. We demonstrate the performance of the framework with a database of 2688 object views