基于圖論思想的山體特征線提取新方法及非真實(shí)感繪制

馮茜 饒思敏 朱晨曦

摘要 從DEM高程數(shù)據(jù)中提取山體特征線的技術(shù)在地形表示、工程設(shè)計、測繪等方面有著重要的意義。本文對現(xiàn)有的山脊線和山谷線提取算法進(jìn)行深入研究后，指出充分利用山體特征線的空間連續(xù)性和像素屬性連續(xù)性是正確且快速提取山體特征線的有效途徑。依照該思想本文設(shè)計出了一種基于圖論思想的山體特征線提取方法。該方法先利用DEM數(shù)據(jù)建立山體的三維模型，之后基于圖論思想，在DEM數(shù)據(jù)上間隔取點(diǎn)，作為圖的結(jié)點(diǎn)，生成最小生成樹，提取特征線。再將特征線覆蓋點(diǎn)沿同一方向平移，將特征線延展成面，進(jìn)行卡通風(fēng)格的二維紋理貼圖。實(shí)驗(yàn)證明，本文方法所提取的山體特征線與實(shí)際地形相符合。最后，對山體模型進(jìn)行非真實(shí)感繪制，利用光線向量與模型面片的法向量乘積和面片上點(diǎn)所示高度決定面片的顏色，并實(shí)現(xiàn)GPU加速的實(shí)時光照。

【關(guān)鍵詞】三維非真實(shí)感 圖論 最小生成樹山脊線

1 緒論

現(xiàn)有的球體軟件普遍用于GIS等領(lǐng)域，對于整體的地形地貌有良好的可視化效果。但由于可視化層次細(xì)節(jié)的要求，對于山脈山系等特定的區(qū)域，沒有針對性的可視化模式，也不能對某幾個特定的大尺度區(qū)域同時進(jìn)行增強(qiáng)可視化。

本文針對山系進(jìn)行非真實(shí)感可視化。根據(jù)DEM數(shù)據(jù)，利用圖論思想提取特征線。使用非真實(shí)著色。以達(dá)到突出特征、忽略不重要信息的非真實(shí)感繪制效果，呈現(xiàn)現(xiàn)實(shí)世界以及現(xiàn)有軟件所沒有的可視化效果，且呈現(xiàn)藝術(shù)性。成果可應(yīng)用于山系地理環(huán)境展示，地理知識科普，地理教學(xué)等。

2 山體特征線的提取

2.1 研究背景

從數(shù)字化地形資料中自動提取山脊線和山谷線的技術(shù)在地形表示、測繪、工程設(shè)計等方面有著重要的意義。目前，提取山脊線和山谷線主要有以下方法。

利用圖像處理技術(shù)提取地形特征：將規(guī)則格網(wǎng)DEM看作柵格圖像，而格網(wǎng)高程值可視為圖像像素值，再將圖像處理的相應(yīng)技術(shù)應(yīng)用于地形特征分析等問題，為了良好的解決問題，方莉[1]提出了灰度形態(tài)學(xué)算子提取山脊線和山谷線的新方法。該方法本身具有快速且高效的優(yōu)勢，但現(xiàn)有的方法中仍普遍存在的兩大問題，無法有效抑制噪聲、結(jié)果中存在大量的偽特征線，灰度形態(tài)學(xué)算子的計算具有一定的難度。

ChangY C等[2]提出的向剖面法提取地形線的算法，它充分利用山脊線和山谷線表現(xiàn)出來的幾何特征，設(shè)計了一種可調(diào)大小的分析窗口，對特征點(diǎn)進(jìn)行識別。其實(shí)質(zhì)是垂直剖面發(fā)的一種改進(jìn)，利用窗口掃描取代切面曲線上的曲率判別，避免了曲率判別時由于閩值分割引起的特征點(diǎn)遺漏，提高了算法效率，但效果與窗口尺度的選擇有關(guān)：當(dāng)選擇小窗口是，無法很好地抑制噪聲;當(dāng)窗口較大時，同樣會引起特征點(diǎn)的丟失。

流水模擬算法具體思想是將當(dāng)前格網(wǎng)八領(lǐng)域中高程下降最快的方向確定為水流方向以確定山谷線的走勢。Jenson S K，Domingue J0 [3]和EbnerH等[4]提出的多方向流水模擬法，具體思想是將當(dāng)前點(diǎn)的八領(lǐng)域內(nèi)所有格網(wǎng)的中心分別作為端點(diǎn)，形成八個三角形平面，然后分別出這八個平面中最大下降方向，然后將八領(lǐng)域方向中與下降方向最小的確定為流水方向。Martz L W.Garbrecht J[5]提出該方法具有較好的抗斷裂的特性，但是很容易受地形的影響，如在多洼地或較平坦的區(qū)域提取的結(jié)果會出現(xiàn)明顯的偏差。

