一種抗幾何變換攻擊的矢量數(shù)據(jù)盲水印算法

王云飛，趙 婧，王 拓，崔偉宏

(1.中國(guó)科學(xué)院遙感應(yīng)用研究所，北京 100101；2.北京四維圖新科技股份有限公司，北京 100028)

1 概述

矢量數(shù)據(jù)是國(guó)家經(jīng)濟(jì)建設(shè)中的一種重要戰(zhàn)略資源，其安全性問(wèn)題十分值得關(guān)注。數(shù)字水印技術(shù)作為保護(hù)數(shù)據(jù)版權(quán)的一種有效手段，近年來(lái)得到廣泛的應(yīng)用。對(duì)于矢量數(shù)據(jù)，目前水印算法研究主要集中在以下4個(gè)方面：

(1)基于坐標(biāo)點(diǎn)的水印算法。該類算法將水印直接嵌入到地物坐標(biāo)點(diǎn)中，例如基于灰度圖像的矢量地理空間數(shù)據(jù)水印算法[1]和抗數(shù)據(jù)壓縮的矢量地圖數(shù)據(jù)數(shù)字水印算法[2]。

(2)基于變換域的水印算法。該類算法將水印信息嵌入到坐標(biāo)序列的變換域中，例如基于小波變換的水印算法[3-4]和基于離散傅里葉變換(Discrete Fourier Transform, DFT)的水印算法[5-6]。

(3)基于地圖劃分的水印算法。該類算法將水印信息分區(qū)域嵌入到地圖坐標(biāo)中，例如基于MQUAD的水印算法[7]和基于坐標(biāo)映射劃分的水印算法[8-10]。

(4)基于坐標(biāo)點(diǎn)排序劃分的水印算法。該類算法通過(guò)新增或移動(dòng)坐標(biāo)點(diǎn)到指定的坐標(biāo)劃分區(qū)域來(lái)嵌入水印，例如文獻(xiàn)[11-12]的算法。

現(xiàn)有的矢量數(shù)據(jù)水印算法對(duì)地圖噪聲、地圖裁剪等常規(guī)攻擊方式具有較好的魯棒性，但是對(duì)幾何變換攻擊的魯棒性較差。目前可以抵抗幾何變換攻擊的水印算法主要包括 2種：(1)通過(guò)幾何校正[13-14]，恢復(fù)待測(cè)數(shù)據(jù)到原始數(shù)據(jù)的坐標(biāo)體系下，但這種方法精度低，不利于在實(shí)際中應(yīng)用。(2)基于變換域的水印算法，但這類算法大多屬于非盲水印算法，并且對(duì)隨機(jī)增點(diǎn)和地圖壓縮攻擊魯棒性較差。針對(duì)以上問(wèn)題，本文在現(xiàn)有研究成果的基礎(chǔ)上，提出一種抗幾何變換攻擊的矢量數(shù)據(jù)盲水印算法，該算法主要針對(duì)線圖層和面圖層。

2 抗幾何變換攻擊的矢量數(shù)據(jù)水印算法

2.1 算法思路

為了增強(qiáng)水印信息對(duì)幾何變換攻擊的魯棒性，一種有效的方式是將水印信息嵌入到幾何變換不變域中。以線地物為例，如圖 1所示，其中，P1～P5為線地物坐標(biāo)節(jié)點(diǎn)；r1～r4為坐標(biāo)節(jié)點(diǎn)與起始坐標(biāo)節(jié)點(diǎn)的距離。地物經(jīng)過(guò)幾何變換后，每一個(gè)節(jié)點(diǎn)的坐標(biāo)位置都發(fā)生了變化，但是每個(gè)節(jié)點(diǎn)之間的距離比值并沒(méi)有發(fā)生變化，例如圖中的r2/r1，不管地物經(jīng)過(guò)何種幾何變換，其比值都是固定的，因此，本文選擇該值作為幾何變換的不變域進(jìn)行水印嵌入，將水印信息按位嵌入到圖中的r2/r1、r3/r1、r4/r1中。

