波函數坍縮算法在數字城市仿真中的應用研究

廖浩宏，韋宇煒，羅立宏

(廣東工業大學，廣東 廣州 510090)

1 引言

所謂的數字城市[1-3]，又稱虛擬城市。是旨在借助計算機技術、多媒體三維技術和大數據存儲等技術的基礎上，綜合應用3S技術(GPS全球定位系統、GIS地理信息系統和RS遙感)，將城市的自然資源、社會資源、公共基礎設施等相關城市資源整合到系統平臺中，并使其可視化的過程[4]。在“十五”期間，國家配合地方與企業共投入45億人民幣，在全國建立了125個數字城市并投入使用，其余145個數字城市建設正在穩步推進。數字城市在城市規劃建設、資源管理、公共服務、人口資源調配等諸多領域起到了不可或缺的作用。

20世紀90年代以后，隨著計算機的運行速度、算力、存儲等方面的大幅提升，數字城市、虛擬漫游、大場景的數據處理和快速繪制優化等技術進入了快速發展階段。Peter. Lindstrom、Hugues Hoppe等人提出了通過LOD(Level Of Detail)技術[5]構建不同細節層次的模型來減輕計算機對高精度模型數據的存儲能力和渲染壓力；Yazdizadeh A等人提出使用Texture Mipmap(紋理映射)技術對場景中的紋理數據進行處理[6]，在不影響用戶漫游體驗的前提下極大程度地壓縮紋理貼圖的分辨率，進而減輕計算機的渲染負荷；在國內劉波[7]等人通過分層來構造單體建筑的幾何模型和紋理，并將分頁式場景剔除技術引入到城市場景的圖形渲染管線中，提高了計算機運行幀速率；在后續研究發展中，一些學者還通過改進LOD技術、結合二級四叉樹索引降低網格搜索時間、利用GPU頂點著色并結合CUDA編碼技術對DEM[8-10](digital elevation model)進行數據抽取來降低CUP的占用率，以此優化場景渲染效果。

隨著5G技術、物聯網等技術的問世，虛擬現實技術、數字化城市被再次推入人們視野之中。數據交換的速度和量化程度也正往高速、海量化的方向發展，虛擬現實所必備的硬件正逐步實現輕量化；而無人駕駛技術也在數字化城市、地理信息系統等技術加持下的取得階段性成果。目前人們已經可以依托大量的智能軟件和數據采集硬件如無人機航測等對現有的現實內容進行數字化、虛擬化快速生成。但是，軟件卻無法代替人腦進行創作。而現階段，大量的虛擬仿真項目和市場需求仍集中在虛構的城市場景內容上，海量虛擬數字城市場景的建模和搭建在開發時間成本上仍是一個較為麻煩的問題。因此，上述項目流程仍存在設計流程上的不足。例如在城市道路規劃的設計過程中仍需要城市規劃師等專業人員進行設計，若能將該算法應用到實現動態生成區域的場景規劃，這將使得建設成本和效率將進一步得到改善。

據《艾瑞2018年L4級自動駕駛技術及應用場景行業研究報告》中提到，由于深度學習只有通過大量的數據訓練才可以實現對相思目標和道路情況的識別和判斷，而由于城市道路交通情況過于復雜，在模擬器上訓練的場景有限，當前L4級自動駕駛系統還難以應付城市開放道路上的載客運輸作業，最終只能應用于封閉園區如港口集裝箱運輸、工業區運輸作業等[11]。

本文主要研究約束求解驅動圖像生成算法WFC(Wave Function Collapse， 波函數坍縮)，并將其應用到數字城市的場景設計和程序生成之中，以此解決上述中城市規劃與機器深度學習的虛擬環境設計提供一個新的設計制作思路。

2 波函數坍縮法則

在整個程序的運行中，波函數坍縮算法主要執行了四個關鍵性任務[12-14]：從輸入圖像中提取局部模式；將這些模式處理成一個索引，以加速約束檢查；通過增加局部熵值來增量地生成輸出圖像；最后，將整個生成的圖像進行輸出(以圖1作為案例樣本)。

通過上述樣本案例進行解析，并且給出以下偽代碼：

defn Run()：

PatternsFromSample()；

BuildPropagator()； ∥構建傳播算子

Loop until finished：

Observe()； ∥觀察

Propagate()； ∥傳播

OutputObservations()； ∥輸出觀測

2.1 構建傳播算子

