请你用c语言实现一个哈夫曼编码图片压缩算法,要求代码要有注释
时间: 2023-11-22 21:55:46 浏览: 45
哈夫曼编码是一种无损压缩算法,它通过将频繁出现的字符用较短的编码表示,来减小文件的大小。在图片压缩中,我们可以将图片中像素点的RGB值看作字符,并对其进行哈夫曼编码。
下面是用C语言实现哈夫曼编码图片压缩的代码,注释已经详细标明。
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_PIXELS 1000000 // 定义最大像素点数
#define MAX_COLORS 256 // 定义最大颜色数
// 定义哈夫曼树节点结构体
typedef struct node {
int freq; // 频率
int pixel; // 像素点
struct node *left; // 左子节点
struct node *right; // 右子节点
} Node;
// 定义哈夫曼编码结构体
typedef struct code {
int bits[MAX_COLORS]; // 编码位
int length; // 编码长度
} Code;
// 定义全局变量
int pixels[MAX_PIXELS]; // 存储像素点的数组
int frequencies[MAX_COLORS]; // 存储每个颜色出现的频率
Code codes[MAX_COLORS]; // 存储每个颜色的哈夫曼编码
int num_pixels; // 像素点数
int num_colors; // 颜色数
// 定义函数
void read_image(char *filename); // 读取图片
void write_compressed(char *filename); // 写入压缩文件
void write_codes(char *filename); // 写入编码文件
void compress_image(); // 压缩图片
void compute_frequencies(); // 计算每个颜色出现的频率
Node* build_tree(); // 构建哈夫曼树
void build_codes(Node *root, int bits[], int length); // 构建哈夫曼编码
void free_tree(Node *root); // 释放哈夫曼树
int main(int argc, char *argv[]) {
if (argc != 4) { // 参数数目不符合要求
printf("Usage: %s input_file output_file code_file\n", argv[0]);
return 1;
}
read_image(argv[1]); // 读取图片
compress_image(); // 压缩图片
write_compressed(argv[2]); // 写入压缩文件
write_codes(argv[3]); // 写入编码文件
return 0;
}
void read_image(char *filename) {
FILE *fp = fopen(filename, "rb"); // 以二进制方式打开文件
if (!fp) { // 文件打开失败
printf("Cannot open file %s\n", filename);
exit(1);
}
unsigned char header[54]; // BMP文件头部为54字节
fread(header, sizeof(unsigned char), 54, fp); // 读取文件头部
int width = *(int*)&header[18]; // 图片宽度
int height = *(int*)&header[22]; // 图片高度
if (width * height > MAX_PIXELS) { // 图片像素点数超过最大值
printf("Image size too large\n");
exit(1);
}
int padding = 0;
while ((width * 3 + padding) % 4 != 0) { // 计算填充字节数
padding++;
}
for (int i = 0; i < height; i++) { // 逐行读取像素点
for (int j = 0; j < width; j++) {
unsigned char pixel[3];
fread(pixel, sizeof(unsigned char), 3, fp);
pixels[i * width + j] = ((int)pixel[0] << 16) | ((int)pixel[1] << 8) | (int)pixel[2]; // 将RGB值存储为一个整数
}
fseek(fp, padding, SEEK_CUR); // 跳过填充字节
}
fclose(fp); // 关闭文件
num_pixels = width * height; // 计算像素点数
}
void write_compressed(char *filename) {
FILE *fp = fopen(filename, "wb"); // 以二进制方式打开文件
if (!fp) { // 文件打开失败
printf("Cannot open file %s\n", filename);
exit(1);
}
fwrite(&num_pixels, sizeof(int), 1, fp); // 写入像素点数
for (int i = 0; i < num_pixels; i++) {
unsigned char r = (unsigned char)((pixels[i] >> 16) & 0xFF); // 从整数中提取RGB值
unsigned char g = (unsigned char)((pixels[i] >> 8) & 0xFF);
unsigned char b = (unsigned char)(pixels[i] & 0xFF);
fwrite(&r, sizeof(unsigned char), 1, fp); // 写入RGB值
fwrite(&g, sizeof(unsigned char), 1, fp);
fwrite(&b, sizeof(unsigned char), 1, fp);
}
fclose(fp); // 关闭文件
}
void write_codes(char *filename) {
FILE *fp = fopen(filename, "w"); // 以文本方式打开文件
if (!fp) { // 文件打开失败
printf("Cannot open file %s\n", filename);
exit(1);
}
for (int i = 0; i < num_colors; i++) {
fprintf(fp, "%d:", i); // 写入颜色编号
for (int j = codes[i].length - 1; j >= 0; j--) {
fprintf(fp, "%d", codes[i].bits[j]); // 写入编码位
}
fprintf(fp, "\n");
}
fclose(fp); // 关闭文件
}
void compress_image() {
compute_frequencies(); // 计算每个颜色出现的频率
Node *root = build_tree(); // 构建哈夫曼树
int bits[MAX_COLORS]; // 定义编码位数组
build_codes(root, bits, 0); // 构建哈夫曼编码
free_tree(root); // 释放哈夫曼树
}
void compute_frequencies() {
num_colors = 0; // 初始颜色数为0
memset(frequencies, 0, sizeof(frequencies)); // 清空频率数组
for (int i = 0; i < num_pixels; i++) {
int found = 0;
for (int j = 0; j < num_colors; j++) {
if (pixels[i] == frequencies[j]) { // 颜色已存在
found = 1;
break;
}
}
if (!found) { // 颜色不存在
frequencies[num_colors++] = pixels[i]; // 添加新的颜色
}
}
for (int i = 0; i < num_colors; i++) {
int freq = 0;
for (int j = 0; j < num_pixels; j++) {
if (pixels[j] == frequencies[i]) { // 统计颜色出现的频率
freq++;
}
}
frequencies[i] = freq;
}
}
Node* build_tree() {
Node *nodes[MAX_COLORS];
int num_nodes = num_colors;
for (int i = 0; i < num_colors; i++) {
nodes[i] = (Node*)malloc(sizeof(Node));
nodes[i]->freq = frequencies[i];
nodes[i]->pixel = i;
nodes[i]->left = NULL;
nodes[i]->right = NULL;
}
while (num_nodes > 1) { // 构建哈夫曼树
int min1 = 0, min2 = 0;
for (int i = 0; i < num_nodes; i++) {
if (nodes[i]->freq < nodes[min1]->freq) {
min2 = min1;
min1 = i;
} else if (nodes[i]->freq < nodes[min2]->freq) {
min2 = i;
}
}
Node *new_node = (Node*)malloc(sizeof(Node));
new_node->freq = nodes[min1]->freq + nodes[min2]->freq;
new_node->pixel = -1;
new_node->left = nodes[min1];
new_node->right = nodes[min2];
nodes[min1] = new_node;
nodes[min2] = nodes[--num_nodes];
}
return nodes[0];
}
void build_codes(Node *node, int bits[], int length) {
if (node->pixel >= 0) { // 叶子节点
memcpy(codes[node->pixel].bits, bits, length * sizeof(int)); // 复制编码位
codes[node->pixel].length = length; // 设置编码长度
} else { // 非叶子节点
bits[length++] = 0; // 左子节点编码为0
build_codes(node->left, bits, length);
bits[length-1] = 1; // 右子节点编码为1
build_codes(node->right, bits, length);
}
}
void free_tree(Node *root) {
if (root->left) {
free_tree(root->left); // 释放左子树
}
if (root->right) {
free_tree(root->right); // 释放右子树
}
free(root); // 释放根节点
}
```
此代码实现了从读取图片到生成压缩文件和编码文件的完整过程。需要注意的是,此代码中只支持BMP格式的图片,并且每个像素点的RGB值需要占用3个字节。如果要支持其他格式的图片,或者像素点的RGB值占用不同的字节数,需要对代码进行相应修改。