Method of reducing index sizes used to represent spectral content vectors

A method identifies a codeword to represent a vector derived from an audio signal by applying the vector to first and second decision trees. The first decision tree is associated with a first type of audio sound and produces a first codeword. The second decision tree is associated with a second type of audio sound and produces a second codeword. One of the first and second codewords is then selected as the codeword for the vector. In further embodiments, the vector describes the spectral content of the audio signal and a linear prediction value is generated for the vector. The difference between the linear prediction value and the vector is used to identify the codeword.

BACKGROUND OF THE INVENTION

The present invention relates to representations of the spectrum of a signal. In particular, the present invention relates to reducing the size of data words needed to describe the spectral content of a signal.

In speech recognition, the speech signal is typically divided into frames and each frame is converted into a set of values that describe the spectral energy of the frame. These spectral values are then used to decode the speech signal to produce a sequence of words.

At times, it is desirable to transmit the spectral values from one computer to another to allow for distributed recognition of the speech signal or to store the spectral values for later processing. One barrier to transmitting or storing these values is that for each frame there are often at least thirteen spectral values and each spectral value is represented by a sixteen bit word. This results in 26 bytes per frame. With a new frame being constructed every ten milliseconds, 2.6 kilobytes of information must be transmitted for every second of speech.

To reduce the amount of information that must be transmitted or stored, the prior art has used Vector Quantization in which each combination of spectral values that can be generated for a frame is represented by a codeword in a codebook. The index for the codeword is then transmitted or stored in place of the spectral values. At the receiver or when the index is retrieved for processing, the index is applied to a copy of the codebook to retrieve the codeword. The codeword is then used as the spectral vector.

Although Vector Quantization reduces the amount of data that must be transmitted or stored, it requires a large amount of memory to store all of the codewords. In fact, the codebook for the spectral values typically exceeds the amount of memory available on the computing device.

To overcome this, split-Vector Quantization has been used. In split-Vector Quantization, the spectral vector is divided into segments and a codeword is identified for each segment of the vector. For example, for a spectral vector of [C0,C1,C2,C3,C4,C5,C6,C7,C8,C9,C10,C11,C12], C0 would constitute one segment, [C1,C2,C3,C4,C5,C6] would constitute a second segment, and [C7,C8,C9,C10,C11,C12] would constitute a third segment. Thus, three codewords would be used to describe each frame. Although more codewords are used at each frame, the number of possible codewords drops significantly using split-Vector Quantization such that the size of the indices is greatly reduced.

However, even with the techniques provided by split-Vector Quantization, additional reductions in the amount of data transmitted or stored for a spectral representation of a speech signal is desired.

SUMMARY OF THE INVENTION

A method identifies a codeword to represent a vector derived from an audio signal by applying the vector to first and second decision trees. The first decision tree is associated with a first type of audio sound and produces a first codeword. The second decision tree is associated with a second type of audio sound and produces a second codeword. One of the first and second codewords is then selected as the codeword for the vector. In further embodiments, the vector describes the spectral content of the audio signal and a linear prediction value is generated for the vector. The difference between the linear prediction value and the vector is used to identify the codeword.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

FIG. 2is a block diagram of a mobile device200, which is an exemplary computing environment. Mobile device200includes a microprocessor202, memory204, input/output (I/O) components206, and a communication interface208for communicating with remote computers or other mobile devices. In one embodiment, the afore-mentioned components are coupled for communication with one another over a suitable bus210.

Memory204is implemented as non-volatile electronic memory such as random access memory (RAM) with a battery back-up module (not shown) such that information stored in memory204is not lost when the general power to mobile device200is shut down. A portion of memory204is preferably allocated as addressable memory for program execution, while another portion of memory204is preferably used for storage, such as to simulate storage on a disk drive.

Memory204includes an operating system212, application programs214as well as an object store216. During operation, operating system212is preferably executed by processor202from memory204. Operating system212, in one preferred embodiment, is a WINDOWS® CE brand operating system commercially available from Microsoft Corporation. Operating system212is preferably designed for mobile devices, and implements database features that can be utilized by applications214through a set of exposed application programming interfaces and methods. The objects in object store216are maintained by applications214and operating system212, at least partially in response to calls to the exposed application programming interfaces and methods.

Communication interface208represents numerous devices and technologies that allow mobile device200to send and receive information. The devices include wired and wireless modems, satellite receivers and broadcast tuners to name a few. Mobile device200can also be directly connected to a computer to exchange data therewith. In such cases, communication interface208can be an infrared transceiver or a serial or parallel communication connection, all of which are capable of transmitting streaming information. Through communication interface208, mobile device200may be connected to a remote server, personal computer, or network node. Under the present invention, mobile device200is capable of transmitting speech data from the mobile device to a remote computer where it can be decoded to identify a sequence of words.

Input/output components206include a variety of input devices such as a touch-sensitive screen, buttons, rollers, and a microphone as well as a variety of output devices including an audio generator, a vibrating device, and a display. The devices listed above are by way of example and need not all be present on mobile device200. In addition, other input/output devices may be attached to or found with mobile device200within the scope of the present invention.

The present invention provides a means for transmitting and/or storing spectral information that describes a speech signal so that a smaller amount of data is transmitted or stored.

FIG. 3shows a block diagram of a local-remote computer system in which embodiments of the present invention may be practiced. InFIG. 3, a local device300, which can be a computer such as computer110described above or a mobile device such as mobile device200, receives a speech signal302at a microphone304. The audio waves of the speech are converted into analog electrical signals by microphone304. An analog-to-digital converter306then converts the analog signal into a sequence of digital values, which are grouped into frames of values by a frame constructor308. In one embodiment, A-to-D converter306samples the analog signal at 16 kHz and 16 bits per sample, thereby creating 32 kilobytes of speech data per second and frame constructor308creates a new frame every 10 milliseconds that includes 25 milliseconds worth of data.

Each frame of data provided by frame constructor308is converted into a feature vector by a feature extractor310. Methods for identifying such feature vectors are well known in the art and include 13-dimensional Mel-Frequency Cepstrum Coefficients (MFCC) extraction, which produces 13 cepstral values per feature vector. The cepstral feature vector represents the spectral content of the speech signal within the corresponding frame.

The feature vectors312generated by feature extractor310are provided to a Vector Quantization (VQ) unit314, which identifies a set of codewords to represent the vectors. The inventive technique for identifying these codewords is described below.

After the codewords have been identified by VQ314, indices for the codewords are transmitted to a remote computer316over a communication path that can include wire or wireless connections through one or more network nodes. In remote computer316, the indices are applied to a codebook by a VQ decoder318to retrieve the corresponding codewords. These codewords are then provided to a speech decoder320, which uses the codewords to identify words represented by the speech signal.

Note that althoughFIG. 3depicts the local device as transmitting the indices to a remote computer where they are used to perform speech decoding, in other embodiments, the local device stores the indices in a local memory and retrieves them at a later time. Upon retrieval, the indices are used to identify the corresponding codewords and the retrieved codewords are used in speech decoding.

In the past, Vector Quantization was performed by applying the feature vector, or some segment of the vector, to a decision tree, such as decision tree400ofFIG. 4. The tree is traversed in a top-down manner and at each node in the tree a question is applied to the segment of the feature vector. Based on the answer to the question, one of the child nodes of the current node is selected. The question at that node is then applied to the segment of the vector. Eventually a leaf node is reached, which contains the codeword index to be assigned to the segment of the feature vector. For example, beginning at node402, the decision tree could be traversed until reaching leaf node404, which contains a codeword index.

Under the prior art, only one decision tree was provided for each segment of the feature vector. Thus, if a 13-dimensional vector composed of values C0–C12 were divided into three segments containing values C0, C1–C6, and C7–C12, respectively, there would be only three decision trees, one for each segment.

Under an embodiment of the present invention, multiple decision trees are provided for each segment. Each decision tree is trained by grouping training feature vectors for similar types of audio sounds. As a result, each tree has a smaller range of possible feature vectors and these vectors can be represented by a smaller number of codewords. This results in fewer bits in the index used to identify the codewords.

For example, under one embodiment, a separate decision tree is provided for each phone in a language, including the silence phone. Thus, as shown inFIG. 5, there are separate decision trees500,502,504, and506for the phones “AA”, “EY”, “T” and “Silence”.

Note there are more phones in most languages and thus there would be more decision trees. Only a small number of the possible phones are shown inFIG. 5for simplicity. In addition, the sizes of the decision trees can be different for different phones and the present invention is not limited to the particular tree sizes shown. Furthermore, binary decision trees do not have to be used and each node can have any number of desired children. In other embodiments, audio sounds are grouped into types based on whether they are a vowel sound or a consonant.

To train each tree, feature vectors are generated from a known text and the feature vectors associated with each phone are grouped together. Thus, all of the feature vectors for the phone “AA” would be grouped together. A decision tree is then constructed based on the group of training vectors for the phone. The construction of such decision trees is well known and involves selecting questions that divide the training data to optimize some goodness measure. Typically, the goodness measure divides the vectors such that the resulting groups or classes formed by the division are clearly discriminated between each other. The particular technique used for selecting the question sets is not critical to the present invention and any technique that results in a reasonable decision tree may be used.

Under many embodiments, split Vector Quantization is performed where several decision trees are formed for each phone with each tree being assigned to a different segment of the feature vector. For example, under one embodiment three decision trees are formed for each phone with one tree for vector value C0, one tree for vector segment C1–C6 and one tree for vector segment C7–C12. These trees are trained in the same manner as described above except that only the segment of the vector that is associated with the tree is used during training.

Once the decision trees have been constructed, they can be used to identify codewords for an input feature vector.FIG. 6provides a flow diagram for one method of selecting codewords for an input vector. At step600, the vector is divided into segments, if desired, so that split vector quantization can be performed. At step602, one of the segments is selected. The selected segment is applied to each phone's decision tree at step604to identify a possible codeword segment by traversing the tree from the top of the tree to a leaf node.

After a possible codeword segment has been identified for each phone, the method determines if there are additional segments of the vector to process at step606. If there are, the process returns to step602where the next segment is selected. The new segment is then applied to the decision trees associated with that segment. In particular, the new segment is applied to a separate decision tree for each phone.

When all of the segments of the vector have been processed at step606, a combined codeword is formed for each phone at step608by combining the codeword segments produced for each phone in step604. Thus, if codeword segments W0, [W1,W2,W3,W4,W5,W6], and [W7,W8,W9,W10,W11,W12] had been formed for the phone “AA”, step608would combine them to form a codeword of [W0,W1,W2,W3,W4,W5,W6,W7,W8,W9,W10,W11,W12].

At step610, the distance between each phone's combined codeword and the feature vector is determined. The combined codeword that is the closest to the vector is then selected as the codeword for the vector. At step612, the indices for the codeword segments that form the selected codeword, together with an identifier that indicates which phone generated the codeword, are transmitted to a remote computer or stored for later use.

Using the stored or transmitted indices, it is possible to retrieve the codeword segments by applying the indices to the codebooks associated with the phone used to form the indices. The retrieved segments can then be combined to form a codeword that is used in decoding.

In other embodiments, different segments of the codeword can come from decision trees associated with different phones. Thus, instead of all of the segments being associated with a single phone, one segment can come from a decision tree associated with a first phone while a different segment can come from a decision tree associated with a second phone. In such embodiments, all of the possible combinations of codeword segments formed from the decision trees for the phones are compared to the feature vector to determine which combination is closest to the feature vector. The transmitted data then consists of a phone label and an index for each segment in the closest combination. For example, the data would include [phone1,N1,phone2,N2,phone3,N3], where phone1, phone2, and phone3 are the phones identified for the first, second and third segment of the codeword, and N1, N2, and N3 are the indices for the respective codeword segments.

Note that in this second embodiment, more data is transmitted. As a result, to maintain efficiency, the decision trees need to shrink to provide a comparable data rate.

In a further embodiment of the present invention, the amount of data that is transmitted or stored is further reduced by utilizing linear predictive coding. As shown in the block diagram ofFIG. 7, under this embodiment of the invention, a client700receives a speech signal at a microphone702, converts the signal into a digital signal using an analog-to-digital convertor704, groups the digital values into frames using a frame constructor706and extracts feature vectors that describe the spectral content of a frame using a feature extractor708in the same manner as described above forFIG. 3. In particular, the feature vector is based on a frequency-domain representation of the audio signal. Thus the vector contains spectral values or cepstral values.

In the embodiment ofFIG. 7, the vectors are not used directly to select the codewords. Instead, the vectors are provided to a linear prediction unit710.

As shown in step800of the flow diagram ofFIG. 8, linear prediction unit710converts the vector into a difference vector, which is equal to the difference between the vector and a vector generated through linear prediction based on past vectors. In particular, linear prediction unit710generates a difference value for each dimension of the vector through the equation:

Δ⁢⁢x=xt-∑τ=1N⁢ατ⁢xt-τEQ.⁢1
where Δx is the difference value, xtis a dimension of the vector for the current time t, xt−τis a dimension of the vector for a previous time t−τ, ατis a linear prediction coefficient, and N is the number of previous vectors that are used to predict the next vector.

At step802, the difference values for the dimensions of the vector are provide to vector quantization unit712, which identifies a codeword for the difference values. This can be done using a single decision tree or using a separate decision tree for each phone as discussed above. In addition, all of the difference values can be applied to the same decision trees or the difference values can be grouped into segments, with each segment being applied to the decision trees separately to thereby perform split vector quantization.

At step804, the index or indices for the identified codewords are passed to a remote computer714(or stored in other embodiments. The index or indices are then used by a VQ decoder716to retrieve the codewords represented by the index or indices at step806. These codewords are provided to a linear prediction unit718, which identifies a current value for each dimension at step808using the equation:

xt=Δ⁢⁢xcodeword+∑τ=1N⁢ατ⁢xt-τEQ.⁢2
where xtis a value for a dimension of the vector for the current time t, Δxcodewordis the difference value for the dimension retrieved from codebooks716, xt−τis the value of the dimension at a previous time t−τ, α96is a linear prediction coefficient, and N is the number of previous vectors that are used to predict the next vector. Note that linear prediction units710and718use the same linear prediction coefficients and the same value of N.

Equation 2 is used for each dimension resulting in a reconstructed vector that is provided to a decoder720. Decoder720uses a sequence of retrieved in the same way as described above to identify a sequence of words represented by the speech signal.

Since the difference values have a smaller range of possible values, they can be described with fewer bits, resulting in fewer codewords in the codebooks. As a result, the indices passed to the remote computer are smaller using the linear prediction technique ofFIGS. 7 and 8.