Digital watermarking system using scrambling method

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a digital watermarking technology, and it particularly relates to a method for embedding a digital watermark and an encoding apparatus and a decoding apparatus using the same method.

2. Description of the Related Art

The number of Internet users has rapidly increased in recent years and we are now entering the age of the broadband, or a new stage in the utilization of the Internet.

Since communication bandwidth has greatly expanded in broadband communication, the distribution of items containing large bodies of data such as audio, still image, and video can be enjoyed with ease. When the distribution of such digital items becomes popular, a highly efficient method of protecting the copyright of their contents will be required.

In the present situation, the copyright is not protected well so that users can easily copy such contents distributed via the Internet. Therefore, technology for embedding information on the originator of the content and the user into the content as a digital watermark has been developed. By using this watermarking technology, it becomes possible to extract the digital watermark from the content distributed via the network, and thereby detect an illegal use and track the distribution route of an illegal copy.

A digital watermark is embedded in the content data in a way that the watermark is perceptually invisible to users in order to prevent malicious attacks. However, the content data will be subject to various operations during the distribution and utilization, for instance, signal processing such as compression, various types of filtering, modification by users, or attacks on the watermark information. In such processes, a part of the digital watermark may be possibly altered or removed. Therefore the digital watermark should be robust enough to withstand such operations.

Various digital watermarking techniques have been developed in order to improve the robustness of digital watermarks. For instance, Japanese Patent Application Laid-Open 2000-13587 discloses a method for embedding a digital watermark with a high level of robustness while providing a degree of freedom for the process of embedding the digital watermark information. Such a digital watermarking technique adopts a method for embedding a digital watermark in high frequency components such as an edge or a region with a significant change in an image texture, according to the characteristics of the human visual system, and therefore the technique depends to a large degree on the individual content data and has limitations on the generality and flexibility so as to be difficult to improve the robustness of the embedded watermark against various operations which might be carried out on the contents data.

SUMMARY OF THE INVENTION

The present invention has been made based on these considerations, and an object thereof is to provide a digital watermarking technology which can embed a watermark with a high degree of robustness and reduce the detection error rate of the embedded watermark.

According to one aspect of the present invention, a digital watermark embedding method is provided. The method comprises scrambling a digital watermark to be embedded in host data and thereby generating a plurality of candidate watermarks, and evaluating the robustness of the respective candidate watermarks when the respective candidate watermarks are embedded in the host data, and obtaining watermarked host data in which one of the candidate watermarks is embedded with a high degree of robustness. According to this method, the watermark data can be converted to a data sequence with a high level of robustness depending on the host data before being embedded in the host data, and therefore the detection error rate in extracting the digital watermark can be reduced.

The host data are original data in which the digital watermark is to be embedded, for instance, data such as still image, video, audio or the like. The digital watermark to be embedded includes identification information, originator information, user information on the original data, and so on. Furthermore, a digest on the host data, that is data plainly representing the characteristics of the host data, can be embedded as the digital watermark. The robustness of the digital watermark means to what extent the digital watermark can survive any kinds of operations against the watermarked host data, for instance, signal processing such as compression or filtering.

The process of embedding the digital watermark utilizes a one-to-many mapping procedure which associates the original digital watermark with a plurality of candidate by converting the digital watermark in many different ways. The process of extracting the digital watermark includes the inverse mapping procedure and thereby obtains the original digital watermark from the scrambled watermark data. For this purpose, the extracting process may utilize a table which associates a plurality of the candidate watermarks with the original digital watermark. Moreover, the embedding process may utilize a scrambling function for generating a plurality of the candidate watermarks using a predefined initial value. In this case, the extracting process descrambles the extracted watermark using the same initial value and scrambling function as used in the scrambling.

According to another aspect of the present invention, a digital watermark embedding method is also provided. The method comprises generating a plurality of candidate locations of host data in which a digital watermark is embedded, and evaluating the robustness of the watermark when the watermark is embedded in the respective candidate locations, and obtaining watermarked host data in which the watermark is embedded with a high degree of robustness from among the candidate locations. According to this method, the digital watermark can robustly be embedded in a location found in the host data.

According to still another aspect of the present invention, an encoding apparatus is provided. The apparatus comprises a scrambling unit which scrambles a digital watermark to be embedded in host data and generates a plurality of candidate watermarks, an embedding unit which embeds the respective candidate watermarks in the host data and generates a plurality of candidate watermarked host data, an evaluating unit which evaluates the robustness of the respective candidate watermarks hidden in the respective candidate watermarked host data, and a selecting unit which selects and outputs one of the plurality of the candidate watermarked host data according to its evaluated robustness.

According to still another aspect of the present invention, an encoding apparatus is also provided. The apparatus comprises a location information generating unit which generates a plurality of candidate locations of host data in which a digital watermark is embedded, an embedding unit which embeds the watermark in the respective candidate locations of the host data and generates a plurality of candidate watermarked host data, an evaluating unit which evaluates the robustness of the digital watermark hidden in the respective candidate watermarked host data, and a selecting unit which selects and outputs one of the plurality of the candidate watermarked host data according to its evaluated robustness.

The scrambling unit may scramble the watermark by an operation using the identification data. This operation may be an operation for converting the watermark by a scrambling polynomial or other conversion formulas. The scrambling unit may scramble the watermark by convoluting the watermark using the identification data on the candidate watermark. By this convolutional operation, a variety of watermark candidates can be generated. This scrambling method may be used for generating the candidate watermark locations. Moreover, the plurality of the candidate locations may be generated by referring to a table which associates the identification data on each of the candidate locations with a random watermark location.

The scrambling unit may insert identification data necessary for descrambling in the candidate watermark generated by scrambling. After the scrambling by the scrambling unit, the identification data necessary for descrambling may be retained as a secret key. The identification data may be information for identifying the scrambling method, for instance, information for identifying the form of scrambling or scrambling/descrambling function. The identification data may contain the initial data necessary for descrambling. In this case, the decoding process can descramble the watermark using this identification data after extracting the scrambled watermark and thereby obtain the original watermark.

In any aspect of the above-mentioned encoding apparatus, the evaluating unit may evaluate the robustness by calculating signal-to-noise ratio (SNR) where the host data are regarded as a distortion in the watermark. Especially in the case of soft-input error correction code such as a turbo code, bit error rate (BER) can be reduced by selecting one of the candidates on criteria based on the SNR. The evaluating unit may evaluate the robustness by comparing a watermark decoded by making a hard decision with an actually embedded watermark. For this comparison, Hamming distance or Euclidean distance between the actual embedded watermark and the extracted watermark based on the hard decision may be evaluated. In this case, the larger the distance becomes, the larger the error rate becomes, and therefore the level of the robustness is judged to be low. According to this criterion, the candidate watermark which has the largest number of bits to be correctly decoded by the hard decision is selected. Especially in the case of a hard-input error correction code, the BER can be reduced by selecting the candidate according to the method in which such a hard decision result is compared with the actual embedded watermark.

The evaluating unit may evaluate the robustness after a utility operation is conducted on the watermarked host data.

The utility operation is, for instance, signal processing such as compression, various filtering or the like, and geometric transformation such as scaling, rotation or the like. The evaluating unit may evaluate the robustness taking account of quantization errors caused by compressing the watermarked host data. In the case of evaluating the robustness on the basis of the SNR, the variance of a watermark extracted from the watermarked host data modified by the utility operation for the actually embedded watermark may be evaluated.

According to still another aspect of the present invention, a decoding apparatus is provided. The apparatus comprises an extracting unit which extracts a scrambled digital watermark from host data in which the digital watermark is supposed to have been embedded, and a descrambling unit which descrambles the scrambled watermark by performing convolution on the watermark using the identification data on the watermark. The descrambling unit may extract the identification data from a part of the scrambled watermark.

According to still another aspect of the present invention, a decoding apparatus is also provided. The apparatus comprises a location information generating unit which generates a plurality of candidate locations of host data in which a digital watermark is supposed to have been embedded, an extracting unit which extracts a plurality of candidate watermarks embedded in the host data according to the respective candidate locations, a checking unit which checks the plurality of the extracted candidate watermarks with an anticipated watermark, and a selecting unit which selects and outputs one of the candidate watermarks according to a checking result produced by the checking unit.

