International Journal of Innovative Research in Computer and Communication Engineering

International Journal of Innovative Research in Computer and Communication Engineering

Menu

ISSN ONLINE(2320-9801) PRINT (2320-9798)

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

A Review of Watermarking Algorithms for Digital Image

Jaishri guru1, Hemant damecha2
  1. Student of M.E. Software Systems, Department of Computer science and Engineering, Shri ram Institute of Technology, Jabalpur (R.G.P.V University Bhopal), Madhya Pradesh, India
  2. Assistent Professor, Shri ram Institute of Technology, Jabalpur, Madhya Pradesh, India
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering

International Journal of Innovative Research in Computer and Communication Engineering

Abstract

The growth of the Internet along with the increasing availability of multimedia applications has spawned a number of copyright issues. One of the areas that this growth has fueled is that of digital watermarking. Digital watermarking is the general technique of embedding a blob of information in the original file, such that an altered file is obtained. The blob of information, thus included, serves one of different uses, such as, identifying piracy, sensing tampering, or reassuring integrity. The approaches to watermarking are diverse and can be broadly classified based on their visibility, robustness, or fragility. Their uses are also versatile, as they can be applied to text, images, audio, or video. In this paper, we will go through various algorithms of watermarking for digital image.

Keywords
Digital watermarking classification, SVD, DCT, DWT, HVS

BROAD CLASSIFICATION OF WATERMARKING TECHNIQUES
I. Watermarking techniques can broadly be classified based on their inherent characteristics: visible and invisible [1].
Visible watermarks: A visible alteration of the digital image by appending a “stamp” on the image is called a visible watermark. This technique directly maps to that of the pre-digital era where a watermark was imprinted on the document of choice to impose authenticity.
Invisible watermarks: By contrast, an invisible watermark, as the name suggests that this is invisible for the most part and is used with a different motive. While the obviousness of visible watermarking makes distinguishing legitimate and illegitimate versions easy, its conspicuousness makes it less suitable for all applications. Invisible watermarking revolves around such suitable factors that include recognizing authentic recipients, identifying the true source and nonrepudiation.
II. Another way of classifying watermarking technique is a factor of its usage: fragile, semi-fragile, and robust [3].
Fragile watermarks: These are complementary to robust watermarks and are, as a rule, more change-sensitive than robust watermarks. They lose their mettle when they are subject even to the smallest changes. Their use lies in being able to pin-point the exact region that has been changed in the original watermarked image. The methods of fragile watermarking range from checksums and pseudo-random sequences in the LSB locate to hash functions to sniff any changes to the watermark [4].
Semi-fragile watermarks: These watermarks are a middle ground between fragile watermarks and fragile watermarks. They engulf the best of both worlds and are more resilient than fragile ones in terms of their robustness. They also are better than robust watermarks in terms of locating the regions that have been modified by an unintended recipient.
Robust watermarks: By hypothesis robust digital watermark repeal all types of attacking techniques on the watermark [5]. Watermarks can be used to hold knowledge of ownership. Such watermarks need to remain steadfast to the original image to do what they advertise. The intactness of the watermark is a measure of its robustness. These watermarks must be able to withstand normal manipulations to the image such as reduction of image size, lossy compression of image, changing the contrast of the images, etc.
III. Digital watermarks are also spatial and spectral watermarks.
Spatial watermarks: Watermarks that are applied to the “spatial domain of the image” are said to be spatial watermarks [6].
Spectral watermarks: These are watermarks that are applied to the “transform coefficients of the image” [6].
The rest of the paper is organized as follow. The ground rules for a good watermark will be laid down in the next section. After describing the various stages of the watermarking process, we will focus on various algorithms for watermarking, and analyze the algorithms.

