非對(duì)偶性點(diǎn)云拓?fù)涮卣髯R(shí)別與過渡特征保護(hù)

張春亢，李紅梅，張 霞

(貴州大學(xué) 測繪工程教研室，貴州 貴陽 550025)

1 引 言

作為一種基礎(chǔ)算法與底層技術(shù)，三維點(diǎn)云特征提取與簡化在模型配準(zhǔn)[1]、模型重建[2]及信息識(shí)別[3]等方面得到了廣泛應(yīng)用。特征提取算法能否獲得正確真實(shí)可靠的特征，并保證特征的完整性與拓?fù)湟恢滦詫?duì)點(diǎn)云數(shù)據(jù)的后續(xù)處理及其應(yīng)用將產(chǎn)生巨大影響[4]。

因此，三維點(diǎn)云的特征提取與簡化一直是學(xué)者研究的重點(diǎn)，大量算法被提出，如基于鄰域信息[5-6]、曲面擬合[7-8]、聚類或區(qū)域分割[9-10]及數(shù)學(xué)模型[11-12]等的特征提取方法。這些特征提取常規(guī)算法對(duì)三維點(diǎn)云模型的輪廓線、棱線提取均取得了比較好的效果，但對(duì)于過渡特征線，或因?yàn)樘崛∵^程中過度強(qiáng)調(diào)特征線的閉合性而無法實(shí)現(xiàn)有效提取，或提取的特征線存在斷裂、散亂、不完整的現(xiàn)象，使得難以根據(jù)這些特征線對(duì)模型進(jìn)行區(qū)域分割或網(wǎng)格劃分[9-10]。此外，建立拓?fù)潢P(guān)系正確的三維模型一直是點(diǎn)云數(shù)據(jù)模型(如建筑物模型)重建的重點(diǎn)與難點(diǎn)[13]，現(xiàn)有算法在構(gòu)建特征線時(shí)建立并保證其正確的拓?fù)潢P(guān)系比較困難，也難以有效揭示點(diǎn)云模型表面的拓?fù)湫螒B(tài)。

Morse理論經(jīng)過微分拓?fù)鋵W(xué)驗(yàn)證，相比于目前主流的點(diǎn)云特征提取方法，是一種有嚴(yán)格數(shù)學(xué)理論基礎(chǔ)的表面拓?fù)涮卣鳂?gòu)建方法，基于其提取的Morse-Smale(MS)復(fù)形在理論上符合拓?fù)渫暾耘c一致性，提取的點(diǎn)云特征線不僅清晰、緊致、完整，能夠?qū)崿F(xiàn)對(duì)點(diǎn)云模型表面的完全分割，而且能在特征簡化過程中根據(jù)需要構(gòu)建特征的多層次表達(dá)體系，是對(duì)大規(guī)模科學(xué)數(shù)據(jù)進(jìn)行分析與可視化的強(qiáng)大工具[14]。根據(jù)特征重要性度量方法不同，目前基于Morse理論的特征識(shí)別算法主要有點(diǎn)持續(xù)值法[15]、線持續(xù)值法[16]和線-復(fù)形差值法[17-18]。文獻(xiàn)[15]基于Morse理論首先實(shí)現(xiàn)了三維模型MS復(fù)形的提取，然后以“持續(xù)值(persistence)”簡化理論與技術(shù)[4]為基礎(chǔ)，通過“同態(tài)收縮算法”[19]完成簡化，這種簡化方法實(shí)質(zhì)上是一種基于特征點(diǎn)度量指標(biāo)差值的方法；文獻(xiàn)[16]首先基于Morse理論實(shí)現(xiàn)了MS復(fù)形的提取，然后以“關(guān)鍵線持續(xù)值(separatrix persistence)”作為線的顯著度度量指標(biāo)完成簡化；文獻(xiàn)[17-18]首先通過網(wǎng)格度量指標(biāo)提取初始MS復(fù)形，然后根據(jù)特征線上的平均度量指標(biāo)值與其鄰接區(qū)域平均度量指標(biāo)值的差值對(duì)特征線進(jìn)行優(yōu)先排序，最后基于“同態(tài)收縮算法”完成拓?fù)浜喕瑢?shí)現(xiàn)模型主要特征的識(shí)別，該方法實(shí)質(zhì)是一種改進(jìn)的線持續(xù)值法。另外，文獻(xiàn)[20]利用MS復(fù)形四邊形的穩(wěn)定性，利用線-復(fù)形差值法對(duì)破損文物模型的拓?fù)涮卣鬟M(jìn)行了提取與簡化，然后運(yùn)用幾何拓?fù)鋱D形進(jìn)行搜索匹配，實(shí)現(xiàn)了文物模型的拼接；文獻(xiàn)[21]利用Morse理論標(biāo)定、提取出了點(diǎn)云模型的潛在特征點(diǎn)，避免了模型的局部曲面擬合或重建，但后期特征線的識(shí)別與提取仍然采用常用算法，沒有充分利用Morse理論提取特征線，提取的特征線不具有MS復(fù)形的特性，無法實(shí)現(xiàn)基于Morse理論的拓?fù)浜喕c多層次表達(dá)。

