基于多尺度張量分解的點(diǎn)云結(jié)構(gòu)特征提取

林洪彬 劉 彬 張玉存

燕山大學(xué)河北省測(cè)試計(jì)量技術(shù)與儀器重點(diǎn)實(shí)驗(yàn)室，秦皇島，066004

0 引言

隨著三維掃描技術(shù)的發(fā)展與廣泛應(yīng)用，三維掃描點(diǎn)云數(shù)據(jù)處理技術(shù)的研究也日益興起。點(diǎn)云結(jié)構(gòu)特征提取作為點(diǎn)云消噪、曲面重建的基礎(chǔ)，成為三維幾何數(shù)據(jù)處理領(lǐng)域的重要研究方向之一［1］。相對(duì)于傳統(tǒng)的網(wǎng)格處理算法，直接點(diǎn)云處理算法無(wú)需進(jìn)行拓?fù)渲亟ǎ哂懈叩拇鎯?chǔ)和執(zhí)行效率，這使得該類算法越來(lái)越受到國(guó)內(nèi)外學(xué)者的青睞［2］。

目前，三維點(diǎn)云結(jié)構(gòu)特征提取方法可以分為基于法向特征提取、基于曲率特征提取和基于曲面擬合的特征提取三類。基于法向的采樣點(diǎn)特征提取算法可用于噪聲不大情況下特征曲線的快速、魯棒重建，對(duì)特征曲線內(nèi)部重建精度較高，但對(duì)孤立的頂點(diǎn)識(shí)別精度不高，容易造成重建曲線角特征的丟失［3－6］。基于曲率的采樣點(diǎn)特征提取算法利用曲率信息進(jìn)行特征點(diǎn)識(shí)別，進(jìn)而構(gòu)建對(duì)象的特征曲線［7－9］。該算法容易受到噪聲的干擾，所提取的特征點(diǎn)可能存在偽特征或特征點(diǎn)漏檢，故需要對(duì)提取的特征點(diǎn)進(jìn)行進(jìn)一步的篩選和處理，從而增加了算法的復(fù)雜性。基于曲面擬合的特征提取算法的關(guān)鍵在于閾值參數(shù)的選取，在三維數(shù)據(jù)存在噪聲的情況下，過(guò)大的閾值會(huì)降低算法的弱特征提取能力，過(guò)小的閾值會(huì)使得算法效率降低，同時(shí)也會(huì)引入過(guò)多偽特征，導(dǎo)致特征曲線提取精度降低［10－12］。總體而言，在三維點(diǎn)云結(jié)構(gòu)特征提取方面，國(guó)內(nèi)外學(xué)者主要致力于弱特征的有效提取和偽特征的有效剔除的研究。然而，僅通過(guò)采樣點(diǎn)法向、曲率等信息判定采樣點(diǎn)的特征屬性存在弱特征提取與偽特征剔除之間的矛盾［13］。為此，Guy等［14］基于張量投票理論，對(duì)噪聲環(huán)境下點(diǎn)云特征邊、角點(diǎn)和特征曲面提取問(wèn)題進(jìn)行了研究，為三維點(diǎn)云結(jié)構(gòu)特征提取的研究提供了良好的思路。

本文以張量分析理論為基礎(chǔ)，對(duì)采樣點(diǎn)特征進(jìn)行顯著性編碼，實(shí)現(xiàn)了采樣點(diǎn)特征的初步提取；為了解決尖銳區(qū)域與平滑區(qū)域特征提取的矛盾，提高特征提取的精度，通過(guò)法向一致性測(cè)度和切向一致性測(cè)度定義了采樣點(diǎn)最優(yōu)鄰域；在最優(yōu)鄰域內(nèi)對(duì)采樣點(diǎn)進(jìn)行多個(gè)尺度的張量分解，統(tǒng)計(jì)不同尺度下的顯著性編碼實(shí)現(xiàn)采樣點(diǎn)特征屬性的精確識(shí)別；利用羅曼諾夫斯基準(zhǔn)則檢測(cè)法向（切向）一致性測(cè)度突變，實(shí)現(xiàn)最優(yōu)鄰域的自動(dòng)選取；利用最小二乘森林進(jìn)行特征點(diǎn)遍歷，并通過(guò)將偽特征點(diǎn)向鄰近特征點(diǎn)圓弧進(jìn)行投影實(shí)現(xiàn)特征曲線平滑，實(shí)現(xiàn)點(diǎn)云結(jié)構(gòu)特征提取。

