System for reconstruction of symbols in a sequence

• US 20040186717A1
• Filed: 03/17/2003
• Published: 09/23/2004
• Est. Priority Date: 03/17/2003
• Status: Active Grant

• Current Assignee: Rensselaer Polytechnic Institute
• Original Assignee: Rensselaer Polytechnic Institute
• Inventors: Moore, Michael, Savic, Michael
• Granted Patent: US 7,024,360 B2
• Time in Patent Office: Days
• US Class Current: 704/256
• CPC Class Codes: G10L 15/14 using statistical models, e.g. Hidden Markov Models [HMMs] G10L15/18 takes precedence
• CPC Class Codes: G10L 21/02 Speech enhancement, e.g. noise reduction or echo cancellation reducing echo effects in line transmission systems H04B3/20; echo suppression in hands-free telephones H04M9/08

Abstract

A method of reconstructing a damaged sequence of symbols where some symbols are missing is provided in which statistical parameters of the sequence are used with confidence windowing techniques to quickly and efficiently reconstruct the damaged sequence to its original form. Confidence windowing techniques are provided that are equivalent to generalized hidden semi-Markov models but which are more easily used to determine the most likely missing symbol at a given point in the damaged sequence being reconstructed. The method can be used to reconstruct communications consisting of speech, music, digital transmission symbols and others having a bounded symbol set which can be described by statistical behaviors in the symbol stream.

Claims

1. A method for reconstructing a damaged stream of symbols using statistical behaviors of the symbol stream to replace damaged or missing symbols from the symbol stream with reconstructed symbols, the method comprising:

inputting a stream of symbols into a symbol reconstruction system;

pre-processing the input stream of symbols by extracting language parameters from the stream of symbols;

generating a hidden semi-Markov model from the extracted language parameters;

generating a generalized hidden semi-Markov model using the hidden semi-Markov model, the generalized hidden semi-Markov model capable of functioning on two different time scales

applying the generalized hidden semi-Markov model to the symbol stream to generate replacement characters for the damaged or missing symbols;

post-processing the symbol stream by substituting replacement characters for the damaged or missing symbols to reconstruct the symbol stream; and

outputting the reconstructed symbol stream from the symbol reconstruction system.

2. The method of claim 1, wherein applying the generalized hidden semi-Markov model comprises applying a confidence window to the symbol stream to generate the replacement characters.

3. The method of claim 2, wherein pre-processing the input stream of symbols comprises selecting a confidence window and screening the input stream of symbols with the confidence window to extract language parameters.

4. The method of claim 3, wherein the extracted language parameters comprise observation probabilities, transition probabilities and duration of symbols.

5. The method of claim 1, wherein generating the generalized hidden semi-Markov model comprises grouping known symbols in the stream of symbols into a first set of states of the hidden semi-Markov model and grouping damaged or missing symbols in the stream of symbols into a second set of states of the hidden semi-Markov model.

6. The method of claim 5, wherein generating the generalized hidden semi-Markov model further comprises adding a transition probability non-commutative multiplication operator and an observation probability non-commutative multiplication operator to the hidden semi-Markov model.

7. The method of claim 6, wherein generating the generalized hidden semi-Markov model further comprises modifying a Viterbi Algorithm of the hidden semi-Markov model to choose symbols for reconstruction based on a maximization operation.

8. The method of claim 1, further comprising applying the generalized hidden semi-Markov model to the symbol stream to generate replacement characters.

9. A method for reconstructing a damaged stream of symbols using statistical behaviors of a language of the symbol stream to replace damaged or missing symbols in the symbol stream with reconstructed symbols, the method comprising:

inputting the stream with known and unknown symbols of the language into a symbol reconstruction system;

extracting language parameters from the known symbols;

generating a hidden semi-Markov model for the language from the extracted language parameters;

generating a generalized hidden semi-Markov model using the hidden semi-Markov model, the generalized hidden semi-Markov model capable of functioning on two different time scales;

generating replacement characters for the damaged or missing symbols by applying the generalized hidden semi-Markov model to the second stream of symbols;

post-processing the stream of symbols by substituting replacement characters for the unknown symbols to reconstruct the stream of symbols; and

outputting the reconstructed stream of symbols from the symbol reconstruction system.

10. The method of claim 9, wherein applying the generalized hidden semi-Markov model comprises applying a confidence window to the stream of symbols to generate the replacement characters.

11. The method of claim 9, wherein the extracted language parameters comprise observation probabilities, transition probabilities and duration of symbols for the language.

12. The method of claim 9, wherein generating the replacement characters comprises grouping known symbols in the stream of symbols into a first set of states of the hidden semi-Markov model and grouping unknown symbols in the stream of symbols into a second set of states of the hidden semi-Markov model.

13. The method of claim 12, wherein generating the replacement characters further comprises adding a transition probability non-commutative multiplication operator and an observation probability non-commutative multiplication operator to the hidden semi-Markov model.

15. A method for reconstructing a damaged stream of symbols using statistical behaviors of a language of the symbol stream and statistical relationships of known symbols to damaged or missing symbols to replace the damaged or missing symbols in the symbol stream with reconstructed symbols, the method comprising:

identifying unknown symbols;

assessing first transition probabilities between first symbols of the symbol stream, the first symbols sized dependent on a first regeneration time parameter;

assessing second transition probabilities between second symbols in the symbol stream, the second symbols sized dependent on a second regeneration time parameter;

generating a generalized hidden semi-Markov model from the symbol stream and first and second transition probabilities;

generating a second, generalized output symbol stream during a first Viterbi algorithm application;

using said second output symbol stream in a Markov Random Field on a GHSMM trellis; and

interleaving a probability of the Random Markov Field in a second Viterbi algorithm application.

14. The method of claim 15, wherein generating the replacement characters further comprises modifying a Viterbi Algorithm of the hidden semi-Markov model to choose symbols for reconstruction based on a maximization operation.