Very Computer

by **Lewis Seller** » Thu, 13 Jun 2002 04:46:10

Let us say for arguement I want to rotate a 2d bitmap 1 degree 360
times. What exactly is the best alg out there at the moment that will
keep the pixels from degrading.

Speed isn't really any issue here. (Though of course it's always
nice.)

THanks for any pointers,

--min

by **Angel Montill** » Thu, 13 Jun 2002 06:31:13

I'm trying just the same.

The problem I've is that sin and cos functions are not enought accurate.

Hope any idea.

Quote:
> Let us say for arguement I want to rotate a 2d bitmap 1 degree 360
> times. What exactly is the best alg out there at the moment that will
> keep the pixels from degrading.

> Speed isn't really any issue here. (Though of course it's always
> nice.)

> THanks for any pointers,

> --min

by **Carsten Neubau** » Thu, 13 Jun 2002 09:22:50

hi,
you only have to look for the best way
to interpolate between pixels.

some months ago i found a great tutorial about this.
see
http://www.fh-furtwangen.de/~dersch/interpolator/interpolator.html
this should answer some questions.

carsten

http://www.c14sw.com/

by **Lewis Seller** » Thu, 13 Jun 2002 11:35:18

Quote:>hi,
>you only have to look for the best way
>to interpolate between pixels.

>some months ago i found a great tutorial about this.
>see
>http://www.fh-furtwangen.de/~dersch/interpolator/interpolator.html
>this should answer some questions.

Interesting. I was thinking perhaps none of my interpolation methods
were correctly coded. After glancing at that link I see all's as it
should be. Nothing seems to survive 360 1degree rotations very well.

Quote:>carsten

>http://www.c14sw.com/

by **Peter Wilso** » Thu, 13 Jun 2002 13:45:24

You are correct - rounding errors will always creep into any incremental
rotation based upon a previous rotation - this is normal. If you want
accuracy, then don't do incremental rotations based upon previous rotations.
Instead, rotate the original data 1 degree. Then rotate the original data
by 2 degrees, and so on.

- Peter

> >hi,
> >you only have to look for the best way
> >to interpolate between pixels.

> >some months ago i found a great tutorial about this.
> >see
> >http://www.fh-furtwangen.de/~dersch/interpolator/interpolator.html
> >this should answer some questions.

> Interesting. I was thinking perhaps none of my interpolation methods
> were correctly coded. After glancing at that link I see all's as it
> should be. Nothing seems to survive 360 1degree rotations very well.

> >carsten

> >http://www.c14sw.com/

by **Angel Montill** » Thu, 13 Jun 2002 21:38:59

> You are correct - rounding errors will always creep into any incremental
> rotation based upon a previous rotation - this is normal. If you want
> accuracy, then don't do incremental rotations based upon previous
rotations.
> Instead, rotate the original data 1 degree. Then rotate the original data
> by 2 degrees, and so on.

> - Peter

> > >hi,
> > >you only have to look for the best way
> > >to interpolate between pixels.

> > >some months ago i found a great tutorial about this.
> > >see
> > >http://www.fh-furtwangen.de/~dersch/interpolator/interpolator.html
> > >this should answer some questions.

> > Interesting. I was thinking perhaps none of my interpolation methods
> > were correctly coded. After glancing at that link I see all's as it
> > should be. Nothing seems to survive 360 1degree rotations very well.

> > >carsten

> > >http://www.c14sw.com/

Yes I know that: It is because:

Sin(a+b) != sin(a)+sin(b)

This is because you must:
1o Rotate (minus) -a degrees.
2o Rotate a+b degrees

You can use: sen(a+b) = sen(a)cos(b)+cos(a)sen(b)

But the problem is. How to interpolate the points.

Do you explain an accurate algorithm for interpolation?

Thank you!!!

by **Hans-Bernhard Broeke** » Thu, 13 Jun 2002 22:07:53

> I'm trying just the same.
> The problem I've is that sin and cos functions are not enought accurate.

No, that's not the true problem. sin() and cos() (if evaluated the
usual way, i.e. in floating point) are effectively of infinite
accuracy, regarding this problem.

The inaccuracy creeps in because you discretize the sin/cos result
(output pixel positions) before using it, not because the result
itself was inaccurate. I.e. every single output pixel has an expected
position error of about half a pixel width in all directions.

Do that 360 times and the output pixels could, roughly spoken, be 180
pixels away from their correct positions.
--

Even if all the snow were burnt, ashes would remain.

by **Hans-Bernhard Broeke** » Thu, 13 Jun 2002 22:15:37

[... please clip quoted postings down to the relevant parts, thank you ...]

Quote:> Yes I know that: It is because:
> Sin(a+b) != sin(a)+sin(b)

No, it's not.

Quote:> This is because you must:
> 1o Rotate (minus) -a degrees.
> 2o Rotate a+b degrees

No, there's almost never a need to do that. Or if there is, you're in
deep trouble without any way out left.

