# A Novel Printable Watermarking Method in Dithering Halftone Images

Authors: Hui-Lung Lee; Ling-Hwei Chen
Journal: Advances in Multimedia
 (2016)

---

## Abstract

Halftone images are commonly printed on books, newspapers, and magazines. How to protect the copyright of these printed halftone images becomes an important issue. Digital watermarking provides a solution for copyright protection. In this paper, we will propose a novel printable watermarking method for dithering halftone images. Based on downsampling and the property of a dispersed dithering screen, the method can resist cropping, tampering, and print-and-scan process attacks. In addition, comparing to Guo et al.’s method, the experimental results show that the proposed method provides higher robustness for the above-mentioned attacks and better visual quality in the high-frequency regions of halftone images.


---

## Body

## 1. Introduction

Digital halftoning is a method to convert continuous-tone images to two-tone ones; it is widely used in printing newspapers, magazines, books, and so forth. When viewed from a proper distance, halftone images resemble the original grayscale images. Today, many digital halftoning methods [1–3] were developed. Error diffusion, ordered dithering, and iteration-based technique are three common types of halftoning methods. Error diffusion [1] is a single-pass sequential algorithm. The past error is diffused back to the unprocessed neighboring pixels. When processing the current pixel, its gray value will add all the past error and compare with a fixed threshold 128 to determine its output. Ordered dithering [2] is applied to a threshold matrix to convert a gray image to a halftone image. It compares the pixel value with the threshold matrix to determine pixel output. Hence, it has better time efficiency. The iteration-based technique [3] is an iterative algorithm; it proceeds by generating an initial halftone image and then iteratively performs a local search on the halftone space by swapping and toggling to minimize the perceived error. It usually generates a better quality images than the error diffusion and the ordered dithering, but it is time consuming.Many watermarking techniques have been provided for halftone image copyright protection and authentication; they are divided into three categories: error diffusion based [4–11], ordered dithering based [4, 12–18], and iteration-based [19–21] techniques.For error diffusion based watermark techniques, in 2002, Fu and Au [4] proposed a few data hiding or watermarking methods in halftone images. When the original multitone image is not available, a data hiding smart pair toggling scheme was presented to hide data in halftone images. When the original multitone image is available and the halftoning method is error diffusion, a modified data hiding error diffusion method was provided to hide data in the halftone images by forced self-toggling with its distortion diffused to the surrounding pixels. This method can be applied to the halftone images generated by ordered dithering. Experimental results show that the proposed methods have high data hiding capacity, low computational complexity, good visual quality, and reasonable resistance toward noise. However, it is not robust to any distortions without applying error correction code, and some artifacts are found in the locations of pair toggling. Later, Fu and Au [5] embedded a single watermark or multiwatermarks in the parity domain of a halftone image during halftoning. However, it can only embed 1 bit to indicate whether a watermark or one of two watermarks exists. Thus, this method is improper for copyright authentication. In 2004, Fu and Au [6] proposed an improved method to embed a watermark in the local correlation coefficient between the watermark bits and the halftone image. The local correlation coefficient is computed by the exclusive operation between a security code and halftone image. However, if the security code size is small, the visual quality of the watermarked halftone image would be degraded. In 2006, Pei and Guo [7] proposed a data hiding method in several halftone images or color planes using minimal-error bit searching. It employed the gray code to divide code vectors into two groups, and each group corresponds to a watermark bit 0 or 1. According to the watermark bit embedded, most suitable code vectors with better visual quality are chosen to form the watermarked halftone images. However, the quality degrades significantly when capacity increases up to 50%. In 2007, Li et al. [8] proposed a watermarking method for error diffusion halftone images; the method provides a block-overlapping parity check algorithm to reduce the number of pair toggling required in the Fu and Au’s method [4]. Experiments show that the method has better visual quality than Fu and Au’s method [4]. To treat Pei and Guo’s problem [7], Guo and Liu [9] proposed a data hiding method in several halftone images by using overall minimal-error searching and secret sharing. Moreover, the least-mean-square based scheme is also employed to achieve even better quality and edge enhanced embedded results. However, the homogeneous regions of watermarked images maybe have artifacts.For ordered dithering based watermark techniques, in 2001, Fu and Au [14] proposed a two-phase watermarking method for ordered dithering images. First, one out of every M pseudorandom locations is selected using threshold selection to embed one data bit. Second, screen modification is applied to the local neighborhood of the selected location to change the ordered dithering screen to achieve the desired data embedding. Some quality measures were proposed to evaluate the visual quality of a dithering image. Simulation results show that the method can hide a large amount of data while maintaining good visual quality. However, it is not robust to the print-and-scan process. In 2001, Hel-Or [13] proposed a method to embed a watermark in printed images. First, based on watermark bits, a dithering screen is created by selecting different dither matrices; then the screen is used to produce a printed image. The method is robust under reconstruction errors. However, it is not robust to cropping and has artifacts.In 2005, Pei et al. [15] presented a method to embed watermarks into dithered halftone images. The method divides a dithered halftone image into several sub-subimages by the bit and sub-subimage interleaving preprocesses, and each watermark bit is embedded into each pair of sub-subimages. The method has low computational complexity and flexible embedding capacity. But the method requires the knowledge of the original watermark to do copyright authentication. To treat Pei et al.’s problem, in 2008, Guo et al. [12] proposed another watermarking method using the blind paired subimage matching ordered dithering (BPSMOD) technique. It does not require the knowledge of the original watermark in the watermark extraction. However, the visual quality in the boundary of the embedded dithered image may be degraded.In 2010, Bulan et al. [16] proposed a data hiding method that embeds bits through clustered-dot orientations during halftoning process. For extracting the embedding data, a moment-based extracting method is used to detect the clustered-dot orientations. The method is only applicable for clustered-dot halftoning methods, and it relies on the ability to accurately control the printing of the halftone image; this may be restrictive in some applications. In 2013, Feng et al. [17] proposed a halftone watermarking algorithm based on particle swarm optimization. It is robust under smearing and cropping attacks. Unfortunately, it needs mean filtering and median filtering to remove noise from the recovered watermark image. This is only suitable for a watermark with a solid black/white object. Thus, the method is unsuitable for a watermark with a random sequence.For iteration-based watermark techniques, in 2003, Chun and Ha [19] proposed a watermark technique based on iterative halftoning method. In the embedding stage, a pseudorandom number generator is used to locate the embedding locations and force these pixel values at these locations to be 0 or 1 according to the watermark bits. Then, in the error minimizing stage, for each unembedded pixel, check whether toggling the pixel value or swapping the pixel value with neighbor pixels can reduce the perceived halftoning error. In 2012, Guo et al. [20] proposed a DBS-based orientation modulation watermarking method. In this method, the direction of the point spread function is used to represent different watermark values. To extract the watermark bit, the LMS trained filters and naive Bayes classifier are used to classify the angle. In 2015, Guo et al. [21] proposed a halftoning-based multilayer watermarking method. An efficient direct binary search and lookup table method is applied to embed multiple watermarks. Then, the least mean square and native Bayes classifier are used to extract the watermarks. Although all these methods provide excellent image quality, they are time consuming.In this paper, we focus on ordered dithering halftone images. And a blind watermarking method will be proposed to treat the disadvantages of the above-mentioned dithering based watermarking methods. First, a grayscale image is transformed into a dithering halftone image according to ann
×
n dispersed dithering screen (for convenience of illustration, here, we take n
=
4; see Figure 1); then the halftone image is divided into several subimages through downsampling. For each subimage, to embed watermark bits, it is first divided into several 4 × 4 blocks. Then, the number of black pixels, p
j, in all blocks corresponding to the position with the jth smallest value T
j (see Figure 1(c), j
=
3, T
3
=
56) in the 4 × 4 dispersed dithering screen is counted. Finally, we take (
p
u
,
p
v
) as a pair to embed a bit based on the sign of (p
u
-
p
v), where (
u
,
v
)
=
(
0
,
4
)
,
(
1,5
)
,
(
2,6
)
,
(
3,7
)
,
(
8,15
)
,
(
9,14
)
,
(
10,12
), or (
11,13
). If the embedding bit is 0 and p
u
<
p
v or the embedding bit is 1 and p
u
>
p
v, nothing is done. Otherwise, in each block, the pixel at position with the uth smallest value and the pixel at position with the vth smallest value are swapped. Since |
p
u
-
p
v
| is usually larger than |
p
u
-
p
u
+
1
|, this provides higher robustness than Guo et al.’s method [12] for the print-and-scan process. In addition, since the number of black pixels in each block is not changed, the proposed method also provides higher visual quality in the edge boundary than Guo et al.’s method [12]. Furthermore, the downsampling technique is presented to provide higher robustness than Guo et al.’s method for cropping and tampering. The rest of the paper is organized as follows. Section 2 outlines Guo et al.’s [12, 15] methods. Section 3 describes the proposed method. Section 4 shows the experimental results and comparisons. Section 5 draws conclusions.Figure 1
An example of dispersed dithering screens. (a) A 4 × 4 dispersed dithering screen. (b) An 8 × 8 dispersed dithering screen. (c) The order and position of each pixel in (a). (d) The order and position of each pixel in (b).
(a)
(b)
(c)
(d)


## 2. A Brief Description for Guo et al.’s Methods

As mentioned previously, Guo et al. [12] proposed a watermarking method using BPSMOD in dithering halftone images. At first, a dispersed dithering method is adopted to convert a grayscale image into a dithering halftone image. Then, the bit-interleaving algorithm proposed by Pei et al. [15] is used to arrange the dithering halftone image. After that, the BPSMOD is applied to the arranged image to embed watermark bits. To raise the embedding capacity, a sub-subimage interleaving algorithm [12, 15] is adopted. The details are described in the following subsections.


### 2.1. Bit-Interleaving Algorithm in a Dithering Halftone Image

As mentioned above, in Guo et al.’s method [12], an n
×
n dispersed dithering screen (DS) [1] is first applied to a P
×
Q grayscale image I to result in a dithering halftone image H according to the following equation:(1)
H
i
,
j
=
0
,
x
i
,
j
<
DS
i
mod
⁡
n
,
j
mod
⁡
n
,
255
,
otherwise
,where x
(
i
,
j
) and H
(
i
,
j
) are the gray levels of pixel (
i
,
j
) in I and H, respectively. D
S
(
i
,
j
) is the value of the position (
i
,
j
) in the dispersed dithering screen. Figure 2(a) shows a 128 × 128 grayscale image. Figure 2(b) is the resulting dithering halftone image by applying Figure 1(a) to Figure 2(a).Figure 2
An example of bit-interleaving algorithm [12]. (a) Lena image. (b) Dithering halftone image of (b) using Figure 1(a). (c) Bit-interleaving result of (b). (d) Dithering halftone image divided into 16 subimages. (e) The result of applying bit-interleaving to each subimage in (d).
(a)
(b)
(c)
(d)
(e)After obtaining the dithering halftone image, all pixels corresponding to the same screen value are then grouped into a subimage; this will result inn
×
n subimages, each of which has P
/
n
×
Q
/
n pixels. Finally, according to the screen values, all subimages will be sorted in ascending order of the screen values and arranged from left to right and bottom to top to result in a binary image R
H. Let R
H
j be the jth subimage, where j
=
0,1
,
…
,
(
n
×
n
)
-
1, and the bottom-left subimage is R
H
0. The above process is called bit-interleaving [12, 15]. Figure 2(c) shows the bit-interleaving result of Figure 2(b), and it contains 16 subimages, and the bottom-left subimage corresponds to screen value 8.


### 2.2. BPSMOD

In BPSMOD, based onR
H, subimages R
H
j and R
H
j
+
1 are considered a pair (
R
H
j
,
R
H
j
+
1
), where j
=
2
m and m
=
0,1
,
…
,
(
n
×
n
)
/
2
-
1. Since the screen value used to form R
H
j is smaller than that used to form R
H
j
+
1, R
H
j will usually have less black pixels than R
H
j
+
1. However, R
H
j sometimes has black pixels more than (equal to) R
H
j
+
1; this kind of pairs is called nonincreased black pixel pair (NIP). Before embedding, if a pair (
R
H
j
,
R
H
j
+
1
) is a NIP, it will be modified by increasing black pixels of R
H
j
+
1 or decreasing black pixels of R
H
j to make the modified R
H
j have less black pixels than the modified R
H
j
+
1. Then, in embedding, each pair (
R
H
j
,
R
H
j
+
1
) will embed 1 bit. If watermark bit being embedded is 1, R
H
j and R
H
j
+
1 will be swapped. Otherwise, nothing is done.Since there are(
n
×
n
)
/
2 pairs of subimages in R
H and each pair of subimages embeds a bit, the embedding capacity is (
n
×
n
)
/
2. To increase the embedding capacity, Guo et al. [12] first divides the original halftone image H into k
×
l subimages H
is. Then, the above-mentioned bit-interleaving method is applied to each H
i to get n
×
n sub-subimages S
H
i
,
j’s to embed (
n
×
n
)
/
2 bits. Hence, the capacity is increased to (
n
k
×
n
l
)
/
2. Figure 2(d) shows the result of dividing Figure 2(c) into 16 subimages. Figure 2(e) shows the result of applying bit-interleaving to each subimage in Figure 2(d).Table1 shows the numbers of black pixels in the sub-subimage pairs (
S
H
0
,
j
,
S
H
0
,
j
+
1
) of the subimage H
0 in the bottom-left of Figure 2(e), where j
=
2
m and m
=
0
,
1
,
…
,
7. In Table 1, the difference of the numbers of black pixels between S
H
0
,
j and S
H
0
,
j
+
1 is 0, for j
=
4,8
,
12. These sub-subimage pairs are NIPs. To eliminate these NIPs, at least one white pixel is chosen and changed into a black pixel in S
H
0,5, S
H
0
,
9, and S
H
0
,
13, respectively. This may make the visual quality degraded. Furthermore, from Table 1, we find that the average difference of numbers of black pixels in the eight sub-subimage pairs is 5.25. The low difference of black pixel numbers between S
H
0
,
j and S
H
0
,
j
+
1 could lead to the sign of the difference being altered, when the embedded dithered image is processed by print-and-scan process. This will make the extracted watermark bit wrong. Here, we will propose a method to treat these disadvantages.Table 1
The black pixel numbers of eight sub-subimage pairs in the bottom-left subimage of Figure2(d).
j
# Black pixels
The difference of black pixel numbers betweenS
H
0
,
j and S
H
0
,
j
+
1
S
H
0
,
j
S
H
0
,
j
+
1
0
0
2
2
2
23
33
10
4
0
0
0
6
18
37
19
8
0
0
0
10
3
6
3
12
0
0
0
14
1
9
8


## 2.1. Bit-Interleaving Algorithm in a Dithering Halftone Image

As mentioned above, in Guo et al.’s method [12], an n
×
n dispersed dithering screen (DS) [1] is first applied to a P
×
Q grayscale image I to result in a dithering halftone image H according to the following equation:(1)
H
i
,
j
=
0
,
x
i
,
j
<
DS
i
mod
⁡
n
,
j
mod
⁡
n
,
255
,
otherwise
,where x
(
i
,
j
) and H
(
i
,
j
) are the gray levels of pixel (
i
,
j
) in I and H, respectively. D
S
(
i
,
j
) is the value of the position (
i
,
j
) in the dispersed dithering screen. Figure 2(a) shows a 128 × 128 grayscale image. Figure 2(b) is the resulting dithering halftone image by applying Figure 1(a) to Figure 2(a).Figure 2
An example of bit-interleaving algorithm [12]. (a) Lena image. (b) Dithering halftone image of (b) using Figure 1(a). (c) Bit-interleaving result of (b). (d) Dithering halftone image divided into 16 subimages. (e) The result of applying bit-interleaving to each subimage in (d).
(a)
(b)
(c)
(d)
(e)After obtaining the dithering halftone image, all pixels corresponding to the same screen value are then grouped into a subimage; this will result inn
×
n subimages, each of which has P
/
n
×
Q
/
n pixels. Finally, according to the screen values, all subimages will be sorted in ascending order of the screen values and arranged from left to right and bottom to top to result in a binary image R
H. Let R
H
j be the jth subimage, where j
=
0,1
,
…
,
(
n
×
n
)
-
1, and the bottom-left subimage is R
H
0. The above process is called bit-interleaving [12, 15]. Figure 2(c) shows the bit-interleaving result of Figure 2(b), and it contains 16 subimages, and the bottom-left subimage corresponds to screen value 8.


## 2.2. BPSMOD

In BPSMOD, based onR
H, subimages R
H
j and R
H
j
+
1 are considered a pair (
R
H
j
,
R
H
j
+
1
), where j
=
2
m and m
=
0,1
,
…
,
(
n
×
n
)
/
2
-
1. Since the screen value used to form R
H
j is smaller than that used to form R
H
j
+
1, R
H
j will usually have less black pixels than R
H
j
+
1. However, R
H
j sometimes has black pixels more than (equal to) R
H
j
+
1; this kind of pairs is called nonincreased black pixel pair (NIP). Before embedding, if a pair (
R
H
j
,
R
H
j
+
1
) is a NIP, it will be modified by increasing black pixels of R
H
j
+
1 or decreasing black pixels of R
H
j to make the modified R
H
j have less black pixels than the modified R
H
j
+
1. Then, in embedding, each pair (
R
H
j
,
R
H
j
+
1
) will embed 1 bit. If watermark bit being embedded is 1, R
H
j and R
H
j
+
1 will be swapped. Otherwise, nothing is done.Since there are(
n
×
n
)
/
2 pairs of subimages in R
H and each pair of subimages embeds a bit, the embedding capacity is (
n
×
n
)
/
2. To increase the embedding capacity, Guo et al. [12] first divides the original halftone image H into k
×
l subimages H
is. Then, the above-mentioned bit-interleaving method is applied to each H
i to get n
×
n sub-subimages S
H
i
,
j’s to embed (
n
×
n
)
/
2 bits. Hence, the capacity is increased to (
n
k
×
n
l
)
/
2. Figure 2(d) shows the result of dividing Figure 2(c) into 16 subimages. Figure 2(e) shows the result of applying bit-interleaving to each subimage in Figure 2(d).Table1 shows the numbers of black pixels in the sub-subimage pairs (
S
H
0
,
j
,
S
H
0
,
j
+
1
) of the subimage H
0 in the bottom-left of Figure 2(e), where j
=
2
m and m
=
0
,
1
,
…
,
7. In Table 1, the difference of the numbers of black pixels between S
H
0
,
j and S
H
0
,
j
+
1 is 0, for j
=
4,8
,
12. These sub-subimage pairs are NIPs. To eliminate these NIPs, at least one white pixel is chosen and changed into a black pixel in S
H
0,5, S
H
0
,
9, and S
H
0
,
13, respectively. This may make the visual quality degraded. Furthermore, from Table 1, we find that the average difference of numbers of black pixels in the eight sub-subimage pairs is 5.25. The low difference of black pixel numbers between S
H
0
,
j and S
H
0
,
j
+
1 could lead to the sign of the difference being altered, when the embedded dithered image is processed by print-and-scan process. This will make the extracted watermark bit wrong. Here, we will propose a method to treat these disadvantages.Table 1
The black pixel numbers of eight sub-subimage pairs in the bottom-left subimage of Figure2(d).
j
# Black pixels
The difference of black pixel numbers betweenS
H
0
,
j and S
H
0
,
j
+
1
S
H
0
,
j
S
H
0
,
j
+
1
0
0
2
2
2
23
33
10
4
0
0
0
6
18
37
19
8
0
0
0
10
3
6
3
12
0
0
0
14
1
9
8


## 3. The Proposed Method

The proposed method contains two parts: embedding and extraction. Figure3 shows the block diagram of the proposed method. In the embedding part, first, a grayscale image I is converted into a halftone image H. Secondly, H is segmented into k
×
l subimages H
i through downsampling. Thirdly, watermark bits are embedded into each subimage. Fourthly, all pixels in the embedded subimages E
H
i are relocated to their original positions to form the embedded dithered image E
H. Finally, E
H can be printed on a paper. In the extraction, after transmission, the printed embedded dithered image E
H
p is scanned by a scanner, and then a scanned embedded dithered image E
H
s is produced. Since the print-and-scan process could cause distortion, a recovering algorithm proposed by Guo et al. [12] is used to correct the distortion in E
H
s. After that, the output E
H
′ will be segmented into several subimages through downsampling. Finally, the watermark w
′ can be extracted from each subimage.Figure 3
The block diagram of the proposed method.In this section, we will first introduce the proposed embedding algorithm. Then, the provided extracting algorithm is described.


### 3.1. Embedding Algorithm

The embedding algorithm contains four stages: halftone conversion, subimage segmentation, embedding, and relocation. They are described in the following.


#### 3.1.1. Halftone Conversion

Ann
×
n dispersed dithering screen (DS) [1] is first applied to a P
×
Q grayscale image I to result in a dithering halftone image H according to (1).


#### 3.1.2. Subimage Segmentation

Suppose that a watermarkw with T bits will be embedded. In the subimage segmentation stage, H is segmented into k
×
l subimages through downsampling, where k
×
l
≥
T
/
(
n
×
n
)
/
2 and each subimage has P
/
k
×
Q
/
l pixels. First, H is divided into P
/
k
n
×
Q
/
l
n blocks, each of which has k
n
×
l
n pixels. Then, each block is further divided into k
×
l subblocks, each of which has n
×
n pixels. Let A
i
,
j be the jth subblock in block i, where i
=
0,1
,
…
,
(
P
×
Q
/
k
n
×
l
n
-
1
) and j
=
0,1
,
…
,
(
k
l
-
1
), respectively. Finally, through downsampling, all jth subblocks (
A
i
,
j
,
i
=
0,1
,
…
,
(
P
×
Q
/
k
n
×
l
n
-
1
)
) are grouped into a subimage H
j. For the convenience of explanation, all H
js are arranged into an image.Figure4(a) shows an image divided into 3 × 3 blocks with P
=
Q
=
48, k
=
l
=
4, and n
=
4, each of which is further divided into 4 × 4 subblocks. Figure 4(b) shows the subimage segmentation result of Figure 4(a). Figure 4(c) shows the segmentation result of Figure 2(b) with T
=
120, k
=
4, l
=
4, and k
×
l
=
16
>
120
/
4
×
4
/
2
=
15. The rectangles in Figure 4(c) denote the 16 subimages.Figure 4
An example of subimage segmentation. (a) An image divided into 3 × 3 blocks, each of which has 4 × 4 subblocks. (b) The segmentation result of (a). (c) The segmentation result of Figure2(b).
(a)
(b)
(c)


#### 3.1.3. Embedding

In the embedding stage, ann
×
n dispersed dithering screen with n
=
2
k and k
∈
N is used. The n
×
n dispersed dithering screen is first divided into 2 × 2 dispersed dithering screens. Secondly, in each 2 × 2 dispersed dithering screen, two elements with thresholds more than 128 are grouped as a pair, and the other two elements with thresholds less than 128 are grouped as a pair. Hence, we can obtain n
×
n
/
2 pairs.Thirdly, sort all values in then
×
n dispersed dithering screen and give each value an order; then each pair is represented by its corresponding order. For example, in Figure 1(b) with n
=
8, the four elements in the top-left 2 × 2 dispersed dithering screen marked by a red rectangle have thresholds 6, 238, 134, and 70. The two elements with thresholds 6 and 70 are grouped as a pair, and 134 and 238 are grouped as another pair. After sorting the values in the dispersed dithering screen in Figure 1(b), the corresponding order of each element is shown in Figure 1(d). The two pairs are represented by their corresponding orders as (
1,17
) and (
33,59
).Fourthly, letO
D
S
j be the position with order j in the dispersed dithering screen DS, where j
=
0
,
…
,
n
×
n
-
1. Figure 1(c) shows the order and position of each pixel in the 4 × 4 dispersed dithering screen shown in Figure 1(a); in this figure, O
D
S
0
=
(
2,2
), O
D
S
15
=
(
2,3
). Fifthly, each subimage H
i is divided into blocks with size n
×
n, and all pixels at position O
D
S
j of all blocks are grouped into a sub-subimage S
H
i
,
j.Sixthly, the number,p
j, of black pixels at S
H
i
,
j is counted. Then, we take (
p
u
,
p
v
) as a pair, when n
=
4, (
u
,
v
)
=
(
0
,
4
)
,
(
1,5
)
,
(
2,6
)
,
(
3,7
)
,
(
8,15
)
,
(
9,14
)
,
(
10,12
), or (
11,13
). Note that, for each of above-mentioned pair (
p
u
,
p
v
) with n
=
4, the difference, d
(
u
,
v
), of values of O
D
S
u and O
D
S
v in the dispersed dithering screen DS is not less than 32. However, for each pair (p
i
,
p
i
+
1) used by Guo et al., the difference, d
(
i
,
i
+
1
), of values of O
D
S
i and O
D
S
i
+
1 in the dispersed dithering screen DS is equal to 16. This will make each pair (
p
u
,
p
v
) used in the proposed method have larger |
p
u
-
p
v
| than |
p
i
-
p
i
+
1
| used in Guo et al.’s method. One example is given in Table 2. Table 2 shows the black pixel numbers of each pair (
p
u
,
p
v
) in the top-left subimage of Figure 4(c); the average difference of numbers of black pixels in the eight pairs is 16.75, which is greater than 5.25 in Guo et al.’s method (see Table 1). This means that the proposed method will provide higher robustness than Guo et al.’s method for the print-and-scan process.Table 2
The black pixel numbers in eight pairs of the top-left subimage in Figure4(c).
Pairs
The number of black pixels
p
u
p
v
(p
0, p
4)
0
18
(p
1, p
5)
0
32
(p
2, p
6)
10
35
(p
3, p
7)
16
44
(p
8, p
15)
53
64
(p
9, p
14)
54
64
(p
10, p
12)
58
64
(p
11, p
13)
60
64Finally, one bit is embedded into each pair(
p
u
,
p
v
). If the embedding bit is 0 and p
u
<
p
v or the embedding bit is 1 and p
u
>
p
v, nothing is done. Otherwise, in each block, the pixel at position O
D
S
u and the pixel at position O
D
S
v are swapped. Note that if p
u
=
p
v, no bit will be embedded into the pair. This kind of pairs is called equivalent black pixel pair (EBP).


#### 3.1.4. Relocation

After embedding, all pixels are relocated to their original positions to form the embedded dithered imageE
H. Then E
H can be printed on a paper to form a printed embedded dithered image E
H
p. Note that the embedding capacity is k
×
l
×
(
n
×
n
)
/
2 bits.Figure5(a) shows the result of embedding 120 watermark bits into Figure 4(c). The rectangle marked in Figure 5(a) denotes the first subimage with 8 watermark bits 10101010 embedded. Figure 5(b) shows the embedded dithered image resulting from relocating Figure 5(a).Figure 5
An example of embedding algorithm. (a) The result of embedding 120 bits into Figure4(c). (b) The embedded dithered image by relocating (a).
(a)
(b)


### 3.2. Recovering Algorithm for Print-and-Scan Process

When we receive the paper with the printed embedded dithered imageE
H
p, a scanner is used to capture E
H
p and produce a scanned image E
H
s. The scanned image E
H
s usually has geometrical distortion and dot gain effect due to the scanner and printer properties. Dot gain is a phenomenon in printing which causes the size of a dot to be increased or decreased slightly. Here, we adopt the recovering algorithm proposed by Guo et al. [12] to get the embedded dithered image E
H
′.


### 3.3. Watermark Extraction Algorithm

The watermark extraction contains two steps: subimage segmentation and extraction. To extract the embedded watermark,E
H
′ will be segmented into several subimages through downsampling mentioned in the embedding algorithm. For each subimage H
i
′, we divide it into blocks with size n
×
n and then count the number, p
j, of black pixels at position O
D
S
j of all blocks. Then, (
p
u
,
p
v
) is taken as a pair, when n
=
4, (
u
,
v
)
=
(
0
,
4
)
,
(
1,5
)
,
(
2,6
)
,
(
3,7
)
,
(
8,15
)
,
(
9,14
)
,
(
10,12
), or (
11,13
). Finally, for each pair (
p
u
,
p
v
), a watermark bit is extracted and considered to be 0 if p
u
<
p
v and 1 if p
u
>
p
v. Otherwise, no watermark bit is embedded if p
u
=
p
v.


## 3.1. Embedding Algorithm

The embedding algorithm contains four stages: halftone conversion, subimage segmentation, embedding, and relocation. They are described in the following.


### 3.1.1. Halftone Conversion

Ann
×
n dispersed dithering screen (DS) [1] is first applied to a P
×
Q grayscale image I to result in a dithering halftone image H according to (1).


### 3.1.2. Subimage Segmentation

Suppose that a watermarkw with T bits will be embedded. In the subimage segmentation stage, H is segmented into k
×
l subimages through downsampling, where k
×
l
≥
T
/
(
n
×
n
)
/
2 and each subimage has P
/
k
×
Q
/
l pixels. First, H is divided into P
/
k
n
×
Q
/
l
n blocks, each of which has k
n
×
l
n pixels. Then, each block is further divided into k
×
l subblocks, each of which has n
×
n pixels. Let A
i
,
j be the jth subblock in block i, where i
=
0,1
,
…
,
(
P
×
Q
/
k
n
×
l
n
-
1
) and j
=
0,1
,
…
,
(
k
l
-
1
), respectively. Finally, through downsampling, all jth subblocks (
A
i
,
j
,
i
=
0,1
,
…
,
(
P
×
Q
/
k
n
×
l
n
-
1
)
) are grouped into a subimage H
j. For the convenience of explanation, all H
js are arranged into an image.Figure4(a) shows an image divided into 3 × 3 blocks with P
=
Q
=
48, k
=
l
=
4, and n
=
4, each of which is further divided into 4 × 4 subblocks. Figure 4(b) shows the subimage segmentation result of Figure 4(a). Figure 4(c) shows the segmentation result of Figure 2(b) with T
=
120, k
=
4, l
=
4, and k
×
l
=
16
>
120
/
4
×
4
/
2
=
15. The rectangles in Figure 4(c) denote the 16 subimages.Figure 4
An example of subimage segmentation. (a) An image divided into 3 × 3 blocks, each of which has 4 × 4 subblocks. (b) The segmentation result of (a). (c) The segmentation result of Figure2(b).
(a)
(b)
(c)


### 3.1.3. Embedding

In the embedding stage, ann
×
n dispersed dithering screen with n
=
2
k and k
∈
N is used. The n
×
n dispersed dithering screen is first divided into 2 × 2 dispersed dithering screens. Secondly, in each 2 × 2 dispersed dithering screen, two elements with thresholds more than 128 are grouped as a pair, and the other two elements with thresholds less than 128 are grouped as a pair. Hence, we can obtain n
×
n
/
2 pairs.Thirdly, sort all values in then
×
n dispersed dithering screen and give each value an order; then each pair is represented by its corresponding order. For example, in Figure 1(b) with n
=
8, the four elements in the top-left 2 × 2 dispersed dithering screen marked by a red rectangle have thresholds 6, 238, 134, and 70. The two elements with thresholds 6 and 70 are grouped as a pair, and 134 and 238 are grouped as another pair. After sorting the values in the dispersed dithering screen in Figure 1(b), the corresponding order of each element is shown in Figure 1(d). The two pairs are represented by their corresponding orders as (
1,17
) and (
33,59
).Fourthly, letO
D
S
j be the position with order j in the dispersed dithering screen DS, where j
=
0
,
…
,
n
×
n
-
1. Figure 1(c) shows the order and position of each pixel in the 4 × 4 dispersed dithering screen shown in Figure 1(a); in this figure, O
D
S
0
=
(
2,2
), O
D
S
15
=
(
2,3
). Fifthly, each subimage H
i is divided into blocks with size n
×
n, and all pixels at position O
D
S
j of all blocks are grouped into a sub-subimage S
H
i
,
j.Sixthly, the number,p
j, of black pixels at S
H
i
,
j is counted. Then, we take (
p
u
,
p
v
) as a pair, when n
=
4, (
u
,
v
)
=
(
0
,
4
)
,
(
1,5
)
,
(
2,6
)
,
(
3,7
)
,
(
8,15
)
,
(
9,14
)
,
(
10,12
), or (
11,13
). Note that, for each of above-mentioned pair (
p
u
,
p
v
) with n
=
4, the difference, d
(
u
,
v
), of values of O
D
S
u and O
D
S
v in the dispersed dithering screen DS is not less than 32. However, for each pair (p
i
,
p
i
+
1) used by Guo et al., the difference, d
(
i
,
i
+
1
), of values of O
D
S
i and O
D
S
i
+
1 in the dispersed dithering screen DS is equal to 16. This will make each pair (
p
u
,
p
v
) used in the proposed method have larger |
p
u
-
p
v
| than |
p
i
-
p
i
+
1
| used in Guo et al.’s method. One example is given in Table 2. Table 2 shows the black pixel numbers of each pair (
p
u
,
p
v
) in the top-left subimage of Figure 4(c); the average difference of numbers of black pixels in the eight pairs is 16.75, which is greater than 5.25 in Guo et al.’s method (see Table 1). This means that the proposed method will provide higher robustness than Guo et al.’s method for the print-and-scan process.Table 2
The black pixel numbers in eight pairs of the top-left subimage in Figure4(c).
Pairs
The number of black pixels
p
u
p
v
(p
0, p
4)
0
18
(p
1, p
5)
0
32
(p
2, p
6)
10
35
(p
3, p
7)
16
44
(p
8, p
15)
53
64
(p
9, p
14)
54
64
(p
10, p
12)
58
64
(p
11, p
13)
60
64Finally, one bit is embedded into each pair(
p
u
,
p
v
). If the embedding bit is 0 and p
u
<
p
v or the embedding bit is 1 and p
u
>
p
v, nothing is done. Otherwise, in each block, the pixel at position O
D
S
u and the pixel at position O
D
S
v are swapped. Note that if p
u
=
p
v, no bit will be embedded into the pair. This kind of pairs is called equivalent black pixel pair (EBP).


### 3.1.4. Relocation

After embedding, all pixels are relocated to their original positions to form the embedded dithered imageE
H. Then E
H can be printed on a paper to form a printed embedded dithered image E
H
p. Note that the embedding capacity is k
×
l
×
(
n
×
n
)
/
2 bits.Figure5(a) shows the result of embedding 120 watermark bits into Figure 4(c). The rectangle marked in Figure 5(a) denotes the first subimage with 8 watermark bits 10101010 embedded. Figure 5(b) shows the embedded dithered image resulting from relocating Figure 5(a).Figure 5
An example of embedding algorithm. (a) The result of embedding 120 bits into Figure4(c). (b) The embedded dithered image by relocating (a).
(a)
(b)


## 3.1.1. Halftone Conversion

Ann
×
n dispersed dithering screen (DS) [1] is first applied to a P
×
Q grayscale image I to result in a dithering halftone image H according to (1).


## 3.1.2. Subimage Segmentation

Suppose that a watermarkw with T bits will be embedded. In the subimage segmentation stage, H is segmented into k
×
l subimages through downsampling, where k
×
l
≥
T
/
(
n
×
n
)
/
2 and each subimage has P
/
k
×
Q
/
l pixels. First, H is divided into P
/
k
n
×
Q
/
l
n blocks, each of which has k
n
×
l
n pixels. Then, each block is further divided into k
×
l subblocks, each of which has n
×
n pixels. Let A
i
,
j be the jth subblock in block i, where i
=
0,1
,
…
,
(
P
×
Q
/
k
n
×
l
n
-
1
) and j
=
0,1
,
…
,
(
k
l
-
1
), respectively. Finally, through downsampling, all jth subblocks (
A
i
,
j
,
i
=
0,1
,
…
,
(
P
×
Q
/
k
n
×
l
n
-
1
)
) are grouped into a subimage H
j. For the convenience of explanation, all H
js are arranged into an image.Figure4(a) shows an image divided into 3 × 3 blocks with P
=
Q
=
48, k
=
l
=
4, and n
=
4, each of which is further divided into 4 × 4 subblocks. Figure 4(b) shows the subimage segmentation result of Figure 4(a). Figure 4(c) shows the segmentation result of Figure 2(b) with T
=
120, k
=
4, l
=
4, and k
×
l
=
16
>
120
/
4
×
4
/
2
=
15. The rectangles in Figure 4(c) denote the 16 subimages.Figure 4
An example of subimage segmentation. (a) An image divided into 3 × 3 blocks, each of which has 4 × 4 subblocks. (b) The segmentation result of (a). (c) The segmentation result of Figure2(b).
(a)
(b)
(c)


## 3.1.3. Embedding

In the embedding stage, ann
×
n dispersed dithering screen with n
=
2
k and k
∈
N is used. The n
×
n dispersed dithering screen is first divided into 2 × 2 dispersed dithering screens. Secondly, in each 2 × 2 dispersed dithering screen, two elements with thresholds more than 128 are grouped as a pair, and the other two elements with thresholds less than 128 are grouped as a pair. Hence, we can obtain n
×
n
/
2 pairs.Thirdly, sort all values in then
×
n dispersed dithering screen and give each value an order; then each pair is represented by its corresponding order. For example, in Figure 1(b) with n
=
8, the four elements in the top-left 2 × 2 dispersed dithering screen marked by a red rectangle have thresholds 6, 238, 134, and 70. The two elements with thresholds 6 and 70 are grouped as a pair, and 134 and 238 are grouped as another pair. After sorting the values in the dispersed dithering screen in Figure 1(b), the corresponding order of each element is shown in Figure 1(d). The two pairs are represented by their corresponding orders as (
1,17
) and (
33,59
).Fourthly, letO
D
S
j be the position with order j in the dispersed dithering screen DS, where j
=
0
,
…
,
n
×
n
-
1. Figure 1(c) shows the order and position of each pixel in the 4 × 4 dispersed dithering screen shown in Figure 1(a); in this figure, O
D
S
0
=
(
2,2
), O
D
S
15
=
(
2,3
). Fifthly, each subimage H
i is divided into blocks with size n
×
n, and all pixels at position O
D
S
j of all blocks are grouped into a sub-subimage S
H
i
,
j.Sixthly, the number,p
j, of black pixels at S
H
i
,
j is counted. Then, we take (
p
u
,
p
v
) as a pair, when n
=
4, (
u
,
v
)
=
(
0
,
4
)
,
(
1,5
)
,
(
2,6
)
,
(
3,7
)
,
(
8,15
)
,
(
9,14
)
,
(
10,12
), or (
11,13
). Note that, for each of above-mentioned pair (
p
u
,
p
v
) with n
=
4, the difference, d
(
u
,
v
), of values of O
D
S
u and O
D
S
v in the dispersed dithering screen DS is not less than 32. However, for each pair (p
i
,
p
i
+
1) used by Guo et al., the difference, d
(
i
,
i
+
1
), of values of O
D
S
i and O
D
S
i
+
1 in the dispersed dithering screen DS is equal to 16. This will make each pair (
p
u
,
p
v
) used in the proposed method have larger |
p
u
-
p
v
| than |
p
i
-
p
i
+
1
| used in Guo et al.’s method. One example is given in Table 2. Table 2 shows the black pixel numbers of each pair (
p
u
,
p
v
) in the top-left subimage of Figure 4(c); the average difference of numbers of black pixels in the eight pairs is 16.75, which is greater than 5.25 in Guo et al.’s method (see Table 1). This means that the proposed method will provide higher robustness than Guo et al.’s method for the print-and-scan process.Table 2
The black pixel numbers in eight pairs of the top-left subimage in Figure4(c).
Pairs
The number of black pixels
p
u
p
v
(p
0, p
4)
0
18
(p
1, p
5)
0
32
(p
2, p
6)
10
35
(p
3, p
7)
16
44
(p
8, p
15)
53
64
(p
9, p
14)
54
64
(p
10, p
12)
58
64
(p
11, p
13)
60
64Finally, one bit is embedded into each pair(
p
u
,
p
v
). If the embedding bit is 0 and p
u
<
p
v or the embedding bit is 1 and p
u
>
p
v, nothing is done. Otherwise, in each block, the pixel at position O
D
S
u and the pixel at position O
D
S
v are swapped. Note that if p
u
=
p
v, no bit will be embedded into the pair. This kind of pairs is called equivalent black pixel pair (EBP).


## 3.1.4. Relocation

After embedding, all pixels are relocated to their original positions to form the embedded dithered imageE
H. Then E
H can be printed on a paper to form a printed embedded dithered image E
H
p. Note that the embedding capacity is k
×
l
×
(
n
×
n
)
/
2 bits.Figure5(a) shows the result of embedding 120 watermark bits into Figure 4(c). The rectangle marked in Figure 5(a) denotes the first subimage with 8 watermark bits 10101010 embedded. Figure 5(b) shows the embedded dithered image resulting from relocating Figure 5(a).Figure 5
An example of embedding algorithm. (a) The result of embedding 120 bits into Figure4(c). (b) The embedded dithered image by relocating (a).
(a)
(b)


## 3.2. Recovering Algorithm for Print-and-Scan Process

When we receive the paper with the printed embedded dithered imageE
H
p, a scanner is used to capture E
H
p and produce a scanned image E
H
s. The scanned image E
H
s usually has geometrical distortion and dot gain effect due to the scanner and printer properties. Dot gain is a phenomenon in printing which causes the size of a dot to be increased or decreased slightly. Here, we adopt the recovering algorithm proposed by Guo et al. [12] to get the embedded dithered image E
H
′.


## 3.3. Watermark Extraction Algorithm

The watermark extraction contains two steps: subimage segmentation and extraction. To extract the embedded watermark,E
H
′ will be segmented into several subimages through downsampling mentioned in the embedding algorithm. For each subimage H
i
′, we divide it into blocks with size n
×
n and then count the number, p
j, of black pixels at position O
D
S
j of all blocks. Then, (
p
u
,
p
v
) is taken as a pair, when n
=
4, (
u
,
v
)
=
(
0
,
4
)
,
(
1,5
)
,
(
2,6
)
,
(
3,7
)
,
(
8,15
)
,
(
9,14
)
,
(
10,12
), or (
11,13
). Finally, for each pair (
p
u
,
p
v
), a watermark bit is extracted and considered to be 0 if p
u
<
p
v and 1 if p
u
>
p
v. Otherwise, no watermark bit is embedded if p
u
=
p
v.


## 4. Experimental Results and Comparisons

Eight 512 × 512 test images used in [12, 15] are shown in Figure 6 and also used in our experiments. Figure 7 shows the visual quality comparison of different methods when n
=
4. The regions marked by cycles in Figures 7(e)–7(h) are high-frequency ones of Figures 7(a)–7(d), respectively. Compared to Figure 7(e), we can see that Figure 7(h) is similar to Figure 7(e), but the boundary area in Figure 7(f) is smeared and unclear. This means that the proposed method provides higher visual quality in high-frequency areas than Guo et al.’s method [12]. Besides, we can see that Figure 7(c) has salt-and-pepper noises. Hence, the proposed method provides better visual quality than Hagit’s method [13].Figure 6
Thumbnail of eight test images. (a) Lena, Mandrill, Earth, and Tiffany. (b) Shuttle, Peppers, Milk, and Lake.
(a)
(b)Figure 7
Visual quality comparison with 128 embedding bits whenn
=
4. (a) Original dithered image. (b) Embedded dithered image using Guo et al.’s method [12]. (c) Embedded dithered image using Hagit’s method [13]. (d) Embedded dithered image using the proposed method. (e) Enlarged partial image of (a). (f) Enlarged partial image of (b). (g) Enlarged partial image of (c). (h) Enlarged partial image of (d).
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)Figure8 shows the visual quality comparison of different methods when n
=
8. Compared to Figure 8(e), we can see that Figure 8(h) is similar to Figure 8(e), but the boundary area in Figure 8(f) is smeared and unclear. Compared to Figures 7(f) and 8(f), we can see that Figure 8(f) is more smeared and unclear than Figure 7(f). Besides, we can see that Figure 8(c) has more salt-and-pepper noises. Hence, the proposed method provides better visual quality than Hagit’s method [13].Figure 8
Visual quality comparison with 128 embedding bits whenn
=
8. (a) Original dithered image. (b) Embedded dithered image using Guo et al.’s method [12]. (c) Embedded dithered image using Hagit’s method [13]. (d) Embedded dithered image using the proposed method. (e) Enlarged partial image of (a). (f) Enlarged partial image of (b). (g) Enlarged partial image of (c). (h) Enlarged partial image of (d).
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)Next, two objective methods [7, 14] are used to measure the halftone image quality. One is the Pei-Guo-PSNR proposed by Pei and Guo [7]; it is adopted to measure the quality of a halftone image and is evaluated as follows:(2)
Pei-Guo-PSNR
=
P
×
Q
∑
i
=
1
P
∑
j
=
1
Q
x
i
,
j
-
∑
m
,
n
∈
R
∑
w
m
,
n
b
i
+
m
,
j
+
n
2
,where w
m
,
n is an r
×
r least-mean square filter and can be obtained by a training process [7], R
=
m
,
n
∣
-
r
-
1
/
2
≤
m
,
n
≤
r
-
1
/
2, x is the original grayscale image, and b is the corresponding halftone image. Here, a 7 × 7 least-mean square (LMS) filter [7] (see Figure 9) is adopted to measure the quality of halftone images. Table 3 shows the quality comparisons of various methods using Pei-Guo-PSNR; a random bit stream is adopted as a watermark. From this table, we can see that the proposed methods and Guo et al.’s method provide similar qualities when n
=
4. But the proposed method provides better qualities than Hagit’s method. When n
=
8, the proposed method provides better qualities than other methods. Because Pei-Guo-PSNR is basically the PSNR of the original grayscale image and a low-pass version of the halftone image, it measures effectively the distortions to the low-frequency image content [14]. But Pei-Guo-PSNR is improper for measuring the high-frequency image content.Table 3
Quality comparisons of various algorithms using Pei-Guo-PSNR [12].
Algorithm
Original
Hagit’s method [13]
Guo et al.’s method [12]
Proposed method
Average Pei-Guo-PSNR
Screen size
n
=
4
n
=
8
n
=
4
n
=
8
n
=
4
n
=
8
n
=
4
n
=
8
Embedded bits
0
31.56
31.19
N/A
N/A
N/A
N/A
N/A
N/A
32
N/A
N/A
26.83
27.55
29.21
26.29
28.65
29.14
128
N/A
N/A
26.80
27.52
29.17
26.55
28.58
28.82
512
N/A
N/A
26.87
27.38
28.91
26.31
28.49
28.92Figure 9
Coefficients of7
×
7 LMS filter.Fu and Au [14] proposed another measure to treat the above-mentioned disadvantage. Let x be the original grayscale image; let E
H be the embedded halftone image. Fu and Au [14] define two special classes of elements in E
H as follows:Class 1. Black pixel in bright region (
E
H
(
m
,
n
)
=
0
,
x
(
m
,
n
)
≥
128
).
Class 2. White pixel in dark region (
E
H
(
m
,
n
)
=
255
,
x
(
m
,
n
)
≤
127
).Based on these two classes, Fu and Au [14] define four scores as follows: (3)
S
1
=
∑
i
=
0
4
N
i
,
S
2
=
∑
i
=
0
4
i
+
1
N
i
,
S
3
=
S
2
S
1
,
S
4
=
∑
i
=
2
4
N
i
,where N
i is the total number of Class 1 and Class 2 elements in E
H having i neighbors with the same pixel values in the 4-neighborhood.  N
0 corresponds to the number of isolated Class 1 or Class 2 elements. S
3 and S
4 can be used to measure the visual disturbing of “salt-and-pepper” clusters formed by neighboring pixels [14]. Thus, we adopt scores S
3 and S
4 to measure the quality of a halftone image. Algorithms with smaller scores of S
3 and S
4 are better. Table 4 shows the quality comparisons of various methods based on scores S
3 and S
4. From this table, we can see that the proposed method has smaller scores of S
3 and S
4; thus, it is better than other methods.Table 4
Quality comparisons of various algorithms based on scoresS
3 and S
4 [14].
Algorithm
Hagit’s method [13]
Guo et al.’s method [12]
Proposed method
AverageS
3
Screen size
n
=
4
n
=
8
n
=
4
n
=
8
n
=
4
n
=
8
Embedded bits
32
2.49
2.23
1.61
1.69
1.61
1.18
128
2.64
2.32
1.67
1.52
1.67
1.18
512
2.58
2.32
1.68
1.61
1.68
1.18
AverageS
4
Screen size
n
=
4
n
=
8
n
=
4
n
=
8
n
=
4
n
=
8
Embedded bits
32
17459
11164
1372
2583
829
899
128
17528
11738
1503
1833
824
815
512
17328
11382
1660
2240
799
854From the above experiments, we can see that the image quality of Guo et al.’s method becomes worse when the dispersed dithering screen size increases. The reason is that if the dispersed dithering screen size increases, the NIP problem in Guo et al.’s method becomes more serious. Many black pixels will be added to eliminate these NIPs in Guo et al.’s method. Hence, the number of black pixels in some subimages will be changed. In addition, the pixel swapping distance of Guo et al.’s method also increases if the dispersed dithering screen size increases. Hence, the boundary of Guo et al.’s method will become more smeared and unclear and its image quality is degraded. However, the proposed method does not have this problem. Hence, the boundary is still clear when the dispersed dithering screen size increases.Since Feng et al.’s method [17] can only embed P
/
8
×
Q
/
8 watermark bits, we compare the qualities of the embedded halftone images using Feng et al.’s method [17] and others only for P
/
8
×
Q
/
8 watermark bits embedded. Table 5 shows the comparison results for the 512 × 512 halftone image shown in Figure 8(a). From this table, we can see that the proposed method provides better qualities than other methods.Table 5
Quality comparisons of various algorithms with 64 × 64 watermark bits embedded in Figure8(a).
Algorithm
Guo et al.’s method [12]
Proposed method
Feng et al.’s method [17]
Pei-Guo-PSNR
28.68
30.17
15.15
S
3
1.43
1.07
3.86
S
4
1847
201
54592To justify the selection of(
u
,
v
) pair, we use three different kinds of selection for (
u
,
v
) pairs. The first selection is used by Guo et al.’s method with v
-
u
=
1; all (
u
,
v
) pairs are (
0,1
), (
2,3
), (
4,5
), (
6,7
), (
8,9
), (
10,11
), (
12,13
), and (
14,15
). The second selection follows the rule 2
≤
v
-
u
≤
5; all (
u
,
v
) pairs are (
0,4
), (
1,5
), (
2,6
), (
3,7
), (
8,15
), (
9,14
), (
10,12
), and (
11,13
). The third selection follows the rule 6
≤
v
-
u
≤
11; all (
u
,
v
) pairs are (
0,8
), (
1,9
), (
2,10
), (
3,11
), (
4,15
), (
5,14
), (
6,12
), and (
7,13
). From the dispersed dithering screens shown in Figure 1, we can see that when (
v
-
u
) is larger, T
v
-
T
u is larger; this will make |
p
u
-
p
v
| larger. When |
p
u
-
p
v
| is larger, then it can provide a higher robustness for the print-and-scan process. But the quality will be degraded. Thus, the second selection will provide higher robustness and better quality. To prove this point, we have done some experiments based on these three kinds of selection by embedding 128 watermark bits into a 512 × 512 image.Table6 shows quality comparisons of three different kinds of pair selections using Pei-Guo-PSNR, scores S
3 and S
4. From this table, we can see that these pair selections provide similar qualities in Pei-Guo-PSNR. But, in S
3 and S
4, the second selection used in the proposed method has the best result, and the third selection has the worst result. Table 7 shows the black pixel numbers in eight pairs of the top-left subimage for various pair selections. The average difference on numbers of black pixels in the eight pairs for the second selection used in the proposed method is 223.5, the third selection is 238.5, and the first selection used in Guo et al.’s method is 62.75. This means that Guo et al.’s method provides less robustness than the other pair selections, and the third selection will provide similar robustness to the second pair selection for the print-and-scan process. However, the image quality using the third pair selection is worse than those of two pair selections. Therefore, under the consideration of image quality and robustness, the second selection used in the proposed method is better.Table 6
Quality comparisons of three different kinds of pair selections using Pei-Guo-PSNR [12] and scores S
3 and S
4 [14].
Selection
The 1st selection used in Guo et al. [12] with v
-
u
=
1
The 2nd selection used in the proposed method with2
≤
v
-
u
≤
5
The 3rd selection with6
≤
v
-
u
≤
11
Images
Quality
Pei-Guo-PSNR
S
3
S
4
Pei-Guo-PSNR
S
3
S
4
Pei-Guo-PSNR
S
3
S
4
Lena
30.78
1.37
480
29.24
1.06
204
28.26
2.26
12967
Mandrill
27.30
2.24
3201
27.32
1.59
2758
26.54
2.36
16866
Earth
27.06
2.07
2772
28.17
1.28
1233
28.45
2.09
6841
Tiffany
31.06
1.12
189
29.06
1.03
159
28.82
1.70
1981
Shuttle
27.66
1.90
2134
28.08
1.20
871
28.12
2.18
10062
Peppers
30.34
1.46
755
29.00
1.08
381
28.25
2.18
10525
Milk
31.04
1.32
529
29.63
1.02
129
28.65
2.17
10080
Lake
28.15
1.88
1967
28.15
1.13
857
28.34
1.95
5753
Average
29.17
1.67
1503.4
28.58
1.17
824
28.18
2.11
9384.4Table 7
The black pixel numbers of the eight pairs in the top-left subimage for different kinds of selections.
Selection
The 1st selection used in Guo et al. [12] with v
-
u
=
1
The 2nd selection used in the proposed method with2
≤
v
-
u
≤
5
The 3rd selection with6
≤
v
-
u
≤
11
Pairs (u, v)
The number of black pixels
Pairs (u, v)
The number of black pixels
Pairs (u, v)
The number of black pixels
p
u
p
v
p
u
p
v
p
u
p
v
(0, 1)
322
352
(0, 4)
389
641
(0, 8)
389
734
(2, 3)
320
354
(1, 5)
391
725
(1, 9)
391
826
(4, 5)
386
540
(2, 6)
364
757
(2, 10)
364
884
(6, 7)
545
547
(3, 7)
421
712
(3, 11)
421
873
(8, 9)
611
758
(8, 15)
734
672
(4, 15)
641
672
(10, 11)
801
668
(9, 14)
826
675
(5, 14)
725
675
(12, 13)
672
674
(10, 12)
884
711
(6, 12)
757
711
(14, 15)
672
672
(11, 13)
873
741
(7, 13)
712
741Furthermore, in the experiments of Guo et al. [12], based on a 4 × 4 dispersed dithering screen, the average percentages of NIPs with 8, 32, 128, and 512 bits embedded into each of eight test images shown in Figure 6 are 12.5%, 15.62%, 27.32%, and 45%, respectively. Guo et al. modify the number of black pixels in these NIPs before embedding watermark. This may lower visual quality. On the contrary, in the proposed method, we do not modify any pair before data embedding.As to the embedding capacity, since the data embedding depends on the difference of black pixel numbers of each pair, if the difference is zero, the pair cannot be used for data embedding in the proposed method. This will reduce the embedding capacity. Fortunately, from our experimental results, we found that the situation rarely appears in most images. Table8 shows the numbers of equivalent black pixel pairs (EBP) in eight dithered test images. From this table, we can see that most images have zero EBP, except “Tiffany” image. The reason is that most pixels in “Tiffany” image have gray values >90, and the gray values of pixels in a local area are nearly constant. For example, for pair (
p
1
,
p
5
), the corresponding values in DS are (
24,88
) (see Figure 1); thus, each pixel in S
H
i
,
1 and S
H
i
,
5 for each i will be a white point. This will make (
p
1
,
p
5
)
=
(
0,0
) and make it an EBP.Table 8
Numbers of equivalent black pixel pairs in eight test images using the proposed method.
Number of subimages
1
4
16
64
128
256
Total number of pairs
8
32
128
512
1024
2048
Number of EBPs
Lena
0
0
0
0
0
0
Mandrill
0
0
0
0
0
0
Earth
0
0
0
0
0
0
Tiffany
0
2
22
146
373
830
Shuttle
0
0
0
0
0
0
Peppers
0
0
0
0
0
0
Milk
0
0
0
0
0
0
Lake
0
0
0
0
0
0In the next experiment, we demonstrate the robustness of the proposed method and Guo et al.’s method by cropping and tampering attacks. To measure the integrity of the extracted watermark, the correct decoding rate (CDR) is defined as follows:(4)
CDR
=
Lev_ Dist
w
,
w
′
T
×
100
%
,where Lev_Dist
(
), w, and w
′ denote the Levenshtein distance [22], original watermark, and extracted watermark, respectively. The Levenshtein distance is a string metric for estimating the least number of edit operations that is necessary to modify one string to obtain another string. In Figures 10 and 11, a 32 × 32 watermark shown in Figure 10(a) is embedded into the halftone image in Figure 11(b) using the proposed method and Guo et al.’s method, respectively, and the results are shown in Figures 10(b) and 11(a), respectively. Figures 10(c) and 11(b) show the embedded dithered images cropped by 1/4 portion. Figures 10(d) and 11(c) show the embedded dithered images tampered with several words. Note that when the number of embedding bits >8, the dithered image is first divided into t subimages, and the watermark bits are also divided into t parts. Each part is embedded into one subimage. The resulting subimages using the proposed method and Guo et al.’s method are shown in Figures 10(e), 10(f), 11(d), and 11(e). From Figure 10(e), we can see that each subimage using the proposed method is also cropped by 1/4 portion; the reason is that each subimage is obtained by block downsampling (see Figure 4). The cropping will make 1/4 portion of all pixel pairs (
u
,
v
) lost. Since a watermark bit is embedded through the sign of (
p
u
-
p
v
), 1/4 portion of pairs (
u
,
v
) lost will not affect the sign of (
p
u
-
p
v
). Thus, the watermark can be extracted correctly (see Figure 10(g)). Figure 10(h) shows the watermark extracted from Figure 10(d) and it can also be extracted correctly. On the contrary, in Figure 11(d), we can see that some subimages using Guo et al.’s method are totally removed; this will make the watermark parts embedded in these subimages lost (see Figure 11(f)). Figures 11(f) and 11(g) show the watermarks extracted from Figures 11(b) and 11(c), respectively. Table 9 shows the average correct decoding rates of cropping 1/3, 1/4, and 1/2 portions, respectively. Note that in this experiment, each of the eight images is cropped at three different locations for each cropping portion; thus there are 72 (3 × 3 × 8) cropped images. From this table, we can see that the proposed method is more robust than Guo et al.’s method and Feng et al.’s method [17].Table 9
Average correct decoding rates of different cropping size.
Average correct decoding rates
Guo et al.’s method [12]
Proposed method
Feng et al.’s method [17]
Cropping size
Watermark size
32 × 32
64 × 64
32 × 32
64 × 64
64 × 64
1/2
50.00%
50.00%
93.98%
91.87%
67.20%
1/3
66.50%
66.55%
94.20%
94.77%
78.25%
1/4
75.00%
75.00%
95.24%
96.05%
83.64%Figure 10
The robustness of the proposed method. (a) A 32 × 32 watermark. (b) Embedded dithered image using the proposed method. (c) Embedded dithered image cropped by 1/4 portion. (d) Embedded dithered image with tampering. (e) Downsampled subimages of (c). (f) Downsampled subimages of (d). (g) The watermark extracted from (c). (h) The watermark extracted from (d).
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)Figure 11
The robustness of Guo et al.’s method [12]. (a) Embedded dithered image using Guo et al.’s method. (b) Embedded dithered image cropped by 1/4 portion. (c) Embedded dithered image with tampering. (d) The result of applying bit-interleaving to each subimage of (b). (e) The result of applying bit-interleaving to each subimage of (c). (f) The watermark extracted from (b). (g) The watermark extracted from (c).
(a)
(b)
(c)
(d)
(e)
(f)
(g)To measure the robustness of the proposed method and Guo et al.’s method [12] under print-and-scan attack, for each of eight test images, we first embed 8, 32, 128, and 512 bits into its corresponding halftone image; then each embedded halftone image is printed at 150 dpi. After printing, each printed image is scanned at 150, 450, and 750 dpi, respectively, and then the embedded watermark from each scanned image is extracted. Table 10 shows the average correct decoding rate with eight test images as shown in Figure 6. From this table, we can see that the average correct decoding rates of the proposed method are higher than those of Guo et al.’s method. This means that the proposed method provides more robustness than Guo et al.’s method under print-and-scan attack.Table 10
Average correct decoding rates of all scanned embedded images with different scanning resolutions.
Algorithm
Guo et al.’s method [12]
Proposed method
Average correct decoding rate
Scanning resolution
150
450
750
150
450
750
Embedded bits
32
65%
72%
70%
77%
85%
84%
128
60%
70%
75%
78%
82%
86%
512
57%
65%
72%
78%
83%
86%


## 5. Conclusions

In this paper, a robust watermarking method has been proposed for dithered halftone images. Before embedding, a dithered halftone image is divided into subimages through downsampling; this step provides robustness to cropping and tampering. In the embedding step, each pair(
p
u
,
p
v
) is taken to embed a watermark bit with (
u
,
v
)
=
(
0
,
4
)
,
(
1,5
)
,
(
2,6
)
,
(
3,7
)
,
(
8,15
)
,
(
9,14
)
,
(
10,12
), or (
11,13
); however, in Guo et al.’s method, the pair (
p
i
,
p
i
+
1
) is taken to embed a watermark bit. Since the average of |
p
u
-
p
v
| is larger than the average of |
p
i
-
p
i
+
1
|, this makes the proposed method provide higher correct decoding rate than Guo et al.’s method after print-and-scan process. Experimental results show that the proposed method actually provides higher robustness than Guo et al.’s method in cropping, tampering, and print-and-scan process. In addition, experimental results also show that the proposed method provides higher visual quality in the high-frequency areas than Guo et al.’s method.



---

*Source: 4901609-2016-05-30.xml*