(南開大學(xué) 信息技術(shù)科學(xué)學(xué)院 嵌入式系統(tǒng)與信息安全研究室， 天津 300071)

摘 要：從漢字分類思維的角度，在充分利用漢字的二維象形性以及人眼視覺冗余特性的基礎(chǔ)上，提出一種將結(jié)構(gòu)化漢字字形拆分再重組的自然型文本水印算法。該算法通過漢字字形的拆分，增加了文檔內(nèi)容編碼冗余，提高了水印信道容量，并通過調(diào)整漢字顯示屬性，增強(qiáng)水印的隱蔽性。最后對其進(jìn)行實(shí)驗(yàn)驗(yàn)證，證明該算法兼具格式水印隱蔽性和語義水印魯棒性的雙重優(yōu)點(diǎn)，并具有嵌入空間大的特點(diǎn)。

關(guān)鍵詞：漢字結(jié)構(gòu);自然型文本水印;格式水印

中圖分類號：TP309文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2009)04-1520-03

Natural text watermarking algorithm based on Chinese characters structure

LI Qing-cheng，ZHANG Zhen-hua，ZHANG Jin

(Embedded System Information Security Lab， Nankai University， Tianjin 300071， China)

Abstract:From the perspective of Chinese characters classification，this paper made full use of pictographic characters of the two-dimensional and the human visual characteristics of redundancy， and presented a novel natural text watermarking algorithm based on Chinese characters glyph rebuild. In the algorithm，spited the glyph of Chinese characters to two other’s， increasing the content of the document coding redundancy， enhancing the watermark capacity， and by adjusting the properties of characters displaying，enhanced the watermarking imperceptibility.Finally， the experiment proves that the algorithm has both advantages of imperceptibility of format watermarking and robustness of the semantic watermarking， and has large capacity characte-ristics.

Key words:Chinese characters structure; natural text watermarking; format watermarking

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，數(shù)字媒體的傳播和獲取越來越方便，然而由于數(shù)字出版物易于修改和拷貝的特點(diǎn)，隨之而來的版權(quán)保護(hù)問題卻一直制約著數(shù)字出版業(yè)的快速發(fā)展。因此，數(shù)字水印作為一種自然型版權(quán)保護(hù)方案越來越受到人們的關(guān)注。

數(shù)字水印作為一種版權(quán)保護(hù)技術(shù)主要是利用載體的數(shù)據(jù)冗余和人眼視覺冗余特性將版權(quán)信息隱藏到數(shù)字作品中，起到保護(hù)數(shù)字作品版權(quán)的作用，并且不影響原作品的使用，具有很好的自然性。因此當(dāng)前許多研究成果主要還是基于圖像、視頻、音頻等具有大量冗余空間的載體水印算法。不幸的是，由于文本字符所固有的原子性問題， 冗余空間非常小，大大增加了文本數(shù)字水印的魯棒性和有效載荷問題的解決難度， 從而使得文本數(shù)字水印的研究成果少之又少。

由于文本文檔的冗余空間小的特性，基于文本的水印技術(shù)主要還是如何找到一個較大的嵌入空間。當(dāng)前基于文本的水印技術(shù)主要可以分為如下三類：基于格式的文本水印算法、基于擴(kuò)展空間的水印算法和基于自然語言處理的文本水印算法。它們分別從不同的角度尋找更大的嵌入空間。

1）格式水印[1～4] 基于文檔格式的水印算法主要是通過改變文本文檔的格式，把水印信息隱藏到文檔的格式信息之中。主要方法有：行間距編碼[1]——通過垂直移動文本行來編碼水印信息，有很強(qiáng)的魯棒性，不足的是嵌入的信息量少；字間距編碼[2]——通過將文本行中的單詞水平移位來插入信息，它不能實(shí)現(xiàn)盲檢測，而且由于漢字特性，其不適合中文；特征編碼[3]——通過改變文本中某些字符的特征（顏色、字體等）隱藏信息。Brassil等人提出的這類通過修改文檔字間距(或行間距、字符特征) 來嵌入水印信息的算法由于完全依賴于文檔格式， 水印信息嵌入在文本內(nèi)容之外， 只要對文本的格式進(jìn)行修改， 嵌入的水印信息便蕩然無存。

