矢量圖數字水印技術
2007-12-31 00:00:00任石秦茂玲劉弘
計算機應用研究 2007年8期
摘要：介紹了矢量圖數字水印的基本要求，并對二維矢量圖數字水印技術進行了分析、比較。二維矢量圖數字水印主要采用基于特征集合的方式進行水印信號的嵌入，其關鍵是對矢量圖進行特征分析，并找出好的模型表達方式。
關鍵詞：矢量圖； 數字水印； 水印信號
中圖分類號：TP391文獻標志碼：A
文章編號：1001－3695(2007)08－0022－03
0引言
20世紀90年代以來，多媒體信息處理技術隨著計算機網絡技術和互聯網的飛速發展而在全世界范圍內得到了迅猛發展。各種形式的多媒體作品如音頻、視頻、動畫、圖像等都紛紛以網絡的形式發布，由此對如何在網絡多媒體時代對多媒體數據進行有效的安全保護提出了新的要求。其中主要應用于多媒體作品的版權保護以及數據認證等領域的多媒體數字水印技術成為多媒體數據處理領域的熱點問題。
目前在多媒體數字水印技術研究中，以圖像、視頻以及音頻數據為對象的數字水印系統被給予了較多的關注。其間經過了使用簡單有效位替換技術的基本算法[1]、應用擴展頻譜等技術的通用算法[2]以及逐漸成為主流研究方向的基于人類感知生理模型的算法等階段，形成了大量的實用算法。
但是，這些研究大部分都集中在視頻數字圖像方面，而對于矢量圖數字水印的研究相對較少。實際上，矢量圖數據作為多媒體數據的一種重要形式，其版權保護也是一個非常重要的問題。隨著CAD/CAM的日益發展和應用，各種圖紙、3D模型的安全性和知識產權的保護問題也備受重視，相應的矢量圖數字水印技術近年來逐漸得到關注。其中針對由三角形網格組成的三維幾何模型的數字水印技術的研究文獻相對較多[3~5]，先后提出了具有不同透明性和魯棒性的數字水印系統；而針對其他類型的矢量圖數據，特別是二維矢量圖數據的數字水印技術的研究工作還較少。
1矢量圖數字水印的基本要求
矢量圖是利用數學公式將地圖中的內容以點、直線、曲線等方式加以存儲。用公式表示的直線和曲線稱為矢量對象；組成矢量圖中各個圖元的點稱為矢量圖的頂點。矢量圖數字水印的基本要求包括魯棒性、透明性、盲檢測、安全性、與相關標準相結合、恒定大小等。其中最為重要的是魯棒性、透明性和盲檢測。
1．1魯棒性
魯棒性是指嵌入圖形中的水印經過一些操作之后水印仍具有較好的可檢測性的能力。這些操作包括幾何變換、格式轉換、網格簡化等；也包括惡意攻擊，如局部修改、裁減以及混合攻擊等。當然，并不是對所有的算法都要求魯棒性越高越好。對于用于版權保護的矢量圖數字水印算法，必須對這些操作是魯棒的；對于用于內容認證的矢量圖水印算法，魯棒性要求低一些。
1．2透明性
透明性是指嵌入到矢量圖中的水印應該是不可見的，即在人眼看來，嵌入水印的矢量圖和原始圖是無差別的。對于矢量圖，因為圖中包含的信息種類雖多，但是冗余的信息很少，所以嵌入水印后必須要保證重要信息不能改動太大以至于引起矢量圖的變形和降質。一個好的、實用的矢量圖水印算法必須具有好的透明性。
1．3 盲檢測
盲檢測是指水印檢測算法不需要用到原始圖形，這也是絕大多數水印系統的基本要求之一。雖然檢測過程中使用原始作品可以提高檢測器的性能，但是對于某些應用來說要獲得原始作品是困難的。對于矢量圖數字水印來說，通常也要求是盲檢測的。這樣，水印檢測器可以統一并且便于分發。
1．4 安全性
安全性是指水印信息應該是安全的，必須難以竄改和偽造。
1．5與相關標準結合
矢量圖的表示和格式是多種多樣的。水印嵌入時如果不考慮相關的圖形表示形式和標準，水印有可能在矢量圖進行格式轉換時丟失。
1．6恒定大小
嵌入的水印不應該增加或顯著增加矢量圖文件的大小。
2矢量圖數字水印算法
2．1傅里葉描述子算法
Solachidis等人[6]提出了一種基于傅里葉描述子的用于多邊形數據的魯棒水印算法。文中提出了多邊形線的概念，即多邊形按照頂點順序連成了一系列頂點。假設L為一包含N個頂點的多邊形線，每個頂點用坐標對x(n)，y(n)表示。由這個坐標對可以構成一個復數信號z(n)=x(n)+i×y(n)(n=0，1，…，N)。這樣一個復數信號經過離散傅里葉變換就可以得到傅里葉系數Z(n)。Z稱為傅里葉描述子，也構成了水印的嵌入域。
水印信號生成過程分兩步：
a)生成一個一維的均值為0的正負1序列，長度等于多邊形線的長度。
b)對序列W0進行調制得到水印信號。
水印嵌入過程采用重復嵌入方式將水印信號疊加到傅里葉描述子的幅值上。
其中：k=0，1，…，N-1；p為強度因子。
水印檢測過程采用相關檢測。令|Z′(k)|表示含有水印的多邊形線L′的傅里葉描述子的幅值。計算Z′(k)與水印信號W(k)的相關性：
如果c大于預定義的閾值，則水印存在；否則水印不存在。
該算法對于一般的幾何變換如平移、旋轉、縮放、反射等具有很好的魯棒性。但是由于該算法是基于傅里葉描述子，而傅里葉變換是一個全局變換，局部很小的改動都會引起傅里葉系數的全局變化，對于局部修改沒有魯棒性。而矢量圖的局部修改是允許的。
2．2基于復數小波域的水印方法
針對上述缺陷，文獻[7]提出了基于復數小波域的水印方法。該方法利用了dual tree復數小波變換的優點，將水印嵌入相對坐標線的復數小波域中。因為一幅矢量圖中最重要的部分就是它的輪廓，所以水印嵌入過程選擇在矢量圖的輪廓中進行。原始圖的輪廓是連續的，采用離散化采樣方法得到矢量圖的輪廓。文中采用基于曲率的不均勻采樣方法，曲率小的地方采樣間距大，曲率大的地方采樣間距小。如果將輪廓圖的每一頂點看做一個質點，整個圖便構成了一個有限質點系。在這里選擇離質心最遠的點作為起始點。為了簡化計算，質心取質點坐標的平均值。
令L代表包含了N 個頂點的多邊形P的相對坐標線。如果頂點表示為(x[i]，y[i])(1≤i≤N)，則L可表示為
對L進行復數小波變換后， 得到L的復數小波表示，其小波系數C包括實部和虛部兩部分。采用直接疊加的方法，通過改變相對坐標線的小波系數進行水印嵌入。水印檢測時仍采用相關系數和給定的閾值來進行衡量，該算法可以有效地抵抗平移、旋轉、縮放和局部修改。
2．3MQUAD算法
Ohbuchi等人[9]提出了一種基于四叉樹劃分的矢量地圖空域水印算法。運用四叉樹算法把地圖劃分成矩形網格，使得每個矩形網格內所含的頂點數不小于某一事先規定的數d。如果某次劃分產生內含頂點數小于d的矩形，則合并同層次中頂點數目最少的相鄰矩形；對劃分所得的樹狀結構矩形網格按深度優先排序；參照Hartung 算法[10]，通過移動一組頂點坐標實現調制矢量數據a=(a1，a2，…，am)到各頂點，通過多次重復嵌入相同數據a產生表示水印的矢量信號b=(b1，b2，…，bmc)。其中c表示矢量數據a的嵌入次數。如果L表示四叉樹算法劃分所得的矩形數， n表示水印信息的長度，則c=floor(L/n)。
水印提取前首先需對水印地圖作一系列預處理，去除幾何變換、插入和刪除頂點等操作的影響。先對原地圖和水印地圖進行與嵌入相同的矩形網格劃分，得到一組矩形序列；計算兩幅地圖對應矩形網格包含的頂點坐標平均值；再計算頂點差值，并去掉最大和最小差值以消除隨機噪聲的影響；最后由頂點差值計算嵌入的矢量數據，由矢量數據a構造原始水印信息b序列。
實驗結果顯示，該算法有較好的抗隨機噪聲及剪切性。但是隨著隨機噪聲的增大，提取水印的錯誤率也快速增長；對水印地圖作扭曲變形處理后，提取水印的錯誤率也很高。
針對這種情況，文獻[11]又提出了一種雙重嵌入的魯棒矢量地圖數字水印算法。該算法按地圖內所含對象特征將矢量地圖分為兩層，對不同的圖層采用不同算法調制水印信息到各頂點;分別計算兩個圖層中代表水印信息的位移量，在閾值的控制下，選擇有效頂點并計算頂點坐標平均值即得到水印信息位序列。實驗結果表明，本文算法對隨機噪聲、扭曲變形和各種剪切具有很強的魯棒性。
2．4注釋水印算法
Sonnet等人[8]提出了一種矢量圖數字水印算法，稱為注釋水印，即與矢量圖本身有關的信息如作者、矢量圖說明與注釋等，經過變換或映射后作為水印信號。算法從三維模型開始，先計算出模型的側影輪廓線；得到的輪廓線由許多矢量線段組成，這些線段就構成了水印的嵌入域。以線段中插入點的方法為例，首先對線段進行細分，使得細分出來的線段不長于預定義的長度，之后在細分出的新線段中插入點來嵌入水印信息。插入點的位置計算如下：
文獻中給出了四種方法：不影響矢量圖外觀的，包括線段中插入點、改變線段長度；改變矢量圖外觀的，包括改變線段角度、改變線段屬性（顏色和寬度）。該類算法更注重嵌入水印的數量，算法的魯棒性較差。雖然它可以抵抗一般的幾何變換，如平移、旋轉、縮放等，但是嵌入的水印信號很容易被去掉，不能用于版權保護。該類算法會增加文件的大小，因此需要額外的存儲空間。
此外， 文獻[12]提出了另一類算法，該算法首先把矢量地圖劃分成很小的網格，將每個網格看做是光柵圖形的一個像素。其中每個像素的值定義為網格內建筑物所占的面積。這樣就把矢量地圖轉換成柵格圖像，最后運用圖像中基于小波的水印算法實現矢量地圖的水印插入與提取。
3結束語
相對于傳統多媒體數據的數字水印技術的研究，現有的矢量圖數字水印研究還很少。本文介紹了矢量圖數字水印的基本要求，并重點分析了二維矢量圖數字水印算法。二維矢量圖數字水印主要采用基于特征集合的方式進行水印信號的嵌入，其關鍵是對矢量圖進行特征分析，并找出好的模型表達方式。用于矢量圖的數字水印技術將會有廣闊的發展前景，下一步的發展熱點包括：
a)二維動畫的數字水印方法。二維矢量圖和二維動畫之間的關系類似于數字圖像和視頻的關系，在引入時間軸之后，數據更加復雜。利用連續的場景間的聯系來完成水印的嵌入和提取將會成為熱點研究內容。
b)通用的適用于多種媒體的數字水印方法。目前的多媒體數據通常同時包含多種媒體，如某個同時具有圖形和圖像數據的場景或某段同時具有視頻和音頻數據的片段。同時存在的多種媒體之間往往具有一定的同步關系。研究一種通用的數字水印方法，除了需要研究如何高效地對不同的數據類型進行移植的數字水印的嵌入和提取，還要考慮多種媒體之間的同步關系。
c)具有防竄改功能的數字水印方法。人們希望用于認證的水印不僅可以檢測和定位出哪些部位遭到了竄改，更能粗略地恢復出被竄改區域的原貌。這樣的水印技術將會更具有吸引力。
參考文獻：
［1］SCHYNDEL van R G， TIRKEL A Z， OSBORNE C F. A digital watermark[C]//Proc of IEEE International Conference on Image Processing.Austin Texas:[s.n.]， 1994:86－90.
[2］COX I J， KILLIAN J， THOMSON F， et al. Secure spread spectrum watermarking for multimedia[J]. IEEE Trans on ImageProces￣sing， 1997，12(6):16731687.
[3］HEALY A， TOUB S. Efficient mesh licensing[R].Cambridge，MA: Harvard University，Computer Science， 2001.
[4］MUROTANI K. Spectral decomposition method for threedimensional shape models and its applications[D].Tokyo: University of Tokyo， Information Science and Technology， 2004.
[5］OHBUCHI R， MASUDA H， AONO M. Watermarking threedimensional polygonal models[C]//Proc ofthe ACM International Confe￣rence on Multimedia.New York:ACM Press， 1997:261－272.
[6］SOLACHIDIS V， NIKOLAIDIS N， PITAS I. Watermarking polygonal lines using fourier descriptors [C]//Proc of IEEE International Conference on Acoustics， Speech and Signal Processing.Istanbul， Turkey:[s.n.]， 2000:19551958.
[7］張琴，向輝，孟祥旭.基于復數小波域的圖形水印方法[J].中國圖象圖形學報， 2005，10(4):494－498.
[8］SONNET H， ISENBERG T， DITTMANN J，et al. Illustration watermarks for vector graphics [C]//Proc of the 11th Pacific Conference on Computer Graphics and Applications.Canmore，Canada:[s.n.]，2003:73－82.
[9］OHBUCHI R， UEDA H， ENDOH S. Robust watermarking of vector digital maps [C]//Proc of IEEE Conference on Multimedia and Expo.Lausanne， Switzerland:[s.n.]，2002.
[10］HARTUNG F， EISERT P， GIROD B. Digital watermarking of MPEG－4 facial animation parameters[J]. Computers and Gra￣phics，1998，22(4):425－435.
[11］王勛，林海，鮑虎軍.一種魯棒的矢量地圖數字水印算法[J].計算機輔助設計與圖形學報，2004，16(10):13771381.
[12］ENDOH S， MASUDA H， OHBUCHI R， et al. Development of digitalwatermarking technology for vector digital maps[R]// IPA Technology Expo 2001 Reports.Tokyo:[s.n.]， 2001.
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”
