Signal Pattern Encoder and Classifier

The present invention relates generally to a signal encoder and classifier and more specifically to such an encoder and classifier for signal data obtained from a multiplicity of property filters.

One particular function of the present invention is in its use relative to automatic speech interpretation. Such use will be used for illustrative and descriptive purposes.

Therefore, in order to place the descriptive matter in its proper perspective, the following discussion of currently available technology that may be applied to solve immediate problems in automatic speech interpretation is presented herewith.

The present assignee has developed certain systems for speech interpretation on which several patents have issued.

An automatic speech interpreter, as disclosed in U.S. Pat. No. 3,812,291 issued May 21, 1974 and assigned to the assignee of the present invention, is essentially an acoustic pattern recognition device. Acoustically isolated utterances, such as words or phrases, are normalized by an information-theoretic compression technique that removes the effect of talker cadence and, to some degree, the effect of speaker variability. The resulting 120-bit pattern is then correlated with reference patterns derived through a training process. The only requirement for accurate recognition is reasonable acoustic separation between the patterns. The system can be retrained on-line for new vocabularies, speakers or acoustic environments at the rate of about 5 seconds per vocabulary utterance. A voice command system using this technique has been demonstrated with a large number of vocabularies of up to 100 words and in several languages. A unique feature is the ability to operate the system over commercial telephone circuits.

The present invention represents a significant improvement to the encoding and classification technology covered, in part, under U.S. Pat. No. 3,812,291 and U.S. Pat. No. 3,582,559 also assigned to the present assignee. Although this invention incorporates a number of logical processes common to those patents, it also incorporates critical differences that yield substantially improved signal classification accuracy while dramatically reducing the requirements for buffer storage of unencoded signal data. These improvements have been measured by operating the present invention as a word recognition device and comparing classification performance with that obtainable using a similar device incorporating the invention described in U.S. Pat. No. 3,812,291. Test material consisted of 1000 prerecorded utterances taken from a 100-word vocabulary designed to span the sounds of the American English language in a balanced fashion. Using these test data, the present invention yielded an average 40% reduction in classification errors when compared with the performance of the invention described in U.S. Pat. No. 3,812,291.

FIG. 1 is a general schematic diagram of the present invention;

FIG. 2 is a schematic diagram of a prior art signal processor subassembly;

FIG. 3 is a schematic diagram of the event encoding subassembly;

FIG. 4a is a schematic diagram of the estimation mode of the pattern classifier subassembly; and

FIG. 4b is a schematic diagram of the classification mode of the pattern classifier subassembly.

An acoustic signal recognition system divides an acoustic pattern into time samples, which are coupled to a spectrum analyzer for generating plural signals representing the amplitude of discrete frequency bands for each time sample.

A circuit is then used for computing the sum of the differences between each of the individual frequency bands of the current time sample and each of the respective frequency bands of the last stored time sample. This sum is compared with a stored threshold value, and the current time sample is stored if the sum exceeds the threshold, but discarded if the sum is less than the threshold.

The resulting stored time samples are compressed, to provide a normalized word length signal pattern, for comparison with a stored library of reference patterns.

Reference patterns are generated for this library by comparing the normalized word length patterns from plural, repetitive, acoustic signals, to provide a record of consistent elements of the normalized word length patterns. These consistent elements are used for identifying acoustic patterns. The ratio of the number of elements of a current normalized word length pattern identical to a given reference pattern divided by the total number of elements in the given reference pattern is used to determine whether or not the normalized word length pattern being compared is in fact the reference word; this ratio is called the normalized score ratio.

The beginning and end of acoustic patterns are identified by counting successive stored and discarded time samples, respectively. When a sufficient number of consecutive stored time samples occurs, a degree of change exists which indicates a word is being input. When a sufficient number of consecutive discarded time samples occurs, the lack of change over a period of time indicates the word has ended.

