基于分支相似度的地形特征线提取方法、装置及电子设备

摘要

本发明提供了一种基于分支相似度的地形特征线提取方法、装置及电子设备，该方法包括：获取地形的DEM数据；扫描DEM数据，提取地形的特征点，并计算各个特征点的显著度；将由各个特征点构成的特征点标记图中的相邻特征点连线生成特征图；遍历特征图中各个特征点所在的连通分量，提取每个连通分量的各个分支，并计算每个分支的平均显著度；根据各个特征点的显著度以及各个分支的分支走向和平均显著度，从特征图中提取出多条待选特征线；根据各个特征点的显著度和各条待选特征线的长度计算待选特征线的显著度；根据每条待选特征线的显著度选取该地形的特征线。这样可以缓解主干特征线的过度延伸，能更准确地控制所提取地形特征线的显著度。

说明书

技术领域

本发明涉及地形处理技术领域，尤其是涉及一种基于分支相似度的地形特征线提取方法、装置及电子设备。

背景技术

山脊线和山谷线描述了地形的骨架结构，是最重要的地形特征线，其自动提取在自动地貌综合、水文分析、地理信息系统等方面有着非常重要的应用，同时还可为地形模型简化和基于样本的地形合成提供重要的特征依据。

目前通常采用基于地表几何形态分析的方法来提取地形特征线，基于地表几何形态分析的方法是利用山脊点和山谷点为相应方向上的高度极值点来提取地形特征线，即将山脊点或山谷点作为特征点构建特征树，从特征树中提取特征线。在对特征线进行筛选时，现有技术通常采用基于特征显著度的筛选方法，将特征线上特征点的显著度之和作为特征线的显著度，以显著度最大化原则从特征树中寻找主干特征线，继而将特征树分解为一条条的特征线，然后根据显著度大小对特征线排序，保留最显著的若干条特征线。

然而由于在搜索主干特征线时追求显著度最大化，该方法会造成主干特征线的过度延伸，另外特征线显著度的定义方式决定了由弱特征点构成的较长特征线的显著度可能超过由强特征点构成的较短特征线，这样会使得对主干特征线的提取不准确，进而导致所提取的特征线与实际情况不符。

发明内容

有鉴于此，本发明的目的在于提供一种基于分支相似度的地形特征线提取方法、装置及电子设备，以缓解主干特征线的过度延伸，更准确地控制所提取地形特征线的显著度。

第一方面，本发明实施例提供了一种基于分支相似度的地形特征线提取方法，包括：

获取地形的数字高程模型DEM(Digital Elevation Model)数据；

扫描所述DEM数据，提取所述地形的特征点，并计算各个所述特征点的显著度；其中，所述特征点包括山脊点或山谷点；

将由各个所述特征点构成的特征点标记图中的相邻特征点连线构成特征边，生成由各条所述特征边组成的特征图；

遍历所述特征图中各个所述特征点所在的连通分量，提取每个所述连通分量的各个分支，并根据各个所述特征点的显著度计算每个所述分支的平均显著度；

根据所述特征图中各个所述特征点的显著度以及各个所述分支的分支走向和平均显著度，从所述特征图中提取出多条待选特征线；其中，所述分支走向为分支两端点所构成线段的方向；

根据各条所述待选特征线中各个所述特征点的显著度和各条所述待选特征线的长度计算所述待选特征线的显著度；其中，所述待选特征线的长度为构成所述待选特征线的特征点的个数；

根据每条所述待选特征线的显著度，从多条所述待选特征线中选取所述地形的特征线。

结合第一方面，本发明实施例提供了第一方面的第一种可能的实施方式，其中，所述根据各个所述特征点的显著度计算每个所述分支的平均显著度，包括：

计算每个所述分支中各个特征点的显著度的平均值，将所述平均值作为所述分支的平均显著度。

结合第一方面，本发明实施例提供了第一方面的第二种可能的实施方式，其中，所述根据所述特征图中各个所述特征点的显著度以及各个所述分支的分支走向和平均显著度，从所述特征图中提取出多条待选特征线，包括：

根据每个所述连通分量中各个所述特征点的显著度以及各个所述分支的分支走向和平均显著度，从所述特征图中提取主干特征线；

根据各个所述分支的分支走向和平均显著度，从所述主干特征线的分叉点开始提取每个所述连通分量的分支特征线，并将各个所述主干特征线和各个所述分支特征线作为所述待选特征线。

结合第一方面的第二种可能的实施方式，本发明实施例提供了第一方面的第三种可能的实施方式，其中，所述根据每个所述连通分量中各个所述特征点的显著度以及各个所述分支的分支走向和平均显著度，从所述特征图中提取主干特征线，包括：

