第六章数据库技术导论.pdf

6 图像压缩6 图像压缩 知识点知识点 3 统计编码压缩 4 预测编码与变换编码压缩 1 图像压缩概述 5 图像编码与压缩标准 2 图像压缩的保真度准则与压缩性能参数 1 图像压缩概述 一. 图像编码技术的研究背景 1. 信息信息传输方式发生了很大的改变 通信方式的改变 文字+语音 图像+文字+语音 通信对象的改变 人与人 人与机器，机器与机器 1 图像压缩概述 一. 图像编码技术的研究背景 2. 图像传输与存储需要的信息量空间 （1）彩色视频信息 对于电视画面的分辨率640*480的彩色图像，每 秒30帧，则一秒钟的数据量为： 640*480*24*30=210.94M 所以播放时，需要211Mbps的通信回路。 参考数据：宽带网为2048K。 存储时，1张DVD可存4.7G，则仅可以存放22.8 秒的数据。 1 图像压缩概述 一. 图像编码技术的研究背景 2. 图像传输与存储需要的信息量空间 （2）传真数据 如果只传送2值图像，以200dpi的分辨率传 输，一张A4稿纸的内容的数据量为： 1654*2337*1=3888768bit 按64K的电话线传输速率，需要传送的时间 是：59.3秒（目前四类传真机15s内传送一 页 ISO A4幅面文件） 1 图像压缩概述 一. 图像编码技术的研究背景 2. 图像传输与存储需要的信息量空间 由于通信方式和通信对象的改变带来的最大 问题是： 传输带宽、速度、存储器容量的限制。 给我们带来的一个难题，也给了我们一个机 会： 如何用软件的手段来解决硬件上的物理极限。 1 图像压缩概述 图像通信系统模型 图像信息源图像信息源 图像预处理图像预处理图像信源图像信源 编码编码 信道编码信道编码调制调制信道传输信道传输 解调解调 信道解码信道解码 图像信源图像信源 解码解码 显示图像显示图像 1 图像压缩概述 二. 图像中的数据冗余的概念 你的朋友，阿利，将于明天晚上8点零5分在武汉 的天河机场接你。- (25*2+5=55个半角字符) 阿利将于明天晚上8点零5分在天河机场接你。 -(18*2+3=39个半角字符） 阿利明晚8点在天河接你。 -(10*2+2=22个半角字符） 结论：只要接收端不会产生误解， 就可以减少承 载信息的数据量。 1 图像压缩概述 描述语言描述语言 1）“这是一幅 2*2的图）“这是一幅 2*2的图 像，图像的第一个像素是像，图像的第一个像素是 红的，第二个像素是红的，红的，第二个像素是红的， 第三个像素是红的，第四第三个像素是红的，第四 个像素是红的”。个像素是红的”。 2）“这是一幅2*2的图像，）“这是一幅2*2的图像， 整幅图都是红色的”。整幅图都是红色的”。 由此我们知道，整理图像的描述方法可以达由此我们知道，整理图像的描述方法可以达 到压缩的目的。到压缩的目的。 1 图像压缩概述 图像冗余无损压缩的原理图像冗余无损压缩的原理 RGBRGBRGBRGB RGBRGBRGBRGB RGBRGBRGBRGB RGBRGBRGBRGB 16RGB 从原来的16*3*8=284bits压缩为：从原来的16*3*8=284bits压缩为： (1+3)*8=32bits(1+3)*8=32bits 1 图像压缩概述 图像冗余有损压缩的原理图像冗余有损压缩的原理 3635343434 3434323434 3337303434 3434343434 3435343431 3434343434 3434343434 3434343434 3434343434 3434343434 2534 1 图像压缩概述 视觉心理冗余：视觉心理冗余： 一些信息在一般视觉处理中比其它信息的一些信息在一般视觉处理中比其它信息的 相对重要程度要小，这种信息就被称为视觉相对重要程度要小，这种信息就被称为视觉 心理冗余。心理冗余。 1 图像压缩概述 2017/12/1813 图像的视觉冗余 （彩色）图像的视觉冗余 （彩色） RGB 24888 22*2*2 = 24 2 = 16,777,216 (248,27,4)(251,32,15)(248,27,4)(248,27,4) 1 图像压缩概述 三. 图像冗余信息分析结论 由于一幅图像存在数据冗余和主观视觉冗余， 其压缩方式就是从这两方面着手来开展的。 （1）因为有数据冗余，将图像信息的描述方式 改变之后，可以压缩掉这些冗余。 （2）因为有主观视觉冗余，当忽略一些视觉不 太明显的微小差异，可以进行所谓的“有损” 压缩。 2017/12/1814 1 图像压缩概述 四. 图像压缩与压缩的必要性 1. 图像压缩 图像压缩，本质上说，就是对图像源数据按一定的 规则进行变换和组合，从而达到以尽可能少的代码 来表示尽可能多的数据信息。压缩通过编码来实现， 或者说编码带来压缩的效果，所以，一般把此项处 理称之为压缩编码。 2. 压缩的必要性 一幅模拟图像必须经过脉冲编码调制（PCM Pulse Code Modulation)才能变成数字图像。 （PCM-脉码调制早期用于语音信号传送） 2017/12/1815 1 图像压缩概述 例1： 设一幅活动图像的像素总数为K，灰度分辨率为 b，时间分辨率为fB，则在实时传输过程中，该 图像在传输通道里的传输率至少应该为=KbfB 若K=512512, b=8, fB=25, 则=6.25 M/s 2017/12/1816 PCM的过程： 模拟图像模拟图像 空间采样空间采样 中间体中间体 幅值量化幅值量化 中间体中间体 数字图像数字图像 编编 码码 1 图像压缩概述 四. 图像压缩与压缩的必要性 例2： 资源卫星(EO1)一帧多光谱图像(10幅)的数据量 为： 181134511610=999961760=119.2Mb 卫星每天要获取很多幅图像，这些数据都先暂 时存储在卫星体内的磁性存储器中，当卫星飞 过地面接收站的有效接收区域时，迅速将这些 数据全部送到地面。 2017/12/1817 1 图像压缩概述 四. 图像压缩与压缩的必要性 3. 图像编码的目的：节省存储空间；减少传输时 间；利于处理，降低处理成本。 图像数据经过编码压缩、传输、解码以及重建图 像数据的流程如下图所示： 2017/12/1818 原始图像数据原始图像数据 编码器编码器 被压缩的图像数据被压缩的图像数据 重建图像数据重建图像数据 解码器解码器 被压缩的图像数据被压缩的图像数据 通道通道 1 图像压缩概述 五. 图像压缩分类 1. 从应用角度分类 静止图像编码，活动图像编码，二值图像编码 2. 从信息保持程度角度分类 有损压缩（保真度编码，特征抽取编码） 无损压缩（信息保持压缩，熵保持压缩） 3. 从具体的编码技术角度分类 空域法，变换域法 预测编码，变换编码，统计编码，等 2017/12/1819 2 图像压缩的保真度准则与压缩性能参数 一. 图像压缩中的保真度准则 图像品质的核心问题是逼真度问题。经过处理的图像（包括 经过压缩编码后的图像）与一个标准图像之间的偏差可以作 为图像逼真度（保真度）的度量。这一偏差，包括亮度，色 度，分辨率以及某些心理物理学参数。（偏差应该在允许的 范围之内） 1. 客观保真度准则 设f(x,y)是输入图像，f(x,y)是输出图像, 定义偏差 e(x,y)=f(x,y)-f(x,y)，则以下的参数可作为保真度准则： 2017/12/1820 一. 图像压缩中的保真度准则 2. 主观保真度准则 挑选一定数量的观察者进行评价。 2017/12/1821 12345671234567 很差较差稍差相同稍好较好很好很差较差稍差相同稍好较好很好 2 图像压缩的保真度准则与压缩性能参数 2017/12/1822 图像信息熵H(d)与平均码长R(d) 令： , , , , m m d dd dd dd d = = 是图像像素灰度级集合 其对应的频率为： ) )( (, ,),),( (),),( ( m m d dp pd dp pd dp p 定义： = = = = m m i i i ii i d dp pd dp pd dH H) )( (loglog) )( () )( ( （单位：比特/像素） 令： , , , , m m 是对应像素灰度级的编码长度 定义： = = = = m m i i i ii i d dp pd dR R ) )( () )( (（单位：比特/像素） 问题：如何度量编码方法的优劣？（速度，效率， 保真度） 二. 编码压缩的性能参数 2 图像压缩的保真度准则与压缩性能参数 2017/12/1823 = = = = m m i i i ii i d dp pd dp pd dH H) )( (loglog) )( () )( ( = = = = m m i i i ii i d dp pd dR R ) )( () )( ( H(d)：该图像的平均信息熵R(d)：平均编码长度。H(d)：该图像的平均信息熵R(d)：平均编码长度。 编码效率 冗余度 = = = = ) )( ( ) )( ( 原始图像的熵原始图像的熵 原始图像平均码长原始图像平均码长 d dH H d dR R r r r rd dR R d dH H = = = ) )( ( ) )( ( 2 图像压缩的保真度准则与压缩性能参数 冗余大致分为三类： 1）编码冗余 符号序列码字（码字长度） 2）像素间相关性冗余 帧间像素信息冗余，帧内像素信息冗余。 3）视觉冗余 人眼对所有视觉信息并不是都具有相同的敏感度； 人眼的空间分辨率，时间分辨率。 消除冗余能达到数据压缩的效果 2017/12/1824 2 图像压缩的保真度准则与压缩性能参数 第一代压缩编码 1948-1988年40年研究的以去除冗余为基础的编码 方法为第一代编码方法，主要是根据传统的信源编码 方法。（PCM, DPCM, 经典变换编码，统计编码等） 第二代压缩编码 八十年代以后，突破信源编码理论，结合分形、模型 基、神经网络、小波变换等数学工具，充分利用视觉 系统生理心理特性和图像信源的各种特性。 从实用方案角度来分，可分为三大类：预测编码，统计 编码，变换编码。 2017/12/1825 2 图像压缩的保真度准则与压缩性能参数 2017/12/1826 像素编码像素编码 变换编码变换编码 预测编码预测编码 位平面编码位平面编码 增量调制增量调制 熵编码熵编码 算术编码算术编码 DCT变换DCT变换 DPCM调制DPCM调制 第第 一一 代代 压压 缩缩 编编 码码 其它编码其它编码 行程编码行程编码 2 图像压缩的保真度准则与压缩性能参数 2017/12/1827 子带编码子带编码 模型编码模型编码 分层编码分层编码 分型编码分型编码 第第 二二 代代 压压 缩缩 编编 码码 2 图像压缩的保真度准则与压缩性能参数 3 统计编码压缩 一. 统计编码概述 根据图像像素灰度值出现的概率的分布特性而进行的 压缩编码叫统计编码。 熵与平均码字长度 1）H(d) < R(d)时，一定可以设计出某种平均码字长更 短的无失真编码方法。 2）平均码字长小于H(d)的无失真编码方法不存在。 熵编码 使编码后的图像的平均码字长度尽可能接近图像的熵H。 基本思路是：概率大的灰度级用短码字，概率小的，用 长码字。 2017/12/1828 3 统计编码压缩 二. 统计编码方法 1. 行程编码(RLE编码) （1）基本原理 通过改变图像的描述方式，来实现压缩。将一行中颜 色值相同的相邻像素用一个计数值和该颜色值来代替。 （2）举例说明 aaaabbbccdeeeeefffffff(共22*8=176 bits) 4a3b2c1d5e7f (共12*8=96 bits) （3）应用分析 适合行程较长的图像，一般不单独使用。 2017/12/1829 3 统计编码压缩 二. 统计编码方法 2. Huffman 编码（熵编码） 基本原理： 为了达到更大的压缩率，提出了一种方法， 就是将在图像中出现频率大的像素值给一个 比较短的编码，将出现频率小的像数值给一 个比较长的编码。 2017/12/1830 3 统计编码压缩 2. Huffman 编码 2017/12/1831 原图像输入原图像输入概率统计概率统计构造H树构造H树 生成H树生成H树 编码压缩编码压缩 存储存储 传输传输 解码复原解码复原 基本霍夫曼编码系统框图基本霍夫曼编码系统框图 3 统计编码压缩 2. Huffman 编码 算法： 1）将灰度级按概率大小进行排序（降序），每个灰度级 作为一个叶子结点，形成一棵树； 2）将两个根节点概率最小的树，合并（规则：这两个结 点构造一个双亲结点，双亲结点的概率大小是两者之 和）；重复1) 2), 直到只有一个树 为止； 3）设所有左后代为0，右后代为1。 特点： 优点：即时码；最优码。 缺点：当需要对大量符号进行编码时，构造最优 霍夫曼 码的计算量会很大。 2017/12/1832 Huffman 编码 2017/12/1833 x1x2x3x4x5x6x7x8 0.400.180.100.100.070.060.050.04 x8:0.04 0.09 x6:0.06 x5:0.07 0.13 x4:0.10 x3:0.10 0.19 0.23 x2:0.18 0.37 0.60 x1:0.40 1.0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 x1:1 x2:001 x3:011 x4:0000 x5:0100 x6:0101 x7:00010 x8:00011 x7:0.05 0 34 = = = = = = = = . . . . . . . . . . . . ) )( () )( ( i i i ii i d dp pd dR R 平均码长：平均码长： 信息熵：信息熵： = = = = = = = = . . . .loglog. . .loglog. . .loglog. . .loglog. . . .loglog. . .loglog. . .loglog. . .loglog. . ) )( (loglog) )( () )( ( i i i ii i d dp pd dp pd dH H % %. . ./ /. .(%)(%) ) )( ( ) )( ( = = = = = d dR R d dH H 编码效率：编码效率： Huffman 编码编码 2017/12/18 3 统计编码压缩 3. Shannon-Fano编码 算法： 1）将灰度级概率按非递增排序； 2）按概率之和相近或相等原则将灰度级集 一分为二； 3）将以上分割准则递归地应用到灰度级子 集，直至最终子集只有一个灰度级为止； 4）在分割过程中，分别给所分得的两个子 集赋予0和1。 2017/12/18 35 36 1010 10 10 10 10 10 0.040.050.060.070.100.100.180.40 x8x7x6x5x4x3x2x1 例：例： x1:00 x2:01 x3:100 x4:101 x5:1100 x6:1101 x7:1110 x8:1111 2017/12/18 Shannon-Fano编码Shannon-Fano编码 37 = = = = = = = = . . . . . . . . . . . . ) )( () )( ( i i i ii i d dp pd dR R 平均码长：平均码长： 信息熵：信息熵： = = = = = = = = . . . .loglog. . .loglog. . .loglog. . .loglog. . . .loglog. . .loglog. . .loglog. . .loglog. . ) )( (loglog) )( () )( ( i i i ii i d dp pd dp pd dH H % %. . ./ /. .(%)(%) ) )( ( ) )( ( = = = = = d dR R d dH H 编码效率：编码效率： 2017/12/18 Shannon-Fano编码Shannon-Fano编码 4.预测编码与变换编码压缩 一. 预测编码 预测编码（Predictive Coding)，是根据“过去” 的时刻的像素值，运用一种模型，预测当前的像 素值，预测编码通常不直接对信号编码，而是对 预测误差进行编码。当预测比较准确，误差较小 时，即可达到编码压缩的目的。 原理：对图像的一个像素的离散幅度的真实值， 利用其相邻像素的相关性，预测它的下一个像素 的可能值，再求两者差，对这种具有预测性质的 差值，量化，编码，就可以达到压缩的目的。 2017/12/18 38 39 预测编码示意图预测编码示意图 2017/12/18 输入输入 预测器预测器 n n 量化器量化器 编码器编码器 n n 解码器解码器 传输传输 n n 预测器预测器 n f n f n f n f n f 输出输出 40 预测器：预测器： ),( 21knnnn fffFf = n f 是根据前面几个像素的亮度值是根据前面几个像素的亮度值knnn fff , 21 nnn ff =预测而得：预测而得： 量化器量化器：对：对 n n进行舍入，整量化进行舍入，整量化 编码器编码器：可采用成熟的编码技术，如Huffman编码等：可采用成熟的编码技术，如Huffman编码等 解码器解码器：编码器的逆：编码器的逆 = = 1,),( 1 21k n lk kkknnnn afafffFf线性预测器：线性预测器： 2017/12/18 预测编码示意图预测编码示意图 41 例：例： = = 5 .0,),( 1 2 21k n nk kknnn afaffFf 246884210 24357863 24331447 246884210 f 预测器预测器 2017/12/18 预测编码示意图预测编码示意图 42 在预测编码中，最常用的是差分脉码调制在预测编码中，最常用的是差分脉码调制 （Differential Pulse Code Modulation, DPCM)，（Differential Pulse Code Modulation, DPCM)， 原理图如下所示：原理图如下所示： nnn ff= 输入输入 预测器预测器 n n 量化器量化器 编码器编码器 n n 解码器解码器 传输传输 n n 预测器预测器 n f n f n f n f n f 输出输出 ),( 21knnnn fffFf = 2017/12/18 预测编码示意图预测编码示意图 43 收端解码时的预测过程与发端相同，所用预测收端解码时的预测过程与发端相同，所用预测 器也相同，收端输出的信号是发端的近似值，器也相同，收端输出的信号是发端的近似值， 两者的误差是两者的误差是 nnnnnnn ffff= 注意：1）多点预测；注意：1）多点预测； x1x1x2x2 x3x3x x ) 3()2() 1()( 321 xfaxfaxfaxf= 2017/12/18 预测编码示意图预测编码示意图 44 3）预测系数随着不同的图像而不同，但对每幅3）预测系数随着不同的图像而不同，但对每幅 图像都计算预测系数太麻烦，也不现实，可参考图像都计算预测系数太麻烦，也不现实，可参考 前人得到的数据选择使用。在静止图像压缩的国前人得到的数据选择使用。在静止图像压缩的国 际标准(JPEG)中，对这种方法的前置点形式以及际标准(JPEG)中，对这种方法的前置点形式以及 预测系数有一推荐值可供参考。预测系数有一推荐值可供参考。 2)每行的最开始的几个像素无法预测，这些像2)每行的最开始的几个像素无法预测，这些像 素需要用其他方式编码，这是采用预测编码所素需要用其他方式编码，这是采用预测编码所 需要的额外操作；需要的额外操作； 2017/12/18 预测编码示意图预测编码示意图 4.预测编码与变换编码压缩 二. 变换编码 原理：图像数据经过正交变换后，其变换系数具 有一定的相互独立性，（例如，对于FT来说，频 普系数大的变换系数均集中在低频部分，而高频 部分的幅值均很小，因而可以对低频的变换系数 量化、编码和传输，对高频部分不处理，这样可 以达到图像压缩的目的。 2017/12/18 45 变换编码的一般系统框图变换编码的一般系统框图 5 图像编码与压缩标准 一. 图像编码标准： JBIG，H.26x，JPEG，MPEG等 二. 静止图像格式-JPEG 国际标准化组织（ID）和国际电报电话咨询委 员会（CCITT）联合成立的专家组JPEG（Joint Photographic Experts Group）于1991年3月 提出了ISO CDIO918号建议草案:多灰度静止图 像的数字压缩编码（通常简称为JPEG标准）。 这是一个适用于彩色和单色多灰度或连续色调 静止数字图像的压缩标准。它包括基于DPCM （差分脉冲编码调制）、DCT（离散余弦变换） 和Huffman编码的有损压缩算法两个部分。 2017/12/18 46 5 图像编码与压缩标准 JPEG压缩编码算法的主要计算步骤如下： 1）正向离散余弦变换(FDCT)。 2）量化(quantization)。 3）Z字形编码(zigzag scan)。 4）使用差分脉冲编码调制(differential pulse code modulation，DPCM)对直流 系数(DC)进行编码。 5）使用行程长度编码(run-length encoding，RLE) 对交流系数(AC)进行编码。 6）熵编码(entropy coding)。 47 2017/12/18 48 2017/12/18 JPEG压缩编码算法 5 图像编码与压缩标准 三. 活动图像格式-MPEG MPEG（Moving Pictures Experts Group）是 ISO/IEC/JTC/SC2/WG11的一个小组。它的工 作兼顾了JPEG标准和CCITT专家组的H.261标准， 于1990年形成了一个标准草案。 MPEG标准分成两个阶段:第一个阶段（MPEG- 1）是针对传输速率为 lMb/s到l.5Mb/s的普通 电视质量的视频信号的压缩；第二个阶段 （MPEG-2）目标则是对每秒30帧的720 x572 分辨率的视频信号进行压缩；在扩展模式下， MPEG-2可以对分辨率达1440Xl152高清晰度 电视（HDTV）的信号进行压缩。 2017/12/18 49 5 图像编码与压缩标准 三. 活动图像格式-MPEG MPEG-3：原本针对于HDTV(19201080)， 后来被MPEG-2代替。 MPEG-4：针对多媒体应用的图像编码标准。 是为了播放流式媒体的高质量视频而专门设 计的，它可利用很窄的带度，通过帧重建技 术，压缩和传输数据，以求使用最少的数据 获得最佳的图像质量。 MPEG-7：基于内容表示的标准，应用于多 媒体信息的搜索，过滤，组织和处理。 2017/12/18 50 本章小结 图像编码的必要性： 编码目的及原理 图像编码的分类： 统计编码、预测编码、变换编码等。 图像编码中的保真度准则： 客观（均方差、均方信噪 比）；主观。 编码的性能参数：熵、平均码长、冗余度、编码效率。 统计编码：行程编码、霍夫曼编码 预测编码、变换编码 图像编码的国际标准：JPEG、MPEG 2017/12/1851 52 回答问题回答问题 本章结束本章结束