曲線數(shù)據(jù)壓縮方法與實(shí)現(xiàn)

韓金峰 張亞超

【摘要】本文主要討論了曲線矢量數(shù)據(jù)的壓縮算法，分析將其運(yùn)用到等高線或其他曲線矢量數(shù)據(jù)壓縮。在Spliting算法基礎(chǔ)上提出了一種針對(duì)無拓?fù)涫噶繑?shù)據(jù)的快速壓縮算法，并在AUTOCAD中實(shí)現(xiàn)該算法過程。

【關(guān)鍵詞】矢量數(shù)據(jù)，壓縮算法，精確度，等高線

中圖分類號(hào)：U212.33+2曲 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：

一﹑引言

在計(jì)算機(jī)自動(dòng)制圖中應(yīng)用計(jì)算機(jī)處理已得到的數(shù)字化的資料就不能不注重計(jì)算機(jī)的容量和計(jì)算量。因此，就產(chǎn)生了計(jì)算機(jī)自動(dòng)制圖中的曲線壓縮問題。曲線壓縮實(shí)質(zhì)上是信息壓縮問題，從信息論上講曲線矢量數(shù)據(jù)壓縮就是從組成曲線的點(diǎn)序集合A中抽取一個(gè)點(diǎn)序子集。用這個(gè)子集作為一個(gè)新的信息源，在規(guī)定的精度范圍內(nèi)對(duì)該子集從內(nèi)容上盡可能地反映原集合，而于數(shù)量上則盡可能精簡(jiǎn)。

由于各種原因，系統(tǒng)接收的原圖數(shù)據(jù)中，有一些等高線、曲線等線狀要素的坐標(biāo)點(diǎn)非常密集，存在大量冗余點(diǎn)。冗余點(diǎn)不但占用大量存儲(chǔ)空間，使曲線上出現(xiàn)許多不應(yīng)有的微小波動(dòng)，還給對(duì)曲線的編輯帶來困難。這有時(shí)是不必要的，而且常常造成系統(tǒng)處理受限制。因此，需要利用一定的壓縮算法消除冗余點(diǎn)，對(duì)數(shù)據(jù)進(jìn)行簡(jiǎn)化，并且在保證精度的前提下使曲線具有原來的輪廓和關(guān)系，節(jié)約存儲(chǔ)空間。

曲線矢量數(shù)據(jù)壓縮是從組成曲線的點(diǎn)序集合A中抽取一個(gè)點(diǎn)序A'，也就是說A'是A中的一部分，不是新的點(diǎn)。而由曲線擬合的方法也可以得到一個(gè)逼近的曲線，但擬合出來的曲線不一定通過原來曲線的點(diǎn)，為了避免誤差的傳遞還是用上述方法壓縮。

二、曲線壓縮方法討論

對(duì)于封閉曲線它是先確定曲線最左邊或最右邊兩點(diǎn)作為起始端點(diǎn)，而對(duì)于非封閉曲線可選擇兩個(gè)斷點(diǎn)為起始點(diǎn)，如圖1，

圖1

找出兩端點(diǎn)之間的曲線上的離散點(diǎn)與兩端點(diǎn)的連線的最大距離點(diǎn)，如果該距離值大于給定的精度值，則保留該點(diǎn)，如：2′大于精度值則保留2點(diǎn)。如果2′小于精度值，則再用分別得到的相鄰點(diǎn)4作為起始端點(diǎn)重新進(jìn)行判斷以確定下一個(gè)要保留的點(diǎn)。依次反復(fù)進(jìn)行直到兩直線之間曲線上的點(diǎn)到直線的 距離大于精度值為止。最后，作為端點(diǎn)的末點(diǎn)與曲線的 最后一個(gè)端點(diǎn)重合進(jìn)行判斷并保留最后一個(gè)端點(diǎn)。

從以上可知，此法可以很大程度上滿足即能保留曲線原始的點(diǎn)，能體現(xiàn)曲線的精度不受太大的變化。這在地形圖作業(yè)上是一個(gè)很好的壓縮方法。

三、曲線壓縮的原理和步驟

曲線數(shù)據(jù)壓縮方法三部分：

⑴把等高線上的離散點(diǎn)提取出來作為待處理的點(diǎn)；

⑵對(duì)相鄰兩點(diǎn)的距離進(jìn)行比較如果大于距離精度值則保留第二個(gè)點(diǎn)；在滿足前面條件的情況下對(duì)兩個(gè)端點(diǎn)之間的離散點(diǎn)進(jìn)行判斷如果到兩端點(diǎn)的距離大于偏離精確值，則保留該離散點(diǎn)；

