精华内容
下载资源
问答
  • matlab图像压缩编码.rar

    2019-12-02 11:09:06
    Matlab实现常用图像压缩编码。包含DM编码、变换编码(FFT和DCT)、算术编码、行程编码、Huffman编码、线性预测编码和一个近似的JPEG编码过程
  • 用MATLAB做的基于霍夫曼编码的图像压缩,里面有个文件时专门的霍夫曼编码函数,自己写的。
  • 本文首先介绍了静态图像压缩(JPEG)编码算法的基本原理、压缩的实现过程及其重要过程的离散余弦变换(DCT)算法的实现原理及软件实现的例程,其次着重介绍了压缩过程中的DCT、量化和编码三个重要步骤的实现原理。
  • 图象压缩(JPEG)编码算法及压缩过程的实现,本文比较详细的介绍了JPEG图像压缩算法,比较不错
  • 图像压缩编码

    2016-07-24 19:36:24
    常用图像压缩编码码matlab实现。包括:DM编码、变换编码(FFT和DCT)、算术编码、行程编码、Huffman编码、线性预测编码和一个近似的JPEG编码过程。非常适合入门用户实践。
  • 图像压缩之算术编码

    千次阅读 2019-04-15 10:43:15
    JPEG中使用了量化、哈夫曼编码等,极大的压缩了图片占用的空间,那么是否可以进一步压缩呢? 从技术角度讲,是可以的。如DropBox开源的lepton,在目前的JPEG压缩基础上,可以再节省22%左右的空间。 lepton中使用算术...

    JPEG中使用了量化、哈夫曼编码等,极大的压缩了图片占用的空间,那么是否可以进一步压缩呢?
    从技术角度讲,是可以的。如DropBox开源的lepton,在目前的JPEG压缩基础上,可以再节省22%左右的空间。
    lepton中使用算术编码(VP8)替换哈夫曼编码,以得到更高的压缩率。算术编码90年代已经出现,但是受限于专利,没有被广泛使用。同样由于专利限制没有广泛使用的还有gif中的压缩编码lzw。


    下面介绍一下,算术编码的基本原理和过程。


    算术编码(  Arithmetic coding )发展历史
    1948 年,香农就提出将信源符号依其出现的概率降序排序,用符号序列累计概率的二进值作为对信源数据的编码,并从理论上论证了它的优越性。
    1960 年,  Peter Elias 发现无需排序,只要编、解码端使用相同的符号顺序即可,提出了算术编码的概念。  Elias 没有公布他的发现,因为他知道算术编码在数学上虽然成  立,但不可能在实际中实现。
    1976 年,  R. Pasco 和  J. Rissanen 分别用定长的寄存器实现了有限精度的算术编码。
    1979 年  Rissanen 和  G. G. Langdon 一起将算术编码系统化,并于  1981 年实现了二进制编码。
    1987 年  Witten 等人发表了一个实用的算术编码程序,即  CACM87 (后用  于  ITU-T 的  H.263 视频压缩标准)。同期,  IBM 公司发表了著名的  Q- 编码器(后用于  JPEG 和  JBIG 图像压缩标准)。从此,算术编码迅速得到了广泛的注意。

    算术编码介绍
    算术编码是一种无损数据压缩方法,也是一种熵编码的方法。
    一般的熵编码方法通常是把输入的消息分割为符号,然后对每个符号进行编码。而算术编码将整个要编码的数据映射到一个位于  [0,1) 的实数区间中。利用这种方法算术编码可以让压缩率无限的接近数据的熵值,从而获得理论上的最高压缩率。

    算术编码用到两个基本的参数:符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率,也决定编码过程中信源符号的间隔,而这些间隔包含在  0 到  1 之间。编码过程中的间隔决定了符号压缩后的输出。

    算术编码可以是静态的或者自适应的。
    在静态算术编码中,信源符号的概率是固定的。在自适应算术编码中,信源符号的概率根据编码时符号出现的频繁程度动态地进行修改,在编码期间估算信源符号概率的过程叫做建模。
    需要开发动态算术编码的原因是因为事先知道精确的信源概率是很难的,而且是不切实际的。当压缩消息时,我们不能期待一个算术编码器获得最大的效率,所能做的最有效的方法是在编码过程中估算概率。因此动态建模就成为确定编码器压缩效率的关键。

    算术编码思想
    算术编码的基本原理是将编码的消息表示成实数  0 和  1 之间的一个间隔(  Interval ),消息越长,编码表示它的间隔就越小,表示这一间隔所需的二进制位就越多。

    算术编码进行编码时,从实数区间  [0,1) 开始,按照符号的频度将当前的区间分割成多个子区间。根据当前输入的符号选择对应的子区间,然后从选择的子区间  中继续进行下一轮的分割。不断的进行这个过程,直到所有符号编码完毕。对于最后选择的一个子区间,输出属于该区间的一个小数。这个小数就是所有数据的编码。

    给定事件序列的算术编码步骤如下:
    ( 1 )编码器在开始时将  “ 当前间隔  ” [ L ,  H)  设置为  [0 ,  1) 。
    ( 2 )对每一个输入事件,编码器按下边的步骤(  a )和(  b )进行处理
    ( a )编码器将 “  当前间隔 ” 分为子间隔,每一个事件一个。一个子间隔的大小与将出现的事件的概率成正比
    ( b )编码器选择与下一个发生事件相对应的子间隔,并使它成为新的  “ 当前间隔  ” 。
    ( 3 )最后输出的  “ 当前间隔  ” 的下边界就是该给定事件序列的算术编码。

    在算术编码中需要注意几个问题:
    ( 1 )由于实际计算机的精度不可能无限长,运算中出现溢出是一个明显的问题,但多数及其都有  16 位,  32 位或者  64 位的精度,因此这个问题可以使用比例缩放方法解决。
    ( 2 )算术编码器对整个消息只产生一个码字,这个码字是在间隔  [0,1) 中的一个实数,因此译码器在接受到表示这个实数的所有位之前不能进行译码。
    ( 3 )算术编码是一种对错误很敏感的编码方法,如果有一位发生错误就会导致整个消息译错。

    算术编码伪代码
    定义一些变量,设  Low 和  High 分别表示  “ 当前间隔  ” 的下边界和上边界;
    CodeRange 为编码间隔的长度,即 " 当前间隔  " 的长度;
    LowRange(symbol) 和 HighRange(symbol)  分别代表为了事件  symbol 的编码间隔下边界和上边界。

    如果 symbol 的编码间隔固定不变,则为静态编码;
    反之,如果  symbol 的编码间隔随输入事件动态变化,则为自适应编码。

    算术编码的编码过程可用伪代码描述如下:
    set Low to 0
    set High to 1
    while there are input symbols do
        take a symbol
        CodeRange = High – Low
        High = Low + CodeRange *HighRange(symbol)
        Low = Low + CodeRange * LowRange(symbol)
    end of while
    output Low
     

    算术编码解码过程用伪代码描述如下:
    get encoded number
    do
        find symbol whose range straddles the encoded number
        output the symbol
        range = symbo.LowValue – symbol.HighValue
        substracti symbol.LowValue from encoded number
        divide encoded number by range
    until no more symbols

    静态的算术编码
    算术编码器的编码解码过程可用例子演示和解释。
    例 1 :假设信源符号为  { A  ,  B  ,  C  ,  D}  ,这些符号的概率分别为  {  0.1 ,  0.4 ,  0.2 ,  0.3 } ,根据这些概率可把间隔  [0 ,  1] 分成  4 个子间隔:  [0 ,  0.1] ,  [0.1 ,  0.5] ,  [0.5 ,  0.7] ,  [0.7 ,  1] ,其中  [x ,  y] 表示半开放间隔,即包含  x 不包含  y 。上面的信息如下表。

      信源符号,概率和初始编码间隔
    符号
    A
    B
    C
    概率
    0.1
    0.4
    0.2
    0.3 
    初始编码间隔
    [0, 0.1)
    [0.1, 0.5)
    [0.5, 0.7)
    [0.7, 1] 

    如果二进制消息序列的输入为:  C A D A C D B 。
    编码时首先输入的符号是  C ,找到它的编码范围是  [0.5 ,  0.7] 。由于消息中第二个符号  A 的编码范围是  [0 ,  0.1] ,因此它的间隔就取  [0.5 ,  0.7] 的第一个十分之一作为新间隔  [0.5 ,  0.52] 。
    依此类推,编码第 3 个符号  D 时取新间隔为  [0.514 ,  0.52] ,编码第  4 个符号  A 时,取新间隔为  [0.514 ,  0.5146] ,  … 。
    消息的编码输出可以是最后一个间隔中的任意数。整个编码过程如下图所示。

         算术编码过程举例

      取一个  (0.5143876~0.514402) 之间的数: 0.5143876 
       (0.5143876)D ≈  (0.1000001)B ,去掉小数点和前面的  0 ,得  1000001 。   
      所以:  cadacdb 的编码  =1000001 ,长度为  7 。

    十进制小数转换为二进制参考:点击打开链接

    编码和译码的全过程分别表示如下。   
      编码过程
    步骤
    输入符号
    编码间隔   
    编码判决
    1
    C
    [0.5, 0.7]
    符号的间隔范围[0.5, 0.7] 
    2
    A
    [0.5, 0.52]
    [0.5, 0.7]间隔的第一个1/10
    3
    D
    [0.514, 0.52]
    [0.5, 0.52]间隔的最后一个1/10
    4
    A
    [0.514, 0.5146]
    [0.514, 0.52]间隔的第一个1/10
    5
    C
    [0.5143, 0.51442]
    [0.514, 0.5146]间隔的第五个1/10开始,二个1/10
    6
    D
    [0.514384, 0.51442]
    [0.5143, 0.51442]间隔的最后3个1/10
    7
    B
    [0.5143836, 0.514402]
    [0.514384,0.51442]间隔的4个1/10,从第1个1/10开始
    8
    从[0.5143876, 0.514402]中选择一个数作为输出:0.5143876
     
                             表  译码过程
    步骤
    间隔
    译码符号   
    译码判决   
    1
    [0.5, 0.7]
    C
    0.51439在间隔 [0.5, 0.7)
    2
    [0.5, 0.52]
    A
    0.51439在间隔 [0.5, 0.7)的第1个1/10
    3
    [0.514, 0.52]
    D
    0.51439在间隔[0.5, 0.52)的第7个1/10
    4
    [0.514, 0.5146]
    A
    0.51439在间隔[0.514, 0.52]的第1个1/10
    5
    [0.5143, 0.51442]
    C
    0.51439在间隔[0.514, 0.5146]的第5个1/10
    6
    [0.514384, 0.51442]
    D
    0.51439在间隔[0.5143, 0.51442]的第7个1/10
    7
    [0.51439, 0.5143948]
    B
    0.51439在间隔[0.51439,0.5143948]的第1个1/10
    8
    译码的消息:C A D A C D B

    在上面的例子中,我们假定编码器和译码器都知道消息的长度,因此译码器的译码过程不会无限制地运行下去。实际上在译码器中需要添加一个专门的终止符,当译码器看到终止符时就停止译码。

    为什么说算术编码压缩率更高?
    算术编码可以对一个二进制序列进一步编码,得到比原序列更小的编码结果。

    例如,假设二进制序列信源符号为  { 1,0}  ,如果消息序列的输入为  1101  。   
      则符号  1 和  0 的概率分别为  :  符号  1 的概率  3/4 ,符号  0 的概率  1/4  。整个编码过程如图所示。


    算术编码的结果:
    下界 =121/256  ,即 0.47265625  或二进制 0.0111 ;
    上界为 37/64  ,即 0.578125  或二进制 0.10010 。

    在该区间范围内任取一个数,例如  0.5 (对应二进制  0.1 ),只取小数点后边的部分,即  1 。   
    这样,原来的 1101  序列就可以用编码  1 来代替。   

    自适应的算术编码
    自适应模型中,在编码开始时,各个符号出现的概率相同,都为  1/n 。随着编码的进行再更新出现概率。另外,在计算时理论上要使用无限小数。这里为了说明方便,四舍五入到小数点后  4 位。

    举个例子来说明自适应算术编码。
    假设一份数据由 “A”  、 “B”  、 “C”  三个符号组成。现在要编码数据  “BCCB” ,编码过程如图所示。



    ( 1 )算术编码是从区间 [0,1) 开始。这时三个符号的概率都是  1/3 ,按照这个概率分割区间。
    ( 2 )第一个输入的符号是 “B” ,所以我们选择子区间  [0.3333,0.6667) 作为下一个区间。
    ( 3 )输入 “B”  后更新概率,根据新的概率对区间  [0.3333,0.6667) 进行分割。
    ( 4 )第二个输入的符号是 “C” ,选择子区间  [0.5834,0.6667) 。
    ( 5 )以此类推,根据输入的符号继续更新频度、分割  区间、选择子区间,直到符号全部编码完成。

    我们最后得到的区间是 [0.6390,0.6501) 。输出属于这个区间的一个小数,例如  0.64 。那么经过算  术编码的压缩,数据  “BCCB” 最后输出的编码就是  0.64 。

    自适应模型的解码
    算术编码进行解码时仅输入一个小数。整个过程相当于编码时的逆运算。解码过程是这样:
    ( 1 )解码前首先需要对区间  [0,1) 按照初始时的符号频度进行分割,然后观察输入的小数位于哪个子区间,输出对应的符号。
    ( 2 )之后选择对应的子区间,然后从选择的子区间中继续进行下一轮的分割。
    ( 3 )不断的进行这个过程,直到所有的符号都解码出来。

    在我们的例子中,输入的小数是  0.64 。
    ( 1 )初始时三个符号的概率都是  1 / 3 ,按照这个概率分割区间。
    ( 2 )根据上图可以发现 0.64 落在子区间  [0.3333,0.6667) 中,于是可以解码出  "B" ,并且选择子区间  [0.3333,0.6667) 作为下一个区间。
    ( 3 )输出 “B”  后更新频度,根据新的概率对区间  [0.3333,0.6667) 进行分割。
    ( 4 )这时 0.64  落在子  区间  [0.5834,0.6667) 中,于是可以解码出  “C” 。
    ( 5 )按照上述过程进行,直到所有的符号都解码出来。
    可见,只需要一个小数就可以完整还原出原来的所有数据。

    自适应模型的整数编码方式
    上边介绍的编码都是得到一个  [0,1)  内的小数,下面说明整数编码方式,以  8 位编码为例,阐述算术编码和解码过程  .

    例如对字符串 "ababcab"  进行编解码,最终得到  8 位编码。
    确定上下界:由于 8 位的取值范围是  [0,255] ,因此下界为  0 ,上界为  255  。
    符号概率:编码开始时,  a 、  b 、  c 的出现概率都是  1/3  。

    编码过程
    ( 1 ) "ababcab"  第 1  个字符为 a ,初始化时三个字符出现概率相同,因此  a 的编码间隔为  [0,1/3] ,即  LowRange(a) = 0, HighRange(a) = 1/3
    ( 2 )更新上下界的值为  [0, 85] ,根据伪代码:
        CodeRange = High – Low
        High = Low + CodeRange *HighRange(symbol)
        Low = Low + CodeRange * LowRange(symbol)
    计算得到:
    CodeRange = 255 - 0 = 255
    High = 0 + 255 * 1/3 = 85
    Low = 0 + 255 * 0 = 0

    此时各个符号的编码间隔动态调整为:  a :  [0, 2/4] ,  b  :  [2/4, 3/4] , c :  [3/4, 1]

    ( 3 )  "ababcab" 第 2 个字符为 b  ,取编码间隔  [2/4, 3/4] ,并更新上下界:
    CodeRange = 85 - 0 = 85
    High = 0 + 85 * 3/4 = 63    (向下取整)
    Low = 0 + 85 * 2/4 = 43    (向上取整)

    ( 4 )同理可得到  "ababcab" 第 3 、 4 个字符 a  、 b  的编码。
    ( 5 )计算 "ababcab"  第 5  个字符 c 的编码,此时  High=49 ,  Low=49 。因为是有限整数,每次又是取的上一区间的子区间  ,high 和  low 趋于相等是必然的。

      8  位编码过程

    我们在此使用 High  和 L ow  向左移的方式进行扩大区间
    极限情况:位移后 Low 的二进制首位为  0 ,其他位为全  1 ;  High 的二进制首位为  1 ,其他位为全  0 。如  8 位时:  Low=01111111B ,  High=10000000B 的情况。
    出现这种情况时,我们可以规定,保留相同位,并将该区间扩展至原始区间,如  8 位是  [0, 255) ,  32 位是  [0, 0xffffffff) 。

    位移时遵循两个原则  :
    (1)  设  Total 为字符表中的字符数  + 已出现的字符数(即编码间隔的分母),需保证  High-Low>=total ,否则继续位移
    (2)  保证  [Low, High] 在上一个  [Low, High] 的子区间。  ( 实际上这条已经在取整运算时得到了保证  )

    上下界左移  1 位后溢出位用新变量  out 存储,同时,用  bits 保存  out 到底存了几个位。  (0B 表示二进制  0)
    位移轮数
    Total
    Out
    Bits
    High
    Low
    1
    7
    0 B
    1
    98 (49<<1)
    94 (47<<1)
    2
    7
    00B
    2
    196 (98<<1)
    188 (94<<1)

    此时满足两条  " 位移原则  " ,继续编码。

      位移和继续编码

    编码第 6 个字符  a 和第  7 个字符  b ,分别需要位移  3 次和  2 次。
                          编码第 6 个字符  a 时位移 3
    位移轮数
    Total
    Out
    Bits
    High
    Low
    1
    8
    0 01B
    3
    136
    134
    2
    8
    00  11B
    4
    16 (136<<1)
    12 (134<<1)
    3
    8
    00110B
    5
    32
    24

          编码第 7 个字符  b 时位移 2
    位移轮数
    Total
    Out
    Bits
    High
    Low
    1
    9
    0 01100B
    6
    54
    48
    2
    9
    00  11000B
    7
    108
    96

    编码结束时最后的区间是  [102, 105] ,后面已经没有字符,不需要位移了。记下此区间的某一个数即可,这里选  magic=104 。

    整个编码过程结束,得到编码结果:
    out=0011000B ,  bits=7 ,  magic=104 。

    编码全过程如图
      
      编码全过程

    解码过程
    根据编码结果:  out=0011000B ,  bits=7 ,  magic=104 。(  Total=9 可选)
    将 magic 转换为  8 位二进制,拼在  out 后,得到  15 位数:
    X = out<<8 | magic = 0011000 01101000B 

    ( 1 )取  X 的高  8 位,令  z = 00110000B = 48;
    ( 2 )  48 是  a 所在区间,于是解码得到字符  "a"
    ( 3 )更新上下界为 [0, 85]  ,更新各符号的编码间隔  a :  [0, 2/4] ,  b  :  [2/4, 3/4] ,  c :  [3/4, 1]
    ( 4 )满足位移原则 1  ,不需要位移,继续解码。  48 是  b 所在区间,解码得到字符串  "ab" 。更新上下界和编码间隔;
    ( 5 )继续解码得到字符串 ”abab” ,此时上下界为  [47, 49] ,不满足位移原则  1 ,需要位移;
    ( 6 )去掉 z  的首位,即左边第一位;取  X 中下一位接到  z 右边,得到  z = 01100001B = 97 。 
    Total=7 ,上下界 [94, 98]  ,不满足原则  1 ,继续位移得到  z = 11000011B = 195 ; 
    满足原则 1 ,继续解码;
    ( 7 ) 195 是 c 所在区间,解码得到字符串  "ababc" ;
    ( 8 )此时需要位移,位移 3 次,得到  z = 00001101B = 25 ,解码得到字符串  "ababca" ;
    ( 9 )此时需要位移,位移 2 次,  Total=9 ,上下界  [96, 108) ,满足位移原则  1 。 
    但是 z = 00110100B = 52 ,不在上下界范围内,于是  z 位移  z = 01101000B = 104 ( 到达 X 末尾  ) ; 
    解码得到字符串  "ababcab" ;
    ( 10 )此时需要位移,位移 1 次,上下界为  [152, 164) ,满足位移原则  1 。 
    但是 z = 01101000B = 104 ,不在上下界范围内,  z 需要位移。此时  X 已经到达末尾,  z 不能继续位移,此时编码结束。 
    (若编码结果中有  Total=9 信息,在上一步就可以结束)


    JPEG 中为什么没有使用算术编码
    因为算术编码的使用存在版权问题。
    JPEG 标准说明的算术编码的一些变体方案属于  IBM ,  AT&T 和  Mitsubishi 拥有的专利。要合法地使用  JPEG 算术编码必须得到这些公司的许可。
    像 JPEG 这种开源的标准,虽然传播广泛,但是大家都是免费在用,明显没有钱买那么贵的专利。
    参考


    转自:https://blog.csdn.net/shelldon/article/details/54234436
    展开全文
  • JPEG图像压缩编码

    2017-09-26 21:20:15
    提供了详细的Matlab编解码过程和程序,包括图片格式转换,零偏置转化,DCT变换,量化,AC系数编码,Z扫描,DC系数编码,JPEG解码,DCT反变换,图像重构等全部函数和实现过程
  • 二维行程编码对图像压缩和解压。利用线性四叉树的结构编写morton码和像素灰度值,然后存成一个线性表,就可以进行无损压缩
  • 魏洪涛 工作单位 信息工程学院 题 目: 通信工程应用技术综合训练与实习 初始条件MATLAB软件平台 设计任务与要求: 图像通信之前需要进行数据量压缩编程实现JPEG图像压缩标准的主要环节完成压缩和解压过程计算压缩比 ...
  • 基于Matlab的图像压缩编码

    热门讨论 2010-03-23 15:56:44
    该程序的编码部分能把一张BMP格式的图象进行JEPG编码压缩成以二进制形式保存的文件;通过相应的解码程序又可以把图象解压缩出来。在图象传送过程中,我们经常采用JPEG格式对静态图象进行编码。JPEG基本系统是一种...
  • python版本为2.7.9,大家注意别下错了,里面有一个txt文件是进行压缩的,可以更改文件中的变量path1来对其他文件进行压缩与解压,代码中有详细注释,实现过程虽然简单,但是包含自己很多一些独特的想法,自己的知识...
  • 行程编码,JPEG压缩编码(基本系统)的源码示例,对了解低层图像编码有重要意义,命令行编译过程如下: vcvars32 rc bmp.rc cl compress.c bmp.res user32.lib gdi32.lib 注意事项: 运行时,文件c:\test.pcx;...
  • 讲述视频压缩和预测编码的基本原理及现有的视频压缩标准
  • 空间光调制过程是空间编码压缩光谱成像方法中影响光谱成像数据保真度的重要环节。为拓展现有压缩光谱成像空间光调制的编码种类,揭示其与成像数据保真度的关联规律,针对压缩光谱成像中的编码调制效应展开研究。基于...
  • 基于MATLAB的图像压缩程序(包含各种压缩编码与解码方法),算法包含详细代码,是图像编码技术的总结
  • 图像处理 有损压缩-变换编码

    千次阅读 2020-06-12 11:41:06
    变换编码是对诸如音频信号或摄影图像之类的“自然”数据进行数据压缩的一种类型。 转换通常本身是无损的(完全可逆的),但可用于实现更好的(更有针对性的)量化,从而导致原始输入的质量降低(无损压缩)。 压缩...

    变换编码概念

    变换编码或称转换编码,对诸如音频信号或摄影图像之类的“自然”数据经过一数学转换后映射至另一值域后再进行编码处理。常用于音频信号编码和图像/视频信号编码。变换编码经常与量化一起使用,进行有损数据压缩。因为转换通常本身是无损的(完全可逆的),但可用于实现更好的(更有针对性的)量化,从而导致原始输入的质量降低(无损压缩)。

    在视频和音频信号数字化后,变换编码就更常用了。从最常见的JPEG静止图像压缩标准到MPEG等运动图像压缩标准,都使用了变换编码。

    常用的变换

    常使用的数学转换傅里叶变换、离散余弦变换、小波变换等。

    最常用的变换是离散余弦变换(DCT),其次还有小波变换、Hadamard变换等等。离散余弦变换在性能上接近K-L变换(Karhunen-Loève变换),能够很好的实现能量集中,广泛的应用于几乎所有的视频压缩标准中。

    另外,也可以说从模拟信号抽样得到数字信号的过程也是一种变换编码。

    压缩变换编码目的

    将数据(图像/视频)转换成易于压缩的形式。

    压缩变换示例

    2*2像素

    AB
    CD

    原格式

    像素点存储位数 (Bits)
    A8
    B8
    C8
    D8
    Total32

    变换过程

    变换逆变换
    X0 = AA = X0
    X1 = B -AB = X1 + X0
    X2 = C - AC = X2 + X0
    X3 = D - AD = X3 + X0

    变换后

    像素点存储位数 (Bits)
    A = X08
    B = X1 + X04
    C = X2 + X04
    D = X3 + X04
    Total20

    特征

    • 一种有损压缩技术
    • 通常用于转换“自然”数据,例如音频信号或摄影图像。
    • 从数据中删除REDUNDANCY
    • 降低数据的带宽
    • 用较少的数据形成图像
    • JPEG是变换编码的实例
    展开全文
  • 数据压缩编码理论

    2015-09-22 16:45:40
    二进制算术编码、解码的实现。利用java语言完成二进制算术编码,作者将其打包成exe文件。测试很好 C盘创建Liyicheng 文件夹,其中放置测试文件...终端会显示编码 解码的过程 可以改变测试文件的内容进行不同的测试。
  • 压缩算法之算术编码

    万次阅读 多人点赞 2017-09-14 22:24:04
    编码 香农范诺(Shannon)编码 霍夫曼(Huffman)编码 算术编码(arithmeticcoding)

        前几天,我们在课堂上学习数字媒体技术的时候,学习了音频压缩算法。针对音频我们有无损和有损


        今天我们来研究一下无损压缩,一般来说,采取的无损压缩算法都是熵编码算法(即在编码过程中按熵原理不丢失任何信息的编码),主要的无损压缩编码有以下几种:

    • 香农范诺(Shannon)编码
    • 霍夫曼(Huffman)编码
    • 算术编码(arithmeticcoding)

        以上的三种算法中,前两种我先找机会说(老师在课上给我们讲过原理,没讲过代码实现,但是把第三种作为作业,,,尴尬),今天我们主要目光是聚焦在第三种上,即算术编码的原理及其代码实现


        好,那么我们言归正传,来将这个算术编码一探究竟——




    一、算术编码的历史

        (以下的这一段落copy自csdn)

        早在1948年,香农就提出将信源符号依其出现的概率降序排序,用符号序列累计概率的二进值作为对芯源的编码,并从理论上论证了它的优越性。1960年, Peter Elias发现无需排序,只要编、解码端使用相同的符号顺序即可,提出了算术编码的概念。Elias没有公布他的发现,因为他知道算术编码在数学上虽然成 立,但不可能在实际中实现。1976年,R. Pasco和J. Rissanen分别用定长的寄存器实现了有限精度的算术编码。1979年Rissanen和G. G. Langdon一起将算术编码系统化,并于1981年实现了二进制编码。1987年Witten等人发表了一个实用的算术编码程序,即CACM87(后用 于ITU-T的H.263视频压缩标准)。同期,IBM公司发表了著名的Q-编码器(后用于JPEG和JBIG图像压缩标准)。从此,算术编码迅速得到了广泛的注意。




    二、算术编码的原理

      A、编码

        算术编码的基本原理是将编码的消息表示成实数0和1之间的一个间隔(Interval),消息越长,编码表示它的间隔就越小,表示这一间隔所需的二进制位就越多。

        (一)步骤

        这样说起来可能有点抽象,说的好理解一点实际上就是

    1. 首先的准备工作——按照各信源信号好出现的频率,将[0, 1)这个区间分成若干段,那么每个信号源就会有自己对应的区间了;
    2. 将[0, 1)这个区间设置为初始间隔;
    3. 然后编码过程就是,按照待处理的信号,一个一个信号源读入,每读入一个信号,就将该信号源在[0, 1)上的范围等比例的缩小到最新得到的间隔中。
    4. 然后依次迭代,不断重复进行步骤3,直到最后信号中的信源信号全部读完为止;

        (二)伪代码

        该过程编码的伪代码如下:

        set lowLevel = 0
        set highLevel = 1
        input symbol 
        do 
            delta = highLevel - lowLevel
            lowLevel = lowLevel + delta * symbol[i].lowLevel
            highLevel = highLevl + delta * symbol[i].highLevel
        while symbol traversed
        output lowLevel


       (三)例题

        可能还是会有点抽象,有点不好理解,那么我们看一个实例(实例同样来自csdn),通过实例来对这个算法进行理解:

        假设信源信号有{A, B, C, D}四个,他们的概率分别为{0.1, 0.4, 0.2, 0.3},如果我们要对CADACDB这个信号进行编码,那么应该怎样进行呢?

        解:首先,我们做好准备工作,按照信源信号的频率为将[0, 1)分解成为若干区间。那么这一步骤完成之后,我们得到以下的表格:

    no

        准备工作完成之后,我们便可以开始进行编码了。

        那么我们首先读入信号:C——因为C在最初始的间隔中是[0.5, 0.7),所以读入C之后我们的编码间隔就变成[0.5, 0.7)了;

        紧接着,我们读入的是A,A在初始区间内是占整个区间的前10%,因此对应这个上来也是需要占这个编码间隔的前10%,因此编码区间变为:[0.5, 0.52)了;

        再然后是D,因为D占整个区间的70% ~ 100%,所以也是占用这个编码区间的70% ~ 100%,操作后的编码区间为[0.514, 0.52)

        ……

        直到最后将信号量全部读出。


        最后,我们将这个操作过程绘制成为一张表:

    no




      B、解码

        解码的过程其实和编码的过程恰恰相反,解码是给定一个[0, 1)中的浮点数,通过解码操作之后就能完全获得原始的信号串。

        (一)步骤

    1. 待解码的数据,首先我们仍然需要在编码时候的那项准备工作,即获取创建一个编码解码表,但是由于我们是在同一个类中完成的,那么我们把该对应表作为类的一个属性就可以实现获取表了;
    2. 准备工作完成之后,我们就可以开始正式的解码工作了,首先判断待解码的数据在哪个范围内,将该范围对应的信源信号输出即可;
    3. 重复步骤2,按理说,按照这样的方法,解码会一直进行下去,无穷不尽,直到达到计算机的精度为止,那么为了正确的进行解码,我们需要对解码的次数进行限定,即我们首先需要事先知道,解码后的信源信号的长度,然后在进行解码,这样才能比较完美的进行解码。


        (二)伪代码

        解码过程可以由以下的伪代码实现:

        input code
        do 
            find the Interval which contains the code
            set range = highLevel - lowLevel
            set code = (code - lowLevel) / range
        while times out


       (三)例题

        我们以上述的那个题目为例:

        假设信源信号有{A, B, C, D}四个,他们的概率分别为{0.1, 0.4, 0.2, 0.3},当我们得到的编码是0.5143876的时候,问原始的信号串(7位)是怎样的?

        解:首先,我们做好准备工作,按照信源信号的频率为将[0, 1)分解成为若干区间。那么这一步骤完成之后,我们得到以下的表格:

    no

        准备工作完成之后,我们现在开始解码:

        我们发现,待解码的数据0.5143876在[0.5, 0.7)内,因此,我们解出的第一个码值为C

        同理,我们继续计算0.5143876处于[0.5, 0.7)的第一个10%内因此解出的第二个码值为A

        ……

        这个过程持续直到执行七次全部执行完为止。


        那么以上的过程我们同样可以列表表示:

    no



    三、编码实现

        那么,我们现在算是理解这个算法了,那么应当怎样通过代码来实现这一算法呢?

        我们先将这个算法的类抽象出来:

    /**
    * @author Mica_Dai
    * @Date Sept 13 2017
    */
    
    // 算术编码类
    class Arithmeticcoding
    {
    public:
        Arithmeticcoding(){
            length = 0;
        }
        ~Arithmeticcoding(){}
    
        // 获取编码,实际上就是创建对应表
        void requirecode();
        double encode(string str);
        string decode(double value);
        int getLength();
    
    private:
        // 这个length是字符串的长度
        int length;
        std::map<char, Range> map;
    };
    


        主要的问题有以下几点:

    • 按照步骤,我们首先应当输入信源信号以及其对应的频率,相当于建立了一个对应的编码解码库;
    • 怎样进行这个算法的操作

        对于第一个问题,我采取的是使用C++的关联容器类map来创建这个编码解码库,map翻译成中文就是映射,相当于就是我们创建一个信源信号与对应频率之间的映射,这样我们在获取信源信号的时候就能够直接获取该信源信号对应的概率了。但是考虑到在算法进行的过程中,参与计算的并不是该信源信号的概率,而是该信源信号的区间上下界;因此,我索性创建一个类用于存放区间上下界,从而创建一个从信源信号到区间上下界类的映射。这样在编码过程之中就能相当方便的寻找到对应的上下界,并参与运算了。


        对于第二个问题,我们在上面的伪代码中其实已经完成了这一步,在这里我就不再啰嗦了;


        好啦,解决了以上的两个问题,废话不多说,我就直接上代码了:

    /**
    * @author Mica_Dai
    * @Date Sept 13 2017
    */
    
    // 区间类,主要的就是用来存放上下界
    class Range
    {
    public:
        Range(){
            low = 0.0;
            high = 1.0;
            deltaLevel = 1.0;
        }
        ~Range(){}
        double getLow(){
            return this -> low;
        }
    
        double getHigh(){
            return this -> high;
        }
    
        void setLow(double low){
            this -> low = low;
        }
    
        void setHigh(double high){
            this -> high = high;
        }
    
        void setDelta(double delta){
            this -> deltaLevel = delta;
        }
    private:
        double low;
        double high;
        double deltaLevel;
    };

        再来看看我们首先创建编码解码表,需要输入,因此我们直接通过一个类方法为类属性map赋值:

    /**
    * @author Mica_Dai
    * @Date Sept 13 2017
    */
    
    void Arithmeticcoding::requirecode(){
        char ch;
        double lowLevel = 0.0;
        double highLevel = 0.0;
        double probability;
        while(1){
            // cout << "youyouyio" << ch << endl;
            // cin >> lowLevel >> highLevel;
            cin >> ch;
            if (ch == '#'){
                break;
            }else{
                cin >> probability;
                // cin >> lowLevel;
                // cin >> highLevel;
                lowLevel = highLevel;
                highLevel = lowLevel + probability;
                Range range;
                range.setLow(lowLevel);
                range.setHigh(highLevel);
                range.setDelta(probability);
                map.insert(std::pair<char, Range>(ch, range));
            }
        }
    }

        以下是编码函数的实现:

    /**
    * @author Mica_Dai
    * @Date Sept 13 2017
    */
    
    double Arithmeticcoding::encode(string str){
        /* encode code */
        double lowRange = 0.0, highRange = 1.0;
        for (auto i = str.begin(); i != str.end(); ++ i){
            // 使用map来通过字符完成概率的查找
            // map[*i]表示的就是对应的字符的出现概率
            double delta = highRange - lowRange;
            highRange = lowRange + delta * map[*i].getHigh();
            lowRange = lowRange + delta * map[*i].getLow();
    
            ++ length;
        }
    
        return lowRange;
    }

        以下是解码过程:

    /**
    * @author Mica_Dai
    * @Date Sept 13 2017
    */
    
    string  Arithmeticcoding::decode(double value){
        double lowInterval;
        double highInterval;
        string symbol = "";
    
        // 译出第一个编码
        for (auto i = map.begin(); i != map.end(); ++ i){
            if ((i -> second).getLow() < value && (i -> second).getHigh() > value){
                lowInterval = (i -> second).getLow();
                highInterval = (i -> second).getHigh();
                symbol += (i -> first);
                break;
            }
        }
    
        for (int i = 0; i < length - 1; ++i){
            /* decode code */
            double deltaInterval;
            deltaInterval = highInterval - lowInterval;
            value -= lowInterval;
            value /= deltaInterval;
    
            for (auto i = map.begin(); i != map.end(); ++ i){
            if ((i -> second).getLow() < value && (i -> second).getHigh() > value){
                lowInterval = (i -> second).getLow();
                highInterval = (i -> second).getHigh();
                symbol += (i -> first);
                break;
                }
            }
        }
    
        return symbol;
    }

        最后贴一下运行过程:

    C:\Users\50口口\Desktop>arithmeticcoding.exe
    A
    0.1
    B
    0.4
    C
    0.2
    D
    0.3
    #
    CADACDB
    0.514388
    CADACDB


        以上。

    展开全文
  • (JPEG)编码算法及压缩过程的实现编码算法及压缩过程的实现
  • 而文件的解压缩实际上就是将压缩文件翻译过来保存到解压缩文件中,需要使用压缩过程中生成的配置文件配合完成。下面将具体介绍文件的压缩和解压缩步骤: 1。统计文件中所有字符的出现次数。由于Ascall码字符一共255...

             本文采用哈夫曼编码的方式进行文件(文本文件)压缩和解压缩,首先介绍项目的整体思路:哈夫曼编码压缩文件实际就是统计出文件中各个字符出现的频率,然后为每个字符生成对应的编码,然后将每个字符用哈夫曼编码的形式按字节保存在压缩文件中。而文件的解压缩实际上就是将压缩文件翻译过来保存到解压缩文件中,需要使用压缩过程中生成的配置文件配合完成。下面将具体介绍文件的压缩和解压缩步骤:

           文件的压缩的核心是产生哈夫曼编码,而哈夫曼编码的过程中需要找到一系列数据中的最小权重和次小权重,我们自然联想到用堆这种结构时间复发度小并且很方便找到最小值和次小值,我将堆的源代码放在Heap.h文件中(见下文)。现在我们进行文件压缩。

           1。统计文件中所有字符的出现次数。由于Ascall码字符一共255个,只有前128个字符可以显示,定义字符变量时一定要定义成无符号型变量unsigned char ch如下,这是ch读不到文件的结束标志,所以我们可以用函数feof来代替文件的结束标志EOF,最重要的是文件的打开方式一定要是二进制的形式打开否则读不到汉字字符,将出现乱码。关于存储方式我们采用哈希表的方式将每个字符映射为哈希表的下标,这样可以很方便的将每个字符和出现的次数对应起来。需要说明的是我们这个哈希表存的绝不是单纯的次数而是结点FileInfo,这个节点称为权重结点中保存出现次数和字符以及将来我们产生的哈夫曼编码,方便我门进行索引。

    bool Compress(const char *filename)//该函数起到统计的作用
    {
    FILE *fout = fopen(filename, "rb");//以二进制形式打开文件
    assert(fout);
    unsigned char ch = fgetc(fout);
    while (!feof(fout))
    {
    _Infos[ch]._count++;//统计各种字符在文件中的个数
    ch = fgetc(fout);
    COUNT++;//统计文件中总的字符个数
    }
    fclose(fout);
    return true;
    }

         2。现在我们创建一个最小堆,将统计到的结点压入堆中

         3。从堆中取数据在HuffMan.h头文件中建立哈夫曼树

         4。通过哈夫曼树产生哈夫曼编码存入节点中

         5。遍历待压缩文件将对应的哈夫曼编码按字节保存到压缩文件中

         6.将每个字符出现的个数保存到配置文件中。由步骤5产生的压缩文件,当我们遍历到文件的最后一个字符时,如果编码凑不成8      一个字节我们给剩下的位置补0,为了解决最后一个字符的解析问题,我们将待压缩文件中的总的字符个数统计出来存到配置文       件的第一行,以后每行一“X,n”的形式存放字符和对应的出现次数。这样我们的文件压缩过程就完成了。


         文件的解压缩思路简单,但是要尤其注意细节读配置文件就要花些心思,体现在换行符的统计上,下面进行文件的解压缩(源文件见Uncompress.h):

          1。读配置文件

          2。通过配置文件重构哈夫曼树

          3。开始文件的解压缩,按字符读入编码通过编码在哈夫曼树种寻找对应的字符,并将字符存入到解压缩文件中去,通过配置文件中读入的COUNT来控制最后一个字符正确编码的起止。这样文件的解压缩完成。

    总结:

    项目的特点和用到的技术有,仿函数,堆,哈夫曼编码技术,string类,哈希表

    项目注意事项,文件名字转换方法艺术,文件的二进制读入写入,读配置文件时换行符的处理,以及统计的字符数如何以10进制字符的形式存到文件中去。其他问题详见源代码重点注释的地方。

    Heap.h

    #include <vector>
    
    
    template<class T>
    struct Less
    {
    	bool operator() (const T& l, const T& r)
    	{
    		return l < r; // operator<
    	}
    };
    
    template<class T>
    struct Greater
    {
    	bool operator() (const T& l, const T& r)
    	{
    		return l > r; // operator>
    	}
    };
    
    
    template<class T, class Compare=Less<T>>//哈夫曼结点的仿函数
    class Heap
    {
    public:
    	Heap()
    	{}
    	Heap(const T* a, size_t size)
    	{
    		for (size_t i = 0; i < size; ++i)
    		{
    			_arrays.push_back(a[i]);//将所有数据插入堆
    		}
    
    		// 建堆
    		for (int i = (_arrays.size() - 2) / 2; i >= 0; --i)
    		{
    			AdjustDown(i);//对这个范围的每个节点都向下调整,建堆的过程实际就是向下调整堆的过程
    		}
    	}
    
    	void Push(const T& x)
    	{
    		_arrays.push_back(x);
    		AdjustUp(_arrays.size() - 1);//插入节点的过程实际就是向上调整堆的过程
    	}
    
    	void Pop()
    	{
    		assert(_arrays.size() > 0);
    		swap(_arrays[0], _arrays[_arrays.size() - 1]);
    		_arrays.pop_back();
    
    		AdjustDown(0);
    	}
    
    	T& Top()
    	{
    		assert(_arrays.size() > 0);
    		return _arrays[0];
    	}
    
    	bool Empty()
    	{
    		return _arrays.empty();
    	}
    
    	size_t Size()
    	{
    		return _arrays.size();
    	}
    
    	void AdjustDown(int root)
    	{
    		int child = root * 2 + 1;
    
    		Compare com;
    		while (child < _arrays.size())
    		{
    			// 比较出左右孩子中小的那个
    			if (child + 1<_arrays.size() &&
    				com(_arrays[child + 1], _arrays[child]))
    			{
    				++child;
    			}
    
    			if (com(_arrays[child], _arrays[root]))
    			{
    				swap(_arrays[child], _arrays[root]);
    				root = child;
    				child = 2 * root + 1;
    			}
    			else
    			{
    				break;
    			}
    		}
    	}
    
    	void AdjustUp(int child)
    	{
    		int parent = (child - 1) / 2;
    
    		while (child > 0)
    		{
    			if (Compare()(_arrays[child], _arrays[parent]))
    			{
    				swap(_arrays[parent], _arrays[child]);
    				child = parent;
    				parent = (child - 1) / 2;
    			}
    			else
    			{
    				break;
    			}
    		}
    	}
    
    	void Print()
    	{
    		for (size_t i = 0; i < _arrays.size(); ++i)
    		{
    			cout << _arrays[i] << " ";
    		}
    		cout << endl;
    	}
    
    public:
    	vector<T> _arrays;
    };
    
    //测试堆 
    //void Test1()
    //{
    //	int a[10] = { 10, 11, 13, 12, 16, 18, 15, 17, 14, 19 };
    //	Heap<int, Greater<int> > hp1(a, 10);
    //	hp1.Push(1);
    //	hp1.Print();
    //
    //	Heap<int> hp2(a, 10);
    //	hp2.Push(1);
    //	hp2.Print();
    //
    //
    //	Less<int> less;
    //	cout<<less(1, 2)<<endl;
    //
    //	Greater<int> greater;
    //	cout<<greater(1, 2)<<endl;
    //}
    
    HuffMan.h

    #pragma once
    
    #include "Heap.h"
    
    template<class T>
    struct HuffManNode
    {
    	HuffManNode<T> *_left;
    	HuffManNode<T> *_right;
    	HuffManNode<T> *_parent;
    	T _weight;
    	HuffManNode(const T&x)
    		: _left(NULL)
    		, _right(NULL)
    		, _parent(NULL)
    		, _weight(x)
    	{}
    };
    
    template<class T>
    class HuffMan
    {
    	typedef HuffManNode<T> Node;
    
    	template<class T>
    	struct NodeCompare
    	{
    		bool operator() ( const Node*l, const Node*r)//模板不能分离编译
    		//因此用到NodeCompare的地方都要放到一个文件
    		{
    			return l->_weight < r->_weight;
    		}
    	};
    
    protected:
    	Node* _root;
    
    public:
    	HuffMan()
    		:_root(NULL)
    	{}
    
    	~HuffMan()
    	{}
    
    public:
    	Node* GetRootNode()
    	{
    		return _root;
    	}
    
    	Node* CreatTree(T*a, size_t size,const T& invalid)
    	{
    		//取数转换成哈夫曼结点,放到最小堆中
    		assert(a);
    		Heap<Node*, NodeCompare<T>> minHeap;
    		for (size_t i = 0; i < size; ++i)
    		{
    			if (a[i] != invalid)
    			{
    				Node*node = new Node(a[i]);
    			    minHeap.Push(node);
    			}
    			
    		}
    		/*for (int i = 0; i<10; i++)
    		{
    			Node *temp = minHeap._arrays[i];//用于测试的代码
    			cout << temp->_weight << " ";
    		}*/
    		//从最小堆中取最小的和次小的结点,建立哈夫曼树
    		while (minHeap.Size()>1)
    		{
    			Node* left = minHeap.Top();//取最小的
    			minHeap.Pop();
    			Node* right = minHeap.Top();//取次小的
    			minHeap.Pop();
    			Node *parent = new Node(left->_weight + right->_weight);
    			parent->_left = left;
    			parent->_right = right;
    			left->_parent = parent;
    			right->_parent = parent;//链接节点间的关系
    
    			minHeap.Push(parent);//将最小的和次小的之和放到堆中重新调整
    		}
    		_root = minHeap.Top();//堆中最后剩下的结点就是哈夫曼的根结点
    		return _root;
    	}
    	
    	HuffManNode<T>* GetRoot()
    	{
    		return _root;
    	}
    	void PrintHuff()
    	{
    		Node *root = _root;
    		_Print(root);
    	}
    protected:
    	void _Print(Node *root)
    	{
    		if (root == NULL)
    		{
    			return;
    		}
    		else
    		{
    			cout << root->_weight;
    		}
    		_Print(root->_left);
    		_Print(root->_right);
    	}
    
    };
    
    //void TestHuff()
    //{
    //	int a[] = { 1, 0, 2, 3, 4, 5, 6, 7, 8, 9 };
    //	HuffMan<int> t;
    //	t.CreatTree(a, sizeof(a) / sizeof(int), -1);
    //
    //}
    filecompress.h

    # include<iostream>
    # include<cassert>
    # include<string>
    # include<algorithm>
    # include"HuffMan.h"
    using namespace std;
    typedef unsigned long long LongType;
    struct FileInfo
    {
      unsigned	char _ch;
      LongType  _count;
      string  _code;
      FileInfo(unsigned char ch=0)
    	  :_ch(ch)
    	  , _count(0)
      {}
     FileInfo operator+(FileInfo filein)
      {
    	 FileInfo temp;
    	 temp._count=_count + filein._count;
    	 return temp;
      }
     bool operator<( const FileInfo filein)const               
     {
    	 return _count < filein._count;
     }
     bool operator!=(const FileInfo  Invalid)const
     {
    	 return _count != Invalid._count;
     }
    };
    class FileCompress
    {
    protected:
    	FileInfo _Infos[256];
    	LongType COUNT = 0;
    public:
    	FileCompress()
    	{
    		for (int i = 0; i < 256;i++)
    		{
    			_Infos[i]._ch = i;
    		}
    	}
    	bool Compress(const char *filename)//该函数起到统计的作用
    	{
    		FILE *fout = fopen(filename, "rb");//以二进制形式打开文件
    		assert(fout);
    		unsigned char ch = fgetc(fout);
    		while (!feof(fout))
    		{
    			_Infos[ch]._count++;//统计各种字符在文件中的个数
    			ch = fgetc(fout);
    			COUNT++;//统计文件中总的字符个数
    		}
    		fclose(fout);
    		return true;
    	}
    	void GenerateHuffManCode()
    	{
    		HuffMan<FileInfo> t;
    		FileInfo invalid;
    		t.CreatTree(_Infos, 256, invalid);
    		HuffManNode<FileInfo>*root = t.GetRoot();
    		_GenrateHuffManCode(root);
    	}
    	void _GenrateHuffManCode(HuffManNode<FileInfo>* root)
    	{
    		if (root == NULL)
    		{
    			return;
    		}
    		_GenrateHuffManCode(root->_left);
    		_GenrateHuffManCode(root->_right);
    
    		if ((root->_left == NULL) && (root->_right == NULL))
    		{
    			HuffManNode<FileInfo>*cur = root;
    			HuffManNode<FileInfo>*parent = cur->_parent;
    			string &code = _Infos[cur->_weight._ch]._code;
    			while (parent)//从叶子节点走到根结点
    			{
    				if (parent->_left == cur)
    			
    					code += '0';		
    				else		
    					code += '1';	
    				cur = parent;
    				parent = cur->_parent;
    			}
    			reverse(code.begin(), code.end());
    		}		
    	}
    
    	//下面进行文件压缩
    	void CompressFile(const char *filename)
    	{
    		Compress(filename);
    		string compressFile = filename;
    		compressFile += ".huffman";
    		FILE *FinCompress = fopen(compressFile.c_str(), "wb");
    		assert(FinCompress);//对压缩文件的命名处理
    		
    		GenerateHuffManCode();//产生编码
    		FILE *fout = fopen(filename, "rb");
    		assert(fout);
    
    		//进行文件压缩
    		 unsigned char inch = 0;
    		int index = 0;
    		char ch = fgetc(fout);
    		while (ch!=EOF)
    		{
    			string&code = _Infos[(unsigned char)ch]._code;
    			for (int i = 0; i < code.size(); ++i)
    			{
    				++index;
    				inch <<= 1;
    				if (code[i] == '1')
    				{
    					inch |= 1;
    				}
    				if (index == 8)
    				{
    					fputc(inch, FinCompress);
    					index = 0;
    					inch = 0;
    				}		
    			}
    			ch = fgetc(fout);
    		}
    		if (index != 0)
    		{
    			inch <<= (8 - index);
    			fputc(inch,FinCompress);
    		}
    		fclose(fout);
    		FileInfo invalid;
    		CreateConfig(filename,invalid);
    	}
    	void CreateConfig( const char* filename,FileInfo invalid)
    	{
    		string ConfigFile = filename;
    		ConfigFile += ".config";
    		FILE *FileConfig = fopen(ConfigFile.c_str(), "wb");
    		assert(FileConfig);
    
    		char ch[256];
    		string tempcount;
    		int i = 0;
    		tempcount=	_itoa(COUNT, ch, 10);
    		while (i < tempcount.size())
    		{
    			fputc(tempcount[i],FileConfig);
    			i++;
    		}//将总的字符数写入配置文件
    		fputc('\n', FileConfig);
    		for (size_t i = 0; i < 256; i++)
    		{
    			if (_Infos[i] != invalid)
    			{
    				string chInfo;
    				chInfo.clear();
    
    				if (_Infos[i]._count>0)
    				{
    					chInfo += _Infos[i]._ch;
    					chInfo += ',';
    					char ch[256]; //转换成的字符可能足够长
    					_itoa(_Infos[i]._count,ch, 10);
    					chInfo += ch;
    					for (int j = 0; j < chInfo.size(); j++)
    					{
    						fputc(chInfo[j], FileConfig);
    					}
    								
    						fputc('\n', FileConfig);					
    				}
    			}
    		}
    		fclose(FileConfig);
    	}
    
    };
    void TestFileCompress()
    {
    	FileCompress FC;
    	FC.CompressFile("fin.txt");
    	cout << "压缩成功" << endl;
    }
    
    Uncompress.h



    # include<iostream>
    using namespace std;
    # include"HuffMan.h"
    # include"filecompress.h"
    
    class Uncompress
    {
    private:
    	FileInfo _UNinfos[256];
    	LongType Count;
    public:
    	Uncompress()//哈希表的初始化
    	{
    		for (int i = 0; i < 256; i++)
    		{
    			_UNinfos[i]._ch = i;
    		}
    		Count = 0;
    	}
    	bool _Uncompress(const char *Ufilename)//读配置文件
    	{
    		string Configfile = Ufilename;
    		Configfile += ".config";
    		FILE *fpConfig = fopen(Configfile.c_str(), "rb");
    		assert(fpConfig);
    
    		string line;
    	    unsigned char ch = fgetc(fpConfig);
    		while (ch != '\n')
    		{   
    			line += ch;
    			ch =fgetc(fpConfig);		
    		}//读取第一个字符
    		Count = atoi(line.substr(0).c_str());//(总的字符个数)
    		ch = fgetc(fpConfig);//读入下一行字符
    		line.clear();
    		int j = 0;
    		while (!feof(fpConfig))
    		{
    			
    			j++;
    			while (ch != '\n')
    			{
    				line += ch;
    				ch = fgetc(fpConfig);
    
    			}
    			if (line.empty())
    			{
    				line += '\n';
    				ch = fgetc(fpConfig);
    				while (ch != '\n')
    				{
    					line += ch;
    					ch = fgetc(fpConfig);
    				}
    			}
    			ch = fgetc(fpConfig);
    			unsigned char tempch = line[0];//将第一个字符转换成无符号数和下标对应起来
    			                               //尤其要注意这里稍微不注意就全乱码了  
    			_UNinfos[tempch]._count = atoi(line.substr(2).c_str());//截取字符串并转换成整型数据
    			line.clear();
    		}
    		return true;
    	}
    	void GenrateHuffManCode(HuffManNode<FileInfo>* root)//重构哈夫曼树
    	{
    		if (root == NULL)
    		{
    			return;
    		}
    		GenrateHuffManCode(root->_left);
    		GenrateHuffManCode(root->_right);
    
    		if ((root->_left == NULL) && (root->_right == NULL))
    		{
    			HuffManNode<FileInfo>*cur = root;
    			HuffManNode<FileInfo>*parent = cur->_parent;
    			string &code = _UNinfos[cur->_weight._ch]._code;
    			while (parent)//从叶子节点走到根结点
    			{
    				if (parent->_left == cur)
    
    					code += '0';
    				else
    					code += '1';
    				cur = parent;
    				parent = cur->_parent;
    			}
    			reverse(code.begin(), code.end());
    		}
    	}
    
    	bool UncomPress(const char *UNfilename)//文件的解压缩过程
    	{
    		_Uncompress(UNfilename);
    		HuffMan<FileInfo> Re_huffTree;
    		FileInfo invalid;
    		HuffManNode<FileInfo>*root = Re_huffTree.CreatTree(_UNinfos, 256, invalid);//重构哈夫曼树
    		GenrateHuffManCode(root);
    
    		//打开文件
    		string UnComPressFile = UNfilename;
    		UnComPressFile += ".Unhuffman";
    		FILE *UCPfile = fopen(UnComPressFile.c_str(), "wb");
    		string ComPressFile = UNfilename;
    		ComPressFile += ".huffman";
    		FILE *CPfile = fopen(ComPressFile.c_str(), "rb");
    
    		//解压缩字符写入文件
    
    
    		HuffManNode<FileInfo>*tempRoot = root;//获得其根结点
    		while (!feof(CPfile))
    		{
    			unsigned char ch = fgetc(CPfile);
    			int bitCount = 7;
    			for (int i = bitCount; i >= 0; i--)
    			{
    				if (ch&(1 << i))
    				{
    					tempRoot = tempRoot->_right;
    				}
    				else
    				{
    					tempRoot = tempRoot->_left;
    				}
    				if (!tempRoot->_left&&!tempRoot->_right)//做到这里
    				{
    					fputc(tempRoot->_weight._ch, UCPfile);
    					Count--;
    					tempRoot = root;
    				}
    				if (Count <= 0)
    				{
    					break;
    				}
    			}
    			if (Count <= 0)
    			{
    				break;
    			}
    		}
    		return true;
    	}
    
    };
    void TestUNCP()
    {
    	Uncompress Uncp;
    	Uncp.UncomPress("fin.txt");
    }




    展开全文
  • matlab实现jpeg压缩过程MATLAB程序,包括分块,DCT2D,哈夫曼编码,熵编码
  • JPEG压缩编码算法原理

    万次阅读 2017-11-16 15:33:12
    本文介绍JPEG压缩技术的原理,对于DCT变换、Zig-Zag扫描和Huffman编码,给出一个较为清晰的框架。 1. JPEG压缩的编解码互逆过程编码 解码 2. 具体过程
  • 数据压缩 算术编码 c++ 程序,包括编码和译码 售后服务QQ:857997674 有任何疑问或问题,请咨询QQ
  • Huffman编码实现压缩压缩

    千次阅读 2016-04-04 23:22:05
    Huffman( 哈夫曼 ) 算法在上世纪五十年代初提出来了,它是一种无损压缩方法,在压缩过程中不会丢失信息熵,而且可以证明 Huffman 算法在无损压缩算法中是最优的。 Huffman 原理简单,实现起来也不困难,在现在的...
  • 视频压缩编码基本原理

    千次阅读 2018-09-26 16:26:31
    视觉冗余:人眼的一些特性,例如亮度分辨阈值、视觉阈值、对亮度和色度的敏感度不同,是的编码的时候引入适量的误差,也不会被察觉出来。可以利用人眼的这一特性,以一定客观失真换取数据压缩。这种压...
  • 基于帧内编码质量下降过程分析的相同编码参数HEVC双压缩检测
  • 通过卷积神经网络对心电图特征提取易实现降维,在卷积自编码器的编码过程中来实现心电压缩,将编码层作为压缩结果。卷积神经网络处理多通道的输入,因此可以实现导联体系的心电压缩。结果采用均方根百分误差和压缩比...
  • 本文介绍一下视频压缩编码和音频压缩编码的基本原理。其实有关视频和音频编码的原理的资料非常的多,但是自己一直也没有去归纳和总结一下,在这里简单总结一下,以作备忘。 1.视频编码基本原理 (1) 视频信号的...
  • 北京工业大学--算法作业3--huffman编码对文本文件进行压缩与解压---... 输入:一个文本文件 输出:压缩后的文件 算法过程: (1)统计文本文件中每个字符的使用频度 (2)构造huffman编码 (3)以二进制流形式压缩文件

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 163,919
精华内容 65,567
关键字:

压缩的过程是编码