基于遞進(jìn)多目標(biāo)蛙跳優(yōu)化的LSB±K 隱寫算法

歐陽春娟，李 霞，李 斌

1)深圳大學(xué)信息工程學(xué)院，深圳518060;2)深圳市現(xiàn)代通信與信息處理重點(diǎn)實(shí)驗(yàn)室，深圳518060

最低有效位匹配［1］(least significant bits matching，LSBM)隱寫，是當(dāng)秘密信息與載體圖像最低有效位不同時(shí)，通過隨機(jī)加減1 方式，有效避免值對現(xiàn)象，增強(qiáng)檢測難度. 該算法安全簡單，因此被廣泛應(yīng)用. 為進(jìn)一步擴(kuò)大嵌入容量，本研究將秘密信息嵌入最低K(K ＞1)個(gè)位平面上，通過像素進(jìn)行加減變換，得到LSB±K 隱寫(其中K 為位數(shù)).然而，安全性和隱藏容量是相互制約的，若對高位平面采用類似策略進(jìn)行數(shù)據(jù)嵌入，在增大嵌入容量的同時(shí)，會(huì)引起安全性的嚴(yán)重下降. 為此，根據(jù)嵌入容量和安全性相互矛盾的關(guān)系，將LSB ±K 隱寫設(shè)計(jì)建模為一個(gè)多目標(biāo)優(yōu)化模型，在保證隱寫安全性的同時(shí)，盡量獲得較大的嵌入容量. 本研究基于非支配排序和分層重構(gòu)等特點(diǎn)設(shè)計(jì)了一種遞進(jìn)多目標(biāo)混合蛙跳優(yōu)化算法，并將其應(yīng)用于LSB ±K 隱寫的優(yōu)化設(shè)計(jì)中. 在優(yōu)化LSB ±K 隱寫中，對圖像進(jìn)行分塊處理，對應(yīng)所有圖像子塊組成的矩陣構(gòu)成優(yōu)化算法的可行解，矩陣元素代表對應(yīng)圖像塊像素的嵌入位數(shù). 以載體圖像與載密圖像差分圖的直方圖特征函數(shù)質(zhì)心差值代表安全性作為一個(gè)優(yōu)化目標(biāo)，另一個(gè)優(yōu)化目標(biāo)為圖像嵌入容量. 選擇Pareto 前沿解集中的解對整幅圖中不同的圖像塊進(jìn)行LSB ±K隱寫得到載密圖像. 實(shí)驗(yàn)結(jié)果表明，采用本研究所提的基于遞進(jìn)多目標(biāo)蛙跳優(yōu)化的LSB ±K 隱寫算法可提供多種滿足安全性和容量平衡的嵌入選擇方案. 在Pareto 解集中，選擇最低嵌入容量的可行解進(jìn)行隱寫，與LSBM 隱寫及單目標(biāo)優(yōu)化LSBM 隱寫相比，在獲得相近抗分析性能下，嵌入容量提高了30%. 與相同容量下的LSB ±2 隱寫及單目標(biāo)優(yōu)化的LSB±2 隱寫相比，具有更強(qiáng)的抗分析能力.

1 多目標(biāo)混合蛙跳優(yōu)化算法

1.1 混合蛙跳算法

2001 年，Eusuff 等［2］提出混合蛙跳算法(shuffled frog leaping algorithm，SFLA). SFLA 將局部搜索和全局信息交換相結(jié)合，具有參數(shù)少、尋優(yōu)能力強(qiáng)等特點(diǎn). SFLA 算法優(yōu)化過程為:初始化種群，P= {X1，X2，…，XF}，按個(gè)體適應(yīng)度值降序排序后，將種群按式(1)平均分配到m 個(gè)族群

每個(gè)族群有n 個(gè)青蛙，F(xiàn) = m × n. 迭代過程中，在每個(gè)族群中依次選擇以下方式不斷更新適應(yīng)度值最差的個(gè)體Xw. 首先，按式(2)更新