由于Morse理論是基于具有對(duì)偶性的二維標(biāo)量場提出的，基于其提取的MS復(fù)形也是一種適用于對(duì)偶性二維標(biāo)量場的拓?fù)鋽?shù)據(jù)結(jié)構(gòu)[22]，現(xiàn)有基于二維和三維點(diǎn)云的拓?fù)涮卣魈崛　⑻卣髦匾远攘考巴負(fù)涮卣骱喕彩腔贛S對(duì)偶性實(shí)現(xiàn)的。而以曲率、法向量改變量為度量指標(biāo)的三維點(diǎn)云模型是一種非對(duì)偶性模型，現(xiàn)有文獻(xiàn)在提取三維點(diǎn)云MS復(fù)形時(shí)，提取結(jié)果中含有大量無意義甚至錯(cuò)誤的特征，不利于點(diǎn)云數(shù)據(jù)的后續(xù)處理與應(yīng)用。另外，有研究與實(shí)驗(yàn)發(fā)現(xiàn)，基于Morse理論的拓?fù)涮卣魈崛∨c簡化是一種比較耗時(shí)的拓?fù)淠Ｐ蜆?gòu)建理論與算法[14]，無意義拓?fù)涮卣鞯奶崛∨c簡化額外消耗了大量不必要時(shí)間。

針對(duì)Morse理論由具有對(duì)偶性的二維標(biāo)量場推廣到非對(duì)偶性三維點(diǎn)云模型時(shí)遇到的問題，本文提出了單復(fù)形拓?fù)淠Ｐ停扑懔藛螐?fù)形模型特征線重要性度量方法和單復(fù)形拓?fù)淠Ｐ偷暮喕惴ǎ员苊鉄o意義特征的提取并提高時(shí)間效率。同時(shí)，針對(duì)模型過渡特征在簡化過程中難以保留的問題，提出了模型過渡特征保護(hù)方法，最后用典型的三維點(diǎn)云模型對(duì)本文模型與方法進(jìn)行了驗(yàn)證與分析。

2 單復(fù)形拓?fù)淠Ｐ吞崛?/h2>

2.1 問題與概念

對(duì)于一般的二維標(biāo)量場，如地形場[4]、溫度場[23]等，其度量指標(biāo)，如高程大小、溫度高低等是一個(gè)基于一定基準(zhǔn)(如高程基準(zhǔn)、絕對(duì)零度等)的宏觀概念，這種標(biāo)量場的特征是基于某一個(gè)參考面具有一定的對(duì)偶性，其基于Morse理論提取的MS復(fù)形也具有對(duì)偶性，提取的上升線對(duì)應(yīng)著標(biāo)量場的脊線(ridge)，提取的下降線對(duì)應(yīng)著標(biāo)量場的谷線(valley)，即提取的脊線和谷線與現(xiàn)實(shí)標(biāo)量場的形狀構(gòu)成相符，如圖1(a)所示的地形場及其MS復(fù)形。本文稱這種MS復(fù)形為對(duì)偶復(fù)形拓?fù)淠Ｐ汀?/p>

