Journal of Computer and Communications, 2014, 2, 121-126
Published Online July 2014 in SciRes. http://www.scirp.org/journal/jcc
http://dx.doi.org/10.4236/jcc.2014.29016
How to cite this paper: Bezzateev, S. and Voloshina, N. (2014) The Digital Fingerprinting Method for Static Images Based on
Weighted Hamming Metric and on Weighted Container Model. Journal of Computer and Communications, 2, 121-126.
http://dx.doi.org/10.4236/jcc.2014.29016
The Digital Fingerprinting Method for Static
Images Based on Weighted Hamming Metric
and on Weighted Container Model
Sergey Bezzateev, Natalia Voloshina
Information Security Technologies Department, Saint-Petersburg State University of Aerospace
Instrumentation, Saint-Petersburg, Russia
Received May 2014
Abstract
The algorithm of fingerprint constructing for still images based on weighted image structure
model is proposed. The error correcting codes that are perfect in weighted Hamming metric are
used as a base for fingerprint constructing.
Keywords
Fingerprin ting, Error Correcting Codes, Perfect Codes in Weighted Hamming Metric, Weighted
Container Model, Digital Rights Management
1. Introduction
The author rights protection is one of the most important problems for the multimedia data distribution. Two
kinds of methods are used to solve this problem such as digital watermarking (DWM) and digital fingerprinting
(DFP) [1] [2]. In the DWM methods the additional information about author (watermark) is embedded into ini-
tial data (for example image) to protect it. This information should be resistant against wide class of attack (fil-
tering, compression, etc.) on the watermarked image as long as the level of visual quality is higher than prede-
fined level. The second type of protection means that the additional information (fingerprint) should be formed
based on the initial information (image) based on its specific salient features. For example in [3] the edges and
corners obtained from an image were used as salient features. The fingerprint is used then to find copies of origi-
nal image including illegal ones. Fingerprinting method should provide stable fingerprint forming process for
different kind of image processing (filtering, compression, etc.).
Main differences between these copy right protection methods are:
Some part of the initial object is changed while watermark embedding process (for example LSB method).
Fingerprinting does not imply any changes of initial information.
Digital watermark is constructed by the user (author). It can be represented in different forms (ID information,
picture, text, etc.) to prove author rights. Digital fingerprint does not contain any author information. It forms
based on initial information.

S. Bezzateev, N. Voloshina
122
The combination of these two types of author rights protection methods is proposed in this paper. The idea is
to add small distortions to the initial image to get stable fingerprint.
In this paper the term salient feature refers to a special vector b in weighted Hamming metric obtained from
the image and to “nearest” (L, G) code perfect in the weighted Hamming metric [4]. The “nearest” means a code
that have codeword a on the minimal distance in weighted Hamming metric from the vector b.
2. Proposed Method Description
The author rights protection systems are developed in a way they give stable information about the person that
has author rights on it. This information should be stable for wide class of distortions that could happen. At the
same time author rights protection method should not change the initial information more than it defined for ex-
act marking object. For example it should keep visual quality of the image.
Fingerprinting methods do not change initial objects. They only use salient features of these objects to con-
struct fingerprint. The problem is that not always such features could be found or they could be not resistant to
attacks. At the same time it is not necessary to avoid any distortions of initial information (for example for digi-
tal images). In this case it is possible to use watermarking approach that changes some part of initial information
to embed additional author information. But it is not always possible to embed watermark with acceptable dis-
tortion level due to inconsistency of watermark and protected object structure.
The method of digital fingerprint construction based on the property of codeword presence in image (F5 con-
cept [5]) is proposed. If the codeword can’t be found then codeword should be added by the watermarking ap-
proach.
For example for the still images the essence of the method can be explained as following. The initial image or
its part is transformed into bit stream. This bit stream is divided into blocks a with length n. These blocks a are
looked at as a code words of code G with error vector e. If a is a codeword of G then
0e=
and syndrome
0s=
. It means that this block has required for fingerprinting property. If
0s≠
then this block does not have
required property. It is necessary to decode this codeword i.e. to correct its errors to get this property. As a result
the distortions will be added to the initial information. The problem of getting
0s=
for any block of bit stream
could be solved by perfect codes usage [4].
It is possible to use several codes with equal parameters that are defined for weighted Hamming metric. For
this approach the code sequence
i
G
that is formed as a result of the blocks
i
a
decoding and for which the
blocks are the “closest” to their code words can be looked at as a fingerprint.
The structure of the blocks a should be weighted because the error corrected codes that are concerted with the
weighted Hamming metric are used to construct fingerprint. These weighted blocks could be looked at as a
weighted container that is formed for weighted watermarking [6] [7].
It is necessary to dived initial image into several zones to construct weighted blocks a. The division is per-
formed based on the influence of the errors that happened during the decoding process on the resulting distor-
tions (visual quality of resulting image). Blocks a are formed as a combination of the parts of these different
significance zones.
The basic scheme of the proposed fingerprinting method is shown in the Figure 1.
3. Error Correcting Codes Consistent with Weighted Hamming Metric
Error correcting codes in weighted Hamming metric are defined as following [4]:
Length n of a code word is
12 1
,,,,
l
li
i
nn nn n
=
=
∑

