实验04：图像压缩(DP算法)

1.实验目的：

掌握动态规划算法的基本思想以及用它解决问题的一般技巧。运用所熟悉的编程工具，运用动态规划的思想来求解图像压缩问题。

2.实验内容：

给定一幅图像，求解最佳压缩，使得压缩后的文件最小。

3.实验要求：

实现lena512.raw（称为原文件）图像压缩并保存到文件（称为压缩文件）中。编写相应的解码器，对保存的文件解压出图像，并将解压图像存储为raw文件，通过图像浏览工具验证解压文件和原文件相同。分析压缩率（即 压缩文件大小 除以 原文件大小），分析算法的时间复杂度和空间复杂度。

$\square$ 基础性实验 $\square$ 综合性实验 $⊠$ 设计性实验

---

实验报告正文

一、问题分析（模型、算法设计和正确性证明等）

设灰度图像共$n$个像素值，灰度图像可以视作一个一维向量 P = { p 1 , p 2 , . . . . . . , p n } P=\{p_1, p_2, ...... , p_n\} P={p1​,p2​,......,pn​}，将n个像素分割成m个连续段 { S i } i = 1 m \{S_i\}_{i=1}^m {Si​}i=1m​.

其中，对第$i$段$S_i$有下列相关变量：

符号	表示含义
$l[i]$	段长，该段内包含像素个数
$b[i]$	该段中各像素位宽，$b[i]=\lceil \log (1+{\max }_{p_k\in S_i}{p}_k)\rceil$

约定每段长度$l[i]$满足：$1\leq l[i] \leq 256 $且$b[i]\geq 1$.

已知：$0\le p_k\le 255$，故$1\le b[i]\le 8$

将$S_i$编码压缩如下：
l [ i ] − 1 b [ i ] − 1 { p i + 1 , p i + 2 . . . . . . , p i + l [ i ] } 8 b i t s 3 b i t s l [ i ] × b [ i ] b i t s \begin{matrix} l[i]-1 & b[i]-1 & \{p_{i+1}, p_{i+2}......, p_{i+l[i]}\}\\ 8bits & 3bits & l[i]\times b[i]bits \end{matrix} l[i]−18bits​b[i]−13bits​{pi+1​,pi+2​......,pi+l[i]​}l[i]×b[i]bits​
压缩完成后，共占用空间：$l[i]\times b[i]+11$

设 f ( { S i } 1 m ) f(\{S_i\}_1^m) f({Si​}1m​)表示压缩为$m$个连续子段集合 { S i } 1 m \{S_i\}_1^m {Si​}1m​占用空间，则递归表达如下：
f ( { S i } 1 m ) = f ( { S i } 1 m − 1 ) + 11 (1) f(\{S_i\}_1^m)=f(\{S_i\}_1^{m-1})+11\tag1 f({Si​}1m​)=f({Si​}1m−1​)+11(1)
最优子结构性质

设最优分段为 { S i } i = 1 m \{S_i\}_{i=1}^m {Si​}i=1m​，其中第$m$个分段$S_m$的长度为$len$，则 { S i } i = 1 m − 1 \{S_i\}_{i=1}^{m-1} {Si​}i=1m−1​是子问题 { p 1 , p 2 , . . . . . . , p n − l e n } \{p_1, p_2, ......, p_{n-len}\} {p1​,p2​,......,pn−len​}的最优分段，递归表达如下：
f ( { S i } i = 1 m ) = f ( { S i } i = 1 m − 1 ) + f ( { S m } ) (2) f(\{S_i\}_{i=1}^m)=f(\{S_i\}_{i=1}^{m-1})+f(\{S_m\})\tag2 f({Si​}i=1m​)=f({Si​}i=1m−1​)+f({Sm​})(2)

简要证明过程如下：

假设 { S i } i = 1 m \{S_i\}_{i=1}^m {Si​}i=1m​为原问题最优分段，即 f ( { S i } i = 1 m ) f(\{S_i\}_{i=1}^m) f({Si​}i=1m​)值最小，但 { S i } i = 1 m − 1 \{S_i\}_{i=1}^{m-1} {Si​}i=1m−1​不是子问题的最优解。

则将其分段策略调整为最优解后， f ( { S i } i = 1 m − 1 ) f(\{S_i\}_{i=1}^{m-1}) f({Si​}i=1m−1​)值减少， f ( { S i } i = 1 m ) = f ( { S i } i = 1 m − 1 ) + f ( { S m } ) f(\{S_i\}_{i=1}^m)=f(\{S_i\}_{i=1}^{m-1})+f(\{S_m\}) f({Si​}i=1m​)=f({Si​}i=1m−1​)+f({Sm​})值减少，与假设矛盾。

令g(n)表示像素序列{p_1, p_2, …, p_n}的最优分段占用空间，则有递归公式如下：
$$g(n)=\min (g(n-k)+k\times b_{max}+11),1\le k\le \min (n,256)\text{\hspace{1em}(3)}$$

二、算法设计复杂度分析（伪代码，不要粘贴源码）

时间复杂度：
$$T(n)\in \theta (\sum _{i=1}^n\min (i,Lmax))=\theta (Lmax\times n)=\theta (n)$$
空间复杂度：

该算法需要辅助空间储存段长、位宽及前$i$个像素最优压缩占用空间大小，$S(n)\in \theta (n)$.

三、实验结果记录和分析（测试向量上的测试结果、运行时间）

实验结果：

原图像大小	压缩后大小
262114字节	257550字节

压缩率：$(1-\frac{257550}{262114})\times 100\%\approx 1.75\%$，详见RESULT文件夹

算法运行时间：267.847

结果验证：

文件大小一致，下使用c++库OpenCV将Decode_lena.raw转存为jpg格式文件，详见RESULT文件夹。

与原图像一致，详见RESULT文件夹。

四、总结（可描述出现的问题和解决方法、经验和反思等）

本实验中采用bin文件格式保存中间编码（压缩）文件以直观显示压缩完成后文件大小，本实验所有代码保存于CODE文件夹，所有结果保存于RESULT文件夹以便老师查阅。

本实验的压缩方式相对单一，压缩率较低，有较大提升空间，具体算法有：

1. 将像素值均大于$2^7=128$的分段进行取反操作，保存像素值与$256$之差，段长最大值减一，需多加一位符号位表示是否取反，对于像素值较大的图像压缩率较大。
2. 对于一段像素值用高斯分布等概率模型拟合，保存参数后解压时用概率分布函数生成像素值。