孟衛(wèi)東，龍美彪

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

(2)選定閾值與數(shù)據(jù)壓縮率沒有直接關(guān)系，導(dǎo)致不能事先確定壓縮點數(shù)；

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

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

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

2 改進的曲線數(shù)據(jù)壓縮算法

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

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

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

式中，Rk為各組頻數(shù)；R為總頻數(shù)；m為 組數(shù).

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

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

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

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

圖1 孤獨指標(biāo)的涵義

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

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

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

(1)指標(biāo)歸一化:

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

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

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

(4)計算各項指標(biāo)的熵權(quán)wj:

式中，0 ≤wj≤1，且；

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

步驟7.依次將 ΔN個數(shù)的最小綜合得分si對應(yīng)的數(shù)據(jù)點Pi從曲線數(shù)據(jù)點集中刪除，算法結(jié)束.

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

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

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

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

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

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

3 實驗分析

3.1 實驗數(shù)據(jù)來源

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

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

3.2 實驗設(shè)計

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

實驗一:由于對比的是數(shù)據(jù)壓縮后曲線的局部形態(tài)特征變化，因此需要對兩種算法應(yīng)用相同的壓縮率.

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

圖2 方案一直方圖頻數(shù)分布

圖3 方案二直方圖頻數(shù)分布

3.3 實驗結(jié)果及分析

3.3.1 實驗一

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

圖4 實驗一兩種算法形態(tài)對比

3.3.2 實驗二

由于試驗方案中各項指標(biāo)的熵權(quán)按表1所示變化，導(dǎo)致各數(shù)據(jù)點的綜合得分發(fā)生變化，進而影響到壓縮數(shù)據(jù)點和位移偏差、面積偏差.壓縮結(jié)果如圖5 至圖6所示，運行時間、壓縮率、位移偏差及面積偏差如表2所示.

表1 各項指標(biāo)的熵權(quán)

圖5 曲線數(shù)據(jù)壓縮率為4%的結(jié)果

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

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

從表2 可以看出:

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

圖6 曲線數(shù)據(jù)壓縮率為12%的結(jié)果

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

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

表2 算法的實驗結(jié)果數(shù)據(jù)比較

4 結(jié)論

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