在三維點(diǎn)云模型特征提取過程中，曲率、法向量的變化等為常用的計(jì)算度量指標(biāo)，這些度量指標(biāo)是一種微觀概念，以其為度量指標(biāo)形成的場模型不具有基于某一參考面的對(duì)偶性。因此，采用這些度量指標(biāo)提取的MS復(fù)形也不具有對(duì)偶性，如圖1(b)所示，其基于Morse理論提取的三維表面模型的脊線包含模型的凸起輪廓線與棱線(如圖1(b)中的特征線pk2-sad3-pk3)和凹陷輪廓線與棱線(如圖1(b)中的特征線pk1-sad1-pk3)，它們構(gòu)成了三維點(diǎn)云模型的真實(shí)有價(jià)值特征，而提取的谷線(圖1(b)中的虛線)均是沒有實(shí)際意義甚至錯(cuò)誤的特征。因此，提取的脊線和谷線與現(xiàn)實(shí)三維表面模型的形狀構(gòu)成不相符，本文稱這種拓?fù)淠Ｐ蜑閱螐?fù)形拓?fù)淠Ｐ汀?/p>

圖1 二維與三維場模型及對(duì)應(yīng)MS復(fù)形Fig.1 2D and 3D scalar fields and corresponding MS complexes

因此，在將Morse理論由二維標(biāo)量場推廣到三維點(diǎn)云模型的應(yīng)用過程中，提取的MS復(fù)形會(huì)存在大量無意義的特征，這些特征不利于后續(xù)的數(shù)據(jù)處理與進(jìn)一步的應(yīng)用，如具有光滑平面的三維表面模型中，每個(gè)鞍點(diǎn)連接的兩個(gè)極小點(diǎn)的度量指標(biāo)值均接近為0，現(xiàn)有的基于“持續(xù)值(persistence)”的簡化操作，需要對(duì)對(duì)偶復(fù)形中的特征點(diǎn)進(jìn)行配對(duì)，這就造成了一定的配對(duì)困難。另外，作為一種非常耗時(shí)的拓?fù)涮卣鳂?gòu)建與簡化方法，沒有實(shí)際意義的拓?fù)涮卣鳂?gòu)建與簡化將消耗大量不必要的時(shí)間。

2.2 單復(fù)形提取

法向量是曲面的一階微分量，與曲面的二階微分量曲率比較，計(jì)算更簡單高效，本文選用點(diǎn)法向量的變化量作為點(diǎn)的度量指標(biāo)。

(1)特征點(diǎn)識(shí)別：在三角網(wǎng)模型中，對(duì)于頂點(diǎn)v，如圖2所示。若一階鄰點(diǎn)的度量指標(biāo)值均大于v點(diǎn)，則v是極小點(diǎn)；若一階鄰點(diǎn)的度量指標(biāo)值均小于v點(diǎn)，則v是極大點(diǎn)；在其與一階鄰點(diǎn)的逆(順)時(shí)針比較中，記度量指標(biāo)差正負(fù)符號(hào)的變化次數(shù)為CN，若CN為2，則頂點(diǎn)v是正則點(diǎn)；若CN為4，則頂點(diǎn)v是單鞍點(diǎn)，若CN大于4，則頂點(diǎn)v是多鞍點(diǎn)。

(2)單復(fù)形拓?fù)淠Ｐ蜆?gòu)建：在構(gòu)建基于Morse理論的單復(fù)形拓?fù)涮卣鲿r(shí)僅需要構(gòu)建脊線，而不需要構(gòu)建谷線。首先展開多鞍點(diǎn)，然后從鞍點(diǎn)出發(fā)，兩條特征線分別沿著度量指標(biāo)值增大的方向?qū)街钡綐O大值點(diǎn)(上升線)結(jié)束。對(duì)于上升線從鞍點(diǎn)到極大點(diǎn)的尋徑方式，目前有三種常用方法：最大鄰點(diǎn)法、最大角度法和梯度法，其中前兩種方法生成的特征線將沿著三角網(wǎng)的邊前進(jìn)；梯度法沿著三角形中真實(shí)梯度尋徑，該方法最接近真實(shí)情況，但會(huì)將三角形分割為兩部分，需要對(duì)現(xiàn)有三角形進(jìn)行分割，重新調(diào)整三角網(wǎng)及其拓?fù)潢P(guān)系，計(jì)算量大。如圖2所示，與點(diǎn)V比較，P3有更大的指標(biāo)值，P1與P2有更大的角度值，采用最大鄰點(diǎn)法尋找下一點(diǎn)為P3點(diǎn)，采用最大角度法為P1或P2，梯度法為P1P2之間的P0。本文采用最大鄰點(diǎn)法，若p點(diǎn)為v點(diǎn)的下一個(gè)尋徑點(diǎn)，其符合如下條件：

