3-23 1,073 views
之前已经写过一篇 stitching_detailed的源码理解了。里面提到了最大生成树的问题。
今天想单独拿出来放在一个专栏里面，以后持续的写下去。
以前在ACM中用到的最小生成树比较多，一般是给定一个图，求一个联通图，路径最短。
一般求最小生成树的方法有两种，Prim算法 和 Kruscal算法。
Prim算法复杂度是 O（n2）（n是点的个数）
Kruscal算法复杂度是O（mlogm）（m是边的个数）
稠密图的话用 Prim好一点。
在图片拼接中。在所有图片进行两两特征点匹配之后，把每一幅图看作一个点，然后特征点匹配个数看左边。
跑一下最大生成树就可以知道这个图片如何拼接，使得特征点匹配的数量最多，使得最终的结果最优。
看下源码如何写的。 和我们平常写的也差不多。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
void findMaxSpanningTree(int num_images, const vector<MatchesInfo> &pairwise_matches, Graph &span_tree, vector<int> ¢ers) { Graph graph(num_images); vector<GraphEdge> edges; // Construct images graph and remember its edges for (int i = 0; i < num_images; ++i) { for (int j = 0; j < num_images; ++j) { if (pairwise_matches[i * num_images + j].H.empty()) continue; float conf = static_cast<float>(pairwise_matches[i * num_images + j].num_inliers); //匹配特征点的数量 graph.addEdge(i, j, conf); //往图里面添加这条边，i,j为两个点，conf为这条边的权值 edges.push_back(GraphEdge(i, j, conf)); } } DisjointSets comps(num_images); //并查集的定义 span_tree.create(num_images); vector<int> span_tree_powers(num_images, 0); // Find maximum spanning tree sort(edges.begin(), edges.end(), greater<GraphEdge>()); for (size_t i = 0; i < edges.size(); ++i) { int comp1 = comps.findSetByElem(edges[i].from); int comp2 = comps.findSetByElem(edges[i].to); if (comp1 != comp2) //检查两个点是否在同一个集合 { comps.mergeSets(comp1, comp2); //合并两个点所在的集合 span_tree.addEdge(edges[i].from, edges[i].to, edges[i].weight); span_tree.addEdge(edges[i].to, edges[i].from, edges[i].weight); span_tree_powers[edges[i].from]++; span_tree_powers[edges[i].to]++; } } // Find spanning tree leafs vector<int> span_tree_leafs; for (int i = 0; i < num_images; ++i) if (span_tree_powers[i] == 1) //度为1的点是叶子节点 span_tree_leafs.push_back(i); // Find maximum distance from each spanning tree vertex vector<int> max_dists(num_images, 0); vector<int> cur_dists; for (size_t i = 0; i < span_tree_leafs.size(); ++i) { cur_dists.assign(num_images, 0); span_tree.walkBreadthFirst(span_tree_leafs[i], IncDistance(cur_dists)); //以第i个节点为根节点进行bfs遍历，所到的位置是上一个位置的值加1 for (int j = 0; j < num_images; ++j) max_dists[j] = max(max_dists[j], cur_dists[j]); // 找出对于所有的点，其他点到达自己最远是多少 } // Find min-max distance int min_max_dist = max_dists[0]; for (int i = 1; i < num_images; ++i) if (min_max_dist > max_dists[i]) min_max_dist = max_dists[i]; //找出所有点中到其他点最近的距离是多少 // Find spanning tree centers centers.clear(); for (int i = 0; i < num_images; ++i) if (max_dists[i] == min_max_dist) //根据最近的距离，找出所有可以当作根的节点为中心点。 centers.push_back(i); CV_Assert(centers.size() > 0 && centers.size() <= 2); } |
