TSEA:極地科考在線系統中海量走航數據的剔除算法

黃冬梅 韋躐晟 王振華 何盛琪 蘇 誠 黃雅馨

1(上海海洋大學信息學院 上海 201306)2(國家海洋局東海分局信息中心 上海 200136)

TSEA:極地科考在線系統中海量走航數據的剔除算法

黃冬梅1韋躐晟1王振華1何盛琪1蘇 誠2黃雅馨2

1(上海海洋大學信息學院 上海 201306)2(國家海洋局東海分局信息中心 上海 200136)

在對環境極端惡劣的兩極區域進行科考的過程中，科考船狀態的實時監控及反饋是推動極地科考事業的重要保障。在極地科考過程中，由于走航數據采集頻率高，監測手段多樣化，催生了具有多源、多類、多態等特性的海量數據，因此如何實時在線快速展示極地科考走航數據是21世紀海洋事業面臨的巨大挑戰。針對極地監控業務化平臺中的快速可視化關鍵問題，提出了TSEA(Time-Space elimination algorithm)數據剔除算法，通過對數據進行冗余剔除及壓縮等操作，使得在對數據進行快速展示時更加快速與高效。TSEA算法在極地科考在線系統中提供了技術支撐，已投入使用于第31次南極科學考察，并得到了相關單位的一致好評。

極地科考 快速可視化 曲線抽稀 TSEA剔除

0 引 言

極地地區自然環境的變化影響著全球的經濟建設和環境變遷，南北極的科學考察成為國際關注熱點[1-3]。目前，我國已進行了6次北極科考和31次南極科考。在科考過程中，極端惡劣的自然環境給科考人員造成了巨大的困難與未知的危險，如進行南極科考需穿越西風帶，科考船受浮冰影響容易導致滯留等狀況[4-6]。因此，對南北極科學考察船的實時狀況進行動態監控對我國的極地科考事業具有重要的意義，如當考察船遇到突發情況時，救援工作人員可直觀、快速地根據考察船的實時展示信息，做出正確的救援決策和部署，提高救援效率，降低科考人員的危險系數。

信息技術的快速發展，尤其是云計算、物聯網、信息獲取技術、促進了極地觀測事業的快速發展。在極地海洋領域，各個國家已經開展了諸多觀測計劃，包括Argo、海王星、OOI、GOOS、IOOS等多個觀測計劃[7-11]并發射了多顆海洋觀測衛星[12-13]，多種不同數據獲取技術同時對極地進行采集，導致海洋數據量急劇增加。同時，極地數據蘊含著巨大的價值，為人類更深入地感知、認識和控制物理世界提供了前所未有的豐富信息。對其日常監控需要保障系統的實時響應能力以及數據的快速可視化效率，以輔助其做出快速準確決策，并為社會認知極地科考提供了便捷的途徑。

隨著“空、天、地、底”海洋立體監測網的建立，海洋觀測數據呈現多源、異構、多模態、數據量大且動態增長等特征[14-15]。而目前，計算機軟、硬件的發展滯后于人們對大數據存儲、管理以及分析應用的迫切需求， “大數據，小知識”現象日益加劇。在極地科考在線系統中，海量的時空數據從存儲、讀取、數據空間計算以及展示等方面對系統提出了挑戰。

基于上述背景，本文面向多源、高維、海量、實時、多類的極地走航數據，針對航跡數據展示時存在的速度慢、過程不流暢等問題，提出了一種數據剔除算法TSEA。該算法從時間維和空間維進行剔除與壓縮，通過篩選特征拐點和控制空間點位數據的時間差，對數據進行壓縮和提出，通過選取空間特征點和時間節點保證了篩選數據的精度，簡化了數據存儲與計算量，提高了系統執行效率。

1 相關工作

