# Visual Cryptography Using Computation-Free Bit-Plane Reconstruction

Authors: Ya-Li Liu; Tao Liu; Bin Yan; Jeng-Shyang Pan; Hong-Mei Yang
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Visual cryptography (VC) using bit-plane decomposition improves the quality of the reconstructed image. The disadvantage of this scheme is that the decoder needs computation in order to reconstruct the secret image from its bit-planes. To solve this problem, we propose a no-computation bit-plane decomposition visual cryptography (NC-BPDVC). In NC-BPDVC, we convert the grayscale secret image into a multitone image by multilevel halftoning. Then, by exploring the difference between a digital pixel and a printed dot, we design different dot patterns to render a digital pixel. By doing so, we abandon the usual assumption that DPI (dots per inch) equals PPI (pixels per inch) during printing. By adopting the more realistic assumption that DPI can be larger than PPI as is supported by most printers, we use different patterns to render different tone levels. These patterns are carefully designed so that no computation is needed when one needs to reconstruct the multitone image from its bit-planes. Our algorithm is tested on a batch of twenty standard grayscale images. The experimental results confirm the correctness and advantages of the proposed scheme. Compared with the ordinary bit-plane decomposition VC, NC-BPDVC does not need computation. The security of the proposed algorithm is also analyzed and verified.


---

## Body

## 1. Introduction

As first proposed by Naor and Shamir [1], one advantage of VC (visual cryptography) is a light-weighted decoder, or even a computation-free decoder. The reconstructed image can be recognized by the HVS (human visual system) once the shares are stacked. This feature brings flexibility into applications involving secret sharing. Currently, most VC algorithms aim to solve two main issues. One is to reduce the size expansion; the other is to improve the perceptual quality of the reconstructed image.Three types of VC schemes have been proposed to solve the poor perceptual quality of the reconstructed image in recent years:(1)
Multipixels Encryption VC (MEVC). The main idea of MEVC is to reconstruct the average brightness of an image block [2–4]. The perceptual quality of the reconstructed image using MEVC is better than usual VC schemes [1, 5]. However, the MEVC scheme has the disadvantages of the line problem in the reconstructed image, and the suitable image to be encrypted is a binary image or coarse image.(2)
Halftone VC. Halftone VC converts the grayscale secret image to a binary image by using halftoning and applies binary VC to halftone result [6–10]. Yan et al. proposed an ABS (analysis-by-synthesis) framework by putting VC into an error diffusion loop [11]. Yan’s scheme diffused the error between the reconstructed image and the original secret image to the high-frequency band, thus can improve the perceptual quality of the reconstructed image. Sun et al. proposed an improved scheme by putting VC into direct binary search halftoning loop [12]. Halftone VC has the advantage of a better quality of the reconstructed image than MEVC. However, some fine details of the secret image are lost during the halftoning process, since halftoning is basically a lossy process.(3)
Bit-Plane Decomposition VC. This kind of VC converted the grayscale secret image into bit-planes by converting decimal numbers of gray level into binary numbers. Each bit-plane has a different weight. Then, each bit-plane is encrypted using binary VC. Those schemes got a better perceptual quality of reconstructed image than MEVC and halftone VC [13, 14]. In [13], the secret image can be completely reconstructed. However, in the decoding process, the weight of each bit-plane cannot be used directly without computation. Therefore, the decoding process of those schemes depends on computation.VC via bit-plane decomposition greatly improves the quality of the reconstructed image. However, this scheme needs computation for decoding. Specifically, the decoder needs computation to combine the weight of each bit-plane with the binary image reconstructed in that bit-plane. So, if we are able to combine the weight directly into the reconstructed binary secret image in each bit-plane, then we can achieve computation-free decoding. A computation-free decoder is required for secure online transactions on a device controlled by a Trojan horse [15]. We propose a no-computation bit-plane decomposition visual cryptography (NC-BPDVC).The main contribution of this paper can be summarized as follows:(1)
Combining weights into each bit-plane so that the decoder uses simple stacking to decode the secret image. No computation is needed during decoding.(2)
A set of patterns designed for the weights by exploring the difference between DPI (dots per inch) and PPI (pixels per inch). These patterns are complementary so that patterns for different bit-plane do not interfere with each other once they are stacked.This paper is organized as follows. In Section2, we describe the background knowledge of our proposed NC-BPDVC. Section 3 gives the general framework and details of the proposed NC-BPDVC. Section 4 presents experimental results and discussions. Finally, we conclude this paper in Section 5.


## 2. Related Background

In this section, we briefly introduce the background knowledge on which the proposed algorithm is built, including usual (2, 2)-VC, multilevel halftoning, and ordinary bit-plane decomposition/reconstruction. Usual (2, 2)-VC and multilevel halftoning can be used in NC-BPDVC directly. The ordinary bit-plane decomposition/reconstruction will be improved to achieve the purpose of computation-free in the decoding process in Section3.


### 2.1. Conventional (2, 2)-Threshold VC

The main idea of the (2, 2)-threshold VC scheme is encoding one binary image into two shares through the codebook. LetL × W be the size of the input binary secret image B, and “×” be a separator. Let Bi,j be the current secret pixel, 1 ≤ i ≤ L, 1 ≤ j ≤ W. In Figure 1, we give the codebook of (2, 2)-VC. The process of (2, 2)-VC is described below.Figure 1
Codebook of (2, 2)-VC.IfBi,j is white, select a pair of combinations from the white column in Figure 1 and assign them to the subpixels at the corresponding positions in the shares S1 and S2. Otherwise, select randomly a pair of combinations from the black element column and assign them to the subpixels at the corresponding positions in the shares S1 and S2. The encoding process is repeated until all pixels in image B are processed. In Figure 2, we give an example of (2,2)-VC process. Once the shares S1 and S2 are stacked, the secret image can be reconstructed.Figure 2
Example of (2, 2)-VC on the airplane image. (a) Airplane, (b)S1, (c) S2, (d) reconstructed image.
(a)(b)(c)(d)A VC system should satisfy the contrast condition and the security condition. The contrast condition ensures that the reconstructed image can be visually revealed (or decoded). The security condition ensures that the secret images will not be leaked when an insufficient number of shares is obtained by attacker [1].


### 2.2. Ordinary Bit-Plane Decomposition

For an 8-bit quantized digital image, the grayscale value of each pixel is usually an integer between 0 and 255. So, each pixel can be uniquely represented by an 8-bit binary sequence. Therefore, binary bit-plane decomposition can split the grayscale image into 8 binary bit-planes [13, 14].Given a decimal numberN, one can convert it into binary form by(1)N=∑k=0S−1bk2k=b020⊗b121⊗…⊗bS−12S−1,where bi is the value of the i-th bit-plane with bk∈0,1.In Figure3, we give an example of bit-plane decomposition. This example shows how a four-pixel block is decomposed into eight bit-planes. Reverting the decomposition process, we can reconstruct the pixel block from the eight bit-planes.Figure 3
Example of binary bit-plane decomposition.


### 2.3. Multilevel Halftoning

