# Reversible Data Hiding Based on Multiple Pairwise PEE and Two-Layer Embedding

Authors: Wenguang He; Gangqiang Xiong; Yaomin Wang
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Recent reversible data hiding (RDH) work tends to realize adaptive embedding by discriminately modifying pixels according to image content. However, further optimization and computational complexity remain great challenges. By presenting a better incorporation of pixel value ordering (PVO) prediction and pairwise prediction-error expansion (PEE) technologies, this paper proposes a new RDH scheme. The largest/smallest three pixels of each block are utilized to generate error-pairs. To achieve optimization of the distribution of error pairs, two-layer embedding is introduced such that full-enclosed pixels of each block can be used to determine how to optimally define the spatial location of pixels within block. Then, to modify error pairs with less distortion introduced, the shifted pairing error is involved in the separable utilization of the other one; i.e., it serves as the context for recalculating the other one. Since the recalculation is equivalent to expansion bins selection, various extensions of original pairwise PEE are designed, parameterized, and combined into the so-called multiple pairwise PEE, with which the 2D histogram can be divided into a set of sub-ones for more accurate modification. The experimental results verify the superiority of the proposed scheme over several PVO-based schemes. On the Kodak image database, the average PSNR gains over original PVO-based pairwise PEE are 0.83 and 0.99 dB for capacities of 10,000 and 20,000 bits, respectively.


---

## Body

## 1. Introduction

REVERSIBLE data hiding (RDH) is a kind of data hiding technology in which some secret message is embedded into the cover media for various purposes such as secret communication and integrity authentication. Moreover, the cover media can be exactly recovered after extracting the hidden data. Compared with traditional data hiding technologies such as digital watermarking whose main concern lies in the robustness against various attacks, RDH is categorized as fragile watermarking technology, and its specific property is to exactly restore the cover media. RDH for uncompressed gray-scale image [1] is the most investigated subject of RDH nowadays. Furthermore, RDH in encrypted domain [2] has also gained increasing attention.In terms of evaluating a RDH scheme, two aspects including fidelity and capacity are usually considered. To achieve desirable trade-off between them, many novel technologies, such as lossless compression [3, 4], histogram shifting [5–7], difference expansion [8], prediction-error expansion [9–12], and integer-to-integer transform [13–16], have been devised. Among them, prediction-error expansion (PEE) has attracted much attention since it can better exploit the spatial redundancy in image. For PEE-based RDH, the target pixel is first predicted to generate prediction error. Then, the obtained errors are expanded or shifted to fulfill data embedding. So far, many advanced prediction methods have been devised to achieve optimization of the distribution of errors or a prediction-error histogram (PEH) [17–22]. For prediction-error modification or PEH manipulation, advanced modification methods such as [23–29] have also been proposed to embed the payload by modifying prediction errors as slightly as possible.Adaptive embedding and high-dimensional PEE are two remarkable achievements in recent years. For example, pixels are adaptively selected for data embedding in [17]. In [29], the obtained errors are classified and embedded with different amounts of data. In [26], the expansion bins are adaptively selected so as to achieve optimal embedding performance. In [23], a histogram sequence is first derived from decomposing the PEH. Then, for each subhistogram the expansion bins are adaptively selected. High-dimensional PEE additionally exploits the correlation of errors by jointly modifying them [25, 27]. For example, pairwise PEE [27] outperforms conventional PEE by introducing more flexible modification of error pairs; i.e., a pair of expandable errors can only be embedded with one of the combinations of bits “00”, “01”, and “10”. Pairwise PEE was firstly incorporated with rhombus prediction [27]. Afterwards, there was also the incorporation of pairwise PEE and pixel value ordering (PVO) prediction [30]. To enhance pairwise PEE by combining expandable errors into a pair, the strategy of adaptive pairing is proposed later [28]. Based on the observation that adaptive pairing actually aims to achieve optimization of the distribution of error pairs, similar optimization is achieved in [31, 32] where pairwise PEE is better incorporated with PVO prediction. Existing pairwise PEE-based schemes have demonstrated the advantage of pairwise PEE in distortion reduction. On the other hand, PVO prediction has been verified to have high accuracy. Therefore, PVO-based pairwise PEE is of great significance to high-fidelity RDH.In this paper, a new RDH scheme is proposed by extending PVO-based pairwise PEE into adaptive embedding from two aspects including adaptive error-pair generation and adaptive error-pair modification. The cover image is first divided into shadow and blank blocks to enable two-layer embedding. In this way, the local complexity of each block can be more precisely computed using full-enclosed pixels, and thus a better selection of pixel blocks for data embedding is presented. For error-pair generation, the largest/smallest three pixels of each block are utilized by improved PVO (IPVO) [33] to generate error pairs. For two correlated pixels, the principle of IPVO can be interpreted as predicting the one having relatively smaller location with the other one. Since errors valued 0 or 1 are expandable in IPVO, it is quite necessary to ensure that the to-be-predicted pixel with relatively smaller location has relatively larger gray value. Based on the above analysis, full-enclosed pixels are additionally used to estimate the distribution of pixels within block and to accordingly fulfill spatial location definition. As for error-pair modification, a key observation lies in that most secret data is embedded into error pairs consisting of one or more shiftable errors. For these error pairs, we propose to use the shifted error to adaptively recalculate the other pairing error. Such recalculation can be equivalent to expansion bins selection. In this way, multiple pairwise PEE is designed and parameterized by the selection of expansion bins. Finally, an efficient mechanism to determine the expansion bins aiming for minimized distortion is also proposed.The rest of the paper is organized as follows. Section2 briefly introduces some related work including PVO, IPVO, and PVO-based pairwise PEE. The proposed scheme is presented in detail in Section 3. The experimental results are given and discussed in Section 4. This paper is concluded in Section 5.


## 2. Related Work

### 2.1. PVO-Based PEE

