signalspot.com

Reversible watermark embedding algorithm A basic approach of reversible watermarking is to select an

Abstract

During the last decade, the availability of information in digital form has increased dramatically. Digital media have numerous advantages over analog media, such as higher quality, easy editing, loss less copying, and fast and efficient distribution. These advantages allow for new applications and enable new opportunities. Digital media also offer the possibility to embed additional data into the original media data in a way that is perceptually, and sometimes also statistically, undetectable.

In this project, we present a reversible watermarking method of digital images. Our method can be applied to digital audio and video as well. Compared with other reversible watermarking methods, our method employs aninteger wavelet transform to losslessly remove redundancy in a digital image to allocate space for watermark embedding. The embedding algorithm starts with a reversible color conversion transform. Then, we apply the integer wavelet transform to one (or more) decorrelated component. The purpose of both the reversible color conversion transform and the integer wavelet transform is to remove irregular redundancy in the digital image, such that we can embed regular redundancy into the digital image, for the purpose of content authentication and original content recovery. The regular redundancy could be a hash of the image, a compressed bit stream of the image, or some other image content dependent watermark. In the integer wavelet domain, we look into the binary representation of each wavelet coefficient and embed an extra bit to “expandable” wavelet coefficient. Besides original content retrieval bit streams, an SHA-256 hash of the original image will also be embedded for authentication purpose.Hash is given as input and Digital signature is generated & verified at the decoded side,for checking the security of image during transmission.

Keywords: Reversible Watermark, Integer Wavelet-Transform, Difference-Expansion,Compression,Content Authentication, Digital Signature Algorithm.

Introduction :

Reversible data embedding, also called loss less data embedding, which is a fragile technique in the sense that the embedded data will mostly be destroyed by small distortions of the image. Reversible data embedding allows one to embed a relatively large amount of data into an image in such a way that the original image can be reconstructed from the watermarked image. This makes it an ideal technique for applications where one wants to store metadata directly into the image and where loss of quality is not always acceptable. Since the watermarked image resembles the original image closely, a legacy viewer that does not know how to reconstruct the original image can still be used to view the watermarked image. Reversible data embedding has drawn lots of interest recently. It serves for the purposes of both self authentication and reversible data embedding. As being reversible, the original digital content (before data embedding) can be completely restored after authentication. Most digital watermarking methods can be categorized as either robust watermarking or fragile watermarking.

A robust watermark should be very resistant to various signal processing operations, while a fragile watermark will be destroyed or degraded in a predictable fashion when the digital content is modified. Thus fragile watermarking is a very valuable tool in content authentication. As a special subset of fragile watermarking, reversible data embedding, which is also called lossless, invertible, or erasable data embedding (or watermarking, data hiding) enables the recovery of the original content.

In this paper we present a novel reversible data embedding method for digital images. We also present a reversible watermarking method based on an integer wavelet transform. We look into the binary representation of each wavelet coefficient and embed an extra bit to“expandable” wavelet coefficient. Most high-capacity reversible watermarking relies on some form of compression to create space for embedding the payload. The location map of all “expanded” coefficients will be coded by compression and these coefficient values will be losslesslycompressed.(Arithmetic Coding or Huffman Coding can be used).Digital Signature Algorithm is used for

Signature generation & Verification for checking the security of image during transmission.

Reversible Watermarking :

We explore the redundancy in digital images to achieve very high embedding capacity, and keep the distortion (the quality degradation on digital images after data embedding) low. We calculate the differences of neighboring pixel values, and select some difference values for difference expansion. The original content restoration information, an authentication hash, and additional data will all be embedded into the difference values. The authentication is based on the decoded authentication hash. When it is verified to be authentic, one can remove the embedded data to restore the original image exactly.

In reversible watermarking, we embed a watermark in a digital image I, and obtain the watermarked image I’. Before sending it to the content authenticator, the image I’ might or might not have been tampered by some intentional or unintentional attack. If the authenticator finds that no tampering happened in I’, i.e., I’ is authentic, then the authenticator can remove the watermark from I’ to restore the original image, which results in a new image I". By definition of reversible watermark, the restored image I" will be exactly the same as the original image I, pixel by pixel, bit by bit.(FIGURE 1)

