图像压缩主要解决的问题是尽量减少用来表示图像信息的数据量, 通常使用某种变换去掉图像中的冗余信息来达到压缩的目的. 针对图像压缩的图像变换, 使图像在变换域能量集中地表示, 大量的信息集中于少数的系数上, 而其他的数据很小或几乎为零, 数据进行压缩编码处理时就能更加有效地压缩数据, 这对图像的高效存储与传输具有十分重要的意义.

目前, 常见的用于图像压缩的变换主要有K-L交换、Fourier变换、离散余弦变换(DCT)、小波变换以及近几年出现的以几何多尺度分析^[1]为主要工具的新型变换等. 多年来, 小波变换在图像压缩中已得到了成功的应用, 但是图像的不连续处的变换系数存在显著误差导致重建图像质量较差. 图可对复杂的、不规则区域中定义的信号^[2,3]进行有效表示. 因此, 2011年Hammond等人提出了谱图小波变换(Spectral Graph Wavelet Transform, SGWT)^[4], 它是一种多尺度几何分析理论, 基于谱图理论^[5]和小波变换理论, 具有很好的尺度不变性和局部自适应性, 能对不规则区域图像进行很好的稀疏表示, 并具备完备的理论体系从稀疏系数中恢复原始图像, 在图像处理领域得到了迅速的发展. 2013年, Ortega等人提出了基于图的小波图像编码方法^[6], 通过设计滤波器, 然后利用SPIHT算法对滤波器系数进行压缩编码.

为了改善小波压缩图像重构质量较差的缺点, 本文利用谱图小波变换对图像进行分解, 提出一种针对谱图小波系数的集合分裂嵌入式块编码(Set Partitioned Embedded Block, SPECK)算法, 具有较高的编码速度, 是嵌入式图像编码算法中性能较好的一种. 实验结果表明, 该算法对经典图像压缩编码后均取得了不错的压缩效果, 具有较高的压缩比和峰值信噪比.

1 谱图小波 1.1 经典小波变换

连续小波的产生与母小波 $\psi (t) \in {L^2}(R)$ 的选择有关, 引入尺度因子s, 这里令s>0, 位置因子a, 则小波在不同的位置和尺度下对应的母小波可表示为:

${\psi _{s,a}}(t) = \frac{1}{s}\psi (\frac{{t - a}}{s})$

(1)

则函数f (t)在尺度s和位置a处的连续小波变换定义为:

${W_f}(s,a) = \int\limits_{ - \infty }^\infty {{\psi ^ * }_{s,a}(t)} f(t)dt = \int\limits_{ - \infty }^\infty {\frac{1}{s}{\psi ^ * }(\frac{{t - a}}{s})} f(t)dt$

(2)

从傅里叶域角度出发, 假设尺度参数s是离散的, 将位置参数a作为函数独立的变量, 连续小波在傅里叶域表示为:

${\psi _{s,a}}(x) = \frac{1}{{2\pi }}\int_{ - \infty }^\infty {\hat \psi } (s\omega ){e^{ - j\omega a}}{e^{j\omega x}}d\omega $

(3)

1.2 谱图理论

加权图可用G=(V, E, W)表示, 其中V表示节点集, E表示边集, w为边对应的权值. 讨论 $\left| V \right| = N < \infty $ 有限无向图, 其中N为图中节点数, $A = \{ {a_{m,n}}\} \in {R^{N \times N}}$ 表示图G的邻接矩阵, 该矩阵元素a_{m, n}可表示如下:

