# Meaningful Image Encryption Based on Reversible Data Hiding in Compressive Sensing Domain

Authors: Ming Li; Haiju Fan; Hua Ren; Dandan Lu; Di Xiao; Yang Li
Journal: Security and Communication Networks
 (2018)

---

## Abstract

A novel method of meaningful image encryption is proposed in this paper. A secret image is encrypted into another meaningful image using the algorithm of reversible data hiding (RDH). High covertness can be ensured during the communication, and the possibility of being attacked of the secret image would be reduced to a very low level. The key innovation of the proposed method is that RDH is applied to compressive sensing (CS) domain, which brings a variety of benefits in terms of image sampling, communication and security. The secret image after preliminary encryption is embedded into the sparse representation coefficients of the host image with the help of the dictionary. The embedding rate could reach 2 bpp, which is significantly higher than those of other state-of-art schemes. In addition, the computational complexity of receiver is reduced. Simulations verify our proposal.


---

## Body

## 1. Introduction

Along with the development of Internet and information science, Internet can definitely provide great convenience to information transmission and processing, but as the same time, severe security problems therein have emerged gradually [1, 2]. Data hiding, as an important method to guarantee secure information transmission, has attracted more and more people’s concern [3, 4]. It has solved the easily-being-attacked problems of Cryptosystem by hiding the existence of data. Most of the methods, however, arbitrarily alter the carrier of information, which result in an unrecoverable host image after the secret information has been extracted by the receiver, and the embedded information may also not be recovered exactly. This is vital in some distortion-unacceptable scenarios. Subsequently, the problem has been solved effectively by the reversible data hiding (RDH) [5–7]. RDH technique may hide the secret messages in digital images, and it has two merits: lossless restoration of host image and lossless extraction of embedded massage. Consequently, RDH has become one effective technique to achieve copyright protection for the host image and covert communication for the embedded message [8–10].Image encryption is a well-known technique to protect the contents of the original images [11–13]. The encrypted result appears as a random image, whose histogram is flat and information entropy is close to 8. Therefore, a secure cryptographic system with large key space and effective encryption mechanism can resist unauthorized user to obtain the original image. But the noise-like image is easily detected and attacked by the hacker during the transmission. If the encryption result presents as a meaningful image, it would be secure visually, and the possibility of being attacked would be dropped down to a very low level. Recently, many researchers contribute to the visually secure encryption scheme [14, 15]. For example, Kanso and Ghebleh [14] first decomposed the host image into four sub-bands denoted by LL, HL, LH and HH, then embedded a scrambled image into the latter three sub-bands. Chai et al. [15] proposed to compress the shuffled plain image and embed it into the host image. In fact, the method to encrypt a plain image into another meaningful image employs the method of data hiding; therefore they have used many common algorithms. Among them, RDH based on lossless compression [6, 16], RDH using difference expansion [17, 18] and RDH using histogram shifting [19, 20] are the most influential methods. It is noticed that, if the secret image is encrypted into a meaningful image, the aim of image encryption (another kind of RDH) is not to protect the host image any more, but to protect the embedded secret image. Therefore, meaningful image encryption can be used for covert communication of the secret image.Compressive sensing (CS), which broke through the Shannon-Nyquist sampling theorem, brings a huge impact on the area of communication. Recently, CS and sparse representation are applied in RDH [15, 21–25]. Xiao et al. [22] embedded the secret data into the AC coefficient of host image and then used compressive sensing to generate the encrypted image. Yamaç et al. [23] proposed to embed the data into the CS measurements. Hua et al. [24] have proposed an informed sparse data hiding system, which embeds the message in the sparse domain and relaxes the sparsity condition. Meanwhile, many researchers tested that CS based RDH is secure to resist multiple attacks, because the measurement matrix or dictionary in CS based RDH is set to be secret. Rachlin and Baron [26] confirmed that it is not possible to reconstruct the signal using only the measurements without knowing the measurement matrix or dictionary. Orsdemir et al. [27] argued that brute attacks to obtain the matrix above were computationally infeasible. Therefore, processing the host image by CS effectively enhanced the security of RDH. In addition, it also broadened the applications of RDH. However, RDH in CS domain is still an attempt, and the computation complexities and the embedding capacities in the existing methods are still not satisfactory.In this paper, enlightened by the idea of encrypting a secret image into another meaningful image which can significantly improve the covertness of the secret image communication, we propose a novel method of meaningful image encryption by combining RDH with CS. The host image is processed by CS, and the key problem of the proposed method is the achievement of RDH in CS domain. The contributions of this paper can be summarized as follows:(
1
) The covertness of the secret image to be encrypted can be ensured by RDH in a meaningful image.(
2
) A novel method of RDH in CS domain is proposed.(
3
) The embedding rate is significantly higher compared with the state-of-art schemes.(
4
) The complexity of computation of receiver is reduced.The rest of this paper is organized as follows. Section2 gives the related works about CS. Our proposed encryption scheme is described in Section 3. Section 4 verifies the proposed scheme via simulations. Comparisons between the proposed scheme and other works are discussed in Section 5. And the last section makes a conclusion of our work.


## 2. The Framework of CS

In this section, we discuss the basic CS theory and the exact recovery condition. Because the host images are usually natural images, they can be compressed by CS theory. Let a host image and its sparse solution beX
∈
R
M
×
1 and Y
∈
R
N
×
1 respectively, then (1)
Y
^
=
a
r
g
m
i
n
Y
Y
0
s.t.
X
=
D
Y
,where D
∈
R
M
×
N is a matrix with full row rank. If we want to reconstruct Y from X, the mutual incoherence property (RIP) [28] must be obeyed, which is showed as follows(2)
μ
≜
m
a
x
i
≠
j
d
i
,
d
j
,
i
,
j
=
0,1
,
…
,
N
-
1
,where d
i and d
j are the ith and jth column vectors of D respectively. Tropp [28] has described the condition to reconstruct Y exactly as follow(3)
K
≜
c
a
r
d
Y
^
<
μ
+
1
2
μ
.This condition requires that the host image must be sparse enough, which is impossible for natural image. Hua et al. [24] proposed that for RDH this condition in (3) can be relaxed as(4)
K
<
M
.In the next section, we will propose how to maximize the embedding capacity by employing this condition above.


