Method and apparatus for selective block processing

• US 6,553,127 B1
• Filed: 11/18/1998
• Issued: 04/22/2003
• Est. Priority Date: 05/20/1998
• Status: Expired due to Term

• Current Assignee: Marking Object Virtualization Intelligence, LLC
• Original Assignee: Macrovision Corporation (Adeia Inc.)
• Inventors: Kurowski, Kordian
• Primary Examiner(s): COUSO, YON JUNG
• Assistant Examiner(s): Choobin, M B
• Application Number:
  US09/195,178
• Time in Patent Office: 1,616 Days
• Field of Search: 380/54, 382/100, 382/112, 382/181, 707/10, 713/176
• US Class Current: 382/100
• CPC Class Codes: G06T 1/0028 Adaptive watermarking, e.g. Human Visual System [HVS]-based watermarking
• CPC Class Codes: G06T 2201/0051 Embedding of the watermark in the spatial domain
• CPC Class Codes: G06T 2201/0052 Embedding of the watermark in the frequency domain
• CPC Class Codes: G06T 2201/0061 Embedding of the watermark in each block of the image, e.g. segmented watermarking
• CPC Class Codes: G06T 2201/0065 Extraction of an embedded watermark; Reliable detection
• CPC Class Codes: G06T 2201/0202 whereby the quality of watermarked images is measured; Measuring quality or performance of watermarking methods; Balancing between quality and robustness
• CPC Class Codes: H04N 1/32144 embedded in the image data, i.e. enclosed or integrated in the image, e.g. watermark, super-imposed logo or stamp
• CPC Class Codes: H04N 1/32187 with selective or adaptive application of the additional information, e.g. in selected frequency coefficients
• CPC Class Codes: H04N 1/32197 according to the spatial domain characteristics of the transform domain components
• CPC Class Codes: H04N 1/32229 with selective or adaptive application of the additional information, e.g. in selected regions of the image H04N1/32213 takes precedence
• CPC Class Codes: H04N 1/32235 in highly textured regions
• CPC Class Codes: H04N 19/00 Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
• CPC Class Codes: H04N 19/467 characterised by the embedded information being invisible, e.g. watermarking
• 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 2201/3233 of authentication information, e.g. digital signature, watermark
• CPC Class Codes: H04N 2201/327 which are undetectable to the naked eye, e.g. embedded codes

Abstract

Methods, devices and systems for embedding and detecting a watermark in a data stream, such as a video stream. A texture criterion is evaluated for each block of the data stream. The texture criterion measures a variation of selected characteristics associated with each element of the data stream, such as luminance and chrominance. Only those blocks that are determined to have at least a predetermined degree of variation in the selected characteristic are selected for embedding of a watermark. By providing the watermark detector with a block selector that evaluates the same texture criterion as was employed in the watermark embedder, the detector attempts detection of the watermark only in those blocks having been determined to have the predetermined degree of variation of the selected characteristic, or greater. By attempting detection only in such blocks, the number of detection computations is decreased and the watermark signal to data stream noise ratio is increased, thereby facilitating detection of even weak watermarks.

Claims

1. A device (150) for detecting the watermark in a watermarked source data stream which includes a plurality of data elements, each data element having at least one characteristic associated therewith, wherein the watermark embedded in selected blocks of the source data stream meet a texture criterion measuring a variation of a selected characteristic associated with each data element of the source data stream, wherein the texture criterion is unrelated to any relationship between corresponding blocks of two different frames, the device comprising:

a buffer circuit (160) receiving as input the watermarked data stream, the buffer circuit buffering and dividing the watermarked data stream into the selected blocks, wherein the blocks are of the same size as chosen arbitrarily in the embedding process reflected in the watermarked source data stream (145);

a block selector circuit (120, 170) coupled to an output of the buffer circuit, the block selector circuit selecting blocks of the watermarked data stream based on a substantially similar texture criterion as that used in selecting the blocks for embedding the watermark, wherein the data input to the criterion function comes only from the block being tried for selection; and

a detector circuit (180) coupled to an output of the block selector circuit, the detector circuit detecting the watermark only in the blocks selected by the block selector circuit, to decrease the time and number of operations necessary to process a given number of blocks.

2. The device of claim 1, wherein the block selector circuit evaluates the texture criterion in a spatial domain.

3. The device of claim 1, wherein the texture criterion used in the detecting device is identical to that used in watermark embedding.

4. The device of claim 1, wherein the block selector circuit is a same circuit as is used to select blocks in which to embed the watermark during an embedding process.

23. The device of claim 1, wherein the data input to the criterion function comes from multiple blocks in the same frame as the frame containing the block being tried for selection.

5. A device (110) for embedding a watermark in selected blocks of a source data stream having a plurality of data elements, wherein the selected blocks meet a texture criterion that measures a variation of a selected characteristic associated with each data element, wherein the texture criterion is unrelated to any relationship between corresponding blocks of two different frames of the source data stream, the device comprising:

a buffer circuit (115) for buffering and dividing the source data stream into a plurality of the selected blocks, wherein the block size is chosen arbitrarily with all blocks being of the same size;

a block selector circuit (120, 170) coupled to the buffer circuit, the block selector circuit selecting the blocks of the source data stream that meet a substantially similar texture criterion, wherein the data input to the criterion function comes only from the block being tried for selection; and

