Abstract:
A multiple step adaptive method for time scaling. Synthesizing S 3 [n] signal from signal S 1 [n]signal and S 2 [n]signal. Comprising following steps: (a) calculating a first magnitude of a cross-correlation function of S 1 [n]signal and S 2 [n]signal according to a first index; (b) comparing the first magnitude with a threshold value; (c) if first magnitude is smaller than threshold value, calculating a first reference magnitude of cross-correlation function of S 1 [n]signal and S 2 [n]signal according to a first reference index behind the first index by a first determined number, or calculating a second reference magnitude of the cross-correlation function of the S 1 [n] signal and the S 2 [n] signal according to a second reference index behind the first index by a second number; (d) synthesizing the S 3 [n] signal by adding S 1 [n]signal to the S 2 [n] signal in accordance with a maximum index corresponding to a largest magnitude among all the magnitudes calculated in (c).

Description:
BACKGROUND OF INVENTION 
   1. Field of the Invention 
   The present invention relates to a signal-synthesizing method, and more particularly, to a multiple step adaptive method for time-scaling. 
   2. Description of the Prior Art 
   Due to the dramatic progress in electronic technologies, an AV player such as a Karaoke can provide more and more amazing functions, such as audio clean-up, dynamic repositioning of enhanced audio and music (DREAM), and time scaling. Time scaling (also called time stretching, time compression/expansion, or time correction) is a function to elongate or shorten an audio signal while keeping the pitch of the audio signal approximately unchanged. In short, time scaling only adjusts the tempo of an audio signal. 
   In general, an AV player performs time scaling with one of three following methods: Phase Vocoder, Minimum Perceived Loss Time Expansion/Compression (MPEX), and Time Domain Harmonic Scaling (TDHS). Phase Vocoder transforms an audio signal into a complex Fourier representation signal with Short Time Fourier Transform (STFT) and further transforms the complex Fourier representation signal back to a time scaled audio signal corresponding to the original audio signal with interpolation techniques and iSTFT (inverse STFT). MPEX is a method researched and developed by Prosoniq for simulating characteristics of human hearing, similar to artificial neural network. MPEX records audio signals received for a predetermined period and tries to “learn” the audio signals, so as to either elongate or shorten the audio signals. TDHS is one of the most popular methods for time scaling. TDHS first establishes an autocorrelogram of a first audio signal, the autocorrelogram consisting of a plurality of magnitudes, and then delays the first audio signal by a maximum index corresponding to a maximum magnitude, a largest magnitude among all of the magnitudes of the autocorrelogram, to form a second audio signal, and lastly synchronizes and overlap-adds (SOLA) the first audio signal to the second audio signal to form a third audio signal longer than the first audio signal. 
   Please refer to  FIG. 1 , which is an autocorrelogram  10  for TDHS according to the prior art, the autocorrelogram  10  consisting of a plurality of magnitudes. In general, besides a maximum magnitude  12  and magnitudes there away, remaining magnitudes in the autocorrelogram  10  has a small value. In addition, two neighboring magnitudes of the autocorrelogram  10  differ slightly. For example, if a first magnitude  14  is far smaller than the maximum magnitude  12 , a second magnitude  16  neighboring the first magnitude  14  is also far smaller than the maximum magnitude  12 . On the contrary, if a third magnitude  18  differs slightly from the maximum magnitude  12 , a fourth magnitude  20  neighboring the third magnitude  18  is probably very close to the maximum magnitude  12  and accordingly a fourth index
 
τ 4 
 
(corresponding to the third  18  or fourth magnitude  20  as shown in  FIG. 1 ) is also probably very close to a maximum index
 
τ max 
 
corresponding to the maximum magnitude  12 .
 
   In a computer system, the autocorrelogram  10  is usually established by a digital signal processing (DSP) chip designed to manage complex mathematic calculation such as convolution and fast Fourier transform (FFT). However, a process to determine the maximum magnitude  12  and the corresponding maximum index
 
τ max 
 
