Watermarking digital vector map using graph theoretic approach

Abstract

Similar to any digital dataset, a digital map is also vulnerable to modification, deliberate alteration and copyright violation. A map is a visual representation of a geographical area that is digitally stored in either raster or vector forms. Vector map is preferred over raster for both space optimization and quick processing time. Digest concept used for message authentication is extended to digitally watermark a digital map. The map digest triplet ( , and ) is generated using various features of a digital map, supplier code and customer code. The approach computes two 160-bit hash values using secured hash algorithm (SHA1)and one 128-bit digest using message digest (MD5) algorithm. These two hash values of 160 bit and one digest of 128 bit are then embedded into a sequence of nodes of the map using graph theoretic approach in such a way that any alteration in the map alters the sub-graph. The sub-graph is the watermark. There are three watermarks.

Keywords:

• geographic information system
• map digest
• steganography
• watermarking
• secure hash algorithm
• DXF
• vector map
• spatial data

1. Introduction

A map is a visual representation of an area. It is a symbolic depiction highlighting relationships among different features of an area like road, rail and soil usage. Once some theme is depicted on a map, it becomes a thematic map. More thematic maps may be produced from one base spatial map. The process of creating a digital map from age-old physical sources is called digitization of map. The field of study that deals with creation of a digital map and its composition into thematic maps is called geographic information system (GIS). It takes time, money and effort to create a map in digital form and it generally accounts for nearly 80% of the total cost of a GIS project.

Once a map is digitized, it is easy to copy, alter and sell it as an original product (Brassil et al. 1995, Date et al. 1999). Alternatively, a mischievous person may also produce this altered map as valid document in support of some false claim. It necessitates developing and placing protection mechanism against such threats so that not only are the commercial interests of investors protected but also, whenever required, the authenticity and integrity of the source can be verified. For instance, use of a digital map in a crucial military operation requires integrity verification of the map before it is put to use.

Cryptography (Stallings 1999) and digital steganography (Johnson et al. 2001) are in use to protect and secure the privacy of a message. Watermark is used to protect a map against piracy. Digital steganography is a science to hide one form of information (message) into another (cover). After embedding, the cover is called stego object. The stego object retains the vital characteristics of the cover so that it remains statistically and visually imperceptible. The process of embedding hidden information in a map without producing perceptible changes is called watermarking and the hidden information is called watermark (Memon and Wong 1998, Mauro et al. 2002). Compared to general multimedia data types, few works have been done in the area of digital vector map watermarking. To our knowledge, a corporation in Uruguay named ‘The Digital Map Ltd.’ has patented a copyright-protecting scheme for vector maps utilizing a lossless watermarking algorithm. They have also developed a commercial software called MapSN for digital map vendors (Lopez 2002). This approach is based on map interpolation and represents watermark bits by adding new vertices into the original cover map. Based on a similar approach there are some other digital vector map watermarking schemes due to Schulz and Voigt (2004) and Lopez (2002). Contrary to steganography, watermarking is used to authenticate media and therefore any change in cover media is not desirable (Karjala 1995, Gopalakrishnan et al. 1999).

Software piracy has been controlled to some extent through hardware keys or software licenses. Software licensing procedure has been made stricter in many cases by forcing the customer to register online to get a software license. However, they do not offer similar protection to the dataset being used by their software. Reasons cited are both technical and legal. Outside the GIS community this problem has been known for a long time. The mechanism using frequency domain technique has been proposed to ensure the protection of digital vector data against piracy (Xiamu et al. 2006).

One solution could be to supply GIS dataset in encrypted form for limited use. This approach binds the user to use the dataset on a specialized set of software and hardware because there exists no GIS software as of today that uses encrypted datasets. Another approach could be to disable the editing of certain features of the GIS dataset (Kumar and Sharma 2006). This approach requires a standard data format that is understood by all GIS software available to support the portability of the dataset. Unfortunately this has not been achieved till now.

In this article, we have introduced a method to watermark a digital vector map using graph theoretic approach. A map digest is generated. The map digest has three parts. The first two parts are generated using secured hash algorithm (SHA1) and therefore there are two 160-bit strings. The third part is generated using message digest (MD5) algorithm and it yields one 128-bit string. These bit strings are then embedded into the map using graph theoretic approach. A graph theoretic approach in the context of information hiding may be interpreted as a method that uses graph data structure to solve information-hiding problem. The approach is used either

