趙 迪 1，2，胡夢雅 1，李世其 2，紀(jì)合超 2，何 寧

(1.湖北工業(yè)大學(xué)，武漢 430068；2.華中科技大學(xué)，武漢 430074；3.中國航天員科研訓(xùn)練中心，北京 100094)

1 引言

移動機(jī)器人的應(yīng)用場景已延伸至復(fù)雜地形環(huán)境(包含凹坑、坡、臺階等)，這些復(fù)雜地形因素會影響移動機(jī)器人執(zhí)行巡視探測任務(wù)，超過越障極限的地形起伏會使機(jī)器人無法通過，不及時的地形信息感知也會影響機(jī)器人的探測安全與效率。如移動機(jī)器人在進(jìn)行行星探測時，由于先驗知識匱乏，需要在根據(jù)指令巡視探測的同時，對周圍環(huán)境地形信息進(jìn)行感知。因此為保證移動機(jī)器人的探測安全，即時、高效地感知地形信息尤為重要。

地形信息感知方法根據(jù)傳感器數(shù)據(jù)的不同，主要包含振動信號數(shù)據(jù)、基于視覺或激光雷達(dá)獲取的數(shù)字高程模型(Digital Elevation Model，DEM)數(shù)據(jù)、RGB數(shù)據(jù)、深度數(shù)據(jù)、點云數(shù)據(jù)等。其中，振動信號分析通過對機(jī)器人探測過程中的振動信號進(jìn)行分類，但在沒有先驗知識的前提下，該方法容易使機(jī)器人處于危險狀態(tài)；基于DEM數(shù)據(jù)的分析方法多用于包括高程在內(nèi)的各種地貌因子的全局描述，但DEM圖像數(shù)據(jù)的比例尺較大，會造成局部地形信息缺失；Blas等采用顏色紋理實現(xiàn)自然地形圖像的在線快速分割，但是顏色信息受外部環(huán)境因素影響較大，分割穩(wěn)定性難以得到保障；基于點云的地形描述可以快速準(zhǔn)確地獲得場景的幾何信息，其中Broten等通過計算各個柵格的加權(quán)平均高度來構(gòu)建高程地圖，能輔助機(jī)器人在未知的室外環(huán)境下運作，但該方法無法準(zhǔn)確表示場景中地形信息；Gingras等通過高程劃分可通行區(qū)域與障礙區(qū)域，并采用改進(jìn)的三角網(wǎng)格法對可通行區(qū)域進(jìn)行地形重建以及路徑規(guī)劃，但該方法在含一定坡度的路面環(huán)境下難以適用。

本文針對移動機(jī)器人在巡視探測過程中對復(fù)雜地形信息的感知問題，提出一種基于點云的地形信息感知與快速三維場景重建的方法。首先采用Kinect2.0深度(RGB-D)相機(jī)獲取原始數(shù)據(jù)，對得到的三維點云數(shù)據(jù)進(jìn)行濾波降噪等處理；然后使用改進(jìn)的隨機(jī)采樣一致性算法(Random Sample Consensus，RANSAC)擬合基準(zhǔn)面，并以此作為移動機(jī)器人運行平面；其次使用基于密度的聚類算法(Density-Based Spatial Clustering of Applications with Noise，DBSCAN)對剩余的三維點云數(shù)據(jù)進(jìn)行分類聚合以獲得地形特征點集，同時為簡化地形特征點集并確定其輪廓，采用凸包算法(Convex Hull)對分類后三維點云數(shù)據(jù)進(jìn)行處理；最后結(jié)合獲取的基準(zhǔn)面與地形特征信息對移動機(jī)器人周圍的環(huán)境進(jìn)行快速三維重建，從而減少了對復(fù)雜地形環(huán)境信息感知與重建的時間。通過在沙地、臺階等復(fù)雜地形的場景下進(jìn)行模擬實驗，快速進(jìn)行三維場景重建，以證明本文方法的有效性。

2 地形信息感知與場景重建

