[Insight-developers] Bug found in SignedDanielssonDistanceMap

Sun Oct 14 16:13:33 EDT 2012

Hi Hans,

I have submitted a patch for this issue and included you and Brad Lowekamp as reviewers.

Thanks,

Dirk

________________________________
From: Johnson, Hans J [hans-johnson at uiowa.edu]
Sent: Thursday, October 11, 2012 9:26 AM
To: Padfield, Dirk R (GE Global Research); insight-developers at itk.org
Subject: Re: [Insight-developers] Bug found in SignedDanielssonDistanceMap

Awesome!  Thank you.

I created a JIRA ticket: https://issues.itk.org/jira/browse/ITK-2960

So that we can track it, (and you get full credit for fixing this).

Hans
=================================================================
Hans J. Johnson, Ph.D.
Assistant Professor, Department of Psychiatry

Mailing Address:
W274 GH                             Email: hans-johnson at uiowa.edu
200 Hawkins Drive                   Phone: (319) 353 8587
The University of Iowa
Iowa City, IA 52242

-----Original Message-----
From: <Padfield>, "Dirk R   (GE Global Research)"
<padfield at research.ge.com>
Date: Thursday, October 11, 2012 8:08 AM
To: Hans Johnson <hans-johnson at uiowa.edu>, ITK <insight-developers at itk.org>
Subject: RE: [Insight-developers] Bug found in SignedDanielssonDistanceMap

Hi Hans,

I plan to submit a patch by the end of the weekend.  I want to submit some
good image regression tests along with the code changes since those
filters currently don't have any.  That is why the bug wasn't found until
now.

Thanks,
Dirk

-----Original Message-----
From: Johnson, Hans J [mailto:hans-johnson at uiowa.edu]
Sent: Wednesday, October 10, 2012 5:39 PM
To: Padfield, Dirk R (GE Global Research); insight-developers at itk.org
Subject: Re: [Insight-developers] Bug found in SignedDanielssonDistanceMap

Dirk,

Do you have an ETA of how long until you could address creating a patch
for this?  It looks like a small change, but since you have thought about
it carefully, it would be best if you could provide the patch.

Thanks,
Hans

=================================================================
Hans J. Johnson, Ph.D.
Assistant Professor, Department of Psychiatry

Mailing Address:
W274 GH                             Email: hans-johnson at uiowa.edu
200 Hawkins Drive                   Phone: (319) 353 8587
The University of Iowa
Iowa City, IA 52242

-----Original Message-----
From: <Padfield>, "Dirk R   (GE Global Research)"
<padfield at research.ge.com>
Date: Thursday, October 4, 2012 11:02 PM
To: ITK <insight-developers at itk.org>
Subject: Re: [Insight-developers] Bug found in SignedDanielssonDistanceMap

Hi Brad,

Thank you for finding this bug and letting us know.  After some searching,
I found that the problem is a result of an error in the initialization of
the voronoiMap variable in the itkDanielssonDistanceMapImageFilter.  There
is no problem with itkSignedDanielssonDistanceMapImageFilter since all it
does is call itkDanielssonDistanceMapImageFilter twice, one time with an
inverted image, and then subtract the two unsigned distance maps to get a
signed distance map.  The itkSignedDanielssonDistanceMapImageFilter sets
the "SetInputIsBinary" flag of itkDanielssonDistanceMapImageFilter to
true, so that the following code is called to initialize the voronoiMap in
lines 170-186 of the PrepareData method of
itkDanielssonDistanceMapImageFilter:

  if ( m_InputIsBinary )
    {
    VoronoiPixelType npt = 1;
    while ( !ot.IsAtEnd() )
      {
      if ( it.Get() )
        {
        ot.Set(npt++);
        }
      else
        {
        ot.Set(0);
        }
      ++it;
      ++ot;
      }
    }

Here "it" is an iterator over the input image, and "ot" is an iterator
over the voronoiMap.  In this loop, the voronoiMap values are ever
increasing as the variable "npt" is incremented. This causes the
voronoiMap values to wrap-around when "npt" is incremented beyond the
value that can be held by the type.  In
itkDanielssonDistanceMapImageFilter.h, the type of the VoronoiMap variable
is a template parameter, and, if it is not set, it defaults to the type of
the InputImage:
template< class TInputImage, class TOutputImage, class TVoronoiImage =
TInputImage >

So if, for example, the input is "unsigned char", which is reasonable, but
the image has more than 255 pixels total, which is usual, this npt will
lead to wrap-around errors.  I believe this variable should not be
incremented.  In that case, the voronoi map resulting after running the
whole filter will have values all 1, which makes sense because by stating
that "SetInputIsBinary", we are saying there is only one label, and thus
the voronoi partition has only one region.  I tested this on a number of
images, and it worked correctly.

We should probably also change the two calls to "SetInputIsBinary" from
"true" to "false" in itkSignedDanielssonDistanceMapImageFilter.hxx.  As I
mentioned, having these set to "true" results in a voronoi map that is all
one label.  However, if they are set to "false", this yields a more
informative voronoi map (actually, the second one will become binary
anyway because of the inversion process, so the flag for that one doesn't
matter).  For example, I have attached to this message the voronoi map
resulting from turning those flags off for the test image that you used.
If you overlay it with the original image, you will see that it indeed
creates the correct voronoi partition of the image from the zero values of
the original image.

So, I recommend that we get rid of the "++" of the "npt" variable, and
this will solve the problem.  We should also add a regression test to test
this case in ITK itself (since you found it with a test in SimpleITK).  I
am willing to make these changes and submit a patch.

Any thoughts?

Dirk

Date: Thu, 4 Oct 2012 07:20:33 -0400
From: Bradley Lowekamp <blowekamp at mail.nih.gov>
Subject: [Insight-developers] Bug found in SignedDanielssonDistanceMap
To: ITK Developers <insight-developers at itk.org>
Message-ID: <65179107-1A18-4C78-8334-33CB59CF483D at mail.nih.gov>
Content-Type: text/plain; charset="us-ascii"

Hello,

I had updated SimpleITK's ITK version to the 4.2.1 release candidate and
then to 4.2.1 with out a problem.

However, yesterday I upgraded sitk's next branch to the latest ITK master,
to get fixes for a label map contour filter, and I am getting wide spread
failures for the SignedDanielssonDistanceMap image filter:

http://open.cdash.org/testSummary.php?project=40&name=BasicFilters.SignedDa
nielssonDistanceMap&date=2012-10-04

Here is the failing comparison to the baseline:

http://open.cdash.org/testDetails.php?test=161367787&build=2595127

While the errors appear to be random, I check a mac, linux and windows
system and they appear to be failing in the same fashion.

I am not sure were this change occurred. Does anyone know what may have
changed?

Thanks,
Brad

________________________________
Notice: This UI Health Care e-mail (including attachments) is covered by
the Electronic Communications Privacy Act, 18 U.S.C. 2510-2521, is
confidential and may be legally privileged.  If you are not the intended
recipient, you are hereby notified that any retention, dissemination,
distribution, or copying of this communication is strictly prohibited.
Please reply to the sender that you have received the message in error,
then delete it.  Thank you.
________________________________

________________________________
Notice: This UI Health Care e-mail (including attachments) is covered by the Electronic Communications Privacy Act, 18 U.S.C. 2510-2521, is confidential and may be legally privileged.  If you are not the intended recipient, you are hereby notified that any retention, dissemination, distribution, or copying of this communication is strictly prohibited.  Please reply to the sender that you have received the message in error, then delete it.  Thank you.
________________________________