基于分塊自適應壓縮感知的可逆水印算法

張秋余 孫 媛 晏 燕

(蘭州理工大學計算機與通信學院 蘭州 730050)

1 引言

近年來，在醫學診斷、軍事圖像和遙感圖像處理等數據準確性要求較高的應用領域中，國內外學者進行深入研究，提出了可逆水印技術。該算法除具備傳統數字水印特點外，還可在水印系統接收端無失真地恢復原始載體圖像信號。該技術通常需要滿足一些技術要求[1]，如不可見性、高容量、安全性等。

可逆水印最早出現在 1999年柯達公司的一項美國專利[2]中，利用求模的嵌入方法在圖像中嵌入數據，使得提取算法在恢復嵌入數據的同時，還能夠完全得到原始圖像，但該方法嵌入容量較小。一般來說，可逆水印算法的性能評估主要體現在嵌入容量和不可見性。鑒于此，國內外學者提出一系列算法。如基于直方圖平移算法[3-5]，基于壓縮技術的算法[6]，基于整數變換的算法[7-10]。然而，對于單嵌入過程的算法，很少有嵌入率達到1.0 bpp。為提高可逆水印算法的嵌入容量，文獻[11]在文獻[12]的基礎上提出一種高容量可逆水印算法，當采用“Lena”圖像為載體時，其嵌入率達到了1.7 bpp。文獻[13]提出多種可逆水印算法以提高水印嵌入容量。文獻[14]在此基礎上改進了文獻[13]提出的利用奇偶特性、和值不變特性和差值調節的可逆水印方案。但是，這些算法大多數具有高嵌入容量而失真大的特點，不利于可逆水印算法的實際應用。

針對上述問題，本文提出一種基于分塊的高容量自適應壓縮感知可逆水印算法(BACS-RWA)。將載體圖像分成互不重疊的小塊，利用周圍塊與目標塊統計特性判斷目標塊類型，將這些塊分成3類：光滑塊集合 、普通塊集合、復雜塊集合。復雜塊不嵌入水印以增強不可見性，光滑塊和普通塊進行壓縮感知后，自適應地壓縮感知嵌入水印從而提高水印嵌入容量。

2 相關理論知識

2.1 采用分塊思想的優勢

現有可逆圖像水印算法中，水印嵌入階段大多是把整幅圖作為處理對象，進行統一操作，該類算法主要存在兩點不足：一方面，在自然圖像中，局部區域的特征與整幅圖表現出的特征常有不同，在利用整幅圖的特征確定相關參數時局部特征常被忽略掉，而從整幅圖的特征得到的可逆圖像水印嵌入參數、灰度溢出控制參數等并不能保證適用于局部區域的最佳參數；另一方面，不同圖像區域水印嵌入能力會有差別，全圖統一處理的方式沒有充分利用這種特性，通常是不加區分地統一對待不同特性的區域。

采用基于圖像分塊思想的可逆水印算法，通過操作對象區域化，各區域操作相互獨立，可以改善以上采用全圖統一操作不足，增加可逆圖像水印算法的性能。

2.2 塊類型的劃分

首先將載體圖像進行分塊，并計算各圖像塊方差和均值。本文通過目標圖像塊與其周圍圖像塊差值與預設閾值的關系，判斷不同圖像塊紋理復雜程度，從而嵌入不同數據。預設兩個閾值 TH1, TH2(TH1≥TH2)，圖像塊分布如圖 1所示，再通過周圍塊的方差對目標塊進行判定其是平滑塊、普通塊、復雜塊。整個過程見圖2，其判定方法如下：

圖1 目標塊與相鄰塊分布

情況 1((V1≤TH2)&&(V2≤TH2)&&(V3≤TH2)&&(V4≤TH2))：塊 0(目標塊)判為平滑塊。其中V1, V2, V3, V4分別表示塊1，塊2，塊3，塊4的方差值。

情況 2(V1, V2, V3, V4中至少有一個大于TH2，且小于TH1)：塊0 判為普通塊。

情況 3((V1≥TH1)&&(V2≥TH1)&&(V3≥TH1)&&(V4≥TH1))：塊0 判為復雜塊。

