彭 凱，饒鈺涵，肖艷軍，楊澤青

（1.河北工業(yè)大學(xué) 機(jī)械工程學(xué)院，天津 300131；2.天津大學(xué) 精密儀器與光電子工程學(xué)院，天津 300072）

隨著工業(yè)制造水平的不斷發(fā)展，傳統(tǒng)的二維接觸式測量存在大量弊端。三維非接觸式點云測量作為機(jī)器視覺技術(shù)，能夠滿足當(dāng)前高速、高產(chǎn)、優(yōu)質(zhì)的生產(chǎn)環(huán)境[1]。采用雙目立體視覺系統(tǒng)生成點云數(shù)據(jù)的方法，可實現(xiàn)目標(biāo)對象的遠(yuǎn)距離定位和測量，且結(jié)構(gòu)簡單，成本較低[2]。

將目標(biāo)物體從點云場景中分割，是保證點云測量結(jié)果準(zhǔn)確性的關(guān)鍵[3]?，F(xiàn)有點云分割算法[4]主要有基于邊緣檢測方法、基于區(qū)域增長分割方法、基于特征聚類方法和基于模型擬合方法。

基于邊緣檢測方法適用于點云數(shù)據(jù)密度均勻的情況，而且噪聲對分割結(jié)果影響較大。Castillo 等人[5]提出這種方法受到噪聲和點分布的影響，只能檢測到間斷的邊緣，但對于連續(xù)封閉的區(qū)域識別效果較差。

基于區(qū)域增長分割方法[6,7]最早由Besl 等人[8]在1988 年提出，適用于小目標(biāo)物體的分割，易產(chǎn)生欠分割現(xiàn)象。由于區(qū)域增長的分割方法使用到了全局信息，因此這種方法比邊緣檢測方法對噪聲更具魯棒性。

基于特征聚類方法[2]適用于特征信息明顯的模型[9]，但分割結(jié)果嚴(yán)格依賴人工和分割閾值的選擇，算法自適應(yīng)能力較差。2016 年，Lu X 等人[10]提出了一種基于聚類中心點連接的點云分割算法，即P-Linkage 分割。該方法無需自定義參數(shù)和閾值，算法自適應(yīng)能力強(qiáng)同樣分割效果較好。

基于模型擬合方法，可以一定程度上減少噪聲對于分割結(jié)果的影響，1981 年提出的隨機(jī)采樣一致性算法（Random Sample Consensus,RANSAC）成為模型擬合方法的基礎(chǔ)模型[11]。

采用單一分割算法普遍存在算法自適應(yīng)性能差、無法根據(jù)環(huán)境及時調(diào)整，因此可采用多個基礎(chǔ)算法融合的方式分步處理，利用多個算法的優(yōu)勢，彼此彌補(bǔ)。楊琳等人[12]將超體素和區(qū)域生長分割融合，首先根據(jù)法向量信息分割得到超體素點，然后將超體素點作為種子點進(jìn)行區(qū)域生長完成分割。該融合算法有效提高了分割效率，但易受點云分布和規(guī)模的影響，且自適應(yīng)性較差。文獻(xiàn)[13]將分水嶺和圖割算法融合，先利用分水嶺算法將圖像分割為多個小區(qū)域，再對小區(qū)域進(jìn)行圖割分割，這種方式提高了分割精準(zhǔn)度，但該算法適用于圖像分割且未在實際中應(yīng)用。上述算法存在一定限制，但對點云分割提供了融合算法的新思路。

綜上，為了提高精度、節(jié)約成本。本文提出一種雙目視覺空間定位系統(tǒng)中多層次點云目標(biāo)物體分割、測量算法。首先通過雙目立體視覺系統(tǒng)獲取的點云數(shù)據(jù)進(jìn)行數(shù)據(jù)預(yù)處理。采用RANSAC 算法檢測并去除場景中多余的背景平面，保留目標(biāo)物體，減少點云數(shù)據(jù)量。其次基于P-Linkage 算法原理[14]將目標(biāo)物體聚類分割，使用最小包圍盒算法進(jìn)行測量，獲取該場景中幾何物體的尺寸信息。最后通過實驗將本文非接觸測量算法與傳統(tǒng)算法進(jìn)行對比，驗證了本文算法在時間成本上有一定優(yōu)勢，且具有較高測量精度。

