海上距离元胞自动机分析法

doi:10.11947/j.AGCS.2019.20170477

测绘学报 ›› 2019, Vol. 48 ›› Issue (3): 384-392.doi: 10.11947/j.AGCS.2019.20170477

海上距离元胞自动机分析法

王加胜^1,2, 杨昆^1,2, 朱彦辉^1,2, 熊建红¹

1. 云南师范大学信息学院, 云南昆明 650500;
2. 西部资源环境地理信息技术教育部工程研究中心, 云南昆明 650500

收稿日期:2017-08-25 修回日期:2018-09-11 出版日期:2019-03-20 发布日期:2019-04-10
通讯作者: 杨昆 E-mail:kmdcynu@163.com
作者简介:王加胜(1984-),男,博士,副教授,研究方向为地理信息科学。E-mail:jersonwang@ynnu.edu.cn
基金资助:
国家自然科学基金（41501436）

Euclidean distance transform on the sea based on cellular automata modeling

WANG Jiasheng^1,2, YANG Kun^1,2, ZHU Yanhui^1,2, XIONG Jianhong¹

1. School of Information Science and Technology, Yunnan Normal University, Kunming 650500, China;
2. The Engineering Research Center of GIS Technology in Western China, Kunming 650500, China

Received:2017-08-25 Revised:2018-09-11 Online:2019-03-20 Published:2019-04-10
Supported by:
The National Natural Science Foundation of China (No. 41501436)

摘要/Abstract

摘要： 针对障碍存在情况下距离变换研究较少的问题，提出了一种基于元胞自动机的绕障欧氏距离变换方法。以南海为例，基于海陆分布数据和目标点数据，以最短绕障路径长度为元胞状态，设计了包含距离算子的元胞状态转换规则。通过元胞自动机模拟距离扩散计算过程，得到绕障距离变换结果，并分析了绕障效果和精度。结果表明：本文方法动态直观地展示了绕障距离变换过程，能够自动计算绕过障碍的最短距离；具有更新机制，能够根据邻域的变化修正状态值；为绕障距离变换问题提供了一种近似的解决途径，错误率低于3.96%，可应用于航线设计、海上救助等领域。

关键词: 距离变换, 元胞自动机, 绕障, 南海

Abstract: To explore the problem of distance transformations while obstacle existing, this paper presents an obstacle-avoiding Euclidean distance transform method based on cellular automata. This research took the South China Sea as an example, imported the data of land-sea distribution and target points, took the length of the shortest obstacle-avoiding path from current cell to the target cells as the state of a cellular, designed the state transform rule of each cellular that considering a distance operator, then simulated the propagation of obstacle-avoiding distance, and got the result raster of obstacle-avoiding distance transform. After analyzing the effect and precision of obstacle avoiding, we reached the following conclusions:first, the presented method can visually and dynamically show the process of obstacle-avoiding distance transform, can automate calculate the shortest distance bypass the land; second, the method has auto update mechanism, each cellular can rectify distance value according to its neighbor cellular during the simulation process; At last, it provides an approximate solution for exact obstacle-avoiding Euclidean distance transform, the proportional error is less than 3.96%. The proposed method can apply to the fields of shipping routes design, maritime search and rescue, and so on.

Key words: distance transform, cellular automata, obstacles avoiding, South China Sea

中图分类号:

P714

王加胜, 杨昆, 朱彦辉, 熊建红. 海上距离元胞自动机分析法[J]. 测绘学报, 2019, 48(3): 384-392.

