压缩搜索引擎教程

多媒体搜索引擎多媒体文档及其内容理解(3)压缩压缩编码小结能够实现压缩的条件可以较准确地预测下一个消息预测越准确,压缩率越高可以用于预测的信息预先的知识压缩和解压缩器必须事先约定好报文中已经传递的消息统计前面的消息预测后面的消息两个方面:(1)概率分布;(2)上下文如何尽可能加长用于预测的上下文压缩字典编码LZ77及其变种(滑动窗口)不吃葡萄倒吐葡萄皮……吃葡萄不吐葡萄皮用什么预测最好输出信息:三元组(指针,长度,字符)指针:指向前面最长匹配串长度:最长匹配串长度字符:输入消息的下一个字符压缩字典编码LZ77及其变种(滑动窗口)最长匹配:1(NULL,0,不)吃葡萄不吐葡萄皮不吃葡萄倒吐葡萄皮压缩字典编码LZ77及其变种(滑动窗口)吃葡萄不吐葡萄皮不吃葡萄倒吐葡萄皮(NULL,0,不)最长匹配:3(-9,3,倒)这个字有很大的概率找不到长匹配直接输出压缩字典编码LZ77及其变种(滑动窗口)吃葡萄不吐葡萄皮不吃葡萄倒吐葡萄皮(NULL,0,不)最长匹配:4(-9,3,倒)(-9,4,)输出:3个三元组利用熵编码可以进一步压缩三元组LZ77的各种变种有很多细节上的差异(如:输出不同的三元组)致谢:复旦大学计算机系赵进教授http://homepage.
fudan.
edu.
cn/~jzhao/course/mm2008/index.
htm压缩字典编码LZ77及其变种(滑动窗口)ZIP,gzip窗口大小:32KB7-zip(LZMA)窗口大小:64KB-1024MB比ZIP高30-70%压缩率的情况下,和ZIP差不多的速度解决的问题:如何快速找到最长匹配索引压缩字典编码LZ78及其变种维护一个字典,字典中记录了最有可能出现的词条.
如果输入流中发现一个词条,则输出代号而不是词条本身.
GIF:LZW算法,字典4096项适合压缩超长串大量重复的文件(如卡通图片)不适合压缩短串经常重复的文件如文字文档:LZ77更适合压缩字典编码小结优点可以利用超长的上下文Zip:32KB,7-zip:最大1GB速度快字符串匹配,无需复杂的概率运算缺点只能利用"重复"这一种冗余PPM:可以做复杂预测压缩听觉和视觉数据的压缩与文字数据有巨大的不同文字数据:较多的简单重复听觉和视觉数据很少简单的重复,但临近元素的值很相近"相似但不相同"B:150151152153……如何压缩压缩基于各类变换的编码把数据变换成易于压缩的形式再压缩把数据变换成某些元素大量重复的形式"某些":0及其附近的元素"某些"元素大量重复,则"另一些"元素少量出现概率分布变得不均匀于是可以使用熵编码什么样的变换适合用于压缩可逆的可以把概率分布变得不均匀(越不均匀越好)变换后的数据上下文相关性尽量小避免使用高阶熵编码压缩预测编码预测之后大量元素在0附近概率分布更不均匀相邻元素的值基本无相关性无需高阶统计10010010010110110010210010010010110210010310010010210210010110010010110210000-101-22000-12-33-1-202-110-1-12100压缩预测编码用前面元素预测后面元素,只编码预测误差LosslessJPEG不是JPEG-LSCBAX像素X的值可以由像素A、B和C来预测第一行非第一行的第一列压缩预测编码LosslessJPEG预测器选择:在文件头中指定,之后不再变化180100191100y=(a+b)/2=145r=145-180=-35二进制表示35,无前导0,需要6位"6"用霍夫曼编码处理(假设:101)-35的6位基1的补码:011100输出:101011100压缩预测编码JPEG-LS动态选择预测器预测值矫正Ifcmax(a,b)X~=min(a,b)}Else{Ifcmin(a,b)X~=max(a,b)ElseX~=a+b-c}CBAX180100191100X~=191diff=-11压缩预测编码DPCM用前面几个样本预测下一个样本样本个数:阶更进一步:如采样率高,则相邻样本差异很小如果差异基本上在(-1,1),则每个样本可用1位表示DM:(DeltaModulation)不再是PCM压缩预测编码DM粒状噪声斜率过载压缩预测编码ADM:AdaptiveDM量化步长增加斜率过载减小量化步长减小粒度噪声减小失真检测压缩预测编码基于预测和差分编码的语音标准G.
7218阶DPCM32kbps或16kbpsG.
722采样率拓展到8KHz通带50Hz-7KHz高质量话音64,56,48kbps压缩预测编码预测误差编码的问题可能出现大量的重复元素例如:80%的"0"是我们所希望的:可以更好地压缩但是:差异太大的分布编码效率不高霍夫曼编码:最小输出1bit,则任何概率超过50%的符号将降低编码性能算术编码:虽然可以输出"小数位",但往往使用自适应技术,则在开始的时候编码效率低尚无较准确的概率模型压缩游程码(RLE:Run-LengthEncoding)重复出现的元素,编码为(元素,重复次数)适合经过预测编码处理的数据、卡通图像、颜色数较少的图像等8888888666665555552222233333333(8,7)(6,5)(5,6)(2,5)(3,8)压缩压缩小结目前为止的压缩方法:无损或接近无损解压缩数据与压缩前数据无差别,或基本无差别好处:信息丢失少坏处:压缩率低所有信息都必须保留包括难以看见或难以听见的信息为什么不去除这些信息压缩变换编码把信息变换到易于数学处理的形式主要是频率域根据心理视觉/听觉的特性,把不易察觉的信息抹去压缩心理声学模型人耳对不同频率的声音敏感度差异很大等响度曲线:"听起来"相同响度的声音在不同频率的实际幅度无法听见的声音:次声波、超声波压缩心理声学模型频域掩蔽当一个频率的声音出现时,人耳对临近频率的声音的敏感度降低(需要更大幅度才能被听到)压缩心理声学模型时域掩蔽当一个声音出现时,人耳对临近时间的声音的敏感度降低(需要更大幅度才能被听到)压缩利用心理声学模型进行编码MPEGLayer-I,II子代编码傅立叶变换到频域,计算心理听觉掩蔽效应,从而计算各子代的量化级别只要量化噪声小于听觉阈值即无法被感知带通滤波器子带QQQBPBPBPFFT心理听觉模型压缩利用心理声学模型进行编码MPEGLayer-III(MP3)直接在频率域进行量化相当于划分更细的子带,可以进行更精细的量化控制DolbyAC-3类似MP3,主要针对较高质量声音对双声道声音,与MP3性能大致相当MDCT(ModifiedDCT)FFT心理听觉模型量化压缩MPEGLayerI,II,III码率与音质的大致关系声音质量带宽模式比特率压缩比率电话2.
5kHz单声道8kbps*96:1好于短波4.
5kHz单声道16kbps48:1好于调幅广播7.
5kHz单声道32kbps24:1类似调频广播11kHz立体声56-64kbps26-24:1接近CD15kHz立体声96kbps16:1CD>15kHz立体声112-128kbps14-12:1压缩心理视觉模型人眼感光的物理特性对三基色敏感:红、绿、蓝图像的采集和表示以三基色为基础人眼感光的心理特性分为亮度和色度,心理上基本独立亮度:光的强度;色度:光的色彩对亮度和色度的空间分辨率不同亮度:空间分辨率高色度:空间分辨率较低色度可以用较低的分辨率压缩心理视觉模型非一致采样的颜色空间把RGB图像信号变换到YUV颜色空间Y:亮度;U/V:两个色差信号亮度分辨率不变,色差信号分辨率降低水平方向和垂直方向均降低一半(4:2:0)大小减小一半,质量基本不变水平分析降低为1/4,垂直方向不变(4:1:1)为了处理方便(电视以行扫描方式重现图像)水平方向降低一半,垂直方向不变(4:2:2)用于质量要求较高的场合压缩心理视觉模型人眼对低频信号的失真比较敏感在均区域的斑点容易被发现在强的纹理区域的失真则不明显低频敏感,高频不敏感按频率编码低频用较小的量化步长保留更多信息高频用较大的量化步长取得更大的压缩率压缩基于频域变换的图像编码把图像变换到频率域在频率域中,对低频信号采取较小量化步长量化,对高频信号采取较大量化步长量化大量高频信号变成"0"用熵编码输出量化系数由于有大量的"0",数据得到压缩下一堂课