With the rapid interest in Geographic Information System (GIS) contents, a large volume of valuable GIS dataset has been distributed illegally by pirates, hackers, or unauthorized users. Therefore the problem focus on how to protect the copyright of GIS vector map data for storage and transmission. At this point, GIS security techniques focusing on secure network and data encryption have been studied and developed to solve the copyright protection and illegal copy prevention for GIS digital map. But GIS vector map data is very large and current data encryption techniques often encrypt all components of data. That means we have encrypted large amount of data lead to the long encrypting time and high complexity computation. This paper presents a novel selective encryption scheme for GIS vector map data protection to store, transmit or distribute to authorized users using Kmeans algorithm. The proposed algorithm only encrypts a small part of data based on properties of polylines and polygons in GIS vector map but it can change whole data of GIS vector map. Experimental results verified the proposed algorithm effectively and error in decryption is approximately zero.
1. INTRODUCTION
GIS is a system which designed to capture, store, manipulate, analyze, and manage all kinds of the geographic information and it is the merging system of cartography, statistical analysis, and database technology
[1

2]
. It consists of hardware, software, and GIS data. GIS allows us to view, understand, question, interpret, and visualize data in many ways that reveal relationships, patterns, and trends in the form of maps, globes, reports, and charts.
GIS has been used in military and commercial applications for many years. The main component of GIS is the data. The GIS data has two important properties. Firstly, the effort it takes to put it in a form suitable for use in the GIS applications. This effort increases its cost. Secondly, in most cases the GIS Data contains confidential information which must be kept away from unauthorized users. Such confidential information includes GIS layers containing troop locations and additional information like movements and mines places in a tactical environment. Hence, it is very important to protect the GIS data. Moreover, the GIS data is too expensive so we have to prevent illegal duplication and distribution of it. Nowadays, it is too easy for a company to buy some GIS layers, make illegal copies from them and distribute or sell them many times without taking any permission from the original GIS data provider. So we have to enforce some kinds of access control on it because the GIS data is sensitive and must not be accessed by unauthorized users.
In section 2, we introduce related works, and in section 3 we present selective encryption scheme for GIS vector map data protection. Finally, we implement the proposed scheme, and show experimental results in section 4.
2. RELATED WORKS
The GIS vector map data includes layers. Each layer is a basic unit of geographical objects which are described and managed in a map. These objects describe the topography and geographical features of real objects or a certain place. Each layer consists of an amount of vector data which uses pairs of coordinates to describe as point, polyline and polygon
[3

4]
, as shown
Fig. 1
. Officially, the point is used to present simple or small objects in the reality on the map while polyline and polygon are used to present complex and large objects. Thus, our algorithm only performs selective encryption for polylines and polygons in GIS vector map.
An example GIS vector map with city, river and country layers; (a) Railway layer, (b) Lake layer, (c) Building layer, and (d) Railway + Lake + Building layers.
The general approach of selective encryption is to separate the content into two parts. The first part is the public part, which is unencrypted and accessible by all users
[5

11]
. The second part is the protected part; it is encrypted. Only authorized users have access to protected part. Polylines and polygons are selected, and encrypted by random keys combine with randomization and clustering process by Kmeans algorithm
[12]
, random algorithms in DCT domain based on their geographical features
[13]
. Our algorithm encrypts only some selective DC values of polylines, polygons in DCT domain but it changes the whole map.
3. PROPOSED SELECTIVE ENCRYPTION ALGORITHM
Our method aims to encrypt GIS vector map perceptually and entirely using a few of selected values, it is called as vector map selective encryption.
 3.1 Selective Encryption Process
