基于C语言的图像压缩算法

康高铭

摘要：该文借鉴静态图像压缩标准JPEG的理论研究成果，将其与DCT快速变换相结合，采用霍夫曼编码方法，用C语言编程实现灰度图像的压缩。最后，计算了基于DCT快速变换的图像压缩算法的压缩比。同时，分析了DCT快速变换后的数据，验证了该算法用于图像压缩的合理性。

关键词：DCT快速变换；霍夫曼编码；图像压缩

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）34-8264-02

随着多媒体技术的发展，人们获取信息由传统方式的模拟图像向数字图像转变。图像以数字形式便于计算机存储、处理和传输，具有质量好、成本低和可靠性高等特点。但是数字图像的数据量非常巨大，这对硬盘等存储设备提出了较高地要求，也对现有网络的传输带宽提出了非常高地需求。图像压缩是在满足一定保真度的前提下，对原始较大的数字图像进行变换、编码，去除冗余数据，从而使用较少的数据表示和传输，达到节省传输带宽或节省所需存储容量的目的。因此，图像压缩技术在多媒体领域得到广泛地应用。

1 二维DCT快速变换

通常对于一幅图像的处理是将图像分成一个一个的小块，然后再将每一个小块进行正交变换，从而为某一种信息处理做准备。该文将图像进行8×8分块，则其DCT变换公式为：

由于余弦函数具有周期性，因此系数矩阵A中的每个元素取值除了[12]外，范围均在[cosnπ16，n=1，…，15]，共16种情况。同理可知，AT中的每个元素取值范围与A相同，也为16种情况。而由公式（2） 求得的系数取值情况即为：[16×16=256]种。定义一个数组存储这256个系数，可减少DCT算法中乘法的次数为：[（64+8）×64=4608]次，大大简化计算，易于硬件实现。

2 霍夫曼编码的实现

首先要计算各符号出现的概率。这样就需要有一个扫描的过程。首先建立一个长为[256×256]的数组，并对文件中从开始到结束每个字符的出现次数进行计数统计，当读到结束标志时，完成计数。

计数开始时文件的输入指针位置得到保存，并在完成时再恢复。经过这个步骤，得到了输入数据中每个符号出现的概率，即叶结点的权值。

调整完各符号的概率后，接下来建立霍夫曼（Huffman）树。在建立树的过程中，需要在一个循环中将两个权值最低的自由结点连同这两结点的权值之和组合成一个新的内部结点。在实际实现过程中，首先搜索权值最低的两个结点，把它们的权相加，得到的和作为新结点的权值，然后在剩下的结点和新生成的结点中进行搜索，合并权值最小的两个结点，依次类推，一旦只剩下一个自由结点，Huffman树就完成了，而这个自由结点就是Huffman的树根。

压缩一个文件，从根本上讲，是想顺着树从上向下工作，然后在每个结点处输出一个0位或1位，直至达到适当的叶结点为止。但是，树的结构不允许这么做。当从树根开始时，无法确定是从0树枝还是1树枝抵达某一特殊的符号。解决这个问题的方法之一是在建立树时在结点的结构中增加一个父成员。当组合两个最小的结点形成一个新的内部结点时，每个最小的结点都让其父结构设置成指向新的结点通过这个新结点，可以从叶结点开始，顺着树向上延伸，直到树根。当对一个文件进行压缩时，只需要通过递归地遍历整个树一次就可能建立一个代码表，而不必试着用树来对符号进行编码。这样便建立了一个代码表，其中包含每个符号的代码和每个代码的长度。一旦这张表建立起来，便可通过简单地输入输出文件中每个字符的适当代码来对这个文件编码。

3 仿真验证

采用C语言编程，该文对三幅灰度图像进行了基于DCT快速变换的压缩，样品图像及其解压后的图像分别如图1～3所示。

三幅图像的具体数据分析如表1～2所示，给出了三幅图像的压缩比和峰值信噪比。

4 结论

