一种文档图像检索算法设计和实现

      摘  要： 介绍了一种基于版面结构距离的文档图像检索算法，使用版面特征作为文档图像的特征检索图像。先将文档图像进行梯度和最大梯度差（MGD）计算，然后使用MGD值作为一个窗口对文本区域进行融合，将文档图像以行线的形式标示出来。同时给出了检索的匹配方法，并对匹配方法进行了实验。实验结果表明，该检索方法具有较高的查准率，具有很好的抗倾斜和抗缩放效果。

　　文档图像一般意为含有文字信息的图像，目前大多数信息是以数字化形式存在的，并以文档的形式组织起来存放在数据库中。在这样的数据库中查找有关资料其技术是关键。常见的文档图像检索方法是基于内容的文档图像检索（CBIR）。它是利用图像本身的信息，通常以图像特征（颜色、纹理、形状、结构布局和语义特征等）的相似性为检索依据，根据每幅图像都有的可比较特征进行检索。

　　近年来，数字化文档被广泛应用于办公自动化、数字化图书馆、工业自动化等领域。随着科技的发展，传统扫描仪体积大、效率低、携带不方便等不足之处日益突出，而数字照相机体积小、价位低，可以很容易地携带并结合到手机、 手提电脑以及各种网络设备中去，它还可以远距离地对背景文字及脆弱的珍贵文档拍照， 更适用于无约束环境下的数字化操作。因此，将数字照相机引入文档图像分析已经引起越来越多人的关注。

　　Newman的调查表明，从报纸上提取段落时，基于PC摄像头的OCR操作比基于扫描仪的OCR操作效率高得多；Fisher等调查了在战场上用数字摄像机替换士兵携带sheet-fed扫描仪的可能性。经证实，数字摄像机能够以200dpi拍摄整张A4文档纸，已经达到OCR所要求的分辨率。

　　BEUSEKOM J V.等人提出了一种基于版面分析的文档图像检索的距离度量方法，将文本区域分为不同的矩形块，然后找到块的中心点，利用角点的曼哈顿距离来计算块之间的距离，再利用三种不同的方法进行匹配[1]；WONG K Y.使用游程平滑算法进行版面信息提取的方法[2]；BREUEL T M.提出了使用Whitespace算法来提取版面信息[3]。

　　图像匹配是指通过一定的匹配算法在两幅或多幅图像之间识别同名点，如二维图像匹配中通过比较目标区和搜索区中相同大小的窗口的相关系数，取搜索区中相关系数最大所对应的窗口中心点作为同名点。其实质是在基元相似性的条件下，运用匹配准则的最佳搜索问题。

　　灰度匹配的基本思想：以统计的观点将图像看成是二维信号，采用统计相关的方法寻找信号间的相关匹配。利用两个信号的相关函数，评价它们的相似性以确定同名点。

　　灰度匹配通过利用某种相似性度量，如相关函数、协方差函数、差平方和、差绝对值和等测度极值，判定两幅图像中的对应关系。

　　最经典的灰度匹配法是归一化的灰度匹配 法，其基本原理是逐像素的把一个以一定大小的实时图像窗口的灰度矩阵，与参考图像的所有可能的窗口灰度阵列，按某种相似性度量方法进行搜索比较的匹配方法，从理论上说就是采用图像相关技术。

　　利用灰度信息匹配方法的主要缺陷是计算量太大，因为使用场合一般都有一定的速度要求，所以这些方法很少被使用。现在已经提出了一些相关的快速算法，如幅度排序相关算法，FFT相关算法和分层搜索的序列判断算法等。

　　1 相关工作

　　1.1 文本行标记

　　将得到的文档图像进行预处理，具体的处理方法是：使用文本行标记算法实现文字区域的行定位。本文使用[-1，0，1]对图像进行处理计算其梯度，然后计算其MGD。MGD计算方法如下：在一个大小为n的窗口内，用它的最大梯度差来进行填充，以达到文本融合的目的。因为英文和中文的字符宽度不同，根据具体的情况选择n，大于字符间距即可。将计算出来的梯度求它的最大值和最小值，然后相减，即为最大梯度差。将得到的MGD图像使用最大类间方差方法[5]（OTSU）求出阈值得到二值图像[2]。图1为使用上述方法对行块进行标记的图像。

　　1.2 消除阶跃跳变

　　对于手写体或者英文的文档，会出现字符高低不一、笔画不连续等情况。线特征产生的断点可采用形态学方法、凸凹点处理和噪声处理三种基本策略提高直线的连续性，然后采用阶梯插补算法来消除阶跃跳变，算法的复杂度相对较低。

　　在像素级上进行处理是：当出现行阶跃跳变的情况时，使用如图2的模板来对其进行填充。因为文档图像的行块在4个方向上都有可能出现这种阶跃，所以采用一个3×3的模板，以位置5为中心点，如图3所示，4种情况都包含其中：1和4为非文本像素，对4进行填充；3和6为非文本像素，对6进行填充；4和7为非文本像素，对4进行填充；6和9为非文本像素，对6进行填充。如果填充之后依然有符合结构的像素，则继续填充，即把需要填充的区域都填充完整。填充前后的图像如图4所示。

