陳義學(xué)，劉 江，馬 磊

(山東省圖像采集與處理工程技術(shù)研究中心 山東山大鷗瑪軟件有限公司，山東 濟(jì)南250101)

圖像插值是圖像處理的重要內(nèi)容之一,在航天、醫(yī)學(xué)、軍事、科研、通訊、衛(wèi)星遙感及電視電影制作等方面得到了廣泛的應(yīng)用，是改善圖像視覺(jué)效果的一種重要方法。

早在1978年就有學(xué)者將三次樣條技術(shù)用于圖像插值，其算法復(fù)雜度非常高。1981年,三次卷積插值方法第一次被提出[1]，同時(shí)產(chǎn)生了一個(gè)重要結(jié)論：插值圖像質(zhì)量?jī)?yōu)于線性插值，但低于三次樣條插值。基于卷積的插值方法可用于圖像的旋轉(zhuǎn)[2]，參考文獻(xiàn)[3]進(jìn)一步討論了各種不同的卷積核函數(shù)及其特性與時(shí)間復(fù)雜性。參考文獻(xiàn)[4]通過(guò)三次卷積模板的整數(shù)化運(yùn)算方案提高其計(jì)算速度，其計(jì)算速度與雙線性插值大致相當(dāng)。相關(guān)研究表明[5]，線性插值和三次樣條具有圖像的平滑性。還有學(xué)者提出了基于邊緣方向的插值方法[6-7]，在降低算法復(fù)雜度的同時(shí)，圖像質(zhì)量?jī)?yōu)于傳統(tǒng)的雙線性方法。相關(guān)研究[8]表明,三次卷積方法比雙線性插值方法具有更好的圖像效果，雙線性插值方法在圖像的高頻部分不能被正確插值，標(biāo)準(zhǔn)的雙線性插值方法可以改進(jìn)其性能[9-10]?；旌喜逯捣椒╗11-12]的主要思想是根據(jù)目標(biāo)像素不同的屬性采用不同的插值方法，目的是既提高圖像的質(zhì)量又保證其效率需求，其核心問(wèn)題是特征分類器的準(zhǔn)確性及其高效性。

本文主要研究了基于文檔圖像特征分析的高速插值方法，利用文檔圖像像素鄰域特征選擇不同的插值方法，插值方法包含了鄰域插值、雙線性插值和三次樣條插值，其中三次樣條插值使用了模板卷積的整數(shù)化運(yùn)算方案。最后給出了理論時(shí)間復(fù)雜性分析，并實(shí)際驗(yàn)證了算法的有效性，給出了實(shí)驗(yàn)結(jié)論。

1 文檔圖像特征分類

文檔圖像有其自身的一些特點(diǎn)，其中與插值方法的選擇密切相關(guān)的有兩類特征：空白塊屬性；像素鄰域值分類特征。第一類可以作為文檔圖像的高級(jí)特征，第二類作為文檔圖像的低級(jí)特征。插值方法選擇的基本思想是先判斷文檔圖像的高級(jí)特征，再根據(jù)高級(jí)特征判斷低級(jí)特征。

文本圖像特征分類模型如圖1所示。文檔圖像通過(guò)適當(dāng)?shù)姆謮K尺寸（8×8）分割后，可以簡(jiǎn)單判斷空白屬性（只涉及加法運(yùn)算），如果是空白塊，則塊內(nèi)所有像素都可以直接拷貝至目的像素位置，可以省去大量的像素位置計(jì)算過(guò)程。如果是非空白塊，則進(jìn)一步分為文字塊和規(guī)則圖形塊，規(guī)則圖形塊與空白塊采用相同的策略，文字塊進(jìn)一步將像素值分為低級(jí)特征：平坦像素和非平坦像素。其中，平坦像素采用鄰近插值方法，非平坦像素采用雙線性插值或者三次樣條插值方法估計(jì)目標(biāo)像素值，更進(jìn)一步邊緣銳利的像素采用三次樣條插值，其余采用雙線性插值，從而確保了輸出圖像的主觀評(píng)價(jià)質(zhì)量。

規(guī)則圖像塊的判斷稍微復(fù)雜一些，假設(shè)圖像分塊尺寸為N，則計(jì)算行投影向量和列投影向量(只涉及加法運(yùn)算)，兩個(gè)投影向量的長(zhǎng)度也為N，投影向量中不為0的元素個(gè)數(shù)分別記為n1、n2,則規(guī)則屬性計(jì)算如下：