According to still another aspect of the present invention, a data structure readable and usable by a computer is provided. The data structure is a host data structure in which a digital watermark is hidden. The host data structure comprises an embedded watermark which is scrambled by a predefined scrambling method and identification data necessary for descrambling the scrambled watermark which are incorporated as a part of the scrambled watermark.

According to still another aspect of the present invention, a computer program executable by a computer is provided. The program comprises generating a plurality of candidate watermarks by scrambling a digital watermark to be embedded in host data, generating a plurality of candidate watermarked host data by embedding the respective candidate watermarks in the host data, evaluating the robustness of the respective candidate watermarks hidden in the respective candidate watermarked host data, and selecting one of the plurality of the candidate watermarked host data according to its evaluated robustness.

According to still another aspect of the present invention, a computer program is also provided. The program comprises generating a plurality of candidate locations of host data in which a digital watermark is embedded, generating a plurality of candidate watermarked host data by embedding the watermark in the respective candidate locations of the host data, evaluating the robustness of the watermark hidden in the respective candidate watermarked host data, and selecting one of the plurality of the candidate watermarked host data according to its evaluated robustness.

Moreover, any arbitrary replacement or substitution of the above-described structural components and the steps, expressions replaced or substituted in part or whole between a method and an apparatus as well as addition thereof, and expressions changed to a system, a computer program, a data structure, a storage medium, a transmission medium or the like are all effective as and are encompassed by the present invention.

This summary of the invention does not necessarily describe all necessary features, so that the invention may also be a sub-combination of these described features.

BRIEF DESCRIPTION OF THE DRAWINGS

<figref idref="DRAWINGS">FIG. 1</figref> shows a structure of an encoding apparatus according to Embodiment 1.

<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram of the modifier and the embedder of <figref idref="DRAWINGS">FIG. 1</figref>.

<figref idref="DRAWINGS">FIG. 3</figref> is a block diagram of a decoding apparatus according to Embodiment 1.

<figref idref="DRAWINGS">FIG. 4</figref> shows a relationship between an original watermark and L kinds of scrambled watermarks.

<figref idref="DRAWINGS">FIG. 5</figref> explains a convolutional operation during an encoding process.

<figref idref="DRAWINGS">FIG. 6</figref> explains a convolutional operation in a decoding process.

<figref idref="DRAWINGS">FIGS. 7A and 7B</figref> explain how a scrambled watermark is embedded.

<figref idref="DRAWINGS">FIG. 8</figref> is a flowchart showing a watermark embedding procedure employed by the encoding apparatus of <figref idref="DRAWINGS">FIG. 1</figref>.

<figref idref="DRAWINGS">FIG. 9</figref> is a flowchart showing another watermark embedding procedure employed by the encoding apparatus of <figref idref="DRAWINGS">FIG. 1</figref>.

<figref idref="DRAWINGS">FIG. 10</figref> is a block diagram of an encoding apparatus according to Embodiment 2.

<figref idref="DRAWINGS">FIG. 11</figref> is a block diagram of the modifier and the embedder of <figref idref="DRAWINGS">FIG. 10</figref>.

<figref idref="DRAWINGS">FIG. 12</figref> is a block diagram of an encoding apparatus according to Embodiment 3.

<figref idref="DRAWINGS">FIG. 13</figref> is a block diagram of the location generator and the embedder of <figref idref="DRAWINGS">FIG. 12</figref>.

<figref idref="DRAWINGS">FIG. 14</figref> is a block diagram of a decoding apparatus according to Embodiment 3.

<figref idref="DRAWINGS">FIG. 15</figref> is a block diagram of a turbo encoder in an encoding apparatus according to Embodiment 4.

<figref idref="DRAWINGS">FIG. 16</figref> is a block diagram of a turbo decoder in a decoding apparatus according to Embodiment 4.

DETAILED DESCRIPTION OF THE INVENTION

The invention will now be described by reference to the preferred embodiments. This does not intend to limit the scope of the present invention, but to exemplify the invention.

Embodiment 1

<figref idref="DRAWINGS">FIG. 1</figref> shows a structure of an encoding apparatus <b>10</b> according to Embodiment 1. This structure can be realized by hardware, such as a CPU in arbitrary computers, memory and other LSIs, or by software, such as a program or the like loaded in the memory, which has functions for embedding digital watermarks. In the figure, functions, which are realized by combinations of such hardware and software, are shown by blocks. It should be understood by those skilled in the art that these functional blocks can be realized by various modes such as hardware only, software only or a combination thereof.

The encoding apparatus <b>10</b> performs a process for embedding watermark information I in host data V and outputs watermarked host data W. The host data V are, for instance, media data such as audio, still image, video or the like.

The watermark information I, for instance, includes copyright information such as identification, creator, or user information on the host data V, authentication information for detecting attacks on the host data V, timestamp information, and so forth.

An encryptor <b>12</b> encrypts the watermark information I to be embedded in the host data V using a secret key K and outputs a watermark X. When this encryption function is denoted by f₀, the encryption process can be represented by a transformation formula X=f₀(I, K). If the watermark information I does not need to be encrypted, the configuration of the encryptor <b>12</b> may be omitted.

A modifier <b>14</b> scrambles the watermark X using the host data V and outputs a scrambled watermark X′. When this scrambling function is denoted by f₂, the scrambling process can be represented by a transformation formula X′=f₂(X, V).

An embedder <b>16</b> embeds the scrambled watermark X′ in the host data V using the secret key K and outputs watermarked host data W. When the watermarking function is denoted by f₁, the watermarking process can be represented by a transformation formula W=f₁(V, X′, K). If a watermarking method which does not depend on the secret key K is applied, the process is represented by W=f₁(V, X′)

The modifier <b>14</b> and the embedder <b>16</b>, in cooperation with each other, generate a plurality of the scrambled watermarks X′ and embed each of them in the host data V, and thereby generate a plurality of candidate watermarked host data W and selects one of the candidates.

<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram of the modifier <b>14</b> and the embedder <b>16</b>. L multiplexers <b>20</b> generate L kinds of bit sequences X_bby adding initial data C₀to C_L−1to the head of the watermark X. L scramblers <b>22</b> scramble the L kinds of bit sequences respectively and generate L kinds of scrambled watermark X′. L error correction coders (ECCs) <b>24</b> generate watermarks X′_cby adding the parity bits to the respective scrambled watermarks X′_b. The ECC <b>24</b> is an option for improving the detection rate of the watermark bits and therefore this configuration may be omitted according to the different applications.

L embedders <b>26</b> embed the L kinds of scrambled watermarks X′_cin the host data V respectively and generate L kinds of candidate watermarked host data W. L SNR calculators <b>28</b> each evaluate the robustness of the watermark X hidden in the L kinds of candidate watermarked host data W.

A selector <b>30</b> selects one of the L kinds of candidate watermarked host data W for which the evaluated value of the robustness is the best, and outputs it as watermarked host data W.

<figref idref="DRAWINGS">FIG. 3</figref> shows a block diagram of a decoding apparatus <b>40</b> according to Embodiment 1. The watermarked host data W in which a digital watermark has been embedded by the encoding apparatus <b>10</b> is distributed via a network and utilized in a computer. During these processes, the watermarked host data W are subject to operations such as compression and malicious attacks. In the case of image data, the data are subject to utility operations, for instance, signal processing such as JPEG compression, filtering, quantization, or color correction, or geometric transformation such as scaling, cropping, rotating, or parallel shifting, and also subject to illegal attacks such as removing or altering the digital watermark. Transformation by such operations adds a noise N to the watermarked host data W and the watermarked host data W with the noise N added is called a watermarked host signal W′. The decoding apparatus <b>40</b> performs a process for extracting the watermark X from the noisy watermarked host signal W′.

An extractor <b>42</b> extracts a watermark X′_cfrom the watermarked host signal W′ using the secret key K. An ECC decoder <b>44</b> corrects errors using the parity bits within the watermark X′_cand thereby generates a watermark X′_b. A descrambler <b>46</b> descrambles the error corrected watermark X′_band thereby outputs a watermark X_b. The watermark X_bis further decoded by the secret key K and the original watermark information I is obtained, although the last process is not shown in the figure.

