PIECEWISE PLANAR RECONSTRUCTION OF THREE-DIMENSIONAL SCENES

• US 20100315412A1
• Filed: 06/15/2009
• Published: 12/16/2010
• Est. Priority Date: 06/15/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sinha, Sudipta Narayan, Szeliski, Richard Stephen, Steedly, Drew Edward
• Granted Patent: US 8,933,925 B2
• Time in Patent Office: Days
• US Class Current: 345/419
• CPC Class Codes: G06T 15/00 3D [Three Dimensional] image rendering
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2207/20072 Graph-based image processing
• CPC Class Codes: G06T 7/143 involving probabilistic approaches, e.g. Markov random field [MRF] modelling
• CPC Class Codes: G06T 7/536 from perspective effects, e.g. by using vanishing points
• CPC Class Codes: G06T 7/55 from multiple images

Abstract

Methods, systems, and computer-readable media for reconstruction a three-dimensional scene from a collection of two-dimensional images are provided. A computerized reconstruction system executes computer vision algorithms on the collection of two-dimensional images to identify candidate planes that are used to model visual characteristics of the environment depicted in the two-dimensional images. The computer vision algorithms may minimize an energy function that represents the relationships and similarities among features of the two-dimensional images to assign pixels of the two dimensional images to planes in the three dimensional scene. The three-dimensional scene is navigable and depicts viewpoint transitions between multiple two-dimensional images.

Claims

1. A computer-implemented method to select planes that are used to render a navigable three-dimensional scene from a collection of images stored in an electronic database, the computer-implemented method comprising:

receiving the collection of images from the electronic database;

extracting scene information from the collection of images;

detecting vanishing directions within each image in the collection of images using edge detection and two-dimensional line segment extraction;

identifying each plane in the navigable three-dimensional scene based on the vanishing directions and the scene information; and

generating a Markov Random Field distribution to assign pixels to each plane based on minimization functions applied to the Markov Random Field distribution to optimize a global cost of assigning the pixel to a plane in the navigable three-dimensional scene.

2. The computer-implemented method of claim 1, wherein the scene information includes camera calibrations, a three-dimensional point cloud, three-dimensional line segments, and data for multi-view correspondence of points and lines.

3. The computer-implemented method of claim 2, wherein mean shift clustering is used to detect the vanishing directions for different views captured by the collection of images.

4. The computer-implemented method of claim 1, wherein parallel lines extracted from the collection of images are used to detect the vanishing directions.

5. The computer-implemented method of claim 1, further comprising:

determining a set of plane orientations based on a cross product of each possible pair of vanishing directions extracted from the collection of images.

6. The computer-implemented method of claim 1, wherein a portion of the global cost of plane-pixel assignments is represented by smoothness terms included in the minimization functions applied to a Markov Random Field distribution graph, the smoothness terms are calculated to prefer transitions between planes at pixels corresponding to discontinuities at two-dimensional lines that are consistent with the vanishing directions orthogonal to the normal vector of an occluding plane.

7. The computer-implemented method of claim 6, further comprising:

calculating smoothness terms in a Markov Random Field distribution graph to penalize assignment of a pixel in one image to a plane if the corresponding pixel in neighboring images did not choose the same plane.

8. The computer-implemented method of claim 6, further comprising:

calculating smoothness terms in the Markov Random Field distribution graph to prefer transitions corresponding to two-dimensional lines or two-dimensional line segments in the image.

9. The computer-implemented method of claim 6, wherein pixels in each image in the collection of images iteratively vote to determine the plane-label assignments that minimize the global cost.

10. The computer-implemented method of claim 6, wherein the minimization functions select cut costs in the Markov Random Field distribution graph that are constrained by the smoothness terms.

12. The computer-readable media of claim 10, wherein the depth maps are used to render a navigable three dimensional scene.

13. The computer-readable media of claim 10, further comprising:

correcting the depth map and boundaries by identifying occlusion edges and crease edges.

14. The computer-readable media of claim 10, further comprising:

rendering a three dimensional scene using the depth map and projections of the two dimensional images onto their corresponding depth maps, wherein cross fading between multiple two dimensional images allows smooth view interpolation for each of the two dimensional images in the collection.

15. The computer-readable media of claim 10, wherein assigning pixels to the generated planes to minimize an energy function represented by the Markov Random Field further comprises:

accounting for multiview-photo consistency, geometric proximity of sparse three-dimensional points and lines, and free space violations derived from ray visibility of the three-dimensional points and lines.

16. The computer-readable media of claim 15, wherein assigning pixels to the generated planes to minimize an energy function represented by the Markov Random Field further comprises:

optimizing the Markov Random Field based on data terms that set conditions for assigning pixels and smoothness terms that set conditions for transitioning between planes.

17. The computer-readable media of claim 10, wherein the data terms penalize assigning a pixel in one image to a plane if the corresponding pixel in neighboring images did not choose the same plane during an iterative pass on each two-dimensional image.

18. The computer-readable media of claim 10, wherein the smoothness terms comprise at least one of the following smoothness terms:

smoothness terms that prefers transitions corresponding to discontinuities at two-dimensional lines that are consistent with the vanishing directions orthogonal to the normal vector of an occluding plane, smoothness term that prefer transitions corresponding to two-dimensional lines in the image, or smoothness terms that penalize assigning a pixel in one image to a plane if the corresponding pixel in neighboring images did not choose the same plane during a simultaneous pass on all images in the collection of two-dimensional images.

19. The computer-readable media of claim 10, wherein the scene information includes vanishing directions, lines, and three-dimensional points.

11. One or more computer-readable media storing computer-executable instructions to a perform method that assigns pixels from two-dimensional images to three-dimensional planes when rendering a navigable three-dimensional scene from a collection of two dimensional images stored in an electronic database, the method comprising:

receiving the collection of two-dimensional images;

generating a set of three-dimensional planes from scene information extracted from the two dimensional images;

generating a Markov Random Field using the scene information and the generated three-dimensional planes; and

assigning pixels to the generated planes to minimize an energy function represented by the Markov Random Field, which provides depth maps for the two-dimensional images.

20. A computer system having memories and processors that are configured to generate a navigable three dimensional scene from a collection of two dimensional images, the computer system comprising:

a plane generator configured to generate a set of three-dimensional planes from the scene information extracted from the two dimensional images;

an optimization engine configured to estimate a depth map for each of the two dimensional images and to define global and local boundary constraints for assigning pixels from the two dimensional images to the generated planes; and

a reconstruction engine to create multiple planar polygons from the generate planes, interpolated views, and cross fade views from each image in the collection based on the depth maps for the three dimensional scene.