Euclidean distance transform on the sea based on cellular automata modeling

doi:10.11947/j.AGCS.2019.20170477

Abstract

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

CLC Number:

P714

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.

References

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