圖1 線狀地物的幾何不變域

此外，如果直接選取地物的坐標(biāo)節(jié)點(diǎn)進(jìn)行水印嵌入，提取出的水印信息很容易會(huì)被地圖壓縮和隨機(jī)增點(diǎn)等攻擊所干擾。為了增強(qiáng)水印的魯棒性，本文將水印嵌入到地物的特征點(diǎn)中。盡管矢量數(shù)據(jù)的冗余較小，但是在不影響精度的條件下，適當(dāng)?shù)臄?shù)據(jù)壓縮是被允許的。如圖2所示，點(diǎn)P1、P3、P4、P6為線的特征點(diǎn)，P2和 P5為線的冗余點(diǎn)，刪除此類點(diǎn)即實(shí)現(xiàn)了數(shù)據(jù)壓縮，而且不會(huì)對(duì)原始數(shù)據(jù)的精度影響太大。

圖2 線數(shù)據(jù)的特征點(diǎn)和冗余點(diǎn)

2.2 水印信息的生成

目前水印信息有2種生成方式：(1)利用水印圖像獲取水印字節(jié)；(2)直接轉(zhuǎn)換水印字符為水印字節(jié)。相比之下，方式(1)生成的水印信息可識(shí)別性較好，如果水印字節(jié)中的部分字節(jié)被干擾，水印信息仍能較完整地識(shí)別出來(lái)，缺點(diǎn)是水印占據(jù)空間較大，嵌入一條完整的水印信息需要的坐標(biāo)點(diǎn)數(shù)目較多，因此，該方式只適用于地物坐標(biāo)節(jié)點(diǎn)較多的地圖。方式(2)生成的水印信息魯棒性相對(duì)較弱，優(yōu)點(diǎn)是占用空間很小，水印可以多次重復(fù)嵌入和提取，因此，可以通過(guò)多數(shù)原則來(lái)判別水印信息的每一位值，從而提高水印信息的魯棒性。

本文將水印分別嵌入到每個(gè)地物特征點(diǎn)的距離比例中，從水印嵌入的完整性上考慮，算法選擇方式(2)生成水印信息。為進(jìn)一步增強(qiáng)水印的抗干擾能力，利用漢明(7, 4)碼對(duì)初始水印信息進(jìn)行糾錯(cuò)編碼。

2.3 水印嵌入流程

水印的嵌入流程如下：

(1)按照一定的壓縮比例，利用 Douglas-Peucker壓縮算法提取原始圖層地物的特征點(diǎn)，對(duì)每個(gè)特征點(diǎn)，屬性中記錄特征點(diǎn)所在的地物編號(hào)和節(jié)點(diǎn)編號(hào)。

(2)計(jì)算每個(gè)地物的特征點(diǎn)距離比值，將水印信息按位嵌入到該距離比值中。其中，每一個(gè)地物嵌入一條水印信息，如果地物特征點(diǎn)數(shù)目小于水印信息位數(shù)目，則按照特征點(diǎn)數(shù)目，嵌入水印的前幾位信息。

定義 ai為每一個(gè)坐標(biāo)節(jié)點(diǎn)的距離比值，其中，a1=r2/r1；a2=r3/r1；…；an=rn+1/r1。將 ai按由小到大的順序組成一個(gè)序列L，定義一個(gè)閾值C，將L劃分為不同的部分，如圖3所示。如果當(dāng)前水印值為0，則將ai移動(dòng)到偶數(shù)間隔中，否則，將ai移動(dòng)到奇數(shù)間隔中。

圖3 序列L的劃分

假設(shè)序列L中一共含有n個(gè)比值數(shù)據(jù)，其中，最小值和最大值分別為amin和amax；閾值C的計(jì)算公式如下：