The procedures of embedding and extracting a watermark by the above-mentioned configuration of the encoding apparatus <b>10</b> and the decoding apparatus <b>40</b> are now explained. <figref idref="DRAWINGS">FIG. 8</figref> is a flowchart showing the watermark embedding procedure employed by the encoding apparatus <b>10</b>. <figref idref="DRAWINGS">FIG. 4</figref> to <figref idref="DRAWINGS">FIGS. 7A and 7B</figref> are referred to in the explanation of the flowchart. The multiplexer <b>20</b> inserts L kinds of initial data in the head of the watermark X encrypted by the encryptor <b>12</b> and thereby generates L kinds of code sequences (S<b>10</b>), and the scrambler <b>22</b> scrambles these code sequences and thereby generates L kinds of scrambled watermarks X′ (S<b>12</b>).

<figref idref="DRAWINGS">FIG. 4</figref> shows a relationship between the watermark X and the L kinds of scrambled watermarks X′. As identification data ID[0] to ID[L−1], r-bit redundant words are added to the head of n-bit watermark X and thus the L kinds of candidate watermarks are generated. At most 2^rkinds of candidates are generated. The bit sequences of the watermark X within the respective candidates are scrambled by a scrambling method that is described below.

As one of the scrambling methods, a guided scrambling (GS) technique, usually used for digital modulation for data transmission and magnetic recording, is adopted. This guided scrambling method generates L kinds of encoded sequences from a data sequence of a definite block length, and treats the generated sequences as candidates for an encoded sequence to be transmitted next. The method selects one which is most suitable to the characteristics of the transmission medium and transmits the selected one as a final encoded sequence.

By this method, a variety of candidates for the encoded sequence can be easily generated.

The multiplexer <b>20</b> and the scrambler <b>22</b> of the encoding apparatus <b>10</b> together function as a GS encoder. The GS encoder augments an n-bit source sequence D(x) with L kinds of r-bit redundant words c_i(i=0, . . . , L−1) to generate L augmented source sequence c_ixⁿ+D(x). The length of the augmented sequence is (n+r) bits. Next, the augmented source sequences are divided by the scrambling polynomial S(x) of degree N to obtain quotients T_i(x) &lt;br /&gt;<i>T</i>_i(<i>x</i>)=<i>Q</i>_s(x)[(<i>c</i>_i<i>x</i>ⁿ<i>+D</i>(<i>x</i>))<i>x</i>^N]  (1)&lt;br /&gt; where Q_a[b] represents the quotient of a polynomial b divided by a polynomial a. The quotient set {T₀(x), . . . , T_L−1(x)} is a set of candidate scrambled code sequences. For each candidate, performance when the code sequence is really used is evaluated and the one for which the evaluated value is the best is selected as the final code sequence.

In decoding, the descrambler <b>46</b> of the decoding apparatus <b>40</b> functions as a GS decoder. The GS decoder multiplies the code sequence by S(x) and discards the lower n bits and upper r bits to obtain the original source sequence D(x).

The case in which the scrambling polynomial S(x)=x^r+1 is applied, is herein explained. When r is a positive number such that n mod r=0, the expression (1) can be represented by a convolutional operation as follows. &lt;br /&gt;<i>t</i>_j<i>=d</i>_j<i>⊕c</i>_i(<i>j=</i>0)&lt;br /&gt;<i>t</i>_j<i>=d</i>_j<i>⊕t</i>_j−1(<i>j=</i>1<i>, . . . , n/r−</i>1)&lt;br /&gt; where i=0, . . . , L−1 and d_jrepresents a bit sequence obtained from the original source sequence D(x) being segmented by every r bit, and t_jrepresents a bit sequence obtained from the code sequence T_i(x) being segmented by every r bit. The r-bit redundant word c_iis at the head of T_i(x). Herein ⊕ denotes an exclusive-OR operation.

<figref idref="DRAWINGS">FIG. 5</figref> explains the convolutional operation during the encoding process. For instance, let n be 6 and r be 2. The redundant word c₀=(0,0) is added to D(x)=(1,0,1,0,0,1) and then a converted code sequence T₀(x) is generated. By the above-mentioned convolutional operation in the encoding, t₀=d₀⊕c₀=(1,0)⊕(0,0)=(1,0), t₁=d₁⊕t₀=(1,0) ⊕(1,0)=(0,0), and t₂=d₂⊕t₁=(0,1)⊕(0,0)=(0,1), and thus the converted code sequence T₀=(0,0,1,0,0,0,0,1) is obtained. It is to be noted that the head 2-bit data of the converted code sequence T₀is the redundant word c₀.

Likewise, for the redundant word c₁=(0,1), c₂=(1,0), c₃=(1,1), the converted code sequences T₁=(0,1,1,1,0,1,0,0), T₂=(1,0,0,0,1,0,1,1), and T₃=(1,1,0,1,1,1,1,0) are obtained, respectively.

In decoding, the original source sequence D(x) is obtained by the following convolutional operation. &lt;br /&gt;<i>d</i>_j<i>=t</i>_j<i>⊕c</i>_i(<i>j=</i>0)&lt;br /&gt;<i>d</i>_j<i>=t</i>_j<i>⊕t</i>_j−1(<i>j=</i>1<i>, . . . , n/r−</i>1)

<figref idref="DRAWINGS">FIG. 6</figref> explains the convolutional operation in the decoding process. When the converted code sequence T₀=(0,0,1,0,0,0,0,1) is given in the above-mentioned example, the redundant word c₀=(0,0) is obtained from the head 2-bit data of the sequence. By the above-mentioned convolutional operation in the decoding, d₀=t₀⊕c₀=(1,0)⊕(0,0)=(1,0), d₁=t₁⊕t₀=(0,0)⊕(1,0)=(1,0), and d₂=t₂⊕t₁=(0,1)⊕(0,0)=(0,1). For the other converted code sequences T₁, T₂and T₃, the original source code D(x) is obtained likewise by this convolutional operation.

Referring to <figref idref="DRAWINGS">FIG. 8</figref> again, the L kinds of watermarks X′ generated by the scrambler <b>22</b> are augmented with parity bits by the ECC <b>24</b> and then the L kinds of parity added watermarks are embedded into the host data V by the embedder <b>26</b> (S<b>14</b>).

<figref idref="DRAWINGS">FIGS. 7A and 7B</figref> explain how the scrambled watermark X′ is embedded. Let L kinds of scrambled watermark X′ be x⁰, x¹, . . . , x^L−1. The bit sequence of each candidate watermark is represented as follows. The head r-bit data indicate the identification data. Hereinafter the bit “0” after the scrambling is replaced by “−1” and then the subsequent processes are conducted.

