第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 bid￾irectional 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·