This pull request introduces a mesh clustering algorithm based on spectral clustering. Inspired by the structure outlined in the paper "Segmentation of 3D Meshes through Spectral Clustering" by Rong Liu and Hao Zhang, with some modifications, the algorithm effectively clusters meshes.
A new class will be created in 3d module of branch 5.x to implement all related clustering algorithms.
void cv::SpectralCluster::cluster(std::vector<cv::Point3f> &vertices, std::vector<std::vector<int32_t>> &indices, int k, OutputArray result)
Details
The algorithm flow is roughly shown in the figure below:
The algorithm mainly contains following steps:
Read Data
After reading the mesh file with cv::loadMesh, the algorithm takes in the vertices and triangular faces as input.
The algorithm requires three user-defined parameters: k, delta, and eta. The parameter k determines the number of segments. Delta and eta dictate the composition of the distance between triangular faces.
It performs check on indices data. Each face element must have exactly 3 vertices. (However, note that the method loadMesh does not convert mesh faces into triangular mesh as Open3D does.)
Build Distance Matrix
The algorithm identifies all pairs of adjacent faces.
It builds a matrix which stores the distance between faces.
For every adjacent faces, the distance will be a combination of geodesic distance and angle distance. For non-adjacent faces, the distances are computed with Dijkstra algorithm.
Build Affinity Matrix
The distances are transformed into similarities using a Gaussian Kernel function.
The matrix is then normalized by a degree matrix.
Eigen Decomposition
Use the eigen solver to compute the eigenvectors of the affinity matrix.
The first k eigenvectors, corresponding to the largest eigenvalues, are extracted and used as column vectors of a new matrix.
Each row is then normalized to unit length.
Segmentation via K-Means
The K-Means algorithm is applied to the matrix obtained from the eigen decomposition to generate segment labels for the mesh.
Implementation
In the 3D module, two additional files have been introduced to support the algorithm:
In modules/3d/include/opencv2/3d.hpp, the SpectralCluster class is defined and documented. This class includes the declarations of functions and their parameters.
In modules/3d/src/spc.cpp, the methods of the SpectralCluster class are implemented.
In modules/3d/test/test_spc.cpp, a test for the SpectralCluster class is created to ensure its functionality.
As shown in the figure, spectral clustering has a better performance over many prevailing algorithms.
Here are some of the cluster results:
Reference
Rong Liu and Hao Zhang, "Segmentation of 3D meshes through spectral clustering," 12th Pacific Conference on Computer Graphics and Applications, 2004. PG 2004. Proceedings., Seoul, South Korea, 2004, pp. 298-305, doi: 10.1109/PCCGA.2004.1348360.
Xiaobai Chen, Aleksey Golovinskiy, and Thomas Funkhouser, A Benchmark for 3D Mesh SegmentationACM Transactions on Graphics (Proc. SIGGRAPH), 28(3), 2009.
Merged with: https://github.com/opencv/opencv_extra/pull/1178
Mesh Spectral Clustering for 3D Module
Description
This pull request introduces a mesh clustering algorithm based on spectral clustering. Inspired by the structure outlined in the paper "Segmentation of 3D Meshes through Spectral Clustering" by Rong Liu and Hao Zhang, with some modifications, the algorithm effectively clusters meshes.
A new class will be created in 3d module of branch 5.x to implement all related clustering algorithms.
New interfaces will be added:
Class constructor
Method
Details
The algorithm flow is roughly shown in the figure below:
The algorithm mainly contains following steps:
cv::loadMesh
, the algorithm takes in the vertices and triangular faces as input.loadMesh
does not convert mesh faces into triangular mesh as Open3D does.)Implementation
In the 3D module, two additional files have been introduced to support the algorithm:
modules/3d/include/opencv2/3d.hpp
, theSpectralCluster
class is defined and documented. This class includes the declarations of functions and their parameters.modules/3d/src/spc.cpp
, the methods of theSpectralCluster
class are implemented.modules/3d/test/test_spc.cpp
, a test for theSpectralCluster
class is created to ensure its functionality.Results
The algorithm has been tested on A Benchmark for 3D Mesh Segmentation.
As shown in the figure, spectral clustering has a better performance over many prevailing algorithms.
Here are some of the cluster results:
Reference
Rong Liu and Hao Zhang, "Segmentation of 3D meshes through spectral clustering," 12th Pacific Conference on Computer Graphics and Applications, 2004. PG 2004. Proceedings., Seoul, South Korea, 2004, pp. 298-305, doi: 10.1109/PCCGA.2004.1348360.
Xiaobai Chen, Aleksey Golovinskiy, and Thomas Funkhouser, A Benchmark for 3D Mesh Segmentation ACM Transactions on Graphics (Proc. SIGGRAPH), 28(3), 2009.
Pull Request Readiness Checklist
See details at https://github.com/opencv/opencv/wiki/How_to_contribute#making-a-good-pull-request