2）擴(kuò)展水印[5～8] 為了尋找更大的嵌入空間，基于擴(kuò)展空間的水印算法通過把文檔轉(zhuǎn)換為圖像格式，大大增加了載體信息冗余，文檔就有足夠的空間來嵌入水印。劉東等人[7]把漢字看做圖像，基于漢字圖像的連通域嵌入水印信息。這樣，文檔即使經(jīng)過打印，通過再掃描成圖像，水印信息仍能識別出來。這種方法最大的問題是文檔圖像化后，文檔的體積顯著增加，而且水印的檢測難度很大。

3）語意水印[9，10] 無論是格式水印還是擴(kuò)展水印都無法抵抗OCR軟件的字符識別或人工的重錄入(retyping)攻擊。Purdue 大學(xué)的Atallah等人[9]提出了基于自然語言處理的水印技術(shù)， 該技術(shù)是在不改變文本原意的前提下， 通過調(diào)整句子的結(jié)構(gòu)以嵌入水印信息到文檔內(nèi)容中的一種信息隱藏技術(shù)。由于是將水印嵌入在文檔內(nèi)容之中， 與基于文本格式的水印算法相比具有良好的抗攻擊性。但是目前像分詞、句法分析、語句修改等自然語言處理技術(shù)還不成熟，使用這種技術(shù)嵌入水印后的載體文本容易發(fā)生語義改變的情況，且中文的表達(dá)比英文豐富得多，稍微進(jìn)行一下詞語替換，語義或句法的修改就不能表達(dá)作者的原意，甚至讓人難以理解或產(chǎn)生歧義。

格式水印把水印信息隱藏于格式當(dāng)中，具有很好的隱蔽性，但其魯棒性較差，而語義水印依賴于對自然語言的處理，通過修改文檔內(nèi)容，以犧牲文檔原意為代價(jià)獲得較好的魯棒性。那么，是否有一種兼具格式水印和語義水印優(yōu)點(diǎn)的水印嵌入方法？Sun等人[11，12]用漢字?jǐn)?shù)學(xué)表達(dá)式將漢字字形表示成漢字基本組件的運(yùn)算式，從而尋找水印嵌入空間。但其算法復(fù)雜，漢字?jǐn)?shù)學(xué)表達(dá)式庫的建立工作量巨大，水印提取依賴于格式信息。本文經(jīng)過對漢字結(jié)構(gòu)和分類的深入研究，充分利用漢字的象形和會意特性，以及人類心理認(rèn)知特性，提出一種基于漢字字形結(jié)構(gòu)的自然型文本水印算法（CSNT）。CSNT通過將某些表具體概念的漢字拆分為表抽象概念的部首漢字和另一個漢字，而在顯示時，通過格式調(diào)整將拆分后的兩個漢字字形拼接為原漢字字形。這樣，通過把一個漢字編碼擴(kuò)展為兩個漢字編碼，提高水印信道容量，并把水印信息嵌入文檔內(nèi)容當(dāng)中，而且不影響文檔原意，具有很好的自然性。通過對文檔格式調(diào)整，保證算法具有很好的隱蔽性。

1 算法的基本思想

漢字作為形、音、義三者統(tǒng)一的文字系統(tǒng)，字符的數(shù)量巨大，字形結(jié)構(gòu)復(fù)雜。這就為漢字文本水印的嵌入提供了極大的容量空間潛力。通過對漢字分類思維的認(rèn)識[13]：漢字中的一些偏旁部首代表著某一類事物，起著抽象分類的作用。其作用于某些具有具體意義的字符，形成另一個有具體意義的漢字，使?jié)h字的表意功能增強(qiáng)。例如表抽象意義的“亻”字作用于“木”，形成另一個有具體意義的“休”字。而從漢字的字形結(jié)構(gòu)來看，“休”字的字形可以通過“亻”和“木”這兩個字的字形共同描繪。

