張可為，陳意軍，陳愛萍，陳軍根

（湖南工程學院 電氣信息學院，湘潭411101）

0 引 言

圖像分割是把圖像分成若干個特定的、具有獨特性質的區(qū)域并提出感興趣目標的技術和過程.通?？砂凑沼脩舻母深A程度分為自動分割、交互式分割和手工分割.由于手工分割費時費力，自動分割又難以取得符合用戶用途要求的分割結果，而交互式能將兩者優(yōu)勢相結合，為用戶提供可以針對特定應用指定分割要求的能力，所以近年來發(fā)展很快.主要的研究方向包括：①基于圖割的分割算法［1］［2］［3］，通過進行信息傳播的最大流計算找出前景與背景種子的最小割；②基于隨機游走的分割算法［4］［5］［6］，通過計算每個像素隨機游走至各類種子的概率來確定像素的分割標志；③最短路徑法分割［7］［8］，通過計算各像素至各類標記的最短路徑實現(xiàn)分割.而且這些算法已被納入同一個框架下，即他們可看作該框架下的特例［9］［10］.盡管這些方法得到廣泛的應用，但所獲得的分割效果嚴重依賴于用戶標記的數(shù)量與位置，原因在于它們采用信息的近鄰傳播方式（只有空間位置相鄰的像素才可直接傳播），且以邊緣檢測為依據(jù)，所以其分割結果不僅體現(xiàn)為同一對象為相連的區(qū)域，而且對紋理區(qū)域容易混淆邊緣特征.但現(xiàn)實圖像中同一對象的組成不僅可能表現(xiàn)為一塊相連區(qū)域，也可能呈零散分布，關鍵它們具有相同或相近的視覺特征，如樹葉后的天空，網(wǎng)狀物后的背景等.盡管從理論上看，將像素間近鄰連接改為像素級全局連接（所有像素兩兩之間均存在連接，可以傳播信息）可以解決這個問題，但其復雜度為圖像尺寸的立方，對一般的圖像而言，計算機無法承受其龐大的計算量以及存儲需求.一種常用的變通方法是通過自動分割方法對圖像進行過度分割，所得到的小塊區(qū)域取代像素作為基本的分割單元［11］進行全局連接.

與基于像素單元的算法相比，該分割算法有利于利用區(qū)域特性，但當區(qū)域與圖像內物體邊界不一致時很難得到精確解.為此，本文提出一種將兩者相結合的兩級信息傳播算法，用戶只需添加非常少的標記也可以獲得很好的分割效果.

1 算法描述

在交互式分割過程中，用戶標記根據(jù)像素間相似度進行擴散，但現(xiàn)有的分割算法在計算像素間相似度時只考慮近鄰連接，其對應的有權圖只有一級－－像素級的近鄰擴散，而我們的擴散機制由兩級組成：在保留原有的像素級近鄰擴散方式上，另外利用均值漂移算法將圖像過度分割成小塊區(qū)域，組成區(qū)域級，作為虛擬像素，而塊與塊之間采用全連接，同時在擴散過程中兩級之間進行信息交換.本節(jié)首先介紹有權圖的設計方法，然后設計一個代價函數(shù)描述像素歸屬于各類用戶標記的概率；最后利用微粒群算法求解該約束優(yōu)化問題，最后得到分割結果.

1.1 有權圖結構模型

建立一個有權圖G，圖由節(jié)點集合V和邊集合E構成，G＝（V，E）.V包括像素集合X和區(qū)域集合R，且組成兩級形式，稱為像素級和區(qū)域級.若像素總數(shù)為n，區(qū)域總數(shù)為m，則共有n＋m個節(jié)點.邊集合E反映節(jié)點間的連接關系，連接節(jié)點i和j之間的邊表示為e（i，j），其權值代表節(jié)點i和j之間的連接緊密程度，對應于像素X（i）和X（j）間的相似度，如果相似度權值非零則稱X（i）和X（j）為鄰居點（像素）.E由三部分組成，E＝｛EX，ER，EXR｝，分別定義如下.

