[Insight-users] Distance transform in a hurry

[Richard Beare]

Hi,
The rle stuff was work in progress that I haven't returned to - you
can definitely comment it out.

It certainly looks like perfDT3D was left in a sorry state.

Usage from the cmake file is:

perfDT3D ${INPUT_IMAGE3D} 100 255 bmask.nii.gz distA.nii.gz
distB.nii.gz distC.nii.gz

100 is a threshold value for the input image and 255 is the value used
for voxels above the threshold.

The use of argv[1] for iterations is clearly wrong, but iterations
isn't being used anywhere.

The perf test crashes for me when using make test, but runs OK from
the command line, perhaps the comparison actually fails now. I'll need
to look into this.

I initially thought these algorithms were related because they both
seemed to be using parabolic structuring elements. There are a family
of methods for efficient parabolic erosions and dilations (I don't
know them well at all), and the one I used is the simplest. There is
an increase in complexity and a theoretical improvement in efficiency
for some structuring element sizes with the other ones. It does
basically work by finding the envelopes you mentioned, but exploits
some of the morphological decomposition tricks to simplify things -
basically breaking the erosion by a parabola into to erosions by half
parabolas, which makes it easy to find the envelope each time.

It is a long time since I looked at the current ITK distance
transforms, so the problems I perceived could well be incorrect. The
first oddity I notices was the use of a 3x3 erosion (or dilation) in
the signed transform. This was used to shrink or enlarge one half of
the transform. This sounded dodgy because the length of the diagonal
is not take into account - i.e. the horizontal, vertical and diagonal
distances are treated with equal weight. The real distance along the
diagonal should be sqrt(2). Thus, at the corner of the square the DT
gets increased or decreased by 1 in the diagonal direction instead of
1.414. I haven't looked closely at this so perhaps I'm mistaken - it
just seemed unnecessary.

The other thing I didn't like was that is seemed to introduce an
asymmetry. I thought you get a different result depending when you
swap foreground and background, and there didn't seem to be any reason
for this. The applications I was using the DT for didn't require a
line of voxels set to zero, so I was happy to consider the positive to
negative crossing as happening between voxels.


On Fri, Aug 13, 2010 at 7:03 PM, Benjamin King <benjaminking at web.de> wrote:
> Hi Richard,
>
>
> thanks for pointing me to your paper. Due to the beauty of Open Access, I'm
> currently checking it out.
>
> Can you give me some advice on how to run perfDT3D manually? I have tried to
> provide the six parameters that the perfDT3D usage tips display, but the
> code requires argc==8 and there seems to be a disparity for the usage of
> argv[1]:
>
> iterations = atoi(argv[1]);
> ...
> IType::Pointer inputOrig = readIm<IType>(argv[1]);
>
> 'make test'  works, though, so this is probably a misconception on my
> behalf.
>
> The code submitted with your paper compiles well and the tests are working
>
>  The rleTest in the latest code at
> http://voxel.jouy.inra.fr/darcs/contrib-itk/parabolicMorphology does not
> compile. I just commented out the body of the doRLE function for the time
> being. On my machine, all tests with the exception of Perf pass, while Perf
> ends with a segmentation fault. Is this related to doRLE?
>
>
>> http://hdl.handle.net/1926/1370
>> [...] I only discovered the generalized DT
>> package after I wrote most of it and never got around to sorting out
>> the details of how they matched up.
>
> The code that I turned up with is not as nicely decomposed into small
> functions as yours. All the loops and decomposition for threading is handled
> in GenerateData.
>
> The algorithm that is implemented by GeneralizedDistanceTransformImageFilter
> needs a temporary vector that manages a lower envelope of a set of
> parabolas. A lot of runtime goes into finding intersection points and
> adding/removing parabolas to this vector, about 35% on my machine.
> The sampling of the envelope takes a little less than 20% runtime.
>
> While I haven't read the original paper that you reference for details on
> the algorithm, I haven't seen code concerned with intersections in doLine().
> Therefore I think that the methods are somewhat different.
>
>
>> It is also loads faster for distance transforms, is fully threaded and
>> there are helper classes for doing binary erosion and dilation. I
>> personally think that the approach of both existing ITK signed DT
>> filters on using a 3x3 morphological operation to introduce a zero
>> contour is wrong (it is definitely wrong at corners) because it
>> introduces a somewhat pointless asymmetry between foreground and
>> background so the signed DT in the parabolicMorph package doesn't do
>> that.
>
> Can you elaborate on that? What would you expect to happen on the corners of
> a square, for example?
>
>
> Regards,
>  Benjamin
>