本文借鉴静态图像压缩标准JPEG的研究成果，使用C语言编程实现了灰度图像的压缩。为了提高运算速度，该文提出了一种DCT快速变换，此算法依据二维DCT变换矩阵形式中系数矩阵每个元素的周期性，将系数矩阵相乘结果的任意情况存储，减少乘法操作。同时，采用C语言编写代码实现了基于DCT快速算法的灰度图像压缩。该文通过对一系列的实验结果进行分析，验证了DCT快速变换用于灰度图像压缩的合理性。

参考文献：

[1] 张春田.苏育挺.数字图像压缩编码[M].北京：清华大学出版社，2006：1-10.

[2] 马平.数字图像处理[M]. 北京：电子工业出版社，2007：164-167.

[3] 小野定康.JPEG/MPEG2技术[M].北京：科学出版社，2004：62-65.

[4] 张旭东.卢国栋.图像编码基础和小波压缩技术[M].北京：清华大学出版社，2004：115-137.

[5] 丁贵广.Visual C++ 6.0数字图像编码[M].北京：机械工业出版社，2004：53-82.

[6] Gilge M，Engelhardt T，Mehlan R. Coding of arbitrarily shaped image segments based on a generalized orthogonal transform[J].Signal Processing on Image Commun， 2002，10：153-180.

[7]T Sikora，Makai B. Shape-adaptive DCT for generic coding of video[J].IEEE Transactions on Circuits System and Video Technol，1995，1：59-62.

[8] 曹雪虹.信息论与编码[M].北京：清华大学出版社，2004：16-34.

[9] 阴躲芬.浅谈数字图像压缩编码技术[J].科技广场学报，2008（1）：138-139.endprint

摘要：该文借鉴静态图像压缩标准JPEG的理论研究成果，将其与DCT快速变换相结合，采用霍夫曼编码方法，用C语言编程实现灰度图像的压缩。最后，计算了基于DCT快速变换的图像压缩算法的压缩比。同时，分析了DCT快速变换后的数据，验证了该算法用于图像压缩的合理性。

关键词：DCT快速变换；霍夫曼编码；图像压缩

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）34-8264-02

随着多媒体技术的发展，人们获取信息由传统方式的模拟图像向数字图像转变。图像以数字形式便于计算机存储、处理和传输，具有质量好、成本低和可靠性高等特点。但是数字图像的数据量非常巨大，这对硬盘等存储设备提出了较高地要求，也对现有网络的传输带宽提出了非常高地需求。图像压缩是在满足一定保真度的前提下，对原始较大的数字图像进行变换、编码，去除冗余数据，从而使用较少的数据表示和传输，达到节省传输带宽或节省所需存储容量的目的。因此，图像压缩技术在多媒体领域得到广泛地应用。

1 二维DCT快速变换

通常对于一幅图像的处理是将图像分成一个一个的小块，然后再将每一个小块进行正交变换，从而为某一种信息处理做准备。该文将图像进行8×8分块，则其DCT变换公式为：

由于余弦函数具有周期性，因此系数矩阵A中的每个元素取值除了[12]外，范围均在[cosnπ16，n=1，…，15]，共16种情况。同理可知，AT中的每个元素取值范围与A相同，也为16种情况。而由公式（2） 求得的系数取值情况即为：[16×16=256]种。定义一个数组存储这256个系数，可减少DCT算法中乘法的次数为：[（64+8）×64=4608]次，大大简化计算，易于硬件实现。

2 霍夫曼编码的实现

首先要计算各符号出现的概率。这样就需要有一个扫描的过程。首先建立一个长为[256×256]的数组，并对文件中从开始到结束每个字符的出现次数进行计数统计，当读到结束标志时，完成计数。

计数开始时文件的输入指针位置得到保存，并在完成时再恢复。经过这个步骤，得到了输入数据中每个符号出现的概率，即叶结点的权值。

调整完各符号的概率后，接下来建立霍夫曼（Huffman）树。在建立树的过程中，需要在一个循环中将两个权值最低的自由结点连同这两结点的权值之和组合成一个新的内部结点。在实际实现过程中，首先搜索权值最低的两个结点，把它们的权相加，得到的和作为新结点的权值，然后在剩下的结点和新生成的结点中进行搜索，合并权值最小的两个结点，依次类推，一旦只剩下一个自由结点，Huffman树就完成了，而这个自由结点就是Huffman的树根。

