巨志勇，何晓蕾，王超男

(上海理工大学 上海现代光学系统重点实验室，上海 200093)



基于文本行基线的倾斜角检测算法

巨志勇，何晓蕾，王超男

(上海理工大学 上海现代光学系统重点实验室，上海 200093)

针对文本图像倾斜检测问题，提出了一种新的基于文本行基线的倾斜角检测算法。该算法用边界标记自动机对一组同行的字符进行轮廓(外边界)跟踪，并标记出字符的最小外接矩形(MER)和字符的边框。在此基础上通过相邻字符间的行高差和字符区域的面积来剔除字符的冗余部分，最后用剩余部分的字符边框底边中点来拟合一条直线，即行文本的基线，并确定文本的倾斜角度。实验结果表明，该方法有效，同时倾斜角检测的精确性得到了优化。

文本图像；倾斜检测；边界标定；直线拟合

JU Zhiyong, HE Xiaolei, WANG Chaonan

(Shanghai Key Laboratory of Modern Optical System, University of Shanghai for Science & Technology,Shanghai 200093, China)

文本图像的倾斜是文本数字化工程中不可避免的问题，扫描时即使再仔细地摆放也会存在小角度的倾斜[1]。因此，在光学字符识别(OCR)系统中，文本图像的倾斜角检测与矫正是字符预处理中的重要一步。现在多数的光学字符识别(OCR)系统都采用串行分立字符识别框架，通用模型如图1所示[2]。

图1 OCR系统的通用模型

目前存在的倾斜角检测算法主要有以下几类：一是基于投影[3]的方法，这种方法只适用于纯文本图像。随着图像变大以及版面复杂度的增加，出错几率和计算量会大幅增加；二是基于Hough变换[4]的方法，Hough变换精度较高，但时间开销和存储开销都比较大；三是基于最近邻簇法[5]，耗时较多，而且精度有待提高；四是基于Fourier变换的方法，Fourier变换的运算量较大，所以在实际中较少使用。虽然后续有这些算法的众多改进，但均存在或多或少的限制条件，影响算法效果。

本文提出了一种基于文本行基线的倾斜角检测算法。利用字符本身的结构特点，选取文本图像中的一部分，有效剔除了排版和要求纯文本图像的限制条件。本文算法的核心是以字符边框底边的中点为特征点，通过字符的行高和联通区域面积来剔除文本的冗余，根据剩余字符的特征点来拟合行文本的基线，最后确定文本的倾斜角度。

1 最小外接矩形的确定

图像的外接矩形是图像的一个几何特征[6-9]。在图像处理与分析的过程中，几何特征具有重要的意义。本文使用最小外接矩形[10]。将图像定义在二维坐标X轴与Y轴上，因此文本图像的每一个像素点在坐标轴上都有对应的坐标[11]。利用边界标定自动机对字符的轮廓进行跟踪，以某一像素点为起始点，起动边界标定自动机，逆时针方向进行跟踪，跟踪边界像素点的同时记录该像素的坐标，跟踪检测到起始点表明该字符的轮廓检测完毕。循环比较这一坐标数组，分别得到X轴与Y轴上的最大与最小的坐标值 (ymax,ymin,xmax,xmin)。则以(ymax,xmax),(ymax,xmin),(ymin,xmax),(ymin,xmin)这4个坐标为顶点的矩形就是字符图像的最小外接矩形(MER)[12-13]，那么字符区域MER的面积为

A=(xmax-xmin)×(ymax-ymin)

(1)

图2 字符最小外接矩形

2 基线的检测定位

2.1 特征点的选择

设一行文本图像T由n个字符Ci组成，字符按照从左向右的顺序排列，即T={C1,C2,…,Cn}。设Pi=(xi,yi)是字符Ci边框底边中点，而P={p1,p2,…,pn}表示这些边框底边中点的集合。由于文本中大多数字符为上行字符和中行字符，其均以基线为基准，所以集合P为基线的基础。此时的集合P只是初始字符的集合。由图3可知，行文本中可能出现“a”、“o”等在中上基线内的字符，也有“T”、“h”等最高点超出上基线的字符，以及“p”、“g”等最低点低于基线的字符。不剔除这些最低点低于基线的字符，将会影响基线检测的可信度，也会对后续倾斜角的检测产生严重的误导。

根据字符的书写格式，笔者对文本行进行了切分，如图3所示。设中线和上基线之间的距离为h，则字符的行高为H1=3h或者H2=2h。由字符的边框可得到字符的高度，则h=H1-H2，规定以h作为剔除的依据。若相邻字符的边框底边中点的纵坐标差Δy≥h，则剔除行高大的那个字符。

图3 字符的书写格式和行高参考

除了删除像“p”“g”这种最低点低于基线的字符，本文还要删除像“i”“j”这种由多个非连通区域组成的字符。因非连通，自动机跟踪时会分别标记，并不会识别出这些部分属于同一个字符，而标记出的“i”“j”上的点同样会给基线检测产生较大的干扰。在标记出字符的最小外接矩形后，通过比较这些区域的面积，剔除区域面积格外小的区域。删除完冗余部分，剩下的点用‘﹒’标记。

2.2 基线定位

确定了集合P，本文用最小二乘法进行直线拟合[14]。

设基线方程

(2)

其中，pi=(xi,yi)∈p；k代表直线的斜率；b代表直线在y轴上的截距；k′和b′分别为其近似值；ε为权值。

根据最小二乘法的定义

(3)

设误差方程

(4)

文中将这一误差方程写成矩阵形式

AεX=L+V

(5)

式中

VTV=min

(6)

即

(7)

