Cryptography Reference
In-Depth Information
The cover data D
o
is divided into two subsets D
A
and D
B
by following
steps:
1) Divide the original map M
o
into patches of uniform size, using a superim-
posed rectangular grid cover.
2) Based on a key k, generate a pseudo-random bit sequence whose length is
equal to the number of the map patches. Every one bit is assigned to one
patch as its flag. The key k can be used as the secret key for watermark
detecting.
3) For each i∈1, 2,,n, check the bit flag of the patch where o
i
is
situated, and then assign D
i
to the subset D
A
or D
B
according to the flag
value 0 or 1. For a certain map, two subsets D
A
and D
B
always have
similar distributions.
Secondly, to embed a bit 0, just leave D
A
and D
B
unchanged. To embed
a bit 1, leave D
A
unchanged and multiply D
B
with a factor α (0 <α<1)
as D
′
B
α. The goal of the procedure is to introduce enough difference
between the distributions of D
A
and D
′
= D
B
B
, which can then be regarded as a
feature to represent a watermark bit.
Finally, combine the subsets D
A
and D
′
B
into a watermarked distance
sequence D
W
. It is used to calculate the new positions of the map vertices
and get the watermarked map M
W
.
Let τ denote the precision tolerance of M
o
. The location-distortions in-
duced by embedding must below τ to maintain the fidelity of the map M
W
.
To meet the condition, T
DP
(1−α)≤τ , where T
DP
is the threshold used for
feature point detection. Thus T
DP
can be determined as T
DP
= τ/(1−α).
Watermark Detecting
Given the possibly tampered map
M
W
, the data set
D
o
is extracted from it
and divided into
D
B
. Here same parameters are used such as T
DP
and
secret key k. The distribution functions of
D
A
and
D
B
are then calculated,
and denoted as f
a
(k)andf
b
(k). The similarity between f
a
(k)andf
b
(k)canbe
used for watermark detecting. The Euclidean distance is used as the measure
to evaluate the similarity between two distributions:
D
A
and
dis(f
a
,f
b
)=
(f
a
(k)−f
b
(k))
2
.
k
Note that lower dis(f
a
,f
b
) means higher degree of similarity between f
a
(k)and
f
b
(k). Taking dis(f
a
,f
b
) as the similarity measure, the detecting procedure is
a judgement based on a threshold T . The map is not marked if dis(f
a
,f
b
) <
T .Ifdis(f
a
,f
b
)≥T , the map should have been watermarked because the
embedding procedure could degrade the similarity between f
a
(k)andf
b
(k).