# Patent

## Title
Fast waveform synchronization for concentration and time-scale modification of speech

## Abstract

A synthesis method for concatenative speech synthesis is provided for efficiently concatenating waveform segments in the time-domain. A digital waveform provider produces an input sequence of digital waveform segments. A waveform concatenator concatenates the input segments by using waveform blending within a concatenation zone to synchronize, weight, and overlap-add selected portions of the input segments to produce a single digital waveform. The synchronizing includes determining a minimum weighted energy anchor in the selected portion of each input segment and aligning synchronization peaks in a local vicinity of each anchor.

## Background
Claims benefit of Ser. No. 60/233,031 Sep. 15, 2000.


FIELD OF THE INVENTION
The present invention relates to speech synthesis, and more specifically, changing the speech rate of sampled speech signals and concatenating speech segments by efficiently joining them in the time-domain.
BACKGROUND OF THE INVENTION
Speech segment concatenation is often used as part of speech generation and modification algorithms. For example, many Text-To-Speech (TTS) applications concatenate pre-stored speech segments in order to produce synthesized speech. Also, some Time Scale Modification (TSM) systems fragment input speech into small segments and rejoin the segments after repositioning. Junctions between speech segments are a possible source of degradation in speech quality. Thus, signal discontinuities at each junction should be minimized.
Speech segments can be concatenated either in the time-, frequency- or time-frequency-domain. The present invention is about time-domain concatenation (TDC) of digital speech waveforms. High quality joining of digital speech waveforms is important in a variety of acoustic processing applications, including concatenative text-to-speech (TTS) systems such as the one described in U.S. patent application Ser. No. 09/438,603 by G. Coorman et al.; broadcast message generation as described, for example, in L. F. Lamel, J. L. Gauvain, B. Prouts, C. Bouhier & R. Boesch, “Generation and Synthesis of Broadcast Messages,” Proc. ESCA-NATO Workshop on Applications of Speech Technology, Lautrach, Germany, September 1993; implementing carrier-slot applications, as described, for example, in U.S. Pat. No. 6,052,664 by S. Leys, B. Van Coile and S. Willems; and Time-Scale Modifications (TSM) as described, for example, in U.S. patent application Ser. No. 09/776,018, G. Coorman, P. Rutten, J. De Moortel and B. Van Coile, “Time Scale Modification of Digitally Sampled Waveforms in the Time Domain,” filed Feb. 2, 2001; all of which are hereby incorporated herein by reference.
TDC avoids computationally expensive transformations to and from other domains, and has the further advantage of preserving intrinsic segmental information in the waveform. As a consequence, for longer speech segments, the natural prosodic information (including the micro-prosody-one of the key factors for highly natural sounding speech) is transferred to the synthesized speech. One major concern of TDC is to avoid audible waveform irregularities such as discontinuities and transients that may occur in the neighborhood of the join. These are commonly referred as “concatenation artifacts”.
To avoid concatenation artifacts, two speech segments can be joined together by fading-out the trailing edge of the left segment and fading-in the leading edge of the right segment before overlapping and adding them. In other words, smooth concatenation is done by means of weighted overlap-and-add, a technique that is well known in the art of digital speech processing. Such a method has been disclosed in U.S. Pat. No. 5,490,234 by Narayan, incorporated herein by reference.
Thus, rapid and efficient synchronization of waveforms helps achieve real time high quality TDC. The length of the speech segments involved depends on the application. Small speech segments (e.g. speech frames) are typically used in time-scale modification applications while longer segments such as diphones are used in text-to-speech applications and even longer segments can be used in domain specific applications such as carrier slot applications.
Some known waveform synchronization techniques address waveform similarity as described in W. Verhelst & M. Roelands, “An Overlap-Add Technique Based on Waveform Similarity (WSOLA) for High Quality Time-Scale Modification of Speech,” ICASSP-93. IEEE International Conference on Acoustics, Speech, and Signal Processing, pages 554–557, Vol. 2, 1993; incorporated herein by reference. In the following, waveform synchronization methods used in TDC that makes use of the waveform shape will be described. This type of synchronization minimizes waveform discontinuities in voiced speech that could emerge when joining two speech waveform segments.
A common method of synthesizing speech in text-to-speech (TTS) systems is by combining digital speech waveform segments extracted from recorded speech that are stored in a database. These segments are often referred in speech processing literature as “speech units”. A speech unit used in a text-to-speech synthesizer is a set consisting of a sequence of samples or parameters that can be converted to waveform samples taken from a continuous chunk of sampled speech and some accompanying feature vectors (containing information such as prominence level, phonetic context, pitch . . . ) to guide the speech unit selection process, for example. Some common and well described representations of speech units used in concatenative TTS systems are frames as described in R. Hoory & D. Chazan, “Speech synthesis for a specific speaker based on labeled speech database”, 12thInternational Conference On Pattern Recognition 1994, Vol. 3, pp. 146–148, phones as described in A. W. Black, N. Campbell, “Optimizing selection of units from speech databases for concatenative synthesis,” Proc. Eurospeech '95, Madrid, pp. 581–584, 1995, diphones as described in P. Rutten, G. Coorman, J. Fackrell & B. Van Coile, “Issues in Corpus-based Speech Synthesis”, Proc. IEE symposium on state-of-the-art in Speech Synthesis, Savoy Place, London, April 2000, demi-phones as described in M. Balestri, A. Pacchiotti, S. Quazza, P. L. Salza, S. Sandri, “Choose the best to modify the least: a new generation concatenative synthesis system,” Proc. Eurospeech '99, Budapest, pp. 2291–2294, September 1999 and longer segments such as syllables, words and phrases as described in E. Klabbers, “High-quality speech output generation through advanced phrase concatenation”, Proc. of the COST Workshop on Speech Technology in the Public Telephone Network: Where are we today?, Rhodes, Greece, pages 85–88, 1997, all of which are incorporated herein by reference.
A well known speech synthesis method that implicitly uses waveform concatenation is described in a paper by E. Moulines and F. Charpentier “Pitch-Synchronous Waveform Processing Techniques for Text-to-Speech Synthesis Using Diphones”, Speech Communication, Vol. 9, No. 5/6, December 1990, pages 453–467, incorporated herein by reference. That paper describes a technique known as TD-PSOLA (Time-Domain Pitch-Synchronous Over-Lap and Add) that is used for prosody manipulation of the speech waveform and concatenation of speech waveform segments. A TD-PSOLA synthesizer concatenates windowed speech segments centered on the instant of glottal closure (GCI) that have a typical duration of two pitch periods. Several techniques have been used to calculate the GCI. Amongst others:

    
    
        B. Yegnanarayana and R. N. J. Veldhuis, “Extraction Of Vocal-Tract System Characteristics From Speech Signals”, IEEE Transactions on Speech and Audio Processing, Vol. 6, pp. 313–327, 1998;
        C. Ma, Y. Kamp & L. Willems, “A Frobenius Norm Approach To Glottal Closure Detection From The Speech Signal”, IEEE Transactions on Speech and Audio Processing, 1994;
        S. Kadambe and G. F. Boudreaux-Bartels, “Application Of The Wavelet Transform For Pitch Detection Of Speech Signals”, IEEE Transactions on Information Theory, vol. 38, no 2, pp. 917–924, 1992;
        R. Di Francesco & E. Moulines, “Detection Of The Glottal Closure By Jumps In The Statistical Properties Of The Signal”, Proc. of Eurospeech '89, Paris, vol. 2, pp. 39–41, 1989; all incorporated herein by reference.
    
    


In PSOLA synthesis, diphone concatenation is performed by means of overlap-and-add (i.e. waveform blending). The synchronization is based on a single feature, namely the instant of glottal closure (pitch markers, GCI). The PSOLA method is fast and lends itself to off-line calculation of the pitch markers leading to very fast synchronization. A disadvantage of this technique is that phase differences between segment boundaries may cause waveform discontinuities and thus may lead to audible clicks. A technique which aims to avoid such problems is the MBROLA synthesis method that is described in T. Dutoit & H. Leich, “MBR-PSOLA: Text-to-Speech Synthesis Based on an MBE Re-Synthesis of the Segments Database”, Speech Communication, Vol. 13, pages 435–440, incorporated herein by reference. The MBROLA technique pre-processes the segments of the inventory by equalization of the pitch period over the complete segment database and by resetting the low frequency phase components to a pre-defined value. This technique facilitates spectral interpolation. MBROLA has the same computational efficiency as PSOLA and its concatenation is smoother. However MBROLA makes the synthesized speech more metallic sounding because of the pitch-synchronous phase resets.
In the field of corpus-based synthesis another efficient segment concatenation method has been proposed recently in Y. Stylianou, “Synchronization of Speech Frames Based on Phase Data with Application to Concatenative Speech Synthesis,” Proceedings of 6th European Conference on Speech Communication and Technology, Sep. 5–9, 1999, Budapest, Hungary, Vol. 5, pp. 2343–2346, incorporated herein by reference. Stylianou's method is based on the calculation of the center of gravity. This method is somewhat similar to the epoch estimation method used for TD-PSOLA synthesis but is more robust since it does not rely on an accurate pitch estimate.
Another efficient waveform synchronization technique described in S. Yim & B. I. Pawate, “Computationally Efficient Algorithm for Time Scale Modification (GLS-TSM)”, IEEE International Conference on Acoustics, Speech, and Signal Processing Conference Proceedings, pp. 1009–1012 Vol. 2, 1996, incorporated herein by reference, (see also U.S. Pat. No. 5,749,064) is based on a cascade of a global synchronization with a local synchronization based on a vector of signal features.
In the method described in B. Lawlor & A. D. Fagan, “A Novel High Quality Efficient Algorithm for Time-Scale Modification of Speech,” Proceedings of Eurospeech conference, Budapest, Vol. 6, pp. 2785–2788, 1999, incorporated herein by reference, the largest peaks or troughs are used as a synchronization criterion.
SUMMARY OF THE INVENTION
The present invention provides an apparatus for concatenating a first quasi-periodic digital waveform segment with a second quasi-periodic digital waveform segment, such that the trailing part of the first waveform segment and leading part of the second waveform segment are concatenated smoothly. The concatenation is done by means of overlap-and-add, a technique well known in the art of speech processing. The waveform synchronizer/concatenator determines an optimum blend point for the first and second digital waveform segments in order to minimize audible artifacts near the join. The waveform regions centered around the optimal blend points are overlapped in time and added to generate a digital waveform sequence representing a concatenation of the first and second digital waveform segment. The technique is applicable to concatenate any two quasi-periodic waveforms, commonly encountered in the synthesis of sound, voiced speech, music or the like.