圖2 特征線尋徑方法Fig.2 Routing method by finding the next point

(1)

其中：pi為v的鄰點(diǎn)，n為點(diǎn)v的鄰點(diǎn)個(gè)數(shù)。

3 單復(fù)形模型拓?fù)浜喕茖?dǎo)

3.1 特征線重要性度量推算

基于Morse理論的拓?fù)涮卣魈崛∷惴ㄊ且环N敏感性較強(qiáng)的算法，在進(jìn)行模型特征提取時(shí)，其不但能識(shí)別出點(diǎn)云的主要特征與各層次過渡特征，而且會(huì)提取一定的噪聲，對(duì)于提取的單復(fù)形拓?fù)淠Ｐ停枰ㄟ^拓?fù)浜喕蕹Ｐ驮肼暎⒏鶕?jù)需要建立特征的多層次表達(dá)。

在進(jìn)行拓?fù)浜喕埃紫刃瓒攘客負(fù)涮卣髦匾裕瑢?duì)拓?fù)涮卣鞯闹匾赃M(jìn)行排序。在MS復(fù)形的拓?fù)浜喕^程中，目前研究的特征重要性度量方法有基于特征點(diǎn)[4,15]和基于特征線[16-18]兩種，在三維點(diǎn)云中，特征線往往比特征點(diǎn)更有價(jià)值，在MS復(fù)形中，定義每個(gè)鞍點(diǎn)連接的兩條升弧和兩條降弧分別為一條特征線, 作為特征重要性度量和操作的基本單元，即為l，文獻(xiàn)[18]“關(guān)鍵線持續(xù)值(separatrix persistence)”度量方法中，脊線和谷線的重要性為:

(2)

其中：pl(x)為特征線上一點(diǎn)x的度量指標(biāo)；max(f(mk))為與l上的鞍點(diǎn)連接的兩個(gè)極小點(diǎn)中的較大值；min(f(Mk))為與l上的鞍點(diǎn)連接的極大點(diǎn)中的較小值，其中，k=1,2。

在三維點(diǎn)云MS復(fù)形中，極小點(diǎn)度量指標(biāo)值趨近為0。因此，對(duì)于單復(fù)形拓?fù)淠Ｐ停?2)中對(duì)應(yīng)的脊線公式為:

pl(x)=f(x)-max(f(mk))≈f(x).

(3)

則單復(fù)形拓?fù)淠Ｐ吞卣骶€的重要性度量指標(biāo)RI可以定義為：

(4)

其中：n為特征線l上的特征點(diǎn)的數(shù)量。

基于特征線度量指標(biāo)的重要性度量方法有一定的片面性，例如，對(duì)于建筑物等棱角分明的接近方體的三維點(diǎn)云模型，由于其棱線度量指標(biāo)值相近、面接近為平面，其計(jì)算得到的特征重要性值大小接近，在簡化過程中，一些顯著度不強(qiáng)的主輪廓線特征被刪除，而顯著度強(qiáng)的細(xì)微特征甚至噪聲被保留。對(duì)于這類三維表面模型，研究聯(lián)合特征線度量指標(biāo)與復(fù)形面積的綜合性計(jì)算方法更有價(jià)值，定義聯(lián)合特征線度量指標(biāo)和復(fù)形面積的重要性計(jì)算方法為：

NRS=λ*NRI+(1-λ)*min(NSk)，

(5)

其中:NRI為特征線l的歸一化重要性度量指標(biāo)，min(NSk)為與特征線l關(guān)聯(lián)的兩個(gè)脊線圍成的復(fù)形C中面積較小復(fù)形的面積歸一化指數(shù)，其中，k=1,2。λ為權(quán)重。三維點(diǎn)云單復(fù)形拓?fù)淠Ｐ蜕刹捎米畲筻忺c(diǎn)法，特征線沿三角形邊尋徑, 則C的面積S近似為C內(nèi)所有三角形面積的和，即為：

(6)

其中，At為復(fù)形C中第t個(gè)三角形的面積。

3.2 拓?fù)浜喕茖?dǎo)

