[Insight-users] MinCut on an itkMesh?

[Nicholas Tustison]

I would start from a simple image (perhaps one of the included images  
used for testing) and see if the assumptions hold for a test case that  
appears to work.



On Sep 2, 2009, at 9:54 AM, David Doria wrote:

> On Tue, Sep 1, 2009 at 11:50 PM, Nicholas Tustison <ntustison at gmail.com 
> > wrote:
> Hi David,
>
> Okay, it's been quite awhile since I've looked at the code but I  
> think I can provide you with a little bit of direction.  If you look  
> in the Initialize() function (the lines in question are 198-205 in  
> my copy), you'll see that Boykov's min-cut algorithm adds 2 edges to  
> the output graph, i.e. the "terminal edge" and the "orphan edge".  
> Also, if I remember correctly, what you do is iterate through the  
> nodes in the graph and inspect  the boolean variable "IsSink" which  
> will be either true (sink node) or false (source node).  Also, the  
> class variable m_MaxFlow should hold the weight of the min cut.   
> Simply call GetMaxFlow().
>
> Nick
>
> Nick,
>
> Thanks for the help so far - however, it doesn't seem to be working  
> as expected.
>
> IsSink is returning false for both nodes.
> GetMaxFlow() is returning 0.
>
> I added this:
>   this->m_MaxFlow += bottleneck;
> std::cout << "added " << bottleneck << " to maxflow." << std::endl;
>
> to line 394 of itkBoykovMinCutGraphFilter.txx and nothing is ever  
> output.. so it follows that GetMaxFlow() would return 0 - but why  
> would it never be incremented? Is this too degenerate of a graph for  
> the algorithm to work properly? I wasn't sure if multiple edges were  
> allowed between nodes - so I now only have one edge of weight 2. I  
> also wasn't sure about the behavior of directed graphs, so I removed  
> the call to SetAllReverseEdges.   Here is the code:
> #include <iostream>
>
> #include "itkGraph.h"
> #include "itkBoykovGraphTraits.h"
> #include "itkBoykovMinCutGraphFilter.h"
>
> int main( int argc, char * argv[] )
> {
>     typedef itk::BoykovGraphTraits<short, 3> GraphTraitsType;
>
>     typedef itk::Graph<GraphTraitsType>           GraphType;
>     GraphType::Pointer graph = GraphType::New();
>
>     typedef GraphType::NodePointerType      NodePointerType;
>     typedef GraphType::EdgePointerType      EdgePointerType;
>
>       // Create graph nodes
>     NodePointerType Nodes[2];
>
>     for( unsigned int i = 0; i < 2; i++ )
>     {
>         graph->CreateNewNode( 2 );
>     }
>
>     //get pointers to the newly created nodes
>     for( unsigned int i = 0; i < 2; i++ )
>     {
>         Nodes[i] = graph->GetNodePointer( i );
>     }
>
>      //create three edges between nodes 0 and 1, each with weight 2
>     graph->CreateNewEdge( Nodes[0], Nodes[1], 2 );
>     //graph->CreateNewEdge( Nodes[0], Nodes[1], 2 );
>     //graph->CreateNewEdge( Nodes[0], Nodes[1], 2 );
>
>     // Set the reverse edges
>     //graph->SetAllReverseEdges();
>
>     //perform the cut
>     typedef itk::BoykovMinCutGraphFilter  <GraphType> FilterType;
>     FilterType::Pointer filter = FilterType::New();
>     filter->SetInput(graph);
>     filter->Update();
>
>     //see which nodes are sinks
>     typedef GraphType::NodeIterator         NodeIteratorType;
>     typedef GraphType::NodeIdentifierType   NodeIdentifierType;
>     NodeIteratorType nit( graph );
>     for( nit.GoToBegin(); !nit.IsAtEnd(); ++nit )
>     {
>         NodePointerType node = nit.GetPointer();
>         NodeIdentifierType Id = graph->GetNodeIdentifier( node );
>         node = graph->GetNodePointer( Id );
>         bool IsSink = node->IsSink;
>
>         if(IsSink)
>         {
>             std::cout << "Node Id: " << Id << " is in group 1." <<  
> std::endl;
>         }
>         else
>         {
>             std::cout << "Node Id: " << Id << " is in group 0." <<  
> std::endl;
>         }
>     }
>
>     //get the cut weight (min cut = max flow)
>     typedef GraphType::NodeWeightType       NodeWeightType;
>     NodeWeightType maxflow = filter->GetMaxFlow();
>     std::cout << "Max Flow: " << maxflow << std::endl;
>
>     return EXIT_SUCCESS;
>
> }
>
> The output is:
> Node Id: 0 is in group 0.
> Node Id: 1 is in group 0.
> Max Flow: 0
>
> The expected output is: (group 1 and 0 could possibly be switched)
> Node Id: 0 is in group 0.
> Node Id: 1 is in group 1.
> Max Flow: 2
>
> Any more suggestions?
>
> Thanks,
>
> David

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.itk.org/pipermail/insight-users/attachments/20090902/9f6a6f65/attachment-0001.htm>