基于层级匹配的维吾尔文关键词文档图像检索

李静静，木特力甫·马木提，吾尔尼沙·买买提，阿力木江·艾沙，库尔班·吾布力+

(1.新疆大学 信息科学与工程学院，新疆 乌鲁木齐 830046；2.新疆大学 图书馆，新疆 乌鲁木齐 830046；3.新疆大学 教师工作部，新疆 乌鲁木齐 830046)

0 引 言

随着信息技术的发展，文档图像检索成为图像检索领域的热门研究方向。传统的基于字识别技术(optical character recognition)的方法人工需求量大、操作成本高，基于图像特征的文档图像检索方法应运而生，其操作简单、运行速度快且无需人工干预。目前基于图像特征的文档检索主要分为基于文档页面内容相似性的检索与基于关键词的检索。其中以关键词为研究对象能有效替代OCR识别技术。

关键词识别技术最先在语音识别领域中应用，于20世纪90年代应用于图像检索领域。近年来魏宏喜等[1]设计了基于word spotting技术的蒙古文历史文档图像检索框架，用轮廓特征、投影特征和笔划穿越数目表示单词图像，将视觉模型融入BOVW模型中[2]并用金字塔匹配将一种空间信息引入到数据集中；喻庚[3,4]等提出采用过切分、字符识别器模型和集束搜索的脱机手写中文文档的关键词检索系统框架；鲍玉来等[5]提出基于LDA的主题模型，采用查询似然模型实现检索，完善蒙古文历史文献关键词检索框架。

对于维吾尔文文档图像的检索，目前仅有阿丽亚·巴吐尔[6]对图文混排的复杂版面结构维吾尔文档图像进行研究，而基于关键词的维吾尔文文档图像检索领域仍处于空白。本文设计了一种基于关键词的维吾尔文文档图像检索框架，采用由粗到细的层级匹配方式。在粗匹配阶段采用模板匹配的方法，对经过粗匹配筛选的图像进行两种HOG特征向量的提取，最后采用SVM算法进行关键词精确匹配。

1 基于关键词的文档图像检索研究

本文提出的基于关键词的维吾尔文文档图像检索方法主要包括5个部分：图像预处理、单词切分、模板匹配、特征提取、分类识别，具体框架如图1所示。将采集的文档图像进行预处理操作并对其进行单词切分形成单词图像数据库，将选定的关键词图像作为模板并对其进行预处理操作，在单词图像数据库中使用基于标准欧式距离的模板匹配进行粗匹配来构造关键词样本集合、非关键词样本集合和有待进一步检索的粗匹配单词图像集合，然后对训练集中单词图像提取HOG特征，并使用SVM分类器对特征数据进行学习得到分类模型，将检索结果返回给用户。

图1 基于关键词的文档图像检索系统框架

1.1 文档图像采集和预处理

本文通过对维吾尔文书籍进行扫描，建立了包含2414张图像的文档图像数据库。其中，图像分辨率为100 dpi，深度为8，格式为*.bmp，本文实验随机抽取其中108张。在将纸质文本扫描文档图像的过程中，如果纸质文本含有背景或者其它的噪音，会对图像质量造成影响，从而影响提取特征中所包含的有效信息，因此需要在使用之前进行预处理。本文对如图2(a)进行预处理操作，包括灰度化、二值化、噪声去除及倾斜校正等，效果如图2(b)所示。

图2 文档图像预处理

本文灰度化是采用加权平均法，根据重要性及其它指标，将3个分量以不同的权值进行加权平均；二值化是使用OTSU算法，是一种基于全局的算法，根据图像的灰度特性，将图像分为前景和背景两个部分；在噪声去除阶段，本文使用的是双边滤波的方法，同时考虑了图像像素点的空间信息和灰度相似性信息，在保留图像的边缘的情况下去除噪声来保证图像的清晰度；对于倾斜校正，本文采取常用的基于Hough变换的方式。

1.2 维吾尔文档图像单词切分

文献[7]中使用了连体段特征聚类的方式对图文混排版面的维吾尔文文档图像进行单词切分。本文为纯文本版面，结合形态学分析与像素积分投影法完成印刷体维吾尔文文档图像的单词切分。由于维吾尔文印刷体文档图像中行与行间隙明显，单词之间与其内部间隙相比较大。因此本文先对图像进行膨胀处理，接着通过水平投影和垂直投影对其进行切分，实验效果如图3所示。