　　1.3 行线标记

　　通过对得到的二值图像的行跳变的填补，文本行的变化相对比较平滑，这有利于行线的标记。本方法取每个文本行的下边缘来作为行线。因为背景区域为黑色，文字区域为白色，所以对文档图像进行扫描，从黑色区域进入白色区域时所遇到的第一个像素进行标记，这样就把每一行的行线标记出来了，所得到的行线是单像素的。这种方法的优点是可以抗倾斜。

　　图5（a）为对图1中的图像中的行用直线的方式标记出来。为了验证提取出的行线与原图是否一致，将它与原图（如图5（b）所示）进行了匹配，可以看出，所得结果是比较满意的。

　　2 匹配算法

　　本文所采用的方法是将行线抽象为空间中的一个点，点的灰度值定义为行线的长度。全局匹配模式考虑版面的加权平均，用于全局位置进行匹配，这个过程相当于文本区定位过程。局部匹配模式是定义两个行在位置、尺寸上的变化情况，通过位置优先（版面）得到匹配模式，进而对匹配误差能量进行计算。

　　匹配方法转化为两组点之间的匹配定义问题，点模式简化了问题的复杂性，只包含了版面结构信息、长度信息和尺寸信息。

　　中心点加权匹配方式不能完全解决问题，图像在两个尺度上的缩放对这种方式影响极大。使用归一化的尺寸可部分解决这个问题，但归一化后仍需计算中心点的位置，通过中心点进行坐标转换，使用坐标转换后的新的点模式对差异性进行度量。

　　每一行起始坐标的相对坐标是（xi′，yi′），xi′=xi-x0，yi′=yi-y0。图6为将行线抽象为空间中的点的图像，其中亮度代表该行的长度，位置为起点坐标。

　　（2）距离匹配模式计算

　　将两个页面的中心点对齐，从第一个页面的第一行开始，与另一个页面每行进行比较。假如另一个页面的相对坐标是（uj′，vj′），j=0，…，n-1，每行长度为wj。计算两个待比较页面的坐标及长度的差Δxi、Δyi、Δzi，其中：Δxi=xi′-uj′，Δyi=yi′-vj′，Δzi=zi-wj。则定义差异能量为：

　　dEnerge（i）=Δxi+Δyi+Δzi

　　将第一个页面的第一行与第二个页面的每一行进行比较，得到n个差异能量，求这n个差异能量的最小值min（dEnerge（i））。第一个页面共有m行，将得到m个值，对其求和：

　　不匹配的情况经常发生，例如一个图像中含有4个点模式，另一个图像中含有10个点模式，内部点模式之间具有结构相关性，结构上的相关性定义为点模式位置掩模距离，该距离用来度量点模式全局匹配能力。如果一个点模式为另一个点模式的子模式，则该方法实现子图检索功能，模式距离最小时，产生最佳匹配。最佳匹配时，产生更为细致的行线检索能力。使用掩模方法是为了产生更好的查准率。

　　3 实验结果与分析

　　应用上述方法进行了实验，数据为手写体英文，数据采集分辨率为100 dpi，256级灰度图像，数据量为100幅文档图像。对不同的图像分别比较它们的相似度。图7（b）、（c）、（d）是与图7（a）的相似度分别为40.422 9、45.760 7和43.407 8的图像。图8（b）、（c）、（d）是与图8（a）原图像版面结构相似的几种图像类型。图9（b）、（c）、（d）是与图9（a）原图像版面结构具有差异的几种图像类型。

　　本文使用对100幅文档图像两两进行版面结构的匹配，共有4 950种结果。实验结果表明，两种不同版面的能量差异最大的在340左右，如图10所示。横坐标显示的是100幅图像两两匹配出现的情况的数目，可以取到的最大坐标为4 950，纵坐标为各匹配情况对应的能量差异，最大值350。从图中可以看出能量差异主要集中在50~200之间。

　　各个能量点的频数的直方图如图11所示，图中横坐标为能量差异数据，最大为340左右，提取到350。纵坐标为取到各个能量的情况的数目的累加。从图11可以更直观地观察到能量差异在50~200之间的数目最多。

　　实验结果表明：（1）文档图像的版面结构具有相对的稳定性。（2）点匹配模式计算了最小距离，可有效表示图像的文本行基本信息。（3）距离匹配较为简单，使用了三个维度的一维距离，有较好的区分性。对距离计算统计表明，具有正态分布特性。（4）点匹配模式需进一步进行研究，算法的复杂度需进一步降低，以进行实时图像处理。

　　本文针对文档图像的检索方法进行了研究，提出一种文档图像检索的新方法。分析了文档图像版面特性，使用分割方法确定文本行，将文本行进行标记，找出页面的中心点坐标，中心点坐标将文本行的长度作为权重考虑在内，得到相对坐标。根据相对坐标和文本行长度得到一个差异能量，根据差异能量来进行匹配。并对该方法进行了实验和结果分析。本方法的优点是，当文档的行出现倾斜和缩放时，不影响匹配的进行。但需要进一步降低所用的点匹配模式时间复杂度，以进行实时图像处理。