一種帶約束限制的三次B樣條曲線矢量數據壓縮算法

馮峰,蔣維

(武漢大學數學與統計學院,湖北武漢 430072)

1 引言

伴隨著定位技術的高速發展和地理空間數據采集能力的不斷增強,地理空間數據的體量正變得越來越大,因此對地理空間數據進行高效率的壓縮,以便后續的儲存和傳輸顯得尤為重要.一般而言,地理空間數據通常可以分為柵格數據和矢量數據兩種數據結構[1].其中,矢量數據因具有拓撲關系容易表達和冗余度較低等優點,占據了地理空間數據的絕大部分.曲線矢量數據壓縮是地理空間數據壓縮中一類很重要也是很常見的子問題,例如:在電子地圖中的道路數據就可以被認為是一類曲線矢量數據,它可以由一連串的采樣于真實道路的坐標點來表示.但是,在大多數情況下,電子地圖中的道路矢量數據信息量需要保證其準確性以描述其位置和相應的拓撲關系,因此往往數據量會很大,勢必會帶來數據的冗余.然而在智能交通,無人駕駛等領域,對高精度導航地圖系統中的道路數據進行高效地檢索、分析、存儲和傳輸是尤為關鍵的.矢量數據壓縮能夠極大地降低道路數據存儲和傳輸的開銷,也會明顯提高相應的數據處理能力,因此針對矢量數據的壓縮算法研究是十分必要的.

針對曲線矢量數據壓縮,傳統的壓縮算法[1–3]包括:垂距限值法,角度限值法,Douglas-Peucker算法[4],Li-OpenShaw簡化算法[5],預測壓縮算法[6],小波法[7,8]等.其中,最經典的算法是Douglas-Peucker算法,該算法可以看作一種從整體到局部的曲線矢量數據壓縮后保留點集數據的方法.Douglas-Peucker算法可以遞歸式的通過編程實現,并可以達到O(nlogn)的時間復雜度,其基本思路為:分別找到每段曲線中距離曲線首尾端點連線最大的中間點,比較該最大距離與預先給定的誤差閾值,如果最大距離小于給定閾值則將該直線作為這段曲線的近似,否則以此作為新的端點將該段曲線分為兩段,并對每段曲線重復上述過程,直到所有曲線段處理完畢.Douglas-Peucker算法簡單并且易于實現,但是該方法卻也存在一些問題,例如選擇不同的首尾點執行算法會得到不同的壓縮結果,壓縮后的的曲線(即折線)在節點處沒有光滑性.另外,最主要的不足在于該算法沒有考慮曲線矢量數據的拓撲關系,如果沒有進行必要的預處理的話,壓縮結果可能會改變原始數據的拓撲結構.

矢量數據的壓縮本質上是由于原始數據信息存在一定的冗余,因此要對數據進行壓縮和結構的化簡.矢量數據壓縮的核心在于在不擾亂數據拓撲關系的前提下,找到一個盡可能少的數據集合能夠在一定的精度范圍內反映原始數據.準確地來講,我們將矢量數據用一系列有序矢量點集[9]表示,

矢量數據壓縮的目標則是從該點集P中抽取或構造一個具有代表性的子集

用來表示該矢量數據,并且需要在保證拓撲結構等關系不改變的情況下在數據量上有盡可能小的壓縮比.我們將壓縮比定義如下,

其中,|P|為原始矢量數據量的大小,|P0|為壓縮后的數據量大小.通常,壓縮后的數據是指從原始矢量數據提取出的一個子集合,這是因為大部分壓縮算法是基于分析原始矢量數據并保留一部分點集.但是,壓縮數據的作用是能夠代表原始矢量數據,因此壓縮數據可以為任意點集,只要其經由某種方式重構后能夠盡可能的近似原始矢量數據.

