ABSTRACT

This paper presents an information hiding algorithm based on GIF image. Firstly, the algorithm divides the color index into the effective color index and the redundant color index according to the frequency of each color index in the image data. Secondly, on the basis of the color difference between the palette color index, the effective color indexes are divided into several groups to get the similar color index subsets. Finally, the redundant color index in the palette will be assigned to each similar color index subset according to certain rules. When embedding information, the secret file is grouped and converted into M-ary code stream, and then the code stream data is embedded into the image data by the method of grouping and Mixed M-ary. The experimental results show that compared with the existing methods, the proposed algorithm not only improves the steganographic capacity, but also has a great improvement in security because of the fewer carrier pixels needed to embed the information.

Keywords:Effective Color Index, Redundant Color Index, Similar Color Index Subsets, Mixed M-ary Embedding

一种基于调色板冗余颜色索引匹配的混合进制信息隐藏算法

马春波，张涛

桂林电子科技大学信息与通信学院，广西 桂林

收稿日期：2017年6月4日；录用日期：2017年6月20日；发布日期：2017年6月23日

摘 要

本文提出了一种基于GIF图像的信息隐藏算法。该算法先根据各颜色索引在图像数据中的频次，将颜色索引分为有效颜色索引与冗余颜色索引；其次根据调色板颜色索引之间的色差，先对调色板中有效颜色索引分组，得到相似颜色索引子集，再将调色板中的冗余颜色索引以一定的规则分配到各相近颜色索引子集中。隐写时，先对秘密文件进行分组及混合多进制转换，继而采取分组混合多进制的方式嵌入到图像数据中。实验表明，相比现有方法，该算法不但提高了隐写容量，且由于嵌入信息时需要的载体像素点更少，在安全性上反而有了巨大的提升。

关键词 :有效颜色索引，冗余颜色索引，相似颜色索引子集，混合多进制嵌入

Copyright © 2017 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

信息隐藏是一种隐蔽的通信方式，其目的是发送方将秘密文件嵌入载体后，将载体文件传送给接收方而不引起第三方的注意。这种通信方式自古以来经过了漫长的演变与发展，从初期的隐写墨水、藏头诗等到数字编码，都是较为浅显的信息隐藏方式。直至20世纪后半期，互联网的出现与极速发展，为信息隐藏技术的发展提供了天然的契机，基于各种载体的信息隐藏算法相继被提出。

本文主要研究了以GIF图片为载体的信息隐藏算法，并在此基础上提出了一种新的基于调色板冗余颜色索引匹配的混合进制嵌入算法。新算法先根据颜色相近原则对调色板中有效索引分组，并将冗余颜色索引逐个匹配到各组颜色索引子集中，继而完成对整个调色板颜色索引的分组。嵌入信息时，先根据分组结果对待嵌入秘密信息进行分组及多进制转换，继而以多进制嵌入的方式分组将秘密信息分别嵌入载体图像数据中。与现有算法相比，新算法充分利用了调色板中的冗余索引，有效地提高了图像的嵌入容量。

2. 研究现状

根据现有的成果，基于GIF图像的信息隐藏算法，大致可以划分为两大类：基于图像调色板的隐写 [1] 、基于图像内容的隐写 [2] - [12] 。其中，基于调色板的隐写主要是通过对调色板进行重排序来达到隐写的目的，该类算法是一种无损信息隐藏算法，但其容量受调色板颜色索引数目所限，容量相当有限。此外，一旦隐秘图像的调色板顺序发生改变，则会删除嵌入在调色板中的信息，鲁棒性差。而基于图像内容的隐写，主要是通过修改图像数据中的索引值来达到嵌入信息的目的，该类算法的隐写容量不受调色板索引数目的限制，只与算法本身和图像尺寸相关，具有隐写容量大、安全性高、鲁棒性强等优点。但该类算法由于改变了图像的图像数据，会给图像带来一定程度上的失真，是一类有损的信息隐藏算法。该类型算法是目前GIF图像信息隐藏技术研究的热点，也是当前GIF图像信息隐藏技术研究的主流方向。比较经典的算法主要有EzStego算法 [2] 、OPA算法 [3] 、基于分量和隐写算法 [4] 、MBA算法 [9] 、MCMB算法 [10] 等。

