Hash-based face recognition system

• US 8,655,029 B2
• Filed: 04/10/2012
• Issued: 02/18/2014
• Est. Priority Date: 04/10/2012
• Status: Active Grant

• Current Assignee: Seiko Epson Corporation (Seiko Group)
• Original Assignee: Seiko Epson Corporation (Seiko Group)
• Inventors: Shiell, Derek, Xiao, Jing
• Primary Examiner(s): AHMED, SAMIR ANWAR
• Application Number:
  US13/443,624
• Publication Number:
  US 20130266195A1
• Time in Patent Office: 679 Days
• Field of Search: 382/118
• US Class Current: 382/118
• CPC Class Codes: G06V 10/7557 based on appearance, e.g. active appearance models [AAM]
• 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

Abstract

In a face recognition system, overlapping patches are defined on a canonical face. Random clusters of pixel pairs are defined within each patch, and binary features are determined for each pixel pair by comparing their respective feature values. An inverted index hash table is constructed of the binary features. Similar binary features are then determined on a library of registrable samples of identified faces. A log probability of each registrable sample generating a binary feature from a corresponding cluster of pixel pairs at each specific patch location is determined and stored in the hash table. In a search phase, similar binary features are determined, and a hash key is determined for each binary feature. The log probabilities for each identity found in the hash table are summed for all clusters of pixel pairs and locations and sorted to find the high probability match.

Claims

1. A method of identifying, within an input test image, a specific item of an item class, said method comprising:

(a) identifying a sample of said item class within said input test image, and aligning the identified sample to a canonical sample of said item class to create a fitted sample;

(b) applying a first patch pattern onto said fitted sample;

(c) applying a second patch pattern onto said fitted sample, said second patch pattern overlapping said first patch pattern;

(d) computing binary features for select overlapping patches of said first and second patch patterns, each computed binary feature being based on a choice of pixel patterns;

(e) creating a different hash key for each computed binary feature, said hash key being based on patch location in which the binary feature was computed and the choice of pixel patterns used in its computation and the binary value of the computed binary feature;

(f) using the created hash keys to access their corresponding entries in a hash table, each entry including identification (ID) information identifying an identity of a previously registered specific sample of said item class and the corresponding log probability of that identity generating a binary feature similar to the computed binary feature of the hash key at the specific patch location;

(g) summing the log probabilities of each identity found in the hash table using the created hash keys, sorting the found identifies by cumulative log probabilities to find the highest probability match;

(h) deeming the identity having the highest probability match to most closely match said specific item.

2. The method of claim 1, wherein in step (a), said fitted sample has a known size and shape.

3. The method of claim 1, wherein each patch within said first and second patch patterns has predefined pixel pair clusters for establishing said binary feature.

4. The method of claim 3, wherein the pixel pairs within said pixel pairs clusters are defined randomly on a corresponding patch on said canonical sample.

5. The method of claim 1, wherein each patch within said first and second patch patterns have randomly defined pixel pair clusters for establishing said binary feature.

6. The method of claim 1, wherein said first patch pattern fully spans said fitted sample, and said second patch pattern does not span the entirety of said fitted sample.

7. The method of claim 1, wherein in step (c), individual patches of said second patch pattern are misaligned with individual patches of said first patch pattern.

8. The method of claim 1, wherein in step (c), said first and second patch patterns have respective patches of uniform size and shape continuously distributed throughout their respective patch pattern.

9. The method of claim 8, wherein said second patch pattern is comprised of patches of identical shape and size as the patches of said first patch pattern.

10. The method of claim 8, wherein said second patch pattern has more patches than said first patch pattern, and the patches of said second patch pattern have the same shape as, and are smaller than, the patches of said first patch pattern.

11. The method of claim 8, wherein said second patch pattern is comprised of patches of different shape than the patches of said first patch pattern.

12. The method of claim 1, wherein in step (d), said choice of pixel patterns includes a random pixel pattern.

13. The method of claim 1, wherein in step (d), said choice of pixel patterns includes predefined pixel patterns defined randomly on said canonical sample.

14. The method of claim 1, wherein in step (d), each computed binary feature is further based on a choice of feature characteristics, and said choice of feature characteristics is implemented as direct comparisons between pixel pairs, defined by the choice of pixel patterns, of one of a plurality of pixel characteristics, wherein the binary value assigned to each pixel of the pixel pair is indicative of which pixel had the greater value and which had the lesser value in the comparison.

15. The method of claim 1, wherein binary features are computed for all patches of said first and second patch patterns.

16. The method of claim 1, wherein said hash table is constructed by

(A) applying said first patch pattern onto said canonical sample;

(B) applying said second patch pattern onto said canonical sample, said second patch pattern overlapping said first patch pattern;

(C) defining a plurality of random pixel pair clusters for each patch in said first patch pattern and in said second patch pattern;

(D) computing a separate binary feature for each pixel pair cluster;

(E) defining said hash table using an inverted indexing scheme, wherein a hash key is computed for each computed binary feature based on the patch location in which the binary feature was computed and the pair cluster used in its computation and the binary value of the computed binary feature;

(F) accessing a library of registrable samples of said item class, each registrable samples having a defined ID information identifying its identity, for each accessed registrable sample;

(i) aligning the registrable sample to said canonical sample to create a registrable fitted sample;

(ii) applying said first patch pattern onto said registrable fitted sample;

(iii) applying said second patch pattern onto said fitted sample, said second patch pattern overlapping said first patch pattern;

(iv) computing a separate binary feature for each of the random pixel pair clusters defined in step (C);

(vi) computing a probability of the current registrable sample generating a binary feature from the pixel pair cluster at the current specific patch location;

(vii) storing said probability and the identify of the current registrable sample at the hash table location corresponding to the current binary feature.

17. The method of claim 16, wherein said probability is a log probability.

18. The method of claim 1, wherein said item class is a human face class.