A Blind Data Hiding Technique with Error Correction Abilities and a High Embedding Payload

Abstract

Least significant bit (LSB) embedding is a simple steganographic technique used in the spatial domain that involves replacing the LSB of each pixel in the cover work with the information bits being hidden to achieve information secrecy. However, considering the current prevalence of information theft and sabotage, the stego image produced using LSB embedding cannot prevent malicious illegal acts. Therefore, this study proposes a blind data hiding technique that combines block-coded modulation (BCM) codes with LSB embedding. The proposed method not only provides error correction capabilities to prevent errors during the extraction process, but also has a superior embedding payload. The peak signal noise ratio (PSNR) exceeds 40 dB by using our proposed method. Regarding the simulation results, the proposed method provides a superior PSNR compared to LSB embedding and a higher embedding payload than that offered by other steganographic techniques with error correction capabilities.

1

Introduction

Watermarking [1, 2, 3, 4, 5] and steganography [6, 7, 8, 9] are the two main information hiding techniques that are used to protect intellectual property by embedding copyright information into digital media such as images, music, and videos. To explain watermarking, consider invisible watermarking as an example; invisible watermarking is employed to embed visually imperceptible data or ciphers into cover work. Steganography involves embedding information (cipher) in cover work through undetectable changes. A major characteristic of blind data hiding watermarking techniques is that the extraction processing can extract the hidden information without cover work. The extraction process that does require cover work is called informed data hiding. To evaluate the efficiency of steganographic techniques, Chang [10] recommended two criteria to evaluate steganographic techniques, namely, embedding efficiency and embedding payload. Embedding efficiency describes the visual quality of the stego image, and the embedding payload refers to the size of the embedded cipher. Generally, embedding efficiency uses a peak signal noise ratio (PSNR) to evaluate the visual quality. When the PSNR value exceeds 30 dB, the human eye cannot detect visual differences between embedded and nonembedded images. Thus, the optimal information hiding technique should have both a high embedding payload and high embedding efficiency. Considering the current prevalence of information theft and sabotage, producing stego images within acceptable bounds of the two criteria while effectively preventing malicious illegal acts has become a popular research objective.

Chang [10] proposed a novel steganographic technique with error correction capability. The proposed method used Hamming codes [7, 4] and LSB embedding to encode the hidden information into codewords and embed the codewords into pixels of the cover work, respectively. The simulation results indicated that the proposed method provided superior PSNR compared to LSB embedding. Briefly, the proposed method first divided 7 secret bits into 3 bits and 4 bits, which were then used to locate the selected codeword in each row and column of the 8 × 16 standard array. Next, each selected codeword was embedded into every 7 pixels of the cover work using LSB embedding until all secret bits were embedded. The extraction process involves extracting the LSB of every 7 pixels of the stego image and locating the codeword in every row and column of the 8 × 16 standard array. Every 7 secret bits extracted can be identified by converting the row number and column number into 3 bits and 4 bits. The method proposed by Chang requires greater memory because the proposed method employs a lookup table for embedding and extracting secret bits. Moreover, the error correction capability of this method can correct only single-bit errors. Therefore, how to further improve the error correction capability and embedding payload of the method proposed by Chang is a popular research topic.

This study combines block coded modulation (BCM) codes with LSB embedding to improve both the error correction capability and embedding payload of Chang‘s proposed method. To further improve the PSNR of the proposed method, this study employs modulus functions [11] to increase the differences between the cover work and stego image before embedding BCM codewords into the cover work. The simulation results show that the method proposed in this study possess superior error correction and LSB embedding capabilities than that of the method proposed by Chang when the stego image is corrupted by salt-and-pepper noise. Furthermore, our proposed method also offers a higher embedding payload than that provided by Chang‘s proposed method.

2

Literature Review

In this section, we first describe the encoding and decoding architecture of BCM codes and Reed-Muller codes. Then, we explicate the embedding and extraction processes of the following three techniques: LSB embedding, Chang‘s proposed method [10], and the modulus function.

2.1

BCM Codes

