自動駕駛汽車虛擬測試中的樹木點云生成方法

唐維軍，徐 琨，柳有權，夏 懸

長安大學 信息工程學院，西安710064

隨著人工智能技術的不斷發(fā)展，自動駕駛為解決交通擁堵、事故頻發(fā)等問題提供了一種新途徑，自動駕駛汽車測試成為自動駕駛的一個重要課題。傳統(tǒng)的道路場地測試存在效率低、測試代價高、測試路況有限、場景環(huán)境氣候單一、難以重復測試等不足[1-2]。自動駕駛汽車虛擬測試具有效率高、安全、成本低、場景和交通流構建靈活等特點[3-8]，已經成為自動駕駛測試評價的重要手段。

激光雷達是自動駕駛中最重要的傳感器之一，激光雷達三維點云蘊涵著豐富的空間位置信息，如空間各點之間相鄰結構關系、被掃描物體表面的紋理細節(jié)等，極大地拓展了自動駕駛環(huán)境感知方法，三維激光雷達數(shù)據(jù)模擬生成是自動駕駛汽車虛擬測試中的重要任務。樹木模型是虛擬交通場景中極具代表性的自然景觀，具有種類繁多、外表形狀千姿百態(tài)、拓撲結構復雜以及枝條縱橫交錯等特點，建立高效、真實性強的樹木三維激光點云仍然是自動駕駛汽車虛擬測試的難點問題之一。

虛擬場景中樹木建模的常用方法有基于三角面片的方法、數(shù)據(jù)驅動的方法、L系統(tǒng)等[9-14]，在實時環(huán)境中常用三角面片的方法，該方法主要包括基于布告牌的方法和基于幾何模型的方法?；趲缀文Ｐ偷姆椒ㄍㄟ^大量三角形面片構建樹木幾何結構，對于結構復雜的樹木，生成點云的實時性難以保證?；诓几媾频姆椒ㄍㄟ^兩個矩形面片建模樹木，三角形面片數(shù)量少，生成點云效率高。

本文將布告牌樹木建模方法引入到樹木的激光雷達三維點云生成中，提出了一種基于布告牌空間變換的快速樹木三維點云生成方法。以布告牌的紋理圖像為輸入，根據(jù)紋理透明度獲取樹木二維平面點云分布，依據(jù)點云的法向量提取二維輪廓點云，并進行點云均勻化操作，利用樹木結構的先驗知識進行旋轉、偏移和尺度變換，最終生成樹木三維點云數(shù)據(jù)。為了驗證本文方法的有效性，本文又提出了空間直方圖三維點云相似度評價方法，最后，通過不同類型樹木的三維點云數(shù)據(jù)驗證了本文方法具有精度高、速度快的特點。本文方法為虛擬交通場景中大規(guī)模樹木的三維點云快速生成提供了一種新的方法與思路。

1 相關工作

1.1 激光雷達三維點云模擬生成

激光雷達模擬生成的主要方法有基于物理模擬的方法、基于數(shù)據(jù)驅動的方法、基于物體表面模型的方法?；谖锢砟M的方法分別對場景數(shù)據(jù)、激光探測距離、大氣傳輸特性以及噪聲等關鍵要素建模，并通過坐標轉換將激光探測距離轉換為三維數(shù)據(jù)，實現(xiàn)激光雷達三維數(shù)據(jù)模擬。Michael等[15]對蓋格模式雪崩二極管（Geiger-mode Avalanche Photodiode Detectors，APD）三維成像進行模擬，該方法假設物體表面是朗伯散射體，應用光線追蹤法獲得成像景物到APD陣列的距離矩陣和反射率矩陣，并考慮太陽光、暗電流等因素的影響，給出激光雷達探測距離的方法，最終以圖像的形式呈現(xiàn)點云數(shù)據(jù)的模擬結果?；谖锢砟M的方法需要分別考慮發(fā)射器功率、大氣環(huán)境、接收器性能、目標特性等因素影響，建立的物理模型可擴展性差[16]，特別是當場景中有植物、人體等非剛性物體時，為了保證點云數(shù)據(jù)的準確性一般采用多樣本射線追蹤方法或建立粒度更小的幾何模型，但算法的實時性很難保證[17]。基于數(shù)據(jù)驅動的方法主要從大量的場景激光雷達數(shù)據(jù)中學習獲得激光雷達數(shù)據(jù)的分布信息。Browning等[18]建立了一個包含射程返回和滲透率，同時考慮激光雷達射程的統(tǒng)計分布、噪聲、混合像素效果的混合隨機仿真模型。該模型能夠有效地考慮場景的變化性，并能根據(jù)測量的大規(guī)模激光雷達數(shù)據(jù)完成模型的自動估計。Abhijeet等[19]在野外環(huán)境中采集樹、灌木的真實點云數(shù)據(jù)，在虛擬場景中通過三角形面片構建真實樹、灌木的模型基元，以這些模型基元作為虛擬場景的輸入數(shù)據(jù)，真實點云與模型場景位置對應得到填充場景數(shù)據(jù)，并將其作為真值，多次訓練得到真實點云與模型基元的對應關系，最后輸入測試的模型基元可模擬出點云數(shù)據(jù)?；跀?shù)據(jù)驅動的方法的難點在于真實數(shù)據(jù)的采集，真實數(shù)據(jù)的完整性決定模擬結果。