•	in finding the relationship, based on mathematical function, between the smallest data unit of a message and a group of such smallest units of the cover object and representing the relationship using a graph. If required, the relationships are used to adjust the corresponding group of elements in the cover so that the portion of the cover represents the corresponding message data unit, or
•	to use a graph as cover object. In this case, redundancy is to be identified in features like node, segment and attribution data in a graph before embedding the secret message in it (Kumar and Muttoo 2009b, 2011).

In the first case, problems related to determination and representations of relationship are addressed for embedding information in the cover. In the second case, redundancy in graphs is identified. The second approach is used in this method to hide the map digest in the map. The process is explained in Section 4.

This article is organized into nine sections. Digital representation of vector map is covered in Section 2. Issues in vector map watermarking are discussed in Section 3. Approach to watermarking scheme is introduced in Section 4. In Section 5 we have outlined the algorithm to generate a map digest and its embedding in the map. An illustrative example showing the way a map digest is created and then used to watermark the map is given in Section 6. Authentication protocol is explained in Section 7. Section 8 contains steganalysis of the embedding algorithm. Finally this article is concluded in Section 9.

2. Digital representation of vector map

Digital vector map is composed of spatial data and attribute data. Spatial data describes the geographical locations of an object in the real world in the form of a sequence of coordinates in a geographical coordinate system. Attribute data describes the properties of map objects such as their names, categories and related information. Different themes are represented by using labels, colours and charts. Spatial data consists of three basic geometrical elements: node, segment and point. Segment is a poly-line that contains a number of intermediate points (Kumar and Muttoo 2009a). Intermediate points are included to draw a curved segment. Many GIS software build polygons (regions) from poly-lines. The information recorded by the attribution data is important and is not generally modified (Schulz and Voigt 2004).

Maps are digitally compiled from data available through various sources. The source may be from age-old archived maps to snaps taken by remote-sensing satellite. The three basic components – node, segments and intermediate points – of a map are stored in the following file:

1.	node,
2.	segment,
3.	data and
4.	segment.dbf

Out of the four files, segment.dbf is a database file and the others are binary files. A segment has attributes like segment number, number of intermediate points, coordinates of these intermediate points, a rectangular extent within which the segment lies (maximum bounding rectangle extent) (Kumar and Muttoo 2009a), length of the segment, the node pairs defining the segment (start and end nodes) and name of the segment. Information related to a segment is stored in three files. Since the number of intermediate points varies from segment to segment, all such intermediate points are stored in a separate file called ‘data’. Offset in the data file, where intermediate points corresponding to the segment are written, is stored in a file called 'segment'. The file ‘node’ contains information related to nodes (Kumar and Muttoo 2009a).

In order to facilitate the display of a map on a screen independent of its resolution and size, coordinates of the leftmost top corner and rightmost bottom corner (or rightmost top corner and leftmost bottom corner) are also stored in a database file extent.dbf. There may be more than one map within the same extent and all such maps are stored with different names. Files related to a map are kept in a directory and the directory is called the map. Information about the number of maps and its attribute is written in graph.dbf. Thus metadata about graphs (maps) are written in

1.	extent.dbf,
2.	graph.dbf and
3.	<Name of graph as directory>.

With the advent of GIS tools, most cartographers use these tools to generate new maps or to edit and recompose the existing maps to reflect the present geographical situation. One of the vector GIS tools is GISNIC (Kumar and Sharma 2006). To facilitate data interoperability of 2D and 3D drawings between AutoCAD and other programs, Autodesk developed in 1982 an open-sourced computer-aided design (CAD) data file format. The file format is known as DXF (Drawing Exchange Format). A DXF file is composed of several sections (DXF reference 2008). Each section has a code that is associated with its value. The code begins with a 0 followed by a string and ends with a 0 followed by ENDSEC. A DXF file can represent almost all CAD drawings (DXF Reference 2008).

3. Issues in vector map watermarking