Criteria for a good watermark:
Though watermarks belong to different categories, some of the general characteristics that watermarks must possess are the following [7]:
1. The watermark must be strongly bound to the image and any changes to the watermark must be apparent in the image.
2. Watermark must also be able to withstand changes made to the image. Such changes include modifications and enhancements of images such as size modifications, cropping, and lossy compression, to name a few.
3. The watermark must not undermine the visual appeal of the image by its presence (especially for invisible watermarks).
4. Watermark must be indelible and must be able to survive linear or non-linear operations on the image [8].
The following are criteria for a visible watermark: [9]
1. The watermark must be apparent on all kinds of images.
2. The size of the watermark is crucial. The more pervasive the watermark the better so that the watermarked area cannot be modified without tampering with the image itself.
3. The watermark must be fairly easy to implant in the image.

The Watermarking Process
The watermarking process comprises of the following stages [10].
1. Embedding stage
2. Extraction phase
3. Distribution stage
4. Decision stage
Embedding stage: In this stage, the image to be watermarked is preprocessed to prime it for embedding. This involves converting the image to the desired transform. This includes the discrete cosine transform (DCT), the discrete Fourier transform (DFT) and the wavelet domains. The watermark to be embedded may be a binary image, a bit stream or a pseudo-random number that adheres to, say, a Gaussian distribution. The watermark is then appended to the desired coefficients (low frequency or intermediate frequency) of the transform, as recommended by Human Visual System (HVS) research. The watermarked image is the output of this process and is obtained by performing an inverse transform on the altered transform coefficients [11].
Distribution stage: The watermarked image obtained above is then distributed through digital channels (on an Internet site). In the process, this may have undergone one of several mappings, such as compression, image manipulations that downsize the image, enhancements such as rotation, to name a few. Peter Meerwald [11] refers to the above as “coincidental attack”. Any of the above may put the watermarking scheme to test, as we will see in the ensuing section. In addition, malicious attacks also are possible in this stage to battle with the watermark. These are referred to in Meerwald’s work [11] as “hostile attacks”.
Extraction stage: In this stage, an attempt is made to regain the watermark or signature from the distributed watermarked image. This stage may need a private key or a shared public key, in combination with the original image, or just the watermarked image [11].
Decision stage: In this stage, the extracted watermark is compared with the original watermark to test for any discrepancies that might have set in during distribution. A common way of doing this is by computing the Hamming distance [11].
image
Where, both the numerator and the denominator are the dot products.
HD obtained above is compared to a threshold, T, to determine how close Wmod is to W.

LITERATURE REVIEW: TECHNIQUES USED IN WATERMARKING FOR DIGITAL IMAGES
Digital watermarking is a technology that manages and assigns data authentication, security, and copyright security to the digital information. Digital watermarking algorithms are divided into two groups. One technique is spatial domain. In this techniques pixel values straightly works. The Second is frequency domain techniques employ several transforms, either local or global. Various widely recognized techniques are described consequently [12].
Spatial Domain Techniques: Watermark in spatial domain technique is inserted in the cover image and changing pixels value. Against the possibility of the watermark becoming visible the algorithm should carefully weight the number of altered bits in the pixels value [12].
Frequency Domain Techniques: Frequency-domain methods are more widely applied as compared to spatial - domain methods. The aim of watermarks in the spectral coefficients of the image is embedded. In frequency domain Mostly used transforms are the DCT (Discrete Cosine Transform), DFT (Discrete Fourier Transform), DWT (Discrete Wavelet Transform).For as much as the characteristics of the HVS (human visual system) are better captured by the spectral coefficients that’s why watermarking in the frequency domain. For example, human visible system for lowfrequency coefficients is more sensitive, and for high-frequency coefficients it is less sensitive, also we can say that in troths, The LF (low frequency) coefficients are significant perceptually, that means distortion in the original image might cause by those components and high-frequency coefficients are insignificant considered. Thus, HF (high frequency) coefficients aggressively remove by processing techniques like compression. To get a balance between robustness and imperceptibility large algorithms embed watermarks in the midrange frequencies [13].
Discrete wavelet transform: Discrete wavelet transform (DWT) is a neoteric technique consecutive used in digital image processing, compression, digital watermarking etc [14]. Discrete wavelet transform is more efficient than discrete cosine transform method. The image is dissolved into high and low frequency elements in two level discrete wavelet transform (DWT). The robustness with respect to divers attacks increases when the watermark is embedding in low frequencies gained by WD (wavelet decomposition). Now first digital media is segmented into frames, Then discrete wavelet transform is applied to luminance element of each frame which outcomes into discrete sub bands. Again these bands are dissolved into discrete components. Now covariance matrix is calculated for each component. Now watermarked luminance component of the frames are gained by applying inverse discrete wavelet transform. Ultimately watermarked digital media is gained by renewing the watermarked frame [14, 3].
Singular value decomposition: Singular value decomposition is a rousing numerical technique which is utilized to diagonally matrices in numerical analysis [15]. In variety of applications singular value decomposition is used as an algorithm. In this singular value decomposition transformation, One matrix can be dissolved into three matrices. These matrices are of the equal size as the original matrix. By the linear algebra, an image is an array of nonnegative entries of scalar values that can be deduced as a matrix. Sine tort of important component, Assume if formula is where A is a square image, R is the real number domain, Then singular value decomposition of A is denoted as . Here U and V both are orthogonal matrices, and diagonal matrix is S, as
image
Here diagonal components i.e. s’s are singular values and satisfy S1≥S2≥…....Sr≥Sr+1≥??……..??Sn??0 Singular value decomposition is an optimal matrix decomposition technique in a least square sense that it grids the highest signal energy into some coefficients as feasible [16].