基于物體表面模型的方法通過三角形面片等方法構建物體表面模型，模擬激光雷達的飛行時間原理，采用光線追蹤方法，計算出激光射線與物體表面模型的交點，獲得場景中物體的點云數(shù)據(jù)。該方法可擴展性強、設計簡單[20-22]。Yue等[21]在游戲中構建車輛等場景模型，并使用光線追蹤技術計算光線與第一個擊中的模型的交點產生LiDAR點云數(shù)據(jù)。Su等[23]采用3D引擎OSG（Open Scene Graph）以樹數(shù)據(jù)結構存儲場景模型，根據(jù)激光雷達的位置、姿勢、范圍等信息查詢區(qū)域的場景模型數(shù)據(jù)，通過渲染該區(qū)域獲得點云信息。

1.2 激光雷達點云相似度評價

與傳統(tǒng)的視頻、圖像等數(shù)據(jù)表示相比，三維激光點云具有非結構化、無序性、不完整的特點。在衡量三維點云數(shù)據(jù)間的差異時，要求三維點云數(shù)據(jù)的輸入順序不能影響結果。點云相似度評價的難點一方面在于在網格空間中很難使用歐氏距離等常用距離測度，另一方面在于評價兩個點云所表示的相似度。目前，常使用兩個點云的距離測度評價離散點云相似度。

Hausdorff距離是早期點云相似度計算的主要方法。Hausdorff距離需要計算一個點集中所有點與另一點集所有點之間的距離。對于三維點云數(shù)據(jù)集合，計算代價非常大。Zhang等[24]提出了一種用于測量3D模型和3D點云之間的部分相似度的快速方法，部分相似度定義為模型的加權表面積與從模型到點云的加權單側Hausdorff距離之比。Zhang等[25]提出了一種基于擴散搜索方法的Hausdorff距離的精確計算方法，該方法不需要掃描每個點，將當前斷點記錄為下一個內部循環(huán)的擴散中心，可以顯著提高計算效率。Zhang同時提出了稀疏點集和密集點集兩種不同的距離計算方法，大大降低了距離計算的時間復雜度。

Chamfer距離[26]通過測量兩幅圖像平均最近平方距離表示兩幅圖像的相似度。EMD（Earth Mover Distance）[27]最早應用于圖像檢索，通過計算從一幅圖像轉化為另一幅圖像的代價來度量兩幅圖像的相似度，代價越小，兩幅圖像相似度越大。Fan等[28]和Huang等[29]分別將這兩個距離測度作為損失函數(shù)使得生成的點云與原始點云趨于最小。Dahlia等[30]提出一種深度學習的方法，通過計算一個點云的點與該點云表面的采樣點之間的EMD和Chamfer距離，使用深度學習網絡估計從點到底層連續(xù)表面的這兩個距離函數(shù)。

Geodesic距離[31]是另一種距離測度，它提供了不受變形影響的度量，以及依賴于點云向量描述符之間距離的度量。

2 基于布告牌空間變換的快速樹木三維點云成方法

幾何建模所得樹木的三角形面片數(shù)目多，需要反復計算激光與三角形面片的交點，生成整棵樹的三維點云數(shù)據(jù)通常需要數(shù)秒，難以滿足虛擬測試系統(tǒng)的實時性要求。布告牌僅通過兩個矩形面片（8個三角形面片）對目標進行建模，三角形面片數(shù)較少。因此，本文使用布告牌建立樹木的三維模型。圖1給出了使用布告牌，采用光線追蹤技術[32]直接生成的三維點云數(shù)據(jù)。

圖1 直接使用布告牌的樹木點云

