基于模運算的并行隱寫算法

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

(廣西財經學院 計算機科學系，廣西 南寧 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混沌系統序列作為密鑰，密鑰空間足夠大，算法獲得了更好的抵御隱寫分析能力的特性和更高的安全性。