一種基于點簽名的散亂點云特征點檢測方法

王晉疆1,2，陳 陽1,2，田慶國1,2，常天宇1,2

(1.天津大學(xué)精密儀器與光電子工程學(xué)院，天津 300072；2.光電信息技術(shù)教育部重點實驗室，天津 300072)

1 概述

隨著坐標(biāo)測量技術(shù)的不斷發(fā)展，人們可以方便地獲得被掃描物體的點云數(shù)據(jù)。點云是以離散點為基元的幾何模型，一般具有散亂和龐大的特點，散亂是指各三維點之間無序排列，只有三維坐標(biāo)值而沒有明確的空間信息；龐大是指掃描到的點云數(shù)據(jù)數(shù)量過于龐大，而往往極少數(shù)的點就可以表征物體的基本信息，因而存在大量的冗余數(shù)據(jù)，給后續(xù)的存儲、處理等帶來諸多不便。特征點檢測就是要檢測出這些能表征模型信息的少量關(guān)鍵點，這些特征點能反映模型最基本的形狀。通過提取散亂點云數(shù)據(jù)中的特征點，可為后續(xù)的存儲、簡化、壓縮、匹配等奠定基礎(chǔ)。

在點云數(shù)據(jù)大規(guī)模應(yīng)用之前，特征點檢測大都針對重建后的網(wǎng)格數(shù)據(jù)。文獻(xiàn)[1]使用局部多項式擬合來估算曲率張量信息，將曲率張量用于密集三角形網(wǎng)格的特征檢測。文獻(xiàn)[2]對于多邊形數(shù)據(jù)重建隱函數(shù)模型，從隱函數(shù)模型中計算曲率信息以完成特征檢測。這類方法的缺點是重建過程復(fù)雜，速度較慢，且網(wǎng)格精度得不到保證。

直接從散亂點云模型中提取特征點的文獻(xiàn)相對較少，文獻(xiàn)[3]基于主成分分析提取特征點，用PCA方法計算模型中各點法向量，用協(xié)方差矩陣求取各點曲率信息，僅對均勻數(shù)據(jù)有效。文獻(xiàn)[4-8]基于曲率、法向量等幾何特征提取特征點，其中，文獻(xiàn)[4-5]定義曲率的突變點為特征點，直接根據(jù)每點的曲率值大小完成提取。文獻(xiàn)[6]定義一個由主曲率及高斯曲率組成的品質(zhì)因數(shù)Qk，選取點云中品質(zhì)因數(shù)大于某一閾值的點作為特征點。文獻(xiàn)[7]定義一個特征參數(shù)，該特征參數(shù)綜合考慮鄰近點的平均距離、相鄰點法矢的夾角、數(shù)據(jù)點的曲率等進(jìn)行檢測，需要復(fù)雜的系數(shù)設(shè)置。文獻(xiàn)[8]基于曲率極值完成特征點云的初步與精確篩選，首先求出各點的平均曲率，將平均曲率值大于某一閾值的點篩選出來作為候選特征點，然后在左右臨近點上進(jìn)行極值判定。這類方法的缺點是直接根據(jù)當(dāng)前點的曲率信息完成篩選，受噪聲干擾較大；且需要一定的人機(jī)交互設(shè)置閾值，但是對于不同的點云數(shù)據(jù)，閾值的設(shè)置往往不同，提取到的特征點數(shù)量難以控制，人機(jī)交互效率較低。

本文提出一種基于點簽名的散亂點云特征點檢測方法，不直接對當(dāng)前點進(jìn)行幾何分析，而是通過k鄰近算法，反映出每一個待測點及其k鄰近內(nèi)的均方根曲率信息，避免噪聲點由于曲率突變而被識別為特征點的情況。在點簽名直方圖與色階圖的基礎(chǔ)上，根據(jù)點簽名的均值與方差設(shè)定篩選閾值，提高篩選效率。

2 特征點提取算法

2.1 散亂點云的k鄰近

