图像无损、有损压缩方法调研
无损压缩
无损压缩的压缩比相对较小，一般只能获得1-5倍的压缩比。常见的图像无损压缩编码方法主要有霍夫曼编码、算术编码、行程编码和LZW编码。
以上四种编码都属于统计编码的范畴，消除的是编码冗余，而预测编码消除的是像素间冗余。预测编码的基本思想建立在图像中邻近像素间高度相关的事实基础上。预测编码的突出的技术特点是不直接传送像素值，而对实际像素值与它的一个预测值之间的差值进行编码和传送，这种差值称为预测误差。
有损压缩
灰度级量化压缩
该算法采用低比特截断。如对于8比特图像，若将图像均匀量化为6比特，则将每个像素中最低两位的比特数截断，仅用前6位来表示，这样便实现了图像数据的压缩。而在重构图像时，低位被截断的比特用0补齐。
改进的行程编码
在全局设定一个阈值T，假定扫描的第一个像素灰度值为a，设为标准值data，第二个像素的灰度值为b，若b与data之差的绝对值小于或等于阈值T，则第二个像素的灰度值也量化为a，第三个像素的灰度值继续与标准值data比较，以此类推，直到遇到差的绝对值大于阈值T的像素，此时将此像素的灰度值设为新的标准值data，量化的方法与前面相同。算法改进的关键是引入了判决门限T，T的引入可以增加游程的长度，从而可以有效地提高压缩比。
基于小波变换的图像压缩算法
小波变换是世纪年代中期发展起来的一种时频域分析方法，由于小波及小波包技术可以将图像分层按小波基展开，所以可以根据图像信号的性质以及事先给定的处理要求确定展开的层数，因此不仅能有效地控制计算量、满足实时处理的要求，而且可以方便地实现累进传输编码。另外，利用小波变换具有放大、缩小和平移的数学显微镜功能，可以方便地产生各种分辨率的图像，适应不同分辨率的图像I/O设备和不同传输速率的通信系统。
一般情况下，对于静止的灰度图像，小波编码可以分成三个部分：小波变换、量化、编码，解码过程与编码过程完全相反。
简单的小波变换压缩
最简单的小波变换压缩便是只保留小波变换低频子带，重构时高频部分全部置零，然后进行反变换。图像像素间的相关性很强，小波分解后的高频分量的能量占整个图像能量的比例很低，因此舍去高频部分的能量对于重构图像的质量应该不会产生很大的影响。
改进的EZW算法
EZW编码的算法是将低频子带的系数包含在其中扫描的，而低频子带集中了图像的大部分能量，系数值较高，因此初始阈值的取值较高，为了提高重构图像的质量，不得不增加扫描的级数。改进的EZW算法可以抑制算法的这种缺点并满足图像压缩的近无损失真且尽量保留细节的要求。改进如下：

对低频系数进行单独的无损编码，因为低频系数所占的比例不大，但同时又包含了图像的大部分能量，所以对低频系数进行无损编码可以大大改善图像的质量。
提取高频系数中的边缘信息，将其保护起来，不作量化。因为边缘和轮廓等细节信息正可能是图像的价值所在。

Reference
哈夫曼编码
算术编码
LZW编码
小波变换

