基于多尺度張量分解的點云結構特征提取

林洪彬 劉 彬 張玉存

燕山大學河北省測試計量技術與儀器重點實驗室，秦皇島，066004

0 引言

隨著三維掃描技術的發展與廣泛應用，三維掃描點云數據處理技術的研究也日益興起。點云結構特征提取作為點云消噪、曲面重建的基礎，成為三維幾何數據處理領域的重要研究方向之一［1］。相對于傳統的網格處理算法，直接點云處理算法無需進行拓撲重建，具有更高的存儲和執行效率，這使得該類算法越來越受到國內外學者的青睞［2］。

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

本文以張量分析理論為基礎，對采樣點特征進行顯著性編碼，實現了采樣點特征的初步提??；為了解決尖銳區域與平滑區域特征提取的矛盾，提高特征提取的精度，通過法向一致性測度和切向一致性測度定義了采樣點最優鄰域；在最優鄰域內對采樣點進行多個尺度的張量分解，統計不同尺度下的顯著性編碼實現采樣點特征屬性的精確識別；利用羅曼諾夫斯基準則檢測法向（切向）一致性測度突變，實現最優鄰域的自動選??；利用最小二乘森林進行特征點遍歷，并通過將偽特征點向鄰近特征點圓弧進行投影實現特征曲線平滑，實現點云結構特征提取。

1 點云的張量分解

二階對稱張量在三維空間微分幾何結構描述方面具有獨特的能力，本文基于Guy等［14］的研究成果，針對點云數據，基于二階對稱張量對幾何特征表達與特征點識別問題進行研究。通常三維空間中采樣點pi的二階對稱張量T可用半正定對稱矩陣表示為

式中，η（pi，n）為采樣 點pi的 鄰 域；n為 鄰 域 內 采 樣 點個數。

根據矩陣奇異值分解理論，對張量矩陣T進行奇異值分解：

式中，λ1、λ2、λ3為張量矩陣T的奇異值，λ1≥λ2≥λ3≥0；e1、e2、e3為λ1、λ2、λ3對應的3個特征向量。

實質上，利用張量矩陣T進行點云局部幾何結構描述，相當于通過鄰域內的采樣點擬合的橢球面進行采樣幾何特性描述，該橢球的3個主方向由正交特征向量e1、e2、e3確定，各主方向橢球的半徑正比于相應特征向量所對應的奇異值。

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

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

2 基于張量分解的點云特征測度

圖1 張量分解示意圖

圖2 曲面點、曲線點、角點的主方向

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

3 基于最優鄰域張量分解的點云特征識別

3.1 鄰域對特征屬性識別的影響

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

圖3 鄰域點數不同時Fandisk模型平均曲率估計結果

3.2 利用最優鄰域估計采樣點特征屬性

由上述分析可知，將全局一致的K作為鄰域點數容易導致高頻區域特征過度平滑與低頻區域抗噪聲能力差的矛盾，使得在進行點云特征屬性識別時，算法抗噪聲能力差，弱特征提取能力不強。為此，針對采樣點各自的微分幾何特性，使高曲率區域的K小一些，低曲率區域的K大一些，即可解決全局一致的K造成的矛盾。為此，本文采用法向（切向）一致性測度進行采樣點最優鄰域估計，以提高采樣點特征屬性識別的可靠性。

采樣點的法向量屬于一階微分幾何量，容易受旁值點（不屬于原有光滑曲面上的點）的影響。當逐漸增大鄰域點數n時，若所有鄰域點均屬于采樣點所在光滑平面或曲面，則估計所得的采樣點法向趨于一致或緩慢變化，一旦跨越特征的采樣點被納入到采樣點鄰域內，采樣點法向將發生突變。因此，將采樣點法向剛好發生突變前之的鄰域作為最優鄰域，不僅可以盡量擴大鄰域范圍，而且有效避免了將旁值點納入到鄰域之中。為此，本文構建了法向一致性測度，以實現采樣點最優鄰域的檢測。

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

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

