[Insight-developers] Rounding Test : Redux

Tue Mar 10 07:29:56 EDT 2009

Hi,

I have submitted a patch to vnl to get a cross-platform consistent
rounding function that rounds half-integer upward. It is called
vnl_math_rnd_halfintup:
http://sourceforge.net/mailarchive/forum.php?thread_name=28392e8b0903100414i454c29e8p137f11d8a606a7fe%40mail.gmail.com&forum_name=vxl-maintainers

In this patch, vnl_math_rnd remains a less well defined rounding
function that can round half-integers either upward or downward. The
most efficient rule is chosen according to the platform.

Let's see how it goes.

Tom

On Sun, Mar 8, 2009 at 22:08, Bill Lorensen <bill.lorensen at gmail.com> wrote:
> I have modified the test to report 1 of 3 results:
>
> 1) Rounds up
> 2) Rounds to even
> 3) Does neither consistently
>
> For 1 and 2, the test will pass. For 3 it will fail.
>
> Bill
>
>
> On Sun, Mar 8, 2009 at 11:45 AM, Simon Warfield
> <simon.warfield at childrens.harvard.edu> wrote:
>> Tom Vercauteren wrote:
>>>
>>> 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.
>>>
>>
>> My vote goes for "round up" for half-way cases, with an implementation that
>> gives the same results on all platforms,
>> with an efficient implementation where that is possible, and a ``slow''
>> implementation where an efficient implementation is not possible.
>>
>>> 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
>>>>
>>>>
>>>
>>>
>>
>>
>> --
>> Simon
>>
>>
>>
>