Multilevel halftoning converts a grayscale image into an image with a smaller number of levels. Typical algorithms include multilevel error diffusion [16, 17] and multilevel dithering [18]. Multilevel halftoning is an extension of binary halftoning [19–23]. Here, we briefly review the multilevel error diffusion method [17].As is shown in Figure4, we present the diagram of multilevel error diffusion. Multilevel error diffusion mainly includes multilevel quantization, error calculation, and error diffusion.Figure 4
Diagram of multilevel error diffusion.We define several symbols to better describe the process of multilevel error diffusion.(1)
P is the number of tones(2)
th and zh are the h-level quantization and output threshold with h∈1,P(3)
K is the error diffusion kernelThrough the multilevel quantization, the multilevel outputG^r,f is represented as(2)G^r,f=z1,ifMr,f<t1,z2,ift1≤Mr,f<t2,…⋮zP,ifMr,f≥tP−1,where Mr,f is the pixel intensity. Let Gr,f and Gr,f′ be the current pixel and the cumulative sum pixel of error diffusion in neighborhood pixel, respectively. Then, Mr,f is represented as(3)Mr,f=Gr,f+Gr,f′.We describe how to getGr,f′. Through error calculation, one can calculate the error between Mr,f and G^r,f by(4)er,f=Mr,f−G^r,f.Then, byK, the error is diffused to the surrounding pixels of the current pixel. As is shown in Figure 5, we give two common error diffusion kernels: Jarvis kernel [20] and Floyd-Steinberg kernel [21]. Compared with Jarvis kernel, Floyd-Steinberg kernel is small, and its computational complexity is small. Therefore, in this paper, we mainly use Floyd-Steinberg kernel [16, 23]. Through error diffusion, we get Gr,f′ by(5)Gr,f′=∑x=01∑z=−10er+x,f+zKx,z.Figure 5
Two error diffusion kernels. (a) Floyd-Steinberg kernel. (b) Jarvis kernel (X denotes the position of the current pixel).
(a)(b)Multilevel quantization is important in multilevel error diffusion. We give an example of it. LetB be the bit depth of the input image. Let t1=2B/P and z1=2B−1/P−1, respectively, be the thresholds and tone levels interval. For example, when P = 4 and B = 8, we get(6)t1=284=64,(7)z1=28−14−1=85.Through (2), we complete multilevel quantization. Therefore, the multilevel output G^r,f is represented as(8)G^r,f=0,ifMr,f<64,85,if64≤Mr,f<128,170,if128≤Mr,f<192,255,ifMr,f≥192.


## 2.1. Conventional (2, 2)-Threshold VC

The main idea of the (2, 2)-threshold VC scheme is encoding one binary image into two shares through the codebook. LetL × W be the size of the input binary secret image B, and “×” be a separator. Let Bi,j be the current secret pixel, 1 ≤ i ≤ L, 1 ≤ j ≤ W. In Figure 1, we give the codebook of (2, 2)-VC. The process of (2, 2)-VC is described below.Figure 1
Codebook of (2, 2)-VC.IfBi,j is white, select a pair of combinations from the white column in Figure 1 and assign them to the subpixels at the corresponding positions in the shares S1 and S2. Otherwise, select randomly a pair of combinations from the black element column and assign them to the subpixels at the corresponding positions in the shares S1 and S2. The encoding process is repeated until all pixels in image B are processed. In Figure 2, we give an example of (2,2)-VC process. Once the shares S1 and S2 are stacked, the secret image can be reconstructed.Figure 2
Example of (2, 2)-VC on the airplane image. (a) Airplane, (b)S1, (c) S2, (d) reconstructed image.
(a)(b)(c)(d)A VC system should satisfy the contrast condition and the security condition. The contrast condition ensures that the reconstructed image can be visually revealed (or decoded). The security condition ensures that the secret images will not be leaked when an insufficient number of shares is obtained by attacker [1].


## 2.2. Ordinary Bit-Plane Decomposition

For an 8-bit quantized digital image, the grayscale value of each pixel is usually an integer between 0 and 255. So, each pixel can be uniquely represented by an 8-bit binary sequence. Therefore, binary bit-plane decomposition can split the grayscale image into 8 binary bit-planes [13, 14].Given a decimal numberN, one can convert it into binary form by(1)N=∑k=0S−1bk2k=b020⊗b121⊗…⊗bS−12S−1,where bi is the value of the i-th bit-plane with bk∈0,1.In Figure3, we give an example of bit-plane decomposition. This example shows how a four-pixel block is decomposed into eight bit-planes. Reverting the decomposition process, we can reconstruct the pixel block from the eight bit-planes.Figure 3
Example of binary bit-plane decomposition.


## 2.3. Multilevel Halftoning

Multilevel halftoning converts a grayscale image into an image with a smaller number of levels. Typical algorithms include multilevel error diffusion [16, 17] and multilevel dithering [18]. Multilevel halftoning is an extension of binary halftoning [19–23]. Here, we briefly review the multilevel error diffusion method [17].As is shown in Figure4, we present the diagram of multilevel error diffusion. Multilevel error diffusion mainly includes multilevel quantization, error calculation, and error diffusion.Figure 4
Diagram of multilevel error diffusion.We define several symbols to better describe the process of multilevel error diffusion.(1)
P is the number of tones(2)
th and zh are the h-level quantization and output threshold with h∈1,P(3)
K is the error diffusion kernelThrough the multilevel quantization, the multilevel outputG^r,f is represented as(2)G^r,f=z1,ifMr,f<t1,z2,ift1≤Mr,f<t2,…⋮zP,ifMr,f≥tP−1,where Mr,f is the pixel intensity. Let Gr,f and Gr,f′ be the current pixel and the cumulative sum pixel of error diffusion in neighborhood pixel, respectively. Then, Mr,f is represented as(3)Mr,f=Gr,f+Gr,f′.We describe how to getGr,f′. Through error calculation, one can calculate the error between Mr,f and G^r,f by(4)er,f=Mr,f−G^r,f.Then, byK, the error is diffused to the surrounding pixels of the current pixel. As is shown in Figure 5, we give two common error diffusion kernels: Jarvis kernel [20] and Floyd-Steinberg kernel [21]. Compared with Jarvis kernel, Floyd-Steinberg kernel is small, and its computational complexity is small. Therefore, in this paper, we mainly use Floyd-Steinberg kernel [16, 23]. Through error diffusion, we get Gr,f′ by(5)Gr,f′=∑x=01∑z=−10er+x,f+zKx,z.Figure 5
Two error diffusion kernels. (a) Floyd-Steinberg kernel. (b) Jarvis kernel (X denotes the position of the current pixel).
(a)(b)Multilevel quantization is important in multilevel error diffusion. We give an example of it. LetB be the bit depth of the input image. Let t1=2B/P and z1=2B−1/P−1, respectively, be the thresholds and tone levels interval. For example, when P = 4 and B = 8, we get(6)t1=284=64,(7)z1=28−14−1=85.Through (2), we complete multilevel quantization. Therefore, the multilevel output G^r,f is represented as(8)G^r,f=0,ifMr,f<64,85,if64≤Mr,f<128,170,if128≤Mr,f<192,255,ifMr,f≥192.


## 3. Proposed Scheme

In this section, we propose the NC-BPDVC. Let one subpattern be a matrix. To realize computation-free bit-plane reconstruction, we carefully designed a set of complementary subpatterns based on their weight.In order to design a set of subpatterns, we need to describe what PPI and DPI are. PPI is usually associated with a digital pixel. For instance, the PPI of a computer displaying one image is 512 × 512 or 1024 × 1024. It means that this image contains 512 × 512 or 1024 × 1024 pixels. DPI is usually associated with a printed dot. For high-quality printing, it is generally set to 600 DPI meaning 600 ink dots per inch. By adopting the more realistic assumption that DPI can be larger than PPI as is supported by most printers, we design printed subpatterns to render a digital pixel.Through a set of subpatterns, a multitone image can be decomposed into independent bit-planes. Reverting the decomposition, a reconstructed multitone image can be obtained combining all bit-planes with their weight. By putting the binary VC encoding/decoding process into the bit-plane decomposition/reconstruction, the proposed NC-BPDVC solves the computational decoding problem compared with [13, 14].


