ITK Registration Optimization

Goals

There are two components to this research

1. Identify registration algorithms that are suitable for non-rigid registration problems that are indemic to NA-MIC
2. Develop implementations of those algorithms that take advantage of multi-core and multi-processor hardware.

Algorithmic Requirements and Use Cases

• Requirements
  1. relatively robust, with few parameters to tweak
  2. runs on grey scale images
  3. has already been published
  4. relatively fast (ideally speaking a few minutes for volume to volume).
  5. not patented
  6. can be implemented in ITK and parallelized.

• Use-cases
  1. Intersubject mapping
     • Example data set (Kilian)
  2. fMRI to hi-res brain morphology mapping
     • Example data set (Steve Pieper)
  3. DTI: components of the diffusion tensor
     • Example data (Sylvain)

Hardware Platform Requirements and Use Cases

• Requirements
  1. Shared memory
  2. Single and multi-core machines
  3. Single and multi-processor machines
  4. AMD and Intel - Windows, Linux, and SunOS

• Use-cases
  1. Intel Core2Duo
  2. Intel quad-core Xeon processors (?)
  3. 6 CPU Sun, Solaris 8 (SPL: vision)
  4. 12 CPU Sun, Solaris 8 (SPL: forest and ocean)
  5. 16 core Opteron (SPL: john, ringo, paul, george)
  6. 16 core, Sun Fire, AMDOpteron (UNC: Styner)

Data

• NA-MIC MIDAS collection for this project

Workplan

Establish testing and reporting infrastructure

1. Identify timing tools
   1. Cross platform and multi-threaded
   2. Timing and profiling
   • Status
     1. Instrumenting modular tests
        • Extending itk's cross-platform high precision timer
        • Adding thread affinity to ensure valid timings
        • Adding method for increasing process priority
        • ViewCVS
     2. Profiling complete registration solutions for use cases
        • Using CacheGrind on single and multi-core linux systems
        • Using LTProf on windows
2. Develop performance dashboard for collecting results
   1. Each test will report time and accuracy to a central server
   2. The performance of a test, over time, for a given platform can be viewed on one page
   3. The performance of a set of tests, at one point in time, for all platforms can be viewed on one page
   • Status
     1. BatchMake database communication code being isolated
     2. Performance dashboard web pages being designed
     3. BatchMake Dashboard

Develop tests

1. Develop modular tests
   • Status
     1. Developed itkCheckerboardImageSource so no IO required
     2. Developed all tests listed in the "Modular Tests" section below
     3. Developing second generation tests that compare optimized performance with standard performance in a single executable
2. Develop C-style tests
   1. Tests should represent the non-ITK way of doing image analysis
      • Use standard C/C++ arrays and pointers to access blocks of memory as images
3. Develop complete registration solutions for use cases
   • Status
     1. Centralized data and provide easy access
     2. Identified relevant registration algorithms
        • rigid, affine, bspline, multi-level bspline, and Demons'
        • normalized mutual information, mean squared difference, and cross correlation
     3. Developing traditional ITK-style implementations

Compute performance on target platforms

• Completing the development of the reporting dashboard, the standard C tests, and the full registration applications (see above).
• Developing optimized versions of select methods in parallel with deploying the testing suite (see below).

ITK Optimization

• Target bottlenecks
  • Multi-thread metric calculation
    • Initial target is MattesMutualInformationImageToImageMetric
  • Optimize code
    • Sacrifice some memory and algorithm initialization speed to gain algorithm operation speed increases
    • Call multi-threaded functions when possible

• Integrate metrics with transforms and interpolators for tailored performance

MattesMutualInformationImageToImageMetric

Optimizations Employed

