基于虛擬坐標的矢量地圖差值擴展可逆水印方法

戴 千 一,吳 柏 燕

(湖南科技大學地理空間信息技術國家地方聯合工程實驗室,湖南 湘潭 411201;湖南科技大學測繪遙感信息工程湖南省重點實驗室,湖南 湘潭 411201;湖南科技大學地球科學與空間信息工程學院,湖南 湘潭 411201)

0 引言

數據安全是城市數字治理的重要前提,數字成果的應用與共享應以數據安全為基礎。數字水印技術能彌補傳統加密技術限制共享的局限性,在嵌入水印的同時保留原始載體的使用價值[1-3],而在醫學診斷、軍事地圖和遙感測繪等特殊場合需要使用無損的高精度數據,可逆數字水印應運而生?？赡嫠〖夹g可在正確提取水印的同時無損恢復原始載體數據,避免數據永久失真[4]。目前柵格圖像的可逆水印算法較成熟,主要包括基于無損壓縮[5]、直方圖平移[6,7]和差值擴展[8,9]3種算法,而矢量數據高精度和低冗余的特性使得水印嵌入條件更嚴格,故柵格圖像的水印算法不完全適用于矢量數據[10]。

國內外針對矢量數據可逆水印的研究大多借鑒圖像水印算法?；跓o損壓縮,Celik等[5]提出一種高容量低失真的廣義無損LSB水印嵌入算法,比傳統 LSB 方法具有更大的靈活性和更精細的容量失真粒度?；谥狈綀D平移,Chen等[7]整合3類直方圖(像素灰度直方圖、差值直方圖和預測誤差直方圖)平移的優勢,采用基于塊的多輪預測提高了圖像質量和水印容量。相比無損壓縮和直方圖平移技術,差值擴展技術具有計算復雜度低和易獲得高水印容量的優勢,如Wang等[11]首次將差值擴展技術用于矢量地圖數據水印,提出基于地圖坐標和曼哈頓距離的兩種水印嵌入方案,但因方案水印容量低,頂點相關性低的地圖在水印嵌入后失真明顯。為平衡水印容量和圖形質量,周璐等[12]基于相鄰頂點構建坐標差值直方圖,利用差值擴展嵌入水印,在相同精度容忍度下取得了更高的水印容量和圖形質量,但地圖水印容量最高僅為0.5 bit/點。隨后,Peng等[13]改進差值擴展技術,將水印嵌入二維CAD工程圖所有頂點相對坐標的比率集上,提高了水印容量和不可感知性,但若參考頂點逆序提取水印則會破壞水印數據完整性。以上研究均為差值擴展技術在矢量數據水印上的應用,嵌入水印時均重點關注水印容量和圖形質量。此外,部分學者從可逆性與魯棒性入手提升水印性能。例如:Cao等[14]從載體數據入手增強水印可逆性,使用Douglas-Peucker算法提取矢量地圖特征點,將非線性加擾后的特征點和非特征點作為載體嵌入水印,算法嚴格可逆且對地圖簡化攻擊魯棒;佟德宇等[15]提出一種結合水印區間定位和區間內部定位的雙重映射機制,同時對區間內部定位和水印值進行校驗,將校驗后的水印信息嵌入坐標的可嵌入位中,增強了算法魯棒性;任娜等[16]基于脆弱水印技術提出通過坐標重排序重新建立空間關系,將當前要素所生成的水印信息量化嵌入其他要素中,從而有效避免了要素刪除導致水印信息一同刪除的問題;唐偉[17]提出一種適用于矢量瓦片數據的大容量魯棒水印方法:在水印生成階段,分段生成代表組編碼和用戶編碼的水印信息,進一步提高水印檢測的正確性,在水印嵌入階段,對經典QIM水印嵌入方法進行改進,劃分出更多數量區間,水印容量大幅提升;奚旭等[18]為彌補水印容量提升使水印不可見性降低的缺陷,提出量化索引調制坐標點狀態值嵌入水印,采用MPR(Maximum Perturbation Regions)方法限定坐標范圍以控制水印隱蔽性,該方法水印容量大且數據擾動程度可控,但算法整體計算復雜度較高。

綜上可知,目前矢量數據可逆水印研究聚焦于水印容量和數據失真問題[13,19-22],水印可逆性和不可見性仍是衡量可逆水印算法性能的重要指標,如何保持水印容量、水印不可見性及數據質量的良好平衡是當前研究的重點和難點。傳統差值擴展技術應用于頂點相關性低的矢量地圖時,水印容量較低,數據失真明顯,導致水印效果不理想。因此,本文提出一種新的矢量地圖差值擴展可逆水印方法,即將虛擬坐標融入差值擴展技術,將水印嵌入差值直方圖平移后的差值中,以解決傳統差值擴展技術應用于矢量地圖可逆水印時容量不足及數據失真問題。