### 3.1. NC-BPDVC Framework

As is shown in Figure6, NC-BPDVC includes an encoder and decoder. Through the encoder, the grayscale secret image is encoded into shares in the form of independent bit-planes. Through the decoder, the shares are decoded into the reconstructed image.Figure 6
Framework of NC-BPDVC.Let us describe the working process of the encoder. The encoder includes bit-plane decomposition and VC encoding. Multilevel halftoning transforms the grayscale secret imageG into the multitone image G^. Through bit-plane decomposition using a set of subpatterns, G^ is decomposed into independent bit-planes. Then, by binary (d, n)-VC encoding, we get the shares.The working process of the decoder is described as follows. Let “⊕” be OR operation and “+” be stacking operation. The decoder includes VC decoding and computation-free bit-plane reconstruction. Through the OR operation on all bit-planes in the same share, we get the reconstructed bit-planes. Simply stacking these, we get the reconstructed secret imageR.


### 3.2. Multilevel Halftoning via Error Diffusion

As is shown in Figure6, multilevel halftoning transforms the grayscale secret image G into the multitone image G^. The multilevel halftoning does not change the size of the secret image. We described the process of error diffusion multilevel halftoning in Section2.3. We summarize the multilevel quantification operation in error diffusion multilevel halftoning as(9)G^r,f=255p−1∗Mr,f255/P−1,where Mr,f rounds Mr,f to the nearest integer towards 0, and “∗” represents the multiplication.In Algorithm 1, we describe the error diffusion multilevel halftoning process. As is shown in Figure7, we give an example of error diffusion multilevel halftoning on the airplane image. We can conclude that when P equals 16, the multitone airplane image has the best perceptual quality. Therefore, in NC-BPDVC, we set the value 16 to P.Figure 7
Different level tone airplane image. (a) Airplane, (b) halftone airplane, (c) 4-level tone airplane, (d) 16-level tone airplane.
(a)(b)(c)(d)Algorithm 1: Multilevel halftoning via error diffusion.
Input:Grayscale imageG, with size L × W.The number of tonesP.Output:Multitone imageG^.(1)
fori from 1 to Ldo(2)
forj from 1 to Wdo(3)
QuantizeMi,j to G^i,j, using:G^i,j=255/P−1∗Mi,j/255/P−1,(4)
Calculate the error betweenMi,j and G^i,jei,j=Mi,j−G^i,j.(5)
Add up the error from the neighboring already process pixels, using:Gi,j′=∑x=01∑z=−10ei+x,j+zKx,z(6)
CalculateMi,j, using:Mi,j=Gi,j+Gi,j′(7)
end for(8)
end for(9)
Output: Multitone image G^.


### 3.3. Computation-Free Bit-Plane Reconstruction

In order to perform computation-free bit-plane reconstruction on the multitone imageG^, we carefully design a set of complementary subpatterns in this section.


#### 3.3.1. Subpatterns and Composite Patterns

We describe how to design a set of complementary subpatterns. In this paper, let value 0 (1) be black (white). The process of designing the first subpattern is selecting half of the positions from a blank matrix. Then, we set the value of all selected blank positions 0. The second subpattern is based on the first subpattern to select half of its blank position to set 0. Repeat the above steps until only one position of the last subpattern is 0. LetYk be k-th subpattern with k∈1,X. Let X be the total number of subpatterns that is related to P. In this paper, X correspondingly equals 2 and 4 when P, respectively, equals 4 and 16. In Algorithm 2, we give the process of designing subpatterns.Algorithm 2: Design a set of subpatterns.
Input:MatricesNk in which all elements are 1, 1 ≤ k ≤ X, size u × u.MatricesYk in which all elements are 1, 1 ≤ k ≤ X, size u × u.Output:SubpatternsYk, size u × u.(1)
fork from 1 to Xdo(2)
Random chose half of the whole blank positions inNk, set value 0 to these positions.(3)
Nk+1 ← Nk.(4)
Set value 1 to positions inNk except positions chosen in step 2,(5)
Yk ← Nk.(6)
end for(7)
Output: Subpatterns Yk.In Figures8 and 9, we give two examples of designing two and four subpatterns when X, respectively, equals 2 and 4. We define the weight of this: all these subpatterns are ordered according to their weight, from high to low.Figure 8
A set of two subpatterns.Figure 9
A set of four subpatterns.Let one composite pattern be a matrix that has the same size as one subpattern. Through subpatterns OR operation in the same set, we get the composite patterns. We define several symbols as follows:(1)
Lety1, y2, …, yk ∈ {0, 1}. Let “◦” be participation symbol that means when the value of yk is 1, the subpattern Yk can participate in the OR operation of obtaining one composite pattern.(2)
LetBs be the s-th composite patterns, where s is positive integers with s ∈ {1, …, P}.In Figure10, we give an example of getting all composite patterns using subpatterns we designed in Figure 8. Therefore, the process of obtaining the composite patterns through different subpatterns combination is summarized as(10)Bs=y1∘Y1⊕y2∘Y2⊕…⊕yk∘Yk.Figure 10
Example of obtaining composite patterns using a set of two subpatterns.In Figure11, we give the four composite patterns obtained by using two subpatterns in Figure 8. In Figure 12, we give the sixteen composite patterns obtained by using four subpatterns in Figure 9. All composite patterns are ordered according to their weight in descending order.Figure 11
Four composite patterns obtained by two subpatterns in Figure8.Figure 12
Sixteen composite patterns obtained by four subpatterns in Figure9.


#### 3.3.2. Bit-Plane Decomposition

In Figure12, we obtain sixteen composite patterns by applying four subpatterns to equation (10). Reverting equation (10), any composite pattern can be decomposed into a set of subpatterns. We refer to this reverting process as bit-plane decomposition. We use an arbitrary digital image G to illustrate this decomposition.Let the size ofG be 1 × 1 with the pixel value 62. In Figure 4, through a 16-level halftoning via error diffusion, G is converted into G^. In Figure 13, through a set of our subpatterns in Figure 9, G^ is in form of four bit-planes. We summarize the process of bit-plane decomposition in Algorithm 3. According to Algorithm 3, a set of bit-planes is ordered.Figure 13
Example of bit-plane decomposition.Algorithm 3: Bit-plane decomposition.
Input:Multitone imageG^, size L × W.A set of subpatternsYk, 1 ≤ k ≤ X, size u × u.Output:Bit-planesTk, 1 ≤ k ≤ X, size u∗L×u∗W./∗∗ is general mathematical multiplication ∗/(1)
fori from 1 to Ldo(2)
forj from 1 to Wdo(3)
fork from 1 to Xdo(4)
Calculate the tone levels intervalz1 by using: z1=2B−1/P−1.(5)
Calculates = G^i,j/z1+ 1.(6)
CalculateBs=y1∘Y1⊕y2∘Y2⊕…⊕yk∘Yk(7)
Tku∗i−1:u∗i,u∗j−1:u∗j←Yk(8)
end for(9)
end for(10)
end for(11)
Output: Bit-planes Tk.