BCM [12] is a coding scheme that combines both modulation and channel coding and is based on the Euclidean distance between symbols. For convenience, we describe how to construct a 4-QAM BCM code based on a 4-QAM signal constellation with set partitioning. First, symbols within the signal constellations are recursively divided into numerous subsets, where the Euclidean distance between the neighboring symbols of each subset are gradually increased. A 4-QAM BCM code is composed of two component codes C₁ and C₂, which are binary block codes with length N. The minimum Hamming distance is d_i, where 1 ≤ i ≤ 2. The two component codes are used to construct a 2 × N codeword array by inserting the codeword c_i of the i^th component code C_i into the i^th row of a 2 × N codeword array. This is represented in the following mathematical expression:

Next, a 4-QAM BCM codeword with length N is created by modulating each column of the codeword array into a 4-QAM symbol. Figure 1 shows a 4-QAM signal constellation, where the bit indicators are arranged by set partitioning and the ratio between the squared Euclidean distances of the two subsets is 1:2. A 4-QAM BCM codeword X = (X₀, X₁,…, X_N–1) can be expressed using the following mathematical equation:

Figure 1.

The set-partitioned 4-QAM signal constellation.

where j=-1. This mathematical expression shows that the 4-QAM BCM codeword X is composed of two binary component codewords c₁ ∈ C_i, i = 1,2.

2.2

Reed-Muller codes

This study employs Reed-Muller codes as the component codes for constructing a BCM code. Let m and r be the two positive integers and 0 ≤ r ≤ m. A rth-order binary Reed-Muller code with a code length of N = 2m, which is a

linear block code, can be expressed as RM(r,m). Assuming 1 ≤ i ≤ m, let x_i be a vector of length 2m that exists in the binary Galois field with the following characteristics:

where (0,...,0︸2i−1) and (1,...,1)︸2i−1 are 2^{i – 1} -tuples with all zeroes and all ones as the content, respectively [12]. For example, if m = 3, the three vectors existing in the binary Galois field of length 8 can be expressed as

x₁ = (0,1,0,1,0,1,0,1),

x₂ = (0,0,1,1,0,0,1,1),

x₃ = (0,0,0,0,1,1,1,1).

2.2.1

Encoding Reed-Muller codes

For an rth-order binary Reed-Muller code with a code length of 2m, the generator matrix G of RM(r,m) can be expressed as follows:

where 1 is a vector of length 2m and the content is all ones. In other words, an rth-order binary Reed-Muller codeword is obtained through a linear combination of the vectors

{1, x₁,…, x_m, x₁x₂,…, x_mx_m–1,…, x₁x₂ … x_r }.

For example, m = 3 and r = 2, the generator matrix of RM (2,3) is a matrix sized k × n = 7 × 8, as shown below.

Assuming the input message is u = (1,0,1,0,0,0,0), the output codeword c is expressed as follows:

2.2.2

Decoding Reed-Muller codes

The Reed decoding algorithm is a type of decoding algorithm for RM(r,m) [12]. Using RM(2,3) as an example, assuming the input message is u = (u₀,u₁,u₂,u₃,u₁₂,u₁₃,u₂₃) and the received codeword is r = (r₁,r₂,r₃,r₄,r₅,r₆,r₇,r₈), the decoded value u12' of input message bit u₁₂ is determined by the results of the two decision equations below.

If both u12(1) and u12(2) are 1, then the input message bit u₁₂ is decoded as u12'=1. Conversely, if both u12(1) and u12(2) are zeroes, then the decoded input message bit u12' is zero. Calculation of the above equations is known as binary addition; that is, 1+1=0, 1+0=1, 0+1=1, and 0+0=0. The corresponding positions in the received codeword of two decision equations are based on the nonzero positions in the two vectors {x₃, 1 + x₃}. The decision equations for decoding input messages u₁₃ and u₂₃ are determined by summing the non-zero positions from {x₂,1 + x₂} and {x₁, 1 + x₁ } of the received codeword for decision equations, as shown below.

