徐垚 李卓然 孟金龍 趙利坡 溫建新 王桂玲

摘 要：傳統(tǒng)的道路數(shù)據(jù)獲取方法成本高、更新慢等無法適用于海洋航道的獲取，從眾源軌跡數(shù)據(jù)中提取道路或航道信息具有成本低、更新快等特性，然而，由于船舶軌跡數(shù)據(jù)噪聲多、數(shù)據(jù)量大、不同區(qū)域分布不均使得航道邊界提取面臨較大挑戰(zhàn)。針對該問題，提出一種基于大規(guī)模船舶軌跡數(shù)據(jù)進(jìn)行航道邊界提取的方法。首先對大規(guī)模的船舶軌跡數(shù)據(jù)進(jìn)行并行化去噪、插值、軌跡分段;然后，基于并行化及基于Geohash編碼的空間聚類，將軌跡數(shù)據(jù)化簡為多個(gè)方形區(qū)域的點(diǎn)集數(shù)據(jù);其次，對其進(jìn)行窗口劃分，對傳統(tǒng)的NiBlack方法進(jìn)行擴(kuò)展，提出SpatialNiBlack算法，對方形區(qū)域進(jìn)行航道識(shí)別;最后，提出一種新的提取算法del-alpha-shape，基于航道識(shí)別結(jié)果獲得航道邊界。理論分析與實(shí)驗(yàn)結(jié)果表明，所提方法在最大密度值是200，最小密度值是10，窗口長和寬分別為5和5時(shí)，可同時(shí)達(dá)到86.7%的準(zhǔn)確率和79.4%的召回率。實(shí)驗(yàn)結(jié)果表明，該方法可以從大規(guī)模的軌跡數(shù)據(jù)中提取有價(jià)值的航道邊界，是一種有效的航道提取方法。

關(guān)鍵詞：軌跡數(shù)據(jù);自動(dòng)識(shí)別系統(tǒng);時(shí)空大數(shù)據(jù);Delaunay三角網(wǎng);航道提取

中圖分類號(hào)： TP319

文獻(xiàn)標(biāo)志碼：A

Abstract： The traditional road information extraction method is high-cost and slow-update. Compared with it， road or marine lane information extraction from crowdsourcing trajectory data is low-cost and easier to update. However， it is difficult to extract lane boundary due to vessel trajectory data with high noise， large data volume and uneven distribution across different regions. To solve this problem， an extraction method of marine lane boundary from exploiting trajectory big data was proposed. Firstly， the parallelized denoising， interpolation and trajectory segmentation for trajectory big data was conducted. Then， based on parallelization and Geohash-encoded spatial clustering， trajectory data was simplified into multiple square regions. The regions were divided and the NiBlack method was extended as SpatialNiBlack algorithm to recognize regions on lane. Finally， based on the filtering results， del-alpha-shape algorithm was proposed to construct a Delaunay triangulation network and obtain marine lane boundary. The theoretical analysis and experimental results show that the proposed method can achieve an accuracy of 86.7% and a recall rate of 79.4% when the maximum density value is 200， minimum density value is 10， length and width of window are 5 and 5 respectively. The experimental results show that the proposed method is effective to extract valuable marine lane boundaries from large-scale trajectory data.

Key words： trajectory data; Automatic Identification System （AIS）; spatio-temporal big data; Delaunay triangulation network; marine lane extraction

0 引言

由于傳統(tǒng)道路數(shù)據(jù)依靠人工測量、高分遙感影像等采集方式，具有價(jià)格昂貴、更新慢等特點(diǎn)，使得道路信息的快速獲取和更新成為一直以來亟待解決和廣受關(guān)注的問題。傳統(tǒng)道路信息提取的難點(diǎn)在于人工測量及高分遙感影像的獲取昂貴，以及基于圖像的準(zhǔn)確道路檢測與識(shí)別技術(shù)。其中，人工測量在采集信息時(shí)耗時(shí)耗力，而且受到地理環(huán)境和自然條件等限制，會(huì)帶來安全問題和時(shí)間成本大問題。高分遙感影像通過衛(wèi)星進(jìn)行高清影像數(shù)據(jù)采集，需要對數(shù)以百萬量不同級別的移動(dòng)物體長期且頻繁地進(jìn)行數(shù)據(jù)采集和處理，由于成本高昂難以推廣使用。尤其是，基于圖像的識(shí)別檢測技術(shù)對已建設(shè)的陸地道路路網(wǎng)識(shí)別是一種常用的方式，但海洋航道不同于陸地道路，該方法無法基于海洋影像識(shí)別航道與非航道區(qū)域。近年來，隨著移動(dòng)傳感器、物聯(lián)網(wǎng)、云計(jì)算、大數(shù)據(jù)等技術(shù)的發(fā)展，產(chǎn)生了海量的時(shí)空軌跡大數(shù)據(jù)，并能夠?qū)ζ溥M(jìn)行處理和分析。通過對眾多在道路上行駛的移動(dòng)物體產(chǎn)生的時(shí)空軌跡大數(shù)據(jù)進(jìn)行分析，提取其中的道路信息成為一種受關(guān)注的技術(shù)。與陸地上的道路相比，海上沒有人為建筑的航道，且受氣候、洋流、事故等各種外部因素影響動(dòng)態(tài)變化，情形更加復(fù)雜。與陸地道路信息采集相比，利用傳統(tǒng)的人工測量等方法采集航道信息代價(jià)更為高昂，而利用來自船舶自動(dòng)識(shí)別系統(tǒng)（Automatic Identification System， AIS）的眾源船舶軌跡數(shù)據(jù)提取航道的信息，如果可行其一定具有低廉、更新快等特性，不失為一種可以探索且較有前景的途徑;但是，眾源船舶軌跡數(shù)據(jù)具有海量、地理范圍大、數(shù)據(jù)質(zhì)量差、數(shù)據(jù)密度在不同區(qū)域差異明顯等特征[1]，這給海上航道的獲取和更新提出了更大的挑戰(zhàn)，本文提出了基于眾源船舶軌跡數(shù)據(jù)進(jìn)行航道信息提取的一整套方法，所瞄準(zhǔn)的主要挑戰(zhàn)及本文貢獻(xiàn)包括：

