三維網(wǎng)格分割算法及應用報告

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