PVO-based PEE [34] exploits image redundancy in a blockwise manner. After dividing the cover image into nonoverlapped blocks consisting of n pixels, pixels of each block are collected to generate a pixel sequence p1,p2,…,pn. Next, they are sorted to obtain pσ1,pσ2,⋯,pσn where σ:1,⋯,n⟶1,⋯,n is the unique one-to-one mapping such that pσ1≤pσ2≤⋯≤pσn, σi<σj if pσi=pσj and i<j. In this way, the prediction error is computed as(1)PEmax=pσn−pσn−1.To fulfill data embedding,PEmax is modified as(2)PEmax′=PEmax,ifPEmax=0PEmax+b,ifPEmax=1PEmax+1,ifPEmax>1,where b∈0,1. Accordingly, pσn is modified to(3)pσn′=pσn−1+PEmax′=pσn,ifPEmax=0pσn+b,ifPEmax=1pσn+1,ifPEmax>1..


### 2.2. IPVO-Based PEE

In PVO-based PEE, smooth blocks are preferentially selected and a large number of errors valued 0 are thus generated. However, these errors are ignored according to (2), which implies insufficient utilization of smooth blocks. To solve this problem, pixel location is introduced into IPVO-based PEE [33] and the prediction error is renewed as(4)emax=pu−pv,where u=minσn−1,σn,v=maxσn−1,σn. If σn>σn−1, there is emax=pσn−1−pσn≤0; otherwise, there is emax=pσn−pσn−1≥1. Obviously, the relative order of σn−1 and σn remains unchanged after enlarging pσn. In this way, the marked prediction error emax′ is computed as(5)emax′=emax−b,ifemax=0,emax−1,ifemax<0,emax+b,ifemax=1,emax+1,ifemax>1,and accordingly pσn is modified to(6)pσn′=pσn+bifemax=0oremax=1,pσn+1,ifemax<0oremax>1.


### 2.3. PVO-Based Pairwise PEE

Despite the superiority over PVO-based PEE, the performance of IPVO-based PEE is still limited by considering only the largest two pixels. By involving the 3rd largest pixel,emax is reinterpreted as emax=emax1−emax2 in PVO-based pairwise PEE [30] where emax1 and emax2 are computed as(7)emax1=pu−pσn−2,emax2=pv−pσn−2.Obviously, expandable errorsemax∈0,1 in IPVO-based PEE would turn to error pairs emax1,emax2/emax1−emax2∈0,1. In this way, the modification rule of IPVO-based PEE is described as a 2D mapping in Figure 1(a), for which only one pairing error is modifiable.Figure 1
2D mapping of IPVO-based PEE and the one of PVO-based pairwise PEE.
(a)(b)To better utilize the largest three pixels, another 2D mapping is proposed as shown in Figure1(b). Correspondingly, pu and pv will be modified after embedding. For this new mapping, six types of error pairs or error-pair transforms are defined as shown in Figure 2. Among them, Type-D error pair is the most valuable one since it introduces the least distortion per embedding one bit, followed by Type-A, Type-B, Type-C, Type-E, and Type-F error pairs, respectively. Based on such consideration, it is quite necessary to optimize the distribution of various types of error pairs. For example, Type-D error pair consists of two expandable errors. As we can learn from IPVO, more expandable errors can be generated with pixel location involved.Figure 2
Error-pair transforms in PVO-based pairwise PEE.


## 2.1. PVO-Based PEE

PVO-based PEE [34] exploits image redundancy in a blockwise manner. After dividing the cover image into nonoverlapped blocks consisting of n pixels, pixels of each block are collected to generate a pixel sequence p1,p2,…,pn. Next, they are sorted to obtain pσ1,pσ2,⋯,pσn where σ:1,⋯,n⟶1,⋯,n is the unique one-to-one mapping such that pσ1≤pσ2≤⋯≤pσn, σi<σj if pσi=pσj and i<j. In this way, the prediction error is computed as(1)PEmax=pσn−pσn−1.To fulfill data embedding,PEmax is modified as(2)PEmax′=PEmax,ifPEmax=0PEmax+b,ifPEmax=1PEmax+1,ifPEmax>1,where b∈0,1. Accordingly, pσn is modified to(3)pσn′=pσn−1+PEmax′=pσn,ifPEmax=0pσn+b,ifPEmax=1pσn+1,ifPEmax>1..


## 2.2. IPVO-Based PEE

In PVO-based PEE, smooth blocks are preferentially selected and a large number of errors valued 0 are thus generated. However, these errors are ignored according to (2), which implies insufficient utilization of smooth blocks. To solve this problem, pixel location is introduced into IPVO-based PEE [33] and the prediction error is renewed as(4)emax=pu−pv,where u=minσn−1,σn,v=maxσn−1,σn. If σn>σn−1, there is emax=pσn−1−pσn≤0; otherwise, there is emax=pσn−pσn−1≥1. Obviously, the relative order of σn−1 and σn remains unchanged after enlarging pσn. In this way, the marked prediction error emax′ is computed as(5)emax′=emax−b,ifemax=0,emax−1,ifemax<0,emax+b,ifemax=1,emax+1,ifemax>1,and accordingly pσn is modified to(6)pσn′=pσn+bifemax=0oremax=1,pσn+1,ifemax<0oremax>1.


## 2.3. PVO-Based Pairwise PEE

Despite the superiority over PVO-based PEE, the performance of IPVO-based PEE is still limited by considering only the largest two pixels. By involving the 3rd largest pixel,emax is reinterpreted as emax=emax1−emax2 in PVO-based pairwise PEE [30] where emax1 and emax2 are computed as(7)emax1=pu−pσn−2,emax2=pv−pσn−2.Obviously, expandable errorsemax∈0,1 in IPVO-based PEE would turn to error pairs emax1,emax2/emax1−emax2∈0,1. In this way, the modification rule of IPVO-based PEE is described as a 2D mapping in Figure 1(a), for which only one pairing error is modifiable.Figure 1
2D mapping of IPVO-based PEE and the one of PVO-based pairwise PEE.
(a)(b)To better utilize the largest three pixels, another 2D mapping is proposed as shown in Figure1(b). Correspondingly, pu and pv will be modified after embedding. For this new mapping, six types of error pairs or error-pair transforms are defined as shown in Figure 2. Among them, Type-D error pair is the most valuable one since it introduces the least distortion per embedding one bit, followed by Type-A, Type-B, Type-C, Type-E, and Type-F error pairs, respectively. Based on such consideration, it is quite necessary to optimize the distribution of various types of error pairs. For example, Type-D error pair consists of two expandable errors. As we can learn from IPVO, more expandable errors can be generated with pixel location involved.Figure 2
Error-pair transforms in PVO-based pairwise PEE.


