Abstract:
The watermarking system uses a first series of parameters, the private key, for the insertion of the watermark, and a second series of parameters, the public key, for the detection of the watermark, so that knowledge of the public key does not make it possible to know the private key and does not make it possible to delete or modify the watermark. The insertion of the watermark is performed by adding a pseudo random noise sequence, filtered by a filter with impulse response, to the data to be watermarked. The detection of the watermark is performed by searching through the data received for whether they contain noise which has been filtered by a filter with predefined spectral response. Application to copy protection.

Description:
This application claims the benefit, under 35 U.S.C. § 365 of International Application PCT/EP00/04053, filed May 5, 2000, which was published in accordance with PCT Article 21(2) on Dec. 7, 2000 in English and which claims the benefit of French patent application No. 9907139 filed Jun. 1, 1999. 
   BACKGROUND OF THE INVENTION 
   The present invention relates to the field of watermarking of digital data. It relates more particularly to a system for watermarking data using novel watermark insertion and detection methods as well as to devices for implementing these methods. 
   RELATED ART 
   Recent methods for protecting against the illicit copying of digital data use the principle of data watermarking which consists in inserting a marking item, commonly referred to as a “watermark”, into a multimedia content (still image, video, sound, etc.) in an imperceptible manner. The watermark can for example be a signal indicating that the content may not be copied or any other item allowing the supplier of the multimedia content to detect illegal copies. 
   In order to play its role perfectly, the watermark must be robust to transformations of the watermarked content, whether these transformations be made intentionally by a pirate who wishes to erase the watermark, or whether they result from distortions which occurred during the transmission of the signal containing the watermarked data. 
   Various data watermarking techniques are known from the prior art. Reference may in particular be made to the documents EP-A-0 828 372, EP-A-0 840 513, WO-A-98/03014 or WO-A-98/54897 which describe methods for inserting watermarks into data to be protected and methods for detecting the presence of such watermarks in the data. 
   A scheme which is generally used to describe the principle of data watermarking is that of  FIG. 1 . A first part  1  relates to the insertion of a hidden item W (the watermark) into a content to be protected C. This results in a watermarked content CT. Part  2  relates to the detection of the presence of the item W in the content received CT. An additional datum K is also necessary in the process for inserting and detecting the watermark. This datum K which must be shared in a secret manner by the device for inserting and detecting the watermark is referred to as the key by analogy with so-called symmetric or private-key cryptography systems. 
   For example, a known watermarking technique consists in adding a pseudo random noise sequence to data which are to be watermarked. The detection process is carried out, in this case, by performing a correlation calculation: the data received are declared watermarked if the correlation with the reference pseudo noise sequence (used for the insertion of the watermark) is greater than a given threshold. In this example, the reference pseudo noise sequence constitutes the key K of the data watermarking scheme of  FIG. 1 . 
   The problem with this scheme is that each entity capable of detecting the watermark must share the same key K as the entity which inserted the watermark. In this case, the entity capable of detecting the watermark can furthermore delete it or modify it, thereby doing away with all the benefit of the initial watermarking of the data. Consequently, a supplier of content protected by watermarking should not communicate his key K, which served for the insertion of the watermark, other than in a secret manner to trusted entities. This considerably limits the possibilities of using data watermarking in numerous fields. 
   In particular, in the field of consumer electronic appliances, it is well known that it is almost impossible, at any event at reasonable cost, to store secret parameters in an appliance or in software contained in such an appliance. Smart cards, which are regarded as the only pieces of equipment allowing the secure storage of a secret parameter, are not themselves powerful enough to perform the calculations connected with a watermark detection process. 
   In the example described above where the watermarking is carried out by adding a pseudo random noise sequence to the data which are to be watermarked, even if the reference pseudo noise sequence is stored secretly in the watermark detection device, it has been demonstrated that a pirate can theoretically discover the reference sequence and thus delete the watermark from the data by observing the output from the detector as a function of a large number of different input signals. 
   BRIEF SUMMARY OF THE INVENTION 
   The invention aims to solve the aforesaid problems. 
   To this end, the invention relates to a method for inserting a watermark into data representing a content to be protected. According to the invention, the method comprises the steps consisting in: 
   a) supplying a pseudo random noise sequence to the input of a filter with predefined impulse response; and 
   b) adding the filtered pseudo noise sequence to the data. 
   According to a preferred aspect of the invention, the method furthermore comprises the steps consisting in: 
   c) performing a pseudo random interleaving of the data before step b); and 
   d) performing an inverse interleaving after step b) so as to obtain the watermarked data. 
   The invention also relates to a method for detecting a watermark in data representing a content received, characterized in that it comprises the steps consisting in: 
   i) performing a spectral analysis of the data; and 
   ii) deducing therefrom whether the data include a pseudo noise sequence which has been filtered by a filter with predefined spectral response. 
   According to another preferred aspect of the invention, a pseudo random interleaving of the data received, which is identical to the interleaving performed in step c) above, is performed before step i). 
   The invention also relates to a system for watermarking data using a watermark insertion method and a watermark detection method as those above. According to the invention, a first series of parameters, the private key, is used for the insertion of the watermark and a second series of parameters, the public key, is used for the detection of the watermark, so that: 
   knowledge of the public key does not make it possible to know the private key; and 
   knowledge of the method of detection and of the public key does not make it possible to delete or modify the watermark. 
   The invention also relates to a device for inserting a watermark into data representing a content to be protected. According to the invention, the device comprises: 
   means for generating a pseudo random noise sequence; 
   filtering means having a predefined impulse response and which are adapted for receiving the pseudo noise sequence and for supplying a filtered pseudo noise sequence; and 
   means for adding the filtered pseudo noise sequence to the data. 
   According to a preferred embodiment of the invention, the device furthermore comprises: 
   first means of pseudo random interleaving of the data representative of the content to be protected so as to supply interleaved data, the interleaved data being supplied to the addition means so as to be added to the filtered pseudo noise sequence; and 
   means of inverse interleaving of the first interleaving means, linked to the output of the said addition means so as to supply the watermarked data. 
   According to a particular embodiment of the invention, the device comprises: 
   means for transforming the content to be protected into data representative of the content; 
   means for generating a modulation sequence indicative of the maximum amount of noise which can be added to the data; 
   first means of pseudo random interleaving of the data representative of the content to be protected so as to supply interleaved data; 
   second means of pseudo random interleaving, which are identical to the first adapted for receiving the modulation sequence so as to supply an interleaved modulation sequence; 
   multiplication means adapted for receiving, on the one hand the interleaved modulation sequence, and on the other hand the filtered pseudo noise sequence, so as to supply the watermark; 
   means of addition of the interleaved data and of the watermark, the output of the addition means being linked to: 
   means of inverse interleaving of the first and second interleaving means so as to supply the watermarked data; and 
   means of inverse transformation of the watermarked data into a marked content. 
   The invention also relates to a device for detecting a watermark in data representing a content received. According to the invention, the device comprises: 
   means for estimating the power spectral density of the data; and 
   means of likelihood testing of hypotheses so as to estimate whether the data include a pseudo noise sequence which has been filtered by a filter with predefined spectral response. 
   According to a particular embodiment, the device furthermore comprises: 
   means of pseudo random interleaving of the data representing the content received, which are adapted for performing the same interleaving as the first interleaving means of the insertion device, the interleaved data being supplied to the means for estimating the power spectral density. 
   According to another particular embodiment, the device furthermore comprises: 
   means for transforming the content received into data representative of the content, the transforming means being adapted for performing the same transformation as the transforming means of the insertion device. 

   
     BRIEF DESCRIPTION OF THE DRAWING 
     Other characteristics and advantages of the invention will become apparent on reading the following description of a particular embodiment, which is non-limiting, of the invention given with reference to the appended figures, among which: 
       FIG. 1 , described previously, illustrates a known scheme for watermarking digital data; 
       FIG. 2  schematically represents a watermark insertion device according to the invention; 
       FIG. 3  schematically represents a watermark detection device according to the invention; 
       FIG. 4  illustrates a novel scheme for watermarking digital data according to the invention. 
   

   DETAILED DESCRIPTION OF THE INVENTION 
   Represented schematically in  FIG. 2  is a device according to the invention for inserting a watermark into a signal representative of a content to be protected. This signal can in particular be a digital video or audio signal or else a signal representing a still image such as a photograph or a computer-calculated synthetic image, or more generally, any signal representing a multimedia content. 
   Firstly, the content to be protected is transformed by a transformation module  10  into a sequence of digital data x={x n }, n lying between 1 and N. For example, if the content to be protected is an image comprising N pixels, the coefficients x n  can correspond to the luminance of each pixel of the image. These may also be coefficients of a Discrete Fourier Transform of the signal representing the content to be protected, or else coefficients of a Fourier-Mellin Transform or coefficients of a wavelet decomposition when the content to be protected is a still image. 
   The data sequence x representing the content to be protected is transmitted on the one hand to a module HPM  12  which outputs a modulation sequence m={m n }, ∀n ε[1 . . . N]. The module HPM calculates this modulation sequence as a function of algorithms based on human perception models, such as Sarnoff&#39;s model of the eye. This sequence m={m n } represents the maximum amount of noise which can be added to each coefficient x n  without perceptible loss of quality. 
   According to one aspect of the invention, the data sequence x is transmitted moreover to an interleaver  20 , which performs a random permutation p of the coefficients x n  so as to supply a sequence of interleaved coefficients {tilde over (x)}={x p(n) }. The purpose of this interleaving of the data sequence x will be explained subsequently. 
   The modulation sequence m is also transmitted to an interleaver  14  which performs the same permutation p of the coefficients m n  as that performed by the interleaver  20  so as to output an interleaved modulation sequence {tilde over (m)}={m p(n)}.    
   In order to constitute the watermark which will be inserted into the data sequence x representing the content to be protected, a pseudo random noise generator (not represented) firstly supplies a pseudo noise sequence v={v n }, ∀n ε[1 . . . N], with Gaussian distribution. This pseudo noise sequence v is transmitted to the input of a filter  16 , of Linear Time Invariant (LTI) type, whose impulse response is: 
   h={h n }, ∀n ε [1 . . . L] where L is an integer corresponding to the length of the filter; 
   and whose spectral response is H(f), H(f) being the Fourier Transform of h. 
   At the output of the filter  16  one obtains a filtered pseudo noise sequence w={w n }, ∀n ε[1 . . . N]satisfying the following equation (1): 
   
     
       
         
           
             
               
                 
                   w 
                   n 
                 
                 = 
                 
                   
                     
                       ∑ 
                       
                         k 
                         = 
                         1 
                       
                       L 
                     
                     ⁢ 
                     
                       
                         v 
                         
                           n 
                           - 
                           k 
                         
                       
                       · 
                       
                         h 
                         k 
                       
                     
                   
                   = 
                   
                     
                       
                         h 
                         n 
                       
                       ⊗ 
                       
                         v 
                         n 
                       
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         ∀ 
                         n 
                       
                       ⁢ 
                       
                         ∈ 
                         
                           [ 
                           
                             1 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             … 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             N 
                           
                           ] 
                         
                       
                     
                   
                 
               
             
             
               
                 ( 
                 1 
                 ) 
               
             
           
         
       
     
   
   in which             represents the convolution product.
   From this may be deduced, from the interference theorem, the following two equations (2) and (3):
 
