Method of recognition of human motion, vector sequences and speech

• US 7,366,645 B2
• Filed: 05/01/2003
• Issued: 04/29/2008
• Est. Priority Date: 05/06/2002
• Status: Expired due to Fees

• Current Assignee: Jezekiel Ben-Arie
• Original Assignee: Jezekiel Ben-Arie
• Inventors: Ben-Arie, Jezekiel
• Primary Examiner(s): Rodriguez; Paul
• Assistant Examiner(s): PROCTOR, JASON SCOTT
• Application Number:
  US10/427,882
• Publication Number:
  US 20030208289A1
• Time in Patent Office: 1,825 Days
• Field of Search: 703/6, 703/11, 703/2, 706/246
• US Class Current: 703/6
• CPC Class Codes: G06F 3/011 Arrangements for interaction with the human body, e.g. for user immersion in virtual reality blind teaching G09B21/00
• CPC Class Codes: G06V 40/20 Movements or behaviour, e.g. gesture recognition recognition of facial expressions G06V40/16
• CPC Class Codes: G10L 15/142 Hidden Markov Models [HMMs]

Abstract

A method for recognition of an input human motion as being the most similar to one model human motion out of a collection of stored model human motions. In the preferred method, both the input and the model human motions are represented by vector sequences that are derived from samples of angular poses of body parts. The input and model motions are sampled at substantially different rates. A special optimization algorithm that employs sequencing constraints and dynamic programming, is used for finding the optimal input-model matching scores. When only partial body pose information is available, candidate matching vector pairs for the optimization are found by indexing into a set of hash tables, where each table pertains to a sub-set of body parts. The invention also includes methods for recognition of vector sequences and for speech recognition.

Claims

1. A method of recognizing and classifying an input record of human movements as a member of a class of records of model human activity A_j in a collection of classes of records of model human activities {A_j}, comprising:

(a) predetermining and recording said collection of classes of records of model human activities {A_j};

(b) obtaining from each said class of records of model human activity A_j at least one model sample;

(c) representing each said model sample by a model vector m_rj;

(d) representing each said class of records of model human activity A_j by a model vectors sequence M_j=(m_lj . . . m_rj . . . m_qj), wherein each said model vector m_rj in said model vectors sequence M_j corresponds to said model sample and wherein the subscript q denotes the total number of model vectors in said model vectors sequence M_j, and wherein the subscript r denotes the location of said model vector m_rj within said model vectors sequence M_j and wherein the subscript j denotes the serial number of said model vectors sequence M_j and also denotes the same serial number of the corresponding said class of records of model human activity A_j;

(e) representing said collection of classes of records of model human activities {A_j} by a collection of corresponding model vectors sequences {M_j};

(f) constructing a table with multidimensional addressing of table bins;

(g) predetermining a distance threshold value;

(h) storing each of said model vector m_rj in a table bin whose address has a multidimensional value which has the smallest multidimensional distance to a multidimensional value of said model vector m_rj;

(i) obtaining from said input record of human movements at least one input sample;

(j) representing each of said input sample by an input vector t_nk;

(k) representing said input record of human movements by an input vectors sequence T_k =(t_lk . . . t_nk . . . t_pk), wherein the subscript p denotes the total number of the input vectors in said input vectors sequence T_k, and wherein the subscript n denotes the location of said input vector t_nk within said input vectors sequence T_k, and wherein the subscript k denotes a serial number of said input vectors sequence;

(l) for each said input vector t_nk selecting all the table bins with multidimensional address values which have multidimensional distances to the multidimensional value of said input vector t_nk, which are below said distance threshold value;

(m) for each selected said table bin, retrieving all said model vectors m_rj that were stored in said selected said table bin;

(n) employing a matching algorithm that uses said input vectors sequence T_k and the retrieved said model vectors m_rj, to produce a collection of matching scores {S_kj}, wherein each matching score S_kj denotes the degree of similarity between said input vectors sequence T_k and one said model vectors sequence M_j, which is a member of said collection of model vectors sequences {M_j};

(o) recognizing and classifying said input record of human movements as a member of said class of records of model human activity A_j which is represented by said model vectors sequence M_j with the highest said matching score S_kj in said collection of matching scores {S_kj};

(p) adding information about said class of records of model human activity A_j that was selected, to contents of said input record of human movements and providing a combined input record of human movements as an output record.

2. The method of claim 1, wherein said matching algorithm further comprises:

