Random Sample Consensus for Groups of Data

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.

1 . A method comprising:
 performing, by one or more computers:
 grouping data captured from one or more sensors into a plurality of groups based on one or more attributes of the data; 
 establishing a quality score for each group of the plurality of groups, wherein the quality score is indicative of the relative quality of the data in the group with respect to other ones of the plurality of groups, wherein data having a higher quality score is more likely to include inlier data than data having a lower quality score; 
 selecting, for a sampling process to fit a model to the data, one or more groups from the plurality of groups based on the quality scores, wherein the selected one or more groups includes one or more groups having the higher quality score; and 
 sampling data from the one or more selected groups, wherein the sampled data is input to a consensus estimator to generate a model that fits the data. 
   
     
     
         2 . The method as recited in  claim 1  wherein the data is captured by one or more sensors in a data acquisition system, and wherein the data is grouped according to which sensor measured the data. 
     
     
         3 . The method as recited in  claim 1  wherein the data is derived from image data captured by a camera in a three dimensional scene, and wherein the data is grouped according to which of a plurality of source images includes the data. 
     
     
         4 . The method as recited in  claim 1  wherein the data is derived from image data captured by a camera in a three dimensional scene, and wherein the data is grouped using one or more image segmentation techniques. 
     
     
         5 . The method as recited in  claim 4  wherein the image segmentation techniques comprise color segmentation. 
     
     
         6 . The method as recited in  claim 1  further comprising:
 biasing the sampling of data from the one or more selected groups. 
 
     
     
         7 . The method as recited in  claim 6  wherein the biasing comprises:
 limiting input data to the consensus estimator to the groups having higher quality scores for one or more initial iterations of the consensus estimator; and 
 including one or more additional groups of the plurality of groups in subsequent iterations of the consensus estimator. 
 
     
     
         8 . The method as recited in  claim 1  wherein the selecting one or more groups comprises:
 forming a plurality of group configurations, each group configuration comprising a set of one or more groups of the plurality of groups; 
 identifying a set of group configurations as a current configuration set; and 
 sampling a group configuration from the current configuration set. 
 
     
     
         9 . The method as recited in  claim 8  further comprising scoring a quality of data in each group configuration of the plurality of group configurations, and wherein the sampling of the current configuration set is biased toward the group configurations having the higher quality scores. 
     
     
         10 . A non-transitory computer accessible storage medium storing a plurality of instructions which, when executed on a computer:
 group data captured from one or more sensors into a plurality of groups based on one or more attributes of the data;   establish a quality score for each group of the plurality of groups, wherein the quality score is indicative of the relative quality of the data in the group with respect to other ones of the plurality of groups, wherein data having a higher quality score is more likely to include inlier data than data having a lower quality score;   select, for a sampling process to fit a model to the data, one or more groups from the plurality of groups based on the quality scores, wherein the selected one or more groups includes one or more groups having the higher quality score; and   sample data from the one or more selected groups, wherein the sampled data is input to a consensus estimator to generate a model that fits the data.   
     
     
         11 . The non-transitory computer accessible storage medium as recited in  claim 10  wherein the data is captured by one or more sensors in a data acquisition system, and wherein the data is grouped according to which sensor measured the data. 
     
     
         12 . The non-transitory computer accessible storage medium as recited in  claim 10  wherein the data is derived from image data captured by a camera in a three dimensional scene, and wherein the data is grouped according to which of a plurality of source images includes the data. 
     
     
         13 . The non-transitory computer accessible storage medium as recited in  claim 10  wherein the data is derived from image data captured by a camera in a three dimensional scene, and wherein the data is grouped using one or more image segmentation techniques. 
     
     
         14 . The non-transitory computer accessible storage medium as recited in  claim 13  wherein the image segmentation techniques comprise color segmentation. 
     
     
         15 . The non-transitory computer accessible storage medium as recited in  claim 10  wherein the plurality of instructions, when executed:
 bias the sampling of data from the one or more selected groups. 
 
     
     
         16 . The non-transitory computer accessible storage medium as recited in  claim 15  wherein the plurality of instructions which, when executed, bias the sampling comprises instructions which, when executed:
 limit input data to the consensus estimator to the groups having higher quality scores for one or more initial iterations of the consensus estimator; and 
 include one or more additional groups of the plurality of groups in subsequent iterations of the consensus estimator. 
 
     
     
         17 . The non-transitory computer accessible storage medium as recited in  claim 10  wherein the instructions which, when executed, select one or more groups comprises instructions which, when executed:
 form a plurality of group configurations, each group configuration comprising a set of one or more groups of the plurality of groups; 
 identify a set of group configurations as a current configuration set; and 
 sample a group configuration from current configuration set. 
 
     
     
         18 . The non-transitory computer accessible storage medium as recited in  claim 17  wherein the plurality of instructions, when executed score a quality of data in each group configuration of the plurality of group configurations, and wherein the plurality of instructions which, when executed, sample the current configuration set include instructions which, when executed, bias the sample toward the group configurations having the higher quality scores. 
     
     
         19 . A non-transitory computer accessible storage medium storing 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;   establish a quality score for each group of the plurality of groups, wherein the quality score is indicative of the relative quality of the 3D points in the group with respect to other ones of the plurality of groups, wherein data having a higher quality score is more likely to include inlier data than data having a lower quality score;   select, for a sampling process to fit a model to the data, one or more groups from the plurality of groups based on the quality scores, wherein the selected one or more groups includes one or more groups having the higher quality score; and   sample data from the one or more 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.   
     
     
         20 . The non-transitory computer accessible storage medium as recited in  claim 19  wherein the 3D model describes one or more structures in the scene. 
     
     
         21 . The non-transitory computer accessible storage medium as recited in  claim 19  wherein the 3D model describes a camera motion through the 3D scene. 
     
     
         22 . A computer-implemented method comprising:
 executing instructions on a specific apparatus so that binary digital electronic signals representing data captured from one or more sensors are grouped into a plurality of groups based on one or more attributes of the data;   executing instructions on the specific apparatus so that binary digital electronic signals representing a quality score for each group of the plurality of groups are established, wherein the quality score is indicative of the relative quality of the data in the group with respect to other ones of the plurality of groups, wherein data having a higher quality score is more likely to include inlier data than data having a lower quality score;   executing instructions on the specific apparatus so that binary digital electronic signals representing one or more groups from the plurality of groups are selected, for a sampling process to fit a model to the data, based on the quality scores, wherein the selected one or more groups includes one or more groups having the higher quality score;   executing instructions on the specific apparatus so that binary digital electronic signals representing data from the one or more selected groups are sampled, wherein the sampled data is input to a consensus estimator to generate a model that fits the data; and   storing the model in a memory location of the specific apparatus.