实验名称：英文文本的Huffman编码压缩
一、实验目的和要求
了解Huffman编码的特点，掌握Huffman编码基本原理及编码算法的设计与程序实现。
二、实验内容和原理
以任意选择一个纯英文文本为数据，设计出Huffman编码的压缩和解压缩算法，并写出程序予以实现。
霍夫曼(Huffman)编码是一种统计编码，属于无损压缩编码。
霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。
三、实验环境
硬件：计算机
软件：Windows 2000和MATLAB编程环境。
四、算法描述及实验步骤
(1)输入一串字符串x=s，即s=hmmyyjhjjgjjpqw，k为其长度，分别用a、b两个数组来表示字符串中出现的不同字母及其出现的个数，调用findstr函数进行统计。
(2)调用Huffmandict函数，即[dict,avglen]=huffmandict(c,d)，使用数组C及其概率数组d进行Huffman编码,编码后产生一个编码词典dict,以及平均码长avglen。
(3)调用huffmanenco函数，即sig_encoded =
huffmanenco(x,dict)，利用上面Huffmandict函数中产生的编码词典dict对sig_encoded来解码,其结果存放在dsig中以及dsig=huffmandeco(sig_encoded,dict)。
(4)代码如下所示：
clear;
x=input('输入一串字符串','s');
k=length(x);
t1=1;
a(t1:k)=0;
b(t1:k)=0;
for i=1 :k
kk=findstr(a,x(i));
if
isempty(kk)
a(t1)=x(i);
b(t1)=b(t1)+1;
t1=t1+1;
else
t2=kk(1);
b(t2)=b(t2)+1;
end
end
for i=1:t1-1
c(i)=a(i);
d(i)=b(i)/k;
end
[dict,avglen] = huffmandict(c,d)
sig_encoded = huffmanenco(x,dict)
dsig=huffmandeco(sig_encoded,dict)
s=char(dsig)
五、调试过程
六、实验结果
(1)输入的字符串以及所得编码词典dict和平均长度avglen：
(2)运行后所得sig_encoded数据：
(3)解码结果dsig数据(最后得到的字符串与输入的字符串一致)：
七、总结
通过这次英文文本的Huffman编码压缩的实验，使我对霍夫曼(Huffman)编码、解码有了更进一步的了解，也知道了Huffman编码的一些函数的调用及其功能，如：huffmanenco函数、Huffmandict函数、Huffmandeco函数等；也对Matlab有了更进一步的了解。

原网址：http://www.cnblogs.com/xudong-bupt/p/3761417.html

基于统计的压缩算法：游程编码

1.游程编码概念

　　游程编码又称“运行长度编码”或“行程编码”，是一种统计编码，该编码属于无损压缩编码。

2.基本原理

　　用一个符号值和串长代替具有相同值的连续符号，使符号长度少于原始数据的长度。

　　如：　　   原始文本：dfffffeeeeettttrrrrttttt

　　　　游程编码后文本：d1f5e5t4r4t5

 3.代码示例



 1 #include <stdio.h>
 2 #include <string.h>
 3 int main()
 4 {
 5     char textBefore[100] ="dfffffeeeeettttrrrrttttt";
 6     char textAfter[100];
 7     memset(textAfter,0,sizeof(textAfter));
 8 
 9     char c;
10     int num,i,j;
11     for(i=0;i<strlen(textBefore);){
12         c   = textBefore[i];    ///临时保存字符
13         num = 1;    ///保存个数
14         for(j=i+1;j<strlen(textBefore);j++){
15             if(c == textBefore[j])
16                 num++;
17             else
18                 break;
19         }
20         i = j;
21 
22         sprintf(textAfter,"%s%c",textAfter,c);
23         sprintf(textAfter,"%s%d",textAfter,num);
24     }
25     printf("textBefore : %s\n",textBefore);
26     printf("textAfter  : %s\n",textAfter);
27     return  0;
28 }



代码输出：

　　

 

参考：

http://zh.wikipedia.org/wiki/%E6%B8%B8%E7%A8%8B%E7%BC%96%E7%A0%81

http://baike.baidu.com/view/721796.htm?fr=aladdin

压缩算法分为两种：无损压缩算法和有损压缩算法。其中我们需要关注的是无损压缩算法。无损压缩算法又可以分为两大类：熵编码和字典编码。
其中属于熵编码的压缩算法有：
1. Unary coding
2. Atithmetic coding
3. Golomb coding
4. Huffman coding
5. Adaptive Huffman coding
6. Shannon-fano coding
7. Range coding
8. Tunstall coding
 
属于词典编码的压缩算法有：
1. Byte pair encoding
2. DEFLATE
3. Run-length encoding
4. L-Z系列算法(LZ77/LZ78/LZSS/LZW/LZMA/LZO)
 
另外，还有一些可能在压缩算法中使用的方法/技术
1. BWT (Burrows-Wheeler transform)
2. CTW (Context tree weighting)
3. Delt (Delta encoding)
4. DMC (Dynamic Markov compression)
5. MTF (Move-to-front transform)
6. PPM (Prediction by partial matching)