《多媒体技术讲座之小波图像编码.ppt》由会员分享，可在线阅读，更多相关《多媒体技术讲座之小波图像编码.ppt（50页珍藏版）》请在金锄头文库上搜索。
1、多媒体技术基础多媒体技术基础( (第第3 3版版) )第第8章章 小波图像编码小波图像编码 林福宗林福宗清华大学清华大学 计算机科学与技术系计算机科学与技术系2008年年9月月第8章 小波图像编码目录 8.1 从子带编码到小波编码从子带编码到小波编码8.1.1 子带编码8.1.2 多分辨率分析8.1.3 滤波器组与多分辨率8.1.4 子带编码与小波编码8.1.5 小波分解图像方法8.2 PSNR失真度量法失真度量法8.3 EZW编码编码8.3.1 介绍8.3.2 算法8.3.3 算法举例8.4 SPIHT编码编码8.4.1 介绍8.4.2 渐进图像的传输8.4.3 分集排序算法8.4.4 类型
2、和变量8.4.5 算法8.4.6 算法举例8.5 EBCOT编码简介编码简介8.5.1 介绍8.5.2 质量层的概念8.6 JPEG 2000简介简介8.6.1 JPEG 2000是什么8.6.2 JPEG 2000的基本结构8.6.3 JPEG 2000的主要功能8.6.4 JPEG 2000标准的文档8/6/20242第8章 小波图像编码8.1 从子带编码到小波编码从子带编码到小波编码 n子带编码子带编码子带编码(subband coding，SBC)的基本思想n把信号的频率分成几个子带，对每个子带分别进行编码n根据每个子带的重要性分配不同的位数来表示数据子带编码的应用n20世纪70年代，
3、开始用于语音编码n20世纪80年代，开始用于图像编码子带分割方法n1986年Woods, J. W.等人曾经使用一维正交镜像滤波器(QMF)把信号的频带分解成4个相等的子带，如图8-1所示n图8-1(a)表示分解方法，图8-1(b)表示其相应的频谱u符号：2表示频带降低1/2，HH表示频率最高的子带，LL表示频率最低的子带n这个过程可以重复，直到符合应用要求为止n滤波器组称为分解滤波器树(decomposition filter trees) 8/6/20243第8章 小波图像编码8.1 从子带编码到小波编码从子带编码到小波编码(续续1)图8-1 Lena图的子带编码8/6/20244第8章
4、小波图像编码8.1 从子带编码到小波编码从子带编码到小波编码(续续2)n多分辨率分析多分辨率分析S.Mallat于1988年在构造正交小波基时提出了多分辨率分析(multiresolution analysis)的概念，从空间上形象地说明了小波的多分辨率的特性，提出了正交小波的构造方法和快速算法，称为Mallat算法。根据Mallat和Meyer等科学家的理论，使用一级小波分解方法得到的图像如图8-2所示 图8-3 Lena的多分辨率分析图像 8/6/20245第8章 小波图像编码8.1 从子带编码到小波编码从子带编码到小波编码(续续3)一级分解后继续分解的过程叫做多分辨率分析，即多级小波分解
5、的概念。n使用多级小波分解可得到分辨率不同的图像，这些图像被称为多分辨率图像(multiresolution images)n图8-3表示Lena的多分辨率图像。其中，粗糙图像1的分辨率是原始图像的1/4，粗糙图像2的分辨率是粗糙图像1的1/4 图8-3 Lena的多分辨率分析图像 8/6/20246第8章 小波图像编码8.1 从子带编码到小波编码从子带编码到小波编码(续续4)n小波分解图像方法小波分解图像方法 使用小波变换把图像分解成各种子带的方法有很多种。例如，n均匀分解(uniform decomposition)n非均匀分解(non-uniform decomposition)n八带分
6、解(octave-band decomposition)n小波包分解(wavelet-packet decomposition)n根据不同类型的图像选择不同小波的自适应小波分解(adaptive wavelet decomposition)等八带分解是使用最广泛的一种分解方法n属于非均匀频带分割方法，它把低频部分分解成比较窄的频带，而对每一级分解的高频部分不再进一步分解n图8-4表示Lena图像的数据分解 8/6/20247第8章 小波图像编码8.1 从子带编码到小波编码从子带编码到小波编码(续续5)图8-4 Lena图像的数据分解 8/6/20248第8章 小波图像编码Standard te
7、st imagenLenna Soderberg(ne Sjblom)The First Lady of the Internet Size：512512 pixelsColors：24 bits/pixelLena24.bmp: 768 KBhttp:/www.cis.rit.edu/cnspci/misc/lenna/In 19728/6/20249第8章 小波图像编码Standard test image(contd 1)nLenna Soderberg (Sjblom) and Jeff Seideman In May 1997 at IS&Ts (Imaging Science an
8、d Technology)50th Anniversary conferencehttp:/www.cis.rit.edu/cnspci/misc/lenna/8/6/202410第8章 小波图像编码Standard test image(contd 2)nGirl (Tiffany)Sizen512512 pixels Colorn24 bits/pixeltiffany24.bmpn768 KBhttp:/sipi.usc.edu/database/8/6/202411第8章 小波图像编码Standard test image(contd 3)nMandrill(a.k.a. Baboon
9、)Sizen512512 pixels, Color n24 bits/pixelmandrill24.bmp n768 KBhttp:/sipi.usc.edu/database/8/6/202412第8章 小波图像编码Standard test image(contd 4)nPeppersSizen512x512 pixels Color n24 bits/pixelpeppers24.bmpn768 KBhttp:/sipi.usc.edu/database/8/6/202413第8章 小波图像编码Standard test image(contd 5)nElaineSizen51251
10、2 pixelsGrayscalen8 bits/pixelElaine8.bmpn256 KBhttp:/sipi.usc.edu/database/8/6/202414第8章 小波图像编码Standard test image(contd 6)nBarbaraSizen512512 pixelsGrayscalen8 bits/pixelbarbara8.bmpn256 KB8/6/202415第8章 小波图像编码Standard test image(contd 7)nGoldhillSizen512512 pixelsGrayscalen8 bits/pixelgoldhill8.bm
11、pn256 KB8/6/202416第8章 小波图像编码8.2 图像失真度量法图像失真度量法n峰值信号噪声比峰值信号噪声比(PSNR)在图像编码系统中，常用峰值信号噪声比(peak signal to noise ratio, PSNR)来衡量最大像素值的平方与均方差(mean square error，MSE)之比5对8位二进制图像： 其中，为原始图像的像素值 为解压缩之后的像素值 8/6/202417第8章 小波图像编码8.2 图像失真度量法图像失真度量法(续续)n其他方法其他方法规格化均方差(normalized mean square error，NMSE)信号噪声比(signal t
12、o noise ratio，SNR)平均绝对误差(mean absolute error，MAE)8/6/202418第8章 小波图像编码Entropy Coding of Wavelet CoefficientsnEZW Shapiro-1993Embedded Zerotree Coding of Wavelet CoefficientsnSPIHT Said-Pearlman-1996Set Partitioning in Hierarchical TreesnEBCOT Taubman-1998Embedded Block Coding with Optimal TruncationA
13、dopted by JPEG 20008/6/202419第8章 小波图像编码8.3 EZW编码编码nEZW是什么是什么embedded zerotree wavelet的缩写EZW是多分辨率图像编码算法nLewis，A. S.和Knowles, G.于1992年介绍了表示小波变换系数的一种树形数据结构6；nShapiro, J. M.于1993年将这种树形数据结构称为“零树(zerotree)”，并开发了称为嵌入式零树小波(embedded zerotree wavelet，EZW)的图像编码算法7，用于熵编码图8-5 EZW算法结构8/6/202420第8章 小波图像编码8.3 EZW编码
14、编码(续续1)EZW(嵌入式零树小波)图像编码概要n“小波”表示该算法以离散小波变换为基础，以变换后的大系数比小系数更重要以及高频子带中的小系数可以忽略为背景n“零树”表示小波变换系数之间的数据结构，用同一方向和相同空间位置上的所有小波系数构成一棵树，如果树根及其子孙的小波系数的绝对值小于某个给定域值，则这棵树就称为零树n“嵌入”表示一幅图像可以分解成一幅低分辨率图像和分辨率由低到高的许多子图像n按用户对图像分辨率的不同要求， EZW编码器进行多次编码，每进行一次编码，域值降低1/2，水平和垂直方向的图像分辨率分别提高1倍8/6/202421第8章 小波图像编码8.3 EZW编码编码(续续2)
15、n编码从最低分辨率图像开始u幅度大于域值的正系数用符号P表示u幅度小于域值的负系数用符号N表示u树根节点上的系数幅度小于域值而树枝中有大于域值的非零树用符号Z表示u零树用符号T表示n编码输出u符号集P，N，T，Z，0，1中的一系列符号 n对整幅图像编码一次，生成一种分辨率图像在扫描过程中需维护两种表n小波系数的符号表n量化表8/6/202422第8章 小波图像编码8.3 EZW编码编码(续续3)n标记标记 小波变换后的系数、名称和符号，以三级小波分解为例，见图8-6图中的数字1、 2和3表示分解的级数编号LL3表示第3级的低频子图像HL3表示第3级分解在水平方向上的子图像LH3表示第3级分解在
16、垂直方向上的子图像HH3表示第3级分解在对角线方向上的子图像其他的组合符号依此类推图8-6 Lena三级分解图像 8/6/202423第8章 小波图像编码8.3 EZW编码编码(续续4)n系数树系数树各级子图像中的系数之间的关系可用树的形式描述，见图8-7(a)最低频率的子图像在左上角，最高频率的在右下角由同一方向和相同空间位置上的所有小波系数组成一棵树n例如，从第三级子图像HH3、第二级子图像HH2到第一级子图像HH1的相应位置上的所有系数构成一棵下降树(a)构造方法图8-7 EZW编码树的构造8/6/202424第8章 小波图像编码8.3 EZW编码编码(续续5)按箭头所指的方向，各级系数
17、的名称分别用祖系数、父系数、子系数和孙系数来称呼 n例如，LL3的系数为63, HH2和HH1的系数分别为3和4, 6, 3, -2, 由这些系数构成的树见图8-7(b)。如果把63指定为父系数，3就称为子系数，而4, 6, 3, -2中的4个系数就称为孙系数图中有两棵树n图8-8(a)：非零树n图8-8(b)：零树(b) 小波系数举例图8-7 EZW编码树的构造8/6/202425第8章 小波图像编码8.3 EZW编码编码(续续6)n零树零树假设编码开始时的阈值为T0=32，由于63比32大，这样的树称为非零树，见图8-8(a)假设下次编码时的阈值为T1=16 ，把-13当作父系数，它的幅度
18、比16小，而它的所有4个子系数的幅度都比16小，这种树称为零树，见图8-8(b)，系数-13称为零树根定义零树的目的n可用一个预先定义的符号表示，从而可提高压缩比 8/6/202426第8章 小波图像编码8.3 EZW编码编码(续续7)n扫描方法扫描方法对小波系数进行编码的次序叫做扫描，两种方法n光栅扫描(raster scan)，见图8-9(a)n迂回扫描(morton scan)，见图8-9(b)(a) 光栅扫描 (b) 迂回扫描图8-9 小波变换系数扫描方法8/6/202427第8章 小波图像编码8.3 EZW编码编码(续续8)n 算法算法 阈值阈值T的选择的选择n初始阈值：其中,表示其
19、值为等于或小于x的最大整数(x)MAX(.)表示最大的系数值，表示小波变换分解到第i级时的系数以后每扫描一次，阈值减少一半 8/6/202428第8章 小波图像编码8.3 EZW编码编码(续续9)给系数分配符号给系数分配符号n每一次扫描需执行两种扫描并产生两种输出符号u主扫描(dominant pass)：将小波系数与阈值进行比较，指定表8-1中的4个系数符号之一 。产生系数符号序列u辅扫描(subordinate pass)：把主扫描取出的带符号P或N的系数进行量化，产生对应量化值的量化符号“0”或“1”8/6/202429第8章 小波图像编码8.3 EZW编码编码(续续10)表8-1 EZ
20、W系数符号集8/6/202430第8章 小波图像编码8.3 EZW编码编码(续续11)(1) 主扫描：扫描每一个系数以产生系数符号n如果系数幅度大于阈值(T)且为正，输出符号P(positive)，n如果系数幅度的绝对值大于阈值(T)且为负，输出符号N(negative)n如果系数是零树根，输出T(zerotree)n如果系数幅度小于阈值但树中有大于阈值的子孙系数，输出孤立零符号Z(isolated zero)8/6/202431第8章 小波图像编码8.3 EZW编码编码(续续12)(2) 辅扫描：量化带符号P和N的系数n在量化系数之前要构造量化器u量化器的输入间隔为Ti-1, 2Ti-1)，
21、该间隔被1.5Ti-1分成两个部分：Ti-1，1.5Ti-1)和1.5 Ti-1, 2 Ti-1)，量化间隔为0.5 Ti-1, 其中i为第i次编码u量化器的输出为量化符号“0”和“1”，“0”对应量化值为(1.5-0.25) Ti-1, “1”对应量化值为(1.5+0.25) Ti-1 n例如，第一次扫描时的阈值T0=32，量化器的间隔就为32，64)，该间隔32，64)被48分成两个相等的部分：32，48)和48，64)，量化间隔为16。对系数进行量化时，如果幅度在32，48)的范围里，该系数的量化值为“0”，对应的量化值为(1.5-0.25)T0=40；如果幅度在48，64)的范围里，该
22、系数的量化符号为“1”，它的量化值为(1.5+0.25)T0=56，详见图8-13。8/6/202432第8章 小波图像编码8.3 EZW编码编码算法举例算法举例 n实例实例假设有一幅88的图像，经过3级分解的小波图像系数见图8-10(a)，扫描方式见 8-10(b)(a) 小波图像数据 (b) 迂回扫描图8-10 88小波变换图像8/6/202433第8章 小波图像编码8.3 EZW编码编码算法举例算法举例(续续1)n树结构树结构图8-10(a)中最低分辨率子图像(即第3级)中的每一个系数在高一级分辨率子图像(即第2级)中有3个子系数，它们之间构成的树见图8-11(b) (a) 88子图像小
23、波变换系数 (b) 最低频带小波变换系数树图8-11 编码树的结构(1)8/6/202434第8章 小波图像编码8.3 EZW编码编码算法举例算法举例(续续2)在其他子图像中，任何一个系数在高一级分辨率子图像中都有4个子系数与它有关，它们之间构成的树见图8-12(b)，图中只表示了一部分的树 (a) 88子图像系数 (b) 2级子图像部分系数树图8-12 编码树的结构(2) 8/6/202435第8章 小波图像编码8.3 EZW编码编码算法举例算法举例(续续3)n第第1次扫描次扫描 步骤步骤1: 最大的系数为63，因此选择T0=32步骤步骤2: 指定系数的符号n存放系数符号的缓存为D1n每个系
24、数与阈值32比较。当系数为符号T时，其所有子孙系数就不再扫描，并用“”表示，比较结果见图8-13(a)nD1中的系数符号: P N T T P T T Z T T T T T T T P T T(a) 系数符号和标记 (b)系数量化图8-13 第一次主扫描8/6/202436第8章 小波图像编码8.3 EZW编码编码算法举例算法举例(续续4)步骤步骤3: 对带符号P/N的系数进行量化n存放量化符号的缓存为S1n阈值T0=32，大于32的4个系数为63，34，49，47n用48把间隔32，64)分成两部分，见图8-13(b)。幅度在 32，48)中的系数指定其符号为“0”, 幅度在48，64)中
25、的系数指定其符号为“1”，这4个系数的量化符号见表8-2n由于解码器重构的系数幅度按(1.5+0.25)T进行计算，因此重构数据的绝对误差在17之间，即小于0.25Tn系数63-P, 34-N, 49-P, 47-P 在 S1中的量化符号：1 0 1 0系数幅度量化符号重构幅度63156340404915647040表表8-2 8-2 第一次辅扫描量化表第一次辅扫描量化表 8/6/202437第8章 小波图像编码8.3 EZW编码编码算法举例算法举例(续续5)步骤步骤4：重新排列带P/N符号的数据。n为便于设置第二次扫描时所用的量化间隔，以提高解码的系数精度。把系数集63-P, 34-N, 4
26、9-P, 47-P排列成63-P, 49-P, 34-N, 47-P步骤步骤5：输出编码信息n编码器输出两类信息，一类是给解码器的系数符号系列等信息，另一类是用于下一次扫描的阈值和大于阈值的系数值等信息。n用于给解码器的系数符号系列等信息包含三种：uHEADER (即T0=32 ), D1: P N T T P T T Z T T T T T T T P T T “AND” S1: 1 0 1 0n用于下次扫描的阈值和大于阈值的系数值等信息包含三种：uT0=32, 63-P, 49-P, 34-N, 47-P “AND”子带图像n第第2次扫描（略）次扫描（略） 8/6/202438第8章 小波
27、图像编码8.3 EZW编码编码算法举例算法举例(续续6)n解码解码EZW的解码过程是EZW编码的逆过程，编码时扫描多少次，解码时也可以解多少次解码过程大致分为三个步骤n解码器设置阈值n构造逆量化器n开始解读位流中包含的位置和小波系数值注意n解码时用的逆量化器与编码时用的量化器相同，因此简称为量化器n像编码时那样，每次解码都需要构造量化器 8/6/202439第8章 小波图像编码8.3 EZW编码编码算法举例算法举例(续续7)n第第1次解码次解码解码器开始时的阈值T0=32 ，接收到来自编码器第一次扫描输出的系数符号为 P N T T P T T Z T T T T T T T P T T /
28、1 0 1 0量化符号与系数符号之间有如下的对应关系 D1PNTTPTTZTTTTTTTPTTS110108/6/202440第8章 小波图像编码8.3 EZW编码编码算法举例算法举例(续续8)按照编码时的扫描和量化方法进行解码。n第1个系数符号是P，对应的量化符号位是“1”，因此第1个系数是56n第2个系数符号是N，对应的量化符号位是“0，因此第2个系数是-40n第3个系数符号是T，在相应的图像系数位置上用“0”表示它的系数nn第一次解码的结果见图8-16u用“0”表示的系数已经扫描过，它们对应符号T或者Zu用“”表示的系数不需要扫描，是零树根的子孙 8/6/202441第8章 小波图像编码
29、8.3 EZW编码编码算法举例算法举例(续续9)在第一次解码之后，解码器需要判断是否要进一步重构比较精细的图像n如果不需要，则退出解码n如果需要则进入第二次解码图8-16 第一次解码8/6/202442第8章 小波图像编码8.3 EZW编码编码算法举例算法举例(续续10)n第二次解码第二次解码分两步n提高第一次解码时得到的系数精度n求解未解码的系数使用编码器生成的第二次编码时的信息nD2: N P T T T T T T T T T T T T T T TnS2： 1 0 0 1 1 0解码结果见图8-17下一步确定是否继续进行解码以得到更精细的图像。n如果要退出，则把两次解码的结果合成之后就
30、可退出n如果继续，则进入第三次解码 8/6/202443第8章 小波图像编码8.3 EZW编码编码算法举例算法举例(续续11)图8-17 第二次解码 8/6/202444第8章 小波图像编码8.4 SPIHT编码编码 nSPIHT简介简介set partitioning in hierarchical trees的缩写Amir Said和William Pearlman于1996年对EZW的改进算法10，称为“层树分集”算法具有人们所期望的特性，例如，n图像的渐进传输；比较高的PSNR；复杂度比较低；计算量比较少；位速率容易控制等算法依据n经过小波变换后，图像的大部分能量都集中在低频子带编码方
31、法n最先传送幅度大的系数，解码器即使在低速率应用环境下也可得到图像的大部分信息n编码树的结构与EZW算法的结构类似，每一个节点要么没有子节点，要么有4个子节点n在编码过程中用三个变量列表存储重要系数和不重要系数n算法和举例请看教材算法和举例请看教材8.4 8/6/202445第8章 小波图像编码8.5 EBCOT编码编码nEBCOT介绍介绍embedded block coding with optimized truncation的缩写，可译成“最佳截断嵌入码块编码” ；David Taubman在1999年发表的编码算法12 对小波变换后的子带系数进行量化和编码的方法。n把每一个子带的小波
32、变换系数分成独立编码的码块(code-block)，并且对所有的码块使用完全相同的编码算法n见图8-21：图(a)表示使用小波变换进行三级分解之后的图像子带；图(b)表示经过这种变换之后各个子带的Lena图像每个码块的编码只用码块自身的信息产生单独的嵌入位流(bitstream)每个码块的嵌入位流可被“截断”成长度不等的位流，生成不同的位速率8/6/202446第8章 小波图像编码“最佳”截断：给定目标位速率，每个码块的嵌入位流应使重构图像的失真程度最小(a) 图像子带划分法 (b) Lena图像子带图8-21 独立编码的码块 8/6/202447第8章 小波图像编码第第8章章 小波图像编码小
33、波图像编码(参考文献参考文献)n参考文献和站点参考文献和站点1.Daubechies, I., Orthonormal Bases of Compactly Supported Wavelets, Comm. Pure and Applied Math., vol. 41, Nov. 1988, pp. 909-9962.A. Cohen, I. Daubechies and J.C.Feauveau. Biorthogonal bases of compactly supported wavelets. Communications on Pure and Applied Mathemati
34、cs, 45(5)：485-560, June 19923.Wim Sweldens，The Construction and Application of Wavelets in Numerical Analysis，May 18, 19954.Sweldens, W. The Lifting Scheme: A Construction Of Second Generation Wavelets. Siam J. Math. Anal, Vol. 29, No. 2, 19975.A. K. Jain, Fundamentals of Digital Image Processing, P
35、rentice-Hall, Englewood Cliffs, New Jersey, 1989.6.Lewis, A. S. and Knowles, G. Image Compression Using the 2-D Wavelet Transform, IEEE Trans. IP, vol. 1, no. 2, April 1992, pp. 244-250.7.Shapiro, J. M. Embedded Image Coding Using Zerotrees of Wavelet Coefficients, IEEE Trans. SP, vol. 41, no. 12, D
36、ec. 1993, pp. 3445-34628.Clemens Valens homepage, http:/perso.wanadoo.fr/polyvalens/clemens/clemens.html9.Ghassan Al-Regib, Embedded Zerotree Wavelet Encoding (EZW) Based on Sharipos Paper, 04/05/2000, Georgia Institute of Technology, Atlanta, GA8/6/202448第8章 小波图像编码第第8章章 小波图像编码小波图像编码(参考文献续参考文献续)n参考文
37、献和站点参考文献和站点(续续)10.A. Said and W. Pearlman, A new, fast and efficient image codec based on set partitioning in hierarchical trees, IEEE Trans. Circuits System, Video Technology, vol. 6, pp. 243250, June 199611.Agnieszka C. Miguel，Teaching Notes, Set Partitioning in Hierarchical Trees (SPIHT), 1999. h
38、ttp:/dcl.ee.washington.edu/amiguel/amiguel.html 12.David Taubman, High performance scalable image compression with EBCOT, Image Processing, IEEE Transactions on , Volume: 9 Issue: 7 , July 2000, Page(s): 1158 - 117013.M. Antonini, M. Barlaud, P. Mathieu and I. Daubechies: Image Coding Using Wavelet
39、Transform, IEEE Trans. Image Proc., pp. 205-220, April 199214.C. Christopoulos, A. Skodras and T. Ebrahimi, The JPEG 2000 still image coding system: An Overview, IEEE Transactions on Consumer Electronics, 2000, Vol 46, No. 4, pp. 1103-1127, November 2000. 15.JPEG 2000，Our new standard!, http:/www.jp
40、eg.org/jpeg2000/index.html16.Vetterli, M. and Herley, C., Wavelets and Filter Banks: Theory and Design, IEEE Trans. SP, vol. 40, no. 9, Sep. 1992, pp. 2207-2232.17.Ramchandran, K., Vetterli, M., Herley, C.，Wavelets, subband coding, and best bases，Proceedings of the IEEE , Volume: 84 Issue: 4 , April 1996，Page(s): 541 -56018.Ingrid Daubechies，Wim Sweldens，Factoring Wavelet Transforms into Lifting Steps，J. Fourier Anal. Appl., Vol. 4, Nr. 3, pp. 247-269, 1998 8/6/202449第8章 小波图像编码ENDEND第第8章章 小波图像编码小波图像编码