## 3. Description of Our Proposed Scheme

### 3.1. The Embedding Process

This section presents the proposed embedding algorithm, whose flowchart is shown in Figure1. As in Figure 1, the embedding algorithm consists of four phases. In the first phase, a plain image can be encrypted by any of the existing cryptosystem. Next, the host image is represented sparsely by a given dictionary. Then, the encrypted plain image is embedded into the sparse coefficients of the host image. At last, the coefficients with message multiply with the new dictionary to generate the final cipher image, which is a meaningful image with visual security.Figure 1
The flowchart of the proposed embedding method.Step 1 (encrypt the plain image).
Let a plain image and its cipher image in the first phase beP
=
{
P
i
j
}
i
=
1
,
j
=
1
m
,
n and C
=
{
C
i
j
}
i
=
1
,
j
=
1
m
,
n. And the cipher image C is called Cipher image 1 in this paper. The plain image can be encrypted by any existing cryptosystem, whose keys are denoted by A
1
,
A
2
,
…
,
A
T in Figure 1. Then we can obtain a vector image c
∈
R
m
n
×
1 of C.Step 2 (represent the host image sparsely).
To compress the host image, we must choose a dictionaryD such as DCT dictionary, wavelet dictionary, noiselets dictionary and so on, which can also be obtained from dictionary learning. Let H
∈
R
M
×
N be a host image, whose vectorized version is h of length M
N. The host vector h can be represented sparsely by D
≜
[
d
1
,
d
2
,
…
,
d
M
N
]
∈
R
M
N
×
M
Nas(5)
Y
˙
=
a
r
g
m
i
n
Y
Y
0
s.t.
h
=
D
Y
,where Y
˙
≜
[
y
1
,
y
2
,
…
,
y
M
N
]
T
∈
R
M
N
×
1. Let the sparsity of h be K, then Y
˙ can be obtained by orthogonal matching pursuit algorithm with the fixed sparsity K. Therefore, the vector Y
˙ would have K nonzero elements. The indices of those nonzero elements are denoted by k
≜
[
k
1
,
k
2
,
…
,
k
K
]. If selecting the K nonzero elements in order, we can get a vector Y
¨
≜
[
y
˙
k
1
,
y
˙
k
2
,
…
,
y
˙
k
K
]
T
∈
R
K
×
1 satisfying(6)
h
˙
=
Φ
Y
¨
,where Φ
≜
[
d
k
1
,
d
k
2
,
…
,
d
k
K
]
∈
R
M
N
×
K and h
˙ is a lossy equivalent of h.Step 3 (embed the message into the coefficients vector of host image).
Let the null space ofΦ
T be Δ
∈
R
M
N
×
(
M
N
-
K
), which satisfying Φ
T
Δ
=
0 and Δ
T
Δ
=
I. We can first construct a new dictionary D
~
=
[
Φ
,
Δ
]
∈
R
M
N
×
M
N. Then the Cipher image 1 is embedded in coefficients vector, which is depicted by Algorithm 1.Algorithm 1:Embed the Cipher image 1 into coefficients vector.
(
1
)
Input: the Cipher image 1 c, sparse coefficients Y
¨
2  c
3
=
[
]; c
2
=
[
]; c
1
=
[
];
3  for
i
=
1
:
m
n
4  c
b
= dec2bin(
c
(
i
)
);
(
5
)   s
3
= bin2dec(getbits(
c
b
,
8
:
7
));
(
6
)   s
2
= bin2dec(getbits(
c
b
,
6
:
4
));
(
7
)   s
1
= bin2dec(getbits(
c
b
,
3
:
1
));
8  for j
=
1
:
3
(
9
)     s
j
=
s
j
+
1;
10   if (
m
o
d
(
s
j
,
2
)
=
=
1
)
(
11
)    s
j
=
s
j
∗
(
-
1
);
(
12
)   end
(
13
)   end
(
14
)   c
3
=
[
c
3; s
3
]; c
2
=
[
c
2; s
2
]; c
1
=
[
c
1; s
1
];
(
15
) end
16
Output:
Y
~
=
[
Y
¨
,
c
3
,
c
2
,
c
1
]In Algorithm1, the function “dec2bin()” converts the decimal number to a binary number and the function “bin2dec()” is opposite. The function “getbits(
c
b
,
i
:
j
)” gets the bits of c
b from the jth bit to the ith bit and constructs a binary number. The typical workflows are introduced as follows. First, by Line (
4
), each pixel of Cipher image 1 is represented by 8-bit binary number. Second, by Line (
5
)–(
7
), each 8-bit binary number is broken up into three parts and transformed to three decimal numbers c
3, c
2 and c
1. These decimal numbers should be small enough to obtain a meaningful cipher image but large enough to eliminate the effect of quantization. Third, we propose parity checks (Line (
10
)–(
12
)) to reduce the quantization error, where even numbers are set to be positive and odd numbers are negative. What’s more, due to the fact that zero is too small to reverse the positive and negative, we add 1 to s
j (Line (
9
)) to avoid the appearance of zero. Last, each group of 8-bit of Cipher image 1 is assigned to three locations of Y
~ for output (Line (
16
)). Meanwhile, the length m
n of c must equal to (
M
N
-
K
)
/
3.Step 4 (generate a meaningful image to transmit).
A vectorx
∈
R
M
N
×
1 can be generated by the following equation(7)
x
=
D
~
Y
~
=
Φ
,
Δ
Y
¨
,
c
3
,
c
2
,
c
1
T
=
Φ
Y
¨
+
Δ
c
~
,where c
~
=
[
c
3
,
c
2
,
c
1
]
T
∈
R
(
M
N
-
K
)
×
1.The meaningful imageX to transmit can be obtained by reshape the vector x. Moreover, because the elements in vector c
~ are much smaller than the minimum value of Y
¨, it has only a small effect on the transmitted image(8)
x
≐
Φ
Y
¨
=
h
˙
.The image quality to transmit depends on the sparsityK. The bigger the sparsity K, the nearer the image approximates to the host image.


### 3.2. The Extraction and Reconstruction Process

