郭建華 呂?？?/p>

(南京航空航天大學(xué)機電學(xué)院 江蘇 南京 210016)

0 引 言

與2D視覺相比,3D視覺具有信息更為豐富全面、光照變化魯棒性強、目標(biāo)空間信息更為直觀準(zhǔn)確等優(yōu)勢。隨著3D數(shù)據(jù)獲取傳感器技術(shù)的迅猛發(fā)展,以及機器學(xué)習(xí)、機器視覺等領(lǐng)域算法技術(shù)的進一步成熟,基于3D視覺的物體識別、場景理解等方面研究熱度與年俱增,其成果在自動化作業(yè)、工業(yè)檢測、機器人導(dǎo)航、虛擬現(xiàn)實、人機交互、遙感測量等領(lǐng)域逐漸得以普及應(yīng)用[1-3]。

興趣點(Interest Point)也稱關(guān)鍵點(Key Point),興趣點提取是3D視覺核心基礎(chǔ)技術(shù)之一。3D點云數(shù)據(jù)興趣點提取即通過一定的檢測算法,從目標(biāo)點云數(shù)據(jù)中提取穩(wěn)定的、標(biāo)志性的特征點,為后續(xù)的物體跟蹤[4]、目標(biāo)配準(zhǔn)[5]、目標(biāo)建模[6]、空間結(jié)構(gòu)描述[7]、物體識別[8]等高層視覺算法服務(wù)。

針對三維模型興趣點的提取,研究人員做了大量的相關(guān)工作。Lee等[9]提出了Mesh Saliency算法,模型中每個頂點的顯著性特征是基于由高斯濾波器加權(quán)得到的平均曲率,根據(jù)所有模型頂點的顯著性特征的局部最大值選擇興趣點。Castellani等[10]提出的Salient Points算法則直接對模型頂點的三維位置進行高斯濾波,其顯著性特征取決于經(jīng)高斯濾波后的頂點與原模型頂點的位移量。Novatnack等[11]提出了尺度依賴(Scale-Depended)的特征檢測方法SD-corner,將三維網(wǎng)格嵌入到二維平面,在二維平面上進行特征檢測后再將特征映射回三維模型,最終識別出模型特征角點,該角點即為興趣點。Sun等[12]提出基于熱量擴散理論的多尺度特征描述算法HKS(Heat Kernel Signature),在模型上采用Laplace-Beltrami算子計算其熱核特征。Sipiran等[13]將經(jīng)典的Harris角點檢測算法擴展到三維上,通過在當(dāng)前頂點及其鄰域上構(gòu)建局部坐標(biāo)系并擬合二次曲面來計算該頂點的Harris響應(yīng),之后根據(jù)局部最大原則選擇興趣點。Godil等[14]也提出了3D Sift算法,該算法首先將3D模型體素化,然后通過高斯差分(Difference of Gaussian,DoG)檢測極值點,最后選擇合適的極值點后將其映射到原模型上作為興趣點。這些算法中常用于點云興趣點檢測的算法是3D Harris和3D Sift算法。為了評價這些算法的性能,Dutagaci等[15]提出了一種評估策略,將算法檢測到的興趣點集與人工標(biāo)注的真實興趣點集相比較。評估結(jié)果表明,3D Sift算法會檢測到許多偏離物體的重要位置的興趣點;HKS算法檢測的興趣點過少;3D Harris 、Mesh Saliency、SD-corners、Salient Points等算法則會漏檢一些重要興趣點。

為了設(shè)計一種更加符合人眼視覺注意力機制的興趣點提取算法,提出一種新的三維點云模型興趣點提取算法。參考人眼識別物體的一些特點,我們認為,錐體是物體邊角的基元特征,點云物體局部幾何特征均可近似表達為該局部區(qū)域的錐度特征:對于物體的型面特征,平面可認為是局部錐度特征為0的特征體,曲面則可認為是由等值或不等值的局部錐度特征集組成的特征體;對于物體的邊角特征,物體的邊緣、棱角、拐角等,均可認為是系列假想椎體(面)的組合,這些椎體(面)可以是規(guī)則的,也可以是不規(guī)則的(圖1)?；谶@個思想,本文:

1) 提出一種新的三維點云數(shù)據(jù)點特征的表達算法,并命名為突出度特征(Saliency Degree,SD)。該特征算法計算點云數(shù)據(jù)中心點與其k近鄰歸一化向量集的平均合向量,搜索歸一化向量集中與合向量最大的夾角,應(yīng)用該夾角與平均合向量二范數(shù)聯(lián)合表達突出度特征,來描述三維點云物體的局部區(qū)域的錐度特征。

