Microsoft Word - 277-284 https://doi.org/10.30526/31.1.1835 Computer | 277 2018) عام 1(العدد ) 31(المجلد مجلة إبن الهيثم للعلوم الصرفة و التطبيقية Ibn Al-Haitham J. for Pure & Appl. Sci. Vol.31 (1) 2018 Robust Watermarking Scheme for GIS Vector Maps Methaq Talib Gaata dr.methaq@uomustansiriyah.edu.iq Dept. of Computer Science/ University of Mustansiriyah Received in:6/September/2017, Accepted in:8/October/2017 Abstract With the fast progress of information technology and the computer networks, it becomes very easy to reproduce and share the geospatial data due to its digital styles. Therefore, the usage of geospatial data suffers from various problems such as data authentication, ownership proffering, and illegal copying, etc. These problems can represent the big challenge to future uses of the geospatial data. This paper introduces a new watermarking scheme to ensure the copyright protection of the digital vector map. The main idea of proposed scheme is based on transforming the digital map to frequently domain using the Singular Value Decomposition (SVD) in order to determine suitable areas to insert the watermark data. The digital map is separated into the isolated parts. Watermark data are embedded within the nominated magnitudes in each part when satisfied the definite criteria. The efficiency of proposed watermarking scheme is assessed within statistical measures based on two factors which are fidelity and robustness. Experimental results demonstrate the proposed watermarking scheme representing ideal tradeoff for disagreement issue between distortion amount and robustness. Also, the proposed scheme shows robust resistance for many kinds of attacks. Keywords: Geospatial data, Digital map, Robust Watermarking, Copyright Protection. https://doi.org/10.30526/31.1.1835 Computer | 278 2018) عام 1(لعدد ا ) 31(المجلد مجلة إبن الهيثم للعلوم الصرفة و التطبيقية Ibn Al-Haitham J. for Pure & Appl. Sci. Vol.31 (1) 2018 Introduction Digital map is a type of significant and topological information reference and is usually used in scientific research, commercial, social, and geographic applications; it is too interrelated to national security activities. The creation and modification of the digital map is too expensive and time consuming, there are some requirements required including specialized equipment’s with manual effort to obtain realistic geospatial data such as satellite image, earth's surface, aerial photography, etc. Digital watermarking system offers an optimal solution for digital map copyright protection [1]. Digital watermarking is the process to insert labels into digital object such as video, audio or images with less distortion. The watermarking applications can be classified into two types which are copyright protection and digital content authentication [9].The assurance of the originality of a digital object fragile watermarking is applied while, for the resolve of ownership problem, robust watermarking is used. Also, other classification is possible based on the domain of inserting of watermark information: spatial and frequency [2]. Commonly, digital watermarking methods need to various requirements included (1) Imperceptibility: the variation between original and watermarked object should not be perceived by naked eyes, to be exact, the quality index of watermarked object must be good enough. (2) Robustness: after the inserted watermark information is tested by using different types of attack (such as translation, scaling, rotation, compressing, filtering, cropping, sharpening, de-blurring, etc.). 3) Capacity: represents the size of watermark that can be hidden without effect on the quality index [3]. Recently, many watermarking schemes are designed to protect the copyright of digital map. In 2013, Tawfiq et al. [4] presented an intelligent watermarking approach to hide watermark into GIS digital map based on extracting some features from the digital vector map and then mix the extracted features with the watermark information. In 2014, Lee et al. [5] have proposed an imperceptible, secure, public, and robust watermarking technique that achieves the copyright protection for GIS vector digital maps by using distribution of arc length. The watermark bits are inserted embedded by modifying the arc length distribution of an appropriate group. In 2015, Penget al. [6] presented a zero-watermarking method for vector digital map. The watermark information is combined with feature vertex distance ratio in order to get high robustness against some attacks. In 2016, Wang [7] has suggested a reversible fragile watermarking scheme for finding changed Polylines/Polygons in digital vector maps. It used the fixed threshold in order to divide the areas of the vector map into certain clusters and hide the watermark of each area into the corresponding cluster. This paper is organized in the following sequence. Section 2 introduces the SVD transform. The robust watermarking scheme for digital vector map is suggested in Section 3. The experimental results and interpretations are presented in Section 4. Conclusions of this paper are provided in Section 5. Singular Value Decomposition The SVD is widely applied in digital watermarking techniques in last year due to its properties. Basically, the SVD is a numerical analysis method depending on a principle of linear algebra. In SVD transform, a rectangular object can be decomposed into the product of three matrixes. The SVD can be used with several digital signal processing operations such as pattern recognition, data compression, information hiding, and noise removal. Given a digital map with M × N matrix A with rank= R, the SVD of A is represented mathematically as: A=USVT…(1) https://doi.org/10.30526/31.1.1835 Computer | 279 2018) عام 1(لعدد ا ) 31(المجلد مجلة إبن الهيثم للعلوم الصرفة و التطبيقية Ibn Al-Haitham J. for Pure & Appl. Sci. Vol.31 (1) 2018 Where U (M×M) and V (N×N) represent the unitary matrixes. The Sis a diagonal matrix having the square roots of the eigen values from U or inV descending order. For more details about the SVD, see [8]. Proposed Watermarking Scheme The main goal of watermark scheme in this work is to protect the copyright of digital map. The proposed scheme consists of two processes are watermarking hiding and extraction. Hiding Process The proposed scheme is based on arranging the vertices of map within SVD in order to insert the watermark information into digital map. The hiding model of proposed scheme is shown in figure (1). Figure (1): The hiding model of proposed scheme. The details of each step in the proposed watermarking scheme are described in below: Extraction of Vertices In this step, the vector map will be scanned in order to extract all vertices and store their coordinates in array with one dimension. The length of array is equal to twice of vertices number in digital map. Each vertex in the map is represented using two locations in the array, one to store the x-coordinate and another to store the y-coordinate sequentially. Vector Map Watermark Extraction of Vertices Construct Host Data Arranging of Vertices Apply the SVD Hiding Watermarking Inverse SVD Rearranging of Create of Watermarked Map Watermarked Map https://doi.org/10.30526/31.1.1835 Computer | 280 2018) عام 1(لعدد ا ) 31(المجلد مجلة إبن الهيثم للعلوم الصرفة و التطبيقية Ibn Al-Haitham J. for Pure & Appl. Sci. Vol.31 (1) 2018 Arranging of Vertices After that, the all vertices which extracted will be organized in array of one dimension as shown in below: x1 y1 x2 y2 ………………………….. xn yn Where n represents the number of vertices in digital map, the xi, y irepresent the coordinate of x-axis and y-axis respectively for each vertex. Construct Host Data At this step, the partition process is applied on the created array in the previous step in order to produce set of matrixes with size 8×8. These matrixes take the role of host data to hide the watermark information. In some cases, the number of coordinates may not be in multiples of 64, therefore it is proposed to extend the coordinates in the minimum range. This extension is done by adding the 0's values in the last matrix. Apply the SVD The SVD transform can be considered as efficient mechanism to analyze the 2D objects and matrixes. One of the important reasons to use the SVD through the proposed scheme is the adding of watermark information causing trivial deformation and does not effect on the quality of digital map. In this step, the SVD transform is applied separately to each partitioned matrix (host data) which is produced in the above step. The SVD is computed for each matrix with size 8×8 to yield the diagonal matrix S and the two unitary matrixes U and V. Hiding Watermarking After applying the SVD transform on each 8 × 8 matrix, some matrixes are selected depending on complexity factor to hid watermark information. The watermark is added as follows: 1. Computing the frequency of non-zero value in the diagonal matrix S for each part. This is computed to decide the complexity degree for each part. 2. Choosing the matrixes which have the larger complexity degree based on definite threshold. This threshold is defined using trial. 3. For each chosen matrix, the watermark information inserted into coefficients of the unitary matrix U depending on the secret key: = + …(2) Where UiWis watermarked unitary matrix U with i-index, K is secret key, and the W represented the watermark information. The U matrix is used to store the watermark information in order to provide robust watermarked map. Inverse SVD In this step, the inverse of SVD is applied for each matrix in order to reproduce the watermarked matrixes after the watermark information inserted in each chosen matrix. Rearranging of Vertices Reording the watermarked matrixes back in order to recreate vertices array with one dimension to construct the watermarked map. https://doi.org/10.30526/31.1.1835 Computer | 281 2018) عام 1(لعدد ا ) 31(المجلد مجلة إبن الهيثم للعلوم الصرفة و التطبيقية Ibn Al-Haitham J. for Pure & Appl. Sci. Vol.31 (1) 2018 Create of Watermarked Map In the last step, the watermarked map will be created by returning all vertices to their coordinates in the digital map. This watermarked map holds the copyright information for map owner and can be distributed through public network in safe way. Watermark Extraction The sequence steps of watermarking extraction process are similar to the steps of watermark hiding process with some differences. The steps of watermark extraction are performed in this way: first, extraction of watermarked vertices. Second, arranging of watermarked vertices. Third, constructing matrixes with size 8×8 for watermarked vertices. Fourth, applying the SVD. Last, extracting the watermark information from coefficients of the unitary matrix U which is chosen through watermarking hiding process. Experimental Results The tests on the ten vector maps with various structures were implemented to evaluate the performance of proposed watermarking scheme. Figure (2) shows two examples of vector maps with corresponding watermarked versions which are used in this experiment. (a) (b) (a1) (b1) Figure (2): A two samples of the vector maps (a) USA map (b) Canada map; (a1) watermarked USA map (b1) watermarked Canada map. https://doi.org/10.30526/31.1.1835 Computer | 282 2018) عام 1(لعدد ا ) 31(المجلد مجلة إبن الهيثم للعلوم الصرفة و التطبيقية Ibn Al-Haitham J. for Pure & Appl. Sci. Vol.31 (1) 2018 After hiding the watermark information into the vector maps, two factors are fidelity and robustness take in consideration when evaluating performance of the proposed watermarking scheme. Fidelity of Vector Map The Fidelity term means the perceptual similarity between the original vector map and watermarked vector map. In order to evaluate the Fidelity, figure (3) shows the same area taken from the original map and its watermarked version. As observed, there is no degradation due to inserted watermark into digital map. As result from that, the fidelity is very high and the map is not affected. (a) (b) Figure (3): Fidelity Evaluation based on perceptual similarity (a) Original map and (b) Watermarked map. Robustness of Watermark The robustness of watermark is its ability to resist common attacks. This factor is based on assessing the similarity ratio between the original watermark and the extracted watermark after passing the watermarked map through some of attacks. In this work, the Bit Error Rate (BER) has been used to measure robustness of proposed watermarking scheme. The mathematical formula for BER is defined as follows [9]: % 100 , … (3) Where EB represents the number of incorrect bits in extracted watermark. While, the TB represents the number of original watermark bits. In this test, the four categories of attacks were applied on the watermarked vector map. These categories are geometrical attacks, vertex attacks, object attacks and noise addition attacks. In order to evaluate the resilience of proposed watermarking scheme to geometrical attacks, the translation, scaling, and rotation attacks have been applied on the watermarked map. In the vertex attacks, simplification process is applied to remove some vertices from watermarked map. Also, interpolation process is applied through adding new vertices into a watermarked map. With object attacks, the reordering process is applied to change the reorder of the vertices of objects. The noise addition attacks aimed to discharge the inserted watermark by adding noise randomly to vertices in the watermarked map. The results of robustness valuation are summarized in the table (1). \ https://doi.org/10.30526/31.1.1835 Computer | 283 2018) عام 1(لعدد ا ) 31(المجلد مجلة إبن الهيثم للعلوم الصرفة و التطبيقية Ibn Al-Haitham J. for Pure & Appl. Sci. Vol.31 (1) 2018 Table (1): The results of robustness valuation As noted in table (1), the experimental results prove that the proposed scheme achieve perfect restoration for the original watermark information after applying the geometrical attacks. When deleting 20% and 30% of the vertices the amount of error is 0.26 and 0.43 respectively. But, when adding some vertices to the watermarked map the error is decreased to 0.16. The reordering object vertices the error is 0.53. In the worst case, the amount of error is 2.5 for noise addition attack. The obtained results verified the proposed scheme has efficient performance against geometrical attacks and other attacks. Conclusions This paper presented robust watermarking scheme to prove ownership of the vector map based on the SVD transform. One of the strength points in proposed scheme does not require the original map at watermark extraction. The proposed scheme achieved high Fidelity level and robust against many types of attacks such as translation, scaling, rotation, interpolation, simplification, reordering, and noise addition attacks. Furthermore, some of other attacks are not taken in account such as collusion attack. In addition to, the developing of GIS watermarking scheme that mixing the vector map with aerial image. These issues are objectives to study in future works. References [1] Ahmed Abubahia and MihaelaCocea “Advancements in GIS map copyright protectionschemes - a critical review” Journal of Multimedia Tools and Applications, 76, 10, 12205-12231. 2017. [2] NamitaTiwari and Sharmila “Digital Watermarking Applications, Parameter Measures and Techniques” International Journal of Computer Science and Network Security, 17.3. 2017. [3] PreetiArya; DherendraTomar and DeepikaDubey “A Review on Different Digital Watermarking Techniques” International Journal of Signal Processing, Image Processing and Pattern Recognition, 8, 10,.129-136. 2015. [4] A. Tawfiq; Abbas and MajidJ.Jawad “Proposed an Intelligent Watermarking in GIS Environment” Journal of Earth Science Research, 1 1, 1-5. 2013 [5] Lee; Suk-Hwan; Xiao-Jiao Huoand and Ki-Ryong Kwon “Vector Watermarking Method for Digital Map Protection Using Arc Length Distribution” IEICE Transactions on Information and Systems ,.E97-D, 1,.34-42. 2014. Category Attack BRE% Geometrical Attacks [10] Translation 0.0 Scaling 0.0 Rotation 0.0 Vertex Attacks [11] Simplification 20% 3.26 Simplification 30% 6.43 Interpolation 0.36 Object Attacks [6] Reordering 0.83 Noise Addition Attacks [12] Noise distortion 4.52 https://doi.org/10.30526/31.1.1835 Computer | 284 2018) عام 1(لعدد ا ) 31(المجلد مجلة إبن الهيثم للعلوم الصرفة و التطبيقية Ibn Al-Haitham J. for Pure & Appl. Sci. Vol.31 (1) 2018 [6] YuweiPeng and MingliangYue, 2015 “A Zero-Watermarking Scheme for Vector Map Based on Feature Vertex Distance Ratio” Journal of Electrical and Computer Engineering, 2015. [7] Nana, Wang “Reversible Fragile Watermarking for Locating Tampered Polylines/Polygons in 2D Vector Maps” International Journal of Digital Crime and Forensics (IJDCF), 8, 1. 2016 [8] Anushikha Singh; NamrataRaghuvanshi and Mala Dutta “An SVD based zero watermarking scheme for authentication of medical images for tele-medicine applications” 39thInternational Conference on Telecommunications and Signal Processing (TSP), Austria- Vienna. 2016 [9] F. Zhang; X.Zhang and H;Zhang, “Digital image watermarking capacity and detection error rate” Pattern Recognition Letters,. 28, 1, 1-10. 2007. [10] H.-J. Chang; B.-J. Jang; S.-H. Lee; S.-S. Park and Kwon,K.-R(2010). “3D GIS Vector Map Watermarking Using Geometric Distribution” Proc. of IEEE International Conference on Multimedia and Expo. 1014-1017. [11] Wang, N. and Men, C. “Reversible fragile watermarking for locating tampered blocks in 2D vector maps”Journal Multimedia Tools and Applications. Springer. 67, 3, 709-739. 2013. [12] Jungyeop Kim; Sungmin Won; WenjunZeng and Soohong Park “Copyright protection of vector map using digital watermarking in the spatial domain” 7th International Conference on Digital Content, Multimedia Technology and its Applications (IDCTA).