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, ...
, particularly
image processing
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimension ...
, total variation denoising, also known as total variation regularization or total variation filtering, is a noise removal process (
filter
Filter, filtering or filters may refer to:
Science and technology
Computing
* Filter (higher-order function), in functional programming
* Filter (software), a computer program to process a data stream
* Filter (video), a software component tha ...
). It is based on the principle that signals with excessive and possibly spurious detail have high ''
total variation
In mathematics, the total variation identifies several slightly different concepts, related to the ( local or global) structure of the codomain of a function or a measure. For a real-valued continuous function ''f'', defined on an interval ...
'', that is, the integral of the absolute
image gradient
An image gradient is a directional change in the intensity or color in an image. The gradient of the image is one of the fundamental building blocks in image processing. For example, the Canny edge detector uses image gradient for edge detection. ...
is high. According to this principle, reducing the total variation of the signal—subject to it being a close match to the original signal—removes unwanted detail whilst preserving important details such as
edges. The concept was pioneered by L. I. Rudin,
S. Osher, and E. Fatemi in 1992 and so is today known as the ''ROF model''.
This noise removal technique has advantages over simple techniques such as
linear smoothing or
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 ...
ing which reduce noise but at the same time smooth away edges to a greater or lesser degree. By contrast, total variation denoising is remarkably effective
edge-preserving filter, i.e., simultaneously preserving edges whilst smoothing away noise in flat regions, even at low signal-to-noise ratios.
1D signal series
For a
digital signal , we can, for example, define the total variation as
:
Given an input signal
, the goal of total variation denoising is to find an approximation, call it
, that has smaller total variation than
but is "close" to
. One measure of closeness is the sum of square errors:
:
So the total-variation denoising problem amounts to minimizing the following discrete functional over the signal
:
:
By differentiating this functional with respect to
, we can derive a corresponding
Euler–Lagrange equation
In the calculus of variations and classical mechanics, the Euler–Lagrange equations are a system of second-order ordinary differential equations whose solutions are stationary points of the given action functional. The equations were discovered ...
, that can be numerically integrated with the original signal
as initial condition. This was the original approach.
[ Alternatively, since this is a ]convex function
In mathematics, a real-valued function is called convex if the line segment between any two points on the graph of the function lies above the graph between the two points. Equivalently, a function is convex if its epigraph (the set of poin ...
al, techniques from convex optimization
Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets (or, equivalently, maximizing concave functions over convex sets). Many classes of convex optimization prob ...
can be used to minimize it and find the solution .
Regularization properties
The regularization
Regularization may refer to:
* Regularization (linguistics)
* Regularization (mathematics)
* Regularization (physics)
* Regularization (solid modeling)
* Regularization Law, an Israeli law intended to retroactively legalize settlements
See also ...
parameter plays a critical role in the denoising process. When , there is no smoothing and the result is the same as minimizing the sum of squares. As , however, the total variation term plays an increasingly strong role, which forces the result to have smaller total variation, at the expense of being less like the input (noisy) signal. Thus, the choice of regularization parameter is critical to achieving just the right amount of noise removal.
2D signal images
We now consider 2D signals ''y'', such as images.
The total-variation norm proposed by the 1992 article is
:
and is isotropic and not differentiable
In mathematics, a differentiable function of one real variable is a function whose derivative exists at each point in its domain. In other words, the graph of a differentiable function has a non- vertical tangent line at each interior point i ...
. A variation that is sometimes used, since it may sometimes be easier to minimize, is an anisotropic version
:
The standard total-variation denoising problem is still of the form
:
where ''E'' is the 2D ''L''2 norm. In contrast to the 1D case, solving this denoising is non-trivial. A recent algorithm that solves this is known as the primal dual method
Interior-point methods (also referred to as barrier methods or IPMs) are a certain class of algorithms that solve linear and nonlinear convex optimization problems.
An interior point method was discovered by Soviet mathematician I. I. Dikin in 1 ...
.
Due in part to much research in compressed sensing
Compressed sensing (also known as compressive sensing, compressive sampling, or sparse sampling) is a signal processing technique for efficiently acquiring and reconstructing a signal, by finding solutions to underdetermined linear systems. This ...
in the mid-2000s, there are many algorithms, such as the split- Bregman method, that solve variants of this problem.
Rudin–Osher–Fatemi PDE
Suppose that we are given a noisy image and wish to compute a denoised image over a 2D space. ROF showed that the minimization problem we are looking to solve is:
:
where is the set of functions with bounded variation
In mathematical analysis, a function of bounded variation, also known as ' function, is a real number, real-valued function (mathematics), function whose total variation is bounded (finite): the graph of a function having this property is well beh ...
over the domain , is the total variation over the domain, and is a penalty term. When is smooth, the total variation is equivalent to the integral of the gradient magnitude:
:
where is the Euclidean norm
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidea ...
. Then the objective function of the minimization problem becomes:From this functional, the Euler-Lagrange equation for minimization – assuming no time-dependence – gives us the nonlinear elliptic
In mathematics, an ellipse is a plane curve surrounding two focal points, such that for all points on the curve, the sum of the two distances to the focal points is a constant. It generalizes a circle, which is the special type of ellipse in ...
partial differential equation
In mathematics, a partial differential equation (PDE) is an equation which imposes relations between the various partial derivatives of a multivariable function.
The function is often thought of as an "unknown" to be solved for, similarly to ...
:For some numerical algorithms, it is preferable to instead solve the time-dependent version of the ROF equation:
Applications
The Rudin–Osher–Fatemi model was a pivotal component in producing the first image of a black hole.
See also
* Anisotropic diffusion
In image processing and computer vision, anisotropic diffusion, also called Perona–Malik diffusion, is a technique aiming at reducing image noise without removing significant parts of the image content, typically edges, lines or other details t ...
* Bounded variation
In mathematical analysis, a function of bounded variation, also known as ' function, is a real number, real-valued function (mathematics), function whose total variation is bounded (finite): the graph of a function having this property is well beh ...
* 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 ...
* Noise reduction
Noise reduction is the process of removing noise from a signal. Noise reduction techniques exist for audio and images. Noise reduction algorithms may distort the signal to some degree. Noise rejection is the ability of a circuit to isolate an un ...
* Non-local means
Non-local means is an algorithm in image processing for image denoising. Unlike "local mean" filters, which take the mean value of a group of pixels surrounding a target pixel to smooth the image, non-local means filtering takes a mean of all pi ...
* 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, ...
* Total variation
In mathematics, the total variation identifies several slightly different concepts, related to the ( local or global) structure of the codomain of a function or a measure. For a real-valued continuous function ''f'', defined on an interval ...
* Basis pursuit denoising
In applied mathematics and statistics, basis pursuit denoising (BPDN) refers to a mathematical optimization problem of the form
: \min_x \left(\frac \, y - Ax\, ^2_2 + \lambda \, x\, _1\right),
where \lambda is a parameter that controls the trad ...
* Lasso (statistics)
In statistics and machine learning, lasso (least absolute shrinkage and selection operator; also Lasso or LASSO) is a regression analysis method that performs both variable selection and regularization in order to enhance the prediction accura ...
References
External links
TVDIP: Full-featured Matlab 1D total variation denoising implementation.
* tp://ftp.math.ucla.edu/pub/camreport/cam08-34.pdf Efficient Primal-Dual Total Variationbr>TV-L1 image denoising algorithm in Matlab
{{Noise, state=uncollapsed
Nonlinear filters
Signal processing
Image processing
Partial differential equations