三維網(wǎng)格分割算法及應(yīng)用報(bào)告

西安郵電大學(xué)畢業(yè)設(shè)計(jì)（論文）開(kāi)題報(bào)告計(jì)算機(jī)院（系）計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)09級(jí)06班課題名稱(chēng)： 三維網(wǎng)格分割的算法及應(yīng)用學(xué)生姓名：于樂(lè)學(xué)號(hào):04091178指導(dǎo)教師：賈暉 報(bào)告日期： 本課題所涉及的問(wèn)題及應(yīng)用現(xiàn)狀綜述近年來(lái)，三維動(dòng)畫(huà)已經(jīng)成為一個(gè)熱門(mén)的研究課題，三維網(wǎng)格模型也出現(xiàn)在了許多行業(yè)中，成為一個(gè)不可分割的部分.三維模型的廣泛應(yīng)用，引發(fā)越來(lái)越多的人開(kāi)始關(guān)注三維模型的處理問(wèn)題，三維模型分割和骨架提取就是其中的重要研究方面.三維網(wǎng)格模型分割技術(shù)在很多領(lǐng)域得到了廣泛應(yīng)用，如建模，三維模型變形、網(wǎng)格簡(jiǎn)化、幾何傳輸?shù)确矫?三維骨架提取也是三維動(dòng)畫(huà)不可或缺的重要組成部分，已經(jīng)有許多網(wǎng)格分割算法被提出，如分水嶺算法，聚類(lèi)算法，區(qū)域增長(zhǎng)算法等等.三維網(wǎng)格模型應(yīng)經(jīng)越來(lái)越多的用于3D數(shù)字動(dòng)畫(huà)、虛擬現(xiàn)實(shí)、真實(shí)感造型等幾何處理領(lǐng)域，逐步代替了傳統(tǒng)的幾何模型，成為數(shù)字主流模型的主流模型。由此，網(wǎng)格分割研究細(xì)化到離散網(wǎng)格處理的各方面。三維網(wǎng)格分割有助于參數(shù)化、形狀匹配、紋理映射、多分辨率建模、網(wǎng)格編輯、模型、壓縮、動(dòng)畫(huà)等。本課題需要重點(diǎn)研究的關(guān)鍵問(wèn)題、解決的思路及實(shí)現(xiàn)預(yù)期日標(biāo)的可行性分析三維網(wǎng)格模型分割的算法有很多主要有如下幾個(gè)研究算法：分水嶺算法：分水嶺算法本身和曲率的類(lèi)型無(wú)關(guān)。算法首先計(jì)算每個(gè)頂點(diǎn)的曲率或者其他高度函數(shù)尋找每個(gè)局部最小值并賦予標(biāo)志。每一個(gè)最小值都作為網(wǎng)格模型的初始分割。然后開(kāi)始自下而上或者自上而下地合并分水嶺高度低于指定閾值的區(qū)域。有時(shí)平坦的部分會(huì)得到錯(cuò)誤的分割結(jié)果。要靠后處理過(guò)程解決過(guò)度分割問(wèn)題。三維網(wǎng)格模型被分割為若干簡(jiǎn)單的、無(wú)明確意義的平面或柱面屬于非有意義的分割區(qū)域增長(zhǎng)算法：對(duì)格網(wǎng)數(shù)據(jù)點(diǎn)逐格網(wǎng)單元掃描，當(dāng)找不到這樣的地物點(diǎn)時(shí)結(jié)束操作；把這個(gè)點(diǎn)同周?chē)?-鄰域點(diǎn)比較，若小于閾值，則合并到同一區(qū)域，并對(duì)合并的地物點(diǎn)賦予該區(qū)域的標(biāo)記；從新合并的地物點(diǎn)開(kāi)始，反復(fù)進(jìn)行上述的操作；反復(fù)進(jìn)行上述兩部的的操作，直到不能合并為止；返回最初的操作，尋找新區(qū)域出發(fā)點(diǎn)。K均值聚類(lèi)算法：K-均值聚類(lèi)算法的基本思想隨機(jī)選取K個(gè)點(diǎn)作為初始聚類(lèi)中心，計(jì)算各個(gè)樣本到聚類(lèi)中心的距離，把樣本歸到離它最近的那個(gè)聚類(lèi)中心所在的類(lèi)，對(duì)調(diào)整后的新類(lèi)計(jì)算新的聚類(lèi)中心。如果相鄰兩次的聚類(lèi)中心沒(méi)有任何變化說(shuō)明樣本調(diào)整結(jié)束，聚類(lèi)準(zhǔn)則函數(shù)已經(jīng)收斂。K-均值聚類(lèi)算法中重要的一步是初始聚類(lèi)中心的選取，一般是隨機(jī)選取待聚類(lèi)樣本集的K個(gè)樣本，聚類(lèi)的性能與初始聚類(lèi)中心的選取有關(guān)，聚類(lèi)的結(jié)果與樣本的位置有極大的相關(guān)性。一旦這K個(gè)樣本選取不合理，將會(huì)增加運(yùn)算的復(fù)雜程度，誤導(dǎo)聚類(lèi)過(guò)程，得到不合理的聚類(lèi)結(jié)果。通過(guò)粗糙集理論提供，K-均值聚類(lèi)所需要的初始類(lèi)的個(gè)數(shù)和均值，提高了聚類(lèi)的效率和分類(lèi)的精度基于拓?fù)浣Y(jié)構(gòu)圖的分割：定義掃掠面周長(zhǎng)在掃掠結(jié)點(diǎn)之間的積分為骨架樹(shù)中分支的面積并將此面積定義為幾何函數(shù)定義拓?fù)浜瘮?shù)為相鄰兩個(gè)掃掠面拓?fù)洳町惖姆?hào)函數(shù)。并定義了基于微分幾何和拓?fù)浜瘮?shù)的關(guān)鍵點(diǎn)。整個(gè)過(guò)程無(wú)需用戶(hù)干涉。三維網(wǎng)格分割算法還有很多種，以上是其中的其中普遍的算法，此處僅作此研究。預(yù)期結(jié)果：通過(guò)以上的幾種算法分割，能夠粗略的將三維立體結(jié)構(gòu)圖進(jìn)行分割，得到分割以后的圖像。完成本課題的工作方案完成本課題首先需要熟悉matlab的編程環(huán)境，通過(guò)查閱資料掌握各個(gè)算法的思想，通過(guò)編譯環(huán)境實(shí)現(xiàn)其功能。工作計(jì)劃如下：第一步：12-10-31---12-11-30查閱資料，熟悉開(kāi)發(fā)環(huán)境第二步：12-12-1---12-12-20熟悉matlab的應(yīng)用第三步：12-12-21---13-1-21概要設(shè)計(jì)系統(tǒng)功能第四步：13-1-22---13-2-23熟悉各個(gè)算法第五步：13-02-24---13-03-31算法性能分析后選擇合適算法進(jìn)行代碼實(shí)現(xiàn)第六步：13-04-1---13-4-30進(jìn)行算法的檢測(cè)第七步：13-05-1---13-05-15撰寫(xiě)論文答辯指