A watermarked map must retain its watermark/fingerprint to achieve the goal even after it undergoes various attacks. The possible attack on a GIS map could be geometric attack, vertex attack, vertex reordering and noise distortion. A successful attack implies removal of the watermark while retaining the fidelity of the cover data. The spatial data of vector maps is virtually a floating point data sequence with a certain precision. Transformations like translation, rotation and scaling are the main forms of geometrical attacks. Since it involves coordinate transformation, no information is lost if information is not stored in coordinates. Alternatively if GIS data is cleaned, built and projected into the required projection system before watermarking it, this limitation can be overcome. Therefore, geometrical attacks are relatively easy to defend in vector map watermarking schemes.

Vertex attack implies adding new vertices into the map (interpolation) or removing vertices from the map (simplification or cropping). Such attacks, especially the map simplification and cropping, are very serious to vector map watermarking. Map simplification is a common operation in GIS applications. As a result, the ability of surviving the map simplification is very important for a robust watermarking scheme. All objects are stored in the map file in a certain order. Either reordering the objects in the map or reordering the vertices within an object can produce a new map file without degrading the data's precision. To some watermarking scheme which is dependent on the objects' order, this operation will be a fatal attack.

There is a possibility of noise distortion. Two sources could introduce noise into vector maps: file format exchange through import/export feature and an attack. The first is essentially required to implement portability of GIS datasets. The second one is unwanted but cannot be ignored. However, insertion of noise is easily detected because it compromises the fidelity of map datasets.

While watermarking a vector map, its fidelity must be retained (Su et al. 1999, Aspert et al 2002). The term fidelity is often used as a measure of a map's validity in the watermarking world. However, according to the different data types and their respective usage, the term fidelity has different meanings. Available watermarking algorithms for digital vector maps use coordinates of spatial data to embed watermark/fingerprint. Every vector map has a precision tolerance which gives the maximum amplitude of the allowed distortions for the coordinates. The distortions of coordinates definitely below the tolerance will not degrade the map's fidelity. The following principles have been considered while developing the methodology:

1.	We need to protect only precious data. The legal copy of a precious data is equally valuable and it has the same market value. If while making a copy, its quality is compromised and its market value is diminished to the extent that copying becomes economically infeasible, then piracy can be controlled.
2.	We find a way to embed the watermark such that neither any coordinate in the cover map is modified nor any extra feature is added to the cover map, that is, the map is treated as naturally watermarked.

4. Outline of the approach

Map digest is defined as a one-way hash function that takes an arbitrary map as its input file and produces a string of bits of fixed length. It is built upon the most common cryptographic hash functions MD5 and SHA-1 (Rivest 1992, Stallings 1999). A map digest has three parts: , and .

1.	The first part is based on the number of nodes, segments, intermediate points, regions and landmark points. It is produced using SHA1. These features are not altered by any transformation applied on the map.
2.	The second part is based on the unique registered supplier code (RSC), serial number of the map (SNM), registered customer code (RCC) and a secret key (K s). It is produced using SHA1. This information is immune to any alteration made in the map.
3.	The third part is obtained from the complete map after exporting it into DXF. It is produced using MD5 algorithm. This part together with the first and second parts of map digest is used to determine whether the map is altered and a fake copy is made.

The map digest inherits the property of MD5 and SHA1 and it is infeasible to find two maps having the same map digest and also given a map digest it is infeasible to reconstruct a map with the same map digest. Two maps G₁ and G₂ are said to be equal if the number of nodes and the corresponding coordinates, number of segments, corresponding end nodes, number of intermediate points in the corresponding segments and their coordinates are all equal in G₁ and G₂, that is, G₁ and G₂ are exact copies of each other. Now we prove a theorem.

Theorem 1:

If map digest () of any two distinct maps G₁ and G₂ are not equal, that is, if G₁ ≠ G₂ then (G₁) ≠ (G₂).

Proof: Let (G₁) = ( (G₁), (G₁), (G₁)) and (G₂) = ( (G₂), (G₂), (G₂)) be map digests for two maps G₁ and G₂, respectively. Two digests are equal iff the corresponding elements in triplets are equal:

Let N ¹, S ¹, IP ¹, R ¹ and P ¹ be the number of nodes, segments, intermediate points, regions and points features, respectively, in map G₁ and N ², S ², IP ², R ² and P ² be the number of nodes, segments, intermediate points, regions and points features, respectively, in map G₂. The concatenated strings N ¹|| S ¹|| IP ¹|| R ¹|| P ¹ and N ²|| S ²|| IP ²|| R ²|| P ² are equal iff these features are individually equal. Therefore if the count of any features differs in two maps, we have

In case of (G₁) = (G₂), the second part of the two digests can never be equal because keys and used for generating the second part of the digest are not equal. This is true even for two copies of the same map sold to the same suppliers for the same customer and thereby controls unauthorized copying of a map at the supplier or customer end.

For two different maps, the corresponding DXF files are different and hence by the inherent property of MD5 algorithm, their third components are also different. Therefore,

While embedding the map digest, the 160-/128-bit string is converted into a sub-graph (sequence of nodes) of the map. This sub-graph is a watermark, naturally placed in the map (Kumar and Muttoo 2009a, 2011). The first part of the digest is embedded in a set of nodes forming a sub-graph (H₁) of the map G. The second part is embedded in another sub-graph (H₂) and the third part in a sub-graph (H₃) of the map G. We call this sub-graph a map digest. This is the theme of this article. The schematic diagram of the presented approach is given in Figure 1.

Figure 1. Schematic diagram of watermarking approach: (a) part 1, (b) part 2 and (c) part 3.

Let us now discuss the algorithm to create the map digest and watermark and then embedding of the watermark in the map.

5. Map digest and watermarking algorithm

Let G be the vector map to be watermarked. The map digest = ((G), (G), (G)) is to be generated and embedded in the graph G. Take the map in its native form. By native form we mean the format of data supported by the GIS software for storing the map in digital form. Basic cleaning and building of polygons are performed on the basic spatial data before watermarking is done. We consider a vector map in two parts:

a.	spatial data part and
b.	complete map that includes both spatial and attribution data.

5.1 Map digest generation

We assign a unique serial number to the map G and call it SNM. Then we find the counts of features: nodes (G_n ), segments (G_S ), intermediate points (G_ip ), regions (G_r ) and landmark points (G_p ), from the graph.dbf file. The size of the data is 20 bytes (4 bytes for nodes, 4 for segments, 4 for intermediate points, 4 for regions and 4 for landmark points). These 20 bytes are repeated 3 times to get 60 bytes and then the maximum of the 5 values is concatenated with the 60 bytes to make it 64 bytes. The 64 bytes form the input block for SHA1 algorithm to produce a 160-bit (G). The procedure is outlined in PROC 1.

PROC 1: Procedure to compute (G)

PROCEDURE (G)

Step 1:	=	Read Gn , Gs , Gip , Gr , Gp from graph.dbf
Step 2:	=	Concatenate the 20 bytes value together to get str1
Step 3:	=	Make a string str2 = str1 || str1 || str1
Step 4:	=	Compute str2 = str2 || max(Gn , Gs , Gip , Gr , Gp )
Step 5:	=	(G) = SHA1(str2)

Features G_n , G_s , G_ip , G_r , G_p of a map remain intact even after a map undergoes any transformation from one coordinate system to another or any exchange of data format for portability. However, it is fragile to map simplification process. To overcome this limitation, the second part – (G) – of the digest is used. To generate the (G) the values of SNM, RSC and RCC are determined and recorded. Each of these values is 10 bytes long. The string is repeated to make it 60 bytes and a secret key Ks of 4 bytes is added before it is sent to SHA1 to produce 160-bit hash values. The procedure is given in PROC 2.

PROC 2: Procedure to compute (G)

PROCEDURE (G)

Step 1:	=	Generate SNM.
Step 2:	=	If Supplier is registered, read RSC
Step 3:	=	Else register the supplier and generate RSC
Step 4:	=	If Customer is registered, read RCC
Step 5:	=	Else register the customer and generate RCC
Step 6:	=	Concatenate the 30 bytes value together to get str1 = SNM || RSC || RCC
Step 7:	=	Make a string str2 = str1 || str1
Step 8:	=	Compute str2 = str2 || K s
Step 9:	=	(G) = SHA1(str2)