其中，Xb為當(dāng)前族群適應(yīng)度值最好的個(gè)體，r ∈［0，1］. 若更新后X'w 優(yōu)于原Xw，則新位置取代舊位置;否則，將當(dāng)前整個(gè)種群中適應(yīng)度值最好的個(gè)體Xg替換Xb進(jìn)行更新. 若更新后仍沒改進(jìn)，則隨機(jī)產(chǎn)生一個(gè)解代替Xw. 在族群內(nèi)重復(fù)此操作，直到設(shè)定的迭代次數(shù). 當(dāng)族群搜索達(dá)到指定迭代次數(shù)后，所有個(gè)體混合并排序，重新劃分族群，如此循環(huán)直到滿足終止條件，最終輸出全局最優(yōu)解為問題的解.

1.2 遞進(jìn)多目標(biāo)混合蛙跳優(yōu)化算法

混合蛙跳算法最初是用來解決水資源分配，橋墩維修等工程設(shè)計(jì)、組合優(yōu)化問題［3］. 其中，大多數(shù)問題實(shí)際上是多目標(biāo)優(yōu)化問題. 對于多目標(biāo)問題的求解，遺傳多目標(biāo)算法［4］是最重要的經(jīng)典多目標(biāo)算法之一，以非支配排序和擁擠機(jī)制為主要特征，其中前者使搜索過程收斂至Pareto 前沿，后者保證Pareto 最優(yōu)解的多樣性. 師瑞峰等［5］針對遺傳算法的改進(jìn)提出了一種遞進(jìn)多目標(biāo)算法，在進(jìn)化到一定的代數(shù)后，對群體進(jìn)行重構(gòu)來提高算法對解空間的遍歷性，有效避免算法早熟. 本研究在混合蛙跳算法基礎(chǔ)上引入非支配排序和擁擠機(jī)制，提出遞進(jìn)多目標(biāo)混合蛙跳 (escalating multi-objective SFLA，EMO-SFLA)算法.

1.2.1 非支配排序

在遞進(jìn)多目標(biāo)混合蛙跳中，對每個(gè)個(gè)體對應(yīng)多個(gè)目標(biāo)函數(shù)值可采用非支配排序［4］(non-dominated sorting)對各個(gè)體進(jìn)行Pareto 分級(jí). 計(jì)算每一代群體中個(gè)體的各個(gè)目標(biāo)函數(shù)值后，對群體進(jìn)行分級(jí)，分成子集P1，P2，…，PS. P 的下標(biāo)代表該子集中個(gè)體的等級(jí)，每個(gè)子集稱為一個(gè)前沿，每個(gè)前沿上的個(gè)體是彼此非支配的. 具體方法為:首先對整個(gè)群體，通過比較每個(gè)個(gè)體的目標(biāo)函數(shù)值與其他個(gè)體目標(biāo)函數(shù)值，選出非支配解分配等級(jí)1，即P1包含當(dāng)前種群的所有非支配個(gè)體;對剩余個(gè)體，按照同樣規(guī)則選出非支配解，分配等級(jí)2，即P2包含只被P1中個(gè)體支配的個(gè)體，重復(fù)此過程，直到所有個(gè)體都分配到等級(jí).

1.2.2 外部精英解集及維護(hù)

對于多目標(biāo)問題，各目標(biāo)之間相互沖突，不存在能夠使所有目標(biāo)同時(shí)得到最優(yōu)化的最優(yōu)解，這也是多目標(biāo)優(yōu)化與單目標(biāo)優(yōu)化的本質(zhì)區(qū)別. 通常，多目標(biāo)優(yōu)化是產(chǎn)生一組可選的折衷解，稱為Pareto 近似最優(yōu)解，由決策過程在可選解集中做出最終的選擇. 在遞進(jìn)多目標(biāo)混合蛙跳算法中，設(shè)置一個(gè)外部伴隨非支配解集(稱為Pareto 外部精英解集)來保存目前所獲得的最優(yōu)解. 假設(shè)其規(guī)模與進(jìn)化種群相同，該解集隨著進(jìn)化逐步收斂為算法最終的Pareto近似最優(yōu)解集. Pareto 外部精英解集的構(gòu)成遵循以下原則:優(yōu)先考慮等級(jí)低的體;同一等級(jí)優(yōu)先考慮擁擠距離［4］大的個(gè)體. 其中，擁擠距離反映了個(gè)體間的疏密程度，表示每一個(gè)體與同級(jí)別相鄰兩個(gè)體間的局部擁擠距離.

