基于点云数据的扭曲文本图像倾斜校正方法

童立靖　郑俊朝

(北方工业大学计算机学院　北京 100144)



基于点云数据的扭曲文本图像倾斜校正方法

童立靖郑俊朝*

(北方工业大学计算机学院北京 100144)

摘要针对传统二维层面的倾斜校正算法难以处理扭曲文本的倾斜，提出一种基于点云数据的扭曲文本图像倾斜校正方法。首先，通过三维扫描仪采集文本的数据信息，重建文本的三维点云模型，接着通过检测文本在空间中的位置，定义为空间倾斜与平面倾斜，最后实现文本的自动倾斜校正。实验结果表明，基于点云数据的倾斜校正算法在处理扭曲文本的倾斜校正正确率达到95%以上。

关键词点云数据扭曲文本倾斜检测空间倾斜平面倾斜倾斜校正

0引言

随着信息技术快速发展，信息化成为人们提高办公效率、生活品质的重要途径。电子文档具有保存方便，并易于在互联网中传输等特点，因此将纸质文档转换为电子文档的技术越来越重要。目前通过电子设备来进行这种转换的方法主要是通过摄像头获取文本资料数字图像，经过一系列的图像预处理、OCR(光学字符识别)等将其转化为电子文档。而在这种转换过程中，文本的倾斜会对整个转化过程产生不利的影响，因此图像的倾斜校正在图像的预处理中始终占据一个非常重要的地位。实际采集文本数字图像时，若整个文本处于一个斜面上时或者拍摄角度不对而出现射影文本情况，导致采集的文本图像出现像素的堆积，影响OCR识别率。同样若文本为具有一定厚度的书籍时，采集文本数字图像时会由于书籍的厚度出现文本扭曲，无法直接进行倾斜校正处理。

传统的二维文本图像倾斜校正算法主要分为以下几类：基于Hough变换的方法、基于投影的方法、基于K-最近邻方法以及基于Fourier变换方法。文献[1,2]中基于Hough变换的方法使用图像空间目标像素的坐标去计算参数空间中参考点的可能轨迹，是目前用得较多的一种倾斜角检测方法，但对扭曲文本图像因无法准确提取文本线而出现难以处理的情况。文献[3]以文字行之间存在一固定的行间距为基础再使用基于投影的方法来确定倾斜角度，同样无法处理扭曲文本。文献[4]使用基于投影轮廓的方法来求得倾斜角度，之后对整幅图片进行等角度旋转，而非像素的旋转，经此方法校正后的扭曲文本图像很难再接着进行扭曲恢复等处理，影响最终的OCR识别率。文献[5]使用近邻法则是找出所有中心点的K个最邻近点，计算每对近邻的矢量方向并统计生成直方图，直方图的峰值对应着整幅图像的倾角，同样对原始扭曲文本校正效果一般。文献[6]基于Fourier变换方法则以Fourier空间密度最大的方向对应于倾斜方向。虽然该方法倾斜校正较为精确,但由于空间复杂度很高, 计算的时间长, 因此在实际中使用较少。

由以上文献可知，传统的二维倾斜校正算法无法有效处理原始扭曲文本的倾斜。而本文将三维处理技术应用于文本图像倾斜校正领域，提出一种基于点云数据的扭曲文档倾斜校正方法，能有效处理扭曲文本的倾斜状况，并通过实验进行了验证。

1算法思路

图1　算法流程图

若文本模型存在噪点，会对后续的处理产生极大的影响，因此需要先对文本点云模型进行去噪。去噪后将倾斜检测分为两步：空间倾斜检测与平面倾斜检测。空间倾斜检测通过提取模型边界特征点，采用鲁棒方法求得文本模型边界所在平面的法向量，最后通过与一平行于Z轴的单位向量之间的叉乘、内积等计算出空间倾斜角，并进行判断，若倾斜则采用空间旋转算法进行旋转校正。平面倾斜检测时，由于文本模型是扭曲、非平面的，因此先对文本模型进行平面投影。接着提取投影的边界特征点，采用空间最小二乘法对其进行空间线性拟合，计算出其平面倾斜角，进行平面倾斜校正。图1是本文的算法流程图。

