基于二叉樹標記與碼分復用的密文域圖像可逆信息隱藏

劉蒙蒙，張敏情，周 能，柯 彥

(武警工程大學密碼工程學院，西安 710086)

密文域圖像可逆信息隱藏(reversible data hiding in encrypted images, RDHEI)是將秘密信息嵌入經過加密的圖像，之后仍然可以無差錯提取秘密信息并無損恢復出原始圖像的技術[1-3]。RDHEI作為密碼技術與信息隱藏的交叉融合技術，能夠實現數據隱私保護與秘密信息傳遞的雙重功能。

RDHEI從生成并利用冗余的角度來歸納主要分為3種框架：加密前生成冗余(vacating room before encryption, VRBE)的密文域可逆信息隱藏、加密后生成冗余(vacating room after encryption, VRAE)的密文域可逆信息隱藏和加密過程中生成冗余(vacating room in encryption, VRIE)的密文域可逆信息隱藏。VRBE框架中產生可嵌入冗余的操作主要是在明文域進行，該操作通常是作為加密前的預處理過程中完成[4-5]；VRAE框架下生成可控冗余主要在密文域實現，嵌入操作實施在加密后的密文上，能夠保持原加密過程的安全性[6-7]。張敏情等[8]提出的VRIE框架實現了在加密過程生成冗余，此框架利用加密算法的特有性質，保證了嵌入算法的可逆性與安全性。但是由于加密數據的特殊性，如數據相關性極小，分布趨于均勻分布，可嵌入位置受加密與壓縮技術限制較大，使得當前該技術在保證明文恢復的可逆性、保證加密安全性、信息提取與圖像恢復可分離、提高嵌入容量、魯棒性等方面存在著許多需要研究解決的難題。

為了解決上述問題，Yi等[9]提出一種VRAE可分離的密文域可逆信息隱藏算法，利用圖像分塊內的局部相關性和參數二叉樹標記方案將秘密信息嵌入加密圖像中；Wu等[10]在Yi等方法的基礎上，提出了一種優化的二叉樹標記(improved parametric binary tree labeling, IPBTL)的密文域可逆信息隱藏算法，這是一種VRBE可分離的密文域可逆信息隱藏算法。IPBTL算法首先通過中值預測器[11](median edge detection, MED)的方法保留了原始圖像的空間冗余性。圖像經過加密后再采用參數二叉樹標記(parametric binary tree labeling, PBTL)的方法，將加密后的像素點進行類別，在滿足相應條件的像素上嵌入秘密消息。并較好地利用了整幅原始圖像的空間冗余性從而有效提高了嵌入容量。

在Yi等[9]和Wu等[10]方法的基礎上，提出了碼分復用與二叉樹標記(code division multiplexing and parametric binary tree labeling, CDMPBTL)的密文域可逆信息隱藏方案，首先利用精確梯度選擇預測[12](accurate gradient selective prediction, AGSP)的方法精準地預測出像素，可以更加充分地利用整幅自然圖像的空間冗余性，在圖像加密后使用PBTL的方法將像素點分類，并在相應像素上嵌入秘密消息，最后利用碼分復用(code division multiplexing, CDM)的方法嵌入輔助信息，提高嵌入率及有效載荷的利用率，增強算法的安全性。

1 相關技術

1.1 參數二叉樹標記方案

參數二叉樹標記的方案可以將圖像中的像素點標記成兩個大類，分別記為G1、G2，G1、G2是用完美二叉樹的結構特性進行選取的。對于一個8位的像素，需要用7層的完美二叉樹來表示。在完美二叉樹中第i層有2i個節點其中i=1,2,…,7。分別選定α、β個比特標記G1和G2中的像素點，其中1≤α,β≤7。如圖1所示。

圖1 完全二叉樹中二進制編碼分布

對于G2，使用相同的β位‘0’比特進行標記，且為前β個比特位。對于G1，可分成nα個不同的子類，nα的大小由α和β共同決定，其計算公式為

(1)