φ ww (τ)=( h               h )         φ vv (τ)  (2)

   in which φ ww  (τ) and φ vv  (τ) respectively represent the auto-correlation functions of w and of v; and
 
Φ ww ( f )=| H ( f )| 2 ·Φ vv ( f )  (3)
 
   in which Φ ww (f) and Φ vv (f) respectively represent the power spectral densities of φ ww (τ) and φ vv (τ) that is to say their Fourier Transforms. 
   Since v is a pseudo random noise sequence with Gaussian distribution, its spectrum, that is to say the function Φ vv (f), has a substantially flat shape. On the other hand, once this sequence v is filtered by the filter  16 , the resulting sequence w exhibits a spectrum Φ ww (f) which is no longer flat on account of the term |H(f)| 2 . It is also important to note, so as to comprehend the rest of the invention, that knowledge of |H(f)| 2  (and by the same token, knowledge of the modulus of H(f): |H(f)|) does not make it possible to retrieve H(f) (and hence h) since there is an uncertainty with regard to the phase of H(f). 
   Returning to  FIG. 2 , the filtered pseudo noise sequence w is multiplied (multiplier  18 ) by the interleaved modulation sequence {tilde over (m)} and the resulting sequence, which constitutes the watermark, is added (adder  22 ) to the sequence of interleaved data x. 
   The output sequence from the adder  22  is denoted {tilde over (y)}={y p(n) } and satisfies the following equations (4) and (5):
 
 y   p(n)   =x   p(n)   +m   p(n) ·( h   n               v   n )  (4)
 
 {tilde over (y)}=ĩ+{tilde over (m)} ·( h             v )  (5)

   The power spectral density of the sequence of watermarked interleaved data {tilde over (y)} is given by the following equations (6) and (7):
 