将每个所述连通分量中显著度最大的特征点所在的分支，确定为所述连通分量的最显著分支；

将每个所述连通分量的最显著分支作为当前分支，向所述当前分支的两端遍历未访问的相邻分支，并根据所述当前分支的分支走向和平均显著度、所述相邻分支的分支走向和平均显著度，从每端的各个所述相邻分支中确定延伸分支；

将所述延伸分支作为当前分支，继续确定所述当前分支的延伸分支，直到所述当前分支无延伸分支；

将每个所述连通分量的最显著分支和基于所述最显著分支得到的各个延伸分支提取出来，作为所述连通分量的主干特征线。

结合第一方面的第三种可能的实施方式，本发明实施例提供了第一方面的第四种可能的实施方式，其中，所述根据所述当前分支的分支走向和平均显著度、所述相邻分支的分支走向和平均显著度，从每端的各个所述相邻分支中确定延伸分支，包括：

从每端的各个所述相邻分支中选取与所述当前分支的分支走向之间的偏转角度小于等于预设角度阈值的待延伸分支；

根据所述当前分支的平均显著度和所述待延伸分支的平均显著度，计算所述待延伸分支与所述当前分支的差异值；

将每端的所述差异值小于等于指定差异阈值的各个所述待延伸分支中差异值最小的待延伸分支确定为所述延伸分支。

结合第一方面，本发明实施例提供了第一方面的第五种可能的实施方式，其中，通过以下公式计算所述待选特征线的显著度：

其中，S(L_i)表示待选特征线L_i的显著度，Ave_i表示待选特征线L_i的平均显著度，Ave_min和Ave_max分别表示各个所述待选特征线的平均显著度中的最小值和最大值，Len_i表示待选特征线L_i的长度，Len_min和Len_max分别表示各个所述待选特征线的长度中的最小值和最大值，Max_i表示待选特征线L_i的最大显著度，Max_min和Max_max分别表示各个所述待选特征线的最大显著度中的最小值和最大值，k_a表示平均显著度权重系数，k_l表示特征线长度权重系数，k_m表示最大显著度权重系数；其中，所述待选特征线的平均显著度为构成所述待选特征线的各个特征点的显著度的平均值，所述待选特征线的最大显著度为构成所述待选特征线的各个特征点的显著度中的最大值。

结合第一方面，本发明实施例提供了第一方面的第六种可能的实施方式，其中，所述将由各个所述特征点构成的特征点标记图中的相邻特征点连线构成特征边，生成由各条所述特征边组成的特征图之前，所述方法还包括：对所述特征点标记图中的由多个所述特征点构成的特征点宽带进行以下细线化处理：

根据各个所述特征点的显著度，从所述特征点宽带中选取待删除点；

从所述特征点宽带中删除所述待删除点，得到细线化处理后的单像素宽的特征点标记图。

结合第一方面，本发明实施例提供了第一方面的第七种可能的实施方式，其中，所述将由各个所述特征点构成的特征点标记图中的相邻特征点连线构成特征边，生成由各条所述特征边组成的特征图之后，所述方法还包括：将所述特征图进行以下优化处理：

检测所述特征图中由多条特征边形成的环路，选取检测到的环路面积小于预设面积的待破除环路；

将所述待破除环路中显著度最小的特征边删除，得到优化处理后的特征图；其中，所述特征边的显著度为构成所述特征边的两个特征点的显著度之和。

第二方面，本发明实施例还提供一种基于分支相似度的地形特征线提取装置，包括：

数据获取模块，用于获取地形的数字高程模型DEM数据；

特征点提取模块，用于扫描所述DEM数据，提取所述地形的特征点，并计算各个所述特征点的显著度；其中，所述特征点包括山脊点或山谷点；

特征图生成模块，用于将由各个所述特征点构成的特征点标记图中的相邻特征点连线构成特征边，生成由各条所述特征边组成的特征图；

分支提取模块，用于遍历所述特征图中各个所述特征点所在的连通分量，提取每个所述连通分量的各个分支，并根据各个所述特征点的显著度计算每个所述分支的平均显著度；

待选特征线提取模块，用于根据所述特征图中各个所述特征点的显著度以及各个所述分支的分支走向和平均显著度，从所述特征图中提取出多条待选特征线；其中，所述分支走向为分支两端点所构成线段的方向；

特征线显著度计算模块，用于根据各条所述待选特征线中各个所述特征点的显著度和各条所述待选特征线的长度计算所述待选特征线的显著度；其中，所述待选特征线的长度为构成所述待选特征线的特征点的个数；

特征线选取模块，用于根据每条所述待选特征线的显著度，从多条所述待选特征线中选取所述地形的特征线。

第三方面，本发明实施例还提供了一种电子设备，包括存储器、处理器，所述存储器中存储有可在所述处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现上述第一方面所述的方法的步骤。

