混合进制嵌入的调色板图像无损信息隐藏

吕金鹏，梁海华，张新鹏

上海大学通信与信息工程学院，上海200444

混合进制嵌入的调色板图像无损信息隐藏

吕金鹏，梁海华，张新鹏

上海大学通信与信息工程学院，上海200444

提出了一种基于混合进制的调色板图像无损信息隐藏方法.首先根据索引分布，区分有效索引与冗余索引.在调色板中分配若干冗余索引指向同一有效索引的颜色，使相同颜色的不同索引值承载不同的秘密信息，用于无损信息隐藏.用动态规划方法产生最大嵌入量下的冗余索引分配方案.不同颜色承载的秘密信息为不同进制秘密数字.该方法中嵌入机制并不影响原始图像内容.实验表明，与以往方法相比，该方法提高了数据嵌入量，医学图像尤为显著.

无损信息隐藏；调色板图像；混合进制；动态规划

信息隐藏是指在不过分影响数字载体的前提下，将秘密信息隐藏在数字媒体中，以实现版权保护、内容认证和数字信息安全传递等［1-5］.如果接收方在提取嵌入信息的同时，还可以毫无损伤地恢复原始载体，这种技术被称为可逆信息隐藏［6］.目前，已经有许多学者提出了可逆信息隐藏方法，如差值扩展［7］、直方图平移［8］、无损压缩［9］等.这些方法在嵌入过程中允许引入失真，但这种失真是可逆的，在提取信息时可以将原始图像恢复.研究者希望减少嵌入信息后载体图像的失真，以避免由失真引起观察者对图像内容的误解，因此需要一种嵌入信息后载体无失真的技术，即无损信息隐藏（lossless data hiding）.

调色板图像在互联网上很常见，也常应用于医学图像，如X射线图像以及磁共振成像（magnetic resonance imaging，MRI），可以作为信息隐藏的载体.它可以用不多于256种颜色来表现可以接受的视觉效果.通常，调色板图像文件分为两部分：前一部分是调色板，为每一个颜色分别定义一个索引值；后一部分为像素矩阵，给出每一个像素的索引值.对于一幅256种颜色的调色板图像，一个索引值只需8比特，图像所需的储存空间便大大减少［10］.目前，针对调色板图像的无损信息隐藏方法并不多.文献［11］提出一种通过改变调色板中索引值与真实颜色的对应关系进行信息隐藏的方法，对调色板的颜色顺序进行重排以嵌入信息，但调色板数据的任意排列不影响图像内容，只要像素矩阵的索引值能有相应变化即可.文献［12］通过利用调色板图像中未用的保留字隐藏秘密的信息，嵌入信息的图像无失真，但嵌入量十分有限.文献［13］首先对调色板预处理，使2L-1个冗余索引值对应同一种颜色，其中L∈（0，8）.修改一个像素的索引值可嵌入L比特秘密数据.由于修改前后索引值都指向同一个颜色，载体图像在嵌入过程中无失真，此时每幅图像的参数L通过遍历（0，8）后计算最大嵌入量得到.文献［14］在文献［13］的基础上进行改进，由于每种颜色的参数L不同，需要遍历每种颜色L的取值，通过计算嵌入量得到最佳冗余分配方案，这样在保证无失真的同时增大了图像的嵌入量.

虽然文献［14］改进了冗余索引的利用效率，但是冗余空间并未得到完全利用.为提高嵌入量，本文改进了文献［14］的方法，提出了一种基于混合进制的无损信息隐藏方法.首先对调色板进行预处理，不同于文献［14］，分配给每一个颜色的冗余索引数目不局限于2L-1，为任意正整数.本文通过动态规划的方法寻找最大嵌入量下的冗余索引分配方案，在信息嵌入过程中只需将秘密信息进行进制转换，根据转换后的混合进制数字序列修改像素的索引值.实验证明，嵌入信息的图像相对于原始图像没有任何失真，且相较于文献［14］的方法，本文方法提高了嵌入量，其中医学图像尤为显著.

1　无损信息隐藏方案

