Facial image bucketing with expectation maximization and facial coordinates

• US 9,639,739 B2
• Filed: 05/28/2016
• Issued: 05/02/2017
• Est. Priority Date: 07/30/2014
• Status: Expired due to Fees

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Poplavski, Michael, Schumacher, Scott, Snehal, Prachi, Welleck, Sean J., Xia, Alan, Zhou, Yinle
• Primary Examiner(s): Kholdebarin, Iman K
• Application Number:
  US15/168,038
• Publication Number:
  US 20160275340A1
• Time in Patent Office: 339 Days
• Field of Search: None
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06F 18/217 Validation; Performance evaluation; Active pattern learning techniques
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06V 10/762 using clustering, e.g. of similar faces in social networks
• CPC Class Codes: G06V 40/171 Local features and components; Facial parts eye characteristics G06V40/18; Occluding parts, e.g. glasses; Geometrical relationships
• CPC Class Codes: G06V 40/172 Classification, e.g. identification
• CPC Class Codes: G06V 40/173 face re-identification, e.g. recognising unknown faces across different face tracks

Abstract

Facial image bucketing is disclosed, whereby a query for facial image recognition compares the facial image against existing candidate images. Rather than comparing the facial image to each candidate image, the candidate images are organized or clustered into buckets according to their facial similarities, and the facial image is then compared to the image(s) in most-likely one(s) of the buckets. The organizing uses particular selected facial features, computes distance between the facial features, and selects ones of the computed distances to determine which facial images should be organized into the same bucket.

Claims

1. A method for facial image bucketing, comprising:

analyzing each of a plurality of facial images in a candidate image set, comprising;

determining, for the each image, a location of each of a plurality of face points;

computing, for the each image, a distance between the location of each of the plurality of face points; and

computing, for the each image, a ratio for each unique pair of the computed distances, the computed ratios representing relationships among facial features of the each image;

selecting, for the candidate image set, a subset of the facial features;

clustering the facial images in the candidate image set into a plurality of buckets according to the image-specific ratio for each facial feature in the selected subset, comprising iteratively computing a mean and a standard deviation, according to the image-specific ratio for each facial feature in the selected subset, for each of at least one image to be included in each of the plurality of buckets until achieving convergence; and

storing the plurality of buckets on a storage medium for subsequent use in performing a query for a query facial image to determine which of the plurality of facial images is most similar to the query facial image, wherein the query facial image is compared only to images clustered into a selected subset of the plurality of buckets.

2. The method according to claim 1, wherein the clustering is performed using an Expectation Maximization algorithm.

3. The method according to claim 1, wherein a count of the plurality of buckets to be used for the clustering is provided by a user.

4. The method according to claim 1, further comprising using the stored buckets for performing the query by performing:

determining, for the query facial image, the location of each of the plurality of face points;

computing, for the query facial image, the distance between the location of each of the plurality of face points;

computing, for the query facial image, the ratio for each unique pair of the computed distances;

computing, for the query facial image, a probability of the computed ratios for the query facial image being in each of the plurality of buckets; and

using the computed probabilities for selecting at least one of the plurality of buckets as comprising the selected subset of the plurality of buckets.

5. The method according to claim 4, wherein:

the selected subset of the plurality of buckets comprises one or more of the plurality of buckets for which the computed probability is highest.

6. The method according to claim 5, wherein:

a user provides a count of the plurality of buckets to include in the selected subset of the plurality of buckets.

7. The method according to claim 4, wherein:

performing the query determines which of the plurality of facial images is most similar to the query facial image.

8. A system for facial image bucketing, comprising:

a plurality of facial images in a candidate image set stored in persistent storage of a computing system;

a computer comprising a processor; and

instructions which are executable, using the processor, to perform functions comprising;

analyzing each of a plurality of facial images in a candidate image set, comprising;

determining, for the each image, a location of each of a plurality of face points;

computing, for the each image, a distance between the location of each of the plurality of face points; and

computing, for the each image, a ratio for each unique pair of the computed distances, the computed ratios representing relationships among facial features of the each image;

selecting, for the candidate image set, a subset of the facial features;

clustering the facial images in the candidate image set into a plurality of buckets according to the image-specific ratio for each facial feature in the selected subset, comprising iteratively computing a mean and a standard deviation, according to the image-specific ratio for each facial feature in the selected subset, for each of at least one image to be included in each of the plurality of buckets until achieving convergence; and

storing the plurality of buckets on a storage medium for subsequent use in performing a query for a query facial image to determine which of the plurality of facial images is most similar to the query facial image, wherein the query facial image is compared only to images clustered into a selected subset of the plurality of buckets.

9. The system according to claim 8, wherein the clustering is performed using an Expectation Maximization algorithm.

10. The system according to claim 8, wherein the functions further comprise using the stored buckets for performing the query by performing:

determining, for the query facial image, the location of each of the plurality of face points;

computing, for the query facial image, the distance between the location of each of the plurality of face points;

computing, for the query facial image, the ratio for each unique pair of the computed distances;

computing, for the query facial image, a probability of the computed ratios for the query facial image being in each of the plurality of buckets; and

using the computed probabilities for selecting at least one of the plurality of buckets as comprising the selected subset of the plurality of buckets.

11. The system according to claim 10, wherein:

the selected subset of the plurality of buckets comprises one or more of the plurality of buckets for which the computed probability is highest.

12. The system according to claim 10, wherein:

performing the query determines which of the plurality of facial images is most similar to the query facial image.

13. A computer program product for facial image bucketing, the computer program product comprising:

a computer-readable storage medium having computer readable program code embodied therein, the computer-readable program code configured for;

analyzing each of a plurality of facial images in a candidate image set, comprising;

determining, for the each image, a location of each of a plurality of face points;

computing, for the each image, a distance between the location of each of the plurality of face points; and

computing, for the each image, a ratio for each unique pair of the computed distances, the computed ratios representing relationships among facial features of the each image;

selecting, for the candidate image set, a subset of the facial features;

clustering the facial images in the candidate image set into a plurality of buckets according to the image-specific ratio for each facial feature in the selected subset, comprising iteratively computing a mean and a standard deviation, according to the image-specific ratio for each facial feature in the selected subset, for each of at least one image to be included in each of the plurality of buckets until achieving convergence; and

storing the plurality of buckets on a storage medium for subsequent use in performing a query for a query facial image to determine which of the plurality of facial images is most similar to the query facial image, wherein the query facial image is compared only to images clustered into a selected subset of the plurality of buckets.

14. The computer program product according to claim 13, wherein the clustering is performed using an Expectation Maximization algorithm.

15. The computer program product according to claim 13, wherein the computer-readable program code is further configured for using the stored buckets for performing the query by performing:

determining, for the query facial image, the location of each of the plurality of face points;

computing, for the query facial image, the distance between the location of each of the plurality of face points;

computing, for the query facial image, the ratio for each unique pair of the computed distances;

computing, for the query facial image, a probability of the computed ratios for the query facial image being in each of the plurality of buckets; and

using the computed probabilities for selecting at least one of the plurality of buckets as comprising the selected subset of the plurality of buckets.

16. The computer program product according to claim 15, wherein:

the selected subset of the plurality of buckets comprises one or more of the plurality of buckets for which the computed probability is highest.

17. The computer program product according to claim 15, wherein:

performing the query determines which of the plurality of facial images is most similar to the query facial image.