<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mtable><mtr><mtd><mrow><msup><mi>x</mi><mn>0</mn></msup><mo>=</mo>&lt;mi /&gt;<mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mo>-</mo><mn>1</mn></mrow><mo>,</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>…</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>,</mo><mrow><mo>-</mo><mn>1</mn></mrow><mo>,</mo><mrow><mo>-</mo><mn>1</mn></mrow><mo>,</mo><msubsup><mi>x</mi><mn>0</mn><mn>0</mn></msubsup><mo>,</mo><msubsup><mi>x</mi><mn>1</mn><mn>0</mn></msubsup><mo>,</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>…</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>,</mo><msubsup><mi>x</mi><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow><mn>0</mn></msubsup></mrow><mo>}</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msup><mi>x</mi><mn>1</mn></msup><mo>=</mo>&lt;mi /&gt;<mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mo>-</mo><mn>1</mn></mrow><mo>,</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>…</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>,</mo><mrow><mo>-</mo><mn>1</mn></mrow><mo>,</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mn>1</mn><mo>,</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msubsup><mi>x</mi><mn>0</mn><mn>1</mn></msubsup><mo>,</mo><msubsup><mi>x</mi><mn>1</mn><mn>1</mn></msubsup><mo>,</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>…</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>,</mo><msubsup><mi>x</mi><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow><mn>1</mn></msubsup></mrow><mo>}</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mi>…</mi><mo>⁢</mo>&lt;mi /&gt;</mrow></mtd></mtr><mtr><mtd><mrow><msup><mi>x</mi><mrow><mi>L</mi><mo>-</mo><mn>1</mn></mrow></msup><mo>=</mo>&lt;mi /&gt;<mo>⁢</mo><mrow><mo>{</mo><mrow><mn>1</mn><mo>,</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>…</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>,</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mn>1</mn><mo>,</mo><mn>1</mn><mo>,</mo><msubsup><mi>x</mi><mn>0</mn><mrow><mi>L</mi><mo>-</mo><mn>1</mn></mrow></msubsup><mo>,</mo><mrow><msubsup><mi>x</mi><mn>1</mn><mrow><mi>L</mi><mo>-</mo><mn>1</mn></mrow></msubsup><mo> </mo></mrow><mo>,</mo><mi>…</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>,</mo><msubsup><mi>x</mi><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow><mrow><mi>L</mi><mo>-</mo><mn>1</mn></mrow></msubsup></mrow></mrow></mrow></mtd></mtr></mtable></math></maths>

A pair of sample sets (V⁺, V⁻) is defined as follows.

The samples in which an n-bit watermark is embedded are selected from the host data V. The sample sets V⁺ and V⁻ each contain n elements. It is to be noted that the host data V are represented by a set of samples over spatial domain, temporal domain, or frequency domain, for instance, the samples processed by Discrete Cosine Transform, Discrete Fourier Transform or Discrete Wavelet Transform.

<maths id="MATH-US-00002" num="00002"><math overflow="scroll"><mtable><mtr><mtd><mrow><msup><mi>V</mi><mo>+</mo></msup><mo>=</mo>&lt;mi /&gt;<mo>⁢</mo><mrow><mo>{</mo><mrow><msubsup><mi>v</mi><mn>0</mn><mo>+</mo></msubsup><mo>,</mo><msubsup><mi>v</mi><mn>1</mn><mo>+</mo></msubsup><mo>,</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>…</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>,</mo><msubsup><mi>v</mi><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow><mo>+</mo></msubsup></mrow><mo>}</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msup><mi>V</mi><mo>-</mo></msup><mo>=</mo>&lt;mi /&gt;<mo>⁢</mo><mrow><mo>{</mo><mrow><msubsup><mi>v</mi><mn>0</mn><mo>-</mo></msubsup><mo>,</mo><msubsup><mi>v</mi><mn>1</mn><mo>-</mo></msubsup><mo>,</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>…</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>,</mo><msubsup><mi>v</mi><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow><mo>-</mo></msubsup></mrow><mo>}</mo></mrow></mrow></mtd></mtr></mtable></math></maths>&lt;br /&gt; where each subset v⁺_iand v⁻_i, an element of the sample sets V⁺ and V⁻, respectively, is composed of m samples of the host data V.

<maths id="MATH-US-00003" num="00003"><math overflow="scroll"><mtable><mtr><mtd><mrow><msubsup><mi>v</mi><mi>i</mi><mo>+</mo></msubsup><mo>=</mo><mrow><mo>{</mo><mrow><msubsup><mi>v</mi><mrow><mi>i</mi><mo>,</mo><mn>0</mn></mrow><mo>+</mo></msubsup><mo>,</mo><msubsup><mi>v</mi><mrow><mi>i</mi><mo>,</mo><mn>1</mn></mrow><mo>+</mo></msubsup><mo>,</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>…</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>,</mo><msubsup><mi>v</mi><mrow><mi>i</mi><mo>,</mo><mrow><mi>m</mi><mo>-</mo><mn>1</mn></mrow></mrow><mo>+</mo></msubsup></mrow><mo>}</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msubsup><mi>v</mi><mi>i</mi><mo>-</mo></msubsup><mo>=</mo><mrow><mo>{</mo><mrow><msubsup><mi>v</mi><mrow><mi>i</mi><mo>,</mo><mn>0</mn></mrow><mo>-</mo></msubsup><mo>,</mo><msubsup><mi>v</mi><mrow><mi>i</mi><mo>,</mo><mn>1</mn></mrow><mo>-</mo></msubsup><mo>,</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>…</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>,</mo><msubsup><mi>v</mi><mrow><mi>i</mi><mo>,</mo><mrow><mi>m</mi><mo>-</mo><mn>1</mn></mrow></mrow><mo>-</mo></msubsup></mrow><mo>}</mo></mrow></mrow></mtd></mtr></mtable></math></maths>

The candidate watermarks x^k(k=0, . . . , L−1) are embedded into the pair of the sample sets (V⁺, V⁻) as follows and thus L kinds of candidate watermarked host data W^kare generated.

<maths id="MATH-US-00004" num="00004"><math overflow="scroll"><mtable><mtr><mtd><mrow><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mo>+</mo><mi>k</mi></mrow></msubsup><mo>=</mo>&lt;mi /&gt;<mo>⁢</mo><mrow><msubsup><mi>v</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>+</mo></msubsup><mo>+</mo><mrow><msubsup><mi>α</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>+</mo></msubsup><mo>⁢</mo><msubsup><mi>x</mi><mi>i</mi><mi>k</mi></msubsup></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mo>-</mo><mi>k</mi></mrow></msubsup><mo>=</mo>&lt;mi /&gt;<mo>⁢</mo><mrow><msubsup><mi>v</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>-</mo></msubsup><mo>-</mo><mrow><msubsup><mi>α</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>-</mo></msubsup><mo>⁢</mo><msubsup><mi>x</mi><mi>i</mi><mi>k</mi></msubsup></mrow></mrow></mrow></mtd></mtr></mtable></math></maths>&lt;br /&gt; where

<maths id="MATH-US-00005" num="00005"><math overflow="scroll"><msubsup><mi>α</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>+</mo></msubsup></math></maths>&lt;br /&gt; and

<maths id="MATH-US-00006" num="00006"><math overflow="scroll"><msubsup><mi>α</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>-</mo></msubsup></math></maths>&lt;br /&gt; are positive scaling parameters to reduce perceptual noise according to a human visual system. The parameters

<maths id="MATH-US-00007" num="00007"><math overflow="scroll"><msubsup><mi>α</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>+</mo></msubsup></math></maths>&lt;br /&gt; and

<maths id="MATH-US-00008" num="00008"><math overflow="scroll"><msubsup><mi>α</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>-</mo></msubsup></math></maths>&lt;br /&gt; may be positive values, using the secret key K, drawn from a certain probability distribution, for instance, a Gaussian distribution, a uniform distribution or the like. In this case, the robustness of the embedded watermark is degraded. However, the confidentiality of the embedded watermark is improved.

Thus, each bit x^k_iof the k-th candidate watermark is redundantly embedded into m samples in each subsets v⁺_iand v⁻_i. As the number m indicating the degree of the redundancy becomes greater, the possibility that the watermark bits are lost becomes lower and the detection error rate becomes smaller, whereas the number of bits that can be embedded into the host data decreases. Since the parameters

<maths id="MATH-US-00009" num="00009"><math overflow="scroll"><msubsup><mi>α</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>+</mo></msubsup></math></maths>&lt;br /&gt; and

<maths id="MATH-US-00010" num="00010"><math overflow="scroll"><msubsup><mi>α</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>-</mo></msubsup></math></maths>&lt;br /&gt; are values set per pixel so that visual degradation is not perceptible, in principle, the degradation of image quality will not be perceptible by human eyes even though the number m of pixels in which a watermark bit is embedded increases.

That is, the increase in m means the number of watermark bits which can be embedded decreases because of the limited region for watermarking, resulting in a decline in the ratio of the number of watermark bits to that of samples.

Each of the subsets v⁺_iand v⁻_iis, for example, a Discrete Cosine Transform (DCT) block into which a block of the host data V are transformed by DCT. The m samples in which the watermark bits are embedded are DCT coefficients in the DCT block. <figref idref="DRAWINGS">FIGS. 7A and 7B</figref> show how a watermark bit x^k_iis embedded into the m DCT coefficients in a pair of DCT blocks v⁺_iand v⁻_iof 8×8 samples. The block pair v⁺_iand v⁻_iand the m DCT coefficients are selected on the basis of the secret key K.

Referring to <figref idref="DRAWINGS">FIG. 8</figref> again, the SNR calculator <b>28</b> evaluates the robustness of the watermark x^kfor each of the L kinds of candidate watermarked host data W^k(S<b>16</b>), and the selector <b>30</b> selects one candidate watermarked host data W^kthat has the highest degree of robustness as the final watermarked host data W (S<b>18</b>).

Before addressing a formula for evaluating its robustness, the manner in which a watermark X′ is to be extracted, is considered, when the watermarked host data W are transformed by signal processing, image processing or the like. The distortion caused by the transformation of the watermarked host data W is regarded as a noise N. The watermarked host data W to which the noise N is added are called a watermarked host signal W′. The method for extracting the watermark X′ from the watermarked host signal W′ is now explained. A pair of the watermarked host signal sets (W′⁺, W′⁻) is defined, where the sets W′⁺ and W′⁻ have n elements, respectively, as follows:

<maths id="MATH-US-00011" num="00011"><math overflow="scroll"><mtable><mtr><mtd><mrow><msup><mi>W</mi><mrow><mi>′</mi><mo>+</mo></mrow></msup><mo>=</mo><mrow><mo>{</mo><mrow><msubsup><mi>w</mi><mn>0</mn><mrow><mi>′</mi><mo>+</mo></mrow></msubsup><mo>,</mo><msubsup><mi>w</mi><mn>1</mn><mrow><mi>′</mi><mo>+</mo></mrow></msubsup><mo>,</mo><mi>…</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>,</mo><msubsup><mi>w</mi><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow><mrow><mi>′</mi><mo>+</mo></mrow></msubsup></mrow><mo>}</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msup><mi>W</mi><mrow><mi>′</mi><mo>-</mo></mrow></msup><mo>=</mo><mrow><mo>{</mo><mrow><msubsup><mi>w</mi><mn>0</mn><mrow><mi>′</mi><mo>-</mo></mrow></msubsup><mo>,</mo><msubsup><mi>w</mi><mn>1</mn><mrow><mi>′</mi><mo>-</mo></mrow></msubsup><mo>,</mo><mi>…</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>,</mo><msubsup><mi>w</mi><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow><mrow><mi>′</mi><mo>-</mo></mrow></msubsup></mrow><mo>}</mo></mrow></mrow></mtd></mtr></mtable></math></maths>&lt;br /&gt; where the subsets

<maths id="MATH-US-00012" num="00012"><math overflow="scroll"><msubsup><mi>w</mi><mi>i</mi><mrow><mi>′</mi><mo>+</mo></mrow></msubsup></math></maths>&lt;br /&gt; and

<maths id="MATH-US-00013" num="00013"><math overflow="scroll"><mrow><msubsup><mi>w</mi><mi>i</mi><mrow><mi>′</mi><mo>-</mo></mrow></msubsup><mo>,</mo></mrow></math></maths>&lt;br /&gt; , each of which is the element of the watermarked host signal W′⁺ and W′⁻, have the m samples, respectively, corresponding to the location in which the watermark is embedded.

<maths id="MATH-US-00014" num="00014"><math overflow="scroll"><mtable><mtr><mtd><mrow><msubsup><mi>w</mi><mi>i</mi><mrow><mi>′</mi><mo>+</mo></mrow></msubsup><mo>=</mo><mrow><mo>{</mo><mrow><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mn>0</mn></mrow><mrow><mi>′</mi><mo>+</mo></mrow></msubsup><mo>,</mo><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mn>1</mn></mrow><mrow><mi>′</mi><mo>+</mo></mrow></msubsup><mo>,</mo><mi>…</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>,</mo><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mrow><mi>m</mi><mo>-</mo><mn>1</mn></mrow></mrow><mrow><mi>′</mi><mo>+</mo></mrow></msubsup></mrow><mo>}</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msubsup><mi>w</mi><mi>i</mi><mrow><mi>′</mi><mo>-</mo></mrow></msubsup><mo>=</mo><mrow><mo>{</mo><mrow><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mn>0</mn></mrow><mrow><mi>′</mi><mo>-</mo></mrow></msubsup><mo>,</mo><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mn>1</mn></mrow><mrow><mi>′</mi><mo>-</mo></mrow></msubsup><mo>,</mo><mi>…</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>,</mo><msubsup><mi>w</mi><mrow><mrow><mi>i</mi><mo>.</mo><mi>m</mi></mrow><mo>-</mo><mn>1</mn></mrow><mrow><mi>′</mi><mo>-</mo></mrow></msubsup></mrow><mo>}</mo></mrow></mrow></mtd></mtr></mtable></math></maths>

The following decision value z_iis calculated in order to determine the watermark bit x^k_i.

<maths id="MATH-US-00015" num="00015"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>z</mi><mi>i</mi></msub><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>m</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo>⁢</mo><mrow><mo>(</mo><mrow><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mi>′</mi><mo>+</mo></mrow></msubsup><mo>-</mo><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mi>′</mi><mo>-</mo></mrow></msubsup></mrow><mo>)</mo></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>m</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo>⁢</mo><mrow><mo>[</mo><mrow><mrow><mo>(</mo><mrow><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>+</mo></msubsup><mo>+</mo><msubsup><mi>n</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>+</mo></msubsup></mrow><mo>)</mo></mrow><mo>-</mo><mrow><mo>(</mo><mrow><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>-</mo></msubsup><mo>+</mo><msubsup><mi>n</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>-</mo></msubsup></mrow><mo>)</mo></mrow></mrow><mo>]</mo></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>m</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo>⁢</mo><mrow><mo>[</mo><mrow><mrow><mo>(</mo><mrow><msubsup><mi>v</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>+</mo></msubsup><mo>-</mo><msubsup><mi>v</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>-</mo></msubsup></mrow><mo>)</mo></mrow><mo>+</mo><mrow><mrow><mo>(</mo><mrow><msubsup><mi>α</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>+</mo></msubsup><mo>+</mo><msubsup><mi>α</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>-</mo></msubsup></mrow><mo>)</mo></mrow><mo>⁢</mo><msubsup><mi>x</mi><mi>i</mi><mi>k</mi></msubsup></mrow><mo>+</mo><mrow><mo>(</mo><mrow><msubsup><mi>n</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>+</mo></msubsup><mo>-</mo><msubsup><mi>n</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>-</mo></msubsup></mrow><mo>)</mo></mrow></mrow><mo>]</mo></mrow></mrow></mrow></mtd></mtr></mtable></math></maths>&lt;br /&gt; where

<maths id="MATH-US-00016" num="00016"><math overflow="scroll"><mrow><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>m</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo>⁢</mo><mrow><mo>(</mo><mrow><msubsup><mi>v</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>+</mo></msubsup><mo>-</mo><msubsup><mi>v</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>-</mo></msubsup></mrow><mo>)</mo></mrow></mrow></math></maths>&lt;br /&gt; conforms to a Gaussian distribution and approaches zero when the number m is large enough. Likewise, the noise term

<maths id="MATH-US-00017" num="00017"><math overflow="scroll"><mrow><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>m</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo>⁢</mo><mrow><mo>(</mo><mrow><msubsup><mi>n</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>+</mo></msubsup><mo>-</mo><msubsup><mi>n</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>-</mo></msubsup></mrow><mo>)</mo></mrow></mrow></math></maths>&lt;br /&gt; also approaches zero. Therefore, the decision value z_ican be approximated by the value

<maths id="MATH-US-00018" num="00018"><math overflow="scroll"><mrow><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>m</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo>⁢</mo><mrow><mrow><mo>[</mo><mrow><mrow><mo>(</mo><mrow><msubsup><mi>α</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>+</mo></msubsup><mo>+</mo><msubsup><mi>α</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>-</mo></msubsup></mrow><mo>)</mo></mrow><mo>⁢</mo><msubsup><mi>x</mi><mi>i</mi><mi>k</mi></msubsup></mrow><mo>]</mo></mrow><mo>.</mo></mrow></mrow></math></maths>&lt;br /&gt; . Since

<maths id="MATH-US-00019" num="00019"><math overflow="scroll"><mrow><mo>(</mo><mrow><msubsup><mi>α</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>+</mo></msubsup><mo>+</mo><msubsup><mi>α</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>-</mo></msubsup></mrow><mo>)</mo></mrow></math></maths>&lt;br /&gt; is positive by definition, z_iis positive if the watermark bit x^k_iis 1, and z_iis negative if the watermark bit x^k_iis −1. Therefore the value of the watermark bit x^k_ican be determined depending on whether z_iis positive or negative.

The robustness of the embedded watermark is evaluated by regarding the host data V as a distortion to the watermark X and calculating the variance of an extracted watermark for the embedded watermark x^k. The smaller the variance is, the greater the robustness is. The signal-to-noise ratio (SNR) is evaluated by the following formula for the pair of candidate watermarked host data (W^+k, W^−k) and the optimal candidate K is selected.

K=argmax_k(P_k/(2σ_k²))

<maths id="MATH-US-00020" num="00020"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>P</mi><mi>k</mi></msub><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo>⁢</mo><mrow><msup><mrow><mo></mo><mrow><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>m</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo>⁢</mo><mrow><mo>(</mo><mrow><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mo>+</mo><mi>k</mi></mrow></msubsup><mo>-</mo><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mo>-</mo><mi>k</mi></mrow></msubsup></mrow><mo>)</mo></mrow></mrow><mo></mo></mrow><mn>2</mn></msup><mo>/</mo><mi>n</mi></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msubsup><mi>σ</mi><mi>k</mi><mn>2</mn></msubsup><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo>⁢</mo><mrow><msup><mrow><mo></mo><mrow><mrow><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>m</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo>⁢</mo><mrow><mo>(</mo><mrow><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mo>+</mo><mi>k</mi></mrow></msubsup><mo>-</mo><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mo>-</mo><mi>k</mi></mrow></msubsup></mrow><mo>)</mo></mrow></mrow><mo>-</mo><mrow><msubsup><mi>P</mi><mi>k</mi><mrow><mn>1</mn><mo>/</mo><mn>2</mn></mrow></msubsup><mo>⁢</mo><msubsup><mi>x</mi><mi>i</mi><mi>k</mi></msubsup></mrow></mrow><mo></mo></mrow><mn>2</mn></msup><mo>/</mo><mi>n</mi></mrow></mrow></mrow></mtd></mtr></mtable></math></maths>

Since the above-mentioned decision value z_ito determine whether the watermark bit x^k_iis 1 or −1 is given as

<maths id="MATH-US-00021" num="00021"><math overflow="scroll"><mrow><msub><mi>z</mi><mi>i</mi></msub><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>m</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><mo>(</mo><mrow><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mo>+</mo><mi>k</mi></mrow></msubsup><mo>-</mo><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mo>-</mo><mi>k</mi></mrow></msubsup></mrow><mo>)</mo></mrow></mrow></mrow></math></maths>&lt;br /&gt; before the noise is added to the watermarked host data W, the variance σ_k²can be regarded as the average power of the difference between the watermark bit determined by the decision value z_iand the actual embedded watermark bit x^k_iamplified by P_k^1/2for i=0, . . . , n−1. P_kcan be regarded as the average power of the decision value z_ifor i=0, . . . , n−1. Therefore, the smaller the Euclidian distance between the embedded watermark and the extracted watermark is and the larger the power of the decision value to determine the watermark bit is, the larger P_k/(2σ_k²) becomes. In other words, by selecting the candidate having the largest P_k/(2σ_k²), the candidate having the smallest detection errors in extracting the watermark bits can be selected.

In respect of the decision value z_i, if

<maths id="MATH-US-00022" num="00022"><math overflow="scroll"><mrow><msubsup><mi>v</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>+</mo></msubsup><mo>&gt;</mo><msubsup><mi>v</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>-</mo></msubsup></mrow></math></maths>&lt;br /&gt; and x^k_i=1, z_i&gt;&gt;0, and if

<maths id="MATH-US-00023" num="00023"><math overflow="scroll"><mrow><msubsup><mi>v</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>+</mo></msubsup><mo>&lt;</mo><msubsup><mi>v</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>-</mo></msubsup></mrow></math></maths>&lt;br /&gt; and x^k_i=−1, z_i&lt;&lt;0. This means that by selecting the optimal candidate watermark x^kaccording to the above-mentioned evaluation, the original watermark bit x_iis changed to x_i′ so that x_i′=1 if v⁺_i,j&gt;v⁻_i,jand x_i′=−1 if

<maths id="MATH-US-00024" num="00024"><math overflow="scroll"><mrow><msubsup><mi>v</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>+</mo></msubsup><mo>&lt;</mo><mrow><msubsup><mi>v</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>-</mo></msubsup><mo>.</mo></mrow></mrow></math></maths>&lt;br /&gt; . This is a guiding rule used in the GS method and thereby the response of the decision value z_iis improved.

When the extractor <b>42</b> of the decoding apparatus <b>40</b> receives the noisy watermarked host signal W′, the extractor <b>42</b> calculates the decision value z_ias follows:

<maths id="MATH-US-00025" num="00025"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>z</mi><mi>i</mi></msub><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>m</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><mo>(</mo><mrow><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mi>′</mi><mo>+</mo></mrow></msubsup><mo>-</mo><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mi>′</mi><mo>-</mo></mrow></msubsup></mrow><mo>)</mo></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>m</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><mo>[</mo><mrow><mrow><mo>(</mo><mrow><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>+</mo></msubsup><mo>+</mo><msup><mi>n</mi><mrow><mrow><mo>+</mo><mi>i</mi></mrow><mo>,</mo><mi>j</mi></mrow></msup></mrow><mo>)</mo></mrow><mo>-</mo><mrow><mo>(</mo><mrow><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>-</mo></msubsup><mo>+</mo><msubsup><mi>n</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>-</mo></msubsup></mrow><mo>)</mo></mrow></mrow><mo>]</mo></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>m</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><mo>[</mo><mrow><mrow><mo>(</mo><mrow><msubsup><mi>v</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>+</mo></msubsup><mo>+</mo><msubsup><mi>v</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>-</mo></msubsup></mrow><mo>)</mo></mrow><mo>-</mo><mrow><mrow><mo>(</mo><mrow><msubsup><mi>α</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>+</mo></msubsup><mo>+</mo><msubsup><mi>α</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>-</mo></msubsup></mrow><mo>)</mo></mrow><mo>⁢</mo><msubsup><mi>x</mi><mi>i</mi><mi>′</mi></msubsup></mrow><mo>+</mo><mrow><mo>(</mo><mrow><msubsup><mi>n</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>+</mo></msubsup><mo>+</mo><msubsup><mi>n</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>-</mo></msubsup></mrow><mo>)</mo></mrow></mrow><mo>]</mo></mrow></mrow></mrow></mtd></mtr></mtable></math></maths>

If the ECC decoder <b>44</b> is configured as a hard-input decoder, whether watermark bit x′ is −1 or 1 is determined depending on whether the decision value z_iis negative or positive, and sent to the ECC decoder <b>44</b>. When the ECC decoder <b>44</b> is configured as a soft-input decoder, the decision value z_iis directly sent to the ECC decoder <b>44</b> without any hard decision on whether the watermark bit is −1 or 1.

Furthermore, the extracted watermark X′ is error corrected by the ECC decoder <b>44</b> and descrambled by the descrambler <b>46</b> and thereby the original watermark X is obtained.

As stated above, according to this embodiment, when media data such as image or audio to be watermarked are given, the watermark bit sequence can be converted to a bit sequence prone to be adhered to the media data and thereafter embedded. Therefore it is possible to make the digital watermark robust against signal processing, geometric transform, compression, attacks and so on, and thereby the detection accuracy in extracting the watermark is highly improved.

In the above-mentioned embodiment, L multiplexers <b>20</b>, scramblers <b>22</b>, ECCs <b>24</b>, embedders <b>26</b>, and SNR calculators <b>28</b> are provided in parallel to generate L kinds of candidate watermarks, however, a plurality of these components can be unified in a single structure and L kinds of candidate watermarks may be sequentially generated and evaluated, and thereby an optimal candidate may be selected.

<figref idref="DRAWINGS">FIG. 9</figref> is a flowchart to explain such a sequential watermark embedding procedure. A variable i is set to 1 (S<b>20</b>). The multiplexer <b>20</b> inserts i-th initial data in the head of the watermark X encrypted by the encryptor <b>12</b> and generates a code sequence (S<b>22</b>), and the scrambler <b>22</b> scrambles the code sequence and generates i-th scrambled watermark X′ (S<b>24</b>). The ECC <b>24</b>, if necessary, adds a parity for error correction to the i-th scrambled watermark X′ generated by the scrambler <b>22</b>, and the embedder <b>26</b> embeds it in the host data V (S<b>26</b>). The SNR calculator <b>28</b> evaluates robustness S_i, that is, tolerance of the watermark x_iembedded in the i-th candidate watermarked host data (S<b>28</b>).

The selector <b>30</b> determines whether the robustness S_iis greater than a threshold value T (S<b>30</b>). If the robustness S_iis greater than the threshold value T (Y of S<b>30</b>), the current value of the variable i is assigned to a variable K (S<b>32</b>), and the K-th candidate watermarked host data is selected as the final watermarked host data W (S<b>40</b>). If the robustness S_iis not greater than the threshold value T (N of S<b>30</b>) and if the current value of the variable i is equal to L (Y of S<b>34</b>), the index k of the greatest robustness S_kevaluated so far is assigned to the variable K (S<b>38</b>), and the K-th candidate watermarked host data is selected as the final host data W (S<b>40</b>) If the current value of the variable i is less than L (N of S<b>34</b>), the variable i is incremented by 1 (S<b>36</b>), and the procedure goes back to the step S<b>22</b>.

By this iterative process, once a candidate with a higher level of robustness than a desired level is obtained, the candidate can be selected as the final watermarked host data W. If such a candidate is not generated, L kinds of candidate watermarked host data are generated and one candidate with the highest level of the robustness can be selected as the final watermarked host data W.

Embodiment 2

<figref idref="DRAWINGS">FIG. 10</figref> shows a block diagram of an encoding apparatus <b>11</b> according to Embodiment 2. In the present embodiment, a specific process such as compression to be performed on host data V in which a watermark is embedded is anticipated beforehand, and the effect by the specific process is considered when the watermark is embedded and thereby the robustness of the watermark is ensured to a distortion caused by the specific process. The same structures as Embodiment 1 are denoted by the same numerals and the explanation thereof is omitted, and the structures and behaviors different from Embodiment 1 are explained below.

In scrambling a watermark X, a modifier <b>15</b> selects a bit sequence of the watermark with a high level of robustness in respect of a distortion D caused by the specific process to be performed on the host data V and outputs a scrambled watermark X′. <figref idref="DRAWINGS">FIG. 11</figref> is a block diagram of the modifier <b>15</b> and the embedder <b>16</b>. Weighed SNR calculators <b>29</b> evaluate the robustness of the watermark X in candidate watermarked host data W in which L kinds of scrambled watermark X′_cexist, taking account of the anticipated distortion D caused by the specific process. Concretely, for evaluating the robustness on the basis of the variance between the embedded watermark and an extracted watermark, the following weighted variance is used, in which the distortion by the specific process to be performed on the watermarked host data W is considered. &lt;br /&gt;<i>K=argmax</i>_k(<i>P</i>_k/(2σ_k²))

<maths id="MATH-US-00026" num="00026"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>P</mi><mi>k</mi></msub><mo>=</mo>&lt;mi /&gt;<mo>⁢</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><mo>|</mo><mrow><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>m</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><mo>(</mo><mrow><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mo>*</mo><mrow><mo>+</mo><mi>k</mi></mrow></mrow></msubsup><mo>-</mo><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mo>*</mo><mrow><mo>-</mo><mi>k</mi></mrow></mrow></msubsup></mrow><mo>)</mo></mrow></mrow><mo>⁢</mo><msup><mo>|</mo><mn>2</mn></msup><mo>⁢</mo><mrow><mo>/</mo><mi>n</mi></mrow></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msubsup><mi>σ</mi><mi>k</mi><mn>2</mn></msubsup><mo>=</mo>&lt;mi /&gt;<mo>⁢</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><mo>|</mo><mrow><mrow><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>m</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><mo>(</mo><mrow><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mo>*</mo><mrow><mo>+</mo><mi>k</mi></mrow></mrow></msubsup><mo>-</mo><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mo>*</mo><mrow><mo>-</mo><mi>k</mi></mrow></mrow></msubsup></mrow><mo>)</mo></mrow></mrow><mo>-</mo><mrow><msubsup><mi>P</mi><mi>k</mi><mrow><mn>1</mn><mo>/</mo><mn>2</mn></mrow></msubsup><mo>·</mo><msubsup><mi>x</mi><mi>i</mi><mi>k</mi></msubsup></mrow></mrow><mo>⁢</mo><msup><mo>|</mo><mn>2</mn></msup><mo>⁢</mo><mrow><mo>/</mo><mi>n</mi></mrow></mrow></mrow></mrow></mtd></mtr></mtable></math></maths>&lt;br /&gt; where

<maths id="MATH-US-00027" num="00027"><math overflow="scroll"><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mo>*</mo><mrow><mo>+</mo><mi>k</mi></mrow></mrow></msubsup></math></maths>&lt;br /&gt; and

<maths id="MATH-US-00028" num="00028"><math overflow="scroll"><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mo>*</mo><mrow><mo>-</mo><mi>k</mi></mrow></mrow></msubsup></math></maths>&lt;br /&gt; are the watermarked host data W on which the specific process has been performed. If the specific process is known in advance and it is, for instance, JPEG compression, w*^+k_i,jand w*^−k_i,jcan be calculated by the following formula using a quantization table in JPEG.

<maths id="MATH-US-00029" num="00029"><math overflow="scroll"><mtable><mtr><mtd><mrow><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mo>*</mo><mrow><mo>+</mo><mi>k</mi></mrow></mrow></msubsup><mo>=</mo>&lt;mi /&gt;<mo>⁢</mo><mrow><mrow><mi>round</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mo>+</mo><mi>k</mi></mrow></msubsup><mo>/</mo><msub><mi>q</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub></mrow><mo>)</mo></mrow></mrow><mo>⁢</mo><msub><mi>q</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mo>*</mo><mrow><mo>-</mo><mi>k</mi></mrow></mrow></msubsup><mo>=</mo>&lt;mi /&gt;<mo>⁢</mo><mrow><mrow><mi>round</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msubsup><mi>w</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mo>-</mo><mi>k</mi></mrow></msubsup><mo>/</mo><msub><mi>q</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub></mrow><mo>)</mo></mrow></mrow><mo>⁢</mo><msub><mi>q</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub></mrow></mrow></mtd></mtr></mtable></math></maths>&lt;br /&gt; where q_i,jis the value of the location (i,j) in the quantization table in JPEG and round( ) is a round function used in the JPEG compression.

