Iterative block tensor singular value thresholding for extraction of lowrank component of image data

Longxi Chen, Yipeng Liu, Ce Zhu

TL;DR

This paper introduces a novel method called Iterative Block Tensor Singular Value Thresholding (IBTSVT) to extract low-rank components from high-dimensional data represented as tensors. By decomposing the tensor into smaller blocks and applying a modified singular value thresholding technique to each block, IBTSVT effectively separates background from foreground in surveillance videos and normalizes illumination in face images, outperforming existing methods.

What Problem Does This Paper Address?

High-dimensional data, often represented as tensors, is prevalent in fields like image and video processing. While Principal Component Analysis (PCA) is a standard technique for 2D data, extending it to tensors (Tensor PCA) is crucial for leveraging the inherent structure of multi-way data. Existing tensor decomposition methods often struggle with the computational complexity of large tensors or don't fully exploit the data's structure. Specifically, robust PCA (RPCA) aims to decompose data into a low-rank component and a sparse component, but applying it directly to large tensors can be inefficient. This paper addresses the challenge of efficiently and effectively extracting low-rank components from large tensors, particularly when the data exhibits block-like structures, by proposing a block-wise decomposition approach.

Methods

The core of the proposed method, IBTSVT, lies in decomposing the input tensor $X \in \mathbb{R}^{n_1 \times n_2 \times n_3}$ into multiple smaller block tensors, $X_p$, each of size $n \times n \times n_3$. For each block tensor $X_p$, the goal is to decompose it into a low-rank component $L_p$ and a sparse component $S_p$, such that $X_p = L_p + S_p$. The extraction of the low-rank component $L_p$ is achieved by minimizing its tensor nuclear norm, which is related to the sum of singular values of its frontal slices after a Fast Fourier Transform (FFT) along the third dimension.

The paper introduces "block tensor incoherence conditions" to ensure successful decomposition. The actual low-rank component extraction for each block uses an iterative singular value thresholding approach in the Fourier domain. This involves applying a soft thresholding operator, denoted by $D_{\tau}$, to the block tensor's transformed representation. The thresholding parameter $\tau$ is crucial and is discussed as being experience-based, with a suggestion of $\tau = 1/\sqrt{nn_3}$ for denoising, but acknowledging that it needs adjustment for applications with non-uniformly distributed sparse components. The final low-rank component of the original tensor is obtained by concatenating the low-rank components of all the blocks.

Datasets

The paper evaluates its method on two real-world datasets:

  • Surveillance Videos: A dataset of 20 frames, each of size $144 \times 176$, is used for motion separation.
  • Yale B Face Database: This dataset consists of face images of size $192 \times 168$ captured under 64 different lighting conditions, used for illumination normalization.

Key Insights and Ideas

  • Block-wise Decomposition for Efficiency: Decomposing a large tensor into smaller blocks significantly reduces computational complexity compared to processing the entire tensor at once. This is a key enabler for handling large-scale tensor data.
  • Leveraging Block Structure: The method explicitly assumes and exploits the idea that some data might have inherent block structures, making a block-wise approach more effective than a global one.
  • Iterative Thresholding for Low-Rank Extraction: The use of iterative singular value thresholding, adapted for tensors via the t-SVD and FFT, is a robust way to extract the low-rank component from each block.
  • Importance of Incoherence Conditions: The paper highlights the theoretical necessity of "block tensor incoherence conditions" for guaranteeing the successful separation of low-rank and sparse components.
  • Adaptive Thresholding: The authors recognize that the thresholding parameter is application-dependent, especially when dealing with non-uniform sparse components like shadows or motion, suggesting the need for careful tuning.

Key Results

The IBTSVT method demonstrates strong performance in two applications:

  • Motion Separation for Surveillance Videos: The method successfully separates the background (low-rank component) from moving objects (sparse component), visually identifying pedestrians in the video.
  • Illumination Normalization for Face Images: IBTSVT effectively removes shadows and illumination variations from face images, resulting in "almost shadow-free faces." This is quantitatively shown by a significant improvement in face and eye detection accuracy using the Viola-Jones algorithm.
  • Face Detection Accuracy: IBTSVT achieved 0.844, compared to 0.375 for low rank + sparsity and 0.359 for multiscale low rank.
  • Eye Detection Accuracy: IBTSVT achieved 1.00, matching the multiscale low rank method but significantly outperforming low rank + sparsity (0.70).
  • Computational Time: IBTSVT was significantly faster, processing 64 face images in 715 seconds, compared to 10 seconds for low rank + sparsity and 4472 seconds for multiscale low rank. The speedup is attributed to parallel processing of block tensors.

Limitations and Future Work

  • Block Size Selection: The paper notes that the block size is a critical parameter. If too large, the sparse part might contain low-rank components; if too small, computational time increases due to the large number of t-SVDs. The authors suggest a block size of $2 \times 2 \times n_3$ as a general choice.
  • Thresholding Parameter Tuning: The thresholding parameter $\tau$ is identified as difficult to determine and is currently set based on experience. The paper suggests that for different applications with non-uniformly distributed sparse components, this parameter needs careful adjustment.
  • Future Work: The paper's success in these two applications suggests that IBTSVT could be applied to other problems involving high-dimensional data with block structures, such as shadow removal in general images or motion segmentation in other types of video data. Further research could focus on developing more principled methods for block size selection and automatic thresholding parameter estimation.

Summary updated

Abstract

Tensor principal component analysis (TPCA) is a multi-linear extension of principal component analysis which converts a set of correlated measurements into several principal components. In this paper, we propose a new robust TPCA method to extract the princi- pal components of the multi-way data based on tensor singular value decomposition. The tensor is split into a number of blocks of the same size. The low rank component of each block tensor is extracted using iterative tensor singular value thresholding method. The prin- cipal components of the multi-way data are the concatenation of all the low rank components of all the block tensors. We give the block tensor incoherence conditions to guarantee the successful decom- position. This factorization has similar optimality properties to that of low rank matrix derived from singular value decomposition. Ex- perimentally, we demonstrate its effectiveness in two applications, including motion separation for surveillance videos and illumination normalization for face images.
BibTeX
@inproceedings{chen2017iterative,
  author = {Longxi Chen and Yipeng Liu and Ce Zhu},
  title = {{Iterative block tensor singular value thresholding for extraction of lowrank component of image data}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2017},
  url = {https://openreview.net/forum?id=-jlB7K2f1i},
}
Figure