由圖可知，直接使用布告牌生成的三維點云數(shù)據(jù)缺少樹木的三維空間信息，誤差很大。針對這一不足，本文提出了一種基于布告牌空間變換的快速樹木三維點云生成方法，方法框架示意圖如圖2所示。

圖2 本文點云生成方法框架圖

該方法分二維輪廓點云生成和空間三維點云生成兩部分。首先根據(jù)樹木紋理的透明度獲得樹木的二維平面點云數(shù)據(jù)，采用法向量估計法提取樹木的二維平面點云的輪廓，并對得到的輪廓點云均勻化，均勻化后的二維輪廓點云進行旋轉得到三維初始點云，最后根據(jù)樹木結構的先驗知識，進行隨機偏移和尺度先驗變換獲得最終的樹木空間三維點云。

2.1 二維輪廓點云生成

設前景樹木透明度?=1，背景透明度?=0，布告牌的紋理圖像大小為pixelw×pixelh，布告牌兩個矩形面片的紋理一致，共有8個三角形面片。遍歷紋理圖像，依據(jù)式（1）計算激光束與布告牌交點的像素坐標。

其中，pixelx、pi xely為紋理的像素坐標，UVx、UVy為紋理坐標。若像素點透明度為1，則將該點的空間信息加入到二維點云集合中，否則忽略該點。

點云內部點的鄰域點分布具有相對均勻性，而輪廓點的鄰域點分布不具有均勻性，如圖3（a）、（b）所示。本文將點云中點的法向量方向作為點云輪廓點的判斷依據(jù)。通過點云中任意一點P的K鄰域構造鄰域微切平面，將微切平面的法線定義為P點的法向量。點云輪廓點提取算法描述如下：

采用八叉樹K近鄰搜索算法構成點云每一點Pi的K鄰域點Nj(j=0,1,…,k)，將其作為組成Pi的鄰域參考點集X，得到該點集的最小二乘微切平面F；點集X中的各點向微切平面F投影，投影點集記為X′，投影點記為Nj′，Pi的投影點Pi與其最近鄰點投影點構成的向量記為Pi′Nk′，與其他點構成的向量記為Pi′Nj′(j=0,1,…,k-1)；Pi′Nk′與微切平面法向量的叉積為V，分別求取Pi′Nj′與Pi′Nk′的夾角αj以及Pi′Nj′與V的夾角βj，如圖3（c）所示；若βj>π/2，則αj=2π-αj；對所有的αj進行升序排序，并添加0和2π兩個極值角度，得到角序列(0,α1,α2,…,αk,2π)；計算角序列相鄰夾角差Lk=αi+1-αi，若相鄰夾角差最大值Lmax大于角度閾值，則Pi是輪廓點。

圖3 輪廓點提取示意圖

在生成二維平面點云時，激光雷達掃描的水平分辨率不高或者紋理透明度計算存在誤差，會導致點云缺失，因此，在生成二維輪廓點云后，本文使用線性插值的方法進行輪廓點云均勻化，設置相鄰點云距離閾值，在大于閾值的點云之間插入點云，將小于閾值的點云刪除。

2.2 空間三維點云生成

設虛擬激光雷達發(fā)射的激光束的垂直分辨率為?，水平分辨率為φ。以二維點云平面的對角線交點為旋轉中心點，繞Y軸分別順時針、逆時針分步旋轉90°，每步旋轉角度為θ,θ∈[-φ/2,φ/2]，如圖4所示。

圖4 旋轉示意圖

真實環(huán)境中大氣、激光雷達硬件等影響，三維點云存在噪聲或偏差。若僅僅通過旋轉二維輪廓點云獲得三維點云，會使點云數(shù)據(jù)過于整齊，與真實情況不符。

因此，在旋轉過程中，對點云數(shù)據(jù)進行隨機偏移操作，偏移操作通過繞X和Y軸旋轉實現(xiàn)。本文采用逆變換法[33]產生隨機旋轉角度，該方法使用均勻分布的隨機數(shù)生成服從指定分布的隨機數(shù)。

通過實驗獲得云杉、針葉樹、懸鈴木三種樹木的最優(yōu)偏移隨機分布及最優(yōu)參數(shù)，具體參數(shù)如表1所示。

表1 樹木點云偏移量最優(yōu)分布及參數(shù)

在真實場景中，樹干表面有凹陷，樹葉會向內卷縮，這兩種情況都會對真實激光點云產生影響。為模擬這些影響，本文進一步提出引入樹木結構先驗知識的點云尺度變換。依據(jù)每種樹木的樹冠和樹干高度信息，在樹冠部分和樹干部分的X方向和Z方向進行等比例隨機尺度變換。

