在当今信息技术高速发展的背景下，多媒体技术的发展使文档图像在信息的交换中运用越来越频繁。日益增长的需求使文档图像的数量越来越庞大，这就要求文档图像存储系统能够为用户提供快速高效的检索服务，为了达成这一目标许多国内外学者进行了卓有成效的研究^[1-2]。王澎等^[3]提出提取图像关键点的64维SURF特征集，计算每一维上的一阶中心矩与加权绝对中心矩，形成特征向量，将其作为SVM分类的依据，对1 000幅图片进行分类，获得86.8%的正确分类率。赵璐璐等^[4-5]，对提取的64维SURF特征点，基于FLANN算法进行双向匹配，对匹配对进行PROSAC分析，剔除误匹配对，提高图像匹配精度，有效缩短匹配占用时间。闫丽等^[6]，扩展Haar响应，生成包含线特征、中心环绕特征、角点特征的Haar-Like特征集，提高描述子的区分率，基于欧氏距离比实现遥感图像的快速准确匹配。陈剑虹等^[7]提出改进SURF关键点检测，提取图像细节区域的特征点，不经过非极大值抑制有效去除边缘点与低对比点，将优先队列(BBF)融入到KD-Tree双向匹配中，实现稳定、快速鲁邦特征的精确匹配。罗楠等^[8]对SURF特征描述进行改进，用改进DAISY描述算子为每个关键点分配主方向，形成维数为200的特征向量，并通过最近邻距离比(NNDR)匹配目标图像，其最大匹配率达到95.78%。王亚文等^[9]基于中心-边缘区域比较模板匹配算法有效跟踪目标区域，提取SURF特征，将匹配对数目与模板匹配数目比较自适应调整跟踪窗口，实现目标检测。这些方法分别对特征提取和匹配方式进行不同程度的改进，但是检索时间或检索准确率需要进一步提高。

本文提取改进的N×64维SURF特征，并对其实现FLANN双向匹配，依次统计匹配性能参数，并将其作为相似性度量依据，从大规模图像数据库中有效检索输出目标文档图像。此外，为降低检索复杂度，笔者运用基于距离的相似性度量方法，快速查找目标文档图像。

1 FAST+SURF特征提取

本文对细节信息丰富的维吾尔文复杂文档图像进行研究，不对其进行版面分析，对改进SURF特征实现脱离于词袋模型的检索方法，从大规模图像数据库中实现有效检索。本文算法流程如图1所示。

图1中的快速鲁棒特征(SURF)提取过程与SIFT相似，由关键点检测与特征描述两部分构成。但其维持图像尺寸不变，以倍数关系改变盒子滤波器的尺寸、尺度，在积分图像的基础上滤波构建尺度空间，使得特征检测耗用时间远短于SIFT。在特征描述中，统计扇形区域内的Haar小波响应值，确定关键点的主方向，累加统计划分区域内X、Y方向的Haar值与Haar绝对值，降低计算复杂度。

1.1 原始SURF特征向量提取

计算灰度图像在(x, y)处的积分值，并与不同尺度下的高斯函数二阶偏导数做卷积运算。为降低计算复杂度，用不同尺寸、尺度的盒子滤波器近似替代卷积结果，形成不同尺寸条件下的Hessian矩阵行列式。最后，计算Hessian行列式的迹，并与相邻尺度下的26个像素点进行非极大值抑制(NMS)运算，获取SURF关键点的精确位置^[10-11]，其数学表达式如下：

$ {I_{{\sum{\left( {X,Y} \right)}}}} = \sum\limits_{i = 0}^{i \ll X} {\sum\limits_{j = 0}^{j \ll Y}} {\rm Gray} \left( {i,j} \right) $

(1)

