Systolic building block for high performance recursive filtering

A novel bit level systolic array is presented that can be used as a building block in the construction of recursive digital filters. The circuit accepts bit-parallel input data, is pipelined at the bit level, and exhibits a very high throughput rate. The most important feature of the circuit is that it allows recursive operations to be implemented directly without incurring the large m cycle latency (where m is approximately the word length) normally associated with such systems. The use of this circuit in the construction of both first- and second-order IIR (infinite-impulse-response) filters is described.

Algorithms and architectures for high performance recursive filtering

Recently, a number of most significant digit (msd) first bit parallel multipliers for recursive filtering have been reported. However, the design approach which has been used has, in general, been heuristic and consequently, optimality has not always been assured. In this paper, msd first multiply accumulate algorithms are described and important relationships governing the dependencies between latency, number representations, etc are derived. A more systematic approach to designing recursive filters is illustrated by applying the algorithms and associated relationships to the design of cascadable modules for high sample rate IIR filtering and wave digital filtering.

Recursive filtering of images with symmetric extension

Recursive filters are widely used in image analysis due to their efficiency and simple implementation. However these filters have an initialisation problem which either produces unusable results near the image boundaries or requires costly approximate solutions such as extending the boundary manually. In this paper, we describe a method for the recursive filtering of symmetrically extended images for filters with symmetric denominator. We begin with an analysis of symmetric extensions and their effect on non-recursive filtering operators. Based on the non-recursive case, we derive a formulation of recursive filtering on symmetric domains as a linear but spatially varying implicit operator. We then give an efficient method for decomposing and solving the linear implicit system, along with a proof that this decomposition always exists. This decomposition needs to be performed only once for each dimension of the image. This yields a filtering which is both stable and consistent with the ideal infinite extension. The filter is efficient, requiring less computation than the standard recursive filtering. We give experimental evidence to verify these claims. (c) 2005 Elsevier B.V. All rights reserved.

A recursive approach to space resection using straight lines

An approach using straight lines as features to solve the photogrammetric space resection problem is presented. An explicit mathematical model relating straight lines, in both object and image space, is used. Based on this model, Kalman Filtering is applied to solve the space resection problem. The recursive property of the filter is used in an iterative process which uses the sequentially estimated camera location parameters to feedback to the feature extraction process in the image. This feedback process leads to a gradual reduction of the image space for feature searching, and consequently eliminates the bottleneck due to the high computational cost of the image segmentation phase. It also enables feature extraction and the determination of feature correspondence in image and object space in an automatic way, i.e., without operator interference. Results obtained from simulated and real data show that highly accurate space resection parameters are obtained as well as a progressive processing time reduction. The obtained accuracy, the automatic correspondence process, and the short related processing time show that the proposed approach can be used in many real-time machine vision systems, making possible the implementation of applications not feasible until now.

Development and simulation of DSP filters for transformer differential protection / by Oskar Reynisson.

Transformer protection is one of the most challenging applications within the power system protective relay field. Transformers with a capacity rating exceeding 10 MVA are usually protected using differential current relays. Transformers are an aging and vulnerable bottleneck in the present power grid; therefore, quick fault detection and corresponding transformer de-energization is the key element in minimizing transformer damage. Present differential current relays are based on digital signal processing (DSP). They combine DSP phasor estimation and protective-logic-based decision making. The limitations of existing DSP-based differential current relays must be identified to determine the best protection options for sensitive and quick fault detection. The development, implementation, and evaluation of a DSP differential current relay is detailed. The overall goal is to make fault detection faster without compromising secure and safe transformer operation. A detailed background on the DSP differential current relay is provided. Then different DSP phasor estimation filters are implemented and evaluated based on their ability to extract desired frequency components from the measured current signal quickly and accurately. The main focus of the phasor estimation evaluation is to identify the difference between using non-recursive and recursive filtering methods. Then the protective logic of the DSP differential current relay is implemented and required settings made in accordance with transformer application. Finally, the DSP differential current relay will be evaluated using available transformer models within the ATP simulation environment. Recursive filtering methods were found to have significant advantage over non-recursive filtering methods when evaluated individually and when applied in the DSP differential relay. Recursive filtering methods can be up to 50% faster than non-recursive methods, but can cause false trip due to overshoot if the only objective is speed. The relay sensitivity is however independent of filtering method and depends on the settings of the relay’s differential characteristics (pickup threshold and percent slope).

