基于像素的少数民族手写体文档倾斜校正算法

王江晴,张 轶

(中南民族大学计算机科学学院,武汉430074)

基于像素的少数民族手写体文档倾斜校正算法

王江晴,张 轶

(中南民族大学计算机科学学院,武汉430074)

针对女书等少数民族手写体文献行间距不固定、竖行书写及存在连笔和粘连等特性,提出了一个能够对这一类倾斜手写体文档进行准确调整的基于像素的改进最小二乘法倾斜校正算法(I L SM P).算法同时考虑横纵坐标的误差,并对字符粘连等进行处理以进一步提高校正准确度.实验结果表明:该算法对于手写体文档的倾斜校正是有效的.

字符粘连;像素;最小二乘法;倾斜校正

少数民族文献记录着各少数民族的文化基因及历史渊源,是我国乃至全世界极其宝贵的非物质文化遗产.在众多少数民族语言文字中,女书是世界上最具性别意识的少数民族文字,这种由女性创造、女性使用、传女不传男的斜体文字,从文化层面上反映了女性的集体智慧.女书没有统一的规范化字体,她的传承主要是通过手写的方式进行.在对这些文献进行信息化时,扫描后的文档经常出现倾斜现象,不利于后续的文字分割、识别等工作,必须对其进行倾斜校正.

常用的倾斜校正方法有以下几类:基于Hough变换的方法、交叉相关性算法、水平或垂直投影法、基于傅里叶变换的方法、K-最近邻簇法[1]和基于最小二乘法的方法.基于Hough变换的方法[2]抗噪声能力强且不受文档中直线方向的影响[3],但它的数据量大,纠斜准确度偏低[4];交叉相关性算法[5]准确率高但相关矩阵的计算量较大;投影法[6]不但计算量大,且精度取决于进行不同角度投影测试时的单位步长角度值;基于傅里叶变换的方法[7]对文档中全部的像素点做傅里叶变换来进行倾斜校正,这种方法的计算量非常大,目前很少采用.

针对女书等手写体少数民族文献行间距不固定、竖行书写等问题,本文提出了一种基于像素的改进的最小二乘法 (I mproved L east Square M ethod Based on Pixel,I L SM P).算法在对各行的粘连现象进行处理以后,利用横纵坐标的误差对像素点位置进行运算,以计算文档倾斜的角度.实验结果表明,对于女书等少数民族手写体文献,该算法比其它算法具有更高的准确度.

1 最小二乘法

最小二乘法选取文本图像的子区域中字符连通域的底边中心点作为特征点[8],利用行基线与特征点的关系,建立数学模型如公式(1).

用最小二乘法计算公式拟合出基线方向[9],从而获取整个页面的倾斜角.基线的斜率值k[10,11]可通过公式(2)来求解.

其中,表示待处理图像中所有离散点横坐标的平均值,表示所有离散点纵坐标的平均值,表示所有离散点横纵坐标乘积的平均值,·表示所有离散点横纵坐标平均值的乘积,表示所有离散点横坐标的平方的平均值,表示所有离散点纵坐标的平方的平均值,Δy表示纵坐标的相对距离,Δx表示横坐标的相对距离.

最小二乘法对倾斜文档的校正是目前常用的校正方法之一.但该方法易受所选取的区域影响,不具有整体特征,且要求文档中的文本行都为水平,行间距离固定.文献[12]对该方法进行了改进,针对页面前景点来进行计算,选择文档中最大矩形和其中的像素点作为倾斜角度的检测对象.这种方法对于包含图片的文档比较有效,但要求文档书写规范,行间距离一致.

2 算法设计及描述

针对最小二乘法在处理手写体文档中连笔和粘连、行间距不固定、竖行排列等现象存在的不足,本文提出了I L SM P算法.算法中引入公式(3)[11]、公式(4).

