應(yīng)用于增強現(xiàn)實變電運檢三維場景重建的增量八叉樹算法

焦進，遲小羽，賴秋，楊子力，儲園，楊坤蓮，楊銳

1. 云南電網(wǎng)有限責(zé)任公司曲靖供電局，云南 曲靖 655000 2. 北京航空航天大學(xué)青島研究院，山東 青島 266100 3. 昆明埃舍爾科技有限公司，云南 昆明 650000

數(shù)字孿生，即物理場景被復(fù)制為大小和內(nèi)容都完全一致的數(shù)字場景并加以應(yīng)用的數(shù)字化技術(shù)，在如今的各行各業(yè)中已經(jīng)得到了越來越廣泛地應(yīng)用[1]。一個標準的數(shù)字孿生模型構(gòu)建過程是通過傳感器、激光雷達和視覺等多種數(shù)字化手段對場景進行掃描和記錄，利用點云或三維實體方式對記錄后的數(shù)字場景進行重建和拼接，進而渲染重建結(jié)果并交互式地漫游瀏覽三維場景。在對數(shù)字場景進行預(yù)構(gòu)建的過程中，可利用專有設(shè)備采集數(shù)據(jù)并通過長時間的預(yù)先處理來完成；對于終端用戶直接參與檢查和驗收的三維渲染成果，它需要適配不同的用戶設(shè)備，并滿足用戶對實時性和結(jié)果真實性的要求。

對于一些特定的行業(yè)應(yīng)用需求，例如變電站的運行檢查輔助系統(tǒng)，終端用戶對于數(shù)字孿生場景的使用要求將更為苛刻。用戶常常會使用AR。增強現(xiàn)實頭盔(例如微軟公司的Hololens)作為承載平臺，在巡檢實際物理場景的同時，疊加顯示數(shù)字場景的內(nèi)容并基于實際位置來顯示虛擬的分析結(jié)果[2]。因此，在變電站數(shù)字場景的建立過程中需構(gòu)建一種預(yù)處理場景分割策略，并且在實時渲染過程利用該策略對場景數(shù)據(jù)進行動態(tài)調(diào)度，將海量數(shù)據(jù)構(gòu)成的數(shù)字場景高效地疊加顯示在性能較低的實時圖形平臺上(例如AR 頭盔顯示屏幕)具有重要意義。

傳統(tǒng)的場景分割方法，例如二叉樹(binary space partitioning，BSP)算法、四叉樹(quadtree)算法和八叉樹(octree)算法，可以將任意大小的原始數(shù)據(jù)劃分成基于空間坐標的樹狀場景結(jié)構(gòu)，并且根據(jù)實時渲染的要求動態(tài)地改變樹中節(jié)點加載和卸載的狀態(tài)，從而調(diào)度當前數(shù)字內(nèi)容的顯示區(qū)域和細節(jié)[3]。但是傳統(tǒng)算法的構(gòu)建時間長，最終的生成結(jié)果數(shù)據(jù)量大，因此調(diào)度過程中的性能損失也大。在帶有獨立顯卡支持的桌面PC 上，該問題通常可以被忽略；但在低存儲量和低運算能力的AR 眼鏡這類硬件設(shè)備上，其問題就變得很突出。

本文在傳統(tǒng)八叉樹場景分割算法的基礎(chǔ)上，提出了一種改進的增量八叉樹(incremental octree)算法，其樹狀節(jié)點更少，遍歷檢索的速度更快，并且非常適用于數(shù)字孿生掃描生成點云場景的渲染。

1 三維場景點云的掃描重建與分割算法

1.1 掃描重建的硬件設(shè)備與重建流程

三維場景的掃描重建過程通常需要用到以下3 種類型的硬件設(shè)備。

1.1.1 激光雷達

通過電機帶動激光線束快速旋轉(zhuǎn)，接觸到物體表面后產(chǎn)生反射，計算激光線束的發(fā)射時間和反射線束的接收時間的差值，即可計算出每條線束到達物體的途經(jīng)距離，進而得到激光在場景中掃描的實時距離列表，其示意圖如圖1 所示。

