多媒体通信图像压缩

第2章多媒体数据压缩的基本技术小波变换及其用于图像编码压缩原理宁晓燕2016年秋季学期变换编码——能量的再分配2傅立叶变换与小波变换傅立叶变换的局限性4傅立叶变换是一种整体变换，无法反映信号的局部特征时频信号分析工具短时傅立叶变换5时频信号分析工具小波变换6二维图像的小波变换分解8小波变换的EZW编解码小波变换的EZW编解码可以看出，经过小波变换后，信号能量已经集中在少数系数上，将幅值很小的其他系数忽略（量化到0），则可达到数据压缩的目的。量化后的变换系数矩阵是一个具有少量非零值和大量零值的稀疏矩阵，在将此矩阵转换为一维序列时，如何有效地组织非零系数和有效地表达零系数所在的位置，对数据压缩的效率有至关重要的影响。Lewis和Knowles在1992年提出了小波零树编码算法。10首先要介绍一个基本概念：零树

一个系数x的直接后代或称子节点有三种情况：（1）最低频子带LLn（n为小波变换的级数），如图所示LL3的任一个系数x在HL3、LH3、HH3中的对应位置均有一个子节点，即LLn子带的系数共有3个子节点或称直接代；（2）最高频的三个子带HL1、LH1、HH1，均无后代；（3）除上述两种情况外，其它各子带的一个系数x在相邻高频子带的相应位置都有4个系数与之对应，且称该4个系数为子节点或直接后代。11一幅图像三级小波变换后的系数结构LL3HL3HH3LH3HL2HL1HH2LH2LH1HH1121.把一个系数x作为一个树根考察时，它的后代包括直接后代（也称子节点）以及这些子节点的后代。根据考察点的位置不同，这棵树的层次（或高矮）也不一样，可以是中的一种，或者是

或它的扩展。2．重要系数与不重要系数。对于一给定的阈值T1，如果系数x的绝对|x|≥T1，则称x为重要系数，否则，为不重要系数。3．零树的概念：对于一给定的阈值T1，如果该系数x本身和它的所有后代都小于T1，则称这棵树为一零树，该系数就为零树根●●●13小波零树编码算法就是利用小波树的强相关性，将父节点的绝对值与门限进行比较，当父节点绝对值小于门限时，认为该小波树均不是显著系数，因此将该小波树都以零值编码，从而减少数据。显然，零树编码不是十分完美，譬如，父节点不显著时也存在子节点显著的情形，此时将造成较大的误差。1993年，Shapiro在小波零树编码算法的基础上提出了嵌入小波零树编码（EmbeddedZero-treeWavelet,EZW）算法。14EZW算法中，用5种符号表示小波系数：正符号（PositiveSymbol,POS）：绝对值大于门限值，且值为正的小波系数。负符号（NegativeSymbol,NEG）：绝对值大于门限值，且值为负的小波系数。孤立零值(IsolatedZero,IZ)：绝对值小于门限值，但存在后代节点的绝对值大于门限值的小波系数。小波零树(Zerotree,ZTR)：绝对值小于门限，且后代节点的绝对值都小于门限的小波系数。零符号(ZeroSymbol,Z)：绝对值小于门限的叶节点。由于小波树在一定扫描顺序下位置能完全确定下来，所以在实际编码中小波零树和令符号可以用同一符号来表示。15（1）门限值的选取

初始门限值：,其中

表示小波系数，

表示取不超过该数的最大整数值。此后每次的门限值：（2）扫描顺序EZW算法通常对小波系数矩阵

采用Z形扫描顺序，如右图所示（3）编码过程

编码过程主要分为三个过程：显著性扫描过程（DominantPass），主要确定小波系数的符号（5种符号之一）；改进扫描过程（RefinementPass），对小波显著系数（正符号和负符号）进行加细量化；符号编码过程（SymbolEncode），对符号进行熵编码。1615106-7-1223130000000000000005-4-3232-210

0

0140

0

000

0

0

00

00

0

0300

0020

0000

0000一幅8×8图像三级小波变换后的系数矩阵以下图所示的8×8图像三级小波分解系数矩阵为例说明EZW编码过程171.首先计算阈值T1，对例子中的系数矩阵，∵Xmax=15:而n=∴T1=23=82.根据阈值进行第一轮显著性扫描：扫描顺序为Z字形，从低频子块到高频子块，在每个子块里都从左到右从上到下一行一行地扫描。3.X>T1的重要系数放入副表中。

18|x|≥T符号？是零树根的后代？该系数的所有后代还有无重要系数？YNY

跳过，不予编码N无用ZTR对x编码有用IZ对x编码－+用POS对x编码并把绝对值放入副表中用NEG对x编码并把绝对值放入副表中对系数x编码扫描每个系数x时的处理流程规则：①对大于T的正值编成P，负值编成N;②对小于T的零树，大小之根都编成