This section presents the proposed extraction and reconstruction algorithm, which is shown in Figure2. As shown in Figure 2, this algorithm includes two phases. The first phase is to obtain the plain image by extracting the Cipher image 1 and decrypting it. The second phase is to recover the host image.Figure 2
The flowchart of the proposed extraction and reconstruction method.Step 1 (generate the matrixΦ and its null space Δ).
Based on the vectork and dictionaryD, we can construct the matrix Φ
≜
[
d
k
1
,
d
k
2
,
…
,
d
k
K
] and compute the null space matrix Δ.Step 2 (extract the plain image).
Sub-Step  1. Obtain the Cipher image 1 c
^ by the following Equation(9)
c
^
=
Δ
T
x
r
=
Δ
T
Φ
Y
¨
+
Δ
c
~
=
Δ
T
Δ
c
~
=
c
~
,where x
r is the received cipher image vector. In application, quantification causes that the difference between vectors c
^ and c
~ is 1. But, this quantification error can be eliminated by our parity checks strategy, which can have a great promoting effect on recovering the embedded image exactly. The extraction flows of the Cipher image 1 are shown in Algorithm 2.Algorithm 2:Extract the Cipher image 1.
1
Input: the received Cipher image x
r, the sparsity K
2 Generate Φ and Δ
3  Δ
T
x
r
=
Δ
T
(
Φ
Y
¨
+
Δ
c
~
)
=
Δ
T
Δ
c
~
=
c
~
4
for
i
=
1
:
m
n
-
K
5    v
=
f
i
x
(
c
~
(
i
)
);
6    s
=
s
i
g
n
(
c
~
(
i
)
);
7    if (
m
o
d
v
,
2
=
=
0
)
8       s
v
=
1;
9     else
10      s
v
=
-
1;
11    end
12    if (
s
∗
s
v
=
=
-
1
)
13       v
=
v
+
1;
14    end
15    c
~
~
(
i
)
=
v;
16  end
17  c
~
~
=
c
~
~
-
1
18  c
3
=
c
~
~
(
1
:
(
M
N
-
K
)
/
3
)
19  c
2
=
c
~
~
(
(
M
N
-
K
)
/
3
+
1
:
(
M
N
-
K
)
/
3
∗
2
)
20   c
1
=
c
~
~
(
(
M
N
-
K
)
/
3
∗
2
+
1
:
M
N
-
K
)
21
for
i
=
1
:
(
M
N
-
K
)
/
3
22    s3 = dec2bin(c
3
(
i
));
23    s2 = dec2bin(c
2
(
i
));
24    s1 = dec2bin(c
1
(
i
));
25    s= bin2dec(strcat(
s
3
,
s
2
,
s
1
));
26    c
^
(
i
)
=
s;
27 end
28
Output:
c
^  and  c
~Algorithm2 achieves the recovery of c
~ precisely, which is the inverse of Algorithm 1. In Algorithm 2, the function “fix()” takes out the integer part of a number, the function “sign()” takes out a positive or negative sign of a number and the function “strcat()” concatenates strings. The main flows are discussed as follows. First, by Line (
4
)–(
16
), the sign of c
~ is extracted and its parity is determined to reduce the quantization errors, which correspond to Line (
10
)–(
12
) of Algorithm 1. Second, by Line (
17
), we have all elements of c
~
~ minus 1, which correspond Line (
9
) of Algorithm 1. Third, by Line (
18
)–(
20
), c
~
~ is divided into three parts (high, middle and low bit vectors), which correspond to Line (
4
)–(
7
) of Algorithm 1. Last, by Line (
21
)–(
27
), each cipher pixel is extracted, which correspond to Line (
4
)–(
7
) of Algorithm 1.Sub-Step  2. Decrypt the Cipher image 1 c
^ and obtain the plain image.Step 3 (recover the host image).
(10)
h
^
=
x
r
-
Δ
c
~
=
Φ
Y
¨
=
h
˙
.


## 3.1. The Embedding Process

