游程编码

利用游程编码实现二值图像压缩 收藏
编码方案设计：
按位进行压缩，对二进制流进行超前扫描，判断是否值得压缩，如果压缩有意义，则压缩；否则保持原始数据。
系统实现方案：
总体思想：将图像文件以二进制方式读入缓冲区，把二进制位转制为整数，对缓冲区数据进行编码，以特定的格式(unsigned short)写入输出文件；解压缩过程反过来即可。
压缩文件存储格式：
以每两个字节为单位储存(即每次写入16位unsigned short类型)。
 0   1              2~15
          

            ...
第0位　存储压缩信息(1压缩；0不压缩，原始数据)
第1位　如果第0位为1(压缩)，此位标明字符类别(0或1)；如果第0位为0(原始数据)，此位无意义，默认为0
后14位　存储字符数量或者原始数据的值
算法实现：
缓冲区：定义缓冲区为一维char数组，因为只用14位来统计数量，所以缓冲区总字符量即维数应小于或等于214(16384)。
判断可压缩性：对当前指针位置，超前扫描16位，如果这16位全相同(例：11111111111111或00000000000000),那么可压缩性为真，从当前位置开始计数并指针前移，直到相同序列终止或到达缓冲区边界为止。将统计数量写入unsigned short类型后14位，第0位置1,第0位置为当前字符；如果16位中有不相同数据(例：11111101111011)或缓冲区中有效数据不足16位，那么可压缩性为假，从当前位置开始读14位(如果缓冲区中剩余不足14位，有多少位读多少位)。把原始数位写入unsinged short类型后14位，前两位置0。
解压缩：每次从压缩文件读取16位到short类型，根据第0位和第1位的数值进行相应的解码处理，直到缓冲区满，每次从缓冲区中取８位，写入文件。


本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/fuchuangbob/archive/2008/03/30/2230753.aspx
Bmpheader.h
typedef unsigned char   BYTE;
typedef unsigned short   WORD;
typedef unsigned long   DWORD;
typedef long            LONG;