式(1)中：α表示標記可嵌入點所用編碼位數；β表示標記不可嵌入點所用編碼位數；nα表示標記可嵌入點的編碼空間。當α≤β時，在第α層，用從右到左的2α-1個節點把G1標記成nα個子類。當α>β，在第α層，用從右到左的(2β-1)2α-β個節點把G1標記成nα個子類。圖2說明當β=1,2,3；α=1,2,…,7時標記的二進制編碼是如何選擇的。

圖2 舉例說明當β=1, 2, 3且α=1, 2,…,7時的標記位

1.2 碼分復用

CDM是一種廣泛應用于通信系統的多址接入技術，用于信息安全傳輸和信道多路復用[13]。在基于CDM的通信系統中，發送方通過一個特定的傳輸序列將所要傳輸的信息進行編碼，只有接收方獲取相同的傳輸序列才能準確地解碼消息內容。通常傳輸序列由Walsh Hadamard矩陣產生，該矩陣滿足以下要求。

每個傳輸序列為L=(li)1×m滿足條件:

(2)

式(2)中:li表示序列中的元素，任意兩個不同的傳輸序列滿足條件：

(3)

式(3)中:Ls和Lr分別表示兩個不同的傳輸序列，在通信過程中，每個發送者使用自己的傳輸序列L代表發送比特“1”，用傳輸序列的反碼-L代表發送比特“0”。不同的發送者可以在同一信道同一時刻向基站發送信息。

例如現有兩個發送者A和B，其被分配的傳輸序列分別為L1=(1,-1,1,-1)和L2=(1,1,-1,-1)。在發送端，發送者A發送比特“1”信號，用L1表示；發送者B發送比特“0”信號，用-L2表示。在接收端基站收到的混合信號L=L1+(-L2)=(0,-2,+2,0)。利用式(4)基站判斷發送者A發送的信號為

(4)

通過該判定規則，A發送的信號為“1”。

利用式(5)判斷發送者 B 發送的信號為

(5)

通過該判定規則，B發送的信號為“0”。

CDM利用發送者之間傳輸序列的正交特性，接收方對接收到的混合序列通過不同的傳輸序列分別進行解碼，發送者之間的通信互不影響。信息隱藏的過程與CDM的通信過程類似，秘密信息相當于傳輸的信號，嵌入序列相當于傳輸序列，載體圖像相當于傳輸信道，多個秘密信息經過不同的嵌入序列可以同時在載體圖像這個信道上傳輸。利用不同傳輸序列相互正交的特性對圖像進行信息隱藏，在進行多層信息比特嵌入的過程中可以部分抵消對像素點造成的失真，擁有較高的嵌入容量和峰值信噪比。

2 本文算法

2.1 算法框架

現提出一種基于參數二叉樹標記與碼分復用的密文域可逆信息隱藏方案，該方案主要由三個階段組成：①圖像預處理；②信息嵌入；③信息提取與圖像恢復。在第一階段中，內容所有者，通過檢測原始明文圖像的預測誤差，并使用加密密鑰對原始明文圖像進行加密；然后，使用PBTL對加密后的圖像進行標記生成帶有標記的加密圖像。在第二階段，在PBTL標記的可嵌入點，嵌入經過嵌入密鑰加密后的秘密消息，之后使用CDM的方法嵌入輔助信息。從而生成了帶標記攜密的密文圖像。在第三階段，在接收方提取出輔助信息后，僅擁有嵌入密鑰的可以準確地提取秘密消息，僅擁有加密密鑰的發送者可以利用空間相關性無損地恢復出原始圖像。二者順序可以相互交換。僅當同時使用這兩個密鑰時，才可以無損地恢復原始圖像和提取秘密信息。圖3為CDMPBTL-RDHEI方法的框架。

圖3 CDMPBTL-RDHEI算法框架

2.2 算法過程

2.2.1 圖像預處理

圖像預處理分成四個步驟：計算預測誤差、圖像加密、像素分組、通過PBTL的方法對像素進行標記。

(1)計算預測誤差。采用文獻[12]的AGSP算法預測像素值，并計算預測值與像素的差值。設原始灰度圖像I的大小為H×W,I(i,j)表示圖像的像素(0≤I(i,j)≤255, 1≤i≤H, 1≤j≤W)，當3≤i≤H,且3≤j≤W-1時I(i,j)的預測值為I′(i,j)，其余像素點不進行預測。圖4所示的灰色區域為可預測區域，其余為不可預測區域。