① 像素之間采用近鄰連接，即只有位置相鄰的像素間才有邊存在，用邊集EX表示，傳統(tǒng)算法中只存在這種連接方式.像素X（i）和X（j）間的相似度權重表示為寬為σ的高斯核函數(shù)

其中N（i）表示像素X（i）的近鄰，cX（i）為像素i的初始顏色.顯然WX為n×n矩陣.

② 塊之間采用全連接（即任意一對區(qū)域塊均有邊存在），用集合ER表示.塊R（i）和R（j）間的相似度權重表示為

其中cR（i）表示塊R（i）顏色，即塊內像素顏色的平均值.WR為m×m矩陣.

由于塊非常少，所以即使采用全連接，增加的計算量普通計算機完全可以承受.

③ 塊與像素間的連接用邊集合EXR表示.塊只跟所包含的像素有邊存在，其像素X（i）與塊R（j）間的相似度權重為

故WXR為n×m矩陣

1.2 基于像素標志歸屬度概率的圖像分割算法

要進行交互式分割，用戶首先要在一些像素上添加分類標記，這些標記像素稱為種子像素（Seeds），用SX表示.而區(qū)域集中包含有標記像素的區(qū)域，定義為標記塊，作為區(qū)域級虛擬像素中的種子像素，其標記與內部標記像素相同，所有標記塊組成的集合為SR.而本文算法通過同時計算各像素與塊到每類標記的歸屬度來確定其標志，從而得到分割結果.

1.2.1 像素的標志歸屬度代價函數(shù)設計

由于交互式分割基于信息沿周圍向外傳播，具有標志的連續(xù)性，即相似度越高的鄰居具有相同標志的概率越大，所以相鄰的像素之間，每塊與其內部的像素之間，塊與塊之間也應該具有這種特性.為此對任意一類標記（如l），定義以下代價函數(shù)來描述相似度高的鄰居（像素或塊）標志的連續(xù)性.

其中αl為長度n＋m的向量，αl（i）為像素（若0＜i≤n）或塊（若n＜i≤n＋m）i歸屬于標記l的概率.ε用于控制級間信息交換比例.約束條件規(guī)定了種子像素或塊的歸屬度取值：標記為l的種子對該類標記的歸屬度規(guī)定為1，而其它類標記的種子對標記l的歸屬度為0.

式（1）第一項用于評價像素級的標志的連續(xù)性，通過衡量相鄰圖像像素相似程度與它們標志歸屬度差異來體現(xiàn)，第三項用于評價區(qū)域級各塊標志的連續(xù)性，即若兩塊間具有相近的顏色則應具有相近的標志歸屬度.第二項用于評估兩級之間的標志連續(xù)性，與現(xiàn)有的基于區(qū)域單元的分割算法不同的是，后者采用硬性的標志連續(xù)性限制，即每塊內所有像素的標志歸屬度必須相同，本文的算法鑒于均值漂移的過度分割結果無法保證區(qū)域與圖像內物體邊界完全一致導致部分區(qū)域出現(xiàn)錯誤劃分，采用柔性的標志連續(xù)性限制，即只要求區(qū)域級中每個小區(qū)域塊內所有像素的標志歸屬度應該相近，而且通過設置衰減因子降低連續(xù)性限制程度，從而彌補錯誤劃分的影響.

該代價函數(shù)的最小化求解實際上是一個約束優(yōu)化問題，通過全局尋優(yōu)，可以獲得像素最佳的標志歸屬度分布.

1.2.2 基于微粒群算法的優(yōu)化求解

由于式（1）的代價函數(shù)的最小化求解為一個NP問題，所以本文采用微粒群算法來進行求解.雖然這是個約束優(yōu)化問題，但考慮到約束條件為賦值約束，可以簡化為基本的無約束優(yōu)化微粒群算法，只是在尋優(yōu)過程中對每次迭代后種子的標志按約束條件重新賦值.

