基于AIS航跡和Douglas-Peucker算法的航線自動生成方法研究

張樹凱，楊家軒, 蔡 垚，史國友

(大連海事大學(xué) 航海學(xué)院，遼寧 大連 116026)

0 引 言

航行計(jì)劃是指船舶在接受航次命令后，擬定的從一個港口航行到另一港口的過程中，有關(guān)航行安全的具體措施與對策[1]。而航線設(shè)計(jì)則是其中的一項(xiàng)重要內(nèi)容。在航次開始前，二副應(yīng)依據(jù)航海圖書資料以及所查閱的海區(qū)的信息或他船的具體航行經(jīng)驗(yàn)，確定并預(yù)畫航線。超過1 500 n mile的航線還應(yīng)確定是否使用大圓航線和氣象定線等[1]。

長期以來，航線設(shè)計(jì)主要靠人工分析海圖、查閱航海圖書資料，手工繪制航線，這種傳統(tǒng)的方法存在效率低、設(shè)計(jì)質(zhì)量依賴于工作人員業(yè)務(wù)水平和工作態(tài)度等局限[2]。航線自動生成的研究，是根據(jù)起航點(diǎn)與目的地之間的航海條件尋求一條最安全、最經(jīng)濟(jì)的航線。李源惠，等[3]在研究可航行與連通性、方格序列折線化等問題基礎(chǔ)上，提出了基于網(wǎng)格模型的進(jìn)行ECDIS航線設(shè)計(jì)的方法。但該方法僅僅是基于海圖數(shù)據(jù)的，沒有考慮水文氣象因素對航線設(shè)計(jì)的影響，應(yīng)考慮推薦航線和網(wǎng)格模型組合的算法，因?yàn)樵谀承┖絽^(qū)的短航段，出于避風(fēng)等考慮，還要決定是否采用氣象定線或者避風(fēng)、避逆流等措施[1]。何立居，等[4]通過研究網(wǎng)格劃分、搜索策略、信息更新等問題提出了基于蟻群算法的航線自動生成算法。但該方法產(chǎn)生的初始航線鋸齒較多，需要根據(jù)不同的情況改變螞蟻的數(shù)量和迭代次數(shù)，否則將曲線平滑后產(chǎn)生的誤差較大，另外該方法也未考慮推薦航線氣象航線等。汪柱，等[5]根據(jù)繞行障礙區(qū)的航路二分性特點(diǎn)，定位左右子節(jié)點(diǎn)并建立航路子二叉樹，提出了基于航路二叉樹的航線自動生成方法。但航路二叉樹繞行障礙區(qū)處理不完備，效率低。

AIS基站存儲了大量AIS信息，如果能夠充分利用這些信息，從中提取已被實(shí)際航行證實(shí)可航行的航線，則可為船舶的駕駛員設(shè)計(jì)航線提供重要參考，以便尋找到一條安全、經(jīng)濟(jì)的航線，同時(shí)這也符合航線設(shè)計(jì)參考“所查閱的海區(qū)的信息或他船的具體航行經(jīng)驗(yàn)[1]”的思想。筆者在研究AIS信息編碼與解析、數(shù)據(jù)清洗異常點(diǎn)、Douglas-Peuker壓縮的基礎(chǔ)上提出基于AIS航跡的航線自動生成的方法。該方法使用Douglas-Peuker算法對原有的AIS航跡點(diǎn)進(jìn)行壓縮，通過壓縮將冗余的航跡點(diǎn)去除，根據(jù)不同比例尺下的閾值設(shè)定從AIS航跡點(diǎn)中提取關(guān)鍵的轉(zhuǎn)向點(diǎn)。AIS航跡點(diǎn)是真實(shí)航行情況的客觀反應(yīng)，在航線設(shè)計(jì)和實(shí)際航行中已經(jīng)包含了氣象、水文、安全、經(jīng)濟(jì)等各方面因素，根據(jù)兩點(diǎn)之間直線最短的原理，從實(shí)際航線中提取關(guān)鍵轉(zhuǎn)向點(diǎn)生成新航線的方法提高了經(jīng)濟(jì)效益。由于在壓縮航跡的過程中將曲線變直線可能穿過障礙物或危險(xiǎn)物，因此，初次提取航跡點(diǎn)生成的航線需要充分利用電子海圖信息對生成的航線進(jìn)行點(diǎn)、線、面的海圖要素檢測確保航海安全。

1 AIS信息的提取

隨著AIS(船舶自動識別系統(tǒng)，Automatic Identification System)應(yīng)用技術(shù)的發(fā)展，船載AIS和AIS基站也迅速增多。由于AIS受外界的干擾較小，現(xiàn)在已廣泛應(yīng)用在船舶通信、船岸通信、海上搜救和海事調(diào)查等方面。

