算术编码 | 学习笔记

简介: 快速学习算术编码,介绍了算术编码系统机制, 以及在实际应用过程中如何使用。

开发者学堂课程【高校精品课-华中科技大学 -智能媒体计算:算术编码】学习笔记,与课程紧密联系,让用户快速学习知识。

课程地址:https://developer.aliyun.com/learning/course/811/detail/15684


算术编码


内容介绍:

一、算数编码思想

二、算数编码过程举例

三、算术编码需要注意的几个问题


一、算数编码思想

1. 算术编码在图像数据压缩标准(如 JPEG)中扮演了重要的角色

在图像压缩中只用一个实数表示,用0和1中的一个小数表示信源的符号,例如颜色值或者声音的样本。

其可以大幅度的压缩数据量,所以使用算数编码的压缩比很高

2.在算术编码中,消息用0到1之间的实数进行编码,算术编码用到两个基本的参数

(1)符号概率

(2)编码间隔

3.注意

编码的间隔取决于符号概率。


二、算数编码过程举例

例1:

假设信源符号为{00,01,10,11},这些符号的概率分别为{0.1,0.4,0.2,0.3 }

根据这些概率可把间隔[0,1)分成4个子间隔:

[0,0.1)∶间隔为0.1

[0.1,0.5)∶间隔为0.4

[0.5,0.7)∶间隔为0.2

[0.7,1):间隔为0.3

区间的间隔是概率值,可以用两个二进制表示,算数编码是用编码间隔去找到0到1之间的数。

先按照间隔将其分为4份,信源符号、概率和初始编码间隔的表格如下:

符号

概率

初始编码

00

0.1

[0,0.1)

01

0.4

[0.1,0.5)

10

0.2

[0.5,0.7)

11

0.3

[0.7,1)

间隔图如下:

image.png

第一个符号为10

[0.5,0.7)是10,将[0.5,0.7)作为一个整体,将该区间进行分割,等比例的划分成4个区间,计算时可以将其分为10份。0.5到0.7的间隔是0.2,除以10为0.02,前面第一个编码空间占1份,也就是0.5到0.52,依此类推,可以把这4个区间开始和结束的值计算出来.

第二个符号为00

00位于该区间的第一段,区间为0.5到0.52,可以再将该区间等比例划分为4个。

第三个符号为11

区间为0.514到0.52,继续输入符号00,然后等比例分割,区间为0.5146到0.514。继续输入符号10,是从下面开始数的第三个子区间,然后等比例放大,区间为0.51442到0.5143.下一个为11,继续等比例分割,区间就为0.514384到0.51442。下一个符号为01,继续等比例分割,区间为0.5143876到0.514402.

假设将所有数编完了,输出的数,就是把该空间的上下两个数选择一个,通常选下面的这个为0.5143876作为前面编码的算数编码。

如下图:

image.png

也就是输入10 00 11 00 10 11 01用小数0.5143876表示。

如果还要输入,则继续按照前面的分割,结果是越后编码的数量越多,小数点后的位数越长。在 不影响区间的情况下可以适当的进行四舍五入,但是不能改变区间。

算数解码过程如下表格:

步骤

间隔

译码符号

译码判决

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

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

8

译码的消息:10 00 11 00 10 11 01

所以译码的过程是编码的过程反过来。


三、算术编码需要注意的几个问题

1. 由于实际的计算机精度不可能无限长,运算中会出现溢出问题

(1)多数机器都有16位、32位或者64位的精度

(2)可使用比例缩放方法解决

(目前多数计算机都有16位、32位,普遍都是64位,所以很大程度上避免了溢出出现的概率,但是将8k的图像整个的用算数编码编是不可能的,算数编码是把一幅图像划分一小块一小块的,例如8*8,现在变成了4*4的,甚至还有2*2的小块,2*2也就是4个像素,8*8也就是64个像素,随着小块的数量是有限的,溢出的问题会得到很好的解决)

还可以通过比例的缩放来解决溢出的问题,但是溢出本身从算数编码的方法来说是存在的。

