3.3.2 EZW编码优化与改进
根据压缩编码需要,可以把小波系数分为四类:零树根、孤立零、重要系数、不重要系数。一些小于设定门阀的小波系数,称为不重要系数,否则就是重要系数。如果一棵树的根节点是不重要系数,且其所有的后代也是不重要系数,那么定义为这棵树为零树,用ZT表示。定义一棵树是孤立零,那么该树需要满足两个特征:树根是不重要系数;在其后代中有重要系数。用IZ表示孤立零树。为了提高编码效率,根据重要系数的正负性质又分成正重要系数和负重要系数两类,分别用POS,NEG表示。EZW 压缩编码相对于其他压缩编码方式,具有高压缩比、精度可变的优点。但是因为在每轮EZW 编码中必须嵌入结构标志位编码,因此带来冗余的信息,制约了编码的压缩比的提高。一般而言,EZW 压缩比CR在1.25~1.80 之间,离实时移动ECG监护的要求还有较大距离。因此本书在编码上从三个方面进行优化。

图3-2 ECG信号QRS波与T波小波分量示意图
一是压缩中用一个主表MT保存系数所在节点的属性及位置信息,用副表ST保存系数的值。主表MT逻辑上是一棵完全二叉树,根据MT的索引信息可以定位逻辑结构位置,把副表ST中保存的值恢复到原来的逻辑位置上。
二是根据分段阀值TL,TL-1,…,T1将ST表的重要系数值按照绝对值的大小分成L 个层次:第i层表示绝对值大于或等于Ti但是小于Ti+1(当i<L 时)的系数,第L 层表示绝对值大于或等于TL的系数。不同的阀值决定了不同分层的最短编码。例如,10 位编码最大可以表示绝对值为1023 的数据,但大部分系数可能绝对值都会小于32,如果都用10 位二进制编码显然是浪费,这时候可以用T1=0,T2=512 将系数分成两类编码。因此对于重要系数来讲,需要用4 种编码来表示:POS1,NEG1 表示绝对值小于512 的第1 类系数;POS2,NEG2 表示绝对值大于512 的第2 类系数,显然第一层系数只需要用5 位二进制码就可以表示。
三是对MT表进行优化。MT对应的是一棵完全二叉树。设这棵树有2N-1个节点,每个节点用两位编码,那么这棵结构树要占用2N+1个额外的空间。事实上在通过小波变换后会产生大量的零树,而对于零树而言,仅保留树根就可以了,其子孙是可以省掉的。对于一棵保留了系数位置及属性的完全二叉树,可以按照以下算法3.1 进行序列化压缩。
算法3.1 零树序列化压缩算法

这样MT表是一棵序列化的经过压缩的二叉树。本书通过如下算法3.2 将其恢复为一棵完全二叉树。
算法3.2 从经过裁剪的序列化表恢复一棵完全二叉树的算法

表3-1 列出了一段含有32 个数据的数字信号经过5 层小波变换后的系数。(https://www.daowen.com)
表3-1 一段含有32个数据的数字信号经过5层小波变换后的系数

按照常规EZW 编码,MT共有s(MT)=31×2=62 位,数据用10 位表示则ST表中共有12 位重要系数,共需要s(ST)=12×10=120 位,因此总共编码需要s(MT)+s(ST)=182 位。下面采用改进的编码方式进行处理。
节点类型编码如表3-2 和表3-3 所示。
表3-2 两层压缩的编码方案

表3-3 压缩后的MT编码与ST编码对应表

MT表的序列化编码结果如下:010,11,010,010,10,011,011,010,11,011,001,011,001,011,011;
ST表的序列化编码结果如下:0000111111,01111,1111111111,11111,01111,11111,00101,00100,00011,00101,01001,01000。
因此总共需要s(MT)+s(ST)=42+70=112 位,如果不进行EZW 编码压缩,则共需要31×10=310 位数据表示,与常规EZW 编码方法相比节省存储空间38%。本书将基于以上思想改进的EZW 算法称为Dynamic EZW(DEZW)。