Sparse modulation for robust signaling and synchronization

• US 9,635,378 B2
• Filed: 05/29/2015
• Issued: 04/25/2017
• Est. Priority Date: 03/20/2015
• Status: Active Grant

• Current Assignee: Digimarc Corporation
• Original Assignee: Digimarc Corporation
• Inventors: Holub, Vojtech, Haaga, Donald, Sharma, Ravi K.
• Primary Examiner(s): Lu, Tom Y
• Application Number:
  US14/725,399
• Publication Number:
  US 20160275639A1
• Time in Patent Office: 697 Days
• CPC Class Codes: G06T 1/0028 Adaptive watermarking, e.g. Human Visual System [HVS]-based watermarking
• CPC Class Codes: G06T 1/005 Robust watermarking, e.g. average attack or collusion attack resistant
• CPC Class Codes: G06T 2201/0051 Embedding of the watermark in the spatial 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/32 Circuits or arrangements for control or supervision between transmitter and receiver or between image input and image output device, e.g. between a still-image camera and its memory or between a still-image camera and a printer device H04N1/38, H04N1/387 take precedence
• 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/32224 Replacing pixels of an image with other pixels from the same image, e.g. texture block coding
• 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/32251 in multilevel data, e.g. greyscale or continuous tone data
• CPC Class Codes: H04N 1/32261 in binary data H04N1/32256 takes precedence
• CPC Class Codes: H04N 1/3232 Robust embedding or watermarking
• 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 19/124 Quantisation
• CPC Class Codes: H04N 19/467 characterised by the embedded information being invisible, e.g. watermarking
• CPC Class Codes: H04N 2201/3233 of authentication information, e.g. digital signature, watermark

Abstract

Sparse signal modulation schemes encode a data channel on a host image in a manner that is robust, flexible to achieve perceptual quality constraints, and provides improved data capacity. The host image is printed by any of a variety of means to apply the image, with sparse signal, to an object. After image capture of the object, a decoder processes the captured image to detect and extract data modulated into the sparse signal. The sparse signal may incorporate implicit or explicit synchronization components, which are either formed from the data signal or are complementary to it.

Claims

1. A method for inserting a sparse, variable data carrying signal into a digital image, the method comprising:

providing a first signal component, the first signal component facilitating a synchronization function of the sparse, variable data carrying signal, and comprising first signal component values at coordinates within a two-dimensional block;

providing a second signal component, the second signal component being modulated to carry a variable data signal, and comprising second signal component values at coordinates within the two-dimensional block;

combining the first signal component and the second signal component to produce the sparse, variable data carrying signal by setting sparse elements at coordinates within the two-dimensional block where the first signal component values and the second signal component values provide compatible modulation of the digital image; and

inserting the sparse, variable data carrying signal into at least a first digital image layer or a first digital image channel of the digital image.

2. The method of claim 1 wherein the compatible modulation comprises a consistent direction of modulation of an optical property at a coordinate within the two-dimensional block.

3. The method of claim 1 wherein the compatible modulation comprises modulation at a coordinate in which both a value of the first signal component and a value of the second signal component fall within a common range bounded by at least one threshold.

4. The method of claim 3 wherein the compatible modulation comprises modulation at a coordinate in which both the value of the first signal component and the value of the second signal component are quantized to a common quantization value.

5. The method of claim 1 in which the first signal component and second signal component are provided in or converted to a binary form, and wherein the compatible modulation is determined by applying a logical AND operation between binary values of the first signal component and the second signal component at a coordinate, and the compatible modulation corresponds to coordinates where the binary values of the first signal component and the second signal component agree.

6. The method of claim 5 wherein at least one of the first signal component or the second signal component is converted to a binary form by applying a threshold.

7. The method of claim 1 wherein at least one of the first signal component or the second signal component is a multi-valued signal, and is converted to a sparse signal component by applying at least a first threshold, and the combining comprises setting sparse elements at coordinates where the sparse signal component and a value of either of the first signal component or the second signal component are consistent.

8. The method of claim 7 wherein the first signal component is a multi-valued signal component.

9. The method of claim 8 wherein the multi-valued signal component represents a synchronization template formed by a set of peaks in a transform domain.

29. The method of claim 1, in which prior to said inserting, said method comprises reducing the sparse, variable data carrying signal with a line screen.

10. A method for inserting a sparse, variable data carrying signal into an image, the method comprising:

providing a first orthogonal signal component, the first orthogonal signal component comprising first signal component values at coordinates within a two-dimensional area;

providing a second orthogonal signal component, the second orthogonal signal component being modulated to carry a variable data carrying signal, and comprising second signal component values at coordinates within the two-dimensional area;

combining the first orthogonal signal component and the second orthogonal signal component to produce the sparse, variable data carrying signal by selecting a subset of the first signal component values and the second signal component values, the selected subset of the first signal component values and the second signal component values comprising less signal component values than the second signal component values; and

inserting the sparse, variable data carrying signal into at least a first image layer or first image channel of the image.

11. The method of claim 10 including quantizing the first orthogonal signal component and the second orthogonal signal component to produce first and second sparse signal components, and merging the first and second sparse signal components.

12. The method of claim 11 wherein the quantizing comprises applying at least a first threshold to remove signal from the first orthogonal signal component or the second orthogonal signal component.

13. The method of claim 10 including combining the first orthogonal signal component and the second orthogonal signal component, and quantizing the combined first orthogonal signal component and the second orthogonal signal component to produce the sparse, variable data carrying signal.