## 3. Proposed Scheme

The proposed method is presented in this section. Firstly, the framework of two-layer embedding is introduced and a new calculation of local complexity is presented. Then, error-pair generation and adaptive definition of spatial location are introduced. Finally, multiple pairwise PEE and implementation details are presented.


### 3.1. Two-Layer Embedding

Existing PVO-based schemes are generally implemented by processing blocks in raster-scan order, i.e., from top to bottom and left to right. For each block, its right and bottom neighbors are always recovered before it at decoder such that they can serve as its context. To obtain a better context so as to achieve better pixel block selection, two-layer embedding is introduced into the proposed scheme. As shown in Figure3(a), all pixels except boundary ones are divided into nonoverlapped blocks denoted by “shadow” and “blank,” respectively. During data embedding, shadow blocks are first embedded with half of the secret data and blank blocks are embedded with the remaining half later. At decoder, blank blocks are first recovered after data extraction. Then, shadow blocks are similarly processed later.Figure 3
Image division and complexity measurement.
(a)(b)Referring to Figure3(a), with the nearest four blank blocks serving as the context of a shadow block, a full-enclosed context is thus constructed. The first advantage of the new framework is to more precisely compute the local complexity of each block. In this paper, a complexity measurement NLi is computed considering the absolute difference between two consecutive context pixels. As shown in Figure 3(b), NLi is computed as the sum of all these differences.


### 3.2. Adaptive Error-Pair Generation

For each selected shadow or blank block, the largest three pixels are utilized to generate an error pair. It has been verified by IPVO that more expandable errors can be derived from two correlated pixels by predicting the one having relatively smaller location. Therefore, withu=minσn−1,σn,v=maxσn−1,σn, two pairing errors emax1 and emax2 are computed as(8)emax1=pr1−ps1emax2=pr2−ps2,where r1=minu,σn−2,s1=maxu,σn−2,r2=minv,σn−2,s2=maxv,σn−2. According to IPVO we have expandable errors emax1∈0,1 and emax2∈0,1 here. By combining them into a pair for pairwise PEE, the initial 2D mapping is obtained and shown in Figure 4.Figure 4
Initial 2D mapping for pairwise PEE.To make a comparison between the new 2D mapping in Figure4 (denoted by f) and the original one in Figure 1(b) (denoted by fo), the image Lena is divided into blocks with the size of 4×4. Then, the numbers of all types of error pairs are computed and presented in Table 1. As it is shown, the new 2D mapping f not only achieves capacity improvement, but also introduces less distortion per embedding one bit.Table 1
Performance comparison of various solutions.
MappingDABCEFCapacityDistortionf2444083562060664510 91425 063fo14972283542400127915016919821 506According tof, all of (0, 0), (1, 0), and (1, 1) are Type-D error pairs. Specifically, the correlation between pσn−2 and pu is exploited to generate emax1 while the one between pσn−2 and pv is exploited to generate emax2. To generate more expandable emax1 or emax2 such that more Type-D error pairs can be obtained, the probability of u<v<σn−2 should be promoted. To accomplish this, we propose to adaptively define the spatial location of pixels within block. Suppose the cover image (denoted by I) is divided into a set of h×w sized blocks, for each of which we propose to use horizontal and vertical gradients to estimate the distribution of pixels within block and thus determine how to collect them. With the upper-left pixel located at i0,j0, horizontal gradient Gh and vertical gradient Gv are computed as(9)Gh=1h∑i=i0i0+h−1Ii,j0−1−Ii,j0+w,Gv=1w∑j=j0j0+w−1Ii0−1,j−Ii0+h,j.For example, every pixel is quite likely to have a right neighbor having smaller gray value whenGh>0. In this case, we should collect pixels from left to right so as to ensure pixel having relatively smaller location has relatively larger gray value. Similarly, every pixel is quite likely to have a bottom neighbor having smaller gray value when Gv>0. In that case, we should collect pixels from top to bottom. By combining Gh and Gv, eight modes of spatial location definition are summarized and presented in Figure 5, taking block with the size of 3 × 4 as an example. Moreover, how to determine the optimal mode is also given in Figure 5.Figure 5
Candidate modes of spatial location definition.Table2 presents the performance comparison after applying adaptive mode. According to Tables 1 and 2, fo obtains more Type-A error pairs but fewer Type-E error pairs or specifically more error pairs (1, 0) but fewer error pairs (0, 1). This can be explained by the higher probability of pu>pv brought by adaptive mode. As a result, the capacity increases whereas the distortion reduces. It is also seen that adaptive mode is even more beneficial for f. Specifically, we have more Type-B, Type-C, and Type-D error pairs but fewer Type-F error pairs. So far, with the improvement in error-pair generation, the capacity, which used to be 9198 bits, now turns to be 11 219 bits. Although there is more serious distortion, the proposed scheme introduces less distortion per embedding one bit; i.e., whereas the original performance is measured by 2.338, the new one is measured by 2.213.Table 2
Performance comparison of various solutions after applying adaptive mode.
MappingDABCEFCapacityDistortionf2587085562640642411 21924 824fo14972346542400127285016926121 474


### 3.3. Multiple Pairwise PEE

