用Huffman编码压缩图像

谨以此文梳理我在使用Huffman编码对图像进行无损压缩和解压的心得与收获,尽力写得深入浅出,对大家也有启发。本文将在4月19日更新完毕。

引言

在各种数字图像处理中,大数据量的图像信息会给存储器的存储容量,通信干线信道的带宽,以及计算机的处理速度增加极大的压力。单纯靠增加存储器容量,提高信道带宽以及计算机的处理速度等方法来解决这个问题是不现实的,这时就要考虑压缩.压缩的理论基础是信息论.从信息论的角度来看,压缩就是去掉信息中的冗余,即保留不确定的信息,去掉确定的信息(可推知的),也就是用一种更接近信息本质的描述来代替原有冗余的描述。

为什么能压缩

图像数据之所以能被压缩,就是因为数据中存在着冗余。图像数据的冗余主要表现为:图像中相邻像素间的相关性引起的空间冗余;图像序列中不同帧之间存在相关性引起的时间冗余;不同彩色平面或频谱带的相关性引起的频谱冗余。

如图为空间冗余,背景的彩色圆环、Tom和Jerry的头像、文字都是相同的颜色

如图为时间冗余,相邻帧的数据有许多共同的地方,如背景的钢琴

人类的视觉系统由于受生理特性的限制,对于图像场的注意是非均匀的,即,人对细微的颜色差异感觉不明显。例如,人类视觉的一般分辨能力为26灰度等级,而一般的图像的量化采用的是28灰度等级,存在视觉冗余。

压缩方法

图像压缩可以是有损数据压缩或无损数据压缩。

无损压缩:要求解压以后的数据和原始数据完全一致,是可逆过程。根据目前的水平,无损压缩一般可以把普通文件的数据压缩到原来的$\frac{1}{2}-\frac{1}{4}$。对于医疗图像、用于存档的扫描图像等,优先选择无损压缩方法。常用的无损压缩方法有:游程编码、熵编码法以及LZW这样的自适应字典算法。

有损压缩:解压以后的数据和原始数据不完全一致,是不可逆压缩方式。根据目前水平,有损压缩的压缩比一般为100:1.由于某些场景包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息,丢掉一些数据而不至于对声音或者图像所表达的意思产生误解,所以有损压缩非常适合于自然的图像。可以接受微小损失(有时是无法感知的)。常用的有损压缩方法有:色度抽样、变换编码等。

Huffman树及其应用

Huffman树

Huffman树,是一类带权路径长度最短的树,又称最优二叉树。

假设有n个权值,则构造出的哈夫曼树有n个叶子结点。n个权值为{$w_1, w_2, …, w_n$},则哈夫曼树的构造规则为:

  1. 将这n个权值$w_1, w_2, …, w_n$,构造成n棵仅有一个根结点的二叉树;
  2. 选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
  3. 删除选取的这两棵树;
  4. 重复第2、3步,直到只剩一棵树为止,该树即为所求得的哈夫曼树。

由上述步骤可得:对n个权值,构造哈夫曼树需要合并n-1次,形成的树结点总数为2n-1。

下图展示了Huffman树的构造过程,其中根节点上标注的数字是所赋的权。不难推知,该树的所有叶子节点到根节点的路径长度和节点权的乘积和最小。

Huffman树的构造过程,其中根节点上标注的数字是所赋的权值。图来自严蔚敏等著的《数据结构》

Huffman编码

如果我们要对下面的字符串使用Huffman编码。

$$“beep\quad boop\quad beer!”$$

首先,我们计算出每个字符出现的次数,得到下面这样一张表 :

字符 频数
‘b’ 3
‘e’ 4
‘p’ 2
‘ ’ 2
‘o’ 2
‘r’ 1
‘!’ 1

将这些字符按其出现频数排序(可以理解为优先级队列)。

频数统计的优先级队列

取权最小的两个字符构造二叉树,再排序。

Huffman树的构造示例

重复该步骤,得到以下结果。

第一遍重复的结果,将子树与p作为叶子节点,再排序

第二遍重复的结果,将'o'和' '作为叶子节点,再排序

第三遍重复的结果,将'b'和子树作为叶子节点,再排序

第四遍重复的结果,将子树和'e'作为叶子节点,再排序

现在就可以得到最终的Huffman树了。

最终得到的Huffman树

为了获得每个符号的编码值,我们只需要遍历这些树,直到我们到达那个符号。向左走时,编码的前缀添加0;向右走时,则添加1。

Huffman树的编码规则

于是,得到下面的编码表。

字符 编码
‘b’ 00
‘e’ 11
‘p’ 101
‘ ’ 011
‘o’ 010
‘r’ 1000
‘!’ 1001