2.1 算法流程

地形信息感知與場景重建算法主要流程如圖1所示。

圖1 算法流程圖Fig.1 Algorithm flowchart

將采集到的RGB-D數(shù)據(jù)轉(zhuǎn)換為點云數(shù)據(jù)，進(jìn)行濾波降噪以及RANSAC算法估計基礎(chǔ)平面；然后采用基于密度聚類的算法感知地形特征信息(凹坑、坡、臺階)，并用凸包圖形學(xué)方法簡化特征信息，最后進(jìn)行三維場景重建。

2.2 原始點云數(shù)據(jù)處理

為了快速三維場景重建，需對原始點云數(shù)據(jù)進(jìn)行處理，獲取有效的基準(zhǔn)平面與地形特征信息。

2.2.1 基準(zhǔn)平面獲取

濾波降噪完成后獲得點云數(shù)據(jù)集

X

={

x

，

x

，…，

x

}。在移動機(jī)器人巡視探測過程中，為區(qū)分復(fù)雜地形中凸起障礙和凹陷障礙，可使用RANSAC算法擬合基準(zhǔn)面作為移動機(jī)器人的運行平面，定義高于基準(zhǔn)面的地形為凸起障礙，低于基準(zhǔn)面的地形為凹陷障礙。傳統(tǒng)RANSAC算法可以在大量離散數(shù)據(jù)集中獲得高精度、一致性模型參數(shù)，但是其參數(shù)設(shè)置難以滿足各不同地形下基準(zhǔn)面擬合的需要，同一參數(shù)設(shè)置難以滿足變化較大的地形環(huán)境，本文提出改進(jìn)的RANSAC算法是通過在機(jī)器人越障能力極限

h

范圍內(nèi)設(shè)置自適應(yīng)閾值

t

，即在

h

范圍內(nèi)的地形起伏對機(jī)器人移動不構(gòu)成影響。改進(jìn)RANSAC算法流程如下:1)計算

X

中點到迭代平面距離

d

，

μ

為所有點沿垂直地面方向的平均距離，并設(shè)置閾值為

t

，式(1)為自適應(yīng)閾值

t

的計算公式。

2)若

d

≤

t

，則認(rèn)為

x

為局內(nèi)點

n′

，并統(tǒng)計局內(nèi)點個數(shù)。3)對1)、2)步驟進(jìn)行重復(fù)迭代

k

次，其中

k

如式(2)所示。

4)選擇局內(nèi)點最多的平面為最優(yōu)平面模型

P

(

ax＋b y＋cz=d

)，并獲得該模型

P

參數(shù)

a

、

b

、

c

、

d

作為該點云數(shù)據(jù)的基準(zhǔn)面參數(shù)值。

本文使用離群點剔除算法以及改進(jìn)RANSAC算法，在Matlab中對點云數(shù)據(jù)進(jìn)行仿真處理，結(jié)果如圖2所示。

圖2 離群點剔除算法以及改進(jìn)RANSAC算法仿真效果Fig.2 Simulation effect of outlier elimination algorithm and improved RANSAC algorithm

由圖2可知，離群點剔除效果較好，且能有效擬合該復(fù)雜地形的基準(zhǔn)平面。

2.2.2 點云數(shù)據(jù)聚類

通過獲取基準(zhǔn)面，對凸起障礙和凹陷障礙進(jìn)行初步分割，但由于復(fù)雜地形的凹陷和凸起等特征形狀存在多樣且隨機(jī)連續(xù)分布的特性，無法根據(jù)幾何形狀對點云特征進(jìn)行信息感知與語義分割。因此，為得到具有語義信息的特征點集，需要對各不同特征的點云數(shù)據(jù)進(jìn)行聚類分割，使得各組點云數(shù)據(jù)能有效表示該環(huán)境下地形特征。為方便進(jìn)行聚類處理，本文做出以下假設(shè)與定義:假設(shè)擬合基準(zhǔn)面為平坦平面，即點垂直高度上的值變化可以忽略不計。定義基準(zhǔn)平面的點云數(shù)據(jù)為無需聚類數(shù)據(jù)，離群及密度小的點云集為離散噪聲點集。

