Ordered histogram of shapemes: An ordered bag-of-features based shape descriptor for efficient shape matching

In this paper, we enhance the Shape Context-based descriptor, shapemes, by introducing an ordered bag-of-features model and dynamic programming. The proposed descriptor consists of a series of sub-histograms of shapemes, each of which represents a subset of sampled points. The division of the sampled points is based on their sequential positions on the contour of the shape, so the representation has intrinsic order and is therefore named ordered histogram of shapemes. Then dynamic programming is utilized for descriptor matching. The framework is effective and efficient owing to the following properties: 1) points division approach together with dynamic programming for invariance under the change of starting point, 2) Earth Mover´s Distance for discriminative power, and 3) pre-caculated shapemes dissimilarity matrix for fast descriptor distance calculation. Experiments on standard shape database and real world application scenario demonstrate the effectiveness and efficiency of the descriptor and the matching framework. We make our code and experimental data publicly available for future reference.