[Insight-developers] 2-fold speed-up of itkBSplineDerivativeKernelFunction.h

[Wenjia Bai]

Hi Luis,

Sorry for the late reply.

I have just written a program to test the improved 
itkBSplineDerivativeKernelFunction class, which is named 
itkBSplineDerivativeKernelFunction2. The testing program and the 
itkBSplineDerivativeKernelFunction2 class are attached.

Experimental results show that,

(1) The difference between the derivative evaluations of the original 
class and new class is negligible. Therefore, the new class is validated.

B-Spline Order        Average Evaluation Difference  
1                               0
2                               1.79E-017
3                               2.08E-017

(2) The new class improves the speed by 3-4 times.

Computation Time per Million Evaluations (sec)   
B-Spline Order        Original        New
1                               0.1215          0.0393
2                               0.1210          0.0340
3                               0.1925          0.0406

Best regards
Wenjia

Luis Ibanez wrote:
> Hi Wenjia,
>
> This sounds like a great idea.
>
> Could you please post this as a patch ?
> (just send it to the list attached to your email).
>
> Also,
> Have you ran Experimental builds with this change ?
>
> Did you find all tests passing ?
>
>
>   Please let us know,
>
>
>      Luis
>
>
>
> -------------------
> wenjia wrote:
>> Dear Developers,
>>
>> Thank you for your effort in providing ITK, such an excellent library.
>>
>> I have a suggestion about 2-fold speeding-up of 
>> itkBSplineDerivativeKernelFunction.h, which is used to calculate the 
>> derivative of a B-spline function. It uses the following equation for 
>> computation, calling itkBSplineKernelFunction twice.
>>
>>   /** Evaluate the function. */
>>   inline double Evaluate( const double & u ) const
>>     {
>>     return ( m_KernelFunction->Evaluate( u + 0.5 ) -       
>> m_KernelFunction->Evaluate( u - 0.5 ) );
>>     }
>>
>> The code is very clear for reading. However, 
>> m_KernelFunction->Evaluate( u + 0.5) and m_KernelFunction->Evaluate( 
>> u - 0.5 ) ) waste time in computing similar equations twice. 
>> Therefore, expanding the above equation, as follows, can give a 
>> two-fold speed up.
>>
>>   /** Zeroth order spline. */
>>   inline double Evaluate (const Dispatch<0>&, const double & u) const
>>     {
>>       return 0;
>>     }
>>
>>   /** First order spline */
>>   inline double Evaluate ( const Dispatch<1>&, const double& u) const
>>     {
>>       if( u == -1 )
>>       {
>>         return 0.5;
>>     }
>>       else if( (u > -1) && (u < 0) )
>>       {
>>         return 1;
>>     }
>>       else if( u == 0 )
>>       {
>>         return 0;
>>     }
>>       else if( (u > 0) && (u < 1) )
>>       {
>>         return -1;
>>     }
>>       else if( u == 1 )
>>       {
>>         return -0.5;
>>     }
>>       else
>>       {
>>         return 0;
>>     }
>>     }
>>
>>   /** Second order spline. */
>>   inline double Evaluate ( const Dispatch<2>&, const double& u) const
>>     {
>>       if( (u > -0.5) && (u < 0.5) )
>>       {
>>         return ( -2 * u );
>>     }
>>       else if( (u >= 0.5) && (u < 1.5) )
>>       {
>>         return ( -1.5 + u );
>>     }
>>       else if( (u > -1.5) && (u <= -0.5))
>>       {
>>         return ( 1.5 + u );
>>     }
>>       else
>>       {
>>         return 0;
>>     }
>>     }
>>
>>   /**  Third order spline. */
>>   inline double Evaluate ( const Dispatch<3>&, const double& u) const
>>     {
>>       if( (u >= 0) && (u < 1) )
>>       {
>>         return ( -2 * u + 1.5 * u * u );
>>     }
>>       else if( (u > -1 ) && (u < 0) )
>>       {
>>         return ( -2 * u - 1.5 * u * u );
>>     }
>>       else if( (u >= 1) && (u < 2) )
>>       {
>>         return ( -2 + 2 * u - 0.5 * u * u);
>>     }
>>       else if( (u > -2) && (u <= -1) )
>>       {
>>         return ( 2 + 2 * u + 0.5 * u * u);
>>     }
>>       else
>>       {
>>         return 0;
>>     }
>>     }
>>
>>   /** Unimplemented spline order */
>>   inline double Evaluate ( const DispatchBase&, const double& ) const
>>     {
>>     itkExceptionMacro("Evaluate not implemented for spline order " << 
>> SplineOrder);
>>     return 0.0; // This is to avoid compiler warning about missing 
>>                 // return statement.  It should never be evaluated.
>>     }
>>
>> Considering that itkBSplineDerivativeKernelFunction is usually called 
>> inside several levels of loops for time-consuming numerical 
>> compuation, speed is more important than brievity of the code. I 
>> think expanding the formula is a good choice.
>>
>> Best regards,
>> Wenjia Bai
>> _______________________________________________
>> Powered by www.kitware.com
>>
>> Visit other Kitware open-source projects at 
>> http://www.kitware.com/opensource/opensource.html
>>
>> Please keep messages on-topic and check the ITK FAQ at: 
>> http://www.itk.org/Wiki/ITK_FAQ
>>
>> Follow this link to subscribe/unsubscribe:
>> http://www.itk.org/mailman/listinfo/insight-developers
>>

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: CMakeLists.txt
URL: <http://www.itk.org/mailman/private/insight-developers/attachments/20090815/4cc5a53d/attachment.txt>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: comp_bspline_derivative_kernel.cxx
Type: text/x-c++src
Size: 2180 bytes
Desc: not available
URL: <http://www.itk.org/mailman/private/insight-developers/attachments/20090815/4cc5a53d/attachment.cxx>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: itkBSplineDerivativeKernelFunction2.h
Type: text/x-chdr
Size: 4720 bytes
Desc: not available
URL: <http://www.itk.org/mailman/private/insight-developers/attachments/20090815/4cc5a53d/attachment.h>