基于預(yù)測誤差擴(kuò)展的可逆文本水印算法

費(fèi)文斌，唐向宏，2，王 靜，林新建

(1. 杭州電子科技大學(xué) 通信工程學(xué)院，浙江 杭州 310018；2. 杭州電子科技大學(xué) 信息工程學(xué)院，浙江 杭州 310018)

?

基于預(yù)測誤差擴(kuò)展的可逆文本水印算法

費(fèi)文斌1，唐向宏1，2，王 靜1，林新建1

(1. 杭州電子科技大學(xué) 通信工程學(xué)院，浙江 杭州 310018；2. 杭州電子科技大學(xué) 信息工程學(xué)院，浙江 杭州 310018)

為了避免在水印嵌入后造成文本內(nèi)容的永久性改變，該文借鑒圖像中可恢復(fù)水印的思想，將預(yù)測誤差擴(kuò)展應(yīng)用于文本文檔，提出了一種基于預(yù)測誤差擴(kuò)展的可逆中文文本水印算法。該算法以句子為單位，通過上下文搭配度大小選擇可替換的詞語，最后利用預(yù)測誤差擴(kuò)展和混沌序列，實(shí)現(xiàn)水印的嵌入。研究結(jié)果表明該算法不僅具有較高的安全性，而且能有效地提取水印和無損地恢復(fù)出原始文本。

可恢復(fù)水印；預(yù)測誤差擴(kuò)展；文本文檔；搭配度；混沌序列

1 引言

數(shù)字水印技術(shù)是利用載體數(shù)據(jù)中的隨機(jī)冗余，將秘密信息嵌入載體數(shù)據(jù)中，使其不被人的感覺系統(tǒng)發(fā)現(xiàn)，并且水印前后作品之間的失真通?？梢赃_(dá)到視覺上的不可感知性。這種方法是把人們扭曲約束在一個(gè)人眼不能察覺的很小范圍內(nèi)，但是在某些應(yīng)用領(lǐng)域?qū)d體數(shù)據(jù)的改變十分敏感，不允許載體數(shù)據(jù)永久損失，例如，醫(yī)療、軍事和司法等由于嵌入水印導(dǎo)致的載體改變會(huì)造成嵌入信息后載體質(zhì)量的嚴(yán)重降低。因此一種稱為可逆水印的技術(shù)在近幾年得到了廣泛的關(guān)注?？赡嫠∫蠼獯a器不僅能提取水印信息，而且能將因嵌入水印而失真的數(shù)字載體無損地恢復(fù)[1-3]。

目前，對可逆水印的研究大多數(shù)主要集中在圖像領(lǐng)域[4-8]，而對應(yīng)用最廣泛的文本文檔較少有研究報(bào)道。Tian在2003年首次提出基于像素差值擴(kuò)展(DE)的可逆算法[4]。該算法使用兩個(gè)相鄰像素之間的差值進(jìn)行擴(kuò)展，將水印嵌入到擴(kuò)展后差值的最低有效位上，實(shí)現(xiàn)盲提取和像素恢復(fù)。在這之后，像素的差值擴(kuò)展被廣泛應(yīng)用于圖像的可逆算法上。Thodi等于2004年在DE的基礎(chǔ)上提出了一種使用預(yù)測誤差擴(kuò)展(PEE)的可逆算法[5]，在嵌入容量和保真度上有了較大的提高。在對可逆文本水印算法研究中，劉志杰等[9]在基于圖像可逆水印的基礎(chǔ)上，提出了基于整數(shù)可逆變換的文本可恢復(fù)水印算法和一種改進(jìn)的差值擴(kuò)展的文本可恢復(fù)水印算法。

