Border following–based reversible watermarking algorithm for images with resistance to histogram overflowing

Abstract

Histogram shifting is an effective manner to achieve reversible watermarking, which works by shifting pixels between the peak point and its nearest zero point in histogram to make room for watermark embedding. However, once zero point is absent, the algorithm suffers from overflowing problem. Even though some works attempt to deal with this risk by introducing auxiliary information, such as a location map, they occupy a lot of embedding capacity inevitably. In this article, in order to deal with overflowing problem efficiently, we propose a border following–based reversible watermarking algorithm for images. With the help of border following algorithm and pre-processing, available regions with at least one zero point are recognized to embed watermark so that auxiliary information is not needed any more. And the algorithm utilized also ensures the same border can be re-recognized from the watermarked image without error, thus the correctness is also guaranteed. The performance of the proposed algorithm is evaluated using classic image datasets in this area, and the results not only validate the effectiveness of the proposed algorithm but also indicate its advantages compared with the classic histogram shifting–based reversible watermarking algorithm as well as the state of the art.

Introduction

Reversible watermarking^1– 6 is an important watermarking technique to achieve information hiding, which enables the cover image to be fully recovered without any distortion once the embedded watermark is extracted. Thus, it has been successfully applied to high-fidelity required environments, such as medical, military, and remote sensing image–based information hiding. For its significant benefit, it is becoming a research hotspot.

Histogram shifting is an effective and important way to achieve reversible watermarking.^7–11 It works by shifting pixel values between the peak point and its nearest zero point in histogram of the cover image by “1” to embed watermark. Since watermark is embedded in pixels corresponding to the peak point, great capacity is achieved. However, such a native implementation suffers from the problem of overflowing. Once a histogram does not have a zero point, in order to achieve information hiding, the embedder has to shift pixels between the peak value point and the minimum value point in histogram, thus the pixel values of minimum value point would be permanently corrupted so that the reversibility cannot be ensured any more. As a means to deal with this problem, location information and pixel value of the minimum value point have to be recorded and embedded as auxiliary information, which increases the overhead and occupies the embedding capacity significantly. In addition, some other solutions^11–13 have also been proposed to reduce the amount of location information, such as by compression. ¹³ Although effective, they bring about extra computation cost at the same time. Moreover, auxiliary information is still required in these works, so that the embedding capacity is also affected.

According to a large amount of statistical analysis, even though histogram of the whole cover image does not have a zero point, there is also high probability that at least one zero point exists in a local region of the image. Border following is an effective manner to extract borders of such regions, thus it is a potential way to handle the problem mentioned above effectively. With the help of this technique, borders with at least one zero-value pixel inside can be recognized. By embedding watermark bits inside, auxiliary information such as location map is not needed any more, thus achieving high efficiency and large embedding capacity. In this article, we propose a border following–based reversible watermarking algorithm for images with resistance to histogram overflowing. The proposed algorithm is not only effective, but also lightweight. Our major contributions can be summarized as follows:

1. We present a novel framework to support border following–based reversible watermarking mechanism, which consists of an image pre-processing module, a histogram shifting–based watermark embedding module, and a watermark extracting module. Furthermore, specific algorithms for all of them are presented respectively.

2. We propose a border following–based reversible watermarking algorithm based on histogram shifting, which is able to resist against overflowing problem with only a small amount of computational overhead required to extract borders. It filtrates images and selects available regions adaptively to embed watermark. To avoid overflowing, the histogram of selected region is ensured to have at least one zero point. Clearly, watermark can be embedded into multiple regions in a single image simultaneously to achieve large capacity as long as they satisfy the requirement.

3. We verify effectiveness of the proposed algorithm and compare it with the state of the art by experiments. Experimental results show that our presented algorithm is fully reversible and overflowing problem is avoided with only small amount of overhead required.

Related works

Ni et al. ¹⁴ proposed the first histogram shifting–based reversible watermarking algorithm, which embeds watermark by modifying pixel values of the cover image between the peak point and its nearest zero point in the histogram. However, for a histogram without zero point, to handle overflowing problem, the scheme has to record and embed location information as well as pixel value of the minimum value point as auxiliary information, which introduces a great amount of extra overhead inevitably. On the basis of their work, to improve imperceptibility, Wang et al. ¹⁵ optimized rate and distortion for histogram shifting–based algorithms. Chen et al. ¹² reduced the extra information by only recording pixels that have been moved. However, to resist overflowing, these methods also have to generate and embed a location map as auxiliary information.

On the other hand, Fu et al. ¹¹ presented a novel reversible watermarking algorithm based on prediction-error histogram shifting as well as exploiting modification direction (EMD) mechanism. They exploit the similarity among adjacent pixels and use the side-match predictors to obtain prediction-error histogram, then embed watermark by shifting this histogram. Thanks to the nonary EMD algorithm and the multi-layer embedding mechanism, the capacity of the proposed method is greatly improved. However, to resist overflowing problem, auxiliary information is still necessary. In addition, Xuan et al. ¹⁶ proposed a histogram-pair-based image reversible data hiding scheme, which embeds data into the prediction errors generated from a cover image. To avoid overflowing, it shrinks the histogram to generate zero point before data embedding, which requires large amounts of computational overhead.

Furthermore, Kim et al. ¹⁷ proposed a gradient-adjusted prediction (GAP) and modulo operation–based solution to provide superior image quality and large capacity. However, the reversibility of the proposed scheme still replies on the existence of zero value points in the histogram. As further development, Caciula et al. ¹⁸ investigated a multiple moduli prediction error expansion approach to achieve reversible data hiding. Thanks to the introduced linear programming model, the specific moduli is selected so as to maximize the embedding bit rate. In order to ensure reversibility, a location map with the expansion information is embedded together with the payload. In this case, auxiliary information is still inevitable.

