当前位置:首页 >> 能源/化工 >>

A lossless data hiding scheme based on three-pixel block differences


Pattern Recognition 41 (2008) 1415 – 1425 www.elsevier.com/locate/pr

A lossless data hiding scheme based on three-pixel block differences
Ching-Chiuan Lin ? , Nien-Lin Hsueh

r />Department of Information Engineering and Computer Science, Feng Chia University, Taichung 40724, Taiwan, ROC Received 19 October 2006; received in revised form 2 September 2007; accepted 6 September 2007

Abstract This paper proposes a data hiding scheme that losslessly embeds a message into a cover image using the two differences—between the ?rst and the second pixel as well as between the second and the third pixel—in a three-pixel block. In the cover image, an absolute difference between a pair of pixels is selected to embed the message if the number of pixel pairs with the difference in the image is the largest. To embed a bit “1” or “0”, the selected difference is increased by 1 or left unchanged, respectively. In the best case, a three-pixel block can embed two bits “11” and only the central pixel needs to be increased or decreased by 1. The average payload capacity among the test images can be up to 2.08 bits per pixel (bpp). 2007 Elsevier Ltd. All rights reserved.
Keywords: Lossless data hiding; Reversible data hiding; Block difference; Steganography

1. Introduction The Internet allows users to exchange information without the limitations of time and location. Unauthorized persons can easily obtain secret data if appropriate precautions are not taken. Although encrypting a message before transmitting it on the Internet may provide a safe way for secret communication, encryption systems, such as data encryption standard (DES) [1] and RSA [2], encrypt a message by transforming it into a meaningless form, which may alert interceptors. Data hiding is a technique that imperceptibly hides secret data into cover media, such as digital images, videos, audios, etc. The cover medium is only slightly modi?ed, so these changes do not arouse suspicion in potential interceptors who might then notice the secret data. A drawback of this method is that the cover media will be injured and cannot be recovered if the restoring information is not provided. However, some applications, such as for military and medical purposes, require the recovery of the original cover medium.
? Corresponding author. Department of Information Management, 100 Chiao Kwang Road, Situn District, Taichung 40721, Taiwan, ROC. Tel.: +886 4 27016855x2133; fax: +886 4 27075420. E-mail addresses: cclin@ocit.edu.tw (C.-C. Lin), nlhsueh@fcu.edu.tw (N.-L. Hsueh).

Recently, many lossless or reversible data hiding techniques were proposed to provide solutions for losslessly restoring the original cover medium [3–13]. Fridrich et al. [6,7] compressed the least signi?cant bit (LSB) plane to obtain extra space for embedding secret data. Celik et al. [8,9] improved Fridrich et al.’s scheme and proposed the generalized-LSB (G-LSB) scheme by compressing the quantization residuals of pixels to obtain extra space for embedding a message. In the above two schemes, the payload capacity is highly related to the compressed results. Tian [10] used a technique of expanding the difference between two neighboring pixels to ?nd redundant space for embedding a message. In his scheme, a large location map is required to determine whether a pair of pixels embeds a message. Alattar [11] used the difference expansion of a vector to obtain more embedding space. Exploiting Tian’s scheme of difference expansion, Chang and Lu [12] calculated the difference between a pixel and the mean value of its neighboring pixels to embed a message. Although the hiding ability was improved, a large location map was still required in both Alattar’s and Chang and Lu’s schemes. Ni et al. [13] proposed a novel reversible data hiding algorithm based on shifting an image histogram. The maximum point of the histogram is selected to embed a message. When embedding a message into the image, the pixel value at the maximum point is altered by 1 or left unchanged if the message bit is “1” or “0”, respectively. However, few

0031-3203/$30.00 2007 Elsevier Ltd. All rights reserved. doi:10.1016/j.patcog.2007.09.005

1416

C.-C. Lin, N.-L. Hsueh / Pattern Recognition 41 (2008) 1415 – 1425

images contain a large number of pixels with equal pixel values, so the embedding capacity of Ni et al.’s algorithm is small. In this paper, we enhance Ni et al.’s algorithm [13] using the two differences—between the ?rst and the second pixel as well as between the second and the third pixel—in a three-pixel block to improve the embedding performance. In the best case, a three-pixel block can embed two message bits and at most only one pixel needs to be increased or decreased by 1. Experimental results show that the image quality and the payload capacity of the stego-image are dramatically improved. The remainder of this paper is organized as follows. In Section 2, the proposed scheme is described. The experimental results are illustrated in Section 3. In Section 4, we discuss the factors, in the proposed scheme, that can improve the image quality and the payload capacity of the stego-image. Finally, conclusions are given. 2. The proposed scheme In the proposed scheme, a three-pixel block in an image contains two absolute differences—the difference between pixels one and two, and the difference between pixels two and three. Such a difference is called block difference. For simplicity, in this paper, difference and block difference are interchangeable. Fig. 1 illustrates an overview of the proposed scheme in which an image is divided into non-overlapping three-pixel blocks, where the maximum and minimum allowable pixel values are 255 and 0, respectively. Let g(d) be the number of pixel pairs with absolute difference equal to d, where 0 d 253 and pixel pairs in the block which contains a pixel value equal to 0 or 255 are not considered when calculating g(d). Before embedding a message, the proposed scheme selects a pair of differences M and m such that g(M) g(M ) and g(m) g(m ) for all 0 M , m 253. Let (bi0 , bi1 , bi2 ) denote a block i with pixel values equal to bi0 , bi1 , and bi2 , and max(bi0 , bi1 , bi2 ) and min(bi0 , bi1 , bi2 ) denote the maximum and minimum pixel values in the block, respectively. First, blocks satisfying the following two conditions are selected: (1) 1 bi0 , bi1 , bi2 254; (2) min(bi0 , bi1 , bi2 ) = 1 or max(bi0 , bi1 , bi2 ) = 254. For each selected block i, the sender performs the following actions: (1) increase di0 by 1 if M + 1 di0 m ? 1, and increase di1 by 1 if M + 1 di1 m ? 1, where di0 = |bi0 ? bi1 | and di1 = |bi1 ? bi2 |; (2) embed a message into block i if di0 = M or di1 = M; (3) after performing actions (1) and (2), record the index of block i as overhead information if min(bi0 , bi1 , bi2 ) = 0 or max(bi0 , bi1 , bi2 ) = 255. For example, if M = 1 and m = 20, then blocks (2, 1, 2), (253, 254, 240), and (246, 243, 254) are selected in this step. The resulting blocks will be: (2, 0, 2) if it embeds two bits “11”, (253, 254, 239) if it embeds a bit “0”, and (246, 242, 254). Note that the results of block (246, 243, 254) are not determined by the embedded message, since it cannot embed a message. On the other hand, blocks (0, 3, 5) and (3, 4, 6) are not selected in this step. In this example, the index of resulting block (2, 0, 2) will be recorded as overhead information. Note that block (2, 0, 2) embeds two bits “11” and only the central pixel is modi?ed by 1.

