一種基于非平滑特征的簡化實景網格評價方法

劉盛恩 薛俊詩 易 輝

(航天工程大學研究生院 北京 101416)

0 引 言

傾斜攝影建模是機器視覺的重要應用之一，可以低成本地實現智慧城市三維架構的構建，并且相對于激光雷達可以較為容易地貼上紋理，使得建模的浸入感真實感強，但精度不足。一方面存在透視失真、遮擋[1]，另一方面機器視覺是通過根據像素分布和亮度、顏色等信息抽取目標的位置信息[2]，而且UDSM存在大量理論上的平整且紋理相似的表面如墻面、屋頂、道路，像素之間的信息分辨度低，容易造成誤差。真實情況中這些表面可以認為是完全平整的，所以理論上對這些位置的簡化三角面應當越少越好[3]。但是在建模得到的網格中，建筑的平整表面并非完全平整，所以這就帶來兩個問題：一是比較平整表面與原網格差異的大小來評價網格簡化算法不客觀；二是無法定量驗證平整表面網格少的情況下簡化其他細節的簡化精度，如文獻[3]就沒有定量驗證。

網格定量評價研究主要針對網格差異和網格平滑兩個要素，Metro簡化網格對照工具[4]至今是評價簡化算法誤差的主要量化標準，通過蒙特卡洛采樣將網格距離簡化為可以計算的點面距離。為了解決Metro工具忽視視覺真實感的問題，文獻[5]利用二次誤差矩陣(QEM)計算誤差，文獻[6]提出單個三角網的質量標準，文獻[7]進一步對頂點的平整度、平滑度、偏差度和形狀進行量化。很多研究常常將模型平滑度作為網格質量的標準，包括研究曲率矩陣的奇點[8]、網格結構失真測度(MSDM)[9]和高斯曲率[10]等，這些方法都基于模型的平滑特性。但是UDSM的曲率變化劇烈，導致一些三角邊對應的二面角變化很大，也就是突變成為了必然，這就是這里說的非平滑特征。利用UDSM這個重要特征，可將其分類為平整網格表面和細節網格表面。

盡管Metro不能體現算法保持原網格細節的能力，但Metro因其對模型和簡化算法沒有先驗要求，所以網格簡化研究一般采用Metro工具進行測量與原網格的差異。文獻[11-12]回避了與經典并且Metro測量結果較好的QSlim[13]算法進行比較。以斯坦福兔子作為案例進行研究時，原模型三角面片數量通常為70 k如文獻[11]，而在文獻[12]中頂點數量就達到了219 k，展示Metro測量結果時壓縮了實際簡化率。文獻[14]的室內網格與UDSM有類似特征，但在加強拓撲保真度的同時Metro測量結果仍然不如QSlilm。文獻[15]的UDSM簡化研究中只是對比在極高簡化率(>0.99)下的Metro測量結果，雖效果良好但片面性強，不符合多層次細節LOD的要求。上述幾種算法簡化后模型的視覺效果好于QSlim，但在Metro工具測量誤差時沒能客觀評估視覺效果。

另外有些算法的評估針對特定的算法或者同類算法。文獻[16]通過面積和離散曲率加權得到新的二次誤差矩陣(QEM)測度方法，但都是通過展示網格來表達簡化模型對原模型特征的保持。另外，有些研究利用自身算法的誤差測度來衡量簡化質量，文獻[17]引入平方體積誤差，文獻[15]引入與代理平面的距離誤差，這些都只限于簡化算法本身或者同一類的簡化算法，缺乏魯棒性。

提取平整表面網格的方法主要包括隨機抽樣一致性(RANSAC)算法[18]、霍夫變換[19]和特征閾值[20]，這些研究基于Lidar數據，而且都以模式識別為目的，文獻[21]采用水平和豎直法向量對傾斜攝影數據進行分類，不能覆蓋所有平整表面。其中特征閾值法識別平整面的精度較高。

本文將頂點、三角邊和面片分成平整與細節兩類，通過邊擴展采樣方法測量細節誤差，然后均勻平衡地對三維表面進行采樣，其中細節區域的采樣需要體現建筑框架的精度，因而采用了基于周長的蒙特卡洛采樣方法。在此基礎上測量兩類表面與原網格的誤差及平整表面的平整度。

1 平整表面的識別

在傾斜攝影重建的三維模型中，墻面、屋頂和道路占了很大一部分。一方面簡化代價最低，具有很大的評估價值；另外一方面，根據機器視覺的原理，特征點匹配往往是灰度微分較大的區域較準，而平整表面常常紋理相似度高，三維重建結果誤差大。不過平整表面在一般的航攝相機精度范圍內(>0.1 m)可視為完全平整，要對其進行單獨研究需要先提取并分類。

1.1 平整頂點識別法

