[Insight-developers] Rounding Test : Redux

Fri Mar 13 13:13:30 EDT 2009

Posting one more time without attachments to pass the size limit.

Luis,

It would indeed be great to have this available. I have attached the
patch for the two files that need to be replaced in ITK:
- Utilities/vxl/core/vnl/tests/test_math.cxx
- Utilities/vxl/core/vnl/vnl_math.h

Some tests will be failing but the fix should be as easy as replacing
vnl_math_round by vnl_math_round_halfintup.

Commit these files would finally allow me to close these bugs:
http://www.itk.org/Bug/view.php?id=2078
http://www.itk.org/Bug/view.php?id=5692

Simon,

Thanks for the feedback. I also saw that issue, I just fear that
introducing bound checking in the interpolators might slow things
down. But do we have the choice?

Tom

On Thu, Mar 12, 2009 at 13:16, Luis Ibanez <luis.ibanez at kitware.com> wrote:
>
> Tom,
>
> This is great,
> Thanks for posting the patch to the vxl list.
>
> Should we include it in the current VNL directory in ITK ?
>
>
>   Luis
>
>
> -----------------------
> Tom Vercauteren wrote:
>>
>> 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
>>>>
>>>>
>>>>
>>>
>> _______________________________________________
>> 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
>>
>