多媒体数据压缩考试要点

1、熵对数据压缩编码的理论意义信源的熵是对该信源进行无失真编码的极限对信源进行无失真编码的最低码率就是该信源的熵如果对信源进行编码的码率小于信源的熵，则这种编码是有失真的2、例：某一信源X有四个符号，其出现概率为：则该信源的熵为：=1.75bit/符号平均码长L==1/2*1+1/4*2+1/8*3=1.75bit/符号3、启示１：只要信源不是等概率分布的，就存在无失真数据压缩的可能性。启示２：既然()mHp非负，严格上凸，且等概率时达到最大，任一pj=1时达到最小值0，那么我们可以通过某中变换T:mmAB，使12{,,,}mmBbbb中某一个符号发生的概率尽可能大（1）使其他的尽可能小（0），这将有利于压缩，这就是变换编码的途径之一。4\研究在限定失真下为了恢复信源符号所必需的编码率，简称率失真理论。5.——表示输入为Ｘ，输出为Ｙ时，整个系统所具有的不确定程度6、7、可见，只要允许误差存在，就可以减少编码输出的字符数，降低码率。输出字符数越少，译码误差失真就越大。8、则平均失真9、10、率失真函数是在允许失真为D的条件下，信源编码给出的平均互信息量的下界。——有失真时的信源编码的逆定理当编码码率R()RD时，无论用何种编码方式，其平均失真必大于D8/18/14/12/143214aaaaA81log41*241log4121log)21()(xH1111101004321aaaaiilp(;)(,)log(,)ijijijHXYpabpab(;)()(/)()log()(,).log(/)(/).()()log()().(/).log()iiijijiijjiiiiijiiijjIXYHXHXYpapapabPabQbapapapapaQbaQb1111()(,).(,)().(/).(,)mnmnijijijiijijijDQpabdabpaQbadab()min(;)DQQRDIXY)(DR３.的性质：)()0(XHR)0(R，代表失真为0时的编码。)(DRD0时，无定义maxDmax,()0DDRD存在一个，使)(DR，为正，连续的，连续的下凹函数max0DD)(DR)(XHD0maxD11、变长码要正确识别码字起点就不是那么容易了，并且还存在着唯一可译性等问题。12、哈夫曼(Huffman)编码①将信源符号出现概率按减小的顺序排列；②将两个最小的概率进行组合相加，并继续这一步；③对每队组合中的上边指定为1，下边指定为0；④画出由每个信源符号概率到1、0处的路径，记下路径的1和0；⑤对于每个信源符号，写出1、0序列。则从右到左就得到哈夫曼码。哈夫曼编码的缺点：需要统计概率需要存储或传输码表13、游程长度(RL):由字符(或信号采样值)构成的数据流中各个字符重复出现而形成字符串的长度。形成串的字符、串的长度及串的位置14、MH/MR编码一ModifiedHuffman(MH)MH码的主要方法是：以多帧标准传真图像样本为统计依据，根据各种RL的出现的概率编出哈夫曼码表，实际过程只是查表，可以实时处理。由于规定每行标准取样1728点，又根据统计结果，实际RL在0—63居多，故MH编码表分为结尾码与组合基于码。编码规则如下：①RL=0—63,用一个相应的结尾码表示；②RL=64—1728，用一个组合基于码加一个补充结尾码，例如RL(白)=128,其编码为1001000110101补充结尾码为０(白)。若RL(白)=129，则其编码为10010000111数据流RLScaj③规定每行都从白游程开始，若实际扫描行由黑开始，则需要在行首加零长度的游程；每行结束时，要加行同步码EOL，每页文件第一个数据前加EOL;④为了同步操作的需要,规定一个编码的结束时间T最小为20ms，最大为5s，不是20ms的行需要再EOL之前填充足够的0，不可填在数据中间。⑤每行恢复像素应为1728个，否则认为该行的传输有误。⑥连续发6个EOL码，表示文件传输结束，转回控制规程，以后发送机将按照帧格式的CCITT建议Ｔ.30规定的控制信号速率发送各种报文后命令。15、MR编码是MH编码的扩展，是一种二维逐行编码方式。把一页文件沿列扫描方向分成若干组，每组有K行图像数据;第一行用一维MH编码，其余K-1行则利用行间相关性对当前像素模式识别后编码。MR编码方法1)迁移像素——沿扫描行由黑变白或由白变黑的的第一像素参考行：编码行：......a0a1a2b1b2a0：在编码行上起参考作用的一个迁移像素。在编码行的开始，a0为假想的白像素，位于该行第一个实际像素之前，在编码过程中，由前一次编码来确定。a1：在参考行上位于a0之后的下一个迁移像素。a2：在参考行上位于a1之后的下一个迁移像素。b1：在参考行上位于a0右边，且与a0颜色相反的第一个迁移像素。b2：在参考行上位于b1之后的下一个迁移像素。编码的模式READ方案将扫描行的各种变化归纳为三种格式，MRC就是识别编码行上的每一个迁移像素应属于哪一个模式，并输出相应的码字，从而编码简化，压缩比提高。特征:a1位于b2右边的一种模式；编码方法:通过模(用P表示)在通过模情况下，无论a0、b2多长，只用一个码字“0001”表示其长度。此后开始下一个模式编码，以b2正下方的像素作为下一个编码模式的参考模式a0。参考行：编码行：......a0a1b1b2a0'垂直模（用V表示）参考行：编码行：......a0a1a2b1b2特征:a1位于b2左边，且的一种模式113ab以a1作为下一个编码模式的a0编码方法:按下表的码字对的长度编码。11ab0000010VL(3)a1b1=3000010VL(2)a1b1=2010VL(1)a1b1=1a1在b1左面0000011VR(3)a1b1=3000011VR(2)a1b1=2011VR(1)a1b1=1a1在b1右面1V(0)a1b1=0a1正好在b1之下垂直001+M(a0a1)+M(a1a2)Ha0a1a1a2水平0001pa0b2通过码字符号需编码的像素模MR码表水平模(用H表示)特征:a1位于b2左边且a1b13的一种模式。编码方法:统计表明，对a1b1编码还不如直接对a0a1和a1a2两个游程长度编码的效率高。编码之后，a2作为下一次编码时的a016、2.算术编码原理算术编码就是将被编码的信息表示成实数0和1之间的一个间隔，信息越大，编码表示它的间隔就越小，表示这一间隔所需要的二进制位就越多。例：假定信源中可能出现的符号有a,e,I,o,u,l，出现的概率如下，用算术编码对输入串eaiil编码2.0,0字符概率范围（range）[rangelow,rangehigh)a0.2e0.35.0,2.0i0.16.0,5.0o0.28.0,6.0u0.19.0,8.0l0.11,9.001aeioul定义：range(n)=high(n)-low(n)。下一次low(n+1)=low(n)+range(n)*rangelowhigh(n+1)=low(n)+range(n)*rangehig初始high(0)=1，low(0)=0。low=0+1*0.2=0.2high=0+1*0.5=0.5range=high–low=0.5-0.2=0.3e编码过程alow=0.2+0.3*0=0.2high=0.2+0.3*0.2=0.26range=high–low=0.26-0.2=0.06．．．1）编码过程0.26)[0.2a0.26)[0.23i0.2336)[0.233i0.2336)[0.23354l0.5)[0.2e1)[0初始highlow区间范围编码字符第４章量化编码1、2、量化就是将连续取值的信号x(n)影射为离散取值的y(n)，即()[()]ynQxn，使得y(n)能够很好地逼近x(n).3、4、5、１．均匀量化器假定目的：寻找，使最小化2q12221([])()()()kkKxqxkxxkxQxpxdxxxpxdx量化标量量化（ScalarQuantization)矢量量化（VectorQuantization)两种方法给定表示值的个数，利用x的pdf来寻找最佳值均匀量化：简单容易实现非均匀量化：复杂，有一定收益选择均匀的量化器，但具有不同的量化步长更实用，JPEG/MPEG使用12221([])()()()kkKxqxkxxkxQxpxdxxxpxdx210210log()xqSNRdB例：对于２阶量化器，设计最佳２.非均匀量化器两种实现方法对x进行预处理，通过非线性函数，然后均匀量化。量化器，最小化2qCompanding(Compression-expanding)压－扩，实现简单常在语音编码中使用，如Ａ－律，－律等码书是是预先设计好的，包含了L个码书矢量i=1,2,3……L）；编码的比特率由码书的大小Ｌ决定．例：码书信号传输到解码端解码信号量化误差码书设计(LBG)法初始化码书yi(i=1,2?L)训练矢量将每个矢量分配给当前的蜂窝计算新的中心点新码书iy第五章预测编码（PredictiveCoding）1、DPCM例：利用信号的前一个取样值来预测当前取样值,即,选择怎样的a使预测误差最小？1KX1ˆKKaXXKX估计值的均方误差2222211ˆ2EKKKKKKEXXEXaEXXaEX自相关函数：,ijRijEXX在数据序列平稳过程条件下)(,jiRjiR22(0)2(1)(0)ERaRaR求使最小时的a2E22(1)2(0)0(1)(0)ERaRaRaR此时222min(1)(0)(1)(0)(0)ERRaRR根据自相关函数的性质(1)(0)RR2min1(0)EaR则当信号为零均值时，误差信号的方差比原信号的方差小。熵是概率分布的函数，分布越均匀熵越大，分布越集中，则熵越小。差分脉冲编码调制（DifferentialPulseCodeModulation,DPCM）Xk++-量化器编码器ekekkk'^^+++预测器XX发送端S(k)矢量量化：使用N个相邻幅值的相关性，将N维空间分割成一个一个蜂窝，这种分割比标量量化更为有效．缓冲器（形成长度为n的矢量）VQ(比较和选择)码书Y传输矢量地址重建（在码书中查表）码书Yy(n)x(n)差值信号原始图象-255255幅度P用传输差值信号代替传输原始图像信号，会使传输的码率降低————预测法图像压缩编码的基本依据解码器ek^^+预测器X接收端S(k)+X（k）’5.2最佳线性预测设集合{X}表示信号序列，K时刻的信号值用过去N个信号值的线性组合来预测KX1ˆNKiKirXaXKKKXXeˆ22ˆekkEXX均方误差Niaaie......2,102NRRRaaaRNRNRNRRRNRRRN1002120111021第六章变换编码1.正交变换（也称酉变换），是线形变换的一种特殊形式①上式是可逆的。②满足正交性设M*N图象阵列f(m1,n1)的正向变换产生M*N的变换图象阵列，11112211112200(,)(,).(,;,)MNmnPmnFmnAmnmn2200mMnN1122(,;,)Amnmn表示正变换核反变换则是从变换域映射回空间域22111122112200(,)(,).(,;,)MNmnFmnPmnBmnmn1100mMnN1122(,;,)Bmnmn表示反变换核如果线性变换满足下面的正交条件，则称之为正