[Insight-users] Speed optimizations in mutual information registration

[Hannu Helminen]

It is great to hear that speed optimizations are among your priorities as well.

I also did some testing with using FixedArray in the internal calculations 
of MutualInformationImageToImageMetric class and got very comparable 
results (about 7-fold speed increase). Since these changes are very well 
localized, I can post the diffs here in case someone is interested in 
attempting to reproduce the results.

However this idea requires templatizing MutualInformationImageToImageMetric 
over the size of the transform parameter space. So it is certainly not in 
the direction of reducing templates!

I agree that too many templates, especially when combined with deep 
inheritance hierarchies, may lead to convoluted code. However, I do not 
fully agree with the idea that use of templates would automatically lead to 
larger library size (in terms of object code). It is a question of how many 
times the templates are instantiated.

Hannu


At 12:57 2002-05-22 -0400, you wrote:
>Hi Hannu-
>
>Your feedback is invaluable, thank you. We are certainly interested in 
>performance. In the coming year we will be addressing issues such as 
>these. Any other feedback like this is greatly encouraged.
>
>One option that you suggest is to add template parameters. We have been on 
>a mission to remove many template parameters because of their effects on 
>library size and wrapping the code with the CABLE system. I'd like to 
>steer away from this solution.
>
>Will
>
>At 01:08 PM 5/22/2002 +0300, Hannu Helminen wrote:
>
>>Hi!
>>
>>I did some profiling to the mutual information multi-resolution matching 
>>routines. It seems that a considerable amount of the total optimization 
>>time is spent in the dynamic allocation of vectors. Since the vector type 
>>itk::Array has variable size, it has to do all memory allocations from 
>>the heap. Unfortunately heap allocations and deallocations tend to be 
>>quite expensive in terms of speed.
>>
>>I then did an quick and dirty hack to replace the use of itk::Array with 
>>itk::FixedArray. This resulted in quite large speedup: the total 
>>registration time (which includes the read & write routines etc.) was cut 
>>in half. I also calculated the time spent in the core optimization 
>>routine m_Optimizer->StartOptimization() by cumulating the run times in 
>>each round:
>>
>>Time before optimization: 270 seconds
>>Time after optimization: 38 seconds
>>
>>My test setup: 2 x Xeon 1,7 MHz, Windows 2000, Visual Studio 6.0, 
>>RelWithDebInfo configuration, CT image 512x512x76, MR image 256x256x82, 
>>latest CVS version of ITK, 5 levels of multiresolution with 2500 
>>iterations per level.
>>
>>Now my question is, is there any interest in the ITK developers or ITK 
>>community in these speed-ups? If there is, I may use part of my work time 
>>in this project, if needed.
>>
>>
>>Here are some of my thoughts about speed-up:
>>1) Changing the type of the parameter and derivative of 
>>MIImageToImageMetric to itk::FixedArray. This is what I did in my quick 
>>hack. Unfortunately this change is not small: currently all the 
>>optimization routines in the Numeric subdirectory are hard-coded to use 
>>itk::Array as the type of parameter and derivative.
>>
>>However, I have the feeling that templatizing the optimization routines 
>>over the vector types would be in the spirit of ITK. It would make them 
>>more generic in the spirit of STL's algorithms.
>>
>>2) A smaller change would be to use a fixed array inside 
>>itk::MutualInformationImageToImageMetric in all the calculations. I have 
>>not benchmarked how this would affect the run times.
>>
>>3) Yet another possibility would be to use specialized fixed size 
>>allocator in itk::Array, such as that in the Loki library [1]. Again, I 
>>do not have any data about the speed-ups attainable by this method.
>>
>>Any thoughts?
>>
>>Hannu Helminen
>>Varian Medical Systems Finland Oy
>>
>>[1] <http://sourceforge.net/projects/loki-lib/>
>>
>>
>>_______________________________________________
>>Insight-users mailing list
>>Insight-users@public.kitware.com
>>http://public.kitware.com/mailman/listinfo/insight-users
>