基于三角形面積的航跡降采樣算法?

陸 遙 劉雪嬌 魯愛國

（1.武漢數字工程研究所 武漢 430205）（2.91977部隊 北京 100036）

1 引言

隨著現代通訊協議和通訊設備的發展，運動目標的航跡數據監測變得越來越容易。已經有很多研究者探討了如何利用ADS-B 系統采集飛行數據［1］或利用AIS 系統采集船舶數據［2］，如何解讀這些報文信息，如何應用特定規則處理時間戳誤差［3］，如何利用卡爾曼濾波等經典算法清洗異常數據［4］以及如何利用各種聚類算法研究不同目標的航跡之間的關聯性［5］。

本文將關注航跡數據的展示環節。在有限的用戶屏幕空間內顯示過多的航跡歷史點，可能會導致整體圖像看起來非常雜亂，尤其是當被監視的目標沒有固定的運動路線或是采取了大量機動動作時。

包含高密度的數據點分布的折線圖無法向圖表的觀察者提供有效的信息。在部分片段上，多個歷史點跡繪制在過于接近的屏幕位置上，因此很難確定飛行目標的運動狀態和未來趨勢。例如，如果在相對較小的畫布上繪制1000個數據點，如圖1所示，最終會得到這種類型的歷史航跡圖。

圖1 包含1000個歷史點跡的航跡數據（模擬生成）

在將大量航跡歷史點跡可視化為圖像時，如果想要看清整個圖表，則須采取一些必要步驟來避免前面討論的問題。在目標運動模式相對簡單的場景下，可以取一些原始數據點的平均值作為新的數據點來表示原始數據的縮略效果。為了實現這一效果，可以應用例如回歸分析等眾所周知的方法。

然而，本文算法設計的重點在于探索使用原始數據中存在的數據點作為子集的降采樣算法。最簡單的辦法即是根據歷史點跡的數據量和畫布的大小，僅使用每隔十個數據點或可能間隔更多取數據點作為原始數據的代表。不過，這種方法僅適用于原始數據平滑且波動很小的情況。如果原始數據的波動幅度巨大，那么使用上述方法繪制的圖像會損失原始數據中的許多視覺特征，如圖2 所示。顯然，航跡數據展示環節需要一種更合適的降采樣算法，這就是本文的寫作目的。

圖2 對圖1每隔10個歷史點跡保留1個點

圖3 點G距離直線AH最遠

需要強調的是，降采樣后的數據僅用于直觀地表示原始數據的特征以供用戶觀察，而不是用于數據分析、統計或其他任務。在處理視覺表示的信息時，只保留提供最多可被人為感知的特征的數據點很重要，其余的數據點可以丟棄。因此，數據分析領域的算法的一部分評估指標可能不適用于評價降采樣算法。

2 相關工作分析

在對船舶AIS 航跡信息或飛行器ADS-B 航跡信息的數據采集、清洗和處理分析的許多相關文章中，有一部分討論了如何壓縮保存海量的原始數據，這些作者采用了幾種不同的航跡簡化辦法。

2.1 最小描述長度準則

對于已經確定的航跡數據，可以利用特定的編碼模型對其進行數據壓縮。為了正確還原航跡原始數據，需要將壓縮后的數據和所用的編碼模型保存起來。需要保存的數據長度即為原始航跡數據被編碼壓縮后的數據長度和編碼模型的數據長度，其被稱為總描述長度。最小描述長度準則［6］即需要尋找總描述長度最小的編碼模型。

肖瀟［7］把航向和航速變化超過閾值的點篩選為特征點，再提出了最小描述長度準則的開銷計算公式，進一步篩選關鍵點。

2.2 自適應航跡擬合壓縮算法

考慮到運動目標在大多時候處于平穩運動狀態，速度、航向和高度變化很小，因此可以在運動目標的平穩運動階段采用三次函數擬合其軌跡，而保留爬升、下降或變速階段的關鍵航跡點，最終只需要存儲原始航跡中的變化關鍵點和平穩狀態的擬合多項式系數。

梁復臺［8］利用迭代逼近的方法尋找擬合誤差最小的航跡分段方式，將其中速度及高度保持穩定的分段用三次函數擬合，將其余分段的航跡信息保留，即使將一段特定的航跡壓縮至7%，仍可以使壓縮后的航跡與原始航跡擬合誤差小于0.0001。