公式(3)计算的是横坐标值存在误差情况下直线的斜率k1.由于在倾斜的手写文档中各个像素点的位置都发生了偏移,即像素点的横纵坐标值都会产生相应的偏差,若仅选择图像子区域且仅考虑其中一类误差,会对手写文档的倾斜校正工作产生影响,使校正后的文档仍存在倾斜现象.因此需要从整个文档出发,针对所有像素点进行处理,本算法同时考虑横纵坐标的误差,采用公式(4)对k、k1的值进行修正,其中α、β是预先给定的修正系数.由于k1的值较大,根据多次实验得出,在α取1、β取0.001时可以得到理想的校正效果.

I L SM P算法对手写体文档进行倾斜校正的基本流程如下:

(1)预处理.读入图像,对图像进行二值化操作,将图像转化为黑白二色;

(2)获取特征点.查找图像中字符像素点,并记录各点所在的位置,对于存在行间粘连现象的水平书写文档,通过设置阈值消除粘连现象;

(3)计算倾斜文档的倾斜角度.利用公式(4)对图像中各字符点的位置进行计算,获得斜率值K,将K值转化为对应的角度值;

(4)利用校正函数im rotate将原图像按照倾斜的角度旋转,从而对图像进行校正.

3 算法实现

3.1 预处理

在对倾斜文档进行校正前,首先要进行二值化处理,使文档图像变为黑白二色,文字部分为黑色像素点(用0表示).本文采用大津法对文档图像进行二值化处理,根据图像的参数信息自动获取一个最佳的阈值作为二值化的分界值,小于此阈值的像素值置为0,表示文字,大于此阈值的像素值置为1,表示背景,使文档图像清晰明了.

3.2 粘连处理

对于水平书写的文档,文档中可能存在行间粘连现象,会使得文字与背景的区分界限模糊,影响了倾斜角计算的准确度.针对此问题,本文通过预设的阈值T对整个文档进行逐行扫描:若第i行黑色像素的个数Hi＜T,则将第i行视为存在行间粘连,在水平方向将Hi行从左至右的像素值置为背景值1,反之,则保持原数据不变,不作处理.这不仅解决了行间粘连的现象,同时也提高了倾斜角计算的准确度.对于竖行书写的文档,则极少存在粘连现象,不需做粘连处理.

3.3 特征点选取

利用查找函数find,通过循环条件逐一对文档中的黑色像素点进行扫描,并定义一个二维数组来存放查找到的字符像素点的行列号,将扫描后查找到为黑色像素点的最小行、最大行和最小列、最大列作为新的待处理矩阵的起始和终止行列,从而仅保留文字部分,剔除多余像素信息,最大限度地记录文档中文字像素点位置,去除非文字像素点,以节省计算的数据量,提高运算速度.

3.4 页面倾斜校正

根据公式(4)计算整个文档的倾斜斜率值K,并通过反正切函数获得文档图像倾斜的弧度θ:

获得倾斜的弧度值后,将其转换为相应的角度值,判断倾斜角度所在的象限,若在第一三象限,则依据计算得出的角度对原图像做顺时针旋转;若在二四象限,则对原图像做逆时针旋转,通过旋转变换即可对原图像进行校正.校正过程如公式(6).其中,x、y为原图像的坐标位置,x′、y′为校正后的坐标位置.

4 实验结果及分析

本文对大量有代表性的、不同质量的样本进行了实验,包括以竖行排列的手写女书文档和有连笔现象的手写文档等,实验中取α=1,β=0.001,T=15.部分实验结果如图1、2所示.

图1 初始女书文档Fig.1 Initial document

图2 校正后的文档Fig.2 Adjusted document

为了进一步验证算法的有效性,将I L SM P算法与只考虑纵坐标误差的标准最小二乘法、Hough算法[8]、交叉相关性算法[9]进行了比较,比较结果如表1,表2所示.从表1中可以看出,本文提出的算法与标准最小二乘法相比,在校正效果和准确率方面都有显著的提高;从表2中可以看出,本文提出算法的误差平均值为0.035,误差标准偏差为0.03279,而Hough算法的误差平均值为0.15,误差标准偏差为0.06707,交叉相关性算法的误差平均值0.068,误差标准偏差为0.0416.本算法在对倾斜文本图像进行校正时,校正的精度比较高,且最大绝对误差和最小绝对误差也相对较小.

