Face recognition and image search system using sparse feature vectors, compact binary vectors, and sub-linear search
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.
1. A method, performed by a search system including one or more servers for enrollment and searching, for searching a database of gallery binary vectors representing gallery images of faces, comprising:
receiving an input image of a face;
processing the received input image of the face, comprising:
processing through a plurality of layers of a deep neural network (DNN) to generate a k-dimensional feature vector; and
binarizing the feature vector to generate a k-dimensional binary vector by converting respective values in the feature vector to corresponding values of 0 or 1 in the binary vector, wherein the conversion is based on whether respective values in the feature vector satisfy predefined criteria;
dividing the binary vector into a plurality of sub-strings;
creating a plurality of hash tables based on gallery sub-strings of gallery binary vectors; and
comparing one or more of the sub-strings of the binary vector to the one or more of the hash tables to identify a subset of the gallery binary vectors that are closest matches to the binary vector.
2. The method of claim 1 , wherein processing the received input image of the face comprises, prior to processing the image through the DNN, cropping the input image of the face to a predefined size.
3. 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.
4. 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.
5. The method of claim 1 , wherein the DNN comprises a fully connected layer configured to reduce dimensionality in the output k-dimensional feature vector to k.
6. The method of claim 1 , wherein k is less than 1/500 the number of data dimensions the cropped input image of the face input into DNN.
7. The method of claim 1 , wherein k is 256.
8. The method of claim 1 , wherein the binary vector is less than 1/4000 the file size of the cropped input image of the face input into the DNN.
9. The method of claim 1 , wherein the binary vector is 32 bytes in file size.
10. A system, for searching a database of gallery binary vectors representing gallery images of faces, the system comprising one or more servers for enrollment and searching and memory, the memory storing instructions that, when executed by the one or more servers, cause the one or more servers to:
receive an input image of a face;
process the received input image of the face, comprising:
processing through a plurality of layers of a deep neural network (DNN) to generate a k-dimensional feature vector; and
binarizing the feature vector to generate a k-dimensional binary vector by converting respective values in the feature vector to corresponding values of 0 or 1 in the binary vector, wherein the conversion is based on whether respective values in the feature vector satisfy predefined criteria;
divide the binary vector into a plurality of sub-strings;
create a plurality of hash tables based on gallery sub-strings of gallery binary vectors; and
compare one or more of the sub-strings of the binary vector to the one or more of the hash tables to identify a subset of the gallery binary vectors that are closest matches to the binary vector.
11. The system of claim 10 , wherein processing the received input image of the face comprises, prior to processing the image through the DNN, cropping the input image of the face to a predefined size.
12. The system of claim 10 , 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.
13. The system of claim 10 , 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.
14. The system of claim 10 , wherein the DNN comprises a fully connected layer configured to reduce dimensionality in the output k-dimensional feature vector to k.
15. The system of claim 10 , wherein k is less than 1/500 the number of data dimensions the cropped input image of the face input into DNN.
16. The system of claim 10 , wherein k is 256.
17. The system of claim 10 , wherein the binary vector is less than 1/4000 the file size of the cropped input image of the face input into the DNN.
18. The system of claim 10 , wherein the binary vector is 32 bytes in file size.
19. A non-transitory computer-readable storage medium storing instructions that, when executed by one or more servers for enrollment and searching, cause the one or more servers to:
receive an input image of a face;
process the received input image of the face, comprising:
processing through a plurality of layers of a deep neural network (DNN) to generate a k-dimensional feature vector; and
binarizing the feature vector to generate a k-dimensional binary vector by converting respective values in the feature vector to corresponding values of 0 or 1 in the binary vector, wherein the conversion is based on whether respective values in the feature vector satisfy predefined criteria;
divide the binary vector into a plurality of sub-strings;
create a plurality of hash tables based on gallery sub-strings of gallery binary vectors; and
compare one or more of the sub-strings of the binary vector to the one or more of the hash tables to identify a subset of the gallery binary vectors that are closest matches to the binary vector.
20. The non-transitory computer-readable storage medium of claim 19 , wherein processing the received input image of the face comprises, prior to processing the image through the DNN, cropping the input image of the face to a predefined size.
21. The non-transitory computer-readable storage medium of claim 19 , 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.
22. The non-transitory computer-readable storage medium of claim 19 , 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 Nis a total number of gallery binary vectors from which the closest matches are identified.
23. The non-transitory computer-readable storage medium of claim 19 , wherein the DNN comprises a fully connected layer configured to reduce dimensionality in the output k-dimensional feature vector to k.
24. The non-transitory computer-readable storage medium of claim 19 , wherein k is less than 1/500 the number of data dimensions the cropped input image of the face input into DNN.
25. The non-transitory computer-readable storage medium of claim 19 , wherein k is 256.
26. The non-transitory computer-readable storage medium of claim 19 , wherein the binary vector is less than 1/4000 the file size of the cropped input image of the face input into the DNN.
27. The non-transitory computer-readable storage medium of claim 19 , wherein the binary vector is 32 bytes in file size.