利用二次B樣條曲線逼近的圖像壓縮方法*

李軍成

(湖南人文科技學院數學系，湖南 婁底 417000)

利用二次B樣條曲線逼近的圖像壓縮方法*

李軍成

(湖南人文科技學院數學系，湖南 婁底 417000)

提出了一種基于Hilbert掃描和二次B樣條曲線逼近的圖像壓縮方法。首先利用Hilbert掃描曲線將二維數字圖像轉化為一維的灰度序列；然后采用二次B樣條曲線對數據進行分段逼近，同時利用逼近的最大絕對誤差小于最大允許誤差來確定最終分段；最后對每段數據的逼近參數進行編碼。實驗結果表明，該方法獲得的壓縮效果較好，且計算量適中，是一種簡單有效的數字圖像壓縮方法。

圖像壓縮；二次B樣條曲線；分段逼近；Hilbert掃描

1 引言

圖像數字化后，其所占的空間通常是很大的，為實現圖像的有效存儲和傳輸，對數字圖像進行壓縮處理顯得尤為重要。數字圖像壓縮，就是通過選用有效的方法，去除或減少圖像中存在的冗余，從而降低圖像的存儲空間要求和傳輸帶寬要求。按照壓縮還原效果是否存在失真，圖像壓縮分為兩類：一類是壓縮后的數據可以完全恢復成原來的圖像，沒有任何信息損失，稱為無損壓縮；另一類是壓縮后的數據只能近似恢復原始圖像，信息有一定的損失，稱為有損壓縮。通常來說，有損壓縮可以獲得更高的壓縮效率。按照實施編碼支持域的不同，圖像壓縮編碼可分為空域法和頻域法[1]。空域法是直接對像素空間進行操作，減少數據在時間和空間上的相關性，以達到壓縮數據的目的，如Huffman編碼、差值脈碼調制DPCM(Differential Pulse Code Modulation)編碼等。而頻域法則是通過正交變換，把分散在原圖像空間的數據在新空間中得到集中，并保留包含圖像主要信息的系數，從而達到壓縮數據的目的，如離散余弦變換DCT(Discrete Cosine Transform)編碼、小波變換編碼等。

在對圖像進行壓縮編碼時，無論是采用空域法還是頻域法，其目的都是為了進一步提高壓縮比和圖像壓縮質量。為此許多學者開始致力于改進傳統的圖像壓縮方法或尋找新的圖像壓縮方法，比如有學者利用空間域提出了基于曲線曲面擬合的圖像編碼方法。文獻[2]討論了利用B樣條曲面擬合的圖像編碼方法，其基本思想是先用B樣條曲面擬合圖像的灰度值曲面，再對B樣條參數進行編碼，以此提高壓縮比和改進恢復后圖像的質量；文獻[3, 4]提出了一種基于Hilbert掃描和分段局部二次Bernstein多項式逼近的圖像壓縮方法，取得了較好的圖像壓縮效果；文獻[5]提出了將三次Bernstein多項式作為逼近函數的圖像壓縮方法；文獻[6]針對交通實時路況圖像，提出了一種多項式擬合的圖像壓縮編碼方法，該方法通過對圖像數據的光柵掃描、單調化處理和多項式擬合系數保存等三個步驟來實現對圖像數據的壓縮；文獻[7]設計了一種基于正交多項式分段擬合的圖像壓縮編碼方法，以探索新的圖像壓縮編碼方法；文獻[8]針對多項式函數在逼近數據時雖能很好地反映數據的漸變性，但不能反映數據的突變性這一不足，提出了一種基于Hilbert掃描和二次有理Bézier曲線逼近進行圖像壓縮的方法。實驗結果表明，該方法比傳統的Bernstein多項式逼近方法在圖像的壓縮比和壓縮質量方面都有所提高。進一步地，文獻[9]又針對二次有理Bézier曲線在逼近曲線時不能表示拐點這一缺陷，提出了一種基于擬三次有理Bézier曲線逼近的圖像壓縮方法。

文獻[4, 5]所給出的二次與三次Bernstein多項式逼近方法實質上可看成是相應的二次與三次Bézier曲線逼近，利用Bézier曲線逼近進行圖像壓縮時，其基本思想是首先將圖像轉化為掃描數據，然后采用分段逼近的方法對圖像進行壓縮編碼。因此，曲線逼近的精度在很大程度上影響著圖像的壓縮比和壓縮質量。

