城市場(chǎng)景結(jié)構(gòu)感知的網(wǎng)格模型簡(jiǎn)化算法

張春森¹,    張會(huì)¹,  郭丙軒², 彭哲³                            

1. 西安科技大學(xué)測(cè)繪科學(xué)與技術(shù)學(xué)院, 陜西 西安 710054;
2.武漢大學(xué)測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室, 湖北 武漢 430079;
3.武漢訊圖科技有限公司, 湖北 武漢 430079

收稿日期：2019-02-26；修回日期：2019-08-10

基金項(xiàng)目：國(guó)家自然科學(xué)基金重大研究計(jì)劃（91638203）；陜西省自然科學(xué)基金（2018JM5103）

第一作者簡(jiǎn)介：張春森(1963—), 男, 博士, 教授, 研究方向?yàn)閿?shù)字?jǐn)z影測(cè)量計(jì)算機(jī)視覺(jué)與遙感應(yīng)用。E-mail:zhchunsen@aliyun.com

摘要：針對(duì)二次誤差測(cè)度（QEM）網(wǎng)格簡(jiǎn)化算法全局幾何特征信息損失嚴(yán)重的缺點(diǎn)，提出一種具有結(jié)構(gòu)感知功能面向城市三維模型重建的網(wǎng)格簡(jiǎn)化算法。該算法顧及城市影像中平面結(jié)構(gòu)特征，以代理平面為全局特征約束條件，使模型在簡(jiǎn)化過(guò)程中全局結(jié)構(gòu)特征更多地被保持，以利于多層次細(xì)節(jié)模型（LOD技術(shù)）、網(wǎng)格優(yōu)化提速等模型后續(xù)操作。以傾斜攝影獲取影像生成的初始三角網(wǎng)格模型為試驗(yàn)數(shù)據(jù)，采用所給算法對(duì)其進(jìn)行網(wǎng)格簡(jiǎn)化并與QEM算法進(jìn)行對(duì)比。結(jié)果表明：所給算法簡(jiǎn)化精度及簡(jiǎn)化效率均優(yōu)于QEM算法。

關(guān)鍵詞：網(wǎng)格簡(jiǎn)化    場(chǎng)景結(jié)構(gòu)感知    三維重建    平面檢測(cè)    

Structure-aware simplified algorithm of mesh model for urban scene

ZHANG Chunsen¹, ZHANG Hui¹,   GUO Binxuan², PENG Zhe³                            

1. College of Geomatics, Xi'an University of Science and Technology, Xi'an 710054, China;
2. State Key Laboratory of Information Engineering in Surveying, Mapping & Remote Sensing, Wuhan University, Wuhan 430079, China;
3.Wuhan Xuntu Technology Co. Ltd., Wuhan 430079, China

Foundation support: The Major Research Plan of the National Nature Science Foundation of China (No. 91638203); The Natural Science Foundation of Shaanxi Province(No. 2018JM5103)

First author:  ZHANG Chunsen (1963—), male, PhD, professor, majors in digital photogrammetry computer vision and remote sensing application. E-mail:zhchunsen@aliyun.com.

Abstract: Aiming at the shortcomings of global geometric feature loss caused by quadratic error measure (QEM) mesh simplification algorithm, a structure-aware mesh simplification algorithm for urban environment 3D model reconstruction is proposed. The algorithm takes into account the planar structure features in urban images, and uses the proxy plane as the global feature constraint in the simplification process, so that the global structural features of the model are more preserved during the simplification process, which is conducive to the refinement and progressive transmission of the model (LOD technology), grid optimization speedup and other model follow-up operations. In this paper, the initial manifold triangle mesh model generated by oblique photography is taken as the experimental data. The proposed algorithm is used to simplify the mesh and compare with the QEM algorithm, which experimental results show that the proposed algorithm has excellent simplification accuracy and simplified efficiency than the QEM algorithm.

Key words: mesh simplification    scene structure aware    3D reconstruction    plane detection    

