基于特征的文档图像高速插值算法

陈义学，刘 江，马 磊

(山东省图像采集与处理工程技术研究中心 山东山大鸥玛软件有限公司，山东 济南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.