基于模运算的并行隐写算法

柯 琦，李 霞，廖琪男，朱丽娜

(广西财经学院 计算机科学系，广西 南宁 530003)

0 引 言

全球信息数字化的时代，数字图像的隐写技术已成为信息安全领域研究的重要内容之一。在空间域信息隐藏算法中，文献[1]使用LSB匹配嵌入方法，分析局部邻域的复杂性以自适应确定图像嵌入的位置，算法获得较好的抗攻击性。文献[2]提出了一种具有纠错能力和高嵌入率的盲信息隐藏算法。文献[3]基于LSB匹配算法的边缘自适应图像隐写改进算法，利用一种新的随机方式选择信息隐藏的相邻像素对。文献[4]对经典的嵌入方向拓展的模运算信息隐藏算法(EMD)提出多组修正方法进行改进，结合多个像素组所构造的开关映射嵌入秘密信息，避免EMD方法的转换冗余和分段策略的空间冗余，有效地提高嵌入量。文献[5]算法利用4个像素的差值判断边缘域和平滑域的像素变化进而实现自适应嵌入的EMD算法，图像边缘特征得以充分考虑，嵌入失真最小化。文献[6]提出基于差值直方图修正和最优EMD算法的可逆信息隐藏算法。文献[7]对全方位拓展的模运算信息隐藏算法(FEMD)提出改进，用数学公式计算来实现嵌入操作，计算4个修改方案进而选择最小修改方案，嵌入率种类选择少且不直观，计算复杂。文献[8]对EMD算法也用数学公式计算实现嵌入操作，但计算获得的不是像素最小修改量，且像素值修改量最大的是FEMD的4(a-1)/a倍。文献[9]实现将一位an进制信息隐藏到n个像素中的模映射隐写算法。以上文献主要从嵌入容量和图像质量两个指标进行算法改进，对隐写算法的不可检测性和安全性问题考虑欠缺，载密图像若被怀疑或被检测分析到有信息隐藏就很可能被拦截攻击。然而要设计安全性好的隐写算法，计算复杂度势必增加，算法运行效率将会降低。为提高隐写算法的不可检测性及安全性，并具有高嵌入率和高运行效率，本文在文献[9]的基础上，深入研究模运算特征[10]，利用多核计算机多个核心并行执行的优越性，设计了一个高效的模运算并行隐写算法。

1 相关算法

1.1 EMD算法

基于嵌入方向拓展的模运算信息隐藏算法(EMD)，其提取函数为

(1)

其中，(g1,g2,…,gn)为载体图像的一组像素值，n=2,3,…。

在n维坐标系中，某点(g1,g2,…,gn)和n个坐标轴方向上相邻点的函数值不相同，且正好是(2n+1)进制数的数码(0,1,2,…,2n)。利用此特性实现载体图像的n个像素隐藏一位(2n+1)进制的秘密信息，且最多修改一个像素值“1”的修改量。例如：图1为2D坐标中的函数值分布。

图1 2D映射坐标，n=2

EMD算法步骤如下：

(1)首先将秘密信息转化为(2n+1)进制的信息。如果加密信息是二进制形式的序列，则需要将序列分为每组L个bit，然后将每组转化为K位的(2n+1)进制数。其计算方式为

(2)

(2)取载密图像的n个像素(g1,g2,…,gn)，按照式(1)计算函数值f。

(3)修改载密图像像素的条件为：(2n+1)进制秘密信息d与函数值f的模距s为

s=(d-f) mod (2n+1)

(3)

若s=0，不改变任何像素值；若s≤n，则gs的值加1，否则g2n+1-s的值减1，即可实现秘密信息d的嵌入。

算法嵌入率为

Payload=log2(2n+1)/n

(4)

其最大嵌入率为1.16 bit/pixel。

1.2 改进的EMD算法

很多文献基于EMD算法思想进行了改进[4-9]，文献[9]提出n维超立方体模映射隐写算法(nDMM)，将n个像素值(x1,x2,…,xn)通过线性组合后的模运算结果映射到一位an进制秘密信息，算法提取函数为

(5)

式中：a=2,3,…；c=0,1,2,3,…,an-1；n=1,2,3,…。

a=2,3,…，选择不同的参数a可以得到不同的嵌入率和载密图像视觉质量。当n=1,2,3,…时，nDMM算法可变为一维模、二维方阵模、三维立方体模直至n维超立方体模映射隐写算法。该算法得到了较好的载密图像视觉质量并且安全性方面得到很大提高。

