基於遞歸嵌入的矢量地圖無損數據隱藏方法
2023-09-22 02:22:05
專利名稱：基於遞歸嵌入的矢量地圖無損數據隱藏方法
技術領域：
本發明涉及的是一種地理信息科學、信息隱藏領域，具體講是一種基於遞歸嵌入的矢量地圖無損數據隱藏方法。
(二)
背景技術：
矢量地圖是構成地理信息系統(GIS)的核心數據，它具有精度高、支持高質量縮放等諸多優良性能。與其他數字媒體一樣，矢量地圖也面臨著一系列數據安全問題，包括版權保護、來源跟蹤、篡改鑑別，因此迫切需要可靠的技術去保障地理空間數據的安全。數字水印技術是隨著數位化的進程而發展起來的保護數據安全的前沿技術，它是在不影響原數據可用性的前提下，將秘密信息-水印與原數據結合併隱藏其中，成為不可分離的一部分，由此來證實數據所有權。可逆水印技術具有在精確提取水印的同時，無失真地恢復原始數據的特性，因此對矢量
地圖有很高的適用性。
目前可逆水印技術的研究主要集中在柵格圖像領域，主要方法包括利用可逆模加、無損壓縮、改變直方圖、和差值擴大來實現算法的可逆性。按照具體的實
現方式可以分為兩類空域法和變換域法。基於空域的數據隱藏方法有1、Fridrich的方法，通過將原始圖像分成互不交疊的由相鄰象素構成的塊，設定一
個判別函數對塊的平滑度進行設定，定義一個可逆變換對象素的最低位進行反轉
完成水印的嵌入，2、 Celik的G-LSB方法，該方法首先對圖像中的各點數據進行量化，然後用圖像中各點的灰度值減去這個量化值，從而得到剩餘量，對剩餘量進行壓縮，然後將其與需要嵌入的信息合併成為一組新的數據流嵌入到圖像各點數據量化值中，3、 NivanLeest的方法，提出一種先對圖像分塊，然後引入一個壓縮函數作用於直方圖，使得直方圖峰值旁出現空位來嵌入水印信息，4、zhicheng的方法，該方法通過找出圖像直方圖中出現的峰值點，使直方圖中的峰值旁出現空位，然後利用圖像中峰值的各點來嵌入水印信息。基於變化域的圖像無損數據隱藏方法有1、宣國榮的方法，採用直方圖調整以避免數據溢出，並在頻域係數上進行水印嵌入的可逆水印算法，2、 JunTian的方法，該方法結合壓縮技術，在對圖像中的各點進行整數Haar小波變換的基礎上進行無損數據隱藏。3、 YangBian的方法，利用整數DCT係數分布近似Laplacian分布的特點，結合比特移位的方法實現的圖像可逆水印算法。
矢量地圖可逆水印算法研究則剛剛起步。2004年Michael Voigt提出一種基於離散餘弦變換的二維矢量數據可逆水印算法"Reversible Watermarking of2D-Vector Data，，(Proceedings of the 2004 multimedia and security workshop onMultimedia and security). 2007年邵承永，王孝通等人基於差值擴大的思想，提出應用於矢量地圖的充損數據隱藏算法:"Reversible Data-Hiding Scheme for 2-DVector Maps Based on Difference Expansion，，(IEEE Transactions on informationforensics and security);"矢量地圖的無損數據隱藏算法研究"(中國圖象圖形學報)。這是目前見到的僅有的三篇關於矢量地圖無損數據隱藏的文章。但是目前矢量地圖無損數據隱藏的研究，在矢量地圖自身特點的考慮、水印嵌入容量以及水印嵌入後矢量地圖的數據精度、視覺感知等方面還存在不足。.
相關的文獻有
1 M.Goljan, Jessica Fridrich, and R.Du, "Distortion-free Data Embedding for
Images",她Information Hiding Workshop, LNCS vol.2137, Springer-Verlag, ■New York, 2001, PP.27-41.(圖像的無損數據隱藏)
2 M. Celik, G. Sharma, A.M.Tekalp, E.Saber. "Lossless Generalized-LSB data
embedding", ImageProcessing， IEEE Transactions on, Volume: 14, Issue:2，Feb.2005,253-266.(廣義LSB無損數據嵌入)
3 Ni.Zhicheng， Y.Q.Shi, N.Ansari et al.， "Revesible data hiding, Circuits and
Systems", 2003.ISCAS，03 . Proceeding of the 2003 International Symposiumon， Volume:2， 25-28 May 2003.(無損數據隱藏)
4 A.van Leest， M.vander Veen， FBraekers， "Reversible image watemarking, Image
processing" ，2003, proceedings.2003 International Connference on, Volume:2，14-17 Spte.2003,Pages:I1 -731-4vol 3.(圖像的無損水印)
5 G麗ong Xuan， Jidong Chen, JiangZhu， Yun Q.shi， zhicheng Ni， Wei Su，
"Lossless Data Hiding Based on Integer Wavelet transform", IEEEMultimedia Signal Processing.2002.(基於整數小波的無損數據隱藏)
66 JunTian， "Revesible watermarking by diference Expansion", Proceedings of
workshop on Multime dia and security, 19-22, Dec. 2002.(基於差值擴大的可逆水印)
7 B.Yang， M.Schmucker, W.Funk, C.Busch and S.Sun. "Integer DCT-based
Reversible watermarking for Images Using Companding Technique". SPIEElectronic Imaging 2004.(利用擴頻技術基於整數DCT的圖像可逆水印)
8 Voigt M, Yang B, Busch C. Reversible watermarking of 2d-vector. In:
Proceedings of the 2004 multimedia and security workshop on Multimedia andsecurity, Magdeburg, Germany, 2004:160-165.(矢量地圖可逆水印)
9 Xiaotong Wang, Chengyong Shao， Xiaogang Xu, Xiamu Niu. "Reversible
Data-Hiding Scheme for 2-D Vector Maps Based on Difference Expansion",information forensics and security, IEEE Transactions on， Volume:2， Issue:2，Sep.2007,311-320.(基於差值擴大的二維矢量地圖可逆數據隱藏)
10邵承永，王孝通，徐曉剛，牛夏牧.矢量地圖的無損數據隱藏算法研究.中國圖象圖形學報，2007,12(2): 206-211.
11專利申請號200810026405.7、名稱"一種基於曲線分割的矢量地圖水印方法"。
12專利申請號200710054817.7、名稱"基於整數小波變換的矢量地理空間數據水印方法"。
發明內容
本發明的目的在於提供一種能夠有效解決矢量地圖水印嵌入容量小，數據精度不足以及原始數據的無損恢復問題的基於遞歸嵌入的矢量地圖無損數據隱藏方法。
本發明的目的是這樣實現的
(1) 對待加入水印的矢量地圖進行多邊曲線的提取；
(2) 對提取的每條多邊曲線分別進行頂點坐標提取；
(3) 對每條多邊曲線的頂點坐標序列分組；
(4) 對步驟(3)中每條多邊曲線中的分組",進行分類；
(5) 對每條多邊曲線的每個可嵌水印分組進行水印嵌入，並且在保證擾動很小的情況下將水印無限次遞歸嵌入在該分組中；
(6) 對每條多邊曲線的每個分組重複步驟(5)，將水印信息完全嵌入其中；
(7) 利用水印提取及無損恢復單元對含有水印信息的矢量地圖進行水印提
取；
(8) 在提取水印的基礎上對信息可嵌分組的原數據進行恢復；如果在水印嵌入過程中對每個可嵌水印分組重複嵌入f次，則在水印提取過
程中對每個可嵌水印分組重複提取f次並將分組數據無損恢復f次。本發明還可以包括
1、 所述的對提取的每條多邊曲線分別進行頂點坐標提取步驟中，每條多邊曲線的頂點坐標序列構成一個有序集合K:
K 二"A,M)'"2,y2)"."}，/￡ {1,2,
其中W表示在步驟(1)中提取出的多邊曲線條數，(Xp, A)表示第/條曲線上第p個頂
點坐標。
2、 所述的對每條多邊曲線的頂點坐標序列分組為其中"個相鄰頂點為一組，
設一條多邊曲線含有的頂點數為AA，各個分組依次記為^， "/， ...， ""， f=「W/"];
其中w廣((x力w，乃."+i)，…，(X(z+i)m，外+1) )}， 乂=0,1,2,...,-1。
3、 所述的對步驟(3)中每條多邊曲線中的分組巧進行分類的方法為首先選定每條多邊曲線的分組^中的第「(7+1)"/21個頂點坐標0「7 +( +1)/21，
、—判)為信息嵌入點，縱坐標與橫坐標的方法相同，其中在橫坐標中嵌入A
印，對分組^/的分類如下
，,(肝1)/2， e[^(A/-0'^(A,0] "》可銜腳粥a
，,一)/q e(,^(A廠0)U(^(A,0,袖)",為不可銜肚吩組
其中
A =-
71 nx("-1)
8且QX)。
4、所述的對每條多邊曲線的每個可嵌水印分組進行水印嵌入的方法為 記水印序列『={w, |w, = 0或w, = 1}，在每個可嵌分組W/中嵌入水印一次，公式
如下formula see original document page 9
(^為波動參數)
其中^;為分組"中W個點的橫坐標均值，附formula see original document page 9'表示
含水印的頂點橫坐標值；
按照此方法在該可嵌分組巧中，將水印位遞歸嵌入其中；該過程中無論水印 遞歸嵌入該分組中的次數f為多大，頂點坐標x 都不會超出波動區間formula see original document page 9即無論在該頂點坐標x「 ，上遞歸嵌入多大容量的水
formula see original document page 9
印信息都不會引起太大的波動。
5、 所述的利用水印提取及無損恢復單元對含有水印信息的矢量地圖進行水
印提取的提取公式為
6、 所述的在提取水印的基礎上依據如下公式對信息可嵌分組的原數據進行 恢復的公式為-formula see original document page 9
本發明基於遞歸嵌入的矢量地圖可逆水印方法，通過遞歸調用矢量地圖多
邊曲線N點均值進行水印重複嵌入，理論及實驗證明該方法可以獲得無限大的
水印嵌入空間，保證了矢量地圖水印的高容量嵌入，針對矢量地圖不可篡改的 高數據精度的要求，該方法在精確提取水印信息的同時，能夠無損恢復原始矢
量地圖數據。與其他矢量地圖可逆水印方法相比，本發明具有以下明顯優點
1、本發明提出了一個遞歸式的可逆水印嵌入方法，在較小擾動的情況下，具有無限大的存儲空間；
2、 本發明選取高相關性的頂點序列組，通過更改接近中間值的頂點坐標進 行水印嵌入，具有視覺上的不可見性。
3、 本發明在提取水印後能無損恢復原矢量地圖數據，特別適用於機密矢量 地圖不容篡改的場合，是矢量地圖無損數據隱藏的一大創新。
(四)
圖1矢量地圖水印嵌入流程圖2矢量地圖水印提取及無損恢復流程圖3嵌入水印前英國高速公路圖4嵌入水印後英國高速公路圖5水印提取後無損恢復的英國高速公路圖6(a)-圖6(d)同一分組重複嵌入不同次數後水印提取效果圖，其中圖6(a) 每個分組遞歸嵌入1次、圖6 (b)每個分組遞歸嵌入2次、圖6 (c)每個分組遞 歸嵌入10次、圖6 (d)每個分組遞歸嵌入20次。
(五)
具體實施例方式
下面結合附圖舉例對本發明做更詳細地描述
本發明基於N點均值可逆技術的矢量地圖無損數據隱藏方法，該方法總體 分為兩方面A、矢量地圖水印嵌入算法(如圖1所示)；B、矢量地圖水印提取算 法以及原矢量數據的無損恢復(如圖2所示)。
A、矢量地圖水印嵌入算法，步驟如下
(1) 對待加入水印的矢量地圖進行多邊曲線的提取；
如圖3所示，我們用Mapinfo提取出的多邊曲線，這些曲線屬於"英國高速公 路"圖層曲線的疊加，在這些疊加曲線中添加水印具有較高的魯棒性。
(2) 對提取的每條多邊曲線分別進行頂點坐標提取； 該步驟中，每條多邊曲線的頂點坐標序列構成一個有序集合K:
其中m表示在步驟(l)中提取出的多邊曲線條數，(&,力)表示第/條曲線上第^個頂 點坐標。
(3)對每條多邊曲線的頂點坐標序列分組；其中n個相鄰頂點為一組，設一條多邊曲線含有的頂點數為iV，各個分組依次記為^， ^，…，^/， P「W/一。
其中"廣fe+i' JVm)，…'(^y+i)"'戶0,1,2,…,"。
(4)為防止嵌入水印信息後引起地圖曲線的過大擾動，對步驟(3)中每條 多邊曲線中的分組";進行分類-
首先選定每條多邊曲線的分組巧中的第「(y+i)W2，個頂點坐標(x「，(。+一，
化. )為信息嵌入點，以在橫坐標中嵌入水印為例(縱坐標與其相同)進行 闡述，分組w/分類情況如式1所示
(A廠0, —(A,+0] ",為可銜腳分組
formula see original document page 11
其中formula see original document page 11
閾值Q取值理論證明如下
(i)如果要正確提取信息，r，則一定要保證、 ，'^附/:由 x ,=附+g -「,("+1)/2，-+ 2,.formula see original document page 11
則得出formula see original document page 11
(2)如果要正確提取信息，o'，則一定要保證、 ，'<附/;由formula see original document page 11附,_ X>+1 + ~ +2 +…+ ，聲+^+d^ +…+ 則得出
x麵+…+ x「 ， +\ ，十…+ x,.則一(w — l)xx
0. > 戸' 「,'"+r +i、"i—i 「,w +i、/ "Ui J則、 ' 1
「乂"+("+l)/2]-l 「>+("+1)/2~|+1_' 「y"+(,，+i)/2"l
綜合(1)(2)得
「>+("+1)/21-1 fy》+("+l)/2l+l_."付 「>+( +1)/2"]
w x (w _ 1)
針對多邊曲線不同的分組嵌入水印，取Q值為
》腿(;Q. I Q. —^M +'"+;爭1)外1十開M肝i)外i十…+x， —("—Dx^fx"w別w i 二 7J "x("-1) ,',…，
另外由";為可嵌水印分組的條件得出x e[」L_(A 0,」L^A+0]:
「/"+("+1)/2] " —1 J w —1 7
則
當\ f唚,"^( +G)時得出，
「,(《+l)/2， w 一 1 J
g>,1 ,2 「乂"+("+l)/2，一l「J"+("+l)/2卜l ," 、 "一l 乂 = 一g
"X(" —1) W-l
由此QX)時，上式一定成立； 當X「 ，= 4(A廣g)時得出，
「/"+("+I)/2")—1、 J "
+x,. +7十…+ x +x + + x, + —(w — l)x-(厶,.一0 n
,1 乂"+2 「>—「一+l)外l 嚴 、 , —1、 .' Q
w x (w — 1) n — 1
由此QX)時，上式一定成立。
綜上所述Q的取值一定要滿足如下條件，即
7' 7 hx("-1) ，,，'
(5)對每條多邊曲線的每個可嵌水印分組進行水印嵌入，並且在保證擾動 很小的情況下可以對該分組遞歸無限次嵌入； .
記水印序列W = fw,卜,- 0或w, = 1}，則在每個可嵌分組M/中嵌入水印一次，公
12式如下
formula see original document page 13
其中^為分組。中"個點的橫坐標均值，=(x,—/+... + x, + )/"， ^,+(/7+1)/21'表示
含水印的頂點橫坐標值。
按照此方法在該可嵌分組w中，可以將水印位遞歸嵌入其中。該過程中無論 水印遞歸嵌入該分組w/中的次數f為多大，頂點坐標x 都不會超出波動區
「_/w+("+l)/2"|
間(工^—0!(A+0)，即無論在該頂點坐標x「 ，上遞歸嵌入多大容量的 水印信息都不會引起太大的波動。證明如下
W (1) = m= -1…》"表示水印第一次嵌入前該分組M個頂點的均值，則"仍 表示水印第f次嵌入前該分組W個頂點的均值
△ -「河肝斜一')外'-表示該分組除載體頂點義 外的"-l
/ 「y' +("+l)/2，
個頂點的均值，
(1)當在分組"y中重複嵌入^次W=l，此種情況下，含水印頂點坐標值逐漸變大， 則有
第一次嵌入後
x iv2， e=(A,+0+^^
第二次嵌入後
0+(肝I)/2"l .' "7 77 J W
第三次嵌入後
;c +0 +W。"，(2) =^(A; +0+^l
「乂—l)/2l、 ,J、 ,-、 J"2 乂 ^第^次嵌入後
其中x「 ， (t)表示嵌入/次"1 "後頂點橫坐標值，可以看出隨著水印信息的
遞歸嵌入，\ ，的波動呈一個遞增趨勢，最大波動極限上限為
;， (0 =輔~ + 0 + -1M (A乂 + g) + ![^!i) = + (a乂 + 0
(2)同理，當在分組^中重複嵌入f次『產0，此種情況下，含水印頂點坐標 值逐漸變小，x 的波動會呈一個遞減趨勢，最大波動極限下限為
「>+(,,+1)/2，
limx (^1im((a廣0十L(a廠0/「沖幸 -^(a 0
(6)對每條多邊曲線的每個分組重複步驟(5)，將水印信息完全嵌入其中；
B、矢量地圖水印提取算法以及原矢量數據的無損恢復，步驟如下-
(7)利用水印提取及無損恢復單元對含有水印信息的矢量地圖進行水印提 取，完全無損地恢復原矢量地圖數據；
① 按照水印嵌入算法第(1 )步對含水印的矢量地圖進行多邊曲線的提取；
② 按照水印嵌入算法第(2)步對提取的每條多邊曲線分別進行頂點坐標提
取；
③ 按照水印嵌入算法第(3)步對矢量地圖中每條多邊曲線進行數據分組劃分。
④ 按照水印嵌入算法第(4)步對每條多邊曲線中的分組w/進行分類；
，麵闊/2〕' e[f^(V0，f;(Ve)] '為力腳併且
， )/21'e ",^(厶廠2))U(^^.+0,—",'為不由腳併且
⑤ 對篩選出的每條多邊曲線中的信息含水印分組進行水印提取；
14該步驟中，水印提取如公式2所示:
⑥矢量地圖數據無損恢復；
在提取水印的基礎上依據如下公式對信息可嵌分組的原數據進行恢復，如式 3所示
如果在水印嵌入過程中對每個可嵌水印分組重複嵌入Z次，則在水印提取過 程中對每個可嵌水印分組重複提取^次並將分組數據無損恢復/次，即重複步驟 ⑤和步驟⑥"欠。
為驗證本發明的可開靠性,我們利用該算法對"英國高速公路"圖進行水印 嵌入，試驗結果如圖3 圖6所示。
W開河肝1)外1 -X「M -…]麵^一)/2，',)
Vi -…1一)外i -，岸鄉_."_x> ,M肝i)/2，',)
權利要求
1、一種基於遞歸嵌入的矢量地圖無損數據隱藏方法，其特徵是(1)對待加入水印的矢量地圖進行多邊曲線的提取；(2)對提取的每條多邊曲線分別進行頂點坐標提取；(3)對每條多邊曲線的頂點坐標序列分組；(4)對步驟(3)中每條多邊曲線中的分組uj進行分類；(5)對每條多邊曲線的每個可嵌水印分組進行水印嵌入，並且在保證擾動很小的情況下將水印無限次遞歸嵌入在該分組中；(6)對每條多邊曲線的每個分組重複步驟(5)，將水印信息完全嵌入其中；(7)利用水印提取及無損恢復單元對含有水印信息的矢量地圖進行水印提取；(8)在提取水印的基礎上對信息可嵌分組的原數據進行恢復；如果在水印嵌入過程中對每個可嵌水印分組遞歸嵌入t次，則在水印提取過程中對每個可嵌水印分組遞歸提取t次並將分組數據無損遞歸恢復t次。
2、 根據權利要求l所述的基於遞歸嵌入的矢量地圖無損數據隱藏方法，其特徵是所述的對提取的每條多邊曲線分別進行頂點坐標提取步驟中，每條多邊曲線的頂點坐標序列構成一個有序集合F"K^(^乂),(^,少2),…,( ,:^)"'j"ep，2，…，W其中w表示在步驟(l)中提取出的多邊曲線條數，(xp, A)表示第i條曲線上第戶個頂 點坐標。
3、 根據權利要求2所述的基於遞歸嵌入的矢量地圖無損數據隱藏方法，其特徵是所述的對每條多邊曲線的頂點坐標序列分組為其中"個相鄰頂點為一組，設一條多邊曲線含有的頂點數為^，各個分組依次記為"c，";，…，""，f=「W/ ];其中w廣脈"+i' ""+i)，， (W+i)"，外+1) )}'產0，1,2,…,M。
4、 根據權利要求3所述的基於遞歸嵌入的矢量地圖無損數據隱藏方法，其特徵是所述的對步驟(3)中每條多邊曲線中的分組";進行分類的方法為首先選定每條多邊曲線的分組"中的第「(/ + 1) /2"1個頂點坐標0[> '",."+( +1)/21)為信息嵌入點，縱坐標與橫坐標的方法相同，其中在橫坐標中嵌入水 印，對分組W/的分類如下formula see original document page 3formula see original document page 3可銜K印併且其中formula see original document page 3且QX)。
5、根據權利要求4所述的基於遞歸嵌入的矢量地圖無損數據隱藏方法，其特徵是所述的對每條多邊曲線的每個可嵌水印分組進行水印嵌入的方法為記水印序列『=^ |w, = O或W, = I}，在每個可嵌分組M/中嵌入水印一次，公式如下formula see original document page 3(g為波動參數)0+("+l)/2，其中,為分組C/y中"個點的橫坐標均值，^ =0>+,+ + ^+ )/"， X「>+0i+1)/2，'表示含水印的頂點橫坐標值；按照此方法在該可嵌分組W/中，將水印位遞歸嵌入其中；該過程中無論水 印遞歸嵌入該分組",中的次數^為多大，頂點坐標x 都不會超出波動區formula see original document page 3間(_5_"—e)l(A+2))，即無論在該頂點坐標、 ，上遞歸嵌入多大容量的 、一J厶乂 ^'"一J勺十y〃 「7"+("+l)/2l水印信息都不會引起太大的波動。
6、根據權利要求5所述的基於遞歸嵌入的矢量地圖無損數據隱藏方法，其特徵是所述的利用水印提取及無損恢復單元對含有水印信息的矢量地圖進行水印 提取的提取公式為- 3!yx義 一"；J 「7"+("+l)/2"] J'》m/) 水印w,.-l <附；') 水印w,.:0「;n+("+l)/2，
7、根據權利要求6所述的基於遞歸嵌入的矢量地圖無損數據隱藏方法，其特徵是所述的在提取水印的基礎上依據如下公式對信息可嵌分組的原數據進行恢 復的公式為-「/咖1)/2， [X,21" 戶5>7+1 -…1河—印-X「「河腫1)/2"JH-^幽^fx孝，'^附/)-5咖J^f;—)/2，'<附/)
全文摘要
本發明提供的是一種基於遞歸嵌入的矢量地圖無損數據隱藏方法。(1)對待加入水印的矢量地圖進行多邊曲線的提取；(2)對提取的每條多邊曲線分別進行頂點坐標提取；(3)對每條多邊曲線的頂點坐標序列分組；(4)對步驟(3)中每條多邊曲線中的分組uj進行分類；(5)對每條多邊曲線的每個可嵌水印分組進行遞歸式水印嵌入；(6)對每條多邊曲線的每個分組重複步驟(5)，將水印信息完全嵌入其中；(7)利用水印提取及無損恢復單元對含有水印信息的矢量地圖進行遞歸式水印提取；(8)在提取水印的基礎上對信息可嵌分組的原數據進行恢復。本發明在提取水印後能無損恢復原矢量地圖數據，特別適用於機密矢量地圖不容篡改的場合。
文檔編號G06T1/00GK101655970SQ20091007242
公開日2010年2月24日 申請日期2009年7月1日 優先權日2009年7月1日
發明者曹劉娟, 李存偉, 門朝光 申請人:哈爾濱工程大學