1 點(diǎn)云的張量分解

二階對(duì)稱張量在三維空間微分幾何結(jié)構(gòu)描述方面具有獨(dú)特的能力，本文基于Guy等［14］的研究成果，針對(duì)點(diǎn)云數(shù)據(jù)，基于二階對(duì)稱張量對(duì)幾何特征表達(dá)與特征點(diǎn)識(shí)別問(wèn)題進(jìn)行研究。通常三維空間中采樣點(diǎn)pi的二階對(duì)稱張量T可用半正定對(duì)稱矩陣表示為

式中，η（pi，n）為采樣 點(diǎn)pi的 鄰 域；n為 鄰 域 內(nèi) 采 樣 點(diǎn)個(gè)數(shù)。

根據(jù)矩陣奇異值分解理論，對(duì)張量矩陣T進(jìn)行奇異值分解：

式中，λ1、λ2、λ3為張量矩陣T的奇異值，λ1≥λ2≥λ3≥0；e1、e2、e3為λ1、λ2、λ3對(duì)應(yīng)的3個(gè)特征向量。

實(shí)質(zhì)上，利用張量矩陣T進(jìn)行點(diǎn)云局部幾何結(jié)構(gòu)描述，相當(dāng)于通過(guò)鄰域內(nèi)的采樣點(diǎn)擬合的橢球面進(jìn)行采樣幾何特性描述，該橢球的3個(gè)主方向由正交特征向量e1、e2、e3確定，各主方向橢球的半徑正比于相應(yīng)特征向量所對(duì)應(yīng)的奇異值。

將張量矩陣T表示為［14］

圖1為張量分解示意圖，當(dāng)λ2＝λ3＝0或λ2＝λ3≈0且λ1≠0時(shí)，采樣點(diǎn)pi為空間直線（曲線）上的點(diǎn)，且該空間直線（曲線）在pi點(diǎn)處的切向量為e1；當(dāng)λ1＝λ2≠0且λ3＝0或λ3≈0時(shí)，采樣點(diǎn)pi為空間平面（曲面）上的點(diǎn)，且該平面（曲面）在pi處的法向量為e3；當(dāng)λ1＝λ2＝λ3≠0時(shí)，采樣點(diǎn)pi為空間角點(diǎn)或孤立點(diǎn)。

2 基于張量分解的點(diǎn)云特征測(cè)度

圖1 張量分解示意圖

圖2 曲面點(diǎn)、曲線點(diǎn)、角點(diǎn)的主方向

由此，可以求取點(diǎn)云P中的任意采樣點(diǎn)pi的上述3個(gè)張量特征指標(biāo)，并且3個(gè)指標(biāo)中有且僅有一個(gè)為1，另外兩個(gè)為0，從而將采樣點(diǎn)劃入相應(yīng)的特征集合（曲線點(diǎn)集、曲面點(diǎn)集、角點(diǎn)集）。根據(jù)上述方法得到的特征集合是真實(shí)特征集合的父集，即真實(shí)特征點(diǎn)必屬于相應(yīng)的特征集合，但特征集合中的點(diǎn)不一定為真實(shí)特征點(diǎn)。

3 基于最優(yōu)鄰域張量分解的點(diǎn)云特征識(shí)別

3.1 鄰域?qū)μ卣鲗傩宰R(shí)別的影響

