Speeding up audio without changing pitch by comparing dominant frequencies

[0002] This invention relates to audio and speech processing, more particularly, to speeding up the audio signal or speech without changing pitch, while maintaining acceptable quality and minimizing processing time.

[0003] This invention will demonstrate how designing a computer program that uses a fast Fourier transform can accomplish the goal of pitch stabilization, i.e., speed up wave audio files (extension: wav) without changing the pitch.

[0004] Speeding up audio or speech generally results in change of pitch and decreased quality. Previous inventions were complex in their methods to protect the integrity of the original information.

[0005] When the playback speed of audio increases, the pitch increases respectively. According to the Similarity Theorem, decreased time (increased playback rate) results in higher frequencies which translates to higher pitch (Zonst 1995). This phenomenon is illustrated when a 33⅓ RPM record is played at 78 RPM. Not only is the resulting sound difficult to understand, but the speaker also is unidentifiable, sounding like a chipmunk.

[0006] An alternative method to achieve this goal is to remove data at a fixed sampling rate, whether the data is redundant (duplicate) or original. Other methods use more complex and process time consuming methods by performing an inverse mathematical manipulation such as an inverse Fourier transform to recreate the shortened information. A variety of encoding methods are used for transmitting audio signals that are not easily manipulated for speeding up the original signal. Simpler approaches which just eliminate periods of silence do not produce a quality result.

[0007] In general, while these other inventions examine various aspects of the objective of this invention, they have not provided a satisfactory conclusion of the combination of simplicity and quality.

[0008] It is the principal object of this invention to create a fast and low cost method to speed up an audio signal without changing pitch while maintaining integrity for the understanding of the information.

[0009] Another objective for this invention to operate with minimal processing requirements for the computer or other device that will be performing the required data manipulations.

[0010] Another objective for this invention is to provide sufficient final audio quality without the complications extreme processing requirements of other methods.

[0011] The trigonometric Fourier series, f(t) in Eq.1, can express any physically realizable function to a desired degree of accuracy by the summation of sinusoids (sine and cosine waves) of various frequencies and a constant term. In Eq. 1, “n” counts the frequencies. The fundamental, one cycle in the waveform domain, is represented by n=1. Successive values of n represent the respective harmonics. For example, n=3 represents the third harmonic, which corresponds to three cycles of the sinusoid in the waveform domain. (Hsu 1984; Zonst 1995)

[0012] Fourier Analysis

[0013] Fourier Series $\begin{array}{cc}f\left(t\right)=a_0+\sum _{n=1}^{\infty }\left(a_n\cos \left(n{\omega }_{0}t\right)+b_n\sin \left(n{\omega }_{0}t\right)\right)& \mathrm{Eq}.1\end{array}$

[0014] where

[0015] ω₀=2π/T=2πf

[0016] In Eq. 1 the limit of summation of the frequencies is infinity, an impossibility in a “real life” system.

[0017] The traditional representation of a function is the time domain. Time is the independent variable, and amplitude is the dependent variable. The frequency domain is another way to represent the same function. Because of the Fourier series, any physically realizable function can be represented as a series of sinusoids. In the frequency domain, frequency (represented by “n” in Eq. 1) is the independent variable, and the corresponding amplitude (represented by “a_n” or “b_n” in Eq. 1) is the dependent variable. These amplitudes are also known as Fourier coefficients. (Zonst 1995). Most sound analysis, including this invention, is performed in the frequency domain. A Fourier transform is a mathematical device to convert between the time and frequency domains. The discrete Fourier transform, also known as the digital Fourier transform, or the DFT, is used to determine the Fourier coefficients for the data points of “digitized” data. Digitized data is a series of discrete data points, instead of a continuous curve of an infinite number of points. In “real-life” applications, discrete data and a finite number of frequencies must be used, because real-life situations must deal with finite quantities. (Bergland 1969)