FIGURE 1: Reversible watermark diagram

Reversible watermark embedding algorithm A basic approach of reversible watermarking is to select an embedding area in an image, and embed both the payload and the original values in this area (needed for exact recovery of the original image) into such area. As the amount of information needed to be embedded (payload and original values in the embedding area) is larger than that of the embedding area, most reversible watermarking techniques rely on lossless data compression on the original values in the embedding area, and the space saved fromcompression will be used for embedding the payload.

Reversible Color Conversion

Reversible color conversion transform [1]

decor relates the dependence among different color components to a large extent. It is a loss less color transform and the transform output is still integer-valued. For a RGB color image, the reversible color conversion transform is Its inverse transform will be

Integer Wavelet Transform :

In recent years, wavelet transforms [3] have been successfully used for lossy encoding of images. The multiresolution nature of the transform is also ideal for progressive transmission. However, common wavelet filters often have floating point coefficients. Thus, when the input data consist of sequences of integers (as is the case for images), the resulting filtered outputs no longer consist of integers. Yet, for lossless encoding, it would be of interest to be able to characterize the output completely again with integers. Using dyadic coefficients with rescaling yields integer coefficients, but thislargely amplifies the dynamic range of the coefficients.

The oldest integer to integer wavelet transform is the S transform [1], which is an integer version of the Haar transform.

d_l,l = s_0,2l+1 - s_0,2l

s_1,l = s_1,l + [d_1,l/2] ———–(1i)

Difference Expansion :

In our method,[2] we will embed the payload in the difference of pixel values. For a pair of pixel values (x, y) in a grayscale image,

,x,y? Z 0<=x,y<=255 , define their (integer) average land difference h as

l= (x+y)./2, h=x-y —————————-(1)

where the symbol ?.??is the floor function meaning “the greatest integer less than or equal to”. The inverse transform of (1) is x=l+?h+1?/2, y=l-?h/2?——–(2)

The reversible integer transforms (1) and (2) are also called integer Haar wavelet transform, or the S transform.

FIGURE 2:

Reversible watermark embedding algorithm

The reversible integer transforms set up a one-to-one correspondence between x; yand l; h).

From (2), to prevent the overflow and underflow problems, i.e., to restrict x; y in the range of

[0, 255],it is equivalent to have 0<= l+?h+1?/2<=255 and 0<=l-?h/2?<=255

Since both l and h are integers, one can derive that the above inequalities are equivalent to

?h?<=2(255-l),and ?h? <=2l+1—————–(3)

Condition (3) sets a limit on the magnitude (absolute value) of the difference value h. As long as h is in such range, it is guaranteed that x; ycomputed from Eqⁿ. (2) will be grayscale values.

Location Map:-

In a digital image, one can select some expandable difference values, and embed one bit into each of them. However to extract the embedded data and restore the original grayscale values, the decoder needs to know which difference values have been selected for difference expansion. To facilitate it, we need to embed such location information, such that the decoder could access and employ it for decoding.

For this purpose, we will create and embed a location map, which contains the location information of all selected expandable difference values.

JBIG2 Compression

The location map can be viewed as a bi-level image. To store the location map, we can losslessly compress the bi-level image and store the compressed bit stream instead. We will employ JBIG2, the new international standard for lossless compression of bi-level images, to compress the location map of expanded difference numbers h. For convenience, we will denote the JBIG2 compressed bit stream of the location map of expanded h as J

JBIG2 [5] is a highly-compressed black and white image format that uses symbol recognition and substitution for very dramatic compressionresults. Any black and white image can be compressedusing JBIG2 including Group 4, MO:DCA, TIFF, PDF and more.

The JBIG2 compression algorithm works by :

1] Searching for groups of pixels that are arranged in similar shapes and using them to define a symbol.

2] Rather than retaining information on the placement of each pixel, a table is created for common symbols. This allows users to see incredible reductions in file size of multi-page documents.

