基于質(zhì)心Voronoi圖重構(gòu)的UDSM邊折疊簡(jiǎn)化

劉盛恩，陳向?qū)帲醯贸?/p>

（中國(guó)人民解放軍航天工程大學(xué)，北京 101416）

引言

網(wǎng)格簡(jiǎn)化主要分為3 類(lèi)：第一種直接從原網(wǎng)格提取矢量數(shù)據(jù)進(jìn)行頂點(diǎn)聚類(lèi)如文獻(xiàn)[1]，這種方法不增加新的矢量數(shù)據(jù)，聚類(lèi)方法的效果很難達(dá)到要求[2]；第二種采樣以減少矢量數(shù)據(jù)，這種方法在消除被采樣的矢量數(shù)據(jù)同時(shí)也少量添加以提高簡(jiǎn)化效果，邊折疊和面聚合都屬于這一類(lèi)；第三種就是基于矢量數(shù)據(jù)本身進(jìn)行分析，重新布點(diǎn)構(gòu)網(wǎng)。

五視圖航拍城市三維重建是機(jī)器視覺(jué)的重要應(yīng)用之一。其中通過(guò)存儲(chǔ)不同簡(jiǎn)化率的網(wǎng)格來(lái)構(gòu)建層次細(xì)節(jié)(level of details, LOD)是實(shí)現(xiàn)動(dòng)態(tài)流暢的三維漫游的基本方法。理想的三維網(wǎng)格瀏覽網(wǎng)格應(yīng)該保持不變，但對(duì)大范圍網(wǎng)格如UDSM，無(wú)簡(jiǎn)化漫游GPU 會(huì)嚴(yán)重過(guò)載，所以簡(jiǎn)化雖然會(huì)對(duì)三維重建結(jié)果分析精度有一定的影響，但在這時(shí)必須對(duì)網(wǎng)格簡(jiǎn)化以構(gòu)建LOD[3]。因此視點(diǎn)變化時(shí)網(wǎng)格出現(xiàn)明顯變化的范圍越小，漫游時(shí)視覺(jué)效果越好。UDSM 結(jié)構(gòu)復(fù)雜，存在大量理論上的平整且紋理相似的表面如墻面、屋頂、道路，像素分辨度低。一方面完全平整的表面幾何上要求苛刻，另外一方面上述位置常常像素分辨度低，如文獻(xiàn)[4]，在光滑的桌子、白色的書(shū)頁(yè)里都沒(méi)有選取特征點(diǎn)，這些位置匹配精度過(guò)低，而城市里的平整表面就符合上述特點(diǎn)。

基于Voronoi 圖的簡(jiǎn)化耗時(shí)較長(zhǎng)[5]。但如果將基于Voronoi 圖重構(gòu)(處理后頂點(diǎn)數(shù)量基本保持不變)為基礎(chǔ)進(jìn)行簡(jiǎn)化，則研究時(shí)不將初始化重構(gòu)的時(shí)間作為簡(jiǎn)化時(shí)間考慮[6]，而且UDSM 表面重建的巨型工程中，就包含對(duì)點(diǎn)云進(jìn)行處理和構(gòu)網(wǎng)的過(guò)程[7]。重建的點(diǎn)云直接進(jìn)行Delaunay 三角化是原網(wǎng)格，包含完整的三維重建信息。本文將對(duì)網(wǎng)格進(jìn)行重構(gòu)代替直接的Delaunay 三角化，再進(jìn)行邊折疊簡(jiǎn)化。

但許多簡(jiǎn)化算法如文獻(xiàn)[6][8][9]與原網(wǎng)格的誤差較大，這些研究回避了與QSlim[10]在誤差和時(shí)間方面的比較，初步比較發(fā)現(xiàn)這些文獻(xiàn)的經(jīng)典模型簡(jiǎn)化后的誤差和簡(jiǎn)化時(shí)間都明顯大于QSlim 簡(jiǎn)化誤差。但是純粹比較與原網(wǎng)格誤差有很大的局限性，實(shí)際上上述文獻(xiàn)細(xì)節(jié)的保持要好于QSlim。細(xì)節(jié)的保持已經(jīng)成為網(wǎng)格簡(jiǎn)化最新成果的基本立足點(diǎn)。

