Image analysis – Pattern recognition – Classification
Patent
1995-05-05
1997-03-25
Boudreau, Leo
Image analysis
Pattern recognition
Classification
382229, G06K 900
Patent
active
056152868
ABSTRACT:
The number of calculations to determine the most likely path is reduced by eliminating a number of paths that are impossible to provide an optimal result. How to eliminate these non-optimal paths, thus greatly reducing the number of calculations performed by a signal processor. The determination of the probability score of the best path to state s at time t may be found as follows. First, transition probabilities to state s are sorted in order of descending probability. Second, the k highest probability scores at time t-1 are identified. Third, the highest transition probability associated with the k highest probability scores at t-1 is identified and designated maxrank. Fourth, the k highest probability scores at t-1 are multiplied with their associated transition probabilities with the highest product being designated maxvalue. Fifth, all transition probabilities higher than maxrank are multiplied with their associated probability scores at t-1. If the product of one of these multiplications is greater than the current maxvalue, this product becomes the new maxvalue. The final maxvalue is multiplied by an observation probability to determine a most likely path sequence to state s at time-1. K is chosen to be .sqroot.N, where N is the total number of possible states.
REFERENCES:
patent: 4827521 (1989-05-01), Bahl et al.
patent: 5029212 (1991-07-01), Yoshida
patent: 5050215 (1991-09-01), Nishimura
patent: 5268990 (1993-12-01), Cohen et al.
patent: 5307444 (1994-04-01), Tsuboka
Rabiner, "A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition", Proceedings of the IEEE, vol. 77, No. 2, Feb. 1989, pp. 257-286.
Forney, "The Viterbi Algorithm", Proceedings of the IEEE, vol. 61, No. 3, Mar. 1973, pp. 268-278.
S. Patel, "A Lower Complexity Viterbi Algorithm", 1995 ICASSP vol. 1, pp. 592-595, published on May 8, 1995, No Publisher.
Floyd, et al., "Expected Time Boundaries for Selection", Communications of the ACM, vol. 18, No. 3 pp. 165-173, Mar. 1975.
Austin et al., "Toward a Real-Time Spoken Language System Using Commercial Hardware", Proceedings DARPA Speech and Natural Language Workshop, pp. 72-77, Jun. 1990, No Publisher.
Bell Communications Research Inc.
Boudreau Leo
Falk James W.
Giordano Joseph
Tadayon Bijan
LandOfFree
Method for determining a most likely sequence of states 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 for determining a most likely sequence of states, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for determining a most likely sequence of states will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2210838