Method of processing signal data on the basis of principal component transform, apparatus for performing the method

• US 5,583,951 A
• Filed: 08/31/1994
• Issued: 12/10/1996
• Est. Priority Date: 03/30/1990
• Status: Expired due to Fees

• Current Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Original Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Inventors: Sirat, Jacques A., Zwierski, Didier E.
• Primary Examiner(s): Mancuso, Joseph
• Assistant Examiner(s): SHALWALA, BIPIN H
• Application Number:
  US08/298,920
• Time in Patent Office: 832 Days
• Field of Search: 382/41, 382/42, 382/54, 382/56, 382/276, 382/277, 382/254, 382/232, 382/233, 382/235, 348/395, 348/400, 348/403, 364/725, 364/731
• US Class Current: 382/232
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06F 18/2135 based on approximation criteria, e.g. principal component analysis

Abstract

A method is proposed for determining approximations of eigenvectors of a covariance matrix associated with signal data on the basis of the Principal Component Transform. Successive iterations on estimates enhance the development into the direction of the principal component considered. The method is applicable to the Singular Value Decomposition of data matrices. The operations to be performed are similar to those required in a neural net for adapting the synaptic coefficients, Apparatus are proposed for performing the method.

Claims

1. Method of compressing signals generated from and representing an image or speech on the basis of a Principal Component Transform, comprising:

determining an approximation of a statistically most significant eigenvector of a covariance matrix associated with signal data generated from and representing an image or speech represented in a vector space,

taking an initial vector in said vector space as a first estimate;

for each next estimate determining a linear combination of the preceding estimate and a next vector in said vector space, said next vector being weighted with a factor that depends on an inproduct of the preceding estimate and said next vector for enhancing the next estimate into a direction of the preceding estimate,

upon termination of determining next estimates taking said approximation parallel to the last obtained estimate, to produce a compressed signal representing the same image or speech.

2. A method of processing electrical data signals generated from and representing images or speech, using a digital data processing apparatus, to provide a revised representation of the image-representing electrical signals for use in compressing the electrical data signals, or for extracting features of the electrical data signals, or for modifying the electrical data signals to represent a rotation of the image, the method comprising the steps of

a) using the digital data processing apparatus, creating a covariance matrix representation of the electrical data signals;

b) using the digital data processing apparatus, determining an approximation of at least a most significant eigenvector of the covariance matrix, the determining including;

i) choosing an arbitrary vector as a first estimate;

ii) creating a next estimate by determining a linear combination of a preceding estimate and a next vector, which linear combination includes weighing the next vector with a factor that depends on an inner product of the preceding estimate and said next vector, to enhance the next vector in a direction of the preceding estimate; and

iii) after at least one application of step b) ii), using a last obtained value of the next estimate as the approximation; and

c) providing electrical signals representing the eigenvectors as the revised representation of the images or speech for further processing.

5. Method as claimed in claim 2, characterized in that a determination of a further approximation of a further eigenvector of the covariance matrix includes the steps of:

taking as a first further estimate an initial further vector, that lies in a subspace of the vector space, said subspace being orthogonal to the previously determined approximations of the respective eigenvectors,

for each next further estimate determining a linear combination of the preceding further estimate and a next further vector in said subspace, said next further vector being weighted with a factor depending on an inner product of the preceding further estimate and the next further vector for enhancing the next further estimate component into a direction of the preceding further estimate,

upon termination of determining next further estimates taking the further approximation parallel to the last obtained further estimate.

6. Method as claimed in claim 2, characterized in that a determination of a further approximation of a further eigenvector of the covariance matrix includes the steps of:

taking as a first further estimate an initial further vector that lies in a region of the vector space that is determined by vectors that have an absolute inner product value with each previously determined respective approximation smaller than a predetermined respective value;

for each next further estimate determining a linear combination of the preceding further estimate and a next further region vector, said next further region vector being weighted with a factor estimate and the next further vector, for enhancing the next further estimate into a direction of the preceding further estimate;

upon termination of determining next further estimates orthogonalizing the last obtained further estimate with respect to each previously determined approximation;

taking the further approximation parallel to said orthogonalized last obtained further estimate.

9. Method as claimed in claim 2, characterized in that said factor is the sign-function operating on the relevant inner product.

10. Method as claimed in claim 2, characterized in that said factor is the sign-function operating on the relevant inner product when the inner product has a value outside a predetermined interval around zero, and in that said factor equals zero when the inner product has a value within the interval.

11. Method as claimed in claim 9, characterized in that the inner product involving each next vector or each next further vector has an absolute value greater than a predetermined non-zero lower bound.

12. Method as claimed in claim 2, comprising approximating an eigenvalue, associated with a particular eigenvector of the covariance matrix, characterized in that the approximating includes the steps of:

normalizing the last obtained estimate, associated with the particular eigenvector, onto unity,

determining a summation of squares of the inproducts, each respective inner product involving the normalized estimate and the respective vector, used for producing a respective estimate, and averaging a summation result.

3. A method for processing electrical data signals generated from and representing images or speech, using a digital data processing apparatus, to provide a revised representation of the electrical data signals for use in compressing the electrical data signals, or for extracting features of the electrical data signals, or for modifying the electrical data signals to represent a rotation of the image, the method comprising the steps of

