Method for encoding auxiliary data within a source signal

• US 5,809,160 A
• Filed: 11/12/1997
• Issued: 09/15/1998
• Est. Priority Date: 07/31/1992
• Status: Expired due to Term

• Current Assignee: Digimarc Corporation
• Original Assignee: Digimarc Corporation
• Inventors: Powell, Robert D., Nitzberg, Mark J.
• Primary Examiner(s): Johns, Andrew W.
• Application Number:
  US08/969,072
• Time in Patent Office: 307 Days
• Field of Search: 382/100, 382/112, 382/232, 340/825.34, 356/71, 902/1, 902/4, 902/6, 283/17, 283/72, 283/73, 283/113, 283/901, 380/9, 380/23, 380/25, 380/54
• US Class Current: 382/100
• CPC Class Codes: G06Q 20/341 Active cards, i.e. cards including their own processing means, e.g. including an IC or chip
• CPC Class Codes: G06T 1/0028 Adaptive watermarking, e.g. Human Visual System [HVS]-based watermarking
• CPC Class Codes: G06T 1/0064 Geometric transfor invariant watermarking, e.g. affine transform invariant
• CPC Class Codes: G06T 2201/0051 Embedding of the watermark in the spatial domain
• CPC Class Codes: G06T 2201/0081 whereby both original and watermarked images are required at decoder, e.g. destination-based, non-blind, non-oblivious
• CPC Class Codes: G07D 7/0047 using checkcodes, e.g. coded numbers derived from serial number and denomination
• CPC Class Codes: G07D 7/0056 involving markings of altered colours
• CPC Class Codes: G07D 7/12 Visible light, infrared or ultraviolet radiation
• CPC Class Codes: G07D 7/2008 using pre-processing, e.g. de-blurring, averaging, normalisation or rotation
• CPC Class Codes: G07D 7/2033 Matching unique patterns, i.e. patterns that are unique to each individual paper
• CPC Class Codes: G07F 7/08 by coded identity card or credit card or other personal identification means without personal verification means G07F7/02
• CPC Class Codes: G07F 7/12 Card verification
• CPC Class Codes: H04N 1/32203 Spatial or amplitude domain methods H04N1/32309 takes precedence
• CPC Class Codes: H04N 1/32208 involving changing the magnitude of selected pixels, e.g. overlay of information or super-imposition H04N1/32219, H04N1/32224 take precedence
• 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/32245 Random or pseudorandom selection of pixels
• CPC Class Codes: H04N 1/32251 in multilevel data, e.g. greyscale or continuous tone data
• CPC Class Codes: H04N 1/32288 Multiple embedding, e.g. cocktail embedding, or redundant embedding, e.g. repeating the additional information at a plurality of locations in the image
• CPC Class Codes: H04N 1/3232 Robust embedding or watermarking
• CPC Class Codes: H04N 2201/3233 of authentication information, e.g. digital signature, watermark
• CPC Class Codes: H04N 2201/3235 : Checking or certification of the authentication information, e.g. by comparison with data stored independently
• CPC Class Codes: H04N 2201/327 : which are undetectable to the naked eye, e.g. embedded codes

Abstract

A method and system for embedding signatures within visual images in both digital representation and print or film. A signature is inseparably embedded within the visible image, the signature persisting through image transforms that include resizing as well as conversion to print or film and back to digital form. Signature points are selected from among the pixels of an original image. The pixel values of the signature points and surrounding pixels are adjusted by an amount detectable by a digital scanner. The adjusted signature points form a digital signature which is stored for future identification of subject images derived from the image. In one embodiment, a signature is embedded within an image by locating relative extrema in the continuous space of pixel values and selecting the signature points from among the extrema. Preferably, the signature is redundantly embedded in the image such that any of the redundant representations can be used to identify the signature. Identification of a subject image includes ensuring that the subject image is normalized with respect to the original image or the signed image. Preferably, the normalized subject image is compared with the stored digital signature.

Claims

1. A method of encoding N-bits of auxiliary data within a source signal, N being at least one, the source signal being comprised of samples, each having a binary value, the method including:

increasing the values of certain source signal samples;

decreasing the values of other source signal samples;

the foregoing steps changing the values of more than N samples, wherein redundant encoding of at least part of said auxiliary data is effected.

2. The method of claim 1, wherein the source signal represents image data, and said increasing and decreasing is slight enough to make said changes inconspicuous.

3. The method of claim 1 wherein the source signal represents still image data.

4. The method of claim 1 in which N is at least two.

5. The method of claim 1 which includes increasing values of source signal samples adjoining the certain source signal samples whose values are increased, and decreasing values of source signal samples adjoining the certain source signal samples whose values are decreased.

6. The method of claim 5 in which the values of the adjoining source signal samples are changed in value less than the certain source signal samples adjacent thereto.

7. The method of claim 1 including identifying portions of the source signal having a predetermined data hiding attribute, and selecting said certain source signal samples from the identified portions.

8. A method of encoding N-bits of auxiliary data within a source signal, N being at least one, the source signal being comprised of samples, each having a binary value, the method including, for each bit of the auxiliary data:

mapping said bit to at least one sample of the source signal;

changing the value of said source signal sample in accordance with the bit of the auxiliary data; and

also changing the values of at least two adjoining source signal samples in accordance with said bit of the auxiliary data;

wherein changes to the source signal are effected in groups of samples, yielding a more robust encoding that better withstands corruption of the encoded source signal.

9. The method of claim 8 which includes mapping by a random function.

10. The method of claim 8 in which the mapping includes identifying portions of the source signal having a predetermined data hiding attribute, and selecting from said identified portions.

