CN105488434B - A kind of map vector completeness certification method based on label - Google Patents

Abstract

The invention provides a mark-based vector map integrity authentication method. The method includes the following steps: identifying vertex coordinates that can be embedded with watermarks; adaptively dividing graph element groups; generating authentication watermarks; embedding authentication watermarks; marking graph elements; watermark authentication and lossless restoration of original data. The invention adaptively divides vector map primitives into different groups, and adopts a reversible information hiding method to embed authentication watermarks under the premise of considering the precision error tolerance of vector maps, and based on the method of inserting vertices, in each map Marks are added to the element to indicate the group of primitives it belongs to, so as to ensure the correct division of the group of primitives in the watermark authentication stage, while accurately locating the tampered primitives, it has better invisibility, and can tolerate the disorder of primitives and reverse order attacks of vertices; On the one hand, in the stage of watermark authentication, after removing the mark and extracting the authentication watermark, the algorithm restores the original data of the vector map losslessly, which can effectively ensure the accurate use of the vector map data.

Description

A Marker-Based Vector Map Integrity Authentication Method

technical field

The invention relates to the fields of geographic information science and information hiding, in particular to a marker-based vector map integrity authentication method.

Background technique

Nowadays, as the basic data of Geographical Information System (GIS), two-dimensional vector maps are widely used in urban planning, post and telecommunications, transportation, navigation, surveying and mapping and other fields. Obtaining vector data is expensive. However, with the help of information processing tools and public networks, these vector data can be copied, modified and published conveniently and quickly, which makes the integrity authentication and authenticity identification of two-dimensional vector maps increasingly prominent.

In order to meet the requirements of data integrity authentication and authenticity identification, digital signature technology has been proposed. However, this technology can only identify whether the data has been tampered with, but cannot locate the tampered location. Once it is found that the data has changed, no matter whether the tampered data is required data or unnecessary data, it will be considered that the data has been tampered with and cannot be used, and it is necessary to obtain the data again, which increases the time and cost of data acquisition, and gives some people who need to obtain data in a timely manner. applications causing unnecessary delays. In order to make up for the shortcomings of digital signature technology, fragile watermark technology emerged as an effective means of integrity authentication, and has become a hot spot in the field of integrity authentication of geographic information products in recent years.

In addition, the patent application number CN201210566500, titled "a multi-level authentication method for the integrity of shp line surface layer"; the patent application number CN201210189469, titled "a digital vector map integrity protection method"; the patent application number CN201210142896 , the Chinese patent document titled "A Fragile Watermarking Technology for Shp Line and Plane Layer Based on Chaotic Mapping" also involves the integrity authentication of vector maps, but it is different from the method used in this patent application, and neither can have accurate positioning and tampering at the same time , After authentication, restore the original data of the vector map and tolerate the disorder of the primitives and the reverse order of the vertices.

"Alternate game-like multi-level authentication" and "Authentication method and system" in the U.S. Patent Library are different from the content of this patent application, and the specific methods are also different.

Contents of the invention

A mark-based vector map integrity authentication method is proposed. On the one hand, the method adaptively divides the vector map primitives into different groups. On the premise of considering the accuracy error tolerance of the vector map, the reversible information hiding method is used to realize the authentication. Watermark embedding, and based on the method of inserting vertices, adding a mark to each primitive to indicate the group of primitives it belongs to, ensuring the correct division of the primitive group in the watermark authentication stage, and accurately locating the tampered primitive, while having better invisibility On the other hand, in the watermark authentication stage, after removing the mark and extracting the authentication watermark, the algorithm restores the original data of the vector map losslessly, which can effectively ensure the accurate use of the vector map data. Experimental results show that the scheme accurately locates tampered data, and it is a practical algorithm for vector map integrity authentication and tampered location.

Vector map primitives (point primitives, line primitives, and surface primitives) are formed by a large number of dense vertices arranged in a specific order, and the map data is the 2-dimensional coordinate sequence of these vertices. Vector map fragile watermarking technology is an important means to solve the problem of vector map integrity authentication and location tampering. The currently proposed vector map fragile watermarking strategies can achieve the goal of authenticating data integrity and authenticity, but these strategies are still insufficient in accurately locating tampering. In view of the problems referred to above, the present invention proposes a kind of mark-based vector map integrity authentication method, comprising the following steps:

(1) Identify the vertex coordinates that can be embedded in the watermark;

