In
signal processing
Signal processing is an electrical engineering subfield that focuses on analyzing, modifying and synthesizing ''signals'', such as audio signal processing, sound, image processing, images, Scalar potential, potential fields, Seismic tomograph ...
, particularly
image processing
An image or picture is a visual representation. An image can be two-dimensional, such as a drawing, painting, or photograph, or three-dimensional, such as a carving or sculpture. Images may be displayed through other media, including a pr ...
, total variation denoising, also known as total variation regularization or total variation filtering, is a noise removal process (
filter). 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 property, local or global) structure of the codomain of a Function (mathematics), function or a measure (mathematics), measure. For a real ...
'', that is, the integral of the
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. ...
magnitude
Magnitude may refer to:
Mathematics
*Euclidean vector, a quantity defined by both its magnitude and its direction
*Magnitude (mathematics), the relative size of an object
*Norm (mathematics), a term for the size or length of a vector
*Order of ...
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 signal noise, noise from an image, signal, and video. Such noise reduction is a typical pre-processing step to improve the results of later processing (for example ...
ing which reduce noise but at the same time smooth away edges to a greater or lesser degree. By contrast, total variation denoising is a 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
A digital signal is a signal that represents data as a sequence of discrete values; at any given time it can only take on, at most, one of a finite number of values. This contrasts with an analog signal, which represents continuous values; ...
, 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, 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 distinct points on the graph of a function, graph of the function lies above or on the graph between the two points. Equivalently, a function is conve ...
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 problems ...
can be used to minimize it and find the solution .
Regularization properties
The regularization 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 squared errors. 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
In physics and geometry, isotropy () is uniformity in all orientations. Precise definitions depend on the subject area. Exceptions, or inequalities, are frequently indicated by the prefix ' or ', hence '' anisotropy''. ''Anisotropy'' is also ...
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 in ...
. 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.
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 (electronics), signal by finding solutions to Underdetermined s ...
in the mid-2000s, there are many algorithms, such as the split-Bregman method
The Bregman method is an iterative algorithm to solve certain convex optimization problems involving regularization. The original version is due to Lev M. Bregman, who published it in 1967.
The algorithm is a row-action method accessing con ...
, 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, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces'' ...
. 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 partial differential equation
In mathematics, a partial differential equation (PDE) is an equation which involves a multivariable function and one or more of its partial derivatives.
The function is often thought of as an "unknown" that solves the equation, similar to ho ...
:
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 ...
* Basis pursuit denoising
* Chambolle-Pock algorithm
* 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 allo ...
* Lasso (statistics)
* 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 u ...
* 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 audio signal processing, sound, image processing, images, Scalar potential, potential fields, Seismic tomograph ...
* Total variation
In mathematics, the total variation identifies several slightly different concepts, related to the (local property, local or global) structure of the codomain of a Function (mathematics), function or a measure (mathematics), measure. For a real ...
References
External links
TVDIP: Full-featured Matlab 1D total variation denoising implementation.
Efficient Primal-Dual Total Variation
TV-L1 image denoising algorithm in Matlab
{{Noise, state=uncollapsed
Nonlinear filters
Signal processing
Image processing
Partial differential equations