Embedded multi-layer coupled hidden Markov model

• US 7,089,185 B2
• Filed: 06/27/2002
• Issued: 08/08/2006
• Est. Priority Date: 06/27/2002
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Nefian, Ara V
• Primary Examiner(s): Dorvil, Richemond
• Assistant Examiner(s): Opsasnick, Michael N.
• Application Number:
  US10/180,042
• Publication Number:
  US 20040002863A1
• Time in Patent Office: 1,503 Days
• Field of Search: 704/202, 704/255, 704/256, 704/256.1, 704/256.5, 382/156, 382/181, 382/190, 382/277, 382/302
• US Class Current: 704/256
• CPC Class Codes: G06V 10/75 Organisation of the matching processes, e.g. simultaneous or sequential comparisons of image or video features; Coarse-fine approaches, e.g. multi-scale approaches; using context analysis; Selection of dictionaries
• CPC Class Codes: G06V 40/16 Human faces, e.g. facial parts, sketches or expressions

Abstract

An arrangement is provided for embedded coupled hidden Markov model. To train an embedded coupled hidden Markov model, training data is first segmented into uniform segments at different layers of the embedded coupled hidden Markov model. At each layer, a uniform segment corresponds to a state of a coupled hidden Markov model at that layer. An optimal segmentation is generated at the lower layer based on the uniform segmentation and is then used to update parameters of models associated with the states of coupled hidden Markov models at lower layer. The updated model parameters at the lower layer are then used to update the model parameters associated with states at the super layer.

Claims

1. A computerized method for generating an embedded couple hidden Markov model for pattern recognition, comprising:

obtaining data of two or more dimensions, the data having a label representing a known pattern;

segmenting the data uniformly into one or more super segments;

assigning each super segment to a super state of a super channel in a coupled hidden Markov model at a super layer of an embedded coupled hidden Markov model, the super layer having at least one super channel;

segmenting each super segment into lower layer segments, each of which corresponds to a lower layer state of a lower channel of a lower layer coupled hidden Markov model associated with one of the super states;

optimally segmenting the data at the lower layer to produce an optimal segmentation;

updating one or more parameters of at least one model associated with at least one lower layer state based on the optimal segmentation; and

updating one or more parameters of at least one model associated with at least one super state based on the at least one model associated with the at least one lower layer state to generate an embedded coupled hidden Markov model modeling the known pattern for use in a subsequent pattern recognition task.

2. The method according to claim 1, wherein each super state embeds a coupled hidden Markov model at the lower layer.

3. The method according to claim 2, wherein the coupled hidden Markov model at the lower layer embedded by a super state comprises a plurality of lower layer channels, each of which has a plurality of lower layer states;

the coupled hidden Markov model at the super layer comprises a plurality of super channels, each of which has a plurality of super states.

4. The method according to claim 3, wherein each of the at least one model associated with a state includes at least one of:

a probability density function, characterized by at least one parameter, modeling the state in a feature space; and

a transition probability matrix modeling transitions from the state to other states within a coupled hidden Markov model.

5. The method according to claim 4, wherein the probability density function includes a Gaussian mixture density function.

6. The method according to claim 5, wherein the optimally segmenting includes using a Viterbi algorithm.

7. The method according to claim 6, further comprising:

computing observation vectors from the data prior to said optimally segmenting; and

selecting the one or more parameters of models associated with the at least one lower layer state based on the observation vectors and the optizrial segmentation prior to updating at the lower layer.

8. The method according to claim 7, wherein said optimally segmenting and updating one or more parameters at the lower layer are iterated until a pre-determined criterion is satisfied.

9. The method according to claim 8, wherein the pre-determined criterion includes a condition that difference in the updated models between two consecutive the updating one or more parameters is below a threshold.

10. A computerized method for generating an embedded coupled hidden Markov model for pattern recognition, comprising:

deriving at least one embedded coupled hidden Markov model based on one or more training samples, each of which having a label representing a known pattern, each of the at least one embedded coupled hidden Markov model modeling a corresponding known pattern, wherein the embedded coupled hidden Markov model comprises a plurality of coupled hidden Markov models, said deriving comprises;

collecting the training samples;

for each of the training samples that have a same label representing a same known pattern;

segmenting data in each of the training samples uniformly into one or more super segments;

assigning cach super segment to a super state of a super channel in a coupled hidden Markov model at a super layer of an embedded coupled hidden Markov model, the super layer having at least one super channel;

segmenting each super segment into lower layer segments, each of which corresponds to a lower layer state of a lower channel of a lower layer coupled hidden Markov model associated with one of the super states;

