一種基于塊分類和差值擴展的可逆數據隱藏算法

宋 偉 ，侯建軍，李趙紅

(1. 北京交通大學 電子信息工程學院，北京，100044；2. 中央民族大學 信息工程學院，北京，100081)

可逆數據隱藏利用可逆變換將數據嵌入宿主圖像中，在接收端利用逆變換提取出所嵌入的數據信息并恢復原始圖像，最早由Honsinger等[1]于2001年提出，到目前為止大致可分為3類算法：基于差值擴展的算法(Difference expansion, DE)，基于預測誤差的算法(Prediction error, PE)和基于直方圖平移的算法(Histogram shifted, HS)。差值擴展算法由Tian[2]提出，通過可逆整數變換對像素對差值進行擴展嵌入數據，算法簡單，其理論嵌入比特率為0.5 bit/像素。基于該算法，出現了很多新算法[3-7]。Alattar[3]用向量進行差值擴展，如將 3個相鄰像素作為1個向量嵌入2 bit信息，理論嵌入比特率為2/3 bit/像素，提高了數據嵌入比特率，但圖像質量也隨之下降較快。該類算法大多通過行掃描或者列掃描進行嵌入，沒有考慮行列之間的區別。Hu等[4]利用整數小波變換，通過閾值選擇水平或豎直2個方向進行嵌入。Hsiao等[5]通過方差預測圖像塊的類型，且進行多方向嵌入，同時采用LSB替代法(Least significant bit substitution method)嵌入輔助信息。Lou等[6]將對數函數引入，提出了一種RDE(Reduced DE)可逆水印算法，減小了數據嵌入對圖像造成的失真，但位圖信息較大。基于預測誤差的數據隱藏算法[8-12]通過預測機制預測目標像素，通過平移誤差嵌入數據。常用的預測器有水平預測器、垂直預測器、Causal SVF和 Causal WA 預測器[9]等。Hong等[10]改進了 MED(Median edge detection)，提出了MPE(Modified PE)算法，提高了數據的嵌入容量，然而，其數據嵌入量受到了圖像內容的限制，只能在嵌入預測誤差為-1和0的目標像素中嵌入數據。Weng等[11]提出了PEA (PE adjustment)預測器將差值擴展和預測誤差結合起來，有效地提高了嵌入數據后的圖像的質量。基于直方圖平移的數據隱藏算法[13-16]通過零點(Zero points)和峰點(Peak point)平移直方圖，為數據嵌入提供一定的冗余空間。Lin等[14]將圖像的差值直方圖代替原始宿主圖像的直方圖，可產生更多的峰點和零點，并利用多層嵌入策略提高數據嵌入容量。該類方法依賴直方圖峰點和零點的數量，數據嵌入容量受到限制。圖像由于紋理不同存在平坦和非平坦的區域，平坦區域應該相應地多嵌入數據，而在復雜區域嵌入數據將會造成較大失真；因此，選擇一種合適的方式對圖像塊的類型進行判斷，從而嵌入不同量的數據，理論上能夠提高嵌入數據后圖像的質量。另外，傳統的算法對圖像進行單向數據嵌入，即逐行進行嵌入或者逐列進行嵌入，沒有考慮圖像行列間的關系，也影響了圖像的質量。為此，本文作者基于圖像內容利用圖像塊嵌入數據前、后均值間的統計特性，設計圖像塊類型判斷準則和數據嵌入方向判斷準則，實現了多容量和多方向的嵌入，提高了數據的嵌入容量和嵌入數據后圖像的質量。

1 像素對擴展差及向量擴展差

1.1 基于像素對的差值擴展

像素對擴展差的具體過程如下：設原始像素對(u1,u2)為(200, 205)，在數據嵌入過程中，首先計算像素對的均值l和差值d：

修改后的像素12(,)uu′′為：

在數據提取過程中，已嵌入數據的像素對12(,)uu′′被選擇用來計算均值l和差值d?：

數據b利用最低有效位(LSB)進行提取：

通過如下方程計算得到原始差值d：

同時，恢復原始像素12(, )uu ：

1.2 基于向量的2 bit差值擴展

假設原始像素(u1, u2, u3)為(202, 200, 205)，數據嵌入時，均值d1以及差值d2和d3經計算得到：

其中：a1, a2和a3為權重，這里賦值為1。設嵌入數據為b1b2=10，則通過如下方式嵌入：

則嵌入的數據b1和b2提取方式為：

