# 使用霍夫曼编码进行图像压缩原理和实现细节

``prob_pixel = numpix/totalnum``

1. 将两个概率最低的叶子节点合并为一个新节点。
2. 用新节点替换两个叶节点, 并根据新的概率值对节点进行排序。
3. 继续步骤(a)和(b), 直到获得概率值为1.0的单个节点。我们称这个节点为根

``````int i, j;
char filename[] = "Input_Image.bmp" ;
int data = 0, offset, bpp = 0, width, height;
long bmpsize = 0, bmpdataoff = 0;
int ** image;
int temp = 0;

//Reading the BMP File
FILE * image_file;
image_file = fopen (filename, "rb" );
if (image_file == NULL)
{
printf ( "Error Opening File!!" );
exit (1);
}
else
{

//Set file position of the
//stream to the beginning
//Contains file signature
//or ID "BM"
offset = 0;

//Set offset to 2, which
//contains size of BMP File
offset = 2;

fseek (image_file, offset, SEEK_SET);

//Getting size of BMP File
fread (&bmpsize, 4, 1, image_file);

//Getting offset where the
//pixel array starts
//Since the information
//is at offset 10 from
//the start, as given
offset = 10;

fseek (image_file, offset, SEEK_SET);

//Bitmap data offset
fread (&bmpdataoff, 4, 1, image_file);

//Getting height and width of the image
//Width is stored at offset 18 and height
//at offset 22, each of 4 bytes
fseek (image_file, 18, SEEK_SET);

fread (&width, 4, 1, image_file);

fread (&height, 4, 1, image_file);

//Number of bits per pixel
fseek (image_file, 2, SEEK_CUR);

fread (&bpp, 2, 1, image_file);

//Setting offset to start of pixel data
fseek (image_file, bmpdataoff, SEEK_SET);

//Creating Image array
image = ( int **) malloc (height * sizeof ( int *));
for (i = 0; i <height; i++)
{
image[i] = ( int *) malloc (width * sizeof ( int ));
}

//int image[height][width]
//can also be done
//Number of bytes in the
//Image pixel array
int numbytes = (bmpsize - bmpdataoff) /3;

//Reading the BMP File
//into Image Array
for (i = 0; i <height; i++)
{
for (j = 0; j <width; j++)
{
fread (&temp, 3, 1, image_file);

//the Image is a
//24-bit BMP Image
temp = temp & 0x0000FF;
image[i][j] = temp;
}
}
}``````

``````//Creating the Histogram
int hist[256];

for (i = 0; i <256; i++)
hist[i] = 0;

for (i = 0; i <height; i++)
for (j = 0; j <width; j++)
hist[image[i][j]] += 1;``````

``````//Finding number of
//non-zero occurrences
int nodes = 0;
for (i = 0; i <256; i++)
{
if (hist[i] != 0)
nodes += 1;
}``````

, 存在一个源, 其最小概率为p, 并且具有霍夫曼码, 其最长单词的长度为K。

, 存在这样一种来源, 对于该来源, 每个最佳代码都具有长度为K的最长字。

``````Gallager [1] noted that every Huffman tree is efficient, but in fact it is easy to see more
generally that every optimal tree is efficient``````

``1/p = 64``
``````For K = 9, F(K+2) = F(11) = 55
F(K+3) = F(12) = 89``````

``````1/F(K+3) <p <1/F(K+2)
Hence optimal length of code is K=9``````
``````//Calculating max length
//of Huffman code word
i = 0;
while ((1 /p) <fib(i))
i++;
int maxcodelen = i - 3;``````
``````//Function for getting Fibonacci
//numbers defined outside main
int fib( int n)
{
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}``````

``````//Defining Structures pixfreq
struct pixfreq
{
int pix;
float freq;
struct pixfreq *left, *right;
char code[maxcodelen];
};``````

``````//Defining Structures huffcode
struct huffcode
{
int pix, arrloc;
float freq;
};``````

``````//Declaring structs
struct pixfreq* pix_freq;
struct huffcode* huffcodes;``````

``````int totalnodes = 2 * nodes - 1;
pix_freq = ( struct pixfreq*) malloc ( sizeof ( struct pixfreq) * totalnodes);
huffcodes = ( struct huffcode*) malloc ( sizeof ( struct huffcode) * nodes);``````

``````j = 0;
int totpix = height * width;
float tempprob;
for (i = 0; i <256; i++)
{
if (hist[i] != 0)
{

//pixel intensity value
huffcodes[j].pix = i;
pix_freq[j].pix = i;

//location of the node
//in the pix_freq array
huffcodes[j].arrloc = j;

//probability of occurrence
tempprob = ( float )hist[i] /( float )totpix;
pix_freq[j].freq = tempprob;
huffcodes[j].freq = tempprob;

//Declaring the child of
//leaf node as NULL pointer
pix_freq[j].left = NULL;
pix_freq[j].right = NULL;

//initializing the code
//word as end of line
pix_freq[j].code[0] = '\0' ;
j++;
}
}``````

``````//Sorting the histogram
struct huffcode temphuff;

//Sorting w.r.t probability
//of occurrence
for (i = 0; i <nodes; i++)
{
for (j = i + 1; j <nodes; j++)
{
if (huffcodes[i].freq <huffcodes[j].freq)
{
temphuff = huffcodes[i];
huffcodes[i] = huffcodes[j];
huffcodes[j] = temphuff;
}
}
}``````

``````//Building Huffman Tree

float sumprob;
int sumpix;
int n = 0, k = 0;
int nextnode = nodes;

//Since total number of
//nodes in Huffman Tree
//is 2*nodes-1
while (n <nodes - 1)
{

//two probabilities
sumprob = huffcodes[nodes - n - 1].freq + huffcodes[nodes - n - 2].freq;
sumpix = huffcodes[nodes - n - 1].pix + huffcodes[nodes - n - 2].pix;

//Appending to the pix_freq Array
pix_freq[nextnode].pix = sumpix;
pix_freq[nextnode].freq = sumprob;
pix_freq[nextnode].left = &pix_freq[huffcodes[nodes - n - 2].arrloc];

//arrloc points to the location
//of the child node in the
//pix_freq array
pix_freq[nextnode].right = &pix_freq[huffcodes[nodes - n - 1].arrloc];
pix_freq[nextnode].code[0] = '\0' ;

//Using sum of the pixel values as
//new representation for the new node
//since unlike strings, we cannot
//concatenate because the pixel values
//are stored as integers. However, if we
//store the pixel values as strings
//we can use the concatenated string as
//a representation of the new node.
i = 0;

//Sorting and Updating the huffcodes
//array simultaneously New position
//of the combined node
while (sumprob <= huffcodes[i].freq)
i++;

//Inserting the new node in
//the huffcodes array
for (k = nnz; k>= 0; k--)
{
if (k == i)
{
huffcodes[k].pix = sumpix;
huffcodes[k].freq = sumprob;
huffcodes[k].arrloc = nextnode;
}
else if (k> i)

//Shifting the nodes below
//the new node by 1
//For inserting the new node
//at the updated position k
huffcodes[k] = huffcodes[k - 1];
}
n += 1;
nextnode += 1;
}``````

``left_child_index=(nodes-n-2)``

``right_child_index=(nodes-n-1)``

``left_child_index=46-1-2=43``

``right_child_index=46-1-1=44``

``pix_freq[nextnode].right = &pix_freq[huffcodes[nodes - n - 1].arrloc];``

``````//Assigning Code through backtracking
char left = '0' ;
char right = '1' ;
int index;
for (i = totalnodes - 1; i>= nodes; i--) {
if (pix_freq[i].left != NULL) {
strconcat(pix_freq[i].left->code, pix_freq[i].code, left);
}
if (pix_freq[i].right != NULL) {
strconcat(pix_freq[i].right->code, pix_freq[i].code, right);
}
}``````
``````void strconcat( char * str, char * parentcode, char add)
{
int i = 0;
while (*(parentcode + i) != '\0' ) {
*(str + i) = *(parentcode + i);
i++;
}
str[i + 1] = '\0' ;
}``````

``````//Encode the Image
int pix_val;

//Writing the Huffman encoded
// Image into a text file
FILE * imagehuff = fopen ( "encoded_image.txt" , "wb" );
for (r = 0; r <height; r++)
for (c = 0; c <width; c++) {
pix_val = image[r];
for (i = 0; i <nodes; i++)
if (pix_val == pix_freq[i].pix)
fprintf (imagehuff, "%s" , pix_freq[i].code);
}
fclose (imagehuff);

//Printing Huffman Codes
printf ( "Huffmann Codes::\n\n" );
printf ( "pixel values ->   Code\n\n" );
for (i = 0; i <nodes; i++) {
if (snprintf(NULL, 0, "%d" , pix_freq[i].pix) == 2)
printf ( "     %d      -> %s\n" , pix_freq[i].pix, pix_freq[i].code);
else
printf ( "    %d      -> %s\n" , pix_freq[i].pix, pix_freq[i].code);
}``````

``````//Calculating Average number of bits
float avgbitnum = 0;
for (i = 0; i <nodes; i++)
avgbitnum += pix_freq[i].freq * codelen(pix_freq[i].code);``````

``````int codelen( char * code)
{
int l = 0;
while (*(code + l) != '\0' )
l++;
return l;
}``````

``Average number of bits = 5.343750``

``````pixel values -> Code
72      -> 011001
75      -> 010100
79      -> 110111
83      -> 011010
84      -> 00100
87      -> 011100
89      -> 010000
93      -> 010111
94      -> 00011
96      -> 101010
98      -> 101110
100      -> 000101
102      -> 0001000
103      -> 0001001
105      -> 110110
106      -> 00110
110      -> 110100
114      -> 110101
115      -> 1100
118      -> 011011
119      -> 011000
122      -> 1110
124      -> 011110
125      -> 011111
127      -> 0000
128      -> 011101
130      -> 010010
131      -> 010011
136      -> 00111
138      -> 010001
139      -> 010110
140      -> 1111
142      -> 00101
143      -> 010101
146      -> 10010
148      -> 101011
149      -> 101000
153      -> 101001
155      -> 10011
163      -> 101111
167      -> 101100
169      -> 101101
170      -> 100010
174      -> 100011
175      -> 100000
188      -> 100001``````

``````0111010101000110011101101010001011010000000101111
00010001101000100100100100010010101011001101110111001
00000001100111101010010101100001111000110110111110010
10110001000000010110000001100001100001110011011110000
10011001101111111000100101111100010100011110000111000
01101001110101111100000111101100001110010010110101000
0111101001100101101001010111``````

## 图像压缩码

``````//C Code for
//Image Compression
#include <stdio.h>
#include <stdlib.h>

//function to calculate word length
int codelen( char * code)
{
int l = 0;
while (*(code + l) != '\0' )
l++;
return l;
}

//function to concatenate the words
void strconcat( char * str, char * parentcode, char add)
{
int i = 0;
while (*(parentcode + i) != '\0' )
{
*(str + i) = *(parentcode + i);
i++;
}
if (add != '2' )
{
str[i + 1] = '\0' ;
}
else
str[i] = '\0' ;
}

//function to find fibonacci number
int fib( int n)
{
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}

