劉 娜，薛河儒，馬學磊

（內(nèi)蒙古農(nóng)業(yè)大學計算機與信息工程學院，內(nèi)蒙古呼和浩特 010011）

【研究意義】在畜牧養(yǎng)殖業(yè)中，傳統(tǒng)的接觸式羊體尺測量不僅測量精度低，耗時長，且易使羊產(chǎn)生應(yīng)激反應(yīng)等問題，因此無接觸體尺精準測量成為目前畜牧養(yǎng)殖業(yè)中的研究熱點。研究表明，羊體點云分割是利用機器視覺實現(xiàn)羊體尺無接觸精確測量的重要環(huán)節(jié)。能夠從具有復(fù)雜背景的點云中精準的分割出羊體點云，可有效地提高無接觸式[1]羊體尺測量[2-4]精準度，從而對羊進行準確的體征分析，如體尺、體質(zhì)量等?！厩叭搜芯窟M展】當前，國內(nèi)外針對三維點云分割的方法主要有：邊緣檢測法、模型擬合法、區(qū)域增長法和特征聚類法。邊緣檢測法[5]-[6]是通過標識點云圖像中特征變化明顯的點，去除不相關(guān)的點云信息，實現(xiàn)除邊緣外的點云數(shù)據(jù)的分割。主要有：基于體素柵格和八叉樹的方法進而對點云圖像進行邊界識別，以完成點云分割；引入Alpha-Shapes條件判斷對點云圖像進行地面邊緣檢測。模型擬合法[7]：根據(jù)三維點云的空間幾何特征選擇合適的幾何模型進行匹配。主要有：利用隨機采樣一致性算法檢測三維點云中存在的平面、球體、長方體、圓柱體等幾何模型，進而得到點云分割結(jié)果。區(qū)域增長法[8-10]：它是根據(jù)具體點云數(shù)據(jù)的特征，選擇恰當?shù)姆N子點并從此點開始增長，搜索指定鄰域內(nèi)滿足自定義生長準則的點云集合。主要有：利用Octree 對城市點云數(shù)據(jù)進行區(qū)域增長，進而完成分割；通過引入點云曲率信息，從而確定種子點的選擇，根據(jù)自定義的生長準則，得到較好的分割效果；結(jié)合超體素和區(qū)域生長法，對所選取的植物3個物候期的點云數(shù)據(jù)進行分割。特征聚類法：是將點云數(shù)據(jù)按照指定的數(shù)據(jù)特征，把特征相同或相似的點云劃分到同一類，不同類間點云數(shù)據(jù)屬性獨立。林國祥等[11]利用傳統(tǒng)K-means 聚類的方法對單檔電力線激光雷達點云進行分割，但分割結(jié)果不穩(wěn)定；Swita等[12]根據(jù)引入的密度信息確定初始聚類中心，進而完成對K-means 聚類算法的改進，提升了算法的執(zhí)行速度；孫紅巖等[13]利用譜系聚類和改進的K-means 聚類算法對三維點云數(shù)據(jù)進行分割，試驗證明其改進的聚類算法分割效果更好?！颈狙芯壳腥朦c】傳統(tǒng)K-means 點云分割，隨機選擇K 個初始聚類中心，并將點云中的每一個點劃分到距離最近的初始聚類中心所在的聚類區(qū)域中，最終得到類內(nèi)點云數(shù)據(jù)屬性相同，類間數(shù)據(jù)屬性獨立的K個點云集合。但傳統(tǒng)K-means 聚類分割算法的不足在于：（1）在計算點云中每個點到聚類中心的距離時，只使用點云的三維坐標值進行計算，參與計算點距離的點云數(shù)據(jù)屬性單一，導(dǎo)致算法對點云曲面特征變化的敏感性較差；（2）初始聚類中心隨機選取導(dǎo)致分割結(jié)果不固定?！緮M解決的關(guān)鍵問題】研究旨在針對以上問題，結(jié)合羊體點云數(shù)據(jù)的特征，引入點云的曲率信息，對傳統(tǒng)K-means 算法進行改進。首先，計算點云數(shù)據(jù)的曲率，利用點云的曲率信息對點云間的距離進行約束。其次，選取點云主曲率最大的前K個點作為K-means 分割算法的初始聚類中心，以期實現(xiàn)對點間坐標距離很近但曲面變化較大的羊體點云進行精確分割及保證分割結(jié)果的唯一性和穩(wěn)定性。

