The effects associated with the switching of filter orders in an incrementally adaptive IIR approximate filtering technique are evaluated in the context of speech signals. Through listening experiments, we have found that the perceptual quality of the speech at the filter output is sensitive to the initial conditions used in initiating a transition to a higher filter order. If zero initial conditions are used there is a significant crackling sound due to error bursts at points where switches to higher order filters take place. If output samples from the pre-transition filter are used as initial conditions for the post-transition filter, the amplitude of the error bursts decreases significantly. An analysis is presented to account for these observations.

We present an approach to the extraction of frequencies corresponding to chords in western polyphonic music. In the first phase of this approach constant-Q spectral analysts directly provides the features from which the fundamental frequencies for 43 of the 57 possible categories of chords can be extracted without ambiguity. Each remaining chord category has a potential ambiguity associated with it because of frequency resolution problems The second phase of our approach is designed to address such ambiguities. A software implementation of our approach was used successfully to validate its performance on a representative set of polyphonic musical signals.

Abstract We show how conceptual and architectural tools from AI may be incorporated into the solution of a complex signal processing problem in a musical application. Signals in this application have multiple components with possible overlap in the time–frequency plane. The challenge here is to carry out time–frequency analysis in a manner that allows the various components to be separated from each other. Such time–frequency analysis may be performed by using a filterbank in which the analysis filters are adapted in a data-dependent fashion to separately resolve individual signal components. While there exists a numerical solution for performing analysis filter adaptation through the use of a time–frequency energy concentration measure, this solution suffers from the drawback that it is computationally very inefficient. Furthermore, this solution also does not incorporate knowledge about the time–frequency properties of musical signals. We present a novel solution to the filter adaptation problem that while incorporating higher-level knowledge about musical signals also results in at least an order of magnitude computational savings over the numerical solution. Our solution has been designed on the basis of the IPUS architecture that allows the easy integration of musical knowledge with numerical signal processing algorithms. We have also carried out an implementation of our IPUS-based solution within ICP, a C++ platform for building IPUS applications. The performance of our implementation in separating individual components from musical signals containing a mixture of two notes illustrates its potential for use in a variety of applications.

We illustrate how high-level knowledge from the musical domain may be integrated with sophisticated signal processing algorithms within a system for separating possibly overlapping partial frequency components from polyphonic music. Musical knowledge utilized in our system is in the form of constraints on the time-frequency behavior of musical signals such as the frequency locations of notes on the western musical scale and the presence or absence of vibrato in each note. For any given signal scenario, these constraints help in appropriately initializing and adjusting a set of algorithms for constant-Q processing, spectral peak picking, and multihypothesis tracking through Kalman filtering. As demonstrated by the evaluation of our system with a variety of signals containing two simultaneously played violin notes, the application of these algorithms results in the accurate separation of individual partials.

We present a probabilistic complexity analysis of a class of multi-stage algorithms for computing successive approximations to the DFT. While the quality of the approximate spectra obtained after any stage of these algorithms can be readily quantified in terms of commonly used input-independent metrics of spectral quality, each stage's arithmetic complexity is dependent on the nature of the input signal. Modeling the input signal as a stationary Gaussian-distributed random process, we obtain estimates of the distribution of the number of arithmetic operations required to complete any algorithm stage. This enables the derivation of important design information such as the probability with which a desired quality of approximation is achieved within a given arithmetic bound. Our results are verified using a Monte Carlo analysis.

In the context of FFT-based maximum-likelihood (ML) detection of a complex sinusoid in noise, we consider the result of terminating the FFT at an intermediate stage of computation and applying the ML detection strategy to its unfinished results. We show that detection performance increases monotonically with the number of FFT stages completed, converging ultimately to that of the exact ML detector. The receiver operating characteristic associated with the completion of each FFT stage is derived. This enables the calculation of the minimum number of FFT stages that must be completed in order for desired detection and false alarm probabilities to be obtained.

The exponential rate operator (ERO) is presented for determining the "instantaneous exponential rate" of the amplitude modulation during musical transients. Its extension to multiband signal representations such as STFT and wavelet transforms is also described. Sensitivity of the ERO to white noise is examined and computational efficiency of the STFT-based ERO is discussed. Examples involving synthetic and real musical transients illustrate the usefulness of ERO analysis.

