基于點云聚類的垛型角點檢測方法

張長勇，馮 冰，陳治華

（中國民航大學(xué) 電子信息與自動化學(xué)院，天津 300300）

0 引 言

目前，國內(nèi)民航運輸市場正處于快速發(fā)展階段，不斷增長的貨物運輸量，對機(jī)場的自動化水平提出了更高的要求，然而在多數(shù)機(jī)場的實際運行中，貨物運輸?shù)难b卸部分仍由人工操作完成。

為改善這一情況，在線碼垛機(jī)械臂的研究和應(yīng)用對實現(xiàn)貨物運輸?shù)淖詣踊b卸至關(guān)重要。為減少碼垛過程中貨物滑落、材質(zhì)變形等對垛型的影響，本文針對垛型點云的角點檢測展開研究，為碼垛規(guī)劃算法提供了真實的垛型空間模型，增強(qiáng)了碼垛規(guī)劃算法[1]的工程實踐性。

近年來，國內(nèi)外許多學(xué)者對點云的角點檢測展開了研究。文獻(xiàn)[2]對獲取的三維點云進(jìn)行邊界提取、直線分割和直線擬合等過程，提取角點坐標(biāo)；文獻(xiàn)[3?4]認(rèn)為角點在兩條或三條直線的交點處；文獻(xiàn)[5]將點云轉(zhuǎn)化成對應(yīng)的深度圖，采用直線求交點的方法獲取角點；文獻(xiàn)[6]在室內(nèi)門窗的三維點云模型中，采用點云轉(zhuǎn)2D圖像再與三維點云相結(jié)合的方法提取角點；文獻(xiàn)[7]采用3D Harris角點檢測的方法提取航天器的角點；文獻(xiàn)[8]利用法向聚類和平面擬合篩選特征點，認(rèn)為三個面的交點為角點；文獻(xiàn)[9]提出一種基于局部重建的方法提取特征點，該方法利用共享近鄰算法對局部三角形內(nèi)的法向進(jìn)行聚類，確定平面擬合的個數(shù)，認(rèn)為同時屬于2個面以上點為角點；文獻(xiàn)[10]等采用高斯法向聚類的方法提取特征點，依據(jù)局部區(qū)域內(nèi)法向聚類的個數(shù)判定特征點；文獻(xiàn)[11]采用平面相交聚類分析的方法提取特征點。

綜上所述，文獻(xiàn)[2?4]采用直線求交點的方法，該方法對直線的擬合精度要求較高；文獻(xiàn)[5?6]采用點云與深度圖相結(jié)合的方法，該方法刪除了高度信息，無法區(qū)分不同水平面的貨物角點；文獻(xiàn)[7?11]依據(jù)點云法向的變化信息檢測角點，該方法適合于三個相交平面的點云均已獲取的情況。

為了解決上述方法在垛型角點檢測中的不足，本文在已獲取垛型邊界三維點云信息的基礎(chǔ)上，分析了垛型角點在平面點云中呈現(xiàn)的角度特性，提出了一種基于點云聚類的垛型角點檢測方法。

1 垛型角點檢測方法

1.1 候選角點獲取

在提取候選角點時，本文采用輪廓尖銳度角點檢測算法[12]中角度閾值檢測的思想，并對其依據(jù)支撐臂長計算角度的方法進(jìn)行改進(jìn)。首先從垛型的三維點云邊界上任選三維點A（如圖1所示），然后通過三維kd?tree的半徑搜索，得到以A為圓心，r為半徑的圓內(nèi)三維點云。

圖1 垛型邊界點云數(shù)據(jù)局部放大圖

將圖1中圓內(nèi)部A點兩側(cè)的點降維成二維點，并采用隨機(jī)采樣一致性算法在A的兩側(cè)分別擬合出一條左直線與一條右直線。然后，依據(jù)如下公式計算兩直線夾角α的余弦值。

設(shè)兩直線的擬合方程為：

則：