引入一種“傳播算子”(或稱為模式)的概念，這個傳播算子是一種特殊的、配置唯一的平鋪板塊。在簡單的平鋪算法中，傳播算子被認為是線性的約束關系；在重疊的算法中，傳播算子可以通過觀察被原圖像所推斷出來，并通過設置一組從圖像中構建出來的子圖像放置到N*N的模式索引數組中，并且還應考慮其對稱性和旋轉不變性。

圖2 通過樣本生成3*4結構圖

如圖2所示，當N=2時，可以從樣本圖像中構建出12個唯一模式，由于紅色和白色像素在原圖像中沒有相鄰的情況，所以沒有該類組合模式。采樣的圖像是周期性的平鋪，這是可選的。在模式設計中，BuildPropagator()創建了一個索引數據結構，用來描述那些可以放置在彼此附近的方式。對于重疊的版本，索引包含提前計算好的答案，這個答案回答了當一個放置在另一個特性的x，y偏移量時，兩個模式之間是否匹配的問題。(當N=3時，有(2(N-1)+1)2=36 個偏移量需要考慮。)對于平鋪的版本，這個索引可以直接從設計器被指定的平鋪關系中創建出來。在任何一種情況下，它在模式之間創建了一種稀疏的關系。

在核心增量生成的過程中，決策變量(網格位置)被重復選擇然后進行被分配。在約束求解過程中，除了當前部分分配之外，求解器通常持續追蹤未分配變量的剩余域，它是一個被存儲在一個名為wave的表中，松散地引用了量子波函數。而表的條目，稱之為系數，是一個記錄算法是否仍然可以將給定的模式分配給給定的位置的布爾值。波函數中所有的系數被初始化成一個真值，這相當于說每一個決策變量都有一個未還原的初始域。分配和傳播都有助于縮小變量的域。

2.2 最小熵原理驅動解析

Observe()的目的是用最低的非零熵來識別網格上的位置。這里的熵所對應于波的解釋，這意味著在每個網格位置上找到模式的概率分布。熵最低的細胞是傳播后最緊或最小域的變量。在約束求解中，在約束求解中，選擇最約束變量或等效最小剩余值變量(MRV)的啟發式方法是最好的。在此設置模式的的生成概率為，則通過以下方法計算模式板塊的熵值

(0≤λ≤4∩λ≤N*)

選擇具有最低的非零熵(或最小的剩余值)的位置的策略期初是任意的。如果想在不回溯的情況下最大限度地優化發現整個任務，應該讓做的每一個選擇都最大限度地增加總任務的數量，這與目前的選擇時一致的。這就避免了排除(可能極為罕見的)合法的全部分配，假設這些轉讓是在其它全部轉讓之間分配的。如果剩余的總任務的數目近似為未分配的變量的域的大小的乘積(換句話說，假設其余的選擇時獨立的)，然后用最小域分配位置(最低熵/最小剩余價值)，在分配之后讓產品價值最大化。為了建立另一個松散的物理聯系(這一次與統計力學)，熵啟發式是最大熵原理的實現之一。

由于在所選的位置有多個有效模式——或者在上一個循環中已經將其設置為零熵——需要在這些模式中選擇其中一種。其中一個模式是選擇一個隨機樣本，加權方式是模式在輸入的圖像中出現的頻率，這實現了模式的出現在輸出中的分布與輸入中的分布相似。

2.3 變量坍縮約束

一旦觀察到一個位置(一個變量已經被分配)，它將被標記為需要在波中更新的位置(作為一個通過約束傳播開始更新變量域的地方)。像AC3，WFC傳播過程確保了如果在相關的變量域中存在一個有效值，這個變量只出現在變量域中，這就可以滿足這些變量上的約束可以被滿足。更新一個變量的域意味著需要潛在地更新所有相鄰變量。因此，傳播是通過一種算法進行的，從圖形的角度可以是作為flood填充方式。

每個觀測的最終結果至少確定了位置和盡可能地降低了周圍區域的熵。

圖3 觀測坍縮范圍逐漸擴大

一旦系統中沒有更多的熵(所有變量只有一個單例域)，可以輸出最終生成的圖像。此外，可以利用一個優勢，就是每一個單元都有一個潛在的狀態數組，并且在每個觀察和傳播周期之后輸出如圖3所示的一個局部完成的圖像，那么以此就能生成一張指定的完美的視覺標記圖。

