[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