收稿日期:2007-01-10;修回日期:2007-03-14。
作者简介:周冠玮(1982-),男,江西南昌人,硕士研究生,主要研究方向:图像处理; 平西建(1953-),男,河南新乡人,教授,博士生导师,主要研究方向:图像处理、信息隐藏; 程娟(1979-),女,河南郑州人,博士研究生,主要研究方向:图像处理。
文章编号:1001-9081(2007)07-1813-04
基于改进Hough 变换的文本图像倾斜校正方法
周冠玮,平西建,程 娟
(信息工程大学信息工程学院,郑州450002)
(zg w _tex @t yahoo .co https://www.doczj.com/doc/0a5533552.html,)
摘 要:文本图像在扫描输入时产生的倾斜现象会对后续的页面分割及光学字符识别(OCR )处理产生很大的影响,而传统的标准H ough 变换虽然具有对噪声不敏感,不依赖于直线连续性的优点,但由于计算量偏大,速度慢,在实用时有较大的局限性。提出一种基于改进的H ough 变换的文本图像倾斜校正方法,通过在变分辨率图像中采用不同的文本方向提取算法,及选择合理投票门限等改进H ough 变换的措施,减小了由图像区域及文字笔画粗细所产生的对倾角判定的不利影响,并使用基于偏移值的方法实现页面倾斜的快速校正。实验结果表明,该算法实现了大范围高精度的文本图像倾角的快速检测,具有较强的实用性。
关键词:文本图像;H ough 变换;数学形态学;游程平滑;变分辨率图像中图分类号:TP391.41 文献标志码:A
Ske w detecti on and correction m ethod of docu m ent i m ages
based on i m proved Hough transfor m
ZHOU Guan-w e,i PI N G X-i jian ,C HENG Juan
(Co llege of Infor ma tion Eng ineering,Information Eng ineering University,Zhengzhou H enan 450002,Chi na )
Abstract :T he ske w o f docu m ent i m ages o rig i na ted from scann i ng w ill bri ng much trouble t o page segm enta ti on and
op tica l charac ter recognition (O CR ).A lthough trad iti ona l standard Hough transf o r m i s insensiti v e to no i se and d i sconti nuous ,it has li m itati on in app licati on because o f huge ca l culati on .A ske w de tecti on and correcti on o f docu m ent i m ages based on i m proved H ough transfor m w as presen ted .T ext -li ne directi on ex tracti on i n mu lt-i reso luti on i m age and reasonab le vo ti ng thres ho l d se lecti on were i ntroduced t o reduce t he affect brought by i m ag e s kew .Experi m ental resu lts sho w t hat t h is me t hod is effecti ve and accurate i n skew detection and correcti on of do cu m ent i m ages .
K ey words :docum ent i m age ;H ough transfor m;m orpho logy ;run -l eng th s m ooth i ng ;mu lt-i reso l ution i m age
0 引言
随着数字化技术的发展,/无纸化0已经成为办公自动化的显著特点。将纸质文件扫描或拍摄转换为文本图像,不仅能够保持原文件的书写特征,而且可以使用JPEG 、T IFF 等图像编码格式表示,易于存储建档并在互联网中传输。文本图像在存储后可以运用信息处理技术提取感兴趣的信息,因此在各类信息系统中得到了广泛应用。然而在将纸质文件转换为文本图像的过程中,由于机械操作和人为的原因,不可避免地会造成文本图像的倾斜,这种倾斜显然将对文本图像的分析,如页面分割、版面分析和理解及光学字符识别(O ptical Character R ecogn iti on ,OCR )处理等产生不利的影响。因此,文本图像倾斜角度的检测和校正是文本图像预处理中一个必不可少的技术环节。
文本图像倾角检测的方法主要有投影特性法、近邻法、Fourier 变换法、交叉相关法和H ough 变换法。基于对投影图的形状分析,Y.Is h itani 提出了局域复杂度的方法[1]。该方法需要对每个倾斜角度下的投影形状进行遍历,不仅计算量大,而且当倾斜角较大时,不能保证校正精度。近邻法[2]通过找出所有连通区中心点的K 个最近邻,计算每对邻近点的矢量
方向并统计生成直方图,直方图的峰值对应于整个页面的倾角。由于在文本图像中连通成分较多,该算法较为费时。W Pstl 等人采用的F our i e r 变换法[3],以F ourier 空间密度最大的
方向对应于倾斜方向。虽然该方法倾斜校正的精确度较高,但由于计算的时间长,空间复杂度很高,实际中使用较少。基于文本区域同一行像素相关统计特性的交叉相关法,计算固定距离间竖直扫描线上像素点的分布,生成相关矩阵,实现倾斜校正。此类方法的缺点是计算量较大。M.Chen 等提出的改进算法[4]解决了文字行的主方向变化和文档中包含图表的问题,准确度较高,但精度较低。
本文根据文本图像的特点,提出了一种基于改进Hough 变换的倾斜校正方法,针对变分辨率图像数据量的差异性,采用了不同的文本方向提取方法,对Hough 变换作出了改进,减少了文字粗细和图像区域的干扰,提高了检测速度和检测精度。
1 Hough 变换
H ough 变换是一种快速的形状匹配技术。经典的H ough 变换适用于曲线形状可以用参数来描述、而曲线位置未知情况下的曲线检测。1981年D.H.Ba llard [5]推广了H ough 变
换,可以检测任意形状的物体,大大扩展了H ough 变换的应用
第27卷第7期
2007年7月
计算机应用
C o mpu ter App lications
V o.l 27No .7
Ju ly 2007
范围。
在笛卡儿坐标系中,直线可以用斜截方程y =kx +b 表示。考虑同一直线上的两点(x i ,y i )和(x j ,y j ),满足y i =kx i +b 和y j =kx j +b,映射到参数空间后的两条正弦曲线Q =x i cos H +y i si n H 和Q =x j cos H +y j s i n H 将相交于一点。从而在图像空间中同一条直线上的所有点在变换到参数空间后的正弦曲线都将会交汇于一点(Q ,H )。因此可以设计二维计数器H (Q ,H )来累加极坐标系中的参考点数。最后通过统计计数器矩阵的局部极大值,即可检测出图像中的直线。对应于文本图像倾角检测,虽然文本图像中很少有真正的直线,但在图像的文本区域中,文字行间有很强的方向性,因此可以通过H ough 变换检测出图像中文本行的走向,
从而得到倾斜角度。
图1 笛卡儿坐标系到极坐标系的H ough 变换
2 改进H ough 变换的文本图像倾斜校正算法
2.1 变分辨率下的分级H ough 变换
影响H ough 变换实用化的一个重要因素是计算量大,较大的检测范围(H m ax -H m in )和较高的检测精度H step 将会急剧地增加时间与内存的消耗,这对于批量文本图倾斜校正的实用化无疑是非常不利的。针对(-90b ,90b )的大检测范围和精度为0.1b 的倾角检测,为了有效减少运算时间,我们引入了在变分辨率图像中进行分级H ough 变换的思想[6]:
1)先在大区间$H 内用低精度D H c 进行H ough 变换,得到倾斜角度的粗略值H c ;
2)然后从H c 出发,在宽度为D H c 的小邻域内用高精度D H 再进行H ough 变换,得到倾斜角度的精确值。
粗精度H ough 变换可以在低分辨率的图像上进行,而最后计算精确角度值的H ough 变换可以在高分辨率图像(即原始文本图像)上进行,当D H c m D H 时,就可以使H ough 变换的运算量大为减少。
得到变分辨率图像组的方法是:基于H ough 变换的抗干扰性能,以保留黑像素点为原则,通过对原图像进行水平和竖直方向减半采样的方式得到低一级分辨率的图像,以此类推,即可得到一组分辨率由高至低的变分辨率图像。则第S -1层和第S 层图像的数据关系可表示为:
B (s ,i ,j)=B (s -1,2i ,2j )G B (s -1,2i ,2j +1)G B (s -1,2i +1,2j )G B (s -1,2i +1,2j +1)(1)其中B (s ,i ,j ),j =1,2,,,2L-S 表示/金字塔0变分辨率图像中第S 层(自底至顶,从0层到L 层)的i 行j 列的像素值,为BOOL 型变量,0代表白像素点,1代表黑像素点。原始图像即为B (0,i ,j )。
在进行第一步粗略检测倾斜角度时,选择变分辨率图像中的哪一级图像作为检测数据对检测速度和准确率影响很大,图像越小,检测速度越快,但过小的图像在后续形态学膨胀及轮廓提取处理时,可能会导致相邻文本行粘连在一起,从而造成较大的误差。
由于待处理的原始图像来源于扫描输入或网页图像等多种途径,分辨率差异很大,固定采样次数显然不是最好的选
择。通过实验,本文算法选择分辨率为R T =350@350作为第
一步倾斜角粗检测时文本图像分辨率的下限,已能满足在倾角检测较为准确的前提下降低计算时间复杂度的要求。2.2 H ough 变换数据提取算法2.2.1 算法的提出
H ough 变换包含了很多浮点运算,二值化灰度图像后,如果直接对图像中的所有黑像素点做H ough 变换,将会造成较大的计算量。此外,由于文本行中字符之间存在间隔,且文本行中的字符并不完全共线,导致H ough 变换极易受到图像区域和文字笔画粗细等因素的干扰,检测出的文本图像倾斜角度误差较大。因此必须有选择地提取能够代表图像中文本行走向的像素点作为H ough 变换的初始数据。
本算法对不同分辨率下的图像使用了不同的数据提取方法。在倾角粗检测时,对低分辨率图像采用形态学膨胀和轮廓提取的方式提取数据。一般来说,由于涉及到整幅图像的逐像素计算,膨胀和轮廓提取会消耗较多的时间,不利于批量的文本图像倾斜校正处理,但对图像预先的变分辨率采样很
好地弥补了这个不足,通过减少原始图像的尺寸使膨胀和轮廓提取的计算量大为减少,将它们的时间消耗量降低到一个很小的程度。
经过粗略校正后,图像已处于小角度倾斜状态。在倾角细检测时,对分辨率较高的原图像采用游程平滑与水平边缘提取的数据提取算法,可以消除笔画粗细对测量精度的影响,由于只需进行水平方向的游程平滑,因此具有较高的检测速度。2.2.2 形态学膨胀和轮廓提取
在汉字笔画之间存在空白间隔,而英文字母、数字、标点符号等也存在大量的空白或小间隔。为了减小误差、提高倾斜角的检测精度,需要对文本行进行字符孔洞填充,填补文本行内的空白。形态学膨胀运算能够起到模糊图像细节、扩张图形的作用,选择合适的结构元素,可以填平文本行边缘上那些不平滑的凹陷部分,弥补字符间的裂痕。
图像集合A 用结构元素B 来膨胀可以定义为[7]:
A á
B ={x |[(B ^
)x H A ]A A }(2)
其中B ^是结构元素B 关于原点的映射。
图2 膨胀运算图示
在这里,结构元素的选择是十分重要的,汉字和西方字符
的笔画基本都在一个外接矩形之内,因此本文算法选择了长方形的结构元素。在实验中我们采用一个3@2的长方形结构元素以适应低分辨率下的图像,原点位于该结构元素的中下部(2,2)处。
对膨胀后的文本图像采用提取轮廓的方法,可以大大减少文本图像中的前景像素数目,特别是减少了图像区的绝大部分像素。通过大量实验表明,在H ough 变换之前,先提取文本图像的轮廓,然后将其作为H ough 变换的操作对象,不仅可以减少图像区对文本区的干扰,更减少了H ough 变换的运算时间,提高了程序运行速度。
提取轮廓的方法:首先对图像进行扫描,当发现黑像素时检查该像素的4-邻域,如果全为黑像素,则使该像素的值为
0;否则,使该像素的值为1。
我们对图3中文本图像(a )进行膨胀和提取轮廓操作
1814 计算机应用2007年
后,再进行H ough 变换,所得到的累加矩阵H (Q ,H )的效果如(c)所示,直接对文本图像进行Hough 变换的累加矩阵效果
如(b)(效果图中以灰度级代表了累加计数的大小,其中为了方便显示,对图像作了一定变形处理)
。
图3 进行H ough 变换的累加矩阵效果
由图3可以看出,经过膨胀和提取轮廓处理后,累加矩阵
中局部极大值区域明显减小,且极大值点更为突出,同时文本图像倾斜角的搜索范围也相应缩小,即累加矩阵中具有固定间隔的局部极大值的H 列数目减少了。所以,我们提出的H ough 变换改进方法提高了文本图像倾斜角的发现精度。2.2.3 游程平滑算法和水平边缘的提取游程平滑算法(R un -L eng t h S m oo thi ng A l gor it hm,RLSA )起源于游程编码的思想,其原理是对同一扫描行上的相邻黑像素点之间的距离进行检测,当两相邻黑像素点之间的空白游程长度小于阈值时,则用黑像素点填充两点之间的空白游程。
设L =(B 1,B 2,,,B i ,W i+1,,,W j-1,B j ,,,B n )为扫描行上的一段游程,其中(B 1,,,B i )和(B j ,,,B n )由两段连续的黑像素点组成,而(W i+1,,,W j-1)由一段连续的白像素点组成。若白像素点的游程长度D w =j -i -1小于阈值T,则平滑后的游程不变;当白游程长度D w 大于阈值T 时,则将白像素游程(W i+1,,,W j -1)全部填充为黑像素点,平滑后的游程为L 2=(B 1,B 2,,,B i ,B i+1,,,B j -1,B j ,,,B n )。当阈值T =4时,字符点阵图像与其经过游程平滑处理后的效果如图4
所示。
图4 游程平滑处理前后对比
由图4可以看出,在文本图像中应用游程平滑算法,可以模糊文本行边缘细节,使图像水平边缘更为平整,与文本行走向更加贴近。游程平滑算法的优点在于运算速度快,而且我们只需要使用水平游程平滑来进行水平边缘的提取,进一步降低了平滑的运算量,因此在高分辨率大尺寸文本图像的数据提取中仍能保持较快的速度。
水平边缘保留了文本图像倾斜角度的基本信息,而由于文字笔画都有一定的粗细,会对测量角度的精度有一定的影响。大量实验表明,提取水平边缘为文本行的特征点,并以此作为H ough 变换的目标像素,不仅可以消除笔画粗细对测量精度的影响,而且减小了计算量,提高了程序运行速度。
提取水平边缘的方法较为简单:首先对图像进行列扫描,当像素值发生变化时,使该像素值为1;若像素未发生变化,则使该像素值为0。
2.3 高检测精度下H ough 变换算法的改进
当检测的精度由1b 提高到0.1b 时,原先投票到点(Q ,
H +1b )的票数将被分散到(Q ,H +0b )到(Q ,H +0.9b )的10个点上,造成累加数组中投票数的扩散。这种扩散会导致H ough 变换累加数组中局部极大值不明显,从而影响倾角的判断。当页面中存在不同方向的多条直线(如表格),或含有较多非文字图像区域时,可能会出现多个与倾斜角无关的局部极大值,在参数空间中产生虚交点。如果此时由于投票数的扩散造成正确局部极大值的削弱,就会造成倾角的误判。文献[8,9]指出,当倾角检测精度过高时,局部极值的扩散将不可避免。通过以下三个步骤,对高检测精度下的H ough 变换算法进行改进:
1)二值化处理后先去除文本图像的边缘,不仅可以避免在扫描质量较差时在图像边缘产生大段黑色噪声点对算法的影响,而且可以在后续逐像素的数据提取操作中减少计算量。
2)为了减少文字混排及噪声等原因对H ough 变换的干扰,需要对图像中各像素点的投票资格进行限定,即只有大于门限的投票计数才会计入最后的累加矩阵中对H 列的投票统计。设置投票门限W =K m ax W (Q ,H ),其中W (Q ,H )为累加矩阵对应元素的投票计数。K 的取值与具体图像的页面结构及清晰程度有关,通过实验我们选取K =0.8,可以较好地去除虚交点。
3)精度D H 的提高分散了同一直线上的投票数,因此可以适当压缩Q 的量级,增强累加矩阵的局部极值以利于区分。2.4 基于偏移值的页面倾斜校正方法
页面倾斜校正一般采用旋转变换的方法,旋转变换虽然直观简单,但是计算量较大。当文本页面的大小为W @H 时,旋转变换需要4WH 次乘法运算和2WH 次加法运算。本文采用基于偏移值的方法,预先生成像素点的水平、竖直偏移值,快速地对倾斜页面进行校正[10]。当倾斜角为H 时,对应于第j 列的像素点的竖直方向偏移值为$y j =j /(W /(Y o ff +1)),其中Y o ff =[W @tan H ];而第i 行的像素点的水平方向偏移值为$x j =i/(W /(X o ff +1)),其中X o ff =[H @tan H ]。该方法只需要2WH 次加法运算,可以显著地减少校正的时间。2.5 算法流程
图5 改进H ough 变换的文本图像倾斜校正
改进H ough 变换的文本图像倾斜校正算法采用/渐进0
的方式,以不同的数据提取算法对两种分辨率下的文本图像进行H ough 变换,实现了由粗到细的倾斜较正,算法描述为:
1)对原始文本图像二值化后,去除边缘,进行减半采样处理,并依次得到一组分辨率由高至低的图像,以R T =350@350为采样分辨率的下界;
2)选择最低分辨率图像,进行形态学膨胀处理,并提取轮廓;
3)以1b 为计算精度,(-90b ,90b )为计算区间,进行H ough 变换,并在步骤6)中使用该值;
4)用偏移值法进行粗倾斜校正;
5)选择最高分辨率图像(即原图),进行游程平滑处理,提取水平边缘;
6)在倾角粗略值的基础上,以0.1b 为计算精度,[-3b ,3b ]为计算区间,进行H ough 变换,并以0.8为投票门限得到
1815第7期周冠玮等:基于改进H ough 变换的文本图像倾斜校正方法
倾角的精确值;
7)用偏移值法进行细倾斜校正。
3 实验结果与分析
图6是一幅倾斜的文本图像及其校正后的结果(为了显示方便,进行了适当缩放),经过人工测算其倾角为7.6b ,采用传统的标准H ough 变换检测倾角为8.0b ,而本文算法检测得到的倾斜角度为7.6b ,检测结果正确。实验结果证明本算法提高了文本图像倾
斜检测的精确度。
图6 倾斜文本图像及其校正结果
为了测试算法的准确率,选取了6幅排版样式、尺寸大小各不相同的灰度文本图像,将每幅图像从-85b 到85b 倾斜12个角度,共得到了72幅图像。然后使用本文算法分别对每个倾斜角度的6幅图像进行检测,统计后得到实验结果如表1,由于算法检测精度为0.1b ,因此我们将统计后的实验结果保留到小数点后2位。计算后可得算法的平均误差为0.26b ,平均准确率为99.32%,可见算法的准确率较高。
表1 算法准确率测试
实际
倾角/b 检测
角度/b 误差
/b 准确率(%)
实际
倾角/b 检测
角度/b
误差/b
准确率(%)
-85-84.730.2799.681515.160.1698.93-75-75.350.3599.533029.600.4098.67-60-59.890.1199.824545.240.2499.47-45-45.460.4698.986060.290.2999.52-30-30.090.0999.707575.180.1899.76-15
-15.280.28
98.13
85
84.68
0.32
99.62
表2 标准H ough 变换与本文算法检测倾角的时间比较图像尺寸S HT 时间/s 本文算法时间/s 图像尺寸SHT 时间/s 本文算法时间/s 649@2821.3220.4111010@10813.9060.851694@544
2.053
0.711957@8381.7230.6511566@232423.694 2.7841700@219911.377
2.6231541@22271
3.549 2.754722@5841.4220.561826@992
1.382
0.480
868@1030
7.711
0.911
另外选取了10幅来源于扫描输入及网络截取,版面为纯文字、含表格或图像域的灰度文本图像,比较传统的标准H ough 变换(以1b 为精度)与本文算法(以0.1b 为精度)的倾斜检测时间,表2列出了比较结果(实验在P41.8G CPU,256M 内存,W i nXP SP2操作系统平台下进行)。
实验表明,将检测的精度提高了10倍后,本文算法的倾角检测速度还是要远快于标准H ough 变换(Standard H ough T ransfor m,S HT ),特别是当图像尺寸增大,黑像素点数量增加时,速度的提高体现得更加明显。使用本文算法检测2000@2000像素的文本图像倾斜角度,平均检测时间在3s 左右。
4 结语
本文提出了一种基于改进Hough 变换的文本图像倾斜校正方法。对变分辨率图像采用不同的数据提取算法进行了两级H ough 变换,并利用去除图像边缘及合理设置投票门限等改进H ough 变换的措施,减小了非文本方向直线段及文字笔画粗细对倾角判定产生的不利影响,使用基于偏移值的方法实现页面倾斜的快速校正。实验结果表明,该算法实现了大
范围高精度的文本图像倾角的快速检测和校正,适用于扫描输入或网页图像等多种形式,具有较高的实用性。参考文献:
[1] ISH I TAN I Y .Docum ent ske w detecti on based on l ocal region co m-p lexity[C ]//1993I EEE Internati onal Con ference on Docum ent A-n al ysis and Recogn iti on.Tsukub a ,Japan :IEEE Co m puter Society ,1993:49-52.
[2] O p GOR M AN L .Th e docum ent s pectrum f or page layou t ana l ysis[J].
IEEE Transacti ons on Patt ern Analys i s and M ach i ne Intelli gen ce ,1993,15(11):1162-1173.
[3] PSTL W.Detection of li near obli que structure and ske w sca n i n d i g-i
ti zed documen t s[C ]//Proceed i ngs of the 8t h Internati onal Con ference on Pattern Recogn iti on.Paris ,France :[s .n .],1986:687-689.[4] CHEN M ,D I NG X Q .A robu st s k e w detecti on al gorith m f or
grayscal e docum en t i m age[C ]//1999IEEE In t ernational Con fer -ence on Docum en tAnalys i s and Recogn iti on.B anga l ore ,I nd ia :[s .n .]1999:617-620.
[5] BALLARD D H.Gen erali z i ng t h e hough transfor m to detect arb itrary
shapes[J].Pattern Recogn ition ,1981,13(4):111-122.
[6] 瞿洋,杨利平.H ough 变换OCR 图像倾斜矫正方法[J ].中国图
象图形学报,2001,6A (2):178-181.
[7] 章毓晋.图像处理和分析[M ].北京:清华大学出版社,1999:
256-260.
[8] 潘武模,焦阳,王庆人.H ough 变换在中文名片图像倾斜校正中
的应用[J].中文信息学报,2001,15(3):50-56.
[9] 李政,杨扬,颉斌,等.一种基于H ough 变换的文档图像倾斜纠
正方法[J].计算机应用,2005,25(3):583-585.
[10]王姝华,李佐,蔡士杰.基于直线连续性的页面倾斜检测与校正
[J].计算机辅助设计与图形学学报,2001,13(8):736-741.
(上接第1812页)
[6] NAKAGA W A M ,M OBAS H ER B .A hybri d w eb personali zati on
m odel based on site conn ecti v i ty [C ]//Proceedi ngs ofW ebKDD .[S ..l ]:SPr i nger ,2003:59-70.
[7] WU K ,YU P S,BALL M A N A .Speedtracer :a web usage m i n i ng and
anal ys i s tool [J].I BM Syste ms J ou rna,l 1998,37(1):89-105.[8] PERKOW I TZ M ,ETZ I ONI O .Adap ti ve w eb sites :con cep t ual
cl u ster m i n i ng [C ]//In ternati onal J o i nt Conference on A rtifici al I n telli gence .S tockhol m ,Sw ed en :[s .n .],1999:264-269.
[9] S I LVESTRI F ,BARAGLI A R,PALM ER I NI P,e t al.On -li ne
gen erati on of suggesti on s for w eb users [C ]//Proceed i ngs of the IEEE In t ernational Con ference on In f or m ati on Technology :C od i ng and Co m pu ti ng .Las Vegas ,N evada ,USA:I EEE Compu t er Society ,2004:392-397.
[10]DOLOG P.Personalizati on i n d i s tri buted e-learn i ng environm en ts
[J].Co mmun ications ofACM,2004,47(11):170-178.
1816
计算机应用2007年