三維重建是數(shù)字城市建設(shè)的重要內(nèi)容之一。近年來(lái)測(cè)繪領(lǐng)域發(fā)展的傾斜攝影技術(shù)克服了傳統(tǒng)航空攝影只能從垂直角度拍攝的局限，以多角度、大范圍、高精度、高分辨率的方式快速獲取城市區(qū)域影像，在大規(guī)模并行計(jì)算的協(xié)助下可快速建立基于傾斜影像的三維模型，有效地降低了城市三維模型的建模成本，因此，傾斜攝影測(cè)量技術(shù)成為城市三維建模的首選技術(shù)^[1-3]。然而，隨著建模場(chǎng)景增大以及對(duì)模型細(xì)節(jié)精度要求提高，三維模型的數(shù)據(jù)量也顯著增大，給計(jì)算機(jī)實(shí)時(shí)計(jì)算、傳輸、處理和顯示三維模型帶來(lái)了困難。網(wǎng)格簡(jiǎn)化一方面在保持目標(biāo)結(jié)構(gòu)信息的同時(shí)，可減少三維模型存儲(chǔ)量，便于數(shù)據(jù)讀取和利用；另一方面，也為生成多層次細(xì)節(jié)模型(LOD)打下基礎(chǔ)^[4]，達(dá)到根據(jù)視點(diǎn)與模型之間的遠(yuǎn)近距離動(dòng)態(tài)調(diào)節(jié)簡(jiǎn)化比，降低場(chǎng)景復(fù)雜度，實(shí)現(xiàn)實(shí)時(shí)動(dòng)態(tài)顯示模型的效果，為后續(xù)網(wǎng)格優(yōu)化^[5-6]、紋理映射等操作奠定基礎(chǔ)。

近年來(lái)，國(guó)內(nèi)外學(xué)者在網(wǎng)格簡(jiǎn)化^[7]方面作了許多卓有成效的工作。根據(jù)簡(jiǎn)化過(guò)程中刪簡(jiǎn)掉的網(wǎng)格元素，可將網(wǎng)格簡(jiǎn)化^[8-9]大致分為：基于頂點(diǎn)移去的網(wǎng)格簡(jiǎn)化、基于面合并和面折疊的網(wǎng)格簡(jiǎn)化、基于邊折疊的網(wǎng)格簡(jiǎn)化^[10]。其中應(yīng)用最廣泛、效果最佳的是邊折疊簡(jiǎn)化策略。文獻(xiàn)[11]提出了通過(guò)優(yōu)化全局函數(shù)的邊折疊網(wǎng)格簡(jiǎn)化方法。由于該算法在誤差測(cè)度計(jì)算方面過(guò)于復(fù)雜，文獻(xiàn)[12]對(duì)其進(jìn)行改進(jìn)，提出了局部二次誤差測(cè)度的邊折疊算法(quadric error metrics，QEM)。QEM算法以網(wǎng)格頂點(diǎn)到局部平面距離的平方作為誤差測(cè)度。該方法計(jì)算過(guò)程簡(jiǎn)單、簡(jiǎn)化效率高、實(shí)用性能強(qiáng)，是最經(jīng)典、應(yīng)用最廣泛的網(wǎng)格簡(jiǎn)化算法。