According to the present embodiment, since a specific process to be performed on the watermarked host data is anticipated in evaluating the robustness and the bit sequence of the watermark with the highest level of the robustness is selected, the watermark that is highly tolerant toward the specific process can be generated.

Embodiment 3

<figref idref="DRAWINGS">FIG. 12</figref> shows a block diagram of an encoding apparatus <b>50</b> according to Embodiment 3. The encoding apparatus <b>50</b> embeds a watermark X in a plurality of candidate locations of host data V and selects one of candidates for the watermarked host data with a high level of robustness and outputs it as a final watermarked host data W. The same structures as Embodiment 1 are denoted by the same numerals and the explanation thereof is omitted, and the structures and behaviors different from Embodiment 1 are explained below.

A location generator <b>52</b> generates a scrambled watermark location P and an embedder <b>54</b> embeds the watermark X in the watermark location P of the host data V and outputs the watermarked host data W. The location generator <b>52</b> and the embedder <b>54</b>, in cooperation with each other, generate a plurality of the watermark locations P, using a secret key K, and embed the watermark X in the respective watermark locations P, and thereby generate a plurality of candidate watermarked host data W and select one of the candidates.

<figref idref="DRAWINGS">FIG. 13</figref> is a block diagram of the location generator <b>52</b> and the embedder <b>54</b>. An ECC <b>24</b> generates a watermark X_cwith a parity added to a watermark X_b. A location information generator <b>60</b> generates L candidate watermark locations P of the host data V. L embedders <b>26</b> embed the watermark X_cto the respective candidate watermark locations P and generate L kinds of candidate watermarked host data W.