BRIEF DESCRIPTION OF THE DRAWINGS
The present invention will be more readily understood by reference to the following detailed description taken with the accompanying drawings, in which:
FIG. 1 gives a general functional view of the waveform synchronization mechanism embedded in a waveform concatenator.
FIG. 2 gives a general functional view of the waveform synchronizer and blender.
FIG. 3 shows the typical shapes of the fade-in and fade-out functions that are used in the waveform blending process.
FIG. 4 shows how the blending anchor is calculated based on some features of the signal in the neighborhood of the join.



DETAILED DESCRIPTION OF SPECIFIC EMBODIMENTS
Before leaping to the specific details of our invention, some underlying signal processing aspects will be discussed, starting with the theory behind detection of the concatenation points and the distortion caused by the concatenation of two speech segments x1(n) and X2(n). The signal after concatenating is described as y(n).
In order to minimize concatenation artifacts, the concatenated signal y(n) is analyzed in the neighborhood of the join. In what follows index Lcorresponds with the time-index of the join, and it is also assumed that the distortion to the left and to the right of the join have the same importance (i.e. same weight). Inside the concatenation interval, y(n) is a mixture of x1(n) and x2(n). The signal y(n) toward the left side of the concatenation zone corresponds to part of the segment extracted from x1(n), and toward the right side of the concatenation zone corresponds to part of the segment extracted from the signal x2(n). Their respective concatenation points are described as E1 and E2. In order to minimize the distortion caused by concatenation a concatenation point is selected, based on a synchronization measure, from a set of potential concatenation points that lay in a (small) time interval called the optimization zone. The optimization zone is typically located at the edges of the speech segments (where the concatenation should take place).
At a distance D from the left side of the join after concatenation, a short-time (ST) Fourier spectrum Y(ω,L−D) of y(n) is expected that closely resembles that of X1(ω,E1−D), the ST Fourier spectrum of x1(n) around E1. Similarly at the right side of the join, a ST spectrum Y(ω,L+D) is expected that closely resembles X2(ω,E2+D), the ST spectrum of x2(n) around time-index E2.
As an approximation for the perceived quality, the spectral distortion may be defined as the mean squared error between the spectra:




  ξ
  =
  
    
      
        1
        
          2
          ⁢
          π
        
      
      ⁢
      
        
          ∫
          
            -
            π
          
          π
        
        ⁢
        
          
            
              
              
                
                  Y
                  ⁢
                  
                    (
                    
                      ω
                      ,
                      
                        L
                        -
                        D
                      
                    
                    )
                  
                
                -
                
                  
                    X
                    1
                  
                  ⁢
                  
                    (
                    
                      ω
                      ,
                      
                        
                          E
                          1
                        
                        -
                        D
                      
                    
                    )
                  
                
              
              
            
            2
          
          ⁢
          
            d
            ω
          
        
      
    
    +
    
      
        1
        
          2
          ⁢
          π
        
      
      ⁢
      
        
          ∫
          
            -
            π
          
          π
        
        ⁢
        
          
            
              
              
                
                  Y
                  ⁢
                  
                    (
                    
                      ω
                      ,
                      
                        L
                        +
                        D
                      
                    
                    )
                  
                
                -
                
                  
                    X
                    2
                  
                  ⁢
                  
                    (
                    
                      ω
                      ,
                      
                        
                          E
                          2
                        
                        +
                        D
                      
                    
                    )
                  
                
              
              
            
            2
          
          ⁢
          
            d
            ω
          
        
      
    
  




The well-known Parseval's relation can be used to reformulate ξ in the time-domain:




  
    
      
        ξ
        =
        
          
            
              ∑
              
                n
                =
                
                  -
                  ∞
                
              
              ∞
            
            ⁢
            
              
                (
                
                  
                    
                      y
                      ⁡
                      
                        (
                        
                          n
                          +
                          L
                        
                        )
                      
                    
                    ⁢
                    
                      w
                      ⁡
                      
                        (
                        
                          n
                          +
                          D
                        
                        )
                      
                    
                  
                  -
                  
                    
                      
                        x
                        1
                      
                      ⁡
                      
                        (
                        
                          n
                          +
                          
                            E
                            1
                          
                        
                        )
                      
                    
                    ⁢
                    
                      w
                      ⁡
                      
                        (
                        
                          n
                          +
                          D
                        
                        )
                      
                    
                  
                
                )
              
              2
            
          
          +
          
            
              ∑
              
                n
                =
                
                  -
                  ∞
                
              
              ∞
            
            ⁢
            
              
                (
                
                  
                    
                      y
                      ⁡
                      
                        (
                        
                          n
                          +
                          L
                        
                        )
                      
                    
                    ⁢
                    
                      w
                      ⁡
                      
                        (
                        
                          n
                          -
                          D
                        
                        )
                      
                    
                  
                  -
                  
                    
                      
                        x
                        2
                      
                      ⁡
                      
                        (
                        
                          n
                          +
                          
                            E
                            2
                          
                        
                        )
                      
                    
                    ⁢
                    
                      w
                      ⁡
                      
                        (
                        
                          n
                          -
                          D
                        
                        )
                      
                    
                  
                
                )
              
              2
            
          
        
      
    
    
      
        (
        1
        )
      
    
  




Where w(n) is the window (e.g. Blackman window) that was used to derive the short-time Fourier transform.

Concatenation artifacts are minimized (in the least mean square sense) by minimizing ξ. The minimization of the spectral distortion ξ through the condition




  
    
      ∂
      ξ
    
    
      ∂
      
        y
        ⁢
        
          (
          n
          )
        
      
    
  
  =
  0




leads to an expression for the “optimal” concatenated signal y(n) y(n) in the neighborhood of L:





  
    
      
        
          y
          ⁡
          
            (
            
              n
              +
              L
            
            )
          
        
        =
        
          
            
              
                
                  
                    
                      x
                      1
                    
                    ⁡
                    
                      (
                      
                        n
                        +
                        
                          E
                          1
                        
                      
                      )
                    
                  
                  ⁢
                  
                    
                      w
                      2
                    
                    ⁡
                    
                      (
                      
                        n
                        +
                        D
                      
                      )
                    
                  
                
                +
                
                  
                    
                      x
                      2
                    
                    ⁡
                    
                      (
                      
                        n
                        +
                        
                          E
                          2
                        
                      
                      )
                    
                  
                  ⁢
                  
                    
                      w
                      2
                    
                    ⁡
                    
                      (
                      
                        n
                        -
                        D
                      
                      )
                    
                  
                
              
              
                
                  
                    w
                    2
                  
                  ⁡
                  
                    (
                    
                      n
                      +
                      D
                    
                    )
                  
                
                +
                
                  
                    w
                    2
                  
                  ⁡
                  
                    (
                    
                      n
                      -
                      D
                    
                    )
                  
                
              
            
            ⁢
            
              
            
            ⁢
            n
          
          ⁢
          
            
          
          ∈
          
            
          
          ⁢
          
            [
            
              
                -
                D
              
              ,
              D
            
            ]
          
        
      
    
    
      
        (
        2
        )
      
    
  




The concatenation of the two segments can thus be readily expressed in the well-known weighted overlap-and-add (OLA) representation as described in D. W. Griffin & J. S. Lim. “Signal Estimation From Modified Short-Time Fourier Transform”, IEEE Trans. Acoustics, Speech and Signal Processing, Vol. ASSP-32(2), pp. 236–243, April 1984, incorporated herein by reference. The overlap and-add procedure for segment concatenation is no more than a (non-linear) short time cross-fade of speech segments. The minimization of the distortion, however, resides in the technique that finds the regions of optimal overlap by appropriately modifying E1 and E2 by a small value in such a way that E1 and E2 stay in their respective optimization intervals.
By choosing the length of the window w(n) equal to 4D+1, a class of symmetrical windows (around time-index n=0) may be defined that normalize the denominator of the above equation:

w2(n+D)+w2(n−D)=1 for nε[−D,D]  (3)

To ensure signal continuity at the boundaries of the concatenation zone, choose w(0)=1. This means that the effective length of the window w is only 4D−1 samples long.

The expression for the concatenated signal y(n) can be further simplified by substituting (3) in (2):




  
    
      
        
          y
          ⁡
          
            (
            
              n
              +
              L
            
            )
          
        
        =
        
          {
          
            
              
                
                  
                  ⁢
                  
                    
                      
                        
                          x
                          1
                        
                        ⁡
                        
                          (
                          
                            n
                            +
                            
                              E
                              1
                            
                          
                          )
                        
                      
                      ⁢
                      
                        
                          w
                          2
                        
                        ⁡
                        
                          (
                          
                            n
                            +
                            D
                          
                          )
                        
                      
                    
                    +
                    
                      
                        
                          x
                          2
                        
                        ⁡
                        
                          (
                          
                            n
                            +
                            
                              E
                              2
                            
                          
                          )
                        
                      
                      ⁢
                      
                        (
                        
                          1
                          -
                          
                            
                              w
                              2
                            
                            ⁡
                            
                              (
                              
                                n
                                +
                                D
                              
                              )
                            
                          
                        
                        )
                      
                    
                  
                
              
              
                
                  
                  ⁢
                  
                    n
                    ⁢
                    
                      
                    
                    ∈
                    
                      
                    
                    ⁢
                    
                      [
                      
                        
                          -
                          D
                        
                        ,
                        D
                      
                      ]
                    
                  
                
              
            
            
              
                
                  
                  ⁢
                  
                    
                      x
                      1
                    
                    ⁡
                    
                      (
                      
                        n
                        +
                        
                          E
                          1
                        
                      
                      )
                    
                  
                
              
              
                
                  
                  ⁢
                  
                    n
                    <
                    
                      -
                      D
                    
                  
                
              
            
            
              
                
                  
                  ⁢
                  
                    
                      x
                      2
                    
                    ⁡
                    
                      (
                      
                        n
                        +
                        
                          E
                          2
                        
                      
                      )
                    
                  
                
              
              
                
                  
                  ⁢
                  
                    n
                    >
                    D
                  
                
              
            
          
        
      
    
    
      
        (
        4
        )
      
    
  




The above equation (4) now may be substituted in the expression for the distortion ξ (1) to eliminate y(n). In that way, the error may be expressed solely as a function of the positions of the left and right cutting points.





  
    ξ
    ⁢
    
      (
      
        
          E
          1
        
        ,
        
          E
          2
        
      
      )
    
  
  =
  
    
      ∑
      
        n
        =
        
          -
          ∞
        
      
      ∞
    
    ⁢
    
      
        
          w
          2
        
        ⁢
        
          (
          
            n
            +
            D
          
          )
        
      
      ⁢
      
        (
        
          1
          -
          
            
              w
              2
            
            ⁢
            
              (
              
                n
                +
                D
              
              )
            
          
        
        )
      
      ⁢
      
        
          (
          
            
              
                x
                1
              
              ⁢
              
                (
                
                  n
                  +
                  
                    E
                    1
                  
                
                )
              
            
            -
            
              
                x
                2
              
              ⁢
              
                (
                
                  n
                  +
                  
                    E
                    2
                  
                
                )
              
            
          
          )
        
        2
      
    
  




In other words, minimization of the concatenation artifacts can be performed by minimizing the weighted mean square error. This can be further expanded in terms of energy as follows:





  
    
      
        
          
            
              
                ξ
                ⁡
                
                  (
                  
                    
                      E
                      1
                    
                    ,
                    
                      E
                      2
                    
                  
                  )
                
              
              =
              
              ⁢
              
                
                  
                    ∑
                    
                      n
                      =
                      
                        -
                        ∞
                      
                    
                    ∞
                  
                  ⁢
                  
                    
                      
                        w
                        2
                      
                      ⁡
                      
                        (
                        
                          n
                          +
                          D
                        
                        )
                      
                    
                    ⁢
                    
                      (
                      
                        1
                        -
                        
                          
                            w
                            2
                          
                          ⁡
                          
                            (
                            
                              n
                              +
                              D
                            
                            )
                          
                        
                      
                      )
                    
                    ⁢
                    
                      
                        x
                        1
                        2
                      
                      ⁡
                      
                        (
                        
                          n
                          +
                          
                            E
                            1
                          
                        
                        )
                      
                    
                  
                
                +
              
            
          
        
        
          
            
              
              ⁢
              
                
                  
                    ∑
                    
                      n
                      =
                      
                        -
                        ∞
                      
                    
                    ∞
                  
                  ⁢
                  
                    
                      
                        w
                        2
                      
                      ⁡
                      
                        (
                        
                          n
                          +
                          D
                        
                        )
                      
                    
                    ⁢
                    
                      (
                      
                        1
                        -
                        
                          
                            w
                            2
                          
                          ⁡
                          
                            (
                            
                              n
                              +
                              D
                            
                            )
                          
                        
                      
                      )
                    
                    ⁢
                    
                      
                        x
                        2
                        2
                      
                      ⁡
                      
                        (
                        
                          n
                          +
                          
                            E
                            2
                          
                        
                        )
                      
                    
                  
                
                -
              
            
          
        
        
          
            
              
              ⁢
              
                2
                ⁢
                
                  
                    ∑
                    
                      n
                      =
                      
                        -
                        ∞
                      
                    
                    ∞
                  
                  ⁢
                  
                    
                      
                        w
                        2
                      
                      ⁡
                      
                        (
                        
                          n
                          +
                          D
                        
                        )
                      
                    
                    ⁢
                    
                      (
                      
                        1
                        -
                        
                          
                            w
                            2
                          
                          ⁡
                          
                            (
                            
                              n
                              +
                              D
                            
                            )
                          
                        
                      
                      )
                    
                    ⁢
                    
                      
                        x
                        1
                      
                      ⁡
                      
                        (
                        
                          n
                          +
                          
                            E
                            1
                          
                        
                        )
                      
                    
                    ⁢
                    
                      
                        x
                        2
                      
                      ⁡
                      
                        (
                        
                          n
                          +
                          
                            E
                            2
                          
                        
                        )
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (
        5
        )
      
    
  




Equation (5) can be further simplified if the window w(n) is chosen to be the following trigonometric window:





  
    
      
        
          w
          ⁡
          
            (
            n
            )
          
        
        =
        
          {
          
            
              
                
                  cos
                  ⁡
                  
                    (
                    
                      
                        n
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        4
                        ⁢
                        D
                      
                    
                    )
                  
                
              
              
                
                  n
                  ⁢
                  
                    
                  
                  ∈
                  
                    
                  
                  ⁢
                  
                    [
                    
                      
                        
                          -
                          2
                        
                        ⁢
                        D
                      
                      ,
                      
                        2
                        ⁢
                        D
                      
                    
                    ]
                  
                
              
            
            
              
                0
              
              
                otherwise
              
            
          
        
      
    
    
      
        (
        6
        )
      
    
  




where w(n) satisfies the normalization constraint (3) and is related to the popular Hanning window.

The error may now be simplified to the following expression:




  
    
      
        
          
            
              
                ξ
                ⁡
                
                  (
                  
                    
                      E
                      1
                    
                    ,
                    
                      E
                      2
                    
                  
                  )
                
              
              =
              
              ⁢
              
                
                  
                    1
                    4
                  
                  ⁢
                  
                    
                      ∑
                      
                        n
                        =
                        
                          -
                          D
                        
                      
                      D
                    
                    ⁢
                    
                      
                        (
                        
                          
                            
                              x
                              1
                            
                            ⁡
                            
                              (
                              
                                n
                                +
                                
                                  E
                                  1
                                
                              
                              )
                            
                          
                          ⁢
                          
                            cos
                            ⁡
                            
                              (
                              
                                
                                  n
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  2
                                  ⁢
                                  D
                                
                              
                              )
                            
                          
                        
                        )
                      
                      2
                    
                  
                
                +
              
            
          
        
        
          
            
              
              ⁢
              
                
                  
                    1
                    4
                  
                  ⁢
                  
                    
                      ∑
                      
                        n
                        =
                        
                          -
                          D
                        
                      
                      D
                    
                    ⁢
                    
                      
                        (
                        
                          
                            
                              x
                              2
                            
                            ⁡
                            
                              (
                              
                                n
                                +
                                
                                  E
                                  2
                                
                              
                              )
                            
                          
                          ⁢
                          
                            cos
                            ⁡
                            
                              (
                              
                                
                                  n
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  2
                                  ⁢
                                  D
                                
                              
                              )
                            
                          
                        
                        )
                      
                      2
                    
                  
                
                -
              
            
          
        
        
          
            
              
              ⁢
              
                
                  1
                  2
                
                ⁢
                
                  
                    ∑
                    
                      n
                      =
                      
                        -
                        D
                      
                    
                    D
                  
                  ⁢
                  
                    
                      (
                      
                        
                          
                            x
                            1
                          
                          ⁡
                          
                            (
                            
                              n
                              +
                              
                                E
                                1
                              
                            
                            )
                          
                        
                        ⁢
                        
                          cos
                          ⁡
                          
                            (
                            
                              
                                n
                                ⁢
                                
                                  
                                
                                ⁢
                                π
                              
                              
                                2
                                ⁢
                                D
                              
                            
                            )
                          
                        
                      
                      )
                    
                    ⁢
                    
                      (
                      
                        
                          
                            x
                            2
                          
                          ⁡
                          
                            (
                            
                              n
                              +
                              
                                E
                                2
                              
                            
                            )
                          
                        
                        ⁢
                        
                          cos
                          ⁡
                          
                            (
                            
                              
                                n
                                ⁢
                                
                                  
                                
                                ⁢
                                π
                              
                              
                                2
                                ⁢
                                D
                              
                            
                            )
                          
                        
                      
                      )
                    
                  
                
              
            
          
        
      
    
    
      
        (
        7
        )
      
    
  




The fade-in and fade-out functions that are used for the waveform blending resulting from the window (6) are shown in FIG. 3.
From the above equation (7), the minimization of the distortion ξ is shown to be a compromise between the minimization of the energy of the weighted segment at the left and right side of the join (i.e. first two terms) and the maximization of the cross-correlation between the left and the right weighted segment (third term).
It should be noted that the distortion minimization in the least mean square sense is interesting because it leads to an analytical representation that delivers insight into the problem solution. The distortion as it is defined here does not take into account perceptual aspects such as auditory masking and non-uniform frequency sensitivity. In the case when the two waveforms are very similar in the neighborhood of their joining points, then the minimization of the three terms in equation (7) is equivalent to the maximization of the cross-correlation only (i.e. waveform similarity condition), while if the two waveform segments are uncorrelated, the best optimization criterion that can be chosen is the energy minimization in the neighborhood of the join.
The concatenation of unvoiced speech waveform segments can be done by means of energy minimization only because the cross-correlation is very low. However, in the phoneme nucleus, most unvoiced segments are of a stationary nature that makes minimization on basis of energy useless. Unsynchronized OLA based concatenation is thus appropriate for the unvoiced case. On the other hand concatenation of voiced speech waveforms requires the minimization of the energy terms and the maximization of the cross-energy term. Voiced speech has a clear quasi-periodic structure and its wave shape may differ between the speech segments that are used for concatenation. Therefore it is important to find the right balance between the waveform similarity condition and the minimum energy condition.
The distortion represented by equation (7) is composed as a sum of three different energy terms. The first two terms are energy terms while the third term is a “cross-energy” term. It is well known that representing the energy in the logarithmic domain rather than in the linear domain better corresponds to the way humans perceive loudness. In order to weight the energy terms approximately perceptually equally, the logarithm of those terms may be taken individually.
To avoid problems with possible negative cross-correlations, it may be useful to further consider this approach. It is well known from mathematics that the sum of logarithms is the logarithm of the product, and that subtraction of logarithms corresponds to the logarithm of the quotient. In other words, additions become multiplications and subtractions become divisions in the optimization formula. The minimization of the logarithm of a function that is bounded by 1 is equivalent to the maximization of the function without the log operator. The minimization of the spectral distortion in the log-domain corresponds to the maximization of the normalized cross-correlation function:




  
    
      
        
          ρ
          ⁡
          
            (
            
              
                E
                1
              
              ,
              
                E
                2
              
            
            )
          
        
        =
        
          
            
              ∑
              
                n
                =
                
                  -
                  D
                
              
              D
            
            ⁢
            
              
                (
                
                  
                    
                      x
                      1
                    
                    ⁡
                    
                      (
                      
                        n
                        +
                        
                          E
                          1
                        
                      
                      )
                    
                  
                  ⁢
                  
                    cos
                    ⁡
                    
                      (
                      
                        
                          n
                          ⁢
                          
                            
                          
                          ⁢
                          π
                        
                        
                          2
                          ⁢
                          D
                        
                      
                      )
                    
                  
                
                )
              
              ⁢
              
                (
                
                  
                    
                      x
                      2
                    
                    ⁡
                    
                      (
                      
                        n
                        +
                        
                          E
                          2
                        
                      
                      )
                    
                  
                  ⁢
                  
                    cos
                    ⁡
                    
                      (
                      
                        
                          n
                          ⁢
                          
                            
                          
                          ⁢
                          π
                        
                        
                          2
                          ⁢
                          D
                        
                      
                      )
                    
                  
                
                )
              
            
          
          
            
              
                ∑
                
                  n
                  =
                  
                    -
                    D
                  
                
                D
              
              ⁢
              
                
                  
                    (
                    
                      
                        
                          x
                          1
                        
                        ⁡
                        
                          (
                          
                            n
                            +
                            
                              E
                              1
                            
                          
                          )
                        
                      
                      ⁢
                      
                        cos
                        ⁡
                        
                          (
                          
                            
                              n
                              ⁢
                              
                                
                              
                              ⁢
                              π
                            
                            
                              2
                              ⁢
                              D
                            
                          
                          )
                        
                      
                    
                    )
                  
                  2
                
                ⁢
                
                  
                    ∑
                    
                      n
                      =
                      
                        -
                        D
                      
                    
                    D
                  
                  ⁢
                  
                    
                      (
                      
                        
                          
                            x
                            2
                          
                          ⁡
                          
                            (
                            
                              n
                              +
                              
                                E
                                2
                              
                            
                            )
                          
                        
                        ⁢
                        
                          cos
                          ⁡
                          
                            (
                            
                              
                                n
                                ⁢
                                
                                  
                                
                                ⁢
                                π
                              
                              
                                2
                                ⁢
                                D
                              
                            
                            )
                          
                        
                      
                      )
                    
                    2
                  
                
              
            
          
        
      
    
    
      
        (
        8
        )
      
    
  




Listening experiments suggest that the normalized cross-correlation is a very good measure to find the best concatenation points E1 and E2.

The concatenation of the two segments can be readily expressed in the well-known weighted overlap-and-add (OLA) representation. The short time fade-in/fade-out of speech segments in OLA will be further referred to as waveform blending. The time interval over which the waveform blending takes place is referred to as the concatenation zone. After optimization, two indices E1Opt and E2Opt are obtained that will be called the optimal blending anchors for the first and second waveform segments respectively.
To achieve high-quality waveform blending, the two blending anchors E1 and E2 vary over an optimization interval in the trailing part of the first waveform segment and in the leading part of the second waveform segment respectively such that the spectral distortion due to blending is minimized according to a given criterion; for example, maximizing the normalized cross-correlation of equation (8). The trailing part of the first speech segment and the leading part of the second speech segment are overlapped in time such that the optimal blending anchors coincide. The waveform blending itself is then achieved by means of overlap-and-add, a technique well known in the art of speech processing.
In one representative embodiment, the distance D from the left side of the join is chosen to be approximately equal to the average pitch period P derived from the speech database from which the waveforms x1(n) and x2(n) were taken. The optimization zones over which E1 and E2 vary are also of the order of P. The computational load of this optimization process is sampling-rate dependent and is of the order of P3.
Embodiments of the present invention aim to reduce the computational load for waveform concatenation while avoiding concatenation artifacts. A distinction is made between speech synthesis systems that are based on small speech segment inventories such as the traditional diphone synthesizers such as L&H TTS-3000TM, and systems based on large speech segment inventories such as the ones used in corpus-based synthesis. It will be appreciated that digital waveforms, short-time Fourier Transforms, and windowing of speech signals are commonplace in audio technology.
Representative embodiments of the present invention provide a robust and computationally efficient technique for time-domain waveform concatenation of speech segments. Computational efficiency is achieved in the synchronization of adjacent waveform segments by calculating a small set of elementary waveform features, and by using them to find the appropriate concatenation points. These waveform-deduced features can be calculated off-line and stored in moderately sized tables, which in turn can be used by the real-time waveform concatenator. Before and after concatenation, the digital waveforms may be further processed in accordance with methods that are familiar to persons skilled in the art of speech and audio processing. It is to be understood that the method of the invention is carried out in electronic equipment and the segments are provided in the form of digital waveforms so that the method corresponds to the joining of two or more input waveforms into a smaller number of output waveforms.
Combination Matrix Approach for Polyphone Concatenation Based on Small Speech Segment Inventories
Small footprint speech synthesizers such as L&H TTS-3000TM or TD-PSOLA synthesis have a relative small inventory of speech segments such as diphone and triphone speech segments. In order to reduce the computational complexity, a combination matrix containing the optimal blending anchors E1OPT and E2Opt for each waveform combination can be calculated in advance for all possible speech segment combinations.
For most languages, a typical diphone database contains more than 1000 different segments. This would require more than a million (=1000×1000) different entries in the combination matrix. Such large matrices are often inappropriate for small footprint systems. Instead, it is possible to create for each phoneme separately a combination matrix. This approach leads to a set of phoneme-dependent combination matrices that occupy only a fraction of the memory that would be required to store the global combination matrix calculated over the complete waveform segment database.
However, when working in a phoneme-dependent way, attention should be paid to the issue of phoneme substitution. Phoneme substitution is a technique well known in the art of speech synthesis. Phoneme substitution is applied when certain phoneme combinations do not occur in the speech segment database. If phoneme substitutions occur, then the waveform segments that are to be concatenated have a different phonetic content and the optimal blending anchors are not stored in the phoneme-dependent combination matrices. In order to avoid this problem, substitution should be performed before calculating the combination matrices.
The easiest way to accomplish this is by off-line substitution. Off-line substitution re-organizes the segment lookup data structures that contain the segment descriptors in such a way that the substitution process becomes transparent for the synthesizer. A typical substitution process will fill the empty slots in the segment lookup data structure by new speech segment descriptors that refer to a waveform segment in the database in such a way that the waveform segment resembles more or less to the phonetic representation of the descriptor.
It is not necessary to construct combination matrices for unvoiced phonemes such as unvoiced fricatives. This may further lead to a significant but language-dependent memory saving.
Fast Waveform Synchronization Method
Corpus-based synthesis as described in P. Rutten, G. Coorman, J. Fackrell & B. Van Coile, “Issues in Corpus-Based Speech Synthesis,” Proc. IEEE symposium on State-of-the-Art in Speech Synthesis, Savoy Place, London, April 2000, uses large databases typically containing hundreds of thousands of speech segments to synthesize high quality natural sounding speech. The creation of a combination matrix as discussed above is not always practical because the size of the combination matrix is more or less quadratically related to the size of the segment database, while current hardware platforms have limited memory capacity. The same remarks apply to time-scale modification.
The minimization of the error based on the three energy terms as given in equation (7) is time-consuming and depends heavily on the sampling-rate. In a representative embodiment of the invention, a simpler technique is used to calculate the optimal blending anchors. This leads also to efficient off-line calculation, even for large speech databases. From equations (7) and (8), it is apparent that attention must be paid to two aspects in the concatenation interval: low energy and high waveform similarity.
Listening experiments suggest that in comparison with unsynchronized waveform blending, concatenation artifacts can be reduced by performing synchronized waveform blending that takes into account minimum energy conditions only, i.e. by selecting the blending anchors E1 and E2 through the minimization of the following error function:




  
    
      ξ
      Engy
    
    ⁢
    
      (
      
        
          E
          1
        
        ,
        
          E
          2
        
      
      )
    
  
  =
  
    
      
        ∑
        
          n
          =
          
            -
            D
          
        
        D
      
      ⁢
      
        
          (
          
            
              
                x
                1
              
              ⁢
              
                (
                
                  n
                  +
                  
                    E
                    1
                  
                
                )
              
            
            ⁢
            
              cos
              ⁢
              
                (
                
                  
                    n
                    ⁢
                    
                      
                    
                    ⁢
                    π
                  
                  
                    2
                    ⁢
                    D
                  
                
                )
              
            
          
          )
        
        2
      
    
    +
    
      
        ∑
        
          n
          =
          
            -
            D
          
        
        D
      
      ⁢
      
        
          (
          
            
              
                x
                2
              
              ⁢
              
                (
                
                  n
                  +
                  
                    E
                    2
                  
                
                )
              
            
            ⁢
            
              cos
              ⁢
              
                (
                
                  
                    n
                    ⁢
                    
                      
                    
                    ⁢
                    π
                  
                  
                    2
                    ⁢
                    D
                  
                
                )
              
            
          
          )
        
        2
      
    
  




The above minimization criterion treats the two waveforms independently (absence of cross term), enabling the process for off-line calculation. In other words, the first blending anchor E1 is determined by minimizing





  
    ∑
    
      n
      =
      
        -
        D
      
    
    D
  
  ⁢
  
    
      (
      
        
          
            x
            1
          
          ⁢
          
            (
            
              n
              +
              
                E
                1
              
            
            )
          
        
        ⁢
        
          cos
          ⁢
          
            (
            
              
                n
                ⁢
                
                  
                
                ⁢
                π
              
              
                2
                ⁢
                D
              
            
            )
          
        
      
      )
    
    2
  




and the second blending anchor E2 is determined by minimizing





  
    ∑
    
      n
      =
      
        -
        D
      
    
    D
  
  ⁢
  
    
      (
      
        
          
            x
            2
          
          ⁢
          
            (
            
              n
              +
              
                E
                2
              
            
            )
          
        
        ⁢
        
          cos
          ⁢
          
            (
            
              
                n
                ⁢
                
                  
                
                ⁢
                π
              
              
                2
                ⁢
                D
              
            
            )
          
        
      
      )
    
    2
  




In the following, these will be called the minimum energy anchors.

In order to find the minimum energy anchors, the above terms would be calculated for different values of E1 and E2 in the optimization interval. That is time-consuming. In general, the two optimization intervals over which E1 and E2 may vary are convex intervals. The weighted energy calculation can be calculated as a sliding weighted energy, and this is a candidate for optimization.
Assume x is the signal from which to compute the sliding weighted energy. The weighting is done by means of a point-wise multiplication of the signal x by a window. In the most straightforward way, the calculation of the weighted energy may be implemented as:




  
    
      
        
          
            e
            n
          
          =
          
            
              
                ∑
                
                  k
                  =
                  
                    n
                    -
                    M
                  
                
                
                  n
                  +
                  M
                
              
              ⁢
              
                
                  w
                  
                    k
                    -
                    n
                  
                
                ⁢
                
                  x
                  k
                  2
                
                ⁢
                
                  
                
                ⁢
                n
              
            
            =
            0
          
        
        ,
        1
        ,
        ...
        ⁢
        
          
        
        ,
        N
      
    
    
      
        (
        9
        )
      
    
  




This requires 2(M+1)(N+1) multiplications and 2M (N+1) additions, assuming that the signal x is squared and stored in a buffer only once before windowing. If the window can be expressed as a trigonometric sum (such as the Hanning, Hamming and Blackman windows), then the computational complexity can be reduced drastically.

Take the Hanning window (i.e. raised cosine window) as an example:




  
    
      w
      n
    
    =
    
      
        
          
            cos
            2
          
          ⁢
          
            (
            
              
                π
                ⁢
                
                  
                
                ⁢
                n
              
              
                2
                ⁢
                M
              
            
            )
          
        
        ⁢
        
          
        
        ⁢
        n
      
      =
      
        -
        M
      
    
  
  ,
  ...
  ⁢
  
    
  
  ,
  0
  ,
  ...
  ⁢
  
    
  
  ,
  M




This can be re-written as:





  
    
      
        
          
            w
            n
          
          =
          
            
              
                1
                2
              
              ⁢
              
                (
                
                  1
                  +
                  
                    cos
                    ⁡
                    
                      (
                      
                        
                          π
                          ⁢
                          
                            
                          
                          ⁢
                          n
                        
                        M
                      
                      )
                    
                  
                
                )
              
              ⁢
              
                
              
              ⁢
              n
            
            =
            
              -
              M
            
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        0
        ,
        ...
        ⁢
        
          
        
        ,
        M
      
    
    
      
        (
        10
        )
      
    
  




The calculation of the energy based on a raised cosine window is obtained by substituting equation (10) in equation (9), resulting in:





  
    
      e
      n
    
    =
    
      
        
          
            ∑
            
              k
              =
              
                n
                -
                M
              
            
            
              n
              +
              M
            
          
          ⁢
          
            x
            k
            2
          
        
        +
        
          
            ∑
            
              k
              =
              
                n
                -
                M
              
            
            
              n
              +
              M
            
          
          ⁢
          
            
              cos
              ⁢
              
                (
                
                  
                    
                      (
                      
                        k
                        -
                        n
                      
                      )
                    
                    ⁢
                    π
                  
                  M
                
                )
              
            
            ⁢
            
              x
              k
              2
            
            ⁢
            
              
            
            ⁢
            n
          
        
      
      =
      0
    
  
  ,
  1
  ,
  ...
  ⁢
  
    
  
  ,
  N




The weighted energy consists clearly out of two terms: en=enu+enc; an unweighted short-term energy





  
    e
    n
    u
  
  =
  
    
      1
      2
    
    ⁢
    
      
        ∑
        
          k
          =
          
            n
            -
            M
          
        
        
          n
          +
          M
        
      
      ⁢
      
        x
        k
        2
      
    
  




and an energy modulation term





  
    e
    n
    c
  
  =
  
    
      1
      2
    
    ⁢
    
      
        ∑
        
          k
          =
          
            n
            -
            M
          
        
        
          n
          +
          M
        
      
      ⁢
      
        cos
        ⁢
        
          (
          
            
              
                (
                
                  k
                  -
                  n
                
                )
              
              ⁢
              π
            
            M
          
          )
        
        ⁢
        
          x
          k
          2
        
      
    
  




These two energy components can be calculated recursively. Assuming that enu is known, the next term en+1u may be expressed as a function of enu:




  
    e
    
      n
      +
      1
    
    u
  
  =
  
    
      
        1
        2
      
      ⁢
      
        
          ∑
          
            k
            =
            
              n
              +
              1
              -
              M
            
          
          
            n
            +
            1
            +
            M
          
        
        ⁢
        
          x
          k
          2
        
      
    
    =
    
      
        e
        n
        u
      
      +
      
        
          1
          2
        
        ⁢
        
          (
          
            
              x
              
                n
                +
                1
                +
                M
              
              2
            
            -
            
              x
              
                n
                -
                M
              
              2
            
          
          )
        
      
    
  




A recursive formulation of the modulated energy term can be obtained by means of some simple math, based on some well-known trigonometric relations:




  
    e
    
      n
      +
      1
    
    c
  
  =
  
    
      
        1
        2
      
      ⁢
      
        cos
        ⁢
        
          (
          
            π
            M
          
          )
        
      
      ⁢
      
        
          ∑
          
            k
            =
            
              n
              -
              M
            
          
          
            n
            +
            M
          
        
        ⁢
        
          
            cos
            ⁢
            
              (
              
                
                  
                    (
                    
                      k
                      -
                      n
                    
                    )
                  
                  ⁢
                  π
                
                M
              
              )
            
          
          ⁢
          
            x
            k
            2
          
        
      
    
    +
    
      
        1
        2
      
      ⁢
      
        sin
        ⁢
        
          (
          
            π
            M
          
          )
        
      
      ⁢
      
        
          ∑
          
            k
            =
            
              n
              -
              M
            
          
          
            n
            +
            M
          
        
        ⁢
        
          
            sin
            ⁢
            
              (
              
                
                  
                    (
                    
                      k
                      -
                      n
                    
                    )
                  
                  ⁢
                  π
                
                M
              
              )
            
          
          ⁢
          
            x
            k
            2
          
        
      
    
    -
    
      
        1
        2
      
      ⁢
      
        x
        
          n
          +
          1
          +
          M
        
        2
      
    
    +
    
      
        1
        2
      
      ⁢
      
        cos
        ⁢
        
          (
          
            π
            M
          
          )
        
      
      ⁢
      
        x
        
          n
          -
          M
        
        2
      
    
  




If we define





  
    
      e
      n
      s
    
    =
    
      
        1
        2
      
      ⁢
      
        
          ∑
          
            k
            =
            
              n
              -
              M
            
          
          
            n
            +
            M
          
        
        ⁢
        
          
            sin
            ⁢
            
              (
              
                
                  
                    (
                    
                      k
                      -
                      n
                    
                    )
                  
                  ⁢
                  π
                
                M
              
              )
            
          
          ⁢
          
            x
            k
            2
          
        
      
    
  
  ,




then the following recursion is obtained:





  
    e
    
      n
      +
      1
    
    c
  
  =
  
    
      
        (
        
          
            e
            n
            c
          
          +
          
            
              1
              2
            
            ⁢
            
              x
              
                n
                -
                M
              
              2
            
          
        
        )
      
      ⁢
      
        cos
        ⁢
        
          (
          
            π
            M
          
          )
        
      
    
    +
    
      
        e
        n
        s
      
      ⁢
      
        sin
        ⁢
        
          (
          
            π
            M
          
          )
        
      
    
    -
    
      
        1
        2
      
      ⁢
      
        x
        
          n
          +
          1
          +
          M
        
        2
      
    
  




A recursive formulation for ens is obtained by applying some some well-known trigonometric relations:





  
    e
    
      n
      +
      1
    
    s
  
  =
  
    
      
        e
        n
        s
      
      ⁢
      
        cos
        ⁢
        
          (
          
            π
            M
          
          )
        
      
    
    -
    
      
        (
        
          
            e
            n
            c
          
          +
          
            
              1
              2
            
            ⁢
            
              x
              
                n
                -
                M
              
              2
            
          
        
        )
      
      ⁢
      
        sin
        ⁢
        
          (
          
            π
            M
          
          )
        
      
    
  




The waveform synchronization algorithm that is described below requires only the location of the minimum energy and a comparison of the minimum energy of the left segment with the minimum energy of the right segment. Therefore, the factor 1⁄2 may be omitted in the definition of the window (10), resulting in simpler expressions. Thus, we assume that A is the time-index corresponding to the first weighted energy value. We also assume that the interval length over which we calculate the weighted energy is N. This leads to the following efficient algorithm:
Square x in the Interval of Interest and Store in Buffer
Algorithm

uk=xk2k=[A−M,A+N+M]

Complexity

    
    
        zero additions and N+2M+1 multiplications.

Calculate Start Values

    
    


Algorithm




  
    
      
        
          e
          A
          u
        
        =
        
        ⁢
        
          
            ∑
            
              k
              =
              
                A
                -
                M
              
            
            
              A
              +
              M
            
          
          ⁢
          
            u
            k
          
        
      
    
  
  
    
      
        
          e
          A
          c
        
        =
        
        ⁢
        
          
            ∑
            
              k
              =
              
                A
                -
                M
              
            
            
              A
              +
              M
            
          
          ⁢
          
            
              cos
              ⁡
              
                (
                
                  
                    
                      (
                      
                        k
                        -
                        A
                      
                      )
                    
                    ⁢
                    π
                  
                  M
                
                )
              
            
            ⁢
            
              u
              k
            
          
        
      
    
  
  
    
      
        
          e
          A
          s
        
        =
        
        ⁢
        
          
            ∑
            
              k
              =
              
                A
                -
                M
              
            
            
              A
              +
              M
            
          
          ⁢
          
            
              sin
              ⁡
              
                (
                
                  
                    
                      (
                      
                        k
                        -
                        A
                      
                      )
                    
                    ⁢
                    π
                  
                  M
                
                )
              
            
            ⁢
            
              u
              k
            
          
        
      
    
  
  
    
      
        
          e
          A
        
        =
        
        ⁢
        
          
            e
            A
            u
          
          +
          
            e
            A
            c
          
        
      
    
  




Complexity

    
    
        2(3M+2) additions and 2(2M+1) multiplications

Use the Following Recursive Relations to Calculate the Other Values

    
    


Algorithm




  {
  
    
      
        
          
            
              
                
                  e
                  
                    n
                    +
                    1
                  
                  u
                
                =
                
                  
                    e
                    n
                    u
                  
                  +
                  
                    (
                    
                      
                        u
                        
                          n
                          +
                          1
                          +
                          M
                        
                      
                      -
                      
                        u
                        
                          n
                          -
                          M
                        
                      
                    
                    )
                  
                
              
            
          
          
            
              
                
                  e
                  
                    n
                    +
                    1
                  
                  c
                
                =
                
                  
                    
                      (
                      
                        
                          e
                          n
                          c
                        
                        +
                        
                          u
                          
                            n
                            -
                            m
                          
                        
                      
                      )
                    
                    ⁢
                    
                      cos
                      ⁡
                      
                        (
                        
                          π
                          M
                        
                        )
                      
                    
                  
                  +
                  
                    
                      e
                      n
                      s
                    
                    ⁢
                    
                      sin
                      ⁡
                      
                        (
                        
                          π
                          M
                        
                        )
                      
                    
                  
                  -
                  
                    u
                    
                      n
                      +
                      1
                      +
                      M
                    
                  
                
              
            
          
          
            
              
                
                  e
                  
                    n
                    +
                    1
                  
                  s
                
                =
                
                  
                    
                      -
                      
                        (
                        
                          
                            e
                            n
                            c
                          
                          +
                          
                            u
                            
                              n
                              -
                              m
                            
                          
                        
                        )
                      
                    
                    ⁢
                    
                      sin
                      ⁡
                      
                        (
                        
                          π
                          M
                        
                        )
                      
                    
                  
                  +
                  
                    
                      e
                      n
                      s
                    
                    ⁢
                    
                      cos
                      ⁡
                      
                        (
                        
                          π
                          M
                        
                        )
                      
                    
                  
                
              
            
          
          
            
              
                
                  e
                  
                    n
                    +
                    1
                  
                
                =
                
                  
                    e
                    
                      n
                      +
                      1
                    
                    u
                  
                  +
                  
                    e
                    
                      n
                      +
                      1
                    
                    c
                  
                
              
            
          
        
        ⁢
        
          
        
        ⁢
        
          

        
        ⁢
        n
      
      =
      A
    
    ,
    
      A
      +
      1
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      A
      +
      N
      -
      1
    
  




Complexity

    
    
        7N additions and 4N multiplications.

Overall Complexity

        7N+6M+4 additions
        5N+6M+3 multiplications

N and 2M are of the same order and much larger than 10. This means that the approximate gain in computational efficiency is

    
    






  
    ≈
    
      
        N
        2
      
      
        10
        ⁢
        N
      
    
  
  =
  
    
      N
      10
    
    .
  




At 22 kHz with N=150, we get an efficiency gain factor of 15.

Unfortunately some concatenation artifacts remain audible if the synchronization is based solely on the minimum energy anchors because waveform similarity is completely neglected. This problem can be addressed by introducing a second optimization criterion that incorporates waveform similarity and thus further reduces the concatenation artifacts.
In one representative embodiment, the time position of the largest peak or trough of the low-pass filtered waveform in the local neighborhood of the join is used in the waveform similarity process. The waveform similarity process may synchronize the left and right signal based on the position of the largest peak instead of using an expensive cross-correlation criterion. The low-pass filter serves to avoid picking up spurious signal peaks that may differ from the peak corresponding to the (lower) harmonics contributing most to the signal power of the voiced speech. The order of the low-pass filter is moderate to low and is sampling-rate dependent. For example, the low-pass filter may be implemented as a multiplication-free nine-tap zero-phase summator for speech recorded at a sampling-rate of 22 kHz.
The decision to synchronize on the largest peak or trough depends on the polarity of the recorded waveforms. In most languages, voiced speech is produced during exhalation resulting in a unidirectional glottal airflow causing a constant polarity of the speech waveforms. The polarity of the voiced speech waveform can be detected by investigating the direction of pulses of the inverse filtered speech signal (i.e. residual signal), and may often also be visible by investigating the speech waveform itself. The polarity of any two speech recordings is the same despite the non stationary character of the speech as long as certain recording conditions remain the same, among others: the speech is always produced on exhalation and the polarity of the electric recording equipment is unchanged in time.
In order to achieve optimal waveform similarity (i.e. maximum cross-correation) the waveforms of the voiced segments to be concatenated should have the same polarity. However, if the recording equipment settings that control the polarity change over time it is still possible to transform the recorded speech waveforms that are affected by a polarity change by multiplying the sample values by minus one, such that their polarity is of all recordings is the same.
Listening experiments indicate that the best concatenation results are obtained by synchronization based on the largest peaks, if the largest peaks have higher average magnitude than the lowest troughs (this observed over many different speech signals recorded with the same equipment and recording conditions, for example, a single speaker speech database). In the other case, the lowest troughs are considered for synchronization. In what follows, those peaks or troughs used for synchronization are called the synchronization peaks. (The troughs are then regarded as negative peaks.) Listening experiments further indicate that waveform synchronization based on the location of the synchronization peaks alone results in a substantial improvement compared with unsynchronized concatenation. A further improvement in concatenation quality can be achieved by combining the minimum energy anchors with the synchronization peaks.
FIG. 4 shows the left speech segment in the neighborhood of the join J. The join J identifies an interval where concatenation can take place. The length of that interval is typically in the order of one to more pitch periods and is often regarded as a constant. In FIG. 4, the weighted energy, the low-pass filtered signal and the weighted signal (fade-out) are also shown. For reasons of clarity, the signals are scaled differently. FIG. 4 helps to understand the process of determining the anchors of the left segment. Time-index D indicates the location of minimum weighted energy in the neighborhood of the join J. This is the so-called minimum energy anchor as defined above. In this particular case, it is assumed that the first blending anchor is taken as that minimum energy anchor (A more detailed discussion on the anchor selection can be found in the algorithm descriptions below).
In a representative embodiment, the middle of the concatenation zone is assumed to correspond to the blending anchor D. Time-index A from FIG. 4 corresponds with the start of the concatenation zone (i.e. fade-out interval), and time-index B indicates the end of the concatenation zone. D corresponds to A plus the half of the fade-out interval. However, this is not a strict condition for this invention. (For example, a fade-out function that differs from 0.5 at its center may result in different positions of the fade-out interval with respect to the blending anchor.) C is the time-index corresponding to the synchronization peak in the neighborhood of the minimum energy anchor. Synchronization requires the synchronization peaks of the two adjoining segments to coincide when the waveforms in the fade-in and fade-out zones are overlapped. If the synchronization peak for the right segment is given by C′, then synchronization requires the blending anchor for the right segment to be equal to D′=C′−(C−D). The resulting blending anchor D′ defines the position of the fade-in interval of the right segment. The fade-in and fade-out intervals have the same length as they are overlapped during waveform blending to form the concatenation zone.
The left and right optimization zones for both segments are assumed to be known in advance, or to be given by the application that uses segment concatenation. For example, in a diphone synthesizer the optimization zone of the left (i.e. first) waveform corresponds to the region (typically in the nucleus part of the right phoneme of the diphone) where the diphone may be cut, and the optimization zone of the right (i.e. second) waveform corresponds to the location of the left phoneme of the right diphone where the diphone may be cut. These cutting locations are typically determined by means of (language-dependent) rules, or by means of signal processing techniques that search for stationarity for example. The cutting locations for TSM application are obtained in a different way by slicing the speech into short (typically equidistant) frames of speech.
An implementation of the synchronization algorithm to concatenate a left and a right waveform segment consists of the following steps:

    
    
        1. Search in the optimization zone located in the trailing part of the left waveform segment and the optimization zone located in the leading part of the right digital waveform segment for the minimum energy anchors; for example, using the efficient sliding weighted energy calculation algorithm described above. The optimization zone is preferably a convex interval around the join that has a length of at least one pitch period.
        2. Based on the left and right low-pass filtered speech signals, the two synchronization peaks are searched for in the (close) neighborhood of the two minimum energy anchors obtained in step 1. The “neighborhood” of a minimum energy anchor corresponds to a convex interval that includes the minimum energy anchor and that has preferably a length of at least one pitch period. A typical choice of the “neighborhood” could be the optimization interval for example.
        3. A first blending anchor is chosen as the minimum energy anchor that corresponds to the lowest energy. This choice minimizes one of the minimum energy conditions. The other blending anchor that resides in the other speech waveform segment is chosen in such a way that the synchronization peaks coincide when the waveforms are (partly) overlapped in the concatenation zone prior to blending.
    
    


Although less optimal, the algorithm may also work if the synchronization does not take into account the value of the minimum weighted energy of the two minimum energy anchors (as described in step 3). This corresponds to blind assignment of a minimum energy anchor to a blending anchor. In this approach one (left or right) minimum energy anchor is systematically chosen as the blending anchor. In this case, the calculation of the other minimum energy anchor is superfluous and can thus be omitted.
In a representative embodiment, the length of the concatenation zone is is taken as the maximum pitch period of the speech of a given speaker; however, it is not necessary to do so. One could, for example, instead take the maximum of the local pitch period of the first segment and the local pitch period of the second segment or a larger interval.
In another variant of the fast synchronization algorithm, the function of the synchronization peak and the minimum energy anchors can be switched:

    
    
        1. Search in the optimization zone located in the trailing part of the left waveform segment and the optimization zone located in the leading part of the right digital waveform segment for the synchronization peaks based on the left and right low-pass filtered speech waveform segments.
        2. The two minimum energy anchors are searched for in the (close) neighborhood of the two synchronization peaks obtained in step 1. The close “neighborhood” of a synchronization peak corresponds to a convex interval that includes the synchronization peak and that has a length preferably larger than one pitch period. A typical choice of the “neighborhood” could be the optimization interval for example.
        3. A first blending anchor is chosen as the minimum energy anchor that corresponds to the lowest energy. This choice minimizes one of the minimum energy conditions. The other blending anchor that resides in the other speech waveform segment is chosen in such a way that the synchronization peaks coincide when the waveforms are partly overlapped in the concatenation zone prior to blending.
    
    


Analogously as discussed above, the algorithm can also work if the synchronization does not take into account the value of the minimum weighted energy corresponding to the two minimum energy anchors (as described in step 3). This corresponds to a blind assignment of a minimum energy anchor to a blending anchor. In this approach one (left or right) minimum energy anchor is systematically chosen as the blending anchor. This means that in this case the calculation of the other minimum energy anchor is superfluous and can thus be omitted.
In the algorithms described above, some alternatives for the synchronization peak may be used such as the maximum peak of the derivative of the low-pass filtered speech signal, or the maximum peak of the low-pass filtered residual signal that is obtained after LPC inverse filtering.
A functional diagram of the speech waveform concatenator is given in FIG. 2, which shows the synchronization and blending process. A part of the trailing edge of the left (first) waveform segment, larger than the optimization zone, is stored in buffer 200. The part of the leading edge of the second waveform segment of a size, larger than the optimization zone is stored in a second buffer 201.
In an embodiment of the invention, the minimum energy anchor of the waveform in the buffer 200 is calculated in the minimum energy detector 210, and this information is passed on to the waveform blender/synchronizer 240 together with the value of the minimum weighted energy at the minimum energy anchor. Analogously, the minimum energy detector 211 performs a search to detect the minimum energy anchor point of the waveform stored in buffer 201 and passes it on together with the corresponding weighted energy value to the waveform blender/synchronizer 240. (In another embodiment of the invention, only one of the two minimum energy detectors 210 or 211 are used to select the first blending anchor.) For some applications, such as TTS, the position of the minimum energy anchors can be stored off-line, resulting in a faster synchronization. In the latter case, the minimum energy detection process is equivalent to a table lookup.
Next, the waveform from buffer 200 is low-pass filtered with a zero-phase filter 220 to generate another waveform. This new waveform is then subjected to a peak-picking search 230 taking into account the polarity of the waveforms (as described above). The location of the maximum peak is passed to the waveform blender/synchronizer 240. On the signal from buffer 201, the same processing steps are carried out by the zero-phase low-pass filter 221 and peak detector 231, which results in the location of the other synchronization peak. This location is send to the waveform blender/synchronizer 240.
As described above, the waveform blender/synchronizer 240 selects a first blending anchor based on the energy values, or based on some heuristics and a second blending anchor based on the alignment condition of the synchronization peaks. The waveform blender/synchronizer 240 overlaps the fade-out interval of the left (first) waveform segment and the fade-in region of the right (second) waveform segment that are obtained from the buffers 200 and 201, before weighting and adding them. The weighting and adding process is well known in the art of speech processing and is often referred to as (weighted) overlap-and-add processing.
Storage of Features
Because of the high computational efficiency of the synchronization algorithm used, for many applications it is not necessary that the parameters that are used in the synchronization process be calculated off-line and stored. However, in some critical cases it might be useful to store one or more synchronization parameters. In general, the minimum energy anchors are stored because of the large gain in computational efficiency and because they are independent of the adjoining waveform. In a TTS system, for example, the computational load may be reduced by storing those features in tables. Most TTS systems use a table of diphone or polyphone boundaries in order to retrieve the appropriate segments. It is possible to “correct” this polyphone boundary table by replacing the boundaries by their closest minimum energy anchor. In the case of a TTS system, this approach requires no additional storage and reduces the CPU load for synchronization significantly. However, on some hardware systems it might be useful to store the closest synchronization anchors instead of the closest minimum energy anchors.

## Claims

1. A digital waveform concatenation system for use in an acoustic processing application, the system comprising:
a digital waveform provider that produces an input sequence of at least two digital waveform segments, each waveform segment being a sequence of samples; and
a waveform concatenator that:
i. synchronizes input waveform segments to form a sequence of partially overlapping waveform segments, and
ii. weights and adds selected portions of the overlapping waveform segments to concatenate the input waveform segments so as to produce a single digital waveform;

wherein for segments of voiced speech, the synchronizing includes aligning a minimum energy anchor in each waveform segment with a corresponding minimum energy anchor of an adjacent waveform segment, each minimum energy anchor location in a given segment being optimized based on determining minimum weighted energy in a neighborhood of a boundary of the given segment.

2. A concatenation system according to claim 1, wherein the acoustic processing application includes a text-to-speech application.

3. A concatenation system according to claim 1, wherein the acoustic processing application includes a speech broadcast application.

4. A concatenation system according to claim 1, wherein the acoustic processing application includes a carrier-slot application.

5. A concatenation system according to claim 1, wherein the acoustic processing application includes a time-scale modification system.

6. A concatenation system according to claim 1, wherein the waveform segments include at least one of speech diphones and speech triphones.

7. A concatenation system according to claim 1, wherein the waveform segments include at least one of speech phones and speech demi-phones.

8. A concatenation system according to claim 1, wherein the waveform segments include at least one of speech demi-syllables, speech syllables, words, and phrases.

9. A concatenation system according to claim 1, wherein determining minimum weighted energy in the selected portion includes using a sliding weighted energy calculation algorithm.

10. A concatenation system according to claim 1, wherein the input segments are filtered before synchronizing.

11. A concatenation system according to claim 1, wherein aligning minimum energy anchors includes determining a largest waveform peak or trough in the close neighborhood of each minimum energy anchor.

12. A concatenation system according to claim 11, wherein the close neighborhood is an interval of at least one pitch period containing the minimum energy anchor.

13. A concatenation system according to claim 11, wherein the close neighborhood is the selected portion of the input segment.

14. A concatenation system according to claim 11, wherein the location of one minimum energy anchor is the lowest weighted energy location in the selected portion.

15. A concatenation system according to claim 14, wherein another minimum energy anchor location is chosen such that the previously determined waveform peak or trough in each selected portion coincide when the input segments are overlap-added.

16. A digital waveform concatenation system for use in an acoustic processing application, the system comprising:
a digital waveform provider that produces an input sequence of at least two digital waveform segments, each waveform segment being a sequence of samples; and
a waveform concatenator that:
i. synchronizes successive waveform segments to form a sequence of partially overlapping waveform segments, the overlapping portion of each waveform segment including an optimization zone near a waveform segment boundary, and
ii. weights, and adds selected portions of the input segments to concatenate the input segments so as to produce a single digital waveform;

wherein for segments of voiced speech, the synchronizing includes aligning a largest waveform peak or trough in the optimization zone of each input waveform segment with a corresponding largest waveform peak or trough in an optimization zone of an adjacent waveform segment.

17. A concatenation system according to claim 16, wherein the acoustic processing application includes a text-to-speech application.

18. A concatenation system according to claim 16, wherein the acoustic processing application includes a speech broadcast application.

19. A concatenation system according to claim 16, wherein the acoustic processing application includes a carrier-slot application.

20. A concatenation system according to claim 16, wherein the waveform segments include at least one of speech diphones and speech triphones.

21. A concatenation system according to claim 16, wherein the waveform segments include at least one of speech phones and speech demi-phones.

22. A concatenation system according to claim 16, wherein the waveform segments include at least one of speech demi-syllables, speech syllables, words, and phrases.

23. A concatenation system according to claim 16, wherein the input segments are filtered before aligning.

24. A digital waveform concatenation system for use in an acoustic processing application, the system comprising:
a digital waveform provider that produces an input sequence of at least two digital waveform segments, each waveform segment being a sequence of samples; and
a waveform concatenator that:
i. synchronizes successive waveform segments to form a sequence of partially overlapping waveform segments, and
ii. weights and adds selected portions of the overlapping waveform segments to concatenate the input waveform segments so as to produce a single digital waveform;

wherein for segments of voiced speech, the synchronizing includes aligning synchronization peaks or troughs in selected portion of each input waveform segment with synchronization peaks or troughs in a corresponding selected portion of an adjacent waveform segment, the location of the selected portions being determined by searching in a neighborhood of waveform segment boundaries for a location where the sum of the weighted energy of the selected portions is minimal.

25. A concatenation system according to claim 24, wherein the acoustic processing application includes a text-to-speech application.

26. A concatenation system according to claim 24, wherein the acoustic processing application includes a speech broadcast application.

27. A concatenation system according to claim 24, wherein the acoustic processing application includes a carrier-slot application.

28. A concatenation system according to claim 24, wherein the acoustic processing application includes a time-scale modification system.

29. A concatenation system according to claim 24, wherein the waveform segments include at least one of speech diphones and speech triphones.

30. A concatenation system according to claim 24, wherein the waveform segments include at least one of speech phones and speech demi-phones.

31. A concatenation system according to claim 24, wherein the waveform segments include at least one of speech demi-syllables, speech syllables, words, and phrases.

32. A concatenation system according to claim 24, wherein determining a minimum weighted energy anchor includes using a sliding weighted energy calculation algorithm.

33. A concatenation system according to claim 24, wherein the input segments are filtered before synchronizing.

34. A concatenation system according to claim 24, wherein aligning synchronization peaks or troughs includes determining a largest waveform peak or trough in the close neighborhood of each anchor.

35. A concatenation system according to claim 34, wherein the close neighborhood is an interval of at least one pitch period containing the minimum energy anchor.

36. A concatenation system according to claim 34, wherein the close neighborhood is the selected portion of the input segment.

37. A concatenation system according to claim 34, wherein the location of one anchor is chosen such that the synchronization peaks or troughs in each selected portion coincide when the input segments are overlap-added.

38. A digital waveform concatenation system for use in an acoustic processing application, the system comprising:
a digital waveform provider that produces an input sequence of at least two digital waveform segments, each waveform segment being a sequence of samples; and
a waveform concatenator that:
i. synchronizes successive waveform segments to form a sequence of partially overlapping waveform segments, and
ii. weights, and adds selected portions of the overlapping waveform segments to concatenate the input waveform segments so as to produce a single digital waveform;

wherein for pairs of overlapping segments of voiced speech, a first selected portion includes a minimum energy anchor in a location optimized based on determining minimum weighted energy in a neighborhood of the waveform segment boundaries, and a second selected portion is determined by aligning synchronization peaks or troughs in the neighborhood of the waveform segment boundaries.

39. A concatenation system according to claim 38, wherein the acoustic processing application includes a text-to-speech application.

40. A concatenation system according to claim 38, wherein the acoustic processing application includes a speech broadcast application.

41. A concatenation system according to claim 38, wherein the acoustic processing application includes a carrier-slot application.

42. A concatenation system according to claim 38, wherein the acoustic processing application includes a time-scale modification system.

43. A concatenation system according to claim 38, wherein the waveform segments include at least one of speech diphones and speech triphones.

44. A concatenation system according to claim 38, wherein the waveform segments include at least one of speech phones and speech demi-phones.

45. A concatenation system according to claim 38, wherein the waveform segments include at least one of speech demi-syllables, speech syllables, words, and phrases.

46. A concatenation system according to claim 38, wherein determining a minimum weighted energy anchor includes using a sliding weighted energy calculation algorithm.

47. A concatenation system according to claim 38, wherein the input segments are filtered before synchronizing.

48. A concatenation system according to claim 38, wherein aligning synchronization peaks or troughs includes determining a largest waveform peak or trough in the close neighborhood of the anchor and determining a corresponding peak or trough in the selected portion of the other input segment.

49. A concatenation system according to claim 48, wherein the close neighborhood is an interval of at least one pitch period containing the minimum weighted energy anchor.

50. A concatenation system according to claim 48, wherein the close neighborhood is the selected portion of the input segment.