WO2006052220A1

WO2006052220A1 - Method and system for embedding data, method and system for detecting data and method and system for reconstructing data

Info

Publication number: WO2006052220A1
Application number: PCT/SG2005/000378
Authority: WO
Inventors: Zhishou Zhang; Qibin Sun; Rongshan Yu; Wai Choong Lawrence Wong
Original assignee: Agency For Science, Technology And Research
Priority date: 2004-11-04
Filing date: 2005-11-04
Publication date: 2006-05-18

Abstract

A method for embedding first data into second data is described comprising transforming the first data according to a domain transformation to generate at least one transformation coefficient splitting the at least one transformation coefficient into a first part comprising a first plurality of bits and into a second part comprising a second plurality of bits according to a splitting point specifying a bit position and modifying the first plurality of bits and the second plurality of bits based on the first data such that the at least one coefficient can be calculated from the modified first plurality of bits and the modified second plurality of bits.

Description

Method and system for embedding data, method and system for detecting data and method and system for reconstructing data

Field of the invention The invention relates to a method and system for embedding first data into second data, a method and system for detecting whether first data are embedded into second data, a method and system for reconstructing second data into which first data have been embedded and computer program elements.

Background of the invention

Data embedding, for example digital watermarking of digital multimedia data, has been studied in recent years for applications such as ownership right protection and content integrity verification. Data embedding can be done . in a lossy way or a lossless way.

In case of lossy data embedding, (see for example [1], [2], [3] ) , the media data in which the data are embedded is permanently impaired. This means that it is not possible to recover the original cover media once data have been embedded. Since lossy embedding methods often employ- perceptual models such as Human Vision System (HVS) or Human Acoustic System (HAS) , humans cannot see or hear, respectively, any difference under normal conditions between the cover media (i.e. the original media data in which data are to be embedded) and the cipher media (i.e. the media data in which the data have been embedded) . However, lossy, data embedding may be unacceptable for some application like for example in the medical field or for military applications where there is a need that cover media can be losslessly recovered. Lossless data embedding (see for example [4] , [5] ) allows to recover the original cover media from the cipher media. Typically, a lossless data embedding method embeds data into perceptually less important parts of the cover media. For example, when the media data are a digital picture, the data embedding produces artifacts especially in flat or smooth regions of the picture, for example in the sky or in a wall shown on the picture. Lossy data embedding is more robust than lossless data embedding since in case of lossy embedding, data may be embedded in perceptually important regions of the cover media. In case of an image, for example, data may be embedded around edges shown in the picture. Due to a lack of robustness, known lossless data embedding methods are not suitable for applications such as right protection.

Multimedia data often need to be transferred from one entity to another entity in a heterogeneous environment which consists of different devices with different capabilities, for example different communication channels with different bandwidth, storage devices with different capacity and so on. It is therefore desired that multimedia data can be transferred and decoded at different quality levels, for example at different resolutions in case of visual data. For this, scalable multimedia coding standards have been developed, for example JPEG2000 (described in [6]) and AAZ (described in [7]) for MPEG-4 SLS (scalable to lossless), which support lossy-to-lossless scalability.

There are demands for a data embedding method wherein the cipher media supports lossy-to-lossless scalability. However, using a lossy embedding method, the original cover media may not be recovered once data have been embedded into the cover media. When using a lossless data embedding method, the embedded data are not robust enough.

In [8], a content based digital signature scheme for verifying the authenticity of JPEG2000 images is described.

In [9], a quality of protection framework is described wherein differential security levels for different device user and application security requirements and preferences.

Document [10] describes a method for digital watermarking for still images that is based on the wavelet transform.

Summary of the invention A method for embedding first data into second data are provided comprising transforming the first data according to a domain transformation to generate at least one transformation coefficient, splitting the at least one transformation coefficient into a first part comprising a first plurality of bits and into a second part comprising a second plurality of bits according to a splitting point specifying a bit position and modifying the first plurality of bits and the second plurality of bits based on the first data such that the at least one coefficient can be calculated from the modified first plurality of bits and the modified second plurality of bits.

Further, a system and a computer program element according to the method for embedding first data into second data described above are provided. Further, a method for detecting whether first data are embedded into second data is provided, wherein the second data are given by at least one transformation coefficient comprising splitting the at least one transformation coefficient into a first part comprising a first plurality of bits and into a second part comprising a second plurality of bits according to a splitting point specifying a bit position, determining a correlation value specifying the correlation between the first plurality of bits or the second plurality of bits with the first data and deciding based on the correlation value if the first data are embedded in the second data.

Further, a system and a computer program element according to the method for detecting whether first data are embedded into second data described above are provided.

