Pattern Feature Extracting System

The present invention relates to a system for extracting feature parameters in a pattern to be recognized, and more particularly to a system for normalizing the feature parameters attained by orthogonal transformations. The memory capacity and number of calculations ordinarily required is reduced.

There is well known in the art of pattern recognition a technique in which the parameters attained by measurements or analyses are orthogonally transformed so as to compress the quantity of information and the number of the calculations required. In speech recognition, for example, cepstrum data is used as the feature parameters. The data is prepared by logarithmically transforming spectral data obtained by frequency analysis of a speech signal, and then inversely Fourier-transforming (as a kind of orthogonal transformation) the logarithmically transformed data.

It is important to extract normalized data which is not influenced by a variety of external factors. In speech recognition, for example, there has been proposed as a normalizing method for extracting the speech features independent of personal characteristics or transmission characteristics a method in which a least-squares straight line fit for a speech spectrum is determined and is subtracted from the original speech spectrum. This method is disclosed in PGPRL 79-46 of The Institute of Electronics and Communication Engineers of Japan, entitled "A System of Spoken Word Recognition by Non-linear Spectral Matching", published in October, 1979.

The personal characteristics of speech vary with vocal tract length or radiation characteristics, whereas transmission characteristics vary with the telephone or other transmission line used. These characteristics can be modelled by a straight line (a.multidot.i+b). By determining the least-squares straight line represented by (a.multidot.i+b) and by subtracting the respective values given by the least-squares straight line from the corresponding value of the original speech spectrum, it is possible to obtain a normalized spectrum from which distortions due to personal and/or transmission characteristics are eliminated. More specifically, if the i-th spectrum is designated by f.sub.i, and the least-squares straight line is expressed by (a.multidot.i+b), the normalized spectrum g.sub.i is given by the following equation:

wherein i=1, . . . , n.

The least-squares straight line is determined by obtaining the coefficients a and b that minimize an error E expressed by ##EQU1## Specifically, the coefficients a and b are obtained by the following equations: ##EQU2## In more detail, the coefficients a and b are calculated by using equations (5) and (6): ##EQU3## By making use of the coefficients a and b thus determined, the least-squares straight line (a.multidot.i+b) is obtained, and the normalization is conducted by substrating the obtained least-squares straight line thus obtained from the original speech spectrum f.sub.i in accordance with equation (1).

The orthogonal transformation used in the pattern recognition includes the Fourier transform, the Walsh-Hadamard transform, and the KL (Karhunen-Loeve) transform, all of which are used frequently especially in the field of speech recognition. The Fourier transform (or inverse Fourier transform) is widely used for extracting cepstrum data, as described above, whereas the two others are also used in feature extracting methods for speech recognition. For example, reference should be made to the paper "A WALSH-HADAMARD TRANSFORM LSI FOR SPEECH RECOGNITION" by Hidefumi Ohga et al., IEEE TRANSACTIONS ON CONSUMER ELECTRONICS, Vol, CE-28, No. 3, August 1982, pp. 263 to 270, the paper "APPLICATION OF THE KARHUNEN-LOEVE EXPANSION TO FEATURE SELECTION AND ORDERING" by Keinosuke Fukunaga and Warren L. G. Koontz, IEEE TRANSACTIONS ON COMPUTERS, VOL. C-19, NO. 4, April 1970, pp. 311 to 318, and the paper "ON TALKER VERIFICATION VIA ORTHOGONAL PARAMETERS" by Robert E. Bogener, IEEE TRANSACTIONS ON ACOUSTICS, SPEECH, AND SIGNAL PROCESSING, VOL. ASSP-29, NO. 1, February 1981, pp. 1 to 12.

As has been described above, normalization in the prior art is effected by an orthogonal transformation after subtracting the parameters given by at least-squares straight line from the corresponding parameters for the input pattern. The calculations for this normalization according to equation (1) require n subtractions, even if the least-squares straight line (a.multidot.i+b) has been tabulated in advance. Therefore the prior art normalization is not preferable in a pattern recognition system which requires a reduction in the number of calculations and a simplification of the circuitry.

It is, therefore, an object of the present invention to provide a pattern feature extracting system which can significantly reduce the number of subtractions in normalizing the feature parameters obtained by orthogonal transformations.

