第14卷第2期 智能系统学报 Vol.14 No.2 2019年3月 CAAI Transactions on Intelligent Systems Mar.2019 D0:10.11992/tis.201709014 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.tp.20180420.1018.002.html 改进SURF特征的维吾尔文复杂文档图像匹配检索 阿丽亚·巴吐尔，努尔毕亚·亚地卡尔，吾尔尼沙·买买提，阿力木江·艾沙2，库尔班·吾布力 （1.新疆大学信息科学与工程学院，新疆乌鲁木齐，830046；2.新疆大学网络与信息中心，新疆乌鲁木齐， 830046) 摘要：针对图像局部特征的词袋模型(Bag-of-Word,BOW)检索研究中聚类中心的不确定性和计算复杂性问 题，提出一种由不同种类的距离进行相似程度测量的检索和由匹配点数来检索的方法。这种方法首先需要改 进文档图像的SURF特征，有效降低特征提取复杂度；其次，对FAST+SURF特征实现FLANN双向匹配与KD- Tre+BBF匹配，在不同变换条件下验证特征鲁棒性；最后，基于这两种检索方法对已收集整理好的各类维吾尔 文文档图像数据库进行检索。实验结果表明：基于距离的相似性度量复杂度次于基于匹配数目的检索，而且两 种检索策略都能满足快速、精确查找需求。 关键词：复杂文档：维吾尔文档图像：文档图像分割：特征提取：SURF特征：FLANN双向匹配：KD-Tre+BBF匹 配：图像检索 中图分类号：TP391.1文献标志码：A文章编号：1673-4785(2019)02-0296-10 中文引用格式：阿丽亚·巴吐尔，努尔毕亚·亚地卡尔，吾尔尼沙·买买提，等.改进SURF特征的维吾尔文复杂文档图像匹配检 索1.智能系统学报，2019,14(2)：296-305. 英文引用格式：ALIYA Batur,NURBIYA Yadikar,HORNISA Mamat,,etal.Complex Uyghur document image matching and re-. trieval based on modified SURF feature[JI.CAAI transactions on intelligent systems,2019,14(2):296-305. Complex Uyghur document image matching and retrieval based on modified SURF feature ALIYA Batur',NURBIYA Yadikar',HORNISA Mamat',ALIMJAN Aysa',KURBAN Ubul' (1.School of Information Science and Engineering,Xinjiang University,Urumgi 830046,China;2.Network and information center, Xinjiang University,Xinjiang University,Urumqi 830046,China) Abstract:This study is aimed at the uncertainty and computational complexity of the clustering center in local image features retrieval based on the bag-of-words(BOW)model.A method to retrieve the measure of similarity degree from different kinds of distance and another method that requires using the matching point number as the basis of retrieval are proposed in this paper.In this method,the SURF feature is first modified to effectively reduce feature extraction com- plexity,and then FLANN(fast library for approximate nearest neighbors)bidirectional matching and KD-Tree +BBF matching are implemented for FAST+SURF features.Feature robustness is verified under different transformation con- ditions.Finally,all kinds of Uyghur document images that have been classified and sorted based on these two retrieval methods are retrieved.The results of the retrieval experiments indicate that the similarity degree measure retrieval based on distance is inferior to the retrieval based on matching number,and both of these two retrieval strategies can meet the requirements of fast and accurate searching. Keywords:complex document image;Uyghur document image;document image segmentation;feature extraction; SURF feature;FALNN bidirectional matching;KD-Tree+BBF matching;image retrieval 收稿日期：2017-09-17.网络出版日期：2018-04-24 在当今信息技术高速发展的背景下，多媒体 基金项目：国家自然科学基金项目(61563052,61163028， 61363064片新疆大学博士科研启动基金项目BS150262), 技术的发展使文档图像在信息的交换中运用越来 新疆维吾尔自治区高校科研计划创新团队项目 越频繁。日益增长的需求使文档图像的数量越来 (XJEDU2017T002). 通信作者：库尔班吾布力.E-mail:urbanu@xju.edu.cn. 越庞大，这就要求文档图像存储系统能够为用户
DOI: 10.11992/tis.201709014 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.tp.20180420.1018.002.html 改进 SURF 特征的维吾尔文复杂文档图像匹配检索 阿丽亚·巴吐尔1 ，努尔毕亚·亚地卡尔1 ，吾尔尼沙·买买提1 ，阿力木江·艾沙2 ，库尔班·吾布力1 （1. 新疆大学 信息科学与工程学院，新疆 乌鲁木齐，830046; 2. 新疆大学 网络与信息中心，新疆 乌鲁木齐， 830046） 摘 要：针对图像局部特征的词袋模型 (Bag-of-Word, BOW) 检索研究中聚类中心的不确定性和计算复杂性问 题，提出一种由不同种类的距离进行相似程度测量的检索和由匹配点数来检索的方法。这种方法首先需要改 进文档图像的 SURF 特征，有效降低特征提取复杂度；其次，对 FAST+SURF 特征实现 FLANN 双向匹配与 KDTree+BBF 匹配，在不同变换条件下验证特征鲁棒性；最后，基于这两种检索方法对已收集整理好的各类维吾尔 文文档图像数据库进行检索。实验结果表明：基于距离的相似性度量复杂度次于基于匹配数目的检索，而且两 种检索策略都能满足快速、精确查找需求。 关键词：复杂文档；维吾尔文档图像；文档图像分割；特征提取；SURF 特征；FLANN 双向匹配；KD-Tree+BBF 匹 配；图像检索 中图分类号：TP391.1 文献标志码：A 文章编号：1673−4785(2019)02−0296−10 中文引用格式：阿丽亚·巴吐尔, 努尔毕亚·亚地卡尔, 吾尔尼沙·买买提, 等. 改进 SURF 特征的维吾尔文复杂文档图像匹配检 索[J]. 智能系统学报, 2019, 14(2): 296–305. 英文引用格式：ALIYA Batur, NURBIYA Yadikar, HORNISA Mamat, et al. Complex Uyghur document image matching and retrieval based on modified SURF feature[J]. CAAI transactions on intelligent systems, 2019, 14(2): 296–305. Complex Uyghur document image matching and retrieval based on modified SURF feature ALIYA Batur1 ，NURBIYA Yadikar1 ，HORNISA Mamat1 ，ALIMJAN Aysa2 ，KURBAN Ubul1 (1. School of Information Science and Engineering, Xinjiang University, Urumqi 830046, China; 2. Network and information center, Xinjiang University, Xinjiang University, Urumqi 830046, China) Abstract: This study is aimed at the uncertainty and computational complexity of the clustering center in local image features retrieval based on the bag-of-words (BOW) model. A method to retrieve the measure of similarity degree from different kinds of distance and another method that requires using the matching point number as the basis of retrieval are proposed in this paper. In this method, the SURF feature is first modified to effectively reduce feature extraction complexity, and then FLANN (fast library for approximate nearest neighbors) bidirectional matching and KD-Tree + BBF matching are implemented for FAST + SURF features. Feature robustness is verified under different transformation conditions. Finally, all kinds of Uyghur document images that have been classified and sorted based on these two retrieval methods are retrieved. The results of the retrieval experiments indicate that the similarity degree measure retrieval based on distance is inferior to the retrieval based on matching number, and both of these two retrieval strategies can meet the requirements of fast and accurate searching. Keywords: complex document image; Uyghur document image; document image segmentation; feature extraction; SURF feature; FALNN bidirectional matching; KD-Tree+BBF matching; image retrieval 在当今信息技术高速发展的背景下，多媒体 技术的发展使文档图像在信息的交换中运用越来 越频繁。日益增长的需求使文档图像的数量越来 越庞大，这就要求文档图像存储系统能够为用户 收稿日期：2017−09−17. 网络出版日期：2018−04−24. 基金项目：国家自然科学基金项 目 (61563052, 61163028, 61363064)；新疆大学博士科研启动基金项目 (BS150262)， 新疆维吾尔自治区高校科研计划创新团队项 目 (XJEDU2017T002). 通信作者：库尔班·吾布力. E-mail：urbanu@xju.edu.cn. 第 14 卷第 2 期 智 能 系 统 学 报 Vol.14 No.2 2019 年 3 月 CAAI Transactions on Intelligent Systems Mar. 2019
第2期 阿丽亚·巴吐尔，等：改进SURF特征的维吾尔文复杂文档图像匹配检索 ·297· 提供快速高效的检索服务，为了达成这一目标许 王亚文等基于中心-边缘区域比较模板匹配算法 多国内外学者进行了卓有成效的研究。王澎 有效跟踪目标区域，提取SURF特征，将匹配对数 等提出提取图像关键点的64维SURF特征集， 目与模板匹配数目比较自适应调整跟踪窗口，实 计算每一维上的一阶中心矩与加权绝对中心矩， 现目标检测。这些方法分别对特征提取和匹配方 形成特征向量，将其作为SVM分类的依据，对1000 式进行不同程度的改进，但是检索时间或检索准 幅图片进行分类，获得86.8%的正确分类率。赵 确率需要进一步提高。 璐璐等4，对提取的64维SURF特征点，基于 本文提取改进的W×64维SURF特征，并对其 FLANN算法进行双向匹配，对匹配对进行PROSAC 实现FLANN双向匹配，依次统计匹配性能参数， 分析，剔除误匹配对，提高图像匹配精度，有效缩 并将其作为相似性度量依据，从大规模图像数据 短匹配占用时间。闫丽等，扩展Haar响应，生成 库中有效检索输出目标文档图像。此外，为降低 包含线特征、中心环绕特征、角点特征的Haar- 检索复杂度，笔者运用基于距离的相似性度量方 Lik特征集，提高描述子的区分率，基于欧氏距 离比实现遥感图像的快速准确匹配。陈剑虹等) 法，快速查找目标文档图像。 提出改进SURF关键点检测，提取图像细节区域 1FAST+SURF特征提取 的特征点，不经过非极大值抑制有效去除边缘点 与低对比点，将优先队列(BBF)融入到KD-Tree 本文对细节信息丰富的维吾尔文复杂文档图 双向匹配中，实现稳定、快速鲁邦特征的精确匹 像进行研究，不对其进行版面分析，对改进 配。罗楠等对SURF特征描述进行改进，用改 SURF特征实现脱离于词袋模型的检索方法，从 进DAISY描述算子为每个关键点分配主方向，形 大规模图像数据库中实现有效检索。本文算法流 成维数为200的特征向量，并通过最近邻距离比 程如图1所示。 NNDR)匹配目标图像，其最大匹配率达到95.78%。 维文复杂文档 复杂文档图像数据库 扫描 FAST关键点检测 FAST关键点检测 SURF特 征向量 SURF特征 SURF特征 FLANN双向匹配 RANSAC分析 基于匹配点数的检索 将检索结果 基于欧式距离的检索 输出给用户 图1基于改进SURF特征的维吾尔文印刷体复杂文档图像检索流程框图 Fig.1 The block diagram of Uyghur printed complex document image retrieval based on modified SURF feature
提供快速高效的检索服务，为了达成这一目标许 多国内外学者进行了卓有成效的研究[1-2]。王澎 等 [3]提出提取图像关键点的 64 维 SURF 特征集， 计算每一维上的一阶中心矩与加权绝对中心矩， 形成特征向量，将其作为 SVM 分类的依据，对 1 000 幅图片进行分类，获得 86.8% 的正确分类率。赵 璐璐等[4-5] ，对提取的 64 维 SURF 特征点，基于 FLANN 算法进行双向匹配，对匹配对进行 PROSAC 分析，剔除误匹配对，提高图像匹配精度，有效缩 短匹配占用时间。闫丽等[6] ，扩展 Haar 响应，生成 包含线特征、中心环绕特征、角点特征的 HaarLike 特征集，提高描述子的区分率，基于欧氏距 离比实现遥感图像的快速准确匹配。陈剑虹等[7] 提出改进 SURF 关键点检测，提取图像细节区域 的特征点，不经过非极大值抑制有效去除边缘点 与低对比点，将优先队列 (BBF) 融入到 KD-Tree 双向匹配中，实现稳定、快速鲁邦特征的精确匹 配。罗楠等[8]对 SURF 特征描述进行改进，用改 进 DAISY 描述算子为每个关键点分配主方向，形 成维数为 200 的特征向量，并通过最近邻距离比 (NNDR) 匹配目标图像，其最大匹配率达到 95.78%。 王亚文等[9]基于中心-边缘区域比较模板匹配算法 有效跟踪目标区域，提取 SURF 特征，将匹配对数 目与模板匹配数目比较自适应调整跟踪窗口，实 现目标检测。这些方法分别对特征提取和匹配方 式进行不同程度的改进，但是检索时间或检索准 确率需要进一步提高。 本文提取改进的 N×64 维 SURF 特征，并对其 实现 FLANN 双向匹配，依次统计匹配性能参数， 并将其作为相似性度量依据，从大规模图像数据 库中有效检索输出目标文档图像。此外，为降低 检索复杂度，笔者运用基于距离的相似性度量方 法，快速查找目标文档图像。 1 FAST+SURF 特征提取 本文对细节信息丰富的维吾尔文复杂文档图 像进行研究，不对其进行版面分析，对改 进 SURF 特征实现脱离于词袋模型的检索方法，从 大规模图像数据库中实现有效检索。本文算法流 程如图 1 所示。 维文复杂文档 复杂文档图像数据库 扫描 基于欧式距离的检索 SURF 特 征向量 将检索结果 输出给用户 FAST 关键点检测 SURF 特征 FAST 关键点检测 SURF 特征 基于匹配点数的检索 FLANN 双向匹配 RANSAC 分析 图 1 基于改进 SURF 特征的维吾尔文印刷体复杂文档图像检索流程框图 Fig. 1 The block diagram of Uyghur printed complex document image retrieval based on modified SURF feature 第 2 期 阿丽亚·巴吐尔，等：改进 SURF 特征的维吾尔文复杂文档图像匹配检索 ·297·
·298· 智能系统学报 第14卷 图1中的快速鲁棒特征(SURF)提取过程与 点的Hessian迹回，其表达式为 SFT相似，由关键点检测与特征描述两部分构成。 Det(H=DxDn-(0.9Dy)月 (3) 但其维持图像尺寸不变，以倍数关系改变盒子滤波 器的尺寸、尺度，在积分图像的基础上滤波构建 尺度空间，使得特征检测耗用时间远短于SFT。在 5199147195 27517599] 特征描述中，统计扇形区域内的Haar小波响应 5273951☐ 值，确定关键点的主方向，累加统计划分区域内XY 9152127 方向的Haar值与Haar绝对值，降低计算复杂度。 Scale 1.1原始SURF特征向量提取 计算灰度图像在(x,y)处的积分值，并与不同 图2SURF尺度空间示意 尺度下的高斯函数二阶偏导数做卷积运算。为降 Fig.2 Schematic diagram of SURF scale space 低计算复杂度，用不同尺寸、尺度的盒子滤波器 在尺度空间被检测出的关键点对文档图像的 近似替代卷积结果，形成不同尺寸条件下的Hessian 尺寸、平移和旋转有鲁棒性。给SURF局部特征 矩阵行列式。最后，计算Hessian行列式的迹，并 点分配主方向来保证其旋转不变。以5°为量级， 与相邻尺度下的26个像素点进行非极大值抑制 在60°滑动扇形区域内累加求和每一个像素点在 NMS)运算，获取SURF关键点的精确位置Io-, 水平、垂直方向上的Haar小波响应分量，求其最 其数学表达式如下： 大值作为此关键点主方向。以关键点为中心 iX jY 〉Gray(i,ji) 取20×20区域，将这个区域又按4×4的大小划分 (1) 00 成25个子区域，然后依次计算每个小区域的像素 H(x,σ)= Lu(x,) Lg(x,σ) 点的水平方向和垂直方向的Haar值以及绝对和 L(x,σ）Lm(x,o) (2) 值，最后将提取64维SURF特征向量。 D(x,)D(x.) D(x,)Dv(x,) 1.2改进SURF特征提取 式中：Isn为积分图像，Hx,o)为Hessian矩阵行 原始SURF特征相比于SIFT,被检测特征点 列式，L(x,o)、L,x,o)分别为X方向、Y方向的二 数目少、特征提取占用时间短。但是，对于图文 阶偏导数卷积，L,(x,σ)、L(x,σ)为混合偏导数卷 混排的复杂文档图像，缩短时间参量不理想。因 积。D(x,σ)为盒子滤波近似值。对应SIFT,构 此，为实现维文复杂版面图像中关键点的快速检 建4组尺度空间，每组含有不同尺寸、尺度下的 测，本文提取文档图像的灰度信息和角点。检测 盒子滤波。其层次表达如图2所示。 角点时用FAST算法，并用SURF算子描述，构成 当盒子滤波器尺寸为W×N时，其对应的高斯 64维FAST+SURF特征，有效缩短特征提取时 尺度为s=0×N/9,其中o=1.2。尺度空间中取每 间。其特征检测算法流程如图3所示。 求所有像素点与中心点的差值的 以像素点P。为中心，在=3的圆上，取 开始 总和S,作为FAST值。 16个像素点 比较以P。为中心的3×3领域内。 所有被检测角点的FAST得分值 P-PKr且p,PKa y S-S N Pg-Pat且pplt Y Y P。为关键点 遗弃 P-PK红，其中 =1-16,if(i》9) 结束 遗弃 Y 图3改进SURF特征关键点检测流程框图 Fig.3 Flow chart of improved SURF feature key point detection
图 1 中的快速鲁棒特征 (SURF) 提取过程与 SIFT 相似，由关键点检测与特征描述两部分构成。 但其维持图像尺寸不变，以倍数关系改变盒子滤波 器的尺寸、尺度，在积分图像的基础上滤波构建 尺度空间，使得特征检测耗用时间远短于 SIFT。在 特征描述中，统计扇形区域内的 Haar 小波响应 值，确定关键点的主方向，累加统计划分区域内 X、Y 方向的 Haar 值与 Haar 绝对值，降低计算复杂度。 1.1 原始 SURF 特征向量提取 计算灰度图像在 (x, y) 处的积分值，并与不同 尺度下的高斯函数二阶偏导数做卷积运算。为降 低计算复杂度，用不同尺寸、尺度的盒子滤波器 近似替代卷积结果，形成不同尺寸条件下的 Hessian 矩阵行列式。最后，计算 Hessian 行列式的迹，并 与相邻尺度下的 26 个像素点进行非极大值抑制 (NMS) 运算，获取 SURF 关键点的精确位置[10-11] ， 其数学表达式如下： I ∑ (X,Y) = ∑i≪X i=0 ∑ j≪Y j=0 Gray(i, j) (1) H (x,σ) = [ Lxx (x,σ) Lxy (x,σ) Lyx (x,σ) Lyy (x,σ) ] = [ Dxx (x,σ) Dxy (x,σ) Dyx (x,σ) Dyy (x,σ) ] (2) 式中： I∑(X,Y)为积分图像，H(x, σ) 为 Hessian 矩阵行 列式，Lxx(x, σ)、Lyy(x, σ) 分别为 X 方向、Y 方向的二 阶偏导数卷积，Lxy(x, σ)、Lyx(x, σ) 为混合偏导数卷 积。Dxx(x, σ) 为盒子滤波近似值。对应 SIFT，构 建 4 组尺度空间，每组含有不同尺寸、尺度下的 盒子滤波。其层次表达如图 2 所示。 当盒子滤波器尺寸为 N×N 时，其对应的高斯 尺度为 s=σ0×N/9，其中 σ0=1.2。尺度空间中取每一 点的 Hessian 迹 [12] ，其表达式为 Det(H) = DxxDyy − ( 0.9Dxy)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 所示。 Octaves Scale 51 99 147 195 27 51 75 99 15 15 27 9 21 27 39 51 图 2 SURF 尺度空间示意 Fig. 2 Schematic diagram of SURF scale space 开始 结束 以像素点 Po 为中心，在 r=3 的圆上，取 16 个像素点 遗弃 Po 为关键点 |P1−P0 |<τ 且 |p9−p0 |<τ S>Si 比较以 Po 为中心的 3×3 领域内， 所有被检测角点的 FAST 得分值 |P5−P0 |<τ 且 |p13−p0 |<τ |Pi−P0 |<τ, 其中 i=1−16，if (i>>9) 遗弃 求所有像素点与中心点的差值的 总和 S，作为 FAST 值。 N Y Y Y N N N Y 图 3 改进 SURF 特征关键点检测流程框图 Fig. 3 Flow chart of improved SURF feature key point detection. ·298· 智 能 系 统 学 报 第 14 卷
第2期 阿丽亚·巴吐尔，等：改进SURF特征的维吾尔文复杂文档图像匹配检索 ·299· 获取具有平移、缩放不变性的关键点后，为 维持旋转不变性，给被检测的FAST关键点进行 SURF描述，统计划分子区域内Haar小波响应的 水平、垂直分量累加值与绝对累加值，形成N×64 维特征。 2FAST+SURF特征匹配分析 如果采用传统的方法进行特征匹配不仅计算 (a)改进的SURF特征匹配效果图 量大，耗时长，而且系统的内存占用率较高。维 吾尔文复杂文档图像的文字区域中存在较多的黑 像素信息，被检测关键点数目较多。因此，为有 效提高匹配速率，笔者对不同版面图像实现双向 快速近似最近邻(FLANN)匹配，将其结果与KD- Tree+BBF匹配结果进行对比分析，以系统性能作 为基本出发点来构建匹配系统，从而使系统能够 对复杂的维吾尔文文档图像进行高效的检索。 2.1双向FLANN匹配 (b)匹配点关系图 设用户输入查询图像与维吾尔文复杂文档图 图4改进SURF特征双向FLANN匹配示意 像库中，待匹配图像的改进SURF特征向量集分 Fig.4 Schematic diagram of improved SURF features bid- 别为A=[xx2…xwJ厂，B=y12…ywJ「。通过计算 irectional FLANN matching x到特征向量B的最大和最小距离，并设定阈值 输入64维数据集合，计算每一维上的 为=pxMin,。如果计算所得距离小于设定阈值，则 最大方差D=E(x-E(x 记录该点并等待进一步匹配计算，如果距离大于 设定阈值，则继续进行其他点的匹配。由于FLANN 取MaxD)]对应的i,并计算i中数据点 算法具有匹配速度快的特点，所以本文采用FLANN 的中值(Median)为根节点(Node-date) 算法进行匹配，并在先后两个方向同时开始匹 ! 配，这样能够快速获得所需匹配对的相似性信 息，从而进行进一步的判断。具体为：先从A到B vp与Node-date()比较 的方向开始匹配，然后再从B到A的方向进行匹 递归上述过程，在左右子树数据 配，分别形成位置信息集合{m,m与{m,m}。这 集中依次选定父节点，再分左右 子树，当找到叶点分割结束 样逐次将m的大小与m进行比较，如果大小相同 则说明m完全匹配。同时在匹配过程中通过 (a)KD-Tree建立流程I RANSAC算法求出将要进行匹配的点与影射矩 阵的距离，并用此距离与设定的距离阈值进行比 输入查询点Q 沿根一父→叶方向 进行二叉搜索 较，这样做的目的是为了能够比较有效地去掉误 匹配点对，从而使个匹配点对能够准确地匹配。 经过回潮操作，用优先级顺序访问待回潮 原始图像FALNN双向匹配结果如图4所示。 树分支，再以查询点为圆心且通过叶子点 2.2KD-Tree+BBF匹配 的圆内域查找最近邻点 KD-Tree的匹配主要由树形结构的建立与最 近领查找等两个部分组成。KD-Tree搜索能力与 求出查询点到最近邻与次近邻点的 特征向量的维数相关，维数越大，搜索能力越 距离，将距离比与國值比较，求出 最佳匹配特征点 差。因此，本文从改进的KD-Tree出发，将得到 的距离结果与预设的阈值相比较，判断是否为匹 (b)特征匹配过程 配关键点。本文中对改进64维SURF特征实 图5改进KD-Tree匹配过程描述 现改进KD-Tree匹配的过程如图5所示。 Fig.5 The description of improved KD-Tree matching
获取具有平移、缩放不变性的关键点后，为 维持旋转不变性，给被检测的 FAST 关键点进行 SURF 描述，统计划分子区域内 Haar 小波响应的 水平、垂直分量累加值与绝对累加值，形成 N×64 维特征。 2 FAST+SURF 特征匹配分析 如果采用传统的方法进行特征匹配不仅计算 量大，耗时长，而且系统的内存占用率较高。维 吾尔文复杂文档图像的文字区域中存在较多的黑 像素信息，被检测关键点数目较多。因此，为有 效提高匹配速率，笔者对不同版面图像实现双向 快速近似最近邻 (FLANN) 匹配，将其结果与 KD− Tree+BBF 匹配结果进行对比分析，以系统性能作 为基本出发点来构建匹配系统，从而使系统能够 对复杂的维吾尔文文档图像进行高效的检索。 2.1 双向 FLANN 匹配 A = [x1 x2 ··· xN] T B = [y1 y2 ··· yN] T xi { m A j ,m B k } { m B k ,m A ′ j } m A j m A ′ j m B k 设用户输入查询图像与维吾尔文复杂文档图 像库中，待匹配图像的改进 SURF 特征向量集分 别为 ， 。通过计算 到特征向量 B 的最大和最小距离，并设定阈值 为 γ=ρ×Mini。如果计算所得距离小于设定阈值，则 记录该点并等待进一步匹配计算，如果距离大于 设定阈值，则继续进行其他点的匹配。由于 FLANN 算法具有匹配速度快的特点，所以本文采用 FLANN 算法进行匹配，并在先后两个方向同时开始匹 配，这样能够快速获得所需匹配对的相似性信 息，从而进行进一步的判断。具体为：先从 A 到 B 的方向开始匹配，然后再从 B 到 A 的方向进行匹 配，分别形成位置信息集合 与 。这 样逐次将 的大小与 进行比较，如果大小相同 则说明 完全匹配。同时在匹配过程中通 过 RANSAC 算法求出将要进行匹配的点与影射矩 阵的距离，并用此距离与设定的距离阈值进行比 较，这样做的目的是为了能够比较有效地去掉误 匹配点对，从而使个匹配点对能够准确地匹配。 原始图像 FALNN 双向匹配结果如图 4 所示。 2.2 KD−Tree+BBF 匹配 KD−Tree 的匹配主要由树形结构的建立与最 近领查找等两个部分组成。KD−Tree 搜索能力与 特征向量的维数相关，维数越大，搜索能力越 差。因此，本文从改进的 KD−Tree 出发，将得到 的距离结果与预设的阈值相比较，判断是否为匹 配关键点[15]。本文中对改进 64 维 SURF 特征实 现改进 KD−Tree 匹配的过程如图 5 所示。 (a) 改进的 SURF 特征匹配效果图 (b) 匹配点关系图 图 4 改进 SURF 特征双向 FLANN 匹配示意 Fig. 4 Schematic diagram of improved SURF features bidirectional FLANN matching 输入 64 维数据集合，计算每一维上的 最大方差 D(i)=E(x_i 2 )−[E(x_i)]2 取Max[D(i)]对应的 i，并计算 i 中数据点 的中值 (Median) 为根节点 (Node-date) υp 与 Node-date (i) 比较 递归上述过程，在左右子树数据 集中依次选定父节点，再分左右 子树，当找到叶点分割结束 左子树 右子树 (a) KD-Tree 建立流程[16] 输入查询点 Q 沿根→父→叶方向 进行二叉搜索 经过回溯操作，用优先级顺序访问待回溯 树分支，再以查询点为圆心且通过叶子点 的圆内域查找最近邻点 求出查询点到最近邻与次近邻点的 距离，将距离比与阈值比较，求出 最佳匹配特征点 (b) 特征匹配过程 图 5 改进 KD−Tree 匹配过程描述 Fig. 5 The description of improved KD−Tree matching 第 2 期 阿丽亚·巴吐尔，等：改进 SURF 特征的维吾尔文复杂文档图像匹配检索 ·299·
·300· 智能系统学报 第14卷 匹配系统在不同变换条件下的匹配效率一般 不同分辨率(100dpi,200dpi,400dpi)扫描形成 是由匹配率(MR)、正确匹配率(CMR)与错误匹 8位的.bmp格式的维文复杂文档图像，构造含有 配率(MR)来衡量，它们计算公式分别为 1000幅不同分辨率、不同底色信息、不同版面结 Ne 构的复杂文档图像的数据库。本系统是在Win- MR= Na (4) dows7环境下用Visual Studio20l0+openCV- CMR=N 2.4.10编程开发的。 (5) Ne 4.2实验结果与分析 SURF特征在检测的时候主要是靠尺度空间 IMR (6) 层数(Octaves)、组数(Intervals)、斑点(THRES)阈 值的选择。阈值(Octaves,Intervals,Init-sample, 式中：N和N分别为总匹配对数目和被检测的 THRES)选定的不同，提取的特征点数目也不相 特征点数；Nc和N分别指正确匹配对总数和错 同。为验证FAST+SURF特征的效率，在不同的 误匹配对总数。 阈值条件下，对1606×2290的同一张图像进行实 3维吾尔文复杂文档图像检索 验，统计关键点数和特征提取时间，实验结果如 表1给出。 用户输入查询复杂文档图像，系统自动获取 表1在不同阈值条件下同一幅图像检测的参数统计表% 64维改进SURF特征向量，与特征向量库之间基 Table 1 The statistical table of detecting parameters using 于多种相似性度量算法，从数据库中查找目标文 the same image under different threshold condi- 档图像，返回用户界面。本文运用两种相似性度 tionss 量算法实现用户特定目标文档图像的检索，即基 阈值 阈值参数 关键点数 特征提取时间s 于距离的相似性度量与基于匹配数目的相似性度 0.0004f 9290 38.536 量。文中用4种特征向量间距离相似性度量算 (4,4,2) 0.004f 2290 19.248 法，其数学表达式为 0.04f 0 10.195 dEnelidean =V(x1-X2)2+(y1-y2) (7) 0.0004f 9290 38.262 dManhattan =1-X2+ly1-y2l (8) (4,3,2) 0.004f 2290 19.378 dchebyshev max (l1-x2l,ly1-y2D) (9) 0.04f 0 10.29 X1X2+Y1y2 dCosine= (10) 0.0004f 9177 37.833 Vx2+x22vy2+y22 (3,3,2) 0.004f 2982 19.326 对于同一个查询文档图像的改进SURF特征 0.04f 0 10.221 向量，基于上述四种距离分别度量相似性，实现 0.0004f 9177 37.811 维吾尔文复杂文档图像的检索，以检索率为系统 (3,42) 0.004f 2982 19.275 性能指标，评估本系统有效性。在以匹配数目为 0.04f 0 10.134 检索依据的检索系统中，从匹配数目和正确匹配 数目考虑，统计查询图像与图像库中每幅图像之 从表1可以得到，尺度空间阈值的变化对 间的正确匹配数目，将其按降序排序，实现文档图 SURF特征点的检测尤为重要。层数与层间组数 像的有效检索。其中越相似复杂文档图像，则其 的变化由改变盒子滤波器数目来实现，其影响表 匹配数目越大。本文计算系统检索率的表达式为 现在对积分图像的处理上，且特征检测耗用时间 R=N-S (11) 上有微小差异。阈值的变化极大影响了最终检索 N-1 结果。对于每一个候选点，取其上下邻域空间中 式中：N是指复杂文档图像数据总的样本数，S是 的26个像素点，相互比较Hessian矩阵行列式 指系统检索出来的目标文档图像的位置序号。 值。若候选点Hessian行列式值比26个像素点行 4实验结果与分析 列式值都大或都小且小于阈值，则此候选点视为 关键点。本文考虑多个阈值参数对SURF关键点 4.1实验数据 检测的影响，并为减少时间和计算复杂度，提出 收集维吾尔文复杂版面书籍、杂志、公文，以 了FAST+SURF特征提取算法。为验证该方法的
匹配系统在不同变换条件下的匹配效率一般 是由匹配率 (MR)、正确匹配率 (CMR) 与错误匹 配率 (IMR) 来衡量，它们计算公式分别为 MR = Nc Nd (4) CMR = Nac Nc (5) IMR = Nai Nc (6) 式中：Nc 和 Nd 分别为总匹配对数目和被检测的 特征点数；Nac 和 Nai 分别指正确匹配对总数和错 误匹配对总数。 3 维吾尔文复杂文档图像检索 用户输入查询复杂文档图像，系统自动获取 64 维改进 SURF 特征向量，与特征向量库之间基 于多种相似性度量算法，从数据库中查找目标文 档图像，返回用户界面。本文运用两种相似性度 量算法实现用户特定目标文档图像的检索，即基 于距离的相似性度量与基于匹配数目的相似性度 量。文中用 4 种特征向量间距离相似性度量算 法，其数学表达式为 dEuclidean = √ (x1 − x2) 2 +(y1 −y2) 2 (7) dManhattan = |x1 − x2|+|y1 −y2| (8) dChebyshev = max(|x1 − x2|,|y1 −y2|) (9) dCosine = x1 x2+y1y2 √ x1 2 + x2 2 √ y1 2 +y2 2 (10) 对于同一个查询文档图像的改进 SURF 特征 向量，基于上述四种距离分别度量相似性，实现 维吾尔文复杂文档图像的检索，以检索率为系统 性能指标，评估本系统有效性。在以匹配数目为 检索依据的检索系统中，从匹配数目和正确匹配 数目考虑，统计查询图像与图像库中每幅图像之 间的正确匹配数目，将其按降序排序，实现文档图 像的有效检索。其中越相似复杂文档图像，则其 匹配数目越大。本文计算系统检索率的表达式为 R = 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 在不同阈值条件下同一幅图像检测的参数统计表[16] Table 1 The statistical table of detecting parameters using the same image under different threshold conditions[16] 阈值 阈值参数 关键点数 特征提取时间/s (4, 4, 2) 0.000 4f 9 290 38.536 0.004f 2 290 19.248 0.04f 0 10.195 (4, 3, 2) 0.000 4f 9 290 38.262 0.004f 2 290 19.378 0.04f 0 10.29 (3, 3, 2) 0.000 4f 9 177 37.833 0.004f 2 982 19.326 0.04f 0 10.221 (3, 4, 2) 0.000 4f 9 177 37.811 0.004f 2 982 19.275 0.04f 0 10.134 从表 1 可以得到，尺度空间阈值的变化对 SURF 特征点的检测尤为重要。层数与层间组数 的变化由改变盒子滤波器数目来实现，其影响表 现在对积分图像的处理上，且特征检测耗用时间 上有微小差异。阈值的变化极大影响了最终检索 结果。对于每一个候选点，取其上下邻域空间中 的 26 个像素点，相互比较 Hessian 矩阵行列式 值。若候选点 Hessian 行列式值比 26 个像素点行 列式值都大或都小且小于阈值，则此候选点视为 关键点。本文考虑多个阈值参数对 SURF 关键点 检测的影响，并为减少时间和计算复杂度，提出 了 FAST+SURF 特征提取算法。为验证该方法的 ·300· 智 能 系 统 学 报 第 14 卷