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 nonblind 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 nonblind 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 nonblind digital image watermarking algorithm based on multiresolution wavelet analysis. They suggest various reasons why HighLow (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 HighHigh (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 nonblind, 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 objectoriented 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 cocentric 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 (W_{nxm}). 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, R_{1},R_{2}...R_{n},
such that
Here, P (R_{i}) is the criteria of homogeneity i.e., a logical predicate
defined over the points in set R_{i} 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., 4or 8connected). Condition (c) indicates that
region must be disjoint. Condition (d) deals with the properties that must be
satisfied by the pixel in a segmented regionfor example P (R_{i}) =
TRUE if all pixel in R_{i} 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 nonuniform 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 cocentric 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 onetoone 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 highresolution 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 x_{min } +(x_{max}x_{min
})/4 <= x <= x_{max}(x_{max}x_{min })/4
and y_{min } +(y_{max}y_{min })/4 <= y <=y_{max}(y_{max}y_{min
})/4 where x_{min}, x_{max}, y_{min}, y_{max
} are the minimum, maximum coordinate value in x and y axes of the image
as shown in Fig. 5 and defined in Eq. 1.
Where M is the number of 4x4 blocks found in decomposition, T = 20 is the threshold
value used by Quadtree decomposition and b_{i } denote i^{th}
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 (W_{nxm}) 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.
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} = [W_{1} W_{2}...W_{N }], where
W_{i } _ {0, 1}, as watermark image is a black and white image.
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.
Where convenc() is a function for convolution encoding.
Encoded watermark is then bit wise exclusive ORed (EXOR) with 128bit user
defined key (k_{1}) to increase security and it is defined in Eq.
5.
Step 3
Watermark bit embedding in wavelet domain:
Bits of (W’’’_{2N}) i.e., bit_{w} are selected randomly depending on a key (k_{2}) 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 b_{i}
_ B’) {
• 
Perform single scale wavelet transform of block b_{i}. 
• 
Compute average (C_{avg}) of all coefficient C_{i }found
in block b_{i}.

• 
For all coefficients C_{H} εCi
such that C_{H }> C _{avg} 
_{
} • 
Select a watermark bit (bit_{w}) randomly depending on the key
(k_{2}) value from watermark bit sequence (W’’’_{2N}^{
}).

• 
Given the value of bit_{w} is 0 or 1; modify all the coefficients
c_{h} ε C_{H} according
to:

Where c’_{h }is the new value of coefficient in C_{H}
which has original coefficient value of c_{h} 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 b_{i} 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 nonblind 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 X_{min } +(X_{max}X_{min })/4 <= X <=
X_{max}(X_{max}X_{min })/4 and Y_{min } +(Y_{max}Y_{min
})/4 <= Y <=Y_{max}(Y_{max}Y_{min })/4
where X_{min,} X_{max,} Y_{min,} Y_{max } 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 (b_{i}) 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 b_{i }and b’_{i}
to get the coefficient in wavelet domain which is defined as

Where function WT() denotes single level wavelet transform. C_{i }and
C’_{i} are the vectors of the same length representing wavelet
coefficient
• 
Compute average of all coefficient C _{avg }of C_{i.} 
• 
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 (k_{2}) as seed.

• 
W^{2 }[pos] = bit_{w. }Where W^{2 } is an array
for storing extracted Watermark bits.
} Until all watermark bit are extracted.

Step 3
Extracted encoded watermark bit sequence (W^{2}) is then bit wise
exclusive ORed with 128bit key (k_{1 }) as defined in Eq.
6.
Step 4
Then output (W^{1}) is decoded by viterbi decoding with constraint
length L = 7 to get decoded
watermark (W) as defined in Eq. 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:
Where W_{ij} and W’ij represent the pixel values at location (I,
j) in the original and extracted watermark images.
Figure 6ac 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
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 index100 and
index80 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.
13ag 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 index80), 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 nonblind 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.