設(shè)p={x1,x2,…,xn}是散亂點云數(shù)據(jù)的采樣點集，p中與待測點xi歐式距離最近的k個點稱為xi的k鄰近。

本文采用空間柵格劃分的方法來搜索任意點的k鄰近[9]，首先根據(jù)點云的空間分布，形成一個與坐標(biāo)軸平行的長方體包圍盒，在x,y,z這3個方向上按照一定的間隔對包圍盒進(jìn)行柵格劃分，將長方體包圍盒劃分為m×n× l個小立方體柵格，使所有的散亂點云都被劃分在立方體柵格之中。

統(tǒng)計每一個點所在的立方體柵格，將索引號保存在柵格中，遍歷每一個點云數(shù)據(jù)，在其本身及上下左右共27個立方體柵格中搜索k個最近點。

2.2 曲率計算

本文采用二次曲面擬合方法來估算散亂點云模型每點的曲率[10]，設(shè)任意點及其k鄰域所擬合出的二次曲面的初始方程為：

對上式進(jìn)行最小二乘擬合等價于使下式取最小值

對式(2)求導(dǎo)，并使其為0，可以解出方程的系數(shù)b0,b1,b2,b3,b4。繼而二次曲面可表示為參數(shù)方程的形式：

其中，rx,ry,rxx,ryy,rxy為r(x,y)的偏微分；矢量n為曲面的單位法向量，且：

根據(jù)曲面的性質(zhì)，繼而求得：

(1)高斯曲率：

(2)平均曲率：

(3)主曲率：

2.3 點簽名與曲率色階圖

計算完點云模型中每一點的k鄰近與主曲率后，引入點簽名 f(k)，定義：

C表示任意點2個主曲率的均方根。點簽名 f(k)實質(zhì)上表示一個定義在k鄰域上的特征描述子，任意點處的點簽名為該點及其k鄰域內(nèi)均方根曲率的平均值。

設(shè)散亂點集 p={x1,x2,…,xn}中任意點xi上的點簽名為fi(k)，遍歷求取散亂點集中每一點處的點簽名得{f1(k),f2(k),…,fi(k),…,fn(k)}，求出點簽名集中最大點簽名 fmax(k)，對點簽名集做歸一化處理，即：

這里假設(shè)待測點集在xj點處的點簽名取得最大值fmax(k)。每0.001為一個子區(qū)間段，對 f′(k)進(jìn)行區(qū)間劃分，統(tǒng)計落入每一子區(qū)間內(nèi)的點云的個數(shù)。如圖1(a)所示，以斯坦福兔子(40256)模型為例，計算每一 f′(k)區(qū)間內(nèi)點云的數(shù)目，繪出 f′(k)直方圖，其中橫坐標(biāo)表示 f′(k)的區(qū)間段，縱坐標(biāo)代表相應(yīng)區(qū)間內(nèi)所含點云的個數(shù)。在 f′(k)直方圖的基礎(chǔ)之上，繪制 f′(k)色階圖，如圖1(b)所示，根據(jù)落入?yún)^(qū)間的不同，每一點都被賦予相應(yīng)的顏色，綠色代表0，紅色代表1。

為了顯示對比效果，本文采用傳統(tǒng)方法直接對模型中每一點進(jìn)行均方根曲率運算，繪出相應(yīng)的直方圖與色階圖，分別如圖2(a)、圖2(b)所示。

圖1 點簽名直方圖與色階圖

圖2 曲率直方圖與色階圖

從圖1與圖2的效果對比上可以明顯發(fā)現(xiàn)，傳統(tǒng)算法直接計算當(dāng)前點曲率信息，一些點的曲率值非常大，而這部分點的個數(shù)又相對很少，致使歸一化時分母較大，使得在曲率直方圖上，絕大部分的點云分布在0.0～0.2很小的區(qū)間段內(nèi)。而反映在色階圖上，由于曲率極大值點(綠色)的個數(shù)非常少，絕大部分點云的曲率又非常接近，從而造成歸一化色階圖很難體現(xiàn)出對比性，可識別性不強(qiáng)。而采用點簽名的方法，反映出待測點及其周圍鄰域內(nèi)的曲率信息，避免了由于單個點曲率突變而導(dǎo)致歸一化時分母過大的問題，增強(qiáng)了色階圖的對比度與可識別性，同時大大降低了對噪聲的敏感程度(具體在第3節(jié)抗噪性對比中分析)。