Bayesian filtering over compressed appearance states

This paper presents a framework for performing real-time recursive estimation of landmarks’ visual appearance. Imaging data in its original high dimensional space is probabilistically mapped to a compressed low dimensional space through the definition of likelihood functions. The likelihoods are subsequently fused with prior information using a Bayesian update. This process produces a probabilistic estimate of the low dimensional representation of the landmark visual appearance. The overall filtering provides information complementary to the conventional position estimates which is used to enhance data association. In addition to robotics observations, the filter integrates human observations in the appearance estimates. The appearance tracks as computed by the filter allow landmark classification. The set of labels involved in the classification task is thought of as an observation space where human observations are made by selecting a label. The low dimensional appearance estimates returned by the filter allow for low cost communication in low bandwidth sensor networks. Deployment of the filter in such a network is demonstrated in an outdoor mapping application involving a human operator, a ground and an air vehicle.

Recursive actuator fault detection and diagnosis for emergency landing of UASs

This paper presents a practical recursive fault detection and diagnosis (FDD) scheme for online identification of actuator faults for unmanned aerial systems (UASs) based on the unscented Kalman filtering (UKF) method. The proposed FDD algorithm aims to monitor health status of actuators and provide indication of actuator faults with reliability, offering necessary information for the design of fault-tolerant flight control systems to compensate for side-effects and improve fail-safe capability when actuator faults occur. The fault detection is conducted by designing separate UKFs to detect aileron and elevator faults using a nonlinear six degree-of-freedom (DOF) UAS model. The fault diagnosis is achieved by isolating true faults by using the Bayesian Classifier (BC) method together with a decision criterion to avoid false alarms. High-fidelity simulations with and without measurement noise are conducted with practical constraints considered for typical actuator fault scenarios, and the proposed FDD exhibits consistent effectiveness in identifying occurrence of actuator faults, verifying its suitability for integration into the design of fault-tolerant flight control systems for emergency landing of UASs.

On Fast Bilateral Filtering Using Fourier Kernels

It was demonstrated in earlier work that, by approximating its range kernel using shiftable functions, the nonlinear bilateral filter can be computed using a series of fast convolutions. Previous approaches based on shiftable approximation have, however, been restricted to Gaussian range kernels. In this work, we propose a novel approximation that can be applied to any range kernel, provided it has a pointwise-convergent Fourier series. More specifically, we propose to approximate the Gaussian range kernel of the bilateral filter using a Fourier basis, where the coefficients of the basis are obtained by solving a series of least-squares problems. The coefficients can be efficiently computed using a recursive form of the QR decomposition. By controlling the cardinality of the Fourier basis, we can obtain a good tradeoff between the run-time and the filtering accuracy. In particular, we are able to guarantee subpixel accuracy for the overall filtering, which is not provided by the most existing methods for fast bilateral filtering. We present simulation results to demonstrate the speed and accuracy of the proposed algorithm.

Single camera pose estimation using Bayesian filtering and Kinect motion priors

Traditional approaches to upper body pose estimation using monocular vision rely on complex body models and a large variety of geometric constraints. We argue that this is not ideal and somewhat inelegant as it results in large processing burdens, and instead attempt to incorporate these constraints through priors obtained directly from training data. A prior distribution covering the probability of a human pose occurring is used to incorporate likely human poses. This distribution is obtained offline, by fitting a Gaussian mixture model to a large dataset of recorded human body poses, tracked using a Kinect sensor. We combine this prior information with a random walk transition model to obtain an upper body model, suitable for use within a recursive Bayesian filtering framework. Our model can be viewed as a mixture of discrete Ornstein-Uhlenbeck processes, in that states behave as random walks, but drift towards a set of typically observed poses. This model is combined with measurements of the human head and hand positions, using recursive Bayesian estimation to incorporate temporal information. Measurements are obtained using face detection and a simple skin colour hand detector, trained using the detected face. The suggested model is designed with analytical tractability in mind and we show that the pose tracking can be Rao-Blackwellised using the mixture Kalman filter, allowing for computational efficiency while still incorporating bio-mechanical properties of the upper body. In addition, the use of the proposed upper body model allows reliable three-dimensional pose estimates to be obtained indirectly for a number of joints that are often difficult to detect using traditional object recognition strategies. Comparisons with Kinect sensor results and the state of the art in 2D pose estimation highlight the efficacy of the proposed approach.