[0018] Eq. 2 is an example of a DFT used to determine the Fourier coefficients for cosine. To find the coefficient of the cosine of frequency f, first multiply and sum each discrete value of the function by a unit cosine wave of that frequency. Then find the average value, the desired information, by dividing the summed value by the number of data points, N. $\begin{array}{cc}\mathrm{DFT}\mathrm{Cos}\left(f\right)=1/N\sum _{t=0}^{N-1}f\left(t\right)\mathrm{Cos}\left(ft\right)& \mathrm{Eq}.2\end{array}$

[0019] where

[0020] f=discrete frequency

[0021] N=number of discrete data points

[0022] t=discrete times

[0023] DFTCos(f)=amplitude of the cosine wave of frequency f

[0024] To find the sin values, replace cosine with sine above equation

[0025] The problem with the DFT is its slow execution. An array of N points, N=2ⁿ, requires N²complex operations to perform a DFT. A “complex operation” includes evaluating sine and cosine functions, multiplying by the data point, and adding these products to the sums of the other operations. However, an FFT requires only N×n operations. For example, for an array size of 1,024 points (n=10) representing under one tenth of a second of audio, a DFT would require 1,048,576 complex operations, while an FFT would require only 10,240 complex operations. The difference in execution time between an FFT and a DFT is further magnified when full-length audio is used. (Zonst 1995)

[0026] In addition, the FFT reduces round-off errors, meaning it is more accurate than the DFT. (Cochran et al. 1967)

[0027] According to the addition theorem, the Fourier transform of the sum of two functions is equal to the sum of the Fourier transforms of the two functions (Zonst 1995)

[0028] According to the shifting theorem, “ . . . if a time domain function is shifted in time, the amplitude of the frequency components will remain constant, but the phases of the components will shift linearly—proportional to both the frequency of the component and the amount of the time shift.” The shift at the Nyquist frequency will always be 180° (π radians) multiplied by the number of data points the time domain function was shifted. (Zonst 1995)

[0029] “Stretching,” a method of expanding digitized data, is accomplished by placing zeros in between the data points in the time domain, thereby repeating the spectrum of the original function in the frequency domain, with the amplitudes (coefficients) of the frequency components halved. (Zonst 1995)

[0030] A DFT on an 8 point array would need 64 complex operations. However, if the 8 point array were split into two 4 point arrays, each 4 point DFT would need only 16 complex operations. Thus, the total number of operations for the two 4 point DFTs would be 32—half the number of the full 8 point DFT. This “divide and conquer” process is the key to the FFT. (Zonst 1995; Transnational College of LEX 1997)

[0031] The theory behind the FFT algorithm rests on the addition, shifting, and stretching theorems. The proof begins with the following 8 point array:

[0032] |DATA ARRAY 0|=|D0, D1, D2, D3, D4, D5, D6, D7|  Eq.3

[0033] The addition theorem allows Eq. 3 to be divided into two arrays without changing the transform:

[0034] |DATA ARRAY 1′|=|D0, 0, D2, 0, D4, 0, D6, 0|  Eq. 4

[0035] |DATA ARRAY 2′|=|0, D1, 0, D3, 0, D5, 0, D7|  Eq. 5

[0036] where

[0037] |DATA ARRAY 0|=|DATA ARRAY 1′|+|DATA ARRAY 2′|  Eq. 6

[0038] In this case each array would require 64 operations to perform a DFT, thus doubling the number of operations. Yet, this situation must be examined further. With the Stretching Theorem, the transform of a stretched array is the same as the transform of the unstretched array, except that it is repeated. The fact that the amplitudes are halved can be ignored during this discussion, because the amplitudes will still be present in the same ratios. (Zonst 1995)

[0039] Xform |DATA ARRAY 1′|=|F0, F2, F4, F6, F0, F2, F4, F6|  Eq. 7

[0040] As expected, the transform of the four data points is repeated. But, if the zeros are removed from the array, the same components will result, but only once.

