欧阳春娟，李 霞，李 斌

1)深圳大学信息工程学院，深圳518060;2)深圳市现代通信与信息处理重点实验室，深圳518060

最低有效位匹配［1］(least significant bits matching，LSBM)隐写，是当秘密信息与载体图像最低有效位不同时，通过随机加减1 方式，有效避免值对现象，增强检测难度. 该算法安全简单，因此被广泛应用. 为进一步扩大嵌入容量，本研究将秘密信息嵌入最低K(K ＞1)个位平面上，通过像素进行加减变换，得到LSB±K 隐写(其中K 为位数).然而，安全性和隐藏容量是相互制约的，若对高位平面采用类似策略进行数据嵌入，在增大嵌入容量的同时，会引起安全性的严重下降. 为此，根据嵌入容量和安全性相互矛盾的关系，将LSB ±K 隐写设计建模为一个多目标优化模型，在保证隐写安全性的同时，尽量获得较大的嵌入容量. 本研究基于非支配排序和分层重构等特点设计了一种递进多目标混合蛙跳优化算法，并将其应用于LSB ±K 隐写的优化设计中. 在优化LSB ±K 隐写中，对图像进行分块处理，对应所有图像子块组成的矩阵构成优化算法的可行解，矩阵元素代表对应图像块像素的嵌入位数. 以载体图像与载密图像差分图的直方图特征函数质心差值代表安全性作为一个优化目标，另一个优化目标为图像嵌入容量. 选择Pareto 前沿解集中的解对整幅图中不同的图像块进行LSB ±K隐写得到载密图像. 实验结果表明，采用本研究所提的基于递进多目标蛙跳优化的LSB ±K 隐写算法可提供多种满足安全性和容量平衡的嵌入选择方案. 在Pareto 解集中，选择最低嵌入容量的可行解进行隐写，与LSBM 隐写及单目标优化LSBM 隐写相比，在获得相近抗分析性能下，嵌入容量提高了30%. 与相同容量下的LSB ±2 隐写及单目标优化的LSB±2 隐写相比，具有更强的抗分析能力.

1 多目标混合蛙跳优化算法

1.1 混合蛙跳算法

2001 年，Eusuff 等［2］提出混合蛙跳算法(shuffled frog leaping algorithm，SFLA). SFLA 将局部搜索和全局信息交换相结合，具有参数少、寻优能力强等特点. SFLA 算法优化过程为:初始化种群，P= {X1，X2，…，XF}，按个体适应度值降序排序后，将种群按式(1)平均分配到m 个族群

每个族群有n 个青蛙，F = m × n. 迭代过程中，在每个族群中依次选择以下方式不断更新适应度值最差的个体Xw. 首先，按式(2)更新

其中，Xb为当前族群适应度值最好的个体，r ∈［0，1］. 若更新后X'w 优于原Xw，则新位置取代旧位置;否则，将当前整个种群中适应度值最好的个体Xg替换Xb进行更新. 若更新后仍没改进，则随机产生一个解代替Xw. 在族群内重复此操作，直到设定的迭代次数. 当族群搜索达到指定迭代次数后，所有个体混合并排序，重新划分族群，如此循环直到满足终止条件，最终输出全局最优解为问题的解.

1.2 递进多目标混合蛙跳优化算法

混合蛙跳算法最初是用来解决水资源分配，桥墩维修等工程设计、组合优化问题［3］. 其中，大多数问题实际上是多目标优化问题. 对于多目标问题的求解，遗传多目标算法［4］是最重要的经典多目标算法之一，以非支配排序和拥挤机制为主要特征，其中前者使搜索过程收敛至Pareto 前沿，后者保证Pareto 最优解的多样性. 师瑞峰等［5］针对遗传算法的改进提出了一种递进多目标算法，在进化到一定的代数后，对群体进行重构来提高算法对解空间的遍历性，有效避免算法早熟. 本研究在混合蛙跳算法基础上引入非支配排序和拥挤机制，提出递进多目标混合蛙跳 (escalating multi-objective SFLA，EMO-SFLA)算法.

1.2.1 非支配排序