图3 切分图像

本实验对随机抽取的108张维吾尔文文档图像做了单词切分，每张文档图像大概能够产生200张多单词图像，形成规模为25 569的单词图像数据库。经验证，本文所使用的单词切分法达到了98.7%的准确率。为了保证后续检索效果，本文所使用的单词图像数据库已删除误切分的单词图像并过滤了无意义的切分图像。

2 文档图像检索主要方法

2.1 基于欧式距离的模板匹配

对于印刷体文本而言，模板匹配[8]是一种具有代表性的字符识别方法。该方法通过计算测试字符和模板字符之间的距离或相似度来识别字符，距离最小或者相似度最大的那类模板将被视为最终的判别类。首先建立模板库，将待识别字符图像进行二值化并将其尺寸大小归一化到模板字符进行匹配，最后根据匹配程度决定所属类别。采用标准欧式距离来度量匹配程度，其公式如下

(1)

式中：X为关键词模板图像，Y为切分数据库中单词图像，d(X,Y) 为两个图像间的欧氏距离，xi和yi分别为两张图像上对应点的像素值。

2.2 HOG特征提取

方向梯度直方图(histogram of oriented gradient，HOG)是一种对像素点求取梯度幅值和方向的特征[9]，最初用于行人检测中，并取得了较好的效果。HOG特征是一种局部区域上的梯度方向直方图构成的图像特征，其特征提取流程如图4所示。本文设I为输入图像，I(x,y)表示图像在像素点 (x,y) 处的灰度值，具体提取步骤描述如下。

图4 HOG提取流程

(1)预处理，使用归一化将图像转化为灰度图像，接着进行“伽马校正”；

(2)计算预处理后图像上每个像素点的梯度，捕获轮廓信息和纹理信息，同时进一步弱化光照的干扰。

先对图像每个像素点 (x,y) 横坐标、纵坐标两个方向的梯度值求解

Gx(x,y)=I(x+1,y)-I(x-1,y)

(2)

Gy(x,y)=I(x,y+1)-I(x,y-1)

(3)

式中：Gx(x,y)、Gy(x,y) 分别代表在像素点 (x,y) 处的水平方向梯度和垂直方向梯度的像素值。接下来计算图像中每个像素的梯度方向值，得出物体的轮廓信息和纹理信息。像素点 (x,y) 的梯度幅值和梯度方向计算公式为

(4)

α(x,y)=arctan(Gy/Gx)

(5)

(3)将输入图像按设定尺寸划分成相同规模的cells；

(4)对每个cell的梯度直方图中不同梯度的个数分别进行统计，就可以构成cell的描述子；

(5)将几个相邻的cell构成block块，相邻cell特征描述子串联起来即为整个block的HOG特征描述子；

(6)通过对输入图像中每个block的HOG特征描述子的串联，获得该目标图像的完整HOG特征描述子。

2.3 SVM分类器

支持向量机(support vector machine，SVM)是一种监督式学习算法[10]。SVM学习算法在小样本学习、非线性数据分类和高维度识别分类中具有较明显的优势。SVM算法能将非线性分类的问题通过松弛变量和核函数的选择来进行解决。其中对于线性分类问题，假设训练样本集Train={(x1,y1),(x2,y2),…,(xN,yN)}， 当中类别yi∈{-1,1}， 通过线性SVM学习可用一个超平面C划分为两部分，如图5所示。

图5 二分类

(6)

对于线性可分的情况，特征向量x满足相应的分类决策方程组

(7)

分别找到两类中距离分类超平面距离C最小的样本点，过两点平行于分类超平面构成两个平面C1、C2， 两个平面之间的距离称为distance。经计算

(8)

对于非线性分类问题，需要将低维空间的输入特征向量映射到高维特征空间中，再通过松弛变量和核函数的选择进行解决。常用核函数类型有线性核函数、径向基核函数和多项式核函数。

3 基于层级匹配的维吾尔文关键词文档图像检索

