基于輪廓草圖的三維地形建模方法研究

徐　勇　馬　燕　康建成

1(上海師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系　上海 200234)2(上海師范大學(xué)地理系　上海 200234)

?

基于輪廓草圖的三維地形建模方法研究

徐勇1馬燕1康建成2

1(上海師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系上海 200234)2(上海師范大學(xué)地理系上海 200234)

針對(duì)傳統(tǒng)的三維地形建模耗時(shí)、提取特征值困難以及建模效果不佳的特點(diǎn)，提出基于輪廓草圖的三維地形建模的改良方法。系統(tǒng)通過(guò)道格拉斯-普克算法分析輪廓的幾何特性，使用高斯高通濾波器對(duì)重構(gòu)出三維地形進(jìn)行去噪。實(shí)驗(yàn)結(jié)果表明該方法生成的三維地形模型有良好的可視化效果，也驗(yàn)證了道格拉斯-普克算法適合于分析勾勒、分解和重構(gòu)輪廓，高斯高通濾波器對(duì)地形的平滑有良好的效果。

地形建模道格拉斯-普克算法數(shù)字高度圖

0　引　言

在計(jì)算機(jī)圖形學(xué)、虛擬現(xiàn)實(shí)以及三維可視化技術(shù)等領(lǐng)域[1]，許多學(xué)者正為找出更加逼真的三維地形建模系統(tǒng)[2]而努力。與二維平面地形相比，三維地形可以將繁雜地理數(shù)據(jù)及其分析結(jié)果數(shù)字化，成為用戶能夠直觀理解的信息，在此基礎(chǔ)上進(jìn)行地理信息顯示和空間分析。我們都在思考：怎樣根據(jù)視點(diǎn)的變化與漫游的需要來(lái)實(shí)時(shí)模擬地形的各種形態(tài)？

現(xiàn)有的建模技術(shù)大致上可以分為兩類，一是使用傳統(tǒng)的3D建模工具，如Blender、Maya和3DMAX；二是分形方法。前一類方法為用戶提供了一個(gè)能夠控制地形外觀的建模方法，但耗時(shí)長(zhǎng)、速度緩慢，要求用戶具有較強(qiáng)的圖形知識(shí)和編程能力，沒(méi)有圖形學(xué)經(jīng)驗(yàn)的用戶很難用這類方法實(shí)現(xiàn)建模。相比之下，后一類方法是自動(dòng)完成的，耗時(shí)短、速度較快，但它存在一個(gè)致命問(wèn)題，即用戶無(wú)法控制最后生成的地形效果。綜上所述，這兩類建模工具都要求用戶具備較強(qiáng)的編程能力，所以它們不適合一般用戶。因此先前的研究者們把以上述兩類方法的優(yōu)點(diǎn)加以結(jié)合，提出基于草圖的三維建模方法。

基于草圖方法[3]的三維地形建模在電腦游戲和電影領(lǐng)域使用頻繁。在先前的研究中，有圖形研究小組開(kāi)發(fā)了一個(gè)基于草圖與等高線[4]的地形模型，它使用繪畫方法。這種模型對(duì)普通用戶而言易于使用，且生成三維地形的可視化效果也較好，但缺乏反映地形詳細(xì)特征的能力，如平滑的丘陵或崎嶇蜿蜒的山脈。這種基于手繪草圖[5]的地形模型不能很好地描繪地形形狀，所以生成的三維地形模型缺乏準(zhǔn)確性和真實(shí)性。

為了使建模工具能反映更詳細(xì)的三維地形信息，通過(guò)對(duì)上述方法的研究與分析，本文提出一種新的基于輪廓草圖的三維地形建模方法。該方法需要用戶描繪某個(gè)地形的部分輪廓，然后自動(dòng)分析輪廓與地形的哪些部分匹配，分析出的輪廓的幾何特性，并根據(jù)相應(yīng)的地形作出修正，通過(guò)道格拉斯-普克算法提取輪廓的幾何特性。該建模方法的目的是為沒(méi)有圖形學(xué)經(jīng)驗(yàn)的用戶提供最后生成結(jié)果的可控性。此方法同時(shí)具有耗時(shí)短、速度快的優(yōu)點(diǎn)，能較逼真地反映三維地形[6]模型。

