基于改進(jìn)粒子群算法的二維閾值圖像分割

摘 要：二維Otsu方法同時(shí)考慮了圖像的灰度信息和像素間的空間鄰域信息，是一種有效的圖像分割方法。針對(duì)二維Otsu方法計(jì)算量大的特點(diǎn)，采用量子粒子群算法來搜索最優(yōu)二維閾值向量， 每個(gè)粒子代表一個(gè)可行的二維閾值向量，通過各個(gè)粒子的飛行來獲得最優(yōu)閾值。結(jié)果表明，所提出的方法不僅能得到理想的分割結(jié)果，而且計(jì)算量大大減少，達(dá)到了快速分割的目的，便于二維Otsu方法的實(shí)時(shí)應(yīng)用。

關(guān)鍵詞：圖像分割； 二維Otsu方法； 粒子群算法；量子粒子群算法

中圖分類號(hào)：TP391.41 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001-3695(2008)08-2402-03

Two dimension threshold image segmentation

based on improved particle swarm algorithm

FENG Bin， WANG Zhang， SUN Jun

(School of Information Technology， Southern Yangtze University， Wuxi Jiangsu 214122， China )

Abstract:2D Otsu method ， which considers the gray information and spatial neighbor information between pixels in the image simultaneously ， is an efficient image segmentation method. However ， the computational burden of finding optimal threshold vector is very large for 2D Otsu method. Used a optimization method， such as quantum-behaved particle swarm optimization(QPSO) ， to find the best 2D threshold vector ， in which each particle represented a possible 2D threshold vector and the best 2D threshold was obtained through the flying among particles. Experimental results show that the proposed method can not only obtain ideal segmentation results but also decrease the computation cost reasonably ， and it is suitable for real-time application.

Key words：image segmentation;2D Otsu;particle swarm algorithm;quantum-behaved particle swarm algorithm

圖像分割是圖像處理和計(jì)算機(jī)視覺中基本且關(guān)鍵的技術(shù)之一，其目的是將目標(biāo)與背景分離，為后續(xù)的分類、識(shí)別和檢索提供依據(jù)。圖像分割方法包括閾值法、邊緣檢測法和區(qū)域跟蹤法等。其中，閾值分割是一種實(shí)現(xiàn)最為簡單、使用最為普遍的分割方法。閾值選取方法有多種如直方圖雙蜂法、最大熵法、Otsu法、矩量保持法、梯度統(tǒng)計(jì)法以及這些方法在二維上的推廣等。在這些方法中，Otsu法以其分割效果好、適用范圍廣而得到了廣泛應(yīng)用，但是與其他分割方法一樣，它同樣存在著計(jì)算量大、計(jì)算時(shí)間長的問題。

粒子群優(yōu)化(particle swarm optimization，PSO)算法是基于群體智能(swarm intelligence)理論的優(yōu)化算法，它通過群體中粒子間的合作與競爭產(chǎn)生的群體智能指導(dǎo)優(yōu)化搜索。2004年Sun等人^[1]在研究了Clerc等人關(guān)于粒子收斂行為的研究成果后，從量子力學(xué)的角度提出了一種新的PSO算法模型。認(rèn)為粒子具有量子行為，并根據(jù)這種模型提出了量子粒子群算法quantum-behaved particle swarm optimization，QPSO），并且得到了很好的實(shí)驗(yàn)效果。

1 粒子群算法和量子粒子群算法

1.1 粒子群算法(PSO)

由Kennedy和Eberhart提出的PSO算法，起源于對(duì)簡單社會(huì)的模擬，最初設(shè)想是模擬鳥群覓食的過程，后來發(fā)現(xiàn)PSO是一種很好的優(yōu)化工具。PSO優(yōu)化算法與其他進(jìn)化算法相類似，也是將尋優(yōu)的參數(shù)組合成群體，通過對(duì)環(huán)境的適應(yīng)度將群體中的個(gè)體向好的區(qū)域移動(dòng)。與其他進(jìn)化算法不同，在描述個(gè)體時(shí)，將其看做是D維尋優(yōu)搜索空間的一個(gè)沒有體積的微粒(點(diǎn))，結(jié)合微粒的歷史最佳位置和群體歷史最佳位置信息，以一定的速度向目標(biāo)值逼近。許多科學(xué)和工程問題均可歸結(jié)為最優(yōu)化問題，每個(gè)優(yōu)化問題的潛在解都是搜索空間中的一個(gè)粒子。第i個(gè)微粒可以表示成D維向量X=[Xi1，Xi2，…，XiD]，微粒的速度表示成Vi=[Vi1，Vi2，…，ViD]這個(gè)微粒經(jīng)歷的最佳位置(對(duì)應(yīng)于最好的適應(yīng)度)表示為Pi=[Pi1，Pi2，…，PiD]也稱為pbest。群體所有微粒經(jīng)歷的最好位置的索引號(hào)用g表示，記為Pg，也稱為gbest，第i個(gè)微粒從n代進(jìn)化到n+1代，通過下式進(jìn)行更新。

