混合量子粒子群圖像分割算法IS-MQPS*

高穎慧,曲智國,盧 凱

(1.國防科學技術大學ATR國家重點實驗室，湖南 長沙 410073；2.國防科學技術大學計算機學院，湖南 長沙 410073)

混合量子粒子群圖像分割算法IS-MQPS*

高穎慧1,曲智國1,盧 凱2

(1.國防科學技術大學ATR國家重點實驗室，湖南 長沙 410073；2.國防科學技術大學計算機學院，湖南 長沙 410073)

基于群智能的圖像分割技術因其與人類視覺機理相符合，受到人們重視。但是，現有群體模型存在的對參數取值敏感和易收斂于局部極值等問題，制約了群智能技術在復雜圖像分割中的應用。首先定義了基于群智能圖像分割的抽象模型，然后將通用量子粒子模型GQPM引進圖像分割，提出了混合量子粒子群圖像分割算法IS-MQPS。IS-MQPS算法以量子粒子攜帶灰度和坐標信息，以糾纏量子態定義群體行為規則，以混合量子粒子群的自組織聚類實現圖像分割。實驗表明，IS-MQPS算法具有對噪聲不敏感、分割區域意義明確等優點，可應用于復雜圖像分割。

圖像分割；群智能；通用量子粒子模型；混合量子粒子群

1 引言

神經心理學對人類視覺機理的研究表明，人類視覺行為需要先后經過直覺和專注兩個階段。以行為科學觀點，直覺階段視覺行為是下意識過程，過程本身沒受到任何集中控制也沒有任何協調者，因此直覺階段視覺行為是一種分布式處理行為。直覺階段視覺行為所要達到的目的是對場景進行區域分割并初步提取出關注點，這與圖像分割目的一致，圖像分割過程可與直覺階段視覺行為相類比。因此，以分布式方案進行圖像分割是一種恰當合理的選擇。

群智能為尋找復雜分布式問題求解方案提供了基礎[1,2]，以群智能技術進行圖像分割成為當前圖像分割領域的一個重要研究方向。如：MacGill J[3]提出一個基于人工鳥模型Boid的圖像分割算法;Ramos V和Almeida F[4]基于Chialvo D R和Millonas M M[5]提出的蟻群模型，設計實現了一個圖像分割算法;何浩和陳艷秋[6]提出一個基于人工細胞模型的圖像分割算法;徐小慧和張安[7]基于一般粒子群模型實現了圖像分割;梁建慧和馬苗[8]基于人工蜂群實現了圖像分割;楚曉麗[9]基于人工魚群實現了圖像分割，等等。

這些算法采用自下而上的建模策略，通過對最小個體間及個體與環境間的簡單作用規則的調整，達到所需的全局演化行為，最終使整個群體“涌現”出某些與圖像本身相聯系的特征，進而實現圖像分割。雖然現有的這些基于群智能的圖像分割算法具有傳統圖像分割算法所不具有的全局性和分布性，但也存在圖像分割效果受群體模型本身性能影響較大的不足。例如，由于粒子群模型存在易發散和易陷入局部最優的不足，蟻群模型存在受參數取值影響較大和對個體初始放置位置敏感的不足，人工細胞模型存在受參數取值影響較大的不足，所以現有的這些基于群智能的圖像分割算法在分割復雜圖像時效果不很理想。

隨著量子理論的發展，研究人員發現量子系統和具有社會性的生物群體間有許多可類比的地方，且以量子系統模擬具有社會性的生物群體擁有許多非量子系統不具有的優點[10]。于是，出現了以量子態定義個體、基于量子糾纏機理和馮·諾依曼(Von Neumann)熵理論設計群體進化規則的新型群體模型-通用量子粒子模型GQPM(Generalized Quantum Particle Model)[10]。GQPM具有對噪聲不敏感、適用于高維和大數據集聚類等優點。