圖4 圖像的可預測區域

利用AGSP計算當前像素的4個方向梯度，使用最小的兩個梯度及對應的像素得到預測值。設X為待預測像素，n、w、nw、ne、ww、nn、nne、nnw和nww為X的相鄰像素，其關系如圖5所示。

圖5 待預測像素X及其相鄰像素

I(i,j)的水平方向、垂直方向、對角(45°和135°)方向的對應的梯度分別為D1、D2、D3和D4，Dmin和Dmin1為其中最小的兩個梯度值，且Dmin和Dmin1對應的像素分別為Cmin和Cmin1,則預測值I′(i,j)可通過式(6)求出。

(6)

求出I(i,j)的預測值I′(i,j)后，計算預測誤差Ie利用式(7)求出。具體過程如圖6所示。

Ie=I(i,j)-I′(i,j)

(7)

(2)圖像加密。得到預測誤差后將圖像的可預測點用Ie代替，并使用流密碼加密方式其密鑰為Kd對替代后的圖像進行加密處理得到密文圖像。圖7為圖6(a)的加密圖像。

圖6 預測像素誤差

圖7 加密后的像素值

(3)像素分類。如圖8所示，將所有像素分成四類，分別為參考像素pr、特殊像素ps、可嵌入像素pe、不可嵌入像素pn。pr為每幅圖像的不包括第一個像素的第1、2行，第1、2、W列其他像素為參考像素，在數據嵌入時其值保持不變。ps為每幅圖像的第一個像素用來存儲參數α和β。其余的像素點根據是否滿足式(8)區分為pe和pn。

圖8 像素分類

(8)

式(8)中：nα由式(1)得出。

(4)利用PBTL標記像素。在整幅圖像中pr與ps是固定的，利用PBTL的方法標記pe和pn。通過給定的參數α和β，對所有的pn用β位‘0’進行標記，剩余(8-β)位保持不變。對所有的pe根據Ie分成nα個種類，利用并利用α位的編碼進行標記。剩余的(8-α)位用來嵌入秘密信息。由于在高α位嵌入會泄露明文相關的統計特性，因此采用低α位逆序嵌入，為提高載體的實際嵌入容量采用碼分復用的方式將輔助信息進行嵌入，同時也對低α進行隨機處理進一步提高了算法的安全性。

2.2.2 嵌入過程

首先需要將參數α和β嵌入ps中，由于1≤α,β≤7，ps的高、低四位足夠存儲α和β。同時對于每一個pn都有β位的輔助信息需要記錄。因此輔助信息則由原始圖像ps中8位信息和被取代的每個pn中β位信息共同構成。

每個pe都通過α位的編碼進行標記，因此還有(8-α)位可以嵌入消息。由此可以得出通過PBTL的方法可以空余出(8-β)ne位用于嵌入秘密信息，其中ne表示可嵌入點的個數；同時也會產生(8+β)nn位的輔助信息需要嵌入，nn表示可嵌入點的個數，輔助信息通過碼分復用的方式多重嵌入到已嵌入秘密信息的密文圖像中。在增加實際嵌入容量的同時，置亂低α的統計特征。為了保證消息的安全秘密消息經過密鑰Kd加密后再進行嵌入。舉例說明當α=3和β=2時如圖9所示。

圖9 像素標記與信息嵌入過程當α=3，β=2時

如圖9(a)所示，當預測誤差為2、1、0、-1、-2、-3時分別用‘111’‘110’‘101’‘100’‘011’和‘010’用來標記pe，‘00’用來標記pn。圖9(b)是圖7的8位二進制表示，圖9(c)是利用二叉樹標記后的密文圖像，其中ps的高四位嵌入α，低四位嵌入β，pe用圖9(a)的6種標記從低3位逆序進行標記，pn用‘00’在低2位標記。圖9(d)表示在每個pe像素的高5位嵌入秘密消息生成含秘密消息二叉樹標記后的密文圖像。圖9(e)在嵌入秘密信息的密文圖像上利用碼分復用的方法嵌入輔助信息。碼分復用的嵌入方法如下。

