本文選題：Morse理論 + 三角網格　； 參考：《中國礦業(yè)大學(北京)》2016年博士論文

【摘要】：現代空間數據采集技術,特別是激光雷達技術(Light Detection and Ranging,LiDAR)能夠在短時間內獲取海量的空間模型表面離散數據。但是,當我們面對越來越大的數據量,僅寄希望于提高計算機的運算速度、增大存儲空間已經不能滿足實際需求。選擇合適的數據表達方式,在最大程度保存信息的前提下對其進行簡潔、有效描述是目前亟待解決的問題之一。目前,在空間表面模型的表達方式中,傳統的幾何方法,如規(guī)則格網、等值線,特別是三角網格仍然占據主導位置,其能對空間表面模型的幾何信息進行精確表達且便于計算與分析,但其數據量大、冗余數據多、計算復雜,且不能揭示模型表面的拓撲形態(tài)信息。作為一種緊致而簡潔的模型表面拓撲表達方式,基于Morse理論拓撲表達能用少量特征點、特征線實現對空間模型表面突出特征的描述,且這些特征點符合歐拉公式,特征線或Morse(-Smale)復形能實現對模型表面的完全分割。因此,在三角網格上構建表面拓撲結構,實現模型幾何表達向拓撲表達的轉換,在計算機圖形學、地學、空間信息科學,影像醫(yī)學等領域得到越來越廣泛的關注。但是由于數據的不確定性及算法本身存在的缺陷,基于Morse理論提取的拓撲特征往往含有大量的“偽特征”,并形成對模型表面的“過剖分”問題。另外,受限于特征提取的精度,目前基于Morse理論的拓撲分析仍然停留在定性分析階段,其嚴重制約了拓撲表達在現實中的應用。因此,研究如何精確地識別出地形網格中的主要特征并建立多層次表達體系,對于數據的簡化、交互式分析與可視化表達等,以及拓撲表達的定量計算至關重要。為此,本文致力于基于Morse理論的三角網格拓撲特征精確提取與簡化研究,主要對海量三角網格構建、小尺度復雜地形以及三維表面模型拓撲特征提取及簡化等所涉及的相關算法與關鍵技術進行了較深入的探討。主要工作與成果如下:1)基礎理論、現有研究成果及現存問題的梳理與總結介紹了本研究的理論依據經典Morse理論及關鍵點、關鍵線、Morse(-Smale)復形、持續(xù)值(Persistence)、拓撲簡化等相關概念及它們之間的關系。根據現實應用需求,引出了經典Morse理論的兩種離散化形式:離散Morse理論與分段線性Morse理論,其中對本研究利用的分段線性Morse理論進行了較為詳細的闡述。在此基礎上,深入分析了基于Morse理論的拓撲特征提取及簡化研究進展,主要包括:特征點提取、關鍵線或Morse(-Smale)復形提取、拓撲簡化。并總結歸納出目前研究成果存在的主要問題。最后,引出本文研究的主要內容及技術路線。2)提出了一種海量三角網格切塊剖分算法三角網格是實現拓撲提取與表達的基礎。為解決海量LiDAR點云三角網構建時時間與空間性能的矛盾問題,并針對基于三角網格分塊構建表面拓撲形態(tài)模型的需要,提出一種三角網切塊剖分算法。首先,利用基于格網的動態(tài)三角網生長算法構建分割墻(dewall),從點云上切割特定大小與形狀的獨立數據塊,避免分治算法的深度遞歸與內存溢出;然后,運用分治算法對切塊剖分,并給出了切塊邊界錯誤三角形刪除算法;迭代上述過程完成三角網子網剖分,并依據非耦合區(qū)域分解模式的性質完成子網合并,同時引入流計算的思想,以進一步提高算法的空間性能。對算法的時間與空間性能進行了理論分析并進行了系統的實驗驗證,實驗與分析表明:①運用切塊策略避免了分治算法的深度遞歸與內存溢出,同時通過模擬流計算,算法獲得了處理較大數據所需的優(yōu)異空間性能。②算法不但保證了各切塊剖分時具有分治算法的時間性能,并且算法的整體時間復雜度接近為o(nlog(δ)),優(yōu)于非線性的分治算法,適合千萬級以上lidar點云的處理。③算法最終構建的三角網為各子網簡單相加的和,并且本算法中各子三角網之間的非耦合性質,為lidar點云分塊進行拓撲特征的提取、表達與分析提供了數據結構支撐。3)設計與實現了小尺度地形拓撲特征的簡化與精確提取算法morse理論是基于光滑流形提出的,目前基于morse理論的拓撲表達仍然停留在定性分析上,且使用的數據源多為大尺度或較為光滑的空間模型表面數據。lidar點云為小尺度地表形態(tài)信息的提取、表達提供了精確的數據源,并使拓撲表達由定性分析擴展到定量計算成為可能。但點云的高密度性與地形的分形特征,導致基于morse理論提取的特征點中含有大量的“偽特征”,并形成對地表的“過剖分”問題。為此,針對現有特征點重要性度量方法的片面性,基于三角形網格結構,首先通過定義特征點指數(fpi)等一系列概念,模擬特征點周圍區(qū)域的地表形態(tài),建立特征點重要性度量指標。并以此為基礎,提出了地表重要特征點的精確提取、拓撲結構簡化與多層次表達算法。fpi不僅能準確度量小尺度復雜地表特征點的重要性,并且特征點數量在fpi值各段分布比較均勻,便于建立拓撲特征的多層次表達體系。基于fpi的特征提取與簡化算法在簡化效果方面優(yōu)于現有的“持續(xù)值(persistence)”法與自然法則法,其不僅可以有效剔除“偽特征點”,實現小尺度復雜地形的特征精確提取與多層次表達,且算法具有良好的重復性、抗噪性與魯棒性。并且特征點的提取精度小于2倍點間距,能夠滿足一定精度要求的定量計算�；谔岢龅囊幌盗刑卣鼽c重要性評價指標,并提出特征點尺度的概念,通過計算不同三角網格上特征點之間的相似系數,實現了基于三角網格的特征點識別與同名點匹配。4)擴展了一種三維表面模型拓撲特征提取與簡化新方法基于分段線性Morse函數的特征提取算法在由二維地表擴展到三維表面模型時,三角網格頂點的顯著度度量指標由高程值變?yōu)榍手怠⒎ㄏ蛄扛淖冎档软旤c屬性�；谶@些屬性提取的極大點、上升線與下降Morse復形為模型表面的顯著特征,而對應的極小點、下降線與上升Morse復形均為無實際意義的錯誤特征。這不但降低了拓撲特征提取的時間效率,且無實際意義的錯誤特征將導致拓撲簡化誤差甚至錯誤。為此,本文首先提出一種基于三角網頂點法向量的特征點顯著度度量方法,發(fā)展了以法向量變化量為點顯著度度量指標的三維表面模型特征提取算法,該算法僅提取有現實意義的三維模型表面拓撲特征。然后基于“關鍵線持續(xù)值(Separatrix Persistence)”度量方法與對偶性Morse-Smale復形拓撲簡化算法,推導了僅有下降Morse復形的單復形拓撲模型的拓撲簡化算法。新的提取算法能有效識別與提取三維模型表面的拓撲特征,避免沒有現實意義的拓撲特征的提取,大幅提高拓撲特征提取的效率。擴展的簡化算法不但可以解決三維模型表面拓撲劃分的“過剖分”問題,并且可以保持下降Morse復形的拓撲完整性,實現對三維模型表面的完全劃分及拓撲特征的多層次表達。5)設計并開發(fā)了“基于Morse理論的三角網格拓撲特征提取及簡化”實驗原型系統采用C++語言,在Visual Studio2008集成環(huán)境下,選用開源的圖形開發(fā)庫OSG和微軟基礎類庫MFC作為框架,將本文研究的有關算法與關鍵技術集成為原型系統。實驗系統的主要功能包括:本研究所提出的各種算法和相關技術的實現、驗證與分析;特征數量、誤差分析等統計計算;離散點云的導入和拓撲模型的輸出等。同時對實驗系統中算法采用的關鍵數據結構作了較為詳細的介紹。通過典型數據對實驗系統及其有關算法的可行性、合理性、正確性和有效性進行了實驗驗證與分析。
[Abstract]:......
【學位授予單位】：中國礦業(yè)大學(北京)
【學位級別】：博士
【學位授予年份】：2016
【分類號】：TP391.41