The first stage correction involves adjusting the received codeword according to the decoded (u12',u13',u23'). After this adjustment, the received codeword of the first stage correction is defined as r‘ = r– u’₁₂x₁x₂ – u’₁₃x₁x₃– u’₂₃x₂x₃. The input message (u₁u₂,u₃) is then decoded from the content of r’, where the input message bit u₁ may be decoded to determine the decoded value u0' using the results of the following four decision equations.

If most of the results of these four decision equations are zeroes, the input message u₁ is decoded as u0'=0. Conversely, if most of the results of these four decision equations is 1, then the input message u₁ is decoded as u0'=1. The four decision equations were decoded by summing the corresponding non-zero positions of the codewords received from the four vectors

Therefore, the decision equations for decoding the input messages u₂ and u₃ are based respectively on the sum of the corresponding non-zero positions from the received codewords in

and

The decoded (u1',u2',u3') are then used in the second stage correction. The received codeword of the second stage correction is defined as

which is used to determine the decoded value of the input message bit u₀. If the majority of the content value for r^‘’ is 0, then the input message bit u₀ is decoded as u0'=0. Conversely, u₀ is decoded as u0'=1 if the majority of the content value for r^" is 1. Finally, the input message decoded using the Reed decoding algorithm is

2.3

Chang‘s proposed method [10]

For a cover work sized M×W, the method proposed by Chang employs the Hamming code [7,4] to hide information. The amount of data that can be hidden is (M×W)/7, where y denotes the smallest positive integer that is less than y. Chang‘s proposed method hides information using the Hamming code [7,4], with a standard array of 8 × 16. Seven bits are read from the data to be hidden and then divided into 3 bits and 4 bits. The 3 bits are used to express which of the 8 coset leaders should be selected, and the 4 bits denote which of the 16 codewords should be chosen. Chang‘s proposed method adds the selected coset leader and codeword using the vector from additions as the information to embed into the cover work. The method to embed information involves obtaining 7 pixels from the cover work and then replacing the LSB content of the 7 pixels with the selected processed information in sequence.

Data is extracted from the receiver by reading the LSB content of the 7 pixels in the sequence that data are embedded into the cover work. The 7 bits obtained using this method are multiplied by the parity check matrix H of the Hamming code [7,4] to obtain the 3 bits syndrome. The coset leader corresponding to the syndrome is added to the extracted 7 bits to obtain the codeword, and the 4 bits corresponding to the codeword are revealed using the standard array, thereby retrieving the embedded 7 bits of hidden data. Because Chang‘s proposed method requires the standard array to be built beforehand, extra memory is required in both the transmitter and the receiver to store the 128 vectors required for embedding and decoding. If the code length N for the Hamming code is extended, the vectors requiring storage increase to the nth power of 2, that is, 2n, which increases the overall costs. Thus, we propose a steganographic technique based on BCM architecture and select Reed-Muller codes as component codes. This is primarily because the Reed decoding algorithm can be decoded through easy calculations and does not require substantial memory to build the standard array, thereby effectively improving the high storage requirements of Chang‘s proposed method.

2.4

Modulus function

Thien and Lin [11] proposed a steganographic technique to improve the visual quality of the stego image using modulus functions. The expression of modulus function is defined as c = a mod b, where a is the dividend, b is the divisor, and c is the reminder. For example, 3 mod 2 equals 1, that is, the division of 3 by 2 leaves a remainder of 1. Let × be a pixel used to hide data in the cover work, z be the hidden information, and y equal log₂z. First, the embedding process of modulus function is employed to compute the following equation:

w=z- (x mod y).

The result w is applied to determine the minimum variance e using the following equations:

where s represents the smallest integer closest to s, and ⌈v⌉ represents the largest integer closest to v. Finally, the modified pixel x‘, which replaces x in the cover work, is obtained by calculating x’ = x + e. The modulus function extraction process involves computing z = x’ mod y to extract the information hidden in the stego image. Although the modulus function offers superior visual quality, it has no error correction capabilities to prevent errors in the extraction process. Therefore, this study uses BCM codes to improve the error correction capabilities of the modulus function.

3

The proposed method

This study proposes a steganographic technique that offers both error correction capabilities and superior visual quality. The proposed method, which can be used in blind data hiding watermarking systems, integrates BCM codes to improve the error correction capabilities of LSB embedding. This study also employs a modulus function to improve the PSNR of the proposed method because using more LSBs to embed hidden information reduces the PSNR. Because every bit of a binary sequence converted by a pixel can be considered a subset of the signal constellation, this study employs various order Reed-Muller codes as the component codes of BCM codes to protect the LSB of each pixel when errors occur during the extraction process. Because the impact on visual quality is lower when information in hidden the first LSB compared to the other LSB, the block codes used to hide information in the first LSB must have equal or superior error correction capabilities to maintain both a high error correction capability and embedding payload. Therefore, the block code encoding length of the first LSB must be less than that of the second LSB. For example, if the block code chosen for the first LSB is a RM(2,4) with a code length of 16 and the ability to correct 1-bit errors, then the block code chosen for the second LSB must use a block code longer than 16 bits and correct 1 or more bits, such as RM(2,5) with a code length of 32 and the ability to correct 3-bit errors. The data encoding and extraction processes of the method proposed in this study are explained below. In this study, a grayscale image sized at M × W was used as the cover work, and Reed-Muller codes were used as the component codes of BCM codes.

3.1

Data embedding procedures

Assume n is the number of LSBs used for hiding information. Let the block code used for hiding information in the ith LSB be RM(r_i,m_i), where RM(r_i,m_i) is a

linear block code and i = 1,2,…,n. The linear block code selected as the component code must satisfy the conditions of n_j+1 > n_j and d_j+1 ≥ d_j, j = 1,2,…,6. First, a grayscale image sized at M × W was adopted as the cover work, and the block divisions required for hiding information in the ith LSB were calculated. That is, the M × W pixels p_f,1 ≤ f ≤ M × W of the grayscale image were divided into M×W2mi block bi'(i),1≤i', 1 ≤ I′ ≤ ≤M×W2mi and i = 1,2, …, n, where each block contains 2mi pixels. The proposed method is used to determine the size of the information hidden as S and sized at ∑i=1nM×W2mi×(ki) bits, where n is the number of LSBs used to hide the information. Then, the k_i bits obtained from the data being hidden and marked as ui=(Ui,1,Ui,2,…,Ui,ki) are converted into Reed-Muller codewords c_i after the Reed-Muller encoding process is performed. Specifically, the codeword c_i is generated from c_i = u_iG_i, where G_i is the generator matrix for RM(r_j,m_j). To perform embedding, each pixel value p_f is first converted into an 8-bit binary sequence l_f = (l₁,l₂,l₃,l₄,l₅,l₆,l₇,l₈) representing the grayscale pixel value, where the grayscale pixel value p_f ranges between 0 and 255. Next, the proposed method sequentially embeds the content of codeword c_i with the length of 2mi into the ith LSB of the divided blocks. This method can be expressed as the ith LSB (lsi(Vi)∈bVi(i))=ci,si(Vi). lsi(Vi) is the binary sequence converted from the s_ith pixel in block vi, bvi(i) is the v_i, th block divided during the ith LSB embedding, and ci,si(vi) is the s_ith element from the codeword that is hidden in the v_i, th block in the ith LSB, where v and 1≤vi≤M×W2mi. Each modified pixel p’_t of the v₁ th block after the n-bit LSB embedding is used as the input value of the modulus function, where t=1,2,…2m1 and n is the number of LSBs used for hiding information. We first employed modulus operation to calculate the following equation:

where p_t is the original tth pixel of the v₁,th block in the cover work and t=1,2,…2m1. Then, the resulting value w_t was used to determine the minimum variance e_t through the following equations:

where s represents the smallest integer closest to s, ⌈v⌉ represents the largest integer closest to v, i = 1,2,..., n, and t=1,2,…,2m1. After calculating the modulus function, the resulting pixel pt* is obtained using the following decision equations.

where t=1,2,…,2m1. The embedding process is explained below.

Procedure: Data embedding

Input: Hidden data S, n LSBs embedded into a pixel, and a grayscale image M × W in size, where the grayscale image is used as the cover work. RM(r_i,m_i) is used as the block codes for hiding information in the ith LSB, where n_j+1 > n_j and d_{j+1 ≥} d_j, j = 1,2,…,6 and i =1,2,...,n.

Output: A stego image I’ M×W in size

• Step 1:

  Define the sequence of the M×W pixels in the grayscale image /, wherep_f,1 ≤ f ≤ M × W, and divide the blocks according to the following procedure: Blocks required to hide information in theith LSB: Divide the M × W pixels p_f,1 ≤ f ≤ M × W in the grayscale image into M×W2mi block bvi(i),1≤Vi≤M×W2mi, where each block contains 2mi pixels.

• Step 2:

  Read the next kvi data bits from the payload S and mark as

  

• Step 3:

  Generate the codeword cvi from

  

  whereG_i is the generator matrices ofRM(r_j,m_i).

• Step 4:

  Replace theith LSBs content of the binary sequence that corresponds with the 2mi pixels in block bvi(i) with content ci,si(vi) from the codeword cvi. This can also be expressed as theith LSB (lsi(vi)∈bvi(i))

  

• Step 5:

  Compute the resulting valuew_t according tow_t = p’_t-(p_t mod 2i), wherep_t is the originaltth pixel of thev₁ th block in the cover work and t=1,2,…,2m1. Use the resulting valuew_t to determine the minimum variancee_t according to (1). Finally, the resulting pixel pt*t=1,2,…2m1 can be obtained using (2).

• Step 6:

  Replace thetth pixelp_t of thev₁ th block with the resulting pixel pt* where t=1,2,…,2m1 and 1≤v1≤M×W2m1.

• Step 7:

  Repeat Steps 2 to 6 until all payload S is embedded.

3.2

Data extraction procedures

Assuming the receiver is aware that the stego image is a grayscale image and the parameters of the Reed-Muller codes are r_j and m_i, when the receiver receives the stego image, all the stego image pixels use modulo 2i operation. Additionally, the stego image after modulus operation is divided into M×W2mi blocks for extracted information from the ith LSB. Specifically, each block used to extract information from the ith LSB contains 2mi pixels

Pixels from each block containing ith LSB hidden information are converted into a binary sequence lt'(vt')=(l1(vt'),l2(vt'),l3(vt'),l4(vt'),l5(vt'),l6(vt'),l7(vt'),l8(vt')), where t'=1,2,…,2mi and 1≤vt'≤M×W2mi. The ith LSB from the 2mi pixels in the v_i th steganographic blocks is extracted, where 1≤vi≤M×W2mi. The extracted LSBs are combined into the binary sequences and expressed as

Finally, the binary sequences di(vi) from each block are decoded with a r_i th order Reed decoding algorithm until all the payload S is extracted. The data extraction process can be consolidated into the following procedures:

Procedure: Data extraction

Input: A stego image I’ M × W in size with n LSBs embedded in each pixel, where the codewords are generated by RM(r_j,m_j) and i = 1,2,..., n.

Output: Original payload S

• Step 1

  First, all M×N pixels

  

  in the stego image I’ employ modulo 2n operation. After modulus operation, divide the M × W pixels pf,received'*1≤f≤M×W,, into the M×W2mi information hiding blocks of theith LSB, where each of theith LSB blocks contain 2mi pixels

  

  and

  

• Step 2:

  Read each pixel in the subsequentith LSB information hiding blocks and convert them into the binary sequences

  

  where t'=1,2,…,2mi and 1≤vt'≤M×W2mi.

• Step 3:

  Extract theith LSB from 2mi binary sequences lt'(vt'),

  

  Assemble the extracted LSBs into binary sequences expressed as

  