1 材料與方法

1.1 點云數(shù)據(jù)采集

采用易福門制造的型號為O3D303的三維攝像機進行數(shù)據(jù)采集，鏡頭孔徑為60°× 45°，圖像分辨率為352像素× 264像素。攝像機需外接電源為其供電，借助以太網(wǎng)和計算機對目標物體進行數(shù)據(jù)采集，可實時記錄獲取到的點云數(shù)據(jù)。與激光掃描儀相比，三維攝像機獲取點云數(shù)據(jù)冗余量較小，且更方便快捷。研究試驗對象為3周歲的蘇尼特羊標本，使用一臺三維攝像機對其進行數(shù)據(jù)采集。進行數(shù)據(jù)采集時，攝像機自動建立空間直角坐標系，并以攝像機所在的點為坐標原點，垂直于地面方向為x軸，垂直于羊體點云所在的平面方向為z軸，垂直于x、z軸所在的平面方向為y軸。如圖1所示，共獲取20 266個點云數(shù)據(jù)。

1.2 點云預(yù)處理

對原始點云進行適當?shù)狞c云預(yù)處理，是點云分割的必要前提。通過攝像機獲取的原始點云數(shù)據(jù)中存在一些離羊體點云較遠的無效點，如圖1中羊體的背景，以及左右兩側(cè)的書桌。因此，需要對原始點云進行濾波，濾除無效點。根據(jù)無效點云的特征，采用直通濾波將不在范圍內(nèi)的點云濾除。對原始羊體點云數(shù)據(jù)進行直通濾波時，在x，y，z軸上的濾波取值范圍分別為0.0～0.0 m（在x軸上不需濾除無效點）、-0.59～0.65 m、1.1～2.0 m。使用直通濾波濾除羊體點云中的離散點，可提高后續(xù)算法的精度。經(jīng)直通濾波后，點云數(shù)據(jù)中依然存在噪聲點及無效點。采用統(tǒng)計濾波[14-15]對其進行準確濾除。統(tǒng)計濾波是通過統(tǒng)計點云數(shù)據(jù)中某一點與其在設(shè)定鄰域內(nèi)的點集之間的距離，以濾除不符合條件的無效點。在該算法中有兩個參數(shù)需要設(shè)置，鄰域點數(shù)目k和標準差倍數(shù)閾值。試驗中，設(shè)定k為25，標準差倍數(shù)閾值為1。原始羊體點云經(jīng)點云濾波后的實驗結(jié)果如圖2所示。經(jīng)直通濾波和統(tǒng)計濾波處理后，羊體點云數(shù)據(jù)量分別為9 395個、8 483個。

圖1 復(fù)雜背景下原始羊體圖像Fig.1 Original sheep body image under complex background

圖2 羊體點云數(shù)據(jù)的濾波結(jié)果Fig.2 Filtered results of sheep point cloud data

濾波后的點云數(shù)據(jù)在去除了噪聲的同時，數(shù)據(jù)量也有所減少，但其密度依然很大，因此，計算效率較低[16]。試驗在能確保點云特征不變的情況下，使用體素柵格的方法對冗余數(shù)據(jù)進行適當?shù)南虏蓸覽17]可大幅度降低點云分割計算量，提高效率。首先，對經(jīng)統(tǒng)計濾波后的點云數(shù)據(jù)采用八叉樹算法進行體素化；其次，確定每個小立方體素柵格的重心，使用距其空間位置最近的點云數(shù)據(jù)代表每個體素柵格。在確保點云數(shù)據(jù)經(jīng)下采樣后形狀特征不發(fā)生改變的情況下，對濾波后的點云數(shù)據(jù)進行疏密判斷，設(shè)置小立方體素邊長為0.025 cm[18]。體素化前后點云數(shù)據(jù)量分別為：8 483個、3 441個，如圖3所示。