Then, the sender scans the image again and performs the following actions for each block i with 2 bi0 , bi1 , bi2 253: (1) increase di0 by 1 if M + 1 di0 m ? 1, and increase di1 by 1 if M + 1 di1 m ? 1; (2) embed the overhead information and the residual message into block i if di0 = M or di1 = M. In the above example, block (3, 4, 6) will become (3, 4, 7) if it embeds a bit “0”. Obviously, the resulting blocks (2, 0, 2), (253, 254, 239), and (246, 242, 254) are not considered in this step. Fig. 1(a) shows the two steps in the embedding process described above. Given M and m, for each block i with 1 bi0 , bi1 , bi2 254, the receiver performs the following actions: (1) extract the overhead information or a message if di0 ∈ {M, M + 1} or di1 ∈ {M, M + 1}; (2) decrease di0 by 1 if M + 2 di0 m, and decrease di1 by 1 if M + 2 di1 m. Then, the receiver extracts the remaining message and recovers original blocks from the blocks with block indexes recorded in the overhead information extracted in the above extraction process. Fig. 1(b) shows the two steps in the extraction process described above. In the above example, two bits “0” and “0” are extracted from blocks (253, 254, 239) and (3, 4, 7), respectively, and blocks (253, 254, 239), (3, 4, 7), and (246, 242, 254) are recovered to (253, 254, 240), (3, 4, 6), and (246, 243, 254), respectively. More messages and overhead information are also extracted. From the extracted overhead information, for example, the receiver knows that block (2, 0, 2) embeds a message “11” and should be recovered to (2, 1, 2) after the embedded message is extracted. On the other hand, block (0, 3, 5) remains unchanged and nothing is extracted from it, since the index of the block was not recorded in the overhead information. Finally, the embedded message is extracted and the original image is completely recovered.

2.1. Embedding process The embedding process is applied to embed a message into an h × w grayscale image I, which is divided into non-overlapping three-neighboring-pixel blocks. Let bj,k be the pixel value of the pixel in the jth row and the kth column in image I, where 0 bj,k 255, 0 j h ? 1, and 0 k w ? 1. Intuitively, three consecutive horizontal pixels (bu,3v+t , bu,3v+t+1 , bu,3v+t+2 ) are taken as one block, where 0 t 2, 0 u h ? 1, and 0 v (w ? t)/3 ? 1. They are called Type-0, Type-1, and Type-2 blocks if t = 0, 1, and 2, respectively. Similarly, three consecutive vertical pixels (b3u+t,v , b3u+t+1,v , b3u+t+2,v ) may also be taken as one block, where 0 t 2, 0 u (h ? t)/3 ? 1, and 0 v w ? 1. They are also called Type-0, Type-1, and Type-2 blocks if t = 0, t = 1, and t = 2, respectively. For simplicity, in this paper we use (bi0 , bi1 , bi2 ) to denote a block in image I, where bi0 , bi1 , and bi2 represent the pixel values of the ?rst, second, and third pixels in block i, respectively. If a block contains at least one pixel with pixel value equal to 0 or 255 (the minimum or maximum allowable value), this block is called a boundary block (BB). If we add 1 to or subtract 1 from the pixels in a block such that the block becomes a

C.-C. Lin, N.-L. Hsueh / Pattern Recognition 41 (2008) 1415 – 1425

1417

Cover image

Message bit string: 011010111…

Overhead information + residual message: 10101110…

Stego-image

Cover image

Remaining message: 10…

Message and overhead information: 01…

Stego-image

Fig. 1. An overview of the proposed embedding and extraction processes: (a) embedding process; (b) extraction process.

boundary block, the modi?ed block is called a fresh boundary block (FB). For example, if we add 1 to 254 in the block (240, 254, 234) such that it becomes (240, 255, 234), the resulting block is an FB. The embedding process is described as follows: (1) For t = 0 to 2, divide image I into non-overlapping horizontal Type-t (1 × 3) blocks and do steps 2 and 3. Then, go to step 4. (2) For each block i with 1 bi0 , bi1 , bi2 254, calculate di0 = |bi0 ? bi1 | and di1 = |bi1 ? bi2 |. Then, calculate g(d), the number of pixel pairs with absolute difference equal to d, where 0 d 253. Note that pixel pairs in the block which contains a pixel value equal to 0 or 255 are not considered when calculating g(d). (3) Find the maximum value g(M) and the minimum value g(m) calculated in step 2, where M and m are the differences at which g(M) and g(m) are the maximum and the minimum, respectively, and M < m. If more than one pair of M and m is found, select the one with the smallest value of |M ? m|, where 0 M, m 253. (4) For t = 0 to 2, divide image I into non-overlapping vertical Type-t (3 × 1) blocks and do steps 2 and 3. (5) Select the block orientation (BO, horizontal or vertical) and the block type (BT, Type-0, Type-1, or Type-2) such that the image has the largest g(M) in step 3 for dividing the image to embed the message. Record the block orientation (horizontal or vertical), the block type (Type-0, Type-1, or Type-2), M, and m as overhead information. The selected BO, BT, M, and m (called the Key of Four) constitute an embedding plane which can provide a payload capacity of g(M) bits.

