直方圖平移的自適應大容量可逆水印算法

王 祥,李 可,付凱元,駱 璠

(1.西安電子科技大學通信工程學院,陜西西安 710071; 2.西安電子科技大學計算機學院,陜西西安 710071)

直方圖平移的自適應大容量可逆水印算法

王 祥1,李 可1,付凱元2,駱 璠1

(1.西安電子科技大學通信工程學院,陜西西安 710071; 2.西安電子科技大學計算機學院,陜西西安 710071)

傳統的基于直方圖平移的可逆水印算法的單遍嵌入過程在每個像素點中至多只能嵌入1 bit水印信息,為了達到更高的嵌入量必須使用多遍嵌入.但在第2遍以及其后的嵌入過程中,所計算的預測誤差將受到嵌入的水印信息的影響,極大地降低嵌入效率.為此,筆者提出一種基于直方圖可逆數字水印的改進算法,該算法根據圖像的紋理復雜度在像素中自適應嵌入1 bit或多比特水印信息,使得單遍嵌入量可以達到2 bit/像素以上.此外,即使在單個像素點嵌入多比特水印信息,所使用的預測誤差仍為原始預測誤差,有效地降低了嵌入失真.實驗結果表明,該算法在有效提高嵌入量的同時仍可保持較高的圖像質量.

自適應;可逆水印;直方圖平移

近年來,數字水印技術作為信息安全研究領域中的一個新興方向得到了廣泛的研究.然而數字水印的嵌入通常會給原始載體帶來不可擦除的失真.雖然這種失真通常很小,但對醫學或軍事圖像保護這種高保真的圖像應用來說,這種失真仍是不可接受的.為了解決該問題,一些學者提出了可逆數字水印技術.可逆數字水印技術的主要思想是,在原始載體信息中嵌入數據或加入水印,得到嵌入有用信息的載體信息.在解碼端,用戶不但可以從嵌入數據或加入水印的載體信號中無失真地提取所嵌入的有用信息,而且還可以無失真地恢復出原始載體信號.

目前可以查找到的最早關于可逆數字水印的思想是1997年Barton申請的專利,該專利通過無損壓縮原始數據流擠出一定的空間以嵌入有用信息.Fridrich等人進一步擴展了該算法,提出了在JPEG(Joint Photographic Experts Group)系數上進行無損嵌入的方法[1],并把上述方法應用到視頻上[2].基于同樣的思想,Celik等人提出了廣義最低有效位(Least Significant Bit,LSB)的可逆水印算法[3].但是由于圖像的LSB具有隨機分布的特性,所以無損壓縮LSB序列并不能節約太多空間,導致該方法的容量有限.

現有可逆水印方案可以分為基于整數變換[4-5]和基于直方圖平移[6-8]兩種,由于基于直方圖平移的可逆水印技術具有較好的容量控制能力,因此,這種技術得到了廣泛的應用.

1 直方圖平移技術

1.1 傳統的直方圖平移嵌入過程

傳統的直方圖平移是一種高質量的可逆水印技術,它通過直方圖的平移操作,利用零點冗余實現秘密信息嵌入.基于傳統直方圖平移的可逆水印嵌入過程,主要包括如下步驟:

Step1 計算圖像中所有像素點的像素預測值的預測誤差.

Step2 依據預測誤差構造統計直方圖,根據統計直方圖將圖像中的像素點劃分為嵌入水印數據的可嵌入點集合以及平移的可移動點集合.

在Step2中,構造的統計直方圖如圖1所示,其中,直方圖的橫軸表示預測誤差的值,縱軸表示預測誤差在圖像中出現的次數.該直方圖被分成兩部分:嵌入區域和平移區域.其中,平移區域內的預測誤差所對應的像素點被用來平移,即該區域內的像素點對應的像素值被改變但未被嵌入水印數據,嵌入區域內的預測誤差所對應的像素點被用來嵌入水印數據.

圖1 直方圖示意圖

Step3 對可嵌入點集合中的所有像素點執行水印嵌入處理,對可移動點集合中的所有像素點執行平移處理.

1.2 傳統的直方圖平移方法

如圖2所示,現假設I={I(i,j):1≤i≤N1,1≤j≤N2},是一幅大小為N1=N2=512的原始圖像;使用預先定義的預測算法,I′={I′(i,j):1≤i≤N1,1≤j≤N2}.I′(i,j)表示原始像素I(i,j)的預測值; d(i,j)=I(i,j)-I′(i,j),表示預測誤差.根據嵌入容量,可以確定門限值T.

圖2 原始像素示意圖

當預測誤差d(i,j)∈[-T,T)時,有1 bit水印信息通過下式被嵌入原始像素中:

式中,b∈0,1,為要嵌入的水印信息,dw(i,j)和Iw(i,j)中的上標w表示嵌入水印信息的意思.當預測誤差d(i,j)∈(-∞,-T)∪[T,+∞)時,不嵌入水印信息而是通過式(3)進行平移操作,以此來避免與含有水印信息的預測誤差發生重疊.

在提取時,根據Iw(i,j)和I′(i,j)恢復出原始的預測誤差和嵌入的水印信息.

1.3 廣義的直方圖平移方法

傳統的差值擴展方法只能在原始像素中嵌入1 bit水印信息.為了在原始像素中單遍嵌入多比特水印信息,對傳統的直方圖平移方法做如下推廣.當d(i,j)∈[-T,T)時,原始像素中嵌入水印信息,dw(i,j)如式(4)定義.

式中,n為水印比特位;b∈(0,1,…,2n-1),為要嵌入的水印信息.當預測誤差d(i,j)∈(-∞,-T)∪[T,+∞)時,原始像素中不嵌入水印信息,而是進行平移操作,dw(i,j)如式(5)定義.

這樣做的好處就是在容量比較大時,不用用到預測誤差大的那些像素,從而減小了像素值的最大修改量,進而減小了嵌入失真.這樣提高了嵌入比特率,傳統的直方圖平移擴展是1bpp,現在可以達到1.8 bpp.

為了論證文中提出的單遍嵌入多比特相比于多遍嵌入的優勢,這里以兩遍嵌入為例.假設對一個原始像素分兩遍分別嵌入水印信息b1和b2,根據式(1)迭代計算兩次可知:基于傳統直方圖擴展方案的像素失真為3d(i,j)+2b1+b2+e;根據式(4),對一個原始像素單遍嵌入2比特水印信息,基于廣義的直方圖擴展方案的預測誤差失真為3d(i,j)+2b1+b2.在傳統的直方圖平移擴展中,e在單遍嵌入和兩遍嵌入過程中有不同的預測值,這個差值是在第1遍嵌入過程中產生的,它減小了像素間的相關性.在大多數情況下,e是正值.通常e隨著嵌入次數的增大而增大.因此,對于可移動的像素來說,廣義的直方圖平移擴展方案的優勢就是所使用的預測誤差仍為原始的預測誤差,有效地降低了嵌入失真.

在提取時,可以如下恢復出原始預測誤差和嵌入的水印信息.

當dw(i,j)∈[-2nT,2nT)時,恢復出原始預測誤差為

2 梯度導向預測(GAP)算子

為了在提高嵌入容量的同時減小嵌入失真,傳統的算法中,在inner區域內的預測誤差被用來嵌入水印,而outer區域內的預測誤差被用來平移以避免發生重疊.很明顯,outer區域內的預測誤差被修改但是沒有嵌入水印.所以對于同樣的門限值來說,如果inner區域的預測誤差在一個直方圖中占有更大的比例,則通過直方圖平移在該直方圖內嵌入水印所帶來的失真更小,也就是說具有更好的嵌入效果.所以,筆者引入比傳統算法使用的JPEG-LS算法[6]更高效的梯度導向預測(GAP)算子[9]來提高inner區域所占比例.

GAP算子是一個簡單、自適應、非線性的預測算子.它可以獲得非常高的預測精度,同時具有較低的時間和空間復雜度.GAP根據一個像素的局部紋理信息自適應地計算預測值.考慮一個像素點pi,根據式(8)計算其紋理特性.

如圖2所示,I={I(i,j):1≤i≤N1,1≤j≤N2},是一幅大小為N1=N2=512的原始圖像,Gh和Gv是像素點I(i,j)在水平和垂直方向上的紋理信息,根據Gh和Gv,I(i,j)的預測值計算如下:

3 自適應嵌入

自適應嵌入方式充分考慮宿主圖像的局部特征,使得水印的嵌入位置、嵌入強度、嵌入信息量隨著局部特征的不同而自適應改變.

根據式(2),某像素點的平均失真按式(10)計算.

在這里仍以兩遍嵌入為例論證筆者提出的單遍嵌入多比特相比于多遍嵌入的優勢.假設對某一原始像素點分兩遍分別嵌入水印信息b1和b2,此時,

兩遍嵌入后某點的額外平均失真為

可以明顯看出,對于兩個預測誤差d1(i,j)和d2(i,j),如果足夠大,則Dis(d1(i,j))大于A Dis(d2(i,j)).也就是說,在預測誤差很大的像素中嵌入1 bit和在預測誤差較小的像素中再嵌入1 bit相比,前者的失真更大.所以,當嵌入容量為n時,多遍嵌入的效果不如單遍嵌入的好.

