透過全域性TGV最小化進行核外表面重建
標題：Out-of-Core Surface Reconstruction via Global TGV Minimization
作者：Nikolai Poliarnyi（photoscan，Metashape作者之一）
機構：Agisoft LLC，聖彼得堡
翻譯：靳軍
稽核：zhuhu
這是泡泡圖靈智庫推送的第691篇文章，歡迎個人轉發朋友圈；其他機構或自媒體如需轉載，後臺留言申請授權
摘要
文中提出了一種利用核外變分方法，用於從一組對齊的深度圖中進行表面重建。重建演算法的輸入可以是深度圖或者陸地LIDAR掃描，或者是兩者的混合。文中的方法基於總廣義變分（TGV）最小化進行表面重建，因為其具有強大的基於可見性的噪聲過濾特性和GPU友好性。文章的主要貢獻是對這種數值演算法的核心外OpenCL加速適應，使得該演算法可以處理具有規模多樣性的任意尺度的現實世界場景。
主要貢獻
構建了一個快速、精細化表面重建的核外框架。從而減小了重建過程中的記憶體使用峰值。
採用自適應方法，能夠適應多種尺度的場景。
演算法流程
從距離場建立八叉樹。在文章中，對於每一個距離場，將樣本與其鄰接樣本之間的距離的二分之一作為每一個樣本的半徑
。對每一個樣本，建立深度為
的八叉樹立方體，深度
與樣本半徑
滿足如下關係：
所有立方體使用96-bit的3D Morton編碼法進行編碼，並且每個距離場單獨儲存。因此，立方體能夠透過核外k-way歸併排序歸併成一個單一的線性八叉樹。
八叉樹平衡。為了限制立方體的鄰接數量，我們需要對八叉樹進行平衡。依據Morton編碼的順序，我們只加載部分已編碼過的線性八叉樹，並且對這部分進行平衡，最終將平衡後的部分單獨儲存。之後對所有平衡過的部分進行核外k-way歸併排序。
建立經過編號處理的樹梢treetop，並且在每個樹頂葉子部分上分別進行原始對偶primal-dual迭代。考慮一個樹梢——一個有根的子樹，它包含葉子中最小數量的八叉樹立方體，限制每個葉子立方體包含少於
個後代，如圖所示。在文中的實驗中，我們設定
。由於核外的限制，我們無法將整個八叉樹載入到記憶體中對全域性樹梢進行估計。因此，我們對所有線性平衡後的八叉樹分塊建立獨立的樹梢，再將這些樹梢歸併成一個全域性樹梢。由於Morton編碼中的“Z”字形排序，我們只需要儲存每一個樹梢葉的兩個索引——線上性平衡八叉樹中的第一個和最後一個相關立方體的索引。
直方圖的計算。將距離場的投票存放在平衡八叉樹上的體素直方圖中。透過檢查每個距離場視錐體與樹梢葉子立方體的交集，實現對每片“葉子”的相關距離場的估計。之後逐一載入每個樹梢葉子的所有相關距離場，並將他們的投票新增到當前樹梢葉子的所有後代中，如演算法1所示。
泛函最小化。在平衡八叉樹的每一分塊上進行由粗到細coarse-to-fine的泛函最小化。我們迭代最小化全域性廣義變分
假設我們已經迭代最小化到了深度
，現在需要在深度
上使用核外方法進行原始對偶primal-dual迭代，並且確保不在八叉樹分塊之間產生“裂縫”。為了實現這一目的，我們將樹梢葉子的立方體載入到集合A中，將其鄰接的立方體載入到集合B中。在對A中的立方體進行數值計算的時候，我們確保B中的立方體的索引
與其父立方體的索引一致。也就是說，我們更新集合A中的索引，但是將B中的索引凍結。如圖所示：
在任何給定的時間中，我們只處理來自樹梢葉子的立方體及其鄰接的立方體。因此記憶體消耗是被所處理的立方體的數量所限制的。由於明確的邊界約束以及從一個級別到下一個級別的表面不會移動很遠，所以不會在樹梢葉子邊界旁邊的表面上產生任何錯位，並且變面只會變得更加細節。
marching cubes。基於marching cubes的等值表面提取。最後提取與指標
對應的多邊形等值面，對此，我們使用與之前相同的核外樹分塊法，對每個立方體執行Marching Cubes演算法。對於每個八叉樹立方體，我們提取不同符號的指標值之間的3D點，然後基於最小化總表面積的動態規劃來構建三角剖分。對於大型資料集來說，三角形面的數量會非常巨大。因此我們使用基於QSlim的降取樣，來跟蹤對每個八叉樹分塊的Marching Cubes。我們使用嚴格的邊界約束對其進行了修改，確保任何邊界邊緣都不被摺疊。透過這種方式，確保了相鄰的樹梢葉子之間的無縫表面
實驗結果
我們在搭載8核CPU和RTX 1080的平臺上對五個大型資料集進行了測試。結果表明，我們的演算法對資料集的重建細節豐富，清晰明瞭。並且，執行過程中的記憶體使用峰值在10GB到17GB之間。與已有的演算法相比，我們演算法的記憶體峰值大幅減小，執行速度更快。
總結
文中我們提出了一個可以從深度圖以及對陸雷達掃描中實現表面重建的核外方法。實驗結果表明，演算法並沒有增加執行時間，並且在GPU加速的幫助下我們的演算法相比我們所採用進行的測試的已有演算法快了不少。並且，我們的重建結果的精細度與in-core演算法GDMR是不相上下的。擁有樹梢索引的核外平衡八叉樹概念能夠推廣到使用其他方法的框架中，不僅僅侷限於我們所使用的全廣義變分最小化方法。我們的方法已經應用與商業軟體之中。