基于預測誤差擴展的可逆文本水印算法

費文斌，唐向宏，2，王 靜，林新建

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

?

基于預測誤差擴展的可逆文本水印算法

費文斌1，唐向宏1，2，王 靜1，林新建1

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

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

可恢復水印；預測誤差擴展；文本文檔；搭配度；混沌序列

1 引言

數字水印技術是利用載體數據中的隨機冗余，將秘密信息嵌入載體數據中，使其不被人的感覺系統發現，并且水印前后作品之間的失真通常可以達到視覺上的不可感知性。這種方法是把人們扭曲約束在一個人眼不能察覺的很小范圍內，但是在某些應用領域對載體數據的改變十分敏感，不允許載體數據永久損失，例如，醫療、軍事和司法等由于嵌入水印導致的載體改變會造成嵌入信息后載體質量的嚴重降低。因此一種稱為可逆水印的技術在近幾年得到了廣泛的關注。可逆水印要求解碼器不僅能提取水印信息，而且能將因嵌入水印而失真的數字載體無損地恢復[1-3]。

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

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

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

2 上下文搭配度計算與預測差擴展

2.1 上下文搭配度

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

圖1 詞與詞的搭配關系

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

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

2.2 預測誤差擴展與混沌映射

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

通過式(4)可轉換為二進制偽隨機數，從而產生偽隨機二進制序列。

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

3 算法原理與實現

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

3.1 嵌入算法

本算法的嵌入流程如圖2所示。具體實現步驟為：

圖2 算法嵌入流程圖

步驟1 分詞。對每個句子進行分詞，并確定詞語之間上下文的搭配關系。

步驟2 選詞。通過式(1)搭配計算，定位出文本中可替換的詞語，為預測誤差擴展作準備。具體實驗步驟如下：

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

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

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

步驟6 遍歷整個文本的句子。

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

3.2 提取算法

水印的提取為水印嵌入的逆過程。具體實現步驟如下：

因此，當lsb(p″e)=1，則水印w=1；當lsb(p″e)=0，則水印w=0。

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

3.3 可逆算法

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

步驟2 利用密鑰y0和B得到由混沌產生的二進制溢出序列，然后根據規則1，得到每個位置的分類信息。

步驟3 根據對應的分類信息，通過規則2，還原出每個位置的x′。

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

步驟5 遍歷整個文本，完成文本的恢復。

4 實驗結果與分析

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

圖3 原始文本

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

圖4 水印文本

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

文本再生攻擊是對原始文本進行重構；文本格式轉換是在文本的各種形式之間的轉換，如word轉化為txt；字體調整是將文本中的字體變換，如宋體變為仿宋體；刪除空格是將多余的空格去掉；標點符號統一修正是中英標點符號的互換。從表1中可以看出，對于這些文本格式攻擊都不會破壞水印信息，這是因為本算法通過自然語言處理技術嵌入水印信息，水印的嵌入發生在文本的內容中，在遇到格式攻擊時，不會破壞水印信息，具有較強的魯棒性。

表1 格式攻擊分析

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

圖5 恢復后的文本

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

圖6 初值不變、起始位置改變時的恢復文本

圖7 初值改變、起始位置不變時的恢復文本

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

圖8 初值和起始位置都改變時的恢復文本

圖9 閥值T改變時的恢復文本

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

表2 算法性能比較

5 結論

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

[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] 葛秀慧，田浩，郭立甫等. 信息隱藏原理及應用[M]. 北京： 清華大學出版社，2008: 107-116.

[3] 黃華，齊春，李俊等. 文本數字水印[J]. 中文信息學報，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] 劉志杰. 基于自然語言的文本可恢復水印研究[D]. 湖南: 湖南大學, 2010.

[10] 姜傳賢，陳孝威. 魯棒可逆文本水印算法[J]. 計算機輔助設計與圖形學學報，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]. 東南大學學報，2007, 37, Sup(Ⅰ): 137-140.

[13] 張宇，劉挺，陳毅恒,等. 自然語言文本水印[J]. 中文信息學報，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] 向華，曹漢強，伍凱寧等. 一種基于混沌調制的零水印算法[J]. 中國圖象圖形學報，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

費文斌(1986—)，碩士，主要研究領域為通信網絡與信息安全技術。E?mail：feiwenbin111@sina．com唐向宏(1962—)，博士、教授，主要研究領域為數字水印、圖像修復、多載波通信等。E?mail：tangxh@hdu．edu．cn王靜(1989—)，碩士，主要研究領域為通信網絡與信息安全技術。E?mail：842098130@qq．com

1003-0077(2015)01-0133-06

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

TP391

A