王憲倫，丁文壯，孫旭祥

(青島科技大學 機電工程學院，山東 青島 266100)

0 引言

隨著計算機技術(shù)的快速發(fā)展，計算速度得到快速提升。作為最直觀反映客觀位置的點云信息運用范圍越來越大，復(fù)雜性要求越來越高，在場景獲取、位置測量、三維重建、逆向開發(fā)[1]方面，點云處理成為場景感知的重要手段。

安裝在移動機器人上的深度相機常常需要通過獲取點云信息來定位，其中孔洞信息經(jīng)常是一些定位的關(guān)鍵信息，例如集裝箱上的吊裝孔位。何學銘等[2]利用最大角度準則、半圓盤度量準則、形狀度量準則，通過三者加權(quán)來判斷為邊界點的概率，但是卻難以選擇恰當?shù)臋?quán)重系數(shù)。陸帆等[3]提出了利用反距離權(quán)重加權(quán)等效合力和點云密度作為目標點為邊界點的判定條件，但是其普遍性較差。王春香等[4]對點云模型的孔洞形成原因及孔洞類型進行了分析和總結(jié), 就邊界識別方法做出了詳細的介紹和歸納。孫殿柱等[5]提出一種基于曲面局部形貌標架的點云特征識別方法。通過標架夾角的差異性，對曲面樣本形貌進行量化分析，區(qū)分平滑、邊界、棱邊及尖角等特征區(qū)域，實現(xiàn)對中心樣點屬性的穩(wěn)健判別，但是其算法就孔洞邊界提取而言開銷較大。TABIB R A等[6]使用深度學習的框架來識別邊界特征。MINEO C等[7]優(yōu)化了現(xiàn)有的邊界點檢測算法并提出了BPD算法。

本文對半圓盤準則和最大角度準則易受噪聲影響的問題，提出了雙半圓盤準則。本文利用質(zhì)心點位置將圓盤劃分為雙半圓盤，通過雙半圓盤中投影點數(shù)目的比值來判斷邊界點，噪聲的影響會成比例縮小，魯棒性較好，能夠快速、穩(wěn)健地實現(xiàn)邊界提取。

1 點云數(shù)據(jù)預(yù)處理

1.1 點云濾波

1.2 點云降采樣

本文采用體素化網(wǎng)格的方法實現(xiàn)下采樣來減少點的數(shù)量，同時保證點云的形狀特征不變。點云幾何結(jié)構(gòu)不僅是宏觀的幾何外形，也包括其微觀的排列方式[9-10]，比如橫向相似的尺寸、縱向相同的距離等。隨機下采樣雖然效率比體素柵格[11]濾波器高，但會破壞點云微觀結(jié)構(gòu)。

2 點云邊界檢測算法

2.1 計算切平面

根據(jù)目標點P及其在半徑為r的范圍內(nèi)的近鄰點構(gòu)造在目標點P處的局部切平面。半徑r的選擇應(yīng)當至少為兩倍的體素格對角線長度，局部切平面的構(gòu)造方法采用最小二乘法來擬合切平面[12]，假設(shè)切平面方程為

Ax+By+Cz+D=0

(1)

變形為

(2)

z=m1x+m2y+m3

(3)

令S=m1x+m2y+m3，近鄰點數(shù)目為k，則

(4)

由近鄰點擬合切平面即：各個近鄰點到切平面的距離的平方和最小，所以應(yīng)取上述公式的最小值，為此要得到m1、m2、m3的最佳參數(shù)估計，所以令

(5)

其中i=1,2,3，所以有

(6)

將上述方程組整理成矩陣的形式為

(7)

對上述方程組求解，即可得到切平面方程。

2.2 計算切平面投影點