平整表面識別的基本單元一般是三角邊和頂點。其中三角邊一般以邊二面角進行測度，頂點主要是研究目標點和周圍點的關系。本文采用的方法是先識別頂點，得到的平整點周圍的三角邊和面認為是平整的，在這之后利用識別的平整邊的特性擴大識別范圍。頂點的相鄰頂點定義為與其構成三角面的所有頂點，三角面片若平整，則至少有一個頂點或者兩條邊是平整的。首先進行平整頂點的識別。

(1)

其特征值為λ1、λ2、λ3(λ1≤λ2≤λ3)，根據最小二乘和特征值原理[22]，最小特征值和特征值之和為：

(2)

(3)

λsum可代表Vp和其鄰接頂點覆蓋的面積，因此將標準化特征值φ=λ1/λsum作為判斷頂點平整度的指標。φ作為平整度指標要好于相鄰三角形的夾角。假設一個頂點和與其連接的頂點在投影面上的形成以Vp為圓心，{Xi(i=1,2，…,nv)}形成八個夾角都為45°的標準形狀。半徑為1 m而假設每個頂點的波動都為0.1 m，則φ的值為0.011，對應圍繞頂點每條鄰邊與最小二乘平面的夾角均值為5.72°，若波動增加到0.2 m，則φ的值為0.045而夾角均值為11.31°。在波動增加一倍時，φ需要增至四倍而夾角只需要增至不到兩倍，所以φ作為頂點平整度指標可以更好地提取準平面區域。

確立提取平整表面的標準后，需要找到適合φ的分割閾值εφ，來分離平整表面和細節區域。為了驗證抽取方法的魯棒性，將由82個瓦片構成的大連市某區域的UDSM的頂點進行平整度計算，并統計所有瓦片φ和頂點加權比例的關系，其中頂點Vp的權為以公共頂點為Vp的所有三角面的面積之和，三角面的權為其面積，φ間隔為0.001，φ對應的值落在區間(φ,φ-0.001]的加權頂點比例。計算區間頂點的加權比例需要采用合適的最小統計值Smin，使得得到的不同瓦片的εφ均方根誤差最小。由于模型是一次完整航拍和同一個三維重建系統構建出來的，εφ應盡量保持一致。以0.01%作為間隔研究Smin的最佳值，得到當Smin為0.06%時，所有瓦片都擁有除初始零點區間之外的零點區間(φ取值連續為零)，且所有瓦片的εφ均方根誤差最小，圖1為整個UDSM的統計結果。其中非初始零點區間中最大“窗口”的中點為εφ，εφ落在區間[0.016,0.019]。在判定簡化網格的分割閾值εφ時，會出現其他零點區間，此時選擇最大的零點區間取中值得到對應的εφ。

圖1 大連某區域UDSM瓦片頂點平整度統計圖

1.2 邊緣平整網格識別

上節得到平整頂點進而得到平整三角面，基本上排除了非平整區域的偶然誤差。而在此識別過程中，有部分三角面只有兩條邊被識別為平整邊緣，另外一條邊可能處于平整區域邊緣，三個頂點都不平整，此時利用邊識別的方式，其二面角的閾值設定為已識別的平整三角邊平均值二面角Ad：

(4)

式中：Ue為頂點識別步驟已經識別出的邊的總和，n1和n2為邊的兩個鄰接面片的外法向量。此時當三角面片的一條邊被識別為平整時，即歸類為平整面片。這個步驟不產生新的平整頂點。

2 測量體系的構建

要構建出能測量原網格與簡化網格差異的架構，既需要滿足網格分類的要求，又要滿足分類后分別測量的要求。網格是由面組成的，測量網格的差異就需要轉化成數學上可以度量的點面距離，要實現這個轉化就需要對采樣主體(主網格)進行采樣。

傳統的三維模型的數據結構(頂點坐標和索引、三角面片對應三個頂點的索引、三角面片的正法向量)不足以支持上述兩個步驟的運行。

2.1 基于周長的邊擴展采樣方法

在UDSM中，建筑結構邊緣的三角面大多屬于低質量三角面片(正三角形質量最高)，但是建筑邊緣又決定了建模的基本架構，重要性高。所以Metro的以面積為權的采樣方式不再適用。同時還存在一些三角邊，交會的兩個面片卻都屬于平整面片，這些邊構造出城市架構：一方面建筑邊緣UDSM中最重要的要素——建筑物精確度非常高，而上述的邊緣位置是決定建筑位置信息的重要元素；另一方面由于光照造成部分鏡面反射，造成邊緣位置與周圍的區域像素區分度高，因而傾斜攝影建模精度高，需提高這種細節的權，即提高采樣率。為了保證采樣測距足夠準確和穩定，引入基于周長的邊擴展采樣方法。

