15

See also: Why is my image rotation algorithm not working?

This question isn't language specific, and is a math problem. I will however use some C++ code to explain what I need as I'm not experienced with the mathematic equations needed to express the problem (but if you know about this, I’d be interested to learn).

Here's how the image is composed:

ImageMatrix image;
image[0][0][0] = 1;
image[0][1][0] = 2;
image[0][2][0] = 1;
image[1][0][0] = 0;
image[1][1][0] = 0;
image[1][2][0] = 0;
image[2][0][0] = -1;
image[2][1][0] = -2;
image[2][2][0] = -1;

Here's the prototype for the function I'm trying to create:

ImageMatrix rotateImage(ImageMatrix image, double angle);

I'd like to rotate only the first two indices (rows and columns) but not the channel.

Nick Bolton
  • 38,276
  • 70
  • 174
  • 242

4 Answers4

37

The usual way to solve this is by doing it backwards. Instead of calculating where each pixel in the input image ends up in the output image, you calculate where each pixel in the output image is located in the input image (by rotationg the same amount in the other direction. This way you can be sure that all pixels in the output image will have a value.

output = new Image(input.size())

for each pixel in input:
{
  p2 = rotate(pixel, -angle);
  value = interpolate(input, p2)
  output(pixel) = value
}

There are different ways to do interpolation. For the formula of rotation I think you should check https://en.wikipedia.org/wiki/Rotation_matrix#In_two_dimensions

But just to be nice, here it is (rotation of point (x,y) angle degrees/radians):

 newX = cos(angle)*x - sin(angle)*y
 newY = sin(angle)*x + cos(angle)*y
Ivan Kochurkin
  • 4,413
  • 8
  • 45
  • 80
Hannes Ovrén
  • 21,229
  • 9
  • 65
  • 75
  • Thanks kigurai. I tried to implement this but haven't had much luck, maybe you could take a look? http://stackoverflow.com/questions/697520/why-is-my-image-rotation-algorithm-not-working – Nick Bolton Mar 30 '09 at 15:30
3

To rotate an image, you create 3 points: 

A----B 
|
|
C

and rotate that around A. To get the new rotated image you do this:

  • rotate ABC around A in 2D, so this is a single euler rotation
  • traverse in the rotated state from A to B. For every pixel you traverse also from left to right over the horizontal line in the original image. So if the image is an image of width 100, height 50, you'll traverse from A to B in 100 steps and from A to C in 50 steps, drawing 50 lines of 100 pixels in the area formed by ABC in their rotated state.

This might sound complicated but it's not. Please see this C# code I wrote some time ago: rotoZoomer by me

When drawing, I alter the source pointers a bit to get a rubber-like effect, but if you disable that, you'll see the code rotates the image without problems. Of course, on some angles you'll get an image which looks slightly distorted. The sourcecode contains comments what's going on so you should be able to grab the math/logic behind it easily.

If you like Java better, I also have made a java version once, 14 or so years ago ;) -> http://www.xs4all.nl/~perseus/zoom/zoom.java

Frans Bouma
  • 8,259
  • 1
  • 27
  • 28
2

Note there's another solution apart from rotation matrices, that doesn't loose image information through aliasing. You can separate 2D image rotation into skews and scalings, which preserve the image quality.

Here's a simpler explanation

heeen
  • 4,736
  • 2
  • 21
  • 24
  • Interesting, but I do not understand most of the math terms like "Nyquist frequency" or "spectrum of the image". Can you point me to materials to read for background info? Is this something I could explore on my own or would I need a real math education? (I'm a last year math high school student.) –  Apr 07 '09 at 18:04
  • @Iraimbilanja: Signal processing theory is second or third year EE stuff. Knowing how to do integral calculus first helps. – Mr Fooz Apr 07 '09 at 20:21
  • There's always wikipedia: http://en.wikipedia.org/wiki/Nyquist_frequency Think of the frequency as the spectrogram of an image: it is equivalent to the output of a graphical analyzer of an audio player, only in 2D. It shows which frequency is visible in the image the most, and in which direction. – heeen Apr 08 '09 at 08:09
  • The paper might be an overcomplication, the method is actually based on shifting rows left or right or colums up and down (shears), I'll edit in a simpler example. – heeen Apr 08 '09 at 08:20
  • The multiple skew method is the only high quality index image rotation, and it prevent s softening with rgba images This answer needs upvoting to the top. – Malcolm McLean Mar 04 '17 at 23:42
  • “Loose information through aliasing”? The quality of the output of this algorithm is not better of that of the straight-forward algorithm. And because it uses 3 shears, you do 3x interpolation along 1D each time, as opposed to only 2x (one for each dimension) in the other algorithm. So unless you use a good interpolation method, the quality might be worse. What this algorithm is, though, is fast. This is typically much faster than the other algorithm. – Cris Luengo Jan 13 '23 at 19:02
0

It seems like the example you've provided is some edge detection kernel. So if what you want to is detect edges of different angles you'd better choose some continuous function (which in your case might be a parametrized gaussian of x1 multiplied by x2) and then rotate it according to formulae provided by kigurai. As a result you would be able to produce a diskrete kernel more efficiently and without aliasing.

Maleev
  • 843
  • 3
  • 12
  • 21