圖3 體素化后的羊體點云Fig.3 Sheep body point cloud after voxelization

1.3 改進k-means點云分割

試驗為實現(xiàn)數(shù)據(jù)預(yù)處理后點云數(shù)據(jù)的精準分割，針對傳統(tǒng)K-means 分割算法存在的不足，提出了利用曲率約束點距離和選取曲率最大的前K個點作為初始聚類中心的計算方法。

1.3.1 曲率約束點距離的計算 由于采用傳統(tǒng)歐式距離對三維點云數(shù)據(jù)的點距離進行度量時，分割效果不準確。試驗根據(jù)羊體點云數(shù)據(jù)特點，考慮引入點云數(shù)據(jù)的曲率信息，對三維點云數(shù)據(jù)的點距離進行重新定義，以實現(xiàn)羊體點云數(shù)據(jù)的細分割。具體定義如下：

定義1.點向量表示。假設(shè)點云集F第i個數(shù)據(jù)點fi的坐標為，數(shù)據(jù)點fi的高斯曲率為，平均曲率為，由高斯曲率和平均曲率構(gòu)成曲率向量主曲率為，則點fi的向量表示為公式①：

（1）點云曲率計算。曲率是反應(yīng)物體空間幾何特征的決定性因素［19］，因此羊體點云表面的彎曲程度可由曲率進行描述。采用kd-tree 建立點云數(shù)據(jù)之間的拓撲關(guān)系，利用二次曲面擬合[20]方式計算點云數(shù)據(jù)的曲率。

對于給定的三維點云集｜F={fi|fi∈R3,i=1,2,…,n}中的任意點fi及fi的k近鄰點集Neighbor(f)i，進行二次曲面擬合，其方程為公式②：

曲面的弧長可決定曲面的第一基本形式，可表示為公式③：

若(u0,v0)與近鄰點的距離表示為公式④：

則曲面第二基本形式可表示為：

由此推導(dǎo)出計算主曲率的公式：

其中，kN表示主曲率，取值為k1和k2。由此可得：

高斯曲率K為：

平均曲率H為：

整理公式（8）、（9），可得主曲率的取值：

（2）點云間距離計算。傳統(tǒng)K-means分割算法中，使用歐式距離衡量點云中每一點到聚類中心的距離。歐氏距離僅使用點云的三維坐標參與計算，其數(shù)據(jù)屬性單一，對羊體點云表面的曲面特征變化沒有給出有效的衡量方式。因此對于給定的距離閾值，即使羊體表面點云數(shù)據(jù)曲率變化顯著，但當前點云到最近的聚類中心距離值在給定閾值范圍之內(nèi)，此點云依然會被劃分到此聚類中心所在的聚類區(qū)域中。為了能得到精確的點云分割效果，試驗引入曲率信息對點距離進行計算。

定義2.點云間的距離。假設(shè)給定點云集F中任意兩點：fi=（xi，yi，zi，Ki，Hi，ki1，ki2），fj=（xj，yj，zj，Kj，Hj，kj1，kj2），則兩點之間的空間距離可定義為：

其中，DB(fi,fj)表示點fi與fj之間的歐式距離，DQ(fi,fj)表示點fi與fj之間距離的曲率約束，α表示調(diào)整參數(shù)。則DB(fi,fj)的計算公式為：

其中，θ=αβ，θ為曲率調(diào)整參數(shù)。當點云曲面特征變化明顯，需要把當前點云分割出當前聚類中心所在的區(qū)域時，調(diào)整θ的取值，使其適當增大。