typedef struct
...{
        /**//* BITMAPFILEHEADER*/
        BYTE    bfType[2];// 位图文件的类型，必须为BM
        DWORD   bfSize;//位图文件的大小，以字节为单位
        WORD    bfReserved1;// 位图文件保留字，必须为
        WORD    bfReserved2;// 位图文件保留字，必须为
        DWORD   bfOffBits;// 位图数据的起始位置，以相对于位图文件头的偏移量表示，以字节为单位
        /**//* BITMAPINFOHEADER*/
        DWORD   BiSize;// 本结构所占用字节数
        LONG    BiWidth;// 位图的宽度，以像素为单位
        LONG    BiHeight;// 位图的高度，以像素为单位
        WORD    BiPlanes;// 目标设备的级别，必须为
        WORD    BiBitCount;//每个像素所需的位数，必须是
        DWORD   BiCompression;// 位图压缩类型，必须是0(不压缩), 1(BI_RLE8压缩类型)或(BI_RLE4压缩类型)之一
        DWORD   BiSizeImage;// 位图的大小，以字节为单位
        LONG    BiXpelsPerMeter;// 位图水平分辨率，每米像素数
        LONG    BiYpelsPerMeter;// 位图垂直分辨率，每米像素数
        DWORD   BiClrUsed;// 位图实际使用的颜色表中的颜色数
        DWORD   BiClrImportant;// 位图显示过程中重要的颜色数
} BITMAPHEADER;
/**//*************颜色表**************/
typedef struct
...{  
        unsigned char   blue;// 蓝色的亮度(值范围为-255)  
        unsigned char   green;  
        unsigned char   red;  
        char   reserved;// 保留，必须为
} RGBQUAD;
/**//*********压缩字符流结点**********/
Main.cpp
 /**//*黑白点二值位图游程编码压缩程序*/
  /**//*2008.3.20 
  作者：付闯　*/
  #include
  #include
  #include
  #include
  #include"bmpheader.h"
  const unsigned short MaxSize=16384;//14字节最大数
 
  void compress(FILE *,FILE *);//压缩
  void decompress(FILE *,FILE *);//解压缩
  void wbuffer(FILE *,char *,int);/**//*将像素信息写入缓冲区*/
  void buf_init(char *,int);//缓冲初始化
  void rbuffer(FILE *,char *,int);//读缓冲到文件

  unsigned long RLE(FILE *,char *,int,unsigned long);//游程压缩，并返回写入字节数
  void decode(FILE *,char *,int);//解码，逆运算
  / /void bufdisplay(char *,char *,int);//打印缓冲，测试用
  DWORD getBMPsize(FILE *ifp);//获取位图大小
  int IsFeasible(char *,char *,int);//判断压缩可行性，可行
 
  int main()
  ...{
        FILE *ifp,*ofp,*ffp;
        char choic;
       char *ifilename,*ofilename;
       ifilename=(char *)malloc(1);
       ofilename=(char *)malloc(1);
        printf("a.压 缩 b.解压缩 ");
        choic=getch();
        if(choic=='a')
        ...{
           printf("请输入压缩(Compress)源文件名:");
           scanf("%s",ifilename);
           printf("请输入压缩(Compress)输出文件名:");
           scanf("%s",ofilename);
           if((ifp=fopen(ifilename,"rb"))==NULL)
           ...{
               printf("无法打开文件!");
               getch();
               return 1;
           }
           if((ofp=fopen(ofilename,"wb"))==NULL)
            ...{
               printf("无法创建文件!");
               getch();
               return 1;
            }
           compress(ifp,ofp);
           printf("文件%s成功压缩为文件%s",ifilename,ofilename);
           fclose(ifp);
           fclose(ofp);
        }
        else
        ...{
           printf("请输入解压缩(Decompress)源文件名:");
           scanf("%s",ifilename);
           printf("请输入解压缩(Decompress)输出文件名:");
           scanf("%s",ofilename);
           if((ofp=fopen(ifilename,"rb"))==NULL)
            ...{
               printf("无法打开文件!");
               getch();
               return 1;
            }
           if((ffp=fopen(ofilename,"wb"))==NULL)
            ...{
               printf("无法创建文件!");
               getch();
               return 1;
            }
           decompress(ofp,ffp);
           printf("文件%s成功解压缩为文件%s!",ifilename,ofilename);
           fclose(ofp);
           fclose(ffp);
        }
        getch();
        return 0;
}
DWORD getBMPsize(FILE *ifp)
...{
        DWORD size;
        fseek(ifp,2,0);
        fread(&size,4,1,ifp);
        rewind(ifp);
        return size;
}
/**//**************************缓冲区初始化****************************/
void buf_init(char *buffer,int size)
...{
    memset(buffer,-1,size);
}
/**//******************************************************************************************/
/**//************************************以下是压缩算法****************************************/
/**//******************************************************************************************/
void compress(FILE *ifp,FILE *ofp)
...{
         
        unsigned long input,output=0;
        input=getBMPsize(ifp);
        char buffer[MaxSize];/**//*缓冲区*/
        while(!feof(ifp))
        ...{
            wbuffer(ifp,buffer,MaxSize);
            output=RLE(ofp,buffer,MaxSize,output);
        }
        printf("Compressing Rate= %f %% ",output*100.0/input);
        //printf("%d",sizeof(OutUnit));
}

