数字图像处理：压缩编码

一、霍夫曼编码

1.算法分析

霍夫曼编码是变长编码的一种，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码。
霍夫曼编码的具体步骤如下：
1）将信源符号的概率升序排队。
2）把两个最小的概率相加，形成一个新的概率集合，并继续这一步骤，始终将较高的概率分支放在右边，直到最后变成概率１。
3）画出由概率１处到每个信源符号的路径，顺序记下沿路径的０和１，所得就是该符号的霍夫曼码字。
4）将每对组合的左边一个指定为0，右边一个指定为1（或相反）。

2.题目解析

1.数据结构：
提到霍夫曼编码必须要提到霍夫曼树，所以首先要定义树：节点存放字符与权重（即字符出现次数），还要有左右两个孩子，考虑到最后分配码字的过程，还可以加上深度优先遍历的实现函数。数据结构如下：

2.实现过程：
首先是获取字符，我采用txt文件的方式存储字符串（直接输入读取更简单所以我介绍这种方式），读取过程中直接统计字符与其出现次数，存储在Map中。
然后开始建树，将Map中的字符与频率建成哈夫曼树节点，然后存放在链表LinkedList中；再将链表中的树节点按权重大小升序排列。
开始循环遍历，每次取出最小的两个树节点（也就是在链表中前两个），加和后成为新树，链接上左右两个子树，再按升序放回链表，直至只剩一个树节点。
深度优先遍历分配码字即可。

运行结果如下：

二、香农-费诺编码

1.算法分析

步骤如下：
1.将信源符号按照其概率大小，从大到小排列；
2.将这一组信源符号分成概率之和尽可能接近或者相等的一组（即两组分别的概率和之间的差尽可能小！）；
3.将上面一组符号编码成0，下面一组编码成1，反之亦可；
4.将已经分好的组重复步骤2,3，直到不能再进行分组为止；
5.从左到右一次写出码字。

2.题目解析

1.数据结构：
费诺编码我没有建树，因为要将所有字符按频率大小降序排列，为了方便排序，我设计了txt类，存储字符与频数，数据结构如下：

2.实现算法：
首先从文件中读取字符，步骤同上，存储在Map中；
将Map中存储的数据以txt的形式存储在链表中，降序排列；
再将频数转成频率（小数）；
因为费诺编码要把所有信符分为两组，重复直至每组只剩下一个信号，所以选择递归实现：终止条件为只剩下一个信号（即开始等于结束）；分成大小差不多的两部分：因为降序排列，所以从第一个开始，以前i个信符的频率和的二倍减总和的差为基准，最小的即为所求；然后进行左右递归。

运行结果如下：

三、算术编码

1.算法分析

算术编码的编码对象是一则消息或一个字符序列，其编码思路是将消息或字符序列表示成0和1之间的一个间隔上的一个浮点小数。 在进行算术编码之前，需要对字符序列中每个字符的出现概率进行统计，根据各字符出现概率的大小，将每个字符映射到[0 ，1]区间上的某个子区间中。然后，在利用递归算法，将整个字符序列映射到[0，1]区间上的某个间隔中。在进行编码时，只需从该间隔中任选一个小数，将其转化为二进制数。 符号序列越长，编码表示他的间隔就越小，表示这个间隔所需的二进制位数就越多，编码输出的码字就越长。
  在进行编码过程中，随着信息的不断出现，子区间按下列规律减小：
  a.新子区间左端=前子区间左端+当前子区间左端×前子区间长度
  b.新子区间长度=前子区间长度×当前子区间长度

2.题目解析

1.数据结构：定义qujian类存储区间前后端；
2.实现过程：
首先读取字符串，统计每个字符的上下端点。然后按照公式进行计算直至算到最后一个字符；最转换成二进制取公共部分，忽略0. 即可完成编码。
编码结果如下：

四、比较分析

1.霍夫曼编码特点：

1.Huffman码的编码方法保证了概率大的符号对应短码，概率小的符号对应长码，而且短码得到充分利用。
2.每次缩减信源的最后两个码字总是最后一位码元不同，前面各位码元相同(二元编码情况)。
3.每次缩减信源的最长两个码字有相同的码长。
这三个特点保证了所得的Huffman码一定是最佳码。
4.霍夫曼编码是无损压缩中效率较高的一种编码方式，但压缩过程复杂，运算量大。

2.香农费诺编码特点：

1.香农费诺编码考虑了信源的统计特性，使概率大的信源符号能对应码长较短的码字，从而有效地提高了编码效率。
2.香农费诺编码不一定是最佳码。因为香农费诺编码方法不一定能使短码得到充分利用。当信源符号较多时，若有一些符号概率分布很接近，分两大组的组合方法就会很多。可能某种分大组的结果，会使后面小组的“概率和”相差较远，从而使平均码长增加。
3.香农费诺编码相较于霍夫曼编码更加方便、快捷。