表1 标准最小二乘法与I LSM P比较Tab.1 Comparison about Standard Least SquareM ethod and I LSM P

表2 Hough算法、交叉相关性算法与I LSM P比较Tab.2 Comparison about Hough A lgorithm、Cross-Correlation A lgorithm and I LSM P

5 结语

针对少数民族手写体文献中存在的连笔、粘连、行间距不固定和竖行书写等特点,本文提出了一个改进的倾斜校正算法I L SM P.算法在计算斜率值时,以文档中所有文字像素点的横纵坐标位置为基本计算元素进行计算,不仅考虑了纵坐标的误差情况,同时将横坐标的误差情况也加以利用,以得出文档倾斜的角度,从而使计算得到的斜率值更为科学合理.针对水平书写方式中各行之间存在的粘连现象,本算法也加以处理.实验表明,对于女书等少数民族手写体倾斜文档,该算法是有效的.

[1] O′Goman L.The document spectrum for page layout analysis[J].IEEE T ransaction on PAM I,1993,15(11):1162-1173.

[2] 李 政,杨 扬,颉 斌,等.一种基于Hough变换的文档图像倾斜纠正方法[J].计算机应用,2005,25(3):583-585.

[3] Zhang Ruilin,Hu Yan,Fang Zhijian,et al.Skew detection and correction method of fabic images based on hough transform [C]//IC ICTA.Proceedings of the 2009 Second International Conference on Intelligent Computation Technology and A utomation.Zhangjiajie:IC ICTA,2009:340-343.

[4] 周冠玮,平西建,程 娟.基于改进Hough变换的文本图像倾斜校正方法[J].计算机应用,2007,27(7):1813-1816.

[5] 李庆峰,付忠良,刘 琴.一种高效的倾斜图像校正方法[J].计算机工程,2006,32(21):194-196.

[6] Ciardiello G,Scafur G,DegrandM T,et al.A n experimental system for office document handling and text recognition[C]//ICPR.Proceedingsofthe 9th International Conference on Pattern Recognition.Rome:ICPR,1998:739-743.

[7] PstlW.Detection of linear oblique structure and skew scan in digitized documents[C]//ICPR.Proceedings of the 8th International Conference on Pattern Recognition,Pairs:ICPR,1986:687-689.

[8] 王姝华,李 佐,蔡士杰.基于最小二乘法的文档图像倾斜检测方法[J].计算机应用与软件,2001,13(9):43-46.

[9] 王姝华,李 佐,蔡士杰.基于直线连续性的页面倾斜检测与校正[J].计算机辅助设计图形学学报,2001(8):736-741.

[10] 王 辉,牟宏鑫,王嘉梅,等.一种文本图像倾斜校正的方法[J].云南民族大学学报:自然科学版,2010,19(3):232-234.

[11] 王文周.用最小二乘法求直线斜率的新公式[J].四川工业学院学报,2000(1):67-69.

[12] 陈 波,王加俊,吴 陈.基于页面前景和最小二乘法的倾斜校正[J].计算机工程,2007,33(15):202-204.

Skew Correction Algorithm s Based on Pixel for Handwriting Document of M inority Nationality

W ang J iangqing Zhang Y iy i
(College of Computer Science,South-CentralU niversity for N ationalities,W uhan 430074,China)

A imed to the characteristics,such as conglutinations,unfixed space lines and vertical-w ritten form s in the scripts and documents in m inority nationa lities,a skew correction algorithm based on pixel called improved least square method( IL SM P)is provided.The algorithm not only takes account of the error of the x-coordinate and y-coordinatel,but also processes the touched characters,and in order to improve the accuracy of the correction.Exper imental results show that the algorithm solves the problem of skew ing handw riting document effectively.

touched characters;pixel point;least square method;skew correction

TP391

A

1672-4321(2011)01-0088-04

2010-09-20

王江晴(1964-),女,教授,博士,研究方向:人工智能,E-mail:w jqing2000@yahoo.com.cn

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