Reversible Watermarking Using Statistical Information

In most reversible watermarking methods, a compressed location map is exploited in order to ensure reversibility. Besides, in some methods, a header containing critical information is appended to the payload for the extraction and recovery process. Such schemes have a highly fragile nature; that is, changing a single bit in watermarked data may prohibit recovery of the original host as well as the embedded watermark. In this paper, we propose a new scheme in which utilizing a compressed location map is completely removed. In addition, the amount of auxiliary data is decreased by employing the adjacent pixels information. Therefore, in addition to quality improvement, independent authentication of different regions of a watermarked image is possible.

Reversible watermarking, also called lossless data hiding, embeds the watermark data into a digital image in a reversible manner, that is, one can restore the original image without any degradation. Many techniques, focusing on capacity-distortion improvement, have been proposed during the last decade. In most of the previous work, channel degradation is not allowed; as a result, such schemes are highly fragile. This limits the usability of reversible watermarking only in lossless environments.

Lossless data embedding can be classified into the following categories: the first one utilizes additive spread spectrum [1, 2]; the second category compresses the selected image features for creating vacancy [3, 4], and employs this spare space for embedding; the third group, namely expansion-based methods [5–16], embeds the watermark data in some features by expanding them; these features are created by some decorrelation operator, and finally, some methods are based on histogram modification [17, 18] in which peak/zero points of the histogram either in spatial domain or transform domain are utilized for embedding.

Most of the existing reversible watermarking algorithms have a highly fragile nature in the sense that changing a single bit in the watermarked media may prevent the hidden data to be extracted. In addition, the restoration process would fail as well. This restricts the employing of reversible data hiding just to the cases in which there is a complete control over the watermarked data. Therefore, due to emerging applications of reversible watermarking schemes [19, 20], it makes sense to extend its scope to lossy environment.

The rest of this paper organized as follows: Section 2 reviews the concept of robust reversible watermarking. In the next section, our proposed method is introduced. The experimental results are presented in Section 4, and conclusion is drawn in Section 5.

Most of reversible watermarking methods, presented so far, have a highly fragile nature; nevertheless, there are some methods which can be deemed as semifragile techniques. In [21], Kalker and Willems provided a theoretical analysis of reversible data hiding techniques in which robust reversible watermarking is interpreted in three ways: firstly, it can refer to robustness of the embedded watermark. Next, it can refer to reversibility of the host signal, and finally, both payload and reversibility are considered. They focused on the third option and concluded that a robust reversible data hiding scheme exploits the side information available from the received data and also error correcting codes.

De Vleecshouwer et al. proposed a modulo-256 addition based on the classical patchwork algorithm in order to achieve a reversible watermarking scheme [2]. Firstly, they map the histogram of each zone to a circle; then instead of the concept of average value, the position of the histogram on the circle is used as the discriminating factor. As a result, unreliable retrieval caused by wrapped around pixels impacting the average value is avoided. Due to embedding in nonoverlapping blocks and the small size of the auxiliary data, the recovery of a fragment of the payload using a grid alignment is possible for the cropped images. In addition, this method along with the message repetition is robust against JPEG compression just for extracting the payload. This scheme, however, is not free from salt and pepper noise. In addition, due to block-based embedding, the capacity is very low.

Ni et al. [22] proposed another semifragile reversible data hiding scheme based on the patchwork algorithm. They classified each block into four different categories and use different embedding schemes in order to avoid overflow and underflow. Their method employs error correction codes (BCH) in order to overcome some ambiguity raised during embedding and also to provide robustness against JPEG compression.

In order to enlarge the scope of reversible watermarking, a joint marking procedure is proposed in which a robust lossy watermark is first embeded and a reversible watermarking scheme is employed in the next stage [23]. The information needed to invert back the marked media should be stored during the reversible embedding. In case of no attack, the original image can be recovered. It should be noted that due to high embedding capacity which is required in this method, the achieved quality is not acceptable.

Among different reversible watermarking schemes, the expansion based methods received more attention because they have the highest embedding capacity along with the lowest quality degradations. However, a location map is needed to determine the positions of the expanded values. This location map should be compressed in order to decrease its influence on embedding capacity. As a result, lots of efforts have been done to decrease the size of location map. Using location map, however, has some other shortcomings, for example, a single bit modification may break the entropy decoder synchronization. Furthermore, it is not possible to employ such embedding scheme in block-based manner.

As a result, it is necessary to remove the location map in order to prepare a less fragile method. There are some methods which do not use a location map. In [24], the locations of expanded values are determined based on some statistical analysis. However, it needs to transfer some information to the recipient separately. As a result, it cannot be consider as a blind scheme.