文獻[8, 9]提出的基于有理型Bézier曲線逼近的圖像壓縮方法相對于二次與三次Bézier曲線逼近方法而言，雖然其壓縮比和壓縮質量方面都有所提高，但由于采用的是有理函數進行比較，計算量稍顯偏大。由于Bézier曲線是一種特殊的B樣條曲線，且B樣條曲線比Bézier曲線具有更好的逼近性，因此利用B樣條曲線逼近進行圖像壓縮是一種較好的選擇。

為進一步減小逼近誤差，提高圖像的壓縮質量和減少計算量，本文提出了一種基于二次B樣條曲線逼近的數字圖像壓縮方法。該方法首先利用Hilbert曲線掃描[3, 4]將二維形式的數字圖像轉化為一個一維的灰度數據序列，然后采用分段二次B樣條曲線對數據進行逼近，最后利用逼近參數對圖像進行壓縮編碼，從而達到壓縮圖像的目的。由于彩色圖像可分解成R、G、B三基色圖像，因此下面主要針對灰度圖像進行討論。

2 二次B樣條曲線逼近方法

2.1 二次B樣條曲線

(1)

第二段曲線的表達式可寫為:

(2)

為方便應用，將式(2)重新參數化，使其參數t∈[1,2]，則式(2)可改寫為:

(3)

于是，整條二次B樣條曲線的表達式可寫為:

(4)

由式(3)易知:

(5)

(6)

(7)

式(5)～式(7)表明，整條二次B樣條曲線r(t)(1≤t≤2)通過首、末控制點且滿足C1連續。

由式(4)可得函數型二次B樣條曲線(簡稱為二次B樣條曲線)的表達式可寫為:

(8)

式中控制頂點di∈R1(i=0,1,2,3)。

2.2 逼近方法

由于二次B樣條曲線通過首、末控制點，故可令d0=V0，d3=Vn，即二次B樣條曲線可寫為:

(9)

于是，只需由給定的數據求出控制頂點d1與d2就可實現二次B樣條曲線對數據Vi(i=0,1,2,…,n)的逼近。

(10)

解得:

(11)

綜合灌漿法：鉆機對中調平固定→開孔鉆至第一段→阻塞洗孔、壓水及灌漿→鉆至終孔段→一次性洗孔、壓水→自下而上分段灌漿至第二段→封孔。

(12)

3 圖像壓縮方法

設某灰度圖像的大小為N×N，首先利用Hilbert掃描將二維形式的數字圖像轉化為一維的灰度值序列，并確定一個預分段長度作為分段的基準值，記為L(一般取為N，N/2，N/4)，然后按照每L個數據作為一段將整個圖像的掃描數據預分為若干段[9, 10]。于是，基于Hilbert掃描與二次B樣條曲線逼近的圖像壓縮方法的步驟為：

Step1將原始圖像通過Hilbert曲線掃描轉化為掃描數據。

Step2設置預分段長度L，對圖像的掃描數據進行預分段。設定最大允許逼近誤差M。

Step3用二次B樣條曲線去逼近預分段的一組數據，并計算最大絕對誤差εmax。

Step4如果εmax≤M，則將此段數據組成一個最終分段，轉到Step 5；如果εmax>M，則找出絕對誤差最大的第i個數據，然后把前面的i個數據作為一組預分段數據，轉到Step 3。

需要注意的是，由于構造二次B樣條曲線至少需要4個數據點，因此在對數據進行分段逼近時，若遇到數據個數少于4個的分段則要單獨考慮。對于僅有1個數據的分段，其逼近曲線退化為這個數據點；僅有2個數據的分段，其逼近曲線退化為連接這2個數據點的直線段；含有3個數據的分段，可將通過這3個數據點的二次曲線作為其逼近曲線。而對于僅有1個數據的分段，存儲這個數據點即可對該段進行編碼；僅有2個數據的分段，存儲這2個數據即可對該段進行編碼；含有3個數據的分段，存儲其二次曲線的系數即可對該段進行編碼。

由整個過程可見，這種圖像壓縮方法是一種有損壓縮。壓縮圖像的精度取決于事先設定的預分段長度L和最大允許逼近誤差M。

4 實驗結果

