多媒体搜索引擎.ppt

《多媒体搜索引擎.ppt》由会员分享，可在线阅读，更多相关《多媒体搜索引擎.ppt（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、多媒体搜索引擎多媒体文档及其内容理解(2)多媒体信息的存储压缩与编码多媒体信息都很大1百万字的小说：2MB10分钟CD质量音频：100MB10分钟普通电视质量视频：8.5GB直接存储难以承受如何节约存储空间？压缩3/8/20232Multimedia Search Engine压缩为什么数据可以被压缩？信息的表达形式有冗余Die Freiheit,die Liebe,Tun beide mir not:Mit Lust fr die LiebeGeh ich in den Tod,Doch opfr ich auch sieWenn die Freiheit bedroht!生命诚可贵爱情价更

2、高若为自由故两者皆可抛3/8/20233Multimedia Search Engine压缩为什么数据可以被压缩？信息的表达形式有冗余用典l“效田光故事”l“二桃杀三士”l“墨守成规”3/8/20234Multimedia Search Engine压缩为什么数据可以被压缩？冗余的本质数据交换的本质l从发送者向接收者传递信息3/8/20235Multimedia Search Engine压缩为什么数据可以被压缩？冗余的本质数据交换的本质l从发送者向接收者传递信息l但是，如果接收者有一些先验知识3/8/20236Multimedia Search Engine压缩为什么数据可以被压缩？冗余的本

3、质先验知识：可以更好地表示数据的模型收到的信息实际获得的信息先验知识预测器3/8/20237Multimedia Search Engine压缩为什么数据可以被压缩？冗余的本质先验知识：可以更好地表示数据的模型需要传递的信息实际传递的信息预测模型预测器反向预测器获得的信息3/8/20238Multimedia Search Engine压缩预测器如何预测？10101001110如果正反出现的概率各50%？无法预测3/8/20239Multimedia Search Engine压缩预测器如何预测？10101001110如果正面出现的概率90%？预测正面出现：命中率90%只需传递反面出现的情况3

4、/8/202310Multimedia Search Engine压缩预测器输入数据的概率分布不是完全均匀的福尔摩斯：跳舞的小人“你们也知道，在英文字母中最常见，它出现的次数多到即使在一个短的句子中也是最常见的。第一张纸条上的十五个符号，其中有四个完全一样，因此把它估计为是合乎道理的”3/8/202311Multimedia Search Engine压缩预测器输入数据的概率分布不是完全均匀的3/8/202312Multimedia Search Engine压缩预测器输入数据的概率分布不是完全均匀的如何把非均匀分布的信息实际用于压缩？l信息论l香农(Claude Shannon)lhttp:

5、/en.wikipedia.org/wiki/Claude_E._ShannonA Mathematical Theory of Communication 19483/8/202313Multimedia Search Engine压缩信息论消息(message)：收到的一个信息1,0A,B,C,D,天,地,玄,黄消息集报文(sequence of messages):一串消息3/8/202314Multimedia Search Engine压缩信息论香农：通信的模型传递的“东西”：信息l如何度量？3/8/202315Multimedia Search Engine压缩信息论信息的度量单个

6、消息的信息量消息s出现的概率符号集大小？对数底？与信息量的单位有关自信息如果正反概率相等：I(正)=log(1/0.5)=log(2)如果底为2，则：I(正)=1 比特(bit)3/8/202316Multimedia Search Engine压缩信息论信息的度量报文中消息的平均信息量l0,1，均匀分布lI(0)=1 bit,I(1)=1 bitl平均信息量 1 bitl0,1，分布0.9,0.1lI(0)=0.15 bit,I(1)=3.32 bitl平均信息量？l(0.15+3.32)/2=1.735 bit?3/8/202317Multimedia Search Engine压缩信息论

