基於分水嶺-量子進化聚類算法的圖像分割方法

2023-04-24 09:46:51 1

專利名稱：基於分水嶺-量子進化聚類算法的圖像分割方法
技術領域：
本發明屬於圖像處理技術領域，特別是涉及一種圖像分割方法，該方法可用於圖像處理中的目標識別。

背景技術：
圖像處理是一個跨學科的領域，隨著計算機科學技術的不斷發展，圖像處理和分析逐漸形成了自己的科學體系。圖像分割是圖像處理中一個非常重要的步驟，它將圖像分割成為具有相關性強的子區域或對象。圖像分割就是依據某種準則將圖像分為若干區域的過程，要求同一區域內的像素具有某種一致性，不同區域的像素之間不存在這種一致性。圖像分割方法一直是圖像處理和分析中基本而關鍵的技術之一，圖像分割的結果包含著對圖像理解更為精確的描述，並且支持一些更高級的概念，例如形狀、區域、連接等。圖像分割通常用於進一步對圖像進行分析、識別、壓縮編碼等，分割的準確性直接影響到後續任務的有效性，作為由圖像處理到圖像分析的關鍵步驟，圖像分割不僅得到了人們的廣泛重視，也在實際中得到了大量的應用。
紋理特徵是圖像的重要屬性，紋理被認為是區分圖像間不同屬性的重要解譯信息。近三十年來研究學者提出了許多基於紋理特徵的分割方法。這些方法主要分為四類統計方法，結構方法，模型方法和信號處理方法。以上幾種方法在處理圖像分割問題時均採用了有監督的方法，而在不同的圖像中，同樣屬性的目標區域看起來往往會有很大的不同，即使是處在同一幅圖像中也存在著這樣的差異。因此，採用有監督方法選擇的訓練樣本往往不能包含圖像中目標區域的所有類屬特徵。在這種情況下，無監督的分割方法，通常又叫做聚類方法，就會更加有效。無監督分割方法一般可以分為兩類層次聚類和劃分聚類，其中劃分聚類通過最小化特定準則將數據集劃分到不同的類屬中。因此這類方法可以看作是最優化問題，將圖像分割問題視為組合優化問題。但是已有的優化方法對於處理優化問題的時候往往耗時很長，並且在搜索過程中容易陷入局部最優，同時對於複雜圖像分割問題往往會存在邊緣定位不夠準確的缺點，這樣勢必會影響到圖像分割的區域一致性與邊緣保持的性能。


發明內容
本發明的目的在於克服上述已有技術的不足，提出一種基於分水嶺-量子進化聚類的圖像分割方法，以快速、有效地搜索到最優聚類中心，準確定位邊緣，提高圖像區域一致性和邊緣保持性能。
實現本發明的技術方案是將圖像分割問題看作組合優化問題，使用分水嶺算法將圖像實行分塊處理，用量子進化算法計算搜索，使適應度函數最大化的序列組合作為聚類結果，進而得到最終分割結果。具體實現步驟如下 (1)輸入待分割圖像，按照分水嶺算法對圖像進行分塊處理； (2)對分塊後圖像的每個像素點提取離散小波能量特徵，進而求得區域塊特徵，將該特徵作為聚類數據集。
(3).設置抗體規模n、類別數k和停機條件，隨機產生初始量子染色體Q(t)作為聚類數據集的初始聚類中心，其中的αit，βit(i＝1，2…m)和所有的qjt都以等概率

