Boost Graph Library:大图的边缘插入速度较慢

发布于 2024-12-11 23:59:26 字数 2858 浏览 3 评论 0原文

我正在尝试使用“智能剪刀”来实现交互式图像分割。因此,我必须从图像创建一个有向图,其中每个顶点代表一个像素。然后,每个顶点通过两条边连接到其每个邻居:一条传出边和一条传入边。这是因为边 (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 作为边,它会变得更慢。

I'm trying to use implement an "intelligent scissor" for an interactive image segmentation. Therefore, I have to create a directed graph from an image where each vertex represents a single pixel. Each vertex is then conntected to each of its neighbours by two edges: one outgoing and one incoming edge. This is due to the fact that the cost of an edge (a,b) may differ from the cost of (b,a). I'm using images with a size of 512*512 pixel so i need to create a graph with 262144 vertices and 2091012 edges. Currently, I'm using the following graph:

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;

I'm using an additional class Graph (sorry for the uninspired naming) which handles the 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();

};

Creating a new graph with 262144 vertices is pretty fast but the insertion of the edges tooks up to 10 seconds which is way too slow for the desired application. Right now, I'm inserting the edges the following way:

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
    }
}

Is there anything I can do do improve the speed of the programm? I'm using Microsoft Visual C++ 2010 Express in release mode with optimization (as recommended by Boost). I thought I could use a listS container for the vertices or edges but the vertices are no problem and if I use listS for the edges, it gets even slower.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

浅唱々樱花落 2024-12-18 23:59:26

adjacency_list 是非常通用的目的;不幸的是,它永远不会像利用特定用例的规律性的解决方案那样有效。 BGL 并不魔法。

您最好的选择可能是想出在没有 BGL 的情况下使用的有效图形表示(提示:对于图像相邻像素的图形,这不会将显式分配所有这些节点和边缘对象),然后将 BGL 拟合到它(示例),或者直接实现现有 adjacency_list / adjacency_matrix 模板的对应部分(概念指南)根据系统的规律进行调整。

通过优化表示,我当然指的是一种实际上并不显式存储所有节点和边,而只是通过某种方式迭代由于图像具有特定尺寸这一事实而产生的隐式节点和边的枚举。 。您真正需要存储的唯一内容是边权重数组。

adjacency_list is very general purpose; unfortunately it's never going to be as efficient as a solution exploiting the regularity of your particular use-case could be. BGL isn't magic.

Your best bet is probably to come up with the efficient graph representation you'd use in the absence of BGL (hint: for a graph of an image's neighbouring pixels, this is not going to explicitly allocate all those node and edge objects) and then fit BGL to it (example), or equivalently just directly implement a counterpart to the existing adjacency_list / adjacency_matrix templates (concept guidelines) tuned to the regularities of your system.

By an optimised representation, I of course mean one in which you don't actually store all the nodes and edges explicitly but just have some way of iterating over enumerations of the implicit nodes and edges arising from the fact that the image is a particular size. The only thing you should really need to store is an array of edge weights.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文