by establishing the autocorrelogram  10  with a DSP chip is tedious and sometimes unnecessary.
 
   SUMMARY OF INVENTION 
   It is therefore a primary objective of the claimed invention to provide a multiple level adaptive method for time scaling capable of determining a maximum index corresponding to S 1 [n] and S 2 [n] signals efficiently and synthesizing an S 3 [n] signalfrom the S 1 [n] and S 2 [n] signals. 
   According to the claimed invention, the method comprises following steps: (a) calculating a first magnitude of a cross-correlation function of the S 1 [n] signal and the S 2 [n] signal according to a first index; (b) comparing the first magnitude with a threshold value; (c) if the first magnitude is smaller than the threshold value, calculating a first reference magnitude of the cross-correlation function of the S 1 [n] signal and the S 2 [n] signal according to a first reference index behind the first index by a first determined number, or calculating a second reference magnitude of the cross-correlation function of the S 1 [n] signal and the S 2 [n] signal according to a second reference index behind the first index by a second number; and (d) synthesizing the S 3 [n] signal by adding the S 1 [n] signal to the S 2 [n] signal in accordance with a maximum index corresponding to the largest magnitude among all of the magnitudes calculated in step (c). 
   In the preferred embodiment of the present invention, the first predetermined number is larger than one, while the second predetermined number is equal to one. 
   It is an advantage of the claimed invention that a DSP chip does not have to calculate all of the magnitudes in an autocorrelogram, thus saving time to establish the autocorrelogram and promoting the efficiency of a computer where the DSP chip is installed in. 
   These and other objectives of the claimed invention will no doubt become obvious to those of ordinary skill in the art after reading the following detailed description of the preferred embodiment that is illustrated in the various figures and drawings. 

   
     BRIEF DESCRIPTION OF DRAWINGS 
       FIG. 1  is an autocorrelogram for TDHS according to the prior art. 
       FIG. 2  is an autocorrelogram corresponding to a method according to the present invention. 
       FIG. 3  is a flow chart demonstrating a method according to the present invention. 
       FIG. 4  is a schematic diagram demonstrating how the method synthesizes an S 3 [n] signal from an S 1 [n] signal and an S 2 [n] signal according to the present invention. 
       FIG. 5  is a schematic diagram demonstrating how the method elongates an audio signal according to the present invention. 
       FIG. 6  is a schematic diagram demonstrating how the method shortens an audio signal according to the present invention. 
   

   DETAILED DESCRIPTION 
   In a process of establishing an autocorrelogram of a first audio signal and a second audio signal, a method  100  of the preferred embodiment of the present invention compares a magnitude corresponding to an index in the autocorrelogram with either a first threshold th 1  or a second threshold th 2 , the first threshold th 1  smaller than the second threshold th 2 , and calculates magnitudes corresponding to indexes following the index in the autocorrelogram. In detail, if a first magnitude
 
R(τ 1 )
 
in the autocorrelogram is smaller than the first threshold th 1 , indicating a first index corresponding to the first magnitude
 
R(τ 1 )
 
is still far from a maximum magnitude
 
R(τ max )
 
corresponding to a maximum index
 
τ max 
 
, the method  100  calculates a second magnitude
 
R(τ 2 )
 
corresponding to a second index
 
τ 2 
 
lagging the first index
 
τ 1 
 
by a first predetermined number Δ 1 ; If a third magnitude
 
R(τ 3 )
 
in the autocorrelogram is larger than the first threshold th 1  but still smaller than the second threshold th 2 , indicating a third index
 
τ 3 
 
corresponding to the third magnitude
 
R(τ 3 )
 
is closer to the maximum index
 
τ max 
 
than the first index
 
τ 1 
 
, the method  100  calculates a fourth magnitude
 
R(τ 4 )
 
corresponding to a fourth index
 
τ 4 
 
lagging the third index
 
τ 3 
 
by a second predetermined numberΔ 2 , the second predetermined numberΔ 2  smaller than the first predetermined numberΔ 1 ; If a fifth magnitude
 
R(τ 5 )
 
in the autocorrelogram is larger than the second threshold th 2 , indicating a fifth index
 
τ 5 
 
corresponding to the fifth magnitude
 
R(τ 5 )
 
is quite close to the maximum index
 
τ max 
 
, the method  100  calculates a sixth magnitude
 
R(τ 6 )
 
corresponding to a sixth index
 
τ 6 
 
right after the fifth index
 
τ 5 
 
   Please refer to  FIG. 2  and  FIG. 3 .  FIG. 2  is an autocorrelogram  30  corresponding to the method  100  according to the present invention.  FIG. 3  is a flow chart demonstrating the method  100  according to the present invention. The method  100  comprises following steps: 
   Step  102 : Start; (An S 3 [n] signal is to be synthesized from an S 1 [n] signal and an S 2 [n] signal. For simplicity, the S 1 [n] signal and S 2 [n] signals are both defined to contain N signals. Of course, the numbers of signals the S 1 [n] signal and S 2 [n] signal contain can be different.) 
   Step  103 : Delaying the S 2 [n] signal by a predetermined number Δ and forming an S 5 [n] signal; (In order to prevent run-in from occurring in a process a pickup of an A/V player reads the S 3 [n] signal, the method  100  delays the S 2 [n] signal by the predetermined number Δ and then determines the maximum index
 
τ max 
 
crucial for the process to synthesize the S 3 [n] signal from the S 1 [n] signal and the S 2 [n] signal. In the preferred embodiment, the predetermined number Δ is equal to [N/3].)
 
   Step  104 : Calculating an initial magnitude R(1) corresponding to an initial index
 
