图像压缩－－－动态规划

柔情只为你懂 2021-12-24 05:39 330阅读 0赞

全面的了解，看书《算法设计分析》曲婉婷  
网上看到的不满意，而且ＴraceBack的时候，采用的大都是递归。

--------------------

# 1 算法与思路描述 #

转载自：[动态规划之–图像压缩][Link 1]

## 1.1问题描述 ##

图像压缩的问题我们是这样理解的：大家都知道计算机的图像是用灰度值序列来表示的｛P1,P2…Pn｝,其中Pi表示像素点i的灰度值。而通常灰度值的范围是0~255，因此需要8位二进制数来表示一个像素。这个时候大家应该有了一些小的疑问：我能不能用更少的位数来表示灰度值？（因为有的灰度值并没有达到255这么大）所以我们引入了图像压缩算法来解决这个问题。

不过在引入问题之前，我要在这里介绍一些算法设计的知识——我们要将灰度值序列分组，而每一组中所有的数就有可能是<255的，所以我们就不需要用8位数字去表示像素大小了，但是分组会带来一个新的问题：我如何表示当前组中像素的个数和像素的位数呢（因为不是八位，所以要有一个数据来记录真正的位数）？这里我们引入两个固定位数的值来表示，①我们用3位数字来表示当前组的每一位像素的的位数②我们引入8来表示当前组中像素点的个数　　因为我们在这里规定了一组中最多存储–>0~255个数字，而一个灰度值最多有8位（2^3），所以我们可以用即3位数字来表示当前组的像素位数（注意这里都是二进制）

## 1.2算法设计 ##

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

而下面我们将其进行分组：  
![在这里插入图片描述][20190626195205816.png]这里我们将他们分为三组：

第一组4个数，最大是7所以用3位表示；

第二组2个数，最大是245所以用8位表示；

第三组6个数，最大是28所以用5位表示；

这个时候，我们最后得到了最后的位数结果为：4*3+2*8+6*5+11*3=91。是不是优化了？？

那我们算法应该怎么做来找最优的值呢？？  
下面我一步一步介绍。

压缩过程中的数组存储：  
既然是DP问题，所以我们肯定需要数组来记录每一步的最优值。这里我们用  
 S \[ n \] S\[n\] S\[n\]来记录前 i i i个数字的最优处理方式得到的最优解。  
 l \[ n \] l\[n\] l\[n\]中来记录第当前第i个数所在组中有多少个数。(因而只有每一组的最后一个 l \[ x \] l\[x\] l\[x\],存储有效)（这句话，暂时看不懂也没关系）  
 b \[ i \] b\[i\] b\[i\]中存第 i i i个数的像素位数。

下面我写出来具体的递推过程–>  
例题:　求像素序列4，6，5，7，129，138，1的最优分段。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_16_color_FFFFFF_t_70 1]在解体过程中，我们知道在我们求s\[3\]的时候，我们是分三种情况----

①前三个数为一组，这个时候我需要的存储位数是3(位数)\*3（每一组中数的个数）+11（每分一组所必须的固定位数）

②s\[1\]为单独一组，剩下的两个数字为一组，此时我所需要的空间为s\[1\]+2\*3+11

③前两个数字为一组，最后一个数为一组。此时我们要用s\[2\]（前面已经计算出的最优值）+3\*1+11

然后比较三个数的大小，取最小的那一种分组情况，然后记下l\[3\]=3（当前最优分组中是三个数在同一组中），b\[3\]=3（每一个像素所用的存储位数）。

递归到最后得到最优解为　　58.

压缩部分代码：

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 + header;  
            l[i] = 1;  
      
            for(int j=2; j<=i && j<=Lmax;j++)  //最后一段含有一个像素，两个像素，所有像素
            {  
                //if(bmax<b[i-j+1])   //最后一个b[i-j+1]有效，是前一段当中的最大值，并不是后一段中的最大值
                if(bmax<length(p[i-j+1])) 
                {  
                    bmax = length(p[i-j+1]);  
                }  
      
                if(s[i]>s[i-j]+j*bmax+header)  
                {  
                    s[i] = s[i-j] + j*bmax+header;  
                    l[i] = j;  
                    b[i] = bmax;  //我加，跟新当前组，所需的存储位数
                }  
            }  
        }  
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_16_color_FFFFFF_t_70 2][]  
(这张图，来自算法书上，不好看，从后向前，利用数据)  
知道压缩代码之后，需要知道具体的分段信息：追踪解的过程。  
（每一个分组中，只有该分组对应的最后一个 l \[ i \] l\[i\] l\[i\]，有效。因为是从后向前）  
伪代码