圖2 塊類型劃分過程

2.3 基于分塊的壓縮感知

Candés和 Donoho于2006年正式提出了壓縮感知(Compressed Sensing, CS)的概念，該理論突破了經典香農定理的瓶頸。其核心思想是將壓縮與采樣合并進行，首先采集信號的非自適應線性投影(測量值)，然后根據相應重構算法由測量值重構原始信號。優點在于信號的投影測量數據量遠遠小于傳統采樣方法所獲的數據量，使得高分辨率信號的采集成為可能。

大尺度整幅圖像采樣時，現有 CS方法存在計算復雜度高、存儲壓縮采樣算子所需存儲器規模大、重建時間長等問題，采用基于分塊的壓縮采樣方法則能夠實現較好的性能折中[15]。

首先將Ir×Ic維圖像X分成大小為B×B的小塊，xi為第i個塊的向量信號，i=1,…,n,n=N/B2,n為塊數，N為像素數且滿足N=nr×nc；然后對每個塊采用相同的壓縮采樣算子，得到每個圖像塊的測量值向量yi，即

在分塊CS算法中僅需存儲ΦB，而不需存儲整幅圖像的測量矩陣Φ。采用l2范數意義下的優化問題求解，則每個塊的重構過程可表示為如式(3)：

式(4)中λ2是權重系數，在數據一致性與稀疏性之間進行權衡。本文在正交小波基下進行稀疏化，高斯矩陣作為測量矩陣，采用非線性共軛梯度算法和帶回溯線搜索進行優化目標的重構[16]。

2.4 整數變換

其中n,k是兩個整數且n≥1,k＞1,α(x)是個可逆整數函數，定義如下：

整數逆變換：

式(7)中x,y分別代表給定像素塊的原始值和嵌入水印后的值，w代表嵌入的信息。

2.5 自適應整數變換

式(5)中基于整數變換的嵌入失真可以表示為式(8)的形式。

為避免數據溢出，設B={x=(x0,x1,…,xn)∈Zn:0≤xi≤255}是大小為n+1所有灰度圖像的像素值數組，其子集為

因此，自適應整數變換過程可由式(5)更改為如下：

綜上可見，嵌入容量參數kx主要由分塊類型及方差決定，方差越小，塊越平滑，失真也小。故本文自適應地選擇kx，在相應的塊中嵌入大量水印信息，以提高水印嵌入容量，保證較好的圖像質量。

表1 kx的自適應選擇過程

3 BACS-RWA算法實現過程

3.1 嵌入算法步驟

步驟 1 將載體圖像X分成N個非重疊小塊x=(x0,x1,…,xn)∈Z n+1,xi是x中任一塊；

步驟 2 按照2.2節方法將所得小塊分為3類塊的集合：滑塊集合I1，普通塊集合I2，復雜塊集合I3；

步驟 4 根據上一步建立比特序列記錄Location Map(LM)，其中

同時采用行程編碼(Run-Length Encoding,RLE)對LM進行無損壓縮得到CLM。

嵌入算法的偽代碼過程如表2所示。

表2 嵌入算法的偽代碼過程

3.2 提取算法步驟

水印提取算法流程圖如圖3所示。

步驟 1 將水印圖像Iw分成N個非重疊小塊Iw=(iw0,iw1,…,iwn)∈Zn+1,iwi是Iw中任一小塊；

步驟 2 用與嵌入過程中光柵掃描順序相反的順序即從左到右，從上到下進行掃描圖像塊，讀取iwi的LSB，得到壓縮的位置圖CLM；

圖3 水印提取算法流程圖

步驟 3 解壓 CLM 即得位置圖 LM，從而得TH1, TH2,T，據此判斷出塊類型，分為光滑塊I1，普通塊I2、復雜塊I3；

步驟 4 對得到的復雜塊I3不做處理，利用2.3節基于塊壓縮感知的重構方法對平滑塊I1，普通快I2利用重構算法進行塊重構，得出壓縮感知后的隨機投影測量值；

