地图学与地理信息

多约束的平面点集形状重构方法

  • 朱杰 ,
  • 孙毅中
展开
  • 1. 南京师范大学虚拟地理环境教育部重点实验室, 江苏 南京 210023;
    2. 江苏省地理信息资源开发与利用协同创新中心, 江苏 南京 210023
朱杰(1989-),男,博士生,研究方向为城市空间数据表达与挖掘。E-mail:Chu_Je@163.com

收稿日期: 2016-03-30

  修回日期: 2016-10-27

  网络出版日期: 2017-03-07

基金资助

国家自然科学基金(41671392);公安部科技强警基础工作专项(2015GABJC39)

An Efficient Approach to Shape Reconstruction from Planar Point Set Based on Multi-constraints

  • ZHU Jie ,
  • SUN Yizhong
Expand
  • 1. Key Laboratory of Virtual Geographic Environment of Ministry of Education, Nanjing Normal University, Nanjing 210023, China;
    2. Jiangsu Center for Collaborative Innovation in Geographical Information Resource Development and Application, Nanjing 210023, China

Received date: 2016-03-30

  Revised date: 2016-10-27

  Online published: 2017-03-07

Supported by

The National Natural Science Foundation of China (No.41671392),Special Program for basic research of Sci-tech Police of Ministry of Public Security (No.2015GABJC39)

摘要

针对平面点集空间分布的复杂性,本文提出了一种基于Delaunay三角网的平面点集形状重构方法。首先采用一种简单且实用的数据结构以表达Delaunay三角网中嵌入的几何信息和拓扑信息,然后由外向内迭代过滤Delaunay三角网得到一个大概边界,最后进一步考虑边界的凹凸信息和空洞现象,获取最终的精细边界。试验结果表明与其他典型的Delaunay三角网重构方法相比,本文提出的算法能更好地适用于平面点集空间分布的复杂性,通过所构建的数学模型实现了凸凹多边形内外边界提取。

本文引用格式

朱杰 , 孙毅中 . 多约束的平面点集形状重构方法[J]. 测绘学报, 2017 , 46(2) : 253 -264 . DOI: 10.11947/j.AGCS.2017.20160122

Abstract

An efficient algorithm to boundary representation from a planar point set in order to adapt the complexity of spatial distribution was presented in this paper. At first, an appropriate and practical data structure was designed to express geometric information and topological information, which provides an easy access to links embedded in DT serving as a basis for the filtering procedures; then the algorithm generates rough boundary based on an iterative removal of Delaunay triangulation. Furthermore, a mathematic formulation for cavities and holes was given and a statistical method to detect them was designed. Finally, a series of experiments including both simulated and real data sets to validate the effectiveness and practicability of our algorithm was conducted.

参考文献