• Step 4:

  Decode the extracted codewords di(vi) intos_i, using ther_i th order Reed decoding algorithm.

• Step 5:

  Repeat Steps 2 to 4 until all payload S is extracted.

4

Experimental results

In this study, we conducted simulations using 8 grayscale images with 256 × 256 pixels, as shown in Fig. 2. We assessed the degree of visual differences between the cover work and the stego image with the embedded information using the PSNRs. PSNR is defined as

Figure 2.

Eight grayscale images 256 × 256 pixels in size.

where MSE=1M×W∑i=0M-1∑j=0W-1li,j-li,j'2, I is the original grayscale image, and, I′ is the stego image. Generally, when the PSNR exceeds 30 dB,

visually distinguishing the differences between the stego image and the cover work is extremely difficult. To compare the payload size that can be embedded using various information hiding techniques, we assessed various embedding payloads P (calculated using the unit of bits-per-pixel, bpp), which can be defined as

where ||S|| refers to the size of the payload S. The larger the P value, the more data can be hidden in the stego image. Generally, PSNR declines with increases in the embedding payload.

Achieving a high embedding payload without being visually distinguishable by the human eye and simultaneously preventing errors is currently a popular topic of steganography research. The experimental results indicate that the method proposed in this study hides and protects data in the first and second LSB of each pixel in the cover work. To further analyze the error correction capabilities of LSB embedding, the method proposed by Chang, and the method proposed in this paper, we compared situations where stego images are disrupted by salt-and-pepper noise [13]. The value of each noisy pixel in the salt-and-pepper noise ranged between 0 and 255 and the image size was 256 × 256. The position where the stego image