在點(diǎn)云特征屬性識(shí)別過(guò)程中，采樣點(diǎn)坐標(biāo)是唯一的可用信息，鄰域點(diǎn)是采樣點(diǎn)微分幾何屬性估計(jì)的直接依據(jù)。鄰域通常對(duì)分析結(jié)果具有較為明顯的影響。利用K鄰域?qū)andisk模型中各采樣點(diǎn)的平均曲率進(jìn)行估計(jì)，不同K值下平均曲率估計(jì)結(jié)果如圖3所示。鄰域越小（K＝20），模型中尖銳區(qū)域平均曲率估計(jì)越準(zhǔn)確，但算法的抗噪能力也越差，表現(xiàn)為平坦區(qū)域的平均曲率發(fā)生跳變；鄰域越大（K＝80），模型中平坦區(qū)域的平均曲率估計(jì)越準(zhǔn)確，表現(xiàn)為平坦區(qū)域的平均曲率跳變被平滑，但尖銳區(qū)域曲率被過(guò)度平滑（在對(duì)這些區(qū)域?qū)Σ蓸狱c(diǎn)特征進(jìn)行估計(jì)時(shí)，容易將不同曲面上的采樣點(diǎn)納入到鄰域之中，使原有特征被旁值點(diǎn)掩蓋）。因此，采用固定的K值對(duì)鄰域點(diǎn)數(shù)進(jìn)行約束，不可避免地存在高頻區(qū)域特征過(guò)度平滑與低頻區(qū)域抗噪聲能力差的矛盾。

圖3 鄰域點(diǎn)數(shù)不同時(shí)Fandisk模型平均曲率估計(jì)結(jié)果

3.2 利用最優(yōu)鄰域估計(jì)采樣點(diǎn)特征屬性

由上述分析可知，將全局一致的K作為鄰域點(diǎn)數(shù)容易導(dǎo)致高頻區(qū)域特征過(guò)度平滑與低頻區(qū)域抗噪聲能力差的矛盾，使得在進(jìn)行點(diǎn)云特征屬性識(shí)別時(shí)，算法抗噪聲能力差，弱特征提取能力不強(qiáng)。為此，針對(duì)采樣點(diǎn)各自的微分幾何特性，使高曲率區(qū)域的K小一些，低曲率區(qū)域的K大一些，即可解決全局一致的K造成的矛盾。為此，本文采用法向（切向）一致性測(cè)度進(jìn)行采樣點(diǎn)最優(yōu)鄰域估計(jì)，以提高采樣點(diǎn)特征屬性識(shí)別的可靠性。

采樣點(diǎn)的法向量屬于一階微分幾何量，容易受旁值點(diǎn)（不屬于原有光滑曲面上的點(diǎn)）的影響。當(dāng)逐漸增大鄰域點(diǎn)數(shù)n時(shí)，若所有鄰域點(diǎn)均屬于采樣點(diǎn)所在光滑平面或曲面，則估計(jì)所得的采樣點(diǎn)法向趨于一致或緩慢變化，一旦跨越特征的采樣點(diǎn)被納入到采樣點(diǎn)鄰域內(nèi)，采樣點(diǎn)法向?qū)l(fā)生突變。因此，將采樣點(diǎn)法向剛好發(fā)生突變前之的鄰域作為最優(yōu)鄰域，不僅可以盡量擴(kuò)大鄰域范圍，而且有效避免了將旁值點(diǎn)納入到鄰域之中。為此，本文構(gòu)建了法向一致性測(cè)度，以實(shí)現(xiàn)采樣點(diǎn)最優(yōu)鄰域的檢測(cè)。

利用峭度分析的突變值檢測(cè)能力，定義采樣點(diǎn)pi的法向一致性測(cè)度α（pi，n）如下：

為了驗(yàn)證法向一致性測(cè)度在最優(yōu)鄰域估計(jì)中的性能，以Fandisk模型中特征邊界附近的采樣點(diǎn)為對(duì)象進(jìn)行分析，結(jié)果如圖4所示。由圖4可見(jiàn)，當(dāng)K＜18時(shí)，鄰域點(diǎn)均位于采樣點(diǎn)所在的平面上，法向一致性較好，α（pi，n）≈0；隨著K的增大，跨特征點(diǎn)被納入到鄰域之中，法向發(fā)生突變，α（pi，n）也突然增大，說(shuō)明可以利用法向一致性測(cè)度進(jìn)行該類采樣點(diǎn)最優(yōu)鄰域的估計(jì)。

圖4 法向一致性測(cè)度隨尺度變化關(guān)系

圖5 角點(diǎn)、平面點(diǎn)和曲線點(diǎn)法向一致性測(cè)度隨尺度變化關(guān)系

