16 Image Sharing with Steganography and Authentication

More and more data are being transmitted via the public access network, the Internet, due to its favorable characteristics such as low cost, speed, and reliability. Although the Internet is a public access network, certain data require secrecy, such as commercial or military images, to protect them from illegitimate users during transmission. Steganography is a technique for transmitting secret data without being noticed. This technique hides secret messages into cover media to avoid malicious attacks. The cover media can be digital images, digital videos, source codes, or even HyperText Markup Language (HTML) codes. The digital image used to embed the secret data is called a cover image, which becomes a stego-image once the secret data are embedded. With steganography, malicious attackers do not know that a stego-image carries secret data. Therefore, they will not try to extract the data or otherwise trespass on it. However, there is a weakness common to all steganographic techniques. If one of the stego-media is lost or corrupted, the secret data cannot be revealed exactly and completely. Therefore, several secret sharing techniques have been proposed to overcome this weakness. With regard to the concept of secret sharing, the well-known (k, n)-threshold schemes pioneered by Shamir [20] and Blakley [2], respectively, have four characteristics in common:

k ≤ n.
The secret is shared among n participants.
Only k or more participants can reconstruct the original secret.
When the number of participants is (k − 1) or less, they cannot recover the original secret.

Based on the (k, n)-threshold schemes, in 1995 Naor and Shamir [17] developed the first secret image sharing technique to safeguard and share image-based secrets. Their approach, called visual secret sharing (VSS), makes it possible to publicly transmit secret images efficiently and safely. The detailed principles of such a technique follow:

The secret image is divided into n noise-like images, called shadows or shares, with each noise-like shadow containing no original image information.
n noise-like shares can be transmitted to n participants via the Internet instead of the secret image itself, so that each participant keeps only one single share. Thereby, VSS can prevent attackers from gaining access to the secret image directly.
When any k or more shadows are brought together co-operatively, the secret image can be restored without any computations based on the properties of the human visual system.

Following this pioneering research, many VSS schemes have been proposed over the past decade. Shamir’s polynomial-based secret sharing approach was adopted into secret image sharing by Thien and Lin in 2002 [23]. Then, Wang and Su [25] made some improvements to decrease the size of the shared images based on Thien and Lin’s scheme [23]. Studies in secret image sharing have focused on different active topics: decreasing share size [4,5,25], dealing with attacks by malicious users, and detecting fake shadows [14,18,29]. The research domain has been also extended from gray images to color images [1,3,4,6,7,21]. And, the generated shares become meaningful instead of noise-like from the start [24]. Aside from these issues, Yang [27], Cimato et al. [8], and Wang et al. [26] separately proposed a new VSS scheme, called a ProbVSS scheme, to deal with problems such as pixel expansion and computational complexity that typically arise in image sharing. The ProbVSS scheme is based on probabilistic concepts and is designed solely for binary images. By taking advantage of Boolean operations, this scheme overcomes the shortcomings inherent in high computational complexity and large pixel expansion at the same time.

In 2004, Lin and Tsai proposed another kind of secret sharing scheme incorporating both steganography and authentication [15]. In Lin-Tsai’s scheme, the secret image is divided into shadows and data hiding is used to embed the shares and corresponding authentication codes into the cover image. During the reconstruction and verifying phase, the hidden authentication codes are then extracted to verify the integrity of the stego-image. However, the size of the cover image becomes fourfold that of the secret image. The Lin-Tsai scheme combines steganography and authentication features to avoid transmitting an erroneous stego-image or intentionally providing a false image by using a parity check bit. However, by the principle of the parity check itself, the authentication ability is weak.

Yang et al. proposed a new scheme to overcome some of the weaknesses in the Lin-Tsai scheme in 2007 [28]. Their objective was to prevent cheating by participants. They also improved the authentication ability and the quality of the reconstructed grayscale secret image. Although the Yang et al. scheme can restore a distortion-free secret image, it allows for a significant probability that a fake stego-image can be authenticated successfully, and the cover image size is still four times that of the original secret image. Building on their predecessors’ experience, in 2008 Chang et al. proposed a secret sharing scheme that incorporates authentication based on the Chinese Remainder Theorem (CRT) [9]. They successfully improved authentication capability by combining CRT. However, in Chang et al.’s scheme, pixel expansion remains a problem and the size of the cover image should be at least twice that of the secret image. In addition, generating authentication bits with CRT increased computational complexity.

This chapter proposes an enhanced scheme with the aim of maintaining the effective authentication but eliminating the pixel expansion problem while retaining an acceptable computational cost. Our scheme uses two techniques in combination to reduce cover image size. The first is an error diffusion technique [13,22] that helps to transform a grayscale image into a binary image. The second, called ELUT, is an edge lookup inverse halftoning technique that relies on edge detection and a lookup table to generate a reconstructed grayscale image from a halftone image [11]. Inverse halftoning is a kind of commonly used technique to reconstruct grayscale images from halftone images. In 2005, a new edge-based lookup table scheme for inverse halftoning was proposed by Chung and Wu [11], by which, the quality of the reconstructed grayscale images was improved. In this chapter we call Chung and Wu’s scheme ELUT for short.

Experimental results confirm that no pixel expansion occurs in the proposed scheme and the visual quality of the stego-image carrying the shadows is much better. Moreover, the proposed scheme successfully reduces computational complexity while maintaining an acceptable authentication ability, which is much better than the performance of either Lin-Tsai’s scheme [15] or Yang et al.’s scheme [28].

The rest of this chapter is organized as follows. In Section 16.2, we briefly introduce the Lin-Tsai scheme [15], the Yang et al. scheme [28], and the Chang et al. scheme [9]. In Section 16.3, we briefly review the techniques adopted in the proposed scheme. Full details of our proposed scheme are explained in Section 16.4. Section 16.5 gives some experimental results. Finally, our conclusions are presented in Section 16.6

16.2 Related Work

In this section three existing schemes, the Lin-Tsai scheme [15], Yang et al.’s scheme [28] and Chang et al.’s scheme [9] are introduced, in turn.

16.2.1 Lin and Tsai’s Scheme

Lin-Tsai’s scheme is a (k, n)-threshold polynomial-based scheme that combines steganography and authentication to enable the sharing of secret images [15]. Their scheme uses parity check to achieve authentication, and each pixel in a secret image is used to produce n shared pixels for n participants by using the polynomial function in Equation 16.1.

F (x) = (c_{0} + c_{1} x + \dots + c_{k - 1} x^{k - 1}) m o d p . (16.1)

$F (x) = (c_{0} + c_{1} x + \dots + c_{k - 1} x^{k - 1}) m o d p . (16.1)$

Later, both the parity check bits and the shared pixels are embedded into the corresponding four-pixel blocks in the cover image. For simplicity, assume that I_ij is the ij-th pixel in the secret image and $B_{i j}^{1}, B_{i j}^{2}, \dots, B_{i j}^{n}$ $B_{i j}^{1}, B_{i j}^{2}, \dots, B_{i j}^{n}$ are the n cover blocks in the cover image, where $B_{i j}^{k}$ $B_{i j}^{k}$ is the block with position (i, j) in the k-th cover for 1 ≤ k ≤ n, which contains four pixels, $Y_{i j}^{k}, V_{i j}^{k}, W_{i j}^{k}$ $Y_{i j}^{k}, V_{i j}^{k}, W_{i j}^{k}$ , and $Z_{i j}^{k}$ $Z_{i j}^{k}$ , as shown in Figure 16.1.

Images

FIGURE 16.1
The ij-th block $B_{i j}^{k}$ $B_{i j}^{k}$ of the k-th cover.

Here, the binary representations of the pixels $Y_{i j}^{k}, V_{i j}^{k}, W_{i j}^{k}$ $Y_{i j}^{k}, V_{i j}^{k}, W_{i j}^{k}$ and $Z_{i j}^{k}$ $Z_{i j}^{k}$ , are (y₁ y₂ …y₈), (v₁ v₂ …v₈), (w₁ w₂…w₈) and (z₁ z₂…z₈), respectively. The steps in this scheme are as follows.

Step 1: Set the modulus p used in the polynomial in 16.1 to 251. If the pixel I_ij ≥ 250, it is directly truncated to 250. Apparently, this operation can distort the secret image.