According to the accuracy error tolerance of the vector map, identify the vertex coordinates that can be embedded in the watermark; assuming that the vector map M contains N line primitives, denoted as P ₁ , P ₂ ,...,P _N , P _j represents the jth (j=1, 2,...,N) line primitives, the number of watermark coordinates that can be embedded in P _j is

(2) Adaptively divide the graph element group;

According to the number of vertex coordinates that can embed watermarks in the primitives, the vector map primitives are adaptively divided into non-overlapping groups; the authentication watermark length of each group in the present invention is L bits, and the vertex coordinates of each embeddable watermark can be embedded The length of the watermark is c(c=1,2,…) bits, and the number of embeddable watermark vertex coordinates required by each group is Suppose the number of tuple groups is N _g (1≤N _g ≤N), and the i (i=0,1,…,N _g –1) tuple group is G _i , and the embeddable watermark contained in G _i The number of vertex coordinates is If the corresponding L-bit authentication watermark is completely embedded in the tuple group G _i , and N _r need to satisfy the following relationship, Record the line primitives contained in the primitive group G _i as

(3) Generate an authentication watermark;

Use the hash algorithm to generate the authentication watermark of each graph element group in step (2); mark the authentication watermark of the graph element group G _i (i=0,1,...,N _g –1) as H _i , H _i ={h _i,j ∈{0,1},j=0,1,...,L-1}, where L represents the number of bits in H _i , h _i,j (j=0,1, ...,L–1) represents the jth bit of H _i ; convert H _i into the watermark sequence to be embedded W _i ={w _i,j |w _i,j =0,1,…,2 ^c –1,j ＝0,1,…,N _r –1}, w _i,j ＝h _i,j×c ×2 ^c-1 +h _i,j×c+1 ×2 ^c-2 +…+h _{i,( j+1)×c-1} ×2 ⁰ ;

(4) Embed authentication watermark;

Using the reversible information hiding method based on interval state values, the embedded watermark sequence W _i (i=0,1,…,N _g –1) generated in step (3) is embedded in the first N of the primitive group G _{i r} can be embedded in the watermark vertex coordinates, after embedding its corresponding authentication watermark H _i in the primitive group G _i , get the watermarked primitive group G _i ^w ;

(5) mark the graphic element;

Use the method of inserting vertices to embed a mark indicating the group of primitives in each watermarked primitive. The inserted vertex is called a position vertex. After embedding the mark in the watermarked primitive, the corresponding marked graph is obtained. According to the characteristics of the marked primitive, it can correctly identify its position vertex, and obtain the primitive group where it is located. After inserting the mark in each primitive, a marked vector map is obtained;

(6) Watermark authentication and original data recovery;

According to the primitive labeling and reversible information hiding method, the vector map data is restored and the tampering is located. The specific steps are as follows:

(6.1) Identify the original group of primitives;

According to the feature of the marked primitive in the step (5), identify the original primitive of each primitive group, and delete the inserted position vertex;

(6.2) Watermark extraction and original data recovery;

Using the embeddable watermark vertex coordinate determination method in step (1), identify the vertex coordinates of the embeddable watermark of the graph element group, extract the watermark and restore the original data of the vector map, and restore the watermarked graph element group G _i ^w ( i=0,1,...,N _g –1) is denoted as G _i ', and the watermark sequence extracted from G _i ^w is denoted as W _i '={w _i,j '|w _i,j '=0, 1,...,2 ^c –1,j=0,1,...,N _r –1}, use the following formula to convert W _i ' into a binary sequence H _i '={h _i,j '|h _i,j '∈{0,1},j=0,1,...,L–1},

(6.3) Generate an authentication watermark;

Use the method of step (3) to generate the authentication watermark of each tuple group after recovering data, assuming that the authentication watermark generated for the tuple group G _i '(i=0,1,...,N _g –1) is H _i ”={h _i,j ”|h _i,j ”∈{0,1},j=0,1,…,L–1};

(6.4) Watermark authentication;

According to the extracted watermark H _i ' and the generated watermark H _i ” in the primitive group G _i ' (i=0,1,…,N _g –1), determine whether the primitive group has been tampered with, if H _i ' =H _i ”, then the group has not been tampered with; otherwise, the group has been tampered with; after verifying the integrity of each graph element group, display all the tampered graph elements.

