通过剪切旋转

BY hcx

2024-06-27

我们知道，像素排列在一个方形的网格上，而这个网格是没法旋转的。那么该怎么旋转一张图片？

像素网格上不能进行的旋转，以及可以进行的“旋转”（使用本文介绍的算法）

这篇文章我想向大家介绍这些算法中的一个，它是我目前为止见过的最优美的算法之一。它的核心想法是：

能不能把一个旋转拆分为几个简单的，能进行的操作？

分而治之

线性代数告诉我们，旋转是一个线性变换，它可以用一个矩阵表示。

\begin{bmatrix} x'\\y' \end{bmatrix} = \begin{bmatrix} \textcolor{#19A974} {cos(\theta)} & \textcolor{#FF4136} {-sin(\theta)} \\ \textcolor{#19A974} {sin(\theta)} & \textcolor{#FF4136} {cos(\theta)} \end{bmatrix} \cdot \begin{bmatrix} \textcolor{#19A974} {x} \\ \textcolor{#FF4136} {y} \end{bmatrix}

theta 59°

将一个黑底上的网格进行旋转，用红绿色标注出两个新的列向量，并展示一个同样配色的矩阵。

这个算法的目标是，将一个旋转表示为几个线性变换的叠加，使得这些简单的线性变换能在像素网格上完成。它利用了以下两个观察。

1. 对于一张像素图，剪切（shear）操作，另一种线性变换，可以近似地进行；只要我们限制剪切方向只沿坐标轴方向。

\begin{bmatrix} 1 & \textcolor{#FF4136} {shearY} \\ 0 & 1 \end{bmatrix} , \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} , \begin{bmatrix} 1 & 0 \\ \textcolor{#19A974} {shearX} & 1 \end{bmatrix}

shear 1

一个渐变色的方块（黄到蓝），左右两图分别展示X与Y方向的剪切。

方法很简单：对于X轴方向的剪切，选定中心行 $i$ 了以后，行 $j$ 的移动量可以用 $\left \lfloor (j-i) \cdot shear \right \rfloor$ 计算；Y轴方向同理。

2. 一个旋转可以由三次剪切的叠加表示：一次 $X$ 轴，一次 $Y$ 轴，再一次 $X$ 轴。

\begin{align*} &\begin{bmatrix} 1 & -tan(\frac \theta 2) \\ 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 \\ sin(\theta) & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & -tan(\frac \theta 2) \\ 0 & 1 \end{bmatrix} \\ &= \begin{bmatrix} 1 & -tan(\frac \theta 2) \\ 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 1 \\ 1 - sin(\theta) & sin(\theta) \cdot tan(\frac \theta 2) \end{bmatrix} \\ &= \begin{bmatrix} 1 & -tan(\frac \theta 2) \\ 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 1 \\ sin(\theta) & cos(\theta) \end{bmatrix} \\ &= \begin{bmatrix} 1 - sin(\theta) \cdot tan(\frac \theta 2) & 1 - tan(\frac \theta 2) \cdot cos(\theta) \\ sin(\theta) & cos(\theta) \end{bmatrix} \\ &= \begin{bmatrix} cos(\theta) & -sin(\theta) \\ sin(\theta) & cos(\theta) \end{bmatrix} \end{align*}

\begin{bmatrix} cos(\theta) & -sin(\theta) \\ sin(\theta) & cos(\theta) \end{bmatrix} = \begin{bmatrix} 1 & -tan(\frac \theta 2) \\ 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 \\ sin(\theta) & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & -tan(\frac \theta 2) \\ 0 & 1 \end{bmatrix}

theta 58°

这四张图分别展示一个渐变色的方块增加一个矩阵变换后，变成的新平行四边形。最左侧的方块进行了旋转。

这是一个非常令人意想不到的结果！经过这样的拆分，最终的算法就显而易见了。

既然我们可以对图片进行近似剪切操作，也可以将一个旋转分解为若干个剪切，那么只要把精细的剪切替换成像素网格上的近似，我们就能旋转一张图片了！

theta

四张图，分别展示本文开始的宇宙飞船增加一个矩阵变换后成为的新形状。

从图里也许你已经能看出来了，这个算法有一个显而易见的劣势：需要一个足够大的边框，用来存放剪切后挪出来的像素点；这也意味着旋转的角度不能太大。上面的动画展示的旋转只有-90° ~ 90°，因为超过这180°的旋转范围，只需要中心对称地翻转一下就能转化为范围内的旋转。文章开头的旋转动画就是这样完成的。

这个奇怪的算法其实也有一些优势。首先一个，图中的每一个像素点恰好对应新图片上的一个像素点，不多不少！基于插值的其他旋转算法在旋转时可能会丢掉一些亮度较高的像素点，但这个算法不会。

另一个有趣的地方是，这个算法是完全可逆的！旋转两次只要和为0°，就能回到原来的位置。

一般来说，图像旋转的任务都会交给GPU来完成，但对于一些古老的、没有内置旋转算法的硬件，这个算法的效率相当地高，因为很多硬件都能高效地实现剪切操作。

这个算法还能拓展到三维以及更高维的空间，因为高维旋转矩阵也能分解为若干个剪切矩阵的乘积（具体的分解方法就留给读者自己推导了）。

说实话，硬要说这个算法有什么用，它的用处其实不大：在硬件那么快的今天，没有什么人会用这个算法来旋转图片。但是，它带给我们的惊奇的确是少有的。正如Samuel Johnson 所说：

"It is not done well; but you are surprised to find it done at all!"