[Insight-users] about TPS and EBS

[Luis Ibanez]

Hi Alex,

The Code for the ThinPlateSpline and
ElasticBodySpline is running much
faster now.

The bottleneck was at the level of
the base class: itkKernelTransform.

It was reorganizing the W matrix each
time a point was transformed.

This reorganization has been moved now
to a "ReorganizeW()" method that is called
only once at the end of ComputeW().

This method produce: (1) a NDxNL Matrix
with the weights to be applied to all the
G Kernel matrices, (2) one NDxND Matrix
and (3) one ND vector with components of
the Affine part of the transformation.

 ND = Dimensions of points
 NL = Dimensions of landmarks

Note that ITK is N-Dimensional !

This KernelTransforms can be applied to
Points in any dimension.


We added the third Spline Kernel described
in Davis' IEEE-TMI paper: the "Volume" spline
where G = r^3 * I. It is in fact quite easy
to add new kernels. Just add a new class
deriving from KernelSpline and rewrite the
G() matrix.


An Important point:
the KernelSpline transform is templated over
the type used for representing the points in
space (typically float or double) This type
is being used now for the transformation matrices
too, which has a fundamental influence in the
results of the inversion of the matrix.

The vnl_svd method is quite sensitive to the
use of float. You can interpret that as :

        "never use float" !     :-)

We will be fixing the intenal matrix type of
the KernelTransform to "double" in the short
term.


If you want to verify how much it changes the
results (and have some fun on the way...),
just change "double" by "float" in line 46 of

Examples/ThinPlateSpline/ThinPlateSplineApplicationBase.cxx

recompile and run the demo.

In order to execute the Transform, click on
the "Map Points" button at the lower right corner
of the GUI.

Points transformed by VTK are displayed in Green
Points transformed by ITK are displayed in Red

You can select the ITK and VTK kernels with the
Choice button in the upper right of the GUI.
Note that the only two equivalent kernels are
VTK's "R" with ITK's ThinPlate.

The other combinations are not supposed to
produce the same results.

Clicking on the menu bar option "Time" will display the
results of computing time for each one of the method.
You can ask for the results at each time by clickin on
the "Report" button or you can run in continuous mode
by clicking on the checkbox "Continuous".


These are the time I got now on Window on debug mode:

  ITK TPS  0.156 seconds
  VTK TPS  0.016 seconds

Under Linux (in debugging mode too) the times are:

  ITK TPS  1.37
  ITK TPS  1.01

(Windows and linux times are not comparable here)


We could probably improve the performance by delegating
computation of the weighted sum of kernels to the
TPS, EBS and VS subclasses.

For example in the TPS and VS the Kernels are diagonal
matrices with const elements, so only three multiplications
are actually required for multiplying the G matrix by a
vector of weights. We perform however nine multiplications
because we use the normal matrix product (six of these
multiplications are always products by zero...in the TPS
and VS cases).




Please let us know if these changes help to improve
the performance of your code.


  Thanks


     Luis



---------------



Alex zhang wrote:
> Dear Mr Luis£º
>      Thank you very much for your work. 
>      I just wonder that why there should be this much diffence between codes in ITK and VTK.
> I have checked the code for TPS and EBS, and I don't think there is special optimization 
> in VTK TPS, it is also follow the matrix calculation step by step similar with the ITK TPS and EBS,only diffence is that the calculation of the ITK is on a 3N+12 times 3N+12 matrix(svd)
> and the VTK TPS is done on three N+4 times N+4 matrices, and I have try svd method in matlab,
> there isn't so much time diffence between the SVD of a 3N+12*3N+12 matrix and a N+4*N+4 
> matrix. I am wondering about this and hope we can find the reason for this.
> 
> regards,
> zhang zhijun
> 
>