基于迭代思想的自适应Niblack算法改进

2023-04-07丁登峰周国鹏张建权陈澜征

计算机应用与软件 2023年3期

丁登峰周国鹏* 张建权陈澜征

1(湖北科技学院自动化学院湖北咸宁 437100) 2(湖北香城智能机电研究院湖北咸宁 437100) 3(武汉纺织大学电子与电气工程学院湖北武汉 430200)

0 引言

在光学字符识别[1-4]、车牌识别和零件识别检测等工程应用中,图像的二值化是一项至为关键的预处理技术。在很多视觉工程应用中,图像特征对于最终的识别结果起到关键作用。在图像二值化过程中,能否保留原图的主要图像特征是最关键的,而图像二值化的关键是确定二值化的阈值以及阈值的确定时间。

二值化的算法有很多,大体分为两类:全局阈值算法[5-6]和局部阈值算法[7-8]。用得比较多的就是全局阈值Otsu算法和局部阈值Niblack算法[7],其中Niblack是一种实现方法较为简单,效果较为稳定,是一种动态阈值分割方法,其二值化效果比大津法(Otsu算法)好,因为大津法是根据整个图像来确定一个阈值,而Niblack则是在不同的邻域会有不同的阈值。

图像二值化的基本要求就是快速地在保留原图主要图像特征的基础上进行二值化转换。针对这两点要求,国内外很多学者对图像二值化算法做了大量研究。Natarajan等[9]提出了一种基于对数二值化技术的文本图像增强方法;Lokhande等[10]提出一种针对文本图像的改进局部二值化技术,该算法根据直方图最小值进行图像分割并结合优化后的Otsu图像去除为轮廓;杨硕等[11]提出了将全局阈值Kittler算法和局部阈值Bernsen算法相结合的二值化算法;石为人等[12]提出将改进Otsu和Niblack算法相结合,提高了处理速度,获取了较好的效果,但二值化图像还是有明显噪声;郑均辉等[13]提出一种局部静态阈值与Niblack相结合的改进算法,该算法能有效消除传统算法中噪声过多现象,但是对处理速度没有改善;李鑫等[14]提出了一种基于粒子群优化方法的Niblack设备红外图像分割算法,算法对含较大噪声密度的红外图像分割性能优于其他传统算法,但算法复杂度较高,处理时间长;李建等[15]提出一种自适应邻域窗口和修正系数的Niblack算法,该算法依据QR码图像的分辨率和灰度值,动态调整修正系数和邻域窗口,进行自适应二值化处理,但是处理速度依旧没有较大的改善;从飞等[16]提出利用数学形态学理论,采用改进的Sauvola算法对非均匀光照图像进行二值化,可以对噪声进行有效的抑制,得到较好的识别效果;孙国栋等[17]提出一种基于卷积神经网络的二值化方法,对复杂光照下含数字重影的仪表图像二值化,但训练所需要的时间较长。

然而,以上方法要么只针对文本图像优化,要么优化了处理效果但处理速度依旧缓慢,有的算法优化了处理速度但是二值化效果还有待改进。本文运用迭代思想快速改进Niblack算法中对灰度均值与标准差的计算,使得同样分辨率的图像处理速度从几十秒降低到毫秒级,同时利用Otsu全局阈值优化原算法阈值函数中的修正系数,使其能自适应地调整阈值,在文本图像和小物体分割处理中获得更好的处理效果。

1 算法简介

1.1 Otsu算法

Otsu算法[3]主要用于自动计算图像分割中的阈值t,计算简单,不受图像亮度和对比度的影响,能更好地区别图像的前景(目标)和背景区域。该算法使用聚类思想,用阈值t把图像按灰度级分成目标和背景两部分,使得两部分之间的灰度值的方差g(t)最大化。

g(t)=w0×(u-u0)2+w1×(u-u1)2

(1)

令t在图像灰度[0,L-1]上进行遍历,计算不同t值下的类间方差g(t)值,使得g(t)值最大时的t值就是Otsu法所要求的最佳阈值。然后利用式(1)计算得到的阈值t,在图像中逐点遍历比较,完成图像二值化。

L为图像灰度级,f(x,y)为图像中一点(x,y)的灰度值。w0、w1分别为目标和背景像素出现的概率,u0、u1分别为目标和背景的平均灰度值,u为总平均灰度值。

1.2 Niblack算法

Niblack算法是一种简单可靠的局部阈值二值化算法,对光照不均匀的图像处理效果明显。其基本思想是通过计算图像中每个像素点(x,y)及其邻域(r×r)内所有像素点的灰度均值m(x,y)和标准差s(x,y),得到二值化阈值T(x,y)。算法具体步骤为:

Step1以每个像素点(x,y)为中心,分别计算其r×r邻域窗口内所有像素点的灰度均值m(x,y)。其中,f(x,y)是图像中一点(x,y)的灰度值。

Step2利用式(3),计算每个像素点(x,y)及其邻域(r×r)内所有像素点的标准差s(x,y)。

