Feat #25150: Pose Graph MST initialization #27423
Conversation
Implements a MST-based initialization for pose graphs, as proposed in issue opencv#25150. Both Prim’s and Kruskal’s algorithms were added to the 3D module, receiving a vector of node IDs and a vector of edges (each with source/target IDs and a weight) and returning a vector with the resulting edges. These MST implementations treat edges as undirected internally, meaning users only need to provide one direction (A→B or B→A), and duplicates are handled automatically. Additionally, a new pose graph initialization method using MST was implemented. It constructs the MST over the pose graph, then traverses it to reconstruct node poses. A set of test cases validating the implementation was also included. Co-authored-by: Miguel Agra <miguel.agra@tecnico.ulisboa.pt>
|
Hi @asmorkalov, We noticed that no reviewers have been assigned to this PR yet. Is there a specific reason for this? Let us know if there's anything we can do to move this PR forward. Thanks! |
| CV_EXPORTS std::vector<MSTEdge> buildMSTPrim( | ||
| const size_t numNodes, | ||
| const std::vector<MSTEdge>& edges, | ||
| size_t root = 0 | ||
| ); | ||
|
|
||
| // builds a MST using Kruskal's algorithm | ||
| CV_EXPORTS std::vector<MSTEdge> buildMSTKruskal( | ||
| const size_t numNodes, | ||
| const std::vector<MSTEdge>& edges |
There was a problem hiding this comment.
I propose to use single function as public API with algorithm type parameter like it's done in many places in OpenCV. Also we have internal MST implementation at least in multi-camera calibration. It makes sense to move it to main header, not details.
| // represents an edge in a graph for MST computation | ||
| struct CV_EXPORTS MSTEdge | ||
| { | ||
| size_t source, target; |
There was a problem hiding this comment.
size_t is not binding friendly. I propose to use just int here. Also you can use CV_EXPORTS_W_SIMPLE for the structure.
Co-authored-by: Miguel Agra <miguel.agra@tecnico.ulisboa.pt>
|
Hi @asmorkalov, thanks for the feedback! Please let us know if everything looks good now or if there’s anything else you'd like us to adjust! |
|
Hi @asmorkalov, could you trigger CI again? It seems to have failed to clone opencv_extra? |
Implements an MST-based initialisation for pose graphs, as proposed in issue #25150. Both Prim’s and Kruskal’s algorithms were added to the 3D module. These receive a vector of node IDs and a vector of edges (each with source and target IDs and a weight), and return a vector with the resulting edges. These MST implementations treat edges as undirected internally, meaning users only need to provide one direction (A→B or B→A), and duplicates are handled automatically.
Additionally, a new pose graph initialisation method using MST (Prim) was implemented. It constructs the MST over the pose graph, then traverses it to reconstruct node poses. With this, users can call
poseGraph->initializePosesWithMST()to create an initial solution for the pose graph problem.A set of test cases validating the implementation was also included.
Notes
weight = || translation || + λ * rotation_angle,where λ = 0.485 was determined empirically based on optimiser performance;
Future Work
Co-authored-by: @miguel1099
Pull Request Readiness Checklist
See details at https://github.com/opencv/opencv/wiki/How_to_contribute#making-a-good-pull-request
Patch to opencv_extra has the same branch name.