[Insight-developers] vnl updates : Rounding Test : Performance and Correctness

[Tom Vercauteren]

Hi,

>   Have the issue of SSE2 been resolved ?

Yes (as far as rounding is concerned) there are now two different
flags. It is thus possible to activated sse2 for rounding but not for
the rest of vnl which apparently is still buggy.


>    An improvement of 10% in registration time sound modest
>    at the price of having to deal with non-portable code.
>
>    There are many other places in an image registration
>    problem where we could squeeze 10% out. From number of
>    samples, to number of iterations, to step lengths (or
>    its equivalent) in the optimizer...

Well this 10% is without changes to the algorithm. In this context,
the border effect induced by how half-integers are rounded is in my
experience not noticable.

IMHO, a 10% gain on a real complete algorithm by only one
micro-optimization of less than 200 lines is a very good result...

Note that other people might have experienced larger gains since
optimized floor has been implemented in
itk::BSplineInterpolationWeightFunction and itk::BilateralImageFilter.
Unfortunately these implementations are buggy and non-testable. See
e.g.:
  http://www.itk.org/Bug/view.php?id=2078
  http://www.itk.org/Bug/view.php?id=5692


>    In the context of medical imaging, the capability of
>    getting the same answer on every machine is a lot more
>    important than saving 10% on the execution of a registration.

I can understand that. It might thus be worth changing the
implementation of vnl_math_rnd to perform round away from zero for
half-integers. This can be done with a fast implementation.


>     We have numbers today from the ITK dashboard
> http://www.cdash.org/CDash/testSummary.php?project=2&name=itkVNLRoundProfileTest1&date=2008-12-31

Great! The failing tests are the one that use the optimized version.
The numbers are consistent with mine, an times 3 improvement.


>     Which also illustrate the platform dependency
>     that you pointed out.
>    This is a problem.
>    We shouldn't have this platform dependency.

This pushes towards an implementation with round away from zero for
half-integers. Would the limitations I mentioned ( valid range:
INT_MIN/2 to INT_MAX/2 ) be a no-go?


>     We should deal not only with 'round' but also with 'ceil'
>     and 'floor'.

Yes my initial goal was actually to fix ITK bugs 2078 and 5692, which
required a floor function. I got trapped by thinking it would be an
easy task :)


>     but for the purpose of mapping physical coordinates to
>     image grid IJK numbers, the fraction of point that will
>     fall directly on .5 locations will already be very small.
>     I found unlikely that this small set of points may afect
>     the outcome of a registration.

That's exactly why I didn't really focus on half-integers!


>      We could still provide several implementations in ITK,
>      but each one properly named.
>
>      the rounding strategy shouldn't be hidden in the details
>      of the implementation, and the compiler options of the day.
>      It should be clearly marked in the name of the rounding
>      function.
>
>      We should have something very explicit, such as:
>
>              itk::Math::Round()
>              itk::Math::RoundNonBiased()
>
>       In this way, when writing ITK code we can select the
>       rounding strategy that is appropriate for the context.

Presented that way, how could I possibly disagree?


>        I agree that VNL is in principle the right place
>        to put these methods. However, given the different
>        domain emphasis of ITK and VNL, the requirements
>        for these methods is somehow different.
>
>        We have been bitten in the past by the rounding
>        issues in VNL, and it is not worth the trouble.
>
>        Note that we already have an ITK-variant of the
>        vnl_math_round method in the itkIndex.h file, in
>        lines 263-290:
> http://www.itk.org/cgi-bin/viewcvs.cgi/Code/Common/itkIndex.h?root=Insight&r1=1.56&r2=1.57
>
>        That we had to add in order to get around the
>        platform-dependent issues of VNL.

I never realized that this piece of code existed... It explains why
the NN interpolation tests are passing in ITK, interesting. This is
the kind of scenario that I think we should avoid. Having different
implementations of the same function makes it too difficult for me to
understand.

Happy new year!
Tom