Method and apparatus for robust information coding

• US 5,748,783 A
• Filed: 05/08/1995
• Issued: 05/05/1998
• Est. Priority Date: 05/08/1995
• Status: Expired due to Term

• Current Assignee: Digimarc Corporation
• Original Assignee: Digimarc Corporation
• Inventors: Rhoads, Geoffrey B.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Werner, Brian P.
• Application Number:
  US08/436,102
• Time in Patent Office: 1,093 Days
• Field of Search: 396/315, 396/316, 283/17, 283/72, 283/88, 283/89, 283/93, 283/97, 283/113, 283/901, 283/902, 382/287, 382/280, 382/232, 380/51, 380/58, 380/3-5, 380/54, 380/55, 356/71, 356/432, 427/7, 235/468, 235/469, 235/494, 250/271, 250/336.1, 250/566, 250/568, 355/79, 399/156, 162/110
• US Class Current: 382/232
• CPC Class Codes: B42D 25/00 Information-bearing cards or sheet-like structures characterised by identification or security features; Manufacture thereof printing processes to produce identification or security features B41M3/14
• CPC Class Codes: B42D 25/23 Identity cards
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]
• CPC Class Codes: G06K 19/06037 multi-dimensional coding
• CPC Class Codes: G06K 19/06046 Constructional details
• CPC Class Codes: G06K 19/14 the marking being sensed by radiation
• CPC Class Codes: G06K 19/18 Constructional details
• CPC Class Codes: G06K 2019/06253 for a specific application
• CPC Class Codes: G06K 7/1417 2D bar codes
• CPC Class Codes: G06K 7/1447 extracting optical codes from image or text carrying said optical code
• 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: G06Q 20/40145 Biometric identity checks
• CPC Class Codes: G06T 1/0064 Geometric transfor invariant watermarking, e.g. affine transform invariant
• CPC Class Codes: G06T 2201/0052 Embedding of the watermark in the frequency domain
• CPC Class Codes: G06T 2201/0601 whereby calibration information is embedded in the watermark, e.g. a grid, a scale, a list of transformations
• CPC Class Codes: G07C 9/253 visually
• CPC Class Codes: G07D 7/0034 using watermarks
• CPC Class Codes: G07D 7/004 using digital security elements, e.g. information coded on a magnetic thread or strip
• CPC Class Codes: G07F 17/26 for printing, stamping, franking, typing or teleprinting apparatus ticket printing or the like apparatus G07F17/42
• CPC Class Codes: G10L 19/018 Audio watermarking, i.e. embedding inaudible data in the audio signal
• CPC Class Codes: G11B 20/00884 : involving a watermark, i.e. a barely perceptible transformation of the original data which can nevertheless be recognised by an algorithm
• CPC Class Codes: G11B 20/00891 : embedded in audio data
• CPC Class Codes: H04N 1/00005 : relating to image data
• CPC Class Codes: H04N 1/00037 : Detecting, i.e. determining the occurrence of a predetermined state H04N1/00031 takes precedence
• CPC Class Codes: H04N 1/00079 : remotely
• CPC Class Codes: H04N 1/32149 : Methods relating to embedding, encoding, decoding, detection or retrieval operations
• CPC Class Codes: H04N 1/3216 : using Fourier transforms
• 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/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/32352 : Controlling detectability or arrangements to facilitate detection or retrieval of the embedded information, e.g. using markers for decoding, detection or retrieval operations H04N1/32149 and subgroups take precedence
• CPC Class Codes: H04N 2201/3205 : of identification information, e.g. name or ID code H04N2201/3209 takes precedence
• CPC Class Codes: H04N 2201/3225 : of data relating to an image, a page or a document
• CPC Class Codes: H04N 2201/3226 : of identification information or the like, e.g. ID code, index, title, part of an image, reduced-size image
• 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
• CPC Class Codes: H04N 2201/3271 : Printing or stamping
• CPC Class Codes: H04N 2201/3274 : Storage or retrieval of prestored additional information
• CPC Class Codes: Y10S 283/901 : Concealed data

Abstract

A digital signal is imperceptibly embedded into an input source signal, such as an image or video signal, to produce an encoded (sometimes termed "watermarked") signal. The principle of quasi-rotational symmetry is employed to facilitate detection of the embedded signal notwithstanding rotation of the encoded signal. Single or multiple degrees of symmetry can be employed. In another aspect, the digital signal is transformed to a frequency domain and phase-only filtered prior to its combination with the input source signal. In an illustrative embodiment, this filtering operation helps hide the digital signal within the source signal, and facilitates detection of the embedded digital signal even after the encoded signal has undergone various forms of corruption.