本发明实施例带来了以下有益效果：

本发明实施例中，获取地形的数字高程模型DEM数据；扫描该DEM数据，提取地形的特征点，并计算各个特征点的显著度；其中，特征点包括山脊点或山谷点；将由各个特征点构成的特征点标记图中的相邻特征点连线构成特征边，生成由各条特征边组成的特征图；遍历该特征图中各个特征点所在的连通分量，提取每个连通分量的各个分支，并根据各个特征点的显著度计算每个分支的平均显著度；根据特征图中各个特征点的显著度以及各个分支的分支走向和平均显著度，从该特征图中提取出多条待选特征线；其中，分支走向为分支两端点所构成线段的方向；根据各条待选特征线中各个特征点的显著度和各条待选特征线的长度计算待选特征线的显著度；其中，待选特征线的长度为构成该待选特征线的特征点的个数；根据每条待选特征线的显著度，从多条待选特征线中选取该地形的特征线。本发明实施例提供的基于分支相似度的地形特征线提取方法、装置及电子设备，在提取待选特征线时考虑了各个分支的分支走向和平均显著度，因此可以缓解主干特征线的过度延伸；在计算待选特征线的显著度时，综合考虑了各条待选特征线中各个特征点的显著度和各条待选特征线的长度，避免了由弱特征点构成的较长特征线的显著度超过由强特征点构成的较短特征线的显著度的发生，因此对主干特征线的提取更加准确，所提取的特征线与实际情况更加符合，提高了提取地形特征线的准确度。

本发明的其他特征和优点将在随后的说明书中阐述，并且，部分地从说明书中变得显而易见，或者通过实施本发明而了解。本发明的目的和其他优点在说明书、权利要求书以及附图中所特别指出的结构来实现和获得。

为使本发明的上述目的、特征和优点能更明显易懂，下文特举较佳实施例，并配合所附附图，作详细说明如下。

附图说明

为了更清楚地说明本发明具体实施方式或现有技术中的技术方案，下面将对具体实施方式或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施方式，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明实施例提供的第一种方法流程示意图；

图2为本发明实施例提供的第二种方法流程示意图；

图3(a)为细线化处理前2像素宽的山脊点宽带的结构示意图；

图3(b)为细线化处理后的山脊点宽带的结构示意图；

图4为本发明实施例提供的一种提取主干特征线的流程示意图；

图5(a)为用于对比实验的某山区DEM的第一张灰度图；

图5(b)为用于对比实验的某山区DEM的第二张灰度图；

图6(a)为采用现有技术从图5(a)中提取5条山脊线的结果图；

图6(b)为采用本发明实施例提供的方法从图5(a)中提取5条山脊线的结果图；

图6(c)为采用现有技术从图5(a)中提取40条山脊线的结果图；

图6(d)为采用本发明实施例提供的方法从图5(a)中提取40条山脊线的结果图；

图7(a)为采用现有技术从图5(a)中提取5条山谷线的结果图；

图7(b)为采用本发明实施例提供的方法从图5(a)中提取5条山谷线的结果图；

图7(c)为采用现有技术从图5(a)中提取40条山谷线的结果图；

图7(d)为采用本发明实施例提供的方法从图5(a)中提取40条山谷线的结果图；

图8(a)为采用现有技术从图5(b)中提取5条山脊线的结果图；

图8(b)为采用本发明实施例提供的方法从图5(b)中提取5条山脊线的结果图；

图8(c)为采用现有技术从图5(b)中提取40条山脊线的结果图；

图8(d)为采用本发明实施例提供的方法从图5(b)中提取40条山脊线的结果图；

图9(a)为采用现有技术从图5(b)中提取5条山谷线的结果图；

图9(b)为采用本发明实施例提供的方法从图5(b)中提取5条山谷线的结果图；

图9(c)为采用现有技术从图5(b)中提取40条山谷线的结果图；

图9(d)为采用本发明实施例提供的方法从图5(b)中提取40条山谷线的结果图；

图10为本发明实施例提供的基于分支相似度的地形特征线提取装置的模块组成示意图；

图11为本发明实施例提供的电子设备的结构示意图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合附图对本发明的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

目前现有技术以显著度最大化原则从特征树中寻找主干特征线，容易造成主干特征线的过度延伸，另外现有技术将特征线上特征点的显著度之和作为特征线的显著度，会使得对主干特征线的提取不准确，进而导致所提取的特征线与实际情况不符。基于此，本发明实施例提供的一种基于分支相似度的地形特征线提取方法、装置及电子设备，可以缓解主干特征线的过度延伸，提高提取地形特征线的准确度。

