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

劉盛恩 薛俊詩 易 輝

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

0 引 言

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

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

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

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

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

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

1 平整表面的識別

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

1.1 平整頂點識別法

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

(1)

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

(2)

(3)

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

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

圖1 大連某區(qū)域UDSM瓦片頂點平整度統(tǒng)計圖

1.2 邊緣平整網(wǎng)格識別

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

(4)

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

2 測量體系的構(gòu)建

要構(gòu)建出能測量原網(wǎng)格與簡化網(wǎng)格差異的架構(gòu)，既需要滿足網(wǎng)格分類的要求，又要滿足分類后分別測量的要求。網(wǎng)格是由面組成的，測量網(wǎng)格的差異就需要轉(zhuǎn)化成數(shù)學(xué)上可以度量的點面距離，要實現(xiàn)這個轉(zhuǎn)化就需要對采樣主體(主網(wǎng)格)進(jìn)行采樣。

傳統(tǒng)的三維模型的數(shù)據(jù)結(jié)構(gòu)(頂點坐標(biāo)和索引、三角面片對應(yīng)三個頂點的索引、三角面片的正法向量)不足以支持上述兩個步驟的運行。

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

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

在細(xì)節(jié)表面中，城市架構(gòu)邊緣主要由低質(zhì)量的三角形和純粹的邊緣構(gòu)成，如圖2所示。

圖2 城市架構(gòu)邊緣示例圖

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

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

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

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

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

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

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;}

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

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

3 測量值及評估參數(shù)

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

平整表面平整度：當(dāng)識別結(jié)束后，更新平整三角邊的總數(shù)Ue和對應(yīng)平整表面中內(nèi)部的三角邊(不包括單個連通域的邊界)兩側(cè)面片的單位法向量，得到評價的其中一個指標(biāo)——表面平整度：

(5)

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

平整表面平均誤差ξm和均方根誤差ξRMS：該指標(biāo)是簡化后的平整區(qū)域與原網(wǎng)格的平均誤差。一方面雖然原模型存在平整表面誤差，平整表面簡化到一定程度理論上不會繼續(xù)增大，若出現(xiàn)突變，簡化網(wǎng)格結(jié)構(gòu)必然沒能保持好。

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

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

(a) 簡化前的細(xì)節(jié)識別效果

(b) QSlim簡化后的細(xì)節(jié)識別效果圖3 網(wǎng)格簡化前后細(xì)節(jié)非對稱性示例圖

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

4 實驗結(jié)果和討論

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

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

(a)

(b)圖4 Metro測量結(jié)果

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

(a)

(b)

(c)

(d)圖5 細(xì)節(jié)表面和平整表面誤差

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

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

圖6 平整表面平整度測量結(jié)果

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

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

(a) 實驗三角網(wǎng)格表面

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

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

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

表1 評估方法的時間性能

從時間上看，本文算法比Metro略快。雖然在采樣測距前本文要對網(wǎng)格進(jìn)行分類而且計算參數(shù)要多于Metro，然而Metro對簡化前后網(wǎng)格需要進(jìn)行采樣并且得到Hausdoff距離。為了保證結(jié)果的客觀性，比較的時候索引統(tǒng)一采用靜態(tài)標(biāo)準(zhǔn)網(wǎng)格，即空間柵格索引[3]。

5 結(jié) 語

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

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