A framework for approximate signal processing is introduced which can be used to design novel classes of algorithms for performing DFT and STFT calculations. In particular, we focus on the derivation of multi-stage incremental refinement algorithms that meet a variety of design criteria on the tradeoff achieved at each stage between solution quality and computational cost.

A new environment for the rapid development of embedded signal processing software is described. The environment encourages incremental design via modular and hierarchical structuring of applications, and additional features are included which support the prototyping, testing, implementation, and integration stages of the system design cycle. Written in C++, the environment is comprised of a scripting language for the definition of system components and a class library which includes a basic application framework. Support is provided for incorporating both numeric and symbolic signal representations, as well as integrating multiple signal processing techniques within a single application. A sophisticated control mechanism allows dynamic scheduling of signal processing operations according to algorithmically defined schema. Signal processing applications developed in this environment are themselves objects, and are suitable for embedding within a larger overall system.

The Integrated Processing and Understanding of Signals (IPUS) architecture is presented as a framework that exploits formal signal processing models to structure the bidirectional interaction between front-end signal processing and signal understanding processes. This architecture is appropriate for complex environments, which are characterized by variable signal-to-noise ratios, unpredictable source behaviors, and the simultaneous occurrence of objects whose signal signatures can distort each other. A key aspect of this architecture is that front-end signal processing is dynamically modifiable in response to scenario changes and to the need to reanalyze ambiguous or distorted data. The architecture tightly integrates the search for the appropriate front-end signal processing configuration with the search for plausible interpretations. In our opinion, this dual search, informed by formal signal processing theory, is a necessary component of perceptual systems that must interact with complex environments. To explain this architecture in detail, we discuss examples of its use in an implemented system for acoustic signal interpretation.

We present a class of multistage algorithms for carrying out incremental refinement of DFT and STFT approximations. Each stage is designed to improve the previous stage's approximation in terms of frequency coverage, frequency resolution, and SNR. These algorithms rely almost exclusively on vector summation operations, and they can be designed to exhibit a variety of tradeoffs between improvement in approximation quality and computational cost per stage. The performance of incremental STFT refinement on real data serves to illustrate the relevance of such algorithms to application systems with dynamic real-time constraints.>

We present a technique for improving the performance of a method for estimating the time-varying fundamental frequency (pitch) of a musical signal corrupted by interference components. The original method, developed by M. Piszczalski and B.A. Galler (1979), involves the calculation and comparison of frequency-pair ratios from each spectrum within a time-frequency transform of the corrupted signal. As the strength of the interference components is increased, the frequency estimates from this method become more unreliable. To obtain improved performance we developed a transform conditioning procedure that enhances the harmonic signal's spectral components in a constant-Q transform prior to the calculation of frequency-pair ratios. This transform conditioning technique is based on a method we have previously developed for principal decomposition analysis of time-frequency transforms.>

In this paper, we present techniques for computing frame-adaptive approximations to the STFT which can satisfy arbitrarily specified bounds on the number of arithmetic operations per frame. The central idea is to represent the samples in each signal frame with a very small number Q of quantization levels, yielding an SNR of 10Iog(Q/sup 2/) dB. This leads to the formulation of the frame's DFT computation as a process of summation among pre-stored vectors. Experimental studies are used to propose and verify mathematical models for how the number of vector additions needed in this process depends on the frequency content of a frame. The models are utilized to design frame-adaptive techniques for excluding various subsets of vector elements from the summation process in order to keep the number of additions per frame from exceeding any specified bound, B.>

We show that the discrete short-time Fourier transform with temporal decimation (DSTFT-TD) can be evaluated using a variety of pruned FFT structures. A pruning method we refer to as overlap pruning can be used to eliminate computational overlap between consecutive FFT's for computing slices of the DSTFT-TD. When only a limited frequency range of the DSTFT-TD is of interest, further computational savings can be achieved by combining overlap pruning with classical frequency pruning. We evaluate the complexity of the overlap and frequency pruned FFT's for the DSTFT-TD in terms of the number of complex multiplications and additions required for the computation of each DSTFT-TD slice.>

