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

2023-12-22 17:34:35

问题描述

在计算机中常用像素点灰度值序列 { p 1 , p 2 , . . . , p n } \{ p_1, p_2, ..., p_n \} {p1?,p2?,...,pn?}表示图像。其中整数 p i ( 1 ≤ i ≤ n ) p_i(1\leq i \leq n) pi?(1in),表示像素点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 S_1, S_2,..., S_m S1?,S2?,...,Sm?,第i个像素段 S i ( 1 ≤ i ≤ m ) S_i(1\leq i\leq m) Si?(1im)中,有I[i]个像素,且该段中每个像素都只用b[i]位表示。设 t [ i ] = ∑ k = 1 i ? 1 ( 1 ≤ i ≤ m ) t[i]=\sum_{k=1}^{i-1} (1\leq i\leq m) t[i]=k=1i?1?(1im),则第i个像素段 S i S_i Si?
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]?}?????????????(1im)

h i = ? l o g ( m a x t [ i ] + 1 ≤ k ≤ t [ i ] + l [ i ] p k + 1 ) ? h_i=\lceil log(max_{t[i]+1\leq k \leq t[i]+l[i]}p_k+1)\rceil hi?=?log(maxt[i]+1kt[i]+l[i]?pk?+1)?,则 h i ≤ b [ i ] ≤ 8 h_i\leq b[i ]\leq 8 hi?b[i]8,需要用3位表示 b [ i ] ( 1 ≤ i ≤ m ) b[i] (1\leq i\leq m) b[i](1im)。如果限制 1 ≤ l [ i ] ≤ 255 1\leq l[i]\leq 255 1l[i]255,则需要用8位表示 l [ i ] ( 1 ≤ i ≤ m ) l[i] (1\leq i\leq m) l[i](1im)。因此第i个像素段所需的存储空间为 l [ i ] ? b [ i ] + 11 l[i]*b[i]+11 l[i]?b[i]+11位。按此格式存储像素序列 { p 1 , p 2 , . . . , p n } \{ p_1, p_2, ..., p_n \} {p1?,p2?,...,pn?},需要 ∑ i = 1 m l [ i ] × b [ i ] + 11 m \sum_{i=1}^{m}l[i]\times b[i]+11m i=1m?l[i]×b[i]+11m位的存储空间。

图像压缩问题要求确定像素序列 { p 1 , p 2 , . . . , p n } \{ p_1, p_2, ..., p_n \} {p1?,p2?,...,pn?}的最优分段,使得依此分段所需的存储空间最小。其中, 1 ≤ p i ≤ 255 1\leq p_i\leq 255 1pi?255 1 ≤ i ≤ n 1\leq i\leq n 1in,每个分段的长度不超过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 = 126 ? b i t 4*3+6*3+4*7+8*3+4*11=126 \ bit 4?3+6?3+4?7+8?3+4?11=126?bit
最优划分为: 6 ? 6 + 4 ? 7 + 8 ? 3 + 3 ? 11 = 121 ? b i t 6*6+4*7+8*3+3*11=121\ 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 ] = 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]=min1kmin{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(maxikj?{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 × b m a x ( i ? k + 1 , i ) k\times bmax(i-k+1, i) k×bmax(i?k+1,i)。除去这k个像素点以外,前面的划分由于其满足最优子结构,还按照原本的来,即 S [ i ? k ] S[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春浙江工业大学算法设计与分析习题分享—图像压缩

文章来源:https://blog.csdn.net/qq_43510916/article/details/135135480
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。