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