$ \begin{array}{c} H\left( {x,\sigma } \right) = \left[ {\begin{array}{*{20}{c}} {{L_{xx}}\left( {x,\sigma } \right)} & \;{{L_{xy}}\left( {x,\sigma } \right)}\\ {{L_{yx}}\left( {x,\sigma } \right)} & \;{{L_{yy}}\left( {x,\sigma } \right)} \end{array}} \right]= \\ \left[ {\begin{array}{*{20}{c}} {{D_{xx}}\left( {x,\sigma } \right)} & {{D_{xy}}\left( {x,\sigma } \right)}\\ {{D_{yx}}\left( {x,\sigma } \right)} & {{D_{yy}}\left( {x,\sigma } \right)} \end{array}} \right] \end{array} $

(2)

式中： ${I_{{\sum ^{\left( {X,Y} \right)}}}}$ 为积分图像，H(x, σ)为Hessian矩阵行列式，L_xx(x, σ)、L_yy(x, σ)分别为X方向、Y方向的二阶偏导数卷积，L_xy(x, σ)、L_yx(x, σ)为混合偏导数卷积。D_xx(x, σ)为盒子滤波近似值。对应SIFT，构建4组尺度空间，每组含有不同尺寸、尺度下的盒子滤波。其层次表达如图2所示。

当盒子滤波器尺寸为N×N时，其对应的高斯尺度为s=σ₀×N/9，其中σ₀=1.2。尺度空间中取每一点的Hessian迹^[12]，其表达式为

$ {\rm Det}\left( H \right) = {D_{xx}}{D_{yy}} - {\left( {0.9{D_{{\rm{xy}}}}} \right)^2} $

(3)

在尺度空间被检测出的关键点对文档图像的尺寸、平移和旋转有鲁棒性。给SURF局部特征点分配主方向来保证其旋转不变。以5°为量级，在60°滑动扇形区域内累加求和每一个像素点在水平、垂直方向上的Haar小波响应分量，求其最大值作为此关键点主方向^[13]。以关键点为中心取20×20区域，将这个区域又按4×4的大小划分成25个子区域，然后依次计算每个小区域的像素点的水平方向和垂直方向的Haar值以及绝对和值，最后将提取64维SURF特征向量。

1.2 改进SURF特征提取

原始SURF特征相比于SIFT，被检测特征点数目少、特征提取占用时间短。但是，对于图文混排的复杂文档图像，缩短时间参量不理想。因此，为实现维文复杂版面图像中关键点的快速检测，本文提取文档图像的灰度信息和角点。检测角点时用FAST算法，并用SURF算子描述，构成64维FAST+SURF特征，有效缩短特征提取时间^[14]。其特征检测算法流程如图3所示。

获取具有平移、缩放不变性的关键点后，为维持旋转不变性，给被检测的FAST关键点进行SURF描述，统计划分子区域内Haar小波响应的水平、垂直分量累加值与绝对累加值，形成N×64维特征。

2 FAST+SURF特征匹配分析

如果采用传统的方法进行特征匹配不仅计算量大，耗时长，而且系统的内存占用率较高。维吾尔文复杂文档图像的文字区域中存在较多的黑像素信息，被检测关键点数目较多。因此，为有效提高匹配速率，笔者对不同版面图像实现双向快速近似最近邻(FLANN)匹配，将其结果与KD−Tree+BBF匹配结果进行对比分析，以系统性能作为基本出发点来构建匹配系统，从而使系统能够对复杂的维吾尔文文档图像进行高效的检索。

2.1 双向FLANN匹配

