高要市建设局网站,东莞企业响应式网页设计,wordpress中英文,高速公路建设网站1.实验目的#xff1a;
掌握动态规划算法的基本思想以及用它解决问题的一般技巧。运用所熟悉的编程工具#xff0c;运用动态规划的思想来求解图像压缩问题。
2.实验内容#xff1a;
给定一幅图像#xff0c;求解最佳压缩#xff0c;使得压缩后的文件最小。
3.实验要求…1.实验目的
掌握动态规划算法的基本思想以及用它解决问题的一般技巧。运用所熟悉的编程工具运用动态规划的思想来求解图像压缩问题。
2.实验内容
给定一幅图像求解最佳压缩使得压缩后的文件最小。
3.实验要求
实现lena512.raw称为原文件图像压缩并保存到文件称为压缩文件中。编写相应的解码器对保存的文件解压出图像并将解压图像存储为raw文件通过图像浏览工具验证解压文件和原文件相同。分析压缩率即 压缩文件大小 除以 原文件大小分析算法的时间复杂度和空间复杂度。 □ \square □ 基础性实验 □ \square □ 综合性实验 ⊠ \boxtimes ⊠ 设计性实验 实验报告正文 一、问题分析模型、算法设计和正确性证明等
设灰度图像共 n n 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\}_{i1}^m {Si}i1m.
其中对第 i i i段 S i S_i Si有下列相关变量
符号表示含义 l [ i ] l[i] l[i]段长该段内包含像素个数 b [ i ] b[i] b[i]该段中各像素位宽 b [ i ] ⌈ log ( 1 max p k ∈ S i p k ) ⌉ b[i]\lceil {\log{(1\max_{p_k \in S_i}{p_k}})} \rceil b[i]⌈log(1maxpk∈Sipk)⌉
约定每段长度 l [ i ] l[i] l[i]满足$1\leq l[i] \leq 256 且 且 且b[i]\geq 1$.
已知 0 ≤ p k ≤ 255 0\leq p_k \leq 255 0≤pk≤255故 1 ≤ b [ i ] ≤ 8 1\leq b[i]\leq 8 1≤b[i]≤8
将 S i S_i Si编码压缩如下 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_{i1}, p_{i2}......, p_{il[i]}\}\\ 8bits 3bits l[i]\times b[i]bits \end{matrix} l[i]−18bitsb[i]−13bits{pi1,pi2......,pil[i]}l[i]×b[i]bits 压缩完成后共占用空间 l [ i ] × b [ i ] 11 l[i]\times b[i] 11 l[i]×b[i]11
设 f ( { S i } 1 m ) f(\{S_i\}_1^m) f({Si}1m)表示压缩为 m m 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\}_{i1}^m {Si}i1m其中第 m m m个分段 S m S_m Sm的长度为 l e n len len则 { S i } i 1 m − 1 \{S_i\}_{i1}^{m-1} {Si}i1m−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\}_{i1}^m)f(\{S_i\}_{i1}^{m-1})f(\{S_m\})\tag2 f({Si}i1m)f({Si}i1m−1)f({Sm})(2)
简要证明过程如下
假设 { S i } i 1 m \{S_i\}_{i1}^m {Si}i1m为原问题最优分段即 f ( { S i } i 1 m ) f(\{S_i\}_{i1}^m) f({Si}i1m)值最小但 { S i } i 1 m − 1 \{S_i\}_{i1}^{m-1} {Si}i1m−1不是子问题的最优解。
则将其分段策略调整为最优解后 f ( { S i } i 1 m − 1 ) f(\{S_i\}_{i1}^{m-1}) f({Si}i1m−1)值减少 f ( { S i } i 1 m ) f ( { S i } i 1 m − 1 ) f ( { S m } ) f(\{S_i\}_{i1}^m)f(\{S_i\}_{i1}^{m-1})f(\{S_m\}) f({Si}i1m)f({Si}i1m−1)f({Sm})值减少与假设矛盾。
令g(n)表示像素序列{p_1, p_2, …, p_n}的最优分段占用空间则有递归公式如下 g ( n ) min ( g ( n − k ) k × b m a x 11 ) , 1 ≤ k ≤ min ( n , 256 ) (3) g(n)\min(g(n-k)k\times b_{max}11), 1\leq k \leq \min{(n, 256)}\tag3 g(n)min(g(n−k)k×bmax11),1≤k≤min(n,256)(3)
二、算法设计复杂度分析伪代码不要粘贴源码 时间复杂度 T ( n ) ∈ θ ( ∑ i 1 n min ( i , L m a x ) ) θ ( L m a x × n ) θ ( n ) T(n) \in \theta(\sum_{i1}^{n}{\min{(i, Lmax)}})\theta(Lmax\times n)\theta(n) T(n)∈θ(i1∑nmin(i,Lmax))θ(Lmax×n)θ(n) 空间复杂度
该算法需要辅助空间储存段长、位宽及前 i i i个像素最优压缩占用空间大小 S ( n ) ∈ θ ( n ) S(n)\in \theta(n) S(n)∈θ(n).
三、实验结果记录和分析测试向量上的测试结果、运行时间
实验结果
原图像大小压缩后大小262114字节257550字节
压缩率 ( 1 − 257550 262114 ) × 100 % ≈ 1.75 % (1-\frac{257550}{262114} )\times 100\% \approx 1.75\% (1−262114257550)×100%≈1.75%详见RESULT文件夹
算法运行时间267.847 结果验证 文件大小一致下使用c库OpenCV将Decode_lena.raw转存为jpg格式文件详见RESULT文件夹。 与原图像一致详见RESULT文件夹。
四、总结可描述出现的问题和解决方法、经验和反思等
本实验中采用bin文件格式保存中间编码压缩文件以直观显示压缩完成后文件大小本实验所有代码保存于CODE文件夹所有结果保存于RESULT文件夹以便老师查阅。
本实验的压缩方式相对单一压缩率较低有较大提升空间具体算法有
将像素值均大于 2 7 128 2^7128 27128的分段进行取反操作保存像素值与 256 256 256之差段长最大值减一需多加一位符号位表示是否取反对于像素值较大的图像压缩率较大。对于一段像素值用高斯分布等概率模型拟合保存参数后解压时用概率分布函数生成像素值。
