iDocSlide.Com

Free Online Documents. Like!

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Share

Description

Abstract A novel {2, 2} visual cryptography scheme for processing color images based on a Karnaugh map design is introduced in this paper. The encryption and decryption functions are executed at the bit levels of the RGB color representation. The

Tags

Transcript

1
A Karnaugh Map Based
{
2,2
}
VisualCryptography Scheme For Color Images
Mohsen Heidarinejad and K.N. PlataniotisThe Edward S. Rogers Sr. Department of ECE,University of TorontoE-mail:
{
mohsen,kostas
}
@comm.utoronto.ca
Abstract
A novel
{
2,2
}
visual cryptography scheme for processing color images based on a Karnaugh mapdesign is introduced in this paper. The encryption and decryption functions are executed at the bitlevels of the RGB color representation. The proposed scheme affords no pixel expansion and offersperfect reconstruction. Experimental results including in this paper support the main argument thatthe developed scheme is ideal for transmission of color images over un-trusted, bandwidth limitedcommunication channels.
I. I
NTRODUCTION
Digital data security and integrity preservation is paramount in modern communication sys-tems. The conﬁdentiality of the visual data transmitted over digital communication networksis usually obtained by encryption. Visual data protection is achieved either by employing datahiding techniques or through secret sharing (visual cryptography). Image data hiding techniquesembed information by modifying the srcinal image to be transmitted in a imperceptible way [1].Secret sharing schemes on the other hand are based on the principle of sharing secret informationamong a group of participants. The shared visual secret is recovered only when a coalition of willing participants are polling their shares together [2].The proposed here visual cryptography scheme is intended for transmission of natural colorimages over untrusted communication channels of limited bandwidth although it is readilyapplicable to gray scale images or computer generated visual data. It operates directly on the bit
April 3, 2007 DRAFT
2
plane representation of the input image and produces noise-like shares for distribution over theuntrusted public networks. Using reciprocal encryption and decryption procedures, the visualcryptography scheme recovers the input image and makes it readily available for subsequentimage processing tasks. The two factors that determine the quality of the recovered image arethe relative contrast difference and the pixel expansion-
m
. The relative contrast difference refersto the difference in contrast between the srcinal image and the recovered image. Pixel expansion(
m
) refers to the number of subpixels in the share images needed to represent a single pixel of the srcinal input image. Obviously the larger the value of factor
m
the larger the size of theshare. Share size must be controlled since most communication channels are of limited capacity.Therefore, in a bandwidth constrained communication channel it is desirable to keep
m
as smallas possible. Given the fact that color images, due to their tristimulus representation, occupymuch more space and require much more bandwidth for transmission compared to gray scaleimages, it is important to develop a visual cryptography scheme with no pixel expansion, inother words a scheme with
m
= 1
. In [3],[4] and [5] half-toning and dithering methods are usedto control pixel expansion. However half-toning reduces the quality of the input as well as thatof the reconstructed srcinal. Many of the existing schemes that offer no pixel expansion resultin either poor quality reconstructed images or images that are not identical to the srcinal input.For example, in [6] and [7] the reconstructed image’s brightness looks unnatural resulting in poorvisual quality results. Similarly the proposed in [8] scheme, has a pixel expansion factor
m
= 1
but it can not restore the original image perfectly. The hybrid visual secret sharing scheme[9] has an adjustable pixel expansion at the expense, however, of the reconstruction quality.The methodology in [9] explains the trade off between share size and contrast and introducessize adjustable visual secret sharing mechanism such that the user can choose the appropriateshare size and the recovered image contrast that ﬁts an application. In [10] a bit reversingvisual cryptography scheme where white pixels are almost perfectly reconstructed in additionto perfectly reconstructed black pixels is proposed. In [11] a color
{
2,2
}
visual cryptographyscheme with a pixel expansion factor of
m
= 4
is proposed, however the solution cannot perfectlyreconstruct the srcinal input image. The same performance is reported in [12]. The method hasan expansion factor of
m
= 1
but it cannot be applied when the reconstructed image must bevery similar to the srcinal input image. The scheme in [13] perfectly reconstructs the srcinalinput image because the encryption and decryption functions are reciprocal but it has a pixel
April 3, 2007 DRAFT
3
expansion factor of
m
= 4
and thus it cannot be used for cost-effective communications overbandwidth constrained channels. The main contribution of this paper is the introduction of a newperfect reconstruction
{
2
,
2
}
visual cryptography scheme with no pixel expansion
(
m
= 1)
. Theproposed algorithm can be viewed as the basic solution of a generic
{
t,n
}
visual secret sharingproblem [14],[15] and [16] for color images.The rest of this paper is organized as follows. A brief description of visual cryptographyis given in section
2
. The proposed scheme is presented in section
3
. Section
4
summarizesexperimental result, while conclusions are drawn in section
5
.II. B
RIEF REVIEW OF VISUAL CRYPTOGRAPHY
Visual cryptography solutions can be applied to binary, gray-scale and color data [17]. Allvisual cryptography(VC) schemes are based on threshold designs or access structure solutions[18]. Threshold VC is a type of secret sharing scheme ﬁrstly introduced by Naor et al [19].The scheme recovers the input image without the use of any complex decoding operations byusing the human ability to process visual content. In the general
t
out of
n
VC scheme, which isdenoted as
{
t,n
}
scheme, an image is encoded to n shares of random patterns by means of twodeﬁned matrix sets. Each participant is given a share which is basically the srcinal input (secret)image whose pixels have been replaced by some other pixels according to a sharing policy. Anysubset of participants with
t
or more elements can detect and reconstruct the srcinal input image[19].An access structure VC scheme typically follows the general access structure developed byAteniese et al [20]. The model describes a set of qualiﬁed subsets
Γ
Qual
and a set of forbiddensubsets
Γ
Forb
on
n
participants
P
=
{
1
,
2
,...,n
}
. Only the participants of any qualiﬁed subsetcan jointly reconstruct the input image. The pair
(Γ
Qual
,
Γ
Forb
)
is called the access structure of the scheme. In the scheme proposed here
Γ
Qual
=
{
P
1
,P
2
}
where
P
i
is
i
th
participant. This isdue to the fact that for reconstructing the input image all shares are needed.
April 3, 2007 DRAFT
4
III. P
ROPOSED METHOD
A. Encryption
Color images are usually represented in the RGB color space for both visualization and storage.In RGB a given color image
A
is deﬁned as
A
:
Z
2
→
Z
3
. In other words it is considered tobe a
(
K
1
×
K
2
)
matrix with each of its elements being a three-dimensional vector. Each pixelhas three colors-red,green and blue-with intensity values ranging from
0
to
255
. Thus each of these color pixels is represented using
24
bits according to the formula:
A
(
i,j
)
= [
a
(
i,j
)1
,a
(
i,j
)2
,a
(
i,j
)3
]
(1)where
(
i,j
)
(for
i
= 1
,
2
,...,K
1
and
j
= 1
,
2
,...,K
2
) and
c
= 1
,
2
or
3
are the spatial positionand color channels respectively with
c
= 1
denoting the
R
component,
c
= 2
denoting the
G
component and
c
= 3
indicating the
B
component. Using the bit-level notation, the
a
(
i,j
)
c
element of the color vector
A
(
i,j
)
can be expressed as follows:
a
(
i,j
)
c
=
8
k
=1
a
k
(
i,j
)
c
2
8
−
k
(2)where
a
k
(
i,j
)
c
equals to binary zero or one (bit). In the proposed method, the original secretimage is transformed into a noise like image by permuting all pixels according to a secret key.A permutation step determines the correlation between neighboring pixels that is needed toincrease the randomness of the shares. Two matrices
R
and
C
with corresponding dimensions
(
K
1
×
K
1
)
and
(
K
2
×
K
2
)
are needed in the implementation of the permutation module. Thedeﬁning characteristic of the two matrices is that they are containing only one
1
in each rowand each column while the rest of the elements are set to zero. The srcinal input image
A
ispermuted using the formula :
A
permuted
= (
R
×
A
)
×
C
(3)In the srcinal proposal of [19] each bit of the binary input image is replaced with a randomlyselected row of some generator matrix using two sets of matrices and a given sharing policy.The proposed scheme follows the same design fundamentals. In particular, the proposed schemeencrypts two srcinal bits by mapping them to two bits thus offering no pixel expansion
(
m
= 1)
.By design the input image (secret input) and the two shares are of the same size. It is easily
April 3, 2007 DRAFT
5
understood that for two bits, the four possible combinations are
{
00
,
01
,
10
,
11
}
. Based on thepermissible combinations, four
(4
×
4)
encryption matrices are deﬁned as follows:
E
00
=
0 1 0 10 1 1 01 1 1 11 0 0 1
E
01
=
0 0 0 01 1 0 01 1 1 01 0 1 1
E
10
=
0 0 0 10 0 1 10 1 1 11 1 0 1
E
11
=
0 0 1 00 1 0 01 0 0 01 0 1 0
where
E
ij
is the basis matrix for encrypting the binary tuple
(
i,j
) (
i,j
= 0
or
1)
. Theencryption module utilizes a random generation algorithm, called ”
rand
function”, to generatea random number
q
[1
,
4]
(the number of
E
ij
rows). Based on its outcome, the dealer usesthe
q
th
row of
E
ij
matrix
(
E
qij
)
to encrypt the tuple
(
i,j
)
. The ﬁrst 2 elements of
E
qij
form theﬁrst share related to
(
i,j
)
while the remaining two elements form its second share. Thus theencryption function can be deﬁned as:
f
e
(
i,j
) =
E
qij
= [
f
e
1
ij
,f
e
2
ij
] = [(
h
11
,h
12
)
,
(
h
21
,h
22
)]
(4)and
E
qij
= (
h
11
,h
12
,h
21
,h
22
)
(5)where
f
ekij
and
h
tz
(
k,t,z
= 1
or
2)
are the
k
th
part of the encryption function for the tuple
(
i,j
)
and
z
th
element of
t
th
share, respectively. Certain conditions and constraints are imposed duringthe matrix generator row selection. For example, each of the 2-tuples
(
h
11
,h
12
)
and
(
h
21
,h
22
)
must be different from the srcinal binary tuple
(
i,j
)
since shares must be signiﬁcantly differentfrom the input image. As each row of encryption matrices has
4
elements, there are
2
4
= 16
possible choices for each row. However, the imposed constraints eliminate 7 choices (forbiddencombinations) from the Karnaugh table [21] (the row and column that contain the binary tuple
(
i,j
)
). Thus, the permissible choices are based on the remaining nine elements as they are deﬁnedby the Karnaugh map logic. For example, assuming that the dealer considers replacing the rowsof matrix
E
00
, the allowable options are restricted to the minterms marked in Fig.2. A minterm
April 3, 2007 DRAFT

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...Sign Now!

We are very appreciated for your Prompt Action!

x