optimally segmenting the data at the lower layer to produce an optimal segmentation;

updating one or more parameters of at least one model associated with at least one lower layer state based on the optimal segmentation to produce updated models associated with the at least one lower layer state; and

updating one or more parameters of at least one model associated with at least one super state based on the undated models associated with the at least one lower layer state to generate an updated embedded coupled bidden Markov model modeling the same known pattern;

receiving input data of two or more dimensions, the input data being indicative of a pattern; and

recognizing the pattern in the input data with respect to the known patterns based on the at least one embedded coupled hidden Markov model.

11. The method according to claim 10, wherein the input data includes a two-dimensional image containing an imagery of a human face.

12. The method according to claim 11, wherein said recognizing the pattern in the input data includes recognizing the identity of a human face appearing in a two dimensional image.

13. An article of generating an embedded coupled bidden Markov model for pattern recognition, comprising a computer readable storage medium having stored thereon instructions that, when executed by a machine, result in the following:

obtaining data of two or more dimensions, the data having a label representing a known pattern;

segmenting the data uniformly into one or more super segments;

assigning each super segment to a super state of a super channel in a coupled hidden Markov model at a super layer of an embedded coupled hidden Markov model, the super layer having at least one super channel;

segmenting each super segment into lower layer segments, each of which corresponds to a lower layer state of a lower channel of a lower layer coupled hidden Markov model associated with one of the super states;

optimally segmenting the data at the lower layer to produce an optimal segmentation;

updating one or more parameters of at least one model associated with at least one lower layer state based on the optimal segmentation; and

updating one or more parameters of at least one model associated with at least one super state based on the at least one model associated with the at least one lower layer state to generate an embedded coupled Markov model modeling the known pattern.

14. The article comprising a computer readable storage medium having stored thereon instructions according to claim 13, wherein each of the at least one super state embeds a coupled bidden Markov model at the lower layer.

15. The article comprising a computer readable storage medium having stored thereon instructions according to claim 14, wherein

the coupled hidden Markov model at the lower layer embedded by a super state comprises a plurality of lower layer channels, each which having a plurality of lower layer states;

the coupled hidden Markov model at the super layer comprises a plurality of super channels, each of which having a plurality of super state.

16. The article comprising a computer readable storage medium having stored thereon instructions according to claim 15, wherein each of the at least one model associated with a state includes at least one of:

a probability density function, characterized by at least one parameters, modeling the state it, a feature space; and

a transition probability matrix modeling transitions from the state to other states within a coupled hidden Markov model.

17. The article comprising a computer readable storage medium having stored thereon instructions according to claim 16, wherein the performing optimal segmentation includes performing optimal segmentation using Viterbi algorithm.

18. An article for generating an embedded coupled hidden Markov model for pattern recognition, comprising a computer readable storage medium having stored thereon instructions that, when executed by a machine, result in the following:

deriving at least one embedded coupled bidden Markov model, each of which modeling a known pattern, using one or more training sample, each of which having a label representing a known pattern, each of the at least one embedded hidden Markov model modeling a corresponding known pattern, wherein the embedded coupled hidden Markov model comprises a plurality of coupled hidden Markov models, said depriving comprises;

collecting the training samples. for each of the training samples that have a same label representing a same known pattern;

segmenting data in each of the training samples uniformly into one or more super segments.

assianing each super segment to a super state of a super channel in a coupled hidden Markov model at a super layer of an embedded coupled hidden Markov modeL the super layer having at least one super channel,

segmenting each super segment into lower laver segments, each of which corresponds to a lower layer state of a lower channel of a lower layer coupled hidden Markov model associated with one of the super states,

optimally segmenting the data at the lower layer to produce an optimal segmentation,

updating one or more parameters of at least one model associated with at least one lower layer state based on the optimal segmentation to produce updated models associated with the at least one lower layer state, and

updating one or more parameters of at least one model associated wit at least one super state based on the updated models associated with the at least one lower layer state to generate an updated embedded coupled hidden Markov model modeling the same known pattern;

receiving input data of two or more dimensions, the input data containing data indicative of a pattern, and

recognizing the pattern from the input data with respect to the known patterns using the at least one embedded coupled hidden Markov model.

19. The article comprising a computer readable storage medium having stored thereon instructions according to claim 18, wherein

the input data includes a two-dimensional image containing an imagery of a human face;

and

said recognizing the pattern includes recognizing the identity of a human face appearing in a two-dimensional image.