但是以上这些算法均存在着一些不足之处。首先，提取函数f未使用或简单使用一个固定值作为提取函数中像素值x的乘数参数，这个固定值并不一定是构成隐写算法的最优参数。因为不同的参数可获得不同的隐写方案，而最优的隐写方案获得更好的隐写效果。其次，由于EMD算法是需要在计算每组像素值之后再选择像素值改变量最小的一组，计算量大，随着n的增加，算法时间复杂度将以指数级增长，算法效率非常低。再次，文献[9]提取函数没有充分考虑算法自身的安全性，当参数a，n确定以后，整个载密过程的嵌入和提取函数就已确定，只使c作为模数移动系数，一旦a值被获知，且n的维数不高，提取函数很容易被穷举出来进而可轻易提取秘密信息。因此，本文在nDMM算法的基础之上进一步改进，设计一种嵌入率高且更安全高效的模运算并行隐写算法。

2 本文算法

2.1 参数化设计的隐写函数

信息隐藏参数设计，是指在信息嵌入和提取函数中，引入若干参数，选择不同的参数，可构成不同的隐写方案。参数个数及取值范围又决定密钥空间大小，因此隐写函数引入合适的参数可进一步加强隐写算法的安全性，提高抗信息提取能力。

本文算法根据模运算性质，实现将一位an进制秘密信息嵌入到n个载体像素中。算法引入一个可变系数μ及一个模数移动系数c，可动态的改变不同的隐写方案及控制载密图像的质量，并能获得载密图像像素失真最小的方案。设在n个载体像素(x1,x2,…,xn)中嵌入一位an进制秘密信息，提取函数定义为

(6)

其中，a=2,3,…；n=1,2,3,…；μ为可变系数，μ=1,2,3,…,an-1；c为模数移动系数，c=0,1,2,3,…,an-1。

实现一位an进制信息d的嵌入过程就是通过修改像数值(xi+Δxi)使得f=d。不同的μ和c取值，可构成不同f的隐写方案

(7)

2.2 建立最优参数查询表

可变系数μ的取值对隐写函数的确定和载密图像质量起决定性因素，不仅要满足式(7)，使得f=d，同时要使载密图像像素失真最小。相同的函数结果会因不同的μ值获得不同的像素变化量。也就是说，提取函数f获得同一个d值，Δxi的值会因为μ值的改变而改变。因此，选择像素组(Δx1,Δx2,…,Δxn)改变量最小的一组所对应的μ值去构造隐写函数进行信息隐藏，就可使得载密图像失真最小。

本文通过求解平均均方差(mean squared error，MSE)最小值来衡量函数值对应的像素变化量的改变大小，均方差的计算公式定义为

(8)

参数μ的取值范围本文定义为μ∈{1,2,3,…,an-1}。因为当μ取{an+1，an+2，an+3,…}时，其模运算结果是和μ∈{1,2,3,…,an-1}的一样，对Δx的值是没有影响的。

即：f(x)=μ’xmodan=μxmodan。

证明：根据模运算的加法和乘法运算规则

(a+b) modp=(amodp+bmodp) modp

(9)

(a*b) modp=(amodp*bmodp) modp

(10)

令f(x)=μ’xmodan， 当μ’∈{an+1,an+2，an+3,…} ，μ∈{1,2,3,…,an-1}时，则可表示为μ’=an+μ，则有

f(x)=μ’xmodan=[(an+μ)*x] modan=
[(an+μ)modan*xmodan] modan=[(anmodan+
μmodan)modan*xmodan]modan=[(0+μmodan)
modan*xmodan]modan=[μmodan*xmodan]
modan=μxmodan

即可证得当μ取{an+1，an+2，an+3,…}时，模运算结果和μ∈{1,2,3,…,an-1}的一样，对Δx的值没有影响，同理可扩展到f(x1,x2,…,xn)中。因此，本文算法参数μ的取值范围只考虑μ∈{1,2,3,…,an-1}。求出满足式(7)的所有μ值及对应的均方差，其中最小均方差对应的μ值，便是可变系数μ的最优参数解集。

在求解最优参数集μ时，μ的每种取值对应的每个d值都需要进行计算，算法达到an指数级运行时间，效率非常低。在求解过程中，每组n、a值的求解是相互独立的，若使用并行操作求解，是基本没有数据迁移、数据频繁交换、仿存冲突等并行开销问题，因此本文采用多核并行算法求解最优参数以提高算法运行效率。并行求解思路为：对需要计算的an组像素进行均匀分块，每个处理器核心取对应的像素组进行并行计算。

