Adaptive reversible data hiding with pyramidal structure

Information security is one of the popular research topics, and it is also an important issue for practical application. Among relating methods in information security and corresponding digital rights management (DRM) systems [1, 2], cryptography and watermarking are two important categories. We focus on reversible data hiding algorithm in this paper, which belongs to a branch in watermarking researches and applications.

Watermarking researches have emerged for around 15 years, and reversible data hiding is a recently developed branch in watermarking researches [3, 4]. For conventional watermarking, at the encoder, the secret information should be embedded into the original multimedia contents, digital images in most cases, by the use of algorithms developed by researchers. Then, the watermarked media can be transmitted to the receiver. Data loss or intentional attacks may be experienced during transmission. After reception of the delivered watermarked media, only the secret information needs to be extracted [1]. In contrast, for reversible data hiding, data embedding is similar to its counterpart with conventional watermarking applications. Different from watermarking, for reversible data hiding, after the reception of marked media, both the original content and embedded secret information need to be recovered and extracted perfectly with a reasonable amount of side information [5, 6]. And this is the origin of the term “reversible” comes from. Besides the development of algorithms, reversible data hiding can be applicable to the protection of medical images [7, 8], or the integration with encryption techniques [9]. Due to this kind of characteristics, during the transmission, the watermarked media need to be kept intact.

Suppose that there are lots of medical images in the database of some hospital. Due to the stressful environment, especially in ICU, doctors or nurses may unintentionally put Patient A’s personal data and medical records into Patient B’s images. With the aid of reversible data hiding, Patient A’s medical records can be embedded into Patient A’s images beforehand [7]. For the doctors and nurses, while retrieving patients’ marked images, corresponding medical records can also be extracted to compare to the database. Also, original images can be perfectly recovered to meet the integrity. Should there be any mismatch, doctors or nurses are alarmed to prevent anything unexpected from happening. Thus, reversible data-hiding techniques can be applicable for practical use.

For evaluating performances of algorithms, and for making fair comparisons, parameters from different aspects should be considered. These parameters include the following.As far as we know, considering practical implementations, some tradeoffs among the parameters should be watched for the design of algorithm. For instance, embedding more capacity into original image introduces larger error, hence the degradation of quality of marked image. We suggest choosing the two criteria of obtaining at least 1.0 bit/pixel (bpp) of maximal embedding capacity, and reaching at least 30 dB in peak signal-to-noise ratio (PSNR) of output image quality. With our algorithm, reversible data hiding can be reached with adaptive embedding and pyramidal structure based on parameters listed above. Reversible data-hiding methods, which will be described in Sect. 2, have their inherent limitations and drawbacks even though lots of advantages can be observed. More importantly, few methods take the characteristics of original images into account in this field. Here, we make use of pyramidal structure of original image for obtaining the larger number of secret bits for embedding, with similar quality of the output images. Simulation results reveal that the algorithm proposed in this paper outperforms conventional ones by use of eight test images.

This paper is organized as follows. In Sect. 2, we describe fundamental concepts of reversible data hiding algorithms, including the histogram-based and difference expansion (DE)-based schemes. The reason why reversibility can be guaranteed is also addressed. Then, in Sect. 3, by considering inherent characteristics of images, we can utilize the difference values, and present the better way to make use of the pyramidal structure for reversible data hiding. Simulation results are demonstrated in Sect. 4, which point out the guaranteed image quality, the more embedding capacity, and the less side information needed for the proposed algorithm. Finally, we conclude this paper in Sect. 5.

The framework of reversible data hiding can be demonstrated in Fig. 1. On the one hand, in Fig. 1a, it depicts the encoder framework. Original image and secret information are integrated altogether with the devised algorithm to form the marked image. For keeping reversibility, the necessary amount of side information should also be provided to the decoder. On the other hand, in Fig. 1b, it displays the decoder framework. It is easily observed that blocks in Fig. 1b are placed in reverse order comparing to its counterpart in Fig. 1a. By doing so, both the original image and secret information can be perfectly separated from the marked image with the devised algorithm. And this is the major reason about the name of “reversible data hiding”.

Practical implementations for making reversible data-hiding possible can roughly be categorized into two major branches. From global point of view, by carefully modifying the histogram, we can reversibly embed the secret information into original image with schemes in [10‐12]. Schemes in this branch are referred to as the histogram-based schemes. On the other hand, considering local characteristics of original image, we can embed secret information by intentionally doubling the difference value between neighboring pixel pairs with schemes in [13‐15]. Schemes in this branch are referred to as the DE-based schemes.

Here, we briefly address the advantages and drawbacks of both schemes. First, for the histogram-based schemes, it has the advantage of guaranteed output image quality because the mean square error (MSE) between the marked and original image is limited to be below 1, leading to the result of at least 48.13 dB in PSNR value [3]. The major drawback of histogram-based schemes is the limited number of capacity, which is constrained by the peak of the histogram.