為保持Pareto 外部精英解集多樣性和有界性，采用改進(jìn)的小生境淘汰技術(shù)［6］來構(gòu)建和維護(hù)Pareto外部精英解集. 當(dāng)Pareto 外部精英解集沒有達(dá)到規(guī)定的大小N 時(shí)，新產(chǎn)生的非劣解直接加入到Pareto解集中. 若Pareto 解集已達(dá)到規(guī)定的大小N，當(dāng)新解支配了Pareto 外部解集中的部分成員，可將這些受支配的成員從N 中去掉，并將新解加入到Pareto解集中;否則，先將新解加入Pareto 外部解集中，采用改進(jìn)小生境淘汰技術(shù)使Pareto 外部解集數(shù)不超過N. 該過程可描述為:對相同Pareto 等級(jí)的個(gè)體，按歐式距離公式計(jì)算相鄰兩個(gè)個(gè)體的距離，當(dāng)兩者差值很小時(shí)，說明兩個(gè)體對應(yīng)的目標(biāo)函數(shù)值非?？拷? 當(dāng)距離小于某一個(gè)規(guī)定值時(shí)，計(jì)算兩者的向量模適應(yīng)度(即每個(gè)向量與原點(diǎn)距離)，比較這兩個(gè)個(gè)體的向量模適應(yīng)度函數(shù)值，對其中較大值對應(yīng)的個(gè)體在下一輪進(jìn)化中淘汰.

1.2.3 全局最優(yōu)位置選擇

在多目標(biāo)蛙跳優(yōu)化算法中，最差個(gè)體的更新策略不同于基本蛙跳算法. 這主要體現(xiàn)在全局最優(yōu)個(gè)體選擇不再滿足唯一性，而是對每個(gè)最差個(gè)體選擇不同的全局最優(yōu)個(gè)體. 選擇操作就是在Pareto 外部精英解集中，從滿足擁擠距離大于一定閾值的解中隨機(jī)選擇一個(gè)作為全局最優(yōu)解. 這樣就降低了稠密區(qū)域中的非支配解作為全局最優(yōu)解的概率，從而保證Pareto 前沿的均勻性.

1.2.4 算法流程

①在可行解目標(biāo)空間中隨機(jī)初始化群體N;②根據(jù)非支配原則排序，將整個(gè)種群分為一系列Pareto 等級(jí)，計(jì)算個(gè)體的擁擠距離;

③按外部精英解集構(gòu)造策略選擇前M1(M1＜N)個(gè)非支配解構(gòu)造Pareto 外部精英解集. 進(jìn)化后，若M1＞N 時(shí)，采用改進(jìn)小生境淘汰策略，讓外部空間最多擁有N 個(gè)個(gè)體;

④對初始種群采用混合蛙跳算法進(jìn)行優(yōu)化，其中個(gè)體的適應(yīng)度值為其各個(gè)目標(biāo)值歸一化后的加權(quán)平均值;

⑤將外部空間M1個(gè)體和按④優(yōu)化后的N 個(gè)個(gè)體混合，重新進(jìn)行非支配排序，計(jì)算擁擠距離，按外部精英解集維護(hù)中策略選擇前N 只青蛙個(gè)體進(jìn)行下一輪進(jìn)化;

⑥進(jìn)化一定代數(shù)后，保留部分較好的個(gè)體，對剩余個(gè)體重新初始化個(gè)體的解;

⑦所有進(jìn)化代數(shù)完成或滿足預(yù)設(shè)停止條件，輸出外部空間的非支配精英解集，算法結(jié)束.

2 遞進(jìn)多目標(biāo)蛙跳優(yōu)化LSB±K 算法

將遞進(jìn)多目標(biāo)蛙跳優(yōu)化算法應(yīng)用于LSB ±K 隱寫優(yōu)化設(shè)計(jì)中，在保證隱寫安全性的前提下，盡量提高嵌入容量.

2.1 LSB±K 隱寫