CSNT算法充分利用漢字的這種字形結(jié)構(gòu)特征，通過漢字的拆分，將文檔中特定漢字的編碼進(jìn)行擴(kuò)展轉(zhuǎn)換，這樣文檔的字符編碼就出現(xiàn)冗余空間。擴(kuò)展的漢字編碼作為攜帶水印比特信息的實(shí)體，為嵌入水印提供了空間。由于人的心理認(rèn)知特性，作為象形文字“亻木”的共同出現(xiàn)，閱讀者也會自然糾正識別為“休”字，從而不會造成任何語義的錯誤表達(dá)。然而，通過調(diào)整“亻木”的顯示格式，“亻木”兩個漢字的字形將與“休”的字形相同，通過肉眼不易發(fā)現(xiàn)其區(qū)別，從而達(dá)到更好的隱藏效果，具有良好的隱蔽性。

為了更清楚地陳述CSNT算法原理，首先解釋算法中用到的數(shù)學(xué)符號：

φ={阝纟忄亻刂扌冫攵礻饣彡钅犭…}。φ是常用的左右結(jié)構(gòu)的偏旁部首集，每個偏旁部首都只具有抽象意義，一般不會作為有意義的漢字在文檔中單獨(dú)使用。這個特性有利于下文中將詳細(xì)講述的水印提取算法的水印嵌入點(diǎn)的快速定位。

Ω={C|C為所有的漢字字符}。Ω中包含所有的漢字字符，是漢字字符的全集。

Φ={c|c是具有上文所述特性的漢字：左右結(jié)構(gòu)的一級或二級漢字，且偏旁部首屬于φ中，而另一部分仍屬于Ω}。Φ中包含本實(shí)驗(yàn)中所有的可嵌入水印的漢字集合。其構(gòu)成一個具有“休亻木”形式的可查找數(shù)據(jù)庫。

LEFT(c)返回漢字c的左半部分字形編碼的功能函數(shù)。返回值是φ中的偏旁部首或者另一漢字。

RIGHT(c)返回漢字c的右半部分字形編碼的功能函數(shù)。返回值是φ中的偏旁部首或者另一漢字。

2 嵌入提取算法

2.1 水印嵌入算法

輸入：中文文檔T（有格式或純文本的），水印信息W。

輸出：嵌有水印信息W的水印文檔Tw。

a）根據(jù)水印信息W生成bit位系列w={w1，w2，w3，…，wn}。重復(fù)擴(kuò)展w并以0x55aa為擴(kuò)展分界符，生成水印嵌入系列β={β1，β2，β3，β4，…}。

b）依次取文檔T中的每一個漢字字符C，若字符CΦ，重復(fù)b）；否則，轉(zhuǎn)c）。

c）若當(dāng)前需要嵌入的bit位βi是0，轉(zhuǎn)b）；否則，轉(zhuǎn)d）。

d）用LEFT(C)和RIGHT(C)兩個漢字代替字符C，若當(dāng)前文檔是有格式的文檔，調(diào)整LEFT(C)和RIGHT(C)的詞間距，使它們的字形顯示與字符C的字形盡可能一樣。

e）文檔T嵌入完畢，退出；否則，轉(zhuǎn)b）。

經(jīng)過實(shí)驗(yàn)分析，本算法具有很大的嵌入容量。所以，冗余嵌入水印信息，并以0x55aa作為嵌入水印的分界符，增加了水印的魯棒性。嵌入過程中，若是純文本格式，則簡單地用LEFT(C)和RIGHT(C)替換C，顯然顯示效果很差，但也不會造成閱讀理解差錯。若需要嵌入水印的文檔是有格式信息的，則通過調(diào)整字符顯示屬性使LEFT(C)和 RIGHT(C)的字形顯示與C的字形相差無幾。這樣就完全隱藏了水印的嵌入，具有很高的魯棒性和隱蔽性。

2.2 水印檢測算法

輸入：嵌有水印的文檔Tw

輸出：水印信息w

a）依次取Tw中的每個字符C，若字符C∈Φ，說明嵌入了bit 0信息，重復(fù)a）；否則，轉(zhuǎn)b）。