Next, for the DE-based schemes, it utilizes the difference value between two neighboring pixels for embedding one secret bit, leading to the capacity of 0.5 bit/pixel (bpp). However, after modifying the difference values, it may cause the overflow for producing the marked image. By following [5] and [6], the side information is named ‘location map’ (LM), which should be recorded in advance to keep the reversibility. There are some effective means for reducing the size of LM in [13] and [14]. Besides, unlike the histogram-based schemes, output image quality cannot be guaranteed.

It may be constructive to integrate the two schemes altogether and to acquire the advantages from both schemes. We take the histogram \(H\) in Fig. 2a, and difference histogram \(D\) in Fig. 2b of test image Lena with size of 512\(\times \)512. With the 8-bit grey-level representation, the pixel values are integers between 0 and 255. Consequently, the range of difference values lies between \(-255\) and 255. We observe that the peak values of Fig. 2a and b are 2,966 and 30,150, respectively, which results in 10.17 times difference. If we can borrow the concept in histogram-based schemes in Fig. 2a and integrate into DE-based scheme in Fig. 2b, larger capacity may be expected by utilizing the difference histogram. Output image quality can also be controlled when the limited amount of capacity is embedded.

Here is a simple illustration for reversible data hiding with difference histogram. The difference histogram can be produced from the difference between neighboring pixels. In Fig. 2b, we observe the difference histogram \(D\) is concentrated around 0. Here, \(D\) is an array, and we can denote the array by \(D=[ d\left[ {-255} \right] ,\;d\left[ {-254} \right] ,\ldots ,d\left[ {-1} \right] ,\;d\left[ 0 \right] \), \(d\left[ 1 \right] ,\;\ldots ,\;d\left[ {254} \right] ,\;d\left[ {255} \right] ]\), because the difference values lie between \(-255\) and 255. Next, the predetermined threshold value \(\delta \), which is a positive integer, is selected for data embedding, and it also serves as the side information at the decoder. For embedding the secret information, the altered difference histogram \({D}'\) should be formed first. By following the same manner, \({D}'\) can be represented with the notation of \({D}'=[{d}'\left[ {-255} \right] ,\;{d}'\left[ {-254} \right] ,\;\ldots ,\;{d}'\left[ {-1} \right] ,\;{d}'\left[ 0 \right] ,\;{d}'\left[ 1 \right] , \;\ldots \), \({d}'\left[ {254} \right] ,\;{d}'\left[ {255} \right] ]\). Next, data embedding should meet one of the following cases.We observe that the value of \(\delta \) plays the role of the secret key in reversible data hiding with only a few bits of overhead. It has another advantage of ease of implementation because only the moving of some portion of difference histogram is needed, and there is no need for calculation. Besides the advantages indicated above, there is one drawback for the proposed algorithm. Under the extreme cases when the index \(i\) reaches \(-255\) or \(255\), the overflow problem would occur, which can be easily observed from Eqs. (1) and (2). Such locations, or LM, should be recorded and served as the side information for decoding.

From Case 1 to Case 4, histogram occurrences at two difference values of \(\delta \) and \(( {-\delta +1})\), or the two bins as described in Case 4, are intentionally set to zero for hiding bit ‘0’ and bit ‘1’. For embedding secret bits, the difference histogram containing the secret, \({D}''\), should be produced correspondingly. Again, by following the same manner, \({D}''\) can be represented with the notation of \({D}''=[{d}''\left[ {-255} \right] ,\,{d}''\left[ {-254} \right] ,\ldots , {d}''\left[ {-1} \right] ,\,{d}''\left[ 0 \right] ,\,{d}''\left[ 1 \right] , \ldots , {d}''\left[ {254} \right] ,{d}''\left[ {255} \right] ]\). For clarity, four the difference values (or the index \(i)\) at \(-\delta \), \(( {-\delta +1})\), \(\delta \), and \(( {\delta +1})\) are employed for data embedding. Other elements in \({D}''\) are identical to their corresponding counterparts in \({D}'\). Embedding meets one of following conditions at the encoder.The difference values for remaining elements in \({D}''\) are identical to their corresponding counterparts in \({D}'\).

If we look into more detail in Eqs. (5a) and (5b), addition or subtraction by 1 implies the embedding of one bit. It has the potential to add or subtract the value of \(2^n-1\), with \(n\) being the number of secret bits, for data embedding. For instance, if \(n=2\), addition or subtraction the difference values by 0–3 is able to hide two bits at the same time. Meanwhile, for the locations of difference values larger than 252 or smaller than \(-252\), they should be recorded as LM. It corresponds to the observation that for smoother regions, they have the potential to hide more bits simultaneously. Larger value of \(n\), or embedding more bits at the same time, might be impractical because the added or subtracted value grows exponentially, which implies the increased amount of LM. By doing so, adaptive embedding can be achieved by incorporating with secret size and smoothness of original image.

