Match, Expand, and Filter Technique for Multi-View Stereopsis

Abstract

In accordance with one or more aspects of a match, expand, and filter technique for multi-view stereopsis, features across multiple images of an object are matched to obtain a sparse set of patches for the object. The sparse set of patches is expanded to obtain a dense set of patches for the object, and the dense set of patches is filtered to remove erroneous patches. Optionally, reconstructed patches can be converted into 3D mesh models.

What is claimed is: 
     
         1 - 20 . (canceled) 
     
     
         21 . A method comprising:
 matching features across multiple images of an object to obtain a sparse set of patches for the object;   expanding the sparse set of patches to obtain a dense set of patches for the object, wherein the expanding is based on images of the multiple images that have photometric discrepancy scores with a reference image that are less than a threshold;   filtering the dense set of patches to remove false matches; and   repeating the expanding and filtering one or more times, each time loosening the threshold and expanding the dense set of patches obtained by the previously performed filtering.   
     
     
         22 . A method as recited in  claim 21 , the filtering comprising filtering the dense set of patches to remove false matches based on visibility information. 
     
     
         23 . A method as recited in  claim 21 , the one or more times comprising multiple times. 
     
     
         24 . A method as recited in  claim 21 , further comprising outputting the filtered dense set of patches as a 3-dimensional model of the object. 
     
     
         25 . A method as recited in  claim 21 , further comprising generating, based on the filtered dense set of patches after repeating the expanding and the filtering one or more times, a set of surface meshes for the object. 
     
     
         26 . A method as recited in  claim 21 , each patch being defined by a center c(p), a unit normal vector n(p) oriented toward a camera observing the patch, and a reference image R(p) in which the patch is visible. 
     
     
         27 . A method as recited in  claim 21 , further comprising:
 overlaying a grid of cells on each of the multiple images;   associating with each cell a set of patches that project in the cell; and   wherein expanding the sparse set of patches comprises expanding the sparse set of patches based at least in part on the sets of patches that project in the cells.   
     
     
         28 . A method as recited in  claim 21 , further comprising:
 overlaying a grid of multiple cells on each of the multiple images; and   wherein the expanding comprises expanding the sparse set of patches to obtain the dense set of patches in which one or more patches are reconstructed for each of the multiple cells.   
     
     
         29 . A method as recited in  claim 21 , further comprising:
 overlaying a grid of multiple cells on each of the multiple images; and   wherein the expanding comprises expanding the sparse set of patches by generating, for a patch in the sparse set of patches that projects in a cell, a new patch in each empty cell neighboring the cell.   
     
     
         30 . A method as recited in  claim 21 , the filtering comprising removing one or more patches that lie outside a surface of the object, and removing one or more patches that lie inside the surface of the object. 
     
     
         31 . A method as recited in  claim 21 , the expanding including using segmentation information to identify portions of the multiple images that are background, and ignoring during the expanding cells included in portions of the multiple images that are background, the cells being included in a grid of cells overlaying each of the multiple images. 
     
     
         32 . A method as recited in  claim 21 , the filtering comprising, for each of one or more particular patches in the dense set of patches:
 identifying a set of patches that is inconsistent in visibility information with the particular patch, an additional patch being inconsistent in visibility information with the particular patch if the additional patch and the particular patch are not neighbors but are stored in a same cell in one of the multiple images; and   where p represents the particular patch, V*(p) represents images of the multiple images having photometric discrepancy scores with the reference image that are less than the threshold, g*(p) represents the photometric discrepancy for the particular patch, U represents the set of patches that is inconsistent in visibility information with the particular patch, removing the patch from the dense set of patches if the following inequality holds:   
       
         
           
             
               
                 
                    
                   
                     
                       V 
                       * 
                     
                      
                     
                       ( 
                       p 
                       ) 
                     
                   
                    
                 
                  
                 
                   ( 
                   
                     1 
                     - 
                     
                       
                         g 
                         * 
                       
                        
                       
                         ( 
                         p 
                         ) 
                       
                     
                   
                   ) 
                 
               
               < 
               
                 
                   
                     ∑ 
                     
                       
                         p 
                         i 
                       
                       ∈ 
                       U 
                     
                   
                    
                   1 
                 
                 - 
                 
                   
                     
                       g 
                       * 
                     
                      
                     
                       ( 
                       
                         p 
                         i 
                       
                       ) 
                     
                   
                   . 
                 
               
             
           
         
       
     
     
         33 . A method as recited in  claim 21 , the filtering comprising, for each of one or more patches in the dense set of patches:
 determining, for a set of images of the multiple images having photometric discrepancy scores with the reference image that are less than the threshold, whether there are at least a threshold number of images in the set of images where the patch is visible; and   removing the patch from the dense set of patches if there are not at least the threshold number of images in the set of images where the patch is visible.   
     
     
         34 . A method as recited in  claim 21 , the filtering comprising, for each of one or more patches in the dense set of patches:
 identifying, from ones of the multiple images in which the patch is visible, a set of patches that includes patches lying in a cell of the patch as well as in cells adjacent to the cell of the patch; and   removing the patch from the dense set of patches if a proportion of patches in the set of patches that are neighbors is less than a threshold amount.   
     
     
         35 . A method as recited in  claim 34 , in which p represents a first patch in the set of patches, c(p) represents the center of the first patch, n(p) represents a unit normal vector of the first patch, p′ represents a second patch in the set of patches, c(p) represents the center of the first patch, c(p′) represents the center of the second patch, n(p′) represents a unit normal vector of the second patch, ρ 1  represents an additional threshold value, and further comprising determining that the first patch and the second patch are neighbors if:
   |( c ( p )− c ( p ′))· n ( p )|+|( c ( p )− c ( p ′))· n ( p ′)|<2ρ 1 .
 
 
     
     
         36 . One or more computer readable media devices having stored thereon multiple instructions that, when executed by one or more processors, cause the one or more processors to:
 match features in multiple images of an object to obtain a sparse set of patches for the object;   expand the sparse set of patches to include additional patches, resulting in a dense set of patches for the object, wherein the expansion is based on images of the multiple images that have pairwise photometric discrepancy scores with a reference image that are less than a threshold;   filter the dense set of patches to remove erroneous patches; and   perform one or more iterations of the expanding and filtering, each iteration expanding, with a loosened threshold, the dense set of patches obtained by the previously performed filtering.   
     
     
         37 . One or more computer readable media devices as recited in  claim 36 , wherein to filter the dense set of patches is to remove erroneous patches based on visibility information. 
     
     
         38 . One or more computer readable media devices as recited in  claim 36 , the one or more iterations comprising multiple iterations. 
     
     
         39 . One or more computer readable media devices as recited in  claim 36 , the instructions further causing the one or more processors to output the filtered dense set of patches as a 3-dimensional model of the object. 
     
     
         40 . One or more computer readable media devices as recited in  claim 36 , the instructions further causing the one or more processors to generate, based on the filtered dense set of patches after performing the one or more iterations of the expanding and filtering, a set of surface meshes for the object. 
     
     
         41 . One or more computer readable media devices as recited in  claim 36 , the instructions further causing the one or more processors to:
 overlay a grid of multiple cells on each of the multiple images; and   wherein to expand the sparse set of patches is to expand the sparse set of patches by generating, for a patch in the sparse set of patches that projects in a cell, a new patch in each empty cell neighboring the cell.   
     
     
         42 . One or more computer readable media devices as recited in  claim 36 , wherein to filter the dense set of patches is to remove one or more patches that lie outside a surface of the object, and remove one or more patches that lie inside the surface of the object. 
     
     
         43 . A device comprising:
 a matching module to match features across multiple images of an object in order to obtain a sparse set of patches for the object;   an expansion module to:
 expand, on a first of multiple iterations, the sparse set of patches to obtain a dense set of patches for the object, wherein the expansion on the first iteration is based on images of the multiple images that have photometric discrepancy scores with a reference image that are less than a threshold, and 
 expand, on subsequent iterations of the multiple iterations, a filtered dense set of patches obtained from filtering a previous dense set of patches for the object, wherein the expansion on the subsequent iterations is based on images of the multiple images that have photometric discrepancy scores with the reference image that are less than an increased threshold, each increased threshold being loosened from the threshold used in the previous iteration of the multiple iterations; and 
   a filtering module to filter, on each of the multiple iterations, the dense set of patches to remove false matches prior to expansion of the dense set of patches in the subsequent iteration of the multiple iterations.   
     
     
         44 . A device as recited in  claim 43 , wherein the filter module is to filter the dense set of patches to remove erroneous patches based on visibility information. 
     
     
         45 . A device as recited in  claim 43 , wherein the device is to generate a 3-dimensional model of the object. 
     
     
         46 . A device as recited in  claim 43 , wherein the device is to generate, based on the filtered dense set of patches after expanding and filtering in the multiple iterations, a set of surface meshes for the object. 
     
     
         47 . A device as recited in  claim 43 , wherein the filtering module is to filter the dense set of patches to remove one or more patches that lie outside a surface of the object, and remove one or more patches that lie inside the surface of the object.