馬蘇上,王澤宇,劉明劍,2,李 洋,趙文彬

(1 大連海洋大學(xué)信息工程學(xué)院,遼寧 大連 116023;2 設(shè)施漁業(yè)教育部重點(diǎn)試驗(yàn)室(大連海洋大學(xué)),遼寧 大連 116023)

近年來漁民捕撈經(jīng)濟(jì)在海洋經(jīng)濟(jì)中日益重要[1],2021年海洋捕撈產(chǎn)值為2 303.72億元,漁船作為漁民捕撈的工具,加強(qiáng)對漁船的行為監(jiān)管,是保障漁業(yè)健康有序地發(fā)展的重要手段[2-3]。漁船在作業(yè)過程中呈現(xiàn)出撈區(qū)域繁多、分布廣、持續(xù)作業(yè)時(shí)間長等特點(diǎn)[4],這就需要在監(jiān)管過程中,對漁船不同作業(yè)特點(diǎn)的軌跡進(jìn)行差異化分析。目前常用的船舶軌跡跟蹤方式是使用船舶自動識別系統(tǒng)[5](Automatic Identification System,AIS)對漁船行駛軌跡進(jìn)行記錄與存儲,但在此過程中,AIS系統(tǒng)會產(chǎn)生大量的軌跡數(shù)據(jù)[6],不僅消耗系統(tǒng)存儲與計(jì)算資源,還存在大量的冗雜和錯(cuò)誤信息[7],不利于對船舶軌跡的有效分析。如海上漁船由于捕撈作業(yè)會產(chǎn)生大量的靜態(tài)信息,此時(shí)僅需保留幾條有效的信息,就可以有效的反映漁船的作業(yè)狀態(tài),因此需要采用軌跡壓縮方法對漁船軌跡數(shù)據(jù)進(jìn)行篩選,從而為漁船行為有效分析提供高精度的軌跡數(shù)據(jù)支撐。

針對上述需求,國內(nèi)外的研究學(xué)者開展了關(guān)于漁船軌跡壓縮方面的相關(guān)研究,目前船舶軌跡壓縮方法大致分為兩類[8]:在線軌跡壓縮方法;離線軌跡壓縮方法。在線壓縮算法為局部處理算法,處理速度較快。其中,Keoghe等[9]采用滑動窗口方式實(shí)現(xiàn)了在線壓縮;文獻(xiàn)[10-12]通過在滑動窗口中加入閾值方式來提升壓縮效率。但以上方法沒有考慮部分特征點(diǎn)對整條軌跡曲線存在軌跡信息量不均衡現(xiàn)象,當(dāng)刪除一些極值點(diǎn)后易造成軌跡失真,不利于漁船軌跡分析;離線軌跡壓縮方法,則是對于全局?jǐn)?shù)據(jù)進(jìn)行分析處理,保證了所有軌跡點(diǎn)都需進(jìn)行判別[13],更適于對漁船軌跡進(jìn)行分析。Mancini等[14]提出了均勻采樣方法,實(shí)現(xiàn)軌跡壓縮;Douglas等[15]提出的Douglas-Peucker(簡稱DP)算法,將軌跡的起始點(diǎn)相連接作為基線,根據(jù)其余軌跡點(diǎn)到直線的垂直歐式距離來進(jìn)行軌跡的壓縮。在DP算法的基礎(chǔ)上,文獻(xiàn)[16-17]通過修改數(shù)據(jù)集、去除數(shù)據(jù)冗余信息來實(shí)現(xiàn)高效漁船軌跡壓縮;文獻(xiàn)[18-19]考慮了船舶軌跡的壓縮形狀,有效保留了船舶航行中作業(yè)的重要特征信息,減少了算法的時(shí)間復(fù)雜度。文獻(xiàn)[20-21]著重研究閾值對于軌跡壓縮的影響,根據(jù)不同情況改變閾值,實(shí)現(xiàn)更精確的壓縮。文獻(xiàn)[22-24]通過引入時(shí)間維度信息來對漁船航向速度等動態(tài)數(shù)據(jù)進(jìn)行壓縮,能夠保留更多的重要動態(tài)行為軌跡點(diǎn)。

