解压缩霍夫曼和算术编码数据的快速方法

信息处理 图像压缩 视频压缩 动态范围压缩
2022-02-06 05:04:51

从本质上讲,当解压缩霍夫曼(我假设也是算术编码数据)时,我们必须逐位读取它,然后查看它如何遍历在每个叶节点处具有实际符号值的霍夫曼代码树。由于处理器是为字节或多字节读/写而设计的,这似乎是一个非常缓慢和低效的过程。

由于使用霍夫曼编码和许多其他方法来编码图像和视频数据会产生非字节边界对齐的结果,我们如何加快解压缩过程?我会假设我们不是一次读取 1 位,而是读取几个位甚至字节,然后使用一些聪明的方法,一次找到其中的所有符号。我认为这就是所有视频和图像编解码器如何快速解压缩压缩图像数据的方式。但是,这只是我的假设,我不知道任何细节。有人可以向我透露这个秘密吗?

2个回答

对于实际实现,请查看解码器的 (C) 编程代码。

基本上这个过程很简单,你创建一个抽象,比如

bits = get_bits(n)

其中,n是您要读取的 n 位。varbits左对齐。它从一些中提取它byte_buffer——比如 32 位或 64 位符号。

注意:所有实用的编解码器都将主要符号置于“字节对齐”位置,即使 > 内部符号可以逐位排列。

现在对于实现效率部分,基本上,不管哈夫曼代码会是什么(以及因此需要什么n)。

这就是实现简单 get_bits 的方式:

// At start
frame_buffer = 0x4444 
bits_delivered = 0 

n = 1 
mask = 0x8000
bits = (mask & frame_buffer) >> 32-n
mask = mask >> n 
bits_delivered += n
if(bits_delivered == 32) 
    { load_framebuffer( &frame_buffer) }  

(实际代码需要处理更多的边界条件)实际数据首先被提取到frame_bufferALU 内部的 32 位寄存器中(实际上是 16/32/64 位,具体取决于 CPU 的类型),然后剩下的处理是仅在 ALU 的寄存器内。

只有当你用尽 frame_buffer 时,你才会真正刷新那个位缓冲区并从内存中获取另一个整数。

这就是它获得有效实施的方式。希望这能回答你的问题。

你基本上自己描述了这个过程。说代码最多n位长,你想使用mn一次位:你建立一个表2m条目。每个条目将使用最右边存储从序列中可解码的第一个符号k位 (knm) 和数量k.

现在你读m来自流 ( cur) 的位,保持m准备好更多位(buf),查看表格,您知道第一个符号。cur现在你右移k位置,移动到最右边kbuf最左边的位kcur并重新开始。清空后buf,再读另一个m位。

m当然应该是 8 的倍数。问题是它可以合理地为 8 或 16。仅此而已,因为这样的表会非常稀疏和重复。如果您需要比现有更复杂的解决方案更多的东西,请按长度对代码进行聚类,并使用主表和多个扩展表。此外,如果多个条目适合于m位。