用哈夫曼树实现图像压缩

1、 用哈弗曼算法实现图像压缩 姓名：黄函 学号：2011221104210146 班级：11计科3班 算法设计课程论文 1.数字图像的冗余表现为以下几种形式：空间冗余、时间冗余、视 觉 冗余、信息熵冗余、结构冗余和知识冗余。(1)空间冗余：图像内部相邻像素之间存在较强的相关性所造成的冗余。 (2)时间冗余：视频图像序列中的不同帧之间的相关性所造成的冗余。(3)视觉冗余：是指人眼不能感知或不敏感的那部分图像信息。(4)信息熵冗余：也称编码冗余，如果图像中平均每个像素使用的比特数大于该图像的信息熵，则图像中存在冗余，这种冗余称为信息熵冗余。(5)结构冗余：是指图像中存在很强的纹理结构或自相似性。(6

2、)知识冗余：是指有些图像还包含与某些先验知识有关的信息。 2.无损压缩很常见的例子是磁盘文件的压缩。有损压缩的实例是图像和声音的压缩。 3.图像压缩的目的就是在给定位速或者压缩比下实现最好的图像质量。但是，还有一些其它的图像压缩机制的重要特性：可扩展编码 ：又称渐进编码、嵌入式位流，通常表示操作位流和文件产生的质量下降（没有解压缩和再压缩）。尽管具有不同的特性，在无损编码中也有可扩展编码，它通常是使用粗糙到精细像素扫描的格式。尤其是在下载时预览图像（如浏览器中）或者提供不同的图像质量访问时（如在数据库中）可扩展编码非常有用，有几种不同类型的可扩展性：质量渐进：又称层渐进，位流渐进更新重建的图像

3、。分辨率渐进：首先在低分辨率编码图像，然后编码与高分辨率之间的差别。成分渐进：首先编码灰度数据，然后编码彩色数据。感兴趣区域编码：图像某些部分的编码质量要高于其它部分，这种方法可以与可扩展编码组合在一起（首先编码这些部分，然后编码其它部分）。元数据信息：压缩数据可以包含关于图像的信息用来分类、查询或者浏览图像。这些信息可以包括颜色、纹理统计信息、小预览图像以及作者和版权信息。压缩方法的质量经常使用峰值信噪比来衡量，峰值信噪比用来表示图象有损压缩带来的噪声。但是，观察者的主观判断也认为是一个重要的、或许是最重要的衡量标准。 4.以哈弗曼算法为实例了解图像压缩算法Huffman码是一种变长码，其基

4、本思想是：先统计图像（已经数字化）中各灰度出现的概率，出现概率较大的赋以较短的码字，而出现概率较小的则赋以较长的码字。我们可以用下面的框图来表示Huffman编码的过程：在整个编码过程中，统计图像各灰度级出现的概率和编码这两步都很简单，关键的是Huffman树的构造。不但编码的时候需要用到这颗树，解码的时候也必须有这颗树才能完成解码工作，因此，Huffman树还得完整的传输到解码端。Huffman树的构造可以按照下面图2的流程图来完成。首先对统计出来的概率从小到大进行排序，然后将最小的两个概率相加；到这儿的时候，先把已经加过的两个概率作为树的两个节点，并把他们从概率队列中删除；然后把相加所得的

5、新概率加入到队列中，对这个新队列进行排序。如此反复，直到最后两个概率相加为1的时候停止。这样，Huffman树就建立起来了。5.哈夫曼图像压缩算法性能评价我们主要从三方面 2 来评价Huffman的性能：（1）压缩比的大小；（2）恢复效果的好坏，也就是能否尽可能的恢复原始数据；（3）算法的简单易用性以及编、解码的速度。 6.我设计的哈弗曼树达到以下要求：（1）软件设计支持灰度图像和彩色图像的压缩（2）图像文件格式为bmp或者gif（3）软件压缩率至少达到30%7.软件源代码：代码分为5个文件，compress.h , pg.h, compress.c , pg.c , main.c compr

6、ess.h/* * File: compress.h * Purpose: To compress file using the Haffman algorithm * Author: puresky * Date: 2011/05/01 */#ifndef _FILE_COMPRESSION_H#define _FILE_COMPRESSION_H/Haffuman Tree Nodetypedef struct HaffumanTreeNode HTN;struct HaffumanTreeNode char _ch; /character int _count; /frequency s

7、truct HaffumanTreeNode *_left; /left child struct HaffumanTreeNode *_right;/rigth child;/FileCompress Struct#define BITS_PER_CHAR 8 /the number of bits in a char#define MAX_CHARS 256 /the max number of chars#define FILE_BUF_SIZE 8192 /the size of Buffer for FILE I/Otypedef struct FileCompressStruct