This section presents the proposed embedding algorithm, whose flowchart is shown in Figure1. As in Figure 1, the embedding algorithm consists of four phases. In the first phase, a plain image can be encrypted by any of the existing cryptosystem. Next, the host image is represented sparsely by a given dictionary. Then, the encrypted plain image is embedded into the sparse coefficients of the host image. At last, the coefficients with message multiply with the new dictionary to generate the final cipher image, which is a meaningful image with visual security.Figure 1
The flowchart of the proposed embedding method.Step 1 (encrypt the plain image).
Let a plain image and its cipher image in the first phase beP
=
{
P
i
j
}
i
=
1
,
j
=
1
m
,
n and C
=
{
C
i
j
}
i
=
1
,
j
=
1
m
,
n. And the cipher image C is called Cipher image 1 in this paper. The plain image can be encrypted by any existing cryptosystem, whose keys are denoted by A
1
,
A
2
,
…
,
A
T in Figure 1. Then we can obtain a vector image c
∈
R
m
n
×
1 of C.Step 2 (represent the host image sparsely).
To compress the host image, we must choose a dictionaryD such as DCT dictionary, wavelet dictionary, noiselets dictionary and so on, which can also be obtained from dictionary learning. Let H
∈
R
M
×
N be a host image, whose vectorized version is h of length M
N. The host vector h can be represented sparsely by D
≜
[
d
1
,
d
2
,
…
,
d
M
N
]
∈
R
M
N
×
M
Nas(5)
Y
˙
=
a
r
g
m
i
n
Y
Y
0
s.t.
h
=
D
Y
,where Y
˙
≜
[
y
1
,
y
2
,
…
,
y
M
N
]
T
∈
R
M
N
×
1. Let the sparsity of h be K, then Y
˙ can be obtained by orthogonal matching pursuit algorithm with the fixed sparsity K. Therefore, the vector Y
˙ would have K nonzero elements. The indices of those nonzero elements are denoted by k
≜
[
k
1
,
k
2
,
…
,
k
K
]. If selecting the K nonzero elements in order, we can get a vector Y
¨
≜
[
y
˙
k
1
,
y
˙
k
2
,
…
,
y
˙
k
K
]
T
∈
R
K
×
1 satisfying(6)
h
˙
=
Φ
Y
¨
,where Φ
≜
[
d
k
1
,
d
k
2
,
…
,
d
k
K
]
∈
R
M
N
×
K and h
˙ is a lossy equivalent of h.Step 3 (embed the message into the coefficients vector of host image).
Let the null space ofΦ
T be Δ
∈
R
M
N
×
(
M
N
-
K
), which satisfying Φ
T
Δ
=
0 and Δ
T
Δ
=
I. We can first construct a new dictionary D
~
=
[
Φ
,
Δ
]
∈
R
M
N
×
M
N. Then the Cipher image 1 is embedded in coefficients vector, which is depicted by Algorithm 1.Algorithm 1:Embed the Cipher image 1 into coefficients vector.
(
1
)
Input: the Cipher image 1 c, sparse coefficients Y
¨
2  c
3
=
[
]; c
2
=
[
]; c
1
=
[
];
3  for
i
=
1
:
m
n
4  c
b
= dec2bin(
c
(
i
)
);
(
5
)   s
3
= bin2dec(getbits(
c
b
,
8
:
7
));
(
6
)   s
2
= bin2dec(getbits(
c
b
,
6
:
4
));
(
7
)   s
1
= bin2dec(getbits(
c
b
,
3
:
1
));
8  for j
=
1
:
3
(
9
)     s
j
=
s
j
+
1;
10   if (
m
o
d
(
s
j
,
2
)
=
=
1
)
(
11
)    s
j
=
s
j
∗
(
-
1
);
(
12
)   end
(
13
)   end
(
14
)   c
3
=
[
c
3; s
3
]; c
2
=
[
c
2; s
2
]; c
1
=
[
c
1; s
1
];
(
15
) end
16
Output:
Y
~
=
[
Y
¨
,
c
3
,
c
2
,
c
1
]In Algorithm1, the function “dec2bin()” converts the decimal number to a binary number and the function “bin2dec()” is opposite. The function “getbits(
c
b
,
i
:
j
)” gets the bits of c
b from the jth bit to the ith bit and constructs a binary number. The typical workflows are introduced as follows. First, by Line (
4
), each pixel of Cipher image 1 is represented by 8-bit binary number. Second, by Line (
5
)–(
7
), each 8-bit binary number is broken up into three parts and transformed to three decimal numbers c
3, c
2 and c
1. These decimal numbers should be small enough to obtain a meaningful cipher image but large enough to eliminate the effect of quantization. Third, we propose parity checks (Line (
10
)–(
12
)) to reduce the quantization error, where even numbers are set to be positive and odd numbers are negative. What’s more, due to the fact that zero is too small to reverse the positive and negative, we add 1 to s
j (Line (
9
)) to avoid the appearance of zero. Last, each group of 8-bit of Cipher image 1 is assigned to three locations of Y
~ for output (Line (
16
)). Meanwhile, the length m
n of c must equal to (
M
N
-
K
)
/
3.Step 4 (generate a meaningful image to transmit).
A vectorx
∈
R
M
N
×
1 can be generated by the following equation(7)
x
=
D
~
Y
~
=
Φ
,
Δ
Y
¨
,
c
3
,
c
2
,
c
1
T
=
Φ
Y
¨
+
Δ
c
~
,where c
~
=
[
c
3
,
c
2
,
c
1
]
T
∈
R
(
M
N
-
K
)
×
1.The meaningful imageX to transmit can be obtained by reshape the vector x. Moreover, because the elements in vector c
~ are much smaller than the minimum value of Y
¨, it has only a small effect on the transmitted image(8)
x
≐
Φ
Y
¨
=
h
˙
.The image quality to transmit depends on the sparsityK. The bigger the sparsity K, the nearer the image approximates to the host image.


## 3.2. The Extraction and Reconstruction Process

This section presents the proposed extraction and reconstruction algorithm, which is shown in Figure2. As shown in Figure 2, this algorithm includes two phases. The first phase is to obtain the plain image by extracting the Cipher image 1 and decrypting it. The second phase is to recover the host image.Figure 2
The flowchart of the proposed extraction and reconstruction method.Step 1 (generate the matrixΦ and its null space Δ).
Based on the vectork and dictionaryD, we can construct the matrix Φ
≜
[
d
k
1
,
d
k
2
,
…
,
d
k
K
] and compute the null space matrix Δ.Step 2 (extract the plain image).
Sub-Step  1. Obtain the Cipher image 1 c
^ by the following Equation(9)
c
^
=
Δ
T
x
r
=
Δ
T
Φ
Y
¨
+
Δ
c
~
=
Δ
T
Δ
c
~
=
c
~
,where x
r is the received cipher image vector. In application, quantification causes that the difference between vectors c
^ and c
~ is 1. But, this quantification error can be eliminated by our parity checks strategy, which can have a great promoting effect on recovering the embedded image exactly. The extraction flows of the Cipher image 1 are shown in Algorithm 2.Algorithm 2:Extract the Cipher image 1.
1
Input: the received Cipher image x
r, the sparsity K
2 Generate Φ and Δ
3  Δ
T
x
r
=
Δ
T
(
Φ
Y
¨
+
Δ
c
~
)
=
Δ
T
Δ
c
~
=
c
~
4
for
i
=
1
:
m
n
-
K
5    v
=
f
i
x
(
c
~
(
i
)
);
6    s
=
s
i
g
n
(
c
~
(
i
)
);
7    if (
m
o
d
v
,
2
=
=
0
)
8       s
v
=
1;
9     else
10      s
v
=
-
1;
11    end
12    if (
s
∗
s
v
=
=
-
1
)
13       v
=
v
+
1;
14    end
15    c
~
~
(
i
)
=
v;
16  end
17  c
~
~
=
c
~
~
-
1
18  c
3
=
c
~
~
(
1
:
(
M
N
-
K
)
/
3
)
19  c
2
=
c
~
~
(
(
M
N
-
K
)
/
3
+
1
:
(
M
N
-
K
)
/
3
∗
2
)
20   c
1
=
c
~
~
(
(
M
N
-
K
)
/
3
∗
2
+
1
:
M
N
-
K
)
21
for
i
=
1
:
(
M
N
-
K
)
/
3
22    s3 = dec2bin(c
3
(
i
));
23    s2 = dec2bin(c
2
(
i
));
24    s1 = dec2bin(c
1
(
i
));
25    s= bin2dec(strcat(
s
3
,
s
2
,
s
1
));
26    c
^
(
i
)
=
s;
27 end
28
Output:
c
^  and  c
~Algorithm2 achieves the recovery of c
~ precisely, which is the inverse of Algorithm 1. In Algorithm 2, the function “fix()” takes out the integer part of a number, the function “sign()” takes out a positive or negative sign of a number and the function “strcat()” concatenates strings. The main flows are discussed as follows. First, by Line (
4
)–(
16
), the sign of c
~ is extracted and its parity is determined to reduce the quantization errors, which correspond to Line (
10
)–(
12
) of Algorithm 1. Second, by Line (
17
), we have all elements of c
~
~ minus 1, which correspond Line (
9
) of Algorithm 1. Third, by Line (
18
)–(
20
), c
~
~ is divided into three parts (high, middle and low bit vectors), which correspond to Line (
4
)–(
7
) of Algorithm 1. Last, by Line (
21
)–(
27
), each cipher pixel is extracted, which correspond to Line (
4
)–(
7
) of Algorithm 1.Sub-Step  2. Decrypt the Cipher image 1 c
^ and obtain the plain image.Step 3 (recover the host image).
(10)
h
^
=
x
r
-
Δ
c
~
=
Φ
Y
¨
=
h
˙
.