1）針對眾源船舶軌跡數(shù)據(jù)規(guī)模大的特點(diǎn)，采用基于MapReduce的方法對眾源船舶軌跡數(shù)據(jù)進(jìn)行并行化預(yù)處理，并基于并行化的Geohash編碼方法進(jìn)行空間聚類，從而既保留了船舶軌跡數(shù)據(jù)中隱藏的航道信息，又將海量的眾源船舶軌跡數(shù)據(jù)進(jìn)行了有效化簡[2-3]。

2）針對大范圍眾源船舶軌跡數(shù)據(jù)在不同區(qū)域分布不均的問題，提出SpatialNiBlack局部動(dòng)態(tài)閾值過濾算法[4]，對軌跡數(shù)據(jù)的聚類結(jié)果進(jìn)行局部閾值過濾，并提出航道邊界提取算法del-alpha-shape，能夠?qū)Υ蠓秶谋娫窜壽E數(shù)據(jù)進(jìn)行航道平面邊界的準(zhǔn)確提取[5]。

需要指出的是，航道本是具有寬度、水深等屬性的水域，本文主要關(guān)注航道的平面屬性，聚焦于如何基于海量的船舶軌跡數(shù)據(jù)提取航道的平面邊界信息。

1 相關(guān)工作

當(dāng)前，利用船舶軌跡數(shù)據(jù)進(jìn)行航道提取的同類研究還比較前沿，直接相關(guān)的工作還比較少。相關(guān)工作有兩類：一類工作通過對軌跡進(jìn)行行為模式的統(tǒng)計(jì)，基于移動(dòng)對象的行為模式與位置對比分析進(jìn)一步建立航道[6-10];另外一類是利用K-Means、DBSCAN（Density-Based Spatial Clustering of Applications with Noise）等聚類算法挖掘航道的行為模式進(jìn)一步提取航道[11-12]。雖然利用船舶軌跡數(shù)據(jù)進(jìn)行航道提取的工作較少，但利用眾源軌跡進(jìn)行道路邊界的提取是交通大數(shù)據(jù)領(lǐng)域的一個(gè)逐漸受到越來越多的研究者關(guān)注的研究問題，國內(nèi)外學(xué)者主要圍繞道路邊界的提取和功能區(qū)域邊界的提取展開了一定的研究工作，已經(jīng)有一些值得借鑒的相關(guān)工作[13-14]。這些工作主要通過約束構(gòu)造平面點(diǎn)集形狀實(shí)現(xiàn)邊界提取。如文獻(xiàn)[15]運(yùn)用約束德洛內(nèi)（Delaunay）三角網(wǎng)從車輛軌跡線集中提取道路邊界[15]，主要通過三角形邊長度和Voronoi面積等幾何特征表達(dá)軌跡點(diǎn)分布的聚集性差異，然后將兩種不同維數(shù)的控制條件集成建立道路邊界識(shí)別模型，運(yùn)用“種子點(diǎn)”擴(kuò)展方法實(shí)現(xiàn)道路邊界的提取。也有一些學(xué)者提出雙閾值的Alpha Shapes算法[16]，利用簡單環(huán)的概念設(shè)計(jì)輪廓搜索算法，獲得既有較好完整性又有較高幾何精度的建筑物輪廓線。有的學(xué)者是基于凸殼的方法，采用凸殼的內(nèi)縮特征獲取邊界的凹凸特征，這種方法一定程度上能處理空間密度分布不均的情況，但難以保證邊界的規(guī)則性，也無法識(shí)別空洞現(xiàn)象[17]。從內(nèi)容上看，這些方法無法適應(yīng)采樣稀疏、高噪聲的全球定位系統(tǒng)（Global Positioning System， GPS）船舶軌跡數(shù)據(jù)，針對大規(guī)模船舶軌跡數(shù)據(jù)難以取得良好的效果。