為了克服傳統Douglas-Peucker算法無法保證壓縮后的曲線具有整體光滑性的缺陷,本文采用三次B樣條曲線擬合方法來構造相應的數據壓縮算法.B樣條是一類特殊的樣條函數,它可以描述為一組分段多項式基函數的線性組合,其良好的局部性和光滑性使得基于B樣條的擬合技術廣泛應用于計算機輔助幾何設計(CAD)[10,11,13],信號處理[14,15]和圖像處理[16]等領域.一般來說,由于B樣條具有良好的性質,B樣條曲線僅需較少的參數就可以精確的表示非常復雜的形狀,因此利用B樣條對矢量數據進行擬合可以僅使用較少的參數滿足較高的誤差精度要求.本文將利用B樣條擬合技術對曲線矢量數據進行壓縮,同時滿足壓縮數據過程中對首尾端點的約束要求.

2 B樣條曲線簡介

B樣條曲線是一組分段多項式基函數的線性組合,而這些基函數確定了曲線的連續性.具體來說,一條平面上的B樣條曲線X:→2,i.e.,ρ 7→X(ρ)可以表示為[10]

其中系數Pi=(xi,yi)T∈2,i=0,1,...,n,是該B樣條曲線的第i個控制點,Ni,k(ρ)∈[ρ]為定義在實數域上的第i個k次B樣條基函數.

B樣條基函數有許多等價定義,而Cox-de Boor遞歸公式是應用最為廣泛的一種標準方法.Cox-de Boor遞歸公式將一個高次B樣條基函數表示為一些較低次B樣條基函數的線性組合,即對于所有正整數k>0來說,Ni,k(ρ)為兩個(k?1)次B樣條基函數的線性組合.我們將第i個k次B樣條基函數的Cox-de Boor遞歸公式定義為:

其中i=0,1,2,...,n,k≥1,并且我們規定0/0為0.特別地,我們有

其中U={ρ0,···,ρm}被稱為節點向量,ρi稱為節點,節點個數必須滿足m=n+k+1.U是一個非遞減序列,即ρi≤ρi+1,i=0,...,m?1.圖1-3分別展示了次數為1,2和3次的B樣條基函數,并同時給出構成其函數的兩個較低次的B樣條基函數.例如,在圖3中,三次B樣條基函數Ni,3由兩個較低次B樣條基函數Ni,2和Ni+1,2線性組合而成.

圖1：一次B樣條基函數

圖2：二次B樣條基函數

圖3：三次B樣條基函數

從遞推式可以看出,B樣條基函數有許多有用的性質,我們將一些常用且重要的性質[10–13]羅列如下:

?非負性和局部支撐性:對于任意正整數k≥0,Ni,k(ρ)為定義在節點向量上的一個非負多項式,并且我們有:當ρ/∈[ρi,ρi+k+1]時,Ni,k(ρ)=0.

?連續可微性:對于任意正整數k≥1,B樣條基函數在重復度為r的節點處是k?r次可微的,即Ni,k(ρ)∈Ck?r(R);而在節點內部,基函數Ni,k(ρ)是無限次可微的,即Ni,k(ρ)∈C∞(U).

?線性無關性:一組 B 樣條基函數{Ni,k(ρ),Ni+1,k(ρ),...,Ni+k,k(ρ)}在區間 [ρi,ρi+k+1]是線性無關的.

利用B樣條基函數的連續可微性,B樣條曲線X(ρ)的r次微分可以通過B樣條基函數的r次微分直接計算得到,即

大部分矢量數據是采樣于具有連續性的曲線,例如電子地圖中的道路數據主要由一系列的線段,圓弧和緩和曲線等圖形要素組成,并且它們的連接處具有一定的光滑性(一般而言,它們所代表的圖形要素組合需要滿足直到二階的可微性).對于這類矢量數據,數據壓縮算法不僅要保證在壓縮率盡可能小(即壓縮后的點盡可能少)的情況下能夠盡可能好地保證其誤差精度要求,還需要滿足其隱含的光滑性要求.在本文中,我們將給出基于帶約束條件的三次B樣條曲線擬合矢量壓縮算法.由于B樣條具有良好的性質,只需較少的參數就可以重構出較為復雜的形狀,因此將B樣條應用于此類矢量數據壓縮可以很好地滿足實際需求.