• GetValue
  • Added multi-threading to GetValue function
    • Partitions the samples - thereby distributes the computation of the transforms and interpolations across threads
    • Original runtime is O(C1+C2*M) given M samples from the fixed image and new runtime is O(C1+(C2*M)/(C3*N)) given N cores. The ratio of C2/C3 varies by the type of transform used. When a BSplineTransform is used, the ratio C2/C3 approaches 1.0.
    • Added the pre-computation of the FixedImageMarginalPDF for the sample to reduce the need for the thread mutex lock
      • Required the concept of an AdjustedFixedImageMarginalPDF that is updated when a fixed image voxel does not map into the moving image and thereby isn't valid for the current computations. By only updating when samples are missed, mutex lock to update a cross-thread data structure is needed less often.
    • Each thread now has its own copy of the joinPDF. After threads complete, jointPDFs from each thread are summed. This eliminates mutex from the main loop over samples.
    • SUMMARY: Speedup on a dual-core system is about 30% (reduction in computation time) when using linear transform and linear interpolation and about 45% when using bspline transform and bspline interpolation.
  • Algorithm optimization (aside from adding multi-threading)
    • None at this level. Will be done for transforms and interpolators.
• GetDerivative
  • Following the same convention as used with GetValue

Profile of standard ITK: time in functions

Time in self	Time in subfuncs	Function
0.00	86.64	__tmainCRTStartup"
0.00	48.47	main"
0.00	37.98	itk::MattesMutualInformationImageToImageMetric<itk::Image<float,3>,itk::Image<float,3> >::GetDerivative"
8.49	20.99	itk::MattesMutualInformationImageToImageMetric<itk::Image<float,3>,itk::Image<float,3> >::GetValueAndDerivative"
0.57	19.27	itk::CentralDifferenceImageFunction<itk::Image<float,3>,double>::Evaluate"
13.40	13.55	itk::CentralDifferenceImageFunction<itk::Image<float,3>,double>::EvaluateAtIndex"
11.70	11.83	itk::BSplineKernelFunction<3>::Evaluate [1]"
9.06	9.16	itk::BSplineKernelFunction<2>::Evaluate [1]"
3.21	8.40	itk::MattesMutualInformationImageToImageMetric<itk::Image<float,3>,itk::Image<float,3> >::GetValue"
8.11	8.21	floor ?"
0.00	7.25	itk::CheckerBoardImageSource<itk::Image<float,3> >::GenerateData"
0.00	4.20	itk::ImageSource<itk::Image<float,3> >::ThreaderCallback"
3.77	3.82	itk::NearestNeighborInterpolateImageFunction<itk::Image<float,3>,double>::EvaluateAtContinuousIndex"
3.21	3.24	itk::StatisticsImageFilter<itk::Image<float,3> >::ThreadedGenerateData"
3.02	3.05	itk::ImageFunction<itk::Image<float,3>,double,double>::IsInsideBuffer"
2.83	2.86	itk::BSplineDerivativeKernelFunction<3>::Evaluate"
2.26	2.29	itk::InterpolateImageFunction<itk::Image<float,3>,double>::Evaluate"
0.00	2.10	endthreadex ?"
2.08	2.10	itk::MattesMutualInformationImageToImageMetric<itk::Image<float,3>,itk::Image<float,3> >::TransformPoint"
2.08	2.10	thunk@403355 ?"
1.89	1.91	_ftol2_pentium4"
1.70	1.72	itk::MattesMutualInformationImageToImageMetric<itk::Image<float,3>,itk::Image<float,3> >::ComputePDFDerivatives"
1.70	1.72	thunk@402f54 ?"
1.51	1.53	itk::BSplineKernelFunction<2>::Evaluate"
1.51	1.53	itk::ImageBase<3>::GetSpacing"
1.13	1.53	itk::ImageFunction<itk::Image<float,3>,double,double>::ConvertContinuousIndexToNearestIndex"
0.94	1.34	itk::CheckerBoardSpatialFunction<double,3,itk::Point<double,3> >::Evaluate"
1.13	1.15	itk::ImageFunction<itk::Image<float,3>,double,double>::IsInsideBuffer [1]"
0.94	0.95	itk::BSplineKernelFunction<3>::Evaluate"
0.75	0.76	itk::ImageBase<3>::GetBufferedRegion"
0.75	0.76	itk::Point<double,3>::operator+"
0.75	0.76	thunk@4036d4 ?"
0.75	0.76	thunk@403cec ?"
0.19	0.57	itk::ImageFunction<itk::Image<float,3>,itk::CovariantVector<double,3>,double>::ConvertContinuousIndexToNearestIndex"
0.57	0.57	itk::MattesMutualInformationImageToImageMetric<itk::Image<float,3>,itk::Image<float,3> >::ComputeImageDerivatives"
0.57	0.57	itk::Point<double,3>::operator="
0.57	0.57	itk::ShiftScaleImageFilter<itk::Image<float,3>,itk::Image<float,3> >::ThreadedGenerateData"
0.57	0.57	itk::TranslationTransform<double,3>::TransformPoint"

