[Insight-developers] BUG in BinaryBallStructuringElement
Padfield, Dirk R (GE Global Research)
padfield at research.ge.com
Wed Oct 23 11:55:41 EDT 2013
Hi Developers,
Thank you all for your insightful comments. Taking into account all of your feedback, I decided to add a mode to the FlatStructuringElement, OFF by default, to enable the more accurate computation that I mentioned in my messages.
I submitted a patch here: http://review.source.kitware.com/#/c/13116/
I also added a wiki example (linked from http://www.itk.org/Wiki/ITK/Examples#Morphology) here: http://www.itk.org/Wiki/ITK/Examples/Morphology/FlatStructuringElementForegroundHasAccurateArea
Thanks again,
Dirk
________________________________
From: Richard Beare [richard.beare at gmail.com]
Sent: Thursday, October 17, 2013 6:21 PM
To: Johnson, Hans J
Cc: Miller, James V (GE Global Research); Bradley Lowekamp; Padfield, Dirk R (GE Global Research); insight-developers at itk.org
Subject: Re: [Insight-developers] BUG in BinaryBallStructuringElement
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<mailto: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<mailto:millerjv at ge.com>>
Date: Thursday, October 17, 2013 2:45 PM
To: Bradley Lowekamp <blowekamp at mail.nih.gov<mailto:blowekamp at mail.nih.gov>>, "Padfield, Dirk R (GE
Global Research)" <padfield at research.ge.com<mailto:padfield at research.ge.com>>
Cc: Richard Beare <richard.beare at gmail.com<mailto:richard.beare at gmail.com>>, Hans Johnson
<hans-johnson at uiowa.edu<mailto:hans-johnson at uiowa.edu>>, ITK <insight-developers at itk.org<mailto: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>
[mailto: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<mailto: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<mailto: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<mailto: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<tel:%28775%29%20388-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><mailto: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><mailto: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<tel:%28775%29%20388-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 at research.ge.com<mailto:padfield at research.ge.com>><mailto:padfield<mailto:padfield>
>@research.ge.com<http://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><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<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<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
________________________________
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.
________________________________
More information about the Insight-developers
mailing list