曲線數據壓縮算法的研究及應用①

孟衛東，龍美彪

(南岳電控(衡陽)工業技術股份有限公司，衡陽 421007)

矢量曲線壓縮，也稱曲線特征點提取，還稱曲線特征點篩選或曲線抽稀，其實質是一個信息壓縮問題，它是從組成曲線的數據集合A中抽取一個子集a，用這個子集作為一個新的信息源，在規定的精度范圍內，該子集能夠從內容上盡可能近似反映原集合A，從數據量上則盡可能大的壓縮[1].數據壓縮的目的主要是刪除冗余數據、減少數據的存儲量、節省存儲空間、加快后繼數據分析和使用速度，數據壓縮的核心就是在不擾亂拓撲關系的前提下，對數據進行合理的加工.曲線壓縮對于計算機圖形學、計算機制圖學等有著非常重要的意義，而在測量系統和控制系統中也需要采集和處理大量的隨機分布的離散數據，這都需要用到數據壓縮，數據壓縮的結果直接影響后續應用研究[2].

目前已經出現多種較成熟曲線壓縮理論，包括間隔取點法、角度限制法、垂距限值法、光欄法、道格拉斯-普克法[3]、最小面積重復刪除法、新興的基于小波技術的曲線壓縮等，由于基于小波技術的壓縮算法可能導致邊界處變形，且壓縮過程復雜，對計算機要求高等缺點，目前應用較少.大家公認的矢量曲線特征點提取的經典算法是道格拉斯-普克法，簡稱D-P 法.目前已有較多研究人員針對道格拉斯-普克法的缺陷進行了改進[4-19]，這些算法各有利弊，并且在不同程度上存在閾值選取不確定、時間復雜度高、壓縮效果不理想、未考慮數據點頻數等問題.

針對上述存在問題，本文提出了一種改進的特征點提取方法，該算法選用數據點到基線的距離，數據點與相鄰數據點間的夾角，考慮數據點的“孤立性”和頻數等屬性作為特征點選取的關鍵因素，利用熵值法確定最終評價值，自動按照給定數據壓縮率進行曲線數據壓縮，并對改進算法進行了實驗驗證.

1 相關工作

在矢量數據中，曲線是由離散的點列組成，曲線數據實際上是一些表示點的數據集合.作為曲線形態的支撐點，數據集的首尾兩點在數據壓縮算法中是必須要保留的.現在最常用的曲線數據壓縮算法是道格拉斯-普克法，該算法的具體步驟是:

步驟1.曲線數據點集合由點序P1,P2,P3,···,Pn組成，設A=P1,B=Pn，用虛線段連接AB；

步驟2.計算AB范圍內的所有內點Pi(i=2,···,m-1)到線段AB的距離di，選取其中距離最大的點Pk，相應距離為dk.

步驟3.判斷dk是否小于設定閾值δ，若否，則點Pk為壓縮后的特征點，設B=Pk，執行步驟2；

步驟4.判斷B是否等于Pn，若否，則將A按原順序放入特征點集合，再設A=Pk,B=Pn，用虛線段連接AB，執行步驟2；

步驟5.將A,B作為特征點放入特征點集合，算法結束.

時間復雜度是衡量算法優劣的主要標準之一.道格拉斯-普克算法第2 步的時間復雜度為O(n)，整個算法是通過遞歸實現的，在一定數據特征下，第3 步和第4 步執行的時間為2T(n/2)，此時整個算法執行的時間2T(n/2)+O(n)，由主定理[20]可得時間復雜度為O(nlogn)；在最壞情況下，第3 步和第4 步執行的時間為T((n-2)+···+1)=T((n-1)(n-2)/2)，則整個算法的時間復雜度為O(n2).

道格拉斯-普克法是一個從整體到局部，即由粗到細的方法來確定曲線壓縮后保留點的過程，其優點是所有特征點都是原曲線上的數據點，可以較好地保持曲線壓縮前后幾何特征的相似性，具有平移、旋轉的不變性，但是道格拉斯-普克法也有自身的局限性:

(1)閾值的選取具有不確定性，如果閾值選取不合理，可能導致一些特征點被誤刪除；

(2)選定閾值與數據壓縮率沒有直接關系，導致不能事先確定壓縮點數；

(3)算法中存在遞歸分段計算，對于復雜的曲線，迭代次數多，計算量大，比較耗費時間；

(4)未考慮頻數等非空間屬性對數據點的影響，可能導致一些特征點被刪除.

目前已有較多研究人員針對道格拉斯-普克法的缺陷進行了相關研究:為了消除迭代、提高算法運行速度，王笑天等[4]提出采用第一特征點法；為了降低壓縮帶來的面積誤差和位置偏差問題，韓曉霞等[5]提出顧及曲線走向及局部面積特征的矢量數據壓縮算法；針對壓縮后曲線保持無自相交屬性的問題，Wu ST 等[6]提出曲線無自相交壓縮的算法；針對海洋權益問題，于靖等[7]提出面向自然岸線抽稀的改進道格拉斯—普克算法；針對閾值優化選取問題，Prasad DK 等[8-13]提出閾值優化選取方法；針對連續彎曲問題，Ai TH 等[14-19]提出對連續彎曲進行壓縮的方法等.以上這些算法更多考慮的是曲線的空間屬性，沒有考慮頻數等非空間屬性；對于閾值優選時，多個屬性之間的協調性不強，導致“綜合”效果較差.

2 改進的曲線數據壓縮算法

對于隨機分布的離散數據點，其點集排序的方法是依次尋找距離最近的下一個新點，因此，得到的點序反映的只是邏輯相鄰關系，這和物理相鄰的程度是有差異的.如果只按邏輯相鄰關系進行點序的成串刪除，有時就會刪去互相遠離的特征點[21，22].在測量系統和控制系統中，采集得到的重復數據點在點集中自動合并成唯一數據點，導致數據壓縮時，該數據點重要度下降；數據點之間的相似程度往往用“距離”來度量，邏輯相鄰的數據點的多少也是特征點選取的關鍵因素，例如連續小角度變化的復雜曲線.因此，特征點確定不僅與單個離散數據點出現頻數有很大關系，還與邏輯相鄰離散數據點間出現頻數有關.

為了防止刪除特征點，不僅要考慮數據點到基線的距離、數據點與相鄰數據點間的夾角，還應結合考慮該數據點的“孤立性”和頻數等非空間屬性來共同決定對它的取舍.改進算法具體步驟如下:

步驟1.根據經驗確定直方圖的極差、組距、組數m和各組界限值；以固定時間間隔 Δu、從連續信號S(u)上采樣得到離散數據點，更新直方圖相應組的頻數Rk(k=1,2,···,m)；計算各組頻率fk:

式中，Rk為各組頻數；R為總頻數；m為 組數.

步驟2.曲線數據點集合由點序P1,P2,P3,···,Pn組成，曲線數據點數為n，內點數為N=n-2.指定需要壓縮的數據點數ΔN(1 ≤ΔN≤N)，則壓縮率σ=ΔN/N.可根據特普費爾公式計算ΔN:

式中，N2為新數據點集的點數；N1為原數據點集的點數；S1為原數據點集的比例尺；S2為新數據點集的比例尺；x為重要度系數，x=0,1,2，分別對應重要，一般和次要；ΔN為要壓縮的數據點數.

步驟3.計算P1,Pn范圍內的所有內點Pi(i=2,···,n-1)的孤獨指標gi:

式中，分子的涵義是當前點Pi到邏輯相鄰的兩個數據點Pi-1,Pi+1的距離之和；分母的涵義是P1,Pn之間所有相鄰數據點間連線的平均長度的兩倍.不難看出，孤獨指標gi是一個在1 左右擺動的正值.

