[Insight-developers] Rounding Test : Redux

[Tom Vercauteren]

Hi all,

First of all, to make things clear, for the operation we are talking
about (rounding), there is no such thing as a round-to-nearest rule
for half-integers. 0.5 is really as close from 0 as from 1.

The typical rules that might be used for half-integers are:
- round away from zero
- round up
- round down
- round to nearest even

Currently, vnl_math_round is implemented in such a way that it tries
to pick the most efficient rule among these ones depending on the
platform. There has been quite some discussion about that on the vnl
mailing list but I have to admit that I kind of dropped the ball on
that one:
http://sourceforge.net/mailarchive/forum.php?thread_name=28392e8b0901120918l45e9e81bq5395cb6630ddacc1%40mail.gmail.com&forum_name=vxl-maintainers

All these rules can be implemented efficiently (approximatively 3x
times faster than lround on my x86 machine) provided that the
following assumptions are made:
- The rounding mode of the FPU is not changed from the default one
- For some rules the efficient implementation only works for  numbers
whose absolute value is less than INTMAX/2

Without these assumptions, there is no possible efficient (and
correct) implementation that I know of.

If we have to pick one of those rules that should be used on all
platforms, I would vote for "round up" with an efficient
implementation so that all pixels (even the 0 one) have exactly the
"same size*" as mentioned by Simon.

This could be done by a new function to vnl_math_rnd_halfintup or within ITK.

I will definitely appreciate any reasonable plan on how to deal with
this issue. I am willing to write a patch for vnl but need some
feedback on what the patch should include.

Regards,
Tom

* Note that the notion of size is not well defined, the size of the
interval ]0.5; 1.5[ is indeed the same as the one of ]0.5; 1.5] or
[0.5; 1.5[


On Sun, Mar 8, 2009 at 17:38, Simon Warfield
<simon.warfield at childrens.harvard.edu> wrote:
>>
>> Folks,
>>
>> Recall the long discussion regarding rounding. Although we never came
>> to consensus, we do have a test that is failing on VS platforms.
>>
>> itkVNLRoundProfileTest1.cxx fails on these platforms because
>> vnl_math_rnd does round-to-even while other platforms do
>> round-to-nearest. Regardless of what we decide, having a constantly
>> failing test is nbot a good practice. Since we know vnl_math_rnd is
>> not platform-independent, I propose removing the pass/fail portion of
>> this test. We should keep the test since it still provides useful
>> profiling info.
>>
>> BTW: on gcc systems, rint() also does round-to-even by default. vxl
>> uses lround() which does round-to-nearest.
>>
>> Comments?
>>
>> Bill
>
> Hi Bill,
>
>  I am interested in resolving the aspect of rounding related to the
> definition of the physical coordinate system.
>
> One way ITK uses rounding is to identify the extent of a voxel by rounding a
> continuous index.
> This use of rounding defines the extent of a voxel. For example, the point
> that is the origin is in the middle of the voxel at index (0,0,0),
> and the extent of that voxel is defined by transforming the physical
> coordinates of the voxel into a continuous index, and then rounding the
> continuous index to identify the integer index (e.g. a continuous index of
> (-0.4, 0.3, 0.2) rounds to (0,0,0).
>
>  If round to even is used for this task, then every second voxel, despite
> having the same physical size, is treated as slightly thinner than its
> neighbors. Using round to nearest ensures that all voxels have the same
> size.  Therefore, I favour round to nearest for this task.
>
> In order for all platforms to have the same definition of the physical
> extent of each voxel, the rounding behaviour needs to be the same
> on each platform.
>
> The transformation of physical points into indexes can occur frequently, and
> so should be efficient. I think the efficiency is the second issue to
> consider, after having first defined the nature of the rounding we need in
> physical coordinate to voxel index conversion.
> That said, lround() is very efficient on x86/x86_64 platforms, it can be
> even faster than truncation (see discussion at
> http://www.itk.org/Bug/view.php?id=6558 )
>
> If we can't decide on a general purpose implementation of vnl_math_round()
> then we could decide to replace it as the rounding function used in the
> physical space transformations, and use an efficient cross-platform
> round-to-nearest-integer for that task.
>
> --
> Simon
>
> _______________________________________________
> 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
>