Abstract: This investigation develops a novel and blind watermarking approach suitable for street-network vector maps that records the information about roads by points and line segments. The proposed method simplifies the map using the Douglas Peucker algorithm to obtain the feature points and then subdivides the map into mesh segments. After map segmentation, the watermark is embedded in each segment. The proposed approach is superior to other vector map watermarking methods, since, it resolve the synchronization problem from the alternation of vertex coordinates. Moreover, the detection step does not require the original map in either the segmentation step or the watermarking step. Simulation results indicate that the proposed approach can withstand a variety of common attacks, including similarity transformation, map shifting, cropping, simplification and noise addition.
INTRODUCTION
The need for rapid travel has led to the appearance of digital maps in many hand-held electronic devices such as PDA, GPS and web-enabled devices. A digital map contains many layers and each layer is composed of spatial data and attributes on specified points or areas. A layer has one of two spatial representations for. One is the raster type or bitmap image, which comprises regularly arranged pixels and is adopted for satellite images, aerial photographs or other remotely sensed row data. The other is the vector type specified by geometrical properties, namely vertices, lines or high-order curves, such as depth contours, rivers, street networks or other line or point based data. Vector-type maps are superior to raster-type ones when their sizes are significantly enlarged or reduced. They do not suffer from aliasing or blocking, because the interior pixels in a line segment are redrawn by linear interpolation from the two ending pixels. Moreover, vector maps take less time to download from the web, since they have more compact descriptions than bitmaps.
However, the acquisition of the digital map takes much time, so the copyright or ownership of vector graphics must be protected. Digital watermarking techniques provide a method for the copyright protection of multimedia data. Most digital watermarking and steganographic research for the recent decade has focused on images or video, which are raster/regular data (Cox et al., 2007). The structures of raster and vector type data differ markedly, so digital watermarking approaches to raster data cannot be applied directly to vector data.
Some recent studies have addressed the issue of vector map watermarking (Kitamura et al., 2001; Kang et al., 2002; Park et al., 2002; Voigt and Busch, 2003; Ohbuchi et al., 2003). Voigt and Busch (2003) laid the map into rectangular grids and split the rectangles into two sets A and B, based on the binary random sequences generated by the secret key. The features of rectangles are then modified depending on their sets. Statistical analysis is then adopted to detect the existence of watermark. The method can resist to the coordinate change in tolerance range and Douglas Peucker simplification. Niu et al. (2006) gave a survey paper of vector map watermarking and noted some unresolved problems. Most studies does not consider the feasibility of shape preservation. Additionally, some proposed methods can resist geometrical attacks, such as translation, rotation and scaling, but cannot resist map simplification and cropping. However, in GIS applications, map simplification (map generalization in GIS terms) and cropping are common operations to obtain a reduced scale map in daily work.
In a GIS system, one map has several layers representing different characteristics. The spatial representations of these layers are mostly vector data, which comprise many points, polylines, curves or polygons. According to the connectivity of points, the vector data are classified as contour type (Fig. 1a) or street-network type (Fig. 1b) which have different properties. In general, contour maps contain more points in one polyline or curve than street maps. Oppositely, street maps have more intersections or high-degree points than street maps. Due to these distinct features, different distortion issues are considered in watermarking. Most watermarking research on vector data regards the cover map as a set of point, but does not preserve the correct topology. However, the issue of shape preserving is more important to contour maps than to street-network maps, while non-cross intersection is more important to the street-network maps than to contour maps.
Most vector map watermarking systems cannot simultaneously be applied to both types of vector data. Niu et al. (2006) presented a shape-preserving watermarking method for contour maps. The watermark is embedded in the feature points generated from map simplification, so that the method is robust to map simplification and interpolation. Pu et al. (2006) also proposed a polyline watermarking algorithm based on normal multi-resolution representation, aiming to preserve the correct topology relations of watermarked polylines. However, while these methods are feasible for contour maps, they are not usable for street-network maps and also cannot resist cropping attacks.
Map segmentation based on rectangular subdivision suffers from the synchronous problem, in which the referred point in each rectangle area must be known in the extraction step of watermarking. Regardless of malicious or non-malicious purpose, map shifting attacking alters the coordinates of points, thus vibrating the selection of the referred points. To resolve this problem, this study develops a map segmentation approach based on topological behavior, which substitutes for the conventional segmentation method based on geometrical behavior.
MAP SEGMENTATION
Vector maps contain details of geographical information and often have tens of thousands of vertices or even more. To reduce the computation overhead and increase the robustness, the watermark embedding generally precedes by subdividing a vector map into small sub-maps or blocks. Some approaches subdivided a map into equal size of blocks (Kang et al., 2002; Voigt and Busch, 2003) and Ohbuchi et al. (2002) adaptively subdivided the map so that each block has a similar number of points. However, all these schemes have the synchronization problem i.e., they need reference points for map subdivision in the extraction step. If map shifting is performed, then it may vibrate the selection of the referred points. This study presents a stable approach for map segmentation, requiring neither the original map nor the reference point for location registration. The steps of map segmentation are shown as follows.
Step 1: Simplify the map by Douglas-Peucker algorithm: First, a Douglas Peucker (denoted as DP) simplification is implemented to obtain the simplified map (Douglas and Peucker, 1973). The DP algorithm is a well-known implementation of polyline simplification. Consider a polyline with two extreme points A and B and an approximation tolerance ε. Initially, find a point C on the polyline with the greatest distance to A-B. If the distance is below ε, then the polyline is approximated using the straight line A-B. Otherwise, repeat the whole process recursively for A-C and C-B to obtain the final approximation. Figure 2 shows the process. For convenience, the DP simplification is implemented by setting ε = ∞, so that all points with degree 2 are removed from the original map. Figure 3 shows the final result.
| Fig. 1: | Vector maps; (a) contour type and (b) street-network type |
| Fig. 2: | Douglas-Peucker
simplification. The thin solid lines are the original polylines, the thick
solid lines are the simplified polylines and the dashed lines are subdivision
in the next stage |
| Fig. 3: | A map and its feature points |
Step 2: Divide the simplified map into different groups: In general, points with large degree (many polylines connecting each other at this point) are important features in a map. This study refers to points with degrees greater than or equal to a threshold L (L>2) in the simplified map as feature points. A feature point and neighboring points connected to it form an aggregation naturally. The policy is to segment the map into many groups, which are directly or indirectly adjacent to the feature points. The points in the simplified map are visited by dilation. The visited points are then added to the same group to the visiting point. Initially, all the feature points are visited. Then, the set of visited points is dilated once, i.e., the points with Dijkstra distance 1 from the visited set are added to the visited set. After dilating N times, the points with Dijkstra distance not larger than N from any feature point are added to the visited set. After the dilation operation, the process finds connected components in the visited set and places these components into separate groups.
Step 3: Assign non-simplified points into the separated groups: After the simplified map is segmented, the other points in the original map but not in the simplified one are assigned to the proper groups. If one non-simplified point is between two simplified points within the same group, then the point is added to the group. Otherwise, if the two simplified points are within different groups, then the non-simplified point is not assigned to any group.
To summarize the above steps, the detailed algorithm is shown below:
| Map_Segmentation Algorithm Input: The vertex set V in the original map Output: Subdivided groups {Gk} Calculate S by simplifying the map V with the extreme DP algorithm Let F = {fi ε S|degree (fi)≥L} For i = 1 to N F = Dilate (F, S) End for Separate F into disjoint connected components {Gk} by the connectivity in the original map For each vi in V but not in F Assume that vi is on the polyline with end points fj and fk in F If both fj and fk belong to the same group Gk |
| vi is assigned into Gk |
| Else |
| vi is not assigned into any group |
| End if End for End |
| Function Dilate(F, S) For each si in S but not in F If existing some fj in F is adjacent si to then |
| Label si as visited |
| End if End for Add all visited si into F Return F End Function |
If the connectivity topology of the map is not altered, then the segmentation procedure is stable and synchronous after other attacks. Even though some noise perturbs the coordinates of points, the segmentation result is still the same as the original one. The segmentation step also resists from DP simplification, since the feature point set F comes from the extreme DP simplification set S.
WATERMARK EMBEDDING AND DETECTION METHODS
Watermark embedding: The watermark sequence W = {w0, w1, …., wm-1} where, wi = 1 or -1 comes from a Pseudo-Random Number Generator (PRNG), whose seed can be the secret key from the owner of the map. After segmenting a map into several groups, the watermark is embedded into each group. Every group has the same copy of the watermark. And each group has several feature points, which are dilated and connected together. Consider that is one group in the segmented map, Gk = {pi|1≤i≤N}. The central point pc of Gk is defined as the mean of the feature points in Gk. In general, all pi in the group Gk encircle and pc may not belong to Gk. According to the representation of polar coordinate (ri, θi) of pi, Gk can be separated into a variety of ring sets and the jth ring set can be represented as:
Suppose that Tole is the error tolerance of the map and λ, the devisor
of the ring radius, is less than 2*Tole and kept as a secret key. The ring Rjset
can be subdivided into inner sub-ring
| (1a) |
| (1b) |
A watermark sequence W = {w0, w1, …., wm-1} with length m is then embedded into Gk. The strategy is to embed the bit W j mod m into the points in the jth ring Rj. The operation of embedding a bit 0 into pjk = (rjk, θjk) in Rj is:
| (2a) |
After the operation,
| (2b) |
| Fig. 4: | The sub-figure in the left-down corner is one group in a segmented
map. And part of the group blocked by the rectangle is enlarged in the main
figure. The solid-circle markers represent the original points and the star
markers represent the watermarked ones |
After the operation,
Watermark detection: Before detecting the watermark, the suspected map is subdivided into groups according to the steps in the last section. This investigation adopts a blind watermark scheme, where the detection step does not require the original map. To detect the watermark bits, a function ∑ (i) with 0≤i≤m is defined where m denotes the length of the original watermark sequence W = {w0, w1, …., wm-1}. Initially, all values of ∑ (i) are 0.
For each group Gk in the suspected map, find its center pc and divide into many similar to the operations in the embedding step. If a point pjk belongs to Rj, then:
| (3) |
The detection rule can be applied for each group. Compute for all points in
the suspected map. If the extracted watermark sequence is
| (4) |
Calculate the linear correlation zlc of W and W* as Eq. 5. A threshold 0<ρ≤1 is adopted to determine whether the map contains the original watermark W. If zlc<ρ then the hypothesis 0, that the watermark W is not embedded in the suspected map, is accepted. Otherwise, the hypothesis 1, that the watermark W is embedded, is accepted. The rule is represented as Eq. 6. However, the detection process does not need the original map and has no synchronicity problem.
| (5) |
| (6) |
RESULTS AND DISCUSSION
To verify the feasibility of the proposed system, experiments were performed using street-network vector maps of different sizes, as shown in Table 1. The three maps from small sized to large sized record streets or roads in one district, one county and the overall Taiwan Island. Besides the maps, some parameters must be predefined.
The length m of the watermark affects the efficiency of the embedding approach. Figure 5 depicts the embedding capacity of the maps in Table 1. To ensure that zlc = 100%, m cannot be set larger about than 100. The length m = 64 was set in the following results. The threshold L for selecting the feature points and the times of dilation N affect the number and size of groups. They are set as L = 4 and N = 3 in these experiments. Table 1 also shows the grouping condition after segmentation for three datasets.
Translation invariant: The watermark embedding adjusts the distance of points from the central point in each group. Thus, the translation attack alters both the embedded points and the central points and does not influence the embedding quantity. The algorithm is resistant to translation attacks.
Additive noise attack: Additive random noise moves the vertices and reduces the detection correctness. Table 2 presents the detection result after additive Gaussian noise with different attack strength.
| Table 1: | Street-network vector maps used in experiments |
| Table 2: | Zlc after additive Gaussian noise attack |
| Fig. 5: | The embedding capacity for the map of Kaohsiung County |
| Table 3: | Zlc after cropping attack |
| Table 4: | Zlc after DP simplification attack |
| Table 5: | Characteristics of street-network vector watermarking methods |
However, the proposed method resists to Gaussian noise with zero mean and standard deviation σ lower than the embedding strength, which is 0.5λ from Eq. 2.
Cropping attack: GIS applications often require cropping a smaller map from a larger one. Nevertheless, the watermark is repeatedly embedded in each group. In a cropped map, most groups can be defined as well as in the original map, except for several groups close to the cropping margin. For a marginal group, the center point may differ from the original one owing to cropped points. The difference may make some mistakes. Table 3 shows the extraction after cropping attack. The Daan district map has just one group and thus cannot resist cropping attack. The other maps have more than one group and thus perform well after cropping except for the case of 30% cropped Kaohsiung county. To compare the effects after cropping, the Bit Error Rate (BER) of watermark extraction in the 3rd map is also shown in Table 3.
DP simplification attack: The street-network maps possess much information about points and adjacency. The huge amount of data need long time for transmission and huge memory for storage. To decrease the transmission and display time and to reduce memory utilization, the map needs to be simplified to a rough level. DP algorithm is a common simplification method for vector maps. However, our segmentation step before watermark embedding/extraction is based on the DP simplified version, making map simplification invariable before or after simplification. Since, the number of points in one group after simplification is less than those before, thus zlc decreases (Table 4).
To compare the properties of the proposed method with previous work, Table 5 lists the characteristics of vector watermarking methods (Niu et al., 2006). Due to distinct embedding strategy, different properties are derived. Most algorithms in Table 5 cannot resist to cropping attack. The vector watermarking algorithm based on mesh spectral analysis (Ohbuchi et al., 2003) is robust to many attacks, but it needs the original map for registration, i.e., not blind. The proposed method is a robust and blind scheme.
CONCLUSION
This study presents a novel watermarking scheme for street-networks vector maps. In contrast to most previous watermarking approaches, which are designed for contour-type vector maps, the proposed method is highly promising for street-network vector maps, which are common in hand-held GIS applications. The proposed watermarking approach is blind both in segmentation step and extraction step and thus has no synchronous problem which exists in most previous methods. Experimental results indicate that the algorithm can resist against attacks such as similarity transformation, map cropping, DP simplification and noise addition.
ACKNOWLEDGEMENTS
The authors would like to thank the National Science Council of the Republic of China, Taiwan for financially supporting this research under Contract No. NSC 93-2213-E-327-003. Ted Knoy is appreciated for his editorial assistance.