1.1 數(shù)據(jù)格式轉(zhuǎn)換

根據(jù)IEC61162-1國際標(biāo)準(zhǔn)規(guī)定，AIS只能傳輸可打印的AIS字符，字符的有效范圍是0X20到0X7E之間，在這個范圍內(nèi)又將字符分為保留字符、有效字符和未定義字符[6]。保留字符是指傳輸語句中用于控制語句格式的關(guān)鍵字；有效字符是指除保留字符外所有可用于打印的ASCII字符；未定義字符不允許直接傳輸使用。AIS的每一條記錄由起始符(“﹩”或“!”)開始，以語句結(jié)束符()結(jié)束，基本的語句格式如表1。

表1 AIS記錄規(guī)范Table 1 Format of AIS records

經(jīng)過封裝后的AIS數(shù)據(jù)經(jīng)過高級鏈接HDLC(High-Level Data Link Control)后進(jìn)行不歸零倒置NRZI(Non Return to Zero Inverted)編碼，再進(jìn)行GMSK(Gaussian Filtered Minimum Shift Keying)調(diào)制，插入同步和停止位后通過VHF頻率傳輸[7]。因此首要工作是根據(jù)IEC61162-1標(biāo)準(zhǔn)和ITU 1371-1協(xié)議將AIS暗碼轉(zhuǎn)換為明碼。

1.2 AIS信息的數(shù)據(jù)清洗

AIS信息包括靜態(tài)信息、動態(tài)信息和與航次有關(guān)的信息。動態(tài)信息的數(shù)據(jù)量一般比較龐大，而且并不是所有的信息都是可為我們所用。因此在AIS信息入庫前需要按照數(shù)據(jù)清洗的原則對AIS信息進(jìn)行預(yù)處理，包括：

1)不完整的數(shù)據(jù)，刪除AIS記錄中不完整的數(shù)據(jù)，例如MMSI為0的記錄。

2)錯誤的數(shù)據(jù)，例如在時(shí)間連續(xù)的記錄中出現(xiàn)經(jīng)緯度變化較大的點(diǎn)，我們稱之為異常點(diǎn)，應(yīng)采用濾波的方法予以剔除。

3)重復(fù)的數(shù)據(jù)，例如船舶錨泊時(shí)AIS的記錄表現(xiàn)為連續(xù)的時(shí)間記錄經(jīng)緯度幾乎不變，為減小數(shù)據(jù)的重復(fù)，應(yīng)只保留一條錨泊記錄。

1.3 數(shù)據(jù)庫的建立

SQLite數(shù)據(jù)庫是一款遵守ACID的關(guān)聯(lián)式輕型數(shù)據(jù)庫，它的設(shè)計(jì)目標(biāo)是嵌入式的，處理速度比Mysql、PostgreSQL這兩款開源世界著名的數(shù)據(jù)庫管理系統(tǒng)快。具有開源、輕便、零配置、處理速度快等諸多優(yōu)點(diǎn)。為了便于嵌入ECDIS系統(tǒng)顯示，解析后的AIS數(shù)據(jù)采用SQLite數(shù)據(jù)庫存儲。

AIS記錄包含了豐富的船舶位置信息。每條記錄都包含了每條船舶唯一的海上移動通信業(yè)務(wù)標(biāo)識碼MMSI(Maritime Mobile Service Identify)，為了便于區(qū)分不同船舶的AIS航跡，以MMSI作為一個字段。由于Douglas-Pecker算法針對按時(shí)間排序后的航跡點(diǎn)進(jìn)行壓縮，因此選取經(jīng)度，緯度，時(shí)間，作為數(shù)據(jù)庫表的另外3個字段。同時(shí)為了便于航海人員根據(jù)船型、船長選擇與本船特征類似的航跡作為參考，將船型、A、B、C、D作為數(shù)據(jù)庫表的另外5個字段，數(shù)據(jù)庫如圖1。這樣，航行人員便可以以起始點(diǎn)、船型、船寬、船長、季節(jié)為條件選擇和本航次計(jì)劃參數(shù)相似的航跡作為參考。

圖1 AIS數(shù)據(jù)庫Fig.1 AIS database

2 AIS航跡點(diǎn)的壓縮

2.1 大地坐標(biāo)系到墨卡托投影變換

