《线性插值算法实现图像缩放旋转祥解》由会员分享，可在线阅读，更多相关《线性插值算法实现图像缩放旋转祥解（6页珍藏版）》请在金锄头文库上搜索。
1、线性插值算法实现图像缩放、旋转详解 这是一篇关于图形处理线性插值算法细节的文章，转载此文的目的在于能给那些对图像处理算法感兴趣的网友一些启示，对于大量的入门网友来说，这样的文章或许有些让人眼晕，但我相信哪怕只理解一些表皮的图像处理算法知识，以后在使用软件处理图片时便能做“心里有数”，还是有所助宜的。 在 Windows 中做过图像方面程序的人应该都知道 Windows 的 GDI 有一个 API 函数：StretchBlt，对应在 VCL 中是 TCanvas 类的 StretchDraw 方法。它可以很简单地实现图像的缩放操作。但问题是它是用了速度最快，最简单但效果也是最差的“最近邻域法”，
2、虽然在大多数情况下，它也够用了，但对于要求较高的情况就不行了。不久前做了一个小玩意儿，用于管理我用 DC 拍的一堆照片，其中有一个插件提供了缩放功能，目前的版本就是用了 StretchDraw，有时效果不能令人满意，我一直想加入两个更好的：线性插值法和三次样条法。经过研究发现三次样条法的计算量实在太大，不太实用，所以决定就只做线性插值法的版本了。从数字图像处理的基本理论，我们可以知道：图像的变形变换就是源图像到目标图像的坐标变换。简单的想法就是把源图像的每个点坐标通过变形运算转为目标图像的相应点的新坐标，但是这样会导致一个问题就是目标点的坐标通常不会是整数，而且像放大操作会导致目标图像中没有被
3、源图像的点映射到，这是所谓“向前映射”方法的缺点。所以一般都是采用“逆向映射”法。但是逆向映射法同样会出现映射到源图像坐标时不是整数的问题。这里就需要“重采样滤波器”。这个术语看起来很专业，其实不过是因为它借用了电子信号处理中的惯用说法（在大多数情况下，它的功能类似于电子信号处理中的带通滤波器），理解起来也不复杂，就是如何确定这个非整数坐标处的点应该是什么颜色的问题。前面说到的三种方法：最近邻域法，线性插值法和三次样条法都是所谓的“重采样滤波器”。所谓“最近邻域法”就是把这个非整数坐标作一个四舍五入，取最近的整数点坐标处的点的颜色。而“线性插值法”就是根据周围最接近的几个点（对于平面图像来说，
4、共有四点）的颜色作线性插值计算（对于平面图像来说就是二维线性插值）来估计这点的颜色，在大多数情况下，它的准确度要高于最近邻域法，当然效果也要好得多，最明显的就是在放大时，图像边缘的锯齿比最近邻域法小非常多。当然它同时还带业个问题：就是图像会显得比较柔和。这个滤波器用专业术语来说（呵呵，卖弄一下偶的专业_）叫做：带阻性能好，但有带通损失，通带曲线的矩形系数不高。至于三次样条法我就不说了，复杂了一点，可自行参考数字图像处理方面的专业书籍，如本文的参考文献。再来讨论一下坐标变换的算法。简单的空间变换可以用一个变换矩阵来表示：x,y,w=u,v,w*T其中：x,y为目标图像坐标，u,v 为源图像坐标，
5、w,w称为齐次坐标，通常设为1，T 为一个 3X3 的变换矩阵。这种表示方法虽然很数学化，但是用这种形式可以很方便地表示多种不同的变换，如平移，旋转，缩放等。对于缩放来说，相当于：Su 0 0 x, y, 1 = u, v, 1 * | 0 Sv 0 |0 0 1 其中 Su,Sv 分别是 X 轴方向和 Y 轴方向上的缩放率，大于 1 时放大，大于 0 小于 1 时缩小，小于 0 时反转。矩阵是不是看上去比较晕？其实把上式按矩阵乘法展开就是： x = u * Su y = v * Sv就这么简单。有了上面三个方面的准备，就可以开始编写代码实现了。思路很简单：首先用两重循环遍历目标图像的每个点坐
6、标，通过上面的变换式（注意：因为是用逆向映射，相应的变换式应该是：u = x / Su 和 v = y / Sv）取得源坐标。因为源坐标不是整数坐标，需要进行二维线性插值运算：P = n*b*PA + n * ( 1 b )*PB + ( 1 n ) * b * PC + ( 1 n ) * ( 1 b ) * PD其中：n 为 v（映射后相应点在源图像中的 Y 轴坐标，一般不是整数）下面最接近的行的 Y 轴坐标与 v 的差；同样 b 也类似，不过它是 X 轴坐标。PA-PD 分别是(u,v)点周围最接近的四个（左上，右上，左下，右下）源图像点的颜色（用 TCanvas 的 Pixels 属性
7、）。P为(u,v)点的插值颜色，即(x,y)点的近似颜色。这段代码我就不写了，因为它的效率实在太低：要对目标图像的每一个点的 RGB 进行上面那一串复杂的浮点运算。所以一定要进行优化。对于 VCL 应用来说，有个比较简单的优化方法就是用 TBitmap 的 ScanLine 属性，按行进行处理，可以避免 Pixels 的像素级操作，对性能可以有很大的改善。这已经是算是用 VCL 进行图像处理的基本优化常识了。不过这个方法并不总是管用的，比如作图像旋转的时候，这时需要更多的技巧。无论如何，浮点运算的开销都是比整数大很多的，这个也是一定要优化掉的。从上面可以看出，浮点数是在变换时引入的，而变换参数
8、 Su,Sv 通常就是浮点数，所以就从它下手优化。一般来说，Su,Sv 可以表示成分数的形式：Su = ( double )Dw / Sw; Sv = ( double )Dh / Sh其中 Dw, Dh 为目标图像的宽度和高度，Sw, Sh 为源图像的宽度和高度（因为都是整数，为求得浮点结果，需要进行类型转换）。将新的 Su, Sv 代入前面的变换公式和插值公式，可以导出新的插值公式：因为：b = 1 x * Sw % Dw / ( double )Dw; n = 1 y * Sh % Dh / ( double )Dh设：B = Dw x * Sw % Dw; N = Dh y * Sh
9、% Dh则：b = B / ( double )Dw; n = N / ( double )Dh用整数的 B，N 代替浮点的 b, n，转换插值公式：P = ( B * N * ( PA PB PC + PD ) + Dw * N * PB + DH * B * PC + ( Dw * Dh Dh * B Dw * N ) * PD ) / ( double )( Dw * Dh )这里最终结果 P 是浮点数，对其四舍五入即可得到结果。为完全消除浮点数，可以用这样的方法进行四舍五入：P = ( B * N * PD + Dw * Dh / 2 ) / ( Dw * Dh )这样，P 就直接是四
10、舍五入后的整数值，全部的计算都是整数运算了。简单优化后的代码如下：int _fastcall TResizeDlg:Stretch_Linear(Graphics:TBitmap * aDest, Graphics:TBitmap * aSrc)int sw = aSrc-Width - 1, sh = aSrc-Height - 1, dw = aDest-Width - 1, dh = aDest-Height - 1;int B, N, x, y;int nPixelSize = GetPixelSize( aDest-ixelFormat );BYTE * pLinePrev, *pL
11、ineNext;BYTE * pDest;BYTE * pA, *pB, *pC, *pD;for ( int i = 0; i ScanLine;y = i * sh / dh;N = dh - i * sh % dh;pLinePrev = ( BYTE * )aSrc-ScanLiney+;pLineNext = ( N = dh ) ? pLinePrev : ( BYTE * )aSrc-ScanLiney;for ( int j = 0; j =2s(x)是对 sin(x*pi)/x 的逼近（pi 是圆周率）最邻近插值（近邻取样法）、双线性内插值、三次卷积法 等插值算法对于旋转变换
12、、错切变换、一般线性变换 和 非线性变换 都适用。原理 线性插值并不难理解。以图像处理领域为例，我们的理想图像是均匀的分布在二维平面直角坐标系中的，任意给出一对坐标，就应该能够得到一个对应的颜色值，然而现实是残酷的，我们只能够用离散的点阵信息来近似表现图像。现在假设给定一对坐标（2.2, 4.0），想要得到这个坐标对应的颜色，那么比较简单的方法是用四舍五入方法来得到距离该点最近的像素，即像素(2, 4)的值来代替，这显然并不十分的精确，如果用这个方法进行图像放大，那么在比例较大的情况下就会出现明显的“马赛克”现象。对于上面的例子，更好的办法是把像素(2, 4)和像素(3, 4)的值按照一定的比
13、例混合。比例如何选取呢？很简单，离哪个像素近，哪个像素的比例就大些。那么（简单起见，后面均假设是灰度图），若设像素(2, 4)的值是 V_24，像素(3, 4)的值是 V_34，就可以得到：坐标(2.2, 4.0)的颜色值 V(2.2, 4.0) = V_24*(1-0.2)+V_34*0.2好，现在你已经懂得什么叫线性插值了!二次线性插值也就不难理解了。这次我们给的坐标不再是那么体贴了求坐标(2.2, 4.6)的颜色值。那么可以想到：可以先分别求出坐标(2.2, 4.0)和坐标(2.2, 5.0)的颜色值，然后用一次纵向的线型插值，就得到了：坐标(2.2, 4.0)的颜色值 V(2.2, 4
14、.0) = V_24*(1-0.2)+V_34*0.2坐标(2.2, 5.0)的颜色值 V(2.2, 5.0) = V_25*(1-0.2)+V_35*0.2坐标(2.2, 4.6)的颜色值 = V(2.2, 4.0)*(1-0.6)+V(2.2, 5.0)*0.6到这里，实际上我们已经得到了二次线性插值的计算公式，表述方便起见下面用符号来表示。设坐标(x, y)的相邻四个像素值分别为 p00, p01, p10, p11, 水平方向的比例系数为h0, h1, 垂直方向的比例系数 v0, v1（其中 h0+h1=1, v0+v1=1），那么用 bilinear interpolation 得到
15、：v(x, y) = (p00*h0+p01*h1)*v0 + (p10*h0+p11*h1)*v1 .(1.1)有了这个公式，已经可以编写出算法了，但是这个公式里有六次浮点乘法，如果是真彩图的话，则对每一像素都要有 18 次浮点乘法！这还不算生成浮点坐标值的时间（比如在旋转算法当中，每得到一对浮点坐标还要有若干次浮点运算）。优化学过一些线性代数知识的朋友可能已经注意到，公式(1.1)其实可以写成矩阵连乘的形式：|p00 p01| |h0|v(x, y) = |v0 v1|*| |*| .(1.2)|p10 p11| |h1|那么我们就可以利用矩阵相乘的运算法则来优化算法。首先，这里的运算瓶颈
16、是 v0, v1, h0, h1 这四个浮点值带来的，而实际上我们需要这么高的精度吗？p00, p01, p10, p11 以及我们的运算结果都是整数（对于我们的情况，是 0-255 之间的整数）。也就是说，其实把我们的结果最后赋值给 v(x, y)时，小数部分已经被截掉了，我们根本用不到那么高的精度！那么我们可以尝试用整数乘法代替浮点乘法。比如，令 V0 = (int)(v0*65536.0+0.5)，V1 = 65536-V0，H0 = (int)(h0*65536.0+0.5), H1 = 65536-H0，那么有： |p00 p01| |H0|v(x, y)*65536*65536 = |V0 V1|*| |*| .(1.