Further, a method for reconstructing second data into which first data have been embedded, wherein the second data into which the first data are embedded are given by at least one transformation coefficient comprising splitting the at least one transformation coefficient into a first part comprising a first plurality of bits and into a second part comprising a second plurality of bits according to a splitting point specifying a bit position and combining the first part and the second part to generate an original transformation coefficient.

Further, a system and a computer program element according to the method for reconstructing second data into which first data have been embedded described above are provided. Short description of the figures

Illustrative embodiments of the invention are explained below with reference to the drawings.

Figure 1 shows a system according to an embodiment of the invention.

Figure 2 shows an encoding and embedding unit according to an embodiment of the invention.

Figure 3 shows a decoding and extracting unit according to an embodiment of the invention.

Figure 4 shows an encoding and embedding unit according to an embodiment of the invention.

Figure 5 shows a decoding and extracting unit according to an embodiment of the invention.

Detailed description

Illustratively, to embed the first data into the second data, a domain transformation is carried out and the second data are represented as transformation coefficients. The transformation may for example be a wavelet transformation, a discrete cosine transformation or a discrete Fourier transformation or other. The transformation coefficients are each split into a first part and a second part and the first data are embedded in such a way by modifying the first parts and the second parts, that a transformation coefficient may be losslessly reconstructed from its modified first part and its modified second part. In particular, the distortion introduced by embedding the data may cancel itself out when the first part and the second part are re-combined to form the transformation coefficient.

The invention may be used for data embedding in scalable media like JPEG2000 image data or AAZ (Advanced Audio Zip) audio data, such that the cipher media (i.e. the media data into which data have been embedded) supports lossy-to- lossless decoding. The first data may be embedded into the first part (also denoted by core part) and into the second part (also denoted by residual part) using a known embedding method, for example the spread spectrum watermarking method or a method based on quantization.

Since the data are embedded in such a way that, illustratively, the modification of the first part and the modification of the second part compensate each other, the second data into which the first data have been embedded can be losslessly reconstructed by a decoder. Even if the decoder receives the first part and only a part of the second part (this may happen when the scalability of the data is exploited and the second part is truncated) the modifications of the first part and the second part cancel each other to a certain extent and the quality loss is small. In the embodiment described below, the second data can even be reconstructed without extracting the first data from the second data.

In the embodiment described below, the first data may be extracted from the second data after it has been embedded based on the modified first parts or the modified second parts. The robustness of the embedding may be controlled by adjusting the splitting point. When the first part of the transformation coefficient comprises the bits of the transformation coefficient with higher significance and the second part comprises those with lower significance, when the splitting point is adjusted towards the first part, the embedded data becomes more robust, and viqe versa. This is quite useful in a pervasive environment that contains many heterogeneous devices with different capabilities and resources. In such an environment, the second data (e.g. media data) is often transcoded according to end-receivers' capability, but it is desirable that the embedded data are not lost. In one embodiment described below experiments show that the embedded data, in this case a watermark, is robust against code stream truncation. The robustness can be controlled by a parameter called the WSR (watermark survival rate) .

The second data into which the first data have been embedded (this, when the second data are media data, is also called cipher media) may be shaped according to a pre-defined distortion bound. For example, when the embedding is done by adding a modification coefficient to the first part, the modification coefficient may be adjusted in a suitable way such that the distortion introduced by the data embedding is within a pre-defined bound.

The compensation can be done either in the spatial domain or in the transform domain.

The first data may be transformed according to any transformation (e.g. DCT or wavelet transformation) as long as the transformation is lossless or is an integer transformation. Embodiments of the invention emerge from the dependent claims. The embodiments which are described in the context of the method for embedding first data into second data are analogously valid for the system for embedding first data into second data, the method and the system for detecting whether first data are embedded into second data, the method and the system for reconstructing second data into which first data have been embedded and the computer program elements.

In one embodiment, when the modified first plurality of bits and the modified second plurality of bits are combined to form the at least one coefficient, the modification of the first plurality of bits and the modification of the second plurality of bits are cancelled out.

From the first data, at least one modification value may be determined and the first plurality of bits and the second plurality of bits may be modified based on the at least one modification value. For modifying the first plurality of bits, the at least one modification value may be added to the first part. For modifying the second plurality of bits, the at least one modification value may be bit-shifted and may be substracted from the second part. The at least one modification value is for example bit-shifted according to the splitting point.

In one embodiment, the method further comprises combining the modified first part and the modified second part to form a modified transformation coefficient. The method may further ^• comprise encoding the modified transformation coefficient. This may be done according to a known encoding technique, for example according BPGC (bit plane Golomb coding) . The second data are for example media data. These may be video data, audio data or image data. The first data are for example digital watermark data.

