基于文本布局块距离度量的文档图像检索

王牡丹，邬春学

(上海理工大学 光电信息与计算机工程学院，上海 200093)

基于文本布局块距离度量的文档图像检索

王牡丹，邬春学

(上海理工大学 光电信息与计算机工程学院，上海 200093)

针对现有基于图像文档转换为文本后进行文档检索的方法，无法满足当今超大量数字图像库的处理场景。文中提出一种基于文本布局块的文档图像检索方法。根据文本布局块之间的距离特征，定义了新的距离函数，利用新的距离函数计算得到文本布局块之间的距离矩阵，并结合匈牙利算法求出文档图像的最佳匹配结果。通过大量实验证明，所提方法能够有效地提高图像文档检索准确度，并且能保证78.2%的正确率。

图像文档检索；文档图像分割；文本布局块；距离函数；匈牙利算法

在新媒体时代，数字文档具有信息量大、方便携带、便于阅读等优点，在图书馆和期刊杂志的文档库中，大多数文档都是以文档图像形式保存的。现有的文档图像检索方式是通过将文档图像转换为文本，然后根据文本信息来检索文档图像。该方法依赖高昂的光学扫描识别以及查询索引的建立，耗时耗力[1-5]。

近年来，一种通过文档布局检索文档图像的新方法被应用于文档图像检索，该方法根据不同文本布局的布局块之间的相似距离来匹配文档图像。其直接基于文档图像的布局块进行检索的特点，能够有效缩短检索复杂性和检索耗时，降低成本[6-10]。现有的处理方法有：文献[6]提出了一种布局对比的two-step方法，首先将文档图像分割为等尺寸的块，然后在使用不同的方法计算块距离。文献[11]提出使用布局块的覆盖面积来找出参考图像和查询图像之间的关系。

1 问题描述

20世纪70年代，基于图像检索的文本图像搜索的相关研究就已经开始，主流的图像检索技术是基于文本信息的图像检索。该技术主要是利用光学扫描的方式来提取图像的文本信息特征，并将这些文本信息存放在一个数据库管理系统中，建立与图像关系索引，最后通过查询数据库完成图像检索。此技术有两个缺点：(1)需要依靠手工完成大量图像特征的标记；(2)手工标记的图像特征会受主观因素影响过大。因此，如何有效地对文档图像进行检索以及如何对文档图像进行布局分析成为提取文档图像信息的关键问题。

本文的研究重点是基于布局块距离度量的文档图像检索，在后续章节中，将结合图像处理系统中的3个模块分别介绍这一技术，即图像分割、图像特征提取和图像匹配，处理流程如图1所示。基于现有的多种块距离计算方式和图像块匹配算法，对文本图像检索进行深入研究和学习，对其中的基于区域覆盖面积的块距离计算方式进行改进，并结合匈牙利图像块匹配算法，定义新的距离函数。

图1 图像检索处理流程

2 设计与实现

基于文本布局块距离度量的文档图像检索技术包括图像分割、图像特征提取和图像匹配3个步骤。图像分割，即通过几何版面分析和版面理解工具获得文档图像的版面逻辑结构信息，并使用XY-CUT算法分割文本图像得到布局块；图像特征提取则利用自定义距离函数计算布局块之间的距离相似度，得到表示布局块之间的图像特征的距离矩阵；将得到的距离矩阵作为匈牙利匹配算法的输入，完成图像匹配。

2.1 文档图像分割

对于文本格式规整的文档图像，采用水平投影和垂直投影相结合的方法即可实现良好的块分割。XY-CUT分割方法通过逐步递归的方式对文档图像按照X方向和Y方向进行切割，将整个文档图像划分成多个布局块。在每步划分时，计算当前划分的节点在X方向和Y方向的投影轮廓，通过寻找X方向和Y方向投影轮廓的谷底得到切割点。

图2 文档部分图像布局块集合

具体分割步骤如下：(1)输入灰度图像，使用双线性插值法对图形进行归一化处理；(2)采用Otsu算法对图像进行二值化的处理；(3)对文档图像进行X-Y cut 分割处理。经过多次的X方向投影和Y方向投影交替进行的过程得到文本图像布局块集合，如图2所示。

2.2 文档图像布局块的信息表示

文档图像经过XY-CUT方法被分割成多个文档布局块的集合，图3表示一个布局块信息，定义下列布局块图像信息：(1)查询文档图像布局，QL={QB1,…,QBn}；(2)参考文档图像布局，RL={RB1,…,RBn}；(3)布局块，每个布局块由一对顶点P表示，B=(p1,p2)；(4)顶点，由一对x，y坐标表示顶点P，P=(x,y)。