在PC機上(CPU:Intel Pentium T4400, RAM:2 GB, OS:WIN7 Basic)通過MATLAB 7.0軟件對256×256 (8bit) 的Lena圖像進行壓縮實驗。

以峰值信噪比(PSNR)和壓縮比(BR)作為壓縮圖像的客觀評價指標，其中PSNR與BR分別定義為:

從客觀上看，PSNR越高，圖像的壓縮質量越好；BR越小，表明壓縮后圖像的每個像素所需的比特數越少，即圖像的壓縮比越高。

當預分段長度L和最大允許誤差M分別取不同值時，本文方法對Lena圖像進行壓縮實驗所得的BR和PSNR如表1所示。

當預分段長度L=64，最大允許逼近誤差M=25時，利用本文方法所得的Lena原圖像與恢復圖像的對比如圖1所示，其Hilbert掃描曲線對比如圖2所示。

Table 1 Experimental results of Lena imageusing the proposed method表1 本文方法對Lena圖像的實驗結果

Figure 1 Compression results contrast of Lena image using the proposed method圖1 本文方法對Lena圖像的壓縮效果對比圖

Figure 2 Hilbert curve scanning results contrast of Lena image using the proposed method圖2 本文方法對Lena圖像的Hilbert掃描曲線對比圖

為了對比本文方法與Bézier曲線逼近方法[4, 5]和有理Bézier曲線逼近方法[8, 9]的壓縮結果，將預分段長度L都取為256，在給定不同的最大允許誤差時，不同方法對Lena圖像的實驗對比結果如表2所示。

Table 2 Experimental results contrast ofLena image using different methods表2 不同方法對Lean圖像的實驗結果對比

由表2可知，在相同條件下，有理Bézier曲線逼近方法[8, 9]所得的結果要好于相應的Bézier曲線逼近方法[4, 5]，且有理三次Bézier曲線逼近方法[9]與有理二次Bézier曲線逼近方法[8]在壓縮比和PSNR方面各占優勢；本文方法所得結果也要好于Bézier曲線逼近方法[4, 5]，但比有理Bézier曲線逼近方法[8, 9]稍遜一籌。

分別利用不同方法對Lena圖像進行壓縮實驗(包括編碼與解碼)，當預分段長度L都取為256、最大允許誤差M都取為25時，各方法所需的平均時間如表3所示。

Table 3 Comparison of time using different methods表3 不同方法所需時間比較

由表3可知，本文方法所需時間與三次Bézier曲線逼近方法[5]基本相當，且要少于有理Bézier曲線逼近方法[8, 9]。由此可見，雖然本文方法的壓縮效果要略遜于有理Bézier曲線逼近方法[8, 9]，但由于本文方法采用的是多項式函數逼近，其計算量明顯要小于采用有理函數逼近的方法，因此本文方法是一種簡單有效的數字圖像壓縮方法。

需要說明的是，對于同一幅圖像，預分段長度L和最大允許逼近誤差M越大，則圖像的壓縮比越高，但恢復圖像的PSNR越小，恢復圖像丟失的細節越多。因此，在實際操作時，要想同時獲得較高的壓縮比和壓縮質量，需根據所考察圖像的具體情況設定合理的預分段長度值和最大允許逼近誤差值。另外，由于本文方法是一種有損壓縮方法，因此相對于原始圖像而言，解碼后恢復圖像的質量不可避免地會所有降低，此時可利用圖像增強或圖像修復等技術對恢復圖像進行再次處理，以獲得質量更高的存儲圖像。

5 結束語

利用曲線逼近方法進行圖像壓縮時，逼近誤差對壓縮圖像的壓縮比和壓縮質量有較大的影響。本文提出了一種利用二次B樣條曲線逼近進行圖像壓縮的方法，該方法首先通過Hilbert掃描將二維圖像轉化為一維灰度序列；然后采用二次B樣條曲線對數據進行分段逼近，同時利用逼近的最大絕對誤差小于最大允許誤差來確定最終分段；最后對每段數據的逼近參數進行編碼。實驗結果表明，本文方法能獲得較好的壓縮效果，且計算量適中，是一種簡單有效的數字圖像壓縮方法。

[1] Taubman D, Marcellin M. JPEG2000:Image compression fundamentals,standards and practice [M]. Boston, MA:Kluwer, 2001.

