3

Boost Graph Library を使用して、2D 画像でグラフ カットを使用しようとしています。私の目標は、各ピクセルを 4 つのフロート エッジ (境界線が少ない) を持つノードとして表すことです。近隣ピクセルのエッジには、グラデーションや強度などに依存する値があります。

そうするために、boost::grid_graph を boost::boykov_kolmogorov_max_flow() で使用しようとしましたが、成功しませんでした。ドキュメントによると、grid_graph は boykov_kolmogorov_max_flow の要件である「頂点リスト」、「エッジ リスト」、および「インシデント グラフ」をモデル化しているため、動作するはずです。

これが私のコードです：

const unsigned int D = 2;
typedef boost::grid_graph<D> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor VertexDescriptor;

boost::array<unsigned int, D> lengths = { { 3, 3 } };
Graph graph(lengths, false);

// Add edge's value between pixels

VertexDescriptor s, t; // Should be initialized, I know.
float flow = boost::boykov_kolmogorov_max_flow(graph, s, t);
// error C2039: 'edge_property_type' is not a member of 'boost::grid_graph<Dimensions>'

s と t を初期化する必要があることはわかっていますが、プログラムをコンパイルするだけです。boykov_kolmogorov_max_flow で grid_graph を使用することは可能ですか? もしそうなら、どのように？そうでない場合は、より一般的な (そしておそらく遅い) boost::adjacency_list を使用せざるを得ないと思いますか? ありがとう。

4

2 に答える 2

5

他の回答の問題は、おそらく古いバージョンの Visual Studio が原因です (そのコードは、Visual Studio 2012 Express/g++ 4.8.0 および boost 1.53.0 で正常に動作します)。その問題がコンパイラの唯一の問題である場合は、capacity. 必要な変更は と でマークされ//ADDEDてい//CHANGEDます。

#include <iostream>

#include <boost/graph/grid_graph.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/graph/iteration_macros.hpp>

int main()
{

    const unsigned int D = 2;
    typedef boost::grid_graph<D> Graph;
    typedef boost::graph_traits<Graph>::vertex_descriptor VertexDescriptor;
    typedef boost::graph_traits<Graph>::edge_descriptor EdgeDescriptor;//ADDED
    typedef boost::graph_traits<Graph>::vertices_size_type VertexIndex;
    typedef boost::graph_traits<Graph>::edges_size_type EdgeIndex;


    boost::array<std::size_t, D> lengths = { { 3, 3 } };
    Graph graph(lengths, false);

    float pixel_intensity[]={10.0f,15.0f,25.0f,
                            5.0f,220.0f,240.0f,
                            12.0f,15.0,230.0f};
    std::vector<int> groups(num_vertices(graph));
    std::vector<float> residual_capacity(num_edges(graph)); //this needs to be initialized to 0
    std::vector<float> capacity(num_edges(graph)); //this is initialized below, I believe the capacities of an edge and its reverse should be equal, but I'm not sure
    std::vector<EdgeDescriptor> reverse_edges(num_edges(graph));//ADDED

    BGL_FORALL_EDGES(e,graph,Graph)
    {
        VertexDescriptor src = source(e,graph);
        VertexDescriptor tgt = target(e,graph);
        VertexIndex source_idx = get(boost::vertex_index,graph,src);
        VertexIndex target_idx = get(boost::vertex_index,graph,tgt);
        EdgeIndex edge_idx = get(boost::edge_index,graph,e);

        capacity[edge_idx] = 255.0f - fabs(pixel_intensity[source_idx]-pixel_intensity[target_idx]); //you should change this to your "gradiant or intensity or something"

        reverse_edges[edge_idx]=edge(tgt,src,graph).first;//ADDED
    }

    VertexDescriptor s=vertex(0,graph), t=vertex(8,graph); 

    //in the boykov_kolmogorov_max_flow header it says that you should use this overload with an explicit color property map parameter if you are interested in finding the minimum cut
    boykov_kolmogorov_max_flow(graph,
        make_iterator_property_map(&capacity[0], get(boost::edge_index, graph)), 
        make_iterator_property_map(&residual_capacity[0], get(boost::edge_index, graph)),
        make_iterator_property_map(&reverse_edges[0], get(boost::edge_index, graph)), //CHANGED
        make_iterator_property_map(&groups[0], get(boost::vertex_index, graph)),
        get(boost::vertex_index, graph),
        s,
        t
    );


   for(size_t index=0; index < groups.size(); ++index)
   {
        if((index%lengths[0]==0)&&index)
            std::cout << std::endl;
        std::cout << groups[index] << " ";
   }

   return 0;
}

コリルに取り組んでいます。

PS: Boost.Graph のドキュメントで明確にされていないことの 1 つは、そこで説明されている概念要件が、すべての引数を明示的に渡す場合に適用されることです。一部のデフォルト引数では、さらに要件が生じる場合があります。

于 2013-04-24T19:05:34.660 に答える
1 
#include <iostream>

#include <boost/graph/grid_graph.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/graph/iteration_macros.hpp>

int main()
{

    const unsigned int D = 2;
    typedef boost::grid_graph<D> Graph;
    typedef boost::graph_traits<Graph>::vertex_descriptor VertexDescriptor;
    typedef boost::graph_traits<Graph>::vertices_size_type VertexIndex;
    typedef boost::graph_traits<Graph>::edges_size_type EdgeIndex;


    boost::array<unsigned int, D> lengths = { { 3, 3 } };
    Graph graph(lengths, false);

    float pixel_intensity[]={10.0f,15.0f,25.0f,
                            5.0f,220.0f,240.0f,
                            12.0f,15.0,230.0f};
    std::vector<int> groups(num_vertices(graph));
    std::vector<float> residual_capacity(num_edges(graph)); //this needs to be initialized to 0
    std::vector<float> capacity(num_edges(graph)); //this is initialized below, I believe the capacities of an edge and its reverse should be equal, but I'm not sure

    BGL_FORALL_EDGES(e,graph,Graph)
    {
        VertexDescriptor src = source(e,graph);
        VertexDescriptor tgt = target(e,graph);
        VertexIndex source_idx = get(boost::vertex_index,graph,src);
        VertexIndex target_idx = get(boost::vertex_index,graph,tgt);
        EdgeIndex edge_idx = get(boost::edge_index,graph,e);
        capacity[edge_idx] = 255.0f - fabs(pixel_intensity[source_idx]-pixel_intensity[target_idx]); //you should change this to your "gradiant or intensity or something"
    }

    VertexDescriptor s=vertex(0,graph), t=vertex(8,graph); 

    //in the boykov_kolmogorov_max_flow header it says that you should use this overload with an explicit color property map parameter if you are interested in finding the minimum cut
    boykov_kolmogorov_max_flow(graph,
        make_iterator_property_map(&capacity[0], get(boost::edge_index, graph)), 
        make_iterator_property_map(&residual_capacity[0], get(boost::edge_index, graph)),
        get(boost::edge_reverse, graph),
        make_iterator_property_map(&groups[0], get(boost::vertex_index, graph)),
        get(boost::vertex_index, graph),
        s,
        t
    );


   for(size_t index=0; index < groups.size(); ++index)
   {
        if((index%lengths[0]==0)&&index)
            std::cout << std::endl;
        std::cout << groups[index] << " ";
   }

   return 0;
}
于 2013-04-24T13:31:00.643 に答える