將目標點P的近鄰點投影到切平面上，其具體步驟為: 建立平面ω過點P且平行于切平面，通過帶入點P的坐標可以得到ω的平面方程，進而獲得平面ω的法向量n(nx,ny,nz)，設(shè)目標點P的近鄰點其中之一P0(x0,y0,z0)在平面ω上對應(yīng)點為P′0(x′0,y′0,z′0)，可以建立方程式(8)。

(8)

將上述兩式帶入ω的平面方程即可解出P′0(x′0,y′0,z′0)的值。

2.3 雙半圓盤算法具體實現(xiàn)

將目標點P的近鄰點P0,P1,…，Pk投影到平面ω上得到其各自的對應(yīng)點P′0,P′1,…，P′k。由于近鄰點所在的空間為球體，且平面ω過球心，所以ω平面的感興趣區(qū)域為一塊圓形區(qū)域，如圖1所示。

圖1 雙圓盤建立示意圖

求取投影在圓形范圍內(nèi)投影點的質(zhì)心坐標，經(jīng)過質(zhì)心點(圖1中空心點)和圓形中心點(圖1中黑色點)來建立直線方程l0(圖1中短直線)。求取過圓心并且垂直于l0的直線ld(圖1中直線ST)。直線ld將圓形區(qū)域分為兩個半圓盤，將坐標點帶入直線ld的方程來判斷點在直線上方或者直線下方，分別對直線上方和下方的點的數(shù)目進行統(tǒng)計，在上下兩個半圓盤點數(shù)目統(tǒng)計時遵循下列原則：恰好位于直線上的點不納入計數(shù)范圍，如果某一半圓盤上的投影點的個數(shù)為0，則設(shè)置該半圓盤的最終參數(shù)為0.25，反之，該半圓盤的參數(shù)等于該半圓盤上投影點的個數(shù)。半圓盤投影點的個數(shù)之和應(yīng)當大于2，認定小于2的為邊界離散點。對兩個半圓盤參數(shù)進行排列大小得到amax、amin，通過兩者之比得到參數(shù)ka，通過給定參數(shù)ka的閾值來判定是否為邊界點。n1、n2分別為兩個半圓盤上投影點的個數(shù)，a1、a2分別為兩個半圓盤的參數(shù)。綜上所述，邊界點條件滿足下式：

(9)

凡是滿足上式的點則認為是邊界點，遍歷點云中的所有點，得到邊界點的索引。

3 內(nèi)邊界判定條件

經(jīng)過上節(jié)可以將邊界點提取出來，然后通過聚類[13]分類出各個邊界所包含的邊界點的索引vi。分別用2.1節(jié)中所提到的最小二乘法求取各個vi所對應(yīng)邊界的切平面，將該邊界所對應(yīng)的邊界點投影到邊界點切平面ωp上。對投影點用廣度優(yōu)先搜索算法(BFS)[14]進行邊界點排序。搜索求取該邊界所對應(yīng)邊界點鄰域內(nèi)點的質(zhì)心，鄰域半徑的選取參考2.1節(jié)中半徑r值，計算得到由質(zhì)心指向邊界點的單位向量ui，然后將各個邊界點所對應(yīng)的單位向量ui也投影到切平面ωp上，并將得到的投影點按照搜索最近點的方法來連接成多邊形，示意圖如圖2所示。其中A、B、C、D、E、F、G代表邊界點，其對應(yīng)的向量代表ui。

圖2 邊界點及其對應(yīng)向量

假設(shè)該邊界上的邊界點個數(shù)為kω，取其中任意一點為起始點kω/4，取為一個步長，得到4個邊界點及其對應(yīng)向量ui，求取任意相鄰的兩向量沿著向量延長線方向的交點。如果交點和質(zhì)心點所構(gòu)成向量與目標點和質(zhì)心點所構(gòu)成向量方向一致，即向量各元素符號相同，則認為是內(nèi)邊界點。隨后沿順時針或者逆時針定向取另外間隔相等的4個點，依次執(zhí)行上述判斷。如果超過一定比例的點都滿足向量延長線交點條件，則認為該邊界為內(nèi)邊界。