Compression rates of up to 100:1 compared to uncompressed black and white TIFFs are possible. JBIG2 is supported by PDF as a compression filter. This means you can create a JBIG2 compressed PDF file and any one with Adobe Acrobat 5.0 or greater can view the image. So most desktops already have a JBIG2 viewer installed.

JBIG2 compress 7 times better than Group 4 compression. An image uncompressed 1 meg was compressed in Tiff group 4 to 82k. JBIG2 was able to compress down to 12k.

If you must know JBIG2 creates a symbol table. Usually text characters in the image. After the table is built redundant symbols can be eliminated. This can be done be creating a tolerance for lossy compression or exact for lossless compression.

Arithmetic Coding

To make more room for embedding the payload, we could further losslessly compressed the collected bit stream R, which are all the changeable bits from difference numbers h. Either arithmetic coding or Huffman coding could be used for this purpose. In our implementation, we use arithmetic coding

C = Arithmetic Coding(R) ,Where C is the compressed bit stream from the arithmetic coding

SHA-256 Hash

To detect tampering and authenticate a watermarked image, we will embed a hash of the image into itself. The new hash algorithm SHA-256 is a 256-bit hash function that is intended to provide 128 bits of security against collision attacks. We calculate the SHA-256 hash of the digital image (before the reversible color conversion transform) and denote the hash as H.

Embedding

With the compressed bit stream J of the location map, the compressed bit stream C of changeable bits, and the SHA-256 hash H (a 256 bit stream), we are ready to embed all three of them into changeable bits of difference numbers h in the integer wavelet domain.

First we combine them into one big bit stream,

where si ? {0, 1}, 1 ? i ? k, k is the bit length of S. Here we append C to the end of J , and append H to the end of C. The order of J , C, and H could be changed, as long as the embedder and the detector use the same order. Next we design a pseudo random scanning order for all the difference numbers h. This pseudo random order will be different from the scanning order used to construct the changeable bit stream R. With the pseudo random order of h, we embed the bit stream S into h by replacing (part of) changeable bits. For expandable h, we increase the bit length of h by 1, thus increase the number of changeable bits by 1.

We modify only the absolute value of h, and keep the sign (and its MSB) unchanged. If h is non-negative, since it has been increased by 1, after bit replacement, positive h will have its value decreased by 1.

We embed the bit stream S by replacing changeable bits in difference numbers h. The capacity of all changeable bits will be much larger than the bit length of S. So after embedding all bits in S, a large portion of changeable bits will not be changed.

We can select changeable bits based on how much difference it will introduce (how much it degrades the image quality) if it is changed during the embedding. We treat two difference cases here, non-expandable h and expandable h.

As we notice, modifying changeable bits in non-expandable h brings imperceptible changes to images. For expandable h, if we increase its bit length by 1 and embed one more bit into it, the visual quality degradation could be very noticeable when |h| is large, like in an edge area or an area containing lots of activity.

To achieve best image quality, the extra changeable bits which are not used for embedding should be allocated to those expandable h with large absolute values. If |h| is large, even if h is expandable, we will treat it as non-expandable by turning it off to “0” in the location map.

Worst possible image quality when changing all changeable bits, but no expanded bits.

For security reasons, the compressed bit streams J and C from JBIG2 and arithmetic coding can be encrypted by the AES algorithm, before they are embedded into changeable bits of difference numbers h.

Authentication

We state a lemma of changeable bits, before we describe the content authentication and original retrieval algorithm,

Lemma:. Assume h has g changeable bits, and its binary representation is

|h| = r₀r₁· · · r_j

.

If we arbitrarily change its changeable bits,

|h’ | = r₀r₁· · · r_j?gr’_j?g+1r’_j?g+2· · · r’_g,

where r’_j?g+i? {0, 1}, 1 ? i ? g, then the new pair is still grayscale-valued, and the changeable bits of h’ is exactly g.

Since the embedder does not change the average numbers l, the authenticator will derive exactly the same number of changeable bits in the difference number as the embedder. For expanded h whose bit length of its binary representation has been increased by 1 during the embedding, the authenticator will know such information from the location map. Thus the authenticator knows exactly which bits have been replaced and which difference numbers are expanded (by one bit) during the embedding process. All these are crucial to retrieve back the original, unwatermarked image with 100% accuracy.