1.3.2 聚類中心的選取 在基于聚類的分割算法中，初始聚類中心選擇的優(yōu)劣直接影響分割效果。因此，根據(jù)不同點云圖像的特征，選擇適當?shù)某跏季垲愔行氖谦@得準確分割效果的重要前提。針對傳統(tǒng)K-means 分割算法隨機選擇初始聚類中心導(dǎo)致的分割結(jié)果不穩(wěn)定，且分割效果不準確的缺陷，經(jīng)多次試驗研究，利用主曲率k2作為選擇羊體初始聚類中心的依據(jù)，并且選擇曲率最大的前K 個點作為初始聚類中心，可提高分割效果的準確性和穩(wěn)定性。

1.3.3 聚類算法的實現(xiàn) 對于點云集合F={fi|fi∈R3,i=1,2,…,n}，分割成K個聚類區(qū)域，則可定義準則函數(shù)為：

其中，點云集合F的第i個聚類區(qū)域表示為Si，Si中任意一點表示為f，Si的聚類中心表示為ci。

點云集合中任意點f被劃分到具體聚類區(qū)域中的判定公式：

對于不滿足收斂條件的聚類區(qū)域，更新其聚類中心的公式為：

其中，n表示聚類區(qū)域中包含的點數(shù)量。

基于改進K-means的羊體點云分割算法步驟如下：

（1）對采集到的點云圖像進行數(shù)據(jù)預(yù)處理。（2）計算經(jīng)預(yù)處理后點云數(shù)據(jù)的高斯曲率K、平均曲率H及主曲率k1、k2，由此得到點云向量（3）利用主曲率k2作為選取初始聚類中心點的依據(jù)，選取曲率最大的前K 個點作為初始聚類中心。（4）通過公式○16得到點云集合F中每一點到{c1,c2,…,ck}中各初始聚類中心的距離。（5）根據(jù)公式○18，將（4）中所得距離聚類中心最近的點聚類到該聚類中心所在的區(qū)域{S1,S2,…,Sk}。（6）按照公式○19 更新{S1,S2,…,Sk}中各聚類區(qū)域的聚類中心，得{c1,c2,…,ck}，重復(fù)（4），（5）。（7）直到更新的聚類中心點集{c1,c2,…,ck}不再發(fā)生變化或者收斂于E，結(jié)束聚類，得到最終分割結(jié)果。

2 結(jié)果與分析

圖4 K增長時算法執(zhí)行時間Fig.4 Algorithm execution time as K grows

研究使用CPU 為Inter（R）Core（TM）i7-8550U CPU@1.80 Hz 2.00 GHz，16 G 內(nèi)存的計算機進行試驗，應(yīng)用Visual C++2017 編程環(huán)境，基于PCL開源C++編程庫，分別用傳統(tǒng)K-means分割算法和改進K-means分割算法對羊體點云數(shù)據(jù)進行分割。圖4 為采用改進的K-means 分割方法對羊體點云數(shù)據(jù)進行分割的過程中，初始聚類中心K 與算法執(zhí)行時間T 的關(guān)系。由圖可知，當K取10～20 時，算法執(zhí)行時間增幅較緩；隨著K 不斷增大，當K取20 以上時，算法執(zhí)行時間增幅較大，時間開銷大，K 值不可用。實驗過程中發(fā)現(xiàn)，當K取10～15時，初始聚類中心數(shù)量過少，分割效果不佳，K值不可用。

圖5 K和θ一定時，曲率排序選取初始聚類中心和隨機選取初始聚類中心的分割對比結(jié)果Fig.5 The results of segmentation comparison between initial clustering center and random clustering center selected when theKandθare fixed

圖5（a）-圖5（f）為采用改進K-means分割算法進行分割試驗過程中，當K和θ一定時，對點云數(shù)據(jù)進行曲率排序選取初始聚類中心和隨機選取初始聚類中心的分割對比結(jié)果。