圖4 法向一致性測度隨尺度變化關系

圖5 角點、平面點和曲線點法向一致性測度隨尺度變化關系

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

為了分析曲線點的最優鄰域，利用最優鄰域內曲線點的切向不變特性，建立切向一致性測度：

3.3 利用最優鄰域張量分解進行點云特征屬性識別

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

圖6 最優鄰域Fandisk模型特征識別計結果

4 利用多尺度張量分解進行采樣點特征屬性的可靠識別

為了實現采樣點特征屬性的自動識別，需要完成如下兩個方面的工作：①提高噪聲環境下特征點識別的可靠性；②在確保特征點識別可靠性的基礎上，保障算法的弱特征提取能力。為此，本文基于多尺度分析的思想，構建多尺度張量特征指標，以提高采樣點特征分析的可靠性。

4.1 點云的多尺度特征分析

多尺度分析兼具強大的全局分析和局部特征識別能力，在一維和二維信號處理中得到了廣泛的應用。本文將多尺度分析與三維點云張量特征顯著性測度相結合，以解決特征識別測度函數抗噪性與弱特征提取之間的矛盾。

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

式中，g（x，t）為高斯函數。

實質上，上述過程相當于用不同尺度參數t的高斯函數對點云進行平滑，當t＝0時，L（x，0）＝f（x）表示原始點云。尺度參數t越大，平滑作用越強，得到的點云就越光滑，越有利于提高噪聲環境下的特征點識別能力；t越小，平滑作用越不明顯，越有利于弱特征的提取。為簡化計算過程，本文以采樣點鄰域點數為采樣點的分析尺度，通過分析最優鄰域內各尺度（鄰域點數）下的張量分解顯著性編碼，建立如下特征指標：

式中，Ωcurve（pi）、Ωplane（pi）、Ωconner（pi）為多尺度張量特征指標；N為采樣點pi最優鄰域的點數。

通過不斷增加尺度參數（鄰域點數），并求取多尺度張量特征指標，進而通過多尺度張量特征指標進行采樣點的特征屬性判別，將大大提高噪聲環境下特征點識別的可靠性。

4.2 基于羅曼諾夫斯基準則的最大尺度求取

式（9）～式（11）中，N關系到所選取的鄰域范圍大小。N過小，算法抗噪性能差；N過大，算法效率和弱特征提取能力變差。由前面分析可知，最優鄰域為N的選取提供了有益的參考，為此，本文以最優鄰域為多尺度分析的最大尺度。為了實現最大尺度的自動選取，利用羅曼多夫斯基準則的突變檢測能力，將羅曼諾夫斯基準則與一致性測度相結合求取最大分析尺度。具體過程如下：

（1）初始化。選取待分析采樣點pi的4個最近點，并通過這4個鄰域點計算法向一致性測度函數α（pi，4）。

（2）依次增加鄰域點數，并計算法向一致性測度函數值α（pi，k），k＝5，6，…。

（3）判斷第k個鄰域點是否屬于最優鄰域：

由計算所得的法向一致性測度的個數和顯著性水平c，查t分布表，確定檢驗系數K（k－3，c）。若｜α（pi，j）－｜＜K（k－3，c）σα，則第k個鄰域點作為最優鄰域點，并轉步驟（2）；否則，第k個鄰域點不作為最優鄰域點，鄰域達到最大尺度并結束擴展。

4.3 多尺度特征指標的遞推求解

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

設尺度參數為j（鄰域采樣點個數為j）時，采樣點p的鄰域指標集為Np，鄰域均值記為（j），張量 矩 陣 記 為T（j），奇 異 值 為λ1（j）、λ2（j）、λ3（j）。尺度變為j＋1時，采樣點q被納入到原有鄰域之中，則可通過下式求取尺度j＋1下的鄰域均值：

將式（14）代入

可得

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

圖7 利用牛頓迭代進行奇異值的遞推求解

