数字视频图像处理PPT电子课件教案-第四章 信源编码和率失真理论.ppt

第04章 源编码和率失真理论 source code and rate-distortion theory,2,内容提要 outline,信源编码定理 信源压缩方法 图像冗余 率失真理论 无记忆信源的率失真理论 有记忆信源的率失真理论,3,信源 编码,调制,信道,解调,噪声 干扰,信源 解码,二进制符号,用二进制符号流表示信源,适应传输信道的特性,数字传输系统,4,信源的原始信号绝大多数是模拟信号，因此，信源编码的第一个任务是模拟和数字的变换，即：a/d、d/a。 取样频率取决于原始信号的带宽： fc = 2 w，w为信号带宽 取样点的比特数决定编解码后的信号质量： snr 6 l(db)，l为量化位数 但是，由于传输信道带宽的限制，又由于原始信源的信号具有很强的相关性，则信源编码不是简单的a/d、d/a，而是要进行压缩。为通信传输而进行的信源编码，主要是压缩编码。 信源编码要考虑的因素： 信源的统计特性。 传输信道引入的损伤，如误码。 信宿的质量要求。,数字传输系统概述,5,信源编码定理： 对于给定的失真率 d，总可以找到一种信源编码方法，只要信源速率 r 大于率失真 r(d)，就可以在平均失真任意接近 d 的条件下实现波形重建。 说明1：r(d) 称为率失真函数，它是单调非增函数，速率越高，平均失真越小。 说明2：为了保证在一定速率下的失真，必需采用信源编码，因而会引入编码延时。 信道编码定理： 如果信源速率 r 小于信道容量 c，总可以找到一种信道编码方法，使得信源信息可以在有噪声信道上进行无差错传输，即：r c，无差错传输条件。 说明1：信道容量 c 是根据仙侬定理得到的 c wlog2(1+s/n) 说明2：为了保证无差错传输，必需采用信道编码，因而会引入编码延时。,数字传输系统信源和信道编码,6,信息传输定理： 将信源编码定理和信道编码定理综合，就得到信息传输定理。即：为保证无差错传输及失真度，必需满足：r(d)rc，即 c r(d)。 说明1：在一般数字通信系统中，信源编码和信道编码可以分开考虑。信道编码定理给出无差错的速率上限 rc，否则产生误码；信源编码定理给出无失真的速率下限 r(d) r，否则产生的失真大于所要求的失真 d。 说明2：为了实现理想性能，都要付出延时的代价。,数字传输系统信息传输定理,7,压缩方法,信源压缩方法可以主要分为三大类： 利用人眼的视觉特性 模拟压缩技术 统计编码 人眼视觉特性：因为最终评价图像的质量是通过人眼来完成，所以可利用人眼的一些视觉特性对图像进行有损压缩，而产生的误差又不易被人眼所察觉。 模拟压缩技术： 常用的有亚取样、隔行隔点取样以及减少刷新速率。 它们的使用都有一定的限制条件。亚取样可能导致混迭现象。隔行隔点取样将降低空间分辨率，可能导致爬行现象，当然也可在收端再插入行和点。减少刷新速率，将出现闪烁，且运动的连续性不好。,8,压缩方法,统计编码：两种有效的压缩方法 无失真压缩 loss-less compression：即熵编码，如游程长 (run-length) 编码和哈夫曼(huffman) 编码； 2 到 5 倍压缩比 有失真压缩 lossy compression：即允许有部分失真，遵循率失真函数，如预测编码、变换编码、运动补偿技术等 5 到 250 倍压缩比 信源的统计特性。 传输信道引入的损伤，如误码。 信宿的质量要求。,9,压缩 - 无失真方法,游程数据编码 101000100010001001101 = 1 + 4x0100 + 1101 源 21 bits 压缩后 12 bits 变字长编码（variable-length code, vlc) 哈夫曼编码 (huffman code) 概率大的块（事件）赋予短码 概率小的块赋予长码 算术编码 (arithmetic code) 概率大的块（事件）赋予短码，概率小的块赋予长码 但它的编码过程与 huffman 编码却不相同,10,压缩 - 有失真方法,量化 quantisation - 截短或舍入 dpcm 编码 运动估计和补偿 变换编码 (transform coding) klt 变换 离散余弦变换 discrete cosine transform (dct) 小波变换 wavelet transform 分形编码 fractal coding,11,图象的相关性（冗余度）,空间冗余 例: 图象中包含许多规则物体，它们的亮度、饱和度及颜色可能都一样， 因此，图象在空间上具有很大的相关性。例如 lenna 图象的脸部和肩部。,例: 序列图象,时间冗余,12,信息熵冗余 信息量： 从 n 个可能事件中选出一个事件所需要的信息度量。 设事件 x 的概率为 p(x)，则信息量定义为： i(x)= -log2p(x) 信息熵：如果将信源所有可能事件的信息量进行平均，就得到了信息熵(entropy)。熵就是平均信息量。 信息源的符号集为 xj (j=1,2,3n)，设 x 出现的概率为 p(xj),则信息源 x 的熵为,图象的相关性（冗余度）,当 xj 等概时，h(x) 最大。 当 xj 非等概时，h(x) 不是最大，就存在冗余。,13,结构冗余 图象有非常强的纹理结构 如草席图结构上存在冗余,图象的相关性（冗余度）,知识冗余 图像的理解与某些基础知识有关 例:人脸的图像有同样的结构：嘴的上方有鼻子，鼻子上方有眼睛，鼻子在中线上,14,视觉冗余 视觉冗余是非均匀、非线性的。 例: 人类视觉分辨率为 26 ，但常用 28 就是数据冗余。,其它冗余 图象空白的非定长性。,图象的相关性（冗余度）,15,率失真理论：有损压缩,前面我们已经讨论了离散信源的无失真编码/熵编码理论 但无失真编码并非总是必需的和可能的 无失真压缩存在固有的限制：熵 人的认知器官 人的视觉/听觉系统只能感知有限范围的信号 如果我们不能看见/听见，为什么还编码呢？ 从部分损失恢复的能力 如低帧率会使得运动跳跃，但仍然可被感知 由于受到信息存储、处理或传输设备的限制，而不得不对信源输出的信号作某种近似以降低熵率，如对连续信号的数字化、音视频。,16,率失真理论：有损压缩,无损编码： x = x 亦称为熵编码（entropy coding）或可逆编码（reversible coding） 有损编码：x x 亦称为不可逆编码（irreversible coding）,17,率失真理论：有损压缩,如果允许信号存在一定可接受的失真度 d，则能得到更低的比特码率 r。,率失真理论旨在寻求一种联系定长编码的失真度与编码数据率的方法。 率失真理论并不针对特定的编码方法,18,率失真理论：失真度量 1/5,符号 xn 原始信源输出 yn 重构输出 平方误差 d(x, y) = (x y)2 绝对误差 d(x, y) = |x y|,绝对最大误差(absolute maximum error),19,率失真理论：失真度量 2/5,信噪比 (signal-to-noise ratio, snr),平均绝对误差 (average absolute difference),均方误差 (mean squared error, mse),20,率失真理论：失真度量 3/5,峰值信噪比 (peak-signal-to-noise ratio, psnr),在实际应用中常用峰值信噪比 psnr，通常 psnr 比 snr 大1215db。 一般认为：峰值信噪比与图像质量近似成正比关系。 但 psnr 有其局限性：由于均方误差d2 是功率的平均，因此它不能完全地反映主观感觉。例如，在图像出现窄的水平亮条干扰时，虽然图像的 psnr 高，但主观感觉差；又如在图像传输处理过程中出现的小错误，虽然它不会对 psnr 值产生大的影响，但如果其位置恰好处在图像理解的关键位置，由于人类视觉系统对关键信息的改变非常敏感，因此，会大大影像主观质量的评价。,21,率失真理论：失真度量 4/5,峰值信噪比=6.24,峰值信噪比=5.98,结论：1、峰值信噪比度量与人的视觉感知并不完全一致！但由于均方误差和信噪比在数学上容易处理，另外也缺少性价比更好的替代方法。因此，上述方法在图像处理的客观失真测量方面仍得到了大量的应用。 2、需要寻求更加符合人类视觉感知的客观度量方法以及相应的编码理论和方法。,22,率失真理论：失真度量 5/5,客观评价：用数学表达式表示原始信号与重构信号之间的差异 如上述准则 不一定符合用户的感知评价，但在数学计算上可以控制 用户主观评价：最终用户评价重构信号的质量（可接受程度） 工作量大 符合用户感知的真实情况，但数学计算可能不好处理 介于二者中间：用数学模型表示人类的感知机制 将信源输出和重构信号都投影到感知空间 然后在感知空间中度量二者之间的差异 但人类感知过程很难建模，或数学模型太复杂,23,率失真理论：条件自信息,信源编码：将输入符号集 映射成另一个输出符号集 条件自信息 i(aj|bk) 表示在发现信源编码器输出为 bk 时，对应的信源发出符号 aj 的不确定程度。而条件自信息 i(bk|aj) 表示在信源发出符号为 aj 而编码输出为 bk 的不确定程度。,24,率失真理论：互信息,互信息：自信息与条件自信息之间的差 i(aj) 表示 aj 所含的信息量（不确定性），i(aj|bk) 表示在知道 bk 后 aj 还保留的信息量，所以互信息表示符号 bk 为 aj 提供的信息量。 平均互信息： 表示信源 x 的平均不确定性与其在信源 y 被确定条件下仍保留的平均不确定性之差，即随机变量 y 对 x 提供的平均信息量。,25,率失真理论：互信息-条件熵,平均条件熵 x、y 的联合熵定义为,26,率失真理论：互信息-条件熵,例题,27,率失真理论：互信息- venn 图,互信息量与熵的关系,仅当 x 与 y 独立时，等号成立。,28,例题：若信源编码器是一个简单的一一对应关系，即m=n，且 即 所以互信息 i(aj; bk) = i(aj) ，即 bk 提供了aj 的全部信息。 信息保持编码属于这种情况。例如： 只要传输不出错，则收到任一码字，如 “110” 后，即可判断出所发的信源符号是 “7” 。,率失真理论：互信息,29,同上例，假设实际信源的 8 个符号，但发现 1,2; 3,4; 5,6; 7,8 两两相差不多，可用同一码字代表，如 n=4 个情况，用 2bit 即可表示，较上面的3bit编码，节省了1bit。但引入了一定的误差，如收到码 “01” 后判断为 “3”，若信源实际发出的是 “4”，则有了误差，这个误差可能是允许的！ 该误差的产生是由于对信源的某些符号进行了合并，减少了事件的数目，从而使新信源的熵降低。所以，当集合中事件结构发生变化时，会引起信源概率结构的变化，从而影响到信源熵的变化。,率失真理论：互信息,30,率失真理论：互信息,只要允许误差存在，就可以减少编码输出的字符数，因而也可以降低码率。可是字符数越少，译码误差或失真就越大。 问题：在给定的失真条件下，最小需要多大的码率，才能保证不超过允许的失真。即要确定每个编码符号至少应提供的关于信源符号的信息量。 用互信息表示，即在一定的失真条件下，得到平均互信息 的最小值 min i(x; y) 。 率失真函数的基本含义,31,率失真理论：平均互信息,互信息由以下概率决定： 信源符号概率 p(aj) 编码输出符号概率 q(bk) 已知信源符号出现的条件概率 q(bk|aj) 在确定信源的条件下，p(aj)已知，选择编码方法实际上是通过改变条件概率 q(bk|aj) 的分布来控制平均互信息量。,32,率失真理论,在信源允许一定失真情况下所需的最少码率：在允许一定失真d的情况下，信源输出的信息传输率可压缩到 r(d) 。 从分析失真函数、平均失真出发，求出信息率失真函数 r(d) 在一些实际问题中，信号有一定的失真是可以容忍的。但是当失真大于某一限度后，信息质量将被严重损伤，甚至丧失其实用价值。 要规定失真限度，必须先有一个定量的失真测度。为此引入失真函数。 客观的失真函数如前所述,33,率失真理论：失真函数,假如某一信源 x，输出样值为 x，xa1,a2,.,am ，经过有失真的信源编码器，输出 y ，样值为y，yb1,b2,.,bm . 失真的大小用一个量来表示，即失真函数 d(aj,bk) 以衡量用 bk 代替 aj 所引起的失真程度。一般失真函数（失真度）定义为：,34,率失真理论：平均失真,平均失真：失真函数 d(aj,bk) 的数学期望或统计平均值，记为 由条件概率 q(bk|aj) 控制。,35,率失真函数 r(d),信源编码器的目的是使编码后所需的码率 r 尽量小。然而 r 越小，引起的平均失真就越大。给出一个失真的限制值 d*，在满足平均失真 d(q)d* 的条件下，选择一种编码方法使码率 r 尽可能小。 所以若要求平均失真函数 d(q)d* ，则必然存在一个条件概率 q(bk|aj) ，使得 d(q)d* ，记 为保证失真在允许范围 d* 内的条件概率的集合。,36,率失真函数 r(d),由于互信息 i(x;y) 也受 q 的控制，可将率失真函数 r(d)（亦称码率-失真函数）定义为 率失真函数是在允许失真为 d* 的条件下，信源编码给出的平均互信息的下界，也是数据压缩的极限码率。 无记忆离散信源限失真编码定理：若一离散无记忆平稳信源的率失真函数是 r(d) ，则当码率 rr(d) ，只要信源序列长度足够长，一定存在一种编码方式，其解码失真 d +， 为任意小的正数。 逆定理：当码率 rr(d)，则无论采用什么编译码方法，其平均失真一定会大于失真限度d。,37,率失真理论：限失真信源编码定理,限失真信源编码定理只能说明最佳编码是存在的，而具体构造编码方法却一无所知。 因而就不能像无失真编码那样从证明过程中引出概率匹配的编码方法。一般只能从优化的思路去求最佳编码。实际上迄今尚无合适的可实现的编码方法可接近 r(d) 这个界。 计算一个具体信源的 r(d) 也很困难 条件极小值求解问题，其解的结果一般以参数形式给出，其中起控制作用的变量只有 q(bk) 。 编码就是通过对 q(bk) 的设计与实现，使码率接近 r(d) 但实际中的一些编码方法却并不直接去设计 q(bk) ，而是从最后的码率来对 r(d) 函数进行性能比较。,38,率失真函数的性质：定义域,r(d) 函数的定义域 (2) 存在一个 dmax ，使得当 ddmax 时，r（d）=0 。即 dmax 为所有满足 r(d)=0 的 d 中最小值，即,选择几个 bk ，使其失真 dk 最小者即为 dmax 。,39,率失真函数的性质：定义域,dmax 的计算 r(d)0 就是 i(x;y)0，这时编码器的输入与输出是互相独立的，所以条件概率 q(bk|aj) 与 aj 无关。即 此时平均失真为 求出满足条件 的 d 中的最小值，即,40,率失真函数的性质：定义域,从上式观察可得：在 k=1,2,3,n 中，可找到使 值最小的 k，当该 k 对应的 q(bk) =1 ，而其余 q(bk) 为零时，上式右边达到最小，这时上式可简化成,41,例题：设输入输出符号表为 x=y 0, 1 ，输入概率分布为 失真矩阵为 则当dmin = 0 时， 比特/符号，这时信源编码器无失真，所以该编码器的条件概率为,率失真函数的性质：定义域,42,当 r(dmax)=0 时， 此时输出符号概率 所以这时的编码器的条件概率为,率失真函数的性质：定义域,对应 k=2，此时 q(b2)=1, 其他q(bk)为0,43,率失真函数的性质：函数值,在定义域 dminddmax 内，r(d) 是正的、连续的下凸函数（单调递减）。 容许的失真度越大，所要求的码率越小。 反之亦然。,h(x)：信源的熵,r(0)：刚刚察觉质量失真时的码率,44,无记忆高斯信源的率失真函数,信源：0 均值、方差为 2 的高斯分布 失真函数（平方误差）：d(x,y) = (x-y)2 失真限制（均方误差）：e(x-y)2 d 方法： 找到互信息 i(x; y) 的下界 证明该下界是可以实现的 互信息：,45,无记忆高斯信源的率失真函数,最小化互信息 i(x; y) h(x) h(x-y) 可最大化 h(x-y) 当 (x-y) 为高斯分布时，熵最大。 而失真限制为 e(x-y)2 d 所以当 h(x-y) 是方差为 d 的高斯分布的微分熵时，下界为 上述下界：y 为 0 均值、方差为 2-d 的高斯分布，且,方差相同时，高斯分布的熵最大,46,无记忆高斯信源的率失真函数,当 d2 时，y=0，则 i(x; y) = 0 且 e(x-y)2 =2 d 所以无记忆高斯信源的率失真函数为,对于具有相同方差 2 的非高斯信源的 r(d) 通常位于这个 r(d) 曲线之下。 (因为在一定功率下，高斯分布信源的熵最大） 无记忆高斯信源代表了最不利于编码的情况，因为绝大多数图象既不是高斯分布，也不是不相关的象素。 也就是说，对于非高斯分布和相关的信源，在同样的失真度下，所需要的比特率低于上述值。,斜率为 6db/bit 的直线，码字长度每增加 1位，snr 增加 6db。,47,