OBJECT IDENTIFICATION AND VERIFICATION USING TRANSFORM VECTOR QUANTIZATION

• US 20090003660A1
• Filed: 06/29/2007
• Published: 01/01/2009
• Est. Priority Date: 06/29/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Das, Amitava
• Granted Patent: US 7,991,199 B2
• Time in Patent Office: Days
• US Class Current: 382/118
• 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 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.

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 4 wherein 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.

6. 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.

7. 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.

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

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

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

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

12. A computer system for verifying that a target image corresponds to a target person, comprising:

for each of a plurality of known persons including the target 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 a representation of the person;

a component that generates a target feature vector for the target image;

a component that, for each known person, calculates the distance between the codebook for the known person and the target person; and

a component that, when the calculated distances satisfies an verification critrion, indicating that the target object can be verified as corresponding to the target image.

13. The computer system of claim 12 including:

a component that, when the calculated distances do not satisfy the verification criterion, indicating that the target person cannot be verified as corresponding to the target image.

14. The computer system of claim 12 wherein the verification criterion is a threshold ratio between the distance calculated for the target person and the minimum of the distances calculated for the other known person.

15. The computer system of claim 12 wherein the codebook for an object is derived from the feature vectors of the person using vector quantization.

16. A computer system for verifying that a target image corresponds to a target person, comprising:

for each of a plurality of persons including the target 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;

a component that generates a target feature vector for the target image;

a component that for each person calculates the distance between the of the codebook for the person and the target feature vector; and

a component that, when the minimum of the distances satisfies an verification criterion, indicating that the target person can be verified as corresponding to the target image.

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

18. The computer system of claim 17 wherein the feature vector of the image is derived from the upper, left sub-matrix of a discrete cosine transform without the upper, left coefficient of the sub-matrix.

19. The computer system of claim 16 wherein the feature vector of an image is derived from a region of interest that includes the face of the person.

20. The computer system of claim 16 wherein a codebook of person is derived from feature vectors of images of the person using a vector quantization technique.