飛行軌跡數(shù)據(jù)壓縮算法研究及應(yīng)用

引用格式：，.飛行軌跡數(shù)據(jù)壓縮算法研究及應(yīng)用[J].指揮控制與仿真，2025，47（4）：74-79.YANGY，XIAOYJ.Re-searchandapicationofflight tajectorydatacompressionalgoit[J]ommandControlamp;Simulation，O25，474）：74-79.

中圖分類號：TP391 文獻標志碼：A DOI：10.3969/j.issn.1673-3819.2025.04.011

Abstract：The vastamountofflighttrajectorydatabrings hugechalengestothedata storage，data query，anddata visualizationinthesituationaldisplaysystem，anddatacompressontechnolgyisanefetivesolutiontothisproblem.Regarding theproblemsthatthecurrentflighttrajectorycompressionalgoritmsdonoteffectivelyutilizeallflightparameterfeaturesand needtosetthresholds manually，thispaper proposesanefectiveflight trajectorydatacompressonalgorithm.Thealgorithm first performs clustering ontheflight direction parametersand selects trajectory feature points basedonthecategory labels. Then，the algorithmcalculates theinformation entropy todeterminethe scoreofeachtrajectoryfeature point，andcomprees the trajectorydata basedonthecompressionrateand score sorting.The simulationresults showthatcomparedwithother algorithms，theproposedalgorithmhasbettercompressonqualityndcompressionefciencyByapplyingthealgorithmtothe trajectory playback andtrajectoryenvelopevisualization inthesituational displaysystem，thesystemresponsespeedanddisplay efficiency can be significantly improved.

Keywords：flight trajectory；data compression；entropy of information；clustering

隨著全球定位技術(shù)和移動通信的快速發(fā)展，在執(zhí)行飛行任務(wù)時，飛行器能夠?qū)崟r將軌跡數(shù)據(jù)傳輸?shù)街笓]所的態(tài)勢系統(tǒng)中，而較高的采集頻率使得飛行軌跡數(shù)據(jù)呈爆炸式增長，給軌跡數(shù)據(jù)存儲、分析挖掘和可視化帶來了巨大挑戰(zhàn)[1]。據(jù)統(tǒng)計，飛行器飛行時1s會采集4～6個軌跡點，飛行1小時約產(chǎn)生兩萬個軌跡點，而這些軌跡點通常包含大量的冗余數(shù)據(jù)，為降低軌跡數(shù)據(jù)存儲和傳輸壓力，提升軌跡數(shù)據(jù)分析和可視化效果，研究一種有效的飛行軌跡數(shù)據(jù)壓縮算法是十分必要的。

