基于幾何分類的自適應(yīng)圖像插值算法*

梁 云，朱為鵬，李 崢，3

(1.華南農(nóng)業(yè)大學(xué) 信息學(xué)院，廣東 廣州 510642;2.中山大學(xué) 信息科學(xué)與技術(shù)學(xué)院∥數(shù)字家庭教育部重點實驗室，廣東 廣州 510006;3.廣東工業(yè)大學(xué) 計算機(jī)學(xué)院，廣東 廣州 510090;4.深圳市數(shù)字生活網(wǎng)絡(luò)與內(nèi)容服務(wù)重點實驗室，廣東 深圳 518057;5.中山大學(xué) 深圳研究院，廣東 深圳 518057)

隨著媒體技術(shù)的發(fā)展，數(shù)字圖像越來越多應(yīng)用到生活和工作的各個領(lǐng)域。數(shù)字電視 (Digital TV)，移動電視 (Mobile TV)，網(wǎng)絡(luò)電視 (Online TV)等的到來，人們對高分辨率圖像的需求越來越迫切。與低分辨率圖像相比，高分辨圖像像素密度高，能提供更多的細(xì)節(jié)信息，而這些細(xì)節(jié)是實際應(yīng)用所不可或缺的。目前，大量現(xiàn)存的圖像攝取設(shè)備只能獲取低分辨率圖像，不能滿足人們需要。更換這些設(shè)備耗費(fèi)巨大，不易實現(xiàn)，且分辨率也不能無限制提高。一種有效獲取高分辨率圖像的方法是插值低分辨圖像?，F(xiàn)有方法的主要缺陷是不能很好的保持圖像邊緣，插值后圖像上產(chǎn)生鋸齒。

本文提出了一種基于幾何分類的自適應(yīng)圖像插值方法。算法分3步:首先將低分辨率圖像賦值給高分辨率圖像部分像素點;然后劃分高分辨率圖像已知像素點所構(gòu)成的插值單元;最后，對不同幾何類型插值單元的未知像素分別求解，獲取高分辨率圖像。

本文的主要貢獻(xiàn)有以下2點。其一是:根據(jù)初步賦值后的高分辨率圖像的已知像素點和未知像素點的相對位置關(guān)系，將插值未知像素點的插值單元分為矩形插值單元和菱形插值單元，保證插值圖像的邊緣走向和寬度，提高插值圖像的質(zhì)量。其二是:從8個方向分別對兩種插值單元進(jìn)行幾何分類，最后再根據(jù)每個像素點所屬的相關(guān)插值單元進(jìn)行分類插值，保證圖像邊緣的尖銳特征，提高插值圖像的質(zhì)量。

1 相關(guān)工作

近幾年，通過插值獲取高分辨率圖像已成為一個研究的熱點。主要方法可分為兩大類，基于圖形學(xué)的插值方法 (如:樣條插值等)和基于統(tǒng)計的插法方法。

插值圖像的邊緣保持決定了插值圖像的質(zhì)量。人們越來越多的通過研究分析圖像的統(tǒng)計特性來保持圖像的邊緣進(jìn)而插值圖像［1－4］。Li等［1］提出基于邊緣的插值，通過保持低分辨圖像的局部幾何特征來提高插值圖像質(zhì)量，但速度慢。Morse等［2］建議基于等高線插值圖像。Fattal［3］研究低分辨率圖像邊緣的統(tǒng)計特性，并將特征強(qiáng)加于插值后的圖像來提高放大圖像質(zhì)量，缺陷是統(tǒng)計特征的微小變化將很大的程度上影響圖像效果。Sun等［5］則對圖像邊緣的梯度變化進(jìn)行研究，并將梯度變化信息附加在高分辨率圖像，該方法雖然能夠在一定程度上提高插值圖像的質(zhì)量，但是受圖像噪聲的影響比較嚴(yán)重。