.
Any position of the code word
( )
12
111 22
12 11
l
ll
nn n
aaaa aaaa= 
have the weight
j
ω
. Let us consider
these weights as growing sequence i.e.
12 jl
ωω ωω < <<<
. The weight of the code word a in weighted
Hamming metric is defined as following:
0
() j
i
WHM j
a
wt a ω
≠
=∑
.
It is obvious that Hamming distance between two vectors in weighted Hamming metric can be defined as
( )
12
111 22
12 11
l
ll
nn n
aaaa aaaa= 
and
( )
12
111 22
12 11
l
ll
nn n
bbbb bbbb= 
:

S. Bezzateev, N. Voloshina
123
Figure 1. The basic scheme of the fingerprinting method for three zone container.
.
For binary codes in weighted Hamming metric it is possible to write the Hamming distance for code with pa-
rameters the same way as for codes in ordinary Hamming metric
where -number of a code words in the code (for binary linear code )
-number of vectors of length in a sphere of radius in weighted Hamming metric.
where .
Therefore we can define a perfect code, i.e. the code with parameters lies on this bound. For linear binary
code we obtain the following equation:
.
Codes that are perfect in a weighted Hamming metric can be constructed by using well-known methods for
optimal codes construction (for example Gilbert-Varshamov bound). But such construction method has high
calculation complexity and doesn’t give any design decoding method for such codes. By using special classes of
Goppa codes in weighted Hamming metric it is possible to solve both these problems.
Special Class of Goppa Codes in Weighted Hamming Metric
To construct Goppa codes consistent with a weighted Hamming metric the construction of generalization (L,G)
codes with position numerators of different degrees [4] is used. Therefore we use locator set
where is formal derivative of denominator , and

