《武汉工程大学学报》 2011年01期
84-87
出版日期：2011-01-30
ISSN:1674-2869
CN:42-1779/TQ
OCR中一种基于最小一乘法的连通域去噪方法
0引言OCR （Optical Character Recognition光学字符识别）技术,是指电子设备（例如扫描仪或数码相机）检查纸上打印的字符,通过检测暗、亮的模式确定其形状,然后用字符识别方法将形状翻译成计算机文字的过程.在识别过程中,需要通过去噪获得只有要提取字符的图像.根据实际图像的特点、频谱分布规律和噪声统计特征,对于去噪已经提出了很多研究方法,比如均值模板法、领域平滑法、连通域分析、滤波等等.最小一乘法准则是1760年波斯科维奇在子午线长度研究中提出的.由于计算上比较复杂,研究长期处于停滞状态,1805年法国数学家勒让德在天文学和测地学研究中提出了最小二乘法,由于其计算上的方便和高斯等数学家的推崇,回归分析中多采用最小二乘法进行计算.但是在降低异常值影响方面,最小一乘法更为优秀［12］.本例中,根据提供的对象,对具有相似特征的图片,对比最小二乘法提出一种基于最小一乘法的连通域去噪方法.1基于最小一乘法的连通域去噪方法1.1方法和思路第一步,找到图像中的所有连通域,并获取它们各自所含像素点的个数；第二步,根据最小一乘法,计算出阈值中间值；第三步,根据阈值中间值确定阈值范围；第四步,根据阈值范围的限定对连通域进行相应的处理.所提出的方法的创新之处在于以下几点:a. 运用深度优先算法结合匹配矩阵查找连通域,在匹配矩阵中用不同的数字表识不同的连通域,提高后续工作的效率.b. 运用最小一乘法对获取的连通域信息进行处理,从而找到阈值范围的中间值.在OCR的背景下,根据字符特征和找到的中间值,确定阈值范围.1.2图像特征本例中要处理的四幅图片尺寸均为512*384,位深度为24.其特征为:（1）待获取区域面积占总图像比例较小.（2）待获取信息轮廓清晰.（3）噪声与待获取信息颜色相似.源图像如图图1所示.图1源图像（a）（b）（c）（d）
Fig.1Source images (a) (b) (c) (d)图1（a）和（b）中待获取信息放大20倍后图像如图2、图3所示.图2图1（a）待测目标放大图
Fig.2Amplify goal in Fig.1 (a)图3图1（b）待测目标放大图
Fig.3Amplify goal in Fig.1 (b)1.3准备工作第一步,利用YIQ公式将RGB图像转化为灰度图像.第二步,利用最大阈值分割算法将灰度图像转化为二值图像.第三步,利用深度优先算法对图像进行搜索,查找连通域,并对最终的结果进行不同的数字标识.匹配矩阵标识效果如图4所示.图4匹配矩阵标识效果图
Fig.4Result for match matrix show第四步,根据先验知识,在连通域大小小于10的情况下,很难构成一个完整的字符,所以将连通域大小小于10的连通域变为背景,不列入后续的统计.第1期刘渝,等：OCR中一种基于最小一乘法的连通域去噪方法
武汉工程大学学报第33卷
1.4最小二乘法和最小一乘法如果有n个数,a1,a2,a3,…,an,现在需要得到一个x使得它和这n个数的偏差a1-x,a2-x,…,an-x在总体上尽可能的小.最小二乘法便是在这一思想上提出的,其表达式为D1=fmin(x)=∑ni=1(x-ai)2；最小一乘法对于这一思想的表达则是D2=fmin(x)=∑ni=1|x-ai|.根据本例中的情况,在一维状态下对比两种方法.a. 从形式上看,D1表达的是一个圆域,解是唯一的；D2表达的是一个方域,解可能是不唯一的.b. 从解的性质上看,求解D1中的x,令dD1dx=2∑ni=1(x-ai)=0,则x=a1+a2+…+ann时,D1达到最小值,所求解为n个数的算术平均数；求解D2中的x,令a(1)≤a(2)≤a(3)≤…a(n)为a1,a2,a3,…,an按由小到大的排列,即a1,a2a3,…,an的顺序统计量,①当n为奇数时,x=a(n+12)②当n为偶数时,x=a(n2)或x=a(n2+1),所求解为n个数的中位数［1］.c. 从回归分析上看,最小二乘法在计算上更为简单,不需要分情况讨论,但是其受异常值的影响较大；最小一乘法缺乏显式表达,有时会出现多解的现象,但是其受异常值的影响较小［3］.本例中针对最小一乘法中多解的问题,可以通过求中间两个值的平均数得到解决［4］.由于模板中小写字母i和大写字母M之间的差距最大,M所包含的像素总和是i的4倍,所以在获得阈值中间值x后,确定的阈值范围为（x4,4x）.2数据结果分析将图1中（a）、（b）、（c）、（d）经过准备工作处理后得到四幅图的连通域个数,如表1所示.表1图1（a）、（b）、（c）、（d）中连通域个数
Table 1Number of connected domain in Fig.1 (a),(b),(c),(d)
图图1（a）图1（b）图1（c）图1（d）连通域（个）10101125图1中（a）、（b）、（c）、（d）经过准备工作处理后得到的连通域大小数据如表2、表3、表4和表5所示.表2图1（a）中连通域数据
Table 2Data of connected domain in Fig.1 (a)
172535292923222223195528表3图1（b）中连通域数据
Table 3Data of connected domain in Fig.1 (b)
772182225282811584724322925表4图1（c）中连通域数据
Table 4Data of connected domain in Fig.1 (c)
8301047516496875474987281415775919634表5图1（d）中连通域数据
Table 5Data of connected domain in Fig.1 (d)
121635270195670260276511325411375834273522212252130221817114615表2中的11个数据利用最小二乘法公式求得x=19 575.3,阈值范围δ1为［4 894,78 301］；利用最小一乘法思想求得x=23+252=24,阈值范围δ2为［10,95］.根据实际情况最佳阈值范围δ3应该是［17,35］,噪声阈值范围δ4为［195 528,195 528］.表3中的数据共有10个,利用最小二乘法公式求得x=19 327.8,阈值范围η1为［4 832,77 311］；利用最小一乘法思想求得x=28+282=28,阈值范围η2为［10,111］.根据实际情况最佳阈值范围η3为［22,32］,噪声阈值范围η4为［77 218,115 847］.表4中的数据共有11个,利用最小二乘法公式求得x=11 054.909,阈值范围φ1为［2 764,44 219］；利用最小一乘法思想求得x=830,阈值范围φ2为［208,3 319］.根据实际情况最佳阈值范围φ3为［591,1 577］,噪声阈值范围φ4为［10,64］∪［9 634,104 751］.表5中的数据共有25个,利用最小二乘法公式求得x=307.88,阈值范围ψ1为［77,1 231］；利用最小一乘法思想求得x=46,阈值范围ψ2为［12,183］.根据实际情况最佳阈值范围ψ3为［541,956］,噪声阈值范围ψ4为［11,352］∪［1 132,1 216］.通过求解表2和表3中的数据可以得出,δ3δ1,η3η1,说明利用最小二乘法没有能够获得正确的阈值范围；与此同时δ3δ2且δ4δ2,η3η2且η4η2,说明利用最小一乘法不但获取了正确的阈值区间,而且没有包含噪声的阈值空间.通过分析可以看出,当噪声不多,且需要获取信息的连通域大小彼此十分相近,相对于有着相同颜色的噪声所在的连通域大小具有明显差异时,将噪声所在连通域大小当做异常值进行处理,由于在一维状态下使用最小一乘法和最小二乘法的开销相差不大（一个进行排序,一个求平均数）,但是运用最小一乘法能够更好的减小异常值带来的影响,由此不难得出与1.4节中c吻合的结论,对于异常值过大或过小的情况运用最小一乘法应该能够得到更好的效果.通过求解表4中的数据可以得出,φ1与φ3没有交集却与φ4有交集,说明利用最小二乘法不但没有能够获得正确的阈值范围,而且选出了噪声；与此同时φ2φ3 且φ2φ4,说明利用最小一乘法不但获取了正确的阈值区间,而且没有包含噪声的阈值空间.通过分析可以看出,在与表2和表3具有相同特征的情况下,缩小目标与噪声所在连通域大小的差距,最小一乘法仍然可以比最小二乘法更精确地命中目标.通过求解表5中的数据可以得出,ψ1ψ3且ψ1与ψ4有交集,说明利用最小二乘法获得了正确的阈值范围,但也选出了噪声；与此同时ψ2ψ3 且ψ2ψ4,说明利用最小一乘法不但没有能够获得正确的阈值范围,而且选出了噪声.通过分析可以看出,相比于前三种情况,本例中噪声较多,且与目标所在连通域大小差值不明显,利用最小一乘法错误的将噪声选成了阈值中间值,最终导致了区域的选择错误.而此处利用最小二乘法则获得了更准确的结果.通过以上数据分析可以总结出,当噪声不多,且噪声所在连通域大小与目标所在连通域大小具有明显差异时,利用最小一乘法能够取得比最小二乘法更准确的结果,这是因为异常值偏离实际中心过远导致的,最小二乘法对于异常值的影响要比最小一乘法敏感,据此说明具有类似特征的图片在使用连通域去噪时,利用最小一乘法进行处理要更为合理一些.但当图像中噪声较多或大小区分不明显时,最小一乘法相比最小二乘法不具备优势［5］.3实验结果用最小二乘法对图1（a）、（b）、（c）、（d）进行处理后效果如图5（a）、（b）、（c）、（d）所示.图5最小二乘法处理效果图
Fig.5Result for dealing with least squares method用最小一乘法对图1（a）、（b）、（c）、（d）进行处理后效果如图6（a）、（b）、（c）、（d）所示.图6最小一乘法处理效果图
Fig.6Result for dealing with least absolute deviation图6（a）和图6（b）中的待获取信息放大10倍后如图7、图8所示.图7图6（a）目标结果放大图
Fig.7Amplify goal in Fig.6 (a)图8图6（b）目标结果放大图
Fig.8Amplify goal in Fig.6 (b)图5和图6的效果符合数据分析的预期结果.从对比中可以看出:对于噪声不多,且噪声所在连通域大小与目标所在连通域大小具有明显差异的图像,利用最小一乘法能够取得比最小二乘法更准确的结果；对于噪声较多或大小区分不明显的图像,最小二乘法相比最小一乘法能够获得更准确的结果.4结语通过实验证明,最小一乘法对于解决异常值影响比最小二乘法更为优秀.与传统的最小二乘法相比,最小一乘法更适合运用在目标轮廓清晰,噪声偏少且所在连通域大小与目标所在连通域大小相差很大情况下的连通域去噪中.针对本例中出现的噪声与目标连通域大小相同的情况,在识别时通过匹配度门限的设置,就可以将通过连通域大小无法判别的噪声去除；针对噪声过多的情况,还有待以后的研究进一步完善［6］.