PaperlayerView exact revision on arXiv

Source-linked AI summary

Weighted Schatten $p$-Norm Minimization for Image Denoising and Background Subtraction

Yuan Xie, Shuhang Gu, Yan Liu, Wangmeng Zuo, Wensheng Zhang, Lei Zhang

arXiv:1512.01003v1cs.CV

TL;DR

WSNM addresses the over-shrinkage and equal treatment of rank components in nuclear-norm minimization for LRMA. It combines weighted singular-value penalties with Schatten p-norm regularization and provides an efficiently solvable formulation under non-descending weights. Experiments apply it to image denoising and background subtraction, where the paper reports improved recovery and state-of-the-art performance.

  • Problem

    NNM can over-shrink low-rank components and treats different singular values equally, limiting LRMA flexibility for practical applications.

  • Method

    WSNM assigns weights to singular values within Schatten p-norm regularization and reduces the problem to independently solvable subproblems under suitable weight ordering.

  • Results

    WSNM achieves improved recovery in image denoising and background subtraction, with WSNM-RPCA obtaining the best results on all nine test sequences.

  • Takeaways & Limitations

    WSNM provides flexible treatment of rank components and is reported to produce impressive improvements over state-of-the-art methods in the evaluated low-level vision tasks.

Abstract

from arXiv · show

Low rank matrix approximation (LRMA), which aims to recover the underlying low rank matrix from its degraded observation, has a wide range of applications in computer vision. The latest LRMA methods resort to using the nuclear norm minimization (NNM) as a convex relaxation of the nonconvex rank minimization. However, NNM tends to over-shrink the rank components and treats the different rank components equally, limiting its flexibility in practical applications. We propose a more flexible model, namely the Weighted Schatten $p$-Norm Minimization (WSNM), to generalize the NNM to the Schatten $p$-norm minimization with weights assigned to different singular values. The proposed WSNM not only gives better approximation to the original low-rank assumption, but also considers the importance of different rank components. We analyze the solution of WSNM and prove that, under certain weights permutation, WSNM can be equivalently transformed into independent non-convex $l_p$-norm subproblems, whose global optimum can be efficiently solved by generalized iterated shrinkage algorithm. We apply WSNM to typical low-level vision problems, e.g., image denoising and background subtraction. Extensive experimental results show, both qualitatively and quantitatively, that the proposed WSNM can more effectively remove noise, and model complex and dynamic scenes compared with state-of-the-art methods.

I. INTRODUCTION

LRMA recovers unknown low-rank matrices from degraded observations, but standard nuclear-norm methods can over-shrink components and treat them equally. WSNM introduces weighted Schatten p-norm regularization to model rank components more flexibly and is applied to image denoising and background subtraction.

  • Motivation: LRMA recovers unknown low-rank matrices from degraded observations for applications including background modeling, face recovery, and image restoration.These applications exploit low-rank or nonlocal self-similar structure.
  • Limitations of Existing Methods: NNM uses nuclear-norm regularization, but measurement noise can cause excessive shrinkage and deviation from rank-minimization solutions.The nuclear norm is a convex relaxation with an efficient soft-thresholding solution.
  • Limitations of Existing Methods: Schatten p-norm models can improve recovery accuracy, but typically treat all singular values equally and lack flexibility when rank components have different importance.The Schatten p-norm is defined as the l_p norm of the singular values for 0 < p ≤1.
  • Related Approaches: Weighted nuclear norm methods assign distinct weights to singular values, penalizing larger values less than smaller ones in applications such as image restoration.This produces more reasonable soft thresholds than traditional NNM.
  • Proposed Approach: WSNM generalizes weighted nuclear norm minimization by combining weights with Schatten p-norm regularization for more flexible low-rank approximation.WNNM is a special case of WSNM when p = 1.
  • Contributions: The paper presents a general WSNM solution, an efficient algorithm for non-descending weights, and applications to image denoising and background subtraction.The method is reported to achieve state-of-the-art performance in low-level vision applications.

B. General Solution of WSNM

The WSNM problem is reduced to singular-value optimization using the SVD of the observation. Although the resulting problem remains non-convex, its order constraint can be separated conceptually into independent subproblems solved by GST.

  • Problem Reduction: WSNM loses convexity because weighting is combined with the non-convex Schatten p-norm, making optimization more difficult.The reduced objective also contains an order constraint on the estimated singular values.
  • Problem Reduction: Using the SVD of Y, the optimal X shares Y's singular vectors, reducing WSNM to optimization over ordered singular values δ_i.The singular values of Y are assumed to be in non-ascending order.
  • Independent Subproblems: If the order constraint is discarded, the reduced objective decomposes into r independent non-convex l_p-norm subproblems.The order constraint is the main coupling between the singular-value variables.
  • Order Constraint: The independent solutions may violate the required singular-value ordering when weights are non-descending or arbitrary.Figure 1 illustrates these ordering violations through the horizontal coordinates of the three optima.
  • Independent Subproblems: Each independent subproblem can be solved using the generalized soft-thresholding algorithm, which selects either zero or a nonzero global optimum based on a threshold.The threshold depends on p and the corresponding weight w_i.

