Abstract: For many applications, a certain portion of an image is more important than others. Especially, for object-oriented images, regions that cover the main object are of major concern to image owner. In this study, we proposed a high capacity novel digital color image watermarking scheme in wavelet domain based on region splitting. Regions of host image where watermark bits will be inserted are selected by quad tree decomposition of the host image. Quad tree decomposition splits an image into regions such that large regions are formed when the intensities are uniform and small regions are formed when the intensities are non-uniform. Small regions represent the presence of critical information of the image and hence if we insert watermark in those region it will be impossible to the attacker to delete the watermark without decreasing image quality significantly. In receiver side the detected watermark from those regions can be used for ownership verification. We propose to embed watermark bit in wavelet domain by manipulating the wavelet coefficients of 4x4 blocks which are find by Quad tree decomposition. We only use blue channel of color image for watermark embedding, as blue channel is less sensitive to Human Visual System (HVS) and makes the scheme more imperceptible. Experimental result shows that a visual recognizable watermark is embedded in the most significant part of the image. Further, it shows that the proposed scheme is imperceptible and also robust to common image processing operations.
INTRODUCTION
The popularity of Internet has greatly facilitated the distribution of multimedia data such as images, videos and music through the Internet. However, due to lack of security, Vendors may be unwilling to distribute data over the Internet because it can be easily duplicated and distributed without the owners consent. In the early days, encryption and control access techniques were used to protect the ownership of media. However, current technology does not protect their copy right properly. Digital watermarking, the art of hiding information in a robust and invisible manner, has been investigated as a complimentary technology. We call a watermarking scheme non-blind if original host image is desired to extract the watermark and blind when original host image is not needed for watermark detection. Our scheme is a non-blind technique and can help image registration when some geometrical manipulation like scaling and rotation is applied on watermarked host image.
There are some desirable characteristics of effective watermarking techniques, including imperceptibility, robustness and high capacity. Imperceptibility means original and watermarked image must looks like the same. It is desirable to embed the watermark in a discreet, unobtrusive manner so that the watermark is imperceptible under casual observation. Robustness is the resistance of watermark against common image processing operation such as lossy compression, filtering, scaling and cropping. Capacity means number of watermark bit can be inserted in to the host image. Obviously, it is desirable to have an imperceptible, robust, high capacity watermarking technique.
Lots of works have been done in image watermarking. We can divide all watermarking scheme into two classes depending on the domain of watermark insertion: frequency and spatial domain (Mukherjee et al., 2004; Hongjun and Na, 2005; Chu, 2003) watermarking method. Watermarking in the transform domain is commonly performed by modulating the Fast Fourier Transformation (FFT), Discrete Cosine Transformation (DCT), or Discrete Wavelet Transformation (DWT) domain coefficients according to watermark.
As Watermarking in the DWT domain has several advantages over FFT and DCT (Langelaar et al., 2000; Potdar et al., 2005), so our scheme use DWT domain for watermark bit insertion. Some related study in wavelet domain is summarized here.
Voloshynovskiy et al. (2001) propose an efficient wavelet domain watermarking method that deals with Random Bending Attack (RBA). The message (m) is encoded using some Error Correcting Code (ECC), encrypted, mixed with the reference watermark and allotted into a block, depending on the secret key (k). This block is then up sampled, flipped and resulting macro block is tiled up to the image size. Watermark is extracted using Maximal Like hood (ML) estimator.
Aboofazeli et al. (2004) propose a watermarking technique for ownership verification. They insert a visually recognizable watermark into the wavelet coefficients corresponding to the points located in a neighborhood that have maximum entropy. They claim that as maximum entropy areas can survive a variety of attacks and hence be used as reference points for watermark embedding.
Hongjun and Na (2005) propose a non-blind digital image watermarking algorithm based on multi-resolution wavelet analysis. They suggest various reasons why High-Low (HL) region is better for watermark embedding and why most of the DCT based watermarking algorithm is replace by wavelet based algorithm. The algorithm keeps the quality of the image as well as robustness against common image processing operations.
Lu et al. (2005) propose, a novel digital image watermarking scheme based on chaotic map. A two dimensional chaotic Baker map is used to encrypt the host image and spread its spectrum, then watermark is embedded in the High-High (HH) sub band of DWT. They directly apply Spread spectrum technique in the host image before watermark embedding and use two keys for chaotic Baker map, one is to encrypt the image and the other is for the watermark. They claim that use of chaotic Baker map makes the scheme secure.
Nallaperumal et al. (2006) propose a non-blind, secure and robust digital image watermarking techniques for authentication. They insert a visual recognizable logo into the wavelet coefficients that have maximum entropy and content based watermark information into middle frequency pairs of the first scale coefficients. This technique provides two levels of protection while maintaining the image quality. It is seen that the proposed method is able to identify malicious changes made on the image, while very insensitive, to common image processing.
All the previous scheme either fail to select the most significant portion of the image automatically or fail to insert high capacity watermark in to the host image or both. But for many applications, a certain portion of an image is more important than others. Especially, for object-oriented images, regions that cover the main object are of major concern to image owner. For example, in a picture with a person appearing at the centre, the image observer usually cares more about the person than the background of the picture. It is desirable to embed the watermarks into the most significant part of the image to give the better protection. So open paths still remain in image watermarking.
In this study, we propose a novel approach to region specific high capacity watermarking scheme for color image in the wavelet domain. The watermark is embedded into the selected area of host image which is most important. Before actually embedding the watermark information, we encode the watermark signal with soft convolution coding and select embedding regions by quad tree decomposition of host image and thus guarantees the watermark is embedded most significant part of the host image and the robustness of the watermark to automated removal. Only blue channel of color image is used for watermark bits insertion, as this channel is less sensitive to HVS and makes the scheme imperceptible. In our scheme we only select only those 4x4 blocks (find by quad tree decomposition) that lie in the co-centric square area within the image with side equal to half the entire image side, to give our scheme more robustness against cropping. Since one watermark bit is embedded by manipulating the coefficient of one 4x4 blocks in wavelet domain, makes a significant improvement in capacity of the scheme. So capacity of the scheme is the maximum number of 4x4 blocks found by quad tree decomposition of image. In the proposed scheme a visually recognizable binary image is used as a watermark. Experimental results show that the scheme is high capacity, robust, invisible and inserts watermark into the significant part of the image.
THE PROPOSED COLOR IMAGE WATERMARKING SCHEME
The proposed method works in four main steps i.e., quad tree decomposition
of the host image to find important region of host image, watermark encoding
using convolution coding to make the scheme more robust, wavelet transform of
blocks found in step one and watermark embedding. For watermark detection quad
tree decomposition is applied and then watermark is extracted from the selected
blocks of the watermarked image in the wavelet domain. Our watermark is a visually
recognizable binary image (Wnxm). Figure 1 and
2 describes the watermark insertion and detection process.
In the following sub sections algorithm is described in detail.
| Fig. 1: | Block diagram of watermark insertion |
| Fig. 2: | Block diagram of watermark detection |
QUAD TREE DECOMPOSITION OF HOST IMAGE
The segmentation of an image can be done by finding boundaries between regions based on discontinuities in intensity levels or via threshold value based on the distribution of pixel properties or by a technique that is based on finding the regions directly. For the Region based segmentation one approach is to subdivide the entire image region successively into smaller and smaller quadrants region such that final partition satisfies following conditions.
Let R represent the entire image region, then we may view region based segmentation as a process that partitions R into n sub regions, R1,R2...Rn, such that
Here, P (Ri) is the criteria of homogeneity i.e., a logical predicate defined over the points in set Ri and Φ is the null set. Condition (a) indicates that the segmentation must be complete; that is, every pixel must be in region. The condition (b) requires that points in a region be connected in some predefined sense (e.g., 4-or 8-connected). Condition (c) indicates that region must be disjoint. Condition (d) deals with the properties that must be satisfied by the pixel in a segmented region-for example P (Ri) = TRUE if all pixel in Ri have the same gray level (Gonzalez et al., 2005).
This particular splitting technique has a convenient representation in the
form of a quad tree. Quad tree is a tree in which each node has exactly four
descendants as shown in Fig. 3. Parent node represents the
entire image region and its four descendant’s nodes represent the disjoint
sub regions within the large region.
| Fig. 3: | Sketch of the decomposition of an image using quad trees |
In this proposed scheme, the homogeneity criterion we have taken is the comparison of difference in the maximum gray values and minimum gray value of the block elements to a threshold value. If the difference is greater than threshold value the block is further partitioned. On the basis of our watermark size we have taken threshold value to 20. The value of threshold has significant impact on the number of blocks which will be produce after quad tree decomposition. If we select large threshold then there will be small number of regions and vice versa. The result of quad tree decomposition may have blocks of several different sizes. It splits image into regions such that large regions are formed when the intensities are uniform and small regions of variable sizes are formed in the comparatively non-uniform area of the image. Large regions represent mainly the background area or less valuable information and absence of edges. Small regions (blocks of size 4x4 or less) represent the presence of critical information of the image and hence are the good place for the watermark insertion. We propose here Quad tree decomposition to select those 4x4 blocks, which passes the homogeneity test and lies in the co-centric square region of the host image for one bit of watermark insertion. Embedding watermark, only in the central area of host image makes the scheme, resistance against cropping. Here we have proposed a block based watermarking scheme because, it is more robust than a pixel based scheme. Moreover we only select blocks of size 4x4 because they generate sufficient number of wavelet coefficients when wavelet decomposition is done for watermark embedding. Blocks of size less then 4x4 do not provide sufficient number of coefficients after wavelet decomposition and blocks of larger size do not represent critical information, so cannot be consider for watermark bit insertion.
ENCODING OF WATERMARK USING CONVOLUTION CODING
In this proposed scheme we have encoded our visually recognizable binary watermark
image by using convolution coding technique. Convolution coding and block coding
are the two major forms of channel coding. We have chosen convolution coding
because Convolution codes operate on serial data, while block coding operates
on block of information symbols, causing delays if complete block is not received
at destination. Moreover in block codes there is always one-to-one correspondence
between the information symbols and the code word symbols. For decoding convolution
codes mainly Sequential Decoding, Threshold Decoding and Viterbi Decoding are
used. The Viterbi Decoding technique became the dominant technique because of
highly satisfactory bit error performance, high speed of operation, ease of
implementation, low cost, fixed decoding time (Bose, 2002). Convolution encoding
with Viterbi decoding is a Forward Error Correcting Code (FEC) technique that
is particularly suited to a channel in which the transmitted signal is corrupted
mainly by Additive White Gaussian Noise (AWGN). Complete description of convolution
codes is given in (Fleming, 2006; Johansson and Jönsson, 1999; Johannesson
and Zigangirov, 1999). We have used here convolution coding (rate = ½)
and viterbi decoder with constraint length 7 to make the scheme more robust,
when the data is transmitted over noisy channel.
| Fig. 4: | Sketch of the decomposition of an image in four resolution levels through the DWT |
WAVELET TRANSFORM OF IMAGE BLOCK
Wavelet transform is done on the selected blocks of size 4x4. The DWT (Discrete Wavelet Transform) partition an image into a lower resolution approximation image (A) as well as horizontal (H), vertical (V) and diagonal (D) detail components. The process can be repeated to computes multiple scale wavelet decomposition. The double scale wavelet transform shows in Fig. 4.
The wavelet transform is more accurately model aspects of the HVS as compared to the FFT or DCT. This helps us to use higher energy watermarks in regions where Human Visual System (HVS) is known to be less sensitive such as the high-resolution detail bands {V, H and D}. Embedding watermark in these regions makes watermarking method more robust, at little to no additional impact on image quality (Langelaar et al., 2000). We use single scale wavelet transform to manipulate significant coefficient for watermark embedding. The average of the entire coefficient is taken and all coefficient larger than average is chosen for watermark bit embedding. Although wavelet transform itself is a hierarchical representation, Here we propose to use two hierarchical methods i.e., Quad tree region splitting method of image segmentation for selecting 4x4 blocks and the wavelet transform for finding coefficient of those selected blocks, for watermark embedding to make the method more robust. Moreover, quad tree decomposition works in spatial domain while wavelet transforms work at different resolutions.
WATERMARK EMBEDDING
The watermark bit embedding scheme consists of four steps which are describe below.
Step 1
Selection of significant region using quad tree decomposition of image:
The host image B(x, y) , which is used to embed a watermark is segmented by
quad tree decomposition to select all 4x4 blocks that passes the homogeneity
test and whose all pixels (x, y) lies in the range xmin +(xmax-xmin
)/4 <= x <= xmax-(xmax-xmin )/4
and ymin +(ymax-ymin )/4 <= y <=ymax-(ymax-ymin
)/4 where xmin, xmax, ymin, ymax
are the minimum, maximum coordinate value in x and y axes of the image
as shown in Fig. 5 and defined in Eq. 1.
(1) |
Where M is the number of 4x4 blocks found in decomposition, T = 20 is the threshold
value used by Quadtree decomposition and bi denote ith
block such that 1=<I<=M, B’ is a array to store the 4x4 blocks and
Quadtree() is a function used for quad tree decomposition of image in spatial
domain.
| Fig. 5: | Watermark embedding region |
Step 2
Encoding of binary watermark image:
Watermark Image (Wnxm) is resized such that number of pixel in resized
watermark (W’n’xm’) is less than or equal to half
of M and defined in Eq. 2. The watermark is resized because
after convolution coding with rate =1/2, make the watermark image same number
of bits.
(2) |
Where n and m are the number of row and column pixel in original watermark and n’ and m’ are the number row and column pixel in resized watermark.
Then W’n’xm’ is converted into a bit sequence (W’N) of length N in row major order as defined in Eq. 3.
W’N = [W1 W2...WN ], where
Wi _ {0, 1}, as watermark image is a black and white image.
(3) |
The bit sequence (W’N) is encoded using convolution coding
with encoding rate R = ½, which doubles its size. The encoded watermark
(W’’2N) is defined in Eq. 4.
(4) |
Where convenc() is a function for convolution encoding.
Encoded watermark is then bit wise exclusive ORed (EX-OR) with 128-bit user
defined key (k1) to increase security and it is defined in Eq.
5.
(5) |
Step 3
Watermark bit embedding in wavelet domain:
Bits of (W’’’2N) i.e., bitw are selected randomly depending on a key (k2) and is embedded into one 4x4 block sequentially in wavelet domain. The bit embedding strategy is as follows.
Step 4
Repeat (for blue component of each selected 4x4 block of host image bi
_ B’) {
| • | Perform single scale wavelet transform of block bi. |
| • | Compute average (Cavg) of all coefficient Ci found in block bi. |
| • | For all coefficients CH εCi such that CH > C avg |
| • | Select a watermark bit (bitw) randomly depending on the key (k2) value from watermark bit sequence (W’’’2N ). |
| • | Given the value of bitw is 0 or 1; modify all the coefficients ch ε CH according to: |
Where c’h is the new value of coefficient in CH which has original coefficient value of ch and λ is the watermark strength
| • | Perform inverse single scale wavelet transform after modification of coefficient to get modified block b’i. |
| • | The original block of pixels bi is then replaced by b’i } Until all watermark bits are inserted. |
| • | Marge red, green and blue channel to get the watermarked image |
WATERMARK DETECTION
In the proposed scheme, extraction algorithm requires the original image. So it is a non-blind scheme. The pseudo code for watermark bit extraction is as follows.
Step 1
Apply quad tree decomposition on original image B(X, Y) and select all 4x4
blocks that passes the homogeneity test and whose all pixels (X, Y) lies in
the range Xmin +(Xmax-Xmin )/4 <= X <=
Xmax-(Xmax-Xmin )/4 and Ymin +(Ymax-Ymin
)/4 <= Y <=Ymax-(Ymax-Ymin )/4
where Xmin, Xmax, Ymin, Ymax are
the minimum, maximum coordinate value in X and Y axes of the image and defined
in Eq. 1.
Step 2
Repeat {
| • | Take one 4x4 blocks (bi) of the host image and corresponding 4x4 block (b’i) of watermarked Image using the same coordinate value as of 4x4 block of host image. |
| • | Perform single level wavelet transform on blocks bi and b’i to get the coefficient in wavelet domain which is defined as |
Where function WT() denotes single level wavelet transform. Ci and C’i are the vectors of the same length representing wavelet coefficient
| • | Compute average of all coefficient C avg of Ci. |
| • | Initialize variable sum_w = 0 and sum_o = 0; |
| • | For j=1:16 |
| • | A watermark bit ( bit w) is decoded by making the comparison |
| • | Find original position (pos) of extracted watermark bit (bit w) using key (k2) as seed. |
| • | W2 [pos] = bitw. Where W2 is an array
for storing extracted Watermark bits. } Until all watermark bit are extracted. |
Step 3
Extracted encoded watermark bit sequence (W2) is then bit wise
exclusive ORed with 128-bit key (k1 ) as defined in Eq.
6.
(6) |
Step 4
Then output (W1) is decoded by viterbi decoding with constraint
length L = 7 to get decoded
watermark (W) as defined in Eq. 7.
(7) |
Where function viterbi_dec () denotes viterbi decoding.
Step 5
The decoded watermark bit stream (W) is then reshaped as W n’xm’
and resized to W nxm
EXPERIMENTAL RESULTS
This section presents the results of the experiment conducted with resized
color image: kids.tif (512x512) where MatLab is used for simulation purpose.
The watermark is a 50x50 binary bitmap. On the basis of trail, the value of
constants has been taken as λ = 0.3, threshold value for quad tree decomposition
= 20 and convolution encoding rate R = ½. For the experimental purpose
single level ’haar’ wavelet is used. The similarity of extracted and
original watermark is quantitatively measured by the normalized cross correlation
(Lee and Lee, 1999; Hsu and Wu, 1996) defined as:
(8) |
Where Wij and W’ij represent the pixel values at location (I, j) in the original and extracted watermark images.
Figure 6a-c show host image, binary watermark
image and watermarked image, respectively. Figure 6d the
reconstructed watermark with NCC = 1.0. Figure 6e selected
region where watermarked is embedded. It is seen that the scheme insert the
watermark in to the most valuable portion of the image. Hence it is impossible
to destroy the watermark without significant degradation of the image quality.
| Fig. 6: | (a) Original or host image kids.tif, (b) watermark image, (c) its watermarked images, (d) Extracted watermark, (e) watermark embedded region and (f) the variation of PSNR w.r.t. Various values of λ |
Figure 6a and c, it is clear that proposed
embedding algorithm does not distort host image much because these looks almost
the same. To measure the distortion incorporated by the watermarking algorithm
we have used MSE and PSNR. For color images with color components R, G and B
it is given by
(9) |
Here MSE represents the mean square error (Saenz et al., 2000). For the value of λ = 0.3, the value of PSNR is 38.8328, which is quite high. High value of PSNR implies better imperceptibility. Graphs in Fig. 6f the variation of PSNR with respect to various values of λ for the test image (kids.tif). It is seen in Fig. 6f that if we increased the value of embedding strength λ, then PSNR of the watermarked image will be decreased which implies imperceptibility of the watermarked image will decreased. So selection of λ has a great impact on the proposed methodology.
The robustness of the algorithm is also tested, by applying common image processing operation on watermarked images and then retrieving the watermark from those attacked image.
Figure 7 shows the result of applying a wiener filter to watermarked image along with the extracted watermark. The filter uses a mask of 3x3.
Figure 8 shows the result of applying median filter to watermarked
image along with the extracted watermark. The filter uses a mask of 3x3.
| Fig. 7: | Wiener filtered watermarked image and extracted watermark |
| Fig. 8: | Median filtered watermarked image and extracted watermark |
To extract watermark after common geometrical attack like scaling and rotation, the scheme does inverse geometric attack.
The scaling operation is done by scaling the watermarked image by factor 0.75 of its original size and rescaled back to 512x512 i.e., the original size, using bilinear interpolation. Bringing the watermarked images to their original size is essential because the algorithm requires the pixels in the watermarked image to be in the corresponding location as the original host image in order to extract the watermark correctly. As original host image is available in receiver side, so one can bring the scaled watermark image into its original size easily. Figure 9 the watermarked image scaled down to 0.75 rescaled image and extracted watermark.
Figure 10 watermarked image cropped with a mask of size 444x444 pixels, along with the extracted watermark from the cropped images. As the scheme insert the watermark only in the center part of the host image, the watermark is efficiently detected from the cropped image with out any loss. If any body cropped in the centre part of the watermarked image to destroy the watermark, then the cropped image will loose its commercial value. So the scheme is robust to cropping.
Figure 11 rotated watermarked images by -10 degrees and
then rotation corrected using bilinear interpolation along with the extracted
watermark. In the proposed scheme we have estimated the rotation angle with
the help of image registration as original image is available in detection time
and then rotated the host image by same angle then corrected the rotation of
host image by bilinear interpolation and then these two rotation corrected images
are compared for watermark detection. This avoids the effect of loss of data
in the rotation.
| Fig. 9: | Scaled down watermarked image, rescaled image and extracted watermark |
| Fig. 10: | Cropped watermarked image and extracted watermark |
Figure 12a and b the index-100 and index-80 JPEG compressed watermarked images along with reconstructed watermark, respectively.
Table 1 lists the Normalized Cross Correlation values for
various operations. Table 2 lists the PSNR between original
host image and watermarked image for various value of λ. Graphs in Fig.
13a-g show the performance of the algorithm for various
operations of variable strength. From the graphs we have seen that the scheme
can extracted watermark 100% in case of filtering (mask size up to 6x6), cropping,
lossy JPEG compression (less than index-80), rotation (in any direction) and
scaling operation.
| Fig. 11: | Rotated watermarked image, rotation corrected image and extracted watermark |
| Fig. 12: | JPEG compressed watermarked image and extracted watermark |
But the scheme is unable to extract watermark 100% for high compression factor,
as some data will be loose during compression and for higher mask size (grater
than 6x6) in case of filtering.
| Table 1: | Normalized cross correlation values for different operations |
| Table 2: | Lists the PSNR between original host image and watermarked image for various value of λ |
| Fig. 13: | Graphs for different operations showing variation of NCC value against various factors, (a) Normalized cross correlation (NCC) vs. Mask size in case of wiener filtered Watermarked image, (b) Normalized cross correlation (NCC) vs. Mask size in case of median filtered Watermarked image, (c) Normalized cross correlation (NCC) vs. Scale down factor, (d) Normalized cross correlation (NCC) vs. Scale up factor, (e) Normalized cross correlation (NCC) vs Angle (in degree) change in negative direction, (f) Normalized cross correlation (NCC) vs. Angle (in degree) change in positive direction, (g) Normalized cross correlation (NCC) vs. Lossy JPEG |
CONCLUSIONS
In this study, a wavelet domain region specific non-blind watermarking scheme for color images using quad tree decomposition is presented. The scheme shows that a high capacity visually recognizable binary watermark is inserted into the most valuable portion of the host image without any visual distortion. So deletion of those region will cause significant loose of image quality. As the watermark is embedded in to the selected area of the blue channel, the PSNR is also high (for this test case 38.8328) which makes the scheme imperceptible. The scheme is shown to be robust to various types of common image processing operation with very high NCC values. We have seen that the extracted watermark after common image processing operation is significantly recognizable, so it can be used easily for ownership verification. This method is rotation invariant and detect watermark 100% up to scaling down factor 0.4. But the scheme is slightly weak against lossy JPEG compressions. The main drawback of the scheme is that it requires original image to recover the watermark. But this is not desirable in all cases. This scheme can be easily extended to video data where location of watermark is very important due to large volume of data.