Patent Publication Number: US-7221774-B2

Title: Local phase filter to assist correlation

Description:
TECHNICAL FIELD OF THE INVENTION 
   The present invention relates generally to the detection of imperceptible watermark patterns in data and, in particular, to the local enhancement and restoration of phase information of an embedded watermark, thereby assisting the detection of the watermark pattern using correlation. 
   BACKGROUND 
   With the advent of digital multimedia data and digital multimedia data distribution, protection of such digital multimedia data against unauthorised copying and dissemination have become an issue for multimedia data publishers and authors. One technique used to identify ownership is to embed a pattern or patterns into the data, such that the embedded pattern is typically imperceptible to an observer. Such a pattern is called a watermark pattern, or simply a watermark. The presence of the watermark pattern can be detected in copied data by the owner of the original data, thereby proving their ownership. 
   A difficulty arises with respect to embedding watermark patterns into the data in such a way that the watermark patterns are both imperceptible to the human senses, and for each embedded watermark pattern to be reliably detected. In general, the watermarked data may be transformed or processed, making the detection of the watermark patterns more difficult to reliably detect. Processing that is often applied to image data is printing and then subsequent scanning of the printed image. During the printing and scanning processes, the high frequency components of the watermark pattern are often attenuated. Other processing that typically adversely affects the reliable detection of the watermark pattern includes interpolation during image rotation or scaling, or even malicious attack. 
   Several watermarking schemes use spread-spectrum signals as watermark patterns. Two advantages of using spread-spectrum signals as watermark patterns are the very sharp peaks obtained when using correlation to detect the watermark pattern, and also the presence of relatively large high-frequency components, which are generally less perceptible than low frequencies. 
   Because images commonly contain a predominance of low frequencies, direct correlation of a watermarked image with the spread-spectrum embedding watermark pattern will be dominated by the low frequencies of the image, resulting in a blurred correlation image in which correlation peaks, corresponding with the positions where the watermark patterns were embedded in the image, may not be discernible. 
   A related problem is the problem of correlation of data features with the watermark pattern during correlation, also causing interference. While usually not a problem with pseudo-random noise watermarks, this can be a problem with watermark patterns based upon logarithmic radial harmonic functions. For example, if the features of an image contain strong curved fringes, such as an image of spiral sea shells, additional noise may be caused during correlation of such an image with a logarithmic radial harmonic function based watermark pattern, which may obscure the correlation peaks. 
   Occasionally special forms of correlation are used to address this problem and restore the peaks. 
   One such special form of correlation is frequency pre-emphasis of the watermarked data before correlation with the watermark pattern. A linear or quadratic scaling factor applied to the high frequencies will reduce the influence of the data&#39;s low frequencies, and increase the influence of the flat spectrum of the watermark patterns, resulting in sharp, visible detection peaks. 
   Another special form of correlation often used is phase correlation in which all frequency components are set to a constant amplitude in the Fourier domain during correlation of the watermarked data with the watermark pattern. Because phase correlation weights all frequencies equally, it has the additional advantage of restoring the high frequency components of the embedded watermark patterns where they have been attenuated. 
   Although very effective in enhancing correlation peaks and reducing interference from the data, phase correlation and frequency emphasis are inherently applied equally over all data samples of the watermarked data, and are thus completely insensitive to any local variations in the watermarked data. 
   SUMMARY OF THE INVENTION 
   It is an object of the present invention to substantially overcome, or at least ameliorate, one or more disadvantages of existing arrangements. 
   According to a first aspect of the invention, there is provided a method of pre-processing data including a watermark before detecting said watermark by correlating said data with said watermark, said method comprising the steps of: 
   (a) dividing said data into a plurality of sub-spaces, each sub-space being associated with a position within said data; 
   (b) for each sub-space, spectral shaping frequency amplitudes of the data of said sub-space to a predetermined function; and 
   (c) adding said data of said sub-spaces at positions corresponding with said sub-space positions. 
   According to another aspect of the invention, there is provided an apparatus for implementing the aforementioned method. 
   According to another aspect of the invention there is provided a computer program product including a computer readable medium having recorded thereon a computer program for implementing the method described above. 
   Other aspects of the invention are also disclosed. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     One or more embodiments of the present invention will now be described with reference to the drawings, in which: 
       FIG. 1  is a schematic block diagram of a general purpose computer system upon which arrangements described can be practiced; 
       FIG. 2A  shows a schematic diagram of a process of watermarking data with a watermark pattern; 
       FIG. 2B  shows a schematic diagram of an alternative process of watermarking data in which an adaptive watermark embedding scheme is used; 
       FIG. 3  shows a schematic diagram of a process of detecting a watermark pattern in watermarked data; 
       FIG. 4  shows a flow diagram of the steps performed by a pre-filter; 
       FIG. 5  shows an example of a 128×128-pixel image and its division into 9 overlapping sub-spaces, 
       FIG. 6A  shows example one-dimensional data; 
       FIG. 6B  shows an example watermark pattern; 
       FIG. 6C  shows one-dimensional watermarked data formed by embedding the example watermark pattern of  FIG. 6B  into the example one-dimensional data of  FIG. 6A ; and 
       FIG. 6D  shows one-dimensional watermarked data formed by adaptively embedding the example watermark pattern of  FIG. 6B  into the example one-dimensional data of  FIG. 6A . 
   

   DETAILED DESCRIPTION INCLUDING BEST MODE 
   Where reference is made in any one or more of the accompanying drawings to steps and/or features, which have the same reference numerals, those steps and/or features have for the purposes of this description the same function(s) or operation(s), unless the contrary intention appears. 
   Some portions of the description which follows are explicitly or implicitly presented in terms of algorithms and symbolic representations of operations on data within a computer memory. These algorithmic descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. An algorithm is here, and generally, conceived to be a self-consistent sequence of steps leading to a desired result. The steps are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated. It has proven convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like. 
   It should be borne in mind, however, that the above and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. 
     FIG. 1  is a schematic block diagram of a general-purpose computer system  100 . The computer system  100  comprises a computer module  101 , input devices such as a scanner  114 , a keyboard  102  and mouse  103 , and output devices including a printer  115  and a display device  116 . A Modulator-Demodulator (Modem) transceiver device  117  is used by the computer module  101  for communicating to and from a communications network  120 , for example connectable via a telephone line  121  or other functional medium. The modem  117  can be used to obtain access to the Internet, and other network systems, such as a Local Area Network (LAN) or a Wide Area Network (WAN). 
   The computer module  101  typically includes at least one processor unit  105 , a memory unit  106 , for example formed from semiconductor random access memory (RAM) and read only memory (ROM), input/output (I/O) interfaces including a video interface  107 , and an I/O interface  113  for the keyboard  102  and mouse  103 , and an interface  108  for the modem  117 , the printer  155  and the scanner  114 . A storage device  109  is provided and typically includes a hard disk drive  110  and a floppy disk drive  111 . A CD-ROM drive  112  is typically provided as a non-volatile source of data. The components  105  to  113  of the computer module  101 , typically communicate via an interconnected bus  104  and in a manner which results in a conventional mode of operation of the computer system  100  known to those in the relevant art. 
     FIG. 2A  shows a schematic diagram of a process  200  of watermarking data  205  with a watermark pattern  210 . Process  200  is preferably practiced using the general-purpose computer system  100  ( FIG. 1 ), wherein the steps of process  200  may be implemented as software, such as an application program executing within the computer system  100 . In particular, the steps of process  200  are performed by instructions in the software that are carried out by the computer system  100 . Typically, the application program is resident on the hard disk drive  110  and read and controlled in its execution by the processor  105 . Intermediate storage of the program and any data fetched from the network  120  may be accomplished using the semiconductor memory  106 , possibly in concert with the hard disk drive  110 . 
   The application program may be supplied to the user encoded on a CD-ROM or floppy disk and read via the corresponding drive  112  or  111 , or alternatively may be read by the user from the network  120  via the modern device  116 . Still further, the software can also be loaded into the computer system  100  from other computer readable media The term “computer readable medium” as used herein refers to any storage or transmission medium that participates in providing instructions and/or data to the computer system  100  for execution and/or processing. Examples of storage media include floppy disks, magnetic tape, CD-ROM, a hard disk drive, a ROM or integrated circuit, a magneto-optical disk, or a computer readable card such as a PCMCIA card and the like, whether or not such devices are internal or external of the computer module  101 . Examples of transmission media include radio or infra-red transmission channels as well as a network connection to another computer or networked device, and the Internet or Intranets including e-mail transmissions and information recorded on websites and the like. 
   The process  200  may alternatively be implemented in dedicated hardware such as one or more integrated circuits performing the functions or sub functions of process  200 . Such dedicated hardware may include graphic processors, digital signal processors, or one or more microprocessors and associated memories. 
   Referring again to  FIG. 2A , the data  205  is typically one-dimensional data, such as audio data, two-dimensional data, such as image data, or three-dimensional data, such as data for a video sequence or for a tomographic scan. However, the data  205  may be data having any number of dimensions. 
   Preferably, the watermark pattern  210  when embedded into the data  205  is imperceptible to the human sensory system under normal conditions. For example, when the watermark pattern  210  is added to image data, then it is desirable for the pattern  210  to be invisible to the human visual system. Imperceptibility is achieved by multiplying  211  the watermark pattern  210  with a constant embedded factor  208  to form a low intensity copy  212  of the watermark pattern  210 . The low intensity copy  212  of the watermark pattern  210  is the simply added  206  to the data  205  to form watermarked data  220 . 
   If the data  205  is a colour image, then the watermark pattern  210  is added to the luminance part of the colour image. This allows the watermark to survive when the watermarked image is converted from colour to a greyscale representation. 
   The watermarked data  220  may be stored on the storage device  109  of the computer system  100 , transmitted to another computer system  100  through communications network  120  or, in the case of image data, printed on printer  115 . 
     FIG. 6C  shows one-dimensional watermarked data formed by adding the watermark pattern represented in  FIG. 6B  to the one-dimensional data shown in  FIG. 6A . The watermark pattern is perceptible in regions having low intensity variation, such as region  601 . 
   Often, even when the constant embedded factor  208  is small, making the level of the watermark pattern  210  significantly lower than that of the data  205  in the watermarked data  220 , the watermark pattern  210  is still perceptible in regions of the data  205  having low intensity variation. For example, in region  601  of the one-dimensional watermarked data shown in  FIG. 6C , and assuming the data is audio data, the watermark pattern would still be perceptible during the play-back of the audio data contained in region  601 . 
   An adaptive watermark embedding scheme, such as perceptual masking, is often used to reduce the level of the watermark in regions having low intensity variation and increase the level of the watermark in regions of high intensity variance. 
     FIG. 2B  shows a schematic diagram of an alternative process  250  of watermarking data  205  in which an adaptive watermark embedding scheme is used. A perceptual mask  260  is formed from the data  205 . The perceptual mask  260  may be formed by evaluation of the local gradient magnitude of the data  205 , such as the local gradient magnitude of the luminance in an image in the case where the data is image data. The perceptual mask  260  may alternatively be formed by evaluation of the second partial derivatives of the data; local estimates of the “energy” or frequency content, local variance, and more sophisticated estimates of human visual system masking. 
   The watermark pattern  210  is then de-emphasised with the perceptual mask  260  by multiplying  270  the values of the watermark pattern  210  with the corresponding values of the perceptual mask  260 . This de-emphasised pattern  265  is added  258  to the data  205  to form watermarked data  280 . 
     FIG. 6D  shows one-dimensional watermarked data formed by the adaptive scheme shown in  FIG. 2B . The watermark pattern would be less perceptible during the play-back of region  602 , which corresponds with region  601  in  FIG. 6C . 
   Before detection of the watermark pattern  210 , it is desirable to normalise the level of the embedded watermark pattern across the watermarked data  280 . Ideally, this normalisation should be performed by dividing the watermarked data  280  by the original perceptual mask  260 . However, because the original perceptual mask  260  may not be known during detection, it would necessary to compute an approximation based on the watermarked data  280 . 
     FIG. 3  shows a schematic diagram of a process  300  of detecting a watermark pattern in watermarked data  310 . The steps of process  300  are also implemented as software executing within the computer system  100 . In particular, the steps of process  200  are performed by instructions in the software which is typically resident on the hard disk drive  110  and read and controlled in its execution by the processor  105 . 
   The watermarked data  310 , formed using any one of watermarking processes  200  or  250 , may be scanned and stored onto the storage device  109 , or may be received from the communication network  120 . A pre-filter  315  is first applied to the watermarked data  310  to form filtered data  317 . The filtered data  317  is then simply correlated  325  with a candidate pattern  320  to form result data  330 . If the candidate pattern  320  is present in the watermarked data  310 , then the result data  330  will have correlation magnitude peak(s) at centre location(s) where that pattern  320  was embedded into the data  205 . 
     FIG. 4  shows a flow diagram of the steps performed by the pre-filter  315 . The pre-filter  315  aims to improve the detection of the embedded watermark pattern(s), and in particular embedded spread-spectrum watermark pattern(s). 
   The pre-filter  315  starts in step  402  where the watermarked data  310  is divided into a set of smaller sub-spaces. In the preferred implementation, adjacent sub-spaces overlap by half the sub-space&#39;s width for reasons that will be set out below.  FIG. 5  shows an example of a 128×128-pixel image  500 . In the example the image  501  is separated by step  402  into  9  overlapping sub-spaces  501  to  519 , each sub-space  501  to  519  having a size of 64×64 pixels The borders of the sub-spaces  501  to  519  are illustrated slightly adjacent the actual border in an attempt to distinguish each sub-space  501  to  519 . 
   In step  404  the processor  105 , for each sub-space, computes the frequency coefficients of the watermarked data contained in that sub-space, and then spectrally shapes the frequency amplitudes of the frequency coefficients. Preferably, the amplitudes of the frequency coefficients of the sub-space are set to a predetermined function. 
   The processor  105  determines in step  406  whether the amplitudes of the frequency coefficients of all the sub-spaces have been set to the predetermined function. 
   If sub-spaces remain that have not been processed using step  404 , then the pre-filtering step  315  returns to step  404  where the next sub-space is processed. The sub-spaces may be processed by step  404  in any order. 
   When the processor  105  determines in step  406  that the amplitudes of the frequency coefficients of all the sub-spaces have been set to the predetermined function, the pre-filter process  315  continues to step  408  where the processor  105  forms filtered watermarked data, having the same size as that of the watermarked data  310 , by adding the filtered data of each sub-space together in the sub-space&#39;s original position. 
   The preferred implementation of step  404  is now described in more detail. The Discrete Fourier Transform (DFT) is preferably used to compute the frequency coefficients of the watermark data contained in the sub-space being processed. However, because the Fourier transform wraps around at the edges of the data to which it is applied, edge effects, and in particular “ringing” artefacts at the edges of every sub-space, are introduced. These artefacts contain a substantial amount of energy not in the watermarked data  310 , and will add noise during any subsequent correlation. 
   To ameliorate these problems, windowing may be used to reduce data values near the edges of each sub-space, causing the wrapped edges of each sub-space to be more continuous. Preferably a Hanning window is applied to each sub-space in sub-step  410  of step  404 . In one-dimension and having sub-space size N samples, the Hanning window is defined as: 
   
     
       
         
           
             
               
                 
                   sin 
                   2 
                 
                 ⁡ 
                 
                   ( 
                   
                     
                       x 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       π 
                     
                     N 
                   
                   ) 
                 
               
             
             
               
                 ( 
                 1 
                 ) 
               
             
           
         
       
     
   
   where x is the sample offset of the data sample within the sub-space. Equivalently, in two-dimensions and having a sub-space size of N×N samples, the Hanning window is defined as: 
   
     
       
         
           
             
               
                 
                   
                     sin 
                     2 
                   
                   ⁡ 
                   
                     ( 
                     
                       
                         x 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         π 
                       
                       N 
                     
                     ) 
                   
                 
                 × 
                 
                   
                     sin 
                     2 
                   
                   ⁡ 
                   
                     ( 
                     
                       
                         y 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         π 
                       
                       N 
                     
                     ) 
                   
                 
               
             
             
               
                 ( 
                 2 
                 ) 
               
             
           
         
       
     
   
   where x and y are the horizontal and vertical sample offsets of the data sample within the sub-space respectively. 
   Applying the Hanning window to each sub-space results in the loss of a substantial part of the data, because the edges of each sub-space are zeroed or set to very small values. In order to compensate for this effect, overlapping sub-spaces are used in step  402 . In step  408  where the filtered watermarked data is formed by adding the filtered data of each sub-space together in the sub-space&#39;s original position, that is overlapping adjacent sub-spaces by half the sub-space&#39;s width, the data which is most attenuated in the adjacent sub-spaces will be centred in the overlapping sub-space. The Hanning window has the useful property of summing to a value of 1 when overlapped in this manner. 
   After the window function has been applied to the sub-space in sub-step  410 , sub-step  412  of step  404  then computes the DFT of the windowed watermarked data of that sub-space as is known in the art of signal processing. The modulus of each is frequency component in the Fourier transform, except the DC component, is then preferably set to 1 in sub-step  414  of step  404 . 
   Preferably, the DC component in the Fourier transform is set to 0, thereby removing the presence of a unit DC component, which will appear as a constant positive or negative offset within each sub-space. In the final sub-step of step  404 , that is sub-step  416 , the inverse Discrete Fourier Transform (IDFT) of the modified Fourier Transform data of that sub-space is calculated by the processor  105 . 
   It is noted that the sum of the overlapping sub-spaces and the use of the Hanning window results in pre-filtered data having levels similar to that of the watermarked data  310  except at the borders of the pre-filtered data. 
   Referring again to step  402  where the watermarked data  310  is separated into the set of smaller sub-spaces, the choice of sub-space size is a trade-off between two factors. If the sub-space size chosen is large, the local effect of the pre-filter  315  is reduced and, in the case where a window is applied, the window causes an amplitude reduction on the edges of the filtered watermarked data, where the edges are dependent on the sub-space size. Contrasted thereto, when the sub-space size chosen is small, the frequency spacings between frequency coefficients are larger. 
   Process  400  has similarities to phase correlation discussed in the Background section. However, using phase correlation, all spatial frequencies are normalised in the Fourier domain in the final stages of correlation. Process  400  including pre-filter  315  locally normalises spatial frequencies, while leaving the global phase information intact. 
   The foregoing describes only some embodiments of the present invention, and modifications and/or changes can be made thereto without departing from the scope and spirit of the invention, the embodiments being illustrative and not restrictive.