韓磊，陳宇，王春陽，于艷鑫

（長春理工大學電子信息工程學院，長春 130022）

0 引言

三維激光掃描技術(shù)現(xiàn)已在考古研究、生物醫(yī)學、汽車工業(yè)、水利工程地形測繪等工程領域有了廣泛的應用[1-2]，但其測得的點云數(shù)據(jù)密度高、數(shù)量大，存在大量的冗余點[3]。因此針對這類點云數(shù)據(jù)首先要進行簡化即去除冗余點，為保證模型最基本的幾何形狀保留完整，需要先提取出點云特征點，進而對點云數(shù)據(jù)進行簡化和三維曲面重建等。另外，特征點檢測對于點云配準也具有重要意義。所以模型的特征點提取是處理三維散亂點云數(shù)據(jù)的關鍵步驟之一[4]。

Charlie等采用雙邊濾波來檢測和重建特征,需要優(yōu)化給定模型的網(wǎng)格連通性，否則尖銳的邊緣區(qū)域頂點坐標會發(fā)生漂移和擁擠[5]。Mian等人通過構(gòu)造一個品質(zhì)因數(shù)Qk，該品質(zhì)因數(shù)Qk包括高斯曲率和主曲率，特征點為其品質(zhì)因數(shù)Qk大于某閾值的點[6]。王小超等提出基于局部重建的點云特征點提取方法，該方法可以處理分片光滑曲面上采集的點云數(shù)據(jù)，但對于兩個彎曲程度較大的曲面相交形成的特征點該方法不適用[7]。王晉疆等提出一種基于點簽名的特征點檢測方法，根據(jù)具有正態(tài)分布特性的點簽名的均值與方差設制曲率閾值，該方法抗噪性能佳但時間復雜度高[8]。

針對現(xiàn)有算法存在的效率低、特征點提取不準確等問題，本文提出一種改進的自適應點云特征點提取算法，通過計算數(shù)據(jù)點到k鄰域點（k可以根據(jù)數(shù)據(jù)密度進行改變）的平均距離、該點的曲率以及該點的法向與k鄰域點法向夾角的和，設定一個特征參數(shù)，根據(jù)特征參數(shù)正態(tài)分布規(guī)律，利用均值與方差的和自適應地設置閾值來提取特征點。該方法適用于復雜的模型數(shù)據(jù)，能夠準確高效地提取出點云特征點。

1 特征點提取方法

1.1 散亂點云空間劃分

本文采用Hash法劃分點云P，建立空間長方體包圍盒，將空間等間距切割成體積相同的若干個立方體柵格（示意圖如圖1），確定離散點所在的子立方體，標記索引號，便于查找k鄰域點[9]。求出X,Y,Z三個坐標軸上的最大值與最小值Xmax,Xmin,Ymax,Ymin,Zmax,Zmin。

長方體包圍盒的邊長為：

定義小立方體邊長：

其中，N為點云數(shù)目，根據(jù)經(jīng)驗k一般取值為15-25。通過下式對數(shù)據(jù)點進行定位，求出任一點在小立方體的索引號m,n,l：

求每個數(shù)據(jù)點的歐氏距離最近的k個鄰域點時，搜索范圍限定在其本身所在小立方體及其上下左右前后的27個立方體。

圖1 立方體柵格示意圖

1.2 基于曲率和密度的特征點檢測算法

一般模型的特征區(qū)域數(shù)據(jù)點比較密集，曲率較大，該算法綜合考慮數(shù)據(jù)點與鄰域點的平均距離、數(shù)據(jù)點曲率，以及數(shù)據(jù)點與鄰域點法向夾角的和。利用八叉樹法對點云進行細分求點云密度，再結(jié)合模型整體信息確定特征檢測閾值[10]。鄰域點的平均距離計算公式如下：

其中M(pi)為數(shù)據(jù)點pi的鄰近點集。

點云數(shù)據(jù)的法向和曲率也是判斷是否為特征點的重要因素，采用基于最小二乘平面擬合法求pi法向量ni，如下所示：

其中n為平面P(n,d)的法向量，d為平面P(n,d)到坐標原點的距離。利用主元分析法求解，最小特征值對應的特征向量即為點云法向量。

，設λ1＜λ2＜λ3，e1可近似曲面在點pi的法向量ni，即ni≈e1。