MS復(fù)形簡化的基礎(chǔ)是Pfaltz[19]提出的“同態(tài)收縮算法”，如圖3所示，對(duì)于簡化前的圖3(a)，極小點(diǎn)pt1與鞍點(diǎn)sad1是符合“持續(xù)值(persistence)”最小的一對(duì)臨界點(diǎn)，其被刪除的同時(shí)，與鞍點(diǎn)sad1關(guān)聯(lián)的脊線pk1-sad1-pk2被同步刪除，原來與極小點(diǎn)pt1連接的谷線直接連接到極小點(diǎn)pt2，如圖3(b)所示，簡化后的MS復(fù)形特征點(diǎn)仍然符合歐拉公式，特征線保持拓?fù)湟恢滦耘c完整性。該簡化過程建立在MS復(fù)形對(duì)偶性質(zhì)基礎(chǔ)上，在簡化過程中，具有對(duì)偶性的脊線或極大點(diǎn)與極小點(diǎn)或谷線均參與了計(jì)算。

圖3 對(duì)偶性SM復(fù)形同態(tài)收縮算法Fig.3 Homomorphic shrinkage algorithm of MS complex

本文提出的單復(fù)形拓?fù)淠Ｐ筒辉贊M足MS復(fù)形的對(duì)偶性，如圖4所示，在單復(fù)形拓?fù)淠Ｐ椭校ㄟ^對(duì)特征線的重要性度量排序，特征線pt1-sad1-pk2是需要?jiǎng)h除的特征線，在對(duì)其進(jìn)行刪除時(shí)，在對(duì)偶復(fù)性拓?fù)淠Ｐ椭校枰絼h除的還有鞍點(diǎn)sad1及與sad1連接且指標(biāo)差較小的極小點(diǎn)，其與sad1組成臨界點(diǎn)對(duì)。但在單復(fù)形模型構(gòu)建時(shí)沒有提取pt1，所以相當(dāng)于該點(diǎn)已經(jīng)被刪除了，結(jié)果如圖4(b)。因此，在簡化過程中保證了單復(fù)形拓?fù)淠Ｐ偷耐負(fù)湟恢滦耘c完整性。

圖4 單復(fù)形拓?fù)淠Ｐ秃喕疐ig.4 Simplification method of the single complex

4 過渡特征保護(hù)方法

根據(jù)Morse理論的關(guān)鍵線構(gòu)建方法，鞍點(diǎn)是特征線構(gòu)建的起始點(diǎn)和驅(qū)動(dòng)點(diǎn)，所有從鞍點(diǎn)出發(fā)的上升線，均沿指標(biāo)值增大的方向?qū)剑⒔Y(jié)束于極大點(diǎn)。部分位于非輪廓線或棱線上的鞍點(diǎn)構(gòu)建關(guān)鍵線時(shí)，結(jié)束于輪廓線或棱線的極大點(diǎn)上，其所構(gòu)造的關(guān)鍵線部分位于較光滑平面或曲面上，部分位于模型的輪廓線或棱線上(如圖5所示)。在利用基于特征線的重要性度量方法進(jìn)行特征重要性度量時(shí)，這類關(guān)鍵線的重要性度量指標(biāo)往往會(huì)大于過渡特征線重要性度量指標(biāo)，從而造成簡化過程中過渡特征被刪除，非特征線被保留的問題。

圖5 跨輪廓與非輪廓的關(guān)鍵線Fig.5 Critical lines crossing contours and surfaces

依據(jù)基于Morse理論的拓?fù)涮卣鳂?gòu)建與簡化理論，在構(gòu)建復(fù)形特征前刪除鞍點(diǎn)，不影響特征的拓?fù)渫暾院鸵恢滦浴?duì)于需要保留過渡特征的點(diǎn)云模型，按照下面特征提取與簡化步驟處理，實(shí)現(xiàn)對(duì)過渡特征的保護(hù)：

(1)基于Morse理論提取模型極大點(diǎn)和鞍點(diǎn)；

(2)設(shè)定閾值，刪除度量指標(biāo)小于閾值的鞍點(diǎn)，避免非特征線的構(gòu)建；

(3)設(shè)定閾值，依據(jù)“持續(xù)值(persistence)”簡化理論與技術(shù)，刪除度量指標(biāo)大于閾值的鞍點(diǎn)；

(4)基于刪除簡化后的模型特征點(diǎn)，構(gòu)建單復(fù)形拓?fù)淠Ｐ停?/p>