S. Bezzateev, N. Voloshina
124
is an irreducible polynomial on
2[]
m
Fx
. Goppa polynomial for such code is irreducible polynomial
() ()
[ ]
()
( )()
( )
2
,, deg,
gcd,1, : 1,
m
l
l
il
Gx GxFxGx
Gx uxiin
τω
∈=≥
=∀=
Number of different Goppa codes with the same parameters
(, ,)
WHM
nkd
from this class is determined by
the number of different irreducible polynomials with degree
τ
on
2[]
m
Fx
.
4. Fingerprint Calculation Algorithm Based on Family of Goppa Codes
ΓWHM(n,k,d) Perfect in Weighted Hamming Metric
We describe here the simplest version of the fingerprint calculations algorithm for static image that contains
different significance zones that is based on the family of Goppa codes perfect in the weighted Hamming metric.
Without loss of generality we consider here a static image that contains three zones.
• Third zone does not assume any distortions, i.e.
3
ω = ∞
.
• Second zone has relative weight
2
ω
of distortions equal to 2.
• First zone allows to make the maximum number of distortions without major consequences for the quality of
the resulting image and therefore has minimal relative weight
1
1 ω
=
.
For such image let us chose a family of Goppa codes perfect in weighted Hamming metric
(,, )
WHM nkd
Γ
with a following parameters:
21 1
12 1
21 1
2
21 1
221,2 ,
22 1,
222 ,5.
mm m
mm
mm WHM
nnn n
n
k md
−−
−−
−−
=+=+ − =
= −−
= +−=
As mentioned in the previous section the number of different codes in this family is determined by the num-
ber of irreducible polynomials of second degree with coefficients from
(2 )
m
GF
:
21 1
(2 )
(2) 22
m
mm
GF
I
−−
= −
.
Obviously as we consider perfect codes any vector
( )
12
111 22
12 1nn
aaaa aa=
that is obtained from image
that was preliminarily splitted into different significance zones can be represented in the weighted Hamming
metric as following:
() ()()
1 21212
11122111 22111 22
12112 1121
,
n nnnnn
ii
aaaaa ccccceeeee= ⊕ 
whe r e
( )
( )
( )
12
12
111 22
12 1
111 22
121
,,
2
n nii
i
WHMnn i
i
ccc ccLG
wte eeeet
∈Γ
= ≤


Thus using for vector a various
(, )
ii
LGΓ
codes of the family
(,, )
WHM nkdΓ
in decoding procedure we will
get error vectors with different weights
i
t
,
02
i
t≤≤
.
Fingerprint will consider as a set of numbers
12
,,,
R
λλ λ 
of a codes from the family
(,, )
WHM nkdΓ
cor-
responding to the vectors obtained from the image splitting into zones as follows:
Vector
12
11122
12 1
()
nn
aaaa aa=
assign the smallest number
λ
of such
(, )
ii
LGΓ
code for which error
vector
12
11122
12 1
()
n ni
eeee ee=
provides the least weight by decoding procedure.
That means
( )
( )
12
12
111 22
12 1
111 22
12 1
min :
min .
WHMnni
i
WHMnnj
j
iwte eeee
wte eeee
λ =
=


The algorithm of fingerprint calculation based on a family of
(, )
ii
LGΓ
codes can be described as:
1) The image is divided into zones of different significance.
2) In accordance with found image zones the blocks are formed and the appropriate parameters of the codes

S. Bezzateev, N. Voloshina
125
family are selected.
3) Fingerp r int
12
,,,
M
λλ λ 
is formed in following way. Found error vectors
12
11122
121
()
n ni
eeee ee=
are
corrected and corresponding blocks
12
11122
12 1
()
nn
aaaa aa=
of source image are converted to code words of
the Goppa codes from the family
(,, )
WHM nkdΓ
. For example the first block is transformed into a codeword
1 211
11122
12 1
()( ,).
nn
cccccLG
λλ
∈Γ 
The distortion of the source image will be minimal according to the pre-
viously described algorithm of obtaining the numbers
i
λ
.
5. The Fingerprint Checking and Its Resistance to Random and Deliberate
Distortions
In accordance with the described algorithm of fingerprint
12
,,,
R
λλ λ 
creation in the processed image P there
are R blocks
( ) ( )
12
111 22
12 1
,,
1,,.
ii
nn
i
ccc ccLG
iR
λλ
∈Γ
=


Each block should be the codeword of corresponding Goppa code from the family
(,, )
WHM nkdΓ
. The pre-
sence of the fingerprint
12
,,,
R
λλ λ 
is verified by the decoding the blocks a by the corresponding code. The
fingerprint is decided to be found if all syndromes for all blocks
0s=
.
The presence of minor distortion in the processed image P may cause errors in these blocks. So in distorted
image P* there are blocks
() ()()
()()
( )
( )
( )
12 12 12
12 12
12
12
12
111 22111 22111 22
12 112 112 1
111 22111 22
12 1121
111 22
12 1
11122
12 1
111 22
12 1
ˆ ˆˆˆˆˆ ˆˆˆˆ,
ˆ ˆˆˆˆ2,
,
ˆ ˆˆˆˆ
nn nnnn
iii
nn nn
ii
WHMn ni
i
nn
i
nn
i
bbb bbccccceeeee
ccc cceee ee
wte eeeewt
ccc cc
ccc cc
= ⊕
= ⊕
= ≤
∈Γ
 
 



