形狀特征描述及聚類算法研究.pdf

1、形狀識(shí)別與聚類是人工智能、數(shù)據(jù)檢索、計(jì)算機(jī)視覺和模式識(shí)別等領(lǐng)域的基礎(chǔ)性研究課題。該課題的研究方向主要是在無先驗(yàn)(已知)類別標(biāo)準(zhǔn)的條件下，以形狀的有關(guān)特征作為判斷依據(jù)，實(shí)現(xiàn)聚類。而相關(guān)特征的選取及其結(jié)構(gòu)分析，一直是形狀識(shí)別與聚類問題的重點(diǎn)和難點(diǎn)。近年來，通過提取形狀特征，以動(dòng)態(tài)規(guī)劃、譜圖理論、中軸變換、數(shù)據(jù)降維等為手段，研究形狀的結(jié)構(gòu)特征的方法，日益受到眾多學(xué)者的關(guān)注，成為相關(guān)研究領(lǐng)域的熱點(diǎn)。
　　 本文在形狀結(jié)構(gòu)特征提取、分析以

2、及形狀的識(shí)別和聚類方面做了較為系統(tǒng)的研究，主要研究內(nèi)容和創(chuàng)新之處有以下四個(gè)方面：
　　 1、提出一種基于編輯距離與動(dòng)態(tài)規(guī)劃的形狀識(shí)別與檢索算法。首先，利用中軸變換提取形狀的骨架特征；然后，將該骨架特征點(diǎn)以字符串的形式表示，利用編輯距離算法，比較字符串間的距離；最后，運(yùn)用動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)形狀的識(shí)別與檢索。該算法利用骨架特征，較好地處理了形狀的非剛體形變的問題。而從空間特征到字符串特征的轉(zhuǎn)換，則為解決特征比較問題提供了新的思路，同時(shí)也有

3、利于增強(qiáng)算法的魯棒性。比較實(shí)驗(yàn)說明該算法對(duì)非剛體形變有較好的識(shí)別效果。
　　 2、提出了一種基于譜圖理論的形狀描述、識(shí)別與聚類算法。該算法主要研究兩個(gè)方面的問題：(1)通過提取形狀的骨架特征點(diǎn)和圖譜分析，以特征值描述形狀的結(jié)構(gòu)特征；(2)運(yùn)用主成分分析，將上述特征值投影到低維空間中，利用該方法實(shí)現(xiàn)了形狀的聚類。算法以特征點(diǎn)間的空間關(guān)系和角度關(guān)系為基礎(chǔ)，綜合應(yīng)用各種結(jié)構(gòu)信息，增強(qiáng)了算法的魯棒性。針對(duì)公共數(shù)據(jù)集的仿真實(shí)驗(yàn)說明了該聚類

4、算法對(duì)具有較大形變的形狀仍有較好的聚類效果。
　　 3、提出了一種利用Laplace譜特征與多維尺度法相結(jié)合的形狀識(shí)別與聚類算法。首先，提取形狀的輪廓點(diǎn)作為特征點(diǎn)，并構(gòu)造Laplace矩陣；然后，以Laplace矩陣的特征值來刻畫圖的結(jié)構(gòu)信息；最后，利用多維尺度法，將由各類形狀的輪廓點(diǎn)構(gòu)成的序列圖投影至低維空間，在該空間內(nèi)分析形狀的分布情況，實(shí)現(xiàn)聚類。在上述算法中，形狀的特征由一組向量表示，向量的維數(shù)越大，越能充分地反映其結(jié)構(gòu)的

5、特征，但卻不利于聚類結(jié)果的比較。為了解決該問題，引入了數(shù)據(jù)降維的方法，實(shí)現(xiàn)了三維空間中形狀聚類結(jié)果的可視化。對(duì)比實(shí)驗(yàn)的結(jié)果說明了該算法有較好的聚類效果。
　　 4、提出一種將Laplace矩陣的譜與隨機(jī)游走模型相結(jié)合，用以表示圖結(jié)構(gòu)特征的形狀聚類算法。針對(duì)形狀的不同空間結(jié)構(gòu)特征，通過對(duì)輪廓點(diǎn)所構(gòu)完全圖的Laplace矩陣的特征值以及圖的隨機(jī)游走模型概率性質(zhì)的分析，建立了描述輪廓點(diǎn)空間結(jié)構(gòu)特征的數(shù)學(xué)模型。以此模型為基礎(chǔ)，定義狀態(tài)向