2) 提出一種新的興趣點選取算法。算法全局與局部相結(jié)合,分為三步:(1) 基于全局閾值的一次篩選:在突出度特征服從高斯分布的假設(shè)下,設(shè)置經(jīng)驗閾值為均值與標(biāo)準(zhǔn)差的和,突出度特征大于閾值的點為初始興趣點。(2) 基于局部最大原則的二次篩選:基于初始興趣點,選取當(dāng)前點及其k近鄰點中具有最大突出度特征的點,作為代表當(dāng)前點的候選興趣點。每次候選興趣點提取操作后給予該興趣點1次投票。(3) 基于投票數(shù)的最終篩選:設(shè)定票數(shù)閾值,按得票數(shù)量進行最終興趣點篩選。

(a) 平面 (b) 曲面

(c) 邊緣和拐角 (d) 圓錐面頂點圖1 物體的錐度特征

1 算法描述

1.1 計算點的突出度特征

設(shè)點云數(shù)據(jù)集P={pm,m=0,1,…,n-1},當(dāng)前點為Pi,首先使用KD-Tree算法[16]獲得其k個近鄰點,設(shè)其近鄰點集合為N(i),則分三步計算該點的突出度特征:

第1步計算點Pi與其近鄰點的平均合向量,對于N(i)中每一點Pj,設(shè)點Pj指向當(dāng)前點Pi的向量為vji,將vji歸一化為單位向量uji,獲得向量集V={uji,pj∈N(i),j≠i},設(shè)當(dāng)前點Pi的k個近鄰點的平均合向量為vi(如圖2所示),則:

圖2 合向量示意圖

第2步計算點Pi的局部錐度特征,將vi歸一化為單位向量ui,分別計算V中各向量與ui的內(nèi)積(即V中各向量與ui的夾角余弦值),獲得內(nèi)積集合I={cji,pj∈N(i),j≠i}。

選擇I中的最小值ci:

ci為點Pi與其近鄰點的差向量中偏離其平均合向量的最大夾角的余弦值(見圖2)。稱ci為點Pi的局部錐度特征(Local Conicity,LC)。ci是一個重要的特征,其大小近似反映了錐面錐度的大小,其正負則反映了錐面的外凸或內(nèi)凹特征,如果ci>0表示Pi點附近區(qū)域具有外錐面特征,如果ci<0則表示Pi點附近區(qū)域具有內(nèi)錐面特征。

第3步計算點Pi的突出度特征,定義點Pi的突出度特征(Saliency Degree)Sdpi為:

1.2 選擇興趣點

按上述步驟計算所有點的Sd值后,從全局和局部兩方面比較各點Sd值選擇最終的興趣點。

首先計算全局閾值,確定初始興趣點。由于興趣點是那些幾何特征比較明顯的點,所以先從全局考慮,選擇那些突出度特征值(Sd)較大的點作為初始的興趣點。假設(shè)三維點云物體各點Sd值近似服從高斯分布N(μ,σ2),計算整個點云中Sd值的均值μ與標(biāo)準(zhǔn)差σ,定義全局閾值t為:

t=μ+σ

(4)

獲得初始的興趣點集合:

S1={pm|pm∈P,Sdpm≥t}

(5)

然后按局部最大原則,確定候選興趣點。對于S1中每一點pm,搜索其自身及其k個近鄰點中Sd值最大的點,作為該點的代表興趣點。pm的代表興趣點表示為:

將所有代表點作為候選興趣點集合S2。易知當(dāng)pm的Sd值在其近鄰區(qū)域中最大時,pmax(m)即為pm自身。而且會出現(xiàn)多個點擁有同一個代表點的情況,一個點被當(dāng)作代表點的次數(shù)越多,說明該點在其局部區(qū)域內(nèi)越重要。在得到pm的代表興趣點的同時,將點pmax(m)的票數(shù)vote(pm)加1,投票之前,先將所有初始興趣點pm的票數(shù)vote(pmax(m))設(shè)置為0。

最后我們根據(jù)得票數(shù)量進行最終興趣點的篩選,與物體表面非特征候選興趣點相比,物體的邊緣、邊角、拐角等部分的候選興趣點一般具有較高的得票。根據(jù)經(jīng)驗,將興趣點票數(shù)閾值設(shè)為k/5,其中k為近鄰點的個數(shù)。則最終興趣點集合S表示為:

1.3 算法流程

綜上所述,算法具體步驟如下:

(1) 對于點云數(shù)據(jù)P,搜索每個點的k近鄰,構(gòu)建鄰接矩陣An×n,計算得到向量差矩陣Bn×n×3。

(3) 計算近鄰差向量的平均合向量二范數(shù)張量Vn×1,及合向量歸一化矩陣Un×3。

(5) 計算Vn×1與Cn×1的Hadamard積,得突出度特征張量Sdn×1。

