Source-linked AI summary
Parallel Proximal Algorithm for Image Restoration Using Hybrid Regularization -- Extended Version
Nelly Pustelnik, Caroline Chaux, Jean-Christophe Pesquet
TL;DR
Image restoration requires regularizers that avoid the distinct artefacts associated with total variation and wavelet penalties. The paper combines multiple convex terms and adapts an accelerated PPXA framework, reporting effective numerical behavior and promising hybrid-regularization results.
Problem
Choosing a suitable regularizer is difficult because total variation can create staircase effects while wavelet regularization can produce ringing artefacts.
Method
The paper adapts PPXA for criteria with multiple convex terms, combining frame-domain sparsity and total variation and using splitting for difficult proximity operators.
Results
Numerical and visual results demonstrate the effectiveness of the proposed approach for restoration with convolutional degradation and non-necessarily additive noise.
Takeaways & Limitations
The framework directly handles the true noise likelihood, supports wavelet-frame sparsity with total variation, and has a parallel structure suitable for multicore architectures.
Takeaways & Limitations
Automatic hyperparameter optimization is not addressed because of space limitations, so the experiments manually adjust parameters to maximize SNR.
Abstract
from arXiv · showhide
Regularization approaches have demonstrated their effectiveness for solving ill-posed problems. However, in the context of variational restoration methods, a challenging question remains, which is how to find a good regularizer. While total variation introduces staircase effects, wavelet domain regularization brings other artefacts, e.g. ringing. However, a compromise can be found by introducing a hybrid regularization including several terms non necessarily acting in the same domain (e.g. spatial and wavelet transform domains). We adopt a convex optimization framework where the criterion to be minimized is split in the sum of more than two terms. For spatial domain regularization, isotropic or anisotropic total variation definitions using various gradient filters are considered. An accelerated version of the Parallel ProXimal Algorithm is proposed to perform the minimization. Some difficulties in the computation of the proximity operators involved in this algorithm are also addressed in this paper. Numerical experiments performed in the context of Poisson data recovery, show the good behavior of the algorithm as well as promising results concerning the use of hybrid regularization techniques.
1 Introduction
The paper motivates convex restoration criteria with multiple regularization terms and adapts PPXA to handle broad degradation models and hybrid spatial–wavelet regularization.
- Nested forward-backward and Douglas-Rachford approaches have limited parallelization and are practically restricted in the number of minimized functions.
- The paper targets restoration criteria with more than two convex terms, enabling constraints or priors that act on image pixels and frame coefficients.
- The proposed PPXA adaptation addresses convolution or decimated-convolution degradation with non-necessarily additive noise and uses splitting when fidelity proximities are difficult to compute.
- Hybrid regularization combines sparsity in a frame domain with total variation to benefit from both regularizers while investigating multiple discrete total-variation forms.
- The paper develops proximity-operator tools, an accelerated PPXA algorithm, and restoration experiments applying these components.
2 Background
The restoration problem recovers an image from degraded observations by minimizing a convex criterion whose terms can encode fidelity, pixel constraints, and frame-domain priors.
- 2.1 Image restoration: The observation is produced by a convolution or decimated convolution operator and non-necessarily additive noise, with the degradation model covering Laplacian and Poisson examples.
- 2.1 Image restoration: The objective is to recover the original image from observations using prior information about frame coefficients and spatial properties.
- 2.2 Frame representation: A frame representation expresses target-image properties through coefficients, with the adjoint frame operator reconstructing the restored image.
- 2.2 Frame representation: The convex criterion can contain more than two functions, allowing additional constraints on the target solution.
- 2.2 Frame representation: Pixel-domain terms may represent data fidelity or range constraints, while frame-coefficient terms commonly encode prior probabilistic models.
3 Proximal tools
The paper develops proximity-operator constructions for convex restoration terms, including linear-operator compositions, convolutional models, and split total variation.
- 3.1 Definition and examples: The proximity operator is a central convex-analysis tool, and projection is the special case associated with an indicator function of a closed convex set.
- 3.2 Proximity operators involving a linear operator: For convolutive operators, partitioning non-overlapping kernel shifts into orthogonal groups makes the corresponding proximity operators computable.
- 3.2 Proximity operators involving a linear operator: The construction covers non-boundary, zero-padded, periodic, and decimated one-dimensional convolution models, with extensions to two-dimensional deconvolution described as straightforward.
- 3.2 Proximity operators involving a linear operator: Choosing many singleton groups does not change the overall computational order, but it reduces memory needed to store proximity-operator results by a factor Md/Q.
- 3.3 Total variation: The total-variation term is split into functions with closed-form proximity operators, using discrete gradients in orthogonal directions and a convex potential ρtv.
4 Proposed algorithm
The paper adapts PPXA for convex restoration problems with many functions and frame representations, then accelerates it by reducing repeated applications of frame operators. Under stated assumptions, the accelerated algorithm converges while requiring only three applications of F or F⊤ per iteration.
- The improved PPXA targets large-function frame problems, where repeatedly applying analysis and synthesis operators causes long computation times.The method is designed for Problem (6), involving synthesis frame representations and a large number of functions.
- PPXA framework: Standard PPXA uses relaxation, weights, and possible proximity-operator errors, with convergence guaranteed under the paper's assumptions.The algorithm permits parameter choices and error terms while retaining convergence guarantees under the required conditions.
- PPXA framework: For tight-frame formulations, PPXA rewrites the functions through F⊤ and obtains specialized iterations for frame-based recovery.
- Accelerated version of PPXA: Algorithm 3 reduces computational load by limiting how often F and F⊤ are applied during PPXA iterations.
- Accelerated version of PPXA: Three applications of F or F⊤ per iteration suffice, yielding a gain over Algorithm 2 when S ≥ 2.The accelerated algorithm is stated to converge to a solution of Problem (6) under the listed assumptions.
5 Application to restoration
The restoration experiments evaluate accelerated PPXA, hybrid wavelet–total-variation regularization, total-variation choices, and boundary handling across convolutional and Poisson-noise settings. Results show computational gains from acceleration, sensitivity to total-variation design, reduced boundary artefacts with zero-padding, and visible benefits from combining regularizers.
- 5.1 Hybrid regularization: The criterion combines Poisson or other fidelity terms with wavelet regularization, total variation, and an image-constraint indicator.The wavelet and spatial smoothness weights are controlled separately by ϑ and µ.
- 5.2.1 Convergence rate comparison between PPXA and its accelerated version: The accelerated PPXA reaches convergence faster than the original algorithm, with gains increasing for larger blur kernels.Table 1 reports iteration and CPU-time comparisons across image sizes and blur kernels; the authors attribute larger gains to the increased number of proximity operators for larger kernels.
- 5.2.2 Comparison between different forms of total variation: Gradient-filter choice and isotropic versus anisotropic total variation significantly affect SNR and SSIM when wavelet regularization is small.When ϑ is larger, the total-variation form has less influence provided the regularization parameters are appropriately chosen.
- 5.2.3 Boundary effects on restored images: Zero-padding avoids the significant boundary artefacts produced by periodic convolution for the tested Boat and Peppers restorations.For the Sebal image, the two convolution models produced similar results.
- 5.2.5 Influence of each regularization term: Hybrid regularization combines wavelet and total-variation penalties to address their distinct ringing and staircase artefacts, while experiments also reveal checkerboard patterns from gradient discretization.The paper motivates the combination as a way to benefit from both regularization types.
- 5.2.5 Influence of each regularization term: The regularization parameters µ and ϑ were manually adjusted to maximize SNR, while automatic hyperparameter procedures were not addressed because of space constraints.The authors note that automatic alternatives include cross-validation, Stochastic EM, MCMC, and Stein-based methods.
6 Conclusion
The paper proposes a convex restoration approach for convolutive degradation and non-additive noise, combining direct noise likelihoods with sparsity and total-variation regularization. Its parallel PPXA-based algorithm produces effective numerical and visual restoration results and may extend to more general linear operators.
- The proposed approach handles possibly decimated convolution, non-additive noise, wavelet-frame sparsity, and total-variation penalization within a parallel convex optimization framework.It directly uses the true noise likelihood, including the Kullback–Leibler divergence for Poisson noise, without approximation.
- Numerical and visual experiments demonstrate the effectiveness of the proposed restoration approach.
- PPXA offers an advantage over alternative primal-dual approaches by supporting efficient parallel implementations.
7 Proof of Proposition 3.4
This proof derives the proximity operator for a composition with a linear operator by decomposing vectors into range and kernel components. The resulting expression uses the inverse of LL⊤ and separability of the potential function.
- The proof decomposes vectors into ran L⊤ and ker L components to characterize the proximity operator of the composed function.This decomposition reduces the calculation to the range component while preserving the orthogonal kernel component.
- The proof concludes by combining the intermediate relations to obtain the target proximity-operator expression.
- Separability of Υ converts the remaining calculation into componentwise proximity-operator problems.
- The operator is obtained using u = (LL⊤)−1Lw, enabled by the projection of w onto ran L⊤.
8 Proof of Proposition 3.8
This proof establishes the proximity-operator construction for the discretized total-variation setting by decomposing local matrix patches into orthogonal components. The resulting relations separate the specified filter directions from their orthogonal residuals.
- The proof uses the Frobenius norm and local coefficient relations to reduce the calculation to a minimization over patch indices.
- The boundary index set B identifies variables that do not belong to the interior patch matrices used in the construction.
- Each local patch is decomposed into components along H and V plus an orthogonal residual.The decomposition is written for both Π and Y, with residuals defined by subtracting the H and V components.
- The resulting identities establish the stated proposition for the discretized total-variation proximity operator.
9 Derivation of Algorithm 3
The derivation rewrites PPXA updates using projections onto the range of F and a complementary projection error. These relations lead to Algorithm 3 and transfer the convergence results from Algorithm 2.
- The first step of Algorithm 2 is transformed through the projector Π_F before the simplified update relations are combined.
- The derivation assumes a_j,ℓ belongs to ran F and represents it as F e_a_j,ℓ to express the projected update in coefficient form.
- Algorithm 3 is obtained by simplifying PPXA relations involving projected variables and their range and orthogonal components.The derivation introduces a projected representation for variables in ran F and updates the complementary component separately.
- Assumption 4.3(3) implies Assumption 4.1(4), allowing the convergence results for Algorithm 2 to be transposed to Algorithm 3.