Notice that the correlation betweenpu and pv is neglected so far. For σn−2, u, and v, their order can be one of the following three: (1) σn−2<u<v, (2) u<σn−2<v, and (3) u<v<σn−2. Then, in Case (3) we have emax1=pu−pσn−2≥1 and emax2=pv−pσn−2≥1. By additionally considering the correlation between pu and pv, one can see that emax1 is shifted in case of pu>pv. In this situation how emax2 is utilized for data embedding should be related to emax1 considering the similarity between them; i.e., the larger emax1 is, the more likely emax2 is shifted. In this paper, we propose to adaptively determine the predicted value of pv and recalculate emax2 as(10)emaxN=pv−maxpσn−2,pu−η,with a parameter η. To fulfill data embedding, emaxN is modified as(11)emaxN′=emaxN+bifemaxN=1emaxN+1ifemaxN>1emaxNifemaxN<1,and accordingly pv is modified to(12)pv′=pv+bifemaxN=1pv+1ifemaxN>1pvifemaxN<1.Given thatpu−η>pσn−2 (i.e., emax1=pu−pσn−2>η), we have emaxN=pv−pu−η. That is to say, if emax1≤η the correlation between pσn−2 and pv is likely to produce expandable error. Otherwise, we turn to utilize the correlation between pv and pu with pu−η serving as the predicted value of pv. By varying η to cover every similarity between pairing errors, pairwise PEE will become more comprehensive. Similarly, emax2 is shifted in case of pv>pu. In that situation pv−η serves as another candidate predicted value of pu and we recalculate emax1 as(13)emaxN=pu−maxpσn−2,pv−η.Then,emaxN′ is obtained according to (11) and pu is similarly modified according to (12). Given that pv−η>pσn−2 (i.e., emax2>η), we have expandable error emaxN=pu−pv−η=pu−pσn−2−pv−pσn−2+η=emax1−emax2−η = 1. That is to say, one data bit will be embedded into error pairs emax1,emax2|emax2−emax1=η−1. This can be equivalent to expansion bins selection. Table 3 presents the evolution of all types of error pairs from Case (3). The same evolution can be performed on error pairs from Cases (1) and (2) as well. In this way, the original 2D mapping is extended into fη for η≥2. One can verify that fη includes the original 2D mapping f as a special case for taking η=255.Table 3
All types of error pairs of original pairwise PEE and multiple pairwise PEE.
Typeffη (η≥2)ANoneNoneBemax1=emax2=2emax1=emax2=2Cemax1=1,emax2>1emax1=1,1<emax2≤ηemax1>1,emax2=11<emax1≤η,emax2=1emax1−emax2=η−1Demax1=emax2=1emax1=emax2=1ENoneemax1−emax2≥ηFRestRest


### 3.4. Multiple Pairwise PEE Embedding

For each block, the minimum pixels are also utilized for data embedding. Letu=maxσ1,σ2,v=minσ1,σ2; another two pairing errors emin1 and emin2 are calculated as(14)emin1=pr1−ps1emin2=pr2−ps2,where r1=minu,σ3,s1=maxu,σ3, ,r2=minv,σ3,s2=maxv,σ3. emin1,emin2 is similarly utilized like emax1,emax2, and only pσ1 and pσ2 are reduced. By counting the frequency of error pairs emax1,emax2 and emin1,emin2 derived from blocks with a given complexity, a 2D histogram sequence hn for n≥0 is defined as(15)hne1,e2=#emax/min1=e1,emax/min2=e2,NLi=n.Algorithm 1: Optimal parameters determination for multiple pairwise PEE-based RDH.
Input: capacity requirement CR, activated mappings η0,η1,⋯,ηT−1, performance measurement ECpwn,η and EDpwn,η;Output: parameters sn;(1)Function Optimization (CR,η0,η1,⋯,ηT−1,ECpwn,η,EDpwn,η)(2)n=0,sn=η0(3)Update (n)(4)While CR is not met do(5)ηn1,dpbn1=minEDpwn+1,η0:ηT−1/ECpwn+1,η0:ηT−1(6)fixed=false(7)fori=0⟶ndo(8)ifrecordi,1>0andrecordi,2<dpbn1then(9)si=recordi,1,fixed=true(10)Update (i)(11)End if(12)End for(13)Iffixed==falsethen(14)n=n+1,sn=ηn1(15)Update (n)(16)End if(17)End while(18)Returnsn(19)End function(20)(21)FunctionUpdate (k)(22)ηset=findECpwk,:>ECpwk,sk(23)recordk,:=0,0(24)IfNot Emptyηsetthen(25)η,dpb=minEDpwk,ηSet−minEDpwk,sk/ECpwk,ηSet−minECpwk,sk(26)recordk,:=η,dpb(27)End if(28)End functionSo far we have histogram sequencehnn≥0 and mapping sequence fηη≥2. The final step is the selection of histograms and mappings and the determination of parameters sn which indicates that the histogram hn is to be processed by the mapping fsn. For histograms selection, the one with low complexity is preferentially selected. For mappings selection, any combination of various mappings can be attempted. Suppose that T mappings fη0,fη1,⋯,fηT−1η0<η1<⋯<ηT−1 are activated; sn takes values from η0 to ηT−1 or 0 indicating that histogram hn is excluded. The determination of optimal sn is described as follows. Firstly, the capacity-distortion performance of fη in manipulating histogram hn is considered. Let Aη,Bη,Cη,Dη,Eη,Fη denote the types of error pair defined by fη. The capacity and distortion, denoted by ECpwn,η and EDpwn,η, can be formulated as(16)ECpwn,η=∑e∈Bηhne+∑e∈Cηhne+log23∑e∈Dηhne,(17)EDpwn,η=∑e∈Bηhne+32∑e∈Cηhne+23∑e∈Dηhne+∑e∈Eηhne+2∑e∈Fηhne.Then, the complete determination procedure is presented in Algorithm1.An example is given here for better illustration. As shown in Figure6, for such a 2×3 sized block with NLi=21, Gh=3.5 and Gv=−1 are calculated according to (9) and (10). As a result, mode-6 is applied to obtain p1,p2,p3,p4,p5,p6=179,188,185,177,178,182. After sorting, there is σ1,σ2,σ3,σ4,σ5,σ6=4,5,1,6,3,2. Then, prediction errors are calculated as emax1=p2−p6=6, emax2=p3−p6=3, emin1=p1−p5=1, and emin2=p1−p4=2. Suppose that s21 is determined as 4; error pairs 6,3 and 1,2 are to be processed by f4. Apparently, both error pairs are categorized as Type-C by f4. Finally, p2 is enlarged to 189 while p3 remains unchanged for embedding one bit valued 0, andp4 is reduced to 176 while p5 is reduced to 177 for embedding one bit valued 1.Figure 6
Example of multiple pairwise PEE embedding.


### 3.5. Implementation of the Proposed Scheme

