Skeleton graph matching based on a novel shape tree

A skeleton graph matching algorithm based on a novel shape tree is proposed in this paper. The shape tree in this paper represents an object shape by simultaneously taking account of both the positive curvature maxima and negative curvature minima of the boundary based on skeleton. Comparing with the existing shape representation scheme, it´s less time-consuming. Based on the proposed shape tree, a more general sequence matching algorithm is presented. It takes account of the selection of the starting node and the case of symmetry match. In contrast to typical order preserving assignment, it doesn´t need to enumerate over different starting nodes and has lower computational complexity than Hungarian algorithm. The similarity of two shapes is measured by considering the best match of two shape trees. Several experimental results demonstrate that the proposed approach can produce correct results in the presence of articulations, stretching, and contour deformations with lower computational complexity.