其中，EzStego算法 [2] 主要是通过对调色板颜色按亮度依次排序，并以各颜色索引序号的LSB来承载相应的信息位；OPA [3] 则是以欧氏距离对调色板中颜色索引两两分组，每组中的两个颜色索引分别承载信息位0和1。基于分量和的算法在OPA算法上做了进一步的改进，该算法以三颜色分量之和的LSB来承载信息，消除了单一颜色分量对隐写安全性带来的影响。EzStego、OPA算法及基于分量和的隐写算法等在分组、排序时各组内索引颜色差值较小，安全性较高；但在嵌入信息时仅在一个像素点上嵌入1比特信息，嵌入容量较小。

为了改进这一缺陷，有学者提出了在一个像素点上嵌入多比特信息的相关算法，比较著名的有MBA算法 [9] 、MCMB算法 [10] 等。其中前者是在一个颜色分量上嵌入多比特信息，而后者是在三个颜色分量上各自嵌入一比特信息。对比EzStego、OPA算法，其隐写容量有了质的提升；但无论是MCMB还是MBA，由于其本质均是在一个像素点上进行了多次独立的单比特嵌入，为了保证嵌入的顺利进行，选定的色差阈值往往较大，相应的嵌入信息后生成的隐秘图像失真率较高，隐写安全性较低。

基于上文的介绍，若将隐写算法进一步详细分类，则以EzStego、OPA等为代表的第一类算法虽然具有较高的安全性，但嵌入容量小；而以MCMB、MBA等为代表的第二类隐写算法，虽然在安全性上有所降低，但在嵌入容量上却有了质的提升。由此可见，进一步研究以GIF图像为载体的信息隐藏算法以获取更大的嵌入容量及更好的安全性，具有十分重要的现实意义。

3. 基于调色板冗余颜色索引匹配的混合进制信息隐藏算法

本文算法是一种混合多进制的信息隐藏算法，其核心是先根据颜色相似原则将调色板有效颜色索引分为若干组相似颜色索引子集S_i，再将冗余颜色索引以嵌入容量增量最大的原则，将各冗余颜色索引逐个分配到S_i中，并修改冗余颜色索引的颜色分量值。在嵌入信息时，先根据调色板索引分组内的颜色索引数目将秘密信息文件进行混合多进制转换，并采取分组嵌入的方式，将文件逐组嵌入到每组颜色索引图像数据中。

3.1. 调色板有效颜色索引分组

本文对调色板颜色索引分组的依据是根据调色板索引颜色间的色差，具体表示为颜色的欧式距离差DL式(3-1)与亮度差DY式(3-2)，其中以亮度距离为主，欧氏距离为辅。由式(3-2)可知，在计算两颜色间的亮度距离时，各颜色分量分别乘上了一个不同的权值系数，必然会使得色差较大的颜色具有相似的亮度，使得两者间的亮度距离极小。为了解决这一问题，本文在衡量色差时，还引入了欧式距离作为亮度距离的补充约束条件，即只有当两颜色间亮度距离较小且欧氏距离满足条件的情况下，才符合分组条件。在判定索引颜色相似度时，对于各索引之间的DY与DL，分别设立了一个亮度距离阈值Dd-Y与欧式距离阈值Dd-L，若DY[i][j] ≤ Dd-Y且DL[i][j] ≤ Dd-L，则判定索引P_i与P_j间颜色相似度较高，可以视为一组相似颜色索引。根据人眼视觉特性，当被观察对象亮度Y发生改变时，人眼并不能立即察觉到，只有当亮度变化到一定值Y + ΔY时，人眼才会察觉到亮度的变化。由韦伯定律可知，在常用的背景亮度变化范围内，对比灵敏度ΔY /Y ≈ 0.22，且变化较小，基于此，本文选定亮度距离阈值Dd-Y = 0.2 * DY。欧氏距离作为亮度距离的补充约束条件，原则上取值越小越精确，但综合考虑嵌入容量与嵌入安全性，将其取值设为亮度距离阈值的一半，即Dd-L = 0.1 * DL。

(3-1)

(3-2)