圖1 多線雷達VLP-16 掃描的單幀結(jié)果

將每幀的激光掃描數(shù)據(jù)拼接在一起，即可得到三維掃描數(shù)字化的點云結(jié)果數(shù)據(jù)。為了得到足夠豐富的場景細節(jié)，一般選用多線雷達(例如Velodyne VLP-16)，或者多臺單線雷達(例如HOKUYO UTM-30LX)來完成掃描[4-6]。

1.1.2 高精度慣導(dǎo)定位設(shè)備

由全球?qū)Ш叫l(wèi)星系統(tǒng)定位技術(shù)(global navigation satellite system，GNSS)和慣性測量單元(inertial measurement unit，IMU)六軸傳感器共同構(gòu)成的慣性導(dǎo)航定位設(shè)備，可以實時輸出設(shè)備位置和姿態(tài)數(shù)據(jù)。將慣導(dǎo)定位設(shè)備與激光雷達固定在一起，即可得到每一幀激光數(shù)據(jù)的實時位置和姿態(tài)信息。當已知每一條激光線束檢測的物體距離為Di、自身的旋轉(zhuǎn)角度為Ai、高度為Hi，以及通過慣導(dǎo)定位得到的激光器中心坐標位置矩陣P0和姿態(tài)矩陣O0，即可得到該激光線束的世界坐標矩陣Pi為

由此可以實現(xiàn)激光掃描數(shù)據(jù)的自動拼接，進而直接得到完整的場景點云數(shù)據(jù)。設(shè)備的對齊和拼接精度越高，得到的掃描重建結(jié)果也就越理想。因此，這一過程中也可以結(jié)合多線雷達采集的實時數(shù)據(jù)，通過并發(fā)建圖與定位(simultaneous localization and mapping，SLAM)算法、IMU 和GNSS系統(tǒng)結(jié)合計算得到更為精確的定位結(jié)果[7-8]。

1.1.3 全景相機

可以用2 個魚眼鏡頭構(gòu)成全景畫面，或者用多個普通攝像頭同步拍攝和拼接得到全景畫面。

將全景相機、激光雷達和慣導(dǎo)定位設(shè)備固定在一起，可通過標定得到全景圖片在三維空間中的位置和姿態(tài)信息。在點云掃描重建過程結(jié)束之后，通過后處理的方式將每張全景圖片重新置入到拼接完成的點云場景當中，并計算每個點投影到全景圖上的顏色，即可完成點云數(shù)據(jù)的著色過程[9]。著色完成后的點云場景如圖2 所示。

圖2 典型變電站三維重建后的點云場景

1.2 基于增量八叉樹算法的場景預(yù)分割

完成數(shù)字場景點云重建和著色過程之后，通常得到的結(jié)果數(shù)據(jù)十分巨大(數(shù)千萬點，甚至數(shù)百億點)，且因為點云本身并不具備幾何拓撲信息，因此難以直接對原始數(shù)據(jù)進行簡化，或者在簡化過程中丟失大量有價值的信息。

為便于對數(shù)字化場景進行檢查和瀏覽，并能在AR 眼鏡設(shè)備中對完整場景進行疊加顯示和數(shù)據(jù)分析，本文提出了一種高效的點云場景調(diào)度算法。該算法主要包括點云場景預(yù)分割算法和點云場景分割后動態(tài)調(diào)度顯示算法，可以流式處理數(shù)百億點的原始數(shù)據(jù)，將它轉(zhuǎn)換為金字塔結(jié)構(gòu)并實時渲染輸出到屏幕上，整個過程幾乎不會產(chǎn)生冗余的中間數(shù)據(jù)。這一方法是目前傳統(tǒng)的分割方案所不具備的。

點云場景預(yù)分割是將三維掃描重建得到的原始數(shù)據(jù)經(jīng)過空間索引(spatial indexing)和入庫操作，無損地轉(zhuǎn)換成一種可以流式讀取和顯示的數(shù)據(jù)管理格式。在格式轉(zhuǎn)換過程中采用一種增量八叉樹的算法，其具體實現(xiàn)過程如下。