Suppose P _j contains u vertices V ₁ (x ₁ ,y ₁ ), V ₂ (x ₂ ,y ₂ ),…,V _u (x _u ,y _u ), V _m (x _m ,y _m )(m =1,2,...,u) means the mth vertex of P _j , x _m and y _m are the x coordinate and y coordinate of the vertex V _m respectively, and are respectively the maximum value and the minimum value of the x coordinates in the line primitive _Pj , and the specific steps of the method for determining whether the x coordinate x _m of the vertex V _m is the vertex coordinates of the embeddable watermark are as follows:

(1.1) will and The average distance between part,

in, Indicates the length of each segment, The value of must meet the following conditions,

In the formula, τ is the precision error tolerance of the vector map M;

(1.2) According to the length of each segment Compute the boundary endpoints of the segment whose coordinates x _m are located,

In the formula, Indicates the index value of the segment where the coordinate x _m is located, and represent the left end point and the right end point of the boundary that limit the range of the segment where the coordinate x _m is located respectively. x _m and as an interval

(1.3) If x _m satisfies the following conditions,

Call x _m the vertex coordinates of the embeddable watermark;

The specific steps of the method for dividing the graph element group are as follows:

(2.1) will The bar line primitives are divided into the primitive group G ₀ , is the smallest positive integer that satisfies the following relation,

(2.2) According to the method of step (2.1), divide the remaining primitives into several groups in turn, that is, for any primitive group G _i (i>0), select from the remaining primitives bar line primitive as its member, is the smallest positive integer that satisfies the following relation,

δ is the number of all primitives in the primitive group G ₀ to the primitive group G _i-1 , namely

(2.3) Since the primitives are divided into groups sequentially, the primitives of the last group may not provide enough embedding space. In this case, the primitives of the last group are divided into the penultimate group.

The method for generating the authentication watermark H _i is as follows:

H _i ＝grouphash(hash(I(G _i ),k,i,V _i ,M _in ),L,K)

Among them, I(·) represents the method for obtaining spatial data and attribute data, k represents the private key for generating hash(·) input parameters, the number of vertices of the V _i graph tuple G _i , and _Min represents the index value of the vector map, hash(·) represents an existing cryptographic hash algorithm, grouphash(H ia ,L,K) _{represents the method of selecting L bits from the bit sequence H i a} ^under the control of the private key K ^; method I(·) When obtaining the spatial data of the primitive group G _i , scan the primitive vertices of the group as follows: According to the storage order of the primitives, scan the line primitives of G _i sequentially, that is, from scan to In each line primitive, scan from the first vertex to the last vertex. The definition of the state value of the interval Q _m is as follows: Assume that the interval corresponding to the vertex coordinate x _m of the embeddable watermark is Divide Q _m into P (P≥2) sub-intervals on average, and the index value of the sub-interval where x _m is located is the state value of the interval Q _m .

Assuming that the watermark embedded in the embeddable watermark vertex coordinate x _m is w _i,j , the specific steps of watermark embedding are as follows:

(4.1) Compute the r-states for the interval _Qm ,

(4.2) Divide Q _m into 2 ^c+1 sub-intervals on average, and calculate the watermarked interval corresponding to the interval Q _m The state value s of , that is, the index value of the subinterval where x _m ' is located,

s=2 ^c ×r+w _i,j

(4.3) Calculate the watermark coordinate x _m ',

in,

Assume that the line primitives of the primitive group G _i ^w Contains f vertices, denoted as The tth vertex represented by , and are the x-coordinate and y-coordinate of vertex V _t ^w respectively, the vertex to be inserted is V _g (x _g , y _g ), and x _g and y _g are the x-coordinate and y-coordinate of vertex V _g respectively y coordinates, the specific steps of marking the graph element group G _i ^w in which it is located are as follows:

(5.1) Divide the distance between vertices V ₁ ^w and V ₂ ^w into N _t (N _t =2×N _g ) segments on average, and the length of each segment is l _t ,

(5.2) Insert the vertex V _g at the midpoint of the i-th segment, and mark it as The tuple group G _i ^w where it is located,

in,

exist After embedding the mark in , get its corresponding marked primitive Has the following characteristics:

i) The three consecutive vertices at one end are on the same straight line, and this end is the starting end of ; assuming that the vertex scanned from the starting end is The t-th vertex represented by V _t ^m (t=1, 2,...,f+1), and the x-coordinate and y-coordinate of the vertex V _t ^m respectively, are the vertex of the inserted position;

