Segmentation in digital watermarking

• US 7,068,809 B2
• Filed: 08/27/2001
• Issued: 06/27/2006
• Est. Priority Date: 08/27/2001
• Status: Expired due to Term

• Current Assignee: Digimarc Corporation
• Original Assignee: Digimarc Corporation
• Inventors: Stach, John
• Primary Examiner(s): Choobin, Barry
• Application Number:
  US09/940,872
• Publication Number:
  US 20030039376A1
• Time in Patent Office: 1,765 Days
• Field of Search: 382/100, 382/173, 382/180, 380/54, 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/0202 whereby the quality of watermarked images is measured; Measuring quality or performance of watermarking methods; Balancing between quality and robustness

Abstract

Segmentation techniques are used in methods for embedding and detecting digital watermarks in multimedia signals, such as images, video and audio. A digital watermark embedder segments a media signal into arbitrary shaped regions based on a signal characteristic, such as a similarity measure, texture measure, shape measure or luminance or other color value extrema measure. The attributes of these regions are then used to adapt an auxiliary signal such that it is more effectively hidden in the media signal. In one example implementation, the segmentation process takes advantage of a human perceptibility model to group samples of a media signal into contiguous regions based on their similarities. Attributes of the region, such as its frequency characteristics, are then adapted to the frequency characteristics of a desired watermark signal. One embedding method adjusts a feature of the region to embed elements of an auxiliary signal, such as an error correction encoded message signal. The detecting method re-computes the segmentation, calculates the same features, and maps the feature values to symbols to reconstruct an estimate of the auxiliary signal. The auxiliary signal is then demodulated or decoded to recover the message using error correction decoding/demodulation operations.

Claims

1. A method of embedding a digital watermark into a media signal comprising:

segmenting the media signal into arbitrary shaped regions according to at least one signal characteristic of the media signal;

evaluating a feature of the regions; and

modifying the feature to embed hidden auxiliary data in the media signal.

2. The method of claim 1 wherein the characteristic comprises a similarity measure.

3. The method of claim 1 wherein the characteristic comprises a texture measure.

4. The method of claim 1 wherein the characteristic comprises a color extrema measure.

5. The method of claim 4 wherein the color extrama comprises luminance extrema.

6. The method of claim 1 wherein the characteristic comprises a shape measure.

7. The method of claim 1 wherein the segmentation comprises a watershed segmentation of the at least one signal characteristic.

8. The method of claim 1 wherein the feature comprises a frequency domain transform of a region.

9. The method of claim 8 wherein modifying comprises modifying the frequency domain transform according to a digital watermark signal definition.

10. The method of claim 1 wherein modifying comprises setting an attribute of a region to a value corresponding to an element of the auxiliary data.

11. The method of claim 10 wherein the auxiliary data comprises an intermediate signal formed from a multi-bit message.

12. The method of claim 11 wherein forming the intermediate signal comprises spread spectrum modulating the multi-bit message.

13. The method of claim 11 wherein forming the intermediate signal comprises error correction encoding the multi-bit message.

14. The method of claim 1 wherein modifying comprises modifying shape of a region to correspond to auxiliary data to be embedded.

15. The method of claim 1 wherein modifying comprises modifying a feature in a region so that the modified feature has a predetermined relationship with another feature in the region, where the predetermined relationship correspond to a symbol to be embedded.

16. The method of claim 15 wherein relative positions of boundary pixels are changed to embed the symbol.

17. The method of claim 1 wherein modifying comprises transforming a feature of a region to created a transformed region, and adding the transformed feature to the region.

18. The method of claim 17 wherein a symbol in the auxiliary data is embedded by establishing a predetermined relationship between the transformed region and the region.

19. The method of claim 17 wherein a symbol in the auxiliary data is embedded by adding the transformed region to the region to form a new region with a feature that corresponds to the symbol.

20. The method of claim 17 wherein a first transform is used to embed a first symbol;

and a second transform is used to embed a second symbol.

21. A computer readable medium on which is stored instructions for performing the method of claim 1.

22. A computer readable medium on which is stored an electronic media signal embedded with a digital watermark using the method of claim 1.

23. A physical object bearing an image which is embedded with a digital watermark using the method of claim 1.

24. A method of reading a digital watermark that has been embedded in a media signal so as to be substantially imperceptible in the media signal, the method comprising:

segmenting the media signal into arbitrary shaped regions based on at least one signal characteristic of the media signal;

evaluating a feature of the regions; and

computing message symbols from the evaluated features of the regions.

25. The method of claim 24 wherein the characteristic comprises a similarity measure.

26. The method of claim 24 wherein the characteristic comprises a texture measure.

27. The method of claim 24 wherein the characteristic comprises a color extrema measure.

28. The method of claim 27 wherein the color extrama comprises luminance extrema.

29. The method of claim 24 wherein the characteristic comprises a shape measure.

30. The method of claim 24 wherein the segmentation comprises a watershed segmentation of the at least one signal characteristic.

31. The method of claim 24 wherein the feature comprises a frequency domain transform of a region.

32. The method of claim 24 wherein computing message symbols comprises estimating message symbols by computing a relationship between the feature and another feature in the region;

and assigning a symbol value based on the relationship, where the symbol value is selected from predetermined symbol values, each being associated with a predetermined feature relationship.

33. The method of claim 24 wherein computing message symbols comprises estimating message symbols by matching the feature with predetermined feature values, each predetermined feature value being associated with a predetermined symbol.

34. The method of claim 24 wherein computing message symbols comprises estimating message symbols from patterns of boundary pixels of the regions, wherein message symbols correspond to predetermined boundary patterns.

35. The method of claim 24 wherein computing the message symbols comprises estimating message symbols from shapes of the regions, wherein message symbols correspond to predetermined region shapes.

36. The method of claim 24 wherein computing the message symbols comprises estimating message symbols by mapping a value of the feature to one of a set of quantization bins, where the quantization bins are associated with predetermined message symbols.

37. The method of claim 33 including:

spread spectrum demodulating the estimated message symbols to produce a spread spectrum demodulated message signal.

38. The method of claim 37 including error correction decoding the spread spectrum demodulated message signal.

39. The method of claim 33 including error correction decoding the estimated message symbols to produce an error corrected message.

40. A computer readable medium on which is stored software for performing the method of claim 24.

41. A method of embedding a digital watermark into a media signal comprising:

segmenting the media signal into arbitrary shaped regions according to at least one signal characteristic of the media signal;

transforming media signal samples in the regions from one domain to another;

adapting the transformed samples in the regions according to a digital watermark definition to embed hidden auxiliary data in the media signal.

42. A computer readable medium on which is stored software for performing the method of claim 41.

43. A computer readable medium on which is stored an electronic media signal embedded with a digital watermark using the method of claim 41.

44. A physical object bearing an image which is embedded with a digital watermark using the method of claim 41.