草庐IT

动态规划---图像压缩

Chen的博客 2023-07-27 原文

动态规划---图像压缩


在算法课上遇到这个图像压缩这个问题，可以用 动态规划来求解，之前没有遇到过这个问题，在网上查找相关的题解也比较少，就写一下自己的理解。

问题描述

	一幅图像的由很多个像素点构成，像素点越多分辨率越高，像素的灰度值范围为0~255，
也就是需要8bit来存储一个像素的灰度值信息。
	一幅由n*m像素点构成的图像，所需存储空间大小为：n*m*8bit=8nmbit(这是非常大的，直接传输很慢)
	
	然而，正常情况下，一幅图像的某一范围内像素点的灰度值是很接近的，表现为一幅图片某一区域颜色相近。
	例如，一个像素灰度值序列P={1,2,2,2,1,2,60,55,78}(传输过程中把图像像素点转成序列，
而不是直接传输矩阵)，每个像素灰度值都用8bit来存储是非常消耗空间的，例如：
直接存储: 9*8bit=72bit，这是非常不划算的，我们想要无损压缩图片。

	即：
	将像素序列分段，段内的像素灰度值相似(可以用小于8bit的空间来存储一个像素灰度值)，
一段内的像素用相同的bit数来存储，只需要额外存树每段的长度和bit数即可，这样可以节省很多空间。


b[i]:第i段中每个像素的位数，1<=b[i]<=8，需要3 bit
l[i];第i段中像素的个数，1<=l[i]<=255,需要8 bit
所以每一段需要额外的 3+8=11 bit来存储段内像素的信息

分析

如何分段?
若分为 m 段，则需要的存储总位数为 : ∑ i = 1 m b [ i ] ∗ l [ i ] + m ∗ 11 若分为m段，则需要的存储总位数为: \sum_{i=1}^{m}b[i]*l[i]+m*11 若分为m段，则需要的存储总位数为:i=1∑m​b[i]∗l[i]+m∗11
考虑用动态对规划来求解问题：
最优子结构 : p 1 , p 2 , p 3 , . . . . p m 考虑最后一个分段为 l [ m ] 个元素 p n − l [ m ] + 1 ∼ p [ n ] , 则子问题为 p 1 ∼ p [ l [ m ] ] 的分段 ( 前 m − 1 段 ) 子问题的最优解为 b [ i ] , l [ i ] , 1 < = i < = m − 1 最后一个分段最优和前 m − 1 个分段最优构成了原问题分段最优，最优子结构存在 在求解第 i 段过程中需要前 i − 1 段分法的信息，存在重复子问题可以用动态规划的思想来求解问题 最优子结构:\\ {p1,p2,p3,....pm}\\ 考虑最后一个分段为l[m]个元素\\ p_{n-l[m]+1}\sim p[n],\\ 则子问题为p_1\sim p[l[m]]的分段(前m-1段)\\ 子问题的最优解为b[i],l[i],1<=i<=m-1\\ 最后一个分段最优和前m-1个分段最优构成了原问题分段最优，最优子结构存在\\ 在求解第i段过程中需要前i-1段分法的信息，存在重复子问题 可以用动态规划的思想来求解问题 最优子结构:p1,p2,p3,....pm考虑最后一个分段为l[m]个元素pn−l[m]+1​∼p[n],则子问题为p1​∼p[l[m]]的分段(前m−1段)子问题的最优解为b[i],l[i],1<=i<=m−1最后一个分段最优和前m−1个分段最优构成了原问题分段最优，最优子结构存在在求解第i段过程中需要前i−1段分法的信息，存在重复子问题可以用动态规划的思想来求解问题

状态表示:
f[i]表示以A[i](包含)结尾的最优分段所需的bit数(最少)

状态转移:
f[i] =A[i-k]+bitmax(i-k+1,i)+11 , 0<=k<=i
bitmax(i-k+1,i)为求i-k+1到i这个序列每个像素灰度值需要的的bit数
其中,k<=256（图像压缩的限制）
f[i] =A[i-k]+bitmax(i-k+1,i)+11 , 0<=k<=min(i,256)

时间复杂度分析:
遍历序列n，
遍历(i-k+1,i)
求bitmax(i-k+1,i)
时间复杂度看起来是O(n^3)
但是k<=256，所以时间复杂度为O(n) (n前常数会比较大)

