Embedding a digital signature in a video sequence

• US 5,960,081 A
• Filed: 06/05/1997
• Issued: 09/28/1999
• Est. Priority Date: 06/05/1997
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Inventors: Vynne, Thorbjorn, Jordan, Frederic
• Primary Examiner(s): Buczinski, Stephen C.
• Application Number:
  US08/869,792
• Time in Patent Office: 845 Days
• Field of Search: 380/14, 380/10, 380/20, 380/23, 380/54, 348/461, 348/467
• US Class Current: 713/176
• CPC Class Codes: G06T 1/0085 Time domain based watermarking, e.g. watermarks spread over several images
• CPC Class Codes: G06T 2201/0053 Embedding of the watermark in the coding stream, possibly without decoding; Embedding of the watermark in the compressed domain
• CPC Class Codes: H04N 19/467 characterised by the embedded information being invisible, e.g. watermarking
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/517 by encoding
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 2005/91335 the copy protection signal being a watermark
• CPC Class Codes: H04N 21/23892 involving embedding information at multiplex stream level, e.g. embedding a watermark at packet level
• CPC Class Codes: H04N 21/8358 involving watermark protecting executable software by watermarking G06F21/16; image watermarking in general G06T1/0021; watermarks inserted in still images for transmission purposes H04N1/32144; inserting watermarks during video coding H04N19/467
• CPC Class Codes: H04N 5/913 for scrambling ; for copy protection
• CPC Class Codes: H04N 7/24 Systems for the transmission of television signals using pulse code modulation H04N21/00 takes precedence

Abstract

Method and apparatus for watermarking digital video material by embedding a digital signature. One embodiment of the system integrates the embedding procedure into a block-based compression scheme. In one embodiment, a 32-bit digital signature is embedded into the x- and y-coordinates of motion vectors. Since not all motion vectors are suitable for coding (with regard to objectionable visible artifacts), three hybrid selection criteria have been developed for determining whether or not to code a motion vector. A probabilistic coding procedure has also been developed to avoid problems that arise when fewer than 16 blocks and/or vectors (where 16 vectors correspond to 32 bits) can be coded in a frame. One such procedure makes use of binary random sequences to virtually code the signature into the motion vectors. The system has been implemented on a CRAY T3D massively parallel supercomputer, where a near-real-time (5 frames per second) embedding of the signature is obtainable. The results show that it is possible to embed and retrieve a 32-bit signature if enough blocks over time are selected.

Claims

1. A method for embedding and retrieving information in a video signal, the method comprising the steps of:

selecting a first subset and a second subset of the video signal;

determining a relationship between the first subset and the second subset of the video signal;

changing the relationship between the first subset and the second subset of the video signal, wherein the step of changing includes encoding the information into the video signal to produce a changed video signal having a changed relationship; and

detecting the changed relationship from the changed video signal and, from the detected changed relationship, retrieving the encoded information;

wherein the first subset belongs to one frame and the second subset belongs to a different frame of the video signal.

2. The method according to claim 1, wherein the step of selecting includes selecting image element subsets using one or more visual perception criteria.

3. The method according to claim 1, wherein the first and second subsets each represent rectangular blocks in the frames of the video signal.

4. The method according to claim 1, wherein the step of selecting includes selecting visually similar subsets.

5. The method according to claim 4, wherein the relationship is a motion between selected subsets.

6. The method according to claim 5, wherein the steps of selecting, or changing the relationship, or both, include using a key to encrypt the encoding of the information into the changed relationship.

7. A system for embedding digital information into a video signal such that the digital information can later be retrieved, the digital information including a plurality of bits, the system comprising:

a selector that selects a first subset and a second subset of the video signal;

a comparator that determines a relationship between the first subset and the second subset of the video signal; and

a changer that changes the relationship between the first subset and the second subset of the video signal by encoding the information into the video signal to produce a changed video signal having a changed relationship;

wherein the first subset belongs to one frame and the second subset belongs to a different frame of the video signal.

8. The system according to claim 7, wherein the selector selects image element subsets using one or more visual perception criteria.

9. The system according to claim 7, wherein the first and second subsets each represent rectangular blocks in the frames of the video signal.

10. The system according to claim 7, wherein the step of selecting includes selecting visually similar subsets.

