Full search page →

Total variation as a regularizer

Optional · supplementary note 7 of 7 for IP 05 · Image Restoration and Reconstruction. Nothing in the main text depends on it; citation numbers refer to the reference list at the bottom of this page.

Navigate: this page and this track: Navigate: this page and this track

In plain words: a regularizer is a penalty that says what a good answer looks like. Wiener and CLS prefer smooth answers. Total variation (TV) prefers answers that are piecewise constant: flat patches separated by sharp jumps. That is a much better description of many photographs than “everywhere smooth”.

The ROF model of Rudin, Osher and Fatemi [21] denoises an image ff by solving

min⁡u 12∥u−f∥22+λ TV(u),TV(u)=∑x,y(∂xu)2+(∂yu)2,\min_{u}\ \tfrac12 \lVert u - f \rVert_2^2 + \lambda\, \mathrm{TV}(u), \qquad \mathrm{TV}(u) = \sum_{x, y} \sqrt{(\partial_x u)^2 + (\partial_y u)^2},

where uu is the denoised image, ff the noisy input, ∂xu\partial_x u and ∂yu\partial_y u the differences of uu between neighbouring pixels, and λ>0\lambda > 0 the regularization strength: larger λ\lambda gives a flatter result. The first term keeps uu close to the data; the second adds up the size of the gradient (an L1L_1-type penalty, a sum of magnitudes). Compare it with the penalty behind the smoothing filters earlier in this chapter. CLS [3] penalizes the squared Laplacian, and the Tikhonov variant penalizes the squared gradient ∥∇u∥22\lVert\nabla u\rVert_2^2. Squared penalties lead to linear filters that can be written in the frequency domain, as in the Wiener and CLS formulas. The L1L_1-type TV penalty gives a nonlinear filter with no such formula; it needs an iterative solver such as Chambolle’s algorithm [22]. The one-dimensional version of the same objective, solved by splitting, is worked out in OPT 08 · Geometric Applications, Splitting and Modern Methods; that page treats signals, not images.

Why edges survive. Take a jump of height 1 and compare it with a ramp that climbs the same height over 100 samples. TV adds up magnitudes, so both cost 1, and the data term decides. A squared-gradient penalty charges 1 for the jump but only about 0.01 for the ramp, so it pays to turn every edge into a slope. Why staircases appear. The L1L_1 penalty likes gradients that are exactly zero, so TV tends to output flat steps even where the true signal is a gentle slope. Staircasing is a known side effect: textures and fine shading are flattened.

Code · Python · 27 lines
import numpy as np
from skimage import data, img_as_float
from skimage.filters import gaussian
from skimage.metrics import peak_signal_noise_ratio as psnr
from skimage.restoration import denoise_tv_chambolle

clean = img_as_float(data.camera())[:256, :256]
rng = np.random.default_rng(0)
noisy = np.clip(clean + rng.normal(0, 0.08, clean.shape), 0, 1)

# 1) A step and a 100-sample ramp with the same end values: total variation vs squared gradient
step, ramp = np.r_[np.zeros(50), np.ones(50)], np.linspace(0, 1, 100)
tv1d = lambda u: np.abs(np.diff(u)).sum()
l2 = lambda u: (np.diff(u) ** 2).sum()
print(f"TV: step {tv1d(step):.2f}, ramp {tv1d(ramp):.2f} | squared gradient: step {l2(step):.2f}, ramp {l2(ramp):.3f}")

# 2) Image: Gaussian vs TV, each at its best setting from a small sweep
g = max((psnr(clean, gaussian(noisy, s)), s) for s in (0.8, 1.0, 1.2, 1.5))
t = max((psnr(clean, denoise_tv_chambolle(noisy, weight=w)), w) for w in (0.05, 0.1, 0.15))
print(f"noisy {psnr(clean, noisy):.2f} dB | Gaussian s={g[1]}: {g[0]:.2f} dB | TV weight={t[1]}: {t[0]:.2f} dB")

# 3) Staircasing: TV on a noisy smooth sine (the true signal has no flat parts)
x = np.linspace(0, 1, 200)
f = 0.5 + 0.4 * np.sin(2 * np.pi * x) + rng.normal(0, 0.05, 200)
u = denoise_tv_chambolle(f, weight=0.1, eps=1e-8, max_num_iter=5000)
flat = lambda v: np.mean(np.abs(np.diff(v)) < 1e-4)
print(f"share of neighbouring pairs that are flat: noisy {flat(f):.2f}, TV {flat(u):.2f}")

Output:

Code · 3 lines
TV: step 1.00, ramp 1.00 | squared gradient: step 1.00, ramp 0.010
noisy 22.30 dB | Gaussian s=1.0: 29.91 dB | TV weight=0.1: 32.20 dB
share of neighbouring pairs that are flat: noisy 0.00, TV 0.69

