Revisiting spectral clustering for near-convex decomposition of 2D shape. (September 2020) - Li, Zhiyang; Hu, Jia; Stojmenovic, Milos; Liu, Zhaobin; Liu, Weijiang
Highlights: Near-convex 2D shape decomposition by recursive spectral clustering is designed. A flexible stopping rule for the recursive decomposition process is proposed. A novel shape signature named visible protrusion strength is presented. Abstract: We present a novel 2D shape decomposition algorithm via a recursive partitioning process. Starting with the contour points of a shape, we repeatedly separate the points into two parts by spectral clustering, until the stopping condition is met. Motivated by the fact that the points in a convex part are mutually visible, we regard the visibility matrix of points as the affinity matrix of spectral clustering to obtain a near-convex decomposition. Additionally, we present an efficient stopping rule to avoid over-segmentation on the shape branches. The stopping criterion is based on a novel shape signature called visible protrusion strength which can be used to measure the segmentability of a sub-shape. Finally, we demonstrate the efficiency of our algorithm on a variety of publicly available shapes, and provide qualitative and quantitative comparisons with state-of-art approaches.