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 by solving
where is the denoised image, the noisy input, and the differences of between neighbouring pixels, and the regularization strength: larger gives a flatter result. The first term keeps close to the data; the second adds up the size of the gradient (an -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 . Squared penalties lead to linear filters that can be written in the frequency domain, as in the Wiener and CLS formulas. The -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 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.69Here the weight argument of denoise_tv_chambolle plays the role of 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 by PSNR alone. A TV result can score well and still look “cartoon-like”, so look at the image too.
References
- R. C. Gonzalez and R. E. Woods, Digital Image Processing, 4th ed., Pearson, 2018, Ch. 5. publisher page
- 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
- 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
- A. C. Kak and M. Slaney, Principles of Computerized Tomographic Imaging, IEEE Press, 1988 (SIAM reprint 2001). free online edition
- 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
- scikit-image developers, “Radon transform,” scikit-image documentation (gallery example). docs
- A. Buades, B. Coll and J.-M. Morel, “A non-local algorithm for image denoising,” IEEE CVPR, vol. 2, pp. 60–65, 2005. DOI
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- J. Adler and O. Öktem, “Learned primal-dual reconstruction,” IEEE Transactions on Medical Imaging, 2018. arXiv
- V. Monga, Y. Li and Y. C. Eldar, “Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing,” arXiv:1912.10557, 2019. arXiv
- 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
- 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
- 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
- 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
- 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