C. Efficient Solution with Non-descending Weights

The paper identifies non-descending weights as the condition that preserves the required singular-value ordering. Under this condition, WSNM becomes equivalent to independently solving the GST-based subproblems.

  • Ordering Condition: Different weight arrangements can cause independently optimized singular values to violate δ1 ≥ δ2 ≥ ... ≥ δr.The figure shows violations for non-ascending and arbitrary weight orders.
  • Ordering Condition: When weights satisfy 0 ≤ w1 ≤ w2 ≤ ... ≤ wr, the independent subproblem optima satisfy δ1 ≥ δ2 ≥ ... ≥ δr.This is the ordering guarantee established by Theorem 2.
  • Efficient Solution: Under non-descending weights, solving the independent subproblems is equivalent to solving the coupled WSNM problem.The resulting subproblems can be handled by the proposed GST-based algorithm.
  • Weight Interpretation: Non-descending weights are meaningful in computer vision because larger singular-value components are more important and should receive less shrinkage.This motivates assigning weights inversely to the importance of the singular components.

III. APPLYING WSNM TO IMAGE DENOISING AND BACKGROUND SUBSTRACTION

WSNM is applied to low-rank patch matrices for image denoising and to low-rank-plus-sparse models for background subtraction. In denoising, weights reflect singular-value importance, and iterative aggregation reconstructs the image.

  • B. WSNM-RPCA for Background Subtraction: WSNM-RPCA replaces nuclear-norm regularization in low-rank-plus-sparse decomposition while retaining l1-norm enforcement for sparse errors.The resulting model separates an observed matrix into low-rank and sparse components.
  • A. WSNM in Image Denoising: WSNM estimates clean patch matrices from noisy nonlocal similar patches under an additive white Gaussian noise model.The observed patch matrix is modeled as Yi = Xi + Ni, with Xi estimated using WSNM.
  • A. WSNM in Image Denoising: Weights are set inversely proportional to estimated singular values because larger singular values represent more important components and should be shrunk less.The paper initializes unavailable optimal singular values before estimation and uses ε = 10^-16 to avoid division by zero.
  • A. WSNM in Image Denoising: The denoising pipeline repeatedly estimates patch weights, forms similar-patch matrices, aggregates recovered patches, and adds filtered residuals through iterative regularization.The final image is reconstructed by aggregating denoised patches.

B. WSNM-RPCA for Background Subtraction

WSNM-RPCA substitutes weighted Schatten p-norm regularization for nuclear-norm regularization in background subtraction. Its alternating optimization has a stated accumulation-point result under ordered weights, but nonconvexity makes convergence analysis difficult.

  • B. WSNM-RPCA for Background Subtraction: WSNM-RPCA replaces NNM in RPCA while l1-norm regularization keeps the error matrix robust to sparse noise.The model targets background subtraction formulated as low-rank matrix analysis.
  • B. WSNM-RPCA for Background Subtraction: The augmented Lagrange problem is optimized by minimizing each variable alternately while fixing the others.The paper describes this procedure using alternating direction minimization.
  • B. WSNM-RPCA for Background Subtraction: Because the weighted Schatten p-norm is nonconvex and lacks a general subgradient, convergence analysis is substantially more difficult.The theorem provides an accumulation-point result rather than a guarantee that the sequence converges to a local minimum.
  • B. WSNM-RPCA for Background Subtraction: When 0 ≤ w1 ≤ w2 ≤ … ≤ wr, the algorithm's sequence has at least one accumulation point and its accumulation points form a compact continuum.These are the stated convergence properties for Algorithm 4.

A. Image Denoising