Moreover, Sachnev et al. ¹⁹ proposed a new rhombus prediction scheme to improve efficiency, which employs sorted prediction errors to reach balance between capacity and imperceptibility. Based on their work, Kim et al. ¹³ proposed a skewed histogram shifting–based embedding framework, which utilizes a pair of extreme predictions. Specifically, only pixels from the peak and short tail are used for embedding, which decreases the distortion from the lesser number of pixels being shifted. However, a location map as auxiliary information is still necessary. Moreover, in order to compress the location map, extra computation overhead is also introduced.

In this article, to deal with security and efficiency problems mentioned above, we propose a border following–based reversible watermarking algorithm for images, which is able to avoid overflowing without introducing auxiliary information. Specifically, once the zero value point is absent in histogram of the cover image, we utilize image pre-processing to make sure there is at least one zero point inside the recognized border.

Reversible watermarking algorithm based on border following

In this article, we propose a border following–based reversible watermarking algorithm for images. The algorithm employs border following to obtain available regions inside of the border. In order to ensure large capacity, peak point of each region is utilized to embed watermark by histogram shifting. To extract watermark, the receiver performs the same border following algorithm to find out the watermarked region inside of the border, which is ensured to be identical with the one recognized from the un-watermarked image under the algorithm. Thus, reversible extraction of the watermark is guaranteed.

Figure 1 is an illustration of the proposed reversible watermarking algorithm. From the flowchart, it is clear that the algorithm consists of three parts: image pre-processing, histogram shifting–based watermark embedding, and watermark extracting. For cover images, we first employ the Otsu method ²⁰ to get the threshold value, which is utilized to convert cover images into binary ones, ensuring the variance of divided pixels in two categories to be maximized. With the help of this method, pixels inside the recognized border are more similar with each other, thus raising the number of peak points in the corresponding histogram with high probability. After successfully identifying the borders in the image, check the number of zero value pixels inside each border to determine whether the image is available. Two simplified examples of available and unavailable images are shown in image pre-processing module. On finishing pre-processing of available images, histograms of pixels inside each recognized border are generated. Due to the limitation of space, histograms are just schematic diagrams and have no direct correspondence with specific regions in the example shown before. Then, watermark bits are embedded based on histogram shifting. For a watermarked image, execute the same procedure of border following to detect borders and then extract watermark from the inside pixels to obtain the recovered image. During the whole procedure, border following algorithm introduced below is the key to achieve resistance against histogram overflowing.

Figure 1.

Framework of our proposed algorithm.

Semantic segmentation model–based border following algorithm

As a preparation for the proposed border following–based reversible watermarking algorithm to deal with histogram overflowing, we need such a semantic segmentation model–based border following algorithm ²¹ as preliminary. In order to segment an image according to semantics, the algorithm first transforms it into a binary one and temporarily expands the image by 0 to deal with pixels on its four boundaries. Then raster scans the original binary image without the expanded scope in pixel level to achieve border following. Once a pixel with value 1 is encountered, it takes the pixel as the center of a 3 × 3 matrix and checks the 8 pixels around. If all of them are zero point, the central pixel is set to −2 to indicate the recognized single pixel. Otherwise, take the current pixel as the center and the first non-zero pixel encountered as the start point, which is scanned in clockwise order from the left pixel of the center. Check the matrix in anti-clockwise order from the chosen start point and select the first non-zero pixel as the next central pixel. Meanwhile, set the current central pixel as the start point for the next round. Specifically, in the latter case, the central pixel is marked as 2 if the value of its right adjacent pixel is non-zero, or marked as −2 otherwise. Repeat the above procedures until scanning to the start point in the first round. Once finishing a complete border following, the algorithm starts a new raster scanning from the right adjacent pixel of the first start point, thus ensuring that none of the previous border pixels are involved in the next 3 × 3 matrix selected. It is worth noting that, since border following algorithm always begins from the first 1-value pixel in each line scanned, even if pixel values inside the recognized region are changed, the position of the border could also be accurately recognized. In order to demonstrate the effect of the algorithm intuitively, we take a 5 × 5 binary image shown in Figure 2 as an example and implement the border following algorithm on it. We first expand the image with 0 pixels in grids surrounded by dotted lines to a 7 × 7 one, in order to implement border following algorithm on original boundaries of the image. Figure 2 shows the first two rounds of border following and the outermost border of the recognized region is marked in Figure 3. After performing the algorithm on the whole image, the expanded grids with 0 pixels inside are eliminated. In this way, expanded boundaries are just employed to ensure the execution of border following on original boundaries, rather than involving in subsequent data processing which may introduce extra overhead. Due to its robustness and reliability, the algorithm has already been widely used in component counting and topological structural analysis of digital images.

Figure 2.

Pixels of a binary image.

Figure 3.

Border presentation of the binary image.

Image pre-processing

We first transform cover images into binary ones and mark the outermost border of the recognized region in border presentation. In order to resist histogram overflowing, we first find out images whose recognized regions contain at least one zero point. Then select them and keep their border coordinate points as preparation. Pixels inside each of the border are employed to embed watermark. Below we introduce the image pre-processing procedure in more detail.

