Source-linked AI summary
Restoration of Images Corrupted by Impulse Noise and Mixed Gaussian Impulse Noise using Blind Inpainting
Ming Yan
TL;DR
The paper studies restoration when impulse-damaged pixels are unknown, including mixed Gaussian impulse noise. It proposes two blind-inpainting formulations using ℓ0 minimization, and reports improved restoration over other methods alongside convergence guarantees to coordinatewise minima.
Problem
Restoration must recover images while identifying an unknown region of pixels whose information is missing because of impulse noise.
Method
Two ℓ0-based blind-inpainting models alternately restore the image and identify damaged pixels, using either an objective penalty or a constraint.
Results
The proposed methods perform better than other methods in experiments, while their algorithms converge to coordinatewise minimum points.
Takeaways & Limitations
Blind inpainting can jointly update the damaged-pixel set and restored image for impulse-noise removal, including mixed Gaussian impulse noise.
Takeaways & Limitations
A coordinatewise minimum need not be a local minimum unless the support update has a unique minimizer; for salt-and-pepper noise, blind-inpainting updates offer little improvement because AMF detection is already accurate.
Abstract
from arXiv · showhide
This article studies the problem of image restoration of observed images corrupted by impulse noise and mixed Gaussian impulse noise. Since the pixels damaged by impulse noise contain no information about the true image, how to find this set correctly is a very important problem. We propose two methods based on blind inpainting and $\ell_0$ minimization that can simultaneously find the damaged pixels and restore the image. By iteratively restoring the image and updating the set of damaged pixels, these methods have better performance than other methods, as shown in the experiments. In addition, we provide convergence analysis for these methods, these algorithms will converge to coordinatewise minimum points. In addition, they will converge to local minimum points (or with probability one) with some modifications in the algorithms.
1. Introduction.
The paper addresses restoration when impulse-damaged pixels are unknown, including mixed Gaussian impulse noise, where accurate damage detection is central to successful inpainting. It proposes blind-inpainting methods using ℓ0 minimization to identify damaged pixels and restore images jointly.
- Impulse noise can arise from malfunctioning camera pixels, faulty hardware memory, or transmission bit errors.
- The hardest setting has an unknown damaged region, requiring simultaneous recovery of lost details and removal of impulse noise.
- Robust fidelity approaches avoid explicitly finding damaged pixels but do not properly treat Gaussian noise in mixed Gaussian impulse-noise images.
- Two-stage methods first estimate the damaged region and then solve an inpainting problem, so their success depends on accurate detection.
- The proposed approach replaces ℓ1 with ℓ0 minimization and alternates between image inpainting and damaged-pixel identification.
- The paper reports convergence to coordinatewise minimum points, with modified algorithms reaching local minima or doing so with probability one.
2. Blind Inpainting Models using ℓ0 Term.
The models use ℓ0 minimization to formulate blind inpainting, either as an objective penalty or as a constraint. Alternating minimization separates image restoration from damaged-pixel estimation, producing tractable subproblems despite non-convexity.
- 2.1. Formulation.: The first model places the ℓ0 term in the objective, with λ1 tied to Gaussian-noise level and λ2 tied to impulse-noise level.
- 2.1. Formulation.: The ℓ0 formulation is non-convex and non-continuous, so an auxiliary binary matrix Λ transforms it into a continuous multi-convex problem.
- 2.1. Formulation.: Eliminating the auxiliary noise variable yields an image-only objective whose pixel fidelity is represented by the truncated function R0(x) = min(|x|2, 2λ2).
- 2.2. Algorithm.: The damaged-pixel update thresholds squared residuals against λ2, while ties permit either binary assignment.
- 2.2. Algorithm.: Alternating minimization solves a convex image-inpainting subproblem for fixed Λ and updates Λ in one separable step for fixed u.
- 2.2. Algorithm.: Initialization uses AMF for salt-and-pepper noise or ACWMF for random-valued noise, and the stopping rule compares successive objective values against ϵ.
3. Blind Inpainting Using Adaptive Outlier Pursuit.
Adaptive outlier pursuit (AOP) imposes an upper bound on the number of corrupted pixels and alternates image restoration with support updates. Its changing threshold is closely related to the first blind-inpainting algorithm, while experiments use AOP because its parameter is easier to obtain.
- The constrained model places the ℓ0 condition on the noise variable and reformulates it using a binary support matrix Λ.
- AOP iteratively reconstructs the image from pixels treated as reliable and identifies impulse-corrupted pixels from the current residuals.
- AOP assumes the number of impulse-corrupted pixels is bounded above by an estimated integer L.
- With the image fixed, AOP updates Λ by selecting pixels according to residual magnitudes while respecting the corruption-count constraint L.
- AOP changes λ2 during support updates, whereas algorithm 1 keeps λ2 fixed; the two methods have similar performance, but L is easier to obtain than λ2.
4. Convergence Analysis.
The two algorithms stop in finite steps at coordinatewise minimum points. Under additional conditions or randomized tie-breaking, they can instead reach local minima, including with probability one.
- If every minimizing Λ for a fixed u* also leaves u* minimizing F(u, Λ), then u* is a local minimum of E0(u).This condition combines the theorem’s requirement over all minimizing Λ with the resulting local-minimum guarantee.
- Both algorithms converge in finite steps to a coordinatewise minimum point of F(u, Λ).The guarantee applies when the subproblems are solved exactly; the finite number of binary Λ configurations supports finite termination.
- A coordinatewise minimum need not be a local minimum of F(u, Λ).Uniqueness of Λ as a minimizer at the corresponding u is a sufficient condition for local minimality.
- If Λ* uniquely minimizes F(u*, Λ), then (u*, Λ*) is a local minimum of F, and u* is a local minimum of E0.The result applies to a coordinatewise minimum point and connects uniqueness in the Λ-subproblem to local optimality.
- Selecting the best Λ among multiple minimizers can make the algorithm stop at a local minimum of E0(u).The selected Λ must have the lowest corresponding minu F(u, Λ), though many candidates may make this impractical.
- Adding a small random perturbation to the objective yields convergence to a local minimum with probability one.Random values make ties in the Λ-update occur with probability zero; the same reasoning applies to the AOP ordering tie.
5. Numerical Experiments.
The experiments evaluate total variation blind inpainting using AOP against established methods on salt-and-pepper and random-valued impulse noise, with and without Gaussian noise. Across tests, iterative damaged-pixel updating improves restoration and outlier identification, especially for random-valued impulse noise.
- Implementation: The experiments use total variation regularization across methods and solve the TV inpainting subproblem with split Bregman iteration.This common regularizer is selected to make comparisons fair.
- Experimental setup: Experiments use PSNR to evaluate restoration quality under salt-and-pepper or random-valued impulse noise, with optional additive Gaussian noise.The salt-and-pepper tests vary σ = 5, 10, 15 and s = 30%, 50%, 70%; random-valued tests use σ = 10, 25 and s = 25%, 40%.
- Salt-and-pepper impulse noise: Total variation blind inpainting using AOP outperforms AMF and TVL1 for salt-and-pepper impulse noise at all tested noise levels.Visual results show smoother flat backgrounds and preserved details, whereas AMF leaves noisy artifacts and TVL1 blurs details.
- Salt-and-pepper impulse noise: For salt-and-pepper noise, AOP is similar to a two-stage detector-then-inpaint method because AMF detects damaged pixels very accurately.The detected set changes little during AOP iterations, so adaptive updating provides limited additional improvement in this setting.
- Random-valued impulse noise: Total variation blind inpainting using AOP outperforms other tested methods for random-valued impulse noise at all tested noise levels.TVL1 outperforms ACWMF, particularly because ACWMF misses corrupted pixels and falsely detects noise-free pixels; AOP improves detection by iteratively updating the binary matrix Λ.
- Overall findings: AOP improves outlier identification and damaged-pixel recovery through iterative region updating, especially when random-valued impulse noise is severe.When s = 40%, ACWMF detection accuracy is very low, while AOP remains preferable; visual results show smooth flat regions with preserved details.
6. Conclusion.
The paper presents two blind-inpainting algorithms using ℓ0 minimization to remove impulse noise by iteratively restoring images and identifying damaged pixels. Both methods perform better than other methods in experiments, with similar performance between them.
- Two algorithms use blind inpainting and ℓ0 minimization, differing in whether the ℓ0 term is placed in the objective or constraint.
- Both methods iteratively restore images and identify damaged pixels to remove impulse noise.
- The two methods show similar performance and are connected through an explicit relationship.
- Experiments show that the proposed methods perform better than other methods.
- The approach can also be applied to cases where the noise model is not Gaussian.