章浩1 刘一鸣2 刘泽远3
1湖北师范大学文理学院工学部435109 2华北理工大学管理学院063210 3华北理工大学建筑工程学院063210
摘要
借助中心极限定理，对传统的霍夫曼编码方法进行改进，提出一种基于－经典序列的霍夫曼编码方法，并通过对扩展信源和其－经典序列两种编码进行了比较，得出了改进后的编码具有更高的扩展编码效率的结论.最后将霍夫曼编码原理引入数字水印领域，提出一种基于图像特征的数字水印新算法，以降低数字水印算法复杂度。
关键词：中心极限定理；标准信息量；a－经典序列；霍夫曼编码；数字水印；
1.前言：传统的霍夫曼编码主要是针对离散信源单符号及其扩展信源符号序列的编码方法，随着扩展次数的增加，霍夫曼编码译码的复杂性急剧上升，而当信源扩展次数达到一定的数值后，信源序列的霍夫曼编码编码效率不再出现较为明显的提高。由于信源符号的概率分布不均匀，在进行N次扩展时，可能存在一些概率非常小的信源符号，表明其在实际通信过程中几乎不可能发生。对于不等长编码的霍夫曼编码，在一定的扩展次数N下，是否也可以给出相关划分标准，在控制出错率的条件下达到高效、快速、限失真的编码？这里借助了中心极限定理，提出了一种基于a－经典序列的限失真霍夫曼编码方法。
数字图像水印技术是目前检测数字图像可信度的有效方法之一。因其具有良好的隐蔽性、鲁棒性和可检测性，目前已经引起了研究者的广泛关注[1]。但数字图像水印技术较高的算法复杂度却成为制约其发展的不利因素。为了解决算法复杂度的问题，本文提出了一种基于图像特征和霍夫曼编码的数字水印新算法。由于霍夫曼编码本身就是基于最小遍历路径的，因此将霍夫曼编码引入数字水印领域中能大大减小水印算法的时间复杂度和空间复杂度。
2.研读霍夫曼编码理论
霍夫曼（Huffman）编码属于码词长度可变的编码类，是霍夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率。生成霍夫曼编码算法基于一种称为“编码树”（coding tree）的技术。算法步骤如下：
（1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序；
（2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和；
（3）重复第2步，直到形成一个符号为止（树），其概率最后等于1；
（4）从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。
霍夫曼编码是一种编码方式，是一种用于无损数据压缩的熵编码算法。霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度[2]。
.png)
.png)
4.实现a－经典序列霍夫曼编码
霍夫曼编码是在给定信源的信源空间和规定的符号集下，合理利用信源的统计特性，构造出单一可译的非延长码，并具有尽可能小的平均码长，从而使无失真信源编码具有较高的有效性，关于霍夫曼编码数据的压缩效果有人已经进行研究[3]．本文借助a－经典序列，将现有的无失真霍夫曼编码改进为限失真霍夫曼编码．计算比较信源编码特征量，分别为平均码长、编码效率、码方差以及编码时间：
给出了编码步骤，具体如下：
.png)
.png)
新水印技术具有复杂度低，容易实现性，隐蔽性、鲁棒性都较好的优点，本文浅略地介绍新水印技术，具体实现过程需要有很强的逻辑性推理和复杂的数学计算，具体手段请参考附件[4]和附件[5],本算法同样适用于图像的纹理特征、颜色特征、突变特征、关系特征等，具有很好的扩展性。将霍夫曼编码原理引入到数字水印领域，具有一定的创新性。
6.参考文献
[1]李国良,谭月辉,齐京礼,等.多小波域可恢复半脆弱数字水印算法[J].计算机工程,2015,37(17):84-86.
[2]姜丹,钱玉美.信息理论与编码［Ｍ］.中国科学技术大学出版社,1992.
[3]时国平.关于霍夫曼编码数据压缩效果[J].池州学院学报,2018,22(5):46-48.
[4]李亚琴,李金祥,梁颖红.基于图像特征和霍夫曼编码的图像水印算法[J].计算机应用与软件,2018,(9):128-130,140.
[5]陈力,艾勇胜.基于DWT的数字水印改进算法[J].信息系统工程，2017(9):18-20.
[6]沈世镒.一般离散序列模型信源编码定理[J].数学年刊A辑（中文版）,2019(2):65-76.