### 3.4. Encoding Process of NC-BPDVC

The main idea of the encoding process in NC-BPDVC is to use VC to process the bit-planes of the multitone imageG^. Each bit-plane is encrypted using ordinary binary VC encode. NC-BPDVC is flexible and suitable for any binary VC. According to a set of complementary subpatterns, there can be only one black pixel in the same position in a set of bit-planes. Therefore, as is shown in Figure 14, if the black pixel is at the same position in a set of reconstructed bit-planes, the final stacking result of that position dose not get affected by which level it is on. The reconstructed bit-planes are obtained by shares. Based on the above, the attacker cannot infer the order of bit-planes in shares.Figure 14
The stacking result relationship between secret and reconstructed bit-planes.LetE (i, j) be the stacking operation result of all the positions (i, j) in secret bit-planes. To get shares based on the (2, 2)-VC codebook, suppose E (i, j) is black. In shares, the pair of bit-planes whose position (2 ∗ i − 1 : 2 ∗ i, 2 ∗ j − 1 : 2 ∗ j) is the black pixel codebook will be randomly determined by a random integer a. As is shown in Figure 15, we give the shares after encoding the secret bit-planes in Figure 13. In Figure 15, the three pairs of green dots represent three black pixels in shares. Supposing one case, the attacker has T11,…,T41. Comparing T11 with T21–T41, the attack cannot infer the first bit-plane. And so on, it also applies in other cases. Therefore, we give the NC-BPDVC encoding process in Algorithm 4.Figure 15
The example of (2, 2)-NC-BPDVC shares.Algorithm 4: The encoding process of (2, 2)-NC-BPDVC.
Input:Bit-planesTk, 1 ≤ k ≤ 4, size u∗L×u∗W.Blank matricesTk1, Tk2, size 2∗u∗L×2∗u∗W.VCB: all blocks used in (2,2)-VC codebook.Output:SharesS1=T11,…,T41, S2=T12,…,T42, with size 2∗u∗L×2∗u∗W.(1)
fori from 1 to u∗Ldo(2)
forj from 1 to u∗Wdo(3)
A ← a randomly chosen 2 × 2 block from VCB.(4)
Ac ← complementary to A.(5)
E (i, j) = T1(i, j) & T2(i, j) & … & T4(i, j)/∗ & represents logic ‘AND’ operations ∗/(6)
a ← generate a random integer between 1 and k(7)
IFE (i, j) = 1(8)
fork = 1 to 4 do(9)
Tk12∗i−1:2∗i,2∗j−1:2∗j←ATk22∗i−1:2∗i,2∗j−1:2∗j←A(10)
end for(11)
Else(12)
fork = 1 to 4 do(13)
IFk = aTk12∗i−1:2∗i,2∗j−1:2∗j←ATk22∗i−1:2∗i,2∗j−1:2∗j←A(14)
ElseTk12∗i−1:2∗i,2∗j−1:2∗j←ATk22∗i−1:2∗i,2∗j−1:2∗j←A(15)
END IF(16)
end for(17)
END IF(18)
end for(19)
end for(20)
Output: Shares S1=T11,…,T41, S2=T12,…,T42.In Figure15, shares which are stored in the form of independent bit-planes are disadvantageous to management. Therefore, each bit-plane is centrally stored in shares. For example, S1=T11,…,T41 can be stored in Figure 16. This form makes the size of shares expand largely. However, after decoding, the size expansion of the (2, 2)-NC-BPDVC reconstructed image is still 2∗u2.Figure 16
Centralized storage of bit-planes in a share.


### 3.5. Decoding Process of NC-BPDVC

As is shown in Figure6, the decoding process of NC-BPDVC includes two parts. Through the shares OR operation, we get the reconstructed bit-planes. The second part is the stacking of reconstructed bit-planes to reconstruct the secret image R. Therefore, we give the NC-BPDVC decoding process in Algorithm 5. According to Algorithm 5, the reconstruction of R is stacking these reconstructed bit-planes with computation-free.Algorithm 5: The decoding process of (2, 2)-NC-BPDVC.
Input:SharesS1=T11,…,T41, S2=T12,…,T42.MatricesTk′ in which all elements are 1, with size 2∗u∗L×2∗u∗W.Output:Reconstructed imageR.(1)
fork from 1 to 4 do(2)
Tk′=Tk1⊕Tk2(3)
end for(4)
fork from 2 to 4 do(5)
R=T1′⊕Tk′(6)
end for(7)
Output: Reconstructed image R.


## 3.1. NC-BPDVC Framework

As is shown in Figure6, NC-BPDVC includes an encoder and decoder. Through the encoder, the grayscale secret image is encoded into shares in the form of independent bit-planes. Through the decoder, the shares are decoded into the reconstructed image.Figure 6
Framework of NC-BPDVC.Let us describe the working process of the encoder. The encoder includes bit-plane decomposition and VC encoding. Multilevel halftoning transforms the grayscale secret imageG into the multitone image G^. Through bit-plane decomposition using a set of subpatterns, G^ is decomposed into independent bit-planes. Then, by binary (d, n)-VC encoding, we get the shares.The working process of the decoder is described as follows. Let “⊕” be OR operation and “+” be stacking operation. The decoder includes VC decoding and computation-free bit-plane reconstruction. Through the OR operation on all bit-planes in the same share, we get the reconstructed bit-planes. Simply stacking these, we get the reconstructed secret imageR.


## 3.2. Multilevel Halftoning via Error Diffusion

As is shown in Figure6, multilevel halftoning transforms the grayscale secret image G into the multitone image G^. The multilevel halftoning does not change the size of the secret image. We described the process of error diffusion multilevel halftoning in Section2.3. We summarize the multilevel quantification operation in error diffusion multilevel halftoning as(9)G^r,f=255p−1∗Mr,f255/P−1,where Mr,f rounds Mr,f to the nearest integer towards 0, and “∗” represents the multiplication.In Algorithm 1, we describe the error diffusion multilevel halftoning process. As is shown in Figure7, we give an example of error diffusion multilevel halftoning on the airplane image. We can conclude that when P equals 16, the multitone airplane image has the best perceptual quality. Therefore, in NC-BPDVC, we set the value 16 to P.Figure 7
Different level tone airplane image. (a) Airplane, (b) halftone airplane, (c) 4-level tone airplane, (d) 16-level tone airplane.
(a)(b)(c)(d)Algorithm 1: Multilevel halftoning via error diffusion.
Input:Grayscale imageG, with size L × W.The number of tonesP.Output:Multitone imageG^.(1)
fori from 1 to Ldo(2)
forj from 1 to Wdo(3)
QuantizeMi,j to G^i,j, using:G^i,j=255/P−1∗Mi,j/255/P−1,(4)
Calculate the error betweenMi,j and G^i,jei,j=Mi,j−G^i,j.(5)
Add up the error from the neighboring already process pixels, using:Gi,j′=∑x=01∑z=−10ei+x,j+zKx,z(6)
CalculateMi,j, using:Mi,j=Gi,j+Gi,j′(7)
end for(8)
end for(9)
Output: Multitone image G^.


## 3.3. Computation-Free Bit-Plane Reconstruction

In order to perform computation-free bit-plane reconstruction on the multitone imageG^, we carefully design a set of complementary subpatterns in this section.