7、信息的度量报文中消息的平均信息量l报文中各个消息的出现概率是不同的！l按概率加权l0,1，分布0.9,0.1lI(0)=0.15 bit,I(1)=3.32 bitl(0.15*0.9+3.32*0.1)=0.467 bitl每收到一个这样的消息，获知0.467比特信息l可以压缩！熵3/8/202318Multimedia Search Engine压缩信息论0,1，分布0.9,0.1如何压缩？如果最小输出信息单位是1比特如果输入信息必须以单比特处理每个输入比特至少需要一个输出比特l无法压缩l必须至少去除一个限制3/8/202319Multimedia Search Engine压缩信息论0,

8、1，分布0.9,0.1如果输入信息可以联合处理多个bit报文可以很长00,01,10,110.81,0.09,0.09,0.01l000,0110,10110,11111l最短码长：1，最长码长：3l平均码长：0.81*1+0.09*2+0.09*3+0.01*3=1.29l1.29/2=0.645 1l熵为0.467编码3/8/202320Multimedia Search Engine压缩霍夫曼码(Huffman Coding)按输入消息的概率分布，编制最佳的码书码书(code book)：输入消息和输出码字的对应关系码字(code)：一个比特串可以被正确译码废话前缀码l一个码书中，任何码

9、字都不是别的码字的前缀3/8/202321Multimedia Search Engine压缩霍夫曼码(Huffman Coding)前缀码非前缀码会导致译码困难l000,0101,10110,11111l试译码：0110l也许可以译码，但必须查看后续符号如何根据概率分布构造最优的前缀码码书?霍夫曼树3/8/202322Multimedia Search Engine压缩霍夫曼码霍夫曼树000.81010.09100.09110.01A0.1B0.19C1010101000011010110111113/8/202323Multimedia Search Engine压缩霍夫曼码优点编解码均非

10、常简单编码效率非常接近熵l英文字母：熵4.5，霍夫曼码平均码长：4.7缺点给定概率分布，编码不唯一只能输出整数比特的码字3/8/202324Multimedia Search Engine压缩算术编码整个输入报文作为整体处理整个输入编码也以整体输出可以输出“小数码字”A,B，分布0.9,0.101ABAABA00.900.810.7290.810.7290.8019输出：区间中的任意一个数3/8/202325Multimedia Search Engine压缩算术编码需要无限精度的浮点运算不可能实现有限精度的整数实现？如果编码器和解码器都使用相同的舍入方式，则有限精度整数实现是可能的l普通实现

11、：采用二进制lRange Code：采用很高的进制3/8/202326Multimedia Search Engine压缩零阶熵编码（霍夫曼码，算术编码）利用消息非均匀分布的特性实现压缩平均码长接近消息集的熵可以非常接近，但很难等于，一定不可能小于需要消息的概率模型编码器和解码器都需要l如果概率模型不符合实际消息分布？l可能实际反而扩展数据大小l如何保证解码器使用编码器所使用的同一个概率模型？3/8/202327Multimedia Search Engine压缩零阶熵编码概率模型静态：整个编码过程中使用同一个概率模型l完全静态：编码器和解码器事先协商好概率模型lMPEG标准，JPEG标准l可

12、能不是最佳的l预先统计：先把需要编码的数据预先扫描一次，获得最佳的概率模型lJPEG标准l需要同时传递概率模型l运算量大，存储开销大，不适合大数据量应用3/8/202328Multimedia Search Engine压缩零阶熵编码概率模型动态：编码中依据前面输入的消息调整概率模型l只要编码器和解码器都按照相同的规则特征概率模型，即可保证解码出正确的信息l自适应编码l自适应霍夫曼码l较复杂，很少使用l自适应算术编码l自适应熵编码一般都是算术编码l算术编码一般都使用自适应技术3/8/202329Multimedia Search Engine压缩零阶熵编码自适应算术编码AABAA:1B:101

13、00.5A:2B:100.333A:3B:10.250.333A:3B:20.250.3A:4B:2假设：已经知道不同消息的个数如果不知道？3/8/202330Multimedia Search Engine压缩零阶熵编码自适应算术编码转义消息(ESC)AABAESC:101遇到A：尚未遇到过，先输出ESC01区间未变：等效于输出0bit以其它手段输出消息AESC:2A:10.6671A:2ESC:23/8/202331Multimedia Search Engine压缩零阶熵编码目前为止：只使用消息本身的信息进行编码“自信息”：只与自身有关的信息如果考虑前面出现过的消息？例：英文单词以th开