Step 2: Take the pixel I_ij· as the coefficient c₀ and choose k − 1 integers as other coefficients c₁, c₂,…,c_k₋₁ randomly to construct a polynomial in Equation 16.1. Then takes the pixel value $Y_{i j}^{k}$ $Y_{i j}^{k}$ for 1 ≤ k ≤ n as the input x of the polynomial to compute the shared pixel $F (Y_{i j}^{k}) = S_{i j}^{k} = (s_{1} s_{2} \dots s_{8})$ $F (Y_{i j}^{k}) = S_{i j}^{k} = (s_{1} s_{2} \dots s_{8})$ , where (s₁ s₂…s₈) means eight bits of the shared pixel $S_{i j}^{k}$ $S_{i j}^{k}$ .

Step 3: Embed the shared pixel $S_{i j}^{k}$ $S_{i j}^{k}$ into the block $B_{i j}^{k}$ $B_{i j}^{k}$ by replacing the eight bits v₇ v₈, w₆ w₇ w₈ and z₆ z₇ z₈ with s₁ s₂…s₈ as shown in Figure 16.2.

Step 4: Generate a check bit b according to parity check policy to achieve the authentication capability shown in Figure 16.2.

Images

FIGURE 16.2
The block of the k-th stego-image in Lin-Tsai’s scheme.

Unfortunately, in Lin-Tsai’s scheme, the parity bit of the upper-right pixel shown in Figure 16.2 is chosen to make this pixel an even or odd parity as a binary parity sequence. Dishonest participants can derive the parity information from their own stego-images, and thus can easily and maliciously counterfeit a stego-image. For instance, assume that the upper-right pixel ${\bar{V}}_{i j}^{k} = (11011 111)$ ${\bar{V}}_{i j}^{k} = (11011 111)$ . A dishonest participant can modify it to (11011 010), which still meets the odd parity, but the 8-bit input of (k-1)-degree polynomial becomes changed. Thus, it successfully passes authentication but the (k-1)-degree polynomial cannot be obtained. In addition, the dishonest participant can also modify three other pixels, ${\bar{Y}}_{i j}^{k}, {\bar{W}}_{i j}^{k},$ ${\bar{Y}}_{i j}^{k}, {\bar{W}}_{i j}^{k},$ and ${\bar{Z}}_{i j}^{k}$ ${\bar{Z}}_{i j}^{k}$ , to change the input and output of (k-1)-degree polynomial without influencing the upper-right pixel ${\bar{V}}_{i j}^{k}$ ${\bar{V}}_{i j}^{k}$ , thus passing authentication. Therefore, their scheme has a weak authentication process, which may allow a fake stego-image to pass the authentication check quite easily.

16.2.2 Yang et al.’s Scheme

To overcome the weaknesses in Lin-Tsai’s scheme, Yang et al. [28] proposed an improved version in 2007. In Yang et al.’s scheme, the modulus value p is set to the Galois Field GF(2⁸), that is, p = g(x) = x⁸ + x⁴ + x³ + x¹ + x⁰. This approach allows the acquisition of a secret image without distortion.

Images

FIGURE 16.3
The cover blocks used in Yang et al.’s scheme.

Images

FIGURE 16.4
The block of a stego-image in Yang et al.’s scheme.

In Yang et al’s scheme, let the pixel I_ij of the secret image be used to produce the n shared pixels $S_{i j}^{1}, S_{i j}^{2}, \dots, S_{i j}^{n}$ $S_{i j}^{1}, S_{i j}^{2}, \dots, S_{i j}^{n}$ , to be embedded into the cover blocks $C_{i j}^{1}, C_{i j}^{2}, \dots, S_{i j}^{n}$ $C_{i j}^{1}, C_{i j}^{2}, \dots, S_{i j}^{n}$ , where each cover block is represented as $C_{i j}^{k} = {V_{i j}^{k}, Y_{i j}^{k}, Z_{i j}^{k}, U_{i j}^{k}}$ $C_{i j}^{k} = {V_{i j}^{k}, Y_{i j}^{k}, Z_{i j}^{k}, U_{i j}^{k}}$ for 1 ≤ k ≤ n as shown in Figure 16.3. Pixel I_ij of the secret image is first embedded into the coefficient c₀ to construct a polynomial as shown in Equation 16.1. Next, the shared pixel $S_{i j}^{k}$ $S_{i j}^{k}$ is computed by taking the pixel value $V_{i j}^{k}$ $V_{i j}^{k}$ of the corresponding cover image block $C_{i j}^{k}$ $C_{i j}^{k}$ as the input x of the polynomial shown in Equation 16.1. Let the binary representation of the shared pixel $S_{i j}^{k}$ $S_{i j}^{k}$ be (s₁ s₂…s₈). Hence, the shared pixel $S_{i j}^{k}$ $S_{i j}^{k}$ is embedded into its corresponding cover image block $C_{i j}^{k}$ $C_{i j}^{k}$ by replacing the eight bits v₁ v₀ y₁ y₀ z₁ z₀ u₁ u₀ with s₁ s₂ …s₈, and at the same time, the bits z₃ z₂ of pixel $Z_{i j}^{k}$ $Z_{i j}^{k}$ are replaced by v₁v₀ of pixel $V_{i j}^{k}$ $V_{i j}^{k}$ in order to keep the complete pixel value $V_{i j}^{k}$ $V_{i j}^{k}$ for recovering the corresponding secret pixel as shown in Figure 16.4.

However, Yang et al.’s scheme cannot avoid the fact that four least significant bits (LSBs) of the pixel value $Z_{i j}^{k}$ $Z_{i j}^{k}$ in each block must be modified. Such modification may make the stego-images different from the cover images visually and the risk of being observed by attackers is increased.

To further improve Lin-Tsai’s authentication ability, Yang et al. used the hash-based message authentication code (HMAC) in Equation 16.2.

H_{k} (({\bar{C}}_{i j}^{k} - b) ‖ i d), (16.2)

$H_{k} (({\bar{C}}_{i j}^{k} - b) ‖ i d), (16.2)$

where id is the block ID; $C_{i j}^{k}$ $C_{i j}^{k}$ is 31 bits except the check bit b; H( ) and k denote a one-way hash function and the secret key, respectively. Next, as shown in Equation 16.3, the 160-bit HMAC output and executes the XOR operation to obtain the authentication bit b.

b = H_{k} (({\bar{C}}_{i j}^{k} - b) ‖ i d) (16.3)

$b = H_{k} (({\bar{C}}_{i j}^{k} - b) ‖ i d) (16.3)$

However, the average probability of detecting any malicious modification is just 50% because of the characteristic of the parity check itself. In other words, the fake stego-images still have a very high probability of being authenticated successfully.

16.2.3 Chang et al.’s Scheme

In 2008, Chang et al. proposed an enhanced secret sharing scheme based on Lin-Tsai’s scheme and Yang et al.’s scheme. They used the concept of Thien and Lin’s secret image sharing [23] to ensure that no distortion is introduced into the secret image and applied the concept of the Chinese Remainder Theorem (CRT) to improve authentication ability. As a result, their scheme can achieve high authentication ability. The flowchart of Chang et al.’s scheme [9] is shown in Figure 16.5.

Four check bits p₁, p₂, p₃, p₄ can be calculated and embedded into the stego-block (shown in Figure 16.5). The details are shown in the steps below.

Step 1: The residues set of the block ${\bar{C}}_{i j}^{k}$ ${\bar{C}}_{i j}^{k}$ in Figure 16.6 is determined.

$R_{i j, 1}^{k} = (x_{7} x_{6} x_{5} x_{4} x_{3} s_{1} s_{2})$ $R_{i j, 1}^{k} = (x_{7} x_{6} x_{5} x_{4} x_{3} s_{1} s_{2})$ ;

$R_{i j, 2}^{k} = (v_{7} v_{6} v_{5} v_{4} s_{3} s_{4})$ $R_{i j, 2}^{k} = (v_{7} v_{6} v_{5} v_{4} s_{3} s_{4})$ ;

$R_{i j, 3}^{k} = (w_{7} w_{6} w_{5} w_{4} w_{3} s_{5} s_{6})$ $R_{i j, 3}^{k} = (w_{7} w_{6} w_{5} w_{4} w_{3} s_{5} s_{6})$ ;