With specific block size and parameterT, all pixels except boundary ones are divided into shadow blocks and blank blocks. Then, the embedding and extraction procedures for the shadow layer are given below. Notice that the shadow and blank layers are embedded equally; i.e., each layer is embedded with half of the secret message.Firstly, to solve the problem of overflow/underflow, pixels are processed in raster-scan order by changing those valued 0 (255) into 1 (254). Here we use a location map record whether a pixel has been changed or not. Then, the location map is compressed using arithmetic coding and we useLclm to denote its length.Next, optimalsn is determined by capacity requirement which refers to the embedding of secret message and auxiliary information. Suppose that histograms with n<M are selected; the transmission of parameters sn requires a capacity of M×log2T bits. Then, the least significant bits (LSBs) of 50+M×log2T pixels from the first few blocks are recorded. These LSBs and the location map will be embedded along with half of the secret message as the payload.With the first few ones skipped, shadow blocks are successively processed to embed the payload. For each block, local complexityNLi and two error pairs emax1,emax2, emin1,emin2 are first calculated. If sNLi≥2, these two error pairs are processed by the 2D mapping fsNLi; otherwise, this block is skipped. After embedding the whole payload, the auxiliary information will be embedded by replacing the LSBS of the first 50+M×log2T pixels. The auxiliary information can be decomposed as follows:(i)
Block sizeh×w (4 bits)(ii)
ParametersT (4 bits) and M (10 bits)(iii)
Index of the last processed block (16 bits)(iv)
Length of the location map (16 bits)(v)
Parameterssn (M×log2T bits)At decoder, the auxiliary information is first retrieved from the LSBs of50+M×log2T pixels of the first few shadow blocks. Next, with the first few ones skipped, shadow blocks are successively processed. For each block, local complexity NLi and two marked error pairs emax1′,emax2′, emin1′,emin2′ are calculated. If sNLi≥2, these two error pairs are processed by the inverse 2D mapping of fsNLi to extract the embedded data and recover the original pixel values; otherwise, this block is skipped. Finally, the LSB sequence, the compressed location map, and the hidden message are retrieved from the extracted data bits. With the LSB sequence, the LSBs of 50+M×log2T pixels of the first few shadow blocks are recovered. The location map is decompressed and used to recover a pixel valued 1 (254).


## 3.1. Two-Layer Embedding

Existing PVO-based schemes are generally implemented by processing blocks in raster-scan order, i.e., from top to bottom and left to right. For each block, its right and bottom neighbors are always recovered before it at decoder such that they can serve as its context. To obtain a better context so as to achieve better pixel block selection, two-layer embedding is introduced into the proposed scheme. As shown in Figure3(a), all pixels except boundary ones are divided into nonoverlapped blocks denoted by “shadow” and “blank,” respectively. During data embedding, shadow blocks are first embedded with half of the secret data and blank blocks are embedded with the remaining half later. At decoder, blank blocks are first recovered after data extraction. Then, shadow blocks are similarly processed later.Figure 3
Image division and complexity measurement.
(a)(b)Referring to Figure3(a), with the nearest four blank blocks serving as the context of a shadow block, a full-enclosed context is thus constructed. The first advantage of the new framework is to more precisely compute the local complexity of each block. In this paper, a complexity measurement NLi is computed considering the absolute difference between two consecutive context pixels. As shown in Figure 3(b), NLi is computed as the sum of all these differences.


## 3.2. Adaptive Error-Pair Generation

For each selected shadow or blank block, the largest three pixels are utilized to generate an error pair. It has been verified by IPVO that more expandable errors can be derived from two correlated pixels by predicting the one having relatively smaller location. Therefore, withu=minσn−1,σn,v=maxσn−1,σn, two pairing errors emax1 and emax2 are computed as(8)emax1=pr1−ps1emax2=pr2−ps2,where r1=minu,σn−2,s1=maxu,σn−2,r2=minv,σn−2,s2=maxv,σn−2. According to IPVO we have expandable errors emax1∈0,1 and emax2∈0,1 here. By combining them into a pair for pairwise PEE, the initial 2D mapping is obtained and shown in Figure 4.Figure 4
Initial 2D mapping for pairwise PEE.To make a comparison between the new 2D mapping in Figure4 (denoted by f) and the original one in Figure 1(b) (denoted by fo), the image Lena is divided into blocks with the size of 4×4. Then, the numbers of all types of error pairs are computed and presented in Table 1. As it is shown, the new 2D mapping f not only achieves capacity improvement, but also introduces less distortion per embedding one bit.Table 1
Performance comparison of various solutions.
MappingDABCEFCapacityDistortionf2444083562060664510 91425 063fo14972283542400127915016919821 506According tof, all of (0, 0), (1, 0), and (1, 1) are Type-D error pairs. Specifically, the correlation between pσn−2 and pu is exploited to generate emax1 while the one between pσn−2 and pv is exploited to generate emax2. To generate more expandable emax1 or emax2 such that more Type-D error pairs can be obtained, the probability of u<v<σn−2 should be promoted. To accomplish this, we propose to adaptively define the spatial location of pixels within block. Suppose the cover image (denoted by I) is divided into a set of h×w sized blocks, for each of which we propose to use horizontal and vertical gradients to estimate the distribution of pixels within block and thus determine how to collect them. With the upper-left pixel located at i0,j0, horizontal gradient Gh and vertical gradient Gv are computed as(9)Gh=1h∑i=i0i0+h−1Ii,j0−1−Ii,j0+w,Gv=1w∑j=j0j0+w−1Ii0−1,j−Ii0+h,j.For example, every pixel is quite likely to have a right neighbor having smaller gray value whenGh>0. In this case, we should collect pixels from left to right so as to ensure pixel having relatively smaller location has relatively larger gray value. Similarly, every pixel is quite likely to have a bottom neighbor having smaller gray value when Gv>0. In that case, we should collect pixels from top to bottom. By combining Gh and Gv, eight modes of spatial location definition are summarized and presented in Figure 5, taking block with the size of 3 × 4 as an example. Moreover, how to determine the optimal mode is also given in Figure 5.Figure 5
Candidate modes of spatial location definition.Table2 presents the performance comparison after applying adaptive mode. According to Tables 1 and 2, fo obtains more Type-A error pairs but fewer Type-E error pairs or specifically more error pairs (1, 0) but fewer error pairs (0, 1). This can be explained by the higher probability of pu>pv brought by adaptive mode. As a result, the capacity increases whereas the distortion reduces. It is also seen that adaptive mode is even more beneficial for f. Specifically, we have more Type-B, Type-C, and Type-D error pairs but fewer Type-F error pairs. So far, with the improvement in error-pair generation, the capacity, which used to be 9198 bits, now turns to be 11 219 bits. Although there is more serious distortion, the proposed scheme introduces less distortion per embedding one bit; i.e., whereas the original performance is measured by 2.338, the new one is measured by 2.213.Table 2
Performance comparison of various solutions after applying adaptive mode.
MappingDABCEFCapacityDistortionf2587085562640642411 21924 824fo14972346542400127285016926121 474