為了能夠合理地使用大數據，減小從數據到知識的運轉周期，大數據的“小數據化”成為很多學者的關注熱點。“小數據化”的主旨就是對數據進行抽稀[16-18]，達到對大數據壓縮的目的；其原則是在壓縮過程中既要提高數據的壓縮效率，也要保證數據的精度。文獻[19]利用道格拉斯-普克法對木材邊緣的曲線進行抽稀，充分減少邊緣要素點的數量，又能將特征點保留下來；文獻[20]使用分區距離度量計算方法對高分辨率 PCB 裸板圖像輪廓進行了抽析，改進了距離度量計算的DP曲線抽稀方法并提高了數據抽稀效率；文獻[21]基于道格拉斯-普克法算法提出了一種“多點逐段進行抽稀”的算法對地形圖上的等高線進行數據抽稀，從而提高抽稀效率；文獻[22]通過合理地使用堆棧結構，給出一種簡單可靠、非遞歸的實現方式的DP算法，并對CAD圖形曲線進行抽稀處理，較于遞歸實現的方法效率得到較大的提升；文獻[23]使用垂矩限值法對道路橫斷面地面線進行抽稀處理，并選取合適的閾值，極大地減少了曲線數據的冗余；文獻[24]采用基于矢量曲線的道格拉斯-普克法與垂距限值法分別對多波束測深數據進行抽稀，并分析兩者的性能以及抽稀效果，最終得出垂距限值法性能高于DP算法。同時，也有部分學者對數據的時間序列進行了研究，如文獻[25]提出的GSB-VLMD算法使用小波變換、極值點分解和符號化提取的組合數據壓縮表示方法對SAX壓縮方法進行改進，對海量的時間序列數據進行了效果較好的壓縮；文獻[26]提出一種簡單快速的基于特征點的篩選算法對對氣象參數進行壓縮，降低對閾值的依賴且計算代價小、快速，文獻[27]提出一種區域極值點提取策略對時間序列數據進行約簡和壓縮，且壓縮效果較好、效率高。

上述研究成果從時間或者空間上解決了大數據的數據量巨大的問題，并在小數據化的過程中提升了數據的計算效率。但極地科考數據是一個強時空關聯的數據集，現有方法無法兼顧其空間和時間特性，不能較好地實現其剔除，壓縮。

本文面對多源、異構、多模態、時空性、數據量的極地走航海洋大數據[28-29]，從時間維和空間維出發，提出了TSEA數據剔除壓縮算法。

2 問題描述與定義

本節將對TSEA數據剔除算法中的相關概念進行描述與定義，具體涉及極地走航數據集、極地走航時間序列數據集和極地走航特征數據集。

定義1 極地走航數據集

極地走航數據集定義為R(T,Lon,Lat,D)，其中，T為極地走航數據的時間；Lon，Lat表示極地走航數據的經度和緯度；D=(d1,d2,…,dk)為一個k元組，表示極地走航數據屬性集，如航速、航向、溫度、主機轉數、主機功率、發電機功率等。

定義2 極地走航時間序列數據集

極地走航時間序列數據集為極地走航數據集R的有序子集，定義為RT(T,Lon,Lat,D)，RT?R。其是將數據集R中時間冗余信息大的要素剔除，實現其時間維度上的壓縮。給出時間閾值△t，為了保證連續數據不被全部剔除，RT的計算方法如下：

(1)

其中：ε是任意小；i=2,3,…,n-1，n是極地走航數據集R的元素個數，即n=|R|；j=2,3,…,m-1，m是極地走航數據集RT的元素個數，即m=|RT|，且2≤m≤n。△t為兩個數據點間的最小時間間隔，當兩數據獲取時間間隔低于△t，則認為該兩點存在冗余。

定義3 極地走航特征數據集

極地走航特征數據集為極地走航時間序列數據集RT的子集，定義為RS(T,Lon，Lat，D)，RS?RT，其是將數據集RT中各元素間夾角小于一定值(或近似一條直線上)的要素剔除，實現其空間維的壓縮。

對數據集RT中除起點與終點外的(j≠1,j≠m,2≤j≤m-1)的每個要素均計算夾角βj，即RT中第j個航跡點與其后一個點以及RS中當前點組成的夾角。

利用三角形的特性求得：

極地走航特征數據集RS計算方法如下：

(2)

其中，k=2,3,…,w-1,是極地走航數據集R的元素個數，即w=|RS|；當βi的值大于閾值△α時，則第i個航跡點作為特征點被保留，否則該點與前一個點存在空間冗余，則剔除。RS為一個w元集，且2≤w≤m。

該方法合理區分了采樣序列中的特征拐點與極值點，通過對原始數據集逐步預處理，降低了數據加載及可視化響應時間。

3 TSEA算法