(6) Let the blocks divided in step 5 be indexed starting with 0. Scan image I in the indexed order. Let ga (M) be the number of pixel pairs with difference equal to M and the blocks to which they belong satisfy the following two conditions: (1) 1 bi0 , bi1 , bi2 254; (2) max(bi0 , bi1 , bi2 ) = 254 or min(bi0 , bi1 , bi2 ) = 1. For each block i satisfying the above conditions (1) and (2), call the procedure embedding_procedure listed in Fig. 2 to embed the message. After invoking the embedding procedure, if max(bi0 , bi1 , bi2 ) = 255 or min(bi0 , bi1 , bi2 ) = 0, record block i as an FB in the overhead information. (7) If g(M) ? ga (M) < the size of the overhead information to be embedded, abort the embedding process. This means that the image cannot provide enough space to embed the message. If g(M)?ga (M) the size of space required for embedding both the overhead information and the residual message, mark this embedding plane as the last one. Scan image I again in the order as that in step 6. For each block i with 2 bi0 , bi1 , bi2 253, call the procedure embedding_procedure listed in Fig. 2 to ?rst embed the overhead information illustrated in Fig. 4, and then the residual message. (8) Go to step 1 until the message is completely embedded. (9) Send the stego-image and the Key of Four of the last embedding plane to the receiver. The procedures invoked in Fig. 2 are listed in Fig. 3. In Figs. 2, 3, and 5, two consecutive equal signs “ == ” denote equality and the single equal sign “ = ” denotes assignment. In Fig. 3, eb1 and eb2 denote the next two message (or overhead information) bits to be embedded. The actions will be performed if their respective conditions are satis?ed. For

1418

C.-C. Lin, N.-L. Hsueh / Pattern Recognition 41 (2008) 1415 – 1425

Procedure embedding_procedure: if di0 == M { if di1 == M call embed_2_bits; else { if M < di1 < m call embed_1_bit_and_increase_difference; else call embed_1_bit_and_leave_unchanged; } } else if M < di0 < m { if di1 == M call increase_difference_and_embed_1_bit; else { if M < di1 < m call increase_2_differences; else call increase_difference_and_leave_unchanged; } } else { if di1 == M call leave_unchanged_and_embed_1_bit; else { if M < di1 < m call leave_unchanged_and_increase_difference; else do nothing; } }
Fig. 2. Embedding procedure.

Procedure embed_2_bits: Conditions bi0 > bi1 > bi2 bi0 < bi1 <bi2 bi0 == bi1 == bi2 Actions bi0 = bi0 + eb1, bi2 = bi2 eb2 bi0 = bi0 eb1, bi2 = bi2 + eb2 if eb1 == 1 and eb2 == 1 bi1 = bi1 + 1 else bi0 = bi0 eb1, bi2 = bi2 + eb2 if eb1 == 1 and eb2 == 1 bi1 = bi1 + 1 else bi0 = bi0 eb1, bi2 = bi2 eb2 if eb1 == 1 and eb2 == 1 bi1 = bi1 1 else bi0 = bi0 + eb1, bi2 = bi2 + eb2 Actions bi0 = bi0 + eb1, bi2 = bi2 1 bi0 = bi0 eb1, bi2 = bi2 + 1 if eb1 == 1 bi1 = bi1 + 1 else bi2 = bi2 1 if eb1 == 1 bi1 = bi1 1 else bi2 = bi2 + 1

bi0 < bi1 > bi2

bi0 > bi1 < bi2

Procedure embed_1_bit_and_increase_difference: Conditions bi0 > bi1 > bi2 bi0 < bi1 < bi2 bi0 bi1 > bi2

bi0

bi1 < bi2

Procedure embed_1_bit_and_leave_unchanged: Conditions bi0 > bi1 bi0 bi1 Conditions bi0 > bi1 > bi2 bi0 < bi1 < bi2 bi0 < bi1 bi2 Actions bi0 = bi0 + eb1 bi0 = bi0 eb1 Actions bi0 = bi0 + 1, bi2 = bi2 eb1 bi0 = bi0 1, bi2 = bi2 + eb1 if eb1 == 1 bi1 = bi1 + 1 else bi0 = bi0 1 if eb1 == 1 bi1 = bi1 1 else bi0 = bi0 + 1

Procedure increase_difference_and_embed_1_bit:

example, in the procedure embed_2_bits, if bi0 > bi1 > bi2 then eb1 will be added to bi0 and eb2 will be subtracted from bi2 . The conditions which are not listed are inexistent. For example, the conditions bi0 = = bi1 > bi2 do not exist in the procedure embed_2_bits, since di0 = = di1 = = M in this case. In general, g(m) is equal to zero, since most blocks in an image are smooth and few differences are larger than 130 in our test images. If g(m) = 0, the indexes of blocks with differences equal to m should be saved in the overhead information. In addition, in step 3 we only consider M < m. If m < M and |M ?m| is the smallest in this step, the differences satisfying the conditions m < di0 < M or m < di1 < M will be decreased by 1 during the embedding process, and the differences satisfying the conditions m di0 < M or m di1 < M will be increased by 1 during the extraction process. Similarly, when embedding a bit “1” into block i, the differences satisfying the conditions di0 = M or di1 = M will be decreased by 1, instead of being increased by 1 as shown in Fig. 3. Moreover, the differences satisfying the condition di0 = M ? 1 or di1 = M ? 1 will be increased by 1 after a bit “1” is extracted. In this paper, for simplicity, neither g(m) = 0 nor m < M will be considered, since few images have the condition g(m) = 0 or m < M. The Key of Four of the last embedding plane is the key to extract the embedded message and restore the original cover image. It can be separately sent to the receiver or embedded into

bi0 > bi1

bi2

Procedure increase_2_differences: Conditions bi0 > bi1 > bi2 bi0 < bi1 < bi2 bi0 < bi1 > bi2 bi0 > bi1 < bi2 Actions bi0 = bi0 + 1, bi2 = bi2 1 bi0 = bi0 1, bi2 = bi2 + 1 bi1 = bi1 + 1 bi1 = bi1 1

Procedure increase_difference_and_leave_unchanged: Conditions bi0 > bi1 bi0 < bi1 Conditions bi1 > bi2 bi1 bi2 Conditions bi1 > bi2 bi1 < bi2 Actions bi0 = bi0 + 1 bi0 = bi0 1 Actions bi2 = bi2 eb1 bi2 = bi2 + eb1 Actions bi2 = bi2 1 bi2 = bi2 + 1