2.4 基于正態(tài)分布的閾值設(shè)定

根據(jù)大規(guī)模散亂點云數(shù)據(jù)的 f′(k)近似服從正態(tài)分布這一特點(如圖1(a)所示)。統(tǒng)計點簽名集{f1(k),f2(k),…,fi(k),…,fn(k)}的均值與方差，即：

選擇 fμ(k)+ efσ(k)作為特征閾值，選取點簽名集中f(k)的值大于 fμ(k)+ efσ(k)所對應(yīng)的點云作為候選特征點。這里e為調(diào)整系數(shù)，通過改變e的大小，可以獲取不同數(shù)量的候選特征點，大量實驗表明，當(dāng)e取1時，能夠?qū)⑺崛〉暮蜻x特征點數(shù)目控制在15%以下，通過改變e的大小，直至獲得滿意的特征提取效果。

傳統(tǒng)方法的閾值往往設(shè)定為所有曲率的平均值，不同的點云模型由于其形狀、密度等區(qū)別，使得提取出的大于閾值的特征點個數(shù)難以控制，需要反復(fù)設(shè)定才能獲得滿意的效果。而本文方法通過設(shè)定e的大小可以完成特征點云數(shù)目的初步定位，提高了人機(jī)交互的效率。

2.5 基于方向投影的極值特征點篩選

遍歷候選特征點集之中的每一個元素，如果某一候選特征點的2個主曲率中的任何一個沿其主方向為極值，那么就定義該點為特征點[11]。具體方法為：對于候選特征點集中的某一個特征點 p，沿著其最大主曲率方向矢量Imax，找到左右2個臨近點pmaxL和pmaxR(L和R代表左右2個方向)。PmaxL和pmaxR的判定原則為將p，pmaxL及pmaxR向p點及其k鄰域所擬合的切平面上投影，如圖3所示，得到其投影點p′，pmaxL′和pmaxR′，過 p′點在切平面內(nèi)做平行于矢量Imax的方向矢量Imax′，pmaxL′和pmaxR′分別向矢量Imax′做垂線，垂足到點 p′的距離分別為dmaxL和dmaxR，滿足dmaxL和dmaxR達(dá)到最小的 pmaxL′和pmaxR′所對應(yīng)的投影點pmaxL以及pmaxR即 為2個鄰近點。如果：

其中，Cmax(p),Cmax(pmaxL),Cmax(pmaxR)分別為點p,pmaxL,pmaxR在矢量Imax方向上的均方根曲率，則將該點從候選點集中篩選出來作為特征點。

否則，沿該點的最小主曲率方向矢量Imax，按照類似的方法，找到左右2個鄰近點 pminL和 pminR，當(dāng)Cmin(p)≤ Cmin(pminL)且 Cmin(p)≤ Cmin(pminR)時，也將該點從候選特征點集中篩選出來。

圖3 切平面投影

3 實驗結(jié)果及抗噪性分析

本文在Matlab環(huán)境下實現(xiàn)特征點提取，計算機(jī)硬件為Intel Dual-Core2處理器，2 GB內(nèi)存，2.10 GHz主頻。為了說明本文所使用的特征點提取方法的適用性，采用了不同形狀、排布及疏密程度的多個點云模型進(jìn)行特征點提取，模型來自于斯坦福大學(xué)、西澳大學(xué)、麥吉爾大學(xué)點云數(shù)據(jù)庫，由不同分辨率的激光掃描儀獲得。

3.1 實驗提取效果

圖4為掃描獲得的簡單飛機(jī)模型特征提取效果，該模型點云分布稀疏，表面平滑，如圖4(a)所示，原始模型共含有11078個點，在k=10，e=0.8下特征點提取效果如圖4(b)所示，特征點個數(shù)為2056?？梢钥闯?，飛機(jī)的一些紋理信息可以通過提取到的特征點反映出來。