τi近似為點云模型在數(shù)據(jù)點pi的平均曲率。數(shù)據(jù)點與鄰域點的法向夾角也是衡量曲面彎曲程度的標準，定義法向夾角參數(shù)wa(pi)為數(shù)據(jù)點與所有鄰域點的法向夾角的和：

θpipj可由下式求得：

特征區(qū)域內(nèi)的點比較密集，數(shù)據(jù)點與鄰域點距離小，所以數(shù)據(jù)點到k鄰域點（k可以根據(jù)數(shù)據(jù)密度進行改變）的平均距離與特征參數(shù)成反比，曲率越大模型特征越明顯，所以曲率與特征參數(shù)成正比，特征點與鄰近點的法向量夾角較大，所以法向夾角參數(shù)與特征參數(shù)成正比，定義特征參數(shù)：

其中λn曲率系數(shù)和λd是距離系數(shù)。

用八叉樹計算特征檢測閾值，子節(jié)點中包含的數(shù)據(jù)點個數(shù)小于8，計算所有葉子節(jié)點的平均對角線長度，作為點云密度ξ。由點云模型邊到中心點的最大距離dc表示模型的尺寸，定義特征檢測閾值為σ=ξ/dc。特征參數(shù)大于檢測閾值σ的數(shù)據(jù)點為特征點。

1.3 自適應點云特征點提取算法

由于基于曲率和密度的特征點檢測算法的特征參數(shù)需要人為輸入和調(diào)整曲率系數(shù)和距離系數(shù)，這兩個系數(shù)僅作為控制特征點數(shù)量，且計算點云密度和模型邊到中心點的最大距離較耗時。因此本文將曲率系數(shù)與距離系數(shù)去掉，重新定義特征參數(shù)如下：

選取斯坦福兔子模型、Horse模型和椅子模型三個在形狀上具有代表性的模型計算其特征參數(shù)，特征參數(shù)分布如圖2。

圖2 特征參數(shù)分布圖

由圖 2（a）（c）（e）可以看出斯坦福兔子模型表面較平坦，數(shù)據(jù)點較緊湊；Horse模型四條腿相對身體較凸出且分散；椅子模型有鏤空部分，數(shù)據(jù)點不完全連續(xù)。這三個模型的特征參數(shù)分布如圖 2（b）（d）（f），圖上曲線為正態(tài)分布曲線，橫坐標為參數(shù)值，縱坐標為點云數(shù)?？梢钥闯鎏卣鲄?shù)近似服從正態(tài)分布，因此，可以認為散亂點云的特征參數(shù)具有正態(tài)分布的特點，根據(jù)這一特點來確定特征點提取閾值。閾值改進如下，取特征參數(shù)的均值與方差：

確定閾值：

若某個數(shù)據(jù)點的特征參數(shù)w(pi)大于閾值δ，那么這個點pi為特征點qi。若特征參數(shù)w(pi)小于閾值δ，pi為非特征點。

2 實驗結(jié)果分析

本文實驗在MATLAB 2016a環(huán)境下進行特征點提取，操作系統(tǒng)為Windows 10，主頻2.5GHz，處理器為Intel Core i7-6500U。圖3、圖4為本文方法提取特征點效果。

圖3 特征點提取

圖3 （a）為斯坦福兔子模型，共35947個點，提取出的特征點個數(shù)為4797。特征點云顏色與原始點云相對應?？梢钥闯?，模型的耳朵、頭部、腿部和尾部等紋理信息可以提取出來。圖3（b）為椅子模型，共49960個點，提取出的特征點個數(shù)為7290。椅子的靠背、凳腿及座板邊框特征可以有效的提取出來，座板內(nèi)部為非特征信息被過濾掉。

圖4 Skull模型及特征點提取

圖4 為Skull模型，原始點云共有20002個點，提取特征點個數(shù)為3830?？梢钥闯瞿Ｐ皖^部的字母很好地保留下來，模型的牙齒信息也基本保留，以及模型的棱角紋理較好地提取出來。

圖5為本文方法取k=15與文獻[8]方法取k=20,e=1和文獻[10]方法取λn=400，λd=100在無噪聲干擾下和隨機添加3000個噪聲點的情況下，對Horse模型的特征點提取效果。