AIS記錄中的經(jīng)緯度都是以地理坐標(biāo)點(diǎn)的形式存儲的，這樣可以保證地理位置上的絕對唯一。電子海圖數(shù)據(jù)的顯示過程是把地理坐標(biāo)值換成某一基準(zhǔn)緯度的墨卡托坐標(biāo)值，然后再由墨卡托坐標(biāo)轉(zhuǎn)化為屏幕坐標(biāo)進(jìn)行顯示。在對AIS數(shù)據(jù)處理之前應(yīng)先把每條記錄中的經(jīng)緯度坐標(biāo)轉(zhuǎn)變?yōu)槟ㄍ凶鴺?biāo)。

地心大地坐標(biāo)系的原點(diǎn)為地球質(zhì)心O，3個基準(zhǔn)面分別是賭球橢球面、橢球赤道面和起始大地子午面，在該坐標(biāo)系中，某點(diǎn)P的經(jīng)度λ為P點(diǎn)子午圈平面與起始子午面構(gòu)成的二面角，緯度φ為過P點(diǎn)的橢球法線與赤道面的夾角。根據(jù)等角正圓柱投影的原理，墨卡托正投影的公式為：

(1)

式中：(x,y)為P點(diǎn)的墨卡托坐標(biāo)；r0為基準(zhǔn)緯度緯圈半徑；q為等量緯度，即：

(2)

(3)

式中：a為地球橢球長軸半徑；e為橢球第一偏心率；φ為基準(zhǔn)緯度。

2.2 Douglas-Peuker算法

一個線狀物體總是由其上的采樣點(diǎn)描述的，采樣點(diǎn)越密集，則描述原始物體的能力越強(qiáng)，但隨之而來的是數(shù)據(jù)量的急劇增大，對數(shù)據(jù)管理和分析都帶來極大的困難。例如，將寧波港2011年1個月的AIS數(shù)據(jù)導(dǎo)入到ECDIS平臺，在進(jìn)行海圖平移和放大縮小時(shí)系統(tǒng)處理速度明顯變慢，若將寧波港1年的AIS數(shù)據(jù)導(dǎo)入得到ECDIS系統(tǒng)，在進(jìn)行海圖的平移和放大縮小等操作時(shí)，系統(tǒng)等待時(shí)間多達(dá)30 s。因此Douglas-Peuker算法的核心思想是用盡可能少的點(diǎn)描述原始事務(wù)，并保證在容許的誤差限之內(nèi)再現(xiàn)原始形態(tài)特征。

Douglas-Peuker算法是對垂距限值算法的改進(jìn)，是一種常用的線要素綜合方法和曲邊形逼近算法，具體的實(shí)現(xiàn)過程如圖2。

圖2 Douglas-Peuker算法提取特征點(diǎn)Fig.2 Extracted feature points of using Douglas-Peuker

1) 設(shè)離散的點(diǎn)分別為P1(x1，y1)，P2(x2，y2)，…，Pn(xn,yn)，設(shè)A=P1(x1，y1)，B=Pn(xn,yn)，用線段連接AB。

2) 在AB線段范圍內(nèi)尋找到AB最大距離的點(diǎn)，記為C。

3) 判斷C點(diǎn)到AB的距離是否小于設(shè)定的閾值，若小于閾值，則用AB代替AB之間的所有點(diǎn)，循環(huán)結(jié)束，否則用線段連接AC和CB。

4) 同樣按照步驟(2)所述分別尋找在AC和CB之間到線段AC和CB之間最大距離的點(diǎn)，假設(shè)為圖2中的D點(diǎn)，判斷D點(diǎn)到線段AC的距離是否小于閾值，若是，則用線段ACD代替原始點(diǎn)，否則用線段連接AD、DC、CB，繼續(xù)循環(huán)。

2.3 AIS數(shù)據(jù)壓縮

將Douglas-Peuker算法映射到航海領(lǐng)域，線狀物等價(jià)于要生成的航線，每條AIS記錄中的經(jīng)緯度位置等價(jià)于采樣點(diǎn)，則航線自動生成方法的內(nèi)涵就是在密集的AIS信息采樣點(diǎn)中提取出能描述原始航跡的數(shù)量最少的點(diǎn)即關(guān)鍵的轉(zhuǎn)向點(diǎn)，將提取出的點(diǎn)連接成線稱為航線。

在存儲AIS航跡的SQLite的數(shù)據(jù)庫中根據(jù)設(shè)定的條件選擇和本船自然條件相類似的歷史航跡，例如“select * from Track where MMSI = 412 454 940”，將數(shù)據(jù)庫Track表中MMSI為412 454 940的船的AIS船位采集點(diǎn)提取出來，將經(jīng)緯度轉(zhuǎn)換為墨卡托坐標(biāo)后變?yōu)椴蓸狱c(diǎn)，用Douglas-Peuker算法對采樣點(diǎn)進(jìn)行壓縮，通過設(shè)定合適的閾值即可得到壓縮后的少量的點(diǎn)，稱之為轉(zhuǎn)向點(diǎn)。將這些轉(zhuǎn)向點(diǎn)連接成線即可得到初步生成的航線，完整的實(shí)現(xiàn)流程如圖3。

