Robust Subspace Estimation Using Low-Rank Optimization

In this chapter, we first review the problem of linear subspace estimation and present example problems where the conventional method (PCA) is typically used. Consequently, we discuss the most prominent advances in low-rank optimization, which is the main theoretical topic of this book. Since the various low-rank formulations discussed in this book fall into several computer vision domains, we additionally review the latest techniques in each domain, including video denosing, turbulence mitigation, background subtraction, and activity recognition.

Several attempts have been lately proposed to tackle the problem of recovering the original image of an underwater scene using a sequence distorted by water waves. The main drawback of the state of the art is that it heavily depends on modelling the waves, which in fact is ill-posed since the actual behavior of the waves along with the imaging process are complicated and include several noise components; therefore, their results are not satisfactory. In this chapter, we address the problem by formulating a data-driven two-stage approach, each stage is targeted towards a certain type of noise. The first stage leverages the temporal mean of the sequence to overcome the structured turbulence of the waves through an iterative registration algorithm. The result of the first stage is a better structured sequence, in which the low-rank property is uncovered, thus allowing us to employ low-rank optimization as a second stage in order to eliminate the remaining sparse noise.

Turbulence mitigation refers to the stabilization of videos with non-uniform deformations due to the influence of optical turbulence. Typical approaches for turbulence mitigation follow averaging or de-warping techniques. Although these methods can reduce the turbulence, they distort the independently moving objects which can often be of great interest. In this chapter, we address the problem of simultaneous turbulence mitigation and moving object detection. We discuss a three-term low-rank matrix decomposition approach in which we decompose the turbulence sequence into three components: the background, the turbulence, and the object. This extremely difcult problem is simplified into a minimization of nuclear norm, Frobenius norm, and ℓ ₁ norm. This method is based on two observations: First, the turbulence causes dense Gaussian noise, and therefore can be captured by Frobenius norm (as the Frobenius norm is equivalent to a squared loss function), while the moving objects are sparse and thus can be captured by ℓ ₁ norm. Second, since the objects motion is linear and intrinsically different than the Gaussian-like turbulence, a Gaussian-based turbulence model can be employed to enforce an additional constraint on the search space of the minimization. We demonstrate the performance of the discussed approach on challenging sequences which are signicantly distorted with atmospheric turbulence and include extremely tiny moving objects.

Recognition of human actions in a video acquired by a moving camera typically requires standard preprocessing steps such as motion compensation, moving object detection and object tracking. The errors from the motion compensation step propagate to the object detection stage, resulting in miss-detections, which further complicates the tracking stage, resulting in cluttered and incorrect tracks. Therefore, action recognition from a moving camera is considered very challenging. In this chapter, we discuss an approach which does not follow the standard steps, and accordingly avoids the aforementioned difculties. The approach is based on Lagrangian particle trajectories which are a set of dense trajectories obtained by advecting optical flow over time, thus capturing the ensemble motions of a scene. This is done in frames of unaligned video, and no object detection is required. Consequently, in order to handle the moving camera, a low-rank trajectory decomposition approach is employed, where the trajectories are decomposed into their camera-induced and object-induced components. Having obtained the relevant object motion trajectories, a compact set of chaotic invariant features are computed, which captures the characteristics of the trajectories. Finally, a SVM is employed to learn and recognize the human actions using the computed motion features.

Complex event recognition is the problem of recognizing events in long and unconstrained videos. Examples of such events are birthday party, changing a tire, making a fire …etc. In this extremely challenging task, concepts have recently shown a promising direction, where core low-level events referred to as concepts are annotated and modelled using a portion of the training data, then each complex event is described using concept scores, which are features representing the occurrence confidence for the concepts in the event. However, because of the complex nature of the videos, both the concept models and the corresponding concept scores are significantly noisy. In order to address this problem, we discuss a low-rank formulation, which combines the precisely annotated videos used to train the concepts, with the rich concept scores. The approach presented in this chapter finds a new representation for each event, which is not only low-rank, but also constrained to adhere to the concept annotation, thus suppressing the noise, and maintaining a consistent occurrence of the concepts in each event. Extensive experiments on large scale real world dataset TRECVID Multimedia Event Detection 2011 and 2012 demonstrate that the approach consistently improves the discriminativity of the concept scores by a significant margin.

In this book, we presented four low-rank optimization-based solutions for fundamental computer vision problems including scene reconstruction, turbulence mitigation, background subtraction, and action recognition.

In this chapter, we include the extended derivations for the solutions of the low-rank optimization problems which appeared in Chap. 4