一种新型的无损视频压缩算法

第28 卷第3期 2 00 6 年 3 月 电 子 与 信 息 学 报 Jo u rn a l o f E le e tro n ie s & In fo rm at io n Te ehn o lo gy 从 , 1. 2 8N o . 3 M a r . 2 0 0 6 一种新型的无损视频压缩算法 夏 杰 侯朝焕 (中国科学院声学研究所 北京 100 08 0) 摘 要 多次使用有损压缩技术压缩数字视频 , 会导致视频的质量大幅下降 , 从而降低了数字视频的可再利用率 , 为此设计了一种新型的无损视频压缩算法 。 该算法的特点在于 : (l)提出了一种改进的基于上下文树的算术编码来 压缩运动补偿后的误差帧 。 (2 )针对改进的算术编码 , 优化基于宏块的运动估计与补偿算法 , 以提高无损视频压缩 算法的压缩率。 对于压缩运动补偿后误差帧的算法 , 与静态图像无损压缩算法 JP E G 一LS 和 CA LI C 相比明 , 该文 设计的无损视频压缩算法的压缩率超过 JP E G 一L S 算法最高为 23 . 3% , 超过 CA LI C 算法最高为 19 .3 % 。 关键词 无损视频压缩 , 算术编码 , 运动估计与补偿 中图分类号 : TN g lg . 8 文献标识码 : A 文章编号 : 1009 一5 896 (20 06)03 一0 38 5 一0 5 L o ssless Vi d eo C o m Pr essio n Syste m D esig n a tio n X ia Jie H o u C ha o · hu a n (加占功翻te oj 刁c 口us l祀s , Ch ~ e A c Q de 坦F of sc ien ce , Be夕才ng 1000 80 , Ch in a ) A b str a e t It w ill e re at e the Pro ble m o f g re a t de g r ad at io n in v ide o qu a lity , w he n the d ig ita l v id e o is e o m Pre s se d by u s in g lo s sy v ide o e o m Pre ss io n a lg o rithm m o re tha n o n e e . T hat w ill re d u e e the rat e o f re u s in g the dig ita l v ide o . T hu s a n ew lo s sle ss v ide o e o m Pre ss io n a lg o rith m ha s be e n Pro Po se d . T h is a lg o rithm fe at u re s in : (l) a n im Pro v ed e o n te xt 一 tre e ba s ed a r ith m e tie eo d in g 15 Pro Po se d to e o m Pre ss the re s id u a lfra m e afte r m o tio n e o m Pe n sa tio n , a n d(2 )m a e ro 一 blo e k ha se d m o tio n e stim at io n an d e o m Pe n sat io n m e tho d 15 o Pt im iz e d to im Pro v e the e o m Pre s sio n rat io o f lo ssle s s vide o e o m Pre ss io n a lg o rith m , w ith e o n s ide rat io n to th e im Pro v e d ar ithm e tie e o d in g . W he n u s in g JPE G 一 L S a n d CA LIC , the e x istin g stat e 一o f- the 一a rt in lo ssle ss e o m Pre ss io n o f s till im a g e s , to e n eo de tho se m o tio n 一e o m Pe n sa te d e rr o r- fr a m e s o r re s id u e fr a m e s to fo rm u lat e be n c hm a rks , the e x Pe rim e n ts illu strat e that the Pro Po se d a lg o rithm o ut Pe rfo rm s JPE G 一 L S by uP to 2 3 . 3% , a n d CA LIC by uP to 19 3 % . K ey w o r d s L o s s le ss v ide o e o m Pre ss io n , A rithm e tie e o d in g , M o tio n e stim a tio n a n d e o m Pe n sat io n 1 引言 由于有限的网络带宽和人类视觉系统的不敏感性 , 有损 压缩技术成为了数字视频压缩研究领域的主流 , 其中的代表 是 M PE G 系列fl. 2] 和 H. 26 x 系列131 视频压缩 。 有损压缩技 术利用舍弃一些人类视觉不敏感的视频图像信息 , 来获取较 高的压缩比率。 但是当我们多次使用有损压缩技术压缩数字 视频时 , 可能丢失非常大的信息量 , 从而导致压缩后的视频 质量非常低 , 这就大大降低了数字视频的可再利用率。 无损 视频压缩技术则可以在压缩过程中保持完整的视频信息 , 从 而避免了压缩失真 。 无损视频压缩技术之所以没有得到应有的关注 , 其中的 原因包括 : (l) 无损视频压缩可以达到的压缩率远远赶不上 实际应用的需要 ; (2) 大部分的数字视频应用产品并不需要 解压的视频效果达到无损的级别 。 然而随着网络带宽的增加 和人们对高质量数字视频需求的提高 , 高质量数字视频的无 损压缩可能成为学术界和工业领域未来发展的方向。 在 e 一ci n e m a 中 , 高质量数字电影采用逐帧渐进式的播放模式 , 而且每一帧都采用无压缩的三原色图像文件 。 在这样情况 下 , 无损视频压缩技术将会对高质量数字电影的存档 , 发行 和编辑等应用起到很大的帮助 。 本文在 MPE G Z 的基础上设计了一个新型的无损视频压 缩算法 , 提出了一种改进的基于上下文树的算术编码算法作 为无损压缩算法中的嫡编码算法部分 , 同时针对改进的嫡编 码算法 , 优化了MPE G 一2 中基于宏块的运动估计与补偿算法 , 以提高无损视频压缩算法的压缩率 。 2 0 0午的一1 6 收到 , 2 0 0 5 一0 1一0 7 改回 国家 9 73 (G 一9 9 90 3 2 9 0 0 )和国家自然科学基金(6 0 0 2 8 一0 2 )资助课 题 2 无损视频压缩算法的结构 Moti on 一 JP E ol 4 1视频压缩标准中提供了无损压缩的模式 , 38 6 电 子 与 信 息 学 报 第 2 8 卷 在整体上定义整个视频码流的数据格式 , 而每幅单帧的编码 则分别由无损图像压缩算法进行处理 , 标准中不使用任何视 频帧间编码算法 。 Mot io n 一JP E G 的框架虽然在硬件实现的成 本上有一定的优势 , 但是无法利用视频中包含的时间域上的 信息冗余也是相当大的损失 。 3D JPE G 一L s[ 5,6 ] 线性组合一系 列基于参考帧的时间预测算子和 JP E G 一L S1 7 一9] 中的空间预测 算子 , 形成新的预测算子去估计需要编码的像素 , 但是预测 效果依赖于线性系数的选择 , 同时基于图像压缩的框架不利 于与现有发展成熟的有损视频压缩算法进行互补 , 基于这个 原因, 我们研究无损视频压缩算法的策略是 , 在 目前最好的 有损视频压缩算法的基础上 , 通过移除有损视频压缩算法中 的有‘损子算法部分 , 使用新的无损子算法取代而设计新的无 损视频压缩算法 。 这样设计的另一个好处在于不同的子算 法 , 比如运动估计和嫡编码 , 可以在平等的基础下进行性能 比较 。 由于 M PE G 一4 和 M PE G 一2 在基本压缩算法上 , L匕如 运动估计 , D C T 和墒编码上采用类似的设计 , 所以我们采用 M PEG 一 2 作为基础设计新的无损视频压缩算法 。 给定一个数字视频序列 , 我们根据不同的场景 , 将视频 序列顺次分成若干个 G O P( 图像组), 每个 G OP 中视频帧的场 景基木一致 , 并且 C O P 之间的场景有明显的变化 。 由于场 景发生了变化 , 所以对于每个 G O P 中的第一个帧 , 算法直 接使用 JPE G 一LS 进行帧内编码 , 而不使用运动估计一与补偿 , 类似 M PE G 一2 中的 I帧 。 对于 G O P 中的其余帧 , 算法则通 过由前一帧的运动预测和补偿 , 去除时间域上的信息冗余 , 然后使用墒编码算法编码运动补偿的误差和运动向量 , 类似 M PE G 一 2 中的 P帧 。 图 l给出了新的无损视频压缩算法的整 体结构 。 无损视频压缩算法需要消除两种信息冗余 : 像素原始值 之间的信息冗余和预测后误差值之间的信息冗余 。 因此要优 化无损视频压缩算法 , 重点应该放在两方面 : (l )优化运动估 计和补偿子算法部分 , 更好地去除像素原始值之间的信息冗 余15, 6] , (2 )优化嫡编码子算法部分 , 更好地去除预测后误差值 之间的信息冗余 。 本文的重点集中于优化嫡编码子算法部 分 , 提出了一种改进的基于上下文树的算术编码 , 作为无损 视频压缩算法中的嫡编码子算法部分 , 来提高无损视频压缩 算法的压缩率 。 同时针对 M PE G 一2 框架中的基于宏块的运动 估计和补偿算法进行了优化 , 使之可以配合墒编码子算法部 分 , 从而发挥更好的效果 。 根据我们在有损视频压缩研究上的经验 , 在视频图像序 列采用 YU v 格式的情况下 , 运动估计和补偿可以取得更佳 的效果 。 所以我们依然在 YU V 格式上执行运动估计和补偿 算法 , 这一点和 M PEG 一2 一样 , 不同的是在我们的算法中 , 颜色向量 U 和 V 的图像尺寸和 Y 向量的图像尺寸一保持一致 , 以避免信息的丢失 。 预测后的运动向量分别储存于 X 分量帧 和 Y分量帧 , 这样可以更好地去除各运动分量帧内的空间信 息冗余 。 视频图像序列 二厂尸一 G O P I IPPPPPP ! _ G p卯 }I G o p 3 1 1 IPI, PFP只 ! 1 IPPPPPP ! GGG O P IIIII JPE G 一 LSSSSSSSSSSSSSSSSS IIIPPPPPPPPPPPPPP 输出的比特特 PPPPPPP 运动 III句量量 XXXXXXXXXXXXXXX 分JJJ致帧帧 图 1 无损视频压缩算法的蔡体结构 3 改进的基于上下文树的算术编码 虽然在无损视频压缩方面的研究工作不多 , 但是对于嫡 编码的研究却非常广泛 , 尤其在文木压缩和静态图像压缩方 面 。 在己经发表的研究算法中 , 我们发觉这一领域最好的技 术可以为 : (1 )基于树结构统计模型的算术编码 ; (2) 基于 简化统计模型的 G ol o m b 编码 。 前者代表了理论上最好的技 术 , 通过为误差建立复杂的统计模型 , 来获取更好的压缩效 率 , 但是需要花费更多的计算代价, c A LI cl ’0J是使用这一技 术的代表 。 后者代表了实际运用上的最好技术 , 通过为误差 建立简化的统计模型 , 可以在花费较低计算代价的情况 下取 得相对不差的压缩效率 , 从而更加适合于在硬件和软件上的 实现 , JP E G 一 LS 是使用这一技术的代表 。 由于无损视频压缩 算法的压缩效果很大程度上依赖于嫡编码 , 所以我们希望设 计一种嫡编码算法既能够保留基于树结构统计模型的算术 编码的压缩效率 , 同时又可以通过简化结构和缩小计算复杂 度来提高编码的速度 , 使之可以适应于实际应用的需要 。 基 于这个 目的 , 我们根据以下 3 个原则改进基木算术编码 l川 和基于树结构的统计模型砂21 。 (l )对于误差帧的每个误差像素 “ x ” , 使用其附近的 4 个 误差像素来建立上下文序列 , 具体结构如图 2 (a) 所显示 。 对 于边界上的误差像素 , 上下文序列的长度可以根据其所在的 位置进行调整 , 原则如下 : (a )第一行的第一个误差像素没有 上下文序列 : (b )其他所有第一行的误差像素的上下文序列中 只有 “ I ’, : (c )其他所有第一列的误差像素的上下文序列只有 “ 2 ” 和 “4 ” ; (4 )其他所有最后一列的误差像素的J: 下文序 列只有 “ l” , “ 2 ” 和 “ 3 ” 。 与 C A L IC 算法中使用的误差统 计模型相比较 , 我们仅仅选择了和 “ x ” 的 4 个相邻位置的 误差像素(C A LI c 算法中为 7 个)来建立上下文序列 。 虽然我 们使用了较少的上下文 , 但是这 4 个误差像素与 “ x ” 的关 联最大 , 并且没有像在 C A LI C 算法中那样 , 被量化后才用 于产生上下文 , 所以我们实际使用的上下文的数目超过了 CA LI c 算法(5 76 X 8) , 这样可以更加准确地估计误差的统计 模型 。 (2 )通过计算 “ x ” , “ lx ” , “ 1 2 x ” , “ 123 x ” , 和 “ 12 3 4 x ” 第 3 期 夏 杰等: 一种新型的无损视频压缩算法 3 87 在误差帧中出现的次数 , 来建立误差值 “ x ” 基于不同上下 文的条件概率统计模型 。 p (x l’)二艺n l(x )炸云n l(y ) n 12 (x ) 丫 二 P( 川 n =l J‘. 日J 〔 七 P(x }12 )“ 艺, 、n lZ (, ) 艺、 , p ( x }12 ) = I P(x {12 3) = n 12 3(x ) (1) 艺, , n . 2 3(y) 艺、 : p ( x 112 3) = l 八二 . 12 34 ) = 一丛巡些一 丫 二尸(: , , 23 4、一 , 2 一二 n : 2 、4 (夕) ~ ·。 。一了“ 其中 。, (x )代表了 : 与上下文序列 : 一起出现的次数 , 若代 表所有可能的误差值 。 所有的条件概率统计模型按照相应的 上下文组织在一个类似文献[1 21 的树形数据结构内 , 我们称 之为上下文树 。 由于上下文序列最多只能由 4 个误差像素构 成 , 所以上下文树中最多只包含 4 层子节点 , 每个子节点代 表了 1 个基于在这个节点之前所出现的所有上下文的误差值 的条件概率统计模型 。 图 2 (b) 展示了一个典型的上下文树的 例子 。 为了减少计算的代价和算法的复杂度 , 我们没有像文 献〔12] 一样 , 为每个误差值 “x ” 建立全部的四个上下文节点 : “ lx ” , “ 12 x ” , “ 12 3 x ” , 和 “ 123 4x ” , 因为在误差帧中 , 唯 一路径上的上下文节点的频率计数是完全一样的 , 所以我们 可以合并这些节点成为一个节点 , 并建立一个分支连接这个 节点到上下文树相应的位置 , 因此每个分支代表了这些频率 计数相同的上下文 。 图 2 (b) 中的树可以简化成图 2 (c) 中的结 构 。 (3) 在上下文树中的每个节点上我们只对在该节点出现 的误差值进行频率计数和保存 , 而不是对所有可能的误差值 进行频率计数 , 因此每个节点的统计模型中都含有一个“ U S ” (u nk o w n 一 sym bo l)符号来编码在统计模型中新 出现 的误差 值 。 (a) 卿 图 2 (a ) 上下文结构 (b) 上下文树的典型例子 (c )简化的上下文树 基于以上 3 个原则 , 对于视频序列中的每一个尸 帧 , 我 们都建立一个上下文树来编码运动补偿后误差帧中的误差 像素 。 首先对于一个需要编码的误差像素 “ x ” , 从上下文树 的根节点起开始搜索 , 依次匹配 “ x ” 的上下文序列 “ 12 34 ” , 直到出现第一个无法匹配的上下文 。 这时 , 在上下文树中的 搜索停止位置可以分为 4 种情况 : (a) 搜索停止在 roo t节点 , 上下文序列中没有一个上下文得到匹配 : (b) 搜索停止在一个 己经存在的非 : oo t节点 , 上下文序列全部得到匹配 ; (c) 搜索 停止 在一个已经存在的非 roo t节点 , 上下文序列部分得到匹配 ; (d )搜索停止在上下文树中的一个分支上 。 对于情况(a ), 根据 roo t 节点的统计模型编码误差像素 “x ” , 如果 ro ot 节点下没有误差像素 ‘,x ” 的频率计数 , 则 编码一个 “ U S ” 符号 , 同时将误差像素值 “ x ” 输入到一个 文件 us fi le 中保存 。 初始化一个 “ 123 4x ” 的节点 , 同时将整 个上下文序列 “ 1234 ” 作为一个分支连接 r on t节点和新产生 的 “ 123 4x ” 节点 , 然后 ro ot 节点统计模型中误差像素值 “ x ” 的频率计数加 1 。 在使用误差值 “x’’初始化一个节点 尸的统计模型时 , 只 保存 ,’x ” 和 “ U S ” 两个值的频率计数 , 且分别记为 1 。 对于情况(b ), 假设搜索停止在一个节点 尸上 , 如果在节 点 尸 的统计模型中 , 各个误差值的频率计数的总和大于一个 预定的闽值 Thr e sho ld( 表明该节点 己经发展成熟), 则根据节 点尸 的统计模型编码误差像素 “ x ” 。 否则上移到节点尸 的父 节点厂 , 如果在节点厂的统计模型中 , 各个误差值的频率 计数的总和大于 T h re sho ld , 则根据节点厂的统计模型编码 误差像素 “ x ” 。 否则依次类推 , 直到达到 roo t节点 。 在编码 过程中 , 如果需要编码的节点下没有误差像素 “ x ” 的频率 计数 , 则编码一个 “ U S ” 符号 , 同时将误差像素值 “ x ” 输 入到一个文件 us . fil e 中保存。 从节点 尸到 : oo t 节点路径上的 所有节点统计模型中误差像素值 “ x ” 的频率计数加 l。 对于情况(c ), 假设搜索停止在一个节点 尸上 , 匹配的上 下文序列为 “ 12 ” , 未匹配的序列为 “ 34 ” , 使用情况(b) 的算 法在节点 尸上编码误差像素 “ x ” , 然后初始化一个 “ 123 4x ” 的节点 , 同时将未匹配的上下文序列 “ 34 ” 作为一个分支连 接节点 尸和新产生的 “ 1 2 3 4x ” 节点 。 对于情况(d ) , 假设搜索停止在一个分支 B “ 2 34 ” 上 , 未匹配的上下文序列为 “4’ ” ,使用情况(b) 的算法在分支 B 的父节点 “ lx ” 上编码误差像素 “ x ” 。 由于分支 B 产生了新 的分支 , 所以分支 B 将分裂为两个分支 : “ 23 ” 和 “ 4 ’, 。 同时 产生一个节点 “ 12 3 x ” 作为分支 “ 2 3 ” 和 “ 4 ” 的连接点 , 其统计模型直接从父节 点 “ 1x ” 继承 。 然后初始化一个 “ 1 234’x ” 的节点 , 同时将未匹配的上下文序列 “ 4’ ” 作为 一个分支连接节点 “ 一2 3x ” 和 “ 1 2 34 , x ” 。 最后完成单幅误差帧的编码后 , 剩余的 us .fi le 使用基木 算术编码 [1l 1 直接编码 , 同时 x 和 y 运动分量帧分别采用 与 编码误差帧相同的方法进行压缩编码 。 在该算法中 , 我们仅使用发展成熟的节点来编码误差 值 , 这样可以解决由于上下文数目过多而产生的上下文稀释 问题 , 同时在更新上下文树的时候 , 没有通过量化误差值来 削减上下文的数 目, 可以使建立起来的上下文树更加符合误 差分布的实际统计规律 , 从而取得更高的压缩率 。 3 8 8 第 2 8 卷 4 优化的基于宏块的运动估计和补偿算法 M PE G 一 2 框架中 P 帧的运动估计和补偿算法是基于 16 x 16 的宏块实现的 , 对于当前帧的每个宏块 , 从前一参考帧 中寻找最相似的宏块 , 进行求差运算 , 从而得到误差值 , 宏 块的偏移量则是该宏块的运动向量 。 对于以 (x , 力 为起点的 宏块 , 运动向量(Vx , 称)和是通过下列公式获得的 : 15 15 sA D (Px ,弓)=艺艺}月一 (Px + ‘,弓+ j)一月(x + ‘, , + 川 (2) j = o j= 0 间相邻像素的误差值变化不会太大 , 从而降低了对这些像素 误差值的编码代价 , 而且从整幅误差帧的角度来看 , 误差值 的全局关联性得到了一定的保证 , 从而降低了上下文树中节 点的数 目 , 节约了运算时间 。 权值 盯 的引入就是为了取得全 局关联性和局部关联性的平衡点 , 通过实验 , 我们发现权值 口取值为 0. 4 适用于很多情况 。 实验结果与分析 (x’ , y’) =( 凡,弓)满足 : {尺 一 x l< 1 1, 1弓一 川< 11 , K 一 x ’一 x, 价= 厂一 y (3) sA D( 凡助为最小值 { 其中月和式_ . 分别是第 t帧和第 卜 1 帧 。 该宏块 中的每一个像 素 (i , 力 运动补偿 后的误差值 E (i , j)为 E (i , j) = 式(i, j)一月一、(i + Vx , j + 称) (4 ) 改进的基于上下文树的算术编码算法侧重于提取误差 帧中空间信息冗余 , 误差值之间关联性越大 , 越容易获取更 大的压缩率 。 根据式(3) , MPE G 一2 框架中运动估计和补偿算 法使用的宏块预测标准是最小化误差绝对一值之和(S A D ), 但 是在满足最小化 SA D 标准的预测结果中 , 有些宏块的预测 误差值之间的波动比较大 , 反映出相邻像素误差值之间的关 联性被减弱了 , 在这种情况下会降低使用改进的基于上下文 树算术编码算法的性能 。 因此我们在 SA D 的计算公式中引 入 一个反映宏块预测误差值之间关联性的参考变量 CO R , 使 得预测误差值可以更好地被压缩 。 新的 sA D 倒ew SA D )的计 算公式如下 : N ew SA D = S A D + 口 · CO R . C o R = 艺艺}E (‘, j. )一厄}, 云二止 2 56 艺艺E (i , j) (5) i, o j = 0 i= O J= 0 其中E (i , 力 是宏块中预测后的误差值 , 口是相应的权值 。 优化后的宏块预测标准就变为最小化 N ew SA D 。 从式(5) 中可以发现 , 在运动估计的过程中 , 我们依然需要将预测误 差值尽可能地保持在一定的范围内 , 这样不仅可以使宏块之 我们使用 5 个标准的 M PEG 一2 测试视频 : M o b ile , F一o w e卜o a rde n , su s ie , Mo m , 几a b le 一介n n is 和 l个使用摄像机 拍摄的视频 : O S U 一2 , 进行了两组对比实验 , 来验证设计的无 损视频压缩算法的优越性 。 在第 l 组实验 中 , 比较在 Mo tio n 一 JP EG 的框架下 , 分别使用 JPEG 一 LS 和 C A LIC 两种 目前最好的无损图像压缩算法产生视频每一帧内容的码流 的无损视频压缩算法 , 与使用我们设计的基于M PE G 一2 框架 的无损视频压缩算法 1(嫡编码子算法部分采用基木算术编码 11 ’〕以及保留 MPE G 一2 中原有的运动估计与补偿算法)分别压 缩测试视频的结果 , 从中我们发现 M P E G 一2 框架下使用帧间 基于宏块 的运动估计 与预测 算法的压缩效 果明显好于 M o tio n 一 JPEG 框架下 JPE G 一L S 和 CA L IC 中仅使用的帧内空 间预测的算法 , 表 l 列出了第 1 组实验的详细结果 。 在第 2 组实验中 , 我们将无损视频压缩算法 l的嫡编码 部分替换为提出的基于上下文树的算术编码 , 同时使用优化 的运动估计与补偿算法形成无损视频压缩算法 2 。 而参照算 法变为 : 参照算法 l使用 JP E G 一L S 来压缩运动补偿后的误差 帧 ; 参照算法 2 使用和 C A LI C 来压缩运动补偿后的误差帧 。 通过对比实验 , 从中我们发现提出的基于上下文树的算术编 码可以更加准确的估计预测误差的统计模型 , 从而压缩率超 过使用 JP EG 一LS 的参照算法最多为 20 . 1% ,超过使用 CA LI C 的参照算法最多为 18 % , 表 2 列出了第 2 组实验的详细结果 。 在算法实现的复杂度方面 , 相比于基本算术编码 l” ] , 计 算量主要增加在庞大的上下文树中搜索 , 找到合适的节点 。 通过在每个节点的对象中加入一个长度为 2 56 , 初始值为空 的指针数组 , 将子节点的指针放入数组中以子节点包含的上 下文序列第一个数值的位置中 , 这样匹配字符时就可以直接 表 l 无损视频压缩算法对比实验的结果(压缩比) 视视频名称称 视频尺寸寸 Mo tio n 一JPE G + JPE G 一LSSS M o tio n 一JPEG + C AL ICCC 无损视频压缩算法 lll MMM o bileee 72 0 X 5 7 666 1 6 9 : lll 1 . 7 1: lll 2 ‘ 2 3 : 111 FFFlo w er 一 G a rd ennn 3 52 X 2 4 000 1 3 0 : lll 1 . 3 3 : lll 1 . 7 8 : lll SSS u sieee 72 0 X 4 8 000 2 , 15 : lll 2 . 18 : lll 3 0 1: 111 MMM o mmm 36 0 X 2 4 000 2 . 24 : lll 2 . 2 4 : lll 2 j 3 : lll TTTa bl e 一te n n isss 3 52 X 2 4 000 1 . 33 : lll 1 . 3 5 : 111 2 2 9 : III OOO S U 一 222 3 2 0 X 2 4 000 1 . 84 :lll 1 . 8 5 : lll 2 . 0 3 : l 第 3 期 夏 杰等 : 一种新型的无损视频压缩算法 3 89 表 2 使用基 于上下文树的算术编码后无损视频压缩算法对比实验的结果 视视频名称称 视频尺寸寸 参照算法 lll 参照算法 222 无损视频压缩缩 对 比参照算法 111 对 比参照算法 222 算算算算算算法 222 的提高(% ))) 的提高(% ))) MMM o bileee 72 0 X 5 7 666 2 . 1 8 : lll 2 . 2 8 : lll 2 . 4 8 : lll 13 . 888 8 . 888 FFFlo w e r- G ar d ennn 35 2 X 2 4 000 1 . 8 1 :lll 1 9 1 : lll 1 . 9 9 : lll 9 . 999 4 . 222 SSSU S ieee 7 20 X 4 8 000 2 8 3 : 111 2 9 8 : lll 3 . 4 9 :lll 2 3 . 333 17 . 111 MMM o mmm 3 60 X 2 4 000 2 . 9 2 : lll 2乡6 : lll 3 . 5 3 :lll 2 0 . 111 19 . 333 TTTa bl e 一te n n isss 3 5 2 X 2 4 000 2乃8 : 111 2 6 3 :lll 2 87 :lll 1 1 . 222 9 . 111 OOOS U 一 222 3 2 0 X * 24 000 2 . 1 1: lll 2 . 19 :lll 2 . 32 :lll 9 . 999 5 . 999 访问包含下一个上下文的节点 , 直到遇到空指针 。 对于压缩 一幅像素总数为 N 的误差帧来说 , 比较基本算术编码11 ’】, 计 算复杂度的增加为 0 (N ) 。 当然添加指针数组使每个节点的 对象大小增加了大概 5 12 个 byte , 考虑上节点对象包含的统 计概率数组的大小 , 在不做任何优化的情况下 , 每个节点在 内存中大约占据 1 . skby te 。 这样在最坏的情况下(编码每个节 点时都产生两个新的节点), 对于 35 2 X 24 0( CI F) 大小的误差 帧进行编码时 , 整个上下文树将有 2 X 35 2 X 240 个节点 , 大 约需要占据 25 0M 的内存空间 。 目前的个人 PC 己经可以忍 受这样的空间代价。 5 结束语 木文在 MPEG 一2 的基础上设计了无损视频压缩算法 , 提 出了一种改进的基于上下文树的算术编码来压缩运动补偿 后的误差帧, 同时针对改进的算术编码 , 优化基于宏块的运 动估计与补偿算法 , 以提高无损视频压缩算法的压缩率 。 从 实验结果发现 , 相比于 JP E G 一 LS 和 CA LI C 中使用的帧内预 测模型 , 基于宏块的帧间运动估计可以取得更好的预测结 果 , 使得补偿后的误差帧更加易于压缩 。 同时提出的基于上 下文树的算术编码可以更好估计补偿误差的概率分布 , 配合 优化后的运动估计与补偿算法 , 从而进一步提高无损视频压 缩算法的性能 。 进一步的工作可以把重点放在开发更好的运 动估计 与补偿算法 , 比如类似 H .2 64 中的基于可变尺寸块的 运动估计算法 , 或者基于对象的运动估计算法 , 来提高无损 视频压缩算法的性能 。 参 考 文 献 [2 ] 15 0 / IE C JT C I/ SC 2 9/ W G l lN 2 7 2 5 , MPEG 一 4 0 ve rv iew , 19 9 9 - 【3 ] TU 一T D r a ft , H 2 6 3 , V id eo C o d in g fo r L o w B it R ate C o m m u n ie atio n , 19 9 8 - 【4」 B ha sk ar an V , K o n stan tin id e s K . Im ag e a n d V id e o C o m Pre ssio n Sta n d a rd s : A lg o rithm s a nd A rc h itee tu re s . N o rw e l卜 Klu w e r A c a d em ie P ub lishe rs , 19 9 7 : 15 一 19 5 . [5 ] C ar o tt i E S G , D e M a rt in J C , M eo A R . L o w 一 c o m Ple x ity Io s sless v id eo e o d in g v ia a dap tiv e sPat io 一tem Po ra lPre d ie tio n . Pr o ee ed in g s . 20 0 3 In te rn a tio n a l C o n fe re n ee o n Im ag e Pr o e ess in g , B a re e lo n a , 2 0 0 3 : 19 7 一 2 00 . [6 1 B r un ello D , C a lv ag n o G , M ian G A , R in a ld o R . L o ssle ss e o m Pre ssio n o f v id eo u sin g tem Po r al in fo r m a tio n . 了石石E T) ℃n s . o n Im ag e Pro cess ing , 2 0 0 3 , 1 2(2 ): 5 7 5 一 5 8 6 . 【7 ] W ein b e rg e r M J, Se ro u ssi G , Sa Piro G . T he LO CO ·1 lo s sless im ag e eo m P re ssio n a lg o rithm : Prin eiPle s a n d stan d ar d iz atio n in to JPE G · LS . 了E石石升 口n s . o n Im a g e Pr o e es s ing, 2 00 0 , 9(8 ): 13 0 9 一 1 32 4 . ts] 15 0 / IE C 14 4 9 5 一 l , IT U R e eo m m e n d at io n T . 8 7 , In fo r m atio n tee hn o lo gy—L o ssle ss an d n e ar 一lo ssle ss e o m Pre ssio n o f e o n tin u o u s 一 to n e stillim a g es , 19 9 9 . 【9 1 15 0 /IE C FCD 14 4 9 5 一2 , JPE G 一L S P art Z , 2 0 0 0 . 【10 ] W u X , M e m o n N . C o n tex t一b a se d a d aPtiv e lo ssle ss im ag e eo d in g . IE E E Tr a ns . o n Co m m u n ic a tio n s , 19 9 7 , 4 5(4 ): 4 3 7 一 4 4 4 . [1 1 ] W itt e n I H , N ea l R M , C lea ry J G A rithm e tie eo d in g fo r d ata eo m Pre ss io n . Co m m u n iea tio ns of rh e A CM, 19 8 7 , 3 0(6 ): 5 2 0 一 5 4 0 . [12 ] W 亡inb erg e r M J , R issa n en J J, A rp s R B . A PPlie atio n s o f u n iv er sal eo n te x t to lo ss les s eo m Pr e ssio n o f g r ey 一 le v e l im a g es . 了石石石升口n s , o n lm ag e Pro c es si儿g , 19 9 6 , 5(4 ): 5 7 5 一 5 8 6 . 【l] M ite hell J L , Pe n n ebak e r W B , Fo g g C E , L eG a ll D J. MPE G V ide o : C o m Pre ssio n Sta nd ard N e w YO rk : C haPm a n & H a ll , 19 9 6 ! 17 1 一 3 3 3 . 夏 杰 : 侯朝焕 : 男 , 19 7 9 年生 , 博士生 , 研究方向为图像与视频处理 . 男 , 19 3 6 年生 , 中国科学院院士 , 研究方向为信息和 信号处理 、 声学等 .