為提高復雜圖像分割性能，本文將GQPM引進圖像分割，提出了混合量子粒子群圖像分割算法IS-MQPS(Image Segmentation Algorithm based on Mixed Quantum Particle Swarm)。實驗結果表明，IS-MQPS算法具有良好的分割效果和抗噪聲能力，可用于復雜圖像的分割。

2 基于群智能圖像分割算法的抽象模型

群智能是人工生命研究的重要內容，是解決分布式問題的重要手段，群智能應用最廣泛的領域之一就是數字圖像處理。通過深入研究文獻[1～9]可知，一個基于群智能的圖像分割算法ISA_SI(Image Segmentation Algorithm based on Swarm Intelligence)，可以表達為一個三元問題：

(1)

其中，PIA(Particle Inhabiting Array)是粒子棲息陣列，用來放置群體;SM(Swarm Model)是群體模型，指放置在粒子棲息陣列上的群體的具體形式；CR(Conjunction Rule)是關聯準則，用于建立群體與圖像數據間聯系的規則。

從圖1可知，群體模型SM包含三個元素：

(1)個體模型IM(Individual Model)：指群體中各個粒子的具體形式，它決定群體的一般性特征。

(2)行為規則AR(Action Rule)：指群體中個體運動、變換或繁殖，進而實現自組織聚類所依據的準則。行為規則是實現群體進化、最終“涌現”出種群特征的關鍵。

(3)協調方程HE(Harmony Equation)：指衡量群體進化程度的方程，可通過它來控制進化。

基于群智能圖像分割的基本思想：將構成群體的個體隨機放置于群體棲息陣列上，基于某種關聯準則建立群體與圖像數據間的聯系。個體依據某種行為規則在群體棲息陣列上運動、變換或繁殖，進而實現自組織聚類。該進程不斷進行，群體逐漸分化成一系列小種群，同一小種群內的粒子具有某種相似特征。

由于建立了群體與圖像數據間的聯系，故由種群特征可凸顯出圖像各區域的特征，達到分割目的。

Figure 1 Composition of SM

群體模型SM是決定基于群智能圖像分割效果的關鍵元素，為了獲得良好的分割效果，需要選擇性能良好的群體模型。

3 通用量子粒子模型GQPM

不斷從不同領域涌現的新思想，啟發群智能研究者定義更多性能更優的群體模型，以拓展群智能應用范圍和改進群智能應用效果。由群智能理論可知，具有社會性的生物群體中大量個體的隨機行為將導致群體的一個確定行為。若將群體看作一個復合系統，群體中的個體看成復合系統的子系統時，以上現象意味著系統聯合熵小于其各子系統的熵，且具有負的條件熵。經典信息論中，Shannon聯合熵大于或等于其任意子系統的Shannon熵，Shannon條件熵不可能為負，所以Shannon熵不滿足以上要求。對量子理論的研究發現：(1)量子系統中大量微觀粒子的隨機微觀行為將導致系統的一個確定性宏觀行為，這可與群智能中個體和群體間關系相類比，因此可以用量子態糾纏方法來刻畫群體行為和個體行為之間的關系；(2)量子糾纏態的馮·諾依曼熵滿足系統聯合熵小于其各子系統熵及條件熵為負的要求，因此量子態糾纏方法較其它非量子化方法更加適用于基于群智能的聚類。Shuai Dian-xun等人[10]將量子態概率幅表示、量子態糾纏機理和馮·諾依曼熵理論引進群體模型，定義了通用量子粒子模型GQPM。

4 混合量子粒子群圖像分割算法IS-MQPS

IS-MQPS基本思路如下：根據像素灰度信息定義粒子量子態及量子態糾纏原則，再令量子粒子攜帶灰度和坐標信息，以量子粒子群在量子粒子棲息陣列上的糾纏進化實現灰度相近且位置接近的像素的聚類，實現分割。IS-MQPS算法基本流程如圖2所示。

Figure 2 Flow of IS-MQPS

一個好的圖像分割算法應該滿足以下三點：(1)不需選取閾值；(2)輪廓連續；(3)區域分割適量。IS-MQPS算法對以上三點都有較好體現。

