定位篡改圖元組的矢量地圖完整性認證方法與流程
2023-06-05 17:30:11
本發明涉及地理信息科學、信息隱藏領域，具體講是一種定位篡改圖元組的矢量地圖完整性認證方法。
背景技術：
隨著地理信息處理技術和通信技術的快速發展，矢量地圖在導航、城市規劃、交通運輸、地籍管理等領域得到了廣泛應用。獲取高精度的矢量地圖數據需耗費大量的人力物力，而藉助於強大的地理信息處理工具和公共網絡，人們可以方便快捷地複製、修改並發布這些矢量數據。如何認證矢量地圖的完整性和真實性，保障矢量地圖的安全應用是當前迫切需要解決的問題。
矢量地圖脆弱水印方法是認證數據完整性的有效方法。通過將原始矢量地圖劃分為若干數據單元(如頂點分組、圖元分組)，為每個數據單元生成相應的認證水印(如數字籤名、消息摘要)並嵌入在其中，篡改發生後，通過對比每個數據單元中提取的認證水印同再次生成的認證水印，矢量地圖脆弱水印方法能夠檢測並定位發生篡改的數據單元。
當前，人們在矢量地圖脆弱水印方面的研究已經取得了一些研究成果。邵承永等人於2005年首先給出了一種定位篡改頂點的可逆脆弱水印算法。該算法能檢測矢量地圖是否發生篡改，但定位增加/刪除頂點攻擊的能力還有待加強。zheng和you進一步提出了一種定位篡改頂點分塊的可逆脆弱水印算法。但當篡改的頂點移出其原始分塊後，可能會影響篡改檢測階段的頂點分塊的劃分，導致篡改定位能力的下降。基於圖元標記的思想，wang和men設計了一種定位篡改圖元分組的可逆脆弱水印算法。由於圖元分組中的圖元數目依賴於人工設定，未充分利用每個頂點的嵌入空間，該方法的篡改定位能力不強。wang和men提出一種定位篡改塊的矢量地圖可逆脆弱水印方案。該方案定位篡改圖元塊的同時，能夠獲取高質量的含水印矢量地圖。但由於塊內的圖元數目不易控制，該方法不適合應用於更高篡改定位精度的場合。結合混沌映射技術，李莎莎等人提出了一種定位篡改圖元分組的脆弱水印方法。基於量化的思想，研究學者提出了定位篡改頂點的脆弱水印算法。這兩種方法能夠準確定位修改或增加的頂點，但定位增加/刪除圖元攻擊的能力不夠強。yue等人提出了一種定位圖元分組的脆弱水印方法。該方法能夠準確定位增加或修改的圖元，但還不能準確定位刪除的圖元。
綜上所述，雖然人們目前提出了一些矢量地圖脆弱水印方法，試圖解決在認證數據完整性的同時，定位篡改的問題，但這些方法在準確定位篡改圖元方面還存在不足。
技術實現要素：
提出一種定位篡改圖元組的矢量地圖完整性認證方法，一方面該方法利用模擬退火方法，將矢量地圖圖元自適應地劃分為不同的組，考慮矢量地圖的精度誤差容限的前提下，採用可逆信息隱藏方法實現認證水印和圖元組別信息的嵌入，確保準確定位篡改圖元的同時，具有較好不可見性，而且無需額外存儲空間；另一方面該算法在水印認證階段，不僅能夠準確定位篡改圖元組，還能夠在認證完整性後，無損恢復矢量地圖原始數據，保證矢量地圖數據的可靠應用。實驗結果表明該方案是一種用於矢量地圖完整性認證、定位篡改的實用算法。
矢量地圖圖元(點圖元、線圖元和面圖元)是由大量密集的頂點按照特定的順序排列而成的，地圖數據就是這些頂點的2維坐標序列。矢量地圖脆弱水印技術是一種解決矢量地圖完整性認證、定位篡改問題的重要手段。人們當前提出的矢量地圖脆弱水印策略能夠達到認證數據完整性和真實性的目標，但這些策略在準確定位篡改圖元方面還存在不足。針對上述問題，本發明提出定位篡改圖元組的矢量地圖完整性認證方法，包括如下步驟：
(1)圖元頂點分類；
該步驟中，將矢量地圖圖元的頂點劃分為兩類：標記頂點和非標記頂點。標記頂點用於嵌入其所在圖元所屬圖元組的組別信息(即標記)，非標記頂點可嵌入認證水印。將每個線圖元的第一個頂點和最後一個頂點視為其標記頂點，其他頂點視為非標記頂點。
(2)基於模擬退火方法的圖元組自適應劃分；
該步驟中，依據每個圖元的非標記頂點數目，利用模擬退火方法，將矢量地圖的圖元劃分為若干組。假設得到的最優圖元組劃分方法為sbest，sbest劃分的圖元組數目為g(sbest)，sbest的第i(j＝1,2,…,g(sbest))個圖元組為中圖元的數目為中第個圖元為
(3)生成認證水印；
該步驟中，生成步驟(2)中每個圖元組的認證水印。將圖元組的認證水印記為hj
hj＝{hj,i∈{0,1},i＝0,1,...,l-1}
其中，l表示hj中比特的數目，hj,i(i＝0,1,…,l–1)表示hj的第i個比特。
將hj轉換為待嵌入水印序列wj＝{wj,i|wj,i＝0,1,…,2c–1,i＝0,1,…,nr–1}，
wj,i＝hj,i×c×2c-1+hj,i×c+1×2c-2+…+hj,(i+1)×c-1×20
(4)嵌入認證水印；
該步驟中，利用基於量化的可逆信息隱藏方法，將步驟(3)中生成的待嵌入水印序列wj(j＝1,2,…,g(sbest))嵌入到圖元組的前個非標記頂點中。在圖元組中嵌入其對應的認證水印hj後，得到含水印圖元組將的含水印線圖元記為
(5)標記圖元；
該步驟中，利用步驟(4)的信息嵌入方法，在含水印圖元組(j＝1,2,…,g(sbest))的每個線圖元的標記頂點的坐標中嵌入組別信息(即該組的索引值j)。在每個圖元中嵌入標記後，得到含標記矢量地圖。
(6)水印認證及原始數據恢復；
該步驟中，依據圖元標記及可逆信息隱藏方法，恢復矢量地圖數據並定位篡改，具體步驟如下：
a.識別原始圖元組；
從每個線圖元的標記頂點中提取嵌入的標記，並將標記頂點恢復至嵌入標記前的狀態，利用標記識別每個圖元組的圖元，得到含水印圖元組
b.水印提取及原始數據恢復；
從每個含水印圖元組(j＝1,2,…,g(sbest))中提取認證水印並恢復矢量地圖原始數據。將恢復數據後的含水印圖元組記為從中提取出的水印序列記為wj'＝{wj,i'|wj,i'＝0,1,…,2c–1,i＝0,1,…,nr–1}。利用以下公式，將wj'轉化為二進位序列hj'＝{hj,i'|hj,i'∈{0,1},i＝0,1,…,l–1}
c.生成認證水印；
利用步驟(3)的方法，生成每個恢復數據後的圖元組的認證水印。假設為圖元組(j＝1,2,…,g(sbest))生成的認證水印為hj」＝{hj,i」|hj,i」∈{0,1},i＝0,1,…,l–1}。
d.水印認證；
依據圖元組(j＝1,2,…,g(sbest))中提取出的水印hj'和生成的水印hj」，判定該圖元組是否發生篡改。若hj'＝hj」，則該組未發生篡改；否則，該組發生了篡改。驗證完每個圖元組的完整性後，顯示所有被篡改的圖元。
本發明提出一種定位篡改圖元組的矢量地圖完整性認證方法，一方面該方法利用模擬退火方法，將矢量地圖圖元自適應地劃分為不同的組，考慮矢量地圖的精度誤差容限的前提下，採用可逆信息隱藏方法實現認證水印和圖元組別信息的嵌入，確保準確定位篡改圖元的同時，具有較好不可見性，而且無需額外存儲空間；另一方面該算法在水印認證階段，不僅能夠準確定位篡改圖元組，還能夠在認證完整性後，無損恢復矢量地圖原始數據，保證矢量地圖數據的可靠應用。與其他矢量地圖完整性認證方法相比，本發明具有以下優點：
1、本發明利用模擬退火方法，自適應地劃分圖元組，並為每個圖元標記其組別信息，能夠更準確的定位篡改圖元組；
2、本發明依據矢量地圖的精度誤差容限，設置嵌入參數，能有效控制水印嵌入給矢量地圖數據帶來的擾動，能夠保證含水印矢量地圖質量；
3、本發明利用可逆信息隱藏方法在每個圖元組中嵌入認證水印和圖元組別信息，不僅無需額外存儲空間，而且還能夠在認證完整性後，無損恢復矢量地圖原始數據，確保矢量地圖數據的可靠應用。
附圖說明
圖1定位篡改圖元組的矢量地圖完整性認證方法流程圖；
圖2嵌入認證水印前的矢量地圖(巖石邊界地圖)；
圖3嵌入認證水印後的矢量地圖(巖石邊界地圖)；
圖4發生篡改的含水印矢量地圖(巖石邊界地圖)；
圖5定位篡改的矢量地圖(巖石邊界地圖)。
具體實施方式
下面結合附圖和實例對本發明技術方案做進一步的描述：
如圖1所示，本發明定位篡改圖元組的矢量地圖完整性認證方法流程圖，該方法總體分為兩個方面：a、矢量地圖水印嵌入算法；b、矢量地圖水印認證算法。
a、矢量地圖水印嵌入算法，步驟如下：
(1)圖元頂點分類；
將矢量地圖圖元的頂點劃分為兩類：標記頂點和非標記頂點。標記頂點用於嵌入其所在圖元所屬圖元組的組別信息(即標記)，非標記頂點可嵌入認證水印。將每個線圖元的第一個頂點和最後一個頂點視為其標記頂點，其他頂點視為非標記頂點。
(2)基於模擬退火方法的圖元組自適應劃分；
依據每個圖元的非標記頂點數目，利用模擬退火方法，將矢量地圖的圖元劃分為若干組。利用如下步驟，定義利用模擬退火方法自適應劃分圖元組所需的解、評價函數和新解生成函數：
a.解的定義：將矢量地圖m的所有線圖元的一種排列視為一個解。假設矢量地圖m包含n個線圖元，將sr＝{p1,p2,…,pn}視為一個解，pi(i＝1,2,…,n)表示解sr中第i(j＝1,2,…,n)個線圖元。
b.評價函數：定義如下函數，計算解sr的評價函數值cost(sr)
cost(sr)＝n-g(sr),
其中，g(sr)表示解sr能夠劃分的圖元組數目。計算g(sr)的具體方法如下：
p1.設定每個圖元組需滿足的條件。假設每個圖元組需嵌入的認證水印的比特數目為l(l≥1)，每個非標記頂點坐標可隱藏的信息比特數目為c，則每個圖元組至少包含個非標記頂點，才能完全嵌入l比特的認證水印。假設一個圖元組中非標記頂點的數目為nc(nc≥0)，則該圖元組需滿足如下條件
nc≥nr
p2.選取解sr的第一個圖元組。將線圖元pi的非標記頂點數目記為解sr的第j(j>0)個圖元組記為gj，將解sr的前個線圖元劃分至第一個圖元組g1中，其中為滿足如下關係的最小正整數
p3.將餘下的解sr的線圖元劃分為各個圖元組。對於每個圖元組gj(j>1)，將餘下的解sr的前個線圖元劃分給該組，為滿足如下關係的最小正整數
δ表示圖元組gj之前的組(即g1,g2…,gj-1)包含的線圖元的數目，即
由於順次將解sr的線圖元劃分為各個圖元組，可能存在最後的圖元組無法完全嵌入認證水印的情況，此時，將最後一組和倒數第二組合併為一組。將解sr的線圖元劃分為各個組後，得到圖元組數目g(sr)。
c.新解生成函數：假設sr為當前解，通過隨機交換sr的兩個線圖元位置的方式，生成當前解的新解。將新解生成函數記為neighbor(·)。
利用模擬退火方法的雙層循環，自適應劃分圖元組的具體過程如下：
a.假設初始解為so，當前解為scur，最優解為sbest，初始溫度為to，當前溫度為tcur，內層循環最大次數為innermax，外層循環最大次數為outermax，當前內層循環次數為innercur，當前外層循環次數為outercur，矢量地圖m的n個線圖元依據記錄號的排列為令scur＝so，sbest＝so，tcur＝to，innercur＝0，outercur＝0。
b.利用新解生成函數neighbor(·)，由當前解scur生成新解snew。
c.依據增量δc，判定是否接受新解snew
δc＝cost(snew)-cost(scur)
kb為boltzmann常數，random為在區間(0,1)內均勻分布的隨機小數，如果δc＜0或者exp(-δc/(kbtcur))＞random，則接受新解snew為當前解，即另scur＝snew；如果接受snew為當前解並且cost(snew)<cost(sbest)，則將snew視為最優解sbest，即另sbest＝snew。
d.另innercur＝innercur+1。如果innercur<innermax，則轉入本過程的步驟b。
e.另outercur＝outercur+1，利用如下方法，依據降溫速率α，降低當前溫度tcur
tcur＝tcur×α，α＝1/(outercur+1)
如果outercur<outermax，則另innercur＝0，轉入本過程的步驟b；否則，結束該過程，將sbest視為最優解，將由sbest劃分的圖元組視為待嵌入水印的圖元組。
將sbest劃分的圖元組數目記為g(sbest)，sbest的第i(j＝1,2,…,g(sbest))個圖元組記為中圖元的數目記為中第個圖元記為
(3)生成認證水印；
利用散列算法，生成步驟(2)中每個圖元組的認證水印。將圖元組(j＝1,2,…,g(sbest))的認證水印記為hj
hj＝{hj,i∈{0,1},i＝0,1,...,l-1}
其中，l表示hj中比特的數目，hj,i(i＝0,1,…,l–1)表示hj的第i個比特。
生成認證水印hj的方法如下：
其中，i(·)表示獲取空間數據和屬性數據的方法，k表示生成hash(·)輸入參數的私鑰，vj圖元組頂點的數目，min表示該矢量地圖的索引值，hash(·)表示一個已有的加密哈希算法，grouphash(hja,l,k)表示在私鑰k的控制下從比特序列hja中選擇l比特的方法。
方法i(·)獲取圖元組的空間數據時，按照如下方法掃描該組的圖元頂點：對於一個線圖元，從具有較大y坐標的標記頂點所在端掃描至另一端，在圖元組內部，則從具有較大y坐標的標記頂點的線圖元掃描至具有較小y坐標的標記頂點的線圖元。
將hj轉換為待嵌入水印序列wj＝{wj,i|wj,i＝0,1,…,2c–1,i＝0,1,…,nr–1}，
wj,i＝hj,i×c×2c-1+hj,i×c+1×2c-2+…+hj,(i+1)×c-1×20
(4)嵌入認證水印；
利用基於量化的可逆信息隱藏方法，將步驟(3)中生成的待嵌入水印序列wj(j＝1,2,…,g(sbest))嵌入到圖元組的前nr個非標記頂點中。假設在非標記頂點vn(xn,yn)的x坐標xn中嵌入的水印為wj,i，利用如下方法嵌入wj,i
其中，
linterval為滿足如下關係的實數
τ為矢量地圖m的精度誤差容限。
在圖元組中嵌入其對應的認證水印hj後，得到含水印圖元組將的含水印線圖元記為
(5)標記圖元；
利用步驟(4)的信息嵌入方法，在含水印圖元組(j＝1,2,…,g(sbest))的每個線圖元的標記頂點的坐標中嵌入組別信息(即該組的索引值j)。
在每個圖元中嵌入標記後，得到含標記矢量地圖。如圖2-3所示，為認證水印嵌入前後矢量地圖對比情況，其中圖2為原始巖石邊界地圖，圖3為嵌入認證水印後的情況。
b、矢量地圖水印認證算法
(6)水印認證及原始數據恢復；
依據圖元標記及可逆信息隱藏方法，恢復矢量地圖數據並定位篡改，具體步驟如下：
a.識別原始圖元組；
從每個線圖元的標記頂點中提取嵌入的標記，並將標記頂點恢復至嵌入標記前的狀態，利用標記識別每個圖元組的圖元，得到含水印圖元組(j＝1,2,…,g(sbest))。假設在標記頂點vm'(xm',ym')的x坐標xm'中嵌入的標記為j(j＝1,2,…,g(sbest))，從xm'中提取j的具體步驟如下：
p1.利用下式提取標記j
其中
p2.利用下式，恢復xm'的原始數據
b.水印提取及原始數據恢復；
利用本步驟的a的公式，從每個含水印圖元組(j＝1,2,…,g(sbest))中提取認證水印並恢復矢量地圖原始數據。將恢復數據後的含水印圖元組記為從中提取出的水印序列記為wj'＝{wj,i'|wj,i'＝0,1,…,2c–1,i＝0,1,…,nr–1}。利用以下公式，將wj'轉化為二進位序列hj'＝{hj,i'|hj,i'∈{0,1},i＝0,1,…,l–1}，
c.生成認證水印；
利用步驟(3)的方法，生成每個恢復數據後的圖元組的認證水印。假設為圖元組(j＝1,2,…,g(sbest))生成的認證水印為hj」＝{hj,i」|hj,i」∈{0,1},i＝0,1,…,l–1}。
d.水印認證；
依據圖元組(j＝1,2,…,g(sbest))中提取出的水印hj'和生成的水印hj」，判定該圖元組是否發生篡改。若hj'＝hj」，則該組未發生篡改；否則，該組發生了篡改。
驗證完每個圖元組的完整性後，顯示所有被篡改的圖元。圖4所示為圖3的含水印巖石邊界地圖發生篡改後的矢量地圖，在區域a、b、c中發生了篡改。圖5中，檢測完每個圖元組的完整性後，發生篡改的圖元組的圖元顯示為深灰色。可以看出，本發明能夠準確定位篡改。