Another object of the present invention is to provide a pattern feature extracting system for obtaining the normalized feature parameters used for speech recognition, which can significantly reduce the memory capacity required and the number of calculations.

According to the present invention, a pattern feature extracting system comprises a first orthogonal transformation means for orthogonally transforming pattern data, which is composed of n pieces of pattern information, in order to develop m (where m<n) first orthogonal parameters; means for determining a least-squares straight line for the n pieces of information; a calculation means for calculating m orthogonal parameters of a least-squares straight line fit for n pieces of pattern information by using the m orthogonal parameters obtained by said orthogonal transformation means; and a substraction means for subtracting the second orthogonal parameters from the corresponding first orthogonal parameters in order to output the subtracted results as pattern features. The Fourier transform, the COSINE transform, the Walsh-Hadamard transform, or the KL transform can be used for the orthogonal transformation. If data, which has been prepared by logarithmically transforming the spectral data of speech, is used as the n pieces of pattern information, and if the Fourier transform is used as the orthogonal transformation, normalized cepstrum data can be used as the feature parameters. In such parameters, the quantity of information is compressed and influences from personal and transmission characteristics are eliminated.

FIG. 1 is a block diagram showing an embodiment in which the present invention is applied to a speech recognition system;

FIGS. 2A and 2B are a detailed block diagram of one example of the first orthogonal transformer employed in FIG. 1, using the Fourier transform, and an operation timing chart thereof;

FIGS. 3A and 3B are a detailed block diagram of one example of the second orthogonal transformer employed in FIG. 1, and an operation timing chart thereof;

FIG. 4 is a block diagram showing another example of the first orthogonal transformer in FIG. 1, which uses the COSINE transform; and

FIGS. 5A and 5B are a detailed block diagram showing another example of the second orthogonal transformer in FIG. 1, and an operation timing chart thereof.

First of all, the fundamental principles of the present invention will be described in the following. Since addition and subtraction operations are not influenced by an orthogonal transformation, the following equations holds if the orthogonal transformation is expressed by T (T<T.sub.1, T.sub.2, . . . , T.sub.k, . . . T.sub.n,):

wherein k=1, . . . , n'.

The orthogonal transformation T.sub.k is an operation for feature extraction. There are n' orthogonal parameters, but are number of orthogonal parameters usually used as feature parameters is a value m which is significantly smaller than the number n of the parameters f.sub.i. This is because the quantity of information in the parameters f.sub.i is compressed by the orthogonal transformation. As a result, the normalization using equation (7) requires a smaller number of calculations than that using equation (1). For example, as has been described hereinbefore, in the case of speech recognition using cepstrum parameters as feature parameters, inverse Fourier Transform as the orthogonal transformation T.sub.k, and n=128, n'=128 and m=8, the number of calculations required by equation (7) is one sixteenth those required by equation (1). From the Parseval equation, moreover, the following holds: ##EQU4## The linear operations are not influenced by the orthogonal transformation. Therefore, the following equation holds: ##EQU5## wherein Re(x) and Im(x) respectively are the real and imaginary parts of x.

From equations (3) and (4), the parameters a and b of the least-squares straight line are determined by solving the following equations:

wherein: ##EQU6## Here, since the orthogonal transformation T.sub.k (f.sub.i) for a large k is sufficiently small, the equations (17) and (18 ) can be used in place of equations (12) and (13) if the terms larger than m are omitted. ##EQU7##

The followings are apparent from equations (7), (10) and (11): The prior art method in which the normalized parameters are developed by first subtracting the value given by the least-squares straight line from the value given by the input patterns, and subsequently subjecting the difference to orthogonal transformations, is equivalent to a method in which both the input patterns and the least-squares straight line are first orthogonally transformed and then the orthogonal parameters of the least-squares straight line are subtracted from the orthogonal parameters of the input patterns. In the former method, the parameters a and b of the least-squares straight line are given by equations (5) and (6), and can be obtained by computing the terms ##EQU8## because the variables are f.sub.i in reality. In the latter method, on the other hand, it is sufficient to use equations (17) and (18) because the variables are T.sub.k (f.sub.i) in reality. Comparing the numbers of calculations involved in the two methods, therefore, the latter method requires m/n times the number of calculations as the former. In addition, the normalizing operation is expressed by the following equation if the number of orthogonal parameters used is m,