8、FCS;struct FileCompressStruct HTN *_haffuman; /A pointer to the root of hafumman tree unsigned int _charsCount; /To store the number of chars unsigned int _total; /Total bytes in a file. char *_dictionaryMAX_CHARS; /to store the encoding of each character int _statisticMAX_CHARS; /To store the numbe

9、r of each character;FCS *fcs_new();void fcs_compress(FCS *fcs, const char *inFileName, const char *outFileName);void fcs_decompress(FCS *fcs, const char *inFileName, const char *outFileName);void fcs_free(FCS *fcs);#endifpg.h/*File: pq.h*purpose: declaration of priority queue in C*Author:puresky*Dat

10、e:2011/04/27*/#ifndef _PRIORITY_QUEUE_H#define _PRIORITY_QUEUE_H/ =KeyValue Struct=typedef struct key_value_struct KeyValue;struct key_value_struct int _key; void *_value;KeyValue *key_value_new(int key, void *value);void key_value_free(KeyValue *kv, void (*freevalue)(void *);/ =PriorityQueue Struct

11、=#define PRIORITY_MAX 1#define PRIORITY_MIN 2typedef struct priority_queue_struct PriorityQueue;struct priority_queue_struct KeyValue *_nodes; int _size; int _capacity; int _priority;PriorityQueue *priority_queue_new(int priority);void priority_queue_free(PriorityQueue *pq, void (*freevalue)(void *)

12、;const KeyValue *priority_queue_top(PriorityQueue *pq);KeyValue *priority_queue_dequeue(PriorityQueue *pq);void priority_queue_enqueue(PriorityQueue *pq, KeyValue *kv);int priority_queue_size(PriorityQueue *pq);int priority_queue_empty(PriorityQueue *pq);void priority_queue_print(PriorityQueue *pq);

13、#endifcompress.c#include <stdio.h>#include <string.h>#include <stdlib.h>#include "compress.h"#include "pq.h"static const unsigned char mask8 = 0x80, /* 10000000 */ 0x40, /* 01000000 */ 0x20, /* 00100000 */ 0x10, /* 00010000 */ 0x08, /* 00001000 */ 0x04, /* 00000