原始均值d1以及差值d2和d3通過如下恢復：

則原始的像素(u1, u2, u3)為：

1.3 基于向量的4 bit差值擴展

假設原始像素(u1, u2, u3)為(202, 200, 205)數據嵌入時，差值d2和d3以及均值d1為：

假設嵌入數據為b1b2b3b4=1 101，則通過如下差值擴展嵌入數據：

提取過程中，計算均值1d?以及差值2d?和3d?：

則提取所嵌入的數據b1b2和b3b4為：

均值d1以及和差值d2和d3經計算得到：

則原始的像素(u1, u2, u3)為：

2 圖像塊分類的差值擴展算法

2.1 數據嵌入算法

數據嵌入過程如圖1所示。該算法為基于向量的差值擴展嵌入算法，包括圖像區域劃分，數據嵌入過程和輔助信息嵌入過程，圖像塊類型判定準則和圖像塊嵌入方向判定準則。具體過程如下。

步驟 1 將圖像分為數據嵌入區域和輔助信息嵌入區域；

圖1 數據嵌入過程圖Fig.1 Data embedding procedure

步驟 2 在數據嵌入區域，利用判斷準則判斷目標圖像塊的類型和目標圖像塊的嵌入方向。

步驟 3 對不同目標圖像塊按嵌入方向嵌入不同比特的數據。若嵌入數據后的像素發生溢出，則不嵌入數據，同時記錄位圖信息。

步驟4 對位置信息圖和2個閾值利用算術編碼進行壓縮。

步驟5 利用MPE將壓縮后位圖信息的長度，數據嵌入輔助信息區域。

步驟 6 發送圖像塊均值差值信息，得到嵌入數據后的圖像。

2.1.1 圖像區域劃分和數據嵌入方向

圖像被劃分為2個區域:數據嵌入區域和輔助信息嵌入區域(圖 2)。輔助信息嵌入區域上半部分高度為3+mod(m, 3)，下半部高度為 3，左半部分寬度為3+mod(n, 3)和右半部分寬度為3(其中m和n分別為原始圖像的高度和寬度)。

傳統的數據嵌入過程都是在數據嵌入區域通過掃描的方式進行數據嵌入，如在嵌入階段通過從上到下、從左到右的方式，則在數據提取過程中，首先計算數據嵌入的長度，然后，按照嵌入過程相反的方向對數據進行提取，即從下到上、從右到左。利用圖像塊間的均值關系對目標圖像塊進行預測，數據的嵌入和提取可以采用同樣的方向，即不必利用數據的長短計算數據提取時的起始位置，然后，采用和數據嵌入相反的方向提取嵌入的數據。該算法利用光柵掃描的方式在數據嵌入區域按照從左向右、從上至下的方式嵌入和提取(圖2)。

2.1.2 均值判斷圖像塊類型的有效性

圖3所示為原始宿主圖像和由圖像塊均值構成的圖像。由圖3可知：視覺上的均值圖像的大小比原始宿主圖像的小，但較好地保留了原始圖像的紋理信息和復雜程度，因此，利用均值預測圖像塊的紋理情況具有一定的理論基礎。

圖2 圖像劃分區域和數據嵌入方向圖Fig.2 Image divided area and data embedded direction

圖3 均值判斷圖像塊類型的有效性Fig.3 Validity of block’s type decided by mean value

對原始宿主圖像(圖3(a))進行分塊，并計算各圖像塊的方差和均值。部分相鄰圖像塊的方差和對應圖像塊的均值如表1所示。方差反映了周圍像素值偏離中心像素的程度，方差越大表明紋理越復雜，從而不利于嵌入數據。方差較大的圖像塊(如方差為6 360的圖像塊)對應的均值(126)和周圍圖像塊的均值相差也較大而對于方差較小的圖像塊(如方差為6)，對應圖像塊和周圍圖像塊的均值差也較小。因此，比較目標像素塊和周圍圖像塊均值差值與選取閾值的關系，可以判斷不同圖像塊的紋理復雜程度，從而嵌入不同的數據。

表1 圖像塊的方差和對應圖像塊的均值Table1 Variation and mean value of image block

2.1.3 圖像塊類型判斷準則