其中n為塊內(nèi)總的有效像素?cái)?shù)。比率越接近于1，說(shuō)明圖像塊越規(guī)則。例如圖像中有一個(gè)有效點(diǎn)，n1=1,n2=1,計(jì)算得到R=1,直線和規(guī)則的矩形塊都滿足該基本特征。僅通過(guò)有限次加法和一次除法運(yùn)算（除法運(yùn)算通過(guò)位移操作）就可以得到塊的基本屬性，以充分保證插值效率。

平坦塊和非平坦塊的判斷在一個(gè)較小的鄰域范圍內(nèi),一般選取3×3的模板，這樣可以充分保證效率問(wèn)題。平坦像素的確切定義是：當(dāng)前像素鄰域特征是空白屬性，在這樣的條件下直接使用鄰近插值算法，不必進(jìn)行復(fù)雜的浮點(diǎn)計(jì)算過(guò)程。根據(jù)相關(guān)研究結(jié)論，雙線性插值具有低通特性，因此在銳利的邊緣采用三次樣條插值是比較理想的策略。

鄰域像素選取如圖2所示?？疾煜袼匚恢谩?”相鄰的8個(gè)像素位置對(duì)應(yīng)的像素值分布情況,一階差分計(jì)算過(guò)程為：

其中像素位置灰度值為P。這個(gè)過(guò)程不涉及浮點(diǎn)數(shù)的計(jì)算問(wèn)題，當(dāng)銳利度變大時(shí)，就應(yīng)當(dāng)避免使用雙線性插值方法。

原圖與鄰域最大差細(xì)節(jié)圖如圖3所示，左邊為原圖，右邊為一階最大差分圖像，高亮部分應(yīng)當(dāng)使用三次樣條插值。

塊屬性的標(biāo)記圖像如圖4所示，右圖中空白塊個(gè)數(shù)為986，規(guī)則的圖像塊 332，文字塊個(gè)數(shù)為 132，不確定塊個(gè)數(shù)為251，其中空白塊所占比例為58%。對(duì)于掃描文檔圖像，空白塊所占的比例較大，空白塊可以直接使用塊拷貝，不必計(jì)算塊內(nèi)像素插值位置，有效地降低了運(yùn)算復(fù)雜度，提高了效率。

2 圖像插值方法的改進(jìn)

2.1 圖像插值原理

本文采用的插值方法包含4種，其中一種為圖像塊的拷貝，嚴(yán)格來(lái)說(shuō)不是插值技術(shù)，其他3種分別是鄰近插值、雙線性插值和雙三次樣條卷積插值。

塊拷貝技術(shù)具有最低的算法復(fù)雜度，塊內(nèi)像素位置不需要計(jì)算位置映射關(guān)系，在傾斜角度很小 （例如0.2角度）的情況下，塊的尺寸可以很大，塊尺寸過(guò)大不利于塊的分類效率，本文塊尺寸選擇為8。

鄰近插值方法考慮像素周圍相鄰的4個(gè)點(diǎn)的灰度值分布情況，其算法模型簡(jiǎn)單。

設(shè)目標(biāo)像素點(diǎn)的空間坐標(biāo)為(i+u,j+v)，其中：i、j均為像素坐標(biāo)的整數(shù)部分，u、v均為像素坐標(biāo)的小數(shù)部分，u、v是取值[0,1)區(qū)間內(nèi)的浮點(diǎn)數(shù)，則目標(biāo)像素點(diǎn)的灰度值 f(i+u,j+v)可由源圖像中像素坐標(biāo)為(i,j)、(i+1,j)、(i,j+1)、(i+1,j+1)所對(duì)應(yīng)的周圍 4個(gè)像素的灰度值所決定線性函數(shù)確定，計(jì)算式為：

其中，f(i,j)表示源圖像中坐標(biāo)為(i,j)處的像素點(diǎn)的灰度值，線性插值也可以轉(zhuǎn)化為整數(shù)化運(yùn)算方案。

雙三次插值算法克服了近鄰插值算法出現(xiàn)的邊緣階梯現(xiàn)象，消除了雙線性插值算法出現(xiàn)的邊緣模糊現(xiàn)象，是一種插值效果很好但運(yùn)算復(fù)雜度較大的插值算法。雙三次插值采用源圖像中待采樣像素點(diǎn)周圍16個(gè)相鄰像素點(diǎn)來(lái)做插值運(yùn)算，利用三次多項(xiàng)式S(w)來(lái)近似地逼近理想的插值函數(shù)C(x)。

設(shè)三次多項(xiàng)式S(w)的數(shù)學(xué)表達(dá)式為：

三次插值算法的插值計(jì)算式為：

從雙三次插值算法的插值計(jì)算式中可以看出，該插值算法的運(yùn)算復(fù)雜度較高。

2.2 三次樣條卷積形式及其改進(jìn)

三次樣條插值計(jì)算式可進(jìn)一步改進(jìn)為兩個(gè)4×4的矩陣的卷積形式：