2点云去噪

在三维扫描仪获取结构光的投影并进行处理的过程中，不可避免地会产生一些噪点数据，这些噪点数据将会对后续的处理产生较大的干扰作用，因此必须先对其进行点云去噪。由于三维扫描仪都有配套的处理软件，可以对采集的模型数据进行初步分割，去除那些不需要的部分。但有时个别单点或者微量点云会由于人眼无法观察到而导致人工清除失败，因此进行去噪的主要目的就是去除那些遗漏的离群点。本文采用的方法是基于K-近邻的散乱点云去噪算法。

2.1K-近邻搜索

文本模型是由无数个孤立的点组成的，因此我们读入到内存中的数据点都是混乱的、无序的，这和传统的BMP位图有着显著区别。所以在对模型进行其他处理前，必须先将模型中的散乱点通过某种结构关联起来，建立数据点之间的空间拓扑关系。本文采用K-近邻结构[7]。

目前最常用的K-近邻计算方法有八叉树法、 空间单元格法和K-d树法。其中前两种方法都是基于空间包围盒的划分， 后一种方法则用来查找相距最近的两点。本文采用空间单元格法进行K-近邻计算。首先设P=Pi(i=0,1,…,n)是文本点云模型S上的一个采样点集，将S中与当前点Pi距离最近的k个数据点称为点Pi的K-近邻，记作Nb(p)。接着读入文本模型数据点集，将整个点集的坐标存入三个一维数组中，得到模型点集在X、Y、Z三个坐标轴方向上的最大值与最小值，然后根据极值信息，k值及点的总数n，计算出子立方体边长L。同时将文本点云模型划分成m′×n′×l′个子立方体，记录每个子立方体所包含的数据点以及每个点所在的立方体索引号，并删去不包含任何点的子立方体。最后通过子立方体内点的信息遍历数据点进行K-近邻搜索。

定义三个方向上最小坐标为: Min _x、Min _ y、Min _z；最大坐标为: Max _ x、Max _ y、Max _ z，则式(1)文本点云模型的子立方体的长度L：

(1)

其中β为调节立方体编程L大小的比例因子；n为数据点的总个数；k为可调整的近邻点的个数。那么由式(2)可以推导出子立方体在三个坐标上的个数：

(2)

同样由式(3)可推导出当前点P(x,y,z)在子立方体中三个坐标方向的索引号：

(3)

在此为每一个立方体子空间建立一链表。该表存储每个子立方体内的所有点，并统计该子立方体内点的个数，其结构如下：

typedefstructCubecell

{

LinkedListLink；

//子立方体内数据点集表的头指针

intn；

//子立方体中所含数据点的个数

}Cube;

求取当前点的K个近邻点的步骤为：

1) 根据当前点的坐标值，确定其所在子立方体的索引号，同时将此子立方体视为初始搜索区域；

2) 计算当前点到所在立方体六个面的最短距离ds；

3) 计算当前搜索区域点的总个数N1，若N1不小于K，则接着计算当前点与搜索区域内其他点的最大距离dmax。若dmax小于ds，取前k个点为当前点的K近邻点，否则以当前区域为中心向周围扩展建立新的搜索区域;

4) 为每一个数据点建立一个k邻近表。该表保存每个点的k个邻近点以及它与邻近点的距离，其结构如下：

typedefstructKpoint

{

doublex,，y，z；

// 邻近点的坐标信息

doubledistance；

// 数据点与邻近点之间的距离

structKpoint*next；

//下一个邻近点

}Kpoint, *List；

2.2邻域平均算法

建立好散乱点之间的空间拓扑关系之后，就可以使用二维图像处理中的滤波算法对点云模型进行去噪处理。遍历模型搜索每个数据点的K-近邻，采用邻域平均法进行去噪。 具体算法描述如下[8]：

