定长编码和哈夫曼编码的密文域可逆信息隐藏

吴友情，张睿灵，汤进，殷赵霞*

1. 安徽大学多模态认知计算安徽省重点实验室， 合肥 230601；2. 合肥师范学院计算机学院， 合肥 230601

0 引 言

数字图像可逆信息隐藏(reversible data hiding, RDH)是一种将秘密信息嵌入图像，接收方可以根据密钥提取秘密信息并恢复原始图像的技术(Zhang，2013；王继林 等，2018)。对于军事、医疗和法律等极为重视数据安全的领域,RDH技术至关重要。随着云存储和云计算技术的发展，大量私密数据被上传并存储在服务器端。为了保护用户隐私，在用户数据上传服务器之前，需要进行加密处理。由此，密文域的可逆信息隐藏(reversible data hiding in encrypted images，RDHEI)技术受到了广泛关注。RDHEI技术具体包含3方面：内容拥有者、信息隐藏者和接收者。内容拥有者即原始图像所有者在将明文图像发送到云端之前对其进行加密。信息隐藏者即云管理者在不知道图像的原始内容或用于加密图像的密钥的情况下，可以在加密的图像中嵌入秘密信息。接收者可以根据加密密钥和隐藏密钥完全恢复原始图像并无误提取秘密信息。

一些RDHEI技术中，接收方的秘密信息提取与原始图像的恢复是同时进行的(Zhang，2011；Zhou 等，2016)，应用比较局限。研究者提出分离的密文域可逆信息隐藏算法，实现了可分离的信息提取和图像恢复，对于用户隐私保护和云数据安全与管理具有重大意义。RDHEI技术虽然保证了图像的安全性，但加密导致图像的冗余度降低，其载荷量要低于明文域的RDH技术。目前的可分离RDHEI技术关注如何更大程度压缩明文图像或密文图像，根据压缩空间在信息隐藏过程中出现的次序，可将RDHEI技术分为3类。

第1类RDHEI技术是在图像加密之后腾出空间(vacating room after encryption, VRAE)，即直接对密文图像进行压缩以嵌入秘密信息。这种方法保证了内容拥有者和数据隐藏者功能相分离，应用比较广泛，但由于密文图像的冗余度低，很难获得较大容量的空余空间，导致嵌入率比较低。Zhang(2012)通过牺牲密文图像的低位平面来嵌入辅助信息和秘密信息，实现了可分离的信息提取和原始图像恢复。Qin等人(2018)根据密文图像各分块的平滑程度来使用不同的压缩方法空出空间。Qin等人(2019)通过位平面、块和像素置乱的方法对明文图像加密，增强了图像的安全性，并用稀疏矩阵编码的方法对密文图像编码，取得了不错的信息嵌入率。王继军等人(2020)通过构造遍历矩阵对明文图像进行加密，对密文图像计算高质量插值图像对应的期望插值，并构造抛物线引导秘密信息嵌入，保证了载密图像的高质量，同时获得了较高嵌入率。

第2类是在加密的同时腾出空间(vacating room by encryption, VRBE)。通过设计特殊加密方法(如同态加密)，使明文图像加密后仍能保持图像的部分区域相关性，从而使一些高效的RDH方法能够直接用在密文图像上。项世军等人(2016)使用同态加密的方式对明文图像加密，在保证图像安全性的同时保持了密文图像的部分区域相关性。Xiao等人(2017)在同态密文图像上使用像素值排序，获得了较好的性能。Huang等人(2016)对明文图像中每个分块使用同一个字节的加密密钥，即每一分块中的所有像素均采用相同的加密密钥，以此来保证密文图像的各分块中仍能保持区域相关性。Yi和Zhou(2019)提出了一种参数二叉树标记算法，充分利用图像分块内的局部相关性，取得了较高的嵌入率。Fu等人(2019)使用块置换和流加密的方式加密图像，保留了各分块的冗余度，数据隐藏者使用哈夫曼编码压缩密文图像高位平面，进一步提升了信息嵌入率。