For the extraction of secret bits and the recovery of original image, they correspond to the reverse procedures to data embedding, as depicted in the framework in Fig. 1. They can be described with the following procedures.With the descriptions above, we can find that reversibility can be guaranteed by manipulating difference histogram for reversible data hiding.

We propose our algorithm by considering the three-tier procedures with the concepts described in Sect. 2. The difference values between neighboring pixels, as well as the pyramidal structure, are utilized to look for better performances. As we mentioned in Sect. 1, for our algorithm, we suggest reaching the performances of at least 1.0 bpp of capacity, and at least 30 dB in PSNR of output image quality. After looking for major research databases, two relating papers [16, 17] met the two criteria, and they are employed to make comparisons with proposed algorithm.

In our simulations, we choose the eight test images baboon, Barbara, boat, F16, Lena, pepper, Tiffany, and Zelda with the picture sizes of \(512\times 512\), for conducting simulations. The secret information to be hidden is the randomly generated bitstreams. Since the proposed method in this paper extends the concepts in [16] and [17], results from the two papers are also compared. Besides, performances with [12] exhibit inferior results than those in [16, 17], and results in this paper, thus, we omit to make comparisons with the results in [12].

By properly adjusting the embedding strengths, performances with the eight test images in alphabetical order are depicted in Figs. 6, 7, 8, 9, 10, 11, 12, and 13. In each figure, taking Fig. 6 as an instance, Fig. 6a in the left presents performance comparisons with those in [16] and [17], and Fig. 6b in the right illustrates the subjective image quality for evaluations. For comparing the embedding capacity, we find that with our algorithm, the more amount of secret can be embedded. Among them, the F16 image can hide at most 408,414 bits (or 1.5580 bpp) in Fig. 9a, and b is depicted for subjective comparisons, with the PSNR of 30.55 dB. We observe that except for the baboon image in Fig. 6, our algorithm outperforms that in [16] and [17]. It might be because the baboon image displays more active than others, which may lead to the large values in differences. However, for large embedding capacities in baboon, we embed more secret with better quality. For the remaining images in Figs. 7, 8, 9, 10, 11, 12 and 13, our algorithm performs better in general. Nevertheless, for low embedding capacities, it performs a bit inferior in Barbara in Fig. 7a and boat in Fig. 8a. It might be because pyramidal structure brings overhead into data embedding, and it causes degradation to output image quality. We are revising our algorithm to conquer the extreme presentation for low capacity.

We also perform the detailed analysis of the results with Lena in Tables 1, 2, 3, 4, 5 and 6. We employ the three-layer pyramid for reversible data hiding. Under a variety of selections of predetermined threshold \(T\), which is an integer with multiples of 8, we observe that if we use more layers for data embedding, then the output image quality gets degraded. We first observe that the increase in capacity is regular; if we use two or three layers for data embedding, the percentage of increase lies around 25 and 31.25 %, respectively. This comes from the observation that the area of the second layer is a quarter of the first later, while the area of the third layer is 1/16 of the first layer. Next, with additional layers for data embedding, the decrease in PSNR values can be expected, from 0.9618 to 0.9815 dB for using two layers, and from 1.0989 to 1.1743 dB for using three layers altogether. The decrease in PSNR comes from the selection of threshold \(T\), and the different characteristics of original images in pyramidal structure. With our method, based on practical requirements, we can predict the necessary capacity with the adaptive embedding with pyramidal structure.

In this paper, we presented an adaptive algorithm of reversible data hiding, which employs pyramidal structure of original images for the better capability to hide more secret bits. Reversible data hiding with the alteration of difference values, obtained based on the characteristics of original images, has presented better performances compared to the conventional histogram-based schemes. For reversible data hiding, the reversibility must be retained at the decoder. Then, performances of algorithm, including the output image quality and capacity, can subsequently be examined.

Inspired by scalable coding of multimedia, we can carefully manipulate difference values in the original image between different layers of the pyramidal structure. Adaptive embedding can be applied to one of the four cases with the characteristics of original image. At the encoder, for adaptive embedding with pyramidal structure, performances with our algorithm present better in general for most test images. At the decoder, with the embedding strength, which implies the side information for decoding, the secret information can perfectly be retrieved. In addition, with the aid of location map, original image can perfectly be recovered. With our algorithm, we can embed more amount of secret with similar output quality. By use of the pyramidal structure, inherent characteristics can be utilized, and better performances can be obtained.