3.算术编码特点：

1.算术编码是比霍夫曼编码的压缩性能更优的一种变长编码方式，，可以采用比霍夫曼编码更少的码字。
2.算术编码的实现方法比霍夫曼更复杂，但是编码效率高。
4.结果比较：
霍夫曼编码：

香农-费诺编码：

可见，香农费诺<霍夫曼。

对于相同字符串，三种方式的编码结果：

可见霍夫曼编码效率小于算术编码，而香农-费诺编码的压缩效率不一定好。

五、代码

代码文件目录：

arithmetic.java

package Arithmetic;

import java.io.*;
import java.util.HashMap;
import java.util.Map;
import java.util.Optional;

/**
 * Description:
 * date: 2022/4/9 16:10
 *
 * @author 颜霸灿烈
 */
public class arithmetic {
    static int sum =0;
    static StringBuffer s=new StringBuffer();
    private static class qujian{
        double start=0.0;
        double end=0.0;
        qujian(double start,double end)
        {
            this.start=start;
            this.end=end;
        }
    }
    static Map<Character,qujian> data=new HashMap<>();
    static Map<Character,Integer>txts;
    //字符串直接给
    public static Map<Character,Integer> read(){
        Map<Character,Integer> res=new HashMap<>();
        res.put('A',400);
        res.put('B',200);
        res.put('C',160);
        res.put('D',120);
        res.put('E',60);
        res.put('F',40);
        res.put('G',20);
        sum=1000;
        qujian q1=new qujian(0,0.4);
        data.put('A',q1);
        qujian q2=new qujian(0.4,0.6);
        data.put('B',q2);
        qujian q3=new qujian(0.6,0.76);
        data.put('C',q3);
        qujian q4=new qujian(0.76,0.88);
        data.put('D',q4);
        qujian q5=new qujian(0.88,0.94);
        data.put('E',q5);
        qujian q6=new qujian(0.94,0.98);
        data.put('F',q6);
        qujian q7=new qujian(0.98,1);
        data.put('G',q7);
        System.out.println("原字符及频率：");
        for(char key:res.keySet())
        {
            int value=res.get(key);
            System.out.print(key+":"+value+" ");
        }
        System.out.println();
        return res;
    }
    //从文件中读取字符串
    public static Map<Character,Integer> readtxt() throws IOException {
        String fileName="src/code.TXT";
        Map<Character,Integer> txts=new HashMap<>();
        File file = new File(fileName);
        FileInputStream fis = new FileInputStream(file);
        InputStreamReader isr = new InputStreamReader(fis);
        BufferedReader br = new BufferedReader(isr);
        String line;
        System.out.println("原字符串为：");
        while((line = br.readLine()) != null){
            System.out.println(line);
            for (int i = 0; i < line.length(); i++) {
                char tmp=line.charAt(i);
                sum++;
                s.append(tmp);
                if(txts.containsKey(tmp))
                {
                    int n=txts.get(tmp);
                    n++;
                    txts.put(tmp,n);
                }
                else
                {
                    txts.put(tmp,1);
                }
            }
        }
//        for(char key : txts.keySet()){
//            int value = txts.get(key);
//            System.out.println(key+":"+value);
//        }
        br.close();
        return txts;
    }
    //压缩
    public static void compress() throws IOException {
        txts=readtxt();
//        qujian q1=new qujian(0,0.2);
//        data.put('a',q1);
//        qujian q2=new qujian(0.2,0.5);
//        data.put('b',q2);
//        qujian q3=new qujian(0.5,0.9);
//        data.put('c',q3);
//        qujian q4=new qujian(0.9,1.0);
//        data.put('d',q4);
//        String ss="bcadc";
        double start=0;
        double end=0;
        for (char key:txts.keySet()) {
            double fre=txts.get(key)*1.0/sum;
            start=end;
            end+=fre;
            qujian tmp=new qujian(start,end);
            data.put(key,tmp);
        }
        String ss=s.toString();
        double L=0;
        double H=1;
        for (int i = 0; i < ss.length(); i++) {
            char tmp=ss.charAt(i);
            qujian qj=data.get(tmp);
            double n=H-L;
            H=L+qj.end*n;
            L=L+qj.start*n;
        }
        String l=decimal2Binary(L);
        String r=decimal2Binary(H);
        StringBuffer res=new StringBuffer();
        for (int i = 0; i < l.length(); i++) {
            if(l.charAt(i)==r.charAt(i))
            {
                res.append(l.charAt(i));
            }
            else{
                res.append('1');
                break;
            }
        }
        System.out.println("算术编码结果为"+res);
        System.out.println("编码长度为"+res.length());
    }
    //纯小数十进制变二进制
    public static String decimal2Binary(double value){
        StringBuilder stringBuilder = new StringBuilder();

        int count = 100; // 限制小数部分位数
        double num = 0;
        while (value > 0.0000000001) {
            count--;
            if (count == 0) {
                return stringBuilder.toString();
            }
            num = value * 2;
            if (num >= 1) {
                stringBuilder.append(1);
                value = num - 1;
            } else {
                stringBuilder.append(0);
                value = num;
            }
        }

        return stringBuilder.toString();
    }
    public static void main(String[] args) throws IOException {
        compress();
    }
}