Referring to FIGS. 1 and 2, the signal processing subassembly 20 is shown in FIG. 2 and consists of amplifier 21, spectrum analyzer 22, multiplexer 23, and analog-to-digital converter 24 which are similar to the same components as disclosed in U.S. Pat. No. 3,812,291 and are all well known components. Transducer 10 may be any known component such as a microphone or telephone handset, and may be remotely located from the rest of the apparatus as indicated in FIGS. 1 and 2.

The present invention differs significantly in the event encoding subassembly 40 of FIG. 1 from the inventions covered by U.S. Pat. Nos. 3,582,559 and 3,812,291.

Referring to FIG. 3, there is shown a diagram of the event encoding logic of the present invention. Instead of storing each digitized spectrum analyzer output for the duration of the utterance, the present invention retains only two spectrum samples in spectral data buffer 41. One sample is the current digitized output of the spectrum analyzer which will be denoted as:

where f.sub.j is the jth filter element, j=1, 2, . . ., 16 and t.sub.c is the current sample time.

The second sample is the last previous spectrum analyzer output accepted for encoding which will be denoted as:

where f.sub.j is the jth filter element, j=1, 2, . . ., 16 and t.sub.L is the sample time of the last previous spectrum accepted for encoding. This is one of the important concepts of the present invention. Either the first spectrum sample or a spectrum sample denoting a change is encoded. Accordingly, if a number of spectrum samples arrive which indicate no change, these samples are discarded. Therefore, any current sample is compared only to the last previously encoded sample. This greatly reduces the storage requirements of the coded data buffer 45. The absolute value of the difference between the two spectra in the spectral data buffer 41 is computed by the change detector 42. This is accomplished by summing the absolute values of the differences between the paired filter outputs of the two spectra according to the equation: ##EQU1## where f.sub.j is the jth filter element, j=1, 2, . . ., 16;

t.sub.c is the current sample time;

t.sub.L is time of the last sample accepted for encoding.

The difference, d.sub.c, is compared to change threshold T.sub.s to determine if the current sample is to be encoded. If

then the current spectrum analyzer output is passed through gate 43 to the binary encoder 44 and entered in coded data buffer 45. At the same time, the current sample, F.sub.c, replaces the "last previously encoded sample", F.sub.L. If

the current sample is purged from the spectral data buffer without being encoded, and the last previously encoded sample is not changed. In this fashion only spectrum samples that differ significantly from the last sample encoded are entered in the coded data buffer. Thus, if the spectrum is not changing significantly, i.e., there is no new information in the digitized spectrum, encoding does not take place.

A second significant difference from U.S. Pat. No. 3,812,291 is the fact that each spectrum analyzer output is substantially simultaneously encoded into a binary format as soon as it is selected by change detector 42. This results in a 16 to 1 savings in data storage when compared with the logic of the previous invention.

The binary encoder 44 operates on the same principal as the same device described in U.S. Pat. No. 3,812,291, FIG. 2, to produce a 15 bit code which will be denoted by

where i is an index representing the ith data sample selected for encoding, and b.sub.j (i) is the jth binary digit (bit) of the ith encoded sample, per U.S. Pat. No. 3,812,291, FIG. 2, with F.sub.1 -F.sub.16 representing the current output of signal processing subassembly 20 (FIG. 1 of the present invention) and Bit 1-Bit 15 as the input to coded data buffer 45 (FIG. 3 of the present invention).

Event detector 46 replaces the "word boundary detector" of U.S. Pat. Nos. 3,582,559 and 3,812,291. This is a third major difference from the previous inventions. Event detector 46 counts the total number samples S that have satisfied criteria (4) since the last previous event decision, and counts the number of consecutive samples S that have satisfied criterion (5) since the last previous event decision. Whenever

an event decision is made.

At that time, if

the data contained in coded data buffer 45 are passed through gate 47 to event encoder 48 and S and S are reset to zero.