ii) According to the following method, calculate The index value i of the primitive group where it is located

The specific steps for extracting watermark information from the embeddable watermark coordinates X _m ′ of the watermarked primitive group G _i ^w (i=0,1,…,N _g –1) are as follows:

(6.2.1) According to step (4.1), calculate the watermark interval corresponding to x _m ' the r state;

(6.2.2) Divide the interval Q _m ' into 2 ^c+1 sub-intervals on average, and calculate the length l _s of each sub-interval,

(6.2.3) Calculate the state value s of the interval Q _m ',

(6.2.4) Extract watermark w _i,j ',

w _i,j '=sr×2 ^c

(6.2.5) restore the original data of x _m ',

in,

The present invention proposes a mark-based vector map integrity authentication method. On the one hand, the method adaptively divides the vector map primitives into different groups, and adopts reversible information hiding under the premise of considering the precision error tolerance of the vector map The method implements the embedding of authentication watermarks, and based on the method of inserting vertices, adding a mark to each primitive to indicate the group of primitives it belongs to, ensuring the correct division of primitive groups in the watermark authentication stage, accurately locating tampered primitives, and having It has better invisibility, and can tolerate primitive disorder and vertex reverse order attacks; on the other hand, in the watermark authentication stage, after removing the mark and extracting the authentication information, the algorithm restores the original data of the vector map losslessly, which can effectively ensure the accuracy of the vector map data. use. Compared with other vector map integrity authentication methods, the present invention has the following advantages:

1. The present invention adaptively divides graph tuple groups and marks its group information for each group, which has higher tampering positioning accuracy and effectively reduces the number of data retransmissions caused by the inability to accurately detect tampered data;

2. The present invention sets the embedding parameters according to the accuracy error tolerance of the vector map, which can effectively control the disturbance caused by the watermark embedding to the vector map data, and can ensure the quality of the watermarked vector map;

3. The present invention uses the reversible information hiding method to embed the authentication watermark in each graph element group, and adds a mark to each graph element based on the method of inserting vertices. In the authentication stage, after removing the mark and extracting the authentication information, not only can realize Integrity authentication, and the ability to restore the original data of the vector map to ensure the accurate use of the vector map.

4. The marking method adopted by the present invention can still correctly indicate the group of the primitive and the scanning order of the vertices after being attacked by the content-keeping operations of the disordered order of the primitives and the reversed order of the vertices, and attack the disordered sequence of the primitives and the reversed order of the vertices robust.

Description of drawings

Fig. 1 is a flow chart of the vector map integrity authentication method based on markers;

Figure 2 is the vector map (Gaussian snow block map) before embedding the authentication watermark;

Figure 3 is the vector map (Gaussian snow block map) after embedding the authentication watermark;

Fig. 4 The tampered watermarked vector map (Gaussian snow block map);

Figure 5. The vector map for locating tampering (Gaussian snow block map).

Detailed ways

Below in conjunction with accompanying drawing and example technical solution of the present invention is described further:

As shown in Figure 1, the flow chart of the mark-based vector map integrity authentication method of the present invention is generally divided into two aspects: A, vector map watermark embedding algorithm; B, vector map watermark authentication algorithm.

A. Vector map watermark embedding algorithm, the steps are as follows:

B. (1) Identify the vertex coordinates that can be embedded in the watermark;

C. According to the precision error tolerance of the vector map, identify the vertex coordinates that can be embedded in the watermark. The method for judging whether the x-coordinate and y-coordinate of the vertex of the graphic element are the vertex coordinates that can be embedded in the watermark is the same. The present invention uses the x-coordinate as an example to illustrate the method for judging the vertex coordinates that can be embedded in the watermark.

Suppose the vector map M contains N line primitives, denoted as P ₁ , P ₂ ,...,P _N , P _j represents the jth (j=1,2,...,N) line primitives, and P _j contains u Vertices V ₁ (x ₁ ,y ₁ ), V ₂ (x ₂ ,y ₂ ),…,V _u (x _u ,y _u ), V _m (x _m ,y _m )(m=1,2,… , u) represents the mth vertex of P _j , x _m and y _m are the x coordinates and y coordinates of the vertex V _m respectively, and are the maximum and minimum values of the x-coordinates in the line primitive P _j , respectively. The specific method for judging whether the x-coordinate x _m of the vertex V _m is the vertex coordinate that can embed the watermark is as follows:

a. Will and The average distance between part,

in, Indicates the length of each segment, The value of must meet the following conditions,

In the formula, τ is the precision error tolerance of the vector map M.

b. According to the length of each segment Compute the boundary endpoints of the segment whose coordinates x _m are located,

In the formula, Indicates the index value of the segment where the coordinate x _m is located, and Respectively represent the boundary left endpoint and the boundary right endpoint that limit the range of the segment where the coordinate x _m is located. Will x _m and as an interval

c. If x _m satisfies the following conditions,

Call x _m the vertex coordinates of the embeddable watermark. The number of embeddable watermark vertex coordinates in the line primitive P _j is recorded as

(2) Adaptively divide the graph element group;

According to the number of vertex coordinates that can embed the watermark in the primitive, the vector map primitives are adaptively divided into non-overlapping groups. In the present invention, the authentication watermark length of each group is L bits, and the watermark length embedded in the vertex coordinates of each embeddable watermark is c (c=1, 2, . . . ) bits. Therefore, the number of embeddable watermark vertex coordinates required for each group is Suppose the number of tuple groups is N _g (1≤N _g ≤N), and the i (i=0,1,…,N _g –1) tuple group is G _i , and the embeddable watermark contained in G _i The number of vertex coordinates is If the corresponding L-bit authentication watermark is completely embedded in the tuple group G _i , and N _r need to satisfy the following relationship,

Groups of primitives are divided using the following methods:

a. Will The bar line primitives are divided into the primitive group G ₀ , is the smallest positive integer that satisfies the following relation,

b. According to the method of step (a), divide the remaining graphic elements into several groups in sequence. That is, for any group of primitives G _i (i>0), select from the remaining primitives bar line primitive as its member,

is the smallest positive integer that satisfies the following relation,

δ is the number of all primitives in the primitive group G ₀ to the primitive group G _i-1 , namely

c. Since the primitives are divided into groups sequentially, the primitives of the last group may not provide enough embedding space. At this time, the primitives of the last group are divided into the penultimate group.

Record the line primitives contained in the primitive group G _i as

(3) Generate an authentication watermark;

Using a hash algorithm, generate an authentication watermark for each tuple group in step (2). Mark the authentication watermark of the tuple group G _i (i=0,1,...,N _g -1) as H _i ,

H _i ={h _i,j ∈{0,1},j=0,1,...,L-1}

Wherein, L represents the number of bits in H _i , and h _i,j (j=0,1,...,L–1) represents the jth bit of H _i .

The method of generating authentication watermark H _i is as follows:

H _i ＝grouphash(hash(I(G _i ),k,i,V _i ,M _in ),L,K)

Among them, I(·) represents the method for obtaining spatial data and attribute data, k represents the private key for generating hash(·) input parameters, the number of vertices of the V _i graph tuple G _i , and _Min represents the index value of the vector map, hash( ) represents ^{an existing cryptographic hash algorithm, and grouphash(H ia ,L,K) represents a} _method ^of selecting L bits from the bit sequence H _ia under the control of the private key K.

Method I(·) When obtaining the spatial data of the primitive group G _i , scan the vertices of the primitives in this group as follows: According to the storage order of the primitives, scan the line primitives of G _i sequentially, that is, from scan to In each line primitive, scan from the first vertex to the last vertex.

Convert H _i to the watermark sequence to be embedded W _i ={w _i,j |w _i,j =0,1,…,2 ^c –1,j=0,1,…,N _r –1},

w _i,j ＝h _i,j×c ×2 ^c-1 +h _i,j×c+1 ×2 ^c-2 +…+h _i,(j+1)×c-1 ×2 ⁰

(4) Embed authentication watermark;

Using the reversible information hiding method based on interval state values, the embedded watermark sequence W _i (i=0,1,…,N _g –1) generated in step (3) is embedded in the first N of the primitive group G _{i r} can be embedded in the watermark vertex coordinates. Assume that the interval corresponding to the embeddable watermark vertex coordinate x _m is The definition of the state value for the interval _Qm is as follows:

Divide Q _m into P (P≥2) sub-intervals on average, and the index value of the sub-interval where x _m is located is the state value of the interval Q _m .

Since the present invention embeds the watermark by changing the state value of the interval, the watermarked vertex coordinate x _m ' corresponding to x _m is still located in the interval middle.