b）若Cφ，即C不是一個偏旁部首，因此不是一個嵌入點(diǎn)，轉(zhuǎn)a）繼續(xù)判斷下一個漢字字符；否則轉(zhuǎn)c）。

c）若C是左偏旁，則取文檔Tw中C的下一個字符next（C），查找集合Φ，判斷C和next（C）字形組成的漢字是否在Φ中，若在，表明此位置嵌入了bit 1 信息。轉(zhuǎn)a）繼續(xù)操作。

d）若C是右偏旁，則取文檔Tw中C的上一個字符prev（C），查找集合Φ，判斷C和prev（C）字形組成的漢字是否在Φ中。若在Φ中，表明此位置嵌入了bit 1 信息。轉(zhuǎn)a）繼續(xù)操作。

e）水印位系列β={β1，β2，β3，β4，…}。提取完畢，從提取的bit系列中，以0x55aa為分隔符，提取含有可能被攻擊的n組冗余水印系列，根據(jù)多數(shù)投票機(jī)制，確定正確的水印信息w。

f）輸出水印信息w。

從提取算法可以看出，水印的檢測不依賴于格式，而只與文檔內(nèi)容相關(guān)，在確定水印信息時，利用嵌入時的冗余信息，保證該算法具有很高的魯棒性。

3 實(shí)驗(yàn)結(jié)果及分析

CSNT算法已經(jīng)在純文本和Microsoft Word 2003 兩種實(shí)驗(yàn)環(huán)境中實(shí)現(xiàn)。與Sun等人[11]提出的基于漢字組件的漢字?jǐn)?shù)學(xué)表達(dá)式相比，CSNT算法有以下優(yōu)點(diǎn)：

a）Sun等人從漢字的圖像顯示特性，硬性對漢字的顯示圖像進(jìn)行組件模塊式劃分：把所有的20 902個CJK漢字字符集都表達(dá)成580個基本字形組件的運(yùn)算，這不僅實(shí)現(xiàn)難度大，而且效率低。本文從漢字的分類思維出發(fā)，充分利用漢字的會意特性和已有漢字字庫中的字形冗余特性，只選取使用頻度最高的一級、二級漢字中的部分左右結(jié)構(gòu)的漢字作為水印嵌入點(diǎn)。而且被選中的高頻漢字的偏旁部首只能屬于集合φ。因?yàn)檫@些部首很少單獨(dú)作為漢字使用，在水印檢測時，就不會與正常使用的漢字產(chǎn)生沖突，所以算法具有很高的效率。在6 000多個一、二級高頻漢字中，符合本算法要求的就有1 700多個漢字，可以充分保證水印的嵌入容量。

b）由于Sun算法中水印載體漢字的隨意性，水印提取只能通過檢測嵌入點(diǎn)的詞間距來判斷嵌入信息，水印的提取完全依賴于格式信息。而本文的算法，由于嵌入載體數(shù)據(jù)庫的獨(dú)特性，水印嵌入和提取只依賴于文檔內(nèi)容，與格式信息無關(guān)，格式信息只起到隱藏水印嵌入點(diǎn)的作用，這樣就達(dá)到了水印的魯棒性和隱蔽性算法分離的效果，因此該算法也可以較好地應(yīng)用于純文本格式。

下面分別從算法的隱蔽性、水印容量和魯棒性對本算法的實(shí)驗(yàn)結(jié)果進(jìn)行分析。

3.1 嵌入隱蔽性分析

實(shí)驗(yàn)中，本文嵌入“克林頓編”這幾個代表版權(quán)信息的漢字在克林頓的回憶錄《我的生活》中，全文16 634字，共有2 520個嵌入點(diǎn)，所以，冗余嵌入“克林頓編”，并以“0101010110101010”位系列即0x55AA作為水印系列的開始和結(jié)束標(biāo)記。在水印嵌入時，針對每個嵌入點(diǎn)，每個漢字的字形通過OfficeAPI調(diào)整嵌入后的字符屬性，使嵌入點(diǎn)的兩個字符的字形與嵌入前的盡可能一樣。圖1是嵌入水印之前的文字，圖2是嵌入水印后的文檔顯示。為了便于嵌入前后顯示效果的對比，用黑點(diǎn)標(biāo)記出所有的嵌入點(diǎn)。