綜上分析，現(xiàn)有的平面點(diǎn)集形狀重構(gòu)算法能夠通過多條件約束表征點(diǎn)集的形狀，但是對于大規(guī)模的船舶軌跡數(shù)據(jù)則存在以下兩點(diǎn)問題：1）由于采樣環(huán)境原因，原始的大規(guī)模船舶軌跡數(shù)據(jù)包含大量噪聲數(shù)據(jù)和丟失數(shù)據(jù)，增加了邊界提取的難度;2）海洋上的軌跡數(shù)據(jù)受船舶的行駛習(xí)慣和活動(dòng)熱度影響，不同區(qū)域的船只由于活動(dòng)程度不同，造成同一時(shí)間范圍下軌跡數(shù)據(jù)量的量級在不同區(qū)域存在差異，使提取航道邊界問題變得更加復(fù)雜。針對以上存在的問題，本文提出了一種新的算法模型，首先針對大規(guī)模的船舶軌跡數(shù)據(jù)，使用并行技術(shù)進(jìn)行插值、去噪和Geohash聚類預(yù)處理;然后通過時(shí)空NiBlack局部動(dòng)態(tài)閾值過濾和約束三角構(gòu)網(wǎng)實(shí)現(xiàn)航道邊界的提取。

2 方法概述

本文提出的算法是一種運(yùn)用空間NiBlack局部動(dòng)態(tài)閾值過濾及約束三角網(wǎng)從海量船舶軌跡點(diǎn)集中提取航道邊界的過程。首先，對海量的船舶軌跡數(shù)據(jù)進(jìn)行并行的去除異常軌跡點(diǎn)以及缺失數(shù)據(jù)補(bǔ)全預(yù)處理，提升數(shù)據(jù)質(zhì)量;然后利用并行的Geohash編碼方法對其進(jìn)行聚類，以在保障結(jié)果精度的前提下提高后續(xù)數(shù)據(jù)處理和分析的效率;其次，提出空間NiBlack算法，針對大范圍海量船舶軌跡數(shù)據(jù)在不同區(qū)域分布不均的問題，對聚類結(jié)果進(jìn)行局部閾值過濾，對軌跡數(shù)據(jù)的預(yù)處理結(jié)果進(jìn)行航道識(shí)別;最后，基于alpha shape邊界算法提出一種新的提取算法del-alpha-shape，利用上一步局部閾值過濾的結(jié)果基于Delaunay三角剖分算法構(gòu)造三角網(wǎng)，并提取邊界輪廓，經(jīng)過閾值過濾等處理后得到航道平面邊界。

3 并行化軌跡數(shù)據(jù)空間聚類

3.1 并行化預(yù)處理

由于測量誤差、傳感器誤差等因素，GPS軌跡數(shù)據(jù)存在數(shù)據(jù)缺失和噪聲的問題，這樣的數(shù)據(jù)在航道提取中很難發(fā)揮作用，所以在應(yīng)用中需要對原始數(shù)據(jù)作預(yù)處理。本文軌跡預(yù)處理過程主要由過濾和插值兩部分組成，過濾是為了消除噪聲，插值是為了補(bǔ)全缺失數(shù)據(jù)。因?yàn)榇霸谡：叫羞^程中不會(huì)頻繁轉(zhuǎn)向，產(chǎn)生的軌跡在一定范圍內(nèi)近似于直線，所以為了提高程序效率，本文采用基于時(shí)間和空間閾值的過濾和插值算法，而不是其他復(fù)雜算法。過濾算法的原理是計(jì)算點(diǎn)到軌跡的距離，如果點(diǎn)到軌跡的距離大于預(yù)定閾值則刪除該點(diǎn)，從而消除孤立的噪聲點(diǎn)。插值算法的原理是計(jì)算兩個(gè)相鄰軌跡點(diǎn)的距離和整體軌跡相鄰兩點(diǎn)的平均距離，根據(jù)相鄰兩點(diǎn)的距離與平均距離的比值大小，在這兩個(gè)點(diǎn)之間插入不同數(shù)量的軌跡點(diǎn)，比值越大插入的點(diǎn)就越多。

本文采用某海洋船舶監(jiān)測系統(tǒng)所采集的12個(gè)月的數(shù)據(jù)作為數(shù)據(jù)源，其中一個(gè)月約有60GB的數(shù)據(jù)，3億多條記錄。在使用CentOS 6.7單機(jī)實(shí)驗(yàn)時(shí)，對于60GB的數(shù)據(jù)量預(yù)處理完成大概需要40h，因此需要采用基于集群的并行化處理技術(shù)進(jìn)行效率的提升。這些數(shù)據(jù)以SequenceFile序列化文件類型保存在Hadoop分布式文件系統(tǒng)（Hadoop Distributed File System， HDFS）中。因?yàn)樵紨?shù)據(jù)集中每條記錄均包含多個(gè)字段，本文對原始數(shù)據(jù)進(jìn)行篩選，每條記錄處理為定義1的四個(gè)基本字段組成。

本文方法基于MapReduce對數(shù)據(jù)并行化預(yù)處理，算法流程如圖1所示。

1）數(shù)據(jù)分割，將HDFS中保存原始數(shù)據(jù)的SequenceFile文件劃分成m（mn，n表示數(shù)據(jù)節(jié)點(diǎn)數(shù)）個(gè)數(shù)據(jù)塊Split，每個(gè)塊交由一個(gè)數(shù)據(jù)節(jié)點(diǎn)Datanode處理。

2）Map階段，程序逐行讀取字段無缺失數(shù)據(jù)，提取每條數(shù)據(jù)的v、x、y、t四個(gè)屬性，以字段v為鍵，元組（x，y，t）為鍵值輸出，其形式為〈v，（x，y，t）〉。

