一种改进的曲线特征点提取 ***

为针对传统曲线特征点的提取 *** 均采用Douglas-Peucher(D-P)算法给定阈值的思路，在曲度较大处易造成一 些重要特征点缺失，在弯曲的水平距离较小处易造成非特征点保留的问题，该文提出一种改进的曲线特征点提取 *** ，通过自适应来提取曲线的全局特征点，即通过标准差分别计算出间隔点连线的参考值和中间点到该线垂线的参考值，比较曲线上每个点的弯曲程度与曲线整体弯曲程度的大小，来提取曲线的全局特征点。以道路和河流的实际线数据进行了实验，结果表明，该 *** 不仅很好地保持了曲线整体形状特征，而且大幅降低了压缩误差、提高了精度。

关键词：特征点；统计法；自适应；标准差；弯曲度

微信号：MeetyXiao
添加微信好友, 获取更多信息
复制微信号

能够概括曲线基本形状的点叫做曲线的特征点[1]。线要素化简算法[2-5]的核心思想是在尽可能保持曲线形状特征的前提下，减少其节点的数量， 所以准确提取特征点十分重要。目前单线压缩的算法已经较为成熟，曲线特征点的提取主要基于垂距、斜率、角度等[6-10] *** ，垂距法具有旋转不变性和位移不变性的优点，受到广泛的应用。垂距法来源于经典D-P算法，通过预先给定阈值，再比较曲线上的点到曲线首末端点连线 的垂距与给定阈值的大小，来提取特征点；很多算法都是在此基础上进行了改进，如：文献[11]提出的面向自然岸线抽稀的改进D-P算法，该算法是将曲线上的一些特殊凸点作为分段点，使用D-P进行化简，提取自然岸线凸点作为备选分段点集，根据凸点与相邻两点组成的三角形面积大小筛选分段点，接着利用相邻分段点作为D-P算法的首尾点，以基于最小二乘法的拟合曲线选定更优距离阈值，并作为初始阈值，进行逐段抽稀。文献 [12]提出的基于Ping的D-P算法抽稀阈值优化选取，将测深条带中每Ping数 据看做一条空间曲线，然后利用D-P算法进行多波束测深数据的抽稀，选取不同抽稀阈值对Ping进行抽稀运算；文献[13]提出的矢量数据压缩算法的实现与改进，即径向约束D-P算法，通过预先给定的垂距阈值和径向约束阈值，然后比较曲线上的点到曲 线首末端点连线的垂距与给定阈值的大小，再比较曲线上的点到曲线首末端点连线的值与给定径向约束阈值 的大小，来提取特征点；上述算法基本上都是D-P算法的延伸和拓展，通 过给定阈值的方式来提取特征点，在曲度较大处易造成一些重要特征点缺失，在弯曲的水平距离较小处易造成一些非特征点的保留。本文针对径向约束D-P算法[13]提取曲线全局特征点的不足，提出了一种全新的曲线全局特征点的识别 *** 。通过标准差分别计算出间隔点连线的参考值和中 间点到该线垂线的参考值，通过比较曲线上每个点的弯曲程度与曲线整体弯曲程度[14]的大小，来提取曲线的全局特征点。

１）D-P算法。D-P算法是曲线矢简量数据压缩 的一种常用而有效的算法，利用递归过程能够非常简洁的完成算法实现，先连接曲线首尾两点构成一条直线，然后计算曲线上其余各个点到该直线的距离ｄ，选取其中的更大值Dk与规定的临界值Ｄ作比较，若曲线上的点到该直线上距离的更大值Dk都小于规定的临界值Ｄ，则直接舍去曲线上首尾间的各个点，若曲线上的点到该直线上距离的更大值Dk不小于规定的临界值Ｄ，则保留曲线上的该点。以图１为例，具体步骤如下：①设曲线由点序P１，P２，…，Pｎ构成，取P１，Pｎ为首尾两点；②计算曲线上所有内点Pｉ（ｉ＝２，３，…， ｎ－１）到直线P１Pｎ的距离Dｉ，选取曲线上的点到直线距离更大的点Pk；③判断曲线到直线P１Pｎ上的更大距离Dk与给定的临界值Ｄ的大小，若Dk小于给定的临界值，则该点不是特征点，若Dk不小于给定的临界值，则该点Ｐｋ成为特征点。