兩種方案分別采用了圖像水印中整數(shù)可逆變換和差值擴(kuò)展的相關(guān)原理，通過同義詞替換的方式嵌入水印，但是沒考慮在完成嵌入水印后，文本語義會(huì)產(chǎn)生扭曲和偏差。姜傳賢等[10]提出了一種魯棒可逆文本水印算法，該算法具有較強(qiáng)的魯棒性，嵌入算法時(shí)，通過計(jì)算搭配詞在訓(xùn)練語料中出現(xiàn)的頻率來計(jì)算搭配詞共同出現(xiàn)的概率，將用最大概率的搭配詞與原生文本中的詞的編碼進(jìn)行異或，將異或值作為恢復(fù)數(shù)據(jù)，但是在提取和恢復(fù)算法時(shí)將使用大量的冗余信息去恢復(fù)原始數(shù)據(jù)。

為此，本文針對以上可逆文本水印算法的不足，首先通過對句子中的詞語進(jìn)行上下文匹配度計(jì)算，得到語義上不會(huì)產(chǎn)生偏差的可替換同義詞詞語；然后將滿足條件的詞語進(jìn)行預(yù)測誤差擴(kuò)展；利用混沌映射，實(shí)現(xiàn)每次同義詞替換嵌入1 bit水印信息，提高所嵌水印的安全性；在恢復(fù)算法時(shí)，利用混沌映射產(chǎn)生的溢出信息完成文本恢復(fù)，探討一種基于預(yù)測誤差擴(kuò)展的可逆文本水印算法。

2 上下文搭配度計(jì)算與預(yù)測差擴(kuò)展

2.1 上下文搭配度

本文采用同義詞替換的方法實(shí)現(xiàn)水印信息的嵌入，首先需要對同義詞進(jìn)行查找，然后進(jìn)行同義詞替換。在同義詞替換時(shí)，必須考慮上下文的語境，避免替換后引起語義的混亂[11-13]。也就是說，并不是所有的同義詞都可進(jìn)行替換。為解決這個(gè)問題，本文采用上下文搭配度算法來消除由同義詞替換引起的詞語間語義的歧義問題[14]。

圖1 詞與詞的搭配關(guān)系

本文利用哈爾濱工業(yè)大學(xué)信息檢索研究室語言技術(shù)平臺(tái)進(jìn)行語法分析[15]，確定上下文詞語之間的搭配關(guān)系，得到句子中詞語Ci與該句中詞語A1,A2,...,An的搭配關(guān)系，如圖1所示，并通過式(1)計(jì)算該詞語Ci的上下文搭配度ZCi。

式(1)中Z(CiAj)是詞語Ci與詞語Aj的搭配頻率，其大小取自于《中文詞語搭配庫》[16]。這樣，詞語Ci與該句中詞語A1,A2,...,An的搭配程度就等價(jià)于ZCi值的大小；在同一句子中，使用詞語Ci的同義詞替換Ci后，也會(huì)得到相應(yīng)的上下文搭配度。

2.2 預(yù)測誤差擴(kuò)展與混沌映射

在進(jìn)行預(yù)測誤差擴(kuò)展時(shí)，x′可能會(huì)超出變量的取值范圍，產(chǎn)生溢出問題，而且文本文檔可嵌入的冗余較少，無法采用圖像中的處理方法，直接將溢出信息保存在水印圖像中。因此，為了克服溢出問題，本文將溢出信息轉(zhuǎn)化為二進(jìn)制序列，再映射到混沌序列中，這樣可將溢出問題轉(zhuǎn)換到混沌序列初值的確定。本文采用Logistic映射[17]，如式(3)所示。

通過式(4)可轉(zhuǎn)換為二進(jìn)制偽隨機(jī)數(shù)，從而產(chǎn)生偽隨機(jī)二進(jìn)制序列。