⑶對(duì)保留的點(diǎn)進(jìn)行繪圖使它成為與原等高線相近的曲線。

3.1對(duì)曲線的離散點(diǎn)進(jìn)行精度壓縮原理

基本思想是去除偏離曲線距離小于規(guī)定值δ（例如圖0.1mm）的點(diǎn)。假設(shè)（圖1）中1、2、3、4、5、6為待壓縮的曲線上的點(diǎn)。首先保留第一點(diǎn)1，并以1為起點(diǎn)，連接1、3兩點(diǎn)，若點(diǎn)2到連線13的垂距22'大于δ，則保留點(diǎn)2，以點(diǎn)3為起點(diǎn)繼續(xù)計(jì)算。若小于δ，則連接1、4兩點(diǎn)，分別考察2、3兩點(diǎn)到連線14的垂距，若任意一個(gè)垂距超過δ，則去掉點(diǎn)2，以點(diǎn)3為起點(diǎn)繼續(xù)計(jì)算；否則，連接1、5兩點(diǎn)，考察2、3、4各點(diǎn)到連線15的垂距，……，如此進(jìn)行下去，直到點(diǎn)1與點(diǎn)i連線時(shí)，其間至少有一個(gè)點(diǎn)到連線1i的垂距超過δ，則去掉2、3，…，i-2各點(diǎn)，然后以i-1為起點(diǎn)繼續(xù)計(jì)算。重復(fù)上述步驟，直到曲線的終點(diǎn)。用這種方法壓縮曲線時(shí)，在曲線變化平緩的地方，曲線上被壓縮掉的點(diǎn)很多，剩下的點(diǎn)間距較大，繪制曲線時(shí)點(diǎn)之間會(huì)產(chǎn)生多余的擺動(dòng)。為避免這種情況，壓縮過程中可以加入距離條件，即當(dāng)點(diǎn)的間距超過某一閾值Δ時(shí)必須保留一個(gè)點(diǎn)，即使其間各點(diǎn)到連線的垂距均不超限。

3.2在曲線矢量數(shù)據(jù)壓縮過程中的實(shí)現(xiàn)

1對(duì)等高線上的離散點(diǎn)進(jìn)行提取。

建立一個(gè)選擇集把提取出的等高線上離散點(diǎn)存入新定義的數(shù)組中，其實(shí)現(xiàn)程序（見附錄）

3.2.2對(duì)數(shù)據(jù)進(jìn)行壓縮計(jì)算。

該算法實(shí)際上是一個(gè)遞歸的過程，其實(shí)現(xiàn)一直以來也都采用遞歸的方式，本文通過利用堆和棧的數(shù)據(jù)結(jié)構(gòu)，提出了該算法的一種非遞歸實(shí)現(xiàn)方法。在算法的實(shí)現(xiàn)過程中，用一個(gè)數(shù)組D來存放曲線的樣點(diǎn)列P。，P ,…P ，用數(shù)組的位置索引來指示樣點(diǎn)，同時(shí)采用了一個(gè)與之相配合的隊(duì)和一個(gè)棧，記隊(duì)尾元素為n，棧頂元素為b。具體步驟如下：

(1)將曲線起點(diǎn)D[0]和終點(diǎn)D[n]的下標(biāo)分別放入隊(duì)和棧中，此時(shí)，n=0，b=n,。

(2)連接D[n]和D[b]，在D[n]和D[b]之間的點(diǎn)列中尋找與直線D[n]D[b]具有最大距離的點(diǎn)，記為D[c]，若D[n]與D[b]之間沒有中間點(diǎn)，轉(zhuǎn)(4)。若之間有最大距離點(diǎn)，利用兩點(diǎn)之間的距離公式： 判斷D(n)與D(c)的距離是否大于距離精度值，若大于則保留點(diǎn)D(c),若小于則轉(zhuǎn)（4）。

(3)判段D[c]到直線D[n]D[b]之間的距離是否小于閾值，利用點(diǎn)到直線公式判斷。若否，則將D[c]的下標(biāo)c壓入棧中，此時(shí)，棧頂元素為c，即b=c，回到(2)。

(4)判斷b是否等于n,，若否，將棧頂元素壓入隊(duì)中，此時(shí)，b出棧，隊(duì)尾元素為b．，即n=b，回到(2)。

(5)將b壓入隊(duì)中，隊(duì)中的元素即為所提取特征點(diǎn)的下標(biāo)。

(6)以隊(duì)中元素為下標(biāo)，從隊(duì)頭到隊(duì)尾依次取數(shù)，組D中的點(diǎn)，即為所提取的特征點(diǎn)。

