通过剪切实现任意角度旋转（Paeth算法）

Question

我正在尝试编写一个Java实现Alan Paeth描述的三重剪切旋转算法（可以在此处找到描述：http://www.cipprs.org/papers/VI/VI1986/pp077-081-Paeth-1986.pdf）。问题不在于计算值，而是将旋转后的点放入图像网格中。论文中通过以下计算执行了三次连续的剪切以进行旋转：

1. x = x + alpha * y
2. y= y + beta * x
3. x = x + alpha * y

其中alpha和beta通过以下公式从给定的角度（弧度制）计算得出：

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

使用这些公式，可以将点围绕坐标系的中心旋转。为了纠正负值，我添加了每个点坐标轴上的最小计算坐标，以便最小值始终为0。

以下是我目前的Java实现：

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;
    }
}

注意：ShiftPoint是一个简单的自编写类，用于保存矩阵中特定坐标和值（在图像处理中：像素的rgb值）。

这里展示了计算的图形表示：

问题：虽然计算出来的值似乎是正确的，并且图形表示显示旋转实际上起作用了，但我不确定如何将计算出的值适应于固定的网格或图像（或2d数组），而不会扭曲它。此外，我不完全理解Paeth论文中给出的实现方法（对于x轴剪切）：

我知道skewi是计算出的值的整数部分，skewf是小数部分，但width、height、oleft和left应该是什么？此外：为什么他在第一个计算中将y值加0.5而没有考虑x值？

注意：我知道Java提供了简单的方法来旋转图像，但我正在尝试实现这个特定算法，只是为了好玩。我也知道可以通过网络搜索找到3-5个网站（如#1和#2），并尝试解释该算法，但首先它们不使用Java，其次它们大多参考Paeth的示例实现，所以它们并不非常有用。

- SilverMonkey

Answer 1

这种图像旋转方法的基本原则有两个：

• 定义一个坐标变换，将旋转后的图像中旋转后的x和y轴映射到原始图像的x和y轴上
• 通过在原始图像附近的值之间进行插值来计算旋转后图像中的每个像素

第一步通常比较容易，只涉及x和y坐标的简单线性组合。剪切变换（不严格是旋转，因为它们不保留每个像素的面积）只涉及类似于x -> x + alpha * y的东西。

Paeth的论文中给出的算法（发布于1986年）似乎是对进行剪切变换的第二步（插值）的仔细优化方法。我认为这归结为沿着x轴的分段线性插值，但写成一种形式，每个输出图像中的像素不需要多次查找数组。更清晰（稍微不那么高效）的方法可能涉及类似于skewf * pixel（x-skewi-1，y）+（1-skewf）* pixel（x-skewi，y）的东西。

这个算法显然是高度专门化的单轴偏斜。对于一般旋转，您可能需要更像双线性插值，覆盖围绕未旋转位置的每个像素中心的2x2像素方块。 （计算此中心像素值可能是Paeth代码中y + 0.5起源的地方。）

考虑到我们现在相对于1986年拥有多少计算能力，我猜测，如果您包括这种双线性插值的明确公式（即使它使用比Paeth方法更多的数组查找），您的代码将更容易理解，除非您真的需要最大的性能。

- rwp