11. The system according to claim 10, wherein the relationship is a motion between selected subsets.

12. The system according to claim 11, wherein the changer uses an encryption key to encrypt the information.

13. The system according to claim 11, wherein the selector uses an encryption key to select subsets in order to encrypt a location of the information.

14. The system according to claim 11, wherein the selector and/or changer use an encryption key in order to encrypt the encoding of the information into the changed relationship.

15. A method for embedding a retrievable watermark into a video signal, the video signal providing a series of video frames including a first frame and a second frame, the method comprising the steps of:

detecting a change between the first frame and the second frame;

producing change information based on the change; and

encoding the retrievable watermark into the change information.

16. A method for embedding a retrievable watermark into a video signal, the video signal providing a series of video frames including a first frame and a second frame, the method comprising the steps of:

detecting a change between the first frame and the second frame;

producing change information based on the change; and

encoding the watermark into the change information;

wherein the step of encoding modifies a motion vector based on the watermark.

17. The method according to claim 16, wherein the step of encoding includes using a encryption key to encrypt the encoding of the watermark into the change information.

18. The method according to claim 16, further comprising the step of:

obtaining a set of motion vectors V(n)={v₁, v₂, . . . v_n }, where V_i =(x_i, y_i), i=1, 2, . . . , m, and m is the number of blocks in each frame, on basis of frame(n-1) by a minimum mean-square-error fit of each block in frame(n), and

wherein the step of encoding uses the set of obtained motion vectors.

19. The method according to claim 16, further comprising the step of:

selecting the subset of blocks based on criteria that are met by blocks in frame_d (n-1), and

wherein the step of encoding uses the selected subset of blocks.

20. The method according to claim 16, further comprising the step of:

selecting the subset of blocks based on criteria that include a threshold value C_hist ;

max (|x_m -x_i |)<

C_hist, I=1, 2, . . . , M

where x_m is the median value, M is the number of pixels in the block and C_hist (histogram criterion) is the maximum-allowed distance to the median value, wherein the difference in pixel intensity from the median intensity for surrounding pixels is smaller than the threshold value C_hist, and

wherein the step of encoding uses the selected subset of blocks.

21. The method according to claim 16, further comprising the step of:

selecting the subset of blocks based on criteria that include a threshold value C.sub.σ

, wherein a block is selected if σ

<

C.sub.σ

where C.sub.σ

(standard deviation criterion) is a threshold value determining the visible limit, and wherein a standard deviation σ

is calculated for the block b(k) using a definition ##EQU16## where ##EQU17## x is the gray-level value, and M is the number of pixels in the image, and wherein the step of encoding uses the selected subset of blocks.

22. The method according to claim 16, further comprising the step of:

selecting the subset of blocks based on criteria that include a threshold value C.sub.σ

, and a block is selected if, a standard deviation (σ

_xy of the pixel gray-level values inside a block plus a band around the block) is less or equal to a given threshold value C.sub.σ

;

σ

_xy ≦

C.sub.σ

where C.sub.σ

(standard deviation criterion) is a threshold value determining the visible limit, and wherein a standard deviation σ

is calculated for the block b(k) using a definition ##EQU18## where ##EQU19## x is the gray-level value, and M is the number of pixels in the image, and wherein the step of encoding uses the selected subset of blocks.

23. The method according to claim 16, further comprising the step of:

selecting the subset of blocks based on criteria that include a threshold value C_size, wherein a magnitude of a motion vector v is larger than or equal to a given threshold value C_size ;

|v|≧

C_size where v is the motion vector and C_size (motion-vector size criterion) is the minimum size of the motion vector, and

wherein the step of encoding uses the selected subset of blocks.

24. The method according to claim 16, further comprising the step of:

selecting the subset of blocks based on criteria that include;

a first hybrid criterion including a first criterion for standard deviation combined with a criterion for maximum distance to the median;

a second hybrid criterion including a second criterion for standard deviation combined with a criterion for a shape of the frequency plot; and

a third hybrid criterion including a third criterion for standard deviation combined with a criterion for size of the motion vectors, and

wherein the step of encoding uses the subset of blocks.

25. A method for embedding digital information into a video signal such that the digital information can later be retrieved;