设用户输入查询图像与维吾尔文复杂文档图像库中，待匹配图像的改进SURF特征向量集分别为 ${{A}} = {[ {x_1}\,\,\,{x_2}\,\,\, \cdots \,\,\,{x_N}] ^{\rm{T}}}$ ， ${{B}} = {[ {y_1}\,\,\,{y_2}\,\,\, \cdots \,\,\, {y_N}] ^{\rm{T}}}$ 。通过计算 ${x_i}$ 到特征向量B的最大和最小距离，并设定阈值为γ=ρ×Min_i。如果计算所得距离小于设定阈值，则记录该点并等待进一步匹配计算，如果距离大于设定阈值，则继续进行其他点的匹配。由于FLANN算法具有匹配速度快的特点，所以本文采用FLANN算法进行匹配，并在先后两个方向同时开始匹配，这样能够快速获得所需匹配对的相似性信息，从而进行进一步的判断。具体为：先从A到B的方向开始匹配，然后再从B到A的方向进行匹配，分别形成位置信息集合 $\left\{ {{{m}}_{{j}}^{{A}},{{m}}_{{k}}^{{B}}} \right\}$ 与 $\left\{ {{{m}}_{{k}}^{{B}},{{m}}_{{j}}^{{{A'}}}} \right\}$ 。这样逐次将 ${{m}}_{{j}}^{{A}}$ 的大小与 ${{m}}_{{j}}^{{{A'}}}$ 进行比较，如果大小相同则说明 ${{m}}_{{k}}^{{B}}$ 完全匹配。同时在匹配过程中通过RANSAC算法求出将要进行匹配的点与影射矩阵的距离，并用此距离与设定的距离阈值进行比较，这样做的目的是为了能够比较有效地去掉误匹配点对，从而使个匹配点对能够准确地匹配。原始图像FALNN双向匹配结果如图4所示。

2.2 KD−Tree+BBF匹配

KD−Tree的匹配主要由树形结构的建立与最近领查找等两个部分组成。KD−Tree搜索能力与特征向量的维数相关，维数越大，搜索能力越差。因此，本文从改进的KD−Tree出发，将得到的距离结果与预设的阈值相比较，判断是否为匹配关键点^[15]。本文中对改进64维SURF特征实现改进KD−Tree匹配的过程如图5所示。

匹配系统在不同变换条件下的匹配效率一般是由匹配率(MR)、正确匹配率(CMR)与错误匹配率(IMR)来衡量，它们计算公式分别为

$ {\rm MR} =\displaystyle \frac{{{N_c}}}{{{N_d}}} $

(4)

$ {\rm CMR} =\displaystyle \frac{{{N_{ac}}}}{{{N_c}}} $

(5)

$ {\rm IMR} =\displaystyle \frac{{N_{ai}}}{{N_c}} $

(6)

式中：N_c和 N_d分别为总匹配对数目和被检测的特征点数；N_ac和N_ai分别指正确匹配对总数和错误匹配对总数。

3 维吾尔文复杂文档图像检索

用户输入查询复杂文档图像，系统自动获取64维改进SURF特征向量，与特征向量库之间基于多种相似性度量算法，从数据库中查找目标文档图像，返回用户界面。本文运用两种相似性度量算法实现用户特定目标文档图像的检索，即基于距离的相似性度量与基于匹配数目的相似性度量。文中用4种特征向量间距离相似性度量算法，其数学表达式为

$ d_{\rm{Euclidean}} = \sqrt {{{\left( {{x_1} - {x_2}} \right)}^2} + {{\left( {{y_1} - {y_2}} \right)}^2}} $

(7)

$ d_{\rm{Manhattan}} = \left| {{x_1} - {x_2}} \right| + \left| {{y_1} - {y_2}} \right| $

(8)

$ d_{\rm{Chebyshev}} = \max \left( {\left| {{x_1} - {x_2}} \right|,\left| {{y_1} - {y_2}} \right|} \right) $

(9)

$ d_{\rm{Cosine}} = \frac{{{x_1}{x_{2 + }}{y_1}{y_2}}}{{\sqrt {{x_1}^2 + {x_2}^2} \sqrt {{y_1}^2 + {y_2}^2} }} $

(10)

对于同一个查询文档图像的改进SURF特征向量，基于上述四种距离分别度量相似性，实现维吾尔文复杂文档图像的检索，以检索率为系统性能指标，评估本系统有效性。在以匹配数目为检索依据的检索系统中，从匹配数目和正确匹配数目考虑，统计查询图像与图像库中每幅图像之间的正确匹配数目，将其按降序排序，实现文档图像的有效检索。其中越相似复杂文档图像，则其匹配数目越大。本文计算系统检索率的表达式为

$ R= \frac{{N - S}}{{N - 1}} $

(11)

式中：N是指复杂文档图像数据总的样本数，S是指系统检索出来的目标文档图像的位置序号。

4 实验结果与分析 4.1 实验数据

收集维吾尔文复杂版面书籍、杂志、公文，以不同分辨率(100 dpi，200 dpi，400 dpi)扫描形成8位的.bmp格式的维文复杂文档图像，构造含有1 000幅不同分辨率、不同底色信息、不同版面结构的复杂文档图像的数据库。本系统是在Windows7环境下用Visual Studio 2010+openCV-2.4.10编程开发的。

4.2 实验结果与分析

SURF特征在检测的时候主要是靠尺度空间层数(Octaves)、组数(Intervals)、斑点(THRES)阈值的选择。阈值(Octaves，Intervals，Init-sample，THRES)选定的不同，提取的特征点数目也不相同。为验证FAST+SURF特征的效率，在不同的阈值条件下，对1 606×2 290的同一张图像进行实验，统计关键点数和特征提取时间，实验结果如表1给出。

从表1可以得到，尺度空间阈值的变化对SURF特征点的检测尤为重要。层数与层间组数的变化由改变盒子滤波器数目来实现，其影响表现在对积分图像的处理上，且特征检测耗用时间上有微小差异。阈值的变化极大影响了最终检索结果。对于每一个候选点，取其上下邻域空间中的26个像素点，相互比较Hessian矩阵行列式值。若候选点Hessian行列式值比26个像素点行列式值都大或都小且小于阈值，则此候选点视为关键点。本文考虑多个阈值参数对SURF关键点检测的影响，并为减少时间和计算复杂度，提出了FAST+SURF特征提取算法。为验证该方法的优越性，在(4，4，2，0.000 4f)阈值下提取相同版面不同尺寸的维文复杂文档的SURF特征，将其与不同灰度阈值下的FAST+SURF特征进行性能分析，实验结果如表2所示。

经多次实验发现FAST(100)+SURF特征数目接近在(4，4，2，0.000 4f)阈值下的原始SURF特征数目。以检测FAST关键点来增加被检测特征点总量为付出，就可以很大程度上减少在特征点检测上耗费的时间复杂度，这样不仅能够明显优化匹配效率，还能够让快速检索维吾尔文复杂文档图像成为可能。从表2中能够了解到，同一幅不同尺寸图像的SURF特征点数目随图像尺寸变大而增多。而本文提出的改进FAST+SURF特征中，特征点数目不与图像尺寸成正比关系。FAST角点检测中，建立高斯卷积或Haar滤波的尺度空间、计算高斯函数导数与积分图像的卷积是完全没有必要的，我们只需要检测相对周围像素点，检测都亮或都暗区域，这样能够明显缩短特征检测时间同时也显著降低计算复杂度。为检测本文提取特征对旋转、尺度、光照变换的鲁棒性，进行不相同变换的情况，选择大小为1 606×2 290的维吾尔文复杂文档图像且提取改进SURF特征，同时分别用FLANN双向匹配、KD−Tree+BBF匹配寻找能够精确匹配对总数。基于FLANN的双向匹配对阈值的依赖性较强，其定义为γ= max{α×min_dist, β}。为精确定位阈值，分别在γ=β与γ=α×min_dist下匹配两幅相同版面文档图像，并得知当γ=0.1或γ=50×min_dist时匹配性能最可靠。分别在两种阈值下匹配换后的文档图像与原始图像，统计匹配性能参数得知当阈值为γ=0.1时，系统匹配性能最可靠。在尺寸变换下FLANN双向匹配在阈值γ=0.1的下匹配与KD−Tree+BBF匹配的结果如下表3所示。

将原始的文档图像划分为相等的2块和4块，随着图像尺寸的减小，被检测的特征点数目也随之减少，在匹配时，匹配到的关键点数目也减少。在特征提取时由于每块剪切图像中文字所占比例的不同，提取的特征点的位置也不尽相同。图像中的非文字区域是由图片组成，特征点的分布较为密集，干扰点也较多，关键特征点的选择比较困难，而文字区域的特征点分布较为均匀，因此被检测局部关键点数目较多。从表3可以得到以下结论，使用KD−Tree+BBF匹配时，它的总的匹配对数、正确的匹配对数、错误的匹配对数比使用FLANN双向匹配的结果好。实验中，随着图像尺寸的减小，提取到的关键点的总数目也成倍减小，匹配时的正确匹配的数目也成倍减小，相较于FLANN双向匹配而言，KD−Tree+BBF匹配时的正确匹配率要高。但在使用这两种匹配算法时，KD−Tree+BBF的匹配算法在构建与匹配上需遍历父节点与叶点且回溯，而FLANN双向匹配不需要回溯，只需要将近似近邻替代最近邻，若实验图像过大时，每幅图像提取的关键点会变多，而数量庞大的关键点会增加运算的复杂度和运行时间，这也给运行系统的稳定性带来影响，因此当关键点数量庞大时FLANN双向匹配的效果较好。为证明SURF特征的旋转不变性，对原始图像进行不同角度旋转，并分别用这两种匹配算法进行匹配，统计实验结果如表4所示。

逆时针或顺时针旋转印刷体维文复杂文档图像，使图像面积扩大，图像的位置也会发生变化，因此特征点的位置也会改变。由表4可以得出，FALNN双向匹配中，当旋转不同的角度时，图像的整体面积不同，关键点的数也不同。因此匹配时的正确匹配率也在62.60%~70.28%变化。可见，匹配对总数变化率与正确/错误匹配率相关。在不进行任何旋转变换时，内点数目为最大值为768。在KD−Tree+BBF匹配中，匹配对数目减少，从9 335~6 005，变化范围较大；对于整体结果，匹配结果相对较好的是KD−Tree+BBF的匹配率，FLANN匹配效果较差，但KD−Tree+BBF检索工作量大，而FALNN检索工作量小。当旋转角度发生变化时，FLANN双向匹配的结果较好，KD−Tree+BBF匹配的结果较差。为验证在光照变换条件下的检索效果，对原始文档图像的亮度进行改变，统计不同亮度变换下的两种匹配性能参数，实验结果如表5给出。

表5中，在FLANN双向匹配中，亮度变亮的变化对匹配的正确率影响较小，在705~758波动；而亮度变暗的变化对匹配的正确率影响较大，在803~1 018，这是受采集的实验样本的影响，亮度过暗时会形成干扰点，因此亮度的变化范围不易过大。在KD−Tree+BBF匹配中，当亮度变暗到−60时，实验样本整体模糊，样本的背景色也被列入检测范围，对检测到的关键特征点造成干扰，从而对匹配时的匹配数目造成干扰，影响正确匹配率；亮度变暗时提取的特征点数目要多于亮度变亮时的特征点数目，匹配的精度也较差。可知，在亮度变换条件下性能较稳定的是KD−Tree+BBF匹配。

由于维吾尔文复杂文档图像库是由不同版面、不同底色、不同分辨率文档图像采集而建立的。在灰度化过程中，不能有效消除文档图像底色，因此底色信息影响关键点检测。此外，将图像几何均匀分割成不同小块与整幅图像匹配时，若图像版面越相似，则匹配率较高；因此从数据库中取不具有底色，相似版面结构的分辨率为100 dpi，尺寸为1 606×2 290的100幅维吾尔文复杂文档图像构建小规模图像数据库。从中任选一幅图像，将其几何均匀划分成2、4、8块，分别作为查询图像，再以基于匹配距离与匹配数目为依据进行图像检索。由于文档图像尺寸大，被检测特征点数目较多，因此系统检索耗用时间较长，本文不作为系统性能指标。用不同匹配方法所进行的检索实验对比如图6所示。

将复杂的文档图像分别均匀划分为等面积的2块、4块和8块，由于每幅图像的文字分布区域不同，所以分割后的每小块中包含的关键点数目也不同。在本实验中，当被选择查询图像分割成4块时，绝大部分为非文字区域，因此提取的特征数目少，并在完整图像库中检索含有本区域的图像时，检索率明显下降。从图6(a)可知，不同距离相似性度量算法对检索系统的影响不同。因此在剪切图像研究中，基于匹配距离的检索系统相对性能优于基于匹配数目的检索。当完整文档图像为查询输入时，与目标图像关键点位置一一对应，因此关键点之间距离为最小；当复杂版面图像均匀分割分别作为查询图像时，被检测关键点数目减少，被分割图文面积不均匀，在诸多相似版面中难以找出含有被分割区域的复杂文档图像。从图6(b)可知，基于匹配数目的检索性能优于基于距离的检索。由于局部特征的尺寸变换不变性维使得对于区域匹配数目相对稳定，因此不同分割条件下检索目标文档图像的检索率都接近100%。

在实验中，采集的原始图像篇幅较大，特征提取到的特征点数目太多，这对最终匹配点的数目造成很大的影响。因此，为更好地评估系统性能，对采集到的原始维吾尔文复杂文档图像数据库进行修改：1) 对图像进行压缩，将图像压缩成256×256尺寸；2) 对图像进行剪切，将图像剪切成256×256尺寸。对同一幅文档图像进行两种修改样本实例如图7所示。