[2] Pan J H, Liao Q M. Region coding using improved B-spline surface approximation [J]. Electronics Letters, 2000, 36(2):129-130.

[3] Biswas S. One-dimensional B-B polynomial and Hilbert scan for gray level image coding [J]. Pattern Recognition, 2004, 37(4):789-800.

[4] Biswas S, Lovell B C. Bézier and splines in image processing and machine vision [M]. London:Springer, 2008.

[5] Wang Qiao-long, Wang Zheng-xuan, Xu Zhi-wen, et al. Image compression algorithm based on third degree Bernstein polynomial [J]. Chinese Journal of Scientific Instrument, 2004, 25(S2):432-435. (in Chinese)

[6] Cao Wen-lun,Shi Zhong-ke,Feng Jian-hu.Traffic image coding method based on polynomial approach [J]. Computer Engineering and Applications, 2006, 42(19):183-185. (in Chinese)

[7] Yu Bo,Jian Wei,Chen Jian-xun,et al. A method based on orthogonal polynomial partitioned imitation for image compression coding [J]. Microcomputer Applications, 2007, 28(12):1316-1320. (in Chinese)

[8] Li Jun-cheng, Zhao Dong-biao, Lu Yong-hua. Image compression based on Hilbert scan and quadratic rational Bézier curve approximation [J]. Journal of Huazhong University of Science and Technology(Natural Science Edition), 2012, 40(1):21-25. (in Chinese)

[9] Li J C, Zhao D B, Lu Y H. Image compression using Hilbert scan and cubic rational Bézier curve approximation [J]. Journal of Computational Information Systems, 2011, 7(12):4311-4318.

[10] Zhu Xin-xiong. Technology for free curves and surfaces modeling [M]. Beijing:Science Press, 2000. (in Chinese)

附中文參考文獻：

[5] 王巧龍, 王鉦旋, 許志聞, 等. 基于三次Bernstein多項式逼

近的數字圖像壓縮算法[J]. 儀器儀表學報, 2004, 25(S2):432-435.

[6] 曹文倫, 史忠科, 封建湖.基于多項式擬合的交通圖像編碼方法[J]. 計算機工程與應用, 2006, 42(19):183-185.

[7] 余波, 簡煒, 陳建勛, 等.基于正交多項式分段擬合的圖像壓縮編碼方法[J]. 微計算機應用, 2007, 28(12):1316-1320.

[8] 李軍成, 趙東標, 陸永華. 基于Hilbert掃描與二次有理Bézier曲線逼近的圖像壓縮[J]. 華中科技大學學報(自然科學版), 2012, 40(1):21-25.

[10] 朱心雄.自由曲線曲面造型技術[M]. 北京:科學出版社, 2000.

LIJun-cheng,born in 1982,PhD,lecturer,CCF member(E200012001M)，his research interests include computer aided geometric design, geometric modeling, and image processing.

ImagecompressionusingquadraticB-splinecurveapproximation

LI Jun-cheng

(Department of Mathematics,Hunan Institute of Humanities,Science and Technology,Loudi 417000,China)

A method for image compression, based on Hilbert scan and quadratic B-spline curve approximation, is proposed. Firstly, the two-dimensional digital image is converted to one-dimensional grayscale sequence by using Hilbert scanning. Secondly, piecewise quadratic B-spline curves are used to approximate the scanning data, while the condition that the approximate maximum absolute error is less than the maximum allowable error is used to determine the final section. Finally, the approximate parameters of each section are coded. Experimental results show that the proposed method has better compression effect and moderate amount of calculation, which is a simple and effective method for digital image compression.

image compression;quadratic B-spline curve;piecewise approximation;Hilbert scanning

2012-08-13;

：2012-11-30

湖南省自然科學基金資助項目(13JJ6081)；湖南人文科技學院省級重點建設學科“計算機應用技術”資助

1007-130X(2014)02-0325-06

TP391.41

：A

10.3969/j.issn.1007-130X.2014.02.022

李軍成(1982-),男,湖北漢川人，博士生，講師，CCF會員(E200012001M)，研究方向為計算機輔助幾何設計、幾何造型與圖像處理。E-mail:lijuncheng82@126.com

通信地址：417000 湖南省婁底市湖南人文科技學院數學系Address:Department of Mathematics, Hunan Institute of Humanities,Science and Technology,Loudi 417000,Hunan,P.R.China