在經(jīng)典的QEM算法基礎(chǔ)上，國(guó)內(nèi)學(xué)者也提出了多種有效的改進(jìn)算法。文獻(xiàn)[13]為提高QEM算法的簡(jiǎn)化效率，將三角網(wǎng)模型劃分為一系列強(qiáng)獨(dú)立區(qū)域，采用二次誤差測(cè)度計(jì)算邊折疊代價(jià)，將獨(dú)立區(qū)域內(nèi)的所有強(qiáng)獨(dú)立邊中的最小折疊代價(jià)作為強(qiáng)獨(dú)立區(qū)域排序值，取各個(gè)強(qiáng)獨(dú)立區(qū)域中折疊代價(jià)最小的邊并行地進(jìn)行折疊操作。文獻(xiàn)[14]給出在QEM算法的基礎(chǔ)上，在權(quán)值的計(jì)算中加入頂點(diǎn)法向量夾角與邊長(zhǎng)因子，以便更準(zhǔn)確地反映出模型的細(xì)節(jié)特征，并利用邊折疊的優(yōu)勢(shì)，引入基于八叉樹(shù)的模型劃分策略，在實(shí)現(xiàn)子模型簡(jiǎn)化的前提下，有效避免了子模型重組過(guò)程中的額外簡(jiǎn)化步驟。文獻(xiàn)[15]針對(duì)簡(jiǎn)化過(guò)程中生成漸進(jìn)網(wǎng)格時(shí)存在局部區(qū)域精度與效率平衡優(yōu)化的問(wèn)題，提出一種基于局部區(qū)域環(huán)間法矢夾角變換的半邊折疊漸進(jìn)網(wǎng)格簡(jiǎn)化算法；文獻(xiàn)[16]在簡(jiǎn)化過(guò)程中引入折疊點(diǎn)的拉普拉斯坐標(biāo)和原三角形法向量信息來(lái)更新折疊點(diǎn)位置；文獻(xiàn)[17]針對(duì)簡(jiǎn)化僅依賴局部特征而造成對(duì)尖銳特征保持差的問(wèn)題，首先計(jì)算曲面局部極點(diǎn)特征值，再疊加不同尺度下局部特征值的高斯差分獲得特征的視覺(jué)顯示度，將視覺(jué)顯示度作為權(quán)值賦給每個(gè)二次誤差矩陣，從而達(dá)到對(duì)顯著度較高區(qū)域特征保持的目的。以上改進(jìn)的QEM算法在簡(jiǎn)化過(guò)程中只改進(jìn)了局部特征保持效果，沒(méi)有顧及模型的整體結(jié)構(gòu)特征，隨著簡(jiǎn)化比的增大，模型的整體結(jié)構(gòu)特征缺失更加明顯^[18]。

為了適應(yīng)城市大場(chǎng)景三維模型重建，顧及城市影像中平面反映了大多數(shù)人工建筑物中諸如房頂、街道等的面狀結(jié)構(gòu)特征^[19]，本文提出一種基于結(jié)構(gòu)感知的城市場(chǎng)景網(wǎng)格模型簡(jiǎn)化算法，即在QEM算法通過(guò)二次誤差測(cè)度維持局部特征的同時(shí)，通過(guò)平面檢測(cè)算法提取代理平面，并以此作為簡(jiǎn)化過(guò)程中的全局特征約束條件對(duì)網(wǎng)格進(jìn)行簡(jiǎn)化。試驗(yàn)結(jié)果表明：在相同的簡(jiǎn)化比下，本文算法能更好地保持模型的結(jié)構(gòu)特征，尤其在較高簡(jiǎn)化比下，本文算法明顯優(yōu)于QEM算法，達(dá)到了較好的簡(jiǎn)化效果。

1  結(jié)構(gòu)保持的場(chǎng)景網(wǎng)格簡(jiǎn)化方法

本文方法是在QEM算法基礎(chǔ)上，通過(guò)二次誤差測(cè)度^[20]在維持局部特征的同時(shí)，根據(jù)平面檢測(cè)算法提取代理平面，并以此作為網(wǎng)格簡(jiǎn)化過(guò)程中的全局特征約束條件參與網(wǎng)格簡(jiǎn)化。算法主要包括：在原始三維模型上通過(guò)區(qū)域增長(zhǎng)檢測(cè)代理平面、代理平面參與簡(jiǎn)化計(jì)算帶權(quán)值的二次誤差Q(e)，根據(jù)代理平面之間的關(guān)系給出結(jié)構(gòu)保持原則，邊收縮代價(jià)計(jì)算以及根據(jù)代價(jià)值確定邊折疊順序簡(jiǎn)化網(wǎng)格模型等步驟。總體技術(shù)流程如圖 1所示。

