Watermark detection utilizing regions with higher probability of success

• US 7,013,021 B2
• Filed: 08/31/2001
• Issued: 03/14/2006
• Est. Priority Date: 03/19/1999
• Status: Expired due to Term

• Current Assignee: Digimarc Corporation
• Original Assignee: Digimarc Corporation
• Inventors: Sharma, Ravi K., Gustafson, Ammon E.
• Primary Examiner(s): Patel, Kanjibahi
• Assistant Examiner(s): Tabatabai, Abolfazl
• Application Number:
  US09/945,244
• Publication Number:
  US 20020057823A1
• Time in Patent Office: 1,656 Days
• Field of Search: 382/100, 382/232, 382/240, 380/51, 380/54, 380/201, 380/210, 380/252, 380/287, 713/176, 713/179, 348/461, 348/463, 370522-529, 725/9, 725/20, 725/22, 283/72, 283 74- 81, 283/85, 283/93, 283/113, 283/901, 283/902, 358/3.28, 375/130
• US Class Current: 382/100
• CPC Class Codes: G06T 1/0071 using multiple or alternating watermarks
• CPC Class Codes: G06T 1/0078 using multiple thresholds
• CPC Class Codes: G06T 2201/0065 Extraction of an embedded watermark; Reliable detection
• CPC Class Codes: H04N 1/32149 Methods relating to embedding, encoding, decoding, detection or retrieval operations
• 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/32235 in highly textured regions
• CPC Class Codes: H04N 1/3224 in edge regions
• 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

The present invention detects the presence of a digital watermark in an image by selecting regions within the image having a high probability of containing the watermark. The image is examined to determine which regions of the image have characteristics indicating that there is a high probability that a watermark signal can be detected in that region of the image. The regions that have a high probability that a watermark can be detected (in contrast to all regions of the image) are examined to find watermark data. Probability factors used to select detection regions include: requiring a minimum variance separation between detection blocks; requiring a minimum distance between overlapping blocks; segmenting the detection blocks into a first and second subset based on separate criteria; establishing a keep away zone to prevent selection of a detection block near an image'"'"'s border; and selecting a detection block only after its neighbors met sufficient threshold requirements. These probability factors can be used separately or in conjunction to determine those regions of an image that have characteristics indicating a high probability that a watermark signal can be detected therein.

Claims

1. A method of detecting a digital watermark in an image or video comprising:

providing at least one probability factor to select a plurality of detection blocks in a watermarked image or video, wherein the probability factor represents or describes a characteristic of the image or video; and

analyzing selected detection blocks to locate watermark data.

2. The method according to claim 1, wherein the at least one probability factor comprises a minimum distance between at least two selected detection blocks.

3. The method according to claim 2, wherein the minimum distance comprises a minimum city-block distance between the at least two selected detection blocks.

4. The method according to claim 3, wherein the minimum distance comprises a minimum diagonal requirement between the at least two selected detection blocks.

5. The method according to claim 2, wherein the at least two selected detection blocks overlap.

6. The method according to claim 1, wherein the at least one probability factor comprises selecting a first subset of detection blocks and selecting a second subset of detection blocks.

7. The method according to claim 6, further comprising requiring a relatively broader spacing of the first subset of detection blocks in the image in comparison to the second subset of detection blocks in the image.

8. The method according to claim 6, wherein said analyzing comprises analyzing the first subset of detection blocks to detect the watermark data.

9. The method according to claim 8, wherein the watermark data comprises a synchronization or orientation signal.

10. The method according to claim 6, wherein said analyzing step comprises analyzing the first or second subset of detection blocks to recover the watermark data.

11. The method according to claim 10, wherein the watermark data comprises a message.

12. The method according to claim 6, wherein said analyzing comprises analyzing the second subset of detection blocks to determine a translation value of an embedded watermark signal.

13. The method according to claim 1, wherein the at least one probability factor comprises a minimum variance separation between at least two of the plurality of selected detection blocks.

19. The method according to claim 1, wherein the at least one probability factor comprises an edginess count.

20. The method according to claim 19, wherein the edginess count is determined by comparing a pixel to a horizontal neighbor pixel and to a vertical neighbor pixel.

21. The method according to claim 20, further comprising creating a horizontal edge count map and a vertical edge count map.

