计算机科学 ›› 2019, Vol. 46 ›› Issue (7): 333-338.doi: 10.11896/j.issn.1002-137X.2019.07.051
• 交叉与前沿 • 上一篇
宋鑫,朱宗良,高银萍,苌道方
SONG Xin,ZHU Zong-liang,GAO Yin-ping,CHANG Dao-fang
摘要: 随着船舶定位技术的进一步发展,大量船舶安装了船舶定位识别系统,该系统生成了海量的船舶轨迹数据。船舶轨迹数据经过压缩处理后能有效提高处理、应用数据的工作效率。针对现有轨迹在线压缩算法处理压缩率高、耗时长等问题,提出了一种动态阈值结合全局优化的两阶段在线压缩算法(DTGO)。该算法在第一阶段对原始轨迹进行分段处理,动态更新各项阈值,从而获得简化轨迹;在第二阶段使用改进的SPM算法对简化轨迹进行全局优化。通过对原始轨迹进行两阶段的处理,将原始轨迹分段成若干个子轨迹段,对子轨迹段进行局部处理,最后使用全局处理算法对所有子轨迹段进行全局优化。实验结果表明,该算法在提高压缩效率的同时取得了良好的压缩效果。
中图分类号:
[1]MUCKELL J,HWANG J H,LAWSON C T,et al.Algorithms for compressing GPS trajectory data:an empirical evaluation[C]∥Sigspatial International Conference on Advances in Geographic Informational Systems.ACM,2010:402-405.<br /> [2]DE VRIES G K D,VAN SOMEREN M.Machinelearning for vessel trajectories using compression,alignments and domain knowledge[J].Expert Systems with Applications,2012,39(18):13426-13439.<br /> [3]JIANG J W,WANG X L.Reciew on trajectory data compression[J].Journal of East China Normal University(Natural Science),2015,2015(5):61-76.(in Chinese)<br /> 江俊文,王晓玲.轨迹数据压缩综述[J].华东师范大学学报(自然科学版),2015,2015(5):61-76.<br /> [4]DOUGLAS D H,PEUCKER T K.Algorithms for the reduction of the number of points required to represent adigitized line or its caricature[J].Canadian Cartographer,2011,10(2):112-122.<br /> [5]LI M,HU Q Y,MENG L.Research on Vessel Motion Trajectory Compression Based on AIS[J].MARINE TECHN- OLOGY,2010(1):11-13.(in Chinese)<br /> 李名,胡勤友,孟良.基于AIS的船舶运动轨迹压缩技术研究[J].航海技术,2010(1):11-13.<br /> [6]SINGH A K,AGGARWAL V,SAXENA P,et al.Perfor-mance analysis of trajectory compression algorithms on marine surveillance data[C]∥International Conference on Advances in Computing,Communications and Informatics.2017:1074-1079.<br /> [7]YING J C,SU J H.On Velocity-Preserving Trajectory Simplification[M]∥Intelligent Information and Database Systems.Springer Berlin Heidelberg,2016:241-250.<br /> [8]ZHANG S K,LIU Z J,YAO C,et al.AIS Trajectories Simplification and Threshold Determination[J].Journal of Navigation,2016,69(4):729-744.<br /> [9]XUK,QIU J Y,LI Y.Offline Efficient Compression Algorithm for AIS Data Retains Time Elapsing Dimension[J].Computer Science,2017,44(S2):498-502.(in Chinese)<br /> 徐凯,邱家瑜,李燕.一种加入时间维的船舶轨迹高效离线压缩算法研究[J].计算机科学,2017,44(S2):498-502.<br /> [10]ZHAO L B,SHI G Y.A method for simplifying ship trajectory based on improved Douglas-Peucker algorithm [J].Ocean Engineering,2018,166:37-46.<br /> [11]KEOGH E,CHU S,HART D,et al.An Online Algorithm for Segmenting Time Series[C]∥Proceedings 2001 IEEE International Conference on Data Mining,2001:289-296.<br /> [12]POTAMIAS M,PATROUMPAS K,SELLIS T.Sampling Trajectory Streams with Spatiotemporal Criteria[C]∥International Conference on Scientific and Statistical Database Management.IEEE Computer Society,2006:275-284.<br /> [13]TRAJCEVSKI G,CAO H,SCHEUERMANNY P,et al.Online data reduction and the quality of history inmoving objects databases[C]∥ACM International Workshopon Data Engineering for Wireless and Mobile Access.ACM,2006:19-26.<br /> [14]MUCKELL J,HWANG J H,PATIL V,et al.SQUISH:an online approach for GPS trajectory compression[C]∥International Conference on Computing for Geospatial Research Applications.ACM,2011:13.<br /> [15]CAO W,Li Y.DOTS:An online and near-optimal trajectory implification algorithm[J].Journal of Systems and Software,2017,126:34-44.<br /> [16]MA W Y,WU Z L,LI W F.Conformal detection algorithm of anomalous behavior of vessel[J].Journal of Traffic and Transportation Engineering,2017,17(5):149-158.(in Chinese)<br /> 马文耀,吴兆麟,李伟峰.船舶异常行为的一致性检测算法[J].交通运输工程学报,2017,17(5):149-158.<br /> [17]QI L,ZHENG Z Y,LI G P.AIS-data-based ship domain of ships in sight of one another[J].Journal of DalianMariti- me University,2011,37(1):48-50.(in Chinese)<br /> 齐乐,郑中义,李国平.互见中基于AIS数据的船舶领域[J].大连海事大学学报,2011,37(1):48-50.<br /> [18]SAALFELD A.Topologically Consistent Line Simplification with the Douglas-Peucker Algorithm[J].American Cartographer,1999,26(1):7-18. <br /> |
[1] | 张玉琴, 张建亮, 冯向东. 一种无约束优化的无参数填充函数算法 Parametric-free Filled Function Algorithm for Unconstrained Optimization 计算机科学, 2020, 47(6A): 54-57. https://doi.org/10.11896/JsJkx.191000179 |
[2] | 李章维,王柳静. 基于群体分布的自适应差分进化算法 Population Distribution-based Self-adaptive Differential Evolution Algorithm 计算机科学, 2020, 47(2): 180-185. https://doi.org/10.11896/jsjkx.181202356 |
[3] | 郭超, 王磊, 尹爱华. 求解一刀切式二维矩形Strip Packing问题的混合搜索算法 Hybrid Search Algorithm for Two Dimensional Guillotine Rectangular Strip Packing Problem 计算机科学, 2020, 47(11A): 119-125. https://doi.org/10.11896/jsjkx.200200016 |
[4] | 倪洪杰, 彭春祥, 周晓根, 俞立. 一种阶段性策略自适应差分进化算法 Differential Evolution Algorithm with Stage-based Strategy Adaption 计算机科学, 2019, 46(6A): 106-110. |
[5] | 朱德剑,白光伟,蔡炎伟,任栋,沈航. 数据中心虚拟机节能管理机制 Energy-aware Management of Virtual Machines in Data Center 计算机科学, 2017, 44(10): 19-25. https://doi.org/10.11896/j.issn.1002-137X.2017.10.004 |
[6] | 曹阳,袁鑫攀,龙军. 连接位极大似然动态过滤算法 Dynamic Filtering Algorithm of Connected Bit Maximum Likelihood Minwise Hash 计算机科学, 2016, 43(Z6): 410-412. https://doi.org/10.11896/j.issn.1002-137X.2016.6A.097 |
[7] | 陈双叶,王善喜. 基于五帧差分和改进的Meanshift算法的运动目标跟踪 Moving Object Tracking Based on Five Frame Difference and Improved Meanshift Algorithm 计算机科学, 2016, 43(Z6): 203-206. https://doi.org/10.11896/j.issn.1002-137X.2016.6A.048 |
[8] | 蔡珍珍,叶仲泉. 一个新的连续可微的单参数填充函数 New Continuously Differentiable Filled Function with One Parameter 计算机科学, 2016, 43(8): 204-206. https://doi.org/10.11896/j.issn.1002-137X.2016.08.041 |
[9] | 杨芳,滕桂法,田学东. 视觉乐谱图像动态多阈值二值化方法 Dynamic Multi-threshold Binarization Method for Visual Music Images 计算机科学, 2016, 43(1): 310-314. https://doi.org/10.11896/j.issn.1002-137X.2016.01.067 |
[10] | 任作琳,田雨波,孙菲艳. 具有强开发能力的风驱动优化算法 Improved Wind Driven Optimization Algorithm with Strong Development Ability 计算机科学, 2016, 43(1): 275-281. https://doi.org/10.11896/j.issn.1002-137X.2016.01.059 |
[11] | 谢飞,龚声蓉,刘纯平,季怡. 基于局部和全局特征视觉单词的人物行为识别 Human Action Recognition by Visual Word Based on Local and Global Features 计算机科学, 2015, 42(11): 293-298. https://doi.org/10.11896/j.issn.1002-137X.2015.11.060 |
[12] | 赵志刚,王伟倩,黄树运. 基于改进粒子群的双层规划求解算法 Bi-level Programming Problem Based on Improved Particle Swarm Algorithm 计算机科学, 2013, 40(Z11): 115-119. |
[13] | 李煜,马良. 新型全局优化蝙蝠算法 Bat-inspired Algorithm:A Novel Approach for Global Optimization 计算机科学, 2013, 40(9): 225-229. |
[14] | 钱伟懿,刘光雷. 融合局部搜索与二次插值的粒子群优化算法 Particle Swarm Optimization Algorithm Combining Local Search and Quadratic Interpolation 计算机科学, 2013, 40(9): 204-207. |
[15] | 王丛佼,王锡淮,肖建梅. 基于极值优化的混合差分进化算法 Hybrid Differential Evolutionary Algorithm Based on Extremal Optimization 计算机科学, 2013, 40(5): 257-260. |
|