步驟 5 根據步驟 3得到位置圖相關信息確定各塊的容量參數kx，對步驟4中I1,I2的重構結果進行自適應整數逆變換即可得到水印信息w和原始載體I。

4 實驗結果及分析

所有實驗均在 Dell Inspiron N4010筆記本電腦，i3 CPU, 2 G內存，Win7操作系統下以MATLAB7.8為實驗平臺得到。選擇4幅標準的具有不同紋理特征的512×512的8 bit灰度載體圖像如圖 4(a)-4(d)，包括 Lena, Baboon, Plane(F-16)和Sailboat，采用隨機函數(rand)隨機生成的隨機比特序列作為水印信息，性能評價標準以數據嵌入比特率(BPP)和峰值信噪比(PSNR)來衡量。

4.1 閾值的選擇

為提高水印嵌入容量，本文進行了2×2, 4×4, 8×8, 16×16分塊實驗。現以其一種情況為例說明閾值選擇，其它分塊情況原理相同。首先計算4類載體圖像分塊后對應的每個塊中各像素的均值(mean)和方差(var)，如表 3，對應塊號的數字組成順序就是其分塊后行列號。當分塊為16×16時，分別對4種情況的方差和均值進行了相應計算并用于實驗中閾值，權衡水印容量、圖像質量及算法綜合性能，自適應容量參數選擇中T取表3結果的4類載體塊方差的均值1.3229e+003, TH1, TH2分別設為相應載體的方差的最大值和最小值，據文中判定方法可確定塊類型。

4.2 不同分塊數目對算法性能的影響

圖5以Lena為例可以看出由分塊2×2到4×4時，嵌入容量較高且圖像不可見性能較好。然而當增加到 8×8時性能居兩者之間，當分塊為 16×16時 PSNR 值略高于 4×4，最大嵌入容量達到 1.8 bpp，而其它分塊最大嵌入容量均低于此值。其主要原因一方面在于塊越大嵌入率就越大，但分塊太大的話不能嵌入的點比較多，從而位置圖比較大；另一方面由于本算法中采用了分塊壓縮感知理論，不同分塊尺寸會影響重建效果和時間。隨著分塊尺寸的減小，在重建圖像中子空間(或塊)的邊界更容易形成明顯的塊邊界，視覺效果逐漸降低，得出的峰值信噪比也逐漸降低，當分塊為16×16時其重建效果較好且重建時間適中，故表現出最優性能。而 8×8分塊重建時，塊效應相對較突出，影響了其重建質量。

本文采用了4幅載體圖像分別進行了2×2, 4×4, 8×8, 16×16分塊嵌入，其對應的最大嵌入率如圖6所示，經多次實驗得最佳分塊為16×16分塊。采用本文嵌入算法后最大嵌入率也有差異，其中Lena為1.8 bpp, Baboon為0.8 bpp, Plane為1.87 bpp, Sailboat為1.6 bpp。

4.3 算法綜合性能與其他文獻方法比較

為驗證 BACS-RWA算法的優越性，實驗選擇16×16分塊，采用相同載體圖像和水印，選取文獻[17]，文獻[18]和文獻[19]3種可逆水印算法進行對比實驗。從圖7(a)-7(d)綜合性能對比實驗結果可以看出，BACS-RWA具有較好的水印容量-失真性能。

圖 7(a)是基于局部水印嵌入能力差別較小的Lena圖像的綜合性能對比曲線圖。在高嵌入率下的質量較高，其PSNR值在嵌入率高達1 bpp時仍高于35 dB；當嵌入率小于0.4時，文獻[19]的算法在分塊處理表現出的效果不太明顯，PSNR性能略低于文獻[18]算法，而文獻[17]算法性能在 1 bpp范圍內都低于其他算法，這是因為其灰度溢出采用的是灰度直方圖最小合并項合并壓縮的方案。本文算法最高嵌入容量可達到1.8 bpp，文獻[19]算法嵌入容量不足 1.4 bpp，文獻[18]算法嵌入容量不足 1.2 bpp，而文獻[17]最大嵌入容量僅1 bpp。

圖4 實驗采用的載體圖像

