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

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

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

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

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

1 文檔圖像特征分類

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

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

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

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

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

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

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

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

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

2 圖像插值方法的改進

2.1 圖像插值原理

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

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

鄰近插值方法考慮像素周圍相鄰的4個點的灰度值分布情況，其算法模型簡單。

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

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

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

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

三次插值算法的插值計算式為：

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

2.2 三次樣條卷積形式及其改進

三次樣條插值計算式可進一步改進為兩個4×4的矩陣的卷積形式：

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

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

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

3 算法實現(xiàn)及測試

3.1 算法流程

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

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

3.2 實驗結(jié)果與算法分析

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

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

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

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

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

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

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

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

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

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

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

文檔圖像是一類特殊圖像，根據(jù)其特點的高速插值方法可以解決實時圖像處理問題。本文算法具有高效率、高質(zhì)量的特點，但是不適用于一般意義的自然圖像，如何擴展本文算法是值得研究的重要課題，其核心問題是特征分類及其快速實現(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]高成敏,陳良,林永和.雙三次卷積模板運算[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é)報,2003,23(3):48-52.

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

[10]王杰,李洪興,王加銀,等.一種圖像快速線性插值的實現(xiàn)方案與分析[J].電子學(xué)報,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.