(5)計(jì)算特征線重要性度量，并設(shè)定閾值，對(duì)提取的復(fù)形進(jìn)行拓?fù)浜喕@取點(diǎn)云模型特定細(xì)節(jié)層次特征。

5 實(shí)驗(yàn)與分析

采用C++編程語言，在VS 2010上完成算法實(shí)驗(yàn)，標(biāo)準(zhǔn)PC平臺(tái)的配置為8 GB內(nèi)存、Intel(R) Core(TM) i7-7700HQ CPU @ 2.80 GHz處理器。

5.1 算法效率

實(shí)驗(yàn)數(shù)據(jù)為Gate點(diǎn)云模型，首先將其構(gòu)建成三角形，如圖6(a)，計(jì)算各個(gè)頂點(diǎn)的度量指標(biāo)值，如圖6(b)。提取了Gate模型的初始單復(fù)形拓?fù)淠Ｐ停鐖D6(d)，作為對(duì)比，根據(jù)文獻(xiàn)[17-18]提出的“線-復(fù)形差值法”提取了Gate模型的初始MS復(fù)形，如圖6(c)。單復(fù)形拓?fù)淠Ｐ筒坏R(shí)別出了模型的輪廓線、棱線，也識(shí)別出了模型的過渡特征和一些噪聲，而MS復(fù)形識(shí)別出單復(fù)形中有效特征的同時(shí)，提取出了大量無意義特征，圖6(c)中模型光滑區(qū)域存在大量特征線。由表1可知，基于Morse理論的拓?fù)涮卣鳂?gòu)建是一種非常耗時(shí)的特征提取方法，與文獻(xiàn)[17-18]提取點(diǎn)云模型初始MS復(fù)形比較，初始單復(fù)形拓?fù)淠Ｐ偷臉?gòu)建時(shí)間效率提高了52.22%，數(shù)據(jù)壓縮率提高了5.09%，且通過對(duì)模型進(jìn)行簡化可以獲取更高的數(shù)據(jù)壓縮率。

表1 Gate模型不同提取方法效率對(duì)比

圖6 Gate模型試驗(yàn)結(jié)果Fig.6 Results of Gate model

基于公式(4)計(jì)算的特征線重要性，利用推導(dǎo)的單復(fù)形拓?fù)浜喕惴ㄟM(jìn)行簡化，設(shè)定不同的閾值，逐步刪除噪聲和過渡特征，在RI=0.1時(shí)，簡化結(jié)果很好地保留了模型的輪廓線，并保持了拓?fù)涮卣鞯耐暾耘c一致性，如圖6(e)所示。但該算法是一種完全基于線度量指標(biāo)的簡化算法，簡化過程中刪除了一些指標(biāo)值不顯著的輪廓線特征，如建筑物圓柱曲面上的特征線，保留了重要性指標(biāo)值較大的細(xì)微特征。利用聯(lián)合特征線度量指標(biāo)與復(fù)形面積的綜合度量指標(biāo)對(duì)初始單復(fù)形模型進(jìn)行了簡化，如圖6(f)所示，其與圖6(e)具有大致相同的數(shù)據(jù)壓縮率，但提取的結(jié)果保留了更多的主輪廓線，如建筑圓柱曲面上的特征線，刪除了更多的細(xì)微特征。由于建筑物模型棱角分明，特征線度量指標(biāo)歸一化后，其值大部分趨近于1，復(fù)形面積歸一化后，其值符合正態(tài)分布，所以特征線度量指標(biāo)的權(quán)重設(shè)置較小，僅為0.2。

5.2 過渡特征保護(hù)