２）带有径向约束的D-P算法。D-P算法仅利用 垂向距离作为约束条件来决定曲线内点的取舍，当给定的临界值差别比较大时，会导致曲线 的压缩结果完全不同；该算法在大比例尺度压缩过程中不能有效控制面积误差[15]，致使压缩后的面积与原图形面积差距比较大；文献[13]针对这些问题引进了径向距离约束条件的 *** ，提出了一种矢 量数据压缩的D-P算法的实现与改进，降低了压缩后图形面积与原图形面积的误差，取得了较好的效果。该算法的基本思想是在D-P算 法②、③ 中间加一个径向约束条件ｒ，步骤如下：步骤的① 和②不变；③给定径向约 束 条 件ｒ；ｒ为 曲线 一 定距离的弧段；④判断曲线到直线P１Pｎ上的更大 距离Dk与给定的临界值Ｄ的大小，若Dk小于给定临界值，则再判断｜PKP１｜或｜PKＰｎ｜的距离与径向约束条件ｒ的大小，只要有一个距离大于径向约束条件ｒ，则点PK仍作为特征点保留；若 Dk不小于给定的临界值，则该点为特征点。

该压缩算法仍然采用D-P 算法的思路，导致在曲线曲度较大处易 造成一些重要特征点缺失， 在弯曲的水平距离较小处易造成非特征点的保留，最终影响压缩后的图形效果[16]。见图２（ａ），该阈值下特征点为B、C、Ｄ、Ｅ、Ｇ、Ｈ、Ｉ、Ｋ、Ｌ、 Ｍ、Ｏ。由于阈值较小，在弯曲的水平距离较小处 造成非特征点 Ｄ、Ｋ、Ｍ 的 保 留，见 图２（ｂ），该阈值下特征点为Ｃ、Ｄ、Ｅ、Ｇ、Ｉ、Ｏ。由于阈值较大，在弯曲的水平距离较小处造成非特征点Ｄ的保留以及在曲度较大处造成特征点 Ｂ、Ｆ 的缺失。

本文针对大比例尺下径向约束D-P算法提取曲 线全局特征点 *** 的不足，结合基于D-P算法特征点的选取 *** 与基于带有径向约束D-P算法特征点 的选取 *** ，提出一种改进的曲线特征点提取 *** 。核心内容为通过自适应来提取曲线的全局特征点， 先分别计算出点到间隔点连线垂距的平均数和中位数以及间隔点连线的平均数和中位数，再通过比较各自的标准差，选取各自更优的平均数或中位数作为能否保留曲线特征点的参考值，最后通过比较曲 线上每个点的弯曲程度与曲线整体弯曲程度[17-18]的 大小，来提取曲线的全局特征点。线要素化简算法的核心思想是在尽可能保持 曲线形状特征的前提下，减少其节点的数量，同时尽可能多地保留 曲线全局特征点。提取曲线全局特征点主要有以下４个步骤，见图３。

１）遍历曲线上所有的点，连接曲线上的每一个间隔点，同时过中间点做间隔点连线的垂线，见图３，依次类推，直至遍历完曲线上所有的点，垂线分别记为 Ｍ１、Ｍ２、Ｍ３…，间隔点连线的长度分别记为 Ｎ１、Ｎ２、Ｎ３…。

２）统计出每条垂线的长度 Ｍ 以及每一条间隔点 连线的长度Ｎ，计算出垂线的中位数 ＭＰ、平均数ＭＱ和标准差，同时计算出间隔点连线长度的中位数ＮＰ、平均数ＮＱ和标准差（这里的 标准差是指分别以中位数为参考值求出的标准差和 以平均数为参考值求出的标准差），标准差反映一组 数据的离散程度，标准差越小离散程度越小，标准 差越大离散程度越大，见表１和式（１）～式（８）。

