图像处理无损压缩-哈夫曼编码（可变字长符号编码）

淡淡的烟草味﹌ 2023-02-17 03:20 76阅读 0赞

### 文章目录 ###

*  有损压缩
 *   *  概念
     *  主要算法
 *  哈夫曼编码
 *   *  定义
     *  性质
     *  定长和变长编码比较
     *  示例
     *  生成哈夫曼编码

# 有损压缩 #

## 概念 ##

按照压缩方法是否丢失信息分为有损压缩和无损压缩，有损压缩解压缩后的数据与原始数据完全相同。 解压缩后获得的数据是原始数据的副本，是一种不可逆压缩。

## 主要算法 ##

消除编码冗余: 哈夫曼编码和算术编码。  
消除像素间冗余：LZW编码，位平面编码，行程编码和无损预测编码。

# 哈夫曼编码 #

## 定义 ##

哈夫曼编码，又称为霍夫曼编码，是一种字符编码。

在计算机数据压缩处理中，霍夫曼编码使用**变长编码表**()对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现几率的方法得到的，出现几率高的字母使用较短的编码，反之出现几率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

## 性质 ##

*  可变字长编码（VLC）
 *  源符号出现的频率越高，使用的代码字长越少。
 *  一致的编码方法（也称为“熵编码方法”），用于数据的无损压缩。

**信息熵**

英文entoropy,反映图像中的平均信息量。

## 定长和变长编码比较 ##

**定长编码**：fixed length coding (FLC)，如定长一字节或者定长二字节  
**变长编码**：virable length coding（VLC）

**示例**

<table> 
 <thead> 
  <tr> 
   <th>Symbol</th> 
   <th>Probability</th> 
   <th>FLC</th> 
   <th>VLC1</th> 
   <th>VLC2</th> 
   <th>VLC3</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>K</td> 
   <td>1/2</td> 
   <td>00</td> 
   <td>0</td> 
   <td>111</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>L</td> 
   <td>1/4</td> 
   <td>01</td> 
   <td>10</td> 
   <td>110</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>P</td> 
   <td>1/8</td> 
   <td>10</td> 
   <td>110</td> 
   <td>10</td> 
   <td>01</td> 
  </tr> 
  <tr> 
   <td>C</td> 
   <td>1/8</td> 
   <td>11</td> 
   <td>111</td> 
   <td>0</td> 
   <td>10</td> 
  </tr> 
 </tbody> 
</table>

对 KLKPLCKK 用上述四个方式编码

<table> 
 <thead> 
  <tr> 
   <th>方式</th> 
   <th>表示</th> 
   <th>编码长度length</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>FLC</td> 
   <td>00 01 00 10 11 00 00</td> 
   <td>2*8 =16 bits</td> 
  </tr> 
  <tr> 
   <td>VLC1</td> 
   <td>0 10 0 110 10 111 0 0</td> 
   <td>1+2+1+3+2+3+2 = 14 bits</td> 
  </tr> 
  <tr> 
   <td>VLC2</td> 
   <td>111 110 111 10 110 0 111 111</td> 
   <td>3+3+3+2+3+1+3+3 = 21 bits</td> 
  </tr> 
  <tr> 
   <td>VLC3</td> 
   <td>0 1 0 01 1 10 0 0</td> 
   <td>1+1+1+2+1+2+1+1 = 10 bits</td> 
  </tr> 
 </tbody> 
</table>

**总结** 根据最后编码长度，VLC3 的长度最短，符合出现概率高的字母使用较短的编码，因此是哈夫曼码。

**信息熵**：反映图像中的平均信息量,用H(entoropy)表示，小于等于Lavg(average length）

## 示例 ##

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

## 生成哈夫曼编码 ##

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tla2VfTWVtb3J5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200611225052950.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tla2VfTWVtb3J5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tla2VfTWVtb3J5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200611224734959.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tla2VfTWVtb3J5,size_16,color_FFFFFF,t_70