[vtkusers] going from binary images to 2D contours

[David Gobbi]

The stripper is the only VTK filter for joining line segments
together, it is the appropriate filter to be using here.  It's failing
because it is getting bad input.  Here's what I think is happening:

I'm guessing that you're images have very high resolution.  The
vtkMarchingSquares filter uses single-precision floats, which have
an epsilon of around 1e-7.  Because of this rather large epsilon,
together with the shortness of the line segments that result from
having a high-res image, the point locator in vtkMarchingSquares is
sometimes going to merge points that it shouldn't, giving rise to tiny
degenerate loops in the output that confuse the vtkStripper.

For my own code for generating contours (the code I linked earlier),
I wrote my own marching squares algorithm that uses double precision.
So failures due to accidentally merged points are still possible, but
are a billion times less likely due to the increased precision.  If you
have compiled your own VTK, you could just edit the line in
vtkMarchingSquares that reads vtkPoints::New() and change it to
vtkPoints::New(VTK_DOUBLE) instead, it might make the problem
go away.

(As an aside, one of the problem with VTK, in general, is that it
relies too much on floating-point comparisons for many of its
algorithms),

 - David

On Thu, Mar 1, 2012 at 6:52 PM, Mark Roden <mmroden at gmail.com> wrote:
> Hi David,
>
> It appears that the big time cost is that the marching squares output
> is several thousand line segments, each with three points.  The
> stripper bounces the number of line segments down to 38, and that
> makes the rest of the program much faster.
>
> Is there a vtk filter, other than the stripper, that can 'linearize'
> all of those lines into a single line, if they are in fact continuous
> (as they are in this case)?  A joining filter or the like?  I can
> write something on my own that attaches the line segments, one to
> another, but if the solution already exists, I'd like to go with
> what's tested.
>
> Thanks,
> Mark
>
> On Thu, Mar 1, 2012 at 10:13 AM, Mark Roden <mmroden at gmail.com> wrote:
>> Hi David,
>>
>> You're right, removing the stripper removed those errors.
>>
>> The program is now quite a bit slower-- I suspect that the stripper
>> was causing some other code to be able to run faster.  That will
>> probably be my next question, once I get a profiler attached to this.
>>
>> Thanks!
>> Mark
>>
>> On Thu, Mar 1, 2012 at 7:44 AM, Mark Roden <mmroden at gmail.com> wrote:
>>> Hi David,
>>>
>>> Sorry, I made a mistake earlier; I'm using marching squares, not
>>> cubes-- but I am following it with the stripper, which I'll try
>>> removing now.  And if that doesn't work, I'll check the stripper
>>> output for single polylines per contours.
>>>
>>> Thanks for the starting point,
>>> Mark
>>>
>>> On Wed, Feb 29, 2012 at 9:03 PM, David Gobbi <david.gobbi at gmail.com> wrote:
>>>> From the image, the problem looks fairly obvious: the contour points
>>>> aren't in order, so when you draw lines between the points, you get
>>>> extra lines that cross the image.  So probably the most important
>>>> question is, what do you do, if anything, to make sure that the points
>>>> in the contours that you produce from the binary image are correctly
>>>> ordered?
>>>>
>>>> In your other email you mentioned vtkMarchingSquares, and in this
>>>> email you say you use vtkMarchingCubes (followed, I'm guessing, by
>>>> vtkCutter).  Then maybe you're using vtkStripper to try to get the
>>>> points into the correct order before saving them?  If you are using
>>>> vtkStripper, it looks like it is producing multiple polylines per
>>>> contour, when it should just be producing one polyline per contour.
>>>> This could be the result of numeric precision issues in vtkCutter
>>>> (given the choice, you should use vtkMarchingSquares on each slice,
>>>> rather than vtkMarchingCubes followed by cutter).
>>>>
>>>>  - David
>>>>
>>>>
>>>>
>>>>
>>>>
>>>> On Wed, Feb 29, 2012 at 9:17 PM, Mark Roden <mmroden at gmail.com> wrote:
>>>>> Hi David,
>>>>>
>>>>> Maybe I should just send you my data :)  I don't think that my problem
>>>>> has to do with being near boundaries, as my objects are away from the
>>>>> edges of the image (but not in z-- that's solved that by padding the
>>>>> image by a plane in either direction in z).
>>>>>
>>>>> The problem I'm having is that, somewhere along the way, the contours
>>>>> are being transformed from 'proper' contours, in the case of the
>>>>> larger mask, to ones with extra connections.
>>>>>
>>>>> The binarization is done via the process we discussed on the other
>>>>> thread; that is, the contour is binarized by first following that
>>>>> function to translate polygons to lines, then
>>>>> vtkPolyDataToImageStencil, then vtkImageStencil.  The reverse, from
>>>>> binary to contour (which actually appears on the image), is done by
>>>>> vtkMarchingCubes.  This output has extra lines.
>>>>>
>>>>> I would love to be able to intercept the binary mask in transit, but
>>>>> unfortunately, some way that I have vtkImageViewer2 set up isn't
>>>>> allowing me to see it.  However, you can see the body mask from the
>>>>> contour image 'body lines.png' I've attached, and then from the second
>>>>> overlay image 'body with strange lines.png' the extra lines on a
>>>>> single plane when overlaid with the data.
>>>>>
>>>>> Have you seen this kind of behavior before in either method?  That
>>>>> this behavior appeared either when I ran the old extrusion method or
>>>>> with the new line-based method suggests to me that it's a problem with
>>>>> the marching squares approach.  Hence my original question.
>>>>>
>>>>> Thanks,
>>>>> Mark
>>>>>
>>>>> On Wed, Feb 29, 2012 at 4:10 PM, David Gobbi <david.gobbi at gmail.com> wrote:
>>>>>> My own experience is that vtkMarchingSquares is the best way to
>>>>>> contour a 2D image.  It is the only 2D contouring filter I'm aware of
>>>>>> that correctly orients the contours, i.e. so that you can be sure what
>>>>>> is "inside" and what is "outside."
>>>>>>
>>>>>> But vtkMarchingSquares generates open contours whenever the contour
>>>>>> reaches the bounds of the image... that might be the cause of the
>>>>>> failures that you are seeing.  Because of this problem, I've written
>>>>>> my own version of marching squares that always produces closed
>>>>>> contours, you can find the code here:
>>>>>> https://github.com/dgobbi/ToolCursor/blob/master/vtkImageToROIContourData.cxx
>>>>>>
>>>>>>  - David
>>>>>>
>>>>>>
>>>>>> On Wed, Feb 29, 2012 at 4:43 PM, Mark Roden <mmroden at gmail.com> wrote:
>>>>>>> Hi all,
>>>>>>>
>>>>>>> After a length conversation over on the developer list, I've now got a
>>>>>>> very fast way to convert 2D contours from DICOM rtstructs into binary
>>>>>>> data.  Now I need to do the reverse.  I already have a method, but
>>>>>>> this approach is failing for large images-- and by 'failing', I mean
>>>>>>> producing contours that do not look like the binary data.
>>>>>>>
>>>>>>> I need contours in the xy, xz, and yz planes.  It's also possible to
>>>>>>> have multiple contours in any given plane.
>>>>>>>
>>>>>>> Right now, I'm using vtkMarchingSquares, but as I said, this is not
>>>>>>> working for larger contours, and produces spurious results.
>>>>>>>
>>>>>>> I note that there's also vtkContourFilter, vtkMarchingContourFilter,
>>>>>>> vtkSliceCubes, vtkImageMarchingCubes, etc.  Is there any reason to
>>>>>>> choose one of these over the other?  What would I need for my
>>>>>>> particular case?
>>>>>>>
>>>>>>> Thanks,
>>>>>>> Mark