## 4. Simulation Results

In this section, we verify our proposed embedding and extraction algorithm by experimental results. Without loss of generality, all host images and embedded images are with size512
×
512 and 256
×
256, respectively. Diaconu’s encryption algorithm [29] is chosen to encrypt the plain image. The Dictionary we choose is DCT dictionary.


### 4.1. The Performance of Extraction and Reconstruction

We choose two host images (Baboon and Lena) and one plain image (Lady) to discuss, which are shown as Figures3(a), 3(b) and 3(c). Figure 3(c) is encrypted by Diaconu’s encryption algorithm [29] and the Cipher image 1 is shown in Figure 3(d). Then, Figure 3(d) is embedded in Figures 3(a) and 3(b) respectively. The embedding results are two cipher images Figures 4(a) and 5(a), which are visually secure. Figures 4(b) and 5(b) are the recovered host images from Figures 4(a) and 5(a). Only through our visual sense, we cannot distinguish the differences among the host image, the cipher image and the recovered host image.Figure 3
Host images and encryption and decryption results of the plain image Lady: (a) host image Baboon; (b) host image Lena; (c) plain image Lady; (d) Cipher image 1 of (c); (e) the extracted image; (f) the extracted image.
(a)
(b)
(c)
(d)
(e)
(f)Figure 4
The cipher image Baboon and its reconstruction: (a) the cipher image containing message; (b) the recovered image; (c) the difference image between the original and recovered host image; (d–f) the histograms of Figures3(a), 4(a) and 4(b).
(a)
(b)
(c)
(d)
(e)
(f)Figure 5
The cipher image Lena and its reconstruction: (a) the cipher image containing message; (b) the recovered image; (c) the difference image between the original and recovered host image; (d–f) the histograms of Figures3(b), 5(a) and 5(b).
(a)
(b)
(c)
(d)
(e)
(f)Figure4(c) is the difference image between Figures 3(a) and 4(b),   and Figure 5(c) is the difference image between Figures 3(b) and 5(b). From Figures 4(c) and 5(c), we can conclude that there is very tiny difference between the original host image and its recovered version. One of the applications of RDH is covertly communication, which aims to protect the embedded secret image, then, little distortion of the host image is acceptable in this scenario. To discrmminate more about the differences among the host image, the cipher image and the recovered one, we draw their histograms. Figures 4(d)-4(e) are the histograms of Figures 3(a), 4(a) and 4(b) and Figures 5(d)-5(e) are the histograms of Figures 3(b), 5(a) and 5(b). Because Lena has more grey center of clustering than Baboon, its histograms Figures 5(d)-5(e) are even more telling. From Figures 5(d)-5(e), especially the the labeled regions, we can see that the recovered image is closer to the original host image than the cipher image with message, which varifies the perfermance of our proposed algorithm to recover the host image.The plain images embedded in two host images can be extracted precisely, which are shown in Figures3(e) and 3(f). One can see that the extracted image is exactly the same as Figure 3(a), indicating that the secret image can be covertly transmitted without any distortion.


### 4.2. The Embedding Rate

From Algorithms1 and 2, the embedding rate can be denoted by(11)
e
r
=
8
3
M
N
-
K
M
N
.We explain the concluded embedding rate as follows. Supposing that a host image has M
N pixles and K sparsity, there are M
N
-
K locations in coefficients vector Y
~ to embed message. The length m
n of Cipher image 1 must equal to (
M
N
-
K
)
/
3 as shown in Algorithm 1. Considering that each pixel is 8-bit, the Eq. (11) can be obtained.By our thoroughly experiments, the embedding rate 2 bpp is a proper rate to balance the embedding capacity and reconstruction performance. If we want to achieve 2 bpp embedding rate, the compressive ratioK
/
M
N
=
0.25. In our experiments, for the host image sized 512
×
512 and e
r
=
2
b
p
p, there are M
N
-
K
=
3
M
N
/
4 locations to embed message. For each pixel of Cipher image 1 is assigned to 3 locations, the total pixels of additional plain image should be M
N
/
4. Therefore, we choose a plain image sized 256
×
256 to verify our algorithm as shown in Figure 3.If we want to improve the quality of the recovered image, the parameterK can be increased. Two indexes, Peak signal to Noise Ratio (PSNR) and Structure Similarity (SSIM), are suitable to measure the quality of the recovered host image, which are shown in Eqs. (12) and (13)(12)
P
S
N
R
=
10
l
o
g
10
25
5
2
M
2
N
2
∑
i
=
1
M
2
N
2
H
o
i
-
H
r
i
,where H
o
i and H
r
i denote the ith pixels of the original and recovered host images respectively(13)
S
S
I
M
=
2
μ
x
μ
y
+
C
1
2
σ
x
σ
y
+
C
2
μ
x
2
+
μ
y
2
+
C
1
σ
x
2
+
σ
y
2
+
C
2
,where μ
x and μ
y are mean values of two host images, σ
x and σ
y are standard deviations, C
1 and C
2 are two adjust parameters. For PSNR, a higher value is better; For SSIM, the nearer a value approximates to 1, the better the recovered image is.Figure6 shows that the PSNRs of the recovered host image increase with the raising of compressive ratio (K
/
(
M
N
)) for three test host images, i.e., Lena, Pepper and Baboon. Meanwhile, different images have different reconstruction performances by using a fixed dictionary. For example, the smooth image Lena is more suitable for embedding data while the textured image Baboon is not. Table 1 gives the SSIMs of the recovered host images with the compressive ratios ranging in [
0.25
,
0.75
], where three images Lena, Pepper and Baoon are chosen as host images. From Table 1, one can see that the SSIMs are all close to 1, which show our proposed algorithm has good performance to recover host image. Since the closer to 1 the SSIM the better the reconstruction is, based on the Table 1 we can see Baboon is the least suited to embedding data and Lena is the most suited one. The analysises from Table 1 are consistant with those from Figure 6.Table 1
The SSIM VS. compressive ratio for three host images.
Image
Compressive ratio
0.25
0.3
0.35
0.4
0.45
0.5
0.55
0.6
0.65
0.7
0.75
Lena
0.9912
0.9939
0.9959
0.9972
0.9980
0.9987
0.9990
0.9993
0.9995
0.9997
0.9999
Pepper
0.9868
0.9907
0.9935
0.9954
0.9968
0.9978
0.9984
0.9989
0.9992
0.9995
0.9997
Baboon
0.9778
0.9845
0.9894
0.9926
0.9948
0.9964
0.9975
0.9983
0.9989
0.9993
0.9995Figure 6
The PSNR VS the compressive ratio for three host images.Because the compressive ratio is proportional to the sparityK and the embedding rate decreases with the increasing the sparity K, the embedding rate decreases with the increasing the compressive ratio.


