基于遺傳算法的二維最大類間方差法的優(yōu)化

， ，

(南京理工大學(xué)機(jī)械工程學(xué)院，江蘇 南京 210094)

0 引言

在計(jì)算機(jī)視覺理論中，圖像分割、特征提取和目標(biāo)識(shí)別是由低層到高層的3大主要任務(wù)，特征提取和目標(biāo)識(shí)別都是以圖像分割為基礎(chǔ)。目前的圖像分割方法主要有基于閾值的分割方法、基于邊緣的分割方法、基于區(qū)域的分割方法和基于特定理論的分割方法等。閾值分割法因?qū)D像的質(zhì)量要求較低，而且運(yùn)算過程相對(duì)簡(jiǎn)單，效果較好，所以在圖像分割中應(yīng)用最為廣泛。常用的閾值分割法中，最大類間方差法因計(jì)算簡(jiǎn)單、運(yùn)算效率高、速度快且得到的閾值較為準(zhǔn)確，得到了廣泛應(yīng)用[1]。

但最大類間差法的缺點(diǎn)也顯而易見，對(duì)于目標(biāo)和背景相差不大的圖像，灰度直方圖呈現(xiàn)雙峰或多峰的情況，使用此方法很容易導(dǎo)致圖像的信息丟失，處理時(shí)也只是考慮到了圖像的灰度信息而沒有考慮其空間信息，因此分割后圖像上目標(biāo)的輪廓在細(xì)節(jié)上會(huì)比較模糊。所以對(duì)分割后圖像質(zhì)量要求較高的情況，一維最大類間方差法顯然是不能滿足要求的[2]。針對(duì)一維閾值法的不足，二維最大類間差法引入了鄰域平均灰度信息和像素信息一起構(gòu)成二維直方圖，通過二維直方圖求解最佳閾值，其準(zhǔn)確性和魯棒性得到了很大提升，但與此同時(shí)，計(jì)算量也成指數(shù)形式增長，實(shí)時(shí)性大打折扣[3]。在此，針對(duì)二維最大類間差法存在的問題，將最佳閾值的判別式由二維降到一維，減少計(jì)算量，同時(shí)通過遺傳算法加快尋優(yōu)過程，減少了原有窮舉法所帶來的計(jì)算量過大的問題。

1 二維最大類間方差法

設(shè)大小為M×N的圖像在像素點(diǎn)(x,y)處像素為f(x,y)，灰度級(jí)為L，以(x,y)為中心點(diǎn)的k×k(k取奇數(shù))的鄰域的平均灰度值g(x,y)為該點(diǎn)的平均灰度值，其灰度級(jí)也為L。f(x,y)和g(x,y)共同組成了一幅圖像的二維直方圖。圖1為一幅測(cè)試圖像的二維直方圖(Z軸為像素點(diǎn)個(gè)數(shù))。由圖1可以看出，大部分的點(diǎn)灰度值與其鄰域灰度值相差不大，集中在對(duì)角線上，遠(yuǎn)離對(duì)角線的點(diǎn)可能是灰度變化較大的邊界點(diǎn)和噪聲點(diǎn)。圖2為二維直方圖的平面投影圖，假設(shè)(s,t)為最佳閾值將投影圖分割成4個(gè)部分，其中沿對(duì)角線方向上A區(qū)域和B區(qū)域內(nèi)元素相近，可分別看作是目標(biāo)和背景，遠(yuǎn)離對(duì)角線方向的C區(qū)域和D區(qū)域可看作是邊界點(diǎn)和噪聲點(diǎn)。

圖1 測(cè)試圖像的二維直方圖

圖2 二維灰度直方圖的投影

記Cij為灰度值為i,鄰域平均灰度值為j的像素點(diǎn)在整幅圖像出現(xiàn)的頻數(shù)，其相應(yīng)的概率密度為Pij，則Pij的計(jì)算公式為：

(1)

根據(jù)閾值分割的思想，把圖像中的像素點(diǎn)分為目標(biāo)和背景兩類(對(duì)應(yīng)投影圖中的A區(qū)域和B區(qū)域)，PA和PB是像素點(diǎn)出現(xiàn)在這兩類區(qū)域的概率，則有：

(2)

(3)

A區(qū)和B區(qū)對(duì)應(yīng)的均值矢量為：

μA=(μAi,μAj)τ=

(4)

μB=(μBi,μBj)τ=

(5)

二維灰度直方圖的總均值矢量為：

μ=(μt,μj)τ=

(6)

實(shí)際情況下，邊界點(diǎn)和噪聲點(diǎn)所占的比例很小[3]，大多數(shù)情況，目標(biāo)和背景所占的比例的統(tǒng)計(jì)值為0.95～0.98。所以有PA+PB≈1，且有μ≈PAμA+PBμB，在忽略邊界點(diǎn)和噪聲點(diǎn)的情況下等式成立。定義目標(biāo)類和背景類的離散測(cè)度矩陣為σ，有

σ=PA(μA-μ)(μA-μ)τ+

PB(μB-μ)(μB-μ)τ

(7)

