Abstract:
Watermark data consisting of known two-dimensional codeword patterns are added to a first portion of each video frame by modifying parameters defining the first portion. Limited randomization of the spatial position of the codeword pattern is also provided. During a decoding process, a predictor continuously estimates the current value of the modified parameters. In one embodiment of the present invention, the predictor employs video samples taken from unmodified areas of the frame to provide the estimates. The estimated parameter values are subtracted from the actual parameter values to provide an error signal. Multiple correlators attempt to detect the presence of the codeword pattern in the error signal within a range of spatial locations surrounding a nominal position of the codeword pattern. The use of multiple correlators provides immunity to feasible attacks aimed at damaging or obscuring the watermark.

Description:
TECHNICAL FIELD 
     The present invention relates generally to steganography and, in particular, to techniques for embedding data in a video signal and for detecting the presence of such embedded data in a video signal. 
     BACKGROUND OF THE INVENTION 
     Steganographic techniques, as known in the art, generally attempt to hide one piece of information within another. Within the broad field of steganography, the ability to embed ancillary data in analog or digital data representing video or graphics has a number of uses. Such systems ideally hide authentication or other data in a data stream or store in such a way as to allow the data stream or store (for example a graphics file on a floppy disk or a video-tape) to function normally and without indicating the presence or absence of the embedded data. Toward the end of aiding in the identification of copyright infringement or source identification, technology that allows authentication data to be carried by the data itself is useful. Employing a video image or stream of images to serve as a “carrier” for embedded data is also useful for annotating and indexing the carrier data itself. An example, called digital watermarking, is a technique that modifies data representing a video image or stream of images in such a way that the modifications are essentially undetectable. 
     Various methods have been used in the past to “hide” digital information in a video signal. In many cases, the added data is associated with the video, but is not part of the video image itself For example, in U.S. Pat. No. 5,737,026 issued Lu et. al., the added data is encoded in an overscan region of the video signal, and therefore can be removed without affecting the video images. Such systems are clearly unsuitable for copyright protection where the added data must be substantially indelible. In other cases, the watermark data is encoded into the video in such a simple manner that straightforward methods may be used to detect and remove the data thereby destroying the watermark. For example, the “fingerprint” apparatus of U.S. Pat. No. 5,668,603 issued to Copeland et al. communicates each bit by raising or lowering the video set-up by 0.5 IRE for a complete field. 
     In U.S. Pat. No. 3,984,624 issued to Waggener et al., data is added to the video signal in randomized positions, making the data difficult to remove. However, no attempt is made in this case to hide the video data from the viewer, and the digital signature therefore impairs the video to some degree. A method for hiding data in a video data stream is disclosed in U.S. Pat. No. 4,969,041 issued to O&#39;Grady, et al. A low-level waveform is added to the video signal during the active video portion of the video signal. The low-level waveform can be any unique waveform, such as a set of random noise waveforms that are unlikely to occur in a normal video signal, each of which represents a unique digital data word. The low-level waveform to be embedded in the video signal has levels significantly below the noise level of the video signal. The low-level waveform is detected by correlating the video signal with all of the unique waveforms, or with a desired one of the unique waveforms if a particular data word is sought. The video signal is multiplied by each waveform, or with the desired waveform, and the result is compared with a threshold value to determine a correlation coefficient for each waveform. This technique, however, is vulnerable to attack in that the video image can be modified in such a way as to make the signal uncorrelatable with the standard waveforms. For example, an adverse party could zoom the video images to distort the embedded signal to the point that it is no longer recognizable without destroying the image. 
     While the foregoing discussion of prior art techniques does not represent an exhaustive review of the state of the prior art, it does point out the shortcomings of current techniques. In particular, a need exists for a simple technique for embedding data in a video signal that minimizes the impact on the quality of the video signal, that is substantially impervious to attempts to remove or obscure the embedded data, and that provides for straightforward detection of the embedded data. 
     SUMMARY OF INVENTION 
     These needs and others are substantially met by the present invention. Generally, the present invention provides a technique for embedding data (a “watermark”) in a video signal. The watermark may be used to identify the source and/or the owner of the information in the video signal. The encoded video signal meets all broadcast and studio specifications, and has no visible impairments. Attempts to obscure or remove the embedded data by adding noise, coring, cropping or warping the image will damage the video to an unacceptable degree before the watermark is eliminated. The method is cascadable, and survives digital compression and/or conversion to analogue. 
     A low-level digital signal is added to a parameter defining the video signal. The watermark data consists of known two-dimensional codeword patterns that are added to portions of each video frame, and covering a large proportion of the frame. The portions can be, for example, alternate lines or alternate fields. The codeword patterns consist of relatively few bits per frame so that each bit of a codeword covers a significant portion of the frame. Therefore only low spatial frequencies are present in the codeword patterns. Limited randomization of the spatial position of the codeword pattern is also employed. By altering a polarity of a codeword pattern, binary data can be communicated on a per frame basis. 
     Detection of the codeword pattern is accomplished by a two step process. In the first step, a predictor is employed that continuously estimates the current value of the modified parameter. In one embodiment of the present invention, the predictor employs video samples taken from unmodified areas of the frame (areas to which no data has been added, e.g., alternate lines or fields) to provide the estimates. The estimated parameter values are then subtracted from the actual parameter values constituting the video signal, thereby producing a low-amplitude noise-like signal containing the embedded watermark data. In the second step, multiple correlators attempt to detect the presence of the codeword pattern in a range of spatial locations surrounding its nominal position in the image frame. The use of multiple detectors (spatially offset from the original codeword location) provides immunity to feasible attacks aimed at damaging the watermark, i.e., levels of zoom, cropping or warping of the signal (short of destroying the video signal) do not materially affect the delectability of the mark. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a flowchart illustrating a method for embedding data in a video signal in accordance with the present invention. 
     FIG. 2 illustrates a video frame in which a pattern comprising multiple zones has been established in accordance with the present invention. 
     FIG. 3 illustrates the pattern of FIG. 2 after various horizontal offsets have been applied thereto. 
     FIG. 4 is a block diagram of an apparatus for detecting the presence of data embedded in a video signal in accordance with the present invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The present invention may be more fully described with reference to FIGS. 1-4. FIG. 1 illustrates a method whereby data can be embedded in a video signal. Preferably, the steps illustrated in FIG. 1 are implemented using a dedicated hardware platform. In one embodiment, it is anticipated that a customized integrated circuit could be used. Alternatively, given current capabilities, a microprocessor-based computer executing suitably adapted software to operate on stored digitally-represented video data could be used. Those having ordinary skill in the art will recognize that the method described in FIG. 1 could be easily implemented to accommodate various video formats (e.g., analog video). At step  101 , a pattern representing a fixed-length codeword and comprising at least one zone is defined. Typically, the pattern will be defined prior to encoding the video to include the watermark. An exemplary pattern is illustrated in FIG.  2 . 
     In particular, FIG. 2 illustrates a video frame  201  in which a pattern  203  has been logically established. That is, in the context of the present invention, the pattern is never actually added to a video frame thereby altering the image provided by the frame, but is only established in a logical sense. The pattern  203  comprises multiple zones  205 , in this case labeled  1  through  18 . The pattern  203  corresponds to an 18-bit codeword, with each bit of the 18-bit codeword uniquely corresponding to one of the zones  205  defining the pattern  203 . For example, the least significant bit of the codeword can correspond to the zone labeled  1 , the most significant bit can correspond to the zone labeled  18 , with those bits between the least significant and most significant bits corresponding to like-numbered zones. Of course, the length of a given codeword, and the particular correspondence between codeword bits and zones is a matter of design choice. It is anticipated that codewords will typically be in the range of 16-24 bits in length with each zone  205  covering a significant portion of the frame  201 . The pattern  203  is assumed to have a nominal position within the frame such that spatially offset versions of the pattern  203  can be derived automatically, as discussed below. 
     Referring again to FIG. 1, at step  102 , a new video frame is provided. Video frames are well known in the art and typically comprise enough video information to fill a standard display screen. At a minimum, the format of the video frames is such that data can be encoded into a component of the video frame, e.g., a luminance component, and be able to withstand conversions between formats. Also at step  102 , a spacial offset for the pattern  203  is determined. FIG. 3 illustrates the effect of introducing various random horizontal offsets, limited in magnitude to one horizontal bit position, relative to a nominal position  301  for a given pattern. That is, assuming that the nominal position  301  may be defined by coordinates represented by fixed-length binary words, a one-bit difference from the nominal position  301  corresponds to a pattern having coordinates that differ in one bit position in the horizontal and/or vertical directions. For example, the spatially offset pattern identified by reference numeral  303  is shifted horizontally one bit position relative to the nominal position  301 . Although not shown in FIG. 3, vertical offsets are likewise possible. The spacial offset determined at step  102  is relative to the nominally-positioned pattern  301 . By randomly offsetting the pattern in this manner, the present invention offers protection against attempts to detect and remove the watermark based on a fixed-position pattern. 
     Referring again to FIG. 1, at step  103  it is determined whether any more bits constituting the codeword remain to be embedded in the current frame. If not, it is determined if there are any more frames to be processed at step  104 . If no more frames need to be processed, the method ends. If more frames are to be processed, the method returns to step  102 . Where bits remain to be embedded in the current frame (step  103 ), the corresponding zone is ascertained at step  105 . Because the particular correspondence between zones and codeword bits is a matter of design choice, the zone ascertained at step  105  need not be contiguous with, or even close to, the previous zone. Regardless, at step  106 , parameters defining a first portion of the zone are modified in accordance with a modification value of the bit. As contemplated by the present invention, each zone within a pattern is composed of at least two separate portions. In one embodiment, separate portions of a zone comprise alternate lines or fields, as known in the art, encompassed within the logical borders of that zone. For example, if a zone is divided into two separate portions, every other line within the borders of the zone could be defined as forming the first portion, and the remaining lines forming the second portion. Of course, other methods of defining such portions are readily determinable and are a matter of design choice. Regardless of the manner in which the respective portions of each zone are defined, the present invention embeds the codeword bits into the video signal by modifying parameters defining the first portion of each zone. For example, assuming that alternate lines are used within each zone, and that luminance parameters are being used to convey the watermark data, a “modification value” (described in further detail below) is added to each luminance parameter defining the alternate lines. In another embodiment, it is possible that the modification value could be added to the first portion of a zone (e.g., alternate lines) and subtracted from a second portion of the zone (remaining lines). 
     Preferably, the parameters modified at step  106  is at least one of a luminance and a chrominance parameter. Luminance and chrominance parameters with regard to video signals are well known in the art and will not be discussed in further detail here. These parameters are modified by adding a modification value corresponding to the bit to be embedded. For example, a bit having a high value (e.g., “1”) will have a corresponding modification value of 0.25 IRE (Institute of Radio Engineers Scale unit; 140 IRE=1 volt p-p) and a bit having a low value (e.g., “0”) will have a corresponding modification value of −0.25 IRE. The amplitude of the modification value is a matter of design choice, but is preferably chosen to be a very low level relative to “typical” video signal levels. Likewise, the polarity (+/−) assigned to high and low level bits can be varied according to the requirements of the system. It should be noted that codewords preferably comprise an equal number of high value and low value bits; for example, an 8-bit codeword of 11010100 is preferred over a codeword of 11011100. Steps  103  through  106  are repeated until all of the bits of a codeword have been embedded in their respective zones, thereby effectively embedding the entire codeword into the current frame. 
     It is further understood that separate values can be conveyed on a per frame basis by altering the polarity of the codeword. In this manner, successive frames can be used to convey a string of individual bits. For example, assume that an 8-bit codeword represented as 10110100 is to be added to each frame in a video signal. When a high bit value is to be conveyed in a given frame, the codeword 10110100 (positive polarity) is added to that frame. Conversely, when a low bit value is to be conveyed, the codeword 01001011 (negative polarity; complement of the positive polarity codeword) is added to the frame. Based on the present method for detecting codewords, discussed in further detail below, the polarity of the codeword detected within a frame will indicate the value of the bit conveyed in that frame. 
     Referring now to FIG. 4, there is shown a block diagram of a decoder  400  capable of detecting a watermark embedded in a video signal in accordance with the present invention. The functionality of the various components making up the decoder  400 , as described below, may be implemented using a hardware and software techniques, or a combination thereof, known to those having ordinary skill in the art. A receiver  401  takes as input a video input signal and provides a frame  402  as output. Preferably, the output of the receiver  401  comprises the luminance or chrominance parameters (i.e., all parameters, both modified and unmodified, used in the conveyance of the watermark data) of the frame data  402 . Assuming that a watermark has been embedded in the video signal, various segments of the frame data  402  should correspond to zones of the known pattern. A separator  403  is provided to direct a first portion  404  and a second portion  405  of the video signal along separate paths. As described above, the first portion  404  and the second portion  405  may comprise alternate lines or fields of the frame  402 . The first portion  404  of each frame is presumed to be functioning as the “carrier” of embedded watermark data, if any, and the second portion of each frame is presumed to have been unmodified by any watermark encoding process. The second, or unmodified, portion  405  is directed to a predictor  406  as shown. 
     The predictor  406  takes as input the second portion  405  and provides an estimate  407  of parameters defining the first portion  404 . The first portion  404  and the estimate  408  are provided to a subtractor  408  which calculates a difference between the first portion  404  and the estimate  407 . For example, assume that the watermark encoding process modifies the luminance parameters corresponding to the first portion  404  of each zone. Further assume that the first and second portions of each zone correspond to alternate lines within each zone. Thus, the separator  403  will provide that data defining those lines that were not modified during the encoding process to the predictor, whereas the data defining those lines that were modified during the encoding process (the first portion) is provided directly to the subtractor. The predictor  406  calculates the estimate  407  of the data defining the modified lines based on the data defining the unmodified lines. In one embodiment of the present invention, this is accomplished by selecting, from the data defining the modified lines, a first datum having a unique spatial location relative to the overall frame, i.e., a single luminance data point corresponding to a given pixel in a given line. A second datum from the unmodified lines, being in closest proximity to the first datum, is also selected and output by the predictor as the estimate of the first datum, i.e., a second luminance data point corresponding to another pixel from a line adjacent to the given line and closest to the given pixel. This process is repeated for all of the data corresponding to first and second portions, i.e., alternate lines, within the frame data  402 . The output of the subtractor  408 , then, is a difference or error signal  409  comprising the embedded data, if any. It is understood that other, more sophisticated techniques could be used to provide the estimate  407 . 
     Either at the request of an operator or automatically, a microprocessor  423  programs a codeword generator  411  with a known pattern signal (codeword). Based on the known pattern signal, the codeword generator  411  generate the codeword pattern  412  corresponding to a known starting position, which may or may not be equivalent to the nominal position of the codeword pattern. For example, assuming that the pattern  203  shown in FIG. 2 is located at its nominal position, and that such a pattern is being searched for in the video signal being analyzed in FIG.  4 . In this case, the codeword pattern  412  would comprise data that is time-aligned with the error signal  409  to correspond to where one would expect watermark data to be embedded in the video signal based on the nominally positioned pattern  203 . The alignment between the codeword pattern  412  and the error signal  409  is maintained by the horizontal and vertical counters  413 ,  415 . Furthermore, delay elements  417  introduce vertical and horizontal delays to the codeword pattern  412  to produce a variety of spatially offset codeword patterns  414  relative to the known starting position. The codeword pattern  412  and spatially offset codeword patterns  414  are provided as one set of inputs to correlators, whereas the error signal  409  is provided as the other input to each of the correlators. In order to simplify the overall operation of the decoder  400 , only the positive polarity version of the codeword pattern  412  is generated. 
     As shown, each correlator comprises a programmable adder/subtractor  419  and a register  421 . Although four correlators are shown in FIG. 4, a larger or smaller number may be provided as required, preferably to match the number of possible spatially offset codeword patterns. Operating in accordance with well-known principles, the correlators compute correlations  422  that are subsequently stored in the registers  421  and provided as input to a multiplexer  425 . At the end of each frame, as delineated by the frame data  402 , the microprocessor  423  addresses the multiplexer  425  and reads the correlations  422  via a data bus  427 . Each correlation  422  gauges the degree of similarity between a version of the known codeword pattern (nominally positioned or spatially offset) and the error signal  409 . 
     Operating in accordance with stored software algorithms, the microprocessor  423  searches through all of the correlations  422  to select that correlation having the highest absolute value. The correlation having the highest absolute value will correspond to that version of the codeword pattern  412  that is most similar to the error signal  409 . The selected correlation is then compared to a correlation threshold. For example, assuming that the absolute values of the correlations  422  are normalized between 0 (indicating perfectly uncorrelated signals) and 1 (indicating perfectly correlating signals), the correlation threshold could be set to 0.85. In this case, if the absolute value of the selected correlation falls below 0.85, it is assumed that the watermark was not present within the frame currently being analyzed. Conversely, if the absolute value off the selected correlation is above 0.85, indicating a relatively high degree of correlation, then the watermark is deemed to be present in the frame currently being analyzed. The sign (+/−) of the selected correlation will then indicated whether a codeword having a positive or negative polarity was embedded in the frame, thereby indicating the value of the single data bit conveyed in that frame. If the embedded watermark data is found in a certain proportion of frames, then the video signal is deemed to have the watermark embedded therein and the microprocessor can generate such an indication. Furthermore, those bits received on a frame basis can be further processed (decrypted, error corrected, etc.) as needed an presented to an operator of the decoder. For example, it is anticipated that the bits conveyed on a frame basis can carry information identifying a copyright owner of the content of the video signal, or similar information. 
     What has been described is merely illustrative of the application of the principles of the present invention. Other arrangements and methods can be implemented by those skilled in the art without departing from the spirit and scope of the present invention.