线性代数的妙用：怎样在Windows画图软件中实现28度旋转？

    在早期的小型图像编辑软件中，考虑到时间空间的限制，再加上算法本身的难度，很多看似非常简单的功能都无法实现。比如说，很多图像编辑软件只允许用户把所选的内容旋转 90 度、 180 度或者 270 度，不支持任意度数的旋转。毕竟，如果我们只是旋转 90 度的整数倍，那么所有像素仅仅是在做某些有规律的轮换，这甚至不需要额外的内存空间就能完成。但是，如果旋转别的度数，那么在采样和反锯齿等方面都将会有不小的挑战。

    不过， Windows 自带的画图软件聪明地用 skew 功能（中文版翻译成“扭曲”）部分地填补了无法自由变形的缺陷。随便选中图中的一块区域，再在菜单栏上选择“图像”→“拉伸/扭曲”，然后在“水平扭曲”那儿填写一个 -89 到 89 之间的整数（表示一个角度值），再按一下确定，于是整个图形就会像下图所示的那样被拉斜，其中 θ 就是你刚才填的度数。如果你填入的 θ 是负数值，则倾斜的方向会与下图方向相反。类似地，“垂直扭曲”功能会在竖直方向上对图形进行拉扯，如果角度值为正数，则整个图形会变得左低右高，如果角度值为负数，则整个图形会变得左高右低。

      

    不过，这玩意儿对于我们来说似乎完全没用。估计 99% 的人在使用画图软件的时候就从来没用过这个功能吧。如果真是这样，那么今天的问题恐怕将会是大家最近一段时间见过的最有趣的问题了：想办法利用 Windows 画图中的扭曲功能（近似地）实现 28 度旋转。


 
 
    答案：如下图，首先水平扭曲 -14 度，然后垂直扭曲 25 度，最后再水平扭曲 -14 度即可。这样的话，画板中被选中的内容将会被逆时针旋转 28 度。

      

    为什么？这是因为，扭曲的本质其实就是在原图上进行一个线性变换。水平扭曲实际上相当于是对图像各行进行平移，平移量与纵坐标的位置成正比。而这又可以看作是对每个点执行了下图所示的矩阵乘法操作：

      

    类似地，垂直扭曲则相当于对每个点执行了这么一个矩阵乘法的操作：

      

    另外，由于

      

    因此

      

    而最后一行就是大家非常熟悉的旋转矩阵！

    也就是说，连续执行上式中的三次扭曲，就可以实现旋转 θ 度了。其中，第一次扭曲和第三次扭曲都是水平扭曲 -θ/2 度，当 θ = 28° 时，我们应该填写的度数就是 -14 。麻烦的就是第二次扭曲：它看上去并不符合垂直扭曲矩阵的标准形式。垂直扭曲矩阵中，左下角那一项应该是 tan(θ) ，而并非 sin(θ) 。不过，我们完全可以用正切值去模拟 sin(θ) 呀！利用计算机可以解得，当 θ = 28° 时， sin(28°) 约为 0.469 ，离它最近的正切值是 tan(25°) ≈ 0.466 。因此，我们在第二步的时候填入了垂直扭曲 25 度。

    值得一提的是，实际上我们已经得到了一种非常高效并且非常容易编写的图像旋转算法：只需要连续调用三次扭曲操作即可。而每次扭曲操作本质上都是对各行或者各列的像素进行平移，因而整个算法完全不需要任何额外的内存空间！根据 Wikipedia 的描述，这种方法是由 Alan Paeth 在 1986 年提出的。

    由于 tan(25°) 并不精确地等于 sin(28°) ，因而这里实现的 28 度旋转也并不是绝对精确的。不过，画图软件本身还提供了水平缩放和垂直缩放的功能，把它们也加进来的话，线性变换的复合将会变得更加灵活，或许我们就能设计出一些更复杂但却更精确的旋转方案了。这些问题就留给感兴趣的读者继续探究吧。

 
参考资料：http://datagenetics.com/blog/august32013/index.html

23 条评论

发表评论




Enter Captcha Here :