为便于对本实施例进行理解，首先对本发明实施例所公开的一种基于分支相似度的地形特征线提取方法进行详细介绍。

实施例一：

图1为本发明实施例提供的第一种方法流程示意图，如图1所示，该方法包括以下几个步骤：

步骤S101，获取地形的数字高程模型DEM数据。

地形的特征线包括山脊线和山谷线，对于山脊线，可以直接利用地形的DEM数据通过执行下述步骤来提取；对于山谷线，需要将该地形的DEM数据取反后再通过执行下述步骤来提取。

步骤S102，扫描上述DEM数据，提取地形的特征点，并计算各个特征点的显著度。

通过扫描上述DEM数据，可以得到地形走势、高度、水平距离等信息。根据前后地形走势、高度差等信息可以提取出特征点，特征点包括山脊点或山谷点。本发明实施例支持在原始分辨率下进行特征点提取，在提取特征点的过程中未进行下采样，这样可以避免下采样过程中带来的信息丢失。在确定特征点之后，利用扫描过程中获得的高度和水平距离等信息，可以计算每个特征点的显著度。

步骤S103，将由各个上述特征点构成的特征点标记图中的相邻特征点连线构成特征边，生成由各条特征边组成的特征图。

对上述特征点标记图中的相邻特征点进行全连接操作，形成特征边，每条特征边由两个相邻的特征点连线构成。在进行全连接操作过程中，如果出现两条特征边交叉的情况，则剔除显著度较小的特征边，其中，特征边的显著度定义为构成该特征边的两个特征点的显著度之和。这样就生成了由各条特征边组成的特征图。

步骤S104，遍历上述特征图中各个特征点所在的连通分量，提取每个连通分量的各个分支，并根据各个特征点的显著度计算每个分支的平均显著度。

分支指一条线段上除去两个端点后剩下点的度均为2，且两个端点均满足度大于2或度为1；对于由度为2的点构成的环路，也称其为一分支，其两个端点相同。其中，某点的度指与该点连接的线段的个数。

遍历上述特征图中各个特征点所在的连通分量，根据上述分支的定义提取每个连通分量的各个分支。根据各个特征点的显著度计算每个分支的平均显著度具体为：计算每个分支中各个特征点的显著度的平均值，将该平均值作为分支的平均显著度。

步骤S105，根据上述特征图中各个特征点的显著度以及各个分支的分支走向和平均显著度，从该特征图中提取出多条待选特征线。

分支走向为分支两端点所构成线段的方向。为了将上述特征图分解为多条特征线，同时解决主干特征线的过度延伸问题，在分解特征图提取待选特征线时，可以将分支走向一致(例如两分支走向的偏转角度不超过90°)且平均显著度相近(相邻分支中平均显著度的差异值最小且小于等于指定差异阈值)的各个分支提取出来作为待选特征线。

步骤S106，根据各条待选特征线中各个特征点的显著度和各条待选特征线的长度计算待选特征线的显著度。

待选特征线的长度为构成该待选特征线的特征点的个数。为了使待选特征线的显著度更加贴近实际，综合考虑各条待选特征线中各个特征点的显著度和各条待选特征线的长度来计算每条待选特征线的显著度。具体地，可以考虑以下因素计算待选特征线的显著度：当前计算的待选特征线(简称为当前特征线)的平均显著度、各条待选特征线的平均显著度中的最大值和最小值、当前特征线的长度、各条待选特征线的长度中的最大值和最小值、当前特征线的最大显著度、各条待选特征线的最大显著度中的最大值和最小值，其中，待选特征线的平均显著度为构成该待选特征线的各个特征点的显著度的平均值，待选特征线的最大显著度为构成该待选特征线的各个特征点的显著度中的最大值。这样可以避免由弱特征点构成的较长特征线的显著度超过由强特征点构成的较短特征线的显著度的发生，因此便于后续对主干特征线的提取，使得所提取的特征线与实际情况更加符合，进而提高提取地形特征线的准确度。

步骤S107，根据每条待选特征线的显著度，从多条待选特征线中选取上述地形的特征线。

具体地，根据每条待选特征线的显著度，可以将显著度大于显著度阈值的所有待选特征线选取为该地形的特征线，也可以将各条待选特征线按照显著度大小排序，从显著度最大的待选特征线开始选取指定数量的待选特征线作为该地形的特征线。其中，显著度阈值可以根据实际情况设置，指定数量也可以根据用户要求设置，这里对设定显著度阈值和指定数量均不作限定。

本发明实施例提供的基于分支相似度的地形特征线提取方法，在提取待选特征线时考虑了各个分支的分支走向和平均显著度，因此可以缓解主干特征线的过度延伸；在计算待选特征线的显著度时，综合考虑了各条待选特征线中各个特征点的显著度和各条待选特征线的长度，避免了由弱特征点构成的较长特征线的显著度超过由强特征点构成的较短特征线的显著度的发生，因此对主干特征线的提取更加准确，所提取的特征线与实际情况更加符合，提高了提取地形特征线的准确度。