最优参数集μ的并行求解步骤：

(1)根据式(7)，令c=0，xi=0。

(2)设置n值，令初值n=2，n∈{2,3,…}。

(3)设置初值a=2，并获得Δx

(4)根据n遍历Δx，计算出{Δx1,Δx2,…,Δxn}所有的排列组合，当a为奇数时共an组(为偶数时(a+1)n组)，存为数组：perm。定义数组MSEk、mse，令k∈{1,2,3,…,an-1}。初始化d=0,d∈{0,1,2,3,…,an-1}。

(5)设处理核心数目为p，线程数为t；p个处理核心对an个d值分成an-1/p组，线程ti顺序取所在组对应的d值记为di。

forp=0 top-1 do in parallel //并行计算(6)～(8)

(7)令线程ti取下一个di值，di=d(i+t)；循环(6)步，则mse(k)=mse(k)+min(MSEk)。//把所有d值的MSE相加，得出一个最优值μ的mse。

(8)令μ=μ+1；循环(2)～(7)，使得直至获得所有μ的从d=0～an-1的MSE总和mse。求解最小值min(mse)，即可得到每组a,n值对应的最优解集μ值。

endfor

经计算后不同n,a组合得到不同的最优μ值解集。选择不同的μ值及其模数移动系数c，则构造出像素改变量最小的不同的最优隐写方案，可使隐写算法的密钥空间增大，安全性增强。

由于求解最优解集μ值与载体图像的像素值没有关系，且求解耗费一定的时间，本文将先建立好一张最优解集查询的二维表，把不同n,a组合的最优解集μ值记录到表中，当对图像进行信息隐藏时，根据n,a实际需要直接查表，选择最优参数μ作为隐写函数的构成参数，则可提高信息隐藏效率。

例如：令a=2,n=2，则an进制秘密信息取值d∈{0,1,2,3}，μ的范围取μ∈{1,2,3}。根据上述算法求出μ=1，mse(1)=4；μ=2，mse(2)=3；μ=3，mse(3)=4；则μ的最优解min(mse)=3，可知μ=2时提取函数f(x1,x2)中Δxi的值改变量最小，即可用于构成最优参数的隐写算法，便将其记录在最优解集查询表中。

2.3 嵌入过程

根据式(6)，本算法秘密信息的嵌入过程如下，令本文嵌入算法记为nDPMM：

(1)将待隐藏的二进制秘密信息转化为an进制信息。依次取L位二进制数据流D转换为K位an进制的数字。L、K的取值为

(11)

利用混沌Lorenz系统产生一组随机序列作为密钥，根据随机序列选择n个载体像素(x1,x2,…,xn)来隐藏1位an进制信息d。根据a和n的值选择最优可变系数μ值，确定提取函数式(6)，再进行函数值f的计算。按以下规则确定像素值xi的修改量：

当f=d时，不改变像素xi；

否则，当f≠d时：

a为奇数时，在集合A中遍历Δxi，使得满足f=d

f(x1+Δx1,x2+Δx2,…,xn+Δxn)=d

(12)

a为偶数时，在集合A中遍历Δxi，使得满足f=d和像素值修改量最小

(13)

(14)

2.4 信息提取

2.5 信息隐藏并行处理

现今的实验环境普遍使用了2核CPU及以上的多核计算机，计算机硬件已经完全支持了图像加解密算法的单机并行化处理。但目前大多数数字图像信息处理方法，很少有利用多核计算机支持多线程并行处理这一硬件条件，而通过编写并行算法去提高信息隐藏算法运行效率的文献则更少。在信息隐藏过程中对像素组进行嵌入和提取时，像素组之间是没有数据通信、资源共享同步及仿存冲突等问题，图像可以按像素组划分成任意大小块，每个任务块的执行没有先后次序，在并行处理时各计算核心及线程可实现完全负载均衡。因此使用线程级粗粒度的并行化方法来提高信息隐藏算法的运行效率是完全可行的。并行处理步骤为：

(1)任务划分。设载体图像像素M*N，有p个处理器核心，t个线程。根据一次要嵌入的载体像素组的个数n，均匀的划分任务块，设每块大小blocki为：blocki=M*N/(n*p*t)，i∈{0,2,3,…,p-1}，剩余像素归入最后一块任务中。设载体像素数组为：CoverImage。

(2)并行执行。每块数据分给每个处理器核心，其线程调用嵌入算法并行执行相应任务块像素的嵌入。定义start及end两个数组用于记录每块任务blocki的起止地址，每个线程依次读取每块任务进行信息隐藏。