1 RANSAC 和P-Linkage 融合分割方法

1.1 基于RANSAC 算法的分割

RANSAC 算法作為一種模型擬合類方法，其原理是：首先隨機(jī)選擇一組點云數(shù)據(jù)作為樣本點集，然后結(jié)合方差估計形成樣本模型，此樣本模型也可以由用戶自定義。接下來就是計算樣本點集內(nèi)所有樣本點值與樣本模型的偏差，并讓偏差值與用戶設(shè)定閾值進(jìn)行比較。將滿足閾值范圍內(nèi)的樣本點設(shè)為內(nèi)點，不滿足即在閾值范圍外的樣本點設(shè)為外點，然后更換模型進(jìn)行比較，選擇包含內(nèi)點數(shù)量最多的模型為最佳擬合模型。圖1 為本文設(shè)計的基于RANSAC 算法點云分割的具體流程圖。

圖1 基于RANSAC 算法的點云分割流程圖Fig.1 Flow chart of point cloud segmentation based on RANSAC algorithm

使用RANSAC 算法可以在數(shù)據(jù)特征過多的點云數(shù)據(jù)中提取滿足目的要求的點云特征。若內(nèi)點占全部數(shù)據(jù)點的比例為t，計算模型使用的點的個數(shù)為n，迭代次數(shù)為k，則采集點為正確模型的概率A和迭代次數(shù)k的計算公式為：

1.2 P-Linkage 分割

基于聚類中心點連接的分割算法與區(qū)域增長分割和特征聚類分割不同的是，P-Linkage 聚類分割方式通過計算三維點云的平面度，并以此作為特征值。通過特征值大小的排列順序，找到點與點之間的連接關(guān)系。通過搜索查詢點和鄰域連接點的關(guān)系，索引類型的聚類。將滿足相似條件的聚類合并，并完成點云目標(biāo)分割。

對于每個數(shù)據(jù)點，基于 K 近鄰（K-Nearest Neighbors,KNN）的方法從點云中選擇與其具有最小距離的點的集合作為其鄰域并進(jìn)行分類，此方法通過應(yīng)用k-d 樹等空間劃分策略來實現(xiàn)。然后通過主成分分析法（Principal Components Analysis,PCA）估計各個鄰域點表面的法線。

通過構(gòu)建一個k-d 樹，對于每個數(shù)據(jù)點P，找到它最近鄰域內(nèi)的m個點，并將其記錄為I。根據(jù)P到近鄰域點I的距離，將I按升序排列。通過計算協(xié)方差矩陣，可以求得各點的法向量、平面度等。每個數(shù)據(jù)點P的協(xié)方差矩陣可表示為：

其中，∑P為數(shù)據(jù)點P的協(xié)方差矩陣；為鄰域點集I中前(m/2)個數(shù)據(jù)點的均值向量。由于數(shù)據(jù)量過大，且每個數(shù)據(jù)點的鄰域點按升序排列，所以用前(m/2)個數(shù)據(jù)點表示。結(jié)合計算點云表面法向量推導(dǎo)出的結(jié)論，可求得數(shù)據(jù)點P協(xié)方差矩陣的特征向量V以及特征向量對應(yīng)的特征值λ。V的特征向量子集ν2、ν1和ν0根據(jù)對應(yīng)的特征值，按照依次減小的順序排列，即λ2＞λ1＞λ0。ν2和ν1形成一個正交基，表示最大可變性的兩個維度，它定義了I中相鄰點的最佳擬合平面，ν0與前兩個特征向量形成正交關(guān)系，并且近似擬合平面的法線。λ0估計點偏離切面的多少表示該點的平面度，可以用其評價一個平面擬合的質(zhì)量。λ0越小，平面擬合的質(zhì)量越好。

找到每個數(shù)據(jù)點P的最近鄰域的m個點I。使用PCA 原理，利用前(m/2)個鄰域點I計算數(shù)據(jù)點P的特征向量。上述計算結(jié)果中的特征向量ν0為擬合平面的法線，特征值λ0是估計平面的平面度。通過各點的計算結(jié)果與計算閾值R找出各個鄰域點I中與P相似的一致集PS。首先，計算數(shù)據(jù)點P的m個最近鄰域點I到其估計擬合平面的正交距離，將其收集為集合。然后，計算中值絕對偏差M與計算閾值R。