微粒群優(yōu)化算法模擬鳥群覓食，將群體中的每個個體作為一個粒子.這些粒子在搜索空間中以一定的速度飛行，并依據(jù)自身以及同伴的飛行經驗對飛行速度作動態(tài)調整，體現(xiàn)為通過比較迭代過程中自身的最優(yōu)值和群體的最優(yōu)值來不斷地修正自己的前進方向和速度，最終搜索、尋找到問題的最優(yōu)解.

本文采用帶慣性權重的PSO算法［12］，粒子的位置表示待優(yōu)化問題（即式（1）的最小化）的解，每個粒子由一個速度矢量決定其飛行方向和速率大小，其速度和位置的更新公式如下所示：

其中i＝1，2，...，k，k為種群規(guī)模；第i個微粒的空間位置定義為xi＝（xi1，xi2，…，xiD），由于每個位置表示優(yōu)化問題的一個潛在解，由每個像素及塊的標志歸屬度構成，而D為搜索空間維度，故D＝n＋m；w為慣性權重（inertia weight），用來平衡局部和全局尋優(yōu)能力；c1和c2都為正常數(shù)，稱為加速系數(shù)（acceleration coefficient），rand1和rand2是兩個在（0，1）范圍內變化的隨機數(shù)，用于保持種群多樣性.

本文以式（1）的代價函數(shù)作為適應度函數(shù)，通過微粒群在搜索空間搜索，獲取使適應度函數(shù)最小的最佳標志歸屬度分布.步驟如下：

①初始化種群.設置微粒群的規(guī)模、各微粒的初始位置和初始速度以及常數(shù)如w，c1和c2，最大允許迭代次數(shù)等.

②計算各微粒的初始適應值.

③根據(jù)式（2）更新速度，并進行限幅處理.

④根據(jù)式（2）更新位置，并進行限幅，然后對每次迭代后種子的標志按約束條件重新賦值.

⑤重新計算各微粒的適應值.

⑥對每個微粒，比較其當前適應值和歷史最好適應值，勝者保存當前位置為其個體歷史最好位置.

⑦若滿足停止條件，搜索停止，輸出搜索結果.否則，返回③繼續(xù)搜索.

1.2.3 利用歸屬度概率實現(xiàn)圖像分割

通過采用上述微粒群算法對每類標志的歸屬度概率尋優(yōu)，從而獲得每個像素對各類標記的歸屬度概率，找出最大概率對應標志，作為該像素的最終標志，通過指定所有像素的標志從而完成圖像分割.

2 實驗結果及數(shù)據(jù)分析

2.1 參數(shù)設置

參數(shù)包括分割參數(shù)、代價函數(shù)參數(shù)以及尋優(yōu)參數(shù).

當采用均值漂移算法作過度分割時，需要確定每次迭代的搜索區(qū)域范圍，所以需要用到一對帶寬參數(shù)（hs，hr），其中hs用于控制平面尺度，而hr用于控制顏色尺度，設置為（hs，hr）＝（7，7），另外分割塊的最小尺寸設置為M＝30.

代價函數(shù)表達式中的參數(shù)ε用于控制級間信息傳播比例，當ε＝0，由于像素無法接受區(qū)域級信息，本算法退化成像素級的近鄰連接形式，而ε＝1，像素接受的信息全部為區(qū)域級信息，本算法退化成基于區(qū)域單元的全連接形式，實驗發(fā)現(xiàn)合適的ε值可選在區(qū)間［0.18，0.45］內，我們取ε＝0.3.

而微粒群算法的參數(shù)采用常規(guī)配置，即慣性權重w＝0.5，加速系數(shù)c1＝c2＝0.5.

2.2 實驗結果與分析

為了驗證本算法的性能，我們選取常用的交互式分割算法－－隨機游走分割法［4］進行實驗比較.

圖1是使用兩種方法根據(jù)完全相同的輸入進行分割的四組結果圖像.從左至右分別為人工標記圖像、隨機游走法和新方法的分割結果.