表3 不同載體圖像4×4塊均值和方差

圖5 Lena 進行不同分塊性能曲線

圖6 不同載體進行4種分塊的嵌入率

圖7 算法綜合性能對比

圖7(b)是基于載體圖像為Baboon的綜合性能對比曲線。由于Baboon是4幅圖像中紋理最復雜的圖像，圖像的質量隨著嵌入數據量的增多下降較快，在嵌入率為0.1 bpp時4種方法PSNR值差異不明顯，當嵌入率達到0.4 bpp時，利用BACS-RWA嵌入數據后的圖像的 PSNR比文獻[19]，文獻[18]和文獻[17]算法分別高2 dB, 4 dB, 5 dB，表現出了良好的性能。隨著嵌入信息量的增多，復雜的紋理對圖像質量影響越來越嚴重，但其PSNR仍高于其他算法。

圖7(c)采用了紋理較為簡單的Plane(F-16)為載體圖像，圖像整體相對于其它3種載體最平滑，像素塊的差值小，使用較小的閾值則可以將圖像劃分成不同的類型，平滑區域能產生較多的嵌入信息可用像素。因此，嵌入率比較高，圖像質量較好，綜合性能較穩定。而另外3種算法當嵌入率達1.2 bpp附近時圖像的PSNR均達到了30 dB，在嵌入率為0.7 bpp附近時，文獻[19]算法與本文算法性能相差較小，本文算法最大嵌入率達到最大值1.87 bpp。

圖7(d)是對Sailboat進行實驗對比結果，嵌入率在0.2 bpp附近時文獻[18]算法PSNR值略微高于本文算法，但隨著其嵌入率的增大，文獻[18]和文獻[17]算法的PSNR值明顯下降，而文獻[19]算法中未對該載體圖進行實驗，本文算法的綜合性能曲線則較平穩，且當達到最大嵌入率時其PSNR值依然高于24 dB。

本文選取3個固定嵌入率0.5 bpp, 1.0 bpp和1.2 bpp進行相應的PSNR對比，結果如表4所示。

表4中的“-”表示由于圖像本身特性無法進行相應實驗測量。從表中可以看出，在所選嵌入率相同的情況下，當在嵌入率為0.5 bpp時，本文算法的平均PSNR高于文獻[18]2.84 dB，高于文獻[19]2.1 dB；隨著嵌入率升高，當達到1.0 bpp時，本文算法平均PSNR高于文獻[18]2.3 dB，高于文獻[19]1.3 dB；在相同嵌入率為 1.2 bpp時，本文算法平均PSNR分別高于文獻[18]3.15 dB，高于文獻[19]1.45 dB。出現此差異主要原因是文獻[17]采用的線性預測誤差相比其他算法的預測誤差要發散，相比而言，該算法性能稍差，但性能比較平穩，這歸功于其灰度直方圖調整采用了最小合并項的方案。文獻[18]采用基于直方圖位移的插值技術的可逆圖像水印，由于取得較集中的預測誤差直方圖，在小嵌入量時算法性能較高，但不足的是灰度溢出控制方案對于在最亮或最暗端含有較大比例像素的宿主圖像，由于輔助信息無法完整保存導致嵌入失效。文獻[19]在水印嵌入能力強的局部區域水印分配的多，嵌入弱的分配的少，但其通過迭代處理后不可避免地產生了失真從而影響圖像質量。由此可見，本文算法具有較好的圖像質量，適于高容量水印信息嵌入。

5 結束語

本文提出一種基于分塊自適應壓縮感知的數字圖像可逆水印算法。利用分塊理論判斷塊類型并進行壓縮感知，自適應選擇嵌入容量系數進行整數變換嵌入信息，以提高水印容量。避免了噪聲塊引起的較大失真，更多的水印嵌入到光滑塊和普通塊中，提高了水印嵌入容量同時確保了圖像質量，不可見性較好。實驗結果表明：該算法較以往可逆水印算法相比在嵌入容量和不可見性等綜合性能上都具有優越性。

表4 相同嵌入率下 PSNR值對比(dB)