[0041] |DATA ARRAY 1|=|D0, D2, D4, D6|  Eq. 8

[0042] Xform |DATA ARRAY 1|=|F0, F2, F4, F6|  Eq. 9

[0043] In the same fashion:

[0044] |DATA ARRAY 2|=|D1, D3, D5, D7|  Eq. 10

[0045] Xform |DATA ARRAY 2|=|F1, F3, F5, F7|  Eq. 11

[0046] After the transforms in equations 9 and 11 are obtained the transforms of |DATA ARRAY 1′| and |DATA ARRAY 2′| are combined. The transform of |DATA ARRAY 1′| is obtained by stretching, or repeating the transform of |DATA ARRAY 1|. However, to get from the transform of |DATA ARRAY 2| back to the transform of |DATA ARRAY 2′|, the transform of the former must be stretched and then shifted. The stretching is accomplished as with the transform of |DATA ARRAY 1|—the spectrum must be repeated. The shifting is accomplished by the frequency equivalent of a one point data shift in the time domain, phase shifts ranging from zero (at the zero frequency component) to π (at the Nyquist frequency). Mathematically, each component must be shifted by 2πf/N radians, where f=frequency and N=total number of frequencies. The two transforms can then be summed together to form the transform of the original function. (Zonst 1995)

[0047] Using the same 8 point array, the two 4 point arrays can be split into four 2 point arrays. These in turn can be split into eight 1 point “arrays.” The one point DFT is special; only one frequency component exists, and the transform is equal to itself. Thus, there is no real DFT to be performed. Instead, the FFT only shifts and adds.

[0048] The above discussion of the FFT states that the original array is divided by two until a one point array is reached. Thus, the original array must be a power of two. However, when a sound is recorded, its size cannot be controlled. Thus, the array must be extended to the nearest power of two by “packing” it with zeros. “Packing” was a term used by the inventor to explain the process of filling the empty array spaces with zeros. This term was first used by Robert Blackwell in 1965.

[0049] When working with audio, a “sample” is a reading of the amplitude of the sound wave. According to the Nyquist rule, the sampling rate, the number of samples taken per second, must be at least twice the highest frequency, known as the Nyquist frequency. If this 2:1 ratio is abandoned, a phenomenon termed “aliasing” will occur, meaning that all frequencies above the Nyquist frequency are folded back into the spectrum, yielding incorrect values. In other words, the data from the frequencies above the Nyquist frequency interfere with the data from the frequencies at or below the Nyquist frequency. For example, for sixteen data points the Nyquist frequency is eight. If frequencies above eight are present, aliasing will occur. The solution is to filter off frequencies above the Nyquist frequency. (Zonst 1995; Zonst 1997)

[0050] The program developed to illustrate this invention uses a sampling rate of 11,025 Hertz. This value may be set in a software such as the Multimedia setup in the Control Panel in Microsoft's Windows 95 or 98. (“Hertz,” or “Hz,” is the unit for “per second,” in this case samples per second.) Thus, the Nyquist frequency of 5512 Hz is more than sufficient, as the typical frequencies of human voice range from 300 Hz to 3000 Hz (http://support.dialogic.com/releases/dos/voicebrick/vfg/VFG-76.htm). Additionally, no filtering is required, as there are no major frequency components above the Nyquist frequency.

[0051] To illustrate this invention a program is created using Microsoft Visual Basic 5 Service Release 3 and a personal computer with an Intel Pentium II processor to speed up audio without changing the pitch. However, rather than speeding up the entire sound, and making the speech faster by a certain increment, an original approach not previously discussed or attempted was designed to eliminate periods of silence and repeated sounds. For example, “Thisssss<pause> is aaaa<pause> tesssst” is shortened to “This is a test.” Thus, the speed-up is not equal throughout the sound.