細(xì)節(jié)的保持主要在于模型的輪廓[8]、建筑架構(gòu)的保持[11]以及網(wǎng)格表面曲率變化較大位置的保持。本文首先將UDSM 瓦片利用質(zhì)心Voronoi 圖規(guī)則進(jìn)行重構(gòu)，再利用QSlim 簡(jiǎn)化。保持較高時(shí)間效率的同時(shí)，提升細(xì)節(jié)的保持度，減少簡(jiǎn)化過(guò)程中發(fā)生明顯變化表面的比例。

1 質(zhì)心Voronoi 圖

質(zhì)心Voronoi 圖(centroid voronoi diagram, CVD)的規(guī)則是網(wǎng)格重劃分的規(guī)則，三角網(wǎng)屬于離散的數(shù)據(jù)模型，從連續(xù)的定義擴(kuò)展到離散的定義，以使其可以對(duì)網(wǎng)格進(jìn)行重構(gòu)或者簡(jiǎn)化。

1.1 連續(xù)質(zhì)心Voronoi 圖

全集Ω 是由n個(gè)不同區(qū)域(zi∶i=0,1,···,n-1)組成的a維區(qū)域(本文的a=3，暨三維)，Voronoi 圖(VD)按照下式規(guī)則將Ω 分為n個(gè)不同的單元格Ci：

連續(xù)情形Voronoi 單元格的位置就是其質(zhì)心坐標(biāo)Zi[12]：

式中ρ(x)是密度函數(shù)。構(gòu)建質(zhì)心Voronoi 圖(CVD)要使其能量值E達(dá)到最低：

1.2 離散質(zhì)心Voronoi 圖

參照[5]對(duì)離散CVD 的定義，Ω 不再是一個(gè)連續(xù)的空間而是一個(gè)三角網(wǎng)M。構(gòu)建CVD 有2 種方法：以三角面片或者頂點(diǎn)作為聚合單元?？紤]到頂點(diǎn)數(shù)量大致只有面片數(shù)量的一半。由于頂點(diǎn)密集處出現(xiàn)拓?fù)涞姆纸缈赡苄源?，UDSM 的建筑邊界等位置都有很多分界，并且這些邊界還有可能包含非流形，以頂點(diǎn)為單元進(jìn)行聚類(lèi)更加適合上述情況。

離散CVD 的能量值定義如下：

這時(shí)每個(gè)單元Cj的中心為zi，但并不一定是Cj的質(zhì)心，每個(gè)單元Ij的能量可以化簡(jiǎn)為：

其中：

Aj的值由Ij的幾何；特性和密度函數(shù)ρ(x)決定，在這個(gè)密度下Ij的權(quán)就是Mj，而γj則是Ij的質(zhì)心。由公式(5)則得總能量：

可繼續(xù)分解為：

其中：

在公式(10)中，只有F隨著Ci聚類(lèi)方式的變化而發(fā)生變化。在(10)式中，無(wú)論Voronoi 圖怎么設(shè)置，參數(shù)Aj和Mi‖γi‖2都不會(huì)變。所以問(wèn)題轉(zhuǎn)化為求Fmin。另一方面，由于Voronoi 圖是離散的，故將Mj視為聚類(lèi)單元的密度ρj。這里還需要強(qiáng)調(diào)的是，基于三維模型的特點(diǎn)，所有公式中的距離都是測(cè)地距離，暨必須按照拓?fù)湟?guī)則沿著頂點(diǎn)或者單元格的中心進(jìn)行測(cè)距，而非簡(jiǎn)單的二維直線距離。