圖3 航線生成流程Fig.3 Workflow of automatic routing

原始的AIS航跡由于已經(jīng)避開危險(xiǎn)物，因此是安全可靠的。在經(jīng)過Douglas-Peuker算法壓縮之后由于將曲線變?yōu)榱酥本€，生成的直線即初次生成的航線有可能跨越危險(xiǎn)物，為了確保安全需要充分利用電子海圖對初次生成的航線進(jìn)行航線檢測，檢測的內(nèi)容包括航線是否穿越孤立危險(xiǎn)物、暗礁等點(diǎn)物標(biāo)，海底電纜、輸油管道等線物標(biāo)，陸地、禁航區(qū)等面物標(biāo)。若檢測為安全則初次航線為最終的自動生成的推薦航線，若不安全則需要修正航線。如圖4，假設(shè)初次生成的航線為ABCD，在初次航線中檢測出的危險(xiǎn)物標(biāo)為E，則以E為圓心，以2 n mile為半徑做圓，選擇壓縮后離危險(xiǎn)物兩邊最近的關(guān)鍵點(diǎn)即B點(diǎn)、C點(diǎn)對圓做切線得到切線BH和切線CG，將切線的交點(diǎn)F定義為新的關(guān)鍵轉(zhuǎn)向點(diǎn)。將新的關(guān)鍵轉(zhuǎn)向點(diǎn)連接成直線生成新的航線ABFCD并對新的航線進(jìn)行航線檢測直至安全。

圖4 航線修正示例Fig.4 Example of route correction

2.4 閾值的參數(shù)優(yōu)化

在Douglas-Peuker算法中通過衡量點(diǎn)到直線的距離是否大于閾值來決定點(diǎn)的取舍，通過2.2節(jié)中描述的步驟可知當(dāng)閾值等于0時(shí)數(shù)據(jù)壓縮比最小，壓縮后的直線和原直線相同，當(dāng)閾值等于∞時(shí)壓縮比最大，壓縮后的曲線只保留起點(diǎn)和終點(diǎn)，曲線內(nèi)點(diǎn)全部被剔除。

根據(jù)大量實(shí)驗(yàn)操作的結(jié)果，當(dāng)比例尺為1∶800 000時(shí)將閾值設(shè)為2 000壓縮的效果最理想，當(dāng)海圖的比例尺變大時(shí)，閾值可適當(dāng)變小，當(dāng)海圖的比例尺變小時(shí)，閾值可適當(dāng)變大。

3 算法實(shí)現(xiàn)與實(shí)例分析

以ECIDS為顯示平臺，將算法應(yīng)用到實(shí)際中去。由于AIS數(shù)據(jù)限制，僅以瓊州海峽VTS中心收集的2006年9月和10月的全部數(shù)據(jù)為例，如圖5。

圖5 航線參數(shù)設(shè)置Fig.5 Route setting

首先設(shè)置航路的起始點(diǎn)經(jīng)緯度，船舶的船長、船寬和船型參數(shù)，以及航行的季節(jié)。算法將自動在SQLite數(shù)據(jù)庫中搜索與設(shè)置參數(shù)相符合或相近的AIS航跡。檢索后符合要求的航跡將在列表中一一列出，航線人員可在搜索結(jié)果中進(jìn)一步挑選，選中后點(diǎn)擊“原始航跡顯示”可將該船的歷史航跡回放，點(diǎn)擊“壓縮航跡顯示”可將該船的歷史航跡進(jìn)行Douglas-Peucker和航線檢測并最終生成關(guān)鍵的轉(zhuǎn)向點(diǎn)，點(diǎn)擊“導(dǎo)出關(guān)鍵轉(zhuǎn)向點(diǎn)”可將轉(zhuǎn)向點(diǎn)導(dǎo)出。以MMSI編號為412454***的歷史航跡為例，將該船舶的AIS數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗后入庫，共計(jì)得到3 352對有效坐標(biāo)點(diǎn)，點(diǎn)擊“原始航跡顯示”將歷史航跡顯示在ECDIS，如圖6。

圖6 船舶的AIS歷史航跡Fig.6 AIS track of ship