圖像塊由于紋理復雜度的不同應嵌入不同的數據。算法將目標圖像塊(Block0: Target Block)的均值和周圍相鄰圖像塊(Block1，Block2，Block3，Block4)(圖4)的均值進行比較，將目標圖像塊分為平滑塊(Smooth Block)、一般塊(Normal Block)和復雜塊(Complex Block)。對于復雜塊，數據的嵌入會引起圖像的較大失真，因此，不嵌入任何數據。對于一般塊，利用1.2節中2 bit差值擴展算法嵌入數據；對于平滑塊，利用1.3節中4 bit差值擴展算法嵌入數據。這樣，使得增加數據嵌入比特流的同時，盡可能減小數據嵌入對圖像帶來的失真。具體分析見圖5。

圖4 圖像塊和像素Fig.4 Image blocks and pixels

圖5 圖像塊類型判斷Fig.5 Classification of image blocks

目標圖像塊3種類型具體判定準則如下：

2.1.4 圖像塊嵌入方向判斷準則

傳統的差值擴展算法進行單一的逐行或逐列嵌入，沒有充分利用行列之間的關系。該算法利用像素塊間的關系，設計了目標圖像塊的嵌入方向即水平方向和豎直方向判斷準則(圖6)。

圖6 目標圖像塊嵌入方向Fig.6 Embedding direction of target block

目標圖像塊嵌入方向具體判定準則如下：

2.1.5 位圖信息與閾值處理方式

對于數據嵌入過程中產生的位圖和對圖像塊類型判斷所用的閾值，需要在數據提取過程中能夠通過數據的提取自動獲取，因此，算法采用壓縮編碼對該部分數據進行壓縮，其數據結構構成圖如圖7所示，壓縮后的輔助信息數據結構圖如圖8所示。在數據提取過程中，輔助信息提取后，按照數據結構圖，提取編碼后的長度，然后，利用壓縮編碼結構圖提取2個閾值和位置圖信息。

圖7 壓縮編碼結構圖Fig.7 Structure of compression coding

圖8 輔助信息數據結構圖Fig.8 Structure of auxiliary information data

2.1.6 輔助信息MPE嵌入方式

對于輔助信息的位置圖，大多采用和數據嵌入相同的方式進行嵌入，這樣，嵌入的結果是嵌入數據后仍然產生新的位置圖，只有通過多次比較和計算才能嵌入輔助信息，使得算法計算量增大，數據處理時間變長。理論上，只要有新的數據需要嵌入，就會產生新的位圖信息，因此，需要尋找新的輔助信息嵌入方法。

MPE[10]對MED進行了改進，利用預測誤差進行數據的嵌入(式(22))，使得嵌入數據后幾乎沒有數據溢出，因此，本文選擇MPE算法嵌入輔助信息。

其中：xi為圖4中被選取的原始像素；ix′為嵌入位置圖信息后的像素。

實驗過程中選取大小為 512×512的不同紋理特征的灰度圖像作為宿主圖像(圖 9)，分別為標準圖像Lena，Plane，Couple，Milk-drop，Peppers，Baboon，Boats和圖像Bridge。

表2所示為8副測試圖像(圖9)輔助信息區域可用像素的數量和利用 MPE嵌入數據后產生位圖信息的情況。由表2可知：可用像素數量大，且嵌入后的位圖信息為 0，表明無新位圖信息產生，不需采用多次嵌入，多次比較嵌入輔助數據[5]。

表2 輔助信息區域可用像素及位圖信息Table2 Amount of useable pixels and location map

2.2 數據提取算法

數據提取過程與數據嵌入過程相似，具體過程見圖10。

步驟 1 將圖像分為數據提取區域和輔助信息區域。

步驟2 查找輔助信息區域可用像素，利用MPE提取嵌入數據，并恢復輔助信息區域像素。

步驟3 利用算術編碼解碼算法對MPE提取出的數據進行解壓縮，利用壓縮編碼結構圖分解出閾值和位置信息圖。

步驟 4 利用輔助信息和圖像塊均值差值信息對數據提取區域圖像塊類型和方向進行判斷，提取出目標圖像塊所含的數據，并恢復原始圖像塊的像素。

步驟 5 執行上述步驟，直到所有目標圖像塊檢測完成為止，得到嵌入的數據和原始宿主圖像。

圖9 測試圖像Fig.9 Test images

圖10 數據提取過程圖Fig.10 Data extraction procedure

3 實驗結果及分析

3.1 算法性能衡量標準

可逆數據隱藏算法的性能評價標準通常通過數據嵌入比特率和嵌入數據后圖像的視覺質量來衡量，將兩者有效結合稱為綜合性能指標。前者通過計算數據嵌入容量和圖像大小的比值進行衡量，后者通過峰值信噪比(PSNR，Peak signal-noise ratio)來判定水印的不可見性這一重要特性。

