第4章小波图像编码 HL2 H3E HIL 1 LH2HH2 LHI 垂圈便 图4-06Lena三级分解图像 各级子图像中的系数之间的关系可以用树的形式描述。如图4-07(a)所示,最低频率的子 图像在左上角,最高频率的子图像在右下角,由同一方向和相同空间位置上的所有小波系数 组成一棵树。例如,从第三级子图像HH3、第二级子图像HD到第一级子图像HH的相应位 置上的所有系数构成一棵下降树。按箭头所指的方向,各级系数的名称分别用祖系数、父系 数、子系数和孙系数来称呼。举例来说,LL3的系数为(63},HH2和HH中的系数分别为{3} 和{4,6,3,-2},由这些系数构成的树如图407b)所示。如果把{63}指定为父系数,{3}就称 为子系数,而{4,6,3,-2}中的4个系数就称为孙系数 LL3HL3 (a)构造方法 (b)小波系数举例 图4-07EZW编码树的构造 现在再来看零树的概念。为便于比较,把图4-07(b)所示的两棵树用图408(a)和(b)表示 假设编码时开始的阈值=32,由于63比32大,这样的树叫做非零树,图4.08(a)所示。假 设下一次编码时的阈值T1=16,把-13当作父系数,它的幅度16小,而它的所有4个子系数 的幅度都比16小,这样的树叫做零树,系数-13叫做零树根,如图4-08(b)所示。根据以上的 分析,零树的定义可概括为一句话:子孙系数都为零的树。定义零树的重要意义在于,如果 棵树是零树,那么这棵树就可以用一个预先定义的符号来代表整棵树,从而提高了压缩比。 顺便要指出的是,小波图像系数结构的形式不只是上面介绍的一种,也可能不是最好的 种 6
第4章 小波图像编码 6 图4-06 Lena三级分解图像 各级子图像中的系数之间的关系可以用树的形式描述。如图4-07(a)所示，最低频率的子 图像在左上角，最高频率的子图像在右下角，由同一方向和相同空间位置上的所有小波系数 组成一棵树。例如，从第三级子图像HH3、第二级子图像HH2到第一级子图像HH1的相应位 置上的所有系数构成一棵下降树。按箭头所指的方向，各级系数的名称分别用祖系数、父系 数、子系数和孙系数来称呼。举例来说，LL3的系数为{63}, HH2和HH1中的系数分别为{3} 和{4, 6, 3, -2}, 由这些系数构成的树如图4-07(b)所示。如果把{63}指定为父系数，{3}就称 为子系数，而{4, 6, 3, -2}中的4个系数就称为孙系数。 (a) 构造方法 (b) 小波系数举例 图4-07 EZW编码树的构造 现在再来看零树的概念。为便于比较，把图4-07(b)所示的两棵树用图4-08(a)和(b)表示。 假设编码时开始的阈值T0 = 32 ，由于63比32大，这样的树叫做非零树，图4-08(a)所示。假 设下一次编码时的阈值T1 = 16 ，把-13当作父系数，它的幅度16小，而它的所有4个子系数 的幅度都比16小，这样的树叫做零树，系数-13叫做零树根，如图4-08(b)所示。根据以上的 分析，零树的定义可概括为一句话：子孙系数都为零的树。定义零树的重要意义在于，如果 一棵树是零树，那么这棵树就可以用一个预先定义的符号来代表整棵树，从而提高了压缩比。 顺便要指出的是，小波图像系数结构的形式不只是上面介绍的一种，也可能不是最好的 一种
第4章小波图像编 (a)非零树例子 (b)零树例子 图4-08非零树与零树的概念 2.扫描方法 ZW算法对小波系数的进行编码的次序叫做扫描。扫描子图像系数的方法有两种,一种 叫做光栅扫描( raster scan),如图4-09(a)所示,另一种叫做迂回扫描( morton scan),如图409(b) 所示。 (a)光栅扫描 (b)迂回扫描 图4-09小波变换系数扫描方法 3.算法 EZW算法可粗略地归纳为下面几个主要步骤 (1)阈值T的选择 开始时的阈值石通常按下式估算 T=2Llog:(MAX(,D)J 其中,MAX()表示最大的系数值,X表示小波变换分解到第i级时的系数。以后每扫描一 次,阈值减少一半。 (2)给系数分配符号 使用w算法编码图像时每一次扫描需要执行两种扫描,并产生两种输出的符号。第一 种扫描叫做主扫描( dominant pass),它的任务是把小波系数X与阈值T进行比较,然后指定 表4-1中的4个符号之一,笔者把这种符号叫做系数符号,对整幅图像扫描之后产生系数符号 序列。第二种扫描叫做辅扫描( subordinate pass),其仼务是对主扫描取出的带有符号P或者N 的系数进行量化,产生代表对应量化值的符号“0”和“1”,笔者把这种符号称为量化符号。 主扫描:扫描每一个系数以产生系数符号 >如果系数幅度大于阈值(T)且为正数,输出符号P( positive)
第4章 小波图像编码 7 (a) 非零树例子 (b) 零树例子 图4-08 非零树与零树的概念 2. 扫描方法 EZW算法对小波系数的进行编码的次序叫做扫描。扫描子图像系数的方法有两种，一种 叫做光栅扫描(raster scan)，如图4-09(a)所示，另一种叫做迂回扫描(morton scan)，如图4-09(b) 所示。 (a) 光栅扫描 (b) 迂回扫描 图4-09 小波变换系数扫描方法 3. 算法 EZW算法可粗略地归纳为下面几个主要步骤。 (1) 阈值 T 的选择 开始时的阈值T0 通常按下式估算， log (MAX(| |)) Xi T = 2 0 2 其中，MAX(.)表示最大的系数值， Xi 表示小波变换分解到第i 级时的系数。以后每扫描一 次，阈值减少一半。 (2) 给系数分配符号 使用EZW算法编码图像时每一次扫描需要执行两种扫描，并产生两种输出的符号。第一 种扫描叫做主扫描(dominant pass)，它的任务是把小波系数 X 与阈值T 进行比较，然后指定 表4-1中的4个符号之一，笔者把这种符号叫做系数符号，对整幅图像扫描之后产生系数符号 序列。第二种扫描叫做辅扫描(subordinate pass)，其任务是对主扫描取出的带有符号P或者N 的系数进行量化，产生代表对应量化值的符号“0”和“1”，笔者把这种符号称为量化符号。 主扫描：扫描每一个系数以产生系数符号 ÿ 如果系数幅度大于阈值(T )且为正数，输出符号 P(positive)
第4章小波图像编 如果系数幅度小于阈值(T)且为负数,输出符号N( negative), 如果系数是零树根,输出T( zerotree), 如果系数幅度小于阈值但树中有大于阈值的子孙系数,输出孤立零符号Z( isolated zero 为了确定一个系数是否为零树根T或者是孤立零Z,需要对整个4叉树进行扫描,这样就 需要花时间。此外,为了保护己经被标识为零树的所有系数,需要跟踪它们,这就意味需要 存储空间来保存。最后要把绝对值大于阈值的系数取出来,并在图像系数相应的位置上填入 一个标记或者零,这样做可防止对它们再编码。 辅扫描:量化带符号P和N的系数 在量化系数之前要构造量化器。量化器的输入间隔为[T1,2T71),该间隔被1.5T1分 成两个部分:[T1,1571)和[15712T1),量化间隔为0.57-1,其中i为第i次编码。量 化器的输出为量化符号“0”和“1”,“0”对应量化值为(15-025)71,“1”对应量化 值为(1.5+025)T1° 例如,第一次扫描时的阈值T=32,量化器的间隔就为[32,64),该间隔[32,64)被 48分成两个相等的部分:[32,48)和[48,64),量化间隔为16。对系数进行量化时,如果幅 度在[32,48)的范围里,该系数的量化值为“0”,对应的量化值为(15-025)T=40 如果幅度在[48,64)的范围里,该系数的量化符号为“1”,它的量化值为 (1.5+025)70=56,详见图413。 8
第4章 小波图像编码 8 ÿ 如果系数幅度小于阈值(T )且为负数，输出符号 N(negative)， ÿ 如果系数是零树根，输出 T(zerotree)， ÿ 如果系数幅度小于阈值但树中有大于阈值的子孙系数，输出孤立零符号 Z(isolated zero)。 为了确定一个系数是否为零树根T或者是孤立零Z，需要对整个4叉树进行扫描，这样就 需要花时间。此外，为了保护已经被标识为零树的所有系数，需要跟踪它们，这就意味需要 存储空间来保存。最后要把绝对值大于阈值的系数取出来，并在图像系数相应的位置上填入 一个标记或者零，这样做可防止对它们再编码。 辅扫描：量化带符号P和N的系数 在量化系数之前要构造量化器。量化器的输入间隔为[ , ) T T i i - - 1 1 2 ，该间隔被1.5Ti -1 分 成两个部分：[ , . ) T T i i - - 1 1 1 5 和[ . , ) 1 5 2 T T i i - - 1 1 ，量化间隔为0.5Ti -1 , 其中i 为第i 次编码。量 化器的输出为量化符号“0”和“1”，“0”对应量化值为( . . ) 1 5 - 025 Ti -1 ，“1”对应量化 值为( . . ) 1 5 + 025 Ti-1 。 例如，第一次扫描时的阈值T0 = 32 ，量化器的间隔就为[32, 64) ，该间隔[32, 64) 被 48分成两个相等的部分：[,) 32 48 和[48, ) 64 ，量化间隔为16。对系数进行量化时，如果幅 度在[,) 32 48 的范围里，该系数的量化值为“0”，对应的量化值为(1.5 - = 0 2. ) 5 T0 40； 如果幅度在 [48, ) 64 的 范 围里，该系数的量化符号为“ 1 ”，它的量化值为 (1.5 + = 0 2. ) 5 T0 56 ，详见图4-13
第4章小波图像编码 表4-1EZW系数符号集 判断条件 输出符号 Ⅺ>T X>0 P( positive):表示正,重要系数 N(negative):表示负,不重要的系数 所有子孙系数X|<T, T:零树根,相对于阈值T为不重要系 <T X叫做零树的根 至少有一个子孙系数Z:孤立的零,相对于阈值T不重要系 X>T 43.3算法举例 为进一步理解EZW算法,综合了C. ValensI8]和在读博士生 Ghassan A-Regb9提供的 个例子[7。假设有一幅8×8的图像P,离散小波变换矩阵为W,经过小波变换之后的图像 为X=WP,小波图像系数X和扫描方式分别如图4-10a)和(b所示。另外还假设,图4-10a) 所示的数据是经过3级分解的小波图像系数。 713-127 3 14|-13346 59-14746 30-3232104 6 36 (a)小波图像数据 (b)迂回扫描 图4-108×8小波变换图像 1.树结构 为叙述方便,图4-10(a中的系数用组合符号(YM^YY)表示。最低分辨率子图像(即第3 级)中的每一个系数在高一级分辨率子图像(即第2级)中有3个子系数与它有关,它们之间构成 的树如图411(b)所示。说明如下 X1L3表示子带LL3的系数,它与第2级子图像中相关的子系数有3个:X/HL2, X/H2和XHH2。 X2/H3表示子带H3的系数,它与第2级子图像中相关的子系数有3个:X2/HL2, X2H2和X2HH2 X3LH3表示子带LH的系数,它与第2级子图像中相关的子系数有3个:X3/HL2, X3/H2和X3/HH2。 X4/HB表示子带HH3的系数,它与第2级子图像中相关的子系数有3个:X4HL2, X4/LH2和X4/HH2。 9
第4章 小波图像编码 9 表4-1 EZW系数符号集 判断条件 输出符号 X > 0 P(positive)：表示正，重要系数 X T > X < 0 N(negative)：表示负，不重要的系数 所有子孙系数 X T i < ， X 叫做零树的根 T：零树根，相对于阈值T 为不重要系 数 X T< 至少有一个子孙系数 X T i > Z：孤立的零，相对于阈值T 不重要系 数 4.3.3 算法举例 为进一步理解EZW算法，综合了C. Valens[8]和在读博士生Ghassan Al-Regib[9]提供的一 个例子[7]。假设有一幅8×8的图像 P ，离散小波变换矩阵为W ，经过小波变换之后的图像 为 X =WP ，小波图像系数 X 和扫描方式分别如图4-10(a)和(b)所示。另外还假设，图4-10(a) 所示的数据是经过3级分解的小波图像系数。 (a) 小波图像数据 (b) 迂回扫描 图4-10 8×8小波变换图像 1. 树结构 为叙述方便，图4-10(a)中的系数用组合符号(YM/YYN)表示。最低分辨率子图像(即第3 级)中的每一个系数在高一级分辨率子图像(即第2级)中有3个子系数与它有关，它们之间构成 的树如图4-11(b)所示。说明如下： ÿ X1/LL3 表示子带 LL3 的系数，它与第 2 级子图像中相关的子系数有 3 个：X1/HL2, X1/LH2 和 X1/HH2。 ÿ X2/HL3 表示子带 HL3 的系数，它与第 2 级子图像中相关的子系数有 3 个：X2/HL2, X2/LH2 和 X2/HH2。 ÿ X3/LH3 表示子带 LH3 的系数，它与第 2 级子图像中相关的子系数有 3 个：X3/HL2, X3/LH2 和 X3/HH2。 ÿ X4/HH3 表示子带 HH3 的系数，它与第 2 级子图像中相关的子系数有 3 个：X4/HL2, X4/LH2 和 X4/HH2
皮图像编 LL3 H3 HL2 HL1 HL3 3X4/|x3/×4x5X6 LH3 HH3 HL2 HL2 H1H1 x1/x2/x1/X2X09X10X11/×12x1 圖圖 x2/×2 LH2 LH2 HH2 HH2H1HL1HL1HL1 H2 LH2HH2 x3×4X3/x4/130142×15/16 LH2 LH2 HH2 HH2HL1HL1 HL1 HL1 X1/x/X3/4x/X2X3/X4 LHILHI LHI LHI HHI HHI HHI x5x6x7/x8/X5/x6 LHI LH1 LHI HH1 HHI HHI X09X0X182X09X101812 HI LH出HHH x3/x3/|x3X4 x3×4193634x56画画画[2 (a)8×8子图像小波变换系数(b)最低频带小波变换系数树 图4-11编码树的结构(1) 在其他子图像中,任何一个系数在高一级分辨率子图像中都有4个子系数与它有关,它 们之间构成的树如图4-12(b所示,图中只表示了一部分的树。从图中可以看到, XHL2表示子带H2的系数,它与第1级子图像中相关的子系数有4个:XlHL1 X2/HL1,X5/HL1和X6/HL X2H2表示子带H2的系数,它与第1级子图像中相关的子系数有4个:X3HL1, X4/HL1, X7/HLl FH X8/HLI X3HL2表示子带H2的系数,它与第1级子图像中相关的子系数有4个:XO9/HL X10/HL1, X13/HLl FH X14/HLl X4HL2表示子带H2的系数,它与第1级子图像中相关的子系数有4个:X1/HLl X12/HL1, X15/HLl FH X16/HLl H2 LH2HH2 HH2 HL1 HLI HI HLI x3/×4/ LH2 LH2 HH2 HH2 HLI HLI HLI HIHI HI HLI LHI LHI LHI HHIHHIHHI 圖圖画幽圖圖 FI x15 (a)8×8子图像小波变换系数(b)2级子图像小波变换部分系数树 4-12编码树的结构(2) 2.编码 根据对图像分辨率的要求,编码时可对小波图像系数进行多次扫描。每一次扫描包括主 扫描和辅扫描。 (1)第一次扫描: 步骤1:选择初始阈值。最大的系数为63,因此选择T=32
第4章 小波图像编码 10 (a) 8×8子图像小波变换系数 (b) 最低频带小波变换系数树 图4-11 编码树的结构(1) 在其他子图像中，任何一个系数在高一级分辨率子图像中都有4个子系数与它有关，它 们之间构成的树如图4-12(b)所示，图中只表示了一部分的树。从图中可以看到， ÿ X1/HL2 表示子带 HL2 的系数，它与第 1 级子图像中相关的子系数有 4 个：X1/HL1, X2/HL1, X5/HL1 和 X6/HL1。 ÿ X2/HL2 表示子带 HL2 的系数，它与第 1 级子图像中相关的子系数有 4 个：X3/HL1, X4/HL1, X7/HL1 和 X8/HL1。 ÿ X3/HL2 表示子带 HL2 的系数，它与第 1 级子图像中相关的子系数有 4 个：X09/HL1, X10/HL1, X13/HL1 和 X14/HL1。 ÿ X4/HL2 表示子带HL2的系数，它与第 1 级子图像中相关的子系数有 4 个：X11/HL1, X12/HL1, X15/HL1 和 X16/HL1。 (a) 8×8子图像小波变换系数 (b) 2级子图像小波变换部分系数树 图4-12 编码树的结构(2) 2. 编码 根据对图像分辨率的要求，编码时可对小波图像系数进行多次扫描。每一次扫描包括主 扫描和辅扫描。 (1) 第一次扫描： 步骤1: 选择初始阈值。最大的系数为63，因此选择T0 = 32