v[] =v[]+c1×rand()×(pbest[]-present[])+

c2×rand()×(gbest[]- present[])(1)

present[]=present[]+v[](2)

其中：v[] 是粒子的速度；present[] 是當(dāng)前粒子的位置； pbest[]和 gbest[]如前定義；rand()是（0， 1）的隨機(jī)數(shù)；c1、c2是學(xué)習(xí)因子，通常c1=c2=2。

PSO算法概念簡單、容易實(shí)現(xiàn)、搜索速度快、范圍大，與其他優(yōu)化算法相比，它的優(yōu)點(diǎn)突出。

1.2 改進(jìn)粒子群算法—量子粒子群算法（QPSO）

有很多實(shí)驗(yàn)已經(jīng)證明PSO算法不能收斂于全局最優(yōu)解，甚至于局部最優(yōu)解，許多學(xué)者已采用很多方法來改進(jìn)粒子群優(yōu)化算法的性能。2004年Sun等人在研究了Clerc^[2]關(guān)于粒子收斂行為的研究成果后，從量子力學(xué)的角度提出了一種新的PSO算法模型^[1，3]。認(rèn)為粒子具有量子行為，并根據(jù)這種模型提出了量子粒子群算法(QPSO)。在量子空間中粒子的滿足聚集態(tài)的性質(zhì)完全不同，它可以在整個(gè)可行解空間中進(jìn)行搜索，因此QPSO算法的全局搜索的性能遠(yuǎn)遠(yuǎn)優(yōu)于標(biāo)準(zhǔn)PSO算法。在量子空間中，粒子的速度和位置是不能同時(shí)確定的。通過波函數(shù)來描述粒子的狀態(tài)，并通過求解薛定諤方程得到粒子在空間某一點(diǎn)出現(xiàn)的概率密度函數(shù)，又通過蒙特卡羅隨機(jī)模擬方式得到粒子的位置方程^[4，5]。

在具有量子行為的粒子群優(yōu)化算法中，粒子的主要迭代公式為

mbest=1/m∑Mi=1Pi=(1/M∑Mi=1Pi1，1/M ∑Mi=1Pi2，…，1/M∑Mi=1Pid)(3)

Pid=×Pid+(1-)×Pgd=rand(4)

xid=Pid±β×|mbest-xid|×ln(1/u)μ=rand(5)

其中：mbest是粒子群pbest的中間位置；Pid為Pid和Pgd之間的隨機(jī)點(diǎn)；和μ都是[0，1]的隨機(jī)數(shù)；β為QPSO的收縮擴(kuò)張系數(shù)。

QPSO的算法流程可以描述如下：

a)初始化粒子群;

b)根據(jù)式(3)計(jì)算mbest的值;

c)求每一個(gè)粒子的適應(yīng)度值，比較求出Pid;

d)對(duì)于每一個(gè)粒子比較Pid，求得Pgd;

e)更新Pgd;

f)對(duì)于粒子的每一維，根據(jù)式(4)，在Pid與Pgd之間取得一個(gè)隨機(jī)點(diǎn)；

g)根據(jù)式(5)獲得一個(gè)新的位置;

h)重復(fù)b)~g)直到條件不滿足，則迭代過程結(jié)束。

1.3 量子粒子群算法的優(yōu)點(diǎn)

量子粒子群算法能克服一般粒子群算法在收斂性能上的缺陷，因?yàn)樗哂泻芏嗵匦?a)量子系統(tǒng)是一個(gè)復(fù)雜的非線性系統(tǒng)，符合狀態(tài)重疊原理，因此量子系統(tǒng)比一個(gè)線性系統(tǒng)具有更多的狀態(tài)。b)量子系統(tǒng)中一個(gè)粒子能以某一確定的概率出現(xiàn)在搜索空間中的任一位置，因?yàn)榱Ｗ記]有一個(gè)確定的軌跡。c)傳統(tǒng)PSO算法中，有限的搜索范圍降粒子限制在一個(gè)固定的區(qū)域。在QPSO算法中，粒子以某一確定的概率出現(xiàn)在整個(gè)可行的搜索空間中任一位置，甚至是遠(yuǎn)離中間點(diǎn)的位置。這樣的位置也可能比當(dāng)前群體中的gbest具有更好的適應(yīng)值。

2 基于量子粒子群算法的Otsu圖像分割

