賈丁凡 謝曉堯 劉 嵩
(貴州師范大學(xué) 貴州省信息與計算重點(diǎn)實驗室, 貴陽 550001)
利用3D測量技術(shù)可以獲得物體的三維表面信息。3D模型的特征提取,在數(shù)字模型的表示、理解和識別中起著重要作用[1]。點(diǎn)云模型特征提取關(guān)鍵的問題是構(gòu)造特征點(diǎn)識別算子。目前,已經(jīng)有許多學(xué)者對此進(jìn)行了研究?,F(xiàn)有的檢測算法可分為2類:一是基于曲率或表面變化的檢測方法。比如劉致遠(yuǎn)等人提出的地下管廊特征線提取方法[2],首先使用LiDAR獲得地下管廊原始點(diǎn)云數(shù)據(jù),然后利用所提算法找出含有管廊整體輪廓信息的面狀點(diǎn)云,最后基于PCA算法,通過設(shè)定角度閾值去提取輪廓數(shù)據(jù)。二是基于法線量的檢測方法。比如Wang Lihui等人提出的基于曲率和法向矢量的特征點(diǎn)檢測方法[3],趙春海提出的基于法向量波動情況劃分關(guān)鍵點(diǎn)的方法[4]。
為了提高點(diǎn)云特征提取的準(zhǔn)確性和計算速度,現(xiàn)提出一種基于法向量和投影平面的特征提取方法。首先根據(jù)矢量分布和聚類的性質(zhì)提取輪廓點(diǎn),然后根據(jù)矢量偏轉(zhuǎn)角和距離對特征點(diǎn)進(jìn)行排序,從而提取點(diǎn)云特征。
首先,使用加權(quán)主成分分析法(WPCA)計算法線向量,由此構(gòu)建投影平面。然后,搜索檢查點(diǎn)的最鄰近點(diǎn),并將它們投影到投影平面上。在檢查點(diǎn)及其每個相鄰點(diǎn)之間構(gòu)造一個矢量,分析該點(diǎn)鄰域的幾何特性。計算矢量的方位角,并將其分布用于檢測物體的邊界點(diǎn)。最后,使用k均值聚類法對檢查點(diǎn)的相鄰單位法線向量進(jìn)行聚類,并根據(jù)聚類數(shù)檢測折疊點(diǎn)。利用兩個相鄰向量的偏轉(zhuǎn)角和兩個相鄰點(diǎn)之間的距離,來確定點(diǎn)的幾何順序。三維點(diǎn)云模型特征提取過程如圖1所示。
圖1 特征提取流程
使用最近鄰搜索(KNNS)方法,搜索檢查點(diǎn)P0的k個相鄰點(diǎn),并根據(jù)WPCA確定法線向量。法線向量垂直于投影平面。投影平面上,任意一點(diǎn)的坐標(biāo)為(x,y,z)。將投影平面在點(diǎn)P0處的法線向量表示為n=(A,B,C);將檢查點(diǎn)P0的坐標(biāo)表示為(X0,Y0,Z0)。于是有:
A(x-X0)+B(y-Y0)+C(z-Z0)=0
(1)
令第j個相鄰點(diǎn)(Xj,Yj,Zj)在投影平面上的投影點(diǎn)坐標(biāo)為(xj,yj,zj),則相鄰點(diǎn)與投影點(diǎn)的關(guān)系為:
(2)
其中,
(3)
即投影點(diǎn)Pj的坐標(biāo)表達(dá)式如(4)。
(4)
檢查點(diǎn)P0與第j個相鄰點(diǎn)的投影點(diǎn)Pj之間的向量為:
Pj=(xj-X0,yj-Y0,zj-Z0)
(5)
為了確定由檢查點(diǎn)和相鄰點(diǎn)構(gòu)成的矢量的方位角的分布特性,在投影平面上建立二維坐標(biāo)系。將P0設(shè)置為坐標(biāo)系的原點(diǎn),將線段從原點(diǎn)延伸到投影點(diǎn)P1(x1,y1,z1)并形成y′軸。y′軸的形成要滿足x′軸、y′軸和法線向量n之間的右手定則,即x′坐標(biāo)單位矢量e1為:
(6)
使用正交關(guān)系,可通過以下公式計算y′坐標(biāo)單位向量e2:
(7)
(8)
(9)
(10)
然后,通過式(11)計算相鄰方位角的差。
(11)
關(guān)于圖像中折疊點(diǎn)的提取方法,國內(nèi)外諸多學(xué)者已經(jīng)對其進(jìn)行了研究?;谕队暗奶崛》椒ǎ队板e誤就會導(dǎo)致特征點(diǎn)檢測錯誤。基于曲率的提取方法[5],計算曲率又需要大量時間。我們認(rèn)為,可以按下述方法來提取3D折疊點(diǎn)。
第一,通過最近鄰搜索,確定每個檢查點(diǎn)的最近鄰點(diǎn)。相鄰的三角形,由檢查點(diǎn)和2個最近的相鄰點(diǎn)組成。
第二,檢查點(diǎn)P0和最近的相鄰點(diǎn)Pi及Pi-1形成的平面,其法線向量由式(12)確定。因此,可按式(13)得到單位法向矢量ej。
(12)
(13)
第三,采用基于最小生成樹的改進(jìn)法向量矢量[6]重定向的方法,來確定法向量的方向。
第四,采用k均值聚類算法對單位法向矢量進(jìn)行聚類,然后根據(jù)最佳聚類數(shù)確定折疊點(diǎn)。當(dāng)檢查點(diǎn)在平面上時,最佳群集數(shù)為1。
第五,利用聚類有效性指數(shù)判斷聚類的有效性,從而進(jìn)一步確定聚類的最佳數(shù)量。
通過實驗主要分析上述方法在ModelNet數(shù)據(jù)集上的有效性。ModelNet數(shù)據(jù)集共有662種目標(biāo)分類,127 915個CAD,10類標(biāo)記過方向的數(shù)據(jù)。實驗在一臺裝有Ubuntu 18.04系統(tǒng)的計算機(jī)上進(jìn)行,計算機(jī)的配置為:英特爾i7-6700 CPU,英偉達(dá)GTX 1080 GPU,8 GB運(yùn)行內(nèi)存。實驗中提取的點(diǎn)云均使用Open3D進(jìn)行可視化。
對ModelNet數(shù)據(jù)集中的凳子、書架、椅子、杯子、吉他的mesh模型,隨機(jī)抽取100 000個點(diǎn)云,采用我們提出的方法(簡稱“法向量和投影平面法”)對其進(jìn)行特征提取,同時也用文獻(xiàn)[7]的“基于曲率”的方法和文獻(xiàn)[8]的“基于法向量”的方法來進(jìn)行特征提取。實驗結(jié)果如圖2至圖6所示。相對而言,法向量和投影平面法具有更好的特征識別度,對凳子的凳腳、平面的梁,書架的整體框架、邊框、藏書格子,椅子的把手、靠背,均做到了更為準(zhǔn)確的識別和提取。對于杯子,各種算法都沒有提取到杯子底座,但法向量和投影平面法提取到了杯子邊緣特征。對于吉他,只有法向量和投影平面法提取到了其邊緣特征??梢妼ι钪谐R娢矬w表面輪廓特征的提取,法向量和投影平面法有一定的優(yōu)勢。
圖2 凳子點(diǎn)云特征提取的可視化效果
圖3 書架點(diǎn)云特征提取的可視化效果
圖4 椅子點(diǎn)云特征提取的可視化效果
圖5 杯子點(diǎn)云特征提取的可視化效果
圖6 吉他點(diǎn)云特征提取的可視化效果
在點(diǎn)云特征提取算法中多數(shù)是針對稀疏點(diǎn)云的,往往不適合百萬點(diǎn)云以上的大規(guī)模點(diǎn)云。為了驗證法向量和投影平面法在密集點(diǎn)云特征提取中的性能,我們運(yùn)用三維激光掃描儀得到的佛像點(diǎn)云數(shù)據(jù)進(jìn)行了實驗。掃描得到的佛像外觀表面共計有1 501 455個點(diǎn)。實驗結(jié)果如圖7所示。從圖中可以看出,法向量和投影平面法對佛像的整體輪廓具有更好的特征識別度,能夠提取出佛像佛光的特征。另外,從計算結(jié)果來看,采用法向量和投影平面法,提取的點(diǎn)云數(shù)量相對較少、運(yùn)行時間較短、運(yùn)算效率較高(見表1)。
圖7 佛像點(diǎn)云特征提取的可視化效果
表1 計算效率對比
為了提高點(diǎn)云特征提取的準(zhǔn)確性和運(yùn)算速度,采用基于法向量和投影平面的提取方法,首先根據(jù)矢量分布和聚類的性質(zhì)提取輪廓點(diǎn),然后根據(jù)矢量偏轉(zhuǎn)角和距離對特征點(diǎn)進(jìn)行排序,從而提取點(diǎn)云特征。在ModelNet數(shù)據(jù)集上的應(yīng)用結(jié)果表明,對于生活中常見物體的表面輪廓,這種方法具有較好的特征識別度;在三維激光掃描的佛像密集點(diǎn)云上,這種方法對佛像的整體輪廓具有相對更好的特征識別度,而且提取的點(diǎn)云數(shù)量相對較少、運(yùn)行時間較短、運(yùn)算效率較高。