### 4.3. Against Noises

Each pixel of the embedded Cipher image 1 is transformed into 8 bits. These bits are divided into three parts and included in the coefficients vectorY
~ by Line (
4
)–(
7
) of Algorithm 1. Therefore, these coefficients related to the embedded pixels are usually smaller than those of host image. If the cipher image is explosure in noisy invironment during transmition, the smaller coefficients would be influenced seriously. Therefore, the embedded Cipher image 1 is more sensitive to noises than the host image. Figure 7 discusses the sensitivity of the proposed algorithm to the noises. We add two levels “salt & pepper” noises to the received images. Figures 7(a) and 7(d) are the received cipher images, and they are full of “salt & pepper” noises. Figure 7(a) has noise density of 0.001 and Figure 7(d) is with 0.01. Figures 7(b) and 7(e) are the recovered host images, which are closer to the original host image. However, the quality of the extracted images are not satisfactory, as shown in Figures 7(c) and 7(f), which are in the presence of noises. These results manifest that the proposed algorithm has good reconstruction performance in noisy envioronment, but the embedded image is sensitive to noises, and this property can be used to detect the potential attacks which is unconspicuous on the stego-image.Figure 7
Lena and its extracted data in noisy environment: (a) the cipher images with density of 0.001 “salt & pepper” noises; (b) the recovered host image from (a); (c) the extracted plain image from (a); (d) the cipher images with density of 0.01 “salt & pepper” noises; (e) the recovered host image from (d); (c) the extracted plain image from (d).
(a)
(b)
(c)
(d)
(e)
(f)


### 4.4. Complexity

We would present the complexity from two phases: embedding phase, extraction and reconstruction phase. In embedding phase, the complexity of encrypting plain image is related to the size of plain image. Therefore, this complexity isO
(
m
×
n
). As for embedding the Cipher image 1, the complexities are related to the bits of the plain image and the sparse presentation by OMP. Then, the complexities are O
(
8
×
M
×
N
) and O
(
K
×
M
×
N
) respectively, where K is sparity. In summary, the complexity in the embedding phase is close to O
(
K
×
M
×
N
).In extraction and reconstruction phase, the computational complexity can be effectively decreased due to the fact that matrix multiply instead of the CS recovery is executed in this phase, which is one of the main merits of this paper. Then, the complexity in extraction and reconstruction phase is related to multiplication betweenΔ and the cipher image, which is close to O
(
M
×
N
×
(
M
N
-
K
)
). Therefore the total complexity of our algorithm is O
(
M
2
×
N
2
).


## 4.1. The Performance of Extraction and Reconstruction

We choose two host images (Baboon and Lena) and one plain image (Lady) to discuss, which are shown as Figures3(a), 3(b) and 3(c). Figure 3(c) is encrypted by Diaconu’s encryption algorithm [29] and the Cipher image 1 is shown in Figure 3(d). Then, Figure 3(d) is embedded in Figures 3(a) and 3(b) respectively. The embedding results are two cipher images Figures 4(a) and 5(a), which are visually secure. Figures 4(b) and 5(b) are the recovered host images from Figures 4(a) and 5(a). Only through our visual sense, we cannot distinguish the differences among the host image, the cipher image and the recovered host image.Figure 3
Host images and encryption and decryption results of the plain image Lady: (a) host image Baboon; (b) host image Lena; (c) plain image Lady; (d) Cipher image 1 of (c); (e) the extracted image; (f) the extracted image.
(a)
(b)
(c)
(d)
(e)
(f)Figure 4
The cipher image Baboon and its reconstruction: (a) the cipher image containing message; (b) the recovered image; (c) the difference image between the original and recovered host image; (d–f) the histograms of Figures3(a), 4(a) and 4(b).
(a)
(b)
(c)
(d)
(e)
(f)Figure 5
The cipher image Lena and its reconstruction: (a) the cipher image containing message; (b) the recovered image; (c) the difference image between the original and recovered host image; (d–f) the histograms of Figures3(b), 5(a) and 5(b).
(a)
(b)
(c)
(d)
(e)
(f)Figure4(c) is the difference image between Figures 3(a) and 4(b),   and Figure 5(c) is the difference image between Figures 3(b) and 5(b). From Figures 4(c) and 5(c), we can conclude that there is very tiny difference between the original host image and its recovered version. One of the applications of RDH is covertly communication, which aims to protect the embedded secret image, then, little distortion of the host image is acceptable in this scenario. To discrmminate more about the differences among the host image, the cipher image and the recovered one, we draw their histograms. Figures 4(d)-4(e) are the histograms of Figures 3(a), 4(a) and 4(b) and Figures 5(d)-5(e) are the histograms of Figures 3(b), 5(a) and 5(b). Because Lena has more grey center of clustering than Baboon, its histograms Figures 5(d)-5(e) are even more telling. From Figures 5(d)-5(e), especially the the labeled regions, we can see that the recovered image is closer to the original host image than the cipher image with message, which varifies the perfermance of our proposed algorithm to recover the host image.The plain images embedded in two host images can be extracted precisely, which are shown in Figures3(e) and 3(f). One can see that the extracted image is exactly the same as Figure 3(a), indicating that the secret image can be covertly transmitted without any distortion.


