定位數據壓縮算法分析論文

導語：定位數據壓縮算法分析論文一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

摘要：為了解決嵌入式GPS車載系統存儲空間小、GPS定位數據量大的矛盾，根據GPS定位數據的特點，提出了專用于GPS定全數據壓縮的改進型半字節壓縮算法。該算法是一種在原半字節壓縮算法的基礎上改進的算法，經過實際測試，壓縮比可達50%。若將壓縮預處理也折算法在內，總壓縮比可達80%以上，為車載系統節省了大量的存儲資源。除此之外，也縮短了GSM信道的占用時間，大大地緩解了向控制調度中心上傳數據的壓力。

關鍵詞：數據壓縮GPS數據格式壓縮預處理半字節壓縮算法

嵌入式GPS車載系統般體積較小，無存儲量大的硬盤等設備，系統程序、應用程序一般裝在FLASH或ROM中。由于FLASH或ROM等存儲介質的價格相對臺式機上廣泛使用的硬盤、光盤等來說是非常昂貴的，因此，在開發嵌入式系統的軟件產品時必須將軟件所占的存儲空間限制在一定的范圍內。

在GPS車載系統的研發過程中，主要需解決的問題是：車載系統為了實現自導航，必須存儲大量的GPS定位數據（每天需要存儲約6MB）；其二是這些數據還要通過GSM信道上傳到控制調度中心（若通過短信業務發送，每次160B，則需要每分上傳6次）。無疑，數據壓縮是在不增加硬件成本的前提下，從軟件的角度來充分發揮系統現有資源的有效辦法。

數據壓縮方法種類繁多，可以分為無損壓縮和有損壓縮兩大類。無損壓縮利用數據的統計冗余進行壓縮。數據統計冗余度的理論限制，般為2：1到5：1。這類方法廣泛用于文本數據、程序和特殊應用場合的圖像數據（如指紋圖像、醫學圖像等）的壓縮。有損壓縮方法利用了人類視覺對圖像中的某些頻率成分不敏感的特性，允許壓縮過程中的損失一定的信息。雖然不能完全恢復原始數據，但是所損失的部分對理解原始圖像的影響較小，卻換來了大得多的壓縮比。有損壓縮廣泛應用于語音、圖像和視頻數據的壓縮。

目前現在的壓縮算法很多，但不能直接用于嵌入式系統當中，這完全由嵌入式系統的特點所決定。首先，用于嵌入式系統的數據壓縮方法應是無損壓縮方法。其次，壓縮代碼和解碼所需的信息代碼必須足夠短，否則就會失去壓縮的意義。還有，嵌入式系統的數據壓縮必須結合具體的數據格式的特點，才能進一步提高數據的壓縮比。除此之外，目前的壓縮程序的啟動執行必須人為干擾，不能自動執行，因為它們是為文件系統設計的，而嵌入式系統的數據壓縮必須能夠自動執行。

1GPS數據格式

GPSOEM板由變頻器、信號通道、微處理器和存儲單元等組成。GPSOEM板的型號甚多，性能各異，但大多采用美國國家海洋電子協會制定的NMEA-0183通信標準格式。本系統選擇的是美國SiRF公司的SiRFstarIIOEM板。SiRFstarIIOEM板語句的輸入、輸出是通過RS232串行接口完成的，其通信端口的數據格式應該設置為8個數據位、1個起始位和1個停止位，校驗方式選為無奇偶校驗，波特率設置為4800波特。NMEA-0183通信標準的輸出數據采用的是ASCII碼，其內容包含了緯度、經度、高度、速度、日期、時間、航向以及衛星狀況等信息，語句有六種，包括GGA，GLL、GSA、GSV、RMC和VTG。對于不同的用途，選用的語句記錄也不同，例如嵌入式GPS車載系統的使用者只關心其日期和時間、糾度、面速度信息，因而可以只選用RMC記錄語句。一條$GPRMC語句包括13個記錄：語句標識頭、世界時間、定位狀態、緯度、緯度方位、經度、經度方位、地面速度、地面路線、日期、磁偏角、校驗和和結束標記，它一共占用70個字節（其中還包括用于分隔記錄所使用的11個逗號），例如：

$GPRMC,121530.998,A,4000.0162,N,11619.5476,E,0.00,240.81,160102,,*3B

由此可見，從SiRFstarIIOEM板接收下來的數據流是文本字符串，根據GPS數據格式的特點，本設計中擬采用半字節法完成壓縮及解壓縮的任務。該方法屬于無損壓縮技術，其原理是去除字節中的冗余位，從而達到壓縮目的。然而，這種方法只適用于純數字文本文件的壓縮，顯然GPS定位數據并不是純數字的，還必須在壓縮前進行一下壓縮預處理，最后再利用半字節壓縮算法完成數據的壓縮。