Fano.java

package Fano;

import Huffman.HuffmanTree;

import java.io.*;
import java.util.*;

import static java.lang.Math.abs;

/**
 * Description:
 * date: 2022/4/8 21:07
 *
 * @author 颜霸灿烈
 */
public class Fano {
    static int res=0;
    static int cnt = 0; //
    static int sum=0;//字符总数
    static LinkedList<txt>datas;//存储降序频率
    static Map<Character,String> fenocode=new HashMap<>();//存储最后的编码结果
    //方便降序
    private static class txt{
        char data;//字符
        int num;//频数
        public txt(char data,int num){
            this.data=data;
            this.num=num;
        }
    }
    public static Map<Character,Integer> read(){
        Map<Character,Integer> res=new HashMap<>();
        res.put('A',400);
        res.put('B',200);
        res.put('C',160);
        res.put('D',120);
        res.put('E',60);
        res.put('F',40);
        res.put('G',20);
        sum=1000;
        System.out.println("原字符及频率：");
        for(char key:res.keySet())
        {
            int value=res.get(key);
            System.out.print(key+":"+value+" ");
        }
        System.out.println();
        return res;
    }
    //从文件中读取统计字符频率
    public static Map<Character,Integer> readtxt() throws IOException {
        String fileName="src/code.TXT";
        Map<Character,Integer> txts=new HashMap<>();
        File file = new File(fileName);
        FileInputStream fis = new FileInputStream(file);
        InputStreamReader isr = new InputStreamReader(fis);
        BufferedReader br = new BufferedReader(isr);
        String line;
        System.out.println("原字符串为：");
        while((line = br.readLine()) != null){
            System.out.println(line);
            for (int i = 0; i < line.length(); i++) {
                char tmp=line.charAt(i);
                sum++;
                if(txts.containsKey(tmp))
                {
                    int n=txts.get(tmp);
                    n++;
                    txts.put(tmp,n);
                }
                else
                {
                    txts.put(tmp,1);
                }
            }
        }
        br.close();
        return txts;
    }
    /*统计频率*/
    static double getSum(LinkedList<Double> p, int begin, int end){
        double sum = 0;
        for(int i = begin ; i <= end ; i++){
            sum += p.get(i);
        }
        return sum;
    }
    //递归实现
    static void Fanocode(LinkedList<Double> p, int begin, int end, String code){
        // 边界条件
        if(begin >= end){
            fenocode.put(datas.get(cnt).data,code);
            cnt++;
            return;
        }
        // 找到分界值
        double sum = getSum(p,begin,end);
        int index = -1; // 初值设定
        double minNum = sum; // 设定最小值
        double tempSum = 0; // 前几个的和
        for(int i = begin ; i <= end ; i++){
            tempSum += p.get(i);
            if(abs(sum-2*tempSum) < minNum){
                index = i; // 记录当前最小的值
                minNum = abs(sum-2*tempSum); // 更新最小值
            }
            else{
                break;
            }
        }
        // 递归左边部分
        Fanocode(p,begin,index,code+'0'); // 左边添加0
        // 递归右边部分
        Fanocode(p,index+1,end,code+'1'); //右边添加1
    }
    //实现压缩
    public static void compressact() throws IOException {
        //读取文件中的字符串
        Map<Character,Integer>txts;
//        txts=read();
        txts=readtxt();
        //降序排列
        datas=new LinkedList<txt>();
        for(char key:txts.keySet())
        {
            int value=txts.get(key);
            txt tmp=new txt(key,value);
            datas.add(tmp);

        }
        Collections.sort(datas,new Comparator<txt>(){
            public int compare(txt a,txt b){
                return (int) b.num-a.num;
            }
        });
        //转化成频率
        LinkedList<Double>p=new LinkedList<>();
        for (int i = 0; i < datas.size(); i++) {
            double fre=datas.get(i).num*1.0/sum;
            p.add(fre);
        }
        String code="";
        System.out.println("香农-费诺编码结果：");
        Fanocode(p,0,txts.size()-1,code);
        for(char key:fenocode.keySet())
        {
            String value=fenocode.get(key);
            res+=(value.length()*txts.get(key));
            System.out.print(key+":"+value+" ");
        }
        System.out.println();
        System.out.println("压缩后总长度："+res);
    }