中位数：将一组数从大到小或从小到大进行有序排列，位于最中间的那个数称为中位数。ＭＱ表示垂线的平均数，ＮＱ表示间隔点连线的平均数；ＭＰ表示垂线的中位数，ＮＰ表示间隔点连线的中位 数；δＭ表示垂线的标准差，δＮ 表示间隔点连线的标准差；D(M)表示垂线的方差，D(N)表示间隔点连线的方差。

３）分别比较以平均数为参考值求出的标准差和以中位数为参考值 求出的标准差值的大小，若以中位数ＭＰ为参考值计算出标准差的值小，则以垂线的中位数ＭＰ为参考值；若以平均数ＭＱ为参考值计算出的标准 差的值小，则以垂线的平均数ＭＱ为参考值。同理，若以中位数ＮＰ为参考值计算出的标准差的值小，则以间隔点连线的中位数ＮＰ为参考值；若以平均数ＮＱ为参考值计算出的标准差的值小，则以间隔点连线的平均数 ＮＱ为参考值。

４）表示曲线在i点的弯曲程度，比值越大表示曲线在该点处的弯曲程度越大，比值越小表示曲线在该点处的弯曲程度越小。这里以各自 的中位数作为参考值来说明本文的 *** ：如果 ，那么表明曲线在该点处弯曲程度较大，则选取该点作为曲线的一个特 征点；如果  ，那么表明曲线在该点处弯曲程 度较小，则不选取该点作为曲线的特征点；依次类推直至遍历完曲线上 所有的特征点，ＡＢＣＤＥＦＧＨ为原折线，ＡＣＤＥＦＧＨ为本文算法自适应后的折线见图４。

在相同的参数条件下用两种算法分别对道路和河流数据进行化简，图５和图６分别截取了部分化简结果，在处理道路、河流等曲度较平缓、弯曲水平距离较大处的线群密集要素时，径向约束D-P算法化简效率较高，但是在曲度较大处、弯曲水平距离较小处时化简结果显得较粗糙，原因是由于垂距阈值和径向约束阈值的随机性，导致在曲度较大处一些重要特征点的丢失和弯曲水平距 离较小处一些非特征点的保留造成 的（图５（ａ）Ａ、Ｂ 处及图６（ａ）Ａ、Ｂ、Ｃ、Ｄ 处）。本文算法通过自 适应来提取曲线的全局特征点，化简结果与原始数据贴合紧密，不仅精确地提取了曲度较大处的特征点，同时避免了弯曲水平距离较小处非特征 点的保留，保证了曲线原有的形状特征不发生明 显变化（图５（ｂ）及图６（ｂ））。对比道路、河流两幅图的化简结果，当线要素曲度平缓而弯 曲水平距离较大时，改进的效果并不明显，而对于曲度较大同时弯曲水平 距离较小的线要素区域，本文算法的化简效果明显优于径向约束D-P算 法，在保证了 曲线压缩的同时，以更大限度保留了曲线原来的形状特征。

１）以道路曲线进行实验效果图对比。图５为分 别依据径向约束D-P算法和本文 *** 提取道路曲线全局特征点的结果。用D-P算法提取曲线全局特征点的局部效果见图５（ａ）；用本文算法提取 曲 线全局特征点的局部效果，见图５（ｂ）。

