CODEWITHSUNDEEP
c++boost
Nil
Nil

Reputation: 2390

3 classes (0, 1, 4) on Boost graph cut

I obtain strange results when I use the BGL boykov_kolmogorov_max_flow() function. I though I would see 2 classes (0-1 or anything else, but only 2!) but I often see three classes: 0, 1 and 4.

For example, using the image below with

8 bits image

I obtain the following results:

444444444444400000000000000000
444444444444440000000000000000
444444444444440000000000000000
444444444444440000000000000000
444444444444444000000000000000
444444444444444000000000000000
444444444444444000000000000000
444444444444444000000000000000
444444444444444000000000000000
444444444444444000000000000000
444444444444444411000000000000
444444444444444444000000000000
444444444444444444000000000000
444444444444444444000000000000
444444444441111111000000000000
444444444440000000000000000000
444444444440000000000000000000
444444444440000000000000000000
444444444440000000000000000000
444444444444000000000000000000
444444444444000000000000000000
444444444444100000000000000000
444444444444110000000000000000
444444444444110000000000000000
444444444444411000000000000000
444444444444444400000000000000
444444444444444400000000000000
444444444444444400000000000000
444444444444444400000000000000
444444444444444400000000000000

Can someone explain the real meaning of these classes? I'm quite sure 4 is the source class and 0 is the sink class, but what about 1? I found nothing in the documentation about that. I think it means a "not sure" horizontal zone, but why would it means that?!?

Second question. Are the 1 reliable? Would it be possible to use them to find a smoother border like in the image below? The goal would be to choose one of the green pixel instead of the red one who are too far to the right. I mean, I know that I could use the 1 in this case to do it, but can I trust them to be there when I need them? :)

Colored border

Thanks for your time.

Upvotes: 4

Views: 502

Answers (1)

Jan Rüegg
Jan Rüegg

Reputation: 10075

In your example:

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

They call the following constructor from here:

boykov_kolmogorov_max_flow(Graph& g,
                       CapacityEdgeMap cap,
                       ResidualCapacityEdgeMap res_cap,
                       ReverseEdgeMap rev,
                       ColorMap color,
                       IndexMap idx,
                       typename graph_traits<Graph>::vertex_descriptor src,
                       typename graph_traits<Graph>::vertex_descriptor sink)

Which means, that what you think are classes are indeed the colors. According to the documentation,

If the color of a vertex after running the algorithm is black the vertex belongs to the source tree else it belongs to the sink-tree (used for minimum cuts).

Now if you look here at the default color map, the colors are an enum going from 0 to 4, where 4 is black.

With all of this, you can conclude that 4 is indeed the source, but everything else (including the 1's) belong to the sink!

The different color probably depends on the implementation itself, but I don't think you can make any assumptions about the 1's without knowing what the implementation is...

Upvotes: 1

Related Questions