基于特征點篩選的漁船軌跡壓縮方法及優化

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

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

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

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

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

1 算法建立和實現

1.1 FMDP軌跡壓縮方法

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

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

1.2 留點篩選

1.2.1 軌跡點間距離

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

(1)

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

1.2.2 停留點閾值設定

依據不同區域行駛距離與所用的時間,求取出不同區域的平均速度作為該區域漁船行駛速度,并篩選出最慢的行駛速度vmin,并根據AIS數據發送的最短時間間隔與速度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,其距離之和根據公式(1)將經緯度轉換為笛卡爾坐標系再進行計算。將距離之和與閾值l0進行對比,如果di小于l0則取中間的點pi+1作為停留點,之后繼續計算軌跡點pi+1到pi+2,pi+2到pi+3的距離之和與閾值l0進行判定,直至將軌跡點集T中所有符合條件的停留點全部篩選出為止,并將這些停留點組成停留點點集ts。

1.3 特征點篩選

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

(3)

式中:x與y為通過投影將經緯度轉化到同一平面坐標的經度與緯度。k和b是笛卡爾坐標系中的常數。

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

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

軌跡點的轉向角度由連續的3個AIS點構成,3個AIS點依次相連,所構成線段的角度即為轉向角度。設定軌跡點的角度閾值,當軌跡點滿足角度閾值條件,但未滿足原始DP算法的特征點選擇條件時,仍可作為特征點計入特征點集TR。

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

(4)

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

圖1 第一階段軌跡壓縮率

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

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

1.4 軌跡點集結合處理

1.5 復雜軌跡壓縮權重機制

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

在每個停留點區間,由于漁船長時間的停留出現多個相同的坐標點集,每個點集均是相同的坐標點所組成。設在此區間中坐標點集的個數為m,將坐標點集個數m與停留點個數δ相比較:

(1)當坐標點集個數m小于停留點個數δ時,只保留該區間的首尾停留點。

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

(5)

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

圖3 算法流程

2 試驗驗證與算法對比

2.1 參數設定

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

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

(6)

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

2.2 壓縮效率對比試驗

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

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

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

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

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

(2)壓縮率對比試驗

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

表1 兩種壓縮算法的試驗結果

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

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

表2 權重對壓縮率影響的試驗結果部分樣例

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

圖5 A組復雜軌跡壓縮率對比圖

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

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

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

3 結論

本研究基于原始DP算法設計了一種特征點分離的多閾值DP算法,并加入權重機制的優化研究。

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