| 76 | } |
| 77 | |
| 78 | image_t MaximumSpanningTree(const ViewGraph& view_graph, |
| 79 | const std::unordered_map<image_t, Image>& images, |
| 80 | std::unordered_map<image_t, image_t>& parents, |
| 81 | WeightType type) { |
| 82 | std::unordered_map<image_t, int> image_id_to_idx; |
| 83 | image_id_to_idx.reserve(images.size()); |
| 84 | std::unordered_map<int, image_t> idx_to_image_id; |
| 85 | idx_to_image_id.reserve(images.size()); |
| 86 | for (auto& [image_id, image] : images) { |
| 87 | if (image.is_registered == false) continue; |
| 88 | idx_to_image_id[image_id_to_idx.size()] = image_id; |
| 89 | image_id_to_idx[image_id] = image_id_to_idx.size(); |
| 90 | } |
| 91 | |
| 92 | double max_weight = 0; |
| 93 | for (const auto& [pair_id, image_pair] : view_graph.image_pairs) { |
| 94 | if (image_pair.is_valid == false) continue; |
| 95 | if (type == INLIER_RATIO) |
| 96 | max_weight = std::max(max_weight, image_pair.weight); |
| 97 | else |
| 98 | max_weight = |
| 99 | std::max(max_weight, static_cast<double>(image_pair.inliers.size())); |
| 100 | } |
| 101 | |
| 102 | // establish graph |
| 103 | weighted_graph G(image_id_to_idx.size()); |
| 104 | weight_map weights_boost = boost::get(boost::edge_weight, G); |
| 105 | |
| 106 | edge_desc e; |
| 107 | for (auto& [pair_id, image_pair] : view_graph.image_pairs) { |
| 108 | if (image_pair.is_valid == false) continue; |
| 109 | |
| 110 | const Image& image1 = images.at(image_pair.image_id1); |
| 111 | const Image& image2 = images.at(image_pair.image_id2); |
| 112 | |
| 113 | if (image1.is_registered == false || image2.is_registered == false) { |
| 114 | continue; |
| 115 | } |
| 116 | |
| 117 | int idx1 = image_id_to_idx[image_pair.image_id1]; |
| 118 | int idx2 = image_id_to_idx[image_pair.image_id2]; |
| 119 | |
| 120 | // Set the weight to be negative, then the result would be a maximum |
| 121 | // spanning tree |
| 122 | e = boost::add_edge(idx1, idx2, G).first; |
| 123 | if (type == INLIER_NUM) |
| 124 | weights_boost[e] = max_weight - image_pair.inliers.size(); |
| 125 | else if (type == INLIER_RATIO) |
| 126 | weights_boost[e] = max_weight - image_pair.weight; |
| 127 | else |
| 128 | weights_boost[e] = max_weight - image_pair.inliers.size(); |
| 129 | } |
| 130 | |
| 131 | std::vector<edge_desc> |
| 132 | mst; // vector to store MST edges (not a property map!) |
| 133 | boost::kruskal_minimum_spanning_tree(G, std::back_inserter(mst)); |
| 134 | |
| 135 | std::vector<std::vector<int>> edges_list(image_id_to_idx.size()); |
no test coverage detected