發(fā)布時間：2018-04-17 11:05

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

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

【參考文獻】

相關(guān)期刊論文 前10條

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

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

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

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

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

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

7 李堅;李德仁;邵振峰;;一種并行計算的流數(shù)據(jù)Delaunay構(gòu)網(wǎng)算法[J];武漢大學(xué)學(xué)報(信息科學(xué)版);2013年07期

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

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

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

，

本文編號：1763344