馮茜 饒思敏 朱晨曦

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

【關鍵詞】三維非真實感 圖論 最小生成樹山脊線

1 緒論

現有的球體軟件普遍用于GIS等領域，對于整體的地形地貌有良好的可視化效果。但由于可視化層次細節的要求，對于山脈山系等特定的區域，沒有針對性的可視化模式，也不能對某幾個特定的大尺度區域同時進行增強可視化。

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

2 山體特征線的提取

2.1 研究背景

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

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

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

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

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

（1）地形特征點的確定;

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

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

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

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

（1）基于高度賦值：邊的權值為兩個端點高度值和的1/2。

（2）“高度加權”與“曲度加權”混合賦值。

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

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

2.3 實現和結果

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

3 山體模型的非真實感繪制

3.1 研究背景

非真實感繪制（NPR）屬于計算機圖形學中的一類，自20世紀90年代中期開始，NPR逐漸成為計算機圖形學的研究熱點之一。NPR是指利用計算機生成不具有照片般真實感，而能表現圖形的藝術特質或作為真實感有效補充的圖形。主要用于模擬藝術式的繪制風格，也用于發展新繪制風格。本文的卡通風格的山體非真實感繪制，能有效地去除不重要的信息，強調、突出山體的形態特征。

3.2 特征線風格化和山體模型非真實感繪制算法

前文中標定的特征線是一維圖形，不能進行卡通風格的二維紋理貼圖。需要將特征線覆蓋的數據點向同一方向平移，將特征線擴展為一個小平面，之后再進行貼圖。由于之前取一定間隔采樣，不會導致貼圖區域過大。如圖2所示。

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

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

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

3.3 實現和結果

根據繪制結果發現，不同的著色等級之間會出現突然的過渡，符合卡通渲染的色塊化渲染特性。很好地體現了山系的形態。

4 總結與展望

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

目前，提取特征線時所取間隔需要根據數據人為確定，希望能應用圖像處理技術或者機器學習技術自動確定間隔，使特征線提取工作達到時間和精確度上最優。同時，希望能用更多兼具科學和藝術的表現形式表現山系。

參考文獻

[1]方莉，利用圖像處理技術提取地形特征線的方法研究[D].西安建筑科技大學，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]靳海亮，康建榮，高井祥，利用等高線數據提取山脊（谷）線算法研究[J]，武漢大學學報信息科學版，2005， 30 （09）.

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