1)計算整個場景的包圍立方體B0，并作為系統(tǒng)的根節(jié)點，將場景點云數(shù)量抽稀(thinning)簡化到低于某個閾值K，并保存到一個新的點云集合P′；原始點云P需減去P′后傳入下一級分割過程；

2)將B0在空間中沿著X、Y和Z這3 個軸向各進行一次切分，將得到8 個新的子節(jié)點；每個子節(jié)點都可表示為B1-x-y-z的形式，其中x、y和z的取值范圍均為0 或1，即根節(jié)點沿著某個方向一分為二后，其中一個子節(jié)點的索引；對于每個B1-x-y-z子節(jié)點，首先獲取對應(yīng)包圍體范圍內(nèi)的原始點云P1-x-y-z，將它抽稀到低于閾值K并保存為傳遞給下一級使用；

3)以此類推，再次對每個B1-?節(jié)點進行切分，可以得到第三級的B2-x′-y′-z′子節(jié)點以及對應(yīng)的抽稀點集合其中x′、y′和z′的取值范圍均為[0，3]區(qū)間內(nèi)的整數(shù)，具體的分割過程和子節(jié)點間的結(jié)構(gòu)關(guān)系圖如圖3 所示。

圖3 增量八叉樹的基本數(shù)據(jù)結(jié)構(gòu)

4)對于第n級的某個子節(jié)點Bn-x-y-z， 可以得出x、y和z的取值范圍以及包圍立方體的實際值為

式中x,y,z的取值均為[2n, 2n+1]。

5)每一級子節(jié)點的分割過程，視該子節(jié)點中傳入的原始點云Pn而定，如果剩余點少于閾值K，那么該子節(jié)點不再被分割，即=Pn；否則，抽稀原始點為新的集合 ρ′

n，并繼續(xù)執(zhí)行下一級分割，傳入下一級的點云集合為Pn-；

6)在分割過程中，記錄所有的Bn-的映射關(guān)系，其可以保存為零散文件的形式，以便于通過網(wǎng)絡(luò)傳輸，也可以保存到NOSQL 數(shù)據(jù)庫中，便于統(tǒng)一管理、修改和快速復(fù)制。

通過以上的場景分割和空間索引得到的樹結(jié)構(gòu)，與經(jīng)典八叉樹結(jié)構(gòu)沒有明顯的差異，因此可以直接使用經(jīng)典八叉樹的插入、查詢和刪除等操作方法。但使用經(jīng)典八叉樹進行三維點云場景的管理時，所有的實際三維點數(shù)據(jù)均保存在最末端的子節(jié)點Bn中，從B0到Bn-1的所有中間節(jié)點中，或者不保存任何數(shù)據(jù)，或者保存自身子節(jié)點中所有點云數(shù)據(jù)的抽稀結(jié)果。前一種八叉樹結(jié)構(gòu)是不均衡的，有大量的空節(jié)點存在導(dǎo)致資源浪費；后一種八叉樹會產(chǎn)生許多新的數(shù)據(jù)，比原始數(shù)據(jù)量增大了數(shù)倍，造成了存儲空間浪費，增加了對后續(xù)點云數(shù)據(jù)的分析處理難度。

為解決這些問題，本文構(gòu)建了一種增量八叉樹算法數(shù)據(jù)結(jié)構(gòu)，在實時運行和瀏覽時，設(shè)計了一種增量式的動態(tài)調(diào)度流程。

2 場景點云在AR 眼鏡環(huán)境中調(diào)度顯示

2.1 基于視場的場景動態(tài)調(diào)度算法實現(xiàn)