盡管上述方法對于離線軌跡壓縮的處理趨于完善,但目前離線壓縮算法無法妥善處理和反映船舶的這些動態(tài)變化特征信息,導(dǎo)致其算法運(yùn)行的時(shí)間復(fù)雜度較高,且軌跡壓縮的誤差較大,致使軌跡壓縮后存在失真的問題。針對上述問題,本研究提出了FMDP漁船軌跡壓縮方法,在保證壓縮率的前提下最大程度保留了漁船軌跡的特征信息。

1 算法建立和實(shí)現(xiàn)

1.1 FMDP軌跡壓縮方法

設(shè)漁船在行駛過程中,AIS軌跡點(diǎn)為p(x,y),由軌跡點(diǎn)p所組成的軌跡點(diǎn)集為T。漁船在某一位置長時(shí)間停留或移動距離極短的點(diǎn)被稱之為停留點(diǎn),停留點(diǎn)集為ts。

FMDP軌跡壓縮方法:首先,將原始軌跡T進(jìn)行停留點(diǎn)篩選出并計(jì)入停留點(diǎn)集ts(ts?T),同時(shí),針對漁船行為停留時(shí)間較長,造成的差異化停留與轉(zhuǎn)向狀態(tài)特征,設(shè)計(jì)壓縮軌跡權(quán)重機(jī)制,對停留點(diǎn)集ts再次篩選;其次,使用加入角度閾值的DP算法進(jìn)行軌跡壓縮處理完成特征點(diǎn)篩選,組成特征點(diǎn)集tr(tr?T);最后,取ts和tr的交集為整合點(diǎn)集tA,將tA按照時(shí)間順序的軌跡點(diǎn)串聯(lián)得到新的壓縮軌跡。

1.2 留點(diǎn)篩選

1.2.1 軌跡點(diǎn)間距離

停留是移動對象的基本運(yùn)動狀態(tài),代表著軌跡中具有重要特征的點(diǎn)序列[25]。當(dāng)漁船停留時(shí)可能會因?yàn)橥饨缫蛩鼗蛘咦陨硪蛩匕l(fā)生偏移現(xiàn)象,導(dǎo)致停留點(diǎn)并不是固定的點(diǎn)。為了可以更準(zhǔn)確判別軌跡點(diǎn)是否屬于停留點(diǎn),進(jìn)行如下設(shè)定:將某條漁船的原始漁船軌跡點(diǎn)集T依次分成n個(gè)船速計(jì)算區(qū)域,其中每個(gè)區(qū)域包含五百個(gè)AIS軌跡數(shù)據(jù)點(diǎn)?？紤]任意相鄰的軌跡點(diǎn)之間距離并不屬于直線距離,因此本研究將軌跡點(diǎn)的經(jīng)緯度坐標(biāo)轉(zhuǎn)換為笛卡爾坐標(biāo),進(jìn)行距離度量。軌跡點(diǎn)距離d是兩個(gè)相鄰的軌跡點(diǎn)的恒向線[26],其距離公式如下:

(1)

式中:Δx和Δy分別為兩個(gè)相鄰軌跡點(diǎn)的經(jīng)緯度差值[27],(°);c為結(jié)合后續(xù)計(jì)算所設(shè)計(jì)的參數(shù)系數(shù);r為地球的半徑,km;a是用來將經(jīng)度轉(zhuǎn)換的等量維度系數(shù)。

1.2.2 停留點(diǎn)閾值設(shè)定

依據(jù)不同區(qū)域行駛距離與所用的時(shí)間,求取出不同區(qū)域的平均速度作為該區(qū)域漁船行駛速度,并篩選出最慢的行駛速度vmin,并根據(jù)AIS數(shù)據(jù)發(fā)送的最短時(shí)間間隔與速度vmin,求出最短的距離l0,作為停留點(diǎn)閾值:

l0=vmin×tmin

(2)

式中:l0為最短的距離,km;vmin為行駛速度,km/s;tmin為停留時(shí)間,s。

1.2.3 停留點(diǎn)篩選

