Rotating a 2d matrix clockwise produces odd results

Question

Using the rotation matrix:

R(-t) = [cos(t)  sin(t)]
        [-sin(t) cos(t)]

where t = angle in radians

functionally expressed as:

[x] = [cos(t)  sin(t)][x]
[y]   [-sin(t) cos(t)][y]

or

x' =  x * cos(t) + y * sin(t)
y' = -x * sin(t) + y * cos(t)

i'm rotating a 2d matrix clockwise by 30 degrees with the dimensions 150x150.

in code it looks like this:

    cv::Mat m = cv::Mat::zeros(150, 150, CV_8UC1);
    cv::Mat nm = cv::Mat::zeros(150, 150, CV_8UC1);
    cv::rectangle(m, cv::Rect(0,0,150,150), cv::Scalar(100,100,100),-1);

    double rad = (30.0 * M_PI/180.0);
    for (int c = 0; c < m.cols;c++){
        for (int r = 0; r < m.rows;r++){
            int x = (m.cols*0.5)-c;
            int y = (m.rows*0.5)-r;
            int xn = (x*cos(rad) + y*sin(rad));
            int yn = (-x*sin(rad) + y*cos(rad));
            xn += (m.cols*0.5);
            yn += (m.rows*0.5);
            if (xn<0||xn>=m.cols||yn<0||yn>=m.rows){
                continue;
            }
            nm.at<uchar>(xn,yn)=m.at<uchar>(c,r);    
        }
    }

Mathematically it looks correct but these are the results I'm getting

Unrotated matrix:

Rotated matrix:

the rotated matrix appears grainy. What causes this? How is a it fixed? I'd prefer an explanation mathematically.

PS. Please do not point to opencv's precooked methods, I am aware that they exist.

Answer 1

Mathematical Explanation of the Pattern:

Consider the unrotated points (0, 0) and (1, 0):

Once rotated 30 degrees, these become (0, 0) and (0.866, -0.5), respectively.

Mathematically, these are distinct points. However, both these points are assigned to int variables, which round downwards for positive numbers, and upwards for negative numbers.

This means the computational value of the rotated points is actually (0, 0) and (0, 0).

Because both values are assigned to the same pixel, a double-up occurs and it appears as if a pixel has disappeared from the rotated square. This process continues to happen every time a double-up of pixel coordinates occurs, resulting in the pattern on your rotated square.

The Fix:

To fix this, you have to approach the problem backwards: Treat each square as if it has already been rotated, and see if it correlates with a point on the original square.

To do this, you use the inverse of the rotation matrix (Which you have done):

X' =  X * cos(t) + Y * sin(t)
Y' = -X * sin(t) + Y * cos(t)

So, all you need to do is augment your calculation loop a little:

for (int r = 0; r < nm.rows; ++r){ 
    for (int c = 0; c < nm.cols; ++c){ 
        int x = c - (m.cols*0.5); //Translates from the origin
        int y = r - (m.rows*0.5); 
        int xn = (x*cos(rad) + y*sin(rad)) + 0.5f; //The 0.5 corrects rounding
        int yn = (-x*sin(rad) + y*cos(rad)) + 0.5f;
        xn += (m.cols*0.5); //Translates back to the origin
        yn += (m.rows*0.5);
        if (xn >= 0 && xn < m.cols && yn >= 0 && yn < m.rows) 
            nm.at<uchar>(c,r) = m.at<uchar>(xn,yn);
            //Changed the above line so that nm is cycled through, not m
    }
}

How the fix works:

You have two rectangles: A blank one: nm, and one filled in one: m.

Originally you were cycling through all of m's pixels, rotating them, and setting the rotated points on nm, which resulted in the funny pattern.

The augmented version does the opposite: It cycles through all points of nm and rotates them back to the original square. If the point is inside m when it is rotated back, then the corresponding point on the nm is valid. Otherwise, it is invalid, and is not drawn.

Answer 2

The trick is to use the inverse transform, then sample every pixel on the result image. Say you want to rotate (or otherwise transform) the image I1(x1,y1) to produce an image I2(x2,y2), where I(x,y) is a function that gives the image intensity at point x,y). Say the transform you have in mind is T(x1,y1) = (x2, y2).

Now you iterate over every point in the target image I2, and apply the inverse transform Tinv to look up the corresponding pixel in the original image:

I2(x,y) := I1(Tinv(x,y))

That should give you a homogeneous box, at least in your example image. For better image quality, you'd want to use some interpolation because Tinv(x,y) will not be exactly the center of a pixel in I1.

It looks like there is some image warping in opencv, that should give you what you want. (Or is there a special reason why you don't want the opencv precooked methods?)

Answer 3

I think what you are experimenting is a form of moire pattern due to the fact that when you rotate pixels you are not rotating math points, but little squares instead. I found a nice pictorial representation of what I'm saying here (scroll down).

The solution would be to apply an anti-aliasing rotation algorithm.

Edit

A quick and dirty solution, which comes to my mind (I don't know how much effective - you should test it), would be to oversample the image before the rotation and then downsample it to the original dimensions. But this is really computationally wasteful. It might be used for testing though.