基于改進粒子群算法的二維閾值圖像分割

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

關鍵詞：圖像分割； 二維Otsu方法； 粒子群算法；量子粒子群算法

中圖分類號：TP391.41 文獻標志碼：A 文章編號：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

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

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

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

1.1 粒子群算法(PSO)

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

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

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

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

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

PSO算法概念簡單、容易實現、搜索速度快、范圍大，與其他優化算法相比，它的優點突出。

1.2 改進粒子群算法—量子粒子群算法（QPSO）

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

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

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之間的隨機點；和μ都是[0，1]的隨機數；β為QPSO的收縮擴張系數。

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

a)初始化粒子群;

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

c)求每一個粒子的適應度值，比較求出Pid;

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

e)更新Pgd;

f)對于粒子的每一維，根據式(4)，在Pid與Pgd之間取得一個隨機點；

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

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

1.3 量子粒子群算法的優點

量子粒子群算法能克服一般粒子群算法在收斂性能上的缺陷，因為它具有很多特性:a)量子系統是一個復雜的非線性系統，符合狀態重疊原理，因此量子系統比一個線性系統具有更多的狀態。b)量子系統中一個粒子能以某一確定的概率出現在搜索空間中的任一位置，因為粒子沒有一個確定的軌跡。c)傳統PSO算法中，有限的搜索范圍降粒子限制在一個固定的區域。在QPSO算法中，粒子以某一確定的概率出現在整個可行的搜索空間中任一位置，甚至是遠離中間點的位置。這樣的位置也可能比當前群體中的gbest具有更好的適應值。

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

2.1 二維Otsu圖像分割

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

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

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

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

使用離散矩陣的跡作為背景和目標類間的距離測度函數，即

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

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

2.2 基于改進粒子群算法的Otsu圖像分割

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

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

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

a) 隨機生成popsize個粒子，粒子的位置在(0，255)產生，設置最大迭代次數MAXITER。

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

c) 根據式(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 實驗結果和分析

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

由圖3和4效果可見，二維分割要比一維分割的效果好，后者有很多的錯分點，而前者的錯分點較少。這主要是因為二維的Otsu法考慮了圖像像素的灰度信息與像素間的位置關系。對于二維的Otsu法，采用窮舉法、PSO算法和QPSO算法所得到的最優閾值向量、計算時間、最大目標函數和達優數如表1所示。

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

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

4 結束語

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

參考文獻：

[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].北京：科學出版社，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.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文