动态规划---图像压缩

1、问题描述：

     在计算机中，常用像素点的灰度值序列{p1,p1,……pn}表示图像。其中整数pi,1<=i<=n，表示像素点i的灰度值。通常灰度值的范围是0~255。因此最多需要8位表示一个像素。

      压缩的原理就是把序列{p1,p1,……pn}进行设断点，将其分割成一段一段的。分段的过程就是要找出断点，让一段里面的像素的最大灰度值比较小，那么这一段像素(本来需要8位)就可以用较少的位(比如7位)来表示，从而减少存储空间。

     b代表bits,l代表length

    b[i]：第i个像素段的每个像素点占b[i]个位数 (少于8位才有意义)，

     l[i]：第i个像素段里面有多少个像素点，

    s[i]：像素序列{p1,p2,...,pi}的最优分段所需的存储位数

     如果限制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]为 S[i]=S[i-1]+1*log(Pi)+11 或 S[i]=S[i-2]+2*log(max(Pi-1,Pi))+11 或S[i]=S[i-3]=log(max(Pi,Pi-1,Pi-2))+11… 或S[i]=S[0]+i*log(max(Pi,Pi-1…,P1))+11中的最小值，可归纳为下面式子：

则s[i]为前i-k个的存储位数加上后k个的存储空间。由最优子结构性质可得：

，式中

这里，S[i]的计算求解可采用k从1开始，一直到i或256其中之一，因为这是在固定的长度段中，从Pi开始，依次进行比较，找到最小的存储位。在计算时，我们可以先求S[1],再求S[2],S[2]中就可以用到S[1],之后求S[3]，可以用到S[1],S[2],S[3],依次类推，就满足了动态规划的要用重叠子问题。 

S[0]=0

         4、构造最优解

     由于根据设计的求最小存储位的算法，数组l[i],b[i]记录了最优分段所需的信息，假设求P1…Pn的最优分段，因为算法求的最优分段是从Pn，依次向前比较直到P1，找到最小的存储位和最优的断点，然后记录在l[n]中，因此，最优分段的最后一段的段长度和像素位数分别存储在l[n]和b[n]中,其前一段的段长度和像素位数存储于l[n-l[n]]和b[n-l[n]]中，依此类推，可在O(n)时间内构造最优解。

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
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
const int N = 7;
int length(int i);
void Compress(int n,int p[],int s[],int l[],int b[]);
void Tracebace(int n,int& i,int s[],int l[]);
void Output(int s[],int l[],int b[],int n);
int main()
{
int p[] = {0,10,12,15,255,1,2};//图像灰度数组{p1,p2,p3,p4,p5,p6} 下标从1开始计数
int s[N],l[N],b[N];
cout<<"图像的灰度序列为："<<endl;
for(int i=1;i<N;i++)
cout<<p[i]<<" ";
cout<<endl;
Compress(N-1,p,s,l,b);
Output(s,l,b,N-1);
return 0;
}
void Compress(int n,int p[],int s[],int l[],int b[])
{//n个像素，存在数组p[]中，
int Lmax = 256,header = 11;
s[0] = 0;
for(int i=1; i<=n; i++)
{
b[i] = length(p[i]);//计算像素点p需要的存储位数
int bmax = b[i];
s[i] = s[i-1] + bmax;
l[i] = 1;
for(int j=2; j<=i && j<=Lmax;j++)//i=1时，不进入此循环
{
if(bmax<b[i-j+1])
{
bmax = 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;
}
}
int length(int i)//存储像素pi所需的位数
{
int k=1;
i = i/2;
while(i>0)
{
k++;
i=i/2;
}
return k;
}
void Traceback(int n,int& i,int s[],int l[])
{
if(n==0)
return;
Traceback(n-l[n],i,s,l);//p1,p2,p3,...,p(n-l[n])像素序列，最后一段有l[n]个像素
s[i++]=n-l[n];//重新为s[]数组赋值，用来存储分段位置，最终i为共分了多少段
}
void Output(int s[],int l[],int b[],int n)
{
//在输出s[n]存储位数后，s[]数组则被重新赋值，用来存储分段的位置
cout<<"图像压缩后的最小空间为："<<s[n]<<endl;
int m = 0;
Traceback(n,m,s,l);//s[0]:第一段从哪分，s[1]:第二段从哪分...，s[m-1]第m段从哪分
s[m] = n;//此时m为总段数，设s[m]=n，分割位置为第n个像素
cout<<"将原灰度序列分成"<<m<<"段序列段"<<endl;
for(int j=1; j<=m; j++)
{
l[j] = l[s[j]];
b[j] = b[s[j]];
}
for(int j=1; j<=m; j++)
{
cout<<"段长度："<<l[j]<<",所需存储位数:"<<b[j]<<endl;
}
}

 算法Compress只需O(n)空间。由于在算法Compress中j的循环次数不超过256,故对每一个确定的i可在O(1)时间内完成。因此整个算法的时间复杂度为O(n)。算法Compress的执行过程可以下图表示：

      方法Output中，在输出s[n]的最小存储空间后，s[]数组被重新赋值，用来存储分段的位置，一边回溯构造最优解

---------------------------------------------------------------------我是有底线的-----------------------------------------------------------------------------

http://blog.csdn.net/liufeng_king/article/details/8648195

最后

以上就是漂亮篮球最近收集整理的关于动态规划---图像压缩的全部内容，更多相关动态规划---图像压缩内容请搜索靠谱客的其他文章。