圖1 孤獨指標的涵義

步驟4.計算P1,Pn范圍內的所有內點Pi(i=2,···,n-1)到相鄰兩個數據點Pi-1,Pi+1連線的距離指標di；

步驟5.計算P1,Pn范圍內的所有內點Pi(i=2,···,n-1)到相鄰兩個數據點Pi-1,Pi+1連線的夾角指標θi；

步驟6.熵值法計算P1,Pn范圍內的所有內點Pi(i=2,···,n-1)的綜合得分si:

(1)指標歸一化:

式中，為第i個數據點的第j項指標的歸一化數值(i=2,···,n-1;j=1,···,J)，其中j分布對應距離、孤獨、夾角和頻數等指標；Xij為第i個數據點的第j項指標的數值；

(2)計算第j項指標下第i個數據點占該指標的比重fij:

(3)計算第j項指標的熵值hj:

(4)計算各項指標的熵權wj:

式中，0 ≤wj≤1，且；

(5)計算各數據點的綜合得分si:

步驟7.依次將 ΔN個數的最小綜合得分si對應的數據點Pi從曲線數據點集中刪除，算法結束.

本文算法比較簡單，包含5個單層循環，分別是第3 至7 步，其中前4個循環的時間復雜度均為O(n)，第5個循環的時間復雜度為O(ΔN)，所以算法的時間復雜度為O(n).

本文算法不僅繼承了道格拉斯-普克算法的優點，如所有特征點都是原曲線上的數據點，具有平移、旋轉的不變性等，而且增加了如下優點:

(1)不需要事先設定閾值，算法自動根據加權修正后的綜合得分，以從小到大順序，依次壓縮數據；

(2)直接指定數據壓縮率，保證壓縮算法運行后結果，滿足測量系統和控制系統的帶寬、分辨率和存儲量的要求；

(3)取消迭代運算，對于復雜的曲線，將有效降低計算量，減少運算時間；

(4)特征點的確定，不僅考慮了邏輯相鄰和物理相鄰關系，而且同時考慮了頻數等非空間屬性的影響，降低了誤刪除概率.

3 實驗分析

3.1 實驗數據來源

實驗一:為證明本文算法的有效性和優越性，以我國東北某段國界線1:100 萬的數據為實驗對象，分別采用道格拉斯-普克算法與改進算法對實驗對象進行數據壓縮效果對比實驗，該部分區域的形態比較曲折，能夠很好地檢驗兩種數據壓縮方法的效果.

實驗二:為了驗證頻數對測量系統和控制系統采集結果數據壓縮的影響，本文選取實測高壓共軌柴油機進油計量閥流量特性變化較明顯的區間作為實驗區，進行濾波、融合等預處理后生成等效數據點集(如圖5所示)，作為本算法抽稀實驗的源數據，共計25個數據點.

3.2 實驗設計

矢量曲線數據壓縮算法的優劣，一般通過運行時間、壓縮率、位移偏差和面積偏差來評價.數據壓縮的速度（時間復雜度）主要以運行時間來評價；數據壓縮率（空間復雜度）是壓縮掉的曲線數據點數與原始曲線點數之比；位移偏差是曲線壓縮導致的原始數據點與壓縮后曲線數據點的空間偏移量，通過計算原始曲線上數據點到壓縮后曲線的最短距離的中值或平均值來度量；面積偏差是曲線壓縮帶來的面積偏差，通過計算原始曲線所圍面積與壓縮后曲線所圍面積的差值來度量，該指標反映了壓縮后曲線與原曲線的貼近程度.

實驗一:由于對比的是數據壓縮后曲線的局部形態特征變化，因此需要對兩種算法應用相同的壓縮率.

實驗二:頻數指標采用兩個直方圖頻數分布來進行計算，分別為方案一和方案二，其直方圖頻數分布如圖2 和圖3所示.