was disrupted by noise was randomly distributed. We used the error correction rate, which is expressed below, to evaluate the error correction capabilities of each technique.

In this equation, b_c is the number of correct bits and b_e is the number of error bits after data extraction.

Figure 3 shows the block codes employed for the first LSB and second LSB embedding using RM(2,4) and RM(3,5). The error correction capability of both RM(2,4) and RM(3,5) can correct single-bit errors. For embedding data in the first LSB, the 256 × 256 original image was divided into 4,096 blocks with lengths of 8. For embedding data in the second LSB, the 256 × 256 image was divided into 2,048 blocks with lengths of 16. In Fig. 1, the payload size of each stego image is 98,304 bit and P=|S|M×W=98,304256×256=1.5. The method proposed in this study guarantees PSNR values above 40 dB. Figure 4 shows the baboon image converted into a stego image using LSB embedding, Chang’s proposed method, and the method proposed in this study. The experimental parameters are identical to those employed in Fig. 3; that is, the block codes employed for the first LSB and second LSB embedding are RM(2,4) and RM(3,5), respectively. The steganographic data extraction was disrupted by the same salt-andpepper noise.

Figure 3.

The visual quality and embedding payload of the stego images created using the method proposed in this study.

Figure 4.

Comparison of the robustness of the three steganographic techniques under salt-and-pepper noise disruption: (a) undisrupted; and (b) after salt-and-pepper noise disruption.