图3 布局块

2.3 距离函数

文档布局的相似性，即布局之间的距离，需要通过布局块之间的关系进行计算，布局块之间距离度量的好坏，直接影响全局距离的计算。布局块之间的关系通过以下几个属性进行表示：(1)位置。如果两个布局块的位置相似，则有利于分析布局的相似性；(2)宽度。如果布局块的宽度相同，则两个布局可能具有相同的列宽。(3)面积。如果不同布局的两个块的面积不同，则暗示这些块互相是不匹配的。基于上述3种块属性，存在多种布局块距离度量的方式，各距离函数的计算公式及应用可采用多种方式进行。

2.3.1 简单块距离

宽度差与高度差的积

DP(QBi,RBj)=Dh(QBi,RBj)×Dw(QBi,RBj)

(1)

块中心距离

Dbc(QBi,RBj)=dmh(center(QBi),center(RBj))

(2)

这两种方法仅仅通过对布局块不同属性值计算得到块距离，不能证明得到的所有块距离都是有意义的，与预期结果存在比较大的偏差。

2.3.2 重叠区域面积

重叠区域面积方法利用布局块之间重叠区域来计算两个布局块之间距离，重叠区域面积是指同时属于两个布局块的像素数量总和。对于每一对布局块(Bi,Bj)，Bi和Bj是分别属于两个文档图像的布局块，即查询布局RL与参考布局RL。其距离函数定义为

(3)

其中，area(RBi)表示布局块RBi中像素的数量；area(QBi)表示布局块QBi中像素的数量；Qv(QBi,RBj)表示QBi和RBj布局块的重叠区域内像素数量总和；每一对布局块的重叠区域面积取值区间为(0,1)，0表示完全重叠，1表示无重叠。

2.3.3 改进距离函数

单纯地用重叠区域面积作为块距离的度量依旧会存在一定偏差。例如两块面积相同，但位置不同的布局块，若只考虑重叠覆盖面积，则无法准确得到两个布局块的匹配精度，同时会出现如图4所示的情况。

图4 重叠区域面积方法计算结果与期望结果

为避免上述情况，需要在选择距离度量时考虑布局块的位置因素。如图5所示，对于重叠面积相同的两个查询布局块QB1和QB2，分别计算它们各自中心点与参考布局块RB中心点 之间的距离，即可得到两个块之间的差异，由此可知考虑中心距离有助于提高匹配精度。

图5 查询布局块中心点与参考布局块中心点距离

结合布局块的重叠区域面积和布局块中心点之间的距离计算方法，提出一种新的距离函数，定义为

(4)

在式(4)中，Dbc(QBi,RBj)表示两个布局块中心点之间的距离。如果使用式(3)进行距离计算，当两个布局块面积相同而位置不同时，将得到相同的距离值，无法计算两个布局块的相似度。此时使用式(4)，所得到中心点之间的距离不同，得到的距离函数值也不同，即能够更加精确的计算出两个区域块的匹配精度。

2.4 块匹配算法

通过求解距离函数，可得到一个N×N阶的整数矩阵，现将问题简化为求该矩阵的最优匹配，即对一个N×N阶的整数矩阵求解，最终求得一个具有最小和的n个元素的独立集。已知矩阵任意一排减去常数C，或任意一列减去常数C，对匹配结果的次序无影响。

将N×N阶矩阵A=(Cij)每行(列)中的各个元素减去该行(列)中的最小元素，得到新矩阵D=(Cij)，将求最优解问题转换为求解系数矩阵D=(Cij)的最大独立集问题，运用匈牙利算法的思想来解决当前问题。

改进“匈牙利算法”：

步骤1 对系数矩阵进行变换，使每行每列都出现0元素。(1)从系数矩阵中每行减去该行最小元素；(2)再在所得矩阵每列减去每列最小元素；

步骤2 确定一个0的最大独立集：在矩阵中找出一个0的最大独立集S；

步骤3 如果|S|

While |S|

设k是不在这个覆盖的排上的最小的矩阵元素；

将不在覆盖的排上的每个元素减去k；

将既在这个覆盖的行中又在这个覆盖的列中的每个元素加上k；

用一个新的0的最大独立集替代S；

end While

步骤4 输出：集合S是具有最小和的n个元素的独立集。

3 实验分析

从IEEE期刊文档图像库中选取120篇文档图像进行文档图像检索实验。这些文档图像在文档行或者文档区域的布局上表现出较为明显的布局块图像特征，因此非常适合作为实验对象。综合文章提出的文档图像分割方法和距离，以及改进的匈牙利算法，运用4种距离函数进行文档图像检索实验。