压缩一个文件，从根本上讲，是想顺着树从上向下工作，然后在每个结点处输出一个0位或1位，直至达到适当的叶结点为止。但是，树的结构不允许这么做。当从树根开始时，无法确定是从0树枝还是1树枝抵达某一特殊的符号。解决这个问题的方法之一是在建立树时在结点的结构中增加一个父成员。当组合两个最小的结点形成一个新的内部结点时，每个最小的结点都让其父结构设置成指向新的结点通过这个新结点，可以从叶结点开始，顺着树向上延伸，直到树根。当对一个文件进行压缩时，只需要通过递归地遍历整个树一次就可能建立一个代码表，而不必试着用树来对符号进行编码。这样便建立了一个代码表，其中包含每个符号的代码和每个代码的长度。一旦这张表建立起来，便可通过简单地输入输出文件中每个字符的适当代码来对这个文件编码。

3 仿真验证

采用C语言编程，该文对三幅灰度图像进行了基于DCT快速变换的压缩，样品图像及其解压后的图像分别如图1～3所示。

三幅图像的具体数据分析如表1～2所示，给出了三幅图像的压缩比和峰值信噪比。

4 结论

本文借鉴静态图像压缩标准JPEG的研究成果，使用C语言编程实现了灰度图像的压缩。为了提高运算速度，该文提出了一种DCT快速变换，此算法依据二维DCT变换矩阵形式中系数矩阵每个元素的周期性，将系数矩阵相乘结果的任意情况存储，减少乘法操作。同时，采用C语言编写代码实现了基于DCT快速算法的灰度图像压缩。该文通过对一系列的实验结果进行分析，验证了DCT快速变换用于灰度图像压缩的合理性。

参考文献：

[1] 张春田.苏育挺.数字图像压缩编码[M].北京：清华大学出版社，2006：1-10.

[2] 马平.数字图像处理[M]. 北京：电子工业出版社，2007：164-167.

[3] 小野定康.JPEG/MPEG2技术[M].北京：科学出版社，2004：62-65.

[4] 张旭东.卢国栋.图像编码基础和小波压缩技术[M].北京：清华大学出版社，2004：115-137.

[5] 丁贵广.Visual C++ 6.0数字图像编码[M].北京：机械工业出版社，2004：53-82.

[6] Gilge M，Engelhardt T，Mehlan R. Coding of arbitrarily shaped image segments based on a generalized orthogonal transform[J].Signal Processing on Image Commun， 2002，10：153-180.

[7]T Sikora，Makai B. Shape-adaptive DCT for generic coding of video[J].IEEE Transactions on Circuits System and Video Technol，1995，1：59-62.

[8] 曹雪虹.信息论与编码[M].北京：清华大学出版社，2004：16-34.

[9] 阴躲芬.浅谈数字图像压缩编码技术[J].科技广场学报，2008（1）：138-139.endprint

摘要：该文借鉴静态图像压缩标准JPEG的理论研究成果，将其与DCT快速变换相结合，采用霍夫曼编码方法，用C语言编程实现灰度图像的压缩。最后，计算了基于DCT快速变换的图像压缩算法的压缩比。同时，分析了DCT快速变换后的数据，验证了该算法用于图像压缩的合理性。

关键词：DCT快速变换；霍夫曼编码；图像压缩

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）34-8264-02

随着多媒体技术的发展，人们获取信息由传统方式的模拟图像向数字图像转变。图像以数字形式便于计算机存储、处理和传输，具有质量好、成本低和可靠性高等特点。但是数字图像的数据量非常巨大，这对硬盘等存储设备提出了较高地要求，也对现有网络的传输带宽提出了非常高地需求。图像压缩是在满足一定保真度的前提下，对原始较大的数字图像进行变换、编码，去除冗余数据，从而使用较少的数据表示和传输，达到节省传输带宽或节省所需存储容量的目的。因此，图像压缩技术在多媒体领域得到广泛地应用。

1 二维DCT快速变换

通常对于一幅图像的处理是将图像分成一个一个的小块，然后再将每一个小块进行正交变换，从而为某一种信息处理做准备。该文将图像进行8×8分块，则其DCT变换公式为：

