快速離散化雙線性插值算法

1、-3787-0引言數(shù)字圖像處理的特點之一是處理的數(shù)據(jù)量大1,對存儲空間和處理速度提出了很高的要求,尤其在實時性要求很高的場合,如TMS320C6201實時圖像處理系統(tǒng)2。實時圖像處理系統(tǒng)的綜合性能取決于算法復(fù)雜度、硬件和軟件實現(xiàn)的技術(shù)水平。其中,算法復(fù)雜度是綜合性能根本的制約因素,如何降低算法復(fù)雜度又不不會對數(shù)字圖像處理的質(zhì)量產(chǎn)生大的影響是一個研究熱點3-4。最近鄰點法、雙線性插值算法是廣泛應(yīng)用于數(shù)字圖像處理的空域變換,如圖像旋轉(zhuǎn)5-6、放縮、幾何失真校正等方面的像素插值算法。在圖像旋轉(zhuǎn)變換中,最臨近插值算法是對于通過反向變換得到的一個浮點坐標(biāo),對其進行簡單的取整,得到一個整數(shù)坐標(biāo),這個整數(shù)坐

2、標(biāo)對應(yīng)的像素值就是目的像素的像素值。最近鄰插值算法的定位誤差最大是半個像素。這種誤差在物體具有直線邊界時就會顯現(xiàn)出來,在變換后可能會呈現(xiàn)階梯狀。其優(yōu)點是計算速度快7。由于只取一個像素值,因此不會產(chǎn)生模糊,最鄰近插值簡單、計算量小。但得到的圖像質(zhì)量不高,會產(chǎn)生不連續(xù)現(xiàn)象。雙線性插值算法的實質(zhì)是對4個相鄰像素值加權(quán)平均得到像素值,因此會產(chǎn)生模糊。它比最近鄰點法復(fù)雜,計算量大,但變換后的圖像質(zhì)量高,連續(xù)性好。為了得到雙線性插值算法的圖像高質(zhì)量和最近鄰點法計算速度快和不模糊的優(yōu)點,提出了離散化雙線性插值算法。1雙線性插值算法雙線性插值又稱一階插值,是利用點,周圍4個鄰點(P 00(0,0,P 10(1

3、,0,P 01(0,1,P 11(1,1的像素值f 在x,y 兩個方向上作線性內(nèi)插(如圖1所示。由于通過4點確定一個平面是一個過約束問題,所以在一個矩形柵格上進行的一階插值就需要用到雙線性函數(shù)。令,為兩個變量的函數(shù),其在單位正方形頂點(P 00(0,0,P 10(1,0,P 01(0,1,P 11(1,1是相鄰4個像素的中收稿日期:2007-01-25E-mail :Chenl基金項目:廣東省科技廳科研基金項目(2003C32401。作者簡介:陳良(1969-,男,遼寧燈塔人,博士研究生,工程師,研究方向為計算機圖形學(xué)、計算機網(wǎng)絡(luò)及網(wǎng)絡(luò)安全;高成敏(1974-,女,遼寧新民人,碩士研究生,實驗

4、師,研究方向為計算機圖形學(xué)、信息系統(tǒng)開發(fā)?？焖匐x散化雙線性插值算法陳良1,2,高成敏1,2(1.廣東警官學(xué)院計算機系,廣東廣州510232;2.華南理工大學(xué)計算機科學(xué)與工程學(xué)院,廣東廣州510640摘要:雙線性插值算法在數(shù)字圖像處理中有廣泛的應(yīng)用。它具有比最近鄰點法更好的連續(xù)性,但計算速度慢。為提高其計算速度,提出了離散化雙線性插值算法。把像素分割成子像素,用雙線性插值函數(shù)計算子像素中心坐標(biāo)處的像素值,可以得到每一個子像素的卷積函數(shù)C ,用C 來代替雙線性插值函數(shù)。理論分析表明離散化算法減少了加法和乘法的浮點運算次數(shù)。通過圖像旋轉(zhuǎn)實驗表明該算法與雙線性插值算法相比計算速度有較大的提高,連續(xù)性略

5、有損失,圖像質(zhì)量基本相同。關(guān)鍵詞:像素分割;離散化;雙線性插值;最近鄰點法;圖像旋轉(zhuǎn)中圖法分類號:TP391.41文獻標(biāo)識碼: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月計算機工程與設(shè)計Aug.2007第28卷第15期Vol.28No.15Computer Engineering and Design-3788-心點的值(f (0,0,f (1,0,f (0,1,f (1,1已知。通過插值得到正方形內(nèi)任意點,的像素值,。由下面雙線

10、性方程(1來定義的一個雙曲拋物面與4 個已知點的擬合, = + +(14 個系數(shù),由已知的4個頂點的值f (0,0,f (1,0,f (0,1,f (1,1代入式(1并解方程組得到。另外一個簡單算法可用于理解雙線性插值函數(shù),并使之與4個頂點的f 值擬合。在y 方向f (0,0,f (0,1之間進行線性插值, 可得 + +,=(4將式(2、式(3代入式(4,展開等式并合并同類項, 可得,=+ +(5雙線性插值法對在正方形區(qū)域P 00(0,0,P 10(1,0,P 11(1,1,P 01(0,1內(nèi)的點, ,進行浮點計算,計算量大,但變換后圖像質(zhì)量高,不會出現(xiàn)像素值不連續(xù)的情況。由于雙線性插值具有低

11、通濾波器的性質(zhì),使高頻分量受損,所以可能會使圖像輪廓在一定程度上變得模糊。2雙線性插值算法離散化2.1像素分割和離散化處理圖2是像素分割及雙線性插值離散化原理圖。P i (i=1,9是33個像素,其中像素P 5(正方形ABCD ,中心是G ,被等分為3x3的子像素i (i=1,9,它們的中心分別是O i (i=1,9。設(shè)A 點坐標(biāo)為(I 1,J 1(I 1,J 1為整數(shù),以圖像的左下角為坐標(biāo)原點,像素P 5(ABCD 內(nèi)任一點P 的全局坐標(biāo)為:(I 1+u,J 1+v ,u,v 0,1。點I,J,K,L 分別是AB ,BC ,CD ,DA 邊的中點。EFGH 是和像素大小相等的正方形。以A 點

12、為坐標(biāo)原點的子像素i (i=1, (9的中心點O i (i=1,9的局部坐標(biāo)分別為:1626,1 ,5646,3,3666,3;1686,5 ,56=1, (9 中心點 , 則用卷積函數(shù)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得到區(qū)域AIGL 內(nèi)點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得到區(qū)域BJGI 內(nèi)點P 的灰度 雙線性插值公式, = +3,= 1(11 3(12(3當(dāng)任意一點P (u,v (以A 為坐標(biāo)原點區(qū)域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得到區(qū)域GKDL 內(nèi)點P 的灰度 雙線性插值公式, = +7,= 1(13 3(14(4當(dāng)任意一點P (u,v (

15、以A 為坐標(biāo)原點區(qū)域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得到區(qū)域GJCK 內(nèi)點P 的灰度 雙線性插值公式, = +9,= 1(152.2計算量比較分析2.2.1雙線性插值的計算量由式(5知每像素計算量:浮點加FA=8次,浮點乘FM=4次。2.2.2離散化雙線性插值的計算量設(shè)點P 落入每個子像素的概率相等,即p i =1/9(i=1,9。并且P 點只能屬于某一個子像素。設(shè)點P 的全局坐標(biāo)

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 判斷相當(dāng)于一次浮點減法,例如,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所示。 浮點數(shù)減法計算量總和為9=30 =9= 16=1 99=16 =9=83實驗及結(jié)果分析分別用最近鄰點法、雙線性插值法、本文插值法、高斯模板旋轉(zhuǎn)算法對圖3(a進行多次旋轉(zhuǎn),記錄旋轉(zhuǎn)所用的時間(ms。比較旋轉(zhuǎn)后的圖像質(zhì)量和

17、計算時間的比值。圖3(a是旋轉(zhuǎn)前的圖像,圖3(b是最近鄰點插值旋轉(zhuǎn)9次*10度的圖像,圖3(c是雙線性插值旋轉(zhuǎn)9次*10度的圖像,圖3(d是本文插值旋轉(zhuǎn)9*10度,圖3(e是Gauss模板8插值旋轉(zhuǎn)9*10度。因為圖像旋轉(zhuǎn)90度是不會產(chǎn)生失真,為了便于觀察,將圖3(b,3(c,3(d,3 (e反向旋轉(zhuǎn)了90度。觀察發(fā)現(xiàn)雙線性插值法和本文插值法旋轉(zhuǎn)后的圖像最清晰,二者沒有大的區(qū)別,由于離散化使圖像的連續(xù)性略有損失。從運行時間比較,表4是旋轉(zhuǎn)9次*10度的計時結(jié)果。D: B表明采用離散化算法與雙線性插值的圖像旋轉(zhuǎn)總的時間比,是坐標(biāo)旋轉(zhuǎn)的幾何變換和采用離散化算法或雙線性插值算法進行灰度插值的時間和。

18、Nearest的圖像旋轉(zhuǎn)時間基本用于坐標(biāo)旋轉(zhuǎn)的幾何變換上,因此,B-N基本可以看作是雙線性插值算法進行灰度插值的時間;D-N基本可以看作是離散化算法進行灰度插值的時間。D-N:B-N是兩者灰度插值計算時間的比值,也是本節(jié)理論上所比較的時間。從表中可計算出采用離散化算法進行圖像旋轉(zhuǎn)比雙線性插值的圖像旋轉(zhuǎn)總體性能提高36%,灰度插值時間減少53%。與本節(jié)理論分析結(jié)果基本吻合。表中同一算法計算時間不同是因為旋轉(zhuǎn)使圖像大小發(fā)生了變化。4結(jié)束語通過對雙線性插值算法進行離散化,保持了雙線性插值算法的主要特性,因此變換圖像的質(zhì)量沒有大的損害。而由于離散化算法降低了雙線性插值算法的復(fù)雜度,因而使灰度插值的時間

19、降低了,同時提高了采用該算法進行灰度插的圖像旋轉(zhuǎn)操作的綜合性能。該算法也可應(yīng)用于其它空域變換的灰度插值,如圖像放縮、幾何失真變換等。參考文獻:1郎銳.數(shù)字圖像處理學(xué)Visual C+實現(xiàn)M.北京:希望電子出版社,2002.2劉松濤,周曉東,沈同圣.基于TMS320C6201的實時圖像處理系統(tǒng)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