[0052] After the sound is acquired, it is placed in an array, and “packed” with zeros to the next power of two. The data must then be divided into “chunks” (frames or subframes). To comply with the requirements for the FFT, the chunk must be of the size 2ⁿ. An FFT was performed against each data chunk to find the coefficients of the frequencies. Next, the absolute values of the coefficients of the cosine and sine of the same frequency were averaged together, to form one value for each frequency. The frequency/frequencies with the highest coefficients are found for each chunk, hereafter to be known as the “signature” of the chunk. This researcher's program compared each chunk with the next chunk. If two successive chunks had the same signature, the second was marked. The original data was then copied to form the output, with the marked chunks ignored. In effect, the second chunk was eliminated. An inverse FFT was never performed. Instead, the FFT was used to ascertain what should be eliminated, and then the original data was adjusted accordingly.

[0053] Code 1 located in the Appendix of this document, is the FFT algorithm used in this researcher's program. The FFT routine first declares variables and prepares the program form for the FFT. It then takes readings of the sound wave at 11,025 Hz and stores the samples in “SoundData( ),” a process written by this researcher. It then calls “PackData” (Code 2 located in the Appendix of this document), a routine developed by this researcher to “pack” SoundData( ) with zeros up to the next power of 2, because the FET only works on powers of two. The FFT then continues to set up variables and arrays to be used during computation. The FFT loop begins at the comment “Outer loop of FFT.”