## 3.3. Multiple Pairwise PEE

Notice that the correlation betweenpu and pv is neglected so far. For σn−2, u, and v, their order can be one of the following three: (1) σn−2<u<v, (2) u<σn−2<v, and (3) u<v<σn−2. Then, in Case (3) we have emax1=pu−pσn−2≥1 and emax2=pv−pσn−2≥1. By additionally considering the correlation between pu and pv, one can see that emax1 is shifted in case of pu>pv. In this situation how emax2 is utilized for data embedding should be related to emax1 considering the similarity between them; i.e., the larger emax1 is, the more likely emax2 is shifted. In this paper, we propose to adaptively determine the predicted value of pv and recalculate emax2 as(10)emaxN=pv−maxpσn−2,pu−η,with a parameter η. To fulfill data embedding, emaxN is modified as(11)emaxN′=emaxN+bifemaxN=1emaxN+1ifemaxN>1emaxNifemaxN<1,and accordingly pv is modified to(12)pv′=pv+bifemaxN=1pv+1ifemaxN>1pvifemaxN<1.Given thatpu−η>pσn−2 (i.e., emax1=pu−pσn−2>η), we have emaxN=pv−pu−η. That is to say, if emax1≤η the correlation between pσn−2 and pv is likely to produce expandable error. Otherwise, we turn to utilize the correlation between pv and pu with pu−η serving as the predicted value of pv. By varying η to cover every similarity between pairing errors, pairwise PEE will become more comprehensive. Similarly, emax2 is shifted in case of pv>pu. In that situation pv−η serves as another candidate predicted value of pu and we recalculate emax1 as(13)emaxN=pu−maxpσn−2,pv−η.Then,emaxN′ is obtained according to (11) and pu is similarly modified according to (12). Given that pv−η>pσn−2 (i.e., emax2>η), we have expandable error emaxN=pu−pv−η=pu−pσn−2−pv−pσn−2+η=emax1−emax2−η = 1. That is to say, one data bit will be embedded into error pairs emax1,emax2|emax2−emax1=η−1. This can be equivalent to expansion bins selection. Table 3 presents the evolution of all types of error pairs from Case (3). The same evolution can be performed on error pairs from Cases (1) and (2) as well. In this way, the original 2D mapping is extended into fη for η≥2. One can verify that fη includes the original 2D mapping f as a special case for taking η=255.Table 3
All types of error pairs of original pairwise PEE and multiple pairwise PEE.
Typeffη (η≥2)ANoneNoneBemax1=emax2=2emax1=emax2=2Cemax1=1,emax2>1emax1=1,1<emax2≤ηemax1>1,emax2=11<emax1≤η,emax2=1emax1−emax2=η−1Demax1=emax2=1emax1=emax2=1ENoneemax1−emax2≥ηFRestRest


## 3.4. Multiple Pairwise PEE Embedding

For each block, the minimum pixels are also utilized for data embedding. Letu=maxσ1,σ2,v=minσ1,σ2; another two pairing errors emin1 and emin2 are calculated as(14)emin1=pr1−ps1emin2=pr2−ps2,where r1=minu,σ3,s1=maxu,σ3, ,r2=minv,σ3,s2=maxv,σ3. emin1,emin2 is similarly utilized like emax1,emax2, and only pσ1 and pσ2 are reduced. By counting the frequency of error pairs emax1,emax2 and emin1,emin2 derived from blocks with a given complexity, a 2D histogram sequence hn for n≥0 is defined as(15)hne1,e2=#emax/min1=e1,emax/min2=e2,NLi=n.Algorithm 1: Optimal parameters determination for multiple pairwise PEE-based RDH.
Input: capacity requirement CR, activated mappings η0,η1,⋯,ηT−1, performance measurement ECpwn,η and EDpwn,η;Output: parameters sn;(1)Function Optimization (CR,η0,η1,⋯,ηT−1,ECpwn,η,EDpwn,η)(2)n=0,sn=η0(3)Update (n)(4)While CR is not met do(5)ηn1,dpbn1=minEDpwn+1,η0:ηT−1/ECpwn+1,η0:ηT−1(6)fixed=false(7)fori=0⟶ndo(8)ifrecordi,1>0andrecordi,2<dpbn1then(9)si=recordi,1,fixed=true(10)Update (i)(11)End if(12)End for(13)Iffixed==falsethen(14)n=n+1,sn=ηn1(15)Update (n)(16)End if(17)End while(18)Returnsn(19)End function(20)(21)FunctionUpdate (k)(22)ηset=findECpwk,:>ECpwk,sk(23)recordk,:=0,0(24)IfNot Emptyηsetthen(25)η,dpb=minEDpwk,ηSet−minEDpwk,sk/ECpwk,ηSet−minECpwk,sk(26)recordk,:=η,dpb(27)End if(28)End functionSo far we have histogram sequencehnn≥0 and mapping sequence fηη≥2. The final step is the selection of histograms and mappings and the determination of parameters sn which indicates that the histogram hn is to be processed by the mapping fsn. For histograms selection, the one with low complexity is preferentially selected. For mappings selection, any combination of various mappings can be attempted. Suppose that T mappings fη0,fη1,⋯,fηT−1η0<η1<⋯<ηT−1 are activated; sn takes values from η0 to ηT−1 or 0 indicating that histogram hn is excluded. The determination of optimal sn is described as follows. Firstly, the capacity-distortion performance of fη in manipulating histogram hn is considered. Let Aη,Bη,Cη,Dη,Eη,Fη denote the types of error pair defined by fη. The capacity and distortion, denoted by ECpwn,η and EDpwn,η, can be formulated as(16)ECpwn,η=∑e∈Bηhne+∑e∈Cηhne+log23∑e∈Dηhne,(17)EDpwn,η=∑e∈Bηhne+32∑e∈Cηhne+23∑e∈Dηhne+∑e∈Eηhne+2∑e∈Fηhne.Then, the complete determination procedure is presented in Algorithm1.An example is given here for better illustration. As shown in Figure6, for such a 2×3 sized block with NLi=21, Gh=3.5 and Gv=−1 are calculated according to (9) and (10). As a result, mode-6 is applied to obtain p1,p2,p3,p4,p5,p6=179,188,185,177,178,182. After sorting, there is σ1,σ2,σ3,σ4,σ5,σ6=4,5,1,6,3,2. Then, prediction errors are calculated as emax1=p2−p6=6, emax2=p3−p6=3, emin1=p1−p5=1, and emin2=p1−p4=2. Suppose that s21 is determined as 4; error pairs 6,3 and 1,2 are to be processed by f4. Apparently, both error pairs are categorized as Type-C by f4. Finally, p2 is enlarged to 189 while p3 remains unchanged for embedding one bit valued 0, andp4 is reduced to 176 while p5 is reduced to 177 for embedding one bit valued 1.Figure 6
Example of multiple pairwise PEE embedding.