1) 读入三维文本模型点云数据；

2) 建立散乱点云之间的空间拓扑关系；

3) 搜索当前点Pi的K-近邻Nb(p)；

4) 计算当前点Pj与其各K-近邻点之间的距离，取其平均值Dmid(pi)可由式(4)求出：

(4)

5) 判断该平均距离Dmid(pi) 是否大于设定的阈值D，若超过，则认为该点是噪点，将其删除；

6) 重复 3)～5)，直到处理完所有的数据点。

3倾斜检测

首先对文本模型可能发生的倾斜情况进行分类，在此共分为三大类：空间单倾斜、平面单倾斜、空间平面双倾斜。以图2(a)所示图像为例，文本点云模型在空间上存在倾斜，同时如图2(b)所示，模型在平面上也存在倾斜，因此模型属于空间平面双倾斜类。图中曲面部分为扭曲文本模型，平面部分为一垂直于Z轴的对照平面，用于观察文本模型在空间中倾斜状况。因此结合分类情况以及文本模型本身特点，将对文本点云模型的倾斜检测分为两步：空间倾斜检测与平面倾斜检测。

图2　倾斜检测示意

3.1空间倾斜检测

由于本文研究的文档模型是扭曲的，也就是说其所有的点并不落在同一个平面上。因此，需要先选择某一斜切面为切入点，通过它来研究完整文本模型的特征。结合实际情况，选择文本模型左右边界所在的平面为我们所需要的平面。确定平面后，采用曲面边界提取算法采集模型的边界特征点。

点云去噪阶段已获得当前点p的K近邻点集X={x0,x1,…,xk-1}，设X的中心点v，可由式(5)计算[9，10]：

(5)

Ax+By+Cz+D=0

(6)

其中A=xp-xv，B=yp-yv，C=zp-zv，D可由式(7)计算：

(7)

图3　模型边界分析图

得到模型的边界特征点集之后，通过限制边界点的X值与Y值得到模型左右边界特征点，如图3所示。

通过鲁棒的方法求得左右边界所在平面的法向量[11]。由式(8)计算平面法向量m的分向量(mx,my,mz)：

(8)

这里的N是特征点集中的顶点总数，(xi,yi,zi)是第i个特征点的位置坐标，next(i)=(i+1)modN是点i的下一个顶点序号。取模运算保证了第(N-1)号顶点的后一个顶点是顶点0。这种方法在计算法向量的每一个分量过程中，只需对每一条边使用一次乘法运算，而且不需要做共线测试。

得到m向量后先将其单位化，得一单位法向量m′。接着选取一平行于Z轴的单位向量n(0,0,1)，并由式(9)计算向量m′与n的夹角：

(9)

计算出夹角后设一阈值D=0.5°，若夹角位于(-D,D)内，则认为模型在空间中无倾斜，否则继续对两个向量进行叉乘运算，得到一新向量即空间旋转所需要的转轴，并使用空间旋转算法对其进行空间旋转。

图4(a)中曲面部分为原始模型，平面为一垂直于Z轴的对照平面，图4(b)为空间校正后模型，黑色线条为上文中所提到的向量m′、n以及它们叉乘后得到的向量。

图4　空间校正示意

3.2平面倾斜检测

经过空间倾斜检测及校正，此时整个文本模型垂直于Z轴。先将文档模型垂直投影到Z=0平面上，投影到此平面上后的模型Z坐标值皆为0，可减少计算量，提高检测精度。

投影后采集投影四条边界的特征点，使用基于最小二乘法的空间线性拟合算法，对模型的四条边界进行线性拟合，分别计算上下两条直线与左右两条直线的斜率，并判定两对倾斜角的差值是否在一个范围(-1°，1°)内。结果可能存在三种情况：

1) 若每对倾斜角的差值都在范围内，则对两对边界直线的倾斜角取两轮平均值，这样可以得到一个高精度的倾斜角；