Procedure leave_unchanged_and_embed_1_bit:

Procedure leave_unchanged_and_increase_difference :

Fig. 3. Conditions and their respective actions of embedding procedures.

C.-C. Lin, N.-L. Hsueh / Pattern Recognition 41 (2008) 1415 – 1425

1419

#FBs

IFBs

load capacity (bits) that can be used to embed the IFBs, in the best case, can be calculated by r = ( ? x) × 2 ? log2 x ? 19.

#FBs

IFBs

BO

BT

M

m

The following condition must be satis?ed: x× r, i.e., x (2 ? log2 x ? 19)/( + 2) < 2 /( + 2). An approximate solution for the space required to save the #FBs is log2 (2 /( + 2)) bits. In a 512 × 512 grayscale image, for example, the #FBs and an IFB will occupy 14 and 17 bits, respectively. 2.3. Extraction process Whenever the Key of Four of the last embedding plane is given, the receiver can extract the embedded message from the stego-image and restore the original cover image using the extraction process described below. (1) Follow the BO and the BT to divide the stego-image into blocks. (2) Scan the stego-image block by block in the order the message was embedded. For each block i with 1 bi0 , bi1 , bi2 254, perform the actions in accordance with the conditions listed in Fig. 5. (3) After the respective actions have been completed, save the extracted message bits in the list List-1 if min(bi0 , bi1 , bi2 ) = 1 or max(bi0 , bi1 , bi2 ) = 254, and save the extracted message bits in the list List-2 if 2 bi0 , bi1 , bi2 253. List-1 contains a part of the message embedded in step 6 in Section 2.1 and List-2 contains the overhead information (List-2 ) and the message (List-2 ) embedded in step 7 in Section 2.1. (4) Decode the overhead information in List-2 according to the formats de?ned in Fig. 4. (5) For each FB, which is recorded in List-2 , perform the actions according to their respective conditions listed in Fig. 5 and save the message bits extracted in the list List-3. (6) According to the indexes of the blocks where the message bits are extracted, reorder the message bits saved in List1 and List-3 to form the list List-4 which is the message embedded in step 6 in Section 2.1. (7) Push the message in List-2 ?rst, then the message obtained in step 6 (List-4) onto a stack. (8) Go to step 1 until the message embedded in each embedding plane is completely extracted. (9) Pop the message pushed in step 7 off the stack to obtain the message embedded in the stego-image. 2.4. An embedding and extraction example Fig. 6 shows an embedding example in a middle plane using the overhead information formats illustrated in Fig. 4(b) for a 5 × 12 grayscale image which is divided into max(5 × 12/3 , 12 × 5/3 ) = 20 non-overlapping three-horizontal-

#FBs

IFBs

BO

BT

M

m

#EPs

Fig. 4. Overhead information formats in an embedding plane: (a) ?rst embedding plane; (b) middle embedding plane; (c) last embedding plane.

