基于Morse理論的三角網(wǎng)格特征提取及簡化研究

張春亢

貴州大學(xué)礦業(yè)學(xué)院，貴陽 550025

LiDAR等新技術(shù)能快速獲取海量模型表面離散數(shù)據(jù)，面對這些數(shù)據(jù)，僅通過提高計(jì)算機(jī)性能已不能滿足實(shí)際需求，選擇合適的數(shù)據(jù)表達(dá)方式，對其進(jìn)行簡潔、有效描述是亟待解決的問題。傳統(tǒng)的幾何方法，如三角網(wǎng)格等能對空間表面模型的幾何信息進(jìn)行精確表達(dá)且便于計(jì)算與分析，但其數(shù)據(jù)量大、冗余多、計(jì)算復(fù)雜。基于Morse理論建立的拓?fù)浔磉_(dá)，能用少量的數(shù)據(jù)實(shí)現(xiàn)對模型表面的描述，并揭示模型表面的拓?fù)湫螒B(tài)。本文基于Morse理論，對表面模型拓?fù)涮卣鞯臄?shù)據(jù)結(jié)構(gòu)基礎(chǔ)、拓?fù)涮卣魈崛∨c簡化的理論與方法等進(jìn)行了深入探討。主要內(nèi)容如下：

(1) 詳述了經(jīng)典Morse理論及關(guān)鍵點(diǎn)、關(guān)鍵線、Morse-Smale復(fù)形、拓?fù)浜喕认嚓P(guān)概念，引出了針對離散數(shù)據(jù)模型的經(jīng)典Morse理論的兩種離散化形式：離散Morse理論與分段線性Morse理論，并對分段線性Morse理論及其在地學(xué)中的應(yīng)用進(jìn)行了較為詳細(xì)的闡述。

(2) 三角網(wǎng)格是實(shí)現(xiàn)拓?fù)涮卣魈崛〉臄?shù)據(jù)結(jié)構(gòu)基礎(chǔ)，針對拓?fù)涮卣魈崛∨c簡化耗時(shí)長，而分塊處理可以有效提高效率的問題，研究了海量三角網(wǎng)格的非耦合剖分方法。首先利用動態(tài)三角網(wǎng)生長算法構(gòu)建分割墻(DeWall)，從點(diǎn)云上切割特定大小與形狀的獨(dú)立數(shù)據(jù)塊，避免分治算法的深度遞歸；然后用分治算法對切塊剖分，并給出了切塊邊界錯(cuò)誤三角形刪除算法；迭代上述過程完成三角網(wǎng)子網(wǎng)剖分，并依據(jù)非耦合區(qū)域分解模式完成子網(wǎng)合并；同時(shí)引入流計(jì)算的思想，進(jìn)一步提高算法的空間性能。試驗(yàn)表明：①算法獲得了優(yōu)異空間性能，且算法的整體時(shí)間復(fù)雜度約為O(nlog(δ))，接近線性；②算法構(gòu)建的各子三角網(wǎng)之間具有非耦合性質(zhì)，為分塊進(jìn)行拓?fù)涮卣魈幚硖峁┝怂惴ㄖ巍?/p>

(3) 研究了小尺度地形拓?fù)涮卣鞯木_提取與簡化算法。針對基于Morse理論提取的小尺度地形拓?fù)涮卣骱写罅俊皞翁卣鳌保⑿纬蓪Φ匦蔚摹斑^剖分”問題。首先通過定義特征點(diǎn)指數(shù)(FPI)等一系列概念，模擬特征點(diǎn)周圍區(qū)域的地表形態(tài)，建立了特征點(diǎn)重要性度量指標(biāo)。并以此為基礎(chǔ)，提出了地表特征的精確提取與多層次表達(dá)算法。新算法可以有效剔除“偽特征”，實(shí)現(xiàn)小尺度復(fù)雜地形拓?fù)涮卣骶_提取，且具有良好的抗噪性與穩(wěn)健性，優(yōu)于現(xiàn)有的Persistence法與自然法則法。

(4) 研究推導(dǎo)了三維表面模型拓?fù)涮卣魈崛∨c簡化方法。基于Morse理論的特征提取算法在由二維擴(kuò)展到三維表面模型時(shí)，提取的極大點(diǎn)與下降Morse復(fù)形為模型表面的有效特征，而極小點(diǎn)與上升Morse復(fù)形為無實(shí)際意義的錯(cuò)誤特征，這不但降低了特征提取效率，且易導(dǎo)致簡化誤差。為此，推導(dǎo)了三維表面模型拓?fù)涮卣鞯奶崛》椒ǎ瑢?shí)現(xiàn)了針對三維表面模型的單復(fù)形拓?fù)淠Ｐ吞崛　；趕eparatrix persistence度量方法與MS復(fù)形簡化算法，推導(dǎo)了單復(fù)形拓?fù)淠Ｐ偷暮喕椒āＴ囼?yàn)表明：單復(fù)形模型能有效識別三維模型表面的拓?fù)涮卣鳎苊忮e(cuò)誤特征的提取，提高了效率；單復(fù)形簡化方法可以有效去除“偽特征”，并且在簡化過程中保持了復(fù)形的完整性與一致性。

(5) 設(shè)計(jì)開發(fā)了“基于Morse理論的三角網(wǎng)格拓?fù)涮卣魈崛〖昂喕痹囼?yàn)系統(tǒng)，將論文研究的有關(guān)算法與模型集成為原型系統(tǒng)。通過典型數(shù)據(jù)對試驗(yàn)系統(tǒng)及相關(guān)算法與模型的可行性、正確性和有效性進(jìn)行了驗(yàn)證。