綜上所述，點云的多尺度張量分解實質上就是通過不同范圍的鄰域點構造張量矩陣（每個鄰域的大小對應多尺度分析的一個尺度），進而通過統計各尺度下的特征顯著性編碼識別采樣點的特征屬性。由圖8可見，利用該方法可以有效識別模型中的角點、曲線點和曲面點。

圖8 利用多尺度張量分解進行Fandisk模型特征點識別結果

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

在進行點云特征識別的基礎上，根據相鄰特征點之間的關系，將特征點連接為光滑的、能夠準確表征點云結構的特征曲線是點云結構特征提取的重要步驟。以角點為樹根，以特征邊上的點為樹枝和樹葉，借鑒Prim算法的思想，建立最小生成森林，流程如下。

（1）根據特征識別結果，利用角點和曲線點構建特征點集。

（2）計算特征點集中任意兩點之間邊的代價函數。為了使特征曲線盡量光滑，在構造代價函數時兼顧考慮邊的長度和采樣點切向夾角，定義采樣點qi與qj之間的代價函數：

（3）初始化曲線點標記變量Flag＝0，搜索連接所有根節點最短的邊，并將其加入到相應的樹中，同時將相應折皺點的Flag置為1。

（4）搜索Flag＝0的點，找到與所有樹（所有以特征角點為根節點的樹）中節點 （包括根節點和樹枝節點、樹葉節點）相連的最短的邊，將其加入到相應的樹中，并將其Flag置1。

（5）重復第（4）步，直至所有曲線點的Flag為1。此時得到以角點為根節點的最小生成森林。

對得到的最小生成森林，以各角點為根節點進行遍歷，即可得到點云的結構特征曲線。雖然采用多尺度策略有效提高了特征點提取的可靠性，然而在強噪聲環境下，仍有少量的偽特征點被納入到特征點集之中。為此，將深度小于一定閾值（本文取閾值深度為3）的樹枝節點（偽特征點）投影到緊鄰有效樹枝節點確定的圓弧上，再以投影點代替偽特征點進行特征曲線的重建，以降低特征曲線復雜性，偽特征點投影過程如圖9所示。在實現偽特征點投影的基礎上，由根節點開始，對每條遍歷路徑進行移動最小二乘曲線擬合，可以獲得多條光滑的點云特征曲線。再將小于特定閾值（本文取3倍采樣點平均距離）的特征曲線端點用擬合圓弧連接起來，形成閉合的特征曲線，避免將原本閉合的特征曲線拆分成多段，即可實現點云結構特征的有效提取。

圖9 偽特征點投影示意圖

6 實驗研究

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

表1 算法運行時間 ms

圖10 立方體點云結構特征提取結果

圖11 Fandisk模型點云結構特征提取結果

7 結語

針對傳統點云結構特征提取過程中尖銳區域特征平滑與平滑區域易受噪聲影響的矛盾，提出了一種基于多尺度張量分解的點云結構特征提取算法。利用張量矩陣奇異值分解的性質，對采樣點特征進行顯著性編碼，實現了采樣點特征的初步提取。為了解決尖銳區域與平滑區域特征提取的矛盾，提高特征提取的精度，研究了鄰域對特征提取結果的影響，在此基礎上通過法向一致性測度和切向一致性測度定義了采樣點最優鄰域。在最優鄰域內對采樣點進行多個尺度張量的分解，統計不同尺度下的顯著性編碼，實現了采樣點特征屬性的精確識別。利用羅曼諾夫斯基準則檢測法向（切向）一致性測度突變，實現最優鄰域的自動選取。利用最小二乘森林進行特征點遍歷，并通過將偽特征點向鄰近特征點圓弧進行投影，實現了特征曲線平滑。實驗結果表明，本文算法可以實現復雜點云對象結構特征識別，解決了傳統點云結構特征提取過程中尖銳區域特征平滑與平滑區域易受噪聲影響的矛盾。

［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］柯映林，范樹遷.基于點云的邊界特征直接提取技術［J］.機械工程學報，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］龐旭芳，龐明勇.點云模型谷脊特征的提取與增強算法［J］.自動化學報，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.