靳海亮等[6]提出的等高線提取法：基于等高線數(shù)據(jù)的山脊線和山谷線的提取過程一般分為兩大步：

（1）地形特征點(diǎn)的確定;

（2）地形特征線（山脊線和山谷線）的連接。

其中第一步又包括兩步，其一為特征點(diǎn)提取算法，采用的是Split方法，其二是山脊點(diǎn)和山谷點(diǎn)識別算法。能夠有效地提取隱含在數(shù)字化地形中的山脊線和山谷線，與實(shí)際地形變化也是相符合的，具有較大的實(shí)際應(yīng)用價值。但是算法比較復(fù)雜，比較耗費(fèi)空間。

2.2 基于圖論思想的山體特征線提取算法

山脊線等高線表現(xiàn)為一凸向低處的曲線，高度是連續(xù)變化的，在DEM圖上的表現(xiàn)就是像素值連續(xù)變化且空間接近的線條。考慮到山脊線、山谷線的空間連續(xù)性和像素屬性連續(xù)性，本文創(chuàng)新的采用了圖論的思想來提取特征線。算法基本處理流程為：首先構(gòu)建基于原始DEM圖像的圖Graph。取一定間隔，對DEM灰度圖進(jìn)行采樣，將每個采樣點(diǎn)作為一個結(jié)點(diǎn)，在8鄰域方向構(gòu)建最小生成樹的連接關(guān)系。之后對圖Graph中各邊賦予權(quán)值。權(quán)值有兩種計算方式：

（1）基于高度賦值：邊的權(quán)值為兩個端點(diǎn)高度值和的1/2。

（2）“高度加權(quán)”與“曲度加權(quán)”混合賦值。

當(dāng)采樣點(diǎn)高度差別較小時，由于原始DEM圖像為8階灰度，只能提供0-255共256級分辨率。單純地利用高度加權(quán)方法可能會導(dǎo)致圖中出現(xiàn)大量權(quán)重相同的邊，從而使得最小生成樹分支在方向上出現(xiàn)不可控現(xiàn)象。為避免這一問題，RJ Blakely等[7]提出了一種結(jié)合梯度加權(quán)的方式，將采樣點(diǎn)權(quán)值分為高程值與梯度加權(quán)值兩部分，從而拉伸其取值區(qū)間。

在空間上，最小生成樹普遍采用的鄰接表法和鄰接矩陣方法生成最小生成樹會耗費(fèi)大量空間。而且由于本文實(shí)現(xiàn)的是大范圍的三維繪制，若采用固有方法需要開辟的空間過大，會造成內(nèi)存溢出，并不適用。故改變了算法的存儲結(jié)構(gòu)，由于山脊線在現(xiàn)實(shí)空間中是連貫的，所以每次尋找下一個結(jié)點(diǎn)只需在8鄰域范圍內(nèi)進(jìn)行遍歷，每個結(jié)點(diǎn)也只需存儲鄰域內(nèi)8個結(jié)點(diǎn)的信息和其他必要信息，采用樹形結(jié)構(gòu)存儲結(jié)點(diǎn)信息，大大減小了時間和空間損耗。如圖1所示。

2.3 實(shí)現(xiàn)和結(jié)果

基于圖論思想的山體特征線提取算法能自動、準(zhǔn)確的提取DEM格式圖像中山脊線和山谷線。但是由于8鄰域的方向限制，又是離散式取點(diǎn)，提取出的山脊線會出現(xiàn)大量的45度、90度或135度的不自然的“鋸齒”，所以該方法的后續(xù)需要進(jìn)行平滑處理。

3 山體模型的非真實(shí)感繪制

3.1 研究背景

非真實(shí)感繪制（NPR）屬于計算機(jī)圖形學(xué)中的一類，自20世紀(jì)90年代中期開始，NPR逐漸成為計算機(jī)圖形學(xué)的研究熱點(diǎn)之一。NPR是指利用計算機(jī)生成不具有照片般真實(shí)感，而能表現(xiàn)圖形的藝術(shù)特質(zhì)或作為真實(shí)感有效補(bǔ)充的圖形。主要用于模擬藝術(shù)式的繪制風(fēng)格，也用于發(fā)展新繪制風(fēng)格。本文的卡通風(fēng)格的山體非真實(shí)感繪制，能有效地去除不重要的信息，強(qiáng)調(diào)、突出山體的形態(tài)特征。