在Logistic映射過程中，產(chǎn)生的偽隨機(jī)二進(jìn)制序列與混沌映射的初始值密切相關(guān)。為了使Logistic映射產(chǎn)生的序列中的某段序列與預(yù)測誤差擴(kuò)展獲得的溢出序列相同，本文采用混沌搜索的方式來實(shí)現(xiàn)。具體實(shí)現(xiàn)方法步驟： 首先設(shè)定一個(gè)較小的初值y0，如y0=0.000 1,產(chǎn)生一個(gè)長度為N的混沌序列，如果此序列沒有包含溢出序列，則將y0加上一個(gè)小的步長，如y0=y0+0.000 1，再次得到混沌序列。通過這種方法將溢出信息映射到混沌序列中，記錄下這個(gè)初值y0和溢出序列匹配時(shí)的起始位置B。通過使用y0和B，就可在恢復(fù)算法時(shí)得到溢出信息，恢復(fù)原始文本。如果溢出序列太長，為減小搜索時(shí)間，可將序列進(jìn)行分段，再映射到混沌序列上。

3 算法原理與實(shí)現(xiàn)

基于以上分析，本文所討論的可逆文本水印算法的基本原理是，通過對句子中的詞語進(jìn)行上下文匹配度計(jì)算，得到在語義上不會(huì)產(chǎn)生較大偏差的可替換同義詞詞語，將滿足條件的每個(gè)詞語進(jìn)行預(yù)測誤差擴(kuò)展，利用混沌映射，在完成同義詞替換實(shí)現(xiàn)水印嵌入的同時(shí)，提高所嵌水印的安全性。在水印提取時(shí)，利用預(yù)測誤差擴(kuò)展，實(shí)現(xiàn)原始同義詞的恢復(fù)。

3.1 嵌入算法

本算法的嵌入流程如圖2所示。具體實(shí)現(xiàn)步驟為：

圖2 算法嵌入流程圖

步驟1 分詞。對每個(gè)句子進(jìn)行分詞，并確定詞語之間上下文的搭配關(guān)系。

步驟2 選詞。通過式(1)搭配計(jì)算，定位出文本中可替換的詞語，為預(yù)測誤差擴(kuò)展作準(zhǔn)備。具體實(shí)驗(yàn)步驟如下：

① 根據(jù)分詞后每個(gè)詞語之間的搭配關(guān)系，計(jì)算上下文搭配度ZCi，完成可替換詞語的選擇。為了提高算法的安全性，可設(shè)一個(gè)閥值T，選擇搭配度ZCi大于閥值T的詞語Ci作為可替換詞語。

② 在同義詞詞庫中，找出詞語Ci的同義詞設(shè)個(gè)數(shù)為N。用同義詞替換原始詞語，并再次計(jì)算各同義詞在該句中的上下文搭配度選擇搭配度大于閥值T的詞語設(shè)其個(gè)數(shù)為M，完成可替換同義詞的篩選。

當(dāng)閥值T取不同值時(shí)，選擇的可替換詞語和其同義詞的數(shù)量不同，閥值T大小的選擇增加了算法的安全性。

步驟6 遍歷整個(gè)文本的句子。

步驟7 把每次保存的二進(jìn)制溢出信息連接成字符串L，根據(jù)混沌搜索算法將L記錄在混沌序列中某段序列，把初值y0和起始位置B作為密鑰保存，完成水印嵌入。

3.2 提取算法

水印的提取為水印嵌入的逆過程。具體實(shí)現(xiàn)步驟如下：

因此，當(dāng)lsb(p″e(cuò))=1，則水印w=1；當(dāng)lsb(p″e(cuò))=0，則水印w=0。

步驟3 遍歷整個(gè)文本，完成水印的提取。

3.3 可逆算法

通過可逆算法將水印文本恢復(fù)為原始文本。

步驟2 利用密鑰y0和B得到由混沌產(chǎn)生的二進(jìn)制溢出序列，然后根據(jù)規(guī)則1，得到每個(gè)位置的分類信息。

步驟3 根據(jù)對應(yīng)的分類信息，通過規(guī)則2，還原出每個(gè)位置的x′。

步驟4 根據(jù)式(2)計(jì)算出原始詞語的序號(hào)，并找到該詞進(jìn)行還原。

步驟5 遍歷整個(gè)文本，完成文本的恢復(fù)。

