Video generation using three-dimensional hulls

• US 8,917,270 B2
• Filed: 08/30/2012
• Issued: 12/23/2014
• Est. Priority Date: 05/31/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sweeney, Patrick, Gillett, Don
• Primary Examiner(s): Brier, Jeffery A
• Assistant Examiner(s): WILLS, DIANE M
• Application Number:
  US13/599,263
• Publication Number:
  US 20130321410A1
• Time in Patent Office: 845 Days
• Field of Search: None
• US Class Current: 345/420
• CPC Class Codes: G06T 15/04 Texture mapping
• CPC Class Codes: G06T 15/08 Volume rendering
• CPC Class Codes: G06T 15/205 Image-based rendering
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 2210/56 Particle system, point based geometry or rendering
• CPC Class Codes: H04N 13/117 the virtual viewpoint locations being selected by the viewers or determined by viewer tracking
• CPC Class Codes: H04N 13/194 Transmission of image signals
• CPC Class Codes: H04N 13/239 using two 2D image sensors having a relative position equal to or related to the interocular distance H04N13/243 takes precedence
• CPC Class Codes: H04N 13/243 using three or more 2D image sensors
• CPC Class Codes: H04N 13/246 Calibration of cameras
• CPC Class Codes: H04N 13/257 Colour aspects
• CPC Class Codes: H04N 7/142 Constructional details of the terminal equipment, e.g. arrangements of the camera and the display
• CPC Class Codes: H04N 7/15 Conference systems
• CPC Class Codes: H04N 7/157 defining a virtual conference space and using avatars or agents computer conference optimisation or adaptation H04L12/1827
• CPC Class Codes: H04R 2227/005 Audio distribution systems for home, i.e. multi-room use
• CPC Class Codes: H04S 2400/15 Aspects of sound capture and related signal processing for recording or reproduction

Abstract

Video of a scene is generated and presented to a user. A stream of mesh models of the scene and a corresponding stream of mesh texture maps are generated from one or more streams of sensor data that represent the scene. Each of the mesh models includes a collection of faces, and each of the mesh texture maps defines texture data for one or more points on the faces. Each of the mesh models is broken down into convex sections. Each of the convex sections is surrounded with a three-dimensional hull. The texture data that is associated with each of the faces in the convex section is projected onto the three-dimensional hull, and a hull texture map for the convex section is produced.

Claims

1. A computer-implemented process for generating a video of a scene, comprising:

using a computing device to perform the following process actions;

inputting one or more streams of sensor data that represent the scene; and

generating scene proxies from said streams of sensor data, said generation comprising the actions of;

generating a stream of mesh models of the scene and a corresponding stream of mesh texture maps from said streams of sensor data, each of the mesh models comprising a collection of vertices and a collection of polygonal faces that are formed by the vertices, each of the mesh texture maps defining texture data for one or more points on each of the polygonal faces, and

for each of the mesh models, breaking down the mesh model into one or more convex sections, and for each of the convex sections of the mesh model, defining a three-dimensional (3D) hull that surrounds the convex section, surrounding the convex section with the 3D hull, and projecting the texture data that is associated with each of the polygonal faces in the convex section onto the 3D hull, said projection producing a hull texture map for the convex section.

2. The process of claim 1, wherein the process action of breaking down the mesh model into one or more convex sections comprises the actions of:

(a) arbitrarily selecting one of the vertices in the mesh model;

(b) assigning said arbitrarily selected one of the vertices to be an initial element of a set of candidate vertices;

(c) computing a convex hull for the set of candidate vertices;

(d) computing an error metric for the convex hull;

(e) whenever the error metric does not exceed a prescribed threshold,

selecting a prescribed number of other vertices in the mesh model that are not in the set of candidate vertices, and are not assigned to a convex section of the mesh model, and are directly connected to one of the candidate vertices,

adding said selected other vertices to the set of candidate vertices, and

repeating actions (c)-(e);

(f) whenever the error metric exceeds the prescribed threshold, assigning the vertices that are bounded by the convex hull to be a convex section of the mesh model; and

(g) whenever there are vertices in the mesh model that are not assigned to a convex section of the mesh model,

arbitrarily selecting one of the vertices in the mesh model that is not assigned to a convex section of the mesh model, and

repeating actions (b)-(g).

3. The process of claim 2, wherein the process action of computing an error metric for the convex hull comprises the actions of:

computing a shortest distance from the convex hull to each of the vertices that are inside the convex hull, said computation producing a set of vertex-to-hull distances;

determining the largest vertex-to-hull distance in said set; and

setting the error metric equal to said largest vertex-to-hull distance.

4. The process of claim 2, wherein the process action of computing an error metric for the convex hull comprises the actions of:

computing a shortest distance from the convex hull to each of the vertices that are inside the convex hull, said computation producing a set of vertex-to-hull distances;

computing an average of the vertex-to-hull distances in said set; and

setting the error metric equal to said average.

5. The process of claim 2, wherein the prescribed number is one.

6. The process of claim 2, wherein the prescribed number is greater than one.

