顾及Gestalt邻近与简化原则的平面点集形状重建

doi:10.11947/j.AGCS.2020.20190406

测绘学报 ›› 2020, Vol. 49 ›› Issue (11): 1485-1496.doi: 10.11947/j.AGCS.2020.20190406

顾及Gestalt邻近与简化原则的平面点集形状重建

颜金彪^1,2, 吴波¹, 彭馨¹

1. 江西师范大学地理与环境学院, 江西南昌 330022;
2. 衡阳师范学院传统村镇文化数字化保护与创意利用技术国家地方联合工程实验室, 湖南衡阳 421002

收稿日期:2019-09-24 修回日期:2020-06-05 发布日期:2020-11-25
通讯作者: 吴波 E-mail:wavelet778@sohu.com
作者简介:颜金彪(1987-),男,博士生,研究方向为时空数据挖掘理论与应用。E-mail:jbyan@hynu.edu.cn
基金资助:
国家自然科学基金（41961055）；湖南省教育厅优秀青年项目（19B078；19C0272）；衡阳市社科基金（2018B（I）002）；传统村镇文化数字化保护与创意利用技术国家地方联合工程实验室开放基金（CTCZ18K01）；国家重点研发计划（2018YFE0207800）

A method to shape reconstruction from planar point sets with Gestalt proximity and simplification principle

YAN Jinbiao^1,2, WU Bo¹, PENG Xin¹

1. School of Geography and Environment, Jiangxi Normal University, Nanchang 330022, China;
2. National-Local Joint Engineering Laboratory on Digital Preservation and Innovative Technologies for the Culture of Traditional Villages and Towns, Hengyang Normal University, Hengyang 421002, China

Received:2019-09-24 Revised:2020-06-05 Published:2020-11-25
Supported by:
The National Natural Science Foundation of China (No. 41961055);The Outstanding Youth Project of Education Department of Hunan Province (Nos. 19B078;19C0272);The Hengyang Social Science Fund (No. 2018B (I) 002);The Open Fund Project of National-Local Joint Engineering Laboratory on Digital Preservation and Innovative Technologies for the Culture of Traditional Villages and Towns (No. CTCZ18K01);The National Key Research and Development Program of China (No. 2018YFE0207800)

摘要/Abstract

摘要： 针对经典Delaunay三角网平面点集形状重构方法存在的经验参数确定和容易出现不符合实际情况的碎洞问题，提出了一种顾及Gestalt邻近与简化原则的Delaunay三角网平面点集形状重构的算法SRGT。首先根据邻近性原则，采用双极差粗差探测技术来识别和定位Delaunay三角网中的极长边，逐步细化三角网中的内外边界；然后基于简化性原则，将形状重构的碎洞优化转化为粗差探测问题，并利用3σ粗差探测原则来实现碎洞的剔除。采用模拟与真实数据验证了本文算法的有效性。与4种经典算法（α-shape、χ-shape、边长比约束法以及∂RGG）进行对照试验，表明本文算法的优越性。模拟数据表明SRGT在面状点集为均匀或随机分布时，无须设置先验参数即可有效提取复杂形状的内外边界，并且L²误差范数值明显低于其余4种方法。真实案例的试验结果也表明本文算法在工程实践中具有良好应用效果。

关键词: 平面点集, Delaunay三角网, Gestalt原则, 形状重建, 粗差探测

Abstract: The widely used shape reconstruction algorithms based on Delaunay triangulation are far from sophisticated,and some problems are to be further addressed. First of all, the current methods involve a few of user-defined parameters, obstructing the effective use of them in practice. Secondly, the current methods cannot guarantee the perfect shape reconstruction if a planar point set follows a randomly distribution. To overcome these aforementioned problems, a method for planar point set shape reconstruction, namely SRGT (shape reconstruction based on Gestalt) based on Gestalt proximity and simplification is developed. On the one hand, based on the proximity theory, the gross error detection technique is used to identify and locate the extreme long edges in the Delaunay triangulation network, and then the inner and outer boundaries of the Delaunay are refined step by step. On the other hand, according to the simplification theory of Gestalt, the inner and outer holes are optimized by gross error detection technique again, and finally the small holes are removed from the list of inner boundary set. To validate the effectiveness of the proposed method, the SRGT was validated on several cases, and 4 widely used algorithms, i.e. α-shape, χ-shape, ∂RGG, and edge length ratios were selected for comparisons. The results demonstrate that SRGT can achieve the fine shape reconstruction from planar point sets in both uniform and random distribution. Moreover, the SRGT generally outperforms the other 4 methods in terms of the L² measure. Finally, the shape reconstructions with the SRGT using two actual datasets corresponding to typical GIS applications were implemented to verify the effectiveness of the proposed method, and the results consistently suggest the superior ability of the SRGT.

Key words: planar point set, Delaunay triangulation, Gestalt, shape reconstruction, gross error detection

中图分类号:

P208

颜金彪, 吴波, 彭馨. 顾及Gestalt邻近与简化原则的平面点集形状重建[J]. 测绘学报, 2020, 49(11): 1485-1496.

YAN Jinbiao, WU Bo, PENG Xin. A method to shape reconstruction from planar point sets with Gestalt proximity and simplification principle[J]. Acta Geodaetica et Cartographica Sinica, 2020, 49(11): 1485-1496.

参考文献

[1] MELKEMI M, DJEBALI M. Computing the shape of a planar points set[J]. Pattern Recognition, 2000, 33(9):1423-1436.
[2] ALANI H, JONES C B, TUDHOPE D. Voronoi-based region approximation for geographical information retrieval with gazetteers[J]. International Journal of Geographical Information Science, 2001, 15(4):287-306.
[3] KOLINGEROVÁ I, ŽALIK B. Reconstructing domain boundaries within a given set of points, using Delaunay triangulation[J]. Computers & Geosciences, 2006, 32(9):1310-1319.
[4] 黄先锋, 程晓光, 张帆, 等. 基于边长比约束的离散点准确边界追踪算法[J]. 武汉大学学报(信息科学版), 2009, 34(6):688-691. HUANG Xianfeng, CHENG Xiaoguang, ZHANG Fan, et al. Boundary tracing from irregular points based on ratio of edge length[J]. Geomatics and Information Science of Wuhan University, 2009, 34(6):688-691.
[5] LIU Yu, YUAN Yihong, XIAO Danqing, et al. A point-set-based approximation for areal objects:a case study of representing localities[J]. Computers, Environment and Urban Systems, 2010, 34(1):28-39.
[6] HU Yingjie, GAO Song, JANOWICZ K, et al. Extracting and understanding urban areas of interest using geotagged photos[J]. Computers, Environment and Urban Systems, 2015, 54:240-254.
[7] 杨伟, 艾廷华. 运用约束Delaunay三角网从众源轨迹线提取道路边界[J]. 测绘学报, 2017, 46(2):237-245. DOI:10.11947/j.AGCS.2017.20160233. YANG Wei, AI Tinghua. The extraction of road boundary from crowdsourcing trajectory using constrained Delaunay triangulation[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(2):237-245. DOI:10.11947/j.AGCS.2017.20160233.
[8] LI Bin, ZHAO Xiaofa, CHEN Yong, et al. Three dimensional laser point cloud slicing method for calculating irregular volume[J]. Journal of Geodesy and Geoinformation Science, 2019, 2(4):31-43.
[9] ZHU Jie, SUN Yizhong, PANG Yueyong. A density based algorithm to detect cavities and holes from planar points[J]. Computers & Geosciences, 2017, 109:178-193.
[10] EDELSBRUNNER H, KIRKPATRICK D, SEIDEL R. On the shape of a set of points in the plane[J]. IEEE Transactions on Information Theory, 1983, 29(4):551-559.
[11] CHAUDHURI A R, CHAUDHURI B B, PARUI S K. A novel approach to computation of the shape of a dot pattern and extraction of its perceptual border[J]. Computer Vision and Image Understanding, 1997, 68(3):257-275.
[12] CHEVALLIER N, MAILLOT Y. Boundary of a non-uniform point cloud for reconstruction[C]//Proceedings of the 27th Annual Symposium on Computational Geometry. Paris, France:ACM, 2011:510-518.
[13] DUCKHAM M, KULIK L, WORBOYS M, et al. Efficient generation of simple polygons for characterizing the shape of a set of points in the plane[J]. Pattern Recognition, 2008, 41(10):3224-3236.
[14] PARAKKAT A D, METHIRUMANGALATH S, MUTHU-GANAPATHY R. Peeling the longest:a simple generalized curve reconstruction algorithm[J]. Computers & Graphics, 2018, 74:191-201.
[15] METHIRUMANGALATH S, PARAKKAT A D, MUTHU-GANAPATHY R. A unified approach towards reconstruction of a planar point set[J]. Computers & Graphics, 2015, 51:90-97.
[16] PEETHAMBARAN J, MUTHUGANAPATHY R. A non-parametric approach to shape reconstruction from planar point sets through Delaunay filtering[J]. Computer-Aided Design, 2015, 62:164-175.
[17] METHIRUMANGALATH S, KANNAN S S, PARAKKAT A D, et al. Hole detection in a planar point set:an empty disk approach[J]. Computers & Graphics, 2017, 66:124-134.
[18] MELKEMI M, ELBAZ M. A simple and efficient algorithm for dot patterns reconstruction[C]//Proceedings of 2014 IEEE International Conference on Image Processing (ICIP). Paris, France:IEEE, 2014:4727-4731.
[19] 方志明, 崔荣一, 金璟璇. 基于生物视觉特征和视觉心理学的视频显著性检测算法[J]. 物理学报, 2017, 66(10):330-343. FANG Zhiming, CUI Rongyi, JIN Jingxuan. Video saliency detection algorithm based on biological visual feature and visual psychology theory[J]. Acta Physica Sinica, 2017, 66(10):330-343.
[20] 刘陶胜, 黄声享, 李沛鸿. 基于双极差的粗差探测方法研究[J]. 大地测量与地球动力学, 2012, 32(1):80-83. LIU Taosheng, HUANG Shengxiang, LI Peihong. Research on gross error detection based on bio-pole method[J]. Journal of Geodesy and Geodynamics, 2012, 32(1):80-83.
[21] 吴浩, 卢楠, 邹进贵, 等. GNSS变形监测时间序列的改进型3σ粗差探测方法[J]. 武汉大学学报(信息科学版), 2019, 44(9):1282-1288. WU Hao, LU Nan, ZOU Jingui, et al. An improved 3σ gross error detection method for GNSS deformation monitoring time series[J]. Geomatics and Information Science of Wuhan University, 2019, 44(9):1282-1288.
[22] 李伯华, 曾荣倩, 刘沛林, 等. 基于CAS理论的传统村落人居环境演化研究——以张谷英村为例[J]. 地理研究, 2018, 37(10):1982-1996. LI Bohua, ZENG Rongqian, LIU Peilin, et al. Human settlement evolution of traditional village based on theory of complex adaptive system:a case study of Zhangguying village[J]. Geographical Research, 2018, 37(10):1982-1996.
[23] LI Qingquan, CHEN Zhipeng, HU Qingwu. A model-driven approach for 3D modeling of pylon from airborne LiDAR data[J]. Remote Sensing, 2015, 7(9):11501-11524.
[24] GALTON A, DUCKHAM M. What is the region occupied by a set of points?[M]//Geographic Information Science. Berlin:Springer, 2006, 4197:81-98.
[25] 艾廷华, 刘耀林. 保持空间分布特征的群点化简方法[J]. 测绘学报, 2002, 31(2):175-181. AI Tinghua, LIU Yaolin. A method of point cluster simplification with spatial distribution properties preserved[J]. Acta Geodaetica et Cartographica Sinica, 2002, 31(2):175-181.

顾及Gestalt邻近与简化原则的平面点集形状重建

A method to shape reconstruction from planar point sets with Gestalt proximity and simplification principle

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	姜三, 江万寿. Delaunay三角网约束下的影像稳健匹配方法[J]. 测绘学报, 2020, 49(3): 322-333.
[2]	李成名, 殷勇, 武鹏达, 刘晓丽. 一种聚集性面群中毗邻区自动识别与处理方法[J]. 测绘学报, 2019, 48(3): 363-373.
[3]	闫广峰, 岑敏仪. L₁范数探测粗差失效的观测量识别方法[J]. 测绘学报, 2019, 48(11): 1430-1438.
[4]	张亚彬, 王利, 范丽红, 曲轩宇. 组合粗差探测的MHSS ARAIM算法[J]. 测绘学报, 2019, 48(1): 9-17.
[5]	刘文凯, 刘启亮, 蔡建南. 自然邻域支持下的空间同位模式挖掘方法[J]. 测绘学报, 2019, 48(1): 95-105.
[6]	杨伟, 艾廷华. 轨迹分割与图层融合的车辆轨迹线构建道路地图方法[J]. 测绘学报, 2018, 47(12): 1650-1659.
[7]	张志衡, 彭认灿, 黄文骞, 董箭, 刘国辉. 考虑自然邻点影响域的多波束测深数据趋势面滤波改进算法[J]. 测绘学报, 2018, 47(1): 35-47.
[8]	杨伟, 艾廷华. 运用约束Delaunay三角网从众源轨迹线提取道路边界[J]. 测绘学报, 2017, 46(2): 237-245.
[9]	朱杰, 孙毅中. 多约束的平面点集形状重构方法[J]. 测绘学报, 2017, 46(2): 253-264.
[10]	郭沛沛, 李成名, 殷勇. 建筑物合并的Delaunay三角网分类过滤法[J]. 测绘学报, 2016, 45(8): 1001-1007.
[11]	郑凯, 刘站科, 肖学年, 张小红. 航空重力GPS测速多粗差探测方法[J]. 测绘学报, 2016, 45(6): 663-669.
[12]	韩元利. 网格总分并行式Delaunay三角网建模方法[J]. 测绘学报, 2015, 44(6): 702-708.
[13]	仝海波张国柱. 改进M估计的抗多个粗差定位解算方法[J]. 测绘学报, 2014, 43(4): 366-371.
[14]	张尧樊红. 一种基于等高线弯曲约束Delaunay三角网的地形特征提取新方法[J]. , 2013, 42(4): 0-0.
[15]	黄亚锋艾廷华刘耀林张航峰. 顾及地理特征保持的溺谷海岸线化简算法[J]. , 2013, 42(4): 0-0.