基于图论的文本数字水印技术

计算机研究与发展 ISSN 100021239ΠCN 1121777ΠTP Journal of Computer Research and Development 44 (10) : 1757～1764 , 2007 　收稿日期 :2006 - 04 - 10 ;修回日期 :2007 - 06 - 19 基于图论的文本数字水印技术 刘 　东1 ,2 　孙 　明1 　周明天1 1 (电子科技大学计算机科学与工程学院 　成都 　610051) 2 (反应堆设计技术国家级重点实验室 　成都 　610041) (Liudong73 @yahoo1com) A Text Digital Watermarking Technology Based on Graph Theory Liu Dong1 ,2 , Sun Ming1 , and Zhou Mingtian1 1 ( School of Com puter Science and Engineering , U niversity of Elect ronic Science and Technology of China , Chengdu 610051) 2 ( N ational Key L aboratory of Reactor System Design Technology , Chengdu 610041) Abstract 　Because of text’s properties , it’s so difficult to find perfect algorithms of embedding watermark into text documents , when compared with other media1 Nowadays , text watermarking technologies is far behind other multimedia watermarking technologies such as images , audios , etc1 A novel text digital watermarking technology based on graph theory is presented in this paper1 Through changing its topology structures of a character or st ring , different figures are schemed out , which represent the same semanteme1 Then those figures are mapped on graphs of graph theory , and the graphs or their properties should be correctly encoded in order to denote different watermarking information1 The mathematic models of embedding and detecting watermarking are also described , and the experimental methods of robustness and visual influence , as well as the relative results are given1 Finally , general rules of removing attack on text watermarking system is proposed , and the attack2resisting capability and methods of this text digital watermarking is analyzed in detail1 According to the experimentation and analysis , the text watermarking technology has the following advantages : great capacity of watermarking , st rong robustness , little visual influence and quite good attack2resisting capability1 With this technology , it is more convenient to embed watermark into characters for ideograph languages such as Chinese and Korean , while it is suitable for embedding watermark into strings for alphabetic languages such as English and French1 Key words 　text digital watermarking ; topology structure ; figures of a character or st ring ; graph theory ; encoding ; rules of removing attack 摘 　要 　由于文本自身的一些特点 ,相对于其他的媒体 ,在文本中嵌入数字水印更加困难1 这造成了当 前文本数字水印技术的发展远远落后于其他数字水印技术1 提出了一种新的基于图论的文本数字水印 技术 ,通过适当改变字符或字符串的拓扑结构 ,设计出语义上相同的字符或字符串的多种字形 ,并将这 些字形映射为图论中的“图”,对“图”或者“图”的特征量进行恰当的编码 ,利用这些编码来表示数字水 印 ;描述了水印嵌入、 检测 工程第三方检测合同工程防雷检测合同植筋拉拔检测方案传感器技术课后答案检测机构通用要求培训 方法的数学模型 ;给出了鲁棒性和视觉影响试验方法与结果 ;提出了文本数字 水印系统通用去除攻击准则 ,并分析了这种水印的抗攻击性能与方法1 通过实验与分析可知 ,该文本数 字水印技术具有水印容量大、鲁棒性强、视觉影响小、抗攻击能力强的特点1 使用这种技术 ,在字符中嵌 入水印对于汉语、韩语等象形文字具有一定的优势 ,而英语、法语等字母文字适于在字符串中嵌入水印1 关键词 　文本数字水印 ;拓扑结构 ;字符 (串)字形 ;图论 ;编码 ;去除攻击准则 中图法分类号 　TP391 ; TP309 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 　　当前 ,数字水印技术已经快速地发展起来[1 ] , 文本数字水印是数字水印技术的一个重要研究领 域1由于文字是人类传递信息最主要的媒介 ,文本数 字水印技术的重要性是毋庸置疑的[223 ]1 现有技术中 ,主要的文本水印嵌入算法有利用 行移、字移、字符间距、像素个数奇偶、黑白像素比 例、逻辑不变量、水平笔划宽度调整、区域亮度调整、 随机位置序列、不可见编码等方法在文本中嵌入水 印信息[224 ]1 这些算法都不同时具有水印容量大、鲁 棒性好、对人的视觉影响小、抗攻击性能好的特点 , 这制约了文本数字水印技术的进一步发展和实际应 用1 当前 ,文本数字水印这一领域的研究成果和应 用远远落后于图像水印、视频水印等其他的数字水 印领域 ,这与文本数字水印应该处于的重要地位是 不匹配的1 本文提出一种新的基于图论的文本数字水印 , 其基本原理在于通过适当改变字符 (或者字符串)的 拓扑结构 ,设计出语义上相同的字符 (或者字符串) 的多种字形 ,并将这些字形映射为图论中的“图”,进 而对“图”及“图”的特征量进行恰当的编码 ,利用这 些编码来表示数字水印信息1 1 　字形设计 由于不存在特定的标准 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 字符精确的拓扑结 构 ,现实生活中 ,人对字符拓扑结构的感觉是模糊 的 ,多种拓扑结构的字符外形均可以表示同一语义 的字符1 利用这一特点 ,通过恰当改变字符的拓扑 结构 ,能够为语义上相同的同一字符设计出多种字 符外形1 例如 ,可为各种典型的字符设计出如图 1 所示的字形1 对于字符串的不同字形设计方法 ,除了分别改 变单个字符的拓扑结构的方法外 ,还可以通过改变 组成字符串的各字符之间的连断关系来改变字符串 的拓扑结构 ,也可综合这两种方式进行设计1 字符 串多种字形设计的示例如图 2 所示1 Fig1 1 　Examples of different structure figures of a character1 图 1 　字符的多种字形示例 Fig1 2 　Examples of different structure figures of a string1 图 2 　字符串的多种字形示例 　　可以将字符串看成一个有复杂拓扑结构的字 符 ,就字形设计思想来说 ,与单个字符没有本质不 同1为简便起见 ,本文主要内容仅针对字符进行讨 论 ,字符串的情况可以简单类推1 通常 ,字符结构越复杂其拓扑结构可能的变化 越多 ,同时 ,同一字符的拓扑结构变化越多越大 ,对 人视觉的影响越大1 考虑到对人视觉影响的因素 , 本文建议采用改变完整笔划之间的连断关系的方法 来改变字符的拓扑结构 ,而不推荐将一个完整的笔 划分成不同的部分1 在这一设计原则下 ,我们针对 GB2312 规定的汉字字符集合进行了设计与测试 , 采用了 WINDOWS2000 操作系统缺省的“宋体”字 体 ,结果是 :大约 10 %～15 %的字符最多可有 2 种 不同拓扑结构 ,可携带 1b 水印 ;35 %～50 %的字符 最多可有 4 种不同拓扑结构 ,可携带 2b 水印 ;25 % ～35 %的字符最多可有 8 种不同拓扑结构 ,可携带 3b 水印 ;10 %～15 %的字符最多可有 16 种及以上 的不同拓扑结构 ,可携带 4b 水印 ;只有小于 1 %的 汉字和大多数的标点符号很难改变其拓扑结构 ,例 如“一、二、十”等1 与此对应的是 ,英语字符结构简 单 ,设计多个不同拓扑结构的字形相对比较困难1 在此意义上 ,以汉语为代表的象形字符相对于以英 语为代表的拉丁字符来说有明显的优势1 对于英 语 ,通过改变单词 (字符串) 中字符的连断关系来改 变整个单词的拓扑结构更为合理1 2 　字符字形的映射 对于任意的可见字符字形 s ,存在特定函数 f g , 使得 s 可以惟一映射到图论中的一个“图”g ,即 f g : S →G , S = {所有可见字形集合} , G = { g : g = ( V ( g) , E ( g) , f g) }1 同时 ,也存在函数 f c ,使得 s 可以 惟一映射到表示其语义的字符 c ,即 f c : S →C , C = {所有可见字符集合}1 注 :本文所有集合、关系与函 8571 计算机研究与发展 　2007 , 44 (10) © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 数的表示方式见文献[5 ] 1 f c 可通过 OCR 技术实现 , f g 通过字形映射规 则实现[628 ]1 字符“王”不同字形的映射示例如图 3 所示 : Fig1 3 　Example of mapping figures of a character on graphs1 图 3 　将字符字形映射为“图”的示例 在图 3 中 ,“王”的多种字形如 (321) 所示 ;其映 射的无向图如 (322) 所示 ,此时 , f g 的映射规则是将 字形笔划的顶点、交叉点映射为“图”的节点 (端点) , 而连接顶点、交叉点之间的笔划映射为“图”的边 ; (321) 映射的有向图如 (323) 所示 ,此时 , f g 的映射 规则需要在无向图的映射方式上定义空间顺序规 则 , (323)中以字形的自然位置为基准 ,按照从左到 右 ,从上到下的方向顺序确定“图”的方向1 针对可见 字符集合 C ,字符、字符字形及“图”的映射关系如图 4 所示 : Fig1 4 　Mapping relationship between characters , figures and graphs1 图 4 　字符、字形及“图”的映射关系 图 4 中 ,定义 G′= { gn : Πi ≠j , gi á µ gj , gn ∈ G} ,符号“µ”表示“图”与“图”同构 ,“ á µ”表示不 同构 ; Q ij = { s ijk : Πm ≠n , f c ( s ijm ) = f c ( s ijn ) = ci , f g ( s ijm ) µ f g ( sijn) ; s ijk ∈S } ; Q′= { Q ij : Πs inp ∈Q in , Πs imq ∈Q im , Πm ≠n , f g ( s im p) á µ f g ( si nq) , f c ( s im p) = f c ( s inq) = ci , i = 1～ | C| }1 注 : s ijk为 S 中的元素 ,其下标 i 为与字符 ci对 应的字形集合序号 , j 为不同构的字形集合序号 , k 为同构字形序号1 上述映射关系表明 ,同一字符的 多个字形映射的“图”有可能是同构的 ,例如图 3 (3 - 2) 中间的两个“图”1 事实上1 不同字符对应的 “图”也有可能同构 ,如字符“三”与“川”1 易知 Q′到 G′的映射为多对一映射 ,故存在 Q′到 G′的函数 f′g , 同时 ,存在二元函数 f cg : C , G′→Q′,组合 C , G′中 的元素可以惟一地映射到 Q′的元素上1 3 　字符字形的编码 本文用相同字符的不同拓扑结构的字形 (其映 射为不同构的“图”) 来表示隐藏水印信息 ,这需要对 字符字形进行编码1 在一定的视觉影响下 ,并不是 所有的字符都能设计出不同拓扑结构的字形 ,所以 仅对那些可以设计出不同拓扑结构的字形进行编 码 ,这些字形具有水印嵌入能力1 例如 ,图 4 中 c1 , c2 , c3具有携带水印信息的能力 ,而 c4没有1 同时 , 考虑到编码及应用的方便 ,对于一个字符对应的多 个映射为同构的“图”的字符字形 ,仅选取其中的一 个字形进行编码 ,即对于图 4 的 Q′集合 ,用 Q ij中的 任意一个字符字形 s ijk表示 Q ij1 定义 C′= {有水印 信息嵌入能力的字符集} , C′< C ; S′= { spq : f c ( spq) ∈C′} , S′< S ; H = {水印信息编码集合} , 则 C′, S′, H 应满足以下编码映射规则 : 1) 存在从 S′到 C′的一元函数 f r : S′→C′,同 时 ,存在从 S′到 H 的一元函数 f t : S′→H1 函数 f r 与 f t 均为映上函数1 2) 存在从 C′, H 到 S′的二元函数 f k : C′, H → S′, f k 为映上函数1 3) 定义 Q i = { sij : f c ( s ij ) = ci , sij ∈S′} ,则 Πci ∈C′, | Q i | > 1 1 4) Πij ≠m n f g ( s ij) á µ f g ( sm n) , s ij ∈S′, sm n ∈ S′, i = 1～| C′| 1 Fig1 5 　Rules of characters’figures coding1 图 5 　字形编码规则示意图 图 5 是上述规则的一个示例 ,字符 c1 , c2 水印 容量为 1b , c3水印容量为 2b1 S′为互不同构的字形 9571刘 　东等 :基于图论的文本数字水印技术 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 集合 , H 集合的二进制元素示例为 H = { 0 , 1 , 00 , 01 ,10 ,11}1 由于 f r , f t 与 f k 不存在解析式 ,需利用 关系数据库直接进行元素的映射 ,详细的编码实现 过程见文献[728 ]1 据集合 S′的定义 ,与第 2 节的二 元函数 f cg : C , G′→Q′相对应 ,同样存在函数 f′cg : C′, G′→S′,使得 C′, G′中的元素可以惟一映射到 S′的元素上1 这种针对字符字形映射的“图”进行编码的方 法 ,字符字形编码状态相对较多 ,文字携带水印信息 的容量较大 ,但编码过程及相应的检测过程都相对 复杂1 同时 ,由于对“图”的存储基于邻接矩阵或关 联矩阵 ,消耗的存储空间也较大1 为了简化上述编 码方法及后续的检测方法 ,可以针对“图”的某些特 征量进行编码 ,例如 ,“图”的顶点数量、边的数量、 “图”包含的连通子图 (“图”的分量) 的个数、“图”包 含的互不相同的圈的个数、“图”分割平面得到的 “面”的个数等1 对“图”的特征量的映射及编码方法 可以按照基于“图”的方法进行类推[728 ]1 4 　水印的加载与检测 将原载体文件中具有水印携带能力的字符串记 为序列{ pi} ,水印数据记为序列{ w j } ,加载了水印 的字符串记为序列{ qi}1 注意到{ p i}中各元素的水 印容量可能不一样 ,因此 ,要恰当地加载水印信息 , 需要将{ w j}进行分割变换 ,假设| { w j} | 足够大 ,能够 匹配整个{ pi}序列的水印容量 ,将分割变换表示为 w i = Segment ({ w j} , pi) , i = 0～| { pi} | - 11 (1) 　　分割后的序列{ w i}中的每个元素 w i 匹配对应 pi 的水印容量 ,有| { w i} | ≤| { w j} | 1 结合 C′, S′, H 间的映射规则 ,可知 : 水印加载模型为 { qi} = ∪ | { pi} | - 1 i = 0 f k ( pi , w i) pi ∈ C′w i ∈ H , (2) 符号 ∪表示字符的串联1 水印检测模型为 { w j} = ∪ | { w i} | - 1 i = 0 w i = ∪ | { qi} | - 1 i = 0 f t ( qi) qi ∈ S′1 (3) 　　在水印加载与检测模型的实现方法中 , 集合 C′, S′, H 中的元素保存在关系数据库中 ,其中 C′, H 的元素以编码形式保存 , S′中的元素以图形形式 保存 ,通过集合之间的关系表来实现 f r , f t 与 f k1 式 (2) 中的 p i 通常是以编码形式存在的字符 , w i 是以 编码形式存在的二进制数据 , p i , w i 均便于对应到 保存在关系数据库中的集合 C′, H 中的元素 ci , hi , 从而进一步通过式 (2) 实现水印的加载1 然而字符 字形 qi 及集合 S′中的元素 s i 是以图形方式存在的 , 式 (3) 中 ,难以自动确认 qi 等于 S′中哪一个具体元 素 s i ,这需要进一步根据字符字形映射的“图”和代 表其语义的字符编码进行间接对应1 即将式 (3) 变 为 { w j} = ∪ | { w i} | - 1 i = 0 w i = ∪ | { qi} | - 1 i = 0 f t ( f′cg ( f c ( qi) , f g ( qi) ) ) 1 (4) 　　如前所述 , f′cg : C′, G′→S′将字符与“图”映射 到该字符对应的特定字形上1 此时 ,同样用关系数 据库保存集合 C′, G′, S′中的元素及实现映射关 系 ,其中 , G′中的元素“图”以矩阵形式保存1 这样 , 图形形式存在的 qi 通过 f c ( qi ) 以编码形式对应 C′ 中的元素 ,通过 f g ( qi) 确认 qi 对应的“图”(矩阵形 式) ,进一步通过“图”的同构性判断与 G′中的元素 进行对应 ,最后 ,综合利用 f t , f′cg实现水印信息的自 动检测1 式 (4) 需要对 qi 映射的“图”与 G′中的“图”元 素进行同构性判断 ,而图的同构性判断是 NP 问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 , 其计算复杂性很高 ,对字符映射的“图”的同构性讨 论见文献[6 ,9 ]1 如果采用基于“图”的特征量的编 码方法进行字形的编码设计[728 ] ,则可以减小水印 检测的计算复杂性1 此时 ,相应的检测方法可以利 用表示“图”的矩阵直接计算出特征量进行比较 ,不 必进行同构性判断1 特别地 ,如果编码针对的特征 量仅涉及字符包含的连通子图个数、“图”分割平面 得到“面”的个数[728 ] ,甚至不需要将被检测的字符 字形映射为“图”,可将其转换为二值图像 ,然后计算 二值图像中互相邻接的、值分别为“0”或“1”的区域 的个数[10 ] ,即可直接求出这些特征量1 这样 ,就避开 了将字符字形映射为“图”,并进行同构性判断等复 杂过程 ,易于实际应用 ,但这是以牺牲字符的水印容 量为代价的1 5 　仿真实验 如图 6 所示 ,原载体文本图 6 (a) 共 55 个字符 (不包括标点符号) ,分别为这些字符设计多个不同 拓扑结构的字符字形 ,并根据这些字形映射的“图” 进行编码 ,以字符为单位携带隐藏水印信息1 总的 水印容量 115b ,在前 96b 嵌入以 ASC 码表示的水印 数据“Watermarking”,后 19b 全部置“0”,结果如图 6 (b)所示1 仔细辨认 ,可以发现图 6 (a) 与图 6 (b) 中 0671 计算机研究与发展 　2007 , 44 (10) © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 对应字符的拓扑结构大多数不同 ,这是加载水印的 结果1 以字符串为单位嵌入水印后的文本如图 6 (c) 所示 ,该文本通过组合改变字符的拓扑结构与字符 间的连断关系的方法来改变字符串的字形 ,并对字 符串包含的独立连通区域个数与独立封闭区域个数 之和的奇偶性进行编码 ,嵌入的水印数据为“a”1 详 细的字形设计、映射及编码实施方法见文献[728 ] , 结合字体文件进行的水印自动嵌入方法见文献[11 ]1 Fig1 6 　Example of embedding watermark in text1 (a) Original text ; (b) Example of watermark embedded in characters ; and (c) Example of watermark embedded in strings1 图 6 　水印嵌入文本示例1 (a) 原载体文本 ; (b) 嵌入了水印的字符示例 ; (c) 嵌入了水印的字符串示例 　　将图 6 (b) 作为实验对象 (纸质文件形式) ,对该 实验对象分别进行鲁棒性实验和人的视觉影响实验1 511 　鲁棒性实验 对实验对象进行如下操作 : 用普通扫描仪 (800dpi) 进行扫描 ,并按照 115 ,1 ,018 ,016 ,014 缩 放比例处理图像 ;将 1∶1 扫描得到的电子文件存为 J PEG格式 ,分别用 90 % ,70 % ,50 % ,30 %的压缩比 进行容量压缩 ;将 1∶1 扫描得到的电子文件按照 15°, 45°, 90°, 180°进行旋转 ; 用普通的复印机 (800dpi)进行复印 ,然后进行 1∶1 比例扫描 ;用普通 数码相机 (300 万 dpi) 进行拍照1 其中 ,缩放操作采 用 Matlab710 软件中 i m resize ( ) 函数进行 ,旋转操 作采用 rotate ( ) 函数进行1 对上述方法得到的实验 结果 (电子文件形式) 进行水印数据的误码率 (错误 bit 数Π水印数据总 bit 数)测试 ,结果如表 1 所示 : Table 1 　Results of Robustness Experiment 表 1 　鲁棒性实验结果 Operation Scale Error2Coding Ratio Resizing 115 0 1 0 018 0 016 11 % 014 26 % Rotating 0 Compressing 90 % 0 70 % 0 50 % 5 % 30 % 14 % Xeroxing 0 Taking Pictures 0 　　可以看出 ,放大、旋转、复印、拍照操作 ,对水印 数据几乎没有什么影响 ,对于缩小和压缩操作 ,水印 数据也具有很强的鲁棒性1 512 　视觉影响实验 Fig1 7 　Results of visual influence experiment1 图 7 　视觉影响实验结果 随机找出 60 个高中文化程度以上的测试人员 , 首先 ,要求每个人按正常速度阅读图 6 ( b) , 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 每 个人所需时间 ,统计平均阅读时间和最大阅读时间1 此后 ,将人员分为 3 组 ,20 人一组 ,3 组人员分别对 应下述 3 种实验条件独立地进行测试实验 :1) 不告 诉测试人员实验对象中存在水印信息 ,在规定的时 间 (10s ,30s ,60s ,90s)内要求找出实验对象的异常情 况 ;2)告诉测试人员实验对象中存在水印信息 ,而且 水印信息是加载到字符的字形中 ,在规定的时间内 要求找出实验对象中的字符与通常情况下看到的这 些字符有什么不同 ; 3) 将图 6 (a) 也提供给测试人 员 ,在规定的时间内要求找出两者的不同1 将每种 实验条件下能发现实验对象中任意一个字符拓扑结 构有异常的测试人员的百分比统计出来1 实验结果 如图 7 所示 : 1671刘 　东等 :基于图论的文本数字水印技术 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 可以看出 ,没有原载体文本对比之下 ,字符拓扑 结构的改变几乎不会给测试人员带来任何的视觉影 响 ;即便提供了原载体文本 ,在正常的阅读时间内 , 视觉影响也很微弱 ;阅读时间越短视觉影响越小1 6 　抗攻击性能分析 水印的攻击类型可以分为无意攻击 (鲁棒性攻 击)和恶意攻击 (安全性攻击和系统攻击) [3 ]1 本文 提出的文本水印的良好鲁棒性由前述鲁棒性实验得 以说明 ,对水印的系统攻击不属于水印本身技术的 范畴 ,本文不做讨论1 安全性攻击包括非授权去除、 修改、检测攻击[3 ]1 字符拓扑结构的定义是模糊的 ,不存在特定的 标准明确其精确的拓扑结构1 按照本文所述的方法 精心设计与编码的字符字形 ,与其他随机设计拓扑 结构的字符字形对于人的识别来说没有什么不同 , 难以被攻击者有效分辨 ,这种模糊特性可有效地防 止非授权检测攻击1 同时 ,在不损害字符原有语义 的情况下 ,去除字符携带的水印信息的惟一方法是 修改字符的拓扑结构 ,所以 ,对于本文的文本水印来 说 ,水印去除攻击和水印修改攻击在攻击实施方式 上是等价的 ,以下仅讨论去除攻击问题1 611 　去除攻击准则 不同于图像、声音、视频等媒体 ,人从文本中获 取信息不仅仅依靠视觉直接感知 ,而且存在抽象的 会意思维过程1 一方面 ,对于字符的识别来说 ,重要 的是最终获取字符内在的语义信息 ,另一方面 ,除了 语义文本水印 (注 :有容量限制、对文本内容存在较 大影响等缺陷)外 ,所有的其他文本水印所必需的冗 余信息均来自与语义无关的外在因素 ,如字符的形 状、拓扑结构、字体、颜色以及字符间距等1 这造成 了除语义水印外的文本水印都存在“录入去除攻击” 问题 ,即恶意攻击者人工录入嵌入了水印的文本 ,从 而重新获得新的文本 ,在去除水印的同时并不影响 原文 少年中国说原文俱舍论原文大医精诚原文注音大学原文和译文对照归藏易原文 本的语义内容1 这种文本水印的独特性质 ,表 明了追求绝对的水印数据安全是徒劳的1 对于一个 确定的嵌入了水印的文本文件 ,将实施“录入去除攻 击”所需的代价记为 A 01 在一定的条件下 , A 0 可以 被认为是一个常量 ,由此引出文本水印的去除攻击 准则 : 1) 有效攻击准则 一种去除攻击方法是有效的 ,必须使得该攻击 方法付出的代价 A 1 < A 01 2) 最佳防范准则 设一种防范去除攻击的方法所付出的代价记为 A 21 这种防范方法使得攻击者在不使用“录入去除攻 击”前提下 ,去除水印所必须付出的代价为 A′21 最佳 防范策略是在 A′2 > A 0 的条件下 , A 2 越小越好1 A 0 , A 1 , A′2 可以用时间作为统一的标准 , A 2 还 涉及有效水印容量、视觉影响等其他因素1 612 　抗去除攻击方法 不同字符的形状差异很大 ,利用人工智能技术 自动修改字符的拓扑结构是困难的 ,因而 ,在不影响 字符语义和对人不造成明显视觉影响的前提下 ,可 行的恶意去除攻击方式是人工修改字符的拓扑结 构1易知 ,人工逐个修改字符字形的拓扑结构所需要 的代价远远大于人工录入字符所需要的代价 ,即这 种恶意的完全去除攻击所需要的代价 A′µ A 0 ,根 据“有效攻击准则”,这种攻击并不是有效攻击 ,不会 被理性的攻击者使用1 更实际的攻击是“部分”去除攻击 ,即攻击者随 机地修改文本的部分字符拓扑结构 ,希望由此引起 整个水印的失效 ,从而达到去除水印的目的1 结合 纠错编码技术或扩频技术生成的水印 ,对这种“部 分”去除攻击引起的局部水印数据错误有一定的防 范和修复作用[12213 ] ,其防范与纠错性能与载体文本 中水印的平均误码率紧密相关1 设修改一个字符拓扑结构的平均时间为 T1 ,录 入一个字符的平均时间是 T2 ,携带了水印的文本总 字符数为 N ,“部分”去除攻击者可能修改的字符个 数为 n ,字符平均水印容量为 W ,根据“有效攻击原 则”: A 1 < A 0 Ζ n × T1 < N × T2 Ζ n < N × T2ΠT11 (5) 　　即攻击者最多会修改的字符数 M ax ( n) = N × T2ΠT1 ,由此可得最大平均水印误码率为 l = Max ( n) ×WN ×W = T2ΠT11 (6) 　　根据式 (6) 进一步在“最佳防范准则”指导下进 行水印设计与纠错、扩频参数的选择 ,纠错编码及扩 频实现见文献[12213 ]1 7 　结 　　语 综合实验及分析结果 ,可以看到本文提出的文 本数字水印技术有以下特点 :利用字符 (或者字符 串)拓扑结构定义的模糊性来嵌入水印信息 ,水印对 2671 计算机研究与发展 　2007 , 44 (10) © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 人的视觉影响小 ;以字符 (串)为单位携带水印 ,水印 容量大 ,而且使用方式灵活 ,不受文本格式、字符间 距离等因素的影响 ;水印仅与字符 (串) 字形的拓扑 结构有关 ,与大小、倾斜角度无关 ,缩放、旋转、打印、 拍照、压缩、扫描等操作对水印的影响小 ,水印的鲁 棒性好 ;恶意的水印去除攻击者难以自动修改字符 (串)的拓扑结构 ,攻击代价较大1 参 　考 　文 　献 [ 1 ] Yin Hao , Lin Chuang , Qiu Feng , et al1 A survey of digital watermarking [J ]1 Journal of Computer Research and Development , 2005 , 42 (7) : 1093 - 1099 (in Chinese) (尹浩 , 林闯 , 邱锋 , 等1 数字水印技术综述[J ]1 计算机研究 与发展 , 2005 , 42 (7) : 1093 - 1099) [ 2 ] S Low , N F Maxemchuk1 Performance comparison of two text making methods [J ]1 IEEE Journal on Selected Areas in Communications , 1998 , 16 (4) : 561 - 572 [ 3 ] Sun Shenghe , Lu Zheming , Niu Xiamu1 Digital Watermarking and Its Applications [ M ]1 Beijing : Science Press , 2004 ( in Chinese) (孙圣和 , 陆哲明 , 牛夏牧1 数字水印技术及应用[ M ]1 北京 : 科学出版社 , 2004) [ 4 ] Keith Ahern1 Invisible encoding of attribute data in character based documents and files [ P]1 U1S1A Patent , 09Π333632 , 1999 [ 5 ] S Lipschutz , M Lipson1 Outline of Theory and Problems of Discrete Mathematics1 Second Edition [ M ]1 New York : Mc Graw2Hill , 1997 [ 6 ] Guo Lianqi , Li Qingfen1 Recognizing restricted handwriting Chinese characters by using the graph theory algorithm [J ]1 Journal of Harbin Engineering University , 1998 , 19 (2) : 72 - 76 (in Chinese) (郭连骐 , 李庆芬1 利用图论算法识别限制性手写汉字 [J ]1 哈尔滨工程大学学报 , 1998 , 19 (2) : 72 - 76) [ 7 ] Liu Dong1 A method of information hiding communication and its applications in digital watermarking technology [ P]1 PCT International Patent , PCTΠCN2005Π001703 , 2005 (in Chinese) (刘东1 一种隐藏数据通信方法及其在文本数字水印技术中 的应用[ P]1 PCT 国际专利 ,PCTΠCN2005Π001703 , 2005) [ 8 ] Liu Dong1 A text digital watermark technology based on topology of alphabetic symbol [ P]1 Chinese Patent , CN20051006589319 , 2005 (in Chinese) (刘东1 基于字符拓扑结构的文本数字水印技术[ P]1 中国专 利 , CN20051006589319 , 2005) [ 9 ] Wataru Mayeda1 A testing method for isomorphic graphs and its application to character recognition [ C]1 China 1985 Int’l Conf on Circuits and Systems , Beijing , 1985 [ 10 ] Rafael C Gonzalez , Richard E Woods1 Digital Image Processing1 Second Edition [ M ]1 New York : Prentice2Hall , 2002 ( in Chinese) ( [美 ]Rafael C Gonzalez , Richard E Woods1 数字图像处理1 第 2版 [ M ]1 阮秋琦 , 阮宇智 , 译1 北京 : 电子工业出版社 , 2003) [ 11 ] Liu Dong1 A text watermarking technology based on storing hiding information in redundant code of symbol [ P]1 Chinese Patent , CN20051006714619 , 2005 (in Chinese) (刘东1 基于符号冗余编码的文本数字水印技术[ P]1 中国专 利 , CN20051006714619 , 2005) [ 12 ] C Berrou , A Glavieux1 Near optimum error correcting and decoding: Turbo2codes [J ]1 IEEE Trans on Communication , 1996 , 44 (10) : 1261 - 1271 [ 13 ] M George , J V Chouinard , N Georganas1 Digital watermarking of images and video using direct sequence spread spectrum techniques [ C]1 IEEE Canadian Conf on Electrical and Computer Engineering , Edmonton , Alta , Canada , 1999 Liu Dong , born in 19731 Ph1 D1 candidate of the School of Computer Science and Engineering , University of Electronic Science and Technology of China1 His main research interests include digital watermarking , information hiding and digital rights management (DRM) 1 刘 　东 ,1973 年生 ,博士研究生 ,主要研究方向为数字水印、 信息隐藏、数字版权保护等1 Sun Ming , born in 19781 Ph1 D1 candidate of the School of Computer Science and Engineering , University of Electronic Science and Technology of China1 His main research interests include data mining and digital watermarking1 孙 　明 , 1978 年生 ,博士研究生 ,主要研究方向为数据挖掘、 数字水印等1 Zhou Mingtian , born in 19391 Professor and Ph1 D1 supervisor of the School of Computer Science and Engineering , University of Electronic Science and Technology of China1 His main research interests include information security ,middleware and grid computing1 周明天 ,1939 年生 ,教授 ,博士生导师 ,主要研究方向为信息 安全、中间件、网格计算等1 3671刘 　东等 :基于图论的文本数字水印技术 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net Research Background With the development of the Internet and the digital technology , information security issues such as digital rights management and integrality guarantee , etc , have become more and more important problems1 Digital watermarking technology , as an important approach to information security technology , plays a key role to solve those problems , and has already succeeded in many research and application fields1 Although text is the most popular media in human being society , text watermarking technology is far behind other multimedia watermarking technology such as images , audios , etc1 Because of text’s properties , it’s so difficult to find perfect algorithms of embedding watermark into text documents1 A new text digital watermarking algorithm is proposed in this paper1 Through changing its topology structures of a character or string , different figures are schemed out , which represent the same semanteme , while those figures denote different watermarking information1 Graph theory is firstly used to be the mathematic foundation of text watermarking technology , and experimental results show that the algorithm has quite good performances such as great capacity of watermarking , strong robustness , and little visual influence1 Nowadays several Chinese and international patents are applied in this technique field and the related text watermarking system has been established1 The system embeds print audit data and digital finger information as text watermark into text documents , in order to control unauthorized print and protect digital rights1 第 8 届中国粗糙集与软计算学术会议、第 2 届中国 Web 智能学术研讨会、 第 2 届中国粒计算学术研讨会联合学术会议( CRSSC2CWI2CGrC2008) 征文通知 　　由中国人工智能学会粗糙集与软计算专业委员会和中国计算机学会人工智能与模式识别专业委员会主办、河南师范大 学承办的“第 8 届中国 Rough 集与软计算学术会议 (CRSSC2008)”、“第 2 届中国 Web 智能学术研讨会 (CWI2008)”和“第 2 届 中国粒计算学术研讨会 (CGrC2008)”拟定于 2008 年 8 月 22 日至 8 月 24 日在河南省新乡市召开1 现将有关征文事宜通知如 下 ,请相关研究人员踊跃投稿和参会1 征文内容 (主要包括 ,但不局限于以下方面) Rough 集与软计算 :Rough 集理论及应用 ,计算智能 ,机器学习 ,神经网络 , Fuzzy 集理论及应用 ,软计算的逻辑基础 ,软计 算及其应用 ,概念格多准则决策分析 ,近似推理与不确定性推理 ,知识发现与数据挖掘 ,数据仓库 ,情感计算 ,模式识别与图像 处理 ,生物信息与生物计算 ,演化计算 ,智能信息处理 ,其他有关领域 Web 智能 : 智慧网络 Web ,Farming 与 Web 挖掘 ,数据和知识网络 ,集成智能系统 ,认知 WI 模型 ,基于 Web 的智能信息系统 ,Web 信 息安全 ,智能 Agent ,网络支持系统 ,语义 Web ,网络推理机 ,Web 信息过滤 ,Web 信息抽取 ,Web 服务 ,其他有关领域 粒计算 : 粒计算基础 ,词计算 ,商空间理论及应用 ,粒逻辑与推理 ,信息粒化 ,信息粒的表示 ,区间分析 ,聚类分析 ,邻域系统 ,认知信 息学 ,双 (异质)聚类 ,多层次数据挖掘 ,数据仓库的多粒度聚合 ,基于粒计算的模式分析与处理 ,基于粒计算的 Web 智能 ,其他 相关领域 投稿要求 1) 投往会议的稿件必须是原始的、未发表的研究成果、研究经验或工作突破性进展报告 ,一般不超过 6000 字1 2) 论文包括中英文题目、作者姓名、单位、籍贯、职称、地址、邮编、E2mail 地址、联系电话 ,中英文摘要 (一般不超过 300 字) 、关键词、中图分类号、正文和参考文献 ;请将基金资助项目及批准号标注于首页页脚 ;参考文献的著录请包含 :作者、论文 名、期刊名 (书名、出版社、出版地) 、出版年、卷、期、页码等项目1 3) 录用论文在《计算机科学》为会议出版的论文专集上发表1 根据论文评审和报告情况 ,确定优秀论文并推荐给各期刊正 刊发表1 在各期刊正刊发表前 ,作者须根据审稿意见和会议交流情况 ,扩充并修改论文 ,然后提交稿件给各期刊1 推荐的期刊 正刊包括 :《Web Intelligence and Agent Systems》(