gate 47 is inhibited, coded data buffer 45 is reset to zero, and S and S are reset to zero. The values of T.sub.s, T.sub.w, T.sub.min, and T.sub.max may be set to match appropriate signal conditions. For use in word recognition, for instance, typical values are:

with the system sampling rate set at 200 samples per second. In this case, T.sub.w specifies a gap of silence between words of at least 160 ms as a key to declaration at the end of an utterance, (criterion 7). Utterances must contain a minimum of 16 coded data samples and a maximum of 199 such samples to be declared "valid" words, (criterion 5). Furthermore, each coded data sample must have satisfied criteria (4). These event criteria provide a very effective filter for the elimination of extraneous acoustic events unrelated to discrete word utterances.

Event encoder 48 receives data under the control of event detector 46. When criteria (7) and (8) are satisfied, the binary encoded data from buffer 45 are further compressed to form a 120 bit representation of the event (word) that just occurred. This is an important step because a variable amount of data (from 16 to 199 coded data samples) may be stored in buffer 45. After processing by event encoder 48, these data will be in a fixed 120 bit format suitable for use by pattern classifier subassembly 50. Event encoder 48 segments the data in buffer 45 into eight equal intervals by dividing the total number of data samples D, by eight, discarding any remainder. Within each interval, the binary encoded data, consisting of a multiplicity of 15-bit samples of form (6), are combined to form a single 15-bit representation as follows:

Assume the binary data samples associated with one of the eight intervals are arranged as follows: ##EQU2## where each row represents a binary encoded sample of form (6). Array (11) is to be replaced by a single 15-bit array of the form:

where B.sub.j replaces column j of (11) according to the following rule: ##EQU3## Since eight arrays of the form (12) are created for each event encoded, a 120-bit binary pattern is output by event encoder 48 for each detected event.

The 120-bit pattern output by event encoder 48 is sent to pattern classifier subassembly 50.

The reference pattern memory 60 must be loaded with encoded patterns representative of the events to be classified. The present invention can be programmed, via the estimation mode of operation of pattern classification subassembly 50, to produce reference patterns matched to events input to the signal processing subassembly. The programming operation, commonly referred to as "training", will be described in terms of use of the invention as a word recognition device, although this should not be interpreted as limiting use of the invention to such an application.

For the purpose of programming reference pattern memory 60, the pattern classification subassembly 50 operates as follows under supervision of the timing and control subassembly 30: (Refer to FIG. 4a.)

(1) The user is prompted via visual or audio means (not shown) to speak each word to be included in the reference pattern memory (vocabulary).

(2) As each prompted word is spoken, it is encoded into a 120-bit binary pattern by event encoding subassembly 40 as described above and transferred to buffer storage 51.

(3) The 120-bit pattern is then inverted by inverting logic 52 to create a second 120-bit pattern which is the two's complement of the original. The complemented pattern is stored in buffer storage 53.

(4) The resulting 240-bit pattern contained in buffers 51 and 53 is then ANDED by gate 54 with the appropriate contents of the reference pattern memory as selected by the timing and control subassembly. (If no previous examples of the particular vocabulary item have been entered into memory, the 240-bit pattern is ANDED with 240 "one" bits.) As a result of the ANDING operation, the first 120 bits of each reference pattern will be "one" bits if and only if each bit was consistently a "one" bit for all training examples. Bits 121 through 240 will be "one" bits if any and only if each bit was consistently a "zero" bit for all training examples. This is a result of the inverting operation. The reference pattern for event class K will be denoted by

where p.sub.1 (k), p.sub.2 (k), . . . p.sub.120 (k) represent the binary digits resulting from ANDING all encoded training examples for class K and p.sub.121 (k), p.sub.122 (k), . . . , p.sub.240 (k) represent binary digits resulting from ANDING all complemented encoded training examples for class K.