The location information generator <b>60</b> generates L candidate watermark locations P scrambled by the GS method. L kinds of initial data C₀to C_L−1are provided for an initial watermark location P* and the initial watermark location P* is scrambled by the method similar to the one described in Embodiment 1.

<figref idref="DRAWINGS">FIG. 14</figref> shows a block diagram of a decoding apparatus according to Embodiment 3. The decoding apparatus extracts an embedded watermark X_cfrom a watermarked host signal W′ and performs error correction on the watermark X_cand thereby obtains the error corrected watermark X_b. The location information generator <b>60</b> generates L candidate watermark locations P, just as the location information generator <b>60</b> in the encoding apparatus <b>50</b> shown in <figref idref="DRAWINGS">FIG. 13</figref> does. L extractors <b>42</b> extract L kinds of candidate watermarks X_chidden in the watermarked host signal W′ from the L candidate watermark locations P given by the location information generator <b>60</b>. Only one among the L candidate watermark locations P is a correct watermark location. A matched filter <b>62</b> computes the correlation between the L candidate watermarks X_cand an anticipated watermark Y. A selector <b>64</b> selects one watermark X_cwith the highest degree of the correlation and thus the watermark X_cin the correct watermark location is obtained. The obtained watermark X_cis error corrected by an ECC decoder <b>44</b>.