為滿足上述假設(shè)與定義條件，首先對濾波降噪后點云數(shù)據(jù)

X

進(jìn)行聚類預(yù)處理，通過統(tǒng)計分析剔除離散噪聲點集；剔除無須聚類點集即基準(zhǔn)面點集；定義低于平面的數(shù)據(jù)集為

G′

(

j=

1，2，…，

m′

)，高于平面的數(shù)據(jù)集記為

H′

(

k=

1，2，…，

h′

)。

通過聚類預(yù)處理各地形特征被分割成不連通且具有一定密度的子集。在使用聚類算法時，各不同子集之間距離信息和密度信息是感知聚類特征的關(guān)鍵因素，故采用DBSCAN聚類算法對各不同子集進(jìn)行聚類，該算法步驟如下:

1)對各子集建立KD索引樹；

2)設(shè)置搜索半徑

r

、聚類最少點數(shù)

Min

以及聚類最大點數(shù)

Max

；3)進(jìn)行最近鄰搜索(K-NearestNeighbor)算法，設(shè)

s

為點集中兩點間歐氏距離；4)設(shè)置計數(shù)變量

N

初始值為0，則當(dāng)

s＜r

可視為同一類地形特征信息點，并令

N

=

N

＋1；當(dāng)

N

＜

Min

值時，該點集未構(gòu)成聚類；當(dāng)

N

＞

Max

值時，終止該子集聚類進(jìn)程。5)重復(fù)步驟2)～4)，直到完成所有子集的聚類過程，并得到

G′

(

j=

1，2，…，

m′

)，

H′

(

k=

1，2，…，

h′

)。其中，搜索半徑

r

與聚類最少點數(shù)

Min

根據(jù)所使用相機(jī)的參數(shù)與采集地形特征進(jìn)行設(shè)置。對降噪后點云數(shù)據(jù)

X

進(jìn)行DBSCAN聚類處理后的效果圖如圖3所示。

圖3 DBSCAN聚類效果圖Fig.3 DBSCAN clustering effect diagram

圖3可以看出，采用DBSCAN聚類算法能有效分割出各地形特征點集，并感知各點集的位置信息與密度信息。

2.3 地形信息感知與快速三維重建

為實現(xiàn)快速的場景重建，需簡化地形特征信息。本文在進(jìn)行地形信息感知中，對各點云子集信息進(jìn)行簡化處理，通過計算得到其位置信息的中心坐標(biāo)以及輪廓信息的包絡(luò)體，以此代表特征點集。該過程如下:

1)對各聚類點集

G′

(

j=

1，2，…，

m′

)、

H′

(

k=

1，2，…，

h′

)，利用式(3)求出其中心坐標(biāo)。

式中，

c

=(

x

，

y

，

z

)為某聚類點集中心坐標(biāo)，

n

表示該聚類點集中點個數(shù)。2)采用凸包算法計算各聚類點集輪廓范圍信息。選取某聚類點集

G′

中任意四點構(gòu)成一個初始的四面體；對

G′

中所有剩余點

G′

進(jìn)行判斷，若該點在四面體外部，則刪除與此點相對的面，形成新的多面體；若該點在四面體內(nèi)部，則跳過該點。對所有聚類點集重復(fù)以上步驟。

通過上述簡化處理，取各聚類點集的中心坐標(biāo)、輪廓信息作為障礙物信息，再結(jié)合擬合的基準(zhǔn)平面進(jìn)行地形信息重建，相較于原始點云數(shù)據(jù)的障礙物描述，不僅可以大大降低地形特征維度，且減小了需要傳遞的測量值數(shù)據(jù)量，從而提升了時間效率。圖4即為仿真數(shù)據(jù)三維重建后的效果圖。圖中可知本文方法可有效感知關(guān)鍵障礙物信息并進(jìn)行快速場景重建，極大地減少了程序運行數(shù)據(jù)量。