在递进多目标混合蛙跳中，对每个个体对应多个目标函数值可采用非支配排序［4］(non-dominated sorting)对各个体进行Pareto 分级. 计算每一代群体中个体的各个目标函数值后，对群体进行分级，分成子集P1，P2，…，PS. P 的下标代表该子集中个体的等级，每个子集称为一个前沿，每个前沿上的个体是彼此非支配的. 具体方法为:首先对整个群体，通过比较每个个体的目标函数值与其他个体目标函数值，选出非支配解分配等级1，即P1包含当前种群的所有非支配个体;对剩余个体，按照同样规则选出非支配解，分配等级2，即P2包含只被P1中个体支配的个体，重复此过程，直到所有个体都分配到等级.

1.2.2 外部精英解集及维护

对于多目标问题，各目标之间相互冲突，不存在能够使所有目标同时得到最优化的最优解，这也是多目标优化与单目标优化的本质区别. 通常，多目标优化是产生一组可选的折衷解，称为Pareto 近似最优解，由决策过程在可选解集中做出最终的选择. 在递进多目标混合蛙跳算法中，设置一个外部伴随非支配解集(称为Pareto 外部精英解集)来保存目前所获得的最优解. 假设其规模与进化种群相同，该解集随着进化逐步收敛为算法最终的Pareto近似最优解集. Pareto 外部精英解集的构成遵循以下原则:优先考虑等级低的体;同一等级优先考虑拥挤距离［4］大的个体. 其中，拥挤距离反映了个体间的疏密程度，表示每一个体与同级别相邻两个体间的局部拥挤距离.

为保持Pareto 外部精英解集多样性和有界性，采用改进的小生境淘汰技术［6］来构建和维护Pareto外部精英解集. 当Pareto 外部精英解集没有达到规定的大小N 时，新产生的非劣解直接加入到Pareto解集中. 若Pareto 解集已达到规定的大小N，当新解支配了Pareto 外部解集中的部分成员，可将这些受支配的成员从N 中去掉，并将新解加入到Pareto解集中;否则，先将新解加入Pareto 外部解集中，采用改进小生境淘汰技术使Pareto 外部解集数不超过N. 该过程可描述为:对相同Pareto 等级的个体，按欧式距离公式计算相邻两个个体的距离，当两者差值很小时，说明两个体对应的目标函数值非常靠近. 当距离小于某一个规定值时，计算两者的向量模适应度(即每个向量与原点距离)，比较这两个个体的向量模适应度函数值，对其中较大值对应的个体在下一轮进化中淘汰.

1.2.3 全局最优位置选择

在多目标蛙跳优化算法中，最差个体的更新策略不同于基本蛙跳算法. 这主要体现在全局最优个体选择不再满足唯一性，而是对每个最差个体选择不同的全局最优个体. 选择操作就是在Pareto 外部精英解集中，从满足拥挤距离大于一定阈值的解中随机选择一个作为全局最优解. 这样就降低了稠密区域中的非支配解作为全局最优解的概率，从而保证Pareto 前沿的均匀性.

1.2.4 算法流程

①在可行解目标空间中随机初始化群体N;②根据非支配原则排序，将整个种群分为一系列Pareto 等级，计算个体的拥挤距离;

③按外部精英解集构造策略选择前M1(M1＜N)个非支配解构造Pareto 外部精英解集. 进化后，若M1＞N 时，采用改进小生境淘汰策略，让外部空间最多拥有N 个个体;

④对初始种群采用混合蛙跳算法进行优化，其中个体的适应度值为其各个目标值归一化后的加权平均值;

⑤将外部空间M1个体和按④优化后的N 个个体混合，重新进行非支配排序，计算拥挤距离，按外部精英解集维护中策略选择前N 只青蛙个体进行下一轮进化;

⑥进化一定代数后，保留部分较好的个体，对剩余个体重新初始化个体的解;

⑦所有进化代数完成或满足预设停止条件，输出外部空间的非支配精英解集，算法结束.

2 递进多目标蛙跳优化LSB±K 算法

将递进多目标蛙跳优化算法应用于LSB ±K 隐写优化设计中，在保证隐写安全性的前提下，尽量提高嵌入容量.

2.1 LSB±K 隐写

为扩大嵌入容量，通过对像素进行加减变换，将秘密信息嵌入最低K(K ＞1)个位平面上时，得到LSB±K 隐写. 该算法可描述为:秘密信息取值为［0，2K］内的数，当秘密信息与像素的最低K 位相同时，不作修改;不相同时，则对像素随机加或减一个［0，2K］内的数，使得其最低K 位与秘密信息相同. 其中，加减操作分别为

