基于遺傳算法的圖形圖像自動聚類.pdf

1、現(xiàn)今社會，網(wǎng)絡技術的飛速發(fā)展，極大地促進了網(wǎng)絡資源的共享，同時也導致人們需要面對的信息海量增長。因此，如何從這些信息中準確快速地找到有效信息，成為人們不得不面對的一個問題。聚類作為數(shù)據(jù)挖掘的一種重要工具，能夠給出數(shù)據(jù)的分類劃分，具有廣泛的應用，已成為目前研究的熱點。在聚類問題的分析研究過程中，往往把聚類看作成一個優(yōu)化問題，并且可以用不同的優(yōu)化方法來解決聚類問題。
　　形狀是事物圖像的基本特征之一。在計算機視覺和圖像理解與解譯中，把

2、目標物體的形狀作為識別特征進行識別是一種重要的方法。實際上，從圖像庫中對相同物體進行識別，就是一種自動聚類問題。本文將遺傳算法用于圖像的聚類，對所給的形狀特征明顯的圖形圖像集用遺傳算法進行處理，劃分出一個個不同的類，并且類別的個數(shù)由算法給出。具體的工作包含以下內(nèi)容：
　?。?）Shape Context是一種用常用的形狀描述方法，它利用輪廓點與其余輪廓點間相對位置信息，計算輪廓點的近鄰點位置分布直方圖，描述形狀。用Shape Co

3、ntext方法表述圖像的輪廓特征，再經(jīng)過Programming Dynamic方法、Procrustes Analysis方法、Edit距離，計算得到圖像間的相似度矩陣。本章所介紹的圖像相似度計算的方法，將用于第三章和第四章中的聚類算法。
　?。?）使用遺傳算法對圖像進行聚類，并在交叉變異操作之后加入k近鄰局部搜索算法，使得種群進化的方向向著“類內(nèi)相似度小”的方向調(diào)整。以一定的概率對染色體進行變異，隨機選擇并改變?nèi)旧w的某一基因位

4、；以概率對染色體進行交叉，隨機選擇交叉位置，互換該位置之后的所有基因位，產(chǎn)生兩條新的染色體；然后進行局部搜索，在局部范圍內(nèi)搜尋更優(yōu)的解；采用輪盤賭的方式進行選擇，產(chǎn)生下一代種群。通過實驗對比，結果表明該算法在ARI和MS評價指標上具有優(yōu)勢，說明了該算法的良好性能。
　?。?）NSGA-II為經(jīng)典多目標聚類算之一，算法計算開銷小，收斂速度快并且有精英保留策略，將其與 Shape Context、Programming Dynamic

5、、Procrustes Analysis及 Edit距離等結合，對圖形圖像進行自動聚類。NSGA-II的染色體變異和交叉同遺傳算法相似，在交叉變異之后，對經(jīng)過非支配排序的染色體進行選擇，產(chǎn)生下一代種群。對測試圖像集進行測試，表明多目標在圖形圖像自動聚類中，較第三章的算法性能有所提高。
　　本課題得到國家自然科學基金(No.60803098)、國家教育部博士點基金(No.20070701022)、省自然科學基金(2010JM8030