Signal processors and methods for estimating transformations between signals with least squares

Patent metadata

Field	Value
Publication number	US-9953390-B2
Application number	US-201514936359-A
Country	US
Kind code	B2
Filing date	Nov 9, 2015
Priority date	Sep 3, 2010
Publication date	Apr 24, 2018
Grant date	Apr 24, 2018

Abstract

Signal processing devices and methods estimate transforms between signals using a least squares technique. From a seed set of transform candidates, a direct least squares method applies a seed transform candidate to a reference signal and then measures correlation between the transformed reference signal and a suspect signal. For each candidate, update coordinates of reference signal features are identified in the suspect signal and provided as input to a least squares method to compute an update to the transform candidate. The method iterates so long as the update of the transform provides a better correlation. At the end of the process, the method identifies a transform or set of top transforms based on a further analysis of correlation, as well as other results.

First claim

We claim:

1. A method of determining a geometric transformation of an image, the method comprising:
receiving an electronic image sampled from a physical object;
with one or more processors:
providing a seed set of candidate geometric transform parameters, the seed set being distributed over a space of candidate geometric transform parameters;
for each of the candidate geometric transform parameters, transforming coordinates of a digital watermark signal with the candidate geometric transform parameters to produce a transformed watermark signal at transformed watermark signal coordinates;
determining a measure of correlation between the transformed watermark signal and the electronic image, for each of the candidate geometric transform parameters;
selecting a subset of the candidate geometric transform parameters based on the measure of correlation;
for a selected candidate geometric transform parameter of the subset, determining peak locations within the electronic image that are within neighborhoods around the transformed watermark signal coordinates;
updating locations of the transformed watermark signal coordinates to the peak locations;
determining a geometric transform that maps the digital watermark signal to the updated locations;
determining correlation between the electronic image signal and the digital watermark signal, transformed by the geometric transform; and
refining the geometric transform by determining peak locations within the electronic image that are within a neighborhood of corresponding transformed watermark signal coordinates, updating locations of the transformed watermark signal coordinates to the peak locations, determining a new geometric transform that maps the digital watermark signal to the updated locations, and determining whether correlation has increased between the electronic image signal and the digital watermark signal, transformed by the new geometric transform.

2. The method of claim 1 wherein the candidate geometric transform parameters comprises two or more affine transform parameters.

3. The method of claim 2 wherein the two or more affine transform parameters comprise rotation, differential scale and shear.

4. The method of claim 1 wherein the digital watermark signal comprises peaks at the coordinates of the digital watermark signal.

5. The method of claim 1 wherein the seed set comprises a seed set of linear transform candidates.

6. The method of claim 5 wherein the linear transform candidates comprise rotation and scale candidates.

7. The method of claim 1 further comprising:
estimating phase of the digital watermark signal, when transformed by the geometric transform, by sampling phase from neighboring image samples at integer locations within the electronic image signal, and using the phase estimates of the digital watermark signal to assess whether the geometric transform improves correlation between the electronic image and the digital watermark signal, as transformed by the geometric transform.

8. A digital watermark detector comprising:
a memory for storing an electronic image sampled from a physical object;
a processor in communication with the memory, the processor configured to measure correlation between the electronic image and a digital watermark signal, transformed by sets of candidate affine transform parameters, the sets including a seed set of transform parameters, the seed set being distributed over a space of candidate affine transform parameters;
the processor further configured to select a set of affine transform parameters based on the measure of correlation, apply the selected set to the digital watermark signal to produce transformed digital watermark signal coordinates, determine peak locations around the transformed watermark signal coordinates, determine a geometric transform between the digital watermark signal coordinates and the peak locations, and measure correlation between the electronic image and the digital watermark signal, as transformed by the geometric transform.

9. The digital watermark detector of claim 8 wherein the candidate affine transform parameters comprise rotation, differential scale, and shear.

10. The digital watermark detector of claim 8 wherein the digital watermark signal comprises peaks at the coordinates of the digital watermark signal.

11. The digital watermark detector of claim 8 wherein the seed set comprises a seed set of linear transform candidates.

12. The digital watermark detector of claim 11 wherein the linear transform candidates comprises rotation and scale candidates.

13. The digital watermark detector of claim 8 wherein the processor is configured to estimate phase of the digital watermark signal, when transformed by the geometric transform, by sampling phase from neighboring image samples at integer locations within the electronic image signal, and using the phase estimates of the digital watermark signal to assess whether the geometric transform improves correlation between the electronic image and the digital watermark signal, as transformed by the geometric transform.

14. A non-transitory, computer readable medium on which is stored instructions, which, when executed by a processor, preform a method of determining a geometric transformation of an image, the method comprising:
obtaining an electronic image sampled from a physical object; providing a seed set of candidate geometric transform parameters, the seed set being distributed over a space of candidate geometric transform parameters;
for each of the candidate geometric transform parameters, transforming coordinates of a digital watermark signal with the candidate geometric transform parameters to produce a transformed watermark signal at transformed watermark signal coordinates;
determining a measure of correlation between the transformed watermark signal and the electronic image, for each of the candidate geometric transform parameters;
selecting a subset of the candidate geometric transform parameters based on the measure of correlation;
for a selected candidate geometric transform parameter of the subset, determining peak locations within the electronic image that are within neighborhoods around the transformed watermark signal coordinates;
updating locations of the transformed watermark signal coordinates to the peak locations;
determining a geometric transform that maps the digital watermark signal to the updated locations;
determining correlation between the electronic image signal and the digital watermark signal, transformed by the geometric transform; and
refining the geometric transform by determining peak locations within the electronic image that are within a neighborhood of corresponding transformed watermark signal coordinates, updating locations of the transformed watermark signal coordinates to the peak locations, determining a new geometric transform that maps the digital watermark signal to the updated locations, and determining whether correlation has increased between the electronic image signal and the digital watermark signal, transformed by the new geometric transform.

15. The computer readable medium of claim 14 wherein the candidate geometric transform parameters comprises two or more affine transform parameters.

16. The computer readable medium of claim 15 wherein the two or more affine transform parameters comprise rotation, differential scale and shear.

17. The computer readable medium of claim 14 wherein the digital watermark signal comprises peaks at the coordinates of the digital watermark signal.

18. The computer reada

Assignees

• Digimarc Corp

Inventors

• Sharma Ravi K
• Lord John D
• Lyons Robert G

Classifications

• G06V10/754

  involving a deformation of the sample pattern or of the reference pattern; Elastic matching · CPC title

• G06F1/02

  Digital function generators · CPC title

• G06T1/0021

  Image watermarking · CPC title

• G06T1/0064 Primary

  Geometric transfor invariant watermarking, e.g. affine transform invariant · CPC title

• G06K9/6206

  Physics · mapped topic