在分组前，先统计调色板Map (256*3)中各颜色索引在图像数据中的频次F_i，则F_i = 0的颜色索引为冗余颜色索引，否则为有效颜色索引。取出Map中的有效颜色索引，计为M个，存入Map₀ (M*3)。对调色板Map₀按颜色向量P_i (R_i, G_i, B_i)的模(式3-3)从小到大的顺序依次排序，得到Map₁ (M*4)。局部调整Map₁中颜色索引顺序，得到Map₂ (M*4)。其中，Map₁和Map₂中第0列存储该颜色索引在原始调色板Map的序号，第1至3列则存储该索引的颜色分量值。

(3-3)

排序后，根据Map₂中各颜色索引间的亮度距离与欧氏距离，构建调色板有效颜色索引相似颜色索引矩阵DD-U (M*M)。当且仅当DY[i][j] ≤ Dd-Y且DL[i][j] ≤ Dd-L时，DD − U[i][j] = 1，表示两索引颜色间色差较小；否则DD − U[i][j] = 0，表示两索引色差较大。显而易见的是，颜色索引替换矩阵DD-U中主对角线上的元素的值均为1，且矩阵为对称矩阵，即DD − U[i][i] = 1，且DD − U[i][j] = DD − U[j][i]。分组时，以矩阵DD-U中第i − 1行、第i列元素DD-U[i − 1][i]的值为标准对颜色索引分组分组，当DD − U[i − 1][i] = 0时，则前i个颜色索引即为一组相似颜色索引。

综上所述，调色板有效颜色索引分组详细步骤如下所示：

1) 取出原始调色板Map中的有效颜色索引并存入Map₀，根据各索引颜色向量额模按从小到大的顺序依次排序，存入Map₁。

2) 从Map1中模最小的索引开始，遍历Map₁，将满足条件(DL < Dd_L)的颜色索引按欧氏距离DL从小大大的顺序依次排序，存入Map₂；

3) 对调色板Map₁中剩下的颜色索引，按步骤2)的方式继续排序，直至结束。

(4) 根据Map₂中各索引颜色间的欧式距离与亮度距离，构建相似颜色索引矩阵DD-U;

5) 从i = 0开始，当DD−U[i₁ − 1][i₁] = 0时，则第零组分组结束，组内的索引为Map (Map₂[0][0]), Map (Map₂[1][0]), ∙∙∙, Map (Map₂[i₁ − 1][0])；

6) 接下来从i₁开始，当DD−U[i₂ − 1][i₂] = 0时，则第一次分组结束，组内的索引为：Map (Map₂[i₁][0]), Map (Map₂[i₁ + 1][0]), ∙∙∙, Map (Map₂[i₂ − 1][0])；

7) 重复步骤6)，直至i_z = M，调色板有效颜色索引分组结束。

3.2. 调色板冗余颜色索引分配

由上文可知，调色板有效颜色索引共被分为z组，每一组内含有的颜色索引数目k_i分别为：i₁, (i₂ − i₁), (i₃ − i₂), ∙∙∙, (i_z − i_{(z − 1)})。对于分组后的调色板有效颜色索引，我们以索引子集S_i中的索引数目k_i为进制数，假定用k_i进制表示0xFF所需的最短码长为，则该组索引的隐写容量(以字节为单位) Num_i为：

(3-4)

其中，N_i为每组索引在图像数据中出现的总频次；floor为向下取整函数，作用是向下舍入，即取不大于的最大整数；

由上式(3-4)可知，每组颜色索引子集的嵌入容量Num_i仅与该组索引的总频次N_i及码长有关。组内颜色索引数目越多，即k_i越大，则该组索引的总频次N_i越大，且越小，故该组隐写容量Num_i越大。为每组颜色索引子集分配冗余颜色索引，即是增大每组颜色索引子集中的颜色索引数目k_i，此时，组内颜色索引的总频次N_i保持不变，而该组的最短码长变短，因此该组隐写容量Num_i会变大。假定将一个冗余颜色索引分配给颜色索引子集S_i，则第i组索引的隐写容量增量ΔC_i如下式所示：

(3-5)

当ΔC_i最大时，意味着将一个冗余颜色索引分到第i组，增加的嵌入容量最大。相应地，对于所有的冗余颜色索引，若均以这种方式进行分配，则图片总的隐写容量达到最大值。基于这一原理，本文设计了一种冗余颜色索引最优分配方案。该方案以单个冗余颜色索引对嵌入容量的增量为原则，将各冗余颜色索引依次分配到各组颜色索引子集中，使图片嵌入容量达到最大值。具体步骤如下所示：