    public static void main(String[] args) throws IOException {
        compressact();
    }
}

Huffman.java

package Huffman;

import java.io.*;
import java.util.*;
//代码仅供参考，不一定正确，有错误请指正！

public class Huffman{
    static int res=0;
    static HashMap<Character,String> CodingMap;
    public static Map<Character,Integer> read(){
        Map<Character,Integer> res=new HashMap<>();
        res.put('A',400);
        res.put('B',200);
        res.put('C',160);
        res.put('D',120);
        res.put('E',60);
        res.put('F',40);
        res.put('G',20);
        return res;
    }
    //从文件中读取统计字符频率
    public static Map<Character,Integer> readtxt() throws IOException {
        String fileName="src/code.TXT";
        Map<Character,Integer> txts=new HashMap<>();
        File file = new File(fileName);
        FileInputStream fis = new FileInputStream(file);
        InputStreamReader isr = new InputStreamReader(fis);
        BufferedReader br = new BufferedReader(isr);
        String line;
        System.out.println("原字符串为：");
        while((line = br.readLine()) != null){
            System.out.println(line);
            for (int i = 0; i < line.length(); i++) {
                char tmp=line.charAt(i);
                if(txts.containsKey(tmp))
                {
                    int n=txts.get(tmp);
                    n++;
                    txts.put(tmp,n);
                }
                else
                {
                    txts.put(tmp,1);
                }
            }
        }
//        for(char key : txts.keySet()){
//            int value = txts.get(key);
//            System.out.println(key+":"+value);
//        }
        br.close();
        return txts;
    }
    //压缩编码
    public static void compressact()throws IOException{
        Map<Character,Integer>txts;
        txts=read();
//        txts=readtxt();
        LinkedList<HuffmanTree> forest=new LinkedList<HuffmanTree>();
        CodingMap=new HashMap<>();
        System.out.println("字符及频率如下：");
        //建树
        for(char key : txts.keySet()){
            int value = txts.get(key);
            forest.add(new HuffmanTree(value,key));
            System.out.print(key+":"+value+" ");
        }
        System.out.println("");
        Collections.sort(forest,new Comparator<HuffmanTree>(){
            public int compare(HuffmanTree a, HuffmanTree b){
                return (int) (a.weight-b.weight);
            }
        });//排序
        while(forest.size()>1){
            HuffmanTree a = forest.removeFirst();
            HuffmanTree b = forest.removeFirst();//取出前两个
            HuffmanTree c = new HuffmanTree(a.weight+b.weight);//增加新的节点
            c.lChild=a;//连接ac
            c.rChild=b;//连接bc
            int index=0;//用来记录应该插入的位置
            for(;index<forest.size();index++) {
                if (forest.get(index).weight >= c.weight) {
                    forest.add(index, c);
                    break;
                }
            }
            //如果森林里没有比它大的，则插在末尾
            if(index>= forest.size())
                forest.add(index,c);
        }
        HuffmanTree result=forest.get(0);
        result.dfs(CodingMap,"");
        System.out.println("霍夫曼编码结果如下：");
        for(char key : CodingMap.keySet()){
            String value = CodingMap.get(key);
            res+=(value.length()*txts.get(key));
            System.out.print(key+":"+value+"  ");
        }
        System.out.println();
        System.out.println("压缩后总长度："+res);

    }
    public static void main(String[] args) throws IOException {
        compressact();
    }
}

HuffmanTree.java

package Huffman;

import java.util.HashMap;

/**
 * Description:
 * date: 2022/4/8 19:35
 *
 * @author 颜霸灿烈
 */
public class HuffmanTree{
    public int weight;//出现频率
    public char data;//字符
    public HuffmanTree lChild,rChild;//左右两个还在
    public HuffmanTree(int weight){
        this.weight=weight;
    }//构造函数
    public HuffmanTree(int weight,char data){
        this.weight=weight;
        this.data=data;
    }
    /*深度优先遍历分配码字*/
    public void dfs(HashMap<Character,String> cm, String prefix){
        int count=0;//记录有几个孩子
        if(lChild!=null){
            lChild.dfs(cm,prefix+"0");
            //左孩子边为0
            count++;//有一个孩子
        }
        if(rChild!=null){
            rChild.dfs(cm,prefix+"1");
            //右孩子边为1
            count++;//有两个孩子
        }
        if(count==0){//一个孩子都没有，叶子节点
            cm.put(data,prefix);

        }
    }
}

最后

以上就是自觉雪糕为你收集整理的数字图像处理：压缩编码的全部内容，希望文章能够帮你解决数字图像处理：压缩编码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。