Φ {overscore (yy)} ( f )=Φ {overscore (II)} ( f )·Φ {overscore (mm)} ( f )·Φ h               v ( f )  (6)

   
     
       
         
           
             
               
                 
                   
                     Φ 
                     
                       yy 
                       _ 
                     
                   
                   ⁡ 
                   
                     ( 
                     f 
                     ) 
                   
                 
                 = 
                 
                   
                     ( 
                     
                       
                         
                           μ 
                           x 
                           2 
                         
                         · 
                         
                           δ 
                           ⁡ 
                           
                             ( 
                             f 
                             ) 
                           
                         
                       
                       + 
                       
                         σ 
                         x 
                         2 
                       
                     
                     ) 
                   
                   + 
                   
                     ( 
                     
                       
                         σ 
                         m 
                         2 
                       
                       · 
                       
                         σ 
                         v 
                         2 
                       
                       · 
                       
                         
                           ∑ 
                           u 
                         
                         ⁢ 
                         
                           h 
                           u 
                           2 
                         
                       
                     
                     ) 
                   
                   + 
                   
                     
                       μ 
                       m 
                       2 
                     
                     · 
                     
                       σ 
                       v 
                       2 
                     
                     · 
                     
                       
                          
                         
                           H 
                           ⁡ 
                           
                             ( 
                             f 
                             ) 
                           
                         
                          
                       
                       2 
                     
                   
                 
               
             
             
               
                 ( 
                 7 
                 ) 
               
             
           
         
       
     
   
   In equation (7), μ j  and σ j  respectively represent the mean and the standard deviation of the sequence j={j n } with j ε {x, m, v}, δ(f) corresponds to the Dirac pulse and the expression 
           (       σ   m   2     ·     σ   v   2     ·       ∑   u     ⁢     h   u   2         )         
