性能 – Boost Graph Library:大图的边插入速度慢

我正在尝试使用实现“智能剪刀”进行交互式图像分割.因此,我必须从图像创建有向图,其中每个顶点表示单个像素.然后通过两个边缘将每个顶点连接到其每个邻居:一个输出边缘和一个输入边缘.这是因为边缘(a,b)的成本可能与(b,a)的成本不同.我正在使用尺寸为512 * 512像素的图像,因此我需要创建一个包含262144个顶点和2091012个边的图形.目前,我正在使用以下图表:

typedef property<vertex_index_t, int,
        property<vertex_distance_t, double,
        property<x_t, int, 
        property<y_t, int
        >>>> VertexProperty;

typedef property<edge_weight_t, double> EdgeProperty;

// define MyGraph
typedef adjacency_list<     
    vecS,           // container used for the out-edges (list)
    vecS,           // container used for the vertices (vector)
    directedS,      // directed edges (not sure if this is the right choice for incidenceGraph)
    VertexProperty,
    EdgeProperty
    > MyGraph;

我正在使用一个额外的类Graph(对于没有灵感的命名),它处理图形:

class Graph
{
private:
    MyGraph *graph;
    property_map<MyGraph, vertex_index_t>::type indexmap;
    property_map<MyGraph, vertex_distance_t>::type distancemap;
    property_map<MyGraph, edge_weight_t>::type weightmap;
    property_map<MyGraph, x_t>::type xmap;
    property_map<MyGraph, y_t>::type ymap;
    std::vector<MyGraph::vertex_descriptor> predecessors;
public:
    Graph();
    ~Graph();

};

创建一个包含262144个顶点的新图形非常快,但边缘的插入需要10秒,这对于所需的应用程序来说太慢了.现在,我按以下方式插入边缘:

tie(vertexIt, vertexEnd) = vertices(*graph);
for(; vertexIt != vertexEnd; vertexIt++){
    vertexID = *vertexIt;
    x = vertexID % 512;
    y = (vertexID - x) / 512;
    xmap[vertexID] = x;
    ymap[vertexID] = y;
    if(y > 0){
        if(x > 0){
            tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y-1)+(x-1)], *graph);    // upper left neighbour
        }
        tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y-1)+(x)], *graph);    // upper
        if(x < 511){
            tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y-1)+(x+1)], *graph);    // upper right
        }
    }
    if(x < 511){    
        tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y)+(x+1)], *graph);    // right
    }
    if(y < 511){
        if(x > 0){
            tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y+1)+(x-1)], *graph);    // lower left
        }
        tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y+1)+(x)], *graph);    // lower
        if(x < 511){
            tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y+1)+(x+1)], *graph);    // lower right
        }
    }
    if(x > 0){
        tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y)+(x-1)], *graph);    // left
    }
}

我有什么办法可以提高程序的速度吗?我在发布模式下使用Microsoft Visual C 2010 Express进行优化(如Boost所推荐).我以为我可以使用listS容器作为顶点或边缘,但顶点没有问题,如果我使用listS作为边缘,它会变得更慢.

adjacency_list是非常通用的;不幸的是,它永远不会像利用你的特定用例的规律性的解决方案那样高效. BGL并不神奇.

您最好的选择可能是在没有BGL的情况下提出有效的图形表示(提示:对于图像的相邻像素的图形,这不会明确地分配所有那些节点和边缘对象)然后适合BGL(example),或者等效地直接实现调整到系统规律的现有adjacency_list / adjacency_matrix模板(concept guidelines)的对应物.

通过优化表示,我当然意味着你实际上并没有明确地存储所有节点和边缘,而只是通过某种方式迭代隐藏节点和边缘的枚举,这是因为图像是特定大小的事实.你应该真正需要存储的唯一一件是边缘权重数组.

相关文章
相关标签/搜索