[Insight-developers] OtsuThresholdCalculator versus OtsuMultipleThresholdsCalculator
Bill Lorensen
bill.lorensen at gmail.com
Tue Jul 9 11:30:15 EDT 2013
Nice job Dirk.
If you add GetMeasurement, leave GetBinMax for backward compatibility.
Bill
On Tue, Jul 9, 2013 at 11:22 AM, Padfield, Dirk R (GE Global Research) <
padfield at research.ge.com> wrote:
> Hi All,
>
> Sorry for my delayed reply; I wanted to go through the code so that I
> could give an accurate answer about the differences. I have now had the
> chance to carefully compare the Otsu and OtsuMultiple code, and I found a
> number of discrepancies that I have fixed. Here is a summary:
>
> First of all, the equations used for the two filters are different because
> the Otsu uses a simplified mathematical representation that only holds when
> there is one threshold. I derived the equations to check that they lead to
> the same mathematical representation, and they do.
>
> For all of the tests, I used the 8-bit image
> ExternalData/Testing/Data/Input/cthead1.png. For each code line below, the
> original line is shown with a "-" first, and the new line is shown with a
> "+" first. All of the comments are about the Otsu because the MultipleOtsu
> is implemented more accurately.
>
> In Otsu, the global mean was being computed incorrectly. We can measure
> this because we can compare the value computed from the histogram to the
> true mean of the image pixels, which is 77.76. The original and corrected
> code are as follows:
> - totalMean += ( j + 1 ) * relativeFrequency[j];
> + totalMean += histogram->GetMeasurementVector(j)[0] *
> relativeFrequency[j];
>
> Here is a comparison of the mean calculated for different bin values.
> Clearly, it should be close to 77.76 for all of them. Before it was a
> monotonically increasing value, but now it is more consistent (it is never
> exactly 77.76 because of how the histogram bins store the image pixels).
> Bins: 4,8,16,32,64,128,256,512,1024
> Old Mean: 1.95, 3.07, 5.42, 10.36, 20.12, 39.66, 78.76, 156.92, 312.99
> New Mean: 92.95, 81.90, 78.38, 78.56, 78.18, 78.03, 77.96, 77.91, 77.82
>
> The initial left mean was being computed incorrectly. By mathematical
> definition, when the leftMean is computed from only the first bin of the
> histogram, it is equal to the bin value itself.
> - double meanLeft = 1.0;
> + double meanLeft = histogram->GetMeasurementVector(0)[0];
>
> The left mean was computed incorrectly in the loop. It only made sense
> when the number of bins was the same as the number of gray levels of the
> image itself.
> - + ( j + 1 ) * relativeFrequency[j] ) / freqLeft;
> + + ( histogram->GetMeasurementVector(j)[0] ) *
> relativeFrequency[j] ) / freqLeft;
>
> The offset of 1 was incorrect in the GetMeasurement call.
> - this->GetOutput()->Set( static_cast<OutputType>(
> histogram->GetMeasurement( maxBinNumber + 1, 0 ) ) );
> + this->GetOutput()->Set( static_cast<OutputType>(
> histogram->GetMeasurement( maxBinNumber, 0 ) ) );
>
> Finally, there is a discrepancy in that Otsu uses GetMeasurement (as shown
> above), but OtsuMultiple uses GetBinMax to get the final threshold. The
> difference is that GetMeasurement is the average of GetBinMax and
> GetBinMin. When the number of bins is large, this makes almost no
> difference because the GetBinMin and GetBinMax are almost the same. But
> for small numbers of bins, the GetMeasurement is more stable. Here are
> some example results:
>
> Bins: 4,8,16,32,64,128,256,512,1024
> GetBinMin: 63.91, 63.83, 63.79, 79.71, 79.70, 81.69, 83.68,
> 83.67, 83.92
> GetBinMax: 127.82, 95.74, 79.74, 87.68, 83.68, 83.68, 84.67,
> 84.17, 84.17
> GetMeasurement: 95.86, 79.79, 71.76, 83.70, 81.69, 82.68, 84.17, 83.92,
> 84.05
>
> Finally, the thresholds should be rounded at the end of the calculator so
> that they are not truncated by the corresponding ImageFilters.
>
> I recommend making all of the changes to the Otsu listed above and
> changing the GetBinMax to GetMeasurement in the OtsuMultiple. This will
> make the two completely consistent. The results are as follows for
> different number of bins:
>
> Bins: 4,8,16,32,64,128,256,512,1024
> Old Otsu threshold: 159.77, 111.70, 87.71, 91.67, 85.68, 84.67, 85.17,
> 84.42, 84.30
> New threshold: 95.86, 79.79, 71.76, 83.70, 81.69, 82.68, 84.17,
> 83.92, 84.05
>
> The ImageJ Otsu plugin (
> http://rsbweb.nih.gov/ij/plugins/otsu-thresholding.html) outputs a
> threshold of 79.
> The ImageJ MultipleOtsu plugin (
> http://rsbweb.nih.gov/ij/plugins/multi-otsu-threshold.html) with 1
> threshold outputs a threshold of 87.
> Using Matlab, I get 84.
> So they are not consistent, but they are all close.
>
> Thanks,
> Dirk
>
> ________________________________
> From: Richard Beare [richard.beare at gmail.com]
> Sent: Wednesday, July 03, 2013 6:01 PM
> To: Padfield, Dirk R (GE Global Research)
> Cc: Johnson, Hans J; Matt McCormick; Bradley Lowekamp; <
> insight-developers at itk.org> Developers; Gaëtan Lehmann
> Subject: Re: [Insight-developers] OtsuThresholdCalculator versus
> OtsuMultipleThresholdsCalculator
>
> Is the difference in threshold when there are a small number of bins
> explainable via the one bin difference? If it isn't then that is cause for
> concern. Otherwise it is just another side effect of the original
> difference. Small numbers of bins can easily break the assumptions in many
> of the histogram based methods, as can data with features like large
> numbers of zeros or maximum values.
>
>
> On Thu, Jul 4, 2013 at 6:17 AM, Padfield, Dirk R (GE Global Research) <
> padfield at research.ge.com<mailto:padfield at research.ge.com>> wrote:
> Exactly. It seems crazy to use more than 256 bins in that case. But the
> goal of that test was simply timing, and the best way to increase the
> computation time is to increase the number of bins.
>
> The real takeaway message is: either implementation is equally fast for
> reasonably-sized inputs, so there is no timing-based concern for replacing
> one for the other.
>
> Dirk
>
>
> ________________________________________
> From: Johnson, Hans J [hans-johnson at uiowa.edu<mailto:
> hans-johnson at uiowa.edu>]
> Sent: Wednesday, July 03, 2013 3:04 PM
> To: Padfield, Dirk R (GE Global Research); Matt McCormick
> Cc: Bradley Lowekamp; <insight-developers at itk.org<mailto:
> insight-developers at itk.org>> Developers; Richard.Beare at ieee.org<mailto:
> Richard.Beare at ieee.org>; Gaëtan Lehmann
> Subject: Re: [Insight-developers] OtsuThresholdCalculator versus
> OtsuMultipleThresholdsCalculator
>
> Dirk,
>
> With 10,000,000 bins, and an unsigned char data set this seems suspicious.
> Are there real needs for such a large number of bins?
>
> I'd hate to spend a lot of time doing optimizations for 10,000,000 bins if
> there is no real-world use case for it.
>
> Hans
>
>
> -----Original Message-----
> From: <Padfield>, "Dirk R (GE Global Research)"
> <padfield at research.ge.com<mailto:padfield at research.ge.com>>
> Date: Wednesday, July 3, 2013 1:27 PM
> To: Matt McCormick <matt.mccormick at kitware.com<mailto:
> matt.mccormick at kitware.com>>, Hans Johnson
> <hans-johnson at uiowa.edu<mailto:hans-johnson at uiowa.edu>>
> Cc: Bradley Lowekamp <blowekamp at mail.nih.gov<mailto:blowekamp at mail.nih.gov>>,
> ITK
> <insight-developers at itk.org<mailto:insight-developers at itk.org>>, "
> Richard.Beare at ieee.org<mailto:Richard.Beare at ieee.org>"
> <Richard.Beare at ieee.org<mailto:Richard.Beare at ieee.org>>, Gaëtan Lehmann <
> gaetan.lehmann at gmail.com<mailto:gaetan.lehmann at gmail.com>>
> Subject: RE: [Insight-developers] OtsuThresholdCalculator versus
> OtsuMultipleThresholdsCalculator
>
> Hi Folks,
>
> I agree as well that we should merge the two implementations and provide
> an update on the migration guide.
>
> I looked in a little more detail at the two implementations. If I run
> both algorithms for a large range of numberOfHistogramBins, they produce
> very different results when the number is small, but very similar results
> when the number of bins is large. This is disturbing in itself, so I am
> looking into the implementations to see why this happens.
>
> In terms of the timing, they are both very fast for normal bin sizes. But
> when I push the numberOfHistogramBins up to 1,000,000 and 10,000,000, I
> get some differences:
>
> numberOfHistogramBins = 1,000,000:
> Otsu = 5 sec
> OtsuMultiple = 0.5 sec
>
> numberOfHistogramBins = 10,000,000:
> Otsu = 45.80 sec
> OtsuMultiple = 4.58 sec
>
> Thus, when the numberOfHistogramBins is very large, the difference is
> significant: the OtsuMultiple is about 10 times faster. This is
> encouraging since the OtsuMultiple is the more general implementation.
>
> All of these tests are on the cthead1.png image that was used for the
> ctest.
>
> My plan is to carefully compare the implementations to see how to make
> them report the same results. And then I will merge them so that the Otsu
> is just a shell that inherits from OtsuMultiple.
>
> Thanks,
> Dirk
>
>
> ________________________________________
> From: Matt McCormick [matt.mccormick at kitware.com<mailto:
> matt.mccormick at kitware.com>]
> Sent: Tuesday, July 02, 2013 3:44 PM
> To: Johnson, Hans J
> Cc: Bradley Lowekamp; Padfield, Dirk R (GE Global Research);
> <insight-developers at itk.org<mailto:insight-developers at itk.org>>
> Developers; Richard.Beare at ieee.org<mailto:Richard.Beare at ieee.org>; Gaëtan
> Lehmann
> Subject: Re: [Insight-developers] OtsuThresholdCalculator versus
> OtsuMultipleThresholdsCalculator
>
> I concur with Brad and Hans.
>
> Adding Gaëtan in CC.
>
> Thanks,
> Matt
>
> On Tue, Jul 2, 2013 at 5:08 PM, Johnson, Hans J <hans-johnson at uiowa.edu
> <mailto:hans-johnson at uiowa.edu>>
> wrote:
> > I agree with brad. The two should produce the same results, even tough
> >it
> > may introduce a different numerical result in the
> > OtsuMultipleThresholdCalculator.
> >
> > -----Original Message-----
> > From: Bradley Lowekamp <blowekamp at mail.nih.gov<mailto:
> blowekamp at mail.nih.gov>>
> > Date: Tuesday, July 2, 2013 12:01 PM
> > To: "Padfield, Dirk R (GE Global Research)" <padfield at research.ge.com
> <mailto:padfield at research.ge.com>>
> > Cc: ITK <insight-developers at itk.org<mailto:insight-developers at itk.org>>,
> "Richard.Beare at ieee.org<mailto:Richard.Beare at ieee.org>"
> > <Richard.Beare at ieee.org<mailto:Richard.Beare at ieee.org>>
> > Subject: Re: [Insight-developers] OtsuThresholdCalculator
> > versus OtsuMultipleThresholdsCalculator
> >
> > Dirk,
> >
> > I would vote to have the two produce the same results, and create a
> >little
> > migration guide which notes the change.
> >
> > Regarding, the refactoring, is there any difference in the algorithm
> > complexity of the two? Any measurements of the performance difference
> > between the two?
> >
> > Brad
> >
> > On Jul 2, 2013, at 11:04 AM, "Padfield, Dirk R (GE Global Research)"
> > <padfield at research.ge.com<mailto:padfield at research.ge.com>> wrote:
> >
> >> Hi Richard,
> >>
> >> Thank you for your response and insight. If anything would need to be
> >>changed, I would also lean towards changing the OtsuMultiple because I
> >>think we shouldn't change Otsu since I am sure many more people are using
> >>the Otsu because it is a standard thresholding algorithm. I will do some
> >>comparisons of the two against other implementations to see what I find.
> >>
> >> But the question still remains: is it okay to change the OtsuMultiple to
> >>give the same output as Otsu for one threshold? I am thinking in terms
> >>of those people who use OtsuMultiple whose results will then be slightly
> >>different. Here are the advantages and disadvantages for keeping things
> >>the same:
> >>
> >> Advantages: everyone's code still works as it did before
> >> Disadvantages: the two implementations are inconsistent with each other
> >>even though they are the same algorithm. The overlapping code cannot be
> >>merged (inheritance). And future enhancements will need to be made in
> >>both places.
> >>
> >> My vote is: change OtsuMultiple to be consistent with Otsu.
> >>
> >> What do others think?
> >>
> >> Dirk
> >>
> >>
> >> ________________________________
> >> From: Richard Beare [richard.beare at gmail.com<mailto:
> richard.beare at gmail.com>]
> >> Sent: Monday, July 01, 2013 5:40 PM
> >> To: Bradley Lowekamp
> >> Cc: Padfield, Dirk R (GE Global Research); <insight-developers at itk.org
> <mailto:insight-developers at itk.org>>
> >>Developers
> >> Subject: Re: [Insight-developers] OtsuThresholdCalculator versus
> >>OtsuMultipleThresholdsCalculator
> >>
> >> Hi,
> >> I think the order was - I introduced new filters copied from ImageJ,
> >>then Gaetan started refactoring to use the histogram framework. We both
> >>did some work to make that correspond to old versions. I don't remember
> >>working on the MultipleThreshold version, but the code does look
> >>similar, so perhaps it was done somewhere along the way - will need to
> >>check the logs.
> >>
> >> I'm pretty sure that Otsu was producing the same results that it used to
> >>- I didn't compare to other implementations. Thus, if the original Otsu
> >>was correct then the current one should be too, which would suggest that
> >>the MultipleThresholds version should probably change.
> >>
> >> Not sure when I'll get a chance to look at this in detail.
> >>
> >> I don't have a current email for Gaetan to CC for confirmation.
> >>
> >>
> >> On Mon, Jul 1, 2013 at 11:02 PM, Bradley Lowekamp
> >><blowekamp at mail.nih.gov<mailto:blowekamp at mail.nih.gov><mailto:
> blowekamp at mail.nih.gov<mailto:blowekamp at mail.nih.gov>>> wrote:
> >> Dirk,
> >>
> >> I believe Richard Beare did the refactoring of the thresholding
> >>framework an Insight Journal Article. He will likely know why it is this
> >>way better than anyone else.
> >>
> >> You also didn't say which implementation is correct.
> >>
> >> Brad
> >>
> >>
> >> On Jun 30, 2013, at 10:03 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>>> wrote:
> >>
> >>> Hi ITK Developers,
> >>>
> >>> I was just looking through the OtsuThresholdCalculator and
> >>>OtsuMultipleThresholdsCalculator to see whether I could refactor them so
> >>>that the Otsu inherits from the OtsuMultiple since the latter is a more
> >>>general case of the former. Currently, the code for these two filters
> >>>is totally different resulting in significant code duplication and a
> >>>need to keep both filters in sync.
> >>>
> >>> As a first step, I wrote a CMake test to check that the output of the
> >>>OtsuMultiple with 1 threshold is the same as the output of the Otsu.
> >>>Unfortunately, they are not! The two filters output thresholds that are
> >>>different by 1 histogram bin! This can be a quite extreme difference
> >>>when the numberOfHistogramBins is low, and it leads to different
> >>>thresholds even when the numberOfHistogramBins is reasonably high (say
> >>>256). I tracked it down to this code in the Calculators:
> >>>
> >>> The relevant code from Otsu:
> >>> const double tolerance = 0.00001;
> >>> if ( (varBetween - tolerance) > maxVarBetween )
> >>> {
> >>> maxVarBetween = varBetween;
> >>> maxBinNumber = j;
> >>> }
> >>> }
> >>> this->GetOutput()->Set( static_cast<OutputType>(
> >>>histogram->GetMeasurement( maxBinNumber + 1, 0 ) ) );
> >>>
> >>> The relevant code from MultipleOtsu:
> >>> if ( varBetween > maxVarBetween )
> >>> {
> >>> maxVarBetween = varBetween;
> >>> maxVarThresholdIndexes = thresholdIndexes;
> >>> }
> >>> }
> >>> for ( j = 0; j < m_NumberOfThresholds; j++ )
> >>> {
> >>> m_Output[j] = histogram->GetBinMax(0, maxVarThresholdIndexes[j]);
> >>> }
> >>>
> >>> The difference is that the Otsu adds one to the computed threshold
> >>>whereas the MultipleOtsu does not. This is problematic because users
> >>>would expect them to give the same result.
> >>>
> >>> My question is: how should we proceed? If we change one or the other,
> >>>people's code that use the changed one will give slightly different
> >>>answers. If we don't change them, the two filters will give different
> >>>outputs for the same input, and it will not be possible to refactor them
> >>>to share code.
> >>>
> >>> What are your thoughts?
> >>>
> >>> 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<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.
> > ________________________________
> > _______________________________________________
> > 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.
> ________________________________
>
> _______________________________________________
> 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
>
--
Unpaid intern in BillsBasement at noware dot com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.itk.org/pipermail/insight-developers/attachments/20130709/f33cd4d2/attachment.htm>
More information about the Insight-developers
mailing list