This second part of the digest (G) is totally independent of the map features and hence not altered by any operations performed on the map. In case of any disputes, if this value is retrieved from the map, it not only authenticates the ownership of the map but also proves any unauthorized alteration that might have been carried out on the map. The third and last part (G₁) of the digest is generated for the entire map. It involves the following steps:

Step 1:	=	Take the vector map in its native data format.
Step 2:	=	Export it to Drawing Exchange Format (DXF).
Step 3:	=	Use this DXF file, which is a text file as input to MD5 algorithm to get the 128-bit digest.

Now the map digest triplet ((G), (G), (G)) is to be embedded in the map to watermark the map. Once the map digest is generated, it is required to determine the corresponding sub-graph that holds the map digest part. This sub-graph is the watermark. Let us determine the sub-graph and the number of nodes in that sub-graph.

5.2. Time complexity of map digest generation

Determining the time complexity of an algorithm requires derivation of an expression that finds the number of steps needed to complete the task as a function of the problem size n. The time complexity H() of the algorithm to generate the map digest is

(1)

where h ₁(), h ₂() and h ₃() are functions representing the time complexity of functions that computes (G), (G) and (G), respectively. We know that the time complexity of SHA1 and MD5 is of O(n) for input data of size n bytes.

Since the input data for and are of fixed size of 64 bytes and the algorithm used is SHA1,

(2)

(3)

While computing , the map is converted to DXF. The size of the DXF file depends on the number of spatial features and attribution data. Let the size of the DXF file corresponding to map G be n bytes. The complexity of MD5 algorithm used to generate the 128-bit is then of O(n), that is,

(4)

Time complexity H() therefore can be written as

(5)

Therefore, the complexity of the map digest generation is of O(n) where n is the number of bytes in the DXF file corresponding to the map G.

5.3 Number of nodes required for (G), for k = 1, 2, 3

Let n be the number of nodes in map G which can be represented by bits. We take one extra bit padded in the leftmost side to indicate whether the next node is adjacent in the map. If X is the number of bits required to represent a node then

(6)

When the padded bit of node v_i is 0, then v_i is not adjacent to v_{i +1} in the sequence of nodes that constitutes the sub-graph for the part of the map digest. If the bit is 1 then v_i is adjacent to v_{i +1}. Let H _k be the sub-graph for (G) for k = 1, 2, 3. The total number of nodes Y_k required to embed (G) is given by the expression

(7)

And the last node in the sub-graph H _k is represented by only

(8)

left-over bits from the size of ((G)) bits map digest. It is obvious that the size of ((G)) is either 160 bits or 128 bits. To represent the last node in H _k (X – Z_k ) ZERO bits are padded in the left side of Z_k . For example if the number of nodes in the map is 100, then X = 8, Y_k  = 23 for k = 1, 2 and Y_k  = 19 for k = 3. Similarly Z_k  = 6 for k = 1, 2 and Z_k  = 2 for k = 3. Therefore 2 bits, 00, are padded for k = 1, 2 and 6 bits for k = 3.

5.4 Watermarking map

The watermark is a sub-graph of the map. Here instead of embedding the watermark in the map by changing any of the features of the map, we are searching for the watermark in the map according to its map digest ( (G), (G), (G)). The watermark must be present in the map. Thus embedding is done in a sustainable way (Kumar and Muttoo 2011) by associating the nodes of the map with bits of (G), k = 1, 2, 3. It is possible that there may not be a node corresponding to a bit string because the values corresponding to the bit string may be greater than the total number of nodes in the map G. In that case we treat that node a virtual node. Each part is embedded separately and independently. Let WT_K[Y_k ] be the array that stores the watermark. Each element of the array is of X bits. The procedure is outlined in PROC 3.

PROC 3: Embedding of (G) in G