由于余弦函数具有周期性，因此系数矩阵A中的每个元素取值除了[12]外，范围均在[cosnπ16，n=1，…，15]，共16种情况。同理可知，AT中的每个元素取值范围与A相同，也为16种情况。而由公式（2） 求得的系数取值情况即为：[16×16=256]种。定义一个数组存储这256个系数，可减少DCT算法中乘法的次数为：[（64+8）×64=4608]次，大大简化计算，易于硬件实现。

2 霍夫曼编码的实现

首先要计算各符号出现的概率。这样就需要有一个扫描的过程。首先建立一个长为[256×256]的数组，并对文件中从开始到结束每个字符的出现次数进行计数统计，当读到结束标志时，完成计数。

计数开始时文件的输入指针位置得到保存，并在完成时再恢复。经过这个步骤，得到了输入数据中每个符号出现的概率，即叶结点的权值。

调整完各符号的概率后，接下来建立霍夫曼（Huffman）树。在建立树的过程中，需要在一个循环中将两个权值最低的自由结点连同这两结点的权值之和组合成一个新的内部结点。在实际实现过程中，首先搜索权值最低的两个结点，把它们的权相加，得到的和作为新结点的权值，然后在剩下的结点和新生成的结点中进行搜索，合并权值最小的两个结点，依次类推，一旦只剩下一个自由结点，Huffman树就完成了，而这个自由结点就是Huffman的树根。

压缩一个文件，从根本上讲，是想顺着树从上向下工作，然后在每个结点处输出一个0位或1位，直至达到适当的叶结点为止。但是，树的结构不允许这么做。当从树根开始时，无法确定是从0树枝还是1树枝抵达某一特殊的符号。解决这个问题的方法之一是在建立树时在结点的结构中增加一个父成员。当组合两个最小的结点形成一个新的内部结点时，每个最小的结点都让其父结构设置成指向新的结点通过这个新结点，可以从叶结点开始，顺着树向上延伸，直到树根。当对一个文件进行压缩时，只需要通过递归地遍历整个树一次就可能建立一个代码表，而不必试着用树来对符号进行编码。这样便建立了一个代码表，其中包含每个符号的代码和每个代码的长度。一旦这张表建立起来，便可通过简单地输入输出文件中每个字符的适当代码来对这个文件编码。

3 仿真验证

采用C语言编程，该文对三幅灰度图像进行了基于DCT快速变换的压缩，样品图像及其解压后的图像分别如图1～3所示。

三幅图像的具体数据分析如表1～2所示，给出了三幅图像的压缩比和峰值信噪比。

4 结论

本文借鉴静态图像压缩标准JPEG的研究成果，使用C语言编程实现了灰度图像的压缩。为了提高运算速度，该文提出了一种DCT快速变换，此算法依据二维DCT变换矩阵形式中系数矩阵每个元素的周期性，将系数矩阵相乘结果的任意情况存储，减少乘法操作。同时，采用C语言编写代码实现了基于DCT快速算法的灰度图像压缩。该文通过对一系列的实验结果进行分析，验证了DCT快速变换用于灰度图像压缩的合理性。

参考文献：

[1] 张春田.苏育挺.数字图像压缩编码[M].北京：清华大学出版社，2006：1-10.

[2] 马平.数字图像处理[M]. 北京：电子工业出版社，2007：164-167.

[3] 小野定康.JPEG/MPEG2技术[M].北京：科学出版社，2004：62-65.

[4] 张旭东.卢国栋.图像编码基础和小波压缩技术[M].北京：清华大学出版社，2004：115-137.

[5] 丁贵广.Visual C++ 6.0数字图像编码[M].北京：机械工业出版社，2004：53-82.

[6] Gilge M，Engelhardt T，Mehlan R. Coding of arbitrarily shaped image segments based on a generalized orthogonal transform[J].Signal Processing on Image Commun， 2002，10：153-180.

[7]T Sikora，Makai B. Shape-adaptive DCT for generic coding of video[J].IEEE Transactions on Circuits System and Video Technol，1995，1：59-62.

[8] 曹雪虹.信息论与编码[M].北京：清华大学出版社，2004：16-34.

[9] 阴躲芬.浅谈数字图像压缩编码技术[J].科技广场学报，2008（1）：138-139.endprint