本文提出了一种由粗到细层级匹配的方法来完成基于关键词的维吾尔文文档图像检索。在前期合适的预处理和精准单词切分的基础上，采用基于模板匹配的粗匹配和在特征提取基础之上使用SVM的精确匹配来完成基于关键词的维吾尔文文档图像检索。

3.1 基于模板匹配的粗匹配

本文基于前期单词图像的准确切分，使用选定关键词和单词图像数据库完成关键词的粗匹配。首先将所选择的关键词作为模板图像并进行预处理，接着将切分数据库中的单词图像尺寸归一化到模板关键词图像尺寸大小，最后与模板关键词图像使用标准欧式距离进行匹配运算。本文模板匹配算法的伪代码如下所示：

算法1： 基于欧式距离的模板匹配

输入： image(关键词模板图像)

输出： positive_set (关键词样本集合)、 negativeset_set (非关键词样本集合)、 coarse_set粗匹配单词集合

(1) pre(image); //对关键词模板预处理

(2) for(inti=1;i<=P;i++) //P为文档图像页数

(3) {

(4) for(intj=1;j

(5) {

(6) image1=读取单词数据库 //读取单词图像

(7) RSize(image1);//单词图像归一化到关键词模板尺寸大小

(8) pre(image1); //预处理单词图像

(9) D=distance(image,image1,CV_L2);//计算图像的欧式距离

(10) if(D<=d1) //欧式距离小于d1时，将图像放入关键词集合

(11) {

(12) positive_set. push(image1);

(13) }

(14) if(D

(15) {

(16) coarse_set. push(image1);

(17) }

(18) if(D>d3) //距离小于d3时，将图像放入非关键词集合

(19) {

(20) negativeset.push(image1);

(21) }

(22) }

(23) }

关键词的粗匹配阶段通过对欧式距离设定合适的阈值构造关键词样本集合、非关键词样本集合以及粗匹配筛选的单词图像集合。在上述算法过程中，d1

3.2 HOG特征提取过程

特征提取是整个文档图像检索过程的关键步骤，从单词图像中提取有意义的信息，减少所需的存储空间，使系统在文档图像检索方面更加快速有效。单一的特征提取很难达到满意的效果，恰当的对不同特征提取方法进行融合可以取得更完善的特征向量。本文使用如图6所示的两种方式提取HOG特征，一种是在预处理之后直接提取HOG特征向量，另一种是预处理之后在将图像细化提取骨架的基础之上提取HOG特征向量，最后将两种HOG特征串联融合。

图6 特征提取

在文字识别的系统中，字符笔划及其相对位置关系是重要的结构特征。为了准确提取字符笔划及其位置特征，本文采用细化[11]的方法对字符进行骨架特征提取。该方法是一种预处理操作，能够在连续擦除字符边缘像素的同时保持字符像素的拓扑连接关系不产生丝毫的变化，使之成为一个像素宽度的图像骨架。

对训练样本集合中的图像进行梯度方向直方图(HOG)特征提取之前，需要设定一些必要的参数，这些参数会对检测效果产生重要的影响。本实验中将梯度方向直方图提取参数设定见表1。

本文将16×16像素的检测窗口划分若干个为8×8像素的胞元，梯度方向量化为9。其中，每一个胞元的梯度直方图能够构成该胞元的特征描述子；本文把4个8×8像素相邻的胞元链接，形成一个16×16像素的block块，将一个block块内4个尺寸相同胞元的特征描述子串联起来构成整个block块的HOG特征描述子；最后，将16×16像素检测窗口内包含的所有块的HOG特征描述子串联融合得到整个窗口的HOG特征描述子。本文融合前HOG特征描述子维度为36维，融合后为72维。

表1 HOG参数

3.3 SVM分类过程

本文将关键词检索问题转换成若干个二分类问题来解决，在粗匹配的基础上采用核函数为RBF的SVM分类器对训练集中单词图像的两种HOG特征向量进行训练，再利用训练好的分类模型做精确匹配，并将识别结果返回给用户。在本文中，基于SVM的学习分类系统的工作流程如图7所示。

图7 SVM工作流程

在样本库的构成中，本文对关键词采取基于标准欧氏距离的模板匹配从分割单词图像库中构建关键词样本集合、非关键词样本集合和粗匹配单词集合。其中各集合数量及比例由关键词的选择及阈值的选择决定。通过对训练集提取HOG特征，本文训练了一个分类模型。本文使用训练好的模型，对上一阶段粗匹配单词集合做出分类识别。在这一步对于SVM分类器的训练，本文选择C类支持向量机SVC，核函数选择基于径向的函数RBF。

4 实验结果及分析

本文中的实验是在windows 7系统环境上进行，其是Intel(R)Core(TM)i5-4210H、CPU2.9 GHz、4 GB内存的PC，具体程序是在visual studio2012开发环境下编程调试，并借助OpenCV-2.4.10开发平台实现的。

为验证本方法在基于关键词的维吾尔文文档图像检索中的有效性，本文选取了10个较常用且具有实际意义的关键词进行实验。本文随机抽取文档图像数据库中的108张文档图像，经单词切分后形成25 569张单词图像库。关键词模板为选定的目标的关键词，在粗匹配阶段通过对阈值的调试来自适应出训练集和粗匹配单词集合，接着在融合两种HOG特征的基础上，由SVM进行目标关键词的精确匹配。本文列举其中一个关键词的检索结果：图8为选定目标关键词的图像，图9为检索出的目标关键词位置示例图(以其中一幅文档图像为示例)。

图8 目标关键词的图像

图9 检索结果

4.1 评价指标

本文在基于关键词的维吾尔文文档图像检索研究中，采用准确率、召回率和F值3个常用指标评价方法的效果。其中准确率是检索出相关关键词数与检索出的所有关键词总数的比率，用来衡量关键词检索方法的查准率；召回率是指检索出的相关关键词数和文档库中人工标注相关关键词数的比率，用来衡量检索系统的查全率；F值，则是综合这二者指标的评估指标，用于综合反映整体的指标。鉴于此，本文做如下变量和指标的定义：

TP(True Positive)：检索为关键词，实际也为关键词；

FP(False Positive)：检索为关键词，实际是非关键词；

TN(True Negative)：未被检索到的关键词，实际是非关键词；

FN(False Negative)：未被检索到的关键词，实际是关键词；

(1)准确率

precision=TP/(TP+FP)*100%

(2)召回率

recall=TP/(TP+FN)*100%

(3)F值

F=precision*recall*2/(precision+recall)

4.2 文档图像检索实验结果及分析

本文选定10个常用单词作为关键词，分别对其在单词规模为25 569的108篇维吾尔文文档图像中层级匹配的检索效果进行统计，包括粗匹配、单特征精确匹配和特征融合精确匹配。每张表中均包含人工标注的目标关键词出现的个数、检索到的目标关键词个数、算法共检索到的相关单词图像个数、准确率、召回率和F值等要素。

本文分别对10个关键词在108篇维吾尔文文档图像中基于欧式距离的模板匹配结果统计见表2。

表2 基于模板匹配的关键词检索结果

表2中数据为使用基于欧式距离的模板匹配算法在维吾尔文文档图像中的粗匹配结果，其中准确率平均值为43.31%，召回率平均值为85.27%，F值平均值为56.79%。从表2中可以看出第8个关键词的准确率最低，为29.82%，表示共检索出57个单词图像，其中目标关键词仅仅包含17个；相反也有准确率较高的关键词，第10个关键词准确率63.77%，即检索到的69个关键词中有44个为目标关键词。而对于召回率，第2个关键词效果最好，为96.65%，共标注的69处检索到66处。最低为第8个关键词73.91%，23个目标关键词检索到了其中17个。

经分析得出，粗匹配阶段准确率普遍偏低而召回率较高。这是因为该阶段是初步筛选的过程，未对关键词图像提取有效的特征而直接使用像素信息进行匹配，欧式距离阈值的设定对匹配有影响。粗匹配应在保证尽可能多的检索到目标关键词的情况下，过滤数据库中部分无关单词图像，过滤数量严重影响粗匹配的准确率。本文在粗匹配的基础上提取了两种HOG特征向量，由SVM分类器学习分类，进一步对目标关键词进行匹配。表3为提取HOG特征实验结果，表4为在细化操作后提取HOG特征实验结果。

由表3可得，在模板匹配的基础上提取HOG特征向量由SVM实现精确匹配的平均准确率为87.96%，平均召回率为78.61%，平均F值为81.94%。其中关键词3、4、10的准确率均为最高值100%，代表检索到的单词图像均为关键词图像。召回率中最高是第10个关键词，为100%，代表标注的目标关键词均被成功检索。

由表4可得，在细化的基础之上提取HOG特征的平均准确率为79.45%，平均召回率为86.90%，平均F值为82%。其中准确率最高为第1个关键词，100%；召回率最高为第3个关键词，100%。

由表3、表4与表2对比可得，分别提取两种HOG特征向量精确匹配的检索效果明显好于基于模板匹配的粗匹配检索效果。其中就平均准确率而言，表3和表4分别提高了44.65%和36.13%；对于平均召回率而言，表3相比降低6.66%，而表4相比提高1.63%；对于同时考虑了准确率和召回率而言的F值的平均值，分别提高了25.15%和25.21%。

表3 模板匹配+HOG+SVM的关键词检索结果

表4 模板匹配+细化+HOG+SVM关键词检索结果

由表3和表4中实验数据对比可知，表3的平均准确率比表4高8.51%，表3的平均召回率比表4的低8.29%，表3、表4的平均F值相差不到0.1%。造成这些现象原因是，模板匹配只是简单的利用了图像的像素信息，不能贴切的体现单词图像的特征，仅能起到初步过滤的作用。特征提取能提取图像有意义的信息，减少所需的存储空间。HOG特征表现了单词图像像素的梯度方向，而细化操作能提取图像的骨架特征，两者均能很好表示单词图像，提高图像检索性能。

单一的特征提取的表现往往不尽如人意，恰当的对不同特征提取方法进行融合可以取得更恰当的特征向量。为了进一步提高检索系统的性能，本文结合了两种HOG特征向量，实验结果见表5。

表5 基于模板匹配+特征融合+SVM的关键词检索结果

从表5中分析可得，10个关键词的检索准确率平均值为91.14%，召回率平均值为79.31%，F值平均为84.23%。其中第7个关键词的准确率最高，为100%，第6个关键词的召回率最高，为93.02%，第7个关键词的F值最高，为93.02%。

表5中的数据实验结果是结合了两种HOG特征所得到的。与表3、表4相比可得，检索系统的整体性能有一定的提升。其中，准确率平均值有大幅提升，召回率平均值有所下降，F值均值也有一定程度的提升。这是因为HOG特征表现了单词图像像素的梯度方向，描述了图像细节和像素分布特征，而细化又能提取关键词图像的骨架，两者结合能更全面的表示单词图像，进一步提高检索性能。

由表1～表5中的实验数据可以总结出，在粗匹配阶段准确率较低，召回率较高；而在精确匹配阶段相反，关键词的平均检索准确率要高于召回率。经分析，两种HOG特征特征提取，能够有效提取单词图像的特征信息，并通过SVM分类器能够得到良好的检索效果。通过特征融合的方法，从多方面表示图像信息，能够有效提高关键词文档图像检索实验的性能。

为了更好探究本文所提出的基于关键词的维吾尔文文档图像检索方法，查阅了关键词检索相关文献，对近几年的实验结果与本文的实验结果进行对比，对比情况见表6。

由表6可知，本文方法在对维吾尔文文档图像进行关键词检索时，平均准确率为91.74%，平均召回率为79.31%，平均F值为84.23%。本文的研究内容弥补了维吾尔文中基于关键词的文档图像检索领域的空白。与表中另外3组实验对比，本文的方法在准确率方面效果较为理想，召回率和F值有较大的提升空间。

5 结束语

本文提出了一种基于层级匹配的维吾尔文关键词文档图像检索方法，是在维吾尔文识别、图像检索等领域中的新研究，弥补了维吾尔文文档图像检索相关领域的空白。该方法在单词切分的基础之上，使用基于欧式距离的模板匹配算法构造出关键字样本和非关键字样本，提取融合两种HOG特征并使用SVM分类器对样本进行训练分类。实验结果表明，本文的单词图像切分准确率达到98.7%，文档图像检索准确率平均值为91.14%，召回率平均值达到79.31%。在今后的研究工作中，将继续提高单词切分精度，并提高粗匹配阶段的性能。尝试提取单词的多种有效特征，并使用多种分类器进行实验对比。

表6 基于关键词的文档图像检索结果对比