Patent US5949055A successfully refreshed from Google Patents.
US5949055A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Automatic geometric image transformations using embedded signals
Assignee: Xerox Corp
•
Filing: 1997-10-23
•
Granted: 1999-09-07
•
Expires: 2017-10-23
Abstract
Abstract An acquired (e.g., scanned) image contains an imperceptible periodic signal component (e.g., a sinusoid), decoding of which can be used to automatically determine a linear geometric relationship between the acquired image and the original image in which the signal was embedded, without having the original image available during the decoding process. This known geometric relationship allows for linear geometric properties of the acquired image, such as alignment and scaling, to be automatically matched with those of the original image so that the acquired image may be automatically oriented and scaled to the size of the original image. The embedded periodic signals produce a distinct pattern of local peak power concentrations in a spatial frequency amplitude spectrum of the acquired image. Using geometric constraint information about the embedded signals when the signals were originally embedded in the image, the locations and spatial frequencies of the signals are decoded from the image, providing a linear mapping between the peak power concentrations of the acquired and original image spatial frequency amplitude spectra. This linear mapping can be used to compute the linear geometric relationship between the two images. In an illustrated embodiment, the acquired image contains a set of sinusoidal signals that act as a grid. Decoding of the sinusoids does not require the original image, only information about the predetermined geometric relationship of the embedded sinusoids.
Inventors
- 👤 David J. Fleet
- 👤 David J. Heeger
- 👤 Todd A. Cass
- 👤 David L. Hecht
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 19:16
CPC Classifications
G; G06; G06T; G06T1/00; G06T1/0021; G06T1/0028; G06T1/005; G06T1/0064; H; H04; H04N; H04N1/00; H04N1/32; H04N1/32101; H04N1/32144; H04N1/32149; H04N1/32203; H04N1/32208; H04N1/32229; H04N1/32309; G06T2201/00; G06T2201/005; G06T2201/0051; G06T2201/0083; G06T2201/0202; G06T2201/0601; H04N2201/00; H04N2201/32; H04N2201/3201; H04N2201/3225; H04N2201/3233; H04N2201/3269; H04N2201/327
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
251 words
A method for operating a machine to automatically transform geometric properties of an acquired image version of an original image to match geometric properties of the original image; the machine including a signal source connected for receiving signals, a processor and a memory device for storing data; the data stored in the memory device including instruction data the processor executes to operate the machine; the processor being connected to the memory device for accessing and executing the instruction data stored therein; the method comprising: operating the processor to obtain from the signal source an acquired image data structure defining an acquired image; the acquired image being a version of an original image and additionally having embedded signals therein not included in the original image; the embedded signals having predetermined geometric relationships with respect to each other; operating the processor to obtain geometric constraint data indicating expected geometric relationships about the embedded signals in the acquired image; operating the processor to determine the predetermined geometric relationships of the embedded signals in the acquired image; operating the processor to compute geometric differences between the acquired image and the original image using the predetermined geometric relationships of the embedded signals in the acquired image and using the geometric constraint data indicating the expected geometric relationships of the embedded signals; operating the processor to transform geometric properties of an acquired image version of an original image to match geometric properties of the original image using the geometric differences computed between the acquired and original images.
Claim 2
Independent Claim
251 words
A method for operating a machine to automatically transform geometric properties of an acquired image version of an original image to match geometric properties of the original image; the machine including a signal source connected for receiving signals, a processor and a memory device for storing data; the data stored in the memory device including instruction data the processor executes to operate the machine; the processor being connected to the memory device for accessing and executing the instruction data stored therein; the method comprising: operating the processor to obtain from the signal source an acquired image data structure defining an acquired image; the acquired image being a version of an original image and additionally having embedded signals therein not included in the original image; the embedded signals having predetermined geometric relationships with respect to each other; operating the processor to obtain geometric constraint data indicating expected geometric relationships about the embedded signals in the acquired image; operating the processor to determine the predetermined geometric relationships of the embedded signals in the acquired image; operating the processor to compute geometric differences between the acquired image and the original image using the predetermined geometric relationships of the embedded signals in the acquired image and using the geometric constraint data indicating the expected geometric relationships of the embedded signals; operating the processor to transform geometric properties of an acquired image version of an original image to match geometric properties of the original image using the geometric differences computed between the acquired and original images.
Claim 3
Dependent Claim
83 words
The method of claim 1 for operating a machine to automatically transform geometric properties of an acquired image version of an original image to match geometric properties of the original image further including, prior to locating the signal in the acquired image data structure, operating the processor to convert the acquired image into a plurality of individual color representations; and wherein determining the geometric relationships of the embedded signals in the acquired image includes using a selected one of the individual color representations.
Claim 4
Dependent Claim
44 words
The method of claim 2 wherein the plurality of individual color representations include a black-white image, a red-green-image and a yellow-blue image; and wherein the selected one of the individual color representations is any one of the black-white, the red-green or the yellow-blue images.
Claim 5
Dependent Claim
43 words
The method of claim 1 for operating a machine to automatically transform geometric properties of an acquired image version of an original image to match geometric properties of the original image wherein the embedded signals in the acquired image are embedded periodic signals.
Claim 6
Dependent Claim
17 words
The method of claim 4 wherein the embedded periodic signals include at least two embedded sinusoidal signals.
Claim 7
Dependent Claim
25 words
The method of claim 5 wherein the at least two embedded sinusoidal signals have different angular orientations and form a grid in the acquired image.
Claim 8
Dependent Claim
94 words
The method of claim 4 wherein determining the geometric relationships of the embedded signals in the acquired image using the geometric constraint data includes operating the processor to produce an amplitude spatial frequency spectrum image of the acquired image; operating the processor to determine locations in the amplitude spatial frequency spectrum image of local peak power concentrations representing the embedded periodic signals in the acquired image; and operating the processor to compute the geometric relationships among the embedded periodic signals using the geometric constraint data and the locations of the local peak power concentrations.
Claim 9
Dependent Claim
44 words
The method of claim 7 wherein the geometric relationships among the embedded periodic signals include angular orientation differences and radial frequency ratios among the local peak power concentrations as measured from a point assigned as an origin of the amplitude spatial frequency spectrum image.
Claim 10
Dependent Claim
88 words
The method of claim 1 for operating a machine to automatically transform geometric properties of an acquired image version of an original image to match geometric properties of the original image wherein the geometric differences computed between the acquired image and the original image include an image size difference; the acquired image being scaled to a different size than the original image; and wherein transforming the geometric properties of the acquired image includes scaling the size of the acquired image to match the size of the original image.
Claim 11
Dependent Claim
85 words
The method of claim 1 for operating a machine to automatically transform geometric properties of an acquired image version of an original image to match geometric properties of the original image wherein the geometric differences computed between the acquired image and the original image include an image orientation difference; the acquired image having a different spatial orientation than the original image; and wherein transforming the geometric properties of the acquired image includes rotating the acquired image to match the spatial orientation of the original image.
Claim 12
Dependent Claim
45 words
The method of claim 1 for operating a machine to automatically transform geometric properties of an acquired image version of an original image to match geometric properties of the original image wherein the geometric constraint data is obtained from data included in the acquired image.
Claim 13
Dependent Claim
42 words
The method of claim 1 for operating a machine to automatically transform geometric properties of an acquired image version of an original image to match geometric properties of the original image wherein the geometric constraint data is obtained from a signal source.
Claim 14
Independent Claim
268 words
A method for operating a processor-controlled machine to decode periodic signals embedded in an image; the machine including a processor and a memory device for storing data; the data stored in the memory device including instruction data the processor executes to operate the machine; the processor being connected to the memory device for accessing and executing the instruction data stored therein; the method comprising: operating the processor to obtain an image data structure defining an image; the image including a set of n periodic signals embedded therein; the set of n periodic signals having geometric relationships with respect to each other; operating the processor to obtain geometric constraint data indicating expected geometric relationships about the set of n periodic signals embedded in the image; operating the processor to identify a plurality of local peak power concentrations in a two-dimensional spatial frequency power spectrum of the image; operating the processor to eliminate a subset of the local peak power concentrations that do not satisfy the geometric constraint data indicating expected geometric relationships about the set of n periodic signals embedded in the image; a remaining subset of the local peak power concentrations being determined to be candidate local peak power concentrations indicating spatial frequencies and directions of the set of n periodic signals; and operating the processor to compute a best linear mapping between sets of n candidate local peak power concentrations in the image and a set of n periodic signals indicated by the geometric constraint data; the best linear mapping identifying the spatial frequencies and directions of the set of n periodic signals embedded in the image.
Claim 15
Independent Claim
268 words
A method for operating a processor-controlled machine to decode periodic signals embedded in an image; the machine including a processor and a memory device for storing data; the data stored in the memory device including instruction data the processor executes to operate the machine; the processor being connected to the memory device for accessing and executing the instruction data stored therein; the method comprising: operating the processor to obtain an image data structure defining an image; the image including a set of n periodic signals embedded therein; the set of n periodic signals having geometric relationships with respect to each other; operating the processor to obtain geometric constraint data indicating expected geometric relationships about the set of n periodic signals embedded in the image; operating the processor to identify a plurality of local peak power concentrations in a two-dimensional spatial frequency power spectrum of the image; operating the processor to eliminate a subset of the local peak power concentrations that do not satisfy the geometric constraint data indicating expected geometric relationships about the set of n periodic signals embedded in the image; a remaining subset of the local peak power concentrations being determined to be candidate local peak power concentrations indicating spatial frequencies and directions of the set of n periodic signals; and operating the processor to compute a best linear mapping between sets of n candidate local peak power concentrations in the image and a set of n periodic signals indicated by the geometric constraint data; the best linear mapping identifying the spatial frequencies and directions of the set of n periodic signals embedded in the image.
Claim 16
Dependent Claim
35 words
The method of claim 13 for operating a machine to decode periodic signals embedded in an image wherein the set of n periodic signals embedded in the image is a set of n sinusoidal signals.
Claim 17
Dependent Claim
30 words
The method of claim 13 wherein the set of n sinusoidal signals include at least two sinusoidal signals having different angular orientations in the modified image and forming a grid.
Claim 18
Dependent Claim
99 words
The method of claim 13 for operating a machine to decode periodic signals embedded in an image wherein the image is a color image; wherein the set of n periodic signals embedded in the color image are embedded in at least one of a plurality of opponent-color image representations of the color image; and wherein identifying the plurality of local peak power concentrations in the image includes converting the color image into the plurality of opponent-color image representations and identifying the plurality of local peak power concentrations in the at least one of the plurality of opponent-color image representations.
Claim 19
Dependent Claim
43 words
The method of claim 16 wherein the opponent color image representations include a yellow-blue color band; and wherein identifying the plurality of local peak power concentrations in the image includes identifying the plurality of local peak power concentrations in the yellow-blue color band.
Claim 20
Dependent Claim
303 words
An article of manufacture for use in a machine that includes a memory device for storing data; a storage medium access device for accessing a medium that stores data; and a processor connected for accessing the data stored in the memory device and for receiving data from the storage medium access device; the article comprising: a data storage medium that can be accessed by the storage medium access device when the article is used in the machine; and data stored in the data storage medium so that the storage medium access device can provide the stored data to the processor when the article is used in the machine; the stored data comprising instruction data indicating instructions the processor can execute; the processor, in executing the instructions, obtaining from a signal source an acquired image data structure defining an acquired image; the acquired image being a version of an original image and additionally having embedded signals therein not included in the original image; the embedded signals having geometric relationships with respect to each other; the processor, further in executing the instructions, obtaining geometric constraint data indicating expected geometric relationships about the embedded signals in the acquired image; the processor, further in executing the instructions, determining the geometric relationships of the embedded signals in the acquired image; the processor, further in executing the instructions, computing geometric differences between the acquired image and the original image using the geometric relationships of the embedded signals in the acquired image and using the geometric constraint data indicating the expected geometric relationships of the embedded signals in the original image; the processor, still further in executing the instructions, transforming geometric properties of an acquired image version of an original image to match geometric properties of the original image using the geometric differences computed between the acquired and original images.
Claim 21
Dependent Claim
303 words
An article of manufacture for use in a machine that includes a memory device for storing data; a storage medium access device for accessing a medium that stores data; and a processor connected for accessing the data stored in the memory device and for receiving data from the storage medium access device; the article comprising: a data storage medium that can be accessed by the storage medium access device when the article is used in the machine; and data stored in the data storage medium so that the storage medium access device can provide the stored data to the processor when the article is used in the machine; the stored data comprising instruction data indicating instructions the processor can execute; the processor, in executing the instructions, obtaining from a signal source an acquired image data structure defining an acquired image; the acquired image being a version of an original image and additionally having embedded signals therein not included in the original image; the embedded signals having geometric relationships with respect to each other; the processor, further in executing the instructions, obtaining geometric constraint data indicating expected geometric relationships about the embedded signals in the acquired image; the processor, further in executing the instructions, determining the geometric relationships of the embedded signals in the acquired image; the processor, further in executing the instructions, computing geometric differences between the acquired image and the original image using the geometric relationships of the embedded signals in the acquired image and using the geometric constraint data indicating the expected geometric relationships of the embedded signals in the original image; the processor, still further in executing the instructions, transforming geometric properties of an acquired image version of an original image to match geometric properties of the original image using the geometric differences computed between the acquired and original images.
References Cited (Backward Citations)
US4120045A
Cited
US4964066A
Cited
US5199081A
Cited
US5091966A
Cited
US5315098A
Cited
US5278400A
Cited
US5416308A
Cited
US5629990A
Cited
WO1995014289A2
Cited
US5646388A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-09-06 | 2003-03-08 | 2003-09-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-09-06 | 2007-03-08 | 2007-09-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-09-06 | 2011-03-08 | 2011-09-07 | $7700.00 | Window Closed / Lapsed |