計(jì)算離散度矩陣的跡作為目標(biāo)類和背景類的離散度的測(cè)度

tr(σ) =[PA(μA-μ)(μA-μ)τ+

PB(μB-μ)(μB-μ)τ]=

PA(s,t)(μAi-μi)2+(μAj-μj)2〗+

PB(s,t)(μBi-μi)2+(μBj-μj)2〗

(8)

使tr(σ)取得最大值時(shí)的閾值(s*,t*)即為隨求的最大閾值，即

(9)

二維最大類間方差法引入像素的鄰域灰度信息，通過二維直方圖求得最佳閾值，和一維閾值法相比，其抗噪性和準(zhǔn)確性顯著提高，與此同時(shí)，算法的復(fù)雜度也成倍上升。其運(yùn)算過程需要遍歷整個(gè)圖像存在的灰度值，離散度矩陣的計(jì)算需要雙重循環(huán)，循環(huán)體需要在A區(qū)和B區(qū)做累加運(yùn)算，次數(shù)為s×t+(L-s)×(L-t)，所以其運(yùn)算復(fù)雜度為O(L4)。為了提高效率，可以從兩方面入手：一方面可以簡(jiǎn)化其離散度矩陣，減少運(yùn)算復(fù)雜度；另一方面可以加快尋優(yōu)過程，減少計(jì)算量。

2 改進(jìn)的二維最大類間差法

為了解決算法的計(jì)算復(fù)雜度問題，本文采用基于二維離散隨機(jī)變量的邊緣概率分布的改進(jìn)算法[4]，對(duì)概率密度Pij求其邊緣概率Wi和Wj。

(10)

(11)

Wi為像素灰度值i的一維直方圖分布，Wj為鄰域灰度值j的一維直方圖分布。由一維最大類間方差法的定義可以推導(dǎo)出Wi和Wj的類間方差。

(12)

(13)

因?yàn)檫吔琰c(diǎn)和噪聲點(diǎn)所占的比例很小，所以假設(shè)C區(qū)和D區(qū)的概率為零，即有

(14)

將式(14)代入式(2)，可推出

(15)

(16)

所以有:

PA=PAi=PAj

(17)

同理，將式(14)代入式(3)，可得:

PB=PBi=PBj

(18)

將式(17)和式(18)代入式(8)，有

tr(σ)=PA(s,t)(μAi-μi)2+(μAj-μj)2〗+

PB(s,t)(μBi-μi)2+(μBj-μj)2〗=

PAi(μAi-μi)2+PBi(μBi-μi)2+

PAj(μAj-μj)2+PBj(μBj-μj)2=

(19)

由式(19)可知，在忽略邊界點(diǎn)和噪聲點(diǎn)的情況下，二維最大類間方差法求最佳閾值的求解問題可以拆分成求解2個(gè)一維閾值之和的形式，復(fù)雜度大大降低，增強(qiáng)了時(shí)效性。

3 自適應(yīng)遺傳算法

在遺傳算法中，交叉概率和變異概率的選取是影響遺傳算法收斂速度和尋優(yōu)結(jié)果的重要因素[5]。Srinvivas等提出的自適應(yīng)遺傳算法中，每一代的交叉和變異概率都會(huì)隨著其適應(yīng)度在每代中的大小而自動(dòng)調(diào)整，使得在保持種群多樣性的同時(shí)也保證了遺傳算法的收斂性。自適應(yīng)遺傳算法的交叉概率Pc和變異概率Pm如下：

(20)

(21)

fmax為每一代種群中的最大適應(yīng)度值；favg為每一代的平均適應(yīng)度值；f為變異前的個(gè)體適應(yīng)度值；f′為交叉的2個(gè)個(gè)體中適應(yīng)度值較大的個(gè)體適應(yīng)度值；k1,k2,k3,k4為(0,1)之間的調(diào)整系數(shù)。

從式(20)和式(21)可以看出，當(dāng)個(gè)體適應(yīng)度值越接近最大適應(yīng)度值時(shí)，交叉和變異的概率越小，當(dāng)與最大適應(yīng)度值一致時(shí)其交叉和變異的概率為零。這在群體處于后期的時(shí)候是可以的，但在進(jìn)化初期，容易導(dǎo)致適應(yīng)度高的個(gè)體幾乎處于不變的情況，而使得進(jìn)化過程陷入局部最優(yōu)解，顯然這是需要避免的[6]。所以在自適應(yīng)遺傳算法的基礎(chǔ)上，需要對(duì)交叉和變異的概率做進(jìn)一步調(diào)整，在保證遺傳多樣性的基礎(chǔ)上，避免進(jìn)化趨于局部最優(yōu)解。調(diào)整后的交叉概率Pc和變異概率Pm如下：

(22)

(23)

Pc0是最大交叉概率；Pm0是最大變異概率。如式(22)和式(23)所示，一方面交叉和變異概率隨種群的適應(yīng)度實(shí)現(xiàn)自動(dòng)調(diào)整，更好地保留適應(yīng)度高的個(gè)體，另一方面交叉和變異的概率不會(huì)為零，避免了陷入局部最優(yōu)解的問題。