The authentication algorithm is illustrated in Fig. . Similar to the embedding algorithm, we go through a reversible color conversion transform and the integer wavelet transform.

FIGURE 3:

Reversible Watermark Authentication Algorithm

From wavelet coefficients, we extract all changeable bits, ordered by the same pseudo random order of the embedding, From the ?rst segment of extracted bits, we decompress the location map of expanded difference numbers h. From the second segment, we decompress the original changeable bits values. The third segment will give the embedded hash.

With Lemma, we know which bits are modi?ed and which bits are extra expanded bits during the embedding. Thus we can reconstruct an image by replacing changeable bits with decompressed changeable bits. Then we compare the extracted hash and the SHA-256 hash of the reconstructed image. If they match bit by bit, then the watermarked image is authentic, and the reconstructed image is exactly the original, unwatermarked image.

Fragile watermarking of digital images has become a valuable tool for content authentication because the authentication information is embedded directly into the image itself.

Certain application domains , such as military and medical ,are sensitive to the embedding distortion and prohibit permanent loss of signal fidelity.

Reversible Data Embedding vs. Cryptography Authentication

Compared with authentication techniques in cryptography, reversible data embedding is covert, and it does not change the file syntax of a digital content. A legacy viewer or player can still view or play the embedded digital content. Secondly, the embedded data becomes an inherent part of the content, and is robust against (lossless) file format conversion, in contrast to a cryptography authentication hash has to be appended as extra metadata. In addition, reversible data embedding provides high capacity data embedding without increasing the storage space (file size) of the digital content.

DIGITAL SIGNATURE (ds) ALGORITHM

A ds algorithm [6] is used by a signatory to generate a digital signature on data and by a verifier to verify the authenticity of the signature. Each signatory has a public and private key. The private key is used in the signature generation process and the public key is used in the signature verification process. For both signature generation and verification, the data which is referred to as a message, M, is reduced by means of the Secure Hash Algorithm (SHA-256) . An adversary, who does not know the private key of the signatory, cannot generate the correct signature of the signatory. In other words, signatures cannot be forged. However, by using the signatory’s public key, anyone can verify a correctly signed message. A means of associating public and private key pairs to the corresponding users is required. That is, there must be a binding of a user’s identity and the user’s public key. This binding may be certified by a mutually trusted party. For example,a certifying authority could sign credentials containing a user’s public key and identity to form a certificate. Systems for certifying credentials and distributing certificates are beyond the scope of this standard.

CONCLUSIONS

With a carefully designed location map, the watermarked image quality is superb. Both the embedding capacity limit and the visual quality of embedded images of our method are among the best Currently the research is on the improvement of location map compression.

Empirical data shows a strong correlation between the location map (before lossless compression) and integer average values. The authenticator can remove the reversible watermark and retrieve an image, which is

exactly the same as the original, unwatermarked image, pixel by pixel.

REFERENCES

[1]. Jun Tian Dig marc Corporation, 19801 SW 72^nd .

Avenue, Tualatin, OR 97062,USA

“Wavelet-based reversible watermarking for

authentication”

[2].Jun Tian Digimarc Corporation, 19801 SW 72^nd

Avenue, Tualatin, OR 97062,USA.

“Reversible Data Embedding and Content

Authentication Using Difference Expansion”

[3].A. R. Calderbank AT&T-Labs Research, Room

2C-363, 600 Mountain Avenue, Murray Hill,

New Jersey 07974. “Wavelet Transforms That

Map Integers to Integers”

[4] Federal Information, Processing Standards

publication 180-22002 August 1. ], “SECURE

HASH STANDARD “

[5]. JBIG2 Image Conversion and Viewers -

Snowbound Software.htm

[6]. FEDERAL INFORMATION

PROCESSING STANDARDS PUBLICATION

2000 January 27. ”DIGITAL SIGNATURE

STANDARD (DSS) “

Attached Files:

• dip01218.doc (96 KB)