基于特征的文檔圖像高速插值算法

陳義學，劉 江，馬 磊

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

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

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

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

1 文檔圖像特征分類

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

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

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

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

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

鄰域像素選取如圖2所示。考察像素位置“*”相鄰的8個像素位置對應的像素值分布情況,一階差分計算過程為：

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

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

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

2 圖像插值方法的改進

2.1 圖像插值原理

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

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

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

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

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

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

設三次多項式S(w)的數學表達式為：

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

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

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

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

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

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

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

3 算法實現及測試

3.1 算法流程

掃描文檔圖像過程中，經常發生圖像的傾斜，因此圖像糾偏的效果、效率是掃描設備的重要指標，圖像插值效率直接決定了圖像糾偏的效率。本文結合傾斜角度估計方法實現了高速圖像糾偏功能。高速圖像插值的基本流程如下：

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

3.2 實驗結果與算法分析

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

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

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

表1 像素分類統計特性

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

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

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

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

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

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

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

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

[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].計算機工程與應用，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].南京郵電學院學報,2003,23(3):48-52.

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

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