Arbitrary angular rotation through shear (Paet algorithm)

Question

I am trying to write a Java implementation of 3 shift rotation algorithms described by Alan Paet . The problem is not in calculating the values, but in placing the rotated points on the image grid. In the article, rotation is performed by three consecutive legs set by the following calculation:

• x = x + alpha * y
• y = y + beta * x
• x = x + alpha * y

Alpha and beta are calculated by a given angle (theta; in radians) according to the following formulas:

• beta = sin (theta)
• alpha = - tan (theta / 2)

Using these formulas, the points rotate around the center of the coordinate system.

To correct negative values, I add the minimum calculated coordinate for the corresponding axis to each point, so that the minimum value will always be 0.

My Java implementation so far:

ShiftPoint[] val = new ShiftPoint[m*n]; double minX = 0,minY = 0, maxX = 0, maxY = 0; double alpha = -1d* Math.tan(Math.toRadians(theta)/2d); double beta = Math.sin(Math.toRadians(theta)); for(int a = 0; a < m; a++) { for(int b = 0; b < n; b++) { ShiftPoint temp = new ShiftPoint(a, b, values[a][b]); double newX = b + alpha * a; //first shear double newY = a + beta * newX; //second shear newX += alpha * newY; //third shear temp.setX(newX); temp.setY(newY); val[m * b + b] = temp; } } 

Note. ShiftPoint is a simple self-employed class for storing certain coordinates and values ​​inside a matrix (in case of image processing: pixel rgb value). Here is a graphical representation of the calculations:

Problem: Although the calculated values ​​seem to be correct, and the graphical representation shows that rotation actually works, I'm not sure how the image (or 2d array) matches the calculated values ​​on a fixed grid does not distort it. Also, I do not fully understand the implementation (for shifting along the x axis) given by Paets:

I get that skewi is the integer part of the calculated value, and skewf is the fractional part, but what should be the width, height, oleft and left? Also: why does it add 0.5 to the y value and not take the x value into account in its first calculation?

Note. I know that Java offers easy ways to rotate images, but I'm trying to implement this particular algorithm just for fun. I also know about 3-5 websites that can be found via web search (for example, # 1 and # 2 ) and try to explain this algorithm, but firstly, they do not use java, and secondly, they are in mostly refer to an example implementation of Paeth, so they are not very useful.

Answer 1

The essential principle of this approach to image rotation is twofold:

• Define a coordinate transformation that rotates the x and y axes in a rotating image on the x and y axes of the original image.
• Compute each pixel in a rotating image by interpolating between the values ​​next to the corresponding point in the original image

The first step, as a rule, is simpler and will include simple linear combinations of x and y coordinates. Shift transformations (which are not strictly rotational, since they do not preserve the area of ​​each pixel) include only something like x → x + alpha * y.

The algorithm presented in Paet's article (dated 1986) seems to be a carefully optimized approach to the second (interpolation) step for the shear transformation. I think this comes down to piecewise linear interpolation along the x axis, but is written in a form that does not require more than one array search for each pixel in the output image. A clearer (and slightly less efficient) approach may include something like a pixel skewf * pixel (x-skewi-1, y) + (1-skewf) * pixel (x-skewi, y).

This particular algorithm is obviously very specialized for uniaxial skew. For general rotation, you may need something more like bilinear interpolation for each 2x2 pixel square that surrounds a non-rotating location corresponding to the center of each pixel in the rotated image. (The calculation of this central pixel value may be the beginning of y + 0.5 in the Paeth code.)

Given how much processing power we have in relative 1986, I suspect your code would be much easier to understand if you included an explicit formula for this bilinear interpolation, even if it uses more array searches than the Paeth approach, if you really need to maximum performance.