其中，pc和ps分别为载体像素值和载密像素值;SM为秘密信息的二进制形式;mod()为取余操作.

2.2 可行解定义

在递进多目标混合蛙跳优化LSB ±K 隐写算法中，首先将图像分成互不重叠的子块，在每个子块中采用不同LSB ±K 隐写. 因此，优化算法中的可行解定义为

定义1 设图像I 由m ×n 个互不重叠同样大小的图像子块构成. 对应所有图像子块组成的矩阵A= {aij| aij∈{1，2，3}，0 ＜i ≤m，0 ＜j ≤n}构成优化算法的可行解. aij的取值表示对应图像子块以LSB ± aij进行嵌入.

2.3 优化目标定义

根据隐写算法安全性和容量相互制约的特点设计两个优化目标. 针对LSBM 隐写算法，Ker 等［7］通过计算图像的直方图特征函数质心 (histogram characteristic function center of mass HCF-COM)提出了有效的分析算法. Li 等［8］指出载体图像与载密图像差分图的质心差异更大. 因此，载体图像与载密图像差分图的质心差异可度量隐写图像的安全性.

其中，N = 255.

【证】由文献［7］ 可知，载密图像直方图hs［k］等于载体图像直方图hc［k］与噪声概率密度fΔ［k］的卷积

离散傅立叶变换后，得

离散傅立叶变换后可得

由式(5)和式(9)可得

其中，N = 510.

根据离散的切比雪夫不等式［9］，对于非减序列a =(a0，a1，…，an)，非增序列b = (b0，b1，…，bn)及非负序列p = (p0，p1，…，pn)有

证毕.

3 仿真实验与讨论

实验所用图像为NRCS 图像库［10］中的1 542 幅图像，全部转为灰度图像，裁剪大小为512 ×512.采用递进多目标混合蛙跳优化LSB ±K 隐写对以上图像进行隐写，图像分块大小为64 ×64，则可行解为8 ×8 的整数矩阵A8×8. 种群数为50，族群大小为10，外部精英空间大小为50，子族群局部更新次数为10，整个种群迭代次数为20. 从NRCS 图像库中随机选择一幅图像，在其Parato 前沿解集中分别取容量最大和容量最小值对应的解进行LSB ±K 隐写得到的载密图像的峰值信噪比(peak signal to noise ratio，PSNR)均大于36 dB. 可见，采用递进多目标混合蛙跳优化的LSB ±K 隐写得到的各种嵌入方式均可满足隐写算法安全性中的不可见性要求. 在每幅图像所得到的Pareto 前沿解集中，选择f2最大，即容量最小的可行解进行隐写 (记为SFLALSB1)得到载密图像. 所有图像对应的f2最大值的平均值为0.77，则1/f2= 1.3，表明SFLA-LSB1 隐写容量比LSBM 满嵌时大30%. 此外，在每幅图像所得到的Pareto 前沿解集中，选择最接近f2= 0.5所对应可行解进行隐写(记为SFLA-LSB2)得到载密图像. 则SFLA-LSB2 隐写容量相当于LSB ± 2(记为LSB2)隐写容量.

将SFLA-LSB1、LSBM 隐写和文献［11］中用遗传算法优化二阶统计量的改进LSBM (记为GALSBM)三种隐写算法进行隐写分析比较. 采用Ker等［7］提出的以一维质心和二维质心特征对以上3 种隐写算法进行隐写分析. Fisher 作为分类器，其中400 幅图像作为训练集，其余图象为测试集，所得的接收机操作特征曲线(receiver operating characteristic curve ，ROC 曲线)如图1 (a). 从中可见，SFLA-LSB1 算法与GA-LSBM 算法的AUC (area under ROC curve)值都低于标准的LSBM 隐写算法，说明两种改进的算法均能提高隐写的安全性. 其中，GA-LSBM 的AUC 值最低为0.609 4，其次是SFLA-LSB1，为0.642 8，最大为LSBM，取值为0.762 7. 虽然SFLA-LSB1 比GA-LSBM 的AUC 值高，但其嵌入容量提高了30%. 由于在SFLA-LSB1算法设计中，采用的是文献［7］中的特征变化作为优化目标. 因此，进一步用其他分析算法来验证该隐写算法的抗分析能力，采用Shi 等［12］提取78维特征对以上3 种隐写算法得到载密图像库进行分析，所得ROC 曲线如图1 (b)，可得与图1 (a)类似的分析结果.