${a_{m,n}}=\left\{ {\begin{array}{*{20}{c}}{w(e)}, & {e \in E,m \ne n}\\0, & {{\text{其它}}}\end{array}} \right.$

(4)

度d(m)定义为 $d(m) = \sum\nolimits_n {{a_{m,n}}} $ , $(m,n = {v_1},{v_2}, \cdots ,{v_N})$ , $D = diag(d({v_1}),d({v_2}), \cdots ,d({v_N}))$ , 称为图G的度矩阵.

图拉普拉斯^[7]矩阵L定义为:

$L = D - A$

(5)

L为实对称矩阵, $L{\chi _\ell } = {\lambda _\ell }{\chi _\ell }$ , $\ell = 0,\cdots,N - 1$ , 该矩阵具有一组完备的正交向量集, 并且L对应的特征值均为非负值. 对应的特征向量 ${\chi _\ell }$ 相互正交, 特征值 ${\lambda _\ell }$ 满足: $0 = {\lambda _0} < {\lambda _1} \le {\lambda _2} \le \cdots \le {\lambda _{N - 1}}$ .

拉普拉斯矩阵的特征空间类似于傅里叶域. 因此, 定义图上傅里叶变换^[8]:

$\hat f(\ell ) = \left\langle {{\chi _\ell },f} \right\rangle = \sum\limits_{n = 1}^N {{\chi _\ell }^ * } (n)f(n)$

(6)

相应的, 图上傅里叶逆变换定义为:

$f(n) = \sum\limits_{\ell = 0}^{N - 1} {\hat f(\ell ){\chi _\ell }} (n)$

(7)

1.3 谱图小波变换

类似于图的傅里叶变换, 为了定义图上的小波变换, 选择满足 $g(0) = 0$ , $\mathop {\lim }\limits_{x \to \infty } g(x) = 0$ 的小波核函数g, 使 $g(sw)$ 对应于 ${\psi ^ * }(sw)$ , 在尺度t和节点n, 图的拉普拉斯矩阵的特征空间L, 定义谱图小波 ${\psi _{t,n}}(m)$ :

${\psi _{t,n}}(m) = \sum\limits_{\ell = 0}^{N - 1} {g(t{\lambda _\ell })} \chi _\ell ^ * (n){\chi _\ell }(m)$

(8)

选择满足 $h(0) = 0$ , $\mathop {\lim }\limits_{x \to \infty } h(x) = 0$ 的低通滤波核函数h, 定义图上的尺度函数 ${\phi _n}(m)$ :

${\phi _n}(m) = \sum\limits_{\ell = 0}^{N - 1} {h({t_J}{\lambda _\ell })} \chi _\ell ^*(n){\chi _\ell }(m)$

(9)

小波系数和尺度系数如式(10)和式(11)所示:

${W_f}(t,n) = \left\langle {{\psi _{t,n}},f} \right\rangle = \sum\limits_{m = 1}^N {\psi _{t,n}^ * } (m)f(m)$

(10)

${S_f}(n) = \left\langle {{\phi _n},f} \right\rangle = \sum\limits_{m = 1}^N {\phi _n^ * } (m)f(m)$

(11)

因为对于大图不能明确的计算拉普拉斯矩阵的特征空间, 文献[6]提出一种快速谱图小波变换算法, 它用切比雪夫多项式逼近^[9]小波核函数g和h.

$g({t_j}x) = \frac{1}{2}{c_{j,0}} + \sum\limits_{k = 1}^{M_j} {{c_{j,k}}T_a^k(x)} $

(12)

c_j,k表示切比雪夫系数, M_j是多项式逼近的阶数, $T_a^k(x) = T_a^k((x - a)/a)$ , $T_a^k(x)$ 表示阶数是k的移位切比雪夫多项式. 给出快速的近似谱图小波变换:

${\tilde W_f}({t_j},n) = \frac{1}{2}{c_{j,0}}f + \sum\limits_{k = 1}^{M_j} {{c_{j,k}}} T_a^k(L)f$

(13)

${\tilde S_f}({t_j},n) = \frac{1}{2}{c_{0,0}}f + \sum\limits_{k = 1}^{{M_0}} {{c_{0,k}}} T_a^k(L)f$

(14)

根据公式(13)和(14)给出的快速小波系数和尺度系数计算公式, 当尺度Nscales = 4, 256×256的lena. bmp谱图小波变换得到一个低频系数和4个高频系数, 如图1所示.

尺度系数也称为低频系数, 如图1(a)所示, 可以看出它集中了原始图像的主要能量. 小波系数也称为高频系数, 如图1(b~f)所示, 显示了图像边缘、轮廓的纹理特征, 其数值远小于尺度系数值. 所以说在谱图小波系数中存在许多不重要的系数, 具有能量聚集性以及能量随尺度增加而衰减的特性.

从一组给定的谱图小波系数c=wf中恢复一个图信号, 合并所有的小波变换, 框架算子 $W:{R^N} \to {R^{N(J + 1)}}$ 将信号f映射成框架系数, 即 $c = Wf = {(c_0^{\rm T},c_1^{\rm T}, \cdots ,c_J^{\rm T})^{\rm T}}$ , 其中c₀=T_hf 是尺度系数, ${c_j} = T_g^Jf$ 是尺度为s_j的小波系数, $1 \le j \le J$ . 使用伪逆算子 ${W^ + } \buildrel \Delta \over = {({W^ * }W)^{ - 1}}{W^ * }$ 从逼近系数和小波系数重构信号, ${({W^ * }W)^{ - 1}}$ 的计算本文采用共轭梯度方法, 而W^*W和W^*的计算采用快速切比雪夫多项式逼近方法.

2 基于谱图小波系数的SPECK算法

在完成图像的谱图小波变换后, 得到多个一维的小波系数向量. 由于小波系数中存在许多不重要的系数, 具有能量聚集性以及能量随尺度增加而衰减的特性, 而基于块集合划分思想的SPECK(集合分裂嵌入式块编码)算法^[10]是一种针对小波系数的编码算法, 该算法是近期嵌入式分级图像编码算法中性能较好的一种.

为了消除分量系数之间的冗余性, 本文使用改进后的SPECK编码算法^[11,12]进行位平面编码, 具体算法为编码时将所有分量系数视为一个整体, 对各个分量进行交叉位平面编码, 生成一个混合的位流.

设 ${c_{j,n}}$ 表示在尺度下s_j的第n个谱小波变换系数. 算法的实现过程中, 采用逐次逼近量化, 定义了非重要集合链表(LIS)和重要系数链表(LSC)两个链表. 具体的算法流程如下所示.

算法. 基于改进的SPECK算法的谱图小波系数编码

1) 算法初始化

