Reversible Binary Image Watermarking Method Using Overlapping Pattern Substitution

ETRI Journal.
2015.
Oct,
37(5):
990-1000

- Received : September 24, 2014
- Accepted : June 08, 2015
- Published : October 01, 2015

Download

PDF

e-PUB

PubReader

PPT

Export by style

Share

Article

Metrics

Cited by

TagCloud

This paper presents an overlapping pattern substitution (PS) method. The original overlapping PS method as a reversible data hiding scheme works well with only four pattern pairs among fifteen possible such pairs. This paper generalizes the original PS method so that it will work well with an optimal pair from among the fifteen possible pattern pairs. To implement such an overlapping PS method, changeable and embeddable patterns are first defined. A class map is virtually constructed to identify the changeable and embeddable pairs. The run-lengths between consecutive least probable patterns are recorded. Experiments show that an implementation of our overlapping PS method works well with any possible type of pairs. Comparison results show that the proposed method achieves more embedding capacity, a higher PSNR value, and less human visual distortion for a given embedding payload.
a weight score
using a randomly generated
weight matrix
, where the score is equal to the secret message.
Further improvements to the visual quality of an embedded image (stereo image) were made by introducing quality control when embedding data into blocks
[8]
. In every block, the number of black pixels can be either an odd or even number. The approach to embed one bit “1” or “0,” in
[8]
, is to flip pixels to control the number of black pixels in one block to be even or odd.
In
[9]
–
[11]
, Wu and others proposed a
flippability score
considering the connectivity and smoothness of a square area comprising three-by-three pixels; Yang and Kot
[12]
–
[13]
proposed a
flippability criterion
.
An authentication scheme with tampering localization was proposed by Cheng that uses a different flippability criterion to reduce image distortion
[14]
–
[16]
.
Tzeng and Tsai
[17]
used an
optimal code holder
to embed binary data into every block.
Yang and others
[18]
used a morphological transform to achieve high embedding capacity. Unfortunately, the algorithms used in the aforementioned studies were all of the lossy type. As a result, there are not many reversible watermarking methods for binary images available today.
Tsai and others
[19]
have proposed a method called pair-wise logical computation (PWLC). It successfully exploits special patterns, such as “000000” and “111111,” and hides secret data within these patterns. The PWLC method identifies such patterns on the boundaries (that is, edge area) of an image to reduce visual perceptibility. Thus, even though there are many cases of such special patterns within a single binary image, only a certain number of such special patterns on the boundaries of the image are used. The embedding rule is simple. If the secret bit is “0,” then the third and fourth bit positions are flipped. Otherwise, if the secret bit is “1,” then the third and fourth bit positions are flipped. Of course, embedding capacity is dependent upon the number of such patterns at the boundaries. Since this method utilizes lengthy special patterns of six bits and flips only the center bit positions, boundaries can look untidy after data hiding.
A pattern substitution (PS) method has been proposed by Ho and others
[20]
and is an improvement upon the PWLC method. The PS method hides data into the boundaries of a binary image. It locates the boundaries using an edge detector
[21]
. The authors’ PS method uses four bits for each pattern; thus, there are sixteen possible patterns in total. Among them, two pattern types — more probable pattern (PM) and less probable pattern (PF) — are used to hide data. For each PM, its counterpart, PF, is decided by the PS method. After this, the PS method records all the locations of the PFs in advance. The PS method hides a secret bit “0” by rewriting a PM or PF pattern to PM, and it hides a secret bit “1” by rewriting a PM or PF pattern to PF. Since a four-bit pattern is used instead of a six-bit pattern, the PS method is less likely to have a significant effect on the appearance of the boundaries of an image.
There are two types of PS — block-wise disjoint PS (non-overlapping PS) and block-wise overlapping PS (overlapping PS). In the case of block-wise disjoint PS, all blocks are mutually exclusive to each other (that is, disjoint). Thus, embedding and extracting procedures are relatively simple. However, the embedding capacity is not so large. On the other hand, if we allow some blocks to overlap each other, as in the case of block-wise overlapping PS, then this allows us to hide more data. Ho and others
[20]
have presented both methods.
In Dong and Kim
[22]
, a non-overlapping PS has been developed by reducing the PF location map. This method chooses the second least probable pattern, and it is defined as PFR in
[21]
. All the PF patterns are replaced with PFR patterns before the embedding process, and the sequence of PFs and PFRs is recorded using 0s and 1s in a new location map. The size of the new location map is equivalent to the sum of the PFs and PFRs. This approach can efficiently decrease the size of a PF location map; however, it can only be applied to a non-overlapping PS.
Xuan and others
[23]
have presented a different binary image reversible watermarking method. Their approach exploits a run-length histogram modification method. They construct a histogram of run-lengths from a binary image. A run-length pair consists of both a run-length of black pixels and a run-length of neighboring white pixels. By swapping one black pixel for one white pixel in the specific pairs, they can hide secret messages. The embedding capacity depends on the population counts of the most probable run-length and its neighboring run-length.
Zhang and others
[24]
–
[25]
have presented an optimal reversible data hiding method for
binary covers
. This method tries to embed binary data into binary covers. A cover is segmented into disjoint blocks, each block being of the same length. In each block, the pixels with value “0” are overwritten with a payload, and the positions of pixels with value “1” are recorded and embedded into the next block to achieve reversibility. The number of 1s in the payload determines the distortion. If the size of the payload is small, then the method losslessly decompresses the payload so that the number of 1s in the payload is reduced; in this way, the level of distortion is decreased.
In this paper, an improved version of the PS method in
[20]
is proposed. The overlapping PS version in
[20]
can be applied to only four pattern pairs among fifteen. Our method generalizes the algorithm so as to use all fifteen possible pattern pairs, which significantly increases the embedding capacity. We introduce two conditions for embedding based on two new concepts — changeable and embeddable patterns. If a pattern satisfies the two new conditions, then we can embed data into the pattern. These two new conditions reflect the interaction between the overlapping patterns that emerge after hiding data. If a pattern satisfies these two new conditions, even though this pattern may overlap with a neighboring pattern, then we can embed data without causing confusion in the extraction procedure. A new coding method is also proposed to decrease the size of the PF location map.
The remaining part of this paper is organized as follows. Section II reviews the original PS method and identifies the problem with this method. Then, the proposed improved PS method is explained in Section III. Important new concepts, such as changeable and embeddable patterns and class map (CCM), are also introduced in this section. Section IV shows that the proposed method works well with any kind of pattern pairs. In addition, this section analyzes the performance of the proposed method. Finally, the conclusion is presented with future works in Section V.
difference-value
matrix, denoted as
D
, is firstly derived from an original binary image according to
(1) $$D(i,j)=\{\begin{array}{ll}C(i,j)\text{}\hfill & i=1,j=1,\hfill \\ C(i,j)\oplus C(i-1,j)\text{}\hfill & i\ne 1,j=1,\hfill \\ C(i,j)\oplus C(i,j-1)\text{}\hfill & j1,\hfill \end{array}$$
where ⊕ stands for the exclusive-OR logic operation;
i
and
j
are the indices of the rows and columns in the binary image, respectively; and
C
is the matrix of the original binary image. Equation (1) shows that there are three different types of pixels in the binary image. The first case (when
i
= 1,
j
= 1) is for the pixel at the top-left corner. The difference value of this pixel is the value of the pixel in the original binary image. The second case (when
i
≠ 1,
j
= 1) is for the pixels in the first column, excluding the first pixel. The difference values of each of these pixels are defined as exclusive-OR with its upper pixel. In the third case (when
j
> 1), which is for the rest of the pixels, the difference values for these pixels is defined as exclusive-OR with its left pixel. One example of a binary image and its corresponding difference-value matrix is shown in
Fig. 1
.
Binary image and its corresponding difference-value matrix.
Each set of four consecutive difference values within difference-value matrix
D
(corresponding to four consecutive pixels) is labelled as being a specific
difference-value pattern
(from hereon in simply referred to as a
pattern
). A single pattern contains four bits. Therefore, there are sixteen possible patterns in total;
P
_{0000}
, … ,
P
_{1110}
, and
P
_{1111}
.” One bit of secret data is hidden through one PS in
D
. To reduce the distortion caused by substitution, the corresponding patterns are listed in
Table 1
.

Two patterns are chosen to embed data. These two patterns are known as a
pattern pair
and are denoted as PM and PF. To minimize image degradation, the following two requirements are necessary:
All the difference-value patterns are classified as belonging to either an “odd pattern set” or an “even pattern set” based on the number of 1s occurring within each of the difference-value patterns.
Each pattern pair consists of a PM and a PF. The PM and PF of a pattern pair should be chosen from the same pattern set (either from the odd pattern set or even pattern set). This statement can be explained with a simple example. Consider a binary bit stream “0010000” from an original image, and assume the bit in front of this stream is “0,” then this bit stream can produce the
difference-value
stream “0011000” by (1). For example, assume the binary stream in the image is “0010.” If the bit in front of this stream is “0,” then the binary stream is “00010;” the
difference value
is “0011.” Otherwise, if it is “1,” then the difference value is “1011.” The first pattern, that is
P
_{0011}
, can be replaced with
P
_{0010}
. Note that
P
_{0011}
belongs to the even group, but
P
_{0010}
to the odd group. As a result, the substituted string becomes 0010000, which produces the watermarked string 0011111 after an inverse transform. The important thing to note here is that the bit string following the first four bits in the watermarked stream is inverted from the original stream. This fact implies that the image quality after data hiding will become extremely poor. However, if the PF and PM are chosen from the same group, then this kind of thing does not happen.
With regards to trying to achieve a Hamming distance of “1” between each set of four bits between the original and watermarked images, “a Hamming distance of 1” means that only one bit is flipped between the two bit streams in question. For a given bit stream, say
B
_{wxyz}
, there are four different possible bit streams that produce a Hamming distance of “1” when paired with
B
_{wxyz}
. For example, bit streams
B
_{1001}
,
B
_{0101}
,
B
_{0011}
, and
B
_{0000}
are four possible streams with a Hamming distance of “1” to
B
_{0001}
. Note that there are PM and PF pairs ensuring a Hamming distance of “1” between the original and watermarked images.
Consider the binary bit pattern
B
_{0001}
and assume that its corresponding difference-value pattern is
P
_{0001}
. The candidates for substitution should then be of the form
B
_{xxx1}
, where
x
stands for a “don’t care” bit. Consider the “Hamming distance of 1” requirement. As a result, three possible output patterns can be
B
_{1001}
,
B
_{0101}
, and
B
_{0011}
, for which the corresponding difference-value patterns are
P
_{0010}
,
P
_{0111}
, and
P
_{1101}
, respectively (see
Fig. 2
). It can be verified that this is also the case for when the previous bit value is “1.” Thus,
P
_{0001}
can be a pair to
P
_{0010}
,
P
_{0111}
, or
P
_{1101}
. In other words,
P
_{0001}
can be substituted by any one of
P
_{0010}
,
P
_{0111}
, and
P
_{1101}
. According to this, the substitutable difference-value patterns for any pattern can be found (see
Table 1
).
Binary bit pattern B _{0001} (with a difference value of P _{0001}) can be substituted for either B _{0011}, B _{0101}, or B _{1001} (with a difference-value pattern of either P _{0010}, P _{0111}, or P _{1101}, respectively).
Note that statistically
P
_{0000}
is the most probable pattern. However, this pattern is not used due to the
visibility problem
. The most probable patterns among
P
_{0001}
, … ,
P
_{1110}
, and
P
_{1111}
are named as PM. For each PM, the least probable pattern among the three candidates from
Table 1
is named as PF.
Data hiding will be carried out by PS. After determining a suitable PM-PF pair, the PS method will rewrite all PM-PF pairs to PM to hide a bit 0; likewise to PF to hide a bit 1. The location map of PF patterns has to be embedded to the image too. In this way, the secret data can be extracted and the original image can be recovered at the decoder.
There are two variants of the PS method in Ho and others
[20]
. The
non-overlapping PS method
processes the difference-value patterns one by one, and the different difference-value patterns contain no overlapping parts. However, different difference-value patterns intersect each other in the
overlapping PS method
; special care needs to be taken with this approach, since tricky situations to be discussed below can happen.
Assume that there is a binary bit pattern contained within a binary stream, such as in 00
0001
1111, and let us assume that
P
_{0001}
and
P
_{0111}
make up the corresponding PM-PF substitution pair. In this case, an encoder, scanning the stream one bit at a time, encounters the first PM — the underlined pattern
P
_{0001}
. The PM can be kept as it is when a bit 0 is hidden. A decoder can recover the hidden message and keep the original pattern as it is. On the other hand, the PM can be substituted by PF, in which case the resultant stream becomes
0001
111111. However, the decoder assumes that the underlined pattern carries a hidden bit 0 — an incorrect interpretation.
To avoid such a misinterpretation, Ho and others
[20]
proposed the following two rules:
Under the above rules, an encoder will skip an input string of “0000011111” in accordance with rule 2.
When
P
_{0001}
is first encountered in the following input string “00
0001
1110,” the encoder searches for a
P
_{0111}
pattern to see whether the PM and PF overlap each other. In this string, 00
0001
1110, since the two patterns overlap, the encoder skips the underlined
P
_{0001}
pattern and uses the pattern
P
_{0111}
to hide a bit according to rule 1. If the bit to be hidden is “0,” then the PF is changed into PM; that is, 0000000110. Otherwise, the PF remains as it is. Thus, there are two possibilities after data embedding — 0000
0001
10 or 0000011110. As a result, there are no problems encountered in the decoding process.
embeddability
and changeability — to generalize the original PS method. These two concepts will be explained in the following examples.
Even though Ho and others
[20]
proposed the two aforementioned rules to avoid misinterpretation at the decoding stage, these rules only work well with the following four specific pairs: <
P
_{0001}
,
P
_{0111}
>, <
P
_{1000}
,
P
_{1110}
>, <
P
_{0011}
,
P
_{1111}
>, and <
P
_{1100}
,
P
_{1111}
>. Unfortunately, these rules do not work for other patterns.
Figure 3
shows three counterexamples that cannot be correctly decoded by Ho and others’ work
[20]
. The input string in
Fig. 3(a)
, 0100100, is encoded as 0111100 when the PM and PF pair is
P
_{0100}
and
P
_{0111}
, respectively. In this encoding, only one bit has been hidden. However, the decoder will try to extract two bits of message. The decoder first encounters the underlined pattern
P
_{0111}
in
0111
100, which is decoded as 0100100. Another underlined pattern, 010
0100
, is about to be decoded; the second decoding should not be carried out.
The input string in
Fig. 3(b)
, 0011110, is encoded as 0010010, where the PM and PF pair is
P
_{0010}
and
P
_{1110}
, respectively. In this encoding, only one bit is hidden using the PF pattern
P
_{1110}
(that is, 001
1110
). However, the decoder tries to extract two bits of message. It first encounters the underlined pattern as
P
_{0010}
in
0010
010, which is decoded as 0010010. Another underlined pattern, 001
0010
, is about to be decoded.
Consider the input string in
Fig. 3(c)
, 0100111, where the PM and PF pair is
P
_{0100}
and
P
_{0111}
, respectively. According to rule 1, an encoder can hide one bit into the PF, whereby the encoded string would become 0100100. The decoder will extract two bits even though just one bit has been hidden. The first bit is recovered from the first PM pattern (
P
_{0111}
) and the second bit from the second PM pattern (
P
_{0111}
) again.
Three counterexamples to Ho et al.’s rules [20] .
To generalize the original PS method, further refinement is needed. The refinement is made possible by categorizing patterns into five classes, as follows:
Every pixel belongs to one class only. An illustration is shown in
Fig. 4
. A table holding the class information is referred to as a CM. Pixels that lie within a distance of one to three pixels from a pixel are called
neighboring-range
pixels; those that are at a distance of one to six pixels are called
relative-range
pixels. A pattern’s representative position is the position of its first pixel.
Let us assume that at position 60 (see
Fig. 4
) a pattern’s difference-value substring is 0001, which is a PM pattern (that is,
P
_{0001}
), and that this pattern is about to be processed by an encoder. Note that in
Fig. 4
the PF pattern is 0111. Thus, the CM at positions 57 to 59 shows “1s”; the other patterns from position 61 onwards have not yet been processed; therefore, all are positions are showing a value of “0.” The CM being described here is shown in
Fig. 4
.
Illustration of CM where PM is 0001 and PF is 0111.
At position 60, the PM pattern can be flipped to the PF pattern to embed a bit 1. In this case, after data hiding, the pattern 0001 is changed into the pattern 0111. In this case, after data hiding, the new pattern at position 58 becomes 0001, which is a PM pattern. Thus, the CM at position 58 is changed from “1” (before data hiding) to “4” (after data hiding: see
Fig. 5
). These kinds of changes to a CM can cause misinterpretation at a decoder. Such misinterpretation can be avoided. Thus, two kinds of patterns are introduced in the next paragraph.
Here, two new concepts are defined — a changeable pattern and an embeddable pattern. As is clear from the counterexamples, not all of the PM or PF patterns can be used for data hiding. A changeable pattern should be either a PM or a PF before data hiding. In
Fig. 5
, let us assume that position 60 is the current position to be processed. In this case, the pixels at positions 57 to 59 and 61 to 63 are neighboring-range pixels. If the neighboring-range pixels of a CM do not change after PS, except in the cases of class 0 and class 2 pixels, then this PM or PF is known as a changeable pattern. Thus, changeability is dependent upon the values of neighboring-range pixels. In
Fig. 5
, the pattern at position 60 is not a changeable one, since after PS, at least one of the neighboring-range pixels is changed from a value of “1” to “4.” Thus, in this case, an encoder should skip data-hiding because it is known that the pattern is not a changeable one. Now, the CM shows a value of “2” at position 60.
Example of pattern that is not changeable when PM is 0001 and PF is 0111: (a) before substitution, (b) after substitution, and (c) final class of pattern 60.
A changeable pattern should meet the following two conditions:
When a PF or PM pattern is about to be substituted to embed data, the substitution has to meet at least two requirements. First, it should not destroy the patterns in which we have already embedded data. This means that PM or PF patterns of the class 3 or class 4 type in a neighboring range should not be destroyed. In other words, any PF pattern of the class 3 type should remain as a PF, and any PM pattern of the class 4 type should remain as a PM. Thus, any pattern in class 1 should be in the same class.
Assume a class 2 pattern is in the neighboring range. Due to the change of the current pattern (either PM or PF), the class 2 pattern can be changed into a class 1 pattern or remain as it is. In the first case, the class 2 pattern can be changed to neither PF nor PM (that is, into a class 1 pattern) after flipping. In the second case, the class 2 pattern can be flipped to either a PF or a PM and still be classed as a class 2 pattern. Thus, a class 2 pattern can be changed to any pattern without misinterpretation in a decoder.
Can an encoder always embed data when a pattern is changeable? The answer is not always. Assume that PM and PF are 1001 and 1111, respectively (see
Fig. 6
). Note that the pixel processing order can be randomized for security purposes. For example, a hiding gap (HG)
[20]
has been proposed, and an HG value is shared by an encoder and decoder.
Assume that the processing order is randomly decided as follows: for example, first, at position 72, second, at position 70, and finally at position 73. The pattern at position 72 is 0100, which is neither PM nor PF. As a result, its CM is “1.” At position 70, the pattern to be processed is 1001, which is a PM. Thus, its CM is “4.” At position 73, the pattern to be processed is 1001, which is also a PM. This pattern is changeable according to the changeability rule. However, we want to see what happens if this pattern is substituted for 1111, which is a PF. If this pattern becomes 1111, then the previous pattern 1001 at position 70 is not changeable at the decoder, and its class changes from “4” to “2” as shown in
Fig. 6(b)
. Thus, the second PM pattern (at position 73) should be skipped without hiding any bit. One bit has been hidden into the first PM pattern at position 70, since it was both changeable and embeddable. However, an encoder has to skip the second PM pattern since it is not embeddable. The encoder can also hide one bit into the third PM pattern at position 76 since it is both changeable and embeddable under the assumption that the second pattern has been skipped.
Changeable but not embeddable pattern when PM is 1001 and PF is 1111, and processing order is at position 72, position 70, and position 73: (a) before substitution, (b) after substitution, and (c) final class of pattern 73.
It is necessary to see whether a pattern is embeddable when a number of PM patterns repeat. An embeddable pattern should meet the following conditions:
The conditions for embeddability are stricter than those for changeability. We have only to check the changeability of a pattern when there are no consecutive repeated PM or PF patterns. However, it is necessary to check if a pattern is embeddable when a number of PM or PF patterns repeat. For this purpose, the current PM pattern is intentionally changed into PF, or PF into PM, to see whether the changeability condition of the previous pattern is kept. One bit of data can be embedded only into an embeddable pattern.
Changeability ensures that after substitution of the current pattern, the change should not generate a new PF or PM, nor should it destroy either a PF or a PM from any class 3 or 4 patterns in the neighboring range. Turning changeable patterns into unchangeable ones, or vice versa, can also cause misinterpretation at a decoder. The embeddability condition ensures that the condition of changeability will not change after a substitution.
Ho and others
[20]
used a tuple, (
x_{i}
,
y_{i}
), to record the
i
th PF pattern, PF
_{i}
, where
x_{i}
and
y_{i}
are its coordinates. This technique needs 18 bits to encode one tuple for a 512 × 512 image, which is not efficient. In this paper, the positions of PF pixels are rearranged into a one-dimensional array, and its run-length between PF patterns is recorded to reduce the size of a location map.
In the embedding procedure, the difference-value matrix is first scanned to get the pattern pair to embed data. In this process, the PM-PF pair is identified based on the population of each pattern. Side information should be sent to a decoder for correct decoding. This information will be hidden in a specific area in the image using bit replacement. The payload consists of the original bit stream replaced with side information, a location map, and the actual secret bits. Side information includes the PM and PF patterns, number of PF patterns, number of secret bits, and the number of bits used for run-length coding for the PF patterns.
A decoder first extracts the side information from a specific region. Next, the decoder constructs a CM to see whether a pattern is changeable and embeddable. The first part of the decoded message is used to recover the replaced pixel values with the original ones. The rest of the decoded message contains the location map and secret message.
Cover images used in experiments: (a) Lena (512×512), (b) Boat (512×512), (c) Mickey (500×370), (d) Cartoon (371×450), (e) English (560×273), (f) Chinese (560×273), and (g) Handwriting (605×378).

Figure 8
shows a comparison of results in terms of embedding capacity based on the number of available flippable pixels. Note that the original PS method can hide 6,251 bits since there are 6,233 PMs and 18 PFs in the Mickey image. However, since not all patterns are changeable or embeddable, the number of flippable pixels is a little smaller than the number of PM and PF patterns. Note that the proposed method can flip only 6,191 patterns due to the changeability and embeddability conditions when the pair
P
_{0100}
and
P
_{0111}
is used, even though there are 6,715 patterns. Thus, in this case, the proposed method can also use the pair
P
_{1000}
and
P
_{1110}
, as in the original PS method. Thus, it is shown that the proposed method can always hide more bits than the original PS method.
Figure 8
shows the proposed method obtains higher capacity than the original PS method. There are mainly two reasons for this. The first is that the original PS method can use only four (PF, PM) pairs including <
P
_{0001}
,
P
_{0111}
>, <
P
_{1000}
,
P
_{1110}
>, <
P
_{0011}
,
P
_{1111}
>, and <
P
_{1100}
,
P
_{1111}
>. Thus, these pairs may exclude the best pair for some images. In the proposed method, any pair can be used. The second reason is that the run-length-based approach uses fewer bits than the coordinate-based method; moreover, the location map can be contracted. The run-length coding for the location map can increase the capacity and also decrease the distortion.
Table 2
shows the longest run-length requiring at most 11 bits.
Comparison results on number of flippable pixels.
Figure 9
compares the original and proposed PS methods in terms of visual quality. It shows that the original PS method produces fuzzier images than the proposed PS method.
Stego images by PS, (a) and (c), and proposed method, (b) and (d).
In
Figs. 10
and
11
, the PS method improved by
[23]
is labelled as “Optimal method,” our generalized PS is labelled as “Proposed,” and our method improved by
[23]
is labelled as “Proposed +.” In the Lena and Boat images in
Fig. 10
, the original PS cannot hide any data. Since the size of the location map is larger than the hiding capacity, there is no performance line for this PS method in
Fig. 10
. In the English and Chinese images, the proposed method is noticeably superior to the PS method.
Comparison of PSNR for (a) Lena (512 × 512) and (b) Boat (512 × 512).
Comparison of PSNR for (a) English (273 × 560) and (b) Chinese (513 × 262).
This work was supported by the Technology Innovation Program of the Ministry of Trade, Industry & Energy, Rep. of Korea (No. 10050653, Research Standardization Project for Multimedia Integrity Verification via Reversible Data Hiding Technique), Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT & Future Planning (No. 2013R1A1A1013410), and the grant from the National Natural Science Foundation of China (No. 61170207).
kevindong333@hotmail.com
Keming Dong received his BS degree in computer science from the Computer Science and Technology Department, Harbin Institute of Technology, China, in 2008. He joined Multimedia Security Lab., Center of Information Security and Technology, Korea University, Seoul, Rep. of Korea, in 2008, where he is currently pursuing his PhD degree in computer science. His research interests include multimedia security, data hiding, and machine learning.
Corresponding Author khj-@korea.ac.kr
Hyoung Joong Kim received his BS, MS, and PhD degrees in electrical engineering from Seoul National University, Rep. of Korea, in 1978, 1986, and 1989, respectively. From 1989 to 2006, he worked for the Department of Control and Instrumentation Engineering, Kangwon National University, Chuncheon, Seoul, Rep. of Korea. Since 2006, he has been with the Center of Information Security, Korea University, Seoul, Rep. of Korea, where he is now a professor. His research interests include parallel and distributed computing; multimedia computing; and multimedia security.
ciechoi@sungkyul.ac.kr
Yong Soo Choi received his BS, MS, and PhD degrees in computer science from the Department of Instrumentation and Control Engineering, Kangwon National University, Chuncheon, Rep. of Korea, in 1998, 2000, and 2006, respectively. From 2006 to 2007, he was a research professor with the Center for Technology Fusion in Construction, Yonsei University, Seoul, Rep. of Korea. From 2007 to 2013, he was a research professor with the Brain Korea 21 of Ubiquitous Information Security, Korea University, Seoul, Rep. of Korea. Since 2013, he has been an assistant professor of the Division of Liberal Arts and Teaching, Sungkyul University, Ansan, Rep. of Korea. He was a Delegate of Korea for ISO/IEC JTC1/SC29. He is a member of the IEEK Computer Society and also has been an Editor in Chief of Journal of the Institute of Electronics Engineers of Korea, the Section of Computer and Information. His research interests include multimedia signal processing, digital watermarking, steganography, image forensics and multimedia hashing.
joos@etri.re.kr
Sang Hyun Joo received his BS and MS degrees in computer science from Dongguk University, Seoul, Rep. of Korea, in 1989 and 1994, respectively. He received his PhD degree in computer science, from Niigata University, Japan, in 1999. From 1994 to 1996, he worked as a research engineer for KaiTech, Seoul, Rep. of Korea. From 1999 to 2001, he worked as a research associate at Niigata University. Since then, he joined ETRI, where he is now a Director in Mobile Content Research Lab. Since 2012, he has worked for MPEG-21 UD (ISO/IEC 21000-22) as both a chairman and an editor. His research interests include media context and control, user description, visual communication technologies.
cbh@etri.re.kr
Byung Ho Chung received his BS, MS, and PhD degrees in computer science from Chungnam National University, Daejeon, Rep. of Korea, in 1988, 2000, and 2005, respectively. From 1988 to 2000, he worked for the Agency for Defense Development, Daejeon, Rep. of Korea, as a research engineer. Since 2000, he has been with ETRI, where he is currently a leader with the ICT Convergence Security Lab. His current research interests include trusted wireless IoT gateways; software-defined cloud security; multimedia-contents analysis and filtering for security; and safety-critical security for embedded devices.

I. Introduction

Digital data hiding techniques hide data into digital files and have been used for copyright protection, covert communications, tamper detection, and authentication of digital property. There are many watermarking techniques for color and gray-scale images
[1]
–
[6]
. However, these techniques cannot be used with binary images. Binary images have only one signal bit in every pixel; therefore, this makes binary image watermarking very challenging.
There are two kinds of data hiding methods for binary images — lossy watermarking and lossless watermarking (also known as reversible watermarking). In the early development stages of binary image watermarking, most binary watermarking methods employed the method of lossy watermarking.
Chen and others
[7]
divided an image into disjoint blocks and then embeded a message by flipping one bit (that is, binary pixel value) in every block to compute
II. PS Method

In the PS method, the
PPT Slide

Lager Image

Binary bit pattern and corresponding possible substitutable patterns.

Difference-value pattern | Substitutable patterns |
---|---|

_{0001} | _{0010}, _{0111}, _{1101} |

_{0010} | _{0001}, _{0100}, _{1110} |

_{0011} | _{0000}, _{0101}, _{1111} |

_{0100} | _{0010}, _{0111}, _{1000} |

_{0101} | _{0011}, _{0110}, _{1001} |

_{0110} | _{0000}, _{0101}, _{1010} |

_{0111} | _{0001}, _{0100}, _{1011} |

_{1000} | _{0100}, _{1011}, _{1110} |

_{1001} | _{1000}, _{1010}, _{1111} |

_{1010} | _{0110}, _{1001}, _{1100} |

_{1011} | _{1000}, _{0111}, _{1101} |

_{1100} | _{0000}, _{1010}, _{1111} |

_{1101} | _{0001}, _{0111}, _{1101} |

_{1110} | _{0010}, _{0111}, _{1101} |

_{1111} | _{0010}, _{0111}, _{1101} |

- ■ The PM and PF elements that make up a pattern pair must come from the same pattern set.
- ■ A PS is to achieve a Hamming distance of “1” between each set of four bits between the original and watermarked images.

PPT Slide

Lager Image

- When the PM and PF overlap, take PF as the hidden pattern.
- If the numeral “1” occurs five times consecutively, then “11111” is deemed an unacceptable hiding place.

III. New PS Method

The basic algorithm of the proposed method is quite similar to that featured in the work of Ho and others
[20]
. In this paper, two important concepts are considered —
PPT Slide

Lager Image

- ■ Class 0: those that form a pattern not yet processed or that is waiting to be processed.
- ■ Class 1: the proposed pattern containing neither PM nor PF.
- ■ Class 2: the processed pattern of PM or PF, but not possible to embed data.
- ■ Class 3: the processed pattern of PF and has been used to embed data.
- ■ Class 4: the processed pattern of PM and has been used to embed data.

PPT Slide

Lager Image

PPT Slide

Lager Image

- ■ The pattern should be PF or PM.
- ■ After flipping the current pattern, any class 1 pattern in a neighboring range should remain as a class 1 pattern; any class 3 pattern should remain as a PF; and any class 4 pattern should remain as a PM.

PPT Slide

Lager Image

- ■ The pattern should be changeable.
- ■ After flipping or substituting the current pattern, the changeability of any PF/PM pattern of relative-range pixels should not change, except class 0.

IV. Experimental Results

The main purpose of this paper is to generalize the original PS method. Experiments show that the generalization is perfect; that is, any pattern pair can be used. The performance comparison between the proposed scheme, the PS method (overlapping case), and other approaches
[19]
,
[22]
–
[23]
is carried out in this section. The host images are shown in
Fig. 7
, where the “Lena” and “Boat” images are converted to binary images; the “Mickey” and “Cartoon” images, which are downloaded from the Internet for research purposes, are binary; and the rest of them are documents. These three image types represent most of the binary images that exist in the world today.
PPT Slide

Lager Image

- 1. Comparison with PS

To implement cyclic embedding and solve the uneven embedding problem, a HG
[20]
is used. For example, if HG = 2, then the hiding places are the first bit, the third bit, the fifth bit, and so on. To obtain a good visual performance, HG should be bigger than a given threshold; since, in this way, any distortion can be spread over the entire image. With this in mind, we used HG = 23 throughout our experiments.
Table 2
shows the PMs and PFs used by the original PS method
[20]
and proposed PS method. It shows that the proposed method can always choose the best PM-PF pairs to embed data.
Comparison of original and proposed PS methods with HG value of 23.

Original PS method | Proposed PS method | ||||||||
---|---|---|---|---|---|---|---|---|---|

PF | PM | # of PFs | # of PMs | PF | PM | # of PFs | # of PMs | RL bits | |

Mickey | _{1110} | _{1000} | 18 | 6,233 | _{0111} | _{0100} | 18 | 6,697 | 11 |

Body | _{0111} | _{0001} | 4 | 5,959 | _{0111} | _{0100} | 4 | 6,644 | 11 |

English | _{1110} | _{1000} | 82 | 6,188 | _{1111} | _{1001} | 5 | 4,998 | 11 |

_{0111} | _{0100} | 82 | 10,536 | 10 | |||||

Chinese | _{1110} | _{1000} | 19 | 6,134 | _{1111} | _{1001} | 0 | 3,885 | N/A |

_{0111} | _{0100} | 19 | 9,285 | 11 | |||||

Handwriting | _{0111} | _{0001} | 23 | 11,296 | _{1101} | _{0001} | 19 | 11,296 | 11 |

_{0111} | _{0100} | 23 | 12,124 | 11 | |||||

Lena | _{0111} | _{0001} | 586 | 7,673 | _{1101} | _{0001} | 496 | 7,673 | 7 |

Boat | _{0111} | _{0001} | 697 | 8,685 | _{1101} | _{0001} | 428 | 8,685 | 8 |

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- 2. Comparison with Other Approaches

Figures 10
and
11
also compare the performances of the PWLC
[19]
, run-length
[22]
, and optimal
[23]
methods. The run-length method cannot embed any data into Lena and Boat, because the size of the location map is bigger than the hiding capacity. Hence, there is no performance line for the run-length method in
Fig. 10
. In the English and Chinese images, the proposed method can achieve better performance than the run-length method. Since the location map of the run-length method cannot be compressed well, the performance is not good.
The PWLC method only embeds data into the boundary. It has to flip two pixels for 1 bit embedding, so the capacity performance as well as the distortion is worse than those for the proposed method.
The optimal method can be applied to any reversible watermarking method for binary covers to achieve better performance.
Figures 10
and
11
show that the proposed method can achieve higher performance than the original PS method, and the proposed method with
[23]
’s improvement can achieve higher performance than the PS with
[23]
’s improvement.
V. Conclusion

In this paper, the original PS method is extended to include all possible pattern pairs by proposing the concepts of changeable and embeddable patterns, and a class map is virtually constructed to identify such patterns. To reduce the size of the location map (that is, the position information of all PF patterns), the run-length information is used. Experiments show that the proposed method works well with any kind of PM-PF pairs and produces better results compared with the original PS in terms of embedding capacity and visual quality.
BIO

Tian J.
2003
“Reversible Data Embedding Using a Difference Expansion,”
IEEE Trans. Circuits Syst. Video Technol.
13
(8)
890 -
896
** DOI : 10.1109/TCSVT.2003.815962**

Ni Z.
2006
“Reversible Data Hiding,”
IEEE Trans. Circuits Syst. Video Technol.
16
(3)
354 -
362
** DOI : 10.1109/TCSVT.2006.869964**

Kim H.J.
2008
“A Novel Difference Expansion Transform for Reversible Data Embedding,”
IEEE Trans. Inf. Forensics Security
3
(3)
456 -
465
** DOI : 10.1109/TIFS.2008.924600**

Sachnev V.
2009
“Reversible Watermark Algorithm Using Sorting and Prediction,”
IEEE Trans. Circuits Syst. Video Technol.
19
(7)
989 -
999
** DOI : 10.1109/TCSVT.2009.2020257**

Yang C.-Y.
,
Hu W.-C.
2011
“High-Performance Reversible Data Hiding with Overflow/Underflow Avoidance,”
ETRI J.
33
(4)
580 -
588
** DOI : 10.4218/etrij.11.0110.0534**

Kang S.
,
Hwang H.J.
,
Kim H.J.
2012
“Reversible Watermark Using an Accurate Predictor and Sorter Based on Payload Balancing,”
ETRI J.
34
(3)
410 -
420
** DOI : 10.4218/etrij.12.0111.0075**

Pan H.-K.
,
Chen Y.-Y.
,
Tseng Y.-C.
“A Secure Data Hiding Scheme for Two-Color Images,”
IEEE Symp. Comput. Commun.
Antibes, France
July 4-6, 2000
750 -
755

Tseng Y.-C.
,
Pan H.-K.
2002
“Data Hiding in 2-Color Images,”
IEEE Trans. Comput.
51
(7)
873 -
878
** DOI : 10.1109/TC.2002.1017706**

Wu M.
,
Tang E.
,
Lin B.
“Data Hiding in Digital Binary Image,”
IEEE Int. Conf. Multimedia Expo
New York, USA
Aug. 1-3, 2000
393 -
396

Wu M.
2001
“Multimedia Data Hiding,” Ph.D. dissertation
Dept. Electr. Eng., Princeton Univ.
Princeton, NJ, USA

Wu M.
,
Liu B.
2004
“Data Hiding in Binary Images for Authentication and Annotation,”
IEEE Trans. Multimedia
6
(4)
528 -
538
** DOI : 10.1109/TMM.2004.830814**

Yang H.
,
Kot A.C.
“Data Hiding for Text Document Image Authentication by Connectivity-Preserving,”
Philadelphia, PA, USA
IEEE Int. Conf. Acoust., Speech, Signal Process.
Mar. 18-23, 2005
2
505 -
508

Yang H.
,
Kot A.C.
2007
“Pattern-Based Data Hiding for Binary Image Authentication by Connectivity-Preserving,”
IEEE Trans. Multimedia
9
(3)
475 -
486
** DOI : 10.1109/TMM.2006.887990**

Yang H.
,
Kot A.C.
2006
“Binary Image Authentication with Tampering Localization by Embedding Cryptographic Signature and Block Identifier,”
IEEE Signal Process. Lett.
13
(12)
741 -
744
** DOI : 10.1109/LSP.2006.879829**

Lee Y.
,
Kim H.
,
Park Y.
2009
“A New Data Hiding Scheme for Binary Image Authentication with Small Image Distortion,”
Inf. Sci.
179
(22)
3866 -
3884
** DOI : 10.1016/j.ins.2009.07.014**

Cheng J.
,
Kot A.C.
2007
“Objective Distortion Measure for Binary Text Image Based on Edge Line Segment Similarity,”
IEEE Trans. Image Process.
16
(6)
1691 -
1695
** DOI : 10.1109/TIP.2007.896619**

Tzeng C.-H.
,
Tsai W.-H.
2003
“A New Approach to Authentication of Binary Images for Multimedia Communication with Distortion Reduction and Security Enhancement,”
IEEE Commun. Lett.
7
(9)
443 -
445
** DOI : 10.1109/LCOMM.2003.815656**

Yang H.
,
Kot A.C.
,
Rahardja S.
2008
“Orthogonal Data Embedding for Binary Images in Morphological Transform Domain: A High-Capacity Approach,”
IEEE Trans. Multimedia
10
(3)
339 -
351
** DOI : 10.1109/TMM.2008.917404**

Tsai C.-L.
2005
“Reversible Data Hiding and Lossless Reconstruction of Binary Images Using Pair-Wise Logical Computation Mechanism,”
Pattern Recogn.
38
(11)
1993 -
2006
** DOI : 10.1016/j.patcog.2005.03.001**

Ho Y.-A.
2009
“High-Capacity Reversible Data Hiding in Binary Images Using Pattern Substitution,”
Comput. Standards Interfaces
31
(4)
787 -
794
** DOI : 10.1016/j.csi.2008.09.014**

Robertson G.R.
,
Aburdene M.F.
,
Kozick R.J.
1996
“Differential Block Coding of Bilevel Images,”
IEEE Trans. Image Process.
5
(9)
1368 -
1370
** DOI : 10.1109/83.535849**

Dong K.
,
Kim H.-J.
“An Efficient Pattern Substitution Watermarking Method for Binary Images,”
Int. Workshop Digital Watermarking
Seoul, Rep. of Korea
Oct. 1-3, 2010
6526
181 -
188

Xuan G.
“Reversible Binary Image Data Hiding by Run-Length Histogram Modification,”
Int. Conf. Pattern Recogn., Tampa
FL, USA
Dec. 8-11, 2008
1 -
4

Zhang W.M.
,
Chen B.
,
Yu N.H.
2012
“Improving Various Reversible Data Hiding Schemes via Optimal Codes for Binary Covers,”
IEEE Trans. Image Process.
21
(6)
2991 -
3003
** DOI : 10.1109/TIP.2012.2187667**

Zhang W.M.
,
Chen B.
,
Yu N.H.
“Capacity-Approaching Codes for Reversible Watermarking,”
Int. Conf. Inf. Hiding
Prague, Czech Republic
May 18-20, 2011
255 -
269

Citing 'Reversible Binary Image Watermarking Method Using Overlapping Pattern Substitution
'

@article{ HJTODO_2015_v37n5_990}
,title={Reversible Binary Image Watermarking Method Using Overlapping Pattern Substitution}
,volume={5}
, url={http://dx.doi.org/10.4218/etrij.15.0114.1058}, DOI={10.4218/etrij.15.0114.1058}
, number= {5}
, journal={ETRI Journal}
, publisher={Electronics and Telecommunications Research Institute}
, author={Dong, Keming
and
Kim, Hyoung Joong
and
Choi, Yong Soo
and
Joo, Sang Hyun
and
Chung, Byung Ho}
, year={2015}
, month={Oct}