22. The method according to claim 21, further comprising combining the horizontal edge count map with the vertical edge count map to generate a second edge count map.

23. The method according to claim 22, further comprising summing values within the second edge count map to generate a total edge count.

24. The method according to claim 23, wherein the total edge count is provided to select a detection block.

25. The method according to claim 1, wherein the at least one probability factor comprises an evaluation of detection blocks neighboring a preliminarily selected detection block.

26. The method according to claim 25, wherein the evaluation comprises comparing the neighboring detection blocks'"'"' variance to a threshold value.

27. The method according to claim 26, wherein the evaluation further comprises comparing the neighboring detection blocks'"'"' edginess to an edginess value.

31. The method according to claim 1, wherein the at least one probability factor comprises variance in a region.

32. The method according to claim 31, wherein to select a detection block the variance in the detection block must be greater than a threshold variance, the threshold being dependent on image resolution.

33. The method according to claim 32, wherein to select a detection block the variance in the detection block must be greater than a threshold variance, the threshold being adaptively determined based on at least one of image resolution, image characteristics, processing speed, available memory and processing time.

34. The method according to claim 1, wherein the at least one probability factor comprises an edginess in a region.

35. The method according to claim 34, wherein to select a detection block the edginess in the detection block must be greater than a threshold edginess.

36. The method according to claim 34, wherein to select a detection block the edginess in the detection block must be greater than a threshold edginess, the threshold being adaptively determined based on at least one of image resolution, image characteristics, processing speed, available memory and processing time.

37. The method according to claim 1, wherein the at least one probability factor comprises a probability of watermark detection based on a multivariable variance distribution.

38. The method according to claim 1, wherein the at least one probability factor comprises a region'"'"'s color saturation.

39. The method according to claim 1, wherein the at least one probability factor comprises a combined metric between a region'"'"'s color saturation and at least one of the region'"'"'s variance and edginess.

14. A method of detecting a digital watermark in an image or video comprising:

providing at least one probability factor to select a plurality of detection blocks in a watermarked image or video; and

analyzing the selected detection blocks to locate watermark data, wherein the at least one probability factor comprises a keep away zone near a border of the image.

15. The method according to claim 14, wherein a detection block is not selected if centered within the keep away zone.

16. A method of detecting a digital watermark in an image or video comprising:

providing at least one probability factor to select a plurality of detection blocks in a watermarked image or video; and

analyzing the selected detection blocks to locate watermark data, wherein the at least one probability factor comprises a probability of watermark detection based on a variance distribution.

17. The method according to claim 16, wherein the at least one probability factor further comprises a multivariable distribution.

18. The method according to claim 17, wherein the multivariable distribution comprises a distribution of variance and edginess.

28. A method of detecting a digital watermark in imagery or video comprising:

providing at least one probability factor to select a plurality of detection blocks in watermarked imagery or video; and

analyzing the selected detection blocks to locate watermark data, wherein the at least one probability factor is determined adaptively based on at least one of processor speed, available memory and processing time requirements.

29. The method according to claim 28, wherein the at least one probability factor comprises determining a number of blocks for the plurality of detection blocks.

30. The method according to claim 28, wherein the at least one probability factor comprises an amount of overlap between the plurality of detection blocks.

40. A method to select at least one region for detection of a watermark signal comprising:

determining variance for each region in an image neighborhood;

comparing the variance of each neighborhood region to a first threshold; and

selecting a central region in the neighborhood when the variance of at least some of the neighborhood regions is greater than the first threshold.

41. The method according to claim 40, further comprising comparing an edginess value of each of the neighboring regions to a second threshold, wherein the central region is selected only when the variance of at least some of the neighboring regions is greater than the first threshold and when the edginess of at least some of the neighboring regions is greater than the second threshold.

42. A method of using probability factors to select detection blocks in an image, the detection block to be analyzed to detect a digital watermark embedded in the image, said method comprising:

requiring a minimum distance between any two selected detection blocks;

requiring a minimum variance separation between at least two of the selected detection blocks;

requiring a minimum border distance between at least one selected detection block and an image border; and

before selecting a detection block, requiring at least some of the detection block'"'"'s neighboring blocks meet at least a minimum threshold variance requirement.