The selective encryption algorithm follows as
Fig. 2
. Our algorithm consists of processes as data extraction to have polylines and polygons, polylines and polygons clustering using
K
clusters, vertices randomization of polylines and polygons by random coefficients using random key. Next, it applies DCT processing for randomized vertices to get DCT coefficients, and then multiply DC coefficients of each cluster with a random value which is created by another random key. Finally, it performs inverse discrete cosine transform (IDCT).
Selective encryption algorithm for polyline/polygon.
In order to encrypt selectivity, we compute the total number of polylines
N_{PLi}
, total number of polygons
N_{PGi}
in
i
^{th}
layer. Each polyline/polygon has attributes such as the number of parts and the number of points. These attributes in each polyline/polygon is different. So, we used them to classify
N_{PLi}
polylines,
N_{PGi}
polygons into
K
clusters using Kmeans algorithm. We have
N_{PLi}
polylines,
N_{PGi}
polygons in
i
^{th}
layer, and we need to cluster them into
K
groups where
K
={
k_{g}

g
∈[1,
K
]}. Each group
k_{g}
in
K
groups is described by a centroid
C_{g}
={
x_{cg}
,
y_{cg}
}. Considering number of parts
N_{paij}
and number of points
N_{poij}
in
j
^{th}
polyline/polygon are coordinates in two dimensional space. And
j
^{th}
polyline/polygon is represented as a point which has coordinates (
N_{paij}
,
N_{poij}
) in that two dimensional space. The
j
^{th}
polyline/polygon is classified in group
k_{g}
using the shortest Euclidean distance to
C_{g}
follow as equation (1).
D_{jg}
is the Euclidean distance from
j
^{th}
polyline/polygon to centroid
C_{g}
, and calculated by equation (2).
Then, we find
NL
_{imax}
of the max number of vertices in a polyline, and
NG
_{imax}
of the max number of vertices in a polygon in
i
^{th}
layer. With values
NL
_{imax}
,
NG
_{imax}
and
K
, we generated random
NL
_{imax}
coefficients where
RL
={
rl_{k}

k
{1,
NL
_{imax}
]} for polylines, random
NG
_{imax}
coefficients where
RG
={
rg_{k}

k
{1,
NG
_{imax}
]} for polygons by random key
R_{1}
using equations (3) and (4):
From
NL
_{imax}
and
NG
_{imax}
coefficients, we randomize them with vertices in polylines, polygons follow as equations (5) and (6). These random coefficients will be applied to all polylines/polygons in a layer depend on the number of vertices in a polyline/polygon because number of vertices in a polyline
NL_{i}
≤
NL
_{imax}
, number of vertices in a polygon
NG_{i}
≤
NG
_{imax}
. And each layer will be applied different random coefficients. After randomization step polylines/polygons are encrypted by random key
R
_{1}
, and we receive
N_{PLi}
new polylines with
PL′_{i}
={
pl′_{ij}

j
∈[1,
N_{PLi}
_{]}
}={
ul′
_{i,j,k}

j
∈[1,
N_{PLi}
],
k
∈[1,
NL_{ij}
]}, and
N_{PGi}
new polygons with
PG′_{i}
={
pg′_{ij}

j
∈[1,
N_{PGi}
_{]}
}={
ug′
_{i,j,k}

j
∈[1,
N_{PGi}
],
k
∈[1,
NG_{ij}
]}.
Fig. 3
(a) shows a randomized example for polyline.
Example of randomization and multiplication for polyline, (a) Randomized example for polyline, (b) Multiplying DC coefficient with random value.
We continue to apply DCT for these new polylines/polygons to get a set of transformed polylines
DL_{i}
by equation (7) and a set of transformed polygons
DG_{i}
by equation (8).
After DCT processing, we continue to encrypt polylines/polygons one more time by multiplying DC coefficients of transformed polylines/polygons with one corresponding random value to their group, from K random values follow as equations (9), (10) and
Fig. 3
(b).
K
random values are
R_{v}
={
rv_{g}

g
∈[1,
K
]}, and generated by random key
R_{2}
using the used random algorithm above.
Finally, we perform IDCT to get encrypted polylines
E_{PLi}
, polygons
E_{PGi}
by equations (12) and (13).
for
i
∈[1,
N_{M}
].
 3.2 Selective decryption process
