陸 遙 劉雪嬌 魯愛國

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

1 引言

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

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

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

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

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

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

圖2 對(duì)圖1每隔10個(gè)歷史點(diǎn)跡保留1個(gè)點(diǎn)

圖3 點(diǎn)G距離直線AH最遠(yuǎn)

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

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

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

2.1 最小描述長(zhǎng)度準(zhǔn)則

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

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

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

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

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

2.3 Douglas-Peucker算法

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

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

2.4 Visvalingam-Whyatt算法

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

圖4 相鄰點(diǎn)組成的三角形EFG面積最小

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

3 算法改進(jìn)設(shè)計(jì)

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

3.1 分段并行的Visvalingam-Whyatt算法

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

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

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

圖6 對(duì)圖1采用算法1降采樣至100個(gè)點(diǎn)

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

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

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

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

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

計(jì)算每個(gè)點(diǎn)與前后兩點(diǎn)組成的三角形面積

選擇面積最大的點(diǎn)作為該組的代表點(diǎn)

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

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

3.2 遠(yuǎn)視的Visvalingam-Whyatt改進(jìn)算法

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

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

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

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

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

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

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

圖8 對(duì)圖1采用算法2降采樣至100個(gè)點(diǎn)

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

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

圖11 采用算法1降采樣至50個(gè)點(diǎn)

圖12 采用算法2降采樣至50個(gè)點(diǎn)

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

算法2 遠(yuǎn)視的Visvalingam-Whyatt改進(jìn)算法

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

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

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

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

計(jì)算下一個(gè)分組的所有點(diǎn)的坐標(biāo)平均值

計(jì)算每個(gè)點(diǎn)與前一個(gè)分組的代表點(diǎn)和下一個(gè)分組的平均點(diǎn)組成的三角形面積

選擇面積最大的點(diǎn)作為該組的代表點(diǎn)

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

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

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

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

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

5 結(jié)語

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