Patent Publication Number: US-8538069-B2

Title: Adaptive video fingerprinting

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     The present application is a divisional application of, and claims priority and full benefit under 35 U.S.C. §120 to U.S. patent application Ser. No. 12/262,377, entitled “ADAPTIVE VIDEO FINGERPRINTING,” filed Oct. 31, 2008, and which is incorporated herein by reference in its entirety. 
    
    
     BACKGROUND 
     Description of the Related Art 
     A typical digital or cable television system includes a hardware device, such as a set-top box, that connects a subscriber&#39;s television, and possibly other electronic equipment, to a cable or satellite network. The hardware device typically connects to the cable or satellite network via a co-axial wall outlet to receive digital content, including digital video. The owners of the digital content are interested in protecting it against illegal copying. 
     Cryptography protects a message by using a secret key to transform it into an unreadable encrypted format. For digital content, cryptography provides the sender with some assurance that the communication to the receiver was confidential, it does not protect against illegal copying of the digital content. Steganography is an information hiding technique that embeds a message within another seemingly harmless message. Even though steganography provides for covert communication of digital content that includes a concealed mark unknown to an attacker, a successful attack will reveal the digital content. 
     Watermarking and fingerprinting are two classes of techniques for copyright protection of digital content. Watermarking embeds an imperceptible mark in the digital content that identifies the sender. Upon extraction of the watermark, watermarking enables provable ownership of the digital content. Fingerprinting, which is also known as forensic watermarking, embeds an imperceptible mark in the digital content that identifies the receiver. Upon extraction of the fingerprint, fingerprint enables identification of the receiver and proof of illegal copying. 
     Prior art fingerprinting methods for digital video have created a large number of unique spatial fingerprints by spreading multi-byte identifiers over several video frames. These methods altered the pixel values in different locations within selected frames to specify which ones contain fingerprint information, what part of the multi-byte identifier is present, and the fingerprint bits themselves. These prior art spatial fingerprinting methods were promising, but modifications were necessary to focus on altering luminance values, and to allow for embedding and recovery of unique, visibly imperceptible, and robust fingerprints that will survive compression and other processing of video data. The advantage of these modifications is that the present invention is sufficiently simple to be implemented in a set top box with limited processing power and memory, and it can provide a large number of unique identifiers by spreading information over multiple frames. 
     Thus, there is a demand for a method for embedding and recovering spatial fingerprints in marked frames of a sequence of digital video frames. The presently disclosed method satisfies this demand. 
     SUMMARY 
     A method and system for embedding and recovering a spatial fingerprint in a sequence of video frames. The sequence includes marked frames that include marked groups having markable positions. 
     The embedding method selects a frame offset and marking period for the marked frames, and determines a marking strength for modifying each marked group. The embedding method embeds a portion of the spatial fingerprint in each marked group of a first subgroup of the marked groups, and an ordering of the portion embedded in the first subgroup in each marked group of a second subgroup of the marked groups. The embedding method may also embed a redundant copy of the ordering embedded in the second subgroup in each marked group of a third subgroup of the marked groups. 
     The recovering method analyzes a quality ratio of the DCT transform energy and the residual for each markable position in the frame to determine whether the frame is a marked frame. The recovering method recovers the spatial fingerprint when the marked groups maintain the quality ratio in a number of successive marked frames. The recovering method may also determine whether the quality ratio of each marked group in a second subgroup of the marked groups is in agreement with the quality ratio of each marked group in a third subgroup of the marked groups. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates the block-based grid spacing of a prior art digital video fingerprinting strategy. 
         FIG. 2  and  FIG. 3  illustrate one embodiment of the block-based grid spacing for an improved fingerprinting strategy. 
         FIG. 4  is a block diagram that illustrates one embodiment of a fingerprint recovery device that performs the present invention. 
         FIG. 5  is a block diagram that illustrates one embodiment of a fingerprint embedding device that performs the present invention. 
         FIG. 6  is a flow chart that illustrates one embodiment of the method of fingerprint recovery for the present invention. 
         FIG. 7  is a flow chart that illustrates one embodiment of the method of fingerprint embedding for the present invention. 
     
    
    
     DETAILED DESCRIPTION 
       FIG. 1  illustrates the block-based grid spacing of a prior art digital video fingerprinting strategy.  FIG. 1  illustrates a video frame  100 , having 720×480 pixels, represented as a 45×30 grid of macroblocks (MBs), where each MB represents a 16×16 block of pixels. The horizontal MBs (numbered 1 through 45) represent 720 pixels, and the vertical MBs (numbered 1 through 30) represent 480 pixels. The video frame  100  denotes marked MBs throughout the grid of MBs (numbered 1 through 76) that are subject to pixel alteration as disclosed in the present invention by the addition of “on-marking” values. The marked MBs are divided into five groups, marked MBs 1-16 are in Group 0, marked MBs 17-32 are in Group 1, marked MBs 33-48 are in Group 2, marked MBs 49-64 are in Group 3, and marked MBs 65-76 are in Group 4. Groups 0, 1, 2, and 3 carry information bits, and Group 4 is used as an index to specify where the bits in Groups 0, 1, 2, and 3 belong in the total fingerprint. The video frame  100  shown in  FIG. 1  excludes the marked MBs from a 3 MB border around the frame periphery, and a 21×12 MB rectangle in the center of the frame. Furthermore, the marked MBs are spaced apart by 3 MB in each direction. As indicated by hexadecimal values [0,F] for the marked MBs in Groups 0, 1, 2 and 3, each group can encode four bits (i.e., one hex value) of the fingerprint identifier information, for a total of two bytes per frame. Group 4 includes 12 marked MBs for indicating that a frame contains fingerprint information and which byte pairs of the multi-byte identifier are given by the marked MBs of Group 0, 1, 2, and 3. Up to 48 bits can be carried in three frames (i.e., 4 bits per group and 4 groups per frame yields 16 bits per frame), and if all byte pairs were used, there would be twelve different marking frame types for a fingerprint of up to 192 bits. Even though the marked MBs shown in  FIG. 1  embed a fingerprint in a digital video frame sequence, recovery of the fingerprint from the block-based grid spacing shown in  FIG. 1  is complex. 
       FIG. 2  and  FIG. 3  illustrate one embodiment of the block-based grid spacing for an improved fingerprinting strategy. The block-based grid spacing, as shown in  FIG. 2 , changes the location of the marked MBs shown in  FIG. 1 .  FIG. 2  illustrates a standard definition (SD) video frame  200 , having 720×480 pixels, represented as a 45×30 grid of MBs. In another embodiment, the video frame  200  is a high-definition (HD). The horizontal MBs (numbered 1 through 45) represent 720 pixels, and the vertical MBs (numbered 1 through 30) represent 480 pixels. The video frame  200  denotes six groups of marked MBs throughout the grid of MBs (Groups 0, 1, 2, 3, 4, and 5). Each group includes 16 marked MBs (labeled 0 through F). Groups 0, 1, 2, and 3 are a subgroup that are subject to pixel alteration as disclosed in the present invention by the addition of “on-marking” values and carry information bits.  FIG. 3  illustrates the 16×16 block of pixels that comprise each marked MB. As denoted by the shaded portion of the 16×16 block of pixels in  FIG. 3 , the present invention, in one embodiment, inserts the mark in a 4×4 block of pixels in the upper, left corner of each marked MB. 
     Referring again to  FIG. 2 , Group 4 is a subgroup that includes 16 marked MBs for indicating that a frame contains fingerprint information and is used as an index to specify where the bits in Groups 0, 1, 2, and 3 belong in the total fingerprint. Each group, including Group 4, has sixteen markable positions, allowing a maximum of 16 byte pairs for fingerprints up to 256 bits in length. Group 5 is a subgroup that includes 16 marked MBs that carry redundant information to improve retrieval of byte pair designators over what can be achieved with Group 4 marks alone. The video frame  200  shown in  FIG. 2  excludes the marked MBs from at least a 4 MB border around the frame periphery, and a 31×16 MB rectangle in the center of the frame  200 . 
       FIG. 4  is a block diagram that illustrates one embodiment of a fingerprint recovery device that performs the present invention. As shown in  FIG. 4 , the fingerprint recovery device  400  is a general-purpose computer that provides powerful computing resources to recover a fingerprint from a sequence of digital video frames. A bus  402  is a communication medium that connects a central processor unit (CPU)  405 , data storage device  410  (such as a disk drive, flash drive, flash memory, or the like), input device  415  (such as a keyboard, keypad, touchscreen, or the like), output device  420  (such as a monitor, graphic display, or the like), and memory  425 . 
     The CPU  405  performs the disclosed methods by executing the sequences of operational instructions that comprise each computer program resident in, or operative on, the memory  425 . The reader should understand that the memory  425  may include operating system, administrative, and database programs that support the programs disclosed in this application. In one embodiment, the configuration of the memory  425  of the fingerprint recovery device  400  includes fingerprint recovery program  430 . The fingerprint recovery program  430  performs the method of the present invention disclosed in detail in  FIG. 6 . These computer programs store intermediate results in the memory  425 , or data storage device  410 . In another embodiment, the memory  425  may swap these programs, or portions thereof, in and out of the memory  425  as needed, and thus may include fewer than all of these programs at any one time. 
       FIG. 5  is a block diagram that illustrates one embodiment of a fingerprint embedding device that performs the present invention. As shown in  FIG. 5 , the fingerprint embedding device  500  is a general-purpose computer that performs the fingerprint embedding in real-time. In various embodiments, the fingerprint embedding device  500  is a simple and fast, limited capability device, such as a set-top box, cable converter box, satellite receiver, or the like. A bus  502  is a communication medium that connects a CPU  505 , data storage device  510  (such as a disk drive, flash drive, flash memory, or the like), input device  515  (such as a keyboard, keypad, touchscreen, or the like), output device  520  (such as a monitor, graphic display, or the like), and memory  525 . 
     The CPU  505  performs the disclosed methods by executing the sequences of operational instructions that comprise each computer program resident in, or operative on, the memory  525 . The reader should understand that the memory  525  may include operating system, administrative, and database programs that support the programs disclosed in this application. In one embodiment, the configuration of the memory  525  of the fingerprint embedding device  500  includes fingerprint embedding program  530 . The fingerprint embedding program  530  performs the method of the present invention disclosed in detail in  FIG. 7 . These computer programs store intermediate results in the memory  525 , or data storage device  510 . In another embodiment, the memory  525  may swap these programs, or portions thereof, in and out of the memory  525  as needed, and thus may include fewer than all of these programs at any one time. 
     In another embodiment, the fingerprint recovery device  400  and the fingerprint embedding device  500  are combined into a single, multi-function device. The multi-function device is simple and fact to perform the fingerprint embedding, and has a powerful CPT to perform the fingerprint recovery. 
       FIG. 6  is a flow chart that illustrates one embodiment of the method of fingerprint recovery for the present invention. Prior art fingerprint recovery methods have been based on the comparison of covariance summation of marked and unmarked luminance pixel blocks for different groups within a video frame. The present invention improves upon those prior art pure or normalized covariance methods. The fingerprint recovery method  600  illustrated in  FIG. 6  searches a sequence of digital video frames to locate a number of the frames that include the fingerprint (i.e., marked frames). The first marked frame is separated from each successive marked frame by a marking period. The fingerprint recovery method  600  locates the marked frames in the sequence based on the ratio of the first diagonal Discrete Cosine Transform (DCT) coefficient of known scaling to the residual, that is, the total energy minus that of the DCT. 
     Using the first diagonal DCT, the fingerprint recovery method  600  computes the floating-point values of the two-dimensional DCT1,1(i,j) basis function for a B×B square array (step  605 ). The computation is given by Eqn. 1 as: 
     
       
         
           
             
               
                 
                   
                     
                       
                         DCT 
                         
                           1 
                           , 
                           1 
                         
                       
                       ⁡ 
                       
                         ( 
                         
                           i 
                           , 
                           j 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         ( 
                         
                           2 
                           B 
                         
                         ) 
                       
                       ⁢ 
                       
                         cos 
                         ⁡ 
                         
                           ( 
                           
                             
                               
                                 ( 
                                 
                                   
                                     2 
                                     ⁢ 
                                     i 
                                   
                                   + 
                                   1 
                                 
                                 ) 
                               
                               ⁢ 
                               π 
                             
                             
                               2 
                               ⁢ 
                               B 
                             
                           
                           ) 
                         
                       
                       ⁢ 
                       
                         cos 
                         ⁡ 
                         
                           ( 
                           
                             
                               
                                 
                                   ( 
                                   
                                     
                                       2 
                                       ⁢ 
                                       j 
                                     
                                     + 
                                     1 
                                   
                                   ) 
                                 
                                 ⁢ 
                                 π 
                               
                               ) 
                             
                             
                               2 
                               ⁢ 
                               B 
                             
                           
                           ) 
                         
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     i 
                     , 
                     
                       j 
                       = 
                       
                         [ 
                         
                           0 
                           , 
                           
                             B 
                             - 
                             1 
                           
                         
                         ] 
                       
                     
                   
                 
               
               
                 
                   Eqn 
                   . 
                   
                       
                   
                   ⁢ 
                   1 
                 
               
             
           
         
       
     
     which has a mean of zero and an auto-covariance 
               ∑     i   =   0       B   -   1       ⁢           ⁢       ∑     j   =   0       B   -   1       ⁢           ⁢       DCT     1   ,   1     2     ⁡     (     i   ,   j     )               
