Method for time-scale modification of signals

• US 5,175,769 A
• Filed: 07/23/1991
• Issued: 12/29/1992
• Est. Priority Date: 07/23/1991
• Status: Expired due to Term

• Current Assignee: Virentem Ventures LLC
• Original Assignee: ROLM Systems (Siemens AG)
• Inventors: Hejna, Jr., Donald J., Musicus, Bruce R., Crowe, Andrew S.
• Primary Examiner(s): KEMENY, EMANUEL
• Application Number:
  US07/734,424
• Time in Patent Office: 525 Days
• Field of Search: 381/34, 381/35, 360/8
• US Class Current: 704/211
• CPC Class Codes: G10L 21/04 Time compression or expansion

Abstract

Method for time-scale modification ("TSM") of a signal, for example, a voice signal, wherein starting positions of blocks in an input signal, referred to as analysis windows, are varied and an output signal is reconstructed by overlapping analysis windows using fixed window offsets, i.e., the duration of overlap between analysis windows is fixed during reconstruction. This is done by searching for segments of the input signal which are similar to the previous portion of the output signal. In one embodiment of the present invention a cross-correlation is used as a similarity measure to evaluate such similarity and the cross-correlation uses a fixed, predetermined minimum number of samples. The starting position of the analysis window which results in the greatest similarity in overlapping regions is determined as the starting position which provides the largest value of cross-correlation in the overlapping regions. Several cross-correlations are evaluated by shifting the analysis window over a predetermined number of samples, removing the first shifted samples in the evaluation each time, and using the same, predetermined number of samples in the evaluation to determine the "best" starting position for an analysis window. Finally, the predetermined number of samples from the beginning of the analysis window are averaged with the predetermined number of samples from the end of the previous portion of the output signal and the remaining samples in the window are appended to the averaged segment of the previous portion of the output signal.

Claims

1. A method for time-scale modification of a signal comprised of an input stream of signal representations to form an output stream of signal representations, the method comprising the steps of:

determining an input block of W signal representations from the input stream for use in overlapping signal representations from the input block with signal representations in the output stream; and

overlapping W_OV signal representations from the beginning of the input block with W_OV signal representations from the end of the output stream, where W_OV is determined by W and the time-scale modification.

2. The method of claim 1 wherein the step of overlapping comprises the step of:

applying a weighting function to W_OV signal representations from the beginning of the input block and to W_OV signal representations from the end of the output stream to determine values of W_OV signal representations to be substituted for the W_OV signal representations at the end of the output stream; and

wherein the step of overlapping further comprises the step of;

placing W-W_OV =S_s signal representations from the input stream at the end of the output stream, the S_s signal representations being subsequent to the W_OV signal representations from the beginning of the input block.

3. The method of claim 2 wherein:

the step of determining an input block comprises the steps of;

determining an initial input block of W+K_max signal representations from the input stream, where K_max is a predetermined amount;

determining a maximum of a similarity measure between W_OV signal representations from the initial input block and W_OV signal representations from the end of the output stream over a fixed search range of K_max signal representations, the search starting at the beginning of the initial input block; and

determining the input block to comprise W signal representations which begin at the sample in the initial input block whose W_OV signal representations provided a maximum of the similarity measure.

4. The method of claim 3 wherein the step of determining an initial input block comprises the step of:

determining the first signal representation of the m^th initial input block as being the signal representation which occurs mS_a signal representations after the first sample in the input stream, where S_a is a predetermined amount;

and wherein the step of determining a maximum of the similarity measure comprises the steps of;

determining a similarity measure for the W_OV signal representations starting at the beginning of the initial input block and the W_OV signal representations at the end of the output stream;

shifting the beginning of the initial input block and repeating the previous step over the fixed search range; and

determining the maximum similarity measure.

5. The method of claim 4 wherein the similarity measure is a cross-correlation.

6. The method of claim 5 wherein the weighting function is a average.

7. The method of claim 3 wherein the step of determining a maximum of a similarity measure comprises the steps of:

determining a single-bit, square-wave, correlation function.

8. The method of claim 7 wherein the step of determining a single-bit, square-wave, correlation function comprises the step of determining a logical exclusive OR of sign-bits of the signal signal representations.

9. The method of claim 5 wherein the weighting function provides a linear fade.

20. The method of claim 1 wherein the method comprises the further step of overlapping signal representations which are more than W_OV signal representations from the beginning of the input block.

10. A method for time-scale modification of a signal comprised of an input stream of signal representations to form an output stream of signal representations, the method comprising the steps of:

determining a number of signal representations for use in overlapping signal representations from the input stream to the output stream, W_OV ;

determining an input block of W signal representations from the input stream for use in overlapping signal representations from the input block with signal representations in the output stream; and

overlapping W_OV signal representations from the beginning of the input block with W_OV signal representations from the end of the output stream.

11. The method of claim 10 wherein the step of overlapping comprises the step of:

applying a weighting function to W_OV signal representations from the beginning of the input block and to W_OV signal representations from the end of the output stream to determine values of W_OV signal representations to be substituted for the W_OV signal representations at the end of the output stream; and

wherein the step of overlapping further comprises the step of;

placing W-W_OV =S_s signal representations from the input stream at the end of the output stream, the S_s signal representations being subsequent to the W_OV signal representations from the beginning of the input block.

12. The method of claim 11 wherein:

the step of determining an input block comprises the steps of;

determining an initial input block of W+K_max signal representations from the input stream, where K_max is a predetermined amount;

determining a maximum of a similarity measure between W_OV signal representations from the initial input block and W_OV signal representations from the end of the output stream over a fixed search range of K_max signal representations, the search starting at the beginning of the initial input block; and

determining the input block to comprise W signal representations which begin at the sample in the initial input block whose W_OV signal representations provided a maximum of the similarity measure.

13. The method of claim 12 wherein the step of determining an initial input block comprises the step of:

determining the first sample of the m^th initial input block as being the sample which occurs mS_a signal representations after the first sample in the input stream, where S_a is a predetermined amount;

and wherein the step of determining a maximum of the similarity measure comprises the steps of;

determining a similarity measure for the W_OV signal representations starting at the beginning of the initial input block and the W_OV signal representations at the end of the output stream;

shifting the beginning of the initial input block and repeating the previous step over the fixed search range; and

determining the maximum similarity measure.

14. The method of claim 13 wherein the similarity measure is a cross-correlation.

15. The method of claim 14 wherein the weighting function is a average.

16. The method of claim 12 wherein the step of determining a maximum of a similarity measure comprises the steps of:

determining a single-bit, square-wave, correlation function.

17. The method of claim 16 wherein the step of determining a single-bit, square-wave, correlation function comprises the step of determining a logical exclusive OR of sign-bits of the signal type representations.

18. The method of claim 14 wherein the weighting function provides a linear fade.

19. A method which comprises the steps of:

time-scale modifying a signal comprised of an input stream of signal representations to form an output stream of signal representations wherein at least one of the steps of time-scale modifying comprises;

determining an input block of signal representations from the input stream for use in appending signal representations from the input block to signal representations in the output stream, where the number appended is determined by the time-scale modification; and

appending the signal representations to the end of the output stream.