初始化； (4).將初始量子染色體Q(t)觀測成為二進位染色體p(t)； (5).計算每個觀測後的二進位染色體p(t)與聚類數據集的親和度函數fk，保留當前種群中的最優個體； (6)將初始量子染色體Q(t)進行量子變異操作，得到量子種群Qm(t) (7)將的量子種群Qm(t)進行量子交叉操作，得到新的量子種群Qc(t)作為新的聚類中心； (8)將新的量子種群Qc(t)觀測成為二進位染色體pc(t)，計算每個染色體與聚類數據集的適應度函數值fc； (9)對pc(t)進行選擇操作，得到子代染色體p(t+1)； (10)判斷子代染色體是否滿足停機條件，如果滿足該條件就將子代染色體中親和度最高的染色體對應的圖像類屬劃分作為輸出結果，否則返回過程(4)，循環執行過程(4)～(10)，直到滿足停止條件。
本發明與現有技術相比具有如下優點 本發明綜合了量子進化計算與分水嶺圖像分割方法，得到了很好的分割效果。首先，量子進化計算作為一種新興的人工智慧方法，可以很好地解決這一類型的組合優化問題，以實現對圖像數據的有效類別劃分。形態學分水嶺算法充分利用了梯度操作捕獲到的邊緣信息，使得邊緣定位比較準確。
1.在圖像數據聚類過程中快速且有效地搜索到最優聚類中心，防止在進化過程中陷入局部最優解。
本發明由於採用了量子進化聚類算法，在圖像分割操作中利用量子編碼的疊加性構造的染色體，使得作用在量子編碼染色體上的操作具有高效的並行性，為防止盲目的搜索，利用當前最優染色體的信息來控制變異，使種群以大概率向著優良模式進化來加速收斂，並且有效地提高了搜索速度，使得該操作的時間複雜度降低。隨著問題的複雜求解能力不盡人意，在各個子群體間採用量子交叉操作增強信息交流，在各個子群體內部採用量子旋轉門對染色體進行進化，並動態調整旋轉角度，在全局搜索的同時兼顧局部，有效防止了在進化過程中陷入局部最優解。
2.邊緣定位比較準確 本發明由於採用了形態學分水嶺算法，在圖像分割過程中充分利用了梯度操作捕獲到的邊緣信息，使得邊緣定位比較準確。
3.圖像分割效果好 本發明由於採用了分塊處理的思想以及量子編碼，量子交叉，量子變異操作和精英選擇策略操作，因而具有比現有技術更好的圖像分割效果。仿真實驗表明，針對不同紋理圖像，SAR圖像，其分割結果的區域一致性，邊緣準確性好，同時具有更低的分割錯誤率。



圖1是本發明的分割流程圖； 圖2是本發明將量子染色體觀測成為二進位染色體示意圖； 圖3是現有量子旋轉門的構造示意圖； 圖4是用本發明方法對人工紋理圖像Image1的分割結果示意圖； 圖5是用本發明方法對人工紋理圖像Image2的分割結果示意圖； 圖6是用本發明方法對人工紋理圖像Image3的分割結果示意圖； 圖7是用本發明方法對Ku波段SAR圖像的分割結果示意圖； 圖8是用本發明方法對X波段SAR圖像的分割結果示意圖。

具體實施例方式 參照圖1，本發明的分割過程如下 過程1，對待分割圖像進行分塊處理。
1.1)輸入待分割圖像圖像，將待分割圖像簡化； 簡化的目的是去掉小的噪聲幹擾以及對感知不重要的細節，對圖像起到平滑作用。這裡選取形態學中最常用的工具之一開形態重建濾波器。與經典的圖像簡化工具，如低通或中通濾波器相比，形態重建濾波器的優勢在於簡化圖像而不造成圖像模糊或改變圖像輪廓。
1.2)計算簡化後圖像的形態梯度圖像； 形態梯度圖像反映了圖像中灰度的變化情況，在灰度值變化較大的邊緣具有較大的梯度值，而在灰度值均勻的區域內部具有較小的梯度值。一幅圖像f的形態梯度圖像定義為膨脹變換減去腐蝕變換 grad(f)＝(f⊕b)-(fΘb) 其中，⊕表示膨脹運算，Θ表示腐蝕運算，b為結構元素，結構元素不能取太大，否則會將灰度變化劇烈的小區域濾掉。
1.3)計算形態梯度圖像的浮點活動圖像； 所謂「浮點」是指圖像的數據類型是浮點型，浮點活動圖像在圖像邊緣具有較高的亮度值，因此，浮點活動圖像本身就比較粗糙地反映了圖像的邊緣。浮點活動圖像定義為 fimg(f)＝grad(f)*grad(f)/255.0 1.4)將浮點活動圖像輸入分水嶺算法產生過分割結果。
過程2，對分塊後圖像的每個像素點提取離散小波能量特徵，進而求得區域塊特徵，將該特徵作為聚類數據集，具體的做法如下 2.1)對原圖像提取離散小波能量的紋理特徵 本發明中選用離散小波兩層變換的子帶能量f作為圖像的特徵向量{f1，f2，…，f3n+1}，其中，n表示特徵向量的維數，本實例選用n＝7但不限於7，該子帶能量為 其中，M×N為子帶大小，(i，j)表示該子帶係數的索引，x(i，j)表示該子帶中第i行第j列的係數值。
2.2)圖像分塊後得到很多不規則子塊，將所有不規則子塊中像素特徵的均值作為該不規則塊的特徵。
過程3，設置初始化參數，生成初始量子染色體。
3.1)按照量子進化算法設置染色體規模n、類別數k，同時給定本發明方法的停機條件—最大適應度值改變量的閾值範圍ε以及連續無法改進次數n； 3.2)隨機產生初始量子染色體Q(t)作為聚類數據集的初始聚類中心。其中初始量子染色體Q(t)的產生，其過程是用一對複數定義一個量子比特位。一個量子比特的狀態可以取0或1，其狀態可以表示為|Ψ＞＝α|0＞+β|1＞，其中α，β為代表相應狀態出現概率的兩個複數。量子比特處於狀態0和狀態1的概率分別是|α|2，|β|2，並且|αi|2+|βi|2＝1(i＝1，2，…，m)。一個具有m個量子比特位的系統可以描述為