从图7中可以得到，对原始的整幅图像进行压缩，会使图像的清晰度降低。而对原始的整幅图像进行剪切，只是剪切图像的一部分，不会对清晰度造成影响，但篇幅的减少也会使提取的特征点减少。因此改造后的数据库都会对检索精度有或多或少影响。本文分别从匹配数目、匹配距离这两个方面进行测试，其检索实验结果如表8、9所示。

由表8可以得出，由于剪切文档图像是从原始文档图像上分割的一部分，因此检测到的特征点数目也会减少。当输入裁剪图像，在剪切构造的维文复杂文档数据库中，基于3种方法检索，其检索率都达到100%，但检索占用时间不同。匹配数目检索时需要先比较最近邻的特征点之间距离，看距离比值是否在设定的阈值范围内，若是，则相匹配，反之不匹配，这就导致检索时耗时较长。

由于压缩文档只是对原始文档图像的缩小，因此其内容包含整体图像内容。由表9可知，在时间损耗上，基于匹配数目的检索系统较多，而基于距离相似性度量的检索时间较少。对于剪切文档和压缩文档这两种数据库，基于匹配数目的检索中提取的特征点数目越多，匹配时的匹配点数目也会增多，则匹配时间也会随之变化。基于距离相似性的检索中，剪切的文档图像篇幅较少，比压缩的文档图像检索用时更短。由于人工剪切采集图像，易受人主观因素的影响；此外原始图像库是由不同分辨率图像构成，采集时分辨率越大则图像获取内容越少，使得图像失去完整性，因此压缩图像检索时间比剪切图像检索时间短。

5 结束语

本文为弥补维吾尔文复杂文档图像在检索领域中的空白，在维吾尔文文档图像检索匹配中运用SURF与改进SURF特征，使得少数民族文档图像检索研究进一步推进。文中通过不同阈值条件下检测SURF特征，分析多种阈值对其影响。因此，为提高特征阈值适应性及快速检测特征点，将FAST角点检测与SURF描述相结合，使特征检测时间压缩到50~1 425倍。文中笔者对选取的64维特征向量运用两种匹配，并在尺寸、旋转、光照变换条件下实验统计匹配率，对两种匹配性能进行对比分析。最后，分别对原始100幅文档图像、压缩1 000幅图像、剪切1 000幅文档图像，基于多种距离度量特征向量间的相似性，检索目标文档图像，将其检索率与基于匹配数目的检索率对比，亮出以匹配数目为检索依据的搜索系统优越性。系统最高检索率都达到100%。

但是，由于原始文档图像篇幅较大，提取的特征点数目较多，特征点之间的匹配点数目也会增大，因此基于匹配数目的检索系统耗用时间比基于距离的检索系统较长，系统检索所占用时间都不太理想。在保证系统较高的检索率的前提下，怎样进一步降低时间开销是下一步研究重点。