wherein k=1, 2, . . . , m.

From the comparison of the number of normalization calculations involved in the two methods as shown by equations (1) and (7'), it is obvious that the latter method requires m/n times the number of subtractions as the former.

As has been described hereinbefore, according to the present invention, the normalizing operation, i.e., the subtractions of the least-squares straight line, which have been conducted before the orthogonal transformations in the prior art, can be conducted after orthogonal transformations so that the number of calculations can be further reduced.

Next, for the case in which the Fourier transform or the COSINE transform is specifically used as the orthogonal transformation, the following description is directed to specific algorithms for determining the parameters of the least-squares straight line and for conducting the normalizing equation (7) after the orthogonal transformations. First of all, when the inverse Fourier transform is used as the orthogonal transformation, i.e., the orthogonal transformation is conducted by the use of the following equation: ##EQU9## the previous equations (17), (18), (14), (15) and (16) become: ##EQU10## and can be substituted into equation (10) to obtain the parameter a in the following form: ##EQU11## Therefore, the orthogonal parameters of the least-squares straight line are expressed by the following equation by using equation (19), taking T.sub.k (b)=bT.sub.k (1)=0 into consideration: ##EQU12## If the normalized feature parameters are expressed by C.sub.k.sup.g, the normalizing equation (7) becomes: ##EQU13## In short, the parameters a and the orthogonal parameters for the least-squares straight line can be developed by equations (20) and (21), and the normalization can be conducted in accordance with equation (22).

On ther other hand, when the COSINE transform is used as the orthogonal transformation, i.e., the orthogonal transformation is conducted by the following equation: ##EQU14## the equations (17), (18), (14), (15) and (16) become: ##EQU15## and can be substituted into equation (10) to obtain the parameter a in the following form: ##EQU16## Therefore, the orthogonal parameters of the least-squares straight line are expressed by the following equation: ##EQU17## and the normalizing equation (7) becomes: ##EQU18## In short, the parameter a and the orthogonal parameters for the least-squares straight line can be computed by equation (24) and (25), and the normalization can be conducted in accordance with equation (26).

The present invention will now be described in connection with its specific applications. FIG. 1 shows an example in which the present invention is applied to a speech recognition system using cepstrum data as the feature parameters.

An input utterance SPEECH IN of electric signals is subjected to frequency analysis in a frequency analyzer 1 such as an n-channel filter bank or an 2n-point FFT circuit to obtain spectral data. This spectral data is logarithmically converted by a log. converter 2 and is then stored in a buffer memory 3. Spectral data f.sub.i is read out from the buffer memory 3 in accordance with a signal i from a controller 9, and is sent to a first orthogonal transformer 4.

An inverse Fourier transform is used as the orthogonal transformation of the first transformer to develop the cepstrum data. In the first orthogonal transformer 4, the input pattern f.sub.i is first subjected to an inverse Fourier transformation, as expressed by equation (19), so that the feature parameters C.sub.k.sup.f are developed and stored in buffer memory 5. Then, in a second orthogonal transformer 6, the orthogonal parameters T.sub.k (a.multidot.i+b) of the least-squares straight line is developed, as expressed in equations (20) and (21), from the orthogonal parameters C.sub.k.sup.f of the input pattern which have been read from the buffer memory. The orthogonal parameters of the least-squares straight line are stored in a buffer memory 7. A subtracter 8, on the basis of signals read out from buffer memories 5 and 7, subtracts the orthogonal parameters of the least-squares straight line from the orthogonal parameters of the input pattern, as expressed by equation (22), so that normalized feature parameters C.sub.k.sup.g are determined.

FIG. 2A is a block diagram showing the construction of a specific example of the first orthogonal transformer 4. A cosine table 414 and a sine table 418 are tables containing cosine values and sine values expressed by cos 2k.pi./n and sine 2k.pi./n, respectively, wherein k=1 to n. In response to a signal k.sub.i from the controller 9, cosine or sine values are output to a multiplier 411 or 415, respectively. The spectral data read out from the buffer memory 3 in accordance with the signal i is input to the orthogonal transformer 4. The controller 9 generates signals i, k.sub.i and cl.sub.1 according to the timing chart shown in FIG. 2B. The signal i varies from 1 to n, and these variations are repeated m times to obtain a total of m orthogonal parameters (T.sub.1, T.sub.2, . . . , T.sub.m). The signal cl.sub.1 is output to accumulators 413 and 417, immediately before the signal i reaches 1, to reset their stored values to zero. The signal k.sub.i is a value R[k.multidot.i,n], where R[ ] is the remainder of a division by n, for i=1 to n and k=1 to m. This is because all the values of cos 2ki.pi./n and sin 2ki.pi./n can be obtained from the n values for a certain period, since sine and cosine are periodic functions. Namely, as the signal k.sub.i, signals are generated which have values 1, 2, . . . , n; 2, 4, . . . , R[2n]; k, R[2k], . . . , R[nk]; and m, R[2m], . . . , and R[nm]. The signals f.sub.i are read out consecutively in accordance with the signal i, for i=1 to n from the buffer memory 3 and are supplied to the multipliers 411 and 415. In accordance with the signal k.sub.i, moreover, the values cos 2ki.pi./n and sin 2ki.pi./n are read out from the cosine table 414 and the sine table 418, respectively, and are supplied to the multipliers 411 and 415, respectively. These multipliers 411 and 415 respectively obtain f.sub.i .multidot.cos 2ki.pi./n and f.sub.i .multidot.sin 2ki.pi./n. The adders 412 and 416 respectively determine ##EQU19## from the outputs of the multipliers 411 and 415. When the value of the signal i becomes equal to n, the real part R.sub.e (C.sub.k.sup.f) and imaginary part I.sub.m (C.sub.k.sup.f) of the Fourier (or orthogonal) parameters are obtained in the accumulators 413 and 417.

FIG. 3A is a block diagram showing a specific construction of the second orthogonal transformer 6. The imaginary parts I.sub.m (C.sub.k.sup.f) of the Fourier parameters for k=1 to m, which are read out from the buffer memory 5 in response to the signal k (1 to m) from the controller 9, are sent to the divider 611. The signals from the controller 9 relating to the second orthogonal transformer 6 are k, l, i.sub.2 and cl.sub.2, as shown in FIG. 3B. The signal k varies from 1 to m, the signals l and i.sub.2 are generated after the end of the supply of the signals k and l, respectively, and also vary from 1 to m. The signal cl.sub.2 is used for clearing the content in an accumulator 613. The imaginary parts I.sub.m (C.sub.k.sup.f) are read out consecutively in accordance with the signal k for k=1 to m from the buffer memory 5, and the quotient I.sub.m (C.sub.k.sup.f)/k is obtained by a divider 611. The summation ##EQU20## is obtained through an adder 612 and the accumulator 613. The summation is divided in a divider 614 by a constant ##EQU21## from a constant memory 615 to determine a value na which is n times as large as the parameter a of the least-squares straight line expressed by equation (20). The signal l is then input as a divisor to a divider 616 so that the value na/l, i.e., the imaginary part of the orthogonal parameter of the least-squares straight line expressed by equation (21) is determined. On the other hand, the real part of the orthogonal parameter of the least-square straight line is zero, as expressed by equation (21). The orthogonal parameters thus determined are stored in the buffer memory 7.

The subtractor 8 is a unit in which the normalization is achieved by subtracting the orthogonal parameters T.sub.k (a.multidot.i+b) of the least-squares straight line from the orthogonal parameters T.sub.k (f.sub.i) generated by the first orthogonal transformer 4, as expressed by equation (7) or (7'). The buffer memories 5 and 7 temporarily store m orthogonal parameters T.sub.k (f.sub.i) and T.sub.k (a.multidot.i+b) obtained by the first and second orthogonal transformers 4 and 6, respectively. In response to a signal i.sub.2 from the controller 9, consequently, the parameters T.sub.k (f.sub.i) and T.sub.k (a.multidot.i+b) are read out from the buffer memories 5 and 7, respectively, and are subjected to a subtraction operation so that the normalized parameters T.sub.k (f.sub.i)-T.sub.k (a.multidot.i+b) are determined.

In the embodiment thus far described, the sine term of the inverse Fourier transform of equation (19) can be zero, if the spectral data is expressed by an even function. Therefore the inverse Fourier transform is substantially identical to the cosine transform, simplifying the circuit construction. A second embodiment is an example in which the cosine transform is used as the orthogonal transformation. The second embodiment has a basic construction substantially identical to that of FIG. 1 but it differs somewhat in the first and second orthogonal transformers 4 and 6. Specifically, the first orthogonal transformer 4 subjects the input pattern f.sub.i to a cosine transform according to equation (23) to develop the feature parameters C.sub.k.sup.f or the orthogonal parameters. The second orthogonal transformer 6 develop the orthogonal parameters T.sub.k (a.multidot.i+b) of the least-squares straight line from the orthogonal parameters C.sub.k.sup.f of the input pattern, as expressed in equations (24) and (25). The subtractor 8 subtracts the orthogonal parameters of the least-squares straight line from the orthogonal parameters of the input pattern, as expressed by equation (26), to determine the normalized feature parameters C.sub.k.sup.g.

FIG. 4 is a block diagram showing a specific construction of the first orthogonal transformer 4 effecting the cosine transform. In this embodiment, the sine table 418, the multiplier 415 for the sine calculation, the adder 416 and the accumulator 417 are omitted from the first orthogonal transformer 4 for the Fourier transform in the first embodiment. The operations are identical to those of the first embodiment except for the first orthogonal transformer 4 and two points that will be described in the following. The first difference residues in the cosine values which are stored in the cosine table 414. Specifically, the cosine table 414 stores a number 2n of cosine values, i.e., cos k.pi./n wherein k=1 to 2n. The second difference resides in the signal k.sub.i. Specifically, the signal k.sub.i is a value R[k.multidot.i, 2n], wherein R [ ] is the remainder of a division by 2n, for i=1 to n and k=1 to m.

FIG. 5A is a block diagram showing a specific construction of the second orthogonal transformer 6. The odd terms C.sub.k.sup.f (k=1, 3, . . . , m) of the orthogonal parameters, i.e., the output of the first orthogonal transformer 4, are temporarily stored in the buffer memory 5. After that, in accordance with the timing chart of FIG. 5B, signals k, k.sub.2 and l.sub.2 are generated by the controller 9. Here, the signal k varies over only the odd numbers 1 to m, the signal k.sub.2 has the value k.sup.2, and the signal l.sub.2 has a value l.sup.2 which varies over the odd numbers l=1 to m. A signal cl.sub.3 is used for clearing the content of an accumulator 513. The odd terms C.sub.k.sup.f are read out consecutively in accordance with the signal k for k=1, 3, . . . , m from the buffer memory 5, and the quotient C.sub.k /k.sup.2 is obtained by a divider 511. The summation of the outputs of the divider 511 ##EQU22## (wherein k=2k'-1 and m=2m'1) is obtained through an adder 512 and the accumulator 513. A division is conducted in a divider 514 by a constant ##EQU23## from a constant memory 515 to develop -na/2.pi. which is -n/2.pi. times as large as the parameter a of the least-squares straight line expressed by equation (24). Subsequently, in accordance with the signal l.sub.2, the value l.sup.2 is given as the divisor to a divider 516 so that a value -an/2l.sup.2 .pi., i.e., the odd term of the least-squares straight line expressed by equation (25), is obtained. On the other hand, the even term of the orthogonal parameter a of the least-squares straight line is zero, as expressed by equation (25). The subsequent normalization is conducted in the subtractor 8 in the same way as in the embodiment of FIG. 1.

Although the present invention has been described hereinbefore in connection with embodiments thereof, it should not have its scope limited by those descriptions. Particularly in the description of the principles of the present invention, it is assumed that the orthogonal parameters T.sub.k (f.sub.i) in equations (10) to (16) for developing the parameters a and b of the least-squares straight line are equal to the orthogonal parameters T.sub.k (f.sub.i) in equation (7) for conducting the normalization. Nevertheless, the least-squares straight line can also be prepared by a method in which they are determined from the average of a plurality of input patterns, i.e., a method in which the pattern f.sub.i used in equations (10) to (16) is replaced in the calculations with an average pattern f.sub.i of the multiple input patterns. It is also natural that the aforementioned Walsh-Hadamard or KL transforms can be used as the orthogonal transformation. Furthermore, the present invention should not be limited to speech recognition but can naturally be applied to other pattern recognitions.