an embedder circuit (130, 140) coupled to the block selector circuit and an output of the buffer circuit, the embedder circuit embedding the watermark only in the selected blocks of arbitrary size that meet said substantially similar texture criterion.

6. The device of claim 5, wherein the buffer circuit (115) and the block selector circuit (120, 170) each provide blocks to the embedder circuit, the embedder circuit being selectively disabled and enabled based upon an output of the block selector circuit for selecting.

7. The device of claim 5, wherein the buffer circuit (115) is connected to a first input of a logic device (140) and to an input of the block selector circuit (120, 170), the block selector circuit being connected to the embedder circuit whose output is connected to a second input of the logic device, the block selector circuit controlling an operation of the logic device to cause the logic device to selectively output blocks with and without watermarks.

8. The device of claim 7, wherein the logic device includes a multiplexer (140).

9. The device of claim 5, wherein the block selector circuit outputs a texture value to the embedding means, the embedding means modulating a strength of the watermark depending upon a magnitude of the texture value.

24. The device of claim 5, wherein the data input to the criterion function comes from multiple blocks in the same frame as the frame containing the block being tried for selection.

10. A method of detecting a watermark embedded in selected blocks of a watermarked data stream having a plurality of data elements, wherein the selected blocks meet a texture criterion that measures a variation of a selected characteristic associated with each data element of the watermarked data stream, wherein the texture criterion is unrelated to any relationship between corresponding blocks of two different frames, the method comprising:

dividing the watermarked data stream into a plurality of equally sized blocks as chosen arbitrarily in the embedding process reflected in the watermarked source data stream (145);

selecting only the blocks that meet substantially similar texture criterion as that used in selecting the blocks for embedding the watermark, wherein the data input to the criterion function comes only from the block being tried for selection; and

detecting the watermark only in the blocks that were embedded with the watermark and were selected by the selecting step thereby decreasing the time and number of operations necessary to process a given number of blocks.

11. The method of claim 10, wherein the detecting involves calculating the average amplitude of corresponding data elements in the selected blocks in a spatial domain relative to a relatively uncorrelated data stream.

12. The method of claim 10, wherein the data stream is a video stream.

13. The method of claim 12 further characterized by preventing playback of the video stream when the watermark is not detected.

14. The method of claim 10, wherein the texture criterion used in the selecting of the selected blocks is identical to the texture criterion used in the watermark embedding.

21. The method of claim 10 further characterized by:

selecting only those blocks likely to include the watermark using the same texture criterion as was used in the watermark embedding process; and

accumulating the selected blocks in a spatial domain to reinforce the watermark, if present, relative to a relatively uncorrelated data stream.

25. The device of claim 10, wherein the data input to the criterion function comes from multiple blocks in the same frame as the frame containing the block being tried for selection.

15. A method of embedding a watermark in selected blocks of a source data stream having a plurality of data elements, wherein the selected blocks meet a texture criterion that measures a variation of a selected characteristic associated with each data element, wherein the texture criterion is unrelated to any relationship between corresponding blocks of two different frames of the source data stream, the method comprising:

buffering and dividing the source data stream into a plurality of the selected blocks, wherein the block size is chosen arbitrarily with all blocks being of the same size;

testing the blocks of arbitrarily chosen same size divided from the source data stream to determine if they meet substantially similar texture criterion, wherein the data input to the criterion function comes only from the block being tried for selection and

once the texture criterion is met, embedding the watermark only in the selected blocks of arbitrarily chosen same size that meet said substantially similar texture criterion.

16. The method of claim 15, wherein the testing comprises:

subtracting a maximum value of the selected characteristic of the texture criterion from a minimum value of the selected characteristic of the texture criterion; and

comparing an absolute value of a result of the subtraction with a given threshold value.

17. The method of claim 15, wherein the testing comprises:

generating a sum of absolute values of differences of the selected characteristic of the texture criterion; and

comparing the sum of absolute values of differences with a given threshold value.

18. The method of claim 17, wherein the data elements are pixels, and the difference operations are performed on pairs of pixels having a separation, location and/or pattern which represents frequencies that best mask the watermark.

19. The method of claim 15, further characterized by de-emphasizing variations of the selected characteristic along edges of each block relative to variations of the selected characteristic within an interior of each block.

20. The method of claim 19, wherein the de-emphasizing is characterized by assigning a weighting coefficient to each data element within each block, data elements along edges of each block being assigned a lower coefficient than data elements within an interior of each block.

26. The device of claim 15, wherein the data input to the criterion function comes from multiple blocks in the same frame as the frame containing the block being tried for selection.

22. A method of embedding and detecting a watermark in selected blocks of a source data stream having a plurality of data elements, wherein the selected blocks meet a substantially similar texture criterion that measures a variation of a selected characteristic associated with each data element, wherein the texture criterion is unrelated to any relationship between corresponding blocks of two different frames of the source data stream, the method comprising:

dividing the source data stream into the selected blocks of substantially similar texture criterion, wherein the selected blocks are divided into a block size which is chosen arbitrarily with all blocks being of the same size;

selecting only the blocks that meet said substantially similar texture criterion, wherein the data input to the criterion function comes only from the block being tried for selection embedding the watermark only in the selected blocks that meet the substantially similar texture criterion;

in the process of detecting, selecting the blocks of the watermarked source data stream based on the same substantially similar texture criterion as that used in selecting the same blocks for embedding the watermark, wherein the size of the blocks is the same as arbitrarily chosen in the embedding process; and

detecting the watermark only in the selected blocks.