线插值算法实现图像缩放旋转祥解.doc_第1页
线插值算法实现图像缩放旋转祥解.doc_第2页
线插值算法实现图像缩放旋转祥解.doc_第3页
线插值算法实现图像缩放旋转祥解.doc_第4页
线插值算法实现图像缩放旋转祥解.doc_第5页
已阅读5页,还剩1页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

线性插值算法实现图像缩放、旋转详解 这是一篇关于图形处理线性插值算法细节的文章,转载此文的目的在于能给那些对图像处理算法感兴趣的网友一些启示,对于大量的入门网友来说,这样的文章或许有些让人眼晕,但我相信哪怕只理解一些表皮的图像处理算法知识,以后在使用软件处理图片时便能做“心里有数”,还是有所助宜的。 在Windows中做过图像方面程序的人应该都知道Windows的GDI有一个API函数:StretchBlt,对应在VCL中是TCanvas类的StretchDraw方法。它可以很简单地实现图像的缩放操作。但问题是它是用了速度最快,最简单但效果也是最差的“最近邻域法”,虽然在大多数情况下,它也够用了,但对于要求较高的情况就不行了。不久前做了一个小玩意儿,用于管理我用DC拍的一堆照片,其中有一个插件提供了缩放功能,目前的版本就是用了StretchDraw,有时效果不能令人满意,我一直想加入两个更好的:线性插值法和三次样条法。经过研究发现三次样条法的计算量实在太大,不太实用,所以决定就只做线性插值法的版本了。从数字图像处理的基本理论,我们可以知道:图像的变形变换就是源图像到目标图像的坐标变换。简单的想法就是把源图像的每个点坐标通过变形运算转为目标图像的相应点的新坐标,但是这样会导致一个问题就是目标点的坐标通常不会是整数,而且像放大操作会导致目标图像中没有被源图像的点映射到,这是所谓“向前映射”方法的缺点。所以一般都是采用“逆向映射”法。但是逆向映射法同样会出现映射到源图像坐标时不是整数的问题。这里就需要“重采样滤波器”。这个术语看起来很专业,其实不过是因为它借用了电子信号处理中的惯用说法(在大多数情况下,它的功能类似于电子信号处理中的带通滤波器),理解起来也不复杂,就是如何确定这个非整数坐标处的点应该是什么颜色的问题。前面说到的三种方法:最近邻域法,线性插值法和三次样条法都是所谓的“重采样滤波器”。所谓“最近邻域法”就是把这个非整数坐标作一个四舍五入,取最近的整数点坐标处的点的颜色。而“线性插值法”就是根据周围最接近的几个点(对于平面图像来说,共有四点)的颜色作线性插值计算(对于平面图像来说就是二维线性插值)来估计这点的颜色,在大多数情况下,它的准确度要高于最近邻域法,当然效果也要好得多,最明显的就是在放大时,图像边缘的锯齿比最近邻域法小非常多。当然它同时还带业个问题:就是图像会显得比较柔和。这个滤波器用专业术语来说(呵呵,卖弄一下偶的专业_)叫做:带阻性能好,但有带通损失,通带曲线的矩形系数不高。至于三次样条法我就不说了,复杂了一点,可自行参考数字图像处理方面的专业书籍,如本文的参考文献。再来讨论一下坐标变换的算法。简单的空间变换可以用一个变换矩阵来表示:x,y,w=u,v,w*T其中:x,y为目标图像坐标,u,v为源图像坐标,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就这么简单。有了上面三个方面的准备,就可以开始编写代码实现了。思路很简单:首先用两重循环遍历目标图像的每个点坐标,通过上面的变换式(注意:因为是用逆向映射,相应的变换式应该是: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属性)。P为(u,v)点的插值颜色,即(x,y)点的近似颜色。这段代码我就不写了,因为它的效率实在太低:要对目标图像的每一个点的RGB进行上面那一串复杂的浮点运算。所以一定要进行优化。对于VCL应用来说,有个比较简单的优化方法就是用TBitmap的ScanLine属性,按行进行处理,可以避免Pixels的像素级操作,对性能可以有很大的改善。这已经是算是用VCL进行图像处理的基本优化常识了。不过这个方法并不总是管用的,比如作图像旋转的时候,这时需要更多的技巧。无论如何,浮点运算的开销都是比整数大很多的,这个也是一定要优化掉的。从上面可以看出,浮点数是在变换时引入的,而变换参数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 % 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就直接是四舍五入后的整数值,全部的计算都是整数运算了。简单优化后的代码如下: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, *pLineNext;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 = dw; +j )x = j * sw / dw * nPixelSize;B = dw - j * sw % dw;pA = pLinePrev + x;pB = pA + nPixelSize;pC = pLineNext + x;pD = pC + nPixelSize;if ( B = dw )pB = pA;pD = pC;for ( int k = 0; k nPixelSize; +k )*pDest+ = ( BYTE )( int )( B * N * ( *pA+ - *pB - *pC + *pD ) + dw * N * *pB+ dh * B * *pC+ + ( dw * dh - dh * B - dw * N ) * *pD+ dw * dh / 2 ) / ( dw * dh );return 0;应该说还是比较简洁的。因为宽度高度都是从0开始算,所以要减一,GetPixelSize是根据PixelFormat属性来判断每个像素有多少字节,此代码只支持24或32位色的情况(对于15或16位色需要按位拆开因为不拆开的话会在计算中出现不期望的进位或借位,导致图像颜色混乱处理较麻烦;对于8位及8位以下索引色需要查调色板,并且需要重索引,也很麻烦,所以都不支持;但8位灰度图像可以支持)。另外代码中加入一些在图像边缘时防止访问越界的代码。通过比较,在PIII-733的机器上,目标图像小于1024x768的情况下,基本感觉不出速度比StretchDraw有明显的慢(用浮点时感觉比较明显)。效果也相当令人满意,不论是缩小还是放大,图像质量比StretchDraw方法有明显提高。不过由于采用了整数运算,有一个问题必须加以重视,那就是溢出的问题:由于式中的分母是dw * dh,而结果应该是一个Byte即8位二进制数,有符号整数最大可表示31位二进制数,所以dw * dh的值不能超过23位二进制数,即按2:1的宽高比计算目标图像分辨率不能超过4096*2048。当然这个也是可以通过用无符号数(可以增加一位)及降低计算精度等方法来实现扩展的,有兴趣的朋友可以自己试试。当然这段代码还远没有优化到极致,而且还有很多问题没有深入研究,比如抗混叠(anti-aliasing)等,有兴趣的朋友可以自行参考相关书籍研究。(转自:迪派影像)实践已证明,插值算法对于缩放比例较小的情况是完全可以接受的,令人信服的。一般的,缩小0.5倍以上或放大3.0倍以下,对任何图像都是可以接受的。最邻近插值(近邻取样法):最临近插值的的思想很简单。对于通过反向变换得到的的一个浮点坐标,对其进行简单的取整,得到一个整数型坐标,这个整数型坐标对应的像素值就是目的像素的像素值,也就是说,取浮点坐标最邻近的左上角点(对于dib是右上角,因为它的扫描行是逆序存储的)对应的像素值。可见,最邻近插值简单且直观,但得到的图像质量不高。(我想易语言的位图支持库中的图象旋转命令就是这种原理!)双线性内插值:对于一个目的像素,设置坐标通过反向变换得到的浮点坐标为(i+u,j+v),其中i、j均为非负整数,u、v为0,1)区间的浮点数,则这个像素得值 f(i+u,j+v) 可由原图像中坐标为 (i,j)、(i+1,j)、(i,j+1)、(i+1,j+1)所对应的周围四个像素的值决定,即:f(i+u,j+v) = (1-u)(1-v)f(i,j) + (1-u)vf(i,j+1) + u(1-v)f(i+1,j) + uvf(i+1,j+1)其中f(i,j)表示源图像(i,j)处的的像素值,以此类推这就是双线性内插值法。双线性内插值法计算量大,但缩放后图像质量高,不会出现像素值不连续的的情况。由于双线性插值具有低通滤波器的性质,使高频分量受损,所以可能会使图像轮廓在一定程度上变得模糊三次卷积法能够克服以上两种算法的不足,计算精度高,但计算亮大,他考虑一个浮点坐标(i+u,j+v)周围的16个邻点,目的像素值f(i+u,j+v)可由如下插值公式得到:f(i+u,j+v) = a * * ca= s(u + 1) s(u + 0) s(u - 1) s(u - 2) f(i-1, j-1) f(i-1, j+0) f(i-1, j+1) f(i-1, j+2) = f(i+0, j-1) f(i+0, j+0) f(i+0, j+1) f(i+0, j+2) f(i+1, j-1) f(i+1, j+0) f(i+1, j+1) f(i+1, j+2) f(i+2, j-1) f(i+2, j+0) f(i+2, j+1) f(i+2, j+2) s(v + 1) c= s(v + 0) s(v - 1) s(v - 2) 1-2*abs(x)2+abs(x)3 , 0=abs(x)1s(x)= 4-8*abs(x)+5*abs(x)2-abs(x)3 , 1=abs(x)=2s(x)是对 sin(x*pi)/x 的逼近(pi是圆周率)最邻近插值(近邻取样法)、双线性内插值、三次卷积法 等插值算法对于旋转变换、错切变换、一般线性变换 和 非线性变换 都适用。原理 线性插值并不难理解。以图像处理领域为例,我们的理想图像是均匀的分布在二维平面直角坐标系中的,任意给出一对坐标,就应该能够得到一个对应的颜色值,然而现实是残酷的,我们只能够用离散的点阵信息来近似表现图像。现在假设给定一对坐标(2.2, 4.0),想要得到这个坐标对应的颜色,那么比较简单的方法是用四舍五入方法来得到距离该点最近的像素,即像素(2, 4)的值来代替,这显然并不十分的精确,如果用这个方法进行图像放大,那么在比例较大的情况下就会出现明显的“马赛克”现象。对于上面的例子,更好的办法是把像素(2, 4)和像素(3, 4)的值按照一定的比例混合。比例如何选取呢?很简单,离哪个像素近,哪个像素的比例就大些。那么(简单起见,后面均假设是灰度图),若设像素(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.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得到: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|那么我们就可以利用矩阵相乘的运算法则来优化算法。首先,这里的运算瓶颈是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.3) |p10 p11|

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论