Patent Publication Number: US-7912244-B2

Title: Video fingerprinting using watermarks

Description:
RELATED APPLICATION 
     This application claims priority to U.S. patent application Ser. No. 11/256,642 to Mihcak et al. entitled, “Video Fingerprinting Using Watermarks,” filed on Oct. 21, 2005 and published as U.S. Patent Application Publication No. 20070092103, which is incorporated herein by reference. 
     BACKGROUND 
     Piracy is an increasing problem faced by video content owners, such as companies that produce, market, and distribute motion pictures. In some instances, the piracy takes the form of unauthorized duplication or leaking of video, whether voluntary or not. In other instances, the piracy can take the form of unauthorized adaptation, editing, or other transformation of the video. 
     In any event, the piracy may be an “inside job”, in the sense that persons associated with, for example, the companies that produce, market, and distribute the motion pictures may be involved with the acts that constitute video piracy. In such instances, it may be beneficial to identify the insiders who are engaging in or otherwise involved with video piracy, whether such involvement is voluntary or not. 
     SUMMARY 
     Video fingerprinting using watermarks is described herein. A watermark encoder embeds a watermark into an input video to produce a watermarked video. The watermark encoder can choose particular regions of the video that are sufficiently complex for watermarking. Spatial and temporal complexity analyses can be performed on a per-pixel basis to locate suitable regions of the video. The watermarks can be embedded using a unique codeword associated with a given user. 
     A watermark decoder can receive the watermarked video. In some instances, the watermarked video may have been attacked in some way after being output by the watermark encoder. In these instances, the watermark decoder can extract the watermark from the watermarked video. In turn, the watermark decoder can extract the codeword from the watermark, and compare the extracted codeword to a plurality of known codewords associated with respective users. 
     This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The detailed description is described with reference to the accompanying figures. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The use of the same reference numbers in different figures indicates similar or identical items. 
         FIG. 1  is a block diagram of an illustrative architecture for video fingerprinting using watermarks, providing illustrative components and data flows. 
         FIG. 2  is a block diagram of further components and data flows relating to a watermark encoder, as shown in  FIG. 1 . 
         FIG. 3  is a block diagram of further components and data flows relating to analyzing complexity of regions of video, as shown in  FIG. 2 . 
         FIG. 4  is a diagram illustrating motion vectors as described herein, shown in the context of tracking a given pixel across an illustrative sequence of three consecutive video frames. 
         FIG. 5  is a diagram illustrating cumulative motion vectors as described herein, shown in the context of tracking a given pixel across an illustrative sequence of video frames. 
         FIG. 6  is a flow diagram illustrating a process flow for performing spatial complexity analysis, as shown in  FIG. 3 . 
         FIG. 7  is a block diagram illustrating a spatial neighborhood of a given pixel, suitable for facilitating the spatial complexity analysis, as shown in  FIGS. 3 and 6 . 
         FIG. 8  is a flow diagram illustrating a process flow for performing temporal complexity analysis, as shown in  FIG. 3 . 
         FIG. 9  is a flow diagram illustrating a process flow for estimating the temporal complexity of pixels, as shown in  FIG. 8 . 
         FIG. 10  is a flow diagram illustrating a process flow suitable for embedding a watermark into selected regions of an input video. 
         FIG. 11  is a block diagram illustrating a host segment from an input video, featuring two prisms shown within the host segment. 
         FIG. 12  is a flow diagram illustrating a process flow for a first algorithm for associating weights with regions in the prism. 
         FIG. 13  is a flow diagram illustrating an alternative process flow for associating weights with regions in the prism. 
         FIG. 14  is a block diagram illustrating weight generation using a seed growing algorithm. 
         FIG. 15  is a block diagram illustrating an architecture that provides at least one alternative to the architecture shown in  FIG. 1 . 
         FIGS. 16A and 16B  are flow diagrams illustrating a process flow suitable to enable the watermark encoder to generate watermarked video in connection with the architecture shown in  FIG. 15 . 
         FIG. 17  is a flow diagram illustrating a process flow suitable for processing watermarked video. 
         FIG. 18  is a flow diagram illustrating a process flow for encoding a watermark using a symbol-based key management system. 
         FIG. 19  is a flow diagram illustrating a process flow for detecting a watermark using a symbol-based key management system. 
         FIG. 20  illustrates an exemplary computing environment within which systems and methods for video fingerprinting using watermarks, as well as the computing, network, and system architectures described herein, can be either fully or partially implemented. 
     
    
    
     DETAILED DESCRIPTION 
     The same numbers are used throughout the drawings to reference like features and components. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The use of the same reference numbers in different figures indicates similar or identical items. 
       FIG. 1  illustrates an architecture  100  for fingerprinting an input video  105  using an input watermark  110 . The architecture  100  includes a watermark encoder  115 , which is operative to receive the video  105  and the watermark  110 , and to embed or encode the watermark  110  into the video  105 , producing a watermarked video  120 . 
     Block  125  represents a process by which the watermarked video  120  is attacked. Suitable examples of attacks can include unauthorized copying of the watermarked video  120 , unauthorized modifications of the watermarked video  120 , or the like. In instances in which the watermarked video  120  undergoes some type of attack, the results of that attack are represented generally as attacked video  130 . Various examples of attack are further discussed below. 
     Block  125  is shown in dashed outline to indicate that it is not to be considered as part of the architecture  100 , but is nevertheless included in  FIG. 1  to facilitate a full discussion of an illustrative environment in which the architecture  100  may operate. In instances where the watermarked video  120  undergoes some form of attack, the attacked video  130  may pass to a watermark decoder  135   
     The watermark decoder  135  is operative to receive the attacked video  130  and to extract or decode a watermark  140  therefrom. If the extracted watermark  140  matches the input watermark  110 , this may provide guidance on investigating the nature of the attack. More particularly, in some implementations of the architecture  100 , given watermarks  110  can be associated with respective persons. When the watermark  140  extracted from an attacked video  130  matches a watermark  110  associated with some person, this may indicate that the person was involved in the attack, or may provide at least part of the chain of custody associated with the attacked video  130 . 
     The watermark decoder  135  can also be operative to process the attacked video  130  so as to “undo” the attack. In such implementations, the output video  145  represents the attacked video  130  after the attack is “undone” by the watermark decoder  135 . Various approaches and techniques for undoing such attacks are discussed in further detail below. 
     It is understood that each instance of the watermarked video  120  is not necessarily attacked. Where the watermarked video  120  is not attacked, it may nevertheless pass directly to the watermark decoder  135  for processing. Once again, block  125  is shown in dashed outline to indicate that it is, in some sense, optional. 
       FIG. 2  illustrates further components and data flows relating to the watermark encoder  115  shown in  FIG. 1 . The input video  105  is received, and then undergoes region complexity analysis, which is represented generally as region complexity analysis  205 . Region complexity analysis  205  is discussed in further detail below, but in overview, the input video  105  is divided into a plurality of regions. Given one of these regions, this region is analyzed to determine whether the region is or would be a good candidate for embedding the watermark  110 . Generally speaking, the more complex a given region is, the better that region is as a candidate for embedding the watermark  110 . A threshold  210  specifying the minimum complexity level appropriate for embedding the watermark  110  in a given region can be received. Those regions satisfying the complexity level threshold  210  are output from the region complexity analysis  205  as regions  215 . It is understood that any given input video  105  could contain one or more regions  215  that are suitable for watermarking. It is also possible that a given input video  105  does not contain any regions that are suitable for watermarking. 
     The regions  215  that are output from the region complexity analysis  205  are routed to a watermark embedding process  220 . The watermark embedding process  220  is described in further detail below, but, in overview, it receives the input watermark  110  and embeds or encodes the watermark  110  onto the regions  215  received from the region complexity analysis  205 . The output of the watermark embedding process  220  is the watermarked video  120 . 
       FIG. 3  illustrates further components and data flows relating to the region complexity analysis  205 , which was introduced in  FIG. 2 . As discussed above, one step in embedding the watermark  110  is to determine which regions  215  of an input video  105  are complex enough to invisibly hold the watermark  110 . These regions  215  can be identified by analyzing the video  105 , for example, using the region complexity analysis  205 . The region complexity analysis  205  can include a spatial complexity analysis  305  and a temporal complexity analysis  310 . In overview, the spatial complexity analysis  305  outputs a measure  315  indicating how spatially complex the input regions  215  are (spatial complexity is determined via analyzing the pixels within a frame), while the temporal complexity analysis  310  outputs a measure  320  indicating how temporally complex the input regions  215  are (temporal complexity is determined via analyzing the relationship between the pixels that belong to different frames). The spatial complexity measure  315  and the temporal complexity measure  320  are input to a combining process  325 , which combines the measures  315  and  320  to produce a final complexity measure  330 . 
     Now turning to the region complexity analysis  205  in more detail, the analysis  205  can be based on a statistical video model that provides spatial and temporal entropy rates in a DC sub-band portion of the input video  105 . A region  215  that exhibits sufficiently high entropy rates may be sufficiently complex to embed the watermark  110  without being detected by a viewer, or otherwise unduly interfering with the perception of the video  105 . Therefore, the spatial complexity measure  315  and the temporal complexity measure  320  of given regions  215  may be estimated based on their spatial and temporal entropy rates. The spatial and temporal entropy rates associated with the regions  215  can be linearly combined by, for example, the combination process  325 , and analyzed on a per-pixel basis. Hence, the complexity analysis taught herein may be characterized as analyzing the complexity of the regions  215  on a pixel-wise basis. 
     Before discussing further the statistical model of the video  105  that facilitates the complexity analysis  205 , it is beneficial to introduce the concept of a motion field. 
     Motion Field and Motion Vectors 
       FIG. 4  illustrates motion vectors  405  and  410  as described herein, shown in the context of tracking a given pixel  415  across an illustrative sequence of, for example, three consecutive video frames  420  within an illustrative but non-limiting region  215 . It is emphasized that  FIG. 4  is not to be understood as limiting a region  215  to three video frames  420 . Instead,  FIG. 4  includes three video frames  420  only for convenience of discussion and illustration. 
     For convenience, the video frames  420  are referenced individually as frames  420 ( 1 ),  420 ( 2 ), and  420 ( 3 ), and collectively as frames  420 . Likewise, the pixel  415  is referenced as pixel  415 ( 1 ) as shown within frame  420 ( 1 ), is referenced as pixel  415 ( 2 ) as shown within frame  420 ( 2 ), and is referenced as pixel  415 ( 3 ) as shown within frame  420 ( 3 ). Collectively, the pixels  415 ( 1 ),  415 ( 2 ), and  415 ( 3 ) are referenced as pixels  415 . In the context of the discussion herein, it can be assumed that the pixel  415  may represent, at least in part, a given point of interest within the video  105 . As a non-limiting example, the pixel  415  may be part of an actor walking across a scene. 
     Unlike a three-dimensional dataset, such as magnetic resonance imagery (i.e., MRIs), in video, behavior along the temporal axis may be radically different than behavior along the spatial axis. The pixels on two frames  420  of a video are correlated spatially and along the motion vectors whereas pixels in MRI are correlated according to 3D neighborhood. 
     Video coders may exploit this phenomenon by using motion vectors. Due to compression efficiency considerations, most state-of-the-art video coding standards use block-based motion vectors. However, since the teachings herein are not limited by compression efficiency, motion vectors  405  and  410  can be utilized at the pixel level, rather than the block level. Furthermore, the teachings herein can use motion vectors  405  and  410  in, for example, a discrete wavelet transform (DWT) direct current (DC) sub-band, instead of in an untransformed domain. This approach may be characterized as processing a spatially down-sampled video. 
     Defining the motion vectors  405  and  410  in more detail, let p(t 0 , C 0 ) denote a given pixel  415 ( 2 ) on the frame  420 ( 2 ) F t0  at coordinates C 0  in the DC sub-band. Note that C 0  can be expressed as two-dimensional coordinates (x 0 , y 0 ). Although there may be concerns such as pixel occlusion between consecutive frames  420 , one can typically assume that this given pixel  415 ( 2 ) exists in frames  420 ( 1 ) F t0−1  and  420 ( 3 ) F t0+1 . Also, assume that an algorithm can find the corresponding pixel  415 ( 3 ) on the next frame  420 ( 3 ), represented as p n (t 0 +1, C n ). Assume also that this algorithm can find the corresponding pixel  415 ( 1 ) on the previous frame  420 ( 1 ), represented as p p (t 0 −1, C p ). Here, a vector representing the difference between the coordinates C n −C 0  may be referred to as a forward motion vector  405  (MV fwd  (t 0 , C 0 )). Additionally, a vector representing the difference between the coordinates C p −C 0  may be referred to as a backward motion vector  410  (MV bck  (t 0 , C 0 )). 
     The algorithm that finds the motion vectors  405  and  410  can be block based or optical flow based. Block based motion estimation techniques may be used in video compression. The idea is to “match” a block of interest in the current frame to the best match in the neighboring frame. Therefore, for a given block of interest in the current frame, a block matching algorithm may find the “closest” block to it in the neighboring frame in the sense of a preferred distortion metric. The distortion metrics used for this purpose are typically L2 norm (Euclidean norm) or L1 norm (corresponds to sum of absolute differences). 
     Optical-flow based motion estimation techniques result from a different approach, namely constant intensity assumption. This assumption yields the result that the luminance of a moving point does not change much between neighboring frames. Mathematically, this can be represented as f(x+dx, y+dy, t+dt)=f(x, y, t), where f(x, y, t) denotes a three dimensional representation of video (the first, second and third dimensions are spatial horizontal, spatial vertical and temporal directions, respectively). Applying Taylor expansion to the left hand side yields the famous optical flow equation:
 