Traceback(n,l)
    j<---1
    while n!=0 do
    	c[j]<---l[n]
    	n<---n-l[n]
    	j<---j+1

下面的代码，用栈的方式处理了这种思路。

# ２代码实现 #

## 图片压缩代码一 ##

//代码参考：https://www.cnblogs.com/caiyishuai/p/8876077.html 
    //dacao 2019/6/25
    #include<iostream> 
    #include<cmath>  
    #include<stack>
    using namespace std;   
      
    const int N = 7;  
      
    int length(int i);  
    void Compress(int n,int p[],int s[],int l[],int b[]);  
    int TraceBack(int n,int l[],int b[]);  //返回有多少个段
    void Out(int m,int min_len,int l[],int b[]);
      
    int main()  
    {  
        //int p[] = {0,10,12,15,255,1,2};//图像灰度数组 下标从1开始计数  
          int p[] = {0,255,1,5,2,1,2};
        int s[N]={0},l[N]={0},b[N]={0};  
      
        cout<<"图像的灰度序列为："<<endl;  
      
        for(int i=1;i<N;i++)  
        {  
            cout<<p[i]<<" ";  
        }  
        cout<<endl;  
      
        Compress(N-1,p,s,l,b);  
        int m=TraceBack(N-1,l,b); 
        Out(m,s[N-1],l,b);
        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 + header;  
            l[i] = 1;  
      
            for(int j=2; j<=i && j<=Lmax;j++)  //最后一段含有一个像素，两个像素，所有像素
            {  
                //if(bmax<b[i-j+1])   //最后一个b[i-j+1]有效，是前一段当中的最大值，并不是后一段中的最大值
                if(bmax<length(p[i-j+1])) 
                {  
                    bmax = length(p[i-j+1]);  
                }  
      
                if(s[i]>s[i-j]+j*bmax+header)  
                {  
                    s[i] = s[i-j] + j*bmax+header;  
                    l[i] = j;  
                    b[i] = bmax;  //我加，跟新当前组，所需的存储位数
                }  
            }  
        }  
    }  
      
    int length(int i)  
    {   
        int k=1;  
        i = i/2;  
        while(i>0)  
        {  
            k++;  
            i=i/2;  
        }  
        return k;
       //return ceil(log(i+1)/log(2));  
    }  
    
    int TraceBack(int n,int l[],int b[]) //从后向前检查，因而之后对应段的，最后一个存储有效
    {
        stack<int>ss;
        ss.push(l[n]);
        ss.push(b[n]);
        while (n!=0)
        {
            n=n-l[n];
            ss.push(l[n]);  //l[0]=0,也被压入栈中
            ss.push(b[n]);
        }
        int i=0;
        while (!ss.empty())
        {
            b[i]=ss.top();
            ss.pop(); 
            l[i]=ss.top(); //此时　ｌ[]，用来存储，第ｉ组中，元素个数
            ss.pop();
            i++;
        }
        return i-1;
    }
    
    void Out(int m,int min_len,int l[],int b[])
    {
        int i=0;
        cout<<"最小长度："<<min_len<<endl;
        cout<<"共分成："<<m<<"段"<<endl;
        for(i=i+1;i<=m;i++)
        {
            cout<<"第一个段含有"<<l[i]<<"元素.   "<<"需要存储位数"<<b[i]<<endl;
        }
    }

## 图片压缩代码二 ##

