当前课程知识点:现代图像分析 > 第六章 图像压缩编码 > 6.4 霍夫曼编码 > 6.4.1 霍夫曼编码学习视频
同学们好 今天我们介绍 霍夫曼编码
也是无损编码中的一种经典编码方法
霍夫曼编码是霍夫曼在1952年根据
可变长最佳编码定理提出的
依据信源集中各信号出现的概率分配不同长度的即时码
那么也就是说,概率比较高的我分配比较短的码字
概率比较低的我分配比较长的码字
使得平均码长比自然码长要短
这是戴维霍夫曼的一个简介
他是美国俄亥俄州人 是加利福尼亚大学
计算机科学系的创始人和终身教授
霍夫曼编码是他在麻省理工攻读博士学位时候的
一篇学习报告提出来的
假设说有这样一组信号100101001 对于定长编码
什么是定长编码
码长是固定的 在这里我们假定这个码长为3
那么也就是说每三个比特我们把它进行一个截取
就可以得到100 101和001 3个码字
那么对于变长编码 我们就无法进行码字解析了
因为我们没有对应的码表
那我们看一下 什么是即时码
即时码必须是唯一可译码
对一组即时码来说 其中的任一个码字
都只能与一种信号存在对应关系,也就是一一映射的关系
而且任意一个码字都不能是其它码字的前缀
那么即时码产生的常用的树形结构
如果这个图所示
在这里1 01 001 0001和0000 它们都是即时码
假设接收到这样一组信号
有了上面的即时码我们就可以唯一解析出以下四个码字
分别是1 001 01和001
看一下霍夫曼编码的过程
假设有一个图像序列 总共含有8个灰度级 即x1到x8
那么统计这8个灰度级的概率分别为
0.4 0.18 0.10 0.10 0.07 0.06 0.05和0.04
当然这八个灰度级的总概率为1
霍夫曼编码的过程
首先我们对这8个灰度级按照概率大小
从大到小进行依次排列
比如第一列 然后寻找最小的两个概率
0.04和0.05进行合并 所谓的合并就是概率相加
那么0.05加0.04等于0.09 得到了0.09
放入到原来的信息源中进行概率的重新排序
就可以看到0.09会插入到0.10和0.07之间
接着对这个新产生的概率排序继续寻找最小的
两个概率并求和再重新排序
按照这样一个规律依次进行
那么最终可以得到两个概率分布 分别是0.60和0.40
接下来对它进行码字的分配
其中我们将概率小的分0 概率大的分1
那么依次进行分配就可以得到霍夫曼的一个编码
从x1到x8对应的码字分别为x1是1 x2是001 x3是010
x4是0000 x5是0110 x6是0111 x7是00010 x8是00011
我们可以看到x1是概率最大的
它码字是最短的 只有1个比特
而x7和x8是概率最小的 它的码长是分别是5个比特
那我们总结一下霍夫曼编码的一个步骤
第一步 将灰度等级按概率从大到小进行排列
取两个最小概率相加形成一个新的概率集合重新进行排序
反复这个步骤 一直到只有两个概率为止
那么最终会构成霍夫曼树
根据霍夫曼树分配码字就可以得到霍夫曼编码
那么这是一个霍夫曼编码以及码长的一个排布表
我们根据这个排布表就可以计算霍夫曼编码的平均码长
也就是每一个灰度级对应的概率和它码字的乘积之和
最终可以得到2.61
而自然码长是3 那么显然2.61是小于3的
也就是说霍夫曼编码进行了一个压缩而且这种压缩是无损的
我们在计算它的熵可以得到是2.55
编码效率就等于熵除以平均码长得到97.7%
霍夫曼编码是无损或者无失真编码中
效率比较高的一种编码方法
在分配码字过程中随机赋予0和1的不同 会使码字不唯一
而码字长和平均码字长是不会改变的
它是唯一可解码的
霍夫曼编码的缺点是信源缩减的过程比较复杂
运算量比较大
今天的课程到此结束,同学们 再见
-1.1 图像及图像的基本概念
--1.1.2 图像及图像的基本概念作业
-1.2 数字图像处理的起源
--1.2.2 数字图像处理的起源作业
-1.3 数字图像处理的步骤和方法
--1.3.2 数字图像处理步骤和方法作业
-1.4 数字图像处理系统的组成
--1.4.2 数字图像处理系统的组成作业
-1.5 数字图像处理主要应用领域
--1.5.2 数字图像处理主要应用领域作业
-2.1 色度学基础
--2.1.3 色度学基础作业
-2.2 人的视觉特性
--2.2.1 人的视觉特性作业
-2.3 图像数字化
--2.3.2 图像数字化作业
-2.4 数字图像特点
--2.4.2 数字图像特点作业
-3.1 图像变换的基本概念
--3.1.2 图像变换的基本概念作业
-3.2 图像的几何变换
--3.2.2 图像的几何变换作业
-3.3 图像的离散傅立叶变换
--3.3.2 图像的离散傅立叶变换作业
-3.4 图像变换的一般表示形式
--3.4.2 图像变换的一般表示形式作业
-3.5 图像的离散余弦变换
--3.5.2 图像的离散余弦变换作业
-3.6 图像离散沃尔什-哈达玛变换
--3.6.2 图像离散沃尔什-哈达玛变换作业
-3.7 K-L变换
--3.7.2 K-L变换作业
-4.1 图像的对比度增强
--4.1.2 图像的对比度增强作业
-4.2 直方图修正
--4.2.3 直方图修正作业
-4.3 图像平滑
--4.3.4 图像平滑作业
-4.4 同态滤波
--4.4.2 同态滤波作业
-4.5 图像锐化
--4.5.2 图像锐化作业
-4.6 图像的彩色增强
--4.6.2 图像的彩色增强作业
-5.1 退化模型及常见退化模型
--5.1.2 退化模型及常见退化模型作业
-5.2 图像的无约束恢复
--5.2.2 图像的无约束恢复作业
-5.3 图像有约束最小二乘恢复
--5.3.2 图像有约束最小二乘恢复作业
-6.1 概述
--6.1.1 概述作业
-6.2 图像编码基本理论
--6.2.2 图像编码基本理论作业
-6.3 无损编码理论
--6.3.2 无损编码理论作业
-6.4 霍夫曼编码
--6.4.2 霍夫曼编码作业
-6.5 算数编码
--6.5.2 算数编码作业
-6.6 预测编码
--6.6.2 预测编码作业
-6.7 正交变换编码
--6.7.2 正交变换编码作业
-7.1 图像分割的定义及依据
--7.1.2 图像分割的定义及依据作业
-7.2 边缘点检测
--7.2.2 边缘点检测作业
-7.3 边缘线跟踪
--7.3.3 边缘线跟踪作业
-7.4 门限化分割
--7.4.2 门限化分割作业
-7.5 区域分割法
--7.5.2 区域分割法作业
-7.6 聚类分割法
--7.6.3 聚类分割法作业
-8.1 像素间的基本关系
--8.1.2 像素间的基本关系作业
-8.2 目标物的边界描述
--8.2.2 目标物的边界描述作业
-8.3 目标物的区域描述
--8.3.2 目标物的区域描述作业
-8.4 图像的几何特征
--8.4.2 图像的几何特征作业
-8.5 特征描述子
--8.5.4 特征描述子作业
-9.1 图像匹配
--9.1.2 图像匹配作业
-9.2 图像分类
--9.2.2 图像分类作业
-9.3 图像识别
--9.3.2 图像识别作业
-9.4 模式识别分类专题
--9.4.4 模式识别分类专题作业
-中国天网
-车道检测
-期末测试
--期末测试