圖 1 本文技術(shù)流程 Fig. 1     Technique flow chart

圖選項(xiàng)

1.1  經(jīng)典QEM算法

QEM算法^[21]是在簡(jiǎn)化過(guò)程中以邊作為刪除對(duì)象，故歸為邊折疊簡(jiǎn)化類。該算法以每條邊兩端點(diǎn)到相關(guān)局部平面距離的平方作為二次誤差測(cè)度確定邊簡(jiǎn)化順序，由簡(jiǎn)化比確定折疊邊數(shù)量。如圖 2所示，邊折疊是將網(wǎng)格中一條滿足條件的邊V₁、V₂折疊，同時(shí)計(jì)算出一個(gè)新頂點(diǎn)V，并更新模型的幾何拓?fù)潢P(guān)系，形成新的網(wǎng)格模型。

圖 2 邊折疊操作 Fig. 2     Edge collapse

圖選項(xiàng)

QEM算法的關(guān)鍵在于求解二次誤差，因此定義任意平面的二次矩陣Q如式(1)所示

(1)

設(shè)圖 2中點(diǎn)V₁=[x₁, y₁, z₁, 1]^T的相關(guān)局部平面集合為plane(V₁)，集合中所有平面的二次矩陣?yán)奂雍蜑?strong>Q₁，同理對(duì)于點(diǎn)V₂=[x₂, y₂, z₂, 1]^T設(shè)其相關(guān)局部平面集合為plane(V₂)，集合中所有平面的二次矩陣?yán)奂雍蜑?strong>Q₂。經(jīng)過(guò)邊折疊操作收縮到頂點(diǎn)V=[x, y, z, 1]^T，更新拓?fù)潢P(guān)系之后，則簡(jiǎn)化后，網(wǎng)格二次誤差為新頂點(diǎn)V到平面集合plane(V₁)和plane(V₂)中所有局部平面的距離累加和，將其稱為該邊折疊后代價(jià)C

(2)

對(duì)于邊折疊簡(jiǎn)化算法，需要在邊折疊之后找到新生成頂點(diǎn)的位置，即圖 2中的V=[x, y, z, 1]^T。由式(2)可知，新頂點(diǎn)的位置直接影響著邊收縮代價(jià)，也決定了整個(gè)模型中邊折疊的順序，以及簡(jiǎn)化后的模型。

1.2  結(jié)構(gòu)感知城市場(chǎng)景網(wǎng)格模型簡(jiǎn)化算法

在城市場(chǎng)景中，人工建筑多以平面作為最基本也是最重要的幾何結(jié)構(gòu)，因此可以用平面代表大多數(shù)人工建筑物如屋頂、街道等重建目標(biāo)的全局結(jié)構(gòu)特征參與簡(jiǎn)化。相較于QEM算法，本文算法在求解二次誤差，確定邊折疊順序時(shí)作如下改進(jìn)：首先檢測(cè)出代理平面作為原始模型的全局特征，然后對(duì)所有邊根據(jù)局部特征和全局特征關(guān)聯(lián)一個(gè)權(quán)值，即帶權(quán)值的二次誤差Q(e)，在此基礎(chǔ)上綜合考慮結(jié)構(gòu)保持原則，最終計(jì)算出網(wǎng)格模型每條邊收縮后新頂點(diǎn)位置以及該邊收縮的代價(jià)值，根據(jù)代價(jià)值確定邊折疊順序簡(jiǎn)化網(wǎng)格模型。

1.2.1  代理平面檢測(cè)

