基于TDD的科考船航跡分段方法研究

王建 史景聰 黃冬梅 鄭小羅 何盛琪 張北辰

研究論文

基于TDD的科考船航跡分段方法研究

王建1史景聰1黃冬梅1鄭小羅1何盛琪1張北辰2

(1上海海洋大學(xué), 上海 201306;2中國極地研究中心, 上海 200136)

“雪龍”號極地科考船是推動我國極地科學(xué)考察事業(yè)發(fā)展的重要工具, “雪龍”號在數(shù)十次的極地科考過程中累積了大量的航跡數(shù)據(jù), 其中蘊含的巨大價值亟須挖掘。針對科考船的航跡分段是將科考船移動軌跡分為停留與行駛兩部分, 合理的分段方法可以分離出信息更豐富的航跡段, 有利于航跡知識提取。然而, 由于原始航跡信息密度分布不均等原因, 現(xiàn)有的航跡分段方法往往會造成分段過多等問題, 結(jié)果并不理想。本文針對該問題, 提出了一種針對科考航跡整體的時域差分(Time Domain Difference, TDD)分段方法。本方法基于時間域?qū)剿龠M行差分處理, 有效降低了因為航速波動頻繁對分段結(jié)果的影響。同時, 考慮到該方法的差分步長在航跡處理過程中的不明確性, 本文將差分后航跡的路程損失和航速波動幅值進行歸一化處理, 提出了航跡差分時間步長的動態(tài)確定方法, 并以速率閾值對航跡進行分段。最后本文以第29次南極科考航跡數(shù)據(jù)為例, 將本方法與經(jīng)典的具有噪聲的基于密度的聚類方法DBSCAN(Density-Based Spatial Clustering of Applications with Noise)進行了比較, 實驗結(jié)果表明本文提出的方法可有效降低航跡分段時分段過多的問題, 在分段準(zhǔn)確性和時間效率等方面結(jié)果更優(yōu)。

科考航跡 時域差分 停留 步長 DBSCAN

0 引言

我國近年來在極地考察領(lǐng)域取得了很大的進展, “雪龍”號作為我國極地科考不可或缺的破冰船, 是科學(xué)家們赴兩極地區(qū)科考的有力支撐。在“雪龍”號航行的幾十年間, 極地科考距離遠(yuǎn), 周期往往長達(dá)數(shù)月之久, 每次出航都會產(chǎn)生數(shù)萬甚至數(shù)十萬不等的航跡點, 累積了大量的航跡數(shù)據(jù)。作為重要的極地科考成果之一, 科考航跡數(shù)據(jù)按照一定采集頻率獲得了連續(xù)時空點序列, 每個航跡點都記錄了科考船在該點的時間、位置、航向、速度等運動信息, 歷史航跡數(shù)據(jù)蘊含極大的研究價值, 并可為后續(xù)航行提供重要參考。但同時, 科考航跡數(shù)據(jù)具有周期長、單條數(shù)據(jù)量大、采樣間隔不一、信息密度不均等特點, 給航跡數(shù)據(jù)的處理、分析和挖掘帶來了困難與挑戰(zhàn)。

航跡分段可根據(jù)船行速度將航跡分為停留與行駛兩部分。停留是指船在某一位置停泊超過一定時間(如船只入港后下錨、裝卸貨物等), 或是在一定區(qū)域內(nèi)徘徊、迂回等狀態(tài), 且此過程也超過一定時間。行駛是指船舶在停留區(qū)之間的移動過程狀態(tài), 期間正常速度高于停留狀態(tài)[1-3]。其中停留部分是航行的重要節(jié)點, 可提取出航行路徑、船只狀態(tài)、考察區(qū)域等重要活動信息, 是分段研究的重要目標(biāo)之一。合理的航跡分段算法可以有效提取出停留航段信息, 減少航跡冗余, 降低處理成本, 在船只行為分析、異常檢測、航跡規(guī)劃和快速可視化展示等方面[4-8]提供有力的技術(shù)支撐。

1 相關(guān)工作

近年來針對“雪龍”號的船行狀況[9]、破冰模式[10]及監(jiān)控系統(tǒng)[11]等都有研究, 然而針對科考航跡分段方法的研究較少。在陸路軌跡及船舶自動識別系統(tǒng)(Automatic Identification System, AIS)等航跡分段方法研究方面, 歸納起來主要可以分為以下3類。

(1)基于速率的分段

2003年Ashbrook和Starner[12]將汽車軌跡的停與留以速度是否為零進行了簡單的粗分段。Krumm和Horvitz[13]針對由GPS定位誤差造成停留識別錯誤的問題做出改進, 通過定義時間閾值與平均速度閾值, 并計算超過該時間閾值內(nèi)的平均速度是否低于速度閾值, 對軌跡的停留進行分段。彭祥文等[14]通過設(shè)置的移動目標(biāo)轉(zhuǎn)向角閾值和速度變化率閾值進行軌跡分段, 計算得到相鄰軌跡點的航行差值以及速率變化后與預(yù)先設(shè)定的值比較, 滿足其中一個則以該點為斷點進行軌跡分段。

(2)基于候選停留區(qū)的航跡分段

Alvares等[15]通過預(yù)先定義重點區(qū)域的邊界和大小, 再判斷航跡在區(qū)域內(nèi)的停留時間是否達(dá)到閾值來獲取停留信息。齊凌艷等[1]定義抽取子軌跡要考慮的三個因素: 時間閾值、距離閾值、地理位置, 通過計算目標(biāo)到達(dá)目的位置后在停留區(qū)內(nèi)的移動距離、到達(dá)及離開時間, 判斷是否滿足設(shè)置閾值, 來獲取軌跡的停留信息。