Step 1:	=	Split (G) into Yk bit strings each of (X – 1) bits except the last one. The last one is Zk bits such that |(G) | = (X – 1)(Yk – 1) + Zk
Step 2:	=	Pad one ‘0’ bit to the left side as MSB (Most Significant Bit) of all (Yk – 1) bit strings except the last one. In the last bit string pad (X – Zk ) bits in leftmost side. In case of virtual node, pad two zero bits and this node is logically isolated node.
Step 3:	=	Store all Yk bit strings in WT_K[Yk ].
Step 4:	=	For I = 2 to Yk doIf WT_K[I – 1] and WT_K[I] are adjacent then Make MSB (WT_K[I – 1]) = 1

The WT_K[Y_k ] is the watermark which is nothing but a sequence of nodes related to the map. If drawn according to adjacency maintained in WT_K[Y_k ], it is a sub-graph Hk of map G. We get a triplet of watermark corresponding to the map digest triplet ( (G), (G), (G)). The robustness of the watermarking scheme is discussed in Section 8.The records related to the watermark are maintained in 1–3. Since the values are very large, only the template of the table is provided to maintain readability of this article.

Table 1. Information related to (G) and H₁

	Features count string
SNM	Gn	Gs	Gip	Gr	Gp	(G)	H 1(G)
Note: Gn, number of nodes in map G; Gs, number of segments; Gip, number of intermediate points; Gr, number of regions; Gp, number of landmark points.

Table 2. Information related to (G) and H₂

SNM	RSC	RCC	K s	(G)	H 2(G)

Table 3. Information related to (G) and H₃

SNM	(G)	H 3(G)

5.5. Records maintenance tables

The watermark is now created and naturally embedded in the map. Now we see how this information is utilized to authenticate and ascertain the ownership of a map in case of any dispute.

6. Illustrative example

Let G be a graph such that G_n  = 500, G_s  = 1000, G_ip  = 10,000, G_r  = 50 and G_p  = 100. Now the input to SHA1 to generate (G) is obtained by concatenating G_n , G_s , G_ip , G_r and G_p in that order. Let this string be str1. Now repeat str1 thrice before concatenating at the end max {G_n , G_s , G_ip , G_r and G_p } to get 64 bytes. Let the string be str2. Therefore,

and

Now the hash value of str2 as determined by HashCalc 2002 is as below:

(9)

For computing (G), suppose SNM, RSC and RCC are, respectively, 2011090101, 0101000001 and 0101000001. Let the key Ks be equal to ‘A9C1’. Now the input to SHA1 to generate (G) is obtained by concatenating SNM, RSC and RCC in that order. Let this string be str1. Now repeat str1 twice before concatenating Ks at the end to get 64 bytes. Let the string be str2. Therefore,

and

Now the hash value of str2 as determined by HashCalc 2002 is as below:

(10)

Now to determine (G), the map is exported to DXF. The map G under consideration is shown in Figure 2. The dotted and broken segments represent continuation of the map. Some nodes are not shown to maintain visibility of the shown nodes and presented concept. The MD5 of the DXF file corresponding to the map G of Figure 2 is given in Equation (11). The digest is computed using tools:

(11)

Figure 2. A map G under consideration for computing map digest.

Now let us determine the sub-graph, that is, the sequence of nodes from graph G that hides the three parts of map digest. From Equation (6)(4), the number of bits X required to represent a node in G is 10. Thus, we split the 160 bits of (G) and (G) and 128 bits of (G) in 9 (10 – 1) bit group. Each such group represents a node in the graph. The bit sequence and the corresponding sequence of nodes obtained from map G for (G) are as below:

Bit sequence:

Node sequence:

201, 418, 229, 148, 242, 283, 48, 202, 149, 246, 84, 249, 440, 257, 305, 300, 252, 94

Similarly, the bit sequence and the corresponding sequence of nodes obtained from map G for (G) are as below:

Bit sequence:

Node sequence:

197, 277, 203, 175, 173, 153, 496, 480, 56, 237, 442, 400, 263, 480, 165, 296, 322, 39

And the bit sequence and corresponding sequence of nodes obtained from map G for (G) are as below:

Bit sequence

Node sequence:

191, 84, 256, 228, 139, 250, 376, 69, 35, 239, 44, 127, 506, 421, 2