1) 对于有效颜色索引，根据分组后的结果，计算每组增加一个索引时，该组增加的嵌入容量ΔC_i；

2) 比较各组的嵌入容量增量ΔC_i，若各组的ΔC_i相等，则将一个冗余索引Q_x分配给N_i最大的一组；否则找出ΔC_i最大的一组，并将一个冗余索引Q_x分配到该组；

3) 修改该冗余索引Q_x的颜色分量值。将Q_x的R、G、B修改为该组索引中频次最高的索引P_i的R、G、B值，并对某个颜色分量值加1。

4) 重新计算各组的容量增量ΔC_i，重复步骤2) 3)，直至冗余索引分配完毕。

3.3. 信息嵌入

分配并修改后的冗余颜色索引与有效颜色索引则构成了隐秘图像的调色板，假定SS_i为分配好冗余颜色索引后的颜色索引子集，则SS_i即为隐秘图像调色板相近颜色索引子集。且SS_i中颜色索引的数目kk_i为S_i中有效颜色索引数目k_i与分配的冗余颜色索引数目q_i之和。此时，每组的隐写容量Num_i为：

(3-6)

在嵌入信息前，先为子集S_i中的k_i个颜色索引分别分配一个不同的P值0, 1, 2, 3, ∙∙∙, (kk_i − 1)，以表征k_i进制的不同信息位。然后根据根据颜色索引与P值的对应关系，构建P值与索引值的对应关系表，其中，每一行即为一组颜色索引子集中的各颜色索引，每一列则为各组中P值相同的颜色索引。此外，为了保证接收方能准确恢复分组，发送方在嵌入信息时，还需要标出冗余索引的位置，即先将冗余索引标号顺序嵌入到图像数据中；再将秘密信息以分组嵌入的方式嵌入进剩余图像数据中。具体步骤如下所示:

1) 将冗余索引依次转换为二进制，以OPA算法嵌入图像数据的前半段。

a) 以各颜色向量的模对调色板颜色索引排序，并从模最小的颜色索引开始，找出与其欧氏距离最小的颜色索引，则这两个颜色索引即为一组，且分别表示信息位0和1。

b) 在调色板剩余颜色索引中，取出模最小的颜色索引及与之欧氏距离最小的颜色索引并分为一组，同样的组内的两个颜色索引分别表示信息位0和1，直至调色板颜色索引分组结束。

c) 将冗余索引信息转换成二进制码流，若当前信息比特与像素点颜色索引值对应的信息位相同，则保持不变并执行下一个信息比特的嵌入；否则将其修改为组内另一个颜色索引值。

2) 从第零组开始，kk₀ > 1，则先从剩余图像数据中依次取出所有属于第0组的索引，总数为N_i，但只有前Len[kk₀]*Num₀个索引承载信息。

3) 取出Num₀字节文件并转换成kk₀进制的码流，码流长度为Len[kk₀]*Num₀，并按照顺序嵌入的方式将其嵌入第0组图像数据中。

4) 嵌入时，对照信息与索引的对应关系表，若当前索引承载的信息位与当前文件码字信息相同，则不做修改，并继续下一次嵌入；否则，将当前索引替换成当前文件码字信息在表中与第零组相对应的索引。

5) 重复步骤2)、3)、4)，直至所有秘密文件全部嵌入图像数据中。

6) 恢复图像数据。将按组取出的索引系数按原位置插入图像数据矩阵。

7) 压缩图像数据，生成隐秘图像。

3.4. 信息提取

提取信息步骤与嵌入类似，都要经过有效颜色索引分组，冗余颜色索引分配以获取隐秘图像调色板相近颜色索引子集SS_i。不同的是，隐秘图像调色板中的颜色索引无法直接区分，必须从前半段隐秘图像数据中提取冗余颜色索引信息以获取有效颜色索引并分组。具体步骤如下所示：

1) 先以OPA算法提取前半段图像数据中嵌入的冗余颜色索引信息，并从调色板中取出剩余颜色索引，则这些颜色索引即为原始图像中的有效颜色索引；

2) 以同样的分组算法，对原始图像中的调色板有效颜色索引进行分组，得到有效颜色索引的相近颜色索引子集S_i；