Suppose the watermark embedded in the embeddable watermark vertex coordinate x _m is w _i,j , the specific steps are as follows:

a. Compute the r-states for the interval Q _m ,

b. Divide Q _m into 2 ^c+1 sub-intervals on average, and calculate the watermark interval corresponding to the interval Q _m The state value s of , that is, the index value of the subinterval where x _m ' is located,

s=2 ^c ×r+w _i,j

c. Calculate the watermark coordinate x _m ',

in,

After embedding its corresponding authentication watermark H _i in the primitive group G _i , the watermarked primitive group G _i ^w is obtained. Denote the watermarked line primitive of G _i ^w as

(5) mark the graphic element;

Using the method of inserting vertices, a mark indicating the group of primitives it is in is embedded in each watermarked primitive. Assume that the line primitives of the primitive group G _i ^w Contains f vertices, denoted as The tth vertex represented by , and are the x-coordinate and y-coordinate of vertex V _t ^w respectively, the vertex to be inserted is V _g (x _g , y _g ), and x _g and y _g are the x-coordinate and y-coordinate of vertex V _g respectively y-coordinate. The specific steps to mark the graph element group G _i ^w where it is located in are as follows:

a. The vertices V ₁ ^w and The distance between is divided into N _t (N _t =2×N _g ) sections on average, and the length of each section is l _t ,

b. Insert the vertex V _g at the midpoint of the i-th segment, and mark it as The tuple group G _i ^w where it is located,

in,

The inserted vertex is called a position vertex. exist After embedding the mark in , get its corresponding marked primitive Has the following characteristics:

i) Three consecutive vertices at one end are on the same straight line, this end is the starting end of . Assuming that the scan obtained from the start Vertex is V _t ^m (t=1,2,…,f+1) means the tth vertex of and are the x-coordinates and y-coordinates of the vertex V _t ^m respectively, then is the inserted position vertex;

ii) According to the following method, calculate The index value i of the tuple group where it is located,

According to the feature of the marked primitive, it can correctly identify its position vertex, and obtain its primitive group.

After inserting markers in each primitive, a vector map with markers is obtained. As shown in Figure 2-3, it is the comparison of the vector map before and after the authentication watermark is embedded, in which Figure 2 is the original Gaussian snow block map, and Figure 3 is the situation after the authentication watermark is embedded.

B. Vector map watermark authentication algorithm

(6) Watermark authentication and original data recovery;

According to the primitive labeling and reversible information hiding method, the vector map data is restored and the tampering is located. The specific steps are as follows:

a. Identify the original primitive group;

According to the feature of the marked primitive in step (5), identify the original primitive of each primitive group, and delete the inserted position vertex.

b. Watermark extraction and original data recovery;

Using the embeddable watermark vertex coordinate judgment method in step (1), the vertex coordinates of the watermark-containing embeddable watermark in the primitive group are identified, the watermark is extracted and the original data of the vector map is restored. The specific steps for extracting watermark information from the embeddable watermark coordinates x _m ' of the watermarked primitive group G _i ^w (i=0,1,...,N _g –1) are as follows:

p1. According to sub-step (a) of step (4), calculate the watermark interval corresponding to x _m ' the r state;

p2. Divide the interval Q _m 'on average into 2 ^c+1 sub-intervals, calculate the length l _s of each sub-interval,

p3. Calculate the state value s of the interval Q _m ',

p4. Extract watermark w _i,j ',

w _i,j '=sr×2 ^c

p5. restore the original data of x _m ',

in,

Denote the watermarked tuple group G _i ^w after recovering data as G _i ', and the watermark sequence extracted from G _i ^w as W _i '={w _i,j '|w _i,j '=0, 1,...,2 ^c -1,j=0,1,...,N _r -1}. Using the following formula, convert W _i ' into a binary sequence H _i '={h _i,j '|h _i,j '∈{0,1},j=0,1,...,L–1},

c. Generate authentication watermark;

Using the method in step (3), an authentication watermark of each tuple group after the data recovery is generated. Assume that the authentication watermark generated for the tuple group G _i '(i=0,1,...,N _g –1) is H _i ”={h _i,j ”|h _i,j ”∈{0,1}, j=0,1,...,L–1}.

d. Watermark authentication;