(a) for each input vector t_nk in said input vectors sequence T_k using all said retrieved said model vectors m_rj to construct a set of vector pairs {(t_nk, m_rj)};

(b) for each vector pair (t_nk, m_rj) within said set of vector pairs {(t_nk, m_rj)}, computing a pair matching score that is a function of the multidimensional values of the two vectors in the pair and reflects said vector pair matching quality;

(c) obtaining a set of valid pair sequences, which is constructed only from sequences of vector pairs that have mutual sequential relation, and wherein said mutual sequential relation between any two said vector pairs . . . (t_nk, m_rj) . . . (t_ck, m_ej) . . . included in a valid pair sequence, fulfills the following four conditions;

(I) c is not equal to n;

(II) if c>

n then r≦

e; and

(III) if c<

n then e≦

r and (IV) all said model vectors included in one said valid pair sequence are components of one said model vectors sequence M_j;

(d) computing for each said valid pair sequence, a sequence matching score, wherein said sequence matching score is a function of all said pair matching scores that correspond to said vector pairs that are components of said valid pair sequence;

(e) for each said model vectors sequence M_j,finding a set of said valid pair sequences that includes all said valid pair sequences which are constructed from model vectors included in said model vectors sequence M_j;

(f) for each said model vectors sequence M_j,finding a set of sequence matching scores, wherein each member of said set of sequence matching scores corresponds to said valid pair sequence which is a member of said set of said valid pair sequences, which are constructed from pairs of said input vectors and said model vectors included in said model vectors sequence M_j;

(g) for each said set of sequence matching scores that pertains to said model vectors sequence M_j, denoting the highest said sequence matching score as said matching score S_kj of said model vectors sequence M_j;

(h) defining said collection of matching scores {S_kj} as the collection of said matching scores S_kj of all said model vectors sequences M_j which are included in said collection of model vectors sequences {M_j};

(i) providing said collection of matching scores {S_kj} as the output of said matching algorithm.

3. The method of claim 2 wherein recorded data in said input records of human movements and in said records of model human activity, includes derived data from at least one trajectory of human body part.

4. The method of claim 3 wherein said derived data includes three dimensional orientations and positions and derivatives of said three dimensional orientations and positions derived from at least one said trajectory of human body part.

5. The method of claim 4 wherein for each said model vectors sequence M_j in said collection of model vectors sequences {M_j}, applying the principles of dynamic programming in computing said highest said sequence matching score in said set of sequence matching scores that pertains to said model vectors sequence M_j.

6. The method of claim 1, wherein said matching algorithm further comprises:

(a) for each input vector t_nk in said input vectors sequence T_k using all said retrieved said model vectors m_rj to construct a set of vector pairs {(t_nk, m_rj)};

(b) for each vector pair (t_nk, m_rj) within said set of vector pairs {(t_nk, m_rj)}, computing a pair matching score that is a function of the multidimensional values of the two vectors in the pair and reflects said vector pair matching quality;

(c) obtaining a set of valid pair sequences, which is constructed only from sequences of vector pairs that have mutual sequential relation, and wherein said mutual sequential relation between any two said vector pairs . . . (t_nk, m_rj) . . . (t_ck, m_ej) included in a valid pair sequence, fulfills the following four conditions;

(I) r is not equal to e, (II) if e>

r, then n≦

c, and (III) if e<

r then c≦

n, (IV) all said model vectors included in one said valid pair sequence are components of one said model vectors sequence M_j;

(d) computing for each said valid pair sequence, a sequence matching score, wherein said sequence matching score is a function of all said pair matching scores that correspond to said vector pairs that are components of said valid pair sequence;

(e) for each said model vectors sequence M_j,finding a set of said valid pair sequences that includes all said valid pair sequences which are constructed from model vectors included in said model vectors sequence M_j;

(f) for each said model vectors sequence M_j,finding a set of sequence matching scores, wherein each member of the said set of sequence matching scores corresponds to said valid pair sequence which is a member of said set of said valid pair sequences, which are constructed from pairs of said input vectors and said model vectors included in said model vectors sequence M_j;

(g) for each said set of sequence matching scores that pertains to said model vectors sequence M_j, denoting the highest said sequence matching score as said matching score S_kj of said model vectors sequence M_j;

(h) defining said collection of matching scores {S_kj} as the collection of said matching scores S_kj of all said model vectors sequences M_j which are included in said collection of model vectors sequences {M_j};