目前，軌跡數(shù)據(jù)壓縮算法有很多，考慮壓縮效率和限制條件等因素，本文側(cè)重于研究線段簡化壓縮算法，該類算法通過比較軌跡點最大誤差與設(shè)定閾值或特定條件的大小來簡化軌跡點[2]。Douglas-Peucker（DP）算法[3]是一種經(jīng)典的線段簡化壓縮算法，該算法從全局軌跡點出發(fā)，使用垂直歐氏距離作為軌跡誤差度量，由于DP算法需要進行遞歸操作，其時間復(fù)雜度為O（N²） 。Meratnia等[4]在DP算法基礎(chǔ)上考慮時間屬性，提出了自頂向下的時間比壓縮算法（TD-TR），雖然有更高的壓縮精度，但時間復(fù)雜度仍為 O（N²） 。后續(xù)，許多學(xué)者對DP算法進行了改進[5]，針對DP算法存在閾值不確定問題，趙永清提出了一種自動閾值的DP算法，張志偉等提出了DP算法閾值選取優(yōu)化方法。近年來，許多學(xué)者嘗試在軌跡壓縮時使用速度、方向等信息來提升壓縮質(zhì)量，Lin等8提出了保留軌跡速度特征的壓縮算法，但在軌跡劃分后仍使用DP進行遞歸；田智慧等[提出了一種同時考慮速度和角度的軌跡簡化算法，增加了累積變向角閾值，有效減少了軌跡關(guān)鍵點的丟失。

由于飛行器飛行的特殊性，采集的軌跡點除了位置信息外，還包含高度、橫滾角、俯仰角、航向角等信息，如表1所示。然而，只有少數(shù)學(xué)者考慮如何有效利用飛行軌跡特征進行數(shù)據(jù)壓縮，鄔鵬等[\"0]針對飛行軌跡特點，提出了一種基于飛行參數(shù)的分段壓縮算法，在每個分段軌跡中，使用DP算法進行軌跡壓縮；雷祥等[1]使用俯仰角和航向角的變化率作為閾值條件，提出了一種限定俯仰角和航向角的改進DP算法。雖然兩種方法考慮了飛行參數(shù)特征，但存在閾值選取不確定、時間復(fù)雜度高等問題。針對上述問題，本文在有效利用飛行參數(shù)的基礎(chǔ)上，選取方向變化率高的點作為軌跡拐點，通過最大限度保留攜帶信息多的拐點，提升軌跡數(shù)據(jù)壓縮質(zhì)量和效率。

1飛行軌跡數(shù)據(jù)壓縮算法

1.1 符號定義

假設(shè) T={tid，fid，P₁，P₂，…，P_i，…P_N} 表示一條飛行軌跡，其中， _tid 表示該軌跡的唯一標識 fid 表示產(chǎn)生該軌跡的飛機型號， P_i 表示軌跡中第 i 個軌跡點，每個軌跡點包含時間、經(jīng)度、緯度、高度、橫滾角、俯仰角、航向角和航速8個參數(shù)，即 Φ_Pi=（t_i，x_i，y_i，h_i，α_i，β_i，θ_i v_i ） N 為原軌跡點數(shù)， T^*={tid，fid，P₁，P₂，…，P_i，… （204P_M} 表示壓縮后的軌跡， M 為壓縮后的軌跡點數(shù)。

表1飛行軌跡點數(shù)據(jù)格式Tab.1Flight trajectory point data format

1.2飛行軌跡數(shù)據(jù)處理

通過對實際飛行軌跡數(shù)據(jù)進行分析，我們發(fā)現(xiàn)軌跡中存在重復(fù)數(shù)據(jù)、異常數(shù)據(jù)和某一屬性值缺失等情況，在數(shù)據(jù)壓縮之前，應(yīng)先對飛行軌跡數(shù)據(jù)進行預(yù)處理。

1.2.1數(shù)據(jù)清洗轉(zhuǎn)換

從態(tài)勢數(shù)據(jù)中獲取的飛行軌跡通常是分批次的，需要人工或通過算法進行批次合并，在這個過程中容易出現(xiàn)重復(fù)數(shù)據(jù)，因此，數(shù)據(jù)清洗首先應(yīng)刪除軌跡中唯一標識、時間相同的軌跡點；其次，在態(tài)勢數(shù)據(jù)解碼的過程中，會出現(xiàn)亂碼或者屬性為空值的問題，需刪除軌跡點中飛機唯一標識、型號、經(jīng)度、緯度等屬性有明顯錯誤的數(shù)據(jù)。

在飛行軌跡壓縮過程中，可能需要計算兩個軌跡點間的距離，而態(tài)勢數(shù)據(jù)中是以經(jīng)緯度來表示飛機的位置，本文采用墨卡托投影方法將其轉(zhuǎn)換到直角坐標系。

1.2.2 異常點檢測

一般情況下，飛機的位置由時間、航速等屬性決定，由于通信設(shè)備異常、信號干擾等因素會導(dǎo)致飛行軌跡中出現(xiàn)跳點，軌跡點位置異常意味著速度異常，因此，跳點檢測可以采用如下公式：

其中， v_i 表示軌跡中第 i 個點的速度， v_max 表示當前環(huán)境下飛機飛行理論上的最大速度。通常，飛機在飛行中高度不會從一個具體數(shù)值突然變?yōu)?，只有在飛機降落時高度值才為0，而在分析飛行軌跡數(shù)據(jù)時，人們發(fā)現(xiàn)存在很多飛行過程中高度為0的軌跡點，本文也將這些認定為異常軌跡點。

1.2.3 數(shù)據(jù)插值修復(fù)

在檢測出軌跡異常點后，最簡單的處理辦法是將這些點刪除。然而，直接刪除異常點可能導(dǎo)致部分軌跡間隔較大且不均勻，不利于后續(xù)的數(shù)據(jù)壓縮操作。因此，本文采用插值技術(shù)對異常點進行修復(fù)。

針對位置異常點，本文采用的是結(jié)合航向和航速的插值方法[12]。該方法通過異常點的前后兩個點分別計算異常點位置的預(yù)測值。然后，通過軌跡點之間的時間屬性計算權(quán)重。最終，采用加權(quán)平均的方式得到異常值的新位置。針對高度異常點，本文利用線性插值方式預(yù)測新的高度屬性值。

1.3飛行軌跡數(shù)據(jù)壓縮算法

很多研究表明保留軌跡方向的壓縮方法優(yōu)于保留軌跡位置的壓縮方法[13]，本文在充分利用軌跡方向特征的前提下，提出了一種有效的飛行軌跡數(shù)據(jù)壓縮算法。

1.3.1 軌跡拐點提取

飛行軌跡的方向參數(shù)包含橫滾角、俯仰角、航向角，為提取具有代表性的方向拐點，本文采用聚類的方法對方向參數(shù)進行類別劃分。成熟的聚類方法有很多，考慮聚類效率，本文采用經(jīng)典的 k -means聚類方法，聚簇數(shù)目 k 值使用肘部法來確定。

為保證飛行軌跡起止位置準確，我們需提前去除軌跡起點和終點。設(shè) ，軌跡點 P_i 的方向特征向量為 （α_i，β_i，θ_i） ，方向特征集 H 可表示為

為避免數(shù)據(jù)數(shù)值域大小給聚類帶來影響，本文對矩陣 H 進行標準化處理，計算公式如下：

其中， 分別為第 j 個分量的標準差和平均值。對方向特征向量 k -means聚類后，每個軌跡點會獲得一個類別標簽。將原始軌跡映射為一個標簽序列。選擇標簽變化處的軌跡點為軌跡拐點，如圖1所示，一條軌跡含有3個不同類別，紅色標記的軌跡點為拐點。

圖1軌跡拐點選取示意圖Fig.1Trajectory inflection point selection diagram

1.3.2 綜合得分計算

由于飛機在飛行過程中方向變化瀕繁，上一節(jié)中得到的軌跡拐點數(shù)量會非常多，人們需要采用計算軌跡拐點的綜合得分來進一步篩選。綜合得分通過軌跡拐點的位置、高度和航速等指標來計算。

首先，定義拐點 P_i 到相鄰軌跡點 P_i-1 和 P_i+1 位置距離、高度差、航速差的計算公式，具體如下：

歸一化處理，具體公式如下：

式中， D_ij^* 為第 i 個拐點的第 j 項指標的歸一化數(shù)值，而i=1，…，p 為拐點的數(shù)量 Δ，j 對應(yīng)位置、高度和航速三個指標， _?Dij 為第 i 個拐點的第 j 項指標值。

接著，計算各指標的熵值 ?h_j

圖2展示了拐點 P_i 位置距離誤差計算示例。

圖2拐點距離誤差計算示例圖 Fig.2Example of calculating distance error of trajectory inflection point

其中， f_ij 為第 χ_i 項指標下第 j 個數(shù)據(jù)點占該指標的比重。

最后，軌跡拐點的綜合得分 σ_?si 為：

其次，為避免各指標間的量綱差異，需對指標進行

其中， w_j 為第 j 個指標的熵值權(quán)重。將各個拐點的綜合得分按照降序排序，選取前 M-2 個拐點，加上軌跡起點、軌跡終點組成壓縮后的軌跡點。算法流程如表2所示。

表2飛行軌跡數(shù)據(jù)壓縮算法Tab.2Flight trajectorydatacompressionalgorithm

本算法的時間復(fù)雜度取決于軌跡拐點提取和綜合得分計算兩個步驟，軌跡拐點提取的時間復(fù)雜度由 k 1means算法決定，為 O（lkN） ，其中，1為迭代次數(shù)， k 為聚簇數(shù)， N 為軌跡點數(shù)；綜合得分計算的時間復(fù)雜度取決于計算軌跡拐點各個指標的循環(huán)操作，均為 O（p） ，其中， p 為軌跡拐點數(shù)，且 p

2 實驗結(jié)果與分析

2.1實驗環(huán)境及數(shù)據(jù)來源

實驗硬件配置為Inteli7-1160G7處理器，16GB內(nèi)存；實驗環(huán)境為Windows10操作系統(tǒng)，算法開發(fā)語言為 Python 3.10。

實驗數(shù)據(jù)來自態(tài)勢系統(tǒng)中飛行器的飛行軌跡，提取一段飛行時間為30分鐘的軌跡作為最終的實驗數(shù)據(jù)，包含7392個軌跡點。實驗對比算法為DP算法和TD-TR 算法。

2.2 性能度量指標

本文選取運行時間、壓縮率、平均距離誤差和平均方向誤差作為度量指標。壓縮率計算公式為

r=（N-M）/N×100%

平均距離誤差和平均方向誤差分別表示壓縮后的軌跡在歐氏距離和方向上的損失，計算公式分別為：

2.3實驗結(jié)果及分析

表3給出了在不同壓縮率下3種算法的運行時間，從表中可以看出，壓縮率為 20% 時，本文算法的運行時間略優(yōu)于其他兩種算法，隨著壓縮率不斷增大，本文算法的優(yōu)勢逐漸顯現(xiàn)，特別是在壓縮率為 80% 時，本文算法的運行時間明顯低于其他兩種算法。主要原因是DP算法和TD-TR算法都是通過遞歸實現(xiàn)的，時間復(fù)雜度為 O（N²） ，而本文算法時間復(fù)雜度為 O（lkN） 。

圖3對3種算法在不同壓縮率下平均距離誤差進行對比，整體來看，3種算法的距離誤差隨著壓縮率的增加而提高，TD-TR算法在距離誤差方面略優(yōu)于DP算法，而使用本文算法進行壓縮產(chǎn)生的距離誤差在不同壓縮率下都低于其他兩種算法，說明本文算法提取的軌跡拐點精度更高，能用相當?shù)能壽E點保留更多的位置信息。