ZTR，而对零树的干枝叶都跳过不编；③对孤立零不论哪级的都编成IZ（即为根）（即为孤零）19显著性扫描过程204.第一轮改进扫描过程：对T1=8时，其副表中的绝对值肯定处于8—16之间，为此我们把处于12（即1.5T1）以下的实际值编为0，处于12及以上的实际值编为1，以对区间进行细化，其编码规则如下图所示，结果如表（1）所示。21最后将这些0，1序列排在原已编过码的四类符号之后，对前例而言，经第一轮编码后的码字就为PPIZ；NZZZ；ZIZZ；ZZZZ；ZPZZ；1011。即15,10,-7,6；-12,2,3,1；3,2,-2,1；3,0,0,0；0,14,0,0；15,10,-12,14。为了把更重要的信息放在更前面，在每次副扫描后都要进行副表的重排序工作，为使编、解码对应，应从解码方的角度对副表进行重排序。我们认为系数绝对值越大的就越重要，把原副表进行重排序，显然，被编码成0的10应排到副表最后。而对于12、14和15，因为都编码为1，这时从解码方的角度就还无法辨别其大小，所以它们之间的顺序仍保持不变。则经重排序后的结果如表（2）所示。22第二轮显著性扫描过程：这里需要注意的是，对前面扫描过程中已经确定的重要系数就不再扫描，且他的细节信息在随副扫描进行而增加。为了与原来的0有所区别，这里用表示。设第二轮的阈值232425第二轮改进扫描过程，此时副表中的绝对值已变为15,12,14,10,7,6,5,4，已知它们分别处于区间[4，8)、[8，12)、[12，16)，我们判断它们是处于每个区间的上半部分[6，8)、[10，12)、[14，16)，还是下半部分[4，6)、[8，10)、[12，14)，并分别用1和0进行编码，有10111100，见表（3）。最后将这个二进制序列排在第二轮已编过的四类符号之后则本次编码输出为：NP；ZZZ；ZZZZ；PNZZ；ZZZZ；ZZZZ；ZZZZ；10111100。即，-7,6；2,3,1；3,2,-2,1；5,-4,-3,2；3,0,0,0；0,3,0,0；0,0,2,0；15,-12,14,10,-7,6,5,-4。

26这时，从解码方的角度已能分辨14>12，所以重排序为15，14，12，10，7，6，5，4。

11011100

自然码字27EZW算法的解码步骤（一）在未获得小波系数的编码码流前，解码方应先获得：图像大小：小波变换级数；初始阈值T1。本例的图像大小为8×8；小波级数为3；初始阀值为T1=8。解码方在获得这些信息以后，会开辟一个8×8的存储空间，并把系数的值赋为028

按照与编码一样的扫描顺序，边扫描这个初始化为0的系数矩阵，边读取码流：PPIZ；NZZZ；ZIZZ；ZZZZ；ZPZZ……

在读到POS时用1.5T1重建=12，并把坐标也放入一个解码方维持的副表。在读到NEG时用―1.5T1重建=-12，并把坐标也放入一个解码方维持的副表。在读到IZ和ZTR时，不用对该系数赋新值，但对于ZTR的后代，以后就跳过，不扫描。29

按照上述规则，当做完第一次显著性扫描时，解码出的系数矩阵如上图所示。这时，解码方副表的情况如表（4）所示，继续读副表中的原始码流：1011，并分别对应。解码方经过第一轮显著性扫描后的重建值30

表（4）：解码方第一轮改进扫描未重排的示意图31

所以，在解码方进行了一次显著扫描和改进扫描后，解码出的系数矩阵为图（8）。与编码对应，这时也要进行一个副表的重排序，重排序后的副表如表（5）所示图（8）：解码方经过第一轮副扫描后的重建值X表（5）：解码方第一轮副扫描重排序后的副表32（二）接着进行第二遍的扫描，这时，与编码一样，对在第一轮中已发现是重要的系数，在第二轮的显著性扫描中，就不对其进行扫描。另外，解码重构规则与第一遍解码扫描时一样，只是把T1换成了T2=4，即：读到POS时用1.5T2=6重建，并把坐标也放入解码方的副表中。在读到NEG时用―1.5T2=-6重建，并把坐标也放入解码方的副表中。33

在读到IZ和ZTR时，不用对该系数赋新值，但对于ZTR的后代，以后就跳过，不扫描。图(9)：解码方经过第二轮主扫描后的重建值34

读到的第二轮原始码流是：NP；ZZZ；ZZZZ；PNZZ；ZZZZ；ZZZZ；ZZZZ和第一轮经重排后的副表之自然码字。则第二遍显著性扫描解码后的结果见图（9）。显然是按±1.5T2=±6进行重建。这时副表的情况见表（6）：表（6）：解码方第二轮

改进扫描的示意图35接着进行第二轮副扫描的解码，这时读到的码流是：经第一轮重排后的第二轮自然码字10111100，与现在副表中的数据相对应，进行解码。按前面所述的副扫描解码规则，这时把T1变成了T2