图2为本发明实施例提供的第二种方法流程示意图，如图2所示，以根据地形的DEM数据提取该地形的山脊线为例，该方法包括以下几个步骤：

步骤S201，采用全局断面扫描算法，分别沿多个方向扫描地形的DEM数据，提取该地形的山脊点，并计算各个山脊点的显著度。

断面极值法是一种简单高效的确定特征点的方法，通常将断面上的高程极大值点作为山脊线上的山脊点，将极小值点作为山谷线上的山谷点。考虑到现有技术中采用局部窗口进行断面分析时，容易受到窗口大小和噪声的影响，本实施例采用全局断面扫描算法提取该地形的山脊点，具体为：分别沿水平、垂直及两个斜45度方向对地形的DEM数据进行逐行扫描，得到地形走势、高度、水平距离等信息，根据前后地形走势、高度差等信息提取出该地形的山脊点。由于提取山脊点时利用了全局信息，因此更容易剔除噪声和伪特征点。

在确定山脊点之后，利用扫描过程中获得的高度和水平距离等信息，可以根据下述公式(1)计算每个山脊点p_i的显著度S(p_i)：

其中，S(p_i)表示山脊点p_i的显著度，h_i表示山脊点p_i的高度，Δh_li和Δh_ri分别表示山脊点p_i与两个相邻候选山脊点的高度落差，d_li和d_ri表示山脊点p_i与两个相邻候选山脊点的水平距离，h_max表示DEM数据中的最大高度，Δh_max表示DEM数据中的最大高度落差，k_h表示高度权重系数，k_d表示高度落差权重系数，k_s表示坡度权重系数；相邻候选山脊点为在扫描方向的垂直方向上与山脊点p_i相邻的山脊点。k_h、k_d、k_s三个权重系数可以根据实际情况设置，例如可以依次设置为3、2、1。

步骤S202，沿每个山脊点的特征方向及与该特征方向相邻的方向进行特征延伸，获取特征延伸产生的各个延伸山脊点，并将各个延伸山脊点的显著度设置为0。

为了增强特征连通性，对于上述获得的每个山脊点尝试沿其特征方向及特征方向的相邻方向进行延伸，其中，特征方向与步骤S201中的扫描方向垂直，特征方向的相邻方向指与特征方向的夹角不超过90°的方向，例如向右延伸时，可以但不限于考虑右方、右上和右下三个方向的相邻点。如果当前考察的相邻点的高度不小于延伸方向两侧的相邻山脊点的高度，则将其纳入新增山脊点即延伸山脊点。为了便于后面选取山脊线时将主要由延伸山脊点构成的山脊线筛选掉，将各个延伸山脊点的显著度设置为0。步骤S201得到的山脊点和步骤S202得到的延伸山脊点均作为上述地形的山脊点，进行后续处理。

步骤S203，对由多个上述山脊点构成的山脊点宽带进行细线化处理，得到单像素宽的特征点标记图。

具体包括以下两个子步骤：

(1)根据各个山脊点的显著度，从上述山脊点宽带中选取待删除点。

具体地，按照扫描线顺序考察每个山脊点，判断当前点是否满足下述预设条件：当前点为上述地形的山脊点，且当前点为山脊点宽带的边缘中的非端点，以及当前点为维持山脊点宽带的连接性的冗余点。若当前点满足该预设条件，则查找当前点的预设邻域内满足上述预设条件的待选山脊点，并将查找到的显著度最小的待选山脊点确定为待删除点，当显著度最小的待选山脊点有两个时，则随机选择一个作为待删除点。进一步地，考虑到山脊点宽带一般为2或3像素宽，本实施例中的预设邻域优选5×5邻域。

(2)从山脊点宽带中删除待删除点，得到细线化处理后的单像素宽的特征点标记图。

下面以5×5邻域、图3(a)和图3(b)为例，具体说明细线化处理的过程。图3(a)为细线化处理前2像素宽的山脊点宽带的结构示意图，图3(b)为细线化处理后的山脊点宽带的结构示意图。图3(a)和3(b)中空白格代表非山脊点，非0数字格代表山脊点，非0数字表示特征点的显著度，0格表示已删除的待删除点。如图3(a)所示，当考查10对应的山脊点时，10格满足预设条件，10格的5×5邻域内显著度最小的山脊点为3格，则将3格标记为待删除点；同样的，考察5格时将4格标记为待删除点；考察9格时不满足预设条件；考察7格将5格标记为待删除点；考察6格将6格标记为待删除点；考察8格时不满足预设条件。将图3(a)中的3格、4格、5格和6格删除后即可得到图3(b)。