表3在不壓縮率下的算法執(zhí)行時間

Tab.3Algorithmexecution timeindifferentcompression ratio 單位：

圖3不同壓縮率下平均距離誤差對比Fig.3Comparison of mean distance error indifferentcompressionratio

圖4比較了不同壓縮率下3種算法的平均方向誤差，從圖中可以看出：壓縮率低于 40% 時，本文算法的方向誤差較低且變化較??；壓縮率為 30% 時，本文算法的方向誤差為TD-TR算法的 1/3 ;壓縮率高于 70% 時，本文算法與其他兩個算法相比，方向誤差均最小。其主要原因是本文算法在選取軌跡拐點時，充分考慮了飛行方向參數(shù)變化因素，而DP算法和TD-TR算法只是簡單進行了距離計算。

在實驗過程中，DP 算法和TD-TR算法要不斷調(diào)整閾值大小，以確定相應(yīng)壓縮率下的特定閾值，而本文算法只需給出壓縮后的軌跡點數(shù)量，不需要人為設(shè)定閾值，因此在實際應(yīng)用中更靈活、高效。

圖4不同壓縮率下平均方向誤差對比Fig.4 Comparison of mean direction error indifferentcompressionratio

縮質(zhì)量的前提下，有效降低了軌跡點的數(shù)量。在實際應(yīng)用中，可將飛行軌跡包絡(luò)可視化功能的效率平均提升3倍，且原飛行軌跡點越多，提升效果越明顯。

