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 应该被初始化，但我只希望程序编译。是否可以将 grid_graph 与 boykov_kolmogorov_max_flow 一起使用？如果是这样，怎么做？如果不是，那么我想我不得不使用更通用（可能更慢）的 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;
}

在 Coliru 上工作。

PS：Boost.Graph 文档未能阐明的一件事是，其中描述的概念要求适用于您明确传递每个参数的情况。一些默认参数可能会引入更多要求。

于 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 回答