隨后將點(diǎn)集T中的軌跡點(diǎn)pi到pi+1的距離為di,pi+1到pi+2所組成線段距離為di+1,兩線段的距離之和為di+di+1,其距離之和根據(jù)公式(1)將經(jīng)緯度轉(zhuǎn)換為笛卡爾坐標(biāo)系再進(jìn)行計(jì)算。將距離之和與閾值l0進(jìn)行對比,如果di小于l0則取中間的點(diǎn)pi+1作為停留點(diǎn),之后繼續(xù)計(jì)算軌跡點(diǎn)pi+1到pi+2,pi+2到pi+3的距離之和與閾值l0進(jìn)行判定,直至將軌跡點(diǎn)集T中所有符合條件的停留點(diǎn)全部篩選出為止,并將這些停留點(diǎn)組成停留點(diǎn)點(diǎn)集ts。

1.3 特征點(diǎn)篩選

1.3.1 原始DP算法的軌跡特征點(diǎn)篩選處理

(3)

式中:x與y為通過投影將經(jīng)緯度轉(zhuǎn)化到同一平面坐標(biāo)的經(jīng)度與緯度。k和b是笛卡爾坐標(biāo)系中的常數(shù)。

1.3.2 加入了角度閾值的軌跡壓縮特征點(diǎn)篩選

傳統(tǒng)的DP軌跡壓縮方法中,僅考慮了距離特性而忽略了船舶的轉(zhuǎn)向變化特性,無法保證將全部特征點(diǎn)進(jìn)行篩選,導(dǎo)致壓縮后的軌跡不能完整反應(yīng)出原始軌跡特征。因此為保證船舶的轉(zhuǎn)向信息最大保留,在DP算法原有距離閾值的基礎(chǔ)上加入了角度閾值篩選特征點(diǎn)方法。

軌跡點(diǎn)的轉(zhuǎn)向角度由連續(xù)的3個(gè)AIS點(diǎn)構(gòu)成,3個(gè)AIS點(diǎn)依次相連,所構(gòu)成線段的角度即為轉(zhuǎn)向角度。設(shè)定軌跡點(diǎn)的角度閾值,當(dāng)軌跡點(diǎn)滿足角度閾值條件,但未滿足原始DP算法的特征點(diǎn)選擇條件時(shí),仍可作為特征點(diǎn)計(jì)入特征點(diǎn)集TR。

角度閾值的選取與軌跡壓縮率有著密不可分的聯(lián)系。為了避免選取不合適角度閾值后導(dǎo)致算法對數(shù)據(jù)的壓縮率效率降低,將采取真實(shí)漁船軌跡數(shù)據(jù)進(jìn)行測算來獲得每條船在壓縮時(shí)的最佳角度閾值,通過對比不同角度下的角度軌跡壓縮率,判斷出最佳的角度閾值,計(jì)算不同角度的范圍壓縮點(diǎn)的剩余點(diǎn)數(shù)目Va與原始軌跡點(diǎn)數(shù)O結(jié)合求出角度壓縮率Ca,其公式如下:

(4)

以2018年10月1日至7日大連世想海洋科技有限公司提供的某條漁船軌跡數(shù)據(jù)為例進(jìn)行角度閾值選取。由于該船在此時(shí)間段AIS數(shù)據(jù)龐大,微小的角度變化就會造成壓縮率巨大變化,因此該算法分兩階段篩選角度閾值。第一階段篩選大致范圍,規(guī)定每10°一個(gè)區(qū)間,根據(jù)峰值挑選出合適的角度范圍,如圖1所示,當(dāng)這條漁船轉(zhuǎn)向角在40°至60°以及130°至150°時(shí)存在有最大的角度壓縮CA,因此需要對于以上兩個(gè)區(qū)間范圍繼續(xù)通過第二階段進(jìn)行篩選。

圖1 第一階段軌跡壓縮率

第二階段將挑選出的角度范圍再次細(xì)分進(jìn)行二次篩選,以確保壓縮率最大化,規(guī)定每2°一個(gè)區(qū)間,同樣根據(jù)峰值篩選出最佳角度范圍,完成最終的角度閾值確立,如圖2所示。