其中，u為用戶自定義系數(shù)，一般可以選擇為10。由于amin和amax用于計(jì)算閾值C，因此這2個(gè)值不嵌入水印信息。

最后根據(jù)嵌入水印后的ai和r1，計(jì)算嵌入水印后的特征點(diǎn)距離ri+1，并根據(jù)ri+1移動(dòng)對(duì)應(yīng)的特征點(diǎn)Pi+2的坐標(biāo)，從而完成該水印位的嵌入。

(3)根據(jù)特征點(diǎn)圖層中每個(gè)點(diǎn)的地物編號(hào)和節(jié)點(diǎn)標(biāo)號(hào)，替換原始圖層中的特征點(diǎn)，從而實(shí)現(xiàn)原始圖層的水印嵌入。

2.4 水印提取流程

水印的提取算法是嵌入算法的逆過(guò)程：

(1)按照水印嵌入時(shí)的壓縮比例，利用 Douglas-Peucker壓縮算法提取原始圖層地物的特征點(diǎn)。

(2)計(jì)算每個(gè)地物的特征點(diǎn)距離比值 ai，并將 ai按照大小關(guān)系形成序列L，將L按閾值C進(jìn)行劃分，根據(jù)ai所在的奇偶間隔提取出相應(yīng)的水印信息位。

(3)根據(jù)每一個(gè)地物提取出的水印信息，由多數(shù)原則選取水印信息的每一位值，最終提取出嵌入的水印信息。

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

下面通過(guò)實(shí)驗(yàn)對(duì)本文的水印算法進(jìn)行性能分析。地圖采用四川省縣級(jí)區(qū)劃行政圖，一共包括234個(gè)多邊形，Douglas-Peucker壓縮限差選取0.005，水印信息選取字符串“IRSA”，占 32 bit，經(jīng)過(guò)漢明碼糾錯(cuò)編碼后占56 bit，嵌入水印后的地圖如圖4所示。

圖4 嵌入水印后的縣級(jí)區(qū)劃行政圖

3.1 透明性

圖5展示了原始圖層和嵌入水印后圖層的疊加圖，從可視化角度看，2個(gè)圖層的數(shù)據(jù)幾乎一致，因此，本文的水印算法在視覺(jué)上是透明的。

圖5 原始圖層和嵌入水印后圖層的疊加圖

3.2 嵌入誤差

原始圖層一共含有234個(gè)多邊形、71 730個(gè)節(jié)點(diǎn)，通過(guò) Douglas-Peucker算法，水印數(shù)據(jù)嵌入到其中的15 918個(gè)特征點(diǎn)的坐標(biāo)中。嵌入誤差的實(shí)驗(yàn)結(jié)果如表1所示，可以看出，水印嵌入后坐標(biāo)點(diǎn)誤差均在圖層精度范圍內(nèi)。

表1 本文算法的嵌入誤差

3.3 魯棒性

最后就隨機(jī)噪聲、隨機(jī)增點(diǎn)、地圖壓縮、地圖裁剪和幾何變換攻擊對(duì)水印信息帶來(lái)的干擾，對(duì)水印算法的魯棒性進(jìn)行分析，實(shí)驗(yàn)結(jié)果如表2所示。從中可以看出，本文算法對(duì)常規(guī)的地圖攻擊方式，例如隨機(jī)噪聲、隨機(jī)增點(diǎn)、地圖壓縮、地圖裁剪等魯棒性較高，只有在地圖壓縮比例過(guò)大時(shí)，算法才會(huì)提取失敗。在實(shí)際應(yīng)用中，過(guò)大比例的地圖壓縮會(huì)嚴(yán)重影響原始數(shù)據(jù)精度，因此，這種攻擊方式并不常見(jiàn)。由于本文算法將水印信息嵌入到地物特征點(diǎn)的距離比值中，因此對(duì)于幾何變換攻擊，水印信息的提取不受影響。