7. The process of claim 1, wherein each of the convex sections of each of the mesh models comprises a plurality of vertices, and the process action of defining a 3D hull that surrounds the convex section comprises the actions of:

using a principal component analysis procedure to identify a major axis of the vertices that are in the convex section, and also identify two minor axes of said vertices; and

defining a 3D hull that surrounds said vertices based on the major and two minor axes of said vertices.

8. The process of claim 1, wherein the 3D hull comprises a sphere.

9. The process of claim 1, wherein the 3D hull comprises an ellipsoid.

10. The process of claim 1, wherein the 3D hull comprises a cube.

11. The process of claim 1, wherein the 3D hull comprises a rectangular cuboid.

12. The process of claim 1, wherein the texture data comprises one or more of:

color data, or specular highlight data, or transparency data, or reflection data, or shadowing data.

13. The process of claim 1, wherein the one or more streams of sensor data comprise a single stream of sensor data which represents the scene from a single geometric perspective, and the video being generated is a single viewpoint video.

14. The process of claim 1, wherein the one or more streams of sensor data comprise a plurality of streams of sensor data each of which represents the scene from a different geometric perspective, and the video being generated is a free viewpoint video.

15. The process of claim 1, wherein the process action of projecting the texture data that is associated with each of the polygonal faces in the convex section onto the 3D hull comprises the actions of:

for each of the faces in the convex section,

projecting the one or more points on the face for which texture data is defined along a normal to the face and onto the 3D hull, and

for each of the projected points on the 3D hull,

entering data into the hull texture map for the convex section that associates the projected point on the 3D hull with the texture data that is defined for the point on the face that corresponds to said projected point, and

entering data into said hull texture map that associates said projected point with the normal along which said projected point was projected.

16. The process of claim 1, further comprising an action of storing the scene proxies, said storing comprising the actions of:

for each of the convex sections of each of the mesh models,

storing the portion of the mesh model that is in the convex section,

storing a mathematical equation describing the 3D hull that surrounds the convex section,

storing data specifying the size of said 3D hull,

storing data specifying the position of said 3D hull in relation to said portion of the mesh model, and

storing the hull texture map for the convex section.

17. The process of claim 1, further comprising an action of distributing the scene proxies to an end user who either is, or will be, viewing the video on another computing device which is connected to a data communication network, said distribution comprising the actions of:

for each of the convex sections of each of the mesh models,

transmitting the portion of the mesh model that is in the convex section over the network to said other computing device,

transmitting a mathematical equation describing the 3D hull that surrounds the convex section over the network to said other computing device,

transmitting data specifying the size of said 3D hull over the network to said other computing device,

transmitting data specifying the position of said 3D hull in relation to said portion of the mesh model over the network to said other computing device, and

transmitting the hull texture map for the convex section over the network to said other computing device.

18. A computer-implemented process for presenting a video of a scene to a user, comprising:

using a computing device to perform the following process actions;

inputting scene proxies, said scene proxies comprising;

a stream of mesh models of the scene, each of the mesh models comprising a collection of polygonal faces, each of the mesh models being broken down into one or more convex sections, and

for each of the convex sections of each of the mesh models, a mathematical equation describing a three-dimensional (3D) hull that surrounds the convex section, data specifying the size of said 3D hull, data specifying the position of said 3D hull in relation to the portion of the mesh model that is in the convex section, and a hull texture map for the convex section, said map comprising data defining a plurality of points on said 3D hull, and data for each of said points that associates the point with texture data and also associates the point with a normal which defines a direction from one of said faces to said 3D hull;

rendering images of the scene from the scene proxies, said rendering comprising the actions of;

for each of the convex sections of each of the mesh models,

rendering the portion of the mesh model that is in the convex section,

using the mathematical equation describing a 3D hull that surrounds the convex section, the data specifying the size of said 3D hull, and the data specifying the position of said 3D hull in relation to said portion of the mesh model to surround the convex section with said 3D hull, and

for each of the points that is listed in the hull texture map for the convex section, projecting the point along the normal that is associated with the point and onto the portion of the mesh model that is in the convex section, and assigning the texture data that is associated with the point to the corresponding projected point on said portion of the mesh model; and

displaying the images of the scene.

19. The process of claim 18, wherein the video being presented comprises one of:

asynchronous single viewpoint video;

or

asynchronous free viewpoint video;

or

unidirectional live single viewpoint video;

or

unidirectional live free viewpoint video;

or

bidirectional live single viewpoint video;

or

bidirectional live free viewpoint video.

20. A system for generating a video of a scene, comprising:

a computing device; and

a computer program having program modules executable by the computing device, the computing device being directed by the program modules of the computer program to,

input one or more streams of sensor data that represent the scene, and

generate scene proxies from said streams of sensor data, said generation comprising,

generating a stream of mesh models of the scene and a corresponding stream of mesh texture maps from said streams of sensor data, and

for each of the mesh models, breaking down the mesh model into one or more convex sections, and for each of the convex sections of the mesh model, defining a three-dimensional (3D) hull that surrounds the convex section, and projecting the texture data that is associated with each of the polygonal faces in the convex section onto the 3D hull, said projection producing a hull texture map for the convex section.