式中：n1為直線l1的法向量；n2為直線l2的法向量。根據(jù)理想角點處的角度特征，垛型角點處cosα的值接近于零。定義一個變量S=1-cosα，S值越大，說明該點越有可能成為候選角點。計算垛型邊界數(shù)據(jù)集B={X i}上每一個點的S值，設(shè)定閾值T，當(dāng)S(X i)>T時，將X i標(biāo)記為候選角點。

改進(jìn)的尖銳度角點檢測算法會抑制部分普通邊界點被誤判為角點的情況。如圖2所示的普通邊界點B，采用尖銳度角點檢測算法得到的角度近似為直角（如兩虛線構(gòu)成的夾角所示），判定B為角點；采用改進(jìn)算法擬合的兩直線接近平行（如直線l1與l2所示），判定B為邊界點。由此可知，改進(jìn)角點檢測算法會在一定程度上減少普通邊界點被誤判為角點的數(shù)量。

圖2 角點誤判示意圖

1.2 候選角點聚類

采用改進(jìn)的尖銳度角點檢測算法時，會在同一角點區(qū)域獲得多個符合判定條件的點，從而得到存在冗余點的候選角點。為了對屬于同一角點區(qū)域的候選角點進(jìn)行合并計算，通過改進(jìn)的快速密度峰值搜索算法（Clustering by Fast Search and Find of Density Peaks，CFSFDP）結(jié)合K?means算法對候選角點進(jìn)行聚類，以區(qū)分不同角點區(qū)域的候選角點。

1）改進(jìn)的CFSFDP算法自動確定簇中心點

CFSFDP算法[13]假設(shè)簇中心是局部密度最大值，并且簇中心遠(yuǎn)離其他更高密度的點，為了尋找符合假設(shè)的簇中心點，計算局部密度ρi與相對距離δi，然后依據(jù)ρi，δi畫出決策圖，最后人為依據(jù)決策圖將局部密度和相對距離同時較大的數(shù)據(jù)點作為簇中心點。文獻(xiàn)[14?15]計算一個將ρ值和δ值綜合考慮的變量γ，γi=ρiδi，然后，通過人工觀測或利用γ值存在非線性變化這一特征來區(qū)分簇中心點與非簇中心點。

本文對排除離群點的γ值降序排列后，發(fā)現(xiàn)在簇中心點之間，非簇中心點之間，γiγi+1值變化平緩，但從簇中心點過渡到非中心點時，會出現(xiàn)較大的跳躍。因此，定義如下中心判別式以實現(xiàn)中心點的自動提?。?/p>

根據(jù)上述判別式可以得出，maxβ對應(yīng)的點即為簇中心與非簇中心的區(qū)分點，排在最大值之前的點即為簇中心點。

2）CFDP結(jié)合K?means聚類候選角點

K?means聚類算法需要隨機(jī)選取k個點作為初始聚類中心進(jìn)行迭代操作，但由于垛型的角點個數(shù)未知，無法初始化k值。因此，通過改進(jìn)的CFDP算法對候選角點進(jìn)行預(yù)處理，將獲得的簇中心點作為K?means的初始聚類中心，以保證K?means的聚類效果。融合算法具體的步驟如下：

Step1：改進(jìn)的CFDP初始化K?means的k值與初始聚類中心C={C1,C2,…,C k}。Step2：計算候選角點中點與聚類中心的距離，將其劃分到距離其最近的聚類中心所屬的集合，分配依據(jù)為：

式中：s i為第k類候選角點；j=1，2,…,N；i=1,2,…,k；p≠i；t為時刻。

Step3：根據(jù)Step2的分配結(jié)果，更新聚類中心：

Step4：若前后兩次聚類中心的差值小于設(shè)定的閾值ε，即，則算法結(jié)束；否則，轉(zhuǎn)向Step2。

1.3 候選角點合并

通過CFDP?K?means算法對垛型候選角點進(jìn)行聚類，得到同一角點區(qū)域的候選角點。假設(shè)同一角點區(qū)域候選角點的集合為H：

h1(x1,y1,z1),h2(x2,y2,z2),…,h n(x n,y n,z n)∈H,n≥2 （7）式中n表示同一角點區(qū)域候選角點的個數(shù)。通過密度值法[12]計算同一角點區(qū)域內(nèi)每個候選角點的密度值，采用點h(xmaxρx,ymaxρy,zmaxρz)作為垛型最終角點坐標(biāo)。其中，xmaxρx表示在x方向上取密度值最大的x作為最終角點坐標(biāo)的x值，同理可得ymaxρy,zmaxρz。

