Object categorization using bone graphs

The bone graph (Macrini et al., in press, 2008) [23] and [25] is a graph-based medial shape abstraction that offers improved stability over shock graphs and other skeleton-based descriptions that retain unstable ligature structure. Unlike the shock graph, the bone graph’s edges are attributed, allowing a richer specification of relational information, including how and where two medial parts meet. In this paper, we propose a novel shape matching algorithm that exploits this relational information. Formulating the problem as an inexact directed acyclic graph matching problem, we extend a leading bipartite graph-based algorithm for matching shock graphs (Siddiqi et al., 1999) [41]. In addition to accommodating the relational information, our new algorithm is better able to enforce hierarchical and sibling constraints between nodes, resulting in a more general and more powerful matching algorithm. We evaluate our algorithm with respect to a competing shock graph-based matching algorithm, and show that for the task of view-based object categorization, our algorithm applied to bone graphs outperforms the competing algorithm. Moreover, our algorithm applied to shock graphs also outperforms the competing shock graph matching algorithm, demonstrating the generality and improved performance of our matching algorithm.

► An object categorization framework is presented based on directed acyclic bone graphs. ► The nodes in a bone graph encode medial parts while edges encode spatial relations. ► A new graph matching algorithm is introduced to exploit both node and edge attributes. ►The algorithm is generally applicable and enforces hierarchical and sibling constraints. ►The algorithm offers improved performance over a leading algorithm.