4 實(shí)驗(yàn)結(jié)果與分析

由于本算法是在對句子分詞后，通過搭配度算法選詞，利用預(yù)測誤差擴(kuò)展實(shí)現(xiàn)水印嵌入，并把溢出信息保存在混沌序列中。因此，在提取算法時(shí)，只需根據(jù)搭配度算法定位出嵌入水印的位置，在不需要任何信息的情況下，就可按預(yù)測誤差擴(kuò)展最低有效位的特征提取水印信息；在恢復(fù)算法時(shí)，利用混沌序列的初值和起始位置確定溢出信息，通過逆預(yù)測誤差擴(kuò)展無損地恢復(fù)原始文本。以下給出實(shí)驗(yàn)的部分仿真結(jié)果。如圖3所示給出了一段原始文本，圖中陰影部分表示定位的詞語，假設(shè)需要嵌入的水印序列為100111001，閥值T=0。 通過仿真，對本嵌入算法的不可見性、魯棒性、可恢復(fù)性、安全性及對比分析等方面分別進(jìn)行討論。

圖3 原始文本

1) 不可見性 采用嵌入算法可得的水印文本如圖4所示，圖中帶單下劃線的詞語為嵌入水印后，發(fā)生改變的詞語。比較圖3和圖4嵌入水印前后的效果可以看出，通過同義詞替換進(jìn)行水印的嵌入后，沒有引起文本格式外觀上的變化；通過采用上下文搭配度算法有效避免語義上的歧義，具有較好的不可見性。

圖4 水印文本

2) 魯棒性 表1分別給出了對水印文本再生攻擊、文本格式轉(zhuǎn)換、字體調(diào)整、刪除空格和標(biāo)點(diǎn)符號(hào)統(tǒng)一修正等操作后提取的水印信息。

文本再生攻擊是對原始文本進(jìn)行重構(gòu)；文本格式轉(zhuǎn)換是在文本的各種形式之間的轉(zhuǎn)換，如word轉(zhuǎn)化為txt；字體調(diào)整是將文本中的字體變換，如宋體變?yōu)榉滤误w；刪除空格是將多余的空格去掉；標(biāo)點(diǎn)符號(hào)統(tǒng)一修正是中英標(biāo)點(diǎn)符號(hào)的互換。從表1中可以看出，對于這些文本格式攻擊都不會(huì)破壞水印信息，這是因?yàn)楸舅惴ㄍㄟ^自然語言處理技術(shù)嵌入水印信息，水印的嵌入發(fā)生在文本的內(nèi)容中，在遇到格式攻擊時(shí)，不會(huì)破壞水印信息，具有較強(qiáng)的魯棒性。

表1 格式攻擊分析

3) 可恢復(fù)性 所謂可恢復(fù)性是指將嵌入算法所替換的詞語用原始詞語替換回來，即嵌入的可逆性。本算法是通過同義詞替換的方式嵌入水印信息，不但要求算法能提取所嵌水印，而且要求將被替換的詞語還原，實(shí)現(xiàn)原始文本內(nèi)容的還原。圖5給出對水印文本圖4的恢復(fù)結(jié)果。比較圖3和圖5的原始文本和恢復(fù)文本的效果可以看出，本算法能夠?qū)崿F(xiàn)無損的恢復(fù)原始文本。

圖5 恢復(fù)后的文本

