Abstract
Signal decomposition is a classical problem in signal processing, aiming to separate an observed signal into two or more components, each characterized by its own property and typically described by a specific subspace or dictionary. While extensive research has focused on additive components, many real-world applications involve non-additive signals. For instance, an image may consist of a foreground object overlaid on a background, where each pixel belongs exclusively to one or the other. This paper proposes a framework for masked signal decomposition that finds a binary mask and subspace representations simultaneously. By relaxing the intractable binary optimization problem into a continuous one and employing an alternating optimization technique, the proposed method achieves significant improvements in text segmentation, motion separation in video, and 1D signal decomposition.
Introduction: The Non-Additive Challenge
In traditional signal processing, the standard model for decomposition is additive: $x = x_1 + x_2$. Methods like Robust Principal Component Analysis (RPCA) excel at separating signals that fit this model, such as a low-rank background and sparse noise. However, many digital signals are "masked" rather than additive. In a digital image with overlaid text, a pixel is either part of the text or part of the background texture. Mathematically, this is expressed as:
$$x = (1-w) \circ x_1 + w \circ x_2$$
where $w$ is a binary mask. Solving for $w$, $x_1$, and $x_2$ simultaneously is highly ill-posed and non-convex, as finding the optimal binary mask is an NP-hard combinatorial problem.
Proposed Framework: Masked Decomposition
Subspace Modeling
The authors leverage the fact that different signal components often reside in distinct subspaces. Each component is represented using a dictionary or basis ($P_1, P_2$) and a sparse coefficient vector ($\alpha_1, \alpha_2$):
$$x = (1 - w) \circ (P_1\alpha_1) + w \circ (P_2\alpha_2)$$
By choosing appropriate bases—such as the Discrete Cosine Transform (DCT) for smooth backgrounds and the Hadamard transform for sharp, high-frequency text—the algorithm can effectively distinguish between the two components.
Optimization via ADMM
To overcome the intractability of binary optimization, the authors apply a linear relaxation, allowing the mask $w$ to take continuous values in the range $[0, 1]$. The problem is then solved using the Alternating Direction Method of Multipliers (ADMM). This iterative approach breaks the global cost function into manageable sub-problems for the mask, the coefficients, and auxiliary variables. Key regularizations include:
- Sparsity ($\\ell_1$ norm): Encourages a sparse foreground mask.
- Total Variation (TV): Promotes spatial coherence, ensuring the mask forms connected regions rather than isolated noise.
Experimental Evaluation
The framework was tested across three domains:
- 1D Signals: Separating sinusoids from spike components.
- Text/Graphic Segmentation: Utilizing 332 image blocks from HEVC test sequences and synthetic "text-over-texture" images.
- Motion Segmentation: Separating moving objects from backgrounds in standard video sequences like "Stefan" and "Coastguard."
Key Results and Discussion
The proposed ADMM approach significantly outperformed traditional clustering and additive sparse decomposition methods. In text segmentation tasks, the method achieved an F1 score of 93.7%, compared to 77.2% for Hierarchical K-means and 80% for standard Sparse Decomposition.
A critical insight was the "Winner-Takes-All" advantage: by explicitly modeling the mask, the algorithm avoids the "ghosting" artifacts common in additive models where pixel energy is split incorrectly. Furthermore, the strategy of binarizing the mask only at the final step of optimization proved superior to enforcing binary constraints throughout the iterations.
Conclusion
Masked Signal Decomposition offers a robust solution for non-additive signal separation. While the current model relies on pre-defined subspaces, it demonstrates high precision and rapid convergence (typically under 10 iterations). Future work aims to integrate Dictionary Learning (e.g., K-SVD) to allow the algorithm to learn optimal subspaces directly from the data, further increasing its flexibility for complex real-world signals.
Summary updated