Contributions To Several Issues Of Skeleton-based Shape Matching

Shapes are everywhere in our world. How to represent and understand shapes is recognized as a fundamental problem. Shape matching has been successfully applied to object detection, animation synthesis, biological shape analysis, image retrieval, robot navigation, virtual reality, and more. Shape matching attracts scientists in Perceptual Psychology, Computer Vision, and Applied Mathematics. Its applications range from the medical field to national defense. Its progress will promote new understanding of vision and help develop new applications and products.In this thesis several perspectives about skeleton-based shape matching are investigated, including shape representation, shape matching, shape similarity, and shape-based object detection. The main contributions of this thesis are summarized as follows:First, a visual skeleton pruning algorithm based on Discrete Curve Evolution is proposed, hierarchical skeletons that match human perception can be obtained by the process of curve evolution. Based on the intrinsic relation between skeleton and contour, we use Discrete Curve Evolution to generate multiscale skeletons based on global significance measures. This is a novel approach that represents a significant advance over existing methods that use local significance measures. Our experiments demonstrate that the proposed algorithm can completely remove redundant skeleton branches without damaging topology. The positions found for skeleton points are accurate, the time cost is low: our algorithm outperforms existing algorithms for skeletonization and for skeleton pruning. The obtained skeletons can be directly used in shape matching, medical shape analysis, topological analysis for sensor networks, etc.Second, a skeleton graph matching algorithm using path similarity is proposed. Different from previous algorithms, it does not consider the topological structure of skeleton graphs. In order to overcome the instability of the skeleton points, the skeleton path information is expressed as a sequence of feature vectors. We approximate the graph matching problem as a sequence matching problem. This idea breaks with tradition and solves the graph matching problem from a new perspective, smartly avoids the process of matching the instable joint points, and makes graph matching more efficient and fast. The experimental results show that the proposed method not only can establish the correct correspondence between different shapes but also can be used for shape recognition. Compared to previous methods, the time cost has been significantly reduced.Third, a new approach to shape similarity is presented. The new idea is to replace the original distance metric in the shape database using instead the learned distance of the geodesic path. For a given shape similarity, a new similarity is learned by graph transduction. The new similarity is learned iteratively so that the neighbors of a given shape influence its final similarity to the query. This research fully exploits prior information from the database shapes to improve on the original shape similarity, and it breaks with the tradition of retrieving shapes based only on pairwise shape similarity. The experimental results show that the proposed method can significantly improve the accuracy rate of shape retrieval. It achieves on the well-known MEPG-7 shape dataset the best ever high rate of 91.61%. The proposed method is general, easy to implement, and can improve any methods for shape similarity measure.Fourth, an object detection approach based on skeletal representation is proposed. The object's skeletons are used to model its main topological structure. This overcomes difficulties with articulations and non-rigid deformation, based on the observation that the object's topological structure will not change under non-rigid deformations. Our active skeleton model is an explicit shape model, it doesn't need to learn shape cues coarsely from bounding boxes, it can informatively represent shapes and perform object detection efficiently. Active skeleton not only can detect the object's global position but can also localize the local parts robustly. The experimental results show that the proposed method is easy to learn and implement, its detection speed is fast, and it's a very good fit for detecting non-rigid objects.The skeletal representation is the foundation for the research in this thesis. This research examines several key problems in shape matching, and achieves some successes confirmed by extensive experimentation. Vision theory and its applications can benefit from the theory, models, and algorithms proposed in this thesis.