2.4 LCV輸出觀測

defn OutputObservations(coefficient＿matrix)：

Foreach cell：

Set observed value to the average of the color value of this cell in the pattern for the remaining valid patterns；

Return the observed values as an output image；

上述偽代碼中可以看出，可以將WFC視為一種約束求解算法。它使用最小的剩余值(MRV)啟發式地選擇要決定的下一個變量，對于決策上，它使用了根據原始圖像中的分布選擇模式的啟發式方式。另一種可供選擇的啟發式就是眾所周知的最小約束值(LCV)選擇啟發式(LCV也可以由最大熵原理驅動)。然而，它很難預測這種啟發式選擇對內容生成的影響。

3 算法的改進系統架構設計

本文通過改進波函數坍縮算法，將其引入的虛擬城市場景的構架中。延續了Maxim Gumin算法中的思想，在Unity程序中將整個場景劃分成若干個 width * length * height的大小的盒子，稱之為“Slot”，用于將生成的道路板塊模型插入到該Slot中，進而拼接成完整的場景地圖[15]。

在第一步構建傳播算子環節中，通過解析構建的道路模型網格拓撲結構，生成模塊與模塊之間的指紋，用于對相鄰兩個道路模型之間是否可以匹配的依據，使其在后續的場景生成過程中可以生成符合邏輯的平鋪模式，并且將其提取成合法的模式相鄰的索引(即Gumin所說的傳播)以及填充算法的網絡拓撲結構。

1 { assign(X，Y，P)：pattern(P) } 1 ：-cell(X，Y)．

：-adj(X1，Y1，X2，Y2，DX，DY)，

assign(X1，Y1，P1)，

not 1 { assign(X2，Y2，P2)：legal(DX，DY，P1，P2) }．

接下來，在觀察和傳播兩個階段中，通過設置板塊生成的概率、通過的方向、封邊等要素結合解析出其個體熵值，再計算每一個Slot可能插入的模塊群中解析出綜合熵值，以此分配影響最低的Slot；系統一旦觀察到該分配的位置，它將被標記為中心點對周圍的Slot進行衍生分配，向外進行坍縮生成。一旦系統中沒有更多的熵，即可生成最終的場景地圖。

4 數據存儲和調度優化

受到計算機硬件設備的性能限制，對于大型場景的虛擬漫游仍然無法一次性渲染出來，即使渲染出來運行幀速率也是非常低，這就必須對程序中的海量模型數據進行分塊管理以及根據玩家的位置進行動態調度加載。程序對模塊數據的管理方式以及動態調度方法對場景的瀏覽效果非常重要，合理的模塊數據管理方式和動態調度方法不僅可以使得程序更好地查找和加載場景，而且可以在運行中保持優質的畫面效果。本文針對Unity引擎對建筑道路進行模塊化設計制作，并且將道路、高架橋拼接模型信息進行有機存儲，并根據玩家所處的視點位置對模型進行動態加載。

4.1 場景數據的分塊組織管理

合理的場景數據管理形式和高效的數據檢索方式[16]，能夠有效地在進行場景漫游的時候快速有效地生成區域模塊。

從場景體素化的角度出發對地圖的剪裁進行考慮，共制作了147個道路組件，包括街道路口，高架橋等模型，旨在搭建一個無限邊界且具有兩層高架橋的數字虛擬城市。每個組件與組件之間用相同的鍵值(即配對指紋)進行標記，在場景生成時即可生成符合邏輯的模塊。

世界場景的區域塊chunk及其子級和每個組件模塊module之間的關系如圖4所示。每個模塊有屬于它們的相關屬性和每個面對應的配對指紋信息；而世界地圖從依據chunk進行剪裁，往下到Room、Slot等小模塊進行細分。將整個世界場景劃分為若干個Slot，接著將所有的module模塊元素往作為中進行穿插，最后即可生成一個符合現實邏輯的虛擬城市。

圖4 數字城市場景地圖生成流

● Chunk是場景中最大的數據模塊，主要負責管理Slot插槽矩陣、通道、房間和模型渲染網格等信息；

● Slot插槽。將整個虛擬場景劃分為三維網格矩陣，每個單元稱之為Slot，在進行坍縮的時候將每個模型的信息坍縮確認之后則放入Slot之中；

● Module主要負責存儲模塊的預設信息(如：截面信息、配對指紋等)和鄰接模塊預設等；

