MantisBT - ITK
View Issue Details
IDProjectCategoryView StatusDate SubmittedLast Update
0009383ITKpublic2009-08-06 23:362010-11-07 02:08
ReporterHans Johnson 
Assigned ToLuis Ibanez 
PriorityhighSeveritymajorReproducibilityalways
StatusclosedResolutionfixed 
PlatformOSOS Version
Product VersionITK-3-14 
Target VersionFixed in Version 
Resolution Date
Sprint
Sprint Statusbacklog
Summary0009383: Floating point overflow in incrementing histogram bin counting
Description
Histograms use floating point values to hold counts for each bin results in overflow errors.

A potential fix is to increase the size of the storage container:


[hjohnson@neuron Insight]$ itkcvs diff Code/Numerics/Statistics/itkSparseFrequencyContainer.h
Index: Code/Numerics/Statistics/itkSparseFrequencyContainer.h
===================================================================
RCS file: /cvsroot/Insight/Insight/Code/Numerics/Statistics/itkSparseFrequencyContainer.h,v
retrieving revision 1.12
diff -r1.12 itkSparseFrequencyContainer.h
53c53
< typedef float FrequencyType;
---
> typedef double FrequencyType;
Steps To Reproduce
Additional InformationA test was written to identify this bug:

[hjohnson@neuron Statistics]$ itkcvs -q commit -m"BUG: Identified bug that causes Otsu thresholds to fail on images with very large number of background voxels that all fit in the first bin of the histogram." itkScalarImageToHistogramGeneratorTest.cxx
Committer: Hans Johnson <hans-johnson@uiowa.edu>
/cvsroot/Insight/Insight/Testing/Code/Numerics/Statistics/itkScalarImageToHistogramGeneratorTest.cxx,v <-- itkScalarImageToHistogramGeneratorTest.cxx
new revision: 1.3; previous revision: 1.2
TagsNo tags attached.
Relationships
Attached Files
Issue History
Date ModifiedUsernameFieldChange
2009-08-06 23:36Hans JohnsonNew Issue
2009-08-06 23:40Hans JohnsonNote Added: 0017079
2009-08-07 08:54Bradley LowekampNote Added: 0017081
2009-08-08 14:40Luis IbanezNote Added: 0017087
2009-08-11 18:44Hans JohnsonNote Added: 0017098
2009-12-11 08:06Hans JohnsonStatusnew => assigned
2009-12-11 08:06Hans JohnsonAssigned To => Hans Johnson
2009-12-11 08:09Hans JohnsonNote Added: 0018813
2009-12-16 08:23Hans JohnsonAssigned ToHans Johnson => Luis Ibanez
2010-08-05 21:05Hans JohnsonNote Added: 0021677
2010-11-07 02:08Luis IbanezSprint Status => backlog
2010-11-07 02:08Luis IbanezNote Added: 0022998
2010-11-07 02:08Luis IbanezStatusassigned => closed
2010-11-07 02:08Luis IbanezResolutionopen => fixed

Notes
(0017079)
Hans Johnson   
2009-08-06 23:40   
The itkSparseFreqeuncyContainer, and the itkDenseFrequenceyContainer are using floating point values for their FrequencyType.

In many common images of size 512x512x384 have backgrounds of all zeros with a count greater than the maximum that can be incremented to using 32 bit floating point numbers.
(0017081)
Bradley Lowekamp   
2009-08-07 08:54   
From: blowekamp@mail.nih.gov
    Subject: Re: [Insight-developers] Limits of Histograms' FrequencyType
    Date: October 22, 2008 8:12:05 AM CDT
    To: insight-developers@itk.org

The problem with creating a a double DenseFrequencyContainer is that the Histogram class with then have conflicting types for it's FrequencyType, one from the container the other from the Superclass, SampleType. This created problems with at least one virtual function.


Another possible solution would be just to improve the algorithm in ListSampleToHistogramGenerator so that if there is over 2^24 samples then it would chunk it up and use an iterative total histogram + accumulator histogram. This would only cause a small loss of precision but would give reasonable results. Perhaps this would also give an opportunity to parallelize this part too.

On Oct 21, 2008, at 2:50 PM, Bradley Lowekamp wrote:

Hello,

I am causing trouble with my large data sets again. I am seeing this number a lot in my histograms: 1.67772e+07 which is 2^24 and the limit of mantissa for 32-bit floats. Unfortunately, the frequency container types don't take this as a template parameter. It seems silly to create another container just for this purpose.

Brad

-----------------

I made simular changed to the DenseFrequency container before. If I recall correctly I also had to change itkSample with:

 typedef float FrequencyType;


because the frequency type was defined differently in the itkSample and itkHistogram
(0017087)
Luis Ibanez   
2009-08-08 14:40   
Added verification for saturation of the Frequency counters, both for the frequency of the instance and for the total frequency:

http://public.kitware.com/cgi-bin/viewcvs.cgi/Code/Numerics/Statistics/itkSparseFrequencyContainer.cxx?root=Insight&r1=1.5&r2=1.6&sortby=date [^]

http://public.kitware.com/cgi-bin/viewcvs.cgi/Code/Numerics/Statistics/itkDenseFrequencyContainer.cxx?root=Insight&r1=1.4&r2=1.5&sortby=date [^]

This doesn't fix the bug, but at least provides a reasonable way of reporting the incorrect behavior of the frequency container.
(0017098)
Hans Johnson   
2009-08-11 18:44   
Luis,

I don't think your fix is going to work.

Where FrequencyType=float

NumericTraits< FrequencyType >::max() is much greater than

http://en.wikipedia.org/wiki/Floating_point [^]

Any integer with absolute value less than or equal to 2^24 can be exactly represented in the single precision format


2^24=16777216

Code that will fail after 16777216

#include <iostream>

int main (int argc, char *argv[])
{
  size_t myint=0;
  float myfloat=0;
  do
  {
     myint+=1;
     myfloat+=1;
  }
  while(myint == static_cast<size_t>(myfloat) );
  std::cout << myint << " does not equal " << static_cast<size_t>(myfloat) << std::endl;
  return 0;
}

16777217 does not equal 16777216


Where NumericTraits< FrequencyType >::max() = 3.403 x 10^38
(0018813)
Hans Johnson   
2009-12-11 08:09   
Luis,

This did not have anyone assigned to it. Since you had made comments and some initial attempts of looking at this, I've assigned it to you so that it has a proper home.

Hans
(0021677)
Hans Johnson   
2010-08-05 21:05   
I don't think this bug is relevant in the new statistics framework.
(0022998)
Luis Ibanez   
2010-11-07 02:08   
not relevant for the new statistics framework in ITKv4