动态规划---图像压缩

在算法课上遇到这个图像压缩这个问题，可以用 动态规划来求解，之前没有遇到过这个问题，在网上查找相关的题解也比较少，就写一下自己的理解。

问题描述

	一幅图像的由很多个像素点构成，像素点越多分辨率越高，像素的灰度值范围为0~255，
也就是需要8bit来存储一个像素的灰度值信息。
	一幅由n*m像素点构成的图像，所需存储空间大小为：n*m*8bit=8nmbit(这是非常大的，直接传输很慢)
	
	然而，正常情况下，一幅图像的某一范围内像素点的灰度值是很接近的，表现为一幅图片某一区域颜色相近。
	例如，一个像素灰度值序列P={1,2,2,2,1,2,60,55,78}(传输过程中把图像像素点转成序列，
而不是直接传输矩阵)，每个像素灰度值都用8bit来存储是非常消耗空间的，例如：
直接存储: 9*8bit=72bit，这是非常不划算的，我们想要无损压缩图片。

	即：
	将像素序列分段，段内的像素灰度值相似(可以用小于8bit的空间来存储一个像素灰度值)，
一段内的像素用相同的bit数来存储，只需要额外存树每段的长度和bit数即可，这样可以节省很多空间。
1
2
3
4
5
6
7
8
9
10
11
12

b[i]:第i段中每个像素的位数，1<=b[i]<=8，需要3 bit
l[i];第i段中像素的个数，1<=l[i]<=255,需要8 bit
所以每一段需要额外的 3+8=11 bit来存储段内像素的信息
1
2
3

分析

如何分段?
$$若分为m段，则需要的存储总位数为:\sum _{i=1}^{m}b[i]\ast l[i]+m\ast 11$$
考虑用动态对规划来求解问题：
$$\begin{gathered} 最优子结构: \\ p1,p2,p3,....pm \\ 考虑最后一个分段为l[m]个元素 \\ {p}_{n-l[m]+1}\sim p[n], \\ 则子问题为p_1\sim p[l[m]]的分段(前m-1段) \\ 子问题的最优解为b[i],l[i],1<=i<=m-1 \\ 最后一个分段最优和前m-1个分段最优构成了原问题分段最优，最优子结构存在 \\ 在求解第i段过程中需要前i-1段分法的信息，存在重复子问题可以用动态规划的思想来求解问题 \end{gathered}$$

状态表示:
f[i]表示以A[i](包含)结尾的最优分段所需的bit数(最少)

状态转移:
f[i] =A[i-k]+bitmax(i-k+1,i)+11 , 0<=k<=i
bitmax(i-k+1,i)为求i-k+1到i这个序列每个像素灰度值需要的的bit数
其中,k<=256（图像压缩的限制）
f[i] =A[i-k]+bitmax(i-k+1,i)+11 , 0<=k<=min(i,256)
1
2
3
4
5
6
7
8

时间复杂度分析:
遍历序列n，
遍历(i-k+1,i)
求bitmax(i-k+1,i)
时间复杂度看起来是O(n^3)
但是k<=256，所以时间复杂度为O(n) (n前常数会比较大)

代码如下

#include
#include
#include
#include
#include
using namespace std;
const int N=1e5+10;
const int inf=0x3f3f3f3f;

int f[N];
int A[N];
int l[N],b[N];
int maxbit(int x){//求某个数存储需要的bit位数
    if(x==0) return 1;
    int res=0;
    while(x){
        x/=2;
        res++;
    }
    return res;
}
int get_maxbit(int l,int r){//求某一区间(区间最大值)需要的bit位数
    int res=0;
    for(int i=l;i<=r;i++) res=max(res,A[i]);
    
    return maxbit(res);
}

int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d",&A[i]);
	
	for(int i=1;i<=n;i++){
	    f[i]=f[i-1]+maxbit(A[i])+11;//假设A[i]单独构成一段,作为初始情况
	    b[i]=maxbit(A[i]);
	    l[i]=1;
	    for(int j=2;j<=min(i,256);j++){//从i-1到j+1遍历取min(f[i])
	        int bit_j=get_maxbit(i-j+1,i);
	        int t=f[i-j]+bit_j*j+11;
	        if(f[i]>t){
	            f[i]=t;
	            b[i]=bit_j;//记录该段需要的bit位
	            l[i]=j;//记录该段的长度
	        }
	    }
	}
	int t=n;
	vector<int>v;
	while(t){
	       v.push_back(l[t]);//将长度信息用vector存储
	       t=t-l[t];
	}
	reverse(v.begin(),v.end());//倒置
	printf("最少需要:%dbit\n",f[n]);
    for(int i=0,t=1;i<v.size();i++){//输出分段信息
        for(int j=0;j<v[i];j++)
            printf("%d ",A[t++]);
        printf("长%d,每个像素需要%dbit\n",l[t-1],b[t-1]);
    }
    return 0;
}
/*
12
10 12 15 255 1 2 1 1 2 2 1 1
#69
/*
/*
6
10 12 15 255 1 2
#57
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

运行结果如下

结果一

结果二

感觉这道题讲的重心错了，应该重点讲解动态规划的，比较少见的动态规划题