TELKOM
NIKA
, Vol.12, No
.4, Dece
mbe
r
2014, pp. 11
23~113
1
ISSN: 1693-6
930,
accredited
A
by DIKTI, De
cree No: 58/DIK
T
I/Kep/2013
DOI
:
10.12928/TELKOMNIKA.v12i4.1009
1123
Re
cei
v
ed Au
gust 18, 20
14
; Revi
sed O
c
t
ober 2
9
, 201
4; Acce
pted
No
vem
ber 1
9
,
2014
Image T
a
mper Detection and Recovery by Intersecting
Signatures
Chun
-Hung Chen
1
, Yuan
-Liang Ta
ng*
2
, Wen-Sh
y
o
ng Hsieh
3
, M
i
n-Shiang Hw
a
n
g
4
1,3
Department of Computer S
c
ienc
e an
d En
gin
eeri
ng, Nati
ona
l Sun Yat-s
en Un
iversit
y
,
Taiwa
n
2
Department o
f
Information Mana
geme
n
t, Chao
ya
n
g
Univ
e
r
sit
y
of T
e
chnol
og
y,
Taiwa
n
3
Department o
f
Computer an
d Commu
nicati
on, Shu-T
e
Uni
v
ersit
y
,
Taiwa
n
4
Department o
f
Computer Sci
ence a
nd Info
r
m
ation En
gi
ne
erin
g, Asia Uni
v
ersit
y
,
Taiwa
n
*Corres
p
o
ndi
n
g
author, e-ma
i
l
:
y
l
ta
ng@c
y
ut.
edu.t
w
A
b
st
r
a
ct
In this pa
per, w
e
pro
pose
an e
x
act imag
e aut
hentic
at
io
n sch
eme that ca
n, in the b
e
st case
, detect
image tamper
ing with the acc
u
racy of
one pixel. This method
is based
on constructing blocks in the image
in s
u
ch
a
man
ner th
at they
i
n
tersect w
i
th
o
ne
an
other
in
different directi
ons.
Suc
h
a
t
e
chn
i
qu
e is
ve
ry
useful
to i
d
e
n
tify w
hether
an
ind
i
vi
dua
l i
m
a
ge
pixe
l h
a
s b
een
ta
mper
ed
w
i
th. Moreov
er, the ta
mper
e
d
regi
on can
be
w
e
ll recover
ed
w
i
th the emb
e
d
ded rec
o
ver d
a
t
a.
Ke
y
w
ords
: inf
o
rmation security
, digital w
a
te
rmark
i
ng, i
m
a
g
e
authe
nticati
o
n, digita
l sig
nat
ures
1. Introduc
tion
As digital technolo
g
ies a
d
v
ance, mo
re and more pu
blicatio
ns a
r
e
produ
ce
d in digital
formats an
d tran
smitted via the Internet
. A
ccomp
anying su
ch adva
n
ce, ho
weve
r, unauthori
z
e
d
use, ill
egal
copyin
g, an
d
mali
ciou
s
modificati
o
n
of
digital produ
cts have
be
com
e
se
riou
s
probl
em
s. Re
sea
r
che
r
s t
h
u
s
try to fin
d
variou
s
wa
y
s
t
o
protect
digit
a
l produ
cts;
solution
s in
clu
de
copyri
ght a
ssertion,
conte
n
t
authent
i
c
ati
on, etc. In
th
e area
of im
a
ge
conte
n
t au
thenticatio
n, the
integrity of a
n
imag
e i
s
regarded
very
impo
rt
ant a
nd mu
st the
r
efore
be
real
ized. A
co
m
m
on
approa
ch i
s
the u
s
e
of d
i
gital waterm
arki
ng te
ch
ni
que
s. Di
gital
wate
rma
r
ki
n
g
serve
s
m
a
ny
purp
o
ses, for
example, pro
o
f of ownersh
ip, cont
ent au
thenticatio
n, copy
control,
and so on.
Re
sea
r
che
r
s
have devel
op
ed vari
ou
s i
m
age
authe
n
t
ication te
chn
i
que
s to d
e
te
ct if an
image
ha
s
e
x
perien
c
e
d
u
nautho
rized
modificatio
n
.
Some of
the
m
can
only d
e
tect
wheth
e
r the
image a
s
a
whol
e ha
s b
een alte
red.
Others may
have the a
d
d
i
tional capabi
lity to detect if a
certai
n p
a
rt
of the imag
e
has bee
n ta
mpered
with. Liu
et al.
[1]
studie
d
the
Zenike mo
m
ent
values
whi
c
h
are g
ene
rate
d from lo
w DWT subb
and
s. They found
that the qua
ntized valu
es are
robu
st to
co
mmon p
r
o
c
e
ssi
ng o
perations
but fra
g
i
l
e to mali
cio
u
s atta
cks.
Therefore, th
ey
embed
ded th
e wate
rma
r
k by quanti
z
in
g the Ze
rni
k
e mome
nt value
s
, and th
e location
s (i
.e.,
blocks) suffe
red
f
r
om ma
liciou
s
attacks can
be
id
entified throu
gh exami
n
in
g the
extract
ed
values.
Thei
r metho
d
h
a
s mod
e
rate
robu
stne
ss
a
gain
s
t JPEG
co
mpressio
n. In Rawat
and
Rama
n’s sch
e
me [2], two
ch
aotic
ma
ps
are
u
s
ed
in o
r
de
r to
enha
nce the
se
cu
rity of the
watermarke
d
image
s. Th
e
pixels i
n
the
i
m
age
ar
e di
sturbed
u
s
ing
the first chaot
ic m
ap
and
a
r
e
further
sepa
rated into bit
plane
s with the least si
gni
ficant bit use
d
for waterm
ark em
bed
din
g
. A
binary wate
rmark
i
s
scra
mbled by
the
se
con
d
cha
o
tic
m
ap.
Th
e watermarke
d image
s can
a
v
oid
cou
n
terfeiting
attacks. Xi’an [3] scram
bl
ed a bi-l
evel
watermark by
the Arnold transfo
rm, and
the
Huma
n Vi
sua
l
System i
s
u
s
ed
to d
e
termine the
qu
a
n
tization
ste
p
.
The
scra
mb
led
watermark i
s
then in
se
rted
into th
e lo
w
DWT
coeffici
ents. T
a
mpe
r
area
s
can
th
en b
e
l
o
cali
zed by
compa
r
in
g
the extracted
and the orig
inal wate
rma
r
ks. Patra
et al.
[4] convert the imag
es into the DCT
domain
and q
uantize the lo
w-frequ
en
cy
coeffici
ents a
c
cordi
ng to th
e target level
s
dete
r
mine
d
by
the Chi
n
e
s
e
Remai
nde
r T
heorem. Th
e
i
r metho
d
i
s
com
putation
a
lly efficient
and i
s
abl
e
to
withsta
nd su
ch
atta
cks as
JPEG com
p
re
ssio
n, sharpenin
g
, and
brighte
n
ing.
Qi
et al.
[5] us
ed
tw
o
co
n
t
e
n
t
-b
a
s
e
d
w
a
te
rma
r
k
s
to
p
r
ote
c
t th
e
ima
g
e
s
. O
n
e
o
f
th
e
m
is
g
e
n
e
r
a
t
e
d
b
y
a
n
edge
detecto
r fo
r
the pu
rpo
s
e
of dete
c
ting
tiny ch
a
nge
s, an
d the
other i
s
g
e
n
e
rated
from
the
relation
shi
p
b
e
twee
n the
w
a
v
e
let
c
oef
f
i
ci
ent
s f
o
r lo
cali
zing
tampered regions
.
Both watermarks
are
emb
edd
ed into
mid
d
le-
and
hig
h
-fre
que
nc
y DWT coeffici
ents.
Fi
nally,
the
g
ene
rat
e
d
watermarks a
nd extra
c
ted
watermarks a
r
e comp
a
r
e
d
to authenticate the image,
and a mali
cio
u
s
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 12, No. 4, Dece
mb
er 201
4: 112
3 – 1131
1124
attack i
s
ide
n
t
ified if error
pixels a
r
e cl
u
s
tere
d togeth
e
r. Thei
r met
hod is
rob
u
st
again
s
t seve
ral
image p
r
o
c
e
ssi
ng op
erati
ons, in
cludi
n
g
JPEG co
m
p
re
ssi
on. In Wu’
s
wo
rk [6], the image is
divided into
b
l
ocks,
and
all
ha
she
s
deri
v
ed from
the
MSBs of
ea
ch
blo
c
k are
further en
co
d
ed
usin
g an erro
r co
rre
cting
code (E
CC
). The paritie
s, rather than th
e cod
e
word
s,
of the ECC are
sep
a
rate
d an
d embe
dde
d
into the LS
Bs of ea
ch
block. Durin
g
authenti
c
ation, the ori
g
i
nal
hashe
s
can
b
e
recovere
d if
the n
u
mb
er
of tampe
r
ed
blocks i
s
le
ss than
a th
re
sh
old. Th
e h
a
sh
of
a block is p
r
o
duced an
d co
mpared with t
he origi
nal
to identity if the
block is tamp
ered
with. Thi
s
method ha
s fine gra
nula
r
ity on detectin
g
tampered re
g
i
ons.
Although
ma
ny tech
niqu
e
s
h
a
ve
been
prop
osed
for
image
auth
e
n
t
ication, m
o
st
of them
can
only
det
ect if
an i
m
a
ge o
r
pa
rt of
it, as a
w
hol
e, is modifie
d
;
very few
ca
n ide
n
tify ima
g
e
tampers down to the granularity
of one-pixel level. In some a
ppli
c
ations, such ability could be
extremely essential. Fo
r e
x
ample, if an image is u
s
e
d
as a critical
piece of evid
ence in the court
or in a poli
c
e
investigation
,
a generali
z
e
d
answe
r as
to whethe
r the entire ima
g
e
or pa
rt of it is
altered to so
me deg
ree m
a
y not be accepta
b
le by
the law. To b
e
exact, it may be manda
tory
that the imag
e sh
ould n
o
t allow fo
r eve
n
tiny modi
fication ever
sin
c
e it wa
s ta
ken. Our
previ
ous
work [7] is a
b
le to achiev
e su
ch exa
c
t
authent
ication. In this p
aper,
we furt
her p
r
op
ose
an
authenti
c
atio
n schem
e that is able n
o
t only to
detect and l
o
cate ima
ge tampe
r
s
with
the
accuracy
of o
ne pixel at th
e be
st case, but also to
re
cover the ta
mpered d
a
ta. This i
s
done
by
first con
s
tru
c
ting line
a
r
blo
c
ks in
the im
age in
su
ch
a
way that the
y
intersect
with one
anoth
e
r
in
different dire
ction
s
. Seco
nd, a sign
ature i
s
creat
ed for ea
ch
block for the purpo
se
of
authenti
c
atio
n. Third, the
sign
at
ure
is
embed
ded
b
a
ck into t
he i
m
age i
n
o
r
de
r to p
r
ote
c
t e
a
ch
pixel by the four signatu
r
es a
nd any
tam
pered p
i
xel can be pinpoi
nted b
y
examining
its
corre
s
p
ondin
g
sig
natures.
And finally, the
qua
ntized
DCT coe
fficients
a
r
e gene
rated a
n
d
embed
ded fo
r the purpo
se
of recove
rin
g
the tamper
regio
n
s. Th
e rest of the pa
per is o
r
g
ani
zed
as follo
ws. The propo
se
d
techni
que i
s
descri
bed i
n
Section 2, fol
l
owe
d
by exp
e
rime
ntal re
sults
in Sectio
n 3.
Section
4
prese
n
ts
a security anal
y
s
is. A com
pari
s
on of d
e
tecti
on g
r
an
ularit
y is
sho
w
n in Se
ction 5. Finally, Section 6 gives so
me co
nclu
ding rem
a
rks.
2. Proposed
Techniqu
e
2.1. Cons
tru
c
ting th
e
Au
thentic
a
tion,
Signature, a
nd Rec
o
v
e
r
y
Blocks
Without loss
of generality, we assume
that
8-bit gra
y
scal
e
image
s are de
alt with. For
other formats, the same te
chni
que a
ppli
e
s, too. The i
m
age i
s
first
divided into e
qual-si
z
ed
B
B
blocks, which
are referred
to a
s
the
a
u
thentication
blo
c
ks
. An
d
then, in
ea
ch auth
entication
block, fou
r
se
ts of
pixels are colle
cted
i
n
four directio
n
s
: ho
ri
zontal,
vertical,
45
and 45
wr
ap-
arou
nd dia
g
o
nals. The
s
e
sets of linear b
l
ocks a
r
e refe
rre
d to as
si
g
nature bl
ocks
. Namely,
H
i
= {
p
ij
|
j
= 0
,
…,
B
1}: horizo
n
tal blo
c
ks,
i
= 0, …,
B
1,
V
j
= {
p
ij
|
i
= 0, …,
B
1}: vertical blo
c
ks,
j
= 0, …,
B
1,
X
m
= {
p
ij
|
i
=
0, …,
B
1,
j
= (
m
+
i
)
m
od B
}: –45
blo
c
ks,
m
= 0, …,
B
1, and
Y
n
= {
p
ij
|
i
= (
B
+
n
j
)
mo
d
B
,
j
= 0, …,
B
1}: 45
block
s
,
n
= 0, …,
B
1,
whe
r
e
p
ij
den
otes the ima
ge pixel and
mo
d
is the modulo op
eration.
Figure 1 depi
cts such a
c
o
ns
tr
uc
tio
n
.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Im
age Tam
p
er Dete
ction
and Recovery by
Inte
rsect
i
ng Signatu
r
e
s
(Chun
-Hun
g Che
n
)
1125
45
wrap
-a
rou
n
d
d
i
ag
on
al
s
i
gna
tur
e
blo
c
k
s
A
u
thenti
ca
ti
o
n
bl
o
c
k
(
B
B
):
V
e
r
t
i
c
a
l
s
i
gna
tu
re
b
l
oc
ks
45
w
r
a
p
-
a
r
oun
d
dia
g
o
n
a
l
s
i
gna
tur
e
bl
ock
s
.
. .
.
.
.
Horizon
t
al
s
i
gna
tur
e
blo
c
k
s
H
0
H
1
V
0
V
1
X
0
Y
0
Figure 1. The
authenticatio
n
block an
d si
gnature blo
c
ks
After establi
s
hing the
sig
n
a
ture bl
ocks, a si
g
nature is cre
a
ted fo
r
each such bl
ock an
d
then embe
dd
ed into the image. If the
DES system
i
s
used for si
g
nature g
ene
ration, 64 bits
are
requi
re
d for
both the in
pu
t and outp
u
t data. The
col
l
ection
of the
first 6 bits
of each pixel i
n
a
sign
ature
blo
c
k
is ha
she
d
first
by su
ch
f
unctio
n
s as MD5 or
S
H
A to
pro
d
u
c
e
a
64-bit data.
A
n
d
then thi
s
d
a
ta
is
en
crypted
usin
g the
DE
S system
to
prod
uce a
64
-bit
signatu
r
e,
whi
c
h
is final
ly
embed
ded
b
a
ck into th
e
least-sig
n
ifica
n
t bits
(LSBs) for th
e pu
rpose of aut
h
enticatio
n. T
h
e
above proced
ure is
rep
eate
d
on all sig
n
a
t
ure blo
c
ks.
By dividing
a
n
auth
entication bl
ock into
R
R
block
s
,
totally (
B
R
)
2
re
co
ve
ry
blo
c
k
s
are
prod
uced. Ea
ch
re
cove
ry
block i
s
re
si
zed into
8
8
p
i
xels, follo
we
d by th
e
DCT op
eratio
n.
The
resulting DCT coefficie
n
ts are then qu
antize
d
acco
rding to the
JPEG qua
ntization tabl
e [8].
Furthe
rmo
r
e,
the quantize
d
DCT
coeffi
cient
s ar
e
scanne
d in the zig-za
g ord
e
r and the first 10
coeffici
ents are recorded using
codes of
different
lengths. The encodi
ng pattern is illust
rated in
Figure 2. F
o
r example, th
e first
and
se
con
d
q
uanti
z
ed coeffici
ent
s
a
r
e re
pre
s
ented with ei
ght
and five bit
s
, re
spe
c
tively. As a
re
sult,
totally
40 bits are
gen
erated for a
reco
very blo
ck, a
n
d
su
ch coding l
ength
s
are e
noug
h for prese
r
ving
the
quality of the image blo
ck.
The gene
rat
ed
data of a
re
covery blo
c
k
are
embe
dde
d into the
LS
Bs of an
othe
r re
cove
ry bl
ock in
ord
e
r
for
better ch
an
ces of data recove
ry. We
denote the
index of a recove
ry block and that o
f
its
corre
s
p
ondin
g
embe
ddin
g
block a
s
a
ij
and
a
oj
(
o
=
(
i
+
s
)
mo
d
(B
R
)), respectively. That is
, a
vertical di
stan
ce bet
wee
n
the two blo
c
ks is pre
s
e
r
ved.
8
5
43
00
0
0
5
4
30
00
0
0
4
2
00
00
0
0
2
0
00
00
0
0
0
0
00
00
0
0
0
0
00
00
0
0
0
0
00
00
0
0
0
0
00
00
0
0
Figure 2. The
enco
d
ing p
a
ttern
Since the
r
e a
r
e 4
B
sign
atu
r
e and (
B
R
)
2
recove
ry blo
c
ks, we
can d
e
termin
e the sizes of
the auth
enti
c
ation
an
d t
he recovery
blo
c
ks, respectively, after the
em
b
eddin
g
spa
c
e is
determi
ned.
If the last two bit
s
of e
a
ch
pi
xel are used fo
r
embed
ding, t
he si
ze
s of
the
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 12, No. 4, Dece
mb
er 201
4: 112
3 – 1131
1126
authenti
c
atio
n and the re
covery bl
ocks are 160
160 (i.e.,
B
= 160) a
nd 10
10 (i.e.,
R
=
10),
r
e
spec
tively.
Whe
n
perfo
rming authe
ntication, the
con
s
tr
u
c
tion
of the authe
ntication blo
c
ks an
d
sign
ature
blo
c
ks a
r
e
re
pe
ated a
s
b
e
fore, followe
d b
y
the sam
e
DES en
crypti
on p
r
o
c
e
ss.
No
w,
the results
can be m
a
tche
d again
s
t
those extr
a
c
ted from th
e LSBs in the image. T
h
e
mismat
ched blocks will be recorded in
the followi
ng four sets, respectively:
E
H
= {
H
i
|
i
=
i
0
,
i
1
, …,
i
h
1
}: hori
z
ontal
bl
o
c
ks,
E
V
= {
V
j
|
j
=
j
0
,
j
1
, …,
j
v
1
}: ver
t
ic
al
blocks
,
E
X
= {
X
m
|
m
=
m
0
,
m
1
, …,
m
x
1
}: –45
blocks, an
d
E
Y
= {
Y
n
|
n
=
n
0
,
n
1
, …,
n
y
1
}: 45
blo
c
ks,
whe
r
e
h
,
v
,
x
, and
y
are the re
spe
c
tive
numbers of mismat
che
d
blocks. The basi
c
idea of
the
algorith
m
i
s
t
hat si
nce e
a
c
h
pixel i
s
p
r
otecte
d
by four sig
natu
r
e
s
a
nd th
e
si
gnature bl
ocks
intersect with
one anoth
e
r,
if a specific
pixel is
indee
d tampered
with, mismat
ches
will occu
r in
all of its fou
r
corre
s
p
ondin
g
sig
natu
r
es.
On the
cont
ra
ry, if some
of t
he co
rrespon
ding
sign
ature
s
are m
a
tch
ed,
it can be
concl
ude
d tha
t
the pixel has n
o
t been
altered. Fi
g. 3 illustrates t
he
algorith
m
of tampe
r
dete
c
tion in an
auth
enticatio
n blo
ck. Ea
ch pixe
l,
p
ij
(0
≤
i
,
j
≤
B
–1), in a bl
o
c
k
is
che
c
ked t
o
see if it i
s
tampe
r
ed
with. This i
s
d
one by
exa
m
ining it
s
co
rre
sp
ondi
ng f
our
sign
ature
s
, i.e., horizontal,
vertical, and
two di
ag
onal
ones. If all four
sign
ature
s
mismatch, the
pixel will be reporte
d as b
e
en tampe
r
ed
with.
Figure 3. The
algorithm of tampe
r
dete
c
tion
If a mismatch is d
e
tecte
d
,
the re
covery is perfo
rm
ed u
s
ing
a referen
c
e i
m
a
ge. The
con
s
tru
c
tion
of the refere
nce
imag
e
starts
by
extra
c
ting th
e recovery data
from ea
ch
re
covery
data. If all
o
f
pixels
of a
re
cove
ry bl
ock
a
r
e
auth
entic, the
e
m
bedd
ed
re
covery d
a
ta a
r
e
c
o
ns
ide
r
ed
as
valid
.
If the
data extracte
d from
the
co
rre
sp
ondi
ng
block
are inv
a
lid, the
re
co
very
block will be
con
s
tru
c
ted
with
its
valid
data
u
s
in
g
d
e
-
qua
ntizatio
n and
i
n
verse
DCT,
follo
we
d
by
scaling b
a
ck
the blo
ck
size from 8
8 t
o
R
R
. The
referen
c
e im
age i
s
obtain
ed after all
of the
blocks a
r
e
p
r
odu
ce
d, an
d
the
re
covery is d
one
by
re
pla
c
ing
th
e tamp
ere
d
pixels
with t
he
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Im
age Tam
p
er Dete
ction
and Recovery by
Inte
rsect
i
ng Signatu
r
e
s
(Chun
-Hun
g Che
n
)
1127
corre
s
p
ondin
g
pixels of the referen
c
e image if t
he correspon
ding
pixels are
co
nstru
c
ted by
the
valid data.
2.2. Analy
s
is
One of the m
a
in short
c
omi
ngs
of most
other
tam
per detectio
n
te
chni
que
s i
s
that they
usu
a
lly creat
e a
sig
nature
for an
ima
ge
block, a
nd
if
a mismatch o
c
curs, the
blo
c
k a
s
a
whole
i
s
identified a
s
being tam
p
e
r
ed with. Th
ere is n
o
way o
f
distingui
shin
g whi
c
h pixel
(or
pixels) is t
h
e
victim. The e
s
sen
c
e of th
e
pro
p
o
s
ed
scheme lie
s
on
t
he fact that
each pixel i
s
prote
c
ted
by four
intersectin
g
sign
ature
blo
c
ks. When
ever on
e pi
xel
is tampe
r
e
d
with, it causes th
e four
corre
s
p
ondin
g
sig
natures to mismat
ch
and, th
roug
h the inte
rse
c
ting
st
ru
cture, the tampe
r
e
d
pixel ca
n be
easily pi
npoi
n
t
ed. In other
words, if le
ss
than fou
r
mismatche
s
occur for a pixel,
we
can elimi
nate
the possibili
ty of tampering. This
met
hod is thu
s
very accurate in identifying
tampered pix
e
ls
as
well
a
s
their l
o
cation
s in
th
e ima
g
e
. The
r
e a
r
e,
however,
so
me conditio
n
s
in
whi
c
h thi
s
scheme
will make fal
s
e positi
ve reports.
Fi
gure 4 illustrates such a
sit
uation, in
whi
c
h
the black pix
e
ls represent
thos
e pixel
s
that have been altered b
y
attacke
rs.
The four
set
s
o
f
mismat
che
d
blocks are:
E
H
= {
H
i
1
,
H
i
2
,
H
i
3
},
E
V
= {
V
j
1
,
V
j
2
,
V
j
3
},
E
X
= {
X
m
1
,
X
m
2
,
X
m
3
}, and
E
Y
=
{
Y
n
1
,
Y
n
2
,
Y
n
3
}
.
It is obviou
s
that, besi
d
e
s
the four bla
c
k pixel
s
, the
system will
erroneo
usly
rep
o
rt
the cente
r
pixel (re
pre
s
e
n
ted by a white
pixel)
as a ta
mpered on
e, i.e., a false positive.
Actually,
the numbe
r of
ta
mpered pixel
s
(or
the si
ze of
the
tam
pered regio
n
)
de
termine
s
the num
ber o
f
mismat
ch
si
gnatures. If t
he form
er i
n
crea
se
s, the l
a
tter in
cre
a
ses, too. T
here is
no
con
s
traint
on the
maxim
u
m
size of
a t
a
mpe
r
ed
regi
on; ho
weve
r,
the shap
e
of the
regi
on
doe
s
affect the number of fal
s
e
positiv
es in the detection.
F
i
gure 5 illust
rates
an exam
ple, in whi
c
h t
h
e
black pixel
s
repre
s
e
n
t the
tampered pix
e
ls. As
ou
r al
gorithm i
denti
f
ies tamp
ere
d
pixels
by fo
ur
intersectin
g
signatures, th
e set of re
po
rted pixels
will
form a conv
ex shap
e (th
e
red p
o
lygo
n in
the figure
)
. As all pixels in
the convex
sha
pe a
r
e re
ported
as ta
mpered with,
the unch
ang
ed
pixels (white
pixels)
are fal
s
e po
sitives.
The si
tu
ation
gets worse if
the tampere
d
pixels
spre
ad
rand
omly a
c
ross the ima
g
e
. The result of a simul
a
tio
n
is
sho
w
n Fi
gure
6, in whi
c
h the tam
p
e
r
ed
pixels a
r
e ge
nerate
d
ra
nd
omly across t
he authe
ntica
t
ion block (1
60
1
6
0
)
. It can be
see
n
that
the numb
e
r
of false p
o
sit
i
ves in
cre
a
se
s rapidly a
s
the num
be
r o
f
tampere
d
p
i
xels in
cre
a
ses,
almost rea
c
hi
ng 16,00
0 wh
en the latter is only a few hund
red
s
. Su
ch a phe
nom
enon verifie
s
the
above a
nalysi
s
that a
s
the
repo
rted
pixel
s
form
a
conv
ex sha
pe, if the lo
cation
s
of the tampe
r
ed
pixels are randomly
gene
rated, the
convex
area will becom
e
very
l
a
rge,
which
result
s in a great
numbe
r of false po
sitives.
Den
o
ting the
numbe
rs of
reporte
d, tampere
d
, and fal
s
e po
sitive pi
xels
as
R
,
T
, and
F
, resp
ectivel
y
, the following relation
shi
p
holds:
R
=
T
+
F
Therefore,
when
R
achiev
es it
s hi
ghe
st
(i.e., the
si
ze of the
blo
c
k), i
n
crea
sin
g
T
will certai
nly
d
e
c
r
e
as
es
F
,
which expl
a
i
ns the pea
k in Figure 6.
The same f
a
lse po
sitive
effect is also
expecte
d in
other
existing
blo
c
k-ba
se
d
authe
ntic
atio
n techniq
u
e
s
. In p
r
a
c
tice,
however, a
s
an
attacker u
s
u
a
lly tries to alter the se
mantics
of the image, ta
mpered pixel
s
tend to cl
uster
together
(ma
y
be in several location
s).
Ran
domly alt
e
ring th
e pix
e
ls i
s
mea
n
in
gless a
nd h
e
n
ce
not likely to happe
n.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 12, No. 4, Dece
mb
er 201
4: 112
3 – 1131
1128
Y
n
1
Y
n
2
Y
n
3
H
i
1
H
i
2
H
i
3
X
m
1
X
m
2
X
m
3
V
j
3
V
j
2
V
j
1
Figure 4. Example of a false positive
Fi
gure 5.
A
tampered re
gio
n
(bla
ck pixel
s
)
Figure 6. Nu
mber of false positive
s
vs. numbe
r of ra
ndomly tamp
ered pixel
s
2.3. Handlin
g Irregular Image Sizes
If the image size i
s
not mul
t
iples of the
size
of the
aut
hentication bl
ock, som
e
thi
ng mu
st
be don
e for the extra area
s. Since 64 b
i
ts are r
equi
red for a sig
n
a
ture, every
32 pixels can
be
colle
cted to
form
an in
dividual a
u
thenti
c
ation
blo
ck.
In those a
r
ea
s, ho
weve
r, i
f
the sig
natu
r
e
mismat
che
s
,
it can
be
only
co
nclu
ded
th
at one
or
more pixels in
su
ch
a blo
c
k
co
uld have
be
e
n
altered. Figu
re
7 sh
ows su
ch a situation
.
The gra
nula
r
ity of identifi
c
ation
in th
ose area
s i
s
th
us
32 pixels.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Im
age Tam
p
er Dete
ction
and Recovery by
Inte
rsect
i
ng Signatu
r
e
s
(Chun
-Hun
g Che
n
)
1129
Figure 7. Han
d
ling the situ
ation in whi
c
h
the image si
ze is n
o
t multiples of
B
B
3. Experimental Re
sults
A set
of 48
0
480
gray
scal
e imag
es (
Ai
rplane
,
Ba
boo
n
,
Len
a
, an
d
Peppe
rs
) we
re
u
s
ed
to test the
prop
osed alg
o
rithm: Figu
re 8(a)
a
nd
8(b
)
sho
w
the origi
nal image
s and
the
corre
s
p
ondin
g
data
em
be
dded
version
s
. Th
e PSNR b
e
twe
e
n
the o
r
igin
al
a
nd the
em
be
dde
d
image
s a
r
e
44.16, 4
4
.14,
44.15,
and
44.12,
re
sp
e
c
tively,
whi
c
h
a
r
e quite accepta
b
le. The
para
m
eters u
s
ed are
B
=160,
R
=10, a
nd
s
=(
160
10
)
2. The
r
efore, th
e si
ze
s of th
e
authenti
c
atio
n
and recovery
blocks
are
1
6
0
1
60 a
nd
10
1
0
, re
spe
c
tively. The distan
ce b
e
twee
n a re
co
very
block
and
its co
rrespon
di
ng em
bed
din
g
on
e i
s
at
l
e
ast h
a
lf of th
e hei
ght of th
e auth
entication
block. Figu
re
8(c) a
nd 8
(
c) sho
w
the ta
mper
ed ima
g
e
s a
nd the
re
sults
of tamp
er dete
c
tion.
The
modificatio
n
s are
as follo
ws. Ai
rplan
e
: the num
be
r
16 is chan
ge
d to 10; Ba
b
oon: a
polyg
on is
place o
n
its n
o
se;
Len
a: a
dot is pla
c
e
d
on h
e
r face;
and P
eppe
rs: a
sq
uare i
s
p
l
ace
d
o
n
o
n
e
of
the pepp
ers. As ca
n be se
en, all of the tampere
d
pi
xels are
co
rrectly identifie
d, together
with
only a few false
po
sitives, whi
c
h
are
sho
w
n
in Fi
gure
8(e). T
he nu
mbe
r
o
n
the ai
rpla
n
e
is
corre
c
tly dete
c
ted
with
a fe
w fal
s
e
po
sitives. Th
e d
o
t
on
L
ena
’
s
fa
ce is corre
c
tly
detecte
d
with
out
any false p
o
si
tive. The p
o
lygon i
s
co
rrect
l
y detecte
d a
nd a
convex
sha
pe i
s
fo
rm
ed tog
e
the
r
with
the false po
sitives. Such result is id
ent
ical to
the previous a
naly
s
is. And the
squ
a
re o
n
th
e
pepp
er i
s
co
rre
ctly dete
c
t
ed
with a
fe
w fal
s
e
po
sitives. The
recovered
results a
r
e
sh
own
in
Figure 8
(
f)
a
nd thei
r PSNR a
r
e
43.64,
43.94, 4
4
.
15,
and
44.1
1
,
resp
ectively. We ca
n see
the
tampered re
g
i
ons a
r
e well recovered.
(a)
(b)
p
B
I
n
dividual
si
g
n
ature
blocks
q
B
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 12, No. 4, Dece
mb
er 201
4: 112
3 – 1131
1130
(c)
(d)
(e)
(f)
Figure 8: (a)
origin
al imag
es, (b
) data e
m
bedd
ed
ima
ges, (c) tam
p
ered im
age
s, (d)
results of
tamper d
e
tect
ion, (e) fal
s
e
positive
s
, and
(f) re
covered
result
s of tampered imag
es
4. Securit
y
A
n
aly
s
is
As the DES encryptio
n syst
em is used to
generate the signatu
r
e
s
, the pro
p
o
s
ed
method
is
se
cu
re
aga
inst the
atta
ck of
mani
pula
t
ing individ
ual
imag
e pixel
s
. Three
other
attacks are th
e
sea
r
c
h
,
collage
, and
cut
-
a
nd-p
a
st
e
atta
cks [9],[10],
whi
c
h are co
mmon for blo
c
k-wi
se
cont
ent
authenti
c
atio
n techniq
u
e
s
. Becau
s
e the
attacked im
a
ge has to mai
n
tain good vi
sual qu
ality, the
size of th
e p
a
s
ted
blo
c
ks
h
a
s to
be
very
small i
n
o
r
d
e
r for
ke
eping
t
he h
o
mog
e
n
e
ity of the bl
o
ck
conte
n
t. Therefore, the
ke
y requi
rem
e
n
t
for these
ki
nds
of attacks to b
e
successful is that
the
block
size is
small e
nou
gh
, usually le
ss
than o
r
eq
ual
to 8
8
pixels. In the pro
p
o
s
ed
method,
as
the si
ze of th
e blo
ck i
s
1
6
0
16
0, it cle
a
r
ly makes th
ese
attac
ks i
n
feasi
b
le. Th
at is, even if
the
attacker may
forge an a
u
thentic im
age
from a
data
base co
ntaini
ng hun
dre
d
s
of thousa
n
d
s
of
authenti
c
ima
ges, it will
certainly have
poor vi
sual
quality due t
o
blo
ck
effects and i
n
correct
block content
. In conclu
sio
n
, our metho
d
is
invulnerable to thes
e attac
k
s
.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Im
age Tam
p
er Dete
ction
and Recovery by
Inte
rsect
i
ng Signatu
r
e
s
(Chun
-Hun
g Che
n
)
1131
5.
Comparis
on of De
tec
t
ion
Granulari
t
y
The dete
c
tio
n
gra
nula
r
ity of the pro
p
o
s
ed metho
d
is comp
are
d
with those of
Patra
et
al.
’s
[4], Qi
et a
l
.
’s [5], a
n
d
Wu’s [6] m
e
thod
s. Be
ca
use
the
gran
ularity of
Qi
et al.
’s and
Wu’
s
method
s d
e
p
end
s on th
e i
m
age
si
ze, a
unified
size
of 256
×25
6
p
i
xels is
used
in the an
alysi
s
here. T
he
co
mpari
s
o
n
is
shown in Ta
bl
e
1, in
whi
c
h
it is obviou
s
t
hat our
meth
od outp
e
rfo
r
ms
the others.
Table 1. Co
m
pari
s
on of the
detection g
r
a
nularity
The pro
posed
Patra
et al.
's
Qi
et al.
's
Wu’s
1×1=1 pixel
8×8=64 pixels
8×8=64 pixels
45 pixels
6. Conclusi
on
In this pap
er,
we have
de
scrib
ed a te
ch
nique to id
ent
ify tampered
pixels in a
n
i
m
age. It
is b
a
sed u
p
on dividin
g
t
he ima
ge i
n
to auth
ent
ication bl
ocks a
nd a
r
rangin
g
linea
r
sign
a
t
ure
blocks in
su
ch a
way th
at they interse
c
t at
every pixel. As a co
nsequ
en
ce, ea
ch
pixel is
prote
c
ted by four sig
natures
and
su
ch
an arrang
em
ent make
s o
u
r tech
niqu
e cap
able of, in the
best
ca
se, pi
npointin
g a
si
ngle alte
re
d
pixel. This
te
chni
que preserves
the perceptu
a
l simila
rity
of the origin
al and the waterma
r
ked i
m
age
s, and
it is also secure ag
ain
s
t variou
s po
ssi
ble
attacks. Although false p
o
sitives are like
l
y to be
reported if altered pixels are sp
read ra
ndoml
y
throug
hout th
e image, an
attacke
r se
ems to have
no rea
s
o
n
to ran
domi
z
e
the alteratio
n
s.
Therefore, ou
r method i
s
very useful fo
r protecti
n
g
the conte
n
ts of the image
s at the granul
ari
t
y
of one
pixel. More
over, th
e tampe
r
ed
region
ca
n be
well
re
cove
red with
the e
m
bedd
ed
re
cover
data
.
Referen
ces
[1]
Liu
H, Lin
J, H
uan
g J.
Image
authe
nticati
o
n
usin
g
co
ntent
base
d
w
a
ter
m
ark
. Proc. IEEE Int. S
y
m.
Circuits a
nd S
ystems. 2005; 4
:
4014-4
0
1
7
.
[2]
Ra
w
a
t
S, Ra
man B. A c
h
aotic s
y
stem
base
d
frag
il
e
w
a
t
e
rmarki
n
g
scheme
for i
m
age
tampe
r
detectio
n
.
Int. J
.
Electron. Comm
un.
2011;
65: 840-
84
7.
[3]
X
i
'an
Z.
A se
mi-fragil
e
d
i
gita
l
w
a
termarki
ng
alg
o
rith
m i
n
w
a
vel
e
t transfor
m
d
o
m
a
i
n
bas
ed o
n
Arn
o
l
d
transform
.
Pro
c
. IEEE
Int. Conf. Signal Proc
ess. 2008: 2
2
1
7
-22
20.
[4]
Patra JC, Phua JE, Rajan
D.
DCT
do
main
w
a
termarki
ng sc
he
me
usi
ng
Ch
ines
e R
e
mai
n
d
e
r T
heor
e
m
for ima
ge a
u
th
enticati
on.
Pro
c
. IEEE
Int. Conf. Multimedi
a and E
x
p
o
. 201
0: 111-1
16.
[5]
Qi
X
,
Xin X
,
Chang R.
Image
auth
entic
ation
an
d ta
mper d
e
tectio
n
usin
g tw
o co
mp
le
me
ntar
y
waterm
arks.
Proc. IEEE Int. Conf. Image Pro
c
ess. 2009: 4
2
57-4
260.
[6]
Wu
Y.
T
a
mper
-Loca
l
i
z
a
t
i
on
W
a
termark
i
n
g
w
i
th Systemati
c
Error Corr
ec
ting C
o
d
e
. Proc. IEEE Int.
Conf. Image Pr
ocess. 200
6: 1
965-
196
8.
[7]
Che
n
CH, T
ang YL, Hsi
e
h
W
S
, H
w
a
n
g
MS. Image Protection
b
y
Intersecti
ng
Sign
atures.
T
E
LKOMNIKA Indon
esi
an Jou
r
nal of Electric
al Eng
i
ne
eri
n
g
.
2014; 1
2
: 638
6-63
92.
[8]
Wallace
GK. T
he JPEG Still Picture
Com
p
ressi
on Sta
n
dard.
IEEE Tr
ans. Consumer Electronics
.
199
2; 38: xv
iii-
xxxiv.
[9]
Holl
iman
M, Memon N.
C
ounterfe
itin
g Atta
cks on O
b
livi
ous
Block-
w
i
se In
de
pe
n
dent Inv
i
sib
l
e
W
a
termarkin
g Schemes.
IEEE Trans. Im
age Process
. 20
0
0
; 9: 432-4
41.
[10]
Barreto PS
LM
, Kim HY, Ri
j
m
en V. T
o
w
a
rd se
cur
e
p
u
b
lic-ke
y
bl
ock
w
i
s
e fra
g
il
e a
u
thentic
atio
n
w
a
t
e
rmarking.
IEE Proc. Vision, Imag
e an
d Sign
al Process
i
n
g
. 2002; 1
49: 5
7
-62.
[11]
Liu Q. An Adap
tive Blin
d W
a
termarking A
l
gor
i
t
hm for Color Image.
T
E
LKOMNIKA Indon
e
s
ian Jo
urna
l
of Electrical En
gin
eeri
n
g
. 20
1
3
; 11: 302-
309.
[12]
T
an X, Hu D.
A W
a
termarkin
g
Method Bas
ed on Optimiz
a
tion Statistics
.
T
E
LKOMNIKA Indones
ia
n
Journ
a
l of Elec
trical Eng
i
ne
eri
n
g
. 201
3; 11: 4
794-
480
2.
[13]
Ne
yma
n
SN,
Pradn
ya
n
a
IN
P,
Sitoh
ang
B.
A N
e
w
Co
p
y
ri
ght Prot
ection
for Vector
Ma
p us
ing
F
F
T
-
base
d
W
a
term
arkin
g
.
T
E
LKOMNIKA T
e
leco
mmu
n
icati
on,
Co
mp
uting,
El
ectronics and Contro
l
. 201
4;
12: 367-
37
8.
[14]
MT
Suryadi,
Nurp
eti E. Pe
rformance
of
Ch
aos-Based Encr
y
p
tion
Algo
rithm for
Digital Image.
T
E
LKOMNIKA T
e
leco
mmunic
a
tion, Co
m
puti
ng, Electron
ics
and Co
ntrol
. 2
014; 12: 6
75-6
82.
Evaluation Warning : The document was created with Spire.PDF for Python.