Image analysis – Learning systems – Trainable classifiers or pattern recognizers
Reexamination Certificate
2000-11-06
2004-10-05
Ahmed, Samir (Department: 2623)
Image analysis
Learning systems
Trainable classifiers or pattern recognizers
C382S160000, C382S228000
Reexamination Certificate
active
06801656
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of signal processing systems, and more particularly to image signal processing and other types of signal processing techniques involving the use of hidden Markov models (HMMs).
BACKGROUND OF THE INVENTION
A variety of well-known signal processing techniques make use of HMMs. For example, HMMs have been used in the analysis of image sequences to recognize facial expressions. Facial expressions are complex, spatio-temporal motion patterns. The movements associated with a given facial expression are generally divided into three periods: (i) onset, (ii) apex, and (iii) offset. These periods correspond to the transition towards the facial expression, the period sustaining the peak in expressiveness, and the transition back from the expression, respectively. The rate of change in the onset period as well as the duration in the apex period are often related to the intensity of the underlying emotion associated with the facial expression.
HMMs have been specifically designed in this context to take advantage of the spatio-temporal character of facial expression patterns. Examples of facial expression recognition techniques based on HMMs are described in T. Otsuka et al., “Recognizing Abruptly Changing Facial Expressions From Time-Sequential Face Images,” International Conference on Computer Vision and Pattern Recognition (CVPR), 1998; and T. Otsuka et al., “Recognizing Multiple Persons≦ Facial Expression Using HMM Based on Automatic Extraction of Significant Frames from Image Sequences,” International Conference on Image Processing (ICIP), pp. 546-549, 1997.
The HMMs used in the above-described facial expression context as well as in other signal processing applications may be sequential HMMs. Sequential HMMs, which are also known as left-to-right HMMs, are typically used to model sequential data for pattern recognition, analysis, etc. The sequential data generally represent linear trajectories in multi-dimensional spaces. For example, the sequential data may represent the path followed by a set of facial feature points in an abstract multi-dimensional space of facial expressions, when a face is observed over time for facial expression recognition.
A significant problem which arises in the conventional use of sequential HMMs and other types of HMMs in signal processing applications is related to the determination of an appropriate number of states for the HMM. In general, it is necessary to specify the number of states in the HMM prior to using the HMM to process actual data. Unfortunately, existing techniques for determining the number of states are deficient in that such techniques are generally unable to provide a model which best matches a given set of training data.
SUMMARY OF THE INVENTION
The invention provides methods and apparatus for determining an appropriate number of states in a hidden Markov model (HMM) using an iterative algorithm which adjusts the number of states based on an inter-state closeness measure. The resulting HMM is utilized to process data in a signal processing system and an action in the system is taken based on a result of the processing operation.
In accordance with one aspect of the invention, a signal processing system processes a signal using an 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 HMM starting from an initial or default number of states, based at least in part on closeness measures computed between the states, until the HMM satisfies a specified performance criterion. For example, the iterative algorithm may iteratively increase or decrease the number of states until an average separation between the states is within a predefined range. The HMM 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.
In an illustrative embodiment, the signal to be processed using the HMM having an adjusted number of states is a sequence of images, and the HMM is used to determine an intensity of a particular facial expression likely to be present in the sequence of images.
In accordance with another aspect of the invention, the inter-state closeness measure is in the form of 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 HMM.
In accordance with a further aspect of the invention, a first iterative algorithm is used to adjust the number of states of the HMM if an expected number of states of the HMM is above a specified number, and a second iterative algorithm is used to adjust the number of states of the HMM if the expected number of states of the HMM is at or below the specified number. The specified number of states may be on the order of ten states. The first iterative algorithm may be configured to perform local closeness tests and to allow multiple states to be added and deleted from the model on each iteration. The second iterative algorithm may be configured to perform a global closeness test and to allow only one state to be added or deleted from the model on each iteration.
Advantageously, the invention allows the determination of an appropriate number of states in a HMM based on a set of training data, such that the resulting model performs with substantially greater accuracy than a model generated by assignment of a fixed number of states. The techniques of the invention can be used in a wide variety of signal processing applications, including video-camera-based systems such as video conferencing systems and video surveillance and monitoring systems, speech recognition systems, and human-machine interfaces.
REFERENCES:
patent: 4903305 (1990-02-01), Gillick et al.
patent: 5289562 (1994-02-01), Mizuta et al.
patent: 5502774 (1996-03-01), Bellegarda et al.
patent: 6078884 (2000-06-01), Downey
patent: 6118890 (2000-09-01), Senior
patent: 6157731 (2000-12-01), Hu et al.
patent: 6460017 (2002-10-01), Bub et al.
patent: 0685835 (1995-12-01), None
patent: 0750293 (1996-12-01), None
patent: 1138993 (1999-12-01), None
Tosuka, T. and Ohya, J. “Spotting segments displaying facial expression from image sequence using HMM”, Automatic Face and Gesture Recognition, 1998, pp.: 442-447.*
“A Probablistic Framework for Embedded Face and Facial Expression Recognition”, Antonio Colmenarez et al, Int'l Conference on Computer Vision and Pattern Recognition (CVPR), 1999.
“Embedded Face and Facial Expression Recognition”, Antonio Colmenarez et al, Int'l Conference on Image Processing (ICIP), 1999.
“Pattern Detection with Information-Based Maximum Discrimination and Error Bootstrapping”, Antonio J. Colmenarez et al.
“Facial Analysis From Continuous Video With Application to Human-Computer Interface”,Antonio J. Colmenarez, PHd. Dissertation, University of Illinois at Urbana-Champaign, Mar. 1999.
“Detection and Tracking of Faces and Facial Features”, Antonio Colmenarez et al, Int'l Conference on Image Processing (ICIP), 1999.
A. Colmenarez et al; “Detection and Tracking of Faces and Facial Features”, Image Processing, 1999, ICIP 99. Proceedings 1999 International Conference on Kobe, Japan Oct. 24-28, 1999, Piscataway, NJ, USA, IEEE, pp. 657-661, XP010369128.
M. Brand; “Pattern Discovery via Entropy Minimization” Mitsubishi Electric Research Laboratory Technical Reports, Online, Oct. 1, 1998, XP002194147.
Colmenarez Antonio J.
Gutta Srinivas
Ahmed Samir
Goodman Edward W.
Koninklijke Philips Electronics , N.V.
Le Brian
LandOfFree
Method and apparatus for determining a number of states for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for determining a number of states for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determining a number of states for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3290892