The watermarks are WT_1[18], WT_2[18] and WT_3[15]. Let us, for illustration, now assign some values to WT_3[15]. While maintaining the adjacency, one bit is padded as the leftmost bit (LMB) and the bit is set to 1 if the node corresponding to WT_3[1] is adjacent to WT_3[2] in the map G. Since node number 191 is not adjacent to node number 84, WT_3[1] = 0010111111. However, node number 256 is adjacent to node number 228; thus WT_3[3] = 1100000000. In this way we can assign values to WT_1[1…18], WT_2[1…18] and the rest of the values in WT_3[1…15]. One exception is a virtual node 506. Thus WT_3[13] = 00111111010.

7. Map authentication protocol

As mentioned by Craver et al. (1998), mere existence of a watermark is not sufficient to prove ownership. We have considered natural embedding of map digest to watermark the map. Let us consider the two possible cases:

	(a) A is the owner and B the aspiring forger or
	(b) A and B are claimants of the ownership of the map.

A map may be distributed from many locations. However, SNM is generated in a synchronous way maintaining absolute uniqueness of the serial number of a map even if it is a true copy of the same map, that is, fingerprinting a map.

In case of (a) any attempt by B to remove/destroy the watermark changes the fidelity of the map reducing its market value and scope of usability. While determining that A is the owner of a map, in disputes one or the other of the following may be available about the unauthorized copy of a map with B:

1.	The map is without any alteration.
2.	The SNM is known.
3.	The map composition is altered but the basic spatial data is unaltered.
4.	The basic spatial data is also altered within the tolerance limit to the extent that map fidelity is retained.

In the case of (1) and (3) above, (G) is generated from the spatial data of the map in possession of B and the details are determined from Tables 1–3 to verify the fact. It is the simplest case of authentication. In case of (2) above, (G), (G) and (G) are retrieved from the tables using the SNM and compared with (G), (G) and (G), the map digest of map with B. It helps in determining the stage of pilferage and/or extent of unauthorized modification carried out in the map. Figure 3 describes the process.

Figure 3. Authentication process.

The watermarking scheme introduced in this article has the advantage that if any one of the three parts of the digest is known or retrieved the other two are also retrieved. However, it has limitations of losing the watermark if the node is renumbered in such a way that some nodes in sub-graph (watermark) are also affected. The renumbering is nevertheless protected by the essential requirement of linking of attribution data. The second part of the digest –(G) – is independent of the features of a map. In case of (4), the supplier/customer code of B's copy is required to search the SNM. Once the suspected source of leakage is guessed, the corresponding SNM is fetched from Table 2 and the rest is verified as it is done in case (2) above.

In case of (b), that is, when both A and B are claimants of the ownership, two tests are performed. Test 1 is performed on the present copy and Test 2 on the original copy with A and B. The results are tested for the presence of watermark in two copies of the maps (Craver et al. 1998). The possible results of the test are summarized in Table 4. In the table, X_A and X_B are checks for the existence of watermark triplets in copies of A and B, respectively. Letters a, p and d stand for absence, presence and don't care, respectively. Cases 1–4 are clear; however, case 5 shows a potential ownership deadlock. This does not arise unless both the maps are similar and the RSC and RCC codes are also similar, that is, both A and B are dealing with the same registered suppliers of the map and have sold the copy to the same customer. On the other hand, if they have different suppliers then either A is a registered customer of the supplier with B or B is a registered customer of the supplier with A. The physical verification of the documents resolves the deadlock. The schematic diagram of the authentication process is shown in Figure 3.

Table 4. Ownership resolution criteria

	Test 1		Test 2
Possible cases	XA	XB	XA	XB	Derived ownership
Case 1	p	a	d	d	A
Case 2	a	p	d	d	B
Case 3	p	p	p	a	A
Case 4	p	p	a	p	B
Case 5	p	p	p	p	Document verification

Let us now discuss the robustness of this watermarking scheme, the level of distortions a map can withstand to retain the watermark in it.

8. Steganalysis

The watermark scheme, introduced in this article, hides the watermark naturally in the map, introducing no distortions in spatial or attribution data. Thus undetectability is achieved by default. The capacity of the object to be watermarked is directly proportional to the number of nodes in the map. Let Y be the number of nodes required in a map to embed map digest and Y_k (k = 1, 2, 3) be the number of nodes used for embedding (G), (G) and (G). The number of nodes required for embedding the map digest triplet is given by the inequality