在細節表面中，城市架構邊緣主要由低質量的三角形和純粹的邊緣構成，如圖2所示。

圖2 城市架構邊緣示例圖

圖2中的光線與下側的平整表面垂直，可以看到邊緣的三角網質量比較低。而其他細節(如樹冠)存在較多高質量的三角形。所以為了能增加城市架構的權，以三角形的周長而不是Metro的面積為權，對三角面片進行蒙特卡洛采樣。

對于兩側都是平整三角面片的三角邊，需要對其進行虛擬三角化，將這種三角邊視為周長為其兩倍的三角面片，周長加權采樣時，某虛擬三角邊的采樣點數量為Nspl時，采樣位置為該邊的Nspl分位點。

平整表面的采樣方法，與Metro相同。

2.2 基于周長的邊擴展采樣方法

根據以上分析，本文算法流程如下：

構建頂點(Vertex)、三角邊(Line)和三角面(Face)的數據結構，許多格式如obj三角面片本身就包含三個頂點的索引或者坐標和單位法向量，利用這個數據構建數據結構。

structure Vertex:

{ float pos[3];

Vertex(&Neivertex)[m];

float

float planarity;

float weight

bool sort;}

structure Line:

{ Vertex(&vertex)[2];

Face(&face)[2];

float angle;

bool sort;}

structure Face:

{ Vertex(&vertex)[3];

Line(&line)[3];

float normal[3];

float area;

float weight;

bool sort;}

其中邊索引是大部分三維模型格式不具備的，需要根據面結構進行重構。并且三個幾何結構都有一個負責分類的bool類型，以記錄點線面是否平整。三角頂點與通過三角邊連接的鄰點的坐標進行計算，得到平整度參數，最后通過整體運算得到頂點的分類——平整頂點或細節頂點。分類步驟所需要的頂點的權則通過面片索引得到，面片的權則通過面積和所有面片的面積得到。

線的分類是否為需要邊擴展成虛擬三角面，這個在細節誤差測量中非常關鍵。而所形成的條件為必須兩個端點為非平整而相鄰平面都平整，所以需要頂點和面片索引各兩個。

3 測量值及評估參數

通過上一節的采樣方法，將原網格視為主網格，所有采樣點與簡化網格的距離借助POV ray-tracer[23]中的高效方法進行測度，在此基礎上，計算兩個部分的平均誤差和均方根誤差。將UDSM原網格分成兩類之后，分別將其與原網格進行對照。評估參數如下：

平整表面平整度：當識別結束后，更新平整三角邊的總數Ue和對應平整表面中內部的三角邊(不包括單個連通域的邊界)兩側面片的單位法向量，得到評價的其中一個指標——表面平整度：

(5)

本質上是平整三角邊二面角的平均值歸一化的結果，相對于文獻[7]定義邊平整度的方法，這里定義的ξp與實際的邊夾角完全的正比例關系，不會受到余弦函數斜率不均勻的干擾。

平整表面平均誤差ξm和均方根誤差ξRMS：該指標是簡化后的平整區域與原網格的平均誤差。一方面雖然原模型存在平整表面誤差，平整表面簡化到一定程度理論上不會繼續增大，若出現突變，簡化網格結構必然沒能保持好。

其他細節表面平均誤差?m和均方根誤差?RMS：細節上特征的保持是所有網格簡化的重點，UDSM也不例外。這些區域的誤差才是UDSM簡化更加需要保持精度的部分。

上述參數的評估方法都是通過改變Metro主網格采樣的對象得到的，這里的主網格固定為原網格，非主網格就是簡化網格。一方面由于這個方向的誤差評價精細，比反向誤差要大，而且一般網格對比時取較大誤差。另一方面簡化后的網格細節表面的位置會發生很大的變化，圖3對比了QSlim[21]簡化90%前后細節表面的識別效果。

(a) 簡化前的細節識別效果

(b) QSlim簡化后的細節識別效果圖3 網格簡化前后細節非對稱性示例圖

圖3中的灰度值大的面片為細節表面，灰度值小的面片為平整表面。由圖可知原網格和簡化網格的分類差異大，無法對應，所以誤差雙向比較沒有意義。一方面研究的目的是評估UDSM原表面網格的細節簡化效果，所以將原網格視為主網格來進行評估；另一方面誤差一般取較大值，由于原網格較為精細，除了異常情況，原網格到簡化網格的距離往往大于簡化網格到原網格的距離。

4 實驗結果和討論