對(duì)Fandisk模型中的角點(diǎn)、曲面點(diǎn)和曲線點(diǎn)的分析結(jié)果如圖5所示。由圖5可見(jiàn)，在1≤K≤100的范圍內(nèi)，曲面點(diǎn)的法向一致性測(cè)度函數(shù)值均趨于0，此時(shí)所有的鄰域點(diǎn)均位于該點(diǎn)所在的曲面上；從K＝4開(kāi)始，角點(diǎn)和曲線點(diǎn)的α（pi，n）值突然增大且劇烈波動(dòng)。這是由于角點(diǎn)和曲線點(diǎn)均位于曲面或曲線相交處，每次增加的鄰域點(diǎn)都有可能取自不同的曲面，使α（pi，n）發(fā)生較大變化。因而，法向一致性測(cè)度用于曲面點(diǎn)最優(yōu)鄰域求取時(shí)效果較好，而用于分析角點(diǎn)和曲線點(diǎn)的最優(yōu)鄰域時(shí)可靠性不高。

為了分析曲線點(diǎn)的最優(yōu)鄰域，利用最優(yōu)鄰域內(nèi)曲線點(diǎn)的切向不變特性，建立切向一致性測(cè)度：

3.3 利用最優(yōu)鄰域張量分解進(jìn)行點(diǎn)云特征屬性識(shí)別

在求取各采樣點(diǎn)最優(yōu)鄰域的基礎(chǔ)上，利用最優(yōu)鄰域點(diǎn)構(gòu)建采樣點(diǎn)張量矩陣，進(jìn)而通過(guò)張量顯著性編碼進(jìn)行采樣點(diǎn)特征屬性識(shí)別。由圖6可知，利用張量分量顯著性編碼不僅可以識(shí)別明顯的曲線點(diǎn)和角點(diǎn)，還可以識(shí)別特征不是很明顯的曲線特征點(diǎn)，這是由于所采用的法向（切向）一致性測(cè)度屬于一階微分算子，具有較好的突變檢測(cè)能力，但同時(shí)也導(dǎo)致算法的抗噪聲能力變差，如圖6中被誤判為曲線點(diǎn)的曲面點(diǎn)。最簡(jiǎn)單的處理方法是通過(guò)計(jì)算特定范圍內(nèi)特征點(diǎn)的個(gè)數(shù)來(lái)剔除這些誤檢點(diǎn)，但該方法僅適用于遠(yuǎn)離特征曲線的誤檢測(cè)點(diǎn)。為此，本文擬通過(guò)最優(yōu)鄰域范圍內(nèi)多尺度張量分解來(lái)提高采樣點(diǎn)特征屬性識(shí)別的可靠性。

圖6 最優(yōu)鄰域Fandisk模型特征識(shí)別計(jì)結(jié)果

4 利用多尺度張量分解進(jìn)行采樣點(diǎn)特征屬性的可靠識(shí)別

為了實(shí)現(xiàn)采樣點(diǎn)特征屬性的自動(dòng)識(shí)別，需要完成如下兩個(gè)方面的工作：①提高噪聲環(huán)境下特征點(diǎn)識(shí)別的可靠性；②在確保特征點(diǎn)識(shí)別可靠性的基礎(chǔ)上，保障算法的弱特征提取能力。為此，本文基于多尺度分析的思想，構(gòu)建多尺度張量特征指標(biāo)，以提高采樣點(diǎn)特征分析的可靠性。

4.1 點(diǎn)云的多尺度特征分析

多尺度分析兼具強(qiáng)大的全局分析和局部特征識(shí)別能力，在一維和二維信號(hào)處理中得到了廣泛的應(yīng)用。本文將多尺度分析與三維點(diǎn)云張量特征顯著性測(cè)度相結(jié)合，以解決特征識(shí)別測(cè)度函數(shù)抗噪性與弱特征提取之間的矛盾。

設(shè)三維點(diǎn)云P可表示為：f（x）：IR3→IR，其中，x為點(diǎn)云P中的任意采樣點(diǎn)，則該三維點(diǎn)云P在尺度t下的線性尺度空間L（x，t）：IR3×IR→IR可表示為卷積形式［4］：

式中，g（x，t）為高斯函數(shù)。

