Farthest sampling segmentation of triangulated surfaces
This method provides a computationally cheaper alternative for segmenting triangulated surfaces, which is beneficial for applications dealing with large 3D triangular meshes.
This paper introduces Farthest Sampling Segmentation (FSS), a new method for segmenting triangulated surfaces that uses a submatrix of the affinity matrix and k-means clustering. The method achieves segmentations as good as those obtained from the full affinity matrix while computing less than 10% of its columns.
In this paper we introduce Farthest Sampling Segmentation (FSS), a new method for segmentation of triangulated surfaces, which consists of two fundamental steps: the computation of a submatrix $W^k$ of the affinity matrix $W$ and the application of the k-means clustering algorithm to the rows of $W^k$. The submatrix $W^k$ is obtained computing the affinity between all triangles and only a few special triangles: those which are farthest in the defined metric. This is equivalent to select a sample of columns of $W$ without constructing it completely. The proposed method is computationally cheaper than other segmentation algorithms, since it only calculates few columns of $W$ and it does not require the eigendecomposition of $W$ or of any submatrix of $W$. We prove that the orthogonal projection of $W$ on the space generated by the columns of $W^k$ coincides with the orthogonal projection of $W$ on the space generated by the $k$ eigenvectors computed by Nyström's method using the columns of $W^k$ as a sample of $W$. Further, it is shown that for increasing size $k$, the proximity relationship among the rows of $W^k$ tends to faithfully reflect the proximity among the corresponding rows of $W$. The FSS method does not depend on parameters that must be tuned by hand and it is very flexible, since it can handle any metric to define the distance between triangles. Numerical experiments with several metrics and a large variety of 3D triangular meshes show that the segmentations obtained computing less than the 10% of columns $W$ are as good as those obtained from clustering the rows of the full matrix $W$.