對比圖1和2可以看出，嵌入水印前后，文檔顯示變化很小，具有極好的隱蔽性。

3.2 水印容量分析

本文對科幻、歷史紀(jì)實(shí)、社會哲學(xué)、文學(xué)小說等各種類型的大量文檔進(jìn)行嵌入容量的統(tǒng)計(jì)，如圖3所示。

橫坐標(biāo)代表選取的文本樣例，本文選取各種類型的文檔40余篇；縱坐標(biāo)代表文檔的水印嵌入比特率（bit/漢字）。由圖中數(shù)據(jù)可以看出，各種不同文體的文檔，嵌入容量均可達(dá)到13%左右，這對于文本水印來說，嵌入容量已經(jīng)是一個飛躍。這也充分表明，本文所選取的可嵌入信息漢字具有很高的使用頻率。

3.3 水印魯棒性分析

由上文實(shí)驗(yàn)和分析發(fā)現(xiàn)，本算法具有很大的嵌入容量。因此，本文在水印嵌入時采用冗余嵌入，以增加算法的魯棒性。

由于文本水印最常見的攻擊為刪除攻擊，而本算法中，只有對嵌入點(diǎn)的攻擊，即拆分的漢字受到攻擊，才會對水印的提取產(chǎn)生影響，而對其他字符或者增加字符都不會影響水印信息。

現(xiàn)從理論上分析本算法對刪除和竄改攻擊的抵抗：設(shè)文檔的總字?jǐn)?shù)為N，待嵌入的水印信息為W bit。由圖3可以看出，本算法的嵌入率在e=13%左右，所以可嵌入的水印信息總量平均為N×13% bit；每次嵌入W bit的水印信息，還要同時嵌入16 bit的同步信息，所以文檔嵌入的水印冗余次數(shù)為

n=N×e/(W+16)=N×13%/(W+16)(1)

要保證水印的正確提取，必須至少有一組水印嵌入系列沒有被破壞，即至少有連續(xù)的水印內(nèi)容沒有被破壞的比率為

1/n=(W+16)/（N×e）=（W+16）/(N×13%)(2)

對于連續(xù)刪除，如連續(xù)前刪除和連續(xù)后刪除，由式（2）可得，抗刪除為1-(1/n)。對于本文的實(shí)驗(yàn)樣本之一《窮爸爸富爸爸》，N=121 659，嵌入水印信息“克林頓編”，W=64，由式（2）計(jì)算刪除率為99%時，仍可以正確提取水印，與實(shí)驗(yàn)結(jié)果相吻合。

對于隨機(jī)刪除，由于刪除的隨機(jī)性，每次對文檔的攻擊，有（13+13）/（100+13）的概率會對水印的提取造成影響，要保證水印的正確提取，必須保證一組水印沒有受到攻擊。假設(shè)刪除攻擊造成文檔的內(nèi)容刪除的比率為P，若需要以D的概率正確提取水印，則

[（n-1）/n]N×P×26/113≤D(3)

求解式（3）就可以計(jì)算出本算法能以D的概率正確提取水印時隨機(jī)刪除的最大容忍度。表1是對幾個實(shí)驗(yàn)文檔分別進(jìn)行最大力度的前刪除、后刪除和隨機(jī)刪除后仍能正確提取水印的分析表。

表1 水印攻擊分析

文檔總字?jǐn)?shù)容量前刪/%后刪/%隨機(jī)/%

1（傳記類）16 6332 520939512

2（武俠小說）445 12857 867999993

3（經(jīng)濟(jì)類）121 65918 528999975

4（網(wǎng)絡(luò)小說類）135 35416 718989978