可见采用该细线化方法选取的待删除点与扫描顺序无关，在一次扫描过程中删除了显著度较小的山脊点，保留了显著度较大的山脊点，这样既保证了最终得到的是单像素宽的山脊线，降低了后续步骤的计算量，又便于实现对所提取山脊线的显著度的准确控制，从而提高了提取山脊线的准确度。

步骤S204，将上述特征点标记图中的相邻山脊点连线构成特征边，生成由各条特征边组成的特征图。

具体过程与上述步骤S103相同，这里不再赘述。

步骤S205，将上述特征图进行环路检测，并破除环路面积小于预设面积的环路，得到环路优化处理后的特征图。

环路是由多条特征边形成的，考虑到步骤S204得到的特征图中通常存在环路，其中绝大多数为面积非常小的环路，尤其是小三角形，这些环路应该被破除，而由于环形山脊等环形特征在自然界及合成地形中广泛存在，因此需要保留较大的环路。

具体地，检测上述特征图中的环路，选取检测到的环路面积小于预设面积的待破除环路，将待破除环路中显著度最小的特征边删除，得到环路优化处理后的特征图；其中，环路面积指环路内部包含的像素点的个数，特征边的显著度为构成该特征边的两个山脊点的显著度之和。预设面积可以根据实际情况设置，例如预设面积为10⁴个像素点。这样既破除了无效的小环路，又保留了面积较大的环路，可以支持环形地形特征线的提取，同时还考虑了特征边的显著度，便于实现对所提取山脊线的显著度的准确控制，以进一步提高提取山脊线的准确度。

步骤S206，根据每个连通分量中各个山脊点的显著度以及各个分支的分支走向和平均显著度，从上述特征图中提取主干特征线。

图4为本发明实施例提供的一种提取主干特征线的流程示意图，如图4所示，通过以下步骤提取主干特征线：

步骤S2061，将每个连通分量中显著度最大的山脊点所在的分支，确定为该连通分量的最显著分支。

最显著分支为在特征图的一个连通分量中拥有最大显著度的特征点所在的分支，若特征图中有多个连通分量，则会有多个最显著分支。

利用最大显著度对应的山脊点往往出现在主干特征线上这一事实，下面几个步骤为：从最显著分支开始，根据分支走向及分支的平均显著度的相似度来连接其他相邻分支，提取主干特征线。

步骤S2062，将每个连通分量的最显著分支作为当前分支，向当前分支的两端遍历未访问的相邻分支，并根据当前分支的分支走向和平均显著度、相邻分支的分支走向和平均显著度，从每端的各个相邻分支中确定延伸分支。

具体地，从每端的各个相邻分支中选取与当前分支的分支走向之间的偏转角度小于等于预设角度阈值的待延伸分支；根据当前分支的平均显著度和待延伸分支的平均显著度，计算待延伸分支与当前分支的差异值；将每端的差异值小于等于指定差异阈值的各个待延伸分支中差异值最小的待延伸分支确定为延伸分支。其中，预设角度阈值和指定差异阈值均可以根据实际需要设置，例如预设角度阈值可以设置为90°，指定差异阈值通常设置在60％-80％之间；差异值可以通过以下公式计算：

其中，dif表示差异值，AveMaxBranch表示当前分支的平均显著度，AveCurBranch表示待延伸分支的平均显著度。

步骤S2063，将上述延伸分支作为当前分支，继续确定当前分支的延伸分支，直到当前分支无延伸分支。

采用上述方法遍历连通分量的各个未访问分支，当向两个端点方向的遍历都终止时，延伸分支的确定完毕。

步骤S2064，将每个连通分量的最显著分支和基于最显著分支得到的各个延伸分支提取出来，作为该连通分量的主干特征线。

采用上述方法即可提取出特征图中的每个连通分量的主干特征线。

步骤S207，根据各个分支的分支走向和平均显著度，从主干特征线的分支点开始提取每个连通分量的分支特征线，并将各个主干特征线和各个分支特征线作为待选山脊线。

在提取主干特征线过程中，将遍历到的度大于2的分支端点(也即主干特征线的分支点)都加入集合BranchPoints中。提取主干特征线结束后，从BranchPoints选取一个主干特征线的分支点，进行分支特征线的提取，具体方法与提取主干特征线的方法相似。若BranchPoints为空，则结束提取分支特征线。

