Shape Retrieval and Classification Based on Geodesic Paths in Skeleton Graphs

Shape Retrieval and Classification Based on Geodesic Paths in Skeleton Graphs

Xiang Bai (Huazhong University of Science and Technology, P.R. China), Chunyuan Li (Huazhong University of Science and Technology, P.R. China), Xingwei Yang (Temple University, USA) and Longin Jan Latecki (Temple University, USA)
Copyright: © 2013 |Pages: 26
DOI: 10.4018/978-1-4666-1891-6.ch010

Abstract

Skeleton- is well-known to be superior to contour-based representation when shapes have large nonlinear variability, especially articulation. However, approaches to shape similarity based on skeletons suffer from the instability of skeletons, and matching of skeleton graphs is still an open problem. To deal with this problem for shape retrieval, the authors first propose to match skeleton graphs by comparing the geodesic paths between skeleton endpoints. In contrast to typical tree or graph matching methods, they do not explicitly consider the topological graph structure. Their approach is motivated by the fact that visually similar skeleton graphs may have completely different topological structures, while the paths between their end nodes still remain similar. The proposed comparison of geodesic paths between endpoints of skeleton graphs yields correct matching results in such cases. The experimental results demonstrate that the method is able to produce correct results in the presence of articulations, stretching, and contour deformations. The authors also utilize the geodesic skeleton paths for shape classification. Similar to shape retrieval, direct graph matching algorithms like graph edit distance have great difficulties with the instability of the skeleton graph structure. In contrast, the representation based on skeleton paths remains stable. Therefore, a simple Bayesian classifier is able to obtain excellent shape classification results.
Chapter Preview
Top

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))

Purchase this chapter to continue reading all 26 pages >

Complete Chapter List

Search this Book:
Reset