為擴(kuò)大嵌入容量，通過對像素進(jìn)行加減變換，將秘密信息嵌入最低K(K ＞1)個(gè)位平面上時(shí)，得到LSB±K 隱寫. 該算法可描述為:秘密信息取值為［0，2K］內(nèi)的數(shù)，當(dāng)秘密信息與像素的最低K 位相同時(shí)，不作修改;不相同時(shí)，則對像素隨機(jī)加或減一個(gè)［0，2K］內(nèi)的數(shù)，使得其最低K 位與秘密信息相同. 其中，加減操作分別為

其中，pc和ps分別為載體像素值和載密像素值;SM為秘密信息的二進(jìn)制形式;mod()為取余操作.

2.2 可行解定義

在遞進(jìn)多目標(biāo)混合蛙跳優(yōu)化LSB ±K 隱寫算法中，首先將圖像分成互不重疊的子塊，在每個(gè)子塊中采用不同LSB ±K 隱寫. 因此，優(yōu)化算法中的可行解定義為

定義1 設(shè)圖像I 由m ×n 個(gè)互不重疊同樣大小的圖像子塊構(gòu)成. 對應(yīng)所有圖像子塊組成的矩陣A= {aij| aij∈{1，2，3}，0 ＜i ≤m，0 ＜j ≤n}構(gòu)成優(yōu)化算法的可行解. aij的取值表示對應(yīng)圖像子塊以LSB ± aij進(jìn)行嵌入.

2.3 優(yōu)化目標(biāo)定義

根據(jù)隱寫算法安全性和容量相互制約的特點(diǎn)設(shè)計(jì)兩個(gè)優(yōu)化目標(biāo). 針對LSBM 隱寫算法，Ker 等［7］通過計(jì)算圖像的直方圖特征函數(shù)質(zhì)心 (histogram characteristic function center of mass HCF-COM)提出了有效的分析算法. Li 等［8］指出載體圖像與載密圖像差分圖的質(zhì)心差異更大. 因此，載體圖像與載密圖像差分圖的質(zhì)心差異可度量隱寫圖像的安全性.

其中，N = 255.

【證】由文獻(xiàn)［7］ 可知，載密圖像直方圖hs［k］等于載體圖像直方圖hc［k］與噪聲概率密度fΔ［k］的卷積

離散傅立葉變換后，得

離散傅立葉變換后可得

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

其中，N = 510.

根據(jù)離散的切比雪夫不等式［9］，對于非減序列a =(a0，a1，…，an)，非增序列b = (b0，b1，…，bn)及非負(fù)序列p = (p0，p1，…，pn)有

證畢.

3 仿真實(shí)驗(yàn)與討論

實(shí)驗(yàn)所用圖像為NRCS 圖像庫［10］中的1 542 幅圖像，全部轉(zhuǎn)為灰度圖像，裁剪大小為512 ×512.采用遞進(jìn)多目標(biāo)混合蛙跳優(yōu)化LSB ±K 隱寫對以上圖像進(jìn)行隱寫，圖像分塊大小為64 ×64，則可行解為8 ×8 的整數(shù)矩陣A8×8. 種群數(shù)為50，族群大小為10，外部精英空間大小為50，子族群局部更新次數(shù)為10，整個(gè)種群迭代次數(shù)為20. 從NRCS 圖像庫中隨機(jī)選擇一幅圖像，在其Parato 前沿解集中分別取容量最大和容量最小值對應(yīng)的解進(jìn)行LSB ±K 隱寫得到的載密圖像的峰值信噪比(peak signal to noise ratio，PSNR)均大于36 dB. 可見，采用遞進(jìn)多目標(biāo)混合蛙跳優(yōu)化的LSB ±K 隱寫得到的各種嵌入方式均可滿足隱寫算法安全性中的不可見性要求. 在每幅圖像所得到的Pareto 前沿解集中，選擇f2最大，即容量最小的可行解進(jìn)行隱寫 (記為SFLALSB1)得到載密圖像. 所有圖像對應(yīng)的f2最大值的平均值為0.77，則1/f2= 1.3，表明SFLA-LSB1 隱寫容量比LSBM 滿嵌時(shí)大30%. 此外，在每幅圖像所得到的Pareto 前沿解集中，選擇最接近f2= 0.5所對應(yīng)可行解進(jìn)行隱寫(記為SFLA-LSB2)得到載密圖像. 則SFLA-LSB2 隱寫容量相當(dāng)于LSB ± 2(記為LSB2)隱寫容量.

