Shape Retrieval and Classification Based on Geodesic Paths in Skeleton Graphs

1. Introduction

Skeleton (or medial axis), which integrates geometrical and topological features of the object, is an important shape descriptor for object recognition (Blum, 1973). Shape similarity based on skeleton matching usually performs better than contour or other shape descriptors in the presence of partial occlusion and articulation of parts (Sebastian and Kimia, 2005; Basri et al., 1998; Huttenlocher et al., 1993; Belongie et al., 2002). However, it is a challenging task to automatically recognize objects using their skeletons due to skeleton sensitivity to boundary deformation (Shaked and Bruckstein, 1998; August et al., 1999). Usually, the skeleton branches have to be pruned for recognition (Shaked and Bruckstein, 1998; Choi et al., 2003; Bai et al., 2006; Bai et al., 2007; Ogniewicz and Kubler, 1995; Bai et al., 2008). Moreover, another major restriction of recognition methods based on skeleton is a complex structure of obtained tree or graph representations of the skeletons. Graph edit operations are applied to the tree or graph structures, such as merge and cut operations (Zhu and Yuille, 1996; Liu and Geiger, 1999; Geiger et al., 2003; Di Ruberto, 2004; Pelillo et al., 1999), in the course of the matching process. Probably the most important challenge for skeleton similarity is the fact that the topological structure of skeleton trees or graphs of similar objects may be completely different. This fact is illustrated in Figure 1. Although the skeletons of the two horses are similar, their skeleton graphs are very different. This example illustrates the difficulties faced by approaches based on graph edit operations in the context of skeleton matching. To match skeleton graphs or skeleton trees like the ones shown in Figure 1, some nontrivial edit operations (cut, merge, et al.) are inevitable. On the other hand, skeleton graphs of different objects may have the same topology.

Figure 1.

Visually similar shapes have very different skeleton graphs. The corresponding end nodes between the two skeleton graphs are linked with lines. (The result is accomplished using the method presented in this book chapter, which is also introduced in Bai and Latecki (2008))