不难发现,每个字符的编码不会成为其他编码的前几位,这样就很好地避免了译码时(同一个码对应不同的译码可能)的冲突。

如果对原字符串”beep boop beer!”进行普通编码,每个字符编为一个4bit的二进制码,总码长为90bit。而采用Huffman编码,总码为0011 1110 1011 0001 0010 1010 1100 1111 1000 1001,总码长为40bit。“90vs40”,Huffman编码的压缩效果很显著了。

用Huffman编码压缩和解压图像

算法流程

压缩步骤:

压缩流程图

1) 读取图像文件,每个像素包含RGB三个色彩通道,每个通道占1个字节,这是编码的单元。

2) 对读取到的每个像素的色彩通道数据进行权重统计。

3) 根据权重统计构建Huffman编码树。

4) 从Huffman编码树的根节点开始向根节点进行DFS,产生编码表。

5) 使用编码表对原来的每个通道的色彩通道数据进行编码。

6) 将编码输出到自定义的编码文件中。

解压步骤:

解压流程图

1) 读取自定义的编码文件,根据对编码文件结构的定义将各个部分分割出来。

2) 构造权重映射表,根据权重映射表重建Huffman编码树。

3) 读取实际编码数据,根据每个位的数据所指定的方向,从根节点开始向下游历编码树,每次到达叶子节点的时候输出叶子节点的对应数据,再重新回到根节点开始下一次游历,直到读取完编码数据。

4) 把得到的解码数据重新构建成图像格式,写入到图像文件中。

实验准备

框架构思

项目需要以下各类:

  • 编码文件辅助类(用于储存编码文件的相关信息)
  • Huffman编码数据单元辅助类(考虑到数据量大的时候,使用字符串来保存码字会由较大的内存开销,所以创建了这个类,采用了与最后存储到文件中一样的位数据集保存形式来保存编码数据单元,也就是在Huffman编码树上的路径)
  • Huffman编码操作类(算法核心)
  • 图像文件辅助类(用于储存图片文件的相关信息)
  • 图像IO异常类(对C++的运行时错误类的扩展,用于报出实际文件IO中详细的错误)
  • 图像IO辅助类(用于进行图像和压缩后文件的读写)

由上到下,分别为下图所示文件。

项目所需的类

项目环境

使用VMware® Workstation 15 Pro上创建的虚拟机Ubuntu64位(19.10)进行编写和测试,项目语言为C++。

文件要求

只针对bmp图像文件进行压缩。

压缩后的文件的扩展名为.hfmc ,压缩后文件结构为:

  • 原图像文件头(54字节)
  • 编码后图像数据总位数dataBitCount(4字节,即一个32为无符号整数)
  • 原图像文件中不同的数据单元的数目weightMapValCount(4字节,即一个32为无符号整数)
  • 权重映射表(表中每一项包含1个字节的原数据和4个字节即32位无符号整数表示的权重值,一共5个字节,表的总大小为weightMapValCount * 5)
  • 编码数据,实际的编码数据位数为dataBitCount,最后一个字节的数据如果是不满8位,余下的位用0作为padding

编程实现

压缩

void HuffmanCompression::getEncodedData(const unsigned char *rawDataPtr, uint32_t rawDataSize, unordered_map &dstWeightMap, unsigned char *&outputDataPtr, uint32_t &outputDataBitSize) {
    calcWeight(rawDataPtr, rawDataSize, dstWeightMap);  // 计算出权值映射表
    generateEncodedNodeQueue(dstWeightMap);  // 根据权值映射表构建编码树节点队列(使用priority_queue这样一个以堆实现的“队列”,可以保证每次进出队操作后队列的节点保持权值从小到大排列)
    buildTree();  // 建立编码树
    unordered_map resCodeMap;
    getCodeMap(resCodeMap);  // 根据编码树产生权值表
    outputDataBitSize = calcEncodedOutputSize(dstWeightMap, resCodeMap);  // 计算编码数据位数
    generateEncodedOutput(rawDataPtr, rawDataSize, resCodeMap, outputDataPtr, outputDataBitSize);  // 对原数据进行编码
}

解压:

void HuffmanCompression::getDecodedData(const unsigned char *rawDataPtr, uint32_t rawDataBitSize, const vector> &srcWeightMapArr, unsigned char *&outputDataPtr, uint32_t &outputDataSize) {
    generateDecodedNodeQueue(srcWeightMapArr);  // 根据读取文件之后构建的权值映射表构建节点队列
    buildTree();  // 建立编码树
    outputDataSize = calcDecodedOutputSize(srcWeightMapArr);  // 计算输出数据大小
    generateDecodedOutput(rawDataPtr, rawDataBitSize, outputDataPtr, outputDataSize);  // 对编码数据进行解码
}