(6) 獲得Sd張量的均值與標(biāo)準(zhǔn)差,確定閾值t←μ+σ。

(9) 搜索S″中vote值大于k/5的點,獲得興趣點集張量S。

2 基于單位圓的點云突出度相關(guān)特征模擬

由于本文算法首先將點云數(shù)據(jù)每一點與其近鄰的差向量歸一化后再進行計算,這里以分布于單位圓上的點來模擬當(dāng)前點的近鄰點,以該單位圓圓心表示當(dāng)前點,此時差向量均為單位向量。

采用兩種方式對算法性能進行了模擬:

圖3 方法1示意圖

圖4 方法1模擬結(jié)果

方法2:仍以1°為步長,選取一差向量為0°起始邊,分別計算0°～359°錐角下方法1中所列的參數(shù)。計算某一錐角θ的系列參數(shù)值時,以在單位圓上按1°步長均布的360個點為候選近鄰點,設(shè)定近鄰數(shù)k,在確定了錐角θ的起始、終止向量邊(近鄰點)后,在錐角θ所包絡(luò)的候選點中隨機選取k-2個近鄰點,由于選取過程隨機,故極有可能產(chǎn)生點的復(fù)選現(xiàn)象,進而有可能導(dǎo)致近鄰點分布的極度不均(圖5),這有利于檢驗算法的魯棒性。模擬結(jié)果如圖6所示。

圖5 方法2示意圖(k=10)

圖6 方法2模擬結(jié)果

由圖3可看出,隨著錐角θ的增大,當(dāng)前點位置的局部錐度在減小,其對應(yīng)的突出度特征值也在減少(見圖4),當(dāng)θ接近360°時,表示當(dāng)前點位于錐度為0的平面,圖4中算法的各項參數(shù)值也達到最小。圖6顯示,在近鄰點分布極度不均的情況下,算法的各項參數(shù)對應(yīng)的曲線會有較大的波動,但是所有曲線的整體趨勢仍與原曲線相同,其中,突出度特征值對應(yīng)的曲線所受影響最小。

由兩種方法的模擬結(jié)果可以看出,本文算法所描述錐度特征較為準(zhǔn)確。方法2的隨機模擬中,在近鄰點分布極度不均的情況下,大多數(shù)情況下仍能獲得正確的特征描述結(jié)果。

3 點云物體興趣點檢測實驗

3.1 算法評價模型

為評估三維點云興趣點提取算法的性能,采用Dutagaci等[4]提出的評價模型。將算法檢測到的興趣點集與人工標(biāo)注的真實興趣點集相比較,若兩者越接近,則算法的性能越優(yōu)秀。通過缺失率(False Negative Errors,FNE)和誤報率(False Positive Errors,FPE)兩個指標(biāo)來衡量算法提取的興趣點集與真實興趣點集的接近程度。

以真實興趣點集為基準(zhǔn),計算算法的缺失率(FNE)和誤報率(FPE)。由于算法提取的興趣點與對應(yīng)位置的真實興趣點往往存在小的位置偏差,即相互近鄰但不是同一點。鑒于此,對模型中的真實興趣點g,定義容忍半徑系數(shù)r,則點g的近鄰點集合Gr(g)為:

Gr(g)={p∈M}|d(g,p)≤rR

(8)

式中:R為點云模型的半徑(三維點云模型中相距最遠的兩個點的距離的一半);d(g,p)為點g和點p之間的距離。若點云中某點a被算法提取到,a與真實值中點g的距離最近,且a∈Gr(g),則表明該算法成功提取到真實興趣點g。

設(shè)在容忍半徑系數(shù)為r時,算法A成功提取到的真實興趣點數(shù)量為NC,真實興趣點的個數(shù)為NG,算法提取到的興趣點的總個數(shù)為NA,則算法A的缺失率(FNE)為沒有被算法所提取到的真實興趣點的個數(shù)與真實興趣點個數(shù)的比率:

算法A的誤報率(FPE)為算法提取的非真實興趣點的個數(shù)與算法提取的所有興趣點個數(shù)的比率:

3.2 實驗結(jié)果分析

選取普林斯頓大學(xué)視覺與機器人實驗室發(fā)布的3D點云數(shù)據(jù)集ModelNet40[17]中的部分物體進行測試。該數(shù)據(jù)集含40個類別11 308個3D點云模型,選擇其中的四個模型,飛機、椅子、電腦和人。