1　基于輪廓草圖的三維地形建模方法

1.1設(shè)計(jì)概述

首先簡(jiǎn)單介紹下早期基于草圖輪廓的三維地形建模，如圖1所示，當(dāng)用戶輸入簡(jiǎn)單輪廓與箭頭后(圖1上左)；系統(tǒng)使用幾組特定算法來(lái)分析輪廓與箭頭，取得它們的主要特征(圖1上中)；在人機(jī)交互界面生成匹配的高程值(圖1上右)；最后生成三維地形模型[7](圖1下)，而我們發(fā)現(xiàn)這種匹配出三維地形可視化程度很低。

圖1　早期基于草圖輪廓的三維地形建模

我們的設(shè)計(jì)理念是新的基于輪廓草圖的建模方法能獲得輪廓與地形區(qū)域高度匹配的效果。

因此，系統(tǒng)需要滿足以下的設(shè)計(jì)要求：

(1) 能讓用戶特別是對(duì)于沒(méi)有經(jīng)驗(yàn)的用戶繪制一個(gè)輪廓。

(2) 可以識(shí)別和區(qū)分不同的輪廓，檢測(cè)正確的等高線域，每個(gè)輪廓構(gòu)造不同的三維地形模型。

(3) 應(yīng)用一些算法來(lái)分析的輪廓，以獲得重要的特征信息。整合這些信息，計(jì)算并重構(gòu)出三維地形模型的功能。

(4) 當(dāng)用戶不滿意他勾畫的地形時(shí)，輪廓可以進(jìn)行修改并在人機(jī)交互界面上重新勾畫。

(5) 生成地三維地形模型具有與用戶輸入的草圖有高度的相似性，匹配性好。輪廓的所有主要特征應(yīng)該顯示在三維地形模型中。

(6) 提供一個(gè)3D窗口觀察，從不同的角度研究三維地形模型。

為滿足上述要求，我們創(chuàng)建二維草圖窗口[8]的用戶界面來(lái)方便用戶勾畫一個(gè)二維的輪廓。

1.2使用道格拉斯-普克算法來(lái)提取草圖信息

目前有很多適合于分析與匹配輪廓的技術(shù)，其中大多都包括大量的數(shù)學(xué)公式與相關(guān)幾何的科學(xué)。我們?cè)趯?shí)驗(yàn)中發(fā)現(xiàn)基于道格拉斯-普克算法更適合用于識(shí)別輪廓[9]的主要特點(diǎn)。通過(guò)迭代使用道格拉斯-普克算法，我們能得到大部分需要的信息。

在項(xiàng)目實(shí)現(xiàn)的過(guò)程中，為了創(chuàng)建逼真的地形的三維模型[10]，我們打算找出一些更有效的函數(shù)來(lái)重建草圖，包括輪廓的主要特征值，最好是在程序的運(yùn)行過(guò)程中添加的隨機(jī)峰，但是添加的隨機(jī)峰又不能損失過(guò)多的資源，包括運(yùn)行時(shí)間與影響輪廓匹配的相似度。于是在項(xiàng)目中系統(tǒng)引入了地形的平滑函數(shù)，無(wú)論是隨機(jī)值和函數(shù)都應(yīng)該受到標(biāo)準(zhǔn)偏差的約束。由于時(shí)間不足以及能力有限，一些要求在本系統(tǒng)中還沒(méi)有實(shí)現(xiàn)。

1.3使用包圍盒來(lái)識(shí)別草圖

本文使用的包圍盒算法識(shí)別草圖的運(yùn)行情況如下：