TSEA算法就是將原極地數據分層分階段進行提取及剔除，從時間維和空間維進行壓縮，最終得到極地走航特征數據集，在保證精度的前提下提高極地數據的計算和展示效率。

算法1TSEA算法：

輸入：極地走航數據集R，時間閾值△t，臨界角閾值△α，原始航跡點的個數n；

輸出：極地走航時間序列數據集RT，極地走航特征數據集RS。

Begin

(1) 將R的起始點R1值賦值給RT1；

(2) 遍歷R中的點，當該點不是最后一個點(2≤i≤n-1)時執行步驟(3)；否則(i=n)執行步驟(12)；

(3) 獲取當前點要提取的點Ri；

(4)ε=min(ε,Ri·T)獲取的前一個點；

(5) 獲取RT當前的數據量j；

(6) 計算Ri與RT時第j間個數據的期望值的時間差△T=[R1·T+(j-1)△t]-Ri·T；

(7)If(△T≤ε)

(8)Ri為特征值并賦值給RTi，跳轉到步驟(2)遍歷下一個點；

(9)Else

(10)Ri=Ri-1，跳轉到步驟(2)遍歷下一個點；

(11) 將R的起終點Rn值賦值給RTm；

(12) 將RT的起始點RT1值賦值給RS1，RS1=RT1；

(13) 遍歷極地走航時間序列數據集RT中所有點，當該點不是起點和終點時(2≤j≤m-1)執行步驟(14)；否則(j=m)執行步驟(18)；

(14) 計算夾角βj；

(15)If(βj>△α)

(16)RTj為特征值并賦值給RSj，RSj=RTj跳轉到步驟(2)遍歷下一個點；

(17)Else令RTj=RTj-1，跳轉到步驟(12)繼續遍歷下一個點；

(18) 將RT的最后一個點賦值給RS；RSw=RTm；

(19)ReturnRS；

End

該算法基于余弦特征函數，在篩選大批量冗余采樣數據點的同時，兼顧考慮特征值、極值點、拐點的保留情況，最大程度地提高系統平臺的訪問速度，保障了數據可視化的實時在線需求。

算法分析：在時間復雜度方面，該算法只執行兩次循環，且記錄級為2n，則該算法時間復雜度為O(n)。在空間復雜度方面，用于存放抽樣樣本的R以及結果集RS存儲特征提取結果，同時使用i、j、RT、△T、△t、βj、△α臨時變量，空間復雜度由與n相關的極大空間決定，則該算法空間復雜度為O(n)。

4 實驗結果與分析

本文實驗環境采用真實數據集，通過獲取29次歷史南極科學考察，模擬真實批次實驗數據。所有測試使用的軟硬件環境如下：(1) 硬件環境：Windows環境，Corei7CPU3.6GHz, 8GBRAM內存，1TB硬盤；(2) 數據庫系統：MySQL數據庫系統；(3) 編程環境：Node.js，JavaScript。

以第29次南極科學考察部分航跡為例，本文分別將時間閾值分別設置為90、180、360; 空間角度閾值△α分別設置為170、165、160，對TSEA進行了實驗。

以時間閾值△α=360和空間閾值△α=160為例，圖1為某部分科考航跡的原始數據。圖2為從時間維壓縮后的航跡線路圖；圖3為從空間維進一步壓縮后的航跡線路圖；圖4是原始數據、時間維壓縮和空間維壓縮后的航跡線路圖。

圖1 原始數據航跡線路展示圖

圖2 時間維剔除后航跡線路展示圖

圖3 TSEA剔除后航跡線路展示圖

圖4 各級數據航跡線路展示圖

由圖1-圖4可以看出：(1) 原始數據具有較高的精度，但其存在大量的數據冗余，給后期的展示以及數據分析帶來了巨大的挑戰，如圖1所示；(2) 從時間維角度壓縮后的數據，在較大程度上剔除了數據的冗余，如圖2所示；(3) 從時間和空間維壓縮后的數據，對原始數據進行的大幅度的壓縮，提高了后期的分析及展示效率，如圖3所示；(4) 通過對各級數據航跡線路的展示比較，可以看出時間維剔除算法一定程度上實現了數據的壓縮，其很好地保持了航跡線路的軌跡趨勢，而從時間維和空間維剔除算法較好地完成了數據的壓縮，維持了航跡線路的總體趨勢，忽略了個別小拐點的趨勢信息，如圖4所示。

