Object identification and verification using transform vector quantization

• US 7,991,199 B2
• Filed: 06/29/2007
• Issued: 08/02/2011
• Est. Priority Date: 06/29/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Das, Amitava
• Primary Examiner(s): MARIAM, DANIEL G
• Application Number:
  US11/771,879
• Publication Number:
  US 20090003660A1
• Time in Patent Office: 1,495 Days
• Field of Search: 382/115, 382/118, 382/159, 382/181, 382/197, 382/209, 382/218, 382/224
• US Class Current: 382/115
• CPC Class Codes: G06F 18/23213 with fixed number of clusters, e.g. K-means clustering
• CPC Class Codes: G06F 18/24137 Distances to cluster centroïds
• CPC Class Codes: G06V 10/763 Non-hierarchical techniques, e.g. based on statistics of modelling distributions
• CPC Class Codes: G06V 40/172 Classification, e.g. identification

Abstract

An identification system uses mappings of known objects to codebooks representing those objects to identify an object represented by multiple input representations or to verify that an input representation corresponds to an input known object. To identify the object, the identification system generates an input feature vector for each input representation. The identification system then accumulates for each known object the distances between the codebook of that object and each of the input feature vectors. The distance between a codebook and a feature vector may be the minimum of the distances between the code vectors of the codebook and the feature vector. The identification system then selects the object with the smallest accumulated distance as being the object represented by the multiple input representations.

Claims

1. A computer system for identifying a target person from multiple input images of the target person, comprising:

for each of a plurality of known persons, a mapping from the person to a codebook derived from feature vectors of the person, each feature vector of the person being derived from an image of the person;

a memory storing computer-executable instructions of;

a component that generates an input feature vector for each of the multiple input images of the target person;

a component that for each known person accumulates the distances between the codebook for the person and each of the input feature vectors of the target person; and

a component that, when the minimum of the accumulated distances satisfies an identification criterion, identifies the target person as the known person with the minimum of the accumulated distances; and

a processor that executes the computer-executable instructions stored in the memory.

2. The computer system of claim 1 including:

a component that, when the minimum of the accumulated distances does not satisfy the identification criterion, indicates that the target person cannot be identified.

3. The computer system of claim 1 wherein the identification criterion is a threshold distance between the minimum of the accumulated distances and the next larger of the accumulated distance.

4. The computer system of claim 3 wherein the threshold distance for a known person is derived from analysis of the images of the known person.

5. The computer system of claim 1 wherein the distance between the input feature vector and a codebook is the minimum of the distances between the input feature vector and each code vector of the codebook.

6. The computer system of claim 1 wherein the codebook for a known person is derived from the feature vectors of the known person using vector quantization.

7. The computer system of claim 6 wherein the vector quantization is based on a Linde, Buzo, and Gray algorithm.

8. The computer system of claim 1 wherein the images of a known person represent different profiles of that known person.

9. The computer system of claim 1 wherein the feature vector of an image is derived from a discrete cosine transform of the image.

10. The computer system of claim 9 wherein the feature vector excludes the DC coefficient of the image.

11. A computer system for identifying a target person from multiple input images of the target person, comprising:

for each of a plurality of known persons, a mapping from the person to a codebook derived from feature vectors of the person, each feature vector of the person being derived from an image of the person;

a memory storing computer-executable instructions of;

a component that generates an input feature vector for each of the multiple input images of the target person;

a component that for each known person accumulates the distances between the codebook for the person and each of the input feature vectors of the target person; and

a component that, when the minimum of the accumulated distances satisfies an identification criterion, identifies the target person as the known person with the minimum of the accumulated distances; and

a processor that executes the computer-executable instructions stored in the memory,

wherein the identification criterion is a threshold distance between the minimum of the accumulated distances and the next larger of the accumulated distance,

wherein the threshold distance for a known person is derived from analysis of the images of the known person, and

wherein the analysis is based on a histogram of distances from feature vectors of images of the known person to the codebooks of the other known person.

12. A computer-readable storage device storing computer-executable instructions for controlling a computing device to verify whether a target image is of a purported person, by a method comprising:

providing, for each of a plurality of persons including the purported person, a mapping from the person to a codebook derived from feature vectors of the person, each feature vector of a person being derived from an image of the person;

receiving the target image;

receiving an indication purported person;

generating a target feature vector for the target image;

calculating by the computing device a target distance between the codebook for the purported person and the target feature vector;

for each of a plurality of persons other than the purported person, calculating a non-target distance between the codebook for that person and the target feature vector;

selecting a minimum distance of the non-target distances; and

when the target distance and the minimum distance satisfy a verification criterion, indicating that the target image is verified as being of the purported person.

13. The computer-readable storage device of claim 12 wherein the verification criterion is a threshold ratio of the target distance and the minimum distance.

14. The computer-readable storage device of claim 13 wherein the threshold ratio is based on a square of the target distance and the minimum distance.

15. A computer-readable storage device storing computer-executable instructions for controlling a computing device to identify a target object of a target image, by a method comprising:

providing, for each of a plurality of known objects, a mapping from the object to a codebook derived from feature vectors of the object, each feature vector of the object being derived from an image of the object;

generating a target feature vector the target image;

for each known object, calculating a distance between the codebook for that known object and the target feature vector of the target image;

identifying the known object with the smallest calculated distance;

generating an identification threshold by,

for each known object other than the identified known object, calculating a confidence measure for the identified known object based on comparison of the distance for the identified known object and the distance for that known object;

generating a histogram of the confidence measures; and

setting the identification threshold based on the generated histogram; and

when the distance of the identified known object satisfies the generated identification threshold, indicating that the target image is an image of the identified known object.

16. The computer-readable storage device of claim 15 wherein the identification threshold is set to a mean distance of the histogram.

17. The computer-readable storage device of claim 15 wherein the confidence measure is based on difference between distance of the identified known object and that known object.

18. The computer-readable storage device of claim 15 wherein the object is a person.

19. The computer-readable storage device of claim 15 wherein the indication that that target image is an image of the identified known object is based on analysis of a plurality of target images of the target object.

20. The computer-readable storage device of claim 19 wherein the confidence measure is based on accumulated distances for the target images.