统计两种压缩 *** 下道路曲线简前后保留点的个数、特征点个数、压缩 率、面积位移总和以及平均偏移差[19-22]的对比情况，见表２。由图５（ａ）和表２可知该道路曲线共有1475个点，当使用径向约束D-P 算法进行曲线全局特征 点提取后，道路曲线全局保留点的数量为351个， 被化简的点的数量为1124个，压缩率达到76.2％，尽管压缩率很高，但是提取曲线全局的特征点数量仅为105个，数量明显偏少，曲线上一 些重要的特 征点没有被保留下来，原因是在提取的过程中曲度较大处的一些特征点被忽略掉，同时面积位移总和为97962.37 ｍ2、平均偏移差为 23.75ｍ2都明显偏大，导致化简后相对位置发生较大变化，主要是由于垂距阈值的随 机性导致曲线在曲度较大处造成一些重要特征点缺失，在弯曲的水平距离较短处造成非特征点的保留造成的。由图５（ｂ）和表２可知在使用本文算法进行曲线全局特征点提取时，道路曲线全局保留点的数量为527个，被化简 的点的数量为948个，压缩率为 64.3％，提取曲线全局特征点的数量为167个，不论是保留点的个数还是特征点的个数均明显多于径向约束D-P算法提取的数量，压缩率也超过了一半，同时面积位移总和为65024.83m2、平均位移差为12.53ｍ，都明显低于传统 *** ，本文 *** 通过比较各自的 标准差，选取各自更优的平均 数或中位数作为能否保留曲线特征点的参考值， 然后判断曲线上每个点的弯曲程度与曲线整体弯曲程度的大小，用自适应来提取曲线的全局特征点。

２）以河流曲线进行实验效果图对比。图６为 分别依据径向约束D-P算法和本文 *** 提取河流曲线全局特征点的结果 。用D-P算法提取 河流曲线全局特征点的局部效果见图６（ａ）；用 本文算法提取曲线全局特征点的局部效果， 见 图６（ｂ）。

统计两种压缩 *** 下河流曲线化简前后保留点的数量、特征点数量、压缩率、面积位移总和、以及平均偏移差[19-22]的对比情况，见表３。

由图6(a)和表３可知该河流曲线共有6654个点， 当使用径向约D-P算法进行曲线全局特征点提 取后，河流曲线全局保留点的数量为1710个，被化简的点的数量为4944个，压缩率为74.3％，压 缩率很高，但是提取曲线全局的特征点个数仅为480个， 数量明显偏少， 同时面积位移总和为 231962.37m2、平均偏移差为25.47m都明显偏大，导致一些交叉口处[22]、曲度较大处以及曲线 弯曲水平距离较短处的特征点化简之后与原曲线 的相对位置误差可能非常大，主要是由于垂距阈值的随机性导致曲线在曲度较大处造成一些重要特征点缺 失，在弯曲的水平距离较短处造成非特 征点的保留造成的。由 图6(b)和表３可知在使用本文算法进行曲线全局特征 点提取时，河流曲线全局保留点的数量为2522个，被化简的点的数量 为4132个，压缩率为62.1％，提取曲线全局特征 点的数量为800个，不论是保留点的个数还是特征 点的个数均明显多于径向约束D-P算法提取的 数量，压缩率也超过了50％，同时面积位移总和为65924.83ｍ2、平均位移 差 为9.62ｍ都明显低于传统 *** ，因为本文通过标准差分别计算出间隔点连线 的参考值和中间点到该线垂线的参考值，通过比较曲线上每个点的弯曲程度与曲线整体弯 曲程度的大小，通过自适应来提取曲线的全局特征点。

曲线特征点的识别被广泛用于反映河流等级化简、道路化简以及等高 线的化简。线要素化简算法的核心思想是在尽可能保持曲线形状特征的前提下，尽量减少其节点的数量，所以准确提取特征点十分重要。对于道路、河流等曲线进行全局特征点提取时，传统的径向约束D-P算法提取的结果与原曲线误差可能较大，主要是由于垂距 阈值的随机性导致在曲度较大处易造成一些重要特征点缺失，在弯曲的水平距离较小处造成非特征点的保留。本文通过判断曲线上每个点的弯曲程度，设计实现了一种改进的曲线特征点提取 *** ，通过比较曲线上每个点的弯曲程度与曲线整 体弯曲程度的大小，通过自适应来提取曲线的全局特征点，能够较好地提取曲度较大处的一些重要特征点，同时能够避免弯曲水平距离较小处一些非特征点的保留，从而更大可能保持与原曲线 形状特征一致，所以本文算法更加符合实际的应用需求。