A combined first and second order variational approach for image reconstruction

Konstantinos Papafitsoros; Carola-Bibiane Schönlieb

Source-linked AI summary

A combined first and second order variational approach for image reconstruction

Konstantinos Papafitsoros, Carola-Bibiane Schönlieb

arXiv:1202.6341v2Feb 27, 2012math.NA

TL;DR

The paper addresses artifacts produced by first-order total variation regularisation, especially staircasing in reconstructed images. It combines first- and second-order nonsmooth regularisation in BH(Ω), proves well-posedness, and solves the discretised problem with split Bregman methods. Across denoising, deblurring, and inpainting, the approach reduces staircasing, connects edges across large gaps, and achieves results competitive with higher-order methods while remaining computationally simple.

Problem
Total variation preserves edges but can create staircasing and blocky-like structures, motivating higher-order regularisation for image reconstruction.
Method
The paper combines convex first- and second-order regularisers in BH(Ω), proves existence and uniqueness by relaxation, and applies split Bregman minimisation to the discretised model.
Results
The combined model significantly reduces staircasing in denoising and deblurring, connects edges across large inpainting gaps, and obtains SSIM improvements over first-order regularisation.
Takeaways & Limitations
The approach is a simple convex higher-order extension that competes with other higher-order methods while requiring a fraction of their computation time.
Takeaways & Limitations
For inpainting, edge connectivity depends on the size and geometry of the inpainting domain, with sufficient conditions left for future research.

Abstract

from arXiv · show

In this paper we study a variational problem in the space of functions of bounded Hessian. Our model constitutes a straightforward higher-order extension of the well known ROF functional (total variation minimisation) to which we add a non-smooth second order regulariser. It combines convex functions of the total variation and the total variation of the first derivatives. In what follows, we prove existence and uniqueness of minimisers of the combined model and present the numerical solution of the corresponding discretised problem by employing the split Bregman method. The paper is furnished with applications of our model to image denoising, deblurring as well as image inpainting. The obtained numerical results are compared with results obtained from total generalised variation (TGV), infimal convolution and Euler's elastica, three other state of the art higher-order models. The numerical discussion confirms that the proposed higher-order model competes with models of its kind in avoiding the creation of undesirable artifacts and blocky-like structures in the reconstructed images -- a known disadvantage of the ROF model -- while being simple and efficiently numerically solvable.

1. Introduction

The paper introduces a convex combined first- and second-order variational model in BH(Ω), extending total variation regularisation to reduce staircasing while retaining edge information. It establishes theoretical well-posedness, develops split Bregman computation, and evaluates applications in denoising, deblurring, and inpainting.

1. Introduction: The model minimises a combined first- and second-order functional over functions of bounded Hessian, using convex regularisers with at most linear growth.The first-order term receives a larger weight to preserve jumps, while the second-order term targets staircasing artifacts.
1. Introduction: Applications cover image denoising, deblurring, and inpainting, with comparisons to infimal convolution, TGV, and Euler’s elastica.The introduction states that the model obtains image-quality results close to leading higher-order reconstruction methods with lower computational effort.
1. Introduction: The paper proves existence and uniqueness through relaxation and numerically minimises the discretised nonsmooth model with an operator-splitting method.The analysis covers the classical W 2,1 setting and the relaxed BH formulation, while the numerical treatment uses f(x)=|x| and g(x)=|x|.
1.1. Context.: Total variation preserves edges and smooths homogeneous regions but produces staircasing on slanted or piecewise-linear image regions.In one dimension this appears as staircase signals, while in two dimensions it creates blocky-like images.
1.1. Context.: Huber-type regularisation reduces staircasing only partly, whereas higher-order derivatives provide another route for improving total variation minimisation.The paper motivates higher-order regularisation as a way to address artifacts not fully removed by smoothing the first-order term.

2. Preliminaries

The preliminaries introduce measures, BV functions, convex functions of measures, relaxation, and the bounded-variation framework underlying the paper’s variational analysis.