3 三次B樣條曲線擬合

此時,當采用上述準均勻分布的節點向量,并使用積累弦長法對數據點進行參數化時,上述極小化問題(3.1)便可以轉化為求解未知控制點的線性最小二乘問題[10,13].應用標準的最小二乘技術,在給定控制點個數n的前提下,上述極小化問題(3.1)可以轉化為關于下列矩陣跡的極小問題:

其中,tr(·)表示求矩陣的跡,N為(K+1)×(n+1)型矩陣,即

Q=[Q0,Q1,...,QK]T為(K+1)×2型二維數據向量集,P=[P0,P1,...,Pn]T為(n+1)×2型未知控制點二維向量集.對極小化問題(3.4)中的目標函數求關于控制點向量P的偏導數,并將其置為0向量,可以得到一個以控制點向量為未知量的線性代數方程組:

并且,由Schoenberg-Whitney定理[10]可推知,NTN是非奇異的.于是,當利用積累弦長法對數據點進行參數化,并采用準均勻分布的節點向量構造相應的三次B樣條基函數時,在給定三次B樣條控制點數目條件下,數據點的三次B樣條曲線擬合所得到的結果是唯一的:

這也就意味著對于任意曲線矢量數據來說,在給定控制點數目前提下,應用三次B樣條擬合技術對其進行曲線擬合可以得到唯一的控制點序列.

4 一種帶約束的三次B樣條曲線矢量數據壓縮算法

在上一節我們考慮了將曲線矢量數據作為一個整體應用最小二乘三次B樣條擬合技術進行數據擬合.然而,在實際應用情況下,對于大部分曲線矢量數據壓縮來說,其首尾端點需要滿足必要的約束條件.本節中,我們將基于一種帶約束的三次B樣條曲線擬合算法,提出一種新的帶約束三次B樣條擬合壓縮算法.

與上一節相同,我們同樣采用準均勻分布的節點向量,并使用積累弦長法對數據點進行參數化.利用式(2.4),我們可以得出如下等式:

結合約束條件(3.3),該問題可以轉化為帶等式約束的二次規劃問題[10],寫成向量形式為:

其中,N為(K+1)×(n+1)矩陣,Q=[Q0,Q1,...,QK]T為(K+1)×2二維數據向量,P=[P0,P1,...,Pn]T為(n+1)×2未知控制點向量,而M和T分別為等式約束線性方程組的4×(n+1)系數矩陣和4×2維系數向量:

利用Lagrange乘子法,令A=[λij]為4×2維Lagrange乘子向量,則帶等式約束的二次規劃問題(4.3)可以轉化為如下最小化問題:

分別對A和P求導并將結果取成0向量,得極小解滿足:

由此可以得到分塊矩陣形式如下

同樣由Schoenberg-Whitney定理[10]可推知,當采用本文所述的準均勻分布的節點向量,并使用積累弦長法對數據點進行參數化時,NTN是非奇異的,又由于M矩陣是行滿秩的,于是M?NTN￠?1MT也是非奇異的.因此,在給定三次B樣條控制點數目條件下,對數據點的帶約束的三次B樣條曲線擬合是唯一的.圖4給出了利用帶約束條件限制的三次B樣條擬合示例,其中控制點數目分別選為8和16,給定邊界條件X(0)=Q0,X(1)=QK,X00(0)=0,X00(1)=0.

圖4：帶約束條件限制的三次B樣條曲線擬合,左圖:8個控制點;右圖:16個控制點.

基于上述帶約束的三次B樣條曲線擬合方法,我們很容易提出一種新的三次B樣條曲線矢量數據壓縮算法.該算法主要步驟如下:

