图片压缩算法--动态规划

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
95
96
97
#include <iostream>
#include <memory.h>

#define N 100

using namespace std;

int p[N+1] , s[N+1] , l[N+1] , b[N+1];//像素点集 ，每段所需长度 ，每段像素个数 ， 每段的像素点位数

/*-----------计算像素的位数*/
int length(int i)
{
        int k = 1;
        i = i/2;
        while(i > 0){
                k++;
                i = i/2;
        }
        return k;
}

/*------------动态规划--计算最优存储*/
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]);//---计算像素位数    例 ： 2 --->>10 所占位数为2位  1*2^1+0*2^0 = 2 , 256--->>10000000 所占位数为8位 1*2^8+0*2^7.....0*2^0 = 256
                int bmax = b[i];//初始化最大位数
                s[i] = s[i-1]+bmax;//初始化第i段所需空间
                l[i] = 1;//初始化第i段像素个数
                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){//如果按最大位数存储，从第i-j个到第i个所需存储空间小于原空间
                                s[i] = s[i-j]+j*bmax;
                                l[i] = j;
                        }
                }
                s[i] += header;//加入头 1<=l[i] <=256-->2^8  1<=b[i]<=8 -->2^3 所需存储空间为 8+3 = 11
        }
}

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]<<"t压缩存储位数："<<b[j]<<endl;
}

int main()
{
        int n;
        memset(s , 0 , sizeof(s));
        cout<<"请输入像素的个数："<<endl;
        cin>>n;
        cout<<"请输入 "<<n<<" 个像素点的像素"<<endl;

        for(int i = 1 ; i <= n ; i++)
                cin>>p[i];
        Compress(n , p , s , l , b);
        Output(s , l , b , n);

        return 0;
}
/*
请输入像素的个数：
6
请输入 6 个像素点的像素
10 12 15 255 1 2
压缩所需存储空间： 57
将原灰度段分成： 3 段存储。
段长度：3       压缩存储位数：4
段长度：1       压缩存储位数：8
段长度：2       压缩存储位数：2

Process returned 0 (0x0)   execution time : 18.252 s
Press any key to continue.

*/