因此,在原始圖像的所有像素值中均勻地嵌入相同比特水印信息并不是最優化的策略.為保證在嵌入大容量水印信息后圖像的質量,需選擇嵌入數據后對圖像修改量小的像素點.在選取嵌入像素對時,首選差值小的像素對嵌入數據,擴展后的差值才不會太大,這樣得到的預測誤差直方圖更尖銳,直方圖中可擴展的預測誤差增多,可移動像素減少,失真小,圖像質量更高.

但是解碼器如何知道某個像素點到底嵌入了多少比特水印信息呢?筆者采用在自適應嵌入和提取過程中都保持不變的量Dis_F來解決這個問題.如圖3所示,Dis_F被稱為前向方差,它反映了I(i,j)的紋理復雜度,是指與I(i,j)相鄰的4個相鄰像素點的均方差.選擇前向方差滿足Dis_F＜s(s是門限值)的像素值嵌入,并且只在這些像素值中嵌入水印信息.這樣,只有被選擇的像素值才被擴展和平移,而其余的像素值保持不變.假定s不變,選擇一個適當的s.最好把s定義為一個關于Tmax的單調遞增函數.因此,筆者這樣定義s:

據圖2可知,式(13)成立.

判斷的步驟如下:首先,對于每一個像素值,依據自適應嵌入的門限值,也就是最大修改量Tmax∈{1,2,…,30},可以計算嵌入比特數;接著,計算像素值的前向方差,依據前向方差和門限值可判斷像素值中是嵌入信息還是進行直方圖平移;最后,通過修改預測誤差直方圖自適應地嵌入水印信息.

數據嵌入過程描述如下:掃描宿主圖像中的每個原始像素值,并計算其嵌入水印信息后的預測誤差.對宿主圖像中的每個像素值,重復以下的步驟直到水印信息被嵌入為止.計算前向方差Dis_F和預測誤差的平均值ε.

如果Dis_F≥s,則這個像素值保持不變,即不嵌入水印信息,計算它的下一個像素值的Dis_F;如果Dis_F＜s,則這個像素值將進行平移或者嵌入水印信息.然后根據相鄰像素預測誤差的平均值來計算該像素點嵌入的比特數目n.

對于傳統的差值擴展,做了以下的推廣:

式中,n由式(15)確定;b∈(0,1,…,2n-1),為要嵌入的水印信息.

當進行平移操作時,根據式(17)進行.

4 嵌入和提取過程

筆者提出的基于廣義直方圖平移的自適應嵌入過程如下:

Step1 計算所有像素值的估計誤差e,根據式(15)確定要嵌入的比特數;

Step2 建立位置地圖M,假設其長度為m.對像素點進行排序后把它們分成3部分:I1,I2,I3.其中,I1中包含m個可嵌入點,I3包含最后的m個像素點,其他的像素點為I2;

Step3 通過LSB替換把位置地圖嵌入到I3中,記錄原始LSB序列為L;

Step4 根據式(16)把L和水印信息嵌入到I1中.如果在一個像素值中可嵌入容量為n,那么只在最后1 bit嵌入L,剩余的n-1嵌入水印信息;

Step5 根據式(16)和式(17),把剩余的水印信息嵌入到擴展像素和修改的平移像素中.

恢復和提取過程為嵌入過程的逆過程,為了節約篇幅,本文不再詳述.

5 實驗結果

文中算法使用512×512的2個灰度級圖像Lena和Airplane進行實驗比較.這些圖像都是從圖像數據庫中下載的.根據選擇門限值的不同可以獲得不同的嵌入率,隨著嵌入容量的增大,文中選擇的門限值T∈[1,30],并且這里使用無損壓縮編碼的算法來壓縮位置地圖.為了評價文中算法,這里使用當前國際上最先進的3種可逆水印算法與文中算法進行比較:Tian等人[8]的算法(以下簡稱Tian算法),Thodi等人[6]的PE算法(以下簡稱Thodi算法)和Alattar等人[4]的算法(以下簡稱Alattar算法).

Tian算法基于差擴展可逆水印技術對Haar整數小波變換的高頻分量(即差值部分)做幅值乘2的數值擴展,將空余出來的LSB嵌入水印信息.此方法第1次引入數值擴展技術,成為大容量可逆水印算法的一個經典,對可逆水印的發展有著廣泛和深遠的影響.但由于Tian算法的含印圖像質量偏低,之后的大容量可逆水印技術大都是從降低位置圖對可用容量的消耗來改進Tian算法,其中比較有代表性的是Thodi算法. Thodi算法把灰度平移應用到了差擴展中,從而在嵌入容量和嵌入失真方面都有了較大改善.Alattar算法代表了典型的基于整數變換的可逆水印算法.

