Recognition and classification based on principal component analysis in the transform domain

• US 7,724,960 B1
• Filed: 09/08/2006
• Issued: 05/25/2010
• Est. Priority Date: 09/08/2006
• Status: Expired due to Fees

• Current Assignee: University of Central Florida Research Foundation Inc. (State University System of Florida)
• Original Assignee: University of Central Florida Research Foundation Inc. (State University System of Florida)
• Inventors: Abdelwahab, Moataz M., Mikhael, Wasfy B.
• Primary Examiner(s): Mehta; Bhavesh M
• Assistant Examiner(s): ZARKA, DAVID PETER
• Application Number:
  US11/518,354
• Time in Patent Office: 1,355 Days
• Field of Search: 382/190
• US Class Current: 382/190
• CPC Class Codes: G06F 18/2135 based on approximation criteria, e.g. principal component analysis
• CPC Class Codes: G06V 10/50 by performing operations within image blocks; by using histograms, e.g. histogram of oriented gradients [HoG]; by summing image-intensity values; Projection analysis
• 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

Abstract

Methods, system apparatus and devices for classification and recognition that is based on principal component analysis and is implemented in the transform domain using the fast two-dimensional PCA to processes the signal in the transform domain. The signal is represented with a reduced number of coefficients, therefore reducing the storage requirements and computational complexity while yielding high recognition accuracy.

Claims

1. A method for a processor in a computer system executing a set of instructions to recognize images comprising the steps of:

extracting plural features from a set of N training images stored in a database on the computer system comprising the steps of;

computing a covariance matrix S for the set of N training images;

applying a discrete cosine transform to the covariance matrix S to obtain T according to T=Tr{S};

determining a covariance submatrix S′

of significant coefficients to replace the covariance matrix S;

obtaining a set of k′

eigen values for S′

;

applying a discrete cosine transform to each image of the set of N training images to obtain submatrix T_i′

=Tr{A_i′

};

selecting a submatrix A_i′

from the submatrix T_i′

to represent the set of training images N; and

calculating a feature matrix B_i′

of the set of N training images;

receiving an unknown image At; and

identifying the unknown image At using the plural extracted features, wherein the identification is accomplished in a transform domain using two-dimensional principal analysis.

2. The method of claim 1, wherein the computing a covariance matrix S computation step comprises the step of:

computing a covariance matrix S according to

$S;<br><br>=\frac{1}{N}·<br><br>\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>{\left[{\left(A_i-\stackrel{\_}{A}\right)}^T·<br><br>\left(A_i-\stackrel{\_}{A}\right)\right]}^{-}.$

3. The method of claim 1, wherein the step of determining a covariance submatrix S′

of significant coefficients comprises the steps of;

selecting a submatrix S′

of covariance matrix S containing significant coefficients of T; and

substituting S′

for S.

4. The method of claim 3, further comprising the step of:

selecting the submatrix S′

having a dimension less than 10×

10.

5. The method of claim 4, further comprising the step of:

selecting the submatrix S′

having a dimension of 5×

5.

6. The method of claim 1, wherein the feature matrix B_i′

calculation step comprises the step of;

calculating feature matrix B_t′

for the set of N training image using

Y_j,i=A_i′

V_j′

j=1, 2, . . . k′ and

i=1, 2, . . . N

B_i′

=[Y_1,i′

, Y_2,i′

, . . . Y_k′

,_i′

].

7. The method of claim 1, wherein the identification step comprises the steps of:

applying a discrete cosine transform to the unknown image At to obtain a training matrix T_t′

;

obtaining a submatrix At′

(l′

×

n′

) from the training matrix T_t′

;

calculating a feature matrix B_t′

for the unknown image At; and

computing an Euclidean distance between the feature matrix B_t′

of the unknown image At and a feature matrix B_i′

of the set of N training images, wherein a predetermined minimum distance is used to identify the unknown image At.

8. The method of claim 7, wherein the feature matrix calculation step comprises the step of:

calculating the feature matrix B_t′

for the unknown image At according to

Y_j,t′

=A_t′

V_j′

j=1, 2, . . . k′

B_t′

=[Y_1t′

, Y_2,t′

, . . . Y_k′

,_t′

].

9. A recognition system comprising:

a processor for processing a set of instructions;

a training set of instructions for extracting plural features of a set of N training images from a data base, the training set of instructions comprising;

a first subset of training instructions for computing a covariance matrix for the set of training images N;

a second subset of training instructions for applying a discrete cosine transform to the covariance matrix according to T=Tr{S}

a third subset of training instructions for determining a covariance submatrix S′

of significant coefficients to replace the covariance matrix S;

a fourth subset of training instructions for obtaining a set of k′

eigenvalues for S′

;

a fifth subset of training instructions for applying a discrete cosine transform to each image of the set of training images N to obtain submatrix T_i′

=Tr{A_i′

};

a sixth subset of training instructions for selecting a submatrix A_i′

from the submatrix T_i′

to represent the set of training images N; and

a seventh subset of training instructions for calculating a feature matrix B_i′

of the set of N training images; and

a testing set of instructions for classification and identification of an unknown image according to the plural extracted features, wherein recognition of the unknown image is accomplished in a transform domain using two-dimensional principal analysis.

10. The system of claim 9, wherein the first subset of training instructions comprises:

a sub-subset of instructions for computing the covariance matrix according to

$S;<br><br>=\frac{1}{N}·<br><br>\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>{\left[{\left(A_i-\stackrel{\_}{A}\right)}^T·<br><br>\left(A_i-\stackrel{\_}{A}\right)\right]}^{-}$

where A is the mean matrix of the set of training images N.

11. The system of claim 9, wherein the seventh subset of instructions comprises:

a sub-subset of instructions for calculating feature matrix B_t′

for the set of training images N is calculated according to

Y_j,i′

=A_i′

V_j′

j=1, 2, . . . k′ and

i=1, 2, . . . N

B_t′

=[Y_1,i′

, Y_2,i′

, . . . Y_k′

,_i′

].

12. The system of claim 9, wherein the testing set of instructions comprises:

a first subset of testing instructions for applying a discrete cosine transform to the unknown image At to obtain a training matrix;

a second subset of testing instructions for obtaining a submatrix At′

(l′

×

n′

) from the training matrix T_t′

;

a third subset of testing instructions for calculating a feature matrix B_t′

for the unknown image; and

a fourth subset of testing instructions for computing an Euclidean distance between the feature matrix B_t′

of the unknown image and a feature matrix B_t′

of the set of testing images, wherein a minimum distance is used to identify the unknown image.

13. The system of claim 9, wherein said unknown image is one-dimensional.

14. The system of claim 9, wherein said unknown image is multi-dimensional.