Fandisk點(diǎn)云模型的棱線特征具有漸變性，含有一定的過渡特征，是檢驗(yàn)特征提取算法的理想模型。文獻(xiàn)[17-18]提取的初始MS復(fù)形存在大量無意義的特征線，如圖7(a)，本文單復(fù)形拓?fù)淠Ｐ驮诒苊鉄o意義特征提取的同時(shí)，有效提取了模型的主輪廓線、各層次過渡特征和部分噪聲，如圖7(b)。對(duì)于圖7(b)，按照推導(dǎo)的關(guān)鍵線重要性度量方法進(jìn)行簡化，閾值為0.4時(shí)，結(jié)果如圖7(c)所示；對(duì)于圖7(a)，利用文獻(xiàn)[17]提出的“線-復(fù)形差值法”進(jìn)行簡化，結(jié)果如圖7(d)所示。圖7(c)～(d)結(jié)果顯示(彩圖見期刊電子版)，由于現(xiàn)有基于特征線指標(biāo)的重要性度量方法存在的問題，簡化過程中部分噪聲未被簡化刪除時(shí)，部分過渡特征被簡化刪除(圖7(c) ～ (d)藍(lán)圈部分)。文獻(xiàn)[10]為目前主流的三維點(diǎn)云特征提取常規(guī)算法，其提取結(jié)果如圖7(e)所示，其提取的特征線在過渡特征部分仍然存在一定程度的局部斷裂、不連續(xù)(圖7(e)藍(lán)圈部分)、或特征識(shí)別不完整(圖7(e)紅圈部分)的情況。利用本文提出的過渡特征保護(hù)處理方法進(jìn)行特征提取，結(jié)果如圖7(f)所示，本文過渡特征處理方法明顯改善了特征線在過渡特征部分的斷裂、不完整問題，對(duì)模型過渡特征的有效識(shí)別率達(dá)到了100%，起到了對(duì)過渡模型特征的保護(hù)作用，提取結(jié)果可實(shí)現(xiàn)對(duì)三維點(diǎn)云模型表面的完全分割，并可以通過設(shè)定簡化閾值提取不同層次的過渡特征。但由于現(xiàn)有的特征線重要性度量方法仍然存在一定的片面性，本文方法簡化后的模型存在少量噪聲特征線沒有被刪除。

圖7 不同方法特征提取效果對(duì)比Fig.7 Feature extraction results of different methods

5.3 其他實(shí)驗(yàn)?zāi)Ｐ?/h3>

圖8給出了其他模型實(shí)驗(yàn)結(jié)果，其中Bunny模型為更復(fù)雜的三維點(diǎn)云模型，且其輪廓線不突出鮮明，經(jīng)過復(fù)形提取與拓?fù)浜喕Ｐ偷闹鬏喞€得到了有效識(shí)別，用較小的數(shù)據(jù)量揭示模型的三維形狀特征與拓?fù)湫螒B(tài)，特征線的識(shí)別率達(dá)到了90%以上；Canstick模型和貴州大學(xué)專家樓模型為較為簡單的點(diǎn)云模型，其特征識(shí)別的完整率達(dá)到了100%，可以滿足模型三維重建等實(shí)際工程的需要。

圖8 其他模型實(shí)驗(yàn)Fig.8 Experiment of other models

6 結(jié) 論

更嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)理論基礎(chǔ)使Morse理論在三維點(diǎn)云拓?fù)涮卣魈崛∨c建模方面更有優(yōu)勢(shì)。針對(duì)三維點(diǎn)云模型非對(duì)偶性導(dǎo)致的拓?fù)涮卣魈崛∨c簡化問題，提出了單復(fù)形拓?fù)淠Ｐ吞崛『拖嚓P(guān)簡化算法，實(shí)驗(yàn)表明，新的提取方法避免了三維點(diǎn)云模型無意義特征的提取，比現(xiàn)有方法在時(shí)間效率上提高了52.22%，數(shù)據(jù)壓縮率提高了5%以上；過渡特征保護(hù)方法對(duì)點(diǎn)云模型過渡特征的識(shí)別率達(dá)到了100%，明顯改善了常規(guī)算法特征線在過渡特征部分的斷裂和不完整問題，為三維點(diǎn)云數(shù)據(jù)在模型重建、逆向工程、智能制造等方面的應(yīng)用提供了更精確可靠的模型基礎(chǔ)。

對(duì)于部分點(diǎn)云模型，采用目前的特征重要性度量方法進(jìn)行簡化，仍然難以刪除部分次要特征甚至噪聲。另外，特征線的簡化過程即是面與面之間的合并過程，現(xiàn)有特征重要性度量方法僅僅考慮了線或面本身的各種參數(shù)指標(biāo)，并未考慮模型結(jié)構(gòu)單元之間的相對(duì)空間關(guān)系，導(dǎo)致簡化時(shí)部分模型結(jié)構(gòu)單元之間的合并不符合實(shí)際(如建筑物立面與平面合并)。這些是下一步需要研究解決的問題。