實(shí)質(zhì)上，上述過(guò)程相當(dāng)于用不同尺度參數(shù)t的高斯函數(shù)對(duì)點(diǎn)云進(jìn)行平滑，當(dāng)t＝0時(shí)，L（x，0）＝f（x）表示原始點(diǎn)云。尺度參數(shù)t越大，平滑作用越強(qiáng)，得到的點(diǎn)云就越光滑，越有利于提高噪聲環(huán)境下的特征點(diǎn)識(shí)別能力；t越小，平滑作用越不明顯，越有利于弱特征的提取。為簡(jiǎn)化計(jì)算過(guò)程，本文以采樣點(diǎn)鄰域點(diǎn)數(shù)為采樣點(diǎn)的分析尺度，通過(guò)分析最優(yōu)鄰域內(nèi)各尺度（鄰域點(diǎn)數(shù)）下的張量分解顯著性編碼，建立如下特征指標(biāo)：

式中，Ωcurve（pi）、Ωplane（pi）、Ωconner（pi）為多尺度張量特征指標(biāo)；N為采樣點(diǎn)pi最優(yōu)鄰域的點(diǎn)數(shù)。

通過(guò)不斷增加尺度參數(shù)（鄰域點(diǎn)數(shù)），并求取多尺度張量特征指標(biāo)，進(jìn)而通過(guò)多尺度張量特征指標(biāo)進(jìn)行采樣點(diǎn)的特征屬性判別，將大大提高噪聲環(huán)境下特征點(diǎn)識(shí)別的可靠性。

4.2 基于羅曼諾夫斯基準(zhǔn)則的最大尺度求取

式（9）～式（11）中，N關(guān)系到所選取的鄰域范圍大小。N過(guò)小，算法抗噪性能差；N過(guò)大，算法效率和弱特征提取能力變差。由前面分析可知，最優(yōu)鄰域?yàn)镹的選取提供了有益的參考，為此，本文以最優(yōu)鄰域?yàn)槎喑叨确治龅淖畲蟪叨取榱藢?shí)現(xiàn)最大尺度的自動(dòng)選取，利用羅曼多夫斯基準(zhǔn)則的突變檢測(cè)能力，將羅曼諾夫斯基準(zhǔn)則與一致性測(cè)度相結(jié)合求取最大分析尺度。具體過(guò)程如下：

（1）初始化。選取待分析采樣點(diǎn)pi的4個(gè)最近點(diǎn)，并通過(guò)這4個(gè)鄰域點(diǎn)計(jì)算法向一致性測(cè)度函數(shù)α（pi，4）。

（2）依次增加鄰域點(diǎn)數(shù)，并計(jì)算法向一致性測(cè)度函數(shù)值α（pi，k），k＝5，6，…。

（3）判斷第k個(gè)鄰域點(diǎn)是否屬于最優(yōu)鄰域：

由計(jì)算所得的法向一致性測(cè)度的個(gè)數(shù)和顯著性水平c，查t分布表，確定檢驗(yàn)系數(shù)K（k－3，c）。若｜α（pi，j）－｜＜K（k－3，c）σα，則第k個(gè)鄰域點(diǎn)作為最優(yōu)鄰域點(diǎn)，并轉(zhuǎn)步驟（2）；否則，第k個(gè)鄰域點(diǎn)不作為最優(yōu)鄰域點(diǎn)，鄰域達(dá)到最大尺度并結(jié)束擴(kuò)展。

4.3 多尺度特征指標(biāo)的遞推求解

在多尺度張量分解中，需不斷增加分析尺度（擴(kuò)展采樣點(diǎn)的鄰域范圍）直至最大尺度，并計(jì)算各尺度下的特征指標(biāo)。在多尺度張量特征指標(biāo)求取過(guò)程中，各采樣點(diǎn)張量矩陣奇異值λ1、λ2、λ3的計(jì)算效率成為影響算法效率的關(guān)鍵。為此，本文采用遞推的方法求取各尺度下的張量矩陣奇異值，具體過(guò)程如下。

設(shè)尺度參數(shù)為j（鄰域采樣點(diǎn)個(gè)數(shù)為j）時(shí)，采樣點(diǎn)p的鄰域指標(biāo)集為Np，鄰域均值記為（j），張量 矩 陣 記 為T(mén)（j），奇 異 值 為λ1（j）、λ2（j）、λ3（j）。尺度變?yōu)閖＋1時(shí)，采樣點(diǎn)q被納入到原有鄰域之中，則可通過(guò)下式求取尺度j＋1下的鄰域均值：