the digital information including a plurality of bits, the video signal providing a series of video frames including a first frame and a subsequent second frame, the first frame being subdivided into a plurality of blocks, the method comprising the steps of;

obtaining a motion vector for each one of a subset of the blocks in the first frame, each motion vector representative of a displacement between a block in the first frame and a corresponding block in the second frame; and

modifying one or more of said motion vectors based on a value of one or more bits of said digital information such that the digital information can later be retrieved.

26. The method according to claim 25, further comprising the step of:

selecting the subset of blocks based on criteria that are met by blocks in frame_d (n-1).

27. A method for embedding digital information into a video signal such that the digital information can later be retrieved;

the digital information including a plurality of bits, the video signal providing a series of video frames including a first frame and a subsequent second frame, the first frame being subdivided into a plurality of blocks, the method comprising the steps of;

obtaining a motion vector for each one of a subset of the blocks in the first frame, each motion vector representative of a displacement between a block in the first frame and a corresponding block in the second frame; and

modifying one or more of said motion vectors based on a value of one or more bits of said digital information;

wherein the digital information includes a signature having a predefined bitset S(I), I=1, 2, . . . , L, where L is the number of bits in the signature, and wherein the step of modifying modifies a component of the motion vector based on one or more bits of said digital information.

28. A method for embedding digital information into a video signal, the video signal providing a series of video frames including a first frame and a subsequent second frame, the method comprising the steps of:

detecting a motion between the first frame and the second frame;

producing a motion vector set based on the motion;

selecting change information that includes a suitable subset of the motion vector set that is suitable for coding; and

encoding the digital information into the change information such that the digital information can later be retrieved.

29. The method according to claim 28, wherein the step of encoding includes using a key to encrypt the encoding of the information into the change information.

30. A watermarking system for embedding digital information into a video signal such that the digital information can later be retrieved;

the digital information including a plurality of bits, the video signal providing a series of video frames including a first frame and a subsequent second frame, the first frame being subdivided into a plurality of blocks, the watermarking system comprising;

a block-based motion-estimation (BBME) coder, and wherein the BBME coder generates a motion vector for each one of a subset of the blocks in the first frame, each motion vector representative of a displacement between a block in the first frame and a corresponding block in the second frame; and

a motion-vector modifier coupled to an output of the BBME coder that modifies one or more of said motion vectors based on a value of one or more bits of said digital information.

31. The watermarking system according to claim 30, wherein the subset of blocks is selected based on criteria that include:

a first hybrid criterion including a first criterion for standard deviation combined with a criterion for maximum distance to the median;

a second hybrid criterion including a second criterion for standard deviation combined with a criterion for a shape of the frequency plot;

or

a third hybrid criterion including a third criterion for standard deviation combined with a criterion for size of the motion vectors.

32. A storage medium having a computer program stored thereon for causing a suitably programmed system to embed information in a video signal by performing the following steps when such program is executed on the system:

selecting a first subset and a second subset of the video signal;

determining a relationship between the first subset and the second subset of the video signal; and

changing the relationship between the first subset and the second subset of the video signal, wherein the step of changing includes encoding the information into the video signal to produce a changed video signal having a changed relationship;

wherein the first subset belongs to one frame and the second subset belongs to a different frame of the video signal.

33. The storage medium of claim 32, wherein the computer program comprises programming for further causing the system, when such program is executed on the system, to perform the following additional step:

detecting the changed relationship from the changed video signal and, from the detected changed relationship, retrieving the encoded information.

34. The storage medium of claim 32, wherein in the step of determining a relationship, the relationship is a motion between selected subsets.

35. The storage medium of claim 32, wherein the steps of selecting, or changing the relationship, or both, include using a key to encrypt the encoding of the information into the changed relationship.

36. A data structure for holding video information, the video information having embedded digital information such that the digital information can be retrieved from the video information, the digital information including a plurality of bits, the data structure comprising:

a plurality of video frames, each frame being subdivided into a plurality of blocks; and

a plurality of motion vectors, each one of said motion vectors associated with one block of a selected subset of the plurality of blocks, each motion vector representative of a displacement between a block in one frame and a corresponding block in a different frame, wherein the plurality of motion vectors has been modified based on a value of one or more bits of said digital information.