Random sample consensus for groups of data

Patent metadata

Field	Value
Publication number	US-10755139-B2
Application number	US-201715494106-A
Country	US
Kind code	B2
Filing date	Apr 21, 2017
Priority date	Aug 15, 2008
Publication date	Aug 25, 2020
Grant date	Aug 25, 2020

Abstract

In one embodiment, a computer accessible storage medium stores a plurality of instructions which, when executed: group a set of reconstructed three dimensional (3D) points derived from image data into a plurality of groups based on one or more attributes of the 3D points; select one or more groups from the plurality of groups; and sample data from the selected groups, wherein the sampled data is input to a consensus estimator to generate a model that describes a 3D model of a scene captured by the image data. Other embodiments may bias sampling into a consensus estimator for any data set, based on relative quality of the data set.

First claim

What is claimed is:

1. A method for reconstructing a three-dimensional (3D) model of a scene based on a consensus estimate of a model parameter from captured images of the scene by at least one computing device, the method comprising:
detecting, by the at least one computing device, a first set of features in a first image of the scene and a second set of features in a second image of the scene;
determining, by the at least one computing device, potential correspondences between the first set of features and the second set of features;
generating, by the at least one computing device, the consensus estimate of the model parameter by:
forming groups of the potential correspondences based on at least one image attribute;
forming group configurations of the groups, the group configurations including configurations having one group, configurations having a maximum number of groups, and configurations having integer numbers of groups between one and the maximum number of groups;
generating a plurality of scores, each score in which each said score based on the potential correspondences in a respective group configuration;
selecting a configuration set that includes each of the group configurations having a same number of groups;
sampling the potential correspondences of at least one of the group configurations within the configuration set based on the plurality of scores such that at least one correspondence has been sampled from each of the groups in the at least one group configuration; and
determining the consensus estimate of the model parameter based on the potential correspondences sampled; and

reconstructing, by the at least one computing device, the 3D model of the scene based at least in part on the consensus estimate of the model parameter.

2. A method as described in claim 1 , wherein the score is based on a number of the potential correspondences in the respective group configuration.

3. A method as described in claim 2 , wherein the group configurations having larger numbers of the potential correspondences are scored more favorably.

4. A method as described in claim 1 , wherein the score is based on a ratio of inlier correspondences to outlier correspondences of the potential correspondences in the respective group configuration.

5. A method as described in claim 4 , wherein the group configurations having higher ratios of the inlier correspondences to the outlier correspondences are scored more favorably.

6. A method as described in claim 1 , further comprising:
sampling the potential correspondences of at least one additional group configuration within at least one additional configuration set based on the plurality of scores; and
determining the consensus estimate of the model parameter based on the potential correspondences sampled from the at least one group configuration and the at least one additional group configuration.

7. A method as described in claim 1 , wherein the features include at least one of points, lines, curves, or surfaces.

8. A method as described in claim 1 , wherein the consensus estimate of the model parameter is determined with RANSAC from the potential correspondences sampled.

9. A method as described in claim 1 , further comprising generating a fit score for the consensus estimate of the model parameter that indicates a fit of the consensus estimate of the model parameter to all the potential correspondences.

10. A method as described in claim 9 , further comprising, responsive to a determination that the fit score does not indicate a suitable fit of the consensus estimate of the model parameter to all the potential correspondences:
sampling the potential correspondences of at least one additional group configuration; and
updating the consensus estimate of the model parameter based on the potential correspondences sampled from the at least one group configuration and the at least one additional group configuration.

11. A method as described in claim 6 , wherein the configuration set corresponds to the group configurations having one group and the additional configuration set corresponds to the group configurations having two groups.

12. A system comprising:
at least one processor; and
memory having stored thereon computer-readable instructions that are executable by the at least one processor to perform operations for reconstructing a three-dimensional (3D) model of a scene based on a consensus estimate of a model parameter from captured sensor data of the scene, the operations comprising:
detecting a first set of features in a first set of sensor data of the scene and a second set of features in a second set of sensor data of the scene;
determining potential correspondences between the first set of features and the second set of features;
generating the consensus estimate of the model parameter by:
forming groups of the potential correspondences based on at least one attribute described by the captured sensor data;
generating a plurality of scores, each score based on the potential correspondences in a respective group;
sampling the potential correspondences of at least one of the groups based on the plurality of scores;
determining the consensus estimate of the model parameter based on the potential correspondences sampled;
verifying the consensus estimate of the model parameter by generating a fit score for the consensus estimate of the model parameter that indicates a fit of the consensus estimate of the model parameter to all the potential correspondences regardless of whether the potential correspondences are included in the at least one group; and
sampling the potential correspondences of at least one additional group of the groups responsive to a determination that the consensus estimate is inaccurate according to the fit score; and

reconstructing the 3D model of the scene based at least in part on the consensus estimate of the model parameter.

13. A system as described in claim 12 , wherein the score is based on a number of the potential correspondences in the respective group.

14. A system as described in claim 13 , wherein the groups having larger numbers of the potential correspondences are scored more favorably.

15. A system as described in claim 12 , wherein the score is based on a ratio of inlier correspondences to outlier correspondences of the potential correspondences in the respective group.

16. A system as described in claim 15 , wherein the groups having higher ratios of the inlier correspondences to the outlier correspondences are scored more favorably.

17. A system as described in claim 12 , wherein:
the captured sensor data of the scene comprises images of the scene;
the first set of sensor data comprises a first image of the scene;
the second set of sensor data comprises a second image of the scene; and
the at least one attribute described by the captured sensor data comprises at least one image attribute.

18. A system as described in claim 12 , wherein the operations further comprise
updating the consensus estimate of the model parameter based on the potential correspondences sampled from the at least one group and the at least one additional group.

19. A method for reconstructing a three-dimensional (3D) model of an object in a scene based on a consensus estimate of a model parameter from captured video of the scene by at least one computing device, the method comprising:
identifying, by the at least one computing device, a first and second image of the scene in a sequence of images forming the captured video;
detecting, by the at

Assignees

• Adobe Inc

Inventors

• Jin Hailin
• Ni Kai

Classifications

• G06V20/647 Primary

  by matching two-dimensional images to three-dimensional objects · CPC title

• G06V10/757

  Matching configurations of points or features · CPC title

• G06F18/2413

  based on distances to training or reference patterns · CPC title

• G06K9/6211 Primary

  Physics · mapped topic

• G06K9/627

  Physics · mapped topic