圖4 飛機(jī)模型及特征點提取

圖5為掃描獲得廚師模型特征點提取效果，如圖5(a)所示，該模型含有特征點69007個，點云分布密集，表面凹凸不平，在k=25，e=1下提取效果如圖5(b)所示，提取特征點6238個，提取出的特征點比較集中地分布在帽子、面部等紋理明顯的地方，較好地反映出模型的基本信息。

圖5 廚師模型及特征點提取

圖6為合成獲得的龍模型特征點提取效果，如圖6(a)所示，模型含有特征點云數(shù)目為100250個，模型表面分布平坦，頭部及身體邊緣錯落排布，在k=25，e=1.1下提取特征點10014個，如圖6(b)所示，本文方法所提取特征點分布在上述特征密集部位，且把光滑非特征區(qū)域區(qū)分出來。

圖6 龍模型及特征點提取

3.2 抗噪性分析

設(shè)p={x1,x2,…,xn}是散亂點云數(shù)據(jù)中某一采樣點集，設(shè) xi=xi′+ξ，其中，xi為點云實際坐標(biāo)；xi′為點云精確坐標(biāo)；ξ代表點云以精確坐標(biāo)為球心的沿任意方向的坐標(biāo)擾動，其宏觀表現(xiàn)為噪聲數(shù)據(jù)。與二維圖像有所區(qū)別，三維點云模型的噪聲主要表現(xiàn)為點云數(shù)據(jù)的坐標(biāo)偏移。為此，本文向點云模型中添加均值為0，方差為ξ的高斯噪聲。具體做法為隨機(jī)選取若干點云數(shù)據(jù)，在x,y,z3個方向上，使每個點云坐標(biāo)分別產(chǎn)生 ξx，ξy，ξz的位置偏移，其偏移大小宏觀上服從高斯分布，每個點云產(chǎn)生ξ的噪聲數(shù)據(jù)，且，方向為3個方向的合成。

為方便控制噪聲干擾的程度，選擇距離場函數(shù)[12]作為噪聲ξ的衡量標(biāo)準(zhǔn)，計算模型中任一點和距其最近點歐氏距離dmin，計算所有dmin的平均值daver，選取不同倍率的daver作為ξ的參照。ξ越大，表明噪聲干擾程度越大。

本文以經(jīng)典的斯坦福兔子模型為例(原始點數(shù)為40256)，隨機(jī)添加3000個噪聲點數(shù)據(jù)，圖7和圖8分別為本文方法與文獻(xiàn)[8]方法在不同程度的噪聲干擾下，對兔子模型的特征點提取效果。圖7(a)～圖7(d)與圖8(a)～圖8(d)表示ξ以距離場為參照，在無噪聲情況，3daver倍率噪聲、5daver倍率噪聲和10daver倍率噪聲下特征點提取效果。

圖7 本文方法在不同噪聲干擾下的特征點提取結(jié)果

圖8 文獻(xiàn)[8]方法在不同噪聲干擾下的特征點提取結(jié)果

表1為本文方法與文獻(xiàn)[8]方法在無噪聲情況下提取的特征點數(shù)與時間對比。

表1 無噪聲情況下特征點提取對比

根據(jù)圖7、圖8以及表1的特征點提取對比，可以發(fā)現(xiàn)：

(1)在無噪聲情況下，文獻(xiàn)[8]方法與本文特征提取方法均可以提取出比較明顯地反映模型幾何信息的特征點集，且運行時間和提取的特征點數(shù)也相當(dāng)。但相比于文獻(xiàn)[8]方法，本文所提取的特征點分布比較集中，雜散孤立點個數(shù)相對較少。

(2)在有噪聲干擾情況下，隨著噪聲干擾程度的不斷加大，文獻(xiàn)[8]方法將很多噪聲點識別為特征點，抗噪性能較差。本文所使用的方法在不同的噪聲干擾下，均能保持相對穩(wěn)定的特征提取結(jié)果，對噪聲敏感度較低。