將式（14）代入

可得

由于奇異值λ1（j）、λ2（j）、λ3（j）為特征方程Γ（λ）＝｜T（j）－λI｜＝λ3＋aλ2＋bλ＋c＝0的3個(gè)根，而每引入一個(gè)性質(zhì)類似的鄰域點(diǎn)不會(huì)引起特征方程系數(shù)的顯著變化，因此，增加1個(gè)鄰域點(diǎn)后的奇異值λ1（j＋1）、λ2（j＋1）、λ3（j＋1）仍在原有奇異值λ1（j）、λ2（j）、λ3（j）附近。為此，本文在每次鄰域更新后以λ1（j）、λ2（j）、λ3（j）為初始值，采用牛頓迭代進(jìn)行奇異值更新，過(guò)程如圖7所示。由牛頓迭代的2次收斂特性可知，每次尺度更新所需的迭代次數(shù)不超過(guò)3，可以大大減少奇異值計(jì)算所需時(shí)間。在求取各尺度參數(shù)張量矩陣奇異值的條件下，將各特征值代入式（4）～式（6）即可求取當(dāng)前尺度下的張量顯著性編碼，再對(duì)各尺度張量顯著性編碼累計(jì)即可求取多尺度特征指標(biāo)。

圖7 利用牛頓迭代進(jìn)行奇異值的遞推求解

綜上所述，點(diǎn)云的多尺度張量分解實(shí)質(zhì)上就是通過(guò)不同范圍的鄰域點(diǎn)構(gòu)造張量矩陣（每個(gè)鄰域的大小對(duì)應(yīng)多尺度分析的一個(gè)尺度），進(jìn)而通過(guò)統(tǒng)計(jì)各尺度下的特征顯著性編碼識(shí)別采樣點(diǎn)的特征屬性。由圖8可見(jiàn)，利用該方法可以有效識(shí)別模型中的角點(diǎn)、曲線點(diǎn)和曲面點(diǎn)。

圖8 利用多尺度張量分解進(jìn)行Fandisk模型特征點(diǎn)識(shí)別結(jié)果

5 利用約束最小生成森林重建特征曲線

在進(jìn)行點(diǎn)云特征識(shí)別的基礎(chǔ)上，根據(jù)相鄰特征點(diǎn)之間的關(guān)系，將特征點(diǎn)連接為光滑的、能夠準(zhǔn)確表征點(diǎn)云結(jié)構(gòu)的特征曲線是點(diǎn)云結(jié)構(gòu)特征提取的重要步驟。以角點(diǎn)為樹(shù)根，以特征邊上的點(diǎn)為樹(shù)枝和樹(shù)葉，借鑒Prim算法的思想，建立最小生成森林，流程如下。

（1）根據(jù)特征識(shí)別結(jié)果，利用角點(diǎn)和曲線點(diǎn)構(gòu)建特征點(diǎn)集。

（2）計(jì)算特征點(diǎn)集中任意兩點(diǎn)之間邊的代價(jià)函數(shù)。為了使特征曲線盡量光滑，在構(gòu)造代價(jià)函數(shù)時(shí)兼顧考慮邊的長(zhǎng)度和采樣點(diǎn)切向夾角，定義采樣點(diǎn)qi與qj之間的代價(jià)函數(shù)：

（3）初始化曲線點(diǎn)標(biāo)記變量Flag＝0，搜索連接所有根節(jié)點(diǎn)最短的邊，并將其加入到相應(yīng)的樹(shù)中，同時(shí)將相應(yīng)折皺點(diǎn)的Flag置為1。

（4）搜索Flag＝0的點(diǎn)，找到與所有樹(shù)（所有以特征角點(diǎn)為根節(jié)點(diǎn)的樹(shù)）中節(jié)點(diǎn) （包括根節(jié)點(diǎn)和樹(shù)枝節(jié)點(diǎn)、樹(shù)葉節(jié)點(diǎn)）相連的最短的邊，將其加入到相應(yīng)的樹(shù)中，并將其Flag置1。