The authors describe and demonstrate how the combined use of Wigner and short-time Fourier transform (STFT) processing can be used to advantage in a sound understanding application. Specifically, the Wigner processing of a signal is used for alerting the signal understanding system to the possibility of inadequate time or frequency resolution in the STFT processing of the same signal. The signal understanding system may then reprocess the signal with an STFT with a different window length. The knowledge-based control required for carrying out such signal processing is available in a sound understanding system in the context of which this research was carried out.>

The authors extend their previous work (Nawab and Lesser, 1991; Weiss et al., 1991) on model variety analysis of a signal processing algorithm with respect to the class of all input signals that may potentially arise in a given signal understanding application. This analysis has two related objectives. The first objective is to partition the set of all possible signals in the application domain into two sets according to whether each signal is correctly or incorrectly processed by the signal processing algorithm under consideration. The second objective of model variety analysis is to characterize the nature of the distortions in the signal processing output for the cases where the input signal is incorrectly processed. The results of model variety analysis are useful for designing signal understanding systems for applications where it is necessary for the signal processing to be carried out in a situation-dependent manner. Model variety analysis and its usefulness for the design of signal understanding systems are illustrated through examples involving the use of short-time Fourier transform (STFT) processing for a sound understanding application.>

The authors introduce a novel time-frequency representation, the principal short-time Fourier transform (PSTFT), as a reduced-data characterization of the nonstationary spectral content of a sequence. To form the PSTFT, the authors apply principal components analysis to STFT frequency slices and retain only the first principal component information. This information alone allows for exact reconstruction of the original sequence from its PSTFT representation. The PSTFT retains explicit information about the nonstationary spectral content of a sequence, as well as implicit information necessary for reconstruction of the sequence. The results obtained are extended to other time-frequency distributions, which include the Wigner-Ville distribution, the complex energy density, and the radar ambiguity function.>

The authors address the problem of passive acoustic tracking from closest point of approach (CPA) time, amplitude and frequency data at spatially distributed sensors in the case of finite sound propagation delay. A method is presented for the computation of source velocity (speed and direction) from the CPA times at three noncollinear sensors that lie on the same side of the source path. The method reduces the problem to the solution of a linear trigonometric equation, and can be used as the basis for robust localization of a straight source path using a square grid of calibrated sensors. In the case of a maneuvering source, qualitative relations are stated between the local shape of the source path, its relative position with respect to an acoustic sensor, and whether amplitude and frequency increase or decrease monotonically with (source) time at that sensor. These qualitative relations from multiple sensors are then used to segment the source path into straight and maneuvering segments (under negligible propagation delay).>

The problem of ringing sound (e.g. telephone, alarm clock, etc.) classification is addressed. A time-domain model, exhibiting the phenomenon of interference is found to have behavior similar to that exhibited by a telephone ringing sound. This motivates a frequency-domain production model which asserts that ringing sounds can be modeled as bandpass-filtered white noise, where the filter has a power spectral density in the form of isosceles triangles. A parameter estimation technique based on this model is found to provide enough information to classify ringing sounds.>

A technique is presented for matching 3-D object models to a segmented region of an image taken from an unknown viewer direction. An appearance graph is defined to capture the appearance variations with viewpoint. The appearance graphs are created at multiple levels of abstraction, allowing for orientation determination from noisy images. The method for searching the appearance graphs for the most appropriate viewpoint consists of reducing feature differences between a given aspect and the segmented region at a given level of abstraction. Both the representation techniques and the search method are described, as well as a system implementing these methods.>