In one embodiment, the splitting point is determined according to the JPEG2000 EBCOT process (see [6]) . The splitting of the at least one wavelet coefficient may be in particular done according to an existing coding technique.

Fig.l shows a system 100 according to an embodiment of the invention.

Original multimedia data 101, also called the cover media, is supplied to an encoding and embedding unit 102. Further, data to be embedded 103, which is to be embedded into the original multimedia data 101 is supplied to the encoding and embedding unit 102.

The encoding and embedding unit 102 embeds the data to be embedded 103 into the original multimedia data 101. In this embodiment, the data embedding process is integrated with the encoding process, so the encoding and embedding unit 102 also encodes the original multimedia data 101 to generate a code stream 104 wherein the data to be embedded 103 is embedded.

The code stream 104 may be standard-compliant for example compliant with the Advanced Audio Zip (AAZ) which has been accepted as reference model for MPEG-4 audio Scalable to Lossless (SLS) coding. The code stream 104 is scalably coded by the encoding and embedding unit 102. It may be sent to a decoding unit 105 which decodes the code stream 104 to reconstruct the original multimedia data 101 from the code stream 104 without distortions, i.e. without loss of quality.

The code stream 104 may also be sent to an extracting unit 106 which extracts the data to be embedded 103 from the code stream 103.

The code stream 104 may as well be sent to a decoding and extracting unit 107 which both extracts the data to be embedded 103 from the code stream 104 and reconstructs the original multimedia 101 from the code stream 104. Since the code stream 104 has been scalably coded, the reconstruction of the original multimedia data 101 can also be done with a loss of quality. This is for example done when the original multimedia 101 is not required in its original quality or when the communication channel used for transferring the code stream 104 to the decoding and extracting unit 107 does not support a high enough bandwidth to transmit all the data of the code stream 104 and parts of the code stream 104 required for high quality are not transmitted.

The encoding and embedding unit 102, the decoding unit 105, the extracting unit 106 and the decoding and extracting unit 107 may be for example realized by computer systems, for example personal computers, but also mobile radio terminals, handhelds, and so on. The code stream 104 may be transmitted to the decoding unit 105, the extracting unit 106 and the decoding and extracting unit 107 by means of a communication network such as a LAN (local area network) , the Internet or a mobile communication network.

Typical applications of the system 100 are: • Ownership protection and copyright protection of media: In order to protect the ownership and copyright of media, a common practice is to embed some related information like author name, transaction date or logo. The encoding and embedding unit 102 can be used to embed such information into cover media in a robust manner with no or minimized distortion introduced.

• Media authentication: Authentication is to verify the origin and integrity of the received media. Many media authentication methods, like fragile and semi-fragile authentication, need to embed the signature into the media. Therefore, the system 100 can be used for media authentication.

• Quality assessment and control: differing from previous two general applications, the system 100 can be used to estimate the quality of the received media based on the quality of the extracted data which was embedded. It therefore naturally provides more functions to the consumption of the media. For example, the amount the user pays could be based on the quality of the received media (i.e., the quality of the extracted data) . The data embedded in the core parts could be used to control the streaming of the residual parts.

An example for an encoding and embedding unit 102 and a decoding and extracting unit 107 for the case that the original multimedia data 101 are image data are explained with reference to Fig.2 and Fig.3,. respectively.

Fig.2 shows an encoding and embedding unit 200 according to an embodiment of the invention. Original multimedia data in form of original image data 201 is processed by a colour transform and wavelet transform unit 202 which performs a colour transform of the original image data 201 and generates wavelet coefficients from the colour transformed original image data 201. The generated wavelet coefficients are supplied to the encoding and embedding unit 200.

The encoding and embedding unit 200 is further supplied with data to be embedded 203, which should be embedded into the original image data 201, with the specification of a robustness level 204 at which the data to be embedded 203 should be embedded into the original image data 201 and with a specification of the compression bit rate 205.

According to the robustness level 204, the encoding and embedding unit 200 searches for a splitting point among the bit planes of the wavelet coefficients. This may be done according to the JEPG2000 EBCOT (Embedded Bit-plane Coding with Optimal Truncation) process (see [6]) .