[1] 艾廷华, 刘耀林. 保持空间分布特征的群点化简方法[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.
[2] GALTON A,DUCKHAM M.What is the Region Occupied by a Set of Points?[M]//RAUBAL M, MILLER H J, FRANK A U, et al. Geographic Information Science. Berlin Heidelberg:Springer, 2006:81-98.
[3] 李佳田,康顺,罗富丽.利用层次Voronoi图进行点群综合[J]. 测绘学报, 2014, 43(12):1300-1306. DOI:10.13485/j.cnki.11-2089.2014.0166. LI Jiatian, KANG Shun, LUO Fuli. Point Group Generalization Method Based on Hierarchical Voronoi Diagram[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(12):1300-1306. DOI:10.13485/j.cnki.11-2089.2014.0166.
[4] ZHU Chao, ZHANG Xiaopeng, HU Baogang, et al. Reconstruction of Tree Crown Shape from Scanned Data[M]//PAN Zhigeng, ZHANG Xiaopeng, RHALIBI A E, et al. Technologies for E-learning and Digital Entertainment. Berlin Heidelberg:Springer, 2008:745-756.
[5] 孙颖, 张新长, 康停军, 等. 改进GAC模型在点云和影像自动提取建筑物边界中的应用[J]. 测绘学报, 2013, 42(3):337-343, 350. SUN Ying, ZHANG Xinchang, KANG Tingjun, et al. Improved GAC Model for Automatic Building Extraction from LiDAR Point Clouds and Aerial Image[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(3):337-343, 350.
[6] 孙颖, 张新长, 罗国玮. 从机载激光雷达点云提取建筑物屋顶边界的活动轮廓模型改进方法[J]. 测绘学报, 2014, 43(6):620-626, 636. DOI:10.13485/j.cnki.11-2089.2014.0106. SUN Ying, ZHANG Xinchang, LUO Guowei. Improved Active Contour Model for Building Roof Boundary Extraction from LiDAR Point Cloud[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(6):620-626, 636. DOI:10.13485/j.cnki.11-2089.2014.0106.
[7] KISILEVICH S, MANSMANN F, BAK P, et al. Where Would You Go on Your Next Vacation? A Framework for Visual Exploration of Attractive Places[C]//Proceedings of 2010 Second International Conference on Advanced Geographic Information Systems, Applications, and Services(GEOPROCESSING). St. Maarten:IEEE, 2010:21-26.
[8] 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.
[9] 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.
[10] SAMPATH A,SHAN Jie. Building Boundary Tracing and Regularization from Airborne LiDAR Point Clouds[J]. Photogrammetric Engineering & Remote Sensing, 2007, 73(7):805-812.
[11] 程效军, 何桂珍. 适用于多值曲面修复的空洞边界提取方法及应用[J]. 测绘学报, 2012, 41(6):831-837. CHENG Xiaojun, HE Guizhen. The Method and Application of Hole Boundary Extraction for Multi-valued Surface Repair[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(6):831-837.
[12] 李雯静, 李少宁, 邱佳, 等. 凸壳内缩法进行多密度离散点群边界检测[J]. 测绘科学, 2014, 39(9):126-129. LI Wenjing, LI Shaoning, QIU Jia, et al. Boundary Detection of Multi-density Point Cluster Using Convex Hull Retracted Method[J]. Science of Surveying and Mapping, 2014, 39(9):126-129.
[13] BOISSONNAT J D. Geometric Structures for Three-dimensional Shape Representation[J]. ACM Transactions on Graphics (TOG), 1984, 3(4):266-286.
[14] 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.
[15] KOLINGEROVÁ I, ŽALIK B. Reconstructing Domain Boundaries Within A Given Set of Points, Using Delaunay Triangulation[J]. Computers & Geosciences, 2006, 32(9):1310-1319.
[16] 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.
[17] 黄先锋, 程晓光, 张帆, 等. 基于边长比约束的离散点准确边界追踪算法[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.
[18] 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.
[19] 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.
[20] MELKEMI M, DJEBALI M. Computing the Shape of A Planar Points Set[J]. Pattern Recognition, 2000, 33(9):1423-1436.
[21] CHEVALLIER N, MAILLOT Y. Boundary of a Non-uniform Point Cloud for Reconstruction:Extended Abstract[C]//Proceedings of the 27th Annual ACM Symposium on Computational Geometry. New York:ACM, 2011:510-518.
[22] KAZHDAN M, HOPPE H. Screened Poisson Surface Reconstruction[J]. ACM Transactions on Graphics (TOG), 2013, 32(3):29.
[23] 顾天奇, 张雷, 冀世军, 等. 封闭离散点的曲线拟合方法[J]. 吉林大学学报(工学版), 2015, 45(2):437-441. GU Tianqi, ZHANG Lei, JI Shijun, et al. Curve Fitting Method for Closed Discrete Points[J]. Journal of Jilin University(Engineering and Technology Edition), 2015, 45(2):437-441.
[24] MERRY B, GAIN J, MARAIS P. Moving Least-squares Reconstruction of Large Models with GPUs[J]. IEEE Transactions on Visualization and Computer Graphics, 2014, 20(2):249-261.
[25] MISTRY S,NIRANJAN U N, GOPI M. Puzzhull:Cavity and Protrusion Hierarchy to Fit Conformal Polygons[J]. Computer-Aided Design, 2014, 46:233-238.
[26] 武晓波, 王世新, 肖春生. Delaunay三角网的生成算法研究[J]. 测绘学报, 1999, 28(1):28-35. WU Xiaobo, WANG Shixin, XIAO Chunsheng. A New Study of Delaunay Triangulation Creation[J]. Acta Geodaetica et Cartographica Sinica, 1999, 28(1):28-35.
[27] 艾廷华, 郭仁忠. 基于格式塔识别原则挖掘空间分布模式[J]. 测绘学报, 2007, 36(3):302-308. AI Tinghua, GUO Renzhong. Polygon Cluster Pattern Mining Based on Gestalt Principles[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(3):302-308.
[28] ESTIVILL-CASTRO V,LEE I.Argument Free Clustering for Large Spatial Point-data Sets Via Boundary Extraction from Delaunay Diagram[J]. Computers, Environment and Urban Systems, 2002, 26(4):315-334.
[29] PAKHIRA M K, BANDYOPADHYAY S, MAULIK U. Validity Index for Crisp and Fuzzy Clusters[J]. Pattern Recognition, 2004, 37(3):487-501.
[30] ESTIVILL-CASTRO V,LEE I. Multi-level Clustering and Its Visualization for Exploratory Spatial Analysis[J]. GeoInformatica, 2002, 6(2):123-152.
[31] 沈蔚, 李京, 陈云浩, 等. 基于LiDAR数据的建筑轮廓线提取及规则化算法研究[J]. 遥感学报, 2008, 12(5):692-698. SHEN Wei, LI Jing, CHEN Yunhao, et al. Algorithms Study of Building Boundary Extraction and Normalization Based on LIDAR Data[J]. Journal of Remote Sensing, 2008, 12(5):692-698.
文章导航

/