You should keep a copy of the *original* input, completely unrotated.
So instead of rotating by -a degrees, you just start from that copy
again, and rotate that by a+b degrees.

The true problem is that there are rounding errors in all rotated
images due to their pixelized structure rather than due to problems
with the evaluation of trig functions. If you use such a stained,
rotated images as input in any further calculations, those rounding
errors will pile up and eventually destroy your image.

--

Even if all the snow were burnt, ashes would remain.

by **Hans-Bernhard Broeke** » Thu, 13 Jun 2002 22:23:29

> Let us say for arguement I want to rotate a 2d bitmap 1 degree 360
> times. What exactly is the best alg out there at the moment that will
> keep the pixels from degrading.

The best is not to do it that way at all. Rather do 360 rotations all
starting from the original image, with rotation angles 0, 1, 2, 3,
... all the way to 359 degrees.

--

Even if all the snow were burnt, ashes would remain.

by **Marius Bernkle** » Thu, 13 Jun 2002 22:24:04

> The true problem is that there are rounding errors in all rotated
> images due to their pixelized structure rather than due to problems
> with the evaluation of trig functions. If you use such a stained,
> rotated images as input in any further calculations, those rounding
> errors will pile up and eventually destroy your image.

Yup, but if you do that with motion blur as well, you get a much
neater effect than some stupid rotate ;-)

Marius
--
<URL: http://www.stud.ifi.uio.no/~mariube/ >

My computer is already slow enough.

by **Maxim Shemanar** » Thu, 13 Jun 2002 22:48:43

There's also a good arcticle with sources in Pascal:
http://www.fho-emden.de/~hoffmann/bicubic03042002.pdf
BTW, Gernot Hoffmann appears here from time to time :-)

McSeem
http://www.antigrain.com

by **Stephen H. West** » Thu, 13 Jun 2002 23:06:57

> > Let us say for arguement I want to rotate a 2d bitmap 1 degree 360
> > times. What exactly is the best alg out there at the moment that will
> > keep the pixels from degrading.

> The best is not to do it that way at all. Rather do 360 rotations all
> starting from the original image, with rotation angles 0, 1, 2, 3,
> ... all the way to 359 degrees.

Well, yes, but that's not the point. He's really talking about a
torture test for image resampling. Intuitively, minimizing the
cumulative error in this case will minimize the error of every
resampling operation, and would be a very safe bet for any resampling
operation. Helmut Dersch has a page on this that has already been
referenced in this thread. His ultimate filter is a 256x256 windowed
sinc() kernel, as I recall.

--
-Stephen H. Westin
Any information or opinions in this message are mine: they do not
represent the position of Cornell University or any of its sponsors.

by **Lewis Seller** » Fri, 14 Jun 2002 06:05:56

>> The best is not to do it that way at all. Rather do 360 rotations all
>> starting from the original image, with rotation angles 0, 1, 2, 3,
>> ... all the way to 359 degrees.

>Well, yes, but that's not the point. He's really talking about a
>torture test for image resampling. Intuitively, minimizing the

Exactly. Personally I would always rotate from the original as well,
however the project design does *allow* end-users do all manner of
things we'd generally know not to even try.

Quote:>cumulative error in this case will minimize the error of every
>resampling operation, and would be a very safe bet for any resampling

4 64-bit floating point vars for rgba, eh? /-)

Quote:>operation. Helmut Dersch has a page on this that has already been
>referenced in this thread. His ultimate filter is a 256x256 windowed
>sinc() kernel, as I recall.

Saw that. Looking at it this morning actually. Slow I'm sure... but
the image held up very well.

--min

by **Gernot Hoffma** » Fri, 14 Jun 2002 16:57:42

> ...
> 4 64-bit floating point vars for rgba, eh? /-)
> ...

Lewis,

thats the crucial point.
The appreciated work by Meijeran, Thevenaz and probably by Dersch
(apologize for eventually wrong spelling), as discussed here two
months ago, was done by "Real" coding of colors, float or double.
This is not relevant for standard image processing applications.
Even Photoshop can use 16 bit per channel only for some operations.

Therefore, in 8-bit per channel coding, the quality of ONE step,
(rotation, moderate scaling, morphing, perspective rectification),
is essential.

Best regards ---Gernot Hoffmann

by **Bart.Vanhauwa..** » Fri, 14 Jun 2002 06:33:33

> Exactly. Personally I would always rotate from the original as well,
> however the project design does *allow* end-users do all manner of
> things we'd generally know not to even try.

In that case, keep the original image and a running count of the
rotations so far.

cu bart

--
http://www.irule.be/bvh/

Very Computer

best alg for n image rotations

best alg for n image rotations

best alg for n image rotations

best alg for n image rotations

best alg for n image rotations

best alg for n image rotations

best alg for n image rotations

best alg for n image rotations

best alg for n image rotations

best alg for n image rotations

best alg for n image rotations

best alg for n image rotations

best alg for n image rotations

best alg for n image rotations

best alg for n image rotations

best alg for n image rotations