2.3 Douglas-Peucker算法

Douglas-Peucker 算法［9］是制圖領域中針對折線簡化的經典算法，其先在軌跡折線的首尾兩點之間連接一條直線AH，然后求折線上的其他所有點到直線AH 的距離，找到距離最遠的點G，將距離記為dmax；比較該距離dmax與預先定義的閾值D 大小，如果dmax

張樹凱［10］對瓊海海峽的AIS 數據應用了不同閾值的Douglas-Peucker 算法，將航跡點數量壓縮至原始數據的15%仍可以取得與原始數據類似的顯示效果。

2.4 Visvalingam-Whyatt算法

Visvalingam-Whyatt算法［11］是另一種制圖領域中專門簡化折線的算法。該算法背后的基本思想是根據一個點與前后的兩個相鄰點形成的三角形的面積大小賦予其重要性等級，這通常記作該點的有效面積。根據有效面積去除原始數據中最不重要的點，被去除的點的相鄰點需要重新計算有效面積，然后再次執行該算法直到所有剩余的點的有效面積超過預先設定的閾值。例如，圖4 中F 點的有效面積EFG 比其余都小，優先刪除F 點，此后相鄰點E的有效面積從DEF變為DEG。

圖4 相鄰點組成的三角形EFG面積最小

秦育羅［12］利用Visvalingam-Whyatt算法簡化了海南省的海岸線地圖點跡，在原始數據壓縮至24%時仍可以不丟失原始細節。

3 算法改進設計

現有的航跡降采樣算法可以在保證誤差極小的前提下對靜態存儲的航跡數據做到極高的壓縮效率，但這些現有算法的時間效率都不是太理想，即使是效率最高的Visvalingam-Whyatt算法的時間復雜度也為O（n log（n））。在部分需要實時展示最新航跡數據的場景下，提高降采樣算法的時間效率是非常必要的任務，為此可以犧牲一部分誤差率，只要求降采樣后的航跡圖像保留原始視覺特征即可。本文將在Visvalingam-Whyatt算法的思想基礎上以提升時間效率為目標改進算法作為新的航跡降采樣算法。

3.1 分段并行的Visvalingam-Whyatt算法

這個算法思路非常簡單。首先將原始航跡數據平均分組，例如將1000 個點降采樣為200 個點時，則每組均有5 個點。然后仿照Visvalingam-Whyatt 算法的第一步計算每個點與前后兩點組成的三角形面積大小作為每個點的重要性，對同一個組內的所有點進行重要性排名（需要排除有效面積為空的點）。最后，選擇每個分組內排名最高的點（最大有效區域）來表示降采樣后的數據。

如圖5 所示，點B、點C、點D 被分到同一個分組內，因為B點與相鄰兩點組成的三角形ABC面積比三角形BCD 或三角形CDE 更大，所以降采樣后的數據將選擇B點作為該分組的代表點。

圖5 B點的有效面積在其分組內最大

圖6 對圖1采用算法1降采樣至100個點

算法1 分段并行的Visvalingam-Whyatt算法

輸入參數：原始數據點，降采樣后的點數量m

1：將原始數據點的首尾兩點作為降采樣后的首尾點

2：將剩余的原始數據點平均分為m-2組

3：在每一個分組內：

計算每個點與前后兩點組成的三角形面積

選擇面積最大的點作為該組的代表點

4：將首尾點和每一組的代表點作為降采樣后的數據點

該算法對于航跡點跡的取舍僅僅取決于每個點與前后點組成的三角形面積，因此在保證了時間復雜度為O（n）的前提下，在一定程度上保留原始數據中的“突變”點，而“突變點”是對于航跡圖像觀察者在視覺上最為顯著的特征。

3.2 遠視的Visvalingam-Whyatt改進算法

3.1節中的算法在計算一個點的有效面積時只考慮這個點前后的兩個相鄰點，這在大多數情況下都可以完成降采樣任務，但如果原始航跡數據中存在大量分布不均勻的跳點時，3.1 節中的算法可能存在問題。此時原始數據中某兩個航跡點的時間距離大于其余點之間的時間距離，也即這兩個點之間的物理距離可能遠大于其余點之間的物理距離，這將導致跳點附近航跡點的有效面積遠大于其他點。以往的算法可能會嘗試利用現有數據補全原始航跡數據中的跳點，但為提升算法的時間效率和存儲效率，本文嘗試采用一種更為巧妙的優化辦法。