(1) 連接草圖上起點(diǎn)A和終點(diǎn)B。起點(diǎn)和終點(diǎn)AB之間的距離作為包圍盒的寬度。

(2) 找到與C點(diǎn)距離最長(zhǎng)的點(diǎn)(CD)垂直于草圖上直線AB。

(3) 計(jì)算AB與CD的長(zhǎng)度比值。

(4) 根據(jù)該比率，我們把草圖分成不同的組。

正如說(shuō)明所述，AB連接作為基準(zhǔn)線和從草圖最遠(yuǎn)的點(diǎn)C點(diǎn)到AB上的D點(diǎn)。比例是通過(guò)使用AB/CD的比率計(jì)算。

1.4使用道格拉斯-普克算法分析輪廓

輪廓一旦可被識(shí)別，接下來(lái)就是分析輪廓，確定的輪廓所包含的信息。例如提取出輪廓包含的峰和谷的數(shù)目等。程序需要用戶指定最高峰以及最低盆地的位置。當(dāng)系統(tǒng)分析完輪廓后，我們便得到輪廓的主要特征。算法接著調(diào)用插值函數(shù)用于進(jìn)一步分析，目的是為了把輪廓信息轉(zhuǎn)換成不同形式的信號(hào)，對(duì)信號(hào)最常用的分析工具就是快速傅立葉變換和離散小波變換，在本文中，我們使用了道格拉斯-普克算法[11]，可能不大常見(jiàn)，但我們使用效果卻很理想。道格拉斯-普克算法可以去除噪聲并且不改變輪廓線的主要特征值。與FFT和DWT相比，道格拉斯-普克算法更適合于非周期信號(hào)的分析和重建。道格拉斯-普克算法可以分解不同層次的細(xì)節(jié)特征。系統(tǒng)使用這些數(shù)據(jù)來(lái)表現(xiàn)的輪廓的幾何形狀，重構(gòu)與之相匹配的幾何性質(zhì)2D地形，算法得出的結(jié)果滿足我們的要求。

如圖2所示，為了分解輪廓在不同高程上的細(xì)節(jié)，我們迭代利用道格拉斯-普克算法分析輪廓，首先我們?nèi)〉镁嚯x基準(zhǔn)線的最大距離的點(diǎn)，基準(zhǔn)線被定義為一條直線，它是輪廓線起點(diǎn)到終點(diǎn)，這個(gè)最大距離是可被認(rèn)為輪廓第一個(gè)確定的層次屬性。接下來(lái)，我們利用道格拉斯-普克算法的ε值等于最大距離的一半獲取更多輪廓屬性。每次調(diào)用的道格拉斯-普克算法時(shí)，ε值降低為原來(lái)的ε值的一半，以此遞推。

圖2　使用道格拉斯-普克算法來(lái)分析輪廓的例子

1.5偵測(cè)輪廓域

有兩種方法來(lái)偵測(cè)出某個(gè)特定區(qū)域來(lái)調(diào)用這樣的重建函數(shù)，一是讓用戶預(yù)先定義使用區(qū)域；二是系統(tǒng)基于輪廓線域自動(dòng)調(diào)用重建函數(shù)。如采用第一種方法，必須讓用戶繪制出另一張草圖來(lái)指示出使用區(qū)域，但添加新草圖的做法會(huì)導(dǎo)致與原始輪廓線產(chǎn)生沖突，系統(tǒng)無(wú)法分辨到底那張草圖是原始輸入的草圖，因此本文中選取第二種方法。

通常情況下，當(dāng)與用戶輸入一條輪廓線后，這條輪廓線是一段連續(xù)的曲線[12]，我們可以認(rèn)為它有多段峰谷組成，輪廓線也存在極值點(diǎn)，極值點(diǎn)滿足兩個(gè)條件：

(1) 不存在其他輪廓線比它的最高點(diǎn)更高。

