精华内容
下载资源
问答
  • 信息的压缩过程是编码吗
    千次阅读 多人点赞
    2022-01-24 10:25:45

    开始之前,务必要看!看了能更好的理解代码

    为了伙伴们更好的理解我们这个代码的实现,笔者先手动计算一个压缩过程,这样我们就能对整体的代码有一个了解了:
    这一部分请真心想要做出哈夫曼压缩解压缩的伙伴们一定认真看,因为这里的逻辑就是代码的逻辑:
    假设我们有一个字符串是:acefkmffmkfafkaffakaeef
    在这里插入图片描述
    那么它的哈夫曼树如图:
    在这里插入图片描述
    之后,我们进行计算:
    在这里插入图片描述
    这里我们说存入参数,其实就是存入了哈夫曼编码,实际上压缩是压缩了,但是参数比较多,就导致压缩后的文件反而比原文件大。

    一、整体的布局

    我们已经对整体的逻辑实现有了一个了解,现在就来看看具体的代码吧:

    我们想要做到功能分模块,也就是我可以自主选择是压缩还是解压缩,并且查看情况,那么我们就把业务逻辑分离:
    在这里插入图片描述
    那么我们首先看看最简单的头文件huffman.h书写了什么东西吧!

    #pragma once
    #define _CRT_SECURE_NO_WARNINGS
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #include<time.h>
    #include<Windows.h>
    struct HuffmanNode
    {
        int letter;						  //保存字符的映射
        long count;                   //文件中该字符出现的次数
        long parent, lchild, rchild;        //构建二叉树所需的数据
        char bits[256];               //对应的哈夫曼编码
    };
    
    struct HuffmanNode TreeNode[512], tmp, temp;  //节点树,TreeNode.count用来记录数据出现的次数
    //函数compress(),读取文件内容并加以压缩,将压缩内容写入另一个文档
    int compress(const char* filename, const char* outputfile);
    //函数:uncompress(),作用:解压缩文件,并将解压后的内容写入新文件
    int uncompress(const char* filename, const char* outputfile);
    

    头文件主要就写了一些定义,并包含了其他可能需要的头文件。

    现在来看看test.c文件
    为了我们更好的互动,在测试文件中书写一个菜单,供选择,那么这个代码很简单:

    #include"huffman.h"//注意头文件的包含
    void menu()
    {
        printf("\n1,压缩文件\n");
        printf("2,解压缩文件\n");
        printf("3,读取解压缩文件\n");
        printf("4,查看哈夫曼编码\n");
        printf("输入'q'退出程序\n");
        printf("请选择需要的操作:\n");
    }
    

    至于功能的实现,我们自然还是选择swtich语句,这里我们就需要考虑可能要写的功能了,比如,压缩文件,我们书写一个compress()函数,解压缩文件,我们书写一个uncompress()函数,读取文件的话,其实不需要再写函数,可以直接在uncompree()函数里实现解压缩文件的读取,而查看哈夫曼代码,我们既可以在编写哈夫曼树的时候去书写,也可以在解压缩的时候书写。

    所以,简单的讲,我们只需要书写两个模块,就可以实现我们想要的功能,那么我们先看看逻辑主函数里都写了什么吧!

    当然,这里的主函数会在尾记的时候详细的说一遍,这里可以选择不去理解。

    void main()
    {
        clock_t begin, end;
        double cost;
        FILE* fp;
        char ch, temparray[30];
        int ret1, ret2;
        int choice, count = 0, n;
        long f;
        memset(&TreeNode, 0, sizeof(TreeNode));
        memset(&tmp, 0, sizeof(tmp));
    
        menu();
        while (scanf("%d", &choice) == 1)
        {   
            system("cls");
            switch (choice)
            {
            case 1:
                ret1 = compress("data.txt", "data.zip.txt");
                menu();
                break;
            case 2:
                //开始记录
                begin = clock();
                ret2 = uncompress("data.zip.txt", "data.unzip.txt");
                //结束记录
                end = clock();
                cost = (double)(end - begin) / CLOCKS_PER_SEC;
                printf("解压缩耗时: %lf secs\n", cost);
                printf("压缩比率是%.3lf%%\n", ((double)ret1 / ret2) * 100);
                menu();
                break;
            case 3:
                printf("读取解压后的文件:\n");
                if ((fp = fopen("data.unzip.txt", "rt")) == NULL) {
                    printf("读取失败!\n");
                    exit(1);
                }
                ch = fgetc(fp);
                while (ch != EOF) {
                    putchar(ch);
                    ch = fgetc(fp);
                }
                fclose(fp);
                menu();
                break;
            case 4:
                if ((fp = fopen("data.zip.txt", "rb")) == NULL)
                {
                    printf("读取失败!\n");
                    exit(1);
                }
                fseek(fp, 4, SEEK_SET);
                fread(&f, sizeof(long), 1, fp);
                fseek(fp, f, SEEK_SET);
                fread(&n, sizeof(long), 1, fp);//读取字符种类总数
                for (int i = 0; i < n; i++)
                {
                    printf("字符:%-5c频数:%-6ld哈夫曼编码:%-20s", TreeNode[i].letter, TreeNode[i].count, TreeNode[i].bits);
                    count++;
                    if (count % 4 == 0)
                        printf("\n");
                }
                menu();
                break;
            case 6:
                printf("欢迎再次使用!\n");
            default:
                    break;
            }
        }
    }
    

    我们每次实现一个功能,再去选择另一个功能,就清理一下屏幕,所以这里书写了一个system("cls"),以便屏幕看着整洁一点。当然,可以根据个人的需要去更改。

    由于我们希望计算压缩比率,那么我们书写模块的时候,还需要注意需要返回字节数。也就是书写一个有返回值的函数。

    现在要看懂这些代码还是不行的,因为这里的功能的选择依赖于书写的模块的内容。所以我们还得继续看看模块都写了什么,才能理解这个main()函数的含义(并且在尾记里还会再介绍的,保证让每个人能有所收获)。放心,笔者会一一解释所有的可能的难点。

    二、模块功能实现

    1、压缩

    压缩的功能就是读取原文件,进行压缩并写入新文件。这里几乎每一行代码我都给了注释,小伙伴们应该都可以看懂的,所以只挑几个必要的说一说了。

    压缩文件的难点就在于写入压缩文件,也就是说,我们需要写入什么东西?因为SEEK_SET可以快速找到文件开头,这里我们在文件开头就写入原文件字节数和压缩文件字节数,为了防止丢失数据(如果不写在开头,就读不到这些数据)

    之后我们就存入压缩文件的容器(char类型,个数也就是存储的压缩文件字节数,所以现在理解为什么要存储原文件长和压缩文件长了吗?是为了不多读取,也不少读取

    然后我们在末尾再存入自己编写的哈夫曼编码(实际上更像一个自己写的ASCII编码表),这些参数的个数我们也需要记录,不然不好读取,也就是记录一共统计了多少个字符。

    #include"huffman.h"//务必注意包含头文件
    int compress(const char* filename, const char* outputfile)
    {
        char temparray[256];
        unsigned char c;
        long i, j, m, n, f;
        long lowest, pt, filelength;
        FILE* inputfilep, * outputfilep;
        int k, q;
        inputfilep = fopen(filename, "rb");//打开文件夹的原始文件
        if (inputfilep == NULL)
        {
            printf("打开文件失败\n");
            return 0;
        }
        outputfilep = fopen(outputfile, "wb");//打开压缩后存储信息的文件,如果没有就创建
        if (outputfilep == NULL)
        {
            printf("打开文件失败\n");
            return 0;
        }
        filelength = 0;
        while (!feof(inputfilep))//功能是检测流上的文件结束符,如果文件结束,则返回非0值,否则返回0
        {
            fread(&c, 1, 1, inputfilep);//从给定文件inputfilep 读取数据到c
            TreeNode[c].count++;//读文件,统计每个字符出现次数,并且使用是ASCII码
            filelength++;//记录文件的字符总数
        }
        filelength--;//去掉结束符
        TreeNode[c].count--;
        for (i = 0; i < 512; i++) //huffman算法中初始节点的设置
        {
            if (TreeNode[i].count != 0)//512个不一定都用了
                TreeNode[i].letter = i;//映射成ASCII码
            else    //赋值-1是为了避免哈夫曼编码时使用0出现冲突
                TreeNode[i].letter = -1;
            TreeNode[i].parent = -1;
            TreeNode[i].lchild = TreeNode[i].rchild = -1;
        }
        //将节点按出现次数排序(选择排序)
        for (i = 0; i < 256; i++)//每次都向后完成一次
        {
            k = i;//k用来记录变化的位置
            for (q = i + 1; q < 256; q++)//每次都在没有排序的数里进行循环
                if (TreeNode[k].count < TreeNode[q].count)
                    k = q;//挑没排序的数里数据最大的
            temp = TreeNode[i];//用t来暂时存储数据(为了与后面的小数据交换)
            TreeNode[i] = TreeNode[k];//把数据最大的赋值
            TreeNode[k] = temp;//把暂存的数据赋值给原来值大的,实现交换
        }
        for (i = 0; i < 256; i++)//统计不同字符的数量
        {
            if (TreeNode[i].count == 0)
                break;
        }//统计出i的数值,以便下面使用
        n = i;
        m = 2 * n - 1;//m是总结点数
        for (i = n; i < m; i++)//使用空结点
        {
            lowest = 999999999;//保证后面的if一定开始执行
            for (j = 0; j < i; j++)
            {
                if (TreeNode[j].parent != -1) 
                    continue;
                if (lowest > TreeNode[j].count)
                {
                    lowest = TreeNode[j].count;
                    pt = j;
                }
            }
            TreeNode[i].count = TreeNode[pt].count;
            TreeNode[pt].parent = i;
            TreeNode[i].lchild = pt;
            lowest = 999999999;
            for (j = 0; j < i; j++)
            {
                if (TreeNode[j].parent != -1) 
                    continue;
                if (lowest > TreeNode[j].count)
                {
                    lowest = TreeNode[j].count;
                    pt = j;
                }
            }
            TreeNode[i].count += TreeNode[pt].count;
            TreeNode[i].rchild = pt;
            TreeNode[pt].parent = i;
        }
        for (i = 0; i < n; i++)//设置字符的编码
        {
            f = i;//从构造数的第一个结点开始,依次对结点进行编排
            TreeNode[i].bits[0] = 0;//初始化
            while (TreeNode[f].parent != -1)//只要有父节点,就进行编排,第一次没有父节点就是根节点
            {
                j = f;
                f = TreeNode[f].parent;
                if (TreeNode[f].lchild == j)//左孩子编0
                {
                    j = strlen(TreeNode[i].bits);
                    memmove(TreeNode[i].bits + 1, TreeNode[i].bits, j + 1);
                    TreeNode[i].bits[0] = '0';
                }
                else//右孩子编1
                {
                    j = strlen(TreeNode[i].bits);
                    memmove(TreeNode[i].bits + 1, TreeNode[i].bits, j + 1);
                    TreeNode[i].bits[0] = '1';
                }
            }
        }
        //下面的就是读原文件的每一个字符,按照设置好的编码替换文件中的字符
        fseek(inputfilep, 0, SEEK_SET);    //将指针定在文件起始位置,没有任何偏移
        fseek(outputfilep, 8, SEEK_SET);   //以8位二进制数为单位,每次移动偏移进行读取
        temparray[0] = 0;
        pt = 8;//后面写入了一共八字节的filelength和pt
        printf("读取将要压缩的文件:%s\n", filename);
        printf("当前文件有:%d字符\n", filelength);
        //压缩文件
        while (!feof(inputfilep))
        {
            c = fgetc(inputfilep);//获取下一个字符(一个无符号字符)
            for (i = 0; i < n; i++)//n是字符种类总数
            {
                if (c == TreeNode[i].letter) //如果读取的字符与我们字符种类映射的ACSCII某一个对应
                    break;
            }
            strcat(temparray, TreeNode[i].bits);//那么就把此字符种类的编码追加给temparray来暂存
            j = strlen(temparray);//j用来暂存初始编码总长
            c = 0;//二进制是00000000
            if (j >= 8)//只要存的编码位数大于8,就执行操作写入文件
            {
                for (i = 0; i < 8; i++)//按照八位二进制数转化写入文件一次进行压缩
                {
                    if (temparray[i] == '1') 
                    {
                        c = c << 1;
                        c = c + 1;
                    }//c的二进制数左移并加1
                    else 
                        c = c << 1;//c的二进制数字左移
                }//实现二进制的读取和记录
                fwrite(&c, sizeof(char), 1, outputfilep);
                //printf("%s",temparray);//temparray数组存储的是char保存的二进制内容
                pt++;//pt使用的初始值是8,用于记录字节数
                strcpy(temparray, temparray + 8);//temparray的值重新覆盖
            }
        }
        if (j > 0)//当剩余字符数量少于8个时
        {
            strcat(temparray, "00000000");
            for (i = 0; i < 8; i++)
            {
                if (temparray[i] == '1')
                {
                    c = c << 1;
                    c += 1;//位运算
                }
                else 
                    c = c << 1;//对不足的位数进行补零
            }
            fwrite(&c, 1, 1, outputfilep);
            pt++;
        }
        fseek(outputfilep, 0, SEEK_SET);//偏移量为零,重新找到开头位置写入参数
        //使用outputfilep指针来确定文件的开头,将编码信息写入存储文件
        fwrite(&filelength, 4, 1, outputfilep);
        //1是写入的元素大小,sizeof(filelength)是需要写入的长度。这些内容写入ouputfilep
        fwrite(&pt, 4, 1, outputfilep);//写入四字节
        fseek(outputfilep, pt, SEEK_SET);//从给定的开头位置,pt大小(压缩之后的位置),在outputfile里读取
        fwrite(&n, 4, 1, outputfilep);//写一个四字节的数据,要注意pt的累加
        //以上是写入压缩的各类参数:字符种类总数,字符总数
        for (i = 0; i < n; i++)
        {
            tmp = TreeNode[i];
            fwrite(&(TreeNode[i].letter), 1, 1, outputfilep);//写入各类字符
            pt++;
            c = strlen(TreeNode[i].bits);//映射
            fwrite(&c, 1, 1, outputfilep);
            pt++;
            j = strlen(TreeNode[i].bits);
            if (j % 8 != 0)//当位数不满8时,对该数进行补零操作(为了一字节八位数的保存)
            {
                for (f = j % 8; f < 8; f++)
                    strcat(TreeNode[i].bits, "0");
            }
            while (TreeNode[i].bits[0] != 0)
            {
                c = 0;//赋值00000000
                for (j = 0; j < 8; j++)
                {
                    if (TreeNode[i].bits[j] == '1')
                    {
                        c = c << 1;
                        c += 1;//进行位运算
                    }
                    else 
                        c = c << 1;//不是1就补0
                }
                strcpy(TreeNode[i].bits, TreeNode[i].bits + 8);
                fwrite(&c, 1, 1, outputfilep);//将所得的编码信息写入文件
                pt++;
            }//以上写入各字符种类哈夫曼编码的数据
    
            TreeNode[i] = tmp;
        }
        fclose(inputfilep);
        fclose(outputfilep);//关闭文件
        printf("\n压缩后文件为:%s\n", outputfile);
        printf("压缩后文件有:%d字符\n", pt + 4);//之前写入了一个四字节的n,所以需要加4
        return pt + 4;//返回压缩成功信息
    }
    

    至于位运算,注释给的也很详细,哈夫曼树的编写,就读者自己看看书喽,我们日后再写一篇文章讲一讲哈夫曼树的编写。不然这篇文章就太长啦!

    2、解压缩

    至于解压缩,也就是读取压缩文件,并把读取结果写入新文件,所以压缩的时候,我们主要使用fseek和fwrite,解压缩的时候,我们就主要使用fseek和fread了。

    同样的,几乎每一行代码都给了注释,认真看一看都能看懂。

    现在就挑几个不好理解的说一说:

    读取的时候,我们需要注意先读取原文件长和压缩文件长,这样我们才能让程序知道,它在读压缩文件的时候应该读多少个,不能读多了,读多了就读到参数了(就是后面存储的哈夫曼编码的数据,那就读多了)

    之后是读取参数的数据(获取解压缩的数据,不然没有编码也解压不了)

    最后一步就是利用读取到的参数进行转译了,这一步就是写入新文件的过程,还是需要使用fwrite函数的。

    至此,我们的哈夫曼解压缩也就实现了。

    int uncompress(const char* filename, const char* outputfile)
    {
        char temparray[256], bx[256];
        unsigned char c;
        long i, j, m, n, k, f, p, l;
        long filelength;
        int len = 0;
        FILE* inputfilep, * outputfilep;
        char cname[512] = { 0 };
        inputfilep = fopen(filename, "rb");//打开压缩的文件
        if (inputfilep == NULL)
        {
            printf("文件打开失败!");
            return 0;//若打开失败,则输出错误信息
        }
    
        outputfilep = fopen(outputfile, "wb");//打开新文件,用于解压缩
        if (outputfilep == NULL)
        {
    
            return 0;
        }
        fseek(inputfilep, 0, SEEK_END);//定下指针位置
        len = ftell(inputfilep);//记录的是inputfilep的位置,也就是字节数
        
        fseek(inputfilep, 0, SEEK_SET);
        printf("将要读取解压的文件:%s\n", filename);
        printf("当前文件有:%d字符\n", len);
        fread(&filelength, sizeof(long), 1, inputfilep);//读取原文件长
        fread(&f, sizeof(long), 1, inputfilep);//f读取的是需要压缩文件的长度,不包括参数
        fseek(inputfilep, f, SEEK_SET);//从文件的f位置后开始读
        fread(&n, sizeof(long), 1, inputfilep);//读取字符种类总数
        for (i = 0; i < n; i++)//读取压缩文件内容并转换成二进制码
        {
            fread(&TreeNode[i].letter, 1, 1, inputfilep);//读取字符(ASCII码)
            fread(&c, 1, 1, inputfilep);//读取字符编码的数据strlen(TreeNode[i].bits))
            p = (long)c;//读的是编码的长度,编码的长度与count反相关
            TreeNode[i].count = p;
            TreeNode[i].bits[0] = 0;//赋初值
            if (p % 8 > 0) //判断字节
                m = p / 8 + 1;
            else 
                m = p / 8;
            for (j = 0; j < m; j++)
            {
                fread(&c, 1, 1, inputfilep);//此步读取的是单个字符类的二进制码
                f = c;
                _itoa(f, temparray, 2);//将f的值转为2进制存入temparray,此时temparray存的是二进制
                f = strlen(temparray);
                for (l = 8; l > f; l--)
                {
                    strcat(TreeNode[i].bits, "0");//位数不足,执行补零操作
                }
                strcat(TreeNode[i].bits, temparray);
            }
            TreeNode[i].bits[p] = 0;
        }//接受解压所需要的参数,读取必要的文件
    
        for (i = 0; i < n; i++)//每次都向后完成一次
        {
            k = i;//k用来记录变化的位置
            for (j = i + 1; j < n; j++)//每次都在没有排序的组里进行循环
                if (strlen(TreeNode[k].bits) > strlen(TreeNode[j].bits))//长度最小的是出现次数最多的
                    k = j;//取短的
            tmp = TreeNode[i];//用t来暂时存储数据
            TreeNode[i] = TreeNode[k];//k是略长的值,换到后面
            TreeNode[k] = tmp;//实现交换
        }//排序的目的是快速找到读取解压对应的字母
    
        p = strlen(TreeNode[n - 1].bits);//p取了一个长度最长的
        fseek(inputfilep, 8, SEEK_SET);//前八位存了两个四字节数据
        m = 0;
        bx[0] = 0;
        while (1)
        {
            while (strlen(bx) < (unsigned int)p)
            {
                fread(&c, 1, 1, inputfilep);//读取压缩的文件
                f = c;//f是一个数,转换十进制再转换二进制丢失了0
                _itoa(f, temparray, 2);//f转换成二进制暂存入temparray
                f = strlen(temparray);
                for (l = 8; l > f; l--)
                {
                    strcat(bx, "0");
                }//如果不足八位,补零
                strcat(bx, temparray);
            }
            for (i = 0; i < n; i++)
            {
                if (memcmp(TreeNode[i].bits, bx, TreeNode[i].count) == 0)
                    break;//比较字节数是为了保证数组保存的二进制数字相同
            }
            strcpy(bx, bx + TreeNode[i].count);//进行赋值覆盖
            c = TreeNode[i].letter;//写入ASCII码
            fwrite(&c, 1, 1, outputfilep);//写入解码的文件
            m++;
            if (m == filelength)//限定写入只写到原文件的内容,再往后就是存储的参数
                break;
        }//读取压缩文件内容,解压缩的过程
        fclose(inputfilep);
        fclose(outputfilep);
        printf("解压后文件为:%s\n", outputfile);
        printf("解压后文件有:%d字符\n", filelength);
        return filelength;//输出成功信息
    }
    

    把压缩的过程理解了,解压缩其实就没什么不能理解的了。

    三、尾记-主函数的详细介绍

    为什么写尾记呢?因为我们要在这个地方再看一看主函数的功能实现,这样就能让读者们真正的了解这些代码的运行了。
    初始化内存就没什么好说的,不操作的话,可能运行不起来

        memset(&TreeNode, 0, sizeof(TreeNode));
        memset(&tmp, 0, sizeof(tmp));
    

    这个代码 while (scanf("%d", &choice) == 1)

     while (scanf("%d", &choice) == 1)
        {......}
    

    则实现了输入字母就退出,当然,我们也可以定向的作其他修改,看读者的需求了。
    scanf函数的返回值是正确读取的个数,所以只要我们输入字母,就会退出循环,从而实现想要的功能
    swtich语句的case1和case2没什么好讲的,就是基本的模块直接调用。
    case3,我们是要实现读取解压缩的文件:

     case 3:
                printf("读取解压后的文件:\n");
                if ((fp = fopen("data.unzip.txt", "rt")) == NULL) {
                    printf("读取失败!\n");
                    exit(1);
                }
                ch = fgetc(fp);
                while (ch != EOF) {
                    putchar(ch);
                    ch = fgetc(fp);
                }
                fclose(fp);
                menu();
                break;
    

    那么这里我们就需要打开文件,并且使用 end of file 结束标志。这一个读取还是很简单,不需要itoa转换二进制,因为解压缩的文件已经是字符文件。

    case4,我们是要读取哈夫曼编码的一些数据,如图:
    在这里插入图片描述
    那么由于我们书写的文件里已经有参数的数据,我们直接找到压缩的文件,读取一下有多少个字符种类,然后用一个循环把结构体打印出来就可以了。

    (当然,笔者认为自己使用的这种方法是一个笨方法,我们也可以直接定义一个全局变量,在压缩的时候就存储一下字符种类个数)

    这里的找到文件的操作,需要使用SEEK_SET的一些知识,上面的代码已经都给出了使用的说明和注释。

     case 4:
                if ((fp = fopen("data.zip.txt", "rb")) == NULL)
                {
                    printf("读取失败!\n");
                    exit(1);
                }
                fseek(fp, 4, SEEK_SET);
                fread(&f, sizeof(long), 1, fp);
                fseek(fp, f, SEEK_SET);
                fread(&n, sizeof(long), 1, fp);//读取字符种类总数
                for (int i = 0; i < n; i++)
                {
                    printf("字符:%-5c频数:%-6ld哈夫曼编码:%-20s", TreeNode[i].letter, TreeNode[i].count, TreeNode[i].bits);
                    count++;
                    if (count % 4 == 0)
                        printf("\n");
                }
                menu();
                break;
    

    那么,现在,我们要实现的功能就都已经书写了,如果有小伙伴说,我想看到二进制的数据,怎么才能看到呢?

    二进制文件,我们是打不开的,看到的都是乱码,不过我们可以使用itoa函数外加一个辅助数组,把写入到压缩文件里的容器一个一个读出来,这样得到的也是一个可以被我们看到的二进制的一些数字(但注意,这不是二进制哦)。有兴趣的小伙伴可以自己实现一下。

    今天的分享就到这里了,希望老铁们有所收获,我们下次再见。

    更多相关内容
  • 图象压缩(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)编码算法的基本原理、压缩的实现过程及其重要过程的离散余弦变换(DCT)算法的实现原理及软件实现的例程,其次着重介绍了压缩过程中的DCT、量化和编码三个重要步骤的实现原理。
  • 计算原图、最终行程/游程编码压缩后数据所需要的存储空间,计算压缩率。 2. 分析 对于灰度图像的任意一行像素,其表达式如下,其中为灰度图像的列数。 给定系数表达式如下 则的第个元素的预测值可表示为 ...

    1. 要求

    选择灰度图像,按照行的方式展开像得到一维的向量。按照一维预测的公式:

    \widehat{x_{k}}=\sum_{i=1}^{k-1}a_{i}x_{i}

    自行设计预测算法实现一维无损预测压缩。将预测压缩后的一维向量(由预测误差组成),进行一维行程/游程编码。计算原图、最终行程/游程编码压缩后数据所需要的存储空间,计算压缩率。

    2. 分析

    对于灰度图像I的任意一行像素X,其表达式如下,其中n为灰度图像I的列数。

    X=[x_{1}, x_{2}, ..., x_{n}]

    给定系数A表达式如下

    A=[a_{1}, a_{2}, ..., a_{n-1}]

    X的第k个元素的预测值\hat{x_{k}}可表示为

    \widehat{x_{k}}=\sum_{i=1}^{k-1}a_{i}x_{i}

    预测误差e_{k}可表示为

    e_{k}=x_{k}-\hat{x_{k}}

    特别地,当k=1时,\hat{x_{k}}不存在,则e_{k}=x_{k}

    更一般地,用矩阵进行简化可得

    \hat{x_{k}}=[x_{1}, x_{2}, ..., x_{k-1}] * [a_{1}, a_{2}, ..., a_{k-1}]^{T}

    e_{k}=x_{k}-[x_{1}, x_{2}, ..., x_{k-1}] * [a_{1}, a_{2}, ..., a_{k-1}]^{T}

    则可以写作如下代码

    clear, close all
    I = imread('cameraman.tif');
    [row, col] = size(I); % 获取I的行数和列数
    a = rand(col-1, 1);   % col-1个系数
    e = zeros(size(I));   % 误差矩阵
    for i = 1: row        % 遍历所有行
        e(i,1) = I(i,j);  % 第i行的第1列元素误差等于实际值
        for j = 2: col    % 从第2列开始遍历
            e(i,j) = I(i,j) - I(i,1:j-1) * a(1:j-1);
        end
    end

    为了方便,我使用rand函数生成长度为col-1(对应于上述的n-1)的列向量,其中的元素为0~1之间的随机浮点数。

    实际运行上述代码的话,除了精度问题的报错,最大的问题是运行时间长。

    3. 编码阶段-矩阵优化

    可以观察到,上述循环的本质是逐列计算,因此我们可以从每一列入手,进行优化。

    对于灰度图像I的第j列像素Y_{j}, 其表达式如下,其中m为灰度图像I的行数,I_{i,j}表示第i行第j列的值。

    Y_{j}=[I_{1,j}, I_{2,j}, ..., I_{m,j}]^{T}

    于是可以得到 

    [\hat{I_{1,j}}, \hat{I_{2,j}}, ..., \hat{I_{m,j}}]^{T}=\begin{bmatrix} I_{1,1} & I_{1,2}& ...&I_{1,j-1} \\ I_{2,1} & I_{2,1}& ... &I_{2,j-1} \\ ... & ... & ... & ...\\ I_{m,1} & I_{m,2}&... & I_{m,j-1} \end{bmatrix} * [a_{1}, a_{2}, ..., a_{j-1}]^{T}

     即

    \hat{Y_{j}}=[Y_{1}, Y_{2}, ..., Y_{j-1}] * [a_{1}, a_{2}, ..., a_{j-1}]^{T}

    于是

    E_{j}=Y_{j}-[Y_{1}, Y_{2}, ..., Y_{j-1}] * [a_{1}, a_{2}, ..., a_{j-1}]^{T}

    其中E_{j}表示误差矩阵中的第j

    特别地,当j=1时,\hat{Y_{1}}不存在,则E_{1}=Y_{1}

    因此图像编码阶段的代码可写为

    clear, close all
    I = imread('cameraman.tif');
    [row, col] = size(I); % 获取I的行数和列数
    a = rand(col-1, 1);   % col-1个系数
    e = zeros(size(I));   % 生成误差矩阵
    e(:,1) = I(:,1);      % 第一列特殊计算
    II = double(I);       % I的副本,类型为double
    for j = 2:col         % 遍历列
        e(:,j) = II(:,j) - (II(:,1:j-1) * a(1:j-1));
    end
    e = round(e);         % 将误差矩阵取整

    这里说下要生成一个I的副本,且类型为double,这是因为在下面的矩阵乘法运算的时候,I的默认类型是uint8,范围在0~255,uint8的矩阵和任何矩阵进行乘法运算,结果仍为uint8,即超出255的变为255,低于0的变为0,浮点数自动取整。为了得到较为准确的误差矩阵,需要在double类型上进行运算,于是预先生成一个double类型的I的副本。

    4. 图像解码

    只需要将上述编码过程逆操作即可得到图像解码对应的代码

    J = zeros(size(e));
    J(:,1) = e(:,1);
    for j = 2: col
        J(:,j) = e(:,j) + (J(:,1:j-1) * a(1:j-1));
    end
    J = uint8(J); %解码图像

    至此,可以解释图像编码的应用场景。比如,张三需要将大量图像通过网络传输给李四,由于网络带宽限制,单张图像都无法直接传输,于是张三和李四事先约定了一个编码系数向量A。

    在发送端,每一张图片都使用A编码得到一个误差矩阵e;

    传输的过程中只需要传输误差矩阵e;

    在接收端,只需要用A对误差矩阵e进行解码即可得到原始图像。

    我们知道,这里的误差矩阵其实和图像的规模是一致的,即行数和列数都等于图像的行数和列数。

    灰度图像中的每一个像素都由8位2进制进行编码表示,实际范围在0~256。

    想要传输误差矩阵e,一个方法是使用调优过的系数向量A,使得生成的每一个误差矩阵中的任何一个元素,都可以用小于8位的2进制编码进行表示;另一个方法就是题目要求的,对误差矩阵进行游程编码。

    游程编码(Run Length Coding,RLC)是一种简单的熵编码(无损压缩编码)方法。其基本原理是,将具有相同数值的、连续出现的信源符号用“符号+符号出现次数”的形式表示。如“zzxxxxyyyyyzzz”将被编码为“2z4x5y3z”。

    这样就存在一个问题:假如图像中相邻的像素均不相等,那么游程编码非但起不到压缩作用,还会因为需要传输像素的出现次数,而使数据量增加一倍。因此,直接对图像进行编码时,游程编码只适用于有较多灰度相同的图像,也就是说图像最好包含大片的平坦区。

    想要得到效果出色的游程编码结果,就必须使误差矩阵中出现较多连续的值,而误差矩阵中值分布情况,只与图像本身和编码系数向量A有关。

    这里就有几个引人深思的问题:

    1. 能不能找出一个A,并且给出证明,任意的图像经过A编码得到的误差矩阵,均适合使用游程编码,或者误差矩阵中的每一个元素可以用7位2进制甚至6位2进制进行编码。
    2. 退而求其次,对于一个图像,能不能通过特定算法,花费较少计算代价计算出一个A,将这个特定的A和它对应的图像一起传输。

    5. 游程编码

    对于一个列向量K,对其游程编码后得到矩阵L,其中第一列表示值,第二列表示这个值连续出现的次数。

    K = \begin{bmatrix} 12\\ 12\\ 13 \\ 14 \\ 14 \\ 13 \\ 12 \end{bmatrix}\Rightarrow L=\begin{bmatrix} 12 & 2\\ 13 & 1\\ 14 & 2\\ 13 & 1\\ 12 & 1 \end{bmatrix}

     代码如下

    %% 游程编码
    function [L, size1, size2] = RLC(K)
    L = [K(1) 1];
    Lj = 1;
    for i = 2: length(K)
        if K(i) == L(Lj,1)
            L(Lj,2) = L(Lj,2) + 1;
        else
            Lj = Lj + 1;
            L(Lj,:) = [K(i) 1];
        end
    end
    L_1 = ceil(log2(max(L(:,1))-min(L(:,1))+1));
    L_2 = ceil(log2(max(L(:,2))-min(L(:,2))+1));
    size1 = L_1 * length(L);
    size2 = L_2 * length(L);
    end

    这里举例说明一下L_1的含义,如果矩阵L的第一列中最大值为260,最小值为20,则max(L(:,1))-min(L(:,1))+1的结果为260-20+1=241,显然20-260之间有241个连续的值,可以被8位2进制所编码表示,ceil(log2(X))计算的就是X能被几位二进制所表示。

    L_1和L_2分别表示第一列和第二列能被几位二进制表示,size1和size2分别表示第一列和第二列占用的总位数。

    size1+size2就是编码L矩阵所需要的总位数(总位数除以8就是总字节数)

    6. 完整代码

    clear, close all
    I = imread('cameraman.tif');
    subplot(1,3,1), imshow(I), title('原始图像')
    [row, col] = size(I);
    a = -1 + 2 * rand(col-1, 1);
    a = a / 200;
    e = zeros(size(I));
    %% encode
    %  由原图像I和预测系数a生成误差矩阵e
    e(:,1) = I(:,1);      % 第一列特殊计算
    II = double(I);       % I的副本,类型为double
    for j = 2:col         % 遍历列
        e(:,j) = II(:,j) - (II(:,1:j-1) * a(1:j-1));
    end
    e = round(e);         % 将误差矩阵取整
    subplot(1,3,2), imshow(uint8(e)), title('误差矩阵')
    %% decode 
    %  该过程只用到误差矩阵e和预测系数a
    J = zeros(size(e));
    J(:,1) = e(:,1);
    for j = 2: col
        J(:,j) = e(:,j) + (J(:,1:j-1) * a(1:j-1));
    end
    J = uint8(J);          % 解码图像
    subplot(1,3,3), imshow(J), title('解码图像')
    %% run length encode
    K = e';
    K = K(:);
    [L, size11, size12] = RLC(K);       % 对K进行游程编码
    [L2, size21, size22] = RLC(L(:,2)); % 对游程编码的矩阵的第二列再次进行游程编码
    total_size = 8 * length(I(:));
    % 图像压缩率 = 原始图像所需空间 / 压缩图像所需空间
    ratio = total_size / (size11+size21+size22);
    
    %% 游程编码函数
    function [L, size1, size2] = RLC(K)
    L = [K(1) 1];
    Lj = 1;
    for i = 2: length(K)
        if K(i) == L(Lj,1)
            L(Lj,2) = L(Lj,2) + 1;
        else
            Lj = Lj + 1;
            L(Lj,:) = [K(i) 1];
        end
    end
    L_1 = ceil(log2(max(L(:,1))-min(L(:,1))+1));
    L_2 = ceil(log2(max(L(:,2))-min(L(:,2))+1));
    size1 = L_1 * length(L);
    size2 = L_2 * length(L);
    end
    

    展开全文
  • 基于哈夫曼编码的文件压缩

    千次阅读 多人点赞 2021-08-14 18:45:01
    文件压缩的概念在生活中已经屡见不鲜,在这个信息化的时代,我们每天的生活基本上离不开手机电脑,在手机或电脑上下载软件,应用,基本上都能接触到文件压缩。对于文件压缩来讲,有许多种不同的方式,每种方式也有...


    前言

    文件压缩的概念在生活中已经屡见不鲜,在这个信息化的时代,我们每天的生活基本上离不开手机电脑,在手机或电脑上下载软件,应用,基本上都能接触到文件压缩。对于文件压缩来讲,有许多种不同的方式,每种方式也有各自的优缺点,这篇文章,就主要介绍以哈夫曼编码的方式来实现文件压缩。


    以下是本篇文章正文内容,下面案例可供参考,如有问题,还请大佬及时指正,交流学习!!!

    一、什么是文件压缩?

    文件压缩是指在不丢失有用信息的前提下,缩减数据量以减少存储空间,提高其传输、存储和处理效率,或按照一定的算法对文件中数据进行重新组织,减少数据的冗余和存储的空间的一种技术方法。
    在这里插入图片描述

    二、为什么需要文件压缩

    1. 紧缩数据存储容量,减少存储空间
    2. 可以提高数据传输的速度,减少带宽占用量,提高通讯效率
    3. 对数据的一种加密保护,增强数据在传输过程中的安全性

    三、怎样实现文件压缩

    实现压缩的方式,大体上主要分为两类:有损压缩和无损压缩。
    无损压缩:简单来将,就是压缩之后的文件经过还原后与源文件相同。常用于对文件的压缩
    有损压缩:压缩过程中损失一定的信息,常用于图片或视频的压缩,有损压缩的压缩比率要比无损压缩高。
    而对于文件的压缩,常用的方式有:
    ①专有名词采用的固定短语
    ②缩短文件中重复的数据
    ③给文件中每个字节找一个更短的编码
    其中,给文件中每个字节找一个更短的编码这种方式较为常用。因为,文件中的数据在磁盘中都是以字节的方式来进行存储的,1字节=8比特位,可以给每个字节找一个更短的比特位编码来表示,这样就可以达到压缩(减小文件所占空间)的目的。
    下图是使用等长的二进制编码来对源文件进行改写:
    在这里插入图片描述
    使用等长的编码来对文件进程改写,不一定能达到最好的压缩率。
    但使用不等长的编码来改写文件的话,压缩率往往会更好,这种方式是使用出现频率高的字符采用更短的编码进行表示。
    下图是使用了不等长编码方法:
    在这里插入图片描述

    四、创建哈夫曼树

    基于哈夫曼编码的文件压缩方式就是使用不等长的编码来对原文件进行改写的。使用Huffman编码来进行文件压缩要经过四个步骤:
    1.获取原文件中每个字节出现的次数
    2.根据字节出现的频次信息构建Huffman树
    3.获取Huffman编码
    4.使用Huffman编码来改写文件

    1.哈夫曼编码的方式

    前面介绍用不等长编码的方式来对文件进行改写,但这些编码是怎么来的呢?为什么A:100 ,B:101, C:11, D:0
    这中编码方式是通过哈夫曼树来进行编排的:
    在这里插入图片描述

    2.构建一棵哈夫曼树

    知道了哈夫曼编码的方式之后,到底该如何构建一棵哈夫曼树呢?
    从二叉树的根结点到二叉树中所有叶结点的路径长度与相应权值的乘积之和为该二叉树的带权路径长度WPL,将带权路径最小的二叉树称为Huffman树。
    下图展示了哈夫曼树的构建方法:
    在这里插入图片描述
    关于具体哈夫曼树的创建代码,请参考:
    (https://gitee.com/zhang-yucheng329/c-file-compression)

    五、压缩

    压缩过程需要要经过四个步骤:

    1.获取原文件中每个字节出现的次数

    对于获取文件中每个字节出现的次数,采用一个含有256个结构体类型的数组来保存较为方便。因为文件在磁盘中都是以字节的方式来进行存储的,可以用每个字符对应的ASCII码值来作为数组的下标,只需遍历文件中的每一个字节,遇到对应ASCII码的元素对结构体中的count进行++即可。
    如下图,数组的下标与字符的ASCII码值一一对应:
    在这里插入图片描述

    2.根据字节出现的频次信息构建Huffman树

    在构建哈夫曼树时,直接调用之前写过的创建树的方式即可,但需要注意一点:
    哈夫曼树每个节点类型为结构体类型,因此在定义结构体的地方,需要对运算符(+,>,!=,==)进行重载,让编译器知道count之间的比较方式。
    下图是创建Huffman树时需要注意的点:
    在这里插入图片描述

    3.获取Huffman编码

    我们现在已经有了根据频次信息创建的Huffman树,现在只需要遍历Huffman树来获取编码即可。对于编码的获取方式,可以从根节点遍历到叶子节点来获取,也可以从叶子节点向上找到根节点获取。
    这里采用第二种方式来获取编码,需要给节点中增加双亲的指针域,让Huffman树的表示方法为孩子双亲表示法。通过这种方式获取的编码最后需要进行逆置才是最终结果,下图是获取编码后的结果,与期望的编码相同:
    在这里插入图片描述

    4.使用Huffman编码来改写文件(压缩)

    前三个步骤进行完之后,只需改写文件即可。还是需要循环读取文件内容,采取位操作按位或的方式将Huffman编码放置到比特位当中。
    步骤:1.定义ch = 0,先让ch左移一位,再判断Huffman编码的每个比特位是否为1,为1则让ch与Huffman编码为1比特位进行或操作,这样就能将文件按照编码的方式改写。
    最终改写结果:
    在这里插入图片描述
    关于具体文件压缩的代码,请参考:
    (https://gitee.com/zhang-yucheng329/c-file-compression/tree/master/Compress)

    六、解压缩

    1.获取解压缩用到的信息

    解压缩过程与压缩过程相反,需要将压缩文件还原成原文件。但使用解压缩进行还原是需要条件的,不能凭空还原,需要根据原文件信息进行。
    因此,在压缩过程中就需要将解压缩需要的信息重新保存一下。解压缩还原有很多种方法,但每种方法的还原效率不一样,这里选择用哈夫曼树的方式来进行还原:通过原文件字节出现的频次信息,还原出一棵哈夫曼树,再从根节点遍历,读取压缩数据,当读到0往左子树走,读到1往右子树走,直到走到叶子节点的位置即还原了原数据,再回到根节点循环遍历压缩数据。
    在解压缩过程中用到的信息:
    1.原文件后缀
    2.统计频次信息的总行数(方便对数据进行操作)
    3.获取原文件字节出现的频次信息
    4.压缩数据
    往文件中写入信息后:
    在这里插入图片描述

    2.恢复哈夫曼树

    有了这些信息,就可以对哈夫曼树进行恢复,继续进行解压缩的过程了,恢复哈夫曼树的过程相对简单,基于之前写过的构建哈夫曼树的方法,只需对文件中压缩信息做相对应的处理

    3.恢复原文件(解压缩)

    解压缩过程就是:根据压缩数据来遍历恢复的哈夫曼树,压缩数据为1就往右子树走,为0就往左子树走,知道走到叶子节点。通过以上所有步骤就能够完成压缩与解压缩的所有过程了。
    这里还有一个小问题,压缩方法不能处理文件中的汉字,因为汉字是采用UTF-8编码进行编排的,它的编码不在ASCII码表中。因此需要将所有的char类型改变为unsigned char类型!!!
    下面为原文件与解压缩之后的结果:
    在这里插入图片描述
    关于具体解压缩的代码(最终代码),请参考:
    (https://gitee.com/zhang-yucheng329/c-file-compression)

    总结

    以上就是今天要讲的内容,本文简单介绍了基于哈夫曼编码的文件压缩方法,我收获很多。在写代码途中,不免遇到很多bug调试半天还解决不了,但最终还是解决了出来,这也是写代码必经的一个过程。
    以下是我总结完成过程中注意的一些问题:
    ①创建哈夫曼树时,使用优先级队列来保存字符出现的频次信息时,优先级队列的比较方式需要自己进行给出,使用仿函数的方法让比较方式为每个节点中的权值
    ②在使用结构体来创建哈夫曼树时,需要对+,>,==,!=,进行重载,重载的目的:让编译器知道权值中的count之间的比较方式
    ③在构建哈夫曼树时,发现其他节点构建正确,但是值域为1的节点不是叶子节点,是因为数组中还存放着许多字符出现次数为0的节点,需要进行过滤,设置第三个参数invalid来过滤权值为0的节点
    ④再次读取文件时,需要将文件指针的位置重置到文件头部,使用fseek函数或者rewind函数
    ⑤在解压缩时,不一定是8个比特位都需要解压缩,因此需要增加判定条件,只要解压缩后的字节数与原文件相等就停止解压缩
    ⑥压缩和解压缩代码写完后,需要讲char类型改成unsigned char类型,因为原文件可能出现汉字,汉字对应的是utf-8编码,不在ASCII码表中
    ⑦在测试多行数据压缩时,又出现了问题,原因是当读取到\n换行使,并没有将换行所在的数据GetLine,因此解压缩时数据少了一行。
    ⑧在进行大量数据测试时出现问题,发现解压缩一部分内容就停止了,部分数据丢失,但已经解压缩的部分内容与原文件一样。原因是解压缩文件是二进制文件(即压缩结果是二进制数字),二进制文件中可能会
    出现-1(FF),当为-1时就默认读到了文件末尾就结束解压缩过程了。
    改进方法是:
    将所有打开文件(fopen)中文件的读写方式由"r",“w"改为二进制读写式"rb”“wb”
    ⑨经过测试,发现对不同的文件(文本文件,二进制文件),图片,视频都能够进行压缩,但哈夫曼编码的文件压缩对不同种类的压缩率是不同的。
    对于txt/c/cpp类后缀的文本文件,压缩率较高在30%~50%
    对于png/jpg类后缀的图片,压缩率一般在70%~90%
    对于exe类后缀的可执行文件,压缩率较低在80%~90%
    ⑩在对文件进行多次压缩时,压缩结果的大小不是每次会减少,有一个限度。
    同时,哈夫曼编码的压缩方法也是可能会出现压缩结果变大的可能性。当文件中字节的种类偏多,并且字节出现的次数比较平均的情况下,压缩效率就会变差,因为统计字节出现的频次信息时,各个字节出现的次数差不多,构建出来的哈夫曼树就接近平衡二叉树,效果就会不理想。
    当然,也会出现压缩后文件变大的情况:当哈夫曼编码的平均长度大于8字节时,压缩文件就会变大

    展开全文
  • 图像压缩之哈夫曼编码

    千次阅读 2021-10-21 01:06:21
    2 用于图像压缩,可根据图像的像素直方图来进行图像压缩,如PNG格式图像压缩使用的算法就包括哈夫曼编码,在编码过程中并未舍弃信息故哈夫曼编码是一种无损压缩方式。 3.哈夫曼解码 即给定由哈夫曼编码的结果10 11 ...
  • 图像压缩编码基础——笔记整理

    千次阅读 2022-02-18 17:03:29
    图像压缩基础 1)压缩的原因:数字视频码率高达216Mb/s。数据量之大,无论是网络传输,还是存储都构成巨大压力。在保持信号质量的前提,要...信源编码: 降低码率的过程,称为压缩编码,也叫信源编码。 4)压缩方法:.
  • 基于Matlab的图像压缩编码

    热门讨论 2010-03-23 15:56:44
    JPEG基本系统是一种有损编码,无法完全恢复出原图象,信息有一定的丢失,称为有损压缩。尽管我们希望能够无损压缩,但是通常有损压缩压缩比(即原图象占的字节数与压缩后图象占的字节数之比,压缩比越大,说明压缩...
  • 数字媒体技术揭秘四、压缩技术4.1 理论基础廿世纪中叶,为了从理论上证明对信息系统进行优化的可行性,Shannon引入了熵的概念,用来表示信息的不确定性,熵越大,信息的不确定性就越大[4],而信息的不确定性越大,其...
  • JPEG编码压缩率调整

    千次阅读 2021-01-08 01:06:05
    u32Qfactor:量化表因子范围为[1, 99],u32Qfactor 越大,量化表中的量化系数越小,得到的图像质量会更好,同时,编码压缩率更低。同理 u32Qfactor 越小,量化表中的量化系数越大,得到的图像质量会更差,同时,编码...
  • 数据压缩 算术编码 c++ 程序,包括编码和译码 售后服务QQ:857997674 有任何疑问或问题,请咨询QQ
  • 基于哈夫曼编码对文件进行压缩和解压缩(详细讲解) 本文对应c++代码实现链接 一、背景 利用特定的算法来压缩数据的工具,压缩后生成的文件称为压缩包。如果想使用其中的数据,就得用压缩软件对数据进行解压。利用...
  • 本文介绍一下视频压缩编码和音频压缩编码的基本原理。其实有关视频和音频编码的原理的资料非常的多,但是自己一直也没有去归纳和总结一下,在这里简单总结一下,以作备忘。 1.视频编码基本原理 (1) 视频信号的...
  • 音频压缩分为两种,其基本的方法都是消除冗余信息,在这里的冗余信息指的是:人的听觉范围以外的音频信息: (1)有损压缩:消除冗余信息后,无法还原出原声。 (2)无损压缩:消除冗余信息后仍能够还原出原声。
  • 块截断编码图像压缩技术

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

    千次阅读 2018-04-08 21:51:05
    算术编码,是图像压缩的主要算法之一。 是一种无损数据压缩方法,也是一种熵编码的方法。和其它熵编码方法不同的地方在于,其他的熵编码方法通常是把输入的消息分割为符号,然后对每个符号进行编码,而算术编码是...
  • 系统的记录下自己在GPCC中的学习过程,由于代码各个版本更迭很大,目前主要看最新的V12版本。(由于本人菜鸟一枚,如有错误,欢迎指正。) 第一章 点云编码器背景综述 文章目录前言一、点云是什么?二、为什么要对...
  • JPEG)编码算法及压缩过程的实现.pdf
  • 图像压缩编码原理

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

    千次阅读 2018-09-26 16:26:31
    数据冗余:空间冗余、时间冗余、结构冗余、信息熵冗余等,图像的各个像素之间存在着很强的相关性,消除这些冗余不会导致信息损失,属于无损压缩。 视觉冗余:人眼的一些特性,例如亮度分辨阈值、视觉阈值、对亮度和...
  • 1、自编码器结构 目前端到端的图片编码大多使用了自编码器结构。这里的自编码器可以理解为是一种神经网络,label与输入相同,目的是让输出接近于输入,...例如图1-1,Hidden2只有150个节点,可以起到压缩的作用。 ...
  • 主流视频编码压缩技术算法分析 主流视频编码压缩技术算法分析主流视频编码压缩技术算法分析一、MPEG-1技术介绍1、 MPEG-1的层次及语法结构①、运动补偿序列(Sequence)②、图片组(GOP)③、 图片(Picture)④、 ...
  • 压缩算法之字典编码(上)

    万次阅读 多人点赞 2017-09-23 10:50:12
    算法 信息论 字典压缩 LZ77
  • JPEG压缩编码算法原理

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

    千次阅读 2018-03-19 20:09:04
    实验一 无失真信源压缩编码此文系后续整理,懒得copy,对应的方法可以根据需要可以直接下载代码,附件:...
  • 而文件的解压缩实际上就是将压缩文件翻译过来保存到解压缩文件中,需要使用压缩过程中生成的配置文件配合完成。下面将具体介绍文件的压缩和解压缩步骤: 1。统计文件中所有字符的出现次数。由于Ascall码字符一共255...
  • Huffman编码实现压缩压缩

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

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 183,506
精华内容 73,402
热门标签
关键字:

信息的压缩过程是编码吗