如圖5所示，可以看出模型頭部、腹部和腿部等是特征點密集區(qū)域，文獻[8]（圖5（a））、文獻[10]（圖5（c））和本文方法（圖5（e））在無噪聲干擾下都能比較好的提取出特征點。但文獻[8]（圖5（b））和文獻[10]（圖5（d））在噪聲的干擾下，可以明顯看出將很多噪聲點識別為特征點，影響后續(xù)重建效果。本文方法（圖5（f））對噪聲敏感度更低，可以保持相對穩(wěn)定的特征提取效果。

圖5 文獻[8]方法、文獻[10]方法與本文方法特征點提取結(jié)果

表1 未加噪特征點提取對比

表2 加噪特征點提取對比

表1為在無噪聲情況下文獻[8]方法、文獻[10]方法與本文方法對Horse模型（48485個點）特征點提取對比，表2為加3000個噪聲點的情況下特征點提取對比結(jié)果。文獻[8]方法由于要經(jīng)過兩次篩選：先根據(jù)散亂點云具有正態(tài)分布規(guī)律的點簽名設定曲率閾值進行篩選，然后再對候選特征點在其主曲率方向上投影，進行進一步篩選，時間復雜度較高。該方法提取出特征點1621個，耗時 16.5s；加噪后特征點為 2120，耗時16.8s。文獻[10]方法根據(jù)點云法向夾角、數(shù)據(jù)點平均距離和曲率計算特征參數(shù)，選取數(shù)據(jù)點密度與模型到中心點最大距離的比值作為閾值，提取出特征點1128個，耗時10.6s；加噪后特征點為10334，耗時13.2s。該方法需人為根據(jù)經(jīng)驗設定系數(shù)。本文方法根據(jù)特征參數(shù)的正態(tài)分布特點選取閾值，提取出7025個特征點，耗時8.2s；加噪后特征點為7382，耗時8.3s?？梢钥闯黾釉牒笞R別出的特征點與未加噪相差不大。由此得出本算法能夠較完整地保留模型的特征信息，耗時短，效率較高。

3 結(jié)語

本文采用Hash函數(shù)法求出數(shù)據(jù)點鄰域點，通過計算數(shù)據(jù)點到k鄰域點距離的平均、該點曲率、該點的法向與k鄰域點法向夾角的和，設定點云特征參數(shù)，根據(jù)特征參數(shù)的均值與方差自適應地設置閾值來提取特征點，不需要輸入系數(shù)。實驗結(jié)果表明，本文的方法準確提取出點云模型特征點，提取出的點少而精，不會遺漏特征點，是一種有效的特征點提取算法。

參考文獻：

[1]高艷芳,豆賀,佟晗,韓勝松.反求工程的研究現(xiàn)狀與發(fā)展趨勢[J].現(xiàn)代化農(nóng)業(yè),2017,09,58-60

[2]劉曉芳,田蘭芬.三維激光掃描技術(shù)在水利工程地形測繪中的應用[J].科技創(chuàng)新與應用，2017,27,141-143

[3]解則曉,劉靜曉,潘成成等.一種散亂分層點云的有序化精簡方法[J].幾何設計與計算,2016,37（3）：359-366

[4]楊斌杰,魯鐵定.點云數(shù)據(jù)特征點提取方法的比較[J].江西科學,2015,33（1）：10-14

[5]Charlie C L.Wang.Bilateral Recovering of Sharp Edges on Feature-insensitive Sampled Meshes[J].IEEE Transactions on Visuallization and Computer Graphics,2006,12（4）.

[6]Mian A,Bennamoun M,Oture-based 3D Object Retrieval from Cluttered Scenes[J].International Journal of Computer Vision,2010,89（2）：348-36.

[7]王小超,劉秀平,李寶軍等.基于局部重建的點云特征點提取[J].計算機輔助設計與圖形學學報,2013,25（5）：659-665.

[8]王晉疆，陳陽，田慶國等.一種基于點簽名的散亂點云特征點檢測方法[J].計算機工程,2014,40（7）：174-178.

[9]王楠.基于三維散亂點云的網(wǎng)格重構(gòu)技術(shù)研究[D].大連：大連大學,2013.

[10]王麗輝,袁保宗.三維散亂點云模型的特征點檢測[J].Signal Processing,2011,27（6）：932-938.