2. Preliminaries: Radon measures are introduced with total variation, weak* convergence, Lebesgue decomposition, and polar decomposition.These notions provide the measure-theoretic language used for distributional derivatives and singular parts.
2. Preliminaries: Convex, positively homogeneous functions extend from vectors to vector-valued measures, while linear-growth convex functions use a recession function for their singular part.The resulting measure functionals retain convexity and support lower-semicontinuity analysis.
2.3. The space [BV (Ω)]m.: A function belongs to BV when its distributional derivative is representable by a finite Radon measure.For Sobolev functions, the derivative measure is absolutely continuous and equals the weak gradient times Lebesgue measure.
2.3. The space [BV (Ω)]m.: Weak* convergence in BV combines L1 convergence with weak* convergence of derivative measures, and bounded sequences admit weakly* convergent subsequences under standard domain conditions.Strict convergence additionally requires convergence of total variations.
2. Preliminaries: Relaxation defines the greatest lower-semicontinuous functional below the original functional and preserves the infimum when a minimum exists.This construction supplies the lower-semicontinuous formulation needed for variational problems that are not well-posed in their original space.

3. The variational formulation

The paper formulates and relaxes a combined first- and second-order regularisation functional in BH(Ω), establishing compactness, lower semicontinuity, existence, uniqueness under assumptions, and stability.

3. The variational formulation: The model uses convex, at-most-linearly-growing f and g with nonnegative weights α and β, under stated assumptions on T and the domain.The first-order term controls gradients while the second-order term controls Hessians.
3. The variational formulation: Relaxation extends the functional from non-reflexive W 2,1(Ω) to BH(Ω), where compactness enables the existence analysis.The original functional may assign +∞ outside W 2,1(Ω), motivating its lower semicontinuous envelope.
3. The variational formulation: BH(Ω) contains W 2,1(Ω) functions whose distributional Hessians are finite Radon measures, and embeds compactly into W 1,1(Ω).It is equipped with a norm combining BV variation and the total variation of the Hessian.
3. The variational formulation: Bounded sequences in BH(Ω) have weak∗-convergent subsequences, providing the compactness needed for variational arguments.The compactness theorem follows from the compact embedding into W 1,1(Ω) and BV compactness for gradients.
3.2. Relaxation of the second order functional.: The relaxed functional is lower semicontinuous with respect to strict convergence in BH(Ω), and strict convergence implies weak∗ convergence.The lower semicontinuous envelope is identified through approximation by smooth W 2,1(Ω) functions.
3.2. Relaxation of the second order functional.: When T(XΩ) ≠ 0 and α, β > 0, the relaxed minimisation problem has a solution; it is unique if T is injective or f is strictly convex.The paper also states stability estimates for minimisers under noisy data and data perturbations.

4. Special cases and extensions

The paper develops anisotropic and L1-fidelity variants of the model, including a special anisotropic theorem and an application of L1 fidelity to impulse-noise restoration.

4. Special cases and extensions: The extensions include an anisotropic functional and a version using an L1 norm in the fidelity term.These are presented as additional versions of the extended functional Hex.
4.1. The anisotropic version.: For f(x) = |x|1 and g(x) = |x|1, the model has an anisotropic analogue based on componentwise norms and distributional derivatives.The resulting functional and theorem are obtained as special cases of the general framework.
4.1. The anisotropic version.: If T is injective, the anisotropic minimisation problem has a unique solution.The preceding existence statement is paired with uniqueness under injectivity.
4.2. The L1 fidelity term.: The L1-fidelity extension is considered with f(x) = |x| and g(x) = |x| for simplicity.The paper motivates this fidelity choice for image data corrupted by impulse noise.
4.2. The L1 fidelity term.: Uniqueness cannot be guaranteed for the L1-fidelity functional because it is not strictly convex, even when T = Id.The general f and g results can nevertheless be extended to the discussed variants.

5. The numerical implementation

The discretised model is solved with Bregman-based operator splitting: gradient and Hessian variables are split from the image, then minimised alternately with convergence under stated assumptions.