## 4.2. The Embedding Rate

From Algorithms1 and 2, the embedding rate can be denoted by(11)
e
r
=
8
3
M
N
-
K
M
N
.We explain the concluded embedding rate as follows. Supposing that a host image has M
N pixles and K sparsity, there are M
N
-
K locations in coefficients vector Y
~ to embed message. The length m
n of Cipher image 1 must equal to (
M
N
-
K
)
/
3 as shown in Algorithm 1. Considering that each pixel is 8-bit, the Eq. (11) can be obtained.By our thoroughly experiments, the embedding rate 2 bpp is a proper rate to balance the embedding capacity and reconstruction performance. If we want to achieve 2 bpp embedding rate, the compressive ratioK
/
M
N
=
0.25. In our experiments, for the host image sized 512
×
512 and e
r
=
2
b
p
p, there are M
N
-
K
=
3
M
N
/
4 locations to embed message. For each pixel of Cipher image 1 is assigned to 3 locations, the total pixels of additional plain image should be M
N
/
4. Therefore, we choose a plain image sized 256
×
256 to verify our algorithm as shown in Figure 3.If we want to improve the quality of the recovered image, the parameterK can be increased. Two indexes, Peak signal to Noise Ratio (PSNR) and Structure Similarity (SSIM), are suitable to measure the quality of the recovered host image, which are shown in Eqs. (12) and (13)(12)
P
S
N
R
=
10
l
o
g
10
25
5
2
M
2
N
2
∑
i
=
1
M
2
N
2
H
o
i
-
H
r
i
,where H
o
i and H
r
i denote the ith pixels of the original and recovered host images respectively(13)
S
S
I
M
=
2
μ
x
μ
y
+
C
1
2
σ
x
σ
y
+
C
2
μ
x
2
+
μ
y
2
+
C
1
σ
x
2
+
σ
y
2
+
C
2
,where μ
x and μ
y are mean values of two host images, σ
x and σ
y are standard deviations, C
1 and C
2 are two adjust parameters. For PSNR, a higher value is better; For SSIM, the nearer a value approximates to 1, the better the recovered image is.Figure6 shows that the PSNRs of the recovered host image increase with the raising of compressive ratio (K
/
(
M
N
)) for three test host images, i.e., Lena, Pepper and Baboon. Meanwhile, different images have different reconstruction performances by using a fixed dictionary. For example, the smooth image Lena is more suitable for embedding data while the textured image Baboon is not. Table 1 gives the SSIMs of the recovered host images with the compressive ratios ranging in [
0.25
,
0.75
], where three images Lena, Pepper and Baoon are chosen as host images. From Table 1, one can see that the SSIMs are all close to 1, which show our proposed algorithm has good performance to recover host image. Since the closer to 1 the SSIM the better the reconstruction is, based on the Table 1 we can see Baboon is the least suited to embedding data and Lena is the most suited one. The analysises from Table 1 are consistant with those from Figure 6.Table 1
The SSIM VS. compressive ratio for three host images.
Image
Compressive ratio
0.25
0.3
0.35
0.4
0.45
0.5
0.55
0.6
0.65
0.7
0.75
Lena
0.9912
0.9939
0.9959
0.9972
0.9980
0.9987
0.9990
0.9993
0.9995
0.9997
0.9999
Pepper
0.9868
0.9907
0.9935
0.9954
0.9968
0.9978
0.9984
0.9989
0.9992
0.9995
0.9997
Baboon
0.9778
0.9845
0.9894
0.9926
0.9948
0.9964
0.9975
0.9983
0.9989
0.9993
0.9995Figure 6
The PSNR VS the compressive ratio for three host images.Because the compressive ratio is proportional to the sparityK and the embedding rate decreases with the increasing the sparity K, the embedding rate decreases with the increasing the compressive ratio.


## 4.3. Against Noises

Each pixel of the embedded Cipher image 1 is transformed into 8 bits. These bits are divided into three parts and included in the coefficients vectorY
~ by Line (
4
)–(
7
) of Algorithm 1. Therefore, these coefficients related to the embedded pixels are usually smaller than those of host image. If the cipher image is explosure in noisy invironment during transmition, the smaller coefficients would be influenced seriously. Therefore, the embedded Cipher image 1 is more sensitive to noises than the host image. Figure 7 discusses the sensitivity of the proposed algorithm to the noises. We add two levels “salt & pepper” noises to the received images. Figures 7(a) and 7(d) are the received cipher images, and they are full of “salt & pepper” noises. Figure 7(a) has noise density of 0.001 and Figure 7(d) is with 0.01. Figures 7(b) and 7(e) are the recovered host images, which are closer to the original host image. However, the quality of the extracted images are not satisfactory, as shown in Figures 7(c) and 7(f), which are in the presence of noises. These results manifest that the proposed algorithm has good reconstruction performance in noisy envioronment, but the embedded image is sensitive to noises, and this property can be used to detect the potential attacks which is unconspicuous on the stego-image.Figure 7
Lena and its extracted data in noisy environment: (a) the cipher images with density of 0.001 “salt & pepper” noises; (b) the recovered host image from (a); (c) the extracted plain image from (a); (d) the cipher images with density of 0.01 “salt & pepper” noises; (e) the recovered host image from (d); (c) the extracted plain image from (d).
(a)
(b)
(c)
(d)
(e)
(f)


## 4.4. Complexity

We would present the complexity from two phases: embedding phase, extraction and reconstruction phase. In embedding phase, the complexity of encrypting plain image is related to the size of plain image. Therefore, this complexity isO
(
m
×
n
). As for embedding the Cipher image 1, the complexities are related to the bits of the plain image and the sparse presentation by OMP. Then, the complexities are O
(
8
×
M
×
N
) and O
(
K
×
M
×
N
) respectively, where K is sparity. In summary, the complexity in the embedding phase is close to O
(
K
×
M
×
N
).In extraction and reconstruction phase, the computational complexity can be effectively decreased due to the fact that matrix multiply instead of the CS recovery is executed in this phase, which is one of the main merits of this paper. Then, the complexity in extraction and reconstruction phase is related to multiplication betweenΔ and the cipher image, which is close to O
(
M
×
N
×
(
M
N
-
K
)
). Therefore the total complexity of our algorithm is O
(
M
2
×
N
2
).


