计算机算法分析与设计（8）---图像压缩动态规划算法(含C++)代码

---

一、知识概述

1.1 问题描述

 1. 一幅图像的由很多个像素点构成，像素点越多分辨率越高，像素的灰度值范围为0~255，也就是需要8bit来存储一个像素的灰度值信息。

注意：在灰度图像中，全0表示黑色，全1表示白色。

 2. 一幅由n×m像素点构成的图像，所需存储空间大小为：n×m×8bit=8nmbit(这是非常大的，直接传输很慢)。这个时候大家应该有了一些小的疑问：我能不能用更少的位数来表示灰度值？（因为有的灰度值并没有达到255这么大）所以我们引入了图像压缩算法来解决这个问题。

1.2 算法思想

 1. 图像压缩：将像素序列分段，段内的像素灰度值相似(可以用小于8bit的空间来存储一个像素灰度值)，一段内的像素用相同的bit数来存储，只需要额外存储每段的长度和bit数即可，这样可以节省很多空间。

 2. 但是分组会带来一个新的问题：我如何表示当前组中像素的个数和像素的位数呢？
 这里我们引入两个固定位数的值来表示：①我们用3位数字来表示当前组的每一位像素的的bit位数。②我们引入8位数字来表示当前组中像素点的个数。
 因为我们在这里规定了一组中最多存储0~255个（$2^8$）数字，而一个灰度值最多有8位（$2^3$），所以我们可以用即3位数字来表示当前组的像素位数（注意这里都是二进制）。

1.3 算法设计

 1. {6, 5, 7, 5, 245, 180, 28, 28, 19, 22, 25, 20}这是一组灰度值序列。我们按照默认的存储方法来看，一共12个数字，所以12×8=96位来表示。

 2. 而下面我们将其进行分组：第一组4个数，最大是7所以用3位表示；第二组2个数，最大是245所以用8位表示；第三组6个数，最大是28所以用5位表示。这个时候，我们最后得到了最后的位数结果为：4×3+2×8+6×5+11×3=91。

 3. 压缩过程中的数组存储：

• $s[i]$来记录前 i 个数字的最优处理方式得到的最优解。
• $l[i]$中来记录当前第 i 个数所在组中有多少个数。
• $b[i]$中存放前 i 个像素点最后一段位数的最大值。

 4. 递推关系式：

1.4 例题分析

二、代码

#include <iostream>   
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};//图像灰度数组 下标从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[])  
{  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++)  {  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) //i表示p数组中元素的值 
{  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);  s[i++]=n-l[n];//重新为s[]数组赋值，用来存储分段位置  
}  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[m] = 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;  }  
}