14. The method of claim 10 wherein the first orthogonal signal component being formed to facilitate synchronization of the sparse, variable data carrying signal.

15. A method for inserting a sparse, variable data carrying signal into an image, the method comprising:

providing a sparse pattern of elements at coordinates within a two-dimensional area;

providing a signal component, the signal component being modulated to carry a variable data signal;

generating the sparse, variable data carrying signal by distributing the signal component within the two-dimensional area based on the location of the sparse pattern of elements; and

inserting the sparse, variable data carrying signal into at least a first image layer or a first image channel of the image.

16. The method of claim 15 wherein the signal component is converted to a sparse, variable data carrying signal by removing signal elements of the signal component at coordinates where the signal component does not coincide with coordinates of the sparse pattern of elements.

17. The method of claim 15 wherein the two-dimensional area comprises a two-dimensional block, and wherein the signal component is repeated in two-dimensional blocks within the image, and different sparse patterns are used to distribute the signal component in plural of two-dimensional blocks.

30. The method of claim 15 in which prior to said inserting, said method comprises reducing the sparse, variable data carrying signal with a line screen.

18. A system for inserting a sparse, variable data carrying signal into a digital image, said system comprising:

memory for storing data representing the digital image; and

one or more processors programmed for;

providing a first signal component, the first signal component facilitating a synchronization function of the sparse, variable data carrying signal, and comprising first signal component values at coordinates within a two-dimensional area;

providing a second signal component, the second signal component being modulated to carry a variable data signal, and comprising second signal component values at coordinates within the two-dimensional area;

combining the first signal component and the second signal component to produce the sparse, variable data carrying signal by setting sparse elements at coordinates within the two-dimensional area where the first signal component values and the second signal component values provide compatible modulation of the digital image; and

inserting the sparse, variable data carrying signal into at least a first digital image layer or a first digital image channel of the digital image.

19. The system of claim 18 wherein the compatible modulation comprises a consistent direction of modulation of an optical property at a coordinate within the two-dimensional block.

20. The system of claim 18 wherein the compatible modulation comprises modulation at a coordinate in which both the value of the first signal component and the second signal component fall within a common range bounded by at least one threshold.

21. The system of claim 20 wherein the compatible modulation comprises modulation at a coordinate in which both the value of the first signal component and the value of the second signal component are quantized to a common quantization value.

22. The system of claim 18 wherein at least one of the first signal component or the second signal component is a multi-valued signal, and is converted to a sparse signal component by applying at least a first threshold, and the combining comprises setting sparse elements at coordinates where the sparse signal component and a value of either of the first signal component or the second signal component are consistent.

28. The system of claim 18 in which said one or more processors each comprises two or more processing cores.

23. An apparatus for inserting a sparse, variable data carrying signal into a digital image, said apparatus comprising:

memory for storing data representing the digital image, the data including a representation of a first digital image layer or a first digital image channel;

means for providing a first orthogonal signal component, the first orthogonal signal component comprising first signal component values at coordinates within a two-dimensional block;

means for providing a second orthogonal signal component, the second orthogonal signal component being modulated to carry a variable data carrying signal, and comprising second signal component values at coordinates within the two-dimensional block;

means for combining the first orthogonal signal component and the second orthogonal signal component to produce the sparse, variable data carrying signal by selecting a subset of the first signal component values and the second signal component values, in which the selected subset of the first signal component values and the second signal component values comprises less signal component values than the second signal component values; and

means for inserting the sparse, variable data carrying signal into at least the first digital image layer or the first digital image channel.

24. The apparatus of claim 23 including means for quantizing the first orthogonal signal component and the second orthogonal signal component to produce first and second sparse signal components, and means for merging the first and second sparse signal components.

25. The apparatus of claim 24 wherein the quantizing comprises applying at least a first threshold to remove signal from the first orthogonal signal component or the second orthogonal signal component.

26. The apparatus of claim 23 including means for combining the first orthogonal signal component and the second orthogonal signal component, and means for quantizing the combined first orthogonal signal component and the second orthogonal signal component to produce the sparse, variable data carrying signal.

27. The apparatus of claim 23 wherein the first orthogonal signal component being formed to facilitate synchronization of the sparse, variable data carrying signal.

31. An apparatus for inserting a sparse, variable data carrying signal into a digital image, said apparatus comprising:

memory for storing data representing the digital image;

means for providing a sparse pattern of elements at coordinates within a two-dimensional area;

means for providing a signal component, the signal component being modulated to carry a variable data signal;

means for generating the sparse, variable data carrying signal by distributing the signal component within the two-dimensional area based on the location of the sparse pattern of elements;

means for inserting the sparse, variable data carrying signal into at least a first image layer or a first image channel of the digital image, said means for inserting yielding a transformed digital image; and

a display for displaying the transformed digital image.

32. The apparatus of claim 31 further comprising means for removing signal elements of the signal component at coordinates where the signal component does not coincide with coordinates of the sparse pattern.

33. The apparatus of claim 31 wherein the two-dimensional area comprises a two-dimensional block, and wherein the apparatus further comprises means for repeating the signal component in two-dimensional blocks within the digital image, with different sparse patterns being used to distribute the signal component in plural of two-dimensional blocks.

34. The apparatus of claim 31 further comprising means for reducing the sparse, variable data carrying signal with a line screen.