應用于增強現實變電運檢三維場景重建的增量八叉樹算法

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

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

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

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

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

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

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

1.1 掃描重建的硬件設備與重建流程

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

1.1.1 激光雷達

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

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

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

1.1.2 高精度慣導定位設備

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

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

1.1.3 全景相機

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

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

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

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

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

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

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

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

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

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

圖3 增量八叉樹的基本數據結構

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

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

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

n，并繼續執行下一級分割，傳入下一級的點云集合為Pn-；

6)在分割過程中，記錄所有的Bn-的映射關系，其可以保存為零散文件的形式，以便于通過網絡傳輸，也可以保存到NOSQL 數據庫中，便于統一管理、修改和快速復制。

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

為解決這些問題，本文構建了一種增量八叉樹算法數據結構，在實時運行和瀏覽時，設計了一種增量式的動態調度流程。

2 場景點云在AR 眼鏡環境中調度顯示

2.1 基于視場的場景動態調度算法實現

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

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

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

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

2.2 基于AR 眼鏡視場的動態加載與卸載流程

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

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

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

1)開始當前幀的渲染；

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

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

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

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

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

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

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

9)返回步驟1)，繼續執行下一幀的渲染。

3 實驗測試與結果分析

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

圖4 掃描重建測試所用的硬件設備

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

圖5 辦公室室內環境三維重建后的點云場景

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

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

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

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

圖6 場景1 實時調度和渲染的效率對比

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

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

圖7 場景2 實時調度和渲染的效率對比

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

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

4 結論

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

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

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