面向傾斜攝影測量數(shù)據(jù)的out-of-core調(diào)度機制

曾紅梅，劉子桓

（四川大學計算機學院，成都610065）

0 引言

隨著城市信息化應用水平不斷提升，智慧城市建設應運而生[1]。以OpenSceneGraph（OSG）三維渲染引擎為代表的場景可視化系統(tǒng)，為實時顯示大規(guī)模城市場景提供了巨大支持[2]。然而，近幾年CPU和GPU發(fā)展迅速，內(nèi)存和硬盤的發(fā)展較為緩慢，數(shù)據(jù)訪問速度成為大規(guī)模場景可視化的主要瓶頸[3]。并且，大規(guī)模場景的LOD模型數(shù)據(jù)量通常十分龐大[4]，不能常駐內(nèi)存和顯存，可視化系統(tǒng)需要利用out-of-core技術完成場景LOD模型內(nèi)外存調(diào)度工作。因此，研究大規(guī)模場景LOD模型out-of-core調(diào)度機制，對推動智慧城市建設具有重要意義。

目前，主要通過基于幾何的建模和基于圖像的建模兩種方式獲取場景模型[5]。隨著無人機的飛速發(fā)展，通常利用無人機傾斜攝影的方法，高效地采集到真實度高的場景數(shù)據(jù)，然后通過幾何校正、影像匹配和空中三角測量技術處理測量得到的數(shù)據(jù)，最終基于圖像建模大規(guī)模場景[6]。其中傾斜攝影測量技術[7]是近年的一種新興測量技術，從垂直、傾斜等不同角度采集影像，以獲得地面物體更為完整準確的信息[8]。

同時對于大規(guī)模場景內(nèi)外存調(diào)度問題，主要通過改變場景數(shù)據(jù)內(nèi)外存組織形式和改進場景數(shù)據(jù)調(diào)度機制兩種方式解決。Da Silva等[9]將大型點云數(shù)據(jù)組織成動態(tài)八叉樹結構，設計了一種基于部分排序的Morton碼，提高外存數(shù)據(jù)查詢效率。Gong等[10]結合八叉樹和R樹葉子節(jié)點，提出3DORTree概念和一種基于深度遍歷與廣度遍歷的混合遍歷方法，對場景數(shù)據(jù)組成的3DORTree進行遍歷。Lindstorm等[11]解決地形可視化問題時，讓操作系統(tǒng)控制內(nèi)外存數(shù)據(jù)分頁工作，提出使用內(nèi)存映射技術加快內(nèi)外存數(shù)據(jù)調(diào)度效率。高宇等[12]利用最近最少使用策略（least recently used，LRU）釋放內(nèi)存，對可能用到的內(nèi)存數(shù)據(jù)進行加鎖處理，減少內(nèi)外存數(shù)據(jù)訪問次數(shù)。Xue等[13]提出一種高效的可交互CAD模型的GPU內(nèi)外存調(diào)度渲染框架，將LOD模型壓縮成高度緊湊的格式，最小化存儲成本。Jia等[14]針對大規(guī)模地址學模型場景可視化系統(tǒng)，在外存中根據(jù)模型的特點構造多分辨率簡化模型。Deibe等[15]開發(fā)了VILMA可視化軟件用于大規(guī)模LiDAR點云數(shù)據(jù)渲染，并且提出Hierarchically Layered Tiles和Tile Grid Partitioning Tree兩種數(shù)據(jù)組織方式減少內(nèi)外存占用率。OSG三維渲染引擎通過DatabasePager實現(xiàn)場景LOD模型動態(tài)out-of-core調(diào)度機制[16]。

OSG調(diào)度機制采用逐層次方式加載LOD模型，LOD節(jié)點樹在加載過程中才被建立，導致OSG無法跨層次加載LOD節(jié)點。即使預先保存LOD節(jié)點樹，然后載入使用，OSG卻不知道是否在一幀內(nèi)能完成目標LOD節(jié)點的加載。從而，OSG為了保證系統(tǒng)幀率，采用了最保守的逐層次加載方法。

