High Watermarking Capacity Based on Spatial Domain Technique

INTRODUCTION

Watermarking is a method of embedding information into digital data, the data into which the watermark is to be embedded is usually referred to as the host data. The information is embedded into the host data by performing alterations to the content of the host data. The embedding is done in such a way that the host and watermark object are indistinguishable (Bender et al., 1996).

The use of cryptography in communications makes it obvious to an intruder that the communication is secret because of the encryption used. The digital watermarking problem however requires that the very existence of communication (i.e., the watermark itself) is kept secret. This can be achieved by embedding the watermark in the media imperceptibly and detecting it when required. Such a digital watermark may carry any information depending on the application (Chen et al., 1999). Using watermarking as a viable form of communication has been propelled largely by the growth of the Internet. The Internet offers an opportunity to exchange large amounts of digital information over great distances. The prevalence of media such as audio, video and images on the Internet provides an ideal channel for watermarking communication.

The human visual system HVS is insensitive to the value change in these areas. Thus, we can use these areas to embed messages. Generally speaking, the more significant bit-plane the noise area appears in, the larger variation of grey values among the neighbouring pixels there will be and then more bits could be used to embed messages. So, the first step is based on the grey value variation of neighbouring pixels to compute the number of embedding bits for each pixel (Jain and Uludag, 2002).

Watermarking capacity refers to the amount of information we are able to insert into the image. Low signal to noise ratio SNR is a phenomenon of watermarking channels which severely limits the capacity. For watermarking image, high embedding capacity may be needed (Zaidan et al., 2010). The challenge is to embed as much information as possible while staying compatible with the image noise model. In general, increasing the capacity will make the watermark more obtrusive in viewing. In addition, the watermarking system is more robust when the watermark signal power rises (Barni et al., 1999). Under the present day scenario a rough estimate of low, medium and high payload, particularly for images, is shown in Table 1.

Although many watermarking techniques have been proposed by various researchers the specific requirements of each watermarking technique vary with the application. Least significant bit LSB technique is one of the earlier techniques of watermarking. Many studies used this technique to develop different watermarking models, recently (Zeki and Manaf, 2009) improved it to new technique called intermediate significant bit ISB. Further improvement has been done to use ISB technique within a block of pixels together (Zeki and Manaf, 2011).

Table 1:	Payload categorization based on message size (Shelby, 2004)

Wu-Tsai’s method (Winkler et al., 2002) inserts the secret data into a grey-valued host images by pixel-value differencing PVD. First, a grey-valued host image is partitioned into non-overlapping blocks of two consecutive pixels, say p_i and p_i+1. From each block we can obtain a difference value d_i by subtracting p_i+1 from p_i. All possible difference absolute values of d_i range from 0 to 255. if d_i≈0, we can consider pixels p_i and p_i+1 locate within the smooth area. Otherwise, if d_i≈255, d_i is located on the edged area. Wu-Tsai’s scheme hid more secret data into edged areas than smooth areas, in order to maintain the good quality of the watermarked image (Winkler et al., 2002).

Yeuan and Ling developed new method to improve the capacity of the watermarking embedding (Jain and Uludag, 2002). First, for each pixel, the capacity evaluation component uses the grey-scale variation of neighbouring pixels and its intensity to evaluate its embedding capacity. Notice that the local characteristics should not be changed after embedding message; then the same characteristics can be used to evaluate the embedded capacity in the extracting module. Then, the minimum-error replacement component finds a replacing grey scale.

However, a loophole exists in the PVD method. Unusual steps in the histogram of pixel differences reveal the presence of a secret message. An analyst can even estimate the length of the hidden bits from the histogram. Zhang and Wang (2004) proposed a modified scheme to enhance security and avoid the occurrence of the above-mentioned steps in the pixel difference histogram, while preserving the advantage of the low visual distortion of the PVD. However, using only two blocks to make prediction may result in a highly distorted block, the two-sided, three-sided and four-sided side match methods are employed, as shown in Fig. 2. In another words, this method provides a large embedding capacity with little perceptual distortion (Chang and Tseng, 2004).

Recently many studies tried to improve the capacity of data embedding such as: Hmood et al. (2010), Qi et al. (2010) and Ahmed et al. (2010). The aim of this study is to develop a digital watermarking model which can find out the possibility to embed high amount of data in an image without degrading the quality of watermarked image.

THE PROPOSED METHOD

There are two criteria opposing each other: Trying to embed the maximum amount of data and keeping minimum amount of distortion so that the difference in picture with and without watermark data is not detected by naked eyes. In this approach, analysis of the original host image will be made in order to classify the regions of the image. The second step is the selection of the sequence of watermark data which will be chosen to embed data within the original image. The embedding process will use a key for embedding data. The same key will be used for restoring of embedded data. Attempts for increasing the amount of embedded data and then evaluation of quality of picture noise and noise recognition by naked eye has to be made.

Host image classification: Six host images were used in this study, as shown in Fig. 1. Each host image contains 256x256 pixels. The host images are the standard images for watermarking and they were downloaded from the internet. They can be found in many websites, for example the Greyscale Standard Images (http://www.dip.ee.uct.ac.za/imageproc/stdimages/greyscale/). The names of these host images are Peppers, Lake, Airplane, Milk drop, Camera man and boat, respectively.

The host images will be partitioned into non-overlapping blocks; each block contains n x m pixels. Consider a block of 3x3. After partitioning the image into blocks and presenting each pixel as decimal (0:255), three pixels from each block will receive special treatment. The first pixel is the maximum pixel value P_max, the second pixel is the minimum pixel value P_min and the third pixel P_mid is the furthest point from P_max and P_min. The embedding module will be applied to each block from left to right and from top to bottom in the image sequentially and for each block (9 pixels, 3x3), after finding P_max, P_min and P_mid. The other 6 pixels P₁, P₂, …. P₆, will be addressed from left to right and from top to bottom in an image sequentially as shown below in Fig. 2.

Figure 2 assumed that P_max in (2, 1) and P_min in (1, 2) then P_mid will be in (3, 3). The furthest point P_mid will be found according to the distance from the two pixels (P_max and P_min), i.e. if P_max in (1, 1) and P_min in (3, 1) then P_mid will be in (2, 3) and so on. P_mid coordinates could be found also by a suitable look up table.

Embedding stages: We consider the watermark text message as a long bit stream after presenting watermark as ASCII code, we want to embed every bit in the bit stream into the blocks of the host image. The number of bits t which can be embedded in each block is decided by the suitability embedding block and from pixel to another pixel. The sequence of watermark data shall be carefully selected and inherited into the key which will be inherited into the program used for recovering the embedded watermark later. The first step for embedding information is modifying the maximum point P_max to P’_max and modifying the P_min to P’_min based on range table which is design by user.

Fig. 1:	The greyscale host image, with 256x256 pixels each

Fig. 2:	Addressing the 9 pixels

Notice that the new P’_max and P’_min should carry some characteristics which should not be changed after embedding message; then the same characteristics will be used to evaluate the embedded capacity in the extracting module.

The length of the range is L = 2ⁿ, n is from 0 to 8 (there are 8 bits per pixel for gray images). In this study n = 4 (up to 4 bits) so L = 16, the number of ranges N = 256/L = 16 ranges. Assume that K is from 0 to N-1, P’_max will be the lowest (KxL+15) which is greater than P_max. While P’_min will be the highest (KxL) which is less than P_min. P’_max will be one from this list: [15, 31, 47, 63, 79, 95, 111, 127, 143, 159, 175, 191, 207, 223, 239 and 255]. While P'_min will be one from this list: [0, 16, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224 and 240]. Notice that P’_max remains the maximum pixel value and P’_min remains the minimum pixel value.

The embedding process idea is to pass an imaginary plane in the three pointsP_max, P_min and P_mid. Then the plane constants A, B and C will be calculated, as shown in Eq. 1. By substituting x and y for each of the remaining 6 points, z for each of them can be calculated where, z is the point on the linear plane:

(1)

The idea of using the imaginary plane is to make the watermarked image more close to original image and embedding more data into edge areas because the Human Visual System (HVS) is less sensitive to distortions around edges and in textured areas than in smooth areas. This effect is called spatial masking and can also be exploited for watermarking by increasing the watermark energy locally in these masked image areas because the human eyes cannot detect the noise in these areas (Winkler et al., 2002; Wu, 2001; Wu and Tsai, 2003).

In the next step we will find z₀ which is the maximum value that can be embedded in each pixel, z₀ is the distance from z to the nearest edge either P_min or P_max as shown in Eq. 2:

(2)

For each pixel we will find the number of bits, b that can be embedded as shown in Eq. 3. The sequence of watermark data will be divided into groups of size b. Each group w is presented by decimal value t which can be calculated by Eq. 4:

(3)

(4)

For embedding process, if P_i is grater than z, the P’_i will be z + t, while if P_i is smaller than z, P’_i will be z-t as shown in Eq. 5. This step is important to decrease the noise or deviation from the original picture values.

Fig. 3:	Embedding steps of the proposed method

(5)

Further, embedded data into P_max and P_min as described above can be considered b up to 4 bits then t will be found as previously. New P’_max and P’_min will be calculated as shown in Eq. 6 and 7, respectively. By this step eight pixels from nine have been used for embedding:

(6)

(7)

Embedding steps can be illustrated in Fig. 3. While Fig. 4 shows detailed example for embedding text into host image by proposed method.

During the extraction stage the three critical pixels (P_max, P_min and P_mid) must be found first, then modifying P_max to the highest (KxL+15) which is less than P_max and modifying the P_min to the lowest (KxL) which is grater than P_min, as in step 2 and 3, then finding z, z₀ and b (the number of bits have been embedded), as steps 3, 4 and 5. Finding t by calculating the difference between P_i and z, then presenting t by binary code and insert it in b number of digits to find w and then collecting each 7 bits together and presenting these groups by decimal and then by characters as ASCI code.

Fig. 4:	Example for embedding text into host image by proposed method

Table 2:	The Capacity and PSNR values for each image using the proposed method

Table 3:	Comparison between embedding capacities

RESULTS AND ANALYSIS

The embedding process has to be applied to all the blocks, i.e., from right to left and from top to bottom. Similarly, a random text message has also been used to embed into the host images. The capacity of embedding = (the number of bytes of watermarked data/number of bytes of the host image)x100% from the host image; the watermarked images after embedding within all blocks of selected host images. Table 2 shows the capacity of the embedded data into all images and the PSNR value for each image.

The above shows that the total capacity is considered very high embedding capacity because the total capacity ranges between 22-26%. The values of the PSNR are almost around 30db range in most cases.

To compare the results of the embedding capacity for the different methods with some other methods, Table 3 shows the comparison table of embedding capacity.

The comparison of the different methods reveals that the proposed method can be considered as one of the highest embedding capacity methods.