The Digital Fingerprinting Method for Static Images Based on Weighted Hamming Metric and on Weighted Container Model

doi:10.4236/jcc.2014.29016

Paper Menu >>

Journal Menu >>

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

Email: [email protected], [email protected]

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

that is formed as a result of the blocks

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

,,,,

nn nn n

∑



Any position of the code word

( )

111 22

12 11

nn n

aaaa aaaa= 

have the weight

. 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:

() j

WHM j

wt a

≠

=∑

It is obvious that Hamming distance between two vectors in weighted Hamming metric can be defined as

( )

111 22

12 11

nn n

aaaa aaaa= 

and

( )

111 22

12 11

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[]

. Goppa polynomial for such code is irreducible polynomial

() ()

[ ]

()

( )()

( )

,, deg,

gcd,1, : 1,

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

2[]

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.

= ∞

• Second zone has relative weight

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

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

221,2 ,

22 1,

222 ,5.

mm m

mm WHM

nnn 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 )

21 1

(2 )

(2) 22

−−

= −

Obviously as we consider perfect codes any vector

( )

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

aaaaa ccccceeeee= ⊕ 

whe r e

( )

111 22

12 1

111 22

121

n nii

WHMnn i

ccc ccLG

wte eeeet

∈Γ

= ≤



Thus using for vector a various

(, )

LGΓ

codes of the family

(,, )

WHM nkdΓ

in decoding procedure we will

get error vectors with different weights

t≤≤

Fingerprint will consider as a set of numbers

,,,

λλ λ



of a codes from the family

(,, )

WHM nkdΓ

cor-

responding to the vectors obtained from the image splitting into zones as follows:

Vector

11122

12 1

()

aaaa aa=

assign the smallest number

of such

(, )

LGΓ

code for which error

vector

11122

12 1

()

n ni

eeee ee=

provides the least weight by decoding procedure.

That means

( )

111 22

12 1

111 22

12 1

min :

min .

WHMnni

WHMnnj

iwte eeee

wte eeee



The algorithm of fingerprint calculation based on a family of

(, )

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

,,,

λλ λ



is formed in following way. Found error vectors

11122

121

()

n ni

eeee ee=

are

corrected and corresponding blocks

11122

12 1

()

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

()( ,).

cccccLG

λλ

∈Γ



The distortion of the source image will be minimal according to the pre-

viously described algorithm of obtaining the numbers

5. The Fingerprint Checking and Its Resistance to Random and Deliberate

Distortions

In accordance with the described algorithm of fingerprint

,,,

λλ λ



creation in the processed image P there

are R blocks

( )

111 22

12 1

1,,.

ccc ccLG

λλ

∈Γ





Each block should be the codeword of corresponding Goppa code from the family

(,, )

WHM nkdΓ

. The pre-

sence of the fingerprint

,,,

λλ λ



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

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

WHMn ni

bbb bbccccceeeee

ccc cceee ee

wte eeeewt

ccc cc

= ⊕

= ≤

∈Γ

 

 



( )

,,1,,.

LG iR

λλ

=

Using fingerprint

,,,

λλ λ



and corrupted image P* it is easy to find an appropriate error vector

11122

121

ˆ ˆˆˆ ˆ

()

n ni

eeeee



and the weight

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

i wt

Fwt f

= ⋅

∑

. In the simplest case it is possible to consider that the

weight coefficients

{ }

f ff∈

of the penalty function have the same value and are equal to 1. However the

more flexible way where

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.