前言：
利用三元组可以实现对稀疏矩阵的压缩，实际上一幅图像就是一个矩阵，当这幅图像的背景色所占的比重比较大时就可以对图像进行压缩处理。
主要的思路
原始图像压缩：
首先将bmp图像文件读入内存，创建一个链表用于统计每种颜色出现的频数，从而找到最多的颜色，即背景颜色。在将从内存读取颜色的数据与背景颜色相对比，若不是背景颜色就将其横坐标、总坐标、RGB颜色分量值写入文件。因此诸多的背景颜色数据就只需要写入一次，从而达到数据的压缩的目的。
将压缩后的数据读取并画图：
首先读取出背景颜色值，设置画布的背景颜色，接着再读取三元组颜色值，用putpixel函数打点画出。
定义的一些结构体
bmp文件信息头部结构体
typedef struct tagBITMAPFILEHEADER // 文件信息头结构体
{
//unsigned short bfType; // 19778，必须是BM字符串，对应的十六进制为0x4d42,十进制为19778，否则不是bmp格式文件
unsigned int bfSize; // 文件大小 以字节为单位(2-5字节)
unsigned short bfReserved1; // 保留，必须设置为0 (6-7字节)
unsigned short bfReserved2; // 保留，必须设置为0 (8-9字节)
unsigned int bfOffBits; // 从文件头到像素数据的偏移 (10-13字节)
} BITMAPFILEHEADER;
bmp图像信息结构体
typedef struct tagBITMAPINFOHEADER //图像信息头结构体
{
unsigned int biSize; // 此结构体的大小 (14-17字节)
long biWidth; // 图像的宽 (18-21字节)
long biHeight; // 图像的高 (22-25字节)
unsigned short biPlanes; // 表示bmp图片的平面属，显然显示器只有一个平面，所以恒等于1 (26-27字节)
unsigned short biBitCount; // 一像素所占的位数，一般为24 (28-29字节)
unsigned int biCompression; // 说明图象数据压缩的类型，0为不压缩。 (30-33字节)
unsigned int biSizeImage; // 像素数据所占大小, 这个值应该等于上面文件头结构中bfSize-bfOffBits (34-37字节)
long biXPelsPerMeter; // 说明水平分辨率，用象素/米表示。一般为0 (38-41字节)
long biYPelsPerMeter; // 说明垂直分辨率，用象素/米表示。一般为0 (42-45字节)
unsigned int biClrUsed; // 说明位图实际使用的彩色表中的颜色索引数（设为0的话，则说明使用所有调色板项）。 (46-49字节)
unsigned int biClrImportant; // 说明对图象显示有重要影响的颜色索引的数目，如果是0，表示都重要。(50-53字节)
} BITMAPINFOHEADER;
RGB颜色结构体
typedef struct
{
unsigned char b;
unsigned char g;
unsigned char r;
}colorData;
一个包含像素颜色的个数的链表节点
typedef struct Node
{
colorData color;
int num;
Node * pNext;
}NODE,*PNODE;
三元组结构体
typedef struct
{
short int i,j;
colorData c;
}Triple;
三元组结构体
typedef struct
{
short int height,width;//原始图像的高、宽
int foreNum;//非背景色元素的个数
Triple * data;
colorData backColor;//背景色
}TSMatrix;
一些函数
链表初始化函数
PNODE InitList(void)
{
PNODE pHead=(PNODE)malloc(sizeof(NODE));
if(pHead == NULL)
{
printf("动态内存分配失败！\n");
exit(-1);
}
PNODE pTail=pHead;
pTail->pNext = NULL;
return pHead;
}
在链表尾部加上之前没出现过的颜色
bool Append(PNODE pHead,colorData c)
{
PNODE pNew=(PNODE)malloc(sizeof(NODE)),q;
PNODE p=pHead;
while((p->pNext)!=NULL)
p = p->pNext;
q=p->pNext;
pNew->color=c;
pNew->num = 1;
p->pNext=pNew;
pNew->pNext=q;
return true;
}
比较颜色在链表中是否有，若有，则数量+1，若没有，在链表尾部加上此颜色
void Compare(PNODE pHead,colorData c)
{
PNODE p=pHead->pNext;
while(NULL!=p)
{
if (p->color.r==c.r&&p->color.g==c.g&&p->color.b==c.b)
{
p->num++;
return;
}
else
p=p->pNext;
}
Append(pHead,c);
}
得到背景色函数
colorData MaxColor(PNODE pHead,int * backNum)//backNum背景色的像素点个数，foreNum非背景色像素点个数
{
PNODE p=pHead->pNext;
colorData c;
int max = 0;//存放最大颜色数
while(NULL!=p)
{
if (p->num>max)
{
c = p->color;
max = p->num;
}
p=p->pNext;
}
*backNum = max;
return c;
}
将bmp图像读入并作压缩出来的主函数
int main(void)
{
unsigned char x;
unsigned short fileType;
BITMAPFILEHEADER fileHeader;
BITMAPINFOHEADER infoHeader;
int i,j,s,xx = 0;
FILE * fp = fopen("dlam.bmp","rb");
fread(&fileType,sizeof (unsigned short),1, fp);
fread(&fileHeader,sizeof(BITMAPFILEHEADER),1,fp);
fread(&infoHeader,sizeof(BITMAPINFOHEADER),1,fp);
colorData c,backColor;
colorData map[infoHeader.biHeight][infoHeader.biWidth];//保存像素数据到内存中的变量
PNODE pHead = NULL;
pHead=InitList();
// -----------------得到背景色数据以及将图像像素数据写入内存保存在map二维数组中-------------------------------------
for(i=0;i<infoHeader.biHeight;i++)//控制行
{
for(j=0;j<infoHeader.biWidth;j++)//控制列
{
fread(&c.b,sizeof(char),1,fp);
map[i][j].b = c.b;
fread(&c.g,sizeof(char),1,fp);
map[i][j].g = c.g;
fread(&c.r,sizeof(char),1,fp);
map[i][j].r = c.r;
Compare(pHead,c);
}
s = 4-(infoHeader.biWidth*3)%4;//每一行的字节数要是4的倍数
fread(&x,s*sizeof(char),1,fp);
}
int backNum = 0,foreNum = 0;//记录背景色像素点个数，非背景色像素点个数
backColor = MaxColor(pHead,&backNum);//得到背景颜色
foreNum = infoHeader.biHeight*infoHeader.biWidth-backNum;
fclose(fp);
// ------------------将压缩后的图像数据写入文件----------------------
FILE * fp1 = fopen("..\\读和画\\dlam1.bmp","wb");
fwrite(&infoHeader.biHeight,sizeof(short int),1,fp1);//写入高度
fwrite(&infoHeader.biWidth,sizeof(short int),1,fp1);//写入宽度
fwrite(&backColor,sizeof(colorData),1,fp1);//写入背景色
fwrite(&foreNum,sizeof(int),1,fp1);//写入非背景色像素点个数
for(i=0;i<infoHeader.biHeight;i++)//控制行
{
for(j=0;j<infoHeader.biWidth;j++)//控制列
{
c = map[i][j];
if(c.b!=backColor.b||c.g!=backColor.g||c.r!=backColor.r)
{
fwrite(&i,sizeof(short int),1,fp1);//先写入非背景颜色的行坐标,用2个字节的大小保存
fwrite(&j,sizeof(short int),1,fp1);//再写入非背景颜色的列坐标
fwrite(&c.b,sizeof(unsigned char),1,fp1);
fwrite(&c.g,sizeof(unsigned char),1,fp1);
fwrite(&c.r,sizeof(unsigned char),1,fp1);
//printf("%d\tsuccess\trow:%d\tcol:%d\tb:%x\tg:%x\tr:%x\n",++xx,i,j,c.b,c.g,c.r);
}
}
}
printf("dlam1.bmp文件写入成功\n\n\n");
fclose(fp1);
// -------------------------------------输出相关信息-------------------------------------
printf("背景色个数：%d\t非背景色个数：%d\n最多颜色为：",backNum,foreNum);
printf("%x\t%x\t%x\n",backColor.r,backColor.g,backColor.b);
int after,before;//存放压缩前后文件大小
after = 2 + 2 + 3 + 4 + 7*foreNum;//2个短整型（原始图像高、宽）+1个背景色+一个整型（非背景色的像素点个数）+三元组颜色（坐标用短整型）
before = fileHeader.bfSize;
printf("压缩前文件大小：%d\t压缩后文件大小：%d\n",before,after);
printf("压缩比：%.2f\n",(double)((double)before/after));
getchar();
return 0;
}
将压缩后的bmp图像再重新读入内存并画出图像的函数
int main()
{
unsigned short int width,height,row,col;
int i,c;//i用于循环，c用于存放颜色值（RGB函数生成）
initwindow(600,600,"画一只机器猫"); //初始化一个图像窗口（默认背景色是黑色）
FILE * fp = fopen("dlam1.bmp","rb");
TSMatrix * m = (TSMatrix * )malloc(sizeof(TSMatrix));//三元组矩阵
//先读取原始图像的高、宽、背景色、非背景颜色像素点个数
fread(&m->height,sizeof(unsigned short int),1,fp);
fread(&m->width,sizeof(unsigned short int),1,fp);
fread(&m->backColor,sizeof(colorData),1,fp);
fread(&m->foreNum,sizeof(int),1,fp);
//---------------------------读取像素点数据到内存中-------------------------
m->data = (Triple * )malloc(m->foreNum*sizeof(Triple));
for(i=0;i<m->foreNum;i++)
{
fread(&m->data[i].i,sizeof(short int),1,fp);
fread(&m->data[i].j,sizeof(short int),1,fp);
fread(&m->data[i].c.b,sizeof(unsigned char),1,fp);
fread(&m->data[i].c.g,sizeof(unsigned char),1,fp);
fread(&m->data[i].c.r,sizeof(unsigned char),1,fp);
}
fclose(fp);
//----------------------------开始画图 ------------------------------------
//设置背景颜色
c = RGB(m->backColor.r,m->backColor.g,m->backColor.b);
setbkcolor(c);
cleardevice(); // 清屏
for(i=0;i<m->foreNum;i++)
{
c = RGB(m->data[i].c.r,m->data[i].c.g,m->data[i].c.b);
putpixel(m->data[i].j,m->height-(m->data[i].i),c);//打点
//printf("%d\t%d\t%x\t%x\t%x\n",m->data[i].i,m->data[i].j,m->data[i].c.b,m->data[i].c.g,m->data[i].c.r);
}
//----------------------------输出相关信息 --------------------------------
printf("height = %d\twidth = %d\t非背景颜色个数 = %d\n",m->height,m->width,m->foreNum);
printf("背景颜色：r = %x\tg = %x\tb = %x \n",m->backColor.b,m->backColor.g,m->backColor.r);
getchar();
getchar();
closegraph(); //关闭图像窗口
return 0;
}