2壓縮預處理

仔細觀察以上各段數據記錄，可以發現語句之間的數據段還存在很多冗余。除此之外，這些記錄中所含的信息既有英文字符又有數字，為了后續的壓縮，對語句中的各個記錄應做如下的預處理：

①語句標識頭（ID）：因為每個語句的標識頭都一樣，所以該記錄段屬地冗余信息，完全可以去除，在解壓縮時再在每個語句前加上該標識頭即可。

②世界時間（UTC）：該信息段以時、分、秒、毫秒的格式指示出當時世界時間。轉換為北京時間還需要再加上8小時。由于車載系統的定位數據的采集是以秒為單位的，所以毫秒量級的數據對本系統根本無用，是冗余信息，由于世界時間是按秒增1，定位數據也是每委員長更新一次，所以世界時間可以在程序的一開始采集記錄一下，在解壓縮時根據語句的指針值再加上起始時間便可以復原，因此該記錄段在第一次存儲后，以后的語句中的該信息全都是冗余信息。

③定位狀態（A/V）：占用1個字節，不進行預處理。由于車載系統處于的地方有可能收不到衛星信號（如隧道中），致使定位信息無效，因此盡管該字段發生變化的概率較小，又與其它信息段不相關，在此仍不能做預處理。

④緯度：占用9個字節，不進行預處理。

⑤緯度：占用10個字節，不進行預處理。

⑥經度指示器（E/W）：占一個字節，它指示出經度是東經，還是匹配。由于各個$GPRMC語句中的該段信息在中國都是東徑，它是冗余信息，因此也采取程序一開始存儲一次的方法。

⑦緯度指示器（N/S）：占一個字節，各個$GPRMC語句中的該段信息完全一樣，是冗余信息，處理方法與上相同。

⑧地面速度：占用4個字節，不進行預處理。

⑨日期：占用6個字節，以日、月、年的格式顯示，各個$GPRMC語句中的該段信息在24小時內完全一樣，是冗余信息，采取程序一開始存儲一次的方法，以后語句中的該段信息全部廢除。

⑩校驗和：占用3個字節，該數據完成校驗后便棄之，不保留和進行壓縮。

結束符合占用2個字節，只用來判斷語句的有效數據范圍，其它記錄段與本系統的設計無關都不保留和進行壓縮。

通過以上壓縮預處理后，保留了四個數據記錄，共占用24個字節，如圖1所示。

3改進型半字節壓縮算法

文本數據的壓縮的都是無損壓縮技術，即還原后的文件應該與源文件完全相同。文本文件壓縮的方法有很多種，如HUFFMAN編碼、算術編碼和字節壓縮方法等。它們均是無損壓縮方法，都適用于文本數據的壓縮。半字節壓縮方法是針對文本數據的特點所設計的，主要是去除文本中的字節中的冗余位，從而達到減少數據文件所占用的存儲空間的目的。在數據壓縮技術中，除壓縮重復字符外，還可以根據數據本身的特點進行壓縮。在計算機中，任何數據都是以某種代碼的方式存儲的。在些文件中，或許有一些代碼具有某些相似之處，我們可以根據代碼的特點進行特定的操作，壓縮掉這些數據的相似部分，或者說壓縮掉這些數據的特征部分，半字節壓縮就是這樣一種方法。半字節方法主要用于純數字的文本文件的壓縮，因為數字0～9的ASCII碼的高四位都一樣，是冗余的，因此每一個數字完全可以用低四位描述，即每個字節的八位編碼可壓縮為四位編碼，壓縮比理論上可趨近50%。

從圖1中可以看出，經過預處理后的數據中，包含的文本字節有：“0～9”十個數字符號，“A”、“V”兩個英文大寫字母和一個小數點“.”符號，共13個字符。“A”、“V”、“.”的ASCII碼的高四位顯然與數字字節的不一樣，半字節壓縮方法不能簡單套用。然而，我們知道四位二進制編碼可區分16種狀態，用來表示13種不同的字符是足夠的。