(12)

because some nodes may be common in the triplets. Let n be the number of nodes required to hide map digests in the map G. For 448 (160 + 160 +128) bits, the required number of nodes Y is given by

(13)

The minimum value of X should be such that

(14)

Therefore the map must have at least 128 nodes to be watermarked according to this scheme. In practice a map that really needs protection against piracy has nodes something in tune of thousands. A common principle followed by all watermarking schemes is that the embedding of hidden messages should not degrade the validity of the cover data (Ohbuchi et al. 1998, Zeng and Liu 1999). The term fidelity is often used as a measure of the data's validity in the watermarking world. In whatever few algorithms for watermarking vector map exists, the space for embedding the watermark is provided in the spatial data, that is,. the coordinates of the vertices. However, in the proposed watermarking algorithm, no coordinate is changed in the map to hide the watermark. In fact nothing is changed in the map.

A digital watermark is called robust if it resists a designated class of transformations whereas a fragile digital watermark fails to be detectable after the slightest modification. A digital watermark is called semi-fragile if it resists benign transformations, but fails detection after malignant transformations (Cox et al. 1997).

The watermarked (stego) map withstands editing of point features, cleaning of the map and building of polygons (Kumar and Sharma 2006), because these simplification processes alter neither the nodes (number) nor the coordinate of any of the intermediate points. A vector map is exported and imported from one format to another format like ASCII, DXF and E00 for using the same map in different GIS software. The watermarking algorithm presented retains all the features of the stego after export (and then import) or vice versa. However, as any steganographic algorithm suffers from tempering related to editing of the stego object, this approach is also prone to drastic editing of the graph. Since any malignant transformation would render the vector map unusable, it will be economically infeasible to drastically edit the watermarked map. Theoretically the presented watermarking scheme is semi-fragile but practically it is robust. Also the algorithm presented is statistically imperceptible.

9. Conclusions

Once digital, data can be easily stored, copied and transferred without losing its original characteristics in a straightforward and inexpensive way. The data is collected and maintained by the data provider and used by others by paying for it. Technically the approach is practical in the era when the bulk of the data exchange takes place through computer communication network. Since GIS projects have similar requirements in terms of data, the possible way to manage costs could be cost-sharing approach. Illegal copying can be controlled if it is made computationally or economically infeasible. The map digest approach facilitates copying and replication of digital dataset for easy distribution by ensuring that any illegal copy can be detected by retrieving its watermark. We have used Gtools to create (G) and HashCalc 2002 to create (G) and (G) while implementing the algorithm. The GISNIC GIS software has been used to compose a map and export it to DXF and for other GIS operations performed on the spatial and attribution data of a map.

The map digest can recognize the copyright ownership for the dataset. The information relating to the contract between the data producer and client is embedded in the dataset (Thorner 1997, Voyatzis and Pitas 1999). In case of unauthorized use of the contents, the producer can recover the embedded information and can produce it in a court. The approach presented in this article helps in creating functionally identical copies with different map digests for different registered users. The study of the watermarking technology for digital vector maps is carried out for providing a level of security to protect both commercial and intellectual interests. The watermarking scheme of a digital vector map must withstand serious attacks that may include map simplification, cropping and additional noise. Other attacks like geometrical transformation and data reordering are relatively easy to defend because they virtually cause no information loss.

The algorithm produces a unique map digest for a given map and it is embedded in the map without introducing any distortion. The process preserves all the basic properties of the original map in the watermarked map. The recovered watermark can be used not only to prove ownership in a court but to verify its authenticity as well. The invisible watermark survives any attacks attempting to remove or damage the watermark under the constraints of retaining fidelity of the map. Steganalysis performed on the approach confirms the same. Further, the approach helps in retrieving the watermark to show whether the copy is legal or otherwise. The work may be extended to other GIS data exchange format like E00 and ARC/Info ASCII.

Acknowledgements

Existence of a problem inspires one to find its solution. To put a solution in place, resources are required. We are very grateful to all those who have been constantly encouraging and providing the required resources for such scientific research work besides the regular work which we are doing in our respective departments.