其中,M=[B]表示鄰域灰度采樣矩陣，T表示卷積核因子，根據(jù)u,v的劃分(平均分成4等份),共有16種卷積模板：

其中,u和v的取值仍然是小數(shù)值，因此將計(jì)算值擴(kuò)大一定的倍數(shù)(如220)，就可以得到整數(shù)化運(yùn)算方案，卷積完成后，再縮小相應(yīng)的倍數(shù)，縮放用位移操作實(shí)現(xiàn)，簡(jiǎn)單高效。

模板選擇與 u、v的關(guān)系如圖 5所示，根據(jù) u、v不同的位置關(guān)系,使用不同的卷積模板估算插值像素灰度值。

3 算法實(shí)現(xiàn)及測(cè)試

3.1 算法流程

掃描文檔圖像過(guò)程中，經(jīng)常發(fā)生圖像的傾斜，因此圖像糾偏的效果、效率是掃描設(shè)備的重要指標(biāo)，圖像插值效率直接決定了圖像糾偏的效率。本文結(jié)合傾斜角度估計(jì)方法實(shí)現(xiàn)了高速圖像糾偏功能。高速圖像插值的基本流程如下：

插值算法基本流程如圖6所示。該方法融合了塊的拷貝技術(shù)、雙線性插值方法、鄰近插值方法和三次樣條卷積快速插值方法，融合圖像的高級(jí)特征和低級(jí)特征屬性，塊拷貝具有非常高的效率，且占有大部分像素區(qū)域，鄰近插值方法對(duì)應(yīng)的像素?cái)?shù)占總像素?cái)?shù)的90%以上，為了保證圖像的質(zhì)量，較少的像素?cái)?shù)（對(duì)應(yīng)銳利邊緣像素）使用了快速三次樣條插值方法。

3.2 實(shí)驗(yàn)結(jié)果與算法分析

本文使用山東山大鷗瑪軟件有限公司自主研制的TS3000掃描設(shè)備掃描的圖像作為測(cè)試圖像，分辨率為100 dpi，圖像尺寸為 2 112×1 152。

圖像傾斜校正測(cè)試結(jié)果如圖7所示，圖7(a)為原始傾斜圖像，圖7(b)是最終的像素分類結(jié)果，其中白色像素需要使用三次樣條插值方法和雙線性插值方法，它們對(duì)應(yīng)了圖像中較為銳利的邊緣部分，像素?cái)?shù)最少；黑色直接使用了塊拷貝方式像素?cái)?shù)最多；灰色采用了鄰近插值方法。

像素分類統(tǒng)計(jì)特性如表1所示，黑色像素?cái)?shù)占總像素?cái)?shù)的50%以上，這些像素不需要計(jì)算插值位置（每個(gè)分塊計(jì)算一次插值位置）和插值后的灰度值，具有最高的效率，時(shí)間上來(lái)說(shuō)只是拷貝的時(shí)間；臨鄰近插值部分需要計(jì)算插值位置但是不需要計(jì)算插值灰度值，這些像素的旋轉(zhuǎn)不會(huì)對(duì)文檔圖像產(chǎn)生大的影響；三次樣條插值對(duì)應(yīng)包含支線、文字、黑色的圖像塊，在傾斜的情況下，這些位置都不是規(guī)則圖形，這些像素?cái)?shù)只占總像素?cái)?shù)約5%，采用了改進(jìn)的雙三次樣條插值算法。

表1 像素分類統(tǒng)計(jì)特性

本文采用的雙線性插值算法沒(méi)有優(yōu)化，一個(gè)像素值的灰度值估計(jì)大約需要8次浮點(diǎn)乘法運(yùn)算，未優(yōu)化的三次樣條插值大約需要28次浮點(diǎn)乘法運(yùn)算，而改進(jìn)的三次樣條插值方法大約需要16次整數(shù)乘法運(yùn)算。

為了能比較整數(shù)運(yùn)算與浮點(diǎn)運(yùn)算的時(shí)間,使用1 000萬(wàn)次浮點(diǎn)數(shù)乘法運(yùn)算和整數(shù)乘法運(yùn)算作為測(cè)試，得到1次浮點(diǎn)數(shù)乘法與1次整數(shù)乘法運(yùn)算之間的時(shí)間相關(guān)性。結(jié)果顯示，1次整數(shù)運(yùn)算的時(shí)間相當(dāng)于1次浮點(diǎn)數(shù)運(yùn)算時(shí)間的1/3，這樣便于從理論上估計(jì)時(shí)間運(yùn)行復(fù)雜度。根據(jù)這個(gè)測(cè)試結(jié)論，使用三次樣條插值大約需要6次浮點(diǎn)乘法運(yùn)算，比雙線性插值方法稍高。

