利用三角剖分骨架图提取简单多边形目标中心点

卢威, 艾廷华

卢威, 艾廷华. 利用三角剖分骨架图提取简单多边形目标中心点[J]. 武汉大学学报 ( 信息科学版), 2020, 45(3): 337-343. DOI: 10.13203/j.whugis20180236
引用本文: 卢威, 艾廷华. 利用三角剖分骨架图提取简单多边形目标中心点[J]. 武汉大学学报 ( 信息科学版), 2020, 45(3): 337-343. DOI: 10.13203/j.whugis20180236
LU Wei, AI Tinghua. Center Point Extraction of Simple Area Object Using Triangulation Skeleton Graph[J]. Geomatics and Information Science of Wuhan University, 2020, 45(3): 337-343. DOI: 10.13203/j.whugis20180236
Citation: LU Wei, AI Tinghua. Center Point Extraction of Simple Area Object Using Triangulation Skeleton Graph[J]. Geomatics and Information Science of Wuhan University, 2020, 45(3): 337-343. DOI: 10.13203/j.whugis20180236

利用三角剖分骨架图提取简单多边形目标中心点

基金项目: 

国家自然科学基金 41531180

国家重点研发计划 2017YFB0503500

详细信息
    作者简介:

    卢威, 博士生, 主要从事地理可视化与空间认知理论与方法研究。whuluwei@whu.edu.cn

    通讯作者:

    艾廷华, 博士, 教授。tinghuaai@whu.edu.cn

  • 中图分类号: P208

Center Point Extraction of Simple Area Object Using Triangulation Skeleton Graph

Funds: 

The National Natural Science Foundation of China 41531180

the National Key Research and Development Program of China 2017YFB0503500

