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

李軍成

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

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

李軍成

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

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

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

1 引言

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

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

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

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

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

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

2.1 二次B樣條曲線

(1)

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

(2)

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

(3)

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

(4)

由式(3)易知:

(5)

(6)

(7)

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

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

(8)

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

2.2 逼近方法

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

(9)

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

(10)

解得:

(11)

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

(12)

3 圖像壓縮方法

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

Step1將原始圖像通過Hilbert曲線掃描轉(zhuǎn)化為掃描數(shù)據(jù)。

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

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

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

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

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

4 實驗結(jié)果

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

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

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

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

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

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

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]的壓縮結(jié)果，將預(yù)分段長度L都取為256，在給定不同的最大允許誤差時，不同方法對Lena圖像的實驗對比結(jié)果如表2所示。

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

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

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

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

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

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

5 結(jié)束語

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

[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多項式逼

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

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

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

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

[10] 朱心雄.自由曲線曲面造型技術(shù)[M]. 北京:科學(xué)出版社, 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

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

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

TP391.41

：A

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

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

通信地址：417000 湖南省婁底市湖南人文科技學(xué)院數(shù)學(xué)系A(chǔ)ddress:Department of Mathematics, Hunan Institute of Humanities,Science and Technology,Loudi 417000,Hunan,P.R.China