4.1 圖像粗分割和過渡區提取

過渡區是環繞目標邊界兼具邊界和區域特征的帶狀區，通過細化過渡區可得到邊界線。過渡區提取是通過圖像粗分割實現的。圖像粗分割就是利用邊緣檢測和區域生長確定待分割圖像大概劃分成多少個區域，并將區域間分隔帶標記出來的過程。

根據圖像特點選擇足夠靈敏的邊緣檢測算子，檢出圖像中所有可能的邊緣點，即過渡區的點，圖像上所有點就被分成了非過渡區和過渡區兩部分。將進行了過渡區標記的圖像記作TR(x,y)，當(x,y)為過渡區點時，TR(x,y)=1，否則TR(x,y)=0。記TR0為所有非過渡區點的集合，TR1為所有過渡區點的集合。

區域生長的基本思想是將具有相似性質的像素集合起來構成區域。具體如下：首先在需要分割的區域找一個種子像素作為生長起點，然后將種子像素鄰域中與其性質相近的像素，根據事先確定的相似準則合并到種子像素所在的區域中。再將這些新像素當作新的種子像素重復以上過程，直到再沒有滿足相似準則的像素可以被包括進來為止，這樣就形成了一個區域。對于整幅圖像的分割，一個區域生長完成后，還必須檢查是否還有尚未涉及到的像素。如果還有，那么在剩下的像素中，再選擇一些種子像素進行生長，形成新的區域。如此繼續下去，直到圖像中所有的像素都歸屬到相應的區域中，整個圖像的分割才算完成。

4.2 混合量子粒子群

粒子群中包含兩種量子粒子：一是像素量子粒子，二是質心量子粒子。以下分別進行介紹。

(1)像素量子粒子。

將過渡區TR1中每一個像素與一個量子粒子相關聯，這種量子粒子攜帶以下信息：① 粒子量子態：通過量子化與粒子相關聯像素的灰度值得到；② 兩類數據信息：一類是與粒子相關聯像素的灰度值，另一類是像素坐標值。將這種量子粒子稱為像素量子粒子，記為pc。

(2)

pck攜帶的兩類數據信息組成如下結構：

(3)

(2)質心量子粒子。

例如，第h個區域如圖3所示。

Figure 3 Sketch map of region border and region centroid

(4)

cch攜帶的數據信息組成如下結構：

(s-1,{t-2,t+2}),(s,{t-3,t+3}),

(s+1,{t-3,t+3}),(s+2,{t-3,t+3}),

(s+3,{t-2,t-1,t+2}),(s+4,{t,t+1})}

(5)

4.3 糾纏聚類

為了進行糾纏聚類，首先需要將混合量子粒子群放置在量子粒子棲息陣列上。可選擇待分割圖像作為粒子棲息陣列，但由于一般有W×H?(s+n)，W×H代表待分割圖像尺寸，(s+n)為混合量子粒子群的粒子數，因此為減少計算量，可以以一個較小尺寸陣列作為粒子棲息陣列。選陣列尺寸為N×N，滿足N×N>(k+n)及N×N?W×H。

(1)碰撞規則。

(6)

Figure 4 Sketch map of pixel neighbourhood

③質心量子粒子間的碰撞。由于每一個質心量子粒子都與一個區域相關聯，每一個區域代表一個類，所以，即使存在某一個質心量子粒子位于另一個質心量子粒子的坐標鄰域中，它們之間也不發生糾纏。

(2)糾纏規則。

量子粒子間的糾纏是完成量子粒子自組織聚類的關鍵，以下考慮如何實現糾纏。設任意兩個量子粒子(既可以是像素量子粒子，也可以是質心量子粒子)滿足糾纏條件，它們基于以下規則實現糾纏：

(7)

公式(7)滿足以下要求：

