目前,光学标记识别(Op ticalMarker Recognition, OMR)文档信息自动处理在银行票据、问卷调查、标准化阅卷以及选票统计等方面得到了广泛应用。
OMR光电阅读技术,根据事先定义的信息卡格式,通过识别特定位置处“涂黑”标记的有无确定标记代表的含义。文献[1]提出了基于图像OMR技术,该技术将涂写信息卡扫描成二值化图像;再经倾斜校正、图像分割,对分割出的小块图像(含“涂点”)的黑点数目进行计算。若大于预先设定的阈值,就认为有标记,否则没有标记,从而完成标记识别[1]。在实际应用场合,基于光电阅读方式的OMR技术对信息卡录入倾斜、纸张质量、印刷质量、填写标记规范等因素均有严格限制,对有倾斜、折皱的信息卡或填写不规范的标记会造成识别出错。而基于图像的OMR技术不仅能克服采用光电阅读OMR方式的上述缺点,而且识别精度高,对纸张质量、印刷技术要求低,可以处理略有折皱的信息卡;参数调整灵活,可适应多种版面形式的信息卡;可采用计算机数字图像处理技术保存信息卡原始图像备查,提高了系统安全性、可靠性和防伪性[1]。图像OMR技术中,倾斜校正和图像分割是最关键的,其中倾斜矫正又是图像正确分割的关键。
1 OMR图像倾斜矫正
在信息卡扫描输入过程中,由于走纸机构走纸不均匀,导致输入到计算机中的信息卡图像不可避免地产生一定的倾斜。为避免重新扫描产生倾斜的图像,在OMR图像识别预处理阶段需进行倾斜角度检测和图像矫正,确保图像分割正确和标记识别无误。对图像倾斜角度检测方法很多,应用场合和效率也各不相同。
图1 倾斜的涂写卡二值化图像
投影法[1,5,6]是检测图像倾斜角度常用方法之一,该法对每个可能存在的倾角生成投影直方图,然后使用相应评价函数选取对应角度投影直方图值最优的即为检测出的倾角。数字图像分割技术中, Hough变换是检测直线的一种有效方法,具有良好抗干扰性和鲁棒性[2] ,能实现OCR文档图像倾斜矫正[2～4]。而对OMR图像,一般包括定位标记、涂写标记和题目编号。对OMR图像,可跟踪一对水平或垂直定位标记,计算其外接矩形中心坐标检测倾角,但如果定位标记因噪声或印刷质量发生断裂时,这种方法就缺乏鲁棒性。文献[1]通过对信息卡学习获得正常图像的定位标记块的位置,并将倾斜图像沿x, y轴方向投影,所有的水平定位标记块和垂直定位标记块会分别在投影图上产生对应的峰,从而确定水平定位标记块和垂直定位标记块的位置。根据正常图像和倾斜图像的定位标记块的位置,可计算出旋转角。该法需获取正常位置图像信息,必然影响处理效率。笔者在进行基于OMR图像技术的标准化阅卷课题研究中发现,标准化考试信息卡图像中题目编号和定位标记在垂直方向排列上具有很强的方向性,提取它们边缘像素点可生成若干条近似平行的虚直线,对边缘像素点进行Hough变换便能检测出这些直线,根据检测出的直线倾角可得到信息卡图像倾角。图1是扫描中倾斜的标准化考试涂写卡二值化图像。
1. 1 图像子抽样处理
人们观察图像时,对于尺寸较小的细节部分,通常采用较高的分辨率观察,而对于尺寸较大或对比度较强的部分,只需要较低的分辨率即可。图像子抽样是降低图像分辨率的一种方法。在机器视觉和模式识别技术中,常常采用多种分辨率分析图像。通常,低分辨率图像用于分析大的图像或图像的整体特征,而高分辨率图像用于分析单个细节部分的局部特征。这种从粗到细的分析方法在模式识别中经常使用。以步长为2的子抽样可以生成原来图像相似但尺寸减半的图像。Hough变换是发现直线的一种有效的方法,然而Hough变换计算的时间、空间复杂度均很大。对于一幅W ×H的二值化图像, Hough变换的时间复杂度是O (WHθ) , 空间复杂度是O( 
，) ,其中
= 
,θmax ,θmin 和Δθ分别是检测角度范围的最大值、最小值和步长(或精度) ,由此Hough变换的计算时间、空间复杂度随图像的尺寸、角度检测范围和步长(或精度)的变化而变化。子抽样图像处理的目的在于提高倾斜角度的检测精度,减少Hough变换的时间和空间复杂度。步长为2的图像的子抽样描述为:
设f ( i, j) 是原图像, f′( i′, j′) 是子抽样后的图像, 按式(1) 生成步长为2的子抽样图像:
f′( i′, j′) = f (2 i′, 2 j′) ∪ f (2 i′, 2 j′+ 1) ∪
f (2 i′+ 1, 2 j′) ∪ f (2 i′+ 1, 2 j′+ 1) ,
0 ≤ i′≤
- 1, 0 ≤ j′≤
(1)
由(1)式知,经一次步长为2的子抽样图像处理能保留原来图像中的黑色像素而使子图像的长和宽均减为原图像的1 /2,有利于提高Hough变换倾角检测精度,减少程序运行时间。
1. 2 垂直边缘提取
使用Hough变换进行倾斜角度检测时,如果对OMR图像中每一个像素点都进行Hough变换,计算量相当大,将影响算法运算速度和实际应用价值。提取具有直线特征的边缘像素是优化Hough变换效率的有效方法。通常,OMR图像中定位标记和编号像素具有很强方向性,提取它们的边缘可生成若干条近似平行分布的虚直线,有利于倾斜角度检测;而涂写标记分布上无直线排列特点,对检测倾斜角度精度有一定的影响。通过大量实验表明,在Hough变换之前,先提取OMR图像垂直边缘,然后将垂直边缘像素点作为Hough变换的目标像素,不仅可以消除涂写标记和噪声对测量精度的影响,而且能减少计算量,提高倾角检测效率。图像垂直边缘提取算法简述:从上向下,从左到右扫描图像,对同行像素,出现由白到黑像素变化时,当前位置像素置为黑。通过垂直边缘提取后,垂直定位标记和编号边缘会生成近似平行分布的黑像素。图2是垂直边缘提取后的子图像,其中垂直定位标记和编号边缘点组成方向性很强的若干条平行虚直线。
图2 垂直边缘提取后子图像
1. 3 Hough变换倾斜检测
Hough变换能检测出图像中存在的直线,其基本原理是:直线y = ax + b对应的极坐标变换表达式ρ = xcosθ+y sinθ为该直线的Hough变换。
图3 Hough变换示意图
由Hough变换知,对任意边缘像素点p ( xi , yi ) 在(ρ, θ)变换域内可用一条正弦曲线表示。如图3是Hough变换的示意图, l1 平行于l2 。由图3 ( a) ,序对(ρ, θ) 可以唯一确定图像中一条直线,其中ρ是坐标原点到直线的垂直距离,θ是该直线到坐标原点的垂直倾角。图3 ( a ) 中, A ( xa , ya ) 和B ( xb , yb ) 点近似在同一条直线l2 上, 在变换域内对应(ρ2 ,θi) , C ( xc , yc ) 点在直线l1 上,在变换域内对应(ρ1 , θi ) 。由于l1 平行与l2 ,所以两者θi 相同而ρ2 ≠ρ1。在变换域内,它们对应相同的θi 单元列上(如图3 ( b) ) 。根据像素在直角坐标中的位置计算在(ρ, θ) 域的值, 可以构造一个累加器Coun t (θi , ρj ) ,序对(ρj , θi ) 对应累加器单元Coun t (θi , ρj ) 。在ρj = xcos (θi ) + y sin (θi ) 上共线的点集Q在变换域内对应相交于点(ρj, θi ) 的正弦曲线, Coun t (θi, ρj ) 表示相交于点(ρ, θ) 正弦曲线的个数。倾斜角度发现是检测ρθ平面细分不同单元对应的累加器Cou n t (θi ,ρj )极大值Max{ Cou n t (θi ,第3期张凯兵等: OMR图像倾斜矫正与分割7ρj) } ,对应列的θi 即为检测到的信息卡图像倾角。为避免累器Coun t (θi , ρj ) 出现局部极大值而影响角度检测精度,需要设定一个合适的门限值
,使其满足:
T =αMax{ Coun t (θi, ρj ) } , α < 1
对所有累加器单元, 如果Coun t (θi, ρj ) < T, 则
Coun t (θi , ρj ) = 0,反之Coun t (θi , ρj ) = 1。然后选取累加器
Coun t (θi , ρj ) 中所有列中累加值最大值单元θi′为检测到的图像倾角。
2 快速标记定位算法
进行“涂写”信息块图像分割前,首先要确定待识别的“涂写”信息块的位置。每个涂写块位置由水平定位标记中心横坐标和垂直定位标记块的中心纵坐标确定,两者交叉点位置作为图像分割的中心位置,以矩形区域分割。根据这一原理,对定位标记的定位只需确定水平定位标记横坐标和垂直定位标记块的纵坐标,为此本文提出一种游程段中心迭代算法。为便于描述,给出与算法描述有关的几个定义:游程段 图像检测区域中确定方向上连续黑像素构成一个游程段。水平方向上的游程段称水平游程段;垂直方向上的游程段称垂直游程段。
游程段中心 游程段起始点与终止点的中心。
游程段长度 游程段的起始点到终止点连续黑像素个数。结合以上定义,给出算法中垂直定位标记位置求解步骤:对经预处理后的二值化OMR图像,假设垂直标记在图像左方,标记个数为coun t,游程段长度阈值T, run_leng th为游程段长度, run_coun t为游程段个数, Itera tionTim es为预先设定的迭代次数。
1) 用垂直扫描线从左向右扫描OMR图像, k = 0;
2) 检测垂直扫描线上所有垂直游程段是否满足条件:
run_leng th ≥ T且run_coun t = coun t
若满足,转入3) , k = k + 1;否则,移到下一垂直扫描线,
转入2) ;
3) 按下列迭代公式计算当前垂直扫描线上第i个垂直游程段中心纵坐标第k次迭代估计值y [ i ] ( k) :
其中k为迭代次数, y [ i ] ( k) 为第i个垂直游程段中心纵坐标值, y [ i ]j, 1 , y [ i ] j, 2为第i个垂直游程段在第j次迭代时起点和终点纵坐标。
4) 若迭代次数k满足: k ≥ itra tiontim es,结束。否则转2) 。算法中迭代求解水平定位标记位置步骤与上相似,只需适当调整部分参数。
3 实验结果
本文采用标准化考试涂写卡的OMR 图像进行实验,对实际扫描涂写卡图像先Hough变换作倾角检测,然后用旋转算法旋转到正常位置,最后用快速游程段中心迭代算法分别确定水平定位标记块中心横坐标和垂直定位标记块中心纵坐标位置,以横纵定位标记的交叉点作为分割矩形中心位置。
实验中,对图1扫描倾角为5°的信息卡图像(W = 667, H =805) 在Pentium566微机上用Hough变换检测倾角,角度检测范围为[ - 45°, 45°] ,步长Δθ = 0. 05°,α = 0. 7。
表1 Hough变换检测图1倾斜角度对比表
表1表明,Hough变换能较精确地检测信息卡图像角度,且子抽样次数越多,算法执行的时间越短,以连续2次子抽样较优;表1还表明,提取垂直边缘后检测结果和效率较优。对尺寸大的图像,可执行更多次子抽样而减少倾斜角度检测的时间和空间复杂度。实验中,对矫正后的信息卡图像,使用本文算法定位水平定位标记块的横坐标和垂直标记的纵坐标与实际对应的标记块外接矩形的中心横坐标和纵坐标最多只差2个像素,分割出的图像块不会导致标记误识。该算法执行时间复杂度与迭代次数和图像大小有关。表2给出了前10个横向定位标记块中心横坐标与实际外接矩形中心横坐标的对照。
表2 定位标记坐标对照表
表2表明,本文算法能准确计算信息卡图像定位标记块坐标,实现图像快速分割。
?
参考文献:
[1] 覃胜,刘晓明. 基于图像的0MR技术的实现[J ]. 电子技术应用,2003, 29 (10) : 17 - 19.
[2] 瞿洋,杨利平. Hough变换OCR图像倾斜矫正方法[ J ]. 中国图像图形学报, 2001, 6 (2) : 178 - 181.
[3] SR IHAR I S, GOV INDARAJU V. Analysis of textual images using the hough transform[J ]. Machine Vision and App lications, 1989, 2
(3) : 141 - 153.
[4] H INDS S, F ISHER J,DpAMATO D. Document skew detection method using run2length encoding and the Hough Transform [A ]. Proceeding of 10 th International Conference on Pattern Recognition[C ],1990. 464 - 468.
[5] CIARD IELLO G, SCAFURO G, DEGRAND IM, et al. An experimental system for office document handling and text recognition[A ].
Proceedings of 9 th International Conference on Pattern Recognition[C ], 1988. 739 - 743.
[6] PAVL ID IS T, ZHOU J. Page segmentation by white streams [A ].Proceedings of the10 th International Conference on Pattern Recognition[C ], 1991. 945 - 953.