3.2 特征線風(fēng)格化和山體模型非真實(shí)感繪制算法

前文中標(biāo)定的特征線是一維圖形，不能進(jìn)行卡通風(fēng)格的二維紋理貼圖。需要將特征線覆蓋的數(shù)據(jù)點(diǎn)向同一方向平移，將特征線擴(kuò)展為一個小平面，之后再進(jìn)行貼圖。由于之前取一定間隔采樣，不會導(dǎo)致貼圖區(qū)域過大。如圖2所示。

三維非真實(shí)感繪制。本文實(shí)現(xiàn)三維非真實(shí)感效果利用非真實(shí)感著色，主要運(yùn)用一種基于漫反射模型的著色方法。對于不同海拔、不同地貌的山系區(qū)域，光照產(chǎn)生的陰面和陽面采用不同顏色、線條等表現(xiàn)形式。通過頂點(diǎn)法向量和光線向量的點(diǎn)乘結(jié)果作為紋理坐標(biāo)來訪問一維紋理，從而確定該點(diǎn)的顏色信息，向陽面亮度高，背陰面亮度低，使模型表面表現(xiàn)出跳變的明暗過渡，體現(xiàn)卡通風(fēng)格。再對不同地貌的區(qū)域不同著色。較高的山頂采用明暗不同的灰白色，山體中部采用黃色，山體底部采用綠色。將圖像分割成三角形，把三角形規(guī)格化，再對這些規(guī)格化后小三角形著色，原圖像的每個候選點(diǎn)對象占據(jù)一個三角形、使用全等三角形的顏色均值作為該點(diǎn)的顏色。

實(shí)時光照。光線位置隨攝像機(jī)位置移動，每次畫面刷新時更新光照位置，從而改變模型每個面片的色彩亮度，實(shí)現(xiàn)實(shí)時光照。在攝像機(jī)連續(xù)移動時，有光線變幻的效果。如圖3所示。

加速繪制。為了提升生成圖像的顯示速度，本項(xiàng)目對繪制算法加速和優(yōu)化，利用了GPU加速，從而為用戶帶來更好的視覺體驗(yàn)。

3.3 實(shí)現(xiàn)和結(jié)果

根據(jù)繪制結(jié)果發(fā)現(xiàn)，不同的著色等級之間會出現(xiàn)突然的過渡，符合卡通渲染的色塊化渲染特性。很好地體現(xiàn)了山系的形態(tài)。

4 總結(jié)與展望

本文實(shí)現(xiàn)了喜馬拉雅山系的非真實(shí)感繪制效果，突出強(qiáng)調(diào)了山體的特征線，通過光照和非真實(shí)感著色能較好的反映出山體的特征。并且提出了借助圖論思想提取山體特征線的新方法。

目前，提取特征線時所取間隔需要根據(jù)數(shù)據(jù)人為確定，希望能應(yīng)用圖像處理技術(shù)或者機(jī)器學(xué)習(xí)技術(shù)自動確定間隔，使特征線提取工作達(dá)到時間和精確度上最優(yōu)。同時，希望能用更多兼具科學(xué)和藝術(shù)的表現(xiàn)形式表現(xiàn)山系。

參考文獻(xiàn)

[1]方莉，利用圖像處理技術(shù)提取地形特征線的方法研究[D].西安建筑科技大學(xué)，2011.

[2] Chang Y C， Song G S，Hsu SK. Automatic Extraction of Ridgeand Valley Axes Using the ProfileRecognition and PolygonbreakingAlgorithm [J]. Computers andGeosciences，1998，24 （01）.

[3] Jenson S K，Domingue J 0，ExtractingTopographic Structure from DigitalElevation Data for GeographicInformation System Analysis.Photogrammetry Engineering andRemote Sensing， 1988.

[4]Ebner H，Reinhardt W，H osslerR. Generztion，Management andUtilization of High FidelityDigital Terrain model [J].Photogrammetry and RemoteSens ing， 1988， 27B（II/III）：556-566.

[5] Martz L W，Garbrecht J.NumericalDefinition of Drainage Network andSubcatchment Areas from DigitalElevation Models [J]. Computers andGeosciences，1992，18 （06）.

[6]靳海亮，康建榮，高井祥，利用等高線數(shù)據(jù)提取山脊（谷）線算法研究[J]，武漢大學(xué)學(xué)報信息科學(xué)版，2005， 30 （09）.

[7]RJ Blakely，RW Simpson， RS Pawlowski.Approximating edges of sourcebodies from magnetic or gravityanomalies [J].