Based on the extracted watermark H _i ' and the generated watermark H _i ” in the primitive group G _i ' (i=0,1,...,N _g –1), determine whether the primitive group has been tampered with. If H _i ' =H _i ”, then no tampering has occurred in this group; otherwise, tampering has occurred in this group.

After verifying the integrity of each primitive group, display all tampered primitives. Figure 4 shows the tampered vector map of the watermarked Gaussian Mountain snow block map in Figure 3, where tampering occurred in areas A, B, and C. In Figure 5, after the integrity of each primitive group is detected, the primitives of the tampered primitive group are displayed in dark gray. It can be seen that the present invention can accurately locate tampering.

Claims (6)

1. a mark-based vector map integrity authentication method, is characterized in that, comprises the following steps: (1) Identify the vertex coordinates that can be embedded in the watermark; According to the precision error tolerance of the vector map, identify the vertex coordinates that can be embedded in the watermark; assuming that the vector map M contains N line primitives, denoted as P ₁ , P ₂ ,...,P _N , P _j represents the jth line primitive, j=1,2,...,N, the number of watermark coordinates that can be embedded in P _j is (2) Adaptively divide the graph element group; According to the number of vertex coordinates that can embed watermarks in the primitives, the vector map primitives are adaptively divided into non-overlapping groups; the authentication watermark length of each group in the present invention is L bits, and the vertex coordinates of each embeddable watermark can be embedded The watermark length is c bits, c=1,2,..., the number of embeddable watermark vertex coordinates required for each group is N _r , Assuming that the number of primitive groups is N _g , 1≤N _g ≤N, the i-th primitive group is G _i , i=0,1,…,N _g –1, the embeddable watermark vertex coordinates contained in G _i The number is If the corresponding L-bit authentication watermark is completely embedded in the tuple group G _i , and N _r need to satisfy the following relationship, Record the line primitives contained in the primitive group G _i as (3) Generate an authentication watermark; Use the hash algorithm to generate the authentication watermark of each graph element group in step (2); mark the authentication watermark of the graph element group G _i as H _i , i=0,1,...,N _g –1, H _i = {h _i,j ∈{0,1},j=0,1,...,L-1}, where L represents the number of bits in H _i , and h _i,j represents the jth bit of H _i , j=0,1,...,L–1; convert H _i into the watermark sequence to be embedded W _i ={w _i,j |w _i,j =0,1,…,2 ^c –1,j=0 ,1,...,N _r –1}, w _i,j ＝h _i,j×c ×2 ^c-1 +h _i,j×c+1 ×2 ^c-2 +Λ+h _{i,(j+ 1)×c-1} ×2 ⁰ ; (4) Embed authentication watermark; Using the reversible information hiding method based on interval state value, the watermark sequence W _i to be embedded generated in step (3) is embedded into the first N _r embeddable watermark vertex coordinates of the primitive group G _i , i=0,1 ,...,N _g –1; After embedding its corresponding authentication watermark H _i in the tuple group G _i , get the watermarked tuple group G _i ^w ; (5) mark the graphic element; Use the method of inserting vertices to embed a mark indicating the group of primitives in each watermarked primitive. The inserted vertex is called a position vertex. After embedding the mark in the watermarked primitive, the corresponding marked graph is obtained. Element, according to the features of the marked primitive, can correctly identify its position vertex, and obtain the primitive group where it is located; after inserting a mark in each primitive, a vector map with a mark is obtained; (6) Watermark authentication and original data recovery; According to the primitive labeling and reversible information hiding method, the vector map data is restored and the tampering is located. The specific steps are as follows: (6.1) Identify the original group of primitives; According to the feature of the marked primitive in the step (5), identify the original primitive of each primitive group, and delete the inserted position vertex; (6.2) Watermark extraction and original data recovery; Using the embeddable watermark vertex coordinate judgment method in step (1), identify the vertex coordinates of the embeddable watermark of the graph element group, extract the watermark and restore the original data of the vector map, and record the watermarked graph element group G _i ^w after the restored data is G _i ', i=0,1,...,N _g –1, the watermark sequence extracted from G _i ^w is written as W _i '={w _i,j '|w _i,j '=0,1 ,…,2 ^c –1,j=0,1,…,N _r –1}, use the following formula to convert W _i ' into a binary sequence H _i '={h _i,j '|h _i,j ' ∈{0,1},j=0,1,...,L–1}, (6.3) Generate an authentication watermark; Use the method of step (3) to generate the authentication watermark of each tuple group after restoring data, assuming that the authentication watermark generated for the tuple group G _i ' is H _i ”={h _i,j ”|h _i,j "∈{0,1}, j=0,1,...,L-1 _} , i=0,1,...,Ng-1; (6.4) Watermark authentication; According to the extracted watermark H _i ' and the generated watermark H _i " in the group of primitives G _i ', i=0,1,...,N _g –1, determine whether the group of primitives has been tampered with, if H _i '= H _i ”, then the group has not been tampered with; otherwise, the group has been tampered with; after verifying the integrity of each graph element group, all tampered graph elements are displayed. 2. The mark-based vector map integrity authentication method according to claim 1, characterized in that: suppose that P _j includes u vertices V ₁ (x ₁ , y ₁ ), V ₂ (x ₂ , y ₂ ), …,V _u (x _u ,y _u ), V _m (x _m ,y _m ), m=1,2,…,u, represent the mth vertex of P _j , x _m and y _m are the vertex V the x-coordinate and y-coordinate of _m , and are respectively the maximum value and the minimum value of the x coordinates in the line primitive _Pj , and the specific steps of the method for determining whether the x coordinate x _m of the vertex V _m is the vertex coordinates of the embeddable watermark are as follows: (1.1) will and The average distance between part, in, Indicates the length of each segment, The value of must meet the following conditions, In the formula, τ is the precision error tolerance of the vector map M; (1.2) According to the length of each segment Compute the boundary endpoints of the segment whose coordinates xm are located, In the formula, Indicates the index value of the segment where the coordinate x _m is located, and represent the left end point and the right end point of the boundary that limit the range of the segment where the coordinate x _m is located respectively. x _m and as an interval (1.3) If x _m satisfies the following conditions, Call x _m the vertex coordinates of the embeddable watermark. 3. the vector map integrity authentication method based on the mark according to claim 1, is characterized in that: the concrete steps of the method for described division graph element group are as follows: (2.1) will The bar line primitives are divided into the primitive group G ₀ , is the smallest positive integer that satisfies the following relation, (2.2) According to the method of step (2.1), divide the remaining primitives into several groups in sequence, that is, for any primitive group G _i , i>0, select from the remaining primitives bar line primitive as its member, is the smallest positive integer that satisfies the following relation, δ is the number of all primitives in the primitive group G ₀ to the primitive group G _i-1 , namely (2.3) Since the primitives are divided into groups sequentially, the primitives of the last group may not provide enough embedding space. In this case, the primitives of the last group are divided into the penultimate group. 4. the vector map integrity authentication method based on mark according to claim 1, is characterized in that: the described method of generating authentication _watermark H is as follows: H _i ＝group uphash(hash(I(G _i ),k,i,V _i ,M _in ),L,K) Among them, I(·) represents the method of obtaining spatial data and attribute data, k represents the private key for generating hash(·) input parameters, i=0,1,…,N _g –1, V _i graph tuple G _i vertex The number of , Min represents the index value of the vector map, hash( ) represents an existing encrypted hash algorithm, _grouphash (H _i ^a ,L,K) represents the bit sequence H _i under the control of the private key K The method of selecting L bits in ^a ; when method I( ) acquires the spatial data of the primitive group G _i , scan the primitive vertices of the group as follows: according to the storage order of the primitives, scan the line graph of G _i sequentially element, that is, scan from P _Gi,1 to In each line primitive, scan from the first vertex to the last vertex. 5. the mark-based vector map integrity authentication method according to claim 1, is characterized in that: the definition of the state value of described interval Q _m is as follows: assume that the interval corresponding to embeddable watermark vertex coordinate x _m is Divide Q _m into P sub-intervals on average, P≥2, and the index value of the sub-interval where x _m is located is the state value of the interval Q _m . 6. The vector map integrity authentication method based on markers according to claim 1, characterized in that: assuming that the watermark embedded in the embeddable watermark vertex coordinate _xm is w _i,j , the concrete steps of watermark embedding are as follows: (4.1) Compute the r-states for the interval _Qm , (4.2) Divide Q _m into 2 ^c+1 sub-intervals on average, and calculate the watermarked interval corresponding to the interval Q _m The state value s of , that is, the index value of the subinterval where x _m ' is located, s=2 ^c ×r+w _i,j (4.3) Calculate the watermark coordinate x _m ', in,