Method and system for processing a non-linear two dimensional spatial transformation

• US 7,126,616 B2
• Filed: 06/12/2002
• Issued: 10/24/2006
• Est. Priority Date: 06/12/2001
• Status: Active Grant

• Current Assignee: Geo Semiconductor Incorporated
• Original Assignee: Silicon Optix (Renesas Electronics Corporation)
• Inventors: Bassi, Zorawar S., Lee, Louie, Jasa, Tomislav
• Primary Examiner(s): Razavi, Michael
• Assistant Examiner(s): Chung, Daniel
• Application Number:
  US10/167,375
• Publication Number:
  US 20030020732A1
• Time in Patent Office: 1,595 Days
• Field of Search: 345/645, 345/643, 345/646, 345/648, 345/649, 345/619, 345/660, 345/606
• US Class Current: 345/645
• CPC Class Codes: G06T 5/80 Geometric correction

Abstract

An image transformation method for translating a non-linear 2D geometrical transformation into two separable 1D geometrical transformations first determines the inverse of the 2D geometrical transformation to form an inverse 2D geometrical transformation. Then the method converts the inverse 2D geometrical transformation into an analytical inverted 2D geometrical transformation and separates the analytical inverse 2D geometrical transformation into first and second 1D geometrical transformations. The method then represents said inverse 2D geometrical transformation and first and second 1D geometrical transformations as tensor spline surfaces and then compares an evaluation of said first and second 1D geometrical transformations at each pixel with an evaluation of the analytical inverse 2D geometrical transformation at each pixel. If the error evaluation does not meet a predetermined level of performance then the separation and transformation steps are repeated. Since the method involves one-dimensional spatial transform processing it results in reduced calculations, efficient memory access, and ability to process data in a real-time environment. In-addition, since the method provides a compact representation of the spatial transforms, it can be scaled for a particular level of precision.

Claims

1. An electronic method for non-linear two-dimensional (2D) digital image transformation of an input image having a plurality of input pixels onto an output image having a plurality of output pixels, said method comprising:

(a) determining the inverse of the non-linear 2D geometrical transformation to form an inverse 2D geometrical transformation;

(b) converting the inverse 2D geometrical transformation into an analytical inverted 2D geometrical transformation;

(c) separating the analytical inverse 2D geometrical transformation into a first and second 1D geometrical transformations;

(d) representing said first and second 1D geometrical transformations as transformation surfaces;

(e) approximating said surfaces of (d) with offset polynomials and target increment polynomials for hardware implementation; and

(f) comparing an evaluation of said first and second 1D geometrical transformations at each pixel with an evaluation of the analytical inverse 2D geometrical transformation at each pixel and repeating steps (c), (d) and (e) until said evaluation meets a predetermined level of performance.

2. The method of claim 1, further comprising the step of performing a geometric transformation on the inverse map, between steps (b) and (c).

3. The method of claim 1, wherein said inverse 2D geometrical transformation must be defined on a uniform point mapping grid.

4. The method of claim 1, wherein said inverse 2D geometrical transformation is applied in combination with a scaling map.

9. The method of claim 1, wherein the offset and target increment polynomials are sampled on a uniform grid for economic hardware implementation, and wherein at each given position, said polynomials are interpolated to estimated the value of these polynomials at the given position.

10. The method of claim 1, wherein each 1D geometrical transformation in (d) is divided into segments and for each segment, the transformation is computed separately.

11. The method of claim 10, wherein the degree of the offset polynomials and the degree of the target increment polynomials in each segment is determined according to the complexity of the geometrical transformation in that segment.

12. The method of claim 1 used for optical and geometric distortion correction of an image acquisition system.

13. The method of claim 1 used for optical and geometric distortion correction of an image display system.

14. The method of claim 1 used for optical and geometric distortion correction of a combined image acquisition and image display system.

19. The system of claim 1 adapted for optical and geometric distortion correction of an image display system.

20. The system of claim 1 adapted for optical and geometric distortion correction of a combined image acquisition and image display system.

5. An electronic system for non-linear two-dimensional (2D) digital image transformation of an input image having a plurality of input pixels onto an output image having a plurality of output pixels, said system comprising:

(a) a processor to determine the inverse of the non-linear 2D geometrical transformation to form an inverse 2D geometrical transformation;

(b) a converter, coupled to said processor, to convert the inverse 2D geometrical transformation into an analytical inverted 2D geometrical transformation;

(c) a separator, coupled to said converter, to separate the analytical inverse 2D geometrical transformation into first and second 1D geometrical transformations;

(d) a surface function estimator, coupled to said separator, to represent said first and second 1D geometrical transformations as transformation surfaces;

(e) a fitting stage, coupled to said surface function estimator, to approximate said surfaces of (d) with offset polynomials and target increment polynomials for hardware implementation; and

,

(f) an error analysis stage, coupled to said filling stage, to compare an evaluation of said first and second 1D geometrical transformations at each pixel with an evaluation of the analytical inverse 2D geometrical transformation at each pixel and to repeat steps (c), (d) and (e) until said evaluation meets a predetermined level of performance.

6. The image transformation system of claim 5, further comprising a geometrical module coupled to the processor for performing a geometric transformation on the inverse map.

7. The image transformation system of claim 5, wherein said inverse 2D geometrical transformation must be defined on a uniform point mapping grid.

8. The image transformation system of claim 5, wherein said inverse 2D geometrical transformation is applied in combination with a scaling map.

15. The system of claim 5, further adapted to sample the offset and target increment polynomials on a uniform grid for economic hardware implementation, at each given position, adapted to interpolate said polynomials to estimate the value of these polynomials at the given position.

16. The system of claim 5, further adapted to divide each 1D geometrical transformation in (d) into segments and for each segment, to compute the transformation separately.

17. The system of claim 16, further adapted to determine the degree of the offset polynomials and the degree of the target increment polynomials in each segment according to the complexity of the geometrical transformation in that segment.

18. The system of claim 5 adapted for optical and geometric distortion correction of an image acquisition system.