### 3.3.1. Subpatterns and Composite Patterns

We describe how to design a set of complementary subpatterns. In this paper, let value 0 (1) be black (white). The process of designing the first subpattern is selecting half of the positions from a blank matrix. Then, we set the value of all selected blank positions 0. The second subpattern is based on the first subpattern to select half of its blank position to set 0. Repeat the above steps until only one position of the last subpattern is 0. LetYk be k-th subpattern with k∈1,X. Let X be the total number of subpatterns that is related to P. In this paper, X correspondingly equals 2 and 4 when P, respectively, equals 4 and 16. In Algorithm 2, we give the process of designing subpatterns.Algorithm 2: Design a set of subpatterns.
Input:MatricesNk in which all elements are 1, 1 ≤ k ≤ X, size u × u.MatricesYk in which all elements are 1, 1 ≤ k ≤ X, size u × u.Output:SubpatternsYk, size u × u.(1)
fork from 1 to Xdo(2)
Random chose half of the whole blank positions inNk, set value 0 to these positions.(3)
Nk+1 ← Nk.(4)
Set value 1 to positions inNk except positions chosen in step 2,(5)
Yk ← Nk.(6)
end for(7)
Output: Subpatterns Yk.In Figures8 and 9, we give two examples of designing two and four subpatterns when X, respectively, equals 2 and 4. We define the weight of this: all these subpatterns are ordered according to their weight, from high to low.Figure 8
A set of two subpatterns.Figure 9
A set of four subpatterns.Let one composite pattern be a matrix that has the same size as one subpattern. Through subpatterns OR operation in the same set, we get the composite patterns. We define several symbols as follows:(1)
Lety1, y2, …, yk ∈ {0, 1}. Let “◦” be participation symbol that means when the value of yk is 1, the subpattern Yk can participate in the OR operation of obtaining one composite pattern.(2)
LetBs be the s-th composite patterns, where s is positive integers with s ∈ {1, …, P}.In Figure10, we give an example of getting all composite patterns using subpatterns we designed in Figure 8. Therefore, the process of obtaining the composite patterns through different subpatterns combination is summarized as(10)Bs=y1∘Y1⊕y2∘Y2⊕…⊕yk∘Yk.Figure 10
Example of obtaining composite patterns using a set of two subpatterns.In Figure11, we give the four composite patterns obtained by using two subpatterns in Figure 8. In Figure 12, we give the sixteen composite patterns obtained by using four subpatterns in Figure 9. All composite patterns are ordered according to their weight in descending order.Figure 11
Four composite patterns obtained by two subpatterns in Figure8.Figure 12
Sixteen composite patterns obtained by four subpatterns in Figure9.


### 3.3.2. Bit-Plane Decomposition

In Figure12, we obtain sixteen composite patterns by applying four subpatterns to equation (10). Reverting equation (10), any composite pattern can be decomposed into a set of subpatterns. We refer to this reverting process as bit-plane decomposition. We use an arbitrary digital image G to illustrate this decomposition.Let the size ofG be 1 × 1 with the pixel value 62. In Figure 4, through a 16-level halftoning via error diffusion, G is converted into G^. In Figure 13, through a set of our subpatterns in Figure 9, G^ is in form of four bit-planes. We summarize the process of bit-plane decomposition in Algorithm 3. According to Algorithm 3, a set of bit-planes is ordered.Figure 13
Example of bit-plane decomposition.Algorithm 3: Bit-plane decomposition.
Input:Multitone imageG^, size L × W.A set of subpatternsYk, 1 ≤ k ≤ X, size u × u.Output:Bit-planesTk, 1 ≤ k ≤ X, size u∗L×u∗W./∗∗ is general mathematical multiplication ∗/(1)
fori from 1 to Ldo(2)
forj from 1 to Wdo(3)
fork from 1 to Xdo(4)
Calculate the tone levels intervalz1 by using: z1=2B−1/P−1.(5)
Calculates = G^i,j/z1+ 1.(6)
CalculateBs=y1∘Y1⊕y2∘Y2⊕…⊕yk∘Yk(7)
Tku∗i−1:u∗i,u∗j−1:u∗j←Yk(8)
end for(9)
end for(10)
end for(11)
Output: Bit-planes Tk.


## 3.3.1. Subpatterns and Composite Patterns

We describe how to design a set of complementary subpatterns. In this paper, let value 0 (1) be black (white). The process of designing the first subpattern is selecting half of the positions from a blank matrix. Then, we set the value of all selected blank positions 0. The second subpattern is based on the first subpattern to select half of its blank position to set 0. Repeat the above steps until only one position of the last subpattern is 0. LetYk be k-th subpattern with k∈1,X. Let X be the total number of subpatterns that is related to P. In this paper, X correspondingly equals 2 and 4 when P, respectively, equals 4 and 16. In Algorithm 2, we give the process of designing subpatterns.Algorithm 2: Design a set of subpatterns.
Input:MatricesNk in which all elements are 1, 1 ≤ k ≤ X, size u × u.MatricesYk in which all elements are 1, 1 ≤ k ≤ X, size u × u.Output:SubpatternsYk, size u × u.(1)
fork from 1 to Xdo(2)
Random chose half of the whole blank positions inNk, set value 0 to these positions.(3)
Nk+1 ← Nk.(4)
Set value 1 to positions inNk except positions chosen in step 2,(5)
Yk ← Nk.(6)
end for(7)
Output: Subpatterns Yk.In Figures8 and 9, we give two examples of designing two and four subpatterns when X, respectively, equals 2 and 4. We define the weight of this: all these subpatterns are ordered according to their weight, from high to low.Figure 8
A set of two subpatterns.Figure 9
A set of four subpatterns.Let one composite pattern be a matrix that has the same size as one subpattern. Through subpatterns OR operation in the same set, we get the composite patterns. We define several symbols as follows:(1)
Lety1, y2, …, yk ∈ {0, 1}. Let “◦” be participation symbol that means when the value of yk is 1, the subpattern Yk can participate in the OR operation of obtaining one composite pattern.(2)
LetBs be the s-th composite patterns, where s is positive integers with s ∈ {1, …, P}.In Figure10, we give an example of getting all composite patterns using subpatterns we designed in Figure 8. Therefore, the process of obtaining the composite patterns through different subpatterns combination is summarized as(10)Bs=y1∘Y1⊕y2∘Y2⊕…⊕yk∘Yk.Figure 10
Example of obtaining composite patterns using a set of two subpatterns.In Figure11, we give the four composite patterns obtained by using two subpatterns in Figure 8. In Figure 12, we give the sixteen composite patterns obtained by using four subpatterns in Figure 9. All composite patterns are ordered according to their weight in descending order.Figure 11
Four composite patterns obtained by two subpatterns in Figure8.Figure 12
Sixteen composite patterns obtained by four subpatterns in Figure9.


## 3.3.2. Bit-Plane Decomposition