此外，Battiato等［6］建議用邊緣自適應(yīng)方法插值。實驗證明基于等高線或邊緣自適應(yīng)的方法對于去除圖像的鋸齒效果比較有效。但仍有不足，特別是對小面積重復(fù)區(qū)域的處理。Shan等［7］建議用卷積處理的方法插值視頻、圖像，可以滿足實時性要求。Kopf等［8］將聯(lián)合雙邊濾波器運(yùn)用到了色調(diào)映射等圖像處理中，通過高分辨圖像的引導(dǎo)信息提高插值圖像的效果。Sajjad等［9］建議一種新的圖像插值方法根據(jù)已知像素點的鄰結(jié)點分類已知像素點。但是他的方法只是水平和垂直的方向，對角線情況沒有處理。事實上，大部分邊的方向都是對角線方向。因為缺乏對對角線因素的考慮，Muhammad方法中有些未知像素點由與它距離較遠(yuǎn)的已知像素點決定。因此，某系已知像素間的相關(guān)信息被丟失，從而引入鋸齒效應(yīng)。

基于圖形學(xué)的插值方法主要采用樣條插值圖像。Unser等［10］提出了基于樣條的插值，Keys等［11］建議用三次卷積放大圖像。它們?nèi)毕菔遣逯岛髨D像變模糊。

2 幾何分類插值單元

若插值低分率圖像S(M×N)得到高分辨圖像T(2M ×2N)。首先設(shè)定所有T2i，2j像素點均來自于Si，j，i，j為整數(shù)，圖1(a)黑色點，我們將這些像素點稱為已知像素點。因此，圖像插值的關(guān)鍵是如何確定Ti，j像素點的值，且i，j不同時為偶數(shù)，圖1(a)中白色點，設(shè)為未知像素點?；趲缀畏诸惖姆较蜃赃m應(yīng)圖像插值首先算法首先根據(jù)高分辨圖像中已知像素點和未知像素點間的相對位置關(guān)系，將未知像素點分成為3種，分別用圖1(a)中的1，2，3描述，并把它們插值單元分為矩形插值單元和菱形插值單元，再根據(jù)8個方向的零交叉點對插值單元進(jìn)行幾何分類，最后對不同類型插值單元的未知像素點求解獲取高分辨圖像。

2.1 矩形插值單元和菱形插值單元

若高分辨率圖像中未知像素點的x，y坐標(biāo)均為奇數(shù)，則未知像素點被其周圍上、下、左、右4個與之等距的已知像素點和4個未知像素點所包圍。如圖1(a)中1和圖1(b)藍(lán)色象素點所代表的未知像素點。圖1(a)中的黑色部分代表已知像素點，白色部分代表未知像素點，圖1(b)的黑色點代表已知像素點，藍(lán)色點的x，y坐標(biāo)均為奇數(shù)，選中的黑色點對藍(lán)色點構(gòu)成矩形插值單元。

若高分辨率圖像中未知像素點的x，y坐標(biāo)一個為奇數(shù)一個為偶數(shù)，未知像素點被2個已知像素點和2個x，y坐標(biāo)均為奇數(shù)的未知像素點和2個x，y坐標(biāo)一個為奇數(shù)且一個為偶數(shù)的像素點包圍。如圖1(a)的數(shù)字2，3和圖2中紅色點和綠色點所代表的未知像素點。將圖2中紅色點和綠色點周圍被選中的4個點，所構(gòu)成的插值單元作為中心未知像素點的菱形插值單元。

2.2 幾何分類矩形插值單元

保證低分辨率的圖像邊緣決定了插值圖像的質(zhì)量。圖像梯度的局部最大值處可能存在邊，因此亮度的二階導(dǎo)數(shù)的零交叉點可判斷邊的存在。根據(jù)零交叉點的值，分割插值區(qū)域為不同類型的區(qū)域。

除圖像邊界點外，每兩個像素點間的零交叉點都可能來在2個方向的計算。如圖3，x2和x3間的零交叉點可以由x2，x3和x4計算，也可以由x1，x2和x3計算。

