25-06-2012, 12:25 PM
A DATA EMBEDDING METHOD USING BPCS PRINCIPLE WITH NEW COMPLEXITY MEASURES
A DATA EMBEDDING METHOD USING BPCS PRINCIPLE WITH NEW.pdf (Size: 477.95 KB / Downloads: 66)
ABSTRACT
This paper presents a new method for embedding data
into an image called “A Block Complexity based Data
Embedding” (ABCDE).The principle of the method is
the same as that of BPCS-Steganography.Em bedding
is performed by replacing pixel data of noisy regions in
an image with another noisy data obtained by converting
data to be embedded.A complexity measure is defined
in BPCS-Steganography for discriminating noisy
regions in an image.It is a suitable measure, but is
not always applicable.The two new complexity measures
called the run-length irregularity and the border
noisiness are proposed in this paper to properly discriminate
noisy regions.An M-sequence is employed
for converting data to be embedded into noisy data.
ABCDE can be successfully applied to various images.
We can expect that near 50% pixels of an image can
be used for embedding without degrading its quality.
1 INTRODUCTION
Data embedding or data hiding is a technique that enables
us to secretly embed extra data into a file such as
an image file, a movie file, and an audio file[1, 9].The
embedded data disappear into the file and we cannot
recognize the embedded data in the file.W e will neither
find any header data or comments added to the
file.The embedded data, however, do exist in the file,
and we can extract it from the file.
Data embedding is applied for copyright protection,
secret communication, and data management.
Data embedding for copyright protection is specifically
called digital watermarking[7].When data embedding
is used for the purpose of secret communication, it is
called steganography[5].Data embedding can be also
applied for data management.F or example, we can
secretly embed annotations into an image.
The robustness of the embedded data is important
in digital watermarking.On the other hand, the embedding
capacity – quantity of data we can embed secretly
– is the main interest in steganography and data
management.
This paper presents a new method for embedding
data into an image.The method is called “A Block
Complexity based Data Embedding” (ABCDE).The
method can be applied for steganography or data management.
An image used for embedding is called a container
image and the data to be embedded into a container
image is called a resource file in this paper.ABCDE
can embed a resource file into 8bit-grayscale and 24bitfullcolor
images not in lossy compression format.The
resource file can be any single file or a set of files.
Since our eyes are not sensitive to slight alterations
of noisy data, we cannot notice even if the pixel data
in noisy regions of an image are replaced with another
data when it is also noisy.ABCDE is based on this
principle, which is introduced in BPCS-Steganography
(BPCS)[6, 8].
This embedding scheme works if we can locate noisy
regions in a container image correctly.The approach
employed in BPCS is to divide each bit-plane of the
container image regularly into small square binary
pixel blocks and to find blocks those have complex
black-and-white patterns.If a binary block has a complex
black-and-white-pattern, we can expect that the
block is in a noisy region.A complexity measure is
introduced to determine whether a block is complex or
not, i.e., whether the block has a complex black-andwhite
pattern or not.It is defined by the total length
of black-and-white borders within a block.If the value
of this black-and-white border complexity measure for a
block is higher than a given threshold value, the block
is regarded as complex one.
We can regard a resource file as a stream of binary
blocks.In BPCS, data embedding is performed by
replacing complex blocks in bit-planes of a container
image with the blocks obtained from the resource file.
When we regard the resource file as a stream of binary
blocks, some of them may be simple, i.e., not complex.
If we embed a simple block as it is, noticeable changes
may be left on the container image.The resource file
should hence be converted into a stream of complex
blocks on embedding.
In BPCS, an operation called conjugation is applied
to convert simple blocks into complex ones.In order
to extract the resource file embedded in the container
image, we should know which blocks of the resource file
are conjugated and which are not.This information is
stored in a conjugation map.It should be embedded
along with the resource file as blocks.Note that the
blocks of the conjugation map should be also conjugated
if they are not complex enough.
The above black-and-white border complexity is a
suitable measure for classifying blocks into complex
ones and simple ones.This measure is, however, not
always applicable.F or example, blocks with periodical
patterns – like chessboard or stripes – are classified
as complex ones by this measure.Suc h blocks
are, however, not suitable for embedding data, since
replacing them with noisy blocks disorders regular patterns.
This measure may also indicate that blocks on
the boundary of a noisy region and an informative region
are complex.Em bedding data in such blocks may
bring remarkable changes to a container image.
The new data embedding method ABCDE uses
two new complexity measures to properly discriminate
complex blocks from simple ones.One is computed
from the distributions of black and white pixels in rows
and columns of a block.It is called the run-length irregularity.
The other is computed from the distributions
of black-and-white borders between adjacent rows and
columns.It is called the border noisiness.These measures
are used at the same time.
The run-length irregularity is introduced to evaluate
the non-uniformity of black-and-white patterns within
a block.This measure can prevent us from selecting
blocks of periodical patterns for embedding.The
border noisiness is additionally introduced to check if
many black-and-white borders can be found within a
block and if they are well-distributed over the block at
the same time.W e can avoid using blocks not entirely
in noisy region with this measure.
A block is regarded as complex if its run-length irregularity
and border noisiness are larger than threshold
values given for these complexity measures.The
threshold values can be specified separately for each
bit-plane.This enables us to make the embedding capacity
large while keep image quality high.The defaults
for these threshold values are provided for convenience.
In ABCDE, data embedding is performed in the
same way as in BPCS.A resource file is regarded as
a stream of binary blocks.All the binary blocks are
converted into complex ones.They are then replaced
with complex blocks in bit-planes of a container image.
An M-sequence is employed for converting the blocks
of the resource file into complex ones.Although, the
block stream of the resource file may contain both complex
blocks and simple ones, all of them are uniformly
converted.As a result, we are not required to embed
information like the conjugation map.This makes the
embedding algorithm simple.A t the same time, overheads
required for embedding in ABCDE are smaller
than those required in BPCS.W e can specify an Msequence
as a parameter.
We can either embed the M-sequence parameter and
the threshold value parameters for complexity measures
with a resource file or keep them outside.When
these parameters are not embedded, we should specify
them correctly on extraction to retrieve the resource
file embedded in a container image.It is almost impossible
to extract the embedded resource file without
knowing them.This secure embedding mode is useful
for steganographic applications.On the other hand,
when these parameters are embedded, we do not have
to know any parameters except the block size.If we use
a default block size in common, anyone can extract the
embedded resource file.This self-contained embedding
mode is useful for data management applications
ABCDE can be successfully applied to various images.
W e can expect that near 50% pixel data of a
container image can be used for embedding without
degrading its quality.
The rest of this paper is organized as follows.The
new complexity measures the run-length irregularity
and the border noisiness are presented in Section 2.
Section 3 gives the details of the conversion required for
obtaining a stream of complex blocks from a resource
file.The embedding and the extraction algorithm are
described in Section 4.Exp erimental results are shown
in Section 5.Section 6 concludes this paper with future
directions of this research.
2 BLOCK COMPLEXITY MEASURES
The new embedding method ABCDE is based on the
principle introduced in BPCS.A resource file is converted
into noisy data, and is replaced with the pixel
data in noisy regions of a container image.W e have
to locate noisy regions appropriately to embed the resource
file secretly.If not, informative regions of the
container image would be disordered by the embedded
resource file and noticeable changes would be left after
embedding.
In BPCS, the noisy region of an image is located on
each bit-plane as small pixel blocks those have noisy
patterns.Eac h bit-plane of a container image is regularly
divided into small square binary pixel blocks as
illustrated in Figure 1.A binary pixel block can be
regarded as one in a noisy region if it has a complex
black-and-white pattern.Only such complex blocks
are used for embedding.
On embedding, the blocks on the lowest bit-plane
(the LSB plane) is used first.The blocks in a container
image are examined one by one from those on the LSB
plane through up to those on the highest bit-plane (the
MSB plane).A resource file is embedded piece by piece
as a complex block is found on a bit-plane.This way
of embedding is preferable, because changes in lower
bit-planes would not spoil the quality of a container
image greatly.
bit 0
bit 1
bit 2
bit 3
bit 4
bit 5
bit 6
bit 7
8bit image 1bit image x 8
binary pixel block
Figure 1: Binary pixel blocks on bit-planes
The problem here we encounter is how to measure
the complexity of the black-and-white pattern in a
block.In what follows, the complexity measure employed
in BPCS is reviewed first in Section 2.1. Two
new complexity measures are then presented in Section
2.2 and Section 2.3. A block is regarded as complex
when the values of the two complexity measures
for the block are large.Section 2.4 shows a variety of
blocks those are different in respect of the two complexity
measures.The distributions of the two complexity
measures for a photo image are also shown.The result
of a simple statistical analysis of the two complexity
measures is described in Section 2.5. The formal definition
of a complex block is given in Section 2.6. A
complex block is discriminated by the threshold values
for the two complexity measures.The defaults of the
threshold values are introduced in Section 2.7
2.1 Black-and-White Border Complexity Measure
We find that a block is simple when it is entirely or
almost entirely in black or white.Figure 2 shows an
8×8 block.It looks simple.There are (8−1)×8×2 =
112 pixel borders inside, but only eight out of them lie
between black and white pixels.The others lie between
the same color pixels, i.e, either between two white
pixels or between two black pixels.A block can thus
be regarded as simple when it has a few black-andwhite
borders in it.
This observation leads us to the definition of a complexity
measure of a block based on the total length
of black-and-white borders in it, which is employed in
BPCS[6, 8].Supp ose that k out of M pixel borders lie
between black and white pixels in a block, the com-
Figure 2: A simple block
plexity measure is then given by
α = k/M. (1)
For example, α = 8/112 for the block in Figure 2.If
α of a block is large, the block has many black-andwhite
borders inside, and we can regard it as complex.
On the other hand, if α of a block is small, the block
must be simple.The range of this measure is [0, 1].A
threshold value α0 is introduced to discriminate complex
blocks from simple ones.A block B is regarded
as complex if α(B) ≥ α0.Figure 3(a) and (b) show a
simple block and a complex block in respect of α.The
values of α are 20/112 and 72/112 respectively.
(a) (b)
Figure 3: A simple block and a complex block in respect
of α
This black-and-white border complexity measure α
is easy to understand and usually works well for classifying
blocks into complex ones and simple ones.This
measure is, however, not always applicable.Ev en when
a block contains many black-and-white pixel borders,
it does not necessarily mean that the block is complex.
(a) (b)
Figure 4: Blocks that are not complex
For example, a block with a chessboard pattern
shown in Figure 4(a) has the measure α = 1, i.e., the
maximum of α.This block, however, has a regular periodical
pattern, and cannot be regarded as complex
one.If we replace such a block with another one with
noisy pattern, it would result in disordering regular
pattern and would bring noticeable change to a container
image.
A possible workaround here is to introduce a upper
limit threshold α1 besides the lower limit threshold α0
and to accept only blocks those have α ∈ [α0, α1].Unfortunately,
even if we adopt this new criterion, we
may still encounter blocks like one shown in Figure
4(b), for which α = 0.5.If we exclude 0.5 from the
range [α0, α1], it would result in missing many complex
blocks.
Figure 5: A blocks on the boundary of a noisy region
We have another problem.Since bit-planes of a container
image is divided regularly into blocks regardless
of their contents, some of the blocks may be on the
boundary of a noisy region and an informative region.
An example of such a block is shown in Figure 5.The
black-and-white border complexity measure α may indicate
such a block is complex.Em bedding a resource
file in such blocks in a container image would, however,
cause the noisy region to grow.As a result, remarkable
changes would be left on the container image.
We thus notice that the black-and-white border complexity
measure cannot always be applicable for finding
complex blocks.Tw o new complexity measures are
proposed in this paper to properly discriminate complex
blocks from simple ones.They are called the runlength
irregularity and the border noisiness.If a block
has large run-length irregularity and large border noisiness
at the same time, we can regard it as complex
one.These complexity measures are presented in the
following sections.