Coltuc and Chassery proposed a method in which using the location map is removed too [12]. Robustness against cropping can be achieved by distributing and storing the auxiliary data close to the corresponding pixel pairs. Still, the size of auxiliary data especially in case of using distortion control is a major problem. In addition, in order to prevent some decoding ambiguity, the decoder should be informed about the error threshold in advance. They generalized their method in [11] in which a high capacity in a single pass of embedding can be achieved. However, the watermarked image quality is not satisfactory: the degradation is more annoying in edges. Moreover, in case of capacity control, the amount of auxiliary data which are used to specify the noncontainer elements increases intensively. In [13], an improved version of [11] is presented. However, due to dependencies in decoding process, it cannot be deemed robust against cropping. In addition, these dependencies may prevent the extraction of the watermark and recovery of the original image. In [14], this problem is solved through considering an extra state in the embedding phase. Still, this method cannot be robust against cropping.

In robustness point of view, introduced in [21], most of the presented semifragile reversible watermarking algorithms can be categorized in the first group in which just the extraction of the payload is possible in case of lossy operation. Although, the proposed methods in [11, 12] can recover the original image after cropping, the large number of auxiliary data is the main disadvantage of these methods.

In [15], we proposed an alternative transform to increase the quality of the marked image by employing the checkerboard structure. In [16], we expand the algorithm by utilizing a new error control strategy to decrease the size of auxiliary data. Since, this kind of reversible embedding algorithm does not employ a location map and the size of auxiliary data is negligible, it can be used to make the method more robust against some geometrical attacks.

Toward overcoming the highly fragile nature of reversible algorithms, two possible solutions are considered: the first one uses a block-based embedding; therefore, in case of some attacks such as cropping, it is possible to extract the embedded watermark using a grid alignment. In this case, the proper grid alignment should be recovered through an exhaustive search [2]; in addition, a low embedding capacity is another disadvantage of this group of algorithms. The other way is to design a reversible method in which the dependency to a location map or any auxiliary data become restricted. For example, by using the statistical information which can be retrieved from watermarked media; it is possible to determine the location of container elements. It should be noted that, this statistical information should be the same in both original and the watermarked image. This self-dependent reversible watermarking can be used as a way to decrease the fragile nature of the reversible methods.

To decrease the dependency to auxiliary data and toward designing self-dependent reversible algorithm, we proposed to use a checker board structure [15]. This structure is utilized in order to better employ the spatial correlation of an image. Half of the pixels were used for embedding and the remaining was kept intact which can be employed for specifying the location of the embedded information. The embedding is done through  (1)

(1)

where

In (1), is the marked pixel and and are the northern, southern, eastern, and western adjacent pixels respectively, as depicted in Figure 1.

The structure of adjacent pixels in embedding process.

Full size image

Furthermore, and indicate the contribution factors of corresponding neighbors. By increasing the contribution factors, it is possible to embed more at the expense of higher degradation. Due to high spatial correlation in natural images, it is expected that differences between P and its neighborhoods will be small (which is the basic assumption in different expansion-based methods).

In the extraction phase, it is sufficient to compute the weighted sum of the pixel group which is illustrated in  (2)

(2)

where

The sum of adjacent pixels should be remained intact so that the watermark extraction and recovery of the original host become possible; consequently, for embedding just half of the pixels, constructing a checkerboard structure is employed.

In (2), and w are congruent modulo M. As a result, it can be concluded from (2) that M symbols can be embedded in each pixel in a reversible manner. Therefore, the raw capacity is  bpp. To achieve more capacity, it is possible to repeat the embedding procedure by changing the role of two pixel groups.

As mentioned before, the sum of differences is often extremely small; however, in some cases it is possible to cause overflow or underflow. As a result, the transform can be applied only when the intensity interval does not change:

(3)