若公式 (3)成立，則表示x2和x3之間至少有一個零交叉點存在，其中T是一個常數(shù)。

矩形插值單元中共存在8個可能零交叉點，分別位于4對像素間。如圖4，虛線為可能存在零交叉點的位置。這些零交叉點的組合將插值單元中具有高對比度的像素區(qū)分開，即可能存在的圖像的邊，帶箭頭的切割線區(qū)分出高對比度的像素點。根據(jù)以上理論，矩形插值單元可以被幾何分類為3種情況:有1個點和其他3個點有高度比度;2個點和另外2個點有高對比度;沒有點和其他點具有高對比度。

以矩形插值單元左上角像素點具有高對比度為例來闡述情況。若圖4中像素點 (2i，2j)和 (2i，2j+2)，(2i，2j)和(2i+2，2j)間的零交叉點值滿足公式 (3)，則像素點 (2i，2j)與其它3個像素點間具有高對比度，圖4左上角的切割線存在。此時，我們認(rèn)為矩形插值單元的左上角像素點對中心未知像素點沒有貢獻(xiàn)，與待求未知像素點無關(guān)，只有其它3個點對中心點有貢獻(xiàn)，圖5(a)和(b)描述了這種情況，圖5(b)是圖5(a)的等價表示。具有高對比度像素點可能位于右上角，左下角或右下角，情況與左上角類似，見圖5(c)，(d)和 (e)。

當(dāng)2個像素點與其他像素點具有高對比度，矩形插值單元存在圖4中的水平或豎直割線。未知像素點的左半部分或右半部分具有較大差異，圖6。若圖4中割線水平，則 (2i，2j)和 (2i+2，2j)，(2i，2j+2)和 (2i+2，2j+2)之間存在零交叉線，如圖6(a)，圖6(b)是圖6(a)的等價表示，其他幾種形式如圖6(c)，(d)和 (e)。

如果插值單元中不存在零交叉線，這意味著插值單元是一個變化不大的連續(xù)平滑區(qū)域。

公式 (4)，(5)用來判斷平滑區(qū)域，f1，f2，f3，f4分別表示插值單元中的已知像素點，f為它們的均值，σ為區(qū)域內(nèi)的均方差。當(dāng)某個區(qū)域的已知像素點滿足公式 (5)時，則表示該區(qū)域是連續(xù)平滑區(qū)域。未知像素點被包含在該區(qū)域內(nèi)，此時未知像素點的值可以用它的四個最鄰近的已知像素點的值平均值求得。

2.3 幾何分類菱形插值單元

菱形插值單元內(nèi)的8個零交叉點是斜對角線方向上相關(guān)像素點確定的。如圖3中介于x7和x10之間的零交叉點。同矩形插值單元類似，x7和x10之間也存在2個方向的零交叉點，由x4，x7，x10和x13，x7，x10這兩組像素點決定。

若公式 (8)滿足則表示在x4和x7之間至少有一個零交叉點存在，其他點對間的零交叉點的判斷類似。

圖7是一個菱形插值核的幾何分類判別圖，虛線為可能存在的零交叉點，位于不同對像素點間的2個零交叉點形成一條割線，割線將菱形插值核分成不同的幾何類型。

圖7 菱形插值單元的幾何分類Fig.7 Geometrical classification of rectangular interpolating unit

圖8為菱形區(qū)域內(nèi)1個像素點具有高對比度的情況。若將菱形插值核中的4個頂點 (2i，2j)，(2i+2，2j)， (2i+1，2j－1)， (2i+1，2j+1)分別稱作左點，右點，上點，下點。當(dāng)上點和左點間，左點和下點間存在零交叉點時，左點與其他像素點之間存在明顯差異，左側(cè)豎直切割線形成。在左點右側(cè)存在邊。菱形的每個頂點都有可能與其它像素點形成明顯對比，對應(yīng)圖5中的某個豎直或水平割線，所有4種情況如圖8。