其中，median（NOD）是上述距離集合的中值，a為常數(shù)。

通過各點的R值與規(guī)定閾值進(jìn)行對比，可以得到與P相似的一致集PS，以及每個數(shù)據(jù)點P的法向量ν0和平面度λ0，建立點與點之間的成對連接。在相似一致集PS中尋找平面度小于P且法向量與P的偏差最小的點，記做CN(P)。如果相似一致集中有滿足CN(P)的點存在，則創(chuàng)建P和CN(P)之間點與點的成對連接，將成對連接點記錄到查找表T中。如果P的平面度λ（p）是其鄰域點平面度中的最小值，同時平面度λ（p）小于跟隨閾值thλ，那么聚類中心可以用P表示，并將其放入點云聚類中心點集C中。跟隨閾值thλ的計算公式為：

其中，λ是m個數(shù)據(jù)點的平面度的平均值；σλ是所有平面度的標(biāo)準(zhǔn)差。

利用找到的成對連接點和聚類中心點集，形成聚類，創(chuàng)建點云的表面切片。首先，從點云聚類中心點集C中選取中心點，并利用查找表T建立點與點之間的連接，查找對應(yīng)連接點并形成聚類。這些聚類點有直接連接也有間接連接，但由于其有相似的特征屬性，因而被歸為一類。當(dāng)某聚類點集中點的個數(shù)小于10 時，則將該類點視為異常點并刪除。然后，通過合平面為每個聚類建立切面，并選擇具有相對最小平面度的面作為最佳擬合面。利用與求數(shù)據(jù)點特性值相同的方法，求得平面的法向量、平面度和相似一致集，并利用相似于P-Linkage 的方式，將這些切片聚類合并，完成分割。

1.3 融合RANSAC 和P-Linkage 算法的分割

對點云數(shù)據(jù)進(jìn)行點云預(yù)處理操作[15]，由于三維點云數(shù)據(jù)包含了豐富的空間信息，所以對點云數(shù)據(jù)按照數(shù)據(jù)特征進(jìn)行結(jié)構(gòu)劃分，可以有效地提高算法搜索效率。

RANSAC 算法通過建立的點云模型檢測并排除點云異常數(shù)據(jù)和噪聲干擾，能夠得到優(yōu)化的點云模型。因此在本文的融合算法中，首先，使用RANSAC 算法將與原始點云數(shù)據(jù)的無關(guān)平面進(jìn)行分割去除，如實驗臺、地面等多余點云環(huán)境。然后，利用P-Linkage 算法對剩余點云進(jìn)行自適應(yīng)性高的精確分割。該融合算法的優(yōu)勢將在下文實驗中，通過與傳統(tǒng)歐式聚類分割算法、區(qū)域生長分割算法進(jìn)行對比驗證。融合分割算法流程圖如圖2 所示。

圖2 融合分割算法流程圖Fig.2 Flow chart of fusion segmentation algorithm

1.4 點云測量

求不規(guī)則形狀點云數(shù)據(jù)的最小包圍盒。首先，將聚類形成的點云聚類集進(jìn)行去均值化的數(shù)據(jù)預(yù)處理操作，各個維度的數(shù)據(jù)減去相應(yīng)維度上的均值，使每個維度的中心坐標(biāo)為0，這樣可以減小數(shù)據(jù)量，方便后續(xù)計算。然后，建立新的數(shù)據(jù)空間(a,b,c)來代替原始的三維空間(x,y,z)。原始聚類點云計算生成協(xié)方差矩陣，然后通過PCA 主成分降維分析法求得的三個特征向量即為新的數(shù)據(jù)特征空間的三個方向。

原始聚類點云在新建立的(a,b,c)數(shù)據(jù)空間坐標(biāo)系中建立投影，即某方向上最內(nèi)點和最外點的坐標(biāo)值。由于點云數(shù)據(jù)已完成預(yù)處理和分割處理，數(shù)據(jù)可靠性高，離散點少。完成投影后，可通過投影求得三個方向上的最小值和最大值。

求得的六個點可以在(x,y,z)坐標(biāo)系確定一個包圍盒，將8 個求得包圍盒坐標(biāo)逆變換可以得到在(x,y,z)坐標(biāo)系下的新坐標(biāo)值以及最小包圍盒。