[0054] The outer loop counts the data chunks, and controls the FFT so that an FFT is performed on each chunk. The “DataStart” variable is initialized at the beginning and represents the location of the first data sample of the chunk in SoundData( ). The data for one chunk is then copied from SoundData into “c(0,x).” The two working arrays in the FFT are “c(x,x)” and “s(x,x).” (The x's are used to make it clear that these are two-dimensional arrays.) These arrays hold only the data for one chunk at a time, unlike SoundData( ) which holds the data for every chunk

[0055] The FFT algorithm begins with the stage loop which counts the partial DFTs. The “Universal Butterfly” (labeled on Code 1) performs the shifting and summing process of the FFT. This is the main part of the FFT, and is carried out in three “For . . . Next” loops: the “freq” loop and the two “data” loops. The FFT is completed and the data is copied from the working arrays into the output arrays, which are fcos(x,x) and fsin(x,x). These arrays, like SoundData( ) hold the data from all chunks at once. The difference is that SoundData( ) is in the time domain and fcos(x,x) and fsin(x,x) are in the frequency domain. This process is then performed on the next chunk.

[0056] Code 3 located in the Appendix of this Document, the “Compress” routine, is the main routine for speeding up the sound. The “Compress” routine is the heart of the program, as it controls the routines that analyzes the sound, and then speeds up the sound without changing the pitch. It is called after the FFT has been performed on the entire sound. The first action is the calling of the “Loudest” routine (Code 4 located in the Appendix of this document), to find the signature for each chunk. After calling Loudest, it compares the signatures of successive chunks, and marks a “True” in the boolean array (killchunk( )) if the chunk should be gotten rid of, and a “False” if the chunk should be kept. Next, it calls the “SquishCopy” routine (Code 5 located in the Appendix of this document) which uses “killchunk( )” to copy the needed chunks. Lastly, it calls “WaveSave” to save the new sound to a temporary file. If the user of the program chooses to do so, he or she may later save the sound to a permanent file. The code for the “WaveSave” routine is not included because it is not part of this researcher's speed up process.

[0057] The “Loudest” routine finds the signature of each chunk. First, it averages together the absolute values of the sine and cosine of each frequency to obtain one positive value for each frequency. These amplitude values are stored in the “val( )” array. The corresponding frequency numbers are stored in the “ix( )” array. Next, the Loudest routine finds the frequency with the highest amplitude and stores the corresponding frequency number in the “fsig( )” array. It then sets the amplitude of the highest frequency to “−1,” so it is not picked up again when searching for the next highest frequency. The procedure repeats the process of finding the frequency with highest amplitude NumSig times. NumSig stands for the number of frequencies in the signature. One would represent the loudest frequency only; two would be the two loudest; etc. During the experimentation process the user tested various values for NumSig.

[0058] “Loudest” does not check the zeroth frequency, stored in val(0), because this is the constant term. Representing a shift in amplitude of the entire time domain wave form, and having a direct relationship with the volume of the entire wave, not a specific frequency, this value will often be higher than all other frequencies. Had Loudest stored this value in the signature, it would be possible that all the chunks would have the same signature, and the entire sound would be eliminated.

[0059] Code 5 located in the Appendix of this document, shows the “SquishCopy” routine, which copies only the needed chunks of the old data. The data is copied from “SoundData( )” back into “SoundData( ).” “OldIndex” represents the location of the first data point of the chunk to be copied, and “NewIndex” represents the target location of the first data point. “OldIndex” increases each time through the loop. “NewIndex” only increases when a copy is made; it stays the same for boolean values of true, insuring that the data is copied to the correct location. Although the data is copied to and from the same array, the needed data is never over written. This is because NewIndex will always be lower or equal to OldIndex. Thus, this researcher's program looks at all of the old data before overwriting. At the end, SoundLength is set to be the length of the new sound, so that when the Compress procedure calls the WaveSave procedure, the correct data is saved.

[0060] FIG. 1 is a functional block diagram of the preferred embodiment.

[0061] FIG. 1 illustrates the preferred method of the present invention. When working with audio, a “sample” is a reading of the amplitude of the sound wave. According to the Nyquist rule, the sampling rate or the number of samples taken per second, must be at least twice the highest frequency, also known as the Nyquist frequency. Therefore, the audio source 10 uses a sampling rate of 11,025 Hertz. The Nyquist frequency of 5512 Hertz is more than sufficient, as the typical frequencies of human voice range from 300 Hertz to 3000 Hertz. No additional filtering is employed since there are no major frequency components above the Nyquist frequency.

[0062] For illustrating the capabilities of this invention, a program was created using Microsoft Visual Basic 5 Service Release 3 on a personal computer with an Intel Pentium II processor. After the sound is acquired, it is placed into an array or wave table, 12, and “packed” 14 with zeros to the next power of two. The data must then be divided into “chunks (frames or subframes),” 16. To comply with the requirements for the fast Fourier transform (FFT) used, the chunk size 18, must be of the size 2ⁿ. The chunk size is a variable input. As chunk size decreases, the length of sound will decrease, as smaller chunk sizes lead to higher compression. Smaller chunk sizes represent less time, thereby increasing the chance for consecutive identical signatures or dominant frequencies. Although each chunk eliminated would save less time as the chunk size gets smaller, this is counteracted by the larger number of chunks being eliminated. Sound quality will diminish as chunk size decreases.

[0063] An FFT, 20, is performed on each data chunk to find the sine, 22, and cosine coefficients, 24, of the frequencies. The absolute values of the sine and cosine coefficients of the same frequency are averaged together, to form one value for each frequency within the each chunk, 26. The frequency/frequencies with the highest values are found for each chunk and are defined hereinafter as the signature or dominant frequency/frequencies, 28. The terminology of dominant frequency or dominant frequencies or signature or signatures may be considered interchangeable for the purposes of this document and claims. The number of frequencies in the signature is a variable that can be input into the process, 30. However, a change in the number of frequencies in the signature proves to have no effect on the length of the sound, meaning the most dominant frequency is the important one.

[0064] A comparison is made between the signatures of one chunk to the next, 32. If two successive chunks have the same signature, the second chunk in the original wave table is marked, 34. The original data can then be copied or stored, 38, without the marked chunks, 36. The shortened signal, 40, can now be played or stored.

[0065] An inverse FFT was never performed. Instead, the FFT was used to ascertain what should be eliminated, and then the original data was advised accordingly.