精华内容
下载资源
问答
  • 图片在计算机存储的是图片中的一个一个像素,也...现在图像压缩问题是这样的:有一些像素序列{p1,p2,……,pn},当然每个像素值都是0到255之间的。要求对这样的像素序列进行分段,使得最后所需要的存储空间最小。比...

    图片在计算机存储的是图片中的一个一个像素,也就是像素的灰度值。灰度值的范围是0~255。有灰白图像和彩色图像,它们每个像素的通道数量不同。灰白图像是单通道的,而彩色图像是3个通道的(BGR),也就是彩色图像的每个像素都存放三个灰度值。

    现在图像压缩问题是这样的:有一些像素序列{p1,p2,……,pn},当然每个像素值都是0到255之间的。要求对这样的像素序列进行分段,使得最后所需要的存储空间最小。比如有些连续的像素点用4位进行存储就可以,那么就可以将这些像素点分在一段中,就没有必要把这些像素点用8位来存储,这样不就节省了一些存储空间嘛。

    可以将问题详细描述分析如下:如果最优的结果是将像素序列分成m段(0<=m<=n),假设每段有l[i]个像素点,我们限定0<=l[i]<=255,那么l[1]+l[2]+……+l[m]=n。所有段的像素点的数量加起来就等于总的像素数。第i段存储l[i]这个值需要8位(log(255)向上取整),每段每个像素的存储位数肯定是一样的(否则这些像素不可能分配在同一段中),用b[i]来表示,每段的存储位数一定是小于等于8的整数,因为灰度值的范围是[0,255],那么存储b[i]这个值呢?可想而知,一定是最多需要3位(log(8)向上取整)。

    也就是每段不管有多少个像素点,最起码得存储l[i]和b[i]这两个值,也就是说每段最少需要8+3=11位。当然,每段中有l[i]个像素点,每个像素点的灰度值用b[i]位存储,所以需要l[i]*b[i]位存储每段的像素点的灰度值,再加上上面分析的11位,每段总共需要的存储空间就是l[i]*b[i]+11。对于m段呢?需要位的存储空间。

    这是一个动态规划问题,满足最优子结构性质,也就是如果l[i],b[i](1<=i<=m)是{p1,p2,……,pn}的一个最优分段。显然,l[1],b[1]是{p1,p2,……,pl[1]}的一个最优分段,且l[i],b[i](2<=i<=m)是{pl[1]+1(l[1]+1是p的下标),...,pn}的一个最优分段。

    设s[i]表示前i个像素点{p1,p2,...,pi}所需要的总的存储位数。由最优子结构的性质可以知道,后面的s[i+1]等是依赖于s[i]的。也可以得到这样的递推公式:

    s[i]={s[i-k]+k*bmax(i-k+1,i)}+11,其中1<=k<=min{i,256},

    bmax(i,j)就是pi和pj之间的最大像素值所需的存储位数。

    程序代码可以见Compress.cpp

    ​​

    a4c26d1e5885305701be709a3d33442f.png

    a4c26d1e5885305701be709a3d33442f.png

    a4c26d1e5885305701be709a3d33442f.png

    a4c26d1e5885305701be709a3d33442f.png

    若像素序列是{10,12,15,255,1,2},则执行结果如下:​

    a4c26d1e5885305701be709a3d33442f.png

    分析算法的空间复杂度和时间复杂度:Compress算法只需O(n)空间。由于compress()函数中j的循环次数不超过Lmax=256次,所以对于每一个i,都可以在O(1)的时间内找到最小的s[i],因此整个算法所需的计算时间为O(n)。

    手动计算 {10,12,15,255,1,2}的最优存储位数:

    i=1: 10是一个分段  需11+4=15位

    后面需11+5*8=51位

    总共需要15+51=66位

    i=2:{10,12}作为一段,需要11+2*4=19位

    {15,255,1,2}需要11+4*8=43位

    总共需要19+43=62位

    i=3:  ......

    最优分段如下:{10,12,15},{255},{1,2}

    (11+3*4)+(11+1*8)+(11+2*2)=57位。

    展开全文
  • 图像以像素点序列格式存储,即{p1 ,p2 ,…,pn }, 0≤pi≤255,pi在问题中是真正要存储的东西,一般的存储过程是将每个pi都存储在8位二进制中,但对于远小于255的pi来说造成了空间上的浪费,也就是说对于[0,1]内的pi...

    问题分析:

    图像以像素点序列格式存储,即{p1 ,p2 ,…,pn }, 0≤pi≤255,pi在问题中是真正要存储的东西,一般的存储过程是将每个pi都存储在8位二进制中,但对于远小于255的pi来说造成了空间上的浪费,也就是说对于[0,1]内的pi,可以用一位二进制表示;对于[2,3]内的pi,可以用两位二进制表示;对于[8,15]内的pi,可以用四位二进制表示……以此类推。

    同时,如果按照这种方法压缩,会产生额外的空间用来存储pi所占的位数,用上边的例子来说,使用一位二进制表示[0,1]内的pi时,额外需要存储的便是1,把这个值记作b[i]。并且,对于{6, 5, 7,5, 245, 180, 28,28,19, 22, 25,20}这样的灰度序列,其中{6,5,7,5}用三位存储,{245,180}八位存储,{28,28,19,22,25,20}用五位存储,我们还需要知道这三个序列的长度用以计算总存储空间。又产生了额外的开销,即每段相同位数存储序列的长度,记作l[i]。(不要把此处的l[i],b[i]中的i跟p[i]中的i搞混,若将原序列分为m段,b[i],l[i]中的i在[1,m]范围内)

    动态规划过程:

    是否满足最优子结构?

    若l[i], b[i]已经是{p1 , p2 , …, pn }的一个最优分段,显然l[1], b[1] 是{p1 ,…,pl[1]}的一个最优分段,l[2], b[2] 是{p1 …,pl[2]+pl[1]}的最优分段……以此类推,满足最优子结构性质

    递归结构

    在这里插入图片描述

    代码就不赘述了,从s[0]开始计算,迭代计算即可。

    展开全文
  • 图像传输和视频处理有时在1秒钟内要处理几十帧图片,这些图片的像素就很可观了,因此图像处理常常需要大量的存储空间和高的处理速度,图像压缩问题就成了计算机科学技术中的重要研究课题之一. ​ 以黑白图像的处理...

    一、题目描述

    ​ 计算机中的图像由一系列像点构成,每个像点称为一个像素,图像分辨率越高,使用的像素就越多,例如Windows桌面的图片经常使用的设置是1024×768个,大概达到106量级.图像传输和视频处理有时在1秒钟内要处理几十帧图片,这些图片的像素就很可观了,因此图像处理常常需要大量的存储空间和高的处理速度,图像压缩问题就成了计算机科学技术中的重要研究课题之一.

    ​ 以黑白图像的处理来说明图像压缩中的问题.每幅黑白图像由像点构成,每个像点具有灰度值,用0~255之间的整数表示.如果每个整数都用相同的二进制位来表示,那么需要用8个二进制位.假设一幅图像有n个像素,那么这n个像素的灰度值构成一个整数序列:P = <p1,p2,…,pn>

    ​ 其中p表示第i个像素的灰度.存储这幅图片时,可以像数组一样连续把这些整数存起来,共需要8n个二进制位.

    ​ 下面考虑一种图像压缩方法.一般来说,在一幅图片中许多连续区域中像点的灰度值是接近的.比如有些交通标志图片,大片的区域是白的,可能少量区域有颜色,而且是比较单调的颜色.对这样的图片是否可以采用分段存储的方法:对灰度值较小的段的像素采用比较少的位数,比如2位;对灰度值较大的段的像素采用较多的位数,比如8位,这样就可能减少空间的占用.这就是变位压缩技术的基本想法.这种技术节省了空间,但在读取图像时带来了新的问题.在每个像素8位的存储方法中,读取图像时每8位就是一个像素的灰度值,不会出错.但是对于分段压缩的图像,看起来就是一个长长的0-1序列.当读取这个序列时,怎么知道每段的划分位置及每段像素占用的二进制位数呢?这里需要对段的划分和段中像素使用的二进制位数(要求同一段内不同像素用的存储位数都一样)给出明确的信息.为此,我们对每个段给出两个整数值,一个表示该段含有的像素个数,一个表示每个像素所占用的二进制位数.比如第i段,有l[i]个像素,每个像素用b[i]位.由于某些技术要求,规定每段像素总数不超过256,即l[i]≤256.于是可以用8位来表示l[i](8位二进制数恰好有256个值).此外,由于每个灰度值在0~255之间,表达每个灰度值所用二进制数的位数b[i]不超过8,于是记录b[i]还需要3个二进制位.对每段来说,这额外的11位作为段头信息.从直觉上来说,分段越多,每段内部像素所占用的位数会减少,但过多的段头会消耗较多的二进制位.相反,分段越少,段内像素的空间消耗会增加,但是段头消耗少.

    示例:

    ​ 请看下面的例子.设输入的灰度值序列是:

    ​ P =<10,12,15,255,1,2,1,1,2,2,1,1>

    • 分法1 S1= <10,12,15>,S2 =<255>,S3=<1,2,1,1,2,2,1,1>

    • 分法2 S1=<10,12,15,255,1,2,1,1,2,2,1,1>

    • 分法3 S1=<10>,S2=<12>,S3=<15>,S4=<255>,S5=<1>,S6=<2>,S7=<1>,S8=<1>,S9=<2>,S10=<2>,S11=<1>,S12=<1>

      ​ 分法1有3段,第1段3个像素,每个像素用4位;第2段1个像素,每个像素用8位;第3段8个像素,每个像素用2位;加上3个段头,每个段头11位,总计位数是:
      4×3+8×1+2×8+3×11=69

      ​ 分法2有1段,12个像素,每个像素用8位,段头11位,总计位数是:
      8×12+11=107

      ​ 分法3有12段,前3段的像素用4位,第4段像素用8位,后面有5段像素用1位,3段像素用2位,还有12个段头,每个11位,总计位数是:
      4×3+8×1+1×5+2×3+11×12=163

      看起来分法1占用的位数最少.我们的问题是寻找存储位数最少的分段方法.

    二、解题思路

    1. 定义状态

    ​ 设dp[i]表示字符串前i个像素点的保存的最少二进制数的数量,i从1开始计数,那么我们最终要求出的是dp[P.length]即为像素序列P的最少消耗空间;

    ​ 假设每个分段数量为j,则由于题目约束可得 1 ≤ j < = m i n ( i , 256 ) 1 \leq j <=min(i,256) 1j<=min(i,256), 假设像素序列i的后j个像素序列分为一段,则有dp[i] = dp[i - j] + j x log2max(Pi-j+1,…,Pi) + 11 ,当然j值可能有多个,我们取最小花费那个。

    2. 定义状态转移方程

    1 ≤ j < = m i n ( i , 256 ) 1 \leq j <=min(i,256) 1j<=min(i,256),有

    d p [ i ] = m i n ( d p [ i − j ] + j × l o g 2 m a x ( P i − j + 1 , . . , P i ) + 11 ) dp[i] = min(dp[i - j] + j \times log_2max(P_{i-j+1},..,P_i) + 11) dp[i]=min(dp[ij]+j×log2max(Pij+1,..,Pi)+11)

    3. 初始化

    ​ 当 i = 0时,有 d p [ 0 ] = 0 dp[0] = 0 dp[0]=0

    4. 计算方式

    ​ 自左向右计算

    三、代码实现

    /**
     * 最优图像压缩位数
     *
     *  @author hh
     *  @date 2021-5-21 21:46
     */
    public class OptimalImageCompression {
    
        public int optimalBits(int[] dots,int[] traces){
            int[] dp = new int[dots.length + 1];
            int cost = Integer.MAX_VALUE;
            //初始化行
            dp[0] = 0;
            for(int i = 1; i <= dots.length; i++){
                dp[i] = Integer.MAX_VALUE;
                for(int j = 1; j <= Math.min(i,256); j++){
                    cost = dp[i -j] + j * (this.minBits(this.max(dots,i -j + 1,i))) +11;
                    if(cost < dp[i]){
                        dp[i] = cost;
                        traces[i] = j;
                    }
                }
            }
            return dp[dots.length];
        }
    
        public void print(int[] traces, int length){
            length -= traces[length];
            if(length <= 0){
                return;
            }
            print(traces,length);
            System.out.print(length + " ");
        }
    
        private int max(int[] dots,int start,int end){
            int[] copy =  Arrays.copyOfRange(dots,start -1,end);
            Arrays.sort(copy);
            return copy[copy.length -1];
        }
    
        private int minBits(int number){
            int bits = 0;
            for(int i = 1; i <= 8; i++){
                if(Math.pow(2,i-1) - 1 <= number && Math.pow(2,i) - 1 >= number){
                    bits = i;
                    break;
                }
            }
            return bits;
        }
    
        public static void main(String[] args){
            int[] dots = new int[]{10,12,15,255,1,2,1,1,2,2,1,1};
            int[] traces = new int[dots.length + 1];
            OptimalImageCompression optimalImageCompression = new OptimalImageCompression();
            System.out.println("最少二进制位:" + optimalImageCompression.optimalBits(dots,traces));
            System.out.print("切分位置:");
            optimalImageCompression.print(traces,dots.length);
        }
    }
    
    

    四、执行结果

    在这里插入图片描述

    五、思考

    ​ 本题和文本压缩的做法非常相似,都是对dp数组进行线性划分,读者有时间可以看我的另一篇文章动态规划经典题目-数据压缩之文本压缩,进行举一反三。

    展开全文
  • //重新为s[]数组赋值,用来存储分段位置,最终i为共分了多少段 } void Output(int s[],int l[],int b[],int n) { //在输出s[n]存储位数后,s[]数组则被重新赋值,用来存储分段的位置 cout图像压缩后的最小空间为:"...
    #include <stdio.h>
    #include <iostream>
    #include <fstream>
    #include <string.h>
    using namespace std;
     
    const int N = 7;
     
    int length(int i);
    void Compress(int n,int p[],int s[],int l[],int b[]);
    void Tracebace(int n,int& i,int s[],int l[]);
    void Output(int s[],int l[],int b[],int n);
     
    int main()
    {
        int p[] = {0,10,12,15,255,1,2};//图像数组{p1,p2,p3,p4,p5,p6} 下标从1开始计数
        int s[N],l[N],b[N];
     
        cout<<"图像的序列为:"<<endl;
     
        for(int i=1;i<N;i++)
            cout<<p[i]<<" ";
        cout<<endl;
     
        Compress(N-1,p,s,l,b);
        Output(s,l,b,N-1);
        return 0;
    }
     
    void Compress(int n,int p[],int s[],int l[],int b[])
    {//n个像素,存在数组p[]中,
        int Lmax = 256,header = 11;
        s[0] = 0;
        for(int i=1; i<=n; i++)
        {
            b[i] = length(p[i]);//计算像素点p需要的存储位数
            int bmax = b[i];
            s[i] = s[i-1] + bmax;
            l[i] = 1;
     
            for(int j=2; j<=i && j<=Lmax;j++)//i=1时,不进入此循环
            {
                if(bmax<b[i-j+1])
                {
                    bmax = b[i-j+1];
                }
     
                if(s[i]>s[i-j]+j*bmax)
                {
                    s[i] = s[i-j] + j*bmax;
                    l[i] = j;
                }
            }
            s[i] += header;
        }
    }
     
    int length(int i)//存储像素pi所需的位数
    {
        int k=1;
        i = i/2;
        while(i>0)
        {
            k++;
            i=i/2;
        }
        return k;
    }
     
    void Traceback(int n,int& i,int s[],int l[])
    {
        if(n==0)
            return;
        Traceback(n-l[n],i,s,l);//p1,p2,p3,...,p(n-l[n])像素序列,最后一段有l[n]个像素
        s[i++]=n-l[n];//重新为s[]数组赋值,用来存储分段位置,最终i为共分了多少段
    }
     
    void Output(int s[],int l[],int b[],int n)
    {
        //在输出s[n]存储位数后,s[]数组则被重新赋值,用来存储分段的位置
        cout<<"图像压缩后的最小空间为:"<<s[n]<<endl;
        int m = 0;
        Traceback(n,m,s,l);//s[0]:第一段从哪分,s[1]:第二段从哪分...,s[m-1]第m段从哪分
        s[m] = n;//此时m为总段数,设s[m]=n,分割位置为第n个像素
        cout<<"将原序列分成"<<m<<"段序列段"<<endl;
        for(int j=1; j<=m; j++)
        {
            l[j] = l[s[j]];
            b[j] = b[s[j]];	//此时s数组存放值为分割的位置 
        }
        for(int j=1; j<=m; j++)
        {
            cout<<"段长度:"<<l[j]<<",所需存储位数:"<<b[j]<<endl;
        }
    }
    
    展开全文
  • 数字化图像是n*n的像素阵列. 假定每个像素有一个0~255的灰度值, 因此存储一个像素至多需8位. 为了减少存储空间, 采用变长模式, 即不同像素用不同位数来存储, 步骤如下: 图像线性化:将nn维图像转换为1n2向量 {p1,p2,...
  • 动态规划算法实现数字图像压缩的研究维普资讯总第222期 计算机与数字工程 VOl_36NOq.42008年第 4期 Computer&Digital Engineering ...
  • 上面的这几个视频对学习图像压缩都有很大的帮助,建议看一看。 分割线-------------------------------------------- 思路参考,这篇不错 我的代码与课本代码的区别在于求最优解,我实在想不明白为什么后面每个分割...
  • ​ 考虑如下数据压缩技术。我们有一个表存了m个文本串,每个长度至多为k。我们想对一个长为n的数据串D使用尽可能少的文本串来编码。例如,如果我们的表包含(“a”,“ba”,“abab", “b"), 且数据串为“bababbaababa...
  • 状态压缩前的代码如下。 dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < length; i++) { dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]); } return dp[length - 1]; i-2...
  • 原标题:图像处理之动态范围压缩1、动态范围压缩介绍自然界中真实场景能够表现比较广泛的颜色亮度区间,比如从很暗(10^-5 cd/m2)的黑夜到明亮(10^5 cd/m2)的太阳光,有将近10个数量级的动态方位。而传统显示设备所能...
  • Matlab的图像压缩技术

    2021-04-24 15:29:23
    -Matlab的图像压缩技术一.目的要求掌握Matlab图像图像压缩技术原理和方法。理解有损压缩和无损压缩的概念,了解几种常用的图像压缩编码方式,利用matlab进行图像压缩算法验证。二.实验内容1、观察颜色映像矩阵的...
  • 小波变换是在短时傅里叶变换的基础上发展起来的一种新型变换方法,他是一种时—...小波变换由于具有很好的时—频特性而且可以匹配人类视觉系统的特性,因而得到图像压缩编码领域的极大关注。小波分析在图像领域的应...
  • 摘要:该文借鉴静态图像压缩标准JPEG的理论研究成果,将其与DCT快速变换相结合,采用霍夫曼编码方法,用C语言编程实现灰度图像压缩。最后,计算了基于DCT快速变换的图像压缩算法的压缩比。同时,分析了DCT快速变换...
  • 实验5 图像压缩一.实验目的:1.掌握图像压缩的原理——编码冗余,压缩比C R的计算等。2.了解并掌握霍夫曼编码的原理、实现步骤。3.掌握JPEG标准——通用的图像压缩/解压缩编码标准。二.实验内容:1.利用已给出...
  • 图像压缩算法

    千次阅读 2021-06-03 21:26:58
    图像压缩 图像压缩算法是对图像在资源空间上的压缩,每一个色块的颜色可以粗略的由红、绿、蓝的各自三个不同的深度合成得来。 那么,如果我们每一个颜色的程度用8位的二进制码来表示,最终需要24m2大小的空间(这里...
  • 2011 基于DCT的图像压缩AMATLAB实现 (贵州大学理学院,贵州贵阳55闐25) 摘要:介绍JPEG图像压缩算法,并在MATLAB数学分析工具环境下从实验角度出发,较为直观地探讨了DCT在JPEG图像压缩中的应用。仿真实验表明,用...
  • 基于DCT的图像压缩编码算法的MATLAB实现 摘要 随着科学技术的发展,图像压缩技术越来越引起人们的关注。为此从众多的图像压缩编码标准中选取了基于DCT变换的JPEG图像压缩编码算法进行研究,并通过对比分析各种软件...
  • 图像压缩基础知识

    2021-11-18 08:50:41
    图像压缩的概念 减少表示数字图像时需要的数据量 从本质上看,无损压缩的方法可以删除一些重复数据,大大减少要在磁盘上保存的图像尺寸。但是,无损压缩的方法并不能减少图像的内存占用量,这是因为,当从磁盘上...
  • 开发与应用 计算机与信息技术 ·23· 基于 Matlab 的图像压缩编码 杨晓 李悦 (贵州大学 计算机与信息学院,贵州 贵阳 550025) 摘 要 本文描述了图像编码压缩方法的主要分类,介绍了每个分类里面的典型算法的原理、...
  • 基于调制自编码器的多压缩图像压缩 公式化 基于端到端模型,扩展优化问题表示: 其中是添加了均匀噪声的瓶颈表示,其中尺度参数。所以,,即作为模型参数(不可训练的)出现,决定压缩效果。 瓶颈缩放(scaling)...
  • 本文主要介绍了基于哈夫曼编码图像压缩技术的原理、算法、过程,并利用matlab作为编程开发工具,开发了一个对256色BMP图像进行压缩.解压缩的软件系统,验证了算法的合理性和可行性. 为了节省空间,在对数据进行编码时,...
  • 这种格式的特点是包含的图像信息较丰富,几乎不进行压缩,但由此导致了它与生俱生来的缺点--占用磁盘空间过大。所以,目前BMP在单机上比较流行。 2、GIF格式 GIF是英文Graphics Interchange ...
  • 数字图像处理——第八章 图像压缩

    千次阅读 热门讨论 2021-05-12 23:08:30
    文章目录数字图像处理——第八章 图像压缩1 图像压缩1.1 为啥要图像压缩1.2 为啥能图像压缩1.2.1 编码冗余1.2.2 空间冗余1.2.3 时间冗余2 一些基本的压缩方法2.1 霍夫曼编码2.2 行程编码2.3 算数编码2.4 LZW编码3 ...
  • 图像压缩与编码及MATLAB实现近年来,随着计算机通信技术的迅速发展,特别是多媒体网络技术的兴起,图像压缩与编码已受到了人们越来越多的关注。 图像压缩与编码从本质上来说就是对要处理的图像按一定的规则进行变换...
  • python环境下用opencv压缩图片尺寸,用python语言...python环境下用opencv压缩图片尺寸,用python语言引入poencv的方法,实用PIL处理图像比用OPENCV更好用。opencv通常是用来采集视频图像和图片的。数字图像处理怎么...
  • RGB=imread('C:\Users\lenovo\Desktop\1.jpg');%读取图片RGB=imresize(RGB,[168,224]);%因为1.jpg大小为169*220,所以我改为168*224... %保存压缩图像%下面是对RGB三个分量进行分离,此时他们依然为整数R=RGB(:,...
  • 一、简介 1974年,法国工程师J.Morlet首先提出小波变换的概念,1986年著名数学家Y.Meyer偶然构造出一个真正的小波基,并与S.Mallat合作建立了构造小波基的多尺度分析之后,小波分析才开始...在图像处理方面的图像...
  • 近年来,随着计算机通信技术的迅速发展,特别是多媒体网络技术的兴起,图像压缩与编码已受到了人们越来越多的关注。 图像压缩与编码从本质上来说就是对要处理的图像按一定的规则进行变换和组合,从而达到以尽可能少...
  • • Fundamentals • Image Compression Models • Error-Free Compression • Lossy Compression有损压缩 • Image Compression Standards
  • 介绍了JPEG图像压缩算法,并在MATLAB数学分析工具环境下从实验角度出发,较为直观地探讨了DCT在JPEG图像压缩中的应用.仿真实验表明,用MATLAB来实现离散余弦变换的图像压缩,具有方法简单,速度快,误差小的优点,大大提高...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 210,139
精华内容 84,055
关键字:

图像压缩动态规划