直方圖平移的自適應(yīng)大容量可逆水印算法

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

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

直方圖平移的自適應(yīng)大容量可逆水印算法

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

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

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

自適應(yīng);可逆水印;直方圖平移

近年來(lái),數(shù)字水印技術(shù)作為信息安全研究領(lǐng)域中的一個(gè)新興方向得到了廣泛的研究.然而數(shù)字水印的嵌入通常會(huì)給原始載體帶來(lái)不可擦除的失真.雖然這種失真通常很小,但對(duì)醫(yī)學(xué)或軍事圖像保護(hù)這種高保真的圖像應(yīng)用來(lái)說(shuō),這種失真仍是不可接受的.為了解決該問(wèn)題,一些學(xué)者提出了可逆數(shù)字水印技術(shù).可逆數(shù)字水印技術(shù)的主要思想是,在原始載體信息中嵌入數(shù)據(jù)或加入水印,得到嵌入有用信息的載體信息.在解碼端,用戶不但可以從嵌入數(shù)據(jù)或加入水印的載體信號(hào)中無(wú)失真地提取所嵌入的有用信息,而且還可以無(wú)失真地恢復(fù)出原始載體信號(hào).

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

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

1 直方圖平移技術(shù)

1.1 傳統(tǒng)的直方圖平移嵌入過(guò)程

傳統(tǒng)的直方圖平移是一種高質(zhì)量的可逆水印技術(shù),它通過(guò)直方圖的平移操作,利用零點(diǎn)冗余實(shí)現(xiàn)秘密信息嵌入.基于傳統(tǒng)直方圖平移的可逆水印嵌入過(guò)程,主要包括如下步驟:

Step1 計(jì)算圖像中所有像素點(diǎn)的像素預(yù)測(cè)值的預(yù)測(cè)誤差.

Step2 依據(jù)預(yù)測(cè)誤差構(gòu)造統(tǒng)計(jì)直方圖,根據(jù)統(tǒng)計(jì)直方圖將圖像中的像素點(diǎn)劃分為嵌入水印數(shù)據(jù)的可嵌入點(diǎn)集合以及平移的可移動(dòng)點(diǎn)集合.

在Step2中,構(gòu)造的統(tǒng)計(jì)直方圖如圖1所示,其中,直方圖的橫軸表示預(yù)測(cè)誤差的值,縱軸表示預(yù)測(cè)誤差在圖像中出現(xiàn)的次數(shù).該直方圖被分成兩部分:嵌入?yún)^(qū)域和平移區(qū)域.其中,平移區(qū)域內(nèi)的預(yù)測(cè)誤差所對(duì)應(yīng)的像素點(diǎn)被用來(lái)平移,即該區(qū)域內(nèi)的像素點(diǎn)對(duì)應(yīng)的像素值被改變但未被嵌入水印數(shù)據(jù),嵌入?yún)^(qū)域內(nèi)的預(yù)測(cè)誤差所對(duì)應(yīng)的像素點(diǎn)被用來(lái)嵌入水印數(shù)據(jù).

圖1 直方圖示意圖

Step3 對(duì)可嵌入點(diǎn)集合中的所有像素點(diǎn)執(zhí)行水印嵌入處理,對(duì)可移動(dòng)點(diǎn)集合中的所有像素點(diǎn)執(zhí)行平移處理.

1.2 傳統(tǒng)的直方圖平移方法

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

圖2 原始像素示意圖

當(dāng)預(yù)測(cè)誤差d(i,j)∈[-T,T)時(shí),有1 bit水印信息通過(guò)下式被嵌入原始像素中:

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

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

1.3 廣義的直方圖平移方法

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

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

這樣做的好處就是在容量比較大時(shí),不用用到預(yù)測(cè)誤差大的那些像素,從而減小了像素值的最大修改量,進(jìn)而減小了嵌入失真.這樣提高了嵌入比特率,傳統(tǒng)的直方圖平移擴(kuò)展是1bpp,現(xiàn)在可以達(dá)到1.8 bpp.

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

在提取時(shí),可以如下恢復(fù)出原始預(yù)測(cè)誤差和嵌入的水印信息.

當(dāng)dw(i,j)∈[-2nT,2nT)時(shí),恢復(fù)出原始預(yù)測(cè)誤差為

2 梯度導(dǎo)向預(yù)測(cè)(GAP)算子

為了在提高嵌入容量的同時(shí)減小嵌入失真,傳統(tǒng)的算法中,在inner區(qū)域內(nèi)的預(yù)測(cè)誤差被用來(lái)嵌入水印,而outer區(qū)域內(nèi)的預(yù)測(cè)誤差被用來(lái)平移以避免發(fā)生重疊.很明顯,outer區(qū)域內(nèi)的預(yù)測(cè)誤差被修改但是沒(méi)有嵌入水印.所以對(duì)于同樣的門限值來(lái)說(shuō),如果inner區(qū)域的預(yù)測(cè)誤差在一個(gè)直方圖中占有更大的比例,則通過(guò)直方圖平移在該直方圖內(nèi)嵌入水印所帶來(lái)的失真更小,也就是說(shuō)具有更好的嵌入效果.所以,筆者引入比傳統(tǒng)算法使用的JPEG-LS算法[6]更高效的梯度導(dǎo)向預(yù)測(cè)(GAP)算子[9]來(lái)提高inner區(qū)域所占比例.

GAP算子是一個(gè)簡(jiǎn)單、自適應(yīng)、非線性的預(yù)測(cè)算子.它可以獲得非常高的預(yù)測(cè)精度,同時(shí)具有較低的時(shí)間和空間復(fù)雜度.GAP根據(jù)一個(gè)像素的局部紋理信息自適應(yīng)地計(jì)算預(yù)測(cè)值.考慮一個(gè)像素點(diǎn)pi,根據(jù)式(8)計(jì)算其紋理特性.

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