但是，OSG逐層次加載的方式導致如下兩個問題：①加載數(shù)據(jù)量大。因為在加載到目標LOD節(jié)點之前，需要加載所有中間層次節(jié)點。②未考慮外存設備讀取能力。即使外存設備讀取能力強，OSG仍然在每幀中，將加載和渲染的LOD層次，向精細化方向只推進一層。從而導致限制時間內(nèi)，OSG無法加載到用戶期望的LOD層次，最終渲染效果達不到用戶的期望。

針對上述OSG調(diào)度機制的缺陷，本文提出跨越式的LOD模型out-of-core調(diào)度機制。為了使系統(tǒng)可以跨層次加載LOD節(jié)點，本文預計算生成場景LOD節(jié)點樹保存在外存。并且，在限制時間內(nèi)不能完全加載用戶期望的LOD節(jié)點時，為了找到替代效果最佳的LOD節(jié)點集合，本文利用多選擇背包問題[17]方法，求解得到最優(yōu)的節(jié)點集合。對比OSG，本文大量減少LOD節(jié)點數(shù)據(jù)量和數(shù)據(jù)總加載量，并且提升場景渲染效果。

1 算法實現(xiàn)

當不能完全加載用戶期望的節(jié)點時，為了找到替代效果最優(yōu)的節(jié)點集合，本文利用多選擇背包問題（multiple-choice knapsack problem，MCKP）[17]方法求取最優(yōu)解。由于每組物品數(shù)量巨大，導致求解多選擇背包問題時間復雜度極高。因此，本文提出物品模板的概念，通過物品模板實時生成少量物品，降低求解時間復雜度。

1.1 求解最優(yōu)節(jié)點集合

將如何找到替代效果最優(yōu)的節(jié)點集合的問題抽象為多選擇背包問題，再利用動態(tài)規(guī)劃算法求解多選擇背包問題[18]。

首先明確合法調(diào)度節(jié)點集合和期望節(jié)點集合的概念，當合法調(diào)度節(jié)點集合L包含某個節(jié)點Nnode時，則此節(jié)點的所有兄弟節(jié)點Nbrother∈L，所有子孫節(jié)點Nchild?L。將場景被化分為n個塊（Tile），根據(jù)當前視點信息進行可見性計算和LOD計算后，由各個Tile中符合計算結果的LOD節(jié)點組合成的集合Hi，所組成的集合H={H1,H2,H3,…,Hn}成為期望節(jié)點集合。

已知外存設備讀取速度，在限制加載時間內(nèi)，將每幀節(jié)點調(diào)度中允許的LOD節(jié)點最大加載量Wtotal視為背包重量。將每個Tile視為一組物品集合，假設第i個Tile的LOD節(jié)點樹有mi個LOD節(jié)點，有ki種合法調(diào)度節(jié)點集合，將每種合法調(diào)度節(jié)點集合視為一個物品，物品重量Wki為集合中所有節(jié)點加載量之和，物品收益Vki為結合種所有節(jié)點三角形面片數(shù)量之和。在每幀LOD節(jié)點調(diào)度中，當期望節(jié)點集合加載量WH>Wtotal，導致無法完全加載期望節(jié)點集合時。如公式（1），從每個可見Tile的ki種合法調(diào)度節(jié)點集合Li中選擇一種即從每組中選擇一個物品，使得加載所有已選擇物品產(chǎn)生的總收益Vactual最大。如公式（2）保證所有被選擇物品的總加載量Wactual≤Wtotal。如公式（3）表示最多只從每個可見Tile中選擇一種合法調(diào)度節(jié)點集合即物品，如公式（4）表示物品是否被選擇。

其中v表示當前可見Tile數(shù)量。Vij表示第i個可見Tile的第j種合法調(diào)度節(jié)點集合收益，同理Wij表示其加載量。yij=0表示這種合法調(diào)度節(jié)點集合不被選擇，yij=1表示被選擇。

