基于軌跡圖像特征匹配的漁船軌跡相似度計算和軌跡分類①

徐文進,解 欽,黃海廣

1(青島科技大學(xué) 信息科學(xué)技術(shù)學(xué)院,青島 266061)

2(溫州大學(xué) 計算機與人工智能學(xué)院,溫州 325035)

據(jù)農(nóng)業(yè)部2019年統(tǒng)計,我國現(xiàn)擁有漁船73.12 萬艘,從事漁業(yè)的人口為1828.02 萬人.全社會漁業(yè)經(jīng)濟總產(chǎn)值26406.50 億元,其中海洋捕撈產(chǎn)值為2116.02 億元[1].在海洋捕撈給人們帶來豐厚經(jīng)濟收入的同時,也使得我國的漁業(yè)發(fā)展遇到了許許多多的問題.隨著出海捕撈成本變高,近海捕撈作業(yè)能力增強,導(dǎo)致我國漁業(yè)資源衰退較為嚴(yán)重和分布范圍變得不均衡.由于漁民作業(yè)方式不規(guī)范及相關(guān)部門監(jiān)管能力不足,海洋生態(tài)環(huán)境遭到嚴(yán)重的破壞.另外,作為海洋經(jīng)濟產(chǎn)值的重要組成部分,越來越多的沿海國家開始大力發(fā)展海洋漁業(yè)的科技信息化和現(xiàn)代化.因此,為了能夠解決漁業(yè)發(fā)展面臨的問題和應(yīng)對其他國家的競爭,我國也開始推動漁業(yè)信息化的建設(shè).其中,實現(xiàn)現(xiàn)代化至關(guān)重要的過程就是實現(xiàn)數(shù)據(jù)的采集和合理分析應(yīng)用.AIS 系統(tǒng)作為漁業(yè)監(jiān)管中不可或缺的手段,它被廣泛應(yīng)用于海上行駛、信息通信和生產(chǎn)作業(yè)等方面.另外,該系統(tǒng)能夠?qū)崟r采集海上作業(yè)漁船的位置、速度和轉(zhuǎn)向角等數(shù)據(jù),并通過衛(wèi)星與地面基站進行接收和通信,從而實現(xiàn)作業(yè)漁船的海上管理和監(jiān)控.但是,AIS 數(shù)據(jù)只包含了漁船自身的信息和實時航行數(shù)據(jù),并不包含漁船的捕撈方式、作業(yè)狀態(tài)和捕魚熱點等深層次信息,這就要求進一步的通過分析航行狀態(tài)數(shù)據(jù)來獲取.傳統(tǒng)的方法對AIS 數(shù)據(jù)的研究和挖掘不夠深入,但隨著人工智能的快速發(fā)展,將機器學(xué)習(xí)應(yīng)用到漁船軌跡的分析中,對實現(xiàn)漁船行為的實時監(jiān)控、作業(yè)漁場的發(fā)現(xiàn)、捕撈強度的挖掘和掌握漁業(yè)資源變動等問題具有重要的意義[2].

為了獲取漁船之間的作業(yè)關(guān)系、發(fā)現(xiàn)捕魚熱點以及精準(zhǔn)預(yù)測漁船未來的軌跡,劃分漁船軌跡類型成為了至關(guān)重要的一步.然而,劃分漁船軌跡類型的主要方式就是計算軌跡相似度,文獻[3]中謝彬等基于歐式距離對移動對象進行軌跡相似度的計算,該算法適用于獲取的軌跡中軌跡點的個數(shù)要跟隨時間序列一一對應(yīng).文獻[4]采用弗雷歇算法對船舶軌跡相似度進行建模,然后使用DBSCAN對軌跡進行聚類,最后得到了經(jīng)典軌跡模型.Zhen 等在文獻[5]里整合k-medoids 聚類和樸素貝葉斯分類器,實現(xiàn)了船舶作業(yè)行為的分類和異常行為的檢測.文獻[6]使用原始的動態(tài)規(guī)劃算法和DBSCAN 聚類實現(xiàn)了漁船軌跡的快速分類識別.涂剛凱等[7]使用傳統(tǒng)的LCSS 算法從海量人員時空軌跡數(shù)據(jù)中挖掘人員之間的關(guān)系,但是最長公共子序列算法出現(xiàn)了時間閾值選取的敏感性問題,并且該算法允許跳過某些軌跡點所以是一種非常粗糙的軌跡相似度度量方法.Lee 等[8-11]使用了多次的軌跡聚類算法,對軌跡段的形狀、特征角點、線段角度等進行線性處理來描述相似度,并對漁船的軌跡實現(xiàn)了線性化的分段和聚類.然而,軌跡的切片標(biāo)準(zhǔn)難以確定,很難將軌跡段劃分為同類型的片段,這也導(dǎo)致軌跡的分段聚類方法效果不穩(wěn)定以及計算復(fù)雜等問題[12].以上方法雖然都取得了不錯的效果,但是均未充分考慮海上捕撈航行軌跡的特點,因而存在種種不足.