(2)給定誤差閾值ε,選取三次B樣條初始控制點數目n(這里的n值初始選取不應過大)求解帶等式約束的二次規劃問題,由式(4.9)得到相應的控制點序列,其中三次B樣條的節點向量設定為準均勻分布.

(3)計算所有數據點到擬合的三次樣條曲線的誤差,如果數據點到樣條曲線的最大誤差小于給定誤差閾值ε:

則將該控制點序列作為該矢量數據的壓縮結果;否則逐漸增大控制點數量,重復第(2)步.

在實際計算中,上述算法可以與二分法結合,從而快速地找到既滿足誤差精度要求,同時又使得控制點(即壓縮存儲點)的數量盡可能少的最優存儲曲線.我們將結合二分法的三次B樣條曲線矢量數據壓縮算法詳細步驟在下列算法1中給出.

算法1結合二分法的帶約束三次B樣條曲線矢量數據壓縮算法輸入:曲線矢量數據{Qk}Kk=0,誤差閾值ε;輸出:矢量數據的壓縮結果,即三次B樣條控制點序列{Pi}ni=0;1:利用積累弦長法(3.2)將曲線矢量數據參數化{(Qk,ρk)}Kk=0;2:選取兩個合適的正整數nlow和nhigh作為候選三次B樣條控制點數目的最小允許值和最大允許值.其中由nlow計算得到的誤差大于給定誤差閾值ε,而由nhigh計算得到的誤差小于給定誤差閾值ε;3:while nlow

5 數值結果比較

為了測試本文所提出的帶約束條件限制三次B樣條曲線矢量數據壓縮算法,同時與傳統的Douglas-Peucker算法[4]進行對比,本節給出相應的數值算例并比較其數據壓縮率結果.我們將三次B樣條曲線矢量數據壓縮算法的壓縮率定義為

而Douglas-Peucker算法的壓縮率定義為

圖5展示了9種不同的曲線矢量數據,它們都是從隨機選取的連續曲線中等距采樣得到的含有1000個點的矢量數據集.

圖5：一些曲線矢量數據的例子

下面分別利用本文所提出的三次B樣條曲線矢量數據壓縮算法和Douglas-Peucker算法對這些曲線矢量數據進行壓縮,表1和表2分別給出了在不同誤差閾值ε下利用Douglas-Peucker算法和本文提出的算法對這些曲線矢量數據進行壓縮的壓縮率結果.從表1和表2中可以看出,對于圖5中的9種不同的曲線矢量數據,在三種給定的誤差閾值下,本文所提出的三次B樣條曲線矢量數據壓縮算法對曲線矢量數據進行壓縮的壓縮率結果均明顯優于經典的Douglas-Peucker算法.

表1.Douglas-Peucker算法的壓縮率αdp數值結果

表2.基于三次樣條壓縮算法的壓縮率αbsp的數值結果

6 結論

基于三次B樣條良好的局部性和光滑性,本文將三次B樣條應用于曲線矢量數據壓縮.通過給定矢量數據端點邊界條件限制,矢量數據壓縮的問題首先被轉化為一類帶約束條件的三次B樣條最小二乘曲線擬合問題,進而通過求解帶等式約束的二次規劃問題得到三次B樣條曲線控制點作為壓縮結果.由數值實驗結果可以看出,本文所提出的三次B樣條矢量數據算法,相對于傳統的Douglas-Peucker矢量數據壓縮算法,在給定相同的誤差閾值條件下,能夠明顯的降低矢量數據壓縮的壓縮率.同時,由于繼承了B樣條曲線的性質,由本算法壓縮后的曲線還整體地滿足C2連續性.除此之外,本文所提出的算法由于額外增加了端點邊界條件的限制,更能夠體現出原始矢量數據的特征.需要強調的是,本文所提出的三次B樣條壓縮算法可以很容易地推廣到多維(例如三維矢量數據)情況,并且由于B樣條良好的局部性,針對大數據量的情況,三次B樣條壓縮算法也可以利用并行計算來顯著提高算法的效率.