Claims

1. In a method of steganographically processing an image signal to embed multi-bit information therein, an improvement comprising representing said information in the form of a plurality of partially overlapping quasi-rotationally symmetric patterns, and processing the image signal to imperceptibly enabled said plurality of partially overlapping quasi-rotationally symmetric patterns therein, wherein said quasi-rotational symmetry of the patterns facilitates detection of the multi-bit information from a resulting processed image signal if said processed image signal is corrupted by scaling or rotation operations.

2. The method of claim 1 in which each of said quasi-rotationally symmetric patterns encodes a single bit of information.

3. The method of claim 1 in which said plurality of quasi-rotationally symmetric patterns comprises at least four patterns, and centers of said plurality of patterns lie on a circle, thereby forming a rosette of patterns.

4. The method of claim 3 which includes processing the image signal to encode a plurality of said rosettes therein, wherein the rosettes are spaced across a representation of the image signal in a pixel domain so that a pattern of one rosette overlaps a pattern of another rosette.

5. The method of claim 4 in which patterns of one rosette overlap patterns of six other rosettes.

6. The method of claim 3 which includes providing at least one pattern in said rosette with a distinguishing feature to aid in distinguishing it from other pattern in said rosette during decoding.

7. The method of claim 1 which includes pre-processing the plurality of patterns prior to encoding the image signal therewith, said pre-processing including performing a fourier transform on said plurality of patterns to produce transformed data, and applying a filtering function to said transformed data.

8. The method of claim 7 in which the filtering function is rotationally symmetric within a spatial frequency domain.

9. The method of claim 7 in which the filtering function is phase-only.

10. The method of claim 1, further comprising storing the processed image signal on a physical medium.

11. The method of claim 10, wherein the physical medium comprises paper.

12. The method of claim 10, wherein the physical medium comprises a magnetic or electronic storage medium.

13. The method of claim 1 in which said patterns are wave patterns.

14. The method of claim 1 in which said quasi-rotationally symmetric patterns exhibit symmetry about more than one axis.

15. The method of claim 1 in which said quasi-rotationally symmetric patterns exhibit symmetry about more than two axes.

16. The method of claim 1 in which said image signal is represented as pixel data in a spatial image domain.

17. The method of claim 16 in which said processing includes adding a bit-mapped representation of said patterns to said pixel data.

18. The method of claim 1 in which the patterns exhibit said quasi-rotational symmetry when represented as pixel data in a spatial image domain.

19. The method of claim 1 in which the quasi-rotational symmetry of the patterns facilitates detection of the multi-bit information from the processed image signal if the processed image signal is corrupted by a rotation operation.

20. The method of claim 1 in which the quasi-rotational symmetry of the patterns facilitates detection of the multi-bit information from the processed image signal if the processed image signal is corrupted by a scaling operation.

21. The method of claim 1 in which the quasi-rotational symmetry of the patterns facilitates detection of the multi-bit information from the processed image signal by enabling re-registration of a corrupted, processed image signal by reference to said patterns.

22. A computer storage medium having instructions stored therein for causing a computer to perform the method of claim 1.

23. In a computer-implemented method of producing a steganographically encoded signal, the method including storing a representation of an input signal in a memory, and combining a multi-bit data signal with said input signal, the method being practiced using a programmed processor in conjunction with said memory, an improvement comprising:

transforming the multi-bit data signal to produce a transformed signal in a complementary frequency domain;

applying a phase-only filtering function to the transformed signal to produce a filtered signal; and

combining the filtered signal with the representation of the input signal to effect steganographic encoding thereof, wherein the multi-bit data signal is hidden within the first signal without commercially impairing the value thereof.

24. The method of claim 23 in which the input signal is a set of image data represented as pixel data in a spatial image domain, and in which the multi-bit data signal comprises data corresponding to a plurality of quasi-rotationally symmetric patterns.

25. The method of claim 23 in which the combining step comprises adding the filtered signal to the representation of the input signal.

26. The method of claim 23 which includes representing the filtered signal as a group of pixels prior to combining same with the representation of the input signal.

27. A computer storage medium having instructions stored therein for causing said computer to perform the method of claim 23.