4 結(jié)束語

本文針對飛行軌跡數(shù)據(jù)壓縮算法未有效利用飛行參數(shù)和閾值設(shè)定難等問題，提出了一種有效的飛行軌跡數(shù)據(jù)壓縮算法。算法對每條軌跡的方向特征向量進行聚類，選取方向變化的點作為軌跡拐點，通過引入信息熵理論，按照各個軌跡拐點的綜合得分排序，確定最終壓縮后的軌跡點。實驗結(jié)果表明，算法壓縮后的軌跡點精度更高且運行時間優(yōu)于其他算法。最后，本文將算法應(yīng)用到態(tài)勢展示系統(tǒng)的飛行軌跡回放和軌跡包絡(luò)可視化功能中，應(yīng)用效果顯著。

3 算法應(yīng)用

前期，我們基于GIS服務(wù)實現(xiàn)了目標與態(tài)勢三維可視化系統(tǒng)[14]，在系統(tǒng)使用過程中，隨著飛機飛行次數(shù)和時間的增加，產(chǎn)生的態(tài)勢數(shù)據(jù)越來越多，嚴重影響了飛行軌跡可視化的效果。本文算法對飛行軌跡數(shù)據(jù)進行有效壓縮，在態(tài)勢系統(tǒng)中的應(yīng)用體現(xiàn)在軌跡回放和軌跡包絡(luò)可視化兩個方面。

