System and method for constructing a 3D scene model from an image

• US 20100085358A1
• Filed: 10/08/2008
• Published: 04/08/2010
• Est. Priority Date: 10/08/2008
• Status: Active Grant

• Current Assignee: Strider Labs, Inc.
• Original Assignee: Strider Labs, Inc.
• Inventors: Wegbreit, Eliot Leonard, Hager, Gregory D.
• Granted Patent: US 10,650,608 B2
• Time in Patent Office: Days
• US Class Current: 345/420
• CPC Class Codes: G06T 19/20 Editing of 3D images, e.g. changing shapes or colours, aligning objects or positioning parts
• CPC Class Codes: G06T 2219/2021 Shape modification

Abstract

A system and method for constructing a 3D scene model comprising 3D objects and representing a scene, based upon a prior 3D scene model. The method comprises the steps of acquiring an image of the scene; initializing the computed 3D scene model to the prior 3D scene model; and modifying the computed 3D scene model to be consistent with the image. The step of modifying the computed 3D scene models consists of the sub-steps of comparing data of the image with objects of the 3D scene model, resulting in associated data and unassociated data; using the unassociated data to compute new objects that are not in the 3D scene model and adding the new objects to the 3D scene model; and using the associated data to detect objects in the prior 3D scene model that are absent and removing the absent objects from the 3D scene model. The present invention may also be used to construct multiple alternative 3D scene models.

Claims

1. A method for computing a 3D scene model comprising 3D objects and representing a scene, based upon a prior 3D scene model, the method comprising the steps of:

(a) acquiring an image of the scene;

(b) initializing the 3D scene model to the prior 3D scene model; and

(c) modifying the 3D scene model to be consistent with the image, by;

(i) comparing data of the image with objects of the 3D scene model, resulting in associated data and unassociated data;

(ii) using the unassociated data to compute new objects that are not in the prior 3D scene model and adding the new objects to the 3D scene model; and

(iii) using the associated data to detect objects in the prior 3D scene model that are absent and removing the absent objects from the 3D scene model.

2. The method of claim 1, wherein the image of the scene is a range image, wherein each object p of the 3D scene model has a signed distance function, and comparing data of the image with objects of the 3D scene model further comprises for each object p, finding locations in the image such that the value of the signed distance function of the object p applied to the location is less than or equal to a specified tolerance, and the value of the distance function for all other objects q applied to the location is not less than the value of p'"'"'s distance function, the data points of these locations being associated data of the object p, and the data points of any locations not associated with any object p of the 3D scene model being unassociated data.

3. The method of claim 2, wherein using the unassociated data to compute new objects further comprises optimizing objective functions containing error terms whose values are computed from data modeling functions that are zero on the surface of an object.

4. The method of claim 3, wherein the objective functions include an exponential of an error term.

5. The method of claim 1, wherein the image of the scene is a range image and using the associated data to detect absent objects further comprises:

(a) for each object p in the 3D scene model, computing a first number n of data points of the image such that the signed distance function of the object applied to the data point is less than a specified tolerance;

(b) computing a second number N of locations of the object visible in the result of rendering the 3D scene model; and

(c) if n is less than a specified function of N for the object, subjecting the object p to additional confirmation to determine whether the object p is absent from the scene.

6. The method of claim 5, wherein subjecting the object p to additional confirmation further comprises determining that there is no other object that may be computed from the image that occludes the object p.

7. The method of claim 6, wherein the step of modifying the computed 3D scene model to be consistent with the image further comprises using the associated data and the 3D scene model to adjust pose and other properties of objects existing in the 3D scene model.

8. The method of claim 7 where the step of determining that there is no other object that may be computed from the image that occludes the object p further comprises processing the object p only after all new objects have been computed and added to the 3D scene model and all pose adjustments made to existing objects in the 3D scene model.

9. The method of claim 1, wherein comparing data of the image with objects of the 3D scene model further comprises:

(a) rendering each object p of the 3D scene model, resulting in a rendered image for p; and

(b) finding locations in the image such that a first difference between the value of the image data at a location and the value of the rendered image for object p at the location is less than or equal to a tolerance and for all other objects q, a second difference between the value of the image data at the location and the value of the rendered image for object q at the location is not less than the first difference, the data points of these locations being associated data of the object p, and the data points of any locations not associated with any object of the 3D scene model being unassociated data.

10. The method of claim 1, wherein using the associated data to detect absent objects further comprises:

(a) rendering the 3D scene model, resulting in a synthetic rendering;