The bit planes above the splitting point constitute the core part u = [u_]_, U2, ... U_n] and the bit planes below the splitting point constitute the residual part d = [d]_, d2, ... , d_n] . This means when all bits of the ith wavelet coefficient are written in significance decreasing order, the bits starting from the most significant bit until the splitting point form the number UJ_ and the remaining bits, starting from the splitting point until the least significant bit form the number dj_. When written as a vector _I, the original wavelet coefficients are consequently given by I = u x 2 + d when L denotes the number of bit planes in the residual part. The splitting of the wavelet coefficients into core parts 207 and residual parts 208 is done by a bit-plane splitting unit 206.

Further, a random noise sequence of real numbers f = [rj_, r£, ... , r_n] is generated which is normally distributed with zero mean and unit variance.

A bit bj_ (being equal to 0 or equal to 1) of the data to be embedded 203 is embedded into core parts 207 UJ by a first embedder 209 and into residual parts dj according to

Uj = Uj + Wj

where WJ = rjX(2bj_ - 1) and im < j < (i + l)m .

The values WJ may be adjusted such that UJ and Uj as well as dj and dj do not have different signs and such that the constraints

Uή + W- < 2^U - 1,

are fulfilled where U is the number of bit planes in the core part and λ is the number of extra bits which are used to accommodate overflow of dj . The range of Wj is [~r-j, rj ] . Given a rj , if WJ does not satisfy the constraints, then a constant with a fixed step- size is repeatedly added or substracted until a value is found such that the constraints are fulfilled. Such a value is definitely found: The worst case is Wj = 0 which means no watermark (rj) is added.

Each bit b^ of the data to be embedded 203 is embedded in this way by the first embedder 209 and the' second embedder 210.

The numbers UJ generated by the first embedder 209 and the numbers dj generated by the second embedder 210 are pairwise combined to single coefficients according to

by a bit-plane merging unit 211. The resulting coefficients are supplied to a entropy coding unit 212 which generates a JPEG2000 codestream 213.

The encoding and embedding unit 200 further comprises a "R-D Summerization" module 214 which is one of the original JPEG2000 coding modules. It collects the R-D (rate distortion) contribution from the individual codeblock / subband / resolution level to formulate (with different weighs) a global R-D curve for whole image. It is used to give the user a guideline on how to truncate the compressed bitstream: if he truncates the bitstream more, then more distortion will be introduced into the decoded image. The decoder and extractor corresponding to the encoding and embedding unit 200 is explained in the following with reference to fig.3.

Fig.3 shows a decoding and extracting unit 300 according to an embodiment of the invention.

A JPEG2000 codestream 301, for example the JPEG2000 codestream 213 generated by the encoding and embedding unit 200 is entropy decoded by an entropy decoding unit resulting in a vector of wavelet coefficients 1C' = [l'ι, I;?, ... , I_n] which is supplied to the decoding and extracting unit 300.

Further, a specification of the robustness level 303 according to which data are embedded is supplied to the decoding and extracting unit 300. Using the robustness level 303, the decoding and extracting unit 300 searches for the splitting point that was used by the encoding and embedding unit 200.

Using the knowledge of the splitting point, the wavelet coefficients I]_, I;?, ... , I_n ^are each split into a core part UJ_ and a residual part d_j_ such that

_OL+λ . j/

¹I = ^Ui z + dή

by a bit-plane splitting unit.

The decoding and extracting unit 300 generates the same sequence r = [q_, ∑2, ... , r_n] that was used by the encoding and embedding unit 200. A first extracting unit 305 extracts the embedded data by calculating the correlation between UJ_ and r_j_:

[0 if Z₁ < 0 1 ⁽i+l⁾m b-j = < where zi = — _/ uk x r-ή

¹ Il if Zi ≥ 0 ^x m ,^. ^{3 3}

The bits bj_ form the extracted data 306.

For reconstructing the original image data 201, a bit-plane merging unit 307 determines reconstructed wavelet coefficients I_j according to

¹J = u^ 2^U + dk

which, under the assumption that no distortion has occurred, are exactly the same as the original wavelet coefficients fed to the encoding and embedding unit 200. An inverse colour transform and wavelet transform unit 308 performs the inverse operation to the colour transform and wavelet transform unit 202 such that a decoded image, i.e. the reconstructed image data, is reconstructed from the reconstructed wavelet coefficients I_j .

Note that the extracted data 306 may also be determined from the residual parts dj_ by a second extracting unit 310 in an analogous way as by the first extracting unit 305.

Variants of the encoding and embedding unit 200 decoding and extracting unit 300 may be for example used for watermark embedding in a digital picture. In this case, their functionality is similar to the one described above and is explained in the following.

Corresponding to the robustness level 303, a watermark survival rate (WSR) is used. The WSR specifies the robustness of the watermark to be embedded in a digital image. The concept of WSR aims to make the watermarking tunable. Such a requirement is very important for security in a pervasive environment which contains many heterogeneous devices with varying computing resources and connected by different communication channels. Therefore, in such an environment, traditional security solutions which only provide yes/no answers cannot work well because different devices and communication channels may have different required security levels due to their limited computing power or their targeted applications. For example, sending a thumb-size grey-level image to a small portable device demands less security than sending a full-size color image to a desktop computer. Similar concepts have been proposed for other multimedia- related streaming applications (see [8], [9]) .

According to the method for watermark embedding described in the following, after embedding the watermark, a single watermarked JPEG2000 codestream (corresponding to the JPEG2000 codestream 213) is generated that supports lossy-to- lossless decoding. The watermarked JPEG2000 image is nearly rate-distortion optimized, compared with a normal JPEG2000 image. To reconstruct the original image, it is not necessary that the embedded watermark is extracted.

Analogously to the method explained with reference to fig.3,, wavelet coefficients are generated and the magnitude bits of the wavelet coefficients are cut into two portions. The watermark is embedded into the upper portion (core portion) while the lower portion (residual portion) is modified to compensate for the distortion introduced in the upper portion. Therefore, the decoder can recover the original image without the need to extract the watermark. The cutting point (splitting point) of the magnitude bits of the wavelet coefficients is controlled by the WSR. Given the WSR the cutting points of the wavelet coefficients may be accurately allocated using the EBCOT process (see [6]) .

Illustratively, the residual portion is modified to compensate for the distortion introduced by the watermark embedding into the core portion. As in the encoding and embedding unit 200, the core portion and the residual portion are concatenated together and are JPEG2000 encoded resulting in one single watermarked JPEG2000 bitstream that supports lossy-to-lossless decoding.

It is assumed that the watermark is a random noise sequence of real numbers W_j_ e W where i = 1, 2, ... , M and M is the length of the watermark sequence. The w^ are normally distributed with zero mean and unit variance. A spread spectrum watermarking technique is used, but other watermarking techniques may also be applicable.

Using 5x3 reversible wavelet transform (see [6]) the original image is decomposed N times such that multi-resolution representations or subbands of the image are obtained. These are denoted by HL_n, LH_n, HH_n and LL_n (where n = 1, 2, ... , N) . The subbands HL_n and LH_n are used to embed the watermark.

The specified WSR is used to search for the optimized truncation point by running the JPEG2000 EBCOT process (see [6]) . For the same WSR value, the truncation point may be different for different codeblocks. If necessary, the truncation point is adjusted to stay at the bit plane boundary (it may be set to the boundary, for example, when it would be higher than the number of bits) . The truncation point is used as the dividing point to split the magnitude bits of the wavelet coefficients. All bits of the wavelet coefficients above the truncation point from the upper portion (consisting of U bits) while the rest form the lower portion (consisting of L bits) . In particular, each wavelet coefficient Ij_ is divided into two numbers Uj_ and dj_ such that

Ii = Ui x 2^L + di , sign (ii) = sign (ui) = sign (di)

The value d_$_ that is added to Ui in order to embed the watermark is calculated according to

where α is a fixed scaling factor between 0 and 1 (for example α = 0.2) . By using Ui , a visual masking factor is implicitly utilized. For instance, for larger coefficients, the watermark will be embedded with more energy to enhance watermark robustness without degrading perceptual quality. However, adding d$_ to Ui may cause overflow or change of sign of Ui, which may affect the JPEG2000 coding efficiency

(performed later) . So, a new value d^ may be generated that does not cause any overflow or change of sign, d^ is an integer with the largest magnitude such that the following conditions

^ai ≤ sign (δj_) = sign Iδ/J

UJ_ + = sign (lj_)

Cl₁- -*i X2¹ < 2 ₍L+λ - 1, sign ldj_ - d^ x 2 I = sign (lj_)

are satisfied.

Once dj_' is determined, the watermark is embedded by

Uj_ = Uj_ + Oj_ .

The distortion introduced in this way is compensated by modifying dj_, such that dj_' = dj_ — øj_' x 2. After that, UJ_' has

U magnitude bits and d-;/ has L + λ magnitude bits where λ is the number of extra bits to accommodate overflow of dj_' . Lastly, the sign bit of Ij, ■ U magnitude bits of UJ_' and L + λ

magnitude bits of dj_' are concatenated as one coefficient Lj/ = UJ_' x 2 which is then encoded (for example according to the EBCOT encoding process) . The output after encoding is the watermarked JPEG2000 coded watermarked image.

For watermark detection, the reverse process of the watermark embedding, similarly, the magnitude bits of the wavelet coefficients are divided into two portions. The correlation between the watermark and either the upper portion or the lower portion of the wavelet coefficients is computed and compared with a threshold to decided whether the watermark has been embedded.

Given a watermarked JPEG2000 image, the detector still needs two other inputs for the watermark detection, the WSR and the watermark (given, as mentioned above, by the sequence WJ_) .

The WSR is used by the decoder to determine the dividing point for each coefficient from the JPEG2000 decoding process for recovering the original image and correctly correlating the watermark.

Each coefficient Ij_ received by the decoder (after decoding the received codestream) is divided into two numbers UJ_ and d_j_ such that Ii = UJ_ x 2^^κ + dj_ and

~k ^ "λ¹ sign(Ij_) = sign(ui) = sign(d^) .

Then, the correlation z between UJ_ and WJ_ is calculated according to

M

1 _Vi * = - Σ ^ui ^{x w}i

^M i=l

By comparing the correlation z with a predefined threshold Thr_z, the detector can decide whether the watermark sequence W is present in the image (see for example [10] ) .

According to the above, only UJ_ is used for watermark detection. The watermark detection based on dj_ can be performed in a similar way. When there is no distortion, i.e., UJ_ = U₁' and dj_ = dj_' , the recovered coefficient can be computed by

lV = Ui x 2^L + di = U₁' x 2^L + d/ = (ui + dΛ x2^L + Id₁ - d/ x2^Lj

= Ui x 2^U + dπ = I-;

The WSR is used to recover the original image and correctly correlate the watermarks by accurately allocating the dividing points for each coefficient. Therefore, whether the exact same dividing points as those used in course of embedding the watermark plays a key role. Experiments have shown that EBCOT works very well in accurately allocating the dividing points by testing various types of images, assuming no distortion is introduced into the coded watermarked bitstream. When there is an exception and EBCOT fails in accurately allocating the truncation points, this can be solved by inserting some special markers (>0xFF8F) into the bitstream to flag them. For the cases where some distortion exists, i.e., UJ_■ ≠ UJ_ and dj_ ≠ dj_ , though the original image can not be recovered (in its original quality)¹, the watermark may still be detected. Further, the watermark embedded in the upper portion and the lower portion may cancel itself out to a certain extent, such that the image quality is not significantly impaired by the embedding.

Experiments performed with a grey level, 1024x1280 pixel, 8bits/pixel image (JPEG2000 coded) show that the PSNR (peak signal to noise ratio) for the normal image is close to the watermarked image (the experiment was done using WSR=I.5bpp and 3.5bpp) . The only exception is when the truncation rate is close to the WSR. In this case, the image quality of the watermarked image is lower than that of the normal image. This is due to the absence of compensation from the lower portion, as all compensated bit planes have been completely truncated. Therefore, the watermarked image is nearly rate- distortion optimized compared to the normal image.

In the experiments, when the truncation rate is greater than 0.2bpp, the detection response for detecting the watermark is always above the corresponding threshold when the watermark is present, so the watermark is properly detected. When the truncation rate is very small (in this case <0.2bpp) the detection response drops drastically and the watermark is not detected. The detection response for the watermark with

WSR=I.5bpp drops much slower than with WSR=3.5bpp. This means that a watermark embedded with a smaller WSR is more robust.

When the detection responses are compared for different watermarks, of which one has been actually embedded, the right watermark can be effectively detected as experiments have shown. The detection response for the embedded watermark is smaller when WSR=I.5bpp compared to when WSR=3.5bpp. This is because UJ_ is smaller when WSR is smaller and thus the watermark is embedded with less energy which results in a smaller detection response.

The size of the watermarked image is about 2%-4% the size of the normal image.

Other examples for an encoding and embedding unit 102 and a decoding and extracting unit 107 are explained with reference to Fig.4 and Fig.5, respectively. In this case, the original multimedia data 101 are audio data to be encoded according to AAZ (Advanced Audio Zip) .

Fig.4 shows an encoding and embedding unit 400 according to an embodiment of the invention.

In this embodiment, original audio data 401 should be encoded and data to be embedded 402 should be embedded into the original audio data 401.

An integer MDCT (modified discrete cosine transform) unit 403 performs a modified discrete cosine transform such that the original audio data 401 is transformed into a vector of frequency domain coefficients c = [c]_, 02, ■■■ t C_n] . The frequency domain coefficients are non-uniformly quantized