2) 若其中一对差值在范围内，另一对差值不在范围内，则取差值在范围内的一对的平均值为倾斜角；

3) 若两对边界线斜率均不在，则提示模型不合格。

基于初期采集模型时已经过选择与处理，因此后两种情况较少。

设空间内方向向量为s=(m,n,p)且过(x0,y0,z0)点的直线方程由式(10)表示[12,13]：

(10)

当点(xi,yi,zi) 不在直线上时，分别记其在x方向、y方向、z方向的误差为(εi2,εi2,εi3)。作为最佳拟合直线，必须同时考虑这三个方向的误差。根据最佳平方逼近原理，最佳直线应满足式(11)：

(11)

最小。因为各测量点在x方向、y方向、z方向的误差(εi2,εi2,εi3)服从正态分布，所以最佳直线也应满足式(12)：

(12)

据此我们在约束条件式(11)式(12)下求由离散点 (xi,yi,zi)，i=1,2,…,N，所确定的最佳直线。

3.3空间旋转算法

本文使用的是由薛文风[14]提出的空间坐标旋转算法。设一个点通过轴(x0,y0,z0)，其方向余弦为(nx,ny,nz)。其中θ为坐标点(x,y,z)绕该轴的旋转角度。则旋转后的点经式(13)计算：

x′ =(x-x0)[nx2(1-cosθ) + cosθ] +(y-y0)[nxny(1-cosθ)-nzsinθ]+ (z-z0)[nxnz(1-cosθ) +nysinθ] +x0y′ =(x-x0)[nxny(1-cosθ) +nzcosθ] +(y-y0)[ny2(1-cosθ)-cosθ]+ (z-z0)[nynz(1-cosθ)-nxsinθ] +y0z′ =(x-x0)[nxnz(1-cosθ)-nycosθ]+(y-y0)[nynz(1-cosθ)-nxcosθ]+(z-z0)[nz2(1-cosθ)-cosθ] +z0

(13)

当(x0,y0,z0)=(0,0,0)时，该轴通过原点绕任意轴旋转的变换关系表达式比较长，而且需要浮点数来表示，所以在程序编写时，最好在计算表达式之前先把sinθ和cosθ算出，以提高程序的执行速度。值得注意的是，当进行空间检测得到所需数据后，若存在倾斜需先进行空间倾斜校正，以免干扰平面倾斜角的计算。

4实验结果

本算法在VisualStudio2005环境下采用C++语言实现，测试环境为:Intel®CoreTM7cpu; 内存 8GB;操作系统为Windows7的机器上进行。本文先使用三维扫描仪对5本不同厚度的书籍共采集了50个书籍点云模型，其中空间域平面倾斜角皆在(-45°,45°)范围内。所用书籍均为16开普通中文书。接着使用普通摄像头采集了50幅BMP图像，拍摄摄像头像素为500万，图像的获取均在光照均匀的环境下进行，忽略噪声的干扰。

表1将传统的Hough变换法、投影法与本文方法对重度扭曲文本倾斜检测精度进行了对比分析。传统的Hough变换法、投影法与K近邻法总体检测正确率都低于50%，而本文方法对三种情况的正确率都达到95%以上。此处的正确率是指经倾斜校正后视觉上无倾斜的文本图像个数与参加测试的样本个数之比。由实验结果可知传统的二维倾斜校正方法只能对扭曲程度较轻的文本进行有效校正，对于厚度较大、扭曲程度较高的倾斜文本处理能力很差。而本文方法则具有很大的适用范围，对于以上情况均有很高的校正正确率。

表1　原始扭曲文本总体校正正确率对比分析

用本文算法对选取模型进行倾斜校正，部分实验效果对比图如图5-图7所示。其中图5为扭曲文本空间单倾斜对比图，图6为扭曲文本空间平面双倾斜校正效果对比图，图7为非扭曲文本倾斜校正效果对比图。

图5　单倾斜对比

图6　双倾斜对比

图7　校正效果对比

5结语

