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

doi:10.11947/j.AGCS.2020.20190406

Abstract

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

CLC Number:

P208

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.

References

[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.