14、头的：l没有thh,thj,thk,thm,thn开头的单词l“_th”后面的字母的概率分布和“_”后面不一样l利用上下文进行更精确的预测3/8/202332Multimedia Search Engine压缩一阶熵编码利用前面一个消息来预测本次消息零阶概率表：统计单个消息的概率一阶概率表：统计跟在某个消息后的消息的概率l每个零阶概率表中的消息下连一个一阶概率表编码中：如果发现前一个消息的一阶概率表中有当前消息的记录，则使用该记录编码；如果没有，则利用该一阶概率表输出一个ESC，然后用零阶概率表输出本次消息l如果零阶概率表还没有？再ESC3/8/202333Multimedia Search

15、Engine压缩高阶熵编码(PPM:Prediction by Partial Match)一阶概率表还可接二阶概率表利用前面2个信息进行预测还可以接更高阶概率表内存需求量随阶的增加指数增加例：英语文字8阶熵：2.4（零阶熵：4.5）l等效于7阶熵编码估计的无穷阶熵：1.3l理论最佳压缩率(目前最佳：RK,1.89)如何现实地进行高阶预测？3/8/202334Multimedia Search Engine压缩压缩编码小结能够实现压缩的条件可以较准确地预测下一个消息l预测越准确，压缩率越高可以用于预测的信息预先的知识l压缩和解压缩器必须事先约定好报文中已经传递的消息l统计前面的消息预测后面的消

16、息l两个方面:(1)概率分布；(2)上下文l如何尽可能加长用于预测的上下文？3/8/202335Multimedia Search Engine压缩字典编码LZ77及其变种(滑动窗口)不吃葡萄倒吐葡萄皮吃葡萄不吐葡萄皮用什么预测最好？输出信息：三元组（指针，长度，字符）指针：指向前面最长匹配串长度：最长匹配串长度字符：输入消息的下一个字符3/8/202336Multimedia Search Engine压缩字典编码LZ77及其变种(滑动窗口)最长匹配：1(NULL,0,不)吃 葡 萄 不 吐 葡 萄 皮 不 吃 葡 萄 倒 吐 葡 萄 皮3/8/202337Multimedia Search

17、 Engine压缩字典编码LZ77及其变种(滑动窗口)吃 葡 萄 不 吐 葡 萄 皮 不 吃 葡 萄 倒 吐 葡 萄 皮(NULL,0,不)最长匹配：3(-9,3,倒)这个字有很大的概率找不到长匹配直接输出3/8/202338Multimedia Search Engine压缩字典编码LZ77及其变种(滑动窗口)吃 葡 萄 不 吐 葡 萄 皮 不 吃 葡 萄 倒 吐 葡 萄 皮(NULL,0,不)最长匹配：4(-9,3,倒)(-9,4,?)输出：3个三元组利用熵编码可以进一步压缩三元组LZ77的各种变种有很多细节上的差异（如：输出不同的三元组）致谢：复旦大学计算机系赵进教授http:/ Sea

18、rch Engine压缩字典编码LZ77及其变种(滑动窗口)ZIP，gzipl窗口大小：32KB7-zip(LZMA)l窗口大小：64KB-1024MBl比ZIP高30-70%压缩率的情况下，和ZIP差不多的速度l解决的问题：如何快速找到最长匹配l索引3/8/202340Multimedia Search Engine压缩字典编码LZ78及其变种维护一个字典，字典中记录了最有可能出现的词条。如果输入流中发现一个词条，则输出代号而不是词条本身。lGIF：LZW算法，字典4096项适合压缩超长串大量重复的文件(如卡通图片)不适合压缩短串经常重复的文件l如文字文档：LZ77更适合3/8/202341Multimedia Search Engine压缩基于各种变换的编码BTW，MTF，适合语音和图像的编码下一堂课3/8/202342Multimedia Search Engine