所有公式中的j可以指代第j個(gè)聚類(lèi)的三角面片或者聚類(lèi)的頂點(diǎn)。對(duì)三維網(wǎng)格進(jìn)行Voronoi 構(gòu)圖時(shí)，距離‖x-zi‖是測(cè)地距離，而一個(gè)面片內(nèi)密度恒定，其距離測(cè)定用其幾何中心來(lái)代替[5]，這種方法會(huì)造成拓?fù)涮卣鞯钠茐?。圖1 中V1和V2是2 個(gè)頂點(diǎn)，邊V1V2是包含重要拓?fù)涮卣鞯娜沁?。?dāng)聚類(lèi)頂點(diǎn)時(shí)V1和V2就是測(cè)距節(jié)點(diǎn)，當(dāng)聚類(lèi)面片時(shí)，F(xiàn)1和F2是測(cè)距節(jié)點(diǎn)。圖1 標(biāo)注出兩種情況從A到B的測(cè)地距離，很明顯看出聚類(lèi)頂點(diǎn)時(shí)，測(cè)地距離為聚類(lèi)頂點(diǎn)時(shí)測(cè)地距離為(假設(shè)邊長(zhǎng)為2，單位密度)，密度不均勻時(shí)這個(gè)距離差依然不會(huì)變，距離差越大，對(duì)應(yīng)位置布點(diǎn)越密集。所以選擇后者進(jìn)行聚類(lèi)。

圖1 圖解2 種聚類(lèi)方式的測(cè)地距離Fig.1 Illustration of geodesic distance of two clustering methods

2 算法的執(zhí)行

定義離散CVD 后，需要解決幾個(gè)問(wèn)題：一是初始化Voronoi 圖密度；二是如何初始化Voronoi 圖中心；三是初始化后如何進(jìn)行聚類(lèi)。

本文算法的Voronoi 單元格數(shù)量與模型頂點(diǎn)數(shù)量一致，進(jìn)行重構(gòu)。再使用QSlim 算法進(jìn)行簡(jiǎn)化，減少了UDSM 簡(jiǎn)化后的失真。

2.1 初始化Voronoi 圖密度

初始化需要確定每個(gè)Voronoi 單元格中心的分布，若采用文獻(xiàn)[5]的隨機(jī)布點(diǎn)方法，則中心點(diǎn)將均勻分布到網(wǎng)格的周?chē)簿褪沟妹總€(gè)單元格的面積大小相似，無(wú)法突出細(xì)節(jié)，難以自適應(yīng)UDSM擁有多層次復(fù)雜度的網(wǎng)格。

首先計(jì)算每個(gè)單元格應(yīng)該分配到的質(zhì)量：

式中：n為目標(biāo)的單元格數(shù)量；ρj為每個(gè)頂點(diǎn)的密度。遍歷每個(gè)頂點(diǎn)，遍歷至頂點(diǎn)密度之和不小于Davg時(shí)，該遍歷周期的頂點(diǎn)構(gòu)成一個(gè)初始單元格，并開(kāi)始下一個(gè)遍歷周期，已經(jīng)被遍歷的頂點(diǎn)被稱為非自由點(diǎn)，重復(fù)這個(gè)過(guò)程，直到所有的頂點(diǎn)遍歷完成為止。當(dāng)所有頂點(diǎn)都變成非自由點(diǎn)時(shí)，離散數(shù)學(xué)的特征決定了單元格的數(shù)量必然沒(méi)能達(dá)到n個(gè)，并用2.2 章節(jié)的方法繼續(xù)構(gòu)造單元格。這種方法相對(duì)于勞埃德松弛法[13]，可實(shí)現(xiàn)高效率的構(gòu)建[14]。

為了使簡(jiǎn)化能調(diào)整局部單元格的數(shù)量，以自適應(yīng)地突出細(xì)節(jié)和簡(jiǎn)化平整區(qū)域ρj必然不是統(tǒng)一的值。利用多項(xiàng)式擬合[15]得到頂點(diǎn)的主曲率ka和kb，并且ρj需要同時(shí)考慮頂點(diǎn)的密集度，設(shè)fg為頂點(diǎn)Pj周?chē)乃腥蔷W(wǎng)格：

式中λ是曲率指標(biāo)，決定著網(wǎng)格曲率ρj和頂點(diǎn)密集度的敏感度。這個(gè)參數(shù)的設(shè)置于2.3 節(jié)重點(diǎn)研究。