（5）重復(fù)第（4）步，直至所有曲線點(diǎn)的Flag為1。此時(shí)得到以角點(diǎn)為根節(jié)點(diǎn)的最小生成森林。

對(duì)得到的最小生成森林，以各角點(diǎn)為根節(jié)點(diǎn)進(jìn)行遍歷，即可得到點(diǎn)云的結(jié)構(gòu)特征曲線。雖然采用多尺度策略有效提高了特征點(diǎn)提取的可靠性，然而在強(qiáng)噪聲環(huán)境下，仍有少量的偽特征點(diǎn)被納入到特征點(diǎn)集之中。為此，將深度小于一定閾值（本文取閾值深度為3）的樹(shù)枝節(jié)點(diǎn)（偽特征點(diǎn)）投影到緊鄰有效樹(shù)枝節(jié)點(diǎn)確定的圓弧上，再以投影點(diǎn)代替?zhèn)翁卣鼽c(diǎn)進(jìn)行特征曲線的重建，以降低特征曲線復(fù)雜性，偽特征點(diǎn)投影過(guò)程如圖9所示。在實(shí)現(xiàn)偽特征點(diǎn)投影的基礎(chǔ)上，由根節(jié)點(diǎn)開(kāi)始，對(duì)每條遍歷路徑進(jìn)行移動(dòng)最小二乘曲線擬合，可以獲得多條光滑的點(diǎn)云特征曲線。再將小于特定閾值（本文取3倍采樣點(diǎn)平均距離）的特征曲線端點(diǎn)用擬合圓弧連接起來(lái)，形成閉合的特征曲線，避免將原本閉合的特征曲線拆分成多段，即可實(shí)現(xiàn)點(diǎn)云結(jié)構(gòu)特征的有效提取。

圖9 偽特征點(diǎn)投影示意圖

6 實(shí)驗(yàn)研究

以Intel Pentium 2.0GHz CPU、1GB 內(nèi)存的PC機(jī)為硬件處理平臺(tái)，在Vs2010環(huán)境下進(jìn)行實(shí)驗(yàn)研究。分別對(duì)立方體點(diǎn)云和Fandisk點(diǎn)云模型進(jìn)行結(jié)構(gòu)特征提取，結(jié)果分別如圖10、圖11所示。圖10表明，對(duì)于結(jié)構(gòu)簡(jiǎn)單、特征明顯的立方體點(diǎn)云，本文算法能夠有效提取立方體對(duì)象的12條特征邊。圖11表明，本文在對(duì)最優(yōu)鄰域進(jìn)行多尺度分析的基礎(chǔ)上，應(yīng)用張量分量的特征統(tǒng)計(jì)編碼，不僅可以識(shí)別明顯的特征角點(diǎn)和特征邊，而且可以識(shí)別不明顯的特征特征曲線，能夠有效解決尖銳區(qū)域特征平滑與平滑區(qū)域易受噪聲影響的矛盾，可以對(duì)點(diǎn)云結(jié)構(gòu)特征進(jìn)行有效識(shí)別。利用本文算法以及文獻(xiàn)［4］和文獻(xiàn)［9］，對(duì)Fandisk點(diǎn)云、Bunny點(diǎn)云和Igea點(diǎn)云進(jìn)行特征曲線重建運(yùn)行時(shí)間的對(duì)比，結(jié)果如表1所示。實(shí)驗(yàn)結(jié)果表明，多尺度分析過(guò)程中采用奇異值遞推求解，在一定程度上提高了算法效率。

表1 算法運(yùn)行時(shí)間 ms

圖10 立方體點(diǎn)云結(jié)構(gòu)特征提取結(jié)果

圖11 Fandisk模型點(diǎn)云結(jié)構(gòu)特征提取結(jié)果

7 結(jié)語(yǔ)

