boost grid_graph and graph cut on image

Question

Я пытаюсь использовать Boost Graph Library для использования графика, вырезанного на двумерном изображении. Моя цель - представить каждый пиксель в виде узла с 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>' 

Я знаю, с и т должен быть инициализирован, но я только хочу, чтобы программа для компиляции. Можно ли использовать grid_graph с boykov_kolmogorov_max_flow? Если да, то как? Если нет, то, наверное, я вынужден использовать более общий (и, вероятно, более медленный) boost :: adjacency_list? Благодарю.

Answer 1

Проблема у вас есть с другим ответом, вероятно, вызвана более старой версией Visual Studio (его код прекрасно работает с Visual Studio 2012 Express,/г ++ 4.8.0 и повысить 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; 
} 

Working on Coliru.

PS: Одна вещь, что документация Boost.Graph не может уточнить, что требования к концепции, описанной здесь относятся к случаю, когда вы явно передать каждому из аргументов. Некоторые из аргументов по умолчанию могут вводить дополнительные требования.

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