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, [email protected] wrote: > Send Insight-developers mailing list submissions to > [email protected] > > 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 > [email protected] > > You can reach the person managing the list at > [email protected] > > 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 <[email protected]> > To: "Johnson, Hans J" <[email protected]> > Cc: "[email protected]" <[email protected]>, > "Padfield, Dirk R \(GE Global Research\)" > <[email protected]> > Subject: Re: [Insight-developers] BUG in BinaryBallStructuringElement > Message-ID: > <CA+V7QS_yN1tfqcuNeNS1HLGjna5gmY6FeZzjK=6RpFZr=9h...@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 > <[email protected]>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)" <[email protected]> >> Date: Thursday, October 17, 2013 2:45 PM >> To: Bradley Lowekamp <[email protected]>, "Padfield, Dirk R (GE >> Global Research)" <[email protected]> >> Cc: Richard Beare <[email protected]>, Hans Johnson >> <[email protected]>, ITK <[email protected]> >> 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: [email protected] >> [mailto:[email protected]] 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; [email protected] >> 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)" >> <[email protected]> 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 [[email protected]] >>> 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) >>> <[email protected]<mailto:[email protected]>> 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 [[email protected]<mailto:[email protected]>] >>> 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) >>> <[email protected]<mailto:[email protected]><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 > [email protected] > http://www.itk.org/mailman/listinfo/insight-developers > > > End of Insight-developers Digest, Vol 115, Issue 1 > ************************************************** _______________________________________________ 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