　计算 $\scriptstyle {k_{\max }} = \left\lfloor {{{\log }_2}\left( {\mathop {\max }\limits_{0 \le j \le J,1 \le n \le N} \left\{ {\left| {{c_{j,n}}} \right|} \right\}} \right)} \right\rfloor $ . 将变换系数c分成根集合S=c₀和剩余集合 $\scriptstyle I = {\left( {{{\left( {{c_0}} \right)}^{\rm T}}, \cdots ,{{\left( {{c_J}} \right)}^{\rm T}}} \right)^{\rm T}}$ . 置LSC为空表, 并将S放入LIS中.

2) 分类扫描过程

　按|S|大小升序排列集合S, 对每个 $\scriptstyle S \in LIS$ 执行子过程 $\scriptstyle ProcessS(S)$ .

　如果 $\scriptstyle I \ne \emptyset $ , 执行子过程 $\scriptstyle ProcessI(I)$ .

3) 精细扫描过程

　对上次分类扫描过程中己是显著的系数, 输出该系数的第k个显著位.

4) 量化步长更新

如果位平面索引k>0,k=k–1, 返回第2)步; 否则停止.

其中, 各个子过程描述如下:

　 $\scriptstyle ProcessS(S)$ :

　　　输出集合S的第k个显著位 $\scriptstyle{B_k}(S)$

　　　如果 $\scriptstyle{B_k}(S) = 1$

　　　如果S是单个系数, 输出系数的符号位, 然后放入LSC中;

　　　否则执行子过程 $\scriptstyle CodeS(S)$

　　　如果 $\scriptstyle S \in LIS$ , 从LIS中删除S

　　　如果 $\scriptstyle {B_k}(S) = 0$

　　　如果 $\scriptstyle S \notin LIS$ , 把S放入LIS中

　 $\scriptstyle CodeS(S)$ :

　　　将S分裂成S₁, S₂, 其中 $\scriptstyle \left| {{S_1}} \right| = \left\lfloor {\left| S \right|/2} \right\rfloor $ , $\scriptstyle \left| {{S_2}} \right| = \left\lceil {\left| S \right|/2} \right\rceil $

　　　对集合 $\scriptstyle {S_i}(i = 1,2)$

　　　输出集合S_i的第k个显著位 $\scriptstyle {B_k}({S_i})$

　　　如果 $\scriptstyle {B_k}({S_i}) = 1$

　　　如果S_i是单个系数, 输出系数的符号位, 然后放入LIS中

　　　否则执行子过程 $\scriptstyle CodeS({S_i})$

　　　如果 $\scriptstyle {B_k}({S_i}) = 0$ , 把S放入LIS中

　 $\scriptstyle ProcessI(I)$ :

　　　输出集合I的第k个显著位 $\scriptstyle {B_k}(I)$

　　　如果 $\scriptstyle {B_k}(I) = 1$