In Figure12, we obtain sixteen composite patterns by applying four subpatterns to equation (10). Reverting equation (10), any composite pattern can be decomposed into a set of subpatterns. We refer to this reverting process as bit-plane decomposition. We use an arbitrary digital image G to illustrate this decomposition.Let the size ofG be 1 × 1 with the pixel value 62. In Figure 4, through a 16-level halftoning via error diffusion, G is converted into G^. In Figure 13, through a set of our subpatterns in Figure 9, G^ is in form of four bit-planes. We summarize the process of bit-plane decomposition in Algorithm 3. According to Algorithm 3, a set of bit-planes is ordered.Figure 13
Example of bit-plane decomposition.Algorithm 3: Bit-plane decomposition.
Input:Multitone imageG^, size L × W.A set of subpatternsYk, 1 ≤ k ≤ X, size u × u.Output:Bit-planesTk, 1 ≤ k ≤ X, size u∗L×u∗W./∗∗ is general mathematical multiplication ∗/(1)
fori from 1 to Ldo(2)
forj from 1 to Wdo(3)
fork from 1 to Xdo(4)
Calculate the tone levels intervalz1 by using: z1=2B−1/P−1.(5)
Calculates = G^i,j/z1+ 1.(6)
CalculateBs=y1∘Y1⊕y2∘Y2⊕…⊕yk∘Yk(7)
Tku∗i−1:u∗i,u∗j−1:u∗j←Yk(8)
end for(9)
end for(10)
end for(11)
Output: Bit-planes Tk.


## 3.4. Encoding Process of NC-BPDVC

The main idea of the encoding process in NC-BPDVC is to use VC to process the bit-planes of the multitone imageG^. Each bit-plane is encrypted using ordinary binary VC encode. NC-BPDVC is flexible and suitable for any binary VC. According to a set of complementary subpatterns, there can be only one black pixel in the same position in a set of bit-planes. Therefore, as is shown in Figure 14, if the black pixel is at the same position in a set of reconstructed bit-planes, the final stacking result of that position dose not get affected by which level it is on. The reconstructed bit-planes are obtained by shares. Based on the above, the attacker cannot infer the order of bit-planes in shares.Figure 14
The stacking result relationship between secret and reconstructed bit-planes.LetE (i, j) be the stacking operation result of all the positions (i, j) in secret bit-planes. To get shares based on the (2, 2)-VC codebook, suppose E (i, j) is black. In shares, the pair of bit-planes whose position (2 ∗ i − 1 : 2 ∗ i, 2 ∗ j − 1 : 2 ∗ j) is the black pixel codebook will be randomly determined by a random integer a. As is shown in Figure 15, we give the shares after encoding the secret bit-planes in Figure 13. In Figure 15, the three pairs of green dots represent three black pixels in shares. Supposing one case, the attacker has T11,…,T41. Comparing T11 with T21–T41, the attack cannot infer the first bit-plane. And so on, it also applies in other cases. Therefore, we give the NC-BPDVC encoding process in Algorithm 4.Figure 15
The example of (2, 2)-NC-BPDVC shares.Algorithm 4: The encoding process of (2, 2)-NC-BPDVC.
Input:Bit-planesTk, 1 ≤ k ≤ 4, size u∗L×u∗W.Blank matricesTk1, Tk2, size 2∗u∗L×2∗u∗W.VCB: all blocks used in (2,2)-VC codebook.Output:SharesS1=T11,…,T41, S2=T12,…,T42, with size 2∗u∗L×2∗u∗W.(1)
fori from 1 to u∗Ldo(2)
forj from 1 to u∗Wdo(3)
A ← a randomly chosen 2 × 2 block from VCB.(4)
Ac ← complementary to A.(5)
E (i, j) = T1(i, j) & T2(i, j) & … & T4(i, j)/∗ & represents logic ‘AND’ operations ∗/(6)
a ← generate a random integer between 1 and k(7)
IFE (i, j) = 1(8)
fork = 1 to 4 do(9)
Tk12∗i−1:2∗i,2∗j−1:2∗j←ATk22∗i−1:2∗i,2∗j−1:2∗j←A(10)
end for(11)
Else(12)
fork = 1 to 4 do(13)
IFk = aTk12∗i−1:2∗i,2∗j−1:2∗j←ATk22∗i−1:2∗i,2∗j−1:2∗j←A(14)
ElseTk12∗i−1:2∗i,2∗j−1:2∗j←ATk22∗i−1:2∗i,2∗j−1:2∗j←A(15)
END IF(16)
end for(17)
END IF(18)
end for(19)
end for(20)
Output: Shares S1=T11,…,T41, S2=T12,…,T42.In Figure15, shares which are stored in the form of independent bit-planes are disadvantageous to management. Therefore, each bit-plane is centrally stored in shares. For example, S1=T11,…,T41 can be stored in Figure 16. This form makes the size of shares expand largely. However, after decoding, the size expansion of the (2, 2)-NC-BPDVC reconstructed image is still 2∗u2.Figure 16
Centralized storage of bit-planes in a share.


## 3.5. Decoding Process of NC-BPDVC

As is shown in Figure6, the decoding process of NC-BPDVC includes two parts. Through the shares OR operation, we get the reconstructed bit-planes. The second part is the stacking of reconstructed bit-planes to reconstruct the secret image R. Therefore, we give the NC-BPDVC decoding process in Algorithm 5. According to Algorithm 5, the reconstruction of R is stacking these reconstructed bit-planes with computation-free.Algorithm 5: The decoding process of (2, 2)-NC-BPDVC.
Input:SharesS1=T11,…,T41, S2=T12,…,T42.MatricesTk′ in which all elements are 1, with size 2∗u∗L×2∗u∗W.Output:Reconstructed imageR.(1)
fork from 1 to 4 do(2)
Tk′=Tk1⊕Tk2(3)
end for(4)
fork from 2 to 4 do(5)
R=T1′⊕Tk′(6)
end for(7)
Output: Reconstructed image R.


## 4. Experimental Results and Discussions

This section mainly includes the experimental setups, comparison in function, performance, and computational complexity, and the feasibility analysis of NC-BPDVC.


### 4.1. Experimental Setups

The proposed NC-BPDVC has the advantages of no-computation in decoding and the better perceptual quality of the reconstructed image compared with [3, 6, 14]. We carried out experiments to prove the advantages. In Table 1, we give the used experimental setups. In Figure 17, we give the example of the reconstructed images through [3, 6] and NC-BPDVC with [1, 5]. We can see that the reconstructed image of NC-BPDVC is better than [3, 6]. We will give quantitative analyses in Section 4.2.1.Table 1
Experimental setups.
Experimental setupsParametersP16X4Secret image512 × 512 grayscale imagesDPI600 DPIPPI1680 × 1050 PPIProgramming environmentMATLAB R2014aVC schemes[3], [6], [14], (2, 2)-NC-BPDVC with [1, 5]Figure 17
Reconstructed image of different schemes on the airplane image. (a) Yang’s scheme [6], (b) Liu’s scheme [3], (c) NC-BPDVC with [1], and (d) NC-BPDVC with [5].
(a)(b)(c)(d)


### 4.2. Comparison

#### 4.2.1. Quality Comparison

To quantitatively evaluate the quality of NC-BPDVC and other algorithms, we use metric parameters peak signal-to-noise rate (PSNR) and mean structural similarity (MSSIM). Algorithms are tested on a batch of twenty standard grayscale images in Figure18.Figure 18
The set of testing images.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)(p)(q)(r)(s)(t)As is shown in Figure19, we give four NC-BPDVC reconstructed images of the secret images that are selected from the testing images. The encoding/decoding process of NC-BPDVC combines binary VC with no-computation bit-plane reconstruction. According to the decoding rules, only black pixels can be completely reconstructed, and only half of the white pixels can be reconstructed. Therefore, the reconstructive image is obviously darker than the original image.Figure 19
Examples of (2, 2)-NC-BPDVC reconstructed images.
(a)(b)(c)(d)In Figure20, we give the PSNR and MSSIM values of [3, 6] and NC-BPDVC. We can conclude that NC-BPDVC is superior to [3, 6] both in structure and tone. [3, 6] Algorithms are designed for binary images; however, NC-BPDVC is designed for multitone image. Therefore, the perceptual quality of NC-BPDVC is better than other algorithms.Figure 20
Testing result of Yang’s scheme [6], Liu’s scheme [3], and NC-BPDVC. (a) PSNR. (b) MSSIM.
(a)(b)


