近年来,在图像压缩领域出现了一些优秀的基于上下图模型的编码方法[1],其中比较著名的有:CALIC,LOCO-1等[2,3]。CALIC算法包含了一个自适应的梯度预测器,以预测误差的能量估计的量化值作为上下图,对预测误差进行编码,压缩比较大,是目前为止一种比较理想的无损压缩方法,但是它的计算方法较复杂;LOCO-1是JPEG-LS[4]的标准算法,它的计算方法比较简单,但是压编比要小于CALIC。除此之外,目前还存在其他一些比较好的无损压缩算法,如在JPEG2000[1]标准中,使用了小波技术,从而可以实现从有损到无损的深进压缩。然而,如果在某一特定环境下,需要将1幅已经压缩完毕的图像的低位舍去,从而来适应带宽等条件的限制,就必须先将该图像解压重建,然后再进行去除低位图像的压缩步骤。很明显,这样的压编步骤大大降低了图像处理的效率。针对此种情况,笔者提出了一种基于嵌入式位平面的无损压编算法,简称LELIC(level embedded lossless image compression),该算法是一种基于上下图模型的算法,使用该算法对图像进行压缩后,如果需要舍去低位,只要直接将码流中所对应的低位部分取出即可,存傅和计算都简单,所需要的时间和资源也少。
《1 LELIC的算法》
1 LELIC的算法
为了说明问题,先讨论只有1个嵌入位平面的情况,即将图像分为2个位平面,称为基础层(高位平面)和剩余层(低位平面)。基础层是通过将每一个像素值s除以一个整数L(工可以取2,4,8,16,...,2n中的任何一个)再取整后得到,记作\(B_{L}(S)=\lfloor S / L\rfloor\)剩余层(即嵌人位平面)也叫增强层,是通过将像素值S与\(L\lfloor S / L\rfloor\)相况得到的,记作\(r=S-L \lfloor S / L\rfloor\)。\(L\lfloor S / L\rfloor\)称为量化像素QL(S)。
由于所得到的基础层是图像中的最重要的位平面,丁编码过程中完全没有涉及到增强层,基础层的统计特性与其他全位深图像又非常相似,所以,我们可以使用任何一种无损压缩算法对基础层进行压缩(这里使用的是CALIC(context-based, adaptive, lossless image code)自适应预测熵编码。
增强层对应的是一连续色调图像的低位平面。它的压缩方法主要有3个组成部分,即预测;根据上下关系建模并进行量化;进行条件墒编码。
下面定义几个量:
(1) \(\hat{S}_{0}\)当前像素的预测值;
(2) d, t测定的上下图值;
(3) \(\dot{S}_{0}\)改进后的预测值\(\left(\hat{S}_{0}, d, t\right)\);
(4)θ测定的上下图\(\Theta\left(\hat{S}_{0}\right)\);
(5)用Sk来表示任一像素值(k=1,…,4)。
《1.1 预测》
1.1 预测
《图1》
图1 像素几何图
Fig.1 Geometric graph of image elements
《图2》
图2 量化像素几何图
Fig.2 Geometric graph of measurable pixels
如图1所示,对于每一个像素来说,都有8个像素与它邻近。将当前像素的位置记为0,邻近的8个像素的位置分别为:W,NW,N,NE,E,SE,S,SW。它们的编码顺序和解码顺序都是从左到右,从上到下。这样的编解码顺序使得当0位置的r被编解码的时候,,NW,N,NE位置的像素都已经完成了编解码,即这些位置的像素值已知。古外,图像中所有的量化像素值QL(S)作为一个给定的条件,便是已知量,这样,在W,NW,N,NE位置的像素值S=QL(S)+r和在E,SE,S,SW位置的量化像素值QL(S)就全都知道了(如图2)。我们定义一个函数了f(·),V,NW,N,NE处的像素值用S表示,而在其余位置,则将量化值加上工/2,来补偿QL(.)中的偏差。\(f(S k)=\left\{\begin{array}{ll}S k & \text { if } k \in\{\mathrm{W}, \mathrm{NW}, \mathrm{N}, \mathrm{NE}\} \\Q_{L(S k)}+\frac{L}{2} & \text { otherwise }\end{array}\right.\) （1）
通过计算0位置像素周围最邻近的4个像素(W,E,N,S位置的像素),可以得到0位置像素值的一个简单的线性预测。\(\hat{S}_{0}=\frac{1}{4} \sum_{k \in(\text { W,N,E,S })} f\left(S_{k}\right)\) （2）
然而这个预测经常出现偏差,于是就会生成一个非零的预测误差:\({S}_{0}-\hat{S}_{0}\),需要改进这个预测,计算公式为:
\(\dot{S}_{0}=\operatorname{round}\left(\hat{S}_{0}+\bar{\varepsilon}(d, t)\right)\) (3)
round()是一个舍入函数〔即将数值四舍五入后取整),\(\bar{\varepsilon} \quad(d, t)\)是在给定d,t上下图的情况下,所有预测误差\(\left(\varepsilon=S_{0}-\dot{S}_{0}\right)\)的平均值。\(\hat{S}_{0}\)是一个基于上下图分类,自适应的非线性预测。
《1.2 于上下图建模及量化》
1.2 于上下图建模及量化
所谓上下图,即本文中的d,t也就是概率中的条件。\(\hat{S}_{0}\)是在上下图d,t下对S0的预测,称这样的一组\(\left(\hat{S}_{0}, d, t\right)\)为一个上下图状态。
典型的自然图像在不同的区域有着不同的统计特性,如果我们在压缩过程中只建立了一个单一特性的成像模型,就会使得压缩后的图像产生显著的恶化。而如果像素可以被分离成一系列的基于上下图的上下图状态,每一个上下图状态的值的统计特性都是非常规则的,那么,上下图状态中的一些统计特性(例如概率分布)就可以用于相关像素的条件熵编码中。所以,合适地选择好上下图及其相关统计特性模型,会大大提高编码的效率。
选择上下图的关键在于要适当地确定上下图的个数:增加上下图个数,有助于提高编码效率;而上下图的增长个数和上下图状态的增长个数又呈指数关系,所以当上下图个数增加时,上下图状态个数的增长是十分惊人的,上下图状态的数量太多,从这些上下图状态中计算统计特性的工作量也将增加,从而影响了编码效率,这种因为上下图的数量太多而导致编码效率下降的现象被称为上下图稀释问题。因此,一个好的上下图模型必须选择一个最佳方案,使上下图状态的个数尽可能少的情况下,上下图的个数尽可能的多。
下面就是有关上下图模型建立的步骤:
第一步,定义一个基于d,t上下图的变量\(\Delta\)
\(\begin{array}{c}\Delta=\sum_{k \in|\mathrm{W}, \mathrm{NW}, \mathrm{N}, \mathrm{NE}, \mathrm{E}, \mathrm{SE}, \mathrm{s}, \mathrm{Sw}|} \frac{1}{8}\left|f\left(S_{k}\right)-\hat{S}_{0}\right| \\d=Q(\Delta)\end{array}\)（4）（5）
\(t_{k}=\left\{\begin{array}{lc}1 & \text { if } f\left(S_{k}\right)>\hat{S}_{0} \\0 & \text { otherwise }\end{array}\right.\) (6) \(t=t_{\mathrm{W}}\left\|t_{\mathrm{N}}\right\| t_{\mathrm{E}} \| t_{\mathrm{S}}\) (7)
《图3》
图3 各种不同概率分布函数
Fig.3 Different PMF
(a)在拉普拉斯假设(σd=10)下 (b)相关像索的概率分布函数 (c)增强层的条件概率分布函数的预测误差率分布函数,p(ε l d,); p(\(\dot{S}\)+ε/d,\(\dot{S}\)); (L=4), p(r l d,\(\dot{S}\), QL(S))
为了避免上下图稀释,t上下图只用于预测中,而不用在编码过程中。预测误差的分布函数一舱用零均值不相关拉普拉排概率分布函数表示。图3(a)所示的就是预测误差的概率分布函数(PMF), p(ε l d)。给定\(\dot{S}\)后,可以将预测误差分布p(ε l d)平移\(\dot{S}\),得到像素的概率分布函数 p(s=\(\dot{S}\)+ε/d,\(\dot{S}\)),相应的PMF如图3(b)所示。
为了得到增强层的概率分布并利用量化像素QL(s),这里引人另一个上下图θ,θ只用于编码过程而不用于预测过程。
这里,已知量化值QL(S)成为一个附加的上下图量化像素值QL(S)将像素S的可能的值限制在区间[QL(S),QL(S)+L)]内,如图3(b)中两条垂直界线所包园的区域所示。图3(c)是由图3(b)[QL(S),QL(S)+L)]之间的概率值标准化后得到的条件概率分布函数p(r/d,\(\dot{S}\),QL(5))。
由于拉普拉斯分布在\(\dot{S}\)的峰值呈指数下降,所以条件概率函数P(r/d,\(\dot{S}\),QL(S))有四种可能的分布,如图4所示:如果\(S \leqslant Q_{L}(S)\),峰值在r=0处。如果\(\dot{S} \geqslant Q_{L}(S)+L-1\),峰值出现r=L-1处。当\(Q_{L}(S)<\dot{S}<Q_{L}(S)+L-1\)
如图4所示,峰值在rθ和L-1-rθ位置的分布图是镜像对称的,因此可以将这些上下图状态合并起来,这样一来,上下图状态的数量减少了,而且不会引起图像质量的恶化。接下来,将每一对对称的分布图赋值为一对相反数(±θi),|θ|就和d一起成为一个用于编码的上下图了。
第二步,将\(\dot{S}=Q_{L}(S)\)和\(\dot{S}=Q_{L}(S)+L - 1\)情况单独赋值到一个中。虽然这些情况已经包含在\(\dot{S} \leqslant Q_{L}(S) \)和\(\dot{S} \geqslant Q_{L}(S)+L-1 \text {, }\),但由于公式(3)中舍人函数round()的特性,当\(\dot{S}\approx Q_{L}(s)\)和\( S\approx Q_{L}(S)+L-1\)时可能会导致预测出现偏差,所以将这两种情况单独赋值给一个,这样可以使编码更加准确。最后,上下图6和编码上下图(d,θ)的个数为\(\lfloor(L+1) / 2+1\rfloor\)和\(8\lfloor(L+1) / 2+1\rfloor\)。如果(θ≥0),
编码/解码增强层(r0,d,θ);
如果(θ<0),
编码/解码增强层(L-1-r0, d, |θ|);
《1.3 条件编码》
1.3 条件编码
为了提高效率,使用了基于上下图的自适应算术编码器。该编码器基于上述上下图模型对增强层进行编码。像素的条件概率分布都是由原先已经偏
《图4 》
图4 条件概率分布函数\(P\left(r \mid d, \dot{S}, Q_{L}(S)\right)\),上下图\(\theta=\{\pm 1, \pm 2\} \quad(L=4)\)
Fig.4 Conditional PMFP
码(解码)好了的像素值预测出来,将每一个像素的概率值用最佳编码长度的算术编码进行编码。
1.4 分解为多个嵌入位平面的方法
以上介绍的是仅将图像分解为一个嵌入位平面(一个基础层和一个增强层)的图像处理方法。多个嵌入位平面的分解可以通过对以上算法的直接递归应用而得到。第一步,图象被L1基础层B1和增强层r1。第二步,基础层B1被L2分为基础层B2和增强层r2。依次类推…...。每一个增强层ri基于相关的基础层Bi进行压缩。最后一层Bn,用CALIC算法进行压缩编码。
《2 实验结果》
2 实验结果
图5是4帽512x512的8位灰度图像。为了说明问题,这里取L=2, 用1.4节的方法,将图像分为基础层和增强层。增强层即嵌人位平面,可以从一个到7个不等,例如:一个增强层就是将最低位作为增强层而其余7位属于基础层;7个增强层就是将最高为作为基础层,而其余7位都是增强层,在这种情况下,所有的位平面都可以被重建,因而可以产生完全可测量的码流。如前所述,基础层使用的压缩算法是CALIC算法。
表1所描述的是基于嵌人式位平面的压缩算法的压缩性能和其他各种优秀的压缩算法的性能的比较。其中,CALIC, JPEC2000和JPEG-LS算法不具有平面可测量性,JBIG,JBIG(gray)和本文所提出的LELIC算法具有平面可测量性,我们用L.E.1, L.E.2,...,L.E.7分别表示1个增强层,2个增强层,....,7个增强层。在无损压缩中,CALIC的压缩率最大,所以在表1中,将CALIC的压缩率作为标准,其他压缩算法的压缩率与CALIC相比,计算它们所增长的比特率的百分比。从表中可以看到,JPEG2000和JPEG-LS仅比CALIC增长了很小的比特率,但是他们和CALIC一样,不具备平面可测量性。]BIG具有平面可测量性,但是却比CALIC增长了平均37.1%的比特率。
《图5》
图5 512X512的8位灰度图像
Fig.5 Each image with 512X512 gray levels(8-bits)
使用LELIC算法对图像进行压缩时,随着增强层数量的增多,图像所产生的恶化程度基本是昔一个线性的增长。如果将一幅8位的图像截断成6位的图像,则需要有2个嵌人式位平面(即2个增强层),这样一来,于CALIC算法相比,平均会增
《表1》
表1 基于嵌入式位平面的压缩算法和其他经典无损压缩算法的性能比较
Table1 Performance of LELIC and CALICF
加3.2%的比特率。这一压缩率已经基本可以和JPEG-LS以及CALIC相媲美。如果将图像截断成只有一位,即需要7个增强层,这样平均会比CALIC算法增加15.1%的比特率,即使这样的压缩率也大大优于了JBIG算法。
《3 结语》
3 结语
到目前为止,并不存在绝对好的图像压缩方法:JPEG2000具有非常丰富的功能,但它的无损压缩比低于JPEG-LS;JPEG~LS和CALIC具有较高的无损压缩比,但是不具备平面可测量性;而笔者提出的LELIC算法,虽然它的压缩比略微低于JPEG-LS和CALIC,但是由于它所具有的位平面可测量性,使得在带宽不稳定的情况下仍然可以完整地访问图像这一愿望成为了可能。因此,在网络带宽经常变化的不佳条件下,LELIC算法是一种比较理想的压缩算法。
京公网安备 11010502051620号