當最大嵌入容量小于1.0比特每像素時,文中算法與上述3種算法在單遍嵌入時的曲線圖如圖3所示.從圖中可以清楚看到,文中算法的嵌入容量明顯好于其他3種算法.當嵌入容量大于1.0比特每像素時,Thodi算法的嵌入效果比Tian算法和Alattar算法的嵌入效果明顯要好,所以此時只用Thodi算法與文中算法進行比較.從圖4可以看出,文中算法在嵌入率大于1.0比特每像素時能達到最好的表現效果,也就是說,文中算法的優勢在大嵌入率時體現得尤為明顯.顯然.在圖4(a)和圖4(b)中,當峰值信噪比為4 d B到5 dB時,文中方法的嵌入率明顯優于Thodi算法.這是因為單遍嵌入的嵌入失真降低了預測性能.所以當使用多遍嵌入時廣義的直方圖平移方法中峰值信噪比下降非常快.當文中方法的單遍嵌入率達到一個較高的嵌入容量時,在嵌入過程中相鄰像素的相關性并沒有下降.

圖3 當最大嵌入容量小于1.0比特每像素時,文中算法與Tian算法、Thodi算法和Alattar算法性能比較曲線圖

圖4 最大嵌入容量大于1.0比特每像素時,文中算法與Thodi算法性能比較曲線圖

6 結 論

文中提出了一種基于直方圖平移的自適應大容量可逆水印算法.首先介紹了傳統的直方圖平移方法,進而通過自適應選擇算法,在適合于多次嵌入的像素點中單遍嵌入多個比特的水印信息.實驗結果表明,所提出的算法在單遍嵌入時可達到1.8比特每像素的嵌入量.在相同容量下,與多遍嵌入相比,所提出的算法具有更小的嵌入失真.

[1]Fridrich J,Goljan M,Du R.Invertible Authentication Watermark for JPEG Images[C]//Proceedings of International Conference on Information Technology:Coding and Computer.Los Alamitos:IEEE Computer Society,2001:223-227. [2]Du R,Fridrich J.Lossless Authentication of MPEG-2 Video[C]//Proceedings of IEEE International Conference on Image Processing.Piscataway:IEEE,2002:Ⅱ1893-Ⅱ1896.

[3]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.

[4]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.

[5]Wang X,Li X,Yang B,et al.Efficient Generalized Integer Transform for Reversible Watermarking[J].IEEE Signal Processing Letters,2010,17(6):567-570.

[6]Thodi D M,Rodriguez J J.Expansion Embedding Techniques for Reversible Watermarking[J].IEEE Transactions on Image Processing,2007,16(3):721-730.

[7]Hong W,Chen T S,Shiu C W.Reversible Data Hiding for High Quality Images Using Modification of Prediction Errors [J].Journal of Systems and Software,2009,82(11):1833-1842.

[8]Tian J.Reversible Data Embedding Using a Difference Expansion[J].IEEE Transactions on Circuits and Systems for Video Technology,2003,13(8):890-896.

[9]Wang X,Guo Z.A Novel Reversible Watermarking Method Using Pre-selection Strategy[J].International Journal of Innovative Computing,Information and Control,2011,7(11):6187-6201.

(編輯:李恩科)

Histogram shifting based adaptive reversible watermarking algorithm with a high capacity

WANG Xiang1,LI Ke1,FU Kaiyuan2,LUO Fan1
(1.School of Telecommunication Engineering,Xidian Univ.,Xi’an 710071,China; 2.School of Computer Science and Technology,Xidian Univ.,Xi’an 710071,China)

The traditional histogram shifting based reversible watermarking algorithm can only embed at most 1.0 bit watermark information into one pixel in single-pass embedding.Therefore,we have to use multi-pass embedding to achieve a higher embedding capacity.However,in the second-pass and the subsequent embedding process,the prediction error will be affected by the embedding distortion,which reduces the embedding efficiency.To this end,this paper proposes an improved reversible watermarking algorithm by employing histogram shifting.The algorithm embeds 1.0 bit or more bit watermark in one pixel in terms of the context of image.Experimental results show that the algorithm can effectively improve the embedding capacity while maintaining a high image quality.

adaptive;reversible watermarking;histogram shifting

TP391

A

1001-2400(2014)01-0124-06

10.3969/j.issn.1001-2400.2014.01.022

2012-11-14 < class="emphasis_bold">網絡出版時間:

時間:2013-09-16

國家自然科學基金資助項目(61202391,61172068);中國博士后科學基金資助項目(2012M521748);中央高校基本業務費資助項目(K5051201030,K50511010003);教育部新世紀優秀人才支持計劃資助項目(NCET-11-0691)

王 祥(1983-),男,副教授,博士,E-mail:wangxiang@xidian.edu.cn.

http://www.cnki.net/kcms/detail/61.1076.TN.20130916.0926.201401.154_018.html