(b) using the synthetic rendering to compute synthetic data associated with objects;

(c) comparing the associated data with the synthetic data associated with objects to find objects in the 3D scene model that do not appear in the image; and

(d) subjecting the objects in the 3D scene model that do not appear in the image to additional confirmation to determine whether the object is absent from the scene.

11. The method of claim 10, wherein subjecting objects to additional confirmation further comprises determining that for each object p that does not appear in the image, there is no other object that may be computed from the image which occludes the object p.

12. The method of claim 11, where the image is range data and the step of determining that, for each object p that does not appear in the image, there is no second object that may be computed from the image that occludes the object p further comprises:

(a) processing the objects in the 3D scene model and the image data in front to back order;

(b) finding any new objects and adding the new objects to the 3D scene mode;

(c) adjusting, in the 3D scene model, the poses of any objects that have moved;

(d) after all objects in the 3D scene model and image data in front of the object p have been processed, comparing data of the image with the object p in the 3D scene model, resulting in image data associated with object p;

(e) rendering the object p in the 3D scene model, resulting in synthetic data for object p;

(f) comparing the image data associated with object p to the synthetic data for object p to determine if the object p appears in the image.

13. The method of claim 1, wherein the step of modifying the computed 3D scene model to be consistent with the image further comprises using the associated data and the 3D scene model to adjust pose and other properties of objects existing in the 3D scene model.

14. The method of claim 1, wherein the step of modifying the computed 3D scene model to be consistent with the image further comprises:

(a) clustering the unassociated data into data clusters;

(b) using the data clusters to compute new objects; and

(c) adding the new objects to the 3D scene model.

15. The method of claim 1, wherein the step of computing new objects further comprises requiring that a new object be in contact with one or more supporting objects.

16. The method of claim 1, wherein the step of computing new objects further comprises requiring that a new object not be in collision with any other object.

17. The method of claim 1, wherein comparing data of the image with objects of the 3D scene model further comprises:

(a) processing the image to detect image features;

(b) processing each object p in the 3D scene model to detect model features of p that would be visible;

(c) associating the image features to model features of p when they match at the same or nearby locations and have no better match with model features from any other object q of the 3D scene model;

(d) taking the image features associated with model features of object p as data associated with object p.

18. The method of claim 1, wherein the step of using the unassociated data to compute new objects further comprises:

(a) finding features in the unassociated data;

(b) matching the features in the unassociated data to features in a library of object models;

(c) using the features in the library of object models to identify objects in the library of object models.

19. The method of claim 1, wherein the step of using the associated data to detect absent objects further comprises:

(a) computing synthetic features from the 3D scene model;

(b) comparing features of the associated data to the synthetic features to find objects in the 3D scene model that do not appear in the image;

(c) subjecting the objects in the 3D scene model that do not appear in the image to additional confirmation to determine whether the objects are absent from the scene.

20. A method for computing alternative 3D scene models, comprising 3D objects and representing a scene, based upon a set of possible prior 3D scene models, the method comprising the steps of

(a) acquiring an image of the scene;

(b) initializing the set of alternative 3D scene models to the set of possible prior 3D scene models;

(c) determining differences between one or more of the alternative 3D scene models and the image by;

(i) comparing data of the image with objects of the 3D scene model, resulting in associated data and unassociated data;

(ii) using the unassociated data to compute possible new objects; and

(iii) using the associated data to detect possible absent objects; and

(d) modifying one or more of the alternative 3D scene models by adding one or more possible new objects, removing one or more possible absent objects, or both, to compute one or more alternative 3D scene models.

21. The method of claim 20, wherein modifying one or more of the alternative 3D scene models further comprises using the likelihood of a 3D scene model to choose which possible new objects are added and which possible absent objects are removed.

22. The method of claim 21, wherein one or more of the alternative 3D scene models is selected as a preferred result based on the likelihood of the 3D scene model.

23. A computer readable storage medium having embodied thereon instructions for causing a computing device to execute a method for computing a 3D scene model comprising 3D objects and representing a scene, based upon a prior 3D scene model, the method comprising:

(a) acquiring an image of the scene;

(b) initializing the 3D scene model to the prior 3D scene model; and

(c) modifying the 3D scene model to be consistent with the image, by;

(i) comparing data of the image with objects of the 3D scene model, resulting in associated data and unassociated data;

(ii) using the unassociated data to compute new objects that are not in the prior 3D scene model and adding the new objects to the 3D scene model; and

(iii) using the associated data to detect objects in the prior 3D scene model that are absent and removing the absent objects from the 3D scene model.