綜上所述，本文的三維點云空間變換如式（2）所示：

其中，θ1、θ2分別為繞X軸和Y軸的旋轉角度，S為縮放矩陣，sx、sz分別為X、Z方向上的縮放比例，Qa、Qs分別為偏移、尺度變換的條件系數(shù)矩陣，根據(jù)樹木的樹冠和樹干的先驗知識，Qa、Qs分別為：

其中，E為單位矩陣，wcrown為二維平面點云輪廓的最大寬度，hstem為樹木點云的樹干高度。

3 空間直方圖點云相似度評價方法

三維激光點云具有非結構化、無序性、不完整的特點，樹木點云每一局部區(qū)域都有唯一的分布特征，這種分布特性不僅需要通過每一子空間內的點云數(shù)目反映，還應通過點云的空間位置信息反映。相對于通過Hausdorff等距離評價點云相似度的方法，空間直方圖點云相似度評價方法考慮了點云的空間位置信息，更能反映點云分布的相似度。且避免了計算一個點集中所有 點與另一點集所有點之間的距離，計算代價更小。因此，本文提出了空間直方圖的點云相似度評價方法。

三維點云空間量化為若干子空間，即進行空間柵格化，并將柵格化點云分別向XOY、XOZ、YOZ三個平面進行投影，統(tǒng)計三個投影平面的空間直方圖。

設二元映射I:x→v，x=為投影柵格的坐標，v為該柵格內的點云數(shù)目，點云的二階空間直方圖為：

其中，nb為第b個柵格內的點云數(shù)目，ub、Σb分別為第b個柵格內投影點云的坐標均值向量和協(xié)方差矩陣，B為投影柵格總數(shù)。

兩個點云空間直方圖h=和h′=的相似度ρ(h,h′)依據(jù)如式（6）計算：

其中，η為高斯歸一化常數(shù)。本文采用巴氏系數(shù)計算ρn( )

nb,n′b，如式（8）所示：

最后，將三個投影平面的空間直方圖相似度的加權和作為兩個點云的相似程度測度。

4 實驗結果及分析

本文在Unity3D平臺采用C#編程實現(xiàn)，實驗平臺軟硬件配置為i5-6550 CPU@3.2 GHz，16 GB，Windows10操作系統(tǒng)。虛擬激光雷達射線數(shù)目64線，最大距離200 m，水平分辨率0.25°，垂直分辨率0.4°，垂直視野26.9°，水平視野360°。為驗證本文方法的有效性，分別采用幾何模型方法[34]和本文布告牌空間變換方法生成云杉、針葉樹、懸鈴木三種類型的樹木點云，將幾何模型方法生成的樹木點云作為參考基準點云，幾何建模樹木的渲染結果作為布告牌的紋理貼圖。

4.1 相似度評價有效性實驗

首先使用幾何模型法生成棕櫚、紅木、松樹三種不同樹木模型及相應點云，如圖5所示。

圖5 不同樹木的模型與點云

計算棕櫚、紅木、松樹三種樹木點云兩兩之間的Hausdorff距離和本文的空間直方圖相似度，數(shù)據(jù)如表2所示。Hausdorff距離越大則兩個點云之間差異越大，空間直方圖相似度越小，兩個點云差異越大。由表2可知，使用Hausdorff距離和空間直方圖相似度評價方法，均可得到棕櫚和紅木的相似度最高，棕櫚和松樹的相似度最低的結論。

表2 不同樹木點云之間的相似度比較

表3給出了不同量化參數(shù)，使用本文評價方法得到的幾何模型樹木三維點云間的兩兩相似度。隨著投影柵格數(shù)目的增加，不同樹種間的相似度均迅速減小，投影柵格數(shù)為20×20以上時相似度在0.5以下，而同種樹木在不同投影柵格數(shù)的相似度始終為1。

表3 不同樹木點云之間的空間直方圖相似度

進一步實驗統(tǒng)計棕櫚、紅木、松樹三種樹木兩兩之間相似度評價的時間，本文方法和Hausdorff距離計算相似度的平均時間分別為0.513 s和0.847 s。綜上所述，本文提出的空間直方圖點云相似度評價方法有效且更快。

4.2 點云生成方法準確性實驗