3）在Reduce階段，每個(gè)Reduce處理具有相同鍵v的數(shù)據(jù)，操作如下：

第1步 將相同v的數(shù)據(jù)按時(shí)間t排序，設(shè)定時(shí)間閾值t_z和距離閾值d_z，軌跡閾值n。

第2步 將第i個(gè)軌跡點(diǎn)保存在數(shù)組list中，如果第i+1個(gè)軌跡點(diǎn)和第i個(gè)軌跡點(diǎn)之間的距離di小于d_z，且時(shí)間間隔Δti

第3步 計(jì)算數(shù)組list中軌跡點(diǎn)的個(gè)數(shù)N，如果N

第4步 計(jì)算相鄰兩點(diǎn)第j和第j+1之間的距離dj，如果dj小于d，或者兩點(diǎn)的經(jīng)度之差大于300（分別在東經(jīng)180°附近和西經(jīng)180°附近的相鄰兩點(diǎn)之間不用插值，這個(gè)判斷的值可以是小于360°且盡可能大的值，設(shè)為300），則j=j+1，繼續(xù)執(zhí)行此步;否則令s=dj/d+2，在第j和第j+1兩點(diǎn)之間插入s個(gè)點(diǎn)，并保存在list中， j=j+1，繼續(xù)執(zhí)行此步，直到遍歷list，執(zhí)行第5步。

第5步 保存list中的元素，并清空list，i=i+1，執(zhí)行第2步，直到遍歷相同v的數(shù)據(jù)。將預(yù)處理后的數(shù)據(jù)以字段v為鍵、元組（x，y，t）為鍵值輸出，其形式為〈v，（x，y，z）〉。

4）將預(yù)處理后的數(shù)據(jù)按v保存在不同的文本文件中，最后得到預(yù)處理后的數(shù)據(jù)。在使用上述基于MapReduce的數(shù)據(jù)預(yù)處理之后，在表1所述的集群實(shí)驗(yàn)條件下，整個(gè)過程從40h縮短為150min。

3.2 基于Geohash編碼的并行化空間聚類算法

軌跡聚類采用基于Geohash編碼的算法，當(dāng)軌跡點(diǎn)較多時(shí)，對于軌跡點(diǎn)，并不需要遍歷計(jì)算數(shù)據(jù)集中所有軌跡點(diǎn)與當(dāng)前點(diǎn)的距離，僅需關(guān)注小范圍內(nèi)的相鄰軌跡點(diǎn)，因此考慮引入Geohash空間編碼技術(shù)并行化聚類GPS軌跡點(diǎn)。基于Geohash編碼空間聚類算法的原理是將地球看作一個(gè)平面，把地球平面劃分為大小相同的網(wǎng)格，所有的軌跡點(diǎn)都會(huì)對應(yīng)一個(gè)柵格，從而將位于同一柵格的軌跡點(diǎn)聚類。在使用CentOS 6.7單機(jī)實(shí)驗(yàn)時(shí)，對于60GB的數(shù)據(jù)量Geohash編碼完成大概需要18h，因此需要基于集群進(jìn)行并行化處理。

本方法基于MapReduce對數(shù)據(jù)并行處理，算法流程如圖2所示。

程序的輸入數(shù)據(jù)是3.1節(jié)預(yù)處理后的數(shù)據(jù)，程序按照以下流程運(yùn)行。

1）數(shù)據(jù)分割，將HDFS中以不同v命名的m個(gè)數(shù)據(jù)文件劃分成m′（m′≥n，n表示數(shù)據(jù)節(jié)點(diǎn)數(shù)）個(gè)數(shù)據(jù)塊Split，每個(gè)塊交由一個(gè)Datanode處理;

2）Map階段，抽取每條數(shù)據(jù)的經(jīng)度x和緯度y并進(jìn)行Geohash編碼，然后以編碼code為鍵，1為鍵值輸出，其形式為〈code，1〉;

3）Reduce階段，統(tǒng)計(jì)不同Geohash編碼code的密度dsy，計(jì)算其對應(yīng)區(qū)域C的中心點(diǎn)經(jīng)緯度C_x和C_y，以C_x、C_y和dsy為鍵，null為鍵值輸出，其形式為〈（C_x，C_y，dsy），null〉;

4）將所有數(shù)據(jù)按元組〈C_x，C_y，dsy〉保存。完成空間聚類。

在本文中，Geohash編碼位數(shù)為11位，大約等于11km見方的一個(gè)區(qū)域。在使用上述基于MapReduce的數(shù)據(jù)預(yù)處理之后，在表1所述的集群實(shí)驗(yàn)條件下，整個(gè)過程從18h縮短為110min。

4 基于NiBlack局部動(dòng)態(tài)閾值過濾及alpha shape的邊界提取算法

4.1 SpatialNiBlack局部動(dòng)態(tài)閾值過濾算法

