Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork56.4k
Mesh Clustering for 3D Module#25597
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
base:5.x
Are you sure you want to change the base?
Conversation
# Conflicts:#modules/3d/include/opencv2/3d.hpp#modules/3d/src/pointcloud/io_base.cpp#modules/3d/src/pointcloud/io_base.hpp#modules/3d/src/pointcloud/load_point_cloud.cpp#modules/3d/src/spc.cpp#modules/3d/test/test_spc.cpp
modules/3d/include/opencv2/3d.hpp Outdated
| @param k integer, indicates number of segments | ||
| @param result output labels | ||
| */ | ||
| voidcluster(std::vector<cv::Point3f> &vertices, std::vector<std::vector<int32_t>> &indices,int k, OutputArray result); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
const vector<>&
modules/3d/include/opencv2/3d.hpp Outdated
| InputArray world2cam,double fovY,double zNear,double zFar, | ||
| const TriangleRasterizeSettings& settings = TriangleRasterizeSettings()); | ||
| /** @brief Mesh Spectral Cluster |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Please add reference to the algorithm description.
modules/3d/include/opencv2/3d.hpp Outdated
| float delta; | ||
| float eta; | ||
| /* Compute the degree matrix and normalize the affinity matrix*/ | ||
| staticvoidgetLaplacianMat(Mat &in, Mat &out); | ||
| /* Compute distance of all pairs of adjacent faces*/ | ||
| voidgetAdjacentDistanceMat(Mat &out, std::vector<Point3f> &vertices, std::vector<std::vector<int32_t>> &indices)const; | ||
| /* Compute distance of all pairs of non-adjacent faces*/ | ||
| staticvoidgetAffinityMat(Mat &in, Mat &out, std::vector<std::vector<int32_t>> &indices); | ||
| /* Calculate the geodesic distance of two triangular faces*/ | ||
| staticfloatgetGeodesicDistance(const std::vector<Point3f>& face1,const std::vector<Point3f> &face2, | ||
| const std::pair<Point3f, Point3f> &edge); | ||
| /* Calculate the angle distance of two triangular faces*/ | ||
| floatgetAngleDistance(const std::vector<Point3f>& face1,const std::vector<Point3f> &face2)const; | ||
| /* Calculate the centroid coordinate of a face*/ | ||
| static Point3fcalculateFaceCentroid(const std::vector<Point3f>& face); | ||
| /* Calculate the normal vector of a face*/ | ||
| static Point3fcalculateFaceNormal(const std::vector<Point3f>& face); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
We use PIMPL idiom to hide private methods.
modules/3d/src/spc.cpp Outdated
| if (delta_val <0 || delta_val >1) | ||
| CV_LOG_ERROR(NULL,"delta must be between 0 and 1.") | ||
| if (eta <0 || eta >1) | ||
| CV_LOG_ERROR(NULL,"eta must be between 0 and 1.") |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Please useCV_Assert
modules/3d/src/spc.cpp Outdated
| for (constauto & index : indices) | ||
| if (index.size() !=3) | ||
| CV_LOG_ERROR(NULL,"Face element has more/less than 3 vertices") |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
use CV_Assert
| } | ||
| }); | ||
| out.setTo(0, out == std::numeric_limits<float>::infinity()); |
asmorkalovJul 12, 2024 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Most probablypatchNans orfiniteMask will be better.
modules/3d/src/spc.cpp Outdated
| cv::parallel_for_(cv::Range(0, num_faces), [&](const cv::Range& range) { | ||
| for (int i = range.start; i < range.end; ++i) | ||
| out.at<float>(i, i) =1.f; | ||
| }); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
why do you needparallel_for_ here?
| @param k integer, indicates number of segments | ||
| @param result output labels corresponding to each triangular face | ||
| */ | ||
| voidcluster(const std::vector<cv::Point3f> &vertices,const std::vector<std::vector<int32_t>> &indices,int k, |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Do we ever need this as a class? It keeps no internal state and has not so many settings to make it a reusable object.
I propose to transform it to a functioncv::spectralCluster(InputArray vertices, InputArray indices, OutputArray result, int k, float delta, float eps) or something like this.
| return std::hash<int>{}(pair.first) ^ std::hash<int>{}(pair.second); | ||
| } | ||
| }; | ||
| std::unordered_map<std::pair<int,int>, std::pair<int,int>, PairHash> map; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
I propose to use different variable name;map can be confused with the STL container.
| sqrt(degree_mat, degree_mat); | ||
| Mat degree_mat_sqrt; | ||
| repeat(degree_mat,1, in.rows, degree_mat_sqrt); | ||
| out = ((in.mul(degree_mat_sqrt).t()).mul(degree_mat_sqrt)).t(); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Do we really need these two consequent transpositions? Looks like this can be shortened.
| } | ||
| voidSpectralCluster::cluster(const std::vector<cv::Point3f> &vertices,const std::vector<std::vector<int32_t>> &indices, | ||
| int k, OutputArray result) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Please check input parameters for emptyness
(later when they are replaced byInputArray instances there should be also a type check)
| } | ||
| } | ||
| // init | ||
| Mat g_dist_mat =Mat::zeros(num_faces, num_faces, CV_32F); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
This may eat all available memory even on some medium-poly models.
Please consider using different data structure or limit max face count to some realistic number.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Hi Savor, I did find this problem when I was implementing this algorithm. Since the spectral clustering algorithm needs to calculate the affinity matrix (Dijkstra algorithm) based on the relationship between each face, it will generate a matrix of sizenum_face * num_face, which takes up too much memory. I have not thought of a better solution to avoid this problem. The possible method I can think of now is to use an algorithm with lower space complexity instead of spectral clustering to implement mesh clustering. I would like to ask if you have any better suggestions? Thanks!
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
@starga2er777 Hi, I don't have any good solution on my mind.
If this matrix is sparse enough you can consider replacing it by some kind of sparse structure likestd::unordered_map<std::pair<int, int>, float> but I am not sure that this will work.
For now I propose to limit the maximum size of mesh by several thousands faces based on an explicit memory limit. You can specify a constant in your code that shows how much memory we want to fit in and calculate the maximum mesh size from it.
| cluster.cluster(vertices, indices,2, results); | ||
| std::vector<int> truth_value = {0,0,1,1,1,1,1,1,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0}; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Do we know for sure which cluster gonna be first, which gonna be second after K-means calculation?
In common case it's not determined.
Since this test has only two clusters please add a case when 0th cluster is 1st and vice versa.
Uh oh!
There was an error while loading.Please reload this page.
Merged with:opencv/opencv_extra#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.loadMeshdoes 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, theSpectralClusterclass is defined and documented. This class includes the declarations of functions and their parameters.modules/3d/src/spc.cpp, the methods of theSpectralClusterclass are implemented.modules/3d/test/test_spc.cpp, a test for theSpectralClusterclass is created to ensure its functionality.Results
The algorithm has been tested onA 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 SegmentationACM Transactions on Graphics (Proc. SIGGRAPH), 28(3), 2009.
Pull Request Readiness Checklist
See details athttps://github.com/opencv/opencv/wiki/How_to_contribute#making-a-good-pull-request
Patch to opencv_extra has the same branch name.