Granted Patent B1

US 7,907,755 · App. 11/382,657 · Granted Mar 15, 2011

Abstract

Claims (92)

1. A method for determining similar faces within images based on a user's perception of facial similarity, the method comprising:

determining, by one or more processors, inequalities between training faces, where the inequalities represent perceptions of one or more training users regarding a similarity of a first set of two, different training faces relative to a similarity of a second set of two, different training faces;

determining, by the one or more processors, training feature vectors in an objective feature space based on the training faces, wherein the training feature vectors are separated by objective differences;

optimizing, by the one or more processors, a function over a matrix M that maximizes a correlation between the training feature vectors in the objective feature space and the inequalities;

determining, by the one or more processors, a mapping function between the objective feature space and a psychological feature space based on the matrix M;

determining, by the one or more processors and based on the determined mapping function, similarity information that indicates human perception of facial similarity;

receiving, by the one or more processors, a query image that includes a query face;

determining, by the one or more processors, one or more search result images that include at least one face that is similar to the query face based on the similarity information that indicates the human perception of facial similarity; and

providing, by the one or more processors, the search result images to a user.

2. The method of claim 1 wherein:

determining one or more search result images that include at least one face that is similar to the query face based on the similarity information comprises determining one or more search result images that include at least one face that is similar to the query face based on the mapping function.

3. The method of claim 2 wherein determining one or more search result images that include at least one face that is similar to the query face based on the mapping function comprises:

generating a query feature vector in the objective feature space based on the query face;

mapping the query feature vector from the objective feature space into the psychological feature space using the mapping function;

accessing a set of search feature vectors in the psychological feature space that are associated with a set of search faces;

determining distances between the mapped query feature vector and the search feature vectors;

selecting one or more search feature vectors that are within a selected distance of the mapped query vector; and

designating images including the search faces associated with the selected search feature vectors as the one or more search result images.

4. The method of claim 3 wherein determining one or more search result images that include at least one face that is similar to the query face based on the mapping function further comprises:

accessing a set of search feature vectors in the objective feature space that are associated with a set of search faces; and

mapping the search feature vectors from the objective feature space into the psychological feature space to form the set of search feature vectors in the psychological feature space that are associated with a set of search faces.

5. The method of claim 3 wherein determining one or more search result images that include at least one face that is similar to the query face based on the mapping function further comprises:

detecting a class for the query face;

accessing a collection of feature vectors in the psychological feature space that are associated with a collection of faces;

determining faces in the collection of faces that are the same class as the query face; and

forming the set of search feature vectors by selecting the feature vectors in the collection of feature vectors that correspond to the faces in the collection of faces that are the same class as the query face.

6. The method of claim 3 wherein the distances are weighted Euclidean distances such that determining distances between the mapped query feature vector and the search feature vectors comprises determining weighted Euclidean distances between the mapped query feature vector and the search feature vectors.

7. The method of claim 2 wherein determining one or more search result images that include at least one face that is similar to the query face based on the mapping function comprises:

generating a query feature vector in the objective feature space based on the query face;

accessing a set of search feature vectors in the objective feature space that are associated with a set of search faces;

determining distances between the query feature vector and the search feature vectors;

mapping the distances into the psychological feature space;

selecting one or more search feature vectors that are within a selected distance of the query vector based on the mapped distances; and

designating images including the search faces associated with the selected search feature vectors as the one or more search result images.

8. The method of claim 7 wherein determining one or more search result images that include at least one face that is similar to the query face based on the mapping function further comprises:

detecting a class for the query face;

accessing a collection of feature vectors in the objective feature space that are associated with a collection of faces;

determining faces in the collection of faces that are the same class as the query face; and

forming the set of search feature vectors by selecting the feature vectors in the collection of feature vectors that correspond to the faces in the collection of faces that are the same class as the query face.

9. The method of claim 7 wherein the distances are weighted Euclidean distances such that determining distances between the query feature vector and the search feature vectors comprises determining weighted Euclidean distances between the query feature vector and the search feature vectors.

10. The method of claim 1 further comprising providing the search result images to the user in a dating application.

11. The method of claim 1 further comprising providing the search result images to the user in a social networking application.

12. The method of claim 1 , wherein the matrix M includes an array of multipliers that correspond to elements of the training feature vectors.

13. The method of claim 12 , wherein optimizing the function over the matrix M includes minimizing a function that (1) correlates distances between (i) the training feature vectors in the objective feature space and (ii) the training feature vectors mapped into the psychological feature space using the matrix M and (2) evaluates whether inequalities between the feature vectors mapped into the psychological feature space using the matrix M match the inequalities that represent perceptions of the one or more training users.

14. A computer-useable medium, which is not a signal, storing a computer program, the computer program including instructions for causing a computer to perform the following operations:

determine inequalities between training faces, where the inequalities represent perceptions of one or more training users regarding a similarity of a first set of two, different training faces relative to a similarity of a second set of two, different training faces;

determine training feature vectors in an objective feature space based on the training faces, wherein the training feature vectors are separated by objective differences;