3) 逐个将冗余索引与每个有效颜色索引对比，并将该冗余颜色索引分配到与该冗余索引颜色最接近的颜色索引所在子集S_i中，得到隐秘图像调色板相近颜色索引子集SS_i；

4) 为SS_i中kk_i个颜色索引分配P值，构建颜色索引与信息位的对应关系表，并根据隐秘图像调色板分组结果SS_i从隐秘图像中分组取出图像数据；

5) 据信息位与颜色索引值的对应关系表，将每组图像数据分别译成相应的多进制码流并转换至十进制，即可完成秘密信息的提取。

4. 实验结果分析

在评估本文算法性能时，本文分别从嵌入容量及安全性等方面来评估算法性能。首先，就嵌入容量而言，该算法由于提高了相似颜色索引及冗余颜色索引的利用效率，在一个像素点上得以嵌入更多比特的信息，整体嵌入容量有了巨大的提升。表1列举了几幅不同尺寸的GIF图片在各算法下的嵌入容量。

需要注意的是，在三类算法的对比中，第一类算法(OPA)与本文算法选用相同的欧式距离阈值和亮度距离阈值，而第二类算法(MBA)选用的阈值则大约是第一类算法的2.5倍。其原因在于第二类算法对替换颜色索引的要求远比第一类算法以及本文算法的要求高，在最大嵌入容量嵌入时，只能通过不断扩大阈值范围以搜索符合条件的替换颜色索引。

其次，评判算法的安全性时，本文主要以隐秘图像相比原始图像的的信噪比SNR式(4-1)和峰值信噪比PSNR式(4-2)等来衡量隐秘图像的失真率。若将嵌入的信息作为噪声，则SNR表示原始图像功率与噪声功率之比，SNR越大，则说明隐秘图像相比原始图像的平均失真越小，隐写的安全性越高；类似的，PSNR表示隐秘图像中相比原始图像失真最大的像素点处的SNR，PSNR越大，表明隐秘图像对比原始图像的峰值噪点越弱，即隐秘图像相比原始图像的最大失真越小。

(4-1)

表1. 隐写容量对比分析

表2. 安全性对比分析

(4-2)

其中，p_h[i][j]为隐秘图像第i行第j列像素点的颜色索引，则为隐秘图像中第i行第j列的像素索引的第m个颜色分量值；则为原始图像中第i行第j列的像素索引的第m个颜色分量值。在讨论算法安全性时，本文算法仅与第一类算法作比较，原因是第一类算法相比第二类算法，在安全性上具有明显的优势。表2列举了在尺寸为227 * 240的GIF图片上嵌入不同大小文件时本文算法与OPA算法的SNR和PSNR。

由表2可知，就安全性而言，在嵌入同样的秘密文件时，由于所需的载体像素点更少，即嵌入信息时对图像的改动更小，使得生成的隐秘图像具有更高的信噪比，失真率更低，隐写安全性大为增强。

综上所述，本文算法不仅在现有算法的基础上进一步提高了最大嵌入容量，同时还在隐写安全性上取得了较大的突破。换言之，本文算法不但兼具了两类算法的优点，还在此基础上进一步提高了算法的性能。

5. 结论

论文在研究现有算法的基础上，提出了一种基于GIF图像调色板冗余颜色索引匹配的混合进制嵌入算法。该算法旨在先对调色板有效颜色索引进行合理分组的基础上，再将调色板中冗余颜色索引依次分到各组有效颜色索引子集中。嵌入信息时，先在图像前半段数据中以OPA算法嵌入冗余索引相关信息，再在后半段图像数据中以混合多进制嵌入的方式将秘密信息分组嵌入到图像数据中。与现有算法相比，本文算法具有更高的嵌入容量及更好的安全性，是一种安全高效的嵌入算法。

资助信息

受广西精密导航技术与应用重点实验室资助(DH201503)。

文章引用

马春波,张 涛. 一种基于调色板冗余颜色索引匹配的混合进制信息隐藏算法
A Mixed M-Ary Information Hiding Algorithm Based on Palette Redundant Color Index Matching[J]. 计算机科学与应用, 2017, 07(06): 572-579. http://dx.doi.org/10.12677/CSA.2017.76068

参考文献 (References)