a) using the digital data processing apparatus, providing signals representing an initial output vector as a representation of the image data signals as a first output estimate of a first output base vector;

b) using the digital data processing apparatus, providing signals representing an initial input vector as a representation of image signals in an input space and as a first input estimate of a first input base vector, which initial input vector is substantially linearly related to the initial output vector;

c) using the digital data processing apparatus, creating a next output estimate by providing signals representing a linear combination of a preceding estimate and a next output vector, which linear combination includes weighing the next output vector with a factor that depends on an inner product of the preceding estimate and said next output vector, to enhance the next vector in a direction of the preceding estimate;

d) using digital data processing apparatus, creating a next input estimate by providing signals representing a linear combination of a preceding input estimate and a next input vector, which linear combination includes weighing the next input vector with said factor, in order to keep the next output estimate substantially linearly related to the next input estimate;

e) after at least one application of steps c) and d), using the digital data processing apparatus, providing signals representing a normalization of a last obtained value of the next input estimate and the next output estimate onto a unit length, to yield the first input base vector and the first output base vector, respectively,

f) using the digital data processing apparatus, providing signals representing the input and output base vectors as the revised representation of the images or speech for further processing.

7. Method as claimed in claim 3, characterized in that a determination of a further output base vector and a related further input base vector includes the steps of:

taking as a first further output estimate an initial further output vector that lies in a subspace in said output space orthogonal to the previously determined output base vectors,

taking as a first further input estimate an initial further input vector related to said initial further output vector;

for each next further output estimate determining a linear combination of the preceding further output estimate and a next further output vector of said subspace, the next further output vector being weighted with a next factor depending on an inner product of the preceding further output estimate and said next further output vector for enhancing the next further estimate into a direction of the preceding further output estimate;

for each next further input estimate determining a linear combination of the preceding further input estimate and a next further input vector related to the next further output vector, the next further input vector being weighted with said next factor for keeping the next further output estimate substantially linearly related to the next further input estimate;

upon termination of determining a next further output estimate and a next further input estimate normalizing the last obtained output estimate and the last obtained input estimate onto unit length for producing the further output base vector and the further input base vector, respectively.

8. Method as claimed in claim 3, characterized in that a determination of a further output base vector and a related further input base vector includes the steps of:

taking as a first further output estimate an initial further output vector that lies in a region of the output vector space that is determined by output vectors that have an absolute inproduct value with each previously determined respective output base vector smaller than a predetermined respective value;

taking as a first further input estimate an initial further input vector related to said initial further output vector;

for each next further output estimate determining a linear combination of the preceding further output estimate and a next further output vector of said region, the next further output vector being weighted with a next factor depending on an inner product of the preceding further output estimate and said next further output vector for enhancing the next further output estimate onto a direction of the preceding further output estimate;

for each next further input estimate determining a linear combination of the preceding further input estimate and a next further input vector related to the next further output vector, the next further input vector being weighted with said next factor for keeping the next further output estimate substantially linearly related to the next further input estimate;

upon termination of determining a next further output estimate and a next further input estimate normalizing the last obtained further output estimate and the last obtained further input estimate onto unit length for producing the further output base vector and the further input base vector, respectively.

13. Method as claimed in claim 3 including a determination of a singular value associated with a particular output base vector and a related particular input base vector, characterized in that the method includes the steps of:

determining respective first inner product values of the particular output base vector with each respective output vector considered in particular iterations producing the particular output base vector;

determining respective second inner product values of the particular input base vector with each respective input vector related to the respective output vector considered;

calculating an average for a quotient of a first inner product value divided by an associated second inner product value.

14. Method as claimed in claim 3 characterized in that said factor is the sign-function operating on the relevant inner product.

15. Method as claimed in claim 3, characterized in that said factor is the sign-function operating on the relevant inner product when the inner product has a value outside a predetermined interval around zero, and in that said factor equals zero when the inner product has a value within the interval.

16. Method as claimed in claim 14, characterized in that the inner product involving each next vector or each next further vector has an absolute value greater than a predetermined non-zero lower bound.

4. Method of compressing signals generated from and representing images or speech utilizing the Singular Value Decomposition, comprising:

a. representing said signal data by input vectors in an input vector space and output vectors in an output space, each output vector being substantially linearly related to a respective input vector,

b. taking an initial output vector as a first output estimate for a first output base vector;

taking an initial input vector related to said output vector as a first input estimate for a first input base vector;

c. for each next output estimate determining a linear combination of the preceding output estimate and a next output vector, the latter being weighted with a factor depending on an inproduct of the preceding output estimate and said next output vector for enhancing the next output estimate into a direction of the preceding output estimate;

d. for each next input estimate determining a linear combination of the preceding input estimate and a next input vector, the latter being weighted with said factor for keeping the next output estimate substantially linearly related to the next input estimate;

e. upon termination of determining a next output estimate and a next input estimate normalizing the last obtained output estimate and the last obtained input estimate onto unit length for producing the first output base vector and the first input base vector, respectively, and providing the first output base vector as output signals for use in deriving a compression representation.