optimize a function over a matrix M that maximizes a correlation between the training feature vectors in the objective feature space and the inequalities;

determine a mapping function between the objective feature space and a psychological feature space based on the matrix M;

determine, based on the determined mapping function, similarity information that indicates human perception of facial similarity;

receive a query image that includes a query face;

determine one or more search result images that include at least one face that is similar to the query face based on the similarity information that indicates the human perception of facial similarity; and

provide the search result images to a user.

15. The computer-useable medium of claim 14 wherein:

the instructions for causing the computer to determine one or more search result images that include at least one face that is similar to the query face based on the similarity information comprise instructions for causing the computer to determine one or more search result images that include at least one face that is similar to the query face based on the mapping function.

16. The computer-useable medium of claim 15 wherein the instructions for causing the computer to determine one or more search result images that include at least one face that is similar to the query face based on the mapping function comprise instructions for causing the computer to:

generate a query feature vector in the objective feature space based on the query face;

map the query feature vector from the objective feature space into the psychological feature space using the mapping function;

access a set of search feature vectors in the psychological feature space that are associated with a set of search faces;

determine distances between the mapped query feature vector and the search feature vectors;

select one or more search feature vectors that are within a selected distance of the mapped query vector; and

designate images including the search faces associated with the selected search feature vectors as the one or more search result images.

17. The computer-useable medium of claim 16 wherein the instructions for causing the computer to determine one or more search result images that include at least one face that is similar to the query face based on the mapping function comprise instructions for causing the computer to:

access a set of search feature vectors in the objective feature space that are associated with a set of search faces; and

map the search feature vectors from the objective feature space into the psychological feature space to form the set of search feature vectors in the psychological feature space that are associated with a set of search faces.

18. The computer-useable medium of claim 16 wherein the distances are weighted Euclidean distances such that the instructions for causing the computer to determine distances between the mapped query feature vector and the search feature vectors comprise instructions for causing the computer to determine weighted Euclidean distances between the mapped query feature vector and the search feature vectors.

19. The computer-useable medium of claim 15 wherein the instructions for causing the computer to determine one or more search result images that include at least one face that is similar to the query face based on the mapping function comprise instructions for causing the computer to:

generate a query feature vector in the objective feature space based on the query face;

access a set of search feature vectors in the objective feature space that are associated with a set of search faces;

determine distances between the query feature vector and the search feature vectors;

map the distances into the psychological feature space;

select one or more search feature vectors that are within a selected distance of the query vector based on the mapped distances; and

designate images including the search faces associated with the selected search feature vectors as the one or more search result images.

20. The computer-useable medium of claim 19 wherein the distances are weighted Euclidean distances such that the instructions for causing the computer to determine distances between the query feature vector and the search feature vectors comprise instructions for causing the computer to determine weighted Euclidean distances between the query feature vector and the search feature vectors.

21. A system comprising:

means for determining, by one or more processors, inequalities between training faces, where the inequalities represent perceptions of one or more training users regarding a similarity of a first set of two, different training faces relative to a similarity of a second set of two, different training faces;

means for determining, by the one or more processors, training feature vectors in an objective feature space based on the training faces, wherein the training feature vectors are separated by objective differences;

means for optimizing, by the one or more processors, a function over a matrix M that maximizes a correlation between the training feature vectors in the objective feature space and the inequalities;

means for determining, by the one or more processors, a mapping function between the objective feature space and a psychological feature space based on the matrix M;

means for determining, by the one or more processors and based on the determined mapping function, similarity information that indicates human perception of facial similarity;

means for receiving, by the one or more processors, a query image that includes a query face;

means for determining, by the one or more processors, one or more search result images that include at least one face that is similar to the query face based on the similarity information that indicates the human perception of facial similarity; and

means for providing, by the one or more processors, the search result images to a user.

22. A method for determining similar faces within images based on a user's perception of facial similarity, the method comprising:

accessing, by one or more processors, training data, where the training data represent perceptions of one or more training users regarding a similarity of a first set of two, different training faces relative to a similarity of a second set of two, different training faces;

determining, by the one or more processors, training feature vectors in an objective feature space based on the training faces, wherein the training feature vectors are separated by objective differences;

minimizing, by the one or more processors, a function that (1) correlates distances between (i) the training feature vectors in the objective feature space and (ii) the training feature vectors mapped into a psychological feature space using a matrix M and (2) evaluates whether inequalities between the feature vectors mapped into the psychological feature space using the matrix M match inequalities that represent the perceptions of the one or more training users;

determining, by the one or more processors and based on the accessed training data and the matrix M, similarity information that indicates human perception of facial similarity;

receiving, by the one or more processors, a query image that includes a query face;

determining, by the one or more processors, one or more search result images that include at least one face that is similar to the query face based on the similarity information that indicates the human perception of facial similarity; and

providing, by the one or more processors, the search result images to a user,

wherein the matrix M includes an array of multipliers that correspond to elements of the training feature vectors.

Assignments (10)