圖8 菱形插值核的1個像素點具有高對比度Fig.8 One point of high contrast in rhombic interpolating unit

零交叉點點不相鄰時，割線形成左對角線或右對角線2種情況。若割線為左對角線，菱形插值核如圖9(a)或圖9(b)。插值單元中心的未知像素點只與割線一側(cè)的像素點有關(guān)，即圖9(a)或圖9(b)的陰影部分。如果割線形成右對角線，如圖9(c)或圖9(d)，圖7中零交叉點位于左點和下點，右點和上點之間。這兩組之間存在較高的對比，未知像素點的值只能與其中的一組相關(guān)。如果所有的8個零交叉點都不存在，未知像素點被4個灰度值相似的點包圍，未知像素點處于平滑區(qū)域，對這種情況的處理與菱形插值單元類似。

圖9 菱形插值核的2個像素點具有高對比度Fig.9 Two points of high contrast in rhombic interpolating unit

3 自適應(yīng)的插值方法

基于幾何分類的方向自適應(yīng)圖像插值方法分步對插值圖像的未知像素點處理。首先根據(jù)T2i，2j=Si，j對高分辨率圖像中x，y坐標(biāo)值均為偶數(shù)的像素點進(jìn)行賦值。然后再矩形插值單元中插值x，y坐標(biāo)值為奇數(shù)的未知像素點。對每個矩形插值單元的8個零交叉點計算，根據(jù)計算值分類插值單元，然后用公式 (9)求解未知像素點。當(dāng)有一個像素點與其他像素點有高對比時，該像素與未知像素點間有邊存在，公式 (9)中該像素點相關(guān)系數(shù)為0;當(dāng)有2個像素點與其它2個像素點有高對比時，則有2個像素的系數(shù)為0。若矩形區(qū)域為平滑區(qū)域，則未知像素點的值取4個像素點的均值。

用矩形插值單元對圖像插值后，已知像素點和部分已求未知像素點構(gòu)成菱形插值單元，再對x坐標(biāo)為奇數(shù)，y坐標(biāo)為偶數(shù)或x坐標(biāo)為偶數(shù)，y坐標(biāo)為奇數(shù)的未知像素點插值。用斜對角線方向的8個零交叉點來判斷菱形插值單元的幾何類類型，然后根據(jù)公式 (10)求出菱形插值單元內(nèi)的中心像素點。若幾何分類為圖8中的某種情況，則具有高對比度的像素點在公式 (10)中的相關(guān)系數(shù)賦為0。若幾何分類為圖9的某一種，則將白色區(qū)域?qū)?yīng)的像素點的系數(shù)賦為0。若菱形區(qū)域為平滑區(qū)域，則未知像素為菱形4個像素的均值。兩次插值后，90%以上的未知像素點已求出。若仍有未知像素點，則用它周圍的已知像素點線性插值。

4 實驗結(jié)果

在Intel Pentium dual core 1.73 GHz處理器和2 GB內(nèi)存的PC機(jī)上實現(xiàn)本文算法。圖10對Lena(60×60)放大2倍，Lena帽檐處的鋸齒非常少。放大同樣倍數(shù)時，本文算法能夠更好的保持圖像邊緣的尖銳特征。

圖10 Lena放大2×2結(jié)果對比圖Fig.10 Comparison of the results of Magnifying Lena by 2×2

圖11是三角形 (60×60)放大2倍的結(jié)果?？梢园l(fā)現(xiàn)，本文推薦的方法在消除插值后的鋸齒方面非常有效。

圖11 三角形放大2×2結(jié)果的對比圖Fig.11 Comparison of the results of magnifying triangle by 2×2

本文用 MSE(Mean Squared Error)［9，12］，PSNR(Peak Signal to Noise Ratio)［13］定量分析插值效果，如表1和表2。