forp=0 top-1 do in parallel

//p个处理器核心同时执行

nDPMM(CoverImage[end(ti)]-CoverImage[start(ti)])；

//第i个线程所分得的数据块进行嵌入操作

endfor

(3)存储载密图像。设数组StegoImage用来存储载密图像，每个并行任务处理完以后，根据该任务块start、end的记录地址，直接写入对应的载密图像数组内，即可完成整个图像的嵌入操作。

并行处理秘密信息的提取过程也同样适用。

3 实验结果与分析

实验采用Matlab2012b、VS2010平台，OpenMP和C语言编程实现，实验图像选用大小都是512×512的Lena，Peppers，Baboon和Airplane的标准灰度图像，如图2所示。分别验证本文信息隐藏算法的可行性及各项性能指标：嵌入率、峰值信噪比(PSNR)、安全性、失真度及其算法运行效率。

图2 载体图像

3.1 嵌入率

本文算法的嵌入率计算式为

Payload=log2a

(15)

3.2 平均均方差及峰值信噪比

峰值信噪比PSNR用来评价载密图像视觉质量，PSNR越大，图像质量越高，理想图像视觉质量要求PSNR>39 dB。256级灰度图像的PSNR计算公式为

PSNR=10×log10(2552/MSE)

(16)

其中，MSE为原图像与载密图像之间的均方差(mean squared error)，计算式为

(17)

本文算法的MSE计算方式为

(18)

本文算法测试不同an情况下，选择最优μ值，对图像进行秘密信息载入。其中Lena图像的嵌入率和载密图像视觉质量峰值信噪比PRSN的实验结果见表1。

表1 不同an值的嵌入率和载密图像峰值信噪比PRSN

表1为载密图像Lena在不同a，n组合下的嵌入率和视觉质量峰值信噪比PRSN的实验结果。表1显示，本文算法选择不同的a值获得不同的嵌入率，并且得到良好载密图像的视觉质量。对于其它不同类型图像得到峰值信噪比也是基本一致的。从实验数据可得结论为当a越大嵌入率越大，但信噪比会相应减小；当a值相同时，选择n较大时获得更好的视觉效果。

3.3 不可感知性

本实验所用的an进制秘密信息、嵌入的像素位置序列及其安全系数c均由Lorenz混沌系统生成的随机序列处理得到。实验将秘密信息嵌满整个载体图像，实验结果表明，无论a，n的值取，从载密图像提取的an进制随机秘密信息与嵌入时的an进制信息是完全一致的。

图3是当a=2，n=4时，本文算法4PDMM对图2的4幅原图像嵌入秘密信息后的载密图像，其中嵌入率为Payload=1bpp，PSNR远大于理想值39 dB。图4是当a=8，n=8时，本文算法8PDMM对图2的4幅原图像嵌入秘密信息后的载密图像，嵌入率Payload=3bpp，PSNR也大于理想值39 dB。虽然图3与图4的PSNR值相差大，但PSNR值均大于39 dB，与图2的原图像对比，图像视觉效果无异样也无失真现象，实验说明了本文算法载密效果的不可感知性是良好的。

图3 当a=2，n=4时本文算法的载密图像

图4 当a=8，n=8时本文算法的载密图像

3.4 与EMD等经典算法比较实验

图5是本文算法与LSBs，OPAP，LSBMR，EMD，FEMD，4DMM经典算法进行信息隐藏后的载密图像视觉质量的对比。其中LSBs，OPAP，LSBMR，EMD，FEMD算法的MSE已在文献[9]中给出了详细的计算式。本实验采用Lena载体图像进行对比，假设秘密信息数据范围是均匀分布的，由于EMD算法在n=2时算法的最大理论嵌入率为1.16 bpp，文献[9]的4DMM算法是采用2位五进制信息表示4位二进制信息数据进行测试的。为了与EMD算法、4DMM算法等保持等同的实验条件，本文算法也选用同样进制数秘密信息进行测试，即嵌入函数的参数为a=2，n=4，实际嵌入率为1 bpp。

图5 本文算法和其它经典算法信噪比对比

图5显示，实验在载体图像、秘密信息、嵌入位置等实验条件等同情况下，当a=2，n=4且选择最优参数u时本文算法在信息隐藏后得出的信噪比PRSN为52.8697，高于其它经典算法，说明本文算法载密图像质量是优于其它算法的。

