基于遺傳算法的圖形圖像自動(dòng)聚類.pdf

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

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

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

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

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