#### 4.2.2. Performance Comparison

We quantitatively tested the proposed scheme in Section4.2.1. The quality of NC-BPDVC is better than [3, 6]. In Table 2, we give the qualitative analysis. Therefore, compared with [14], NC-BPDVC does not need computation in decoding.Table 2
Qualitative comparison of related schemes.
SchemeImage quality of reconstructed imageComputation[6]Fair✕[3]Fair✕[14]High✓Proposed schemeHigh✕


#### 4.2.3. Computational Complexity Comparison

LetC be the time complexity of one scheme. CLW of the proposed and others are linear functions of the secret image size. L and W denote the row and column width of the original secret image which can be estimated. Let the operation time of addition/subtraction be Tad, anyone multiplication/division be Tmu, and one random number generation be Trn.In Table3, we give the total time complexity of [3, 6], and NC-BPDVC. The total time complexity of [3, 6] is both 5LWTad+4LWTmu+LWTrn. The error diffusion kernel of [3, 6] and NC-BPDVC are both Floyd-Steinberg error diffusion kernel. Compared with error diffusion used in [3, 6], the multilevel quantization in multilevel error diffusion of NC-BPDVC brings extra computation. Therefore, the total time complexity of NC-BPDVC is 7LWTad+8LWTmu+LWTrn.Table 3
Comparison of computational complexion.
Operation schemeTadTmuTrn[6]Error diffusion: 5LWError diffusion: 4LWSharing:LW[3]Error diffusion: 5LWError diffusion: 4LWSharing:LWProposed schemeError diffusion: 5LWQuantization: 2LWError diffusion: 4LWQuantization: 4LWSharing:LW


### 4.3. Feasibility Analysis

A VC system should satisfy the contrast condition and the security condition. The following analysis proves that NC-BPDVC satisfies the two conditions. To describe the two conditions, we define some symbols as follows:(1)
LetQ1 (Q2) be the matrix codebook of encoding a white (black) pixel, such as in Figure 1. Each matrix size in Q1 (Q2) is n × m.(2)
Letq1 (q2) be any pair of matrices chosen in Q1 (Q2).(3)
Letq11 (q21), q12 (q22) represent one matrix in q1 (q2). H(q1) is the weight of q1.Letd, n, m, ι, and ζ be nonnegative integers satisfying 1 ≤ ζ ≤ m and 2 ≤ d ≤ n.We give the two conditions of (d, n)-VC [1]as follows:(1)
Contrast condition:Inq1, the OR operation result of any d rows in n rows satisfies(11)H⊕q1|Q1≤ζ−ι∗m.Inq2, the OR operation result of any d rows in n rows satisfies(12)H⊕q2|Q2≥ζ.(2)
Security condition:Inq1 and q2,(13)H⊕q11|q1=H⊕q12|q1=H⊕q21|q2=H⊕q22|q2.In the two conditions described above,(1)
m is the number of pixels in q1 or q2. We call it the pixel expansion and(2)
ι represents the loss in contrast. It is the relative difference in weight between shares from a white pixel and a black pixel in the secret image.As is shown in Table4, we prove the usual (2, 2)-VC satisfies the two conditions. In Figure 13, the bit-planes are independent. Therefore, the process of encoding each bit-plane is noninterfered with each other. In Table 5, we give the two conditions analysis of NC-BPDVC using the encoding process of the first bit-plane. Through the results in Table 5, we proved this process satisfies the two conditions. It is independently encoded bit-planes; therefore, the whole encoding process of NC- BPDVC satisfies the two conditions.Table 4
Condition analysis of (2, 2)-VC.
ConditionsResultsContrastH⊕q1|Q1 = 1/2, H⊕q2|Q2 = 1SecurityH⊕q11|q1 = 1/2, H⊕q12|q1 = 1/2H⊕q21|q2 = 1/2, H⊕q22|q2 = 1/2Table 5
Condition analysis of (2,2)-NC-BPDVC using the 1th bit-plane in Figure15.
ConditionsResultsContrastH⊕q1|Q1 = 1/2, H⊕q2|Q2 = 1SecurityH⊕q11|q1 = 1/2, H⊕q12|q1 = 1/2H⊕q21|q2 = 1/2, H⊕q22|q2 = 1/2


## 4.1. Experimental Setups

The proposed NC-BPDVC has the advantages of no-computation in decoding and the better perceptual quality of the reconstructed image compared with [3, 6, 14]. We carried out experiments to prove the advantages. In Table 1, we give the used experimental setups. In Figure 17, we give the example of the reconstructed images through [3, 6] and NC-BPDVC with [1, 5]. We can see that the reconstructed image of NC-BPDVC is better than [3, 6]. We will give quantitative analyses in Section 4.2.1.Table 1
Experimental setups.
Experimental setupsParametersP16X4Secret image512 × 512 grayscale imagesDPI600 DPIPPI1680 × 1050 PPIProgramming environmentMATLAB R2014aVC schemes[3], [6], [14], (2, 2)-NC-BPDVC with [1, 5]Figure 17
Reconstructed image of different schemes on the airplane image. (a) Yang’s scheme [6], (b) Liu’s scheme [3], (c) NC-BPDVC with [1], and (d) NC-BPDVC with [5].
(a)(b)(c)(d)


## 4.2. Comparison

### 4.2.1. Quality Comparison

To quantitatively evaluate the quality of NC-BPDVC and other algorithms, we use metric parameters peak signal-to-noise rate (PSNR) and mean structural similarity (MSSIM). Algorithms are tested on a batch of twenty standard grayscale images in Figure18.Figure 18
The set of testing images.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)(p)(q)(r)(s)(t)As is shown in Figure19, we give four NC-BPDVC reconstructed images of the secret images that are selected from the testing images. The encoding/decoding process of NC-BPDVC combines binary VC with no-computation bit-plane reconstruction. According to the decoding rules, only black pixels can be completely reconstructed, and only half of the white pixels can be reconstructed. Therefore, the reconstructive image is obviously darker than the original image.Figure 19
Examples of (2, 2)-NC-BPDVC reconstructed images.
(a)(b)(c)(d)In Figure20, we give the PSNR and MSSIM values of [3, 6] and NC-BPDVC. We can conclude that NC-BPDVC is superior to [3, 6] both in structure and tone. [3, 6] Algorithms are designed for binary images; however, NC-BPDVC is designed for multitone image. Therefore, the perceptual quality of NC-BPDVC is better than other algorithms.Figure 20
Testing result of Yang’s scheme [6], Liu’s scheme [3], and NC-BPDVC. (a) PSNR. (b) MSSIM.
(a)(b)


### 4.2.2. Performance Comparison