第3类是在加密之前预留空间(reserving room before encryption, RRBE)。由内容拥有者对明文图像进行压缩，腾出空间后再进行加密，这种方法充分利用了明文图像的空间相关性，极大地提高了RDHEI技术的嵌入率。Ma等人(2013)将明文图像各分块分为平滑类和非平滑类，将RDH算法用于平滑的块，空出的空间用非平滑块的低位平面填充，非平滑块空出的空间用于嵌入秘密信息。Yi和Zhou(2017)在位平面分块中的0或1的个数较少的时候，只保存该分块的类别和其中0或1的个数信息，空余空间用于嵌入秘密信息。袁源等人(2019)在Yi和Zhou(2017)的基础上，充分利用了相邻位平面之间的相关性，通过相邻位平面的异或操作来减少其冗余度，得到了较大的嵌入空间。还有不少算法均采用像素预测和存储预测误差的方法空出空间。Puteaux和Puech(2018a)对明文图像最高位平面进行预测，嵌入率不超过1 bit/像素。Puyang等人(2018)在Puteaux和Puech(2018a)的基础之上预测两个高位平面，将嵌入率提升到1.3 bit/像素左右。Puteaux和Puech(2018b)进一步充分利用明文图像的相关性，预测所有位平面，将嵌入率提升到1.8 bit/像素左右。Wu等人(2020)基于Yi和Zhou(2019)的参数二叉树标记算法，将其应用在整个图像上，充分利用了明文图像的相关性，较大程度提升了信息嵌入率。Yin等人(2020)使用MED(median edge detector)方法对像素进行预测，并使用哈夫曼编码记录预测值与原始值出现差异的最高位平面位置，空出了较大空间。Chen和Chang(2019)利用扩展的行程编码对明文图像的前5个高位平面进行压缩，并通过位平面重排列将空出的空间排放在3个低位平面中，分离的实现了信息无错提取与原始图像无损恢复，并取得了较高的嵌入率。

本文基于Chen和Chang(2019)提出了一种定长编码和哈夫曼编码相结合的高位平面编码方案，使用哈夫曼编码代替Chen和Chang(2019)中扩展行程编码的定长码字编码，同时变长码字编码也不再使用其长度商和余数的组合，而是使用定长编码。基于该编码方案设计出一种RRBE的RDHEI算法。提取原始图像的高位平面并将其分块，提取出每一分块的比特流。根据高位平面比特流中相同比特的长度进行编码：对于相同比特长度较短的比特串进行哈夫曼编码；对于相同比特长度较长的比特串进行定长编码，将图像低位平面的比特流填充到高位平面压缩后的空出空间中。然后对图像进行加密，并将秘密信息根据隐藏密钥嵌入密文图像腾空的低位平面中。在接收方可以仅利用隐藏密钥提取载密图像低位平面中的信息并解密成原始秘密信息，也可以仅使用图像加密密钥恢复原始明文图像。

1 联合编码

对于灰度图像的8个位平面，高位平面代表图像的轮廓特征，体现着图像的区域相关性，所以明文图像的高位平面相邻比特相关性很强(如图1位平面8所示)。相比之下，低位平面对像素值的影响较小，其随机性强(如图1位平面1所示)，若对其进行编码压缩，不仅不能获得较大的压缩空间，还会增加过多的额外比特。所以本文算法只对前5个高位平面进行压缩，而后3个低位平面不做压缩，对各高位平面中相同比特较长的连续比特串进行定长编码，对相同比特长度较短的比特串进行哈夫曼编码。由于自然图像高位平面的空间相关性，由高位平面扫描而成的比特流大多较为连续，上述组合编码能够充分利用这个特性，对高位平面比特流进行压缩能够腾出较大的空间。

图1 灰度图像位平面示意图Fig.1 The bit planes diagram of grayscale image

1.1 分块扫描

对高位平面进行分块，可以充分利用图像的局部相关性，提取出更为连续的比特串。本文算法采用了Chen和Chang(2019)中(如表1所示)的4种分块扫描方式，将位平面转换成比特流。

如图2(a)所示，选取一个4×4的高位平面，块大小为2×2，图2(b)为表1中4种扫描方式得到的对应比特流。

表1 分块位平面的4种扫描方式Table 1 Four types of blocked-plane scanning

图2 高位平面扫描示意图Fig.2 Diagram of MSB plane scanning((a)MSB plane；(b)bitstreams from four types of scanning)

1.2 编码方案

为了充分利用扫描得到的比特流的比特连续性，设计了一种联合编码方案：短比特串的哈夫曼编码与长比特串的定长编码相结合。

1.2.1 短比特串的哈夫曼编码

用Ls来表示短比特串的长度，当比特流中相同比特的长度L小于Ls时，继续选取后Ls-L位比特构成一个长度为Ls的比特串。当比特流末尾的串长度不足Ls-L时，通过补0将其扩展为长度为Ls的比特串。统计高位平面中短比特串出现的概率，使用哈夫曼算法对该类短比特串进行编码，并在码字前添加前缀(flag=1)组成短比特串的编码，其中前缀flag=1用来表示该组编码属于短比特串编码。

