Minimum near-convex decomposition for robust shape representation

Shape decomposition is a fundamental problem for part-based shape representation. We propose a novel shape decomposition method called Minimum Near-Convex Decomposition (MNCD), which decomposes 2D and 3D arbitrary shapes into minimum number of near-convex parts. With the degree of near-convexity a user specified parameter, our decomposition is robust to large local distortions and shape deformation. The shape decomposition is formulated as a combinatorial optimization problem by minimizing the number of non-intersection cuts. Two major perception rules are also imposed into our scheme to improve the visual naturalness of the decomposition. The global optimal solution of this challenging discrete optimization problem is obtained by a dynamic subgradient-based branch-and-bound search. Both theoretical analysis and experiment results show that our approach outperforms the state-of-the-art results without introducing redundant parts. Finally we also show the superiority of our method in the application of hand gesture recognition.