● FaceDetails 模塊面的詳細信息；

4.2 場景數據的動態調度

當實現對整個地圖的自動化生成之后，開始著手對系統化的運行進行動態加載，以防止城市模型數據過多而導致的運行卡頓，提高虛擬漫游的瀏覽效果。在這里采用基于視點的動態加載策略方案[16]。

如圖5所示，將正式大數字城市的場景數據劃分成三個部分，視點關注區、預可見緩沖區和數據局緩沖區。其中視點關注區是3*3個由100為單位的形成的模塊矩陣，經過一些建筑物的遮擋關系原理玩家在虛擬漫游場景中的視線點幾乎在該區域之內；而外圍的16個預可見緩沖區則是對玩家進行下一步移動的時候的預處理區域：劃分場景的最中心100為移動界限，通過unity的Update事件函數來更新玩家在世界坐標的位置，程序通過開啟一個新的線程，每50毫秒對玩家的位置信息和中心邊界的位置關系進行判斷，當玩家超過當前的邊界時則會開始發生三者數據區域的數據交換和更新。

圖5 數據動態調度變化

建立預可見緩沖區數據的最大的優點就是為了保證關注區周圍的場景數據都已經被繪制出來，解決玩家視點方向隨機性所帶來的的可能會出現視野穿幫的問題，同時也優化了場景中可能因為單個模塊的加載時間太長而出現了卡頓的瀏覽問題，保證平滑過渡的漫游體驗。

5 實驗數據測試

本研究測試輸出的硬件環境如下：

圖6 在算法生成的數字場景中漫游

● 硬件環境

筆記本：華碩飛行堡壘7

處理器：Intel(R) Core(TM)i5-9300H 2.4GHz

內存： DDR4 2666MHz 8GB

顯卡：NVIDIA GeForce GTX 1650 獨立顯卡4GB

硬盤空間：512GB

本文基于Unity物理引擎平臺作為內容開發工具，結合波函數坍縮算法進行研究，并設計實現了汽車駕駛的第三人稱城市漫游系統[17]。通過實踐與數據測試，主要解決大型場景搭建耗費成本高，且在虛擬漫游平臺加載緩慢，幀率不穩定等問題。這里主要從以下兩方面來進行數據測試，驗證其算法的可行性與優越性。

5.1 不同方式制作大場景所需時間對比

上述表中在相同的模型貼圖制作流程的情況下，進行了算法生成的方式和傳統手動搭建的兩種方式中相關流程開發時間的比對，發現對于大型虛擬場景的制作開發尤其是無邊界數字城市場景而言，通過波函數坍縮算法生成的場景在開發時間成本上有著其本身優越的特性，并且這個優勢隨著場景的增大而不斷凸顯。

表1 傳統搭建流程與算法生成成本數據對比

5.2 不同量級場景下運行性能優化數據對比

在Unity的Profiler性能測試工具中對實現的系統進行數據性能測試[18]，并最終匯集成數據表格和統計圖。

表2 性能優化效果對比

圖7 不同量級場景下運行幀速率對比

上述表中通過使用相同的模型，用不同的方式去搭建虛擬場景，通過在運行過程中對幀速率、DrawCall、以及模型面片數等性能指標進行數據比對，發現在傳統的搭建方式中，虛擬漫游的運行性能與場景的大小成反比，當場景達到1500m*1500m的大小時，漫游的運行速率掉到了10幀以下，并出現了卡頓等現象；而通過算法生成的場景在越大的場景中甚至是無邊界場景中展現出了算法的優越性，穩定保持在30FPS左右。

6 結語

本文主要針對Unity物理引擎，使用波函數坍縮算法，對目前城市規劃設計領域傳統設計模式開發時間長、耗費精力大、成本投入高等問題以及針對于深度學習的無人駕駛所依托的海量的訓練場景面臨的場景搭建的等問題進行研究和實現。經過實驗和分析對比，得出以下結論：

1)通過研究波函數坍縮算法求解生成制作虛擬漫游系統，通過與普通人工搭建場景進行數據對比可以得出：該算法在對大型場景尤其是無邊界場景的制作時有著巨大的優勢；

2)結合動態調度算法，可實現對大規模分塊數據進行動態管理研究，可優化系統的運行性能。通過不同量級場景下未做優化處理的數字場景進行數據對比證明了該算法對大型場景搭建的便捷性和漫游的優越性的提高。