## 3.5. Implementation of the Proposed Scheme

With specific block size and parameterT, all pixels except boundary ones are divided into shadow blocks and blank blocks. Then, the embedding and extraction procedures for the shadow layer are given below. Notice that the shadow and blank layers are embedded equally; i.e., each layer is embedded with half of the secret message.Firstly, to solve the problem of overflow/underflow, pixels are processed in raster-scan order by changing those valued 0 (255) into 1 (254). Here we use a location map record whether a pixel has been changed or not. Then, the location map is compressed using arithmetic coding and we useLclm to denote its length.Next, optimalsn is determined by capacity requirement which refers to the embedding of secret message and auxiliary information. Suppose that histograms with n<M are selected; the transmission of parameters sn requires a capacity of M×log2T bits. Then, the least significant bits (LSBs) of 50+M×log2T pixels from the first few blocks are recorded. These LSBs and the location map will be embedded along with half of the secret message as the payload.With the first few ones skipped, shadow blocks are successively processed to embed the payload. For each block, local complexityNLi and two error pairs emax1,emax2, emin1,emin2 are first calculated. If sNLi≥2, these two error pairs are processed by the 2D mapping fsNLi; otherwise, this block is skipped. After embedding the whole payload, the auxiliary information will be embedded by replacing the LSBS of the first 50+M×log2T pixels. The auxiliary information can be decomposed as follows:(i)
Block sizeh×w (4 bits)(ii)
ParametersT (4 bits) and M (10 bits)(iii)
Index of the last processed block (16 bits)(iv)
Length of the location map (16 bits)(v)
Parameterssn (M×log2T bits)At decoder, the auxiliary information is first retrieved from the LSBs of50+M×log2T pixels of the first few shadow blocks. Next, with the first few ones skipped, shadow blocks are successively processed. For each block, local complexity NLi and two marked error pairs emax1′,emax2′, emin1′,emin2′ are calculated. If sNLi≥2, these two error pairs are processed by the inverse 2D mapping of fsNLi to extract the embedded data and recover the original pixel values; otherwise, this block is skipped. Finally, the LSB sequence, the compressed location map, and the hidden message are retrieved from the extracted data bits. With the LSB sequence, the LSBs of 50+M×log2T pixels of the first few shadow blocks are recovered. The location map is decompressed and used to recover a pixel valued 1 (254).


## 4. Experimental Results

