转 算术编码算法的分析与实现
转算术编码算法的分析与实现
[转]算术编码算法的分析与实现2011-06-09 14：20本论文题目：算术编码算法的分析与实现，作者：叶叶，于2010年10月16日在编程论坛上发表。页面地址：。本论文全文及相关配套程序可以在上述页面中下载。请尊重他人劳动成果，转载或引用时请注明出处。
目录
1前言2 2理论2 2.1编码2 2.2解码3 3改进4 3.1整数运算4 3.2正规化5 4实现8 4.1编码8 4.2解码10 4.3统计模型11 5分析12 6结束语12
参考文献13
附录13
算术编码算法的分析与实现
作者：叶叶(网名：yeye55)
摘要：分析了算术编码的理论基础，着重介绍WNC算法的实现方式。详细讨论了算术编码原理、正规化操作、WNC算法代码实现等技术。给出了一个切实可行的应用程序。
关键词：算术编码；正规化；Delphi
中图分类号：TP301.6 1前言
早在1948年C.E.Shannon提出信息论[1]的时候，就提出了算术编码的思想。但是经过多年的研究，许多学者认为算术编码是无法实现的。算术编码要求进行无限精度的实数运算，这在仅能进行有限精度运算的计算机系统上是无法进行的。随着研究的深入，终于在1987年Ian H.Witten、Radford M.Neal和John G.Cleary发表了一篇论文[2]，提出了一种基于整数运算的算术编码实现算法。该算法后来被命名为CACM87，并应用于ITU-T的H.236视频编码标准。也有学者根据作者姓名将该算法称之为WNC算法。WNC算法是一个实用性算法，它可以应用在许多方面。在Witten等人的论文[2]中给出了一个使用C语言编写的WNC算法实现程序的源代码(以下简称"WNC源代码")。在许多时候，WNC源代码已经作为算术编码的范本程序
来使用。本文将分析算术编码的理论基础，并着重介绍WNC算法的实现方式。同时给出一个在Delphi 7.0下开发，使用算术编码算法压缩数据的应用程序。
2理论
2.1编码
算术编码将整个要编码的数据映射到一个位于[0,1)的实数区间中。并且输出一个小于1同时大于0的小数来表示全部数据。利用这种方法算术编码可以让压缩率无限的接近数据的熵值，从而获得理论上的最高压缩率。
算术编码进行编码时，从实数区间[0,1)开始。按照符号的频度将当前的区间分割成多个子区间。根据当前输入的符号选择对应的子区间，然后从选择的子区间中继续进行下一轮的分割。不断的进行这个过程，直到所有符号编码完毕。对于最后选择的一个子区间，输出属于该区间的一个小数。这个小数就是所有数据的编码。现在来举个例子。假设一份数据由"A"、"B"、"C"三个符号组成。现在要编码数据"BCCB"，编码过程如图2.1所示。
图2.1"BCCB"的编码过程
首先说明一点，这里使用的是自适应模型。也就是说一开始时，三个符号的频度都是1。随着编码的进行再更新频度。另外，在计算时理论上要使用无限小数。这里为了说明方便，四舍五入到小数点后4位。
观察图2.1可以发现算术编码的过程。首先，算术编码是从区间[0,1)开始的。这时三个符号的概率都是1/3，按照这个概率分割区间。第一个输入的符号是"B"，所以我们选择子区间[0.3333,0.6667)作为下一个区间。输入"B"后更新频度，根据新的概率对区间[0.3333,0.6667)进行分割。这时输入的符号是"C"，我们可以选择子区间[0.5834,0.6667)。继续更新频度、分割区间、选择子区间，直到符号全部编码完成。我们最后得到的区间是[0.6390,0.6501)。输出属于这个区间的一个小数，例如0.64。那么经过算术编码的压缩，数据"BCCB"最后输出的编码就是
0.64。
2.2解码
算术编码进行解码时仅输入一个小数。解码前首先需要对区间[0,1)按照初始时的符号频度进行分割。然后观察输入的小数位于那个子区间。输出对应的符号，选择对应的子区间，然后从选择的子区间中继续进行下一轮的分割。不断的进行这个过程，直到所有的符号都解码出来。整个过程相当于编码时的逆运算。
在我们的例子中，输入的小数是0.64。首先，初始时三个符号的概率都是1/3，按照这个概率分割区间。观察图2.1可以发现0.64落在子区间[0.3333,0.6667)中，
于是可以解码出"B"。并且选择子区间[0.3333,0.6667)作为下一个区间。输出"B"后更新频度，根据新的概率对区间[0.3333,0.6667)进行分割。这时0.64落在子区间[0.5834,0.6667)中，于是可以解码出"C"。按照上述过程进行，直到所有的符号都解码出来。可见，只需要一个小数就可以完整还原出原来的所有数据。
3改进
3.1整数运算
上一节中描述的算法，在当前的计算机系统上是很难实现的。尤其是无限精度的实数运算。所以在实现的时候，需要对算法做一些改进。使得它可以在当前的计算机系统上较快的运行。当然，这种改进是以降低运算精度为代价的。也就是说，这种改进实际上会降低算法的压缩率。但是，它会使算法的实现成为可能。
观察前面描述的算法过程可以发现，运算时区间的上下沿都是小于1的小数。那么我们可以省略0和小数点，仅仅使用小数的尾数来表示小数。省略0和小数点后的尾数，实际上就是一个无限大的整数。使用无限整数的部分高位来表示整数，并在这些整数上进行整数运算就可以模拟出实数运算。在我们的例子里，可以使用区间[3333,6667)来表示区间[0.3333,0.6667)。最后可以输出64来表示0.64。
另外，分割区间、选择子区间的过程，相当于将一个区间映射到另一个更小的区间中(以下简称"映射区间")。如果我们知道一个符号的频度。以及符号值小于该符号的其它符号的频度总计(以下简称"累积频度(Cumulative Frequency)")。还有到目前为止所有符号频度的总计(以下简称"总计频度(Total Frequency)")。那么就可以根据这些频度信息，从当前区间中计算出映射区间。计算的公式如下。
Range=High-Low+1 High=Low+Range*(CumFreq+Freq)div Total-1
Low=Low+Range*CumFreq div Total
其中Low表示区间的下沿；High表示区间的上沿；Range表示区间的范围；Freq 表示符号频度；CumFreq表示累积频度；Total表示总计频度。这些变量中保存的都是整数，并进行整数运算。其中div表示整除。另外需要注意一点，这里使用闭区间[Low,High]，而不是使用右开区间[Low,High)。
在我们的例子里，实数运算时四舍五入到小数点后4位。那么在整数运算时可以采用4位整数来进行。初始区间可以设定在[0,9999]的闭区间中。按照上述公式进行编码计算所得的结果如表3.1所示。
输入数据输入符号映射区间区间范围
""[0000,9999]10000
"B"B[3333,6665]3333
"BC"C[5832,6665]834
"BCC"C[6332,6665]334
"BCCB"B[6387,6498]112
表3.1整数运算的区间变化
将表3.1中的数据与图2.1中的数据进行对比可以发现，整数运算会降低运算精度。整数运算时最后映射到区间[6387,6498]，实数运算时最后映射到区间
[0.6390,0.6501)。由于精度降低运算出现了误差，但是我们仍旧可以输出64代替0.64来表示整个数据。所以这种精度的降低是在允许的范围内。
在解码的时候也可以进行整数运算。根据输入的整数数值、当前区间的下沿和总计频度，可以计算出一个估算出来的累积频度(以下简称"估算频度(Estimate Frequency)")。其计算公式如下。
Range=High-Low+1 EstFreq=((Value-Low+1)*Total-1)div Range
其中，Value表示输入的整数数值；EstFreq表示估算频度。利用估算频度在当前的累积频度表中查找，当满足CumFreq≤EstFreq 在我们的例子中，输入的整数数值是64。但是64本质上是0.64，所以在参与运算时要将64扩展成6400。初始时区间的范围同编码时是一样的，从[0,9999]开始。利用6400进行解码，其过程如表3.2所示。 映射区间估算频度累积频度解码符号 A BC [0000,9999]1 01 2B [3333,6665]3 01 3C [5832,6665]3 01 3C [6332,6665]1 01 3B 表3.2整数运算的解码过程 可以看出利用一个整数数值64，就可以解码出全部数据。另外，观察解码过程可以发现。在解码时不仅要计算映射区间，还要计算和查找估算频度。所以算术编码的解码过程通常要比编码过程慢。 在本小节中给出的计算公式都来自WNC源代码。观察这些计算公式可以发现，有许多运算是重复的。这意味着，这些公式还有改进的可能。在本文的第4节中将给出改进后的计算方法。 3.2正规化 上述算法实际上是无法实现的。观察表3.1可以发现，随着编码的进行区间范围会越来越小，最后区间范围会趋向0。如果编码较长的数据，区间范围为0时就无法继续编码。解决这一问题的方法是使用正规化(Renormalization,又称"归一化")。正规化操作就是当区间的上下沿满足一定的条件时，将一定的位数从区间中移出，同时对区间进行一次放大。使用正规化操作，可以在有限区间上模拟无限区间的运算。当然这种模拟同样会降低精度，但是它让无限区间的运算成为可能。下面就来介绍正规化操作的过程。 上一节已经说过，区间的运算可以转换为整数运算。而区间的上下沿都是用整数来保存。在实现的时候，都是进行二进制整数运算。在本节中为了说明方便全部使用二进制整数来表示区间的上下沿。那么对于一个区间的上下沿有可能出现以下两中情况。 [00101101,或[10101101, 01001011]11001011] 情况1情况2 可以发现这两种情况中，区间上下沿的最高位都是相同的。根据前面对算法的描述，计算时区间总是映射到一个更小的区间中。那么当区间上下沿的最高位相同时，在后续的计算中最高位将不会再发生变化。这意味着我们可以将最高位移出区间并输出。同时将区间的下沿左移1位，将区间的上沿左移1位加1。这样在输出一个二进制位的同时，对区间进行了扩展。其过程如下所示。 0←[01011010,或1←[01011010, 10010111]10010111] 区间的上下沿还会出现其它情况。特别的，如果区间上下沿的最高位不相同，而次高位与最高位只相差一个1。那么可能会出现一个极端的情况，如下所示。 [01111111, 10000000] 以上区间的范围只有1。实际上此时已经无法继续编码了。为了避免出现这种情况，当区间上下沿的最高位不相同时，还需要检查次高位。如果下沿的次高位为1，而上沿的次高位为0。那么需要忽略次高位，同时对区间进行一次扩展。另外，需要记录一下我们忽略了一个次高位。因为，我们只是忽略它并没有抛弃它。当出现这种情况时，我们并不知道次高位的趋向。随着区间的变化，次高位可能趋向1也有可能趋向0。所以现在先将它记录下来并忽略掉，等到区间变化趋向稳定后再输出。另外，这种情况可能会连续出现。所以需要记录忽略次数，输出时要按忽略次数输出。忽略次高位，同时对区间进行扩展的操作过程如下所示。 [01011010,→[00110100, 10010111]10101111] 情况3 如果当前有未输出的次高位，又遇到上述三种情况，那么需要区别对待。当遇到情况1时，可以确定忽略的次高位趋向0。此时可以输出0，以及按忽略次数输出多个1。然后扩展区间。当遇到情况2时，可以确定忽略的次高位趋向1。此时可以输出1，以及按忽略次数输出多个0。然后扩展区间。当遇到情况3时，仍然无法确定忽略次高位的趋向。所以此时将忽略次数加1，再次忽略次高位并扩展区间。 在实现的时候为了计算方便，可以设定一个区间的最大范围。最大范围的取值为2的次方数。初始时区间的大小就是最大范围。那么，根据前面的算法描述可以断定，区间的上下沿变化不会超过最大范围。我们将最大范围等分为4份，用虚线表示。将区间上下沿的变化情况用实线表示，并在虚线中标示出来。如图3.1所示。 图3.1区间变化的三种情况 图3.2区间变化的另外三种情况 当区间的上下沿是情况1和情况2时。由于最大范围的取值为2的次方数，那么可以断定此时区间上下沿的最高位是相同的。情况1的区间位于下半区，上下沿的最高位为0；情况2的区间位于上半区，上下沿的最高位为1。类似的，情况3的区间位于中间区。区间的下沿位于下半区，其最高位为0，次高位为1；区间的上沿位于上半区，其最高位为1，次高位为0。上述这三种情况都需要进行正规化操 作。除此之外，区间上下沿的变化还有另外三种情况。这三种情况可以不进行正规化操作。直接从当前区间开始，进行下一轮的编码。这三种情况如图3.2所示。 综上所述，有三种情况需要进行正规化操作。对于有未输出次高位的情况，可以合并一起处理。对于情况1和情况2，在输出最高位后可以检查忽略次数是否为0。对于情况3，可以直接对忽略次数加1。另外，在解码的时候同样需要进行正规化操作。而且，解码时正规化的操作要和编码时正规化的操作相一致。唯一不同的是，解码时扩展区间需要输入一个位，以填补移出的空位。 4实现 4.1编码 本文中编写的实现代码主要基于WNC源代码，但同时进行了一些修改。修改的部分将在本节中进行介绍。现在先来看代码的实现。在实现代码的时候我们先要定义一些常量和变量。如下所示。 01 const 02 Top=Cardinal(1 shl 31)；//最大范围 03 Half=Top shr 1；//最大范围的一半 04 Quar=Half shr 1；//最大范围的四分之一 05 var 06 Low,High,Range,Follow,Value：Cardinal； 代码4.1常量和变量的定义 前面已经论述过，区间计算时可以使用整数运算。所以这里使用Cardinal类型来保存数据。在代码4.1中，我们定义了一个区间的最大范围Top，以及Half和Quar。使用这些常量可以方便的判断出当前区间的位置。另外，Low表示区间的下沿；High表示区间的上沿；Range表示区间的范围；Follow表示忽略次数；Value 表示解码时输入的数据。编码程序的代码如下所示。 01 procedure ArithCoder_Encode(CumFreq,Freq,Total：Cardinal)； 02 var 03 Check,Bit：Cardinal； 04 i：Integer； 05 begin 06//区间计算 07 Range：=Range div Total； 08 Inc(Low,CumFreq*Range)； 09 High：=Low+(Freq*Range)-1； 10//调整区间 11 while True do 12 begin 13 Check：=High xor Low； 14 if(Check and Half)=0 then 15 begin 16//区间位于上半区或下半区 17 Bit：=(High shr 30)and 1； 18 OutputBit(Bit)； 19 if Follow 0then 20 begin 21 if Bit=0 then Bit：=1 22 else Bit：=0； 23 for i：=1 to Follow do OutputBit(Bit)； 24 Follow：=0； 25 end； 26 end 27 else if((Check and Quar)0)and 28((High and Quar)=0)then 29 begin 30//区间位于中间区 31 Inc(Follow)； 32 Dec(High,Quar)； 33 Dec(Low,Quar)； 34 end 35 else break； 36//扩展区间 37 High：=((High shl 1)+1)and(Top-1)； 38 Low：=(Low shl 1)and(Top-1)； 39 end； 40 Range：=High-Low+1； 42 end； 代码4.2编码程序 代码4.2中CumFreq表示符号的累积频度；Freq表示符号的频度；Total表示所有符号的总计频度。OutputBit函数用以输出一个位的数据。需要说明的是，在WNC 源代码中编码部分与模型部分是合并在一起的。在本文的实现代码中将这两部分分离。编码部分专门负责区间的计算和正规化，而模型部分专门负责符号频度信息的统计。这样分离的好处是，可以使用不同的模型进行压缩。从而使编码部分可以和各种模型相配合，例如PPM。另外一点，本文实现代码中区间的计算与WNC源代码中区间的计算并不相同。采用本文中的计算方法可以减小运算量。同时允许出现较大的总计频度。这样可以减少削减频度的次数。还有一点，本文实现正规化的代码。从表面上看与WNC源代码不一样，但实质上是一致的。 所有数据都编码完成后，还需要多输出一个位，以便最后一个符号的解码。输出的这个位是1还是0可以根据当前的区间下沿判断。另外，如果此时忽略次数不为0，那么需要按忽略次数输出1或0。收尾操作的代码如下所示。 01 procedure ArithCoder_FinishEncode； 02 var 03 i：Integer； 04 begin 05//输出剩余编码 06 Inc(Follow)； 07 if Low Quar then 08 begin 09 OutputBit(0)； 10 for i：=1 to Follow do OutputBit(1)； 11 end 12 else 13 begin 14 OutputBit(1)； 15 for i：=1 to Follow do OutputBit(0)； 16 end； 17//完成 18 end； 代码4.3编码的收尾操作 由于将编码部分与模型部分相分离。在解码的时候需要两个函数来完成。第一个函数根据总计频度，从当前的区间中计算出估算频度。这个估算频度交给模型部分解码出符号。根据解码出的符号可以统计出符号的累积频度和频度。第二个函数根据符号的累积频度和频度重新计算区间。这样才能保证区间的变化与编码时相一致。第一个函数的代码如下。 01 function ArithCoder_DecodeTarget(Total：Cardinal)：Cardinal； 02 begin 03 Range：=Range div Total； 04 Result：=(Value-Low)div Range； 05 end； 代码4.4解码程序1 代码4.4中的函数返回估算频度，这个估算频度交给模型部分解码。另外，代码4.4第3行计算得到的Range并不是区间范围，而是一个临时的值。这个值将在第二个函数中用到，这里保存这个值可以防止重复运算。第二个函数的代码如下。 01 procedure ArithCoder_Decode(CumFreq,Freq：Cardinal)； 02 var 03 Check：Cardinal； 04 begin 05//区间计算 06 Inc(Low,CumFreq*Range)； 07 High：=Low+(Freq*Range)-1； 08//调整区间 09 while True do 10 begin 11 Check：=High xor Low； 12 if(Check and Half)=0 then 13 begin 14//区间位于上半区或下半区 15 end 16 else if((Check and Quar)0)and 17((High and Quar)=0)then 18 begin 19//区间位于中间区 20 Dec(High,Quar)； 21 Dec(Low,Quar)； 22 Dec(Value,Quar)； 23 end 24 else break； 25//扩展区间 26 High：=((High shl 1)+1)and(Top-1)； 27 Low：=(Low shl 1)and(Top-1)； 28 Value：=((Value shl 1)or InputBit)and(Top-1)； 29 end； 30 Range：=High-Low+1； 31//完成 32 end； 代码4.5解码程序2 代码4.5中的函数主要对区间进行重新计算和调整，同时还会输入数据。InputBit 是一个输入函数，每次调用时会返回一个位的数据。观察代码4.5中的代码可以发现。解码时进行的正规化操作，每次左移时最高位就被抛弃了。对于Value来说左移后需要输入一个位的数据填补到最低位。 4.3统计模型 除了编码部分还需要模型部分上述代码才可以运行。模型部分需要使用一个数据结构来记录符号的累积频度或频度。编码前需要查找一个符号的累积频度和频度。编码后需要更新一个符号的频度。另外，由于精度的限制。每当总计频度达到一个限定值的时候，需要对所有符号的频度减半。可以看出，查询和维护模型使用的数据结构需要占用大量的耗时。有研究指出[3]，当使用自适应模型时，模型使用的数据结构和算法对于压缩算法的整体性能有着决定性的作用。 在WNC源代码中使用了一个move-to-front的算法来实现模型。如果符号容量为N，那么这个算法需要4个N个元素的数组来完成算法。当然这并不是一个最优秀的算法。Peter M.Fenwick在1994年提出了一个新的数据结构：二进制索引树(Binary Indexed Tree，以下简称"BIT结构")[4]。BIT结构只需要1个N个元素的数组就可以完成算法。目前，在统计累计频度的数据结构中，BIT结构是速度最 快的。同时它的内存占用也是最低的。本文中算术编码程序的模型部分，就是使用BIT结构来实现的。 由于本文主要讨论算术编码的实现，所以对于BIT结构的实现这里不做介绍。请感兴趣的读者自行查阅相关的资料。 5分析 算术编码算法是所有基于统计模型的压缩算法中压缩率最高的一种算法。与哈夫曼编码相比，算术编码突破了以变长编码替换符号的瓶颈。算术编码使用一个小数来表示整个数据。并且根据符号的概率来调整小数的位数。这使得算术编码可以无限的接近数据的熵极限。另外由于算术编码的特点，它可以很好的与高阶模型相配合。这使得算术编码的用途越来越广泛。 算术编码在实现时也有许多缺点。首先一点，就是它的速度较慢。算术编码虽然可以获得比哈夫曼编码更高的压缩率。但是，算术编码的速度却比哈夫曼编码慢很多。另外一点，经过算术编码后的压缩数据无法进行随机访问。哈夫曼编码是使用变长编码替换符号的方法压缩数据。只要建立相关的索引表，就可以从压缩数据的任意位置开始解码符号。算术编码解码一个符号需要依赖以前解码符号的统计信息。所以使用算术编码解码一份压缩数据时，只能从压缩数据的最开头开始。这限制了算术编码的灵活性。 另外，许多算术编码的实现方法受美国专利的保护。如果在软件中使用这些算术编码的实现方法，需要得到相关的授权。一些实现方法的授权是免费的，而另一些则需要收取一定的授权费用。这些授权协议对于商业软件来说是可行的，但对于自由软件和开源软件项目来说它是不可行的。一个著名的例子就是压缩软件bzip2。由于考虑到算术编码的版权限制，bzip2放弃了算术编码的使用，转而使用哈夫曼编码。正是由于算术编码的版权限制，许多研究人员已经开始放弃对算术编码的研究。进而将目光转向了与算术编码本质上相同的区间编码。 6结束语 算术编码由于其更高的压缩率，以及更适用于高阶模型，已经被大量的使用。本文分析了算术编码的理论基础，着重介绍WNC算法的实现方式。详细讨论了算术编码原理、正规化操作、WNC算法代码实现等技术。并给出了一个切实可行的应用程序。希望本文能够对压缩算法的研究人员有所帮助。 参考文献 [1]C.E.Shannon,A Mathematical Theory of Communication,Bell System Technical Journal,1948,Vol 27,379-423,623-656. [2]Ian H.Witten,Radford M.Neal,John G.Cleary,Arithmetic Coding for Data Compression,Communications of the ACM,1987,30(6),520-541. [3]Alistair Moffat,Linear Time Adaptive Arithmetic Coding,IEEE Transactions on Information Theory,1990,36(2),401-406. [4]Peter M.Fenwick,A New Data Structure for Cumulative Frequency Tables,Software-Practice and Experience,1994,24(3),327-336. 附录 本论文的配套程序没有单独提供。我在编程论坛上发表过另一篇论文《区间编码算法的分析与实现》(以下简称"《区》")，页面地址：。在论文《区》的配套程序中有一个ArithmeticCoding.pas文件。该文件实现的就是本论文论述的算术编码算法。所以论文《区》的配套程序也可以作为本论文的配套程序使用。相关的项目说明请参考论文《区》中的项目说明。 本论文的第4.3节并没有对BIT结构进行详细的论述。但在论文《区》有进行详细的介绍。在论文《区》中论述了BIT结构的理论基础、介绍了频度信息的统计和更新操作。并且给出了相关操作的源代码。这部分的内容请参考论文《区》中的第5节。 另外，在论文《区》中有哈夫曼编码、区间编码和算术编码的比较测试。其测试结果对于本论文也同样适用。所以本论文中没有给出算术编码的性能测试。相关的测试结果请参考论文《区》中的第7节。 叶叶 2010年9月10日 特别声明： 1：资料来源于互联网，版权归属原作者 2：资料内容属于网络意见，与本账号立场无关 3：如有侵权，请告知，立即删除。 105103105822 常见的视频编码详解 A VI所采用的压缩算法并无统一的标准。也就是说，同样是以A VI为后缀的视频文件，其采用的压缩算法可能不同，需要相应的解压软件才能识别和回放该A VI文件。除了Microsoft 公司之外，其他公司也推出了自己的压缩算法，只要把该算法的驱动(Codec)加到Windows 系统中，就可以播放用该算法压缩的A VI文件。最新流行的MPEG-4视频也借用A VI的名称，只要机器安装了它的编码解码，也能够实现正常的播放。这些A VI都能够在用Authorware 或PowerPiont开发的作品当中正常放映。各种编码Codec所生成的A VI文件的大小和质量是不同的，对系统和硬件要求也不同。 因此在压缩A VI时，必须根据计算机的软硬件情况，来考虑采用什么Codec算法，否则你的作品中视频放映是难以令人满意的。下面就是对各种常见编码解码Codec的说明。 常见的视频编码 1、Cinepak Codec by Radius 它最初发布的时候是用在386的电脑上看小电影，在高数据压缩率下，有很高的播放速度。利用这种压缩方案可以取得较高的压缩比和较快的回放速度，但是它的压缩时间相对较长。 2、Microsoft Video 1 用于对模拟视频进行压缩，是一种有损压缩方案，最高仅达到256色，它的品质就可想而知，一般还是不要使用它来编码A VI。 3、Microsoft RLE 一种8位的编码方式，只能支持到256色。压缩动画或者是计算机合成的图像等具有大面积色块的素材可以使用它来编码，是一种无损压缩方案。 4、Microsoft H.261和H.263 Video Codec 用于视频会议的Codec，其中H.261适用于ISDN、DDN线路，H.263适用于局域网，不过一般机器上这种Codec是用来播放的，不能用于编码。 5、Intel Indeo Video R3.2 所有的Windows版本都能用Indeo video 3.2播放A VI编码。它压缩率比Cinepak大，但需要回放的计算机要比Cinepak的快。 6、Intel Indeo Video 4和5 实现算术编码及其译码 一、实验内容 借助C++编程来实现对算术编码的编码及其译码算法的实现 二、实验环境 1.计算机 2.VC++6.0 三、实验目的 1.进一步熟悉算术编码的原理，及其基本的算法； 2.通过编译，充分对于算术编码有进一步的了解和掌握； 3.掌握C++语言编程（尤其是数值的进制转换，数值与字符串之间的转换 等） 四、实验原理 算术编码 算术编码的基本原理是将编码的消息表示成实数0和1之间的一个间隔，消息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。 算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。 给定事件序列的算术编码步骤如下： （1）编码器在开始时将“当前间隔”设置为[0，1)。 （2）对每一事件，编码器按步骤（a）和（b）进行处理 （a）编码器将“当前间隔”分为子间隔，每一个事件一个。 （b）一个子间隔的大小与下一个将出现的事件的概率成比例，编码器选择子间隔对应于下一个确切发生的事件相对应，并使它成为新的“当前间 隔”。 （3）最后输出的“当前间隔”的下边界就是该给定事件序列的算术编码。 编码过程 假设信源符号为{A， B， C， D}，这些符号的概率分别为{ 0.1， 0.4， 0.2，0.3 }，根据这些概率可把间隔[0， 1]分成4个子间隔：[0， 0.1]， [0.1， 0.5]， [0.5， 0.7]， [0.7， 1]，其中[x，y]表示半开放间隔，即包含x不包含y。上面的信息可综合在表03-04-1中。 下表为信源符号，概率和初始编码间隔 如果二进制消息序列的输入为：C A D A C D B。编码时首先输入的符号是C，找到它的编码范围是[0.5，0.7]。由于消息中第二个符号A的编码范围是[0，0.1]，因此它的间隔就取[0.5， 0.7]的第一个十分之一作为新间隔[0.5，0.52]。依此类推，编码第3个符号D时取新间隔为[0.514， 0.52]，编码第4个符号A 时，取新间隔为[0.514， 0.5146]，…。消息的编码输出可以是最后一个间隔中的任意数。整个编码过程如图03-04-1所示。 编码和译码的全过程分别表示在下表。 编码过程 用A*算法解决八数码问题 一、 题目：八数码问题也称为九宫问题。在3×3的棋盘，有八个棋子，每个 棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有 一个空格，与空格相邻的棋子可以移到空格中。要解决的问题是：任意给 出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动 棋子步数最少的移动步骤。 二、 问题的搜索形式描述 状态：状态描述了8个棋子和空位在棋盘的9个方格上的分布。 初始状态：任何状态都可以被指定为初始状态。 操作符：用来产生4个行动（上下左右移动）。 目标测试：用来检测状态是否能匹配上图的目标布局。 路径费用函数：每一步的费用为1，因此整个路径的费用是路径中的步数。 现在任意给定一个初始状态，要求找到一种搜索策略，用尽可能少的步数 得到上图的目标状态算法介绍 三、 解决方案介绍 1.A*算法的一般介绍 A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。对于 几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即 ()()()()()()**f g n sqrt dx nx dx nx dy ny dy ny =+--+--； 这样估价函数f 在g 值一定的情况下，会或多或少的受估价值h 的制约，节点距目标点近，h 值小，f 值相对就小，能保证最短路的搜索向终点的 方向进行。明显优于盲目搜索策略。 A star算法在静态路网中的应用 2.算法伪代码 创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。算起点的估价值，将起点放入OPEN表。 while(OPEN!=NULL) { 从OPEN表中取估价值f最小的节点n; if(n节点==目标节点) {break;} for(当前节点n 的每个子节点X) { 算X的估价值; if(X in OPEN) { if( X的估价值小于OPEN表的估价值 ) {把n设置为X的父亲; 更新OPEN表中的估价值; //取最小路径的估价值} } if(X inCLOSE) { if( X的估价值小于CLOSE表的估价值 ) {把n设置为X的父亲; 更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值} } if(X not inboth) {把n设置为X的父亲; 求X的估价值; 并将X插入OPEN表中; //还没有排序} 班级 __ __ 学号__姓名 __ ___评分__________ 1．实验名称 LZW编码与解码算法 2．实验目的 2.1通过实验进一步掌握LZW编码的原理； 2.2 用C/C++等高级程序设计语言实现LZW编码。 3．实验内容步骤或记录（包括源程序或流程和说明等） 3.1 实验原理 （1）在压缩过程中动态形成一个字符列表（字典）。 （2）每当压缩扫描图像发现一个词典中没有的字符序列，就把该字符序列存到字典中，并用字典的地址（编码）作为这个字符序列的代码，替换原图像中的字符序列，下次再碰到相同的字符序列，就用字典的地址代替字符序列 3.2实验步骤 LZW编码算法的具体执行步骤如下： 步骤1：开始时的词典包含所有可能的根(Root)，而当前前缀P是空的； 步骤2：当前字符(C) ：=字符流中的下一个字符； 步骤3：判断缀-符串P+C是否在词典中 (1) 如果“是”：P ：= P+C // (用C扩展P) ； (2) 如果“否” ①把代表当前前缀P的码字输出到码字流; ②把缀-符串P+C添加到词典; ③令P ：= C //(现在的P仅包含一个字符C); 步骤4：判断码字流中是否还有码字要译 (1) 如果“是”，就返回到步骤2； (2) 如果“否” ①把代表当前前缀P的码字输出到码字流; ②结束。 3.3 源程序 #include const int N=200; class LZW{ private: string Dic[200];//存放词典 int code[N];//存放编码过的码字 public: LZW(){//设置词典根 Dic[0]='a'; Dic[1]='b'; Dic[2]='c'; string *p=Dic;//定义指针指向词典中的字符} void Bianma(string cs[N]);//进行编码 int IsDic(string e);//判断是否在词典中 int codeDic(string f); void display(int g);//显示结果 }; void LZW::Bianma(string cs[N]){ string P,C,K; P=cs[0]; int l=0; for(int i=1;i 算术编码工作原理 在给定符号集和符号概率的情况下，算术编码可以给出接近最优的编码结果。使用算术编码的压缩算法通常先要对输入符号的概率进行估计，然后再编码。这个估计越准，编码结果就越接近最优的结果。 例: 对一个简单的信号源进行观察，得到的统计模型如下： ?60% 的机会出现符号中性 ?20% 的机会出现符号阳性 ?10% 的机会出现符号阴性 ?10% 的机会出现符号数据结束符. (出现这个符号的意思是该信号源'内部中止'，在进行数据压缩时这样的情况是很常见的。当第一次也是唯一的一次看到这个符号时，解码器就知道整个信号流都被解码完成了。) 算术编码可以处理的例子不止是这种只有四种符号的情况，更复杂的情况也可以处理，包括高阶的情况。所谓高阶的情况是指当前符号出现的概率受之前出现符号的影响，这时候之前出现的符号，也被称为上下文。比如在英文文档编码的时候，例如，在字母Q 或者q出现之后，字母u出现的概率就大大提高了。这种模型还可以进行自适应的变化，即在某种上下文下出现的概率分布的估计随着每次这种上下文出现时的符号而自适应 更新，从而更加符合实际的概率分布。不管编码器使用怎样的模型，解码器也必须使用同样的模型。 一个简单的例子以下用一个符号串行怎样被编码来作一个例子：假如有一个以A、B、C三个出现机会均等的符号组成的串行。若以简单的分组编码会十分浪费地用2 bits 来表示一个符号：其中一个符号是可以不用传的(下面可以见到符号B正是如此)。为此，这个串行可以三进制的0和2之间的有理数表示，而且每位数表示一个符号。例如，“ABBCAB”这个串行可以变成0.011201(base3)(即0为A, 1为B, 2为C)。用一个定点二进制数字去对这个数编码使之在恢复符号表示时有足够的精度，譬如 0.001011001(base2) –只用了9个bit，比起简单的分组编码少(1 – 9/12)x100% = 25%。这对于长串行是可行的因为有高效的、适当的算法去精确地转换任意进制的数字。 编码过程的每一步，除了最后一步，都是相同的。编码器通常需要考虑下面三种数据： ?下一个要编码的符号 ?当前的区间(在编第一个符号之前，这个区间是[0,1), 但是之后每次编码区间都会变化) ?模型中在这一步可能出现的各个符号的概率分布(像前面提到的一样，高阶或者自适应的模型中，每一步的概率并不必须一样) 编码其将当前的区间分成若干子区间，每个子区间的长度与当前上下文下可能出现的对应符号的概率成正比。当前要编码的符号对应的子区间成为在下一步编码中的初始区间。 音视频编码技术报告 姓名: 学号： 学院(系):电子与信息工程学院 专业: 电子与通信工程 题目: 基于DCT变换的图像压缩技术的仿真 1.引言 在信息世界迅猛发展的今天, 人们对计算机实时处理图像信息的要求越来越高。如何在保证图像质量的前提下, 同时兼顾实时性和高效性成了一个值得关注的问题。于是, 对图像信息进行一定的压缩处理成为了一个不可或缺的环节。图像压缩是关于用最少的数据量来表示尽可能多的原图像的信息的一个过程。 本文主要研究基于DCT 变换的有损压缩编码技术。离散余弦变换, 简称DCT , 是一种实数域变换, 其变换核为余弦函数, 计算速度快。DCT 除了具有一般的正交变换性质外, 它的变换阵的基向量能很好地描述人类语音信号和图像 信号的相关特征。因此, 在对语音信号、图像信号的变换中,DCT 变换被认为是一种准最佳变换。近年颁布的一系列视频压缩编码的国际标准建议中, 都把DCT 作为其中的一个基本处理模块。而且对于具有一阶马尔柯夫过程的随机信 号,DCT 十分接近于Karhunen -Loeve 变换, 也就是说它是一种最佳近似变换。 2.图像压缩编码的简介 从信息论的角度看，图像是一个信源。描述信源的数据是信息量和信息量冗余之和。数据压缩实际上就是减少这些冗余量。图像编码压缩的方法目前有很多，其分类方法根据出发点不同而有差异。根据解压重建后的图像和原始图像之间是否具有误差（对原图像的保真程度），图像编码压缩分为无误差（亦称无失真、无损、信息保持）编码和有误差（有失真或有损）编码两大类。 无损压缩（冗余度压缩、可逆压缩）：是一种在解码时可以精确地恢复原图像，没有任何损失的编码方法，但是压缩比不大，通常只能获得1~5倍的压缩比。用于要求重建后图像严格地和原始图像保持相同的场合，例如复制、保存十分珍贵的历史、文物图像等。 有损压缩（不可逆压缩）：只能对原始图像进行近似的重建，而不能精确复原，适合大数工用于存储数字化了的模拟数据。压缩比大，但有信息损失，本文采用有损压缩。 DCT图像压缩编码可以概括成图2.1的框图。 图2.1 DCT压缩编码过程简化 3.DCT变换 最小均方误差下得到的最佳正交变化是K-L变换，而离散余弦变换(DCT)是仅次于K-L变换的次最佳变换，目前已获得广泛应用。离散预先变换DCT用于图像压缩操作中的基本思路是，将图像分为8×8的子块或16×16的子块，并对每一个子块进行单独的DCT变换，然后对变换结果进行量化、编码。 用A算法解决八数码 问题 用A*算法解决八数码问题 一、 题目：八数码问题也称为九宫问题。在3×3的棋盘，有八个棋子，每个 棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要解决的问题是：任意给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 二、 问题的搜索形式描述 状态：状态描述了8个棋子和空位在棋盘的9个方格上的分布。 初始状态：任何状态都可以被指定为初始状态。 操作符：用来产生4个行动（上下左右移动）。 目标测试：用来检测状态是否能匹配上图的目标布局。 路径费用函数：每一步的费用为1，因此整个路径的费用是路径中的步数。 现在任意给定一个初始状态，要求找到一种搜索策略，用尽可能少的步数得到上图的目标状态算法介绍 三、 解决方案介绍 1.A*算法的一般介绍 A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。对 于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价 值，即 ()()()()()()**f g n sqrt dx nx dx nx dy ny dy ny =+--+--； 这样估价函数f 在g 值一定的情况下，会或多或少的受估价值h 的制 约，节点距目标点近，h 值小，f 值相对就小，能保证最短路的搜索向终点的方向进行。明显优于盲目搜索策略。 A star算法在静态路网中的应用 2.算法伪代码 创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。算起点的估价值，将起点放入OPEN表。 while(OPEN!=NULL) { 从OPEN表中取估价值f最小的节点n; if(n节点==目标节点) {break;} for(当前节点n 的每个子节点X) { 算X的估价值; if(X in OPEN) { if( X的估价值小于OPEN表的估价值 ) {把n设置为X的父亲; 更新OPEN表中的估价值; //取最小路径的估价值} } if(X inCLOSE) { if( X的估价值小于CLOSE表的估价值 ) LZW编码算法详解 LZW(Lempel-Ziv & Welch)编码又称字串表编码，是Welch将Lemple和Ziv所提出来的无损压缩技术改进后的压缩方法。GIF图像文件采用的是一种改良的LZW 压缩算法，通常称为GIF-LZW压缩算法。下面简要介绍GIF-LZW的编码与解码方程 解：例现有来源于二色系统的图像数据源（假设数据以字符串表示）：aabbbaabb，试对其进行LZW编码及解码。 1）根据图像中使用的颜色数初始化一个字串表（如表1），字串表中的每个颜色对应一个索引。在初始字串表的LZW_CLEAR和LZW_EOI分别为字串表初始化标志和编码结束标志。设置字符串变量S1、S2并初始化为空。 2）输出LZW_CLEAR在字串表中的索引3H(见表2第一行)。 3）从图像数据流中第一个字符开始，读取一个字符a，将其赋给字符串变量S2。判断S1+S2=“a”在字符表中，则S1=S1+S2=“a”（见表2第二行）。 4）读取图像数据流中下一个字符a，将其赋给字符串变量S2。判断S1+S2=“aa”不在字符串表中，输出S1=“a”在字串表中的索引0H，并在字串表末尾为 S1+S2="aa"添加索引4H，且S1=S2=“a”（见表2第三行）。 5）读下一个字符b赋给S2。判断S1+S2=“ab”不在字符串表中，输出S1=“a”在字串表中的索引0H，并在字串表末尾为S1+S2=“ab”添加索引5H，且 S1=S2=“b”（见表2第四行）。 6）读下一个字符b赋给S2。S1+S2=“bb”不在字串表中，输出S1=“b”在字串表中的索引1H，并在字串表末尾为S1+S2=“bb”添加索引6H，且S1=S2=“b”（见表2第五行）。 7）读字符b赋给S2。S1+S2=“bb”在字串表中，则S1=S1+S2=“bb”（见表2第六行）。 8）读字符a赋给S2。S1+S2=“bba”不在字串表中，输出S1=“bb”在字串表中的索引6H，并在字串表末尾为S1+S2=“bba”添加索引7H，且S1=S2=“a”（见表2第七行）。 9）读字符a赋给S2。S1+S2=“aa”在字串表中，则S1=S1+S2=“aa”（见表2第八行）。 10）读字符b赋给S2。S1+S2=“aab”不在字串表中，输出S1=“aa”在字串表中的索引4H，并在字串表末尾为S1+S2=“aab”添加索引8H，且S1=S2=“b”（见表2第九行）。 11）读字符b赋给S2。S1+S2=“bb”，在字串表中，则S1=S1+S2=“b”（见表2第十行）。 12）输出S1中的字符串"b"在字串表中的索引1H（见表2第十一行）。 13）输出结束标志LZW_EOI的索引3H，编码完毕。 最后的编码结果为"30016463“。 简单短序列的算术编码的MATLAB实现 正确实现的算术编码算法压缩能力Shannond定理描述的理论极限，是目前已知的压缩能力最强的无损压缩算法。 不过，由于算术编码算法的实现比较复杂，使用它作为默认压缩算法的应用程序还相当少。在Unix平台上非常流行的bzip2(这个工具有命令行模式的Windows版本)使用的就是经过修改的算术编码算法。 目前为止还没有使用算术编码作为默认压缩算法的Windows应用程序，WinRAR和WinIMP能够支持bzip2的解压。除此之外，在最新的JPEG标准中也用到了经过修改的算术编码压缩算法，但JPEG所用的那种算法受专利保护，因此使用时必须获得授权。 在之后的文章会很好的研究这个算法的实现： 现在给出一个简单的实例： 运行过程如下： %I=imread('001.bmp') %imshow(I); clear I=[3 3 1 1 3 3 1 2;2 3 3 1 3 2 3 2;1 2 3 3 3 3 1 2]; %I=[1 1 1 1 0 0 1 0 1 1 1 0]; [m,n]=size(I); % 第一列为灰度值,第二列为个数,第三列为概率百分数，应该也可以用imhist table = tabulate(I(); % 注意的是，tabulate要求I的元素必须为非负整数 % 否则，以采用如下方法求解 % 如[1 2 3；1 2 2]，则统计出结果1是2个，2是3个，3是1个 % sortM=sort(M(); % uniqueM=([diff(sortM);1]>0); % count = [sortM(uniqueM) diff(find([1;uniqueM]))] % 即color,p如下所示 color = table(:,1)'; p = table(:,3)'/100; % 计算上下限 csump = cumsum(table(:,3)'); allLow =[0,csump(1:end-1)/100]; allHigh = csump/100; numberlow = 0; numberhigh = 1; for k = 1:m for kk = 1:n data = I(k,kk); low = allLow(data==color); high = allHigh(data==color); range = numberhigh-numberlow; tmp = numberlow; numberlow = tmp+range*low; numberhigh = tmp+range*high; end 收稿日期：2011－03－16；修回日期：2011－05－09。 基金项目：国家自然科学基金资助项目（30970780）；北京市自然科学基金及教委重点科技项目（KZ200910005005）。作者简介：邓智玭（1983－），女，湖南邵阳人，博士研究生，主要研究方向：视频编码；贾克斌（1962－），男，北京人，教授，博士生导师，主要研究方向：多媒体技术；陈锐霖（1971－），男，香港人，教授，博士生导师，主要研究方向：视频技术；伏长虹（1981－），男，香港人，副教授，主要研究方向：视频编码；萧允治（1954－），男，香港人，教授，博士生导师，主要研究方向：视频编码。 文章编号：1001－9081（2011）09－2453－04 doi ：10．3724/SP．J．1087．2011．02453 三维视频编码技术的发展与挑战 邓智玭1，2，贾克斌1，陈锐霖2，伏长虹2，萧允治 2 （1．北京工业大学电子信息与控制工程学院，北京100124；2．香港理工大学电子资讯工程系，香港九龙） (zhipindeng@gmail．com;kebinj@bjut．edu．cn) 摘 要：介绍了三维视频编码的核心技术。首先比较了纯视频格式和深度增强格式三维视频编码技术的发展方 向及面临的挑战，其中重点分析了深度估计技术和视点合成技术的研究思路；然后概括了国际3DV /FTV 标准的制定 现状；最后对三维视频编码技术进行了总结和展望。 关键词：三维视频；多视点视频；立体视频；视频编码；深度图 中图分类号：TN919．81 文献标志码：A New trend and challenges in 3D video coding DENG Zhi-pin 1，2，JIA Ke-bin 1，CHAN Yui-lam 2，FU Chang-hong 2，SIU Wan-chi 2 (1．College of Electronic Information and Control Engineering，Beijing University of Technology，Beijing 100124，China ；2．Department of Electronic and Information Engineering，The Hong Kong Polytechnic University，Kowloon Hongkong，China ) Abstract:The key technologies of 3D video coding were introduced．Firstly，the developing directions and challenges of video-only format and depth-enhancement format 3D videos were elaborated．The depth estimation and view synthesis technologies were analyzed in detail．Subsequently，the process of standardizing the current 3DV /FTV standard of MPEG was summarized．The conclusion and prospect were given at last． Key words:3D video;multiview video;stereoscopic video;video coding;depth map 0引言 近二十年来，视频广播技术发生了重大变革，从20世纪的模拟电视到数字电视、高清数字电视，乃至现在的三维电 视，视频技术随着人们生活水平的提高不断发展进步 ［1－2］ 。当今世界，人们已经不再满足于传统的单目视频带来的视觉感受，具有临场感和交互性的三维立体视频以其独特的景深 效果给用户带来前所未有的奇妙体验［3］ 。随着好莱坞推出《阿凡达》等立体电影，三维视频技术逐渐成为多媒体信息产 业的热门话题［4－6］ 。与传统的单目视频相比，三维视频包含的数据量成倍增加［7］ 。为了避免信道中数据量激增，必须对其进行有效的编码压缩。近年来，全球各大研究机构都投入大量精力对三维视频编码技术进行深入研究。 1三维视频编码技术 根据传输形式不同将三维视频分为两大类：1）纯视频格 式，需要传输所有视角的数据［8］ ；2）深度增强格式，传输有限个单目视频及其深度序列， 在解码端利用视点合成技术生成虚拟视点［9］ 。这两类三维视频由于传输形式不同而采用不同的编码方式。 1．1纯视频格式三维视频 纯视频格式三维视频由多路具有细微视角差异的视频组成，由两台（或多台）相邻摄像机从不同角度同时对同一场景进行拍摄得到，这些视频可以直接在三维立体显示设备上播放。1．1．1 立体视频编码 最直接的双通道立体视频编码方式是采用Simulcast 方 法直接对左右视点数据进行独立压缩，如图1（a ）所示，但是 左右视点间的相关性没有得到利用，编码效率较低［10］ 。早在 十几年前， MPEG-2Multiview Profile 就提出结合左右视点之间的交叉相关性和同一视点内部的时空相关性来提高立体视频编码效率［11－12］ 。近年来，立体补充增强信息（Stereo Supplemental Enhancement Information ，Stereo SEI ）和帧组合补 充增强信息（Frame Packing Arrangement SEI ）被纳入到H.264/AVC 中［13］。根据Stereo SEI ，在编码前将左右视点以左右/上下方式交错排列成一段视频，然后通过场间预测来消除视点间的交叉冗余，在解码端通过反交错将立体视频还原成两段独立视点，如图1（b ）所示。该方式与原有的H．264编 解码器完美兼容， 不需要改变原有硬件结构。2009年7月，国际运动图像专家组（Moving Picture Expert Group ，MPEG ）颁 布了MPEG-4AVC Stereo High Profile ，作为多视点视频编码 （Multiview Video Coding ，MVC ）标准的一个子集［14］。然而，Stereo High Profile 只适用于逐行和隔行扫描的双通道立体视频序列，不支持临场感更强的多视点视频和自由视点视频。1．1．2 多视点视频编码 多视点视频是由多台相邻摄像机从不同角度对同一场景 进行拍摄得到的多路视频序列［15］ 。多视点视频的数据量巨 大，相邻视点间的交叉冗余信息比双通道立体视频大得多，为 了最大限度地提高压缩率， 在编码时采用一种基于分层B 帧（Hierarchical B Pictures ，HBP ）的视点—时间金字塔型预测结构［16－18］ ，如图2所示。该结构被MVC 的官方测试模型JMVC 采纳［19］ 。 2009年1月，国际联合视频小组（Joint Video Team ，JVT ） 第31卷第9期2011年9月 计算机应用 Journal of Computer Applications Vol．31No．9Sep．2011 实验报告 一、实验问题 八数码问题求解 二、实验软件 VC6.0 编程语言或其它编程语言 三、实验目的 1. 熟悉人工智能系统中的问题求解过程； 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用； 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 四、实验数据及步骤 （一、）实验内容 八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 2 8 3 1 2 3 1 4 8 4 7 6 5 7 6 5 (a) 初始状态(b) 目标状态 图1 八数码问题示意图 （二、）基本数据结构分析和实现 1.结点状态 我采用了struct Node数据类型 typedef struct _Node{ int digit[ROW][COL]; int dist; // distance between one state and the destination一 个表和目的表的距离 int dep; // the depth of node深度 // So the comment function = dist + dep.估价函数值 int index; // point to the location of parent父节点的位置 } Node; 2.发生器函数 定义的发生器函数由以下的四种操作组成： (1)将当前状态的空格上移 Node node_up; Assign(node_up, index);//向上扩展的节点 int dist_up = MAXDISTANCE; (2)将当前状态的空格下移 Node node_down; Assign(node_down, index);//向下扩展的节点 int dist_down = MAXDISTANCE; (3)将当前状态的空格左移 Node node_left; Assign(node_left, index);//向左扩展的节点 int dist_left = MAXDISTANCE; (4)将当前状态的空格右移 Node node_right; Assign(node_right, index);//向右扩展的节点 int dist_right = MAXDISTANCE; 通过定义结点状态和发生器函数，就解决了8数码问题的隐式图的生成问题。接下来就是搜索了。 3.图的搜索策略 经过分析，8数码问题中可采用的搜速策略共有：1.广度优先搜索、2.深度优先搜索、2.有界深度优先搜索、4.最好优先搜索、5.局部择优搜索，一共五种。其中，广度优先搜索法是可采纳的，有界深度优先搜索法是不完备的，最好优先和局部择优搜索法是启发式搜索法。 实验时,采用了广度(宽度)优先搜索来实现。 （三、）广度(宽度)优先搜索原理 1. 状态空间盲目搜索——宽度优先搜索 其基本思想是，从初始节点开始，向下逐层对节点进形依次扩展，并考察它是否为目标节点，再对下层节点进行扩展（或搜索）之前，必须完成对当层的所有节点的扩展。再搜索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面，后进入的节点排在后面。其搜索过程如图（1）所示。 LZW编码算法，尝试使用matlab计算 %encoder LZW for matlab %yu 20170503 clc; clear; close all; %初始字典 dic = cell(512,1); for i = 1:256 dic{i} = {num2str(i)}; end %输入字符串a，按空格拆分成A，注意加1对应围1~256 a = input('input:','s'); a = deblank(a); A = regexp(a,'\s+','split'); L = length(A); for j=1:L A{j} = num2str(str2num(A{j})+1); end A_t = A{1};%可识别序列 B_t = 'test';%待验证词条 d = 256;%字典指针 b = 1;%输出指针 B = cell(L,1);%输出初始 output = ' ';%输出初始 j=1; for j = 2:L m=1; B_t =deblank([A_t,' ',A{j}]);%合成待验证词条 while(m <= d) if strcmp(dic{m},B_t) A_t = B_t; break else m=m+1; end end while(m == d+1) d = d+1; dic{d} = B_t; q=1; for q=1:d if strcmp(dic{q},A_t) B{b} = num2str(q); b = b+1; end end A_t = A{j}; end end for q=1:d%处理最后一个序列输出 if strcmp(dic{q},A_t) B{b} = num2str(q); b = b+1; end end for n = 1:(b-1) B{n} =num2str(str2num(B{n})-1); output=deblank([output,' ',B{n}]); end output 运算结果 计算结果为39 39 126 126 256 258 260 259 257 126 视频编码的基本原理及基本框架 视频图像数据有极强的相关性，也就是说有大量的冗余信息。其中冗余信息可分为空域冗余信息和时域冗余信息。压缩技术就是将数据中的冗余信息去掉（去除数据之间的相关性），压缩技术包含帧内图像数据压缩技术、帧间图像数据压缩技术和熵编码压缩技术。 去时域冗余信息 使用帧间编码技术可去除时域冗余信息，它包括以下三部分： －运动补偿 运动补偿是通过先前的局部图像来预测、补偿当前的局部图像，它是减少帧序列冗余信息的有效方法。 －运动表示 不同区域的图像需要使用不同的运动矢量来描述运动信息。运动矢量通过熵编码进行压缩。－运动估计 运动估计是从视频序列中抽取运动信息的一整套技术。 注：通用的压缩标准都使用基于块的运动估计和运动补偿 去空域冗余信息 主要使用帧内编码技术和熵编码技术： －变换编码 帧内图像和预测差分信号都有很高的空域冗余信息。变换编码将空域信号变换到另一正交矢量空间，使其相关性下降，数据冗余度减小。 －量化编码 经过变换编码后，产生一批变换系数，对这些系数进行量化，使编码器的输出达到一定的位率。这一过程导致精度的降低。 熵编码是无损编码。它对变换、量化后得到的系数和运动信息，进行进一步的压缩。 视频编码的基本框架 H.261 H.261标准是为ISDN设计，主要针对实时编码和解码设计，压缩和解压缩的信号延时不超过150ms，码率px64kbps(p=1~30)。 H.261标准主要采用运动补偿的帧间预测、DCT变换、自适应量化、熵编码等压缩技术。只有I帧和P帧，没有B帧，运动估计精度只精确到像素级。支持两种图像扫描格式：QCIF 和CIF。 H.263 H.263标准是甚低码率的图像编码国际标准，它一方面以H.261为基础，以混合编码为核心，其基本原理框图和H.261十分相似，原始数据和码流组织也相似；另一方面，H.263也吸收了MPEG等其它一些国际标准中有效、合理的部分，如：半像素精度的运动估计、PB帧预测等，使它性能优于H.261。 H.263使用的位率可小于64Kb/s,且传输比特率可不固定（变码率）。H.263支持多种分辨率：SQCIF(128x96)、QCIF、CIF、4CIF、16CIF。 与H.261和H.263相关的国际标准 与H.261有关的国际标准 H.320：窄带可视电话系统和终端设备； H.221：视听电信业务中64~1 920Kb/s信道的帧结构； H.230：视听系统的帧同步控制和指示信号； H.242：使用直到2Mb/s数字信道的视听终端的系统。 与H.263有关的国际标准 H.324：甚低码率多媒体通信终端设备； H.223：甚低码率多媒体通信复合协议； H.245：多媒体通信控制协议； G.723.1.1：传输速率为5.3Kb/s和6.3Kb/s的语音编码器。 JPEG 国际标准化组织于1986年成立了JPEG(Joint Photographic Expert Group)联合图片专家小组，主要致力于制定连续色调、多级灰度、静态图像的数字图像压缩编码标准。常用的基于离散余弦变换(DCT)的编码方法，是JPEG算法的核心内容。 转算术编码算法的分析与实现 [转]算术编码算法的分析与实现2011-06-09 14：20本论文题目：算术编码算法的分析与实现，作者：叶叶，于2010年10月16日在编程论坛上发表。页面地址：。本论文全文及相关配套程序可以在上述页面中下载。请尊重他人劳动成果，转载或引用时请注明出处。 目录 1前言2 2理论2 2.1编码2 2.2解码3 3改进4 3.1整数运算4 3.2正规化5 4实现8 4.1编码8 4.2解码10 4.3统计模型11 5分析12 6结束语12 参考文献13 附录13 算术编码算法的分析与实现 作者：叶叶(网名：yeye55) 摘要：分析了算术编码的理论基础，着重介绍WNC算法的实现方式。详细讨论了算术编码原理、正规化操作、WNC算法代码实现等技术。给出了一个切实可行的应用程序。 关键词：算术编码；正规化；Delphi 中图分类号：TP301.6 1前言 早在1948年C.E.Shannon提出信息论[1]的时候，就提出了算术编码的思想。但是经过多年的研究，许多学者认为算术编码是无法实现的。算术编码要求进行无限精度的实数运算，这在仅能进行有限精度运算的计算机系统上是无法进行的。随着研究的深入，终于在1987年Ian H.Witten、Radford M.Neal和John G.Cleary发表了一篇论文[2]，提出了一种基于整数运算的算术编码实现算法。该算法后来被命名为CACM87，并应用于ITU-T的H.236视频编码标准。也有学者根据作者姓名将该算法称之为WNC算法。WNC算法是一个实用性算法，它可以应用在许多方面。在Witten等人的论文[2]中给出了一个使用C语言编写的WNC算法实现程序的源代码(以下简称"WNC源代码")。在许多时候，WNC源代码已经作为算术编码的范本程序 1、程序源代码 #include LZW编码的编程和实现 一、实验目的 编写源程序,实现LZW的编码和解码 二、实验要求 1.编码输入若干字母(如abbababac),输出相应的编码 2.解码输入若干数字(如122473),输出相应的字母 三、编程思想 1.编码 根缀表已知 1 A 2 B 3 C 编码 分析字符串流，从词典中寻找最长匹配串，即字符串P在词典中，而字符串P+后一个字符C不在词典中 此时，输出P对应的码字，将P+C放入词典中。 如第一步： 输入A 此时，A在表中，而AB不在表中，则输出A对应的码字1,同时将AB写入表中，此时表为 1 A 2 B 3 C 4 AB 编码输出为1 (A已编码) 第二步,输入B,B在词典中，而BB不在词典中，则输出2，将BB写入表中，此时表为 1 A 2 B 3 C 4 AB 5 BB 编码输出为12 (AB已经编码) .... 2.解码 根缀表为 1 A 2 B 3 C 定义如下变量 StringP :前一步码字流 pW : StringP的第一个字符 StringC :当前的码字流 cW : StringC的第一个字符 第一步 输出StringC 并StringP = StringC 如: 1解码为A,则StringC = A 那么 输出A,并令St ringP = A --------------------------------------------------------------------------- 第二步 1.解码得到StringC,并输出StringC 2.将StringP + cW放入词典(如果当前码字不在词典中,则将StringP + cP放入词典中) 3.StringP = StringC 如: 第二步要解码为2,解码为B,则StringC=B,输出B (此时St ringP = A) 将StringP+cW放入表中,即将AB放入表中,此时表为 1 A 2 B 3 C 4 AB 四、实验情况及分析 编码解码 错误提示 附:源代码 #include常见的视频编码详解
算术编码
用A算法解决八数码问题
LZW编码算法
算术编码工作原理
音视频编码技术
用A算法解决八数码问题演示教学
LZW编码算法详解
简单短序列的算术编码的MATLAB实现
三维视频编码技术的发展与挑战
八数码问题求解--实验报告讲解
LZW编码算法matlab实现
视频编码的基本原理及基本框架
转 算术编码算法的分析与实现
启发式搜索算法解决八数码问题(C语言)
LZW编码编程实现(C++版)