將SFLA-LSB1、LSBM 隱寫和文獻(xiàn)［11］中用遺傳算法優(yōu)化二階統(tǒng)計(jì)量的改進(jìn)LSBM (記為GALSBM)三種隱寫算法進(jìn)行隱寫分析比較. 采用Ker等［7］提出的以一維質(zhì)心和二維質(zhì)心特征對以上3 種隱寫算法進(jìn)行隱寫分析. Fisher 作為分類器，其中400 幅圖像作為訓(xùn)練集，其余圖象為測試集，所得的接收機(jī)操作特征曲線(receiver operating characteristic curve ，ROC 曲線)如圖1 (a). 從中可見，SFLA-LSB1 算法與GA-LSBM 算法的AUC (area under ROC curve)值都低于標(biāo)準(zhǔn)的LSBM 隱寫算法，說明兩種改進(jìn)的算法均能提高隱寫的安全性. 其中，GA-LSBM 的AUC 值最低為0.609 4，其次是SFLA-LSB1，為0.642 8，最大為LSBM，取值為0.762 7. 雖然SFLA-LSB1 比GA-LSBM 的AUC 值高，但其嵌入容量提高了30%. 由于在SFLA-LSB1算法設(shè)計(jì)中，采用的是文獻(xiàn)［7］中的特征變化作為優(yōu)化目標(biāo). 因此，進(jìn)一步用其他分析算法來驗(yàn)證該隱寫算法的抗分析能力，采用Shi 等［12］提取78維特征對以上3 種隱寫算法得到載密圖像庫進(jìn)行分析，所得ROC 曲線如圖1 (b)，可得與圖1 (a)類似的分析結(jié)果.

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

對SFLA-LSB2、LSB ±2 和采用文獻(xiàn)［11］優(yōu)化LSB±2 (記為GA-LSB2)三種隱寫，分別采用文獻(xiàn)［7］和文獻(xiàn)［12］進(jìn)行隱寫分析比較. 實(shí)驗(yàn)設(shè)置與上相同，所得的ROC 曲線分別見圖2 (a)和圖2 (b). 由圖2 可見，SFLA-LSB2 均獲得了最低的AUC 值，抗隱寫分析能力最強(qiáng). 圖2 (a)表明，SFLA-LSB2 抵抗Ker 分析能力顯著提高. 因此，圖像進(jìn)行分塊處理，采用多目標(biāo)優(yōu)化手段，在不同的塊中嵌入不同量的載密信息，這種自適應(yīng)地嵌入載密方式，可在獲得較大嵌入容量的同時(shí)，有效提高算法的抗分析能力.

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

結(jié) 語

本研究利用隱寫安全性和容量相互制約關(guān)系，將隱寫過程建模為多目標(biāo)優(yōu)化模型. 采用非支配排序、精英保留、群體重構(gòu)等特點(diǎn)，提出一種遞進(jìn)多目標(biāo)混合蛙跳優(yōu)化算法，并將其應(yīng)用于LSB ±K 隱寫優(yōu)化設(shè)計(jì)中. 該算法以載體圖像與載密圖像差分圖的直方圖特征函數(shù)質(zhì)心差值和隱寫容量為兩個(gè)優(yōu)化目標(biāo)，對圖像子塊的嵌入位數(shù)進(jìn)行優(yōu)化，在各圖像子塊中嵌入不同位數(shù)的秘密信息，得到基于多目標(biāo)混合蛙跳優(yōu)化的LSB ± K 隱寫算法. 實(shí)驗(yàn)表明，使用該算法得到的隱寫圖像均可滿足不可見性，且在增加嵌入容量同時(shí)，可有效提高算法安全性.

/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)師瑞峰，周 泓，譚小衛(wèi). 遞進(jìn)多目標(biāo)遺傳算法［J］. 系統(tǒng)工程理論與實(shí)踐，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ìn)的遺傳多目標(biāo)優(yōu)化算法及其應(yīng)用［J］. 中國電機(jī)工程學(xué)報(bào)，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，F(xiàn)ink 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.