熵编码算法

野性酷女 2021-12-09 06:17 676阅读 0赞

## 一、熵编码概念 ##

信源的熵：

*  用于度量消息的平均信息量，和信息的不确定性；
 *  越是随机的、前后不相关的信息，其熵越高（信息越无序，我们表达它要付出的代价越高）；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjA0OTUwNg_size_16_color_FFFFFF_t_70]

*  信息的熵为信源无损编码后平均码长的下限（最短码长）
 *  公式理解：编码一个符号的最佳bit长度是-logP，P是这个符号出现的概率；一段信息的长度就是所有符号长度求期望。

熵编码的基本思想：

*  尽可能的减少信源的冗余，使前后的码字之间尽量更加随机，减少前后相关性，更加接近其信源的香农熵，用更少的比特传递更多的信源信息

熵编码具有消除数据之间统计冗余的功能，在编码端作为最后一道工序，将语法元素写入输出码流。  
熵解码作为解码过程的第一步，将码流解析出语法元素供后续步骤重建图像使用  
H.264针对不同的语法元素定义了不同的熵编码方法

常用熵编码算法：

*  变长编码：运算复杂度和编码效率都较低，常用方法：哈夫曼编码、香农-费诺编码等。用于计算资源比较吃紧，对压缩效率又比较高的场合；
 *  
 *  算术编码：运算较复杂，但编码效率更高。

## 哈夫曼编码原理 ##

哈夫曼编码是变长编码的一种，依赖于码字的概率来构造平均长度最短的编码方法；  
关键步骤：建立符合哈夫曼编码规则的二叉树，即哈夫曼树；

哈夫曼树：  
\*一种特殊的二叉树，叶结点个数等于码元数，且每个终端节点带有各自的权值；

*  加权路径长度，即根结点到叶结点的路径长度乘以权值的总和最小

注意：在保存编码过后，huffman编码的码表也要保存。不同的信源，每个符号的编号是不同的！  
没有码表就无法进行解码。

## 指数哥伦布编码 ##

H.264语法元素描述符  
![加粗样式][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjA0OTUwNg_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjA0OTUwNg_size_16_color_FFFFFF_t_70 2]

在H.264中定义了4类指数哥伦布编码：

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>ue(v)</td> 
   <td>无符号指数哥伦布编码</td> 
  </tr> 
  <tr> 
   <td>se(v)</td> 
   <td>有符号指数哥伦布编码</td> 
  </tr> 
  <tr> 
   <td>te(v)</td> 
   <td>截断指数哥伦布编码</td> 
  </tr> 
  <tr> 
   <td>me(v)</td> 
   <td>映射指数哥伦布编码</td> 
  </tr> 
 </tbody> 
</table>

其中ue(v)是其他变型算法的基础，其它算法的结果由ue(v)的结果进一步处理得到

0阶无符号哥伦布编码  
这里只讨论0阶，1阶，2阶等视频编码并没有实际应用

*  ue(v)的码字分为三部分：  
    \[prefix\] + 1 + \[surfix\]  
    即，前缀，1bit，后缀  
    \[prefix\]部分为连续的n个0，\[surfix\]部分表示实际数值的信息位，其长度与\[prefix\]一致。  
    \[prefix\]和\[surfix\]的长度由码元取值决定

<table> 
 <thead> 
  <tr> 
   <th>指数哥伦布编码模板</th> 
   <th>适用码元值</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>010</td> 
   <td>1~2</td> 
  </tr> 
  <tr> 
   <td>001xx</td> 
   <td>3~6</td> 
  </tr> 
  <tr> 
   <td>0001xxx</td> 
   <td>7~14</td> 
  </tr> 
  <tr> 
   <td>00001xxxx</td> 
   <td>15~30</td> 
  </tr> 
  <tr> 
   <td>000001xxxxx</td> 
   <td>31~62</td> 
  </tr> 
 </tbody> 
</table>

计算公式：  
 c o d e N u m = 2 L e a d i n g Z e r o B i t s − 1 + x x x codeNum = 2^\{LeadingZeroBits\}-1+xxx codeNum=2LeadingZeroBits−1\+xxx  
xxx表示后缀的部分由二进制换算成十进制的取值  
例子：  
如果前边一个0，后边x为0，2^1-1+0=1  
如果xxx是00011，2^5-1+3 = 34

有符号指数哥伦布编码se(v)

*  有符号指数哥伦布编码通过无符号指数哥伦布编码换算得到，换算关系为：  
     s e = ( − 1 ) k + 1 × C e i l ( k / 2 ) se=(-1)^\{k+1\}\\times Ceil(k/2) se=(−1)k\+1×Ceil(k/2)
 *  se和ue的相互关系可表示为下表：

<table> 
 <thead> 
  <tr> 
   <th>codeNum</th> 
   <th>syntax element value</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>0</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>-1</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>-2</td> 
  </tr> 
 </tbody> 
</table>

te(v)和me(v)

*  te(v)：截断指数哥伦布编码。解吗时首先判断语法元素的取值范围  
    \[o,x\],x>=1:
    
     *  若x>1，解析方法同ue(v)
     *  若x=1，语法元素值等同于下一位bit值的取反
 *  me(v)：映射指数哥伦布编码，适用于预测模式为Intra\_4*4，Intra\_8*8或Inter的宏块的coded\_block\_pattern
    
     *  无指定的换算公式，通常由查表的方式进行

指数哥伦布编码也是变长编码的一种。  
和哈夫曼编码的区别：

*  信源相关性不同：哈夫曼编码依赖与信源的概率分布；指数哥伦布编码与信源无关；
 *  额外信息不同：哈夫曼编码的数据必须额外携带与该信源匹配的码表；指数哥伦布编码无需携带任何额外信息；
 *  由于没有考虑到信源的实际特性，指数哥伦布编码端压缩率通常较低，甚至毫无压缩效果，比原始数据更大；而在不考虑码表的情况下，哈夫曼编码压缩效率更高

在实际中，指数哥伦布编码只作为少数的辅助语法元素的编码，以及大多数语法元素的二值化的方法，h264真正依赖的是cavlc和cabac

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjA0OTUwNg_size_16_color_FFFFFF_t_70]: /images/20211209/18abadbb73084c238c5aa52ff3861703.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjA0OTUwNg_size_16_color_FFFFFF_t_70 1]: /images/20211209/38c2e056a7684b029eba13f9a5dd1c53.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjA0OTUwNg_size_16_color_FFFFFF_t_70 2]: /images/20211209/4d8b92476f994a799f4370bb074234e9.png