(i) providing said collection of matching scores {S_kj} as the output of said matching algorithm.

7. The method of claim 6 wherein recorded data in said input records of human movements and in said records of model human activity, includes derived data from at least one trajectory of human body part.

8. The method of claim 7 wherein said derived data includes three dimensional orientations and positions and derivatives of said three dimensional orientations and positions, derived from at least one said trajectory of human body part.

9. The method of claim 8 wherein for each said model vectors sequence M_j in said collection of model vectors sequences {M_j}, applying the principles of dynamic programming in computing said highest said sequence matching score in said set of sequence matching scores that pertains to said model vectors sequence M_j.

10. A method of recognizing and classifying a record of input signals as a member of a class of records of model signals A_j in a collection of classes of records of model signals {A_j}, comprising:

(a) predetermining and recording said collection of classes of records of model signals {A_j};

(b) obtaining from each said class of records of model signals A_j at least one model sample;

(c) representing each said model sample by a model vector m_rj;

(d) representing each said class of records of model signals by a model vectors sequence M_j=(m_lj . . . m_rj . . . m_qj), wherein each said model vector m_rj in said model vectors sequence M_j corresponds to said model sample and wherein the subscript q denotes the total number of model vectors in said model vectors sequence M_j, and wherein the subscript r denotes the location of said model vector m_rj within said model vectors sequence M_j and wherein the subscript j denotes the serial number of said model vectors sequence M_j and also denotes the same serial number of the corresponding said class of records of model signals A_j;

(e) representing said collection of classes of records of model signals {A_j} by a collection of corresponding model vectors sequences {M_j};

(f) constructing a table with multidimensional addressing of table bins;

(g) predetermining a distance threshold value;

(h) storing each of said model vector m_rj in a table bin whose address has a multidimensional value which has the smallest multidimensional distance to a multidimensional value of said model vector m_rj;

(i) obtaining from said record of input signals at least one input sample;

(j) representing each of said input sample by an input vector t_nk;

(k) representing said record of input signals by an input vectors sequence T_k=(t_lk . . . t_nk . . . t_pk), wherein the subscript p denotes the total number of the input vectors in said input vectors sequence, and wherein the subscript n denotes the location of said input vector t_nk within said input vectors sequence T_k, and wherein the subscript k denotes a serial number of said input vectors sequence;

(l) for each said input vector t_nk selecting all the table bins with multidimensional address values which have multidimensional distances to the multidimensional value of said input vector t_nk, which are below said distance threshold value;

(m) for each selected said table bin, retrieving all said model vectors m_rj that were stored in said selected said table bin;

(n) employing a matching algorithm that uses the retrieved said model vectors m_rj and said input vectors sequence T_k, to produce a collection of matching scores {S_kj}, wherein each matching score S_kj denotes the degree of similarity between said input vectors sequence T_k and one said model vectors sequence M_j, which is a member of said collection of model vectors sequences {M_j};

(o) recognizing and classifying said record of input signals as a member of said class of records of model signals A_j which is represented by said model vectors sequence M_j that has the highest said matching score S_kj in said collection of matching scores {S_kj};

(p) adding information about said class of records of model signals A_j that was selected, to contents of said record of input signals and providing a combined record of input signals as an output record.

11. The method of claim 10, wherein said matching algorithm further comprises:

(a) for each input vector t_nk in said input vectors sequence T_k using all said retrieved said model vectors m_rj to construct a set of vector pairs {(t_nk, m_rj)};

(b) for each vector pair (t_nk, m_rj) within said set of vector pairs {(t_nk, m_rj)}, computing a pair matching score that is a function of the multidimensional values of the two vectors in the pair and reflects said vector pair matching quality;

(c) obtaining a set of valid pair sequences, which is constructed only from sequences of vector pairs that have mutual sequential relation, and wherein said mutual sequential relation between any two said vector pairs . . . (t_nk, m_rj) . . . (t_ck, m_ej) . . . included in a valid pair sequence, fulfills the following four conditions;

(I) c is not equal to n;

(II) if c>

n then r≦

e; and

(III) if c<

n then e≦

r and (IV) all said model vectors included in one said valid pair sequence are components of one said model vectors sequence M_j;

(d) computing for each said valid pair sequence, a sequence matching score, wherein said sequence matching score is a function of all said pair matching scores that correspond to said vector pairs that are components of said valid pair sequence;