具体地，选取以分支点p为端点的一个未访问分支为参考分支，沿该分支的另一端点方向遍历相邻分支，根据分支走向及在平均显著度上的差异值来选取延伸分支，并将延伸分支纳入到当前提取的分支特征线中，同时将遍历到的度大于2的分支端点都加入到集合BranchPoints中。在结束当前分支特征线的提取后，考察是否有其他以p为端点的未访问分支，有则将其作为参考分支继续提取分支特征线，没有则重新从BranchPoints中选取分支点并进行分支特征线的提取。

最后将采用上述方法提取出的各个主干特征线和各个分支特征线作为待选山脊线。

步骤S208，根据各条待选山脊线中各个山脊点的显著度和各条待选山脊线的长度计算待选山脊线的显著度。

具体地，通过以下公式计算待选山脊线的显著度：

其中，S(L_i)表示待选山脊线L_i的显著度，Ave_i表示待选山脊线L_i的平均显著度，Ave_min和Ave_max分别表示各个待选山脊线的平均显著度中的最小值和最大值，Len_i表示待选山脊线L_i的长度，Len_min和Len_max分别表示各个待选山脊线的长度中的最小值和最大值，Max_i表示待选山脊线L_i的最大显著度，Max_min和Max_max分别表示各个待选山脊线的最大显著度中的最小值和最大值，k_a表示平均显著度权重系数，k_l表示特征线长度权重系数，k_m表示最大显著度权重系数。

步骤S209，将各条待选山脊线按照显著度大小排序，从显著度最大的待选山脊线开始选取指定数量的待选山脊线作为上述地形的山脊线。

具体地，可以将各条待选山脊线按照显著度从大到小的顺序排序，根据各条待选山脊线的排列顺序，从显著度最大的待选山脊线开始选取指定数量的待选山脊线作为上述地形的山脊线。这里的指定数量可以由用户预先指定，也可以是排序后由用户交互式地指定。

为了验证本实施例提供的方法的有效性，选用了某山区30米精度DEM数据(如图5(a)和5(b)所示)进行测试，其中图5(a)的像素为480×480，图5(b)的像素为512×512。为了凸显本实施例的效果，分别采用本实施例提供的方法和现有技术进行了实验，本实施例提供的方法所独有的参数设置如下：在进行破环时保留环内面积大于10⁵个像素的环路；预设角度阈值为90°，指定差异阈值设为70％；按公式(3)计算待选特征线的显著度时权重系数k_a、k_l、k_m均取1。现有技术是将特征线上特征点的显著度之和作为特征线的显著度，以显著度最大化原则从特征树中寻找主干特征线。

实验结果对比如图6(a)、6(b)、6(c)、6(d)、7(a)、7(b)、7(c)、7(d)、8(a)、8(b)、8(c)、8(d)、9(a)、9(b)、9(c)、9(d)所示，其中，图6(a)、6(b)、7(a)、7(b)、8(a)、8(b)、9(a)、9(b)中的数字表示对应特征线的显著度。从上述实验结果中可以看出，采用现有技术提取特征线时，存在主干特征线过度延伸以及主干特征线提取不准确等问题，且特征线的显著度排序与人眼观察有较大出入；采用本实施例的方法提取特征线，较好地避免了特征线的过度延伸，此外特征显著度的计算同时考虑了特征线的长度、线上特征点的平均显著度和最大显著度三方面因素，这样如果某特征线在三方面中有任一方面排名较后，总体排名都不会靠前。从提取5条山脊线(或山谷线)的结果图(例如图6(b)、7(b)等)中可以发现，本实施例的方法对特征图的分解以及特征线的显著度排序更加合理，更接近人眼观察结果。

实施例二：

图10为本发明实施例提供的基于分支相似度的地形特征线提取装置的模块组成示意图，如图10所示，该基于分支相似度的地形特征线提取装置包括：数据获取模块11，用于获取地形的数字高程模型DEM数据；特征点提取模块12，用于扫描上述DEM数据，提取地形的特征点，并计算各个特征点的显著度；其中，特征点包括山脊点或山谷点；特征图生成模块13，用于将由各个特征点构成的特征点标记图中的相邻特征点连线构成特征边，生成由各条特征边组成的特征图；分支提取模块14，用于遍历上述特征图中各个特征点所在的连通分量，提取每个连通分量的各个分支，并根据各个特征点的显著度计算每个分支的平均显著度；待选特征线提取模块15，用于根据上述特征图中各个特征点的显著度以及各个分支的分支走向和平均显著度，从特征图中提取出多条待选特征线；其中，分支走向为分支两端点所构成线段的方向；特征线显著度计算模块16，用于根据各条待选特征线中各个特征点的显著度和各条待选特征线的长度计算待选特征线的显著度；其中，待选特征线的长度为构成该待选特征线的特征点的个数；特征线选取模块17，用于根据每条待选特征线的显著度，从多条待选特征线中选取上述地形的特征线。