To demonstrate the performance of the proposed scheme, several experiments are conducted in this section. The test images are several gray-scale images with the size of512×512. Except Barbara, they are all downloaded from the USC-SIPI1 image database. To achieve the best performance, the embedding procedure is conducted for various block sizes taking h,w∈2,3,4,5. In terms of activated mappings, we consider only the combination of mappings with η∈2,3,⋯,T+1 where T is set as 2, 4, and 8.To verify the performance of the proposed scheme, some embedding parameters are presented in Table4. As it is shown, for a given EC of 10,000 bits, the image Lena is divided into 4×3 sized blocks. At error generation stage, mode-8 becomes the most popular one and it is chosen by about 16.5% of blocks in shadow layer and about 16.1% of blocks in blank layer. During shadow-layered embedding histograms with n<53 are selected, of which 34 are processed by f2 and 19 are processed by f3. During blank-layered embedding histograms with n<56 are selected, of which 45 are processed by f2 and 11 are processed by f3. As a result, the highest PSNR reaches up to 61.15 dB.Table 4
Parameters of the proposed scheme, for images Lena, Boat, and Lake with different capacities.
ImageCapacityBlock sizeTLayerMMode (1–8)f2−9PSNRLena10,0004×32Shadow53(12.5%, 14.7%, 9%, 10.9%, 10.9%, 15.7%, 10.1%, 16.5%)(34, 19, 0, 0, 0, 0, 0, 0)61.15Blank56(12.4%, 15.2%, 9%, 10.6%, 10.6%, 16%, 10.5%, 16.1%)(45, 11, 0, 0, 0, 0, 0, 0)Boat20,0003×34Shadow140(14.7%, 13.2%, 11%, 11.7%, 12.7%, 11.9%, 11.1%, 13.3%)(53, 37, 27, 23, 0, 0, 0, 0)54.84Blank155(14.6%, 13.7%, 12%, 12.1%, 12.5%, 11.7%, 10.8%, 12.9%)(77, 32, 24, 22, 0, 0, 0, 0)Lake30,0002×38Shadow216(11.6%, 14.8%, 12%, 14.4%, 9.3%, 12.9%, 10.3%, 14.4%)(44, 54, 30, 29, 15, 11, 18, 15)52.01Blank206(11.2%, 15.2%, 12%, 14.3%, 9.6%, 12.8%, 10.8%, 14.3%)(34, 46, 31, 31, 22, 15, 13, 14)Then, the proposed scheme is compared with five state-of-the-art schemes [17, 27, 30, 31, 35], as shown in Figure 7. Notice that rhombus prediction is adopted by [17, 27] while PVO prediction is adopted by [30, 31, 35] and the proposed scheme. Figure 7 shows that larger maximum EC is always guaranteed by rhombus prediction. However, PVO-based schemes are generally better in fidelity when capacity is moderate. Rhombus prediction is firstly utilized in 1D PEE [17]. Later, it is incorporated with pairwise PEE to realize 2D PEE [27]. As shown in Figure 7, the comparison of [17, 27] indicates that significant performance improvement is brought by the incorporation with pairwise PEE.Figure 7
Performance comparison with related schemes including Sachnev et al. [17], pairwise PEE [27], PVO-based pairwise PEE [30], multipass PVO-based pairwise PEE [31], and dynamic IPVO [35].
(a)(b)(c)(d)(e)(f)PVO-based pairwise PEE is firstly proposed in [30]. Figure 7 shows that, for some smooth images with large capacity (e.g., Lena with an EC larger than 35,000 bits and Barbara with an EC larger than 27,000 bits), [27] outperforms [30]. In other cases, [30] always outperforms [27]. The proposed scheme can also be regarded as an improved PVO-based pairwise PEE. As shown in Figure 7, the proposed scheme always outperforms [30]. According to Tables 5 and 6, the average gains of the proposed scheme over [30] are 0.52 and 0.63 dB for capacities of 10,000 and 20,000 bits, respectively. The proposed scheme also outperforms [27] in almost all cases. Rhombus prediction guarantees very large capacity on smooth images Lena and Barbara. As a result, on these images the proposed scheme only outperforms [27] with EC not larger than 44,000 and 35,000 bits, respectively.Table 5
Comparison of PSNR for the capacity of 10,000 bits, where the unit is dB.
Image[17][27][30][35][31]ProposedLena58.1859.7060.7560.8060.9161.15Barbara58.1459.4360.7360.8060.8961.10Boat56.1657.4958.4658.8858.6659.04Elaine56.1458.0658.2058.8058.5058.86Lake56.6558.6259.8760.2560.0560.62Peppers55.5656.2159.2759.4059.4059.75Average56.8158.2559.5559.8359.7460.07Table 6
Comparison of PSNR for the capacity of 20,000 bits, where the unit is dB.
Image[17][27][30][35][31]ProposedLena55.0456.2256.9857.0057.1057.45Barbara55.0456.2356.7256.7057.0057.38Boat52.6453.3254.2354.4554.4354.84Elaine52.0052.9153.4854.0853.7054.06Lake52.7053.7054.7855.4055.0055.74Peppers52.3052.8355.3155.2555.4555.89Average53.2954.2055.2555.4855.4555.88An improved incorporation of pairwise PEE and PVO prediction is proposed in [31] and it motivates the strategy of multiple pairwise PEE. In [31], the original 2D mapping of [30] is extended to two new ones according to local complexity. However, the gain is limited and the reason mainly lies in that only error pairs consisting of shiftable error are involved in the 2D mapping evolution. The proposed scheme, by contrast, achieves rather significant performance improvement over [30]. Referring to Tables 5 and 6, the proposed scheme outperforms [31] by 0.33 dB on average for an EC of 10,000 bits and 0.43 dB on average for an EC of 20,000 bits.The spatial correlation of pixels in a block is similarly exploited in [35]. Although the obtained errors are modified individually, the advantage of [35] is to fully exploit block redundancy by predicting as many pixels as possible. As shown in Figure 7, the proposed scheme outperforms [35] in almost all cases. Referring to Tables 5 and 6, the proposed scheme outperforms [35] by 0.24 dB on average for an EC of 10,000 bits and 0.4 dB on average for an EC of 20,000 bits. Furthermore, there is also significant superiority of the proposed scheme over [35] in capacity.In summary, the proposed scheme mainly aims to present a better incorporation of pairwise PEE and PVO prediction technologies. Specifically, original PVO-based pairwise PEE [30] is extended into adaptive embedding from two aspects including adaptive error-pair generation and adaptive error-pair modification. To better verify the advantage of adaptive embedding, the comparison of the proposed scheme with [30] on the Kodak2 image database which contains several 512×768 or 768×512 sized images is shown in Figure 8. It shows that the proposed scheme achieves significant superiority over [30] on all kinds of images.Figure 8
Performance comparison between the proposed scheme and [30] on the Kodak image database.Finally, Table7 gives the main notations used in this paper and it is worth mentioning that although achievement is achieved through adaptive error-pair generation and adaptive error-pair modification, the proposed scheme still uses only the largest/smallest three pixels in a block for data embedding. In the future work, we will focus on how to predict more pixels in a block and obtain more error pairs.Table 7
Main notations used in this paper.
NotationDescriptionpi, pσiThe i-th pixel in a block before/after sortingPEmaxPrediction error of PVO-based PEEemaxPrediction error of IPVO-based PEEemax1,emax2Prediction error of PVO-based pairwise PEEemin1, emin2emaxNPrediction error after recalculationNLiComplexity measurement of the i-th blockICover imageGh, GvHorizontal gradient and vertical gradient of a blockf, foThe 2D mappings in Figures4 and 1(b)fηThe parameterized 2D mappinghn2D histogram sequenceECpwn,ηCapacity performance of usingfη to modify hnEDpwn,ηDistortion performance of usingfη to modify hnLclmLength of the compressed location map


## 5. Conclusion

In this paper, a novel RDH scheme is proposed by presenting a better incorporation of pairwise PEE and PVO prediction. For error-pair generation, two-layer embedding is applied to obtain full-enclosed pixels. Then, full-enclosed pixels are used to estimate the distribution of pixels within a block and to realize adaptive spatial location definition. In this way, the error-pair generation becomes adaptive, and the distribution of error pairs is thus optimized. For error-pair modification, pairwise PEE is extended to multiple pairwise PEE with which the 2D histogram can be divided into a set of sub-ones for more accurate modification. The experimental results have shown that the proposed scheme outperforms previous state-of-the-art schemes by improving the marked image quality.



---

*Source: 2051058-2022-01-31.xml*