视频压缩编码技术(H.264) 之算术编码

算术?编码?

算术+编码

算术编码?什么鬼

是不是感觉越来越难了呢

(向上滑动查看内容)

早在1948年,香农就提出将信源符号依其出现的概率降序排序,用符号序列累计概率的二进值作为对芯源的编码,并从理论上论证了它的优越性。1960年, Peter Elias发现无需排序,只要编、解码端使用相同的符号顺序即可,提出了算术编码的概念。Elias没有公布他的发现,因为他知道算术编码在数学上虽然成 立,但不可能在实际中实现。1976年,R. Pasco和J. Rissanen分别用定长的寄存器实现了有限精度的算术编码。1979年Rissanen和G. G. Langdon一起将算术编码系统化,并于1981年实现了二进制编码。1987年Witten等人发表了一个实用的算术编码程序,即CACM87(后用 于ITU-T的H.263视频压缩标准)。同期,IBM公司发表了著名的Q-编码器(后用于JPEG和JBIG图像压缩标准)。从此,算术编码迅速得到了 广泛的注意。

算术编码和哈夫曼编码不同,不采用一个码字代表一个输入信息符号的办法,而采用一个浮点数来代替一串输入符号,经算术编码后输出一个小于1,大于或等于0 的浮点数,在解码端被正确地唯一的解码,恢复原符号序列,算术编码的基本原理是将编码的消息表示成实数0和1之间的一个间隔(Interval),消息越长,编码表示它的间隔就越小,表示这一间隔所需的二进制位就越多。

算术编码用到两个基本的参数:符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率,也决定编码过程中信源符号的间隔,而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。

给定事件序列的算术编码步骤如下:

1.编码器在开始时将“当前间隔” [ L, H) 设置为[0,1)。

2.对每一事件,编码器按步骤(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。上面的信息可综合在下表中。

符号

A

B

C

D

概率

0.1

0.4

0.2

0.3

初始编码间隔

[0, 0.1)

[0.1, 0.5)

[0.5, 0.7)

[0.7, 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),…。消息的编码输出可以是最后一个间隔中的任意数。整个编码过程如下表所示

步骤

输入符号

编码间隔

编码判决

1

C

[0.5, 0.7)

符号的间隔范围[0.5, 0.7)

2

A

[0.5, 0.52)

[0.5, 0.7)间隔的第一个1/10

3

D

[0.514, 0.52)

[0.5, 0.52)间隔的最后一个1/10

4

A

[0.514, 0.5146)

[0.514, 0.52)间隔的第一个1/10

5

C

[0.5143, 0.51442)

[0.514, 0.5146)间隔的第五个1/10开始,二个1/10

6

D

[0.514384, 0.51442)

[0.5143, 0.51442]间隔的最后3个1/10

7

B

[0.5143836, 0.514402)

[0.514384,0.51442]间隔的4个1/10,从第1个1/10开始

8

从[0.5143876, 0.514402)中选择一个数作为输出:0.5143876

其译码过程如下表所示:

步骤

间隔

译码符号

译码判决

1

[0.5, 0.7)

C

0.51439在间隔 [0.5, 0.7)

2

[0.5, 0.52)

A

0.51439在间隔 [0.5, 0.7)的第1个1/10

3

[0.514, 0.52)

D

0.51439在间隔[0.5, 0.52)的第7个1/10

4

[0.514, 0.5146)

A

0.51439在间隔[0.514, 0.52]的第1个1/10

5

[0.5143, 0.51442)

C

0.51439在间隔[0.514, 0.5146]的第5个1/10

6

[0.514384, 0.51442)

D

0.51439在间隔[0.5143, 0.51442]的第7个1/10

7

[0.51439, 0.5143948)

B

0.51439在间隔[0.51439,0.5143948]的第1个1/10

8

译码的消息:C A D A C D

想知道更多关于视频压

缩编码技术(H.264)的内容么

那记得及时关注小编的动态

原文发布于微信公众号 - 瓜大三哥(xiguazai_tortoise)

原文发表时间:2018-08-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏王亚昌的专栏

A*算法C实现

参考 http://www.cppblog.com/christanxw/archive/2006/04/07/5126.html 实现了A*算法,模拟了一下,...

952
来自专栏数据结构与算法

2-SAT速成

本文只做总结性说明 2-SAT 2-SAT是k-SAT问题的一种,k-SAT问题在k>=3时已经被证明是NP完全问题 2-SAT问题定义比较简单 有n个布尔变量...

2826
来自专栏深度学习之tensorflow实战篇

tensorflow载入数据的三种方式 之 TF生成数据的方法

Tensorflow数据读取有三种方式: Preloaded data: 预加载数据 Feeding: Python产生数据,再把数据喂给后端。 Reading...

4094
来自专栏bboysoul

1475: C语言实验题――一元二次方程 II

描述:求一元二次方程ax2+bx+c=0的解。a,b,c为任意实数。 输入:输入数据有一行,包括a b c的值 输出:按以下格式输出方程的根x1和x2。x1...

1203
来自专栏CVPy

利用 Python 优雅地可视化数据

最近看《机器学习系统设计》的前两章,学到了一些用Matplotlib进行数据可视化的方法。在这里整理一下。

8510
来自专栏软件开发 -- 分享 互助 成长

经典算法学习之回溯法

回溯法的应用范围:只要能把待求解的问题分成不太多的步骤,每个步骤又只有不太多的选择就可以考虑使用回溯法。  若用回溯法求问题的所有解时,要回溯到根,且根结点的所...

2328
来自专栏生信小驿站

Python数据处理从零开始----第四章(可视化)(7)(多图合并)目录正文

=========================================================

851
来自专栏ml

nyoj-----幸运三角形

幸运三角形 时间限制:1000 ms  |  内存限制:65535 KB 难度:3 描述         话说有这么一个图形,只有两种符号组成(‘+’或者‘-’...

30010
来自专栏C语言及其他语言

【每日一题】1445: [蓝桥杯][历届试题]最大子阵

节日快乐,筒子们! 不过小编还是给大家准备了每日一题! 2333 题目描述 给定一个n*m的矩阵A,求A中的一个非空子矩阵,使这个子矩阵中的元素和最大。 其...

3778
来自专栏数据结构与算法

1038 一元三次方程求解

1038 一元三次方程求解 2001年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver ...

2848

扫码关注云+社区

领取腾讯云代金券