代理平面檢測(cè)首先根據(jù)三角面到其局部切平面的距離作為平坦度衡量標(biāo)準(zhǔn)，將原始模型中所有三角網(wǎng)格按照平坦度進(jìn)行排序。依次選取平坦度指數(shù)，將指數(shù)最高且尚未被遍歷到的三角面作為種子面進(jìn)行區(qū)域增長(zhǎng)。每擴(kuò)散到一個(gè)三角面則計(jì)算其與本次區(qū)域增長(zhǎng)的種子面之間的法向量夾角和兩者之間的距離，判斷是否同時(shí)小于給定閾值作為區(qū)域繼續(xù)增長(zhǎng)的判斷條件，若均小于給定閾值則繼續(xù)進(jìn)行區(qū)域增長(zhǎng)，否則停止。此外，為避免每個(gè)三角形都能成為一個(gè)單獨(dú)的區(qū)域，每完成一次區(qū)域增長(zhǎng)還需保證該區(qū)域的面積總和大于給定閾值才能作為一個(gè)完成的增長(zhǎng)區(qū)域。

每次區(qū)域增長(zhǎng)遍歷到的三角面認(rèn)為屬于一個(gè)近似平面，取區(qū)域內(nèi)所有網(wǎng)格頂點(diǎn)擬合為代理平面Φ，表示為ax+by+cz+d=0或Φ=[a, b, c, d]，其中n=[a, b, c]為該平面的單位法向量。值得注意的是原始模型中的三角面未必只對(duì)應(yīng)一個(gè)代理平面，可能對(duì)應(yīng)多個(gè)代理平面，也可能沒(méi)有對(duì)應(yīng)的代理平面。

為了使區(qū)域增長(zhǎng)結(jié)果和代理平面更加直觀，對(duì)原始模型和檢測(cè)出的代理平面按照以下原則可視化^[22-23]：

原則1：相鄰代理平面賦予不同的顏色。

原則2：對(duì)于屬于多個(gè)代理平面的三角面，將三角面的顏色設(shè)置為與自身法向量和代理平面的法向量最接近的代理平面的顏色。

原則3：對(duì)于不屬于任何代理平面的三角面，將其顏色設(shè)置為灰色。

1.2.2  加權(quán)二次誤差Q(e)

在經(jīng)典的QEM算法中二次誤差計(jì)算只考慮到邊折疊后新生成頂點(diǎn)到相關(guān)局部切平面之間的距離并作為邊折疊代價(jià)。本文算法引進(jìn)代表城市模型全局特征的代理平面，在計(jì)算二次誤差時(shí)兼顧全局輪廓和內(nèi)部結(jié)構(gòu)特征，計(jì)算新生成頂點(diǎn)到其相關(guān)的局部切平面、代理平面、兩者的正則面的距離，提出一種新的加權(quán)二次誤差Q(e)計(jì)算公式

(3)

Q(e)由維持模型的內(nèi)部結(jié)構(gòu)特征Q_inner和維持整個(gè)模型的輪廓結(jié)構(gòu)特征Q_bdry兩部分組成。其中參數(shù)μ∈(0, 1)。Q_inner可表達(dá)為新生成頂點(diǎn)到局部切平面和多個(gè)代理平面的加權(quán)二次誤差，Q_bdry可表達(dá)為局部切平面和代理平面正則曲面的加權(quán)二次誤差

(4)

式(4)為待折疊邊e的二次誤差計(jì)算公式，即本文式(3)中維持模型的內(nèi)部結(jié)構(gòu)特征Q_inner和維持整個(gè)模型的輪廓結(jié)構(gòu)特征Q_bdry的計(jì)算過(guò)程。

其中Q_inner可表達(dá)為新生成頂點(diǎn)到局部切平面和多個(gè)代理平面的加權(quán)二次誤差, 維持模型的內(nèi)部結(jié)構(gòu)特征。T(e)代表待折疊邊e所屬原始模型三角面的集合，t代表集合T(e)中的任意一個(gè)三角面，|t|代表三角面t的面積。如圖 3(a)所示，折疊邊e屬于三角面t₁和t₂，即T(e)={t_1, t₂}；λ∈(0, 1)是一個(gè)經(jīng)驗(yàn)值常量；Q_pt表示局部切平面pt(如圖 3(c)所示)的Q矩陣；proxies表示三角面t所屬代理平面集合，如圖 3(b)所示黃色區(qū)域?yàn)槿敲?em>t₁屬代理平面集合，Q_Φ表示代理平面Φ的Q矩陣。