调色板共有256种索引，但真实图像通常并未使用调色板中的所有索引，而是存在冗余索引，可用于信息隐藏.在调色板中，分配若干冗余索引指向同一有效索引的颜色，使相同颜色的不同索引值承载不同秘密信息.通过动态规划来确定最佳的冗余索引分配方案，嵌入时将秘密信息进制转换，在像素矩阵中根据转换后的混合进制数字序列修改像素的索引值；提取时由调色板恢复出索引分配方案，在像素矩阵中根据像素索引值提取其承载的混合进制数字序列，转为二进制即为秘密信息.

1.1冗余索引分配

设图像中索引i对应的颜色Di=（ri，gi，bi），Di为三维向量，其中ri、gi、bi分别为该颜色的红色分量、绿色分量、蓝色分量.根据各颜色在图像中像素数目对256种颜色降序排列，其对应的索引值修改为0，1，···，255.排序后颜色Di在图像中像素数目为H［i］，其中H［i］=0的索引值为冗余索引，其总数为N.

设（i，Di）为有效索引值与颜色对，在调色板中修改Si个冗余索引值f，f+1，f+2，···，f+Si-1指向颜色Di，其中Si∈［0，N］.此时颜色Di对应Si+1个索引值，即Di对应的索引值有Si+1种可能性.若每个索引值都携带一个隐藏码K，那么一个颜色为Di的像素可以嵌入lb（Si+1）比特信息.假设像素矩阵为I，一个颜色为Di的像素的坐标为（x，y），隐藏码与索引值对应关系为

在像素矩阵中，根据秘密信息修改索引值可以实现信息隐藏.因为修改前后索引值指向的颜色仍为Di，所以载体图像无失真.值得注意的是，式（1）隐藏码不局限于二进制.若秘密信息为二元数字序列，则需秘密信息转为Si+1进制数字序列.合理分配每个颜色对应冗余索引的数目，可以使嵌入量达到最大.由式（1）可知，假设一个有效索引颜色对应Si个冗余索引，那么图像中该颜色可嵌入（Si+1）H［i］比特信息.N个冗余索引分配方案如图1所示.显然S0+S1+···+SN-1=N，此时调色板图像的嵌入量C为

对于一幅图像，H［0］，H［1］，···，H［255］和N均为定值，图像最大嵌入量是关于变量S0～SN-1非线性约束的组合优化问题.优化的标准式如下：

式中，h为S0～SN-1取值的第h种情况，为C（i，h）取最大值时Si的取值.对于上述问题，若通过遍历，则计算量过大.本文采用动态规划算法（dynamic programming，DP）来减少时间复杂度.对式（3）的求解步骤如下：

步骤1设M（u，v）表示u个冗余索引最多分为v组时的最大嵌入量.每组依次为指向颜色D0，D1，···，Dv-1的冗余索引值，设每组的数目依次为S0，S1，···，Sv-1.

步骤2当v=1时，u个冗余索引值都分配给颜色D0

当v＞1时，由式（2）可知，已知H［0］≥H［1］≥···≥H［255］，最大嵌入量下的S0～ Sv-1必须满足S0≥S1···≥Sv-1，那么最后一组冗余索引数目Sv-1的取值范围为，遍历Sv-1的取值，则有

步骤3根据递推关系，迭代求出N个冗余索引最多分为N组的最大嵌量M（N，N）以及此时S0～SN-1的值.

图1　冗余索引分配示意图Figure 1 Distribution solutions of redundant indices

1.2嵌入与提取过程

嵌入与提取过程的步骤如下：

步骤1修改调色板.由原始图像索引分布并根据1.1可得最佳冗余索引分配方案S0～SN-1，按照该方案在调色板中修改冗余索引的颜色为其对应有效索引的颜色.

步骤2对秘密信息进行预处理.如图2所示，假设加密后待嵌入二进制信息S的数据总量为Payload，将S切割为N组，第i+1组的数据量Pi，其中i∈［0，N-1］，Pi对应图像中颜色Di嵌入信息量，Pi最多为「lb（Si+1）H［i］」比特.然后将每组大小为Pi的数据流分别转换为S0+1，S1+1，···，SN-1+1进制秘密数字序列.

