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 De-composition (MNCD), which decomposes 2D and 3D arbi-trary shapes into minimum number of “near-convex ” parts. With the degree of near-convexity a user specified param-eter, our decomposition is robust to large local distortions and shape deformation. The shape decomposition is formu-lated as a combinatorial optimization problem by minimiz-ing the number of non-intersection cuts. Two major percep-tion 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 re-sults 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. 1