動態規劃--圖形壓縮 - acm1314－IT工程師數位筆記本

文章出處

1、問題描述：

在計算機中，常用像素點的灰度值序列{p1,p1,……pn}表示圖像。其中整數pi,1<=i<=n，表示像素點i的灰度值。通常灰度值的范圍是0~255。因此最多需要8位表示一個像素。

壓縮的原理就是把序列{p1,p1,……pn}進行設斷點，將其分割成一段一段的。分段的過程就是要找出斷點，讓一段里面的像素的最大灰度值比較小，那么這一段像素(本來需要8位)就可以用較少的位(比如7位)來表示，從而減少存儲空間。

b代表bits,l代表length,分段是，b[i]表示每段一個像素點需要的最少存儲空間(少于8位才有意義)，l[i]表示每段里面有多少個像素點，s[i]表示從0到i壓縮為一共占多少存儲空間。

如果限制l[i]<=255,則需要8位來表示l[i]。而b[i]<=8，需要3位表示b[i]。所以每段所需的存儲空間為l[i]*b[i]+11位。假設將原圖像分成m段，那么需要位的存儲空間。

圖像壓縮問題就是要確定像素序列{p1,p1,……pn}的最優分段，使得依此分段所需的存儲空間最小。

2、最優子結構性質

設l[i],b[i],1<=i<=m是{p1,p1,……pn}的一個最優分段，則l[1],b[1]是{p1,……,pl[1]}的一個最優分段，且l[i],b[i],2<=i<=m是{pl[1]+1,……,pn}的一個最優分段。即圖像壓縮問題滿足最優子結構性質。

3、遞推關系

設s[i],1<=i<=n是像素序列{p1,p1,……pi}的最優分段所需的存儲位數，則s[i]為前i-k個的存儲位數加上后k個的存儲空間。由最優子結構性質可得：

，式中

4、構造最優解

數組l[i],b[i]記錄了最優分段所需的信息最優分段的最后一段的段長度和像素位數分別存儲在l[n]和b[n]中,其前一段的段長度和像素位數存儲于l[n-l[n]]和b[n-l[n]]中，依此類推，可在O(n)時間內構造最優解。

摘自：http://blog.csdn.net/liufeng_king/article/details/8648195

 1 int lmax = 256;
 2 int header = 11;
 3 int m;
 4 
 5 void compress(int p[], int s[], int t[], int b[])
 6 {
 7     int n = n.length - 1;
 8     s[0] = 0;
 9     for(int i=1; i<=n; i++)
10     {
11         b[i] = length(p[i]);
12         int bmax = b[i];
13         s[i] = s[i-1] + bmax;
14         l[i] = 1;
15         for(int j=2; j<=i&&j<=lmax; j++)
16         {
17             if(bmax<b[i-j+1]) bmax = b[i-j+1];
18             if(s[i]>s[i-j] + j*bmax)
19             {
20                 s[i] = s[i-j] + j*bmax;
21                 l[i] = j;
22             }
23         } 
24         s[i]+=header;
25     }
26 }
27 
28 int length(int i)
29 {
30     int k=1;
31     i=i/2;
32     while(i>0)
33     {
34         k++;
35         i/=2;
36     }
37     return k;
38 }

View Code

算法compress中用l[i]和b[i]記錄了最優分段所需的信息。最優分段的最后一段的段長度和像素位數分別存儲在l[n] 和 b[n]中。其前一段的段長度和像素位數存儲于l[n-l[n]]和b[n-l[n]]中。依次類推，由算法計算設計出的l和b可在O（n）的時間內構造出最優的最優解。

算法Compress只需O(n)空間。由于在算法Compress中j的循環次數不超過256,故對每一個確定的i可在O(1)時間內完成。因此整個算法的時間復雜度為O(n)。算法Compress的執行過程可以下圖表示：

 1 void taceback(int n int s[], int t[])
 2 {
 3     if(n==0) return;
 4     traceback(n-l[n], s, l);
 5     s[m++] = n - l[n];
 6 }
 7 
 8 void output(int s[], int l[], int b[])
 9 {
10     int n = s.length - 1;
11     printf("The optimal value is+%d", s[n]);
12     m = 0;
13     trackback(n, s, l);
14     s[m] = n;
15     printf("Decomposed into+%d+segments", m);
16     for(int j=1; j<=m; j++)
17     {
18         l[j] = l[s[j]];
19         b[j] = b[s[j]];
20     }
21     for(int j=1; j<=m; j++)
22     printf("%d + , + %d", l[j], b[j]);
23     
24 }