Hash Functions as fragile watermarks:
According to Wolfgang and Delp’s [17], hash functions can be used as fragile watermarks. One of the methods they have used as watermarks is the block-based hash function (BBHF) [17]. The hash is computed on the width and height of the image block. Specifically, Xb is the width of the block and Yb is the height of the block and Xb * Yb is the hash function. The hash values of every block of the image are stored. In order to test the sanctity of an image, the stored hash values are compared to the hash values of the image whose sanctity is to be tested. If the hash values do not correspond to each other, then the block which houses the discrepancy is the one that has been altered.

Variable-Watermark Two-Dimensional Algorithm (VW2D) [17]
Wolfgang and Dr. Delp’s have developed this algorithm for image authentication. Both the watermark and the watermarked image are used here to authenticate the image. A pseudorandom binary sequence is the watermark and this sequence is superimposed on the original image in blocks. This can be elucidated as follows: Let WI be the watermarked image, W be the watermark and X be the original image. Then WIb is a block of the watermarked image, Wb is a block of the watermark and Xb is a block of the original image. The watermarked image is generated as follows [17]:
image
And each watermarked image block is generated as follows:
image
Checking to see if a watermark resides in an image (Test) is done as follows:
image
A threshold value can be chosen to authenticate the test image. The threshold is compared with the delta value computed above. The choice of the threshold value can determine the extent of changes that are tolerated to the watermarked image. The spectrum of scenarios that can be tested range gradually from unchanged to highly manipulate. Such a choice also gives the users of this algorithm some leeway in choosing the strictness with which manipulations are caught. The effect of choosing different threshold values can be seen in the images in the Appendix (Figures 3, 4, 5, 6).

HUMAN VISUAL SYSTEM (HVS)
In order to develop good watermarking algorithms, characteristics of the human visual system have been extensively studied. The nuances of visual perception have given scientists an insight into modeling watermarks that do not interfere with the host image. Wolfgang, Delp and Podilchuk [17, 8] have listed some of the characteristics of the human visual system by the following 3 criteria, as given in Wolfgang et al’s paper [17, 8]:
1. Sensitivity to frequency: The HVS is more sensitive to higher frequencies than to lower frequencies. [17,8]
2. Contrast masking: This refers to how one signal influences the expression of another signal. Presence of two signals in the same frequency enhances this property [17, 8].
While the above two algorithms have been applied to the spatial domain of the image, watermarking algorithms that tap into various transforms became popular, thanks to their robustness and quality. Some of the transforms that are used for this purpose include the DCT (discrete cosine transform), DFT (discrete Fourier transform) and the wavelet domains. These techniques combined with studies on the human visual system have allowed for the development of good watermarking techniques.
A very popular compression technology for still images is JPEG [17,8]. Compression in JPEG occurs as follows. The still image to be compressed is passed through a coder, which transforms the image by ripping it into distinct blocks of 8*8 pixels. A DCT is applied on the thus obtained distinct blocks.

