Rounding of real numbers near the origin leads to rotation artifacts

Question

I recently noticed anomalous artefacts in the output of my rotation algorithm. The implementation I used projected high densities of points from the destination matrix onto the source image to calculate the relative ratios of the contributions from the source pixels. These values were cached to allow very fast rotations via unrolled loops.

The problem was caused by rounding behaviour, this is best illustrated from the context of a one-dimensional sampling strategy:

If the center is 0.0 and is translated by 0.9 in either direction, it is still 0 when rounded

short(+0.9) == 0
short(-0.9) == 0

however if the center is 1.0 and is translated by 0.9 in either direction, then

short(+0.1) == 0
short(+1.9) == 1

Any point that fell within 1 unit distance from the origin was attributed to the origin when rounded. This caused oversampling of points that fell near the origin of an axis in the source image. The solution was to translate the floating point coordinate deep into postive space when performing the rounding operation and the translate it back towards the origin afterwards.

My question: Is there a way to avoid this rounding bug without translating into positive space?

You should probably round to nearest rather than truncating ? — Paul R, Nov 19 '12 at 21:50
I don't understand. `short` is an integer. `0.9` is `0`. `1.9` is `1`. There are no decimals. — David, Nov 19 '12 at 21:50
It's the rounding behaviour of C++, the first effect introduced oversampling in my implementation, that is what I want to avoid — Gearoid Murphy, Nov 19 '12 at 21:51
Use the function from this previous answer: http://stackoverflow.com/a/485549/805659 — japreiss, Nov 19 '12 at 21:53
Rounding to the nearest integer is not what I need, the projected positions are point samples, they should accurately reflect the value of the pixel they land on — Gearoid Murphy, Nov 19 '12 at 21:56
You could define your own function, roundToward(0.1, 1.0) = 1.0, and not worry about the implementation-- which would probably be the translation solution. — Beta, Nov 19 '12 at 22:17

huysentruitw · Accepted Answer · 2012-11-19T22:26:29.527

4

It seems like you just need to use the floor function:

(short)floor(0.9) = 0
(short)floor(-0.9) = -1

edited Nov 19 '12 at 22:26

answered Nov 19 '12 at 22:20

huysentruitw

27,376
9
90
133

I had mistakenly thought that the floor function would round towards zero even for negative numbers. – Gearoid Murphy Nov 19 '12 at 22:56

score 1 · Answer 2 · answered Nov 19 '12 at 22:37

So the obvious answer is to use the floor function. And it is a good answer, it will fix your problem.

It does leave you with the issue that (1.0/3.0)*3.0 != 3.0 in IEEE floating point mathematics. In fact, static_cast<short>(floor((1.0/3.0)*3.0)) == 2.

You probably want to add an epsilon to your values before calling floor. And you probably don't want to use C-style casts, because there is about one legitimate reason to use a C-style cast (google "do not use C-style casts" to find out more), and that one is quirky.

So you want something like this:

short smart_round( double d, double epsilon=0.00001 ) {
  short retval = static_cast<short>(floor( d + epsilon ) );
  return retval;
}

which incorporates an epsilon, does a static_cast, and uses floor to otherwise round down (instead of the default C/C++ behavior of "round towards zero").

Rounding of real numbers near the origin leads to rotation artifacts

2 Answers2