More Information
    Author Bio:

    LU Wei, PhD candidate, specializes in geo-visualization and spatial cognition. E-mail: whuluwei@whu.edu.cn

    Corresponding author:

    AI Tinghua, PhD, professor. E-mail: tinghuaai@whu.edu.cn

  • 摘要: 在地图学与地理信息科学领域,面状目标中心点的提取涉及空间关系计算、地图注记配置、地图综合等多个领域。几何形心作为面状目标的形状中心是领域内的常用方法,但在实际应用中由于面状目标形状特征的多样性,利用形心计算的中心点常常不能真实地表达区域中心,比如形心处于区域外部。利用面状目标三角剖分骨架图,考虑面状目标的几何特征与区域连接的拓扑特征,结合图论中的中心性度量方法,定义了面状目标的两种不同的中心点:邻近中心点和居间中心点,分析并讨论了所提出方法的相关特殊情形。利用中国448个地、市区域面要素进行认知实验,讨论了所提出的中心点计算方法的实用性和适用性。实验结果表明,所提出的两种中心点位置可以保证在多边形内部,同时也较好地体现了面状目标的拓扑和几何特征,符合形状特征的视觉认知,可以满足不同应用场景下中心点计算的需求。
    Abstract: In the area of cartography and geographic information science, the center points of area features are related to many fields. The centroid is a conventional choice for center point of area feature. However, it is not suitable for features with a complex shape for the center point may be outside the area or not fit the visual center so well. We propose a novel method to calculate the center point of area feature based on triangulation skeleton graph. We define two kinds of centrality of vertices in skeleton graph according to the centrality theory in graph and network analysis. Through the measurement of vertices centrality, the center points of polygon area features are defined as the vertices with maximum centrality. The complexity and special cases are discussed. A cognitive experiment is designed to test the usability of our method based on 448 districts and cities area features. The experimental result shows that the method is more suitable for complex area features than conventional centroid.
  • 图  1   三角剖分示意图

    Figure  1.   Triangulation Decomposition

    图  2   一个多边形骨架图中的所有骨架路径

    Figure  2.   All Skeleton Paths of a Skeleton Graph

    图  3   骨架边覆盖长度、宽度定义示意图

    Figure  3.   Cover Length, Width of Skeleton Edge

    图  4   中心点计算步骤

    Figure  4.   Procedure of Center Point Extraction

    图  5   两种中心性实例

    Figure  5.   Two Centrality Cases

    图  6   特例情况

    Figure  6.   Special Cases

    图  7   实验数据

    Figure  7.   Experiment Data

    图  8   实验案例示意图

    Figure  8.   Experiment Cases

    图  9   形状特征描述子示意图

    Figure  9.   Diagram of Shape Descriptors

    图  10   不同中心点形状分布特征

    Figure  10.   Shape Descriptor Distribution of Different Center Points

    表  1   实验测试结果

    Table  1   Experiment Results

    人数比例 形心 邻近中心 居间中心
    0.2 431 251 96
    0.4 379 154 30
    0.6 327 114 13
    0.8 198 36 2
    1 0 0 0
    下载: 导出CSV
  • [1] 胡鹏, 王海军, 邵春丽, 等.论多边形中轴问题和算法[J].武汉大学学报·信息科学版, 2005, 30(10):853-857 http://ch.whu.edu.cn/CN/abstract/abstract2287.shtml

    Hu Peng, Wang Haijun, Shao Chunli, et al. Polygon Medial Axis Problem and the Algorithm[J]. Geomatics and Information Science of Wuhan University, 2005, 30(10):853-857 http://ch.whu.edu.cn/CN/abstract/abstract2287.shtml

    [2] 孙毅中, 姚驰, 陈少勤, 等.顾及几何特征的地理要素空间位置唯一性标识方法[J].武汉大学学报·信息科学版, 2012, 37(12):1486-1489 http://ch.whu.edu.cn/CN/abstract/abstract404.shtml

    Sun Yizhong, Yao Chi, Chen Shaoqin, et al. Geographical Elements' Spatial Location Identification Considering Geometric Features[J]. Geomatics and Information Science of Wuhan University, 2012, 37(12):1486-1489 http://ch.whu.edu.cn/CN/abstract/abstract404.shtml

    [3] 刘雅文, 李精忠, 张俊, 等.利用骨架线端点匹配进行面状要素渐变变换[J].武汉大学学报·信息科学版, 2018, 43(3):392-398 http://ch.whu.edu.cn/CN/abstract/abstract5997.shtml

    Liu Yawen, Li Jingzhong, Zhang Jun, et al. The Morphing of Area Features Based on Skeleton Line Endpoint Matching[J]. Geomatics and Information Science of Wuhan University, 2018, 43(3):392-398 http://ch.whu.edu.cn/CN/abstract/abstract5997.shtml

    [4]

    Yuan Shuxin, Tao Chuang. Development of Conflation Components[C]. Geoinformatics Conference, Ann Arbor, Michigon, USA, 1999

    [5] 王琤, 李霖, 朱海红.小比例尺地图面状水系名称注记自动配置研究[J].武汉大学学报·信息科学版, 2007, 32(6):544-547 http://ch.whu.edu.cn/CN/abstract/abstract1912.shtml

    Wang Cheng, Li Lin, Zhu Haihong. Automatic Name Placement for Area Water Features on Small Scale Maps[J]. Geomatics and Information Science of Wuhan University, 2007, 32(6):544-547 http://ch.whu.edu.cn/CN/abstract/abstract1912.shtml

    [6] 张晓通, 李霖, 舒亚东, 等.面状要素注记智能化配置方法研究[J].武汉大学学报·信息科学版, 2008, 33(7):762-765 http://ch.whu.edu.cn/CN/abstract/abstract1636.shtml

    Zhang Xiaotong, Li Lin, Shu Yadong, et al. Intelligent Automated Cartographic Text Placement of Area Features[J].Geomatics and Information Science of Wuhan University, 2008, 33(7):762-765 http://ch.whu.edu.cn/CN/abstract/abstract1636.shtml

    [7] 王骁, 钱海忠, 何海威, 等.利用空白区域骨架线网眼匹配多源面状居民地[J].测绘学报, 2015, 44(8):927-935 http://d.old.wanfangdata.com.cn/Periodical/chxb201508016

    Wang Xiao, Qian Haizhong, He Haiwei, et al. Matching Multi-source Areal Habitations with Skeleton Line Mesh of Blank Region[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(8):927-935 http://d.old.wanfangdata.com.cn/Periodical/chxb201508016

    [8] 唐雪华, 秦昆, 孟令奎.基于拓扑参考的定性方向关系矩阵描述模型[J].测绘学报, 2014, 43(4):396-403 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=chxb201404013

    Tang Xuehua, Qin Kun, Meng Lingkui. A Qualitative Matrix Model of Direction-Relation Based on Topological Reference[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(4):396-403 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=chxb201404013

    [9]

    Leu J G. Computing a Shape's Moments from Its Boundary[J]. Pattern Recognition, 1991, 24(10):949-957 doi: 10.1016/0031-3203(91)90092-J

    [10]

    Garcia-Castellanos D, Lombardo U. Poles of Inaccessibility:A Calculation Algorithm for the Remotest Places on Earth[J]. Scottish Geographical Journal, 2007, 123(3):227-233 doi: 10.1080/14702540801897809

    [11]

    Kang H, Elhami S, Saalfeld A. Using Shape Analyses for Placement of Polygon Labels[C]. ESRI International User Conference, San Diego, California, USA, 2001

    [12] 陈涛, 艾廷华.多边形骨架线与形心自动搜寻算法研究[J].武汉大学学报·信息科学版, 2004, 29(5):443-446, 455 http://ch.whu.edu.cn/CN/abstract/abstract4672.shtml

    Chen Tao, Ai Tinghua. Automatic Extraction of Skeleton and Center of Area Feature[J]. Geomatics and Information Science of Wuhan University, 2004, 29(5):443-446, 455 http://ch.whu.edu.cn/CN/abstract/abstract4672.shtml

    [13] 白翔.基于骨架的形状匹配中若干问题的研究[D].武汉: 华中科技大学, 2009

    Bai Xiang. Contributions to Several Issues in Skeleton-Based Shape Matching[D]. Wuhan: Huazhong University of Science and Technology, 2009

    [14]

    Bai Xiang, Latecki L J. Path Similarity Skeleton Graph Matching[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(7):1282-1292 doi: 10.1109/TPAMI.2007.70769

    [15]

    Borgatti S P, Everett M G. A Graph-Theoretic Perspective on Centrality[J]. Social Networks, 2006, 28(4):466-484 doi: 10.1016/j.socnet.2005.11.005

    [16]

    Opsahl T, Agneessens F, Skvoretz J. Node Centrality in Weighted Networks:Generalizing Degree and Shortest Paths[J]. Social Networks, 2010, 32(3):245-251 doi: 10.1016-j.socnet.2010.03.006/

    [17]

    Jiang Bin, Liu Xintao. Scaling of Geographic Space from the Perspective of City and Field Blocks and Using Volunteered Geographic Information[J]. International Journal of Geographical Information Science, 2012, 26(2):215-229 http://d.old.wanfangdata.com.cn/OAPaper/oai_arXiv.org_1009.3635

    [18]

    Rogerson P A. A New Method for Finding Geographic Centers, with Application to U.S. States[J]. The Professional Geographer, 2015, 67(4):686-694 doi: 10.1080/00330124.2015.1062707

    [19]

    Blum H. Biological Shape and Visual Science (Part Ⅰ)[J]. Journal of Theoretical Biology, 1973, 38(2):205-287 doi: 10.1016/0022-5193(73)90175-6

    [20]

    Aigner W, Aurenhammer F, Juttler B. On Triangulation Axes of Polygons[J]. Information Processing Letters, 2015, 115(1):45-51 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=c0de6cca6f4182ce119578e55b41f5de

    [21]

    Ai Tinghua, van Oosterom P. GAP-Tree Extensions Based on Skeletons[C].The 10th International Symposium on Spatial Data Handling, Ottawa, Canada, 2002

    [22]

    de Berg M, Cheong O, van Kreveld M. Computational Geometry:Algorithms and Applications[M]. Santa Clara:Springer, 2008

  • 期刊类型引用(10)

    1. 曾广泉,马韬,张孟希,戴妍,陈凯文,丁继辉,俞双恩,王中文. 基于无人机多光谱影像的不同施氮量水稻LAI反演方法研究. 江苏农业科学. 2024(20): 41-48 . 百度学术
    2. 高钰琪,许桂玲,冯跃华,王晓珂,任红军,由晓璇,韩志丽,李家乐. 基于冠层高光谱植被指数的水稻产量预测模型研究. 中国稻米. 2023(05): 38-44 . 百度学术
    3. 彭晓伟,张爱军,王楠,赵丽,杨晓楠. 高光谱技术在土壤及适种作物的研究进展. 遥感信息. 2022(01): 32-39 . 百度学术
    4. 王晓珂,刘婷婷,许桂玲,冯跃华,彭金凤,李杰,罗强鑫,韩志丽,卢苇,PHONENASAY Somsana. 基于冠层高光谱遥感的杂交水稻植被指数氮素营养诊断模型. 中国稻米. 2021(03): 21-29 . 百度学术
    5. 王浩淼,宋苗语,李翔,扈朝阳,鲁任翔,王翔,马会勤. 无人机高光谱遥感监测葡萄长势与缺株定位. 园艺学报. 2021(08): 1626-1634 . 百度学术
    6. 刘雅婷,龚龑,段博,方圣辉,彭漪. 多时相NDVI与丰度综合分析的油菜无人机遥感长势监测. 武汉大学学报(信息科学版). 2020(02): 265-272 . 百度学术
    7. 陈晓凯,李粉玲,王玉娜,史博太,侯玉昊,常庆瑞. 无人机高光谱遥感估算冬小麦叶面积指数. 农业工程学报. 2020(22): 40-49 . 百度学术
    8. 落莉莉,常庆瑞,武旭梅,杨景,李粉玲,王琦. 夏玉米叶片光合色素含量高光谱估算. 干旱地区农业研究. 2019(04): 178-183 . 百度学术
    9. 张良培,刘蓉,杜博. 使用量子优化算法进行高光谱遥感影像处理综述. 武汉大学学报(信息科学版). 2018(12): 1811-1818 . 百度学术
    10. 李亚妮,鲁蕾,刘勇. 基于PROSAIL模型的水稻田缨帽三角-叶面积指数模型及其应用. 应用生态学报. 2017(12): 3976-3984 . 百度学术

    其他类型引用(17)

图(10)  /  表(1)
计量
  • 文章访问数:  1928
  • HTML全文浏览量:  291
  • PDF下载量:  130
  • 被引次数: 27
出版历程
  • 收稿日期:  2018-06-11
  • 发布日期:  2020-03-04

目录

    /

    返回文章
    返回