Step3利用式(3)和式(4),计算每个像素点(x,y)的二值化阈值T(x,y)。

T(x,y)=m(x,y)+k×s(x,y)

(5)

式中:k为修正系数,取值范围为[-1,1],一般取-0.1～0.5。

Step4利用式(5),在图像中逐点遍历每个像素点(x,y)的灰度值f(x,y)及其对应的T(x,y)值,按式(6)进行图像二值化。

在经典Niblack算法中,阈值T(x,y)计算式为式(5)。当图像中像素点灰度值f(x,y)大于或等于T(x,y)时,则设置为白色,否则为黑色,这样就完成了图像的二值化。但是如果某一邻域内都是背景,按Niblack计算,必定有一部分被判定为目标点,从而导致伪影现象。针对此问题,2000年Sauvola提出了一种改进的Niblack算法,差异部分就是采用了不同的阈值选取方法,具体公式如式(7)所示,其中:k是修正系数,取值范围为[0,1],R为标准方差的动态范围,若当前输入图像为8位灰度图,则R=128。

改进后的算法对伪影现象有了一定的改善,同时用Niblack算法进行图像处理时,选择的邻域窗口r×r大小很关键,选择的邻域太小,则噪声抑制的效果不理想,目标不够突出,选择的邻域太大,则目标的细节就会部分丢失,同时计算复杂度高,导致处理速度过慢。

2 Niblack算法优化改进

本文主要从图像处理速度和处理效果这两方面对Niblack算法进行优化改进。在处理速度优化方面,主要是运用迭代思想降低算法复杂度,使原复杂度O(size×area)降低为O(size),从而做到与邻域窗口大小area基本无关。在处理效果优化方面,主要是利用Otsu全局阈值优化原算法阈值函数中的修正系数,使其能自适应地调整阈值,在文本图像和小物体分割处理中获得更好的处理效果。

2.1 运用迭代思想优化算法复杂度

传统Niblack算法运算速度比较慢,通常处理时间由几秒到几十秒。如果图像尺度过大,处理时间甚至超过100秒,其主要原因是由于该算法需遍历图像中每一个点的邻域窗口r×r的所有像素点的灰度均值及标准差,并且需要重复求和,计算量巨大,而且随着邻域窗口r×r的增大而急剧增加。

假定图像imag像素尺寸大小为size(H×W),邻域窗口大小为area(r×r),传统Niblack算法复杂度为O(size×area),考虑到计算图像任意一像素点灰度均值及标准差时重复求和,同时需要遍历图像的每一像素点,依次从图像矩阵的行或列逐点移动,本文运用迭代思想对计算灰度均值和标准差的方法进行了改进,使得每次计算第n个像素点的邻域窗口灰度值和Sn的时候使用前一个像素点的邻域窗口灰度值和Sn-1,避免大量重复计算,使总体算法复杂度降低为O(size),从而做到与邻域窗口大小基本无关。具体算法流程如图1所示。

图1 Niblack算法复杂度优化流程

改进算法的具体步骤为:

Step1把原图像矩阵imag四周镜像反射扩展r行/列,生成(H+2r)×(W+2r)的新图像矩阵imag1。

扩展后,原imag图起点坐标(1,1)变成新图像imag1的坐标(1+r,1+r)。对于图像imag1中的任意一像素点(i,j),其邻域窗口大小为r×r,每一行(i,j+Pre)→(i,j+Post)共r个像素点,每一列(i+Pre,j)→(i+Post,j)共r个像素点,具体像素点位置见图2所示。

图2 图像矩阵像素点位置示意图

以像素点(i,j)为中心,定义长度为r的前后位置参数,floor()指向下取整:

Step2计算起始行1+r+Pre的所有垂直方向r个像素点灰度值之和的初temp(1+r+Pre,j)。

每一列像素点(1+r+Pre+Pre,j)到(1+r+Pre+Post,j)共r个像素点灰度值之和,即是第1+r+Pre行的初值temp(1+r+Pre,j)。

Step3从下一行2+r+Pre开始到末尾行H+r+Post,基于前一行的求和结果计算所有行的垂直方向r个像素点灰度值之和temp(i,j)。

temp(i,j)=temp(i-1,j)+imag1(i+Post,j)-

imag1(i+Pre-1,j)

(9)

Step4基于上述保存的垂直方向求和结果,进行水平方向temp(i,j)值的求和。计算起始列1+r+Pre,所有行的水平方向r个temp值之和得到像素点(i,1+r+Pre)邻域窗口r×r的所有像素点的灰度值之和,即起始列的初值Sum(i,1+r+Pre)。

Step5从下一列2+r+Pre到末尾列Wid+r+Post,依次基于前一列的求和结果进行计算,求出所有列水平方向r个temp值之和得到每一个像素点邻域窗口的所有像素点的灰度值之和Sum(i,j)。

Sum(i,j)=Sum(i,j-1)+temp(i,j+Post)-

temp(i,j+Pre-1)

(10)

