boost grid_graph and graph cut on image

Question

我正在嘗試使用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應該被初始化，但我只希望程序編譯。是否有可能與boykov_kolmogorov_max_flow一起使用grid_graph？如果是這樣，怎麼樣？如果沒有，那麼我想我被迫使用更通用（可能更慢）的boost :: adjacency_list？謝謝。

Answer 1

您對其他答案的問題可能是由較舊版本的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; 
} 

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