5. The numerical implementation: The numerical section discretises the functional for f(x) = |x|, g(x) = |x|, using L2 data fidelity and a discrete image u ∈ Rn×m.The discrete forward operator T maps Rn×m to itself.
5. The numerical implementation: Periodic boundary conditions define discrete gradient and Hessian operators together with their adjoint divergences.The operators ∇ and div, and ∇2 and div2, are constructed consistently as adjoint pairs.
5. The numerical implementation: Bregman iteration enforces the constraints through an unconstrained penalised problem whose penalty parameter would otherwise need to increase to infinity.The split Bregman algorithm combines Bregman iteration with operator splitting.
5. The numerical implementation: Under coercivity and uniqueness assumptions, the Bregman iterates converge to the unique solution of the constrained minimisation problem.The theorem does not require the iterates to satisfy the constraint in finitely many steps.
5. The numerical implementation: The split formulation replaces ∇u and ∇2u by auxiliary variables v and w, imposing v = ∇u and w = ∇2u.This converts the nonsmooth regularisers into separable terms within a constrained optimisation problem.
5. The numerical implementation: When T is injective, the discrete subproblem and constrained problem have unique solutions, so the convergence theorem applies.The paper explicitly notes this setting for denoising and deblurring.
5. The numerical implementation: The algorithm alternates minimisation over u, v, and w; the u-subproblem is quadratic and is solved through a linear optimality system.For the higher-order case, solving this system exactly is reported as more preferable and robust than one Gauss-Seidel iteration.

6. Applications in Denoising

The denoising experiments test whether adding a second-order term improves reconstruction quality over first-order TV, using SSIM alongside PSNR and visual inspection. TV-TV2 reduces staircasing and achieves competitive quality, while parameter choice exposes a trade-off between contrast and artifact removal.

Experimental setup: The experiments compare TV-TV2 denoising with ROF, infimal convolution, and TGV on Gaussian-corrupted images.For β = 0, TV-TV2 reduces to ROF; the experiments use the identity forward operator and an L2 fidelity term.
Experimental setup: SSIM is the primary quality measure because it evaluates structural preservation in addition to reconstruction fidelity.The paper uses SSIM rather than PSNR as its main assessment, with perfect reconstruction assigned SSIM = 1.
Convergence and runtime: After 80–100 iterations, the relative residual is about 10^-3 or lower, with no noticeable subsequent change in the iterates.The algorithm generally uses a predefined stopping count of 300 iterations.
Synthetic-image denoising: 0.9081 is the highest SSIM reported for the synthetic example with TV-TV2, compared with 0.8979 for TV and 0.9053 for infimal convolution.The TV-TV2 value occurs at α = 0.06, β = 0.03; the optimal SSIM parameters do not always produce the best visual result.
Convergence and runtime: 86 split Bregman iterations take 4.05 seconds for TV-TV2, versus 1297 primal-dual iterations and 36.25 seconds for TGV.The authors present TV-TV2 as suitable when fast, though not necessarily optimal, results are needed.
Convergence and runtime: During optimization, TV-TV2 reaches an SSIM peak of 0.9103 after 1.08 seconds and then remains essentially constant, whereas TGV improves more gradually.TV peaks earlier at 0.9130 but later drops sharply when staircasing appears; TGV begins outperforming the methods after 1.89 seconds.
Synthetic-image denoising: The higher-order term reduces staircasing, but larger β can also reduce contrast and introduce slight blur.The paper reports that this blur can be addressed through sharpening and contrast adjustment in post-processing.
Natural-image denoising: For the natural-image example, TV-TV2 reaches SSIM 0.8319 at α = β = 0.017, while TV produces visible staircasing with SSIM 0.8168.Choosing α = β = 0.023 further reduces staircasing without excessive blur, yielding SSIM 0.8185.

7. Applications in deblurring

The TV-TV2 method improves deblurring by reducing staircasing, while parameter choices trade additional blur against smoother reconstructions. On a natural image, its best reported result achieves SSIM=0.8361.

Adding a small second-order weight noticeably decreases staircasing in Gaussian-kernel deblurring.Increasing β further can reduce staircasing, but may introduce blur.
The best natural-image deblurring result reaches SSIM=0.8361 with α = 0.0005 and β = 0.0001.Slightly larger β values remove more staircasing, while sharpening can control the resulting blur.

8. Applications in inpainting

