概述
起因
前几天老师讲了下课本《计算机算法设计与分析》上的动态规划的一个问题，特地来这里实现下。
如果你提前知道了这个算法的背景，比如像素点啊，位长之类的概念，理解起来可能会比较好接受。
先将彩色图片转黑白图片，然后按顺序像个贪吃蛇一样来回走，扫描出灰度值之后，如何压缩的过程。
这个算法本身也有一定的难度，理解起来不太容易，不过按照定义直接推导也能实现出来，只是时间上的问题罢了。
说起来还有点好笑的事，老师代码上写了灰度值序列10,12,15,255,1,2，经过压缩后的最小空间为：57
擦，这比不压缩还大啊。
不过不用担心，在日常生活上，照片上有很多像素点是冗余的，所以完全不必要质疑这个算法。只不过是因为数据选取的不够好的原因。
代码方案和书上有所不同，但思路是相同的。
代码如下
#include <iostream>
#include <algorithm>
using namespace std;
#define LMAX 256
#define HEADER 11
/********************** Image_Compression ************************
/_____________________ 图像压缩 _____________________ */
// 函数声明
int getBLength(int i);
void printArray(int* array, int length);
int Compress(int* p, int length);
void output(int* Llength, int* BLength, int length);
int Compress(int* p, int length, int* L, int* B);
// main函数
int main() {
int p[] = { 0,10,9,12,40,50,35,15,12,8,10,9,15,11,130,160,240 }; //下标从1开始计数
int length = sizeof(p) / 4; // 求出数组长度
printArray(p, length); // 打印输入的 灰度值序列
// 输入L[i]和B[i]
int* Llength = new int[length]();//申请数组，下标从1开始计数
int* Blength = new int[length]();//申请数组，下标从1开始计数
cout << "该灰度值序列最小可压缩为: " << Compress(p, length, Llength, Blength) << endl; // 对【灰度值序列】p进行压缩的函数
// 上式 Llength[i] 存储了前i个灰度值后，当前最优排序方式的 灰度值元素数量， 即: 区间(i - Llength[i], i) 成为了一排
// 上式 Blength[i] 存储了前i个灰度值后，当前最优排序方式下 灰度值的最大值， 即: 区间(i - Llength[i], i) 中最大的灰度值。
output(Llength, Blength, length); // 打印输出的 最优压缩方式，即 输出L[i]和B[i]
system("pause");
return 0;
}
int getBLength(int i) { // 已知数字，求其所需最大二进制数的公式: 1 <= log[xi+1] <= 8
// 返回灰度值i需要的存储位数 。
// 例如:灰度值是0--1则返回1，灰度值是2--3则返回2，灰度值是4--7则返回3，... 灰度值是128--255则返回8
int k = 1;
i = i >> 1;
// >>1表示除于2。例子:4>>1 = 4/2。相比除法运算，位运算效率更高。
while (i > 0) {
k++;
i = i >> 1;
}
return k;
}
/* dp常规推导流程
* 先下定义，不妨定义dp(i) 是灰度序列从【第1个】到【第i个】之间的最优压缩值
定义bmax(i, j) 是灰度序列从【第i个】到【第j个】之间的最大的存储位数
dp(1) = min (
dp(0) + bmax(1，1) * 1,
)
dp(2) = min (
dp(1) + bmax(2, 2) * 1,
dp(0) + bmax(1, 2) * 2,
)
dp(3) = min (
dp(2) + bmax(3, 3) * 1,
dp(1) + bmax(2, 3) * 2,
dp(0) + bmax(1, 3) * 3
)
dp(4) = min (
dp(3) + bmax(4, 4) * 1,
dp(2) + bmax(3, 4) * 2,
dp(1) + bmax(2, 4) * 3,
dp(0) + bmax(1, 4) * 4
)
……
dp(7) = min (
dp(6) + bmax(7, 7) * 1,
dp(5) + bmax(6, 7) * 2,
dp(4) + bmax(5, 7) * 3,
dp(3) + bmax(4, 7) * 4,
dp(2) + bmax(3, 7) * 5,
dp(1) + bmax(2, 7) * 6，
dp(0) + bmax(1, 7) * 7
)
dp(8) = min (
dp(7) + bmax(8, 8) * 1，
dp(6) + bmax(7, 8) * 2,
dp(5) + bmax(6, 8) * 3,
dp(4) + bmax(5, 8) * 4,
dp(3) + bmax(4, 8) * 5,
dp(2) + bmax(3, 8) * 6,
dp(1) + bmax(2, 8) * 7，
dp(0) + bmax(1, 8) * 8
)
通过上述的推导，不难发现规律，求dp[i]时，总是从dp[i-1]开始，一直到dp[0]
而bmax则容易发现，永远都是 bmax(j, i) 【j属于[1,i]】, 而右边的 * 次数，其数字结果总是 i - j；
dp(i) = min (
dp(i-1) + bmax(i, i) * ( i-(i-1) ),
dp(i-2) + bmax(i-1, i) * ( i-(i-2) ),
……
dp(i-(i-1)) + bmax(i-(i-2), i) * ( i- (i-(i-1)) ),
dp(i-i) + bmax(i-(i-1), i) * ( i - (i-i) )
)
但是，很容易发现，bmax(i,j)该如何实现呢？或者说，我们需要做出一个数组或者用函数封装起来调用吗？
事实上，通过观察数字之间的关系，很容易发现一个规律：直接拿到第i个数据后，直接和前边的比较，以此类推，不就能完美解决这个方法了吗？
因此，经过上述推导后，很容易能理解下述代码。
*
*/
// 此函数重载了Compress(int* p, int length)
int Compress(int* p, int length, int* L, int* B) {
int* dp = new int[length]();//下标从1开始计数
// 定义dp[i] 是灰度序列从【第1个】到【第i个】之间的最优压缩值
int Bmax = getBLength(p[1]); // getBLength把该灰度值作为参数传入，返回这个灰度值所需的存储位数, 先把第一个灰度值所需的存储位数传给Bmax
for (int i = 1; i < length; i++) {
int Min = INT_MAX; // <algorithm>下定义的一个常量，即:int所能存取的最大值
for (int j = i - 1; j >= 0; j--) {
int tmp = getBLength(p[j + 1]);
if (tmp > Bmax) Bmax = tmp; // 如果发现 新的灰度值的存储位数 > 原先的灰度值的存储位数，则替换
if (i - j > LMAX) continue; // 如果这段长度是> 规定长度(256)，则跳出
if ((dp[j] + Bmax * (i - j)) < Min) { // dp[j] + Bmax * (i - j):即前j个最小压缩值 + (i-j)个所需的最大存储位数
Min = dp[j] + Bmax * (i - j); // Min 和 dp[j] + Bmax * (i - j)进行比较，返回最小值。
L[i] = i - j; // 存储 序列长度进入L数组
B[i] = Bmax; // 存储 (i-j) 到 i 之间的最大存储位数
}
}
dp[i] = Min + HEADER; // bit位(3)和length(8)位加上头部
Bmax = 0; // 清零 如若不置换，且Bmax在dp(i)情况下已经置为8，则影响不到后面Bmax的变化！Bmax将锁死在8
}
return dp[length - 1]; // 因为0不在考虑范围，需要减1;
// 举例: 灰度值序列length = 3 分别是0 15 5, 则因为第0位不用补0，所以只需要返回dp[2]; 即 dp[length - 1]
}
int Compress(int* p, int length) { // 这是没有存储L和B的，只能返回最小压缩长度
int* dp = new int[length](); //下标从1开始计数
// 定义dp[i] 是灰度序列从1到i的最优压缩值
int Bmax = getBLength(p[1]); // getBLength把该灰度值作为参数传入，返回这个灰度值所需的存储位数, 先把第一个灰度值所需的存储位数传给Bmax
for (int i = 1; i < length; i++) {
int Min = INT_MAX; // <algorithm>下定义的一个常量，即:int所能存取的最大值
for (int j = i - 1; j >= 0; j--) {
int tmp = getBLength(p[j+1]);
if (tmp > Bmax) Bmax = tmp; // 如果发现 新的灰度值的存储位数 > 原先的灰度值的存储位数，则替换
if (i - j > LMAX) continue; // 如果这段长度是> 规定长度(256)，则跳出
Min = min(dp[j] + Bmax * (i-j), Min); // <algorithm>下定义的一个函数，两个参数进行比较，返回最小值。
}
dp[i] = Min + HEADER; // 11：压缩后的序列，前11位是告知接下来读取几位，并以什么样的方式去读写的。
//如:B=6 L=4 则读取 4个长度，以一个长度占6位来读写 (B缩写:Bits per pixel, L缩写: lengths of segment i )
Bmax = 0; // 一个循环之后，再跳入下一个循环之前，即此时dp(i)求出，将要进入求dp(i-1)的循环
// 需要将Bmax置为0，如若不置换，且Bmax在dp(i)情况下已经置为8，则影响不到后面Bmax的变化！Bmax将锁死在8
}
return dp[length - 1]; // 因为0不在考虑范围，需要减1; 举例: 灰度值序列length = 3
}
void output(int* Llength, int* BLength, int length) {
// 1. 首先需要算出到底分了几段，我这里设分了m段
int m = 0;
int t = length - 1; // t是辅助变量，无实际意义
while (t > 0) {
m++;
t = t - Llength[t]; // 这里已经分完一段，这段长度是 Llength[t]; 分完之后，把t往前移动，因为已经划分出了Llength[t]个长度了，所以需要减掉这个长度
} // 举例：length = 17, t = 16, Llength[16] = 3; 把 长度为3，下标从14 - 16的划分出去，则原序列剩下 1 - 13,以此类推
int* L = new int[m + 1](); //申请数组存放每段的长度，下标从1开始计数
int* B = new int[m + 1](); //申请数组存放每段的最大存储位数，下标从1开始计数
t = length - 1; // t 重新赋值
for (int i = m; i >= 1; i--) { // 从后往前推出L和B的值
L[i] = Llength[t];
B[i] = BLength[t];
t = t - Llength[t]; // 这段的B和L求出来之后，需要减掉这个已经求出值来的长度
}
for (int i = 1; i <= m; i++) {
cout << "第" << i << "段长度：" << L[i] << ",所需存储位数:" << B[i] << endl;
}
}
// 打印数组
void printArray(int* array, int length) {
cout << "【 ";
for (int i = 1; i < length; i++) {
cout << array[i] << " ";
}
cout << "】 " << endl;
}
控制台输出：
【 10 9 12 40 50 35 15 12 8 10 9 15 11 130 160 240 】
该灰度值序列最小可压缩为: 121
第1段长度：6,所需存储位数:6
第2段长度：7,所需存储位数:4
第3段长度：3,所需存储位数:8
请按任意键继续. . .
最后
以上就是阔达春天为你收集整理的动态规划- 图像压缩起因代码如下的全部内容，希望文章能够帮你解决动态规划- 图像压缩起因代码如下所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复