多媒体编码方法有哪些

算术编码在图像数据压缩标准(如JPEG，JBIG)中扮演了重要的角色。在算术编码中，消息用0到1之间的实数进行编码，算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。算术编码器的编 码过程可用下面的例子加以解释。 [例4.2] 假设信源符号为{00, 01, 10, 11}，这些符号的概率分别为{ 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)，其中表示半开放间隔，即包含不包含。上面的信息可综合在表4-04中 。 表4-04 信源符号，概率和初始编码间隔 符号 00 01 10 11 概率 0.1 0.4 0.2 0.3 初始编码间隔 初始编码间隔 [0, 0.1) [0.1, 0.5) [0.5, 0.7) [0.7, 1) 如果二进制消息序列的输入为：10 00 11 00 10 11 01。编码时首先输入的符号是10， 找到它的编码范围是[0.5, 0.7)。由于消息中第二个符号00的编码范围是[0, 0.1)，因 此它的间隔就取[0.5, 0.7)的第一个十分之一作为新间隔[0.5, 0.52)。依此类推，编码 第3个符号11时取新间隔为[0.514, 0.52)，编码第4个符号00时，取新间隔为[0.514, 0 .5146)，… 。消息的编码输出可以是最后一个间隔中的任意数。整个编码过程如图4-0 3所示。 图4-03 算术编码过程举例 这个例子的编码和译码的全过程分别表示在表4-05和表4-06中。根据上面所举的例子， 可把计算过程总结如下。 考虑一个有M个符号的字符表集，假设概率，而。输入符号用表示，第个子间隔的范围用 表示。其中，和，表示间隔左边界的值, 表示间隔右边界的值，表示间隔长度。编码步 骤如下： 步骤1：首先在1和0之间给每个符号分配一个初始子间隔，子间隔的长度等于它的概率， 初始子间隔的范围用[，)表示。令，和。 步骤2：L和R的二进制表达式分别表示为： 和 其中和等于“1”或者“0”。 比较和：①如果，不发送任何数据，转到步骤3；②如果，就发送二进制符号。 比较和：①如果，不发送任何数据，转到步骤3；②如果，就发送二进制符号。 … 这种比较一直进行到两个符号不相同为止，然后进入步骤3， 步骤3：加1，读下一个符号。假设第个输入符号为，按照以前的步骤把这个间隔分成如 下所示的子间隔： 令，和，然后转到步骤2。 表4-05 编码过程 步骤 输入 符号 编码间隔 编码判决 1 10 [0.5, 0.7) 符号的间隔范围[0.5, 0.7) 2 00 [0.5, 0.52) [0.5, 0.7)间隔的第一个1/10 3 11 11 [0.514, 0.52) [0.5, 0.52)间隔的最后一个1/10 4 00 [0.514, 0.5146) [0.514, 0.52)间隔的第一个1/10 5 10 [0.5143, 0.51442) [0.514, 0.5146)间隔的第五个1/10开始，二个1/10 6 11 [0.514384, 0.51442) [0.5143, 0.51442)间隔的最后3个1/10 7 01 [0.5143836, 0.514402) [0.514384, 0.51442)间隔的4个1/10，从第1个1/10开始 8 从[0.5143876, 0.514402中选择一个数作为输出：0.5143876 表4-06 译码过程 步骤 步骤 间隔 译码符号 译码判决 1 [0.5, 0.7) 10 0.51439在间隔 [0.5, 0.7) 2 [0.5, 0.52) 00 0.51439在间隔 [0.5, 0.7)的第1个1/10 3 [0.514, 0.52) 11 0.51439在间隔[0.5, 0.52)的第7个1/10 4 [0.514, 0.5146) 00 0.51439在间隔[0.514, 0.52)的第1个1/10 5 [0.5143, 0.51442) 10 10 0.51439在间隔[0.514, 0.5146)的第5个1/10 6 [0.514384, 0.51442) 11 0.51439在间隔[0.5143, 0.51442)的第7个1/10 7 [0.51439, 0.5143948) 01 0.51439在间隔[0.51439, 0.5143948)的第1个1/10 7 译码的消息：10 00 11 00 10 11 01 [例3] 假设有4个符号的信源，它门的概率如表4-07所示： 表4-07 符号概率 信源符号ai 概率 初始编码间隔 [0, 0.5) [0.5, 0.75) [0.75, 0.875) [0.875, 1) 输入序列为。它的编码过程如图4-04所示，现说明如下。 输入第1个符号是，可知，定义初始间隔[，)＝[0.5, 0.75)，由此可知，左右边界的二 进制数分别表示为：L＝0.5=0.1(B)，R＝0.7＝0.11… (B) 。按照步骤2，，发送1。因 ，因此转到步骤3。 输入第2个字符，，它的子间隔， )＝[0.5, 0.625)，由此可得=0.125。左右边界的二进 制数分别表示为：L＝0.5=0.100 … (B)，R＝0.101… (B)。按照步骤2，，发送0，而和 不相同，因此在发送0之后就转到步骤3。 输入第3个字符，，, 它的子间隔[, )＝[0.59375, 0.609375)，由此可得=0.015625。左 右边界的二进制数分别表示为：＝0.59375=0.10011 (B)，＝0.609375=0.100111 (B)。 按照步骤2，，，，但和不相同，因此在发送011之后转到步骤3。 … 发送的符号是：10011…。被编码的最后的符号是结束符号。 图4-04 算术编码概念 就这个例子而言，算术编码器接受的第1位是“1”，它的间隔范围就限制在[0.5, 1)， 但在这个范围里有3种可能的码符, 和，因此第1位没有包含足够的译码信息。在接受第 2位之后就变成“10”，它落在[0.5, 0.75)的间隔里，由于这两位表示的符号都指向开 始的间隔，因此就可断定第一个符号是。在接受每位信息之后的译码情况如下表4-08所 示。 表4-08 译码过程表 接受的数字 间隔 译码输出 1 [0.5, 1) [0.5, 1) - 0 [0.5, 0.75) 0 [0.5, 0.609375) 1 [0.5625, 0.609375) - 1 [0.59375, 0.609375) … … … 在上面的例子中，我们假定编码器和译码器都知道消息的长度，因此译码器的译码过程 不会无限制地运行下去。实际上在译码器中需要添加一个专门的终止符，当译码器看到 终止符时就停止译码。 在算术编码中需要注意的几个问题： 由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多数机 器都有16位、32位或者64位的精度，因此这个问题可使用比例缩放方法解决。 算术编码器对整个消息只产生一个码字，这个码字是在间隔[0, 1)中的一个实数，因此 译码器在接受到表示这个实数的所有位之前不能进行译码。 算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译 错。 算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。 在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改 ，在编码期间估算信源符号概率的过程叫做建模。需要开发动态算术编码的原因是因为 事先知道精确的信源概率是很难的，而且是不切实际的。当压缩消息时，我们不能期待 一个算术编码器获得最大的效率，所能做的最有效的方法是在编码过程中估算概率。因 此动态建模就成为确定编码器压缩效率的关键。