Method and apparatus for determining a number of states for a hidden Markov model in a signal processing system

• US 6,801,656 B1
• Filed: 11/06/2000
• Issued: 10/05/2004
• Est. Priority Date: 11/06/2000
• Status: Expired due to Fees

• Current Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Colmenarez, Antonio J., Gutta, Srinivas
• Primary Examiner(s): Ahmed, Samir
• Assistant Examiner(s): LE, BRIAN Q
• Application Number:
  US09/706,668
• Time in Patent Office: 1,429 Days
• Field of Search: 704/256, 382/228, 382/118, 382/159, 382/160, 382/186, 382/187-189
• US Class Current: 382/159
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models
• CPC Class Codes: G06V 40/176 Dynamic expression
• CPC Class Codes: G06V 40/20 Movements or behaviour, e.g. gesture recognition recognition of facial expressions G06V40/16

Abstract

A signal processing system processes a signal using a hidden Markov model (HMM) having a number of states determined at least in part based on application of an iterative algorithm to the model. The iterative algorithm adjusts the number of states of the model, based at least in part on closeness measures computed between the states, until the model satisfies a specified performance criterion. The model having the adjusted number of states is then utilized to determine a characteristic of the signal, and an action of the signal processing system is controlled based on the determined characteristic.

Claims

1. A method for use in processing a signal in a signal processing system, the method comprising the steps of:

processing the signal using a hidden Markov model having a number of states determined at least in part based on application of an iterative algorithm to the model, the iterative algorithm adjusting the number of states of the model, based at least in part on closeness measures computed between the states, until the model satisfies a specified performance criterion, wherein the model having the determined number of states is utilized to determine a characteristic of the signal; and

controlling an action of the signal processing system based on the determined characteristic of the signal,

wherein the closeness measure for a given pair of states of the model is computed as;