為驗證評估方法的性能，采用Visual Studio 2015平臺和VTK庫，對比分析所用的軟件是Metro4.07，計算機配置為Intel Core i5 CPU, 2.6 GHz，內存為8 GB，對三種不同的二次誤差矩陣邊折疊網格簡化算法進行評估，對比的三個簡化方法為QSlim算法、面積加權的QEM方法(aQSlim)和體積平方的度量方法(vQSlim)。實驗中用Metro測量這三種簡化方法與原網格的誤差時，最優替換法的結果比子集替換法更為接近，所以不同于文獻[3]采用子集替換法進行半邊折疊，本文采用最優替換法進行實驗，簡化比從微小的0.2至較高簡化比0.95，提升對評估方法精度的要求。

對選取的瓦片(v:55816;f:109936;diag:166.03)使用Metro測量三種簡化算法的均值誤差和均方誤差，如圖4所示。

(a)

(b)圖4 Metro測量結果

Metro測量的平均誤差和均方根誤差可以辨別vQSlim法比其他兩種簡化方法效果要差，與文獻[3]的結果一致，仔細比對結果可以發現其他兩種方法在不同簡化率的誤差沒有確定的大小關系。使用本文方法，得到平整表面和細節表面的簡化誤差如圖5所示。

(a)

(b)

(c)

(d)圖5 細節表面和平整表面誤差

細節表面的誤差增長的趨勢與整體誤差相似，而相對于Metro的結果，已經可以量化三種簡化算法的性能。細節表面的簡化精度決定UDSM簡化后的質量，由圖6看出對網格較為復雜的表面的簡化效果由高至低aQSlim>QSlim>vQSlim。實驗中aQSlim的平整表面網格最少，符合文獻[3]的實驗結果，在此基礎上細節表面的誤差說明了aQSlim算法用客觀數據表明其對UDSM細節和建筑框架的保持效果。相對aQSlim對平整表面簡化精度較差，vQSlim相對于QSlim有微小的優勢。通過圖5(b)(d)還可以看出分類比較誤差方法的均方根誤差不穩定性較大，在QSlim和vQSlim的平整表面均方根誤差比較中，大小關系不穩定，并且曲線平滑度不理想，不適合算法性能的精確比較，適合異常的監測。

由于UDSM中的平整表面精度不高，而平整表面的簡化精度主要指標是其平整度，如圖6所示。

圖6 平整表面平整度測量結果

平整表面平整度越高，平整度參數ξp越小，基于前文討論，平整度越高，證明對UDSM平整區域的還原程度越高。圖6說明了aQSlim算法對平整區域的還原度較高。而綜合圖5進行分析，vQSlim簡化后對平整網格平整度提升效果最差，而在平整網格誤差的降低效果不明顯(與QSlim算法相比)。說明以上涉及的評價指標沒有絕對的對應關系，都有自身的意義。從理論上說，是aQSlim對平整表面的高簡化率導致上述結果，上述實驗量化地證明了文獻[3]的結論。

圖7展示了實驗采用的瓦片樣貌，和挑選了黑色方框內的網格進行比較。aQSlim明顯建筑邊緣與地面垂直效果較好，與真實情況相符，從直觀效果上說明量化效果是可靠的。還可以看出，簡化后的建筑表面更加平整，更符合絕大多數建筑的特征，所以表面平整度參數也可視為評價簡化網格質量改善的指標，該平整度參數越低，網格質量改善程度越好。

(a) 實驗三角網格表面

(b)原網格 (c) QSlim簡化90%

(d) aQSlim簡化90% (e) vQSlim簡化90%圖7 簡化效果直觀展示圖

表1對整個大連某區域網格，并挑選了該UDSM的三個瓦片，比較本文評估方法與Metro的時間性能。

表1 評估方法的時間性能

從時間上看，本文算法比Metro略快。雖然在采樣測距前本文要對網格進行分類而且計算參數要多于Metro，然而Metro對簡化前后網格需要進行采樣并且得到Hausdoff距離。為了保證結果的客觀性，比較的時候索引統一采用靜態標準網格，即空間柵格索引[3]。

5 結 語

在比較原網格與簡化網格誤差的研究方面，直到現在，國內外的簡化算法改進研究一直使用Metro作為驗證手段，本文針對UDSM的網格，改進了長時間未進行改進的網格比較工具。

針對UDSM在非平滑特點，本文對簡化網格與原網格的誤差評價方法進行了較大改進，將原網格分為平整表面和細節表面兩類。針對細節表面的特點，設計出強調建筑物框架誤差的基于周長的邊擴展采樣方法，使得對UDSM細節測量更貼近UDSM的需求，即基于更大程度地保持建筑物的框架結構設計評估方法。針對平整表面傾斜攝影三維重建的建模精度較低，基于對城市地物的認識，引入平整度參數代替與原網格的誤差，更加客觀地評價平整網格表面。同時簡化過程中平整度的提升實際上提升了平整表面的精度，平整度指標從數據上證明了UDSM網格簡化并非只是降低城市三維重建的質量。本文提出的評估方法不依賴網格簡化算法的任何先驗步驟，魯棒性高。