Profile of standard ITK: time in files

Time in self	Time in subfuncs	Files
16.42	72.33	itkmattesmutualinformationimagetoimagemetric.txx"
0.00	48.47	mattesmutualinformationimagetoimagemetrictest.cxx"
23.21	23.47	itkbsplinekernelfunction.h"
0.57	19.27	itkcentraldifferenceimagefunction.h"
13.40	13.55	itkcentraldifferenceimagefunction.txx"
0.00	7.25	itkcheckerboardimagesource.txx"
5.66	6.49	itkimagefunction.h"
0.00	4.20	itkimagesource.txx"
3.77	3.82	itknearestneighborinterpolateimagefunction.h"
3.21	3.24	itkstatisticsimagefilter.txx"
2.83	2.86	itkbsplinederivativekernelfunction.h"
2.83	2.86	itkimagebase.h"
2.26	2.29	itkinterpolateimagefunction.h"
0.94	1.34	itkcheckerboardspatialfunction.txx"
1.32	1.34	itkpoint.txx"
0.75	0.76	itktranslationtransform.txx"
0.57	0.57	itkshiftscaleimagefilter.txx"
0.38	0.38	vnl_matrix.txx"
0.00	0.19	itkbsplinedeformabletransform.txx"
0.19	0.19	itkfixedarray.txx"
0.19	0.19	itkimageregionconstiterator.txx"
0.19	0.19	itkobject.cxx"
0.19	0.19	vnl_vector.txx"
0.19	0.19	vector"
0.19	0.19	secchk.c"

Modular tests

All tests send two values to performance dashboards

• the time required
• an measure of the error (0 = no error; 1 = 100% error)

Tests being developed and their parameter spaces

1. NearestNeighborInterpTest <numThreads> <dimSize> <factor> [<outputImage>]
2. LinearInterpTest <numThreads> <dimSize> <factor> [<outputImage>]
3. BSplineInterpTest <numThreads> <dimSize> <factor> <bSplineOrder> [<outputImage>]
4. SincInterpTest <numThreads> <dimSize> <factor> [<outputImage>]
   • Uses the Welch window function
5. BSplineTransformLinearInterpTest <numThreads> <dimSize> <numNodesPerDim> <bSplineOrder> [<outputImage>]
   • 3 nodes are also added outside of the image for interpolation
6. MeanSquaresImageToImageMetricTest <numThreads> <dimSize> <iterations>
7. CorrelationCoefficientHistogramMetricTest <numThreads> <dimSize> <iterations>
8. NormalizedCorreltationImageToImageMetricTest <numThreads> <dimSize> <iterations>
9. MattesMutualInformationImageToImageMetricTest <numThreads> <dimSize> <numSamples> <iterations>
   • MattesMutualInformationMetric defaults to BSpline interpolator - this test overrides to use nearest neighbor interpolation
10. MutualInformationImageToImageMetricTest <numThreads> <dimSize> <numSamples> <iterations>
11. NormalizedMutualInformationHistrogramMetricTest <numThreads> <dimSize> <iterations>

SECOND GENERATION TEST

• Computes runtime for GetValue, GetDerivative, and GetValueAndDerivative for standard ITK implementation and for the optimized version being developed. Also computes difference (if any) between their answers and reports as an error measure

1. OptMattesMutualInformationImageToImageMetricTest

Events

• April 6, 2007: TCon

Related Pages

• Non Rigid Registration
• Slicer3:Performance_Analysis
• User:Barre/ITK Registration Optimization

Performance Measurement

• LTProf - simple profilter for Windows - Shareware
• Intel's VTune for Linux ($)
• TAU
• Threadmon: Thread usage/blockage
• TotalView ($)
• PerfSuite (POSIX Threads)
• GProf work-around for multi-threaded apps
• References on multi-threaded profiling and code optimization
  • General C++ performance optimization
  • Multi-threaded performance measurement (pdf document)
  • Wikipedia - General performance analysis