代码如下

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+10;
const int inf=0x3f3f3f3f;

int f[N];
int A[N];
int l[N],b[N];
int maxbit(int x){//求某个数存储需要的bit位数
    if(x==0) return 1;
    int res=0;
    while(x){
        x/=2;
        res++;
    }
    return res;
}
int get_maxbit(int l,int r){//求某一区间(区间最大值)需要的bit位数
    int res=0;
    for(int i=l;i<=r;i++) res=max(res,A[i]);
    
    return maxbit(res);
}

int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d",&A[i]);
	
	for(int i=1;i<=n;i++){
	    f[i]=f[i-1]+maxbit(A[i])+11;//假设A[i]单独构成一段,作为初始情况
	    b[i]=maxbit(A[i]);
	    l[i]=1;
	    for(int j=2;j<=min(i,256);j++){//从i-1到j+1遍历取min(f[i])
	        int bit_j=get_maxbit(i-j+1,i);
	        int t=f[i-j]+bit_j*j+11;
	        if(f[i]>t){
	            f[i]=t;
	            b[i]=bit_j;//记录该段需要的bit位
	            l[i]=j;//记录该段的长度
	        }
	    }
	}
	int t=n;
	vector<int>v;
	while(t){
	       v.push_back(l[t]);//将长度信息用vector存储
	       t=t-l[t];
	}
	reverse(v.begin(),v.end());//倒置
	printf("最少需要:%dbit\n",f[n]);
    for(int i=0,t=1;i<v.size();i++){//输出分段信息
        for(int j=0;j<v[i];j++)
            printf("%d ",A[t++]);
        printf("长%d,每个像素需要%dbit\n",l[t-1],b[t-1]);
    }
    return 0;
}
/*
12
10 12 15 255 1 2 1 1 2 2 1 1
#69
/*
/*
6
10 12 15 255 1 2
#57
*/

运行结果如下

结果一

结果二


感觉这道题讲的重心错了，应该重点讲解动态规划的，比较少见的动态规划题

动态规划动态spanclasstoken算法c++

