基于改進FEMD算法的可逆秘密圖像共享方案

馬利民，王佳慧

（1. 北京信息科技大學計算機學院，北京 100101；2. 國家信息中心信息與網絡安全部，北京 100045）

1 引言

網絡技術的高速發展對于數據傳輸具有重要意義，然而如何保證秘密數據在網絡上的傳輸安全已成為一個亟待解決的問題。秘密圖像共享技術可以將需要安全存放及傳輸的秘密圖像按照一定方法進行劃分并分別交給不同管理人。假設目標秘密圖像被劃分為n個圖像，只有同時擁有其中的t(2≤t≤n)個劃分圖像時，才能恢復出秘密圖像，防止秘密過于集中，達到一定的安全性；另一方面，如果有劃分圖像丟失或者損壞，只要剩余的劃分圖像個數大于或等于t，仍然可以恢復秘密圖像，因此該技術對安全風險具有一定的容忍性。隱寫術是信息隱藏技術的一種，用于實現數字內容在網絡中的安全存放及傳輸[1-2]。基于隱寫術的秘密圖像共享將n個共享圖像嵌入n個載體圖像當中，生成n個含密圖像，通過傳輸含密圖像達到安全傳輸秘密圖像的目的。

Shamir[3]首次提出了基于拉格朗日多項式內插原理實現的秘密共享技術，又稱為(t,n)-門限秘密共享技術。Thien等[4]基于(t,n)-門限秘密共享技術提出了秘密圖像共享的概念，其中，秘密圖像中的每一個像素作為一個秘密信息，與文獻[3]不同，他們將(t-1)次多項式的每一個系數均用于攜帶秘密信息，因此生成的每一個劃分圖像的大小是原始秘密圖像大小的此后的一些秘密圖像共享方案大都是為了減小生成的劃分圖像而設計的，如文獻[5-6]。Wang等[5]提出將哈夫曼編碼應用于秘密圖像的差分圖像編碼以減少劃分圖像。Lin等[6]提出了一種基于隱寫術的秘密圖像共享方案，將產生的噪聲隱藏在多幅載體圖像中。基于文獻[6]提出的算法框架，后續研究人員提出了許多基于隱寫技術的秘密圖像共享方案[7-13]。其中，Amir等[7]利用 OAEP（optimal asymmetric encryption padding）和 IDA（information dispersal algorithm）進一步提高了共享秘密圖像的密鑰的安全性，并采用 FEMD（fully exploiting modification direction）隱寫算法提高了隱寫圖像質量。Jamal等[8]通過在共享圖像時利用細胞自動機技術來替代上述基于拉格朗日多項式內插原理實現的秘密共享技術，取得了更好的隱寫圖像質量。上述算法性能較好，但存在的共同問題是載體圖像不可恢復，假如載體圖像是一些敏感圖像（例如軍事圖像、醫學圖像），考慮到載體圖像的實用價值，應盡量避免這種情況發生。因此，可逆的秘密圖像共享技術更具有實用性。

可逆秘密圖像共享方法設計過程中，需要考慮載體圖像的恢復，因此在秘密共享階段，需要將載體圖像的一些特征信息連同秘密圖像一起生成含密圖像。這樣就可以在秘密圖像恢復階段，利用載體圖像特征信息恢復載體圖像。對于此類算法，一方面，特征信息提取越少生成的劃分圖像越小，嵌入載體圖像后生成的含密圖像質量越高；另一方面，隱寫術算法性能的優劣也將決定含密圖像的質量。因此，基于隱寫術的秘密共享算法需要同時注重這兩方面的因素。Lin等[14]提出一種基于模運算的可逆秘密圖像共享機制，該機制利用（t-1）次多項式的t系數中的■logm255■個系數來攜帶載體圖像中像素的值，剩余的系數則用來攜帶秘密數據。隨后，Lin等[15]又提出一種能提高嵌入秘密數據量的改進方案，但是這2種方案都需要解決溢出問題[16]。Feng等[17]基于(t,n)-門限秘密共享技術提出一種可逆的主動式秘密圖像共享方案，可以實現對生命周期較長的秘密圖像進行安全保護，但是生成的含密圖像質量有待提高。Liu等[18]提出一種針對 H.264的可逆數據共享方案，通過在空間域嵌入秘密信息，但是嵌入數據量較小。