Niblack算法是一種比較常用、簡單、有效的局部動(dòng)態(tài)閾值算法，通常應(yīng)用于數(shù)字圖像分割、圖像二值化等領(lǐng)域，該算法根據(jù)局部平均值和局部標(biāo)準(zhǔn)差確定當(dāng)前區(qū)域閾值。由于不同區(qū)域的軌跡點(diǎn)密度存在差異，固定閾值無法準(zhǔn)確地過濾數(shù)據(jù)，因此本文基于NiBlack動(dòng)態(tài)窗口過濾算法思想，提出適于軌跡數(shù)據(jù)分析的SpatialNiBlack算法，實(shí)現(xiàn)不同密度的軌跡點(diǎn)數(shù)據(jù)過濾，該方法有效克服了固定閾值的缺陷。

本文所用的數(shù)據(jù)是3.2節(jié)中聚類的結(jié)果，這些數(shù)據(jù)被保存在一個(gè)二維數(shù)組中，數(shù)組中的每一行用一個(gè)三元組〈C_x，C_y，dsy〉來表示一個(gè)柵格C，其中C_x和C_y分別表示柵格中心點(diǎn)的經(jīng)度和緯度，dsy表示柵格C中軌跡點(diǎn)的密度。

本方法步驟如圖3所示，基于SpatialNiBlack局部動(dòng)態(tài)閾值的過濾算法如下。

1）首先得到全球11位的柵格，設(shè)置大小為m×n的矩形窗口，因?yàn)閿?shù)據(jù)從緯度變化方向來看，有密度差異，所以窗口設(shè)置成扁平的矩形，使窗口內(nèi)大多的點(diǎn)的密度在同一個(gè)級別。窗口包含m×n個(gè)11位柵格，執(zhí)行第2）步;

2）遍歷當(dāng)前窗口中的柵格，統(tǒng)計(jì)窗口中所有柵格的dsy值，根據(jù)式（1）計(jì)算出閾值T（x，y），然后判斷窗口中心點(diǎn)所在柵格是否保留。執(zhí)行下一步;

其中對于柵格中心點(diǎn)經(jīng)緯度（x，y），T（x，y）為該位置的閾值，m（x，y）為該點(diǎn)所在窗口內(nèi)軌跡點(diǎn)密度的均值，s（x，y）為該點(diǎn)所在窗口內(nèi)軌跡點(diǎn)密度的標(biāo)準(zhǔn)差，k為修正系數(shù)（通常取-0.1）。

3）窗口中心柵格后移一個(gè)格，以該柵格為中心建立新的窗口，執(zhí)行第2）步;直到窗口遍歷所有柵格。最后輸出過濾后的數(shù)據(jù)。

4.2 基于alpha shape的邊界提取

本文基于alpha shape邊界算法，提出一種新的提取算法del-alpha-shape，該算法能夠有效地對點(diǎn)集進(jìn)行邊界提取。

alpha shape是一種經(jīng)典的點(diǎn)集輪廓提取算法，即輸入點(diǎn)集，通過對任意兩點(diǎn)建立半徑為alpha的外接圓，如果沒有第三個(gè)點(diǎn)在該圓內(nèi)，則這兩點(diǎn)連成的線段是邊界線段。通過對alpha值的調(diào)整可以得到不同精確程度的輪廓。如果兩個(gè)點(diǎn)連線距離大于2倍alpha閾值，那么無法構(gòu)成半徑alpha的外接圓，對這兩點(diǎn)不進(jìn)行判斷。

Delaunay三角剖分算法是將點(diǎn)集處理成由三角面構(gòu)成的凸包平面圖，該平面圖內(nèi)除了端點(diǎn)，不包含任何點(diǎn)集中的點(diǎn)。

定義9 三角形密度指數(shù)alpha。三角形的三個(gè)點(diǎn)可以構(gòu)成唯一的一個(gè)外接圓，該外接圓半徑circum_r的倒數(shù)值，稱為三角形密度指數(shù)。

在Delaunay三角網(wǎng)圖（圖4）中，航道內(nèi)的三角形的密度指數(shù)較大，航道外的三角形的密度指數(shù)較小。設(shè)定alpha閾值（用alpha_value表示），如果三角形alpha≥alpha_value，為航道三角形，保留該三角形的三條邊到Edges;否則，為空洞三角形，不保留邊。

該算法流程如圖5所示。

本文4.1節(jié)得到的柵格過濾結(jié)果是一個(gè)點(diǎn)集數(shù)據(jù)，以Points表示。該算法首先使用Delaunay方法對點(diǎn)集Points進(jìn)行Delaunay三角化，得到三角面集合Triangles（第1）行）;然后遍歷Triangles，使用calCircum方法計(jì)算每個(gè)三角形的密度指數(shù)circum，如果circum不小于密度指數(shù)閾值，則將該三角形的邊加入邊集Edges（第2）～6）行）;下一步用polygonize方法對Edges進(jìn)行多邊形化，構(gòu)成多邊形集Polys（第7）行）;最后，遍歷Polys，判斷每個(gè)多邊形的面積是否大于面積閾值maxArea，如果大于，則將該多邊形的邊界坐標(biāo)polygon.coords添加到Channels集合（第8）～11）行）。算法時(shí)間成本主要在第7）行多邊形生成過程，整體時(shí)間復(fù)雜度是O（N2）。

5 實(shí)驗(yàn)分析

5.1 數(shù)據(jù)集介紹

