MantisBT - ITK
View Issue Details
IDProjectCategoryView StatusDate SubmittedLast Update
0007481ITKpublic2008-08-11 13:452009-03-10 20:05
ReporterHans Johnson 
Assigned ToHans Johnson 
PriorityurgentSeveritycrashReproducibilityalways
StatusclosedResolutionfixed 
PlatformOSOS Version
Product VersionITK-3-8 
Target VersionFixed in VersionITK-3-10 
Resolution Date
Sprint
Sprint Status
Summary0007481: itkStatisticsAlgorithm changes introduce infinite loop
DescriptionThe changes to the itk::StatisticsAlgorithm introduced in itkStatisticsAlgorithm.txx (v1.20) and itkStatisticsAlgorithm.h (v1.10) on april 27, 2008 are causing an infinite loop to occur in the code.
  
Steps To Reproduce
Additional InformationHow to induce the error:


cd ${INSIGHT_SOURCE}
cvs update -dAP ## to get the new test added to itk
## First check out version that passes the test
cvs update -r 1.19 Code/Numerics/Statistics/itkStatisticsAlgorithm.txx
cvs update -r 1.9 Code/Numerics/Statistics/itkStatisticsAlgorithm.h

make -C ${INSIGHT_BUILD_DIR}
pushd ${INSIGHT_BUILD_DIR}
ctest -R itkScalarImageKmeansImageFilter
echo "This test should pass"
popd

## Now induce the error case that never completes the test
cvs update -r 1.20 Code/Numerics/Statistics/itkStatisticsAlgorithm.txx
cvs update -r 1.10 Code/Numerics/Statistics/itkStatisticsAlgorithm.h

make -C ${INSIGHT_BUILD_DIR}
pushd ${INSIGHT_BUILD_DIR}
ctest -R itkScalarImageKmeansImageFilter
echo "This test never completes"
popd



TagsNo tags attached.
Relationships
related to 0007528assigned Jim Miller Statistics::QuickSelect() huge performace burden 
Attached Files
Issue History
Date ModifiedUsernameFieldChange
2008-08-11 13:45Hans JohnsonNew Issue
2008-08-11 14:04Hans JohnsonNote Added: 0012983
2008-08-20 09:04Luis IbanezNote Added: 0013109
2008-08-20 09:06Luis IbanezNote Added: 0013110
2008-08-22 19:49Luis IbanezNote Added: 0013157
2008-08-22 19:58Luis IbanezNote Added: 0013158
2008-08-22 20:00Luis IbanezRelationship addedrelated to 0007528
2008-11-07 10:37Hans JohnsonNote Added: 0014058
2009-03-10 20:04Hans JohnsonStatusnew => assigned
2009-03-10 20:04Hans JohnsonAssigned To => Hans Johnson
2009-03-10 20:05Hans JohnsonNote Added: 0015633
2009-03-10 20:05Hans JohnsonStatusassigned => closed
2009-03-10 20:05Hans JohnsonResolutionopen => fixed
2009-03-10 20:05Hans JohnsonFixed in Version => ITK-3-10

Notes
(0012983)
Hans Johnson   
2008-08-11 14:04   
Oops:

before building you

cd ${INSIGHT_SOURCE}
## To get the rest of the code in a working form.
cvs update -dAP -D "20080426"

## to get the new test added to itk
cd Testing/Code/Algorithms
cvs update -dAP
## to get the new test datasets
cd Examples/Data
cvs update -dAP
(0013109)
Luis Ibanez   
2008-08-20 09:04   
After profiling the code, it was found in the itkKdTreeGenerator.txx file, that by replacing the QuickSelect function with the NthElement function, there is a speed up of about two orders of magnitude. It seems that the QuickSelect function is performing some unnecessary computations.
(0013110)
Luis Ibanez   
2008-08-20 09:06   
After the change in KdTreeGenerator.txx, the computation time required to run the Generator decreased dramatically (for 70^3 points, it went from 103sec to 1.01sec).

The computation time of the ScalarKMeansImage is still in the 100s. This still requires some profiling...
(0013157)
Luis Ibanez   
2008-08-22 19:49   
The QuickSelect algorithm needed to be replaced with NthElement in the itkWeightedKdTreeGenerator.

There is definitely a performance bug in the QuickSelect algorithm.
(0013158)
Luis Ibanez   
2008-08-22 19:58   
The following change restored the performance of the ScalarKmeansImageFilter.
http://www.itk.org/cgi-bin/viewcvs.cgi/Code/Numerics/Statistics/itkWeightedCentroidKdTreeGenerator.txx?root=Insight&r1=1.9&r2=1.10&sortby=date [^]
(0014058)
Hans Johnson   
2008-11-07 10:37   
Luis has fixed this, and perhaps the bug should be closed.
(0015633)
Hans Johnson   
2009-03-10 20:05   
This problem was solved quite a while ago.