Face recognition and image search system using sparse feature vectors, compact binary vectors, and sub-linear search

Abstract

Systems and methods are provided for performing automated face recognition and comparison. An input image of a face may be received and cropped, and the image may be processed through a deep neural network (DNN) to produce a k-dimensional feature vector. The k-dimensional feature vector may be converted to a k-dimensional binary vector by transforming each value in the vector to either 1 or 0. To search for nearest matches of the image in a database of gallery images of faces, the system may compare sub-strings of the binary vector to hash tables created from sub-strings of the gallery images, enabling sub-linear searching that allows locating the closest matches from among the entire gallery without requiring an exhaustive linear search of the entire gallery.

What is claimed is: 
     
         1 . A method, performed by a search system including one or more processors, for searching for images of faces, the method comprising:
 generating a plurality of query sub-strings representing an image of a face, wherein the plurality of query sub-strings are generated by dividing a k-dimensional query binary vector to form the plurality of query sub-strings;   generating a plurality of hash tables based on gallery sub-strings of gallery binary vectors; and   comparing one or more of the query sub-strings to the one or more of the hash tables to identify a subset of the gallery binary vectors that are closest matches to the query binary vector.   
     
     
         2 . The method of  claim 1 , further comprising generating the k-dimensional query binary vector based on the image of the face. 
     
     
         3 . The method of  claim 2 , wherein generating the k-dimensional query binary vector comprises binarizing a feature vector by converting respective values in the feature vector to corresponding values of 0 or 1 in the k-dimensional query binary vector, wherein the conversion is based on whether respective values in the feature vector satisfy predefined criteria. 
     
     
         4 . The method of  claim 3 , further comprising generating the feature vector based on the image of the face. 
     
     
         5 . The method of  claim 4 , wherein generating the feature vector comprises processing the image of the face through a plurality of layers of a neural network. 
     
     
         6 . The method of  claim 5 , wherein k is less than 1/500 the number of data dimensions of the image of the face processed by the neural network. 
     
     
         7 . The method of  claim 5 , wherein the binary vector is less than 1/4000 the file size of the image of the face processed by the neural network. 
     
     
         8 . The method of  claim 5 , wherein the neural network comprises a fully connected layer configured to reduce dimensionality in the output feature vector to k. 
     
     
         9 . The method of  claim 1 , wherein identifying the subset of the gallery binary vectors that are the closest matches is based on a number of comparisons that is fewer than a total number of gallery binary vectors from which the closest matches are identified. 
     
     
         10 . The method of  claim 1 , wherein identifying the subset of the gallery binary vectors that are the closest matches is based on a number of comparisons that is equal to or less than log(N), where N is a total number of gallery binary vectors from which the closest matches are identified. 
     
     
         11 . A system for searching for images of faces, the system comprising one or more processors and memory, the memory storing instructions that, when executed by the one or more processors, cause the one system to:
 generate a plurality of query sub-strings representing an image of a face, wherein the plurality of query sub-strings are generated by dividing a k-dimensional query binary vector to form the plurality of query sub-strings;   generate a plurality of hash tables based on gallery sub-strings of gallery binary vectors; and   compare one or more of the query sub-strings to the one or more of the hash tables to identify a subset of the gallery binary vectors that are closest matches to the query binary vector.   
     
     
         12 . The system of  claim 11 , wherein the instructions are configured to further cause the system to generate the k-dimensional query binary vector based on the image of the face. 
     
     
         13 . The system of  claim 12 , wherein generating the k-dimensional query binary vector comprises binarizing a feature vector by converting respective values in the feature vector to corresponding values of 0 or 1 in the k-dimensional query binary vector, wherein the conversion is based on whether respective values in the feature vector satisfy predefined criteria. 
     
     
         14 . The system of  claim 11 , wherein identifying the subset of the gallery binary vectors that are the closest matches is based on a number of comparisons that is fewer than a total number of gallery binary vectors from which the closest matches are identified. 
     
     
         15 . The system of  claim 11 , wherein identifying the subset of the gallery binary vectors that are the closest matches is based on a number of comparisons that is equal to or less than log(N), where N is a total number of gallery binary vectors from which the closest matches are identified. 
     
     
         16 . A non-transitory computer-readable storage medium storing instructions that, when executed by one or more processors of a system for searching for images of faces, cause the system to:
 generate a plurality of query sub-strings representing an image of a face, wherein the plurality of query sub-strings are generated by dividing a k-dimensional query binary vector to form the plurality of query sub-strings;   generate a plurality of hash tables based on gallery sub-strings of gallery binary vectors; and   compare one or more of the query sub-strings to the one or more of the hash tables to identify a subset of the gallery binary vectors that are closest matches to the query binary vector.   
     
     
         17 . The non-transitory computer-readable storage medium of  claim 16 , wherein the instructions are configured to further cause the system to generate the k-dimensional query binary vector based on the image of the face. 
     
     
         18 . The non-transitory computer-readable storage medium of  claim 17 , wherein generating the k-dimensional query binary vector comprises binarizing a feature vector by converting respective values in the feature vector to corresponding values of 0 or 1 in the k-dimensional query binary vector, wherein the conversion is based on whether respective values in the feature vector satisfy predefined criteria. 
     
     
         19 . The non-transitory computer-readable storage medium of  claim 16 , wherein identifying the subset of the gallery binary vectors that are the closest matches is based on a number of comparisons that is fewer than a total number of gallery binary vectors from which the closest matches are identified. 
     
     
         20 . The non-transitory computer-readable storage medium of  claim 16 , wherein identifying the subset of the gallery binary vectors that are the closest matches is based on a number of comparisons that is equal to or less than log(N), where N is a total number of gallery binary vectors from which the closest matches are identified.