( )
,,1,,.
ii
LG iR
λλ
=
Using fingerprint
12
,,,
R
λλ λ 
and corrupted image P* it is easy to find an appropriate error vector
12
11122
121
ˆ ˆˆˆ ˆ
()
n ni
eeeee 
and the weight
i
wt
corresponding to this vector. Obviously that in case of small corrup-
tions
12 12
11122111 22
12 112 1
ˆ ˆˆˆˆ
()()
n nin ni
cccccccc cc = 
and therefore
12 12
11 12211 122
121 121
ˆ ˆˆˆ ˆ
( )( )
n nin ni
eeee eeeee e=  
.
Let’s define now the penalty function
1
i
R
i wt
i
Fwt f
=
= ⋅
∑
. In the simplest case it is possible to consider that the
weight coefficients
{ }
12
,
i
wt
f ff∈
of the penalty function have the same value and are equal to 1. However the
more flexible way where
12
ff≠
is possible too. By taking into account the nature of the corruptions and their
impact on the perception of the resulting image i.e. its visual quality we can chose different values of the weight
coefficients.
Decision of the definite fingerprint availability in an existing picture P* is made by the value of the penalty
function F and threshold values B1 and B2 that are define the events of the “false alarm” and “skip goal” respec-
tivel y.
6. Conclusion
A new method of fingerprint construction that uses the features of the original image structure (weighted con-
tainer) associated with the different degree of its sensitivity to the corruptions in different zones of the container
is proposed. In order to use this property of the container it is proposed to use the weighted Hamming metric un-
like used in previously known schemes usual Hamming metric. For effective use of this metric it is proposed a
family of generalized Goppa codes perfect in weighted Hamming metric. Thanks to the usage of such family of
codes it is possible to make the minimum number of distortions when fingerprint is constructed. Additionally the
use of error-correcting codes construction allows to correct random corruptions that can occurred during con-
tainer (image) storing or transmitting. Still open question in optimal choice of the coefficients in the penalty

S. Bezzateev, N. Voloshina
126
function provides the minimal probability of “false alarm” and “skip goals” when deciding on the availability of
the fingerprint presence in the analyzed image.
References
[1] Duric, Z., Johnson, N.F. and Jajodia, S. (1999 ) Recovering Watermarks from Images. Technical Report ISE-TR -99-04,
Center for Secure Information Systems, George Mason University.
[2] Johnson, N.F., Duric, Z. and Jajodia, S. (1999) A Role for Digital Watermarking in Electronic Commerce. Accepted
for Publication ACM Computing Surveys. Publication TBA.
[3] Johnson, N.F., Duric, Z. and Jajodia, S. (19 99) On Fingerprinting Images for Recognition. In: Multimedia Information
Systems, 4-11.
[4] Bezzateev S. and Shekhunova N. (2012) Binary Generalized ( L, G) Codes That Are Perfect in a Weighted Hamming
Metric. Problems of Information Transmission, 48, 239-242. http://dx.doi.org/10.1134/S0032946012030039
[5] Westfeld, A. (2001) High Capacity Despite Better Steganalysis (F5-A Steganographic Algorithm). In: Moskowitz, I.S.,
Eds., Information Hiding. 4th International Workshop. Lecture Notes Computer Science, Vol. 2137, Springer-Verlag,
Berlin, Heid elberg, New York.
[6] Bezzate ev, S., Voloshina, N. and Zhidanov, K. (2012 ) Special Class of Error-Correcting Codes for Steganography
Systems . P roceed ing s TUSUR (Novosib irsk), 1, 112-118.
[7] Neeta, D. (2006) Implementation of LSB Steganography and Its Evaluation for Various Bits. Digital Information
Management, 1st International Conference.