1 基于虛擬坐標的改進差值擴展技術

1.1 基于虛擬坐標的差值計算

(1)

圖1 虛擬坐標構建差值示意

(2)

(3)

(4)

1.2 參考坐標標識圖

理論上虛擬坐標與實際頂點重合時,在提取水印時易造成參考坐標判斷錯誤,從而導致無法正確提取水印,故僅對不與虛擬坐標重合的頂點嵌入水印。提取水印時,差值計算所基于的參考坐標與水印嵌入時應保持同步,因此在水印嵌入階段記錄每個實際頂點的參考坐標,稱為參考坐標標識圖,記為L={b1,b2,…,bn},n為地圖頂點個數。根據式(5),bi可取值0、1、2,由差值di選取的參考坐標及是否與虛擬坐標重合兩個條件確定。參考坐標標識圖能為后續水印正確提取提供依據,為提高算法效率,對參考坐標標識圖L采用游程壓縮編碼,壓縮率受區間步長lt的影響。

(5)

1.3 差值直方圖平移

在基于差值擴展嵌入水印時,差值越小,引入的數據失真越小。因此,需對差值直方圖進行平移,進一步降低差值的大小,以減少水印嵌入引入的數據失真。差值直方圖峰值所在點記為dmax,則直方圖平移按式(6)進行。

d′i=di-dmax

(6)

1.4 水印的嵌入、提取和原始數據恢復

水印嵌入的對象為差值直方圖平移后的差值,水印的提取為水印嵌入的逆過程。為提高算法可讀性,水印的嵌入、提取以及數據恢復以x坐標為例說明,y坐標的相關方法和流程與x坐標相同。

dw′i=d′i×2+w

(7)

(8)

(9)

(10)

(11)

w=dw′i%2

(12)

3)數據恢復:①不含水印差值計算:依據式(13)計算不含水印的差值d′i;②差值直方圖逆平移:按式(14)將所有差值d′i向右平移dmax恢復原始差值di;③原始坐標計算:結合參考坐標標識圖L,按式(15)求得原始坐標。

d′i=floor(dw′i/2)

(13)

di=d′i+dmax

(14)

(15)

2 基于改進差值擴展的矢量地圖水印方案

本文算法利用虛擬坐標和差值直方圖對傳統差值擴展技術進行改進(圖2):在水印嵌入階段,首先生成虛擬坐標,然后對基于虛擬坐標計算的差值直方圖平移,差值擴展嵌入水印,形成含水印地圖;水印提取階段,在水印密鑰的輔助下生成與嵌入階段一致的虛擬坐標,獲取含水印差值,提取水印驗證數據來源;數據恢復基于差值擴展的逆過程,再經差值直方圖平移變換求得原始差值,然后計算原始坐標,最終恢復原始地圖。

圖2 本文算法框架

2.1 水印嵌入

(16)

式中:P為小數點向右移動的位數,Pmax=6。

將區間長度lt、參考坐標標識圖L、差值直方圖峰值點dmax、P值保存為密鑰K2,用于后續水印提取與數據恢復。

2.2 水印提取和數據恢復

以x坐標為例,水印提取和數據恢復過程如下:

①遍歷水印地圖Mw所有頂點,按式(16)調節坐標,水印提取基于整數坐標;②讀取密鑰K2確定區間步長lt,參照1.1節生成虛擬坐標;③利用密鑰K2中的參考坐標標識圖L,按式(10)計算含水印差值;④按式(11)將含水印的差值直方圖向左平移;⑤按式(12)提取水印,比較原始水印信息驗證數據一致性;⑥基于式(13)求出不含水印的差值d′i;⑦按式(14)將差值直方圖向右平移恢復原始差值di;⑧按式(15)得到整數化的原始坐標xi;⑨解除坐標整數化,獲得原始地圖M。

3 實驗與分析

為驗證算法的有效性,在Windows 10操作系統采用Visual Studio 2013開發平臺進行實驗。矢量地圖數據由點、線、面要素構成,不同類型地圖的數據相關性存在差異,本文選取具有代表性的風景名勝POI、等高線、路網和居民地矢量數據(圖3)進行實驗,數據格式為Shapefile,基本信息如表1所示。實驗中原始水印圖像為寫有“地理空間”的二值圖像,大小為125×125像素,水印嵌入強度默認為1,邏輯映射的初始值k0= 0.635 435。