目前，基于隱寫術的可逆秘密圖像生成的含密圖像質量不高，本文針對此問題提出了一種高質量的基于隱寫術的可逆秘密圖像共享算法，并通過實驗進行分析比較。實驗結果表明，本文提出的算法可以生成高質量的含密圖像，同時可以無損恢復載體圖像，在保證秘密圖像安全存放的同時增強了其在網絡傳輸的安全性。

2 相關工作

2.1 秘密共享技術

1979年，Shamir[3]首先提出(t,n)-門限秘密共享技術，該技術基于拉格朗日多項式內插原理實現[19-20]。如果要保護的秘密為s，則采用(t,n)-門限秘密共享方法進行秘密共享，具體實現步驟如下。

1) 根據式(1)生成一個(t-1)次多項式。

其中，t≥2，GF (p)是一個有限域，p是一個素數或者p=2m，a0=s，a1,a2, …,at-1是隨機選擇且分布在[0,p-1]范圍內的整數。

2) 根據n個參與者選定的密鑰X={x1,x2, …,xi,…,xn}生成n個劃分y1,y2, …,yi,…,yn。

其中，n≥t。將yi交由對應的參與者進行保管。

恢復秘密信息s時，需隨機選擇t個劃分，即y1,y2, …,yt，基于拉格朗日多項式內插方法重建多項式F(x)，如式(2)所示，其常數項系數即是秘密信息s的值。

2.2 FEMD算法

在基于隱寫術實現可逆秘密圖像共享方案中，特征提取方法和隱寫算法是決定含密圖像質量好壞的關鍵因素。Kieu等[21]給出了一種很好的隱寫算法——FEMD算法，但是由于嵌入過程中存在多對一的映射關系及溢出像素問題，該算法無法實現載體圖像的恢復。

FEMD算法的基本思想是將一個s2進制數嵌入一個像素對(ai,ai+1)中，嵌入過程中對ai或者ai+1的最大改變量為其中 0 ≤a,a≤ 255。當ii+1s值固定時，算法的最大嵌入量為因此s值越大，最大嵌入量越大，但嵌入失真也就越大。基于FEMD算法將s2進制系統中的一個數d嵌入像素對(ai,ai+1)中得到含密像素對(bi,bi+1)，具體步驟如下。

步驟1 定義提取函數F(xi,xi+1)如式(3)所示。

步驟2 建立一個256×256的映射矩陣M，如式(4)所示。

步驟3 根據式(3)計算(ai,ai+1)的提取函數值F(ai,ai+1)。

步驟4 若F(ai,ai+1) =d，(bi,bi+1)= (ai,ai+1)，嵌入結束；否則執行步驟5。

步驟5 在映射矩陣M中定義一個以(ai,ai+1)為中心的方形搜索框W，如式(5)所示。

步驟6 掃描搜索框中的每一個元素，使M[p][q]=d。若滿足條件的像素對(p,q)不止一個，則選擇具有最小嵌入失真D的像素對賦值給(bi,bi+1)，其中，D根據式(6)進行計算。

在提取端，根據參數s來定義提取函數F(xi,xi+1)，s需要通過一種安全保密的方式傳遞給提取端。假設提取端接收到的像素對為 (bi′,bi′+1)，則嵌入的秘密數據d′ =F(bi′,bi′+1)。

通過研究 FEMD算法發現，對于大部分像素對，可以通過將原始像素對的提取函數值作為秘密信息嵌入含密像素對中恢復原始像素對的值。但是對于有些像素對則不可恢復，本文稱之為問題像素對。問題像素對可以分為2類，第一類是由嵌入秘密信息時可以對應不同含密像素對的問題像素對組成；第二類是由溢出像素對構成，所謂溢出像素對是指像素對中至少有一個像素的值落在區間[0,r)∪(255-r, 255]。

