一种面向地形可视性分析的可视性图网络构建方法

摘要

本发明提供了一种面向地形可视性分析的可视性图网络构建方法。该方法包括：(1)对DEM格网数据进行扫描，分析是否存在空数据，若存在，进行插值计算，补充数据；(2)选择构建图网络的DEM格网单元邻近模式，模式类型包括4格网单元邻近模式、8格网单元邻近模式和16格网单元邻近模式；(3)计算可视图网络中顶点的属性值：结合可视域分析算法，计算网络中每个顶点对应的格网单元的可视的格网点数目或可视域面积大小；(4)根据选择的邻近模式类型，计算可视图网络中边的权值；(5)保存可视图网络数据。本发明完全可应用于大规模海量数据的地形可视性分析的不同领域的基于图网络的优化建模与求解方面，能够提高处理效率。

说明书

技术领域

本发明属于数字地形分析的可视性分析技术领域，涉及利用规则格网模型的DEM数据转换成以图论为基础的可视图网络转换方法的实现，进而为基于可视图网络模型的可视性分析与应用打下基础。

背景技术

数字地形分析(Digital Terrain Analysis，简称DTA)是在数字高程模型(Digital Elevation Model，简称DEM)的基础上进行地形属性计算和特征提取的数字信息处理技术。可视性分析是数字地形分析的重要地形分析因子，包括通视性分析和可视域分析。可视域分析又称地形通视分析，指的是从单个或者多个地理位置所能看到的地形范围或者与其他地理位置之间的可见程度，是数字地形分析中的不可缺少的一部分。地形可视域分析在很多相关领域都有比较重要的意义，已经成为景观分析与评估、建筑规划、军事、空间认知与决策、考古等领域的重要研究手段。

DEM模型是一种场模型，包括规则格网(Regular Square Grid，简称RSG)模型和不规则三角形网(Triangulated Irregular Network，简称TIN)模型。由于可视性分析及其应用都是基于DEM进行分析，这些应用顾及可视性特征建立各种优化模型，而建立在DEM模型上的优化模型无论是在建模方面，还是在模型求解方面都是比较复杂的，且面向海量DEM数据的应用算法的求解速度无法有效提高，即使采用并行计算技术，但这些应用中所涉及的数据具有依赖特性，而无法通过并行化手段提高计算的效率。

一方面，DEM模型反映的是地形的高程数据，而无法表达地形上观察点与目标点之间的关系，需要通过应用进行解析。如果将DEM模型转换成一种基于图论的图网络模型，为顾及可视性特征的各种地理应用建模带来极大的便利，并为地形可视性分析与应用建立新的理论基础和工具。另一方面，随着各种新型传感器以及测量技术的出现，DEM数据呈级数增长，从而导致单机环境下对大规模的数据进行处理是一件十分困难的事情。因此，基于图网络模型的大图数据可以采用并行计算技术提高数据处理的效率。

在基于栅格DEM数据表示的数字地形表面上，每个格网单元可以看作是一个节点，格网单元之间的关系(比如距离、高程差等)可以描述为具有权值的边，从而将规则格网单元组成的具有2.5维的数字高程模型区域抽象为一个具有2维平面特征的虚拟图网络模型。不同的规则格网单元基本邻近模式有4格网单元模式、8格网单元模式、16格网单元模式。选择不同的邻近模式取决于问题的精度和求解效率要求，以及数据量和计算复杂度约束。

发明内容

本发明针对上述问题，顾及可视性分析，提出了一种将DEM地形数据表示的场模型转换成用图表示的可视图网络模型的构建方法。

本发明采用的技术方案如下：

一种面向地形可视性分析的可视性图网络构建方法，包括以下步骤：

步骤1，DEM数据初始化：对DEM格网数据进行扫描，分析是否存在空数据，若存在，进行插值计算，补充数据；

步骤2，选择构建图网络的DEM格网单元邻近模式，模式类型包括4格网单元邻近模式、8格网单元邻近模式和16格网单元邻近模式；