2.1 二維Otsu圖像分割

Otsu法是由日本的大津等人^[6]首先提出的，也稱大津閾值法或最大類間方差法。該方法以圖像的一維直方圖為依據(jù)，以目標(biāo)和背景的類間方差最大為閾值選取準(zhǔn)則，在很多情況下均能取得很好的閾值。在實(shí)際應(yīng)用中，由于用一維直方圖來確定閾值往往會(huì)造成錯(cuò)誤分割，常利用原始圖像與其鄰域平滑圖像聯(lián)合直方圖，將一維Otsu法推廣到二維而得到二維Otsu閾值分割方法，使分割效果得到改善。但二維直方圖的引入，大大增加了計(jì)算復(fù)雜性，在很大程度上限制了該算法的應(yīng)用范圍。

設(shè)一幅圖像f(x，y )的灰度級(jí)為 (0，1，… ，L-1)，其鄰域平滑圖像g(x，y )(以3×3鄰域均值作為該像素灰度值)的灰度級(jí)也為L，對(duì)于圖像中的任何一個(gè)像素，就有了一個(gè)二元組，即像素灰度值i和鄰域平均灰度值。設(shè)像素灰度值為i，且鄰域平均灰度值的像素點(diǎn)數(shù)為j，圖像總像素為M，則二維聯(lián)合概率的密度為

pij=fij/M且∑L-1i=1∑L-1j=1pij=1， ∑L-1i=1∑L-1j=1fij=M(6)

任意給定一個(gè)閾值(s，t)，就可以將圖像分割為圖1所示的四個(gè)區(qū)域：A、B、C、D。其中，對(duì)角線上的兩個(gè)區(qū)域B和C分別對(duì)應(yīng)于目標(biāo)與背景。而遠(yuǎn)離對(duì)角線的區(qū)域A和D則對(duì)應(yīng)于邊緣和噪聲。

使用離散矩陣的跡作為背景和目標(biāo)類間的距離測度函數(shù)，即

rtrace(Sb)=w0[(μ0i-μi)2+(μ0j-μj)2]+

w1[(μ1i-μi)2+(μ1j-μj)2](12)

2.2 基于改進(jìn)粒子群算法的Otsu圖像分割

適應(yīng)度值即是計(jì)算適應(yīng)度函數(shù)所得到的值，它的大小是粒子群算法中選擇個(gè)體極值和全體極值的依據(jù)。適應(yīng)度函數(shù)是根據(jù)具體問題而設(shè)計(jì)的，通常在目標(biāo)函數(shù)并不復(fù)雜的情況下，可以直接將目標(biāo)函數(shù)選擇為適應(yīng)度函數(shù)。本文以距離測度函數(shù)為rtrace(Sb)適應(yīng)度函數(shù)^[7]，求其最大值，即

f(s，t)=max rtrace(Sb)(13)

圖像灰度值為[0，255]的正整數(shù)，而根據(jù)QPSO更新公式得到的位置均為連續(xù)值，所以在每次速度更新后都要對(duì)其進(jìn)行取整操作，同時(shí)檢查位置是否越界(>255或<0)。由于量子粒子群算法與粒子群算法相比較，具有較強(qiáng)的魯棒性，控制的參數(shù)也較少。本文算法將惟一的參數(shù)beta定義為[0，1]的隨機(jī)數(shù)。具體的流程步驟如下：

a) 隨機(jī)生成popsize個(gè)粒子，粒子的位置在(0，255)產(chǎn)生，設(shè)置最大迭代次數(shù)MAXITER。

b) 根據(jù)式(13)來計(jì)算粒子的適應(yīng)度。更新每個(gè)粒子的個(gè)體極值pbest(i)(i=1，2，3，…，popsize)和整個(gè)粒子群的全局的極值gbest(i)(i=1，2，3，…，popsize) 。

c) 根據(jù)式(5)來更新粒子的位置。

d)令t＝t+1，返回b)，直到t＝MAXITER。

e)輸出粒子群的位置，即輸出最佳的閾值的向量(s，t)，分割后的圖像fs，t(x，y)為

if f(x，y) < s and f(x，y) < tthen fs，t(x，y) = 1

if f(x，y) > s or f(x，y) > tthen fs，t(x，y) =0

3 實(shí)驗(yàn)結(jié)果和分析

為了驗(yàn)證本文算法的有效性，采用本文方法對(duì)Lena圖進(jìn)行圖像分割實(shí)驗(yàn)。所有的實(shí)驗(yàn)都在Petium 3.0 GHz 的PC上利用MATLAB 7.0進(jìn)行實(shí)驗(yàn)。為了使所作的實(shí)驗(yàn)更加具有對(duì)比性，Lena圖的大小為(256×256)。對(duì)Lena圖分別采用窮舉法，PSO算法和QPSO算法進(jìn)行分割。為了客觀地比較算法的性能，對(duì)每一幅圖像運(yùn)行10次的PSO算法和QPSO算法。得到的分割后的圖像如圖3、4所示。

