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

Elena Ranguelova elboyran at gmail.com
Wed Feb 6 03:41:03 EST 2013


Hi Nick,

Thanks for your answer.

I have read some papers and am aware of the broad strokes of the alpha
expansion and the Boykov min-cut algorithms.

I just wanted to confirm that in your implementation,if one sets Nlabels =2
(i.e. binary segmentation problem),your code invokes then only (once) the
Boykov min cut filter, i.e. it's equivalent of using simply the latter.

That's how it looks to me, when I looked inside your code (by eye as I
wtill didn't find a way to "debug" the template classes). So, I was simply
wondering if my conclusion is correct?

Regards,
Elena

On 5 February 2013 20:09, Nick Tustison <ntustison at gmail.com> wrote:

> 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/20130206/42e2f72b/attachment.htm>


More information about the Insight-users mailing list