表2是本文算法nDPMM与FEMD、nDMM算法在采用相同a，n取值、相同秘密信息、相同嵌入位等实验条件等同情况下，对载体图像Lena进行秘密信息嵌入获得的PRSN比较。

表2显示，当n=1时，根据本文式(7)计算x1的μ参数为μ0=1，本文算法1DPMM与文献[9]的1DMM算法相同，两者的载密图像信噪比PRSN也相同，但比FEMD的信噪比略低。当n=2时，由于本文算法的嵌入函数选择的最优参数μ=2，与nDMM算法的嵌入函数一样，二者算法得到的PRSN基本是一致的。当n>2时，由于本文算法的嵌入函数选择了最优参数μ值，使得信息嵌入时像素值改变量达到最小，则比FEMD、nDMM获得的均方差都减小，进而PRSN更大，得到了更好的图像嵌入质量。因此，本文算法引入一个可变系数μ控制像素的改变量，在选择最优系数μ后与其它算法相比，载密图像像素相失真最小，载密图像质量更好。

3.5 算法效率

本文算法采用了多核并行计算提高算法效率，图6、图7是实验使用多个核心并行的执行嵌入算法的运行时间对比。

表2 本文算法和FEMD、nDMM信噪比对比

图6 a=2时本文算法运行时间

图6是参数选取a=2，嵌入像素个数n=2～8时，本文嵌入算法分别在串行和并行2核、3核、4核情况下的运行时间对比图。如图6所示，在串行情况下执行时，算法运行时间是最高的。当并行执行核心数从2核增加到4核时，算法运行时间随着执行核心数的增加而降低。实验结果说明对载体图像进行分块，多个处理核心并行执行嵌入操作，算法运行效率可获得显著的提高。

根据图6曲线变化趋势，当本文算法在n取值从2至8时，运行时间曲线图不是线性增长，而是在n=4时最低，而随着n往两端的减小或增大，算法时间逐渐增加。当分别在两端n=2和n=8时，算法运行时间明显增高，串行执行时间曲线更明显，并行执行时间曲线图亦然。说明本文的嵌入算法在n=4附近算法运行效率最高，即一位an进制秘密信息嵌入到4个载体像素中，嵌入率为Payload=2bpp。其原因在于本文算法每次要对n个像素进行嵌入处理，如果n值较小，整幅图像需要嵌入操作的次数增多。如果n值较大，嵌入次数虽减少，但是每一次嵌入的时间则增大。因此实验结果表明，当n=4时嵌入算法时间效率最高。

图7是像素个数为n=4，a取2～8时，本文嵌入算法分别在串行和并行2核、3核、4核情况下的运行时间对比。根据图7所示，本文嵌入算法在串行执行时，算法的运行时间随着a值的增加显著上升。当分别使用2核、3核、4核并行运行时，本文算法对载体图像进行分块并行嵌入，随着计算核心数的增加，算法的运行时间逐渐降低。因此，本文算法利用多核并行处理以后，算法运行效率得到显著提高。

图7 n=4时本文算法运行时间

3.6 算法安全性

本文使用了Lorenz混沌系统产生的随机序列作为密钥。由模数移动系数c和可变系数μ的排列组合密钥来确定具体嵌入方案，不同的c和μ的取值将构成不同的嵌入算法，c和μ的密钥取值空间均为an！。对嵌入像素的位置进行随机性选择，以Lorenz混沌系统双精度浮点数为密钥，可取精度10-15，则密钥空间是1045。因此本文嵌入算法的密钥空间为1045×an！×an！，密钥空间足够大，使用密钥穷举法进行蛮力破译是难以成功的。若在同一图像的载密过程中，对不同的像素选择不同参数的嵌入算法，或同一载密图像的嵌入位置分段使用不同的Lorenz随机序列组作为密钥，则本文信息嵌入的密钥空间更大、安全性更高。

4 结束语

本文针对隐写函数的不可检测性及安全性因素，并考虑算法的运行效率，提出一种通过查表方式选择最优参数构造嵌入函数的高效模运算并行隐写算法。理论分析及实验结果表明，通过选择可变系数构造最优的嵌入算法，使载体图像像素的改变量最小，载密图像的不可感知性获得了良好的效果。与其它隐写算法相比，本文算法有更好的嵌入效果，更高的信噪比。其次，使用多核并行计算进行处理，多个处理核心并行的对载体图像进行像素嵌入，算法运行效率得到很大的提升。最后采用参数化设计思想，使用Lorenz混沌系统序列作为密钥，密钥空间足够大，算法获得了更好的抵御隐写分析能力的特性和更高的安全性。