本文在對漁船AIS 數(shù)據(jù)進行可視化之后,發(fā)現(xiàn)某些漁船的軌跡是很相似的,這是因為捕魚區(qū)的位置在較長時間內(nèi)是不會發(fā)生變化以及漁船之間存在協(xié)同作業(yè)的行為.針對這種特點,論文提出了一種基于軌跡圖像的相似度計算方法,這種方法使用了圖像特征點檢測、特征點描述與特征點匹配,然后設(shè)定閾值來進行軌跡的分類.通過這種方法使得計算軌跡相似度的方法轉(zhuǎn)換為計算圖像相似度的方法,從而使計算效率和速度提高,并且結(jié)果可視化.經(jīng)過劃分漁船軌跡之后,可以更好的對軌跡數(shù)據(jù)進行挖掘,能夠有效地發(fā)現(xiàn)漁船之間的協(xié)作關(guān)系、訓(xùn)練分類漁船預(yù)測模型.

1 相關(guān)概念

ORB 將FAST 算法和BRIEF 算法進行了結(jié)合,并在兩種算法的基礎(chǔ)上添加了圖像旋轉(zhuǎn)與尺度不變性以及特征提取速度快的優(yōu)點[13].首先,它通過FAST 來獲取圖像的特征點,然后使用BRIEF對特征點進行描述.

1.1 FAST 特征點

FAST (Features from Accelerated Segment Test)是一種快速的特征檢測算法.首先,它通過計算隨機選取的像素點與其鄰域的像素差值,若存在連續(xù)數(shù)個像素點的灰度值大于預(yù)先設(shè)定的閾值,即認(rèn)為該像素點為特征點,但是該特征點不具有旋轉(zhuǎn)不變性[14].針對這一個問題,ORB 算法使用灰度質(zhì)心法為每個檢測到的特征點添加一個主方向.特征點的灰度矩陣定義為:

其中,I(x,y)為點(x,y) 處的灰度值,那么圖像的質(zhì)心C為:

那么質(zhì)心與特征點之間的夾角定義為該檢測點的方向:

另外,將x和y的取值范圍設(shè)定在半徑為r的圓形區(qū)域內(nèi),即x,y∈[-r,r],這能夠提升算法的旋轉(zhuǎn)不變性.

1.2 BRIEF 特征描述符

BRIEF (Binary Robust Independent Elementary Features)用來對特征點進行描述.首先,它在特征點附近隨機選取若干像素點,計算這些點對的二值響應(yīng)值,然后由這些響應(yīng)值構(gòu)成特征點的描述符.

在該算法中使用長度為n的二值碼串來描述特征點,其中,這個二值碼串是由特征點周圍的n個像素點對生成的,將這2n個點 (xi,yi),i=1,2,···,2n組成一個矩陣S:

然后,使用鄰域方向 θ和對應(yīng)的旋轉(zhuǎn)矩陣Rθ,構(gòu)建S的一個矯正版本Sθ,那么:

其中,θ是式(3)中特征點求得的主方向.

2 本文算法

計算軌跡相似度的過程中主要是軌跡特征點檢測、特征點描述,最后是特征匹配.圖像特征點檢測的關(guān)鍵在于角點檢測,角點的特性是向任何方向移動像素的變化都很大.本文中使用ORB 特征檢測和BF 匹配計算軌跡圖片的相似度,其中BF 匹配是一種暴力匹配的方式,它將計算樣本圖片中的每一個特征點與對照圖片中的所有特征點之間漢明距離,然后選擇最近鄰和次近鄰的兩個特征點,設(shè)定最近鄰距離除以次近鄰距離的比率小于某個閾值來進行特征點篩選.

假設(shè)樣本圖片的特征點個數(shù)為numx,樣本某一特征點與最近鄰特征點M、次近鄰特征點N的距離分別為disM、disN,則閾值η為:

滿足閾值η的特征點個數(shù)為numy,則相似度ζ為:

為了計算軌跡圖像相似度,設(shè)計了算法1.

算法1.漁船捕撈軌跡圖像相似度算法1) 將漁船AIS 數(shù)據(jù)轉(zhuǎn)換為可視化圖像,圖像只保留軌跡,并設(shè)定軌跡圖像大小;2) 從文件夾中讀取軌跡圖像,并將軌跡圖像轉(zhuǎn)換為灰度圖;