3.2 算法綜合性能測試

圖11和圖12所示為8副測試圖像(圖9)的綜合性能測試結果。從圖11可以看出：對于紋理較為簡單的圖像Plane，由于其像素塊間的差值較小，使用較小的閾值就可以將圖像塊分成不同的類型，同時，在輔助信息嵌入區域，平滑的區域能夠產生較多的嵌入信息可用像素，因此，嵌入比特率較高，圖像質量較好。對于 Milk-drop圖像同樣存在這些特性，在該圖像的上部分由于存在一定的紋理特征，在嵌入同樣比特率條件下，圖像的質量較 Plane的低，但當嵌入比特率超過0.5時，圖像質量高于Plane圖像的質量。這表明該算法充分利用了圖像的紋理特征，將圖像的內容特性考慮在數據嵌入的過程當中。對于圖像Lena，其紋理較Plane和Milk-drop圖像的紋理復雜，因此，其綜合性能指標圖大部分在Plane和Milk-drop的下方。對于圖像Couple，其復雜的圖像內容使得圖像塊類型的控制不如前3幅圖像容易，嵌入數據后對圖像造成的失真較前3幅圖像的大，其性能指標與其他圖像相比較差。但當圖像嵌入容量為 0.7 bit/像素時，圖像的PSNR仍然高于30 dB，滿足容量和圖像質量的要求。

圖12所示的4副測試圖像的綜合性能更進一步地驗證了上述的論述。Boats，Peppers，Bridge和Baboon復雜度逐漸增大，同時，Boats的綜合性能較好，與其他曲線相比位于圖像的上方。其次是 Peppers關系曲線圖，位于Boats的下方；最下面的是紋理最為復雜的Baboon圖，在嵌入比特率相同時，Boats的PSNR比Baboon的PSNR高達10 dB。這充分表明該算法利用均值控制圖像塊的類型和方向進行數據的嵌入具有一定的有效性和適用性。

圖11 Lena, Couple, Milk drop和Plane的綜合性能測試Fig.11 Performance test of Lena, Couple, Milk drop and plane

圖12 Peppers, Baboon, Boats和Bridge的綜合性能測試Fig.12 Performance test of Peppers, Baboon, Boats and Bridge

3.3 算法綜合性能對比測試

為了更進一步測試算法的有效性，實驗將該算法和優秀的算法Tian的差值擴展算法(DE)[2]與Thodi的預測誤差數據嵌入算法(PE)[8]進行對比。圖 13～15所示為3種算法在不同紋理圖像Baboon，Peppers和圖像Lena的綜合性能對比關系圖。

從圖 13可以看出：對于紋理較為復雜的圖像Baboon，圖像的質量隨著嵌入數據量的增多下降較快，在比特率較低時，利用該算法嵌入數據后圖像的PSNR比Tian的DE算法嵌入數據后圖像的PSNR高達5 dB，比Thodi的PE算法嵌入數據后圖像的PSNR高達7 dB，表現出了良好的性能；但隨著嵌入數量的增多，復雜的紋理對圖像的質量影響越來越嚴重，但其PSNR仍比DE和PE的高。

對于圖像Peppers(圖14)，圖像良好的局部平滑特性使得不同的圖像塊根據圖像塊類型判斷準則被很好地區分，從而嵌入數據后對圖像造成的失真較小；在不同的嵌入比特率下，該算法的綜合性能曲線一直在基于DE和基于PE的綜合性能曲線上方，該算法的PSNR比同比特率時DE算法的PSNR高達5 dB，比基于PE的PSNR高達8 dB?？梢姡涸撍惴▽τ陬愃芇eppers的局部圖像特征較為明顯的圖像，其綜合性能明顯高于DE算法和PE算法的綜合性能。

圖15所示為基于Lena圖像的綜合性能對比測試曲線圖。圖像在高嵌入比特率下的質量較高，其PSNR在嵌入比特率高達1 bit/像素時仍高于30 dB；當嵌入數據較少時，該算法的PSNR高于DE和PE的PSNR，當嵌入比特率高于0.6 bit/像素時，Thodi的算法所得的PSNR略高于該算法所得的PSNR。因為高嵌入比特率條件下，位于圖像下方較為復雜的紋理圖像使得圖像塊嵌入數據后產生了的較多數據溢出，該部分圖像塊的不嵌入數據必須通過增大閾值從而增多平滑圖的數量進行平衡，從而在一定程度上影響了嵌入數據后圖像的質量。但從圖15可以看出：該算法的PSNR一直高于Tian的算法的PSNR。因此，該算法對于各種類型的圖像都比較適用。

