摘 要：提出了一種基于文檔圖像特征的混合插值算法。該算法通過(guò)分析文檔圖像的像素鄰域特征，使用鄰近插值、雙線性插值和雙三次樣條插值方法估計(jì)插值像素灰度值。其中，三次樣條插值方法使用了優(yōu)化算法，即三次樣條卷積模板的整數(shù)化運(yùn)算，其時(shí)間復(fù)雜度接近雙線性插值。給出了算法的實(shí)現(xiàn)過(guò)程。實(shí)驗(yàn)結(jié)果表明，該算法輸出的圖像質(zhì)量接近雙三次樣條插值，運(yùn)行效率高于雙線性插值算法，在文檔圖像掃描過(guò)程取得了良好的應(yīng)用效果。
關(guān)鍵詞： 文檔圖像； 樣條插值； 三次卷積插值； 圖像特征

    圖像插值是圖像處理的重要內(nèi)容之一,在航天、醫(yī)學(xué)、軍事、科研、通訊、衛(wèi)星遙感及電視電影制作等方面得到了廣泛的應(yīng)用，是改善圖像視覺(jué)效果的一種重要方法。
    早在1978年就有學(xué)者將三次樣條技術(shù)用于圖像插值，其算法復(fù)雜度非常高。1981年,三次卷積插值方法第一次被提出[1]，同時(shí)產(chǎn)生了一個(gè)重要結(jié)論：插值圖像質(zhì)量?jī)?yōu)于線性插值，但低于三次樣條插值?；诰矸e的插值方法可用于圖像的旋轉(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ì)算如下：
    R=n1×n2/n
其中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所示?？疾煜袼匚恢?ldquo;*”相鄰的8個(gè)像素位置對(duì)應(yīng)的像素值分布情況,一階差分計(jì)算過(guò)程為：    

2 圖像插值方法的改進(jìn)
2.1 圖像插值原理
    本文采用的插值方法包含4種，其中一種為圖像塊的拷貝，嚴(yán)格來(lái)說(shuō)不是插值技術(shù)，其他3種分別是鄰近插值、雙線性插值和雙三次樣條卷積插值。
    塊拷貝技術(shù)具有最低的算法復(fù)雜度，塊內(nèi)像素位置不需要計(jì)算位置映射關(guān)系，在傾斜角度很?。ɡ?.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ì)算式為：

    模板選擇與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)的雙三次樣條插值算法。

    本文采用的雙線性插值算法沒(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)算法。
參考文獻(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, high quality 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 interpolation-image 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] 申利平, 李開宇. 基于局部梯度的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.