其最小二乘解为

(8)

由此即可求出k和b，即求出了直线方程。基线确定后，通过基线方程f(xi)=k×xi+b,(i=1,2,…,n)可知基线的倾斜角即与坐标轴的夹角，设基线与x轴正向的夹角为α

(9)

3 实验结果分析

为证明算法的有效性，实验分别对印刷体(新罗马体)和手写体进行测试。

实验结果以图4(a)中的倾斜行文本为例，字符的最小外接矩形用大小为一个像素的边框标记出，字符边框用绿色的标记，如图4(c)中所示的行文本，图中标记的点即为所需字符的边框底边的中点，下划线即为拟合基线。

图4 文本行基线的检测

图5 手写体行文本的基线

除了印刷字体，对于书写清晰、连笔不多的手写体文本，依据本文的算法基线也能检测出。如图5中的“ase”和“ete”，对于连笔书写或产生粘连的多个字符，自动机会识别成一个字符，因此只能标记出一个中点，但文本整体书写工整，所以并不影响基线的检测。由此可见，本文的算法对于书写工整、连笔较少的手写文本也可进行倾斜角检测。

将本算法应用于两种不同的文本，如图6和图7所示，实验证明，本文的算法对于带图的文本和纯文本同样可行，且不受排版的局限。

图6 带图文本校正前和校正后的二值图像

图7 纯文本图像矫正前和矫正后的二值图像

4 结束语

本文提出了一种基于文本行基线的文本图像倾斜角检测算法，第3部分的实验结果分析已证实了本文算法对于倾斜角检测的有效性。通过10组不同角度的对比实验可知，实验数据如表1所示，本文算法的平均误差为0.028，低于轮廓投影法和文献[1]的算法;轮廓投影法的最大绝对误差0.08，文献[1]算法的最大绝对误差为0.11，而本文算法的最大绝对误差为0.07；轮廓投影法的误差标准偏差为0.174 50，文献[1]算法的误差标准偏差为0.075 43，而本文算法的误差标准偏差为0.046 90(标准偏差反映算法的精确度，值越小代表偏差越小，说明精确度越高)。本文算法无需计算整个文本图像，只需选取一行即可对整个文本进行倾斜角的检测，这在某种程度上也提高了执行效率。而且对于工整的手写体文本也可以进行倾斜角的检测。本文算法清晰，操作方便，但对于中文及其他语言的检测仍有待改进，另外在噪声情况下也需要优化。

表1 倾斜角检测算法实验结果对比

[1] 巨志勇,王平殿.基于几何约束的文本图像倾斜角检测算法[J].计算机应用研究,2013,30(3):950-952.

[2] 顾国庆,许彦冰.数字图像区域标定的方法[J].上海理工大学学报,2001,23(4):295-299.

[3] 吴晓光,王涤琼,盛慧.一种获取图像区域最小外接矩形的算法及实现[J].计算机工程,2004,30(12):124-125.

[4] Gu Guoqing,Chen Ke. Region-labeling-automata for images in square,triangular and hexagonal lattice [J].Journal of Three Dimensional Images,2003,17(1):161-165.

[5] 卢达,谢铭培.文本行字符基线的精确测定算法[J].小型微型计算机系统,2000, 21(7):726-728.

[6] 王涤琼,张薇,顾国庆.用顶点链编码计算图像区域密集度和体态比[J].华东师范大学学报:自然科学版,2005(1):59-62.

[7] 丁克良,沈云中,欧吉坤.整体最小二乘法直线拟合[J].辽宁工程技术大学学报:自然科学版,2010,29(1):44-47.

[8] Golub G H,Van Loan C F.An analysis of the total least squares problem[J].SIAM Journal Numer Anal,1980,17(6):883-893.

[9] Van Huffel S,Vandewalle J.The total least squares problem computational aspects and analysis[M].USA:SIAM Philadelphia,1991.

[10] 曾接贤,张桂梅,储珺,等.霍夫变换与最小二乘法相结合的直线拟合[J].南昌航空大学学报:自然科学版,2003,17(4):9-13.

[11] Mehdi F,Nicolas B,Salvatore T.A robust skew detection method based on maximum gradient difference and R-signature[C].Washington DC:Proceedings of the 18th IEEE International Conference on Image Processing,2011.

[12] Lu Y,Tan C L.Improced nearest neighbor based approach to accurate document skew estimation[C].Washington DC:Proceedings of 7th International Conference on Document Analysis and Recognition,2003.

[13] Yu B,Jain A K.A robust and fast skew detection algorithm for generic documents[J].Pattern Recognition,1996,29(10):1599-1629.

A Skew Detection Algorithm Based on the Baseline of Document

For the problem, this paper proposed a new skew detection algorithm based on the baseline of document for detecting the angle of the document image. The algorithm obtains the minimum external rectangles and the frames of the characters by the region-labeling-automata, and eliminates the redundancy of characters based on the areas of the parts and the line height difference of the adjacent characters. A straight line is fitted as the baseline based on the frame of rest characters, and the skew angle is evaluated by the moment calculation. The experimental results show that this algorithm is effective and can improve the accuracy.

document image; skew detection; boundary demarcation; linear fitting

2016- 01- 12

国家自然科学基金资助项目(81101116)

巨志勇(1975-)，男，博士，讲师。研究方向：图像处理和模式识别。何晓蕾(1991-)，女，硕士研究生。研究方向：图像处理和模式识别。王超男(1992-)，女，硕士研究生。研究方向：图像处理和模式识别。

10.16180/j.cnki.issn1007-7820.2016.10.012

TP391.41

A

1007-7820(2016)10-039-04