基于预测误差扩展的可逆文本水印算法

费文斌，唐向宏，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