Three-dimensional image synthesis using view interpolation

• US 5,613,048 A
• Filed: 08/03/1993
• Issued: 03/18/1997
• Est. Priority Date: 08/03/1993
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Williams, Lance, Chen, Shenchang E.
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US08/100,923
• Time in Patent Office: 1,323 Days
• Field of Search: 395/119, 395/120, 395/121, 395/125, 395/126, 395/127, 395/133, 395/136-139, 395/141, 395/152, 395/919, 395/920, 382/286, 382/289, 382/293, 382/300, 382/302, 382/307, 382/308
• US Class Current: 345/419
• CPC Class Codes: G06T 15/205 Image-based rendering
• CPC Class Codes: G06T 2210/44 Morphing

Abstract

Three-dimensional scenes are portrayed from different viewpoints by morphing two-dimensional images. Various key views of a scene are stored, along with offset maps that identify the correspondence of pixels in adjacent stored images. When an intermediate view of the scene is to be presented, one or more stored views are interpolated through a morphing technique. Since the key views and their offset data are pre-stored, the morphing and presentation of new views can be carried out at interactive rates. By providing the ability to quickly compute many closely spaced views, the disclosed morphing technique also facilitates the rapid computation of soft shadows and motion blur in images.

Claims

1. A method for synthesizing views of a three-dimensional scene, comprising the steps of:

storing a plurality of two-dimensional images of the scene from different respective source viewpoints;

for each pair of images relating to adjacent viewpoints, determining and storing a map which identifies correspondence of pixels in the two images;

identifying a viewpoint located between at least two of said source viewpoints;

determining a coefficient relating to the location of said intermediate viewpoint relative to said source viewpoints;

morphing at least one of said images in accordance with said coefficient and the information contained in at least one of said maps to produce an interpolated image which defines the view from said intermediate viewpoint; and

displaying the interpolated image.

2. The method of claim 1 wherein multiple images are morphed, using multivariate interpolation, to produce a composite image that comprises said interpolated image.

3. The method of claim 1 wherein a pair of bidirectional offset maps are determined and stored for each pair of adjacent images.

4. The method of claim 1 wherein each map contains offset vectors which describe spatial displacement of image pixels in going from one image to another.

5. The method of claim 1, further including the step of decomposing said maps into blocks of pixels, in accordance with a compression threshold.

6. The method of claim 5, wherein the offset map identifies the correspondence of groups of pixels in the two images.

7. The method of claim 5, further including the step of sorting the blocks of pixels within a map in accordance with range information.

8. The method of claim 7 wherein said step of producing an interpolated image includes the steps of:

copying pixel blocks from the source image to the destination image in said sorted order;

identifying pixels in the destination image to which no pixel from the source image was copied; and

for each identified pixel, filtering a parameter associated with at least one pixel in the neighborhood of said identified pixel, to compute a display value for the identified pixel.

9. The method of claim 8 wherein said parameter is the color of the adjacent pixel.

10. The method of claim 8 wherein said parameter is a displacement value for the adjacent pixel.

11. The method of claim 1, wherein each source viewpoint has an associated field of view defined by a central axis and edge boundaries, and wherein said source viewpoints are selected such that the angle between the edge boundary of one viewpoint and the central axis of an adjacent viewpoint does not exceed 90°

.

12. A system for generating a sequence of related images corresponding to different views of a scene, comprising:

means for storing an array of images which correspond to views of the scene from different respective source viewpoints;

means for determining correspondence between adjacent images in said array and storing maps which identify said correspondence;

means for indicating a new viewpoint located between at least two of said source viewpoints;

means for interpolating information in at least one of said maps to produce an interpolated image corresponding to a view of the scene from said new viewpoint; and

means for displaying the interpolated image.

13. The system of claim 12 further including means for decomposing said maps into blocks of pixels, wherein the pixels in each block have a common characteristic relating to the correspondence between images.

14. The system of claim 13 wherein said decomposing means includes means for determining the value of a parameter for each block which relates to distance from a viewpoint, and means for storing said blocks in an order determined by said parameter values.

15. The system of claim 14 wherein said interpolating means interpolates and displays said blocks in said stored order.

16. The system of claim 12 wherein said array is multi-dimensional, and said interpolated image is interpolated from at least two of said maps.

17. The system of claim 12, wherein said interpolating means comprises means for morphing pixel data for at least one of said images in accordance with the information in said at least one map.

18. A method for synthesizing views of a scene, comprising the steps of:

storing two images of the scene from two different reference source points;

determining and storing a map which identifies correspondence of pixels in the two images;

identifying a plurality of intermediate locations between said reference source points;

for each intermediate location, determining a coefficient relating to its location relative to said reference source points, and morphing at least one of said images in accordance with said coefficient and information contained in at least one of said maps to produce an interpolated image for said intermediate location; and

combining the interpolated images for the plurality of intermediate locations to produce a composite image.

19. The method of claim 18 wherein said reference source points are the respective ends of a linear light source, and said composite image comprises a soft shadow of the light source.

20. A method for synthesizing views of a three-dimensional scene that contains a moving object, comprising the steps of:

storing a plurality of source images of the scene from different respective source viewpoints, where each image is comprised of pixels having data associated therewith;

for each pair of source images relating to adjacent viewpoints, determining and storing a map which identifies the correspondence of pixels in the two images;

identifying a viewpoint between at least two of said source viewpoints;

determining a coefficient relating to the location of said intermediate viewpoint relative to said source viewpoints;

morphing pixel data for at least one of said source images to corresponding pixel locations in a destination image which defines a view from said intermediate viewpoint, in accordance with said coefficient and the information contained in at least one of said maps;

determining a time interval;

for at least selected ones of the pixel locations in said destination image, determining a portion of said time interval during which a pixel from said one source image crosses the location of a selected pixel; and

displaying the pixel from said one source image in the selected pixel of said destination image during the determined portion of the time interval.

21. The method of claim 20 further including the steps of determining whether at least two pixels from said source image cross the selected pixel of the destination image during the same portion of said time interval, establishing a depth value for each pixel in the source image, and displaying one of said two pixels during said portion of said time interval in accordance with their respective depth values.