注:(a)圖為40°至60°區(qū)間內(nèi)的軌跡壓縮率,(b)圖為130°至150°區(qū)間內(nèi)的軌跡壓縮率

1.4 軌跡點(diǎn)集結(jié)合處理

1.5 復(fù)雜軌跡壓縮權(quán)重機(jī)制

考慮到漁船的作業(yè)類型不同,部分捕撈作業(yè)花費(fèi)時(shí)間較長,如捕撈金槍魚和石斑魚等魚類,需要在同一地點(diǎn)持續(xù)2～3 h的捕撈作業(yè)。僅依靠上述軌跡壓縮方法進(jìn)行壓縮時(shí),由于大量停留點(diǎn)被壓縮導(dǎo)致軌跡信息嚴(yán)重缺失。針對上述情況,本研究設(shè)計(jì)了壓縮軌跡權(quán)重機(jī)制,其目的在于通過對停留點(diǎn)進(jìn)行再次篩選,避免因?yàn)樽鴺?biāo)信息重復(fù)或相近而導(dǎo)致停留點(diǎn)被大量刪除。從而保留重要的軌跡特征信息。其具體方法如下:加入權(quán)重的軌跡壓縮,是在進(jìn)行FMDP算法的停留點(diǎn)篩選后,將出現(xiàn)的多個(gè)停留點(diǎn)連續(xù)區(qū)間視為停留點(diǎn)區(qū)間。在每個(gè)停留點(diǎn)區(qū)間,設(shè)停留點(diǎn)數(shù)為ns,停留時(shí)間為ts,停留閾值為β=ns/ts,對β進(jìn)行向下取整為δ,那么δ為該停留點(diǎn)區(qū)間應(yīng)保留的停留點(diǎn)個(gè)數(shù)。

在每個(gè)停留點(diǎn)區(qū)間,由于漁船長時(shí)間的停留出現(xiàn)多個(gè)相同的坐標(biāo)點(diǎn)集,每個(gè)點(diǎn)集均是相同的坐標(biāo)點(diǎn)所組成。設(shè)在此區(qū)間中坐標(biāo)點(diǎn)集的個(gè)數(shù)為m,將坐標(biāo)點(diǎn)集個(gè)數(shù)m與停留點(diǎn)個(gè)數(shù)δ相比較:

(1)當(dāng)坐標(biāo)點(diǎn)集個(gè)數(shù)m小于停留點(diǎn)個(gè)數(shù)δ時(shí),只保留該區(qū)間的首尾停留點(diǎn)。

(2)當(dāng)坐標(biāo)點(diǎn)集個(gè)數(shù)m大于等于停留點(diǎn)個(gè)數(shù)δ時(shí),并將停留點(diǎn)數(shù)目ns與δ作比,得出比值γ,保留γ倍數(shù)序號的停留點(diǎn)。其公式如下所示:

(5)

加入權(quán)重機(jī)制的FMDP算法(FMDP algorithm with Weight mechanism added,后文稱為“FMDPW算法”)雖然提高了算法的復(fù)雜度,但處理停留時(shí)間較長的漁船作業(yè)行為更加精準(zhǔn);反之,處理停留時(shí)間較短的漁船作業(yè)行為時(shí),未加入權(quán)重機(jī)制的FMDP算法更加快速準(zhǔn)確,提高了軌跡壓縮的效率,完成了對漁船不同作業(yè)類型軌跡的高效壓縮。其算法流程由圖3所示,圖3中i代表軌跡點(diǎn)從隊(duì)首到隊(duì)尾的序號;di+1代表由經(jīng)緯度坐標(biāo)系轉(zhuǎn)化為笛卡爾直角坐標(biāo)系后的第i點(diǎn)與第i+1點(diǎn)的距離。

圖3 算法流程

2 試驗(yàn)驗(yàn)證與算法對比

2.1 參數(shù)設(shè)定