步骤3在像素矩阵中嵌入信息.依次读取信息量大小为Pi的Si+1进制数字序列，设像素矩阵中颜色为Di的像素集合为Ui，根据式（1）索引值对应的隐藏码修改Ui的索引值.对N组数字序列重复上述操作后，已将秘密信息完全嵌入.

步骤4在接收端提取信息.由嵌入图像的调色板可知冗余索引的分配方案，即S0～ SN-1.设颜色Di对应冗余索引值为.扫描像素矩阵中索引值为， ···，根据式（1）提取Si+1进制隐藏数据，并转化为二进制序列，对颜色D0，D1，···， DN-1执行上述操作，直到秘密信息完全提取为止.

图2　秘密信息切割示意图Figure 2 Segments of secret data

2　仿真与对比分析

本文从嵌入率来评估算法性能.为验证本文算法，采用12幅256色图像作为测试载体，如图3所示.

设图像大小为X×Y，嵌入率e为平均每个像素可以承载的秘密信息量，则其表达式为

图3　测试图像Figure 3 Test images

实验用占图像50%的颜色种类数目T来表示图像索引颜色分布的复杂程度.在图3中，图像（a）～（e）为医学图像，T集中在［1，10］，纹理较为简单；图像（f）～（h）为卡通图像，T集中在（10，20］，纹理较复杂；图像（i）～（l）为自然图像，T集中在（20，+∞），纹理最复杂.本文对12幅图像进行信息嵌入，所得嵌入率与文献［14］的对比如表1所示.

从表1中可以看出，图像的嵌入率与图像内容具有很大的相关性.对于实验中的3类图像，医学图像表现最好，图像（c）的嵌入率可达4.723 bpp（bpp为平均每像素嵌入的比特数）.因为医学图像冗余索引较多，且颜色分布较集中，所以嵌入量就较多.

文献［14］在冗余索引分配时，2L-1个冗余索引对应同一有效索引的颜色，嵌入信息为二进制.由于混合进制充分利用了冗余索引，针对第1类医学图像，嵌入率较文献［14］提高较多，最多可提高36.4%；对第3类图像及第2类部分图像，其颜色分布平均，较文献［14］只提高1%～4.85%，可见本方法在医学图像上的性能更显著.

表2给出了文献［14］与本文方法的冗余索引分配方案.MRI图像为简单纹理图像，冗余索引数目为6，经排序后对应的索引值为250～255.排序后H［0］～H［5］为［90 156，2 339，1 447，1 440，1 205，1 108］.文献［14］冗余索引分配方案如表3所示.索引值［0，250，251，252］对应颜色为D0，索引值［1，253］对应颜色为D1，索引值［2，254］对应颜色为D2，索引值［3，255］对应颜色为D3.本方法分配给每个颜色的冗余索引数目为任何正整数，由动态规划得到的最佳分配方案可知，索引值［0，250，251，252，253，254，255］均对应D0.混合进制嵌入方法更高效地利用了冗余索引，故本文提出方法的嵌入量大于文献［14］.

表1　本文方法与文献［14］方法所得嵌入率对比Table 1 Embedding rate comparison of the proposed method and reference［14］

针对复杂纹理图像，如Flower图像和Lake图像，文献［14］与本文方法的冗余索引分配方案如表2所示.相较于二进制信息嵌入方法［14］，本文提出的混合进制嵌入方法更高效地利用了冗余索引，嵌入量均有所提高.

表2　冗余索引分配方案对比Table 2 Comparison of distribution solutions of redundant indices

3　结语

本文提出了一种基于混合进制的调色板图像无损信息隐藏方法.分配若干冗余索引指向同一有效索引的颜色，使相同颜色的不同索引值承载不同秘密信息.在嵌入过程中，对加密后的秘密信息进制进行转换，根据转换后的混合进制数字序列修改像素的索引值.实验结果表明，同文献［14］相比，混合进制嵌入方法更高效地利用了冗余索引，提高了嵌入量，对于医学图像尤为显著.在实际应用中，更高的嵌入量给隐蔽通信带来极大的便利，所以本文的研究很有意义.