　　　执行子过程 $\scriptstyle CodeI(I)$

　 $\scriptstyle CodeI(I)$ :

　　　将I分裂成S^*和I^*, 其中 $\scriptstyle \left| {{S^ * }} \right| = \left| S \right|$ , $\scriptstyle \left| {{I^ * }} \right| = \left| I \right| - \left| {{S^ * }} \right|$

　　　对集合S^*, 执行子过程 $\scriptstyle ProcessS({S^ * })$

　　　对集合I^*, 执行子过程 $\scriptstyle ProcessI({I^ * })$

3 实验结果与分析

对该算法整体分析可知, 算法中全部可变参数有尺度参数Nscales, 切比雪夫多项式阶数m, 设计参数k=200以及扫描次数sm. 由于切比雪夫多项式阶数m影响重构图像的质量, 因此实验中以m值作为变量, 得到不同质量的重构图像.

3.1 图像数据压缩

对图像压缩性能的评价则可以用压缩比C_r来表示如下:

${C_r} = \frac{{M \times N \times n}}{C}$

(15)

由于不同码率下恢复图像的质量不同, 因此压缩率并不是一个独立的指标, 必须与图像恢复质量统一进行比较.

在进行算法测试时, 选取512×512像素的经典图像, 利用文中提出的算法, 设置Nscales=5, 在保证图像重构质量良好的情况下, 得到压缩后数据量与原数据的压缩比(C_r)及峰值信噪比(PSNR), 压缩结果如表1所示.

分析表1中的数据, 将谱图小波压缩后得到的图像与原图像进行对比, 可以看出文中提出的压缩算法在一定程度上减少了数据量, 总体得到了不错的压缩效果, 证明了本文提出的谱小波压缩方案的可行性. 这是由于选取了合适的参数, 突出了图像重构中较大小波系数的重要性, 而且基于块编码的算法较大程度地减少了较小的小波系数, 从而提高了压缩比.

3.2 重构误差衡量

峰值信噪比(PSNR)表示峰值信号与噪声的比值, 它是表征图像重构效果的重要指标^[13], PSNR评价模型定义如下:

$PSNR = 10\lg \frac{{{l^2}}}{{MES}}$

(16)

式中, MES为均方误差, 是原始图像与重构图像之间的灰度差, M和N为图像矩阵维度数(图像像素), l为图像最大灰度值, 通常8 bit的图像l为255. PSNR值越大, 表示重构误差越小, 两幅图像相似度越高.

为验证算法的有效性, 设置不同的切比雪夫多项式阶数m, 得到图像重构结果如表2所示, 在相同条件下m越小, 相应的图像的PSNR也越高, 重构误差就相对较小.

分别以256×256和512×512像素的lena图像为例进行相关实验. 选取扫描次数sm=6, 尺度参数Nscales=5, 切比雪夫多项式阶数m分别取3和5, 得到结果如图2所示. 对比不同m下的重构图像, 可以看出, 图2(b)的重构图像与图2(c)相比更接近原始图像, 也就是说, 重构误差就相对较小.

3.3 相关算法的分析比较

选取256×256的lena和template图像, 利用上述压缩比C_r和峰值信噪比PSNR的定义式, 我们可以在相同条件下, 利用本文的算法与基于小波变换的SPECK编码算法计算得到不同尺度下的C_r值和PSNR值, 结果如表3所示.

表3中的数据显示, 本文提出的压缩算法与基于小波变换的压缩算法相比较, 有更大的压缩比, 这说明谱图小波压缩的压缩效果更为明显. 并且随着尺度的改变压缩比变化很小, 图像重构质量也相对稳定.

综上所述, 本文提出的压缩算法在对几个经典图像进行压缩编码后, 均取得了较好的压缩比. 且与基于小波变换的编码算法进行对比, 在减少占用内存空间和重构误差方面都有了一定的改进.

4 结论与展望

本文采用基于谱图理论和经典小波变换理论的谱图小波变换, 提出了一种针对谱小波系数利用SPECK编码进行压缩编码的新方法. 文中对几个经典的图像进行了性能测试, 均取得了不错的压缩效果, 并从压缩比和峰值信噪比两个方面讨论了图像压缩及重构的质量, 该算法在减少数据存储空间和重构误差方面都有了一定的改进. 但是对于大图来讲, 编解码的速度相对较慢, 这也是未来继续研究的方向.