$R_{i j, 4}^{k} = (z_{7} z_{6} z_{5} z_{4} z_{3} s_{7} s_{8})$ $R_{i j, 4}^{k} = (z_{7} z_{6} z_{5} z_{4} z_{3} s_{7} s_{8})$ ;

$R_{i j, 5}^{k} = i;$ $R_{i j, 5}^{k} = i;$ ;

$R_{i j, 6}^{k} = j .$ $R_{i j, 6}^{k} = j .$ .

Images

FIGURE 433.16
The block of a stego-image in Chang et al.’s scheme.

Step 2: Decide six moduli that are pairwise relatively prime $M_{i j, 1}^{k}, M_{i j, 2}^{k}, M_{i j, 3}^{k}, \dots$ $M_{i j, 1}^{k}, M_{i j, 2}^{k}, M_{i j, 3}^{k}, \dots$ , and $M_{i j, 6}^{k}$ $M_{i j, 6}^{k}$ , where each modulus $M_{i j, a}^{k}$ $M_{i j, a}^{k}$ , for 1 ≤ a ≤ 6, is the prime number greater than $R_{i j, a}^{k}$ $R_{i j, a}^{k}$ .

Step 3: Calculate the $Y_{i j}^{k}$ $Y_{i j}^{k}$ integer by Equation 16.4. Suppose that the binary representation of the $Y_{i j}^{k}$ $Y_{i j}^{k}$ is (y₁y₂…y_e). Note that the number of binary bits of $Y_{i j}^{k}$ $Y_{i j}^{k}$ has to be a multiple of 4.

Y = (\sum_{i = 1}^{r} R_{i} \times \frac{M}{M_{i}} \times I_{i}) (16.4)

$Y = (\sum_{i = 1}^{r} R_{i} \times \frac{M}{M_{i}} \times I_{i}) (16.4)$

Step 4: Four interim authentication bits a₁, a₂, a₃, and a₄ are computed by Equation 16.5.

a_{1} a_{2} a_{3} a_{4} = (y_{1} y_{2} y_{3} y_{4}) \oplus (y_{5} y_{6} y_{7} y_{8}) \oplus \dots \oplus (y_{e - 3} y_{e - 2} y_{e - 1} y_{e}) . (16.5)

$a_{1} a_{2} a_{3} a_{4} = (y_{1} y_{2} y_{3} y_{4}) \oplus (y_{5} y_{6} y_{7} y_{8}) \oplus \dots \oplus (y_{e - 3} y_{e - 2} y_{e - 1} y_{e}) . (16.5)$

Step 5: Denote b₁, b₂, b₃, and b₄ as the current four watermark bits; four check bits p₁, p₂, p₃, and p₄ can be computed by Equation 16.6.

p_{1} p_{2} p_{3} p_{4} = (a_{1} a_{2} a_{3} a_{4}) \oplus (b_{1} b_{2} b_{3} b_{4}) . (16.6)

$p_{1} p_{2} p_{3} p_{4} = (a_{1} a_{2} a_{3} a_{4}) \oplus (b_{1} b_{2} b_{3} b_{4}) . (16.6)$

Step 6: Replace the four LSBs x₀v₀w₀z₀ with the computed check bits p₁ p₂ p₃ p₄ as presented in Figure 16.6.

Images

FIGURE 434.16
The flowchart of Chang et al.’s scheme.

16.3 Adopted Techniques in the Proposed Scheme

To give sufficient background knowledge, this section briefly introduces the related techniques adopted in our proposed scheme, including error diffusion, interpolation, canny edge detector, and edge lookup inverse halftoning as well as the Shamir scheme for secret sharing, respectively.

16.3.1 Error Diffusion Technique

The error diffusion technique is typically used to convert a multiple-level color image into a two-level color image. There are many kinds of idiographic error diffusion strategies. The common concept behind diffusion is the diffusion of errors to neighboring pixels; in this way, no image luminance is lost. The diffused image generated based on an error diffusion strategy is called an error filter. Each error filter has a set of kernel weights. Assume that GI(x,y) is the value of a pixel in position (x,y) in a grayscale secret image. Figure 16.7 is a flowchart of the error diffusion technique.

In the proposed scheme, the Floyd and Steinberg error diffusion strategy is adopted and the kernel weights are $W_{r} = \frac{7}{16}, W b = \frac{5}{16}, W b l = \frac{3}{16}, W b r = \frac{1}{16},$ $W_{r} = \frac{7}{16}, W b = \frac{5}{16}, W b l = \frac{3}{16}, W b r = \frac{1}{16},$ , as shown in Figure 16.8.

After the quantization procedure, a pixel GI(x,y) at position (x,y) in grayscale image GI becomes HI(x,y) and has a value of either 0 or 255. During the quantization procedure, a threshold TH is used to determine HI(x,y) according to Equation 16.7 and the quantization error is determined by Equation (5.8).

Images

FIGURE 435.16
Error diffusion architecture.

Images

FIGURE 16.8
The kernel weights of Floyd and Steinberg’s error filter.