is equal to a constant.
 
   The sequence of watermarked interleaved data {tilde over (y)} is then transmitted to an inverse interleaver  24  which performs the operation inverse to the permutation p performed by the interleavers  20  and  14  so as to supply a sequence of watermarked data y={y n } whose coefficients are in the same order as the initial order of the data x={x n }. 
   A transformation inverse to that performed by the transformation module  10  is then performed by the module  26  so as to obtain the marked content (or watermarked content) which is thus protected against illicit copying without the watermark being perceptible within the content. 
   We shall now describe, in conjunction with  FIG. 3 , a device for detecting a watermark in a received content when this watermark has been inserted into a content to be protected by a device such as that of  FIG. 2 . 
   The principle of the detection is based on the spectral analysis of the signal received. 
   The signal received is representative of the received content for which one will seek to determine whether or not it is watermarked. This content is of the same type as the content to be protected described previously. In the example which follows, it will be assumed that the content received is an image containing N pixels. 
   The content received is firstly transmitted to a transformation module  30  which performs the same transformation operation as the module  10  of the watermark insertion device of  FIG. 2  so as to supply a data sequence r={r n }, ∀n ε [1 . . . N] representing the content received. In our example, it is assumed that the luminances r n  of the pixels of the image received are obtained as output from the transformation module  30 . 
   If the content received were to correspond exactly to the watermarked content emanating from the device of  FIG. 2 , that is to say if no transformation or distortion of the signal had taken place during transmission between the watermark insertion device and the detection device, then one would have:
 
 r={r   n   }=y={y   n }
 
   In practice, this is not always the case since the signal sometimes undergoes transformations during its transmission. 
   Since the watermark has been inserted, in the device of  FIG. 2 , into a sequence of interleaved data {tilde over (x)}, the data sequence r will, in order to detect the possible presence of a watermark in the content received, be transmitted to an interleaver  32  performing the same permutation p of the coefficients r n  as that performed by the interleavers  20  and  14  of  FIG. 2 . 
   A sequence of interleaved data {tilde over (r)}={r p(n) } is obtained as output from the interleaver  32 . 
   It was seen previously that when the watermark inserted is a pseudo noise sequence filtered by a filter with impulse response h and with spectral response H(f), the power spectral density of the (interleaved) data obtained {tilde over (y)} is expressed by relations (6) and (7). 
   The purpose of the interleaving of the data sequence x and of the modulation sequence m will now be apparent. Indeed, if the data sequence x represents the pixels of an image, its spectral density has a very structured shape with very large amplitude differences. The role of the interleaving of the data is to sever the statistical coherence of this sequence so that the spectral density of the sequence of interleaved data {tilde over (x)} has a substantially flat shape, such as that of a pseudo noise sequence with Gaussian distribution. 
   Thus, if a watermark consisting of a pseudo noise sequence filtered by a filter with spectral response H(f) is added to this interleaved sequence, a data sequence is obtained whose power spectral density can be expressed by relation (7) in which the significant term |H(f)| 2  can be detected. 
   The principle of the detection will therefore be based on the spectral analysis of the sequence {tilde over (r)} and on a Maximum Likelihood Ratio Hypothesis test (MLR Hypothesis test), the hypothesis tested being the following: if the sequence of interleaved data {tilde over (r)} contains noise, is it noise which has been filtered by a filter whose spectral response has a modulus similar to |H(f)|? If the response is yes, one will deduce from this that the noise present in the sequence {tilde over (r)} is a watermark and, in the contrary case, one will conclude from this that the content received was not watermarked. 
   In practice, this analysis is based on calculations relating to spectral analysis and the likelihood testing of hypotheses which are described in detail in the work by K. Dzhaparidze, “ Parameter Estimation and Hypothesis Testing in Spectral Analysis of Stationary Time Series ”, Springer Series in Statistics, Springer-Verlag, 1986, to which reference may be made for further details. 
   Returning to  FIG. 3 , the sequence of received interleaved data {tilde over (r)} is transmitted to a module  34  performing a Periodogram calculus. This calculus is aimed at estimating the power spectral density of the sequence {tilde over (r)}. A quantity I N (f) given by the following relation (8) 
                     I   N     ⁡     (   f   )       =       1   N     ⁢              ∑     k   =   1     N     ⁢         r   ~     k     ·     exp   ⁡     (     2   ⁢   π   ⁢           ⁢   j   ⁢           ⁢   f   ⁢           ⁢   k     )                2               (   8   )               
