Method and system for pattern recognition based on dynamically constructing a subset of reference vectors

• US 5,933,806 A
• Filed: 08/28/1996
• Issued: 08/03/1999
• Est. Priority Date: 08/28/1995
• Status: Expired due to Fees

• Current Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Original Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Inventors: Ullrich, Meinhard D., Beyerlein, Peter
• Primary Examiner(s): Hudspeth, David R.
• Assistant Examiner(s): ABEBE, DANIEL DEMELASH
• Application Number:
  US08/704,201
• Time in Patent Office: 1,070 Days
• Field of Search: 704/256, 704/259, 704/251, 704/252
• US Class Current: 704/256.8
• CPC Class Codes: G10L 15/08 Speech classification or search
• CPC Class Codes: G10L 15/142 Hidden Markov Models [HMMs]

Abstract

A system and method are used for recognising a time-sequential input pattern (20), which is derived from a continual physical quantity, such as speech. The system has input means (30), which accesses the physical quantity and therefrom generates a plurality of input observation vectors. The input observation vectors represent the input pattern. A reference pattern database (40) is used for storing a plurality of reference patterns. Each reference pattern includes a sequence of reference units, where each reference unit is represented by at least one associated reference vector μ_a in a set {μ_a } of reference vectors. A localizer (50) is used for locating among the reference patterns stored in the reference pattern database (40), a recognised reference pattern, which corresponds to the input pattern. The locating includes selecting a subset {μ_s } of reference vectors from said set {μ_a } for each input observation vector o by calculating a measure of dissimilarity between the input observation vector o and each reference vector of the set {μ_a }. A number of reference vectors μ_a, whose measures of dissimilarity with said input observation vector o are the smallest, are used as the subset {μ_s } of reference vectors. The reference vectors of the subset {μ_s } are used to calculate for each reference pattern, a pattern similarity score. The recognised pattern is one of the reference patterns for which an optimum of the pattern similarity scores is calculated. Output means (70) are used for outputting the recognised pattern.

Claims

1. A method for recognising a time-sequential input pattern which is derived from a continual physical quantity, said method comprising the steps of:

accessing said physical quantity and therefrom generating a plurality of input observation vectors, representing said input pattern;

locating among a plurality of reference patterns a recognised reference pattern, which corresponds to said input pattern;

at least one reference pattern being a sequence of reference units, each reference unit being represented by at least one associated reference vector μ

_a in a set {μ

_a } of reference vectors, and said locating comprising selecting for each input observation vector o a subset {μ

_s } of reference vectors from said set {μ

_a } and calculating vector similarity scores between said input observation vector o and each reference vector μ

_s of said subset {μ

_s }, such that selecting a subset {μ

_s } of reference vectors for each input observation vector o comprises calculating a measure of dissimilarity between said input observation vector o and each reference vector of said set {μ

_a } and using as said subset {μ

_s } of reference vectors a number of reference vectors μ

_a, whose measures of dissimilarity with said input observation vector o are the smallest;

quantising each reference vector μ

_a to a quantised reference vector R(μ

_a), and

wherein selecting the subset {μ

_s } of reference vectors comprises, for each input observation vector o, the steps of;

quantising said input observation vector o to a quantised observation vector R(o),

calculating for said quantised observation vector R(o) distances d(R(o), R(μ

_a)) to each quantised reference vector R(μ

_a), and

using said distance d(R(o), R(μ

_a)) as said measure of dissimilarity between said input observation vector o and said reference vector μ

_a ; and

quantising a vector x which is one of a reference vector μ

_a or an observation vector o to a quantised vector R(x) comprising calculating a sign vector S(x) by assigning to each component of said sign vector a binary value, with a first binary value b1 being assigned if the corresponding component of the vector x has a negative value and a second binary value b2 being assigned if the corresponding component of the vector x has a positive value.

2. A method as claimed in claim 1, wherein said quantising further comprises calculating an L_r -norm of the vector x and multiplying said norm with said sign vector S(x).

3. A method as claimed in claim 2, wherein said quantising further comprises dividing said sign vector S(x) by the dimension of the vector x to the power 1/r.

4. A method as claimed in claim 2, wherein calculating said distances d(R(o), R(μ

_a)) comprises;

calculating the L_r -norm ∥

μ

_a ∥

_r of each vector μ

_a, and

for each input observation vector o;

calculating the L_r -norm ∥

o∥

_r of the vector o; and

calculating a Hamming distance H(S(o), S(μ

_a)) of the vector S(o) to each vector S(μ

_a).

5. A method as claimed in claim 1, wherein calculating said distance d(R(o), R(μ

_a)) comprises calculating a Hamming distance H(S(o), S(μ

_a)) of the vectors S(o) and S(μ

_a).

6. A method as claimed in claim 5, wherein calculating said Hamming distance H(S(o), S(μ

_a)) of the vectors S(o) and S(μ

_a) comprises;

calculating a difference vector by assigning to each component of said difference vector the binary XOR value of the corresponding components of S(o) and S(μ

_a);

determining a difference number by calculating how many components in said difference vector have the value one; and

using said difference number as the Hamming distance.

7. A method as claimed in claim 6, wherein:

said method comprises constructing a table specifying for each N-dimensional vector, with components having a binary value of zero or one, a corresponding number, indicating how many components have the value one; and