4 實驗驗證

本實驗采用PCL(point cloud library)，Visual Studio 2015，kinect2.0平臺來獲取點云數(shù)據(jù)。為了直觀地表達本文提出的雙半圓盤準則，本文采用基于Opencv3.4.7和Visual Studio 2015平臺的C++語言來直觀地測試該準則,計算機采用Inter Core i5-6400CPU內(nèi)存為12 GB。在實驗中創(chuàng)建了空白圖片然后將圖片分為40×60的格子，并分別在格子中隨機生成黑色點來代表投影點，隨機截取其中一塊并去掉外圍點和內(nèi)孔點，采用上述算法對其邊界點檢測，結(jié)果圖如圖3所示。圖3中：列為a、b、c；行為1、2、3。(1a)、(2a)、(3a)為隨機生成的待檢測圖；(1b)、(2b)、(3b)為本文改進的邊界點檢測結(jié)果圖；(1c)、(2c)、(3c)為半圓盤準則的邊界點檢測結(jié)果圖(本刊黑白印刷，相關(guān)疑問請咨詢作者)。

圖3 邊界點檢測實驗結(jié)果圖

圖4為各個點對應(yīng)算法判定值的區(qū)間分布圖，圖4中表明本文算法(雙半圓盤準則)和半圓盤準則邊界點檢測算法結(jié)果，圓圈點表示外邊界點，星號點表示內(nèi)邊界點。本實驗中采用半圓盤邊界檢測算法檢測邊界點數(shù)目略微多于本文算法的原則。由結(jié)果可知，本文算法邊界點檢測結(jié)果更好，邊界點均勻程度更好，并且能夠在一定程度上排除噪聲點所帶來的影響，因而其魯棒性更高。對本文算法提出范圍為0.6～3.4共28個區(qū)間，半圓盤準則為從0～28共28個區(qū)間，對其進行歸一化得到區(qū)間分布點數(shù)直方圖。由圖4可知：本文算法邊界點范圍為>2.0，對應(yīng)圖中的>14的值；半圓盤準則為>0.255R的數(shù)值，實驗中R值為28，即>7.13的為邊界點。經(jīng)上述分析，本文提出的邊界點判定方法使得邊界點和非邊界點分界明顯，而半圓盤方法邊界點和非邊界點分布密集，不易區(qū)分。

圖4 各個投影點對應(yīng)判定值結(jié)果分布區(qū)間圖

實驗結(jié)果表明質(zhì)心點位置精度對邊界點檢測結(jié)果具有較大的影響，可以通過改變ka值進行多次實驗來獲取較好的檢測邊界點的效果，圖4所示為ka=2.0時的結(jié)果。通過多次實驗表明本算法穩(wěn)定、有效且計算效率較高。

5 結(jié)語

通過多次實驗表明本算法穩(wěn)定、高效、檢測結(jié)果較好，可以有效地將邊界點檢測出來，達到預(yù)期目標。該算法在多次實驗后可以確定在值的選擇范圍上本算法的有效范圍較小，相比于文獻[2]可以快速地確定適當?shù)闹?。相比于文獻[5]而言，該算法具有更簡潔的運算原則，因而計算速度更快，對硬件要求更低。在多次實驗中發(fā)現(xiàn)，偶然會出現(xiàn)檢測結(jié)果出錯的情況，并且內(nèi)邊界檢測比外邊界檢測更困難(可能曲率較小的原因)，出現(xiàn)這種現(xiàn)象原因猜測為簡單將圓盤分為兩個半圓，應(yīng)該是根據(jù)密度不同將圓盤分為兩個區(qū)域，再統(tǒng)計投影點數(shù)目進行比較可以得到較好的效果?？傮w來講，該算法簡單、快速、穩(wěn)定，噪聲的影響較小，可以快速地實現(xiàn)邊界點的提取。