參照Dutagaci等提出的方法[4],組織22名志愿者對選取的點云物體進行了真實值標(biāo)注。由于志愿者對三維模型興趣點標(biāo)注具有較大的主觀性,不同的志愿者可能會標(biāo)注同一個位置而非同一個點,為綜合考慮各個志愿者的意見,得到最符合人類視覺的興趣點集,將相互距離小于0.04r的興趣點(由不同志愿者標(biāo)注)合并為一組,若組中興趣點被標(biāo)記的總次數(shù)少于7,則丟棄該組。在興趣點組中選擇一個中心點設(shè)置為該組的代表興趣點,該中心點到組中其余興趣點之間的距離之和最小。將這些代表點作為最終的人工標(biāo)注的真實興趣點集(Ground Truth)。

基于真實興趣點集,對本文算法以及常用的點云興趣點檢測算法3D-Sift和3D-Harris算法進行了測試,檢測效果如圖7-圖10所示,依次為Ground Truth和各算法在飛機、椅子、電腦、人模型上所提取的興趣點。

(a) Ground Truth (b) 3D-Sift算法

(c) 3D-Harris算法 (d) 本文算法圖7 飛機模型上的興趣點提取結(jié)果

(a) Ground Truth (b) 3D-Sift算法

(c) 3D-Harris算法 (d) 本文算法圖8 椅子模型上的興趣點提取結(jié)果

(a) Ground Truth (b) 3D-Sift算法

(c) 3D-Harris算法 (d) 本文算法圖9 電腦模型上的興趣點提取結(jié)果

(a) Ground Truth (b) 3D-Sift算法

(c) 3D-Harris算法 (d) 本文算法圖10 人模型上的興趣點提取結(jié)果

可以看出,Ground Truth中絕大多數(shù)的點都位于物體邊緣和拐角位置,如飛機機翼、椅子和電腦的邊緣和頂點處、人的頭部和腳部的位置,本算法(Sd)基本能夠全部檢測到這些興趣點,而3D-Sift和3D-Harris算法對于這些興趣點卻多有漏檢的情況。由于這些點的位置的錐度特征明顯,突出度特征值比較大,因而容易被本文算法檢測到。少量真實興趣點位于物體表面比較平緩的位置,如飛機機身、電腦屏幕和椅子靠背中央處的點,這些點的錐度特征并不明顯,但是在表達整個物體結(jié)構(gòu)時具有重要作用,由于其突出度特征值比較小,本文算法并不能夠很好地檢測到。

圖11-圖14依次顯示了各算法的興趣點提取性能在四個模型上的定量比較結(jié)果。FNE反映算法提取真實興趣點的能力,其值越低,表明算法提取到的真實興趣點就越多,提取能力越強。而FPE反映算法提取真實興趣點的錯誤率,其值越低,表明算法提取到的非真實興趣點越少。隨著容忍半徑系數(shù)r的增大,真實興趣點能被檢測到的范圍擴大,因此各算法的FNE和FPE值也隨之降低。

(a) 缺失率(FNE)

(b) 誤報率(FPE)圖11 各算法在飛機模型上的定量比較結(jié)果

(a) 缺失率(FNE)

(b) 誤報率(FPE)圖12 各算法在椅子模型上的定量比較結(jié)果

(a) 缺失率(FNE)

(b) 誤報率(FPE)圖13 各算法在電腦模型上的定量比較結(jié)果

(a) 缺失率(FNE)

可以看出,本文算法(Sd)的FNE曲線要明顯低于3D-Sift和3D-Harris算法。這是由于絕大多數(shù)真實興趣點都位于物體的邊緣和拐角處,而這些點能夠全部被本文算法檢測到,只有極少數(shù)錐度特征不明顯的興趣點被本文算法漏檢,3D-Sift和3D-Harris算法漏檢的興趣點則比較多。而且在多數(shù)情況下本文算法的FPE值也要略低于3D-Sift和3D-Harris算法。因此,整體上本文算法要明顯優(yōu)于3D-Sift和3D-Harris算法,所提取的興趣點與Ground Truth更接近,更符合人類視覺。

4 結(jié) 語

本文提出錐體為三維物體邊角基元特征的思想,基于點云數(shù)據(jù)點與其k近鄰歸一化向量集的合向量,構(gòu)建突出度特征值,對點云物體的局部錐度進行描述。將全局閾值與局部最大原則相結(jié)合,應(yīng)用投票方式進行趣點的選取。實驗結(jié)果表明,本文算法能夠較好地檢測到大部分真實興趣點(位于物體邊緣和拐角處的興趣點),算法整體性能要優(yōu)于3D-SIFT和3D-Harris算法,所提取的興趣點與Ground Truth更加接近。

未來主要考慮開展兩個方面的工作:(1) 優(yōu)化算法,有效提取到錐度特征不明顯但在表達整個物體的結(jié)構(gòu)時具有重要作用的興趣點;(2) 借鑒人眼視覺邊緣感知機制,設(shè)計興趣點連接算法,以提取物體邊緣輪廓、紋理等特征。