哈夫曼算法根据短比特串所出现的概率对其进行变长编码，由此构造出一个平均编码长度最短的编码表。如短比特串长度为2，有00、01、10、11共4种串，若其出现的概率依次为0.1、0.1、0.3、0.5，根据哈夫曼编码，出现概率越大的比特串采用越短的码字，编码如图3所示。这4种比特串分别对应码字110、111、10、0，该编码表的平均编码长度为1.7，小于原始的编码长度2。

图3 哈夫曼编码过程Fig.3 Example of huffman coding

在图1所示的位平面中，选取Ls=3，统计前5个高位平面中长度为3的短比特串所出现的概率，其中000和111视为长比特串，将在定长编码中介绍。表2为其短比特串对应概率和哈夫曼编码。哈夫曼编码属于前缀编码，在解码过程中可以按比特流顺序扫描，当遇到前缀flag=1时，表明该组编码为短比特串的哈夫曼编码，此时根据哈夫曼编码表依次扫描，直到与编码表中某一码字完全匹配时停止，该码字对应的短比特串即为原始比特串。

表2 图1的5个高位平面中长度为3的短比特串的哈夫曼编码Table 2 Huffman coding for short bitstreams of length 3 in five MSB planes of figure 1

1.2.2 长比特串的定长编码

图5展示了图1中位平面4长度为64的比特流的编码过程(其中短比特串的哈夫曼编码表由表2所示)。

图4 定长编码结构Fig.4 Fixed-length coding structure

图5 图1中位平面4的压缩编码过程示例Fig.5 The process of compressing the 4th MSB plane in Fig.1

2 联合编码的RDHEI算法

本文提出的联合定长编码和哈夫曼编码的密文域可逆信息隐藏算法结构如图6所示。根据RDHEI技术中的3方分为3部分，高位平面压缩与图像加密、信息隐藏、信息提取和图像恢复。原始图像所有者对高位平面采用分块扫描得到比特流，对比特流中连续长比特串进行定长编码，对短比特串进行哈夫曼编码，从而腾出较大空间，通过重排列将空出空间排放在低位平面中，并使用流密码加密重排后的图像。信息隐藏者利用隐藏密钥将秘密信息嵌入密文图像低位平面已空出的空间中。在接收方，可以通过隐藏密钥进行秘密信息提取，通过加密密钥对原始明文图像进行无损恢复。

图6 本文RDHEI算法框架Fig.6 Framework of the proposed RDHEI algorithm

2.1 高位平面压缩与重排

本文算法中的编码方案针对前5个高位平面进行编码压缩，在随机性强的低位平面编码压缩率较低，且会增加过多的额外比特，故后3个低位平面不做编码处理。压缩后的位平面重排列基于Chen等人(2019)的重排列方案，添加了辅助信息Lfix和Ls以及哈夫曼编码表信息。图7详细给出了对图1中位平面压缩编码和重排列的具体过程。首先在最高位平面(位平面8)的开始位置存储辅助信息，包括块大小(4位)、压缩的位平面数量(3位)、Lfix(3位)、Ls(3位)、哈夫曼编码表(29位)。其中哈夫曼编码表按照短比特串依次存储码字，以011110为分隔符(在图7中，为更好展示，使用更短且与码字无冲突的0110为分隔符)，各码字中每连续3个1后添加一个0，从而防止码字与分隔符冲突，解码时依次寻找分隔符，分隔符之间的比特串即为对应短比特串的码字，通过删去各码字中3个连续1后的0得到正确的码字。所有经过压缩的高位平面，均需两个比特存储该位平面的扫描类型(Type1:00, Type2:01, Type3:10, Type4:11)，用log2(mn)=6位比特(m=8,n=8为原始图像的尺寸)表示该高位平面压缩后的比特流长度Lc，接着后Lc位比特存储该高位平面压缩后的比特流。压缩后的高位平面剩余的比特位则用低位平面填充。在最低位平面(位平面1)中用log2(mn)+2=8位表示空出的空间总大小Lv，后Lv-(log2(mn)+2)位(以位平面1、2、3的顺序依次计数)用来嵌入秘密信息。

2.2 图像加密

经过上述压缩和重排后的位平面比特表示为Ii,j,k，i,j表示位平面的第i行第j列，k表示第k个位平面，使用流密码对重排后的图像进行加密，用加密密钥Ken产生一个随机矩阵Em×n，m,n为原始图像的尺寸。加密后的图像I′为

(1)

式中，1≤i≤m，1≤j≤n，⊕为按位异或操作。为了能够正确的嵌入和提取信息，对低位平面表示空出空间大小的信息位不进行加密处理。加密后灰度图像V第i行第j列的像素值Vi,j为

(2)

2.3 信息嵌入