//代码参考：https://www.cnblogs.com/caiyishuai/p/8876077.html 
    //dacao 2019/6/25
    #include<iostream> 
    #include<cmath>  
    #include<stack>
    #include<algorithm>
    using namespace std;   
      
    const int N = 7;  
      
    int length(int i);  
    void Compress(int n,int p[],int s[],int l[],int b[]);  
    int TraceBack(int n,int l[],int b[]);  //返回有多少个段
    void Out(int m,int min_len,int l[],int b[]);
      
    int main()  
    {  
        //int p[] = {0,10,12,15,255,1,2};//图像灰度数组 下标从1开始计数  
          int p[] = {0,255,1,5,2,1,2};
        int s[N]={0},l[N]={0},b[N]={0};  
      
        cout<<"图像的灰度序列为："<<endl;  
      
        for(int i=1;i<N;i++)  
        {  
            cout<<p[i]<<" ";  
        }  
        cout<<endl;  
      
        Compress(N-1,p,s,l,b);  
        int m=TraceBack(N-1,l,b); 
        Out(m,s[N-1],l,b);
        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 + header;  
            l[i] = 1;  
      
            for(int j=2; j<=i && j<=Lmax;j++)  //最后一段含有一个像素，两个像素，所有像素
            {  
                //if(bmax<b[i-j+1])   //最后一个b[i-j+1]有效，是前一段当中的最大值，并不是后一段中的最大值
                if(bmax<b[i-j+1]) 
                {  
                    bmax = b[i-j+1];  
                }  
      
                if(s[i]>s[i-j]+j*bmax+header)  
                {  
                    s[i] = s[i-j] + j*bmax+header;  
                    l[i] = j;  
                    //b[i] = bmax;  //我加，跟新当前组，所需的存储位数
                }  
            }  
        }  
    }  
      
    int length(int i)  
    {   
        int k=1;  
        i = i/2;  
        while(i>0)  
        {  
            k++;  
            i=i/2;  
        }  
        return k;
       //return ceil(log(i+1)/log(2));  
    }  
    
    int TraceBack(int n,int l[],int b[]) //从后向前检查，因而之后对应段的，最后一个存储有效
    {
        stack<int>ss;
        ss.push(l[n]);
        //ss.push(b[n]);
        while (n!=0)      //此时　ｌ[]，用来存储，第ｉ组中，元素个数  
        {
            n=n-l[n];
            ss.push(l[n]);  //l[0]=0,也被压入栈中
            //ss.push(b[n]);
        }
        int i=0;
        while (!ss.empty())
        {
            //b[i]=ss.top();
            //ss.pop(); 
            l[i]=ss.top(); //此时　ｌ[]，用来存储，第ｉ组中，元素个数
            ss.pop();
            i++;
        }
        i--;
    
        int m=i;//共分成ｍ段
        for(i=1;i<=m;i++)
            b[i]=*max_element(b+i,b+i+l[i]);  // 此时　ｂ[],用来存储，第ｉ组中，元素所需的存储位数
        
        return m;
    }
    
    void Out(int m,int min_len,int l[],int b[])
    {
        int i=0;
        cout<<"最小长度："<<min_len<<endl;
        cout<<"共分成："<<m<<"段"<<endl;
        for(i=i+1;i<=m;i++)
        {
            cout<<"第一个段含有"<<l[i]<<"元素.   "<<"需要存储位数"<<b[i]<<endl;
        }
    }

结果图片：略

代码比较：这两个代码，大同小异。代码一：让 b \[ i \] b\[i\] b\[i\]和 l \[ i \] l\[i\] l\[i\]的作用相同。每一组对应的数组段中，只用最后一个存储有效。代码二：是常见的处理方式。代码一、二在追踪的时候，都采用了栈的方式，代替了递归。

参考文章：  
[动态规划之–图像压缩][Link 1]  
[0016算法笔记——【动态规划】图像压缩问题][0016]  
[0016算法笔记——【动态规划】图像压缩问题(同上)][0016 1]  
[介绍视频(未看)][Link 2]

如果看到更好的介绍文章，欢迎留言链接，多谢。

[Link 1]: https://blog.csdn.net/bingqingsuimeng/article/details/78675855
[20190626195205816.png]: /images/20211223/29b59f4c774543e5b5e706bf6f0963fd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_16_color_FFFFFF_t_70]: /images/20211223/9d68dcd39e6b47c9b64f0b18e0286a8a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190626195920584.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_16_color_FFFFFF_t_70 2]: /images/20211223/0736bdc04b104b1e8a9fda2f017560c6.png
[0016]: https://blog.csdn.net/huoyahuoya/article/details/53576853
[0016 1]: http://www.voidcn.com/article/p-vjjplokn-xr.html
[Link 2]: https://zh.coursera.org/lecture/algorithms/044tu-xiang-ya-suo-c2AAR