FACIAL RECOGNITION

• US 20120213420A1
• Filed: 02/21/2012
• Published: 08/23/2012
• Est. Priority Date: 02/18/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Steiner, Matthew S.
• Granted Patent: US 9,135,500 B2
• Time in Patent Office: Days
• US Class Current: 382/118
• CPC Class Codes: G06V 20/30 in albums, collections or shared content, e.g. social network photos or video
• CPC Class Codes: G06V 40/173 face re-identification, e.g. recognising unknown faces across different face tracks
• CPC Class Codes: G06V 40/50 Maintenance of biometric data or enrolment thereof

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for performing facial recognition. In one aspect, a method includes accessing a first digital photograph. A first face template is generated for each face detected in the first digital photograph. Second user identifiers that are associated with a first user identifier are determined. A digital photograph index of photographs, user identifiers, and areas in the digital photographs in which a face of a user identified by user identifier is located is accessed. Second user identifiers are selected, and second face templates are generated from the faces of the user the digital photographs. First face templates that match second face templates are identified, and for each first face template that matches a second face template, data is generated specifying the area in the first digital photograph in which the face of the second user is located.

Claims

1. A method performed by data processing apparatus, the method comprising:

accessing, at a data processing apparatus, a first digital photograph;

generating a first face template for each face detected in the first digital photograph;

determining second user identifiers that are associated with a first user identifier, the first user identifier and second user identifiers identifying users;

accessing a digital photograph index that indexes photographs by user identifiers, and that specifies, for each digital photograph and for each user identifier indexing the digital photograph, an area in the digital photograph in which a face of a user identified by user identifier is located;

selecting second user identifiers, and for each of the selected second user identifiers, generating a second face template for the second user identifier from each of the faces of the user in the predefined areas of the digital photographs indexed by the second user identifier;

identifying first face templates that match second face templates; and

for each first face template that matches a second face template, generating data specifying the area in the first digital photograph in which is located the face of the second user identified by the second user identifier of the second face template.

2. The method of claim 1, wherein each face template is stored in non-persistent memory and is not persisted after identifying first face templates that match second face templates.

3. The method of claim 1, wherein:

determining second user identifiers that are associated with the first user identifier comprises;

generating, for each of a plurality of second user identifiers, an affinity score representing a relationship of the first user identified by the first user identifier to the second user identified by the second user identifier; and

determining second user identifier having an affinity score that meet a threshold are associated with the first user identifier.

4. The method of claim 3, further comprising:

ordering the second user identifiers according to the affinity scores; and

selecting the second user identifiers, generating the second face templates for the second user identifiers, and identifying first face templates that match the second face templates according the order.

5. The method of claim 3, wherein generating an affinity score for each of a plurality of second user identifiers comprises:

for each digital photograph indexed by the first user identifier, determining second user identifiers indexing the digital photograph; and

for each second user identifier, determining the affinity score, in part, on a value that is proportional to a number of digital photographs that are indexed by both the first user identifier and the second user identifier.

6. The method of claim 5, wherein the affinity score is further based, in part, on a time that each of the digital photographs was generated.

7. The method of claim 3, wherein generating an affinity score for each of a plurality of second user identifiers comprises determining the affinity score based, in part, on a value that is proportional to a number of digital photographs of the second user that the first user has tagged with the identifier of the second user.

8. The method of claim 7, wherein the affinity score is further based, in part, on a time that that the first user tagged each of the digital photographs.

9. The method of claim 1, wherein:

determining second user identifiers that are associated with the first user identifier comprises;

selecting second user identifiers that are associated with the first user identifier by contact list for the first user identifier.

10. The method of claim 1, further comprising:

selecting third user identifiers, each third user identifier being a user identifier indexing a digital photograph in the digital photograph index that is also indexed by one or more of the first user identifier and second user identifiers;

for each of the selected third user identifiers, generating a third face template for the third user identifier from each of the faces of the user in the predefined areas of the digital photographs indexed by the third user identifier;

identifying first face templates that match third face templates; and

for each first face template that matches a third face template, generating data specifying the area in the first digital photograph in which is located the face of the third user identified by the third user identifier of the third face template.

11. The method of claim 1, further comprising, for each first face template that matches a second face template for a second user identifier:

generating a quality score for the first face template;

determining whether the quality score exceeds a quality score threshold; and