步驟1 將嵌入秘密信息的加密圖像劃分成2×2的互不重疊的像素塊，根據所需嵌入的層數選取k個長度為4的輔助信息嵌入密鑰組成嵌入序列：

Qj=[q1,q2,q3,q4],qi∈{1,-1};1≤i≤k

(9)

且兩兩之間相互正交。

步驟2 嵌入秘密信息前要對秘密信息進行變換，將秘密信息中的比特 0 變換成-1，以便于嵌入 即對E=[e1,e2,…,en](ej表示比特位地值,ej∈{0,1},1≤j≤n)進行變換，得：

e′j=2ej-1

(10)

變換后，得：

E′={e′1,e′2,…,e′j},e′j∈{-1,1}

(11)

步驟3 根據需要選取合適的增益因子θ。

(12)

步驟5 按照像素塊嵌入的順序將載密塊恢復為原來的順序，生成嵌入輔助信息的加密圖像。

從圖像第一個像素塊到最后一個像素塊嵌入一層后，用同樣的方法嵌入下一層，直至輔助信息全部嵌入。在不滿足嵌入條件時嵌入偽比特的策略，使得整個嵌入過程不必考慮記錄不滿足嵌入條件的點。進行多層嵌入的目的是增大嵌入容量，如果最大嵌入容量都不能嵌入全部輔助信息，則此階段僅隨機0、1比特改變統計特性。通過實驗結果分析當圖像大小為512×512時輔助信息小于13 000 bit，才進行嵌入，否則輔助信息作為秘密消息嵌入到圖像中。

2.2.3 消息提取與圖像恢復

在接收端，在使用碼分復用提取過輔助信息后，僅使用隱藏密鑰kd可以在嵌入秘密消息的密文圖像中提取出秘密信息。僅使用加密密鑰ke可以對原始圖像進行恢復。根據使用者權限可以相應獲得原始圖像、秘密信息或者同時可以得到兩者。

(1)輔助信息提取。首先將利用碼分復用方法嵌入的輔助信息提取出來。具體過程如下。

步驟1 對接收到的圖像進行大小為2×2不重疊的分塊。

步驟2 對輔助信息密鑰進行整理，得到提取序列Qj，如式(13)所示：

Qj=[q1,q2,q3,q4],qi∈{1,-1};1≤i≤k

(13)

步驟3 從第k層到第1層進行提取。

(14)

步驟4 提取信息為E′=[e′1,e′2,…,e′3],其中：e′i∈{0,1}。對秘密信息進行處理，得到修改后的秘密信息為E=[e1,e2,…,en]，其中ei∈{0,1}，1≤i≤n。即可得到嵌入秘密信息后的加密圖像。

(2)消息提取。在得到了已經提取出輔助信息的嵌入信息的加密圖像后，首先在第一個像素ps中提取參數α和β，然后在可預測區域中通過檢查標記位的值找出pe和pn。提取順序提取每個pe中的(8-α)秘密消息。并通過kd解密得到明文秘密消息。

(3)圖像恢復。在得到了已經提取出輔助信息的嵌入信息的加密圖像后，得到了每個pn中β位原始圖像信息和ps中的α和β。將β位原始圖像信息填充到原始位置，通過加密密鑰ke解密可以恢復出每個pn像素的明文信息，pr可以通過加密密鑰ke直接解密。每個pe像素通過其α標記位得到預測誤差與相應預測值結合可以恢復出每個pe像素的明文信息。

由于秘密信息提取與圖像恢復的過程是可以交換的，秘密信息通過嵌入密鑰kd解密后可以完全提取，原始圖像通過加密密鑰ke解密后可以無損恢復。故這個過程秘密信息提取與圖像恢復相互獨立且可分離的。

3 實驗及分析

實驗中使用MATLAB R2015b進行仿真，主機配置為CPU IntelCore i7-6700HQ 2.60 GHz，內存8 GB，操作系統Windows 10。所有實驗數據均來自 MATLAB仿真結果，實驗圖像采用USC-SIPI圖像庫中512×512的8 bit灰度圖像Lena、Baboon、Man、Jetplane(圖10)表示仿真實驗所用測試圖像。