由于OBB（Oriented Bounding Boxes）算法具有方向性，可以生成最貼合點云的包圍盒。因此，當(dāng)點云數(shù)據(jù)為規(guī)則形狀，如長方體時，可利用OBB 完全貼合。當(dāng)點云形狀不規(guī)則時，可以使用AABB（Axis-Aligned Bounding Boxes）生成包圍盒，來近似估計幾何物體的尺寸。因此，通過最小包圍盒的八點距離的差值可以求出包圍盒的長寬高，進(jìn)而求得聚類點云的長寬高。使用最小包圍盒算法對點云進(jìn)行測量可以將分割出來的目標(biāo)點云的長、寬、高的尺寸參數(shù)化，再與實際物體尺寸進(jìn)行對比分析，該方法即可以檢驗各個算法的分割精度又可以對實際物體尺寸進(jìn)行非接觸式測量。

2 實驗驗證

本文實驗以Qt5.14.2 為開發(fā)平臺，使用VS2019作為編譯器。利用OpenCV4.5.1 視覺庫處理雙目相機(jī)采集的圖像，通過PCL1.10.1 進(jìn)行點云數(shù)據(jù)相關(guān)算法設(shè)計，并生成用戶操作界面，方便用戶獨立完成點云數(shù)據(jù)處理的各項操作，實現(xiàn)點云數(shù)據(jù)讀取、處理并保存的完整體系。

2.1 點云分割實驗

通過分析隨機(jī)采樣一致性算法、歐式聚類分割算法、區(qū)域生長分割算法運(yùn)行結(jié)果原理，明確了各個分割算法的適用情況。為了驗證該組合分割算法的理論在工程社會中具備實際應(yīng)用效果，本實驗在工程環(huán)境中拍攝了標(biāo)準(zhǔn)工件照片如圖3 所示，通過雙目空間立體視覺系統(tǒng)生成點云圖，如圖4 所示。

圖3 實際空間環(huán)境物體Fig.3 Actual space environment objects

圖4 初始點云圖Fig.4 Initial point cloud image

圖5 為點云數(shù)據(jù)預(yù)處理運(yùn)行結(jié)果，從圖中可以發(fā)現(xiàn)，點云離散點被濾除，點云數(shù)量減少，同時保留原始形狀。

圖5 點云數(shù)據(jù)預(yù)處理運(yùn)行結(jié)果Fig.5 Result of point cloud data preprocessing

隨機(jī)采樣一致性算法分割結(jié)果如圖6 所示，該算法只適用于固定模型的分割，檢測并剔除場景中的背景平面，保留目標(biāo)點云數(shù)據(jù)。后續(xù)點云聚類分割的數(shù)據(jù)源，均使用此結(jié)果。

圖6 平面分割算法運(yùn)行結(jié)果Fig.6 Result of plane segmentation algorithm

歐式聚類分割算法分割運(yùn)行結(jié)果如圖7 所示，在該場景下多個物體相距較遠(yuǎn)，因此，具有良好的分割效果。聚類分割算法適合于分割間隔較大的物體，且聚類距離需要進(jìn)行測試。當(dāng)有多個目標(biāo)物體且距離較近時，聚類分割無法將目標(biāo)進(jìn)行合理分割。

區(qū)域生長分割算法運(yùn)行結(jié)果如圖8 所示，由于區(qū)域生長算法可以根據(jù)曲率、法向量等實現(xiàn)不同區(qū)域的劃分，這種算法嚴(yán)格依賴于種子點的選擇以及閾值的設(shè)置，自適應(yīng)能力較差。通過觀察分割結(jié)果可以發(fā)現(xiàn)，正方體物體被分割成為多個區(qū)域，產(chǎn)生了過分割的問題。

圖8 區(qū)域生長分割算法運(yùn)行結(jié)果Fig.8 Results of region growth segmentation algorithm

P-Linkage 分割算法運(yùn)行結(jié)果如圖9 所示，由于不需要提前設(shè)置參數(shù)，該算法的自適應(yīng)能力較好。而且與區(qū)域生長算法分割結(jié)果相比較，并沒有產(chǎn)生過分割現(xiàn)象。與歐式聚類算法分割結(jié)果相比較，該算法也可以把間隔小的物體分割開，適用范圍更大。

