Enlarge grid_graph and graph on image

Question

I am trying to use the Boost Graph Library to use a graph cut in a two-dimensional image. My goal is to represent each pixel as a node with 4 float edges (less at the borders). The pixel neighborhood of the pixels will have a value depending on the gradient or intensity, or something else.

For this, I tried to use boost :: grid_graph with boost :: boykov_kolmogorov_max_flow (), without success. Doc says grid_graph models the “Vertex List”, “Border List” and “Incident Graph”, which are requirements for boykov_kolmogorov_max_flow, so I think it should work.

Here is 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 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 that s and t must be initialized, but I want the program to compile. Is it possible to use grid_graph with boykov_kolmogorov_max_flow? If so, how? If not, then I probably have to use a more general (and probably slower) boost :: adjacency_list? Thanks.

Answer 1

The problem 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 raises the level of 1.53.0). If this problem is the only one with your compiler, you can easily get around it by creating another custom property map, similar to the one using capacity . Necessary changes are marked //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; } 

Work with Coliru.

PS: One thing the Boost.Graph documentation does not allow to clarify is that the concept requirements described there apply to the case where you explicitly pass each of the arguments. Some of the default arguments may introduce additional requirements.

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