τ 1 (τ=1)
 
corresponding to the S 1 [n] signal and the S 5 [n] signal, setting a determinant magnitude R c  to be the initial magnitude R(1), and setting a determinant index
 
τ c 
 
corresponding to the determinant magnitude R c  to be the initial index
 
τ 1 
 
; (The initial magnitude R(1) is equal to
 
             ∑     n   =   0       N   -   1       ⁢           ⁢         S   1     ⁡     [   n   ]       *       S   2     ⁡     [     n   +   1     ]               
.)
 
   Step  106 : If
 
(τ c   =N− 1)
 
, then go to step  200 , else go to step  108 ; (
 
τ c 
 
equal to N−1, indicates the determinant magnitude R c , is the last magnitude in the autocorrelogram  30 . The autocorrelogram  30  is completely established.)
 
   Step  108 : Comparing the determinant magnitude R c  with either the first threshold th 1  or second threshold th 2 . If the determinant magnitude R c  is smaller than the first threshold th 1  (as the R(1) shown in  FIG. 2 ), then go to step  110 ; If the determinant magnitude R c  falls on a region between the first threshold th 1  and the second threshold th 2 , then go to step  140 ; If the determinant magnitude R c  is larger than the second threshold th 2 , then go to step  170 ; (If the determinant magnitude R c  is larger than the second threshold th 2 , indicating the determinant index
 
τ c 
 
corresponding to the determinant magnitude R c  is located on a region nearby the maximum index
 
τ max 
 
, then the method  100  calculates magnitudes corresponding to indexes right after the determinant index
 
τ c 
 
(as a magnitude R(
 
R(τ j )
 
corresponding to an index
 
τ j 
 
shown in  FIG. 2 ), or the method  100  neglects the calculation of magnitudes corresponding to indexes following the determinant index
 
τ c 
 
and calculates magnitudes corresponding to indexes lagging the determinant index
 
τ c 
 
by the first predetermined numberΔ 1  or second predetermined numberΔ 2  directly to save the time for a DSP chip to calculate magnitudes in the autocorrelogram  30 . Please note that, in order to find out the maximum index
 
τ max 
 
corresponding to the maximum magnitude R max  exactly, the first threshold th 1  and second threshold th 2  can not be defined to have too large values in the beginning to calculate the maximum index
 
τ max 
 
according to the method  100 . For example, if the second threshold th 2  is set to be a third threshold th 3  initially, after calculating the
 
R(τ j )
 
, the method  100 , according to the decision performed in the step  108 , calculates a magnitude
 
R(τ j +Δ 2 )
 
instead of calculating a magnitude
 
R(τ j +1)
 
and in the end does not calculate the exact magnitude
 
R(τ max )
 
, but obtains a magnitude
 
R(τ′ max )
 
instead, a wrong index
 
τ′ max 
 
corresponding to the magnitude
 
R(τ′ max )
 
is therefore used to synthesize the S 3 [n] signal from the S 1[n] and S   5 [n] signals.)
 
   Step  110 : Setting magnitudes
 
 R ( k|τ   c   &lt;k&lt;τ   c +Δ 1 , if  k&lt;N )
 
to be zero and the determinant index
 
τ c 
 
to be(
 
τ c 
 
+Δ1) and calculating the determinant magnitude
 
R(τ c )
 
corresponding to the determinant index
 
τ c 
 
of the S 1 [n] and S 5 [n] signals; go to step  106 ; (The determinant magnitude
 
R(τ c )
 
is equal to
 
             ∑     n   =   0       N   -   1       ⁢           ⁢         S   1     ⁡     [   n   ]       *         S   2     ⁡     [     n   +     τ   C       ]       .             
)
 
   Step  140 : Setting magnitudes
 
 R ( k|τ   c   &lt;k&lt;τ   c +Δ 2 , if  k&lt;N )
 
to be zero and the determinant index
 
τ c 
 
to be(
 
τ c 
 
+Δ2) and calculating the determinant magnitude
 
R(τ c )
 
corresponding to the determinant index
 
τ c 
 
of the S 1 [n] and S 5 [n] signals; go to step  106 ;
 
   Step  170 : Setting the determinant index
 
τ c 
 
to be
 
(τ c +1)
 
and calculating the determinant magnitude
 
R(τ c )
 
corresponding to the determinant index
 
τ c 
 
of the S 1 [n] and S 5 [n] signals; go to step  106 ;
 
   Step  200 : Determining the maximum index
 
τ max 
 
corresponding to the maximum magnitude R max  in the autocorrelogram  30 ;
 
   Step  202 : Delaying the S 5 [n] signal by the maximum index
 
τ max 
 
and forming an S 4 [n] signal;
 
   Step  204 : Weighing the S 1 [n] signal and adding to the S 4 [n] signal and forming the S 3 [n] signal; (The S 3 [n] signal=S 1 [n] signal, where 0&lt;=n&lt;([N/3]+
 
τ max 
 
); =(N−n)/(N−([N/3]+
 
τ max 
 
))*S 1 [n]+(n−([N/3]+ max ))/(N−([N/3]+
 
τ max 
 
))*S 4 [n−([N/3]+
 
τ max 
 
)], where ([N/3]+
 
τ max 
 
)&lt;=n&lt;N; =S 4 [n−([N/3]+
 
τ max 
 
)], where N&lt;=n&lt;=(N+[N/3]+
 
τ max 
 
))
 
   Step  300 : Updating the first threshold th 1  and second threshold th 2  based on the maximum magnitude R max ; and(Since the S 1 [n] and S 2 [n] signals are both derived from an S[n] derived from an original signal S org  (an audio or video signal), any sampling signals in the S[n] following the S 1 [n] and S 2 [n] signals, such as an S 6 [n] signal and an S 7 [n] signal, have certain characteristics similar to those of the S 1 [n] and S 2 [n] signals. Therefore, the maximum magnitude R max  calculated in step  200  can be used to be an updating reference to update the first threshold th 1  and the second threshold th 2  needed for the synthesizing of the S 6 [n] and S 7 [n] signals, omitting the necessity to set too small and the first threshold th 1  and second threshold th 2  from calculating the wrong maximum index
 
τ′ max 
 
, too small the first threshold th 1  and second threshold th 2  increasing the burden for the DSP chip to calculate unnecessary magnitudes.)
 
   Step  302 : End. 
   Please refer to  FIG. 4 , which is a schematic diagram demonstrating how the method synthesizes the S 3 [n] signal from the S 1 [n] and S 2 [n] signals according to the present invention. In  FIG. 4 , a first part  400  shows the S 1 [n] and S 2 [n] signals in the step  102  of the method  100 , a second part  402  shows the maximum index
 
τ max 
 
and the S 4 [n] signal calculated from the step  103  to step  202  of the method  100 , and a third part  404  shows the S 3 [n] signal synthesized from the S 1 [n] and S 4 [n] signals in the step  204  of the method  100 .
 
   In the preferred embodiment of the present invention, the magnitudes
 
 R ( k|τ&lt;k&lt;τ+Δ   1′2 , if  k&lt;N )
 
calculated in the steps  110  and  114  of the method  100  are all set to be zero. However, these magnitudes can be set to be any values, equal or different from each other, as long as these values are all smaller, preferably far smaller, than the maximum magnitude R max .
 
   If the S 1 [n] signal is the same as the S 2  [n] signal and both are derived from the S[n] at an identical region, as shown in  FIG. 5 , the method  100  in fact elongates the S 1 [n]. On the contrary, if the S 1 [n] signal and the S 2 [n] signals are different from each other and are derived from the S[n] at two distinct regions respectively, as shown in  FIG. 6 , the method  100  in fact combines and shortens the S 1 [n], an S [n] (discarded) and the S 2 [n] signals into the S 3 [n] signal. 
   In contrast to the prior art, the method of the present invention compares a temporary magnitude (R c ) in an autocorrelogram with a threshold (th 1  or th 2 ) and calculates magnitudes corresponding to indexes lagging a temporary index corresponding to the temporary magnitude by a predetermined number without calculating all magnitudes in the autocorrelogram, saving time for a DSP chip to calculate the maximum index
 
τ max 
 
and therefore promoting the efficiency of a computer where the DSP chip is installed in accordingly. In the preferred embodiment of the present invention, the first pre-determined number is 24 while the second predetermined number is 6, the first threshold th 1  and the second thresholds th 2  can be set to be R max /2 and R max /4 respectively, that is numbers truncating the maximum magnitude R max  by one and two bits respectively, and count of the calculation can be reduced to ten percent without impacting quality of the S 3 [n] signal.
 
   Following the detailed description of the present invention above, those skilled in the art will readily observe that numerous modifications and alterations of the device may be made while retaining the teachings of the invention. Accordingly, the above disclosure should be construed as limited only by the metes and bounds of the appended claims.