Detection, recognition and coding of complex objects using probabilistic eigenspace analysis

• US 5,710,833 A
• Filed: 04/20/1995
• Issued: 01/20/1998
• Est. Priority Date: 04/20/1995
• Status: Expired due to Term

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Pentland, Alex, Moghaddam, Baback
• Primary Examiner(s): Johns, Andrew
• Assistant Examiner(s): Davis, Monica S.
• Application Number:
  US08/425,579
• Time in Patent Office: 1,006 Days
• Field of Search: 382/118, 382/228, 382/248, 382/205, 382/210, 382/203, 382/206
• US Class Current: 382/228
• CPC Class Codes: G06F 16/739 in form of a video summary, e.g. the video summary being a video sequence, a composite still image or having synthesized frames
• CPC Class Codes: G06F 18/213 Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods
• CPC Class Codes: G06V 40/16 Human faces, e.g. facial parts, sketches or expressions

Abstract

Methods and apparatus for detecting instances of a selected object or object feature in a digitally represented scene utilize analysis of probability densities to determine whether an input image (or portion thereof) represents such an instance. The invention filters images of objects that, although in some ways similar to the object under study, fail to qualify as typical instances of that object. The invention is useful in the detection and recognition of virtually any multifeatured entity such as human faces, features thereof (e.g., eyes), as well as non-rigid and articulated objects such as human hands.

Claims

1. A method for detecting selected features in digitally represented input images, the method comprising the steps of:

a. representing a training set of instances of the selected feature as a set of eigenvectors in a multidimensional image space;

b. representing portions of the input image as input vectors in the image space;

c. performing a density-estimation analysis on the input vectors to estimate, for each input vector, a probability level indicative of the likelihood that the input vector corresponds to an image portion containing an instance of the selected feature, wherein said density estimation analysis is based on all vector components; and

d. identifying image portions having the highest associated probability levels.

2. The method of claim 1 wherein the step of performing a density-estimation analysis comprises the steps of:

a. dividing the image space into a principal subspace and an orthogonal subspace, the principal subspace including a unimodal set of principal eigenvectors;

b. computing the distance between a point identified by an input vector and the principal subspace;

c. projecting the input vector onto the principal subspace;

d. computing the probability distribution of the input-vector projection with respect to the principal eigenvectors; and

e. estimating, from the computed distance and the computed probability distribution, the probability level indicative of the likelihood that the input vector corresponds to an image portion containing an instance of the selected feature.

3. The method of claim 2 wherein the estimating step comprises computing a first marginal probability density in the principal subspace and a second marginal probability density in the orthogonal subspace, the first density being a true density, the second density being an estimated density and the first and second densities being statistically consistent with one another, and multiplying the first and second densities.

4. The method of claim 1 wherein the step of performing a density-estimation analysis comprises the steps of:

a. dividing the image space into a principal subspace and an orthogonal subspace, the principal subspace including a multimodal set of principal eigenvectors;

b. computing the distance between a point identified by an input vector and the principal subspace;

c. projecting the input vector onto the principal subspace;

d. computing the probability distribution of the input-vector projection with respect to the principal eigenvectors using a parametric mixture model; and

e. estimating, from the computed distance and the computed probability distribution, the probability level indicative of the likelihood that the input vector corresponds to an image portion containing an instance of the selected feature.

5. The method of claim 1 further comprising a recognition step of determining, for each identified image portion, which one, if any, of a reference set of digitally represented instances of the selected feature the instance contained in the identified image portion resembles.

6. The method of claim 5 wherein the reference set of digitally represented instances is represented by a plurality of vectors in the principal subspace and the recognition step comprises projecting the input vector onto the principal subspace and locating the instance vector closest thereto.

7. The method of claim 1 further comprising the step of encoding each identified image portion as a set of quantized projection coefficients.

8. The method of claim 1 wherein the selected features are faces.

9. The method of claim 1 wherein the selected features are facial features.

10. An apparatus for detecting selected features in digitally represented input images comprising:

a. a computer memory for storing the input images;

b. means for representing a training set of instances of the selected feature as a set of eigenvectors in a multidimensional image space;

c. means for isolating at least a portion of the stored input image and representing it as an input vector in the image space; and

d. image processing means for performing a density-estimation analysis and analyzing an input vector to estimate, for each input vector, a probability level indicative of the likelihood that the input vector corresponds to an image portion containing an instance of the selected feature, wherein said density estimation analysis is based on all vector components.

11. The apparatus of claim 10 wherein each input is represented as a plurality of pixels, and further comprising:

a. means for representing the input image at a plurality of scales;

b. means for defining, for each scaled image, a window including a fixed number of pixels of the image, and transferring the contents of each window to the image-processing means to generate a probability level for each window; and

c. means for identifying the window having the highest associated probability.

12. The apparatus of claim 10 wherein the image-processing means is configured to:

a. divide the image space into a principal subspace and an orthogonal subspace, the principal subspace including a unimodal set of principal eigenvectors;

b. compute the distance between a point identified by an input vector and the principal subspace;

c. project the input vector onto the principal subspace;

d. compute the probability distribution of the input-vector projection with respect to the principal eigenvectors; and

e. estimate, from the computed distance and the computed probability distribution, the probability level indicative of the likelihood that the input vector corresponds to an image portion containing an instance of the selected feature.

13. The apparatus of claim 12 wherein the image-processing means estimates the probability level using maximum-likelihood analysis.

14. The apparatus of claim 10 further comprising means for identifying, based on probability level, at least one input vector likely to contain an instance of the selected feature.

15. The apparatus of claim 14 wherein the training set of feature instances are generated at a single viewing angle, and further comprising means for isolating and processing the input-image portion corresponding to each identified input vector, said means comprising:

a. means for normalizing the input-image portion with respect to translation and scale;

b. means for identifying a plurality of subfeatures in the input-image portion;

c. validation means for analyzing identified subfeatures for geometric consistency with a stored template;

d. warping means for spatially aligning validated input-image portions for consistency with the viewing angle; and

e. masking means for deleting those portions of the input image that do not correspond to the feature.

16. The apparatus of claim 15 further comprising contrast-normalization means for processing the masked image to compensate for variations in contrast.

17. The apparatus of claim 15 further comprising:

a. a database for storing each of the training images as a set of projection coefficients onto a set of eigenvectors;

b. identification means comprising (i) means for projecting the masked image onto the set of eigenvectors to obtain a set of input projection coefficients, and (ii) means for locating the training image whose projection coefficients most closely match the input projection coefficients.

18. The apparatus of claim 17 wherein the identification means includes means for computing a confidence level indicative of the degree to which the coefficients of the selected training image match the coefficients of the input projection.

19. The apparatus of claim 15 further comprising a reconstruction module for reconstructing the input image from the isolated and processed input-image portion.

20. The apparatus of claim 15 further comprising an encoder module that itself comprises:

a. means for projecting the masked image onto a set of eigenvectors to obtain a set of input projection coefficients; and

b. means for quantizing the input projection coefficients.