$H<br><br>\left(P_1,P_2\right)={\int <br><br>}_{-\mathrm{\infty <br><br>}}^{+\mathrm{\infty <br><br>}}<br><br>P_1<br><br>\left(v_0+\mathrm{\alpha <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{v<br><br>\text{\hspace{1em}<br><br>}}_1\right)<br><br>\log <br><br>\frac{P_1<br><br>\left(v_0+\mathrm{\alpha <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>v_1\right)}{P_2<br><br>\left(v_0+\mathrm{\alpha <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>v_1\right)}<br><br><br><br>\mathrm{\alpha <br><br>}$

where H(P₁, P₂) denotes the closeness measure, α

is an integration variable, P₁(x) and P₂(x) are probability functions of the two states, x₀¹ and x₀² are the most likely points in each state, $x_0=\arg <br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{x}{\max }<br><br>P<br><br>\left(x\right),$

v₀=x₀¹ and v₁=x₀²−

x₀¹.

2. The method as claimed in claim 1, wherein the signal comprises a sequence of images, and the determined characteristic comprises an intensity of a particular facial expression present in the sequence of images.

3. The method as claimed in claim 1, wherein the iterative algorithm is applied to an initial number of states of the model.

4. The method as claimed in claim 3, wherein the initial number of states comprises a default number of states for the model.

5. The method as claimed in claim 1, wherein the iterative algorithm iteratively increases or decreases the number of states until an average separation between the states is within a predefined range.

6. The method as claimed in claim 1, wherein the closeness measure comprises a mutual entropy computed along a line that passes through a pair of points, each of the points representing a most likely point in a feature space associated with a corresponding state of the model.

7. The method as claimed in claim 1, wherein the iterative algorithm comprises a selected one of a plurality of algorithms, the selection of a particular one of the algorithms being based at least in part on an expected number of states of the model.

8. The method as claimed in claim 1, wherein a first iterative algorithm is used to adjust the number of states of the model if an expected number of states of the model is above a specified number, and a second iterative algorithm is used to adjust the number of states of the model if the expected number of states of the model is at or below the specified number.

9. The method as claimed in claim 8, wherein the specified number of states comprises approximately ten states.

10. The method as claimed in claim 8, wherein the first iterative algorithm performs local closeness tests and allows multiple states to be added and deleted from the model on each iteration.

11. The method as claimed in claim 8, wherein the second iterative algorithm performs a global closeness test and allows only one state to be added or deleted from the model on each iteration.

12. The method as claimed in claim 1, wherein the controlling step comprises generating an output of the signal processing system based on the determined characteristic of the signal.

13. The method as claimed in claim 1, wherein the controlling step comprises altering an operating parameter of the signal processing system based on the determined characteristic of the signal.

14. An apparatus for use in processing a signal in a signal processing system, the apparatus comprising:

a processor-baaed device operative;

(i) to process the signal using a hidden Markov model having a number of states determined at least in part based on application of an iterative algorithm to the model, the iterative algorithm adjusting the number of states of the model, based at least in part on closeness measures computed between the states, until the model satisfies a specified performance criterion, wherein the model having the determined number of states is utilized to determine a characteristic of the signal; and

(ii) to control an action of the signal processing system based on the determined characteristic of the signal,

wherein the closeness measure for a given pair of states of the model is computed as;

$H<br><br>\left(P_1,P_2\right)={\int <br><br>}_{-\mathrm{\infty <br><br>}}^{+\mathrm{\infty <br><br>}}<br><br>P_1<br><br>\left(v_0+\mathrm{\alpha <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{v<br><br>\text{\hspace{1em}<br><br>}}_1\right)<br><br>\log <br><br>\frac{P_1<br><br>\left(v_0+\mathrm{\alpha <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>v_1\right)}{P_2<br><br>\left(v_0+\mathrm{\alpha <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>v_1\right)}<br><br><br><br>\mathrm{\alpha <br><br>}$

where H(P₁, P₂) denotes the closeness measure, α

0 is an integration variable, P₁(x) and P₂(x) are probability functions of the two stated, x₀¹ and x₀² are the most likely points in each state, $x_0=\arg <br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{x}{\max }<br><br>P<br><br>\left(x\right),$

v₀=x₀¹ and v₁=x₀<sup>2−

x</sup>₀¹.

15. An article of manufacture comprising a storage medium for storing one or more programs for use in processing a signal in a signal processing system, wherein the one or more programs when executed by a processor implement the step of:

processing the signal using a hidden Markov model having a number of states determined at least in part based on application of an iterative algorithm to the model, the iterative algorithm adjusting the number of states of the model, based at least in part on closeness measures computed between the states, until the model satisfies a specified performance criterion,

wherein the model having the determined number of states is utilized to determine a characteristic of the signal,

wherein an action of the signal processing system is controlled based on the determined characteristic, and

wherein the closeness measure for a given pair of states of the model is computed as;

$H<br><br>\left(P_1,P_2\right)={\int <br><br>}_{-\mathrm{\infty <br><br>}}^{+\mathrm{\infty <br><br>}}<br><br>P_1<br><br>\left(v_0+\mathrm{\alpha <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{v<br><br>\text{\hspace{1em}<br><br>}}_1\right)<br><br>\log <br><br>\frac{P_1<br><br>\left(v_0+\mathrm{\alpha <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>v_1\right)}{P_2<br><br>\left(v_0+\mathrm{\alpha <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>v_1\right)}<br><br><br><br>\mathrm{\alpha <br><br>}$

where H(P₁,P₂) denotes the closeness measure, α

is an integration variable, P₁(x) and P₂(x) are probability functions of the two states, x₀¹ and x₀² are the most likely points in each state, $x_0=\arg <br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{x}{\max }<br><br>P<br><br>\left(x\right),$

v₀=x₀¹ and v₁=x₀²−

x₀¹.

16. A method for use in processing a signal in a signal processing system, the method comprising the steps of:

processing the signal using a hidden Markov model having a number of states determined at least in part based on application of an iterative algorithm to the model, the iterative algorithm adjusting the number of states of the model, based at least in part on closeness measures computed between the states, until the model satisfies a specified performance criterion, wherein the model having the determined number of states is utilized to determine a characteristic of the signal; and

controlling an action of the signal processing system based on the determined characteristic of the signal,

wherein the closeness measure for a given pair of states of the model is computed as;

$H<br><br>\left(P_1,P_2\right)={\int <br><br>}_{-\mathrm{\infty <br><br>}}^{+\mathrm{\infty <br><br>}}<br><br>\left[P_1<br><br>\left(v_0+\mathrm{\alpha <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>v_1\right)-P_2<br><br>\left(v_0+\mathrm{\alpha <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>v_1\right)\right]<br><br>\log <br><br>\frac{P_1<br><br>\left(v_0+\mathrm{\alpha <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>v_1\right)}{P_2<br><br>\left(v_0+\mathrm{\alpha <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>v_1\right)}<br><br>\text{\hspace{1em}<br><br>}<br><br><br><br>\mathrm{\alpha <br><br>}$

where H(P₁, P₂) denotes the closeness measure, a is an integration variable, P₁(x) and P₂(x) are probability functions of the two states, x₀¹ and x₀² are the most likely points in each state, $x_0=\arg <br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{x}{\max }<br><br>P<br><br>\left(x\right),$

v₀=x₀¹ and v₁=x₀²−

x₀¹.

17. The method as claimed in claim 16, wherein the signal comprises a sequence of images and the determined characteristic comprises an intensity of a particular facial expression present in the sequence of images.

18. The method as claimed in claim 16, wherein the iterative algorithm is applied to an initial number of states of the model.

19. The method as claimed in claim 18, wherein the initial number of states comprises a default number of states for the model.

20. The method as claimed in claim 16, wherein the iterative algorithm iteratively increases or decreases the number of states until an average separation between the states is within a predefined range.

21. The method as claimed in claim 16, wherein the closeness measure comprises a mutual entropy computed along a line that passes through a pair of points, each of the points representing a most likely point in a feature space associated with a corresponding state of the model.

22. The method as claimed in claim 16, wherein the iterative algorithm comprises a selected one of a plurality of algorithms, the selection of a particular one of the algorithms being based at least in part on an expected number of states of the model.

23. The method as claimed in claim 16, wherein a first iterative algorithm is used to adjust the number of states of the model if an expected number of states of the model is above a specified number, and a second iterative algorithm is used to adjust the number of states of the model if the expected number of states of the model is at or below the specified number.

24. The method as claimed in claim 23, wherein the specified number of states comprises approximately ten states.

25. The method as claimed in claim 23, wherein the first iterative algorithm performs local closeness tests and allows multiple states to be added and deleted from the model on each iteration.

26. The method as claimed in claim 23, wherein the second iterative algorithm performs a global closeness test and allows only one state to be added or deleted from the model on each iteration.

27. The method as claimed in claim 16, wherein the controlling step comprises generating an output of the signal processing system based on the determined characteristic of the signal.

28. The method as claimed in claim 16, wherein the controlling step comprises altering an operating parameter of the signal processing system based on the determined characteristic of the signal.

29. An apparatus for use in processing a signal in a signal processing system, the apparatus comprising:

a processor-based device operative;

(i) to process the signal using a hidden Markov model having a number of states determined at least in part based on application of an iterative algorithm to the model, the iterative algorithm adjusting the number of states of the model, based at least in part on closeness measures computed between the states, until the model satisfies a specified performance criterion, wherein the model having the determined number of states is utilized to determine a characteristic of the signal; and

(ii) to control an action of the signal processing system based on the determined characteristic of the signal,

wherein the closeness measure for a given pair of states of the model is computed as;

$H<br><br>\left(P_1,P_2\right)={\int <br><br>}_{-\mathrm{\infty <br><br>}}^{+\mathrm{\infty <br><br>}}<br><br>\left[P_1<br><br>\left(v_0+\mathrm{\alpha <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>v_1\right)-P_2<br><br>\left(v_0+\mathrm{\alpha <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>v_1\right)\right]<br><br>\log <br><br>\frac{P_1<br><br>\left(v_0+\mathrm{\alpha <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>v_1\right)}{P_2<br><br>\left(v_0+\mathrm{\alpha <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>v_1\right)}<br><br>\text{\hspace{1em}<br><br>}<br><br><br><br>\mathrm{\alpha <br><br>}$

where H(P₁, P₂) denotes the closeness measure, α

is an integration variable, P₁(x) and P₂(x) are probability functions of the two states, x₀¹ and x₀² are the most likely points in each state, $x_0=\arg <br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{x}{\max }<br><br>P<br><br>\left(x\right),$

v₀=x₀¹ and v₁=x₀²−

x₀¹.

30. An article of manufacture comprising a storage medium for storing one or more programs for use in processing a signal in a signal processing system, wherein the one or more programs when executed by a processor implement the step of:

processing the signal using a hidden Markov model having a number of states determined at least in part based on application of an iterative algorithm to the model, the iterative algorithm adjusting the number of states of the model, based at least in part on closeness measures computed between the states, until the model satisfies a specified performance criterion,

wherein the model having the determined number of states is utilized to determine a characteristic of the signal,

wherein an action of the signal processing system is controlled based on the determined characteristic, and

wherein the closeness measure for a given pair of states of the model is computed as;

$H<br><br>\left(P_1,P_2\right)={\int <br><br>}_{-\mathrm{\infty <br><br>}}^{+\mathrm{\infty <br><br>}}<br><br>\left[P_1<br><br>\left(v_0+\mathrm{\alpha <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>v_1\right)-P_2<br><br>\left(v_0+\mathrm{\alpha <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>v_1\right)\right]<br><br>\log <br><br>\frac{P_1<br><br>\left(v_0+\mathrm{\alpha <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>v_1\right)}{P_2<br><br>\left(v_0+\mathrm{\alpha <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>v_1\right)}<br><br>\text{\hspace{1em}<br><br>}<br><br><br><br>\mathrm{\alpha <br><br>}$

where H(P₁, P₂) denotes the closeness measure, α

is an integration variable, P₁(x) and P₂(x) are probability functions of the two states, x₀¹ and x₀² are the most likely points in each state, $x_0=\arg <br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{x}{\max }<br><br>P<br><br>\left(x\right),$

v₀=x₀¹ and v₁=x₀²−

x₀¹.