the LSBs of the pixels (for example, the ?rst several pixels), by simple LSB replacement, in the stego-image negotiated beforehand by both the sender and the receiver. If the latter is used, an embedding space of 19 bits (1/2/8/8 bits for BO/BT/M/m, respectively, as explained in Section 2.2) are needed to save the Key of Four of the last embedding plane. If one pixel embeds one bit, the last embedding plane should not include the 19 pixels used to embed the Key of Four. In addition, the 19 LSBs to be replaced by the Key of Four should be saved in the overhead information so that the cover image can be restored. For convenience, in this paper the method of separately sending the Key of Four is used to enable the receiver to extract the message and restore the cover image. 2.2. Overhead information formats A grayscale image I of h rows × w columns can be divided into at most = max(h × w/3 , w × h/3 ) non-overlapping three-pixel blocks. In this situation, at least = log2 bits are required to identify an index of FB (IFB). In addition, the number of embedding planes (#EPs), M, and m should be less than 256 for a grayscale image in which each pixel takes up eight bits, since we cannot increase or decrease a pixel value more than 255 times and the block difference is less than 256. We need 1 and 2 bits to save BO and BT, respectively, since BO is either 0 (horizontal) or 1 (vertical) and BT includes three different values (0/1/2 for Type-0/Type-1/Type-2, respectively). Therefore, the Key of Four of an embedding plane consumes 19 bits of payload capacity in total. Figs. 4(a)–(c) show the overhead information formats in the ?rst, middle, and last embedding planes, respectively. Each embedding plane embeds the number of FBs (#FBs) and the IFBs for itself. The middle and last embedding planes embed the Key of Four for their preceding embedding planes. The number of embedding planes of the stego-image is embedded in the last embedding plane. Again, for simplicity, in this paper the Key of Four of the last embedding plane is separately sent to the receiver. In the best case, the maximum payload capacity in an embedding plane is 2 = 2 × max(h × w/3 , w × h/3 ) bits. Let the maximum number of FBs that may be encountered in step 6 in Section 2.1 be x, so it will consume log2 x and x × bits to embed the #FBs and the IFBs, respectively, in an embedding plane. In step 7 in Section 2.1, the maximum remaining pay-

1420

C.-C. Lin, N.-L. Hsueh / Pattern Recognition 41 (2008) 1415 – 1425

Item 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

Conditions di0 == M and di1 == M di0 == M and di1 == M + 1 and bi1 > bi2 di0 == M and di1 == M + 1 and bi1 < bi2 di0 == M and M + 1 < di1 m and bi1 > bi2 di0 == M and M + 1 < di1 m and bi1 < bi2 di0 == M and (di1 < M or di1 > m) di0 == M + 1 and di1 == M and bi0 < bi1 di0 == M + 1 and di1 == M and bi0 > bi1 di0 == M + 1 and di1 == M + 1 and bi0 < bi1 < bi2 di0 == M + 1 and di1 == M + 1 and bi0 > bi1 > bi2 di0 == M + 1 and di1 == M + 1 and bi0 < bi1 > bi2 di0 == M + 1 and di1 == M + 1 and bi0 > bi1 < bi2 di0 == M + 1 and M + 1 < di1 m and bi0 > bi1 > bi2 di0 == M + 1 and M + 1 < di1 m and bi0 < bi1 < bi2 di0 == M + 1 and M + 1 < di1 m and bi0 < bi1 > bi2 di0 == M + 1 and M + 1 < di1 m and bi0 > bi1 < bi2 di0 == M + 1 and (di1 < M or di1 > m) and bi0 < bi1 di0 == M + 1 and (di1 < M or di1 > m) and bi0 > bi1 M + 1 < di0 m and di1 == M and bi0 > bi1 M + 1 < di0 m and di1 == M and bi0 < bi1 M + 1 < di0 m and di1 == M + 1 and bi0 > bi1 > bi2 M + 1 < di0 m and di1 == M + 1 and bi0 < bi1 < bi2 M + 1 < di0 m and di1 == M + 1 and bi0 < bi1 > bi2 M + 1 < di0 m and di1 == M + 1 and bi0 > bi1 < bi2 M + 1 < di0 m and M + 1 < di1 m and bi0 > bi1 > bi2 M + 1 < di0 m and M + 1 < di1 m and bi0 < bi1 < bi2 M + 1 < di0 m and M + 1 < di1 m and bi0 < bi1 > bi2 M + 1 < di0 m and M + 1 < di1 m and bi0 > bi1 < bi2 M + 1 < di0 m and (di1 < M or di1 > m) and bi0 < bi1 M + 1 < di0 m and (di1 < M or di1 > m) and bi0 > bi1 (di0 < M or di0 > m) and di1 == M (di0 < M or di0 > m) and di1 == M + 1 and bi1 < bi2 (di0 < M or di0 > m) and di1 == M + 1 and bi1 > bi2 (di0 < M or di0 > m) and M + 1 < di1 m and bi1 < bi2 (di0 < M or di0 > m) and M + 1 < di1 m and bi1 > bi2 (di0 < M or di0 > m) and (di1 < M or di1 > m)

Actions Extract “00” Extract “01”, bi2 = bi2 + 1 Extract “01”, bi2 = bi2 1 Extract “0”, bi2 = bi2 + 1 Extract “0”, bi2 = bi2 1 Extract “0” Extract “10”, bi0 = bi0 + 1 Extract “10”, bi0 = bi0 1 Extract “11”, bi0 = bi0 + 1, bi2 = bi2 1 Extract “11”, bi0 = bi0 1, bi2 = bi2 + 1 Extract “11”, bi1 = bi1 1 Extract “11”, bi1 = bi1 + 1 Extract “1”, bi0 = bi0 1, bi2 = bi2 + 1 Extract “1”, bi0 = bi0 + 1, bi2 = bi2 1 Extract “1”, bi1 = bi1 – 1 Extract “1”, bi1 = bi1 + 1 Extract “1”, bi0 = bi0 + 1 Extract “1”, bi0 = bi0 1 Extract “0”, bi0 = bi0 1 Extract “0”, bi0 = bi0 + 1 Extract “1”, bi0 = bi0 1, bi2 = bi2 + 1 Extract “1”, bi0 = bi0 + 1, bi2 = bi2 1 Extract “1”, bi1 = bi1 1 Extract “1”, bi1 = bi1 + 1 bi0 = bi0 1, bi2 = bi2 + 1 bi0 = bi0 + 1, bi2 = bi2 1 bi1 = bi1 1 bi1 = bi1 + 1 bi0 = bi0 + 1 bi0 = bi0 1 Extract “0” Extract “1”, bi2 = bi2 1 Extract “1”, bi2 = bi2 + 1 bi2 = bi2 1 bi2 = bi2 + 1 Do nothing

Fig. 5. Conditions and their respective actions for extracting a message.

pixel blocks. In this image, log2 20 = 5 bits are required to identify an index of a block and log2 ((2 × 20)/(5 + 2)) = 3 bits are used to save the number of FBs in an embedding plane. Here, we take 4 bits to embed each M and m for simplicity (in a practical case we need 8 bits to embed each M and m for a grayscale image in which each pixel takes up 8 bits). To select the block orientation and the block type with the largest g(M), we list the possible partitions of the image and their respective results as follows: (1) (2) (3) (4) (5) (6) 1 × 3 Type-0: M = 1, m = 5, g(M) = 23, and g(m) = 0, 1 × 3 Type-1: M = 1, m = 5, g(M) = 16, and g(m) = 0, 1 × 3 Type-2: M = 1, m = 5, g(M) = 14, and g(m) = 0, 3 × 1 Type-0: M = 1, m = 7, g(M) = 7, and g(m) = 0, 3 × 1 Type-1: M = 1, m = 5, g(M) = 8, and g(m) = 0, and 3 × 1 Type-2: M = 1, m = 7, g(M) = 7, and g(m) = 0.

As blocks (1, 0, 7), (2, 1, 0), and (0, 6, 5) are boundary blocks in partitions 1, 3, and 4, respectively. Therefore, they are not

considered as the blocks which can embed a message. Apparently, partition 1 has the largest g(M) and is, thus, selected to embed the message. Its overhead information BO = 0 (horizontal), BT = 0 (Type-0), M = 1, and m = 5 will be embedded in the next embedding plane. Note that g(M) is 23 instead of 24, since block 3 (1, 0, 7) is not considered when calculating g(d) in step 2 in Section 2.1. Assume that the message to be embedded is (0011)2 and the Key of Four of the preceding embedding plane is BO = 0, BT = 1, M = 1, and m = 3. The blocks are indexed as follows: block 0 is in the left-top corner, and blocks 1 and 4 are on the right of and below block 0, respectively, and so on. In step 6 in Section 2.1, the ?rst message bit “0” is embedded into block 1 (1, 3, 4) by changing it to (0, 3, 4). Block 13 (1, 5, 2) embeds nothing and is changed to (1, 6, 2), and the following two message bits “01” are embedded into block 14 (1, 2, 3) by changing it to (1, 2, 4). After embedding the ?rst message bit “0”, block 1 contains a pixel with pixel value equal to 0, so this block will be recorded as an FB. The number of FBs (=1,

C.-C. Lin, N.-L. Hsueh / Pattern Recognition 41 (2008) 1415 – 1425

1421

3 8 6 7 2

4 8 4 4 4

3 9 7 3 5

1 5 7 1 5

3 4 6 5 4

4 3 6 2 5

5 6 3 1 3

4 5 4 2 7

2 4 5 3 4

1 3 4 5 3

0 6 5 6 6

7 7 4 7 8

3 8 6 8 1

4 8 3 4 4

3 9 7 2 6

0 5 7 1 5

3 4 6 6 3

4 3 6 2 5

6 6 2 1 3

4 5 4 2 8

1 3 5 4 4

1 2 4 5 2

0 6 5 6 6

7 7 4 7 9

Fig. 6. An embedding and extraction example: (a) original image; (b) stego-image.

in List-1 and List-2, respectively. In List-2, the ?rst 19 bits (i.e., 001, 00001, 0, 01, 0001, 0011) are the overhead information (List-2 ) and the last bit (i.e., 1) is the residual message (List-2 ). After decoding the overhead information, the receiver knows that there is one FB (#FBs = (001)2 ) in the embedding plane and it is block 1 (IFB = (00001)2 ). The Key of Four of the preceding embedding plane—BO = 0, BT = 1, M = 1, and m = 3—is also extracted. Note that both block 1 (0, 3, 4) and block 3 (1, 0, 7) in the stego-image contain a pixel with pixel value equal to 0. In step 2 in Section 2.3, the receiver skips these two blocks because he/she cannot determine whether they are a BB or an FB. However, in step 4 in Section 2.3, after decoding the overhead information in List-2 , the FBs are determined and the receiver knows that blocks 1 and 3 are an FB and a BB, respectively. In step 5 in Section 2.3, given that block 1 (0, 3, 4) is an FB, a bit “0” is extracted and saved in List-3, since M + 1 < (d10 = |0 ? 3| = 3) m, (d11 = |3 ? 4| = 1) = M, and 0 < 3 (i.e., the conditions in item 20 in Fig. 5 are satis?ed). Then this block is restored to (1, 3, 4). According to the index of the block from which the message is extracted, the receiver reorders the message bits in List-1 (01) and List-3 (0) to obtain List-4 (001) which, then, concatenates the residual message bit (1) in List-2 to constitute the embedded message (0011)2 . 3. Experimental results In this section, we will show the performance of the proposed scheme by using eight 512 × 512 grayscale test images as cover images which vary from complex (Baboon) to smooth (Gradient, a computer generated image) as shown in Fig. 7. Each pixel of the test images takes up 8 bits. The pixel values of the ?rst two rows in Gradient are equal to zero and those of the third and fourth rows are equal to 1, etc. We utilized the peak signal to noise ratio (PSNR) to show the distortion of the stego-image. For an h × w grayscale image, the PSNR value is de?ned as follows: PSNR = 10 × log10 255 × 255 × h × w
h?1 i=0 w?1 j =0 (pi,j

bit string =001), the index of FB (=1, bit string =00001), BO (=0, bit string =0), BT (=1, bit string =01), M (=1, bit string =0001), and m (=3, bit string =0011) constitute the overhead information bit string 001, 00001, 0, 01, 0001, 0011 (where the commas are used to separate ?elds visually and, of course, are not embedded into the image) which will be embedded into blocks 0, 2, 4–7, 9–12, and 15–17 in step 7 in Section 2.1 ?rst, then the residual message bit “1” is embedded into the second pixel pair of block 17. The results of the embedded image are shown in Fig. 6(b) which can be used to embed a message in the next embedding plane. Given the Key of Four of the middle embedding plane—BO = 0 (block orientation is horizontal), BT = 0 (block type is Type-0), M = 1, and m = 5, the receiver follows the BO and the BT to divide the stego-image and scans it block by block in the order the message was embedded. In step 2 in Section 2.3, when scanning the image in Fig. 6(b), if 1 bi0 , bi1 , bi2 254, the receiver calculates the differences for block i to extract the message embedded in Fig. 6(b) and restore the original image in Fig. 6(a). Appropriate actions are performed in accordance with the respective conditions in Fig. 5. For example, two bits “00” are extracted from block 0 (3, 4, 3) since d00 =|3?4|=M and d01 =|4?3|=M, and a bit “1” is extracted from block 2 (6, 4, 1) which, then, is restored to (5, 4, 2), since (d20 =|6?4|=2)=M +1, M +1 < (d21 =|4?1|=3) m, and 6 > 4 > 1 (i.e., the conditions in item 13 in Fig. 5 are satis?ed). The message and the overhead information extracted in step 2 in Section 2.3 will be (0010000100100010100111)2 in which the underlined bits “01” (since they are extracted from block 14 (1, 2, 4) and the restored block (1, 2, 3) satis?es min(1, 2, 3) = 1) and the other bits (i.e., 00100001001000100111) will be saved

? qi,j )2

dB,

where pi,j and qi,j denote the pixel values in row i and column j of the cover image and the stego-image, respectively. In our experiments, a part of Lena image was taken as user’s message and embedded into each of the test images. Table 1 shows the maximum payload capacity, in bits and bpp, that the test images can offer using the proposed scheme. Pure payload capacity is the size of space that can be used to embed the user’s message, and the payload capacity of an image is the sum of the payload capacities of the embedding planes. For example, Airplane can offer up to 56 embedding planes and its payload capacity is 585,380 bits, which is equivalent to 2.23 bpp. When using the header formats illustrated in Fig. 4, the overhead information embedded in Airplane is equal to 585, 380 ? 563, 704 = 21, 676 bits. The average payload and pure payload capacities of the test images are 2.08

1422

C.-C. Lin, N.-L. Hsueh / Pattern Recognition 41 (2008) 1415 – 1425

a

b

c

d

e

f

g

h

Fig. 7. Test images: (a) Baboon; (b) Boat; (c) Lena; (d) Airplane; (e) Pepper; (f) Tiffany; (g) GoldHill; (h) Gradient.

Table 1 The performance of the proposed scheme
Image name PSNR Planes Payloada bits Baboon Boat Lena Airplane Pepper Tiffany GoldHill Gradient
a Average b Average

Pure payloadb bpp 1.29 2.04 1.96 2.23 2.19 1.68 1.91 3.31 bits 297,607 446,141 452,546 563,704 449,035 405,475 426,504 706,931 bpp 1.14 1.70 1.73 2.15 1.71 1.55 1.63 2.70

20.5 20.3 20.8 21.0 20.8 25.2 21.4 26.5 payload = 2.08 bpp. pure payload = 1.79 bpp.

57 62 58 56 59 34 53 33

339,308 535,301 513,983 585,380 574,850 441,674 501,546 867,554

and 1.79 bpp, respectively. The payload capacity of Baboon is 1.29 bpp, whereas Gradient has a payload capacity of up to 3.31 bpp. This implies that smooth images are good candidates to be used in the proposed scheme for losslessly embedding a message. Table 2 depicts the performance of the proposed scheme for PSNR 30 dB. The average payload and pure payload capacities of the test images for PSNR 30 dB can be up to 1.39 and 1.32 bpp, respectively. In Table 2, most of the test images have an overhead information size of less than 1,000 bits. To compare the performance between Ni et al.’s algorithm [13] and our scheme, we also implemented their algorithm. Fig. 8 shows Ni et al.’s and our histograms for Lena and Baboon. In the two images, most of the pixel values are between 30 and 230, and the numbers of pixels at the maximum points are less than 3000 in their histograms as shown in Figs. 8(a) and (c). However, in Fig. 8(b), the block differences are fo-

cused in between 0 and 25, and the number of differences at the maximum point in the ?rst embedding plane can be up to 32,339 in our histogram. This means that the payload capacity of the ?rst embedding plane of Lena will be less than 3,000 bits in Ni et al.’s algorithm and up to 32,339 bits in our scheme. The histogram for Baboon, as shown in Fig. 8(d), gives results similar to those of Lena. Fig. 9 shows a comparison between Ni et al.’s algorithm and our scheme in terms of the payload capacities and the PSNR values. Our payload capacities are much higher than Ni et al.’s in each embedding plane. In addition, our PSNR values are higher than Ni et al.’s after the sixth embedding plane. In the ?rst 20 embedding planes, Ni et al.’s algorithm encountered no saturation point, whereas our scheme encountered only 3 FBs. Fig. 9 indicates that the performance of our scheme is much better than that of Ni et al.’s algorithm, especially in the ?rst several embedding planes.

C.-C. Lin, N.-L. Hsueh / Pattern Recognition 41 (2008) 1415 – 1425
Table 2 The performance of the proposed scheme for PSNR
Image name PSNR

1423

30 dB Planes Payloada bits bpp 0.62 1.17 1.18 1.40 1.36 1.27 1.16 2.92 Pure payloadb bits 161,118 307,193 308,474 366,784 322,744 331,962 302,784 660,511 bpp 0.61 1.17 1.18 1.40 1.23 1.27 1.16 2.52

Baboon Boat Lena Airplane Pepper Tiffany GoldHill Gradient
a Average b Average

30.4 30.4 30.0 30.3 30.2 30.1 30.1 30.1 payload = 1.39 bpp. pure payload = 1.32 bpp.

17 19 20 19 20 19 20 21

162,544 307,937 309,166 367,392 356,450 332,570 303,629 764,817

Lena 3,000 Number of pixels 2,500 2,000 1,500 1,000 500 0 0 50 100 150 Pixel value Baboon 3,000 Number of pixels 2,500 2,000 1,500 1,000 500 0 0 50 100 150 Pixel value 200 250 Number of differences 15,000 12,000 9,000 6,000 3,000 0 0 20 200 250 Number of differences 35,000 30,000 25,000 20,000 15,000 10,000 5,000 0 0 20

Lena

40 60 80 Difference value Baboon

100

40 60 80 Difference value

100

Fig. 8. Comparison between Ni et al.’s and our histograms for Lena and Baboon: (a) Ni et al.’s histogram for Lena; (b) our histogram for Lena; (c) Ni et al.’s histogram for Baboon; (d) our histogram for Baboon.

4. Discussion The advantage of altering the block type of an image in an embedding plane is that the distortion of the image can be decreased, which can be shown in the following example. Fig. 10(a) is a 1 × 8 original cover image partitioned into horizontal Type-0 blocks. Suppose that M =1 and m=4. After embedding two bits “1” and “1” into blocks (3, 5, 6) and (9, 10, 13), respectively, the stego-image is as shown in Fig. 10(b). Then the image is partitioned into Type-1 blocks as shown in Fig. 10(c), in which M = 1 and m = 3 are assumed. Fig. 10(d) shows the stego-image after embedding two bits “1” and “0” into blocks

(5, 7, 8) and (10, 14, 13) in Fig. 10(c), respectively. From Fig. 10(d), we can see that b0,3 (=9) is equal to the pixel value in the original image in Fig. 10(a) after two modi?cations in the two embedding planes. Thus, the distortion of the cover image is reduced. The experimental results also show that the alteration of block type can reduce the decreases of both the PSNR values and the number of pixel pairs at the maximum point M. As a result, both image quality and payload capacity are improved. Moreover, the two pixels on the right of each row of a 512 × 512 grayscale cover image are also utilized. Another driving force of reducing the distortion of the cover image is described below. In the proposed scheme, a pair of

1424

C.-C. Lin, N.-L. Hsueh / Pattern Recognition 41 (2008) 1415 – 1425

40,000 35,000 Payload capacity (bits) 30,000 25,000 20,000 15,000 10,000 5,000 0 0 2 4 6 8 10 12 14 Embedding plane 16 18 20
Ni et al.'s payload capacity Our payload capacity Ni et al.'s PSNR Our PSNR

55 50 45 PSNR (dB) 4 40 35 30 25 20 15

Fig. 9. Comparison between Ni et al.’s algorithm and our scheme in terms of the payload capacities and the PSNR values for Lena.

3

5

6

9

10

13

13

13

4

3

6

2

6

3 2 5 7 8 10 14 13 13

4

1

3

5

1

2

5

7

8

10

14

13

4 13 3

3

4

4

2

4

4

3

3

5

3

2

4

7

9

10

14

13

13 6 4 7 6 3 7

Fig. 10. An example demonstrating the advantage of altering block types: (a) a cover image partitioned into horizontal Type-0 blocks; (b) the stego-image of (a); (c) the stego-image partitioned into horizontal Type-1 blocks; (d) the stego-image of (c).

4

6

3

4

7

3

pixels can embed at most one message bit in an embedding plane. Each pair of pixels in a block shares the central pixel. In general, if two differences in a block should be increased, two pixels need to be modi?ed. If we can reduce the number of pixels changed, we can reduce the distortion of the cover image. Fortunately, in some cases modifying only the central pixel can increase two differences in a block. This is a reason why the proposed scheme can reduce the distortion of the cover image. Fig. 11 illustrates the ideas of reducing the distortion of the cover image by reducing the number of pixels changed when using the proposed scheme to embed a message. Suppose that the maximum and minimum points are at M =1 and m=4, respectively. Fig. 11(a) shows that only the central pixel in the block is modi?ed to embed a bit “1” into a pair of pixels and increase the difference in another pair of pixels. When embedding two bits “11” into a block, only the central pixel will be modi?ed in the cases of Fig. 11(b). Fig. 11(c) shows two cases where only the central pixel in the block is modi?ed if the block cannot embed any message. To obtain a higher payload capacity, when dividing an image into blocks before embedding a message into an embed-

Fig. 11. Examples illustrating the ideas of reducing the modi?cations of pixels in a block: (a) examples of embedding a bit “1” and increasing a difference; (b) examples of embedding two bits “11”; (c) examples of increasing two differences.

ding plane, each combination of block orientation (horizontal or vertical) and block type (Type-0, Type-1, or Type-2) will be considered. The combination which can achieve the largest number of differences at the maximum point will be selected as the one to divide the image into blocks for the embedding plane. The selected block orientation and block type of the image are saved in the BO and BT ?elds of the next embedding plane, respectively. In each embedding plane (excluding the ?rst one), the two ?elds consume only three bits of payload capacity, but the payload capacity of an embedding plane can be increased by hundreds to thousands of bits. 5. Conclusions A lossless data hiding scheme was proposed in this paper. Experimental results have proven that the average payload and

C.-C. Lin, N.-L. Hsueh / Pattern Recognition 41 (2008) 1415 – 1425

1425

pure payload capacities of the test images can be up to 2.08 and 1.79 bpp, respectively. For PSNR 30 dB, the average payload and pure payload capacities can be up to 1.39 and 1.32 bpp, respectively, among the test images. The payload capacity of the proposed scheme is about six to ten times higher than that of Ni et al.’s algorithm. Therefore, the proposed scheme can provide a high payload capacity and better image quality for applications that losslessly embed a message in a cover image. In addition, our scheme can be applied to various images varying from complex to smooth as shown in the test images. References
[1] Data Encryption Standard (DES), National Bureau of Standards (U.S.), Federal Information Processing Standards Publication 46, National Technical Information Service, Spring?eld, VA, (1977). [2] R.L. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM 21 (2) (1978) 120–126. [3] C.L. Tsai, H.F. Chiang, K.C. Fan, C.D. Chung, Reversible data hiding and lossless reconstruction of binary images using pair-wise logical computation mechanism, Pattern Recognition 38 (11) (2005) 1993–2006. [4] L. Kamstra, H.J.A.M. Heijmans, Reversible data embedding into images using wavelet techniques and sorting, IEEE Trans. Image Process. 14 (12) (2005) 2082–2090.

[5] C.T. Li, Reversible watermarking scheme with image-independent embedding capacity, IEE Proc.-Vis. Image Signal Process. 152 (6) (2005) 779–785. [6] J. Fridrich, M. Goljan, R. Du, Invertible authentication, Proc. SPIE Security and Watermarking of Multimedia Contents, San Jose, CA, 2001 pp. 197–208. [7] J. Fridrich, M. Goljan, R. Du, Lossless data embedding—new paradigm in digital watermarking, EURASIP J. Appl. Signal Process. 2002 (2) (2002) 185–196. [8] M.U. Celik, G. Sharma, A.M. Tekalp, E. Saber, Lossless generalizedLSB data embedding, IEEE Trans. Image Process. 14 (2) (2005) 253–266. [9] M.U. Celik, G. Sharma, A.M. Tekalp, Lossless watermarking for image authentication: a new framework and an implementation, IEEE Trans. Image Process. 15 (4) (2006) 1042–1049. [10] J. Tian, Reversible data embedding using a difference expansion, IEEE Trans. Circuits Syst. Video Technol. 13 (8) (2003) 890–896. [11] A.M. Alattar, Reversible watermark using the difference expansion of a generalized integer transform, IEEE Trans. Image Process. 13 (8) (2004) 1147–1156. [12] C.C. Chang, T.C. Lu, A difference expansion oriented data hiding scheme for restoring the original host images, J. Syst. Software 79 (12) (2006) 1754–1766. [13] Z. Ni, Y.Q. Shi, N. Ansari, W. Su, Reversible data hiding, IEEE Trans. Circuits Syst. Video Technol. 16 (3) (2006) 354–362.

About the Author—CHING-CHIUAN LIN joined the Overseas Chinese Institute of Technology as a lecturer in the Department of Information Management since 1992. Currently, he is a Ph.D. candidate in the Department of Information Engineering and Computer Science, Feng Chia University, Taiwan. His research interests include image processing, data hiding, network computing, and software engineering. About the Author—NIEN-LIN HSUEH is an assistant professor in the Department of Information Engineering and Computer Science at Feng Chia University in Taiwan. His research interests include object-oriented methodologies, image processing, and software testing. He was the technology consultant in the CMMI-based process improvement project of Of?ce of Information Technology at Feng Chia University. He received his Ph.D. in Computer Science from National Central University in Taiwan.


相关文章:
2004年SCI收录信息学院
Block Coding Based on ICA Neural Networks A ...lossless image coding Formation of waveguide by ...Data Hiding with Video Independent Components A ...
Colorimageretrieval technique based on colorfeature...
Image Hiding Algorithms ... 暂无评价 9页 2....differences among adjacent pixels for imageretrieval...block, the scheme used “0” to represent the ...
更多相关标签: