Multi-point voice conferencing system over a wide area network

Field of the Invention

0001The present invention relates to wide-area network communication, and in particular, to interactive communication of speech and related information over a wide-area network.

Background of the Invention

0002Computer technology went through major developments during the past several years. The first development is the availability of low cost yet powerfull personal computers. The reduction in cost makes computers affordable to a large number of people. As a result, the number of computers increases exponentially. The processing power of these computers is more than that of mainframe computers existed about ten years ago. Further, these computers typically come with modems, sound cards, high resolution video boards, etc., which allow them to process multimedia information, such as speech and images.

0003The second development is the popularity of a wide-area network called Internet. Internet is currently the largest computer network in existence. It is a worldwide interconnection of millions of computers, from low end personal computers to high-end mainframes. The Internet grew out of work funded in the 1960s by the U. S. Defense Department's Advanced Research Projects Agency. For a long time, Internet was used by researchers in universities and national laboratories to share information. As the existence of the Internet became more widely known, many users outside of the academic/research community (e.g., employees of large corporations) started to use Internet to carry electronic mails. In 1989, a wide-area information system known as the World Wide Web ("the Web") was developed. The Web is a wide-area hypermedia information retrieval system aimed to give universal access to a large universe of documents. A user can use a software (called a browser) to retrieve web documents (typically displayed in graphic form) and navigate the Web using simple commands and popular tools such as point-and-click. Because the user does not have to be technically trained and the browser is pleasant to use, it has the potential of opening up the Internet to the masses. Consequently, many communication companies have developed hardware and software products which allow people to use their computers to access the Internet.

0004Because of these developments, many people have the resources to electronically communicate with other people using the Internet. Currently, most of the communication involve text (e.g., electronic mails) and graphics (e.g., Web documents). Further, the mode of communication is passive, i.e., the information can be read or displayed by recipients a long time (e.g., hours or days) after its creation.

0005It is known that human beings enjoy interaction with other people. It is also known that speech and facial expression associated with speech are powerful communication tools. Thus, it is desirable to use the Internet to interactively communicate speech and associated facial expression. Currently, there is no product that can efficiently achieve this mode of communication.

Summary of the Invention

0006The present invention can be used in an interactive network system for communicating speech and associated information among a plurality of participants at different sites. Each participant uses a multimedia computer to connect to the network. The multimedia computer contains a microphone, at least one loudspeaker, a display device and a network accessing device (such as a modem). A speech processing software is executing in the computer while an interactive speech session takes place. The participant can speak to the microphone. The software encodes the speech and associated data, and sends the data to a speech server using the network accessing device. The speech server can accumulate speech data from one of more participants at different sites, and deliver a combined speech data to a designation site. The software in the multi-media personal computer can decode information received from the server, and reproduce the speech through its loudspeaker.

0007Many modems have a low communication rate (i.e., bits-per-second). Thus, it is important to compress the speech and associated data so that it can be handled by the modems. The compression method of the present invention takes into account of the characteristics of speech so as to be able to communicate speech within the communication rate of the modem.

0008One aspect of the compression method is a novel method to obtain the acoustic characteristics of the echo path and perform echo cancellation. The system can also detect silence. During a silence period, there is no need to transmit speech information. Thus, the ability to accurately detect silence can increase the compression ratio. This method involves determining residual echo energy, and use this energy in the determination of silence.

0009The echo energy is an acoustic characteristic of the user site. The present invention also involves a novel method of measuring and calibrating the acoustic characteristics of the user site.

0010The present invention also uses novel methods to compress speech data by using a combination of vector and scalar quantization of linear predictive coding parameters, multi-pulse excitation parameters, pulse position coding, and pulse amplitude coding, either individually or in combination. Further, speech compressed using these methods can be decompressed, thereby recovering the original speech.

0011The present invention also involves novel and computationally efficient lip synching methods. It is observed that the lip positions in human beings can be determined to a large extent by the first two peaks, known as formant frequencies, of the short term spectra of speech and the short-term energy of the speech signal. Further, the variables associated with the lip positions are highly correlated. The present invention exploits these relationship to code the lip positions using a very small number of bits. These bits are sent to a destination site (via the server). The computer at the destination site can draw a face with appropriate lip positions on the display device.

Brief Description of the Drawings

0012Fig. 1 is a drawing showing a multi-point voice conferencing system of the present invention.

0013Fig. 2A is a block diagram of an encoder of the present invention.

0014Fig. 2B is a block diagram of a decoder of the present invention.

0015Fig. 2C is a schematic diagram of a participant site of the present invention.

0016Fig. 3 is a block diagram of an arrangement for measuring acoustic characteristics in accordance with the present invention.

Detailed Description of the Invention

0017The present invention comprises a novel voice conferencing system and associated methods. The following description is presented to enable any person skilled in the art to make and use the invention. Descriptions of specific applications are provided only as examples. Various modifications to the preferred embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the invention. Thus, the present invention is not intended to be limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein.

0018Fig. 1 is a drawing showing a multi-point voice conferencing system 100 of the present invention. System 100 comprises a plurality of user stations, such as stations 104-106, and a speech server 110. User stations 104-106 and speech server 110 are connected to a data network such as the Internet 112.

0019The structure of the user stations are similar. Thus, only one of the stations (for example, station 104) will be described in detail here. Station 104 comprises a desktop computer 114, a display device 116, a microphone 118, two loudspeakers 119 and 120, and a modem 122. Desktop computer 114 contains software (not shown) which provides a connection to Internet 112 using modem 122. A person in station 104 can talk to microphone 118. The speech is then processed by a software 126 of the present invention executing in desktop computer 114. The processed speech is then sent to server 110 via Internet 112. Software 126 can also process speech information received from server 110 and send the output to loudspeakers 119 and 120. Two loudspeakers are used in the present embodiment to generate stereo effects. It should be appreciated that one loudspeaker could be used if no stereo effect is needed.

0020In this embodiment, all speeches are sent by the user stations to speech server 110, which then directs the speeches to their destination. In addition to speeches, lip synching information is also sent and received by the user stations (again routed through server 110).

0021One aspect of the present invention is methods to reduce the bandwidth requirement for speech and lip-synching information transmission. An important factor affecting the performance of system 100 is the speed of data transmission between user stations and the server. Currently, the transmission speed of a modem in a dial-up telephone line is around 30 kilobits per second (kbps). Even when an ISDN (Integrated Services Digital Network) line is used, the transmission speed is about 128 kbps. On the other hand, the transmission of uncompressed speech alone requires a higher bandwidth than can be supported using current telephone lines. If it is necessary to transmit other information (e.g., control data and lip-synching information), the bandwidth requirement is much higher. Consequently, there is a need to reduce the bandwidth requirement.

0022Software 126 contains an encoder and a decoder. Fig. 2A is a block diagram of an encoder 200 in accordance with the present invention. Various blocks of encoder 200 will be discussed in detailed in this specification. Encoder 200 accepts speech input digitized at 8 kHz and a width of 16 bits per sample. The DC component of the digitized speech is removed by a DC removal block 204. Encoder 200 also contains a silence detector 206. When a period of silence is detected, there is no need to transmit speech information. Encoder 200 contains an automatic gain control 210 so as to allow speech having a wide dynamic range to be adequately processed by the system. Encoder 200 contains a voice morpher block 214 for allowing a change of the characteristics of the speech. The speech data then goes to a linear predictive coding (LPC) analysis block 222 to generate a plurality of LPC parameter. The parameters pass through a two-stage vector quantization block 224. The result is delivered to a scalar quantization block 226 and a lip information extraction block 250. The resulting parameters from block 226 are delivered to a multi-pulse excitation parameters generator 228, a robot/whisper excitation generator 230, and a bit stream encoder 232. The output of robot/whisper excitation generator 230 is also delivered to bit stream encoder 232. The output of multi-pulse excitation parameter generator 228 is coupled to a pulse-position coder 236 and a pulse-amplitude coder 238. The outputs of coders 236 and 238 are delivered to bit stream coder 232.

0023The output of lip information extractor 250 is delivered to a lip filter 252, which is connected to a lip information coder 256. The result of lip information coder 256 is sent to bit stream encoder 232.

0024As explained in more detail below, the input speech (digitized at 8 kHz and having a width of 16 bits per sample) can be compressed such that the output of bit stream encoder 232 is approximately 12,800 bits-per-second. This data stream is sent to speech server 110 via the Internet.

0025Fig. 2B is a block diagram of a decoder 300 which can decode bit streams received from speech server 110. Decoder 300 contains a bit stream decoder 304 which is able to recover information from the bits sent by speech server 110. The information is sent to a lip information decoder 306, which generates lip position information to a lip synch program for generating graphics of lips. The information from bit stream decoder 304 is also sent to a LPC parameter decoder 308, a pulse amplitude decoder 310, a pulse location decoder 312, and a whisper/robot excitation decoder 314. The outputs of these decoders are sent to a LPC synthesizer 320 which generates digital speech signals. The digital speech signal is sent to an adaptive post filter 322, which also accepts information from LPC parameter decoder 308. The output of adaptive post filter 322 is sent to an echo filter 324 and then to a bandpass filter 326. The result is a decompressed stereo speech which is transformed into acoustic sound by loudspeakers 119 and 120.

0026Fig. 2C is a schematic diagram of a participant site 350 of the present invention. A participant 352 speak to a microphone 354, which transform the sound signal into electrical signal. Typically, the site contains background noise (e.g., from a radio). The electrical signal is combined with signals from an adaptive echo cancelor 362 in a multimedia personal computer 360. The result is almost echo free speech. This signal is sent to an adaptive silence detection and software automatic gain control (AGC) module 364. The output of this module is sent to a lip-synching and speech codec 366. Codec 366 incorporates the ability to disguise voice (i.e., voice morph). Codec 366 compresses and encodes the speech data, and send the data to speech server 110 through a bidirectional communication link 368.

0027Codec 366 also include software to decode and decompress speech data received from speech server 110. After decoding and decompressing, the data is sent to a wave mixer 370, which also accepts data from an ambient sound generator 372. The signal generated by wave mixer 370 is sent to adaptive echo cancelor 362 and two loudspeakers 376 and 377.

Determination of the Acoustic Characteristics of a User Station

0028When computer 114 in user station 104 is first turned on, the acoustic characteristics of user station 104 need to be determined. This involves the determination of the bulk delay and the acoustic transfer function of user station 104.

0029Fig. 3 is a block diagram of an arrangement capable of measuring the acoustic characteristics of user station 104. Like elements in Figs. 1 and 3 share like reference numerals. This arrangement comprises an audio transmitter block 130 and an audio receiver block 140. Block 130 includes loudspeaker 119 which generates an audio signal in response to the magnitude of an analog electrical signal applied thereto. The analog signal is derived from the content of a digital play buffer 134. Bits in buffer 134 are shifted to a digital-to-analog converter (not shown) at a predetermined rate. Thus, the audio signal generated by loudspeaker 119 is determined by the bits in buffer 134. Audio transmitter block 130 also contains a signal generation block 132 for generating bits for storing into buffer 134 so as to cause loudspeaker 119 to generate audio signals having a specified relationship between amplitude and time.

0030Audio receiver block 140 contains microphone 118 for receiving the audio signals generated by loudspeaker 119. The received audio signals are converted to digital form by an analog-to-digital converter (not shown). The digital information is shifted to a record buffer 142 at a predetermined rate. A signal analysis block 144 analyzes the digital information in buffer 142 to generate a relationship between the amplitude of the received audio signal and time.

0031One aspect of the present invention is a simple method to determine the acoustic characteristics of user station 104. This method involves the following steps: <ul id="ul0001" list-style="none" compact="compact"><li>(1) measure the bulk delay between buffer 134 and buffer 142 through loudspeaker 119;</li><li>(2) measure the transfer function between loudspeaker 119 and microphone 118;</li><li>(3) measure the bulk delay between buffer 134 and buffer 142 through loudspeaker 120; and</li><li>(4) measure the transfer function between loudspeaker 120 and microphone 118.</li></ul>

0032The acoustic characteristics of user station 104 may change over time during a virtual world session. Consequently, the acoustic system needs to be "re-trained" at predetermined times. One aspect of the present invention is a non-intrusive way to re-train the acoustic system.

Measuring the Bulk Delay

0033The measurement involves (i) generating a chirp signal by signal generation block 132, (ii) filling buffer 134 with bits corresponding to the chirp signal, and (iii) transmitting acoustic signal of the chirp signal by loudspeaker 119. The signal received by microphone 118 is then analyzed by signal analysis block 144.