图1 不同LSBM 算法的ROC 曲线Fig.1 The ROC curves of three different LSB1 algorithms

对SFLA-LSB2、LSB ±2 和采用文献［11］优化LSB±2 (记为GA-LSB2)三种隐写，分别采用文献［7］和文献［12］进行隐写分析比较. 实验设置与上相同，所得的ROC 曲线分别见图2 (a)和图2 (b). 由图2 可见，SFLA-LSB2 均获得了最低的AUC 值，抗隐写分析能力最强. 图2 (a)表明，SFLA-LSB2 抵抗Ker 分析能力显著提高. 因此，图像进行分块处理，采用多目标优化手段，在不同的块中嵌入不同量的载密信息，这种自适应地嵌入载密方式，可在获得较大嵌入容量的同时，有效提高算法的抗分析能力.

图2 不同LSB2 算法的ROC 曲线Fig.2 The ROC curves of three different LSB2 algorithms

结 语

本研究利用隐写安全性和容量相互制约关系，将隐写过程建模为多目标优化模型. 采用非支配排序、精英保留、群体重构等特点，提出一种递进多目标混合蛙跳优化算法，并将其应用于LSB ±K 隐写优化设计中. 该算法以载体图像与载密图像差分图的直方图特征函数质心差值和隐写容量为两个优化目标，对图像子块的嵌入位数进行优化，在各图像子块中嵌入不同位数的秘密信息，得到基于多目标混合蛙跳优化的LSB ± K 隐写算法. 实验表明，使用该算法得到的隐写图像均可满足不可见性，且在增加嵌入容量同时，可有效提高算法安全性.

/References:

［1］Sharp T. An implementation of key-based digital signal steganography ［C］// Proceedings of the 4th International Workshop on Information Hiding. Pittsburgh (USA):IEEE Press，2001，2137:13-26.

［2］Eusuff M M，Lansey K E. Optimization of water distribution network design using the shuffled frog leaping algorithm ［J］. Journal of Water Sources Planning and Management，2003，129(3):210-225.

［3］Hateme，Emad E，Tarek H，et al. Comparison of two evolutionary algorithms for optimization of bridge deck repairs ［J］. Computer-Aided Civil and Infrastructure Engineering，2006，21:561-572.

［4］Deb K，Pratab A，Agrawal S，et al. A fast and elitist nondominated sorting genetic algorithm for multi-objective optimization:NSGA-II ［J］. IEEE Transcations on Evolutionary Computation，2002，6 (2):182-197.

［5］SHI Rui-feng，ZHOU Hong，TAN Xiao-wei. A multi-objective genetic algorithm based on escalating strategy ［J］.Systems Engineering Theory and Practice，2005，25(12):48-56.(in Chinese)师瑞峰，周 泓，谭小卫. 递进多目标遗传算法［J］. 系统工程理论与实践，2005，25(12):48-56.

［6］ZHAO Liang，JU Gang，LU Jian-hong. An improved genetic algorithm in multi-objective optimization and its application ［J］. Proceedings of the CSEE，2008，28(2):96-102.(in Chinese)赵 亮，雎 刚，吕剑虹. 一种改进的遗传多目标优化算法及其应用［J］. 中国电机工程学报，2008，28(2):96-102.

［7］Ker A D. Steganalysis of lsb matching in grayscale images［J］. IEEE Signal Processing Letters，2005，12(6):441-444.

［8］Li X，Zeng T. Detecting lsb matching by applying calibration technique for difference image ［C］// Proceedings of 10th ACM Workshop on Multimedia and Security. Oxford(UK):ACM Press，2008:133-138.

［9］Mitrinovic D S，Pecaric J E，Fink A M. Classical and New Inequalities in Analysis ［M］. Dordrecht (Netherlands):Kluwer Academic Publishers，1993.

［10］United States Department of Agriculture. Natural resources conservation service photo gallery ［DB/OL］http://photogallery.nrcs.usda.gov，2002.

［11］LIU Guang-jie，ZHANG Zhan. Improved LSB-matching steganography for preserving second-order statistics ［J］.Journal of Multimedia，2010，5(5):458-463.

［12］Xuan G，Shi Y，Gao J，et al. Steganalysis based on multiple features formed by statistical moments of wavelet characteristic functions ［J］. Computer Science，2005，3727:262-265.