In
signal processing
Signal processing is an electrical engineering subfield that focuses on analyzing, modifying and synthesizing '' signals'', such as sound, images, and scientific measurements. Signal processing techniques are used to optimize transmissions, ...
, a nonlinear (or non-linear) filter is a
filter whose output is not a
linear function
In mathematics, the term linear function refers to two distinct but related notions:
* In calculus and related areas, a linear function is a function whose graph is a straight line, that is, a polynomial function of degree zero or one. For di ...
of its input. That is, if the filter outputs
signal
In signal processing, a signal is a function that conveys information about a phenomenon. Any quantity that can vary over space or time can be used as a signal to share messages between observers. The '' IEEE Transactions on Signal Processing' ...
s ''R'' and ''S'' for two input signals ''r'' and ''s'' separately, but does not always output ''αR'' + ''βS'' when the input is a
linear combination ''αr'' + ''βs''.
Both continuous-domain and discrete-domain filters may be nonlinear. A simple example of the former would be an electrical device whose output
voltage
Voltage, also known as electric pressure, electric tension, or (electric) potential difference, is the difference in electric potential between two points. In a static electric field, it corresponds to the work needed per unit of charge t ...
''R''(''t'') at any moment is the square of the input voltage ''r''(''t''); or which is the input clipped to a fixed range
'a'',''b'' namely ''R''(''t'') = max(''a'', min(''b'', ''r''(''t''))). An important example of the latter is the
running-median filter, such that every output sample ''R''
''i'' is the
median of the last three input samples ''r''
''i'', ''r''
''i''−1, ''r''
''i''−2. Like linear filters, nonlinear filters may be
shift invariant or not.
Non-linear filters have many applications, especially in the removal of certain types of
noise
Noise is unwanted sound considered unpleasant, loud or disruptive to hearing. From a physics standpoint, there is no distinction between noise and desired sound, as both are vibrations through a medium, such as air or water. The difference aris ...
that are not
additive. For example, the median filter is widely used to remove
spike noise
Spike, spikes, or spiking may refer to:
Arts, entertainment, and media
Books
* ''The Spike'' (novel), a novel by Arnaud de Borchgrave
* ''The Spike'' (book), a nonfiction book by Damien Broderick
* ''The Spike'', a starship in Peter F. Hamilto ...
— that affects only a small percentage of the samples, possibly by very large amounts. Indeed, all
radio receiver
In radio communications, a radio receiver, also known as a receiver, a wireless, or simply a radio, is an electronic device that receives radio waves and converts the information carried by them to a usable form. It is used with an antenna. T ...
s use non-linear filters to convert
kilo-
Kilo is a decimal unit prefix in the metric system denoting multiplication by one thousand (103). It is used in the International System of Units, where it has the symbol k, in lowercase.
The prefix ''kilo'' is derived from the Greek word ( ...
to
gigahertz
The hertz (symbol: Hz) is the unit of frequency in the International System of Units (SI), equivalent to one event (or cycle) per second. The hertz is an SI derived unit whose expression in terms of SI base units is s−1, meaning that one ...
signals to the
audio
Audio most commonly refers to sound, as it is transmitted in signal form. It may also refer to:
Sound
*Audio signal, an electrical representation of sound
*Audio frequency, a frequency in the audio spectrum
* Digital audio, representation of soun ...
frequency range; and all
digital signal processing
Digital signal processing (DSP) is the use of digital processing, such as by computers or more specialized digital signal processors, to perform a wide variety of signal processing operations. The digital signals processed in this manner ar ...
depends on non-linear filters (
analog-to-digital converter
In electronics, an analog-to-digital converter (ADC, A/D, or A-to-D) is a system that converts an analog signal, such as a sound picked up by a microphone or light entering a digital camera, into a digital signal. An ADC may also provide ...
s) to transform
analog signal
An analog signal or analogue signal (see spelling differences) is any continuous signal representing some other quantity, i.e., ''analogous'' to another quantity. For example, in an analog audio signal, the instantaneous signal voltage vari ...
s to
binary number
A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" ( zero) and "1" (one).
The base-2 numeral system is a positional notati ...
s.
However, nonlinear filters are considerably harder to use and design than linear ones, because the most powerful mathematical tools of signal analysis (such as the
impulse response
In signal processing and control theory, the impulse response, or impulse response function (IRF), of a dynamic system is its output when presented with a brief input signal, called an impulse (). More generally, an impulse response is the reac ...
and the
frequency response
In signal processing and electronics, the frequency response of a system is the quantitative measure of the magnitude and phase of the output as a function of input frequency. The frequency response is widely used in the design and analysis of s ...
) cannot be used on them. Thus, for example, linear filters are often used to remove noise and distortion that was created by nonlinear processes, simply because the proper non-linear filter would be too hard to design and construct.
From the foregoing, we can know that the nonlinear filters have quite different behavior compared to linear filters. The most important characteristic is that, for nonlinear filters, the filter output or response of the filter does not obey the principles outlined earlier, particularly scaling and shift invariance. Furthermore, a nonlinear filter can produce results that vary in a non-intuitive manner.
Linear system
Several principles define a
linear system
In systems theory, a linear system is a mathematical model of a system based on the use of a linear operator.
Linear systems typically exhibit features and properties that are much simpler than the nonlinear case.
As a mathematical abstracti ...
. The basic definition of
linearity
Linearity is the property of a mathematical relationship ('' function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear ...
is that the output must be a linear function of the inputs, that is
:
for any
scalar values
and
.
This is a fundamental property of linear system design, and is known as superposition. So, a system is said to be nonlinear if this equation is not valid. That is to say, when the system is linear, the superposition principle can be applied. This important fact is the reason that the techniques of linear-system analysis have been so well developed.
Applications
Noise removal
Signals often get corrupted during transmission or processing; and a frequent goal in filter design is the restoration of the original signal, a process commonly called "noise removal". The simplest type of corruption is additive noise, when the desired signal ''S'' gets added with an unwanted signal ''N'' that has no known connection with ''S''. If the noise ''N'' has a simple statistical description, such as
Gaussian noise
Gaussian noise, named after Carl Friedrich Gauss, is a term from signal processing theory denoting a kind of signal noise that has a probability density function (pdf) equal to that of the normal distribution (which is also known as the Gaussian ...
, then a
Kalman filter
For statistics and control theory, Kalman filtering, also known as linear quadratic estimation (LQE), is an algorithm that uses a series of measurements observed over time, including statistical noise and other inaccuracies, and produces estima ...
will reduce ''N'' and restore ''S'' to the extent allowed by
Shannon's theorem. In particular, if ''S'' and ''N'' do not overlap in the
frequency domain
In physics, electronics, control systems engineering, and statistics, the frequency domain refers to the analysis of mathematical functions or signals with respect to frequency, rather than time. Put simply, a time-domain graph shows how a ...
, they can be completely separated by linear
bandpass filters.
For almost any other form of noise, on the other hand, some sort of non-linear filter will be needed for maximum signal recovery. For
multiplicative noise
In signal processing, the term multiplicative noise refers to an unwanted random signal that gets multiplied into some relevant signal during capture, transmission, or other processing.
An important example is the speckle noise commonly observed ...
(that gets multiplied by the signal, instead of added to it), for example, it may suffice to convert the input to a
logarithmic scale
A logarithmic scale (or log scale) is a way of displaying numerical data over a very wide range of values in a compact way—typically the largest numbers in the data are hundreds or even thousands of times larger than the smallest numbers. Such a ...
, apply a linear filter, and then convert the result to
linear scale
A linear scale, also called a bar scale, scale bar, graphic scale, or graphical scale, is a means of visually showing the scale of a map, nautical chart, engineering drawing, or architectural drawing. A scale bar is common element of map layo ...
. In this example, the first and third steps are not linear.
Non-linear filters may also be useful when certain "nonlinear" features of the signal are more important than the overall information contents. In
digital image processing
Digital image processing is the use of a digital computer to process digital images through an algorithm. As a subcategory or field of digital signal processing, digital image processing has many advantages over analog image processing. It allow ...
, for example, one may wish to preserve the sharpness of
silhouette
A silhouette ( , ) is the image of a person, animal, object or scene represented as a solid shape of a single colour, usually black, with its edges matching the outline of the subject. The interior of a silhouette is featureless, and the silhou ...
edges of objects in photographs, or the connectivity of lines in scanned drawings. A linear noise-removal filter will usually blur those features; a non-linear filter may give more satisfactory results (even if the blurry image may be more "correct" in the information-theoretic sense).
Many nonlinear noise-removal filters operate in the time domain. They typically examine the input digital signal within a finite window surrounding each sample, and use some statistical inference model (implicitly or explicitly) to estimate the most likely value for the original signal at that point. The design of such filters is known as the
filtering problem for a
stochastic process in
estimation theory
Estimation theory is a branch of statistics that deals with estimating the values of parameters based on measured empirical data that has a random component. The parameters describe an underlying physical setting in such a way that their val ...
and
control theory
Control theory is a field of mathematics that deals with the control of dynamical systems in engineered processes and machines. The objective is to develop a model or algorithm governing the application of system inputs to drive the system to a ...
.
Examples of nonlinear filters include:
*
phase-locked loop
A phase-locked loop or phase lock loop (PLL) is a control system that generates an output signal whose phase is related to the phase of an input signal. There are several different types; the simplest is an electronic circuit consisting of a ...
s
*
detector
A sensor is a device that produces an output signal for the purpose of sensing a physical phenomenon.
In the broadest definition, a sensor is a device, module, machine, or subsystem that detects events or changes in its environment and sends ...
s
*
mixers
*
median filter
The median filter is a non-linear digital filtering technique, often used to remove noise from an image or signal. Such noise reduction is a typical pre-processing step to improve the results of later processing (for example, edge detection on ...
s
*
ranklet
In statistics, a ranklet is an orientation-selective non-parametric feature which is based on the computation of Mann–Whitney–Wilcoxon (MWW) rank-sum test statistics. Ranklets achieve similar response to Haar wavelets as they share the same ...
s
Nonlinear filter also occupy a decisive position in the image processing functions. In a typical pipeline for real-time image processing, it is common to have many nonlinear filter included to form, shape, detect, and manipulate image information. Furthermore, each of these filter types can be parameterized to work one way under certain circumstances and another way under a different set of circumstance using adaptive filter rule generation. The goals vary from noise removal to feature abstraction. Filtering image data is a standard process used in almost all image processing systems. Nonlinear filters are the most utilized forms of filter construction. For example, if an image contains a low amount of noise but with relatively high magnitude, then a median filter may be more appropriate.
Kushner–Stratonovich filtering
The problem of optimal nonlinear filtering was solved in the late 1950s and early 1960s by
Ruslan L. Stratonovich
Ruslan Leont'evich Stratonovich (russian: Русла́н Лео́нтьевич Страто́нович) was a Russian physicist, engineer, and probabilist and one of the founders of the theory of stochastic differential equations.
Biography
R ...
and
Harold J. Kushner.
The Kushner–Stratonovich solution is a
stochastic partial differential equation
Stochastic partial differential equations (SPDEs) generalize partial differential equations via random force terms and coefficients, in the same way ordinary stochastic differential equations generalize ordinary differential equations.
They hav ...
. In 1969,
Moshe Zakai introduced a simplified dynamics for the unnormalized conditional law of the filter known as
Zakai equation.
It has been proved by
Mireille Chaleyat-Maurel
Mireille () is a French given name, derived from the Provençal Occitan name ''Mirèio'' (or ''Mirèlha'' in the classical norm of Occitan, ). It could be related to the Occitan verb ''mirar'' "to look, to admire" or to the given names ''Miriam'' " ...
and
Dominique Michel that the solution is infinite dimensional in general, and as such requires finite dimensional approximations. These may be heuristics-based such as the
extended Kalman filter or the
assumed density filters described by
Peter S. Maybeck or the
projection filter
Projection, projections or projective may refer to:
Physics
* Projection (physics), the action/process of light, heat, or sound reflecting from a surface to another in a different direction
* The display of images by a projector
Optics, graphic ...
s introduced by
Damiano Brigo,
Bernard Hanzon
Bernard (''Bernhard'') is a French and West Germanic masculine given name. It is also a surname.
The name is attested from at least the 9th century. West Germanic ''Bernhard'' is composed from the two elements ''bern'' "bear" and ''hard'' "brave ...
and
François Le Gland, some sub-families of which are shown to coincide with the
assumed density filters.
Energy transfer filters
Energy transfer filters
In physics, energy (from Ancient Greek: ἐνέργεια, ''enérgeia'', “activity”) is the quantitative property that is transferred to a body or to a physical system, recognizable in the performance of work and in the form of heat an ...
are a class of nonlinear dynamic filters that can be used to move energy in a designed manner.
[Billings S.A.]
Nonlinear System Identification: NARMAX Methods in the Time, Frequency, and Spatio-Temporal Domains
. Wiley, 2013 Energy can be moved to higher or lower frequency bands, spread over a designed range, or focused. Many energy transfer filter designs are possible, and these provide extra degrees of freedom in filter design that are just not possible using linear designs.
See also
*
Moving horizon estimation
*
Nonlinear system
In mathematics and science, a nonlinear system is a system in which the change of the output is not proportional to the change of the input. Nonlinear problems are of interest to engineers, biologists, physicists, mathematicians, and many other ...
*
Particle filter
Particle filters, or sequential Monte Carlo methods, are a set of Monte Carlo algorithms used to solve filtering problems arising in signal processing and Bayesian statistical inference. The filtering problem consists of estimating the int ...
* Unscented Kalman filter section in
Kalman filter
For statistics and control theory, Kalman filtering, also known as linear quadratic estimation (LQE), is an algorithm that uses a series of measurements observed over time, including statistical noise and other inaccuracies, and produces estima ...
References
Further reading
*
{{refend
External links
Prof. Ilya Shmulevich page on nonlinear signal processing
Filter theory