向原始模型添加噪聲后，一些點云數(shù)據(jù)的坐標(biāo)發(fā)生偏移，由于位置的變動，破壞了原始的存儲結(jié)構(gòu)，產(chǎn)生了許多孤立的點云數(shù)據(jù)。當(dāng)這部分點云數(shù)據(jù)的曲率值非常大時，采用文獻(xiàn)[8]的方法，由于直接根據(jù)當(dāng)前點的曲率信息進(jìn)行特征篩選，就會將這些噪聲數(shù)據(jù)識別為特征點。而本文所采用的基于點簽名的方法，是一個反映鄰域幾何信息的特征描述算符，當(dāng)鄰域內(nèi)有少數(shù)曲率突變噪聲數(shù)據(jù)時，通過點簽名對噪聲極值做了平滑，受噪聲點的干擾相對較小。

4 結(jié)束語

本文提出了一種基于點簽名的散亂點云特征點檢測方法，引入點簽名以反映出鄰域內(nèi)曲率信息，通過點簽名均值與方差設(shè)定曲率閾值。實驗結(jié)果表明，本文所采用的方法降低了特征提取算法對噪聲的敏感程度，提高了人機(jī)交互的效率，是一種有效的特征點檢測算法。在處理數(shù)目特別龐大的點云數(shù)據(jù)時，本文特征點檢測方法時間復(fù)雜度較高，因此下一步的工作重點是提高本文方法特征提取的時間效率，以及將該方法應(yīng)用到后續(xù)的點云存儲、簡化、壓縮、匹配中。

[1]Yoshizawa S,Belyaev A,Seidel H P.Fast and Robust Detection of Crest Lines on Meshes[C]//Proc.of Symposium on Solid and Physical Modeling.Cambridge,USA:ACM Press,2005:269-275.

[2]Ohtake Y.Ridge-valley Lines on Meshes via Implicit Surface Fitting[J].ACM Transactions on Graphics,2004,23(3):609-612.

[3]Yang Yongliang,Lai Yukun,Hu Shimin.Robust Principal Curvatures on Multiple Scales[C]//Proc.of Eurographics Symposium on Geometry Processing.Sardinia,Italy:[s.n.],2006:326-334.

[4]Woo H,Kang E,Wang S.A New Segmentation Method for Point Cloud Data[J].International Journal of Machine Tools and Manufacture,2002,42(2):167-178.

[5]馬驪溟,徐 毅,李澤湘.基于高斯曲率極值點的散亂點云數(shù)據(jù)特征點提取[J].系統(tǒng)仿真學(xué)報,2008,20(9):2341-2344.

[6]Mian A,Bennamoun M,Owens R.On the Repeatability and Quality of Keypoints for Local Feature-based 3D Object Retrieval from Cluttered Scenes[J].International Journal of Computer Vision,2010,89(2):348-361.

[7]王麗輝,袁保宗.三維散亂點云模型的特征點檢測[J].信號處理,2011,27(6):932-938.

[8]王永波,盛業(yè)華.一種基于曲率極值法的LIDAR點云特征提取算法[J].中國礦業(yè)大學(xué)學(xué)報,2011,40(4):640-646.

[9]周儒榮,張麗艷,蘇 旭,等.海量散亂點的曲面重建算法研究[J].軟件學(xué)報,2001,12(2):249-255.

[10]Lin Zeming,He Bingwei.A Curvature-based Automatic Registration Algorithm for the Scattered Points[C]//Proc.of the 3rd International Conference on Measuring Technology and Mechatronics Automation.Shanghai,China:[s.n.],2011:125-132.

[11]Milroy M J,Bradley C,Vickers G W.Segmentation of a Wrap-around Model Using an Active Contour[J].Computeraided Design,1997,29(4):299-320.

[12]Wang Jun,Tan Ying.Efficient Euclidean Distance Transform Algorithm of Binary Images in Arbitrary Dimensions[J].Pattern Recognition,2013,46(1):230-242.