Here the weight argument of denoise_tv_chambolle plays the role of λ\lambda above. On the same noisy crop as the NLM note, TV beats the best Gaussian filter by about 2.3 dB (and NLM beats TV by about 0.65 dB), while on the sine, where the truth has no flat parts, 69% of neighbouring pairs of the TV output are flat: that is staircasing. The common mistake is to judge λ\lambda by PSNR alone. A TV result can score well and still look “cartoon-like”, so look at the image too.

References

  1. R. C. Gonzalez and R. E. Woods, Digital Image Processing, 4th ed., Pearson, 2018, Ch. 5. publisher page
  2. H. Hwang and R. A. Haddad, “Adaptive median filters: new algorithms and results,” IEEE Transactions on Image Processing, vol. 4, no. 4, pp. 499–502, 1995. DOI
  3. B. R. Hunt, “The application of constrained least squares estimation to image restoration by digital computer,” IEEE Transactions on Computers, vol. C-22, no. 9, pp. 805–812, 1973. DOI
  4. A. C. Kak and M. Slaney, Principles of Computerized Tomographic Imaging, IEEE Press, 1988 (SIAM reprint 2001). free online edition
  5. L. A. Shepp and B. F. Logan, “The Fourier reconstruction of a head section,” IEEE Transactions on Nuclear Science, vol. 21, no. 3, pp. 21–43, 1974. DOI
  6. scikit-image developers, “Radon transform,” scikit-image documentation (gallery example). docs
  7. A. Buades, B. Coll and J.-M. Morel, “A non-local algorithm for image denoising,” IEEE CVPR, vol. 2, pp. 60–65, 2005. DOI
  8. K. Dabov, A. Foi, V. Katkovnik and K. Egiazarian, “Image denoising by sparse 3-D transform-domain collaborative filtering,” IEEE Transactions on Image Processing, vol. 16, no. 8, pp. 2080–2095, 2007. DOI
  9. K. Zhang, W. Zuo, Y. Chen, D. Meng and L. Zhang, “Beyond a Gaussian denoiser: Residual learning of deep CNN for image denoising,” IEEE Transactions on Image Processing, vol. 26, no. 7, pp. 3142–3155, 2017. doi · arXiv
  10. C. Tian, L. Fei, W. Zheng, Y. Xu, W. Zuo and C.-W. Lin, “Deep learning on image denoising: An overview,” Neural Networks, vol. 131, pp. 251–275, 2020. arXiv
  11. M. Elad, B. Kawar and G. Vaksman, “Image denoising: The deep learning revolution and beyond — A survey paper,” SIAM Journal on Imaging Sciences, vol. 16, no. 3, pp. 1594–1654, 2023. arXiv
  12. K. Zhang, W. Ren, W. Luo, W.-S. Lai, B. Stenger, M.-H. Yang and H. Li, “Deep image deblurring: A survey,” International Journal of Computer Vision, 2022. arXiv
  13. G. Ongie, A. Jalal, C. A. Metzler, R. G. Baraniuk, A. G. Dimakis and R. Willett, “Deep learning techniques for inverse problems in imaging,” arXiv:2005.06001, 2020. arXiv
  14. U. S. Kamilov, C. A. Bouman, G. T. Buzzard and B. Wohlberg, “Plug-and-play methods for integrating physical and learned models in computational imaging: Theory, algorithms, and applications,” IEEE Signal Processing Magazine, vol. 40, no. 1, pp. 85–97, 2023. arXiv
  15. K. Zhang, Y. Li, W. Zuo, L. Zhang, L. Van Gool and R. Timofte, “Plug-and-play image restoration with deep denoiser prior,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 44, no. 10, pp. 6360–6376, 2022. arXiv
  16. K. H. Jin, M. T. McCann, E. Froustey and M. Unser, “Deep convolutional neural network for inverse problems in imaging,” IEEE Transactions on Image Processing, vol. 26, no. 9, pp. 4509–4522, 2017. arXiv
  17. J. Adler and O. Öktem, “Learned primal-dual reconstruction,” IEEE Transactions on Medical Imaging, 2018. arXiv
  18. V. Monga, Y. Li and Y. C. Eldar, “Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing,” arXiv:1912.10557, 2019. arXiv
  19. G. Wang, J. C. Ye and B. De Man, “Deep learning for tomographic image reconstruction,” Nature Machine Intelligence, vol. 2, no. 12, pp. 737–748, 2020. DOI
  20. A. Buades, B. Coll and J.-M. Morel, “A review of image denoising algorithms, with a new one,” Multiscale Modeling & Simulation, vol. 4, no. 2, pp. 490–530, 2005. DOI
  21. L. I. Rudin, S. Osher and E. Fatemi, “Nonlinear total variation based noise removal algorithms,” Physica D: Nonlinear Phenomena, vol. 60, no. 1–4, pp. 259–268, 1992. DOI
  22. A. Chambolle, “An algorithm for total variation minimization and applications,” Journal of Mathematical Imaging and Vision, vol. 20, no. 1–2, pp. 89–97, 2004. DOI
  23. A. Buades, B. Coll and J.-M. Morel, “Non-Local Means Denoising,” Image Processing On Line, vol. 1, pp. 208–212, 2011. DOI · article and implementation