Preprocessor for Spectral Pattern Classification Systems

The present invention pertains to a preprocessor for spectral pattern classification systems and the like. In general, spectral pattern classification systems are systems which classify spectral patterns, such as the frequency spectra of sounds or electromagnetic energy from various sources. Different categories of spectra may be defined in advance so that as a spectrum is received from each source it can be compared to the defined categories and properly classified.

A prior art method of obtaining the spectra from a desired source is to provide a plurality of samples of the source and take the discrete Fourier transform of the samples. Many fast versions of the discrete Fourier transform exist (e.g., the Cooley-Tukey, Winograd, Prime Factor, etc. algorithms), all of which produce the same result and are generally included in the term discrete Fourier transform. Two major problems exist with respect to the power spectrum obtained by means of the discrete Fourier transform. The first problem is that the values making up the spectra depend to an undersirable degree on the phase of the samples of the signal to be classified. The second problem is that the power spectrum derived from two sources that appear to be very similar (i.e., look similar on a spectrum analyzer) do not necessarily lie near one another in spectrum space. As an example, if the spectral patterns being classified are due to sounds coming from two difference sources, the power spectra may not be close to one another even though the sounds come from sources that sound almost alike. This situation might exist, for example, as the result of a modest amount of Doppler shift of one signal relative to the other.

The present invention pertains to a preprocessor for spectral pattern classification systems and the like which modifies the discrete Fourier transform to remove or reduce the phase dependency problem and to enhance the clustering of similar spectra. In at least one embodiment this is performed by weighting the time-domain samples before being processed by the individual filters that serve to define the frequency spectrum so that the frequency response of the selected stages is substantially defined by ##EQU2## where: k=0, .alpha., 2.alpha., 3.alpha., . . . , r.sup..alpha.

.alpha.=constant, 1<.alpha.<N/2

r+1=greatest integer in N/.alpha.

In this relationship, the frequency variable has been scaled so that 2.pi. radians/second corresponds to the signal sampling rate.

It is an object of the present invention to provide a new and improved preprocessor for spectral pattern classification systems and the like.

It is a further object of the present invention to provide a preprocessor for spectral pattern classification systems and the like wherein dependency on the phase of samples of the signal to be classified is removed or substantially reduced.

It is a further object of the present invention to provide a preprocessor for spectral pattern classsification systems wherein similar spectrum clustering is provided.

These and other objects of this invention will become apparent to those skilled in the art upon consideration of the accompanying specification, claims and drawings.

Referring to the drawings,

FIG. 1 illustrates the relationship of overlapping frequency response curves of the properly selected frequency channels;

FIG. 2 is the frequency response of a plurality of channel bandpass filter stages according to the present invention; and

FIG. 3 is a simplified block diagram of a preprocessor for spectral pattern classification systems and the like embodying the present invention.

The present invention is embodied in apparatus and a method for transforming blocks of one-dimensional (i.e., time) data into spectra in such a way that data block coming from similar sources will have spectra that are close to one another in spectrum space. Given N samples of data: ##EQU3## from a source, it is desired to convert these samples to a spectrum. The samples may be obtained from, for example, sensors which sense the sound of a device, sonar, radar doppler infrared sensors, heat sensors, etc. A standard method of converting the samples to a spectrum is to take the discrete Fourier transform of the samples. Two major problems exist with respect to the discrete Fourier transform power spectrum: (1) the resultant numbers depend to an undesirable degree on the phase of the samples and (2) the power spectrum vectors from two sample sets which are derived from two sources that appear similar in frequency space (such as on the scope of a spectrum analyzer) do not necessarily lie near one another in spectrum space.

The simplest answer to the problem of phase dependency is the introduction of a filter window. Such a filter window may be produced by providing a set of N numbers ##EQU4## that are used to carry out the operation

before performing the discrete Fourier transform. This operation produces reduced phase sensitivity for a variety of choices of the numbers w.sub.i.

