凸壳内缩法进行多密度离散点群边界检测-论文.pdf

《凸壳内缩法进行多密度离散点群边界检测-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第39卷第9期测绘科学Vo1．39NO．92014年09月ScienceofSurveyingandMappingSep．凸壳内缩法进行多密度离散点群边界检测李雯静，李少宁，邱佳，周侗(1．武汉科技大学资源与环境工程学院，武汉430081；2．南京师范大学地理科学学院，南京210046)摘要：针对现有离散点群边界检测方法对多密度点群检测结果效果不够理想这一1'7题，本文提出利用凸壳内缩法检测离散点的边界：先建立离散点群凸壳结构，再定义内缩精度后通过点群凸壳结构特征实现最适内缩精度的识别。该方法对内缩扫描区域面积会随边界点密度不

2、同而变化，因此更加适用于多密度离散点群边界的检测。通过与现有边界检测方法的对比，本文提出的方法在处理多密度离散点群的边界检测问题时具有高效性和普适性。关键词：边界检测；凸壳内缩；多密度离散点群；内缩精度【中图分类号】P208【文献标识码】A【文章编号11009—2307(2014)09—012604系的聚类分析，又是对地理目标总体分布的评价。l引言利用凸壳结构可以较好地表示目标的作用边界，离散点群的边界检测在地图学、遥感及计算但是很难准确表示边界为凹多边形的点群作用区机图形学等领域中都有广泛的应用]。目前，用域。为了得到符合真

3、实地理环境的边界形状，本于离散点边界检测的方法主要分为两类：计算几文对离散点群的凸壳边界进行内缩检测以得到最何方法和聚类边界方法。前者包括：剥离三角网适精度的边界。法]、角度法E。和AlphaShapes算法E7-83等。后者2．1边界精度有：BDKD算法]、BPGG算法

4、】叫等。现有方法能文献[6]利用离散点的平均距离作为提取凸够针对特定点群解决边界提取问题，但是其应用也壳内缩边界的参数，但是这种方法很难解决多密有一定的局限性。例如以上算法在处理多密度离散度点群的边界问题。对于点集密度较大区域的边点群时，由于边界处点密度不均

5、匀而导致检测效果界可能得到不合理的内缩检测结果，对于点集密不够理想；有些方法还要求用户对空间数据具有一度较小区域却很难检测到其边界。定先验知识，在此前提下输人参数或阈值完成边界针对多密度点群的边界提取问题，本文提出检测，否则会造成边界检测结果与实际边界不一致。内缩精度的概念，用于限定检测边界内缩区域。凸壳结构可以有效地用于点群全局结构的描离散点集P内缩精度建立过程如下：①建立离散述_】，本文利用凸壳内缩结构对离散点群的边界点集P的凸壳结构P；②点P、P为凸壳P上进行检测，利用可变的扫描面积改善多密度离散连续两点，即线段PP为一

6、凸壳边，如图1所点群的边界检测问题，同时用户在输人参数前不示；③过点P、P向凸壳内部作圆弧，使得PP需对数据充分了解。的弧度大小为；④弧PP与线段PP组成的2凸壳内缩算法弓形区域即边界检测的内缩精度，其值大小为Ct。当内缩精度a区域内离散点群的边界问题既是对地理目标临近关不包含有其他离散点时，即认为线段PP即该精作者简介：李雯静(1978)，女，副教度下的边界线。在a趋近授，现主要从事粗集、分形理论在于0时，内缩区域面积也GIS与地图综合中的应用研究。趋近于0，得到离散点的图1内缩精度a示意图E—mail：wtusm—1wj@

7、126．corn边界为凸壳；随着内缩精度值增大，同一边界线内缩面积也随之增大，得到的边界精度也越高，收稿日期i2012—12一lO如图2所示；但是当内缩精度大于兀时，扫描区基金项目：国家自然科学基金(41271449，41171350)；高校博士点域大于半圆，就易形成不断内缩的现象，得到边基金(20103207110012)界检测结果就会将内部点作为边界点，如图3所第9期李雯静等凸壳内缩法进行多密度离散点群边界检测127示。根据内缩精度与边界合理性之间的变化关系L一~／b／n(1)可知，内缩精度的取值范围一般为[0，]。a中心

8、值参数：一L凸／(一L·)(2)”曲1凸壳边界离散度：一[Ec()／E一1](3)由此得到内缩精度的估算模型如下：图2扫描区域随内缩精度a变化“∈[max(0,n-2⋯一蠢)，min(一2rarc嘶+蠢，)](4)式(1)中为凸壳面积，为离散点个数，式(2)中L为凸壳边长度，式(3)中为凸壳的节点数量，E()为凸壳第i条边界长度。2．3凸壳内缩算法流程图3口大于时的情况已知离散点集P，利用凸壳对边界点检测的算2．2内缩精度识别法流程如下：一般边界检测算法提取边界时，需要用户反1)离散点群的凸壳结构CH{E()}，E()为复调整

9、输入参数，这在很大程度上降低了算法效凸壳边，凸壳边个为数7"l；点集P一{P，uP)，率，并且在设定参数的过程之中引人人为偏见，P为凸壳点，P为非凸壳点。造成边界检测结果与实际结果不一致。本文通过2)根据第2．2节中方法，初步判断内缩精度离散点的分布特点及其凸壳特征，进行初步