［1］王朔中，张新鹏，张开文.数字密写和密写分析：互联网时代的信息战技术［M］.北京：清华大学出版社有限公司，2005.

［2］CHAN C K，CHENG L M.Hiding data in images by simple LSB substitution［J］.Pattern Recognition，2004，37（3）：469-474.

［3］SALLEE P.Model-based steganography［M］//Digital Watermarking.Berlin Heidelberg：Springer，2004：154-167.

［4］ZHANG X，WANG S.Efficient steganographic embedding by exploiting modification direction［J］. IEEE on Communications Letters，2006，10（11）：781-783.

［5］PENG F，LI X，YANG B.Adaptive reversible data hiding scheme based on integer transform［J］. Signal Processing，2012，92（1）：54-62.

［6］ZHANG X.Reversible data hiding in encrypted image［J］.Signal Processing Letters，2011，18（4）：255-258.

［7］TIAN J.Reversible data embedding using a difference expansion［J］.IEEE Transactions on Circuits and Systems for Video Technology，2003，13（8）：890-896.

［8］NI Z，SHI Y Q，ANSARI N，SU W.Reversible data hiding［J］.IEEE Transactions on Circuits and Systems for Video Technology，2006，16（3）：354-362.

［9］CELIL M U，SHARMA G，TEKALp A M，SABER E.Lossless generalized-LSB data embedding［J］. IEEE Transactions on Image Processing，2005，14（2）：253-266.

［10］张新鹏，王朔中.对OPA密写的检测和增强安全性的调色板图像密写方案［J］.电子学报，2004，（10）：1702-1705. ZHANG X P，WANG S Z.Detection of OPA stego-data and secure steganography in palette images［J］.Acta Electronica Sinica，2004（10）：1702-1705.（in Chinese）

［11］KWAN M.The gifshuffie homepage［EB/OL］.http：//www.darkside.com.au/gifshuffie/，2003

［12］BANDYOpADHYAY S K，MAITRA I K，BHATTACHARYYA D，TAI-HOON K.Reserved fields of palette for data hiding in steganography［C］//International Conference on Computational Intelligence and Communication Networks（CICN），2010 International Conference，2010：398-402.

［13］LIU H M，ZHANG Z F，HUANG J W，HUANG X L，SHI Y Q.A high capacity distortion-free data hiding algorithm for palette image［C］//IEEE International Symposium on Circuits and Systems（ISCAS），2003：916-919.

［14］SALEHA N A，BOGHDAYA H N，SHAHEENB S I，DARWISHB A M.High capacity lossless data embedding technique for palette images based on histogram analysis［J］.Digital Signal Processing，2010，20（6）：1629-1636.

（编辑：秦巍）

Lossless Data Hiding in Palette Images Based on Mix-ary Codes

LÜ Jin-peng，LIANG Hai-hua，ZHANG Xin-peng
School of Communication and Information Engineering，Shanghai University，Shanghai 200444，China

This paper proposes a lossless data hiding method in palette images based on mix-ary codes.According to the distributionof indices，the indices are divided into effective indices and redundant indices.In the palette a certain number of redundant indices are mapped to the color of an effective index.Then the indices mapping to the same color stand for different secret digits in order to embed extra data losslessly.A dynamic programming algorithm is used to find the best allocation for redundant indices to achieve the highest embedding capacity.Embedded data subsets carried by different colors are different notational sequences.The data embedding operation does not affect the original image.Experiments showthat themethod has higher embedding capacity than previous methods，especially for medical images.

lossless data hiding，palette image，mix-ary code，dynamic programming

TN911.73

0255-8297（2015）06-0637-07

10.3969/j.issn.0255-8297.2015.06.007

2015-06-26；

2015-07-20

国家自然科学基金（No.61472235）资助

张新鹏，教授，博导，研究方向：多媒体信息安全，E-mail：xzhang@shu.edu.cn