其中，圖5（a）、（c）、（e）分別為K取16、18、20時，利用曲率排序選取初始聚類中心進行分割，所得的最佳聚類結(jié)果，但僅圖5（c）（K=18,θ=0.9）分割效果較為理想。由圖5（a）-圖5（f）對比可知，利用曲率排序選取初始聚類中心相較于隨機選取初始聚類中心得到的分割效果更好。

圖6 為利用傳統(tǒng)K-means 算法進行分割的結(jié)果。傳統(tǒng)K-means 算法在曲面曲率變化顯著的區(qū)域仍按照歐式距離進行聚類，因此羊體腳部與地面接觸的區(qū)域無法精確分割。圖7（a）-圖7（h）為利用改進的K-means聚類算法在K一定(K=18)的前提下，θ取不同值時的聚類結(jié)果。當θ=0.1 時（圖5（a）），曲率對點距離約束較弱，導(dǎo)致不同聚類區(qū)域的點被分割到同一區(qū)域中，出現(xiàn)欠分割現(xiàn)象（圖5（b））；當θ取值逐漸增大時（圖5（c）），曲率對點距離的約束逐漸增強，分割效果準確性逐漸提高；當θ取值過大時（圖5（g），θ=5），曲率對點距離約束過強，導(dǎo)致同一聚類區(qū)域的點被劃分出去，出現(xiàn)過分割現(xiàn)象（圖5（h））。相對來說，θ=0.9 時的分割效果較為理想，圖5（f）為從圖5（e）中提取出的羊體點云數(shù)據(jù)，分割結(jié)果達到了預(yù)期。圖7（a）-圖7（b）為利用改進的K-means分割算法，在K=18，θ=0.9 時，以羊體點云數(shù)據(jù)中隨機選取的點作為初始聚類中心進行分割的結(jié)果圖?？梢钥闯觯瑑纱卧囼灥姆指罱Y(jié)果明顯不一致且均不準確。與圖5（f）相比，后者分割結(jié)果更具穩(wěn)定性和準確性。研究改進的K-means 算法可將羊體從地面準確的分割出來，且避免了傳統(tǒng)K-means 算法隨機選取初始聚類中心導(dǎo)致的分割結(jié)果不穩(wěn)定及不精確的問題?？傮w分割效果較好，可提高后續(xù)測點識別度。

圖6 傳統(tǒng)K-means分割結(jié)果Fig.6 Traditional K-means segmentation results

圖7 改進K-means分割結(jié)果Fig.7 Improved K-means segmentation results

圖8 隨機選取初始聚類中心不同試驗的分割結(jié)果Fig.8 Segmentation results of randomly selected initial cluster centers with different trial times

3 結(jié)論與討論

研究采用改進的K-means 羊體點云分割方法，引入曲率信息，對點云間的距離進行重新定義，實現(xiàn)了羊體點云數(shù)據(jù)曲率變化顯著部位的準確分割。同時，對點云的主曲率k2排序，選取曲率最大的前k 個點云作為初始聚類中心，避免了隨機選擇初始聚類中心存在的弊端，提高了分割效率。以此分割結(jié)果作為下一步羊體測量點識別的試驗依據(jù)，對羊體的無接觸測量具有重要的研究意義。

采用改進的K-means算法對所采集到的羊體點云數(shù)據(jù)進行分割的過程中，可以通過手動調(diào)節(jié)θ的取值，來獲得較為理想的分割效果。為進一步提高羊體分割的準確性，可以采用去羊場拍攝活體羊同時增加羊體點云數(shù)據(jù)樣本數(shù)量的方式，以提高分割模型在惡劣環(huán)境下的分割能力。

致謝：內(nèi)蒙古農(nóng)業(yè)大學計算機學院薛河儒教授對研究給予了指導(dǎo)與支持，馬學磊博士對研究給予了幫助，謹致謝意!