is obtained at output.
 
   This quantity is then transmitted to a module  36  performing a MLR Hypothesis test so as to determine whether the content received is watermarked (output response “Y”) or not (output response “N”) 
   The module  36  tests the likelihood of two hypotheses: 
   according to the first hypothesis G 0 , the content received is not watermarked, hence the spectral density of the sequence {tilde over (r)} is substantially flat and can be estimated via the following relation (9):
 
 g   0 ( f )=σ r   2   +μ   r   2 ·δ( f )  (9)
 
   according to the second hypothesis G 1 , the content received is watermarked and the spectral density of the sequence {tilde over (r)} can be estimated via the following relation (10):
 
 g   1 ( f )=μ m   2   ·σ   r   2   ·|H ( f )| 2   +C   (10)
 
   in which C is a constant and σ v  is equal to 1 (one preferably chooses the pseudo noise sequence v at the level of the insertion device so that σ v  is equal to 1, but one may equally choose other values). Furthermore, μ m  is normed at the level of the insertion device and equals for example 3. 
   To estimate the likelihood of the hypotheses G 0  and G 1 , the module  36  calculates two numbers U N,0  ({tilde over (r)}) and U N,1 ({tilde over (r)}) representing the likelihoods of the hypotheses G 0  and G 1  according to the following relation (11): 
   
     
       
         
           
             
               
                 
                   
                     U 
                     
                       N 
                       , 
                       1 
                     
                   
                   ⁡ 
                   
                     ( 
                     
                       r 
                       ~ 
                     
                     ) 
                   
                 
                 = 
                 
                   
                     - 
                     
                       
                         ∫ 
                         
                           - 
                           
                             1 
                             2 
                           
                         
                         
                           1 
                           2 
                         
                       
                       ⁢ 
                       
                         
                           ( 
                           
                             
                               log 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 
                                   g 
                                   i 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   f 
                                   ) 
                                 
                               
                             
                             + 
                             
                               
                                 
                                   I 
                                   N 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   f 
                                   ) 
                                 
                               
                               
                                 
                                   g 
                                   i 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   f 
                                   ) 
                                 
                               
                             
                           
                           ) 
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           ⅆ 
                           f 
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         with 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         i 
                       
                     
                   
                   ∈ 
                   
                     { 
                     
                       0 
                       , 
                       1 
                     
                     } 
                   
                 
               
             
             
               
                 ( 
                 11 
                 ) 
               
             
           
         
       
     
   
   By then comparing these two numbers, the module  36  deduces from this: 
   if U N,1 ({tilde over (r)})&gt;U N,0 ({tilde over (r)}), then the response of the detector is “Y” signifying that the content received is watermarked; and 
   if U N,1 ({tilde over (r)})&lt;U N,0 ({tilde over (r)}), then the response of the detector is “N” signifying that the content received is not watermarked. 
   It is also possible, in a preferential manner, to calculate the difference (U N,1 ({tilde over (r)})&lt;U N,0 ({tilde over (r)}) and to perform the above comparisons only if this difference is greater than a predetermined threshold, this being so as to guarantee better exactness of detection. 
   The watermark insertion and detection methods just described with reference to  FIGS. 2 and 3  make it possible to produce a novel watermarking system which is illustrated by  FIG. 4 . In this novel system and according to a preferred aspect of the invention, a parameter which is referred to as the “private key” K PRI  is used for the insertion ( 100 ) of a watermark W into a content C, whereas another parameter which is referred to as the “public key” K PUB  is used for the detection ( 200 ) of a watermark in a content received CT. The terms “private key” and “public key” are used by analogy with public key crytographic systems. It will be noted that here the watermark W is binary, that is to say that, either the content C is watermarked, or it is not, but W does not contain any item of its own. 
   In the embodiment described above, the private key K PRI  is formed by the pseudo random noise sequence v as well as by the impulse response h of the filter  16  ( FIG. 2 ). The sequences v={v n } and h={h n } are in effect indispensable to the calculation of the sequence w={w n } which is itself, after having been multiplied by the interleaved modulation sequence {tilde over (m)}, inserted into the data representing the content to be protected. 
   The public key used to detect the watermark in the content received is for its part formed from the modulus of the spectral response of the filter  16  |H(f) |. Indeed, in the spectral analysis calculations performed (modules  34  and  36  of  FIG. 3 ) to detect the presence of a watermark in a content received CT, only the knowledge of |H(f)| is necessary. In particular, it is not necessary to know v and h (the private key) to perform the detection of the watermark. In actual fact, as was seen earlier in the description, the knowledge of |H(f)| does not suffice to know H(f) and hence h. 
   A system is therefore obtained in which knowledge of the public key does not make it possible to deduce the private key from this. Also, not knowing the private key, it is impossible for the device performing the detection of the watermark to delete it or to modify it. The detection can therefore be performed in a non-secure environment with no risk of the watermark being erased.