Method, apparatus and computer program product for generating perspective corrected data from warped information

• US 6,369,818 B1
• Filed: 11/25/1998
• Issued: 04/09/2002
• Est. Priority Date: 11/25/1998
• Status: Expired due to Term

• Current Assignee: Chartoleaux KG LLC (Intellectual Ventures LLC)
• Original Assignee: Be Here Corporation
• Inventors: Furlan, John Louis Warpakowski, Hoffman, Robert G.
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US09/200,172
• Time in Patent Office: 1,231 Days
• Field of Search: 345/419, 345/427, 345/433, 345/423, 345/424, 345/441, 345/442, 345/443
• US Class Current: 345/427
• CPC Class Codes: G06T 15/20 Perspective computation

Abstract

Apparatus, methods, and computer program products are disclosed that provides fast and accurate means of mapping one data space into another by precisely mapping grid points between the data spaces and then by performing a bilateral-bilinear interpolation to map the points bounded by the precisely mapped grid points. The precisely mapped grid points define boundary lines that bound a data region in a source: space. Each scan line mapped to the source space is dependent on the slopes of the bounding lines of the data region.

Claims

1. A computer controlled method including steps of:

determining a region in a destination data space, said region bounded by a plurality of grid points and said region defining a first plurality of data points in said destination data space;

precisely mapping said plurality of grid points to a plurality of mapped grid points in a source data space associating a second plurality of data points, wherein said plurality of mapped grid points define a plurality of boundary lines that represent the boundary of said region as mapped into said source data space; and

applying a bilateral-bilinear interpolation algorithm to map said first plurality of data points to said second plurality of data points wherein the bilateral-bilinear interpolation algorithm includes steps of;

determining a second slope for a second of said plurality of boundary lines and a third slope for a third of said plurality of boundary lines, wherein a first of said plurality of boundary lines is bounded by said second of said plurality of boundary lines and said third of said plurality of boundary lines;

determining a subsequent line defined by a subsequent starting point and a subsequent ending point dependent on said second slope and said third slope respectively, said subsequent line having a subsequent line slope also dependent on said second slope and said third slope;

iterating, responsive to said subsequent line slope, to map some of said first plurality of data points to some of said second plurality of data points associated with said subsequent line; and

repeating the step of determining said subsequent line and the step of iterating until substantially all of said first plurality of data points in said region are mapped to said source data space.

2. The computer controlled method of claim 1 further including:

determining a first slope for said first of said plurality of boundary lines; and

iterating, responsive to said first slope, to map some of said first plurality of data points to some of said second plurality of data points associated with said first of said plurality of boundary lines.

3. The computer controlled method of claim 1 further including:

storing a value for one of said first plurality of data points.

4. The computer controlled method of claim 1 wherein said region is a patch and said destination data space is a two dimensional space.

5. The computer controlled method of claim 1 wherein said second plurality of data points represents a warped image and said first plurality of data points represents a perspective corrected image.

6. The computer controlled method of claim 5 wherein said warped image represents a true image warped by a lens, said perspective corrected image substantially representing said true image.

7. The computer controlled method of claim 6 wherein said lens is a catadioptric lens.

8. The computer controlled method of claim 1 further including presenting said first plurality of data points using a presentation device.

9. An apparatus having a central processing unit (CPU) and a memory coupled to said CPU, said apparatus including:

a region determination mechanism configured to determine a region in a destination data space, said region bounded by a plurality of grid points and said region defining a first plurality of data points in said destination data space;

a precise mapping mechanism configured to precisely map said plurality of grid points determined by the region determination mechanism to a plurality of mapped grid points in a source data space associating a second plurality of data points, wherein said plurality of mapped grid points define a plurality of boundary lines that represent the boundary of said region as mapped into said source data space; and

a bilateral-bilinear interpolation mechanism configured to map said first plurality of data points in said region to said second plurality of data points using said plurality of mapped grid points wherein the bilateral-bilinear interpolation mechanism includes;

a boundary line determination mechanism configured to determine a second slope for a second of said plurality of boundary lines and a third slope for a third of said plurality of boundary lines, wherein a first of said plurality of boundary lines is bounded by said second of said plurality of boundary lines and said third of said plurality of boundary lines;

a subsequent line determination mechanism configured to determine a subsequent line defined by a subsequent starting point and a subsequent ending point dependent on said second slope and said third slope respectively, said subsequent line having a subsequent line slope also dependent on said second slope and said third slope;

a data point iteration mechanism configured to map some of said first plurality of data points to some of said second plurality of data points associated with said subsequent line and responsive to said subsequent line slope; and

a loop mechanism configured to repetitively apply the subsequent line determination mechanism and the data point iteration mechanism until substantially all of said first plurality of data points in said region are mapped to said source data space.

10. The apparatus of claim 9 further including:

an assignment mechanism configured to store a value for one of said first plurality of data points.

11. The apparatus of claim 9 wherein said region is a patch and said destination data space is a two dimensional space.