Many signal-processing systems can be viewed as transforming their input signals into a representation of the real-world scenario from which the signals originated. Such systems usually have parameters whose settings are selected on the basis of the class of expected input scenarios. Finding the appropriate parameter settings for a class of input scenarios usually involves testing the system against typical and/or important input scenarios from that class. Whenever the system output does not match the input scenario, the parameter settings responsible for the fault are identified. The system user can then adjust the system parameters to ensure correct system behavior for such scenarios. The diagnostic process of identifying the parameters responsible for system faults is generally difficult because the signal-processing system carries out a complicated mathematical transformation involving a multistage algorithm that generates an enormous amount of intermediate data. A new approach to the diagnosis of such systems is developed. The approach is based on the availability of an abstract and possibly qualitative description of the input scenario and the use of an alternative system model derived from the underlying mathematical theory that explicitly represents the phenomena responsible for any incorrect processing. This approach to diagnosis models a system as a combination of processes that transform the user-specified abstract description of the input scenario into the system output. Whenever the correct answer is obtained at the system output, each process reduces to an identity transformation at the level of abstraction of the system output.

Signal processing systems usually have parameters whose settings are selected on the basis of the class of expected input signals. Finding the appropriate parameter settings for a class of inputs usually involves testing the system against typical and/or important inputs from that class. Whenever the system produces an incorrect output, the parameter settings responsible for the fault are identified. The system user can then adjust the system parameters in order to ensure correct system behavior. The diagnostic process of identifying the parameters responsible for system faults is generally difficult because the signal processing system carries out a complicated mathematical transformation involving a multi-stage algorithm that generates an enormous amount of intermediate data. We develop a new approach to the diagnosis of such systems. The approach is based on the availability of an abstract and possibly qualitative description of the input scenario and the use of an alternative system model derived from the underlying mathematical theory that explicitly represents the phenomena responsible for any incorrect processing.

A signal processing system which integrates signal and symbol processing was designed and initial implementation experiments were performed. The system design was derived from the systematic observation (protocol collection) and analysis of human signal processing activity. The resulting system consists of (i) expert rules, which process symbolic representations of signal characteristics at various levels of abstraction, and (ii) signal processing operators, which are invoked by the rules to extract signal features. This design parallels the apparent operational mode of a human analyst. The signal processing operators include those used by the human expert (e.g. FFT) and others that perform perceptual feature extraction normally done by the expert while reviewing plots of numeric algorithmic outputs. In comparison to previous signal/symbol processing systems, which relied mostly on symbol processing, our system is based on the concept that a small amount of planned signal processing can save a lot of symbol processing.

A computationally efficient sensor array processing method has been developed for detection and bearing estimation of wideband planewave sources above or below a planar array of sensors. The method uses the time-averaged covariances of undelayed sensor signals to estimate the wavenumber spectrum in the array plane. This spectrum contains directional information as well as wideband temporal frequency characteristics of the planewave sources. The usefulness of this method for an acoustic aircraft tracking problem is demonstrated with experiments on real data.

We have previously established a number of conditions under which a real signal can be uniquely reconstructed from its STFT magnitude. For the STFT magnitude to be a practical signal representation, we need robust reconstruction algorithms. In this paper, we discuss such a class of algorithms within the framework of sequential extrapolation techniques. Such techniques reconstruct the short-time sections of a signal in an order determined by their positions on the time axis. We find that compared to direct reconstruction, the robust algorithms are less sensitive to roundoff errors. To further test the robustness of these algorithms, we applied them to STFT magnitudes which were purposely modified for accomplishing signal processing tasks such as noise reduction and time-scale modification of speech.

This paper presents various conditions that are sufficient for reconstructing a discrete-time signal from samples of its short-time Fourier transform magnitude. For applications such as speech processing, these conditions place very mild restrictions on the signal as well as the analysis window of the transform. Examples of such reconstruction for speech signals are included in the paper.

Major artifacts of the spectral subtraction signal restoration technique are the presence of harmonic patterns and blurring effects for images, and the presence of short tone bursts of varying frequency for speech signals. In this paper, we discuss several techniques developed to reduce these artifacts. Examples are shown to illustrate the performance of these techniques.

Arithmetic concurrencies, such as those found in special-purpose fast Fourier transform (FFT) hard-ware, are surveyed and categorized. Similar structures are then derived for the Winograd Fourier transform algorithm (WFTA). Relative time-efficiency plots are obtained for the 1024-point radix-4 FFT and the 1008-point WFTA as a function of the number of real arithmetic operations executable in parallel. This comparison shows that the relative time efficiency of the two algorithms in sequential computations generally carries over to cases where arithmetic parallelism is exploited.