我们在计算机中国通常是使用的像素点的灰度值序列{p1,p2,p3,p4,...,pn}表示图像。pi表示的是像素点i的灰度值。灰度值的范围是在0~255.因此，需要使用8位表示一个像素。

图像的压缩就是将所给的像素点序列{p1,p2,p3..}分割成为m个连续的段S1,S2,...Sm。

目标:图像压缩的问题就是要求确定像素序列{p1,p2,p3,...pn}的最优分段，使得依次分段所需的存储空间最少。0<=pi<=256,1<=i<=n。每个分段长度不超过256位。

最优子结构的性质，设L[i],B[i],1<=i<=m是{p1,p2,...pn}的最优分段。显而易见，L[1],B[1]是{p1,p2,....pn}的最优分段。图像压缩满足最优子结构的性质。

递归计算最优值

设S[i],1<=i<=n是像素序列{p1,...pn}的最优的分段所需要的存储位数。

压缩算法:

static final int lmax = 256;
static fianl int header = 11;
static int m;

public static void compress(int[] p,int[] s,int[] l,int[] b){

int n = p.length-1;
s[0] = 0;
for(int i = 1;i<=n;i++){
b[i] = length(p[i]);
int bmax = b[i];
s[i] = s[i-1] + bmax;
l[i] = 1;
for(int j = 2;j<=i&&j<=lma;j++){

if(bmax < b[i-j+1]) vmax = b[i-j+1];
if(s[i]>s[i-j]+j*bmax){
s[i] = s[i-j]+j*bmax;
l[i] = j;
}
}
s[i]+ = header;
}
}


private static int length(int i){

int k = 1;
i = i/2;
while(i>0){
k++;
i=i/2;
}
return k;
}

构造最优解

 

前面上个compress算法使用了l[i]和b[i]记录最优分段需要的信息。其实最优分段的最后一段的段长度和像素位数分别存储在l[n]和b[n]中。前一段的段长度和像素位存在l[n-l[n]]和b[n-l[n]中，所以构造最优解的算法如下:

private static void traceBack(int n int[] s,int[] l){

if(n==0)return;
traceBack(n-l[n],sl);
s[m++] = n-l[n];
}

public static void output(int[] s,int[] l,int[] b){


int n = s.length-1;
m = 0;
traceBack(n,s,l);
s[m] = n;

for(int j = 1;j<=m;j++){
l[j] = l[s[j]];
b[j] = b[s[j]];
}
}