The anticipated watermark Y is given if the watermark X to be embedded in the host data V is known. For instance, there is the case in which the originator of the host data V is known and it is to be confirmed that the watermark X on the originator has been embedded in the host data V. In general, the present embodiment can be applied to the case in which the embedded watermark information is known beforehand but its watermark location is only given as some candidates.

According to the present embodiment, when media data to be watermarked are given, the location in which a given watermark is to be stickily embedded can be detected depending on the media data, and the robustness of the watermark embedded in the location can be improved.

Embodiment 4

In Embodiments 1 to 3, an error correction code is used for correcting errors in the watermark X. In the respect that the decision value z_iis used for detecting watermark bit x^k_iin the process of decoding, it can be understood that a soft-decision decoding, which utilizes auxiliary information indicating the reliability of decoded bits for the soft-decision, is effective for detecting the watermark. In the present embodiment, a turbo code is used as such a soft-decision decoding method, and the ECC <b>24</b> of the encoding apparatus and the ECC decoder <b>44</b> of the decoding apparatus are replaced by a turbo encoder <b>70</b> of <figref idref="DRAWINGS">FIG. 15</figref> and a turbo decoder <b>90</b> of <figref idref="DRAWINGS">FIG. 16</figref> respectively.

Referring to <figref idref="DRAWINGS">FIG. 15</figref>, the structure and behavior of the turbo encoder <b>70</b> is explained. A user bit sequence UB, input data to be encoded, is input to the first encoder <b>72</b> which generates a parity bit sequence P₀. The user bit sequence UB is put in random order by an interleaver <b>74</b> and input to the second encoder <b>76</b> which generates another parity bit sequence P₁. The two parity bit sequences P₀and P₁are punctured and multiplexed by a multiplexer and puncturer <b>78</b> and then multiplexed with the user bit sequence UB by a multiplexer <b>80</b> and finally output as a coded bit CB. It is to be noted that the puncturing process is an optional process to increase the number of the watermark bits and the process can be omitted if it is not necessary.

