專利名稱：基于免疫稀疏譜聚類的圖像分割方法
技術領域：
本發明屬于圖像處理技術領域，涉及圖像分割，可用于對紋理圖像和SAR圖像進行目標檢測和目標識別。
背景技術：
聚類是指把一個沒有類別標記的樣本集按某種準則劃分成若干個子集或類別，使相似的樣本盡可能歸為一類，而不相似的樣本盡量劃分到不同的類中。聚類分析是多元統計分析的一種，也是非監督模式識別的一個重要分支。作為一種無監督分類方法，聚類分析已經被廣泛地應用于模式識別、數據挖掘、計算機視覺和模糊控制等許多領域。傳統的聚類算法，如k-means算法，EM算法等都是建立在凸球形的樣本空間上，但當樣本空間不為凸時，算法會陷入局部最優。
譜聚類方法能在任意形狀的樣本空間上聚類，且收斂于全局最優解。該算法具有實現簡單，與維數無關，以及全局尋優的良好特性，因此得到了越來越廣泛的應用。譜聚類方法僅僅考慮所有樣本的權值矩陣，也叫相似性矩陣，它將聚類問題轉化為無向圖劃分問題。但是，譜聚類方法需要計算一個wxw權值矩陣的主要特征向量，"是樣本個數。這對于大規模數據，計算量是相當大的，這也成為了譜聚類方法的瓶頸問題。
Fowlkes等人提出了基于Nystr6m逼近的譜聚類方法。該方法首先從所有樣本中隨機選取一個樣本子集作為代表求解特征問題，然后再將其特征向量擴展為整個樣本集合權值矩陣的特征向量。然而，選取結果對聚類影響很大，聚類結果
表現出不穩定性。2005年Marie Ouimet等人提出的貪婪譜聚類方法很好的解決了這個問題。貪婪譜聚類方法用貪婪選取替代隨機選取選出代表全部樣本的樣本子集，并用包括所選的和未選的所有樣本，來估計特征空間的協方差矩陣。這使得聚類結果的穩定性和準確率都大大提高。但是，與Nystr6m方法不同，貪婪譜聚類方法采用容差作為重要的輸入參數。容差實際上直接決定了選取樣本子集的大小。為了輸入合適的容差來控制選取個數，需要預先知道容差和選取個數之間的關系。這在實踐中無論是計算量上還是時間復雜度上都是有很大難度的。另一方面，即使找到了合適的容差，貪婪選取方式需要逐個依次計算用己選樣本逼近當前候選樣本的誤差，當樣本規模較大時，這個過程的計算量和時間花費很大，這就造成圖象分割的速度非常慢。
發明內容
本發明的目的在于克服上述已有問題的缺點，提出了 一種基于免疫稀疏譜聚類的圖像分割方法，以避免貪婪譜聚類方法中合適容差的選取和所有樣本誤差的依次計算，降低計算復雜度，加快圖像分割的速度。為實現上述目的，本發明的具體實現過程包括如下
(1) 使用灰度共生矩陣對所待分割的圖像進行特征提取；
(2) 將所得的特征數據歸一化到
之間，以去除數據間量級的影響；
(3) 對歸一化后的特征數據，使用免疫克隆選擇方法選出具有代表性的樣本子
集
3a)對歸一化后的數據采用實數編碼方式進行編碼；
3b)隨機生成初始種群J(A卜(4， 4,…，《)，將it初始化為0，其中4-(v^2,…v")， i = l，2,...，"，、是要選出的樣本點，m是種群大小，"是選取個數，A表示迭代的次數；
3C)對所生成的初始種群，按照下式計算每個抗體的親和度
其中，<formula>formula see original document page 5</formula>
^是所有選出樣本的均值，hl是樣本點V,，、之間的歐氏距離3d)根據求得的親和度按照下式計算每個抗體克隆的個數
<formula>formula see original document page 5</formula>
其中，/"《;c)表示大于;c的最小整數，"r是設定的克隆規模；克隆后的每個抗體變為40t)—4,W,…,人(州,z、1，2，…附，整個種群變為Y,"(",如,…乂(")；
3e)先隨機確定，個變異位置，其中，=|"，然后在變異概率/^下對變異位置的抗體進行高斯變異，比較變異后每個種群的抗體親和度，并將每個種群親和度最大的抗體取出，組成下一輪的初始值A(/t + l);3f)判斷最大親和度是否在連續三次迭代中是否有提高，如果沒有提高，則 從總樣本中隨機生成60%新的樣本子集，取代種群中親和度小的抗體，如果有提 高，就不進行操作；
3g)對原迭代次數A重新賦值為;k'，其中/fc、"l，并判斷A'是否超過設定的 最大迭代次數T，如果超過T，則輸出親和度最高的抗體作為最終選出的樣本子 集，如果沒超過T，返回步驟3c);
(4) 用貪婪譜嵌入方法對選出的樣本子集進行降維；
(5) 對降維后的數據進行k-means聚類，該聚類為圖像的最終分割結果。 本發明與現有的技術相比具有以下優點
1. 與Nystr6m譜聚類方法相比，本發明由于利用親和度關系選取樣本子集， 因此選取的樣本子集更有代表性，分割結果有明顯提高；
2. 與貪婪譜聚類方法相比， 一方面，本發明由于采用選取樣本子集個數為輸 入，避免了容差的選取，另一方面，本發明由于從整體上選取和優化樣本子集， 避免了在所有樣本上逐一進行誤差計算的過程，從而降低計算復雜度，加快圖像 分割速度。
圖1是本發明基于免疫稀疏譜聚類的圖像分割方法流程圖； 圖2是本發明中選取子集的主要操作子流程圖； 圖3是本發明應用于2分類(1)紋理圖像的分割結果圖； 圖4是本發明應用于2分類(2)紋理圖像的分割結果圖； 圖5是本發明應用于3分類紋理圖像的分割結果圖6是本發明應用于SAR1圖像的分割結果圖； 圖7是本發明應用于SAR2圖像的分割結果圖； 圖8是本發明應用于SAR3圖像的分割結果圖。
具體實施例方式
參照圖l，本發明的具體實施過程如下 步驟l.使用灰度共生矩陣對待分割圖像進行特征提取。 對待分割的圖象生成灰度共生矩陣AG")，其中S是樣本點X,和、.之間的距
離，0的取值為4個離散的方向0°， 45°， 90°， 135°，每個方向上取三個統計角二階矩，同質區，對比度，每個統計量按照以下公式進行計算
角二階矩<formula>formula see original document page 7</formula>
同質區:<formula>formula see original document page 7</formula>
對比度:<formula>formula see original document page 7</formula>
其中，W是樣本總數，/7G,力是灰度共生矩陣A^,。第/行第/列的元素。
在4個方向上分別計算上述統計量，得到特征數據v- (入,/2，...,/2)。
步驟2.對所提取的特征數據"(_/;，,/2,-,_/;2)進行歸一化處理以去除數據 間量級的影響
<formula>formula see original document page 7</formula>
其中，min(v)表示C/i,/2,…,/,2)之中的最小值，max(v)表示(人,/2，…,y;2)之
中的最大值，得到歸一化后的特征數據v-(/'L，/2',…，^')。
步驟3.對歸一化后的特征數據采用實數編碼方式進行編碼。
步驟4.隨機生成初始種群^(A:)^4，《…，4J，其中A:表示迭代的次數，
初始化為0， 4 =(w,v2,...v")， / = 1,2,...，"，、是要選出的樣本點，m是種群大小，w
是選取個數。
步驟5.對所生成的初始種群，按照下式計算每個抗體的親和度<formula>formula see original document page 7</formula>其中，<formula>formula see original document page 7</formula>
;是所有選出樣本的均值，kl是樣本點v,,"之間的歐氏距離。 步驟6.根據抗體的的親和度大小，依次進行克隆，變異，選擇操作c
參照圖2，本步驟的具體實現如下
6a)根據求得的親和度按照下式計算每個抗體克隆的個數《! = 7n
其中，/""x)表示大于x的最小整數，^是設定的克隆規模； 克隆后的每個抗體變為4詢={4^)，...,4#)}，/ = 1,2,. W ，整個種群變為
6b)對克隆后的抗體種群，先隨機確定,個變異位置，其中，=|"，然后在
變異概率p:下對變異位置的抗體進行高斯變異；
6c)比較變異后每個種群的抗體親和度，并將每個種群親和度最大的抗體
取出，組成下一輪的初始值A(;k + l);
步驟7.判斷最大親和度是否在連續三次迭代中有提高，如果沒有提高，則 從總樣本中隨機生成60%新的樣本子集，取代種群中親和度小的抗體，如果有提 高，就不進行操作。
步驟8.對原迭代次數*重新賦值為*'，其中*' = "1,并判斷V是否超過設 定的最大迭代次數T，如果超過T，則輸出親和度最高的抗體作為最終選出的樣 本子集，如果沒超過T，返回步驟5。
步驟9.用下式對選出的樣本子集", 進行降維-
V，Vi)
義a "1
其中v是待嵌入的坐標，A(v)是v降維后的第)fc維坐標，(tA，;u)是整個權值矩陣 Xd(v,，v》的第；t個特征值和特征向量，C/汰是K的第/個坐標，
&(V，V,) = eXp(J^)，其中CT是核參數。
步驟10.對降維后的數據進行k-means聚類，該聚類為圖像的最終分割結果<
本發明效果可以通過以下實驗進一步證實-1.實驗條件和內容
實驗仿真環境為MATLAB 7.0.4， Intel(R) Pentium(R) 4 CPU 32GHz, WindowXP Professional 。
實驗內容包括分別應用Nystr6m譜聚類方法，貪婪譜聚類方法和本發明三 種方法對紋理圖像和SAR圖像進行分割。實驗參數設置為Nystri3m譜聚類方 法隨機選取100個樣本點，貪婪譜聚類方法取得到100個樣本點時的容差，本 發明方法參數設置為，種群規模20，克隆規模為種群規模2.5倍，變異概率0.99， 終止條件為最大迭代次數100。另外，實驗中貪婪譜聚類方法的運行時間不包括 找出合適容差的時間。這在實際中節約了大量反復實驗的時間。
2.實驗結果
1)將Nystr6m譜聚類方法，貪婪譜聚類方法和本發明三種方法應用于2分類 紋理圖像和3分類紋理圖像的分割結果如圖3,圖4，圖5所示，其中圖3(a)，圖 4(a)，圖5(a)是原紋理圖像，圖3(b)，圖4(b)，圖5(b)是模板，圖3(c)，圖4(c)， 圖5(c)是Nystr6m譜聚類方法的分割結果，圖3(d)，圖4(d)，圖5(d)是貪婪譜聚 類方法的分割結果，圖3(e)，圖4(e)，圖5(e)是本發明的分割結果。
三種方法對紋理圖象分割的時間和準確率統計見表1，其中運行時間和準確 率分別用T和R表示。
表1三種方法對紋理圖像分割的時間和準確率統計
選取 個數Nystr6m譜聚類貪婪譜聚類本發明T(s)R(%)T(s)R(%)T(s)R(%)
2分類(l)1008.8299.5713526199.6212652799.62
2分類(2)1008.4153.4313722255.1012484866.07
3分類1008.3177.1214426594.3312707994.36
從圖3，圖4，圖5和表1可以看到， 一方面，本發明在區域一致性和錯誤 劃分上明顯優于Nystr6m譜聚類方法，這是由于本發明方法有針對性的選取子 集，選取的子集更有代表性；另一方面，本發明與貪婪譜聚類方法相比不需要找 出合適容差，并且時間花費有所減少，這是由于在選取過程采用免疫克隆選擇策 略，以選取個數為輸入，避免了容差的確定和每個樣本逼近誤差的計算。
2)將Nystr6m譜聚類方法，貪婪譜聚類方法和本發明三種方法應用于SAR 圖像的分割結果如圖6，圖7，圖8所示，其中圖6(a),圖7(a),圖8(a)是原SAR 圖像，圖6(b),圖7(b),圖8(b)是Nystr6m譜聚類方法的分割結果，圖6(c),圖7(c), 圖8(c)是貪婪譜聚類方法的分割結果，圖6(d),圖7(d)，圖8(d)是本發明的分割結
9果，三種方法對SAR圖像分割的時間統計見表2。
表2三利3方法對SAR圖像分割的時間統計
選取 個數Nystr6m譜聚類貪婪譜聚類本發明
運行時間(s)運行時間(s)運行時間(s)
SAR11008.60136389126657
SAR21008.92140621126132
SAR31008.90137076114688
從圖6，圖7，圖8和表2可以看到，本發明在區域一致性和錯誤劃分上明 顯優于Nystr6m譜聚類方法，這是由于本發明選取子集選取的樣本子集更有代表 性，從表2可以看到，本發明與貪婪譜聚類方法相比不需要找出合適容差，并且 時間花費有所減少，這是由于本發明以選取個數為輸入，避免了容差的確定和每 個樣本逼近誤差的計算。
以上實驗表明，本發明方法與Nystr3m譜聚類方法相比準確率有大幅度提 高，與貪婪譜聚類方法相比計算復雜度減小，加快圖像分割速度。
權利要求
1、一種基于免疫稀疏譜聚類的圖像分割方法，包括如下步驟(1)使用灰度共生矩陣對所待分割的圖像進行特征提取；(2)將所得的特征數據歸一化到
之間，以去除數據間量級的影響；(3)對歸一化后的特征數據，使用免疫克隆選擇方法選出具有代表性的樣本子集3a)對歸一化后的數據采用實數編碼方式進行編碼；3b)隨機生成初始種群A(k)＝(A1，A2，…，Am)，其中k表示迭代的次數，初始化為0，Ai＝(v1，v2，...vn)，i＝1，2，...，n，vi是要選出的樣本點，m是種群大小，n是選取個數，；3c)對所生成的初始種群，按照下式計算每個抗體的親和度f(Ai)＝s(Ai)×d(Ai)其中，<maths id="math0001" num="0001" ><math><![CDATA[ <mrow><mi>S</mi><mrow> <mo>(</mo> <msub><mi>A</mi><mi>i</mi> </msub> <mo>)</mo></mrow><mo>=</mo><msup> <mrow><mo>{</mo><munderover> <mi>Σ</mi> <mrow><mi>i</mi><mo>=</mo><mn>1</mn> </mrow> <mi>n</mi></munderover><msup> <mrow><mo>(</mo><msub> <mi>v</mi> <mi>i</mi></msub><mo>-</mo><mover> <mi>v</mi> <mo>‾</mo></mover><mo>)</mo> </mrow> <mn>2</mn></msup><mo>/</mo><mi>n</mi><mo>}</mo> </mrow> <mrow><mn>1</mn><mo>/</mo><mn>2</mn> </mrow></msup> </mrow>]]></math> id="icf0001" file="A2009100243740002C1.tif" wi="55" he="13" top= "116" left = "48" img-content="drawing" img-format="tif" orientation="portrait" inline="yes"/></maths><maths id="math0002" num="0002" ><math><![CDATA[ <mrow><mi>d</mi><mrow> <mo>(</mo> <msub><mi>A</mi><mi>i</mi> </msub> <mo>)</mo></mrow><mo>=</mo><munderover> <mi>Σ</mi> <mrow><mi>i</mi><mo>=</mo><mn>1</mn> </mrow> <mi>n</mi></munderover><munderover> <mi>Σ</mi> <mrow><mi>j</mi><mo>=</mo><mn>1</mn> </mrow> <mi>n</mi></munderover><mo>|</mo><mo>|</mo><msub> <mi>r</mi> <mi>ij</mi></msub><mo>|</mo><mo>|</mo> </mrow>]]></math> id="icf0002" file="A2009100243740002C2.tif" wi="34" he="10" top= "120" left = "109" img-content="drawing" img-format="tif" orientation="portrait" inline="yes"/></maths>v是所有選出樣本的均值，||rij||是樣本點vi，vj之間的歐氏距離；3d)根據求得的親和度按照下式計算每個抗體克隆的個數<maths id="math0003" num="0003" ><math><![CDATA[ <mrow><msub> <mi>q</mi> <mi>i</mi></msub><mo>=</mo><mi>Int</mi><mo>{</mo><msub> <mi>n</mi> <mi>c</mi></msub><mo>×</mo><mfrac> <mrow><mi>f</mi><mrow> <mo>(</mo> <msub><mi>A</mi><mi>i</mi> </msub> <mo>)</mo></mrow> </mrow> <mrow><munderover> <mi>Σ</mi> <mrow><mi>j</mi><mo>=</mo><mn>1</mn> </mrow> <mi>n</mi></munderover><mi>f</mi><mrow> <mo>(</mo> <msub><mi>A</mi><mi>j</mi> </msub> <mo>)</mo></mrow> </mrow></mfrac><mo>}</mo><mo>,</mo> </mrow>]]></math> id="icf0003" file="A2009100243740002C3.tif" wi="47" he="24" top= "150" left = "49" img-content="drawing" img-format="tif" orientation="portrait" inline="yes"/></maths>i＝1，2，...n其中，Int(x)表示大于x的最小整數，nc是設定的克隆規模；克隆后的每個抗體變為 id="icf0004" file="A2009100243740002C4.tif" wi="37" he="4" top= "183" left = "83" img-content="drawing" img-format="tif" orientation="portrait" inline="yes"/>i＝1，2，…m，整個種群變為Y(k)＝{A′1(k)，A′2(k)，…，A′m(k)}；3e)先隨機確定t個變異位置，其中 id="icf0005" file="A2009100243740002C5.tif" wi="11" he="6" top= "197" left = "101" img-content="drawing" img-format="tif" orientation="portrait" inline="yes"/>然后在變異概率pmi下對變異位置的抗體進行高斯變異，比較變異后每個種群的抗體親和度，并將每個種群親和度最大的抗體取出，組成下一輪的初始值A(k+1)；3f)判斷最大親和度是否在連續三次迭代中有提高，如果沒有提高，則從總樣本中隨機生成60％新的樣本子集，取代種群中親和度小的抗體，如果有提高，就不進行操作；3g)對原迭代次數k重新賦值為k′，其中k′＝k+1，并判斷k′是否超過設定的最大迭代次數T，如果超過T，則輸出親和度最高的抗體作為最終選出的樣本子集，如果沒超過T，返回步驟3c)；(4)用貪婪譜嵌入方法對選出的樣本子集進行降維；(5)對降維后的數據進行k-means聚類，該聚類為圖像的最終分割結果。
全文摘要
本發明公開了一種基于免疫稀疏譜聚類的圖像分割方法，主要解決譜聚類方法穩定性差和復雜度高的問題。其實現過程是(1)對待分割圖像提取特征；(2)對特征數據進行歸一化以去除數據間量級影響；(3)對歸一化后的特征數據，進行實屬編碼；(4)對編碼后的數據，隨機生成初始種群并進行親和度計算；(5)根據抗體的親和度大小進行克隆；(6)對克隆后的抗體種群進行高斯變異并選出親和度最高的抗體作為下一輪的輸入；(7)迭代設定的最大迭代次數，得到最終選出的樣本子集；(8)對選出的樣本子集進行貪婪譜降維，并對降維后的數據聚類，輸出最終的圖像分割結果。本發明與現有的技術相比具有不需要先驗知識，準確度高，計算復雜度低的優點，可用于目標檢測和目標識別。
文檔編號G01S7/02GK101673398SQ20091002437
公開日2010年3月17日 申請日期2009年10月16日 優先權日2009年10月16日
發明者吳建設, 雄 莊, 佳 張, 楊淑媛, 毛莎莎, 焦李成, 田小林, 緱水平, 樺 鐘 申請人:西安電子科技大學
專業數控銑床產品供應商
20年生產經驗，實力工廠，精工品質，質量有保障