(∇ f ) T   ·v+∂f/∂t= 0,
         where ∇f=[∂f/∂x, ∂f/∂y] T  is the spatial gradient of the video f(x, y, t) and v=[∂x/∂t, ∂y/∂t] T  is the motion vector In practice, in optical flow methods, the goal is to find motion vector v at each location (x, y, t) to minimize 7 (∇f) T ·v+∂f/∂t7.       

     Cumulative Motion Vectors 
       FIG. 5  illustrates cumulative motion vectors  505  and  510  as described herein, shown in the context of tracking a given pixel  515  across an illustrative sequence of video frames  520 . As above in  FIG. 4 , the pixels  515  are referenced collectively as pixels  515 , and severally as pixels  515 ( 1 ),  515 ( 2 ), and  515 ( 3 ). Likewise, the video frames  520  are referenced collectively as video frames  520 , and severally as video frames  520 ( 1 ),  520 ( 2 ), and  520 ( 3 ). 
     Consider an example of tracking a given pixel  515 ( 2 ) p(t 0 , C 0 ) in a video frame  520 ( 2 ) for N frames into the future, and determining the spatial coordinates of that pixel  515  as the video  105  advances through those N frames. The spatial coordinates of that pixel  515  through the N frames may be denoted as the coordinates C f  of the pixel p n (t 0 +N, C f ). For convenience, the final or N-th frame is referenced as frame  520 ( 3 ), and the pixel  515  within the frame  520 ( 3 ) is referenced as pixel  515 ( 3 ). A vector representing the movement of the given pixel  515  between the coordinates C f −C 0  as the video  105  is advanced N frames may be referred to as a cumulative forward motion vector  505  (CMV fwd (t 0 , C 0 , N)). A similar vector representing the movement of the given pixel between the coordinates C p −C 0  as the video is reversed N frames may be referred to as a cumulative backward motion vector  510  (CMV bck  (t 0 , C 0 , N)). 
     Since these motion vectors  405  and  410  (MVs) and cumulative motion vectors  505  and  515  (CMVs) are not necessarily integer valued, error accumulation may be prevented by using error diffusion in computation of the MVs and CMVs. Further, sub-pixel accuracy (i.e. floating point numbers) may be used in computing and storing the MVs and CMVs. 
     Having described the motion field, and defined the related concepts of the motion vectors  405  and  410  and cumulative motion vectors  505  and  515 , the spatial complexity analysis  305  shown in  FIG. 3  is now described in more detail. 
     Spatial Dependencies 
       FIG. 6  is a flow diagram illustrating a process flow  600  for performing spatial complexity analysis  305 , as shown in  FIG. 3 . In block  605 , a spatial neighborhood relative to a given pixel is defined. The given pixel can be, for example, the pixel  415  as shown in  FIG. 4  in the frames  420 , or the pixel  515  as shown in  FIG. 5  in the frames  520 . For convenience, this given pixel around which the neighborhood is defined is referenced as pixel  415 / 515 . For more detail on defining the spatial neighborhood,  FIG. 7  is now described. 
       FIG. 7  illustrates a spatial neighborhood  700  of the given pixel  415 / 515 . The pixel  415 / 515  can appear, for example, in a DWT DC-subband. Assume that a window  705  of neighboring pixels is defined around the given pixel  415 / 515 . As shown in  FIG. 7  for illustration, but not limitation, the window  705  is illustrative size of M×M, although the window  705  can take any convenient size, shape, or dimension relative to the given pixel  415 / 515 . Assume that the pixels neighboring the given pixel  415 / 515  in the DC sub-band are characterized by an approximately i.i.d. (independent identically distributed) Gaussian distribution. In  FIG. 7 , the given pixel  415 / 515  is marked black, and the M×M window  705  is shaded. In implementations, an illustrative size of M=5 may be suitable for the window  705 . 
     Returning to  FIG. 6 , in block  610 , to determine the spatial complexity (C s ) at the pixel  415 / 515  in the DC sub-band, the variance of the samples in the M×M window  705  can be estimated by relying on the above i.i.d. assumption. For p(t 0 , C 0 ), the samples are 
                 p   ⁡     (       t   0     ,       C   0     +     (     c   ,   d     )         )       ⁢   s   ⁢     :     ⁢   t   ⁢     :     ⁢     (     c   ,   d     )       ∈         {         -     (     M   -   1     )       2     ,   …   ⁢           ,       (     M   -   1     )     2       }     2     .           
In block  615 , using the Gaussian entropy formula C s =½ log 2πeσ 2 , (here σ 2  is the variance of the samples in the spatial neighborhood of the coefficient of interest) the spatial entropy rate of the given pixel  415 / 515  can be estimated. In block  620 , the spatial entropy rate can be returned for use as a measure  315  of the spatial complexity of the pixel  415 / 515 .
 
     Temporal Dependencies 
       FIG. 8  illustrates a process flow  800  for performing the temporal complexity analysis  310  as shown in  FIG. 3 . Given a pixel  415 / 515  in the DC subband, and given a motion field  805  associated with that pixel  415 / 515 , it can be assumed that in the direction of the motion field  805 , the movement of the pixel  415 / 515  can be modeled using a Gauss-Markov process. For convenience, the motion field  805  corresponds to the motion vectors  405  and  410  and/or the cumulative motion vectors  505  and  515 . 
     In block  810 , a temporal window related to the pixel  415 / 515  is defined. Assume that the temporal window of interest is of a length L. In implementations, an illustrative length of interest (L)=11 may be suitable. Furthermore, in the developments below, without loss of generality assume L is odd (the analysis and developments can be extended to the case of even L without any difficulty). 
     In block  815 , one or more given pixels of interest are identified. Assume that this given pixel is the pixel  415 / 515 . For the given pixel  415 / 515  p(t 0 , C 0 ), the corresponding pixels in the motion field  805  are given as p(t 0 +t, C 0 +CMV (t 0 ; C 0 ; t)), 
             t   ∈       {         -     (     L   -   1     )       2     ,   …   ⁢           ,       (     L   -   1     )     2       }     .           