步骤3，计算可视图网络中顶点的属性值：结合可视域分析算法，计算网络中每个顶点对应的格网单元的可视的格网点数目或可视域面积大小；

步骤4，根据步骤2选择的邻近模式类型，计算可视图网络中边的权值：

(1)对于4格网单元邻近模式，可以看作格网单元沿坐标轴4个方向连接，其权值计算公式为：

其中，d为正方形格网单元采样间隔，即边长；E_i、E_j分别是源格网点和目标格网点的高程值；

(2)对于8格网单元邻近模式，格网单元沿坐标轴4个方向连接和沿对角线的4个方向连接，其权值计算公式为：

其中，d为正方形格网单元采样间隔，即边长；E_i、E_j分别是源格网点和目标格网点的高程值；

(3)对于16格网单元邻近模式，格网单元沿坐标轴4个方向连接、沿对角线的4个方向连接、以及沿坐标轴与对角线夹角的角平分线8个方向连接，其权值计算公式为：

其中，d为正方形格网单元采样间隔，即边长；E_i、E_j分别是源格网点和目标格网点的高程值；

步骤5，保存可视图网络数据。

本发明提供了一种基于图论的DEM数据模型到以图数据表达的可视图网络模型的转换方法，与现有技术相比，本发明的技术特点及有益效果为：

1、本发明提出的面向地形可视形分析的图网络方法，结合数字地形分析的DEM规格格网数据表示的场模型，在基于图论数学基础上，构建图网络模型，为地形可视性分析与应用建立基础。

2、本发明提出的基于可视域分析的图网络中属性值计算方法和边的权值计算方法，可以构建完整的图网络模型，为顾及可视性特征的可视性应用的优化建模和分析，提供了新的途径。

3、本发明完全可应用于大规模海量数据的地形可视性分析的不同领域的基于图网络的优化建模与求解方面，例如，基于可视域分析的旅游路径规划、危险品运输路径规划、军队行军隐蔽路径规划，也可以应用于景观分析与评估、军事、空间认知与决策、考古等领域的可视域分析为基础的研究手段等应用场合，提高处理效率。

附图说明

图1是本发明实施例中的图网络构建流程图；

图2是本发明实施例中的面向地形可视域分析的DEM格网邻近模式图，其中，a)是4格网单元模式；b)是8格网单元模式；c)是16格网单元模式；

图3是本发明实施例中的4格网邻近单元模式图网络边的权值计算示意图；

图4是本发明实施例中的8格网邻近单元模式图网络边的权值计算示意图；

图5为本发明实施例中的16格网邻近单元模式图网络边的权值计算示意图，其中，a)是图2c)中9,12,13,16格网点方向；b)是图2c)中10,11,14,15格网点方向。

具体实施方式

以下结合附图对本发明具体说明。需要指出，所描述的实施例仅仅视为说明的目的，而不是对发明的限制。

本发明的实施例提供了一种面向可视性分析与应用建模的图网络构建方法，其目的是为了将地形可视性分析应用的优化建模问题分成两个步骤来完成，一是先将数字高程模型的场模型的数据转换成用图模型表达的图数据，然后是基于图模型的优化建模和模型求解。这样做的好处是可以简化建模的复杂性和模型求解的效率。

比如在基于可视性分析的路径规划问题中，先将数字高程模型转换成图网络模型，然后在平面图网络中进行路径规划就可以利用有关图论中的算法进行最短路径搜索。在军事上，可以通过图网络寻找最隐蔽路径。在旅游路径规划中，可以利用图网络寻找最短路线且看到最多的景点。在危险品运输路线规划中，就是在图网络的基础上寻找一个最短且危险品泄露或爆炸所引起的危害最小的路线。

在森林火警瞭望塔、通讯基站、军事上的观察点等选址规划中，可以在图网络的基础上寻找一组观察点所组成的网络，使得该瞭望塔网络或军事观察点网络所观察到的范围(面积)最大，或者该基站网络所覆盖的信号区域最大。

