增强 grid_graph 和图像上的图形切割

我正在尝试使用 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？谢谢。

您在另一个答案中遇到的问题可能是由旧版本的 Visual Studio 引起的（其代码与 Visual Studio 2012 Express/g++ 4.8.0 和 boost 1.53.0 正常工作）。如果该问题是您的编译器的唯一问题，则可以通过创建另一个类似于使用的自定义属性映射来轻松回避capacity。所需的更改标记为//ADDED and //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 上工作。 http://coliru.stacked-crooked.com/view?id=5dfb6672edbad279a31cf2e6949141a7-50d9cfc8a1d350e7409e81e87c2653ba

PS：Boost.Graph 文档未能澄清的一件事是，其中描述的概念要求适用于显式传递每个参数的情况。一些默认参数可能会引入进一步的要求。