針對(duì)傳統(tǒng)點(diǎn)云結(jié)構(gòu)特征提取過(guò)程中尖銳區(qū)域特征平滑與平滑區(qū)域易受噪聲影響的矛盾，提出了一種基于多尺度張量分解的點(diǎn)云結(jié)構(gòu)特征提取算法。利用張量矩陣奇異值分解的性質(zhì)，對(duì)采樣點(diǎn)特征進(jìn)行顯著性編碼，實(shí)現(xiàn)了采樣點(diǎn)特征的初步提取。為了解決尖銳區(qū)域與平滑區(qū)域特征提取的矛盾，提高特征提取的精度，研究了鄰域?qū)μ卣魈崛〗Y(jié)果的影響，在此基礎(chǔ)上通過(guò)法向一致性測(cè)度和切向一致性測(cè)度定義了采樣點(diǎn)最優(yōu)鄰域。在最優(yōu)鄰域內(nèi)對(duì)采樣點(diǎn)進(jìn)行多個(gè)尺度張量的分解，統(tǒng)計(jì)不同尺度下的顯著性編碼，實(shí)現(xiàn)了采樣點(diǎn)特征屬性的精確識(shí)別。利用羅曼諾夫斯基準(zhǔn)則檢測(cè)法向（切向）一致性測(cè)度突變，實(shí)現(xiàn)最優(yōu)鄰域的自動(dòng)選取。利用最小二乘森林進(jìn)行特征點(diǎn)遍歷，并通過(guò)將偽特征點(diǎn)向鄰近特征點(diǎn)圓弧進(jìn)行投影，實(shí)現(xiàn)了特征曲線平滑。實(shí)驗(yàn)結(jié)果表明，本文算法可以實(shí)現(xiàn)復(fù)雜點(diǎn)云對(duì)象結(jié)構(gòu)特征識(shí)別，解決了傳統(tǒng)點(diǎn)云結(jié)構(gòu)特征提取過(guò)程中尖銳區(qū)域特征平滑與平滑區(qū)域易受噪聲影響的矛盾。

［1］Gross M，Pfister H.Point－based Graphics［M］.Burlington：Morgan Kaufmann，2007.

［2］Kobbelt L，Botsch M.A Survey of Point－based Techniques in Computer Graphics［J］.Computers and Graphics，2004，28（6）：801－814.

［3］Gumhold S，Wang X，McLeod R.Feature Extraction from Point Clouds［C］//Proceedings of 10th International Meshing Roundtable. Newport Beach：John Chawner Pointwise，Inc.，2001：1－10.

［4］Pauly M，Keiser R，Gross M.Multi－scale Feature Extraction on Point－Sampled Surfaces［J］.Eurographics，2003，22（3）：281－289.

［5］Lee I K.Curve Reconstruction from Unorganized Points［J］.Computer Aided Geometric Design，2000，17（2）：161－177.

［6］柯映林，范樹(shù)遷.基于點(diǎn)云的邊界特征直接提取技術(shù)［J］.機(jī)械工程學(xué)報(bào)，2004，40（9）：116－120.

［7］Jenke P，Wand M，Bokeloh M，et al.Bayesian Point Cloud Reconstruction［J］.Computer Graphics Forum，2009，25（3）：379－388.

［8］Joel D II，K H Linh，Tilo Ochotta，et al.Robust Smooth Feature Extraction from Point Clouds［C］//IEEE International Conference on Shape Modeling and Applications.Lyon，2007：1－11.

［9］龐旭芳，龐明勇.點(diǎn)云模型谷脊特征的提取與增強(qiáng)算法［J］.自動(dòng)化學(xué)報(bào)，2010，36（8）：1073－1083.

［10］Joel D II，Tilo Ochotta.Spline－based Feature Curves from Point－Sampled Geometry［J］.The Visual Computer，2008，24（6）：449－462.

［11］Demarsin K，Vanderstraeten D，Volodine T，et al.Detection of Closed Sharp Edges in Point Clouds Using Normal Estimation and Graph Theory［J］.Computer Aided Design，2007，39（4）：276－283.［12］Liu Yu，Xiong Youlun.Automatic Segmentation of Unorganized Noisy Point Clouds Based on the Gaussian Map［J］.Computer Aided Design，2008，40（5）：576－594.

［13］Oztireli C，Guennebaud G，Gross M.Feature Preserving Point Set Surfaces Based on Non－linear Kernel Regression［J］.Computer Graphics Forum，2009，28（2）：493－501.

［14］Guy G，Medioni G.Inference of Surfaces，3D Curves，and Junctions from Sparse，Noisy，3DData［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1997，19（11）：1265－1277.