• Step 1. To convert an M × N cover image I into a binary one, we first employ the Otsu method ²⁰ to get the binary threshold t. Under the value, the pixels of Image I are divided into two categories, between which the variance is ensured to be maximized. Then scan pixels of I in a raster order. Compare pixel value $v_{p_{i,j}}$ ∈ [0, 255] (i ∈ [1, M] ∈ [1, N]) and the threshold t, if $v_{p_{i,j}}<t$ , update $v_{p_{i,j}}$ to 0, otherwise, update $v_{p_{i,j}}$ to 1.

• Step 2. In order to cover pixels on the boundary of the original image, expand its four boundaries with zero-value pixels to get the expanded (M + 2) × (N + 2) image $I_b$ . It is worth noting that the expanded pixels only ensure borders on original boundaries can be followed, rather than participating in border following itself. Thus, no extra overhead is introduced actually.

• Step 3. Raster scan $I_b$ , we employ the border following algorithm introduced above to find out the first pixel $p_{i,j}$ (i ∈ [2, $M+1$ ], j ∈ [2, $N+1$ ]) with value 1. The procedure can be exhibited by a 5 × 7 and a 2 × 2 binary images shown in Figures 4 and 5, corresponding to border following of a region and a single pixel, respectively. Take $p_{i,j}$ and $p_{i,j-1}$ as the center and start point separately to scan pixels clockwise. Once the first non-zero pixel $p_{i\prime ,j\prime }$ is encountered, stop border following, and mark it as the end point of this turn of scanning. If none of the non-zero pixel is encountered, $p_{i,j}$ is marked as a single pixel. This scanning process in both cases is shown in Figures 4(b) and 5(b).

As is shown in Figure 4(c), take $p_{i\prime ,j\prime }$ as the new start point to scan pixels in anti-clockwise order. Once the first non-zero pixel is encountered, stop border following. In order to mark the pixels on the border, we need to update the value $v_{p_{i,j}}$ of the central pixel as follows