(for example as described in [9]) by a quantizer 404 to form a vector of quantized coefficients 1 = [i]_, ±2r ••• /■ in] • This vector corresponds to the core part of the encoded audio ^■ data .

The data to be embedded 403 is supplied to an embedding unit 405 which embeds the data to be embedded 403 into the core part such that a vector of coefficients i' = [i]_, i2, ... , in] i^s formed. The embedding is done similar to the embodiment described above with reference to fig.2, wherein the vector i. corresponds to u and the vector i' corresponds to the vector u' . For embedding, the embedder 405 may take into account the results of a perceptual model unit 406 which processes the original audio data 401 according to a perceptual model. For example, the embedder 405 embeds the data to be embedded 402 such that the distortion introduced by the embedding is of low perceptual significance. An inverse quantizer 404 generates an inversely quantized coefficient vector c' from the vector JL. A substracting unit 407 calculates the difference between c' and the vector of frequency domain coefficients c . The result corresponds to the residual part and is denoted by e' = [ei, &2' •■• _< ^en] •

The vector i' is encoded by an entropy encoder 408 which generates the core layer (CL) according to AAZ and the vector e' is encoded by a BPGC (Bit Plane Golomb Coding) unit 409 which generates the Lossless Enhancement layer according to AAZ. The core layer and the lossless enhancement layer are multiplexed by a multiplexer 410 to form the AAZ audio stream 411.

The decoder and extractor corresponding to the encoding and embedding unit 400 is explained in the following with reference to fig.5.

Fig.5 shows a decoding and extracting unit 500 according to an embodiment of the invention.

The decoding and extracting unit 500 is supplied with an AAZ audio stream 501 corresponding to the AAZ audio stream 411 generated by the encoding and embedding unit 400. The AAZ audio stream 501 is de-multiplexed by a de-multiplexer 502 into a core layer and a lossless enhancement layer. The core layer is entropy decoded by an entropy decoder 503 to form a coefficient vector i' = [i]_, i*?, ■•• _r in] (called core part) and the lossless enhancement layer is BPGC decoded by a BPGC decoding unit 504 to generate a coefficient vector e' = [e]_, e2, ... , e_n] (called residual part) . The core part is de-quantized by a de-quantizer 505 and the result is added to the residual part e' = [β]_, e2, ... , e_n] by an adding unit 506 to form the reconstructed frequency domain coefficients c = [c]_, C2f ... , c_n] . The reconstructed frequency domain coefficients c =