Step6通过式(11)得到灰度均值m(x,y),把f(i,j)-m(i,j)代入imag(i,j)重新计算得到像素点灰度标准差s(x,y)。

m(x,y)=Sum(i,j)/r2

(11)

式中:f(i,j)、imag(i,j)表示原图像矩阵第i行、第j列的灰度值,imag1(i,j)表示新图像矩阵第i行、第j列的灰度值,temp(i,j)表示新图像矩阵第i行、第j列元素垂直方向r个像素点灰度值之和,Sum(i,j)表示新图像矩阵第i行、第j列元素邻域窗口r×r的所有像素点的灰度值之和。

2.2 自适应阈值函数优化

根据Niblack算法原理,每个像素点需要利用邻域窗口r×r模板遍历图像,导致边缘区域(r-1)/2的范围内无法求取阈值;同时如果某一邻域内都是背景,按Niblack计算,必定有一部分被判定为目标点,从而导致伪影现象。针对此问题,本文在快速计算灰度值之和的时候运用padarray()函数扩展原图像,保证了边缘区域的计算问题。另外,针对伪影问题,根据Sauvola算法思路结合全局阈值Otsu算法提出新的阈值函数,实验结果证明改进算法效果明显。

Sauvola算法的阈值函数如式(7)所示,其阈值由邻域窗口的灰度均值m(x,y)、标准差s(x,y)和修正系数k决定。当k的值不断增大,小物体边缘越模糊,文字图像的字符笔迹越来越细,也越来越模糊不清,但是噪声也在慢慢地消除。实验表明,Sauvola算法对文本图像处理有比较好的效果,但是在小物体识别、分割中效果比较差。同时,对经典的文本图像、小物体分割图像做分析,发现文本、车牌图像的Otsu分割阈值较低(Thotsu<0.49),而像rice、coin小物体图像的Otsu分割阈值较高(Thotsu>0.49),本文实验所用的典型图像如图3所示,计算的对应图像的Otsu分割阈值如表1所示。其中:图3(a)来自于国际文档图像二值化竞赛(DIBCO)图集,图3(b)和图3(d)来自于车牌OCR识别练习数据集,图3(c)、图3(e)和图3(f)是数字图像处理(冈萨雷斯第三版)图集中的原始图。

(a) 文本1 (b) 车牌1

根据Niblack算法阈值式(5)以及式(4),可以把阈值函数T(x,y)表示为:

T(x,y)=m(x,y)×[1+g(t)×s(x,y)]

(12)

式中:g(t)是与m(x,y)相关的函数,g(t)×m(x,y)的值范围为[-1,1]。

经过多组文本、车牌和小物体分割图像实验,发现Otsu分割阈值Thotsu与Sauvola算法分割阈值成比例关系。当Thotsu≥0.49时,参考式(12),通过多次实验对比效果,建立阈值函数模型为:

当Thotsu<0.49时,参考Sauvola算法阈值式(7),建立阈值函数模型为:

由于式(14)中修正系数t的取值范围为[0,1],通过调整t值,多次实验对比效果,发现当t=0.9时,文本、车牌类图像二值化效果最佳。最终,针对文本、车牌及小物体分割图像设计了一种使用范围更广、处理效果优良的阈值函数,表示为:

(15)

3 实验仿真及结果分析

本文实验所使用的环境为Win7 64 bit中文旗舰系统,CPU:AMD Ryzen 5 1600 3.2 GHz,内存:DDR3 16 GB,在MATLAB R2017a应用上对图1的6幅图像进行实验,分别用Otsu、Kittler、Niblack、Sauvola、Otsu+Niblack[12]以及本文算法做对比分析,结果如图2-图7所示。其中,Niblack算法的修正系数为k=-0.2,邻域窗口大小为80×80;Otsu+Niblack算法参数主要参考文献[12];本文算法邻域窗口大小也为80×80。

表2是用原Niblack与本文算法在不同分辨率图像上进行多次实验之后计算的平均时间列表。可以看出,在同样的邻域窗口大小时,本文算法运行速度比原来Niblack算法快几十倍到几百倍,并且这两者之间的倍数随着图像分辨率的增大而急剧增大,说明新算法运算速度受图像分辨率大小的影响相对较小。随着邻域窗口大小r的增大,Niblack算法增加的耗时与r增大的大小成等比例关系,而本文算法则受邻域窗口大小的影响比较小。因此,本文算法运行速度比原Niblack算法提高了上百倍,并且算法稳定,受图像分辨率及邻域窗口大小影响小。对比贾坤昊等[18]采用积分思想对Niblack算法速度的改进,本文算法更优。

表2 算法运算平均时间对比单位:s

使用不同的算法分别对图3中的图像进行二值化处理,得到6组不同效果的二值化图像。从图4可以看出Niblack算法及其改进的Sauvola算法效果明显比全局阈值Otsu、Kittler和Niblack+Otsu算法好,但是Niblack算法处理后其四周有大量伪影,而Sauvola算法和本文算法能获得更准确、完整的目标信息,无明显伪影及噪点。