(3)基于聚類的分段

杜勝蘭等[16]采用DBSCAN算法對武漢大學(xué)校內(nèi)的大量學(xué)生軌跡進行處理, 結(jié)合校園超市、教學(xué)樓等地理信息提取停留特征, 用于分析武大學(xué)生的特定群體行為。權(quán)宇澄和吳健平[17]提出了以時間為聚類核心距的DBSCAN改進算法, 該算法一定程度上解決了航跡數(shù)據(jù)采樣間隔不均的問題。Pallotta等[18]使用DBSCAN算法基于航跡點聚類去除不可用數(shù)據(jù), 進一步識別具有異常行為的航跡, 搭建了船只航跡異常檢測和路線預(yù)測框架。

在現(xiàn)有航跡分段方法中, 基于速率閾值分段的方法在移動目標(biāo)速度波動頻繁時容易造成分段過多的問題; 候選停留區(qū)方法, 由于海上區(qū)域邊界不明確且無路網(wǎng)匹配, 并不適用于海上航跡分段; 聚類分段方法容易受采樣密度和空間重疊等因素的影響, 時間復(fù)雜度較高。綜上所述, 針對陸路及海上AIS航跡分段方法的研究雖然取得了一定進展, 但分段效率和準(zhǔn)確性方面仍有待進一步提升。本文在分析現(xiàn)有分段方法基礎(chǔ)上提出了一種針對科考航跡整體的時域差分分段方法(TDD), 并動態(tài)地解決了差分步長在航速差分過程中的不明確問題, 最后通過與航跡分段的經(jīng)典算法DBSCAN進行對比, 驗證了本文方法的有效性。

2 研究方法

本研究的技術(shù)路線如圖1所示。首先提取原始航跡數(shù)據(jù)中包含必要信息的航跡點作為可用航跡數(shù)據(jù), 并進行插值擬合處理, 減少因數(shù)據(jù)缺失或采樣間隔差異對采樣點空間密度分布的影響, 然后根據(jù)采樣點的經(jīng)緯度計算得到航跡點的航程數(shù)據(jù), 并采用差分法對航跡做多階差分處理, 在多階差分?jǐn)?shù)據(jù)的基礎(chǔ)上通過歸一化方法求得航程損失與航速標(biāo)準(zhǔn)差的平衡點, 確定合適的差分步長。最后計算原始航跡數(shù)據(jù)的平均航速作為分段閾值, 實現(xiàn)航跡分段。下面將針對技術(shù)路線中的多階差分計算和動態(tài)差分步長確定進行進一步說明。

圖1 基于TDD的科考航跡分段技術(shù)路線

Fig.1. Technical route of track segmentation for scientific expedition based on TDD

2.1 多階差分計算

式(1)中各參數(shù)定義與計算方法如下。

圖2 原始航速數(shù)據(jù)

Fig.2. Original speed data

圖3 多階航跡差分

Fig.3. Multi-order track difference

2.2 動態(tài)差分步長的確定

差分法通過增大差分步長來計算較長時間段內(nèi)的平均航速, 使得航速狀態(tài)的改變更加明顯, 便于航跡分段, 但差分步長過大時也會帶來數(shù)據(jù)失真較大的問題。由于差分步長過大使得多個航速峰值和谷值等特征點缺失, 導(dǎo)致過度縮小航速狀態(tài)差異, 造成相鄰分段被合并而分段過少的問題, 如圖3中的圖d所示。不同航跡有著不同的停留分布與特點, 造成航跡分段時的差分步長也有所不同。因此, 動態(tài)地確定差分步長對航跡的準(zhǔn)確分段有著重要的影響。

比較不同差分步長的差分結(jié)果后, 可發(fā)現(xiàn)鋸齒狀航速的幅值過大是造成分段過多的主要原因, 而鋸齒現(xiàn)象的嚴(yán)重程度可以通過航速的標(biāo)準(zhǔn)差來衡量, 且隨著差分步長的增大, 航速標(biāo)準(zhǔn)差逐漸減小。同時, 采用差分法所獲得的差分航速是伴隨著路程損失的, 隨著差分步長的增大, 路程損失也隨之增大。圖4為航跡的路程損失和航速標(biāo)準(zhǔn)差隨差分步長增大的變化圖, 可以看出路程損失隨差分步長的增大而增大, 與差分步長正相關(guān), 而航速標(biāo)準(zhǔn)差則相反, 與差分步長負(fù)相關(guān)。

對同一航跡不同差分步長的航速標(biāo)準(zhǔn)差和路程損失采用歸一化方法處理后求交點[21], 可在航速標(biāo)準(zhǔn)差和路程損失帶來的影響中求取一個平衡點, 得到相對合理的差分步長值。航速的標(biāo)準(zhǔn)差公式為:

其中v為原始航跡的速度平均值。路程損失為:

其中S為當(dāng)前路程值,S為實際路程值,S為路程損失值。將多階差分步長的航速標(biāo)準(zhǔn)差和路程損失值歸一化處理, 即

其中, 為航速最大標(biāo)準(zhǔn)差, 為航跡最大路程損失值。當(dāng)式(6)成立時, 可求得即為適用于當(dāng)前航跡分段的差分步長值。