霍夫曼算法范文（精选7篇）
霍夫曼算法 第1篇
数字图像水印技术是目前检测数字图像可信度的有效方法之一。因其具有良好的隐蔽性、鲁棒性和可检测性, 目前已经引起了研究者的广泛关注[1]。但数字图像水印技术较高的算法复杂度却成为制约其发展的不利因素。文献[2]提出的一种基于边缘特征和纹理特征的数字水印算法, 将边缘特征的特征向量嵌入到数字图像中;文献[3]中提出了一种基于人类视觉系统特征的离散余弦变换数字水印算法, 对水印信息进行Amold置乱变换, 将水印信息量化嵌入到载体图像的DCT域直流分量中;文献[4]中对基于图像内容的小波域鲁棒水印技术做了进一步的研究。这些研究都取得很好的效果, 但由于算法要提取图像的不同特征及进行置乱、扩展等变换, 复杂度较高, 不利于该技术的应用。
为了解决算法复杂度的问题, 本文提出了一种基于图像特征和霍夫曼编码的数字水印新算法。由于霍夫曼编码本身就是基于最小遍历路径的, 因此将霍夫曼编码引入数字水印领域中能大大减小水印算法的时间复杂度和空间复杂度。
1 图像特征和霍夫曼编码
常用的图像特征有颜色特征、纹理特征、形状特征、空间关系特征。颜色特征是一种全局特征, 描述了图像或图像区域所对应的景物的表面性质。一般颜色特征是基于像素点的特征。纹理特征需要在包含多个像素点的区域中进行统计计算。在模式匹配中, 这种区域性的特征具有较大的优越性, 不会由于局部的偏差而无法匹配成功。各种基于形状特征的检索方法都可以比较有效地利用图像中感兴趣的目标来进行检索。空间关系, 是图像中分割出来的多个目标之间的相互的空间位置或相对方向关系, 这些关系也可分为连接/邻接关系、交叠/重叠关系和包含/包容关系等。
霍夫曼编码是一种编码方式, 是一种用于无损数据压缩的熵编码算法。霍夫曼树又称最优二叉树, 是一种带权路径长度最短的二叉树。所谓树的带权路径长度, 就是树中所有的叶结点的权值乘上其到根结点的路径长度[5]。
2 提出的新水印算法
Input:原始图像I
Output:含有水印的图像I*
Step1对原始图像I进行三级小波分解, 小波基选择db1, 得到HHi, HLi, LHi, LLi (i=1, 2, 3) , 分别是小波变换后的逼近分量和细节分量;
Step2利用Canny算子提取出LL3子带的边缘特征, 记为Edge;
Step3将LL3嵌入到LH3中, 将LL3和LH3分为若干个44矩阵, LL3的每个矩阵中包含16个像素值, 将这16个像素值利用霍夫曼编码的方法进行编码, 然后用最顶层树结点替换LH3中的像素值, 此结点即是本算法的水印信息, 具体替换哪个像素值由叶子结点的个数确定, 即如果有N个叶子结点, 就替换LH3中对应小矩阵中的第N个像素值;
Step4对原始逼近分量和修改后的细节分量进行三级小波逆变换, 得到含有水印的图像I*。
3 水印提取算法
Input:含有水印的图像I*
Output:图像认证结果
Step1对含有水印的图像I*进行三级小波分解, 小波基选择db1, 得到HHi*, HLi*, LHi*, LLi* (i=1, 2, 3) , 分别是小波变换后的逼近分量和细节分量;
Step2从LH3*中根据嵌入过程嵌入的位置, 提取出像素值, 此像素值即是本算法提取出的水印信息;
Step3对比原始水印信息和提取出的水印信息, 验证图像, 对图像可信度进行分析。
4 仿真实验
为了验证算法的有效性和可行性, 做了大量的实验, 本文实验全部在Matlab 7.0和Photoshop CS3上完成, 水印嵌入部分、提取部分、信噪比计算部分等都在Matlab 7.0中完成, 对重构图像的部分攻击操作在Photoshop CS3中完成, 再把攻击后图像在Matlab 7.0中读取并提取水印。实验图像采用网络资源或者自行拍摄的二维图像等, 对图像大小、分辨率等无特殊要求。现以一幅图为例:实验中以256256大小的灰度图像进行测试, 图1表示原始图像, 采用db1’的小波基对图像进行小波分解;图2表示嵌入水印后的图像;图3是用于提取水印信息的图像特征, 即小波第三级变换的低频边缘特征。
水印嵌入算法的软件编程是在Matlab 7.0中实现的, 主要代码如下:
因为算法代码简单, 执行循环较少, 所以算法的时间复杂度较低, 容易实现。
仿真实验表明, 采用本文算法后的嵌入水印图像的峰值信噪比为49.8472 d B, 从主观视觉效果上评价, 与原始图像非常一致, 体现了本文算法的不可视性。表1是本文算法的PSNR值与其他算法的比较。
(单位:db)
提取水印的核心代码如下:
表2是含有水印的图像经过一系列攻击后, PSNR值和水印信息与原始水印信息的相关系数。
图4是对含有水印的图像进行顺时针旋转10度攻击后的图像;图5是进行系数0.02高斯噪声攻击后的图像;图6是锐化图像的结果;图7是腐蚀图像的结果;图8是图像增亮后的结果;图9是与另外一幅图像进行相乘的结果。
5 结语
提出了一种基于图像特征和霍夫曼编码的数字水印新算法, 本文使用的是图像的边缘特征, 算法同样适用于图像的纹理特征、颜色特征、突变特征、关系特征等, 具有很好的扩展性。特征的选取对实验结果无明显影响, 用户选择最易提取的特征即可。将霍夫曼编码原理引入到数字水印领域, 具有一定的创新性。算法只使用边缘特征, 利用霍夫曼编码求出待嵌入的水印, 复杂度低, 容易实现, 且使用的是图像本身的特征, 载荷小, 通过仿真实验证明算法具有很好的性能, 隐蔽性、鲁棒性都较好。算法可以应用在照相馆照片的版权鉴定、网络上图像的版权鉴定、军事秘密图像可信度鉴定等等。但是图像经过个别类型攻击后水印与原始水印的相关系数不够理想, 今后将做进一步研究和改进。虽然本算法的PSNR值比一些算法高, 但是也低于某些优秀的算法, 这也是今后改进的方向。
摘要：将霍夫曼编码原理引入数字水印领域, 提出一种基于图像特征的数字水印新算法, 以降低数字水印算法复杂度。算法在嵌入水印时, 首先将数字图像进行三级小波分解, 并提取三级逼近分量的边缘特征。然后用霍夫曼编码计算边缘特征矩阵的顶端结点, 再将此结点值嵌入到细节分量中。最后进行三级小波逆变换得到嵌入水印的图像。算法在提取水印时, 根据嵌入水印的过程找到嵌入点, 提取出待检测图像中的水印, 并分析得到检测结果。仿真实验表明, 该算法复杂度低、载荷小, 具有很好的有效性和可行性。
关键词：数字水印,图像特征,霍夫曼编码,边缘特征,小波变换
参考文献
[1]李国良, 谭月辉, 齐京礼, 等.多小波域可恢复半脆弱数字水印算法[J].计算机工程, 2011, 37 (17) :84-86.
[2]李亚琴.利用图像纹理和边缘特征的数字水印方法[J].计算机工程与应用, 2011, 46 (22) :124-126.
[3]王洪秀, 王冰.基于图像纹理复杂度的数字水印算法[J].计算机工程, 2011, 37 (17) :102-104.
[4]张力, 韦岗.一种基于图像内容的小波域鲁棒水印技术[J].中国图象图形学报, 2002, 7 (9) :975-979.
[5]张敏瑞, 路陈红, 易克初.霍夫曼码平均冗余量的研究[J].西安科技学院学报, 2004, 24 (2) :228-239.
[6]陈力, 艾勇胜.基于DWT的数字水印改进算法[J].信息系统工程, 2011 (9) :18-20.
[7]魏雯.基于小波变换和HVS的数字水印算法研究[J].山西电子技术, 2010 (4) :35-37.
霍夫曼算法 第2篇
十多年来, 在信元编解码领域的研究中音频信号的压缩编解码越来越成为人们重视和研究的课题, 尤其是最近10多年来, 计算机科学技术的高速发展, 数字音频逐渐取代了模拟音频, 成为了多媒体技术领域的重要研究方向, 尤其是宽带音频的高效编码得到了广泛发展和应用。数字音频在消费电子、网络、广播移动无线通信和数字影视等众多领域中有了广泛的应用。但是在很多领域中由于存储介质容量和传输带宽的限制, 都要求在很低的比特率下实现数字音频信号的传输。虽然当前的数字音频编码技术已经达到很高的水平, 但还是不能满足人们各式各样的个性化需求[1]。
2 AAC音频解码器结构
MPEG-2AAC解码器的组成, 包括比特流解复用、无噪解码、反量化、比例因子解码、M/S、IS.、TNS、合成滤波器组和形成PCM模块。MPEG-2AAC的解码流程为:比特流解复用模块从原始的AAC码流中分离出数据和控制信息, 数据信息送至量化频谱解码模块, 控制信息则送到各个相关模块, 并由控制信息决定各个功能模块是否激活。量化频谱解码模块根据指定的码本对输入的数据进行Huffman解码, 解码后的量化频谱送到逆量化模块, 将解出的1024个量化数据进行逆量化变换。缩放因子解码模块将经由Huffman和差分解码后得到的缩放因子与逆量化后得到的频谱数据加权, 得到实际的频谱值, 并将其传送至M/S解码模块。M/S解码模块通过矩阵运算将传输左右声道频谱和与差的两路频谱数据变换为原始的左右声道。IS解码模块将右声道频谱通过对左声道频谱值做能量加权实现强度立体声解码。TNS解码模块将频谱数据通过一组TNS无限冲积响应IIR滤波器, 进行时域噪声整形。最后, 合成滤波器组将经过上述各模块处理后的频谱数据转化成时域数据, 完成音频解码[2]。
3 快速霍夫曼解码的应用和实现
AAC解码器复杂度最高的Huffman解码部分。由于AAC标准中规定的每一个Huffman码表都很长, 因此传统的算法解码速度比较慢特别是对于支持多路解码的系统而言, 实践证明最坏的情况下, 对于5.1声道的AAC音频输入, 在MIPS24Kc主频400M下, 每一帧的解码必须在150Mbps以下。因此, 我们在这里提出一种快速Huffman解码算法, 并在本系统中实现。
通过观察Huffman码表的规律, 我们可以看出:相同的码字加1递增, 如果码字后面补0扩找到m位 (m是码表中的最大码长) , 则码长小的码字, 其扩展后的值一定小于码长大的码字扩展后的值。为了实现快速Huffman解码, 可以根据上述Huffman码表的规律建立一个定位表, 用于对Huffman码表定位, 从而迅速找到匹配值。定位表中也存放了三个信息, 分别是扩展的码字、实际码长和码字在Huffman码表中的存放地址。对于Huffman码表中不同的码长, 提取其最小的码字及存放地址, 并将码字后面补0到m位, 形成扩展的码字[3]。
建立了所需要的定位标志后, 接着我们设计出下面的伪代码来具体描述快速Huffman解码算法的实现。
通过上述对任务和内存访问的优化, 以及快速Huffman算法的实现, 我们在MIPS仿真器上进行模拟运行两路AAC音频解码, 实验的结果, 在支持两路5.1声道解码的情况下, 每一路的解码性能为120Mbps。因此, 可以在输出端得到较高质量的音频信号。
4 实验结果和分析
为了验证将快速霍夫曼解码应用于AAC解码器后的效果, 我们利用MIPS公司出品的MIPS软件仿真器来运行我们的代码, 并设定CPU为主频400MHz的MIPS24Kc, 同时利用COOLEDIT软件来读取解码后的PCM文件, 从而模拟出解码后的音频波形图。在实验中, 我们选用的文件是为编码压缩的AAC正弦波信号。经过本系统的解码后, 通过读取MIPS24Kc的协处理器中的计数器后, 得到整个系统的性能为70MIPS~80MIPS, 同时得到如图1所示的波形图。仿真结果无论从解码的效率和效果来说都非常理想。
通过利用快速霍夫曼解码, 改进了传统的无噪声解码过程, 在很大程度上提高了系统的解码效率, 节省了CPU的负载, 成功并且高效的完成了AAC音频解码过程。
参考文献
[1]ISO/IEC13818-3.Information Tech-nology一Generic Coding of Moving Picture and Associated Audio Infor-mation一Part3:Audio.ISO/IEC JTCI/SC29WG11, 1998.
[2]卢官明, 宗昉.数字音频应用原理[M].机械工业出版社, 2005.1.
赫夫曼算法效率的优化 第3篇
现代信息技术所使用的赫夫曼算法普遍存在运行效率不高、算法时间复杂度偏大 (其时间复杂度为O (n2) ) 的缺陷, 直接制约了赫夫曼算法的实际应用。笔者提出了一种优化改进的赫夫曼算法, 以期降低算法的复杂度, 提高运行效率, 提升算法的应用前景。
1.1 最佳判定树问题 (分类优化)
举例:某产品的分类标准如表1所示。
一般的, 根据检测值来判定某个产品的等级算法的判定树可采取如图1所示的形式。
但是这种方法存在一个明显的缺陷就是效率的不可预见性, 当等级在A, B左右的产品占绝大部分的时候, 算法的效率还不错, 但当等级E在结果中占绝大部分的时候, 算法的时间复杂度便显著增加, 可以计算, 判定树计算平均执行次数为0.1*4+0.3*4+0.4*3+0.15*2+0.05*1=3.15 (次) 。为了降低时间复杂度, 我们借助赫夫曼算法, 先取样进行统计, 优化判定树。假设此次统计后的质量分布统计情况如表2。
根据统计后的情况便可建立如图2的判定树。
它实际的平均执行次数为0.1*2+0.3*2+0.4*1+0.05*3+0.15*3=2.2 (次) , 显然优化后判定树的计算效率大大提高了。
同样的情况也会出现在成绩分布统计等问题中。所以当统计中显示的数据比较集中及某个等级的覆盖率比较高的时候, 采用赫夫曼判定树便会大大提高程序的执行速度。
另外在人力资源的多环节选拨过程中, 由于每个环节需要淘汰一定比率的人数, 因此通过赫夫曼判定树的方法制定部分满足的情况统计, 也会节省很大的人力物力和财力, 为选拔工作带来很大的方便。
1.2 报文压缩 (赫夫曼编码应用)
赫夫曼编码采取无损的方式对报文进行压缩, 所以在对已压缩的资料解压缩时, 资料的内容会和原始资料内容相同, 这种方法的应用非常广泛, 压缩率可达20%-90%。
假设在要对一篇由5个字母组成的报文进行压缩时, 每个字母的出现个数分别为:100, 80, 50, 40, 30。为了要区分这些字母, 每个字母需要使用[log25]=3 (bit) 来表示。那么, 一共需要3*300=900位来储存这篇文章。其实这是一种固定长度码原则, 当报文中出现n种字符的时候, 每个字符需要使用[log2n]bit长度来表示, 显然当报文种类多且个数比较分散的时候, 这种方法的利用率不是很高, 于是我们来介绍一种可变长度码。这种编码的原则是多出现的字符用较少的bit来表示, 少出现的字符用较多的bit来表示, 即利用贪心算法的思想解决编码问题, 有效地达到无损报文压缩的目的, 下面对上面的样例进行说明。根据可变长度码的编码原则, 各个字符可以如图4表示。
现在需要的编码长度为100+80+50*2+40*2+30*3=450, 通过比较可以发现, 报文的大小被大大压缩了, 节省了大量的存储空间, 而内容却未发生变化, 达到了无损压缩的目的。
现实生活中的报文中出现会近百种的字符, 而有很大一部分的字符的出现比率会很高, 因此通过这种可变长度码即赫夫曼编码的应用, 可以在保持内容不丢失的情况下达到很高的压缩率, 具有很大的现实意义。
通过以上叙述, 不难发现, 赫夫曼算法在这些应用技术中扮演了核心调控的角色, 赫夫曼算法的效率高低直接影响着这些信息技术的应用前景和市场空间。
2 赫夫曼树和赫夫曼编码实例
2.1 算法实例
现给出一道赫夫曼树简单应用的题目, 读者可以加深对赫夫曼算法的认识。
计划将一块未知长度的木头锯成N块, 每次锯一块长度为M的木头需要付费为M, 为了得到N块小木头, 至少需要付多少钱。笔者首先给出一个样例具体说明这个问题。
如图5, 需要将一块木头锯成长度分别为8, 5, 8的3块, 得出需要付钱为34, 并且可以通过计算确定, 该方法是付费最少的方法。
问题并不复杂, 但是如何建立合适的数学模型, 实现程序化的高效解决问题呢?问题的关键在于应该采用怎样的算法来解决。笔者从样例入手, 建立一个简单的数学模型, 如图6。
可以看到, 木块总长度即为图中被圈起来的数字的和:34=13+21, 而付费数额:34=5*2+8*2+8。通过这个简单的样例, 很容易看出赫夫曼树以及树的带权路径长度两点知识在解决这个问题的时候发挥了决定作用, 这就是笔者需要的数学模型。实际上, 只需要对输入的小木头作为每个特点的结点建立一个赫夫曼树即可, 下面是笔者的思路: (1) 建立赫夫曼树的结构体, 动态分配数组存储赫夫曼树的结点 (一棵完全二叉树中根结点数=叶子节点数-1, 因此在定义时需要m=2*n-1个结点来存放) ; (2) 对前n个结点初始化, 只需将读入的权值更新weight即可, 其他为0;而对于后n-1也就是m-n个结点, 只需初始化全为0即可; (3) 建立一棵赫夫曼树:每次从所有结点中取出两个权值最小的结点, 对取出的最小的两个结点的权值相加作为新的结点的权值, 并更新它们的父结点和子结点所指的位置; (4) 对后面的n-1个结点的权值相加即为上述问题所要求解的值。
对于这种方法, 在情况简单的时候是没有什么问题的, 但是在过程中使用了双重循环, 当结点数量增大至一定范围的时候使得时间复杂度 (n2) 超出了我们所能容忍的限度。即这是一个超时算法, 必须加以改进。
2.2 改进算法
根据上述算法, 可以将运算的时间复杂度控制在nlgn以内, 而外层的一层循环是必不可少的, 所以算法的优化只能发生在寻找两个最小权值结点处。上面的算法在寻找结点的时候过于暴力, 这是导致运算超时最重要的原因, 所以一定有另一种更优的查找方法, 这里笔者使用了一个新的概念优先队列。
优先队列就是多个元素的集合, 每次从队列中取出优先级最高的元素, 此时的算法复杂度为lgn, 应该可以满足正常情况下对时间复杂度的要求。
(1) 新建结点。
(2) 同样按照上面的步骤, m=2*n-1, 但此时需要分配m+3个结点 (原因可以参考第4步) 。
(3) 定义最小优先队列q并且初始化, 其中的每个元素为赫夫曼树的结点。
(4) 取出最小优先队列的结点, 并分别进行保存 (使用前面额外分配的两个节点) , 更新新结点的权值为两最小结点权值的和, 优先级的大小与权值相等, 下标保存当前新结点的位置, 最后将当前结点入队列:
笔者采用多组不同数量级的测试数据, 比较上述两种算法的效率, 得到了如表3的测试结果。对比优化前后的运算时间, 可以得到如下结论: (1) 当需要构建成树的节点很少时, 优化算法在时间上并不具备优越性; (2) 当节点的个数的数量级达到10^2左右时, 优化算法的优越性开始慢慢体现出来, 并且优化的效率随着节点数量的增加而增强; (3) 当节点值不具备规律性而且节点数量级很大的时候, 优化算法的优越性体现的特别明显; (4) 在实际分类优化工作及其他信息处理中, 数据总体的特点是数量级巨大且无规律性, 因此优化算法具有很强的现实意义及应用性。
2.3 赫夫曼编码
在编码中, 若各码字长度严格按照码字所对应符号出现概率的大小逆序排列, 则编码的平均长度是最小的。赫夫曼编码就是这样一种变长的编码, 根据字符出现的概率来构造平均长度最短的编码。例如快速远距离通信中所用到的电报, 就是将报文中的每个字符出现的频率高低构造出一棵赫夫曼树, 按每个字符和节点的位置进行赫夫曼编码, 经编码后的报文总长减少。接受报文的一方只要使用同一棵赫夫曼树, 就可把编码还原成原来那组字符。显然赫夫曼编码是前缀编码, 否则, 编码就不能进行翻译。
赫夫曼编码在实际电文传递操作中有较多的应用, 尤其是当电文中某一个或是多个字符多次重复出现时候, 可以有效地减少传递报文的长度。例如要传递电文ABCDAAAB’, 通常的做法是设计A.B.C.D的编码分别为00.01.10.11, 总长为16位, 可是如果设计A.B.C.D为0.10, 110, 111的时候, 此时满足任意一个字符都不是另一个字符的前缀编码, 且长度只有14位, 显然这在大量电文传递的过程中大大减少了电文的传送量。
3 结束语
优化后的算法明显降低了赫夫曼算法时间复杂度, 进一步提升了赫夫曼算法在应用领域内的应用范围。通过实验, 验证本算法的实际可行性和效率优先性。
参考文献
[1]严蔚敏, 吴伟民.数据结构 (C语言版) [M].北京:清华大学出版社, 1997.
[2]王晓东.算法分析与设计[M].北京:电子工业出版社, 2004.
哈夫曼算法及其应用研究 第4篇
1 赫夫曼算法
1)根据给定的n个权值{w1,w2,...,wn}构成n棵二叉树的集合F={T1,T2,...,Tn},其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树均空。
2)在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
3)在F中删除这两棵树,并将新得到的二叉树加入F中。
4)重复2和3,直到F只含一棵树为止。这棵树便是赫夫曼树。
2 赫夫曼算法的一种实现方法
3 Huffman算法的应用
3.1 赫夫曼编码
Huffman编码是一种基于符号频率统计的编码方式,是无损的压缩算法,一般用来压缩文本和程序文件。其基本思想是:首先统计文本文件中各字符出现的频度,然后以此频度作为权重,利用Huffman算法构建Huffman树,约定左子树分支表示字符0,右分支表示字符1。则从树根到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码,即Huffman编码。
本文建立Huffman编码的算法的基本思路是:n个字符的Huffman编码用n个字符单链表表示。首先建立n个单链表的头结点,然后依次从叶子到根逆向生成字符单链表,最后从头结点开始,遍历这个字符单链表,即叶子结点字符的Huffman编码。实现程序如下:
各字符的二进制编码为:
a(5):0001 B(29):10 C(7):1110 D(8):1111
E(14):110 F(23):01 G(3):0000 H(11):001
用Huffman算法构造出的这棵扩充二叉树给出了各字符的编码,同时也用来译码。从二叉树的根开始,用需要译码的二进制位串中的若干个相邻位与二叉树边上标的0、1相匹配,确定一条达到树叶的路径。一旦到达树叶,则译出了一个字符,再回到树根,从二叉树位串中的下一位开始继续译码。也可以建立译码字典。
3.2 判定树
在解某些判定问题时,如果将不同情况出现的频度作为权重的话,利用Huffman算法可以构建最佳判定树。在编制一个将百分制转换成优、良、中、及格、不及格五级分制的程序时,一般学生的成绩呈正态分布,各级别的比例分别为:优秀10%,良好30%,中等40%,及格15%,不及格占5%左右。利用上述Huffman算法构建的判定树如图3所示。按最佳判定树编写程序,可提高比较的效率,显著降低操作时间。
3.3 最佳归并树
在外部排序中,对多个不等长的有序记录的二路归并时,利用Huffman树可以得到最佳合并顺序,即最佳归并树。
设有6个有序表A、B、C、D、E、F,分别含有10,35,40,50,60和200个数据元素,各表中元素按升序排列。要求通过5次两两合并,将6个表最终合并成1个升序表,并在最坏情况下比较的总次数达到最小。将各表长作为权重,用上述的Huffman算法构建的最佳合并树如图4所示。
4 结论
Huffman树与Huffman编码有着广泛的应用,例如对Huffman编码进行改进可用于软件测试数据进化生成[3]、SVM多分类器构造[4]、超光谱图像分层无损压缩[5]、基于稀疏分解的交通图像压缩中[6]等等。因此,正确理解Huffman算法的实质,对有关的研究工作提供有益的启示。
参考文献
[1]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2010:144-148.
[2]许卓群,杨冬青,唐世渭,等.数据结构与算法[M].北京:高等教育出版社,2006:126-128.
[3]巩敦卫,张岩.一种新的多路径覆盖测试数据进化生成方法[J].电子学报,2010(6):1299-1304.
[4]谷胜伟.基于赫夫曼树的SVM多分类器构造方法[J].滁州学院学报,2009,11(3):41-43.
[5]张威,田峰.超光谱图像分层无损压缩方案[J].小型微型计算机系统,2011,32(12):2499-2503.
哈夫曼算法在数据压缩中的应用 第5篇
关键词：数据压缩,哈夫曼算法,优先队列,对象序列化
1 引言
在数据的存储和表示中常常存在一定的冗余度,一些研究者提出了不同的理论模型和编码技术降低了数据的冗余度。Huffman提出了一种基于统计模型的压缩方法[1],Ziv Jacob提出了一种基于字典模型的压缩方法。基于统计模型的Huffman方法以统计推理为数学基础,算法简单明了,是数据压缩中的一个重要方法,有着广泛的应用。学者围绕统计模型对Huffman方法提出了许多改进的措施,如Cormack Gordorn V提出了一种自适应的哈夫曼算法[2]。
介绍了哈夫曼算法的基本思想,运用哈夫曼算法设计了一个文件压缩器,用Java语言内置的优先队列、对象序列化等功能实现了文件压缩器的压缩和解压功能。
2 哈夫曼算法
文件压缩的基本思想是对字符设计长度不等的编码方案,对出现次数多的字符用尽可能短的编码表示,这样文件的总长度就会降低,实现文件压缩。比如有字符串“ABACADA”,4个字符需要两个比特编码,假设A、B、C、D的编码分别是00、01、10和11,则整个字符串可表示成00010010001100,总长度14个比特。如果A、B、C、D的编码分别是0、10、110和111,则字符串总长度为12比特。设计长短不等的编码方案时,必须满足一个字符的编码不能是另一个字符编码的前缀,以保证解码成字符的转换过程中不发生歧义,这种编码称为前缀编码。
哈夫曼算法提出了一种编码方法,使得文本总长度最短。其基本思想是利用字符的频率作为权重,以字符作为叶结点构造一颗最优二叉树(也称为哈夫曼树),使得带权路径长度WPL=W1L1++Wn Ln最小,其中Wi表示第i个字符结点的权重,Li表示第i个字符结点的路径长度。哈夫曼算法流程如下:
(1)每个字符创建一棵二叉树构成一个树集合F={T1,T2,Tn},其中二叉树Ti的根结点为权重wi,左右子树为空。
(2)在树集F中选取两颗根结点权值最小的树作为左右子树构成一颗新的二叉树,根结点为左右子树根结点的权重之和。
(3)在树集F中删除这两颗树,把新得到的二叉树加入到F中。
(4)重复步骤2和3,直到F中只有一棵树为止。
例如字符串“ABACADA”4个字符A、B、C、D的频率分别为4、1、1、1。以字符频率为权重构造的最优树如图1所示。
利用图1的最优二叉树,A、B、C、D的编码分别是0、10、110和111。这种以字符频率为权重,构造一颗最优二叉树,使得带权路径长度最小的前缀编码方案称为哈夫曼编码。哈夫曼算法保证了高频字符用短编码,低频字符用长编码,到达整体编码长度最短,从而实现文件压缩的目的。
3 文件压缩器的设计与实现
文件数据在机器内部以二进制形式存在,机器对二进制比特以字节为单位进行处理。从机器处理层面上来说,对文件数据的压缩就是对字节码形式的数据进行压缩。文件压缩器的一个设计思想就是对高频字节码用短编码,低频字节码用长编码,把文件的字节码变换成哈夫曼码,使文件长度变短。
文件压缩器主要的功能是压缩和解压,分别设计压缩类和解压类实现压缩和解压功能。还有辅助功能的类,如结点类设计、叶结点类设计,用来构建哈夫曼树。为了方便压缩后的数据保存及解压,需要设计一个压缩结果类,用来保存压缩结果和哈夫曼码表,在解压过程中必须用压缩过程的哈夫曼码表才能做逆变换,把压缩数据还原成原来的数据。
3.1 结点类设计
Node类表示哈夫曼树的分支结点,类中成员变量包括结点类型、权重、左子结点和右子结点等记录结点的基本信息数据。Node类表述如下:
Leaf类是Node类的派生类,表示哈夫曼树的叶子结点,成员变量包括字节码及字节码的哈夫曼编码。Leaf类表述如下:
3.2 压缩结果类设计
Compressed Result类,用来保存压缩后的数据,保存原文件名供解压之后用,此外还要保存哈夫曼码表,在解压过程从哈夫曼码转换到字节码,必须使用压缩过程中的哈夫曼码表。Compressed Result类描述如下:
在具体实现过程中,采用了Java语言的对象序列化功能,使得保存压缩文件和加载压缩文件的过程变得简单,简化了实现过程。
3.3 压缩类设计
Compress类该类完成文件加载、统计字节频率、构建哈夫曼树、生成哈夫曼码和文件压缩等功能。Compress类描述如下:
函数built Hufftree()完成哈夫曼的构建,算法采用第2节中算法。具体实现中哈夫曼树用Java语言内置的优先队列Priority Queue类实现,队列中元素按权重自动排序,需要提供一个按权重比较大小的比较器,实现代码如下:
huff Tree=new Priority Queue
函数Huffman Coding(Node root,String huffcode)完成对字节码的哈夫曼编码,生成字节码映射到哈夫曼码表huff Codes,其中字节码是huff Codes的索引。由于Java语言byte类型范围是-128--127,byte类型的bytecode表示字节码用作索引时需要作适当的变换,映射成0-255。算法伪代码如下:
函数generate Compressed Data()生成压缩数据,把文件的字节码映射成哈夫曼码,算法流程如下:
(1)字节码转换为字符形式哈夫曼码。
(2)字符形式哈夫曼码转化为数字形式。
(3)把压缩数据和哈夫曼码表保存到comed Result。
3.4 解压类设计
Decompress类基本功能是加载文件生成comed Result,对comed Result压缩数据利用哈夫曼码表完成压缩数据的解压。Decompress类描述如下:
函数haffcode2Bytecode()完成对comed Result对象中的压缩数据进行解压,算法伪代码如下:
4 结语
采用数据压缩技术设计一种文件压缩器,压缩方法采用了基于统计模型的哈夫曼算法,用Java语言实现了该文件压缩器。在实现过程中用优先队列构建哈夫曼树,用对象序列化保存和加载压缩数据的方法简单易用,有一定的通用性。本文用哈夫曼算法实现的压缩器解压过程比压缩过程慢,哈夫曼算法的压缩方法属于无损压缩。
参考文献
[1]Huffman David A.A Method for the Construction of minimum-redundancy Codes.Proceeding of the Institute of Radio Engi-neers 40(1952):930-932.
[2]Cormack Gordorn V,Horspool R.Nigel.Algorithms for Adap-tive Huffman Codes.Information Procession Letters 18(1984):159-163.
[3]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,1997.
霍夫曼算法 第6篇
目前剧毒液体灌装工作多数由人工操作完成,其对人身危害很大。研发自动化液体灌装系统具有生产需要的迫切性。以计算机视觉技术实现桶口的识别与定位是本课题研究的关键技术之一。由于课题要求图像处理对桶口定位时间很短,传统的霍夫变换圆检测定位算法不能满足课题要求。提出了一种改进的霍夫变换圆检测算法,实验证明该算法对圆的检测及圆心的定位快速准确,满足了课题研究要求并具有了工程实用性。
1 基于视觉技术的自动化灌状系统
图1所示为一基于视觉技术的自动化灌装系统。其工作过程如下:储液桶被传送到灌装位置,光电传感器触发,使计算机获得储液桶到位信号,指令灌装位上方摄像机启动拍摄储液桶图像。图像被采集到图像采集卡,经过对数字图像的解码、A/D转换、PCI总线传输等,储液桶图像数据被传到计算机内存储。计算机中的图像处理系统对采集到的储液桶图像进行处理,通过一系列图像处理算法求取储液桶图像中圆形桶口中心的位置坐标,圆心位置坐标被传给驱动电机,由驱动电机驱动灌装执行器,准确快速运动到储液桶口上方,从而实现对储液桶的自动化加注。
2 霍夫变换
在基于视觉定位技术的储液桶灌装系统研究中,桶口的视觉识别及中心坐标的定位是难点与重点。在图像处理中,圆形边界的求取通常采用霍夫变换方法,经常被用来识别图像中的直线、曲线与圆[1]。
霍夫变换方法中常用到图像空间与参数空间,在图像空间中任意解析曲线可以用公式(1)表达。
式(1)中,a1,ax,,an是曲线特征参数。如果将公式(1)中的特征参数与变量x、y调换,则公式(1)等价于
式(2)说明,图像空间中同一解析曲线上的点通过式(2)变换,在参数空间中映射为一点,该点由特征参数a1,ax,,an确定。因此,通过判断参数空间中各参数点的积累值,可以实现对图像空间中解析曲线的描述。
设一个圆的方程为(x-a)2+(y-b)2=r2,令(xi,yi)(i=1,2,3n)为图像中满足圆周特性的点集合,那么图像空间集合中的点(xi,yi)在参数空间中方程为:
式(3)为一个三维锥面。对于图像空间中圆周上任意一点(xi,yi),均对应于参数空间中一个三维锥面;对于图像空间中满足圆周的全部点,则在参数空间与之对应的三维锥面就会组成一组圆锥面簇,如图2所示。
如果检测图像中圆的圆心坐标及半径(rmin≤r≤rmax),则需在参数空间建立一个三维累加器数组A(a,b,r),其中r为变量。根据公式(3),对图像圆周上每一个像素点计算(a,b,r),并对A(a,b,r)累加。通过计算A(a,b,r)数组中最大值Amax(a,b,r),则数组中的(a,b)就是图像空间中所求圆周的圆心坐标,r为半径。
3 霍夫变换的改进算法
传统的Hough变换有计算量大、占用内存大、提取的参数受参数空间的量化间隔制约。为了克服上述缺陷,不断有人提出Hough变换改进及快速算法,使计算速度和存储器的利用率有较大的提高[27]。由于本研究中视觉系统的特性及检测系统各部分配备关系制约,尚不能完全套用已有算法,故在借鉴相关算法的基础上,本文根据课题研究需要对传统的Hough变换圆检测算法进行了改进,其原理如下:
(1)在判断一个点是否为圆周上点时,要分析该点邻域内其它点与本点的相互位置,从而判断该点所在曲线的凸凹性。
(2)通过凸凹性可以判断圆心方向,只分析能在参数空间具有累加特性的曲线上点,这类点会位于待求的圆周上。
(3)为了提高运算速度,改进算法对图像中直线、孤立噪声和角点自动去除,不进行运算。
经过Canny边缘检测后,可以得到的单像素的边缘图像F(i,j):
以(2k+1)(2k+1)像素点建立搜索窗口,窗口坐标系如图3所示。该搜索窗口在边缘图像F(i,j)上移动,若某个圆周边缘上存在一系列像素值为1的点,如点A、O、B等,作经过AB两点的中垂线,其必在圆周半径方向上,通过判断点O与弦AB之间的位置关系,可以确定圆弧的圆心方向,从而可以确定参数空间内圆心数组累加方向,如图4所示。当搜索到多处满足条件的边缘点,其垂线的交点即为圆弧的中心点,如图5所示。
背景复杂的二值边缘图像可能含有大量直线段、角点和孤立噪声点,为了提高算法的运算速度,算法中将去除这些点,它们可能分布形式如图6所示。
图7为改进算法流程图。针对算法的快速性,传统算法与本文算法进行了比较,用于比较运算的原始图像如8a所示。对该图像进行图像分割并进行二值化得到图8b;利用Canny算子对图像进行边缘检测得到图8c;利用新的快速圆检测算法进行检测得到结果如图8d所示。表1为采用新算法与传统Hough算法对圆形检测的对比,可以看出,改进的Hough算法在提取圆心坐标时用的时间少,运算速度比传统Hough算法有大幅度提高。
4 霍夫变换改进算法在桶口检测中的应用
将霍夫变换改进算法应用到了储液桶口的识别与定位中,实验中对储液桶口随机位置提取了一系列图像,如图9所示。通过新算法的应用计算确定了桶口圆心坐标位置及所用时间,如表2所示。
通过表2可以看出,改进算法对储液桶口定位的图像识别时间均少于课题要求的0.5 s,满足研究需要。储液桶口自动定位系统检测运行界面如图10所示,储液桶口圆心图像坐标和世界坐标可实时显示。为便于调整,设置了手动功能,加注枪X轴、Y轴均可实现点动,达到了课题研究的各项指标要求。
5 结论
本文提出的霍夫变换改进算法充分利用了圆形边缘轮廓上点与其周围点的关系,通过圆弧中心线的方向判断出圆心在参数域的累加方向,从而求得在参数域累加最大值为圆的圆心点。由于该方法大幅度地拒绝了无意义的累加信息,从而极大程度地提高了霍夫变换算法的运算速度,与传统的霍夫变换算法相比,计算工作量小,运行速度快,所占计算机内存少。通过将该算法在储液桶口圆心的自动化识别与定位研究中的应用,验证了改进的霍夫变换算法的有效性与高效性,并且证明了该算法具有工程实用性。
参考文献
[1]章毓晋.图像处理和分析.北京:清华大学出版社,2001
[2]刘延杰,赖日飞,荣伟彬,等.基于改进随机Hough变换的快速中心检测方法.纳米技术与精密工程,2011;9(4):298—303
[3]秦开怀,王海颍,郑辑涛.一种基于Hough变换的圆和矩形的快速检测方法.中国图象图形学报,2010;15(1):109—115
[4] Chen A J,Dong G H.Efficient method for rapidly detecting circlesbased on edge-tracking.Second International Symposium on Computa-tional Intelligence and Design.Changsha,China,2009:402—405
[5]王磊,陈临强.基于弦中点Hough变换的同心圆检测方法.计算机应用,2009;29(7):1937—1939
[6] Zhang M Z,Cao H R.A new method of circle's center and radius de-tection in image processing.IEEE International Conference on Auto-mation and Logistics.Qingdao,China,2008:2239—2242
霍夫曼:讲故事的艺术 第7篇
《国际公关》:新媒体的普及改变了人们的交流方式。在新媒体环境下, 你认为应当如何提升企业信息传播的有效性?
霍夫曼:与十年前相比, 全球各地都经历了信息量的极大增长并且持续保持这样的增长势头, 在这样一个环境里, 仅仅是分享信息、教育并不能带来有效的沟通, 其中必须要有娱乐的元素, 这就让大家重新认识到了“讲故事的艺术”的重要。人们喜欢具有个性的企业, 这样的企业会让人们觉得在与实实在在的人对话, 而不是冰冷的机器。“讲故事的艺术”正是塑造企业个性有效的工具。讲故事的技巧应该被越来越多的应用到多种沟通方式当中, 包括新闻稿、企业博客, 甚至是致股东的信或者是公司主页的“关于我们”板块。
《国际公关》:对于公关人来说, 如何通过“讲故事”来实现与利益相关方的沟通?
霍夫曼:由于互联网将包括新闻在内的所有信息商品化, 媒体也必须娱乐化, 来提升信息价值。而公共关系需要与这种变化同步。这就意味着, 公关行业的专业人员要能够发掘出囊括故事要素的内容, 从而让记者来讲故事。我们坚决拥护将叙事艺术应用到所有的传播中去 (不仅限于与媒体的沟通) 。