表2 本文算法的水印魯棒性

4 結(jié)束語(yǔ)

本文提出一種可以抵抗幾何變換攻擊的矢量數(shù)據(jù)盲水印算法，算法選取地物坐標(biāo)節(jié)點(diǎn)距離比值這一幾何不變域作為水印嵌入位。通過(guò)實(shí)驗(yàn)證明，算法能夠抵抗幾何變換攻擊，水印在經(jīng)過(guò)適度地圖壓縮、地圖裁剪和隨機(jī)增點(diǎn)等攻擊后可以正確提取出來(lái)，只有當(dāng)?shù)貓D壓縮比例過(guò)大時(shí)，水印才會(huì)提取失敗，這也是下一步需要改進(jìn)的方向。

[1]郭思遠(yuǎn), 朱長(zhǎng)青.基于灰度圖像的矢量地理空間數(shù)據(jù)水印算法[J].測(cè)繪工程, 2008, 17(1): 21-23.

[2]朱長(zhǎng)青, 楊成松, 李中原.一種抗數(shù)據(jù)壓縮的矢量地圖數(shù)據(jù)數(shù)字水印算法[J].測(cè)繪科學(xué)技術(shù)學(xué)報(bào), 2006, 23(4):281-283.

[3]楊成松, 朱長(zhǎng)青.基于小波變換的矢量地理空間數(shù)據(jù)數(shù)字水印算法[J].測(cè)繪科學(xué)技術(shù)學(xué)報(bào), 2007, 24(1): 37-39.

[4]李媛媛, 許錄平.矢量圖形中基于小波變換的盲水印算法[J].光子學(xué)報(bào), 2004, 33(1): 97-100.

[5]許德合, 王奇勝, 朱長(zhǎng)青.基于 DFT幅度的矢量地理空間數(shù)據(jù)數(shù)字水印算法[J].測(cè)繪科學(xué), 2008, 33(5): 129-131.

[6]許德合, 朱長(zhǎng)青, 王奇勝.利用QIM的DFT矢量空間數(shù)據(jù)盲水印模型[J].武漢大學(xué)學(xué)報(bào): 信息科學(xué)版, 2010,35(9): 1100-1103.

[7]Ohbuchi R, Ueda H, Endoh S.Robust Watermarking of Vector Digital Maps[C]//Proceedings of IEEE Conference on Multimedia and Expo 2002.Lausanne, Switzerland:IEEE Press, 2002: 1-4.

[8]王 勛, 林 海, 鮑虎軍.一種魯棒的矢量地圖數(shù)字水印算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2004, 16(10):1377-1381.

[9]閔連權(quán).一種魯棒的矢量地圖數(shù)據(jù)的數(shù)字水印[J].測(cè)繪學(xué)報(bào), 2008, 37(2): 262-267.

[10]楊成松, 朱長(zhǎng)青, 陶大欣.基于坐標(biāo)映射的矢量地理數(shù)據(jù)全盲水印算法[J].中國(guó)圖象圖形學(xué)報(bào), 2010, 15(4):684-688.

[11]王 偉, 李 巖.一種魯棒性的2D矢量圖形水印算法[J].中國(guó)圖象圖形學(xué)報(bào), 2007, 12(2): 200-205.

[12]Wang Chungming, Wang Pengcheng.Data Hiding on Point-sampled Geometry[J].Journal of the Chinese Institute of Engineers, 2006, 29(3): 539-542.

[13]金 聰, 葉俊民, 許凱華.具有抗幾何攻擊能力的盲數(shù)字圖像水印算法[J].計(jì)算機(jī)學(xué)報(bào), 2007, 30(3): 474-481.

[14]楊曉元, 季稱利, 王育民.基于幾何變換特征集的水印圖像失真校正算法[J].計(jì)算機(jī)工程與應(yīng)用, 2005, 41(16):127-129.