本文结合当前快速发展的三维处理技术，将三维点云处理技术应用到文本图像倾斜校正领域，克服了传统二维倾斜校正方法对原始扭曲文本、射影文本倾斜校正效果不佳的缺点。提出的基于点云数据的扭曲文本倾斜校正方法，对于复杂文本如扭曲文本、射影文本可以直接进行倾斜校正处理。经试验表明，本文方法对于扭曲文本倾斜校正正确率能达到95%。本方法已试用于本实验室开发的辅助阅读器改进项目，实现了对于市面上大部分不同厚度的书籍的自动倾斜校正处理，扩大了阅读器使用范围，提高了用户操作容错率。

参考文献

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

[2] 段汝娇,赵伟,黄松岭. 一种基于改进Hough变换的直线快速检测算法[J]. 仪器仪表学报, 2012, 31(12):2774-2780.

[3] 张顺利,李卫斌,吉军. 基于投影的文档图像倾斜校正方法[J].计算机工程与应用,2010,46(3): 166-168.

[4] 程立,姚为,李波. 基于投影轮廓的文本图像倾斜检测[J]. 中国图象图形学报,2015,20(1):29-38.

[5]DeyP,NoushathS.Arobustskewdetectionmethodforscanneddocumentimages[J].PatternRecognition, 2010, 43(3):937-948.

[6]PSTLW.Detectionoflinearobliquestructureandskewscanindigitizeddocuments[C]//Proceedingsofthe8thInternationalConferenceonPatternRecognition.Paris,France:[s.n.],1986:687- 689.

[7] 谢方方,徐连诚,牛冰茹. 一种基于反向K近邻的孤立点检测改进算法[J].计算机应用与软件,2014,31(6),267-270.

[8] 曹爽,岳建平,马文. 基于特征选择的双边滤波点云去噪算法[J]. 东南大学学报(自然科学版),2013,43(S2):351-354.

[9] 陈义仁,王一宾,彭张节，等．一种改进的散乱点云边界特征点提取算法[J]. 计算机工程与应用,2012,48(23):177-180.

[10] 吴禄慎,晏海平,陈华伟，等. 一种基于散乱点云的边界提取算法[J]. 计算机应用与软件，2014,31(11):264-268.

[11] 李宝,程志全,党岗,等. 三维点云法向量估计综述[J]. 计算机工程与应用,2010,46(23):1-7.

[12] 姚宜斌,黄书华,孔建,等. 空间直线拟合的整体最小二乘算法[J]. 武汉大学学报(信息科学版),2014,39(5):571-574.

[13] 王继刚,周立,蒋廷臣，等. 一种简单的加权整体最小二乘直线拟合方法[J]．测绘通报,2014(4):33-35.

[14] 薛文风. 三维空间坐标的旋转算法[J].电脑编程技巧与维护,1995(6):59-60.

A TILT CORRECTION METHOD FOR DISTORTED TEXT ANDIMAGEBASEDONPOINTCLOUDDATA

Tong LijingZheng Junchao*

(College of Computer, North China University of Technology, Beijing 100144, China)

AbstractIn view of that traditional two-dimensional tilt correction algorithm is difficult to deal with the tilts of distorted text, we put forward a point cloud data-based tilt correction method for distortion text and image. First, it collects data information of text by a 3D scanner, and reconstructs the 3D point cloud model of text. Then according to the examined text position in space, it defines the tilt as either the space tilt or plane tilt. Finally it realises automatic tilt correction of the text. Experimental results show that the correction rate of tilt correction algorithm based on point cloud data reaches over 95% in dealing with the distorted text.

KeywordsPoint cloud dataDistorted textSkew detectionSpace tiltPlane tiltTilt correction

收稿日期：2015-06-10。国家自然科学基金项目(61371142)；北京市教委专项(PXM2013_014212_000026)。童立靖，副教授，主研领域：图像处理，智能控制，系统辨识等。郑俊朝，硕士生。

中图分类号TP3

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.06.043