如圖1，使用一個例子說明本文利用多選擇背包問題求解的思想。假設場景中經(jīng)過可見性計算后，只有Tile1和Tile2，并且期望節(jié)點集合分別為A={6 ,7,8,5}，B={6,7,4}。在一幀節(jié)點調(diào)度中，最大加載量Wtotal=15，期望節(jié)點集合加載量WH=32。因此，需要從每個可見Tile的所有合法調(diào)度節(jié)點集合中最多選擇一種加載，使得節(jié)點加載總量Wactual≤Wtotal的前提下，加載總收益Vactual最大。Tile1和Tile2分別有6種、4種合法調(diào)度節(jié)點集合，在24種組合中，Tile1選擇C={6,7,4,5}，Tile2選擇D={1}加載后產(chǎn)生最大收益為15。最終，此次節(jié)點調(diào)度應該選擇集合C和D進行加載顯示。

圖1加載LOD節(jié)點過程

但是，多選擇背包問題被證明是NPC問題[19]，求解時間復雜度與每組物品數(shù)量呈指數(shù)級相關。根據(jù)公式（5）計算根節(jié)點的組合代表一個Tile中的合法調(diào)度節(jié)點集合數(shù)量即物品數(shù)量。如表1所示，在四川大學場景中，計算得到部分Tile的合法調(diào)度節(jié)點集合數(shù)量。每個Tile的合法調(diào)度節(jié)點集合數(shù)量巨大，導致求解十分困難，無法保證系統(tǒng)的實時性。

其中c表示節(jié)點的子節(jié)點數(shù)量，kj表示子節(jié)點的組合數(shù)，k表示節(jié)點的組合數(shù)。葉子節(jié)點沒有子節(jié)點，則kleaf=1。

表1合法調(diào)度節(jié)點集合數(shù)量

因此，本文提出通過物品模板實時生成少量物品，降低時間復雜度。

1.2 生成物品模板集合

本文提出物品模板的概念。首先，通過離線處理方式，預計算生成少量合法調(diào)度節(jié)點集合作為物品模板集合。然后，在系統(tǒng)運行時，根據(jù)可見性計算與LOD計算生成期望節(jié)點集合，結合保存節(jié)點加載量、三角面數(shù)量和節(jié)點文件是否在內(nèi)存等信息的節(jié)點狀態(tài)表，實時地從各個物品模板中生成物品。最后，每個Tile中的物品數(shù)量大量減少，使得求解節(jié)點調(diào)度最優(yōu)化問題容易。本文提出BaseN節(jié)點集合作為物品模板，其定義如下：

定義BaseN節(jié)點集合：每個Tile的LOD節(jié)點樹中，以深度為N的全部節(jié)點以及深度小于N的所有葉子節(jié)點組成的集合，稱之為BaseN節(jié)點集合。

本文使用如圖2的一個例子說明BaseN節(jié)點集合。其中，基于深度4的Base4集合，由深度為4的節(jié)點{10,11,12,13,14,15,16}和小于深度的全部葉子節(jié)點{5,8}組合而成。

圖2 Tile中BaseN節(jié)點集合

本文將BaseN節(jié)點集合為物品模板的理由如下：

（1）是合法調(diào)度節(jié)點集合。當物品模板自身不是合法調(diào)度節(jié)點集合時，必須花費時間令其轉變?yōu)楹戏ǖ摹?/p>

（2）覆蓋LOD節(jié)點樹的各個層級。當物品模板未覆蓋到某些層級時，將會影響最終節(jié)點調(diào)度最優(yōu)化問題的求解。

（3）能快速生成物品。當面臨不符合LOD計算以及剔除計算結果的節(jié)點，可以快速將節(jié)點從BaseN節(jié)點集合中刪除或者替換，然后生成物品。

最后，預計算為場景中每個Tile生成BaseN節(jié)點集合保存在外存，當系統(tǒng)運行時，實時根據(jù)可見性計算和LOD計算生成物品。

1.3 生成物品

本文為場景中所有Tile生成BaseN節(jié)點集合時，默認所有Tile的所有節(jié)點可見。但是在系統(tǒng)運行時，用戶的視點位置變換，將會出現(xiàn)部分Tile不可見和部分節(jié)點不可見的情況。因此，在每次節(jié)點調(diào)度時，需要根據(jù)視點信息，將物品模板轉化為真正的物品，才能作為多選擇背包問題的輸入。本文算法結合期望節(jié)點集合以及節(jié)點狀態(tài)表，從物品模板中生成物品，具體生成步驟如下：