船只航行軌跡數(shù)據(jù)是全球2016年內(nèi)的所有船只軌跡。船只航行軌跡數(shù)據(jù)包括GPS時(shí)間戳、水上移動(dòng)通信業(yè)務(wù)標(biāo)識(shí)碼（MMSI）、GPS經(jīng)度、GPS緯度等多項(xiàng)信息。軌跡點(diǎn)采樣間隔在10～120s，總數(shù)據(jù)量在1TB左右。

本實(shí)驗(yàn)選取兩次不同的數(shù)據(jù)：一是2016年6月渤海區(qū)域的油輪航行軌跡數(shù)據(jù);一是2016年6、7、8月“一帶一路”區(qū)域大宗貨物船只航行軌跡數(shù)據(jù)。本實(shí)驗(yàn)的預(yù)處理步驟是在6臺(tái)搭建了Hadoop環(huán)境的機(jī)器下進(jìn)行的，系統(tǒng)為CentOS release 7.0操作系統(tǒng)，JDK版本為1.7.0，Hadoop版本為2.6.0。集群具體配置如表1所示。

實(shí)驗(yàn)合并過濾程序使用Java1.8編程語言實(shí)現(xiàn)，航道提取使用Python 3.5編程語言實(shí)現(xiàn)，在單臺(tái)物理機(jī)（64GB內(nèi)存，系統(tǒng)CentOS release 7.0）運(yùn)行。

5.2 實(shí)驗(yàn)結(jié)果與分析

本文設(shè)計(jì)以下實(shí)驗(yàn)驗(yàn)證模型，第一組實(shí)驗(yàn)使用數(shù)據(jù)是中國—東南亞—非洲連線區(qū)域2016年2—12月的大宗船只的航行數(shù)據(jù)。

圖6（a）是使用3.1和3.2節(jié)介紹預(yù)處理方法，預(yù)處理相關(guān)的參數(shù)取值為：距離閾值30km，時(shí)間閾值3600s，分段軌跡點(diǎn)數(shù)目閾值30，對中國—東南亞—非洲連線區(qū)域2016年2—12月的大宗船只原始軌跡數(shù)據(jù)預(yù)處理后的柵格化聚類結(jié)果上圖此句不通順，請作相應(yīng)調(diào)整。。圖6（b）是使用4.1節(jié)介紹方法滑動(dòng)窗口局部動(dòng)態(tài)閾值過濾的結(jié)果。這里涉及到幾個(gè)參數(shù)設(shè)置，柵格位數(shù)11位、柵格最大閾值200、窗口寬50、窗口高3。圖6（c）是基于滑動(dòng)窗口局部動(dòng)態(tài)閾值過濾結(jié)果用4.2節(jié)介紹方法作航道提取的上圖圖6（c）是基于滑動(dòng)窗口局部動(dòng)態(tài)閾值過濾和4.2節(jié)介紹方法做航道提取的結(jié)果[18]此句不通順，請作相應(yīng)調(diào)整。。

第二組實(shí)驗(yàn)使用數(shù)據(jù)是渤海區(qū)域的2016年6—8月的油輪航行數(shù)據(jù)，主要為了進(jìn)一步驗(yàn)證較小地理空間范圍下模型提取航道和空洞的準(zhǔn)確性。

圖7（a）是使用3.1和3.2節(jié)介紹的預(yù)處理方法，預(yù)處理相關(guān)的參數(shù)取值為：距離閾值30km，時(shí)間閾值3600s，分段軌跡點(diǎn)數(shù)目閾值30，對渤海區(qū)域2016年6—8月油輪原始軌跡數(shù)據(jù)預(yù)處理后的柵格化聚類結(jié)果如圖7。

圖7（b）是使用4.1節(jié)介紹方法滑動(dòng)窗口局部動(dòng)態(tài)閾值過濾的結(jié)果。這里參數(shù)設(shè)置為，柵格位數(shù)16位，柵格最大閾值500，窗口寬15，窗口高7。圖7（c）是基于滑動(dòng)窗口局部動(dòng)態(tài)閾值過濾結(jié)果用4.2節(jié)介紹方法作航道提取的上圖圖7（c）是基于滑動(dòng)窗口局部動(dòng)態(tài)閾值過濾和4.2節(jié)介紹方法做航道提取的結(jié)果。

本文以渤海某一區(qū)域的使用固定閾值進(jìn)行航道提取的結(jié)果為參考，如圖8（a），然后使用本文提出的大規(guī)模窗口局部過濾法的航道結(jié)果與之對比分析。采用過濾結(jié)果疊置方法評價(jià)航道提取的有效性，并借鑒文獻(xiàn)的方法計(jì)算兩種常用的評價(jià)指標(biāo)，即準(zhǔn)確率（precision）和召回率（recall）來評價(jià)疊置結(jié)果。準(zhǔn)確率反映實(shí)驗(yàn)結(jié)果的準(zhǔn)確度，召回率反映實(shí)驗(yàn)結(jié)果的完整度。

本文準(zhǔn)確率和召回率的計(jì)算如式（2）和式（3）：

其中：gridNumextstd表示新提取的航道柵格結(jié)果與標(biāo)準(zhǔn)航道柵格結(jié)果重合的數(shù)目，gridNumstd表示標(biāo)準(zhǔn)航道柵格結(jié)果的數(shù)目，gridNumext表示提取航道柵格結(jié)果的數(shù)目。

