利用二次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