压缩后的图像经重排列后，空出空间大小信息和空出空间在图像低位平面中，如图7所示，在图像加密过程中空出空间大小信息不经过加密。在信息嵌入过程中，首先根据最低位平面中空出空间大小信息计算出用于嵌入秘密信息的空间，然后使用隐藏密钥Kh将秘密信息嵌入空出空间中。

图7 腾出高位平面空间过程示例Fig.7 The process of vacating room from MSB planes

2.4 信息提取与图像恢复

当接收方拥有隐藏密钥Kh时，可以直接从载密图像的最低位平面中提取得到空出空间的总大小Lv，低位平面后Lv-(log2(mn)+2)位(以位平面1、2、3的顺序依次计数)即为嵌入的秘密信息，然后通过Kh解密得到原始秘密信息，从而不需要对载密图像进行解密就可提取出秘密信息。

当接收方拥有加密密钥Ken时，可以恢复出加密之前的原始明文图像。首先通过加密密钥生成随机矩阵Em×n，与载密图像做按位异或操作，提取出最高位平面中的块大小、压缩位平面数量、定长编码长度、短比特串长度以及哈夫曼编码表等辅助信息。根据各高位平面中压缩串长度提取位平面的压缩串，即压缩后的比特流，对其解码还原原始高位平面，将高位平面中填充的低位平面还原，从而得到原始图像的所有位平面，即可恢复原始明文图像。

3 实验结果与分析

密文域可逆信息隐藏算法的性能可以从有效载荷、错误提取的比特数和重构后的图像质量来评估，而一般算法都能满足秘密信息的无错提取和原始明文图像的无损恢复，因此有效载荷是密文域可逆信息隐藏的关键评价指标。为了验证本文算法的有效性，实验选取了5幅标准测试图像进行性能测试，如图8所示。同时测试了UCID(an uncompressed color image database)(Schaefer和Stich，2003)、BOSSBase(Break Our Steganographic System)(Bas等，2011)和BOWS-2(Break Our Watermarking System 2nd)(Bas和 Furon，2017)这3个数据集证明算法的普适性。为了定量分析本文算法的性能，使用峰值信噪比PSNR(dB)和结构相似度SSIM两个指标来衡量原始明文图像的恢复质量，选用秘密信息的嵌入率ER(bit/像素)作为衡量算法有效载荷大小的关键指标。

图9展示了测试图像在不同短比特串长度和定长编码长度上的嵌入率，选取块大小均为2×2。可以看出定长编码长度为5时比长度为4时嵌入率更高，同时随着短比特串长度的增加，嵌入率出现先增后减的趋势，在Ls=7时图像嵌入率较高。定长编码长度取决于原始比特流中出现的连续比特的长度，若取值过大，会增加过多的额外比特，影响压缩率。而短比特串长度过大时，哈夫曼编码对短比特串的压缩效率也会降低。所以实验中将定长编码长度设置为Lfix=5，短比特串长度设置为Ls=7。

图10比较了本文算法与同类算法Puteaux和Puech(2018a)，Puyang等人(2018)，Yi和Zhou(2019)，Chen和Chang(2019)在测试图像上的嵌入率。为了获得更好的性能，将Yi和Zhou(2019)算法中的参数设置为α=5，β=2，块大小为3×3，设置Chen和Chang(2019)算法中的定长码字长度为3，块大小为4×4。从图10可以看出， Puteaux和Puech(2018a)算法对测试图像的嵌入率在1 bit/像素以下， Puyang等人(2018)方法通过替换两个高位平面使嵌入率提升到1 bit/像素以上，Yi和Zhou(2019)方法和Chen和Chang(2019)方法进一步提升性能，都获得了较好的嵌入率。本文算法采用定长编码和哈夫曼编码相结合的方式，对图像的前5个高位平面进行压缩，块大小选取为2×2，定长编码长度为Lfix=5，短比特串长度为Ls=7。在测试图像中，除了Baboon图像，其余各图像分别较同类算法中最高嵌入率高出0.023 5 bit/像素，0.051 8 bit/像素，0.159 1 bit/像素和0.060 7 bit/像素。在Baboon图像中，非平滑区域较多，导致比特流中短比特串较多，定长编码压缩效率低，从而秘密信息嵌入率较低。

图8 测试图像Fig.8 Test images ((a) Lena; (b) Man; (c) Jetplane; (d) Baboon; (e) Tiffany)

图9 测试图像在定长编码长度(5,4)和短比特串长度(4,5,6,7,8)上的嵌入率Fig.9 Embedding rates under fixed-length (5,4) and short stream length (4,5,6,7,8) on test images((a)fixed-length Lfix=5；(b)fixed-length Lfix=4)