當多于兩個量子粒子需要糾纏時，對糾纏規則進行如下改進：設量子粒子ch也在ck的坐標鄰域內，它們也滿足相互糾纏的條件，則根據糾纏態傳遞性，ch與cl也滿足糾纏條件，ch、cl及ck將糾纏在一起。

(8)

(3)聚類后處理。

在粒子碰撞糾纏過程中，當某一個糾纏類中已經包含了一個質心量子粒子，此時，若再有一個質心量子粒子跟該類中的某一個量子粒子滿足糾纏條件，后出現的質心量子粒子將不與該類糾纏。這是由于每個質心量子粒子都代表一個初始分割出來的區域，也就是代表一個類，而每一類中只能有一個質心量子粒子。后出現的質心量子粒子將等待其它滿足糾纏條件的不含質心量子粒子的糾纏類進行糾纏。

閾值TH的取值由待分割圖像的特點決定，最小取9。若待分割圖像每一個區域都較大，則TH的值可以適當取大一些。

混合量子粒子群完成聚類后，根據量子粒子攜帶的像素坐標值，將各類量子粒子所攜帶像素映射回待分割圖像，并將同類量子粒子攜帶的像素賦予相同灰度值，從而完成圖像分割。

5 實驗及結果分析

5.1 分割質量評價方法

圖像分割算法的分割質量評價方法分為主觀評價方法和客觀評價方法兩類。主觀評價方法是最常用的方法，是通過人對圖像本身的觀察理解，主觀地對比不同算法的分割結果。但是，主觀評價方法存在一些局限，如需要有參照、圖像類型對評價結果有影響等等。客觀評價方法是通過一些已經建立的評價模型或評價標準來評價算法的優劣，但沒有一種通用有效的客觀評價標準。常見的評價標準和評價方法包括：

(1)區域內部均勻性：分割常常被定義為把一幅原始圖像分成若干個內部性質相似的區域，因此可以用分割圖中各個區域內部特性的均勻程度來描述分割圖像的質量。

(2)輪廓連續性：輪廓連續可以保證分割出來的每一個區域有意義。若輪廓不連續，則本來不同的區域可能會連在一起，這樣的分割就不好。

(3)抗噪聲能力：噪聲在圖像中是普遍存在的。當噪聲嚴重時，需要采用專門的去噪算法進行處理。但是，對于輕度噪聲，好的分割算法應該不受其影響，所以抗噪聲能力也是衡量分割算法性能的一個方面。

5.2 分割實驗及結果分析

本文提出的IS-MQPS算法，需要基于邊緣檢測和區域生長對圖像進行粗分割。實驗中，我們統一采用Krisch算子來檢測邊緣，Krisch算子定義如下：

K1～K8是八個卷積模板。在每一個像素位置分別用這八個模板計算卷積值，然后將這八個卷積值中的最大值輸出，作為檢測到的邊緣值。模板在圖像上移動，計算出每一個像素位置的邊緣值，就完成了對整幅圖像的邊緣檢測。

(1)分割效果對比實驗。

通過分析圖5和圖6兩組分割效果對比圖，總結本文算法特點如下：

① 由于本文算法的粗分割過程可以將圖像中明顯區域的邊緣提取出來，從而保證了圖像中的明顯區域在分割過程中不會被割裂，使得分割后區域意義比較明確，提高了分割質量。同時本文算法對混合量子粒子群的初始放置位置不敏感，所以本文算法的分割質量比較穩定。蟻群分割算法的分割質量受粒子數量、迭代次數及原圖像質量的影響較大，當粒子數量不夠多、迭代次數較少或原圖像比較復雜時，該算法的分割質量就不很理想。人工細胞群分割算法的分割質量受迭代次數及原圖像質量的影響也較大，當迭代次數較少或原圖像比較復雜時，該算法的分割質量也不理想。

②本文算法的時間性能較好，尤其當圖像中各區域內部灰度較均勻，過渡區像素個數較少時，如圖6a所示。人工細胞群分割算法的時間性能最差，這主要是由于該算法粒子數量多，且在每一輪迭代中對每一個粒子進行更新的計算量較大。蟻群分割算法的時間性能受粒子數量和迭代次數的影響較大。