2.2 初始化Voronoi 圖中心

引入二次誤差矩陣（ quadric error matrics,QEM）[10]，建立每個(gè)初始化的區(qū)域內(nèi)部頂點(diǎn)的QEM，借助QEM 得到折疊誤差，就是折疊點(diǎn)與相鄰面片所在平面的距離之和，選擇每個(gè)單元格中二次誤差最小的三角邊上的點(diǎn)作為中心點(diǎn)，使得每個(gè)頂點(diǎn)周?chē)娜沁叾紳M足初始化所定的數(shù)量指標(biāo)。確定中心點(diǎn)后將不再改變其位置，聚類(lèi)至增加新中心點(diǎn)并改變單元格的形狀。這樣聚類(lèi)過(guò)程能保持尖銳的細(xì)節(jié)(折疊誤差大)得到更好的保留，降低與原網(wǎng)格的誤差。這種后處理的方法[16]也驗(yàn)證了其性能。

2.3 網(wǎng)格重構(gòu)過(guò)程

確定了上文要素后，按照以下步驟進(jìn)行網(wǎng)格重構(gòu)：

1) 按照三維網(wǎng)格文件的頂點(diǎn)索引順序(相鄰的索引在模型中也是相鄰的頂點(diǎn))劃分中心點(diǎn)，當(dāng)遍歷的頂點(diǎn)的權(quán)之和大于Davg時(shí)分配一個(gè)中心點(diǎn)并進(jìn)入下個(gè)周期，直至遍歷完所有的頂點(diǎn)為止。按照離散離散CVD 的規(guī)則繪得初始Voronoi 圖。并確定每個(gè)Voronoi 單元的中心。

2) 按照Voronoi 圖中心的定義將QEM 得到的誤差大小對(duì)每個(gè)三角邊進(jìn)行最佳邊折疊點(diǎn)加入隊(duì)列，繼續(xù)以Davg作為閾值進(jìn)行遴選，折疊誤差從大到小排列。并且每選取一個(gè)中心點(diǎn)，該點(diǎn)與兩側(cè)的頂點(diǎn)要繼續(xù)進(jìn)行邊折疊，得到新的兩個(gè)折疊點(diǎn)按照大小順序插入到隊(duì)列中，直到中心點(diǎn)數(shù)量達(dá)到原網(wǎng)格頂點(diǎn)數(shù)量為止。

3) 按照離散CVD 的規(guī)則得到最終Voronoi 圖，按照文獻(xiàn)[6]的方法進(jìn)行構(gòu)網(wǎng)。除了每個(gè)單元的中心，Voronoi 單元的一些交會(huì)點(diǎn)也被歸為頂點(diǎn)重新進(jìn)行Delaunay 三角構(gòu)網(wǎng)。所以重構(gòu)UDSM 的頂點(diǎn)數(shù)量略大于原網(wǎng)格。

4) 按照簡(jiǎn)化率要求用QSlim 算法進(jìn)行簡(jiǎn)化。若不進(jìn)行這一步驟，直接按照簡(jiǎn)化率要求設(shè)置聚類(lèi)的Voronoi 單元數(shù)量，在實(shí)驗(yàn)中稱為CVD(2)。

3 曲率指標(biāo)的選擇

自由點(diǎn)的比例受曲率指標(biāo)λ的影響很大，而重新分配的自由點(diǎn)以QEM 計(jì)算的誤差作為標(biāo)準(zhǔn)。同QSlim 受到后來(lái)研究者指出的缺點(diǎn)一樣，雖然與原網(wǎng)格誤差小，但損失細(xì)節(jié)。如果自由點(diǎn)的比例過(guò)大，同樣的問(wèn)題也會(huì)出現(xiàn)。

