图谱理论在文本图像二值化算法中的应用.doc

图谱理论在文本图像二值化算法中的应用研究常丹华，苗 丹，何耘娴作者简介：常丹华（1948-），女，河北省秦皇岛人，教授，硕士生导师，主要研究方向：图像传感及应用；苗丹（1986-），女，河北省邢台人，硕士研究生，主要研究方向：图像处理，字符识别；何耘娴（1985-），女，河北省衡水人，硕士研究生，主要研究方向：图像处理，汉字识别。（燕山大学 信息科学与工程学院，河北秦皇岛 066004）（）摘 要：由于常用的阈值二值化方法不能很有效的分割出文字图像，利用图谱理论的思想可以清晰有效地对文本图像进行二值化分割。针对传统的图谱理论分割图像算法计算量大、空间复杂度高的不足，提出了利用直方图灰度等级代替像素级，在此基础上近似计算了权函数的参数，算法的计算量和复杂度都有所降低。实验结果表明，该方法大大降低了计算的复杂性，在速度上优于传统的图谱理论分割方法，质量上由于常用的二值化分割方法。 在复杂的背景下，常用的阈值化方法不能有效地提取文本，利用图谱分组理论可以有效地对文本图像进行二值化分割。由于其计算量大和复杂度高，提出了在利用直方图灰度等级代替像素级的基础上近似计算权函数的参数。通过实验表明，该方法大大降低了计算的复杂性，质量上优于常用的阈值分割方法。关键词：图谱理论；阈值分割二值化；文本图像；直方图；边权值中图分类号：TP391 文献标志码：AApplication of Study on Text Image Binarization Processing Based on Graph Spectral TheoryCHANG Dan-hua, MIAO Dan, HE Yun-xian(Institute College of Information Science and TechnologyEngineering,Yanshan University,Qinhuangdao 066004,Hebei Province,China)Abstract: Due to traditional thresholding methods cannot segment the character image effectively from the whole image. The improved method based on graph spectral theory can segment the character image effectively and clearly. Contrary to the traditional algorithm requires much more calculation and much higher computation complexity. Therefore, this paper proposed using gray levels of an image instead of pixel of an image, on this basis, calculated the parameter of weight function approximately. The experimental results show that this method reduces the complication much more, the superior performance on speed of it compared to the traditional method based on graph spectral theory, on quality of it compared to the other thresholding algorithms.Keywords: graph spectral therory; thresholding segmentbinarization; text image; histogram; edge weight0 引言图像二值化图像中常常包含有丰富的文本信息，如道路指示牌、车牌、各种提示牌和标志牌等等，如果能快速的将文字信息从图像中提取识别出来，就对于更高语义层次上进行图像、视频检索和认知极具意义。例如，文化差异造成了外国游客交通、购物等众多不便，就可以通过数码相机拍摄路标和指示牌，利用图像处理技术将图像中的文字自动检测、提取、识别出来，并通过翻译机翻译成需要的语言朗读出来，为外国游客提供了便利。研究计算机在自然环境下的自动文本提取具有广泛的应用领域，如手机自动翻译系统、名片自动输入系统、车牌牌照识别、办公室的文档处理和图书馆大量文献的数字化等等，因此，该研究课题是图像处理领域的研究热点。在自然场景下，图像中的阴影或者复杂背景不能有效地利用传统OCR(Optical Character Recognition)引擎进行识别，通过二值化将背景和文字很好的分离开来是十分必要的。阈值分割的基本原理是通过将图像中的每个像素与某一门限值进行比较从而将图像区分为背景和目标，其关键问题在于寻找一个合适的门限值来区分目标和背景而且不损害目标的完整性。目前，最广泛应用的阈值分割技术包括全局阈值方法1,2和局部阈值方法3,4，全局方法根据文档图像的直方图和灰度空间分布确定一个阈值，以此实现灰度文档图像到二值化图像的转化，典型的全局算法包括平均灰度法，Otsu方法，迭代最优算法等；局部阈值通过考查每个像素点的领域来确定阈值，比全局阈值具有更广泛的应用，常用的局部阈值方法有Niblack方法，Bemsen方法，平均梯度法等。自然场景下文本字符的复杂使得文本区域或背景区域往往不具有某种单调性，比如同一个字符上可能具有明暗两种笔画，此时阈值化分割就会失效。因此，应用各种新的思想和理论来解决这一难题仍然是具有挑战性的。近年来，图谱理论是目前模式识别研究的热门方法之一，在数据降维、聚类和图像分割方面获得了广泛的应用5。图谱划分理论作为一种新型的工具被应用到图像分割领域，其基本思想是将图像看做看作是一个带权图，其每个节点对应图像的一个像素或区域，连接每两个节点的边的权值表示该两节点属于同一区域的可能性，权值的大小与两节点的相似性、邻近性以及连续性等相关。根据图的某种特定划分建立相应的能量函数，该能量函数的最小值即对应图像的一个最佳分组。不足的是，图谱分割的特征值求解时往往需要较大的空间复杂度和计算复杂度，这限制了改方法的应用。在文献16中陶文兵提出一种基于图谱划分的阈值分割方法，采用图谱划分测度作为阈值分割的准则来区分目标和背景。该方法通过计算一个256256的灰度矩阵获得权值矩阵简化了计算，但是该方法在求取最小Nuts值时，是根据阈值化条件，求取的局部最优值，这局限了该方法的应用对象；还有在计算图顶点之间的边权值采用指数函数导致其计算量很大且对有些图像无法获得满意分割效果的不足。本文提出了在图像的灰度直方图上构造相似矩阵，通过将像素级上的划分转化为灰度等级上的划分，这样使运算量大大减少；采用距离倒数的计算方式近似计算图顶之间的边权值以降低计算复杂度，最终的目的都是大大减少特征值求解时的计算量，提高使用实用性使图像达到满意的分割效果。1 基于图谱理论的图像分割方法1.1 图像分割中的图谱理论 任意特征空间的点集都可以采用一个无向图来表示，其中是节点的集合，是连接节点的边的集合，其每个顶点对应图像的一个像素或区域，连接任意两个顶点的边的权值表示顶点和属于同一个区域的可能性，权值的大小与两顶点的相似性、邻近程度以及连续性等相关。如果将点集分成两个独立的子集和，其中，那么通过移去连接和中所有节点的边就可以得到点集和之间的分离度，称为划分（cut）7： (1)寻找图中的最小切（minimum cut）7，即是对图的一个最优化分。Shi和Malik8在此基础上提出了规范化切（Normalized cut,Ncut）实现对图像的分割，规范化切分定义如下： (2)其中，分别表示或到整个顶点集合的关联度，此时最小的值对应的划分即为图的最优划分。为求得式（2）中最小的值，将上述最优化问题转化为求解式（3）中的特征系统。 (3)其中为对角矩阵，其对角线元素，为对称矩阵，其元素为，显然有，和分别为相应的特征值和特征向量。 特征系统（3）的第二个最小的特征值所对应的特征向量对应着图的最优划分【8】，从而得到对应图像的一个分割结果。当图像的尺寸较大时，采用方法其对应的邻接权值矩阵的位数也相应较大。如果采用基于像素的邻接权值矩阵，我们必须求解一个如式（3）的的矩阵特征解，这样使得求解变得十分困难，因此限制了方法的应用。1.2 本文采用的算法 设表示大小为的数字图像，其灰度级为，；为图像中像素点的灰度值；，代表灰度直方图9。将图像中的每个位置看成无向图的节点，则，和满足以下条件：，；，；，。将图像中的每个位置看作无向图的一个节点，每对节点均用一条边连接起来，边的权值反映这两个位置所对应的像素属于相同目标的可能性，那么就可以构建一个带权的无向图，可定义图中连接2个节点和的边的权值如下： (4)其中，是节点的空间位置，是节点在图像中位置坐标处的灰度值，表示一个矢量的二范数。另外，和是尺度因子，分别控制权值对2个节点和得灰度差异及空间位置差异，控制和之间的顶点个数，随着的增加，参与计算权值的节点个数也增加，同时计算量也相应地增大。可将具体展开写成如下形式： (5)由于上式计算边权值采用幂指数运算，导致给定图像构造其图顶点之间边权的计算量很大，原因在于计算式采用下列近似公式： (6)这就导致直接利用指数函数其计算量。因此，采用倒数近似的方法来计算权值，公式如下： (7)对于任意门限，我们能够得到图像对应的图的一个而二划分，和可分别表示为 ，。那么等式（1）可转化为 (8)同样可得 (9) (10)令为中所有节点（其灰度级为）与中所有节点（其灰度级为）间总的连接权值之和，则式（8）（10）可分别转化为 (11) (12) (13)注意到下式成立： (14) (15)那么（2）式变为 (16) 对给定的一幅图像，通过计算其对应图中所有顶点间的权值可以构建一个基于灰度直方图的权值矩阵，其中矩阵为的对称矩阵，为灰度直方图的灰度等级数，且，。本文的算法就是寻找使图像的测度值最小的门限对图像进行阈值分割，以下是算法实现的步骤：图1 本文算法实现的流程图在上述方法中，相似度矩阵的大小取决于直方图的等级，而不是图像中像素的个数；同时，算法中只需求解一个维矩阵的特征系统，而不再是维的，通常比小得多，且大小固定。因而算法的计算复杂度和空间复杂度都大为降低，。实时性大大增强。2 参数设定和实验结果通过一系列的实验来测试本文方法的性能，在实验中，为了测试不同灰度等级对文本图像的分割效果，选取了30幅经定位分割后包含有字符文本的灰度图像进行试验。式(5)中各参数设置为=5，=65，=5，运行环境为PIV=1.60G，内存为512M。通过两个指标来衡量算法的优劣，分别为分割到字符区域的精确度(Precision)和提取率(Recall)，分别记为和：， 为了方便算法性能对比，给出综合评测标准，其中：。为了对比本文方法的分割性能，选取了最经典的最佳阈值分割方法和基于最大类间方差的Otsu方法和为改进的基于图谱理论的阈值分割方法与本文的方法进行二值化比较。最佳阈值方法又称为逼近迭代算法，原理是将直方图用两个或多个正态分布的概率密度函数来近似的方法，阈值取为对应两个或多个正态分布的最大值之间的最小概率出的灰度值，其结果是具有最小误差的分割。这种算法可以较好的区分图像的前景和背景，但是会导致图像一些细微信息的丢失。Otsu方法又称最大类间方差的方法，是一种自适应的阈值确定方法。它根据图像的灰度特性，将图像分成背景和目标两部分，背景和目标的方差越大，说明两部分的差别越大。该算法速度较快，目前应用非常广泛。下图是具有代表性的三种类型的图像分割结果。图2 前景和背景边界清晰图像的分割结果图3 背景有阴影但前景分布均匀的图像的分割结果图4 背景光照不均匀的图像分割结果 图2中的字符前景与背景的对比明显，且字符区域的灰度值基本均匀分布，3中种方法都取得较好的效果。图3中的字符有笔画粘连的情况，背景中的颜色分布也不均匀，左边的颜色要比右边的颜色深，这是拍照的角度造成的，利用最佳阈值Otsu法没有把字符和背景完全区分开来，而利用本文的算法和Otsu基于图谱分组理论的阈值分割方法都有效的将背景和字符分割开来，但由于字符的颜色分布不均匀导致字符中的笔画重叠。图4中的背景由于光照的原因只导致反光使得背景像素的灰度差异较大，一般的阈值分割方法很难将字符区域准确的提取出来，本文的算法优于其它算法可以将字符区域很好的提取出来。实验方法Precision(%)Recall(%)f(%)平均时间开销(s)Otsu方法最佳阈值化法81.371.283.773.682.572.90.1350.146未改进的基于图论的分割方法Otsu方法83.681.386.583.785.082.23.050.135本文方法84.588.786.52.301表1 3种方法分割图像的试验结果 从处理一幅图像的平均时间来看，利用最佳阈值化Otsu方法的平均时间为0.1460.135s，Otsu未改进的基于图论的分割方法的平均时间为0.1353.05s，而利用本文方法的平均时间为2.301s。由于在计算权值时进行了近似计算，从实验结果可以看出本文的方法比未改进算法CPU所用时间平均减少0.749s，大大提高了运算速度，实时性提高。虽然Otsu方法最为快速，但是其二值化的质量没有基于图论方法的效果好；本文的方法与传统的基于图谱理论阈值分割的方法达到的效果基本相同，而且所用的时间有所下降，实时性有所提高。综上表明了本文的方法质量效果上优于常用的图像二值化方法，时间上优于传统的基于图谱理论的阈值分割方法。本文的方法慢的多，这也表明基于图谱方法的实时性有待提高。3 结论 基于图谱理论的图像分割方法通过将图像看做一个带权图，图像中的各个像素点看做图中的节点，构建节点邻接权值矩阵，进而采用求解特征系统的方法来寻求最优解，这类方法虽然非常有效但是其相应的计算量非常大，计算复杂度也非常高。因此利用此方法对自然场景下的字符提取是很有效的，基于此方法的计算量大复杂度高，提出了基于灰度直方图的方法降低计算量，将计算像素点转化为计算灰度级，采用距离倒数的计算方式降低其计算的复杂度。实验结果表明，该方法对字符图像分割具有良好的性能，质量和速度都优于一般的阈值分割方法。参考文献：1 TSAI T H and CHEN Y C. A comprehensive motion videotext detection localization and extraction method J. Proc. of IEEE Intl Conference on Data Engineering Workshop，Istanbul，Turkey，2007(2)：113-116.2 PAN W M，BUI T D，and SUEN CY. Text segmentation from complex background using sparse representations J. Proc. of Intl Conference on Document Analysis Recognition，Curitiba，Brazil，2007(1)：412-416.3 LIENGART R and WERNICKE A. Localizing and segmenting text in images and videos J. IEEE Transactions on Circuits and Systcms for Video Technology，2002，12(4)：256-268.4 WU V，MANMATHA R，and RISEMAN E M. Text finder: An automatic system to detect and recognize text in images J. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1999，