Depending on the sign of t, one can use the cumulative motion vector  505  CMV fwd  if t&gt;0, and can use the cumulative motion vector  515  CMG bck  if t&lt;0.
 
     In block  820 , the temporal complexity of the pixel(s) of interest is estimated. To provide more detail on an illustrative method for performing the processing represented in block  820 ,  FIG. 9  illustrates a process flow  900  for estimating the temporal complexity of the pixel(s) processing performed in block  820 . 
     Turning now to  FIG. 9 , in block  905 , to determine the temporal complexity (C t ), an analysis based on a 1st order Gaussian auto-regressive (AR) model can be performed among the corresponding pixels, as follows: p(t 0 +t, C 0 )=ρp(t 0 +t−1, C 0 +CMV (t 0 , C 0 , t))+g(t), where g(t)˜N(0, σ 2 ); furthermore {g(t)} are independent of each other for different t. As above, depending on the sign of t, one may use CMV fwd  or CMV bck . 
     In block  910 , for each pixel  415 / 515 , the value of ρ is estimated that minimizes the Euclidean norm of the error; this estimate is also known as the least-squares estimate. In block  915 , the calculated value of ρ can then be used to determine the innovations process g( ). 
     In block  920 , again from the Gaussian entropy rate formula, the temporal complexity (C t ) can be found using the distribution of the innovations process g( ). 
     Returning to  FIG. 8 , in block  825 , the measure  320  of the temporal complexity (C t ) can be returned. The temporal complexity (C t ) can be estimated using, for example, the process flow  900  shown in  FIG. 9 . 
     Combined Complexity 
     Turning briefly to  FIG. 3 , particularly block  325  thereof, the spatial complexity (C s ) and the temporal complexity (C t ) may be combined linearly, with the result being used as the final per-pixel complexity  330  (C f ). The final per-pixel complexity  330  (C f ) may be calculated as follows: C f =αC s +βC t . The coefficients α and β can be chosen experimentally using, for example, a heuristic approach. 
     It is noted that the additive method described above for computing the final per-pixel complexity  330  (C f ) is illustrative and not limiting. Other alternatives, such as multiplicative combinations of the spatial complexity (C s ) and the temporal complexity (C t ), can be implemented. For example, the final per-pixel complexity  330  (C f ) may be computed as C f =C s   α C t   β , depending on particular applications. 
     Returning briefly to  FIG. 2 , recall that the input video  105  is divided into a plurality of candidate regions into which the watermark  110  may be embedded. The final per-pixel complexity  330  (C f ) of all the pixels in a given candidate region can be combined and compared to the complexity threshold  210 . If the final combined per-pixel complexity  330  (C f ) meets or exceeds the complexity threshold  210 , the given region of the video can be sent to the watermark embedding process  220  as a region  215  suitable for embedding the watermark  110 . 
     Region Selection 
     Candidate regions can be randomly selected in time. One illustrative criterion in selecting the regions  215  is to consider scene-cuts in the input video  105 , such that the selected region  215  does not overlap with any of the scene-cuts. Once such a region  215  (Ri) is selected, the complexity analysis  205  as described above can be performed. The per-pixel complexity  330  C f (t, C) can be calculated at all pixels from t Ri  to t Ri +T, with the coordinates Cε{(0, 0), . . . , (W, H)}, where W is the width and H is the height of a frame in the DWT DC band. 
     For future use, the per-pixel complexity  330  C f  can be stored. To prevent visual artifacts, and for security purposes, a modified version of C f  such that Ĉ f =LF(C f ×N Ku ) can be used, where N Ku  is a noise field with mean 1.0 securely generated from key Ku, and where LF( ) is the low pass filtering operator. Finally, in some implementations, Ĉ f  can be clamped between 0 and C fmax . 
     The combined complexities  330  can be thresholded and counted for all pixels in the region R i : ∀(t, C), if Ĉ f (t, C)&gt;C thresh =&gt;increment (Count Ri ). If (Count Ri &lt;α×T×W×H), then the region Ri can be considered unsuitable for marking. Otherwise, the process  220  of embedding the watermark  110  in the region  215  Ri can proceed. The parameter αε(0, 1) can be experimentally determined. 
     Embedding the Watermark 
       FIG. 10  illustrates a process flow  1000  suitable for embedding the watermark  110  into the selected regions  215  of the input video  105 . The watermark  110  may be embedded in the video  105 , for example, by changing the statistics of groups of pixels in the DWT DC subband. Any change in the DC subband is reflected on the untransformed domain and in the watermarked video  120 . The “group of pixels” can correspond to a T-frame region of video from time t Ri  to t Ri +T, for a given region Ri. 
     De-Correlation Transform 
     To be more robust against attacks, the watermark embedding process  220  can work on an approximately de-correlated version of the video signal. The signal de-correlation process is represented in  FIG. 10  by the block  1005 . For this purpose, a two-dimensional DWT along the spatial axes can be used. It is noted that de-correlation along the time axis can be handled in a different way by using the motion field of the video. 
       FIG. 11  illustrates a host segment from an input video, featuring two prisms shown within the host segment. Each video frame can be DWT decomposed into N 1  levels on the vertical axis and into N 2  levels on the horizontal axis. As shown in  FIG. 11 , the lowest frequency (DC) sub-band  1100  is selected for mark embedding. 
     Prism Selection and Thresholding 
     In block  1010 , a prism that corresponds to a feature is pseudo-randomly selected within the DWT&#39;s DC sub-band  1100 , as shown in  FIG. 11 . Let Pr i  denote the ith prism, let Pr isz  denote the size of the prism Pr i , and let Pr iloc  denote the location of the prism Pr i , s.t. i ε{(1, . . . , M), with M being the number of features or prisms. It is noted that Pr iloc  and Pr isz  εZ 3 . 
     Complexity mapping can be used during the prism selection process, as described now. In block  1015 , the complexity level of each pixel in a given prism can be thresholded. In the given prism, if the total number of pixels whose statistical complexities exceed this threshold is less than a certain percentage (P pass ) of the total pixels, the given prism is discarded. This process allows the mark embedding process to discard undesired regions of the video, i.e., low complexity regions that do not have enough entropy to visually and securely hide the mark. 
     In some implementations of the teachings herein, an illustrative size of the prisms can be chosen as about 40% of the host. The term “host” refers to the unmarked video signal  105  throughout this description). The percentage P pass  can be chosen as 50% and the threshold can be chosen as equal to C fmax /2. 
     Weight Generation 
     In block  1020 , weights are associated with the regions in the prism. Then, a statistic is computed for each prism using the weights assigned to that prism; the statistic of a given prism is a weighted linear combination of the coefficients inside that prism and the assigned weights are used in obtaining this linear combination. Then, the statistic of each prism is quantized to a secret lattice (potentially a different lattice for every prism). Then, a watermark is designed such that, when it is added to the unmarked signal (host), the statistics of the resulting signal sum are exactly equal to the quantized versions of the statistics of the unmarked host; the resulting sum will constitute the watermarked signal. 
     It can be shown that, under some mild conditions on the secret weights, there are infinitely many watermark solutions that satisfy this criterion (i.e., the criterion that the statistics of the watermarked signal need to be exactly equal to the quantized versions of the statistics of the unmarked signal); the one, which is minimum in its Euclidean norm, is called the “minimum norm” solution. The minimum norm solution determines the general nature of the embedded watermark and one can show that the embedded watermark will behave according to the utilized weights (this is because of the fact that the minimum-norm solution consists of a linear combination of the rows of the weight matrix). For example, if the weights in a region are constant, then the minimum norm solution will be constant in that region. This behavior can separately be observed in the temporal and spatial domains. By looking at a natural video, one can generally observe the following:
         i) the spatial characteristics are smoothly changing; and   ii) the temporal characteristics are approximately constant (or very slowly varying) throughout the motion direction.       

     It is understood that both observations may not necessarily be 100% true, since abrupt edges may violate the first observation, and occlusions may violate the second observation. Nevertheless, for the purposes of the instant discussion, it is safe enough to assume that these observations will generally hold true. Furthermore, the statistical video model introduced above generally agrees with the above observations. 
     Therefore, it may be appropriate to select the weights so that they vary smoothly in the spatial domain and so that they stay approximately constant along the motion field in the temporal domain. Furthermore, for security purposes, it may be appropriate to include a degree of randomness in the selection of the weights. Based on these design criteria, two weight generation algorithms are described and illustrated in connection with  FIGS. 11 and 12 , respectively. 
       FIG. 12  illustrates a process flow for a first algorithm for associating weights with regions in the prism, as represented in  FIG. 10  by the block  1020 . For convenience, but not limitation, the algorithm shown in  FIG. 12  is referred to herein as “Algorithm I”. 
     Algorithm I: Turning to  FIG. 12 , in block  1205 , a given, pseudo-randomly selected 3D rectangular prism, is filled with zero-mean Gaussian weights. In block  1210 , the prism is low-pass filtered with a sufficiently-low cutoff frequency along the spatial direction. This process achieves spatial smoothness. To achieve temporal smoothness, the weights can be filtered in the direction of motion, as represented in block  1215 . For example, see Appendix A for details of motion-compensated filtering. After the temporal filtering, windowing can be performed on the prism, as represented in block  1220 . A window, such as a Hanning window, is applied in both the spatial and the temporal directions. To ensure total decay, the ends of the window go to zero. 
     In some implementations, the foregoing algorithm may be suitable. In other implementations, an alternative algorithm described below and illustrated in  FIG. 13  may be suitable. 
       FIG. 13  illustrates an alternative process flow for associating weights with regions in the prism, as represented in  FIG. 10  by the block  1020 . For convenience, but not limitation, the algorithm shown in  FIG. 13  is referred to herein as “Algorithm II”. 
     Algorithm II: Consider  FIG. 14  along with  FIG. 13 .  FIG. 14  illustrates weight generation using a seed growing algorithm. In block  1305 , to select the weights that correspond to one three-dimensional rectangular prism  1405 , one can start with a pseudo-randomly selected two-dimensional rectangle  1410  in the temporal center of this prism  1405 . In block  1310 , this rectangle  1410  can be filled with pseudo-random zero-mean Gaussian weights. In block  1315 , the rectangle can be low-pass filtered with a low cutoff frequency. 
     In block  1320 , a windowing can be applied to achieve smoothness at the borders of the prism in the spatial domain. For convenience, but not limitation, this rectangle  1410  can be referred to as the “seed”  1410 . To achieve temporal smoothness, the seed  1410  can be grown in the direction of the motion vectors, as represented in block  1325 . Assume, for example, that it is desired to calculate the weight that corresponds to the location (x 0 , y 0 , t 0 ). Also, assume that the seed plane is located at (:, :, t mid ). First, a seed value is determined that corresponds to the weight at (x 0 , y 0 , t 0 ). This can be done using the cumulative motion vectors discussed above. If t 0  is greater than t mid , the backward motion vectors can be used, and if t 0  is less than t mid , the forward motion vectors can be used. 
     In block  1330 , once the corresponding seed is found, the video model can be imitated by putting a pseudo-random (PR) AR1 Gauss-Markov model on the seed: x(t)=ρx(t−1)+z(t). A smoothly-varying ρ field can be generated for use in the AR process. This field can be smoothly-varying around 1.0 as appropriate to prevent too much attenuation or amplification, since there can be as many as 70 frames in one direction. The parameter ρ can be selected from, for example, a Gaussian distribution ˜N(1, σ ρ   2 ) every N ρ  frames and interpolated in between. In block  1335 , an innovations process z can also be defined based on a Gaussian distribution ˜N(0; σ z   2 ). Note that this process z is designed to be independent of the innovations process g that was obtained during the temporal analysis; furthermore their statistical characterization do not need to be the same. However, special cases, where z and g are correlated, may also be employed in the design. The aforementioned weight generation (or growing) mechanism can be applied to the seed to find the final weight or weights, as represented in blocks  1340  and  1345 . It is noted that the above algorithm can be applied to find all weights in the prism. As an optimization, increased computational speed is possible if cumulative motion vectors are stored, and if the PR (pseudo-random) AR1 process is pre-computed. 
     Returning now to  FIG. 10 , after the weight generation process is performed in block  1020 , the prism can be spatially low pass filtered (i.e., two-dimensional, per-frame filtering), as represented in block  1025 . As part of this low-pass filtering, windows can be applied both temporally and spatially. In some implementations, an illustrative cutoff frequency used in the low-pass filtering in the spatial domain can be chosen as π/3. 
     In the spatial domain, a Hanning window can be used. The temporal window can be modified so that the peak is smoothed in the temporal axis to allow for unlocalized distribution of weights temporally. The modified temporal window can be similar to a Hanning window, except a plateau can be inserted at the peak of the window. Equations 1 and 2 below correspond to the spatial and temporal windows, respectively. L is the length of samples. In the temporal window, T is a percentage of the length L. In some implementations, an illustrative value of T=0.2×L may be used. 
     
       
         
           
             
               
                 
                   
                     W 
                     spatial 
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               1 
                               2 
                             
                             ⁢ 
                             
                               ( 
                               
                                 1 
                                 + 
                                 
                                   cos 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         π 
                                         ⁢ 
                                         
                                             
                                         
                                         ⁢ 
                                         x 
                                       
                                       L 
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                           
                         
                         
                           
                             
                               - 
                               L 
                             
                             &lt; 
                             x 
                             &lt; 
                             L 
                           
                         
                       
                       
                         
                           0 
                         
                         
                           otherwise 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
             
               
                 
                   
                     W 
                     temporal 
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               1 
                               2 
                             
                             ⁢ 
                             
                               ( 
                               
                                 1 
                                 + 
                                 
                                   cos 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         π 
                                         ⁡ 
                                         
                                           ( 
                                           
                                             x 
                                             + 
                                             L 
                                             - 
                                             T 
                                           
                                           ) 
                                         
                                       
                                       T 
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                           
                         
                         
                           
                             
                               - 
                               L 
                             
                             &lt; 
                             x 
                             &lt; 
                             
                               
                                 - 
                                 L 
                               
                               + 
                               T 
                             
                           
                         
                       
                       
                         
                           1 
                         
                         
                           
                             
                               
                                 - 
                                 L 
                               
                               + 
                               T 
                             
                             &lt; 
                             x 
                             &lt; 
                             
                               L 
                               - 
                               T 
                             
                           
                         
                       
                       
                         
                           
                             
                               1 
                               2 
                             
                             ⁢ 
                             
                               ( 
                               
                                 1 
                                 + 
                                 
                                   cos 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         π 
                                         ⁡ 
                                         
                                           ( 
                                           
                                             x 
                                             - 
                                             L 
                                             + 
                                             T 
                                           
                                           ) 
                                         
                                       
                                       T 
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                           
                         
                         
                           
                             ( 
                             
                               
                                 L 
                                 - 
                                 T 
                               
                               &lt; 
                               x 
                               &lt; 
                               L 
                             
                             ) 
                           
                         
                       
                       
                         
                           0 
                         
                         
                           otherwise 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
     Calculating Statistics 
     In block  1030 , statistic μ i  can be computed for a given group i, 1&lt;=i&lt;=N (where N is the total number of groups) that represents the sum of the element-wise multiplications of weights and corresponding pixels in the DWT DC sub-band. Each μ i  can be quantized via a scalar uniform quantizer with step size δ. The output of the quantizer can be expressed as {circumflex over (m)} i , 1,&lt;=i&lt;=N. 
     Embedding the Mark in the Host 
     In block  1035 , the watermark signal  110  to be embedded in the input video  105  is defined. Let s denote the original unmarked host video  105  in the DWT DC sub-band, as received in block  1040 . It is understood that the processing represented in block  1040  can occur in any order or sequence relative to the other {circumflex over (m)} blocks shown in  FIG. 10 . In any event, a pseudo-randomly generated watermark signal  110  ( n ) is found, such that the statistics of the watermarked video signal  120  (x=s+n) are equal {circumflex over (m)} and ∥x−s∥ is minimized. First, the following Equations 3 and 4 are defined as set forth below. Here, the weights for the i-th prism are represented by c ij . Thus, the i-th row of T, which consists of T ij , contains the weights generated to computed the statistic of the i-th rectangle: 
                 d   ∈       R   m     :   d       ⁢     =   Δ     ⁢       u   ^     -   u       ,     
     ⁢       T   ∈       R     M   ×   N       :     T   ij         ⁢     =   Δ     ⁢     {           c   ij             if   ⁢           ⁢   j     ∈     R   i               0       else                   
where T is chosen such that Ts=u.
 
Let n=x−s. We solve
 
                       min   x     ⁢            x   -   s          ⁢           ⁢     s   .   t     ⁢           ⁢   Tx       =     u   ^             (   3   )               
which is equivalent to
 
                       min   x     ⁢          n        ⁢           ⁢     s   .   t     ⁢           ⁢   Tn       =   d           (   4   )               
the solution is given by n=T T (TT T ) −1 (û−u).
 
     Equation (4) is the minimum norm solution, and it may be considered optimal in the sense of the Euclidean norm. However, this does not necessarily guarantee that the watermarked video  120  provides an acceptable visual output. In order to improve perceptual quality, to enforce complexity measures in the watermark  110 , and to enforce the motion behavior on the watermark  110 , an iterative regularization can be applied on the minimum norm solution, which is denoted by n MN . This regularization process is represented generally in  FIG. 10  by block  1045 , and discussed in more detail below. 
     Regularization of the Minimum Norm Watermark 
     Continuing with block  1045  in more detail, once the minimum norm solution n MN  is found using the above formula, the following iterations can be applied: 
     1. n MN =T T  (TT T ) −1 d 
     2. Set n 0 =n MN    
     3. for K steps . . .
         (a) n 1 =C(n 0 )   (b) n 2 =M(n 1 )   (c) n 3 =F(n 2 )   (d) n d =n 3 −n MN      (e) n n =n d −T T (TT T ) −1 Tn d      (f) ń 0 =n n +n MN      (g) if ∥ń 0 −n 0 ∥&lt;εstop, else n 0 =ń 0  and go to 3.a       

     The C(•) operator corresponds to the per-pixel multiplication with the complexity map. This operator ensures that the watermark embedded in the low complexity regions is attenuated. 
     The M(•) operator corresponds to the temporal filtering as described in Appendix A. In some implementations, an illustrative filter length as high as 20 samples may be appropriate. This operator may help achieve temporal smoothness, but, in some implementations, may not be as dominant as motion directed weight selection in doing so. 
     The F(•) operator corresponds to low-pass filtering in the spatial domain. In some implementations, perfect low-pass fast Fourier transform (FFT) filtering may be used. In such implementations, the F operator enforces a spatially smooth WM. 
     Power Adjustment 
     Turning to block  1045 , in some implementations, it may be appropriate to regulate the power of the watermark  110  to control the amount of distortion introduced to the host video  105  when the watermark  110  is embedded therein to produce the watermarked video  120 . Power management can be performed by iterating the embedding process. With each iteration, the quantization level can be updated until the desired power level is matched within a predefined margin of error. 
     In block  1050 , the watermark signal  110  as processed above is embedded or encoded onto the input video  105 . 
     Time Synchronization 
       FIG. 15  illustrates an architecture  1500  that provides at least one alternative to the architecture  100  shown in  FIG. 1 . The architecture  1500  and techniques related thereto can address additional challenges that may arise in some implementations of video watermarking. These challenges are discussed in more detail below, along with how the architecture  1500  addresses such challenges. 
     Turning to  FIG. 15  in more detail, in some instances, the watermarked video  120  may be temporally distorted. This distortion can be in the form of edits, scene cuts, and/or insertions made to the watermarked video  120 . Also, temporal distortion may result from temporal re-sampling performed on the watermarked video  120 . The foregoing operations to the watermarked video  120  may or may not be authorized. Such cases of temporal distortion can present the decoder  135  with additional challenges in effectively locating the same watermark embedding regions  215  of the input video  105  that are suitable for embedding the watermark signals  110 ; this is appropriate in order to have synchronization between encoder and decoder. 
     One approach to addressing these and other types of temporal distortions is to use a video hash that is based on a two-dimensional (2D) image hash function. One aspect of an algorithm for addressing such temporal distortion includes sending two-dimensional hashes of randomly selected frames within the watermarked video  120  as side information  1505  from the watermark encoder  115  to the watermark decoder  135 . It is understood that the side information  1505  is shown separate from the watermarked video  120  in  FIG. 15  only for convenience and clarity of illustration and discussion, and not to limit possible implementations of the architecture  1500 . Instead, the side information  1505  may be integrated into the watermarked video  120 , or can be provided separately from the watermarked video  120 . 
     Turning to the side information  1505  in more detail, it can include the two-dimensional hash values mentioned above. The side information  1505  can also include data representing the motion fields described above, such as the motion vectors  405  and  410  ( FIG. 4 ), and/or the cumulative motion vectors  505  and  515  ( FIG. 5 ). The side information  1505  may also include other data as described in further detail below. 
     An image hash function suitable for generating the hash values that can be sent as at least part of the side information  1505  is now described. 
     Image Hash Function 
     The architectures  100  and  1500  are discussed based on the assumption that a fast and robust image hash function is available. Let h(•) denote such a hash function. In this case, h(S) represents the hash value of an input image S. In the architectures  100  and  1500  taught herein, the hash function h(•) can be applied to respective video frames. Furthermore, it is assumed that the output of the hash function is a binary string of length L. That is, the range of h(•) is {0, 1} L . Let d(•, •) denote the normalized Hamming distance, as normalized by L. In this case, then, it is assumed that the hash function h(•) satisfies the following properties:
         h(S) is approximately uniformly distributed in {0, 1} L  for any given input image S.   Pr [d (h(S i ), h(S j ))≧T 1 ]≈1, where S i  and S j  are perceptually different images (objects).   Pr [d (h(S i ), h(S′ i ))≦T 0 ]≈1, where S i  and S′ i  are perceptually approximately the same images (objects).       

     With an efficient hash function, T 1  should be greater than T 0 , with T 1  as close as possible to 0.5. The latter value is the expected Hamming distance between two hashes randomly selected from a uniform distribution. Further, T 0  should be as close to 0 as possible. Any hash function h (•) that satisfies the aforementioned properties can be used in the algorithms taught herein. In the remainder of the description herein, S i  is used to denote the i-th frame of a given digital input video  105  at the watermark encoder  115 . Similarly, X i  is used to denote the i-th frame of a given digital watermarked video  120  at the watermark decoder  135 . As used herein, the variable i can be referred to as a “temporal frame index”. 
     Encoder Side Operation 
       FIGS. 16A and 16B  illustrate a process flow  1600  suitable to enable the watermark encoder  115  to generate the watermarked video  120  in the architecture  1500 . For clarity and convenience, the process flow  1600  is broken across  FIGS. 16A and 16B , and is connected by the reference “A” as shown in these two Figures. 
     As represented in block  1605 , at the watermark encoder  115 , one task is to select one or more appropriate regions of the input video  105  in which to embed the input watermark  110 . While a completely random (i.e., uniformly distributed) selection may be appropriate in terms of security, it is described herein to choose the regions randomly (uniformly distributed) within a subset of all possible selections, such that the watermark decoder  135  is more likely to produce reliable results when producing the output video  145  from the watermarked video  120 . 
     To perform the task of selecting regions, the input video  105  can first be partitioned into scenes, as represented in block  1610 . This approach helps to combat “scene-cut” type attacks, which are one type of attack represented by the block  125 . Having partitioned the input video  105  into scenes, one criterion in selecting an appropriate region in which to embed the watermark  110  is that a selected region should not overlap with any scene-cut. In block  1615 , this condition is evaluated. If the given region overlaps with a scene-cut, the region is rejected, as shown in block  1620 . Afterwards, another candidate region is selected (block  1625 ), and the process  1600  then returns to block  1615  to evaluate the region. 
     When a candidate region passes block  1615  (i.e., does not overlap with a scene-cut), the process  1600  can, for convenience, accumulate or otherwise store for future reference the candidate regions that do not overlap scene-cuts, as represented in block  1630 . 
     In block  1635 , the process  1600  evaluates whether the candidate regions are sufficiently complex to embed the watermark  110 . A given region of the input video  105  is considered to be suitable for embedding the watermark  110  if it is sufficiently complex, i.e., the video region exhibits high entropy. The complexity of given regions of the input video  105  can be determined by using statistical complexity measures, as discussed in detail above. 
     The rationale for selecting highly complex (i.e., high entropy) regions of the input video  105  is that regions with low entropy are more likely to show perceptually annoying artifacts after the watermarks  110  are embedded therein. As a byproduct of this characteristic, such regions of the input video  105  may be more susceptible to malicious estimation attacks. Malicious estimation attacks are another example of the attacks represented generally in block  125 . Malicious estimation attacks aim to estimate the watermark and/or the unmarked host signal via exploiting the differences (if any) in the statistical characterization of the watermark and the unmarked signal. For instance, if the watermark is designed to be in the form of a high-frequency noise and added to directly on top of a signal which is low-frequency dominated, it could be possible to erase most of the watermark by some cleverly-designed noise-removal (also termed as denoising) algorithms. Such broad classes of attacks are called malicious estimation attacks and it is the designer&#39;s responsibility to design the watermark such that the watermark statistically resembles the unmarked signal as much as possible. Illustrative techniques for measuring the statistical complexity of regions of the input video  105  are described above. 
     The regions of the input video  105  into which the watermark  110  is embedded can be selected based on one or more complexity measures, such as the spatial complexity measure  315 , the temporal complexity measure  320 , and/or the final per-pixel complexity measure  330 , as shown in  FIG. 3 . Using one or more of these complexity measures, the process  1600  can determine whether a candidate region is sufficiently complex to embed the watermark  110 . If the region is not sufficiently complex, the process  1600  proceeds to block  1640 , where the candidate region is rejected and a new candidate region is selected. The new candidate region is then evaluated by branching back to block  1635 . 
     From block  1635 , if the candidate region is sufficiently complex, then within each selected region, at least N P  frames can be selected as “representative frames”, as represented in block  1645 . These representative frames can be called (for ease of description but not limitation) “poles”, and their temporal frame indices are denoted as {P i }, i ε{1, . . . , N P ). In block  1650 , hash values can be defined for each of the poles. 
     Without loss of generality, it is assumed that the corresponding poles {S Pi } are sorted temporally, i.e., that P i &gt;P i−1  for all i. Furthermore, the poles can be randomly selected within each watermark region from a uniform distribution, subject to the condition that the distances between the hash values of neighboring poles are sufficiently high, as represented in block  1655 . This condition can be referred to as the distinction criterion. The hash values of these poles can form, at least in part, the side information  1505  that is sent from the watermark encoder  115  to the watermark decoder  135 , to enable the latter to perform temporal re-synchronization on the watermarked video  120 . Hence, these hash values constitute the perceptually-representative information for an embedding region. 
     The aforementioned distinction criterion promotes accurate representation of each watermark region as a whole at the watermark decoder  135 . The distinction criterion helps to ensure that the poles stand distinct enough from their neighboring regions. The rationales described herein can be better understood by the following example. Consider a region of the input video  105  characterized by a constant background and very little foreground motion. If a pole is selected from such a region, it may be difficult to re-synchronize to the temporal location of this pole at the watermark decoder  135 , even in the absence of attacks. This difficulty may result because a robust image hashing algorithm run on several similar poles from this region would be expected to output several hash values that are close to one another. Accordingly, at the watermark decoder  135 , it may be difficult to identify where one of the poles fits in temporally within the region, based only on the hash values corresponding to the several poles. 
     Therefore, given a candidate watermark region, that region is analyzed to determine if that region would be suitable for re-synchronization at the watermark decoder  135 . Put differently, poles from the candidate region can be analyzed to determine if any of them satisfy the distinction criterion (block  1660 ). If one or more poles meet the distinction criterion, the hash values of one or more of these poles can be sent as side information to the watermark decoder  135  (block  1665 ). This processing can be performed in addition to the complexity analysis described above. 
     If the pole does not meet the distinction criterion, the process  1600  can proceed to block  1670  to evaluate whether any more candidate poles are to be evaluated. If so, the process  1600  returns to block  1655  to select another candidate pole, and that candidate pole is evaluated in block  1660 . 
     Having set forth the architecture  1500  and the process flow  1600 , the distinction criterion is described and defined in more detail. Let {P i −Δ i , P i −Δ i +1, . . . P i +Δ i } denote a temporal neighborhood of the i-th pole located at P i , where Δ i  ε Z +  is an input parameter to the algorithm. For each pole S pi , the average distance between its hash value and the hash values of its neighboring poles is calculated as follows: 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             D 
                             i 
                           
                           ⁢ 
                           
                             = 
                             Δ 
                           
                           ⁢ 
                           
                             
                               1 
                               
                                 
                                   2 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     Δ 
                                     i 
                                   
                                 
                                 + 
                                 1 
                               
                             
                             ⁢ 
                             
                               
                                 ∑ 
                                 
                                   j 
                                   = 
                                   
                                     
                                       P 
                                       i 
                                     
                                     - 
                                     
                                       Δ 
                                       i 
                                     
                                   
                                 
                                 
                                   
                                     P 
                                     i 
                                   
                                   + 
                                   
                                     Δ 
                                     i 
                                   
                                 
                               
                               ⁢ 
                               
                                 d 
                                 ⁢ 
                                 
                                   ( 
                                   
                                     
                                       h 
                                       ⁡ 
                                       
                                         ( 
                                         
                                           S 
                                           
                                             P 
                                             i 
                                           
                                         
                                         ) 
                                       
                                     
                                     , 
                                     
                                       h 
                                       ⁡ 
                                       
                                         ( 
                                         
                                           S 
                                           j 
                                         
                                         ) 
                                       
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                         
                         , 
                       
                     
                     
                       
                         i 
                         ∈ 
                         
                           { 
                           
                             1 
                             , 
                             
                               … 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 N 
                                 P 
                               
                             
                           
                           } 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
     Choosing a threshold T D  as an input parameter to the algorithm, a video region can be declared unsuitable for re-synchronization if D i &lt;T D  for some i. In implementations of the teachings herein, T D  can be determined heuristically based on experiments. If a candidate watermark region is declared to be suitable to re-synchronization, the hash values of the poles, {h(S Pi )}, are computed and sent to the watermark decoder  135  as side information  1505 . This process can be carried out for each watermark embedding region. 
     Decoder Side Operation 
       FIG. 17  illustrates a process flow  1700  suitable for processing watermarked video. For example, the process flow  1700  may be performed by or in connection with the watermark decoder  135 . The watermark decoder  135  can receive as input the watermarked video  120  or the watermarked/attacked video  130 . For convenience of discussion but not limitation, the input to the watermark decoder  135  is denoted herein as the watermarked video  120 . However, it is understood that the watermarked/attacked video  130  could also be input to the watermark decoder  135 . 
     Turning to  FIG. 17  in more detail, in block  1705 , the watermarked video  120  that is input to the watermark decoder  135 , referred to symbolically as {X i }, is traversed. In block  1710 , the hash values of all of the frames present in the video  120  are extracted. As a result, the hash values {h(X i ), i ε{1, 2, . . . , N x } are obtained, where N x  denotes the total number of frames in the input video  120 . In general, there may be an arbitrary number of watermark embedding regions in the video  120 . However, for brevity and convenience, the discussion herein is confined to a single watermark region, with the understanding that the discussion could be readily applied to any number of watermark regions. Similar operations would be performed separately for each watermark region. 
     In block  1715 , in order to temporally match a watermark region, one task is to perform, for example, a fuzzy comparison between the original hash values of the poles of that region, represented as {h(S Pj )}, and the hash values of the frames of the received video  120 , represented as {h(X i )}. Recall that the hash values of the poles of the region can be provided as at least part of the side information  1705 . In this manner, a similarity list for each pole can be populated, as represented in block  1720 . Let L j  denote the similarity list (i.e., a set of temporal frame indices) of the original pole S Pj , j ε{1, 2, . . . , N P }. Using the above, the similarity list L j  can be defined as:
 
 L   j   { i ε{ 1,2 , . . . N   X   }|d ( h ( X   i ), h ( S   Pi ))&lt;ε H   },jε{ 1,2 , . . . , N   P }.
 
     Here, ε H  is an input parameter to the algorithm, and is chosen with care since the average size of each similarity list, and in return the synchronization performance of the described algorithm, depends on its value. If ε H  is chosen to be too small, the described algorithm may miss the real pole in the populated similarity list, for example, due to malicious attacks. This would result in the failure of the synchronization algorithm. On the other hand, if ε H  is chosen to be too high, each similarity list can unnecessarily include many inaccurate pole candidates. This condition may result in an unmanageable algorithm in implementation, because of the required computational workload imposed by the high number of pole candidates. From this perspective, choosing a “good” image hash function directly enhances the performance of the algorithm, since as the accuracy of the underlying hash function increases, it becomes feasible to choose smaller values of ε H  without the algorithm failing to synchronize. 
     Having produced the similarity lists {L j } for the original poles {S Pj }, the next step is to select the best N-tuple (one from each similarity list L j ), such that:
         1. The original pole distribution and the candidate pole distribution are matched temporally as much as possible (criterion 1), and   2. The sum of the distances between the hash values of the original poles and pole candidates are minimized (criterion 2).       

     Criterion 1 limits how much change is permitted between the temporal locations of two poles. It will be shortly seen that this leads to significant performance gains in the sense of algorithmic complexity, even in the presence of an allowed error margin for robustness against malicious temporal attacks. One example of such an attack would be to time-compress certain regions of video and/or apply video interpolation to them, thereby changing the temporal distribution of the original poles. 
     Let QεZ +NP  denote a candidate pole location vector that consists of temporal frame indices in the received video {X i }, where Q={Q 1 , Q 2 , . . . , Q NP }. Note that in an illustrative case of no attacks or modifications (i.e., X i =S i , for all i), it may be desired to find Q i =P i , 1≦i≦N P  using the instant algorithm, since the original poles would be unchanged in this case. Combining criteria 1 and 2, the following combinatorial optimization problem is to be solved: 
                     min   Q     ⁢       ∑     j   =   1       N   P       ⁢     d   ⁡     (       h   ⁡     (     X     Q   j       )       ,     h   ⁡     (     S     P   j       )         )                 (   6   )               
such that
 
∀ jε{ 1,2 , . . . , N   P   },Q   j   εL   j ,  (7)
 
and
 
                       ∀   j     ⁢     ∈     {     1   ,   2   ,   …   ⁢           ,       N   P     -   1       }         ,           ⁢            1   -              Q   j     -     Q     j   +   1             P   j     -     P     j   +   1                       &lt;     ε   T       ,           (   8   )               
where ε T  is the maximum allowed temporal scaling (i.e., corresponds to the allowed error margin for robustness against temporal attacks). Note that, here (6) (respectively (8)) represents the aforementioned criterion 2 (respectively criterion 1).
 
     If we have |L j |≈M on average, then the size of a feasible set is about M Np . This implies that an assumed straightforward implementation that uses an exhaustive search would require O(M Np ) tests. In such an implementation, this may lead to an algorithmic complexity that may be unacceptably high and may even be infeasible, considering that similarity lists can potentially be hundreds of frames long and there may be about 15-30 poles per region. 
     To overcome the computational burden of this combinatorial optimization problem, a trellis-based search method is described. This search method exploits dynamic programming, and the algorithmic steps of the search method are given in Table 1. 
     
       
         
           
               
               
               
             
               
                   
                 TABLE 1 
               
               
                   
                   
               
             
            
               
                   
                 1. 
                 d ij  = ∞, i ∈ {1, . . . , M j } and j ∈ {1, . . . , N p } 
               
               
                   
                 2. 
                 C(j) = 1, and j ∈ {1, . . . , N p }, bestpath dist  = ∞ 
               
               
                   
                 3. 
                 do 
               
               
                   
                 3.1 
                  Initialize p = 1 and sum dist  = 0, terminate = false 
               
               
                   
                 3.1.1 
                  sum dist  = sum dist  + d (h (X Lp(c(p))  ) , h(S Pp ) ) 
               
               
                   
                 3.1.2 
                  if sum dist  ≦ d C(p), p   
               
               
                   
                 3.1.2.1 
                   d C(p),p  = sum dist   
               
               
                   
                 3.1.3 
                  else if sum dist  &gt; d C(p), p   
               
               
                   
                 3.1.3.1 
                   Set C (k + 1) = M k , for k ∈ {p, . . . N p } 
               
               
                   
                 3.1.3.2 
                   terminate = true, goto 3.2 
               
               
                   
                   
               
               
                   
                 3.1.4 
                  
       if   ⁢           |     1   -           L   p     (     C   ⁡     (   p   )       )     -       L     p   -   1       ⁡     (     C   ⁡     (     p   -   1     )       )             P   p     -     P     p   -   1             |     &gt;     ε   T           
 
               
               
                   
                   
               
               
                   
                 3.1.4.1 
                   Set C (k + 1) = M k , for k ∈ {p, . . . N p } 
               
               
                   
                 3.1.4.2 
                   terminate = true, goto 3.2 
               
               
                   
                 3.1.2 
                  p = p + 1 If p ≦ N p  goto 3.1.1 
               
               
                   
                 3.2 
                  if terminate == false and bestpath dist  &gt; sum dist   
               
               
                   
                 3.2.1 
                  result(i) = C(i), i ∈ {1, . . . , N p } 
               
               
                   
                 3.2.2 
                  bestpath dist  = sum dist   
               
               
                   
                 3.3 
                  If C is at the limit 
               
               
                   
                 3.3.1 
                  goto 4 
               
               
                   
                 3.4 
                  else 
               
               
                   
                 3.4.1 
                  Increment C, goto 3.1 
               
               
                   
                 4. 
                 result holds the optimal path. 
               
               
                   
                   
               
            
           
         
       
     
     Brief Description of the Proposed Algorithm in Table 1: dynamic programming techniques are applied by using a special N P  digit counter CεZ +NP , C(j)ε{1, . . . , M j }, where C(j) denotes the j-th component of C. Each digit of C has a different base: 1≦C(j)≦M j , where M j =|L j |. For example, for a 3-digit counter with bases {2, 3, 2}, the counter can run as follows: {1, 1, 1 }, {1, 1, 2}, {1, 2, 1}, {1, 2, 2}, {1, 3, 1}, {1, 3, 2}, {2, 1, 1}, . . . {2, 3, 2}. 
     The counter is increased until it reaches the upper bound. The j-th digit of the counter C represents the temporal frame index of the j-th candidate pole Q j , i.e., Q j =L j  (C(j)), 1≦j≦N P , where L j (n) denotes the n-th largest element of L j . At each increment of the counter C, the validity of the specified path is tested. For each entry in the similarity lists, a variable d i,j , with iε{1, . . . , M j } and jε{1, . . . , N P }, is defined. This variable d i,j  is initialized to a “high” value. The variables d i,j  are active variables, and represent the minimum of the sum of distances observed since the beginning of the counter. 
     Remark 2: The efficiency of the described algorithm is due, at least in part, to the early termination tests at the steps of 3.1.3 and 3.1.4 in Table 1. Note that 3.1.3 is a valid test, because if sum dist  at that point is larger than a previous path&#39;s sum, than there is no point in continuing with this path, since the algorithm has already found a better path to that point. Also, 3.1.4 is a test that is included to emphasize the allowable temporal scaling limits. Steps 3.1.3.1 and 3.1.4.1 are the purging steps, where the rest of the invalid path is effectively removed from the search space, thus increasing the search speed. 
     Fine-Tuning Using Image Registration 
     At the end of block  1725 , using the algorithm given in Table I, we find the poles from the received video such that these poles match as much as possible with the original poles of the original unmarked video. However, in most practical situations, the match between the resulting poles of the received video and the original poles of the original unmarked video does not need to be exact. This is possible due to the potential existence of malicious geometric attacks (such as time interpolation, rotation, cropping, etc) that the received video may have gone through. In order to “perceptually match” the received video to the original video further, we “warp” the resulting poles of the received video to the original poles of the original unmarked video as accurately as possible. To achieve this task, we can use image registration techniques. In other words, we “register” the received poles to the original poles and thus, we hope to achieve optimal geometric synchronization between the received video and the original unmarked video. For the pole i at Q i , try to register the original pole S i  to X j , |j−Q i |&lt;τ s . A value of j is chosen that maximizes the “success of registration” metric, and the fine-tuned receiver side poles are denoted with Q′ i . Such a metric can be minimization of L2 norm. τ s  can be the temporal search neighborhood, and can be, for example, as long as 20 frames. 
     Temporal Undoing 
     In block  1730 , once the fine tuned poles (Q′ i ) are found, temporal undoing can be applied on the synchronized region to achieve at least two goals:
         1. Match the received region&#39;s length to the original region&#39;s length, and   2. If the lengths match, perform piecewise linear temporal scaling to undo any mismatch within the region.       

     Assume that a temporal video interpolation algorithm is available. For a suitable example of the foregoing interpolation algorithm, see S. B. Kang, M. Uyttendaele, S. A. J. Winder, and R. Szeliski, “High dynamic range video,” Proceedings of ACM Siggraph, 2003. Given M frames, this algorithm would generate N frames, and could be applied to each pole-pair as follows. The region between poles i and i+1, which is Q′ i+1 −Q′ i  frames long, is mapped to S i+1 −S i  frames. Then the remapped regions are concatenated to generate the final temporal undone region. 
     Key Management 
       FIG. 18  illustrates a process flow  1800  for encoding a watermark using a symbol-based key management system. The process flow  1800  can be performed by, for example, the watermark encoder  115 . 
     Key Assignment 
     In block  1805 , users can be assigned or associated with respective identifiers (IDs) in the form of codewords. For example, if each symbol is allocated some number of binary bits, than an illustrative ID for a given user can be 1001101001101; here the length of the ID is the same as the number of embedding regions in video. Alternatively, it is possible to apply an error correction code to the user IDs and increase the length such that the length of the encoded ID is the same as the number of mark-embedding regions in video; if this is employed, then the decoder can apply an error correction decoding strategy accordingly after decoding the bits for each embedding region in the video. Once a “bit” (either zero or one) is assigned to each embedding region, each region can then be embedded with a pseudo-random key, which may be generated from a master “zero” key and a master “one” key. Note that, in this construction, the “zero” keys and the “one” keys for different regions may potentially be different and pseudo-randomly generated from the master “zero” key and master “one” key. Afterwards, the regions can be edited and combined to generate a properly coded video. 
     Preprocessing 
     A given video  105  to be fingerprinted can be preprocessed. In block  1810 , the scenes in the video  105  are located. Any method for detecting scenes and/or scene cuts may be suitable. For example, a thresholding based on two-dimensional image hashes can be used. If the hash distance between frame f i  and f i−1 , (D(f i ; f i−1 )) is greater than 
                 1   N     ⁢       ∑     j   =   1     N     ⁢     D   ⁡     (       f     i   -   1       ,     f     i   -   j         )           ,         
then the frame f i  can be labeled as a scene change. Further improvements, such as histogram comparisons, are also possible and may be especially appropriate to capture blending-type scene changes. In general, any scene detection algorithm can be used at this stage.
 
     Region Selection 
     In block  1815 , the scene information is used to select random regions in the video  105 . In some implementations, these regions do not overlap with the scene boundaries, and these regions do not overlap with each other. These random regions should possess certain complexity properties such that they are suitable for watermarking. In general other potential robustness properties under several attacks may be employed for the region selection mechanism. 
     Once the scenes and/or scene cuts are detected, N R  regions can be selected. Each region can be selected randomly, but nevertheless selected based on certain criteria. Once a random region that does not fall onto any other previously selected regions is selected, the spatial and temporal complexity measures  315  and  320  for this region are computed as described above. The resulting per-pixel complexity measure  330  for this region is then thresholded. If the total number of pixels that pass the threshold is greater than, for example, half of the total pixels in the region, the region can be selected. Otherwise, the region can be discarded and another random region is selected for complexity measurement and thresholding analysis. 
     This process can be repeated until N R  regions are selected. After the selection process in block  1815 , the video hashes of each of the N R  regions can be extracted and stored as side information, as represented in block  1620 . 
     Pre-Embedding 
     In block  1825 , each given region can be coded with the keys K i0  and K i1 , iε1, . . . , N R . K i0  and K i1  are the i-th pseudo-random keys generated from the “zero” and “one” master keys K M0  and K M1  respectively. This coding process results in video segments {circumflex over (R)} i0  and {circumflex over (R)} i1  for the N R  regions. 
     Side Information 
     In block  1830 , the side information  1505  can be associated with the regions. Side information  1505  for a given region can include the forward and backward motion vectors  410  and  415 , the forward and backward cumulative motion vectors  510  and  515 , the video hashes of the regions, and side information for the keys K 0  and K 1 . 
     Embedding 
     In block  1835 , the watermark  110  is embedded into the selected region of the video  105 . Embedding refers to editing the video  105  based on the codeword for a particular user. For a user u with a codeword CW u =(b 0 , . . . , b N     R   ), such that all b i ε{0, 1}, the editing is the concatenation of regions {circumflex over (R)} ib     0    . . . {circumflex over (R)} ib     NR    of the video  105 . 
     Watermark Detection 
     Region Identification 
     After the synchronization process is performed using, for example, the process flow  1700  shown in  FIG. 17 , the locations of the embedding regions in the video  120  can be determined. Since the watermark decoder  135  knows which keys are associated with which users, it can use the same pseudo-random generation processes as the watermark encoder  115 , and can generate the same weights as the watermark encoder  115  did previously. 
     One way of detecting whether a given region i is embedded with a given key k is to determine the correlation C, as follows: 
     
       
         
           
             
               
                 
                   C 
                   = 
                   
                     
                       〈 
                       
                         
                           
                             
                               u 
                               ~ 
                             
                             ik 
                           
                           - 
                           
                             u 
                             ik 
                           
                         
                         , 
                         
                           
                             
                               u 
                               ~ 
                             
                             ik 
                           
                           - 
                           
                             u 
                             ik 
                           
                         
                       
                       〉 
                     
                     
                        
                       
                         
                           
                             u 
                             ~ 
                           
                           ik 
                         
                         - 
                         
                           u 
                           ik 
                         
                       
                        
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
     u ik  can be sent as side information, and û ik  is the quantized coefficient. ũ ik  is the coefficient calculated at the receiver. If C is greater than a threshold τ, then the user i can be labeled as involved in producing the given region. 
     Note that is the foregoing describes one illustrative method of using the watermarking system. In connection with  FIG. 19  below, a different detection rule is described that may be appropriate for handling multiple regions and users. 
     Dynamic Range Undoing 
     The side information  1505  for each region can contain the histogram of the original frames of that region. At the decoder side, once the region is “temporally undone”, the histograms of the received frames can be re-mapped to the histograms of the original frames. As a result, this effectively undoes any histogram mapping type of attacks. 
     Registration Based Undoing 
     Suppose two regions R i  and {tilde over (R)} i  are given. Using an image registration algorithm, the per-pixel mapping C can be found that takes {tilde over (R)} i  to R i . If C is applied to {tilde over (R)} i , the image {tilde over (R)}′ i  results. Undoing can be performed on a given region {tilde over (R)} i  and the calculation of û ik  can be carried out over the “undone” region {tilde over (R)}′ i . 
     Detection by Watermark Decoder 
       FIG. 19  illustrates a further process flow  1900  for detecting a watermark using a symbol-based key management system. The process flow  1900  can be performed by, for example, the watermark decoder  135 . 
     In block  1905 , the video  120  is received by, for example, the watermark decoder  135 . In block  1910 , detection can start by extracting the hashes generated to synchronize the regions during the encoding process  1800 . In block  1915 , the regions in the input video  120  corresponding to the extracted hashes are located. Once the regions are found, each region can be decoded using the keys K i0  and K i1 , as represented in block  1920 . This results in ũ i0  and ũ i1  being obtained or extracted; note that, here ũ i0  and ũ i1  represent the statistics of the received video obtained by using the keys K i0  and K i1 , respectively. In block  1925 , for each user with codeword CW u , a respective likeliness measure L u  can be calculated as: 
     
       
         
           
             
               
                 
                   
                     
                       L 
                       u 
                     
                     = 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         
                           i 
                           = 
                           
                             N 
                             R 
                           
                         
                       
                       ⁢ 
                       
                          
                         
                           
                             
                               u 
                               ~ 
                             
                             ib 
                           
                           - 
                           
                             
                               u 
                               ^ 
                             
                             ib 
                           
                         
                          
                       
                     
                   
                   , 
                   
                     b 
                     ∈ 
                     
                       { 
                       
                         0 
                         , 
                         1 
                       
                       } 
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
     In block  1930 , the codeword that results in the minimum L u  is identified as the owner. The owner as determined in block  1930  is the user whose “fingerprint” was used in connection with watermarking the input video  105  by the watermark encoder  115 . As such, if the watermarked video  120  undergoes some type of attack (block  125 ), the process  1900  can establish that the owner is at least in the chain of custody involving the attacked video  130 . In some instances, this may suggest that the owner actually performed the attack on the video  130 . In other instances, this may indicate that the owner leaked the video  105  to one or more authorized parties, whether voluntarily or involuntarily. 
       FIG. 20  illustrates an exemplary computing environment  2000  within which systems and methods for video fingerprinting using watermarks, as well as the computing, network, and system architectures described herein, can be either fully or partially implemented. For example, aspects of the computing environment  2000  may be suitable for implementing the watermark encoder  115  and/or the watermark decoder  135 , as well as the components thereof as described above. 
     Exemplary computing environment  2000  is only one example of a computing system and is not intended to suggest any limitation as to the scope of use or functionality of the architectures. Neither should the computing environment  2000  be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the exemplary computing environment  2000 . 
     The computer and network architectures in computing environment  2000  can be implemented with numerous other general purpose or special purpose computing system environments or configurations. Examples of well known computing systems, environments, and/or configurations that may be suitable for use include, but are not limited to, personal computers, server computers, client devices, hand-held or laptop devices, microprocessor-based systems, multiprocessor systems, set top boxes, programmable consumer electronics, network PCs, minicomputers, mainframe computers, gaming consoles, distributed computing environments that include any of the above systems or devices, and the like. 
     The computing environment  2000  includes a general-purpose computing system in the form of a computing device  2002 . The components of computing device  2002  can include, but are not limited to, one or more processors  2004  (e.g., any of microprocessors, controllers, and the like), a system memory  2006 , and a system bus  2008  that couples the various system components. The one or more processors  2004  process various computer executable instructions to control the operation of computing device  2002  and to communicate with other electronic and computing devices. The system bus  2008  represents any number of several types of bus structures, including a memory bus or memory controller, a peripheral bus, an accelerated graphics port, and a processor or local bus using any of a variety of bus architectures. 
     Computing environment  2000  includes a variety of computer readable media which can be any media that is accessible by computing device  2002  and includes both volatile and non-volatile media, removable and non-removable media. The system memory  2006  includes computer readable media in the form of volatile memory, such as random access memory (RAM)  2010 , and/or non-volatile memory, such as read only memory (ROM)  2012 . A basic input/output system (BIOS)  2014  maintains the basic routines that facilitate information transfer between components within computing device  2002 , such as during start-up, and is stored in ROM  2012 . RAM  2010  typically contains data and/or program modules that are immediately accessible to and/or presently operated on by one or more of the processors  2004 . 
     Computing device  2002  may include other removable/non-removable, volatile/non-volatile computer storage media. By way of example, a hard disk drive  2016  reads from and writes to a non-removable, non-volatile magnetic media (not shown), a magnetic disk drive  2018  reads from and writes to a removable, non-volatile magnetic disk  2020  (e.g., a “floppy disk”), and an optical disk drive  2022  reads from and/or writes to a removable, non-volatile optical disk  2024  such as a CD-ROM, digital versatile disk (DVD), or any other type of optical media. In this example, the hard disk drive  2016 , magnetic disk drive  2018 , and optical disk drive  2022  are each connected to the system bus  2008  by one or more data media interfaces  2026 . The disk drives and associated computer readable media provide non-volatile storage of computer readable instructions, data structures, program modules, and other data for computing device  2002 . 
     Any number of program modules can be stored on RAM  2010 , ROM  2012 , hard disk  2016 , magnetic disk  2020 , and/or optical disk  2024 , including by way of example, an operating system  2028 , one or more application programs  2030 , other program modules  2032 , and program data  2034 . Each of such operating system  2028 , application program(s)  2030 , other program modules  2032 , program data  2034 , or any combination thereof, may include one or more embodiments of the systems and methods described herein. 
     Computing device  2002  can include a variety of computer readable media identified as communication media. Communication media typically embodies computer readable instructions, data structures, program modules, or other data in a modulated data signal such as a carrier wave or other transport mechanism and includes any information delivery media. The term “modulated data signal” refers to a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared, other wireless media, and/or any combination thereof. 
     A user can interface with computing device  2002  via any number of different input devices such as a keyboard  2036  and pointing device  2038  (e.g., a “mouse”). Other input devices  2040  (not shown specifically) may include a microphone, joystick, game pad, controller, satellite dish, serial port, scanner, and/or the like. These and other input devices are connected to the processors  2004  via input/output interfaces  2042  that are coupled to the system bus  2008 , but may be connected by other interface and bus structures, such as a parallel port, game port, and/or a universal serial bus (USB). 
     A display device  2044  (or other type of monitor) can be connected to the system bus  2008  via an interface, such as a video adapter  2046 . In addition to the display device  2044 , other output peripheral devices can include components such as speakers (not shown) and a printer  2048  which can be connected to computing device  2002  via the input/output interfaces  2042 . 
     Computing device  2002  can operate in a networked environment using logical connections to one or more remote computers, such as remote computing device  2050 . By way of example, remote computing device  2050  can be a personal computer, portable computer, a server, a router, a network computer, a peer device or other common network node, and the like. The remote computing device  2050  is illustrated as a portable computer that can include any number and combination of the different components, elements, and features described herein relative to computing device  2002 . 
     Logical connections between computing device  2002  and the remote computing device  2050  are depicted as a local area network (LAN)  2052  and a general wide area network (WAN)  2054 . Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets, and the Internet. When implemented in a LAN networking environment, the computing device  2002  is connected to a local network  2052  via a network interface or adapter  2056 . When implemented in a WAN networking environment, the computing device  2002  typically includes a modem  2058  or other means for establishing communications over the wide area network  2054 . The modem  2058  can be internal or external to computing device  2002 , and can be connected to the system bus  2008  via the input/output interfaces  2042  or other appropriate mechanisms. The illustrated network connections are merely exemplary and other means of establishing communication link(s) between the computing devices  2002  and  2050  can be utilized. 
     In a networked environment, such as that illustrated with computing environment  2000 , program modules depicted relative to the computing device  2002 , or portions thereof, may be stored in a remote memory storage device. By way of example, remote application programs  2060  are maintained with a memory device of remote computing device  2050 . For purposes of illustration, application programs and other executable program components, such as operating system  2028 , are illustrated herein as discrete blocks, although it is recognized that such programs and components reside at various times in different storage components of the computing device  2002 , and are executed by the one or more processors  2004  of the computing device  2002 . 
     Although embodiments of video fingerprinting using watermarks have been described in language specific to structural features and/or methods, it is to be understood that the subject of the appended claims is not necessarily limited to the specific features or methods described. Rather, the specific features and methods are disclosed as exemplary implementations of video fingerprinting using watermarks. 
     It is further understood that the foregoing description discloses several process flows and/or related flow diagrams. It is understood that while these process flows may be described herein as being executed in connection with certain components, these process flows could readily be performed or executed in connection with other components without departing from the spirit and scope of the subject matter described herein. It is also noted that various sub-processes are disclosed herein as illustrative sub-components of broader processes. However, implementations of the broader processes need not include all of the illustrative components shown herein, and may include one or more of these illustrative components without departing from the spirit and scope of the subject matter described herein.