基于图论思想的山体特征线提取新方法及非真实感绘制

冯茜 饶思敏 朱晨曦

摘要 从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].