/**//************************************将二进制的位写入缓冲区***************************************/
void wbuffer(FILE *ifp,char *buffer,int size)
...{
          char *tpbuf=buffer;
          unsigned char temp=0;
          int i;
          /**//* fseek(ifp,62,0); */
          buf_init(buffer,size);
         
          while(size>0&&!feof(ifp))
          ...{
               temp=fgetc(ifp);/**//*每次取8个像素*/
               if(feof(ifp))break;//BUG之所在,必须要再读一个字节,函数才能判断文件尾
              
               for(i=7;i>=0;--i,++tpbuf)
               ...{
                   *tpbuf=(temp>>i)&1;/**//*写入一行转换为二进制,高位在行左边*/
                    /**//* printf("%d",buffer[MaxSize-size][j]); */
               }
               size-=8;
              
          }
          //bufdisplay("codisplay.txt",buffer,MaxSize);
          //getch();
}
/**//**********************************对缓冲区中数值进行编码，并返回码序列**************************************/
unsigned long RLE(FILE *ofp,char *buffer,int size,unsigned long output)
...{
              unsigned short ounit=0,count=0;
              int i=0;            
              char temp;
              char *tpbuf=buffer;
             
              temp=0;
             
              while(*tpbuf!=-1&&(i              ...{
                      temp=*tpbuf;
                      ounit=count=0;
                      //currentbit=temp;
                      if(!IsFeasible(tpbuf,buffer,MaxSize))
                      ...{
                          int k=0;
                          for(k=13;k>=0&&*tpbuf!=-1&&tpbuf!=(buffer+size-1);--k,++tpbuf,++i)//！！！！越界了！！！！
                          ...{
                              count+=(*tpbuf)<                          }
                          ounit=count;//不压缩
                          //ounit->id=0;//任意值
                          fwrite(&ounit,sizeof(unsigned short),1,ofp);
                         
                      }
                      else
                      ...{
                          count=0;
                          ounit+=1<<15;//压缩
                          ounit+=temp<<14;
                          while(*tpbuf==temp&&i                          ...{
                              ++count;
                              ++tpbuf;
                              ++i;
                          }
                          ounit+=count;
                          fwrite(&ounit,sizeof(unsigned short),1,ofp);
                      }
                      output+=sizeof(unsigned short);
              }
             
              return output;
}
int IsFeasible(char *current,char *buffer,int size)
...{
            char i,id;
            int distance=current-buffer;
            for(i=0,id=*current;i<16;++i,++distance)
            ...{
                if(*(current+i)!=id||*(current+i)==-1||distance>(size-1))return 0;
            }
            return 1;
}
/**//******************************************************************************************/
/**//************************************以下是解压缩算法****************************************/
/**//******************************************************************************************/
void decompress(FILE *ifp,FILE *ofp)
...{
        char buffer[MaxSize];
        buf_init(buffer,MaxSize);
        while(!feof(ifp))
        ...{
            //fgetc(ifp);
            decode(ifp,buffer,MaxSize);
            rbuffer(ofp,buffer,MaxSize);
            //printf("Waiting..... ");getch();
        }
       
}
/**//********************************根据编码规则进行解码************************************/
void decode(FILE *ifp,char *buffer,int size)
...{
        int i=0;
        unsigned short temp=0;
        char *tpbuf=buffer;
                   
        buf_init(buffer,MaxSize);
        while(i        ...{
                fread(&temp,sizeof(unsigned short),1,ifp);
                if(feof(ifp))   break;//BUG之所在,解决了,没有这句就会多读32位
                if(temp>(1<<15))//第一位为１压缩，否则按非压缩处理
                ...{
                   if(((temp>>14)&1)==1)//第２位为１，则像素为１,否则为
                       //一定要将操作数移位和１与，不可将１移位和操作数与
                   ...{
                        unsigned short num1=temp&((1<<14)-1);
                        for(;num1>0&&i                            *tpbuf=1;
                   }
                   else
                   ...{
                        unsigned short num0=temp&((1<<14)-1);
                        for(;num0>0&&i                            *tpbuf=0;
                   }
                }
                else//非压缩
                ...{
                       int k;
                       for(k=13;k>=0&&(tpbuf-buffer)                       ...{
                           //if(*)
                           *tpbuf=(temp>>k)&1;
                       }
                }
                //int a=temp;
       }
       
       //bufdisplay("dedisplay.txt",buffer,MaxSize);
}
/**//*******************************读取缓冲区中二进制，输出到文件**********************************/
void rbuffer(FILE *ofp,char *buffer,int size)
...{
            unsigned char temp=0;
            int i=0;
            char *tpbuf=buffer;
           
            while(size>0&&*tpbuf!=-1)
            ...{
                   for(i=7;i>=0;--i,++tpbuf)//将位信息转换为１字节整数，并输出到文件
                   ...{
                        /**//* printf("%d ",buffer[MaxSize-size][i]<                        if(*tpbuf==-1)break;
                        /**//* getch(); */
                        temp+=*tpbuf<                        --size;
                   }
                   fputc(temp,ofp);
                   temp=0;
            }
}

/**//*void bufdisplay(char *s,char *buffer,int size)
{
            int i;
            FILE *fp=fopen(s,"wt");
            for(i=0;i            {
              fprintf(fp,"%d",buffer[i]);
              //fprintf(fp," ");
            }
            fclose(fp); 
}*/

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/fuchuangbob/archive/2008/03/30/2230753.aspx