C2, ■•• _r C_n] are processed by an inverse integer MDCT unit 507 to generate the decoded audio data 508 corresponding to the original audio data 401.

An extractor 509 extracts the data embedded in the AAZ audio stream 501 by processing the vector i' = [i_]_, i^, ... , i_n] as described above with reference to fig.3 (extracting data from the vector u' ) . The result is extracted data 510 corresponding to the data to be embedded 402.

In this document, the following publications are cited:

[1] P.-C. Su, H. -J. M. Wang and C-C. Jay Kuo, "An Integrated Approach to Image Watermarking and JPEG-2000 Compression", Journal of VLSI Signal Processing, vol 27, pp.35-53, 2001

[2] R. Grosbois, T. Ebrahimi, "Watermarking in the JPEG2000 domain", MMSP2001, October 3-5, 2001

[3] W. Zeng and S. Lei, "Transform Domain Perceptual Watermarking with Scalable Visual Detection - A Proposal for JPEG2000", ISO/IEC JTC/SC29/WG1 N759, March 1998

[4] M. Goljan, J. Fridrich and R. Du, "Distortion-Free Data Embedding For Images", in 4th Information Hiding Workshop, LNCS vol. 2137, Springer-Verlag, New York, 2001, pp. 27-41 [5] Z. Ni, Y. Q. Shi, N. Ansari, W. Su, Q. Sun and X. Lin, - "Robust Lossless Image Data Hiding", submitted to ICME 2004

[6] "JPEG2000 Part I Final Draft International Standard", ISO/IEC JTC 1/SC29/WG1 N1876, August 2000

[7] R. Yu, X. Lin, S. Rahardja and C. C. Ko, "A Scalable Lossy To Lossless Audio Coder For MPEG-4 Lossless Audio Coding", ICASSP 2004

[8] Q. Sun, S.-F. Chang, M. Kurato and M. Suto, "A Quantitative Semi-Fragile JPEG2000 Image Authentication System", ICIP 2002

[9] C. S. Ong, K. Nahrstedt and W. Yuan, "Quality of

Protection for Mobile Multimedia Applications", ICME 2003

[10] H. Inoue, A. Miyazaki, T. Katsura, "An Image Watermarking Method Based on the Wavelet Transform", ICIP, 1999

Claims

1. A method for embedding first data into second data comprising - transforming the first data according to a domain transformation to generate at least one transformation coefficient

