張長勇，馮 冰，陳治華

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

0 引 言

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

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

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

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

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

1 垛型角點檢測方法

1.1 候選角點獲取

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

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

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

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

則：

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

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

圖2 角點誤判示意圖

1.2 候選角點聚類

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

1）改進的CFSFDP算法自動確定簇中心點

CFSFDP算法[13]假設(shè)簇中心是局部密度最大值，并且簇中心遠離其他更高密度的點，為了尋找符合假設(shè)的簇中心點，計算局部密度ρi與相對距離δi，然后依據(jù)ρi，δi畫出決策圖，最后人為依據(jù)決策圖將局部密度和相對距離同時較大的數(shù)據(jù)點作為簇中心點。文獻[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聚類算法需要隨機選取k個點作為初始聚類中心進行迭代操作，但由于垛型的角點個數(shù)未知，無法初始化k值。因此，通過改進的CFDP算法對候選角點進行預處理，將獲得的簇中心點作為K?means的初始聚類中心，以保證K?means的聚類效果。融合算法具體的步驟如下：

Step1：改進的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算法對垛型候選角點進行聚類，得到同一角點區(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)作為垛型最終角點坐標。其中，xmaxρx表示在x方向上取密度值最大的x作為最終角點坐標的x值，同理可得ymaxρy,zmaxρz。

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

2 實驗結(jié)果分析

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

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

2.1 候選角點分析

1）候選角點提取分析

采用改進的尖銳度角點檢測算法提取垛型的候選角點，以90°-6×n≤α≤90°+6×n（n=0，1，2，3）為α變化范圍；r=10+10×n（n=0，1，2），為r的取值進行實驗。不同參數(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 誤差分析

將本文算法計算的角點坐標與人工測量的角點坐標進行對比，并計算估計誤差，以驗證本文所提算法的準確性。估計誤差計算公式為：

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

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

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

3 結(jié) 論

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