【參考文獻】

相關期刊論文 前10條

1 張春亢;趙學勝;王洪斌;;采用Morse理論的小尺度地形特征提取方法[J];測繪科學技術學報;2015年03期

2 湯國安;;我國數字高程模型與數字地形分析研究進展[J];地理學報;2014年09期

3 曹秉萬;趙大偉;陳建軍;黃爭舸;鄭耀;;面向組合參數曲面擴展B-rep的特征簡化和網格生成算法[J];計算機輔助設計與圖形學學報;2014年01期

4 王洪斌;朱新穎;張春亢;;基于自然法則的地表拓撲簡化[J];測繪科學技術學報;2013年06期

5 張堯;樊紅;李玉娥;;一種基于等高線的地形特征線提取方法[J];測繪學報;2013年04期

6 陳璋雯;達飛鵬;;基于模糊熵迭代的三維點云精簡算法[J];光學學報;2013年08期

7 李堅;李德仁;邵振峰;;一種并行計算的流數據Delaunay構網算法[J];武漢大學學報(信息科學版);2013年07期

8 王磊;聶玉峰;李義強;;Delaunay四面體網格并行生成算法研究進展[J];計算機輔助設計與圖形學學報;2011年06期

9 宋妍;田玉剛;賈小霞;;基于極大似然估計采樣一致性準則的遙感影像配準參數解算方法研究[J];測繪科學;2011年01期

10 吳文周;李利番;王結臣;;平面點集凸包Graham算法的改進[J];測繪科學;2010年06期

，

本文編號：1763344