本发明实施例提供的基于分支相似度的地形特征线提取装置，在提取待选特征线时考虑了各个分支的分支走向和平均显著度，因此可以缓解主干特征线的过度延伸；在计算待选特征线的显著度时，综合考虑了各条待选特征线中各个特征点的显著度和各条待选特征线的长度，避免了由弱特征点构成的较长特征线的显著度超过由强特征点构成的较短特征线的显著度的发生，因此对主干特征线的提取更加准确，所提取的特征线与实际情况更加符合，提高了提取地形特征线的准确度。

实施例三：

图11为本发明实施例提供的电子设备的结构示意图，参见图11，本发明实施例还提供一种电子设备100，包括：处理器40，存储器41，总线42和通信接口43，所述处理器40、通信接口43和存储器41通过总线42连接；存储器41中存储有可在处理器40上运行的计算机程序，处理器40执行该计算机程序时实现上述地形特征线提取的方法的步骤。

其中，存储器41可能包含高速随机存取存储器(RAM，Random Access Memory)，也可能还包括非不稳定的存储器(non-volatile memory)，例如至少一个磁盘存储器。通过至少一个通信接口43(可以是有线或者无线)实现该系统网元与至少一个其他网元之间的通信连接，可以使用互联网，广域网，本地网，城域网等。

总线42可以是ISA总线、PCI总线或EISA总线等。所述总线可以分为地址总线、数据总线、控制总线等。为便于表示，图11中仅用一个双向箭头表示，但并不表示仅有一根总线或一种类型的总线。

其中，存储器41用于存储程序，所述处理器40在接收到执行指令后，执行所述程序，前述本发明实施例任一实施例揭示的流过程定义的装置所执行的方法可以应用于处理器40中，或者由处理器40实现。

处理器40可能是一种集成电路芯片，具有信号的处理能力。在实现过程中，上述方法的各步骤可以通过处理器40中的硬件的集成逻辑电路或者软件形式的指令完成。上述的处理器40可以是通用处理器，包括中央处理器(Central Processing Unit，简称CPU)、网络处理器(Network Processor，简称NP)等；还可以是数字信号处理器(Digital SignalProcessing，简称DSP)、专用集成电路(Application Specific Integrated Circuit，简称ASIC)、现成可编程门阵列(Field-Programmable Gate Array，简称FPGA)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件。可以实现或者执行本发明实施例中的公开的各方法、步骤及逻辑框图。通用处理器可以是微处理器或者该处理器也可以是任何常规的处理器等。结合本发明实施例所公开的方法的步骤可以直接体现为硬件译码处理器执行完成，或者用译码处理器中的硬件及软件模块组合执行完成。软件模块可以位于随机存储器，闪存、只读存储器，可编程只读存储器或者电可擦写可编程存储器、寄存器等本领域成熟的存储介质中。该存储介质位于存储器41，处理器40读取存储器41中的信息，结合其硬件完成上述方法的步骤。

本发明实施例提供的基于分支相似度的地形特征线提取方法、装置及电子设备具有相同的技术特征，所以也能解决相同的技术问题，达到相同的技术效果。

所属领域的技术人员可以清楚地了解到，为描述的方便和简洁，上述描述的装置和电子设备的具体工作过程，可以参考前述方法实施例中的对应过程，在此不再赘述。

附图中的流程图和框图显示了根据本发明的多个实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段或代码的一部分，所述模块、程序段或代码的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。也应当注意，在有些作为替换的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个连续的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图和/或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行规定的功能或动作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。

本发明实施例所提供的进行地形特征线提取的计算机程序产品，包括存储了处理器可执行的非易失的程序代码的计算机可读存储介质，所述程序代码包括的指令可用于执行前面方法实施例中所述的方法，具体实现可参见方法实施例，在此不再赘述。

在本申请所提供的几个实施例中，应该理解到，所揭露的系统、装置和方法，可以通过其它的方式实现。以上所描述的装置实施例仅仅是示意性的，例如，所述单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，又例如，多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些通信接口，装置或单元的间接耦合或通信连接，可以是电性，机械或其它的形式。

所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。另外，在本发明各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。

所述功能如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个处理器可执行的非易失的计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器(ROM，Read-Only Memory)、随机存取存储器(RAM，Random Access Memory)、磁碟或者光盘等各种可以存储程序代码的介质。

最后应说明的是：以上所述实施例，仅为本发明的具体实施方式，用以说明本发明的技术方案，而非对其限制，本发明的保护范围并不局限于此，尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，其依然可以对前述实施例所记载的技术方案进行修改或可轻易想到变化，或者对其中部分技术特征进行等同替换；而这些修改、变化或者替换，并不使相应技术方案的本质脱离本发明实施例技术方案的精神和范围，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应所述以权利要求的保护范围为准。