由表1可以看出，當(dāng)文檔的字?jǐn)?shù)越多時，能夠容忍的攻擊力度也越大。在以后的繼續(xù)研究中，還可以對嵌入的水印加密，并重編碼，如利用海明碼的自糾錯和循環(huán)冗余特性，被破壞的水印系列中仍有部分的可利用信息，以幫助還原水印信息。水印算法將具有更好的魯棒性。

由于本算法水印嵌入在內(nèi)容中，所有的行移、字移和特征修改等基于格式的攻擊對本算法水印的提取沒有任何影響。

4 結(jié)束語

隨著網(wǎng)絡(luò)的快速發(fā)展，相對于傳統(tǒng)出版業(yè)出版物復(fù)本的生成和傳播的高成本，電子文檔副本的復(fù)制和傳播的零成本優(yōu)勢將大大推動電子出版業(yè)的發(fā)展。而文本水印對出版商和作者的版權(quán)保護(hù)將大大提高電子出版的積極性，進(jìn)而有力地推動電子出版業(yè)的發(fā)展。

本文從漢字分類思維角度出發(fā)，利用漢字的圖形顯示模式和人類心理認(rèn)知特性，提出的基于文本內(nèi)容的自然型漢字文本水印算法具有格式水印的隱蔽性和語義水印的魯棒性的雙重優(yōu)點(diǎn)，將在中文出版物的版權(quán)保護(hù)中起重要作用。CSNT算法已經(jīng)在津科電子的翰林電子書手持設(shè)備閱讀器平臺中實(shí)現(xiàn)，并取得了良好的效果。

參考文獻(xiàn)：

［1］

BRASSIL J，LOW S，MAXEMCHUK N，et al.Electronic marking and identification techniques to discourage document copying[J].IEEE Jon Select Areas in Commun，1995，13（8）:1495-1504.

[2]BRASSILJ，LOW S，MAXEMCHUKN F.Copyright protection for the electronic distribution of text documents[J].Proc of the IEEE，1999，87（7）：1181-1196.

[3]HUANG Ding，YAN Hong.Interword distance changes represented by sine waves for watermarking text images[J].IEEE Trans on Circuits and Systems for Video Technology，2001，11（12）:1237-1245.

[4]LOW S，MAXEMCHUK N.Capacity of text marking channel[J].Signal Processing Letters，2000，7(12):345-347.

［5］ 弋英民，李人厚，梅時春，等.一種基于文本行和對角側(cè)面特性的數(shù)字水印方法[J]. 小型微型計(jì)算機(jī)系統(tǒng)，2005，26(2):293-296.

[6]WANG Hui-qin，LI Ren-hou.A binary text digital watermarking algorithm[J].Acta Simulata Systematica Sinica，2004，16（3）:521-524.

[7]劉東， 陳松，周明天.基于字符拓?fù)浣Y(jié)構(gòu)的文本數(shù)字水印技術(shù)[J].小型微型計(jì)算機(jī)系統(tǒng)，2007， 28(5):812-815.

[8]SHIRALI-SHAHREZA M H，SHIRALI-SHAHREZA M.A new approach to Persian/Arabic text steganography [C]//Proc of the 5th IEEE/ACIS International Conference on Computer and Information Science.2006:310-315.

[9]ATALLAH M J，RASKIN V，CROGAN M，et al.Natural language watermarking: design， analysis， and a proof-of-concept implementation[C]//Proc of IH’01.Berlin:Springer，2001.

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

[11]SUN Xing-ming，LUO Gang，HUANG Hua-jun.Component-based digital watermarking of Chinese texts[C]//Proc of ACM International Conference Proceeding Series on Information Security.2004:75-81.

[12]SUN X Ming-ming，CHEN Huo-wang，YANG Li-hua，et al.Mathematical representation of a Chinese character and its applications[J].International Journal of Pattern Recognition and Artificial Intelligence，2002，16(8):735-747.

[13]李敏生.漢字哲學(xué)初探[M].北京：社會科學(xué)文獻(xiàn)出版社，2000.

[14]劉超，孫星明，周新民.基于模糊聚類方法的盲文本水印算法研究[J].計(jì)算機(jī)應(yīng)用研究，2007，24(2):148-150.