這種表示方法能夠表徵任意的線性疊加態。在本發明中，均以等概率

初始化，意味著所有可能的線性疊加態以相同的概率出現。
過程4，將初始量子染色體Q(t)觀測成為二進位染色體p(t)。
通過觀察初始量子染色體Q(t)的狀態，產生一組普通二進位解p(t)，其中在第t代中每個xjt(j＝1，2，…，n)是長度為m的串(x1x2…xm)，它是由量子比特幅度

或

得到的。產生二進位染色體的具體過程，見圖2隨機產生一個
數，若它大於

則相應的二進位位上取1，否則取0。
過程5，計算每個觀測後的二進位染色體p(t)與聚類數據集的親和度函數fk，保留當前群體中的個體。
個體適應度函數定義為 其中，μij表示一個像素點樣本j屬於各個類別i的隸屬度，m表示模糊指數，d(i，j)表示第i個聚類中心到第j個像素樣本之間的歐幾裡德距離。
過程6，將初始量子染色體Q(t)進行量子變異操作，得到新的量子種群Qm(t)。
在本發明中，各個狀態間的轉移是通過量子門變換矩陣實現的，用量子旋轉門的旋轉角度表徵了量子染色體中的優化方向，進而方便的在變異過程中加入最優個體的信息，加快算法收斂。在0、1編碼的問題中，設計了下面這種量子變異算子來加速進化求優表示量子旋轉門，旋轉變異的角度θ可由表1得到。
表1 變異角θ(二值編碼)
其中xi為當前染色體的第i位；besti為當前的最優染色體的第i位；f(x)為適應度函數，Δθi為旋轉角度的大小，控制算法收斂的速度；s(αiβi)為旋轉角度的方向，保證算法的收斂。
量子旋轉門的構造參照圖3直觀的說明如當xi＝0，besti＝1，f(x)≥f(best)時，為使當前解收斂到一個具有更高適應度的染色體，應增大當前解取0的概率，即要使|αi|2變大，如果(αi，βi)在第一、三象限，θ應向順時針方向旋轉；如果(αi，βi)在第二、四象限，θ應向逆時針方向旋轉。
過程7，將新的量子種群Qm(t)進行量子交叉操作，得到Qc(t)，並將其作為新的聚類中心。
本發明通過使用量子的相干特性構造一種新的交叉操作—「全乾擾交叉」。量子染色體在實行在這種交叉操作之前的狀態如表2所示，該量子交叉操作採用對角線交叉的方式，讓處於對角線上的染色體經過這種量子交叉方式之後處於同一行上面，這樣保證了種群中的所有染色體均參與交叉。實行量子交叉後各個染色體之間的狀態如表3所示。這種量子交叉可以充分利用種群中的儘可能多的染色體的信息，改進普通交叉的局部性與片面性，在種群進化出現早熟時，它能夠產生新的個體，給進化過程注入新的動力。
表2 量子交叉操作前的染色體
表3 量子交叉操作後的染色體
過程8，將新的量子種群Qc(t)觀測成為二進位染色體pc(t)，計算每個染色體與聚類數據集的適應度函數值fc； 過程9，對pc(t)進行選擇操作，得到子代染色體p(t+1)。選擇操作的目的是選擇出適應度較高的染色體，這些染色體對應的待分割圖像的結果要好於適應度低的染色體對應的分割結果。本發明採用的是精英選擇策略。通常的選擇方法就是高適應度的個體被選擇保留下的機率會很大。採用精英選擇策略可以保證某一代的最優解在整個進化過程中可以毫髮無損地被保留下來。具體為，即在進化過程中，如果某一代中的最優解的適應度函數值優於當前代最優解的適應度函數值，則當前代最優解就被該最優解所代替，以保證在進化過程中每一代的最優解都不會丟失。
過程10，輸出圖像類屬劃分結果的條件判斷。
按照輸出分割結果時最佳的染色體適應度改變量至少連續迭代n次不變的原則，設置停機條件。具體為判斷第t代與t+1代最大適應度值之差是否大於該閾值，如果最大適應度值之差，則稱為最佳適應度改變量1次不變。如此反覆迭代，直到滿足n次不大於已設定的閾值範圍，就將該染色體中親和度最高的染色體體對應的圖像類屬劃分作為輸出結果。否則返回步驟(4)，循環執行步驟(4)～(10)，直到滿足輸出類屬劃分結果的條件為止。
通過上面十個步驟的操作，對於輸入的待分割圖像均可以輸出一個最佳的分割結果。
本發明的效果可以通過以下仿真進一步說明 1仿真內容將本發明方法與基於遺傳算法聚類方法GAC，和基於免疫進化聚類算法IEC以及傳統的K均值聚類方法KM，分別針對人工紋理圖像數據，Ku波段SAR圖像數據，X波段SAR圖像數據的分割性能進行了比較。
2仿真參數設置本發明QWC參數設置為種群規模40個個體；現有的遺傳算法GA的參數設置為種群規模40個個體，交叉概率pc＝0.75，變異概率pm＝0.1；現有的免疫進化算法IEA的參數設置為種群規模40個個體，疫苗長度v＝10，交叉概率pc＝0.75，變異概率pm＝0.1，疫苗接種概率pv＝0.3，所有方法均以指定預先精度1e-5為閾值，連續30次最大適應度無改進為停機條件。
3.仿真實驗結果 (1)人工紋理圖像分割的仿真結果 為進一步驗證新方法的有效性，對三幅人工紋理圖像進行了測試。Image1是一幅256×256的灰度圖，取自Brodatz紋理圖像庫，它包含兩類紋理特徵，如圖4(a)所示，圖4(b)給出了Image1的理想分割結果。Image2包含三類紋理特徵，圖5(a)和圖5(b)分別代表了Image2的原始圖像和理想分割結果。Image3包含四類紋理，圖6(a)和6(b)分別代表了Image3的原始圖像和理想分割結果。針對每一個測試問題分別進行20次獨立實驗，三幅人工紋理圖像分割結果的Cluster Error指標平均結果如表4所示。圖4～圖6中的(c)～(f)分別是基於QWC，GAC，IEA和KM四種算法針對三幅紋理圖像的分割結果。
表4 QWC，GAC，IEA和KM對三幅人工紋理圖像的分割對比結果
從表4中可以看出，四種方法均可以很好地對Image1進行分割。從Clustering Error指標以及圖3的結果均可以看出，方法獲得結果要比其他三種方法更好。
針對Image2的分割結果，本發明的方法獲得的平均Cluster Error指標要遠小於GAC、IEA和KM方法，從圖5以及表4中可以看出，對Image2這幅圖像，採用本發明方法獲得的結果要遠好於GAC和KM的結果，並且QWC方法的結果要好於IEA的結果。因此本發明針對Image2獲得了最優結果。
針對更加複雜的紋理圖像Image3進行分割時，從表4中可以很直觀地看出本發明方法所得到的平均Cluster Error指標要小於其他三種方法。從圖6可以看出，採用本發明得到的分割結果圖(c)，雜點明顯減少，區域一致性優於圖(d)，(e)，(f) QWC方法對於兩類紋理的分割結果要好於其他三種方法，這主要歸功於採用了分水嶺算法實現分塊處理，以及量子進化聚類算法更好地搜索到聚類中心，這大大提高了方法實現圖像分割效果的能力。
從表4及圖3～圖6對比結果可以明顯看出，對於三幅人工紋理圖像的分割結果具有更低的分割誤差率，雜點較少，紋理的一致性要明顯優於其它三種方法，因此本發明方法對人工紋理圖像具有更好的分割效果。
(2)遙感圖像紋理分割的仿真結果 第一幅如圖7(a)所示，為一幅美國新墨西哥州中部Rio Grande River的Ku波段SAR圖像，圖像大小為256×256，圖7(a)顯示圖像具有三個區域，分別為河流、植被和莊稼。圖7(b)給出了7(a)採用分水嶺算法後的初始分割圖像。圖7(c)～(f)分別給出了基於QWC、GAC、IEA和KM四種方法針對圖7(a)的分割結果。圖8(a)的分割結果則分別在圖8(c)～(f)中給出。第二幅圖像是一幅256×256大小的X-SAR子圖像，其解析度為5cm。圖8(a)顯示圖像具有四個區域，河流，城區以及兩類農作物。圖8(b)給出了8(a)採用分水嶺算法後的初始分割圖像。圖8(c)～(f)分別給出了基於QWC、GAC、IEA和KM四種方法針對圖8(a)的分割結果。
從圖7中可以看出基於分水嶺量子進化聚類的和IEA方法產生的分割結果要好於GAC和KM方法。然而，四種方法均可以對河流區域進行很好的劃分。在區分植被和莊稼時，IEA，GAC和KM方法在分割結果的連續性與區域一致性上遠遠不如QWC方法。GAC和IEA以及KM方法更易於將沿著河流的莊稼和植被錯分，同時將莊稼區域進行了過分割。
從圖8中可以看出，四種方法均能夠對X波段的SAR圖像的河流，城區以及兩類農作物四類目標分別開來。圖8(d)、(e)和(f)顯示GAC和IEA和KM方法將許多作物區域錯誤分為河流。圖8(c)顯示方法可以很好地識別這些區域，該方法可以明顯地降低這種誤識別概率。同時其他三種方法對原圖像的一致性都造成了很大程度的破壞，在確定圖像分割性能兩個重要因素——圖像一致性與圖像邊緣保持，本發明方法能夠輸出更好的劃分效果。
從圖7，圖8的分割結果中可以明顯看出本發明方法對於複雜的SAR圖像，相比於其它方法具有更好的區域一致性，區域邊緣劃分準確，分割效果圖中雜點明顯少於其它幾種方法。
權利要求
1.一種基於分水嶺-量子進化聚類算法的圖像分割方法，包括以下過程
(1)輸入待分割圖像，按照分水嶺算法對圖像進行分塊處理；
(2)對分塊後圖像的每個像素點提取離散小波能量特徵，進而求得區域塊特徵，將該特徵作為聚類數據集；
(3).設置抗體規模n、類別數k和停機條件，隨機產生初始量子染色體Q(t)作為聚類數據集的初始聚類中心，其中的αit，βit(i＝1，2…m)和所有的qjt都以等概率
初始化；
(4).將初始量子染色體Q(t)觀測成為二進位染色體p(t)；
(5).計算每個觀測後的二進位染色體p(t)與聚類數據集的親和度函數fk，保留當前種群中的最優個體；
(6)將初始量子染色體Q(t)進行量子變異操作，得到量子種群Qm(t)；
(7)將的量子種群Qm(t)進行量子交叉操作，得到新的量子種群Qc(t)作為新的聚類中心；
(8)將新的量子種群Qc(t)觀測成為二進位染色體pc(t)，計算每個染色體與聚類數據集的適應度函數值fc；
(9)對pc(t)進行選擇操作，得到子代染色體p(t+1)；
(10)判斷子代染色體是否滿足停機條件，如果滿足該條件就將子代染色體中親和度最高的染色體對應的圖像類屬劃分作為輸出結果，否則返回過程(4)，循環執行過程(4)～(10)，直到滿足停止條件。
2.根據權利要求1所述的圖像分割方法，其中過程(1)所說的按照分水嶺算法對待分割圖像進行分塊處理，具體過程如下
2a)將待分割圖像簡化；
2b)計算簡化後圖像的形態梯度圖像；
2c)計算梯度圖像的浮點活動圖像；
2d)將浮點活動圖像輸入分水嶺算法產生過分割結果。
3.根據權利要求1所述的圖像分割方法，其中過程(2)所說的求得區域塊特徵，是先求得待分割圖像的離散小波能量的紋理特徵，然後將圖像分塊後所得到的所有不規則塊的紋理特徵的均值作為該不規則塊的特徵。
4.根據權利要求1所述的圖像分割方法，其中過程(3)所說的隨機產生初始量子染色體Q(t)作為聚類數據集的初始聚類中心，其過程是用一對複數定義一個量子比特位，該量子比特位的狀態取0或1，其狀態表示為|Ψ>＝α|0>+β|1>，其中α，β為代表相應狀態出現概率的兩個複數，量子比特處於狀態0和狀態1的概率分別是|α|2，|β|2，並且|αi|2+|βi|2＝1(i＝1，2，…，m)。
5.根據權利要求1所述的圖像分割方法，其中過程(6)所說的將初始量子染色體Q(t)進行變異操作，是通過量子門變換矩陣實現量子染色體各個狀態間的轉移。
6.根據權利要求1所述的圖像分割方法，其中過程(7)所涉及的量子染色體Qm(t)進行量子交叉操作，是通過使用量子的相干特性構造全乾擾交叉操作，該操作採用對角線交叉的方式，使得種群中的所有染色體均參與交叉。
7.根據權利要求1所述的圖像分割方法，其中過程(9)所說的將對pc(t)進行選擇操作，採是用精英選擇策略，即在進化過程中，如果某一代中的最優解的適應度函數值優於當前代最優解的適應度函數值，則當前代最優解就被該最優解所代替，以保證在進化過程中每一代的最優解都不會丟失。
8根據權利要求1所述的圖像分割方法，其中過程(3)所說的設置停機條件，是通過兩個參數共同控制的，一個是第t代與t+1代染色體中最大適應度值改變量的閾值範圍ε，另外一個是第t代與t+1代染色體中最大適應度值連續無改進的次數n。
9根據權利要求1所述的圖像分割方法，其中過程(10)所說的判斷子代染色體p(t+1)是否停機條件，是判斷第t代與t+1代染色體中最大適應度值之差是否大於已設定的閾值範圍ε，如果不大於已設定的閾值範圍，就稱為最佳適應度改變量1次不變；如此反覆迭代，直到滿足n次不大於已設定的閾值範圍，就將該染色體中親和度最高的染色體體對應的圖像類屬劃分作為輸出結果。
全文摘要
本發明公開一種基於分水嶺-量子進化聚類算法的圖像分割方法。其過程為(1)分塊處理輸入的待分割圖像，求其區域塊特徵作為聚類數據集(2)設置種群規模、類別數k及停機條件，隨機產生初始量子染色體Q(t)作為初始聚類中心；(3)將Q(t)觀測成為二進位染色體p(t)，計算每個染色體的適應度函數值fk，保留當前群體中的個體；(4)對Q(t)進行變異操作得到Qm(t)；(5)量子交叉Qm(t)得到Qc(t)；(6)將Qc(t)觀測成為二進位染色體pc(t)，計算每個染色體的適應度函數值fc；(7)選擇操作pc(t)，得到子代染色體；(8)判斷子代染色體的停機條件，若滿足就將子代染色體中親和度最高的染色體對應的圖像類屬劃分作為輸出結果，否則返回過程(3)。本發明具有區域一致性好，邊緣保持準確的優點，可用於圖像處理領域中的目標識別。
文檔編號G06T5/00GK101625755SQ20091002351
公開日2010年1月13日 申請日期2009年8月6日 優先權日2009年8月6日
發明者李陽陽, 石洪竺, 焦李成, 芳 劉, 馬文萍, 尚榮華, 公茂果, 吳建設 申請人:西安電子科技大學