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

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

研究論文

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

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

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

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

科考航跡 時(shí)域差分 停留 步長(zhǎng) DBSCAN

0 引言

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

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

1 相關(guān)工作

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

(1)基于速率的分段

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

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

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

(3)基于聚類(lèi)的分段

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

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

2 研究方法

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

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

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

2.1 多階差分計(jì)算

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

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

Fig.2. Original speed data

圖3 多階航跡差分

Fig.3. Multi-order track difference

2.2 動(dòng)態(tài)差分步長(zhǎng)的確定

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

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

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

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

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

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