- splitting the at least one transformation coefficient into a first part comprising a first plurality of bits and into a second part comprising a second plurality of bits according to a splitting point specifying a bit position

- modifying the first plurality of bits and the second plurality of bits based on the first data such that the at least one coefficient can be calculated from the modified first plurality of bits and the modified second plurality of bits.

2. Method according to claim 1, wherein when the modified first plurality of bits and the modified second plurality of bits are combined to form the at least one coefficient, the modification of the first plurality of bits and the modification of the second plurality of bits are cancelled out.

3. Method according to claim 1, wherein from the first data, at least one modification value is determined and the first plurality of bits and the second plurality of bits are modified based on the at least one modification value.

4. Method according to claim 3, wherein for modifying the first plurality of bits, the at least one modification value is added to the first part.

5. Method according to claim 3, wherein for modifying the second plurality of bits, the at least one modification value is bit-shifted and substracted from the second part.

6. Method according to claim 5, wherein the at least one modification value is bit-shifted according to the splitting point.

7. Method according to claim 1, further comprising combining the modified first part and the modified second part to form a modified transformation coefficient.

8. Method according to claim 7, further comprising encoding the modified transformation coefficient.

9. Method according to claim I₁ wherein the second data are media data.

10. Method according to claim 9, wherein the media data are video data, audio data or image data.

11. Method according to claim 1, wherein the first data are digital watermark data.

12. Method according to claim 1, wherein the splitting point is determined according to the JPEG2000 EBCOT process.

13. A system for embedding first data into second data comprising - a transforming unit configured to transform the first data according to a domain transformation to generate at least one transformation coefficient - a splitting unit configured to split the at least one transformation coefficient into a first part comprising a first plurality of bits and into a second part comprising a second plurality of bits according to a splitting point

5 specifying a bit position

- a modifying unit configured to modify the first plurality of bits and the second plurality of bits based on the first data such that the at least one coefficient can be calculated from the modified first plurality of bits and the modified

.0 second plurality of bits.

14. A computer program product, which, when executed by a computer, makes the computer perform a method for embedding first data into second data comprising

.5 - transforming the first data according to a domain transformation to generate at least one transformation coefficient

- splitting the at least one transformation coefficient into a first part comprising a first plurality of bits and into a

!0 second part comprising a second plurality of bits according to a splitting point specifying a bit position

- modifying the first plurality of bits and the second plurality of bits based on the first data such that the at least one coefficient can be calculated from the modified

!5 first plurality of bits and the modified second plurality of bits.

15. A method for detecting whether first data are embedded into second data, wherein the second data are given by at

SO least one transformation coefficient comprising

- determining a correlation value specifying the correlation between the first plurality of bits or the second plurality

5 of bits with the first data

- deciding based on the correlation value if the first data are embedded in the second data.

16. A system for detecting whether first data are embedded .0 into second data, wherein the second data are given by at least one transformation coefficient comprising

- a splitting unit configured to split the at least one transformation coefficient into a first part comprising a

.5 first plurality of bits and into a second part comprising a second plurality of bits according to a splitting point specifying a bit position

- a determining unit adapted to determine a correlation value specifying the correlation between the first plurality of

!0 bits or the second plurality of bits with the first data

- a deciding unit configured to decide based on the correlation value if the first data are embedded in the second data.

15 17. A computer program product, which, when executed by a computer, makes the computer perform a method for detecting whether first data are embedded into second data, wherein the second data are given by at least one transformation coefficient comprising

SO - splitting the at least one transformation coefficient into a first part comprising a first plurality of bits and into a second part comprising a second plurality of bits according to a splitting point specifying a bit position - determining a correlation value specifying the correlation between the first plurality of bits or the second plurality of bits with the first data

- deciding based on the correlation value if the first data 5 are embedded in the second data.

18. A method for reconstructing second data into which first data have been embedded, wherein the second data into which the first data are embedded are given by at least one

LO transformation coefficient comprising

L5 - combining the first part and the second part to generate an original transformation coefficient.

19. A system for reconstructing second data into which first data have been embedded, wherein the second data into which

20 the first data are embedded are given by at least one transformation coefficient comprising

- a splitting unit configured to split the at least one transformation coefficient into a first part comprising a first plurality of bits and into a second part comprising a

25 second plurality of bits according to a splitting point specifying a bit position

- a combining unit adapted to combine the first part and the second part to generate an original transformation coefficient.

30

20. A computer program product, which, when executed by a computer, makes the computer perform a method for reconstructing second data into which first data have been embedded, wherein the second data into which the first data are embedded are given by at least one transformation coefficient comprising

- combining the first part and the second part to generate an original transformation coefficient.