3.1 軌跡回放

在大型模擬訓(xùn)練后，通常需要基于態(tài)勢回放系統(tǒng)進行復(fù)盤總結(jié)，飛行軌跡回放是將所有軌跡點按照時間順序進行三維可視化，而飛機在飛行過程中會頻繁采集軌跡數(shù)據(jù)，飛行時間超過1小時可達上萬個軌跡點，給態(tài)勢回放帶來了巨大挑戰(zhàn)。在實際應(yīng)用中，如果飛機數(shù)量達到20架以上，態(tài)勢回放功能要加載60s左右，嚴重影響用戶的使用體驗。本文算法通過保留最優(yōu)軌跡拐點的壓縮方式，不僅將飛機航跡壓縮至指定長度，也保留原軌跡的方向、位置等重要特征。使用本文算法后，20架飛機態(tài)勢回放加載時間縮短至15s左右，并且壓縮后的航跡跟原航跡的可視化效果基本一致。

3.2軌跡包絡(luò)可視化

飛機執(zhí)行任務(wù)后，根據(jù)飛行軌跡和雷達探測范圍，利用線緩沖區(qū)生成算法15在態(tài)勢展示系統(tǒng)中生成飛行軌跡包絡(luò)圖，能夠直觀呈現(xiàn)飛機此次任務(wù)的偵察區(qū)域。然而，一次飛行任務(wù)持續(xù)時間長，產(chǎn)生軌跡點數(shù)量巨大，在軌跡展示和包絡(luò)范圍計算時消耗資源多，直接導(dǎo)致了此功能效率變低，時常出現(xiàn)卡頓，嚴重影響了用戶的使用體驗。使用本文算法可在后端服務(wù)將飛行軌跡壓縮到指定軌跡點數(shù)，方便前端服務(wù)調(diào)用，在保證壓

參考文獻：

[1] ZHENG Y. Trajectory data mining：an overview[J].ACMTransactions on Intelligent Systemsand Technology，2015，6（3）：1-41.

[2] 江俊文，王曉玲.軌跡數(shù)據(jù)壓縮綜述[J].華東師范大學(xué)學(xué)報（自然科學(xué)版），2015（5）：61-76.JIANG JW，WANG XL.Review on trajectory datacom-pression［J]. Journal of East China Normal University（Natural Science），2015（5）：61-76.

[3] DOUGLASD H，PEUCKER TK.Algorithms for the re-duction of the number of points required to represent adigitized line or its caricature[J].Cartographica：the In-ternational Journal for Geographic Information and Geovi-sualization，1973，10（2）：112-122.

