Revisiting spectral clustering for near-convex decomposition of 2D shape. (September 2020)

• Record Type: Journal Article
• Authors: Li, Zhiyang; Hu, Jia; Stojmenovic, Milos; Liu, Zhaobin; Liu, Weijiang
• Is Part Of: Pattern recognition. Volume 105(2020:Sep.)
• Publication Date: 2020-09
• Subjects: Convex decomposition -- Visibility -- Shape signature -- Spectral graph cut; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2020.107371
• Languages: English
• ISSNs: 0031-3203

Abstract

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.