遺傳算法的流程如圖3所示。其主要步驟歸納如下：

圖3 遺傳算法流程

a.編碼。因?yàn)榛叶戎档梅秶?～255共256(28)個(gè)灰度級(jí)，通常采用二進(jìn)制編碼的方式，又有(s,t)2個(gè)變量閾值，所以編碼為16位，其中前8位表示像素點(diǎn)的閾值s，后8位表示鄰域閾值t。

b.隨機(jī)產(chǎn)生初始種群。初始種群的規(guī)模將影響算法的精度和效率。種群規(guī)模太小則搜索空間有限，種群規(guī)模太大將增加計(jì)算時(shí)間。本文的種群規(guī)模為20。

c.選擇適應(yīng)度函數(shù)。選擇式(19)作為適應(yīng)度函數(shù)計(jì)算適應(yīng)度值。

d.選擇、交叉和變異。采用輪盤賭作為選擇方法。對(duì)前8位和后8位采用雙點(diǎn)交叉，交叉和變異的概率如式(22)和式(23)所示，取Pc0=0.9，Pm0=0.1。

e.終止準(zhǔn)則。當(dāng)算法執(zhí)行到最大代數(shù)或經(jīng)過20代進(jìn)化后，群體中最高適應(yīng)度值仍未發(fā)生變化，則該個(gè)體即為所求閾值編碼。本文實(shí)驗(yàn)確定最大遺傳代數(shù)為100代較為合適。

4 實(shí)驗(yàn)驗(yàn)證

為了驗(yàn)證算法的正確性，分別采用經(jīng)典Otsu法、遺傳算法和本文算法對(duì)圖片進(jìn)行分割。實(shí)驗(yàn)的圖片樣本為PCB板，分割結(jié)果如圖4所示。

圖4 各類方法圖形處理后的對(duì)比

3種算法的閾值以及運(yùn)行時(shí)間結(jié)果如表1所示。對(duì)分割結(jié)果進(jìn)行分析可以發(fā)現(xiàn)經(jīng)典二維Otsu法和本文算法的分割效果較好，且差距不大，遺傳算法的分割效果相對(duì)較差，處理結(jié)果可以看出丟失了一些目標(biāo)信息。由表1可知，和經(jīng)典二維Otsu算法相比，本文算法在處理速度上大大提高，比經(jīng)典算法的運(yùn)算時(shí)間節(jié)約50%左右，且穩(wěn)定性相比經(jīng)典算法也有所提升。遺傳算法的穩(wěn)定性和經(jīng)典算法相差不大，但閾值的精確性有所下降，運(yùn)行速度提升的也很有限。綜上所述，本文算法在運(yùn)算速度上較之經(jīng)典算法有很大提高，穩(wěn)定性也有所提升。

表1 不同方法的圖像閾值及運(yùn)行時(shí)間

5 結(jié)束語

針對(duì)經(jīng)典二維最大類間方差法存在的復(fù)雜度高，運(yùn)行時(shí)間長的問題，首先通過近似將原有的二階離散度矩陣拆分成2個(gè)一階的類間差之和，減少了運(yùn)算難度，同時(shí)引入遺傳算法，將原有的窮舉法搜尋最優(yōu)解改為由遺傳算法進(jìn)行尋優(yōu)，加快尋優(yōu)過程，進(jìn)一步提高運(yùn)算效率。實(shí)驗(yàn)證明，本文算法較之經(jīng)典算法，效率上有較大提升，運(yùn)算時(shí)間減少約50%，同時(shí)，在保證精確度的同時(shí)，穩(wěn)定性也有所提升，使最終結(jié)果穩(wěn)定在2個(gè)像素，大大改善了經(jīng)典算法的實(shí)時(shí)性，提升了穩(wěn)定性，具有推廣價(jià)值。

參考文獻(xiàn)：

[1] 胡藝,楊帆,潘國峰. 一種改進(jìn)的印刷電路板缺陷檢測(cè)分割算法[J]. 科學(xué)技術(shù)與工程,2017,17(9):221-228.

[2] 王福斌,李迎燕,劉杰,等. 基于OpenCV的機(jī)器視覺圖像處理技術(shù)實(shí)現(xiàn)[J]. 機(jī)械與電子,2010,28(6):54-57.

[3] 吳一全,樊軍,吳詩婳. 改進(jìn)的二維Otsu法閾值分割快速迭代算法[J]. 電子測(cè)量與儀器學(xué)報(bào),2011,25(3):218-225.

[4] 劉金,金煒東.噪聲圖像的快速二維Otsu閾值分割[J].計(jì)算機(jī)應(yīng)用研究,2013,30(10):3169-3171,3200.

[5] 李賢陽,黃嬋. 一種結(jié)合改進(jìn)Otsu法和改進(jìn)遺傳算法的圖像分割方法[J]. 實(shí)驗(yàn)室研究與探索,2012,31(12):57-61,112.

[6] 吳昊,汪榮貴,方帥,等. 基于最小類內(nèi)差和最大類間差的圖像分割算法研究[J]. 工程圖學(xué)學(xué)報(bào),2011,32(1):67-75.