[Insight-developers] Insight-developers Digest, Vol 115, Issue 1

Padfield, Dirk R (GE Global Research) padfield at research.ge.com
Thu Dec 26 13:01:39 EST 2013


Hi Richard,

It looks like this old thread was re-posted; not sure why.  But I thought I would respond in case any clarity is needed.

The patch to address this issue has already been merged: http://review.source.kitware.com/#/c/13116/

The implementation, based on consensus, was to add a flag to the FlatStructuringElement code to enable users to change the mode if desired.  No changes were made to the defaults.

Thanks,
Dirk


On Dec 24, 2013, at 12:00 PM, insight-developers-request at itk.org wrote:

> Send Insight-developers mailing list submissions to
> 	insight-developers at itk.org
> 
> To subscribe or unsubscribe via the World Wide Web, visit
> 	http://www.itk.org/mailman/listinfo/insight-developers
> or, via email, send a message with subject or body 'help' to
> 	insight-developers-request at itk.org
> 
> You can reach the person managing the list at
> 	insight-developers-owner at itk.org
> 
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of Insight-developers digest..."
> 
> 
> Today's Topics:
> 
>   1. Re: BUG in BinaryBallStructuringElement (Richard Beare)
> 
> 
> ----------------------------------------------------------------------
> 
> Message: 1
> Date: Fri, 18 Oct 2013 09:21:27 +1100
> From: Richard Beare <richard.beare at gmail.com>
> To: "Johnson, Hans J" <hans-johnson at uiowa.edu>
> Cc: "insight-developers at itk.org" <insight-developers at itk.org>,
> 	"Padfield,	Dirk R \(GE Global Research\)" <padfield at research.ge.com>
> Subject: Re: [Insight-developers] BUG in BinaryBallStructuringElement
> Message-ID:
> 	<CA+V7QS_yN1tfqcuNeNS1HLGjna5gmY6FeZzjK=6RpFZr=9HdSA at mail.gmail.com>
> Content-Type: text/plain; charset="iso-8859-1"
> 
> Hi all,
> I haven't been involved in the thread till now.
> 
> A couple of points that may have been covered somewhere in the thread.
> 
> The original binary ball structuring element has been part of ITK almost
> for ever. It uses Bresenham sphere's/circles - this leads to one criteria
> for whether a voxel is inside or outside. From memory the decision is based
> on whether any part of a voxel is closer than the specified radius. The
> original motivation was apparently the Bresenham algorithm that used only
> integer arithmetic.
> 
> This is one choice for approximating circles/spheres with voxels, but
> obviously not the only one. Other obvious choices are 1) centre of voxel
> must be closer than the radius to be inside or 2) all of a voxel must be
> inside. Any of these options look OK for larger circles and all can look
> bad for small ones.
> 
> I'd certainly be supporting Brad's advice of not changing the current
> defaults. The best option, if people are really unhappy with the current
> circles, is to make it a bit easier to import an image as a structuring
> element and use that. There was some code floating around in the original
> contribution that did this, but it may have been lost.
> 
> Here's a summary of how I remember the structuring element options via the
> grayscale morphology tools:
> 
> Do use the FlatStructuringElement. It ties all the algorithms together and
> provides a consistent interface. "Flat" refers to binary, not 2D - i.e a
> structuring element of 1's and 0's rather than a structuring function of
> arbitrary values (e.g. ranging from 0 to 1).
> 
> 1)  If you use the "Ball" option :
> 
>  typedef typename itk::FlatStructuringElement< dim > SRType;
> 
>  typename SRType::RadiusType rad;
>  rad.Fill(10);
>  SRType kernel;
> 
>  kernel = SRType::Ball(rad);
> 
> Then the ball will be constructed using the BinaryBallStructuringElement
> code.
> 
> You then have a choice of algorithm
> a) Default, direct implementation
> b) Sliding histogram
> 
> sliding histogram is much faster for anything bigger than the unit SE.
> Sliding histogram gives identical results to the direct implementation
> 
> Naive: O(n^d)
> Histogram : O(n^(d-1))
> 
> where n=radius, d=SE dimension.
> 
> 2) Poly option:
> 
> This is an example of the decomposition approach. A circle is constructed
> by repeated applications of lines at angles. The approximation is quite
> good - there are some pictures in the IJ paper, or you can generate them by
> dilating a single voxel. However it is difficult to achieve an exact
> radius. For example you might be able to get a good radius 25 circle, but
> have trouble getting something that is 26. The construction approach
> attempts to be smart about the number of angles and length of lines, but it
> isn't possible to achieve perfect circles of arbitrary size this way.
> 
> There is code for 3D, but the approximations to spheres are not great. You
> can get cubes with corners cut off and some more complex shapes, but these
> need to be quite big to be useful.
> 
> The big benefit of this option is low complexity:
> 
> k O(const), where k is the line count in the decomposition.
> 
> 3) Box
> basically a special case of the Poly. These are exact boxes.
> 
> 
> These are all for greyscale images, but work on binary too. However there
> are some other options for operations with circles/spheres on binary images
> that I can go into if this is of interest.
> 
> Finally, just a practical note based on personal experience:
> 
> I find that exact structuring element size isn't usually a big concern.
> Typically, when I want to use a large structuring element it is to
> eliminate larger objects, so it really doesn't matter if the size isn't
> exactly what I requested. If it does matter then the approach is never
> going to be reliable.
> 
> Hope this helps
> 
> 
> 
> On Fri, Oct 18, 2013 at 7:27 AM, Johnson, Hans J <hans-johnson at uiowa.edu>wrote:
> 
>> I like the idea of a new element the best.  It keeps it clean and easy to
>> replace.
>> 
>> Hans
>> 
>> 
>> -----Original Message-----
>> From: <Miller>, "James V   (GE Global Research)" <millerjv at ge.com>
>> Date: Thursday, October 17, 2013 2:45 PM
>> To: Bradley Lowekamp <blowekamp at mail.nih.gov>, "Padfield, Dirk R (GE
>> Global Research)" <padfield at research.ge.com>
>> Cc: Richard Beare <richard.beare at gmail.com>, Hans Johnson
>> <hans-johnson at uiowa.edu>, ITK <insight-developers at itk.org>
>> Subject: RE: [Insight-developers] BUG in BinaryBallStructuringElement
>> 
>> Our current element does not build the ball by alternating the application
>> of crosses and boxes.  Perhaps we should have an element that does it that
>> way.  For speed, I think old school morphology would not build a large
>> structuring element but apply small elements in a particular sequence to
>> the image (dilate with triangle, dilate with rotated triangle, ...).
>> 
>> I like the idea of introducing a new structuring element that implements
>> Dirk's design.  I'd also be happy with a mode on the current element to
>> switch between the behaviors as long as the default was the current
>> behavior.
>> 
>> 
>> 
>> -----Original Message-----
>> From: insight-developers-bounces at itk.org
>> [mailto:insight-developers-bounces at itk.org] On Behalf Of Bradley Lowekamp
>> Sent: Thursday, October 17, 2013 1:44 PM
>> To: Padfield, Dirk R (GE Global Research)
>> Cc: Richard Beare; Johnson, Hans J; insight-developers at itk.org
>> Subject: Re: [Insight-developers] BUG in BinaryBallStructuringElement
>> 
>> Dirk,
>> 
>> First, I have been using the FlatStructuringElement class as opposed to
>> the BinaryBallStructuring element. Does the resulting shape differ? I
>> think they should be consistent.
>> 
>> Please, please do not  change the shape of the current structuring
>> elements.
>> 
>> Many optimized usage and implementation of morphology rely on a specific
>> decomposition of the binary ball structuring element. To create a ball,
>> you are alternate between a 1-cross and a 1-box. I believe your change is
>> simple switching for the cross be for the box. Which would make such
>> decomposition optimization inconsistent.
>> 
>> I would suggest you create a new structuring element class to meet you
>> needs. I think this would make a easier transition of we wish to deprecate
>> the current version in favor of yours interpretation of correctness.
>> 
>> I would like to hear from Richard Beare and/or Gaetan on this issue. They
>> are the resident morphology experts in our community.
>> 
>> 
>> Brad
>> 
>> On Oct 17, 2013, at 1:14 PM, "Padfield, Dirk R (GE Global Research)"
>> <padfield at research.ge.com> wrote:
>> 
>>> Hi Ho,
>>> 
>>> Thanks for looking into this more closely.  Your agreement that this is
>>> a bug is encouraging!
>>> 
>>> Now, what to do...This is the perennial battle between backward
>>> compatibility and future correctness!
>>> 
>>> Hans' suggestion to add a member function to enable the correct behavior
>>> makes sense.  But I am concerned that it adds additional complexity and
>>> that these methods will be ignored if not set as default.
>>> 
>>> Hans, what do you think about the idea of adding such a method and then
>>> marking the old method as deprecated and setting an
>>> ITK_FUTURE_LEGACY_REMOVE flag?
>>> 
>>> Thanks,
>>> Dirk
>>> 
>>> ________________________________
>>> From: Ho Cheung [hocheung20 at gmail.com]
>>> Sent: Thursday, October 17, 2013 12:22 PM
>>> To: Padfield, Dirk R (GE Global Research)
>>> Subject: Re: [Insight-developers] BUG in BinaryBallStructuringElement
>>> 
>>> I totally agree that the corrected version is more accurate.
>>> 
>>> Upon examining the code more closely and further thought, it also does
>>> seem to be an oversight by the original author.
>>> 
>>> Furthermore, my suggestion that it was simply a discretization problem
>>> turns out to be a non-sequiter. It turns out that the additional pixel on
>>> the axes length was approximating the "rounding discretization process"
>>> for the radius sizes I was looking at.
>>> 
>>> I do share the same concerns about backwards compatibility as Hans and
>>> Wes, but definitely I'll change my opinion of this to being an actual bug.
>>> 
>>> Regards,
>>> 
>>> Ho Cheung
>>> (775) 388-2368
>>> 
>>> On Oct 17, 2013, at 8:09 AM, Padfield, Dirk R (GE Global Research)
>>> <padfield at research.ge.com<mailto:padfield at research.ge.com>> wrote:
>>> 
>>> Hi Ho,
>>> 
>>> Thanks for your feedback and insight!  I agree that discretizing
>>> continuous functions is always a tricky thing.  Luckily, we have the
>>> spatial objects to help with this since they define their own
>>> inside-outside tests.  The Ellipse spatial object is used in the
>>> BinaryBallStructuringElement implementation, but the problem is that the
>>> spatial object itself is used incorrectly.  By definition, the axes
>>> should be "radius*2" rather than "radius*2+1".  Defining the axes of an
>>> ellipse/circle to be "radius*2+1" is simply an error.
>>> 
>>> We can also attack this question by considering the area of the
>>> continuous function versus the discretized version by counting the number
>>> of "on" pixels in the kernel as follows:
>>> 
>>> For radius=1, the true area is pi = 3.14 Using the old version, we get
>>> 9 Using the correction, we get 5
>>> 
>>> For radius=5, the true area is 25*pi = 78.5 Using the old version, we
>>> get 97 (24% error) Using the correction, we get 81 (3% error)
>>> 
>>> For radius=11, the true area is 121*pi = 380 Using the old version, we
>>> get 421 (11% error) Using the correction, we get 377 (1% error)
>>> 
>>> For radius=21, the true area is 21*21*pi = 1385 Using the old version,
>>> we get 1457 (5% error) Using the correction, we get 1373 (1% error)
>>> 
>>> As expected, as the radius increases, the discretized version better
>>> approximates the continuous function.  We can also see that the corrected
>>> version is always more accurate than the old version.
>>> 
>>> What do you think?
>>> 
>>> Thanks,
>>> Dirk
>>> 
>>> 
>>> ________________________________
>>> From: Ho Cheung [hocheung20 at gmail.com<mailto:hocheung20 at gmail.com>]
>>> Sent: Wednesday, October 16, 2013 6:26 PM
>>> To: Padfield, Dirk R (GE Global Research)
>>> Cc: ITK
>>> Subject: Re: [Insight-developers] BUG in BinaryBallStructuringElement
>>> 
>>> Dirk,
>>> 
>>> As a counterpoint, I do not agree that there is a bug but rather just an
>>> ambiguity in the way we have defined whether or not a pixel is to be
>>> included.
>>> 
>>> If you take a protractor and plotted a unit circle, then superimpose a
>>> grid on it (this this case, 3x3), and then shaded in the nearest pixels
>>> to the circle, it would look like the "original" example. The same
>>> applies to the radius 5 circle.
>>> 
>>> Technically, if you look at the parametric definition of a circle, then
>>> yes, those pixels would not be included, as their physical space points
>>> fall outside the circle.
>>> 
>>> However, I believe (anecdotal) in graphics rendering, it is common
>>> practice to include those pixels which are nearest to the actual physical
>>> space point.
>>> 
>>> Regards,
>>> 
>>> Ho Cheung
>>> (775) 388-2368
>>> 
>>> On Oct 16, 2013, at 1:05 PM, Padfield, Dirk R (GE Global Research)
>>> <padfield at research.ge.com<mailto:padfield at research.ge.com><mailto:
>> padfield
>>> @research.ge.com>> wrote:
>>> 
>>> Hi All,
>>> 
>>> I am writing to ask your advice about a bug I found in
>>> BinaryBallStructuringElement.
>>> 
>>> For a while, I have been bothered by the fact that the
>>> BinaryBallStructuringElement return balls that are larger than the
>>> specified radius.  For example, when given a radius of 1, it returns the
>>> structuring element:
>>> 1    1    1
>>> 1    1    1
>>> 1    1    1
>>> 
>>> But this structuring element has a radius that is more than 1!  If it
>>> truly had a radius of 1, it would be a cross shape in this case.
>>> 
>>> When choosing a larger radius, the problem is more obvious.  Setting
>>> radius = 5 (leading to a structuring element size of 11x11) results in:
>>> 0    0    0    1    1    1    1    1    0    0    0
>>> 0    0    1    1    1    1    1    1    1    0    0
>>> 0    1    1    1    1    1    1    1    1    1    0
>>> 1    1    1    1    1    1    1    1    1    1    1
>>> 1    1    1    1    1    1    1    1    1    1    1
>>> 1    1    1    1    1    1    1    1    1    1    1
>>> 1    1    1    1    1    1    1    1    1    1    1
>>> 1    1    1    1    1    1    1    1    1    1    1
>>> 0    1    1    1    1    1    1    1    1    1    0
>>> 0    0    1    1    1    1    1    1    1    0    0
>>> 0    0    0    1    1    1    1    1    0    0    0
>>> 
>>> This is clearly not an ellipse/circle with radius 5 because the interior
>>> ellipse/circle is touching each image border at five points rather than
>>> just one.  As it turns out, the code is actually defining a radius that
>>> is "X + 0.5", where X is the radius that is requested!
>>> 
>>> The problem is in the specification of the ellipse axes on lines 70-76
>>> of itkBinaryBallStructuringElement.hxx:
>>> // Define and set the axes lengths for the ellipsoid typename
>>> EllipsoidType::InputType axes; for ( i = 0; i < VDimension; i++ )  {
>>> axes[i] = this->GetSize(i);  }
>>> spatialFunction->SetAxes(axes);
>>> 
>>> In this case, "this->GetSize()" is equal to radius*2+1.  But, an
>>> ellipse/circle with radius X should have axes length 2X, not 2X+1!  In
>>> the implementation, the center of the ellipse is properly accounted for
>>> by setting it to "this->GetRadius+1", but the size of the ellipse is not
>>> correct!
>>> 
>>> To correct this, we can make a simple change either  axes[i] =
>>> this->GetSize(i) - 1; or  axes[i] = this->GetRadius(i) * 2;
>>> 
>>> The second is probably more intuitive.
>>> 
>>> With this fix, we get for radius=1:
>>> 0    1    0
>>> 1    1    1
>>> 0    1    0
>>> 
>>> and for radius=5:
>>> 0    0    0    0    0    1    0    0    0    0    0
>>> 0    0    1    1    1    1    1    1    1    0    0
>>> 0    1    1    1    1    1    1    1    1    1    0
>>> 0    1    1    1    1    1    1    1    1    1    0
>>> 0    1    1    1    1    1    1    1    1    1    0
>>> 1    1    1    1    1    1    1    1    1    1    1
>>> 0    1    1    1    1    1    1    1    1    1    0
>>> 0    1    1    1    1    1    1    1    1    1    0
>>> 0    1    1    1    1    1    1    1    1    1    0
>>> 0    0    1    1    1    1    1    1    1    0    0
>>> 0    0    0    0    0    1    0    0    0    0    0
>>> 
>>> This is a true circle with radius 5!
>>> 
>>> My questions are:
>>> 1) Is anyone else bothered by this bug?  I imagine that many users
>>> expect the corrected version and don't realize they are getting the
>>> incorrect one.
>>> 2) Do others agree with this fix?
>>> 3) Can we make this fix given the number of filters/applications that
>>> will change slightly as a result of this fix?
>>> 
>>> Many thanks,
>>> Dirk
>>> 
>>> 
>>> 
>>> _______________________________________________
>>> Powered by
>>> www.kitware.com<http://www.kitware.com><http://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://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-developers
>>> 
>>> 
>>> _______________________________________________
>>> 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://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-developers
>> 
>> _______________________________________________
>> 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://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-developers
>> 
>> 
>> 
>> ________________________________
>> 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.
>> ________________________________
>> 
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL: <http://www.itk.org/pipermail/insight-developers/attachments/20131018/cc3d711c/attachment.html>
> 
> ------------------------------
> 
> _______________________________________________
> Insight-developers mailing list
> Insight-developers at itk.org
> http://www.itk.org/mailman/listinfo/insight-developers
> 
> 
> End of Insight-developers Digest, Vol 115, Issue 1
> **************************************************



More information about the Insight-developers mailing list