$$v_{p_{i,j}}=\{\begin{array}{cc}2,\hfill & v_{p_{i,j+1}}\ne 0\mathrm{and}{v}_{p_{i,j}}=1\hfill \\ \multicolumn{1}{c}{-2,}& v_{p_{i,j+1}}=0\mathrm{and}{v}_{p_{i,j}}=1\hfill \end{array}$$

(1)

Select the first non-zero pixel as the next central pixel, and the current central pixel as the start point. Scan pixels in anti-clockwise order again and update the value of central pixel. The scanning process is shown in Figure 4(d). Repeat the above process until scanning to the start point $p_{i,j}$ of the recognized border. The marked border of both situations is exhibited in Figures 4(e) and (f) and 5(c). Specifically, for pixels on original boundaries of the image, with the help of expanded pixels, they can still perform the above process. Since the values of pixels on expanded boundaries are all 0, no new borders would be introduced. On the other hand, on finishing border following, the expanded boundaries are completely able to be eliminated.

• Step 4. Start a new raster scanning from the right adjacent pixel $p_{i,j+1}$ of $p_{i,j}$ . In order to recognize a new border, repeat Step 3 once none of the previous border pixels is involved in the next 3 × 3 matrix selected. Update the first central pixel $p_{i″,j″}$ of the new border and show the process of border following in Figure 4(g)–(k).

• Step 5. On finishing border following of the cover image, update the marked border with its absolute value to make sure the marked value is constant even though watermark bits are embedded inside. Show the updated border in Figures 4(l) and 5(d).

• Step 6. In order to ensure the feasibility of border following after watermark embedding and the reversible extraction in corresponding regions, sort each border according to the size of region it enclosed. If at least one zero-value pixel exists inside of the largest k borders, denote them as $B_{\gamma }(\gamma =1,2,...,k)$ .

Figure 4.

Border following of regions: (a) pixels of a binary image, (b) clockwise scanning, (c) first anti-clockwise scanning, (d) second anti-clockwise scanning, (e) first-border presentation, (f) end of first round scanning, (g) find a new border, (h) clockwise scanning of the new border, (i) first anti-clockwise scanning of the new border, (j) second-border presentation, (k) end of second round scanning, and (l) marked border with its absolute value.

Figure 5.

Border following of a single pixel: (a) pixels of a binary image, (b) clockwise scanning, (c) border presentation, and (d) marked border with its absolute value.

Watermark embedding based on histogram shifting

According to the procedure of image pre-processing, at least one zero point exists inside of the recognized border. Denote the pixel value of peak-value point as $m_{\gamma }$ and the pixel value of the nearest zero-value point as $t_{\gamma }$ , in which $\gamma$ is the index of recognized border $B_{\gamma }$ and $\gamma$ ∈ [1, k]. For simplicity, we assume $m_{\gamma }$ < $t_{\gamma }$ . In addition, suppose the capacity of cover image is larger than or equal to the length of watermark sequence. To facilitate the illustration, some notations used in this article are listed in Table 1.

Table 1.

Notations used in this article.

Notations	Notation description
I	M × N cover image.
$I_s$	Shifted image.
$I\prime$	Watermarked image.
$I_r$	Recovered image.
$\{w_l,l=1,2,...,L\}$	Watermark image with length L.
$\{w_{l\prime },l=1,2,...,L\}$	Recovered watermark sequence with length L, which is initially empty.
$B_{\gamma }$	Coordinates of pixels on the border of un-watermarked area, $\gamma =1,2,...,k$ .
$B{\prime }_{\gamma }$	Coordinates of pixels on the border of watermarked area, $\gamma =1,2,...,k$ .
$p_{i,j}$	Pixels of I, $i=1,2,...,M$ , $j=1,2,...,N$ .
$v_{p_{i,j}}$	Pixel value of $p_{i,j}$ , $i=1,2,...,M$ , $j=1,2,...,N$ .
$H_{\gamma }(x)$	Histogram of pixels inside of $B_{\gamma }$ , x ∈ [ $0,255$ ]
$h_{\gamma }(x)$	Ordinate of x in $H_{\gamma }(x)$ , $\gamma =1,2,...,k$ .
$m_{\gamma }$	Pixel value at the peak point of $H_{\gamma }(x)$ , $\gamma =1,2,...,k$ .
$t_{\gamma }$	Pixel value at the zero point to $m_{\gamma }$ , $\gamma =1,2,...,k$ .

In order to embed watermark into I, we first scan pixels inside of each border $B_{\gamma }$ ( $\gamma$ ∈ [1, k]) to find out the corresponding peak point whose value equals to $m_{\gamma }$ . Shift the pixels whose value is between $m_{\gamma }$ and $t_{\gamma }$ by “1” to prepare for watermark embedding. The process of histogram shifting can be performed as shown in Table 2. Then, from $B_1$ to $B_k$ , embed watermark sequence recurrently in the way listed in Table 3, until every one of the embedding position is occupied. Without loss of generality, in the following steps, we take $B_{\gamma }$ ( $\gamma$ ∈ [1, k]) for example to describe the procedure mentioned above in detail.

Table 2.

Histogram shifting.

Input: M × N cover image I, recognized borders

$B_{\gamma }(\gamma =1,2,...,k)$ .

Output: Shifted image $I_s$ , pixel value $m_{\gamma }(\gamma =1,2,...,k)$

of the peak point.

Obtain the pixels $p_{i,j}$ inside of $B_{\gamma }$ , with values $v_{p_{i,j}}$

$(i=1,2,...,M,j=1,2,...,N)$ .

Loop recognized border $B_{\gamma },\gamma =1$ to k.

Take pixels inside of $B_{\gamma }$ and its corresponding

histogram $H_{\gamma }(x)(\gamma =1,2,...,k)$ .

Find the peak point of $H_{\gamma }(x)$ and denote its

pixel value as $m_{\gamma }$ .

Find the nearest zero point to the peak point,

whose pixel value is $t_{\gamma }$ .

for $v_{p_{i,j}}=m_{\gamma }+1$ to $t_{\gamma }-1$ .

if $(m_{\gamma }<v_{p_{i,j}}\mathrm{\&}\mathrm{\&}{v}_{p_{i,j}}<t_{\gamma })$

$v_{p_{i,j}}=v_{p_{i,j}}+1$

end if

end

end

Get the shifted image $I_s$ and peak point value $m_{\gamma }$

$(\gamma =1,2,...,k)$ .

Table 3.

Watermark embedding.

Input: Shifted image $I_s$ , watermark sequence { $w_l,l=1,2,$

…, L}, recognized borders $B_r(r=1,2,...,k)$ ,

pixel value $m_{\gamma }$ $(\gamma =1,2,...,k)$ of each peak point in

$H_{\gamma }(x)$ $(\gamma =1,2,...,k,x=0,1,...,255)$ .

Output: Watermarked image $I\prime$ .

Obtain the pixels $p_{i,j}$ inside of $B_{\gamma }$ , with values $v_{p_{i,j}}$

$(i=1,2,...,M,j=1,2,...,N)$ .

$\mathrm{count}=1$

Loop recognized border $B_{\gamma },\gamma =1$ to k.

Scan pixels $p_{i,j}$ inside of $B_{\gamma }$ .

if $(v_{p_{i,j}}==m_{\gamma })$

Judge the difference of count and L to determine

the start point to  check the watermark sequence

{ $w_l$ }

if (count ≤ L)

Check { $w_l$ } from l = count.

if ( $w_{\mathrm{count}}==0$ )

$v_{p_{i,j}}=m_{\gamma }$

$\mathrm{count}=\mathrm{count}+1$

else if $(w_{\mathrm{count}}==1)$

$v_{p_{i,j}}=m_{\gamma }+1$

$\mathrm{count}=\mathrm{count}+1$

end if

else if $(w_{\mathrm{count}}>L)$

$\mathrm{count}=\mathrm{count}$ mod L

go to Step 7

end if

end if

end

Generate the watermarked image $I\prime$ .

• Step 1. Generate histograms of pixels inside of each border $B_{\gamma }$ ( $\gamma$ ∈ [1, k]), which are denoted as $H_{\gamma }(x)$ . Similar to the method proposed by Ni et al., ¹⁴ before histogram shifting, we first find out the peak point in $H_{\gamma }(x)$ and its nearest zero point. Then, scan pixels inside of each $B_{\gamma }$ in a sequence order, from top to bottom, and left to right. Once a pixel with value ${v_p}_{i,j}$ (i ∈ [1, M], j ∈ [1, N], $m_{\gamma }$ < $v_{p_{i,j}}$ < $t_{\gamma }$ ) is encountered, increase $v_{p_{i,j}}$ by “1” to leave the position corresponding to $m_{\gamma }$  + 1 empty in the histogram as shown in Table 2. For a $v_{p_{i,j}}$ , the principle of the above procedure can be denoted as follows

$$v_{p_{i,j}}=\{\begin{array}{c}{v}_{p_{i,j}},v_{p_{i,j}}\le m_{\gamma }\mathrm{or}{v}_{p_{i,j}}\ge t_{\gamma }\hfill \\ \multicolumn{1}{c}{v_{p_{i,j}}+1,m_{\gamma }<v_{p_{i,j}}<t_{\gamma }}\end{array}$$

(2)

• Step 2. Scan pixels inside of $B_{\gamma }$ in the same order as in Step 1 to find out pixels with value $m_{\gamma }$ and put them in the sequence { $a_r$ , r = 1, 2, …, $h_{\gamma }(m_{\gamma })$ }. For the region inside of $B_{\gamma }$ , the capacity is $h_{\gamma }(m_{\gamma })$ , thus $\sum _{\gamma =1}^k{h}_{\gamma }(m_{\gamma })$ is the capacity of I. Check the to-be-embedded bit $w_l$ (l ≤ [1, L]) in the watermark sequence and the start position is selected as shown in Table 3. Once $w_l=1$ , increase the corresponding pixel value of $a_r$ by “1.” Otherwise, keep the pixel value unchanged. We take $a_r$ for example to show the update process of pixel value $v_{a_r}$

$$v_{a_r}=\{\begin{array}{c}{m}_{\gamma },w_{\mathrm{l}}=0\hfill \\ \multicolumn{1}{c}{m_{\gamma }+1,w_{\mathrm{l}}=1}\end{array}$$

(3)

Watermark extraction and recovery of cover image

Once receiving a watermarked image $I\prime$ , the receiver executes border following algorithm introduced above to recognize k largest borders $B{\prime }_{\gamma }$ ( $\gamma$ ∈ [1, k]) based on the same threshold value t and the number k. According to the employed border following algorithm, positions of the border could still be recognized without error even if watermark bits have already been embedded inside. Thus, watermark extraction and recovery of cover image are guaranteed.

We first scan pixels inside of each $B{\prime }_{\gamma }$ to find out embedding positions. Then, extract watermark bits according to the process shown in Table 4. In order to achieve recovery of the cover image, scan pixels inside of $B{\prime }_{\gamma }$ again to shift back pixels with $v_{p_{i,j}}$ (i ∈ [1, M], j ∈ [1, N], $m_{\gamma }$  + 1 < $v_{p_{i,j}}$ ≤ $t_{\gamma }$ ). The corresponding pseudocode is shown in Table 5. Similar to the procedure of watermark embedding, the following steps take $B{\prime }_{\gamma }$ for example to describe details of the above process.

Table 4.

Watermark extraction.

Input: Watermarked image $I\prime$ with recognized border $B{\prime }_{\gamma }$

$(\gamma =1,2,...,k)$ .

Output: Recovered watermark sequence $w{\prime }_l$ $(l=1,2,...,k)$ .

Obtain pixels $p_{i,j}$ inside of $B{\prime }_{\gamma }$ , each of which with

a value $v_{p_{i,j}}$ $(i=1,2,...,M,j=1,2,...,N)$ .

Loop $B{\prime }_{\gamma },\gamma =1$ to k.

Scan pixels $p_{i,j}$ inside of $B{\prime }_{\gamma }$ .

if ( $v_{p_{i,j}}==m_{\gamma }+1$ )

Extract a bit “1” into temporary watermark

sequence $\{w_q,q=1,2,...,\sum _{\gamma =1}^k{h}_{\gamma }(m_{\gamma })\}$

else if ( $v_{p_{i,j}}==m_{\gamma }$ )

Extract a bit “0” into sequence $\{w_q\}$

end if

end

Check $\{w_q\}$ to extract a complete watermark

sequence $\{w{\prime }_l,l=1,2,\dots ,L\}$ as recovered sequence.

Table 5.

Cover image recovery.

Input: Image $I\prime$ , border $B{\prime }_{\gamma }(\gamma =1,2,...,k)$ , original peak point

pixel value $B{\prime }_{\gamma }(\gamma =1,2,...,k)$ .

Output: Recovered image $I_r$

Obtain pixels $p_{i,j}$ inside of $B{\prime }_{\gamma }$ , each of which with

a value $v_{p_{i,j}}$ $(i=1,2,...,M,j=1,2,...,N)$ .

Loop border $B{\prime }_{\gamma },\gamma =1$ to k.

Scan pixels $p_{i,j}$ inside of $B{\prime }_{\gamma }$ .

for $v_{p_{i,j}}==m_{\gamma }$ to $t_{\gamma }$

if $(m_{\gamma }<v_{p_{i,j}}\mathrm{\&}\mathrm{\&}{v}_{p_{i,j}}\le t_{\gamma })$

$v_{p_{i,j}}=v_{p_{i,j}}-1$

end if

end

end

Get the recovered image $I_r$

• Step 1. Scan pixels inside of $B{\prime }_{\gamma }$ in the same order as the procedure of watermark embedding. If a pixel with value $v_{p_{i,j}}$  =  $m_{\gamma }+1$ is encountered, a bit “1” is extracted into the temporary watermark sequence $\{w_q,q=1,2,...,\sum _{\gamma =1}^k{h}_{\gamma }(x_{\gamma })\}$ . Otherwise, if a pixel whose value $v_{p_{i,j}}=m_{\gamma }$ is encountered, a bit “0” is extracted. Denote the process of watermark extracting as follows

$$w_q=\{\begin{array}{c}0,v_{p_{i,j}}=m_{\gamma }\hfill \\ \multicolumn{1}{c}{1,v_{p_{i,j}}=m_{\gamma }+1}\end{array}$$

(4)

• Step 2. Scan the pixels inside of $B{\prime }_{\gamma }$ once again in the same order as in Step 1. Once a pixel with value $v_{p_{i,j}}$ ∈ ( $m_{\gamma }$ , $t_{\gamma }$ ] is encountered, decrease $v_{p_{i,j}}$ by 1 to recover the original cover image. Show the recovering procedure as follows

$$v_{p_{i,j}}=\{\begin{array}{c}{m}_{\gamma },v_{p_{i,j}}\le m_{\gamma }\hfill \\ \multicolumn{1}{c}{m_{\gamma }-1,m_{\gamma }<v_{p_{i,j}}\le t_{\gamma }}\end{array}$$

(5)

• Step 3. On finishing extracting from $B{\prime }_1$ to $B{\prime }_k$ , check $\{w_q,q=1,2,...,\sum _{\gamma =1}^k{h}_{\gamma }(x_{\gamma })\}$ to extract a completed watermark sequence $\{w_l,l=1,2,...,L\}$ as the recovered sequence.

Security analysis

To evaluate the security of the proposed algorithm, we consider three types of attackers. The first type intercepts the watermarked image and wants to steal the content of the watermark. The latter two focus on specific types of watermarks. For the second type, the attackers aim at the watermark used for copyright protection. In order to abuse the content of images, it is devoted to destroy the watermark while keeping the cover image unchanged. While for the third one, they contrapose the watermark used for tampering detection. In this case, the watermark embedded may be the hash value of the content of cover image. On receiving the watermarked image, the attacker extracts the watermark to recover the cover image. Then it tampers the recovered image and re-generates its hash value before embedding. Obviously, the watermarked image would pass the process of tampering detection even though the content of which is tampered.

For the first type of attackers, they are completely able to obtain the threshold value at first by employing the Otsu method ²⁰ and then recognize watermarked regions with the help of border following algorithm. However, the watermark still cannot be successfully extracted on account that the positions of peak value point as well as zero value point before embedding are actually unknown to attackers. In this scenario, the security of the proposed algorithm is equal to histogram shifting–based ones, rather than being affected by the introduced image binarization and border following methods. As for the second type of attackers, once they destroy the watermark embedded, the cover image is actually not able to be recovered without error, which is ensured by the principle of reversible watermark algorithms, thus the security is guaranteed. For the third one, attackers have to extract watermark first. Due to the same reason mentioned above for the first type of attackers, watermark cannot be extracted since the previous positions of both peak and zero points are still unknown. As a result, security of the proposed algorithm is always guaranteed against three types of attackers mentioned above.

Experiments and results

In this section, we take experiments to validate the effectiveness and evaluate the efficiency of the proposed border following–based reversible watermarking algorithm. Our watermark embedding and extracting procedures are considered to be executed by sender and receiver of the watermarked image, respectively. In this section, we employ a workstation with Intel(R) Core (TM) i7-6700 CPU @3.40 GHz, 8GB RAM, and a 7200 RPM 1TB hard drive to implement both of them. All algorithms are implemented using MATLAB 2019a and Python version 3.7. We perform our experiments on three image datasets: Boss dataset, ²² Caltech 101 dataset, ²³ and Oxford5k dataset, ²⁴ in which the first one contains 40,000 images, the second one 9144 images, while the third one 5062 images. All results are on the average of 20 tries.

Watermark embedding and extracting

In this part, we first choose an image shown in Figure 6(a) from the Oxford5k dataset. According to its histogram in Figure 7, zero-value pixel is absent, which means the algorithm proposed by Ni et al. ¹⁴ is not applicable any more. We execute the pre-processing procedure and transform the image into a binary one shown in Figure 6(b). Specifically, we exhibit three largest available regions recognized under the border following algorithm and mark their respective borders in Figure 6(c). The relationship between the number of available regions and performance of the proposed algorithm is also evaluated in detail in next part of the experiment.

Figure 6.

Un-watermarked images: (a) original image, (b) binary image, and (c) recognized borders in the image.

Figure 7.

Histogram of original image.

We exhibit the pixels inside of each recognized border in Figure 8(a), (c), and (e), each of which is paired with the corresponding histogram, as is shown in Figure 8(b), (d), and (f). For each histogram, it contains 4, 50, and 121 zero value pixels, and the value of peak point is 3180, 456, and 1151, respectively, which means overflowing problem is avoided and embedding capacity is guaranteed if watermark bits are embedded in these regions. Embed watermark sequence iteratively by histogram shifting–based embedding method introduced above until every one of the embeddable positions are occupied. For the watermarked image shown in Figure 9, we re-recognized the borders by the border following algorithm and showed the watermarked pixels inside in Figure 10(a), (c), and (e) respectively, together with their histograms in Figure 10(b), (d), and (f).

Figure 8.

Un-watermarked regions and corresponding histograms: (a) region 1, (b) histogram of region 1, (c) region 2, (d) histogram of region 2, (e) region 3, and (f) histogram of region 3.

Figure 9.

Watermarked image.

Figure 10.

Watermarked regions and corresponding histograms: (a) region 1, (b) histogram of region 1, (c) region 2, (d) histogram of region 2, (e) region 3, and (f) histogram of region 3.

To validate the effectiveness of our proposed algorithm, we first verify whether the border could still be recognized by executing border following algorithm employed introduced above. According to the image pre-processing, it is clear that even if pixels inside of each region may change after watermark embedding, the largest three borders can still be accurately recognized by the receiver based on the agreement with the sender on the number of borders, for the reason that pixels of the borders are not embedded. The recognized borders in the watermarked image are shown in Figure 11.

Figure 11.

Recognized borders in the watermarked image.

For a selected cover image, present its extracted borders and the ones from its watermarked version in Figure 12(a) and (b), respectively. To demonstrate whether the latter one is identical to the former one, perform exclusive OR operation on them and show the result in Figure 12(c), which is a binary image. Since the result image is all black, the re-recognized borders are validated to be the same as previous ones, which means watermark embedding does not affect border following procedure and our proposed algorithm is effective.

Figure 12.

Extracted borders and result of exclusive OR: (a) border of un-watermarked image, (b) border of watermarked image, and (c) result of exclusive OR.

Then, Figure 13(a) exhibits extracted borders and regions inside of each one, while Figure 13(b) shows the ones from the watermarked image. To further demonstrate whether the watermark is embedded, perform exclusive OR operation on them and the result is shown in Figure 13(c). Inferring from Figures 12(c) and 13(c), we can eventually draw the conclusion that the borders are identical before and after watermark embedding.

Figure 13.

Extracted borders with pixels inside and result of exclusive OR: (a) unwatermarked regions, (b) watermarked regions, and (c) result of exclusive OR.

Finally, the process of image recovery is shown in Figure 14(a)–(d). Figure 14(a) exhibits the un-watermarked regions of the cover image. As the inverse process of embedding, we extract watermark bits from pixels inside of the re-recognized three borders, respectively, to recover the corresponding regions. Then we put the recovered regions back into the original image successively. The process is shown in Figure 14(b)–(d). It is worth noting that Figure 14(d) is the fully recovered image and it is completely consistent with the original image which is guaranteed by the principle of histogram shifting–based reversible watermarking.

Figure 14.

Process of image recovery and recovered image: (a) unrecovered image, (b) recover region 1, (c) recover region 2, and (d) recover region 3.

Performance evaluation

In this part, we compare our proposed algorithm with the classic histogram shifting–based reversible watermarking algorithm as well as the state of the art. In order to evaluate performance as objective as possible, we implement our algorithm together with algorithms proposed by Ni et al. ¹⁴ and Kim et al. ¹³ based on the three selected classic image datasets.

Availability of images in datasets

As the first step, we find out available images for our algorithm and Ni’s algorithm ¹⁴ from the selected datasets separately and compare availability. To ensure embedding capacity, we set the number of available borders in a single image to be 3, even though a few regions to be embedded means better performance to our algorithm. The result is shown in Figure 15, in the form of histogram pairs.

Figure 15.

Percentage of available images.

According to Figure 15, the percentage of available images to our algorithm is 94.75%, 67.81%, and 51.55% for Boss dataset, Caltech 101 dataset, and Oxford5k dataset, respectively. The ratio drops to 82.65%, 58.67%, and 32.71% for Ni’s algorithm. The reason lies in that Ni’s algorithm requires the existence of at least one zero-value point in histogram of the cover image. And for our proposed algorithm, the image is available as long as at least one zero point exists inside of the recognized border. Therefore, even if the whole image does not have a zero point, it is still possible to satisfy the requirements of our algorithm.

Imperceptibility of the proposed algorithm

Next, we compare the imperceptibility of our proposed algorithm and Kim’s algorithm ¹³ under the same amount of watermark bits embedded. In order to keep the computational overhead comparable for both algorithms, in Kim’s algorithm, we embed location map directly into cover image without compression.

We randomly take out 12 available images from the selected three image datasets, respectively, each of which with 4 pieces. The images selected are shown in Figures 16–18. We restrict the amount of watermark bits embedded of both algorithms to be 1000, 2000, 3000, and 4000 bits, respectively, and compare the corresponding imperceptibility, which is evaluated by peak signal-to-noise ratio (PSNR) (dB). The result is shown in Table 6.

Figure 16.

Test images from Boss dataset: (a) building, (b) bell tower, (c) mountain, and (d) canyon.

Figure 17.

Test images from Caltech 101 dataset: (a) small-sized passenger aircraft, (b) medium-sized passenger aircraft, (c) fighter, and (d) transport plane.

Figure 18.

Test images from Oxford5k dataset: (a) dining room, (b) teaching building, (c) campus, and (d) church.

Table 6.

Comparison of imperceptibility.

Payload (bits)		1000		2000		3000		4000
		PSNR (dB)
Datasets	Images	Proposed	Kim’s	Proposed	Kim’s	Proposed	Kim’s	Proposed	Kim’s
Boss	a	64.38	53.94	63.17	53.83	62.20	53.75	61.44	53.67
	b	57.63	56.33	57.34	56.26	57.18	56.19	57.15	56.14
	c	60.50	56.10	59.97	55.95	59.48	55.79	59.06	55.66
	d	60.20	59.98	59.71	57.24	59.24	56.12	58.84	55.86
Caltech 101	a	64.75	55.74	63.16	55.61	61.96	55.50	61.06	55.38
	b	65.49	57.13	63.90	56.94	62.70	56.69	61.80	56.23
	c	63.60	55.30	62.45	54.71	61.51	54.32	60.77	54.05
	d	64.88	55.10	63.59	55.03	62.56	54.96	61.77	54.88
Oxford5k	a	78.07	74.14	75.97	71.54	74.52	69.99	73.47	68.78
	b	74.43	72.19	73.40	70.77	72.53	69.84	71.84	68.95
	c	75.02	69.96	73.96	69.68	73.08	69.32	72.38	69.05
	d	80.06	70.29	77.09	68.91	76.14	67.85	74.66	66.94

PSNR: peak signal-to-noise ratio.

According to the table, the PSNR of our algorithm is obviously higher than Kim’s work. ¹³ For example, for the first selected image in Boss dataset, the PSNR of our algorithm is 64.38, 63.17, 62.20, and 61.44 dB for the payload of 1000, 2000, 3000, and 4000 bits, respectively, which is obviously higher than 53.94, 53.83, 53.75, and 53.67 dB for Kim’s algorithm. The reason is that in order to resist overflowing, Kim et al. embed a location map as auxiliary information into the cover image, which occupies large amounts of embedding space. And for our proposed algorithm, auxiliary information is not needed any more so that for the same quantity of watermark bits embedded, fewer pixels are shifted thus a better imperceptibility is guaranteed.

Relationship between binary threshold value and embedding capacity

Finally, we explore the relationship between binary threshold value t and embedding capacity C of the cover image. In order to evaluate correlation of the number of recognized borders and capacity simultaneously, we divide the 12 pieces of images employed above into three categories according to datasets and restrict the number k to be 1, 2, and 3 to calculate the average embedding capacity of three groups under different t, respectively. The result is shown in Figure 19(a)–(c).

Figure 19.

The relationship between binary threshold value and embedding capacity: (a) Boss dataset, (b) Caltech 101 dataset, and (c) Oxford5k dataset.

Referring to these figures, we find the general trend is that the average embedding capacity of each group increases with the number k in general. For example, in Figure 19(a), compared with the curve k = 1, when k = 2, the capacity (bits) increases from [7430, 9777] to [7818, 9794]. And once k = 3, the capacity is even greater. This is because in our scheme, larger k means more regions recognized in the cover image could be employed to embed watermark. Moreover, we can also find in the figure, in some selected values of t, various k corresponds to the same capacity, for example, under threshold t = 10, the curve of k = 2 overlaps with the curve of k = 3. This is because in this case, the number of recognized regions is actually 2. According to the result obtained, we can conclude that the embedding capacity of our proposed algorithm is flexible, which means once more regions recognized by border following algorithm are employed, the capacity of our algorithm still has room to improve. Finally, it is clear that the capacity C decreases with the increase of threshold value t. The reason is that, in our algorithm, the capacity is determined by the number of peak-value points, which is largely affected by the size of recognized regions. According to the principle of border following algorithm utilized, a smaller value of t means more pixels in the cover image are marked with 1, thus larger recognized regions could be obtained.

Universality of image binarization

In order to validate the universality of our proposed algorithm, we employ the Otsu method to generate binary threshold values for the selected 12 images, respectively. Then, we calculate the embedding capacity for each of them under the corresponding threshold value, and the average capacity for each group under different k. The result is shown in Table 7.

Table 7.

The relationship between binary threshold value and average embedding capacity.

The number of regions			1		2		3
Datasets	Images	Otsu threshold value	Capacity (bits)	Average capacity (bits)	Capacity (bits)	Average capacity (bits)	Capacity (bits)	Average capacity (bits)
Boss	a	145	12,277	8909	15,246	9700.25	15,257	9704.25
	b	153	9127		9241		9243
	c	164	9480		9486		9489
	d	160	4752		4828		5835
Caltech 101	a	130	8182	9188	8183	9240.5	8184	9260
	b	128	6887		6985		7000
	c	124	8935		9043		9103
	d	155	12,748		12,751		12,753
Oxford5k	a	97	11,708	8756.5	12,043	8952	12,283	9177
	b	90	11,608		11,851		12,204
	c	107	5029		5038		5047
	d	133	6681		6876		7174

According to the table, for Boss dataset, restrict the number k to be 1, 2, 3, the average embedding capacities are 8909, 9700.25, and 9704.25 bits, which are very close to the maximum values 9777.5, 9794, and 9796 bits in Figure 19(a). As for Caltech 101 dataset, the values change to 9188, 9240.5, and 9260 bits, which are also very close to the corresponding maximum average embedding capacities 9199, 9248.25, and 9301.5 bits in Figure 19(b). However, for Oxford5k dataset, restrict the number k to be 1, 2, 3, the average embedding capacities are 8756.5, 8952, and 9177 bits, which are lower than the maximum values 14,015.25, 14,111.75, and 14,230.75 bits in Figure 19(c).

The reason is that the Otsu method only ensures pixels in each one of the categories are as similar as possible. A natural result is that the number of peak point pixels in each category is maximized with high probability, which is the basic guarantee to achieve large capacity. However, it is not enough since that the capacity is actually determined by the number of peak point pixels inside of the regions recognized by border following algorithm. On calculating the threshold value, for images with good contrast ratio, pixels are ensured to be divided as accurately as possible, thus raising the possibility to achieve high capacity. On the other hand, for those with bad contrast ratio, due to the inherent defects of the Otsu method, image details are easy to be lost, resulting in the poor continuity of the region recognized by the border following algorithm, thus affecting the embedding capacity. However, Otsu method is still the most outstanding representative of binarization algorithm for gray scale images. Therefore, thanks to superior contrast ratio of images in both Boss and Caltech 101 datasets, they are with high capacity under the employed Otsu threshold value. While for Oxford5k dataset, the capacity drops rapidly due to worse contrast ratio. Despite the above problem, we still achieve fairly good performance since the average capacity for images in Oxford5k dataset reaches the average level in Figure 19(c).

Conclusion

In this article, we propose a novel histogram shifting–based reversible watermarking algorithm for images to resist overflowing problem. Specifically, we utilize border following algorithm to find out appropriate regions in the cover image for watermark embedding, thus auxiliary information is not needed any more. Our algorithm is compared with the classic histogram shifting–based reversible watermarking algorithm as well as the state of the art through experiments and the results show that the proposed algorithm has better performance.