圖2 方案一直方圖頻數分布

圖3 方案二直方圖頻數分布

3.3 實驗結果及分析

3.3.1 實驗一

由于道格拉斯-普克算法不能事先確定壓縮率，經過多次優選閾值后確定相同壓縮率.從圖4 可以看到，道格拉斯-普克算法數據壓縮結果雖然能較好地保留曲線特征，但會導致尖銳角的出現，壓縮效果比較生硬，平滑度不夠，而改進算法較好地保持了曲線的整體形態特征，能夠較好地體現出“綜合”的本質.

圖4 實驗一兩種算法形態對比

3.3.2 實驗二

由于試驗方案中各項指標的熵權按表1所示變化，導致各數據點的綜合得分發生變化，進而影響到壓縮數據點和位移偏差、面積偏差.壓縮結果如圖5 至圖6所示，運行時間、壓縮率、位移偏差及面積偏差如表2所示.

表1 各項指標的熵權

圖5 曲線數據壓縮率為4%的結果

圖5中，本文改進算法與道格拉斯-普克算法的壓縮率同為4%，即壓縮點數為1個.道格拉斯-普克算法迭代次數為45 次.道格拉斯-普克算法刪除圖5中序號2 點；方案一刪除圖中序號18 點；方案二刪除圖5中序號15 點.

圖6中，本文改進算法與道格拉斯-普克算法的壓縮率同為12%，即壓縮點數為3個.道格拉斯-普克算法迭代次數為41 次.道格拉斯-普克算法刪除圖6中序號2、17 和18 點；本文改進算法方案一刪除圖6中序號15、18 和21 點.方案二刪除圖6中序號14、15 和24 點.

從表2 可以看出:

(1)運行時間:壓縮率為4%時，本文改進算法運行時間比傳統道格拉斯-普克算法減少了68.33%；壓縮率為12%時，減少了50.13%.由于道格拉斯-普克算法迭代次數分別為45 次和41 次，即使按時間復雜度為O(nlogn)，也遠大于本文改進算法的時間復雜度為O(n)，導致程序運行時間較長.輸入數據量n急劇增加時，傳統道格拉斯-普克算法執行次數的增長次數差異顯著增加[20].

圖6 曲線數據壓縮率為12%的結果

(2)位移偏差、面積偏差:本文改進算法根據數據點多種屬性的相對重要性程度進行壓縮，當考慮數據的非空間屬性，如頻數時，在較好地保持曲線形狀的同時，可能導致位移偏差和面積偏差大于傳統道格拉斯-普克算法.

(3)壓縮率:由于道格拉斯-普克算法最佳閾值選取需要多次試探，Prasad DK 等[8-13]采用曲線擬合等閾值優化選取方法，嚴重影響壓縮計算效率，很難直接給定壓縮率.本文改進算法自動按照給定數據壓縮率進行曲線數據壓縮，容易實現高壓縮率與保真效果之間的平衡.

表2 算法的實驗結果數據比較

4 結論

本文對傳統的曲線壓縮算法進行了簡單的介紹，分析了道格拉斯-普克數據壓縮算法，針對其閾值的選取、數據壓縮率、時間復雜度和特征因素等方面存在的不足，保留道格拉斯-普克算法的優點，如所有特征點都是原曲線上的數據點，具有平移、旋轉的不變性等，提出了一種改進的特征點提取方法，該算法通過直方圖統計數據點的頻數，根據數據點到基線的距離、數據點與相鄰數據點間的夾角，考慮數據點的“孤立性”和頻數，自動按照給定數據壓縮率進行曲線數據壓縮.在MATLAB 上進行了仿真實驗，利用自主研發的控制系統平臺，對進油計量閥流量特性進行增量自學習，并在油泵臺架和發動機臺架上完成了相應的實驗.實驗結果表明，本算法可以有效的對數據進行壓縮處理，滿足測量系統和控制系統的數據壓縮需求.