有关动态规划---图像压缩的更多相关文章

  1. ruby - 使用 RubyZip 生成 ZIP 文件时设置压缩级别 - 2

    我有一个Ruby程序，它使用rubyzip压缩XML文件的目录树。gem。我的问题是文件开始变得很重，我想提高压缩级别，因为压缩时间不是问题。我在rubyzipdocumentation中找不到一种为创建的ZIP文件指定压缩级别的方法。有人知道如何更改此设置吗？是否有另一个允许指定压缩级别的Ruby库？ 最佳答案 这是我通过查看ruby​​zip内部创建的代码。level=Zlib::BEST_COMPRESSIONZip::ZipOutputStream.open(zip_file)do|zip|Dir.glob("**/*")d

  2. ruby-on-rails - 添加回形针新样式不影响旧上传的图像 - 2

    我有带有Logo图像的公司模型has_attached_file:logo我用他们的Logo创建了许多公司。现在，我需要添加新样式has_attached_file:logo,:styles=>{:small=>"30x15>",:medium=>"155x85>"}我是否应该重新上传所有旧数据以重新生成新样式？我不这么认为……或者有什么rake任务可以重新生成样式吗？ 最佳答案 参见Thumbnail-Generation.如果rake任务不适合你，你应该能够在控制台中使用一个片段来调用重新处理!关于相关公司

  3. ruby-on-rails - 在 Ruby (on Rails) 中使用 imgur API 获取图像 - 2

    我正在尝试使用Ruby2.0.0和Rails4.0.0提供的API从imgur中提取图像。我已尝试按照Ruby2.0.0文档中列出的各种方式构建http请求，但均无济于事。代码如下:require'net/http'require'net/https'defimgurheaders={"Authorization"=>"Client-ID"+my_client_id}path="/3/gallery/image/#{img_id}.json"uri=URI("https://api.imgur.com"+path)request,data=Net::HTTP::Get.new(path

  4. python ffmpeg 使用 pyav 转换 一组图像 到 视频 - 2

    2022/8/4更新支持加入水印水印必须包含透明图像，并且水印图像大小要等于原图像的大小pythonconvert_image_to_video.py-f30-mwatermark.pngim_dirout.mkv2022/6/21更新让命令行参数更加易用新的命令行使用方法pythonconvert_image_to_video.py-f30im_dirout.mkvFFMPEG命令行转换一组JPG图像到视频时，是将这组图像视为MJPG流。我需要转换一组PNG图像到视频，FFMPEG就不认了。pyav内置了ffmpeg库，不需要系统带有ffmpeg工具因此我使用ffmpeg的python包装p

  5. ruby - Ruby 的压缩库？ - 2

    是否有任何可用于Ruby的开源压缩/解压库？有没有人实现过LZW？或者，是否有任何使用压缩组件的开源库可以提取出来独立使用？编辑——感谢您的回答!我应该提到我必须压缩的是只驻留在数据库中的长字符串(我不会压缩文件)。此外，如果可以执行此操作的任何库都具有用于客户端压缩/分解的等效JavaScript实现，那将是理想的，因为这将用于Web应用程序。 最佳答案 您会在rubystdlib下找到所有已交付的ruby​​库的一个很好的列表.我会使用zlib库，它是开放的，无处不在，您会发现几乎所有语言的库!

  6. ruby - 在 Ruby 中动态创建数组 - 2

    有没有办法在Ruby中动态创建数组？例如，假设我想遍历用户输入的书籍数组:books=gets.chomp用户输入:"TheGreatGatsby,CrimeandPunishment,Dracula,Fahrenheit451,PrideandPrejudice,SenseandSensibility,Slaughterhouse-Five,TheAdventuresofHuckleberryFinn"我把它变成一个数组:books_array=books.split(",")现在，对于用户输入的每一本书，我想用Ruby创建一个数组。伪代码来做到这一点:x=0books_array.

  7. ruby - 是否可以将 IRB 提示配置为动态更改？ - 2

    我想在IRB中浏览文件系统并让提示更改以反射(reflect)当前工作目录，但我不知道如何在每个命令后进行提示更新。最终，我想在日常工作中更多地使用IRB，让bash溜走。我在我的.irbrc中试过这个:require'fileutils'includeFileUtilsIRB.conf[:PROMPT][:CUSTOM]={:PROMPT_N=>"\e[1m:\e[m",:PROMPT_I=>"\e[1m#{pwd}>\e[m",:PROMPT_S=>"FOO",:PROMPT_C=>"\e[1m#{pwd}>\e[m",:RETURN=>""}IRB.conf[:PROMPT_MO

  8. ruby - 是否有将图像文件转换为 ASCII 艺术的命令行程序或库？ - 2

    有这样的事吗？我想在Ruby程序中使用它。 最佳答案 试试这个http://csl.sublevel3.org/jp2a/此外，Imagemagick可能还有一些东西 关于ruby-是否有将图像文件转换为ASCII艺术的命令行程序或库？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/6510445/

  9. ruby-on-rails - 使用 Dragonfly 从 URL 分配图像 - 2

    我正在使用Dragonfly在Rails3.1应用程序上处理图像。我正在努力通过url将图像分配给模型。我有一个很好的表格:{:multipart=>true}do|f|%>RemovePicture?Dragonfly的文档指出:Dragonfly提供了一个直接从url分配的访问器:@album.cover_image_url='http://some.url/file.jpg'但是当我在控制台中尝试时:=>#ruby-1.9.2-p290>picture.image_url="http://i.imgur.com/QQiMz.jpg"=>"http://i.imgur.com/QQ

  10. Ruby-vips 图像处理库。有什么好的使用示例吗？ - 2

    我对图像处理完全陌生。我对JPEG内部是什么以及它是如何工作一无所知。我想知道，是否可以在某处找到执行以下简单操作的ruby​​代码:打开jpeg文件。遍历每个像素并将其颜色设置为fx绿色。将结果写入另一个文件。我对如何使用ruby​​-vips库实现这一点特别感兴趣https://github.com/ender672/ruby-vips我的目标-学习如何使用ruby​​-vips执行基本的图像处理操作(Gamma校正、亮度、色调……)任何指向比“helloworld”更复杂的工作示例的链接——比如ruby​​-vips的github页面上的链接，我们将不胜感激!如果有ruby​​-

随机推荐