数字图像处理与分析基础.ppt

数字图像处理与分析基础,第七章 图像编码技术,新世纪电子信息与自动化系列课程改革教材,ISBN7-5084-2930-3,整理发布,数字图像处理与分析基础,第七章 图像编码 Image Coding,压缩目的基本原理基本方法图像编码标准,数字图像处理与分析基础,7.1 编码的目的,减少数据量：存储量、传输时间,例1:一般彩色电视信号,YIQ色空间中各分量的带宽分别为4.2MHz、1.5MHz、0.5MHz，采样原理，采样频率=2倍原始信号频率，量化为8bit，1秒钟的数据量为(4.2+1.5+0.5)*2*8=99.2MBits，约为100Mbits/S，1GB的CD-ROM存1分钟的原始电视节目。HDTV数据量约为1.2GBits/S，1GB存6秒钟HDTV。彩色静止图像：3*1024*1024*8=3MB，,数字图像处理与分析基础,图像通信的一般过程,数字图像处理与分析基础,基本概念,信源需要传输或存储的原始信息称为“信源”。包括语音、图像、视频等信息源。“信源编码”的主要任务是利用一定的编码方法降低数码率，即比特率。信道信息传输的通路；信息在传输中要增加可靠性、抗干扰能力，就要进行“信道编码”，此时要进行奇偶校验等检测，需要增加比特数。抗干扰能力越强，增加的比特数就越多。,数字图像处理与分析基础,图像编码压缩要研究的主要内容,信源压缩方法与信源模型有关语音，线性模型比特率采样速率（每秒样本数）乘以样本精度（比特/样本）逼真度准则或失真度准则平方误差准则 基于主观感受的逼真度准则,数字图像处理与分析基础,4、编码准则,输入图像f(x,y),输出g(x,y),x,y=0,1,2,N-1,（1）均方误差：,（2）均方根信噪比：,（3）压缩比=原图像编码每个象素平均所需bit数/压缩后象素平均所需bit数,保真度准则：主观保真度准则、客观保真度准则。客观保真度准则：图像均方误差、均方根信噪比。,数字图像处理与分析基础,主观保真度准则,数字图像处理与分析基础,7.2 图像压缩的基本原理,1、压缩的根据：图像数据量信息量,I=D-du,I（信息量），D（数据量），du（冗余量）保留意义完全的信息，支持查询与检索。冗余(redundancy)信息和不相干(irrelevancy)的信息。,数字图像处理与分析基础,压缩率,用n1表示一幅图像原来的数据量，n2表示压缩后的数据量，压缩率 Cr 定义为：Cr=n1/n2（7-2）冗余量 Rd 可表示为：Rd=1-1/Cr（7-2）,数字图像处理与分析基础,7.2.2数据冗余的类型,编码冗余像素间冗余心理视觉冗余,数字图像处理与分析基础,1、编码冗余（信息熵冗余）,“码本”是表示一组信息或一组事件的一系列符号（如字母、数字等）。其中对每个信息或事件所赋予的符号成为“码字”，每个码字含有的基本符号的个数称为“码长”。设l(rk)为码字rk的码长，在二进制表示时称为“比特数（bits）”，Pr(rk)为码字的出现概率。若编码系统共有L种不同的码字，则系统可获得的平均比特数为：,数字图像处理与分析基础,自然码，如表示256个不同的灰度级，就用8bits的等长的二进制数据来编码每一个灰度级，这样系统的平均码长就是8bits。定理：当l(rk)根据pr(rk)降序设计成变长编码的形式时，平均码长最小。,数字图像处理与分析基础,等长编码与非等长编码比较,数字图像处理与分析基础,2、像素间冗余,（1）空间冗余：规则物体和规则背景的表面物理特性具有相关性。,（2）时间冗余：序列图像,像素的灰度级和颜色之间具有相关性，随机场模型,数字图像处理与分析基础,（3）结构冗余：纹理结构（4）知识冗余：人脸的固定结构。空间冗余、时间冗余又称统计冗余，将图像信号作为概率信号时的统计特性。,数字图像处理与分析基础,3、心理视觉冗余,视觉系统非线性、非均匀分辨率约26，图像量化28动态图像的视觉延迟现象,数字图像处理与分析基础,7.2.3 编码方法的分类,由压缩数据恢复的图像与原始图像的差别“可逆压缩”：编码的数据可完恢复出原始图像“熵编码”（Entropy Coding），“无失真编码”、“无误差编码”（Error Free Coding）、无噪声编码”(Noiseless)、“冗余度压缩”（Redundancy Reduction）、“数据紧缩”（DATA Compaction Lossless Bit-Preserving）。“不可逆压缩”：“有失真编码”（lossy Coding），采用这类编码方法，由编码数据恢复的图像与原始图像有区别，图像编码产生的误差与编码的方法以及压缩比等因素有关。,数字图像处理与分析基础,1、“第一代”编码技术,三大经典编码方法“熵值编码”“预测编码”“变换编码”。,数字图像处理与分析基础,“熵值编码”,（概率匹配编码）主要针对无记忆信源，根据信息码字出现概率的分布特征，寻找概率与码字长度间的最优匹配，从而进行压缩编码，又称为统计编码。游程编码、Huffman编码和算术编码等多种。熵值编码是信息编码的基础，也是各种实用算法的一个基本组成部分。,数字图像处理与分析基础,“预测编码”,根据数据的统计特性得到预测值，然后传输图像像素与其预测值的差值信号，使传输的码率降低，达到压缩的目的。预测编码方法简单经济，编码效率较高，是语音的基本编码方法。预测编码分为线性预测编码、非线性预测编码。根据处理的信息维数不同，又可分为行内编码（一维）、帧内编码（二维）以及帧间编码（三维）。预测编码是视频图像压缩的基础。,数字图像处理与分析基础,“变换编码”,进行某种正交变换来消除像素间的相关性。可分为最佳变换编码，如K-L变换，以及次优变换编码，如离散余弦变换（DCT）等。在实施时，辅助以区域变换编码、门限变换编码。基于离散余弦变换的静止图像压缩标准jpeg和运动图像压缩标准mpeg等一系列标准。,数字图像处理与分析基础,“自适应编码”,从本质上来说就是一种“混合编码”方案，它在不同阶段根据图像的不同特征将变换编码、预测编码、无误差编码等各种方案的优势综合利用起来。关键是识别图像的特征。多种方案的复用可实现多级压缩，已经可以得到较大的压缩比了，现有的图像压缩标准JPEG、MPEG等在设计中就利用了这种思路。,数字图像处理与分析基础,2、第二代编码技术,要充分利用人的视觉生理、心理特征和图像信源的各种特征，实现从“波形”编码到“模型”编码的转变，以便获得更高压缩比。向量量化编码、基于分形的编码、基于模型的编码、基于区域分割的编码、基于神经网络的编码以及识别编码和基于知识的编码等。,数字图像处理与分析基础,3、过渡编码技术,充分利用人类视觉特性的“多分辨率编码”方法，如子带编码、金字塔形编码和基于小波变换的编码。这类方法原理上仍属于线性处理，属于“波形”编码，可归入经典编码方法，但它们又紧密结合人类视觉系统的特性，因此可以被看作是“第一代”编码技术向“第二代”编码技术过渡的桥梁。,数字图像处理与分析基础,子带编码技术：,子带编码是一种高质量、高压缩比的图像编码方法，它早已在语音信号压缩编码中获得了广泛的应用。其基本依据是：图像信号可以划分为不同的频域段，人眼对不同频域段的敏感程度不同。例如图像信号的主要能量集中在低频区域，它反映图像的平均亮度；而细节、边缘信息则集中在高频区域。子带编码的基本思想是利用一滤波器组，通过重复卷积的方法，将输入信号分解为高频分量和低频分量，然后分别对高频和低频分量进行量化和编码。解码时，高频分量和低频分量经过插值和共轭滤波器而合成原信号。进行子带编码的一个关键问题，是如何设计共轭滤波器组，除去混叠频谱分量。,数字图像处理与分析基础,小波变换编码技术,小波变换编码技术是目前的研究热点。小波变换它不仅为多分辨分析、时-频分析和子带编码建立了统一的分析方法，而且提供了更合理的表示框架。目前小波变换在图像编码中的应用研究主要课题有：正交小波基的选择（小波包法）、小波变换与各种量化方式的结合、小波变换在分形法中实现初级分形、小波变换用于运动估值等方面。小波变换法处于图像编码当前首选方法的位置，一方面，它有快速算法，实现起来简单方便、速度快，可暂时弥补“第二代”编码技术的不足；另一方面，它有着先进的分析方法，可有效提高现有技术的水平，实现突破性进展。,数字图像处理与分析基础,4、第三代编码技术,在第三代编码方案中主要提出了基于运动模型（VR）的编码概念，主要针对提高电视会议、可视电话等的图像效果。,数字图像处理与分析基础,数字图像处理与分析基础,7.2.4 简单的图像编码模型,编码部分,解码部分,数字图像处理与分析基础,（1）信源编码器和信源解码器,原始图像,映射变换（信息抽取）,映射后数据,量化器,符号编码器（码元分配）,码字,图像数据压缩的一般过程（信息源）,映射器：将输入数据从象素域变换到另一个域中。量化器：将每个映射数据舍入为数目较少的可能数值。均匀、非均匀,数字图像处理与分析基础,（2）信道编码器和信道解码器,汉明（Hamming）编码：正确的码字之间的最小距离要大于一个给定值,码字以二进制形式表示，比特（bit）D(101),(110)=2,汉明:将3个比特位的冗余加到4比特的码字上，任意两个正确码字间的距离为3，可发现和校正错误。,数字图像处理与分析基础,例：4bit(b3b2b1b0)7bit(h1h2h3h4h5h6h7),h1、h2、h4分别是比特区h3b2b0、b3b1b0、b2b1b0的偶校验位。,信道解码器对已建立偶校验的比特区进行检查，由c1、c2、c4指出错误，从校正后的h3h5h6h7得到正确值。,数字图像处理与分析基础,7.3 编码器和典型的编码方法,编码器：给每一量化器的输出分配一个码字。等长码、非等长码、唯一可译码、瞬时码,X:信号源；A:构成码字的符号集，a称为码元；W:代码,信号源：象素灰度、行程长度、方向码、预测误差、变换系数、上一过程的结果，等等。,数字图像处理与分析基础,码字的形式,二进制码：码元数等于2时的代码称为二进制码。等长码：如果码字集合W中的所有码字都具有相同的长度，就是等长码。如自然二进制码。码长不等的就称为非等长码，如Huffman码。唯一可译码（单义码）：如果任何长度的一段代码只能分割成唯一的一个码字集合，则为唯一可译码。如 W=0,10,11，对代码序列S=100111000，只能分割成10、0、11、10、0、0。,数字图像处理与分析基础,在编码中形成的代码集合必须是单义码，否则没有实际使用价值。非续长代码：码字集合中的任何一个码字都不是另一个码字的续长。如W=0,10,100,111就不是非续长代码，其中“100”是“10”的续长。非续长代码一定是单义码，但单义码不一定是非续长代码。如 W=0,01是单义码，但又是续长代码。非续长代码可以用树型结构构造。,数字图像处理与分析基础,构造非续长码,设A=0,1,W=w1,w2,w3,w4,设置根节点，从根节点开始分枝，每条分枝代表一个码元0或者1，取其中任意一个分枝的节点代表w1。,对没有被选作代码的节点再分枝，选择其中任意一个分枝的节点作为代码w2。,依次类推，至所有节点都代表一个码字结束。,数字图像处理与分析基础,4、按照分枝顺序构成各码字：w1=0，w2=10，w3=110，w4=111。各码字的长度为：n1=1，n2=2，n3=n4=3。树形图说明，被选作代码的节点不会再有分支，因此形成的必然是非等长的非续长代码。,数字图像处理与分析基础,无噪声编码定理,Shannon的信息论如何构造码字，才能得到最短的平均码长？对特定的信息源，平均码长有下限吗？随机事件提供的信息量，与事件的出现概率有关。,数字图像处理与分析基础,称为E的自信息。,（即事件总是发生），那么，,结论：确定的事件没有提供任何新的信息，而偶然发生的事件，提供的信息量比较大。,设有随机事件E，它的出现概率是p(E)，那么它包含的信息量为：,如果,数字图像处理与分析基础,那么信息源X=xj,j=1,2,3,n提供的信息量定义为：,H(X)称为信息的“熵”，它定义了信息的平均信息量（每单位字符）。熵值总是非负的，当构成信息源的所有事件的概率都相等时，熵值最大。如果对数的底是2，那么信息熵的度量单位就是比特（bits per symbol）。,数字图像处理与分析基础,某种编码方法的编码效率定义为：,其中H(x)为信号的信息为熵，L(x)为编码的平均长度。这种编码方法的冗余度为,：,如果某种编码方法产生的平均字长等于信息源的熵，那么它就没有任何冗余信息，达到了编码的最优状态。这时要求：,某种编码方法的编码效率定义为,数字图像处理与分析基础,“Shannon（香农）第一定理”,“无噪声编码定理”，也就是“Shannon（香农）第一定理”。信息的码字长度与它的出现概率成反比，大概率事件的码长较短，小概率事件的码长较大，严格按照这个规律构造非等长码，就可以获得概率统计意义上最优的编码。平均码长的下限是，对二进制编码而言，只有当所有符号的出现概率等于2的负整数幂时，（如0.5，0.25等），才能达到下限。信息的出现概率在实际应用中很难获得，一般是用它的频率代替。,数字图像处理与分析基础,几种典型的统计编码方法,根据信息熵的理论，将信息出现的概率模型引入编码模型中，得到概率意义下最优编码最常用的霍夫曼码对数码移位码算术编码等。,数字图像处理与分析基础,1、霍夫曼码(Huffman),基本思想：统计信号的概率分布模型，然后按信号出现的概率赋予信号不同的码长。出现概率大的信号赋予较短的码字，出现概率小的，赋予较长的码字。,数字图像处理与分析基础,算法,（1）统计输入信号的概率（如对一幅图像或M幅同种类型图像进行灰度分布概率统计），得到N个不同概率的信息符号；（2）将N个输入信号按照它们的出现概率由大到小排列；（3）合并两个概率最小的信号，形成一个新的信号。新信号的概率是这两个信号的概率和。这时概率减少为N-1个；（4）在形成新概率集合后重新排列；（5）重复第4步，至只剩两个概率序列为止；（6）以二进制码元（0，1）赋值，形成非续长代码树。注意，最好按统一规律分配码元，这样解码时更易于理解。（7）霍夫曼代码的产生从根节点开始，反向进行。,数字图像处理与分析基础,霍夫曼码举例,例:H-CP110.42000.330110.1401000.15010100.066010110.04,L=k=1,M kP(k)=1(0.4)+2(0.3)+3(0.1)+4(0.1)+5(0.06)+5(0.04)=2.20 bitsH=-k=1,M P(ak)log P(ak)=-0.4log(0.4)-0.3log(0.3)-0.1log(0.1)-0.1log(0.1)-0.06log(0.06)-0.04log(0.04)=2.14 bits,数字图像处理与分析基础,霍夫曼码是最佳编码：按给定的概率分布构成的最短的代码-与概率分布相匹配的编码。编码效率：=H(x)/L(x)=2.14/2.20=0.97,缺点：1、强烈依赖于概率结构，工作量大。2、码字变化大，结构复杂，实现困难。,数字图像处理与分析基础,2、B码（对数码）,概率服从乘幂定律时最佳，Pk=k-r,k=1,2,.,M,rN两部分构成：一半延续比特C、一半信息比特B（采用长度增长的自然码），CBC=0/1，C同，则还是同一码字；C变，则新的码字开始。Bn:每一延续比特，有n个信息比特。例1：B1:c0 c1B2:c00 c10 c11 c01例2：1 8 5B1：001010110100,数字图像处理与分析基础,3、S码（移位码，shift code）,两部分：CS，基本码S、移位信息C。Sn中n表示基本码字的长度。2n中有2n-1个基本码字，一个移位信息。例：S2码1：C1 00 2：C2 01 3：C3 104：C4C1 1100 5：C4C2 1101 6：C4C3 1110 7：C4C4C1 111100特点：易于实现，对单调减小概率相当有效。,数字图像处理与分析基础,算术编码是60年代初期Elias提出，由Rissanen和Pasco首次介绍了它的实用技术，在信源概率分布比较均匀情况下，它的编码效率高于哈夫曼编码(5%)，没有变换编码对数据输入分块的要求，在JPEG扩展系统中用它来取代哈夫曼编码。,4、算术编码(Arithmetic),数字图像处理与分析基础,1、算术编码原理,将被编码的信源消息表示成实数轴01之间的一个间隔(Interval)(也称子区间)，消息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位数就越多。信源中连续符号根据某一模式生成概率的大小来缩小间隔。,数字图像处理与分析基础,例 已知信源，,二进制信源符号只有两个“0”和“1”，设置 小概率Pc1/4，大概率Pe=1-Pc3/4设C为子区的左端起始位置，L为子区的长度(等效于符号概率)，根据：符号“0”的子区为0,1/4)；“0”的子区左端C0，子区长L1/4；符号“1”的子区为1/4，1)；“1”的子区左端C1/4，子区长L3/4。,试对1011进行算术编码。,算术编码过程,数字图像处理与分析基础,在编码运算过程中，随着消息符号的出现，子区按下列规则缩小。规则A：新子区左端 前子区左端十当前子区左端前子区长度；规则B：新子区长度=前子区长度当前子区的长度。初始子区为0，1)，即0=x1,数字图像处理与分析基础,步序 符号 C L(1)1 1/4 3/4(2)0 1/4+0*3/4=1/4 3/4*1/4=3/16(3)1 1/4+1/4*3/16=19/64 3/16*3/4=9/64(4)1 9/64+1/4*9/64=85/256 9/64*3/4=27/256 最后的子区左端(起始位置)C(85/256)d=(0.01010101)b 最后的子区长度L(27/256)d(0.00011011)b 最后的子区右端(子区间尾)(7/16)d=(0.0111)b编码结果：子区间头尾之间取值，其值为0.011，可编码为011，原来4个符号1011被压缩为三个符号011。解码过程：是逆过程，首先将区间1，0)按Pc靠近0侧，Pe靠近1侧分割成两个子区间，判断被解码字落在哪个子区，而赋予对应符号。,数字图像处理与分析基础,（1）算术编码的模式选择，直接影响编码效率，有固定模式，也有自适应模式。（2）算术编码的自适应模式，无需先定义概率模型，对无法进行概率统计的信源合适，在这点上优越于哈夫曼编码。（3）在信源符号概率接近时，算术编码比哈夫曼编码效率高。（4）算术编码硬件实现比哈夫曼编码要复杂些。（5）算术编码在JPEG的扩展系统中被推荐代替哈夫曼编码。,算术编码的特点,数字图像处理与分析基础,小结,编码器，不可缺少变长编码统计编码实现困难,