實(shí)驗(yàn)數(shù)據(jù)是2016年6月至2016年—8月份油輪軌跡數(shù)據(jù)，在渤海某一區(qū)域內(nèi)進(jìn)行航道提取方法驗(yàn)證，采取不同參數(shù)對比結(jié)果如圖8。

參數(shù)值含義

maxDsy100～∞這個(gè)數(shù)據(jù)項(xiàng)是何意？100后面加了“--”，何意？回復(fù)：表示取值范圍，可改為100-∞最大密度值

minDsy0～10最小密度值

w_size3×3、5×5、10×3滑動(dòng)窗口大小

表3是選用不同參數(shù)進(jìn)行多組實(shí)驗(yàn)后，與標(biāo)準(zhǔn)航道結(jié)果疊置后求得的準(zhǔn)確率和召回率結(jié)果。其中：precision表示準(zhǔn)確率，recall表示召回率。從表中可以看出：

1）最大密度值maxDsy的限制能夠避免局部窗口內(nèi)方差過大造成的閾值過大，圖8（b）導(dǎo)致窗口內(nèi)所有值被過濾舍棄，造成召回率偏低，因此，設(shè)置最大密度值進(jìn)行限制，并分多組實(shí)驗(yàn)測試當(dāng)該值為200時(shí)效果準(zhǔn)確率和召回率都有較好的表現(xiàn)。

2）最低密度值minDsy可以過濾掉一些存在的噪聲數(shù)據(jù)，提升召回率，經(jīng)過多組測試發(fā)現(xiàn)10是一個(gè)比較合適的值。

3）滑動(dòng)窗口的大小選擇對結(jié)果有一定影響，當(dāng)窗口較小時(shí)，準(zhǔn)確率因閾值計(jì)算考慮范圍過小造成準(zhǔn)確率下降，如圖8（k）;當(dāng)窗口形狀不合適，可能造成閾值結(jié)果過大，過濾舍棄掉過多的值導(dǎo)致航道部分缺失，如圖8（l）。

實(shí)驗(yàn)驗(yàn)證了本文所提方法能夠在大范圍數(shù)據(jù)下保持較高的提取精確度，同時(shí)依然保持較高的完整度;同時(shí)，本文所提算法與其他相似的研究算法有所區(qū)別：

1）基于三角網(wǎng)的邊界提取。文獻(xiàn)[15]通過對軌跡數(shù)據(jù)構(gòu)造三角網(wǎng)并約束條件提取道路，但其主要思路是通過自定義的長短邊概念找到邊界。本文主要通過三角網(wǎng)的外接圓半徑約束條件尋找邊界邊;同時(shí)，通過實(shí)現(xiàn)兩種算法進(jìn)行實(shí)驗(yàn)，發(fā)現(xiàn)本文算法在相同量的大規(guī)模數(shù)據(jù)下的效率更高，運(yùn)行時(shí)間效率可提高約5倍此處表述不當(dāng)，意義不對，“運(yùn)行時(shí)間”應(yīng)該是“減少幾分之幾”，請按照這個(gè)思路進(jìn)行調(diào)整;或者改為“運(yùn)行效率可提高約5倍”，這樣修改合適嗎？請明確。

2）基于GPS道路軌跡線提取。文獻(xiàn)[13]通過聚類方式改進(jìn)算法，提取了不同級別道路的中心線結(jié)果。本文所提航道除了能夠表示路網(wǎng)結(jié)構(gòu)外，還能夠看出航道的邊界大致范圍，由于航道在海面上沒有寬度限制，因此該范圍是一個(gè)不嚴(yán)格的大概范圍。

3）圖像輪廓線提取算法。文獻(xiàn)[16]借助圖像處理的研究中進(jìn)行，其輸入大致是圖像數(shù)據(jù)，通過對像素值的識(shí)別計(jì)算，提取出包括空洞的輪廓線結(jié)果。本文算法是基于時(shí)空軌跡大數(shù)據(jù)進(jìn)行的邊界提取，由于時(shí)空軌跡數(shù)據(jù)密度值相比0～255的像素值范圍具有更大的取值范圍，因此在算法思路上有所區(qū)別，本文在4.1節(jié)局部過濾算法內(nèi)通過參數(shù)的限制有效解決了時(shí)空數(shù)據(jù)復(fù)雜的問題。

6 結(jié)語

本文提出一種基于大規(guī)模船舶軌跡數(shù)據(jù)進(jìn)行航道邊界提取的方法，通過去噪、插值、分段預(yù)處理和Geohash編碼簡化處理數(shù)據(jù);然后基于處理后的數(shù)據(jù)結(jié)果使用文中提出的SpatialNiBlack航道識(shí)別算法過濾航道;最后使用del-alpha-shape算法獲得有效的航道邊界。通過實(shí)驗(yàn)可以發(fā)現(xiàn)：該方法能夠有效解決邊界提取的空洞問題;在較大的地理范圍下能夠進(jìn)行航道邊界提取;通過改進(jìn)的局部過濾算法，可以解決全局范圍下的數(shù)據(jù)因存在質(zhì)量差異導(dǎo)致部分航道丟失的問題。進(jìn)一步改進(jìn)的方面：完善算法，使其能夠同時(shí)對近海區(qū)域的一些較為精細(xì)的航道進(jìn)行更加有效的提取。

