标签: boost-graph

目前的情况:我正在尝试从图像中提取片段.感谢openCV的findContours()方法,我现在有一个每个轮廓的8连接点列表.但是,这些列表不能直接使用,因为它们包含大量重复项.

问题:给定一个包含重复项的8个连接点的列表,从中提取段.

可能的解决方案 :

• 起初,我使用openCV的approxPolyDP()方法.然而,结果非常糟糕......这是缩放的轮廓:

以下是结果approxPolyDP():(9段!有些重叠)

但我想要的更像是:

这很糟糕,因为approxPolyDP()可以在"几个细分"中转换"看起来像几个细分"的东西.但是,我所拥有的是一个点列表,这些点往往会对自己进行多次迭代.

例如,如果我的观点是:

0 1 2 3 4 5 6 7 8 
  9   

然后,点的列表将是0 1 2 3 4 5 6 7 8 7 6 5 4 3 2 1 9......如果点的数量变大(> 100),那么提取的段approxPolyDP()不幸地不是重复的(即:它们彼此重叠,但是不是非常相等,所以我可以'只是说"删除重复",而不是像素一样)

• 也许,我有一个解决方案,但它很长(虽然很有趣).首先,对于所有8个连接列表,我创建一个稀疏矩阵(为了效率),如果像素属于列表,则将矩阵值设置为1.然后,我创建一个图形,其中节点对应于像素,相邻像素之间的边缘.这也意味着我在像素之间添加了所有缺失的边缘(复杂性很小,可能因为稀疏矩阵).然后我删除所有可能的"正方形"(4个neighouring节点),这是可能的,因为我已经在很薄的轮廓上工作.然后我可以启动最小生成树算法.最后,我可以使用openCV来近似树的每个分支approxPolyDP()

细分http://img197.imageshack.us/img197/4488/segmentation.png

这是原始列​​表的精彩图片(感谢Paint!)和相关图表.然后,当我在邻居之间添加边缘时.最后,当我删除边缘并制作最小生成树(这里没用)

总结一下:我有一个乏味的方法,我还没有实现,因为它似乎容易出错.但是,我问你,StackOverflow的人:是否有其他现有的方法,可能有很好的实现？

编辑:澄清一下,一旦我有一棵树,我就可以提取"分支"(分支从叶子或连接到3个或更多其他节点的节点开始)然后,openCV中的算法approxPolyDP()是Ramer-Douglas-Peucker算法,这里是维基百科的图片:

通过这张图片,很容易理解为什么当点可能彼此重复时它会失败

另一个编辑:在我的方法中,有一些东西可能有趣值得注意.当您考虑位于网格中的点(如像素)时,通常,最小生成树算法没有用,因为有许多可能的最小树

X-X-X-X
|
X-X-X-X

在基金会上是非常不同的 …

我试图找出如何使用boost :: graph来存储一些信息.但是,我希望有关于每个顶点的信息.盯着库的文档揭示了(a)写得不好的文档,或者(b),我显然不像我想的那样擅长C++.选择两个.

我正在寻找一个简单的示例用法.

我正在寻找一种通过使用键而不是顶点引用本身来访问顶点属性的方法.例如,如果我有

class Data
{
  public:
    std::string  name;
    unsigned int value; 
}; 
typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::directedS, Data > Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;

而不是使用

Vertex vertex1 = boost::add_vertex( g );
g[vertex1].name  = "Alpha";
g[vertex1].value = 10;

我想拥有

g["Alpha"].name  = "Alpha";
g["Alpha"].value = 10;

是否存在现成的机制？

如何创建C++ Boost无向图并以深度优先搜索(DFS)顺序遍历它？

我正在使用boost::graph,我有两个vertex_descriptor.在没有遍历所有边缘的情况下,获得它们之间边缘的最快方法是什么？

我正在尝试在预先制作的图形/节点网络库之间做出决定,或者自己动手.

我正在实现一些图搜索算法,这可能需要对节点和/或边的类结构进行一些重要的定制.

我不知道该怎么做的原因是我不确定预制的定制是否比首先制作我自己的更加昂贵/麻烦.我也很好奇,但不那么重要的是性能权衡.

有没有人有使用其中一个库的直接经验,并根据成功或失败的故事提出建议？我想听到最坏的情况,所以无论我选择什么,我都知道自己要进入什么.

到目前为止,我在搜索中找到的只有两个:Boost Graph Library(BGL)和GOBLIN.其中任何一方的具体建议或对他人的建议也非常受欢迎.BGL似乎非常奥术.值得挣扎吗？

更新:问题可能在中介代码中.如果我注释掉brandes_betweenness_centrality代码的调用将编译.问题可能不是以前认为的索引设置.如果您能够提出另一个对Brandes_betweenness_centrality的调用,我将授予赏金,这将允许将索引保持在外部.

我正在尝试将一些旧的vecS代码转换为listS,特别是brandes_betweenness_centrality算法.

我试图保持Vertex和Edge属性非常轻,并且主要使用外部属性.这样做的原因是我不知道在这一点上我想要与他们联系的是什么.

我得到的错误来自内部adjacency_list.hpp所以我认为问题出在我们的老朋友vertex_index_tlistS上.

以下代码显示了如何重现编译错误.在此工作示例中,您可以更改定义以将vertex_index填充到图形定义中,并在完整工作代码(正确运行中介性)的中介方法中更改设置.

完整的例子:

#include <iostream>
#include <algorithm>
#include <vector>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/betweenness_centrality.hpp>

#include <boost/timer.hpp>

using namespace std;

enum edge_t {A,B};

struct VertexProperties{
    std::string id;
};

struct EdgeProperties{
    edge_t type;
};

//vertex_index in as internal property, switch to this graph and change below vertex map for working code
//typedef boost::adjacency_list < boost::listS, boost::listS, boost::undirectedS,
//      boost::property<boost::vertex_index_t,size_t,VertexProperties>, EdgeProperties > DynamicNet;

// No internal vertex_index
typedef boost::adjacency_list < …

在Boost图库中,何时应该使用顶点描述符和何时使用索引？既然执行vertex_descriptor实际上是无符号整数,那么这两个东西是否具有相同的值？

我有使用boost图库的C++程序.我想知道是否有任何方法可以在节点中包含的某个位置值之后可视化图形(节点和可选边).请查看下面的图像示例,以了解我想要想象的内容:http: //img11.hostingpics.net/pics/647608graphViz.png

谢谢.

我有一个图表的表示std::vector<std::unordered_set<unsigned>> neighbors,即顶点是整数,并且对于每个顶点,我们保留一组它的邻居.因此,为了走遍所有的边缘,我会做类似的事情

for (unsigned u = 0; u < neighbors.size(); ++u)
    for (unsigned v : neighbors[u])
        if (u <= v)
            std::cout << u << ' ' << v << std::endl;

现在,我希望能够从中获得同样的效果

for (auto e: g.edges())
    std::cout << e.first << ' ' << e.second << std::endl;

其中g是从类包封neighbors矢量.

但是,我尝试过的所有东西看起来都非常复杂,我能想到的最好的版本有50行,而且很难看出它是正确的.有一个简单的方法吗？

这是我丑陋的版本:

#include <iostream>
#include <unordered_set>
#include <vector>
typedef unsigned Vertex;
class Graph {
public:
    typedef std::unordered_set<Vertex> Neighbors;
    std::size_t numVertices() const { return neighbors_.size(); }
    Graph(std::size_t n = …