当前位置:   article > 正文

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

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 2^8 28)数字,而一个灰度值最多有8位( 2 3 2^3 23),所以我们可以用即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 ] s[i] s[i]来记录前 i 个数字的最优处理方式得到的最优解。
  • l [ i ] l[i] l[i]中来记录当前第 i 个数所在组中有多少个数。
  • b [ i ] b[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;  
    }  
}  
  • 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
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小惠珠哦/article/detail/819373
推荐阅读
相关标签
  

闽ICP备14008679号