0034The chirp signal is defined as<maths id="math0001" num=""><math display="block"><mrow><mtext mathvariant="italic">c(n)=sin(</mtext><mtext></mtext><mfrac><mrow><mtext>π</mtext></mrow><mrow><mtext mathvariant="italic">N</mtext></mrow></mfrac><mtext> ∗ </mtext><msup><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">2</mtext></mrow></msup><mtext mathvariant="italic">),</mtext></mrow></math><img file="EP0779732A2_D0001.tif" /></maths><i>for n</i>=0,1,...,(<i>N</i>-1), and 0 otherwise. N is the length of the chirp signal.

0035The signal received by the microphone is processed by a matched filter, which is a digital finite impulse response (FIR) filter, with an impulse response of<maths id="math0002" num=""><math display="block"><mrow><mtext mathvariant="italic">h(n)=sin(</mtext><mtext></mtext><mfrac><mrow><mtext>π</mtext></mrow><mrow><mtext mathvariant="italic">N</mtext></mrow></mfrac><mtext> ∗(N-1-</mtext><mtext mathvariant="italic">n</mtext><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><mtext>),</mtext></mrow></math><img file="EP0779732A2_D0002.tif" /></maths><i>for n</i>=0,1,...(<i>N</i>-1), and 0 otherwise. N is the length of the chirp signal defined above.

0036The output of the matched filter is<maths id="math0003" num=""><img file="EP0779732A2_D0003.tif" /></maths> where <i>k(n)</i> is the signal recorded into buffer 142. Let "T" be the instant at which the matched filter output has maximum amplitude, then the bulk delay for the channel is estimated as (T-N). In the current implementation, the value ofN used is 512. The expected bulk delay range is 1,000 to 3,000 samples.

0037A similar bulk delay of the loudspeaker 120 and microphone 118 pair is obtained by the same method.

Measuring the transfer Function

0038The measurement involves generating a white-noise signal by signal generation block 132 and transmitting its associated acoustic signal by loudspeaker 119. Then by using the signal received by microphone 118 and the white noise transmitted, the impulse response of the echo channel (from loudspeaker 119 to the microphone 118) is determined as follows. Let x(n), n = 0,1, ..., (L-1) be the white noise sequence, y(n) be the signal received by the microphone, h(n), n = 0,1,...,(M-1) be the impulse response of the echo channel and B be the bulk delay of the channel, then<maths id="math0004" num=""><img file="EP0779732A2_D0004.tif" /></maths> where <i>w</i>_n is the background noise in the system. A value of M=3 80 is sufficient to perform good echo cancellation. Using the least-squares estimation technique, the impulse response of the channel can be estimated by solving the matrix equation<maths id="math0005" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">R</mtext></mrow><mrow><mtext mathvariant="italic">xx</mtext></mrow></msub><mtext mathvariant="italic"> H</mtext><mtext>=</mtext><msub><mrow><mtext mathvariant="italic">R</mtext></mrow><mrow><mtext mathvariant="italic">xy</mtext></mrow></msub><mtext mathvariant="italic">,</mtext></mrow></math><img file="EP0779732A2_D0005.tif" /></maths> where <i>R</i>_<i>xx</i> is the (M by M) auto-correlation matrix of the white noise, <i>R</i>_<i>xy</i> is an (M by 1) cross-correlation vector and <i>H</i>= [<i>h</i>(<i>0</i>)<i>h</i>(1)... <i>h</i>(<i>M</i> - 1)]^<i>T</i> is the echo filter impulse response vector. <i>R</i>_<i>xx</i> is computed as<maths id="math0006" num=""><img file="EP0779732A2_D0006.tif" /></maths><i>R</i>_<i>xy</i> is computed as<maths id="math0007" num=""><img file="EP0779732A2_D0007.tif" /></maths> Similar calculation is performed to obtain the characteristics of the echo channel between the loudspeaker 120 and the microphone 118 pair. It is preferable to use a value of L = 10*M to obtain accurate estimate of echo channel filter characteristics.

Quick training

0039Quick training is performed if the user perceives that the echo cancellation is not yielding satisfactory results or the system detects the same. Quick training can be performed to adjust the bulk-delay and/or the echo channel gain of user station 104, changed as a consequence of altering the speaker volume control. It can also detect if the full-training is needed.

0040The quick training involves (i) loudspeaker 119 transmitting an acoustic signal <i>x(n) =G*h</i>(<i>M</i> - 1 - <i>n</i>) <i>for n</i> = 0,1,...,(<i>M</i> - 1) <i>and</i> 0 otherwise, and (ii) microphone 188 receiving the acoustic signal, y(n). The value of G is chosen to be<maths id="math0008" num=""><img file="EP0779732A2_D0008.tif" /></maths> The symbol ^T is used to designate the instant at which this signal (i.e., y(n)) peaks. First it is determined if full training is needed. If the echo channel characteristics have not deviated much from the previous calculations, the shape of the received signal (i.e., y(n)) around it peak (i.e., around <i>n = T</i>) will be similar to that of the echo channel auto-correlation function obtained using the relation<maths id="math0009" num=""><img file="EP0779732A2_D0009.tif" /></maths> around k=0. Therefore, if<maths id="math0010" num=""><img file="EP0779732A2_D0010.tif" /></maths> is greater than a certain threshold, then it will be determined that the echo path impulse response has changed substantially and a full training is performed. The value of g is obtained using the equation where<maths id="math0011" num=""><img file="EP0779732A2_D0011.tif" /></maths> When full training is not required, the bulk delay and gain of the echo filter is updated to new values, (T-M) and <i>h</i>_<i>new</i>(<i>n</i>) = <i>g</i>^<i>*</i><i>h</i>(<i>n</i>), <i>for</i> 0≤<i>n</i>&lt;(<i>M</i>-1).

0041The length and strength of the signal used for re-training is less than that of the signals used during full training. Thus, the quick training is generally not noticeable by people in user station 104. The quick training is performed for both the echo channels.

Adaptive Echo Cancellation

0042Let <i>h</i>_<i>1</i>(<i>n</i>), 0≤<i>n</i>&lt; <i>M,</i> be the impulse response of the echo path from left speaker to the microphone and <i>h</i>_<i>r</i>(<i>n</i>), 0 ≤<i>n&lt; M,</i> be the impulse response of the echo path from left speaker to the microphone. Furthermore, let <i>B</i>_<i>1</i> and <i>B</i>_<i>r</i> be the respective bulk delays. Let, <i>x</i>₁(<i>n</i>) and <i>x</i>_<i>r</i>(<i>n</i>) be the speech samples being fed to the left and right speakers. Then, the echo cancellation is performed by subtracting<maths id="math0012" num=""><img file="EP0779732A2_D0012.tif" /></maths> from the signal recorded by the microphone, <i>y</i>_<i>n</i>. This computation can be implemented using the fast Fourier Transform algorithm or directly.

Adaptive Silence Detection

0043Due to non-linearity in the transducers (speakers and microphone), it is impossible to achieve perfect echo cancellation. This residual echo can be perceived by the listeners when the speaker is not speaking. Therefore, to eliminate echo when the near-end speech is absent, silence detection is performed and no speech packets are transmitted during the silence periods (i.e., when the near-end speaker is not speaking). By not transmitting speech information during the period of time when there is a silence, the bandwidth requirement of the system is further reduced. This additional bandwidth can be used to transmit other information (e.g., graphics and/or control information).

0044In a typical environment, silence is not the same as no measurable audio signal. This is because there is always some background noise and (some times) residual echo. Thus, microphone 118 generally receives some audio signal, even when there is no speech. The equation of audio input to microphone 118 is given by:<maths id="math0013" num=""><math display="block"><mrow><msub><mrow><mtext>A</mtext></mrow><mrow><mtext>n</mtext></mrow></msub><msub><mrow><mtext> = S</mtext></mrow><mrow><mtext>n</mtext></mrow></msub><msub><mrow><mtext> + E</mtext></mrow><mrow><mtext>n</mtext></mrow></msub><msub><mrow><mtext> + B</mtext></mrow><mrow><mtext>n</mtext></mrow></msub></mrow></math><img file="EP0779732A2_D0013.tif" /></maths> where A_n is the amplitude of sound received by microphone 118, S_n is the contribution due to speech, E_n is the contribution due to the residual echo, and B_n is the contribution due to background noise.

0045The present invention makes use of the fact that human speech contains periods of silence. Thus, audio signal corresponds to background noise and echo during this periods.

0046In one embodiment of the present invention, microphone 118 monitors the short-term signal energy (computed every 20 msecs using a block of 20 msec signal) in a time period of one second. The segment having the lowest energy is assumed to be in a period of silence (i.e., S_n = E_n = 0). Using the echo signal computed as earlier, the expected echo energy for a given time period can be easily computed. The residual echo energy for the given period is estimated to be equal to 0.1 times the expected echo energy. This assumes a conservative echo cancellation of 10 dB. Since S_n, E_n, and B_n are generated independently, the energy in the signal A_n can be assumed to be equal to the sum of energy in each of the three component signals. In other words, E_s = E_A - E_E - E_B, where E_s is the speech energy, E_A is the energy in recorded speech, E_E is the residual echo energy and E_B is the background noise energy. A recorded segment of data is classified as silence if E_s is found to be below a certain threshold. Otherwise, the recorded speech is compressed and the compressed information is transmitted to the server.

Software Automatic Gain Control

0047The PC microphone is very sensitive to the distance between the speaker's mouth and the microphone. Automatic gain control (AGC) module is used to reduce this sensitivity. Most multi-media PCs provide this functionality using hardware solution. Need for the software AGC arises because use of hardware AGC introduces non-linearity in the data which can affect the performance of echo and cancellation. The software AGC is implemented as follows: <ul id="ul0002" list-style="none" compact="compact"><li>1. Initially set <i>currentGain</i> = 1.0.</li><li>2. Once every 60 msecs compute the root mean squared (rms) value using the relation<maths id="math0014" num=""><img file="EP0779732A2_D0014.tif" /></maths> where <i>x</i>_<i>n</i> is echo free (i.e., echo removed) non-silence input speech data.</li><li>3. Compute target AGC gain, <i>targetGain</i> using the relation<maths id="math0015" num=""><math display="block"><mrow><mtext mathvariant="italic">targetGain</mtext><mtext> = min (</mtext><mtext mathvariant="italic">targetGain</mtext><mtext>, </mtext><mfrac><mrow><mtext>4096</mtext></mrow><mrow><mtext mathvariant="italic">rms</mtext></mrow></mfrac><mtext> )</mtext></mrow></math><img file="EP0779732A2_D0015.tif" /></maths></li><li>4. set <i>n=0</i> and do the following <i>N</i> times <ul id="ul0003" list-style="none" compact="compact"><li><i>x</i><img file="EP0779732A2_D0016.tif" /><i> currentGain*x</i>_<i>n</i></li><li><i>currentGain</i>←0.95*<i>currentGain</i> + 0.05*<i>targetGain</i></li><li><i>n</i>←<i>n</i> + 1</li></ul></li></ul>

An Efficient Speech Coding Scheme for Voice Bridging Application

0048In a multi-point voice conferencing (i.e., voice bridging) system, each participant speaks into his microphone connected to his multi-media computer or work station. The computer performs data compression to enable efficient data transmission using modem to the server. The server collects the speech packets from each participant. Using the knowledge about the position of the participants and the direction of their faces, the server decides which speakers (a maximum of two), if any, should be heard by each listener. In doing so, the server should be able to combine bit-streams from two speakers into one bit-stream, so that this bit-stream can be transmitted on the modem. The multi-media system at the client side will use this bit-stream to synthesize the voice of two participants, combine them and generate a composite signal which is played out through the speakers along with the ambient sound. The unique feature of the speech coding technique presented here is that it is designed to work as a dual rate coder. That is the most important parameters of the speech coder output are coded at a rate of 6,400 bits per second. Additional information, which can be used to improve the quality of synthesized speech, is coded using another 6,400 bits per second. This way, the coder can function as a high quality speech compression system at 12,800 bit per second or as a communication quality speech compression system at 6,400 bits per second. When we need to transmit the voice data about two speakers, the server allocates 6,400 bits per second (i.e., half-rate) for each speaker's voice. However, when only one person's speech information needs to be transmitted to a client, full bandwidth is allocated for one speaker's voice data; thus permitting higher quality speech synthesis. The ability to take a 12,800 bits per second bit-stream and convert it easily into a half-rate bit-stream (i.e., 6,400 bits per sec bit-stream) can also be exploited when more control or graphics information has to be transmitted along with the speech data from the client to the server.

0049The algorithm allows for the client to make the decision for the server as to which of the arbitrary number of voice streams that could be sent to the client are actually chosen. Since the client knows the location of each of the speakers, it can choose to take into account distance between the listener and speakers as well as direction of sight of all avatars, objects that might be in the "path of the sound," even allow for different sound mediums (i.e. underwater, on a windy hill). The priority decision process is continually re-evaluated, and when this re-evaluation occurs fast enough, it can approximate to having many more concurrent streams between server and client than actually exist.

0050The algorithm allows each client to make such a decision independently of the others, hence allowing a client to provide the best audio experience for the user, taking into account the machine and bandwidth limitations of that particular client.

LPC Analysis

0051The speech compression system implemented here is based on the general principle of Linear Prediction Coding (LPC) of speech using multi-pulse excitation signals described in B. S. Atal and J. R. Remde, "A new model for LPC excitation for producing natural sounding speech at low bit-rates," <i>Proc. Int. Conf</i>. <i>On Acoustics Speech and Signal Processing,</i> Paris, France, 1982, pp. 614-617. The speech signal, <i>S</i>_<i>n</i><i> ,</i> is modeled as follows,<maths id="math0016" num=""><img file="EP0779732A2_D0017.tif" /></maths> as the output of a digital time-varying infinite impulse response filter excited by a sequence of irregularly spaced pulses of different amplitudes, where, <i>a</i>_<i>k</i>, 0&lt;<i>k</i>≤<i>M</i>, are the <i>M</i>^<i>th</i> order LPC filter coefficients. The filter order is typically about 10. <ul id="ul0004" list-style="none"><li><i>p</i>_<i>n</i> represents multi-pulse sequence, and</li><li><i>W</i>_<i>n</i> represents the random noise sequence.</li></ul>

0052The time varying filter coefficients are obtained using LPC analysis as described in S. Shankar Narayan and J. P. Burg, "Spectral Estimation of quasiperiodic data", <i>IEEE Transactions on Acoustics Speech and Signal Processing,</i> March 1990, pp.512-518.-554-II-557. Prior to LPC analysis, the speech data is pre-emphasized using a first order filter of the form <i>P</i>(<i>z</i>)=(1-0.875<i>z</i>^-1). The coefficient estimation is performed once every 5 msecs. However, for the purpose of speech coding only every fourth parameter set are used. The higher rate of computation is for the purpose of lip-synch parameter estimation, which will be discussed later. Typically 10-32 pulses are used to represent the multi-pulse excitation function. The synthesized speech quality depends on the number of pulses used (more the better). However, the amount of data compression achieved also depends on the number of pulses used to represent the excitation function (fewer the better). In order to transmit this information over the modern, the LPC parameters are quantized using a two-stage vector quantizer followed by a scalar quantizer to generate a 38-bit representation of the LPC filter. This procedure is discussed next.

Vector and Scalar Quantization

0053<ul id="ul0005" list-style="none" compact="compact"><li>1. Convert the LPC filter coefficients to reflection coefficients using the transformation described in J. Markel and A. Gray, Linear Prediction of Speech, Springer-Verlag, 1976. Reflection coefficients are another representation of LPC filter coefficients. The transformation from one set of parameters to the other is loss less and invertible. Let <i>k</i>_<i>i</i><i>,0&lt;i</i>≤M, be the M reflection coefficients corresponding to the computed LPC filter coefficients.</li><li>2. Convert the first four reflection coefficients to log-area-ratio (lar) functions using the method described in J. Markel and A. Gray, Linear Prediction of Speech, Springer-Verlag, 1976. Use the transformation<maths id="math0017" num=""><img file="EP0779732A2_D0018.tif" /></maths> where In[.] stands for natural logarithm operation.</li><li>3. The 10 parameters <i>lar</i>_<i>1</i>,<i>···,lar</i>_<i>4</i><i>,k</i>_<i>5</i><i>,···,k</i>_<i>10</i> are quantized using a 64-codebook vector quantizer. The procedure for codebook generation and implementation of vector quantizer is described in Y. Linde, A. Buzo and R. M. Gray, "An Algorithm for Vector Quantizer Design", <i>IEEE Trans. On Communications,</i> Jan 1980, pp. 84-95; R. M. Gray, "Vector Quantization," <i>IEEE ASSP Magazine,</i> April 1984, pp. 4-29. The vector quantizer accepts the vector <i>X=[lar</i>₁,···,<i>lar</i>₄,<i>k</i>₅,···,<i>k</i>₁₀]^<i>t</i>, searches through a codebook with 64 entries, finds the output sequence best matching the input vector in the mean squared sense and outputs a 6-bit codeword index <i>il</i>_<i>opt</i><i>.</i> The decoder can look up the corresponding codeword in its codebook and obtain the sequence <i>qX</i>_<i>1</i><i>=</i>[<i>lar'</i>₁<i>,···,lar'</i>₄<i>,k'</i>₅<i>,···,k'</i>₁₀]^<i>t</i> as a 6-bit approximation to the given input vector.</li><li>4. A difference vector <i>dX</i>₁=<i>X</i>-<i>qX</i>₁ is formed and is vector quantized again using a 64-codebook vector quantizer, generating codeword index <i>i2</i>_opt and the sequence <i>qX</i>₂= <i>[lar''</i>₁<i>,···,lar''</i>₄<i>,k''</i>₅<i>,···,k''</i>₁₀]^<i>t</i></li><li>5. A difference vector <i>dX</i>₂=<i>dX</i>₁-<i>q</i> is formed next. Now each component of this vector is quantized individually (i.e., using scalar quantizers). The number of bits used to quantize each components are [4, 3, 3, 3, 3, 2, 2, 2, 2, 2]. This 26-bit information along with the 2 6-bit VQ codes <i>i1</i>_<i>opt</i> and <i>i2</i>_<i>opt</i> forms the 38-bit representation of the LPC filter and this information will be a part of the packet of information to be transmitted as encoded speech information. Let the quantized values of the vector <i>qX</i>_<i>2</i><i> be</i> defined as    <i>qX</i>_<i>3</i><i>= [lar</i>'''₁,···,<i>lar'''</i>₄,<i>k'''</i>₅,···,<i>k'''</i>₁₀]^<i>t</i>, then, the decoded value of the vector X as X̂= <i>qX</i>₁ + <i>qX</i>₂ +</li><li>6. From this X̂ vector, the quantized LPC filter coefficients can be obtained by performing the needed transformations (i.e., log-area-ratio to reflection coefficients and reflection coefficients to LPC filter coefficients). The sequence â_k, 0 &lt; <i>k</i> ≤ <i>M</i>, is used to designate the resulting filter coefficients.</li></ul>

Generation of multi-pulse excitation parameter

0054Using an analysis by synthesis approach, the multi-pulse excitation parameters (i.e., pulse positions and amplitudes) are obtained as follows: Let <i>S</i>_<i>n</i> represent speech data in a 20 msec frame and let <i>â</i>_<i>n</i>, 0&lt;<i>n</i>≤<i>M</i> be the LPC filter coefficients obtained for this frame of speech. Compute the residual signal, <i>r</i>_<i>n</i> , using the relationship,<maths id="math0018" num=""><img file="EP0779732A2_D0019.tif" /></maths>

0055Compute impulse response of the perceptual weighting filter using the relationship <i>h</i>_<i>n</i><i>=0 for n&lt;0</i><i>h</i>_<i>0</i><i>=</i> 1 and<maths id="math0019" num=""><img file="EP0779732A2_D0020.tif" /></maths> for 0&lt;<i>n</i>&lt;<i>L</i> , where λ=0.85 and L is chosen as 40.

0056Next form two sequences<maths id="math0020" num=""><img file="EP0779732A2_D0021.tif" /></maths> and<maths id="math0021" num=""><img file="EP0779732A2_D0022.tif" /></maths> for 0<i>≤n&lt;(L - 1)</i><maths id="math0022" num=""><img file="EP0779732A2_D0023.tif" /></maths> for <i>(L -</i> 1<i>)≤n&lt;(N-L)</i><maths id="math0023" num=""><img file="EP0779732A2_D0024.tif" /></maths><i>for (N-L)≤n&lt;(N+L-1)</i> In other words the sequence <i>p</i>_<i>n</i> is obtained by convolving the sequence <i>h</i>_<i>n</i> with itself and the sequence <i>q</i>_<i>n</i> is obtained by convolving the residual sequence, <i>r</i>_<i>n</i><i>, with p</i>_<i>n</i><i>.</i> Let <i>q'</i>_<i>n</i> = <i>q</i>_<i>n</i>

0057The location of an excitation pulse is chosen to be the value of <i>n</i> for which <i>q'</i>_<i>n</i> is maximum. Let this location be <i>I</i>_<i>i</i> , then the height of the pulse, <i>h</i>_<i>i</i> is obtained using the relationship<maths id="math0024" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">h</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub><mtext mathvariant="italic">=q'</mtext><msub><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">ℓ</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub></mrow></msub><msub><mrow><mtext> / p</mtext></mrow><mrow><mtext>(</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">L</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext>-1)</mtext></mrow></msub></mrow></math><img file="EP0779732A2_D0025.tif" /></maths>

0058After each pulse information (i.e., location and height) is obtained, the sequence <i>q'</i>_<i>n</i> is modified using the relation<maths id="math0025" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">q'</mtext></mrow><mrow><mtext mathvariant="italic">n</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">←q'</mtext></mrow><mrow><mtext mathvariant="italic">n</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">-h</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub><msub><mrow><mtext> p</mtext></mrow><mrow><mtext>(</mtext><mtext mathvariant="italic">n+L</mtext><mtext>-1-ℓ)</mtext></mrow></msub></mrow></math><img file="EP0779732A2_D0026.tif" /></maths>

0059This sequential procedure is continued until the desired number of excitation pulses are determined. Using the pulse locations thus obtained, the optimal height information is then obtained by solving the matrix equation <i>S</i>_<i>xx</i><i> h=S</i>_<i>xy</i><i>,</i> where <i>S</i>_<i>xx</i> is an (M x M) matrix whose (<i>i,j</i>)^<i>th</i> element is equal to <i>L</i>-1+|<i>l</i>_<i>i</i><i>-l</i>_<i>j</i>|, <i>S</i>_<i>xy</i> is an (Mx1) vector, whose <i>i</i>^<i>th</i> element is equal to <i>q</i>_{<i>t</i><sub2><i>i</i></sub2>} and h is an (M x 1) vector of excitation impulse heights.

0060In an embodiment of the present system, 12 excitation pulses are first determined sequentially for every 20 msec of speech data and then the pulse heights are optimized. 38-bits of LPC coefficient information along with the information about these 12 excitation pulses (i.e., height and amplitude) can be used as transmission parameters of a speech coding system with a bit-rate of 6,400 bits per second. The contribution from these 12 pulses are subtracted from the sequence <i>q</i>_<i>n</i> and an additional 14 excitation pulses are obtained using the same approach. In essence, 26 multi-pulse excitation pulses are determined in two stages. 38-bits of LPC coefficient information along with the information about these 26 excitation pulses (i.e., height and amplitude) can be used as transmission parameters of a speech coding system with a bit-rate of 11,600 bits per second. In voice bridging application, the client system (i.e., multi-media computer station) in addition to sending the server this 11,600 bits per second bit stream, also sends an additional information of (1,200 bit per second bitstream) as to which 12 pulses should be chosen amongst these 26 pulses if the server wants to generate 6,400 bits per second bitstream data. Thus the bandwidth required to send speech information to the server is 12,800 bit per second, while the server sends the compressed speech data to the client either at 11,600 bits per second (in case of one speaker) or 12,800 (2x6,400) bits per second (in case of two speakers). The encoding of the excitation pulse information is now described.

Pulse Position Coder

0061Positions of 26 excitation pulses computed for each 20 msec segments of speech have to be coded efficiently in order to accomplish low-bit rate speech coding. 20 msec of speech corresponds to 160 samples of speech. Each pulse can be in one of the 160 locations, but no two pulse can have the same location. Combinatorial coding scheme presented in M. Berouti, <i>et. al.</i> "Efficient Computation and Encoding of the multi-pulse excitation for LPC," <i>Proc. Int. Conf. On Acoustics Speech and Signal Processing</i>, San Diego, CA, 1984, pp. 10.1.1-10.1.4. is used to code this information using 102 bits. The encoder uses the combinatorial coding scheme to code the information needed by the server to select 12 pulses out ofthese 26 pulses (²⁶<i>C</i>₁₂ combinations or 24-bits) in order to generate half-rate bit stream. The same strategy is used in coding the positions of 12 pulses in the case of half-rate coder. Thus a total of 114 bits are needed to code the pulse location information for every 20 msecs.

Pulse Amplitude Coder

0062Amplitudes of 26 excitation pulses computed for each 20 msec segments of speech have to be coded efficiently in order to accomplish low-bit rate speech coding. The pulse amplitudes are coded efficiently by normalizing them by the root mean-square (rms) pulse amplitude. After scaling, the pulse amplitudes are quantized using an 8-level gaussian quantizer described in T. Max, "Quantizing for minimum distortion," <i>IRE Trans. On Information Theory,</i> vol. 16, 1970, pp. 7-12. The rms pulse amplitude which is optimized to minimize the quantization noise is coded as a transmission parameter using 6 bits. Thus a total of 84 bits are needed to code the pulse amplitude information for every 20 msecs.

An Efficient Lip Synching Method

0063We have observed that the lip positions in human beings can be determined to a large extent by the first two peaks, known as formant frequencies, of the short-term spectra of the speech, and the short-term energy of the speech signal. Specifically, the separation between the first two formant frequencies is proportional to the width of the lip. The lower lip height tends to be proportional to the value of the first formant frequency. Finally the upper lip height and the lip rounding phenomenon (i.e., both the lips moving away from closed mouth position) is inversely proportional to the sum of the first two formant frequencies. In other words, both the first and second formant frequencies have to reduce to produce lip rounding. These estimates may not be identical to the real lip positions of the speaker, but when used for facial animation they are expected to provide very realistic effects. The method for computing lip positions comprises the following steps:

Lip Information Extractor

0064<ul id="ul0006" list-style="none" compact="compact"><li>1. The LPC parameters estimated for the purpose of speech encoding (as discussed earlier) can be employed to obtain short-term spectral information in the speech data. However, the computational requirement for estimating the formant frequencies from the knowledge about the LPC filter information would be high. In one embodiment of the present invention, formant frequencies corresponding to each entry of the first 64-codeword VQ codebook is pre-computed in non-real-time and stored. Therefore, when the first stage vector quantization is performed on the LPC parameters, an estimate of formant frequencies is also obtained. The symbols <i>f</i>₁ and <i>f</i>_<i>2</i> are used as the first two formant frequencies for a given segment of speech. Furthermore, the symbol <i>E</i> is used as the signal energy for the frame in decibels (dB). Given the two formant frequencies and the signal energy and assuming a nominal lip width of size 1 unit, the following heuristics is used to get preliminary estimates of the lip positions:</li><li><b>2. Filtering of signal energy information:</b> The signal energy, <i>E</i>, computed for a frame of speech includes the background noise energy also. The effect of background noise level should be eliminated before using this information for the calculation of lip positions. The following algorithm is used to modify the computed signal energy: Initially set <i>AverageSignalLevel</i>=0 Once every 5 msecs, update this using the relation,    <i>AverageSignalLevel=</i>0.999*<i>AverageSignalLevel+</i>0.001<i>*E</i> The signal energy, <i>E</i>, is updated as    <i>E←E-</i>(<i>AverageSignalLevel-20</i>) Set the value of <i>E</i> to 0 if less than 0 and equal to 40 dB, if greater than 40.</li><li>3. <b>Lower Lip Height Computation:</b> If <i>f</i>_<i>1</i> is in the range (300-800 Hz), compute lower lip height using the relation    <i>lowerLipHeight=1.5 -cos(π(f</i>_<i>1</i>-250)/500)<i>∗</i>(<i>E/80</i>) Otherwise, lower lip height is computed using the relation    <i>lowerLipHeight =E/200</i></li><li>4. <b>Lip Width Computation:</b> The heuristics here is not to change the lip width if <i>f</i>_<i>2</i> is in the region 1000-1800 Hz range. If <i>f</i>_<i>2</i> is in the range 700-1000 Hz range, the lip width is decreased using the relation    <i>lipWidth</i> = 1-[1+cos(π*(<i>f</i>₂-700)/300)]*<i>E</i>/133 If <i>f</i>₂ is in the range 1800-2500 Hz range, the lip width is increased using the relation    <i>lipWidth</i>=1+[1+cos(π*(<i>f</i>₂-1800)/700)]*<i>E</i>/200</li><li>5. <b>Lip Rounding:</b> This is found to happen when <i>f</i>₁ + <i>f</i>₂&lt;1600 , 250&lt; <i>f</i>₁&lt; 800 and 700&lt; <i>f</i>₂&lt; 2500 . Then    <i>upperLipHeight=</i>1.2<i>*E*</i>[1.1<i>+cos{π*(f</i>_<i>1</i><i> + f</i>_<i>2</i>-800)/800}]/40 and the lower lip height is modified using the equation    <i>lowerLipHeight=lowerLipHeight+</i>0.6*<i>E</i>*[1.1+cos{π*(<i>f</i>₁+<i>f</i>₂ -800)/800}]/40 If lip rounding does not occur, the upper lip height depends mildly on the signal energy and is calculated as    <i>upperLipHeight=E</i>/400<i>.</i></li></ul>

Lip Filtering

0065A lip position smoothing filter is used in the present embodiment. The instantaneous lip positions so obtained every 5 msecs (or 200 times a second) tend to be noisy. Furthermore, most visual displays are refreshed at a much lower rate (typically 6 to 30 times per second). A 31-point finite impulse response (FIR) low-pass filter with a cut-off frequency of 6.25 Hz is applied to each of the lip parameters to obtain smooth estimates of the parameters at the desired rate. In the current implementation, the smoothed lip parameters are computed 16.67 times per second.

Lip Information Encoding

0066The lip position variables are highly correlated. For example, when the mouth is widened, it is likely that the lip heights tend to be small. On the other hand, when mouth is rounded, the lip width is small and lip heights are large. This information is exploited in coding the lip position using a very few number of bits. In the present invention, 8 bits per 60 msec are used to encode all the lip position variables. The lower lip height information is coded using a 16-level quantizer and it can take the following values: <tables id="tabl0001" num="0001"><table frame="all"><tgroup cols="2" colsep="1" rowsep="0"><colspec colnum="1" colname="col1" colwidth="78.75mm" /><colspec colnum="2" colname="col2" colwidth="78.75mm" /><thead valign="top"><row rowsep="1"><entry namest="col1" nameend="col1" align="left">Code</entry><entry namest="col2" nameend="col2" align="left">(Lower Lip Height * 5)</entry></row></thead><tbody valign="top"><row><entry namest="col1" nameend="col1" align="left">0</entry><entry namest="col2" nameend="col2" align="char" char=".">0.005</entry></row><row><entry namest="col1" nameend="col1" align="left">1</entry><entry namest="col2" nameend="col2" align="char" char=".">0.070</entry></row><row><entry namest="col1" nameend="col1" align="left">2</entry><entry namest="col2" nameend="col2" align="char" char=".">0.141</entry></row><row><entry namest="col1" nameend="col1" align="left">3</entry><entry namest="col2" nameend="col2" align="char" char=".">0.199</entry></row><row><entry namest="col1" nameend="col1" align="left">4</entry><entry namest="col2" nameend="col2" align="char" char=".">0.252</entry></row><row><entry namest="col1" nameend="col1" align="left">5</entry><entry namest="col2" nameend="col2" align="char" char=".">0.306</entry></row><row><entry namest="col1" nameend="col1" align="left">6</entry><entry namest="col2" nameend="col2" align="char" char=".">0.377</entry></row><row><entry namest="col1" nameend="col1" align="left">7</entry><entry namest="col2" nameend="col2" align="char" char=".">0.458</entry></row><row><entry namest="col1" nameend="col1" align="left">8</entry><entry namest="col2" nameend="col2" align="char" char=".">0.554</entry></row><row><entry namest="col1" nameend="col1" align="left">9</entry><entry namest="col2" nameend="col2" align="char" char=".">0.653</entry></row><row><entry namest="col1" nameend="col1" align="left">10</entry><entry namest="col2" nameend="col2" align="char" char=".">0.752</entry></row><row><entry namest="col1" nameend="col1" align="left">11</entry><entry namest="col2" nameend="col2" align="char" char=".">0.876</entry></row><row><entry namest="col1" nameend="col1" align="left">12</entry><entry namest="col2" nameend="col2" align="char" char=".">1.034</entry></row><row><entry namest="col1" nameend="col1" align="left">13</entry><entry namest="col2" nameend="col2" align="char" char=".">1.213</entry></row><row><entry namest="col1" nameend="col1" align="left">14</entry><entry namest="col2" nameend="col2" align="char" char=".">1.468</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="left">15</entry><entry namest="col2" nameend="col2" align="char" char=".">1.825</entry></row></tbody></tgroup></table></tables>

0067As the upper lip height information and the lip width are highly correlated, they are jointly quantized using a 16 level quantizer and can take the following values: <tables id="tabl0002" num="0002"><table frame="all"><tgroup cols="3" colsep="1" rowsep="0"><colspec colnum="1" colname="col1" colwidth="52.50mm" /><colspec colnum="2" colname="col2" colwidth="52.50mm" /><colspec colnum="3" colname="col3" colwidth="52.50mm" /><thead valign="top"><row rowsep="1"><entry namest="col1" nameend="col1" align="left">Code</entry><entry namest="col2" nameend="col2" align="left">5*UpperLipHeight</entry><entry namest="col3" nameend="col3" align="left">LipWidth</entry></row></thead><tbody valign="top"><row><entry namest="col1" nameend="col1" align="left">0</entry><entry namest="col2" nameend="col2" align="char" char=".">0.017</entry><entry namest="col3" nameend="col3" align="char" char=".">1.002</entry></row><row><entry namest="col1" nameend="col1" align="left">1</entry><entry namest="col2" nameend="col2" align="char" char=".">0.053</entry><entry namest="col3" nameend="col3" align="char" char=".">1.005</entry></row><row><entry namest="col1" nameend="col1" align="left">2</entry><entry namest="col2" nameend="col2" align="char" char=".">0.189</entry><entry namest="col3" nameend="col3" align="char" char=".">0.986</entry></row><row><entry namest="col1" nameend="col1" align="left">3</entry><entry namest="col2" nameend="col2" align="char" char=".">0.089</entry><entry namest="col3" nameend="col3" align="char" char=".">1.002</entry></row><row><entry namest="col1" nameend="col1" align="left">4</entry><entry namest="col2" nameend="col2" align="char" char=".">0.532</entry><entry namest="col3" nameend="col3" align="char" char=".">0.853</entry></row><row><entry namest="col1" nameend="col1" align="left">5</entry><entry namest="col2" nameend="col2" align="char" char=".">0.347</entry><entry namest="col3" nameend="col3" align="char" char=".">0.943</entry></row><row><entry namest="col1" nameend="col1" align="left">6</entry><entry namest="col2" nameend="col2" align="char" char=".">0.743</entry><entry namest="col3" nameend="col3" align="char" char=".">0.778</entry></row><row><entry namest="col1" nameend="col1" align="left">7</entry><entry namest="col2" nameend="col2" align="char" char=".">0.839</entry><entry namest="col3" nameend="col3" align="char" char=".">0.728</entry></row><row><entry namest="col1" nameend="col1" align="left">8</entry><entry namest="col2" nameend="col2" align="char" char=".">0.046</entry><entry namest="col3" nameend="col3" align="char" char=".">1.040</entry></row><row><entry namest="col1" nameend="col1" align="left">9</entry><entry namest="col2" nameend="col2" align="char" char=".">0.076</entry><entry namest="col3" nameend="col3" align="char" char=".">1.038</entry></row><row><entry namest="col1" nameend="col1" align="left">10</entry><entry namest="col2" nameend="col2" align="char" char=".">0.055</entry><entry namest="col3" nameend="col3" align="char" char=".">1.082</entry></row><row><entry namest="col1" nameend="col1" align="left">11</entry><entry namest="col2" nameend="col2" align="char" char=".">0.101</entry><entry namest="col3" nameend="col3" align="char" char=".">1.081</entry></row><row><entry namest="col1" nameend="col1" align="left">12</entry><entry namest="col2" nameend="col2" align="char" char=".">0.065</entry><entry namest="col3" nameend="col3" align="char" char=".">1.120</entry></row><row><entry namest="col1" nameend="col1" align="left">13</entry><entry namest="col2" nameend="col2" align="char" char=".">0.074</entry><entry namest="col3" nameend="col3" align="char" char=".">1.155</entry></row><row><entry namest="col1" nameend="col1" align="left">14</entry><entry namest="col2" nameend="col2" align="char" char=".">0.082</entry><entry namest="col3" nameend="col3" align="char" char=".">1.187</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="left">15</entry><entry namest="col2" nameend="col2" align="char" char=".">0.093</entry><entry namest="col3" nameend="col3" align="char" char=".">1.225</entry></row></tbody></tgroup></table></tables> Thus the lip position information is coded using only 8 bits.

Robot/Whisper Excitation Generator

0068As pointed out earlier, the speech signal can be modeled as the output of a time-varying digital filter (i.e., LPC filter) excited by either random noise sequence or an impulse pulse train. Typically, when the spoken sound is a fricative (like sounds s, SH, f), the filter is excited by random noise. On the other hand, when vowels are spoken, the filter is excited by a quasi-periodic signal with a period corresponding to the pitch of the speaker. The filter excitation signal can be altered to accomplish the task of voice morphing. In the present invention, morphing involves modifying the excitation function parameters to produce the specific type of voice disguising and modification.

0069A whisper speech is produced when there is no vocal cord vibration, which translates to no periodic pulse excitation in the case of LPC synthesizers (i.e., using only random noise for exciting the LPC filter). If it is desirable to generate a whisper, the excitation signal is changed to a random noise. The energy of the random noise is adjusted so as to be proportional to the actual energy of the speech.

0070Robotic speech is produced when the pitch of the human speaker tends towards monotone (i.e., pitch changes very little during their talk). In the context of LPC synthesis, this translates to using a periodic pulse excitation function, whose period changes very little. The energy of these impulses should be adjusted such that the energy of the synthesized speech is equal to that of the original speech. The periodicity of the robotic speech is specified by the user. To reduce the buzz in the synthesized speech, a low frequency jitter is added to the periodicity information in the case of robotic speech.

Voice Morpher

0071Another type of voice morphing implemented in the system is that of altering the pitch of the speaker. This way, a male voice can be made to sound more like a female, and vice versa. The voice morphing is accomplished in two stages. Suppose the pitch frequency is to be increased by a factor <i>r.</i> First, the sampling frequency of the speech data is decreased by the same pitch change factor <i>r</i> using speech interpolation/decimation technique. This also changes the duration of the speech samples (i.e., decreases the speech duration by a factor of <i>r</i>). In order to keep the duration of the pitch altered speech same as that of the original speech, time scale modification of the speech is performed using the technique described in Werner Verhelst, and Marc Roelands, "An overlapadd technique based on waveform similarity (WSOLA) for high quality time-scale modification speech," <i>Proc. Int. Conf</i>. <i>On Acoustics Speech and Signal Processing,</i> Minneapolis, 1993, pp. II-554-II-557. This type of voice morphing is performed on the speech data prior to performing speech analysis at the encoder.

Bitstream Encoder

0072The bitstream encoder accepts as input the various pieces of encoding information produced by the analyzer and pack them into a 96 byte packet, to be sent to the server once every 60 msecs. It should however be noted that the speech analysis is performed once every 20 msecs. Therefore, the bit-stream encoder uses three sets of analysis data to make one voice packet. The following set of parameters computed every 20 msec and are included in each voice packet: <ul id="ul0007" list-style="none" compact="compact"><li>1. VQ codeword <i>i</i>1_<i>opt</i> (6-bits)</li><li>2. VQ codeword <i>i</i>2_<i>opt</i> (6-bits)</li><li>3. 10 residual 1pc filter coefficients (26-bits)</li><li>4. rms pulse amplitude code (6-bits)</li><li>5. 26 pulse amplitude codes (78-bits)</li><li>6. pulse location code (114 bits)</li><li>7. Lip position information (8-bits per 60 msecs)</li><li>8. Speech type code (i.e., whether it is whisper, normal speech or robotic sound).</li></ul>

Decoder Implementation

0073The bitstream decoder accepts as input the voice packet set from the server and decodes them into various parameters to be used by the decoder to and implement the LPC synthesizer function to get synthesized speech. The synthesizer is implemented using the following difference function:<maths id="math0026" num=""><img file="EP0779732A2_D0027.tif" /></maths> where <i>â</i>_<i>k</i> are the decoded LPC filter coefficients of order <i>M</i>, <i>S</i>_<i>n</i> are synthesized speech samples and <i>P</i>_<i>n</i> are decoded excitation pulses.

Adaptive Post Filter, Distance and Echo Filter, and Bandpass Filter

0074Adaptive Post-filtering is discussed in J.H. Chen and A. Gersho, "Real-Time Vector APC Speech Coding at 4800 bps with adaptive post-filtering," <i>Proc. Int. Conf. On Acoustics Speech and Signal Processing</i> Dallas, 1987, pp. 2185-2188. This filtering is applied to the synthesized speech to further improve the speech quality. This system can create special sound effects to simulate the virtual space setting. For this purpose, echo or reverberation filtering can be employed. The echo filter is a first order infinite impulse filter with the following system function<maths id="math0027" num=""><math display="block"><mrow><mtext mathvariant="italic">H(z)</mtext><mtext>= </mtext><mfrac><mrow><mtext>1</mtext></mrow><mrow><mtext>1-</mtext><mtext mathvariant="italic">GZ</mtext><msup><mrow><mtext></mtext></mrow><mrow><mtext>-</mtext><mtext mathvariant="italic">D</mtext></mrow></msup></mrow></mfrac></mrow></math><img file="EP0779732A2_D0028.tif" /></maths> where <i>D</i> is the reverberation delay and <i>G</i> is the reverberation coefficient (which has a magnitude less than 1.0) to create the needed special effect. The bandpass filtering is applied to the output of the echo filter to remove the DC and low-frequency offset noise, and to effect the de-emphasis filtering. The filter transfer function is<maths id="math0028" num=""><math display="block"><mrow><mtext mathvariant="italic">H(z)</mtext><mtext>= </mtext><mfrac><mrow><mfenced open="(" close=")"><mrow><mtext>1-</mtext><msup><mrow><mtext mathvariant="italic">z</mtext></mrow><mrow><mtext>-1</mtext></mrow></msup></mrow></mfenced></mrow><mrow><mtext>(1-0.875</mtext><msup><mrow><mtext mathvariant="italic">z</mtext></mrow><mrow><mtext>-1</mtext></mrow></msup><mtext>) (1-</mtext><mfrac><mrow><mtext>63</mtext></mrow><mrow><mtext>64</mtext></mrow></mfrac><msup><mrow><mtext mathvariant="italic">z</mtext></mrow><mrow><mtext>-1</mtext></mrow></msup><mtext>)</mtext></mrow></mfrac></mrow></math><img file="EP0779732A2_D0029.tif" /></maths>

0075Using the knowledge about the spatial positions of the speaker and the listener in the virtual world, the distance filtering is implemented to convert the mono sound samples into stereo sound samples using the following algorithm: <ul id="ul0008" list-style="none" compact="compact"><li>1. Let Θ_<i>l</i> and Θ_<i>s</i>, be listener and speaker angles in the virtual space and let dbe the distance between them (in meters).</li><li>2. Then distance gain, <i>G</i>_<i>d</i>, is obtained as<maths id="math0029" num=""><img file="EP0779732A2_D0030.tif" /></maths></li><li>3. The left and right distance filter coefficients are compputed as<maths id="math0030" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">L</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>=</mtext><msub><mrow><mtext mathvariant="italic">G</mtext></mrow><mrow><mtext mathvariant="italic">d</mtext></mrow></msub><msub><mrow><mtext>∗(0.65-0.35∗sin(Θ</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><mtext>- </mtext><mfrac><mrow><mtext>π</mtext></mrow><mrow><mtext>6</mtext></mrow></mfrac><msub><mrow><mtext> )∗(0.65+0.35∗cos(Θ</mtext></mrow><mrow><mtext mathvariant="italic">s</mtext></mrow></msub><msub><mrow><mtext>))/(1.5-0.5∗cos(Θ</mtext></mrow><mrow><mtext mathvariant="italic">s</mtext></mrow></msub><mtext>))</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">L</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><mtext>=</mtext><msub><mrow><mtext mathvariant="italic">L</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext>∗(1-cos(Θ</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><mtext>)/2</mtext></mrow></math><img file="EP0779732A2_D0031.tif" /></maths><maths id="math0031" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">R</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>=</mtext><msub><mrow><mtext mathvariant="italic">G</mtext></mrow><mrow><mtext mathvariant="italic">d</mtext></mrow></msub><msub><mrow><mtext>∗(0.65-0.35∗sin(Θ</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><mtext>+ </mtext><mfrac><mrow><mtext>π</mtext></mrow><mrow><mtext>6</mtext></mrow></mfrac><msub><mrow><mtext> )∗(0.65+0.35∗cos(Θ</mtext></mrow><mrow><mtext mathvariant="italic">s</mtext></mrow></msub><msub><mrow><mtext>))/(1.5+0.5∗cos(Θ</mtext></mrow><mrow><mtext mathvariant="italic">s</mtext></mrow></msub><mtext>))</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">R</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><mtext>=</mtext><msub><mrow><mtext mathvariant="italic">R</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext>∗(1+cos(Θ</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><mtext>)/2</mtext></mrow></math><img file="EP0779732A2_D0032.tif" /></maths></li><li>4. Finally, the left and right channel speech samples are computed using the following filtering operations,<maths id="math0032" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext mathvariant="italic">n</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">=R</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>∗</mtext><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext mathvariant="italic">n</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">+R</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><mtext>∗</mtext><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext mathvariant="italic">n-</mtext><mtext>1</mtext></mrow></msub></mrow></math><img file="EP0779732A2_D0033.tif" /></maths><maths id="math0033" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">l</mtext></mrow><mrow><mtext mathvariant="italic">n</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">=L</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>∗</mtext><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext mathvariant="italic">n</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">+L</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><mtext>∗</mtext><msub><mrow><mtext mathvariant="italic">l</mtext></mrow><mrow><mtext mathvariant="italic">n-</mtext><mtext>1</mtext></mrow></msub></mrow></math><img file="EP0779732A2_D0034.tif" /></maths></li></ul> where <i>x</i>_<i>n</i> is the output of speech synthesizer (mono sound), <i>l</i>_<i>n</i> and <i>r</i>_<i>n</i>, are the resulting left and right channel sound sequences.

Ambient Sound Generation

0076In a virtual socialization environments, background sounds are generated to create special effects. Examples are when a participant leaves/enters a discussion group, the rest of the people in the group hear a sound like opening/closing of a door. It could also be a background music in the virtual space. Such sounds are generated by this module.

Wave Mixer

0077The sound output through the acoustic speakers can be one of the following <ul id="ul0009" list-style="none" compact="compact"><li>1. One person's speech only</li><li>2. One person's speech with background sound (music or ambient noise to simulate virtual space).</li><li>3. Two person's speech only, or</li><li>4. Two person's speech with background sound (music or ambient noise to simulate virtual space.</li></ul>

0078The wave mixer takes as input different sound data streams, apply appropriate user specified gains, add them and finally apply soft clipping on the date to ensure high speech quality.

0079The invention now being fully described, it will be apparent to one of ordinary skill in the art that any changes and modifications can be made thereto without departing from the spirit or scope of the invention as set forth herein. Accordingly, the present invention is to be limited solely by the scope of the appended claims.