精华内容
下载资源
问答
  • JPEG压缩编码过程

    千次阅读 2011-06-02 15:27:00
        JPEG压缩编码过程   1.1JPEG简介    JPEG(Joint Photographic Experts Group)是由ISO与IEC于1986年联合成立的一个专家委员会(WG1)。该委员会制定了一系列的静态连续...

     

     

    JPEG压缩编码过程

     

    1.1 JPEG简介

     

             JPEGJoint Photographic Experts Group)是由ISOIEC1986年联合成立的一个专家委员会(WG1)该委员会制定了一系列的静态连续色调图像压缩编码标准(如:有损、无损及接近无损等编码标准,并于1996年开始制定JPEG 2000标准。

    JPEG文件使用的颜色空间为YCbCr空间。因此要先将RGB转化为YCbCr空间:

                       Y = 0.299 R + 0.587 G + 0.114 B

         Cb = - 0.1687R - 0.3313G + 0.5 B + 128

         Cr = 0.5 R - 0.4187G - 0.0813 B + 128

     

    1.2     JPEG压缩编码及解压缩算法

    1.1 压缩编码算法                1.2解压缩算法

     

    JPEG压缩编码算法的主要计算步骤如下(解压缩步骤与其相反)

    (1)正向离散余弦变换(FDCT)

    (2)量化;

    (3)Z形扫描;

    (4)使用差分脉冲编码调制(DPCM)对直流系数(DC)进行编码;使用行程长度编码(RLE)对交流系数(AC)进行编码;熵编码。

     

    1.2.1          FDCT

     

             对每个单独的彩色图像分量,把整个分量图像分成8x8的图像块,并作为二维离散变换DCT的输入。通过DCT变换,把能量集中在少数几个系数上。它所作的变换可以简单地理解成(x,y)->(x’,y’),即实数对应到实数。

    DCT变换使用下面的计算公式:

    它的逆变换使用下式计算:

    在上面的式子中:

     

    f(ij)经变换之后,F(0,0)是直流系数(DC,64个空域图像采样值的平均值),其他为交流系数(AC)

     

    1.2.2  量化

     

        量化是对经过FDCT变换后的频率系数进行量化,其目的是减小非“0”系数的幅度以及增加“0”值系数的数目。对于有损压缩算法,使用均匀量化器进行量化。用FDCT生成的数据除以对应的量化步距。因为人眼对亮度信号比对色差信号更敏感,因此使用了两种量化表:亮度量化值和色差量化值。

    1.3亮度量化表         1.4 色差量化表

     

    1.2.3          z形扫描

     

     

    1.5 Z形扫描

     

             量化后的系数要重新编排,目的是为了增加连续的“0”系数的个数,就是“0”的游程长度,方法是按照Z字形的式样编排,其结果是把一个8x8的矩阵变成一个1x64的矢量,频率较低的系数放在矢量的顶部。

     

    1.2.4          DC编码

     

             8x8图像块经过DCT变换之后得到的DC直流系数有两个特点,一是系数的数值比较大,二是相邻8x8图像块的DC系数值变化不大。JPEG算法使用了差分脉冲调制编码(DPCM)技术,对相邻图像块之间量化DC系数的差值(Delta)进行编码。

     

    1.2.5         AC编码

             AC系数的特点:1x64矢量中包含有许多“0”系数,并且许多“0”是连续的。JPEG使用非常简单和直观的游程编码(RLE)对它们进行编码。

    例如:5555557777733322221111111

    行程编码为:(56)(75)(33)(24)(17)

     

    1.2.6         熵编码

             采用huffman编码。对DPCM编码后的直流DC系数和RLE编码后的交流AC系数作进一步的压缩。压缩数据符号时,霍夫曼编码器对出现频度比较高的符号分配比较短的代码,而对出现频度较低的符号分配比较长的代码。这种可变长度的霍夫曼码表可以事先进行定义。

        参考资料

    http://read.chaoxing.com/ebook/read_11769804.html DCT

    http://read.chaoxing.com/ebook/read_12304091.html 数字图像处理

    http://nes.ustc.edu.cn/jy/05/050001/050001005/m3_2.ppt JPEG图像编码标准

    展开全文
  • 视频压缩编码和音频压缩编码的基本原理

    万次阅读 多人点赞 2014-06-03 00:01:20
    本文介绍一下视频压缩编码和音频压缩编码的基本原理。其实有关视频和音频编码的原理的资料非常的多,但是自己一直也没有去归纳和总结一下,在这里简单总结一下,以作备忘。

    本文介绍一下视频压缩编码和音频压缩编码的基本原理。其实有关视频和音频编码的原理的资料非常的多,但是自己一直也没有去归纳和总结一下,在这里简单总结一下,以作备忘。

    1.视频编码基本原理

    (1)  视频信号的冗余信息

    以记录数字视频的YUV分量格式为例,YUV分别代表亮度与两个色差信号。例如对于现有的PAL制电视系统,其亮度信号采样频率为13.5MHz;色度信号的频带通常为亮度信号的一半或更少,为6.75MHz或3.375MHz。以4:2:2的采样频率为例,Y信号采用13.5MHz,色度信号U和V采用6.75MHz采样,采样信号以8bit量化,则可以计算出数字视频的码率为:

    13.5*8 + 6.75*8 + 6.75*8= 216Mbit/s

    如此大的数据量如果直接进行存储或传输将会遇到很大困难,因此必须采用压缩技术以减少码率。数字化后的视频信号能进行压缩主要依据两个基本条件:

    l  数据冗余。例如如空间冗余、时间冗余、结构冗余、信息熵冗余等,即图像的各像素之间存在着很强的相关性。消除这些冗余并不会导致信息损失,属于无损压缩。

    l  视觉冗余。人眼的一些特性比如亮度辨别阈值,视觉阈值,对亮度和色度的敏感度不同,使得在编码的时候引入适量的误差,也不会被察觉出来。可以利用人眼的视觉特性,以一定的客观失真换取数据压缩。这种压缩属于有损压缩。

    数字视频信号的压缩正是基于上述两种条件,使得视频数据量得以极大的压缩,有利于传输和存储。一般的数字视频压缩编码方法都是混合编码,即将变换编码,运动估计和运动补偿,以及熵编码三种方式相结合来进行压缩编码。通常使用变换编码来消去除图像的帧内冗余,用运动估计和运动补偿来去除图像的帧间冗余,用熵编码来进一步提高压缩的效率。下文简单介绍这三种压缩编码方法。

    (2)  压缩编码的方法

    (a)  变换编码

    变换编码的作用是将空间域描述的图像信号变换到频率域,然后对变换后的系数进行编码处理。一般来说,图像在空间上具有较强的相关性,变换到频率域可以实现去相关和能量集中。常用的正交变换有离散傅里叶变换,离散余弦变换等等。数字视频压缩过程中应用广泛的是离散余弦变换。

    离散余弦变换简称为DCT变换。它可以将L*L的图像块从空间域变换为频率域。所以,在基于DCT的图像压缩编码过程中,首先需要将图像分成互不重叠的图像块。假设一帧图像的大小为1280*720,首先将其以网格状的形式分成160*90个尺寸为8*8的彼此没有重叠的图像块,接下来才能对每个图像块进行DCT变换。

    经过分块以后,每个8*8点的图像块被送入DCT编码器,将8*8的图像块从空间域变换为频率域。下图给出一个实际8*8的图像块例子,图中的数字代表了每个像素的亮度值。从图上可以看出,在这个图像块中各个像素亮度值比较均匀,特别是相邻像素亮度值变化不是很大,说明图像信号具有很强的相关性。


    一个实际8*8图像块

    下图是上图中图像块经过DCT变换后的结果。从图中可以看出经过DCT变换后,左上角的低频系数集中了大量能量,而右下角的高频系数上的能量很小。


    图像块经过DCT变换后的系数

    信号经过DCT变换后需要进行量化。由于人的眼睛对图像的低频特性比如物体的总体亮度之类的信息很敏感,而对图像中的高频细节信息不敏感,因此在传送过程中可以少传或不传送高频信息,只传送低频部分。量化过程通过对低频区的系数进行细量化,高频区的系数进行粗量化,去除了人眼不敏感的高频信息,从而降低信息传送量。因此,量化是一个有损压缩的过程,而且是视频压缩编码中质量损伤的主要原因。

    量化的过程可以用下面的公式表示:

         

    其中FQ(u,v)表示经过量化后的DCT系数;F(u,v)表示量化前的DCT系数;Q(u,v)表示量化加权矩阵;q表示量化步长;round表示归整,即将输出的值取为与之最接近的整数值。

    合理选择量化系数,对变换后的图像块进行量化后的结果如图所示。


    量化后的DCT系数

    DCT系数经过量化之后大部分经变为0,而只有很少一部分系数为非零值,此时只需将这些非0值进行压缩编码即可。

    (b)  熵编码

    熵编码是因编码后的平均码长接近信源熵值而得名。熵编码多用可变字长编码(VLC,Variable Length Coding)实现。其基本原理是对信源中出现概率大的符号赋予短码,对于出现概率小的符号赋予长码,从而在统计上获得较短的平均码长。可变字长编码通常有霍夫曼编码、算术编码、游程编码等。其中游程编码是一种十分简单的压缩方法,它的压缩效率不高,但编码、解码速度快,仍被得到广泛的应用,特别在变换编码之后使用游程编码,有很好的效果。

    首先要在量化器输出直流系数后对紧跟其后的交流系数进行Z型扫描(如图箭头线所示)。Z型扫描将二维的量化系数转换为一维的序列,并在此基础上进行游程编码。最后再对游程编码后的数据进行另一种变长编码,例如霍夫曼编码。通过这种变长编码,进一步提高编码的效率。

    (c)  运动估计和运动补偿

    运动估计(Motion Estimation)和运动补偿(Motion Compensation)是消除图像序列时间方向相关性的有效手段。上文介绍的DCT变换、量化、熵编码的方法是在一帧图像的基础上进行,通过这些方法可以消除图像内部各像素间在空间上的相关性。实际上图像信号除了空间上的相关性之外,还有时间上的相关性。例如对于像新闻联播这种背景静止,画面主体运动较小的数字视频,每一幅画面之间的区别很小,画面之间的相关性很大。对于这种情况我们没有必要对每一帧图像单独进行编码,而是可以只对相邻视频帧中变化的部分进行编码,从而进一步减小数据量,这方面的工作是由运动估计和运动补偿来实现的。

    运动估计技术一般将当前的输入图像分割成若干彼此不相重叠的小图像子块,例如一帧图像的大小为1280*720,首先将其以网格状的形式分成40*45个尺寸为16*16的彼此没有重叠的图像块,然后在前一图像或者后一个图像某个搜索窗口的范围内为每一个图像块寻找一个与之最为相似的图像块。这个搜寻的过程叫做运动估计。通过计算最相似的图像块与该图像块之间的位置信息,可以得到一个运动矢量。这样在编码过程中就可以将当前图像中的块与参考图像运动矢量所指向的最相似的图像块相减,得到一个残差图像块,由于残差图像块中的每个像素值很小,所以在压缩编码中可以获得更高的压缩比。这个相减过程叫运动补偿。

    由于编码过程中需要使用参考图像来进行运动估计和运动补偿,因此参考图像的选择显得很重要。一般情况下编码器的将输入的每一帧图像根据其参考图像的不同分成3种不同的类型:I(Intra)帧、B(Bidirection prediction)帧、P(Prediction)帧。如图所示。

    典型的I,B,P帧结构顺序

    如图所示,I帧只使用本帧内的数据进行编码,在编码过程中它不需要进行运动估计和运动补偿。显然,由于I帧没有消除时间方向的相关性,所以压缩比相对不高。P帧在编码过程中使用一个前面的I帧或P帧作为参考图像进行运动补偿,实际上是对当前图像与参考图像的差值进行编码。B帧的编码方式与P帧相似,惟一不同的地方是在编码过程中它要使用一个前面的I帧或P帧和一个后面的I帧或P帧进行预测。由此可见,每一个P帧的编码需要利用一帧图像作为参考图像,而B帧则需要两帧图像作为参考。相比之下,B帧比P帧拥有更高的压缩比。

    (d)  混合编码

    上面介绍了视频压缩编码过程中的几个重要的方法。在实际应用中这几个方法不是分离的,通常将它们结合起来使用以达到最好的压缩效果。下图给出了混合编码(即变换编码+ 运动估计和运动补偿+ 熵编码)的模型。该模型普遍应用于MPEG1,MPEG2,H.264等标准中。

    混合编码模型

    从图中我们可以看到,当前输入的图像首先要经过分块,分块得到的图像块要与经过运动补偿的预测图像相减得到差值图像X,然后对该差值图像块进行DCT变换和量化,量化输出的数据有两个不同的去处:一个是送给熵编码器进行编码,编码后的码流输出到一个缓存器中保存,等待传送出去。另一个应用是进行反量化和反变化后的到信号X’,该信号将与运动补偿输出的图像块相加得到新的预测图像信号,并将新的预测图像块送至帧存储器。


    2.音频编码基本原理

    (1)  音频信号的冗余信息

    数字音频信号如果不加压缩地直接进行传送,将会占用极大的带宽。例如,一套双声道数字音频若取样频率为44.1KHz,每样值按16bit量化,则其码率为:

    2*44.1kHz*16bit=1.411Mbit/s

    如此大的带宽将给信号的传输和处理都带来许多困难,因此必须采取音频压缩技术对音频数据进行处理,才能有效地传输音频数据。

    数字音频压缩编码在保证信号在听觉方面不产生失真的前提下,对音频数据信号进行尽可能大的压缩。数字音频压缩编码采取去除声音信号中冗余成分的方法来实现。所谓冗余成分指的是音频中不能被人耳感知到的信号,它们对确定声音的音色,音调等信息没有任何的帮助。

    冗余信号包含人耳听觉范围外的音频信号以及被掩蔽掉的音频信号等。例如,人耳所能察觉的声音信号的频率范围为20Hz~20KHz,除此之外的其它频率人耳无法察觉,都可视为冗余信号。此外,根据人耳听觉的生理和心理声学现象,当一个强音信号与一个弱音信号同时存在时,弱音信号将被强音信号所掩蔽而听不见,这样弱音信号就可以视为冗余信号而不用传送。这就是人耳听觉的掩蔽效应,主要表现在频谱掩蔽效应和时域掩蔽效应,现分别介绍如下:

    (a)  频谱掩蔽效应

    一个频率的声音能量小于某个阈值之后,人耳就会听不到,这个阈值称为最小可闻阈。当有另外能量较大的声音出现的时候,该声音频率附近的阈值会提高很多,即所谓的掩蔽效应。如图所示:


    频率掩蔽效应

    由图中我们可以看出人耳对2KHz~5KHz的声音最敏感,而对频率太低或太高的声音信号都很迟钝,当有一个频率为0.2KHz、强度为60dB的声音出现时,其附近的阈值提高了很多。由图中我们可以看出在0.1KHz以下、1KHz以上的部分,由于离0.2KHz强信号较远,不受0.2KHz强信号影响,阈值不受影响;而在0.1KHz~1KHz范围,由于0.2KHz强音的出现,阈值有较大的提升,人耳在此范围所能感觉到的最小声音强度大幅提升。如果0.1KHz~1KHz范围内的声音信号的强度在被提升的阈值曲线之下,由于它被0.2KHz强音信号所掩蔽,那么此时我们人耳只能听到0.2KHz的强音信号而根本听不见其它弱信号,这些与0.2KHz强音信号同时存在的弱音信号就可视为冗余信号而不必传送。

    (b)  时域掩蔽效应

    当强音信号和弱音信号同时出现时,还存在时域掩蔽效应。即两者发生时间很接近的时候,也会发生掩蔽效应。时域掩蔽过程曲线如图所示,分为前掩蔽、同时掩蔽和后掩蔽三部分。

    时域掩蔽效应

    由图我们可以看出,时域掩蔽效应可以分成三种:前掩蔽,同时掩蔽,后掩蔽。前掩蔽是指人耳在听到强信号之前的短暂时间内,已经存在的弱信号会被掩蔽而听不到。同时掩蔽是指当强信号与弱信号同时存在时,弱信号会被强信号所掩蔽而听不到。后掩蔽是指当强信号消失后,需经过较长的一段时间才能重新听见弱信号,称为后掩蔽。这些被掩蔽的弱信号即可视为冗余信号。

    (2)  压缩编码方法

    当前数字音频编码领域存在着不同的编码方案和实现方式, 但基本的编码思路大同小异, 如图所示。

    数字音频编码系统模型

    对每一个音频声道中的音频采样信号,首先都要将它们映射到频域中,这种时域到频域的映射可通过子带滤波器实现。每个声道中的音频采样块首先要根据心理声学模型来计算掩蔽门限值, 然后由计算出的掩蔽门限值决定从公共比特池中分配给该声道的不同频率域中多少比特数,接着进行量化以及编码工作,最后将控制参数及辅助数据加入数据之中,产生编码后的数据流。

     


    展开全文
  • 而文件的解压缩实际上就是将压缩文件翻译过来保存到解压缩文件中,需要使用压缩过程中生成的配置文件配合完成。下面将具体介绍文件的压缩和解压缩步骤: 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");
    }




    展开全文
  • 图像压缩之算术编码

    千次阅读 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"34个字符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
    0B
    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
    001B
    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
    001100B
    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,继续解码;
    7195c所在区间,解码得到字符串 "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
    展开全文
  • Huffman编码实现压缩压缩

    千次阅读 2016-04-04 23:22:05
    Huffman( 哈夫曼 ) 算法在上世纪五十年代初提出来了,它是一种无损压缩方法,在压缩过程中不会丢失信息熵,而且可以证明 Huffman 算法在无损压缩算法中是最优的。 Huffman 原理简单,实现起来也不困难,在现在的...
  • 本博客主要是自己看的,看了下面这些文章后就会很容易理解JPEG压缩编码过程。 书籍: 多媒体技术基础(第二版)林福宗————5.6 JPEG压缩编码 论文: 基于DCT的JPEG图像压缩的研究_马媛媛.pdf基于...
  • 文件压缩与解压缩(哈夫曼编码

    千次阅读 2017-09-07 15:41:51
    本文采用哈夫曼编码的方式进行...而文件的解压缩实际上就是将压缩文件翻译过来保存到解压缩文件中,需要使用压缩过程中生成的配置文件配合完成。下面将具体介绍文件的压缩和解压缩步骤: 文件的压缩的核心是产生哈夫曼
  • 图像压缩编码

    千次阅读 2017-04-10 13:59:52
    图像的数据量非常大,为了有效地传输和储存图像,有必要压缩图像的数据量,而且随着现代通讯技术的发展,要求传输的图像信息的种类和数据量愈来愈大,若不进行数据压缩,难以推广应用。二 、图像压缩编码的可行性 ...
  • 图像压缩编码原理

    千次阅读 2018-01-10 17:23:12
    为什么要进行图像压缩编码? 1) 在数字分量编码中,按照4:2:2格式对电视信号进行取样、量化、编码后,数据率达27MW/S。 2) 在数字高清晰度电视格式中,取样、量化、编码后的数据率会更大。 3) 电视信号...
  • 信息论中的编码压缩基础

    千次阅读 2014-12-01 14:48:15
    大脑是终极的压缩和通信系统。 ----《INFORMATION THEROY,INFERENCE,AND LEARNING ALGORITHMS》
  • 图像处理 有损压缩-变换编码

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

    千次阅读 2016-11-22 20:56:00
    背景早在1948年,香农就提出将信源符号依其出现的概率降序排序,用符号序列累计概率的二进值作为对信源的编码,并从理论上论证了它的优越性。1960年, Peter Elias发现无需排序,只要编、解码端使用相同的符号顺序...
  • JPEG压缩编码算法原理

    万次阅读 2017-11-16 15:33:12
    本文介绍JPEG压缩技术的原理,对于DCT变换、Zig-Zag扫描和Huffman编码,给出一个较为清晰的框架。 1. JPEG压缩的编解码互逆过程编码 解码 2. 具体过程
  • 霍夫曼编码压缩算法

    千次阅读 2017-08-02 23:04:00
    霍夫曼编码压缩算法
  • 数据压缩,算术编码

    千次阅读 2016-01-04 15:49:53
    早在1948年,香农就提出将信源符号依其出现的概率降序排序,用符号序列累计概率的二进值作为对芯源的编码,并从理论上论证了它的优越性。1960年, Peter Elias发现无需排序,只要编、解码端使用相同的符号顺序即可,...
  • 算术编码压缩算法

    千次阅读 2018-04-08 21:51:05
    算术编码,是图像压缩的主要算法之一。 是一种无损数据压缩方法,也是一种熵编码的方法。和其它熵编码方法不同的地方在于,其他的熵编码方法通常是把输入的消息分割为符号,然后对每个符号进行编码,而算术编码是...
  • 压缩编码与格式

    千次阅读 2017-07-05 11:15:41
    1、视频编码是指视频文件压缩过程中的运算方法,同一种格式的视频文件其视频编码和音频编码有可能不同。比如同样是AVI格式的视频文件,其视频编码可以是DIVX、XVID、AVC、H.263、H.264、Windows Madia Video等等,...
  • 《H.264/AVC视频编解码技术...“纸上得来终觉浅,绝知此事要躬行”,只有自己按照标准文档以代码的形式操作一遍,才能对视频压缩编码标准的思想和方法有足够深刻的理解和体会!链接地址:H.264/AVC视频编解码技术详解
  • 压缩算法之字典编码(上)

    万次阅读 2017-09-23 10:50:12
    算法 信息论 字典压缩 LZ77
  • 视频压缩编码基本原理

    千次阅读 2015-06-17 12:56:09
    本文介绍一下视频压缩编码和音频压缩编码的基本原理。其实有关视频和音频编码的原理的资料非常的多,但是自己一直也没有去归纳和总结一下,在这里简单总结一下,以作备忘。 1.视频编码基本原理 (1) 视频信号的...
  • 1.视频编码基本原理 (1) 视频信号的冗余信息 以记录数字视频的YUV分量格式为例,YUV分别代表亮度与两个色差信号。例如对于现有的PAL制电视系统,其亮度信号采样频率为13.5MHz;色度信号的频带通常为...
  • 块截断编码图像压缩技术

    千次阅读 2020-10-04 03:20:19
    编码压缩技术的发展,使大容量图像信息的存储与传输得以实现,并且解决了多媒体等新技术在实际应用中遇到的各种困难。 论文先介绍了当前流行的图像压缩技术,重点介绍块截断编码技术,先从理论上介绍块截断编码原理...
  • 压缩算法之算术编码

    万次阅读 多人点赞 2017-09-14 22:24:04
    编码 香农范诺(Shannon)编码 霍夫曼(Huffman)编码 算术编码(arithmeticcoding)
  • 大数据与算法系列之字符压缩编码

    千次阅读 2018-06-04 10:53:57
    压缩的目的在于将出现频率较高的字符用短编码表示,而对于很少出现的字符用较长编码表示,从而提升字符在某些领域中的负荷,如网络传输过程中减少流量开销,常用的字符串压缩编码包括哈夫曼编码及香农-范诺编码。...
  • 静态哈夫曼编码的C++实现--使用哈夫曼编码压缩和解压缩

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 160,617
精华内容 64,246
关键字:

信息的压缩过程是编码吗