[4] MERATNIAN，DE BYRA.Spatiotemporal compressiontechniques for moving point objects.Advances in DatabaseTechnology-EDBT2004[C]//Berlin，Heidelberg：SpringerBerlin Heidelberg，2004：765-782.

[5] 王笑天，呂海洋.基于第一特征點的道格拉斯-普克壓縮算法[J].軟件導(dǎo)刊，2016，15（11）：68-70.WANG X T， LYU H Y. Douglas-poker compression algo-rithmbased on the first feature point[J]. Software Guide，2016，15（11）：68-70.

[6] 趙永清.自動設(shè)置閾值的道格拉斯-普克壓縮法[J].山西煤炭管理干部學(xué)院學(xué)報，2013，26（3）：120-122.ZHAO Y Q.Douglas-poker compression method with auto-matic threshold setting[J]. Journal of Shanxi Coal-MiningAdministrators College，2013，26（3）：120-122.

[7] 張志偉，暴景陽，肖付民，等.基于Ping的Douglas-Peucker法抽稀閾值優(yōu)化選取[J].海洋測繪，2015，35（2） ： 9-12.ZHANG Z W， BAO J Y， XIAO F M， et al. Selecting op-timum thinning thresholdvalue of Douglas-peucker algo-rithmbasedon Ping[J] .Hydrographic Surveying andCharting，2015，35（2）：9-12.

[8] LINC Y，HUNG C C，LEI P R.A velocity-preservingtrajectory simplification approach[C]//2O16 ConferenceonTechnologiesand Applications of Artificial Intelligence（TAAI），Hsinchu，2016：58-65.

[9] 田智慧，馬占宇，魏海濤.基于密度核心的出租車載客軌跡聚類算法［J]．計算機工程，2021，47（2）：133-138.TIAN ZH，MA ZY，WEI HT. Taxi passenger trajectoryclustering algorithm based on density core[J].ComputerEngineering，2021，47（2）：133-138.

[10］鄔鵬，彭曉明.DP算法在飛行參數(shù)數(shù)據(jù)壓縮中的應(yīng)用[J].艦船電子工程，2013，33（11）：46-47，64.WUP，PENG X M.Application ofDP algorithm in theflight parameter data compression[J]. Ship Electronic En-gineering，2013，33（11）：46-47，64.

[11］雷祥，張少華，任凌云，等.D-P算法的改進及其在飛行軌跡回放中的應(yīng)用[J].軟件，2012，33（9）：149-150，152.LEIX，ZHANGSH，RENLY，etal.ImprovementofDouglas-Peucker algorithm and itsapplication in flighttrackplayback[J].Software，2012，33（9）：149-150， 152.

[12］王超，紀永剛，黎明，等.一種考慮船舶航速航向的AIS航跡插值方法[J]．艦船科學(xué)技術(shù)，2015，37（4）：60-64.WANGC，JIYG，LIM，etal.AnAIStrackinterpolationmethod considering the vessel’s speed and course[J]. ShipScience and Technology，2015，37（4）：60-64.

[13]LONGC，WONGRC，JAGADISH HV.Direction-pre-serving trajectory simplification[J].Proceedings of theVLDBEndowment，2013，6（10）：949-960.

［14］楊垚，劉永海，肖雅娟，等.目標與態(tài)勢三維可視化系統(tǒng)設(shè)計與實現(xiàn)[J].網(wǎng)絡(luò)安全與數(shù)據(jù)治理，2023，42（12）：90-95.YANGY，LIUYH，XIAOYJ，etal.Designandimple-mentation of the 3D visualization system for target and sit-uation[J].Cyber Security and Data Governance，2023，42（12）：90-95.

[15］董鵬，毛東軍，李軍，等.一種有效的GIS緩沖區(qū)生成算法[J].計算機工程與應(yīng)用，2004，40（16）：4-8，12.DONGP，MAODJ，LIJ，et al.Aneffectivebuffer gen-eration method in GIS[J].Computer Engineering and Ap-plications，2004，40（16）：4-8，12.

（責任編輯：張培培）