Bit-level systolic arrays for IIR filtering.

A novel bit-level systolic array architecture for implementing IIR (infinite-impulse response) filter sections is presented. A first-order section achieves a latency of only two clock cycles by using a radix-2 redundant number representation, performing the recursive computation most significant digit first, and feeding back each digit of the result as soon as it is available. The design is extended to produce a building block from which second- and higher-order sections can be connected.

Systolic two-port adaptor for high performance wave digital filtering

The authors present a VLSI circuit for implementing wave digital filter (WDF) two-port adaptors. Considerable speedups over conventional designs have been obtained using fine grained pipelining. This has been achieved through the use of most significant bit (MSB) first carry-save arithmetic, which allows systems to be designed in which latency L is small and independent of either coefficient or input data wordlength. L is determined by the online delay associated with the computation required at each node in the circuit (in this case a multiply/add plus two separate additions). This in turn means that pipelining can be used to considerably enhance the sampling rate of a recursive digital filter. The level of pipelining which will offer enhancement is determined by L and is fine-grained rather than bit level. In the case of the circuit considered, L = 3. For this reason pipeline delays (half latches) have been introduced between every two rows of cells to produce a system with a once every cycle sample rate.

Polyphase Implementation of Non-recursive Comb Decimators for Sigma-Delta A/D Converters

In a sigma-delta analog to digital (A/D) As most of the sigma-delta ADC applications require converter, the most computationally intensive block is decimation filters with linear phase characteristics, the decimation filter and its hardware implementation symmetric Finite Impulse Response (FIR) filters are may require millions of transistors. Since these widely used for implementation. But the number of FIR converters are now targeted for a portable application, filter coefficients will be quite large for implementing a a hardware efficient design is an implicit requirement. narrow band decimation filter. Implementing decimation In this effect, this paper presents a computationally filter in several stages reduces the total number of filter efficient polyphase implementation of non-recursive coefficients, and hence reduces the hardware complexity cascaded integrator comb (CIC) decimators for and power consumption [2]. Sigma-Delta Converters (SDCs). The SDCs are The first stage of decimation filter can be operating at high oversampling frequencies and hence implemented very efficiently using a cascade of integrators require large sampling rate conversions. The filtering and comb filters which do not require multiplication or and rate reduction are performed in several stages to coefficient storage. The remaining filtering is performed reduce hardware complexity and power dissipation. either in single stage or in two stages with more complex The CIC filters are widely adopted as the first stage of FIR or infinite impulse response (IIR) filters according to decimation due to its multiplier free structure. In this the requirements. The amount of passband aliasing or research, the performance of polyphase structure is imaging error can be brought within prescribed bounds by compared with the CICs using recursive and increasing the number of stages in the CIC filter. The non-recursive algorithms in terms of power, speed and width of the passband and the frequency characteristics area. This polyphase implementation offers high speed outside the passband are severely limited. So, CIC filters operation and low power consumption. The polyphase are used to make the transition between high and low implementation of 4th order CIC filter with a sampling rates. Conventional filters operating at low decimation factor of '64' and input word length of sampling rate are used to attain the required transition '4-bits' offers about 70% and 37% of power saving bandwidth and stopband attenuation. compared to the corresponding recursive and Several papers are available in literature that deals non-recursive implementations respectively. The same with different implementations of decimation filter polyphase CIC filter can operate about 7 times faster architecture for sigma-delta ADCs. Hogenauer has than the recursive and about 3.7 times faster than the described the design procedures for decimation and non-recursive CIC filters.

Improved robust Kalman filtering for uncertain systems with missing measurements

In this paper, a novel robust finite-horizon Kalman filter is developed for discrete linear time-varying systems with missing measurements and normbounded parameter uncertainties. The missing measurements are modelled by a Bernoulli distributed sequence and the system parameter uncertainties are in the state and output matrices. A two stage recursive structure is considered for the Kalman filter and its parameters are determined guaranteeing that the covariances of the state estimation errorsare not more than the known upper bound. Finally, simulation results are presented to illustrate the outperformance of the proposed robust estimator compared with the previous results in the literature.