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

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

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

1 概述

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

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

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

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

2 特征點提取算法

2.1 散亂點云的k鄰近

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

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

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

2.2 曲率計算

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

對上式進行最小二乘擬合等價于使下式取最小值

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

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

根據曲面的性質，繼而求得：

(1)高斯曲率：

(2)平均曲率：

(3)主曲率：

2.3 點簽名與曲率色階圖

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

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

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

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

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

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

圖2 曲率直方圖與色階圖

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

2.4 基于正態分布的閾值設定

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

選擇 fμ(k)+ efσ(k)作為特征閾值，選取點簽名集中f(k)的值大于 fμ(k)+ efσ(k)所對應的點云作為候選特征點。這里e為調整系數，通過改變e的大小，可以獲取不同數量的候選特征點，大量實驗表明，當e取1時，能夠將所提取的候選特征點數目控制在15%以下，通過改變e的大小，直至獲得滿意的特征提取效果。

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

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

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

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

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

圖3 切平面投影

3 實驗結果及抗噪性分析

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

3.1 實驗提取效果

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

圖4 飛機模型及特征點提取

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

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

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

圖6 龍模型及特征點提取

3.2 抗噪性分析

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

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

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

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

圖8 文獻[8]方法在不同噪聲干擾下的特征點提取結果

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

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

根據圖7、圖8以及表1的特征點提取對比，可以發現：

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

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

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

4 結束語

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

[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]馬驪溟,徐 毅,李澤湘.基于高斯曲率極值點的散亂點云數據特征點提取[J].系統仿真學報,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]王永波,盛業華.一種基于曲率極值法的LIDAR點云特征提取算法[J].中國礦業大學學報,2011,40(4):640-646.

[9]周儒榮,張麗艷,蘇 旭,等.海量散亂點的曲面重建算法研究[J].軟件學報,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.