對于第一類問題像素對，其嵌入過程是一個一對多的映射，例如當s=4時，所建立的映射矩陣M如圖1所示。選擇的像素對(ai,ai+1) = (4, 5)，淺灰色矩形框為根據式(5)構建的方形搜索框W，深灰色標注位置為所要嵌入的秘密數據d=11，按照FEMD算法嵌入數據后得到的含密像素對的值為(bi,bi+1)=(5, 3)或者(bi,bi+1)=(5, 7)，此時無法通過FEMD算法將F(ai,ai+1) 的值嵌入(bi,bi+1)中來恢復(ai,ai+1)的值。對于第二類問題像素對，即溢出像素對，采用FEMD算法在一個像素對(ai,ai+1)中嵌入秘密數據時，可能無法從搜索框W(s,(ai,ai+1),r)中找到一個元素等于所要嵌入的秘密數據。因此，FEMD算法在一個載體圖像中嵌入秘密數據之前，將位于區間[0,r) 和 (255-r, 255]的所有數據作為溢出像素，分別用r和255-r來替換，然后在修改后的像素中嵌入秘密信息。這樣對溢出像素對的修改過程是一個多對一的映射，因此根據修改后數值無法知曉原始溢出像素的值。

圖1 當s=4時FEMD算法中構建的映射矩陣M

FEMD算法作為一種隱寫術算法，實現了較高的嵌入量和較好的含密圖像質量，此后 Kuo等[22]對其進行了改進，提出一種新的隱寫術算法，在秘密數據嵌入載體像素時，利用數學式計算含密像素。Kuo等[23]提出一種基于 FFEMD（formula FEMD）算法和像素值差分辦法來克服溢出問題。這些算法大多只是改進隱寫術的性能而沒有在秘密共享方面進行設計。

3 可逆秘密圖像共享算法的設計

3.1 改進FEMD算法

針對 FEMD算法處理過程中遇到的問題像素對，本文從嵌入過程和溢出像素對處理兩方面解決像素對的可逆性恢復問題。

3.1.1 改進的FEMD算法嵌入過程

在采用FEMD算法嵌入秘密數據時，需按照一定方向遍歷搜索框，使原始像素對和嵌入后含密像素對成為一對一的映射。對FEMD算法嵌入過程的步驟6改進如下。

步驟6按照圖2 (a)中所示方向遍歷搜索框，嵌入過程為自左至右，掃描到最右邊后從下一行最左側開始繼續遍歷，直到找到滿足條件M[p][q]=d且具有最小嵌入失真D的像素對(p,q)，如果這樣的像素對不止一對，則將最先掃描到的像素對賦值給(bi,bi+1)。

在使用改進 FEMD算法進行秘密信息嵌入后，利用提取函數F(ai,ai+1)和s就可以從含密像素對(bi,bi+1)中恢復原始像素對(ai,ai+1)。但恢復時需按圖 2(b)中所示方向進行遍歷，與嵌入時掃描方向相反。

圖2 掃描方向

3.1.2 溢出像素對處理

為每一個溢出像素對分配一個溢出標志位 sf來記錄其原始狀態，然后分別用r和255-r替換溢出像素對的值。為了唯一地恢復原始像素對的值，本文在對溢出像素對(ai,ai+1)設計溢出標志位sf時，分為2種情況進行處理。

1)ai和ai+1的值都屬于區間

2) 像素對中只有一個數位于區間[0,r]∪[255-r, 255]

如果一個溢出像素對(Rj,Rj+1)經上述方法處理后，像素對為 (R′j,R′j+1)，溢出標志位為sf，那么根據(R′j,R′j+1)和sf可以通過下面的方法恢復(Rj,Rj+1)。

1) 若R′j,R′j+1∈{r,255 -r}，(Rj,Rj+1)可以根據式(9)計算得到。

2) 若Rj′和R′j+1中只有一個數等于r或者255-r，為解釋方便，本文將等于r或者 255-r的數據表示為X′，另一個數據表示為Y′，其相應的原始像素的值分別表示為X和Y，那么Y= Y′，X可以根據式(10)計算得到。

通過上述對溢出像素對的處理方法可以實現基于改進的 FEMD算法來恢復原始溢出像素對的值，實現載體圖像的無損恢復。

3.2 秘密圖像共享及嵌入