由圖3和4效果可見，二維分割要比一維分割的效果好，后者有很多的錯(cuò)分點(diǎn)，而前者的錯(cuò)分點(diǎn)較少。這主要是因?yàn)槎S的Otsu法考慮了圖像像素的灰度信息與像素間的位置關(guān)系。對(duì)于二維的Otsu法，采用窮舉法、PSO算法和QPSO算法所得到的最優(yōu)閾值向量、計(jì)算時(shí)間、最大目標(biāo)函數(shù)和達(dá)優(yōu)數(shù)如表1所示。

表1 三種算法性能比較方法最佳閾值向量最優(yōu)目標(biāo)值運(yùn)行時(shí)間/s達(dá)優(yōu)數(shù)窮舉法（70，127）4 069.51 806.542 -PSO（70，127）4 069.543.140 66QPSO（70，127）4 069.540.781 310實(shí)驗(yàn)共運(yùn)行10次，表中的達(dá)優(yōu)數(shù)是指運(yùn)行結(jié)果和窮舉法結(jié)果相同的次數(shù)。從表1可以看出，在相同條件下，QPSO和基本PSO計(jì)算時(shí)間差別不大，但兩者均不到窮舉法的5% ，說明了粒子群的Otsu法在計(jì)算速度方面的優(yōu)勢，顯然這種優(yōu)勢還會(huì)隨著閾值維數(shù)的增多而加大。同時(shí)QPSO的達(dá)優(yōu)率為100%，而基本PSO只有60%，這是由于QPSO算法的量子性質(zhì)確保算法收斂，同時(shí)提高算法的精度，改善了PSO陷入局部最優(yōu)，保證了計(jì)算結(jié)果的精確和穩(wěn)定。與此同時(shí)，運(yùn)行10次的PSO算法和QPSO算法的平均收斂曲線進(jìn)行比較如圖5所示。

如圖5所示，兩種粒子群算法只需要迭代十幾次就能達(dá)到最佳的收斂值，搜索到全局的最優(yōu)閾值向量和全局最優(yōu)值。QPSO與PSO相比較而言，具有更快的迭代次數(shù)，因此QPSO的計(jì)算時(shí)間也要優(yōu)于PSO運(yùn)行的時(shí)間。

4 結(jié)束語

二維Otsu方法是一種有效的圖像分割方法，它不僅考慮了圖像的灰度信息而且考慮了像素間的空間鄰域信息。在圖像的信噪比較低時(shí)，該方法能夠得到比一維Otsu方法更好的分割結(jié)果。由于該方法需要根據(jù)二維類間方差最大的準(zhǔn)則來計(jì)算二維最優(yōu)閾值向量，與一維Otsu方法相比，其計(jì)算量大大增加。為此，本文提出采用QPSO算法來計(jì)算最優(yōu)二維閾值向量。結(jié)果表明， QPSO算法不僅能有效地搜索到全局最優(yōu)二維閾值向量而且計(jì)算量大大減少，也要優(yōu)于PSO算法，為二維Otsu方法的實(shí)時(shí)應(yīng)用提供了一個(gè)新的途徑。

參考文獻(xiàn)：

[1]SUN J， FENG B， XU W B. Particle swarm optimization with particles having quantum-behavior[C]//Proc of Congress on Evolutionary Computation.2004:325-331.

[2]CLERC M. The swarm and queen: towards a deterministic and adaptive particle swarm optimization[C]//Proc of CEC.1999:1951-1957.

[3]SUN J， XU W B. A global search strategy of quantum-behaved particle swarm optimization[C]//Proc of IEEE Conference on Cybernetics and Intelligent Systems.2004:111-116.

[4]曾建潮，介婧，崔志華.微粒群算法[M].北京：科學(xué)出版社，2004.104-105.

[5]YIN P Y. A discrete particle swarm algorithm for optimal polgonal approximation of digital curves [J ] . J of Visual Communication and Image Representation ，2004，15 (2):241-260.

[6]JIANG C W，BOMPARD W.A hybrid method of chaotic particle swarm optimization and linear interior forreactive power optimization [J].Mathematics and Computers in Simulation，2005， 68 (1):57-65.

[7]SALMAN A， AHMAD I， MADANI S A. Particle swarm optimization for task assignment problem [J] .Microprocessors and Microsystems， 2002， 26 (8):363-371.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文