4) 安全性 傳統(tǒng)的同義詞替換算法的安全性由采用的同義詞詞庫的不確定性來保證，同義詞詞庫通常都是保密的，而本算法采用哈工大的《同義詞詞林(擴(kuò)展版)》[15]實(shí)現(xiàn)同義詞查找，是公開的。因此，本算法的安全性是指攻擊者在不完全知道混沌映射的初值和序列起始位置信息的情況下，無法得到原始文本。圖6給出了混沌映射的初值不變，但序列起始位置改變時(shí)所恢復(fù)的文本；圖7給出了混沌序列初值改變，但起始位置不變時(shí)所恢復(fù)的文本；圖8給出了混沌初值和起始位置都改變時(shí)所恢復(fù)的文本，帶雙下劃線部分表示沒有準(zhǔn)確恢復(fù)的詞語。從圖6～8所示的恢復(fù)結(jié)果可以看，所恢復(fù)的內(nèi)容與原始文本有較大的區(qū)別，也就是說在沒有全部獲得密鑰(混沌映射初值和序列起始位置信息)的情況下，攻擊者無法準(zhǔn)確地恢復(fù)出原始文本，算法具有較強(qiáng)的安全性。

圖6 初值不變、起始位置改變時(shí)的恢復(fù)文本

圖7 初值改變、起始位置不變時(shí)的恢復(fù)文本

另外，當(dāng)選詞閥值T發(fā)生改變時(shí)，提取的水印信息會(huì)發(fā)生變化，水印文本恢復(fù)情況也有所改變。圖9給出了當(dāng)選詞閥值T=10時(shí)的水印文本恢復(fù)情況，其提取的水印為10111001。從圖中可以看出，定位的詞語發(fā)生了改變；恢復(fù)的內(nèi)容與原始文本有較大的區(qū)別。因此，閥值T的選擇可進(jìn)一步增加本算法的安全性。

圖8 初值和起始位置都改變時(shí)的恢復(fù)文本

圖9 閥值T改變時(shí)的恢復(fù)文本

5) 對比實(shí)驗(yàn)分析 實(shí)驗(yàn)中也與其他可逆算法進(jìn)行了性能比較，如表2所示。通過對比可以看出，本算法與文獻(xiàn)[9]相比，文本在完成同義詞替換后，不會(huì)發(fā)生語義上的歧義，增加了算法的不可見性，且詞庫是公開的，采用密鑰使得算法的安全性更好；與文獻(xiàn)[10]相比，避免了大量的輔助信息來恢復(fù)文本，易于實(shí)際應(yīng)用。

表2 算法性能比較

5 結(jié)論

本文通過上下文搭配度計(jì)算，定位出可嵌入水印信息的位置，消除了替換詞語后上下文語義上的歧義性，用混沌序列來確定溢出信息，將安全性轉(zhuǎn)換到混沌映射初值的選取和序列起始位置的確定，探討了一種基于預(yù)測誤差擴(kuò)展的可逆文本水印算法。本算法在提取水印時(shí)，不需要原始載體；在原始文本恢復(fù)時(shí)，只需通過密鑰獲得溢出序列就可完全恢復(fù)原始文本。仿真實(shí)驗(yàn)表明， 本算法能夠滿足較好的不可見性，在格式攻擊上也表現(xiàn)出了較強(qiáng)的魯棒性，在提取水印和恢復(fù)原始文本時(shí)，具有較強(qiáng)的安全性。但本算法也有一定的不足，如不能抵抗針對內(nèi)容的攻擊，這將是今后需要進(jìn)一步研究的問題。

[1] Feng J B, Lin I C, Tsai C S, et al, Reversible watermarking:current status and key issues[J]. International Journal of Network Security, 2006, 2(3):161-171.

[2] 葛秀慧，田浩，郭立甫等. 信息隱藏原理及應(yīng)用[M]. 北京： 清華大學(xué)出版社，2008: 107-116.

[3] 黃華，齊春，李俊等. 文本數(shù)字水印[J]. 中文信息學(xué)報(bào)，2001, 15(5): 52-57．

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

[5] Thodi D M, Rodriguez J J. Reversible Watermarking by Prediction-Error Expansion[C]//Proceedings of the IEEE Southwest Symposium on Image Analysis and Interpretation, on Image Analysis and Interpretation, 2004,5:21-25.

[6] Hu Yongjian, Lee HeungKyu, Li Jianwei. DE-Based Reversible Data Hiding With Improved Overflow Location Map [J]. IEEE Transactions on Circuits and Systems for Video Technology, 2009, 19(2): 250-260.