圖10 測試圖像

實驗中使用比特(bit)作為嵌入信息的單位，在密文域可逆信息隱藏中使用結構相似性指標(structural similarity index measurement，SSIM)如式(15)所示和峰值信噪比(peak signal-to-noise ratio，PSNR)如式(16)所示，用于衡量嵌入秘密消息后密文圖像的安全性。

(15)

(16)

如圖11所示，以圖像Lena為例，圖11(a)表示原始圖像，經過編碼加密之后嵌入信息得到圖11(b)表示嵌入秘密信息的加密圖像；而圖11(c)表示PBTL標記的加密圖像；圖11(d)表示嵌入秘密信息的加密圖像；圖11(e)表示嵌入輔助信息的加密圖像；圖11(f)表示提取輔助信息與秘密信息之后的解密圖像，圖11(g)表示圖11(a)與圖11(f)兩者完全一致。

圖11 算法處理的不同階段

3.1 性能與安全性分析

所提出的CDMPBTL-RDHEI算法通過在測試圖像Lena、Baboon、Man、Plane(圖10)得出表1～表3，當β∈[2,4]和α∈[2,5]時，該算法的最大嵌入容量。從表1可以看出，當α過小時，空余空間小于輔助信息時將不能嵌入秘密消息用“—”表示，α、β的選取影響著嵌入像素點的個數以及每個可嵌入像素的可嵌入位數，圖像的光滑程度影響著預測算法的準確度，越光滑的圖像預測效果越好，嵌入容量越高，反之亦然。當β=4 和α=4時，圖像Plane達到最大嵌入容量3.473 bpp。

表1 當β=2 和α=2、3、4、5時，測試圖像的嵌入容量

表2 當β=3和α =2、3、4、5時，測試圖像的嵌入容量

表3 當β=4 和α =2、3、4、5時，測試圖像的嵌入容量

表4～表7分別為比較加密后的圖像、PBTL標記后的圖像、嵌入秘密消息后的圖像以及嵌入輔助信息之后的圖像與原始圖像的PSNR與SSIM的實驗結果。由表4～表7可知，每個版本的加密圖像的PSNR值都較低，且SSIM接近0，表明沒有有效信息泄露，證明所提出的CDMPBTL-RDHEI算法安全地保護了原始圖像的隱私，沒有降低圖像加密的安全性。

表4 當β=2和α=5時，加密圖像的PSNR與SSIM

表5 當β=2和α=5時，標記后加密圖像的PSNR與SSIM

表6 當β=2和α=5時，嵌入秘密消息圖像的PSNR與SSIM

表7 當β=2和α=5時，嵌入輔助信息圖像的PSNR與SSIM

3.2 相關算法對比與分析

通過對比提出的CDMPBTL-RDHEI算法與幾種最新的高容量可逆信息隱藏算法。本文算法與文獻[10]將參數α和β分別設置成5和2，此時文獻[10]可以取得最佳嵌入容量。為對比文獻[9]與文獻[14]的最佳嵌入容量，將文獻[9]圖像分塊大小為3×3且參數α和β也設置成5和2，文獻[14]定長碼設置為3，圖像分塊大小為4×4。

如圖12所示，在測試圖像中的最大嵌入容量，本文算法總體上優于文獻[9,10,14]的表現。

圖12 對比三種最新算法在測試圖像中嵌入容量

4 結論

結合CDM與AGSP技術提出了一種基于二叉樹標記的密文域可逆信息隱藏算法，利用AGSP預測方法改進了預測精度，增加了可嵌入點數量，提高了嵌入容量，運用CDM技術將嵌入輔助信息在進一步增加嵌入容量的同時改善圖像的統計特性。實驗證明，該方法具有較高嵌入容量，在無干擾的情況下實現了圖像的完全可逆，下一步的工作中需要解決圖像的嵌入容量受限于預測精確度的問題，從而進一步提高算法隱藏信息的嵌入率，通過改進算法的嵌入方法提高其魯棒性使其具有更強的抵抗分析的能力。