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

研究論文

基于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é)果表明本文提出的方法可有效降低航跡分段時分段過多的問題, 在分段準確性和時間效率等方面結(jié)果更優(yōu)。

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

0 引言

我國近年來在極地考察領(lǐng)域取得了很大的進展, “雪龍”號作為我國極地科考不可或缺的破冰船, 是科學(xué)家們赴兩極地區(qū)科考的有力支撐。在“雪龍”號航行的幾十年間, 極地科考距離遠, 周期往往長達數(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ū)域等重要活動信息, 是分段研究的重要目標之一。合理的航跡分段算法可以有效提取出停留航段信息, 減少航跡冗余, 降低處理成本, 在船只行為分析、異常檢測、航跡規(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è)置的移動目標轉(zhuǎn)向角閾值和速度變化率閾值進行軌跡分段, 計算得到相鄰軌跡點的航行差值以及速率變化后與預(yù)先設(shè)定的值比較, 滿足其中一個則以該點為斷點進行軌跡分段。

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

Alvares等[15]通過預(yù)先定義重點區(qū)域的邊界和大小, 再判斷航跡在區(qū)域內(nèi)的停留時間是否達到閾值來獲取停留信息。齊凌艷等[1]定義抽取子軌跡要考慮的三個因素: 時間閾值、距離閾值、地理位置, 通過計算目標到達目的位置后在停留區(qū)內(nèi)的移動距離、到達及離開時間, 判斷是否滿足設(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)有航跡分段方法中, 基于速率閾值分段的方法在移動目標速度波動頻繁時容易造成分段過多的問題; 候選停留區(qū)方法, 由于海上區(qū)域邊界不明確且無路網(wǎng)匹配, 并不適用于海上航跡分段; 聚類分段方法容易受采樣密度和空間重疊等因素的影響, 時間復(fù)雜度較高。綜上所述, 針對陸路及海上AIS航跡分段方法的研究雖然取得了一定進展, 但分段效率和準確性方面仍有待進一步提升。本文在分析現(xiàn)有分段方法基礎(chǔ)上提出了一種針對科考航跡整體的時域差分分段方法(TDD), 并動態(tài)地解決了差分步長在航速差分過程中的不明確問題, 最后通過與航跡分段的經(jīng)典算法DBSCAN進行對比, 驗證了本文方法的有效性。

2 研究方法

本研究的技術(shù)路線如圖1所示。首先提取原始航跡數(shù)據(jù)中包含必要信息的航跡點作為可用航跡數(shù)據(jù), 并進行插值擬合處理, 減少因數(shù)據(jù)缺失或采樣間隔差異對采樣點空間密度分布的影響, 然后根據(jù)采樣點的經(jīng)緯度計算得到航跡點的航程數(shù)據(jù), 并采用差分法對航跡做多階差分處理, 在多階差分數(shù)據(jù)的基礎(chǔ)上通過歸一化方法求得航程損失與航速標準差的平衡點, 確定合適的差分步長。最后計算原始航跡數(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)地確定差分步長對航跡的準確分段有著重要的影響。

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

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

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

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

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