圖 3 Q(e)求解過(guò)程相關(guān)元素解釋 Fig. 3Q(e) interpretation of the relevant elements of the calculation process

圖選項(xiàng)

式(4)中Q_bdry可表達(dá)為局部切平面和代理平面正則曲面的加權(quán)二次誤差, 維持整個(gè)模型的輪廓結(jié)構(gòu)特征。其中，e′表示原始三角網(wǎng)模型的邊界邊，如圖 3(d)所示三角網(wǎng)模型中，標(biāo)注的紫色邊只屬于一個(gè)三角面則認(rèn)為該類邊為三角網(wǎng)模型的邊界邊，集合E_?κ表示原始三角網(wǎng)模型的邊界邊集合；|t_e′|代表邊界邊e′所屬的原始模型中唯一三角面的面積；Q_e′, t_e′代表包含邊界邊e′的三角面t_e′的正則面(如圖 3(e)所示)的Q矩陣；E_?κ\Φ表示原始三角網(wǎng)模型代理平面中包含的邊界邊集合；Q_{e′, Φ}代表包含邊界邊e′且垂直于其所在代理平面的Q矩陣。

Q_inner項(xiàng)的作用是維持模型的內(nèi)部結(jié)構(gòu)特征。前一項(xiàng)維持原始模型在簡(jiǎn)化過(guò)程中到其局部切平面的距離變化不大，因?yàn)榫植壳衅矫娲砹四Ｐ蛢?nèi)部局部特征，因此這一項(xiàng)意義為控制簡(jiǎn)化前后模型內(nèi)部局部變化不大；后一項(xiàng)維持簡(jiǎn)化前后模型到代理平面之間的距離變化不大，因?yàn)榇砥矫娲砹四Ｐ蛢?nèi)部全局特征，因此這一項(xiàng)的意義為保持簡(jiǎn)化后模型內(nèi)部的全局特征。

Q_bdry的前一項(xiàng)維持原始模型的大致輪廓，防止過(guò)度簡(jiǎn)化，如若是一張近似平面化成一個(gè)點(diǎn)，這種操作不能出現(xiàn)在網(wǎng)格簡(jiǎn)化過(guò)程中；后一項(xiàng)是維持代理平面的形狀，因?yàn)榇砥矫娲砟Ｐ驼w大致輪廓，也有邊界并不是一個(gè)無(wú)限制的平面，因此簡(jiǎn)化后要保持代理平面的整體結(jié)構(gòu)變化不大。

1.2.3  結(jié)構(gòu)保持規(guī)則

QEM算法每次折疊一條邊，就會(huì)刪去兩個(gè)頂點(diǎn)、兩個(gè)三角面及一條邊，并生成一個(gè)新頂點(diǎn)。一系列操作之后不但影響了模型自身點(diǎn)、線、面的拓?fù)潢P(guān)系，也可能影響該模型代理平面的拓?fù)潢P(guān)系^[24-25]。而代理平面的拓?fù)潢P(guān)系代表了全局結(jié)構(gòu)特征應(yīng)禁止發(fā)生改變。因此本文算法添加了以下兩種結(jié)構(gòu)保持原則，將折疊后會(huì)破壞這兩種原則的邊的權(quán)值強(qiáng)制設(shè)置為一個(gè)極大值，不能被折疊。

(1) 代理平面圖保持原則。如圖 4(a)所示，代理平面無(wú)向圖中P₀和P₁之間沒(méi)有連通關(guān)系，若將v₀和v₁所組成的邊收縮之后，形成如圖 4(b)所示的新的代理平面無(wú)向圖，兩代理平面相互連通，破壞了原模型代理平面拓?fù)潢P(guān)系，因此該邊禁止折疊。

