基于特征點篩選的漁船軌跡壓縮方法及優(yōu)化

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

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

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

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

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

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

1.1 FMDP軌跡壓縮方法

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

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

1.2 留點篩選

1.2.1 軌跡點間距離

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

(1)

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

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

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

l0=vmin×tmin

(2)

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

1.2.3 停留點篩選

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

1.3 特征點篩選

1.3.1 原始DP算法的軌跡特征點篩選處理

(3)

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

1.3.2 加入了角度閾值的軌跡壓縮特征點篩選

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

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

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

(4)

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

圖1 第一階段軌跡壓縮率

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

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

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

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

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

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

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

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

(5)

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

圖3 算法流程

2 試驗驗證與算法對比

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

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

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

(6)

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

2.2 壓縮效率對比試驗

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

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

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

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

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

(2)壓縮率對比試驗

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

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

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

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

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

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

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

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

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

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

3 結(jié)論

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

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