(2) 不存在其他輪廓線比它的最低點(diǎn)更低。

如果存在一條輪廓線滿足上述兩個(gè)條件之一，我們把它定義為一條極值線。系統(tǒng)被設(shè)計(jì)為讓用戶來(lái)預(yù)定義哪些輪廓線區(qū)域適用重構(gòu)函數(shù)，因此文章構(gòu)思了一個(gè)簡(jiǎn)單的方法來(lái)滿足要求。

如圖3所示：首先我們建立由輪廓起點(diǎn)和終點(diǎn)的連接線為基線，顯然我們發(fā)現(xiàn)了基準(zhǔn)線與輪廓線相交，于是本文定于與基線相交的區(qū)域?yàn)檎{(diào)用重建函數(shù)區(qū)域。當(dāng)然，如果系統(tǒng)可直接自動(dòng)識(shí)別出了相交域，這樣調(diào)用重建函數(shù)就會(huì)更方便。

為了證實(shí)是外部輪廓線，我們給定三個(gè)步驟來(lái)考慮。第一步是計(jì)算出輪廓線與基準(zhǔn)線相交后的交點(diǎn)。第二步是計(jì)算兩個(gè)交點(diǎn)之間的距離。第三步是找到兩個(gè)交叉點(diǎn)之間的最大距離。

圖3　例輪廓線與基準(zhǔn)線相交

1.6與其他項(xiàng)目比較

圖4是早期通過(guò)使用基于草圖的三維地形建模技術(shù)[13]生成地三維地形模型簡(jiǎn)單粗糙，原本應(yīng)該是陡峭山脈的地方幾乎與盤山公路在同一個(gè)平面上。

與基于草圖的地形模型相比，本文讓用戶繪制地形的輪廓，該系統(tǒng)自動(dòng)分析該輪廓和它的幾何性質(zhì)，確定地形區(qū)域。生成了光滑的山丘，與輪廓相對(duì)應(yīng)的地形高度相似，構(gòu)造了較好的三維地形模型，創(chuàng)建了一個(gè)更加逼真的山峰而不是一個(gè)平面[14]。

圖4　兩個(gè)結(jié)果的例子，基于草圖的地形模型(上3幅)，本文(下2幅)

1.7不使用高斯高通濾波器

項(xiàng)目的實(shí)現(xiàn)過(guò)程中發(fā)現(xiàn)一個(gè)有意思的問(wèn)題，如果不使用高斯高通濾波器[15]，生成的三維是不逼真的，可視化程度較差。以圖5作為舉例說(shuō)明。三維地形在Y軸出現(xiàn)了多個(gè)意想不到的山峰與山谷，這些峰谷的出現(xiàn)才有機(jī)會(huì)讓高斯高通濾波大顯身手，這是在本文先前設(shè)計(jì)時(shí)沒(méi)有考慮到的。

產(chǎn)生如圖5所示的糟糕結(jié)果的原因在于：有些像素在系統(tǒng)應(yīng)用重構(gòu)函數(shù)的時(shí)候沒(méi)有被修改為理想的高程值，在重構(gòu)時(shí)以原值的形式重新運(yùn)用到了3D地形建模中，與它相鄰已經(jīng)被修改的像素之間產(chǎn)生了非常大的差異。當(dāng)用戶從不同的角度觀察生成的地形時(shí)，三維地形模型中出現(xiàn)了多個(gè)峰谷。

圖5　意外出現(xiàn)的山谷

1.8最后的結(jié)果

當(dāng)系統(tǒng)調(diào)用了輪廓線重構(gòu)函數(shù)后，會(huì)重新生成用于渲染3D地形模型的數(shù)字高度圖。由于保存在數(shù)組中的高程值并不是一組連續(xù)的值，所以系統(tǒng)調(diào)用高程值后，應(yīng)該使用高斯高通濾波器去剔除與相鄰像素有較大差異的高程值，舍去低頻信號(hào)，創(chuàng)建出平滑的地形。

如圖6所示，該系統(tǒng)允許用戶通過(guò)二維的窗口繪制輪廓。這個(gè)輪廓由程序自動(dòng)識(shí)別。然后我們按照不同細(xì)節(jié)將輪廓分解成不同高程。該系統(tǒng)用這些層次采集的特征值來(lái)來(lái)重構(gòu)與之等效的幾何性質(zhì)，創(chuàng)建出二維地形。接下來(lái)系統(tǒng)會(huì)判斷能夠反應(yīng)這個(gè)輪廓的地形區(qū)域，并調(diào)用重構(gòu)函數(shù)到這個(gè)區(qū)域中。在很短的時(shí)間里，系統(tǒng)就重建了高相似度的三維地形模型。輪廓的主要屬性很都能在形成的三維地形中反應(yīng)出來(lái)。

圖6　2D草圖窗口(左上)，其他圖為從不同角度觀察的三維地形

實(shí)驗(yàn)中還發(fā)現(xiàn)高斯高通濾波功能存在缺陷：一是系統(tǒng)如果要調(diào)用高斯高通函數(shù)，必須先建立一個(gè)二維數(shù)組來(lái)存儲(chǔ)原始高程值，然后還需要設(shè)計(jì)另一組二維數(shù)組來(lái)存儲(chǔ)已被修正過(guò)的高程值，便于系統(tǒng)對(duì)這些值進(jìn)行濾波去噪，這占用了大量計(jì)算機(jī)內(nèi)存，減慢系統(tǒng)運(yùn)行時(shí)間，所以要注意存儲(chǔ)器分配，以免產(chǎn)生存儲(chǔ)沖突。二是生成的三維地形由于濾波損失了部分精度，某些主要的特征值會(huì)得不到很好的重構(gòu)。

2　結(jié)　語(yǔ)

輪廓在基于草圖的地形建模中是一項(xiàng)令人興奮的技術(shù)。特

別是在電腦游戲和計(jì)算機(jī)圖形學(xué)領(lǐng)域。這個(gè)程序給用戶提供了一把鑰匙，用戶只需勾畫二維的草圖就可以得出三維的地形。

本文中，首先提出了一系列的算法對(duì)草圖進(jìn)行分析，并對(duì)這些算法做了簡(jiǎn)要介紹，隨后提出了一種新方法來(lái)分析復(fù)雜的和非周期性輪廓。后來(lái)，我們驗(yàn)證了道格拉斯-普克算法[13]可以分解和重構(gòu)輪廓。我們把輪廓的細(xì)節(jié)按照不同的高程來(lái)分解，使用這些層次來(lái)反映的輪廓的幾何形狀，并通過(guò)調(diào)用函數(shù)來(lái)采集輪廓的二維信息。最后，本文證明了高斯高通濾波器適用于創(chuàng)造平滑的地形模型。本文中利用此濾波器替換不合理的高程值，移除了意想不到的山谷。

在未來(lái)，我們希望實(shí)現(xiàn)3D建模更加真實(shí)，匹配程度更高。讓這項(xiàng)技術(shù)在電腦游戲、視景仿真、地理、氣象和軍事發(fā)揮更大的作用。當(dāng)用戶輸入草圖后，系統(tǒng)能完全匹配的輪廓區(qū)域，高程值也不會(huì)損失，實(shí)現(xiàn)完美匹配。

[1] 郭濤，平西建. 基于OpenGL的三維地形可視化技術(shù)研究[J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2008(1)：193-196.

[2] 韓紅波. 基于手繪草圖三維建模方法研究[D]. 南京航空大學(xué)， 2008.

[3]ZeleznikRobertc，HerndonKennethP，HughesJohnF.SKETCH：aninterfaceforsketching3Dscenes[C]//ComputerGraphicsProceedings，AnnualConferenceSeries，ACMSIGGRAPH，NewOrleans，1996：161-170.

[4]IgarashiT,MatsuokaS,TanakaH.Teddy:Asketchinginterfacefor3Dfreeformdesign[C]//ComputerGraphicsProceedings,AnnualConferenceSeries,ACMSIGGRAPH,LosAngeles,California,1999:409-416.

[5] 孫正興，馮桂煥，周若鴻．基于草圖的人機(jī)交互技術(shù)研究進(jìn)展[J]．計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2005，17(9)：1889-1899.

[6]QinSF,WrightDK，JordanovIN.Fromon-linesketchto2Dand3Dgeometry:Asystembasedonfuzzyknowledge[J].ComputerAidedDesign,2000，32(14)：851-866.

[7]CherlinJosephJ，F(xiàn)aramarzSamavati，MarioC．Sousa，etal.Sketch-basedmodelingwithfewstrokes[C]//ProceedingsoftheSpringConferenceonComputerGraphics(SCCG’05)，Budmerice，2005：1-9.

[8]HartsonRH，HixD.Human-ComputerInterfaceDevelopment：ConceptsandSystemsforItsManagement[J].ACMComputingSurveys，1989,21(1)：5-92.

[9]CohenJM，HughesJF，ZeleznikRC.Harold:aworldmadeofdrawings[J].ProceedingsoftheFirstInternationalSymposiumonNonPhotorealisticAnimation&Rendering,2000：83-90.

[10] 周煒，董福安，吉楠. 基于分形和高度圖控制的三維地形生成技術(shù)研究[J]. 電光與控制，2007,14(7)：66-71.

[11]DouglasDH，PeuckerT.Algorithmsforthereductionofthenumberofpointsrequiredtorepresentadigitizedlineoritscaricature[J].TheCanadianCartographer，1973，10(2)：112-122.

[12] 雷海峰. 基于DEM的地形信息提取及運(yùn)用[D]. 成都理工大學(xué)， 2012.

[13]DouglasPeucker.Ramer-Douglas-Peuckeralgorithm[DB/OL]. [2010-2-2].http：//en.wikipedia.org/wiki/Ramer-Douglas-Peuckeralgorithm.

[14] 伍燕萍. 基于圖像的三維重建[D]. 北京交通大學(xué)，2009.

[15] 謝勤嵐. 圖像降噪的自適應(yīng)高斯平滑濾波器[J]. 計(jì)算機(jī)工程與應(yīng)用，2009(16)：182-186.

RESEARCHONCONTOURSKETCH-BASED3DTERRAINMODELLINGMETHOD

XuYong1MaYan1KangJiancheng2

1(Department of Computer Science and Technology,Shanghai Normal University,Shanghai 200234,China)2(Department of Geography,Shanghai Normal University,Shanghai 200234,China)

Aimingattraditional3Dterrainmodellingcharacteristicssuchastimeconsuming,difficultineigenvalueextractionandpoormodellingeffect,weputforwardthecontoursketch-basedimprovedmethodfor3Dterrainmodelling.ThesystemanalysesthegeometriccharacteristicsofcontourwithDouglas-Peuckeralgorithm,anddenoisesthereconstructed3DterrainwithGausshigh-passfilter.Experimentalresultsshowedthatthe3Dterrainmodelgeneratedbythismethodhadgoodvisualisationeffect,andprovedaswellthattheDouglas-Peuckeralgorithmissuitablefortheanalysisofoutlining,decomposingandreconstructingcontour,andthatGausshigh-passfilterhasgoodeffectonterrainsmoothing.

TerrainmodellingDouglas-PeuckeralgorithmDigitalelevationmap

2014-10-18。徐勇，助理工程師，主研領(lǐng)域：圖形學(xué)。馬燕，教授。康建成，教授。

TP3

ADOI:10.3969/j.issn.1000-386x.2016.03.028