determining said difference number comprises locating said difference vector in said table and using said corresponding number as the Hamming distance.

8. A method as claimed in claim 1, wherein said method is adapted to, after having selected a subset of reference vectors for a predetermined input observation vector o, use the same subset for a number of subsequent observation vectors.

9. A method as claimed in claim 1, wherein said method comprises:

after selecting said subset of reference vectors for an input observation vector o, ensuring that each reference unit is represented by at least one reference vector in said subset, by adding for each reference unit, which is not represented, a representative reference vector to said subset.

10. A method as claimed in claim 9, wherein said method comprises:

after ensuring that each reference unit is represented by at least one reference vector in said subset, choosing for each reference unit said representative reference vector by selecting as the representative reference vector the reference vector from the subset, which represents said reference unit and has a smallest distance to said input observation vector o.

11. A system for recognising a time-sequential input pattern, which is derived from a continual physical quantity, said system comprising:

input means for accessing said physical quantity and therefrom generating a plurality of input observation vectors, representing said input pattern;

a reference pattern database for storing a plurality of reference patterns;

at least one reference pattern being a sequence of reference units, each reference unit being represented by at least one associated reference vector μ

_a in a set {μ

_a } of reference vectors;

a localizer for locating among the reference patterns stored in said reference pattern database a recognised reference pattern, which corresponds to said input pattern, said locating comprising selecting for each input observation vector o a subset {μ

_s } of reference vectors from said set {μ

_a } and calculating vector similarity scores between said input observation vector o and each reference vector μ

_s of said subset {μ

_s }; and

output means for outputting said recognised pattern;

wherein said selecting of a subset {μ

_s } of reference vectors for each input observation vector o comprises calculating a measure of dissimilarity between said input observation vector o and each reference vector of said set {μ

_a } and using as said subset {μ

_s } of reference vectors a number of reference vectors μ

_a, whose measures of dissimilarity with said input observation vector o are the smallest; and

wherein said reference pattern database further stores for each reference vector μ

_a a quantised reference vector R(μ

_a), and selecting the subset {μ

_s } of reference vectors comprises for each input observation vector o means for executing the steps of;

quantising said input observation vector o to a quantised observation vector R(o),

calculating for said quantised observation vector R(o) distances d(R(o), R(μ

_a)) to each quantised reference vector R(μ

_a), and

using said distance d(R(o), R(μ

_a)) as said measure of dissimilarity between said input observation vector o and said reference vector μ

_a ; and

means for quantising a vector x which is one of a reference vector μ

_a or an observation vector o as a quantised vector R(x) is proportional to a sign vector S(x), each component of said sign vector S(x) comprising a first binary value b1 if the corresponding component of the vector x has a negative value and a second binary value b2 if the corresponding component of the vector x has a positive value.

12. A system as claimed in claim 11, wherein said quantised vector R(x) is proportional to an L_r -norm of the vector x.

13. A system as claimed in claim 12, wherein:

for each reference vector μ

_a the reference pattern database comprises the L_r -norm ∥

μ

_a ∥

_r of the reference vector μ

_a ; and

said localizer calculates said distances d(R(o), R(μ

_a)) by, for each input observation vector o;

calculating the L_r -norm ∥

o∥

_r of the vector o and a Hamming distance H(S(o), S(μ

_a)) of the vector S(o) to each vector S(μ

_a), and

combining the L_r -norm ∥

o∥

_r and the Hamming distance H(S(o), S(μ

_a)) with the L_r -norm ∥

μ

_a ∥

_r stored in said reference pattern database.

14. A system as claimed in claim 11, wherein calculating said distance d(R(o), R(μ

_a)) comprises calculating a Hamming distance H(S(o), S(μ

_a)) of the vectors S(o) and S(μ

_a).

15. A system as claimed in claim 14, wherein calculating said Hamming distance H(S(o), S(μ

_a)) of the vectors S(o) and S(μ

_a) comprises;

calculating a difference vector by assigning to each component of said difference vector the binary XOR value of the corresponding components of S(o) and S(μ

_a);

determining a difference number by calculating how many components in said difference vector have the value one, and

using said difference number as the Hamming distance.

16. A system as claimed in claim 15, wherein:

said system comprises a memory for storing a table specifying for each N-dimensional vector, with components having a binary value of zero or one, a corresponding number, indicating how many components have the value one; and

determining said difference number comprises locating said difference vector in said table and using said corresponding number as the Hamming distance.

17. A system as claimed in claim 11, wherein said localizer, after having selected a first corresponding subset of reference vectors for a predetermined input observation vector o, uses said first subset as said corresponding subset of reference vectors for a number of successive observation vectors.

18. A system as claimed in claim 17, wherein said localizer, after selecting said subset of reference vectors for an input observation vector o, ensures that each reference unit is represented by at least one reference vector in said subset, by adding for each reference unit, which is not represented, a representative reference vector to said subset.

19. A system as claimed in claim 18, wherein said localizer, after ensuring that each reference unit is represented by at least one reference vector in said subset, chooses for each reference unit said representative reference vector by selecting as the representative reference vector the reference vector from the subset, which represents said reference unit and has a smallest distance to said input observation vector o.