The denoising experiments examine how WSNM’s power p affects recovery across noise levels and compare it with established methods. WSNM reduces over-shrinkage and achieves stronger quantitative and visual denoising results, especially as noise increases.

  • 1) Advantages of the Weighted Schatten p-Norm:: WSNM reduces singular-value over-shrinkage as p decreases, bringing more high-rank components closer to their clean-image values.The p = 1 solution deviates substantially, whereas smaller p values improve alignment with the clean singular values.
  • 1) Advantages of the Weighted Schatten p-Norm:: The best p values decrease as noise increases: 1.0, 0.85, and 0.75 for noise levels 20, 30, and 50, versus 0.7, 0.1, and 0.05 for 60, 75, and 100.The study evaluates 40 Berkeley Segmentation Dataset images across six noise levels, using averaged PSNR to select p.
  • 2) Comparison with State-of-the-Art Methods:: The denoising comparison uses BM3D, PBNO, SAIST, EPLL, GID, and WNNM on 20 test images corrupted by Gaussian noise at six variance levels.Results are generated using authors’ source code or executables with parameter settings from the original papers.
  • 2) Comparison with State-of-the-Art Methods:: WSNM achieves the highest PSNR in almost all cases and outperforms competing methods at every tested noise level.Average gains over WNNM increase from 0.03 dB at noise level 20 to 0.1 dB at 50 and 0.12 dB at 100.
  • 2) Comparison with State-of-the-Art Methods:: WSNM also produces better visual quality, recovering face structure and butterfly wing veins with fewer artifacts than competing methods.These qualitative differences are reported in the highlighted regions of Figures 5–8, including the noise-level-100 example.

B. Experimental results for WSNM-RPCA

WSNM-RPCA improves low-rank matrix recovery under sparse corruption and performs strongly in denoising and background subtraction experiments. The reported results show broader successful recovery and clearer foreground extraction than competing models.

  • Synthetic Evaluations: WSNM-RPCA with p = 0.7 gives the best latent-matrix recovery, while p = 0.4 improves over NNM-RPCA but remains sensitive to rank and noise.NNM-RPCA fails to estimate intrinsic rank as rank or corruption increases; WNNM-RPCA and WSNM-RPCA with p = 0.4 are also sensitive.
  • Synthetic Evaluations: WSNM-RPCA achieves larger success areas than NNM-RPCA and WNNM-RPCA in recovering low-rank matrices with sparse noise.Both p = 0.7 and p = 0.4 outperform the competing RPCA models in the log-scale relative-error evaluation.
  • Image Denoising: WSNM produces higher PSNR than the listed alternatives on the Lolly, Boat, Monarch, and House examples.For example, WSNM reaches 29.00dB on Lolly and 27.01dB on Boat at σn = 50.
  • Background Subtraction: WSNM-RPCA achieves the best quantitative background-subtraction results on all nine test sequences.Visual results also show clear backgrounds and accurate foreground separation, whereas other methods produce ghost shadows and incomplete segmentation.

VI. APENDIX

The appendix develops the scalar optimization underlying WSNM and analyzes the generalized iterated shrinkage procedure. It establishes the relevant inequalities and boundedness properties used in the optimization analysis.

  • Appendix: The WSNM matrix optimization can be reduced to minimizing a problem over singular values when the singular-vector alignment condition holds.The equality condition requires the singular vectors of the solution and observation to align.
  • Appendix: Because the scalar equation is non-trivial to solve directly, the appendix analyzes the iterative algorithm used to solve it.The proof establishes the relevant inequality for successive generalized shrinkage iterates.
  • Appendix: The generalized shrinkage iterates satisfy the target inequality for every nonnegative iteration index, completing the proof of the stated lemma.The argument separately handles the cases where the input is below or above the generalized threshold.

C. Proof of Theorem 2

The proof of Theorem 2 establishes the required monotonicity properties of the unique scalar generalized-shrinkage minimum with respect to its input and weight.

  • Proof of Theorem 2: Theorem 2 is reduced to verifying two inequalities for the unique minimum SGST^p(y; w), viewed as an implicit function of y and w.One inequality fixes w, while the other fixes y.
  • Proof of Theorem 2: For fixed w, the required inequality follows from a result proved in prior work.The proof then combines this fact with the fixed-y inequality established by Lemma 2.
  • Proof of Theorem 2: Combining the two inequalities establishes the target relation and completes the proof of Theorem 2.

D. Proof of Theorem 3

The proof of Theorem 3 establishes boundedness and feasibility properties for the iterative WSNM-RPCA sequence, then shows that consecutive iterates converge in difference.

  • Proof of Theorem 3: The generalized soft-thresholding step produces the singular-value matrix used in the WSNM-RPCA update.This operation is incorporated into step 6 of the WSNM-RPCA algorithm.
  • Proof of Theorem 3: The sequence {Zk} is bounded because the singular-value update is bounded by the iteration count in Algorithm GST.
  • Proof of Theorem 3: Bounded Zk prevents the augmented Lagrange function from diverging through unbounded Xk or Ek, so Xk and Ek are also bounded.Consequently, the sequence has at least one accumulation point.
  • Proof of Theorem 3: Every accumulation point is feasible for the objective function.
  • Proof of Theorem 3: The proof separately analyzes E and X to show that the difference between consecutive iterations tends to zero.
Loading 1512.01003v1…