目前，常見的AR 眼鏡(例如Hololens)采用了微型投影方式將虛擬場景畫面投射到鏡片上，與人實際視野疊加形成增強現(xiàn)實的顯示效果。當人們戴上AR 眼鏡觀察一個已經(jīng)數(shù)字化的場景(例如變電站)時，如果期望物理場景和數(shù)字場景能夠完全貼合在一起，需要預(yù)先知道一些參數(shù):人所在位置的姿態(tài)矩陣M0，可以通過慣導(dǎo)定位系統(tǒng)實時獲?。晃⑿屯队皺C的內(nèi)參矩陣Mi(記錄鏡頭畸變參數(shù))、透視投影矩陣Mp(通過投影機視場角設(shè)置)，可以通過AR 眼鏡的標定流程獲得；窗口變換矩陣Mw，根據(jù)當前顯示分辨率計算得到。因此，將點云場景投影到鏡片上并與真實物理世界疊加時，每個點P到屏幕坐標P′的變換公式為

對于增量八叉樹的結(jié)構(gòu)，首先判斷某一級節(jié)點Bn投影到鏡片之后的顯示大小，該方法可獲取Bn的中心點PBn以及一個邊界點PEn并將它們轉(zhuǎn)換到屏幕坐標。如果PBn和PEn均位于屏幕范圍之外，或者兩者的距離值小于某個指定的閾值L，則當前節(jié)點和所有子節(jié)點均被剔除出渲染隊列；否則，顯示當前節(jié)點的點云內(nèi)容，并繼續(xù)遍歷下一級子節(jié)點，判斷是否可以顯示。

邊界點PEn的計算方法可分為多種，一種較為簡單的方法是:首先從M0計算得到佩戴AR 眼鏡的人頭頂方向V0，然后取Bn的外界包圍球的半徑Rn，于是有

上述計算顯示大小和動態(tài)裁減八叉樹算法的計算速度快，適合在AR 眼鏡這種低算力的環(huán)境中使用。整個八叉樹裁減過程幾乎對實時渲染的效率沒有影響，并且裁減結(jié)束后每幀剩余的可渲染數(shù)據(jù)量可控；點云場景的密度分布符合人眼觀察的自然規(guī)律，可以直接用于海量數(shù)字化成果的展示應(yīng)用。

2.2 基于AR 眼鏡視場的動態(tài)加載與卸載流程

傳統(tǒng)的場景調(diào)度方案往往是針對游戲場景設(shè)計的，多個不同分辨率的場景地塊被線性地輸入到隊列中，依次完成加載和顯示操作。而本文的調(diào)度算法是通過動態(tài)遍歷八叉樹的方式來快速完成場景的調(diào)度，并且自動優(yōu)先選取更靠近用戶視野中心的區(qū)塊進行加載和顯示，從而更貼近實際的使用體驗。

將經(jīng)過增量八叉樹預(yù)處理的點云數(shù)據(jù)復(fù)制到AR 眼鏡中(或者通過網(wǎng)絡(luò)服務(wù)器進行流式調(diào)度)，并且可以通過慣導(dǎo)定位或其他定位方案來精確計算AR 眼鏡在空間中的位置和姿態(tài)，即可精確地實現(xiàn)數(shù)字點云場景實時渲染，并且與眼睛中所見的物理場景實現(xiàn)準確地疊加顯示，在此基礎(chǔ)上實現(xiàn)虛實結(jié)合的場景導(dǎo)航或數(shù)據(jù)分析和計算工作。

因為AR 眼鏡自身的CPU/GPU 算力和內(nèi)存空間均非常有限，所以無法一次性將所有點云數(shù)據(jù)加載到內(nèi)存中渲染。因此，采取動態(tài)調(diào)度的方法，即每幀計算和加載當前視野可見的子節(jié)點數(shù)據(jù)，并卸載已經(jīng)不在當前視野內(nèi)的子節(jié)點；同時，還需要設(shè)置一個總體加載閾值，例如1 000 萬點。如果當前已經(jīng)加載的點數(shù)據(jù)超過了該閾值，則自動屏蔽所有其他的子節(jié)點數(shù)據(jù)，不再載入新的數(shù)據(jù)。通過這些參數(shù)的設(shè)置，即可實現(xiàn)海量數(shù)字點云數(shù)據(jù)在AR 眼鏡中的動態(tài)調(diào)度顯示，其具體執(zhí)行過程為:

1)開始當前幀的渲染；

2)根據(jù)當前視角，遍歷增量八叉樹數(shù)據(jù)，判斷BPn和BEn的數(shù)值，得到加載列表An和卸載列表Rn；

3)如果BPn和BEn均在視野之外，將當前子節(jié)點Bn加入到Rn；

4)如果BPn和BEn的距離小于閾值L，將當前子節(jié)點Bn加入到Rn；

5)如果都不滿足，則當前子節(jié)點Bn加入到An，繼續(xù)遍歷Bn的子節(jié)點；

6)對于An中的每一個元素Ai:如果Ai已經(jīng)被加載，則略過當前元素，否則加載Ai中的數(shù)據(jù)請求，渲染對應(yīng)點云數(shù)據(jù)；

7)對于Rn中的每一個元素Ri:如果Ri沒有被加載，則略過當前元素，否則卸載Ri中的數(shù)據(jù)，不再渲染對應(yīng)點云數(shù)據(jù)；

8)繼續(xù)遍歷下一級子節(jié)點，自動補充到Rn中；

9)返回步驟1)，繼續(xù)執(zhí)行下一幀的渲染。

3 實驗測試與結(jié)果分析

本文使用了Unity 引擎作為主要的算法實現(xiàn)和測試平臺，并使用C#語言編寫了動態(tài)調(diào)度和實時渲染程序。場景掃描重建的硬件設(shè)備包括1 臺VLP-16 多線雷達(負責(zé)實時位置和姿態(tài)計算)、2 臺HOKUYO 單線雷達、IMU 慣性傳感器、全景相機和運算用的PC 機，如圖4 所示。

圖4 掃描重建測試所用的硬件設(shè)備

本文通過C++和ROS 系統(tǒng)來完成場景掃描重建和增量八叉樹預(yù)處理過程，測試場景1 是一個辦公室的室內(nèi)場景，其掃描得到的原始數(shù)據(jù)點約為8 000 萬，如圖5 所示。

圖5 辦公室室內(nèi)環(huán)境三維重建后的點云場景

測試場景2 是運檢系統(tǒng)功能驗證所用的變電站場景，占地大約600 m2，其掃描得到的原始數(shù)據(jù)點約為15 億，如圖2 所示。2 個測試場景均采用Laz 壓縮格式來保存數(shù)據(jù)。它們的原始數(shù)據(jù)量經(jīng)過空間索引后的數(shù)據(jù)量和構(gòu)建空間索引所用的時間如表1 所示。

表1 場景空間索引所需的時間對比

從表1 中可以看出，采用增量八叉樹方法構(gòu)建的場景空間索引結(jié)構(gòu)，其在數(shù)據(jù)量上比原始場景的數(shù)據(jù)增加幅度不超過20%(增加的數(shù)據(jù)量主要來自大量散碎的子節(jié)點文件存儲時產(chǎn)生的磁盤碎片)。構(gòu)建過程中沒有拋棄或者新增任何點，因此可以直接替代原始場景數(shù)據(jù)用于分析等用途，或者無損轉(zhuǎn)換為原始數(shù)據(jù)的版本。而本算法的主要缺點在于數(shù)據(jù)預(yù)處理的時間較長，這主要是因為現(xiàn)有點云抽樣稀疏化算法所限[10]。整個構(gòu)建過程需要遍歷所有的原始數(shù)據(jù)，因此消耗了較多的時間。

測試場景1 的原始數(shù)據(jù)和增量八叉樹場景數(shù)據(jù)，分別使用帶集成顯卡(Intel HD)的PC 機、帶獨立顯卡GTX1070 的PC 機和Hololens 眼鏡，每隔1 min 測量一次當前運行的幀速率，對比結(jié)果如圖6 所示。

圖6 場景1 實時調(diào)度和渲染的效率對比

