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

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

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

0 引 言

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

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

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

1 AIS信息的提取

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

1.1 數據格式轉換

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

表1 AIS記錄規范Table 1 Format of AIS records

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

1.2 AIS信息的數據清洗

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

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

2)錯誤的數據，例如在時間連續的記錄中出現經緯度變化較大的點，我們稱之為異常點，應采用濾波的方法予以剔除。

3)重復的數據，例如船舶錨泊時AIS的記錄表現為連續的時間記錄經緯度幾乎不變，為減小數據的重復，應只保留一條錨泊記錄。

1.3 數據庫的建立

SQLite數據庫是一款遵守ACID的關聯式輕型數據庫，它的設計目標是嵌入式的，處理速度比Mysql、PostgreSQL這兩款開源世界著名的數據庫管理系統快。具有開源、輕便、零配置、處理速度快等諸多優點。為了便于嵌入ECDIS系統顯示，解析后的AIS數據采用SQLite數據庫存儲。

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

圖1 AIS數據庫Fig.1 AIS database

2 AIS航跡點的壓縮

2.1 大地坐標系到墨卡托投影變換

AIS記錄中的經緯度都是以地理坐標點的形式存儲的，這樣可以保證地理位置上的絕對唯一。電子海圖數據的顯示過程是把地理坐標值換成某一基準緯度的墨卡托坐標值，然后再由墨卡托坐標轉化為屏幕坐標進行顯示。在對AIS數據處理之前應先把每條記錄中的經緯度坐標轉變為墨卡托坐標。

地心大地坐標系的原點為地球質心O，3個基準面分別是賭球橢球面、橢球赤道面和起始大地子午面，在該坐標系中，某點P的經度λ為P點子午圈平面與起始子午面構成的二面角，緯度φ為過P點的橢球法線與赤道面的夾角。根據等角正圓柱投影的原理，墨卡托正投影的公式為：

(1)

式中：(x,y)為P點的墨卡托坐標；r0為基準緯度緯圈半徑；q為等量緯度，即：

(2)

(3)

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

2.2 Douglas-Peuker算法

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

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

圖2 Douglas-Peuker算法提取特征點Fig.2 Extracted feature points of using Douglas-Peuker

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

2) 在AB線段范圍內尋找到AB最大距離的點，記為C。

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

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

2.3 AIS數據壓縮

將Douglas-Peuker算法映射到航海領域，線狀物等價于要生成的航線，每條AIS記錄中的經緯度位置等價于采樣點，則航線自動生成方法的內涵就是在密集的AIS信息采樣點中提取出能描述原始航跡的數量最少的點即關鍵的轉向點，將提取出的點連接成線稱為航線。

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

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

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

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

2.4 閾值的參數優化

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

根據大量實驗操作的結果，當比例尺為1∶800 000時將閾值設為2 000壓縮的效果最理想，當海圖的比例尺變大時，閾值可適當變小，當海圖的比例尺變小時，閾值可適當變大。

3 算法實現與實例分析

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

圖5 航線參數設置Fig.5 Route setting

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

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

將閾值上限設為2 000，下線設置為800，點擊“壓縮航跡顯示”,后進行Douglas-Peuker和航線檢測運算，經過運算后得到7對轉向點，壓縮率高達99.79%，大大節省了AIS數據庫的空間。點擊“導出關鍵轉向點”將這7對轉向點導出。顯示在ECDIS上，如圖7。

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

4 結 語

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

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

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

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

[2] 夏雷,姜漢新,汪柱.電子海圖最優航線自動生成算法的改進[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] 李源惠,潘明陽,吳嫻.基于動態網格模型的航線自動生成算法[J].交通運輸工程學報,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].武漢大學學報:信息科學版,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] 初秀民,徐海潮,萬劍,等.基于多線程的船載自動識別系統報文解析 [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標準的電子海圖數據保護方案研究[D].大連:大連海事大學,2013.

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