2.算术编码器对整个消息只产生一个码字(在间隔[O,1)中的一个实数),因此译码器在接收到表示这个实数的所有位之前不能进行译码

(1)一种对错误很敏感的编码方法(这时需要加一些错误保护)

(2)如果有一位发生错误就会导致整个消息译错

相关文章
|
安全 网络安全 PHP
网络安全-RCE(远程命令执行)漏洞原理、攻击与防御
网络安全-RCE(远程命令执行)漏洞原理、攻击与防御
2061 0
网络安全-RCE(远程命令执行)漏洞原理、攻击与防御
|
资源调度 算法 计算机视觉
数字图像处理实验(六)|图像分割{阈值分割、直方图法、OTUS最大类间方差法(edge、im2dw、imfilter、imresize)、迭代阈值法、点检测}(附matlab实验代码和截图)
数字图像处理实验(六)|图像分割{阈值分割、直方图法、OTUS最大类间方差法(edge、im2dw、imfilter、imresize)、迭代阈值法、点检测}(附matlab实验代码和截图)
2491 0
数字图像处理实验(六)|图像分割{阈值分割、直方图法、OTUS最大类间方差法(edge、im2dw、imfilter、imresize)、迭代阈值法、点检测}(附matlab实验代码和截图)
|
存储 机器学习/深度学习 缓存
vLLM 核心技术 PagedAttention 原理详解
本文系统梳理了 vLLM 核心技术 PagedAttention 的设计理念与实现机制。文章从 KV Cache 在推理中的关键作用与内存管理挑战切入,介绍了 vLLM 在请求调度、分布式执行及 GPU kernel 优化等方面的核心改进。PagedAttention 通过分页机制与动态映射,有效提升了显存利用率,使 vLLM 在保持低延迟的同时显著提升了吞吐能力。
10341 22
vLLM 核心技术 PagedAttention 原理详解
|
安全 Java API
Java SE 与 Java EE 区别解析及应用场景对比
在Java编程世界中,Java SE(Java Standard Edition)和Java EE(Java Enterprise Edition)是两个重要的平台版本,它们各自有着独特的定位和应用场景。理解它们之间的差异,对于开发者选择合适的技术栈进行项目开发至关重要。
1880 1
|
搜索推荐
大模型训练常见通信源语解释
本文总结了在大模型分布式训练中常用的通信原语,包括一对多操作(Broadcast、Scatter)、多对一操作(Gather、Reduce)以及多对多操作(AllGather、AllReduce、ReduceScatter、All-To-All)。这些操作在模型并行和数据并行场景中起到关键作用,如参数初始化、数据切分与汇聚、规约运算等。通过详细介绍每种通信方式的功能与应用场景,帮助理解分布式训练中的数据交互机制。
2192 2
|
编解码 Linux API
【Camera基础(一)】Camera摄像头工作原理及整机架构
【Camera基础(一)】Camera摄像头工作原理及整机架构
|
IDE 开发工具 Android开发
eclipse自动补全及其空格键优化(去除空格自动补全)
本文介绍了如何在Eclipse IDE中配置自动补全功能,并提供了去除空格键自动补全代码的技巧。
eclipse自动补全及其空格键优化(去除空格自动补全)
|
机器学习/深度学习 存储 人工智能
【AI系统】谷歌 TPU v2 训练芯片
2017年,谷歌推出TPU v2,专为神经网络训练设计,标志着从推理转向训练的重大转变。TPU v2引入多项创新,包括Vector Memory、Vector Unit、MXU及HBM内存,以应对训练中数据并行、计算复杂度高等挑战。其高效互联技术构建了TPU v2超级计算机,显著提升大规模模型训练的效率和性能。
902 0
|
存储 安全 物联网
物联网(IoT)安全:挑战与解决方案
【8月更文挑战第5天】物联网(IoT)深刻改变着我们的生活,但随之而来的安全挑战不容忽视。面对设备身份验证复杂、数据隐私泄露、软件漏洞及资源受限等问题,本文提出加强身份验证、加密保护、定期更新、安全开发生命周期、多层次防御、安全培训及标准化合作等解决方案,旨在构建一个更加安全可靠的物联网环境。
1625 2