1、数字图像处理数字图像处理Digital Image ProcessingDigital Image Processing目目 录录1.概论2.数字图像处理基础3.图像增强4.图像的几何变换5.频域处理6.数学形态学基础7.图像分割8.图像特征与理解9.图像编码10.图像复原第九章第九章 概论概论1.图像编码概述2.哈夫曼编码3.香农-范诺编码4.算术编码5.行程编码6.LZW编码7.JPEG2000编码9.1 图像图像编码概述编码概述n 图像编码基本原理与方法n 1.图像数据冗余 图像数据通常包含有大量冗余信息，为图像压缩提供了依据。图像压缩又称图像编码，目的就是充分利用图像中存在的各种冗余信
2、息，在图像重建质量可以接受的前提下，通过编码实现以尽量少的比特数来表示图像。图像数据的冗余形式主要有空间冗余空间冗余、时间冗余时间冗余、信信息熵冗余息熵冗余、结构冗余结构冗余、知识冗余知识冗余和视觉冗余视觉冗余。9.1 图像图像编码概述编码概述n 图像编码基本原理与方法n 1.图像数据冗余空间冗余：指图像内部相邻像素之间存在较强的相关性而造成的冗余。时间冗余：是指图像序列中的相邻两帧之间存在较强的相关性而造成的冗余。信息熵冗余：也称编码冗余，是指用于表示信源符号的平均比特数大于其信息熵时所产生的冗余。结构冗余：是指图像中存在较强的纹理结构或自相似性，如布纹图像、墙纸图案等。知识冗余：是指图像中
3、包含与某些先验知识有关的信息。视觉冗余：是指人眼不能感知或不敏感的那部分图像信息。9.1 图像图像编码概述编码概述n 图像编码基本原理与方法n 2.图像编码方法 根据编码过程中是否存在信息损耗可将图像编码方法分为有损编码和无损编码。无损编码又称无失真编码或信息保持编码或可逆编码，解码时能够从压缩数据精确地恢复原始图像。有损编码又称有失真编码或保真度编码或不可逆编码，不能从压缩数据精确重建原始图像，存在一定程度的失真。无损编码的压缩比较低，主要应用于医学图像等数据质量要求较高的场合。有损编码允许在一定的保真度准则下，最大限度地压缩图像，可以实现较大的压缩比，主要用于数字电视技术、静止图像、通信、
4、娱乐等方面。9.1 图像图像编码概述编码概述n 图像编码基本原理与方法n 2.图像编码方法熵编码：熵编码是一种基于信号统计特性的编码技术，要求编码过程中按熵原理不丢失任何信息，是一种无损编码。预测编码：预测编码是基于图像数据的空间或时间冗余特性，用相邻的已知像素（或像素块）来预测当前像素（或像素块）的取值，然后再对预测误差进行量化和编码。无损预测编码系统9.1 图像图像编码概述编码概述n 图像编码基本原理与方法n 2.图像编码方法变换编码：变换编码通常是将空间域上的图像经过正交变换映射到另一变换域上，使变换后的系数之间的相关性降低。量化编码：量化编码就是通过将动态范围内较大的输入信号值映射到有
5、限个离散值来实现数据压缩，是个不可逆过程。变换编码系统9.1 图像图像编码概述编码概述n 图像编码新技术n 新的图像编码方法，子带编码：子带编码是一种在频率域中进行数据压缩的方法。首先用一组带通滤波器将输入信号分成若干个不同频段的子带信号，然后经过频率搬移将子带信号转变成基带信号，再对它们在奈奎斯特速率上分别重新取样，最后对取样后的信号进行量化编码，并合并成一个总的码流传送给接收端。分形编码：分形编码最大限度地利用了图像在空间域上的自相似性（即局部与整体之间存在某种相似性），通过消除图像的几何冗余来压缩数据。9.1 图像图像编码概述编码概述n 图像编码新技术n 新的图像编码方法，小波编码：经过
6、小波变换后的图像，具有良好的空间方向选择性，且为多分辨率，能够保持原图像在各种分辨率下的精细结构，与人的视觉特性十分吻合。模型编码：模型编码是近年发展起来的一种低比特率编码方法，其基本出发点是在编、解码两端分别建立起相同的模型，编码时利用先验模型抽取图像中的主要信息并用模型参数的形式表示，解码时则利用所接收的模型参数重建图像。9.1 图像图像编码概述编码概述n 图像编码评价n 图像编码算法的优劣主要从编码效率、编码质量、算法复杂度及适用范围等方面进行评判。编码效率：衡量图像编码效率的指标主要有：平均码字长度（L），压缩比（CR），编码效率（）。编码质量：图像的编码质量是指解压后的重建图像与压缩
7、前的原始图像之间的相似度，可分为主观质量评价和客观质量评价。主观质量评价是指由一批观察者对编码图像进行观察并打分，然后综合所有人的评判结果，给出图像的质量评价。9.1 图像图像编码概述编码概述n 图像编码评价n 图像编码算法的优劣主要从编码效率、编码质量、算法复杂度及适用范围等方面进行评判。算法的复杂度：图像编码算法的复杂度是指完成图像压缩和解压所需的运算量以及实现该算法的难易程度。优秀的压缩算法除了要求有较高的编码效率和编码质量外，还要求算法简单、易于实现，压缩和解压缩快。算法的适用范围：特定的图像编码算法具有其相应的适用范围，并非对所有图像都有效。一般说来，大多数基于图像信息统计特性的压缩
8、算法具有较广的适用范围，而一些特定的编码算法的适用范围较窄，如分形编码主要用于自相似性高的图像。9.2 哈夫曼哈夫曼编码编码n 哈夫曼编码，又称为最佳编码，是Huffman于1952年依据变长最佳编码定理提出的一种无损编码方法。n 由于一般无法事先知道信源的概率分布，通常采用对大量数据进行统计后得到的近似分布来代替，这样会导致实际应用时哈夫曼编码无法达到最佳性能。通过利用输入数据序列自适应地匹配信源概率分布的方法，可以有效改进哈夫曼编码的性能。9.2 哈夫曼哈夫曼编码编码n 举例:设一幅灰度级为8的图像，灰度S0、S1、S2、S3、S4、S5、S6、S7出现的概率分别为0.40、0.18、0.
9、10、0.10、0.07、0.06、0.05、0.04。如果编码之前采用等长编码，由于有8种灰度级，则每种灰度级别至少需要3比特来表示。其哈夫曼编码过程及结果如下图所示：9.2 哈夫曼哈夫曼编码编码n 哈夫曼编码形成的码字是可识别的，即能够保证一个符号的码字不会与另一个符号的码字的前几位相同。比如说，如果S0的码字为1，S1的码字为01，而S2的码字为011，则当编码序列中出现011时，就不能判别它是S2的码字还是S1的码字后面跟了一个S0的码字。n 上例的信息熵H、平均码长L、编码效率和压缩比CR如下：21log2.55NiiiHpp 10.40 1 0.18 30.10 30.10 40.
10、07 40.06 40.05 50.04 52.61NiiiLp L /100%2.55/2.61 100%97.8%HL3 2.61 1.149RCB L9.2 哈夫曼哈夫曼编码编码n 哈夫曼编码的编码效率n根据信息论中信源编码理论，对于二进制编码，当信源概率为2的负幂时，哈夫曼编码的编码效率可达100%，其平均码字长度也很短，而当信源概率为均匀分布时，其编码效果明显降低。9.2 哈夫曼编码哈夫曼编码n 哈夫曼编码存在问题：n（1）虽然哈夫曼编码的码字可以识别，但是编码并不唯一，这是因为概率相等的2个符号的排序及其赋值“0”或“1”是随机的。n（2）变长编码导致硬件实现复杂，且抗误码能力弱，
11、也很难随意查找或调用压缩数据中间的内容。如果编码传输中有错误，哪怕是1位错误，也会引起一连串的错误。n（3）编码效率依赖于信源统计特性，需要有信源概率分布的先验知识，限制了哈夫曼编码的应用。9.3 香香农农-范诺编码范诺编码n 香农-范诺（Shannon-Fano）编码也是一种基于统计的无损、变长编码算法，理论基础是符号的码字长度完全由该符号出现的概率来决定。9.3.1 香香农农-范诺编码的基本方法范诺编码的基本方法n 香农-范诺编码基本方法的步骤如下：(1)将信源符号按其出现概率pi从大到小排序，如S0,S1,SN。(2)计算出符号Si对应的码字长度Ni。(3)计算符号Si对应的累加概率Ai
12、。(4)将累加概率Ai由转换为二进制，取前Ni位作为信源符号Si的码字。9.3.1 香香农农-范诺编码的基本方法范诺编码的基本方法n 香农-范诺编码举例:n 以上例图像为对象，对其进行香农-范诺编码，编码过程及结果如下：。信源符号出现概率Pi码字长度Ni累加概率Ai转换为二进制分配码字BiS00.4020000S10.1830.4001100011S20.1040.58100101001S30.1040.68101001010S40.0740.78110001100S50.0650.85110110011011S60.0550.91111010011101S70.0450.9611110111
13、1110平均码长L=3.17图像熵H=2.55编码效率=80.4%表表9 9 2 2 香农香农-范诺编码过程及结果范诺编码过程及结果9.3.2 二分法二分法香农香农-范诺范诺编码方法编码方法n 二分法香农-范诺编码与哈夫曼编码相似，但采用从上到下的编码过程，步骤如下：（1）将信源符号按其出现概率从大到小排序。（2）将符号分成2组，使2组符号的概率和尽可能接近，将第1组标0，第2组标1。（3）重复步骤2，直到每组只有一个符号为止。（4）将每个符号所属组的值依次串起来，即可得到各个符号的香农-范诺编码。9.4 算术编码算术编码n 算术编码是80年代发展起来的一种熵编码方法，其基本原理是将被编码的整
14、个数据序列表示成实数0到1之间的一个间隔（或区间），在该间隔内选择一个代表性的二进制小数作为实际的编码输出。n 算术编码有2种模式：一种是基于信源概率统计特性的固定编码模式，另一种是针对未知信源概率模型的自适应模式。自适应模式中各个符号的概率初始值均相同，它们依据出现的符号而相应地改变。只要编码器和解码器均使用相同的初始值和改变值的方法，那么它们的概率模型将保持一致。9.4 算术编码算术编码n 固定模式的算术编码步骤如下：n（1）将数据序列的编码间隔L,H)初始化为0,1)，按照信源符号Si的概率pi成比例将其映射为0,1)上的子间隔Li,Hi)，子间隔之间互不重叠。n（2）从输入序列中按序取
15、走一个符号，依据该符号的出现概率如下更新间隔L,H)。计算间隔的长度：W=H L；更新间隔的上界和下界：H H+W*Hi，L L+W*Li。n（3）重复第2步，直到输入序列中没有符号为止。n（4）最后从间隔中选择一个数n（如间隔的下界）作为数据序列的编码输出。9.4 算术编码算术编码n 算术编码举例：n 设一待编码的数据序列为“dacab”，信源中各符号出现的概率依次为P(a)=0.4，P(b)=0.2，P(c)=0.2，P(d)=0.2。其算术编码过程如下图所示。算术编码过程示意图算术编码过程示意图9.5 行程编码行程编码n 行程编码（Run Length Encoding，RLE）是一种利
16、用空间冗余度的无损编码方法，在BMP、PCX、TIFF、PDF文件中均得到了应用。它将具有相同值的连续符号串用其串长和一个代表值来代替，该连续串就称之为行程，串长称为行程长度。n 行程编码比较适合于二值图像的编码，一般用于量化后出现大量零系数连续的场合，用行程来表示连零码。如果图像是由很多块颜色或灰度相同的大面积区域组成，那么，采用行程编码可以达到很高的压缩比。若图像中的数据非常分散，则行程编码不但不能压缩数据，反而会增加图像文件的大小。为了达到较好的压缩效果，一般不单独采用行程编码，而将其和其他编码方法结合使用。9.6 LZW编码编码n LZW（Lempel-Ziv&Welch）编码又称字串
17、表编码，属于一种无损编码，是Welch将Lempel和Ziv所提出的无损压缩技术改进后的压缩方法。LZW编码的基本思想是：在编码过程中，将所遇到的字符串建立一个字符串表（或称为词典），表中的每个字符串都对应一个索引（或称为码字），编码时用该字符串在字串表中的索引来代替原始的数据串。n GIF图像文件采用改良的LZW压缩算法，通常称为GIF-LZW压缩算法。GIF图像文件以块（又称为区域结构）的方式来存储图像相关的信息，具体的文件格式可参考图像文件格式的相关书籍。9.6 LZW编码编码n GIF-LZW的编码步骤如下：（1）根据图像中使用的颜色数初始化一个字串表，字串表中的每个颜色对应一个索引。
18、在初始字串表的末尾再添加两个符号LZW_CLEAR和LZW_EOI（分别为字符表初始化标志和编码结束标志）的索引。（2）设置字符串变量pF和cH并初始化为空，输出LZW_CLEAR在字串表中的索引。（3）从数据流中的第一个字符开始，依次读取一个字符，将其赋给cH。（4）判断pF+cH是否已存在于字串表中。如果已存在，则用cH扩展pF，即pF=pF+cH；否则，输出pF在字串表中的索引，并在字串表末尾为pF+cH添加索引，并令pF=cH。（5）重复第3和第4步，直到所有字符读完为止。（6）输出pF在字串表中的索引，然后输出结束标志LZW_EOI的索引，编码完毕。9.6 LZW编码编码n GIF-
19、LZW的解码过程和编码过程正好相反，即将编码后的码字转换成对应的字符串，重新生成字串表，然后依次输出对应的字符串即可。GIF-LZW的解码流程如下图所示，其中，Code和OldCode是两个存放索引的临时变量。GIF-LZW解码流程9.6 LZW编码编码n LZW编码实例n 设有一来源于4色（以a、b、c、d表示）图像的数据流：aabcabbbbd，对其进行LZW编码的过程如下：编码前，首先需要初始化一个字符串表。由于图像中只有4种颜色，因而，可以只用4比特表示字符串表中每个字符串的索引，表中的前4项代表4种颜色，后2项分别表示初始化和图像结束标志，建立的初始化字符串表如右表所示。字符串索引a
20、0 Hb1 Hc2 Hd3 HLZW_CLEAR4 HLZW_EOI5 H初始化初始化字符串表字符串表9.6 LZW编码编码n LZW编码实例n 设有一来源于4色（以a、b、c、d表示）图像的数据流：aabcabbbbd，对其进行LZW编码的过程如下：表 GIF-LZW编码示例输入数据cHpF+cH输出结果pF生成的新字符串及索引NULLNULL4HNULL aa a aaa0Haaa bab0Haab cbc1Hcbc aca2Haca bab ab babb7Hbabb bbb1Hbbb bbb bb dbbdBHdbbd 3H 5H 9.7 JPEG2000编码编码n 9.7.1 JPE
21、G2000概述n JPEG 2000是由联合图像专家组（Joint Photographic Experts Group）于2000年底推出的一种基于小波变换的静态图像压缩标准，具有广泛的应用前景。JPEG2000标准仍在不断发展和完善中，目前包括12部分，对应代号为ISO/IEC 15444-112，每一部分都在第1部分的基础上增加了新的特性。9.7 JPEG2000编码编码n 9.7.1 JPEG2000概述n JPEG 2000优点：n 良好的低比特率压缩性能n 连续色调和二值图像压缩n 有损和无损压缩n 按照像素精度或者分辨率进行渐进式传输n 随机访问和处理码流n 抗误码特性好n 大图
22、像和多分量图像n 固定速率、固定大小、有限的存储空间n 感兴趣区域编码9.7 JPEG2000编码编码n 9.7.2 JPEG2000核心编码系统n JPEG2000核心编码系统用离散小波变换（Discrete Wavelet Transform,DWT）和最优截断嵌入式块编码（Embedded Block Coding with Optimized Truncation,EBCOT）取代了JPEG基线编码系统中的离散余弦变换和哈夫曼编码，其编解码流程如图所示。JPEG2000核心编码系统编解码流程9.7 JPEG2000编码编码n 9.7.2 JPEG2000核心编码系统n 1.预处理：n(
23、1)图像分片:JPEG2000允许将图像按网格形式分割成若干互不重叠、任意尺寸的矩形块图像片或拼接块（Tile），每个拼接块可以按特定的参数独立进行编码。n(2)电平位移:希望图像的样本数据有近似集中于零附近的动态范围。n(3)分量变换:分量变换的主要目的是减少图像分量之间的相关性，以便利用人眼对色度的分辨率低于亮度的特性进行压缩。9.7 JPEG2000编码编码n 9.7.2 JPEG2000核心编码系统n 2.离散小波变换：n 二维离散小波变换是通过对样本数据先沿行方向进行低通和高通滤波，并对滤波结果进行21下采样，再对采样结果沿列方向进行与行方向同样的滤波和下采样来实现的。经过小波变换后
24、，图像片的每个分量被分解为低频和高频子带，如图所示。图像小波分解示意图9.7 JPEG2000编码编码n 9.7.2 JPEG2000核心编码系统n 3.量化n对于无损压缩，小波系数不需要量化；对于有损压缩，对小波系数采用带死区（deadzone，输出为0的区域）的均匀标量量化方法。带死区的量化示意图9.7 JPEG2000编码编码n 9.7.2 JPEG2000核心编码系统n 4.码率控制n 编码的码率R（每符号的比特数）与失真度D（原始图像与重建图像之间的均方误差）之间的函数关系称为率失真函数。率失真函数在定义域内是单调递减的，给出了失真度为D时的极限码率。率失真优化示意图9.7 JPEG
25、2000编码编码n 9.7.2 JPEG2000核心编码系统n 5.EBCOT编码n 经过量化后，将子带进一步划分为更小的矩形区域码块（code-blocks），使得同一子带的码块大小相同（典型大小为3232或6464）。EBCOT采用2层编码策略：在第1层编码中，对每个码块独立进行熵编码，包括分数位平面编码（BPC）和二进制算术编码（BAC），得到码块的嵌入式位流；在第2层编码中，根据率失真最优原则将所有码块的嵌入式位流组织成具有不同质量的位流层，按照一定的码流格式对每一层打包输出压缩码流。9.7 JPEG2000编码编码n 9.7.2 JPEG2000核心编码系统n 5.EBCOT编码n（
26、1）分数位平面编码n从码块的最高有效位平面（至少包含一个1）到最低位平面，依次对每个位平面执行重要性传播（SPP）、幅度精练（MRP）和清理（CUP）3个编码通道。位平面上的每个系数位必须且只能在其中一个编码通道上编码。码块中的每个位平面从左上角开始，按条带方式从上到下扫描，条带内按列从左到右扫描，条带高度为4。码块位平面内的扫描顺序9.7 JPEG2000编码编码n 9.7.2 JPEG2000核心编码系统n 5.EBCOT编码n（1）分数位平面编码n码块的每个系数都有一个对应的“重要性状态”，1表示该系数重要，0表示不重要。重要性状态初始化为0，编码过程中可能变为1。8个邻域系数的重要性状
27、态确定了当前系数的上下文，最多有256种上下文。考虑到待编码位与邻域位的相关性和设计的可行性，EBCOT将8个邻域分为水平、垂直和对角3类，通过零编码（重要性编码）、符号编码、幅度精练编码和游程编码（清理编码）4个算子使得上下文缩减到19种。这4个算子由3个编码通道来执行，每个位生成一个上下文标志CX和0/1判定D，然后将其送入算术编码器处理。9.7 JPEG2000编码编码n 9.7.2 JPEG2000核心编码系统n 5.EBCOT编码n（2）二进制算术编码n JPEG2000中采用MQ算法实现基于上下文的二进制算术编码，包括概率估计、间隔计算和区间调整等过程。MQ将输入的0/1判定D映射
28、为小概率符号（LPS）和大概率符号（MPS），通过递归划分概率区间来实现编码。当收到一个0/1判定D时，首先根据上下文标志CX在上下文表和概率估计表中查出LPS的概率Qe，然后根据D是否为MPS来划分概率区间。9.7 JPEG2000编码编码n 9.7.2 JPEG2000核心编码系统n 5.EBCOT编码n（2）二进制算术编码n假设当前概率区间的下界和大小分别为C和A，则概率区间更新如下：,DLPS,DMPSeeeCC AAQCCAQ AAAQ为时为时划分之后，LPS对应区间为C,C+AQe)，MPS对应区间为C+AQe,C+A)。为了简化计算，让A保持在0.751.5，用Qe替换。9.7
29、JPEG2000编码编码n 9.7.2 JPEG2000核心编码系统n 5.EBCOT编码n（3）码流组织n为了使得压缩码流具有失真率可伸缩性（即传输渐进性），JPEG2000采用压缩后率失真优化（PCRD）算法计算码块位流在每一层上的截断点，将码块位流按照截断点分层组织成不同的质量层（Quality Layer）。9.7 JPEG2000编码编码n 9.7.2 JPEG2000核心编码系统n 5.EBCOT编码n（3）码流组织n设每个码块有n个截断点（对应有n个质量层），zik为码块Bi的第k个截断点，Li(zik)和Di(zik)分别为码块Bi在zik处对应的码长和失真率，有：10()()
30、()kniiiiiiL zL zL z给定第k个质量层的总目标码长上限为Lkmax，假定码的失真率具有可加性，则理想的截断策略是在总码长满足 的条件下，使得总失真率 最小。max()kkkiiiLL zL()kkiiiDD z9.7 JPEG2000编码编码n 9.7.2 JPEG2000核心编码系统n 5.EBCOT编码n（3）码流组织n每个质量层由拼接块中各个码块的部分嵌入式位流组成，可以涉及码块任意数量的位平面编码通道。质量层示意图9.7 JPEG2000编码编码n 9.7.2 JPEG2000核心编码系统n 6.感兴趣区域编码n通过使用Maxshift方法，JPEG2000允许对任意形
31、状的感兴趣区域（ROI）进行编码，且无需对ROI的形状进行编码和解码。Maxshift方法的基本思想：在进行EBCOT编码之前，找到ROI的最小值和背景的最大值，将ROI的小波系数整体平移到背景系数之上，因而ROI中的系数的位平面编码先于背景系数。9.7 JPEG2000编码编码n 9.7.3 JPEG2000编码实例n 下面用Kakadu中的kdu_compress程序对示例图像进行JPEG2000编码。n用如下命令将输入图像WarnTree.bmp分别以目标码率1.0、0.25和0.05bpp编码为JP2文件，压缩后的文件大小分别为34.4、8.7和1.84KB，峰值噪声比分别为30.07
32、、24.66和21.27 dB，效果如下图。不同目标码率的压缩效果(a)24bpp,837KB(b)1bpp,34.4KB(c)0.25bpp,8.7KB(d)0.05bpp,1.84KB9.7 JPEG2000编码编码n 9.7.3 JPEG2000编码实例n 如下命令对输入图像Cabrite.bmp分为4个质量层进行无损编码，前3层的目标码率分别为0.05、0.2和1.0bpp，后一条命令用矩形区域进行感兴趣区域编码。nkdu_compress-i Cabrite.bmp-o CabriteNoRoi.jp2-rate-,1.0,0.5,0.1 Creversible=yes Rlevels=5nkdu_compress-i Cabrite.bmp-o CabriteRectRoi.jp2-rate-,1.0,0.5,0.1 Creversible=yes Rshift=12 Rlevels=5-roi 0.2,0.1,0.4,0.49.7 JPEG2000编码编码n 9.7.3 JPEG2000编码实例n 效果如下图。(a)原始图像(b)无ROI编码的第一质量层(c)ROI编码的第一质量层(d)ROI编码的第三质量层感兴趣区域编码效果