The decryption algorithm for these polylines and polygons shown by
Fig. 4
is the inverse process of selective encryption given at
Fig. 2
. Similar with the selective encryption process, we must also extract the protected data which consists of encrypted polylines and encrypted polygons, compute number of polylines and polygons, and find maximum number of vertices in polylines and polygons. The next step is to divide them into several groups by using Kmeans algorithm, similar with the encryption process, because the encryption changes the value of vertices only. Then, random coefficients and random values are generated again by random generator using random keys. Firstly, encrypted polylines and encrypted polygons are transformed using DCT and the DC coefficients are divided by random values. Secondly, they are inversed using IDCT to get randomized polylines and polygons again. Finally, we perform inverse randomization by dividing values of polylines/polygons in IDCT domain for random coefficients to have decrypted polylines and polygons.
Selective decryption algorithm for polyline/polygon.
4. EXPERIMENTAL RESULTS
We used 1:5000, 1:10000, and 1:100000 scalingmaps in our experiments. Firstly, we experimented with each polyline layer and polygon layer with the scale of 1:5000. Then, we tested the full layers of 1:10000 and 1:100000 scale. Experimental results with polyline layer, polygon layer and full maps show that all maps are changed as given by
Fig. 5
and
Fig. 6
. Unauthorized user cannot see anything on map because we changed polylines and polygons through four processes: randomization, DCT, multiplication, and IDCT using random keys
R
_{1}
,
R
_{2}
.
Experimental result with scaling layers 1:5000; (a) original polyline layer, (b) encrypted polyline layer, (c) original polygon layer, and (d) encrypted polygon layer.
Experimental result with full scaling map 1:10000, 1:100000; (a) original map 1:10000, (b) encrypted map 1:10000, (c) original map 1:100000, and (d) encrypted map 1:100000.
Our selective encryption scheme only changes values of vertices in polylines and polygons of the map. It did not alter the size of encrypted file. The result of loss accuracy is shown in
Table 1
. In addition, DCT and IDCT are not processes absolutely. That means, if we have an input sequence
x_{n}
, and we perform DCT to get
x_{k}
, and next we perform IDCT to get input sequence again
x′_{n}
, it shows that
x′_{n}
is not absolutely equal to
x_{n}
because the cosine value is not integer. However, in GIS vector map data, vertices are stored in double type such that the errors between original vertices and decrypted vertices values are approximately zero as given by
Table 2
.
The result of loss accuracy
The result of loss accuracy
The error between original coordinates and decrypted coordinates
The error between original coordinates and decrypted coordinates
Finally, the distance between maps
d_{M}
is computed by equation (14):
We used polyline map, polygon map to experiment other three times. Each time, we encrypted maps with different passwords which are used to create random keys as
figure 3
. Then we calculate
d_{M}
distances of each experimental time. In
Table 3
, experimental results show that dM distance of two maps which are encrypted by different passwords from an original map is depend on passwords.
Experimental distance measure
Experimental distance measure
5. CONCLUSION
Our paper focuses on the issues how to encrypt GIS vector map selectivity with low complexity. We classified objects and encrypted them by random algorithms in DCT domain. Only some values are selected to encrypt by random processes but it made changing whole map. Experimental results showed that the proposed algorithm has very effective with a large volume of GIS dataset. Decrypting results also show the error in decryption process approximates zero. Our algorithm can be applied to various file formats or standard vector map because only polyline and polygon objects are encrypted and can be used for map database security of GIS map service on/offlines. Furthermore, our algorithm can be applied to various vector contents such as CAD and 3D content fields. Next time, we will continue to improve our algorithm by reducing number of selective values to reduce complexity while not change effectively.
BIO
Giao Pham Ngoc
Giao Pham Ngoc received a B.S. degree in School of Electronic & Telecommunication from Hanoi University of Science & Technology (HUST) in 2011, and Master degree from Pukyong National University (PKNU) in 2014. Currently, he is an researcher in Multimedia Communication & Signal Processing Lab in PKNU. His research interests include video processing & application, GIS applications, data security, and smart system.
GiChang Kwon
GiChang Kwon received a B.S., a M.S., and Ph.D. degrees from Andong National University in 1985, Daegu Univsrsity in 1993, and Yeongnam University in 2000. Currently, he is a professor in Department of IT Cooperative System at Geongbuk Provincial College. His research interests include multimedia contents and image processing, digital contents and smart system.
SukHwan Lee
He received a B.S., a M.S., and a Ph. D. degrees in Electrical Engineering from Kyungpook National University, Korea in 1999, 2001, and 2004 respectively. He is currently an associate professor in Department of Information Security at Tongmyong University. His research interests include multimedia security, digital image processing, and computer graphics.
KiRyong Kwon
He received the B.S., M.S., and Ph.D. degrees in electronics engineering from Kyungpook National University in 1986, 1990, and 1994 respectively. He worked at Hyundai Motor Company from 19861988 and at Pusan University of Foreign Language from 19962006. He is currently a professor in Department of IT Convertgence and Application Engineering at the Pukyong National University. He has researched University of Minnesota in USA on 2000~2002 with PostDoc. and Colorado State University on 2011~2012 with visiting professor. He is currently the General Affair Vice President of Korea Multimedia Society. His research interests are in the area of digital image processing, multimedia security and watermarking, bioinformatics, weather radar information processing.
Foote K.E.
,
Lynch M.
2011
Geographic Information Systems as an Integrating Technology: Context, Concepts, and Definitions
Goodchild M.F.
2010
“Twenty Years of Progress: GIS Science in 2010,”
Journal of Spatial Information Science
(1)
3 
20
(2004)
Geographic Information System
http://en.wikipedia.org/wiki/Geographic_information_system
(2006)
GIS Vector Map
http://en.wikipedia.org/wiki/Vector_map
Massoudi A.
,
Lefebvre F.
,
De Vleeschouwer C.
,
Macq B.
,
Quisquater J.J.
2008
“Overview on Selective Encryption of Image and Video: Challenges and Perspectives,”
Hindawi Publishing Corporation EURASIP Journal on Information Security
Article ID:179290
2008
(5)
18 
Abomhara M.
2011
Enhancing Selective Encryption for H.264/AVC Using Advanced Encryption Standard
University of Malaya
Kuala Lumpur
Hasan M.Y.
,
Ahmed F.A.
,
Abdelhamid K.
2009
“Image Adaptive Selective Encryption of Vector Quantization Index Compression,”
Proceeding of IEEE International Conference on Image Processing
1277 
1280
Puech W.
,
Rodrigues J.M.
2005
“CryptoCompression of Medical Images By Selective Encryption of DCT,”
Proceeding of European Signal Processing Conference
Vol. 1
225 
228
Sharma S.
,
Pateriya P.
2012
“A Study on Different Approaches of Selective Encryption Technique,”
International Journal of Computer Science & Communication Networks
2
(6)
658 
662
Jang. B.J.
,
Moon. K.S.
,
Lee. S.H.
,
Kwon. K.R.
2011
“Effective Compression Technique for Secure Transmission and Storage of GIS Digital Map,”
Journal of Korea Multimedia Society
14
(2)
210 
218
DOI : 10.9717/kmms.2011.14.2.210
Nazneen M.G
,
Banu S.
,
Tabassum Z.
,
Fatima K.
,
Shariff A.
2013
“Selective Bitplane Encryption for Secure Transmission Of Image Data In Mobile Environment,”
International Journal of Scientific & Technology Research
2
(6)
92 
96
Queen Mac
1967
Some Methods for Classification and Analysis of Multivariate Observations
University of California Press
Berkeley, Calif.
Vol. 1
281 
297
Strang G.
1999
“The Discrete Cosine Transform,”
Society for Industrial and Applied Mathematics
41
(1)
135 
147