Computational effectiveness enhancement of frequency domain pitch estimators

FIELD OF THE INVENTION

[0001] The present invention relates generally to methods and apparatus for processing of audio signals, and specifically to methods for estimating the pitch of a speech signal.

BACKGROUND OF THE INVENTION

[0002] Speech sounds are produced by modulating air flow in the speech tract. Voiceless sounds originate from turbulent noise created at a constriction somewhere in the vocal tract, while voiced sounds are excited in the larynx by periodic vibrations of the vocal cords. Roughly speaking, the variable period of the laryngeal vibrations gives rise to the pitch of the speech sounds. Low-bit-rate speech coding schemes typically separate the modulation from the speech source (voiced or unvoiced), and code these two elements separately. In order to enable the speech to be properly reconstructed, it is necessary to accurately estimate the pitch of the voiced parts of the speech at the time of coding. A variety of techniques have been developed for this purpose, including both time- and frequency-domain methods.

[0003] The Fourier transform of a periodic signal, such as voiced speech, has the form of a train of impulses, or peaks, in the frequency domain. This impulse train corresponds to the line spectrum of the signal, which can be represented as a sequence {(a_i, θ_i)}, wherein θ_iare the frequencies of the peaks, and a_iare the respective complex-valued line spectral amplitudes. To determine whether a given segment of a speech signal is voiced or unvoiced, and to calculate the pitch if the segment is voiced, the time-domain signal is first multiplied by a finite smooth window. The Fourier transform of the windowed signal is then given by: <maths id="MATH-US-00001" num="1"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>X</mi><mo></mo><mrow><mo>(</mo><mi>θ</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munder><mo>∑</mo><mi>k</mi></munder><mo></mo><mrow><msub><mi>a</mi><mi>k</mi></msub><mo></mo><mrow><mi>W</mi><mo></mo><mrow><mo>(</mo><mrow><mi>θ</mi><mo>-</mo><msub><mi>θ</mi><mi>k</mi></msub></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mi>EQ</mi><mo>.</mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>1</mn></mrow></mtd></mtr></mtable></math><img file="US20040167775A1-20040826-M00001.TIF" id="EMI-M00001" he="19.93005" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00001" attachment-type="nb" file="US20040167775A1-20040826-M00001.NB" /></attachments></maths>

[0004] wherein W(θ) is the Fourier transform of the window.

[0005] Given any pitch frequency, the line spectrum corresponding to that pitch frequency could contain line spectral components at all multiples of that frequency. It therefore follows that any frequency appearing in the line spectrum may be a multiple of a number of different candidate pitch frequencies. Consequently, for any peak appearing in the transformed signal, there will be a sequence of candidate pitch frequencies that could give rise to that particular peak, wherein each of the candidate frequencies is an integer dividend of the frequency of the peak. This ambiguity is present whether the spectrum is analyzed in the frequency domain, or whether it is transformed back to the time domain for further analysis.

[0006] Frequency-domain pitch estimation is typically based on analyzing the locations and amplitudes of the peaks in the transformed signal X(θ), such as by correlating the spectrum with the “teeth” of a prototypical spectral “comb.” The pitch frequency is given by the comb frequency that maximizes the correlation of the comb function with the transformed speech signal.

[0007] A related class of schemes for pitch estimation are known as “cepstral” schemes, where a log operation is applied to the frequency spectrum of the speech signal, and the log spectrum is then transformed back to the time domain to generate the cepstral signal. The pitch frequency is the location of the first peak of the time-domain cepstral signal. This corresponds precisely to maximizing over the period T, the correlation of the log of the amplitudes corresponding to the line frequencies z(i) with cos(ω(i)T). For each guess of the pitch period T, the function cos(ωT) is a periodic function of ω. It has peaks at frequencies corresponding to multiples of the pitch frequency 1/T. If those peaks happen to coincide with the line frequencies, then 1/T is a good candidate to be the pitch frequency, or some multiple thereof.

[0008] A common method for time-domain pitch estimation uses correlation-type schemes, which search for a pitch period T that maximizes the cross-correlation of a signal segment centered at time t and one centered at time t−T. The pitch frequency is the inverse of T.

[0009] Both time- and frequency-domain methods of pitch determination are subject to instability and error, and accurate pitch determination is therefore computationally intensive. In time domain analysis, for example, a high-frequency component in the line spectrum results in the addition of an oscillatory term in the cross-correlation. This term varies rapidly with the estimated pitch period T when the frequency of the component is high. In such a case, even a slight deviation of T from the true pitch period will reduce the value of the cross-correlation substantially and may lead to rejection of a correct estimate. A high-frequency component will also add a large number of peaks to the cross-correlation, which complicate the search for the true maximum. In the frequency domain, a small error in the estimation of a candidate pitch frequency will result in a major deviation in the estimated value of any spectral component that is a large integer multiple of the candidate frequency.

[0010] With currently known techniques, an exhaustive search with high resolution must be made over all possible candidates and their multiples in order to avoid missing the best candidate pitch for a given input spectrum. It is often necessary, dependent on the actual pitch frequency, to search the sampled spectrum up to high frequencies, such as above 1500 Hz. At the same time, the analysis interval, or window, must be long enough in time to capture at least several cycles of every conceivable pitch candidate in the spectrum, resulting in an additional increase in complexity. Analogously, in the time domain, the optimal pitch period T must be searched for over a wide range of times and with high resolution. The search in either case consumes substantial computing resources. The search criteria cannot be relaxed even during intervals that may be unvoiced, since an interval can be judged unvoiced only after all candidate pitch frequencies or periods have been ruled out. Although pitch values from previous frames are commonly used in guiding the search for the current value, the search cannot be limited to the neighborhood of the previous pitch. Otherwise, errors in one interval will be perpetuated in subsequent intervals, and voiced segments may be confused for unvoiced.

SUMMARY OF THE INVENTION

[0011] It is an object of the present invention to provide improved methods and apparatus for determining the pitch of an audio signal, and particularly of a speech signal.

[0012] In one aspect of the present invention, a method for estimating a pitch frequency of a speech signal is provided, including finding a line spectrum of the signal, the spectrum including spectral lines having respective line amplitudes and line frequencies, computing a utility function which is indicative, for each candidate pitch frequency in a given pitch frequency range, of a compatibility of the spectrum with the candidate pitch frequency, and estimating the pitch frequency of the speech signal responsive to the utility function.

[0013] In another aspect of the present invention, computing the utility function includes computing at least one influence function that is periodic in a ratio of the frequency of one of the spectral lines to the candidate pitch frequency. Computing the at least one influence function also preferably includes computing a function of the ratio having maxima at integer values of the ratio and minima therebetween. Computing the function of the ratio also preferably includes computing values of a piecewise linear function c(f), having a maximum value in a first interval surrounding f=0, a minimum value in a second interval surrounding f=1/2, and a value that varies linearly in a transition interval between the first and second intervals.

[0014] In another aspect of the present invention, computing the at least one influence function includes computing respective influence functions for multiple lines in the spectrum, and computing the utility function includes computing a superposition of the influence functions. Preferably, the respective influence functions include piecewise linear functions having break points, and computing the superposition includes calculating values of the influence functions at the break points, such that the utility function is determined by interpolation between the break points. Computing the respective influence functions also preferably includes computing at least first and second influence functions for first and second lines in the spectrum in succession, and computing the utility function includes computing a partial utility function including the first influence function and then adding the second influence function to the partial utility function by calculating the values of the second influence function at the break points of the partial utility function and calculating the values of the partial utility function at the break points of the second influence function.

[0015] In another aspect of the present invention, a method for estimating a pitch frequency of a speech signal is provided, including determining a line spectrum of a frame of a speech signal, the spectrum including a plurality of spectral lines having respective line amplitudes and line frequencies, selecting a predefined number of the spectral lines having the highest amplitudes among the spectral lines, where the number of selected spectral lines is less then the total number of the plurality of spectral lines, calculating a preliminary utility function over a pitch frequency range, thereby providing a preliminary utility function value for each pitch frequency in the range that is a measure of a compatibility of the selected spectral lines with the pitch frequency, identifying a predefined number of preliminary pitch frequency candidates at least partly responsive to the preliminary utility function, where each preliminary pitch frequency candidate is a local maximum of the preliminary utility function, calculating a final utility score for each of the preliminary pitch frequency candidates, and selecting any of the plurality of preliminary pitch frequency candidates to be an estimated pitch frequency of the speech signal at least partly responsive to any of the final utility scores.

[0016] In another aspect of the present invention the calculating a preliminary utility function step includes computing an influence function respective to each of the selected spectral lines, where the influence function is periodic in a ratio of the frequency of the spectral line to any pitch frequency, and computing a superposition of the influence functions.

[0017] In another aspect of the present invention the computing an influence function step includes computing a function of the ratio having maxima at integer values of the ratio and minima therebetween.

[0018] In another aspect of the present invention the computing an influence function step includes computing values of a piecewise linear function c(f), having a maximum value in a first interval surrounding f=0, a minimum value in a second interval surrounding f=1/2, and a value that varies piecewise linearly in a transition interval between the first and second intervals.

[0019] In another aspect of the present invention the influence functions are piecewise linear functions, and where the computing a superposition step includes calculating values of the influence functions at their break points such that the preliminary utility function is determined by interpolation between the break points.

[0020] In another aspect of the present invention the computing the influence function step includes computing at least first and second influence functions for first and second spectral lines from among the selected spectral lines in succession, and where the computing a preliminary utility function step includes computing a partial utility function including the first influence function, and adding the second influence function to the preliminary utility function by calculating the values of the second influence function at the break points of the preliminary utility function and calculating the values of the preliminary utility function at the break points of the second influence function.

[0021] In another aspect of the present invention the determining a pitch frequency candidate step includes preferentially selecting a local maximum of the preliminary utility function that is near in frequency to a previously-estimated pitch frequency of a preceding frame of the speech signal.

[0022] In another aspect of the present invention the calculating a final utility score step includes computing an influence function respective to each of the spectral lines, where the influence function is periodic in a ratio of the frequency of the spectral line to any pitch frequency, and computing a sum of the influence functions.

[0023] In another aspect of the present invention the computing an influence function step includes computing a function of the ratio having maxima at integer values of the ratio and minima therebetween.

[0024] In another aspect of the present invention the computing the function of the ratio step includes computing values of a piecewise linear function c(f), having a maximum value in a first interval surrounding f=0, a minimum value in a second interval surrounding f=1/2, and a value that varies piecewise linearly in a transition interval between the first and second intervals.

[0025] In another aspect of the present invention the selecting a pitch frequency step includes preferentially selecting one of the preliminary pitch frequency candidates that has a higher final utility score than another one of the preliminary pitch frequency candidates.

[0026] In another aspect of the present invention the selecting a pitch frequency step includes preferentially selecting one of the preliminary pitch frequency candidates that has a higher frequency than another one of the preliminary pitch frequency candidates.

[0027] In another aspect of the present invention the selecting a pitch frequency step includes preferentially selecting one of the preliminary pitch frequency candidates that is near in frequency to a previously-estimated pitch frequency of a preceding frame of the speech signal.

[0028] In another aspect of the present invention the method further includes determining whether the speech signal is voiced or unvoiced by comparing the final utility score of the estimated pitch frequency to a predetermined threshold.

[0029] In another aspect of the present invention the method further includes encoding the speech signal responsive to the estimated pitch frequency.

[0030] In another aspect of the present invention apparatus is provided for estimating a pitch frequency of a speech signal, including means for determining a line spectrum of a frame of a speech signal, the spectrum including a plurality of spectral lines having respective line amplitudes and line frequencies, means for selecting a predefined number of the spectral lines having the highest amplitudes among the spectral lines, where the number of selected spectral lines is less then the total number of the plurality of spectral lines, means for calculating a preliminary utility function over a pitch frequency range, thereby providing a preliminary utility function value for each pitch frequency in the range that is a measure of a compatibility of the selected spectral lines with the pitch frequency, means for identifying a predefined number of preliminary pitch frequency candidates at least partly responsive to the preliminary utility function, where each preliminary pitch frequency candidate is a local maximum of the preliminary utility function, means for calculating a final utility score for each of the preliminary pitch frequency candidates, and means for selecting any of the plurality of preliminary pitch frequency candidates to be an estimated pitch frequency of the speech signal at least partly responsive to any of the final utility scores.

[0031] In another aspect of the present invention the means for calculating a preliminary utility function is operative to compute an influence function respective to each of the selected spectral lines, where the influence function is periodic in a ratio of the frequency of the spectral line to any pitch frequency, and compute a superposition of the influence functions.

[0032] In another aspect of the present invention the means for computing an influence function is operative to compute a function of the ratio having maxima at integer values of the ratio and minima therebetween.

[0033] In another aspect of the present invention the means for computing an influence function is operative to compute values of a piecewise linear function c(f), having a maximum value in a first interval surrounding f=0, a minimum value in a second interval surrounding f=1/2, and a value that varies piecewise linearly in a transition interval between the first and second intervals.

[0034] In another aspect of the present invention the influence functions are piecewise linear functions, and where the means for computing a superposition is operative to calculating values of the influence functions at their break points such that the preliminary utility function is determined by interpolation between the break points.

[0035] In another aspect of the present invention the means for computing the influence function is operative to compute at least first and second influence functions for first and second spectral lines from among the selected spectral lines in succession, and where the means for computing a preliminary utility function is operative to compute a partial utility function including the first influence function, and add the second influence function to the preliminary utility function by calculating the values of the second influence function at the break points of the preliminary utility function and calculating the values of the preliminary utility function at the break points of the second influence function.

[0036] In another aspect of the present invention the means for determining a pitch frequency candidate is operative to preferentially select a local maximum of the preliminary utility function that is near in frequency to a previously-estimated pitch frequency of a preceding frame of the speech signal.

[0037] In another aspect of the present invention the means for calculating a final utility score is operative to compute an influence function respective to each of the spectral lines, where the influence function is periodic in a ratio of the frequency of the spectral line to any pitch frequency, and compute a sum of the influence functions.

[0038] In another aspect of the present invention the means for computing an influence function is operative to compute a function of the ratio having maxima at integer values of the ratio and minima therebetween.

[0039] In another aspect of the present invention the means for computing the function of the ratio is operative to compute values of a piecewise linear function c(f), having a maximum value in a first interval surrounding f=0, a minimum value in a second interval surrounding f=1/2, and a value that varies piecewise linearly in a transition interval between the first and second intervals.

[0040] In another aspect of the present invention the means for selecting a pitch frequency is operative to preferentially select one of the preliminary pitch frequency candidates that has a higher final utility score than another one of the preliminary pitch frequency candidates.

[0041] In another aspect of the present invention the means for selecting a pitch frequency is operative to preferentially select one of the preliminary pitch frequency candidates that has a higher frequency than another one of the preliminary pitch frequency candidates.

[0042] In another aspect of the present invention the means for selecting a pitch frequency is operative to preferentially select one of the preliminary pitch frequency candidates that is near in frequency to a previously-estimated pitch frequency of a preceding frame of the speech signal.

[0043] In another aspect of the present invention the apparatus and further includes means for determining whether the speech signal is voiced or unvoiced by comparing the final utility score of the estimated pitch frequency to a predetermined threshold.

[0044] In another aspect of the present invention the apparatus and further includes means for encoding the speech signal responsive to the estimated pitch frequency.

[0045] In another aspect of the present invention a computer program embodied on a computer-readable medium is provided, the computer program including a first code segment operative to determine a line spectrum of a frame of a speech signal, the spectrum including a plurality of spectral lines having respective line amplitudes and line frequencies, a second code segment operative to select a predefined number of the spectral lines having the highest amplitudes among the spectral lines, where the number of selected spectral lines is less then the total number of the plurality of spectral lines, a third code segment operative to calculate a preliminary utility function over a pitch frequency range, thereby providing a preliminary utility function value for each pitch frequency in the range that is a measure of a compatibility of the selected spectral lines with the pitch frequency, a fourth code segment operative to identify a predefined number of preliminary pitch frequency candidates at least partly responsive to the preliminary utility function, where each preliminary pitch frequency candidate is a local maximum of the preliminary utility function, a fifth code segment operative to calculate a final utility score for each of the preliminary pitch frequency candidates, and a sixth code segment operative to select any of the plurality of preliminary pitch frequency candidates to be an estimated pitch frequency of the speech signal at least partly responsive to any of the final utility scores.

BRIEF DESCRIPTION OF THE DRAWINGS

[0046] The present invention will be more fully understood from the following detailed description of the preferred embodiments thereof, taken together with the drawings in which:

[0047]FIG. 1 is a schematic, pictorial illustration of a system for speech analysis and encoding, in accordance with a preferred embodiment of the present invention;

[0048]FIG. 2 is a flow chart that schematically illustrates a method for pitch determination and speech encoding, in accordance with a preferred embodiment of the present invention;

[0049]FIG. 3 is a flow chart that schematically illustrates a method for extracting line spectra and finding candidate pitch values for a speech signal, in accordance with a preferred embodiment of the present invention;

[0050]FIG. 4 is a block diagram that schematically illustrates a method for extraction of line spectra over long and short time intervals simultaneously, in accordance with a preferred embodiment of the present invention;

[0051]FIG. 5 is a flow chart that schematically illustrates a method for finding peaks in a line spectrum, in accordance with a preferred embodiment of the present invention;

[0052]FIGS. 6A, 6B, <b>6</b>C, and <b>6</b>D are flow charts that schematically illustrate a method for evaluating candidate pitch frequencies based on an input line spectrum, in accordance with a preferred embodiment of the present invention;

[0053]FIG. 7 is a plot of one cycle of an influence function used in evaluating the candidate pitch frequencies in accordance with the method of FIGS. <b>6</b>A-<b>6</b>D;

[0054]FIG. 8 is a plot of a partial utility function derived by applying the influence function of FIG. 7 to a component of a line spectrum, in accordance with a preferred embodiment of the present invention;

[0055]FIGS. 9A and 9B are flow charts that schematically illustrate a method for selecting an estimated pitch frequency for a frame of speech from among a plurality of candidate pitch frequencies, in accordance with a preferred embodiment of the present invention; and

[0056]FIG. 10 is a flow chart that schematically illustrates a method for determining whether a frame of speech is voiced or unvoiced, in accordance with a preferred embodiment of the present invention.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

[0057]FIG. 1 is a schematic, pictorial illustration of a system <b>20</b> for analysis and encoding of speech signals, in accordance with a preferred embodiment of the present invention. The system comprises an audio input device <b>22</b>, such as a microphone, which is coupled to an audio processor <b>24</b>. Alternatively, the audio input to the processor may be provided over a communication line or recalled from a storage device, in either analog or digital form. Processor <b>24</b> preferably comprises a general-purpose computer programmed with suitable software for carrying out the functions described hereinbelow. The software may be provided to the processor in electronic form, for example, over a network, or it may be furnished on tangible media, such as CD-ROM or non-volatile memory. Alternatively or additionally, processor <b>24</b> may comprise a digital signal processor (DSP) or hard-wired logic.

[0058]FIG. 2 is a flow chart that schematically illustrates a method for processing speech signals using system <b>20</b>, in accordance with a preferred embodiment of the present invention. At an input step <b>30</b>, a speech signal is input from device <b>22</b> or from another source and is digitized for further processing (if the signal is not already in digital form). The digitized signal is divided into frames of appropriate duration and relative offset, typically 25 ms and 10 ms respectively, for subsequent processing. At a pitch identification step <b>32</b>, processor <b>24</b> extracts an approximate line spectrum of the signal for each frame. The spectrum is extracted by analyzing the signal over multiple time intervals simultaneously, as described hereinbelow. Preferably, two intervals are used for each frame: a short interval for extraction of high-frequency pitch values, and a long interval for extraction of low-frequency values. Alternatively, a greater number of intervals may be used. The low- and high-frequency portions together preferably cover the entire range of possible pitch values. Based on the extracted spectra, candidate pitch frequencies for the current frame are identified.

[0059] The best estimate of the pitch frequency for the current frame is selected from among the candidate frequencies in all portions of the spectrum, at a pitch selection step <b>34</b>. Based on the selected pitch, system <b>24</b> determines whether the current frame is actually voiced or unvoiced, at a voicing decision step <b>36</b>. At an output coding step <b>38</b>, the voiced/unvoiced decision and the selected pitch frequency are used in encoding the current frame. Any suitable encoding method may be used, such as the methods described in U.S. patent applications Ser. Nos. 09/410,085 and 09/432,081. Preferably, the coded output includes features of the modulation of the stream of sounds along with the voicing and pitch information. The coded output is typically transmitted over a communication link and/or stored in a memory <b>26</b> (FIG. 1). The methods for pitch determination described herein may also be used in other audio processing applications, with or without subsequent encoding.

[0060]FIG. 3 is a flow chart that schematically illustrates details of pitch identification step <b>32</b>, in accordance with a preferred embodiment of the present invention. At a transform step <b>40</b>, a dual-window short-time Fourier transform (STFT) is applied to each frame of the speech signal. The range of possible pitch frequencies for speech signals is typically from 55 to 420 Hz. This range is preferably divided into two regions: a lower region from 55 Hz up to a middle frequency F_b(typically about 90 Hz), and an upper region from F_bup to 420 Hz. As described hereinbelow, for each frame a short time window is defined for searching the upper frequency region, and a long time window is defined for the lower frequency region. Alternatively, a greater number of adjoining windows may be used. The STFT is applied to each of the time windows to calculate respective high- and low-frequency spectra of the speech signal.

[0061] Processing of the short- and long-window spectra preferably proceeds on separate, parallel tracks. At spectrum estimation steps <b>42</b> and <b>44</b>, high- and low-frequency line spectra, having the form {(a_i, θ_i)}, defined above, are derived from the respective STFT results. The line spectra are used at candidate frequency finding steps <b>46</b> and <b>48</b> to find respective sets of high- and low-frequency candidate values of the pitch. The pitch candidates are fed to step <b>34</b> (FIG. 2) for selection of the best pitch frequency estimate among the candidates. Details of steps <b>40</b> through <b>48</b> are described hereinbelow with reference to FIGS. 4, 5 and <b>6</b>A-<b>6</b>D.

[0062]FIG. 4 is a block diagram that schematically illustrates details of transform step <b>40</b>, in accordance with a preferred embodiment of the present invention. A windowing block <b>50</b> applies a windowing function, preferably a Hamming window 25 ms in duration, as is known in the art, to the current frame of the speech signal. A transform block <b>52</b> applies a suitable frequency transform to the windowed frame, preferably a Fast Fourier Transform (FFT) with a resolution of 256 or 512 frequency points, dependent on the sampling rate.

[0063] Preferably, the output of block <b>52</b> is fed to an interpolation block <b>54</b>, which is used to increase the resolution of the spectrum, such as by applying a Dirichlet kernel <maths id="MATH-US-00002" num="2"><math overflow="scroll"><mrow><mrow><mi>D</mi><mo></mo><mrow><mo>(</mo><mrow><mi>θ</mi><mo>,</mo><mi>N</mi></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mfrac><mrow><mi>sin</mi><mo></mo><mrow><mo>(</mo><mrow><mi>N</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mi>θ</mi><mo>/</mo><mn>2</mn></mrow></mrow><mo>)</mo></mrow></mrow><mrow><mi>sin</mi><mo></mo><mrow><mo>(</mo><mrow><mi>θ</mi><mo>/</mo><mn>2</mn></mrow><mo>)</mo></mrow></mrow></mfrac></mrow></math><img file="US20040167775A1-20040826-M00002.TIF" id="EMI-M00002" he="18.00225" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00002" attachment-type="nb" file="US20040167775A1-20040826-M00002.NB" /></attachments></maths>

[0064] to the FFT output coefficients X^d[k], giving interpolated spectral coefficients: <maths id="MATH-US-00003" num="3"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>X</mi><mo></mo><mrow><mo>(</mo><mi>θ</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>N</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo></mo><mrow><mfrac><mn>1</mn><mi>N</mi></mfrac><mo></mo><mrow><msup><mi>X</mi><mi>d</mi></msup><mo></mo><mrow><mo>[</mo><mi>k</mi><mo>]</mo></mrow></mrow><mo></mo><mrow><mi>D</mi><mo></mo><mrow><mo>(</mo><mrow><mrow><mi>θ</mi><mo>-</mo><mrow><mn>2</mn><mo></mo><mi>π</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mi>k</mi><mo>/</mo><mi>N</mi></mrow></mrow></mrow><mo>,</mo><mi>N</mi></mrow><mo>)</mo></mrow></mrow><mo></mo><mi>exp</mi><mo></mo><mrow><mo>{</mo><mrow><mrow><mo>-</mo><mrow><mi>j</mi><mo></mo><mrow><mo>(</mo><mrow><mi>θ</mi><mo>-</mo><mrow><mn>2</mn><mo></mo><mi>π</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mi>k</mi><mo>/</mo><mi>N</mi></mrow></mrow></mrow><mo>)</mo></mrow></mrow></mrow><mo></mo><mrow><mrow><mo>(</mo><mrow><mi>N</mi><mo>-</mo><mn>1</mn></mrow><mo>)</mo></mrow><mo>/</mo><mn>2</mn></mrow></mrow><mo>}</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mi>EQ</mi><mo>.</mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>2</mn></mrow></mtd></mtr></mtable></math><img file="US20040167775A1-20040826-M00003.TIF" id="EMI-M00003" he="37.9323" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00003" attachment-type="nb" file="US20040167775A1-20040826-M00003.NB" /></attachments></maths>

[0065] For efficient interpolation, a small number of coefficients X^d[k] are preferably used in a near vicinity of each frequency θ. Typically, 16 coefficients are used, and the resolution of the spectrum is increased in this manner by a factor of two, so that the number of points in the interpolated spectrum is L=2N. The output of block <b>54</b> gives the short window transform, which is passed to step <b>42</b> (FIG. 3).

[0066] The long window transform to be passed to step <b>44</b> is calculated by combining the short window transforms of the current frame, X^s, and of the previous frame, Y^s, which is held by a delay block <b>56</b>. Before combining, the coefficients from the previous frame are multiplied by a phase shift of 2πmk/L, at a multiplier <b>58</b>, wherein m is the number of samples in a frame. The long-window spectrum X¹is generated by adding the short-window coefficients from the current and previous frames (with appropriate phase shift) at an adder <b>60</b>, giving:

<i>X</i>¹(2<i>πk/L</i>)=<i>X</i>^s(2<i>πk/L</i>)+<i>Y</i>^s(2<i>πk/L</i>)<i>exp</i>(<i>j</i>2<i>πmk/L</i>)  EQ. 3

[0067] Here k is an integer taken from a set of integers such that the frequencies 2πk/L span the full range of frequencies. The method exemplified by FIG. 4 thus allows spectra to be derived for multiple, overlapping windows with little more computational effort that is required to perform a STFT operation on a single window.

[0068]FIG. 5 is a flow chart that schematically shows details of line spectrum estimation steps <b>42</b> and <b>44</b>, in accordance with a preferred embodiment of the present invention. The method of line spectrum estimation illustrated in this figure is applied to both the long- and short-window transforms X(θ) generated at step <b>40</b>. The object of steps <b>42</b> and <b>44</b> is to determine an estimate {(<b>81</b> â_i|, {circumflex over (θ)}_i)}, of the absolute line spectrum of the current frame. The sequence of peak frequencies {{circumflex over (θ)}_i} is derived from the locations of the local maxima of X(θ), and ∥â_i|=|X({circumflex over (θ)}_i)|. The estimate is based on the assumption that the width of the main lobe of the transform of the windowing function (block <b>50</b>) in the frequency domain is small compared to the pitch frequency. Therefore, the interaction between adjacent windows in the spectrum is small.

[0069] Estimation of the line spectrum begins with finding approximate frequencies of the peaks in the interpolated spectrum (per equation (2)), at a peak finding step <b>70</b>. Typically, these frequencies are computed with integer precision. At an interpolation step <b>72</b>, the peak frequencies and amplitudes are calculated to floating point precision, preferably using quadratic interpolation based on the spectrum amplitudes at the three nearest neighboring integer multiples of 2π/L.

[0070] At a distortion evaluation step <b>74</b>, the array of peaks found in the preceding steps is processed to assess whether distortion was present in the input speech signal and, if so, to attempt to correct the distortion. Preferably, the analyzed frequency range is divided into three equal regions, and for each region, the maximum of all amplitudes in the region is computed. The regions completely cover the frequency range. If the maximum value in either the middle- or the high-frequency range is too high compared to that in the low-frequency range, the values of the peaks in the middle and/or high range are attenuated, at an attenuation step <b>76</b>. It has been found heuristically that attenuation should be applied if the maximum value for the middle-frequency range is more than 65% of that in the low-frequency range, or if the maximum in the high-frequency range is more than 45% of that in the low-frequency range. Attenuating the peaks in this manner “restores” the spectrum to a more likely shape. Generally speaking, if the speech signal was not distorted initially, step <b>74</b> will not change its spectrum.

[0071] The number of peaks found at step <b>72</b> is counted, at a peak counting step <b>78</b>.

[0072] At a significant-peak evaluation step <b>80</b>, the number of peaks is compared to a predetermined maximum number, which is typically set to seven. If seven or fewer peaks are found, the process proceeds directly to step <b>46</b> or <b>48</b>. Otherwise, the peaks are sorted in descending order of their amplitude values, at a sorting step <b>82</b>. Once a predetermined number of the highest peaks have been found (typically equal to the maximum number of peaks used at step <b>80</b>), a threshold is set equal to a certain fraction of the amplitude value of the lowest peak in this group of the highest peaks, at a threshold setting step <b>84</b>. Peaks below this threshold are discarded, at a spurious peak discarding step <b>86</b>. Alternatively, if at some stage of sorting step <b>82</b>, the sum of the sorted peak values exceeds a predetermined fraction, typically 95%, of the total sum of the values of all of the peaks that were found, the sorting process stops. All of the remaining, smaller peaks are then discarded at step <b>86</b>. The purpose of this step is to eliminate small, spurious peaks that may subsequently interfere with pitch determination or with the voiced/unvoiced decision at steps <b>34</b> and <b>36</b> (FIG. 2).

[0073]FIG. 6A is a flow chart that schematically shows details of candidate pitch frequency finding steps <b>46</b> and <b>48</b> (FIG. 3), in accordance with a preferred embodiment of the present invention. These steps are applied respectively to the short- and long-window line spectra {(∥â_i|, {circumflex over (θ)}_i)} output by steps <b>42</b> and <b>44</b>, as shown and described above. In step <b>46</b>, pitch candidates whose frequencies are higher than a certain threshold are generated, and their utility functions are computed using the procedure outlined below based on the line spectrum generated in the short analysis interval. In step <b>48</b>, the line spectrum generated in the long analysis interval also generates a pitch candidate list and computes utility functions only for pitch candidates whose frequency is lower than that threshold. For both the long and short windows, the line spectra are normalized, at a normalization step <b>90</b>, to yield lines with normalized amplitudes b_iand frequencies f_igiven by: <maths id="MATH-US-00004" num="4"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>b</mi><mi>i</mi></msub><mo>=</mo><mfrac><mrow><mo></mo><msub><mover><mi>a</mi><mo>^</mo></mover><mi>i</mi></msub><mo></mo></mrow><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover><mo></mo><mrow><mo></mo><msub><mover><mi>a</mi><mo>^</mo></mover><mi>k</mi></msub><mo></mo></mrow></mrow></mfrac></mrow></mtd><mtd><mrow><mi>EQ</mi><mo>.</mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>4</mn></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>f</mi><mi>i</mi></msub><mo>=</mo><mfrac><msub><mover><mi>θ</mi><mo>^</mo></mover><mi>i</mi></msub><mrow><mn>2</mn><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>π</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><msub><mi>T</mi><mi>S</mi></msub></mrow></mfrac></mrow></mtd><mtd><mrow><mi>EQ</mi><mo>.</mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>5</mn></mrow></mtd></mtr></mtable></math><img file="US20040167775A1-20040826-M00004.TIF" id="EMI-M00004" he="57.12525" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00004" attachment-type="nb" file="US20040167775A1-20040826-M00004.NB" /></attachments></maths>

[0074] In both equations 4 and 5, i runs from 1 to K, where K is the number of spectral lines (peaks) and T_sis the sampling interval. In other words, 1/T_sis the sampling frequency of the original speech signal, and f_iis thus the frequency in samples per second of the spectral lines.

[0075] A predefined number of spectral lines with highest amplitudes values are selected at a select dominant lines step <b>92</b>. Then at step <b>94</b> a preliminary utility function is computed which is indicative, for each candidate pitch frequency in a given pitch frequency range, of a compatibility of the dominant spectral lines selected at step <b>92</b> with the candidate pitch frequency. A utility function definition in accordance with a preferred embodiment of the present invention is described in greater detail hereinbelow with reference to FIG. 7 and FIG. 8, while a preferred method of calculating the preliminary utility function is described in greater detail hereinbelow with reference to FIG. 6B. A predefined number of pitch frequency candidates are then selected at a select preliminary candidates step <b>96</b> using the preliminary utility function. A preferred method of selecting preliminary candidates is described in greater detail hereinbelow with reference to FIG. 6C. A utility score is then calculated for each preliminary candidate at a compute final utility scores for preliminary candidates step <b>98</b>. A preferred method of computing final utility scores is described in greater detail hereinbelow with reference to FIG. 6D.

[0076] In accordance with a preferred embodiment of the present invention the utility function is defined through an influence function, such as is shown in FIG. 7, which is a plot showing one cycle of an influence function <b>120</b> identified as c(f). The influence function preferably has the following characteristics:

[0077] 1. c(f+1)=c(f), i.e., the function is periodic, with period 1.

[0078] 2. 0≦c(f)≦1

[0079] 3. c(0)=1.

[0080] 4. c(f)=c(−f).

[0081] 5. c(f)=0 for r≦|f|≦1/2, wherein r is a parameter &lt;1/2.

[0082] 6. c(f) piecewise linear and non-increasing in [0,r].

[0083] In the preferred embodiment shown in FIG. 7, the influence function is trapezoidal, and its one period cycle has the form: <maths id="MATH-US-00005" num="5"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>c</mi><mo></mo><mrow><mo>(</mo><mi>f</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mo>{</mo><mtable><mtr><mtd><mn>1</mn></mtd><mtd><mrow><mi>f</mi><mo>∈</mo><mrow><mo>[</mo><mrow><mrow><mo>-</mo><msub><mi>r</mi><mn>1</mn></msub></mrow><mo>,</mo><msub><mi>r</mi><mn>1</mn></msub></mrow><mo>]</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mn>1</mn><mo>-</mo><mrow><mrow><mo>(</mo><mrow><mrow><mo></mo><mi>f</mi><mo></mo></mrow><mo>-</mo><msub><mi>r</mi><mn>1</mn></msub></mrow><mo>)</mo></mrow><mo>/</mo><mrow><mo>(</mo><mrow><mi>r</mi><mo>-</mo><msub><mi>r</mi><mn>1</mn></msub></mrow><mo>)</mo></mrow></mrow></mrow></mtd><mtd><mrow><mrow><mo></mo><mi>f</mi><mo></mo></mrow><mo>∈</mo><mrow><mo>[</mo><mrow><msub><mi>r</mi><mn>1</mn></msub><mo>,</mo><mi>r</mi></mrow><mo>]</mo></mrow></mrow></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mrow><mi>r</mi><mo>&lt;</mo><mrow><mo></mo><mi>f</mi><mo></mo></mrow><mo>&lt;</mo><mn>0.5</mn></mrow></mtd></mtr></mtable></mrow></mrow></mtd><mtd><mrow><mi>EQ</mi><mo>.</mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>6</mn></mrow></mtd></mtr></mtable></math><img file="US20040167775A1-20040826-M00005.TIF" id="EMI-M00005" he="31.9221" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00005" attachment-type="nb" file="US20040167775A1-20040826-M00005.NB" /></attachments></maths>

[0084] Alternatively, another periodic function may be used, preferably a piecewise linear function whose value is zero above some predetermined distance from the origin.

[0085]FIG. 8 is a plot showing a component <b>130</b> of a utility function U(f_p), which is generated for candidate pitch frequencies f_pusing the influence function c(f), in accordance with a preferred embodiment of the present invention. The utility function U(f_p) for any given pitch frequency is generated based on the line spectrum {(b_i, f_i)}, as given by: <maths id="MATH-US-00006" num="6"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>U</mi><mo></mo><mrow><mo>(</mo><msub><mi>f</mi><mi>p</mi></msub><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover><mo></mo><mrow><msub><mi>b</mi><mi>i</mi></msub><mo></mo><mrow><mi>c</mi><mo></mo><mrow><mo>(</mo><mrow><msub><mi>f</mi><mn>1</mn></msub><mo>/</mo><msub><mi>f</mi><mi>p</mi></msub></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mi>EQ</mi><mo>.</mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>7</mn></mrow></mtd></mtr></mtable></math><img file="US20040167775A1-20040826-M00006.TIF" id="EMI-M00006" he="24.97635" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00006" attachment-type="nb" file="US20040167775A1-20040826-M00006.NB" /></attachments></maths>

[0086] A component of this function, U_i(f_p), is then defined for a single spectral line (b_i,f_i) as:

<i>U</i>_i(<i>f</i>_p)=<i>b</i>_i<i>c</i>(<i>f</i>_i<i>/f</i>_p)  EQ. 8

[0087]FIG. 8 shows one such component, wherein f_i=700 Hz, and the component is evaluated over pitch frequencies in the range from 50 to 400 Hz. The component comprises a plurality of lobes <b>132</b>, <b>134</b>, <b>136</b>, <b>138</b>, . . . , each defining a region of the frequency range in which a candidate pitch frequency could occur and give rise to the spectral line at f_i.

[0088] Because the values b_iare normalized, and c(f)≦1, the utility function for any given candidate pitch frequency will be between zero and one. Since c(f_i/f_p) is by definition periodic in f_iwith period f_p, a high value of the utility function for a given pitch frequency f_pindicates that most of the frequencies in the sequence {f_i} are close to some multiple of the pitch frequency. Thus, the pitch frequency for the current frame could be found in a straightforward (but inefficient) way by calculating the utility function for all possible pitch frequencies in an appropriate frequency range with a specified resolution, and choosing a candidate pitch frequency with a high utility value.

[0089] Returning now to FIG. 6A, a number M of spectral lines {(b_ij, f_ij)}, j=1, 2, . . . , M associated with M highest amplitudes is selected out of K lines at a dominant lines selection step <b>92</b>. M is set to seven in a preferred embodiment of the present invention. A preliminary utility function computed at step <b>94</b> mentioned above is given by: <maths id="MATH-US-00007" num="7"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>UD</mi><mo></mo><mrow><mo>(</mo><msub><mi>f</mi><mi>p</mi></msub><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>M</mi></munderover><mo></mo><mrow><msub><mi>b</mi><mi>ij</mi></msub><mo></mo><mrow><mi>c</mi><mo></mo><mrow><mo>(</mo><mrow><msub><mi>f</mi><mi>ij</mi></msub><mo>/</mo><msub><mi>f</mi><mi>p</mi></msub></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mi>EQ</mi><mo>.</mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>9</mn></mrow></mtd></mtr></mtable></math><img file="US20040167775A1-20040826-M00007.TIF" id="EMI-M00007" he="25.9119" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00007" attachment-type="nb" file="US20040167775A1-20040826-M00007.NB" /></attachments></maths>

[0090] Only the M dominant lines selected at step <b>92</b> are used. The preliminary utility function is computed over the full pitch frequency search range by using a fast method described hereinbelow with reference to FIG. 6B. Since the influence function c(f) is piecewise linear, the value of U_ij(f_p) at any point is defined by its value at break points of the function (i.e., points of discontinuity in the first derivative), such as points <b>140</b> and <b>142</b> shown in FIG. 8. Although U_ij(f_p) is itself not piecewise linear, it can be approximated as a linear function in all regions. The fast method of UD(f_p) computing uses the breakpoint values of the components U_ij(f_p) to build up the full function UD(f_p). Each component U_ij(f_p) adds its own breakpoints to the full function, while values of the utility function between the breakpoints may be found by performing linear interpolation.

[0091] The process of building up UD(f_p) uses a series of partial utility functions PU_j, generated by adding in the components U_ij(f_p) for each of the dominant spectral lines (b_ij, f_ij) in succession: <maths id="MATH-US-00008" num="8"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>PU</mi><mi>j</mi></msub><mo></mo><mrow><mo>(</mo><msub><mi>f</mi><mi>p</mi></msub><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>j</mi></munderover><mo></mo><mrow><msub><mi>U</mi><mi>ik</mi></msub><mo></mo><mrow><mo>(</mo><msub><mi>f</mi><mi>p</mi></msub><mo>)</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mi>EQ</mi><mo>.</mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>10</mn></mrow></mtd></mtr></mtable></math><img file="US20040167775A1-20040826-M00008.TIF" id="EMI-M00008" he="25.9119" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00008" attachment-type="nb" file="US20040167775A1-20040826-M00008.NB" /></attachments></maths>

[0092] Continuing with FIG. 6B, the influence function c(f) is applied iteratively to each of the dominant lines (b_ij, f_ij) in the normalized line spectrum in order to generate the succession of partial utility functions PU_j. The process begins with the first component U_il(f_p). This component corresponds to the dominant spectral line (b_i1,f_i1). The value of U_i1(fp) is calculated at all of its break points over the range of search for f_pat a utility function component generation step <b>102</b>. The partial utility function PU₁at this stage is simply equal to U_i1. In subsequent iterations at this step, the new component U_ij(f_p) is determined both at its own break points and at all break points of the partial utility function PU_j−1(f_p). The values of U_ij(f_p) at the break points of PU_j−1(f_p) are preferably calculated by interpolation. The values of PU_j−1(f_p) are likewise calculated at the break points of U_ij(f_p). If U_ij(f_p) contains break points that are very close to existing break points in PU_j−1, these new break points are preferably discarded as superfluous at a discard step <b>103</b>. Most preferably, break points whose frequency differs from that of an existing break point by no more than 0.0006*f_p²are discarded in this manner. U_ijis then added to PU_j−1at all of the remaining break points, thus generating PU_j, at an addition step <b>104</b>.

[0093] At a termination step <b>105</b>, when the component U_iMof the last dominant spectral line (b_iM,f_iM) has been evaluated, the process is complete, and the resultant utility function UD(f_p) is passed to preliminary pitch candidates selection step <b>96</b>. The function has the form of a set of frequency break points and the values of the preliminary utility function at the break points. Otherwise, if other dominant spectral lines remain to be evaluated, the next dominant line is taken at step <b>106</b>, and the iterative process continues from step <b>102</b> until all dominant spectral lines have been evaluated.

[0094] It may be observed that the method of FIG. 6B searches all possible pitch frequencies in the search range, but it does so with optimized efficiency, since few spectral lines are involved, and the contribution of each line to the utility function is calculated only at specific break points, and not over the entire search range of pitch frequencies.

[0095]FIG. 6C is a flow chart that schematically illustrates details of preliminary pitch candidates selection step <b>96</b> (FIG. 6A) in accordance with a preferred embodiment of the present invention. A predefined number m of preliminary pitch candidates are selected. In a preferred embodiment of the present invention m is set to four. The selection of the preliminary pitch frequency candidates is based on the preliminary utility function output from step <b>94</b>, including all break points that were found. The break points of the preliminary utility function are evaluated, and some are chosen as the preliminary pitch candidates.

[0096] At step <b>110</b>, those break points that represent the local maxima of the preliminary utility function are found. Then m (typically four) highest local maxima are selected as the initial set {(f₁,UD(f₁)),(f₂,UD(f₂)), . . . ,(f_m,UD(f_m))} of preliminary candidates. Let (f_k,UD(f_k)) be the lowest member of the set, i.e., UD(f_k)&lt;UD(f_i) if i≠k.

[0097] It is generally desirable to choose a pitch for the current frame that is near the pitch of the preceding frame, provided the pitch was stable in the preceding frame. Therefore, at a previous frame assessment step <b>112</b>, it is determined whether the previous frame pitch was stable. Preferably, the pitch is considered to have been stable if over the six previous frames certain continuity criteria are satisfied. It may be required, for example, that the pitch change between consecutive frames was less than a predetermined value, such as 22%, and a predetermined value of the utility function was maintained in all of the frames. If the pitch has been stable, an alternative pitch frequency candidate f_p^altassociated with the local maximum that is closest to the previous pitch frequency is selected at a nearest maximum selection step <b>113</b>. Closeness between the alternative candidate frequency f_p^altand the previous pitch frequency f_previs then tested by evaluation of the condition:

1<i>/R≦f</i>_p^alt<i>/f</i>_prev<i>≦R</i>  EQ. 11

[0098] where R is set to a predetermined value, such as 1.22. If the condition is satisfied, the preliminary utility function at the alternative candidate frequency UD(f_p^alt) is evaluated against the preliminary utility function of the lowest set member UD(f_k) at a comparison step <b>114</b>. If the values of the utility function at these two frequencies differ by no more than a predetermined threshold amount T₁, such as 0.06, then the lowest set member (f_k,UD(f_k)) is replaced by (f_p^alt,UD(f_p^alt)) at step <b>114</b>. Otherwise, the initial set of preliminary candidates is kept unchanged. The initial set of preliminary candidates is likewise chosen if the pitch of the previous frame was found to be unstable at step <b>112</b>, and if no local maximum was found in the vicinity of the previous pitch at step <b>113</b>.

[0099]FIG. 6D is a flow chart that schematically illustrates details of computation step <b>98</b> (FIG. 6A) of the final utility scores associated with a preliminary pitch frequency candidate f. The sequence of steps shown on FIG. 6D is preferably applied to each preliminary candidate pitch frequency found at step <b>96</b>. The final utility score is performed using EQ. 7 using all the spectral lines. At the initialization step <b>116</b> the score is set to zero and the first spectral line (b₁,f₁) is selected. A weighted influence function is computed using EQ. 6 at step <b>117</b>. This includes computation of ratio f₁/f, taking the fractional part of the ratio in order to warp it to the main period cycle (−1,+1) of the influence function, applying EQ. 6 and multiplying by b₁. The obtained value is added to the score. The steps of FIG. 6D are preferably repeated for all the spectral lines.

[0100]FIG. 9A and FIG. 9B are flow charts that illustrate details of the best pitch frequency selection step <b>34</b> (FIG. 2). The best pitch candidate is to be selected from among preliminary pitch candidates using their utility scores computed at step <b>98</b>. Typically, preference is given to high pitch frequencies, in order to avoid mistaking integer dividends of the pitch frequency (corresponding to integer multiples of the pitch period) for the true pitch. Therefore, at a frequency sorting step <b>152</b>, the preliminary candidates {f_pⁱ}_i=1^mare sorted by frequency such that:

f_p¹&gt;f₂²&gt; . . . &gt;f_p^m  EQ. 12

[0101] The estimated pitch {circumflex over (F)}₀is preferably set initially to be equal to the highest-frequency candidate f_p¹at an initialization step <b>154</b>. Each of the remaining candidates is evaluated against the current value of the estimated pitch, in descending frequency order.

[0102] The process of evaluation begins at a next frequency step <b>156</b>, with candidate pitch f_p². At an evaluation step <b>158</b>, the value of the utility function, U(f_p²), is compared to U({circumflex over (F)}₀). If the utility function at f_p²is greater than the utility function at {circumflex over (F)}₀by at least a threshold difference T₂, or if f_p²is near {circumflex over (F)}₀and has a greater utility function, then f_p²is considered to be a superior pitch frequency estimate to the current {circumflex over (F)}₀. Preferably, T₂=0.06, and f_p²is considered to be near {circumflex over (F)}₀if 1.17f_p²&gt;{circumflex over (F)}₀. In this case, {circumflex over (F)}₀is set to the new candidate value, f_p², at a candidate setting step <b>160</b>. Steps <b>156</b> through <b>160</b> are repeated in turn for all of the preliminary candidates f_pⁱ, until the last frequency f_p^mis reached, at a last frequency step <b>162</b>.

[0103] It is generally desirable to choose a pitch for the current frame that is near the pitch of the preceding frame, provided the pitch was stable in the preceding frame. Therefore, in FIG. 9B, a process similar to the one used for preliminary candidates selection and shown on FIG. 6D may also be applied to the best pitch candidate selection. At a previous frame assessment step <b>170</b> it is determined whether the previous frame pitch has been stable as described above. If the pitch has been stable, the alternative pitch frequency f_p^altin the set {f_pⁱ} that is closest to the previous pitch frequency is selected at step <b>172</b>. The condition of EQ. 11 is then evaluated in order to determine if the alternative candidate is sufficiently close to the previous pitch frequency. If the condition is satisfied the utility function at this alternative frequency U(f_p^alt) is evaluated against the utility function of the current estimated pitch frequency U({circumflex over (F)}₀) at a comparison step <b>174</b>. If the values of the utility function at these two frequencies differ by no more than a predetermined threshold amount T₂, then the alternative frequency f_p^altis chosen to be the estimated pitch frequency {circumflex over (F)}₀for the current frame at step <b>176</b>. Typically T₂is set to be 0.06. Otherwise, if the values of the utility function differ by more than T₂, the current estimated pitch frequency {circumflex over (F)}₀from step <b>162</b> remains the chosen pitch frequency for the current frame, at a candidate frequency setting step <b>178</b>. This estimated value is likewise chosen if the pitch of the previous frame was found to be unstable at step <b>170</b>, and if no preliminary candidate was found in the vicinity of the previous pitch at the step <b>172</b>.

[0104]FIG. 10 is a flow chart that schematically shows details of voicing decision step <b>36</b>, in accordance with a preferred embodiment of the present invention. The decision is based on comparing the utility function at the estimated pitch, U({circumflex over (F)}₀), to the above-mentioned threshold T_uv, at a threshold comparison step <b>180</b>. Typically, T_uv=0.75. If the utility function is above the threshold, the current frame is classified as voiced, at a voiced setting step <b>188</b>.

[0105] During transitions in a speech stream, however, the periodic structure of the speech signal may change, leading at times to a low value of the utility function even when the current frame should be considered voiced. Therefore, when the utility function for the current frame is below the threshold T_uv, the utility function of the previous frame is checked, at a previous frame checking step <b>182</b>. If the estimated pitch of the previous frame had a high utility value, typically at least 0.84, and the pitch of the current frame is found, at a pitch checking step <b>184</b>, to be close to the pitch of the previous frame, typically differing by no more than 18%, then the current frame is classified as voiced, at step <b>188</b>, despite its low utility value. Otherwise, the current frame is classified as unvoiced, at an unvoiced setting step <b>186</b>.

[0106] It is appreciated that one or more of the steps of any of the methods described herein may be omitted or carried out in a different order than that shown, without departing from the true spirit and scope of the invention.

[0107] While the methods and apparatus disclosed herein may or may not have been described with reference to specific computer hardware or software, it is appreciated that the methods and apparatus described herein may be readily implemented in computer hardware or software using conventional techniques.

[0108] It will be appreciated that the preferred embodiments described above are cited by way of example, and that the present invention is not limited to what has been particularly shown and described hereinabove. Rather, the true spirit and scope of the present invention includes both combinations and subcombinations of the various variations and modifications thereof which upon reading the foregoing description and