根據(jù)表1所列的像素比例關(guān)系，針對(duì)掃描原圖的糾偏插值問(wèn)題，可以大致估計(jì)插值所用的時(shí)間復(fù)雜度（比率與插值算法的時(shí)間復(fù)雜度相乘）：

O=0.518 5×0+0.4339 57×0+0.047 543×6

標(biāo)準(zhǔn)的三次樣條插值算法是28，雙線性插值方法是8，理論上估計(jì)算法的效率提高10倍以上，如果文檔圖像比較復(fù)雜(文本內(nèi)容較多)，算法的復(fù)雜度會(huì)上升。實(shí)際測(cè)試證明了該插值算法的高效性，比雙線性插值效率提高2倍以上。

本文提出一種基于文檔圖像高級(jí)特征分類和低級(jí)特征分類的高速插值方法，高級(jí)特征使用了圖像的空白屬性和規(guī)則圖形判斷方法，低級(jí)特征使用了一階鄰域最大差屬性。根據(jù)特征分類，結(jié)合常用的圖像插值方法，確定了插值方法的選擇策略，并針對(duì)算法復(fù)雜度較高的三次樣條插值方法，使用整數(shù)化模板卷積替代浮點(diǎn)運(yùn)算。最后針對(duì)圖像的傾斜校正問(wèn)題，給出了具體的插值過(guò)程流程圖，結(jié)合經(jīng)典插值算法，分析了算法的時(shí)間復(fù)雜度，從理論和實(shí)際測(cè)試都說(shuō)明了算法的高效性。

本文的高速插值方法的有效性基于3點(diǎn)：(1)文檔圖像具有一定的空白屬性，充分利用了數(shù)據(jù)塊的拷貝策略；(2)鄰近插值算法選擇策略，大量的減少浮點(diǎn)數(shù)的運(yùn)算，銳利度使用了一階差分方法,不涉及浮點(diǎn)數(shù)的運(yùn)算；(3)三次樣條卷積整數(shù)化模板卷積運(yùn)算，該方法使得三次樣條插值算法相比雙線性插值算法效率更高，而插值圖像的光滑性、清晰度更好。

文檔圖像是一類特殊圖像，根據(jù)其特點(diǎn)的高速插值方法可以解決實(shí)時(shí)圖像處理問(wèn)題。本文算法具有高效率、高質(zhì)量的特點(diǎn)，但是不適用于一般意義的自然圖像，如何擴(kuò)展本文算法是值得研究的重要課題，其核心問(wèn)題是特征分類及其快速實(shí)現(xiàn)算法。

[1]KEYS R G.Cubic convolution interpolation for digital image processing[J].IEEE Transactions on Acoustics,Speech,and Signal Porcessing,1981,ASSP-29(6):1153-1160.

[2]UNSER M.Convolution-based interpolation for fast,highquality rotation of images[J].IEEE Transactions on Image Porcessing,1995,4(10):1371-1881.

[3]MEIJERING E,UNSER M.A note on cubic convolution interpolation[J].IEEE Transactions on Image Processing,2003,12(4):477-479.

[4]高成敏,陳良,林永和.雙三次卷積模板運(yùn)算[J].計(jì)算機(jī)工程與應(yīng)用，2009,45(17):151-153.

[5]PARKER J A,KENYON R V,TROXEL D E.Comparison of interpolating methods for image resampling[J].IEEE Transactions on Medical Imaging,1983,MI-2(1):31-39.

[6]Li Xin,ORCHARD M T.New edge-directed interpolationimage processing[J].IEEE Transactions on Image Processing,2001,10(10):1521-1527.

[7]Zhang Lei,Wu Xiaolin.An edge-guided image interpolation algorithm via directional filtering and data fusion[J].IEEE Transactions on Image Processing,2006,15(8):2226-2238.

[8]曹 寧,孫宇.H26L中立方卷積插值算法的研究[J].南京郵電學(xué)院學(xué)報(bào),2003,23(3):48-52.

[9]申利平,李開(kāi)宇.基于局部梯度的WaDi圖像插值[J].計(jì)算機(jī)技術(shù)與發(fā)展,2008,18(6):76-82.

[10]王杰,李洪興,王加銀,等.一種圖像快速線性插值的實(shí)現(xiàn)方案與分析[J].電子學(xué)報(bào),2009,37(7):1481-1486.

[11]LEE C.Rapid hybrid interpolation methods[J].Optical Engineering,2004,43(5):1183-1194.

[12]LUMING L.Image interpolation by blending kernels[J].IEEE Signal Processing Letter,2008(15):805-808.