7

インタラクティブな画像セグメンテーションに「インテリジェントなはさみ」を実装しようとしています。したがって、各頂点が 1 つのピクセルを表す画像から有向グラフを作成する必要があります。次に、各頂点は、2 つのエッジ (1 つの発信エッジと 1 つの着信エッジ) によって隣接する各頂点に接続されます。これは、エッジ (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を使用すると、さらに遅くなります。

4

1 に答える 1

6

adjacency_list非常に汎用的です。残念ながら、特定のユースケースの規則性を利用するソリューションほど効率的になることはありません。BGL は魔法ではありません。

あなたの最善の策は、おそらくBGLがない場合に使用する効率的なグラフ表現を考え出すことです（ヒント：画像の隣接ピクセルのグラフの場合、これはそれらすべてのノードとエッジオブジェクトを明示的に割り当てることはありません）そして次にBGL をそれに適合させる ( example ) か、同等に、システムの規則性に合わせて調整された既存のadjacency_list/adjacency_matrixテンプレート (概念ガイドライン)に対応するものを直接実装します。

最適化された表現とは、もちろん、実際にすべてのノードとエッジを明示的に格納するのではなく、画像が特定のサイズであるという事実から生じる暗黙のノードとエッジの列挙を反復する何らかの方法があるものを意味します. 本当に保存する必要があるのは、エッジの重みの配列だけです。

于 2011-10-25T23:07:12.133 に答える