14、100 */ 0x02, /* 00000010 */ 0x01 /* 00000001 */ ;/static functions of HTNstatic HTN *htn_new(char ch, int count) HTN *htn = (HTN *)malloc(sizeof(HTN); htn->_left = NULL; htn->_right = NULL; htn->_ch = ch; htn->_count = count; return htn;static void htn_print_recursive(HTN *htn, int depth

15、) int i; if(htn) for(i = 0; i < depth; +i) printf(" "); printf("%d:%dn", htn->_ch, htn->_count); htn_print_recursive(htn->_left, depth + 1); htn_print_recursive(htn->_right, depth + 1); static void htn_print(HTN *htn) htn_print_recursive(htn, 0);static void htn_fre

16、e(HTN *htn) if(htn) htn_free(htn->_left); htn_free(htn->_right); free(htn); /static functions of FCSstatic void fcs_generate_statistic(FCS *fcs, const char *inFileName) int ret, i; unsigned char bufFILE_BUF_SIZE; FILE *pf = fopen(inFileName, "rb"); if(!pf) fprintf(stderr, "can&#

17、39;t open file:%sn", inFileName); return; while(ret = fread(buf, 1, FILE_BUF_SIZE, pf) > 0) fcs->_total += ret; for(i = 0; i < ret; +i) if(fcs->_statisticbufi = 0) fcs->_charsCount+; fcs->_statisticbufi+; fclose(pf);static void fcs_create_haffuman_tree(FCS *fcs) int i, count;

18、HTN *htn, *parent, *left, *right; KeyValue *kv, *kv1, *kv2; PriorityQueue *pq; pq = priority_queue_new(PRIORITY_MIN); for(i = 0; i < MAX_CHARS; +i) if(fcs->_statistici) htn = htn_new(char)i, fcs->_statistici); kv = key_value_new(fcs->_statistici, htn); priority_queue_enqueue(pq, kv); /fp

19、rintf(stdout, "the number of haffuman leaf is %dn", priority_queue_size(pq); while(!priority_queue_empty(pq) /fprintf(stdout, "priority queue size:%dn", priority_queue_size(pq); kv1 = priority_queue_dequeue(pq); kv2 = priority_queue_dequeue(pq); if(kv2 = NULL) fcs->_haffuman =

20、 kv1->_value; key_value_free(kv1, NULL); else left = (HTN *)kv1->_value; right = (HTN *)kv2->_value; count = left->_count + right->_count; key_value_free(kv1, NULL); key_value_free(kv2, NULL); parent = htn_new(0, count); parent->_left = left; parent->_right = right; kv = key_val

21、ue_new(count, parent); priority_queue_enqueue(pq, kv); priority_queue_free(pq, NULL); /htn_print(fcs->_haffuman);static void fcs_generate_dictionary_recursively(HTN *htn, char *dictionary, char path, int depth) char *code = NULL; if(htn) if(htn->_left = NULL && htn->_right = NULL) c

22、ode = (char *)malloc(sizeof(char) * (depth + 1); memset(code, 0, sizeof(char) * (depth + 1); memcpy(code, path, depth); dictionary(unsigned char)htn->_ch = code; if(htn->_left) pathdepth = '0' fcs_generate_dictionary_recursively(htn->_left, dictionary, path, depth + 1); if(htn->_

23、right) pathdepth = '1' fcs_generate_dictionary_recursively(htn->_right, dictionary, path, depth + 1); static void fcs_generate_dictionary(FCS *fcs) char path32; fcs_generate_dictionary_recursively(fcs->_haffuman, fcs->_dictionary, path, 0); /fcs_print_dictionary(fcs);static void fcs

24、_print_dictionary(FCS *fcs) int i; for(i = 0; i < MAX_CHARS; +i) if(fcs->_dictionaryi != NULL) fprintf(stdout, "%d:%sn", i, fcs->_dictionaryi);static void fcs_write_statistic(FCS *fcs, FILE *pf) int i; fprintf(pf, "%dn", fcs->_charsCount); for(i = 0; i < MAX_CHARS;

25、 +i) if(fcs->_statistici != 0) fprintf(pf, "%d %dn", i, fcs->_statistici); static void fcs_do_compress(FCS *fcs, const char *inFileName, const char* outFileName) int i, j, ret; char *dictEntry, len; unsigned int bytes; char bitBuf; int bitPos; unsigned char inBufFILE_BUF_SIZE; FILE *

26、pfIn, *pfOut; pfIn = fopen(inFileName, "rb"); if(!pfIn) fprintf(stderr, "can't open file:%sn", inFileName); return; pfOut = fopen(outFileName, "wb"); if(!pfOut) fclose(pfIn); fprintf(stderr, "can't open file:%sn", outFileName); return; fcs_write_statis

27、tic(fcs, pfOut); bitBuf = 0x00; bitPos = 0; bytes = 0; while(ret = fread(inBuf, 1, FILE_BUF_SIZE, pfIn) > 0) for(i = 0; i < ret; +i) len = strlen(fcs->_dictionaryinBufi); dictEntry = fcs->_dictionaryinBufi; /printf("%sn", dictEntry); for(j = 0; j < len; +j) if(dictEntryj = &

28、#39;1') bitBuf |= maskbitPos+; else bitPos+; if(bitPos = BITS_PER_CHAR) fwrite(&bitBuf, 1, sizeof(bitBuf), pfOut); bitBuf = 0x00; bitPos = 0; bytes+; if(bitPos != 0) fwrite(&bitBuf, 1, sizeof(bitBuf), pfOut); bytes+; fclose(pfIn); fclose(pfOut); printf("The compression ratio is:%f%n

29、", (fcs->_total - bytes) * 100.0 / fcs->_total);static void fcs_read_statistic(FCS *fcs, FILE *pf) int i, charsCount = 0; int ch; int num; fscanf(pf, "%dn", &charsCount); fcs->_charsCount = charsCount; for(i = 0; i < charsCount; +i) fscanf(pf, "%d %dn", &

30、ch, &num); fcs->_statistic(unsigned int)ch = num; fcs->_total += num; static void fcs_do_decompress(FCS *fcs, FILE *pfIn, const char *outFileName) int i, j, ret; unsigned char ch; HTN *htn; unsigned char bufFILE_BUF_SIZE; unsigned char bitCode; int bitPos; FILE *pfOut; pfOut = fopen(outFil

31、eName, "wb"); if(!pfOut) fprintf(stderr, "can't open file:%sn", outFileName); return; htn = fcs->_haffuman; bitCode = 0x00; bitPos = 0; while(ret = fread(buf, 1, FILE_BUF_SIZE, pfIn) > 0) for(i = 0; i < ret; +i) ch = bufi; for(j = 0; j < BITS_PER_CHAR; +j) if(ch &

32、amp; maskj) htn = htn->_right; else htn = htn->_left; if(htn->_left = NULL && htn->_right = NULL) /leaf if(fcs->_total > 0) fwrite(&htn->_ch, 1, sizeof(char), pfOut); fcs->_total-; htn = fcs->_haffuman; fclose(pfOut);/FCS functionsFCS *fcs_new() FCS *fcs = (FCS

33、 *)malloc(sizeof(FCS); fcs->_charsCount = 0; fcs->_total = 0; memset(fcs->_statistic, 0, sizeof(fcs->_statistic); memset(fcs->_dictionary, 0, sizeof(fcs->_dictionary); fcs->_haffuman = NULL; return fcs;void fcs_free(FCS *fcs) int i; if(fcs) if(fcs->_haffuman) htn_free(fcs->

34、;_haffuman); for(i = 0; i < MAX_CHARS; +i) free(fcs->_dictionaryi); free(fcs); void fcs_compress(FCS *fcs, const char *inFileName, const char *outFileName) fprintf(stdout, "To compress file: %s .n", inFileName); fcs_generate_statistic(fcs, inFileName); fcs_create_haffuman_tree(fcs);

35、fcs_generate_dictionary(fcs); fcs_do_compress(fcs, inFileName, outFileName); fprintf(stdout, "The compressed data of file: %s stored at %s!n", inFileName, outFileName);void fcs_decompress(FCS *fcs, const char *inFileName, const char *outFileName) FILE *pfIn; fprintf(stdout, "To decomp

36、ress file: %s .n", inFileName); pfIn= fopen(inFileName, "rb"); if(!pfIn) fprintf(stderr, "can't open file: %sn", inFileName); return ; fcs_read_statistic(fcs, pfIn); fcs_create_haffuman_tree(fcs); fcs_generate_dictionary(fcs); fcs_do_decompress(fcs, pfIn, outFileName); f

37、close(pfIn); fprintf(stdout, "The decompressed data of file: %s stored at %sn", inFileName, outFileName);pg.c/*File:pq.c*purpose: definition of priority queue in C*Author:puresky*Date:2011/04/27*/#include <stdio.h>#include <stdlib.h>#include <string.h>#include "pq.h&

38、quot;/Private Functionsstatic void priority_queue_realloc(PriorityQueue *pq);static void priority_queue_adjust_head(PriorityQueue *pq);static void priority_queue_adjust_tail(PriorityQueue *pq);static int priority_queue_compare(PriorityQueue *pq, int pos1, int pos2);static void priority_queue_swap(Ke

39、yValue *nodes, int pos1, int pos2);/Functions of KeyValue StructKeyValue *key_value_new(int key, void *value) KeyValue *pkv = (KeyValue *)malloc(sizeof(KeyValue); pkv->_key = key; pkv->_value = value; return pkv;void key_value_free(KeyValue *kv, void (*freevalue)(void *) if(kv) if(freevalue) f

40、reevalue(kv->_value); free(kv); /Functions of PriorityQueue StructPriorityQueue *priority_queue_new(int priority) PriorityQueue *pq = (PriorityQueue *)malloc(sizeof(PriorityQueue); pq->_capacity = 11; /default initial value pq->_size = 0; pq->_priority = priority; pq->_nodes = (KeyVal

41、ue *)malloc(sizeof(KeyValue *) * pq->_capacity); return pq;void priority_queue_free(PriorityQueue *pq, void (*freevalue)(void *) int i; if(pq) for(i = 0; i < pq->_size; +i) key_value_free(pq->_nodesi, freevalue); free(pq->_nodes); free(pq); const KeyValue *priority_queue_top(PriorityQ

42、ueue *pq) if(pq->_size > 0) return pq->_nodes0; return NULL;KeyValue *priority_queue_dequeue(PriorityQueue *pq) KeyValue *pkv = NULL; if(pq->_size > 0) pkv = pq->_nodes0; priority_queue_adjust_head(pq); return pkv;void priority_queue_enqueue(PriorityQueue *pq, KeyValue *kv) printf(

43、"add key:%dn", kv->_key); pq->_nodespq->_size = kv; priority_queue_adjust_tail(pq); if(pq->_size >= pq->_capacity) priority_queue_realloc(pq);int priority_queue_size(PriorityQueue *pq) return pq->_size;int priority_queue_empty(PriorityQueue *pq) return pq->_size <= 0;void priority_queue_print(PriorityQueue *pq) int i; KeyValue *kv; printf("data in the pq-