Physica D 60 (1992) 259-268
North-Holland
Nonlinear total variation based noise removal algorithms*
Leonid I. Rudin 1, Stanley Osher and Emad Fatemi 2
Cognitech Inc., 2800, 28th Street, Suite 101, Santa Monica, CA 90405, USA
A constrained optimization type of numerical algorithm for removing noise from images is presented. The total
variation of the image is minimized subject to constraints involving the statistics of the noise. The constraints are imposed
using Lagrange multipliers. The solution is obtained using the gradient-projection method. This amounts to solving a time
dependent partial differential equation on a manifold determined by the constraints. As t---~ 0o the solution converges to a
steady state which is the denoised image. The numerical algorithm is simple and relatively fast. The results appear to be
state-of-the-art for very noisy images. The method is noninvasive, yielding sharp edges in the image. The technique could
be interpreted as a first step of moving each level set of the image normal to itself with velocity equal to the curvature of
the level set divided by the magnitude of the gradient of the image, and a second step which projects the image back onto
the constraint set.
1. Introduction
The presence of noise in images is unavoid-
able. It may be introduced by the image forma-
tion process, image recording, image transmis-
sion, etc. These random distortions make it dif-
ficult to perform any required picture processing.
For example, the feature oriented enhancement
introduced in refs. [6,7] is very effective in re-
storing blurry images, but it can be "frozen" by
an oscillatory noise component. Even a small
amount of noise is harmful when high accuracy is
required, e.g. as in subcell (subpixel) image
analysis.
In practice, to estimate a true signal in noise,
the most frequently used methods are based on
the least squares criteria. The rationale comes
from the statistical argument that the least
squares estimation is the best over an entire
* Research supported by DARPA SBIR Contract
#DAAH01-89-C0768 and by AFOSR Contract #F49620-90-
C-0011.
1
E-mail: cogni!leonid@aerospace.aero.org.
2 Current address: Institute for Mathematics and its Appli-
cations, University of Minnesota, Minneapolis, MN 55455,
USA.
ensemble of all possible pictures. This procedure
is L 2 norm dependent. However it has been
conjectured in ref. [6] that the proper norm for
images is the total variation (TV) norm and not
the L 2 norm. TV norms are essentially L 1 norms
of derivatives, hence L1 estimation procedures
are more appropriate for the subject of image
estimation (restoration). The space of functions
of bounded total variation plays an important
role when accurate estimation of discontinuities
in solutions is required [6,7].
Historically, the L~ estimation methods go
back to Galileo (1632) and Laplace (1793). In
comparison to the least square methods where
closed form linear solutions are well understood
and easily computed, the L 1 estimation is non-
linear and computationally complex. Recently
the subject of L 1 estimation of statistical data has
received renewed attention by the statistical
community, see e.g. ref. [13].
Drawing on our previous experience with
shock related image enhancement [6,7], we pro-
pose to denoise images by minimizing the total
variation norm of the estimated solution. We
derive a constrained minimization algorithm as a
0167-2789/92/$05.00 © 1992 - Elsevier Science Publishers B.V. All rights reserved