綜上所述，本文方法流程圖如圖3所示。

2 實驗結(jié)果分析

為驗證本文方法的可行性，采用Kinect一代相機(jī)，分辨率為640×480的深度像機(jī)獲取垛型的三維點云數(shù)據(jù)。采用C++編程語言，VS2015編譯環(huán)境，在硬件參數(shù)Intel CoreTMi5?7200U CPU@2.50 GHz 4.00 GB，WIN10 x64操作系統(tǒng)進(jìn)行實驗。

實驗搭建如圖4所示的紙箱垛型，在其上方高約1.4 m的位置安裝一臺相機(jī)，通過直通濾波得到對應(yīng)的三維點云如圖5所示。

2.1 候選角點分析

1）候選角點提取分析

采用改進(jìn)的尖銳度角點檢測算法提取垛型的候選角點，以90°-6×n≤α≤90°+6×n（n=0，1，2，3）為α變化范圍；r=10+10×n（n=0，1，2），為r的取值進(jìn)行實驗。不同參數(shù)下的提取狀況如表1所示，其中部分參數(shù)下的提取效果圖如圖6所示。

圖3 本文方法流程圖

圖4 實驗垛型圖

圖5 垛型三維點云圖

由表1可知，角點的個數(shù)隨著r值的增加與α范圍的增大而增多；由圖6的效果圖可以看出，圖6a）比圖6b）的候選角點數(shù)量少，且圖6a）比圖6b）漏檢了4個角點區(qū)域；圖6c）與圖6b）相比，圖6c）中出現(xiàn)大量邊界點。因此，選取r=20，α=84°~96°為角點檢測的參數(shù)范圍。

表1 不同參數(shù)下候選角點提取效果對比

圖6 部分參數(shù)下的候選角點效果圖

2）候選角點聚類分析

由CFDP算法獲得候選角點的簇中心點，如圖7中的“+”所示，從圖7中可以看出，14個候選角點區(qū)域獲得了14個初始簇中心，驗證了CFDP算法在候選角點數(shù)據(jù)集上的有效性。

圖7 初始簇中心

候選角點集的聚類結(jié)果如圖8所示，從圖8中可以看出，14個候選角點區(qū)域中每一個區(qū)域內(nèi)的點都具有相同形狀的符號，驗證了CFDP?K?means算法的良好聚類結(jié)果。

圖8 候選角點聚類結(jié)果

2.2 誤差分析

將本文算法計算的角點坐標(biāo)與人工測量的角點坐標(biāo)進(jìn)行對比，并計算估計誤差，以驗證本文所提算法的準(zhǔn)確性。估計誤差計算公式為：

式中：e表示估計結(jié)果誤差值；(x,y,z)為角點的真實坐標(biāo)值；(x?,y?,z?)是計算的角點坐標(biāo)，誤差結(jié)果如表2所示。

從表2可以看出，通過本文所提方法計算的垛型角點坐標(biāo)誤差在8 mm以內(nèi)。這是由于前期采用的數(shù)據(jù)預(yù)處理以及邊界提取的方法還有待改善，導(dǎo)致進(jìn)行垛型角點檢測時出現(xiàn)一定的誤差。

表2 貨物垛型對應(yīng)的角點坐標(biāo)數(shù)據(jù) mm

3 結(jié) 論

本文主要研究垛型的角點檢測，提出一種基于點云聚類的垛型角點檢測方法。該方法在已獲取垛型邊界三維點云信息的基礎(chǔ)上，依據(jù)局部區(qū)域內(nèi)兩直線的角度值獲取候選角點，減少邊界點被誤判為角點的可能性；然后對候選角點采用先聚類再合并的計算方式，確保角點計算的準(zhǔn)確性。最后，通過搭建真實的紙箱垛型進(jìn)行實驗，結(jié)果表明，本文所提方法能有效地檢測出垛型的特征角點。