圖4 點云數(shù)據(jù)三維重建Fig.4 Three-dimensional reconstruction of point cloud data

3 實驗與驗證

3.1 實驗條件

對本文方法在實際場景中的可行性與運行結(jié)果進(jìn)行驗證，實驗硬件設(shè)備條件如表1所示。

表1 實驗硬件設(shè)備Table 1 Hardware specifications

實驗場景選擇具有代表性的沙地實驗環(huán)境，該環(huán)境具有連續(xù)高低起伏等特點，適合作為復(fù)雜地形環(huán)境下地形感知與重建的實驗場地。本文在強(qiáng)自然光照條件下采集多幀數(shù)據(jù)，每幀通過融合生成包含約20 000個點的點云數(shù)據(jù)集。選擇一幀包含該環(huán)境下各種噪聲的特征點云數(shù)據(jù)進(jìn)行分析，圖5(a)所示為沙地實驗環(huán)境，圖5(b)為該環(huán)境下融合生成的點云數(shù)據(jù)。

圖5 實驗環(huán)境及該環(huán)境點云數(shù)據(jù)Fig.5 Experiment environment and point cloud data of the environment

3.2 實驗數(shù)據(jù)分析

3.2.1 點云數(shù)據(jù)處理實驗效果與分析

在擬合基準(zhǔn)面時，通過使用改進(jìn)RANSAC算法計算并得到閾值

t=

3.26，并當(dāng)?shù)螖?shù)達(dá)到200次時滿足期望需要。圖6(a)為原始點云數(shù)據(jù)，紅點表示基準(zhǔn)面局內(nèi)點，這些點將會作為擬合基準(zhǔn)面的點集，藍(lán)點表示擬合基準(zhǔn)面后剩余點；圖6(b)為該環(huán)境下點云數(shù)據(jù)側(cè)視圖，原始點云數(shù)據(jù)在垂直方向上分布變化較大，且其中包含某些尖銳噪聲點，可被視為點云數(shù)據(jù)中離群點，會影響后續(xù)聚類算法的效果，故應(yīng)使用離群點剔除算法將其剔除；圖6(c)為局內(nèi)點到擬合基準(zhǔn)面距離值分布情況，其直方圖分布情況與高斯曲線吻合，實現(xiàn)了較好的擬合效果；圖6(d)為擬合基準(zhǔn)面后剩余點云數(shù)據(jù)。對圖6(d)中剩余點云使用DBSCAN聚類算法，并設(shè)置近鄰搜索半徑為

r

=0.02 m時，可得到進(jìn)行DBSCAN聚類算法后特征點集在原始點云數(shù)據(jù)中的位置信息，如圖7所示。

圖6 原始點云數(shù)據(jù)離群點剔除以及基準(zhǔn)面擬合Fig.6 Outlier elimination of original point cloud data and datum surface fitting

3.2.2 特征地形點云信息重建

對圖7中各特征點集進(jìn)行凸包輪廓提取，簡化特征點，以輪廓點簇生成包絡(luò)體表示起伏地形信息。根據(jù)此包絡(luò)體的范圍(高度、深度)判斷當(dāng)前地形特征信息。其中

H

、

H

表示為凸起障礙，

G

表示為凹陷障礙，具體數(shù)據(jù)如表2所示。

圖7 DBSCAN聚類后特征點集信息Fig.7 Feature point set information after DBSCAN clustering

從表2中可以看出，在進(jìn)行包絡(luò)體提取后，使用相對較少的點云數(shù)據(jù)即可表示該地形特征，大大降低了計算障礙物輪廓的復(fù)雜度，提高了運算效率。圖8為使用包絡(luò)體信息并結(jié)合擬合基準(zhǔn)面信息，將三維場景進(jìn)行重建，與原始數(shù)據(jù)直接進(jìn)行重建的效果進(jìn)行對比。圖8可以看出，相較于原始數(shù)據(jù)直接進(jìn)行重建，本文方法較好還原了該復(fù)雜環(huán)境地形特征，同時減少了約2/3的時間，為移動機(jī)器人避障提供了可靠保障。

