[Insight-users] Tustison's Graph cut ITK implementation

[Nick Tustison]

Hi Elena,

Please keep this on the email list in case others have similar
questions.

Unfortunately, I don't have the time to walk you through the code
identifying in detail where certain events of Boykov's graph cut
algorithm occur.  However, in broad strokes, the alpha expansion
filter takes an input image to be segmented into n labels.  Within
the alpha expansion filter, for each binary segmentation problem,
the image is converted to a graph structure (itkGraph) using the 
BoykovImageToGraphFunctor where the traits of the graph are 
defined by the class BoykovGraphTraits.  The min cut for that graph
is found using the BoykovMinCutFilter.  We then iterate through the
nodes of the output graph and label the voxels of the image based 
on the labels of the nodes (note that each graph node has the index
to it's corresponding voxel as defined by the graph traits).

Nick


On Feb 5, 2013, at 8:40 AM, Elena Ranguelova <elboyran at gmail.com> wrote:

> Hello Nick,
> 
> Thanks for the quick answer. 
> 
> I have looked at the code, but I find it difficult to trace (debug) C++ template classes, have no experience in that. So, for example, I still can't locate what happens  
> when filter->Update() is called, so it's hard to trace the steps of the algorithm.
> 
> I was aware that the Boykov graph min cut is a step of the alpha expansion, but does it mean that if we specify Nlabels = 2 (i.e. we want binary segmentation) your program using alpha expansion would be equivalent to using directly and only the Boykov graph cut filter (i.e. 1 step only)?
> 
> I see that the alpha expansion filter is descendant of MRFImageFilter, while the BoykovMinCutFliter descends from InPlaceGraphFilter, hence there usage is not so equivalent in terms of input and output.
> 
> Regards,
> Elena
> 
> On 5 February 2013 02:19, Nick Tustison <ntustison at gmail.com> wrote:
> Hi Elena,
> 
> I haven't looked at that code for a long time.  As soon as we found out
> it was patented, we kind of lost interest in its further development and
> went a different direction for our segmentation needs.  I don't have 
> any of those example files any more and I don't know why they aren't
> in the source code (or if they ever were in the first place).  
> 
> Although the test code itkBoykovGraphCutFilterTest.cxx, does 
> interface with the alpha expansion filter, the latter requires the use of
> the Boykov graph min cut filter to work for each binary segmentation
> step.  You have the basic idea regarding the main steps.  I would 
> encourage you to look at the code for further details.  
> 
> Nick
> 
> 
> On Feb 4, 2013, at 8:32 AM, Elena Ranguelova <elboyran at gmail.com> wrote:
> 
>> Hello,
>> 
>> I'm new to ITK and graph cuts, but currently very interested in both. Hence, I came across to Nick Tustison's graph cuts extension of ITK and I found he is an active member of this mailing list.
>> 
>> http://www.insight-journal.org/browse/publication/306
>> 
>> The paper presented  claims that there are 2 codes  for testing:
>> itkGraphTest.cxx
>> itkBoykovAlphaExpansionFilterTest.cxx
>> and 1 example:
>> BoykovGraphCutFilter,
>> 
>> but in reality the example doesn't exist, nor the AlphaExpansion test under that name. There is a testing source called
>> itkBoykovGraphCutFilterTest.cxx, but in fact it illustrates the Alpha Expansion filter, not the BoykovGraphCut filter.
>> 
>> I would really like to have an example of how to use the provided code for performing only Boykov Minimum graph cut filtering on an input image/volume + likelihood images, as shown on figure 7 of the paper. Also how the main steps are performed?:
>> 1. input image to  graph conversion
>> 2. the setup of the likelihood images as filter input
>> 3. the actual minimal cut
>> 4. obtaining image (segmentation) from the cut graph
>> 
>> Does anyone have such a code/example? Would the author (Tustison) be willing to provide such an example usage? (This remark is already mentioned in the first review by David Doria).
>> 
>> Kind regards,
>> Elena
>> 
>> _____________________________________
>> Powered by www.kitware.com
>> 
>> Visit other Kitware open-source projects at
>> http://www.kitware.com/opensource/opensource.html
>> 
>> Kitware offers ITK Training Courses, for more information visit:
>> http://www.kitware.com/products/protraining.php
>> 
>> 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/20130205/1ebc06dc/attachment.htm>