In this case, it is necessary to distinguish between transformable and nontransformable pixels. Therefore, similar to [12], one symbol is assigned to decide between the container elements and noncontainers. Since one can embed M symbols with keeping the ability of recovering the original value, we reserve the symbol `0' for noncontainer elements; hence, the watermark symbol can be chosen from . On the other hand, the range of auxiliary data may fall outside of this range since in case of overflow it is necessary to use negative corrective data. Thus, a prefix is utilized for encoding the range of with symbols.

Since the transform in (1) employs the image structure more fittingly, it can better preserve the image quality especially in edges, in comparison to similar methods [11–13]; this is because the human visual system is adapted to extract the structural information of a viewing scene [25].

As mentioned before, the pixels which are not capable of embedding the watermark should be changed to be recognized at the decoder side. Therefore, the increase of the auxiliary data has a doubled effect on capacity: on one part, there are less embeddable pixels; besides, the auxiliary data occupy a potion of the capacity:

(4)

where E is the number of embeddable pixels and N represents the number of pixel pairs.

In this case, missing the auxiliary data due to a synchronization attack prevents the algorithm to extract the payload and reverts back the original media. Thus, increasing the amount of auxiliary data will increase the fragility of the reversible watermarking methods.

The amount of auxiliary data especially after applying distortion control is increased dramatically which deteriorate the situation. As a result, to present a less fragile reversible method, reducing the number of auxiliary data is unavoidable.

Figure 2 illustrates that there is a high correlation between the variance of adjacent pixels and the resulting error after applying the transform (1) due to spatial correlation of natural images. As it is presented in [15], half of the watermarked pixels remain intact in the proposed method, and the variance of adjacent pixels can estimate the introduced error; we decide to use it as distortion control parameter:

(5)

where is . In order to reduce the number of auxiliary data, the idea is to utilize just the pixels the variance of which does not exceed a predefined threshold. The threshold can be easily found due to spatial correlation of natural images and the application demands.

The relation between introduced error and standard deviation of adjacent pixels for Lena.

Full size image

Although, utilizing this technique may exclude some transformable pixels, the decrease of the number of auxiliary data is more significant than the decrease of the embeddable pixels. Therefore, the actual capacity is improved; furthermore, the dependency of embedded payload to the auxiliary data is highly decreased. The relation between the embeddable pixels and the correction data for different test images is illustrated in Figure 3. All images are of size and with error threshold equal to 10, the standard deviation varies from 30 to 5 as depicted in Figure 3. It is clearly shown that by restricting the variance, the ratio between the embeddable pixels and the auxiliary data is increased; therefore, the major part of the payload is taken by the watermark information rather than the auxiliary data.

The relation of embeddable pixels to correction data.

Full size image

Consequently, by using the information from the intact pixels, the amount of auxiliary data is decreased significantly. In other words, it is possible to embed the watermark in some elements independent from others. In this case, this scheme has the potential to be robust against synchronization attacks because the extracting and recovery for a fragment of a picture can be done independently.

In this section, firstly, the performance of our method is evaluated in terms of capacity and distortion. Then, the results in case of some lossy environment are explored.

We evaluate the results of location map-free different expansion (DE) based methods by comparing capacity versus distortion. The results are illustrated in Figure 4.

Performance comparison on test images Lena, Baboon, and Cameraman.

Full size image

For a fair comparison, the same expansion amount is utilized. For the proposed method and [15], 1.5 is considered as the contribution factors while in [11, 23] the simulation is performed for . In this case, the expansion amounts are similar in all cases. The experiments are conveyed on benchmarks of size .

As it is indicated, the proposed method outperforms the other methods especially in low embedding bit rate due to decreasing the required auxiliary data. In this case, just a less portion of the payload is occupied by the auxiliary data.

As it is depicted in above figures, decreasing the size of auxiliary data could restrict the introduced distortion. On the other hand, it decreases the dependency of the embedded watermark to the auxiliary data as well.

The number of auxiliary data for different benchmarks with different capacity is illustrated in Table 1. As it is clearly shown, the required auxiliary data is negligible especially in low embedding bit rate.

We compare our method with similar schemes in term of auxiliary data too. The required auxiliary data for different location map-free reversible watermarking method for Lena are depicted in Table 2. The proposed method produces less auxiliary data than the other location map-free schemes. Since the watermark extraction and recovery process for each part can be done independently, the recovery of a fragment of the watermarked image is possible. Therefore, the proposed method allows robustness against cropping. It is worth noting that it is possible to recover parts of an image without considering grid alignment.

A location map-free reversible watermarking scheme is proposed. Since the information of adjacent pixels is utilized, the size of the auxiliary data decreases. Therefore, the quality of the proposed method is improved significantly especially in low embedding rate. Furthermore, the negligible amount of the auxiliary data provides robustness against some geometric attacks such as cropping in which in addition to extracting the embedded watermark, the original image can be recovered.

The authors would like to thanks ITRC (Iran Telecommunication Research Center) for partially supporting this research.

Authors and Affiliations

1. Electrical & Computer Engineering Faculty, Shahid Beheshti University, G.C., Tehran, 1983963113, Iran

   Ahmad Mahmoudi Aznaveh, Farah Torkamani-Azar & Azadeh Mansouri

2. The Institute of Electronics, Communications and Information Technology, Queen's University Belfast, Belfast, BT3 9DT, UK

   Fatih Kurugollu (EURASIPMember)

Corresponding author

Correspondence to Farah Torkamani-Azar.

Open Access This article is distributed under the terms of the Creative Commons Attribution 2.0 International License ( https://creativecommons.org/licenses/by/2.0 ), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Reprints and permissions