Foreground–Background Separation in Videos

Convex vs. Non-Convex Methods (PCP, GoDec, ADMM)

This project performs background–foreground separation in video sequences using three different matrix decomposition methods:

• PCP (Principal Component Pursuit) – convex RPCA
• GoDec – fast non-convex approximation
• ADMM-based RPCA – augmented Lagrangian optimization

The goal is to decompose a video into:

[ D = L + S ]

where:

• L = low-rank background
• S = sparse foreground (moving objects)

---

1. Overview

A video is loaded frame by frame, converted to grayscale, resized, vectorized, and stored as columns of the data matrix. Each method then performs Low-Rank + Sparse decomposition to extract the static background and dynamic foreground.

The project includes full visualization for all frames:

• Original frame
• Background estimated by each method
• Foreground extracted by each method

---

2. Implemented Methods

---

🟦 A. PCP – Principal Component Pursuit (Convex RPCA)

Solves the convex optimization problem:

[ \min_{L,S} |L|_* + \lambda |S|_1 \quad \text{s.t. } D = L + S ]

• Nuclear norm → promotes low rank
• L1 norm → promotes sparsity
• Very accurate but computationally slow
• Ideal for high-quality separation

In the code:

[L2, S2] = PCP(D, lambda_pcp, tol);

---

B. GoDec – Alternating Projections (Non-Convex)

Fast non-convex method using alternating projections:

1. Projection onto low-rank matrices (rank ≤ r)
2. Projection onto sparse matrices (cardinality ≤ k)

Model:

[ \min_{L,S} |D - L - S|_F^2 ]

• Much faster than PCP
• Good approximation for long videos
• Requires choosing rank r and sparsity k

In the code:

[L3, S3, ~, ~] = GoDec(D, rank_godec, card, power);

---

C. ADMM for RPCA (Augmented Lagrangian)

Uses the augmented Lagrangian:

[ \mathcal{L}*\beta(L,S,\Lambda)= |L|** + \lambda|S|_1 + \frac{\beta}{2}|D - L - S + \frac{1}{\beta}\Lambda|_F^2 ]

Updates:

• SVT (Singular Value Thresholding) for ( L )
• Soft-thresholding for ( S )
• Dual update for ( \Lambda )

A good compromise between PCP accuracy and GoDec speed.

In the code:

[L4, S4, ~, ~] = RPCA_ADMM(D, lambda_admm, p_admm, maxIter_admm);

---

3. Program Pipeline

1. Read video

2. Convert each frame to grayscale

3. Resize frames

4. Vectorize each frame

5. Construct matrix (D)

6. Run:

   • PCP
   • GoDec
   • ADMM

7. Display in real-time:

Original | PCP Background | GoDec Background | ADMM Background
         | PCP Foreground | GoDec Foreground | ADMM Foreground