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

Patent metadata

Field	Value
Publication number	US-11410262-B2
Application number	US-201916557929-A
Country	US
Kind code	B2
Filing date	Aug 30, 2019
Priority date	Sep 3, 2010
Publication date	Aug 9, 2022
Grant date	Aug 9, 2022

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 signal processing to estimate a geometric transformation between a reference signal, and a depiction of said reference signal in imagery of an object captured by a camera from a capture point, the reference signal comprising plural signal components, each signal component having a coordinate location in a Fourier plane and a phase, the geometric transformation including scale, rotation and translation, the method comprising the acts:
receiving the imagery in a memory;
with a processor, performing the acts of:
performing a domain transformation on the imagery of the object captured by the camera, to yield image data at a plurality of coordinate locations in the Fourier plane;
producing first and second linear transform estimates, each estimate including parameters estimating scale and rotation of said geometrical transformation;
applying the first linear transform estimate to the reference signal to produce a first transformed reference signal, the first transformed reference signal including first-transformed components at first-transformed coordinate locations;
processing the image data to produce estimated phases of the depiction of the reference signal at said first-transformed coordinate locations;
for each of several translation offsets, each corresponding to expected phases of the reference signal components, generating a first phase deviation metric by summing phase deviation at each of said first-transformed coordinate locations between (i) said expected phase of the first transformed reference signal component at said first-transformed coordinate location and (ii) said estimated phase of the image data at said first-transformed coordinate location, and identifying a translation offset that produces a minimum first phase deviation metric;
applying the second linear transform estimate to the reference signal to produce a second transformed reference signal, the second transformed reference signal including second-transformed components at second-transformed coordinate locations;
processing the image data to produce estimated phases of the depiction of the reference signal at said second-transformed coordinate locations;
for each of several translation offsets, each corresponding to expected phases of the reference signal components, generating a second phase deviation metric by summing phase deviation at each of said second-transformed coordinate locations between (i) said expected phase of the second transformed reference signal component at said second-transformed coordinate location and (ii) said estimated phase of the image data at said second-transformed coordinate location, and identifying a translation offset that produces a minimum second phase deviation metric;
selecting one of said first and second linear transform estimates as a better estimate of said geometrical transformation based on values of said minimum first phase deviation metric and said minimum second phase deviation metric; and
determining whether the reference signal is present in the imagery based on the selected better estimate of said geometrical transformation.

2. The method of claim 1 that includes refining the selected one of said linear transform estimates to include parameters corresponding to the selected translation offset of the selected one of said first and second linear transform estimates.

3. The method of claim 1 in which said domain transformation produces image phase data at each of plural integer locations in the Fourier plane, and one of said first-transformed reference signal components has a first-transformed coordinate location between four of said integer locations in the Fourier plane, wherein the method includes applying a point spread function to the image phase data from said four integer locations to produce the estimated phase of the depiction of the reference signal at said first-transformed coordinate location.

4. The method of claim 1 in which said translation offsets are integer translation offsets.

5. The method of claim 1 in which said translation offsets are smaller than integer translation offsets.

6. The method of claim 1 that includes producing the first and second linear transform estimates by correlating the reference signal with depiction of the reference signal in the imagery, in a log polar coordinate space.

7. The method of claim 1 that includes producing the first and second linear transform estimates by a matched filter correlation operation between image data corresponding to the imagery captured by the camera, and the reference signal.

8. The method of claim 1 that includes producing the first and second linear transform estimates by a least squares method.

9. The method of claim 1 that includes producing the first and second linear transform estimates by refining previous first and second linear transform estimates.

10. The method of claim 1 that includes producing N linear transform estimates, each characterized by a rotation and a scale value, wherein said N estimates span a sparse subspace of rotation and scale values, and wherein said first and second linear transform estimates are among said N linear transform estimates.

11. The method of claim 1 that includes:
producing N linear transform estimates, each characterized by a rotation and a scale value, wherein said N estimates span a sparse subspace of rotation and scale values; and
iteratively refining said N linear transform estimates;
wherein more iterations are performed for linear transform estimates that exhibit convergence; and
wherein said first and second linear transform estimates result from said iterative refining.

12. A method of computing an estimate of a geometric transformation between a reference signal, and a depiction of said reference signal in imagery of an object captured by a camera from a capture point, the reference signal comprising plural signal components, each signal component having a coordinate location in a Fourier plane and a phase, the geometric transformation including scale, rotation and translation, the method comprising the acts:
receiving the imagery in a memory;
with a processor, performing the acts of:
performing a domain transformation on the imagery of the object captured by the camera, to yield image data at a plurality of coordinate locations in the Fourier plane;
producing plural linear transform estimates, each estimate including scale and rotation parameters of said geometrical transformation;
for each of said plural linear transform estimates:
(a) applying the linear transform estimate to the reference signal to produce a transformed reference signal, the transformed reference signal including transformed components at transformed coordinate locations;
(b) processing the image data to produce estimated phases of the depiction of the reference signal at said transformed coordinate locations;
(c) for each of several translation offsets, each corresponding to expected phases of the reference signal components, generating a phase deviation metric by summing phase deviation at each of said transformed coordinate locations between (i) said expected phase of the transformed reference signal component at said transformed coordinate location and (ii) said estimated phase of the image data at said transformed coordinate location, and identifying a translation offset that produces a minimum phase deviation metric;
outputting an estimate of said geometrical transformation based on values of said minimum phase deviation metrics; and
determining that the reference signal is present in the imagery using the estimate of said geometrical transformation.

13. A non-transitory computer re

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

• G06T1/0064 Primary

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

• G06T1/0021

  Image watermarking · CPC title

• G06F1/02

  Digital function generators · CPC title

• G06T3/0006

  Physics · mapped topic