[發明專利]用于圖形圖像的k近鄰局部搜索遺傳自動聚類方法

有效

• 申請號: 201210391449.6
• 申請日: 2012-10-15
• 公開（公告）號: CN102930291A
• 公開（公告）日: 2013-02-13
• 發明（設計）人: 劉若辰;史文博;焦李成;劉靜;馬文萍;張向榮;馬晶晶;王爽
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 王品華;朱紅星

1.一種用于圖形圖像的k近鄰局部搜索遺傳自動聚類方法，包括如下步驟：

（1）輸入待聚類的N幅圖像S_i,i＝1,…,N，利用canny算子分別對每幅圖像進行邊緣檢測，得到各幅待聚類圖像的輪廓圖像I_i；

（2）對各輪廓圖像I_i沿其輪廓線進行均勻采樣，并以笛卡爾坐標表示采樣得到的輪廓點P_ij=(x_ij,y_ij),i＝1,…,N,j=1,…,M，其中，P_ij表示采樣得到的第i幅輪廓圖像的第j個點，x_ij,y_ij分別為輪廓點P_ij位置的橫縱坐標，M為采樣點的個數；

（3）計算待聚類的任意兩幅圖像間的距離；

（4）令進化代數t=0，初始化種群：

（4a）隨機產生ρ個大于等于2小于等于ζ的整數k_i,i＝1,…,ρ，作為ρ條染色體的聚類數，ρ=30為種群規模，ζ=15為最大聚類數；

（4b）對每條染色體隨機產生N個大于等于1小于等于k_i的整數c_j,j=1,…,N，作為該染色體的各個基因位B_j的值，組成該染色體H_i；

（5）計算所有染色體的適應度值f_i，找出適應度值最大的染色體作為當前最佳染色體H；

（6）根據所得到的染色體的適應度值f_i，用輪盤賭選擇法對所有染色體H_i進行選擇，選出要進行遺傳操作的中間代染色體H′_i；

（7）對得到的中間代染色體H′_i，以概率σ₁,σ₁∈[0,1]進行單點交叉操作；

（8）對經過單點交叉操作后所有中間代染色體H″_i，以概率σ₂,σ₂∈[0,1]進行單點變異操作；

（9）計算經過單點交叉操作后所有中間代染色體H″_i的適應度值f_i；

（10）對每條中間代染色體H″_i，產生一個隨機數r,r∈[0,1]，如果r<0.5，執行步驟（11），否則執行步驟（12）；

（11）對中間代染色體H″_i的每個基因位B_j，產生隨機數ψ，ψ≠c_j，1≤ψ≤k_i，k_i為中間代染色體H″_i的聚類數，c_j為基因位B_j的值，將基因位B_j的值c_j改為ψ，計算此時中間代染色體H″′_i的適應度值f′_i，并與改動前的中間代染色體適應度值f_i比較，若f′_i>f_i，則基因位B_j的值設置為ψ，執行步驟（13），否則基因位B_j的值設置為c_j，執行步驟（13）；

（12）對中間代染色體H″_i進行k近鄰局部搜索：

（12a）將中間代染色體H″_i的每個基因位B_j所對應的待聚類圖像S_j，與其它待聚類圖像S_l的距離d(S_j,S_l)從小到大進行排序；

（12b）從排好序的距離中，選取前K=5個距離所對應的待聚類圖像，作為K副最近鄰圖像S′_v；

（12c）對所選出的K副最近鄰圖像S′_v對應的基因位B_v，統計不同基因位值的個數，找到個數最多的基因位值τ，若τ=c_j，c_j為待聚類圖像S_j對應的基因位B_j的值，則執行步驟（13）；

（12d）將中間代染色體H″_i的基因位B_j的值改為τ，計算此時中間代染色體H″′_i的適應度值f″_i，將改變前中間代染色體H″_i的適應度值f_i，若f″_i>f_i，則基因位B_j的值設置為τ，否則基因位B_j的值設置為c_j；

（13）比較所有中間代染色體的適應度值f_i，找出適應度值最大的染色，將該染色體與當前最佳染色體H比較，若該染色體的適應度值大于當前最佳染色體H的適應度值，則將該染色體復制到當前最佳染色體H，若當前最佳染色體H的適應度值大于該染色體的適應度值，則將當前最佳染色體H復制到該染色體；

（14）對進化代數t值加1，此時若t小于最大進化代數T=100，則返回步驟（6），否則，將當前最佳染色體H的每一個基因位B_i的值c_i作基因位B_i所對應待聚類圖像S_i的類標，將所有類標相同的待聚類圖像分為一個類，輸出分類后的待聚類圖像和當前最佳染色體H的聚類數。