表1 原始矢量數據基本信息

圖3 原始實驗數據

實驗選取文獻[11,17,23,24]中的算法作為本文對比算法。其中,文獻[11]是傳統矢量地圖差值擴展可逆水印算法;文獻[23]同為虛擬坐標在矢量地圖水印的應用,但與本文構建虛擬坐標方法不同;文獻[24]是針對文獻[23]在2維 CAD工程圖的改進算法;文獻[17]為矢量瓦片數據魯棒水印算法,該算法通過改進QIM方法嵌入水印,有效提升了水印容量但不可逆。

3.1 區間步長lt的討論

本文算法中,確定區間步長lt是構建虛擬坐標的前提,不同P值下不同的區間步長所構建的虛擬坐標不同,用于水印嵌入的坐標差值也不同,區間步長lt越小,差值越小,基于差值擴展嵌入水印后的頂點擾動越小。因此,在相同水印嵌入強度下,區間步長越小越好。此外,為提升算法的水印容量,虛擬坐標與實際坐標的重合概率要盡可能小,因此要求區間步長盡可能大。綜上,區間步長的選擇本質上是數據精度與水印容量的平衡。

3.2 水印容量分析

水印容量即一個數據集可嵌入水印數量的上限,可用平均每個頂點所嵌入的水印比特數(bit/點)表示,即嵌入率。理論上每個頂點的水印容量為2 bit/點,本文算法中,水印嵌入在不與虛擬坐標重合的坐標中,如果部分實際頂點坐標與虛擬坐標重合,則重合坐標不嵌入水印,此時水印嵌入率小于2 bit/點。由圖4可以看出,4個數據集的水印嵌入率均隨lt增大而增大,最大達到2 bit/點,變化速度呈先快后慢趨勢,除風景名勝POI數據外,在相同lt下,P值越大,水印容量越高;等高線數據集首次取得最大水印容量的lt大于其他3個數據集,這是由于坐標點分布越密集,在相同lt下,與虛擬坐標重合的實際坐標越多,水印嵌入率越低;風景名勝POI數據集由于頂點相關性較低,受P值變化影響小;當lt取最小值時,居民地數據集的水印容量最好。

圖4 水印嵌入率與區間步長lt的關系

由表2可以看出,當區間步長取合適值時,本文算法水印容量在不同數據集中穩定為2 bit/點,高出文獻[11]的傳統差值擴展方法6倍以上。文獻[17]算法水印容量受嵌入位置影響,為便于比較,實驗設定坐標可更改的精度位為6,量化區間數為2,即每個坐標嵌入一個水印位,水印容量與本文相同且點線面數據集均適用。理論上文獻[24]算法迭代次數可趨近無限,故在不考慮其他水印性能的情況下,文獻[24]算法的水印容量會遠高于本文算法,但實驗發現文獻[24]算法應用于本文大比例尺地圖時,迭代次數增加會不同程度地影響水印不可見性和計算復雜度,因此對比實驗時迭代次數設為1。在同等水印嵌入強度下,文獻[23]與文獻[24]水印嵌入坐標數量相同,故水印容量相同。本文算法水印容量略高于文獻[23,24],這是由于文獻[23,24]算法不能將水印嵌入參考坐標中,而本文算法通過控制區間步長lt所有頂點均可參與水印嵌入。值得注意的是,雖然POI數據集的頂點相關性很低,但本文算法基于約束的區間步長lt引入虛擬坐標,以虛擬坐標為參考計算每個實際坐標的差值,水印可嵌入每個實際坐標中,故水印容量依然很好,而文獻[11,24]在頂點分布稀疏的POI數據集中無法嵌入水印。綜上,相對傳統差值擴展方法,本文算法擁有更大的水印容量,且顯著降低了頂點相關性對水印容量的影響。

表2 不同算法水印容量比較(P=6)

3.3 水印不可見性分析

