Vector-based face recognition algorithm and image search system

Patent metadata

Field	Value
Publication number	US-9405965-B2
Application number	US-201514642458-A
Country	US
Kind code	B2
Filing date	Mar 9, 2015
Priority date	Nov 7, 2014
Publication date	Aug 2, 2016
Grant date	Aug 2, 2016

Abstract

Systems and methods for performing face recognition and image searching are provided. A system for face recognition and image searching includes an ingestion system, a search system, a user device, and a database of galley files that include feature vectors. The ingestion system crawls the internet starting with a seed URL to scrape image files and generate feature vectors. Feature vectors of images input by a user may be compared by the search system to feature vectors in the gallery files. A method for generating feature vectors includes landmark detection, component aligning, texture mapping, vector computation, comparing cluster centers defined by vectors stored in a database with vectors generated based on an input image, linear discriminant analysis, and principal component analysis.

First claim

What is claimed is:

1. A method, performed by an ingestion system including one or more servers for enrollment and web crawling, for creating a searchable database of feature vectors representing images of a faces, the method comprising:
receiving an image of a face;
detecting landmarks on the image of the face and associating the detected landmarks with points;
subjecting the points to a transformation;
aligning a portion of the image of the face in accordance with the transformation;
performing texture mapping on the portion of the image of the face;
computing a first vector based on the portion of the image of the face;
creating a second vector based on a similarity of the first vector to each of a predetermined number of a first plurality of vectors;
generating a feature vector by concatenating the second vector with a second plurality of vectors, wherein the second vector and each of the second plurality of vectors each correspond to a respective portion of the image of the face; and
storing the feature vector, along with associated metadata as part of a gallery file, in a database.

2. The method of claim 1 , wherein creating the second vector includes:
calculating a distance of the first vector from each of the first plurality of vectors, and
selecting from the calculated distances, for entry into the second vector, the predetermined number of calculated distances that are smallest.

3. The method of claim 2 , wherein each of the first plurality of vectors defines a center of a cluster, each cluster comprising a third plurality of vectors computed based on a portion of a different image of a face.

4. The method of claim 3 , wherein each of the first plurality of vectors is calculated using a radial basis function.

5. The method of claim 3 , wherein computing the first vector and computing each of the third plurality of vectors include computing local binary patterns.

6. The method of claim 3 , wherein computing the first vector and computing each of the third plurality of vectors include computing a histogram oriented gradient.

7. The method of claim 1 , comprising:
subjecting the feature vector to linear discriminant analysis.

8. The method of claim 1 , comprising:
subjecting the feature vector to principal component analysis.

9. The method of claim 1 , wherein the portion of the image of the face is a component image representing a part of the face selected from the group consisting of: eyes, eyebrows, nose, mouth, and entire face.

10. The method of claim 1 , wherein the portion of the image of the face is a rectangular sub-portion of a component image representing a part of the face selected from the group consisting of: eyes, eyebrows, nose, mouth, and entire face.

11. The method of claim 1 , wherein receiving an image of a face comprises:
receiving, by a crawler, input of a seed network address,
accessing, by the crawler, the seed network address, and
retrieving, by the crawler, an image located at the seed network address.

12. The method of claim 11 , wherein receiving an image of a face further comprises:
detecting, by the crawler, on a page located at the seed network address, a second network address,
accessing, by the crawler, the second network address, and
retrieving, by the crawler, an image located at the second network address.

13. The method of claim 11 , wherein receiving an image of a face further comprises:
determining, by a duplicate filter, whether the image has previously been retrieved, and
if the image has previously been retrieved, preventing creation of the a new feature vector corresponding to the image.

14. The method of claim 1 , comprising:
associating the feature vector with an identity tag;
generating a covariance matrix based on the feature vector.

15. A system for creating a searchable database of feature vectors representing images of faces, comprising:
a crawler configured to retrieve an image of a face;
a duplicate filter configured to prevent creation of a new feature vector if the image has previously been retrieved;
an enrollment server configured to:
receive an image of a face;
detect landmarks on the image of the face and associate the detected landmarks with points,
subject the points to a transformation,
align a portion of the image of the face in accordance with the transformation,
perform texture mapping on the portion of the image of the face,
compute a first vector based on the portion of the image of the face,
create a second vector based on a similarity of the first vector to each of a predetermined number of a first plurality of vectors, and
generate a feature vector by concatenating the second vector with a second plurality of vectors, wherein the second vector and each of the second plurality of vectors each correspond to a respective portion of the image of the face; and
a database configured to store the feature vector, along with associated metadata as part of a gallery file.

16. A method, performed by a search system including one or more servers for enrollment and searching, for searching a database of feature vectors representing images of faces to select resulting images of faces that are similar to an input image of a face, comprising:
receiving an image of a face;
detecting landmarks on the image of the face and associating the detected landmarks with points;
subjecting the points to a transformation;
aligning a portion of the image of the face in accordance with the transformation;
performing texture mapping on the portion of the image of the face;
computing a first vector based on the portion of the image of the face;
creating a second vector based on a similarity of the first vector to each of a predetermined number of a first plurality of vectors;
generating a query feature vector by concatenating the second vector with a second plurality of vectors, wherein the second vector and each of the second plurality of vectors each corresponds to a respective portion of the image of the face and;
selecting a plurality of resulting images of faces based on a comparison of the query feature vector with a plurality of feature vectors stored in gallery files in a database.

17. The method of claim 16 , wherein selecting a plurality of resulting images comprises:
comparing the query feature vector to each of the plurality of feature vectors stored in gallery files, including calculating a distance between the query feature vector and each of the plurality of feature vectors stored in gallery files, and
assigning each of the plurality of feature vectors stored in the gallery files a normalized similarity score based on the calculated distance of the respective feature vector to the query feature vector.

18. The method of claim 16 , wherein selecting a plurality of resulting images comprises:
transmitting the query template from a search master server to a plurality of search slave servers,
transmitting, from each search slave server to the search master server, a predetermined number of candidate gallery files associated with feature vectors having highest similarity scores from among the plurality of feature vectors, and

transmitting, from the search master server to the enrollment server, the selected plurality of resulting images of faces, selected from the candidate gallery files based on which candidate gallery files are associated with highest similarity scores.

19. The method of claim 18 , wherein selecting a plurality of resulting images comprises:
transmitting, from the search master server

Assignees

• Noblis Inc

Inventors

• Klare Brendan
• Klontz Joshua
• Blanton Austin

Classifications

• G06V10/7715

  Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods · CPC title

• G06V40/171 Primary

  Local features and components; Facial parts (eye characteristics G06V40/18); Occluding parts, e.g. glasses; Geometrical relationships · CPC title

• G06V40/172

  Classification, e.g. identification · CPC title

• G06T11/10

  Texturing; Colouring; Generation of textures or colours (retouching, inpainting or scratch removal G06T5/77) · CPC title

• G06F18/22

  Matching criteria, e.g. proximity measures · CPC title