在本文提出的方法中，用一幅灰度圖像作為載體圖像，利用(t,n)-門限秘密共享技術來生成共享劃分，最后基于改進FEMD算法將生成的共享劃分單獨地嵌入一幅載體圖像中形成n個含密圖像。為了恢復原始載體圖像的值，提取端需要知道載體圖像的所有像素對的特征值。對于載體圖像的每個像素對，根據式(1)構建(t-1)次多項式時，需要根據3.1節提出的算法，利用一個或 2個系數存儲該像素對的特征值，用剩余的系數來攜帶來自于秘密圖像的秘密信息。在實現方案中，采用基于 2m的有限域GF (2α)來構建(t-1)次多項式，為此需要將秘密圖像中的每個像素采用 2α進制數來表示。對于參數為s的改進FEMD算法，其可嵌入的秘密數據的數值落在[0,s2)，為了兼容，采取的有限域GF (2α)算法中要求2α=s2，因此本文中α=s=2或者α=s=4。

假設秘密圖像I大小為hs×ws，宿主載體圖像C大小為hc×wc，n個參與者所對應的n個互不相同的密鑰表示為X={x1,x2, …,xn}，則基于改進的FEMD可逆秘密圖像共享方案的共享及嵌入流程如圖3所示，算法過程如下。

1) 將I中的數據重新排列為一維矢量

圖3 可逆秘密圖像共享及嵌入流程

2) 將S中的每一個像素用進制數表示 ， 進 而 形 成 一 個 矢 量S′ ={d1,d2,… ,dl,… ,其中，

3) 順序化遍歷C中的每一個像素，將相鄰 2個像素作為一個像素對(ci,ci+1)。

4) 若(ci,ci+1)是溢出像素對，按照式(7)或式(8)計算溢出標志位sf，然后利用式(3)計算經溢出過程處理后的修改像素對的提取函數值f；否則，直接計算(ci,ci+1)的提取函數值f。

5) 若(ci,ci+1)是溢出像素對，從S′中順序選擇(t-2)個連續的 2α進制數，形成劃分片段否則，從S′中順序選擇(t-1)個數據，形成劃分片段

6) 若(ci,ci+1)是溢出像素對，利用f、sf和(dsj, dsj, … , d sj)構建式(11)。

1 2t-2

否則，構建式(12)。

7) 將n個密鑰xk分別代入Fj(x)中得到Fj(xk)，其中，k∈[1,n]。

8) 對于每個Fj(xk)，k∈[1,n]，基于改進FEMD算法單獨嵌入(ci,ci+1)中得到含密圖像 SIk中對應的含密像素對。

9) 重復執行步驟 3)～步驟 8)，直到S′中的所有數據處理完畢。

10) 至此，若載體圖像中尚有剩余像素對沒有嵌入數據，則直接將剩余的像素對復制到含密圖像SIk的對應位置。

經過上面的處理，可以得到n個大小為hc×wc的含密圖像SIk，k=1, 2, …,n，這n個含密圖像將由相應的參與者保管。另外，由于提取端需要知道秘密圖像大小hs×ws和參數s才能恢復出秘密圖像和載體圖像，這2個信息將作為算法的私鑰通過一種安全的方式發送給提取端。

3.3 秘密圖像提取和載體圖像恢復

根據(t,n)-門限秘密共享技術原理，恢復出共享的秘密圖像至少需要t個不同的含密圖像，假設所提供的含密圖像是SI1,SI2, …, SIt，對應的參與者所擁有的密鑰分別是x1,x2, …,xt，則提取端進行秘密圖像提取和原始載體圖像恢復的過程如下。

1) 對于每個含密圖像SIi，i=1, 2, …,t，順序選擇 2個相鄰的像素作為一個像素對根據式(3)計算其提取函數值fi。

2) 根據步驟1)得到的t組數據(xi,fi)，i=1, 2, …,t，來重建多項式F(x)，如式(13)所示，其中α=s。

3) 根據共享過程可知，a0所承載的信息就是原始載體圖像對應像素對（或修改后溢出像素對）的提取函數值，因此根據的值，利用3.1節中給出的原始像素對恢復方法即可得到之前像素對的值，這里用來表示。根據a0和的值以及恢復算法計算得到

4) 通過以下步驟提取秘密圖像和恢復載體圖像中像素對(Rj,Rj+1)的值。