Figure 5 Comparison of segmentation effect (Part 1)

Figure 6 Comparison of segmentation effect (Part 2)

(2)抗噪聲能力測試。

本實驗的目的是測試本文算法的抗噪聲能力。圖7是一幅人工合成的簡單圖像，通過在該圖像中加入椒鹽噪聲和高斯噪聲得到所需的含噪圖像，具體如圖8a和圖9a所示。

Figure 7 Source image used to test anti-noise ability

Figure 8 Segmentation result of salt and pepper noise image

Figure 9 Segmentation result of Gaussian noise image

從圖8和圖9的含噪圖像分割結果可以看出：

①圖8a是含椒鹽噪聲(噪聲強度為0.02)的圖像。圖8d是本文算法的分割結果，可以看出分割結果與原圖像間差異較小，噪聲僅僅在邊緣部分對分割結果有所影響。

②圖9a是含高斯噪聲的圖像，噪聲均值為0，方差為0.004。圖9d是本文算法的分割結果，可以看出分割結果比較準確，區域連續性和邊緣完整性都較好，沒有受到噪聲影響。

本文算法具有一定的抗噪聲能力，從算法本身來分析，有三個方面可以減小噪聲對分割的影響：(1)群智能技術本身就具有一定的抗噪聲能力，量子粒子群作為一種群智能實現模式，也具有一定的抗噪聲能力。(2)每一個量子粒子所攜帶的數據信息，除了灰度以外，還有像素坐標信息。粒子間的糾纏前提是所攜帶的數據信息要相似，不但灰度值要接近，坐標位置也需相距不遠，才能進行粒子糾纏。這在一定程度上抑制了相對孤立的小區域的存在。(3)當進化過程終止之后，雖然仍可能存在一些由噪聲引起的相對孤立的部分，但分割后處理會重新調整和優化分割結果，這樣可以很大程度上抑制噪聲對分割結果的影響。

6 結束語

基于群智能的圖像分割因其與人類視覺機制相符合，成為一種重要的圖像分割算法。由于現有群智能實現模式存在對參數取值敏感、易收斂于局部極值等問題，所以利用現有群智能實現模式對復雜圖像進行分割，分割效果往往不很理想。針對該問題，本文將基于量子糾纏機理和VonNeumann熵理論定義的通用量子粒子模型GQPM引進圖像分割，設計基于GQPM的高性能圖像分割算法，提出了混合量子粒子群圖像分割算法IS-MQPS，以滿足復雜圖像的分割需求。實驗表明，IS-MQPS分割算法具有良好的分割效果和較強的抗噪聲能力，可應用于復雜圖像的分割。

[1]LeiXiu-juan.Swarmintelligentoptimizationalgorithmsandtheirapplications[M].Beijing:SciencePress, 2012.(inChinese)

[2]LiBi,HaoZhi-feng.Cooperativecoevolutionaryalgorithmanditsapplications[M].Beijing:SciencePress,2013.(inChinese)

[3]MacGillJ.Usingflockstodriveageographicalanalysisengine[C]∥ProcofArtificialLifeⅥ, 2000:453-466.

[4]RamosV,AlmeidaF.Artificialantcoloniesindigitalimagehabitats—Amassbehavioureffectstudyonpatternrecognition[C]∥Procofthe2ndInternationalWorkshoponAntAlgorithms(FromAntColoniestoArtificialAnts), 2000:113-116.

[5]ChialvoDR,MillonasMM.Howswarmsbuildcognitivemaps[C]∥ProcoftheBiologyandTechnologyofIntelligentAutonomousAgents, 1995:439-450.

[6]HeH,ChenYQ.Artificiallifeforimagesegmentation[J].InternationalJournalofPatternRecognitionandArtificialIntelligence, 2001, 15(6):989-1003.