為了對本研究提出的FMDP軌跡壓縮方法的準(zhǔn)確性和執(zhí)行的效率進(jìn)行驗(yàn)證。采用 Python 語言編寫,選取來自大連世想海洋科技有限公司的原始試驗(yàn)數(shù)據(jù)集起止時(shí)間為2018年1月20日到2018年12月20日,在壓縮效率方面與原始DP算法性能進(jìn)行對比評估。

評估指標(biāo):以壓縮效率作為試驗(yàn)結(jié)果參考,對FMDP與DP算法進(jìn)行評測,評測公式如下所示:

(6)

式中:Cp為壓縮率;Vp為剩余軌跡點(diǎn)數(shù);O為原始軌跡點(diǎn)數(shù)。

2.2 壓縮效率對比試驗(yàn)

對漁船作業(yè)行為進(jìn)行有效監(jiān)控的前提是完成漁船軌跡數(shù)據(jù)信息的高效壓縮處理,如通過處理壓縮軌跡中轉(zhuǎn)向與停留的特征信息,可以較為準(zhǔn)確判定漁船是否有越界、騙保等違規(guī)行為;通過數(shù)據(jù)壓縮可以刪除原始軌跡中冗雜、錯(cuò)誤的軌跡點(diǎn)。但是由于大量數(shù)據(jù)被壓縮難免出現(xiàn)重要軌跡點(diǎn)缺失的問題,例如:魷魚釣漁船在進(jìn)行捕撈作業(yè)時(shí)長時(shí)間處于漂流狀態(tài),會產(chǎn)生的大量漂流軌跡點(diǎn),之前軌跡壓縮方法會因?yàn)閿?shù)據(jù)重復(fù)將大量的停留作業(yè)軌跡點(diǎn)刪除,導(dǎo)致漁船作業(yè)信息丟失。因此為了實(shí)現(xiàn)漁船在不同作業(yè)情況均能高效地進(jìn)行軌跡壓縮,本研究依據(jù)漁船軌跡估計(jì)的復(fù)雜度在算法中加入權(quán)重機(jī)制,以此實(shí)現(xiàn)較為完整的保留漁船軌跡的特征信息。

試驗(yàn)一:FMDP算法與DP算法對比相同漁船在不同日期的軌跡壓縮情況,通過軌跡的壓縮效果,來測試FMDP算法的壓縮性能。

(1)軌跡壓縮效果情況對比

在數(shù)據(jù)集中選取一組較為復(fù)雜軌跡數(shù)據(jù),使用FMDP算法與DP算法進(jìn)行壓縮效果對比評估。如圖4所示。通過計(jì)算FMDP算法與DP算法的軌跡壓縮率Cp均超過98%,可知DP算法與FMDP算法均能實(shí)現(xiàn)對軌跡的有效壓縮,但是通過對比壓縮情況可以得出,當(dāng)漁船作出停留轉(zhuǎn)向等行為出現(xiàn)造軌跡折返時(shí),DP算法在進(jìn)行軌跡壓縮時(shí)可能會刪除速度變化較大的動態(tài)信息點(diǎn),進(jìn)而導(dǎo)致軌跡的時(shí)間特征的丟失[30],而FMDP算法會保留漁船轉(zhuǎn)向、停留的重要特征信息(圖4c中畫圈處),在確保高壓縮率的基礎(chǔ)上,保留了更多的漁船軌跡的特征信息。

圖4 12月7日軌跡壓縮對比情況

(2)壓縮率對比試驗(yàn)

為了進(jìn)一步對比FMDP算法與DP算法的壓縮效果,進(jìn)行了壓縮率的對比試驗(yàn),如表1所示,DP算法的壓縮率Cp均值為98.0%,FMDP的壓縮率Cp均值為97.5%,最低為95.51%。雖然FMDP算法在壓縮率上略低于DP算法,但依據(jù)圖4得出結(jié)論,DP算法所刪除的點(diǎn)集,大多屬于轉(zhuǎn)向點(diǎn)與停留點(diǎn)被刪除,無法反映軌跡的時(shí)間特征。

表1 兩種壓縮算法的試驗(yàn)結(jié)果

