Euclidean Distance Transform on the Sea Based on Cellular Automata Modeling

doi:10.11947/j.JGGS.2020.0208

Abstract

Abstract:

To explore the problem of distance transformations while obstacles existing, this paper presents an obstacle-avoiding Euclidean distance transform method based on cellular automata. This research took the South China Sea and its adjacent sea areas 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, and automatically calculate the shortest distance bypass the land; second, the method has auto-update mechanism and 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 and the proportional error is less than 1.96%. The proposed method can apply to the fields of shipping routes design, maritime search and rescue, etc.

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

Jiasheng WANG,Kun YANG,Yanhui ZHU,Jianhong XIONG. Euclidean Distance Transform on the Sea Based on Cellular Automata Modeling[J]. Journal of Geodesy and Geoinformation Science, 2020, 3(2): 71-80.

Figures/Tables 7

Fig.1

Tab.1

Tab.2

Maximum absolute error rate for 3×3 distance operator"

Distance operator (a,b)	Maximum absolute error rate (%)	Operator name
(1, 1)	41.41	Chess Board Distance
(1, 2)	29.29	City block distance
(1, $2$ )	7.61	Euclidean local distance
(3, 4)/3	6.07	Integer Operator
(1, 1.3507)	5.63	Borgefors Operator
(1, 1.3420)	5.38	Butt-Maragos Operator
(0.95509, 1.36930)	4.69	Borgefors Optimization operator
(0.96194, 1.36039)	3.96	Butt-Maragos Optimization operator

Tab.2

Fig.2

Fig.3

Fig.4

Fig.5

References 29

[1]	ROSENFELD A, PFALTZ J L. Sequential operations in digital picture processing[J]. Journal of the ACM, 1966,13(4):471-494. doi: 10.1145/321356.321357
[2]	BORGEFORS G. Distance transformations in digital images[J]. Computer Vision, Graphics, and Image Processing, 1986,34(3):344-371. doi: 10.1016/S0734-189X(86)80047-0
[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. doi: 10.1016/j.patrec.2010.08.010
[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. doi: 10.5772/52938
[6]	HILL B, BALDOCK R A. Constrained distance transforms for spatial atlas registration[J]. BMC Bioinformatics, 2015,16(1):90. doi: 10.1186/s12859-015-0504-5
[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. doi: 10.1068/b29123
[8]	QIN Kun. Theories and methods of spatial analysis in GIS[M]. 2nd ed. Wuhan: Wuhan University Press, 2010.
[9]	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. doi: 10.3778/j.issn.1002-8331.2011.01.010
[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. doi: 10.1007/s12665-014-3521-1
[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. doi: 10.1016/j.marpolbul.2015.07.045
[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. doi: 10.1016/j.ssci.2013.08.002
[13]	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]	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]	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]	LI Xia, YE Jiaan, LIU Xiaoping, et al. Geographic simulation system:cellular automata and multi-agent[M]. Beijing: Science Press, 2007.
[18]	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]	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]	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]	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]	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]	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]	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. doi: 10.3390/ijgi4020447
[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. doi: 10.1080/13658816.2017.1301457
[29]	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.

Symbol	Name	Description
d_t	Status	The OAED between the cell and the closest target point set at time t
f_s	Status flag	True, indicating that the state of the cell has changed. False, indicating that the state of the cell has not changed.
f_l	Obstacle sign	True, indicating that the location is an obstacle area False, indicating that the location is a normal area
x	x coordinate	Cell center x coordinate
y	y coordinate	Cell center y coordinate