The paper applies TV-TV2 to inpainting, where the higher-order term can connect large gaps but its behavior depends on the inpainting domain and may introduce blur. The formulation retains flexibility for noisy known regions.

Inpainting reconstructs a missing domain D ⊆Ω from information in the intact image region.The operator uses the characteristic function of Ω\D to represent the known part.
The inpainting framework is kept flexible so that noise in known image regions can also be handled.
TV2 inpainting connects large gaps that harmonic and TV inpainting cannot connect, at the price of blur.A shock filter can control the blur, and TV2 must dominate by choosing α small or zero.
TV2 connectivity across large gaps depends on the size and geometry of the inpainting domain.Sufficient conditions for this connectivity remain future research.
For large-font text removal, TV2 and Euler’s elastica produce comparable results that appear closer to the true solution than TV inpainting.TV inpainting produces piecewise constant results inside the missing domain.

9. Comparison with other higher-order methods

TV-TV2 is compared with TGV, infimal convolution, Euler’s elastica, and other inpainting methods. It offers competitive reconstructions with simpler convex optimization and favorable computational characteristics, although TGV gives better qualitative results in denoising and deblurring.

The figures compare deblurring, inpainting connectivity, inpainting-domain width, and large-font text removal across higher-order methods.
TGV gives better qualitative SSIM results than TV-TV2 in denoising and deblurring, but requires significantly more computation.TV-TV2 can achieve comparable results with simple and fast post-processing.
TV-TV2 is slightly faster and reconstructs deblurred images better than infimal convolution, while denoising results are comparable.
TV2 connects large inpainting gaps like Euler’s elastica, while its convex regulariser avoids the non-convexity of Euler’s elastica.TV2 may produce slight blur, which can be reduced with a shock filter.

10. Conclusion

The paper develops and analyzes a convex first- and second-order variational model for image reconstruction, then solves its discretization numerically. Experiments show reduced staircasing, large-gap connectivity, and competitive quality with faster computation, while parameter selection and continuum-discrete relations remain open.

The authors formulate a second-order variational problem in BH(Ω), prove existence and uniqueness through relaxation, and establish stability.
Split Bregman provides a robust numerical solver for the discretized model, converging after a few iterations across denoising, deblurring, and inpainting experiments.
The second-order term reduces staircasing in denoising and deblurring, producing piecewise smooth rather than piecewise constant images.
Higher-order inpainting connects edges across large gaps, which TV inpainting cannot solve.
TV-TV2 is a simple convex extension of total variation that gives almost comparable qualitative results to other higher-order methods in a fraction of the time.
Future work includes principled selection of α and β, links to infimal convolution and spatially dependent regularisation, and Γ-convergence analysis.

Appendix A. Some useful theorems

Appendix A collects measure-theoretic and approximation results used for convex functionals involving measures and Hessians. It includes convexity, weak∗ lower semicontinuity, and smooth approximation statements, alongside auxiliary sequence lemmas.

Measure functionals: Positive one-homogeneity allows g to be applied to vector measures through their densities relative to a dominating positive measure, while convexity is inherited by the resulting measure functional.The proposition assumes absolute continuity with respect to the reference measure and states convexity on [M(Ω)]^m.
Lower semicontinuity: The Buttazzo–Freddi theorem establishes weak∗ lower semicontinuity for convex functionals of vector-valued Radon measures and positive reference measures.The theorem is stated using Lebesgue decompositions of the limiting and approximating measures.
Lower semicontinuity: When the reference measures equal Lebesgue measure, the measure-theoretic lower-semicontinuity inequality specializes according to definition (2.1).
Approximation: For convex g with at most linear growth, every u in BH(Ω) admits smooth W 2,1(Ω) approximations preserving the limiting g(D2u)(Ω) value.The approximation sequence lies in C∞(Ω) ∩ W 2,1(Ω), and g(D2u_k)(Ω) converges to g(D2u)(Ω).
Auxiliary lemma: Kronecker’s lemma supplies an auxiliary sequence result for summable real sequences and increasing positive denominators diverging to infinity.The appendix also records a consequence for decreasing positive sequences with finite sum.