基于迭代思想的自適應Niblack算法改進

2023-04-07 03:16:30丁登峰周國鵬張建權陳瀾征

計算機應用與軟件 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算法和本文算法能獲得更準確、完整的目標信息,無明顯偽影及噪點。