Recognition via high-dimensional data classification

• US 8,406,525 B2
• Filed: 01/29/2009
• Issued: 03/26/2013
• Est. Priority Date: 01/31/2008
• Status: Active Grant

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Board of Trustees of The University of Illinois, Regents of the University of California (University of California)
• Inventors: Ma, Yi, Yang, Allen Yang, Wright, John Norbert, Wagner, Andrew William
• Primary Examiner(s): Ahmed, Samir
• Assistant Examiner(s): LE, TOTAM HA
• Application Number:
  US12/865,639
• Publication Number:
  US 20110064302A1
• Time in Patent Office: 1,517 Days
• Field of Search: 382/191, 382/159
• US Class Current: 382/191
• CPC Class Codes: G06F 18/213 Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods
• CPC Class Codes: G06F 18/2413 based on distances to training or reference patterns
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 10/7715 Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods
• CPC Class Codes: G06V 40/169 Holistic features and representations, i.e. based on the facial image taken as a whole

Abstract

A method is disclosed for recognition of high-dimensional data in the presence of occlusion, including: receiving a target data that includes an occlusion and is of an unknown class, wherein the target data includes a known object; sampling a plurality of training data files comprising a plurality of distinct classes of the same object as that of the target data; and identifying the class of the target data through linear superposition of the sampled training data files using l¹ minimization, wherein a linear superposition with a sparsest number of coefficients is used to identify the class of the target data.

Claims

1. A computer-implemented method for recognition of high-dimensional data in the presence of occlusion, comprising:

receiving by a computer a target data that includes an occlusion and is of an unknown class, wherein the target data comprises a known object;

sampling with the computer a plurality of training data files comprising a plurality of distinct classes of the same object as that of the target data; and

identifying the class of the target data by the computer through linear superposition of the sampled training data files using l¹ minimization, wherein a linear superposition with a sparsest number of coefficients is used to identify the class of the target data.

2. The method of claim 1, wherein the plurality of training data files contain the target data, and wherein recognizing the class of the target data is through execution of an algorithm that includes l¹ minimization to remove the occlusion such that allows identification of the target data.

3. The method of claim 2, wherein the object of the target data comprises a test voice file and wherein the plurality of training data files comprise training voice files.

4. The method of claim 2, wherein the object of the target data comprises a test image (y) that is partially occluded with a plurality of pixels, and wherein the plurality of training data files comprises a plurality of training images.

5. The method of claim 4, wherein a single matrix (A) represents the sampled plurality of training images, and wherein the algorithm recovers a representation of the form y=Ax_o+e, wherein x_o comprises a solution that yields the sparsest number of coefficients, and wherein e comprises a vector of errors, which is also a sparse representation of y.

6. A computer-implemented method for recognition of high-dimensional data in the presence of occlusion, comprising:

receiving by a computer a test data (y) that includes an occlusion and which identity is unknown, wherein the test data comprises a known object;

sampling with the computer a plurality of labeled training data files represented by matrix A=[A₁ . . . A_k] that comprise a plurality (k) of distinct identities, wherein the sampled training data files are of the same object as that of y; and

expressing, with the computer, y as a sparse linear combination of the plurality of training data files (A) plus a sparse error (e) due to the occlusion using l¹-minimization, wherein the identity of the test data y is recognized by the computer.

7. The method of claim 6, wherein the object of the test data y comprises a test voice or audio file.

8. The method of claim 6, wherein the object of the test data y comprises a test image that is partially occluded with a plurality of pixels, and wherein the plurality of training data files comprises a plurality of training images.

9. The method of claim 8, wherein expressing y as a sparse linear combination of A and e comprises:

generating coefficients (x_o) such that y=Ax_o+e, wherein eε

^m comprises an error vector of non-zero entries in m space, and x_o and e comprise simultaneous sparse representations of y through l¹-minimization, wherein non-zero entries of eε

^m lie on a set of size ρ

m corresponding to the occluded pixels, where m comprises the total number of pixels in the test image and ρ

comprises a fraction corresponding to the number of occluded pixels.

10. A computer-implemented method for recognition of high-dimensional data in the presence of occlusion, comprising:

receiving by a computer a test data (y) that includes an occlusion and which identity is unknown, wherein the test data comprises a known object;

partitioning by the computer a plurality of n training samples into k classes to produce a matrix A=[A₁ . . . A_k], wherein the object of the training samples is the same as that of the test data y;

setting B=[A₁ . . . A_k I];

computing ŵ

₁=arg min_w=[xe]∥

w∥

₁ such that Bw=y by l¹ linear programming;

for i=1;

k, computing a residual r_i∥

y−

Aδ

_i({circumflex over (x)}₁)−

ê

₁∥

₂; and

outputting by the computer î

(y)=arg min_{i=1, . . . , k}^ri to assign y to a class whose coefficients best approximate it, thereby recognizing the identity of the test data y.

11. The method of claim 10, wherein the object of the test data y comprises a test voice or audio file.

12. The method of claim 10, wherein the object of the test data y comprises a test image that is at least partially occluded with a plurality of pixels, and wherein the plurality of n training samples comprises a plurality of training images.

13. The method of claim 10, wherein at least one class of the k classes of the n training samples comprises the test data y.

14. A system for recognition of high-dimensional data in the presence of occlusion, comprising:

a processor coupled with a memory;

a database coupled with the processor;

a user interface to receive a target data that includes an occlusion and that is of an unknown class, wherein the target data comprises a known object;

a feature extractor coupled with the database and the processor to sample a plurality of training data files comprising a plurality of distinct classes of the same object as that of the target data, wherein the database comprises the training data files;

an l¹ minimizer coupled with the processor to linearly superimpose the sampled training data files using l¹ minimization; and

a recognizer coupled with the l¹ minimizer to identify the class of the target data through use of the superimposed sampled training data files, wherein a linear superposition with a sparsest number of coefficients is used to identify the class of the target data.

15. The system of claim 14, wherein the l¹ minimizer executes an algorithm that includes l¹ minimization to remove the occlusion such that allows identification of the target data.

16. The system of claim 15, wherein the object of the target data comprises a test voice file and wherein the plurality of training data files comprise training voice files.

17. The system of claim 15, wherein the object of the target data comprises a test image (y) that is partially occluded with a plurality of pixels, and wherein the plurality of training data files comprises a plurality of training images.

18. The system of claim 17, wherein a single matrix (A) represents the sampled plurality of training images, the algorithm recovers a representation of the form y=Ax_o+e, wherein x_o comprises a solution that yields the sparsest number of coefficients, and wherein eε

^m comprises a vector of errors including a sparse representation of y, wherein non-zero entries of eε

^m lie on a set of size ρ

m corresponding to the occluded pixels, where m comprises the total number of pixels in y, and ρ

comprises a fraction corresponding to the number of occluded pixels.

19. A system for recognition of high-dimensional data in the presence of occlusion, comprising:

a processor coupled with a memory;

a database coupled with the processor, the database including a plurality of n training samples;

a user interface to receive a target data (y) that includes an occlusion and that is of an unknown class, wherein the target data comprises a known object;

a feature extractor coupled with the processor and the database to partition a plurality of n training samples into k classes to produce a matrix A=[A₁ . . . A_k], wherein the object of the training samples is the same as that of the test data y, wherein the feature extractor sets B=[A₁ . . . A_k I];

an l¹ minimizer coupled with the processor to;

compute ŵ

₁=arg min_w=[xe]∥

w∥

₁ such that Bw=y by l¹ linear programming;

for i=1;

k, compute a residual r_i=∥

y−

Aδ

_i({circumflex over (x)}₁)−

ê

₁∥

₂; and

a recognizer coupled with the l¹ linear minimizer to output î

(y)=arg min_{i=1, . . . , k}^ri and to assign y to a class whose coefficients best approximate it to thereby recognize the identity of the test data y.

20. The system of claim 19, wherein the object of the test data y comprises a test voice or audio file.

21. The system of claim 19, wherein the object of the test data y comprises a test image that is at least partially occluded with a plurality of pixels, and wherein the plurality of n training samples comprises a plurality of training images.

22. The system of claim 19, wherein at least one class of the k classes of the n training samples comprises the test data y.