① 如果R′j和R′j+1都不等于r或者 255-r，則說明宿主載體中的原始像素對不是溢出像素對，此時(Rj,Rj+1)的值等于 (R′j,R′j+1)的值。因此，重建多項式F(x)中系數(a1,a2, …,at-1)均承載的是秘密數據。

② 如果R′j和R′j+1之間至少有一個等于r或者255-r，則說明宿主載體中的原始像素對是溢出像素對。根據嵌入過程可知，系數a1所承載的是溢出標志位的信息，其他系數(a2,a3, …,at-1)承載的是秘密信息。這時可以根據溢出標志位a1和 (R′j,R′j+1)的值來恢復原始像素對(Rj,Rj+1)的值。

5) 重復執行步驟 1)～步驟 4)，直至所提取出的秘密數據個數為然后將含密圖像SI1中的剩余像素直接賦值給載體圖像中的相應位置處，即可恢復宿主載體圖像。

4 實驗結果及分析

首先，為了分析所提算法對不同載體圖像進行處理后得到的含密圖像的質量，在模擬實驗中本文使用10幅512像素×512像素的灰度圖像作為作載體圖像來測試算法性能，根據有限域GF (2α)算法中要求 2α=s2，改進 FEMD 算法中的參數s=α=4。對于本文算法來說，可供嵌入的秘密圖像的最大尺寸為實驗中選取的秘密圖像是300像素×300像素的圖像，如圖4所示，因此需設置實驗參數為t=3，n=3。對于基于隱寫術實現秘密圖像共享的算法，生成的含密圖像失真越小，在網絡中傳輸時越不易被攻擊者察覺，安全性越好。本文用PSNR（peak signal to noise ratio）指標來衡量得到的含密圖像質量。

圖4 秘密圖像（300像素×300像素）

表 1為 10幅圖像作為載體圖像使用改進的FEMD算法得到含密圖像的PSNR結果。此外，圖5展示了Lena圖像作為載體圖像時得到的3幅含密圖像。從表1及圖5可以看出，在以上實驗條件下，嵌入的秘密圖像大小為300像素×300像素，本文提出的改進FEMD算法可以取得高達48 dB的含密圖像質量，同時肉眼無法看出含密圖像與原始載體圖像的差別，因此所提算法具有良好的不可見性。

其次，為了進一步比較分析算法性能，將本文算法與文獻[15-17]算法進行比較。其中，為使對比算法可以取得最好的結果，并保持相同的實驗條件，即嵌入的秘密圖像為 300像素×300像素的圖像，在實現文獻[15]算法時將其參數m設置為3，將文獻[16]算法中參數α設置為2，將文獻[17]算法中參數設置為t=7，m=3。表2是實驗數據對比，就含密圖像質量來說，本文算法相比文獻[15]、文獻[16]和文獻[17]中算法可以分別實現 6.4 dB、2.8 dB和0.57 dB的性能提高。

表1 含密圖像質量

圖5 含密圖像質量評估

對于本文算法，當t=3，s=4時，采用本文算法共享和嵌入一個 8 bit數據在一個像素上所引入的誤差可以通過式(14)計算得到，為1.375。采用文獻[15]算法和文獻[16]算法，實現一個8 bit數據的共享和嵌入時，在載體圖像的一個像素上引入的誤差可以分別通過式(15)和式(16)來計算，當t=3，m=3，α=2時，引入的誤差分別為 5和 2.5。因此本文算法得到的含密圖像質量比較好。本文算法可以為秘密圖像的安全存放和傳輸提供一種很好的一體化解決方案。

表2 算法性能比較

5 結束語

本文重點分析了基于隱寫術的可逆秘密圖像共享方案，提出了一種基于改進FEMD算法的可逆秘密圖像共享算法。作為一種隱寫算法，由于嵌入過程及在對溢出像素處理時的不唯一性，FEMD算法無法實現可逆秘密圖像共享方案設計。本文從嵌入過程和對溢出像素對處理兩方面來改進 FEMD算法，并利用改進的FEMD算法設計了一種基于隱寫術的可逆秘密圖像共享方案。實驗結果表明，本文提出的算法可以生成高質量的含密圖像，在保證秘密圖像安全存放的同時增強了其在網絡傳輸的安全性，具有較高的實用性。