In
mathematicsMathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
,
deconvolution is an
algorithm-basedIn mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
process used to reverse the effects of
convolutionIn mathematics and, in particular, functional analysis, convolution is a mathematical operation on two functions f and g, producing a third function that is typically viewed as a modified version of one of the original functions. Convolution is similar to cross-correlation...
on recorded data. The concept of deconvolution is widely used in the techniques of
signal processingSignal processing is an area of systems engineering, electrical engineering and applied mathematics that deals with operations on or analysis of signals, in either discrete or continuous time...
and
image processingIn electrical engineering and computer science, image processing is any form of signal processing for which the input is an image, such as a photograph or video frame; the output of image processing may be either an image or, a set of characteristics or parameters related to the image...
. Because these techniques are in turn widely used in many
scientificScience is a systematic enterprise that builds and organizes knowledge in the form of testable explanations and predictions about the universe...
and
engineeringEngineering is the discipline, art, skill and profession of acquiring and applying scientific, mathematical, economic, social, and practical knowledge, in order to design and build structures, machines, devices, systems, materials and processes that safely realize improvements to the lives of...
disciplines, deconvolution finds many applications.
In general, the object of deconvolution is to find the solution of a convolution equation of the form:
-
Usually,
h is some recorded signal, and
ƒ is some signal that we wish to recover, but has been convolved with some other signal
g before we recorded it. The function
g might represent the
transfer functionA transfer function is a mathematical representation, in terms of spatial or temporal frequency, of the relation between the input and output of a linear time-invariant system. With optical imaging devices, for example, it is the Fourier transform of the point spread function i.e...
of an instrument or a driving force that was applied to a physical system. If we know
g, or at least know the form of
g, then we can perform deterministic deconvolution. However, if we do not know
g in advance, then we need to estimate it. This is most often done using methods of
statisticalStatistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....
estimationEstimation theory is a branch of statistics and signal processing 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 value affects the distribution of the...
.
In physical measurements, the situation is usually closer to
-
In this case
ε is noise that has entered our recorded signal. If we assume that a noisy signal or image is noiseless when we try to make a statistical estimate of
g, our estimate will be incorrect. In turn, our estimate of
ƒ will also be incorrect. The lower the
signal-to-noise ratioSignal-to-noise ratio is a measure used in science and engineering that compares the level of a desired signal to the level of background noise. It is defined as the ratio of signal power to the noise power. A ratio higher than 1:1 indicates more signal than noise...
, the worse our estimate of the deconvolved signal will be. That is the reason why usually
inverse filterIn all proposed models for the production of human speech, an important variable is the waveform of the airflow, or volume velocity, at the glottis. The glottal volume velocity waveform provides the link between movements of the vocal folds and the acoustical results of such movements, in that the...
ing the signal is not a good solution. However, if we have at least some knowledge of the type of noise in the data (for example,
white noiseWhite noise is a random signal with a flat power spectral density. In other words, the signal contains equal power within a fixed bandwidth at any center frequency...
), we may be able to improve the estimate of
ƒ through techniques such as
Wiener deconvolutionIn mathematics, Wiener deconvolution is an application of the Wiener filter to the noise problems inherent in deconvolution. It works in the frequency domain, attempting to minimize the impact of deconvoluted noise at frequencies which have a poor signal-to-noise ratio.The Wiener deconvolution...
.
The foundations for deconvolution and time-series analysis were largely laid by
Norbert WienerNorbert Wiener was an American mathematician.A famous child prodigy, Wiener later became an early researcher in stochastic and noise processes, contributing work relevant to electronic engineering, electronic communication, and control systems.Wiener is regarded as the originator of cybernetics, a...
of the
Massachusetts Institute of TechnologyThe Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...
in his book
Extrapolation, Interpolation, and Smoothing of Stationary Time Series (1949). The book was based on work Wiener had done during
World War IIWorld War II, or the Second World War , was a global conflict lasting from 1939 to 1945, involving most of the world's nations—including all of the great powers—eventually forming two opposing military alliances: the Allies and the Axis...
but that had been classified at the time. Some of the early attempts to apply these theories were in the fields of
weather forecastingWeather forecasting is the application of science and technology to predict the state of the atmosphere for a given location. Human beings have attempted to predict the weather informally for millennia, and formally since the nineteenth century...
and
economicsEconomics is the social science that analyzes the production, distribution, and consumption of goods and services. The term economics comes from the Ancient Greek from + , hence "rules of the house"...
.
Seismology
The concept of deconvolution had an early application in
reflection seismologyReflection seismology is a method of exploration geophysics that uses the principles of seismology to estimate the properties of the Earth's subsurface from reflected seismic waves. The method requires a controlled seismic source of energy, such as dynamite/Tovex, a specialized air gun or a...
. In 1950, Enders Robinson was a graduate student at MIT. He worked with others at MIT, such as
Norbert WienerNorbert Wiener was an American mathematician.A famous child prodigy, Wiener later became an early researcher in stochastic and noise processes, contributing work relevant to electronic engineering, electronic communication, and control systems.Wiener is regarded as the originator of cybernetics, a...
,
Norman LevinsonNorman Levinson was an American mathematician. Some of his major contributions were in the study of Fourier transforms, complex analysis, non-linear differential equations, number theory, and signal processing. He worked closely with Norbert Wiener in his early career...
, and economist
Paul SamuelsonPaul Anthony Samuelson was an American economist, and the first American to win the Nobel Memorial Prize in Economic Sciences. The Swedish Royal Academies stated, when awarding the prize, that he "has done more than any other contemporary economist to raise the level of scientific analysis in...
, to develop the "convolutional model" of a reflection seismogram. This model assumes that the recorded
seismogramA seismogram is a graph output by a seismograph. It is a record of the ground motion at a measuring station as a function of time. Seismograms typically record motions in three cartesian axes , with the z axis perpendicular to the Earth's surface and the x- and y- axes parallel to the surface...
s(
t) is the convolution of an Earth-reflectivity function
e(
t) and a seismic wavelet
w(
t) from a
point sourceA point source is a localised, relatively small source of something.Point source may also refer to:*Point source , a localised source of pollution**Point source water pollution, water pollution with a localized source...
, where
t represents recording time. Thus, our convolution equation is
The seismologist is interested in
e, which contains information about the Earth's structure. By the
convolution theoremIn mathematics, the convolution theorem states that under suitableconditions the Fourier transform of a convolution is the pointwise product of Fourier transforms. In other words, convolution in one domain equals point-wise multiplication in the other domain...
, this equation may be
Fourier transformIn mathematics, Fourier analysis is a subject area which grew from the study of Fourier series. The subject began with the study of the way general functions may be represented by sums of simpler trigonometric functions...
ed to
-
in the
frequency domainIn electronics, control systems engineering, and statistics, frequency domain is a term used to describe the domain for analysis of mathematical functions or signals with respect to frequency, rather than time....
. By assuming that the reflectivity is white, we can assume that the
power spectrumIn statistical signal processing and physics, the spectral density, power spectral density , or energy spectral density , is a positive real function of a frequency variable associated with a stationary stochastic process, or a deterministic function of time, which has dimensions of power per hertz...
of the reflectivity is constant, and that the power spectrum of the seismogram is the spectrum of the wavelet multiplied by that constant. Thus,
-
If we assume that the wavelet is
minimum phaseIn control theory and signal processing, a linear, time-invariant system is said to be minimum-phase if the system and its inverse are causal and stable....
, we can recover it by calculating the minimum phase equivalent of the power spectrum we just found. The reflectivity may be recovered by designing and applying a
Wiener filterIn signal processing, the Wiener filter is a filter proposed by Norbert Wiener during the 1940s and published in 1949. Its purpose is to reduce the amount of noise present in a signal by comparison with an estimation of the desired noiseless signal. The discrete-time equivalent of Wiener's work was...
that shapes the estimated wavelet to a
Dirac delta functionThe Dirac delta function, or δ function, is a generalized function depending on a real parameter such that it is zero for all values of the parameter except when the parameter is zero, and its integral over the parameter from −∞ to ∞ is equal to one. It was introduced by theoretical...
(i.e., a spike). The result may be seen as a series of scaled, shifted delta functions (although this is not mathematically rigorous):
-
,
where
N is the number of reflection events,
τ i τ i are the reflection times of each event, and
r i are the
reflection coefficientThe reflection coefficient is used in physics and electrical engineering when wave propagation in a medium containing discontinuities is considered. A reflection coefficient describes either the amplitude or the intensity of a reflected wave relative to an incident wave...
s.
In practice, since we are dealing with noisy, finite
bandwidthIn computer networking and computer science, bandwidth, network bandwidth, data bandwidth, or digital bandwidth is a measure of available or consumed data communication resources expressed in bits/second or multiples of it .Note that in textbooks on wireless communications, modem data transmission,...
, finite length, discretely sampled datasets, the above procedure only yields an approximation of the filter required to deconvolve the data. However, by formulating the problem as the solution of a
Toeplitz matrixIn linear algebra, a Toeplitz matrix or diagonal-constant matrix, named after Otto Toeplitz, is a matrix in which each descending diagonal from left to right is constant...
and using
Levinson recursionLevinson recursion or Levinson-Durbin recursion is a procedure in linear algebra to recursively calculate the solution to an equation involving a Toeplitz matrix...
, we can relatively quickly estimate a filter with the smallest
mean squared errorIn statistics, the mean squared error of an estimator is one of many ways to quantify the difference between values implied by a kernel density estimator and the true values of the quantity being estimated. MSE is a risk function, corresponding to the expected value of the squared error loss or...
possible. We can also do deconvolution directly in the frequency domain and get similar results. The technique is closely related to
linear predictionLinear prediction is a mathematical operation where future values of a discrete-time signal are estimated as a linear function of previous samples....
.
Optics and other imaging
In optics and imaging, the term "deconvolution" is specifically used to refer to the process of reversing the optical distortion that takes place in an optical
microscopeA microscope is an instrument used to see objects that are too small for the naked eye. The science of investigating small objects using such an instrument is called microscopy...
,
electron microscopeAn electron microscope is a type of microscope that uses a beam of electrons to illuminate the specimen and produce a magnified image. Electron microscopes have a greater resolving power than a light-powered optical microscope, because electrons have wavelengths about 100,000 times shorter than...
,
telescopeA telescope is an instrument that aids in the observation of remote objects by collecting electromagnetic radiation . The first known practical telescopes were invented in the Netherlands at the beginning of the 1600s , using glass lenses...
, or other imaging instrument, thus creating clearer images. It is usually done in the digital domain by a software
algorithmIn mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
, as part of a suite of
microscope image processingMicroscope image processing is a broad term that covers the use of digital image processing techniques to process, analyze and present images obtained from a microscope. Such processing is now commonplace in a number of diverse fields such as medicine, biological research, cancer research, drug...
techniques. Deconvolution is also practical to sharpen images that suffer from fast motion or jiggles during capturing. Early
Hubble Space TelescopeThe Hubble Space Telescope is a space telescope that was carried into orbit by a Space Shuttle in 1990 and remains in operation. A 2.4 meter aperture telescope in low Earth orbit, Hubble's four main instruments observe in the near ultraviolet, visible, and near infrared...
images were distorted by a flawed mirror and could be sharpened by deconvolution.
The usual method is to assume that the optical path through the instrument is optically perfect, convolved with a
point spread functionThe point spread function describes the response of an imaging system to a point source or point object. A more general term for the PSF is a system's impulse response, the PSF being the impulse response of a focused optical system. The PSF in many contexts can be thought of as the extended blob...
(PSF), that is, a mathematical function that describes the distortion in terms of the pathway a theoretical
point sourceA point source is a localised, relatively small source of something.Point source may also refer to:*Point source , a localised source of pollution**Point source water pollution, water pollution with a localized source...
of light (or other waves) takes through the instrument. Usually, such a point source contributes a small area of fuzziness to the final image. If this function can be determined, it is then a matter of computing its
inverseIn mathematics, an inverse function is a function that undoes another function: If an input x into the function ƒ produces an output y, then putting y into the inverse function g produces the output x, and vice versa. i.e., ƒ=y, and g=x...
or complementary function, and convolving the acquired image with that. The result is the original, undistorted image.
In practice, finding the true PSF is impossible, and usually an approximation of it is used, theoretically calculated or based on some experimental estimation by using known probes. Real optics may also have different PSFs at different focal and spatial locations, and the PSF may be non-linear. The accuracy of the approximation of the PSF will dictate the final result. Different algorithms can be employed to give better results, at the price of being more computationally intensive. Since the original convolution discards data, some algorithms use additional data acquired at nearby focal points to make up some of the lost information.
RegularizationIn mathematics and statistics, particularly in the fields of machine learning and inverse problems, regularization involves introducing additional information in order to solve an ill-posed problem or to prevent overfitting...
in iterative algorithms (as in
expectation-maximization algorithmIn statistics, an expectation–maximization algorithm is an iterative method for finding maximum likelihood or maximum a posteriori estimates of parameters in statistical models, where the model depends on unobserved latent variables...
s) can be applied to avoid unrealistic solutions.
When the PSF is unknown, it may be possible to deduce it by systematically trying different possible PSFs and assessing whether the image has improved. This procedure is called
blind deconvolutionIn image processing and applied mathematics, blind deconvolution is a deconvolution technique that permits recovery of the target scene from a single or set of "blurred" images in the presence of a poorly determined or unknown point spread function ....
. Blind deconvolution is a well-established image restoration technique in
astronomyAstronomy is a natural science that deals with the study of celestial objects and phenomena that originate outside the atmosphere of Earth...
, where the point nature of the objects photographed exposes the PSF thus making it more feasible. It is also used in fluorescence microscopy for image restoration, and in fluorescence
spectral imagingSpectral imaging is a branch of spectroscopy and of photography in which a complete spectrum or some spectral information is collected at every location in an image plane...
for spectral separation of multiple unknown
fluorophoreA fluorophore, in analogy to a chromophore, is a component of a molecule which causes a molecule to be fluorescent. It is a functional group in a molecule which will absorb energy of a specific wavelength and re-emit energy at a different wavelength...
s. The most common
iterativeIteration means the act of repeating a process usually with the aim of approaching a desired goal or target or result. Each repetition of the process is also called an "iteration," and the results of one iteration are used as the starting point for the next iteration.-Mathematics:Iteration in...
algorithm for the purpose is the Richardson–Lucy deconvolution algorithm; the
Wiener deconvolutionIn mathematics, Wiener deconvolution is an application of the Wiener filter to the noise problems inherent in deconvolution. It works in the frequency domain, attempting to minimize the impact of deconvoluted noise at frequencies which have a poor signal-to-noise ratio.The Wiener deconvolution...
(and approximations) are the most common non-iterative algorithms.
Radio astronomy
When performing image synthesis in radio
interferometryInterferometry refers to a family of techniques in which electromagnetic waves are superimposed in order to extract information about the waves. An instrument used to interfere waves is called an interferometer. Interferometry is an important investigative technique in the fields of astronomy,...
, a specific kind of
radio astronomyRadio astronomy is a subfield of astronomy that studies celestial objects at radio frequencies. The initial detection of radio waves from an astronomical object was made in the 1930s, when Karl Jansky observed radiation coming from the Milky Way. Subsequent observations have identified a number of...
, one step consists of deconvolving the produced image with the "dirty beam", which is a different name for the
point spread functionThe point spread function describes the response of an imaging system to a point source or point object. A more general term for the PSF is a system's impulse response, the PSF being the impulse response of a focused optical system. The PSF in many contexts can be thought of as the extended blob...
. A common used method is the
CLEAN algorithmThe CLEAN algorithm is a computational algorithm to perform a deconvolution on images created in radio astronomy. It was published by Jan Högbom in 1974 and several variations have been proposed since then ....
.
See also
- Digital filter
In electronics, computer science and mathematics, a digital filter is a system that performs mathematical operations on a sampled, discrete-time signal to reduce or enhance certain aspects of that signal. This is in contrast to the other major type of electronic filter, the analog filter, which is...
- Filter (signal processing)
In signal processing, a filter is a device or process that removes from a signal some unwanted component or feature. Filtering is a class of signal processing, the defining feature of filters being the complete or partial suppression of some aspect of the signal...
- Filter design
Filter design is the process of designing a filter , often a linear shift-invariant filter, that satisfies a set of requirements, some of which are contradictory...
- Minimum phase
In control theory and signal processing, a linear, time-invariant system is said to be minimum-phase if the system and its inverse are causal and stable....
- Independent component analysis
Independent component analysis is a computational method for separating a multivariate signal into additive subcomponents supposing the mutual statistical independence of the non-Gaussian source signals...
- Wiener deconvolution
In mathematics, Wiener deconvolution is an application of the Wiener filter to the noise problems inherent in deconvolution. It works in the frequency domain, attempting to minimize the impact of deconvoluted noise at frequencies which have a poor signal-to-noise ratio.The Wiener deconvolution...
- Richardson–Lucy deconvolution
- Digital room correction
Digital room correction is a process in the field of acoustics where digital filters designed to ameliorate unfavorable effects of a room's acoustics are applied to the input of a sound reproduction system...
- Free deconvolution
Free convolution is the free probability analog of the classical notion of convolution of probability measures. Due to the non-commutative nature of free probability theory, one has to talk separately about additive and multiplicative free convolution, which arise from addition and multiplication...
- Point spread function
The point spread function describes the response of an imaging system to a point source or point object. A more general term for the PSF is a system's impulse response, the PSF being the impulse response of a focused optical system. The PSF in many contexts can be thought of as the extended blob...
External links
Presentations
Tutorials and techniques
Software
Other