本发明的方法正是实现上述应用中的第一步，即将2.5维的数字高程模型转换成1维的平面图网络模型，为采用图网络模型进行优化建模建立基础。同时也为进一步实现并行计算算法设计提供新途径，从而解决大规模数据的高性能计算问题。本实施例的转换方法，包括以下步骤：

1：DEM数据初始化。对DEM格网数据进行扫描，分析是否存在空数据，若存在，进行插值计算，补充完善空数据；

2：选择格网单元邻近模式。有4格网邻近模式、8格网邻近模式和16格网邻近模式供选择；

3：计算图网络中每个顶点的属性值。结合可视域分析算法，计算每个顶点对应的格网单元的可视的格网点数目或可视域面积大小。顶点属性表达图网络中每个顶点的特征，可通过一组属性值描述。如果需要可视域大小，则可通过可视域分析算法计算每个顶点对应的格网单元的可视域面积。如果是离散点表示，则可以是从该点所看到的目标点数目。

4：计算图网络中边的权值。根据图网络规模和精度要求，可选择4格网邻近模式、8格网邻近模式、或16格网邻近模式进行边的权值计算公式，并计算出权值大小：

1)基于4格网单元邻近模式，参看图2a)，可以看作格网单元沿坐标轴4个方向连接，即格网中心到1,2,3和4格网点。其图网络模型的边的权值计算比较简单，其几何表示如图3所示。

假设格网单元V_i和V_j的高程值分别为E_i和E_j，格网间沿X轴长为a，沿Y轴长为b，则图网络的边的权值计算公式如下：

若格网是正方形，即a＝b＝d，则式(1)变为：

若进行归一化处理，则式(2)变为：

2)基于8格网单元模式，参看图2b)，除沿坐标轴的4个方向外(1,2,3和4点)，还有沿对角线的4个方向(5,6,7和8点)。其图模型网络的边的权值计算方法如图4所示。假设格网单元V_i和V_j的高程值分别为E_i和E_j，格网间沿X轴长为a，沿Y轴长为b，则图网络的边的权值为：

如果是正方形格网，即a＝b＝d，则式(4)变为：

进行归一化处理，则式(5)变为：

3)16邻近格网单元模式，参看图2c)，其包括X轴方向(2和4点)、Y轴方向(1和3点)、对角线方向(5,6,7和8点)和其他8个方向(一组是9,12,13和16，另一组是10,11,14，和15点)。其图网络边的权值计算方法为：假设格网单元V_i和V_j的高程值分别为E_i和E_j，格网间沿X轴长为a，沿Y轴长为b，则图网络的边的权值为(参看图5)：

若是正方形格网，即a＝b＝d，则式(7)变为：

进行归一化处理，则式(8)变为：

图网络模型是一种图论中的图表示方法，将规则格网上地形点的高程值转化成为用顶点和边表示的图网络，为优化建模提供了新途径。节点的属性包括可视性视点数目或面积表示，边的权值可以根据高程值依据转换策略计算得到。为了考虑可视覆盖问题，根据可视性分析建立视点的覆盖范围(用面积表示或用可见点的数目表示)，其值作为图模型中节点的属性值。在离散的情况下，可以采用复杂网络进行建模，建立典型视点和被观察点的可视性网络模型，其观察点或视点的度可用于表示可视覆盖范围。

计算出每个边的权值后，接着需要构建每个顶点V的属性，包括可视域大小(可以表示为面积大小、可视的目标点个数等)、度大小(有向网络可以是入度和出度值)。对于4邻近格网模式，其每个顶点的度是4。8邻近格网模式，其每个顶点的度是8，而16邻近格网模式，其每个顶点的度是16。显然，构建的可视性网络是规则网络。

5：存储图网络数据。根据图网络中每个顶点属性值和边的权值的计算结果，并存储在数据文件中。

在具体的路径规划中，可根据图网络建立目标优化模型，比如最短路径、最小可视路径等等。在选址规划中，可以建立基于图网络的最大可视域的模型及其算法等等。