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

陸 遙 劉雪嬌 魯愛國

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

1 引言

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

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

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

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

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

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

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

圖3 點G距離直線AH最遠

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

2 相關(guān)工作分析

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

2.1 最小描述長度準則

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

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

2.2 自適應(yīng)航跡擬合壓縮算法

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

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

2.3 Douglas-Peucker算法

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

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

2.4 Visvalingam-Whyatt算法

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

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

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

3 算法改進設(shè)計

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

3.1 分段并行的Visvalingam-Whyatt算法

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

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

圖5 B點的有效面積在其分組內(nèi)最大

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

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

輸入?yún)?shù)：原始數(shù)據(jù)點，降采樣后的點數(shù)量m

1：將原始數(shù)據(jù)點的首尾兩點作為降采樣后的首尾點

2：將剩余的原始數(shù)據(jù)點平均分為m-2組

3：在每一個分組內(nèi)：

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

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

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

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

3.2 遠視的Visvalingam-Whyatt改進算法

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

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

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

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

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

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

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

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

圖9 包含1000個點的原始數(shù)據(jù)圖像（即圖1）

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

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

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

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

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

輸入?yún)?shù)：原始數(shù)據(jù)點，降采樣后的點數(shù)量m

1：將原始數(shù)據(jù)點的首尾兩點作為降采樣后的首尾點

2：將剩余的原始數(shù)據(jù)點平均分為m-2組

3：在每一個分組內(nèi)：

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

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

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

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

4 極端降采樣比例下的結(jié)果對比

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

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

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

5 結(jié)語

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