Smoothing and robust normal estimation for 3D point clouds

• US 9,767,598 B2
• Filed: 08/03/2012
• Issued: 09/19/2017
• Est. Priority Date: 05/31/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Winder, Simon A. J.
• Primary Examiner(s): Liu, Zhengxi
• Assistant Examiner(s): Yang, Yi
• Application Number:
  US13/566,796
• Publication Number:
  US 20130321393A1
• Time in Patent Office: 1,873 Days
• Field of Search: 345419, 345611, 345687
• 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 17/05 Geographic models
• 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

A “Point Cloud Smoother” provides various techniques for refining a 3D point cloud or other 3D input model to generate a smoothed and denoised 3D output model. Smoothing and denoising is achieved, in part, by robustly fitting planes to a neighborhood of points around each point of the input model and using those planes to estimate new points and corresponding normals of the 3D output model. These techniques are useful for a number of purposes, including, but not limited to, free viewpoint video (FVV), which, when combined with the smoothing techniques enabled by the Point Cloud Smoother, allows 3D data of videos or images to be denoised and then rendered and viewed from any desired viewpoint that is supported by the input data.

Claims

1. A computer-implemented process for smoothing 3D models, comprising using a computer to perform process actions for:

receiving a set of 3D input points representing a 3D input model;

using the set of 3D input points to determine a set of the nearest j neighbors of each input point;

for each input point, fitting a corresponding plane in 3D space to the point and its set of nearest j neighbors;

creating a set of 3D output points by projecting each input point onto its corresponding plane;

using the set of 3D output points to determine a set of the nearest k neighbors of each output point;

for each output point, fitting a corresponding plane in 3D space to the point and its set of nearest k neighbors;

for each output point, computing a corresponding surface normal from the corresponding plane; and

wherein the set of 3D output points and corresponding surface normals represent a smoothed 3D output model.

2. The computer-implemented process of claim 1 further comprising constructing a corresponding 3D index tree from any set of 3D points.

3. The computer-implemented process of claim 2 wherein the set of nearest neighbors of any point is determined using the corresponding 3D index tree.

4. The computer-implemented process of claim 1 wherein a robust estimator is used to fit each 3D plane to each point and its set of nearest neighbors.

5. The computer-implemented process of claim 1 wherein projecting each input point onto its corresponding 3D plane further comprises projecting each input point along a computed normal of the corresponding plane to lie on the surface of that plane.

6. The computer-implemented process of claim 1 wherein the number of nearest neighbors for any point is an adjustable parameter.

7. The computer-implemented process of claim 1 further comprising reversing a direction of the corresponding surface normal of any output point whenever that direction does not point in the same relative direction as the corresponding surface normals of each point in the set of nearest neighbors.

8. The computer-implemented process of claim 1 further comprising one or more iterations of designating the original set of 3D output points as a new set of 3D input points, and repeating the processes of claim 1 using the new set of 3D input points to create a new set of 3D output points and corresponding surface normals.

9. A system for smoothing 3D point clouds, comprising:

a general purpose computing device; and

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to;

receive a 3D point cloud comprising a set of 3D input points;

determine a set of the nearest neighbors of each 3D point;

fit a plane in 3D space to each 3D point and its set of nearest neighbors;

create a set of 3D output points by projecting each input point onto its corresponding plane;

determine sets of nearest neighbors for each output point;

fit planes to each output point and its set of nearest neighbors;

compute a surface normal for each output point from the corresponding plane; and

wherein the set of 3D output points and corresponding surface normals represent a smoothed 3D point cloud.

10. The system of claim 9 further comprising generating a 3D object model from the smoothed 3D point cloud.

11. The system of claim 9 wherein a robust estimator is used to fit each 3D plane to each point and its set of nearest neighbors.

12. The system of claim 9 wherein projecting each input point onto its corresponding 3D plane further comprises projecting each input point along a computed normal of the corresponding plane to lie on the surface of that plane.

13. The system of claim 9 wherein the number of nearest neighbors for any point is an adjustable parameter.

14. The system of claim 9 further comprising reversing a direction of the corresponding surface normal of one or more output points whenever that direction does not point in the same relative direction as the corresponding surface normals of a set of neighboring points.

15. The system of claim 9 further comprising one or more iterations of designating the smoothed 3D point cloud as a new set of 3D input points, and repeating the processes of claim 9 using the new set of 3D input points to create a new smoothed 3D point cloud.

16. A computer-readable storage device having computer executable instructions stored therein for smoothing 3D point-based models, said instructions causing a computing device to execute a method comprising:

receiving a set of 3D input points representing a 3D input model;

using the set of 3D input points to determine a set of the nearest j neighbors of each input point;

for each input point, fitting a corresponding plane in 3D space to the point and its set of nearest j neighbors;

creating a set of output 3D points by projecting each input point onto its corresponding plane along a surface normal of that plane;

using the set of 3D output points to determine a set of the nearest k neighbors of each output point;

for each output point, fitting a corresponding plane in 3D space to the point and its set of nearest k neighbors;

for each output point, computing a corresponding surface normal from the corresponding plane; and

wherein the set of 3D output points and corresponding surface normals represent a smoothed 3D output model.

17. The computer-readable storage device of claim 16 further comprising constructing a corresponding 3D index tree from any set of 3D points and wherein the set of nearest neighbors of any point is determined using the corresponding 3D index tree.

18. The computer-readable storage device of claim 16 wherein a robust estimator is used to fit each 3D plane to each point and its set of nearest neighbors.

19. The computer-readable storage device of claim 16 wherein the number of nearest neighbors for any point is an adjustable parameter.

20. The computer-readable storage device of claim 16 further comprising reversing a direction of the corresponding surface normal of any output point whenever that direction does not point in the same relative direction as the corresponding surface normals of each point in the set of nearest neighbors.