建立Huffman树:

// 因为节点队列能够根据进出队列的节点的权值进行顺序调整,所以每次只需要从队首取出2个节点构造一棵树,将树根再次加进节点队列,直到队列只剩下一个节点,这个节点就是编码树的根节点
void HuffmanCompression::buildTree() {
    while (nodeQueue.size() > 1) {
        TreeNode* rightNode = nodeQueue.top();
        nodeQueue.pop();
        TreeNode* leftNode = nodeQueue.top();
        nodeQueue.pop();
        auto parentNode = new TreeNode(0, rightNode -> weight + leftNode -> weight);
        parentNode -> left = leftNode;
        parentNode -> right = rightNode;
        nodeQueue.push(parentNode);
    }
    treeRoot = nodeQueue.top();
}

生成编码表:

// 深度优先搜索,过程中使用path来记录路径,到达每个叶子节点的path就是叶子节点对应数据的编码
void HuffmanCompression::dfs(TreeNode* node, hfmCodeBitSet& path,
                             unordered_map &resCodeMap) {
    if (node -> left == nullptr && node -> right == nullptr) {
        resCodeMap[node -> val] = path;
        return;
    }
    path.append(0);
    dfs(node -> left, path, resCodeMap);
    path.pop_back();
    path.append(1);
    dfs(node -> right, path, resCodeMap);
    path.pop_back();
}

// 生成编码表:调用dfs来生成编码表
void HuffmanCompression::getCodeMap(unordered_map &resCodeMap) {
    if (treeRoot == nullptr)
        return;
    hfmCodeBitSet path;
    dfs(treeRoot, path, resCodeMap);
}

计算图像熵:

double Entropy(Mat img)
{

//开辟内存
double temp[256] = { 0.0 };

// 计算每个像素的累积值
for (int m = 0; m < img.rows; m++)
{// 有效访问行列的方式
    const uchar* t = img.ptr(m);
    for (int n = 0; n < img.cols; n++)
    {
        int i = t[n];
        temp[i] = temp[i] + 1;
    }
}

// 计算每个像素的概率
for (int i = 0; i < 256; i++)
{
    temp[i] = temp[i] / (img.rows*img.cols);
}

double result = 0;
// 计算图像信息熵
for (int i = 0; i < 256; i++)
{
    if (temp[i] == 0.0)
        result = result;
    else
        result = result - temp[i] * (log(temp[i]) / log(2.0));
}

return result;

}

结果分析

从压缩前后的图片质量来主观描述,压缩再解压的图像与原始图像无差异

原始图像和压缩后恢复图像的视觉对比

引入Shannon熵描述图像的平均信息量,假设各像素和各灰度是统计独立的,而且不考虑像素的几何位置,则有

$$H=-\sum_{i=1}^{n}p(x_i)log(x_i)$$

因为在计算机编码中,色彩表现为数字,那么色彩的丰富度就可以用概率来量化,如果每个像素值出现的概率都不为零,我们就有理由相信这是一张颜色艳丽的照片,而这个概率最终的量化结果,又恰恰就是信息熵所拟合的值。所以我们可以认为,“熵值大=色彩艳丽”。

以 24 位真彩图作为实验数据,计算图像信息熵和压缩比(压缩后的文件大小与原文件大小的比值),得到下表。

图像编号 信息熵 压缩比
A 7.5978 97.60%
B 7.5395 95.07%
C 7.3948 92.81%
D 6.1614 85.42%
E 4.9992 62.68%
F 2.8226 53.44%
G 0.3903 27.95%

由实验结果可以看出,Huffman编码的压缩比随着信息熵的增大而增大,满足一定的线性关系。这是因为信息熵越大,码字的出现频率就越低,而在Huffman编码中,出现频率越低,则Huffman编码就越长(在Huffman树的更深处叶子节点),越靠近普通编码的长度,于是压缩比越大。

当图片的色彩比较丰富,图像信息熵较大时,冗余度低,压缩比大,压缩效果差,如下图。

图像信息熵大时,压缩比大,该图例熵为7.5978,压缩比为97.60%

当图片的色彩比较单一,图像信息熵较小时,冗余度高,压缩比小,压缩效果好,如下图。

图像信息熵小时,压缩比小,该图例熵为4.9992,压缩比为62.68%


   转载规则


《用Huffman编码压缩图像》 帅张 采用 知识共享署名 4.0 国际许可协议 进行许可。
  目录