[Insight-users] MinCut on an itkMesh?

[Nicholas Tustison]

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



On Sep 1, 2009, at 3:27 PM, David Doria wrote:

> On Tue, Sep 1, 2009 at 1:56 PM, Nicholas Tustison  
> <ntustison at gmail.com> wrote:
> Hi David,
>
> You are going to have to write a MeshToGraphFilter as I never  
> thought to perform graph cuts on a mesh.  Let me know if you have  
> any questions.
>
> Good luck,
> Nick
>
>
> Hi Nick,
>
> I've seen graph cuts on a mesh a few times point cloud segmentation  
> - it will be straight forward to convert a mesh into a graph, as a  
> mesh is already a graph! I'll post the filter on the IJ when it's  
> working.
>
> I have a question about the usage of your existing tools, though.  
> The example that shipped with the IJ paper is very involved. I tried  
> to extract the simplest example possible - I created 2 nodes, put 3  
> edges between them, each of weight 2, and I would expect the cut to  
> tell me that node 0 is in one set and node 1 is in the second set,  
> and the cut weight is 6. How would I get those pieces of information?
>
> Right now, when I run the cut filter, number of nodes stays at 2,  
> but the number of edges goes from 3 to 5!?
>
> Here is the example:
>
> #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();
>   graph->DebugOn();
>
>   typedef GraphType::NodeType             NodeType;
>   typedef GraphType::EdgeType             EdgeType;
>   typedef GraphType::NodePointerType      NodePointerType;
>   typedef GraphType::EdgePointerType      EdgePointerType;
>
>
>   // Create graph
>   NodePointerType Nodes[2];
>   //EdgePointerType Edges[3];
>
>   for( unsigned int i = 0; i < 2; i++ )
>     {
>     graph->CreateNewNode( 2 );
>     }
>
>   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 );
>
>   /*
>   for( unsigned int i = 0; i < 3; i++ )
>     {
>     Edges[i] = graph->GetEdgePointer( i );
>     }
> */
>   /** Set the reverse edges */
>   graph->SetAllReverseEdges();
>
>   std::cout << "Input graph" << std::endl << " --------- " <<  
> std::endl;
>   std::cout << "Total number of nodes: "
>     << graph->GetTotalNumberOfNodes() << std::endl;
>   std::cout << "Total number of edges: "
>     << graph->GetTotalNumberOfEdges() << std::endl;
>
>   typedef itk::BoykovMinCutGraphFilter  <GraphType> FilterType;
>   FilterType::Pointer filter = FilterType::New();
>   filter->SetInput(graph);
>     filter->Update();
>
>
>   std::cout << "Output graph" << std::endl << " --------- " <<  
> std::endl;
>   std::cout << "Total number of nodes: "
>           << graph->GetTotalNumberOfNodes() << std::endl;
>   std::cout << "Total number of edges: "
>           << graph->GetTotalNumberOfEdges() << std::endl;
>
> //how would I see which edges are cut? (and hence be able to see the  
> weight of the cut?)
>
> //how would I see which vertices are in set 0 and set 1?
>
>
>   return EXIT_SUCCESS;
> }
>
> Any help would be great.
>
> Thanks!
>
> David
> _____________________________________
> Powered by www.kitware.com
>
> Visit other Kitware open-source projects at
> http://www.kitware.com/opensource/opensource.html
>
> Please keep messages on-topic and check the ITK FAQ at: http://www.itk.org/Wiki/ITK_FAQ
>
> Follow this link to subscribe/unsubscribe:
> http://www.itk.org/mailman/listinfo/insight-users

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