參考文獻(xiàn) （References）

[1] WANG Y， ZHU Y， HE Z， et al. Challenges and opportunities in exploiting large-scale GPS probe data， HPL-2011-109 [R]. Palo Alto， CA： HP Laboratories， 2011.

[2] ZHANG W， GOERLANDT F， KUJALA P， et al. An advanced method for detecting possible near miss ship collisions from AIS data[J]. Ocean Engineering， 2015， 107（1）：60-69.

[3] WANG X， LIU X， LIU B， et al. Vessel route anomaly detection with Hadoop MapReduce[C]// Proceedings of the 2015 IEEE International Conference on Big Data. Piscataway， NJ： IEEE， 2015：25-30.

[4] NIBLACK W. An Introduction to Digital Image Processing[M]. Englewood Cliffs， NJ： Prentice-Hall， 1986：115-116.

[5] EDELSBRUNNER H， KIRKPATRICK D， SEIDEL R. On the shape of a set of points in the plane[J]. IEEE Transactions on Information Theory，1983，29（4） ：551-559.

[6] SUN F， DENG Y， DENG F， et al. Unsupervised maritime traffic pattern extraction from spatio-temporal data[C]// Proceedings of the 2015 International Conference on Natural Computation. Piscataway， NJ： IEEE， 2015：1218-1223.

[7] MAZZARELLA F， FERNANDEZ ARGUEDAS V， VESPE M. Knowledge-based vessel position prediction using historical AIS data[C]// Proceedings of the 2015 Sensor Data Fusion： Trends， Solutions， Applications. Piscataway， NJ： IEEE， 2015：1-6.

[8] FERNANDEZ ARGUEDAS V， PALLOTTA G， VESPE M. Maritime traffic networks： from historical positioning data to unsupervised maritime traffic monitoring[J]. IEEE Transactions on Intelligent Transportation Systems， 2017， 19（3）： 722-732.

[9] PALLOTTA G， VESPE M， BRYAN K. Vessel pattern knowledge discovery from AIS data： a framework for anomaly detection and route prediction[J]. Entropy， 2013， 15（6）：2218-2245.

[10] SPILIOPOULOS G， ZISSIS D， CHATZIKOKOLAKIS K. A big data driven approach to extracting global trade patterns[C]// Proceedings of the 2017 International Workshop on Mobility Analytics for Spatio-temporal and Social Data. Berlin： Springer， 2017：109-121.

[11] ETIENNE L， DEVOGELE T， BOUJU A. Spatio-temporal trajectory analysis of mobile objects following the same itinerary[C]// Proceedings of the 2010 International Symposium on Spatial Data Handling. Hong Kong： [s.n.]， 2010：86-91.

[12] 楊杰，李小平，陳湉.基于增量時(shí)空軌跡大數(shù)據(jù)的群體挖掘方法[J].計(jì)算機(jī)研究與發(fā)展，2014，51（s2）：76-85.（YANG J， LI X P， CHEN T. A group mining method for incremental spatio-temporal trajectory big data[J]. Journal of Computer Research and Development， 2014， 51（s2）：76-85.）

[13] 歐陽鴻，劉建勛，劉毅志，等.基于步行GPS軌跡的路網(wǎng)提取方法[J].計(jì)算機(jī)與現(xiàn)代化，2014（2）：124-128.（OUYANG H， LIU J X， LIU Y Z， et al. An extraction method of road network based on walking GPS trajectories[J]. Computer and Modernization， 2014，（2）：124-128.）

[14] 楊偉，艾廷華.基于車輛軌跡大數(shù)據(jù)的道路網(wǎng)更新方法研究[J].計(jì)算機(jī)研究與發(fā)展，2016，53（12）：2681-2693.（YANG W， AI T H. A method for road network updating based on vehicle trajectory big data[J]. Journal of Computer Research and Development， 2016，53（12）：2681-2693.）

[15] 楊偉，艾廷華.運(yùn)用約束Delaunay三角網(wǎng)從眾源軌跡線提取道路邊界[J].測繪學(xué)報(bào)，2017，46（2）：237-245.（YANG W， AI T H. The extraction of road boundary from crowdsourcing trajectory using constrained Delaunay triangulation[J]. Acta Geodaetica et Cartographica Sinica， 2017， 46（2）： 237-245.）

[16] 李云帆，譚德寶，高廣，等.雙閾值A(chǔ)lpha Shapes算法提取點(diǎn)云建筑物輪廓研究[J].長江科學(xué)院院報(bào)，2016，33（11）：1-4.（LI Y F， TAN D B， GAO G， et al. Extraction of building contour from point clouds using dual threshold Alpha Shapes algorithm[J]. Journal of Yangtze River Scientific Research Institute， 2016，33（11）： 1-4.）

[17] 朱杰，孫毅中.多約束的平面點(diǎn)集形狀重構(gòu)方法[J].測繪學(xué)報(bào)，2017，46（2）：253-264.（ZHU J， SUN Y Z. An efficient approach to shape reconstruction from planar point set based on multi-constraints[J]. Acta Geodaetica et Cartographica Sinica， 2017，46（2）：253-264.）

[18] WU L， XU Y， WANG Q， et al. Mapping global shipping density from AIS data[J]. Journal of Navigation， 2017， 70（1）：67-81.