圖5和圖6分別給出了原始數據、時間維壓縮后數據、以及時間維和空間維壓縮后數據的量與響應時間比較。

圖5 各級剔除壓縮后數據量對比圖

圖6 各級剔除壓縮后數據展示時間對比圖

由圖5和圖6可以看出：(1) 當時間閾值△t分別為90、180、360時，其數據的壓縮比分別為33.3%、16.6%、8.3%；當加上空間角度閾值△α分別為170°、165°、160°進行剔除時，其數據的壓縮比分別為3.1%、1.8%、0.9%；故此，時間閾值△t與空間角度閾值△α是一個精度和效率之間的平衡，如圖5所示；(2) 但從時間維出發，可對數據進行部分壓縮，但由于極地數據的時空特性，加上空間維的剔除，可對數據的冗余進一步剔除，實現數據的高度壓縮，如圖5所示；(3) 航跡數據的展示所需時間與需加載的數據量成正比，時間維基本實現了10倍展示效率的提高；而時間維和空間維剔除壓縮后，展示效率提高了80到100倍，優勢逐漸凸顯，如圖6所示。

實驗證明，該算法可有效地剔除航跡數據時間冗余信息，并保留航軌跡的特征點部分，在保證航跡線路趨勢精度條件下，降低數據存儲量，提高數據的分析及展示效率，為極地海洋業務化平臺實時監控提供強有力的服務，保證了系統的實時響應及數據的快速可視化。

本文將TSEA算法已應用于真實工程任務中，為系統中航跡線路的再現提供了有利的理論支撐，圖7是我國南極科考第28次以及第30次在澳大利亞附近海域的航行路線圖。

圖7 南極28、30次澳大利亞附近海域航線圖

5 結 語

數據量的不斷增加，給數據的計算、展示以及應用帶了挑戰，目前“大數據，小知識”的現象開始凸顯。如何在保證精度的前提下，快速將獲取的數據轉化為知識，服務于社會是一個亟待解決的問題。本文針對極地海量數據的快速可視化關鍵問題，提出了TSEA算法，該算法從時間維和空間維兩個角度對極地海量數據進行了剔除和壓縮，保證數據提取精度的同時，提高了數據的利用效率，并保障系統的訪問速度。

本文提出了極地走航時間序列和極地特征數據集等相關概念，并給出了TSEA算法的定量計算模型。但是在剔除走航數據判斷時，時間閾值△t和角度閾值△α是一個關鍵問題，閾值的確定關系著整個存儲系統的資源訪問效率及數據剔除精度。未來的工作將對此進行更為深入的研究，并基于Spark云環境制定更適用于極地海洋數據載體的數據快速可視化方案。

[1] 陳立奇.21世紀的極地科學探索——面臨的機遇和挑戰[J].自然雜志,2009,31(2):81-87.

[2] 陳毓峻,高強.極地國際競爭與極地文化關系研究[J].現代經濟信息,2014(22):445.

[3] 鄭英琴.南極話語權芻議[J].國際關系研究,2014(6):64-74,151-152.

[4] 程文芳,張潔,夏明一,等.極地標本資源共享平臺系統設計與實現[J].極地研究,2013,25(2):185-196.

[5] 沈權.從“雪龍”號救援俄羅斯船看極地航行風險及破冰船發展趨勢[J].航海,2014(2):14-18.

[6] 王祥濤,趙強.從第25次南極科考論穿越西風帶航線選擇[J].極地研究,2010,22(2):199-210.

[7]TheInternationalARGOProject[OL].http://www.argo.net/.

[8]OceanNetworksCanada[OL].http://www.neptunecanada.ca/.

[9]OceanObservatoriesInitiative(OOI)[OL].http://oceanobservatories.org/.

[10]TheGlobalOceanObservingSystem(GOOS)[OL].http://www.ioc-goos.org/.

[11]TheUSIntergratedOceanObservingSystem(IOOS)[OL].http://www.ioos.noaa.gov/.

[12]NationalAeronauticsandSpaceAdministration[OL].http://www.nasa.gov/.

[13]NationalOceanicandAtmosphericAdministration[OL].http://www.noaa.gov/.