that is equal to unity.
 
     The fingerprint recovery method  600  selects a frame k of a video sequence that includes embedded B×B marks based upon Eqn. 1 (step  610 ). The fingerprint recovery method  600  extracts the marks from the frame k by detecting the most strongly correlated square array in one of the 16 marked MBs, h=[0,15], within each of six groups, g=[0,5]. Beginning in row ig(h) and column jg(h) for a given group and marked MB, the method  600  computes the DCT1,1 frame energies, Dk,g(h) as given by Eqn. 2 below, for a total of 96 B×B square arrays (i.e., 16 marked MBs×6 groups) of decoded luminance pixels, pk(i,j), using the definition in Eqn. 1 in the squared summation (step  615 ). In another embodiment, the frame may be shifted due to processing, such as cropping, distortion, or attack such as eliminating a single column of pixels, and the fingerprint recovery method searches the frame to locate the marks in the shifted frame before computing the DCT1,1 frame energies. 
     
       
         
           
             
               
                 
                   
                     
                       
                         d 
                         
                           k 
                           , 
                           g 
                         
                       
                       ⁡ 
                       
                         ( 
                         h 
                         ) 
                       
                     
                     = 
                     
                       
                         ( 
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               0 
                             
                             
                               B 
                               - 
                               1 
                             
                           
                           ⁢ 
                           
                             
                               ∑ 
                               
                                 j 
                                 = 
                                 0 
                               
                               
                                 B 
                                 - 
                                 1 
                               
                             
                             ⁢ 
                             
                               
                                 
                                   p 
                                   k 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     
                                       
                                         
                                           i 
                                           g 
                                         
                                         ⁡ 
                                         
                                           ( 
                                           h 
                                           ) 
                                         
                                       
                                       + 
                                       i 
                                     
                                     , 
                                     
                                       
                                         
                                           j 
                                           g 
                                         
                                         ⁡ 
                                         
                                           ( 
                                           h 
                                           ) 
                                         
                                       
                                       + 
                                       j 
                                     
                                   
                                   ) 
                                 
                               
                               ⁢ 
                               
                                 
                                   DCT 
                                   
                                     1 
                                     , 
                                     1 
                                   
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     i 
                                     , 
                                     j 
                                   
                                   ) 
                                 
                               
                             
                           
                         
                         ) 
                       
                       2 
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     h 
                     = 
                     
                       [ 
                       
                         0 
                         , 
                         15 
                       
                       ] 
                     
                   
                 
               
               
                 
                   Eqn 
                   . 
                   
                       
                   
                   ⁢ 
                   2 
                 
               
             
           
         
       
     
     Because the linear DCT function is orthogonal, total energy in the transform domain, Ak,g(h), is equal to that easily computed in the spatial domain by auto-covariance of a B×B pixel block as described in Eqn. 3 (step  620 ). The second term in this expression below is necessary because unlike the basis function DCT1,1(i,j), a pixel array most probably has a mean μ≠0. 
     
       
         
           
             
               
                 
                   
                     
                       
                         A 
                         
                           k 
                           , 
                           g 
                         
                       
                       ⁡ 
                       
                         ( 
                         h 
                         ) 
                       
                     
                     = 
                     
                       
                         ( 
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               0 
                             
                             
                               B 
                               - 
                               1 
                             
                           
                           ⁢ 
                           
                             
                               ∑ 
                               
                                 j 
                                 = 
                                 0 
                               
                               
                                 B 
                                 - 
                                 1 
                               
                             
                             ⁢ 
                             
                               
                                 p 
                                 
                                   k 
                                   , 
                                   g 
                                 
                                 2 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   
                                     
                                       
                                         i 
                                         g 
                                       
                                       ⁡ 
                                       
                                         ( 
                                         h 
                                         ) 
                                       
                                     
                                     + 
                                     i 
                                   
                                   , 
                                   
                                     
                                       
                                         j 
                                         g 
                                       
                                       ⁡ 
                                       
                                         ( 
                                         h 
                                         ) 
                                       
                                     
                                     + 
                                     j 
                                   
                                 
                                 ) 
                               
                             
                           
                         
                         ) 
                       
                       - 
                       
                         
                           B 
                           2 
                         
                         ⁢ 
                         
                           μ 
                           2 
                         
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     h 
                     = 
                     
                       [ 
                       
                         0 
                         , 
                         15 
                       
                       ] 
                     
                   
                 
               
               
                 
                   Eqn 
                   . 
                   
                       
                   
                   ⁢ 
                   3 
                 
               
             
           
         
       
     
     For each group g and frame k, fingerprint mark recovery is based on comparing each of the 16 ratios of DCT1,1 energy at each marked MB to that of the residual total energy of all (B2−1) other basis functions, DCTi,j, where i≠1, j≠1 (step  625 ): 
     
       
         
           
             
               
                 
                   
                     
                       R 
                       
                         k 
                         , 
                         g 
                       
                     
                     ⁡ 
                     
                       ( 
                       h 
                       ) 
                     
                   
                   = 
                   
                     
                       
                         
                           
                             D 
                             
                               k 
                               , 
                               g 
                             
                           
                           ⁡ 
                           
                             ( 
                             h 
                             ) 
                           
                         
                         
                           
                             
                               A 
                               
                                 k 
                                 , 
                                 g 
                               
                             
                             ⁡ 
                             
                               ( 
                               h 
                               ) 
                             
                           
                           - 
                           
                             
                               D 
                               
                                 k 
                                 , 
                                 g 
                               
                             
                             ⁡ 
                             
                               ( 
                               h 
                               ) 
                             
                           
                         
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       h 
                     
                     = 
                     
                       [ 
                       
                         0 
                         , 
                         15 
                       
                       ] 
                     
                   
                 
               
               
                 
                   Eqn 
                   . 
                   
                       
                   
                   ⁢ 
                   4 
                 
               
             
           
         
       
     
     Denoting the first recovery frame k=0 and setting initial sums represented by S0(h) to zero, the method  600  accumulates the frame-by-frame energy ratios, Rk(h) for k&gt;0, separately for each byte pair, group, and h=[0,15] in a given frame (step  630 ), where
 
 S   k ( h )= S   k−1 ( h )+ R   k ( h ) h=[ 0,15]  Eqn. 5
 
     In one embodiment, the fingerprint recovery method  600  determines the byte pairs from recovered values for groups 4 and 5. In another embodiment, the method  600  extracts each of the six groups independently. At frame k, the fingerprint recovery method  600  selects the index of the maximum of the sixteen cumulative sums, max h  {S k (h)} for a given group as the most likely hexadecimal value, h 1st  (step  635 ), and the index of the second maximum of the sixteen cumulative sums, max h  {S k (h)} for a given group as the second most likely hexadecimal value, h 2nd  (step  640 ). If there is no agreement of h 1st  or h 2nd  of group 4 with h 1st  or h 2nd  of group 5 (i.e., between h 1st  and/or h 2nd  for group 4 and group 5) (step  645 , No branch), the fingerprint recovery method  600  continues processing with the next frame in the sequence (step  610 ). Otherwise (step  645 , Yes branch), the fingerprint recovery method  600  computes the quality of this decision as the relative value of S k (h) for the index h 2nd  having the second to the maximum cumulative sum for a given byte pair and group (step  650 ): 
     
       
         
           
             
               
                 
                   
                     
                       Q 
                       k 
                     
                     ⁡ 
                     
                       ( 
                       h 
                       ) 
                     
                   
                   = 
                   
                     
                       
                         S 
                         k 
                       
                       ⁡ 
                       
                         ( 
                         
                           h 
                           
                             2 
                             ⁢ 
                             nd 
                           
                         
                         ) 
                       
                     
                     
                       
                         S 
                         k 
                       
                       ⁡ 
                       
                         ( 
                         
                           h 
                           
                             1 
                             ⁢ 
                             st 
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   Eqn 
                   . 
                   
                       
                   
                   ⁢ 
                   6 
                 
               
             
           
         
       
     
     The rank2-to-rank1 quality ratio in Eqn. 6 is the principal measure used in defining a stopping rule for fingerprint recovery. In one embodiment, cumulative summation of S k (h) as described in Eqn. 5 continues for each byte pair until the first four groups all yield a value of Q k  less than a predetermined threshold qthrshd (step  655 ), each maintaining a constant h 1st  for a predetermined number qcount of successive frames (step  660 ). If in addition, the hexadecimal values for byte pair indicator groups, g=[4,5] agree with at least one of them yielding the same h 1st  value for frames k and k−1, recovery for that byte pair is terminated, with h 1st  values output for each of the six groups. 
       FIG. 7  is a flow chart that illustrates one embodiment of the method of fingerprint embedding for the present invention. In one embodiment, the fingerprint embedding method  700  substitutes the value of B=4 in Eqn. 1 of the fingerprint recovery method  600  of  FIG. 6  to describe the first diagonal DCT basis function for a 4×4 square array that is smaller and less visible than another embodiment, such as substituting the value of B=8 to describe an 8×8 square array. Due to the symmetry properties of the cosine function, 16 elements of the 4×4 diagonal DCT array have up/down and right/left odd mirrored symmetry of 2×2 sub-blocks, with only 3 unique absolute values α 2 , αβ, and β 2  as shown in Eqn. 7. 
     
       
         
           
             
               
                 
                   
                     
                       DCT 
                       
                         1 
                         , 
                         1 
                       
                     
                     ⁡ 
                     
                       ( 
                       
                         i 
                         , 
                         j 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       1 
                       2 
                     
                     ⁢ 
                     
                       { 
                       
                         
                           
                             
                               α 
                               2 
                             
                           
                           
                             αβ 
                           
                           
                             
                               - 
                               αβ 
                             
                           
                           
                             
                               - 
                               
                                 α 
                                 2 
                               
                             
                           
                         
                         
                           
                             αβ 
                           
                           
                             
                               β 
                               2 
                             
                           
                           
                             
                               - 
                               
                                 β 
                                 2 
                               
                             
                           
                           
                             
                               - 
                               αβ 
                             
                           
                         
                         
                           
                             
                               - 
                               αβ 
                             
                           
                           
                             
                               - 
                               
                                 β 
                                 2 
                               
                             
                           
                           
                             
                               β 
                               2 
                             
                           
                           
                             αβ 
                           
                         
                         
                           
                             
                               - 
                               
                                 α 
                                 2 
                               
                             
                           
                           
                             
                               - 
                               αβ 
                             
                           
                           
                             αβ 
                           
                           
                             
                               α 
                               2 
                             
                           
                         
                       
                       } 
                     
                   
                 
               
               
                 
                   Eqn 
                   . 
                   
                       
                   
                   ⁢ 
                   7 
                 
               
             
           
         
       
     
     Recognizing that α=cos(π/ 8 ) and β=cos( 3 π/ 8 )=sin(π/ 8 ), the three unique absolute values in the above expression are given in Eqn. 8. 
     
       
         
           
             
               
                 
                   
                     
                       α 
                       2 
                     
                     = 
                     
                       
                         
                           cos 
                           2 
                         
                         ⁡ 
                         
                           ( 
                           
                             π 
                             8 
                           
                           ) 
                         
                       
                       = 
                       
                         
                           
                             1 
                             + 
                             
                               cos 
                               ⁡ 
                               
                                 ( 
                                 
                                   π 
                                   4 
                                 
                                 ) 
                               
                             
                           
                           2 
                         
                         = 
                         
                           
                             2 
                             + 
                             
                               2 
                             
                           
                           2 
                         
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     αβ 
                     = 
                     
                       
                         
                           cos 
                           ⁡ 
                           
                             ( 
                             
                               π 
                               8 
                             
                             ) 
                           
                         
                         ⁢ 
                         
                           sin 
                           ⁡ 
                           
                             ( 
                             
                               π 
                               8 
                             
                             ) 
                           
                         
                       
                       = 
                       
                         
                           
                             ( 
                             
                               1 
                               2 
                             
                             ) 
                           
                           ⁢ 
                           
                             sin 
                             ⁡ 
                             
                               ( 
                               
                                 π 
                                 4 
                               
                               ) 
                             
                           
                         
                         = 
                         
                           
                             2 
                           
                           4 
                         
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       β 
                       2 
                     
                     = 
                     
                       
                         
                           sin 
                           2 
                         
                         ⁡ 
                         
                           ( 
                           
                             π 
                             8 
                           
                           ) 
                         
                       
                       = 
                       
                         
                           
                             1 
                             - 
                             
                               cos 
                               ⁡ 
                               
                                 ( 
                                 
                                   π 
                                   4 
                                 
                                 ) 
                               
                             
                           
                           2 
                         
                         = 
                         
                           
                             2 
                             - 
                             
                               2 
                             
                           
                           2 
                         
                       
                     
                   
                 
               
               
                 
                   Eqn 
                   . 
                   
                       
                   
                   ⁢ 
                   8 
                 
               
             
           
         
       
     
     Including the constant factor of ½ from Eqn. 7, the unique floating point DCT basis values are approximately equal to 0.427, 0.177, and 0.073 for the absolute values ½α 2 , ½αβ, and ½β 2 , respectively. 
     The fingerprint embedding method  700  begins by selecting a frame offset and a marking period for a sequence of digital video frames (step  705 ). The frame offset identifies the location of the first marked frame in the sequence of frames, and the marking period identifies the location of successive marked frames in the sequence. 
     To simplify computations for calculation of this first diagonal DCT transform, these floating point values, DCT 1,1 (i, j), are multiplied by 128 and rounded to integers, dct 1,1 (i,j) (step  710 ), which yields the zero-mean 4×4 array, 
                       dct     1   ,   1       ⁡     (     i   ,   j     )       =     {         54       23         -   23           -   54             23       9         -   9           -   23               -   23           -   9         9       23             -   54           -   23         23       54         }             Eqn   .           ⁢   9               
having an auto-covariance,
 
                 ∑     i   =   0     3     ⁢           ⁢       ∑     j   =   0     3     ⁢           ⁢     dct   ⁡     (     i   ,   j     )           ≈     2   14           
to facilitate scaling by simple bit shifting. The auto-covariance for this set of coefficients has an error of only 0.1%. In another embodiment, the floating point DCT 1,1 (i, j) values are multiplied by 32 (unique absolute values of 14, 6, 2) and the resultant is within 0.3% of approximately 2 12 .
 
     Embedded 4×4 fingerprint marks of varying strengths are also generated by different scaling of the diagonal DCT basis function to integer values. Table 1 illustrates a set of 16 such marks, and provides for each mark, the scale factor, and absolute values for the corner (i.e., max=½α 2 ), edge (i.e., med=½αβ), and center (i.e., min=½β 2 ). The number of least significant bits (lsb&#39;s) altered at the mark corner ranges from one to seven, and the auto-covariance varies from 12 for mrk(0) to 22,700 for mrk(14). 
     The fingerprint embedding method selects one of the 15 marks illustrated in Table 1 based on the relative value of integer diagonal dct 1,1  transform energy for the marked location compared to that of the other 15 marked MB locations in a group. As shown in Table 1, the all zero mark is for cases where the ratio exceeds all others in the group without marking. In the block-based grid spacing shown in  FIG. 2 , the video frame  200  includes six marking groups, four which carry 4 bits of fingerprint information each, and two which are used to indicate that a frame is marked and to specify byte pair ordering for fingerprints of more than 16 bits. 
     
       
         
           
               
               
               
               
               
             
               
                 TABLE 1 
               
               
                   
               
               
                   
                 Scale 
                   
                   
                   
               
               
                 Mark 
                 Factor 
                 Corner 
                 Edge 
                 Center 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
               
               
               
            
               
                 mrk(0) 
                 0 
                 0 
                 0 
                 0 
               
               
                 mrk(1) 
                 4 
                 2 
                 1 
                 0 
               
               
                 mrk(2) 
                 12 
                 5 
                 2 
                 1 
               
               
                 mrk(3) 
                 16 
                 7 
                 3 
                 1 
               
               
                 mrk(4) 
                 28 
                 12 
                 5 
                 2 
               
               
                 mrk(5) 
                 32 
                 14 
                 6 
                 2 
               
               
                 mrk(6) 
                 40 
                 17 
                 7 
                 3 
               
               
                 mrk(7) 
                 44 
                 19 
                 8 
                 3 
               
               
                 mrk(8) 
                 56 
                 24 
                 10 
                 4 
               
               
                 mrk(9) 
                 60 
                 26 
                 11 
                 4 
               
               
                 mrk(10) 
                 72 
                 31 
                 13 
                 5 
               
               
                 mrk(11) 
                 84 
                 36 
                 15 
                 6 
               
               
                 mrk(12) 
                 100 
                 43 
                 18 
                 7 
               
               
                 mrk(13) 
                 117 
                 50 
                 21 
                 8 
               
               
                 mrk(14) 
                 128 
                 55 
                 23 
                 9 
               
               
                 mrk(15) 
                 145 
                 62 
                 26 
                 10 
               
               
                   
               
            
           
         
       
     
     To assign strength for a particular mark, the fingerprint embedding method  700  employs an integer-based comparison analogous to the fingerprint recovery method  600  of  FIG. 6 . Before adding a mark to a given marked MB location to denote a hexadecimal value η=[0,F] for a particular byte pair and group, the fingerprint embedding method  700  computes the integer covariance c(η) of pixel values p with integers dct 1,1 (i,j) (step  715 ) according to Eqn. 10, 
                     c   ⁡     (   η   )       =       ∑     i   =   0     3     ⁢       ∑     j   =   0     3     ⁢       p   ⁡     (         i   ⁡     (   η   )       +   i     ,       j   ⁡     (   η   )       +   j       )       ⁢       dct     1   ,   1       ⁡     (     i   ,   j     )                     Eqn   .           ⁢   10               
and the sign s(η)=sgn(c(η) is noted for a mark applied in this location of a given frame. For comparative purposes, basis function energy d(h) is calculated for each of 16 group MB locations as in Eqn. 2, but in integer arithmetic with rounded results achieved by bit shifting to correct for the auto-covariance of dct 1,1 (i,j) equal to approximately 2 14  (step  720 ).
 
 d ( h )=(( c ( h )+64) 7) 2    h=[ 0,15]  Eqn. 11
 
     The fingerprint embedding method  700  calculates the integer auto-covariance for the 4×4 block of pixels (step  725 ) as specified in Eqn. 3 with the mean term in Eqn. 12 for each h=[0,15] also computed by bit shifting. 
     
       
         
           
             
               
                 
                   
                     a 
                     ⁡ 
                     
                       ( 
                       h 
                       ) 
                     
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           0 
                         
                         3 
                       
                       ⁢ 
                       
                         
                           ∑ 
                           
                             j 
                             = 
                             0 
                           
                           3 
                         
                         ⁢ 
                         
                           
                             p 
                             2 
                           
                           ⁡ 
                           
                             ( 
                             
                               
                                 
                                   i 
                                   ⁡ 
                                   
                                     ( 
                                     h 
                                     ) 
                                   
                                 
                                 + 
                                 i 
                               
                               , 
                               
                                 
                                   j 
                                   ⁡ 
                                   
                                     ( 
                                     h 
                                     ) 
                                   
                                 
                                 + 
                                 j 
                               
                             
                             ) 
                           
                         
                       
                     
                     - 
                     
                       
                         ( 
                         
                           
                             [ 
                             
                               8 
                               + 
                               
                                 
                                   ∑ 
                                   
                                     i 
                                     = 
                                     0 
                                   
                                   3 
                                 
                                 ⁢ 
                                 
                                   
                                     ∑ 
                                     
                                       j 
                                       = 
                                       0 
                                     
                                     3 
                                   
                                   ⁢ 
                                   
                                     p 
                                     ⁡ 
                                     
                                       ( 
                                       
                                         
                                           
                                             i 
                                             ⁡ 
                                             
                                               ( 
                                               h 
                                               ) 
                                             
                                           
                                           + 
                                           i 
                                         
                                         , 
                                         
                                           
                                             j 
                                             ⁡ 
                                             
                                               ( 
                                               h 
                                               ) 
                                             
                                           
                                           + 
                                           j 
                                         
                                       
                                       ) 
                                     
                                   
                                 
                               
                             
                             ] 
                           
                           ⁢ 
                           »4 
                         
                         ) 
                       
                       2 
                     
                   
                 
               
               
                 
                   Eqn 
                   . 
                   
                       
                   
                   ⁢ 
                   12 
                 
               
             
           
         
       
     
     The fingerprint embedding method  700  selects a mark index from Table 1 (step  730 ) starting with a predetermined minimum mark index strength equal to zero. As given by Eqn. 13, the 4×4 array of pixels beginning at row i(η) and column j(η) is modified by the addition or subtraction of mrk m (i, j) integer values to pixel value p depending on the natural sign s(i) determined before marking (step  735 ).
 
 P   m ( i (η)+ i,j (η)+ j )= p ( i (η) i,j (η)+ j )+ s (η)mrk m ( i,j ) i=[ 0,3 ],j=[ 0,3]  Eqn. 13
 
     Since marking changes both the value of basis function energy and that of pixel block auto-covariance, the quantities d m (η), a m (η) must be recomputed for each new mark index (step  740 ). The recalculation of d(η) values for each new mark can be greatly simplified by saving c(η) of unmarked pixels and pre-computing covariance of marks mrk m (i, j) and dct 1,1 (i,j) for all mark indices m=[0,15]. 
     To avoid having to perform a division of integer first-diagonal DCT energy, d(h), by the residual (a(h)−d(h)) in Eqn. 4, comparison of a marked 4×4 pixel block and each of the other 15 in a particular group is based upon the relative value of the two products (step  745  and  750 ) given in Eqn. 14 for each unmarked location h for a marking index m. 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             
                               
                                 prod 
                                 m 
                               
                               ⁡ 
                               
                                 ( 
                                 η 
                                 ) 
                               
                             
                             = 
                             
                               
                                 
                                   d 
                                   m 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   η 
                                   ) 
                                 
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   
                                     
                                       a 
                                       m 
                                     
                                     ⁡ 
                                     
                                       ( 
                                       h 
                                       ) 
                                     
                                   
                                   - 
                                   
                                     
                                       d 
                                       m 
                                     
                                     ⁡ 
                                     
                                       ( 
                                       h 
                                       ) 
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               
                                 prod 
                                 m 
                               
                               ⁡ 
                               
                                 ( 
                                 h 
                                 ) 
                               
                             
                             = 
                             
                               
                                 
                                   d 
                                   m 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   h 
                                   ) 
                                 
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   
                                     
                                       a 
                                       m 
                                     
                                     ⁡ 
                                     
                                       ( 
                                       η 
                                       ) 
                                     
                                   
                                   - 
                                   
                                     
                                       d 
                                       m 
                                     
                                     ⁡ 
                                     
                                       ( 
                                       η 
                                       ) 
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                     ⁢ 
                     h 
                   
                   ≠ 
                   η 
                 
               
               
                 
                   Eqn 
                   . 
                   
                       
                   
                   ⁢ 
                   14 
                 
               
             
           
         
       
     
     Because these products can become very large, mark embedding implementation includes scaling as necessary by variable bit shifting. As the m index is incremented, a stronger mark is applied at pixel location p(i(η), j(η)), which raises the diagonal basis function energy d(η) and prod m (η), while prod m (h) is constant and the residual (a(η)=d(η)) remains approximately unchanged. 
     Setting a predetermined comparative multiplier, compmult, provides control of the tradeoff between fingerprint robustness and visibility by selecting the minimum mark strength for each group of each frame for which (step  755 ):
 
prod m (η)&gt;compmult×prod m ( h )∀ h≠η   Eqn. 15
 
     If this condition cannot be met due to either overflow or underflow of marked 8-bit pixel values of a mark index m equal to 15 or the maximum specified in the command line, the mark index is no longer incremented and saturation is noted. 
     Although the disclosed embodiments describe a fully functioning system and method for embedding and recovering spatial fingerprints in marked frames of a sequence of digital video frames, the reader should understand that other equivalent exemplary embodiments exist. Since numerous modifications and variations will occur to those reviewing this disclosure, the system and method for embedding and recovering spatial fingerprints in marked frames of a sequence of digital video frames is not limited to the exact construction and operation illustrated and disclosed. 
     Accordingly, this disclosure intends all suitable modifications and equivalents to fall within the scope of the claims.