（1）復制所有BaseN節(jié)點集合作為待處理的物品模板集合。

（2）進行可見性計算，刪除不可見Tile的物品模板集合，以及可見Tile物品模板中的不可見節(jié)點。

（3）根據(jù)期望節(jié)點集合，得到每個Tile對應期望節(jié)點集合中的最大節(jié)點深度Ni。刪除Tile中最大節(jié)點深度大于Ni的物品模板。

（4）將物品模板中，不符合LOD計算結果的節(jié)點，替換為符合LOD計算的祖先節(jié)點。并且根據(jù)節(jié)點狀態(tài)表，標記物品模板中已經(jīng)存在于內(nèi)存中的節(jié)點，表示該節(jié)點的加載量為0。最終每個物品模板中，剩余的節(jié)點組合成物品，即每個Tile中實際可選擇的合法調(diào)度節(jié)點集合。

最后，將生成的物品作為多選擇背包問題的輸入，求解得到替代效果最佳的節(jié)點集合，作為系統(tǒng)此次調(diào)度的實際節(jié)點集合。即每個可見Tile中僅有少量的物品，從每個Tile中最多選擇一個物品，組成的物品集合加載量不超過限制加載量，并且使得系統(tǒng)渲染效果最好。

2 實驗結果

2.1 實驗環(huán)境

本文實驗環(huán)境如表2所示。

表2實驗環(huán)境

通過精靈Phantom 4 RTK型無人機在成都市青羊宮和四川大學周邊進行傾斜攝影采集到的兩套數(shù)據(jù)，詳細信息如表3所示。

表3無人機采集數(shù)據(jù)

使用Bentley System公司的ContextCapture軟件[20]對采集到的數(shù)據(jù)處理，自動建模三維場景。然后，僅保留模型文件OpenSceneGraph Binary（OSGB）中關于LOD節(jié)點調(diào)度的相關信息。最終，生成本文用于場景LOD模型調(diào)度機制研究的數(shù)據(jù)格式，包含bin、bint、lodtree這3種格式文件。二進制幾何數(shù)據(jù)文件（.bin）保存LOD節(jié)點的幾何數(shù)據(jù)，二進制紋理數(shù)據(jù)文件（.bint）保存LOD節(jié)點的紋理數(shù)據(jù)，LOD節(jié)點樹文件（.lodtree）保存多個LOD節(jié)點的信息以及節(jié)點間的關系。調(diào)度文件相關信息如表4所示。

表4調(diào)度文件相關信息

2.2 數(shù)據(jù)加載量對比實驗

本實驗對比本文算法和OSG逐層次調(diào)度機制的LOD節(jié)點數(shù)量與數(shù)據(jù)總加載量，證明本文算法在每次調(diào)度時，能夠大量減少需要加載的LOD節(jié)點數(shù)量和數(shù)據(jù)總加載量。

實驗中記錄了在同一場景的同一視點位置處，調(diào)度相同的期望LOD節(jié)點集合時，OSG逐層次調(diào)度機制和本文算法加載的LOD節(jié)點數(shù)量與節(jié)點數(shù)據(jù)總加載量。分別在成都市青羊宮和四川大學場景下進行實驗，實驗結果如表5和表6所示。

表5成都市青羊宮場景加載信息記錄

表6四川大學場景加載信息記錄

由表5和表6實驗結果可以看出，在相同場景和外存設備的條件下，本文算法的數(shù)據(jù)總加載量為OSG的50%左右，加載的LOD節(jié)點數(shù)量為OSG的30%左右。例如在成都市青羊宮場景，固態(tài)硬盤的條件下，OSG需要加載897個節(jié)點才能顯示用戶期望的效果，數(shù)據(jù)總加載量為140.273 MB，然而，本文算法只需要加載284個LOD節(jié)點，數(shù)據(jù)總加載量為僅為74.988 MB。