[7]XuXiao-hui,ZhangAn.Entropicthresholdingmethodbasedonparticleswarmoptimizationforimagesegmentation[J].ComputerEngineeringandApplications, 2006,42(10):8-11.(inChinese)

[8]LiangJian-hui,MaMiao.Artificialbeecolonyalgorithmbasedresearchonimagesegmentation[J].ComputerEngineeringandApplications, 2012,48(8):194-196.(inChinese)

[9]ChuXiao-li. K-meansclusteringalgorithmandartificialfishswarmalgorithmappliedinimagesegmentationtechnology[J].ComputerSystems&Applications, 2013,22(4):92-94.(inChinese)

[10]ShuaiDian-xun,ShuaiQing,DongYu-min.Self-organizingdataclusteringbasedonquantumentanglementmodel[C]∥Procofthe1stInternationalMulti-SymposiumonComputerandComputationalSciences,2006:1.

附中文參考文獻：

[1] 雷秀娟.群智能優化算法及其應用[M].北京：科學出版社，

2012.

[2] 李碧，郝志峰.協同進化算法及其應用[M].北京：科學出版社，2013.

[7] 徐小慧，張安.基于粒子群優化算法的最佳熵閾值圖像分割[J].計算機工程與應用，2006，42(10)：8-11.

[8] 梁建慧，馬苗.人工蜂群算法在圖像分割中的應用研究[J].計算機工程與應用，2012，48(8)：194-196.

[9] 楚曉麗.K-Means聚類算法和人工魚群算法應用于圖像分割技術[J].計算機系統應用，2013，22(4):92-94.

GAO Ying-hui,born in 1975,PhD,associate professor,her research interests include image processing, quantum information processing, and pattern recognition.

曲智國(1982-),男,山東德州人，博士，研究方向為圖像處理、量子信息處理和模式識別。E-mail:Green20001@sina.com

QU Zhi-guo,born in 1982,PhD,his research interests include image processing, quantum information processing, and pattern recognition.

盧凱(1973-),男，上海人，博士，教授，研究方向為并行計算機結構和高性能并行系統軟件。E-mail:kailu@nudt.edu.cn

LU Kai,born in 1973,PhD,professor,his research interests include parallel computer architecture, and high performance parallel system software.

A novel image segmentation algorithm based on mixed quantum particle swarm

GAO Ying-hui1,QU Zhi-guo1,LU Kai2

(1.National Key Laboratory of Automatic Target Recognition,National University of Defense Technology,Changsha 410073；2.College of Computer,National University of Defense Technology,Changsha 410073,China)

Image segmentation technology based on swarm intelligence has been paid more and more attentions due to its consistency with human visual mechanism. However, many existing swarm models are sensitive to parameter values and easy to converge to the local minimum, which restricts the application of swarm intelligence in complex image segmentation. In the paper, we define the abstract model of image segmentation based on swarm intelligence firstly, and then propose a novel image segmentation algorithm based on mixed quantum particle swarm (IS-MQPS) by introducing the eneralized quantum particle model (GQPM) into image segmentation. IS-MQPS contains three key parts: defining the quantum particle by pixel's grey value and position value, defining the swarm action rule by entangled quantum state, and realizing image segmentation by self-organization clustering of mixed quantum particle swarm. Experiments show that IS-MQPS is insensitive to noise, has good segmentation effect, and can be used in complex image segmentation.

image segmentation;swarm intelligence;generalized quantum particle model;mixed quantum particle swarm

1007-130X(2015)01-0125-08

2013-04-01;

2014-11-07基金項目：國家自然科學基金資助項目(61103082)

TP18

A

10.3969/j.issn.1007-130X.2015.01.019

高穎慧(1975-),女,黑龍江大興安嶺人，博士，副教授，研究方向為圖像處理、量子信息處理和模式識別。E-mail:yhgao@nudt.edu.cn

通信地址：410073 湖南省長沙市國防科學技術大學ATR國家重點實驗室

Address:National Key Laboratory of Automatic Target Recognition,National University of Defense Technology， Changsha 410073,Hunan,P.R.China