基于上下文自适应算术编码的设计与实现

29 0年6月 0

电脑学习

第3 期

基于上下文自适应算术编码的设计与实现 安向明’ 张丹邹红 摘要：实现了经典算术编码的流程设计。提出基于上下文自适应算术编码的算法。建立了基于上下文的多阶自适应的概率 模型 .其符号的压缩码长尽量的接近其熵值。使

关键词：图像压缩

算术编码

自适应模式

中图分类号： T 998 N 1.1

文献标识码： A文章编号：0 2 22 ( 0 9) 3 0 0— 2 10— 4 2 20 0 - 17 0

De in a d Re l a i n o n e t b s d Ad p v i m e c Co i g sg n ai t f Co tx - a e a t e Art z o i h i t dn An a mi Xing ng Zh n n a g Da Z n ou Ho g

Ab t a t T e p p r rai s te f w c atd s n o a io a r h t o ig a d it d c s a d pie bn r r h t sr c: h a e el e h o h r e i ft d t n lai me c c dn,n nr u e n a a t iay ai me- z l g r i t i o v t i o n loi m ae i mut- re o tx. e he p p r as uls mut- r e o tx d pie p o a ii c c dig ag rt h b s d Ol liod r c ne tTh n t a e o b i l i od rc ne ta a tv r b b l l d - t d lwhih e a ls te s otn d c e c aa tr amot p ra h i nrp rt. y mo e, c n b e h h re e o d h rce l s d a p o c t e to y ae s

Ke wo d: I g o p e s y r ma e C m rs

A i mei C ig rh t o n t c d

A a t e Mo e d p v dl i

算术编码利用区间代码的原理，是一种到目前为止最佳的熵编码方法Ⅲ。由于算术编码涉及到求一系列字符在『, 0 1区间的概率分布问题， 1并逐渐缩小其区间，需要较长码字， 所以对计算机硬件以及精度方面有严格的限制。本文提出采用树结构图作为码表、上下文模型及中间变量的方式，构造多阶二进制算术编码树，来解决文

本冗余信息的压缩问题。

1算术编码原理 11算术编码算法 .算术编码采用静态模式和自适应模式两种。 在固定模式编码中，随着字符序列的增长，需要的编码 区间从[,】 0 1逐渐的变窄，上下限逐渐的接近。在到达一定的程度时，上、下区间的高位就会出现相同值，如区间『. 0

图 1算术编码流程图表 1算术编码字符概率分配表 字符 a e i O U

塑 :奎

:

:

: .:兰 三

范围【,. 【 2 0】[ 5 0】【6 08【 8 1】 0 0】 0,. 0,. 0, . 0,. 2 . 5 . 6 .】 . 0

0 10,.1 1 0, 1 1 10 1 11小数点后的高位 0 l 1 0 l1是相同的，以可所以把这些相同位进行移位保存，作为当前压缩码流的输出位，再将当前子区间剩余位作为上下位进行以后的运算[ 2 1。 u 。

, U

/ u —、

/

O

固定模式编码需要预先对符号序列中的符号进行预扫 描，根据统计符号的概率来列出编码概率表。引入几个变量：o lw为编码间隔的高端；ag为编码间隔的长度；ag W rn rnl o为编码字符的间隔的低端； s i￣ hs h为编码字符分配的高端。在固定模式编码中，ago rn]w和砌 g i ls l h的编码概率不变。设待编码字符串为 s,初始值为：il 1l 0 rn= hg=, w=,ag l o Is—o l h lw。计算流程如图 1 i。 1 . 2编解码原理 O e

/ O/ O / 一/}一， r/ l —— a 02 .

.j _

e\

a 。

\\ 02 .3

02 .

图 2算术编码示意图

符号所在的概率区间，因为其编码器和解码器采用同样的改变值的方法，以，所其概率模型将会保持相同。

2基于上下文自适应算术编码 21算法提出 .

用例子说明算术编码编、解码原理，采用固定模式符号 概率分配表见表 1。

在自适应算术编码中，信源信号的概率根据编码时符号出现的频繁程度动态地调整，只要监视一小段时间内符号出现的频度，码结果总能趋近信源的熵翻自应算术编。适 编码根据下一个信息符号的预测概率值， (, )区间作将 01进一步分割，得到的码值就是最后分割的子区间

范围。 如果考虑编码符号之间的相关性，把多个符号按照不

若要编码字符串 s ei,=‘a则编码过程如图 2’。 从原理上讲，解码的过程是编码的逆过程，只要保证编码和解码使用同样的字符概率分配表，解码后的字符就不

会出现误差。自应模型中，在适按照一定的次序统计每个符 号出现的频率次数，采用符号的累计频率区间来表示这个

收稿日期：0 8 l— 1 2 0一 2 2安向明大庆师范学院计算机科学与信息技术系助教 (黑龙江，大庆 131 ) 67 2。 17 0