11. The method of claim 10 in which the predetermined data hiding attribute is an area of relative maxima or minima.

12. The method of claim 8, wherein the mapping comprises mapping said bit to plural samples of the source signal.

13. The method of claim 8 in which the sample to which the bit is mapped is a first sample, and the changes to said adjoining source signal samples are smaller than the change to said first sample.

14. The method of claim 8, further including changing the value of said source signal sample in accordance with another factor not related to the bit of the auxiliary data.

15. In a method of encoding N-bits of auxiliary data within a source signal, N being at least one, the source signal being comprised of samples, each having a binary value, the method including--for each bit of the auxiliary data--changing the value of a source signal sample in accordance therewith, an improvement comprising employing a random function to randomize the locations within the source signal at which said bits of auxiliary data change said values of the source signal samples.

16. The method of claim 15 in which the source signal represents image data.

17. A method of encoding N-bits of auxiliary data within a source signal, N being at least one, the source signal representing image data, the method including:

evaluating data hiding characteristics of plural locations in the source signal; and

encoding the auxiliary data in the source signal, avoiding the locations that have poor data hiding characteristics;

wherein the auxiliary data is encoded where it is relatively less perceptible.

18. A method of encoding N-bits of auxiliary data within a source signal, N being at least one, the source signal representing image data, the method including:

identifying portions of the source signal having a predetermined data hiding attribute; and

changing the source signal in at least certain of said portions to effect encoding of the auxiliary data therein;

wherein the auxiliary data is encoded where it is relatively less perceptible.

19. A method of encoding N-bits of auxiliary data within a source signal, N being at least two, the source signal representing an image and including plural pixels,

pseudo-randomly identifying plural signature point pixels within the image;

for a selected first group of said signature point pixels, increasing values of said pixels, and pixels in a region associated therewith; and

for a second group of said signature point pixels, distinct from the first, decreasing values of said pixels, and pixels in a region associated therewith;

wherein said selected increasing and decreasing of pixel values at said signature points and in the regions associated therewith serves to mark the image for later identification.

20. The method of claim 19 in which each of said regions comprises pixels contiguous with the signature point pixel.

21. The method of claim 19 which includes:

assigning each of said N-bits to at least one of said pseudo-randomly identified signature points;

defining one of said first or second groups of pixels as those to which a "1" bit of auxiliary data is assigned; and

defining the other of said first or second groups of pixels as those to which a "0" bit of auxiliary data is assigned.

22. In a method of marking an image to encode auxiliary data therein, the method including changing the image at plural points thereof, an improvement comprising defining a bounding area within which certain changes to the image are to be confined, said bounding area being less than the entirety of the image, and only making said certain changes within said area.

23. The method of claim 22 where the bounding area is rectangular in shape.

24. The method of claim 22 in which each of said changes is made at a predetermined point, and the method includes changing the image at first and second points adjoining at least certain of said predetermined points in accordance with the change to the adjoining predetermined point.

25. The method of claim 24 which includes changing image luminance at said predetermined points, and changing the luminance at each of said first and second points by an amount less than the luminance change to the adjoining predetermined point.

26. The method of claim 22 including identifying portions of the image having a predetermined data hiding attribute, and making said certain changes only in portions identified as having said predetermined data hiding attribute.

27. In a method of marking an image to encode auxiliary data therein, the method including changing the image at plural points thereof, an improvement wherein the image is comprised of pixels, and the method includes randomly selecting pixels where changes are to be made.

28. The method of claim 27 which includes both changing values of said randomly selected pixels, and increasing or decreasing the value of each pixel adjoining said randomly selected pixels, depending on whether the change to each selected pixel was an increase or a decrease.

29. The method of claim 28 in which the values of pixels adjoining each randomly selected pixel are increased or decreased by an amount less than the value the randomly selected pixel is changed.

30. The method of claim 27 including defining a bounding area within which changes to the image are to be confined, said bounding area being less than the entirety of the image, and only changing the image within said bounding area.

31. The method of claim 27 including identifying portions of the image having a predetermined data hiding attribute, and selecting said randomly selected pixels from said identified portions.

32. In a method of marking an image to encode auxiliary data therein, the method including changing the image at plural points thereof, an improvement wherein the image is comprised of pixels, the changes increase or decrease a value of a signature pixel at each said point, and the method further includes increasing or decreasing the value of each pixel adjoining said signature pixels to correspond to the change of the signature pixel adjacent thereto.

33. The method of claim 32 in which the changing includes increasing or decreasing the value of each signature pixel in accordance with the value of a corresponding bit of said auxiliary data.

34. A method of marking an image to encode auxiliary data therein, said data facilitating later identification of said image, the method comprising:

randomly selecting plural signature points in the image;

increasing a value of the image at a first subset of said randomly selected signature points, and at points surrounding said randomly selected signature points;

decreasing a value of the image at a second subset of said randomly selected signature points, and at points surrounding said randomly selected signature points.

35. A method of decoding a suspect image to determine whether it was marked in accordance with the method of claim 34, comprising:

determining the value of the suspect image at a first of said signature points;

subtracting from said value a second value to yield a difference;

repeating the foregoing steps for others of the signature points in the image and other second values to yield plural differences; and

assessing said plural differences to indicate whether the image was marked.

36. The method of claim 35 in which each second value is an original value of said image at said signature point, prior to performing the marking method of claim 34.

37. The method of claim 34 which includes increasing and decreasing each of said values by less than 10 percent.

38. The method of claim 34 which includes increasing and decreasing said values in accordance with bits of said auxiliary data.