(5) Finally, the total number of "one" bits in R.sub.k are counted by bit counter 55. This count, which represents the total number of bits, either "one" or "zero", that were consistent in all training examples, is stored along with R.sub.k in reference pattern memory 60, which may be one of many well known devices for storing binary data. The number of consistent bits for event class K will be denoted by N.sub.k.

From the above discussion it can be seen that the training operation of this invention is "open ended", i.e., it can be continued indefinitely in time. In particular, the reference pattern memory could be "updated" every time a word was spoken and identified, thus allowing the invention to adapt itself to changes in signal conditions, e.g. fatigue in a speaker's voice. This method of pattern estimation differs substantially from that described in U.S. Pat. No. 3,812,291 which required that pattern estimation be limited to a fixed number of class examples presented to the estimator prior to operation of the pattern classifier. This aspect of the present invention then represents a fourth significant difference from the invention described in U.S. Pat. No. 3,812,291. Optional operation of updating pattern classification subassembly 50 in the estimation mode is indicated by the dashed line in FIG. 1.

The classification mode of pattern classifier 50 is diagrammed in FIG. 4b. The 120-bit binary pattern generated by event encoding subassembly 40 is ANDED in both its original and two's complement form with class candidate reference patterns selected from reference pattern memory 60. Bits 1-120 of the event encoder output are ANDED with bits 1-120 of each selected reference pattern. The resulting count of "one" bits generated by counter 55 represents the number of bit matches between the event encoder output and reference pattern "one" bits that were consistent for all training examples. Bits 121-240, generated by inverting the event encoder output, are ANDED with bits 121-240 of each selected reference pattern. The resulting count of "one" bits generated by counter 55 represents the number of bit matches between the event encoder output and reference pattern "zero" bits that were consistent for all training examples. Thus the total 240 bit count generated by "one" bit counter 55 represents the total number of bit matches between the "ones" and "zeros" of the event encoder output and the consistent "ones" and "zeros" contributing to the reference pattern. This count will be denoted by C.sub.k where K is the class index. For each class, the maximum output from counter 55 is N.sub.k, which represents a perfect match with the consistent bits of the reference pattern. Score computer 56 calculates the value

where S.sub.k is the pattern classification score computed between the event encoder output and reference pattern class K, and M is a constant equal to the maximum score possible.

By definition C.sub.k /N.sub.k .ltoreq.1. This ratio "normalizes" the scores obtained to account for the consistency of the training patterns.

The highest value of S.sub.k for the selection of reference patterns matched with the event encoder output is stored in best score buffer 27 along with the class index, K.

The selection by the operator or machine of pattern classes (vocabulary items in word recognition) presented for matching with the output of the event encoder is controlled by timing and control assembly 30. The selection presented may be altered on the basis of previous classification decisions. When all selected classes have been matched, the best score stored in buffer 57 is compared to a reject threshold, RTHL, by decision circuit 58. If

where S.sub.k is the highest score resulting from the selected classification sequence, the decision is made in favor of class K and index K is sent to output buffer 70. The information stored in buffer 70 may then be used by a suitable process or storage device 80 such as data processing or data storage devices. If

no decision is made and no code is output to buffer 70.

Classification decisions are monitored by timing and control subassembly 30 to permit selection of reference patterns for additional classification decisions. The timing and control subassembly 30 provides clocking signals to activate multiplexer 23 and analog-to-digital converter 24 of FIG. 2, as well as change detector 42 and event detector 46 of FIG. 3. The timing and control subassembly also provides class identification during the estimation mode of operation of pattern classification subassembly 50, and provides a sequence of candidate class indices during the classification mode of operation. For some applications of the invention, timing and control subassembly 30 may be interfaced to external controls and displays including switches, push buttons, keyboards and visual display devices of known art as indicated in FIG. 1. Timing and control subassembly 30 is of known art and may generally be considered to be any of a number of commercially available stored program controllers.

It is to be understood that the above description and drawings are illustrative only since equivalent components may be used in the practice of the invention. Accordingly, the invention is to be limited only by the scope of the following claims.