【计算机算法设计与分析】图像压缩问题（C++_动态规划）

问题描述

在计算机中常用像素点灰度值序列 { p 1 , p 2 , . . . , p n } \{ p_1, p_2, ..., p_n \} {p1?,p2?,...,pn?}表示图像。其中整数$p_i(1\le i\le n)$，表示像素点i的灰度值。通常灰度值的范围是0~255。因此，需要用8位表示一个像素。

图像的变位压缩存储格式将所给的像素点序列 { p 1 , p 2 , . . . , p n } \{ p_1, p_2, ..., p_n \} {p1?,p2?,...,pn?}分割成m个连续段$S_1,S_2,...,S_m$，第i个像素段$S_i(1\le i\le m)$中，有I[i]个像素，且该段中每个像素都只用b[i]位表示。设$t[i]={\sum }_{k=1}^{i?1}(1\le i\le m)$，则第i个像素段$S_i$为
S i = { p t [ i ] + 1 , . . . , p t [ i ] + l [ i ] } ????????????? ( 1 ≤ i ≤ m ) S_i=\{ p_{t[i]+1}, ..., p_{t[i]+l[i]} \} \ \ \ \ \ \ \ \ \ \ \ \ \ (1\leq i\leq m) Si?={pt[i]+1?,...,pt[i]+l[i]?}?????????????(1≤i≤m)

设$h_i=?log(ma{x}_{t[i]+1\le k\le t[i]+l[i]}{p}_k+1)?$，则$h_i\le b[i]\le 8$，需要用3位表示$b[i](1\le i\le m)$。如果限制$1\le l[i]\le 255$，则需要用8位表示$l[i](1\le i\le m)$。因此第i个像素段所需的存储空间为$l[i]?b[i]+11$位。按此格式存储像素序列 { p 1 , p 2 , . . . , p n } \{ p_1, p_2, ..., p_n \} {p1?,p2?,...,pn?}，需要${\sum }_{i=1}^{m}l[i]\times b[i]+11m$位的存储空间。

图像压缩问题要求确定像素序列 { p 1 , p 2 , . . . , p n } \{ p_1, p_2, ..., p_n \} {p1?,p2?,...,pn?}的最优分段，使得依此分段所需的存储空间最小。其中，$1\le p_i\le 255$，$1\le i\le n$，每个分段的长度不超过256位。

举例：
有一组数据 { 10 , 9 , 12 , 40 , 50 , 35 , 15 , 12 , 8 , 10 , 9 , 15 , 11 , 130 , 160 , 240 } \{10, 9, 12, 40, 50, 35, 15, 12, 8, 10, 9, 15, 11, 130, 160, 240\} {10,9,12,40,50,35,15,12,8,10,9,15,11,130,160,240}
对应的存储位数为 { 4 , 4 , 4 , 6 , 6 , 6 , 4 , 4 , 4 , 4 , 4 , 4 , 4 , 8 , 8 , 8 } \{4, 4, 4, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 8, 8, 8\} {4,4,4,6,6,6,4,4,4,4,4,4,4,8,8,8}
我们能想到的最简单的划分是：$4?3+6?3+4?7+8?3+4?11=126bit$
最优划分为：$6?6+4?7+8?3+3?11=121bit$
最优化分所占用的存储是更少的。

算法原理

这道题是满足最优子结构的，因此采用动态规划算法。
算法中的四个数组分别是：

• p[i]：第i个像素的数据。
• b[i]：第i个像素的存储长度。
• S[i]：S[i]为前i个段最优合并的总存储位数。
• l[i]：l[i]表示第i点的前l[i]个像素点为一组。

动态规划的过程中不断更新S数组，保证前i个段的最优合并的总存储位数最小，状态转移方程如下：
S [ i ] = m i n 1 ≤ k ≤ m i n { i , 256 } { S [ i ? k ] + k ? b m a x ( i ? k + 1 , i ) } + 11 S[i]=min_{1\leq k \leq min\{ i, 256\}}\{ S[i-k]+k*bmax(i-k+1, i) \}+11 S[i]=min1≤k≤min{i,256}?{S[i?k]+k?bmax(i?k+1,i)}+11