(e) for each said model vectors sequence M_j, finding a set of said valid pair sequences that includes all the said valid pair sequences which are constructed from model vectors included in said model vectors sequence M_j;

(f) for each said model vectors sequence M_j, finding a set of sequence matching scores, wherein each member of the said set of sequence matching scores corresponds to said valid pair sequence which is a member of said set of said valid pair sequences, which are constructed from pairs of said input vectors and said model vectors included in said model vectors sequence M_j;

(g) for each said set of sequence matching scores that pertains to said model vectors sequence M_j, denoting the highest said sequence matching score as said matching score S_kj of said model vectors sequence M_j;

(h) defining said collection of matching scores {S_kj} as the collection of said matching scores S_kj of all said model vectors sequences M_j which are included in said collection of model vectors sequences {M_j};

(i) providing said collection of matching scores {S_kj} as the output of said matching algorithm.

12. The method of claim 11 wherein recorded data in said records of input signals and in said records of model signals, includes data derived from at least one speech signal.

13. The method of claim 12 wherein for each said model vectors sequence M_j in said collection of model vectors sequences {M_j}, applying the principles of dynamic programming in computing said highest said sequence matching score S_kj in said set of sequence matching scores that pertains to said model vectors sequence M_j.

14. The method of claim 11 wherein each of said signal is derived from at least one source, wherein each said source emits signals selected from the group consisting of continuous signals and discrete signals.

15. The method of claim 14 wherein for each said model vectors sequence M_j in said collection of model vectors sequences {M_j}, applying the principles of dynamic programming in computing said highest said sequence matching score in said set of sequence matching scores that pertains to said model vectors sequence M_j.

16. The method of claim 10, wherein said matching algorithm further comprises:

(a) for each input vector t_nk in said input vectors sequence T_k using all said retrieved said model vectors m_rj to construct a set of vector pairs {(t_nk, m_rj)};

(b) for each vector pair (t_nk, m_rj) within said set of vector pairs {(t_nk, m_rj)}, computing a pair matching score that is a function of the multidimensional values of the two vectors in the pair and reflects said vector pair matching quality;

(c) obtaining a set of valid pair sequences, which is constructed only from sequences of vector pairs that have mutual sequential relation, and wherein said mutual sequential relation between any two said vector pairs . . . (t_nk, m_rj) . . . (t_ck, m_ej) . . . included in a valid pair sequence, fulfills the following four conditions;

(I) r is not equal to e, (II) if e>

r, then n≦

c, and (III) if e<

r then c≦

n (IV) all said model vectors included in one said valid pair sequence are components of one said model vectors sequence M_j;

(d) computing for each said valid pair sequence, a sequence matching score, wherein said sequence matching score is a function of all said pair matching scores that correspond to said vector pairs that are components of said valid pair sequence;

(e) for each said model vectors sequence M_j,finding a set of said valid pair sequences that includes all the said valid pair sequences which are constructed from model vectors included in said model vectors sequence M_j;

(f) for each said model vectors sequence M_j,finding a set of sequence matching scores, wherein each member of the said set of sequence matching scores corresponds to said valid pair sequence which is a member of said set of said valid pair sequences, which are constructed from pairs of said input vectors and said model vectors included in said model vectors sequence M_j;

(g) for each said set of sequence matching scores that pertains to said model vectors sequence M_j, denoting the highest said sequence matching score as said matching score S_kj of said model vectors sequence M_j;

(h) defining said collection of matching scores {S_kj} as the collection of said matching scores S_kj of all said model vectors sequences M_j which are included in said collection of model vectors sequences {M_j};

(i) providing said collection of matching scores {S_kj} as the output of said matching algorithm.

17. The method of claim 16 wherein recorded data in said record of input signals and in said records of model signals, includes data derived from at least one speech signal.

18. The method of claim 17 wherein for each said model vectors sequence M_j in said collection of model vectors sequences {M_j}, applying the principles of dynamic programming in computing said highest said sequence matching score in said set of sequence matching scores that pertains to said model vectors sequence M_j.

19. The method of claim 16 wherein each of said signal is derived from at least one source, wherein each said source emits signals selected from the group consisting of continuous signals and discrete signals.

20. The method of claim 19 wherein for each said model vectors sequence M_j in said collection of model vectors sequences {M_j}, applying the principles of dynamic programming in computing said highest said sequence matching score in said set of sequence matching scores that pertains to said model vectors sequence M_j.