同時，OSG對于具有不同讀取能力的外存設備，調(diào)度的總節(jié)點數(shù)量不變。但是本文算法在不同的外存讀取能力下，調(diào)度的總節(jié)點數(shù)量不同。例如四川大學場景中，OSG在固態(tài)硬盤和機械硬盤上調(diào)度的節(jié)點數(shù)量都是380個，本文算法在固態(tài)硬盤上調(diào)度的節(jié)點數(shù)量為95個，在機械硬盤上調(diào)度的節(jié)點數(shù)量為114個，因為本文是在外存設備讀取范圍能力內(nèi)，求解多選擇背包問題得到的替代節(jié)點集合，所以不同的外存設備下，求解結果不同，最終總共需要加載的LOD節(jié)點數(shù)量也不同。

OSG為了保證系統(tǒng)幀率，將數(shù)據(jù)加載壓力分攤到了多個渲染循環(huán)中，逐層次的加載節(jié)點。從而必須加載所有中間層次節(jié)點，導致加載的LOD節(jié)點數(shù)量更多。相比之下，本文算法不需要加載中間層次節(jié)點，當加載能力足夠時，則直接加載期望的LOD節(jié)點，當加載能力不足時，在限制時間內(nèi)，求解多選擇背包問題，完成節(jié)點加載工作。

2.3 渲染效果對比實驗

本實驗在四川大學場景的同一視點位置下，對比本文算法與OSG逐層次調(diào)度機制加載顯示LOD節(jié)點的渲染效果。

本文算法使用加載的LOD節(jié)點集合擁有的三角形面片數(shù)量衡量渲染效果，在不同的限制時間條件下進行實驗，實驗結果如表7所示。

表7節(jié)點加載效果表

由表7可知，在不同限制時間條件下，本文算法最終渲染的LOD節(jié)點集合擁有的三角形面片數(shù)量是OSG的140%左右。在限制加載時間為500 ms時，圖3為OSG的渲染效果，圖4為本文算法渲染效果，圖5為用戶期望的節(jié)點渲染效果。對比圖3和圖4可以從看出本文算法的渲染效果比OSG更加清晰。分別對比圖3與圖5、圖4與圖5，可以看出本文算法效果更加接近用戶期望顯示的效果。

圖3 OSG渲染效果

圖4本文算法渲染效果

圖5期望渲染效果

實驗結果表明，OSG渲染效果不如本文算法。分別求取本文渲染效果圖4與期望渲染效果圖5和OSG渲染效果圖4與期望渲染效果圖5的結構相似性SSIM、峰值信噪比PSNR和均方誤差MSE，結果如表8所示，可知本文方法的渲染效果更好，結構相似度更高，均方誤差更小，峰值信噪比更高。由于不能完全加載到用戶期望的LOD節(jié)點，OSG最終加載顯示某個中間層次的LOD節(jié)點集合。而本文算法求解多選擇背包問題，最終加載顯示的渲染效果最優(yōu)的中間層次LOD節(jié)點集合。

表8渲染效果比較

3 結語

本文使用多選擇背包問題求解出替代效果最優(yōu)的LOD節(jié)點集合進行加載顯示，并且提出物品模板與物品的概念降低求解時間復雜度，最終實現(xiàn)了面向傾斜攝影測量數(shù)據(jù)的跨越式LOD模型out-of-core調(diào)度機制。實驗結果表明，對比OSG，本文算法在每幀調(diào)度中，大量減少了需要加載的節(jié)點數(shù)據(jù)總加載量和節(jié)點數(shù)量，并且渲染效果比OSG更精細。本文算法對于大規(guī)模城市場景的可視化具有一定的價值和參考。不足的是本文假設讀取不同數(shù)量、不同大小的文件耗時相同，視外存設備讀取速度為常數(shù)，導致對調(diào)度最優(yōu)化問題的求解有一定影響，后續(xù)考慮利用回歸森林方法預測出外存設備的讀取速度。并且，本文求解調(diào)度最優(yōu)化問題時，為了降低求解時間復雜度，進而求取次優(yōu)解作為最終結果。因此，找到降低時間復雜度的，且渲染效果比本文算法更好的方法是本文未來繼續(xù)的研究方向。