[1]Tian J. Reversible data embedding using a difference expansion[J].IEEE Transactions on Circuits System Video Technology, 2003, 13(8): 890-896.

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

[3]Tai W L, Yeh C M, and Chang C C. Reversible data hiding based on histogram modification of pixel differences[J].IEEE Transactions on Circuits System Video Technology, 2009,19(6): 906-910.

[4]Chung Kuo-liang, Huang Yong-huai, Yan Wen-ming,et al..Distortion reduction for histogram modification-based reversible data hiding[J].Applied Mathematics Computation,2012, 218(9): 5819-5826.

[5]王俊祥, 倪江群, 潘金偉. 一種基于直方圖平移的高性能可逆水印算法[J]. 自動化學報, 2012, 38(1): 88-96.

Wang Jun-xiang, Ni Jiang-qun, and Pan Jin-wei. A high performance reversible watermarking scheme based on histogram shifting[J].Acta Automatica Sinica, 2012, 38(1):88-96.

[6]Celik M U, Sharma G, Tekalp A M,et al.. Lossless generalized-LSB data embedding[J].IEEE Transactions on Image Processing, 2005, 14(2): 253-266.

[7]Peng Fei, Li Xiao-long, and Yang Bin. Adaptive reversible data hiding scheme based on integer transform[J].Signal Processing, 2012, 92(1): 54-62.

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

[9]朱立, 趙耀, 倪蓉蓉. 基于混合整數變換的高容量可逆數字水印[J]. 數據采集與處理, 2010, 25(2): 188-194.

Zhu Li, Zhao Yao, and Ni Rong-rong. High-capacity reversible watermarking based on mixed integer transform[J].Journal of Data Acquisition and Processing, 2010, 25(2):188-194.

[10]Arsalan M, Malik S A, and Khan A. Intelligent reversible watermarking in integer wavelet domain for medical images[J].Journal of Systems and Software, 2012, 85(4):883-894.

[11]Chaumont M and Puech W. A high capacity reversible watermarking scheme[C]. Proceedings of the SPIE-IS&T Electronic Imaging, Visual Communications and Image Processing, San Jose, California, USA, Sept. 11-12, 2009,SPIE Vol. 7257: 1-9.

[12]Coltuc D. Improved capacity reversible watermarking[C].Proceedings of the 14th IEEE International Conference on Image Processing(ICIP’07), San Antonio, TX, USA, Sept. 16-Oct. 19, 2007, Vol.3: 249-252.

[13]翁韶偉. 數字圖像的高容量可逆水印研究[D]. [博士論文]. 北京交通大學, 2009.

Weng Shao-wei. Research on high-capacity reversible watermarking algorithms[D]. [Ph.D. dissertation], Beijing Jiaotong University, 2009.

[14]呂林濤, 張璽. 改進的大容量可逆數字水印嵌入算法[J]. 計算機工程, 2011, 37(22): 107-109.

Lv Lin-tao and Zhang Xi. Improved large capacity reversible digital watermark embedding algorithm[J].Computer Engineering, 2011, 37(22): 107-109.

[15]趙春暉, 劉巍. 基于分塊壓縮感知的圖像半脆弱零水印算法[J]. 自動化學報, 2012, 38(4): 609-617.

Zhao Chun-hui and Liu Wei. Block compressive sensing based image semi-fragile zero-watermarking[J].Acta Automatica Sinica, 2012, 38(4): 609-617.

[16]Lustig M, Donoho D L, and Pauly J M. Sparse MRI: the application of compressed sensing for rapid MR imaging[J].Magnetic Resonance in Medicine, 2007, 58(6): 1182-1195.

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

[18]Luo Li-xin, Zheng yong, Chen Ming,et al.. Reversible image watermarking using interpolation technique[J].IEEE Transactions on Information Forensics and Security, 2010,5(1): 187-193.

[19]羅劍高. 可逆圖像水印及可逆圖像認證技術研究[D]. [博士論文], 華南理工大學, 2011.

Luo Jian-gao. Research of reversible image watermarking and reversible image authentication techniques[D]. [Ph.D.dissertation]. South of China University of Technology, 2011.