表2 地形特征提取Table 2 Terrain feature extraction

圖8 原始數(shù)據(jù)與本文方法地形重建效果對比Fig.8 Comparison of the original data and the terrain reconstruction effect of this method

4 實驗效果對比分析

4.1 算法執(zhí)行效果

本文算法主要由點云數(shù)據(jù)處理以及地形信息重建構(gòu)成。在分析點云數(shù)據(jù)處理算法的執(zhí)行效果時，分別從基準(zhǔn)面擬合算法以及聚類算法兩方面進(jìn)行分析。

4.1.1 擬合基準(zhǔn)面效果

聚類效果優(yōu)劣很大程度上取決于基準(zhǔn)面擬合效果。實驗中地形點云數(shù)據(jù)包含大量離群點，這對于擬合基準(zhǔn)面有較大影響。針對基準(zhǔn)面擬合效果，本文對比了最小二乘法、特征值法以及改進(jìn)RANSAC算法在處理相同實驗采集數(shù)據(jù)時效果。其中實驗數(shù)據(jù)為在相同參數(shù)設(shè)置下，各方法均進(jìn)行20次實驗取平均值得到的基準(zhǔn)面方程，如表3所示。其中

T

表示運算時間，

σ

是數(shù)據(jù)標(biāo)準(zhǔn)偏差，

a

，

b

，

c

，

d

為基準(zhǔn)面方程

ax＋b y＋cz=d

參數(shù)。由表3可知，在處理包含大量離群點的地形點云數(shù)據(jù)時，受到離群點影響，最小二乘法和特征值法的標(biāo)準(zhǔn)偏差

σ

較大，擬合效果不理想。而本文通過改進(jìn)RANSAC算法，使用局內(nèi)點擬合基準(zhǔn)面，相較于其他2種方法具有標(biāo)準(zhǔn)偏差小、時間效率較高等特點。

表3 基準(zhǔn)面擬合算法效果對比Table 3 Comparison of the effect of base-level fitting algorithms

在傳統(tǒng)RANSAC算法中，閾值

t

的選取對擬合效果影響較大，通常較高的

t

值會導(dǎo)致局內(nèi)點分割過量，難以去除無效點；而較小的

t

值會導(dǎo)致欠分割，難以保存有效的局內(nèi)點。在上述點云數(shù)據(jù)中，對相同數(shù)據(jù)選擇不同

t

值分別使用RANSAC算法擬合，得到圖9所示擬合結(jié)果，表4所示為不同

t

值對擬合平面的影響。通過對圖9和表4中不同

t

值對RANSAC算法影響分析可得出:

表4 不同t值對RANSAC算法影響Table 4 The influence of different t values on RANSAC algorithm

圖9 RANSAC算法中在不同t值下剩余點云數(shù)據(jù)Fig.9 The remaining point cloud data under different t values in the RANSAC algorithm

1)從時間上來看閾值

t

與運行時間近似成正比，且閾值越大，計算的局內(nèi)點數(shù)越多，耗時越久。2)隨著閾值

t

的增大，局內(nèi)點數(shù)越多，所占比例越大；若選取的

t

較大時則會將過多無效點或誤差點認(rèn)定為局內(nèi)點；若選取的

t

較小則會剔除應(yīng)該選擇的有效點，擬合平面效果不明顯，影響聚類算法。因此

t

應(yīng)該選擇在一定的閾值區(qū)間內(nèi)可達(dá)到較好的分割效果。3)改進(jìn)RANSAC算法通過設(shè)置自適應(yīng)

t

值，動態(tài)的改變了與

t

值呈正相關(guān)的比例系數(shù)

w

值。隨著地形變化，比例系數(shù)

w

發(fā)生改變從而會改變迭代次數(shù)

k