[7] Chrysochos E, Varsaki E E, Fotopoulos V, et al.High capacity reversible data hiding using overlapping difference expansion[C]//Proceedings of Image Analysis for Multimedia Interactive Services,London, 2009:121-124.

[8] Coltuc, Dinu. Improved embedding for prediction-based reversible watermarking[J]. IEEE Transactions on Information Forensics and Security, September 2011, 6: 873-882.

[9] 劉志杰. 基于自然語言的文本可恢復(fù)水印研究[D]. 湖南: 湖南大學(xué), 2010.

[10] 姜傳賢，陳孝威. 魯棒可逆文本水印算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2010,22(5): 879-885.

[11] Topkara M, Topkara M, Mercan, et al. The hiding virtues of ambiguity: Quantifiably resilient watermarking of natural language text through synonym substitutions[C]//Proceedings of ACM Multimedia and Security Workshop(MMSEC’07), 2006:164-174.

[12] 甘燦，孫星明，劉玉玲，等. 一種改進(jìn)的基于同義詞替換的中文文本信息隱藏方法[J]. 東南大學(xué)學(xué)報(bào)，2007, 37, Sup(Ⅰ): 137-140.

[13] 張宇，劉挺，陳毅恒,等. 自然語言文本水印[J]. 中文信息學(xué)報(bào)，2005, 19(1): 56-62．

[14] Zheng Xueling, Huang Liusheng, Chen Zhili,et al. Hiding Information by Context-Based Synonym Substitution[C]//Proceedings of Digital Watermarking - 8th International Workshop Proceedings, Guildford, United kingdom, 2009: 162-168.

[15] Wanxiang Che, Zhenghua Li, Ting Liu. LTP: A Chinese Language Technology Platform[C]//Proceedings of the Coling 2010:Demonstrations, Beijing, China, 2010: 13-16.

[16] Sougou Labs. SougouR[DB/OL]. http://www.sogou.com/labs/dl/r.html, 2011

[17] 向華，曹漢強(qiáng)，伍凱寧等. 一種基于混沌調(diào)制的零水印算法[J]. 中國圖象圖形學(xué)報(bào)，2006, 11(5): 720-724.

Reversible Text Watermarking Algorithm Based on Prediction Error Expansion

FEI Wenbin1, TANG Xianghong1, 2, WANG Jing1, LIN Xinjian1

(1. School of Communication Engineering, Hangzhou Dianzi University, Hangzhou， Zhejiang 310018, China; 2.School of Information Engineering, Hangzhou Dianzi University, Hangzhou， Zhejiang 310018, China)

In order to avoid the permanent change of the text content caused by watermark embedding, this paper proposes a reversible watermarking algorithm for Chinese text document based on prediction error expansion englightened by the reversible watermarking for the image. Taking the sentence as the unit, The algorithm selects the words to be replaced according to the size of context collocation degree, and then realizes the embedding by the prediction error expansion and Chaos Sequence. Results show that this algorithm not only has the higher security, but also can extract watermark effectively while maintaining an exact restoration of the original text.

reversible watermarking; prediction error expansion; text document; collocation degree; chaos sequence

費(fèi)文斌(1986—)，碩士，主要研究領(lǐng)域?yàn)橥ㄐ啪W(wǎng)絡(luò)與信息安全技術(shù)。E?mail：feiwenbin111@sina．com唐向宏(1962—)，博士、教授，主要研究領(lǐng)域?yàn)閿?shù)字水印、圖像修復(fù)、多載波通信等。E?mail：tangxh@hdu．edu．cn王靜(1989—)，碩士，主要研究領(lǐng)域?yàn)橥ㄐ啪W(wǎng)絡(luò)與信息安全技術(shù)。E?mail：842098130@qq．com

1003-0077(2015)01-0133-06

2013-03-12 定稿日期： 2013-06-12

TP391

A