四川大学计算机学院多媒体基础无损压缩

多媒体技术基础四川大学计算机学院陈虎[e-mail]数字化原理1模拟信号模拟信号指幅度的取值是连续的（幅值可由无限个数值表示）。现实中涉及的许多媒体对象是模拟信号例如：声音、图像、视频等数字信号数字信号是人为抽象出来的在时间上的不连续信号，是离散时间信号的数字化表示，通常由模拟信号获得。计算机处理的对象是数字信号（二进制数“0”和“1”）例如：英文字符以的ASCII代码，汉字字符的国标GB2312-80代码表示都是二进制数字串多媒体系统的数模与模数转换传感器(声音、图像、视频等--模拟）A/D计算机（数字）输出设备（数字）D/A输出设备（声音、电视--等模拟）模数转换-采样概念：从连续时间信号中提取离散样本的过程；或者说在某些离散的时间点上提取连续时间信号值的过程称为采样。采样按采样间隔可分为:均匀采样与非均匀采样。采样的必要性例如，电影的连续画面，实际上是由一组时间样本快速播放实现的，数字通信系统，微处理器系统对连续时间信号的处理，都是通过采样来实现的。采样是连续时间信号和离散时间信号之间的桥梁，对连续信号而言，随着数字处理技术的发展，越来越迫切地要求连续信号的离散化。采样示例采样当取出的样本一样时，样本对应的连续时间函数却不是唯一的。采样此外，对同一个连续时间信号，当采样间隔不同时也会得到不同的样本序列。结论：没有任何条件限制的情况下，从连续时间信号采样所得到的样本序列，不能唯一地确定原来的连续时间信号，即：一个连续时间信号必须在某一种条件下才能由其样本来表示。采样分析采样样本：采样函数：nnTttp)()(nnTttx)()()()(nnTtnTx)()()(tptxtxp采样分析已采样信号的频谱：采样函数频谱：)2(2)(kTkTjP)()(21)(jPjXjXPkskjXT)((1原连续时间信号：)()(jXtxMMsMMs采样分析对连续时间信号在时域理想采样，就相当于在频域以采样频率s为周期延拓，幅值减小1/T。要使频谱不混迭，就必须使信号带限，且MsMMs2上述即为时域采样的约束条件从而我们得到怎样抽取样本，样本才能唯一地表征原信号的取样条件，下面为上述分析的一个完整总结－－采样定理。采样定理设是某一个带限信号，在||M时，X（j）=0。如果采样频率s2M，其中s＝2/T,那么就唯一地由其样本所确定。已知这些样本值，我们能用如下办法重建：让采样后的信号通过一个增益为T,截止频率大于M，而小于（sM）的理想滤波器，该滤波器的输出就是。2M称为奈奎斯特率；M称为奈奎斯特频率。)(tx)(nTx)(tx)(tx数据压缩2压缩的必要性音频、视频的数据量很大，如果不进行处理，计算机系统几乎无法对它进行存取和交换。例如：一幅中等分辨率（640×480）的真彩色图像（24b/像素），它的数据量约为0.9MB/帧，若要达到每秒25帧的全动态显示要求，每秒所需的数据量约为22MB。对于声音也是如此，CD音质的声音每秒将有约为172KB的数据量。信息论1948年C.E.Shannon香农发表了题为“通信的数学理论”的论文。运用通信技术与概率论、随机过程、数理统计的方法系统讨论了通信的基本问题，得出了几个重要而带有普遍意义的结论：1.阐明通信系统传递的对象就是信息2.对信息给予科学的定量描述3.提出了信息熵的概念信息论科学体系香农信息论压缩理论有失真信源编码无失真信源编码率失真理论压缩编码等长编码定理变长编码定理最优码构成Huffman码Fano码传输理论有噪声信道编码理论码构成纠错码代数编码卷积码网络信道网络信息理论网络最佳码保密理论保密系统的信息理论保密码信息论之父TheFatherofInformationTheory——ClaudeElwoodShannonBorn:30April1916inGaylord,Michigan,USADied:24Feb2001inMedford,Massachusetts,USA熵定义：设随机变量X，取值空间Ω，Ω为有限集合。X的分布密度为p(x)，p(x)=P(X=x)x∈X，则该随机变量的取值不确定程度，即其熵为：当使用log2时，熵的单位为比特反映一个信源发出不同信号，具有的平均信息量。2()()()log()0log00,loglogxHXHppxpxallpossiblevaluesDefine熵为什么能够进行压缩信息论认为：若信源编码的熵大于信源的实际熵，该信源中一定存在冗余度（信息熵冗余）。冗余的基本概念指信息存在的各种性质的多余度举例：（1）广播员读文稿时每分钟约读180字，一个汉字占两个字节；文本数据量为360B；（2）如果对语音录音，由于人说话的音频范围为20Hz到4kHz，即语音的带宽为4kHz，若设量化位数为8bit,则一秒钟的数据量为：4×2×8=64kbit/s=8KB/s则一分钟的数据是480KB。360B480KB数据冗余的类别空间冗余时间冗余统计冗余信息熵冗余结构冗余知识冗余视觉冗余听觉冗余数据冗余的类别●空间冗余规则物体和规则背景的表面物理特性都具有相关性，数字化后表现为数据冗余。●时间冗余序列图像（如电视图像和运动图像）和语音数据的前后有着很强的相关性，经常包含着冗余。在播出该序列图像时，时间发生了推移，但若干幅画面的同一部位没有变化，变化的只是其中某些地方，这就形成了时间冗余。数据冗余的类别空间冗余和时间冗余是把图像信号看作概率信号时反应出的统计特性，因此，这两种冗余也被称为统计冗余。●统计冗余●信息熵冗余信息熵实际情况又称编码冗余。信息熵是指一组数所携带的信息量。●结构冗余数字化图像中的物体表面纹理等结构往往存在着冗余数据冗余的类别由图像的记录方式与人对图像的知识差异所产生的冗余称为知识冗余。●知识冗余人类的视觉系统对于图像场的注意在非均匀和非线性的，视觉系统并不是对图像的任何变化都能感知。●视觉冗余●听觉冗余人耳对不同频率的声音的敏感性是不同的，并不能察觉所有频率的变化，对某些频率不必特别关注，因此存在听觉冗余。信息冗余从信息论关系中图像信息中冗余信息，如果一个图像的灰度级编码，使用了多于实际需要的编码符号，则该图像包含了信息冗余例：如果用8位表示下面图像的像素，我们就说该图像存在着编码冗余，因为该图像的像素只有两个灰度，用一位即可表示。统计冗余从统计的观点，某点像素的灰度与其邻域灰度有密切关系。因此任何给定的像素值，原理上都可以通过它的相邻像素预测到，单个像素携带的信息相对是小的。对于一个图像，很多单个像素对视觉的贡献是冗余的。例：原图像数据：234223231238235压缩后数据：23411-8-73空间冗余规则物体表面有相关性，数字化后表现出冗余。图像相邻像素之间色彩、明度相同或相似，产生信息（有意义的内容）冗余时间冗余时间发生了推移，若干幅画面的同一部位没有变化，于是产生了冗余t结构冗余数字化图像中具有规则纹理的表面产生的冗余。取其中一块编码，其余只记录坐标视觉心理冗余一些信息在一般视觉的处理中比其它信息的相对重要程度要小，可以忽略不计，这种信息就被称为视觉心理冗余。33K15K数据压缩的评价-压缩比设：n1和n2是输入数据和输出数据压缩比为：CR=n1/n2例如：图像512×480，24位输入＝(512×480×24)/8=737280B输出15000B压缩比＝737280/15000＝49相对数据冗余：•RD=1–1/CR=(n1-n2)/n2数据压缩的评价-压缩质量客观质量评价：压缩过程对信息的损失能够表示为原始信息与压缩并解压缩后信息的函数。（信噪比（SNR））例如，图像中112001(,)(,)HWijMSEsijcijWH21025510logPSNRMSE数据压缩的评价-压缩质量主观质量评价：以人的主观感受作为评价标准。例如：通过视觉比较两个图像，给出一个定性的评价，如很粗、粗、稍粗、相同、稍好、较好、很好等，可以对所有人的感觉评分计算平均感觉分来衡量。评分评价说明1优秀的优秀的具有极高质量的图像2好的是可供观赏的高质量的图像，干扰并不令人讨厌3可通过的图像质量可以接受，干扰不讨厌4边缘的图像质量较低，希望能加以改善，干扰有些讨厌5劣等的图像质量很差，尚能观看，干扰显著地令人讨厌6不能用图像质量非常之差，无法观看压缩解压缩速度算法复杂－压缩解压慢，压缩效果好算法简单－压缩解压快，压缩效果差在许多应用中，压缩和解压可能不同时用，在不同的位置不同的系统中。所以，压缩、解压速度分别估计。例如静态图像中，压缩速度没有解压速度严格；动态图像中，压缩、解压速度都有要求，因为需实时地从摄像机或其他设备中抓取动态视频。压缩编码的分类数据压缩(datacompression)与信号编码(signalcoding)往往含义相同压缩(compress)解压缩/还原/重构(decompress)编码(encode/coding)解码/译码(decode)相关学科：信息论、数学、信号处理、数据压缩、编码理论和方法压缩编码的分类编码压缩的方法目前有很多，其分类方法根据出发点不同而有差异。一般根据根据解码后数据与原始数据是否完全一致将编码压缩分为：无损压缩编码有损压缩编码压缩编码的分类无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。图像、声音压缩编码的分类压缩有损压缩无损压缩行程编码LZW编码哈夫曼编码算术编码无损预测编码位平面编码有损预测编码分形编码模型编码子带编码神经网络编码变换编码K-L变换Haar变换Walsh.Hadamard变换离散余弦变换离散傅立叶变换斜变换小波变换压缩编码的分类从信息语义角度分为：熵编码、源编码和混合编码熵编码(entropyencoding)（也称平均信息量编码）熵编码是一种泛指那些不考虑被压缩信息的性质的无损编码。它是基于平均信息量的技术把所有的数据当作比特序列，而不根据压缩信息的类型优化压缩。也就是说，平均信息量编码忽略被压缩信息的语义内容。如RLE（runlengthencoding行程编码）、LZW（Lempel-Ziv-Walch基于词典的编码算法）、Huffman编码。压缩编码的分类源编码(SourceCoding)源编码的冗余压缩取决于初始信号的类型、前后的相关性、信号的语义内容等。源编码比严格的平均信息量编码的压缩率更高。当然压缩的程度主要取决于数据的语义内容，比起平均信息量编码，它的压缩比更大。简而言之，利用信号原数据在时间域和频率域中的相关性和冗余进行压缩的有语义编码。如：预测编码：DM、ADPCM变换编码：DCT、DWT分层编码：如子采样、子带编码其他编码：如矢量量化、运动补偿、音感编码压缩编码的分类混合编码(hybridcoding)混合编码=熵编码+源编码大多数压缩标准都采用混合编码的方法进行数据压缩，一般是先利用信源编码进行有损压缩，再利用熵编码做进一步的无损压缩。如H.261、H.263、JPEG、MPEG等。压缩编码的分类此外，也可根据不同的依据对数据的压缩算法进行其它不同的分类，如：按作用域在空间域或频率域：空间方法、变换方法、混合方法按是否自适应：自适应性编码和非适应性（静态）编码按码长：定长码和变长码香农-范诺香农-范诺编码(Shannon–Fanocoding)在香农的源编码理论中，熵的大小表示非冗余的不可压缩的信息量在计算熵时，如果