Patent US5808623A successfully refreshed from Google Patents.
US5808623A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for perspective transform in computer using multi-pass algorithm
Assignee: Adobe Inc
•
Filing: 1996-10-07
•
Granted: 1998-09-15
•
Expires: 2016-10-07
Abstract
Abstract A multi-pass algorithm for applying a perspective transform to quadrilateral images by means of at least two phases of 1-dimensional resampling processes for each dimension. Each phase constitutes a perspective transform from a rectangle to a trapezoid with parallel sides parallel to the corresponding sides of the rectangle. More particularly, each phase comprises a foreshortening pass in one dimension (vertical for parallel horizontal sides, horizontal for parallel vertical sides) followed by a trapezoidal pseudo-shear pass in the other dimension. Thus, in the first phase, the source rectangle is transformed to a first, intermediate trapezoid with either parallel horizontal or parallel vertical sides. In the second phase, the bounding box of this intermediate trapezoid (i.e., the smallest axis-aligned rectangle containing the trapezoid) is transformed to a second, target trapezoid with either parallel vertical or parallel horizontal sides (i.e., the opposite of the intermediate trapezoid) that bounds the final quadrilateral. Thus, by so transforming the bounding box of the intermediate trapezoid, the comers of the intermediate trapezoid are mapped to the corners of the target quadrilateral. The invention has two advantages over the prior art processes: although some complex calculations have to be performed for each row or column, the per pixel calculations are much simpler; and since the shape of the result is a simple trapezoid (remembering that a rectangle is a trapezoid) at each step, it is easy to control the resampling process to ensure that these shapes are achieved and the result appears stable.
Inventors
- 👤 Mark Hamburg
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 18:28
CPC Classifications
G; G06; G06T; G06T3/00
Claims Analysis
Total Claims: 51
Claim 1
Independent Claim
123 words
A computerized method of perspective transformation of an axis-aligned source rectangle represented in a computer by a plurality of pixels, each having coordinates <u, v>, to a target quadrilateral represented in the computer by a plurality of pixels, each having coordinates <x,y>, including the steps of: (a) applying a first phase transformation, comprising two one-dimensional resampling processes, to the pixels <u, v> of the source rectangle to generate an intermediate trapezoid, represented by a plurality of pixels <p,q>, with axis-aligned parallel sides; and (b) applying a second phase transformation, comprising two one-dimensional resampling processes, to the pixels of a rectangle bounding the pixels of the intermediate trapezoid to generate a target trapezoid with axis-aligned parallel sides, the target trapezoid bounding the target quadrilateral.
Claim 2
Dependent Claim
123 words
A computerized method of perspective transformation of an axis-aligned source rectangle represented in a computer by a plurality of pixels, each having coordinates <u, v>, to a target quadrilateral represented in the computer by a plurality of pixels, each having coordinates <x,y>, including the steps of: (a) applying a first phase transformation, comprising two one-dimensional resampling processes, to the pixels <u, v> of the source rectangle to generate an intermediate trapezoid, represented by a plurality of pixels <p,q>, with axis-aligned parallel sides; and (b) applying a second phase transformation, comprising two one-dimensional resampling processes, to the pixels of a rectangle bounding the pixels of the intermediate trapezoid to generate a target trapezoid with axis-aligned parallel sides, the target trapezoid bounding the target quadrilateral.
Claim 3
Dependent Claim
32 words
The method of claim 1, wherein the two one-dimensional resampling processes of the first phase comprise a foreshortening process in a first dimension and a trapezoidal pseudo-shear process in a second dimension.
Claim 4
Dependent Claim
32 words
The method of claim 2, wherein the two one-dimensional resampling processes of the second phase comprise a foreshortening process in the second dimension and a trapezoidal pseudo-shear process in the first dimension.
Claim 5
Dependent Claim
182 words
A computerized method of perspective transformation of an axis-aligned source rectangle represented in a computer by a plurality of pixels, each having coordinates <u, v>, to a target quadrilateral represented in the computer by a plurality of pixels, each having coordinates <x, y>, including the steps of: (a) performing a one-dimensional resampling process comprising a foreshortening, in a first dimension, of the source rectangle to generate a foreshortened rectangle represented by a plurality pixels; (b) performing a one-dimensional resampling process comprising a trapezoidal pseudo-shear, in a second dimension, of the foreshortened rectangle to generate an intermediate trapezoid, with axis-aligned parallel sides, represented by a plurality pixels; (c) performing a one-dimensional resampling process comprising a foreshortening, in the second dimension, of a first rectangle bounding the intermediate trapezoid to generate a second rectangle bounding a foreshortened intermediate trapezoid represented by a plurality pixels; and (d) performing a one-dimensional resampling process comprising a trapezoidal pseudo-shear, in the first dimension, of the second rectangle bounding the foreshortened intermediate trapezoid to generate a target trapezoid, with axis-aligned parallel sides, the target trapezoid bounding the target quadrilateral.
Claim 6
Dependent Claim
182 words
A computerized method of perspective transformation of an axis-aligned source rectangle represented in a computer by a plurality of pixels, each having coordinates <u, v>, to a target quadrilateral represented in the computer by a plurality of pixels, each having coordinates <x, y>, including the steps of: (a) performing a one-dimensional resampling process comprising a foreshortening, in a first dimension, of the source rectangle to generate a foreshortened rectangle represented by a plurality pixels; (b) performing a one-dimensional resampling process comprising a trapezoidal pseudo-shear, in a second dimension, of the foreshortened rectangle to generate an intermediate trapezoid, with axis-aligned parallel sides, represented by a plurality pixels; (c) performing a one-dimensional resampling process comprising a foreshortening, in the second dimension, of a first rectangle bounding the intermediate trapezoid to generate a second rectangle bounding a foreshortened intermediate trapezoid represented by a plurality pixels; and (d) performing a one-dimensional resampling process comprising a trapezoidal pseudo-shear, in the first dimension, of the second rectangle bounding the foreshortened intermediate trapezoid to generate a target trapezoid, with axis-aligned parallel sides, the target trapezoid bounding the target quadrilateral.
Claim 7
Dependent Claim
91 words
The method of claim 4, further including the steps of: (a) determining a parallel-sided trapezoid bounding the target quadrilateral; (b) determining a rectangle bounding the parallel-sided trapezoid bounding the target quadrilateral, such rectangle being the second rectangle; (c) determining coefficients for a perspective transformation resampling function that transforms the second rectangle to the axis-aligned parallel-sided trapezoid bounding the target quadrilateral; and (d) determining the inverse of the determined resampling function; (e) applying the inverse of the determined resampling function to map the corners of the target quadrilateral to the intermediate trapezoid.
Claim 8
Dependent Claim
18 words
The method of claim 4, wherein steps (b) and (c) are combined as a single one-dimensional resampling process.
Claim 9
Dependent Claim
46 words
The method of claim 4, wherein each one-dimensional resampling process has an input for receiving pixels, and an output for generated pixels, wherein the output of the one-dimensional resampling process of step (a) is pipelined to the input of the one-dimensional resampling process of step (b).
Claim 10
Dependent Claim
46 words
The method of claim 4, wherein each one-dimensional resampling process has an input for receiving pixels, and an output for generated pixels, wherein the output of the one-dimensional resampling process of step (b) is pipelined to the input of the one-dimensional resampling process of step (c).
Claim 11
Dependent Claim
70 words
The method of claim 4, wherein each one-dimensional resampling process has an input for receiving pixels, and an output for generated pixels, wherein the output of the one-dimensional resampling process of step (a) is pipelined to the input of the one-dimensional resampling process of step (b), and the output of the one-dimensional resampling process of step (b) is pipelined to the input of the one-dimensional resampling process of step (c).
Claim 12
Dependent Claim
20 words
The method of claim 1 or claim 4, further including the step of displaying the pixels representing the target quadrilateral.
Claim 13
Dependent Claim
21 words
The method of claim 1 or claim 4, wherein the intermediate trapezoid is non-convex and the target quadrilateral is permutably convex.
Claim 14
Dependent Claim
22 words
The method of claim 1 or claim 4, wherein at least one of the intermediate trapezoid and the target trapezoid is non-convex.
Claim 15
Dependent Claim
33 words
The method of claim 4, wherein the one-dimensional resampling process comprising a foreshortening, in the second dimension, of the first rectangle bounding the intermediate trapezoid is limited to avoid excessive compression or expansion.
Claim 16
Dependent Claim
38 words
The method of claim 13, wherein the ratio of the lengths of the parallel sides of the intermediate trapezoid is constrained to be within a selected maximum and a selected minimum value, thereby avoiding excessive compression or expansion.
Claim 17
Dependent Claim
27 words
The method of claim 4, wherein the one-dimensional resampling process comprising a foreshortening, in a first dimension, is applied to a rectangle other than the source rectangle.
Claim 18
Dependent Claim
126 words
A computerized system of perspective transformation of an axis-aligned source rectangle represented in a computer by a plurality of pixels, each having coordinates <u, v>, to a target quadrilateral represented in the computer by a plurality of pixels, each having coordinates <x, y>, including: (a) means for applying a first phase transformation, comprising two one-dimensional resampling processes, to the pixels <u, v> of the source rectangle to generate an intermediate trapezoid, represented by a plurality of pixels <p, q>, with axis-aligned parallel sides; and (b) means for applying a second phase transformation, comprising two one-dimensional resampling processes, to the pixels of a rectangle bounding the pixels of the intermediate trapezoid to generate a target trapezoid with axis-aligned parallel sides, the target trapezoid bounding the target quadrilateral.
Claim 19
Dependent Claim
126 words
A computerized system of perspective transformation of an axis-aligned source rectangle represented in a computer by a plurality of pixels, each having coordinates <u, v>, to a target quadrilateral represented in the computer by a plurality of pixels, each having coordinates <x, y>, including: (a) means for applying a first phase transformation, comprising two one-dimensional resampling processes, to the pixels <u, v> of the source rectangle to generate an intermediate trapezoid, represented by a plurality of pixels <p, q>, with axis-aligned parallel sides; and (b) means for applying a second phase transformation, comprising two one-dimensional resampling processes, to the pixels of a rectangle bounding the pixels of the intermediate trapezoid to generate a target trapezoid with axis-aligned parallel sides, the target trapezoid bounding the target quadrilateral.
Claim 20
Dependent Claim
32 words
The system of claim 16, wherein the two one-dimensional resampling processes of the first phase comprise a foreshortening process in a first dimension and a trapezoidal pseudo-shear process in a second dimension.
Claim 21
Dependent Claim
32 words
The system of claim 17, wherein the two one-dimensional resampling processes of the second phase comprise a foreshortening process in the second dimension and a trapezoidal pseudo-shear process in the first dimension.
Claim 22
Dependent Claim
187 words
A computerized system of perspective transformation of an axis-aligned source rectangle represented in a computer by a plurality of pixels, each having coordinates <u, v>, to a target quadrilateral represented in the computer by a plurality of pixels, each having coordinates <x, y>, including: (a) means for performing a one-dimensional resampling process comprising a foreshortening, in a first dimension, of the source rectangle to generate a foreshortened rectangle represented by a plurality pixels; (b) means for performing a one-dimensional resampling process comprising a trapezoidal pseudo-shear, in a second dimension, of the foreshortened rectangle to generate an intermediate trapezoid, with axis-aligned parallel sides, represented by a plurality pixels; (c) means for performing a one-dimensional resampling process comprising a foreshortening, in the second dimension, of a first rectangle bounding the intermediate trapezoid to generate a second rectangle bounding a foreshortened intermediate trapezoid represented by a plurality pixels; and (d) means for performing a one-dimensional resampling process comprising a trapezoidal pseudo-shear, in the first dimension, of the second rectangle bounding the foreshortened intermediate trapezoid to generate a target trapezoid, with axis-aligned parallel sides, the target trapezoid bounding the target quadrilateral.
Claim 23
Dependent Claim
187 words
A computerized system of perspective transformation of an axis-aligned source rectangle represented in a computer by a plurality of pixels, each having coordinates <u, v>, to a target quadrilateral represented in the computer by a plurality of pixels, each having coordinates <x, y>, including: (a) means for performing a one-dimensional resampling process comprising a foreshortening, in a first dimension, of the source rectangle to generate a foreshortened rectangle represented by a plurality pixels; (b) means for performing a one-dimensional resampling process comprising a trapezoidal pseudo-shear, in a second dimension, of the foreshortened rectangle to generate an intermediate trapezoid, with axis-aligned parallel sides, represented by a plurality pixels; (c) means for performing a one-dimensional resampling process comprising a foreshortening, in the second dimension, of a first rectangle bounding the intermediate trapezoid to generate a second rectangle bounding a foreshortened intermediate trapezoid represented by a plurality pixels; and (d) means for performing a one-dimensional resampling process comprising a trapezoidal pseudo-shear, in the first dimension, of the second rectangle bounding the foreshortened intermediate trapezoid to generate a target trapezoid, with axis-aligned parallel sides, the target trapezoid bounding the target quadrilateral.
Claim 24
Dependent Claim
98 words
The system of claim 19, further including: (a) means for determining a parallel-sided trapezoid bounding the target quadrilateral; (b) means for determining a rectangle bounding the parallel-sided trapezoid bounding the target quadrilateral, such rectangle being the second rectangle; (c) means for determining coefficients for a perspective transformation resampling function that transforms the second rectangle to the axis-aligned parallel-sided trapezoid bounding the target quadrilateral; and (d) means for determining the inverse of the determined resampling function; (e) means for applying the inverse of the determined resampling function to map the corners of the target quadrilateral to the intermediate trapezoid.
Claim 25
Dependent Claim
22 words
The system of claim 19, wherein the means of element (b) and (c) are combined to perform a single one-dimensional resampling process.
Claim 26
Dependent Claim
46 words
The system of claim 19, wherein each one-dimensional resampling process has an input for receiving pixels, and an output for generated pixels, wherein the output of the one-dimensional resampling process of element (a) is pipelined to the input of the one-dimensional resampling process of element (b).
Claim 27
Dependent Claim
46 words
The system of claim 19, wherein each one-dimensional resampling process has an input for receiving pixels, and an output for generated pixels, wherein the output of the one-dimensional resampling process of element (b) is pipelined to the input of the one-dimensional resampling process of element (c).
Claim 28
Dependent Claim
70 words
The system of claim 19, wherein each one-dimensional resampling process has an input for receiving pixels, and an output for generated pixels, wherein the output of the one-dimensional resampling process of element (a) is pipelined to the input of the one-dimensional resampling process of element (b), and the output of the one-dimensional resampling process of element (b) is pipelined to the input of the one-dimensional resampling process of element (c).
Claim 29
Dependent Claim
19 words
The system of claim 16 or claim 19, further including means for displaying the pixels representing the target quadrilateral.
Claim 30
Dependent Claim
21 words
The system of claim 16 or claim 19, wherein the intermediate trapezoid is non-convex and the target quadrilateral is permutably convex.
Claim 31
Dependent Claim
22 words
The system of claim 16 or claim 19, wherein at least one of the intermediate trapezoid and the target trapezoid is non-convex.
Claim 32
Dependent Claim
33 words
The system of claim 19, wherein the one-dimensional resampling process comprising a foreshortening, in the second dimension, of the first rectangle bounding the intermediate trapezoid is limited to avoid excessive compression or expansion.
Claim 33
Dependent Claim
38 words
The system of claim 28, wherein the ratio of the lengths of the parallel sides of the intermediate trapezoid is constrained to be within a selected maximum and a selected minimum value, thereby avoiding excessive compression or expansion.
Claim 34
Dependent Claim
27 words
The system of claim 19, wherein the one-dimensional resampling process comprising a foreshortening, in a first dimension, is applied to a rectangle other than the source rectangle.
Claim 35
Dependent Claim
136 words
A computer program, residing on a computer-readable medium, for perspective transformation of an axis-aligned source rectangle represented in a computer by a plurality of pixels, each having coordinates <u, v>, to a target quadrilateral represented in the computer by a plurality of pixels, each having coordinates <x, y>, the computer program comprising instructions for causing a computer to: (a) apply a first phase transformation, comprising two one-dimensional resampling processes, to the pixels <u, v> of the source rectangle to generate an intermediate trapezoid, represented by a plurality of pixels <p, q>, with axis-aligned parallel sides; and (b) apply a second phase transformation, comprising two one-dimensional resampling processes, to the pixels of a rectangle bounding the pixels of the intermediate trapezoid to generate a target trapezoid with axis-aligned parallel sides, the target trapezoid bounding the target quadrilateral.
Claim 36
Dependent Claim
136 words
A computer program, residing on a computer-readable medium, for perspective transformation of an axis-aligned source rectangle represented in a computer by a plurality of pixels, each having coordinates <u, v>, to a target quadrilateral represented in the computer by a plurality of pixels, each having coordinates <x, y>, the computer program comprising instructions for causing a computer to: (a) apply a first phase transformation, comprising two one-dimensional resampling processes, to the pixels <u, v> of the source rectangle to generate an intermediate trapezoid, represented by a plurality of pixels <p, q>, with axis-aligned parallel sides; and (b) apply a second phase transformation, comprising two one-dimensional resampling processes, to the pixels of a rectangle bounding the pixels of the intermediate trapezoid to generate a target trapezoid with axis-aligned parallel sides, the target trapezoid bounding the target quadrilateral.
Claim 37
Dependent Claim
33 words
The computer program of claim 31, wherein the two one-dimensional resampling processes of the first phase comprise a foreshortening process in a first dimension and a trapezoidal pseudo-shear process in a second dimension.
Claim 38
Dependent Claim
33 words
The computer program of claim 32, wherein the two one-dimensional resampling processes of the second phase comprise a foreshortening process in the second dimension and a trapezoidal pseudo-shear process in the first dimension.
Claim 39
Dependent Claim
193 words
A computer program, residing on a computer-readable medium, for perspective transformation of an axis-aligned source rectangle represented in a computer by a plurality of pixels, each having coordinates <u, v>, to a target quadrilateral represented in the computer by a plurality of pixels, each having coordinates <x, y>, the computer program comprising instructions for causing a computer to: (a) perform a one-dimensional resampling process comprising a foreshortening, in a first dimension, of the source rectangle to generate a foreshortened rectangle represented by a plurality pixels; (b) perform a one-dimensional resampling process comprising a trapezoidal pseudo-shear, in a second dimension, of the foreshortened rectangle to generate an intermediate trapezoid, with axis-aligned parallel sides, represented by a plurality pixels; (c) perform a one-dimensional resampling process comprising a foreshortening, in the second dimension, of a first rectangle bounding the intermediate trapezoid to generate a second rectangle bounding a foreshortened intermediate trapezoid represented by a plurality pixels; and (d) perform a one-dimensional resampling process comprising a trapezoidal pseudo-shear, in the first dimension, of the second rectangle bounding the foreshortened intermediate trapezoid to generate a target trapezoid, with axis-aligned parallel sides, the target trapezoid bounding the target quadrilateral.
Claim 40
Dependent Claim
193 words
A computer program, residing on a computer-readable medium, for perspective transformation of an axis-aligned source rectangle represented in a computer by a plurality of pixels, each having coordinates <u, v>, to a target quadrilateral represented in the computer by a plurality of pixels, each having coordinates <x, y>, the computer program comprising instructions for causing a computer to: (a) perform a one-dimensional resampling process comprising a foreshortening, in a first dimension, of the source rectangle to generate a foreshortened rectangle represented by a plurality pixels; (b) perform a one-dimensional resampling process comprising a trapezoidal pseudo-shear, in a second dimension, of the foreshortened rectangle to generate an intermediate trapezoid, with axis-aligned parallel sides, represented by a plurality pixels; (c) perform a one-dimensional resampling process comprising a foreshortening, in the second dimension, of a first rectangle bounding the intermediate trapezoid to generate a second rectangle bounding a foreshortened intermediate trapezoid represented by a plurality pixels; and (d) perform a one-dimensional resampling process comprising a trapezoidal pseudo-shear, in the first dimension, of the second rectangle bounding the foreshortened intermediate trapezoid to generate a target trapezoid, with axis-aligned parallel sides, the target trapezoid bounding the target quadrilateral.
Claim 41
Dependent Claim
95 words
The computer program of claim 34, further comprising instructions for causing a computer to: (a) determine a parallel-sided trapezoid bounding the target quadrilateral; (b) determine a rectangle bounding the parallel-sided trapezoid bounding the target quadrilateral, such rectangle being the second rectangle; (c) determine coefficients for a perspective transformation resampling function that transforms the second rectangle to the axis-aligned parallel-sided trapezoid bounding the target quadrilateral; and (d) determine the inverse of the determined resampling function; (e) apply the inverse of the determined resampling function to map the corners of the target quadrilateral to the intermediate trapezoid.
Claim 42
Dependent Claim
19 words
The computer program of claim 34, wherein elements (b) and (c) are combined as a single one-dimensional resampling process.
Claim 43
Dependent Claim
47 words
The computer program of claim 34, wherein each one-dimensional resampling process has an input for receiving pixels, and an output for generated pixels, wherein the output of the one-dimensional resampling process of element (a) is pipelined to the input of the one-dimensional resampling process of element (b).
Claim 44
Dependent Claim
47 words
The computer program of claim 34, wherein each one-dimensional resampling process has an input for receiving pixels, and an output for generated pixels, wherein the output of the one-dimensional resampling process of element (b) is pipelined to the input of the one-dimensional resampling process of element (c).
Claim 45
Dependent Claim
71 words
The computer program of claim 34, wherein each one-dimensional resampling process has an input for receiving pixels, and an output for generated pixels, wherein the output of the one-dimensional resampling process of element (a) is pipelined to the input of the one-dimensional resampling process of element (b), and the output of the one-dimensional resampling process of element (b) is pipelined to the input of the one-dimensional resampling process of element (c).
Claim 46
Dependent Claim
24 words
The computer program of claim 31 or claim 34, further comprising instructions for causing a computer to display the pixels representing the target quadrilateral.
Claim 47
Dependent Claim
22 words
The computer program of claim 31 or claim 34, wherein the intermediate trapezoid is non-convex and the target quadrilateral is permutably convex.
Claim 48
Dependent Claim
23 words
The computer program of claim 31 or claim 34, wherein at least one of the intermediate trapezoid and the target trapezoid is non-convex.
Claim 49
Dependent Claim
34 words
The computer program of claim 34, wherein the one-dimensional resampling process comprising a foreshortening, in the second dimension, of the first rectangle bounding the intermediate trapezoid is limited to avoid excessive compression or expansion.
Claim 50
Dependent Claim
39 words
The computer program of claim 43, wherein the ratio of the lengths of the parallel sides of the intermediate trapezoid is constrained to be within a selected maximum and a selected minimum value, thereby avoiding excessive compression or expansion.
Claim 51
Dependent Claim
28 words
The computer program of claim 34, wherein the one-dimensional resampling process comprising a foreshortening, in a first dimension, is applied to a rectangle other than the source rectangle.
References Cited (Backward Citations)
US4841292A
Cited
US5392385A
Cited
US5204944A
Cited
US5247583A
Cited
US5550960A
Cited
US5579456A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-09-14 | 2002-03-16 | 2002-09-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-09-14 | 2006-03-16 | 2006-09-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-09-14 | 2010-03-16 | 2010-09-15 | $7700.00 | Window Closed / Lapsed |