圖 4 代理平面圖保持原則 Fig. 4     Graph preservation rules

圖選項(xiàng)

(2) 代理平面保持原則。由于代理平面是由多個(gè)原始模型中的三角面限制的有限平面，邊折疊過(guò)程會(huì)造成三角面?zhèn)€數(shù)的減小，引起代理平面改變。如圖 5所示，代理平面P₁為正方形，若將v₀和v₁所組成的邊收縮之后，P₁形狀改變?yōu)槿切?，破壞了代理平面的形狀特征，因此?guī)定代理平面無(wú)向圖中任意一個(gè)代理平面包含的頂點(diǎn)的個(gè)數(shù)小于閾值μ則不能進(jìn)行邊收縮。

圖 5 代理平面保持原則 Fig. 5     Proxy preservation rules

圖選項(xiàng)

1.2.4  邊收縮代價(jià)

邊折疊操作代價(jià)如式(2)所示，因此新頂點(diǎn)位置的選取直接決定了邊折疊代價(jià)的大小。對(duì)比多種新頂點(diǎn)位置確定方法，本文采用文獻(xiàn)[26-27]中的方法，將Q(e)=(Q₁+Q₂)分解

(5)

若A為非奇異矩陣，則新頂點(diǎn)位置V=A^-1f; 若A為奇異矩陣，該矩陣不存在逆矩陣的情況下新頂點(diǎn)位置為收縮邊的中點(diǎn)。

計(jì)算原始網(wǎng)格模型中所有邊的初始代價(jià)值，按照升序進(jìn)行排列，優(yōu)先折疊代價(jià)值最小的邊，確定新的頂點(diǎn)，再重新計(jì)算邊折疊代價(jià)值，再次進(jìn)行排序重復(fù)操作。由于實(shí)現(xiàn)過(guò)程中包含了大量的舊邊刪除和新頂點(diǎn)插入的操作，且每次都折疊代價(jià)值最小的邊，因此在實(shí)現(xiàn)過(guò)程中為了提高效率將邊折疊代價(jià)按照堆排序算法^[28]后，以頂堆的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)，確定簡(jiǎn)化邊序列。

2  試驗(yàn)結(jié)果與分析

為了驗(yàn)證本文算法的可行性及有效性，在Microsoft Visual C++及CGAL庫(kù)環(huán)境下將算法編程實(shí)現(xiàn)。利用無(wú)人機(jī)拍攝的135幅山東威海某區(qū)域傾斜影像，通過(guò)圖割構(gòu)網(wǎng)算法生成網(wǎng)格模型(圖 6)，并以此作為網(wǎng)格簡(jiǎn)化原始數(shù)據(jù)。采用本文算法對(duì)其進(jìn)行簡(jiǎn)化，其中計(jì)算加權(quán)二次誤差Q(e)時(shí)，參數(shù)λ取值0.5，代理平面保持原則中閾值μ=4，并與QEM算法得到的簡(jiǎn)化結(jié)果進(jìn)行對(duì)比。圖 7(a)為采用本文算法對(duì)試驗(yàn)區(qū)三維網(wǎng)格模型檢測(cè)出的代理平面，圖 7(b)-(d)為檢測(cè)出代理平面局部放大圖。從顯示結(jié)果可以看出：本文算法對(duì)試驗(yàn)區(qū)建筑物的立面、屋頂及平坦的街道等面狀特征都能很好地檢測(cè)出來(lái)。

圖 6 試驗(yàn)區(qū)網(wǎng)格模型 Fig. 6     Test area mesh model

圖選項(xiàng)

圖 7 代理平面檢測(cè) Fig. 7     Proxy plane detection

圖選項(xiàng)

圖 8為試驗(yàn)區(qū)網(wǎng)格模型不同程度的簡(jiǎn)化結(jié)果，其中圖 8(a)為原始網(wǎng)格模型，圖 8(b)、(d)、(f)為利用本文算法簡(jiǎn)化比分別為10%、50%、99%的簡(jiǎn)化結(jié)果，對(duì)應(yīng)的圖 8(c)、(e)、(g)為使用QEM算法簡(jiǎn)化比分別為10%、50%、99%的簡(jiǎn)化結(jié)果。