实验检索的输出结果为两个文档图像以及两个坐标文件，如图6所示，图6(a)为覆盖面积距离函数计算结果，图6(b)为改进距离函数得到的结果。从实验结果中可以看出，虽然匹配结果存在一定的偏差，但通过大量数据实验统计，正确率可达78.2%，表示此方法有效提高了文档图像的检索准确度。

图6 匹配结果

表1的实验结果表明，在综合考虑重叠区域面积及布局块中心点位置等因素后提出的距离函数能够有效提高文档匹配的准确度，相比于原有的宽度差与高度差之积的方法、块中心距离方法以及重叠区域面积等文档图像检索方式，准确率分别提高26.5%、15.7%、8.9%。

表1 距离函数实验结果

4 结束语

本文提出的基于文本布局块的图像文档检索方式，适用于检索具有典型布局的文档，如期刊杂志和数字文档图像库中的文档图像。随着当前文档图像检索领域发展，需要用于具有更加复杂文档布局的文档检索方法，以提供更优的文档图像查询。目前在文档图像检索技术的研究已取得了部分成果，提出了许多有价值的概念和方法，对文档图像检索的研究也在不断深入。面对当前数字信息迅速增长的情况，将图像文档检索与Hadoop、Spark等分布式技术结合，带来了新的研究方向。

[1] 杜丙新.图像检索研究综述及系统实现[J].电子科技,2016, 29(6):185-189.

[2] 蒋从文,李隐峰,齐鹏,等.学术期刊电子论文检索系统设计[J].电子科技,2014,27(2):122-124.

[3] Breuel T M,Janssen W C,Popat K,et al.Paper to PDA[C].PF,USA:International Conference On pattern Recognition,2002.

[4] Shafait F,Keysers D,Breuel T.Performance evaluation and benchmarking of six-page segmentation algorithms[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2008,30(6):941-54.

[5] Breuel T M.Hign performance document layout analysis[C].NG,USA:Symposium on Document Image Understanding Technology,2003.

[6] Hu J,Kashi R,Wilfong G T.Document image layout comparison and classification[C].HW,USA:Proceedings of the International Conference on Document Analysis and Recognition,1999.

[7] Liang J,Phillips I T,Haralick R M.Performance evaluation of document structure extraction algorithms[J].Computer Vision and Image Understanding，2001，84(1)：144-159.

[8] 胡芝兰,林行刚,严洪.基于分层密度特征的文档图像检索[J].清华大学学报:自然科学版,2006,46(7):1231-1234.

[9] 宋涛,刘刚.一种基于内容的文档图像检索方法[J].郑州大学学报:工学版,2010,31(1):120-124.

[10] 张田.综合文字和非文字区域特征的文档图像检索[J].计算机工程与应用,2010,46(12):5-8.

[11] 赵慧.基于版面分析的文档图像检索算法研究[D].济南:山东师范大学,2011.

[12] 赵慧,王希常,刘江.一种基于版面结构距离的文档图像检索算法[J].微型机与应用,2010,29(21):42-44.

[13] 张敏.基于纹理特征的数字图书馆文档图像检索技术[J].河南理工大学学报:自然科学版,2014,33(4):506-509.

[14] 张田.一种基于特征的文档图像检索方法[C].北京:全国模式识别学术会议,2008.

[15] 郭加旋.面向非纯文本文档图像的检索技术研究与实现[D].重庆:西南大学,2014.

[16] 周静雯.基于布局相似性的文本图像检索[D].上海:华东师范大学,2014.

Document Image Retrieval Based on Text Layout Block Distance

WANG Mudan,WU Chunxue

(School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093, China)

The existing methods of document retrieval based on the conversion of image documents into text can not meet the processing scenes of today’s large number of digital image databases. This paper proposes a document image retrieval method based on text layout block. According to the feature of distance between text blocks, a new distance function is defined. Then, the new distance function is used to calculate the distance matrix between text blocks. Finally, the best matching result is obtained by combining the Hungarian algorithm. A lot of experiments show that this method can effectively improve the image document retrieval accuracy, and can guarantee the correct rate of 78.2%.

image document retrieval; document image segmentation; text layout block; distance function; Hungarian algorithm

2016- 11- 21

国家自然科学基金(61202376)；上海市教育基金会晨光计划基金(10CG49)

王牡丹(1990-)，女，硕士研究生。研究方向：数字图像处理。邬春学(1964-)，男，博士，教授。研究方向：嵌入式系统及应用等。

10.16180/j.cnki.issn1007-7820.2017.09.013

TN911.73；TP391.41

A

1007-7820(2017)09-046-04