圖13 基于Baboon圖像的綜合性能對比測試Fig.13 Capacity vs. distortion comparison on Baboon

圖14 基于Peppers圖像的綜合性能對比測試Fig.14 Capacity vs. distortion comparison on Peppers

圖15 基于Lena圖像的綜合性能對比測試Fig.15 Capacity vs. distortion comparison on Lena

4 結論

(1) 分析了利用圖像塊間均值關系判斷圖像塊類型的可行性，設計了圖像塊類型判斷準則；根據不同類型嵌入不同數據量的信息，解決了單一嵌入容量易給載體圖像造成較大失真的問題。

(2) 設計了圖像塊數據嵌入方向判斷準則，達到了根據圖像紋理信息多方向嵌入數據的目的。

(3) 將差分擴展算法和預測誤差算法相結合，有效地提高了圖像的可嵌入比特率和嵌入數據后圖像的質量。

(4) 下一步研究重點是研究壓縮域下的可逆信息隱藏算法和設計，以便有效地減少輔助信息。

[1] Honsinger C W, Jones P, Rabbani M, et al. Lossless recovery of an original image containing embedded data: US 6278791[P].2001-08-21.

[2] TIAN Jun. Reversible data embedding using a difference expansion[J]. IEEE Trans on Circuits and Systems for Video Technology, 2003, 13(8): 890-896.

[3] Alattar A M. Reversible watermark using the difference expansion of a generalized integer transform[J]. IEEE Trans on Image Processing, 2004, 13(8): 1147-1156.

[4] HU Yong-jian, Lee H K, CHEN Kai-ying, et al. Difference expansion based reversible data hiding using two embedding direction[J]. IEEE Trans on Multimedia, 2008, 10(8):1500-1512.

[5] Hsiao J Y, CHAN K F, CHANG J M. Block-based reversible data embedding[J]. Signal Processing, 2009, 89(4): 556-569.

[6] Lou D C, Hu M C, Liu J L. Multiple layer data hiding scheme for medical images[J]. Computer Standards & Interfaces, 2009,31(2): 329-335.

[7] Hu Y J, Lee H K, Li J W. DE-based reversible data hiding with improved overflow location map[J]. IEEE Trans on Circuits and Systems for Video Technology, 2009, 19(2): 250-260.

[8] Thodi M, Rodriguez J J. Prediction error-based reversible watermarking[C]// Proc IEEE ICIP2004. International Conference on Image Processing, Singapore: IEEE, 2004:1549-1552.

[9] Tseng H W, Hsieh C P. Prediction-based reversible data hiding[J].Information Sciences, 2009, 179(14): 2460-2469.

[10] Hong W, Chen T S, Shiu C W. Reversible data hiding for high quality images using modification of prediction errors[J]. The Journal of System and Software, 2009, 82(11): 1833-1842.

[11] WENG Shao-wei, ZHAO Yao, NI Rong-rong, et al. Lossless data hiding based on prediction-error adjustment[J]. Sci China Ser F-Inf Sci, 2009, 52(2): 269-275.

[12] Wu H C, Lee C C, Tsai C S, et al. A high capacity reversible data hiding scheme with edge prediction and difference expansion[J].Journal of Systems and Software, 2009, 82(12): 1966-1973.

[13] Chung K L, HUANG Yong-huai, YANG Wei-ning, et al.Capacity maximization for reversible data hiding based on dynamic programming approach[J]. Applied Mathematics and Computation, 2009, 208(1): 284-292.

[14] LIN Chia-chen, TAI Wei-liang, Chang C C. Multilevel reversible data hiding based on histogram modification of difference images[J]. Pattern Recognition, 2008, 41(12): 3582-359.

[15] Tsai P Y, Hu Y C, Yeh H L. Reversible image hiding scheme using predictive coding and histogram shifting[J]. Signal Processing, 2009, 89(6): 1129-1143.

[16] NI Zhi-cheng, SHI Yun-qing, Ansari N, et al. Reversible data hiding[J]. IEEE Trans on Circuits and Systems for Video Technology, 2006, 16(3): 354-362.