(7)將保留的特征點(diǎn)在圖中依次連接起來用不同的顏色顯示作為比較。

具體實(shí)現(xiàn)代碼見附錄。

3.3起始點(diǎn)的處理

從上所述可以看出，用上述方法所確定的曲線壓縮后的保留點(diǎn)與起始點(diǎn)的選擇密切相關(guān)，即不同起始點(diǎn)所得到的壓縮后的保留點(diǎn)不盡相同。因此，起始點(diǎn)的選擇對(duì)獲取最大壓縮比的保留點(diǎn)至關(guān)重要。選擇那些不引起始點(diǎn)變化而變化的曲線壓縮后的保留點(diǎn)為起始點(diǎn)較為合理。對(duì)于非閉合曲線，其兩端點(diǎn)總是壓縮后的保留點(diǎn)。因此對(duì)于非閉合曲線可選擇該曲線的任一端點(diǎn)作為起始點(diǎn)。而在壓縮過程中要不斷的存儲(chǔ)保留點(diǎn)，并把保留點(diǎn)作為起點(diǎn)，而終點(diǎn)則由起點(diǎn)的變化根據(jù)情況來確定。

四﹑實(shí)驗(yàn)結(jié)果和結(jié)論

（2）

根據(jù)上述原理對(duì)一條等高線進(jìn)行曲線矢量數(shù)據(jù)壓縮。如圖（1）為一條等高線的其中一段，有大量的矢量點(diǎn)組成，利用這條等高線進(jìn)行矢量數(shù)據(jù)壓縮實(shí)驗(yàn)，實(shí)驗(yàn)的等高線有418個(gè)矢量點(diǎn)組成。用本文的方法進(jìn)行矢量數(shù)據(jù)壓縮，其結(jié)果如圖（2）所視，壓縮后剩余158個(gè)點(diǎn)，大大壓縮的矢量數(shù)據(jù)。并與原圖比較（如圖2）保留了原本的曲線形態(tài)。為矢量數(shù)據(jù)的存儲(chǔ)節(jié)省了大量的空間，簡(jiǎn)化曲線的計(jì)算量，同時(shí)壓縮后的數(shù)據(jù)能夠保留曲線的原始精度在一定的范圍內(nèi)。

曲線簡(jiǎn)化在自動(dòng)制圖綜合、應(yīng)用模型邊界簡(jiǎn)化等方面有著較廣泛的應(yīng)用，但由于曲線形態(tài)的復(fù)雜性，算法設(shè)計(jì)仍存在一定困難，主要表現(xiàn)在它的過程、指標(biāo)和方法難以數(shù)量化和模型化。本文的研究為此提供了一種思路和途徑，在這些初步工作的基礎(chǔ)上，還可以進(jìn)一步綜合考慮曲線壓縮。從我個(gè)人的實(shí)驗(yàn)了來看壓縮效果很明顯。能夠滿足等高線的矢量數(shù)據(jù)壓縮，但還存在著一些問題，不足之處請(qǐng)指教。

五﹑結(jié)束語

本文介紹了一種常用的矢量曲線數(shù)據(jù)壓縮的算法，該算法在通過距離精度的算法進(jìn)行壓縮的基礎(chǔ)上進(jìn)行偏離精度壓縮，最大限度地保留原曲線的特征點(diǎn)減小誤差，并有效地壓縮了矢量曲線數(shù)據(jù)地壓縮，為系統(tǒng)節(jié)省了空間，同時(shí)為工作減輕了壓力。希望該算法能為CAD的矢量曲線數(shù)據(jù)提供技術(shù)支持和幫助。

參考文獻(xiàn)

（1）龔有亮，付子傲，翟翊 —— 一種實(shí)用的等高線內(nèi)插算法（信息工程大學(xué)牪饣嫜г海河南犞Ｖ藎450052）

（2）翟戰(zhàn)強(qiáng)，管華，王雙亭——一種快速空間矢量數(shù)據(jù)壓縮方法 （北京大學(xué)遙感所，北京10087E52．解放軍信息工程大學(xué)測(cè)繪學(xué)院，鄭州）

（3）易輝偉，江資斌，周翠竹，鄒嶺蝶 ——地形圖矢量化的后處理（中南大學(xué)信息物理學(xué)院，長(zhǎng)沙410083；2．湖南省建筑學(xué)校，湘潭411001）

（4）張帆，鄭立楷，盧擇臨，王成煌——AutoCAD VBA二次開發(fā)教程（北京.清華大學(xué)出版社）

（5）張帆，鄭立楷，王華杰——AutoCAD VBA開發(fā)精彩實(shí)例教程（北京.清華大學(xué)出版社）