從圖6 中可以看出，當不進行優(yōu)化時，直接渲染原始點云，在普通集成顯卡PC 或者Hololens 端的渲染速率均低于10 f/s，即低于人眼可以感受到動畫效果的最低幀速率，此時已經(jīng)嚴重影響了場景瀏覽的效果，操作員無法繼續(xù)執(zhí)行其他工作；使用獨立顯卡渲染場景時幀速率穩(wěn)定在30 f/s 左右，可以滿足使用要求，但是對系統(tǒng)渲染資源的消耗較為嚴重。使用本文所述的增量八叉樹算法進行調(diào)度后，Hololens 平臺的渲染速度已經(jīng)可以達到32 f/s 左右的水準，滿足使用需要；而采用臺式PC 進行渲染時，渲染速度可以達到60 f/s 甚至更高，達到了獨立顯卡渲染未優(yōu)化點云速度的2 倍，完全滿足場景顯示和瀏覽的要求，并且大幅度節(jié)省了系統(tǒng)的渲染資源。

測試場景2 在不經(jīng)過優(yōu)化以及經(jīng)過了增量八叉樹優(yōu)化之后的渲染效果對比如圖7 所示，每隔1 min 測量一次當前運行的幀速率。

圖7 場景2 實時調(diào)度和渲染的效率對比

從圖7 中可以看出，如果直接渲染未優(yōu)化的原始數(shù)據(jù)，無論在PC 端還是在Hololens 眼鏡中都無法正常瀏覽測試場景2(變電站)的數(shù)據(jù)，這是因為數(shù)據(jù)量巨大，使用集成顯卡的PC 和Hololens AR 眼鏡端已經(jīng)無法承載實時顯示的要求，導(dǎo)致測試程序長時間未響應(yīng)就直接退出；獨立顯卡系統(tǒng)雖然可以顯示場景，但是幀速率接近于0，無法進行任何進一步的操作。而經(jīng)過本文所述方法進行動態(tài)調(diào)度之后，該測試場景在包括AR 眼鏡的多種工作平臺上均可以正常運行，其中基于獨立顯卡的PC 端的渲染效率已經(jīng)完全滿足人眼和VR/AR環(huán)境下觀看的需求，達到了80 f/s；而集成顯卡和Hololens 端的渲染效率雖然稍差，但是也超過了25 f/s，在操作者看來是流暢的，因此可以滿足變電站運檢系統(tǒng)的應(yīng)用需求。

對比測試場景1 和測試場景2，采用增量八叉樹算法進行調(diào)度的結(jié)果，在渲染效率上均可以滿足要求；并且隨著場景數(shù)據(jù)量的增加，渲染效率并沒有明顯的下降趨勢，這也進一步驗證了本算法的可靠性和應(yīng)用價值。

4 結(jié)論

1)本文提出了一種改進的空間索引算法，即增量八叉樹算法。它可用于三維場景掃描重建后得到的海量點云數(shù)據(jù)的存儲和顯示，構(gòu)建結(jié)果的數(shù)據(jù)量幾乎沒有增加，并且可以與原始數(shù)據(jù)進行無損轉(zhuǎn)換。

2)利用空間索引的結(jié)果數(shù)據(jù)，本文還給出了一種基于視場的場景動態(tài)調(diào)度和渲染虛擬場景的方法，可以將數(shù)字化的虛擬場景與實際物理場景無縫疊加，并在AR 眼鏡中進行顯示，滿足了各種行業(yè)數(shù)據(jù)監(jiān)測和數(shù)據(jù)分析的需求。

目前，本文所述的方法還存在一定的不足之處，如場景構(gòu)建所需時間過長、數(shù)據(jù)更新效率較低，無法選擇更新指定區(qū)域的數(shù)據(jù)等。這與本文目前所采取的點云數(shù)據(jù)采樣稀疏化的方式直接相關(guān)，在后續(xù)研究工作中可以引入一些更加高效的手段和方法，并通過并行計算的方法來同時處理多組子節(jié)點的生成過程，進一步提升運算效率和顯示效果。