快速离散化双线性插值算法

1、-3787-0引言数字图像处理的特点之一是处理的数据量大1,对存储空间和处理速度提出了很高的要求,尤其在实时性要求很高的场合,如TMS320C6201实时图像处理系统2。实时图像处理系统的综合性能取决于算法复杂度、硬件和软件实现的技术水平。其中,算法复杂度是综合性能根本的制约因素,如何降低算法复杂度又不不会对数字图像处理的质量产生大的影响是一个研究热点3-4。最近邻点法、双线性插值算法是广泛应用于数字图像处理的空域变换,如图像旋转5-6、放缩、几何失真校正等方面的像素插值算法。在图像旋转变换中,最临近插值算法是对于通过反向变换得到的一个浮点坐标,对其进行简单的取整,得到一个整数坐标,这个整数坐

2、标对应的像素值就是目的像素的像素值。最近邻插值算法的定位误差最大是半个像素。这种误差在物体具有直线边界时就会显现出来,在变换后可能会呈现阶梯状。其优点是计算速度快7。由于只取一个像素值,因此不会产生模糊,最邻近插值简单、计算量小。但得到的图像质量不高,会产生不连续现象。双线性插值算法的实质是对4个相邻像素值加权平均得到像素值,因此会产生模糊。它比最近邻点法复杂,计算量大,但变换后的图像质量高,连续性好。为了得到双线性插值算法的图像高质量和最近邻点法计算速度快和不模糊的优点,提出了离散化双线性插值算法。1双线性插值算法双线性插值又称一阶插值,是利用点,周围4个邻点(P 00(0,0,P 10(1

3、,0,P 01(0,1,P 11(1,1的像素值f 在x,y 两个方向上作线性内插(如图1所示。由于通过4点确定一个平面是一个过约束问题,所以在一个矩形栅格上进行的一阶插值就需要用到双线性函数。令,为两个变量的函数,其在单位正方形顶点(P 00(0,0,P 10(1,0,P 01(0,1,P 11(1,1是相邻4个像素的中收稿日期:2007-01-25E-mail :Chenl基金项目:广东省科技厅科研基金项目(2003C32401。作者简介:陈良(1969-,男,辽宁灯塔人,博士研究生,工程师,研究方向为计算机图形学、计算机网络及网络安全;高成敏(1974-,女,辽宁新民人,硕士研究生,实验

4、师,研究方向为计算机图形学、信息系统开发。快速离散化双线性插值算法陈良1,2,高成敏1,2(1.广东警官学院计算机系,广东广州510232;2.华南理工大学计算机科学与工程学院,广东广州510640摘要:双线性插值算法在数字图像处理中有广泛的应用。它具有比最近邻点法更好的连续性,但计算速度慢。为提高其计算速度,提出了离散化双线性插值算法。把像素分割成子像素,用双线性插值函数计算子像素中心坐标处的像素值,可以得到每一个子像素的卷积函数C ,用C 来代替双线性插值函数。理论分析表明离散化算法减少了加法和乘法的浮点运算次数。通过图像旋转实验表明该算法与双线性插值算法相比计算速度有较大的提高,连续性略

5、有损失,图像质量基本相同。关键词:像素分割;离散化;双线性插值;最近邻点法;图像旋转中图法分类号:TP391.41文献标识码:A文章编号:1000-7024(200715-3787-04Fast discrete bilinear interpolation algorithmCHEN Liang 1,2,GAO Cheng-min 1,2(1.Department of Computer,Guangdong Police Officers College,Guangzhou 510232,China;2.College of Computer Science and Engineering,

6、South China University of Technology,Guangzhou 510640,China Abstract :Bilinear interpolation is widely used to process digital image.Its continuity is better than Nearest neighbor interpolation,but is time-consuming.In order to speed up,a discrete bilinear interpolation algorithm is proposed.First,p

7、ixel is cut into 3x3sub-pixel.Then the center value of each sub-pixel with bilinear interpolation function is calculated,we can get a convolution function C related with each sub-pixel,the function C can be a substitute of bilinear interpolation.Theoretical analyses show that the discrete algorithm

8、decreases the times of floating addition and floating multiplication.Experiments of image rotation show that the discrete algorithm improve the per-formance more greatly than that of bilinear interpolation.The quality of image rotated by the discrete algorithm is almost equal to that by the bilinear

9、 interpolation except for a little loss of continuity.Key words :pixel segmentation;discrete;bilinear interpolation;nearest neighbor interpolation;image rotation2007年8月计算机工程与设计Aug.2007第28卷第15期Vol.28No.15Computer Engineering and Design-3788-心点的值(f (0,0,f (1,0,f (0,1,f (1,1已知。通过插值得到正方形内任意点,的像素值,。由下面双线

10、性方程(1来定义的一个双曲抛物面与4 个已知点的拟合, = + +(14 个系数,由已知的4个顶点的值f (0,0,f (1,0,f (0,1,f (1,1代入式(1并解方程组得到。另外一个简单算法可用于理解双线性插值函数,并使之与4个顶点的f 值拟合。在y 方向f (0,0,f (0,1之间进行线性插值, 可得 + +,=(4将式(2、式(3代入式(4,展开等式并合并同类项, 可得,=+ +(5双线性插值法对在正方形区域P 00(0,0,P 10(1,0,P 11(1,1,P 01(0,1内的点, ,进行浮点计算,计算量大,但变换后图像质量高,不会出现像素值不连续的情况。由于双线性插值具有低

11、通滤波器的性质,使高频分量受损,所以可能会使图像轮廓在一定程度上变得模糊。2双线性插值算法离散化2.1像素分割和离散化处理图2是像素分割及双线性插值离散化原理图。P i (i=1,9是33个像素,其中像素P 5(正方形ABCD ,中心是G ,被等分为3x3的子像素i (i=1,9,它们的中心分别是O i (i=1,9。设A 点坐标为(I 1,J 1(I 1,J 1为整数,以图像的左下角为坐标原点,像素P 5(ABCD 内任一点P 的全局坐标为:(I 1+u,J 1+v ,u,v 0,1。点I,J,K,L 分别是AB ,BC ,CD ,DA 边的中点。EFGH 是和像素大小相等的正方形。以A 点

12、为坐标原点的子像素i (i=1, (9的中心点O i (i=1,9的局部坐标分别为:1626,1 ,5646,3,3666,3;1686,5 ,56=1, (9 中心点 , 则用卷积函数3 6,取像素P 1,P 2,P 4,P 5的中心点E ,F ,H ,G 分别作为双线性插值中的点P 00,P 10,P 01,P 11(如图1所示,即f p00=f p1,f p10=f p2,f p01=f p4,f p11=f p5。代入式(5得到区域AIGL 内点P 的灰度双线性插值公式, = + +2 6,P (u,v 用O 1(1/6,1/6代替, 则 =12=2=12=21, = 2 223 +9

13、 6+ 6+4+9(7如果P (u,v 子像素2,即 ,6 62 =32=1 ,+0. 56+13。 将离散化的点2, = 1+ 2123 3+ 2+2+3(8如果P (u,v 子像素4,即 ,223 =12=2=12=1 。将离散化的点 ,1, x-3789 -, = 2 1+23 2+ 3+2+3(9如果P (u,v 子像素5,即 ,6 66 6,P (u,v 用O 5(3/6,3/6代替, 则 =32=1 ,+0. 56+15, = 1+ 1+1 1+ + + +6 06,取像素P 2,P 3,P 5,P 6的中心点分别作为双线性插值中的点P 00,P 10,P 01,P 11(如图1所

14、示,即f p00=f p2,f p10=f p3,f p01=f p5,f p11=f p6。代入式(5得到区域BJGI 内点P 的灰度 双线性插值公式, = +3,= 1(11 3(12(3当任意一点P (u,v (以A 为坐标原点区域GKDL 时,即 ,331,取像素P 4,P 5,P 7,P 8的中心点分别作为双线性插值中的点P 00,P 10,P 01,P 11(如图1所示,即f p00=f p4,f p10=f p5,f p01=f p7,f p11=f p8。代入式(5得到区域GKDL 内点P 的灰度 双线性插值公式, = +7,= 1(13 3(14(4当任意一点P (u,v (

15、以A 为坐标原点区域GJCK 时,即 ,631,取像素P 5,P 6,P 8,P 9的中心点分别作为双线性插值中的点P 00,P 10,P 01,P 11(如图1所示,即f p00=f p5,f p10=f p6,f p01=f p8,f p11=f p9。代入式(5得到区域GJCK 内点P 的灰度 双线性插值公式, = +9,= 1(152.2计算量比较分析2.2.1双线性插值的计算量由式(5知每像素计算量:浮点加FA=8次,浮点乘FM=4次。2.2.2离散化双线性插值的计算量设点P 落入每个子像素的概率相等,即p i =1/9(i=1,9。并且P 点只能属于某一个子像素。设点P 的全局坐标

16、为(I 1+u,J 1+v ,(m,n 为P 点所属于的子像素的行列值,其中m=0,1,2;n=0,1,2。确定P (u,v 落入子像素的算法如表1所示,其中if 和else if 判断相当于一次浮点减法,例如,u=1/3等价于u-0.33333330。P (u,v 落入P 1(m=0,n=0需2次判断,P (u,v 落入P 2(m=0,n=1需3次判断,依此类推,如表2所示。 浮点数减法计算量总和为9=30 =9= 16=1 99=16 =9=83实验及结果分析分别用最近邻点法、双线性插值法、本文插值法、高斯模板旋转算法对图3(a进行多次旋转,记录旋转所用的时间(ms。比较旋转后的图像质量和

17、计算时间的比值。图3(a是旋转前的图像,图3(b是最近邻点插值旋转9次*10度的图像,图3(c是双线性插值旋转9次*10度的图像,图3(d是本文插值旋转9*10度,图3(e是Gauss模板8插值旋转9*10度。因为图像旋转90度是不会产生失真,为了便于观察,将图3(b,3(c,3(d,3 (e反向旋转了90度。观察发现双线性插值法和本文插值法旋转后的图像最清晰,二者没有大的区别,由于离散化使图像的连续性略有损失。从运行时间比较,表4是旋转9次*10度的计时结果。D: B表明采用离散化算法与双线性插值的图像旋转总的时间比,是坐标旋转的几何变换和采用离散化算法或双线性插值算法进行灰度插值的时间和。

18、Nearest的图像旋转时间基本用于坐标旋转的几何变换上,因此,B-N基本可以看作是双线性插值算法进行灰度插值的时间;D-N基本可以看作是离散化算法进行灰度插值的时间。D-N:B-N是两者灰度插值计算时间的比值,也是本节理论上所比较的时间。从表中可计算出采用离散化算法进行图像旋转比双线性插值的图像旋转总体性能提高36%,灰度插值时间减少53%。与本节理论分析结果基本吻合。表中同一算法计算时间不同是因为旋转使图像大小发生了变化。4结束语通过对双线性插值算法进行离散化,保持了双线性插值算法的主要特性,因此变换图像的质量没有大的损害。而由于离散化算法降低了双线性插值算法的复杂度,因而使灰度插值的时间

19、降低了,同时提高了采用该算法进行灰度插的图像旋转操作的综合性能。该算法也可应用于其它空域变换的灰度插值,如图像放缩、几何失真变换等。参考文献:1郎锐.数字图像处理学Visual C+实现M.北京:希望电子出版社,2002.2刘松涛,周晓东,沈同圣.基于TMS320C6201的实时图像处理系统J.计算机工程,2005,31(7:214-216.3Gribbon K T,Bailey D G.A novel approach to real-time bilinearinterpolationC.Second IEEE International Workshop on Elec-tronic Design,Test and Applications,2004:126-131.4Uthaichana P,Leelarasmee E.A pipelined bilinear interpolationfor real time video image expansionC.IEEE Region10Con-feren