We quantitatively tested the proposed scheme in Section4.2.1. The quality of NC-BPDVC is better than [3, 6]. In Table 2, we give the qualitative analysis. Therefore, compared with [14], NC-BPDVC does not need computation in decoding.Table 2
Qualitative comparison of related schemes.
SchemeImage quality of reconstructed imageComputation[6]Fair✕[3]Fair✕[14]High✓Proposed schemeHigh✕


### 4.2.3. Computational Complexity Comparison

LetC be the time complexity of one scheme. CLW of the proposed and others are linear functions of the secret image size. L and W denote the row and column width of the original secret image which can be estimated. Let the operation time of addition/subtraction be Tad, anyone multiplication/division be Tmu, and one random number generation be Trn.In Table3, we give the total time complexity of [3, 6], and NC-BPDVC. The total time complexity of [3, 6] is both 5LWTad+4LWTmu+LWTrn. The error diffusion kernel of [3, 6] and NC-BPDVC are both Floyd-Steinberg error diffusion kernel. Compared with error diffusion used in [3, 6], the multilevel quantization in multilevel error diffusion of NC-BPDVC brings extra computation. Therefore, the total time complexity of NC-BPDVC is 7LWTad+8LWTmu+LWTrn.Table 3
Comparison of computational complexion.
Operation schemeTadTmuTrn[6]Error diffusion: 5LWError diffusion: 4LWSharing:LW[3]Error diffusion: 5LWError diffusion: 4LWSharing:LWProposed schemeError diffusion: 5LWQuantization: 2LWError diffusion: 4LWQuantization: 4LWSharing:LW


## 4.2.1. Quality Comparison

To quantitatively evaluate the quality of NC-BPDVC and other algorithms, we use metric parameters peak signal-to-noise rate (PSNR) and mean structural similarity (MSSIM). Algorithms are tested on a batch of twenty standard grayscale images in Figure18.Figure 18
The set of testing images.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)(p)(q)(r)(s)(t)As is shown in Figure19, we give four NC-BPDVC reconstructed images of the secret images that are selected from the testing images. The encoding/decoding process of NC-BPDVC combines binary VC with no-computation bit-plane reconstruction. According to the decoding rules, only black pixels can be completely reconstructed, and only half of the white pixels can be reconstructed. Therefore, the reconstructive image is obviously darker than the original image.Figure 19
Examples of (2, 2)-NC-BPDVC reconstructed images.
(a)(b)(c)(d)In Figure20, we give the PSNR and MSSIM values of [3, 6] and NC-BPDVC. We can conclude that NC-BPDVC is superior to [3, 6] both in structure and tone. [3, 6] Algorithms are designed for binary images; however, NC-BPDVC is designed for multitone image. Therefore, the perceptual quality of NC-BPDVC is better than other algorithms.Figure 20
Testing result of Yang’s scheme [6], Liu’s scheme [3], and NC-BPDVC. (a) PSNR. (b) MSSIM.
(a)(b)


## 4.2.2. Performance Comparison

We quantitatively tested the proposed scheme in Section4.2.1. The quality of NC-BPDVC is better than [3, 6]. In Table 2, we give the qualitative analysis. Therefore, compared with [14], NC-BPDVC does not need computation in decoding.Table 2
Qualitative comparison of related schemes.
SchemeImage quality of reconstructed imageComputation[6]Fair✕[3]Fair✕[14]High✓Proposed schemeHigh✕


## 4.2.3. Computational Complexity Comparison

LetC be the time complexity of one scheme. CLW of the proposed and others are linear functions of the secret image size. L and W denote the row and column width of the original secret image which can be estimated. Let the operation time of addition/subtraction be Tad, anyone multiplication/division be Tmu, and one random number generation be Trn.In Table3, we give the total time complexity of [3, 6], and NC-BPDVC. The total time complexity of [3, 6] is both 5LWTad+4LWTmu+LWTrn. The error diffusion kernel of [3, 6] and NC-BPDVC are both Floyd-Steinberg error diffusion kernel. Compared with error diffusion used in [3, 6], the multilevel quantization in multilevel error diffusion of NC-BPDVC brings extra computation. Therefore, the total time complexity of NC-BPDVC is 7LWTad+8LWTmu+LWTrn.Table 3
Comparison of computational complexion.
Operation schemeTadTmuTrn[6]Error diffusion: 5LWError diffusion: 4LWSharing:LW[3]Error diffusion: 5LWError diffusion: 4LWSharing:LWProposed schemeError diffusion: 5LWQuantization: 2LWError diffusion: 4LWQuantization: 4LWSharing:LW


## 4.3. Feasibility Analysis

A VC system should satisfy the contrast condition and the security condition. The following analysis proves that NC-BPDVC satisfies the two conditions. To describe the two conditions, we define some symbols as follows:(1)
LetQ1 (Q2) be the matrix codebook of encoding a white (black) pixel, such as in Figure 1. Each matrix size in Q1 (Q2) is n × m.(2)
Letq1 (q2) be any pair of matrices chosen in Q1 (Q2).(3)
Letq11 (q21), q12 (q22) represent one matrix in q1 (q2). H(q1) is the weight of q1.Letd, n, m, ι, and ζ be nonnegative integers satisfying 1 ≤ ζ ≤ m and 2 ≤ d ≤ n.We give the two conditions of (d, n)-VC [1]as follows:(1)
Contrast condition:Inq1, the OR operation result of any d rows in n rows satisfies(11)H⊕q1|Q1≤ζ−ι∗m.Inq2, the OR operation result of any d rows in n rows satisfies(12)H⊕q2|Q2≥ζ.(2)
Security condition:Inq1 and q2,(13)H⊕q11|q1=H⊕q12|q1=H⊕q21|q2=H⊕q22|q2.In the two conditions described above,(1)
m is the number of pixels in q1 or q2. We call it the pixel expansion and(2)
ι represents the loss in contrast. It is the relative difference in weight between shares from a white pixel and a black pixel in the secret image.As is shown in Table4, we prove the usual (2, 2)-VC satisfies the two conditions. In Figure 13, the bit-planes are independent. Therefore, the process of encoding each bit-plane is noninterfered with each other. In Table 5, we give the two conditions analysis of NC-BPDVC using the encoding process of the first bit-plane. Through the results in Table 5, we proved this process satisfies the two conditions. It is independently encoded bit-planes; therefore, the whole encoding process of NC- BPDVC satisfies the two conditions.Table 4
Condition analysis of (2, 2)-VC.
ConditionsResultsContrastH⊕q1|Q1 = 1/2, H⊕q2|Q2 = 1SecurityH⊕q11|q1 = 1/2, H⊕q12|q1 = 1/2H⊕q21|q2 = 1/2, H⊕q22|q2 = 1/2Table 5
Condition analysis of (2,2)-NC-BPDVC using the 1th bit-plane in Figure15.
ConditionsResultsContrastH⊕q1|Q1 = 1/2, H⊕q2|Q2 = 1SecurityH⊕q11|q1 = 1/2, H⊕q12|q1 = 1/2H⊕q21|q2 = 1/2, H⊕q22|q2 = 1/2


## 5. Conclusion

In this paper, we propose NC-BPDVC, where a set of complementary subpatterns are designed based on their weight. Through the subpatterns, we directly combine the weight of each reconstructed bit-plane into the reconstructed secret image. Therefore, NC-BPDVC has the advantage of computation-free in reconstructing the secret image. The perceptual quality of the reconstructed image is also improved.



---

*Source: 4617885-2022-06-26.xml*