H I (x, y) = {\begin{array}{l} 255, i f G I (x, y) \geq T H \\ 0, o t h e r w i s e \end{array} (16.7)

$H I (x, y) = {\begin{array}{l} 255, i f G I (x, y) \geq T H \\ 0, o t h e r w i s e \end{array} (16.7)$

E (x, y) = G I (x, y) - H I (x, y) (16.8)

$E (x, y) = G I (x, y) - H I (x, y) (16.8)$

Next, error E(x,y) is diffused over four neighboring pixels, GI(x, y+1), GI(x +1, y-1), GI(x + 1, y), and GI(x + 1, y+1), according to Equation 16.9 and the kernel weights (denoted as W) of the error filter are shown in Figure 16.8.

G I (x + i, y + j) = G I (x, y) + E (x, y) \times W, (16.9)

$G I (x + i, y + j) = G I (x, y) + E (x, y) \times W, (16.9)$

where i, j ∈ {0,1}, $W \in {\frac{1}{16}, \frac{3}{16}, \frac{5}{16}, \frac{7}{16}}$ $W \in {\frac{1}{16}, \frac{3}{16}, \frac{5}{16}, \frac{7}{16}}$ ·

Based on Figure 16.8 and Equation 16.9, we can see that when pixels are on the border of the grayscale image, special cases occur. The four kinds of pixels listed below should be considered in distinguishing these cases.

Case 1: The pixels located at (x, 1), where x =1, 2,…, H-1.

Case 2: The pixels located at (H, y), where y =1, 2,…, W-1.

Case 3: The pixels located at (x, W), where x =1, 2,…, H-1.

Case 4: The pixel located at (H, W).

The positions of all four kinds of pixels are represented in Figure 16.9, with the white squares showing the positions of the pixels located at the border of an image. To deal with these special cases, we adopt a special skill, called “excursion” in the procedure, as shown in Figure 16.10.

Images

FIGURE 16.9
The positions of pixels located at the border in an image.

When applied to these pixels, Floyd and Steinberg’s error filter is slightly modified to ignore the nonexistent pixels because the number of these pixels is small compared with the total number of pixels in the whole image. To give a clearer explanation, the following paragraphs give one instance for each case.

At first, set E(1, 1) = 0. For case 1, the pixels at position (x, 1), where x = 1, 2,…, H-1 are considered. We take the pixel at position (1, 1) for example. The value of HI(1, 1) is determined by Equation 16.7. However, there is no pixel at position (2, 0) corresponding to GI(x+1, y-1). Thus, the neighboring pixels that accepted error diffusion are shown in Figure 16.11 for Case 1.

For Case 2, we take the pixel at position (H, 1) for example. The pixel at position (H, 1) is called GI(H, 1) and has an error value of E(H, 1). However, there are no pixels at positions (H+1, 0), (H+1, 1), and (H+1, 2) corresponding to GI(x+1, y-1), GI(x+1, y), and GI(x+1, y+1). Thus, the neighboring pixels that accepted error diffusion are shown in Figure 16.12 for Case 2.

Images

FIGURE 16.10
The “excursion” skill.

For Case 3, we take the pixel at position (1, W) for example. There are no pixels at positions (1, W+1) and (2, W+1) corresponding to GI(x, y+1) and GI(x+1, y+1). Thus, the neighboring pixels that accepted error diffusion are shown in Figure 16.13 for Case 3.

And last, for Case 4, the pixel GI(H, W) at position (H, W), there are no pixels at positions (H, W+1), (H+1, W-1), (H+1, W), and (H+1, W+1) corresponding to GI(x, y+1), GI(x+1, y-1), GI(x+1, y), and GI(x+1, y+1). Thus, there are no neighboring pixels that accepted error diffusion for this case.

We next describe how to use the Floyd and Steinberg error diffusion strategy to transform a gray-scale image into a binary image. The detailed steps are set forth as follows:

Input: A gray-scale secret image GI sized H × W.

Output: A binary image HI sized H × W.

Step 1: Set a threshold TH = 127

Step 2: for i=1 H, j=1: W

Images

FIGURE 438.16
The neighboring pixels that accepted error diffusion for Case 1.

Images

FIGURE 16.12
The neighboring pixels that accepted error diffusion for Case 2.

Loop: if (i = 1) or i = H + 2)|(j = 1) or (j= W+2) → EGI(i,j) = 0; else EGI(i, j) = GI(i − 1,j − 1);

Step 3: for i = 2:H + 1, j = 2: W +1

Loop: if EGI(i, j) ≥ TH → EHI(i,j) = 255;

else EHI(i,j) = 0;

E(i,j) = EGI(i,j)-EHI(i,j);

EGI(i,j + 1) = EGI(i,j + 1) +E(i, j) × Wr; EGI(i + 1,j = EGI(i,j + 1) +E(i, j) × Wb;

EGI(i + 1,j + 1) = EGI(i + 1,j + 1) +E(i, j) × Wb;

EGI(i + 1,j - 1) = EGI(i + 1,j - 1) + E(i, j) × Wbl;

Step 4: for i = 1: H, j = 1:W

HI(i,j) = EHI(i + 1, j + 1).

Images

FIGURE 439.16
The neighboring pixels that accepted error diffusion for Case 3.

16.3.2 Interpolation Technique

In computer computations, a discrete number system rather than a real number system is applied due to the limitations of machine representation. Therefore, a continuous signal must be sampled for computer storage and calculation. However, sampling is always destructive to the original information and new samples often must be reselected when the sampling scale is changed. Let us denote R as a real signal performed in the real number system as shown in Figure 16.14(a); denote D as the digital signal created by R, which is performed in the discrete number system shown in Figure 16.14 (b). The digital signal D′ shown in Figure 16.14(c) is generated by sampling digital signal D.

Images

FIGURE 16.14
Example of sampling an image: (a) Real signal R; (b) Sampled signal D of R; (c) Sampled signal D′ of D.

Figure 16.14 shows that the re-sampled signal D′ can be easily retrieved when the real signal R is always available. However, the original signal is usually discarded after receiving the digital signal D. As a result, the resampled signal D′ must be created from the former signal D. Interpolation is a classical solution for calculating the new samples from another digital signal. Take bilinear interpolation for example. A new sample in signal D′ is expected to be an average value of the two neighboring original samples in D. Assuming that (x, f(x)) and (y, f(y)) are two neighboring samples in D, we can calculate a new sample (z, f (z)) in D′ according to Equation 16.10.

f (z) = \frac{y - z}{y - x} \times f (x) + \frac{z - x}{y - x} \times f (y) . (16.10)

$f (z) = \frac{y - z}{y - x} \times f (x) + \frac{z - x}{y - x} \times f (y) . (16.10)$

16.3.3 Canny Edge Detector

Edge detection is a kind of commonly used technique in image processing. The areas in an image with strong intensity contrasting from one pixel to the next are called edges. The purpose of edge detection is filtering out useless information in an image and significantly reducing the amount of data, while preserving the important structural properties.

Since the pioneering work by Roberts in 1965 [19], a mass of schemes have been developed for detecting edges. The Canny edge detection algorithm is known to many as the optimal edge detector proposed by J. Canny in 1986 [12], which finds edges by looking for local maxima of the gradient of the input image. The gradient is calculated using the derivative of a Gaussian filter. The Canny edge detector contains several adjustable parameters, listed as follows, which can affect the computation time and effectiveness of the algorithm itself. The first parameter is the size of the Gaussian filter, the smoothing filter used in the first stage, which directly affects the results of the Canny detection algorithm. Generally, smaller filters cause less blurring, and allow detection of small, sharp lines. On the contrary, larger filters cause more blurring, smearing out the value of a given pixel over a larger area of the image. Two thresholds are the other parameters. Actually, a too high threshold may make missing important information. On the other hand, a threshold set too low will falsely identify irrelevant information as important. Therewith, the detection would be more likely to be fooled by noise. The Canny edge detection method uses two thresholds, to detect strong and weak edges, and includes the weak edges in the output only if they are connected to strong edges.

The Canny edge detector works in a multistage process. First of all, the image is smoothed by Gaussian convolution. Afterwards, to highlight regions of the image with high first spatial derivatives, a simple 2-D first derivative operator is applied to the smoothed image and edges give rise to ridges in the gradient magnitude image. Then, the algorithm tracks along the top of these ridges and sets to zero all pixels that are not actually on the ridge top so as to give a thin line in the output, a process known as nonmaximal suppression. The tracking process exhibits hysteresis controlled by two thresholds, denoted by T₁ and T₂, where T₁ > T₂. Tracking can only begin at a point on a ridge higher than T₁ and then continues in both directions out from that point until the height of the ridge falls below T₂ . The Canny edge detector is more likely to detect true weak edges and less likely than the others to be fooled by noise.

16.3.4 Edge Lookup Inverse Halftoning Technique

The inverse halftoning technique is used to reconstruct a gray-scale image from an input halftone image. Based on the lookup table (LUT) [10,16] technique, in 2005 Chung and Wu [11] proposed a new edge-based lookup table (LUT) scheme that improves the quality of the reconstructed grayscale image. In the following paragraphs we call Chung and Wu’s scheme ELUT for short. The ELUT scheme first applies the LUT-based inverse halftoning scheme as a preprocessing step to transform the input halftone image to a base grayscale image, and then the edges are extracted and classified from the base grayscale image. According to these classified edges, a novel edge-based LUT is built up to reconstruct the grayscale image, i.e., the ELUT scheme. Figure 16.15 is a flowchart of Chung and Wu’s ELUT scheme.

Images

FIGURE 16.15
The flowchart of Chung and Wu’s ELUT scheme.

Input: A set of n training image pairs (GI_i, HI_i), where GI_i and HI_i are denoted as the i-th grayscale image and its corresponding halftone image, respectively.

Step 1: Generate the lookup table (LUT) by using the five substeps that follow. An array LUT[ ] is used to map the given halftone image to the corresponding grayscale image.

For initialization, i = 1, LUT[k] = 0, where 0 ≤ k ≤ 2¹⁶ − 1.
Divide images double HIi and GIi into overlapping 4 × 4 blocks and denote them as BH_ij and BG_ij. In other words, BH_ij and BG_ij are the j-th halftone block of halftone image HI_i and the j-th grayscale block of grayscale image GI_i, respectively.
Calculate index k for each halftone block BH_ij and update the value of the intermediate LUT[k] by using Equation 16.10. Here, BG_ij(3, 3) is a representative pixel for each grayscale block.

${\begin{array}{l} k = \sum_{u = 1}^{4} \sum_{v = 1}^{4} 2^{(v - 1) + 4 \times (u - 1)} \times B H_{i j} (u, v) \\ L U T [K] = L U T [K] + B G_{i j} (3, 3) \end{array}, (16.11)$ ${\begin{array}{l} k = \sum_{u = 1}^{4} \sum_{v = 1}^{4} 2^{(v - 1) + 4 \times (u - 1)} \times B H_{i j} (u, v) \\ L U T [K] = L U T [K] + B G_{i j} (3, 3) \end{array}, (16.11)$
i = i + 1. If i ≤ n, go to Step b. Otherwise, compute and archive the final LUT[]. N[k] is another array used to store the number of halftone blocks that obtain the same index value k.
For 0 ≤ k ≤ 2¹⁶ − 1, $L U T [k] = \frac{L U T [k]}{N [k]}$ $L U T [k] = \frac{L U T [k]}{N [k]}$ .

Step 2: Replace the element BH_ij(3, 3) in every block BH_ij by LUT[k], where k is the index value of block BH_ij calculated in Step c. When the replacement procedure is finished, retrieve the grayscale image with pixel values corresponding to LUT[k].

Step 3: After applying Step 2 to a set of n training images in succession, a set of reconstructed grayscale images called $G {I^{'}}_{i}$ $G {I^{'}}_{i}$ , i = 1, 2,…, n, can be retrieved. Adopt Canny’s edge detector to each reconstructed grayscale image $G {I^{'}}_{i}$ $G {I^{'}}_{i}$ to generate an edge map EM_i, for i =1, 2,…, n. Each edge map EM_i consists of a set of 4 × 4 blocks. Therefore, the j-th block of the edge map EM_i is denoted as BE_ij. By combining the lookup table LUT generation procedure described in Step 1 with a set of edge maps EM_i, an edge-based LUT, called an ELUT, is generated. Note that in this step, we call the edge map EM. The order of the edge pattern of the ij-th block is denoted as BE_ij. The index value for ij-th block is I_ij for 0 ≤ k ≤ 2¹⁶ − 1. Finally, the mean grayscale value can be derived from ELUT[I_ij, BE_ij], where 0 ≤ EM_ij ≤ 38 based on the number of edge patterns reported by Chung and Wu [11]. In Chung and Wu’s scheme, the value of $G {I^{'}}_{i j}$ $G {I^{'}}_{i j}$ (3, 3) is determinate as Equation 16.12.

G {I^{'}}_{i j} (3, 3) = E L U T [I_{i j}, B E_{i j}] (16.12)

$G {I^{'}}_{i j} (3, 3) = E L U T [I_{i j}, B E_{i j}] (16.12)$

Step 4: Input a halftone image HI, which will be converted to the grayscale image GI′ . The detailed procedure is shown in Figure 16.16.

Images

FIGURE 16.16
Procedure for generating final grayscale image in Step 4.

16.3.5 Shamir Scheme for Secret Sharing

The proposed scheme for secret image sharing is based on the (k,n)-threshold secret sharing scheme proposed by Shamir (1979) [20]. In this section we describe how to use the Shamir scheme to generate secret sharing. In the following steps we use the (k-1)-degree polynomial shown in Equation 16.16 to generate n shares for a group of n secret sharing participants from a secret integer value s for the threshold k.

F (x_{i}) = s + a_{1} x_{i}^{1} + a_{2} \times x_{i}^{2} + \dots + a_{k - 1} \times x_{i}^{k - 1} (16.13)

$F (x_{i}) = s + a_{1} x_{i}^{1} + a_{2} \times x_{i}^{2} + \dots + a_{k - 1} \times x_{i}^{k - 1} (16.13)$

where i = 1, 2,… , n.

Step 1: Select the number k, k ≤ n.

Step 2: Choose the (k-1) integers a₁, a₂, a_k_-1 randomly.

Step 3: For the i-th secret sharing participant, choose a value of x_i freely, i = 1, 2,…, n. Note that all x_i must be distinct from one another.

Step 4: For each chosen x_i, compute the corresponding F(x_i) by using Equation 16.13.

Step 5: Deliver each pair of (x_i, F(x_i)) as a secret share to each participant.

In this secret sharing process, the values of a_i, i = 1, 2, … , k − 1, need not be kept after all secret shares are generated. As well as the secret value s, each αi can be recovered from the n secret shares in the secret recovery steps listed below.

Step 1: Collect at least k secret shares from the n ones to form a system of equations as shown in Equation 16.13. Note that the xi and F(x_i) in Equation 16.13 with i =1, 2, … , k can all be extracted from the k secret shares.

Step 2: Use a polynomial interpolation technique, e.g., Lagrange scheme, to solve s and a_i, i = 1, 2, … , k − 1. Reconstruct the (k − 1)-degree polynomial F(x) described by Equation 16.14.

\begin{array}{l} F (x) = F (x_{1}) \frac{(x - x_{2}) (x - x_{3}) \dots (x - x_{k})}{(x_{1} - x_{2}) (x_{1} - x_{3}) \dots (x_{1} - x_{k})} \\ + F (x_{2}) \frac{(x - x_{1}) (x - x_{3}) \dots (x - x_{k})}{(x_{2} - x_{1}) (x_{2} - x_{3}) \dots (x_{2} - x_{k})} \\ + \dots \\ + F (x_{k}) \frac{(x - x_{1}) (x - x_{2}) \dots (x - x_{k - 1})}{(x_{k} - x_{1}) (x_{k} - x_{2}) \dots (x_{k} - x_{k - 1})} \end{array} (16.14)

$\begin{array}{l} F (x) = F (x_{1}) \frac{(x - x_{2}) (x - x_{3}) \dots (x - x_{k})}{(x_{1} - x_{2}) (x_{1} - x_{3}) \dots (x_{1} - x_{k})} \\ + F (x_{2}) \frac{(x - x_{1}) (x - x_{3}) \dots (x - x_{k})}{(x_{2} - x_{1}) (x_{2} - x_{3}) \dots (x_{2} - x_{k})} \\ + \dots \\ + F (x_{k}) \frac{(x - x_{1}) (x - x_{2}) \dots (x - x_{k - 1})}{(x_{k} - x_{1}) (x_{k} - x_{2}) \dots (x_{k} - x_{k - 1})} \end{array} (16.14)$

Step 3: Compute the solution for the secret value s by Equation 16.15.

\begin{array}{l} s = F (0) \\ = F (x_{1}) \frac{(x - x_{2}) (x - x_{3}) \dots (x - x_{k})}{(x_{1} - x_{2}) (x_{1} - x_{3}) \dots (x_{1} - x_{k})} \\ + F (x_{2}) \frac{(0 - x_{1}) (0 - x_{3}) \dots (0 - x_{k})}{(x_{2} - x_{1}) (x_{2} - x_{3}) \dots (x_{2} - x_{k})} \\ + \dots \\ + F (x_{k}) \frac{(0 - x_{1}) (0 - x_{2}) \dots (0 - x_{k - 1})}{(x_{k} - x_{1}) (x_{k} - x_{2}) \dots (x_{k} - x_{k - 1})} \\ = {(- 1)}^{k - 1} [F (x_{1}) \frac{x_{2} x_{3} \dots x_{k}}{(x_{1} - x_{2}) (x_{1} - x_{3}) \dots (x_{1} - x_{k})}] \\ + F (x_{2}) \frac{x_{1} x_{3} \dots x_{k}}{(x_{2} - x_{1}) (x_{2} - x_{3}) \dots (x_{2} - x_{k})} \\ + \dots \\ + F (x_{k}) \frac{x_{1} x_{2} \dots x_{k - 1}}{(x_{k} - x_{1}) (x_{k} - x_{2}) \dots (x_{k} - x_{k - 1})} \end{array} (16.15)

$\begin{array}{l} s = F (0) \\ = F (x_{1}) \frac{(x - x_{2}) (x - x_{3}) \dots (x - x_{k})}{(x_{1} - x_{2}) (x_{1} - x_{3}) \dots (x_{1} - x_{k})} \\ + F (x_{2}) \frac{(0 - x_{1}) (0 - x_{3}) \dots (0 - x_{k})}{(x_{2} - x_{1}) (x_{2} - x_{3}) \dots (x_{2} - x_{k})} \\ + \dots \\ + F (x_{k}) \frac{(0 - x_{1}) (0 - x_{2}) \dots (0 - x_{k - 1})}{(x_{k} - x_{1}) (x_{k} - x_{2}) \dots (x_{k} - x_{k - 1})} \\ = {(- 1)}^{k - 1} [F (x_{1}) \frac{x_{2} x_{3} \dots x_{k}}{(x_{1} - x_{2}) (x_{1} - x_{3}) \dots (x_{1} - x_{k})}] \\ + F (x_{2}) \frac{x_{1} x_{3} \dots x_{k}}{(x_{2} - x_{1}) (x_{2} - x_{3}) \dots (x_{2} - x_{k})} \\ + \dots \\ + F (x_{k}) \frac{x_{1} x_{2} \dots x_{k - 1}}{(x_{k} - x_{1}) (x_{k} - x_{2}) \dots (x_{k} - x_{k - 1})} \end{array} (16.15)$

16.4 Proposed Scheme

Following on the details described in the previous discussions, this section presents a detailed and complete description of the proposed scheme. In our scheme, a halftone image HI is created from the grayscale secret image GI, sized H × W with 8 bits per pixel, by using an error diffusion technique called EDT. The transmitted stego-image is called SI and the reconstructed grayscale secret image is called GI′. The proposed scheme includes two procedures: the first is the sharing and embedding phase, and the second is the reconstruction and verifying phase. General flowcharts of the phases of our scheme appear in Figure 16.17 and Figure 16.18.

16.4.1 Sharing and Embedding Phase

A detailed algorithm for the sharing and embedding phase is described in this section.

Input: The secret grayscale image GI and cover image CI.

Output: Stego-image SI.

Step 1: Apply the error diffusion technique (EDT) to the grayscale image GI to retrieve a halftone image HI Obviously, the width and height of HI are W and H. Moreover, each pixel in halftone image HI contains only 1 bit.

Images

FIGURE 446.16
The flowchart of the work by the sender.

Images

FIGURE 16.18
The flowchart of the work by the recipient.

Step 2: Divide halftone image HI into Z nonoverlapping 6-bit blocks, $Z = ⌊ \frac{H \times W}{6} ⌋$ $Z = ⌊ \frac{H \times W}{6} ⌋$ . HI_z (z = 1,2,…,Z) is the z-th block of HI and the value of HI_z, is denoted as P_z illustrated in Figure 16.19.

Images

FIGURE 16.19
The z-th block of GI and the corresponding HI_z, P_z.

Step 3: This is the basic process for secret image sharing with P_z as the secret, z = 1, 2, … Z, $Z = ⌊ \frac{H \times W}{6} ⌋$ $Z = ⌊ \frac{H \times W}{6} ⌋$ . This procedure contains five substeps, which are performed as follows.

Take the value X_i formed from 2-MSBs (Most Significant Bits) of the four pixels of each cover CB_i as the value x specified in Equation 16.16, i = 1, 2 …, n, as shown in Figure 16.20, X_i = (c₇c₆d₇d₆g₇g₆h₇h₆)_D.

$F (x_{i}) = (s + a_{1} \times x_{i}^{1} + a_{2} \times x_{i}^{2} + \dots + a_{k - 1} \times x_{i}^{k - 1}) m o d 2^{6} (16.16)$ $F (x_{i}) = (s + a_{1} \times x_{i}^{1} + a_{2} \times x_{i}^{2} + \dots + a_{k - 1} \times x_{i}^{k - 1}) m o d 2^{6} (16.16)$
Take the secret P_z as the value s specified in Equation 16.16.
With a random number generator, generate a set of k − 1 integers a₁, a₂, a_k₋₁ in Equation 16.16, where k ≤ n.
For each X_i, compute the corresponding value of F(X_i) by Equation 16.16 to form a secret share (X_i, F(X_i)) for each participant in the secret sharing group, F(X_i) = f₅ f₄ f₃ f₂ f₁ f_0.
Hide the six data bits of F(X_i) in the Least Significant Bits of the four pixels C_i, D_i, G_i, and H_i of the corresponding cover block C B_i as shown in Figure 16.21.

Images

FIGURE 448.16
The four pixels of each cover block CBi.

Step 4: To prevent illicit attempts, a simple authentication ability is added here. Compute check bits pi by using Equation 16.17 and embed pi into the remaining LSBs of C_i, D_i, G_i, H_i from the same cover block where i = 1, 2, …, t. Note that t is the total number of check bits, which is discretionary and could be decided by the sender according to authentication strength. For simplicity, we take t = 2 as an example to explain the procedure as shown in Figure 16.22. Figure 16.23 illustrates a flowchart of this phase.

Images

FIGURE 16.21
Hiding the six data bits of F(Xi).

{\begin{array}{l} T = c_{7} c_{6} c_{5} c_{4} c_{3} c_{2} f_{5} f_{4} ‖ d_{7} d_{6} d_{5} d_{4} d_{3} d_{2} f_{3} f_{2} ‖ g_{7} g_{6} g_{5} g_{4} g_{3} g_{2} f_{1} ‖ h_{7} h_{6} h_{5} h_{4} h_{3} h_{2} f_{0} \\ P = T m o d 2^{t} \\ P = {p_{i} | i \in {1, 2, \dots t}, p_{i} \in {0, 1}} \end{array} (16.17)

${\begin{array}{l} T = c_{7} c_{6} c_{5} c_{4} c_{3} c_{2} f_{5} f_{4} ‖ d_{7} d_{6} d_{5} d_{4} d_{3} d_{2} f_{3} f_{2} ‖ g_{7} g_{6} g_{5} g_{4} g_{3} g_{2} f_{1} ‖ h_{7} h_{6} h_{5} h_{4} h_{3} h_{2} f_{0} \\ P = T m o d 2^{t} \\ P = {p_{i} | i \in {1, 2, \dots t}, p_{i} \in {0, 1}} \end{array} (16.17)$

Images

FIGURE 16.22
Hiding the check bits p₁, p₂.

16.4.2 Reconstruction and Verifying Phase

This section describes the proposed secret recovery scheme and authentication scheme. Recall that after performing the secret sharing process for a group of n participants, each participant obtains one stego-image $S {I^{'}}_{j}$ $S {I^{'}}_{j}$ . The proposed process for stego-image authentication and secret image recovery is summarized in the following paragraphs.

Input: The random number generator used to generate integers a₁, a₂, …, a_k₋₁ in Equation 16.16, the secret key t used for generating the check bits (e.g., t = 2), and a set of at least k stego-images $S {I^{'}}_{j}$ $S {I^{'}}_{j}$ , say m ones, with k ≤ m ≤ n, j =1, 2, …, m.

Output: A report of failure of secret reconstruction, or the recovered secret image GI′ if all the stego-images are authenticated as genuine.

Step 1: Use the random number generator to generate a₁, a₂, a_k₋₁ in Equation 16.16.

Images

FIGURE 450.16
The flowchart of Step 4.

Step 2: Divide each received stego-image $S {I^{'}}_{j}$ $S {I^{'}}_{j}$ , j = 1, 2,…, m, into 2 × 2 blocks $C {B^{'}}_{1}, C {B^{'}}_{2}, \dots, C {B^{'}}_{z}$ $C {B^{'}}_{1}, C {B^{'}}_{2}, \dots, C {B^{'}}_{z}$ and denote the four pixels in each block $C {B^{'}}_{z}$ $C {B^{'}}_{z}$ as ${C^{'}}_{z}, {D^{'}}_{z}, {G^{'}}_{z}$ ${C^{'}}_{z}, {D^{'}}_{z}, {G^{'}}_{z}$ , and ${H^{'}}_{z}$ ${H^{'}}_{z}$ as shown in Figure 16.24.

Step 3: For each stego-image $S {I^{'}}_{j}$ $S {I^{'}}_{j}$ from participant j, j ∈ {1, 2,…, m}, perform the following substeps for stego-image authentication.

t = 2, extract the 2-bit check bits from each block $C {B^{'}}_{z}$ $C {B^{'}}_{z}$ , as shown in Figure 16.25. $P_{2} = {g^{'}}_{1}, P_{1} = {h^{'}}_{1}$ $P_{2} = {g^{'}}_{1}, P_{1} = {h^{'}}_{1}$ .
Calculate the data for verification according to Equation 16.18.

FIGURE 451.16
The four pixels of each stego block CB′j.

${\begin{array}{l} T = {C^{'}}_{z} ‖ D^{'} ‖ {G^{'}}_{z} - {g^{'}}_{1} ‖ {H^{'}}_{z} - {h^{'}}_{1} \\ P = T^{'} m o d 2^{t} \\ P^{'} = {{p^{'}}_{i} | i \in {1, 2, \dots t}, {p^{'}}_{i} \in {0, 1}} \end{array}, (16.18)$ ${\begin{array}{l} T = {C^{'}}_{z} ‖ D^{'} ‖ {G^{'}}_{z} - {g^{'}}_{1} ‖ {H^{'}}_{z} - {h^{'}}_{1} \\ P = T^{'} m o d 2^{t} \\ P^{'} = {{p^{'}}_{i} | i \in {1, 2, \dots t}, {p^{'}}_{i} \in {0, 1}} \end{array}, (16.18)$
If for each block, ${P^{'}}_{2} = p_{2}, {P^{'}}_{1} = p_{1}$ ${P^{'}}_{2} = p_{2}, {P^{'}}_{1} = p_{1}$ , then regard the stego-image as having passed authentication and continue; otherwise, decide that the stego-image has been tampered with.

Images

FIGURE 16.25
The 2-bit check bits carried in CB’z when t = 2.

Images

FIGURE 452.16
The bits of X_i and F(X_i) carried in the stego block.

Step 4: If m′ stego-images have passed authentication in Step 3, and m′ ≥ k, then continue. For each collected stego-image $S {I^{'}}_{i}, S {I^{'}}_{i} = S I_{i}$ $S {I^{'}}_{i}, S {I^{'}}_{i} = S I_{i}$ ; otherwise, stop the program and report failure of the secret recovery step.

Step 5: For each z =1, 2, …, Z, $Z = ⌊ \frac{H \times W}{6} ⌋$ $Z = ⌊ \frac{H \times W}{6} ⌋$ , perform the following sub-steps to recover the secret data P_z.

For each $S {I^{'}}_{i}, i \in {1, 2, \dots m^{'}}$ $S {I^{'}}_{i}, i \in {1, 2, \dots m^{'}}$ , extract the 2 most significant bits (MSBs) of the four pixels of each cover as the value X_i specified in Equation 16.16, $X = {({c^{'}}_{7} {c^{'}}_{6} {d^{'}}_{7} {d^{'}}_{6} {g^{'}}_{7} {g^{'}}_{6} {h^{'}}_{7} {h^{'}}_{6})}_{D}$ $X = {({c^{'}}_{7} {c^{'}}_{6} {d^{'}}_{7} {d^{'}}_{6} {g^{'}}_{7} {g^{'}}_{6} {h^{'}}_{7} {h^{'}}_{6})}_{D}$ ; extract the data bits of F(X_i) from the LSBs of pixels ${C^{'}}_{i}, {D^{'}}_{i}, {G^{'}}_{i}$ ${C^{'}}_{i}, {D^{'}}_{i}, {G^{'}}_{i}$ , and ${H^{'}}_{i}$ ${H^{'}}_{i}$ , as shown in Figure 16.26, as a value of F(X_i) appearing in Equation 16.16.
By using the scheme described in Section 16.3.5, compute the corresponding value of y as the value P_z.
For each z = 1, 2, …, Z, $Z = ⌊ \frac{H \times W}{6} ⌋$ $Z = ⌊ \frac{H \times W}{6} ⌋$ , perform last steps to obtain all of the P_z for the blocks of halftone image HI of the secret image GI.

Step 6: Apply the edge- and LUT-based inverse halftoning algorithm (ELUT, introduced in Section 16.3.4) to the halftone image HI to retrieve the gray-scale image GI′, i.e., the secret image.

16.5 Experimental Results

The feasibility of the proposed scheme was confirmed by the experimental results discussed in this section. We conducted three experiments, one to estimate the visual quality of the stego-images; the second to estimate the visual quality of the reconstructed secret images; and the last to evaluate the capability of identifying the tampered region. The test images shown in Figure 16.27 are four grayscale images ” Jet-F16” “Baboon”, “Lena”, and “Pepper”.

For our experiments, we chose the peak-signal-to-noise ratio (PSNR) as the criterion to measure the visual quality of the grayscale images, which is defined in Equation 16.19 and Equation 16.20.

P S N R = 10 l o g_{10} \frac{255^{2}}{M S N} (16.19)

$P S N R = 10 l o g_{10} \frac{255^{2}}{M S N} (16.19)$

M S N = \frac{1}{H \times W} \sum_{h = 1}^{H} \sum_{w = 1}^{W} {(P_{h w} - {P^{'}}_{h w})}^{2} (16.20)

$M S N = \frac{1}{H \times W} \sum_{h = 1}^{H} \sum_{w = 1}^{W} {(P_{h w} - {P^{'}}_{h w})}^{2} (16.20)$

H and W is the height and width of the images P and P′ respectively. P_hw and ${P^{'}}_{h w}$ ${P^{'}}_{h w}$ are the corresponding pixel values, and MSE is the mean-square-error between the two images.

In the first experiment, to compare the visual quality (i.e., PSNRs) between the cover images and the corresponding stego-images in Lin-Tsai’s scheme, Yang et al.’s scheme, Chang et al.’s scheme, and ours, we took the image ” Jet-F16” as the secret image and the images “Lena”, “Pepper,” and “Baboon” as the cover images, as shown in Figure 16.27. Figure 16.28 demonstrates the experimental results. The PSNRs of different schemes reveal that the visual quality of the stego-images generated by our scheme is the best of the schemes compared in our experiments.

To evaluate the visual quality of the recovered gray-scale images, we compared the PSNRs of the reconstructed grayscale images and the original secret image in Figure 16.29. From Figure 16.29, we can see the PSNR of Jet-F16, which is extracted from “Lena”, “Baboon” and “Pepper”, is larger than 30 dB. It means that not only does the revealing function of our scheme work well but also that the visual quality of the secret grayscale image is acceptable.

In addition, storage space and stego-image transmission time are important issues in secret sharing. Consequently, the pixel expansion problem should be eliminated or minimized with any useful secret image sharing scheme. In other words, the size of the cover images used in the sharing algorithm should be no larger than that of their secret images. However, the cover images produced during previous research, which are based on a polynomial approach [9,15,28], are much larger than their secret images. The cover-to-secret image size ratios of the existing schemes and the proposed scheme are listed in Table 16.1 for comparison. From Table 16.1, we can see the cover size/secret size of our scheme is the smallest and the most satisfactory.

Images

FIGURE 16.27
The test images.

To evaluate the capacity to identify a region of the secret image that has been tampered with, we compared the proposed scheme, Lin-Tsai’s scheme, Yang et al.’s scheme, and Chang et al.’s scheme using some manipulated stego-images that satisfy the parity check policy (shown in Figure 16.30).

Both Figure 16.30 and Table 16.2 show the experimental results for the various schemes. These results reveal that, among Lin-Tsai’s scheme, Yang et al.’s scheme, and the proposed scheme, our scheme provides the best authentication capability. In Lin-Tsai’s scheme, there is only one pixel for each block undergoing parity check. As a result, the authentication capability is not very good.

Images

FIGURE 16.28
The experimental results for comparing the PSNR among the past work and ours.

Images

FIGURE 456.16
The visual quality of the reconstructed grayscale image.

In Yang et al.’s scheme, four pixels of each block all undergo the procedure using a hash function. However, their final check bit is computed by using an XOR operation. So, their probability of successful authentication should remain at 50%. In our scheme, two check bits are adopted and the probability of successful authentication could be increased to 75%. On the other hand, compared with Chang et al.’s scheme, in which four check bits are adopted and authentication is implemented by using CRT (the Chinese Remainder Theorem), our proposed scheme has a lower detection ratio while maintaining lower computation complexity. However, because the set of shadows and the reconstructed secret image are generated through simple operations, no computational complexity or pixel expansion occurs with our scheme. Moreover, in practice, the nearly 80% detection ratio is sufficiently effective.

Images

FIGURE 16.30
Three tampered stego-images.

Table 16.1 The cover-to-secret image size ratios of the existing schemes and the proposed scheme.

Schemes	Cover size / secret size
Lin-Tsai’s scheme	4
Yang et al.’s scheme	4
Chang et al.’s scheme	2
Our scheme	2/3

Table 16.2 The detection ratios of different schemes.

Schemes	Detection ratios (DR)
Lin-Tsai’s scheme	0%
Yang et al.’s scheme	52%
Chang et al.’s scheme	97%
Our scheme	79%

16.6 Conclusions

In this chapter, we propose a novel secret image sharing and authentication scheme in which the set of shadows and the reconstructed secret image are generated through simple operations, and no computational complexity or pixel expansion occur. The PSNR value of the reconstructed secret image is larger than 30 dB, and the visual quality of the reconstructed secret gray-scale image is acceptable.

Some research reported in the literature uses steganography as with Shamir’s secret sharing scheme [9,15,28]. However, with these approaches the cover images must be many times larger than their secret images. For a secret image of H × W pixels, for earlier schemes (introduced in Section 16.2), the cover image should be 2H × 2W pixels or 2H × W pixels in size. Such a restriction requires more storage capacity in the cover image and consumes a larger bandwidth during transmission. Experimental results confirm that each shadow generated by our scheme is six times smaller than the secret image. Moreover, the ratio of cover image size and secret image size is reduced to 2/3. This is the primary advantage of our scheme over past work. To compare visual quality between cover images and their corresponding stego-images with the earlier schemes and our proposed scheme, we used several images for our experiments. The experimental results are shown in Figure 16.29. The PSNRs of the various schemes compared demonstrate that the visual quality of the stego-images generated by our scheme is the best. This is the second advantage of our scheme over earlier work. The third advantage of our scheme over past work is that, based on the check bits embedded, our scheme provides an effective solution for verifying the reliability of the set of collected shadows in the context of low computational complexity. Furthermore, experiments confirm that our proposed scheme is suitable for real-time applications.

Bibliography

[1] A. Adhikari, and S. Sikdar, A New (2, n)-Visual Threshold Scheme for Color Images, INDOCRYPT 2003, Lecture Notes in Computer Science, Vol. 2904, pp. 148–161, 2003.

[2] G. R. Blakley, Safe guarding Cryptographic Keys, Proceedings of the National Computer Conference, American Federation of Information Processing Societies, Seoul, Korea, pp. 313–317, 1979.

[3] C. Blundo, A. D. Santis, and M. Naor, Visual Cryptography for Grey Level Images, Information Processing Letters, Vol. 27, pp. 255–259, 2000.

[4] C.C. Chang, C.C. Lin, C.H. Lin, and Y.H. Chen, A Novel Secret Image Sharing Scheme in Color Images Using Small Shadow Images, Information Sciences, Vol. 178, No. 11, pp. 2433–2447, 2008.

[5] Y. F. Chen, Y. K. Chan, C. C. Huang, et. al, A Multiple-Level Visual Secret-Sharing Scheme Without Image Size Expansion, Information Sciences, Vol. 177, No. 21, Part II, pp. 4696–4710, 2007.

[6] C. C. Chang, C. C. Lin, T. H. N. Le, and B. H. Le, A Probabilistic Visual Secret Sharing Scheme for Grayscale Images with Voting Strategy, Intelligent Information Hiding and Multimedia Signal Processing, pp. 184–188, 2008.

[7] C. C. Chang, C. C. Lin, T. H. N. Le, and B. H. Le, A New Probabilistic Visual Secret Sharing Scheme for Color Images, International Symposium on Electronic Commerce and Security, pp. 1305–1308, 2008.

[8] S. Cimato, R. De Prisco, and A. De Santis, Probabilistic Visual Cryptography Schemes, The Computer Journal, Vol. 49, No. 1, pp. 97–107, 2006.

[9] C.C. Chang, Y.P. Hsieh, and C.H. Lin, Sharing Secrets in Stego-images with Authentication, Pattern Recognition, Vol. 41, No. 10, pp. 3130–3137, 2008.

[10] P. C. Chang, C. S. Yu, and T. H. Lee, Hybrid LMS-MMS Inverse Halftoning Technique, IEEE Trans. Image Process., Vol. 10, No. 1, pp. 95–103, 2001.

[11] K. L. Chung and S. T. Wu, Inverse Halftoning Algorithm Using Edge-Based Lookup Table Approach, IEEE Trans. Image Process., Vol. 14, No. 10, pp. 1583–1589, 2005.

[12] J. Canny, A Computational Approach to Edge Detection, IEEE Trans. Pattern Analysis and Machine Intelligence., Vol. 8, No. 6, pp. 679–698, 1986.

[13] J. B. Feng, I. C. Lin, and Y. P. Chu, Halftone Image Resampling by Interpolation and Error-Diffusion, Proceedings of the 2nd International Conference on Ubiquitous Information Management and Communication, pp. 409–413, 2008.

[14] G. Horng, T. Chen, and D. Tasi, Cheating in Visual Cryptography, Designs, Codes and Cryptography, Vol. 38, pp. 219–236, 2006.

[15] C.C. Lin and W.H. Tsai, Secret Image Sharing with Steganography and Authentication, Journal of Systems and Software, Vol. 73, No. 3, pp. 405–414, 2004.

[16] M. Mese and P. P. Vaidyanathan, Look up Table (LUT) Scheme for Inverse Halftoning, IEEE Trans. Image Process., Vol. 10, No. 10, pp. 1566–1578, 2001.

[17] M. Naor and A. Shamir, Visual Cryptography, Advances in Cryptology - Eurocrypt’ 94, Lecture Notes in Computer Science, Vol. 950, pp. 1–12, 1995.

[18] R. D. Prisco and A. D. Santis, Cheating Immune (2, n)-Threshold Visual Secret Sharing, Lecture Notes in Computer Science, Vol. 4116, pp. 216–228, 2006.

[19] L. G. Roberts, Machine Perception of Three-Dimensional Solids, Optical and Electro-Optical Information Processing, pp. 159–197, 1965.

[20] A. Shamir, How to Share a Secret, Communications of ACM, Vol. 22, no. 11, pp. 612–613, 1979.

[21] S. J. Shyu, Efficient Visual Secret Sharing Scheme for Color Images, Pattern Recognition Letters, Vol. 39, No. 5, pp. 866–880, May 2006.

[22] A. Shiozaki, Digital Half-Toning by Error Diffusion with Perturbation, Electronics Letters, Vol. 32, No. 18, pp. 1655–1656, 1996.

[23] C.C. Thien and J.C. Lin, Secret Image Sharing, Computers and Graphics, Vol. 26, No. 5, pp. 765–770, 2002.

[24] C.C. Thien and J.C. Lin, An Image-Sharing Scheme with User-Friendly Shadow Images, IEEE Transactions on Circuits and Systems for Video Technology, Vol. 13, No. 12, pp. 1161–1169, 2003.

[25] R.Z. Wang and C.H. Su, Secret Image Sharing with smaller Shadow Images, Pattern Recognition Letters, Vol. 27, No. 6, pp. 551–555, 2006.

[26] A. Wang, L. Zhang, N. Ma, and X. Li, Two Secret Sharing Schemes Based on Boolean Operations, Pattern Recognition, Vol. 40, pp. 2776–2785, 2007.

[27] N. Yang, New Visual Secret Sharing Schemes Using Probabilistic Schemes, Pattern Recognition Letters, Vol. 25, No. 4, pp. 481–494, 2004.

[28] C.N. Yang, T.S. Chen, K.H. Yu, and C.C. Wang, Improvements of Image Sharing with Steganography and Authentication, Journal of Systems and Software, Vol. 80, No. 7, pp. 1070–1076, 2007.

[29] R. Zhao, J.J. Zhao, F. Dai, and F.Q. Zhao, A new Image Secret Sharing Scheme to Identify Cheaters, Computer Standards and Interfaces, Vol. 31, No. 1, pp. 252–257, 2009.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for
16 Image Sharing with Steganography and Authentication

16

Image Sharing with Steganography and Authentication

CONTENTS

16.1 Introduction

16.2 Related Work

16.2.1 Lin and Tsai’s Scheme

16.2.2 Yang et al.’s Scheme

16.2.3 Chang et al.’s Scheme

16.3 Adopted Techniques in the Proposed Scheme

16.3.1 Error Diffusion Technique

16.3.2 Interpolation Technique

16.3.3 Canny Edge Detector

16.3.4 Edge Lookup Inverse Halftoning Technique

16.3.5 Shamir Scheme for Secret Sharing

16.4 Proposed Scheme

16.4.1 Sharing and Embedding Phase

16.4.2 Reconstruction and Verifying Phase

16.5 Experimental Results

16.6 Conclusions

Bibliography

Table of Contents for 16 Image Sharing with Steganography and Authentication

Create new playlist

Sign In

Sign Up

CONTENTS

Table of Contents for
16 Image Sharing with Steganography and Authentication