其中， b m a x ( i , j ) = ? l o g ( m a x i ≤ k ≤ j { p k } + 1 ) ? bmax(i, j)=\lceil log(max_{i\leq k \leq j}\{ p_k\}+1) \rceil bmax(i,j)=?log(maxi≤k≤j?{pk?}+1)?。

bmax函数的意思就是找出i到j之间最大的b[k]，也即是 b m a x ( i , j ) = m a x { b [ i ] , b [ i + 1 ] , . . . , b [ j ] } bmax(i, j)=max\{ b[i], b[i+1], ..., b[j]\} bmax(i,j)=max{b[i],b[i+1],...,b[j]}。

状态转移方程更新的过程简单来说就是：在每次加入新像素点的时候从后往前去试，把新像素和前几个像素放在一起可以使总体的存储位数最少。

状态转移方程的含义是后k个像素点为一组，这k个像素点都按照最多存储长度来算，也就是$k\times bmax(i?k+1,i)$。除去这k个像素点以外，前面的划分由于其满足最优子结构，还按照原本的来，即$S[i?k]$。由于多分了一组，新的组需要附加像素点数目l[i]的8位和最大像素存储长度 b m a x ( i , j ) = m a x { b [ i ] , b [ i + 1 ] , . . . , b [ j ] } bmax(i, j)=max\{ b[i], b[i+1], ..., b[j]\} bmax(i,j)=max{b[i],b[i+1],...,b[j]}的3位信息，所以要再加11位。

算法实现

#include<bits/stdc++.h>
#define VLength 100 
#define LMAX 256
#define HEADER 11
using namespace std;

int length(int x) {  //计算数据存储位数
	int num = 0;
	while (x / 2.0>=1) {
		x = x / 2.0;
		num++;
	}
	if (x > 0)
		num++;
	return num;
}
void compress(int n, int S[], int l[], int b[], int P[]) {//更新S[i]为前i个段最优合并的存储位数
	S[0] = 0;
	for (int i = 1; i <= n; i++) {//遍历每一个像素点
		//每个新的像素点单独成段
		b[i] = length(P[i]);//更新第i位的像素位数
		int bmax = b[i];
		S[i] = S[i - 1] + bmax;
		l[i] = 1;
		for (int j = 2; j <= i && j <= LMAX; j++) {//倒序遍历分段长度，j=2表示后俩点为一组
			bmax = bmax > b[i - j + 1] ? bmax : b[i - j + 1];//前i个像素的后j个像素的最大像素位数
			if (S[i] > S[i - j] + j * bmax) {//后j个像素一组的分组方法更优
				S[i] = S[i - j] + j * bmax;
				l[i] = j; //前i个像素的后j个像素为一组
			}

		}
		S[i] += HEADER;//新分了组那就要加上附加信息11位
	}
}
void IC() {
	int n;//像素点数目
	int P[VLength];//像素点
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> P[i];
	int S[VLength], l[VLength], b[VLength];//S[i]为前i个段最优合并的存储位数，l[i]表示第i点的前l[i]个像素点为一组，b[i]为第i个像素的存储长度
	compress(n, S, l, b, P);
	int temp = n;
	stack<int> Length, beginP;//记录分段长度和分段起始位置(使用栈把倒序转为正序)
	while (temp) {
		//最优分段的最后一段的段长度和像素位数分别存储于l[n], b[n]中,前一段的段长度和像素位数存储于l[n - l[n]]和 b[n - l[n]]中.
		Length.push(l[temp]);
		beginP.push(temp - l[temp] + 1);
		temp -= l[temp];
	}
	cout << "共分：" << Length.size() << "段" << endl;
	while (Length.size()) {
		cout << "段起始位置：" << beginP.top() << " ";
		cout << "段长度：" << Length.top() << " ";
		int bmax = INT_MIN;
		for (int i = 0; i < Length.top(); i++) //确定每个分段中最大的存储位数
			bmax = bmax > b[beginP.top() + Length.top() - 1] ? bmax : b[beginP.top() + Length.top() - 1];
		cout << "存储位数：" << bmax << endl;
		Length.pop();
		beginP.pop();
	}
}
/*
测试数据：
6
10 12 15 255 1 2
16
10 9 12 40 50 35 15 12 8 10 9 15 11 130 160 240
*/

参考资料

1. 3.7动态规划–图像压缩
2. 2022春浙江工业大学算法设计与分析习题分享—图像压缩