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

Fri Feb 15 11:50:34 EST 2013

Hello again,

Thank you for all your time and answers.

I have one more issue, I hope you will remember if your software worked
with 3D volumes. In your code and paper you give only one example with a
Nifti image called lungs.nii.gz.
I have the following questions:
1. Why the result provided by you (and in fact the result if one runs your
code on that volume), i.e. lung.out.nii.gz is with much smaller size than
the original?
2. Why the raw data have such bizar values (like voxel value of 1000)?
3. Why I couldn't make the code run on any other Nifti volumes containing
voxel values between 0 and 255? I'm getting the following error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

I'll be very grateful if you can give me any hint and if you could, please,
confirm the code worked on other Nifti images, not only on lungs.nii.gz. If
that is the case, I'd like to try it on at least one more volume if  you
point to me to the data source.

Kind regards,
Elena

On 6 February 2013 15:10, Nick Tustison <ntustison at gmail.com> wrote:

> yes.
>
>
> On Feb 6, 2013, at 3:41 AM, Elena Ranguelova <elboyran at gmail.com> wrote:
>
> 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/20130215/67aeb358/attachment.htm>