λ如何影響自由頂點(diǎn)的比例，舉個(gè)簡(jiǎn)單的例子：假設(shè)5 個(gè)頂點(diǎn)的|Pi|分別為(1,2,3,4,5)，λ=0 時(shí)這5 個(gè)頂點(diǎn)按照上述規(guī)則初始可分為5 個(gè)子集((1)(2)(3)(4)(5))，自由點(diǎn)比例0；同理當(dāng)λ=1 時(shí)初始分為4 個(gè)子集，自由點(diǎn)比例0.2；當(dāng)λ=2 時(shí)初始分為3 個(gè)子集，自由點(diǎn)比例0.4。所以須對(duì)存在大量頂點(diǎn)的UDSM 選擇恰當(dāng)?shù)摩酥?，如圖2 所示。

圖2 質(zhì)心Voronoi 單元格的初始化與聚類(lèi)Fig.2 Initiation and clustering of centroidal Voronoi cells

圖2（a）（c）（e）斑駁的點(diǎn)就是自由點(diǎn)，隨著λ值的增加，自由點(diǎn)的比例增加，Voronoi 單元的初始化和最終聚類(lèi)結(jié)果的差別就越來(lái)越大，只有減少平整網(wǎng)格的面片數(shù)量真正減少才能更好地保持城市網(wǎng)格的構(gòu)造[17]。經(jīng)過(guò)觀察比較，λ=2 時(shí)平整網(wǎng)格的Voronoi 單元分布較為稀疏，下一章實(shí)驗(yàn)以λ=2 進(jìn)行實(shí)驗(yàn)。

4 實(shí)驗(yàn)與討論

實(shí)驗(yàn)采用2 個(gè)傾斜攝影三維重建構(gòu)造的UDSM。模型1 是大雁塔和其周?chē)恍∑瑓^(qū)域；模型2 是大連某商區(qū)。這2 個(gè)模型有個(gè)共同的特點(diǎn)：存在“假平面”。在簡(jiǎn)化率比較高的時(shí)候，很多網(wǎng)格重構(gòu)的簡(jiǎn)化方法會(huì)誤把有波動(dòng)但波動(dòng)幅度不大的區(qū)域簡(jiǎn)化成扁平區(qū)域，這個(gè)現(xiàn)象在CVD 聚類(lèi)簡(jiǎn)化中尤為嚴(yán)重。

但本文的方法將CVD 聚類(lèi)運(yùn)用在網(wǎng)格預(yù)處理這個(gè)步驟里，較大地克服了CVD 簡(jiǎn)化消耗時(shí)間過(guò)長(zhǎng)的缺陷。圖3 展示了大雁塔（頂點(diǎn)：81 821；面片：160 834）和大連某商區(qū)（頂點(diǎn)：55 816；面片：109 936）的UDSM，分別用QSlim[10]、ACVD[5]、CVD（2）和直接使用本文重構(gòu)算法進(jìn)行簡(jiǎn)化，利用Metro 工具[18]測(cè)量不同簡(jiǎn)化率簡(jiǎn)化結(jié)果的最大誤差、平均誤差和均方根誤差（單位為誤差值占對(duì)角線長(zhǎng)度的比例）：

總體上Metro 的測(cè)量結(jié)果QSlim 都比較好。由圖3 可以看出，最大誤差和均方根交錯(cuò)位置較多，無(wú)法準(zhǔn)確判斷出除了QSlim 算法的質(zhì)量，QSlim 的最大誤差基本都是最低的，這里也可以看出基于原網(wǎng)格的邊折疊在保持網(wǎng)格邊緣精度方面的優(yōu)勢(shì)。平均誤差本文算法與QSlim 是最接近的。

而這樣的“誤差”并非真正的誤差。一方面這是為了突出網(wǎng)格效果，使得簡(jiǎn)化后細(xì)節(jié)保留效果較好必須付出的代價(jià)；另一方面，三維重建構(gòu)造的UDSM 細(xì)節(jié)最少的是平整表面，為了保證其他細(xì)節(jié)的質(zhì)量，簡(jiǎn)化后的UDSM 更應(yīng)當(dāng)盡可能減少平整表面的網(wǎng)格數(shù)量。