本文從主觀和客觀兩方面評估水印數據的不可見性。①主觀上,對嵌入水印后的數據與原始數據疊加比較,在ArcGIS中進行拓撲檢查,未出現要素重疊等問題。觀察圖5發現,正常情況下水印嵌入前后地圖無明顯區別,局部放大發現坐標點出現微小偏移,但整體沒有出現明顯形變,要素拓撲關系保持良好。②客觀上,依據式(17)和式(18)計算水印嵌入前后坐標點的均方根誤差RMSE(ERMSE)和地圖坐標最大改變量Max-R(RMax),二者數值越小,表示坐標偏移越小,水印不可見性越好。由圖6和圖7可知,4個數據集的RMSE和Max-R均隨區間步長lt增大而增大;lt取相同值時,P值越大,同一數據集的RMSE和Max-R越小,等高線數據在4個數據集中的RMSE最小,不可見性最優;在相同P值下,4個數據集的Max-R變化曲線幾乎相同,這是因為相同lt下坐標構建的最大差值相同。風景名勝POI數據集在P=5時的RMSE與P=6時相差較小,而其他3個數據集在P=5時的RMSE與P=4時更接近,P=6時不可見性顯著提升。

(17)

圖5 水印嵌入前后細節對比(路網)

圖6 Max-R與區間步長lt的關系

圖7 RMSE與區間步長lt的關系

RMax=max(‖V-Vw‖)

(18)

從表3可以看出,本文算法應用于4種數據的地圖坐標偏移很小,水印不可見性好。文獻[17]作為不可逆水印算法,雖然擁有高水印容量,但水印坐標偏移量遠高于本文算法和其他對比算法。與文獻[11]相比,本文算法的RMSE和Max-R明顯偏低,表明本文算法的坐標偏移量更小,圖形質量更高,水印不可見性更好;與文獻[23]比較,本文算法應用于風景名勝POI數據的RMSE和Max-R更小,但文獻[23]應用于路網數據的不可見性與本文算法相差不大;文獻[24]應用于等高線和路網數據的不可見性略差于文獻[23],原因是文獻[24]的水印坐標受虛擬坐標區間狀態值影響;此外,本文算法在4種數據集中的RMSE相差不大,即使對頂點相關性低的POI數據集,也取得了與其他3個數據集相當的RMSE結果,這是因為虛擬坐標的構建提高了數據相關性,差值直方圖平移減小了坐標擾動,整體上可嵌入水印的數據單元增加而數據失真保持在較小范圍。

表3 不同算法水印不可見性比較(P=6)

本文算法實驗中,1∶1 000的原始地圖和水印地圖之間的最大Max-R為 0.000 285 19<0.30 m(國標《1∶500 1∶1 000 1∶2 000外業數字測圖技術規程 GB14912—2005》中的地形圖精度平面誤差要求),符合實際生產標準,其他4個測試數據的水印地圖數據精度也均滿足應用要求,因此,本文算法嵌入水印所引起的數據擾動不會影響矢量地圖的可用性。

3.4 可逆性分析

為評價恢復地圖客觀質量,計算不同算法下原始矢量地圖與恢復后矢量地圖之間的RMSE和Max-R值(表4)。通常矢量地圖數據存儲精度約為0.1 mm,實驗中原始坐標與恢復坐標之間的差異小于10-4m即認為方案可逆。理論上本文算法可以在正確提取水印的基礎上無損地恢復原始地圖,這是由本文算法機制決定的:本文算法和文獻[11]算法是基于整數坐標進行運算,小數部分不參與水印嵌入,因此水印嵌入后的精度在運算過程中并無損失;另一方面,水印嵌入和數據恢復時差值直方圖經過兩次平移變換,兩次變換互為逆運算,不會對地圖坐標產生影響。文獻[24]算法中,水印坐標含有失真參數Q,會影響水印提取恢復,文獻[17]為魯棒水印算法,無法從水印地圖中恢復出可用的地圖,因此算法不可逆。由表4可知,基于文獻[23,24]算法的RMSE和Max-R雖然不為0,但數值極小,對地圖數據質量的影響很小,因此也認為是可逆算法;從可逆性上看,文獻[11]算法與本文算法最優。

4 結束語

本文基于傳統差值擴展技術引入虛擬坐標計算差值,將構建的差值直方圖平移,通過差值擴展將水印信息嵌入坐標,與傳統差值擴展方法(文獻[11])相比,有效提升了水印容量并減小數據擾動。與文獻[23,24]的方法相比,本文算法虛擬坐標由區間步長lt構建,無需浪費參考坐標。同時,本文算法對于頂點相關性低的地圖數據(如POI數據)同樣適用,可以實現大比例尺地圖的水印嵌入,在實際工程建設中具有現實意義。

本文未涉及高強度嵌入水印的情況,對于單個水印嵌入單元能否攜帶大量水印信息也欠考慮。因此,提升可逆水印算法的魯棒性和探討高水印嵌入強度的水印算法可行性是下一步的重點研究內容。