壓縮數據編碼表如表1的慰，為了充分利用編碼表中的狀態，在原來13個字節的基礎上又新增添了兩個字符“B”和“W”，其四位編碼分別為1101和1110。這兩個字符是在壓縮預處理過程中，用來記錄那些因語句校驗和出錯而舍棄的語句。因為每條語句的時間信息全部在預處理階段被舍棄，在解壓縮時要恢復時間值。該值在正常情況下是根據時間的基數再加上語句的計數值（由于每秒接受到一條語句，所以語句計數值就是以秒為單位的時間增量）確定的。當發生語句校驗和出錯時，若處于定位有效狀態，則在定位狀態記錄上不填寫“A”字符，而填寫“B”字符；若處在定位無效狀態，則不填寫“V”字符，而填寫“W”字節。在以后解壓縮時，若檢測到“A”、“V”字節，時間的還原按正常的算法進行；若檢測到“B”、“W”字符時，進行的還原除了按正常的算法進行以外還要加上秒鐘，這樣才能確保時間能夠正確的恢復，這是因為“B”、"W"字節表示上一條語句發生錯誤已經被丟棄，語句的壓縮是非連續的，有繼句現象發生。

表1壓縮數據編碼表

預處理后所含的字符ASCII碼四位二制編碼備注

1

2

3

4

5

6

7

8

9

.

A

B

V

W00110000

00110001

00110010

00110011

00110100

00110101

00110110

00110111

00111000

00111001

00101110

01000001

01000010

01010110

010101110000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1101

1100

1110

定位有效

定位有效，秒值1

定位無效

定位無效，秒增1

通過此編碼表進行轉換后，原來經過壓縮預處理后的固定24個字節第的文本數據就可以減小一半（壓縮后為固定的12個字節長），壓縮比為50%，若從未經過預處理的文本數據算起，則壓縮比可達到80%。

由圖2可知，實現半字節壓縮算法需要解決兩上問題：首先是壓縮對象的計數；其次是如何把兩個數字的低位合并到一個字節中。后一個問題只要規定好壓縮后的字節中奇數號字符的四位編碼與偶數號字符的四位編碼的存放次序即可，程序的實現非常簡單，在此我們規定編號是奇數的字符放在高四位，編號為偶數的字符的編碼放在低四位。假設壓縮前的數據流中的前四個字節分別為“1、2、3、4”,則壓縮后的數據格式如圖3所示。

半字節壓縮中需要解決的首要問題是壓縮對象的計數問題，解決此問題的方法有兩種：一種是半字節計數器（Half-ByteCounter），另一種是全字節計數器（Full-ByteCounter）。不管那一種方法，它們都要占用字節，再加上壓縮標識也要占用字節，所以要影響數據的壓縮比。改進后的半字節壓縮算法完全解決了此問題，因為GPS定位數據經過壓縮預處理后的數據長度是固定的24個字節長，不是動態可變的，所以不需要解決壓縮對象的計數問題。一般來說，任何一種壓縮算法都需要用壓縮指示字符作壓縮數據的標識，壓縮標識符越短越好，因為過長會影響縮效果。然而，由于GPS定位數據中的所有字符都進行了編碼處理，不存在原樣字符（不進行壓縮的字符，在解壓縮時原樣輸出），因此壓縮標識完全可以省略，可進一步提高數據的壓縮比。壓縮預處理程序框圖和改進后的半字節壓縮算法框圖如圖4所示。

壓縮文件包括解壓縮所需的重要信息，由釋放參數信息和依次壓縮了的定長數據塊組成。釋放參照信息包含有解壓縮所要使用的時間基數信息，它通過語句計數器以及錯誤代碼號可以將時間還原。除此之外，釋放參照信息還包括各個定長數據塊在解壓縮時所需的共同信息，如E/W、N/S、日期，壓縮文件的格式如圖5所示。

嵌入式系統的壓縮是不需要人為干涉、而自動實時完成的，具體的實現方法是通過駐留內存（單任務操作系統中，如DSP）或作為一個后臺任務（在多任務操作系統中，如Windows中）對數據完成實時壓縮或解壓縮。

表2改進型半字節壓縮算法的測試結果

處理

文件大小（B）預處理后改進型半字節壓縮壓縮比

1035k=69×15000

103.5k=69×1500

10.36k=69×150

360KB+23B

36KB+23B

3.6KB+23B180KB+23B

18KB+23B

1.8KB+23B0.8260

0.8259

0.8239

GPS定位數據的壓縮算法經過實際的驗證，壓縮比隨著壓縮數據的減小而略有減少，這是因為參照信息隨著壓縮數據的減小其所占的比例在逐漸增加的原故。但示，該壓縮方法在車載系統中使用不僅能節省存儲空間，而且能減少信道占有時間及提高數據的安全性。由于壓縮程序是針對GPS數據格式編寫的的，因此其壓縮比大但通用性不強。盡管如此，該程序略做修改可移植到其它系統中，因為各個GPS廠家所執行的規范標準都是GPS廠家所執行的規范標準都是NMEA-0183，其數據的輸出格式略有差別。