Why is my image rotation algorithm not working?

Question

Attempts 1 & 2:

Note: Removed first attempts to cut down on question size. See community wiki for previous attempts.

Attempt 3:

As per fuzzy-waffle's example, I have implemented the following, which doesn't appear to work correctly. Any ideas what I could be doing wrong?

ImageMatrix ImageMatrix::GetRotatedCopy(VDouble angle)
{
    // Copy the specifications of the original.
    ImageMatrix &source = *this;
    ImageMatrix &target = CreateEmptyCopy();

    double centerX = ((double)(source.GetColumnCount()-1)) / 2;
    double centerY = ((double)(source.GetRowCount()-1)) / 2;

    // Remember: row = y, column = x
    for (VUInt32 y = 0; y < source.GetRowCount(); y++)
    {
     for (VUInt32 x = 0; x < source.GetColumnCount(); x++)
     {
            double dx = ((double)x) - centerX;
            double dy = ((double)y) - centerY;

            double newX = cos(angle) * dx - sin(angle) * dy + centerX;
            double newY = cos(angle) * dy + sin(angle) * dx + centerY;

            int ix = (int)round(newX);
            int iy = (int)round(newY);

            target[x][y][0] = source[ix][iy][0];
     }
    }

    return target;
}

With this prototype matrix...

1 2 1 
0 0 0 
-1 -2 -1

... prototype.GetRotatedCopy(0) (which is correct) ...

1 2 1 
0 0 0 
-1 -2 -1

... prototype.GetRotatedCopy(90) (incorrect) ...

-2 0 0 
-2 0 2 
0 0 2

... prototype.GetRotatedCopy(180) (incorrect - but sort of logical?) ...

0 -1 -2 
1 0 -1 
2 1 0

... prototype.GetRotatedCopy(270) (incorrect - why is this the same as 0 rotation?) ...

1 2 1 
0 0 0 
-1 -2 -1

Solution:

As pointed out by Mark Ransom, I should be using radians, not degrees; I have adjusted my code as follows:

ImageMatrix ImageMatrix::GetRotatedCopy(VDouble degrees)
{
    // Copy the specifications of the original.
    ImageMatrix &source = *this;
    ImageMatrix &target = CreateEmptyCopy();

    // Convert degree measurement to radians.
    double angle = degrees / 57.3;

    // ... rest of code as in attempt #3 ...

Thanks for all your help guys!

1 2 1 
0 0 0 
-1 -2 -1 

1 2 1 
0 0 0 
-1 -2 -1 

-1 0 1 
-2 0 2 
-1 0 1 

-1 -2 -1 
0 0 0 
1 2 1 

1 0 -1 
2 0 -2 
1 0 -1

Answer 1

your formulas for newRow and newColumn are switched. Remember that row = y and column = x.

Rotation

Answer 2

The problem is that your memory accesses are out of bounds.

After rotation your NewRow and NewColumn may be larger than the original width/height of the image. They may even be negative. If you don't take care about that fact, you'll end up with garbage data (best case) or crashes.

The most common way to deal with this is to just ignore all such pixels. You could also clamp or wrap around the valid intervals. This get's a padding or tiling effect.

Here it's shown with ignoring outside pixels.

int width = 10;
int height = 10;
for (int row = 0; row < height; row++)
{
        for (int column = 0; column < width; column++)
        {
                int newRow = (cos(angle) * row) - (sin(angle) * column);
                int newColumn = (sin(angle) * row) + (cos(angle) * column);

                if ((newRow >=0) && (newRow < width) && 
                   (newColumn >=0) && (newColumn < height))
                {
                  target[row][column][0] = source[newRow][newColumn][0];
                }
        }
}

Answer 3

The algorithm, unless I read it wrong, seems to rotate around the point 0,0 which is not what you want. Maybe you need to add height/2 and width/2 to your row and column values before you plug them in.

for (int y = 0; y < 10; y++) { 
   for (int x = 0; x < 10; x++) { 
      VUInt32 newX = (cos(angle) * (x-5)) - (sin(angle) * (y-5)); 
      VUInt32 newY = (sin(angle) * (x-5)) + (cos(angle) * (y-5)); 
      target[newY][newX][0] = source[y][x][0]; 
   } 
}

This basically adjusts the rotation center from the upper left corner to the center of the image.

Answer 4

Here is a complete example I hacked up: I think among other things you may have not been using radians (which we all should use and love). I keep the new coordinates in doubles which seemed to make it less finicky. Note that I am not doing bounds checking which I should but I was lazy.

If you need a faster rotation you can always use shearing like this example.

#include <math.h>
#include <stdio.h>

#define SIZEX 3
#define SIZEY 3

int source[SIZEX][SIZEY] = {
  { 1, 0, 0 },
  { 0, 1, 0 },
  { 0, 0, 1 }
};

int target[SIZEX][SIZEY];

int main () {
  double angle = M_PI/2.0;

  memset(target,0,sizeof(int)*SIZEX*SIZEY);

  double centerX = ((double)(SIZEX-1))/2.0;
  double centerY = ((double)(SIZEY-1))/2.0;

  for (int y = 0; y < SIZEY; y++) {
    for (int x = 0; x < SIZEX; x++) {
        double dx = ((double)x)-centerX;
        double dy = ((double)y)-centerY;
        double newX = cos(angle)*dx-sin(angle)*dy+centerX;
        double newY = cos(angle)*dy+sin(angle)*dx+centerY;

        int ix = (int) round(newX);
        int iy = (int) round(newY);
        target[x][y] = source[ix][iy];
    }
  }

  for (int i=0;i<SIZEY;i++) {
    for (int j=0;j<SIZEX;j++) {
      printf("%d ", target[j][i]);
    }
    printf("\n");
  } 
}

Answer 5

short answer: you're doing it wrong.

This is essentially a problem in interpolation, and the way you've approached it introduces discontinuities. Fundamentally this is because rotating a lattice (the regular grid your image is laid out on) does not result in another sampling on the same lattice except for very special cases.

There is no single correct way to do this, by the way, but there are various trade offs with respect to speed and accuracy and also what can be assumed about the original signal (image).

So what are your design parameters? Do you need this to be very fast or very accurate? How do you want to handle aliasing?