表1 Lena，Beach，Triangle的MSE值Table 1 MSE of Lean，Beach and Triangle

表2 Lena，Beach，Triangle的PSNR值Table 2 MSE of Lean，Beach and Triangle

表1和表2分別是最近鄰 (NN)，雙線性(BI)，雙三次 (BC)，Muhammad方法 (MU)和本文方法 (PR)插值 Lena(64×64)，三角形(60×60)和beach(60×60)后MSE和PSNR的數(shù)據(jù)統(tǒng)計，數(shù)據(jù)已分別被歸一化到0～70和0～30。圖12和圖13分別是它們的MSE和PSNR的柱狀描述圖。

對同一幅圖用不同的方法插值放大相同的倍數(shù)，MSE越小，PSNR越大，則該種方法的效果越好。由表1，2和圖12，13知本文方法比最近鄰、雙線性、雙三次和Muhammad's方法效果好。更多實驗結(jié)果見圖14，15。

5 總結(jié)與展望

本文提出了一種基于幾何分類的自適應(yīng)的圖像插值方法放大圖像。該方法最重要的貢獻(xiàn)是提出了八個方向的割線來判斷插值單元的分類，特別是斜對角方向，并基于未知像素點所屬插值單元的幾何分類插值圖像。本文方法保持插值后圖像的邊緣走向和寬度，保證圖像邊緣的尖銳特征，從而提高插值圖像的質(zhì)量。

本文方法更準(zhǔn)確的對插值單元進(jìn)行幾何分類，并根據(jù)未知像素點周圍最近鄰的已知像素點插值。因此，能夠更好的保持圖像尖銳特征，提高插值圖像的質(zhì)量。進(jìn)一步的工作是將本文方法擴(kuò)展到視頻放大。

［1］LI X，ORCHARD M T.New edge-directed interpolation［J］.IEEE Transactions on Image Processing，2001，10(10):1521－1527.

［2］MORSE B S，SCHWARTZWALD D.Isophote-based interpolation［C］∥Proc IEEE Int Conf on Image Processing，1998，3:227－231.

［3］FATTAL R.Image upsampling via imposed edges statistics［C］∥SIGGRAPH，2007，26(3):95－102.

［4］THURNHOFER S，MITRA S.Edge-enhanced image zooming［J］.Optical Engineering，1996，35(7):1862 －1870.

［5］SUN J，XU Z B，SHUM H Y.Image super-resolution using gradient profile prior［C］∥CVPR，2008.

［6］BATTIATO S，GALLO G，STANCO F.A New Edge-A-daptive Zooming Algorithm for Digital Images［C］∥Proc Signal Processing and Communication，2000:144－149.

［7］SHAN Q，LI Z R，JIA J Y，et al.Fast image/video upsampling［J］.ACM Transactions on Graphics，2008，27(5):153－159.

［8］KOPF J，COHEN M，LISCHINSKI D，et al.Joint bilateral upsampling［J/OL］.ACM Transactions on Graphics，2007，26(3):96［2010 － 05 － 19］.http:∥doi.acm.org/10.1145/1275808.1276497.

［9］SAJJAD M，KHATTAK N，JAFRI N.Image magnification using adaptive interpolation by pixel level data-dependent geometrical shapes［J］.International Journal of Computer Science and Engineering，2007:118－127.

［10］UNSER M，ALDROUBI A，EDEN M.Fast B-spline transforms for continuous image representation and interpolation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1991，13(3):277 －285.

［11］KEYS R.Cubic convolution interpolation for digital image processing ［J］.IEEE Trans Acoustics，Speech，Signal Processing，1981，29(6):1153－1160.

［12］MALGOUYRES F，GUICHARD F.Edge direction preserving image zooming:A mathematical and numerical analysis［J］.Society for Industrial and Applied Mathematics，2001，39(1):1－37.

［13］YOUNGJOON C，SEONGJAI K.Error-amended sharp edge schemes for image interpolation［C］∥ICIP，2006:701－704.