[14] 孟小峰,慈祥.大數據管理：概念、技術與挑戰[J].計算機研究與發展,2013,50(1):146-169.

[15] 李建中,劉顯敏.大數據的一個重要方面：數據可用性[J].計算機研究與發展,2013,50(6):1147-1162.

[16]DouglasDH,PeuckerTK.Algorithmsforthereductionofthenumberofpointsrequiredtorepresentadigitizedlineoritscaricature[J].TheCanadianCartographer,1973,10(2):112-122.

[17] 劉彥花,葉國華.矢量曲線抽稀算法分析[J].城市勘測,2001(4):49-52.

[18] 米學軍,盛廣銘,張婧,等.GIS中面積偏差控制下的矢量數據壓縮算法[J].地理科學,2012,32(10):1236-1240.

[19] 衛宏,丁建文,曹平祥,等.基于圖像處理的樹干彎曲度自動測量方法[J].林業科技開發,2012,26(6):70-73.

[20] 胡濤,任仙怡,張基宏.高分辨率PCB裸板圖像輪廓快速DP曲線抽稀[J].光電工程,2013,40(7):83-88.

[21] 陳莉,喬小艷,毛建.等高線抽稀算法研究[J].工程地質計算機應用,2009(4):39-42.

[22] 吳銘杰.CAD矢量曲線抽稀的算法和實現[J].測繪與空間地理信息,2010,33(3):207-208.

[23] 李俊,趙娜娜.曲線抽稀算法在剛果(布)國家1號公路數模處理中的應用[J].四川建筑,2012,32(2):209-210.

[24] 秦茂芬,李珂.矢量曲線簡化方法在多波束測深數據中的應用[J].科技創新導報,2011(15):79,81.

[25] 朱躍龍,彭力,李士進,等.水文時間序列模體挖掘[J].水利學報,2012,43(12):1422-1430.

[26] 程敏,翁寧泉,劉慶,等.基于時間序列分段的氣象數據壓縮算法[J].計算機系統應用,2014,23(8):125-129.

[27] 孫雅,李志華.基于區域極值點的時間序列聚類算法[J].計算機工程,2015,41(5):33-37.

[28] 張明華,黃冬梅,熊中敏,等.多源異構海量海洋數據綜合管理平臺構建研究[J].海洋科學,2012,36(2):110-115.

[29] 黃冬梅,季麗偉,袁小華,等.基于時空一體化的海洋大數據快速展示平臺[J].海洋環境科學,2015,34(5):743-748.

TSEA:A DATA ELIMINATION ALGORITHM OF POLAR EXPEDITION ROUTE IN POLAR EXPEDITION ONLINE SYSTEM

Huang Dongmei1Wei Liesheng1Wang Zhenhua1He Shengqi1Su Cheng2Huang Yaxin2

1(SchoolofInformation,ShanghaiOceanUniversity,Shanghai201306,China)2(InformationCenter,EastChinaSeaBranchofStateOceanicAdministration,Shanghai200136,China)

In the process of polar region expedition in extreme environments, the real-time monitoring and feedback of expedition ship is the important safeguard to push the cause of polar expedition. Due to the high frequency collecting and diverse monitoring acquisition，massive data with characteristics like multi-source, multi-class, multi-state emerges， how to display polar expedition route efficiently is a great challenge of the 21st century facing the marine industry. To visualize the data in Polar monitoring business platform, a data culling algorithm of TSEA(Time-Space elimination algorithm) is proposed to exclude redundancy and compress data, which makes it more quickly and efficiently in data display. TSEA algorithm has provided technical support in the polar expedition online systems and has been in operation the 31st Antarctic scientific expedition which made notable results.

Polar expedition Quick visualization Polyline simplification TSEA-algorithm

2015-11-24。國家自然科學基金項目(61272098)；國家重點基礎研究發展計劃項目(2012CB316200)；上海市自然科學基金項目(13ZR1455800)；數字海洋科學技術重點實驗室開放基金項目(KLDO201403)；海洋觀測系統運行狀態監控技術研究與示范項目(201105034)。黃冬梅，教授，主研領域：WebGIS，智能信息處理，輔助決策系統。韋躐晟，碩士生。王振華，博士。何盛琪，講師。蘇誠，工程師。黃雅馨，工程師。

TP3

A

10.3969/j.issn.1000-386x.2017.02.009