//Driver code
int main()
{
int i, j;
char filename[] = "Input_Image.bmp" ;
int data = 0, offset, bpp = 0, width, height;
long bmpsize = 0, bmpdataoff = 0;
int ** image;
int temp = 0;

//Reading the BMP File
FILE * image_file;

image_file = fopen (filename, "rb" );
if (image_file == NULL)
{
printf ( "Error Opening File!!" );
exit (1);
}
else
{

//Set file position of the
//stream to the beginning
//Contains file signature
//or ID "BM"
offset = 0;

//Set offset to 2, which
//contains size of BMP File
offset = 2;

fseek (image_file, offset, SEEK_SET);

//Getting size of BMP File
fread (&bmpsize, 4, 1, image_file);

//Getting offset where the
//pixel array starts
//Since the information is
//at offset 10 from the start, //as given in BMP Header
offset = 10;

fseek (image_file, offset, SEEK_SET);

//Bitmap data offset
fread (&bmpdataoff, 4, 1, image_file);

//Getting height and width of the image
//Width is stored at offset 18 and
//height at offset 22, each of 4 bytes
fseek (image_file, 18, SEEK_SET);

fread (&width, 4, 1, image_file);

fread (&height, 4, 1, image_file);

//Number of bits per pixel
fseek (image_file, 2, SEEK_CUR);

fread (&bpp, 2, 1, image_file);

//Setting offset to start of pixel data
fseek (image_file, bmpdataoff, SEEK_SET);

//Creating Image array
image = ( int **) malloc (height * sizeof ( int *));

for (i = 0; i <height; i++)
{
image[i] = ( int *) malloc (width * sizeof ( int ));
}

//int image[height][width]
//can also be done
//Number of bytes in
//the Image pixel array
int numbytes = (bmpsize - bmpdataoff) /3;

//Reading the BMP File
//into Image Array
for (i = 0; i <height; i++)
{
for (j = 0; j <width; j++)
{
fread (&temp, 3, 1, image_file);

//the Image is a
//24-bit BMP Image
temp = temp & 0x0000FF;
image[i][j] = temp;
}
}
}

//Finding the probability
//of occurrence
int hist[256];
for (i = 0; i <256; i++)
hist[i] = 0;
for (i = 0; i <height; i++)
for (j = 0; j <width; j++)
hist[image[i][j]] += 1;

//Finding number of
//non-zero occurrences
int nodes = 0;
for (i = 0; i <256; i++)
if (hist[i] != 0)
nodes += 1;

//Calculating minimum probability
float p = 1.0, ptemp;
for (i = 0; i <256; i++)
{
ptemp = (hist[i] /( float )(height * width));
if (ptemp> 0 && ptemp <= p)
p = ptemp;
}

//Calculating max length
//of code word
i = 0;
while ((1 /p)> fib(i))
i++;
int maxcodelen = i - 3;

//Defining Structures pixfreq
struct pixfreq
{
int pix, larrloc, rarrloc;
float freq;
struct pixfreq *left, *right;
char code[maxcodelen];
};

//Defining Structures
//huffcode
struct huffcode
{
int pix, arrloc;
float freq;
};

//Declaring structs
struct pixfreq* pix_freq;
struct huffcode* huffcodes;
int totalnodes = 2 * nodes - 1;
pix_freq = ( struct pixfreq*) malloc ( sizeof ( struct pixfreq) * totalnodes);
huffcodes = ( struct huffcode*) malloc ( sizeof ( struct huffcode) * nodes);

//Initializing
j = 0;
int totpix = height * width;
float tempprob;
for (i = 0; i <256; i++)
{
if (hist[i] != 0)
{

//pixel intensity value
huffcodes[j].pix = i;
pix_freq[j].pix = i;

//location of the node
//in the pix_freq array
huffcodes[j].arrloc = j;

//probability of occurrence
tempprob = ( float )hist[i] /( float )totpix;
pix_freq[j].freq = tempprob;
huffcodes[j].freq = tempprob;

//Declaring the child of leaf
//node as NULL pointer
pix_freq[j].left = NULL;
pix_freq[j].right = NULL;

//initializing the code
//word as end of line
pix_freq[j].code[0] = '\0' ;
j++;
}
}

//Sorting the histogram
struct huffcode temphuff;

//Sorting w.r.t probability
//of occurrence
for (i = 0; i <nodes; i++)
{
for (j = i + 1; j <nodes; j++)
{
if (huffcodes[i].freq <huffcodes[j].freq)
{
temphuff = huffcodes[i];
huffcodes[i] = huffcodes[j];
huffcodes[j] = temphuff;
}
}
}

//Building Huffman Tree
float sumprob;
int sumpix;
int n = 0, k = 0;
int nextnode = nodes;

//Since total number of
//nodes in Huffman Tree
//is 2*nodes-1
while (n <nodes - 1)
{

//Adding the lowest two probabilities
sumprob = huffcodes[nodes - n - 1].freq + huffcodes[nodes - n - 2].freq;
sumpix = huffcodes[nodes - n - 1].pix + huffcodes[nodes - n - 2].pix;

//Appending to the pix_freq Array
pix_freq[nextnode].pix = sumpix;
pix_freq[nextnode].freq = sumprob;
pix_freq[nextnode].left = &pix_freq[huffcodes[nodes - n - 2].arrloc];
pix_freq[nextnode].right = &pix_freq[huffcodes[nodes - n - 1].arrloc];
pix_freq[nextnode].code[0] = '\0' ;
i = 0;

//Sorting and Updating the
//huffcodes array simultaneously
//New position of the combined node
while (sumprob <= huffcodes[i].freq)
i++;

//Inserting the new node
//in the huffcodes array
for (k = nodes; k>= 0; k--)
{
if (k == i)
{
huffcodes[k].pix = sumpix;
huffcodes[k].freq = sumprob;
huffcodes[k].arrloc = nextnode;
}
else if (k> i)

//Shifting the nodes below
//the new node by 1
//For inserting the new node
//at the updated position k
huffcodes[k] = huffcodes[k - 1];

}
n += 1;
nextnode += 1;
}

//Assigning Code through
//backtracking
char left = '0' ;
char right = '1' ;
int index;
for (i = totalnodes - 1; i>= nodes; i--)
{
if (pix_freq[i].left != NULL)
strconcat(pix_freq[i].left->code, pix_freq[i].code, left);
if (pix_freq[i].right != NULL)
strconcat(pix_freq[i].right->code, pix_freq[i].code, right);
}

//Encode the Image
int pix_val;
int l;

//Writing the Huffman encoded
//Image into a text file
FILE * imagehuff = fopen ( "encoded_image.txt" , "wb" );
for (i = 0; i <height; i++)
for (j = 0; j <width; j++)
{
pix_val = image[i][j];
for (l = 0; l <nodes; l++)
if (pix_val == pix_freq[l].pix)
fprintf (imagehuff, "%s" , pix_freq[l].code);
}

//Printing Huffman Codes
printf ( "Huffmann Codes::\n\n" );
printf ( "pixel values ->   Code\n\n" );
for (i = 0; i <nodes; i++) {
if (snprintf(NULL, 0, "%d" , pix_freq[i].pix) == 2)
printf ( "     %d      -> %s\n" , pix_freq[i].pix, pix_freq[i].code);
else
printf ( "    %d      -> %s\n" , pix_freq[i].pix, pix_freq[i].code);
}

//Calculating Average Bit Length
float avgbitnum = 0;
for (i = 0; i <nodes; i++)
avgbitnum += pix_freq[i].freq * codelen(pix_freq[i].code);
printf ( "Average number of bits:: %f" , avgbitnum);
}``````

gcc -o huffman huffman.c

./huffman

• 回顶