，通過不同的迭代次數(shù)達(dá)到期望概率。

4.1.2 聚類效果分析

針對特征點集聚類效果，通常采用緊密型指標(biāo)(Compactness，CP)、間隔性指標(biāo)(Separation，SP)、戴維森堡丁指數(shù)(Davies-Bouldin，DBI)、鄧恩指數(shù)(Dunn Validity Index，DVI)等指標(biāo)進(jìn)行分析。其中CP表示類中各點到聚類中心的平均距離，該值越低意味著類內(nèi)聚性越好；SP代表各聚類中心兩兩之間平均距離，SP越高意味各類間間聚越遠(yuǎn)；DBI代表任意兩點簇內(nèi)平均距離之和與兩聚類中心距離之比的最大值；DVI代表任意兩點簇元素的類間最短距離與任意點簇中類內(nèi)最大距離之比。

本文采用上述4種評價標(biāo)準(zhǔn)，選用3種常用算法:K-Mean算法、層次聚類算法、DBSACN算法，對去除基準(zhǔn)面擬合點后的剩余點云數(shù)據(jù)進(jìn)行聚類。在聚類效果中，通常簇內(nèi)越緊密、簇間越分離代表聚類效果越好。這3種聚類算法效果如圖10和表5所示。

圖10 不同算法的地形聚類效果Fig.10 Terrain clustering effect of different algorithms

表5 聚類評價表Table 5 Cluster evaluation table

從圖10以及表5中可以看出，層次聚類相對其他2種算法耗時較長，聚類緊密性較差，DBI分類適確性較差且DVI指標(biāo)較差，故層次聚類不適合地形特征感知。K-mean聚類算法耗時較短，但相較于DBSCAN算法，其CP和DBI指標(biāo)較高，SP和DVI指標(biāo)較低，其聚類效果劣于DBSCAN算法，此外K-mean聚類需要選取

K

值，且對噪聲、孤立點數(shù)據(jù)敏感，故不適合地形特征感知。DBSCAN算法耗時較短，聚類簇緊密性較好，簇間分隔性較遠(yuǎn)，可以較好的聚類特征地形。綜上所述，DBSCAN聚類算法相對其他算法效果更好。

4.2 地形信息重建效果分析

地形信息重建效果主要取決于重建精確度以及耗時長短。為了驗證本文三維重建方法效果，在不同類型復(fù)雜場景下進(jìn)行實驗(表6)。這些場景分別為沙地、樹林、堆積雜物、減速帶、臺階等。通過分析場景地形特征點云數(shù)據(jù)量、地形信息感知時間、復(fù)雜場景重建時間，得到如表7所示數(shù)據(jù)。對比表6各環(huán)境下的效果圖，可以看出本文使用的凸包算法在地形信息重建過程中不僅識別出所有地形特征，且有效保留了各地形特征信息。結(jié)合表6可知，在保證各地形特征的位置與輪廓精度前提下，本文方法極大縮短了重建時間，符合復(fù)雜環(huán)境下移動機(jī)器人執(zhí)行探測任務(wù)時的避障需要。

表6 場景1～5的RGB圖、特征圖、原始數(shù)據(jù)重建以及本文方法場景重建Table 6 RGB map,feature map,original data reconstruction of scene 1～5 and scene reconstruction of the method in this paper

表7 多場景重建對比Table 7 Comparison of multi-scene reconstruction

5 結(jié)論

1)改進(jìn)的RANSAC算法可以從包含大量離群點的數(shù)據(jù)集中提取出一致性較好的擬合平面；

2)通過凸包算法提取特征輪廓，能有效保留特征信息，且簡化無用信息，大幅度減少了數(shù)據(jù)運行量；

3)結(jié)合簡化的擬合平面方程快速重建地形可以極大地提高了數(shù)據(jù)利用率與時間利用率，在復(fù)雜地形中識別定位障礙物具有有效性和可行性，能實現(xiàn)復(fù)雜地形下的信息感知與快速重建。