3 自適應(yīng)嵌入

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

根據(jù)式(2),某像素點(diǎn)的平均失真按式(10)計(jì)算.

在這里仍以兩遍嵌入為例論證筆者提出的單遍嵌入多比特相比于多遍嵌入的優(yōu)勢(shì).假設(shè)對(duì)某一原始像素點(diǎn)分兩遍分別嵌入水印信息b1和b2,此時(shí),

兩遍嵌入后某點(diǎn)的額外平均失真為

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

因此,在原始圖像的所有像素值中均勻地嵌入相同比特水印信息并不是最優(yōu)化的策略.為保證在嵌入大容量水印信息后圖像的質(zhì)量,需選擇嵌入數(shù)據(jù)后對(duì)圖像修改量小的像素點(diǎn).在選取嵌入像素對(duì)時(shí),首選差值小的像素對(duì)嵌入數(shù)據(jù),擴(kuò)展后的差值才不會(huì)太大,這樣得到的預(yù)測(cè)誤差直方圖更尖銳,直方圖中可擴(kuò)展的預(yù)測(cè)誤差增多,可移動(dòng)像素減少,失真小,圖像質(zhì)量更高.

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

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

判斷的步驟如下:首先,對(duì)于每一個(gè)像素值,依據(jù)自適應(yīng)嵌入的門限值,也就是最大修改量Tmax∈{1,2,…,30},可以計(jì)算嵌入比特?cái)?shù);接著,計(jì)算像素值的前向方差,依據(jù)前向方差和門限值可判斷像素值中是嵌入信息還是進(jìn)行直方圖平移;最后,通過(guò)修改預(yù)測(cè)誤差直方圖自適應(yīng)地嵌入水印信息.

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

如果Dis_F≥s,則這個(gè)像素值保持不變,即不嵌入水印信息,計(jì)算它的下一個(gè)像素值的Dis_F;如果Dis_F＜s,則這個(gè)像素值將進(jìn)行平移或者嵌入水印信息.然后根據(jù)相鄰像素預(yù)測(cè)誤差的平均值來(lái)計(jì)算該像素點(diǎn)嵌入的比特?cái)?shù)目n.

對(duì)于傳統(tǒng)的差值擴(kuò)展,做了以下的推廣:

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

當(dāng)進(jìn)行平移操作時(shí),根據(jù)式(17)進(jìn)行.

4 嵌入和提取過(guò)程

筆者提出的基于廣義直方圖平移的自適應(yīng)嵌入過(guò)程如下:

Step1 計(jì)算所有像素值的估計(jì)誤差e,根據(jù)式(15)確定要嵌入的比特?cái)?shù);

Step2 建立位置地圖M,假設(shè)其長(zhǎng)度為m.對(duì)像素點(diǎn)進(jìn)行排序后把它們分成3部分:I1,I2,I3.其中,I1中包含m個(gè)可嵌入點(diǎn),I3包含最后的m個(gè)像素點(diǎn),其他的像素點(diǎn)為I2;

Step3 通過(guò)LSB替換把位置地圖嵌入到I3中,記錄原始LSB序列為L(zhǎng);

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

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

恢復(fù)和提取過(guò)程為嵌入過(guò)程的逆過(guò)程,為了節(jié)約篇幅,本文不再詳述.

5 實(shí)驗(yàn)結(jié)果

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

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

當(dāng)最大嵌入容量小于1.0比特每像素時(shí),文中算法與上述3種算法在單遍嵌入時(shí)的曲線圖如圖3所示.從圖中可以清楚看到,文中算法的嵌入容量明顯好于其他3種算法.當(dāng)嵌入容量大于1.0比特每像素時(shí),Thodi算法的嵌入效果比Tian算法和Alattar算法的嵌入效果明顯要好,所以此時(shí)只用Thodi算法與文中算法進(jìn)行比較.從圖4可以看出,文中算法在嵌入率大于1.0比特每像素時(shí)能達(dá)到最好的表現(xiàn)效果,也就是說(shuō),文中算法的優(yōu)勢(shì)在大嵌入率時(shí)體現(xiàn)得尤為明顯.顯然.在圖4(a)和圖4(b)中,當(dāng)峰值信噪比為4 d B到5 dB時(shí),文中方法的嵌入率明顯優(yōu)于Thodi算法.這是因?yàn)閱伪榍度氲那度胧д娼档土祟A(yù)測(cè)性能.所以當(dāng)使用多遍嵌入時(shí)廣義的直方圖平移方法中峰值信噪比下降非?？?當(dāng)文中方法的單遍嵌入率達(dá)到一個(gè)較高的嵌入容量時(shí),在嵌入過(guò)程中相鄰像素的相關(guān)性并沒(méi)有下降.

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

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

6 結(jié) 論

文中提出了一種基于直方圖平移的自適應(yīng)大容量可逆水印算法.首先介紹了傳統(tǒng)的直方圖平移方法,進(jìn)而通過(guò)自適應(yīng)選擇算法,在適合于多次嵌入的像素點(diǎn)中單遍嵌入多個(gè)比特的水印信息.實(shí)驗(yàn)結(jié)果表明,所提出的算法在單遍嵌入時(shí)可達(dá)到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">網(wǎng)絡(luò)出版時(shí)間:

時(shí)間:2013-09-16

國(guó)家自然科學(xué)基金資助項(xiàng)目(61202391,61172068);中國(guó)博士后科學(xué)基金資助項(xiàng)目(2012M521748);中央高?；緲I(yè)務(wù)費(fèi)資助項(xiàng)目(K5051201030,K50511010003);教育部新世紀(jì)優(yōu)秀人才支持計(jì)劃資助項(xiàng)目(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