圖 8 簡(jiǎn)化結(jié)果對(duì)比 Fig. 8     The comparison of the proposed model

圖選項(xiàng)

從視覺(jué)效果看，在簡(jiǎn)化程度比較小的情況下本文結(jié)構(gòu)感知算法和QEM算法都能夠達(dá)到很好的簡(jiǎn)化效果，其中本文算法局部和全局特征更加明顯；當(dāng)簡(jiǎn)化程度增大以至模型要求達(dá)到極簡(jiǎn)的情況時(shí)，本文結(jié)構(gòu)感知算法相較于傳統(tǒng)的QEM算法效果顯著，即對(duì)模型大程度的簡(jiǎn)化依舊能保持模型的整體結(jié)構(gòu)特征。

采用文獻(xiàn)[29-30]中Metro4.7工具測(cè)量原始模型與簡(jiǎn)化模型間的豪斯多夫距離作為客觀評(píng)價(jià)兩種算法的簡(jiǎn)化效果標(biāo)準(zhǔn)，對(duì)比結(jié)果如表 1所示。圖 9是根據(jù)表 1給出的可視化折線圖。

表 1 不同方法簡(jiǎn)化模型誤差對(duì)比Tab. 1 Error comparison of simplified models by different methods

表選項(xiàng)

圖 9 不同方法簡(jiǎn)化模型誤差對(duì)比曲線 Fig. 9     Error comparison curves of simplified models by different methods

圖選項(xiàng)

由圖 9可以看出：當(dāng)簡(jiǎn)化程度較小時(shí)，兩種算法的簡(jiǎn)化誤差基本上相差不大，隨著簡(jiǎn)化比的加大簡(jiǎn)化誤差明顯增大，尤其當(dāng)簡(jiǎn)化比大于80%以后，本文算法表現(xiàn)出明顯的優(yōu)勢(shì)。表 2為兩種不同方法簡(jiǎn)化時(shí)間對(duì)比，可以得出：在相同簡(jiǎn)化比下，本文算法較QEM算法更加高效。綜合表 1與表 2結(jié)果可以看出：本文所給算法的簡(jiǎn)化精度與速度均優(yōu)于QEM方法，是一種有效的三角網(wǎng)格簡(jiǎn)化算法。

表 2 不同方法簡(jiǎn)化時(shí)間對(duì)比

Tab. 2 Different methods simplify time comparison

表選項(xiàng)

3  結(jié)論

由于城市環(huán)境下的三維模型構(gòu)建，帶有平面的網(wǎng)格簡(jiǎn)化模型更有助于對(duì)場(chǎng)景的理解以及后續(xù)應(yīng)用的部署^[31-32]，本文在QEM算法基礎(chǔ)上提出一種感知全局特征的網(wǎng)格模型簡(jiǎn)化算法，利用原始三角網(wǎng)格檢測(cè)出來(lái)的平面代理全局特征，將其幾何和結(jié)構(gòu)特征添加到QEM算法邊收縮簡(jiǎn)化過(guò)程中。試驗(yàn)結(jié)果表明，本文提出的結(jié)構(gòu)感知算法相較于傳統(tǒng)的QEM算法更能夠在簡(jiǎn)化過(guò)程中保持模型的局部和全局特征，簡(jiǎn)化前后誤差更小，是一種有效的三角網(wǎng)格簡(jiǎn)化算法。

【引文格式】張春森, 張會(huì), 郭丙軒, 等. 城市場(chǎng)景結(jié)構(gòu)感知的網(wǎng)格模型簡(jiǎn)化算法. 測(cè)繪學(xué)報(bào)，2020，49(3)：334-342. DOI: 10.11947/j.AGCS.2020.20190068