[發明專利]一種基于頂點插入的矢量地圖完整性認證方法

在審

• 申請號: 201410120970.5
• 申請日: 2014-03-28
• 公開（公告）號: CN103903217A
• 公開（公告）日: 2014-07-02
• 發明（設計）人: 門朝光;王娜娜;田澤宇;門宇博;王思佳
• 申請（專利權）人: 哈爾濱工程大學
• 主分類號: G06T1/00
• 分類號: G06T1/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于頂點插入的矢量地圖完整性認證方法，其特征在于：

（1）劃分矢量地圖區域；

將矢量地圖圖元劃分為互不重疊的塊，將矢量地圖劃分的塊的行數和列數記為N_R和N_W，塊的總數記為N_B，N_B=N_R×N_W，第i，i=1,2,…,N_B個矢量地圖塊記為B_i，包含塊B_i的區域范圍的矩形的左上頂點和右下頂點分別記為和和分別表示的x坐標和y坐標，和分別表示的x坐標和y坐標；

（2）矢量地圖塊分類；

將所有的塊劃分為兩類，normal塊和empty塊，將塊B_i的頂點數目記為如果則塊B_i為normal塊；否則，塊B_i為empty塊；

（3）記錄矢量地圖塊類型；

生成包含N_B個元素的序列F，記錄步驟（2）中每個塊的類型，

F＝{f_i|f_i∈{0,1},i＝1,...，N_B}

其中，f_i=0表示第i塊為一個normal塊，f_i=1表示第i塊為一個empty塊；

（4）生成認證水印；

生成步驟（2）中每個normal塊的認證水印，將塊B_i的水印信息記為H_i，

H_i＝{h_i,j∈{0,1},j∈[0,L-1]}

其中，L表示Hi中比特的數目，h_i,j(0≤j≤L–1)表示Hi中第j個比特；

（5）嵌入認證水印；

將步驟（4）中生成的認證水印嵌入到normal塊中，在normal塊中嵌入水印

（5.1）依據矢量地圖塊B_i的邊界，計算B_i的中心和分別表示中心B_c,i的x坐標和y坐標；

（5.2）生成一個以B_c,i為中心，r為半徑的圓CB_i(B_c,i,r)，將在圓CB_i(B_c,i,r)的圓周上插入含水印頂點以隱藏認證水印，半徑r的取值為：

(Bi,maxx-Bi,minx,Bi,maxy-Bi,miny)]]>

（5.3）將認證水印Hi轉換成要嵌入的水印序列W_i={W_i,j|j∈[0,N_A–1]}，W_i,j表示序列Wi中第j個元素，N_A表示序列W_i中元素數目；

（5.4）根據密鑰K^d，生成雙精度浮點數序列A_i={A_i,j|j∈[0,N_A–1],(0≤A_i,j<180)}，A_i,j表示序列A_i的第j個元素，序列A_i即用來嵌入水印序列W_i的角度序列；

（5.5）對于序列Wi的每個元素W_i,j(j∈[0,N_A–1])，嵌入到序列A_i中的第j個角度A_i,j的尾數部分，將得到的含水印角度記為A_i,j'；

（5.6）依據含水印角度A_i，j'，計算在圓CB_i的圓周上的含水印頂點的位置，

rja=Ai,j′×(π/180)vi,jx=Bc,jx+r×cos(rja)vi,jy=Bc,iy+r×sin(rja)]]>

其中，和分別表示v_i,j的x坐標和y坐標，將計算得到的含水印頂點集合記為V_i={v_i,j|j∈[0,N_A–1]}；

（5.7）將V_i中的含水印頂點插入到矢量地圖中，得到含水印矢量地圖；

（6）水印認證及原始數據恢復；

將含水印矢量地圖的圖元劃分為互不重疊的塊；根據步驟（3）中序列F識別每個塊的類型；

對于empty塊，塊中含有頂點，則視其遭到了篡改；否則，認為該塊通過認證，對于normal塊：

（6.1）根據步驟（5）中計算塊B_i'的中心并生成以B_c,i'為中心，r'為半徑的圓和分別表示中心B_c,i'的x坐標和y坐標；

（6.2）搜索CB_i'圓周上所有的頂點，將CB_i'圓周上所有頂點的集合記為Vic=]]>{vi,jc(vi,jc,x,vi,jc,y)|j∈[0,Nc-1])},vi,jc]]>表CB_i'圓周上第j個頂點，vi,jc,x]]>和vi,jc,y]]>分別表示頂點vi,jc]]>的x坐標和y坐標，N_c表示V_i^c包含的頂點數目；

（6.3）獲得所有可能的含水印頂點集合，將含水印頂點集合的序列記為Vip={Vi,jp|j∈[0,]]>Np-1]},Vi,jp={vi,j,kp(vi,j,kp,x,vi,j,kp,y)|k∈[0,NA-1]}]]>表示一個可能的含水印頂點集合，通過從Vic]]>中選取N_A個不同的頂點獲得，表示可能含水印頂點集合中第k個頂點，和分別表示頂點的x坐標和y坐標，表示可能含水印頂點集合的數目；

（6.4）對于中每個可能含水印頂點集合

（6.4.1）利用步驟（4）中描述的水印生成方法生成B_i''的水印信息H_i'={h_i,_j'|h_i,_j'∈{0,1},j∈[0,L–1]}，B_i''表示不包含中頂點的塊B_i'；

（6.4.2）生成一個含水印頂點集合Vi,j′={vi,j,k′(vi,j,kx′,vi,j,ky′)|k∈[0,NA-1]},vi,j,k′]]>表示V_i,j'的第k個頂點，和分別表示頂點v_i,j,k'的x坐標和y坐標；

（6.4.3）如果塊B_i'包含其相應的含水印頂點，塊B_i^'通過完整性認證，刪除中的頂點以恢復原始數據，塊B_i'的認證過程到此結束；否則，重復步驟（6.4）直至所有的集合都測試完畢；

（6.5）如果中沒有一個可能含水印頂點集合是塊B_i'的含水印頂點集合，則認為塊B_i'遭到了篡改。