The problem of similar spectrum clustering is more difficult. To make the problem precise, state the requirement that two single spectral line signals (represented by sample sets {x.sub.i } and {x.sub.i "}) that have their lines which are simple sine wave frequencies separated by a distance .DELTA. in frequency should have normalized spectral points P.sub.1 and P.sub.2 within an angle [.pi.(N-1)/.alpha..omega..sub.s ].DELTA. of one another, where .omega..sub.s is the sampling frequency at which the sample sets were obtained. This formula will hold true if and only if the frequency response of individual filters that serve to define the discrete power spectrum overlap exactly one-half the bandpass of adjacent filters. In order to form a good approximation to this desired behavior only a subset (K=0, .alpha., 2.alpha., . . . , r.alpha.) of the N frequency channels of the Fourier transform are used in forming the power spectrum. Further, the channel bandpass filters must be shaped, in voltage, like the functions H.sub.k.sup..alpha. (e.sup.j.omega.), K=0, .alpha., 2.alpha., 3.alpha., . . . , r.alpha.; so that as a single spectral line moves slightly between adjacent chosen spectral frequency bins the point representing the spectrum rotates slightly around the origin. Referring specifically to FIG. 1, where the sinusoidal power level P corresponds to the voltage level .sqroot.P, if the spectrum is represented by vector P in spectrum space,

then the frequency response curves of FIG. 1 are formed in accordance with equation (0) above and overlap as described. Values of .alpha. greater than 1 permit better approximation of the desired frequency response using a weighting window w.sub.n. However, for .alpha.>1 it requires .alpha. times as much sample data to achieve a given frequency resolution in the power spectrum as in the m=1 case. Thus, the choice of .alpha. is highly application dependent. Typical values are .alpha.=1, 2, 3, or 4. From FIG. 1 it can be seen that point P rotates in linear proportion to .DELTA.. Thus, spectra that are similar to one another get mapped into points that are close to one another.

The following formalizes the overall process and presents a minimum-mean-squared error solution to an approximation which exploits the efficiency of the discrete Fourier transform. To simplify the presentation, the case .alpha.=1 will be treated below. The modifications required for the .alpha.>1 case are simple and will be obvious to anyone skilled in the art.

The power versus frequency responses of the filters of the filter bank of FIG. 1 are given by ##EQU5## where k=0, 1, . . . , N-1, and where the notation e.sup.j.omega. is used in anticipation of a discrete-time implementation. To make the filter bank a useful pattern preprocessor, the outputs of each filter are detected at some instant of time. The numbers so collected are best conceptualized as a vector p=[p.sub.0, p.sub.1 . . . , p.sub.n-1 ].sup.t where p.sub.n is the detected output of the n-th filter. It is also necessary to provide insensitivity to overall signal level, since signal level does not contribute any useful information to the classifier which follows. This is accomplished by simply normalizing p, i.e., ##EQU6## is the Euclidean norm of any p.epsilon.IR .sup.r. This normalization then forces all vectors to lie on the unit hypersphere. Note that since all of the components of such vectors represent power (which is always non-negative), all of these vectors will point into the positive 2.sup.r -tant of IR .sup.r.

Since the filters in the filter bank described above and shown in FIG. 1 each have finite support in the frequency domain, i.e., they have strictly bandlimited transfer functions, they cannot be realized in practice. A useful approximation is afforded by the minimum mean-squared error (MSE) method. If H.sub.k (e.sup.j.omega.) is the complex-valued desired transfer function, then the optimum filter is that function H.sub.k (e.sup.j.omega.) which minimizes the mean-squared error. ##EQU7##

An optimal form of the described filter bank will be derived, and it will be shown that the discrete Fourier transform can be used to implement that filter bank.

We will use the fact that a periodic function is representable by a Fourier series. The usual formulas for the Fourier coefficients and the series are ##EQU8## respectively. Using these definitions, the Fourier coefficients for the k-th filter in the filter bank are ##EQU9## which are recognized collectively as being the impulse response of that filter. Evaluation of this integral is simplified by using the fact from Fourier theory that if a.sub.n are the coefficients for f(x), then a.sub.n e-.sup.jnx o are the coefficients for f(x-x.sub.o). Also, by breaking the integral into its real and imaginary parts and observing that the imaginary part has an odd-symmetric integrand and that the real part has an even-symmetric integrand, the integral may be expressed as ##EQU10## The corresponding frequency response for the k-th filter can then be written ##EQU11##

The impulse response above is not only infinite in extent, but is non-causal and therefore non-realizable. The theory of the convergence of Fourier series provides a minimum mean-squared error solution to the problem of the impulse response being infinite in extent. As is commonly known, the error specified above is minimized, for any specific value of N, by simply truncating the series, that is, ##EQU12## where it is assumed that N is an odd number. (A simple modification to the present derivation applies to the case where N is even.) The problem of non-causality is fixed by simply changing the time index n in the above equation so that it begins as 0, as is done in the next paragraph.

The contention that the discrete Fourier transform can be used to implement the above equation will now be proved. If the data sequence x(n), representing samples of the signal to be classified, is first weighted by a window function w(n), its discrete Fourier transform is given by ##EQU13## To compute the frequency response (in voltage) of the k-th "bin" of the discrete Fourier transform, i.e, its response to an N-point sequence which consists of samples of a sinusoid of arbitrary frequency, simply substitute x(m)=exp (j m). Assuming again that N is odd (similar comments hold if N is even), and changing indices according to n=m-(N-1)/2 to achieve causality as promised in the preceeding paragraph, gives the desired result, ##EQU14## Making the equivalence ##EQU15## or in other terms: ##EQU16## where n=0, 1, 2, . . . , N-1, comparison with the approximating frequency response H.sub.k (e.sup.j.omega.) given above shows that

The constant delay term and the constant multiplier term can easily be absorbed for exact equality, or merely ignored, as they essentially contribute a simple scale factor. In either case, ##EQU17## as desired.

Using equation 16, the actual frequency response of the synthesized filters become: ##EQU18## where N=number of filter stages, Referring specifically to FIG. 2, the frequency response of N channel bandpass filter stages constructed in accordance with the above approximation is illustrated. The frequency response of each channel bandpass filter stage is defined by equation (13) or equation (20) and the frequency response of adjacent filter stages overlap such that the outermost frequency passed is approximately equal to the center frequency of adjacent stages.

Referring specifically to FIG. 3, a preprocessor for spectral pattern classification systems embodying the present invention is illustrated. An input terminal 10 is connected to an analog to digital converter 11, the output of which is connected to an input of a word-wide shift register, generally designated 15. While the present embodiment is illustrated in digital form, hence the A-to-D converter 11, it will be understood by those skilled in the art that a complete analog version can be devised if desired and the present digital version is illustrated because of its simplicity and ease of understanding. The shift register 15 contains N stages so that a batch of N samples can be shifted into the register 15 before operating thereon. A memory 20 has N constants, w(0) to w(N-1), stored therein. A bank of N multipliers generally designated 25 are connected to the stages of the shift register 15 and the various constants stored in memory 20 so that the sample in each stage of the shift register is multiplied by one of the constants in one of the multipliers 25. The product of each constant or weight stored in memory 20 and the corresponding sample in shift register 15 is supplied to a storage unit 30 having N stages. Instead of separate storage unit 30 the product could be placed in the shift register 15 so as to replace the sample utilized to obtain the product. However, for simplicity, a separate storage unit 30 is illustrated herein. The products stored in the storage unit 30 are then supplied to unit 35 which takes the discrete Fourier transform of the batch of products, computes the complex absolute value (power) in each of the discrete Fourier transform "bins" or synthesized filters, and, treating the batch of N resulting numbers as an N-dimensional vector, normalizes it so that it has a known length, e.g., one. The net result is to pass the signal at the terminal 10 through a filter bank of N stages having a frequency response as illustrated in FIG. 2 and to sample the output of each filter. The spectral features or samples are available at the output of the unit 35 and are supplied to a spectral classifier for comparison with previous samples, known samples, or other processing. The timing of the various components illustrated in FIG. 3 can be such that new samples are being entered into shift register 15 as the discrete Fourier transform is being taken of the previously obtained products. The constants stored in memory 20 are calculated in accordance with equations (10), (12) and (16) above, to within a scale factor.

Thus, an improved preprocessor for spectral pattern classification systems is disclosed, which preprocessor is designed to supply conditioned spectra to a spectral pattern classification system. The conditioning operation carried out by the preprocessor introduces reduced sensitivity to small changes in spectral line positions and amplitudes that would lead to significant distortions of a normal power spectrum. The preprocessor also normalizes the conditioned spectrum so as to introduce insensitivity to absolute signal power. The preprocessor can be used to increase the classification accuracy of radar, sonar, acoustic, magnetic, seismic, and speech spectrum classifiers.

While we have shown and described a specific embodiment of this invention, further modifications and improvements will occur to those skilled in the art. We desire it to be understood, therefore, that this invention is not limited to the particular form shown and we intend in the appended claims to cover all modifications which do not depart from the spirit and scope of this invention.