12. The apparatus of claim 9 wherein said second plurality of data points represents a warped image and said first plurality of data points represents a perspective corrected image.

13. The apparatus of claim 12 wherein said warped image represents a true image warped by a lens, said perspective corrected image substantially representing said true image.

14. The apparatus of claim 13 wherein said lens is a catadioptric lens.

15. The apparatus of claim 9 further including a presentation device configured to present said first plurality of data points.

16. A computer program product including:

a computer usable storage medium having computer readable code embodied therein for causing a computer to map a destination data space to a source data space, said computer readable code including;

computer readable program code configured to cause said computer to effect a region determination mechanism configured to determine a region in said destination data space, said region bounded by a plurality of grid points and said region defining a first plurality of data points in said destination data space;

computer readable program code configured to cause said computer to effect a precise mapping mechanism configured to precisely map said plurality of grid points determined by the region determination mechanism to a plurality of mapped grid points in said source data space associating a second plurality of data points, wherein said plurality of mapped grid points define a plurality of boundary lines that represent the boundary of said region as mapped into said source data space; and

computer readable program code configured to cause said computer to effect a bilateral-bilinear interpolation mechanism configured to map said first plurality of data points in said region to said second plurality of data points using said plurality of mapped grid points wherein the bilateral-bilinear interpolation mechanism includes;

computer readable program code configured to cause said computer to effect a boundary line determination mechanism configured to determine a second slope for a second of said plurality of boundary lines and a third slope for a third of said plurality of boundary lines, wherein a first of said plurality of boundary lines is bounded by said second of said plurality of boundary lines and said third of said plurality of boundary lines;

computer readable program code configured to cause said computer to effect a subsequent line determination;

mechanism configured to determine a subsequent line defined by a subsequent starting point and a subsequent ending point dependent on said second slope and said third slope respectively, said subsequent line having a subsequent line slope also dependent on said second slope and said third slope;

computer readable program code configured to cause said computer to effect a data point iteration mechanism configured to map some of said first plurality of data points to some of said second plurality of data points associated with said subsequent line and responsive to said subsequent line slope; and

computer readable program code configured to cause said computer to effect a loop mechanism configured to repetitively apply the subsequent line determination mechanism and the data point iteration mechanism until substantially all of said first plurality of data points in said region are mapped to said source data space.

17. The computer program product of claim 16 wherein said region is a patch and said destination data space is a two dimensional space.

18. The computer program product of claim 16 wherein said second plurality of data points represents a warped image and said first plurality of data points represents a perspective corrected image.

19. The computer program product of claim 18 wherein said warped image represents a true image warped by a lens, said perspective corrected image substantially representing said true image.

20. The computer program product of claim 19 wherein said lens is a caladioptric lens.

21. The computer program product of claim 16 further including computer readable program code configured to cause said computer to drive a presentation device configured to present said first plurality of data points.

22. A computer program product including,

a computer data signal embodied in a carrier wave having computer readable code embodied therein for causing a computer to map a destination data space to a source data space, said computer readable code including:

computer readable program code configured to cause said computer to effect a region determination mechanism configured to determine a region in said destination data space, said region bounded by a plurality of grid points and said region defining a first plurality of data points in said destination data space;

computer readable program code configured to cause said computer to effect a precise mapping mechanism configured to precisely map said plurality of grid points determined by the region determination mechanism to a pluralityof mapped grid points in said source data space associating a second plurality of data points, wherein said plurality of mapped grid points define a plurality of boundary lines that represent the boundary of said region as mapped into said source data space; and

computer readable program code configured to cause said computer to effect a bilateral-bilinear interpolation mechanism configured to map said first plurality of data points in said region to said second plurality of data points using said plurality of mapped grid points wherein the bilateral-bilinear interpolation mechanism includes;

computer readable program code configured to cause said computer to effect a boundary line determination mechanism configured to determine a second slope for a second of said plurality of boundary lines and a third slope for a third of said plurality of boundary lines, wherein a first of said plurality of boundary lines is bounded by said second of said plurality of boundary lines and said third of said plurality of boundary lines;

computer readable program code configured to cause said computer to effect a subsequent line determination mechanism configured to determine a subsequent line defined by a subsequent starting point and a subsequent ending point dependent on said second slope and said third slope respectively, said subsequent line having a subsequent line slope also dependent on said second slope and said third slope;

computer readable program code configured to cause said computer to effect a data point iteration mechanism configured to map some of said first plurality of data points to some of said second plurality of data points associated with said subsequent line and responsive to said subsequent line slope; and

computer readable program code configured to cause said computer to effect a loop mechanism configured to repetitively apply the subsequent line determination mechanism and the data point iteration mechanism until substantially all of said first plurality of data points in said region are mapped to said source data space.

23. The computer program product of claim 22 wherein said region is a patch and said destination data space is a two dimensional space.

24. The computer program product of claim 22 wherein said second plurality of data points represents a warped image and said first plurality of data points represents a perspective corrected image.

25. The computer program product of claim 24 wherein said warped image represents a true image warped by a lens, said perspective corrected image substantially representing said true image.