一個明顯的解決思路是能否讓一個點的有效面積更大，并且在某種意義上讓每一組內選擇的點更具有長期代表性？本節將討論與3.1節類似的算法，但此算法中一個點的有效面積不取決于它的兩個相鄰點的位置，而是取決于上一個和下一個分組中的點，使得該點的有效面積所表示的特征區域大得多也更具有長期代表性。

第一步與算法1 相同，也是將所有數據點平均分成數量相等的分組。同樣地，將原始數據點的起始點和結束點作為降采樣后的起始點和結束點。

下一步是從左到右依次遍歷從第一個到最后一個分組，在每一個分組內選擇一個點，該點應與前一個分組的代表點和后一個分組的代表點組成的三角形面積最大。

計算形成上述的三角形面積時，左側的第一個點始終固定為上一個分組的代表點，中間的點為當前的分組中的一個點，需要通過遍歷求出。問題是從下一個分組中選擇哪一個點來形成三角形。

顯而易見的答案是使用蠻力方法并簡單地嘗試所有可能性。即對于當前分組中的每個點，與下一個分組中的所有點形成一個三角形，顯然這種蠻力做法效率低下，不可能應用于實際生產環境中。例如，如果要將1000個原始數據點降采樣為100個點，則算法共計需要計算大約10000 次三角形的面積。更高效的解決方案是在下一個分組中添加一個虛擬點作為下一個分組的代表。這樣需要計算的三角形的數量只等于原始數據的點數，然后選擇當前分組中與左右兩個固定點形成面積最大的三角形的點。圖7 中顯示了B 點、C 點、D 點被分到同一個分組，其中C 點與固定點A（之前分組選擇的）和虛擬點X 形成的三角形ACX 面積比三角形ABX或三角形ADX更大，所以這一分組內將選擇C點作為代表點。

圖7 C點與A點和虛擬點X組成的三角形在其分組內最大

圖8 對圖1采用算法2降采樣至100個點

圖9 包含1000個點的原始數據圖像（即圖1）

圖10 每隔20個點保留一個點的降采樣結果

圖11 采用算法1降采樣至50個點

圖12 采用算法2降采樣至50個點

下一個分組中的這個虛擬點應該如何決定的問題仍然存在。一個簡單的想法是使用下一個分組中的所有點的平均值。經過實驗在大多數情況下，這與蠻力方法降采樣后的圖像一樣有效，但效率更高。

算法2 遠視的Visvalingam-Whyatt改進算法

輸入參數：原始數據點，降采樣后的點數量m

1：將原始數據點的首尾兩點作為降采樣后的首尾點

2：將剩余的原始數據點平均分為m-2組

3：在每一個分組內：

計算下一個分組的所有點的坐標平均值

計算每個點與前一個分組的代表點和下一個分組的平均點組成的三角形面積

選擇面積最大的點作為該組的代表點

4：將首尾點和每一組的代表點作為降采樣后的數據點

4 極端降采樣比例下的結果對比

上述幾種算法在常規的降采樣任務中得到的最終圖像非常相近，時間復雜度均為O（n），滿足了實時展示航跡數據場景下的降采樣需求。但在極端條件下，即降采樣后的數據點與原始數據點的數量比例下降到一個極小值時，兩者產生的圖像會產生些許不同。

經過實際測試，在包含不規則變化的連續數據集上進行降采樣時，如果用少于原始數量5%的點表示原始圖像時，不管采取何種高效算法或暴力算法，都會大幅度損失其原始數據的變化特征。因此，本文比較了降采樣比例恰好為5%的情況下各算法生成的圖像。

顯然算法2 在降采樣比例低至5%時更能保留原始數據的圖像特征。作為時間復雜度O（n）的算法，算法2 是同等運行時間條件下降采樣效果最好的算法。

5 結語

本論文的主要目標是設計和實現一些可以對航跡數據進行降采樣的高效率的算法，以產生保留數據特征的視覺簡化表示，然后比較這些算法以確定哪些是最實用的。事實證明，算法2 在大多數情況下能夠高效地產生良好的結果。但對包含大量平滑區間的航跡數據采用平均分組的降采樣算法，在極端的降采樣比例下無論如何取舍原始點都會損失大量圖形特征，后續工作將探討根據原始航跡數據的運動特征進行不平均分組的降采樣算法。