3) 使用ORB 特征檢測器對軌跡圖像進行特征檢測,并對特征點使用BRIEF 算法進行描述;4) 使用BF 暴力匹配的方式,將樣本圖片中的每一個特征點與對照圖片中的所有特征點計算漢明距離;η numy/numx 5) 選擇最近鄰M和次近鄰N 兩個特征點計算閾值.然后計算滿足閾值的特征點的個數(shù)占總特征點的比例,此值即為相似度;6) 將相似度滿足閾值的軌跡劃分為同一類別.

3 實驗

3.1 實驗數(shù)據(jù)

漁船AIS 數(shù)據(jù)來源于浙江省海洋與漁業(yè)局,其中漁船均在浙江登記,數(shù)據(jù)格式如表1所示.由于設(shè)備或者其它異常原因會出現(xiàn)一些錯誤,要對異常、錯誤或者不符合范圍的數(shù)據(jù)進行分析和過濾.首先設(shè)定了漁船的海上航行范圍:經(jīng)度范圍[105°,130°],緯度范圍[10°,40°].其次設(shè)定漁船的速度區(qū)間,因為漁船的行為分為:拋錨、捕撈、航行,所以每種行為對應(yīng)不同的速度區(qū)間.根據(jù)統(tǒng)計可得,漁船拋錨時的速度接近于0 節(jié),捕撈時的速度為0～5.5 節(jié),正常航行的速度為5.5～12節(jié),所以選擇0～12 節(jié)作為速度區(qū)間.

表1 漁船AIS 數(shù)據(jù)格式表

如圖1,編號為29902的漁船在2016年4月～2016年6月3 個月,漁船的真實軌跡點數(shù)據(jù)共計18 049 條.

圖1 編號為29902的漁船軌跡

3.2 捕魚熱點實驗

針對前文所述,本文使用2015年、2016年的漁船數(shù)據(jù)做了熱力圖對比,如圖2所示.通過實驗發(fā)現(xiàn),沿海區(qū)域以及遠(yuǎn)海區(qū)域的捕魚熱點變化較小,主要是海洋中部區(qū)域有些許變化,捕魚熱點整體呈穩(wěn)定趨勢.

圖2 2015年、2016年捕魚熱力圖

3.3 實驗結(jié)果

經(jīng)過本文中提出的軌跡圖像相似度計算方法,可以快速、有效地進行計算和分類,文中選取部分劃分類型的漁船軌跡進行比對.由圖3、圖4、圖5所示,漁船軌跡劃分類型準(zhǔn)確率高,各類型的主要軌跡相同.通過這種方式,也可以清晰獲取漁船之間的協(xié)作關(guān)系以及捕魚熱點的發(fā)現(xiàn).下文中選取兩組漁船的軌跡圖像,通過匹配特征來驗證算法.

圖3 A 組部分漁船2016年4月至5月軌跡

圖4 B 組部分漁船2016年4月至5月軌跡

圖5 C 組部分漁船2016年4月至5月軌跡

如圖6所示,選擇兩組軌跡圖像其部分特征點進行特征匹配,并且特征點之間匹配度高.其中,存在某些特征點匹配發(fā)生偏移的現(xiàn)象,主要原因在于軌跡圖像過于繁雜,導(dǎo)致部分特征模糊.

圖6 兩對漁船軌跡特征點匹配

本文選擇傳統(tǒng)的軌跡相似度算法DTW (Dynamic Time Warping)和LCSS (Longest Common SubSequence)作為對照.通過表2可知,在浙江漁船的數(shù)據(jù)集上,本文算法在時間和準(zhǔn)確率上都有較好的效果,其中時間一欄代表一條漁船軌跡與其他漁船軌跡匹配一輪所花費的時間.傳統(tǒng)方法的不足之處在于,一方面兩者均是動態(tài)算法,復(fù)雜的計算帶來了較大的時間消耗.另一方面,LCSS 只關(guān)注于局部匹配,而DTW對噪音和離群點的抑制效果較差.對于本文算法來說,本質(zhì)是將軌跡點之間的計算轉(zhuǎn)換為圖像點之間的計算,這種方法提高了計算效率和準(zhǔn)確率.

表2 算法效果對比

4 結(jié)論與展望

通過實驗驗證了本文所提出的圖像軌跡相似度算法可以有效并快速地對軌跡進行計算和分類,也驗證了捕魚熱點區(qū)域隨時間變化較小.文中提出的ORB 算法和暴力匹配的方法可以對圖像進行特征點檢測、描述以及匹配,但是這種方法需要多次實驗嘗試不同的閾值.另外,由實驗結(jié)果可發(fā)現(xiàn),處理之后的軌跡圖像存在冗余的現(xiàn)象.所以接下來的研究工作,一方面要進一步處理漁船AIS 數(shù)據(jù),壓縮軌跡數(shù)據(jù);另一方面需要嘗試改進算法,將人為設(shè)定的閾值改為算法設(shè)定.