if the quality score exceeds the quality score threshold, storing in the digital photograph index data indexing the first photograph by second user identifier, and that specifies that area in the digital photograph in which the face of the second user identified by second user identifier is located.

12. A computer storage medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

accessing a first digital photograph;

generating a first face template for each face detected in the first digital photograph;

determining second user identifiers that are associated with a first user identifier, the first user identifier and second user identifiers identifying users;

accessing a digital photograph index that indexes photographs by user identifiers, and that specifies, for each digital photograph and for each user identifier indexing the digital photograph, an area in the digital photograph in which a face of a user identified by user identifier is located;

selecting second user identifiers, and for each of the selected second user identifiers, generating a second face template for the second user identifier from each of the faces of the user in the predefined areas of the digital photographs indexed by the second user identifier;

identifying first face templates that match second face templates; and

for each first face template that matches a second face template, generating data specifying the area in the first digital photograph in which is located the face of the second user identified by the second user identifier of the second face template.

13. The computer storage medium of claim 12, wherein:

determining second user identifiers that are associated with the first user identifier comprises;

generating, for each of a plurality of second user identifiers, an affinity score representing a relationship of the first user identified by the first user identifier to the second user identified by the second user identifier; and

determining second user identifier having an affinity score that meet a threshold are associated with the first user identifier.

14. The computer storage medium of claim 13, the operations further comprising:

ordering the second user identifiers according to the affinity scores; and

selecting the second user identifiers, generating the second face templates for the second user identifiers, and identifying first face templates that match the second face templates according the order.

15. The computer storage medium of claim 14, wherein generating an affinity score for each of a plurality of second user identifiers comprises:

for each digital photograph indexed by the first user identifier, determining second user identifiers indexing the digital photograph; and

for each second user identifier, determining the affinity score, in part, on a value that is proportional to a number of digital photographs that are indexed by both the first user identifier and the second user identifier.

16. The computer storage medium of claim 12, the operations further comprising, for each first face template that matches a second face template for a second user identifier:

generating a quality score for the first face template;

determining whether the quality score exceeds a quality score threshold; and

if the quality score exceeds the quality score threshold, storing in the digital photograph index data indexing the first photograph by second user identifier, and that specifies that area in the digital photograph in which the face of the second user identified by second user identifier is located.

17. A system, comprising:

a data processing apparatus; and

a memory storage apparatus in data communication with the data processing apparatus and storing instructions executable by the data processing apparatus and that upon such execution cause the data processing apparatus to perform operations comprising;

accessing a first digital photograph;

generating a first face template for each face detected in the first digital photograph;

determining second user identifiers that are associated with a first user identifier, the first user identifier and second user identifiers identifying users;

accessing a digital photograph index that indexes photographs by user identifiers, and that specifies, for each digital photograph and for each user identifier indexing the digital photograph, an area in the digital photograph in which a face of a user identified by user identifier is located;

selecting second user identifiers, and for each of the selected second user identifiers, generating a second face template for the second user identifier from each of the faces of the user in the predefined areas of the digital photographs indexed by the second user identifier;

identifying first face templates that match second face templates; and

for each first face template that matches a second face template, generating data specifying the area in the first digital photograph in which is located the face of the second user identified by the second user identifier of the second face template.

18. The system of claim 17, wherein:

determining second user identifiers that are associated with the first user identifier comprises;

generating, for each of a plurality of second user identifiers, an affinity score representing a relationship of the first user identified by the first user identifier to the second user identified by the second user identifier; and

determining second user identifier having an affinity score that meet a threshold are associated with the first user identifier.

19. The system of claim 17, wherein generating an affinity score for each of a plurality of second user identifiers comprises:

for each digital photograph indexed by the first user identifier, determining second user identifiers indexing the digital photograph; and

for each second user identifier, determining the affinity score, in part, on a value that is proportional to a number of digital photographs that are indexed by both the first user identifier and the second user identifier.

20. The system of claim 17, the operations further comprising, for each first face template that matches a second face template for a second user identifier:

generating a quality score for the first face template;

determining whether the quality score exceeds a quality score threshold; and

if the quality score exceeds the quality score threshold, storing in the digital photograph index data indexing the first photograph by second user identifier, and that specifies that area in the digital photograph in which the face of the second user identified by second user identifier is located.