對于軌跡的整體規(guī)劃不理想。FMDP算法則是在確保壓縮率Cp平均達(dá)到97.5%的基礎(chǔ)上,保證了壓縮后軌跡具備更多特征信息。此外,通過對比兩種算法的軌跡壓縮消耗的時(shí)間可以看出,FMDP算法處理軌跡壓縮花費(fèi)時(shí)間與DP算法所消耗的時(shí)間相近,可見算法處理數(shù)據(jù)的壓縮時(shí)間不會對試驗(yàn)結(jié)果評估造成影響。

試驗(yàn)二:為判斷在FMDP算法中加入權(quán)重機(jī)制,是否在處理所有的軌跡時(shí)都具有必要性。本試驗(yàn)將待壓縮軌跡分為A,B兩組:A組為復(fù)雜漁船軌跡;B組中為簡單漁船軌跡。進(jìn)行壓縮效率的計(jì)算,其具體結(jié)果如表2所示。

表2 權(quán)重對壓縮率影響的試驗(yàn)結(jié)果部分樣例

通過對比表2中的A、B兩組數(shù)據(jù)中的壓縮率變化可以得出以下結(jié)論:FMDPW算法的壓縮率雖然要低于FMDP的壓縮率,但保留了原始軌跡中更多的特征信息,且原始軌跡復(fù)雜程度與保留的特征信息數(shù)量成正比。當(dāng)軌跡復(fù)雜需要保留更多特征信息時(shí),優(yōu)先考慮使用FMDPW算法處理原始軌跡。為進(jìn)一步證明權(quán)重機(jī)制的必要性,直觀反應(yīng)軌跡壓縮后的變化情況。試驗(yàn)篩選出A、B兩組中有代表性的數(shù)據(jù)進(jìn)行數(shù)據(jù)可視化,其對比結(jié)果如下圖5、圖6所示。

圖5 A組復(fù)雜軌跡壓縮率對比圖

圖6 B組簡單軌跡壓縮率對比圖

通過對比圖5中的數(shù)據(jù)可以看出A組數(shù)據(jù)在加入權(quán)重機(jī)制處理后,更完整地保留了原始軌跡的變化特征,可以得出結(jié)論:FMDPW算法可以有效地從船舶軌跡數(shù)據(jù)中篩選出體現(xiàn)原始軌跡特征的子集,保留原始軌跡的特征信息。雖然FMDPW算法保留了原始軌跡中更多的特征信息,但導(dǎo)致了漁船軌跡的壓縮率和壓縮效率降低。并且根據(jù)圖6可以看出,簡單的漁船軌跡在FMDPW算法壓縮后軌跡并沒有明顯變化,因此在處理簡單的漁船軌跡時(shí),無需在算法中加入壓縮權(quán)重機(jī)制。根據(jù)原始軌跡的復(fù)雜程度選擇是否進(jìn)行權(quán)重考慮,可以最大程度上保證軌跡壓縮的高效性與準(zhǔn)確性。

通過試驗(yàn)對比與壓縮率對比,可以得出FMDP算法在處理漁船軌跡時(shí)能精準(zhǔn)保留漁船的特征信息。同時(shí)FMDP算法權(quán)重機(jī)制的考慮有效避免停留點(diǎn)過多造成壓縮軌跡失真的問題。在保證高壓縮率的情況下保留軌跡特征信息。

3 結(jié)論

本研究基于原始DP算法設(shè)計(jì)了一種特征點(diǎn)分離的多閾值DP算法,并加入權(quán)重機(jī)制的優(yōu)化研究。

本研究基于原始算法首次提出了將軌跡中的停留點(diǎn)進(jìn)行分離處理的方法,并通過權(quán)重機(jī)制以及加入角度閾值改進(jìn)算法,最大程度保留了漁船軌跡的特征信息,為后續(xù)計(jì)算捕撈魚量,統(tǒng)計(jì)漁場捕撈強(qiáng)度提供數(shù)據(jù)支持,更能有效完成漁船作業(yè)行為分析,但漁船停留點(diǎn)閾值上選取需要進(jìn)一步驗(yàn)證。后續(xù)將會研究算法的最佳距離閾值與尺度變化間的定量關(guān)系,將著重考慮閾值的影響。