可以看到在人工標記很少的情況下，基于隨機游走的交互式算法分割結果不佳，容易出現(xiàn)錯分，相反，新算法可以獲得滿意的分割效果.原因在于前者基于近鄰擴散，信息只能沿周圍像素向外擴散，如果圖中含有復雜紋理，會妨礙信息的有效傳播，導致錯劃分，所以分割結果強烈依賴于用戶標記的數(shù)量及位置，特別是對零散分布對象（如第二組圖像中樹葉后天空），在顏色標記為單筆標記時，每個對象必然表現(xiàn)為一塊相連的區(qū)域，無法實現(xiàn)高質量分割，相反，新算法由于引入?yún)^(qū)域間全連接，有利于信息的遠距離跨塊傳輸，提高了分割效果對標記的魯棒性.

圖1 本文算法與隨機游走算法的分割效果

3 結 論

鑒于圖像中同一對象的組成不僅可能表現(xiàn)為一塊相連區(qū)域，也可能呈零散分布，還可能呈現(xiàn)為復雜的紋理形式，關鍵它們具有相同或相近的視覺特征，本文通過構建兩級有權圖引入圖像區(qū)域特性，而且設計一個約束優(yōu)化問題實現(xiàn)兩級信息的協(xié)調傳播，并結合微粒群進行全局尋優(yōu)獲得每個像素對各類標記的歸屬度概率，以此作為圖像分割的依據(jù).在該算法中引入了兩類連接方式：在區(qū)域級，塊與塊之間采用全連接，而兩級之間的連接實現(xiàn)塊與塊內每個像素的信息交流.為減少分割精度的影響，對區(qū)域級中每個小區(qū)域塊內所有像素的標志歸屬度連續(xù)性采用柔性限制.由于能有效地將全局信息與局部信息相結合，所以該算法對人工標記的數(shù)量與位置具有強魯棒性，即使在圖像中對象為零散分布時也可以獲得高質量的分割效果.

［1］ Boykov Y，Veksler O，Zabih R.Fast Approximate Energy Minimization via Graph Cuts［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2001，23（11）：1222－1239.

［2］ Rother C，Kolmogorov V，Blake A.Grabcut－Interactive Foreground Segmentation Using Iterated Graph Cuts［J］.ACM Transactions on Graphics，2004，23（3）：309－314.

［3］ 劉嘉，王宏琦.一種基于圖割的交互式圖像分割方法［J］.電子與信息學報，2008，30（8）：1973－1976

［4］ Grady L.Random Walks for Image Segmentation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2006，28（11）：1768－1783.

［5］ Kim T H，Lee K M，Lee S U.Generative Image Segmentation Using Random Walks with Restart［C］.Proceedings of 9th European Conference on Computer Vision，2008：264－275.

［6］ 徐海霞，田錚，丁明濤，溫顯斌.基于圖上隨機游走過程的SAR圖像圖譜分割方法［J］.光電子.激光，2009，20（7）：967－971

［7］ Bai Xue，Sapiro G.Distancecut：Interactive Segmentation and Matting of Images and Videos［C］.Proceedings of 2007IEEE International Conference on Image Processing，2007：249－252

［8］ Criminisi A，Sharp T，Blake A.GeoS：Geodesic Image Segmentation［C］.Proceedings of 9th European Conference on Computer Vision，2008：99－112

［9］ Couprie C，Grady L，Najman L etc.Power Watersheds：a Unifying Graph－Based Optimization Framework［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33（7）：1384－1399.

［10］Sinop A K，Grady L.A Seeded Image Segmentation Framework Unifying Graph Cuts and Random Walker Which Yields a New Algorithm［C］.Proceedings of 11th International Conference on Computer Vision，2007：1－8.

［11］Arbelaez P，Cohen L.Constrained Image Segmentation from Hierarchical Boundaries［C］.Proceedings of 2008IEEE Conference on Computer Vision and Pattern Recognition，2008：1－8.

［12］Shi Y，Eberhaet R C.A Modified Particle Swarm Optimizer［C］.Proceedings of IEEE International Conference on Evolutionary Computation，1998：69－73.