在獲取布告牌建模樹木的二維平面點云時，保持虛擬車輛的虛擬激光雷達中心點的Z軸坐標值和布告牌建模樹木中心點的Z軸坐標值相同，防止受布告牌模型中另一矩形面片影響，產生噪聲點。幾何模型法及本文方法生成云杉、針葉木、懸鈴木點云結果如圖6所示。從圖6（a）和（e）可知，本文方法生成的點云在視覺上與幾何模型方法生成的點云結構相似。

圖6 本文方法點云生成結果（第一至第三行的樹木分別為云杉、針葉樹、懸鈴木）

采用本文的相似度評價方法進行相似度評價，表4給出了在不同量化參數(shù)下的計算結果。從表中可知，本文方法生成的點云和幾何模型法生成點云的平均相似度在90%以上，說明兩個樹木點云在三個投影平面內的分布均很相似，本文點云生成方法具有較高的準確性。

表4 本文方法與幾何模型生成點云的相似度

表5給出了投影柵格數(shù)為20×20時，本文方法中使用法向量輪廓提取、二維輪廓點云均勻化、三維點云隨機偏移、三維點云尺度先驗變換生成的樹木點云與幾何模型法生成點云的相似度。

表5 本文方法分步操作生成點云與幾何模型點云的相似度

實驗數(shù)據(jù)表明，在法向量提取的二維輪廓基礎上進行三維旋轉獲得的點云與幾何模型法生成點云的相似度平均在0.819左右，相似度較低。在此基礎上，分步使用輪廓點云均勻化、隨機偏移和尺度先驗變換，三種樹木的點云相似度均有提高，相似度平均值最終達到0.917左右，提高近10%。

4.3 點云生成方法時間效率實驗

表6給出了分別使用本文方法和幾何模型法，生成云杉、針葉樹、懸鈴木三種樹木的單條射線射出生成點云的平均生成時間和整棵樹木點云平均生成時間。

表6 點云生成時間統(tǒng)計數(shù)據(jù)

在單條激光射線點云生成中，幾何模型三角形面片數(shù)目相對較多，點云生成時間相對比本文方法略多。在整棵樹木點云生成中，幾何模型法需旋轉激光雷達車360°獲得樹木三維點云數(shù)據(jù)，點云平均生成時間為7.199 2 s。而本文方法旋轉布告牌建模樹木的二維輪廓點云，通過隨機偏移、尺度先驗變換，得到整棵樹木的三維點云數(shù)據(jù)。布告牌三角形面片個數(shù)少，大大減少了激光雷達射線與三角形面片計算交點的次數(shù)。同時，旋轉操作避免了頻繁通過光線追蹤法計算多條激光射線與三角形面片的交點，點云平均生成時間為0.071 9 s，僅為幾何模型法的1%。

圖7 點云生成平均幀率變化

在虛擬測試場景中，將本文方法生成的樹木點云通過動態(tài)加載和實時生成兩種方式加載到場景中，圖7給出了在30 s內生成16棵樹木點云的平均幀率變化曲線。實驗中每秒統(tǒng)計4次平均幀率值，共統(tǒng)計120次?？梢钥闯?，隨著時間的增長，實時生成點云方式的平均幀率隨之降低，最終在78 frame/s左右，而動態(tài)加載方式的平均幀率一直穩(wěn)定在400 frame/s以上。在虛擬測試應用場景中，動態(tài)加載方式不需要實時計算激光射線與三角形面片的交點，這種方式可以更加穩(wěn)定、可靠地加載三維點云數(shù)據(jù)并顯示。

5 結束語

本文提出了一種基于布告牌空間變換的快速樹木點云生成方法。選取幾何建模樹木的渲染結果作為布告牌模型的紋理，根據(jù)紋理透明度獲取二維平面點云，結合樹木結構的先驗知識，經過輪廓提取、均勻化、旋轉、隨機偏移及尺度先驗變換等操作，以更少的三角形面片數(shù)和更小的計算代價獲得樹木的三維點云數(shù)據(jù)。

為評價本文方法生成點云的準確性，本文提出一種空間直方圖的三維點云相似度評價方法，分別統(tǒng)計樹木點云在XOY、XOZ、YOZ三個投影平面內點云的二階空間直方圖，采用巴氏系數(shù)計算空間直方圖相似度。該評價方法能夠反映點云分布的相似度且更加高效。

通過實驗驗證，相對于幾何模型法，本文方法在單條激光射線點云生成和整棵樹木點云生成的時間上都有了較大幅度的提高，在虛擬測試場景中通過動態(tài)加載點云的方法，點云生成平均幀率穩(wěn)定、可靠。