WANG Jiasheng, YANG Kun, ZHU Yanhui, XIONG Jianhong. Euclidean distance transform on the sea based on cellular automata modeling[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(3): 384-392.

参考文献

[1] ROSENFELD A, PFALTZ J L. Sequential operations in digital picture processing[J]. Journal of the ACM, 1966, 13(4):471-494.
[2] BORGEFORS G. Distance transformations in digital images[J]. Computer Vision, Graphics, and Image Processing, 1986, 34(3):344-371.
[3] FABBRI R, COSTA L D F, TORELLI J C, et al. 2D Euclidean distance transform algorithms:a comparative survey[J]. ACM Computing Surveys, 2008, 40(1):1-44.
[4] GUSTAVSON S, STRAND R. Anti-aliased Euclidean distance transform[J]. Pattern Recognition Letters, 2011, 32(2):252-257.
[5] CARLOS J, FEDERICO E, GABRIEL J. The exact Euclidean distance transform:a new algorithm for universal path planning[J]. International Journal of Advanced Robotic Systems, 2013, 10(10):1.
[6] HILL B, BALDOCK R A. Constrained distance transforms for spatial atlas registration[J]. BMC Bioinformatics, 2015, 16(1):90.
[7] DE SMITH M J. Distance transforms as a new tool in spatial analysis, urban planning, and GIS[J]. Environment and Planning B:Planning and Design, 2004, 31(1):85-104.
[8] 秦昆. GIS空间分析理论与方法[M]. 2版. 武汉:武汉大学出版社, 2010. QIN Kun. Theories and methods of spatial analysis in GIS[M]. 2nd ed. Wuhan:Wuhan University Press, 2010.
[9] 邓敏, 赵彬彬, 徐震, 等. GIS空间目标间距离表达方法及分析[J]. 计算机工程与应用, 2011, 47(1):35-39, 45. DENG Min, ZHAO Binbin, XU Zhen, et al. Representation methods of distance between spatial objects in GIS and their analysis[J]. Computer Engineering and Applications, 2011, 47(1):35-39, 45.
[10] NOURQOLIPOUR R, SHARIFF A R, BALASUNDRAM S K, et al. A GIS-based model to analyze the spatial and temporal development of oil palm land use in kuala langat district, malaysia[J]. Environmental Earth Sciences, 2015, 73(4):1687-1700.
[11] MORONI D, PIERI G, TAMPUCCI M, et al. A proactive system for maritime environment monitoring[J]. Marine Pollution Bulletin, 2016, 102(2):316-322.
[12] WANG Jiasheng, LI Manchun, LIU Yongxue, et al. Safety assessment of shipping routes in the south China sea based on the fuzzy analytic hierarchy process[J]. Safety Science, 2014(62):46-57.
[13] 曹鸿博, 张立华, 贾帅东, 等. 电子海图最短距离航线自动生成的改进方法[J]. 武汉大学学报(信息科学版), 2011, 36(9):1107-1110. CAO Hongbo, ZHANG Lihua, JIA Shuaidong, et al. An improved method for automatically building shortest route based on electronic chart[J]. Geomatics and Information Science of Wuhan University, 2011, 36(9):1107-1110.
[14] 王军, 王美蓉. 海上突发灾难事件应急物资调度优化方法研究[J]. 中国安全科学学报, 2013, 23(1):166-170. WANG Jun, WANG Meirong. Study on optimizing of emergency resources scheduling for maritime perils[J]. China Safety Science Journal, 2013, 23(1):166-170.
[15] PERERA L P, SOARES C G. Weather routing and safe ship handling in the future of shipping[J]. Ocean Engineering, 2017(130):684-695.
[16] 陈海力, 李源惠, 刘涛. 海上救助辅助决策系统支撑平台的研究[J]. 大连海事大学学报, 2013, 39(2):44-48. CHEN Haili, LI Yuanhui, LIU Tao. Research on marine rescue assistant decision system support platform[J]. Journal of Dalian Maritime University, 2013, 39(2):44-48.
[17] 黎夏, 叶嘉安, 刘小平, 等. 地理模拟系统:元胞自动机与多智能体[M]. 北京:科学出版社, 2007. LI Xia, YE Jiaan, LIU Xiaoping, et al. Geographic simulation system:cellular automata and multi-agent[M]. Beijing:Science Press, 2007.
[18] 杨青生, 黎夏. 多智能体与元胞自动机结合及城市用地扩张模拟[J]. 地理科学, 2007, 27(4):542-548. YANG Qingsheng, LI Xia. Integration of multi-agent systems with cellular automata for simulating urban land expansion[J]. Scientia Geographica Sinica, 2007, 27(4):542-548.
[19] 杨小雄, 刘耀林, 王晓红, 等. 基于约束条件的元胞自动机土地利用规划布局模型[J]. 武汉大学学报(信息科学版), 2007, 32(12):1164-1167. YANG Xiaoxiong, LIU Yaolin, WANG Xiaohong, et al. Land utility planning layout model based on constrained conditions cellular automata[J]. Geomatics and Information Science of Wuhan University, 2007, 32(12):1164-1167.
[20] 余雷, 薛惠锋, 高晓燕, 等. 基于元胞自动机的传染病传播模型研究[J]. 计算机工程与应用, 2007, 43(2):196-198, 237. YU Lei, XUE Huifeng, GAO Xiaoyan, et al. Epidemic spread model based on cellular automata[J]. Computer Engineering and Applications, 2007, 43(2):196-198, 237.
[21] 贾斌, 高自友, 李克平, 等. 基于元胞自动机的交通系统建模与模拟[M]. 北京:科学出版社, 2007. JIA Bin, GAO Ziyou, LI Keping, et al. Models and simulations of traffic system based on the theory of cellular automaton[M]. Beijing:Science Press, 2007.
[22] 吕春杉, 翁文国, 杨锐, 等. 基于运动模式和元胞自动机的火灾环境下人员疏散模型[J]. 清华大学学报(自然科学版), 2007, 47(12):2163-2167. LÜ Chunshan, WENG Wenguo, YANG Rui, et al. Fire evacuation model based on motor schema and cellular automaton[J]. Journal of Tsinghua University (Science and Technique), 2007, 47(12):2163-2167.
[23] 王海鹰, 张新长, 康停军, 等. 基于CA模型的3维虚拟城市构建方法研究[J]. 测绘学报, 2009, 38(6):556-561. DOI:10.3321/j.issn:1001-1595.2009.06.015. WANG Haiying, ZHANG Xinchang, KANG Tingjun, et al. Research on the methods of 3D virtual city construction based on CA model[J]. Acta Geodaetica et Cartographica Sinica, 2009, 38(6):556-561. DOI:10.3321/j.issn:1001-1595.2009.06.015.
[24] 余接情, 石珍, 吴立新, 等. 基于SDOG-ESSG的地球系统元胞自动机框架及其应用试验[J]. 测绘学报, 2016, 45(S1):40-47. DOI:10.11947/j.AGCS.2016.F005. YU Jieqing, SHI Zhen, WU Lixin, et al. The framework of earth system cellular automata based on SDOG-ESSG and its preliminary experiment[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(S1):40-47. DOI:10.11947/j.AGCS.2016.F005.
[25] LI Dewei, HAN Baoming. Behavioral effect on pedestrian evacuation simulation using cellular automata[J]. Safety Science, 2015(80):41-55.
[26] MASOUDI-NEJAD A, BIDKHORI G, ASHTIANI S, et al. Cancer systems biology and modeling:microscopic scale and multiscale approaches[J]. Seminars in Cancer Biology, 2015(30):60-69.
[27] KAMUSOKO C, GAMBA J. Simulating urban growth using a random forest-cellular automata (RF-CA) model[J]. ISPRS International Journal of Geo-Information, 2015, 4(2):447-470.
[28] LI Xia, CHEN Yimin, LIU Xiaoping, et al. Experiences and issues of using cellular automata for assisting urban and regional planning in China[J]. International Journal of Geographical Information Science, 2017, 31(8):1606-1629.
[29] 周明, 王韩民, 吴晓军. 基于元胞自动机的距离变换方法[J]. 陕西师范大学学报(自然科学版), 2006, 34(2):13-15, 19. ZHOU Ming, WANG Hanmin, WU Xiaojun. A distance transform method based on cellular automata[J]. Journal of Shaanxi Normal University (Natural Science Edition), 2006, 34(2):13-15, 19.

海上距离元胞自动机分析法

Euclidean distance transform on the sea based on cellular automata modeling

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

编辑推荐

Metrics

本文评价

[1]	谢志文, 王海军, 张彬, 黄鑫鑫. 城市扩展元胞自动机多结构卷积神经网络模型[J]. 测绘学报, 2020, 49(3): 375-385.
[2]	丁凯, 李清泉, 朱家松, 汪驰升, 管明雷, 崔扬, 杨超, 徐天. 运用MODIS遥感数据评测南海北部区域机载激光雷达测深系统参数[J]. 测绘学报, 2018, 47(2): 180-187.
[3]	王鹤, 曾永年. 城市扩展极限学习机模型[J]. 测绘学报, 2018, 47(12): 1680-1690.
[4]	余接情, 石珍, 吴立新, 邢松伟, 贾永基. 基于SDOG-ESSG的地球系统元胞自动机框架及其应用试验[J]. 测绘学报, 2016, 45(S1): 40-47.
[5]	刘小凤吴艳兰胡海. 面状要素的多层次骨架线提取[J]. , 2013, 42(4): 0-0.
[6]	王海鹰,张新长. 基于CA模型的三维虚拟城市构建方法研究[J]. 测绘学报, 2009, 38(6): 0-501.
[7]	耿协鹏杜晓初胡鹏. 基于栅格距离变换的扩展对象空间聚类方法[J]. 测绘学报, 2009, 38(2): 0-174.