View Issue Details [ Jump to Notes ] [ Print ]
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 
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.
  
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.
Resolution Date
Sprint
Sprint Status
Attached Files

 Relationships
related to 0007528assignedJim Miller Statistics::QuickSelect() huge performace burden 

  Notes
(0012983)
Hans Johnson (developer)
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 (manager)
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 (manager)
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 (manager)
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 (manager)
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 (developer)
2008-11-07 10:37

 Luis has fixed this, and perhaps the bug should be closed.
(0015633)
Hans Johnson (developer)
2009-03-10 20:05

 This problem was solved quite a while ago.

 Issue History
Date Modified Username Field Change
2008-08-11 13:45 Hans Johnson New Issue
2008-08-11 14:04 Hans Johnson Note Added: 0012983
2008-08-20 09:04 Luis Ibanez Note Added: 0013109
2008-08-20 09:06 Luis Ibanez Note Added: 0013110
2008-08-22 19:49 Luis Ibanez Note Added: 0013157
2008-08-22 19:58 Luis Ibanez Note Added: 0013158
2008-08-22 20:00 Luis Ibanez Relationship added related to 0007528
2008-11-07 10:37 Hans Johnson Note Added: 0014058
2009-03-10 20:04 Hans Johnson Status new => assigned
2009-03-10 20:04 Hans Johnson Assigned To => Hans Johnson
2009-03-10 20:05 Hans Johnson Note Added: 0015633
2009-03-10 20:05 Hans Johnson Status assigned => closed
2009-03-10 20:05 Hans Johnson Resolution open => fixed
2009-03-10 20:05 Hans Johnson Fixed in Version => ITK-3-10

Copyright © 2000 - 2018 MantisBT Team