## 5. Comparison and Discussion

In what follows, we compare our proposed algorithm with three CS based RDH methods [22–24].First, we discuss these algorithms from the view of the embedded image. Our proposed algorithm embeds natural image, but Refs. [22–24] embed binary image. Binary image is much sparser than natural image and it is much easier to be embedded.Second, from the view of embedding location, we discuss their differences. In [22], the message is embedded in the AC coefficients, and then is compressed by CS. If one wants to extract the message precisely, the plain image must have ultra-sparse pixels. Yamaç et al. [23] proposed a method to embed data in the measurements, but our method is to embed the data in the sparse coefficients. The embedded locations in Hua et al. [24] are the same as those of our proposed algorithm, but there is drastically difference between them.In [24], Hua et al. expanded possible locations to embed data, and they also dictated that there are M
N
-
K locations for data hiding except the coefficients of host image. At the same time they indicated that multiple chips can be inserted, but the length of multiple chips was not stated explicitly. If inserting multiple chips at the same time, using their detection algorithm multiple chips are inseparable and cannot be extracted precisely. Therefore, they did not give the method how to embed and extract multiple bits. In a word, our proposed work improves Hua’s algorithm in two ways. One is to give a method to embed data into M
N
-
K locations at the same time and to extract them precisely. The other is to insert more than two bits into one location.Last, from the view of embedding rate, our proposed work achieves the largest rate. As previously described, our embedding rate achieves 2 bpp, which is larger than those in [22–24], but it leads to the sensitivity to noises. If we insert one bit into a coefficient location, the demerit (sensitivity to noises) can be made up. The idea is discussed as follows.In Line(
16
) of Algorithm 1, the output can be changed to Y
~
=
[
Y
¨
,
α
b
], where α denotes the embed strength and b
=
{
b
i
}
i
=
1
M
N
-
K represents the embedded bits. If the ith embedded data is 0, then b
i
=
1. If the ith embedded data is 1, then b
i
=
-
1. Thus, the embed rate can achieve (
M
N
-
K
)
/
M
N. If the transmitted cipher image is polluted by noises, the receiver data is changed to(14)
x
~
=
x
+
z
=
Φ
Y
¨
+
Δ
c
~
+
z
,where z is additive noise satisfying z
2
≤
ε. After extracting data like Line (
3
) of Algorithm 2, we can obtain(15)
Δ
T
x
~
=
Δ
T
x
+
z
=
Δ
T
Φ
Y
¨
+
Δ
c
~
+
z
=
c
~
+
Δ
T
z
.For Δ
T
z
2
=
(
Δ
T
z
)
T
(
Δ
T
z
)
=
z
T
Δ
Δ
T
z
=
z
T
z
=
z
2
≤
ε, we can change (15) into (16)
Δ
T
x
~
=
c
~
+
z
~
=
α
b
+
z
~
,where z
~
=
Δ
T
z.When extracting, we can useα
s
i
g
n
(
Δ
T
x
~
)
=
α
s
i
g
n
(
c
~
+
z
~
)
=
α
s
i
g
n
(
α
b
+
z
~
) to replace Line (
5
) of the Algorithm 2. If z
~
∞
<
α, then α
s
i
g
n
(
Δ
T
x
~
)
=
α
b, i.e., the embedded bits can be extracted precisely. In simulation, α is set to be 5.The simulation results are shown from Figures8–10. Figures (a) are the transmitted cipher images. Because each pixel in a binary image can be represented by 1 bit, we embed a binary image Lady in three Figures (a). Figure 8(a) is polluted by Gaussian noise, where noise level is smaller than the embed strength α. From Figure 8(c), we can see the extracted image is without noises. In contrast, the Gaussian noise level in Figure 9(a) is larger than the embed strength and from Figure 9(c) we can see the extracted image is degraded by Gaussian noise. In Figure 10(a), the cipher image is exposed in “salt & pepper” noisy environment. From Figure 10(c), we can see that the extracted result is degraded as same as Figure 9(c). It is because the “salt” noises are much larger than α, and the “pepper” noises cleared some information of transmitted data. In fact, these noises caused by strong Gaussian or “salt & pepper” cannot be eliminated by these methods [22–24].Figure 8
Lena and its extracted data in Gausian noisy environment: (a) the noisy cipher image containing message; (b) the recovered host image; (c) the extracted image.
(a)
(b)
(c)Figure 9
Lena and its extracted data in Gaussian noisy environment: (a) the noisy cipher image containing message; (b) the recovered host image; (c) the extracted image.
(a)
(b)
(c)Figure 10
Lena and its extracted data in “salt & pepper” noisy environment: (a) the noisy cipher image containing message; (b) the recovered host image; (c) the extracted image.
(a)
(b)
(c)We can conclude, for our proposed algorithm in this section, decreasing the embedding rate and embedding a bit in a location of coefficients vector can improve the robustness to noises. If the compressive ratio is stillK
/
M
N
=
0.25, the embedding rate is 0.75 bpp, which is still larger than those in [22–24].


## 6. Conclusions

In this paper, an algorithm for meaningful image encryption is proposed. The main idea is to embed the secret image into the sparse representation of host image to achieve high covertness. Our proposed algorithm has the following merits. First, a novel method of RDH in CS domain is proposed, and the data embedding capacity is significantly higher than other similar schemes. Second, we propose the parity checks strategy to eliminate quantization error. Third, if the transmitted cipher image is not polluted by noises, the embedding rate achieves 2 bpp. And, if the transmitted cipher image is polluted by additive noise with lower level, the embedding rate(
M
N
-
K
)
/
(
M
N
) bpp is equal to the difference between 1 and compressive ratio. Last, we use matrix multiplication in reconstruction phase to decrease computational complexity. In the future, we aim to improve the robustness of the proposed algorithm with lower computational complexity.



---

*Source: 9803519-2018-02-14.xml*