圖4 展示UDSM 的原網(wǎng)格及其簡(jiǎn)化網(wǎng)格和本文方法重構(gòu)和簡(jiǎn)化后的效果(簡(jiǎn)化率為0.9)?？梢钥吹剑疚姆椒ê?jiǎn)化后與重構(gòu)網(wǎng)格相比UDSM 的平整表面變化很小，因此在LOD 漫游過(guò)程只有細(xì)節(jié)表面網(wǎng)格發(fā)生明顯變化。由于局部發(fā)生網(wǎng)格細(xì)分后再進(jìn)行的簡(jiǎn)化，誤差曲線中偶爾也會(huì)出現(xiàn)LOD 層誤差小于高一層的LOD 的情況(如圖3)。

圖3 簡(jiǎn)化誤差測(cè)量（上：大雁塔；下：大連某商區(qū)）Fig.3 Measurement of simplification error (up: Wild Goose Pagoda; down: a region of Dalian)

圖4 簡(jiǎn)化效果展示1（上：大雁塔；下：大連某商區(qū)）Fig.4 Display 1 of simplification results (up: Wild Goose Pagoda; down: a region of Dalian)

對(duì)比Voronoi 重構(gòu)前后進(jìn)行QSlim 的結(jié)果，可以發(fā)現(xiàn)整體上重構(gòu)后再進(jìn)行QSlim 簡(jiǎn)化視覺(jué)上網(wǎng)格的變化幅度明顯減少，這是平整表面簡(jiǎn)化后變化很小營(yíng)造的效果。圖4 的展示只能證明漫游時(shí)視覺(jué)效果優(yōu)良，除了這個(gè)方面，細(xì)節(jié)的保持也是重要的指標(biāo)。將大連某商區(qū)的UDSM 的面片數(shù)簡(jiǎn)化至2 000，并截取圖4（e）的黑框部分，得到圖5。使用CVD（2）算法也可以得到類(lèi)似圖4（c）（d）和圖4（g）（h）的LOD 效果。但從圖5 可以看到本文算法克服了基于Voronoi 圖的簡(jiǎn)化算法失真化平整波動(dòng)不大的細(xì)節(jié)網(wǎng)格，并且相對(duì)于QSlim 算法，屋頂?shù)妮喞玫礁玫谋３帧?/p>

圖5 簡(jiǎn)化效果展示2(上：大雁塔；下：大連某商區(qū))Fig.5 Display 2 of simplification results (up: Wild Goose Pagoda; down: a region of Dalian)

實(shí)驗(yàn)條件CPU 為i5-4210 m（主頻：2.60 Ghz），內(nèi)存為DDR3（8 G）。將本文算法與QSlim、ACVD和CVD（2），其中也將面片數(shù)為69 451 的bunny 模型加入進(jìn)行對(duì)比，簡(jiǎn)化率為0.9，結(jié)果如表1 所示。

表1 本文算法的時(shí)間性能對(duì)比Table 1 Time performance comparison for oursimplification method

由表1 可看出，由于細(xì)節(jié)網(wǎng)格復(fù)雜度和數(shù)量的輕微增加，本文算法耗時(shí)略微高于QSlim，可以認(rèn)為與QSlim 保持一致。QSlim 時(shí)間性能較好，在許多的研究中都有所體現(xiàn)。

5 結(jié)論

UDSM 的三維重建需要大量時(shí)間，而網(wǎng)格重構(gòu)的魯棒性強(qiáng)不需要隨著簡(jiǎn)化率變化而變化。本文融合了基于Voronoi 圖形的重構(gòu)簡(jiǎn)化算法保持網(wǎng)格細(xì)節(jié)特征，和QSlim 總體上與原網(wǎng)格誤差小的特點(diǎn)，得到了基于質(zhì)心Voronoi 圖重構(gòu)的UDSM 邊折疊簡(jiǎn)化，部分克服了Voronoi 平整失真的問(wèn)題。但網(wǎng)格重構(gòu)的過(guò)程中，雖然增加了細(xì)節(jié)區(qū)域的網(wǎng)格數(shù)量，但是細(xì)分過(guò)程中出現(xiàn)了建筑邊緣鈍化現(xiàn)象，可以通過(guò)簡(jiǎn)化率較低時(shí)使用QSlim 為代表的均勻簡(jiǎn)化構(gòu)建LOD。