將閾值上限設(shè)為2 000，下線設(shè)置為800，點(diǎn)擊“壓縮航跡顯示”,后進(jìn)行Douglas-Peuker和航線檢測運(yùn)算，經(jīng)過運(yùn)算后得到7對轉(zhuǎn)向點(diǎn)，壓縮率高達(dá)99.79%，大大節(jié)省了AIS數(shù)據(jù)庫的空間。點(diǎn)擊“導(dǎo)出關(guān)鍵轉(zhuǎn)向點(diǎn)”將這7對轉(zhuǎn)向點(diǎn)導(dǎo)出。顯示在ECDIS上，如圖7。

圖7 從AIS航跡中提取的航路Fig.7 Route extracted from AIS track

4 結(jié) 語

通過對照AIS歷史航跡在電子海圖上的顯示和壓縮后的數(shù)據(jù)在電子海圖上的顯示，雖然壓縮率高達(dá)99.79%，但壓縮后的數(shù)據(jù)仍能夠真實(shí)而完整的顯示原始的形態(tài)?；贏IS航跡的航線自動生成算法由于數(shù)據(jù)來源于真實(shí)的船舶航跡，船舶在經(jīng)過特殊的地理位置時(shí)會查閱相應(yīng)的航海圖書資料和氣象水文資料等幫助船舶駕駛員設(shè)計(jì)航線，而船舶的歷史軌跡能夠?yàn)榇榜{駛員提供重要參考。經(jīng)過實(shí)例證明筆者提出的基于AIS航跡的船舶自動生成算法是切實(shí)有效的，但筆者只針對1條船的AIS航跡進(jìn)行了Douglas-Peuker運(yùn)算從而提取出轉(zhuǎn)向點(diǎn)生成航線，在選擇AIS航跡時(shí)為了更加適合本船特性，需要進(jìn)行人工干預(yù)，找出和本船船長、船型、季節(jié)等特性

和本船相似的AIS航跡。下一步的工作將提取多條AIS航跡進(jìn)行Douglas-Peuker運(yùn)算并采用模糊聚類的方法將多條航跡匯合形成推薦的航跡帶，這樣，在船舶設(shè)定好季節(jié)和船舶參數(shù)后，自動生成算法將在航跡帶中找出最佳適合船舶的航跡作為推薦航線。

[1] 郭禹.航海學(xué)[M].大連:大連海事大學(xué)出版社,2005.

Guo Yu.Marine Navigation[M].Dalian:Dalian Maritime University Press,2005.

[2] 夏雷,姜漢新,汪柱.電子海圖最優(yōu)航線自動生成算法的改進(jìn)[J].海洋測繪,2012,32(2):43-45.

Xia Lei,Jiang Hanxin,Wang Zhu.The improvement of automatic routing algorithm based on electronic chart[J].Hydrographic Surveying and Charting,2012,32(2):43-45.

[3] 李源惠,潘明陽,吳嫻.基于動態(tài)網(wǎng)格模型的航線自動生成算法[J].交通運(yùn)輸工程學(xué)報(bào),2007,7(3):34-39.

Li Yuanhui,Pan Mingyang,Wu Xian.Automatic creating algorithm of route based on dynamic grid model[J].Journal of Traffic and Transportation Engineering,2007,7(3):34-39.

[4] 何立居,李啟華.基于蟻群算法的航線自動生成研究[J].中國航海,2009,32(3):71-75.

He Liju,Li Qihua,Automatic generation of ship route based on ant colony algorithm[J].Navigation of China,2009,32(3):71-75.

[5] 汪柱,李樹軍,張立華,等.基于航路二叉樹的航線自動生成方法[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版,2010,35(4):407-410.

Wang Zhu,Li Shujun,Zhang Lihua,et al.A method for automatic routing based on route binary tree[J].Journal of Wuhan University:Geomatics and Information Science,2010,35(4):407-410.

[6] International Electrotechnical Commission.Maritime navigation and radio communication equipment and systems Digital interfaces [EB/OL].(2006-3-20) [2013-10-10].http://www.iec.ch/.

[7] 初秀民,徐海潮,萬劍,等.基于多線程的船載自動識別系統(tǒng)報(bào)文解析 [J].中國航海,2011(2):20-23.

Chu Xiumin,Xu Haichao,Wan Jian,et al.Parsing shipborne AIS message based on multithreading[J].Navigation of China,2011(2):20-23.

[8] 張樹凱.基于S63標(biāo)準(zhǔn)的電子海圖數(shù)據(jù)保護(hù)方案研究[D].大連:大連海事大學(xué),2013.

Zhang Shukai.Research of ENC Data Protection Scheme Based on S63[D].Dalian:Dalian Maritime University,2013.