boost grid_graph and graph cut on image

问题:

I'm trying to use Boost Graph Library to use graph cut on a 2D image. My goal is to represent each pixel as a node with 4 float edges (less on the borders). Neighborhood pixels' edge will have a value dependant on gradiant or intensity or something.

To do so, I tried using boost::grid_graph with boost::boykov_kolmogorov_max_flow(), without success. The doc says that grid_graph models "Vertex List", "Edge List" and "Incidence graph", which are the requirements for boykov_kolmogorov_max_flow, so I think it should work.

Here's my code:

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

I know s and t should be initialized, but I only want the program to compile. Is it possible to use grid_graph with boykov_kolmogorov_max_flow? If so, how? If not, then I guess I'm forced to use the more generic (and probably slower) boost::adjacency_list? Thanks.

回答1:

The problem you have with the other answer is probably caused by an older version of Visual Studio (its code works fine with Visual Studio 2012 Express/g++ 4.8.0 and boost 1.53.0). If that problem is the only one with your compiler it can easily be sidestepped by creating another custom property map similar to the one that uses capacity. The changes required are marked with //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;
}

Working on Coliru.

PS: One thing that the Boost.Graph documentation fails to clarify is that the concept requirements described there apply to the case when you explicitly pass every one of the arguments. Some of the default arguments may introduce further requirements.

回答2:

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