图10 本文算法与同类算法在测试图像上的嵌入率比较Fig.10 Comparison of embedding rate of the proposed method and four competitors on test images

为进一步验证本文算法的普适性，将本文算法应用在UCID、BOSSBase和BOWS-2这3个数据集上，同样块大小选取为2×2，定长编码长度为Lfix=5，短比特串长度为Ls=7，测试结果如表3所示。本文利用前5个位平面进行压缩，空出空间经过重排列排放在3个低位平面中，因表示空出空间大小的比特可忽略不计，故所能达到的最高嵌入率约为3 bit/像素，此时高位平面压缩出的空间不小于3个低位平面的总容量。由表3可知，在3个数据集上的最低嵌入率分别为0.362 7 bit/像素，0.311 2 bit/像素和0.202 5 bit/像素，平均嵌入率分别为2.123 4 bit/像素，2.410 7 bit/像素和2.380 3 bit/像素。表3中PSNR→+∞，SSIM均为1，说明本文算法能够对原始明文图像进行无损恢复。

表3 本文算法在不同数据集上的嵌入率、峰值信噪比和结构相似度Table 3 The embedding rate, PSNR and SSIM of the proposed method on different datasets

图11比较了本文算法与同类算法在3个数据集上的平均嵌入率。可以看出，本文算法的平均嵌入率较同类算法均有提升，在数据集UCID上比同类算法中的最好嵌入率高出0.246 6 bit/像素，在数据集BOSSBase上高出0.088 1 bit/像素，在数据集BOWS-2上高出0.135 6 bit/像素。实验结果表明，本文提出的联合定长编码和哈夫曼编码的RDHEI算法，能分离的、无损的提取秘密信息和恢复原始图像，并取得了较高的信息嵌入率，具有更好的性能。

图11 本文算法与同类算法在3个数据集上的平均嵌入率比较Fig.11 Comparison of average embedding rate of the proposed method and four competitors on three datasets

时间复杂度与空间复杂度是衡量算法效率与计算代价的重要指标，时间复杂度能够反映出算法的计算时间开销，空间复杂度反映出算法运行时占用空间的开销。本文方法在内容拥有者上，对前5个高位平面进行分块扫描得到比特流，长比特串可以在扫描时直接进行定长编码，短比特串在扫描时统计各短比特串出现的频数，扫描全部完成后利用短比特串出现的频率来生成哈夫曼树并对比特流中的短比特串压缩。总的时间复杂度为O(5mn+slog2s)，其中m,n为图像的大小，s=2Ls-2为短比特串的种类数。设除去编码表后的辅助信息占d比特，若通过编码压缩可腾出k比特的空间，则在信息隐藏者上，根据辅助信息得到腾出空间的位置，依次嵌入k比特加密后的数据，时间复杂度为O(d+k)。在接收者恢复图像过程中，提取辅助信息，根据编码表生成哈夫曼树，扫描压缩比特流并同步解压缩的时间复杂度为O(slog2s+8mn-k)。在接收者提取秘密信息的过程中，根据辅助信息定位秘密信息的位置，然后使用密钥解密，花费时间O(d+k)。根据哈夫曼树的结构可知哈夫曼编码表中码字共2s+1比特，分割符占6s比特，共占t=8s+1比特。在空间复杂度上，内容拥有者提取出位平面的比特流，存储比特流的同时直接进行定长编码，存储短比特串然后根据哈夫曼编码表压缩与重排，所需空间O(8mn+t)，信息隐藏者需要空间O(8mn+k)以存储8个位平面与待嵌入数据，接收者恢复图像与提取数据分别需要空间复杂度为O(8mn+t)与O(8mn+k)。

4 结 论

密文域可逆信息隐藏技术应用广泛，其中最重要的衡量标准是信息嵌入率。为了提升密文图像的信息嵌入率，基于Chen和Chang(2019)的方法，本文联合定长编码和哈夫曼编码实现了高压缩率，使用图像分块扫描得到较为连续的比特串，对长比特串采用定长编码，对短比特串采用哈夫曼算法进行编码，为嵌入秘密信息预留较大空间，相比同类算法提高了秘密信息的嵌入率。接收方通过隐藏密钥可提取秘密信息，通过加密密钥可以从载密图像中恢复原始明文图像，且提取和恢复的过程是分离的、无损的。虽然提出的算法在嵌入率上有提升，但对于非平滑图像，连续的比特串较少，编码压缩率较低，导致信息嵌入率偏低。如何提升算法在非平滑图像上的嵌入率是下一步继续研究的方向。