圖9 P-Linkage 分割算法運(yùn)行結(jié)果圖9 Results of P-Linkage segmentation algorithm

2.2 點云測量實驗

在本次實驗中，使用RANSAC 算法分別融合歐式聚類和P-Linkage 分割方式，對數(shù)據(jù)預(yù)處理后的原始點云進(jìn)行分割，然后用最小包圍盒算法對分割的點云目標(biāo)進(jìn)行測量。將測量結(jié)果與實際測量值進(jìn)行對比，并計算出每種分割算法的測量誤差和相對誤差。

Type-A 插口實際測量寬度為8 mm，鋼板實際測量長度和寬度分別為120 mm 和90 mm，三通管實際測量長度和寬度分別為140 mm 和100 mm。在多目標(biāo)場景環(huán)境中，正方體邊長為20 mm，選擇的圍棋直徑為24.5 mm。

采樣相同數(shù)據(jù)預(yù)處理操作后，不同分割算法的測量值、測量誤差和相對誤差結(jié)果，分別如表1-7 所示。表1-7 中分割算法1、2、3 分別為融合RANSAC 與歐式聚類算法、區(qū)域生長算法、融合 RANSAC 與P-Linkage 算法。

表1 Type-A 寬度測量結(jié)果Tab.1 Type-A width measurement results

表2 鋼板長度測量結(jié)果Tab.2 Steel plate length measurement results

表3 鋼板寬度測量結(jié)果Tab.3 Steel plate width measurement results

表4 三通管長度測量結(jié)果Tab.4 Tee length measurement results

表5 三通管寬度測量結(jié)果Tab.5 Tee width measurement results

表6 多目標(biāo)物體中正方體邊長測量結(jié)果Tab.6 Measurement results of cube side length in multi-object object

表7 多目標(biāo)物體中圍棋直徑測量結(jié)果Tab.7 Measurement results of the diameter of Weiqi in multi-object

分別使用三種分割算法分割上述七類目標(biāo)物體，并測量。將測量結(jié)果的相對誤差進(jìn)行統(tǒng)計，統(tǒng)計結(jié)果如表8 所示。物體類別1、2、3、4、5、6、7 分別對應(yīng)上述幾種測量物體。

表8 各類融合分割算法目標(biāo)物體測量結(jié)果的相對誤差統(tǒng)計表Tab.8 Statistical table of relative errors of object measurement results in various segmentation algorithms

表8 的相對誤差統(tǒng)計結(jié)果證明融合RANSAC 與P-Linkage 分割算法的分割精度相較于融合RANSAC與歐式聚類算法和區(qū)域生長算法更高。在各種環(huán)境下，目標(biāo)物體尺寸測量相對誤差始終保持在3.8%及以下。

為了證明融合使用RANSAC 算法和P-Linkage 分割算法可以提高單一算法效率，分別計算采用單一P-Linkage 算法和融合算法分割上述幾種類別物體的算法運(yùn)行時間，其中Type-A 插口、鋼板、三通管、多目標(biāo)物體分別對應(yīng)類別A、B、C、D，兩種算法的運(yùn)行時間如表9 所示。

表9 算法運(yùn)行時間（單位：ms）Tab.9 Algorithm running time (Unit: ms)

從表9 可以看出，使用本文提出的融合分割算法比使用單一P-Linkage 算法運(yùn)行效率提高1.5～4.4 倍。

3 結(jié)論

RANSAC 算法通過擬合模型實現(xiàn)快速場景平面分割，P-Linkage 算法在多種來源的多目標(biāo)場景空間中能表現(xiàn)出良好的分割效果。本文結(jié)合二者優(yōu)點提出了一種基于雙目立體視覺系統(tǒng)的點云多層次融合分割和測量的算法。本算法設(shè)計的用戶操作界面可以完成點云數(shù)據(jù)的讀取、操作和保存，實現(xiàn)了工業(yè)制造的自動化測量。實驗結(jié)果表明，本文使用的融合分割算法，可以使運(yùn)行效率提高1.5～4.4 倍，具有精度高和良好的自適應(yīng)能力，并且可以將物體測量誤差穩(wěn)定在3.8%以下。