Assuming that half the 256 × 256 pixels in the stego image are disrupted by salt-and-pepper noise, as shown in Fig. 4(a), regardless of whether the PSNR of Chang’s proposed method is superior to that of the method proposed in this study and of 2-bits LSB embedding, the embedding payload of the method proposed in this study is higher than that of Chang’s proposed method. In Fig. 4(b), the error correction rate of the method proposed in this study is superior to that of the two other techniques. Table 1 shows a comparison of the PSNR, embedding payload, and error correction rates of the three steganographic techniques applied to 8 images. However, no error correction rate is displayed for LSB embedding in Table 1 because

Table 1.

Comparison of the three steganographic techniques according to their PSNR, embedding payload, and error correction rate under salt-and-pepper noise disruption: (a) LSB embedding; (b) Chang‘s proposed method; and (c)the method proposed in this study.

Image Name	PSNR			Embedding payload (P)			Error correction rate (C)
	(a)	(b)	(c)	(a)	(b)	(c)	(a)	(b)	(c)
Lena	44.1683	48.9787	46.3463	2	0.99997	1.5	-	1.526	3.0292
Baboon	44.1586	50.1165	46.3728	2	0.99997	1.5	-	1.526	3.0292
Barbara	44.1398	48.6595	46.3881	2	0.99997	1.5	-	1.526	3.0292
Boats	44.1584	48.1376	46.3607	2	0.99997	1.5	-	1.526	3.0292
Bridge	44.1371	51.1283	46.3593	2	0.99997	1.5	-	1.526	3.0292
Jet (F16)	44.1502	47.0562	46.3713	2	0.99997	1.5	-	1.526	3.0292
Goldhill	44.1483	50.8054	46.3642	2	0.99997	1.5	-	1.526	3.0292
Zelda	44.1732	49.7253	46.34	2	0.99997	1.5	-	1.526	3.0292

LSB embedding does not possess error correction capabilities. The results in Table 1 show that the method proposed in this study provides a PSNR and embedding payload nearly equivalent to that of 2-bits LSB embedding while offering almost double the error correction rates provided by the other two techniques.

5

Conclusion

This study proposed a blind data hiding method with error correction capabilities and high embedding payloads by combining LSB embedding and BCM to produce stego images. Compared with Chang‘s proposed method, although the PSNR of the method proposed in this study is less than optimal, this method does not require substantial memory to construct standard arrays for extracting data. Additionally, our proposed method offers significantly superior embedding payloads and error correction capabilities.

Acknowledgements

This work was supported in part by the National Science Council (NSC) of Republic of China under grant NSC 101-2221-E-324-026 and NSC 101-2221-E-150-059.