A Semi-Fragile Watermark in the DCT domain –Lin’s algorithm:
Lin’s et. al [18] has developed a semi-fragile watermark in the DCT domain.
Watermark: The watermark is given by “pseudo-random zero-mean, unit variance Gaussian distributed numbers” [18]
In the figure 7, clear blocks are marked coefficients while the grey blocks are unmarked coefficients. Figure obtained from ftp://skynet.ecn.purdue.edu/pub/dist/delp/ei00-water/paper.pdf
Embedding stage: Watermark is embedded in every 8*8 DCT block. Though each block has a different watermark, the watermark is embedded on the same indices of each block. The DC coefficient and some other coefficients including the high frequency AC coefficients of the block are not marked. The inverse DCT is constructed to produce the watermark W. [18]
WI= O + strength (W),
Where, WI is the watermarked image, O is the original image, and strength is the strength of the watermark.
Detection stage: Detection is done by comparing blocks with corresponding blocks to localize any changes. A threshold is compared to the test value computed for each of the blocks to figure out if a block has been modified. The algorithm described in Lin’s paper is discussed below. [18] Let B(x, y) be an arbitrary block.
Col-diff (Block(x, y)) = Block(x, y) – Block(x+1, y) for x in {1, 2,…blocksize –1) or 0 if x = blocksize
Row-diff (Block(x, y)) = Block(x, y) – Block(x, y+1) for y in {1, 2,…block size –1) or 0 if y = block size
T is computed as a single matrix obtained by concatenating col-diff and row-diff of the test image block and waterblock is the corresponding matrix for the watermarked image.
T = [Col-diff (T(x, y)) Row-diff (T(x, y))]
W = [Col-diff (W(x, y)) Row-diff (W(x, y))]
Since we need to obtain a dot product, the matrix T and W above are permuted to obtain a vector. The permutation function, F, should be uniform for both the matrices.
F (T) = vector (T)
W (T) = vector (T)
The test statistic, S, can be computed as follows:
S = (T.W) / sort ((T.T) (W.W))
Comparing the blocks can be done as follows. An appropriate threshold, T, is chosen and compared with the test statistic.
S >= T => block unaltered
S < T => block altered

EVALUATION OF ALGORITHMS
The hash algorithm and the VW2D algorithms were used in the spatial domain while Lin’s algorithm utilized the DCT domain. The hash algorithm is the least tolerant to changes to images, while both VW2D and Lin’s algorithm offered some resilience to change in the form of a tolerance level that could be assigned for comparisons. However, while both VW2D and Lin’s algorithm can handle lossy compression that JPEG doles out to images, Lin’s algorithm also made use of the HVS perception in its algorithm by only making changes to the low frequency coefficients. Since JPEG compression is done using the DCT transform, Lin’s algorithm is the best bet for JPEG images. Using any of the above algorithms will reflect changes made to the watermarked images, although to different extents. The watermarks themselves are not too difficult to embed and hence can be embedded easily. An appropriate watermarking process can therefore be chosen, based on the purpose and level of protection required.

CONCLUSION
Watermarking is a vast field and a lot of research is going on in this area. There are commercial players who are vying for dominance in this field. Though a clear-cut winner has not been declared yet, a combination of other cryptographic techniques (such as encryption) and watermarking together will definitely provide copyright protection for images. Depending on the intended requirements and the level of security required, an appropriate watermarking algorithm can be chosen.
 

Figures at a glance
Figure 1 Figure 2 Figure 3 Figure 4
Figure 1 Figure 2 Figure 3 Figure 4
Figure 5 Figure 6 Figure 7
Figure 5 Figure 6 Figure 7
 

References