【计算机算法设计与分析】图像压缩问题（C++

这篇具有很好参考价值的文章主要介绍了【计算机算法设计与分析】图像压缩问题（C++_动态规划）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

问题描述

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

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

设 $h_i=\lceil log(max_{t[i]+1\leq k \leq t[i]+l[i]}p_k+1)\rceil$ ，则 $h_i\leq b[i ]\leq 8$ ，需要用3位表示 $(1\leq i\leq m)$ 。如果限制 $1\leq l[i]\leq 255$ ，则需要用8位表示 $(1\leq i\leq m)$ 。因此第i个像素段所需的存储空间为 $l [i] * b [i] + 11$ 位。按此格式存储像素序列 ${ p_1, p_2, ..., p_n \}$ ，需要 $\sum_{i=1}^{m}l[i]\times b[i]+11m$ 位的存储空间。

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

举例：
有一组数据 ${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\}$
我们能想到的最简单的划分是： $\ bit$
最优划分为： $6*6+4*7+8*3+3*11=121\ bit$
最优化分所占用的存储是更少的。

算法原理

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

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

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

其中， $j)=\lceil log(max_{i\leq k \leq j}\{ p_k\}+1) \rceil$ 。

bmax函数的意思就是找出i到j之间最大的b[k]，也即是 $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位和最大像素存储长度 $bmax(i, j)=max\{ b[i], b[i+1], ..., b[j]\}$ 的3位信息，所以要再加11位。文章来源地址https://www.toymoban.com/news/detail-768664.html

算法实现

#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
*/