Referring to <figref idref="DRAWINGS">FIG. 16</figref>, the structure and behavior of the turbo decoder <b>90</b> is explained. The first soft decoder <b>92</b> corresponding to the first encoder <b>72</b> of <figref idref="DRAWINGS">FIG. 15</figref> decodes a received channel output CO and outputs extrinsic information that contains the decoding result of each information bit and its reliability information. The soft value z_ithat is obtained as a decision value from the received host data is herein utilized as the channel output CO. The second soft decoder <b>98</b> corresponding to the second encoder <b>76</b> of <figref idref="DRAWINGS">FIG. 15</figref> uses the extrinsic information obtained from the first soft decoder <b>92</b> via an interleaver <b>94</b> as the a priori probability and decodes the channel output CO that is sorted by an interleaver <b>96</b>. The second soft decoder <b>98</b> provides extrinsic information for the decoding result to the first soft decoder <b>92</b> via a deinterleaver <b>100</b>. The first soft decoder <b>92</b> uses the extrinsic information from the second soft decoder <b>98</b> as the a priori probability and decodes the channel output CO. By iterating this process, the turbo decoder <b>90</b> outputs a final decision FD. The arrangement by the interleavers <b>94</b> and <b>96</b> is the same as that by the interleaver <b>74</b> of <figref idref="DRAWINGS">FIG. 15</figref>. The deinterleaver <b>100</b> restores the data ordered randomly by the interleavers <b>94</b> and <b>96</b>.

In the turbo decoder <b>90</b>, the first soft decoder <b>92</b> and the second soft decoder <b>98</b> can utilize a priori information provided from the other and gradually improve the decoding result by maximum a posteriori probability (MAP) decoding.

Therefore BER in detecting watermark bits can be further reduced.

Although the present invention has been described by way of exemplary embodiments, it should be understood that many changes and substitutions may be made by those skilled in the art without departing from the scope of the present invention which is defined by the appended claims. Some such alterations are stated as follows.

The method for evaluating the robustness anticipating a specific process described in Embodiment 2 can be also applied to evaluating the robustness in Embodiment 3.

The GS method based on the convolutional operation is used for generating a plurality of candidate watermarks and candidate watermark locations, in which a variety of candidates can be generated, however, the other scrambling methods are also applicable and the candidates may be randomly generated by some methods. In the embodiments, the original watermark is restored by unscrambling the watermark bits extracted from the host data, however, a table that associates the original watermark with the candidate watermarks may be provided and the original watermark may be obtained by referring to the table.

The identification data used as initial data in the scrambling process are inserted in the head of watermark data and provided to the decoding apparatus, however, the identification data may not be embedded as the watermark and may be retained and managed as a secret key in the encoding apparatus. In this case, the decoding apparatus obtains the secret key and then descrambles the watermark. In Embodiment 3, since the decoding apparatus can identify the watermark location by using the identification data obtained as the secret key, the watermark location does not need to be detected and it becomes unnecessary to provide anticipated watermark bits beforehand.

In Embodiment 4, a turbo code is explained, however, any other soft-decision based error correction codes can be applied.

As a variation of Embodiment 1, the sequential type of candidate generation and evaluation is explained. As a matter of course, the same structure and behavior can be applied to Embodiments 2 and 3.

In Embodiment 3, the candidate watermark locations are generated by the scrambling method, however, the candidate locations may be randomly generated by looking up a table as described below. For this purpose, the encoding apparatus and the decoding apparatus have a table that associates identification data on the candidate watermark locations with the actual watermark location. In other words, the table stores a correspondence relation between identification numbers and coordinates of the watermark locations, for instance, a location (1, 19) for an identification number 0, a location (983,251) for an identification number 1, . . . , and a location (542,37) for an identification number 15, for the first bit of the watermark. For each of the second to the n-th bits, a different correspondence relation which defines different watermark locations is stored. In this way, the watermark locations are randomly generated by some method.

The encoding apparatus, by referring to the table, generates the candidate watermark locations corresponding to its identification data and embeds the watermark in one of the candidate locations. The decoding apparatus refers to the table using the identification data on the candidate location and thereby identifies the watermark location and then extracts the watermark from the location. By this method, the randomness of the watermark location is sufficiently guaranteed and the robustness of the watermark can be realized. In addition, since the decoding apparatus cannot identify the watermark location unless the apparatus has the table as well as the identification data on the candidate locations, the security can be improved.