Keywords: . . . . . D.1 LRSLibrary GUI. . . . . . . . . . . . . . moving object detection, background/foreground separation, low-rank and sparse representation, matrix decomposition, tensor factorization

6.4 FG results on 1 st and 2 nd videos of the MSVS dataset. (a) input image, (b) ground truth, (c) results for only RGB, (d) for only 6 visible bands, and (e) for 1 NIR spectral band alone. . . . . . . . . . . . . . . . . . . . . . . . . . 6.5 FG results on the 3 rd video of the MSVS dataset (red = FP). From top to bottom:

First I would like to express my gratitude to my supervisors, Dr. Thierry Bouwmans and Dr. El-hadi Zahzah for their invaluable guidance and advices. I would also like to take this opportunity to thank the CAPES/Brésil for providing me a full Ph.D. scholarship. Thank you to the Computer Vision Centre (CVC) members for having welcomed me (Doctoral stage), especially Dr. Jordi Gonzàlez. Without the above supports, this thesis is impossible.

I would like to thank Dr. Lucia Maddalena from ICAR-CNR (Italy) and Prof. Alfredo Petrosino from Univ. of Naples Parthenope (Italy) for their acceptances to be the reviewers of the this European thesis manuscript and for sharing interesting comments and criticism that helped improve this manuscript.

Sincere thanks to my dissertation examiners, Prof. Laure Tougne from Univ. of Lyon (France), Dr. Francois Brémond from INRIA Sophia-Antipolis (France) and Mehran Yazdi from Univ. of Shiraz (Iran), for their interest in my work and for making their time available for me.

I am very grateful to my family for their unconditional love and support without which this journey would not have been possible. My gratefulness is also my beloved fiancee Caroline Pacheco for her inspiring support and for being my best companion in this challenging journey.

Last but not least, I would also like to thank my friends and colleagues from the University of La Rochelle, especially those from the L3I and MIA labs. Their support has been invaluable throughout my Ph.D. study, making my time both memorable and enjoyable. i

Abstract

The detection of moving objects is an important step in computer vision field to develop numerous kinds of systems, such as intelligent video surveillance, motion capture, among the others. These systems are used in a wide range of applications, including retail, home automation, safety and security. The most commonly used equipment are stationary cameras or pan-tilt-zoom (PTZ) cameras to monitor activities in outdoor or indoor environments. Since the cameras are stationary (or almost stationary), the detection of moving objects can be achieved by building a representation of the scene background and comparing each new frame with this one. This process is called background subtraction, also named background/foreground separation.

More recently, the research on decomposition into low-rank plus sparse matrices (or tensors) has been showing to be a suitable framework to deal with the background/foreground separation problem. This framework consider that the data to be processed satisfy two important assumptions: a) the inliers (latent structure) are drawn from a single or a union of low-dimensional subspaces, and b) the corruptions are sparse. This assumption holds a particular association to the problem of background/foreground separation, where the background model (almost static) is represented as a low-rank structure and the foreground objects are associated with the sparse residuals. However, the key issues and challenges in such approaches are their capabilities to handle complex and dynamic background scenarios, as well as performing in a real-time manner.

Given the importance of this subject, this thesis introduces the recent advances on decomposition into low-rank plus sparse matrices and tensors, as well as the main contributions to face the principal issues in moving object detection. First, we present an overview of the state-of-the-art methods for low-rank and sparse decomposition, as well as their application to background modeling and foreground segmentation tasks. Next, we address the problem of background model initialization as a reconstruction process from missing/corrupted data. A novel methodology is presented showing an attractive potential for background modeling initialization in video surveillance. Subsequently, we propose a double-constrained version of robust principal component analysis to improve the foreground detection in maritime environments for automated video-surveillance applications. The algorithm makes use of double constraints extracted from spatial saliency maps to enhance object foreground detection in dynamic scenes. We also developed two incremental tensor-based algorithms in order to perform background/foreground separation from multidimensional streaming data. These works address the problem of low-rank and sparse decomposition on tensors. Finally, we present a particular work realized in conjunction with the Computer Vision Center (CVC) at Autonomous University of Barcelona (UAB).

iii

Résumé

La détection d'objets mobiles dans des vidéos acquises à partir de caméras est une étape importante dans plusieurs systèmes automatiques de vision par ordinateur. Ces systèmes sont utilisés dans une large gamme d'applications, comprenant entre autres la Vidéo-Surveillance Intelligente (VSI) et la capture de mouvement optique. Les équipements les plus utilisés sont des caméras fixes ou pan-tilt-zoom (PTZ) pour surveiller les activités dans les environnements extérieurs ou intérieurs. Étant donné que les caméras sont fixes (ou presque stationnaires), la détection d'objets mobiles peut être obtenue en construisant une représentation du modèle du fond et comparant chaque nouvelle image avec ce modèle. Ce processus est appelé soustraction de fond ou séparation fond et objets du premier plan.

Les récentes avancées en ACP robuste par décomposition en matrices (ou tenseurs) de rang faible et parcimonieuse montrent un grand potentiel pour séparer les objets en mouvement dans des vidéos. Cette formulation de problème considère que les données à traiter ont deux hypothèses importantes: a) les inliers (structure latente) proviennent d'un seul sousespace (ou d'une union de sous-espaces) de dimension faible, et b) les données corrompues outliers sont de caractères parcimonieuses. Cette hypothèse est particulièrement adaptée au problème de la séparation entre le fond et les objets du premier plan, où le modèle du fond (presque statique) est représenté par une structure de rang faible et les objets de premier plan sont associés aux résidus parcimonieux. Cependant, les principaux enjeux et défis dans telles approches sont ses capacités à gérer des scénarios de fond complexes et dynamiques ainsi que l'exécution incrémentale et en temps-réel.

Dans ce contexte, cette thèse introduit les avancées récentes sur la décomposition en matrices (et tenseurs) de rang faible et parcimonieuse ainsi que les contributions pour faire fâce aux principaux problèmes dans ce domaine. Nous présentons d'abord un aperc ¸u des méthodes matricielles et tensorielles les plus récentes ainsi que ses applications sur la soustraction de fond. Ensuite, nous abordons le problème de l'initialisation du modèle de fond comme un processus de reconstruction à partir de données manquantes ou corrompues. Une nouvelle méthodologie est présentée montrant un potentiel intéressant pour l'initialisation de la modélisation du fond dans le cadre de VSI. Par la suite, nous proposons une version double contrainte de l'ACP robuste pour améliorer la détection de premier plan en milieu marin dans des applications de vidéo-surveillance automatisés. Nous avons aussi développé deux algorithmes incrémentaux basés sur tenseurs afin d'effectuer une séparation entre le fond et le premier plan à partir de données multidimensionnelles. Ces deux travaux abordent le problème de la décomposition de rang faible et parcimonieuse sur des tenseurs. A la fin, nous présentons un travail particulier réalisé en conjonction avec le Centre de Vision Informatique (CVC) de l'Université Autonome de Barcelone (UAB). 11 Illustration of a Tucker model for a third-order tensor. A third-order tensor is decomposed as the sum of a low-rank tensor (a core tensor multiplied by its factor matrices) and a residual tensor. Image adapted from [START_REF] Acar | Unsupervised multiway data analysis: A literature survey[END_REF][START_REF] Kolda | Tensor decompositions and applications[END_REF]. . . . . . . 2.12 Illustration of the CP decomposition of a third-order tensor as the sum of rank-1 tensors u r1 •u r2 •u r3 for r ∈ {1, 2, . . . , R}. Image adapted from [START_REF] Acar | Unsupervised multiway data analysis: A literature survey[END_REF][START_REF] Kolda | Tensor decompositions and applications[END_REF]. 2. [START_REF] Baker | Low-rank incremental methods for computing dominant singular subspaces[END_REF] Extending robust principal component analysis on a third-order tensor. . . . . to right: (a) input frame, (b) saliency map with its temporal median subtracted (due to the high saliency from the buildings around the river), (c) low-rank component, (d) sparse component, (e) foreground mask, and (f) ground truth. 65 5.1 Block diagram of the proposed approach. In the step (a), the last N frames from a streaming video are stored in a sliding block or tensor A t . Next, a feature extraction process is done at step (b) and the tensor A t is transformed in another tensor T t (step (c)) . In (d), an incremental higher-order singular value decomposition (iHOSVD) is applied in the tensor T t resulting in a lowrank tensor L t . Finally, in the step (e) a foreground detection method is applied for each new frame to segment the moving objects. . . . . . . . . . . Chapter 1

Introduction

In this chapter, we provide the thesis context concerning the application of low-rank and sparse decomposition to the problem of moving object detection in videos.

Presentation

The detection of moving objects is an important step in computer vision to develop numerous kinds of systems, such as intelligent video surveillance and motion capture, among the others [START_REF] Bouwmans | Background Modeling and Foreground Detection for Video Surveillance[END_REF][START_REF]Background Subtraction: Theory and Practice[END_REF][START_REF] Shaikh | Moving Object Detection Using Background Subtraction[END_REF]. These systems are used in a wide range of applications, including retail, home automation, safety and security [START_REF]An introduction to video content analysis -industry guide[END_REF]. For example, in visual surveillance systems, the detection of moving objects can be important to identify useful insights from video data, such as intrusion/anomaly detection, abandoned objects, traffic data collection, etc. These insights are usually extracted after a sequence of video processing steps that are part of a more general module named Video Content Analysis (VCA), also known as Intelligent Video Analytics. Figure 1.1 summarizes the approach described here, where a VCA module is used to auto- matically report road traffic incidents. In many domains, VCA is implemented on CCTV systems, where the most commonly used equipments are stationary cameras or pan-tilt-zoom (PTZ) cameras to monitor activities in outdoor or indoor environments. Since the cameras are stationary (or almost stationary), the detection of moving objects can be achieved by building a representation of the scene background and comparing each new frame with this one. This process is called background subtraction (BS), also named background/foreground (B/F) separation, and the scene representation is called the background model (BM) [START_REF] Bouwmans | Background Modeling and Foreground Detection for Video Surveillance[END_REF][START_REF]Background Subtraction: Theory and Practice[END_REF]. This basic operation works as a two-class classifier and it consists in separating the moving objects called "foreground" (FG), from the static (or quasi static) information, called "background" (BG). Typically the BS process includes three main steps: a) background model initialization, b) background model maintenance, and c) foreground detection (see block diagram in Figure 1.2). These steps work as follows:

• Model initialization -In general, this step consists in creating a BM that best represents the scene background. It is often assumed that initialization can be achieved by exploiting some "clean" frames (free of foreground objects) at the beginning of the sequence, and the scene here is assumed to be stationary or quasi stationary. However, this assumption is rarely encountered in indoor or outdoor scenarios, because several challenges appear and perturb this process, such as noise acquisition, dynamic factors, etc. [25,[START_REF] Maddalena | Background model initialization for static cameras[END_REF].

• Model maintenance -In real-life scenarios, there are changes that occur over time. These changes can be local, such as a moving object entering (or leaving) the scene, or global, such as day-light inference [START_REF] Bouwmans | Background Modeling and Foreground Detection for Video Surveillance[END_REF][START_REF]Background Subtraction: Theory and Practice[END_REF]. It is important for any BM to adapt to these changes. The model maintenance step aims to preserve and maintain the BM learned in the initialization step to be as close as possible to the real scene background.

• Foreground detection -Given the representation of the scene background, the foreground detection step consists in comparing the learned background model with the input frame. This process depends on the type of changes expected in the scene background. These changes could be related to a specific object of interest or any other 1.1. Presentation 3 factor, such as noise, illumination changes, among the others [START_REF] Bouwmans | Background Modeling and Foreground Detection for Video Surveillance[END_REF][START_REF]Background Subtraction: Theory and Practice[END_REF]. The main challenge of this step is to minimize the number of false positive and false negative pixels.

The BS process must deal with a large number of challenges that may occur during its application for moving object detection, as described below:

• Camera jitter: In general, the camera jitter occurs when a fixed camera is affected by natural or environmental events, such as strong winds or earthquake. In such cases, the fixed camera presents a nominal motion that is usually indistinguishable from the motion of the foreground objects, leading to undesirable detection results.

• Camera automatic adjustments: Today, most of digital cameras have automatic adjustments, such as automatic exposure mode. This feature automatically determines the correct exposure for pictures. In automatic mode, the cameras make some decisions without any user input, including the aperture setting, the shutter speed and white balance. These settings may make difficult the task of segmentation.

• Pan-Tilt-Zoom (PTZ) cameras: Most of background subtraction research is focused on stationary cameras. However, the adoption of PTZ cameras for intelligent video surveillance became more frequent because of their ability to cover a wide field of view. These cameras are capable of (automatically or manually) remote directional and zoom control. In general, most of background subtraction algorithms fail in the case of moving cameras, due to the non stationarity of the background.

• Video noise: In general, a video signal can be contaminated by noise in the recording process. The noise is usually a random pattern that is caused by signal transmission/acquisition, coding, and between the processing steps. Usually, this phenomenon can produce undesirable effects or artifacts affecting the background scenes.

• Intermittent object motion: In some cases, moving objects stop for a long period of time or a background object starts moving. In such situations, the intermittent objects can produce "ghosting" artifacts in the background model. Typical examples include parking vehicles and abandoned objects. Dealing with these situations depends on the context. For some applications, motionless foreground objects must be incorporated into the background model and others not.

• Dynamic backgrounds: Dynamic factors of the environment are one of the main causes of dynamic backgrounds that are generally the outcome of an external event or a chain of events, such as flowing water and moving leaves caused by winds. In such environment, modeling a good representation of the background is a challenging task for a background subtraction algorithm, due to the separation of the dynamics of the foreground objects in comparison to the natural dynamics of the scene background.

• Shadows: Normally shadows are generated as result of a light source blocked by an opaque object. Shadows can be seen as a dark area that either may be attached or not to detected objects, causing objects merging and objects shape distortion. The presence of shadows usually does not allow a robust shape detection of moving objects. In general, the shadow areas are often misclassified as foreground objects, causing errors in the segmentation of moving objects. • Bootstrapping: It is often assumed that a representative model of the background can be produced by exploiting some clean frames (without moving objects) at the beginning of the sequence. However, this assumption is rarely encountered in reallife scenarios, because of continuous clutter presence. In such situations, a robust initialization process of the background model must be adopted, learning the correct background model over time.

INTRODUCTION

• Camouflage: Moving objects can be visually similar to the background scene, or some portion of it. This effect is called camouflage, leading to erroneous distinction between foreground and background. The camouflage can be at color level, texture level, or any other appearance/depth feature level.

• Night scenes: Night videos are still a challenging task. Indeed, the low contrast between foreground and background causes many false detections due to the dramatic illumination change and low signal to noise ratio (SNR).

Many background subtraction methods facing these issues have been designed over the last decade [START_REF] Bouwmans | Traditional and recent approaches in background modeling for foreground detection: An overview[END_REF][START_REF] Sobral | A comprehensive review of background subtraction algorithms evaluated with synthetic and real videos[END_REF][START_REF] Xu | Background modeling methods in video analysis: A review and comparative evaluation[END_REF], and they generally share the same scheme presented previously in the Figure 1.2. Conventional BS methods exploit the temporal (or spatio-temporal) variation of each pixel (or region) under many mathematical models, including probabilistic/statistical models, fuzzy models, neural/neuro-fuzzy models, subspace learning models, among the others [START_REF] Bouwmans | Traditional and recent approaches in background modeling for foreground detection: An overview[END_REF][START_REF] Sobral | A comprehensive review of background subtraction algorithms evaluated with synthetic and real videos[END_REF][START_REF] Xu | Background modeling methods in video analysis: A review and comparative evaluation[END_REF].

More recently, the research on decomposition into low-rank plus sparse matrices (or tensors 1 ) has been showing to be a suitable framework to deal with the background/foreground separation problem [27,[START_REF] Bouwmans | Robust PCA via Principal Component Pursuit: A review for a comparative evaluation in video surveillance[END_REF]. This framework consider that the data to be processed satisfy two important assumptions: a) the inliers (latent structure) are drawn from a single (or a union of) low-dimensional subspace(s), and b) the corruptions are sparse. This assumption holds a particular association to the problem of B/F separation, where the background model 1.2. Contributions

5

(almost static) is represented as a low-rank structure and the foreground objects are associated with the sparse residuals. Figure 1.3 illustrates the process described here. In general, the input video is converted into a matrix (or tensor) representation and then decomposed into a sum of low-rank and sparse components. The choice of the number of components is a free parameter and it varies according to the type of behavior needed to be modeled. Sometimes a third component that models the Gaussian noise is used to enhance the noise suppression, improving the foreground detection. However, the key issues and challenges in such approaches are their capabilities to handle complex and dynamic background scenarios, as well as performing in a real-time manner.

Given the importance of this subject, the thesis introduces recent advances in decomposition into low-rank plus sparse matrices and tensors, as well as the main contributions to face the principal issues in this domain. In the next sections, we present a list of the main contributions developed in the thesis and the outline of each chapter.

Contributions

In order to fit the above objectives, we have accomplished the following contributions summarized in this thesis2 :

• A new library, named LRSLibrary3 : that provides a collection of low-rank and sparse decomposition algorithms. The library was designed for background/foreground separation in videos and it contains a total of 104 4 matrix-based and tensorbased algorithms [START_REF] Sobral | LRSLibrary: Low-rank and sparse tools for background modeling and subtraction in videos[END_REF]. It has been fundamental for all the experiments conducted in the thesis.

• A novel methodology for background model initialization: that considers the background model initialization as a reconstruction problem from missing/corrupted data. Given a sequence of images, a simple joint motion-detection and frame-selection operation removes the redundant frames and induces missing entries from the moving regions. Next, the background model is recovered by matrix/tensor completion under partially observed data [START_REF] Sobral | Comparison of matrix completion algorithms for background initialization in videos[END_REF][START_REF] Sobral | Matrix and tensor completion algorithms for background model initialization: A comparative evaluation[END_REF].

• A double-constrained Robust Principal Component Analysis (RPCA) method, named SCM-RPCA: that takes the advantage of shape and confidence maps, both extracted from spatial saliency maps, to enhance object foreground detection in dynamic scenes [START_REF] Sobral | Double-constrained RPCA based on saliency maps for foreground detection in automated maritime surveillance[END_REF].

• An incremental tensor subspace learning (IMTSL) algorithm: that handles the problem of background/foreground separation in streaming multidimensional data for intelligent video surveillance applications. Differently from the traditional tensorbased methods for background/foreground separation that only use the gray-scale or

INTRODUCTION

color information, the proposed method constructs a multi-feature low-rank model for robust modeling of the scene background [START_REF] Sobral | Incremental and multi-feature tensor subspace learning applied for background modeling and subtraction[END_REF].

• An online stochastic tensor decomposition (OSTD): that is more robust and faster than IMTSL algorithm for handling streaming multispectral video sequences. The OSTD algorithm makes use of RPCA on tensors for robust background/foreground separation. The proposed method was designed to be much faster than IMTSL and to address the major difficulties of multispectral imaging for video surveillance [START_REF] Sobral | Online stochastic tensor decomposition for background subtraction in multispectral video sequences[END_REF].

• A survey of low-rank and sparse representation: that covers the main aspects of the recent approaches for low-rank and sparse representation [27].

• An evaluation of subspace clustering algorithms to the problem of human action recognition from 3D skeletal data: that explores a particular approach for low-rank and sparse representation, named subspace clustering (SC). Instead of applying SC for background modeling and foreground separation as shown previously, here we evaluate the robustness of some subspace clustering algorithms to the problem of human action recognition from 3D skeletal data. This is a work realized in conjunction with CVC at UAB [START_REF] Gong | Human pose estimation from monocular images: A comprehensive survey[END_REF][START_REF] Sobral | Robust subspace clustering of human activities from 3D skeletal data[END_REF].

Outline

The rest of the thesis is organized as follows:

• Chapter 2 provides an overview of the state-of-the-art methods for low-rank and sparse decomposition on matrices and tensors, as well as their application to the problem of background modeling and foreground segmentation. The methods were unified in a more general framework, named DLSM, that categorizes the matrix separation problem into three main approaches: implicit, explicit and stable.

• Chapter 3 presents a novel methodology for background model initialization, seen as a reconstruction problem from missing/corrupted data. This chapter is closely related to the first part of the DLSM framework introduced in Chapter 2, covering a wide range of methods for low-rank approximation on matrices and tensors.

• Chapter 4 describes a new double-constrained RPCA, named SCM-RPCA, to improve the object foreground detection in maritime scenes. This algorithm follows the third approach of the DLSM framework by adopting a stable decomposition. The algorithm makes use of double constraints extracted from spatial saliency maps to enhance object foreground detection in dynamic scenes.

• Chapters 5 and 6 present two incremental tensors-based algorithms in order to perform background/foreground separation from multidimensional streaming data. These chapters address the problem of low-rank and sparse decomposition on tensors. Chapter 5 introduces a new incremental method for higher-order decomposition on tensors, whereas Chapter 6 presents a new online stochastic algorithm that makes use of robust principal component analysis on tensors.

INTRODUCTION

Chapter 2

Recent approaches via low-rank and sparse representation

This chapter introduces the principles of low-rank and sparse decomposition for the problem of B/F separation. Here, we present a concise overview based on our recently published survey (Computer Science Review, 2016, [27]) to cover the main aspects of the recent approaches of low-rank and sparse representation. In addition, an extension to tensors was also considered.

Introduction

Learning low-rank and sparse structures from corrupted or even incomplete observations has recently attracted wide attention in intelligent video surveillance to develop robust algorithms for background modeling and foreground segmentation [27]. As stated in Chapter 1, the main objective of these algorithms is to highlight the foreground (or moving) objects for further steps, such as detection, tracking and recognition. However, in this domain the observed data (images or videos) are rarely pure and often have high dimensionality.

A large number of approaches for robust low-rank and sparse modeling have been proposed in the last few years [27,[START_REF] Davenport | An overview of low-rank matrix recovery from incomplete observations[END_REF][START_REF] Lin | A review on low-rank models in data analysis[END_REF]259]. These approaches are based on the assumption that the uncorrupted information lies in a low-dimensional subspace, whereas noise is sparse. This assumption holds a particular association to the problem of B/F separation, where the background model (almost static) is represented as a low-rank structure and the foreground objects are associated with the sparse residuals. However, the key issues and challenges in such approaches are their capabilities to handle complex and dynamic background scenarios, as well as performing in a real-time manner. Given the importance of this subject, several methods have been developed in order to perform B/F separation in a robust way [27].

In the next sections, we present an overview of the state-of-the-art algorithms for lowrank and sparse decomposition, as well as their application to background modeling and foreground segmentation tasks. First we start with recovering low-rank and sparse structures 10 LOW-RANK AND SPARSE REPRESENTATION on matrices in Section 2.2, then we present a more general case of RPCA, named subspace clustering, in Section 2.3. Finally, in Section 2.4, we show how to deal with the multidimensional case through tensor methods. The reader may refer to Appendix A for a complete description of the mathematical notations and symbols found in the current and next chapters of the thesis.

Decomposition into low-rank plus additive matrices

Let a sequence of n gray-scale images (or frames) F 1 . . . F n captured from a static camera, that is, F ∈ R i1×i2 where i 1 and i 2 denote the frame resolution (rows by columns, a.k.a image height by image width), and considering that all frames are vectorized1 into an observation matrix A = [vec(F 1 ) . . . vec(F n )], where A ∈ R m×n and m = (i 1 × i 2 ). The process of background/foreground separation can be regarded as a matrix separation problem. The background (almost static and highly correlated between frames) is assumed to lie in a lowdimensional subspace, where the sparse outliers usually represent the foreground (or moving) objects. We assume that this matrix separation problem can be unified in a more general framework formulated as follows:

A = Y y=1 K y (2.1)
where, in most of the cases, Y ∈ {1, 2, 3}, and for Y = 1 . . . 3, the matrices K 1 . . . K 3 are commonly defined as follows:

• Implicit: For Y = 1, the first matrix K 1 is a low-rank matrix (e.g. K 1 = L). The matrix L is assumed to be the best low-rank approximation of the matrix A, where A ≈ L. The low-rank assumption for A comes from the fact that the uncorrupted data appear to be highly correlated to a certain degree. This means that we try to recover only the background component (almost stationary) from a sequence of vectorized images in the matrix A. We call this decomposition as "implicit decomposition" due to the fact that we have any constraint with respect to the sparse components (or foreground objects). The sparse matrix S is recovered by performing the difference between the input matrix A and its low-rank component L (e.g. S = A -L). Some methods are included in this category, such as Low-Rank Approximation (LRA), Nonnegative Matrix Factorization (NMF), and Matrix Completion (MC).

An alternative approach is to assume that the first matrix K 1 = S is the best sparse approximation of the matrix A (also known as sparse coding), where A ≈ S. In this case, we ignore the low-rank structure and we find only the sparse components that minimize the reconstruction error. This approach is widely used for sparse dictionary learning [START_REF] Mairal | Online dictionary learning for sparse coding[END_REF] and compressed sensing [START_REF] Patel | Sparse representations, compressive sensing and dictionaries for pattern recognition[END_REF]. Some authors [START_REF] Xiao | Fast 1 -minimization algorithm for robust background subtraction[END_REF] considered the background model can be sparsely represented as a linear combination of a few atoms in the learned dictionary. However, in the context of this thesis we consider that our first matrix K 1 (implicit decomposition) is recovered from a low-rank perspective.

The main drawback of the methods based on Y = 1 is that there is only one assumption about the structure of the approximated matrix K 1 (either it is low-rank or sparse). In the case where K 1 = L, the foreground objects in the matrix S = A -L are mixed with dense or sparse noise, or anything else. Otherwise, if we consider that K 1 = S, any assumption about the structure of the background exists. For this reason, some authors proposed to "explicitly" specify a sparse component, resulting in Y = 2.

• Explicit: For Y = 2, the matrices K 1 and K 2 are usually assumed to be the low-rank and sparse representation of the data, respectively, such that K 1 = L and K 2 = S.

In this case, the input matrix A is decomposed in such way that A ≈ L + S. We call this decomposition as "explicit decomposition" due to the fact that we have two constraints: the first one enforcing a low-rank structure over the matrix L, and the second one enforcing a sparse structure over the matrix S. Usually we call the methods based on Y = 2 as robust methods, such as Robust Principal Component Analysis (RPCA), Robust Non-Negative Matrix Factorization (RNMF), Robust Dictionary Learning (RDL), among the others [27].

Methods based on Y = 2 usually work better for the problem of background/foreground separation in comparison to the methods based on Y = 1. However, in real life surveillance videos the background is never completely stationary, and there is always measurement noise or corruptions. In order to deal with this, some authors [260] proposed to "explicitly" add a new component representing the noise term, resulting in Y = 3.

• Stable: For Y = 3, the matrices K 1 , K 2 and K 3 are usually assumed to be the low-rank, sparse and noise components, respectively, resulting in K 1 = L, K 2 = S and K 3 = E, where A ≈ L + S + E. The noise can be modeled by a Gaussian, a Mixture of Gaussians (MoG) or a Laplacian distribution [START_REF] Meng | Robust matrix factorization with unknown noise[END_REF]. This decomposition is called "stable decomposition" as it separates the outliers in S and the noise in E. In the case of background/foreground separation, the noise matrix E can also represent some dynamic properties of the background, as well as it can capture the turbulence in thermal videos [START_REF] Oreifej | Simultaneous video stabilization and moving object detection in turbulence[END_REF].

Several methods based on Y = 3 were developed [START_REF] Bouwmans | Robust PCA via Principal Component Pursuit: A review for a comparative evaluation in video surveillance[END_REF] From left to right: the input matrix A, its rank-1 approximation and its rank-3 approximation.

LOW-RANK AND SPARSE REPRESENTATION

Implicit decomposition

The implicit decomposition of the DLSM framework can be seen as a low-rank matrix recovery problem, where the uncorrupted data can be recovered from a low-dimensional representation of the input matrix. The low-rank approximation is formulated as a minimization problem, in which the cost function measures the fit between the input matrix A and an approximating matrix L (the optimization variable), subject to a constraint that the approximating matrix has reduced rank. This optimization, also known as rank minimization under hard-rank constraint, is defined as follows:

minimize L f (A -L), subject to rank(L) = r, (2.2)
where f (.) denotes a loss function and r (1 ≤ r < rank(A)) represents the desired rank. The minimum error can be given by the Frobenius norm or the 2 -norm, due to their invariance to rotation. Solving (2.2) can be interpreted as finding the best rank r estimation of A in a least-squares sense, where the loss function is defined as f (A-L) = ||A-L|| 2 F . This means that (2.2) does not have a local minimum and also a closed form solution can be estimated by computing the Singular Value Decomposition (SVD) of A. Formally, the SVD of an m × n real or complex matrix A is a factorization of the form:

A = UΣV T (2.3)
where U is an m × m real or complex unitary matrix, Σ is an m × n rectangular diagonal matrix with non-negative real numbers on the diagonal, and V T is an n × n real or complex unitary matrix. The m columns of U and the n columns of V are called the left-singular vectors and right-singular vectors of A, respectively. The diagonal entries Σ are known as the singular values of A and they are ordered in decreasing order. However, instead of taking all singular values (full SVD), the low-rank approximation problem, according to Eckart and Young [START_REF] Eckart | The approximation of one matrix by another of lower rank[END_REF] theorem, considers the existence of an optimal rank r approximation, denoted by

svd r (A) = r i=1 u i σ i v T i (2.4)
where u i and v i denote the ith column of U and V, respectively, and σ i represents the diagonal entries of Σ. Figure 2.1 shows an example of an input matrix A contaminated by a Gaussian noise and its rank-1 (A 1 = svd 1 (A)) and rank-3 (A 3 = svd 3 (A)) approximation, respectively. As it can be seen, the low-rank approximation can eliminate the noise component enough. However, some partial information in the rank-1 approximation is lost compared to the rank-3 approximation. For example, there are only 3 peaks in A 1 instead of 4 peaks in A 3 , that is, A 3 is closer to the original matrix (without noise) than A 1 .

Concerning the problem of background/foreground separation, the low-rank approximation can be used for the background model initialization task. As an example, Figure 2.2 (a) shows how to estimate the background model through low-rank approximation. It can be observed that the rank-1 approximation can recover, successfully, a good representation of the background model. Figure 2.2 (b) presents the influence of the rank approximation in the background model. It can be seen that the more the rank is increased the more artifacts are included into the background model. Taking into account the first 10 singular values, the high magnitude of the first singular value explains the high correlation between video frames and why the rank-1 approximation can give a good approximation of the background model. The best rank r approximation for background modeling is not always evident to find, and it depends on the scene. The next step for estimating the foreground components is to find the sparse matrix S, which can be recovered by performing the difference between the input matrix A and its lowrank component L = svd r (A) for a given r, such that S = A -L (e.g. Figure 2.3 (c)). The foreground masks (e.g. Figure 2.3 (d)) are simply obtained by hard thresholding the sparse matrix S such that:

O = S 2 < σ 2 , σ 2 = var(s), (2.5)
where O represents the outliers, s = vec(S) denotes the vectorization of the matrix S and var(s) is the variance of the elements of the vector s. Equation (2.5) is also known as variance threshold method, that removes all low-variance entries of S. Finally the segmentation of the moving objects is obtained by coloring the elements of O (see Figure 2.3 (e)).

However, the low-rank approximation method presented previously is based on rank minimization under hard-rank constraint, and a closed form solution is obtained by SVD. Unfortunately, this approach has several limitations and drawbacks. It cannot handle affine transformations, missing entries, gross corruptions, etc. Consider the following example:

Affine transformation and missing entries: In many applications, we need to recover a minimal rank matrix subject to some problem-specific constraints, often characterized as an affine set. A typical situation is when the columns are i.i.d. samples of a random process with low-rank covariance [START_REF] Recht | Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization[END_REF], such as collaborative filtering [START_REF] Abernethy | A new approach to collaborative filtering: Operator estimation with spectral regularization[END_REF] and latent semantic indexing [START_REF]Similarity-based matrix completion algorithm for latent semantic indexing[END_REF]. This affine rank minimization problem is defined as follows:

minimize L rank(L), subject to A(L) = b, (2.6)
where A : R m×n → R p denotes a linear mapping and b ∈ R p represents a vector of observations of size p. The above minimization is equivalent to seeking the simplest model satisfying a given set of constraints. A special case of problem (2.6) is the matrix completion problem: minimize L rank(L), where P Ω (.) denotes a sampling operator restricted to the elements of Ω (set of observed entries), i.e., P Ω (A) has the same values as A for the entries in Ω and zero values for the entries outside Ω.

subject to P Ω (L) = P Ω (A), (2.7)
However, the problems (2.6) and (2.7) are NP-hard and all known finite time algorithms have at least doubly exponential running times in both theory and practice [START_REF] Candès | Exact matrix completion via convex optimization[END_REF]. Candès and Recht [START_REF] Candès | Exact matrix completion via convex optimization[END_REF] proposed to replace the rank(.) function with the nuclear norm [START_REF] Fazel | A rank minimization heuristic with application to minimum order system approximation[END_REF] (sum of singular values, see Appendix A) making the problem tractable, in such a way that the problem reduces to: minimize L ||L|| * , subject to P Ω (L) = P Ω (A).

(2.8)

Given that the singular values are always positive, the nuclear norm can be regarded as an 1 -norm of the singular values, while the rank(.) function is the cardinality or 0 -norm of the singular values. The advantages of using the nuclear norm relaxation are: a) the nuclear norm is convex2 , enabling to compute global optima efficiently, b) the nuclear norm is the tightest convex surrogate of the rank function [START_REF] Fazel | A rank minimization heuristic with application to minimum order system approximation[END_REF], and c) due to its convexity, the minimization can be achieved tractably via several popular algorithms, such as semidefinite programming (SDP) [124], projected subgradient method [START_REF] Do | A fast and efficient heuristic nuclear-norm algorithm for affine rank minimization[END_REF], or low-rank parametrization [START_REF] Recht | Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization[END_REF]. Candès and Recht [START_REF] Candès | Exact matrix completion via convex optimization[END_REF] theoretically proved that the solution of problem (2.8) can exactly recover the low-rank matrix with a high probability. However, in real applications, the input matrix can be contaminated by noise and the equality constraint in Equation (2.8) is too strict. For matrix completion with noise [START_REF] Candès | Matrix completion with noise[END_REF], a relaxed form of (2.8) it is often considered as follows:

minimize L 1 2 ||P Ω (L) -P Ω (A)|| 2 F +λ||L|| * (2.9)
where λ is a trade-off parameter between the error and the low-rank regularization induced by the nuclear norm, and the selection of λ should depend on the noise level. This is an unconstrained convex optimization problem, and can be solved in a systematic way using a proximal algorithm [START_REF] Parikh | Proximal algorithms[END_REF][START_REF] Toh | An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems[END_REF]. a uniform distribution by P Ω (.) where only 50% of its entries are revealed. As it can be seen, the low-rank matrix L was reconstructed successfully by using a Singular Value Thresholding (SVT) algorithm proposed by Cai et al. [START_REF] Cai | A singular value thresholding algorithm for matrix completion[END_REF]. In Chapter 3 we develop the formulation of Matrix Completion for the recent approaches. In addition, we investigate the background model initialization as a reconstruction problem from missing/corrupted data.

Explicit decomposition

When considering the low-rank recovery problem in the case of strong noise, it seems that this problem is well solvable by the traditional Principal Component Analysis (PCA). However, the traditional PCA is effective in accurately recovering the underlying low-rank structure only when the noise is Gaussian. If the noise is non-Gaussian and strong, even a few outliers can make PCA fail. To overcome this issue, an extended model called "Robust PCA" or RPCA was considered by Wright et al. [START_REF] Wright | Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization[END_REF], Candès et al. [START_REF] Candès | Robust Principal Component Analysis[END_REF] and Chandrasekaran et al. [START_REF] Chandrasekaran | Rank-sparsity incoherence for matrix decomposition[END_REF] when the gross errors are sparse, and we call this model as "explicit decomposition".

The explicit decomposition of the DLSM framework refers to the problem of decomposing an input data matrix A into the sum of two other matrices in such way that A = L + S, where L is a low-rank matrix and S express the corrupted entries assumed to be sparse (see Figure 2.5). This definition is also known as Robust Principal Component Analysis (RPCA), and can be formulated as follows: minimize L,S rank(L) + card(S),

subject to A = L + S, (2.10)
where card(S) = ||S|| 0 denotes the number of non-zero entries of S. Usually problem (2.10) is rewritten as: minimize L,S rank(L) + λ||S|| 0 ,

subject to A = L + S, (2.11)
where λ > 0, similar to the Equation 2.9, is a weight parameter that balances the significance between minimizing ||S|| 0 and minimizing rank(L). That is, for a larger λ the optimal solution will maximize the sparsity in S providing a less "low-rankness" in L, whereas a smaller λ will result in a minimum sparsity in S and a more low-rankness in L.

The low-rank minimization concerning L offers a suitable framework for background modeling due to the high correlation between frames. So, minimizing L and S implies that the background is approximated by a low-rank subspace that can gradually change over time, while the moving foreground objects constitute the correlated sparse outliers which are contained in S. The rank(L) influences the number of "modes" of the background that can be represented by L: if rank(L) is too high, the model will incorporate the moving objects into its representation; if the rank(L) is too low, the model tends to be uni-modal and then the multi-modality which appears in dynamic backgrounds will be not captured. The quality of the background/foreground separation is directly related to the assumption of the low-rank and sparsity of the background and foreground, respectively. However, as stated in Section 2.2.1, rank(L) = ||σ(L)|| 0 and ||S|| 0 yields a highly nonconvex optimization problem. The problem (2.10) involves both low rank matrix recovery problem and 0 -minimization problem, and both are NP-hard and hard to approximate [START_REF] Amaldi | On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems[END_REF][START_REF] Candès | Robust Principal Component Analysis[END_REF][START_REF] Wright | Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization[END_REF]. In order to address this issue, a tractable optimization problem is obtained by relaxing (2.10) with convex envelopes that are easier to minimize [START_REF] Candès | Robust Principal Component Analysis[END_REF][START_REF] Wright | Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization[END_REF]. Usually the 0 -norm is replaced with the 1 -norm and the rank(.) with the nuclear norm ||.|| * , yielding the following convex surrogate: minimize

L,S ||L|| * +λ||S|| 1 , subject to A = L + S, (2.12)
where ||L|| * +λ||S|| 1 is the convex envelope of rank(L) + λ||S|| 0 over the set of (L, S) such that max(||L|| F , ||S|| 1,∞ ) ≤ 1 (see Appendix A) [START_REF] Wright | Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization[END_REF]. Wright et al. [START_REF] Wright | Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization[END_REF] showed that, under natural probabilistic models, the low-rank matrix L and the sparse matrix S can be efficiently recovered by solving a convex program. However, the recovery depends on an appropriate choice of the regularizing parameter λ > 0. Usually, λ is widely assigned as λ = (2.13) Figure 2.6 presents an illustration of the background/foreground separation by using RPCA via PCP proposed by Candès et al. [START_REF] Candès | Robust Principal Component Analysis[END_REF]. Essentially, the nuclear-norm term corresponds to the low-frequency components while the 1 -norm describes the high-frequency components. Usually, the low-frequency components (smooth variations) represent the background model and the high-frequency components are the foreground objects. However, this separation is not a trivial task. For example, low frequency components from foreground objects can leak into extracted background images for areas that are very crowded by moving objects. The leakage as ghost artifacts which appear in extracted background cannot be well handled by adjusting the weights between the two regularization parameters. An inverse problem occurs when we seek to separate the moving objects from a very dynamic background. Figure 2.7 shows a typical issue faced by RPCA via PCP for handling very dynamic background scenes (e.g. videos recorded by maritime video surveillance systems). As can be seen, the foreground segmentation is highly contaminated by sparse outliers coming from the dynamic factors in the background model. In order to deal with this issue, some authors [10,260] proposed a stable version of PCP, discussed in the next section.

Stable decomposition

As previously shown, the PCP has some limitations, as the low-rank component needs to be exactly low-rank and the sparse component needs to be exactly sparse (e.g. consider the input matrix as the sum of a true low-rank matrix plus a true sparse matrix, see Figure 2.5).

However, in real applications the observations are often corrupted by noise.

subject to ||A -L -S|| 2 F ≤ , (2.15)
resulting in a stable recovery of L and S. SPCP offers a suitable framework for background/foreground separation in real-life applications, as the background model is frequently contaminated by noise. Reconsidering the Figure 2.7, we can see a visual comparison between PCP and SPCP. We can note a relevant improvement given by SPCP compared to PCP in the foreground segmentation mask when dealing with scenes containing a highly dynamical background. In the SPCP model, the dynamical factors from the background model are usually included in the noise matrix E, decreasing the number of wrong sparse components added in the matrix S.

Solvers

In the last few years several algorithms (also named solvers) have been proposed for solving RPCA. All these algorithms require solving the following generalized model defined as follows:

minimize

L,S λ 1 f low (L) + λ 2 f sparse (S) + λ 3 f noise (E), subject to C, (2.16)
where f low (.), f sparse (.) and f noise (.) are surrogate loss functions that are easier to minimize (usually convex functions), and C is a constraint on the matrices L, S and E. Depending on the choice of f low (.), f sparse (.) and f noise (.), different instantiations of the problem (2.16) can be produced. Usually f low (.), f sparse (.) and f noise (.) are taken to enforce the low-rank, sparsity, and noise constraints of L, S and E, respectively. Common choices for f low (.), f sparse (.) and f noise (.) are the nuclear norm, 1 -norm, and (squared) Frobenius norm, respectively. The constraint C is generally based on: a) an equality, such as ||A -L -S|| η norm = 0 or A = L + S, or b) an inequality, such as ||A -L -S|| η norm ≤ where η and are defined commonly as η ∈ {1, 2} and = 0.5. The ||.|| norm could be any norm, and the most used are the 2 -norm and the Frobenius norm.

20

LOW-RANK AND SPARSE REPRESENTATION

Optimization algorithms

A wide number of algorithms for solving RPCA both via PCP and via SPCP were proposed in the literature [27,[START_REF] Lin | A review on low-rank models in data analysis[END_REF]. Here we present an overview of the state-of-the-art algorithms, but for a more complete review, please refer to the recent surveys Bouwmans et al. [27] and Lin [START_REF] Lin | A review on low-rank models in data analysis[END_REF]. In Chapter 4 we present a special case of RPCA via SPCP in which a particular type of constraint is employed. We also propose a new variant of SPCP to deal with background/foreground separation in maritime video surveillance applications.

Given the original formulation of RPCA, where f low (L) = rank(L) = ||σ(L)|| 0 and f sparse (S) = card(S) = ||S|| 0 , this minimization problem yields a NP-hard discrete optimization problem. To overcome this difficulty, a common way is to convert it into a continuous optimization problem, and there are two principal ways to do this. The first way is by converting into a convex program. For example, f low (.) and f sparse (.) are replaced by the nuclear norm and the 1 -norm, respectively. The second way is by converting into a nonconvex program. More specifically, using a non-convex continuous function to approximate the rank(.) and the card(.) functions. For example, replacing the rank(.) by the Schatten-p pseudo norm ||.|| Sp and card(.) by α pseudo norm ||.|| α where 0 < α < 1. The principal advantage of convex programs is that a global optimal solution can be relatively easily obtained. The disadvantage is that the solution may not be strictly low-rank or sparse. In contrast, the advantage of non-convex optimization is that low-rank and/or sparse solutions can be obtained. However, their global optimal solution may not be reached. The quality of the solution may heavily depend on the initialization. So the convex and non-convex algorithms complement each other. In the next paragraphs we introduce both convex and non-convex algorithms for solving RPCA.

Convex algorithms:

The nuclear norm in the PCP/SPCP problem can be represented as a semidefinite program and solved by interior point methods [START_REF] Boyd | Convex Optimization[END_REF][START_REF] Candès | Robust Principal Component Analysis[END_REF][START_REF] Lin | A review on low-rank models in data analysis[END_REF][START_REF] Recht | Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization[END_REF]. These methods are implemented in some commercial solvers such as Mosek3 , SeDuMi4 , YALMIP 5and CVX 6 . However, interior point methods are typically limited to small size problems (e.g. n < 100), due to the O(n 6 ) complexity. In real applications such as computer vision and machine learning, we often require matrices of size n > 10 4 , making interior point methods impractical. To overcome this issue, recent approaches focus on first-order optimization methods instead. In general, first-order methods have less numerical precision than interior point methods, but large scale problems can be solved efficiently because no second-order information needs to be stored. First-order methods, such as iterative thresholding algorithms for 1 -minimization [START_REF] Cai | A singular value thresholding algorithm for matrix completion[END_REF], perform nuclear-norm minimization by repeatedly shrinking the singular values of the input matrix. This approach reduces the complexity of each iteration to the cost of a SVD. However, iterative thresholding algorithms, such as SVT, converge very slowly [START_REF] Candès | Robust Principal Component Analysis[END_REF]. Sub-gradient methods have also been used for convex minimization problems with very large number of dimensions [START_REF] Recht | Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization[END_REF]. The main advantages of sub-gradient methods are their simplicity to implement and their scalability to large-scale problems. However, as it remains on SVD, the computation of the singular values can be computationally expensive. Currently, the majority of optimization methods for large scale computing are based on first order methods [START_REF] Lin | A review on low-rank models in data analysis[END_REF]. The most popular techniques include the Accelerated Proximal Gradient (APG) [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF][START_REF] Nesterov | A method of solving a convex programming problem with convergence rate o(1/sqr(k))[END_REF], the Frank-Wolfe algorithm [START_REF] Frank | An algorithm for quadratic programming[END_REF][START_REF] Jaggi | Revisiting frank-wolfe: Projection-free sparse convex optimization[END_REF], and the Alternating Direction Method (ADM) [119,[START_REF] Lin | Linearized alternating direction method with adaptive penalty for low-rank representation[END_REF].

Non-convex algorithms: RPCA is a popular convex optimization scheme for decomposing an observation matrix into its sparse and low rank components. However, the current methods based on convex optimization are computationally expensive as they require either matrix inversion and/or full (or partial) SVD. Moreover, replacing 0 -norm by 1 -norm to achieve sparsity may be suboptimal, since the 1 -norm is a slack approximation of the 0norm leading to an over-penalized problem [START_REF] Lu | Generalized singular value thresholding[END_REF]. Recently, some authors [START_REF] Gu | Weighted nuclear norm minimization with application to image denoising[END_REF][START_REF] Jin | Provable efficient online matrix completion via non-convex stochastic gradient descent[END_REF][START_REF] Kang | Robust PCA via nonconvex rank approximation[END_REF][START_REF] Lerman | Fast, robust and non-convex subspace recovery[END_REF][START_REF] Lin | Generalized non-convex non-smooth sparse and low rank minimization using proximal average[END_REF][START_REF] Lu | Smoothed low rank and sparse matrix recovery by iteratively reweighted least squares minimization[END_REF][START_REF] Lu | Generalized singular value thresholding[END_REF][START_REF] Netrapalli | Nonconvex robust PCA[END_REF][START_REF] Sun | Robust principal component analysis via capped norms[END_REF][START_REF] Wang | Global convergence of admm in nonconvex nonsmooth optimization[END_REF]242,[START_REF] You | A non-convex admm heuristic for a low-rank matrix approximation[END_REF][START_REF] Zhang | Restricted low-rank approximation via ADMM[END_REF] developed a non-convex counter part to rank minimization and RPCA. In general, non-convex optimization problems are NP-hard, even if our goal is to compute a local minimizer [START_REF] Sun | When are nonconvex problems not scary?[END_REF]. However, some problems, such as deep neural networks (or deep learning) [START_REF] Bengio | Learning deep architectures for AI[END_REF][START_REF] Lecun | Deep learning[END_REF], dictionary learning [START_REF] Sun | Complete dictionary recovery over the sphere[END_REF] and tensor decomposition [START_REF] Ge | Escaping from saddle points -online stochastic gradient for tensor decomposition[END_REF] can be efficiently solved with heuristic algorithms such as (noisy) gradient descent and alternating directions [START_REF] Sun | When are nonconvex problems not scary?[END_REF]. Indeed, recent works demonstrate that some non-convex regularizers can outperform their convex counterparts [START_REF] Wang | Nonconvex relaxation approaches to robust matrix recovery[END_REF][START_REF] Xiang | Efficient nonconvex sparse group feature selection via continuous and discrete optimization[END_REF]. Several non-convex regularizers have been proposed, such as the p -norm [133], Capped 1 -norm [START_REF] Zhang | Analysis of multi-stage convex relaxation for sparse regularization[END_REF], Logarithm [START_REF] Gasso | Recovering sparse signals with a certain family of nonconvex penalties and DC programming[END_REF], Exponential-Type Penalty (ETP) [START_REF] Gao | A feasible nonconvex relaxation approach to feature selection[END_REF], Smoothly Clipped Absolute Deviation (SCAD) [START_REF] Fan | Variable selection via nonconcave penalized likelihood and its oracle properties[END_REF], Minimax Concave Penalty (MCP) [START_REF] Zhang | Nearly unbiased variable selection under minimax concave penalty[END_REF], Geman [START_REF] Geman | Nonlinear image recovery with half-quadratic regularization[END_REF] and Laplace [START_REF] Trzasko | Highly undersampled magnetic resonance image reconstruction via homotopic 0 -minimization[END_REF].

The major limitation of the convex approaches for rank minimization (i.e. nuclear norm minimization) is that all the singular values are simultaneously minimized. As previously shown in Equation (2.8), the nuclear norm is essentially an 1 -norm of the singular values and it has a shrinkage effect leading to a biased estimator. In order to deal with this issue, Hu et al. [START_REF] Hu | Fast and accurate matrix completion via truncated nuclear norm regularization[END_REF] developed a better approximation to the rank by Truncated Nuclear Norm (TNN), which is given by the nuclear norm subtracted by the sum of the largest few singular values. By minimizing TNN, the tailing singular values are influenced to be small, while the magnitudes of the first r singular values are unaffected. A weighted version of the TNN, named Weighted Nuclear Norm (WNN), was also proposed in Gu et al. [START_REF] Gu | Weighted nuclear norm minimization with application to image denoising[END_REF], adding larger weights to smaller singular values. In Lu et al. [START_REF] Lu | Generalized nonconvex nonsmooth low-rank minimization[END_REF], an Iteratively Reweighted Nuclear Norm (IRNN) algorithm was proposed to solve the non-convex non-smooth low-rank minimization problem. The authors developed a weighted version of the Singular Value Thresholding (SVT) algorithm, which has a closed form solution and is solved iteratively by IRNN. In Lu et al. [START_REF] Lu | Smoothed low rank and sparse matrix recovery by iteratively reweighted least squares minimization[END_REF], the authors used a non-convex continuous function to approximate the rank(.) and the card(.) functions, replacing the rank(.) by the Schatten-p pseudo norm ||.|| Sp and card(.) by α pseudo norm ||.|| α where 0 < α < 1. The authors have shown that the algorithm can be solved effectively by Iteratively Reweighted Least Squares (IRLS) [START_REF] Lu | Smoothed low rank and sparse matrix recovery by iteratively reweighted least squares minimization[END_REF]. In Lu et al. [START_REF] Lu | Generalized singular value thresholding[END_REF], the authors generalized the SVT, which is widely used in many convex lowrank minimization methods. A Generalized Singular Value Thresholding (GSVT) operator is proposed to solve the non-convex low-rank minimization problem in place of SVT.

Most recently, some authors [START_REF] Kang | Robust PCA via nonconvex rank approximation[END_REF][START_REF] Netrapalli | Nonconvex robust PCA[END_REF]242] proposed fast methods for non-convex RPCA. For example, in Netrapalli et al. [START_REF] Netrapalli | Nonconvex robust PCA[END_REF] the method has a linear convergence rate, low complexity, global convergence guarantee and a theoretical guarantee for exact recovery of the

LOW-RANK AND SPARSE REPRESENTATION

low-rank matrix. The method consists of simple alternating (non-convex) projections onto low-rank and sparse matrices. When the rank r is small, the method nearly matches the complexity of the traditional PCA. In Kang et al. [START_REF] Kang | Robust PCA via nonconvex rank approximation[END_REF], the authors proposed a new matrix norm for non-convex rank approximation, named γ-norm. The γ-norm overcomes the imbalanced penalization by different singular values in convex nuclear norm. The authors adopted the difference of convex (DC) programming [START_REF] Tao | Convex analysis approach to d.c. programming: theory, algorithms and applications[END_REF] to decompose a non-convex function as the difference of two convex functions. As the final solution might not be a globally optimal one, the experiments have shown that the algorithm produces promising results and converges more than twice faster than Netrapalli et al. [START_REF] Netrapalli | Nonconvex robust PCA[END_REF] and 54 times faster than traditional convex RPCA solved by inexact augmented Lagrange multiplier (IALM) [START_REF] Candès | Robust Principal Component Analysis[END_REF]. Finally, Yi et al. [242] proposed fast and efficient non-convex algorithms for RPCA via gradient descent. The method was also extended to solve robust PCA with partial observations (matrix completion). In short, the authors propose a projected gradient method that uses a novel sorting-based sparse estimator to produce a rough estimate of the sparse matrix based on the observed matrix. The sparsification operator keeps simultaneously a α-fraction of the entries of the residual matrix that have large magnitude. The algorithm outperforms previous nonconvex RPCA approaches and shows a linear convergence rate under proper initialization.

Relation to low-rank/sparse subspace clustering

Subspace clustering via sparse [START_REF] Elhamifar | Sparse subspace clustering[END_REF] and/or low-rank representation [START_REF] Liu | Robust recovery of subspace structures by low-rank representation[END_REF] can be regarded as a particular case of RPCA. Differently from RPCA, where inliers7 lie on a single low dimensional subspace, Low-rank/Sparse Subspace Clustering (L/S-SC) methods consider the inliers are drawn from the union of low-dimensional subspaces. These two common models can be summarized as follows:

• Sparse Subspace Clustering (SSC):

Z,E min ||Z|| 1 +λ||E|| l , s.t. X = AZ + E, diag(Z) = 0, (2.17)
• Low-Rank Representation (LRR):

Z,E min ||Z|| * +λ||E|| l , s.t. X = AZ + E, (2.18)
In the above formulations, Z ∈ R m×n , E ∈ R m×n and A ∈ R m×n as the representation matrix, the noise matrix, and the dictionary matrix (linearly spans the data space), respectively, where λ > 0 is a parameter to balance the effects of two terms. By choosing A = X (i.e., X = XZ + E), we assume that the data matrix X is self-expressive. When A = I (I = diag(1, 1, . . . , 1)), LRR degenerates to RPCA [START_REF] Candès | Robust Principal Component Analysis[END_REF], which is suitable for the case that data are drawn from a single subspace. An appropriate dictionary A enables the low-rank representation to reveal the true subspace structure of the data lying near several subspaces [START_REF] Chen | Robust subspace segmentation via low-rank representation[END_REF][START_REF] Liu | Robust recovery of subspace structures by low-rank representation[END_REF]. Usually, the minimization of ||Z|| 1 enforces the sparsity in the represen- Robustness of SSC and LRR algorithms has been reported previously in the works of Elhamifar et al. [START_REF] Elhamifar | Sparse subspace clustering[END_REF] and Liu et al. [START_REF] Liu | Robust recovery of subspace structures by low-rank representation[END_REF]. The SSC algorithm addresses the subspace clustering problem using techniques from sparse representation theory, while LRR aims to decompose the data matrix as the sum of a clean, self-expressive, low-rank dictionary plus a matrix of noise. Normally, the observed data is chosen to be the dictionary and the noise is assumed to be sparse.

Recent advances in subspace clustering

In the last few years, several authors have developed improved versions of the SSC and LRR given their successes in many computer vision applications. Several variants of SCC and LRR have been developed to deal with special cases when the data matrix can be corrupted by noise, missing entries, and outliers.

SSC variants: Wang et al. [START_REF] Wang | Nonconvex relaxation approaches to robust matrix recovery[END_REF] developed a modified version of SSC that considers the problem of subspace clustering under noise. Specifically, when random noise is added to the unlabeled input data points, which are assumed to lie in a union of low-dimensional subspaces. Patel et al. [START_REF] Patel | Latent space sparse subspace clustering[END_REF] proposed a novel algorithm called Latent Space Sparse Subspace Clustering (LS3C) for simultaneous dimensionality reduction and clustering of data lying in a union of subspaces. Specifically, the method learns the projection of data and finds the sparse coefficients in the low-dimensional latent space. Cluster labels are then assigned by applying SC to a similarity matrix built from these sparse coefficients. Soltanolkotabi et al. [START_REF] Soltanolkotabi | Robust subspace clustering[END_REF] developed a robust version of SSC to cluster noisy data. In particular, the authors used geometric functional analysis to show that the algorithm can accurately recover the underlying subspaces under minimal requirements on their orientation and on the num-ber of samples per subspace. Xu et al. [START_REF] Xu | Reweighted sparse subspace clustering[END_REF] proposed a new subspace clustering algorithm, named re-weighted sparse subspace clustering (RSSC) that consists of an iterative weighting (reweighted) l 1 minimization framework which improves the performance of the traditional l 1 minimization framework used in the original SSC. Yang et al. [START_REF] Yang | Sparse subspace clustering with missing entries[END_REF] proposed a SSC variant to deal with missing entries outperforming the natural approach (low-rank matrix completion followed by sparse subspace clustering) when the data matrix is high-rank or the percentage of missing entries is large. Li et al. [START_REF] Li | Structured sparse subspace clustering: A unified optimization framework[END_REF] proposed a unified optimization framework for learning both the affinity (affine transformation) and the segmentation (identification of multiple subspaces). The framework is based on expressing each data point as a structured sparse linear combination of all other data points, where the structure is induced by a norm that depends on the unknown segmentation.

LRR variants: Babacan et al. [START_REF] Babacan | Probabilistic low-rank subspace clustering[END_REF] considered the problem of clustering data points into low dimensional subspaces in the presence of outliers. The authors first developed an iterative expectation-maximization (EM) algorithm and then derived its global solution. While the first method is based on an alternating optimization scheme for all unknowns, the second method makes use of recent results in matrix factorization leading to fast and effective estimation. Both methods are extended to handle sparse outliers and missing values. Vidal and Favaro [START_REF] Vidal | Low rank subspace clustering (LRSC)[END_REF] proposed a framework, named Low Rank Subspace Clustering (LRSC), that considers the problem of fitting a union of subspaces to a collection of data points drawn from one or more subspaces and corrupted by noise and/or gross errors. The authors decomposed the corrupted data matrix as the sum of clean and self-expressive dictionary plus a matrix of noise and/or gross errors. The solution involves a novel polynomial thresholding operator on the singular values of the data matrix, which requires a minimal shrinkage. Chen et al. [START_REF] Chen | Robust subspace segmentation via low-rank representation[END_REF] proposed a new framework, named robust low-rank representation (Robust LRR), by considering the low-rank representation as a low-rank constrained estimation for the errors in the observed data. This framework aims to find the maximum likelihood estimation of the low-rank representation residuals and the experimental results have shown the robustness of this method to various type of noises (illumination, occlusion, etc) compared to the original LRR.

Combinations of SSC and LRR: Wang et al. [START_REF] Wang | Nonconvex relaxation approaches to robust matrix recovery[END_REF] showed that SSC and LRR are fundamentally similar in that both are convex optimizations exploiting the intuition of "Self-Expressiveness". The authors proposed a new algorithm, named Low-Rank Sparse Subspace Clustering (LRSSC), by combining SSC and LRR taking the advantages of both methods in preserving the "Self-Expressiveness Property" and "Graph Connectivity" at the same time. Patel et al. [160] proposed three novel algorithms for simultaneous dimensionality reduction and clustering of data lying in a union of subspaces. Specifically, the authors described methods that learn the projection of the data points and find the sparse and/or low-rank coefficients in the low-dimensional latent space.

Adequacy for the background/foreground separation

L/S-SC methods were widely applied to the motion segmentation (or motion clustering) problem by separating a video sequence into multiple spatio-temporal regions, as they correspond to different rigid-body motions in the scene [START_REF] Elhamifar | Sparse subspace clustering[END_REF][START_REF] Kanatani | Motion segmentation by subspace separation and model selection[END_REF][START_REF] Li | Structured sparse subspace clustering: A unified optimization framework[END_REF][START_REF] Rao | Motion segmentation via robust subspace separation in the presence of outlying, incomplete, or corrupted trajectories[END_REF][START_REF] Vidal | Multiframe motion segmentation with missing data using powerfactorization and GPCA[END_REF][START_REF] Xu | Reweighted sparse subspace clustering[END_REF][START_REF] Yang | Sparse subspace clustering with missing entries[END_REF]. Differently from background/foreground separation by RPCA where the entire video sequence is represented by a dense matrix decomposed into its low-rank and sparse components, L/S-SC methods work slightly differently. In general, they solve this problem by extracting a set of points in an image, and tracking these points through the video. Given a set of points drawn from a union of linear (or affine) subspaces, all the trajectories associated with a single rigid motion live in a low-dimensional subspace. Therefore, the motion segmentation problem reduces to clustering a collection of point trajectories according to multiple subspaces [START_REF] Elhamifar | Sparse subspace clustering[END_REF][START_REF] Vidal | Generalized principal component analysis (GPCA)[END_REF]. Usually the algorithms assume that the feature points are visible in all the frames. However, some authors [START_REF] Rao | Motion segmentation via robust subspace separation in the presence of outlying, incomplete, or corrupted trajectories[END_REF][START_REF] Vidal | Multiframe motion segmentation with missing data using powerfactorization and GPCA[END_REF] extended existing methods to the case of missing data, where some of the features are not visible in all the frames. Figure 2.9 (top) illustrates how motion trajectories are clustered into multiple subspaces using Hopkins 155 database [205]. As can be seen, the output from subspace clustering methods differs from the traditional foreground masks given by RPCA approaches. In general, clustering motion trajectories results in sparse trajectories and some additional efforts need to be done to obtain a foreground mask. Some authors [START_REF] Brox | Object segmentation by long term analysis of point trajectories[END_REF][START_REF] Ochs | Object segmentation in video: A hierarchical variational approach for turning point trajectories into dense regions[END_REF][START_REF] Ochs | Segmentation of moving objects by long term video analysis[END_REF] developed novel techniques for turning sparse point trajectories into dense regions, please see Figure 2.9 (bottom). Compared to the binary foreground masks obtained from RPCA methods, where the background is represented by a black color and the moving objects by a white color, subspace clustering approaches can provide a more complete information about the moving objects, splitting them into different class of motions. In addition, L/S-SC methods can deal with a particular limitation of the traditional B/F separation methods, that cannot perform well the case of moving cameras.

Extension to tensors

As seen in previous sections, matrix-based low-rank and sparse decomposition methods used for background subtraction work only on a single dimension and consider the image as a vector; hence, multidimensional data for efficient analysis can not be considered. In addition, the local spatial information is lost and erroneous foreground regions can be obtained. Some authors [START_REF] Hu | Incremental tensor subspace learning and its applications to foreground segmentation and tracking[END_REF]112,[START_REF] Sobral | Incremental and multi-feature tensor subspace learning applied for background modeling and subtraction[END_REF][START_REF] Sobral | Online stochastic tensor decomposition for background subtraction in multispectral video sequences[END_REF][START_REF] Tan | Low-n-rank tensor recovery based on multi-linear augmented Lagrange multiplier method[END_REF][START_REF] Tran | Video detection anomaly via low-rank and sparse decompositions[END_REF] used a tensor representation to solve this problem.

In the thesis, we address some related works that employ robust tensor subspace learning for the background/foreground separation problem. First, we present the principal tensor decomposition tools in Section 2.4.1, then we describe the recent works that employ RPCA on tensors in Section 2.4.2. Moreover, we also present in Chapters 5 and 6 two different approaches for background modeling via tensor subspace learning.

Tensor decomposition and factorization

Tensor decompositions have been widely studied and applied to many real-world problems [START_REF] Grasedyck | A literature survey of low-rank tensor approximation techniques[END_REF][START_REF] Kolda | Tensor decompositions and applications[END_REF][START_REF] Lu | A survey of multilinear subspace learning for tensor data[END_REF]. They were used to design low-rank approximation algorithms for multidimensional arrays [START_REF] Acar | Unsupervised multiway data analysis: A literature survey[END_REF][START_REF] Goldfarb | Robust low-rank tensor recovery: Models and algorithms[END_REF][START_REF] Grasedyck | A literature survey of low-rank tensor approximation techniques[END_REF][START_REF] Lathauwer | On the best rank-1 and rank-(r1 ,r2 ,. . .,rn) approximation of higher-order tensors[END_REF] taking full advantage of the multi-dimensional structures of the data.

In the next sections we introduce two widely-used models for low rank decomposition on tensors: the Tucker decomposition (Section 2.4.1.1) and the PARAFAC decomposition (Section 2.4.1.2). Other approaches were also developed [START_REF] Acar | Unsupervised multiway data analysis: A literature survey[END_REF][START_REF] Cichocki | Tensor decompositions for signal processing applications: From two-way to multiway component analysis[END_REF][START_REF] Grasedyck | A literature survey of low-rank tensor approximation techniques[END_REF] and usually they are classified as alternative models (see Figure 2.10). The reader may refer to [START_REF] Acar | Unsupervised multiway data analysis: A literature survey[END_REF][START_REF] Cichocki | Tensor decompositions for signal processing applications: From two-way to multiway component analysis[END_REF][START_REF] Grasedyck | A literature survey of low-rank tensor approximation techniques[END_REF][START_REF] Kolda | Tensor decompositions and applications[END_REF] for a deep literature review on tensor methods. We suggest the reader to refer to Appendix A for a summarized overview of mathematical notations and symbols used for tensors. The reader can also refer to Appendix C for an introduction on tensors, their properties and their operations.

Tucker decomposition

The Tucker decomposition can be considered as a form of higher-order principal component analysis. It decomposes a tensor into a small tensor, named core tensor, multiplied by a matrix along each mode [START_REF] Kolda | Tensor decompositions and applications[END_REF] (please refer to Figure 2.11 for a better illustration). For an N -order tensor X ∈ R I1×I2×...×I N , the Tucker model is formulated as:

X = G × N i=1 U i + E (2.19)
where

G × 1 U 1 × 2 U 2 . . . × N U N is the Tucker model, G ∈ R r1×r2×.
..×r N represents the core tensor, U i ∈ R Ii×ri are the factor matrices along the N modes, r 1 × r 2 × . . . × r N represents the rank of each mode, and E contains the residuals. Unlike the SVD for matrices, the core tensor G does not always result in a diagonal tensor. The columns of U n are the principal components of the n-mode fibers on X . For a third-order tensor, the core tensor of minimal size is defined by r 1 (the column rank), r 2 (the row rank), and r 3 (the tube rank). In other words, the multi-linear rank of an N -order tensor is represented by an N -tuple (r 1 , r 2 , . . . , r N ). The Tucker decomposition is also considered as a non-convex optimization problem. Several algorithms were developed to solve the Tucker model and the most popular are based on the Alternating Least Squares (ALS) framework [START_REF] Kolda | Tensor decompositions and applications[END_REF], also named as Tucker-ALS. However, the ALS method is not guaranteed to converge to a global optimal. In Goldfarb and Qin [START_REF] Goldfarb | Robust low-rank tensor recovery: Models and algorithms[END_REF], the authors solve the Tucker model under a convex optimization framework by using an alternating direction augmented Lagrangian (ADAL) method, also named as Tucker-ADAL.

Some authors [START_REF] Acar | Unsupervised multiway data analysis: A literature survey[END_REF][START_REF] Lathauwer | A multilinear singular value decomposition[END_REF][START_REF] Lathauwer | On the best rank-1 and rank-(r1 ,r2 ,. . .,rn) approximation of higher-order tensors[END_REF] considered the Tucker model as the generalization of SVD to higher-order tensors 8 . Lathauwer et al. [START_REF] Lathauwer | A multilinear singular value decomposition[END_REF][START_REF] Lathauwer | On the best rank-1 and rank-(r1 ,r2 ,. . .,rn) approximation of higher-order tensors[END_REF] presented a Tucker model (also named as Tucker3) with orthogonality constraints on the components, and this approach is frequently referred to as Higher-Order Singular Value Decomposition (HOSVD). The HOSVD is computed by flattening the tensor in each mode and calculating the singular vectors corresponding to its mode. In other words, it considers the tensor as multiple matrices and forces the un- folding matrix along each mode of the tensor to be low rank as follows:

LOW-RANK AND SPARSE REPRESENTATION

X = N n=1 U [n] Σ [n] V [n]T + E (2.20)
where

U [n] Σ [n] V [n]
T represents the SVD applied in the n-mode matricized tensor X [n] (see Appendix C). This approach is usually referred to as Multilinear SVD [START_REF] Cichocki | Tensor decompositions for signal processing applications: From two-way to multiway component analysis[END_REF][START_REF] Lathauwer | A multilinear singular value decomposition[END_REF]. A major difference between SVD and HOSVD is that SVD represents a matrix as a sum of rank-one matrices, while HOSVD does not have this property.

CANDECOMP/PARAFAC decomposition

CANDECOMP/PARAFAC(CP)-decomposition can be seen as a special case of the Tucker model, where the core tensor is superdiagonal and the number of components in the factor matrices is the same [START_REF] Kolda | Tensor decompositions and applications[END_REF]. The CP-decomposition expresses a tensor as the sum of a finite number of rank-one tensors (please refer to Figure 2.12). Given an N order tensor X , the Rcomponent CP model (also referred to as canonical decomposition) results into the following optimization problem:

X = R r=1 u r1 • u r2 • u r3 = U 1 • U 2 . . . • U R + E (2.21)
where • denotes the outer product,

U i ∈ R Ii×R , U 1 • U 2 . . . • U R represents the PARAFAC model
, and E contains the residuals. Differently from the matrix case, the rank of a tensor is a NP-hard problem [START_REF] Hillar | Most tensor problems are NP-hard[END_REF][START_REF] Kolda | Tensor decompositions and applications[END_REF]. In practice, the rank of a tensor is determined numerically by fitting several rank-R CP models. It is important to note that the best rank-R approximation of a tensor of a rank higher than R is not guaranteed [START_REF] Cichocki | Tensor decompositions for signal processing applications: From two-way to multiway component analysis[END_REF][START_REF] Silva | Tensor rank and the ill-posedness of the best lowrank approximation problem[END_REF]. In general, to compute the rank-R CP model in the presence of noise, the Frobenius norm of the difference between the data tensor and its CP approximation is minimized as follows:

minimize

L 1 2 ||X -L|| 2 F , (2.22)
where

L = U 1 • U 2 . . . • U R .
Usually the PARAFAC model is considered to be the method closest to SVD for matrices, because it decomposes an N -order tensor as the sum of rank-one tensors. In general, the algorithms for solving the PARAFAC model use the ALS framework due to its simplicity. These algorithms were also named as CP-ALS. In the CP-ALS, each component matrix is optimized at a time, keeping the other component matrices fixed [START_REF] Cichocki | Tensor decompositions for signal processing applications: From two-way to multiway component analysis[END_REF][START_REF] Kolda | Tensor decompositions and applications[END_REF]. Algorithms based on closed form solutions and gradient methods have also been proposed [START_REF] Tomasi | A comparison of algorithms for fitting the PARAFAC model[END_REF]. Other authors, e.g. Xu and Yin [START_REF] Xu | A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion[END_REF], imposed additional structure on the coefficients of the CP decomposition, such as non-negativity. In Zhou et al. [START_REF] Zhou | Accelerating online CP decompositions for higher order tensors[END_REF], the authors proposed an accelerated and online algorithm for fitting the PARAFAC model. Their method achieves the solution much faster than the traditional PARAFAC solved by ALS. Algorithms for solving the PARAFAC model with missing entries were also proposed [START_REF] Tomasi | PARAFAC and missing values[END_REF][START_REF] Yokota | Smooth PARAFAC decomposition for tensor completion[END_REF][START_REF] Zhao | Bayesian CP factorization of incomplete tensors with automatic rank determination[END_REF]. In Chapter 3, we investigate a particular problem of background model initialization. Not only matrix-based completion methods are evaluated, but also the recent approaches for tensor completion. We address the problem of background model initialization as a reconstruction problem from missing/corrupted data.

Robust Principal Component Analysis on tensors

In the last few years, some authors [START_REF] Goldfarb | Robust low-rank tensor recovery: Models and algorithms[END_REF][START_REF] Li | Optimum subspace learning and error correction for tensors[END_REF][START_REF] Lu | Tensor robust principal component analysis: Exact recovery of corrupted low-rank tensors via convex optimization[END_REF][START_REF] Sobral | Online stochastic tensor decomposition for background subtraction in multispectral video sequences[END_REF][START_REF] Tran | Video detection anomaly via low-rank and sparse decompositions[END_REF] extended the Robust PCA framework to the multilinear case. Basically, the RPCA for matrices was reformulated into its "tensorized" version. For an N -order tensor X , it can be decomposed as:

X = L + S + E, (2.23)
where L, S and E represent the low-rank, sparse and noise tensors, respectively (please see Figure 2.13). Similarly to the matrix-case, problem (2.23) can be rewritten as the following optimization problem: minimize

L,S rank(L) + card(S) subject to X = L + S. (2.24)
Due to the intractability of problem (2.24), the rank(.) and card(.) are replaced by their convex envelopes, such as nuclear norm and the element-wise 1 -norm. However, differently from matrices, the rank of a tensor is known to be NP-hard to compute. It is usually replaced by the tensor n-rank.

Definition 2.1. (Tensor n-rank). Let X ∈ R I1×I2×...×I N be an N -th order tensor. The nrank of X , denoted as rank n (X ), is defined as the number of linearly independent n-mode fibers of X by LOW-RANK AND SPARSE REPRESENTATION

rank n (X ) = rank(X [n] ) (2.25)
For matrices, rank(X) = rank(X T ). However, for a N -th order tensor this is not true. The convex envelope of a rank n (X ) = rank(X [n] ) is replaced by ||X [n] || * . Given an N -order tensor X , its nuclear norm can be generalized as follows:

||X || * = N n=1 ||X [n] || * . ( 2
||L [n] || * +λ||S|| 1 subject to X = L + S.
(2.27)

This formulation, first introduced in Li et al. [START_REF] Li | Optimum subspace learning and error correction for tensors[END_REF], was also extended to the Stable PCP problem: minimize

L,S N n=1 ||L [n] || * +λ||S|| 1 subject to ||X -L -S|| 2 F ≤ , (2.28)
resulting in a stable recovery of L and S. Li et al. [START_REF] Li | Optimum subspace learning and error correction for tensors[END_REF] proposed a multilinear extension of the PCP and SPCP problem to the tensor case. The tensor is decomposed into a low dimensional structure plus additive (sparse) component. Their method, named Rank Sparsity Tensor Decomposition (RSTD), employs the alternating direction method (ADM) for the optimization, leading to a block coordinate descent (BCD) algorithm. Some computer vision applications, such as image restoration, BS and face recognition, were also addressed [START_REF] Li | Optimum subspace learning and error correction for tensors[END_REF]. Subsequently, Tran et al. [START_REF] Tran | Video detection anomaly via low-rank and sparse decompositions[END_REF] proposed a tensor-based method for video anomaly detection, applying the Stable PCP decomposition in each tensor mode. The proposed method uses the IALM framework [START_REF] Candès | Robust Principal Component Analysis[END_REF] for each unfolded matrix of a tensor to determine which frames are anomalous in a video. Next, Tan et al. [START_REF] Tan | Low-n-rank tensor recovery based on multi-linear augmented Lagrange multiplier method[END_REF] proposed a method, named Low-n-rank Tensor Recovery Based on Multi-linear Augmented Lagrange Multiplier Method (LTR-MALM), to overcome the slowly convergence of the previous algorithm [START_REF] Li | Optimum subspace learning and error correction for tensors[END_REF]. A new minimization method based on augmented Lagrange multiplier method (ALM) is used. The authors showed in the experimental results that the LTR-MALM algorithm is at least several times faster than the RSTD algorithm, while their results are comparable in terms of accuracy. Moreover, Donald and Qin [START_REF] Goldfarb | Robust low-rank tensor recovery: Models and algorithms[END_REF] developed a rich framework with several variants of Higher-Order RPCA (HORPCA) methods for robust tensor recovery. Convergence guarantee and proofs of each method were also addressed. Recently, Zhao et al.

[253] proposed a Robust Bayesian Tensor Factorization (BRTF) scheme for incomplete tensor completion data. BRTF provides a fast multi-way data convergence but tuning of annoying parameters and batch processing are the major difficulties of this approach. Finally, Lu et al. [START_REF] Lu | Tensor robust principal component analysis: Exact recovery of corrupted low-rank tensors via convex optimization[END_REF] proposed a new approach for robust PCA on tensors. Their model is based on a new tensor Singular Value Decomposition (t-SVD) method developed by [START_REF] Kilmer | Factorization strategies for third-order tensors[END_REF][START_REF] Zhang | Novel methods for multilinear data completion and de-noising based on tensor-SVD[END_REF]. t-SVD is the best close representation of SVD for third order tensors, decomposing X = U * S * V T .

Conclusion

In summary, we presented an overview of the state-of-the-art methods for low-rank and sparse decomposition, as well as their application to the problem of background/foreground separation. The methods were unified in a more general framework, named DLSM, that categorizes the matrix separation problem into three main approaches: implicit, explicit and stable. In addition, we presented the matrix separation problem from a single low dimensional subspace to a union of low-dimensional subspaces, introducing the subspace clustering approach. We also showed its adequacy to the problem of background/foreground separation by clustering motion trajectories. Finally, we extended the matrix case to the tensor case for handling multidimensional data.

Chapter 3 Background model initialization via matrix and tensor completion

In this chapter, we investigate the problem of background model initialization as a reconstruction problem from missing/corrupted data. This problem can be formulated as a matrix or tensor completion task where the image sequence (or video) is revealed as partially observed data. This work is based on our publication (SBMI/ICIAP, 2015, [START_REF] Sobral | Comparison of matrix completion algorithms for background initialization in videos[END_REF]), and on its extended version for tensors (PRL, 2016, [START_REF] Sobral | Matrix and tensor completion algorithms for background model initialization: A comparative evaluation[END_REF]). In addition, the majority of matrix and tensor completion algorithms presented here were made publicly available in the LRS library [START_REF] Sobral | LRSLibrary: Low-rank and sparse tools for background modeling and subtraction in videos[END_REF] 1 (see Appendix D).

Introduction

As outlined in Chapter 1, background model initialization is commonly the first step of the BS process. It typically consists of creating a background model that best represents the scene background. In a simple way, this can be done by manually setting a static image that represents the background. Indeed, it is often assumed that initialization can be achieved by exploiting some clean frames at the beginning of the sequence, and the scene here is assumed to be stationary or quasi stationary. Naturally, this assumption is rarely encountered in real-life scenarios, because of continuous clutter presence. In addition, this procedure presents several limitations, because it needs a fixed camera with constant illumination, and the background needs to be static (commonly in indoor environments), and having no moving object in the first frames. In practice, several challenges appear and perturb this process, such as noise acquisition, bootstrapping, dynamic factors, etc. [25,[START_REF] Maddalena | Background model initialization for static cameras[END_REF].

The main challenge is to obtain a first background model when video frames contain foreground objects. Some authors perform the initialization of the background model by the arithmetic mean [START_REF] Lai | A fast and accurate scoreboard algorithm for estimating stationary backgrounds in an image sequence[END_REF] (or weighted mean) of the pixels between successive images. Prac- Eigen [START_REF] Oliver | A bayesian computer vision system for modeling human interactions[END_REF], RSL [START_REF] La | A framework for robust subspace learning[END_REF], RPCA [START_REF] Candès | Robust Principal Component Analysis[END_REF]

Missing Data Reconstruction

Matrix Completion [START_REF] Sobral | Comparison of matrix completion algorithms for background initialization in videos[END_REF], Tensor Completion [START_REF] Sobral | Matrix and tensor completion algorithms for background model initialization: A comparative evaluation[END_REF] Neural Networks SC-SOBS [START_REF] Maddalena | The SOBS algorithm: What are the limits[END_REF], BEWiS [START_REF] Gregorio | Background Modeling by Weightless Neural Networks[END_REF] tically, some algorithms are: (1) batch, using n training frames (consecutive or not), (2) incremental with known n or (3) progressive with unknown n, as the process generates partial backgrounds and continues until a complete background image is obtained. Furthermore, initialization algorithms depend on the number of background modes and the complexity of their background models. However, BS initialization has also been achieved by many other methodologies [START_REF] Bouwmans | Traditional and recent approaches in background modeling for foreground detection: An overview[END_REF]25,[START_REF] Maddalena | Background model initialization for static cameras[END_REF].

In 2014, Maddalena and Petrosino [START_REF] Maddalena | Background model initialization for static cameras[END_REF] initiated a first survey on background initialization models. This survey was extended in Maddalena and Petrosino [START_REF] Maddalena | Towards benchmarking scene background initialization[END_REF] by adding new methods. Moreover, the authors assembled a dataset, named SBI 2015, consisting of sequences frequently adopted for background initialization. Second, a more complete survey was developed in Bouwmans et al. [25] by adding new methods and extending the SBI 2015 dataset. The main investigations used methods based on temporal statistics [START_REF] Ramirez-Alonso | Temporal weighted learning model for background estimation with an automatic re-initialization stage and adaptive parameters update[END_REF][START_REF] Stauffer | Adaptive background mixture models for realtime tracking[END_REF][START_REF] Zivkovic | Improved adaptive gaussian mixture model for background subtraction[END_REF][START_REF] Zivkovic | Efficient adaptive density estimation per image pixel for the task of background subtraction[END_REF], subintervals of stable intensity [21,[START_REF] Laugraud | Labgen: A method based on motion detection for generating the background of a scene[END_REF][START_REF] Wang | A Novel Robust Statistical Method for Background Initialization and Visual Surveillance[END_REF], model completion [START_REF] Reddy | A low-complexity algorithm for static background estimation from cluttered image sequences in surveillance contexts[END_REF], optimal labeling [START_REF] Agarwala | Interactive digital photomontage[END_REF], subspace estimation [START_REF] Candès | Robust Principal Component Analysis[END_REF][START_REF] La | A framework for robust subspace learning[END_REF][START_REF] Oliver | A bayesian computer vision system for modeling human interactions[END_REF], and neural networks [START_REF] Gregorio | Background Modeling by Weightless Neural Networks[END_REF][START_REF] Maddalena | The SOBS algorithm: What are the limits[END_REF]. Table 3.1 summarizes the type of methods according to the taxonomies presented in [25]. Concerning the works based on subspace learning (related to this chapter), we can cite for example the computation of eigen values and eigen vectors [START_REF] Oliver | A bayesian computer vision system for modeling human interactions[END_REF], and the robust subspace learning approach proposed by De La Torre and Black [START_REF] La | A framework for robust subspace learning[END_REF]. However, the recent research on subspace estimation by sparse representation and rank minimization [START_REF] Bouwmans | Robust PCA via Principal Component Pursuit: A review for a comparative evaluation in video surveillance[END_REF] has been showing a suitable framework for background modeling. The background model is recovered by the low-rank subspace that can gradually change over time, while the moving foreground objects constitute the correlated sparse outliers.

Proposed methodology

In this chapter, we present a novel methodology for background model initialization, classified as Missing Data Reconstruction in Table 3.1. The initialization of the background model is addressed as a reconstruction problem from missing data. Indeed, this problem can be formulated as a matrix or tensor completion task, where the image sequence (or video) is revealed as partially observed data. The missing entries are induced from the moving regions through a simple joint motion-detection and frame-selection operation. The redundant frames are eliminated, and the moving regions are represented by zeros in our observation model. The second stage involves evaluating twenty-three state-of-the-art algorithms including thirteen matrix completion and ten tensor completion algorithms. These algorithms aim to recover the low-rank component (or background model) from partially observed data. All experiments were performed by using the SBI dataset proposed by Maddalena and Petrosino [START_REF] Maddalena | Towards benchmarking scene background initialization[END_REF] 2 . Figure 3.1 shows the proposed framework. In this chapter, the processes described here are conducted in a batch manner.

Joint motion detection and frame selection

The elimination of redundant frames is an important step for a fast low-rank reconstruction process, removing the irrelevant information and decreasing the high computational cost of some matrix and tensor based methods. All algorithms evaluated in this thesis (except GROUSE) are batch methods, requiring all frames to be vectorized and stored in a column vector from a big matrix (usually, frame resolution × number of frames) before optimization.

Given a sequence of images, in order to reduce the number of redundant frames, a simple joint motion-detection and frame-selection operation is applied. First, the color images are converted into their gray-scale representation. So, let a sequence of n gray-scale images (frames) F 1 . . . F n captured from a static camera, that is, F ∈ R I1×I2 where I 1 and I 2 denote the frame resolution (rows by columns). The difference between two consecutive frames (motion detection step) is calculated by:

D t = 0 if t = 1 (F t -F t-1 ) 2 otherwise , (3.1)
where t = 1, . . . , n, 0 ∈ R I1×I2 denotes a zero matrix3 and D t ∈ R I1×I2 denotes the matrix of pixel-wise L 2 -norm differences from frame t -1 to frame t. Next, the sum of all elements of D t is stored in a data vector d ∈ R n whose t-th element is given by:

d t = I1 x=1 I2 y=1 D t (x, y), (3.2)
where D t (x, y) is the matrix element located in the row x ∈ [1, . . . , I 1 ] and column y ∈ . Then, the data vector d is normalized between 0 and 1 by:

BACKGROUND MODEL INITIALIZATION

d = norm(d) = d -min(d) max(d) -min(d) , (3.3)
where min(d) and max(d) denote the minimum and the maximum value of the vector, respectively. The frame-selection step is done by calculating the derivative of d by:

d = d dt d, (3.4)
Next, the vector d is also normalized as in Equation (3.3). Finally, the index of the more relevant frames is obtained by thresholding d :

v = 1 if | d -µ | > τ 0 otherwise , (3.5)
where µ denotes the mean value of the vector d , and τ ∈ [0, 1] controls the threshold operator. In this chapter, ṅ ≤ n represent the set of all frames where v = 1, and the parameter τ was chosen empirically for each scene. Figure 3.2 illustrates the frame selection operation in HallAndMonitor scene. The normalized vector (in blue) shows the difference between two consecutive frames. The derivative vector (in red) draws how much the normalized vector changes. Then, it is thresholded and the more relevant frames are selected (in orange). For this example, with τ = 0.075, only 94 relevant frames are selected from a total of 296 frames (68, 24% of reduction). Table 3.2 shows the number of selected frames after frame selection process for the SBI dataset. As it can be seen, an average of 80% of reduction was achieved for each scene. The Toscana scene was ignored, due to its small amount of frames.

Low-rank reconstruction from missing data

In this section the low-rank reconstruction is addressed from two points of view: matrix completion (MC) and tensor completion (TC). First, we start with a matrix concept of the completion process in Section 3.2.2, and next we describe a generalized concept with tensors in Section 3.2.2, providing brief descriptions of the methods adopted for the evaluation (Section 3.3).

The matrix completion case

As explained previously in Chapter 2, MC aims to recover a low rank matrix from partial observations of its entries. In recent years, several methods for low-rank matrix recovery have been proposed. Basically, they are divided into two categories based on their approaches to modeling the low-rank prior [259]. The first approach is to minimize the rank of the input matrix subject to some constraints. The second approach is to factorize the input matrix as the product of two factor matrices; the rank of the input matrix is upper bounded by the ranks of the factor matrices.

Matrix completion by rank minimization A direct approach to recover a low-rank matrix is to find a matrix L ∈ R m×n with minimum rank that best approximates the matrix A ∈ R m×n , as reported in Section 2.2.1, Equation (2.7). Candès and Recht [START_REF] Candès | Exact matrix completion via convex optimization[END_REF] showed that this problem can be formulated as: minimize L rank(L),

subject to P Ω (L) = P Ω (A), (3.6)
where rank(L) indicates the rank of the matrix L, and P Ω denotes the sampling operator restricted to the elements of Ω (set of observed entries), i.e., P Ω (A) has the same values as A for the entries in Ω and zero values for the entries outside Ω. Candès and Recht [START_REF] Candès | Exact matrix completion via convex optimization[END_REF] proposed to replace the rank(.) function with the nuclear norm:

minimize L ||L|| * , subject to P Ω (L) = P Ω (A), (3.7)
where ||L|| * = r i=1 σ i such that σ 1 , σ 2 , ..., σ r are the singular values of L and r is the rank of L. The nuclear norm makes the problem tractable and Candès and Recht [START_REF] Candès | Exact matrix completion via convex optimization[END_REF] proved theoretically that the solution can be exactly recovered with a high probability. In addition, Cai et al. [START_REF] Cai | A singular value thresholding algorithm for matrix completion[END_REF] proposed an algorithm based on soft Singular Value Thresholding (SVT) to solve this convex relaxation problem. However, in real world applications the observed entries may be noisy. In order to make the problem (3.7) robust to noise, Candès and Plan [START_REF] Candès | Matrix completion with noise[END_REF] proposed a stable matrix completion approach relaxing the equality constraint by: minimize

L 1 2 ||P Ω (L) -P Ω (A)|| 2 F +λ||L|| * , (3.8)
where ||.|| F denotes the Frobenious norm and the parameter λ controls the rank of L. The selection of λ should depend on the noise level [START_REF] Candès | Matrix completion with noise[END_REF].

A few recent works used an online formulation for matrix completion [START_REF] Balzano | On GROUSE and incremental SVD[END_REF][START_REF] He | Incremental gradient on the Grassmannian for online foreground and background separation in subsampled video[END_REF][START_REF] Lois | Online matrix completion and online robust PCA[END_REF]]. Online algorithms are useful because they are faster and need less storage compared to most batch techniques. In He et al. [START_REF] He | Incremental gradient on the Grassmannian for online foreground and background separation in subsampled video[END_REF], the authors introduce GRASTA (Grassmannian Robust Adaptive Subspace Tracking Algorithm), an online robust subspace tracking algorithm that operates on highly subsampled data. In Balzano and Wright [START_REF] Balzano | On GROUSE and incremental SVD[END_REF], the authors present GROUSE (Grassmanian Rank-One Update Subspace Estimation), a subspace identification and tracking algorithm that builds high quality estimates from very sparsely sampled vectors. In Lois and Vaswani [START_REF] Lois | Online matrix completion and online robust PCA[END_REF], the authors introduce the ReProCS (Recursive Projected Compressive Sensing) algorithm for both online MC and online RPCA.

Matrix completion by matrix factorization Instead of minimizing rank, another approach for performing MC is through matrix factorization (MF). MF methods decompose the matrix A ∈ R m×n as the product of two factor matrices: A = WH T , where W ∈ R m×r , H ∈ R n×r , and r controls the rank of W and H. Therefore, if r is small, A has a small rank. Using matrix factorization to model a low-rank matrix is based on the fact that rank(WH T ) ≤ min(rank(W), rank(H)). The problem of recovering a low-rank matrix can be converted into estimating two factor matrices W and H. In the case of missing values, the factorization-based methods for MC aim to solve the following optimization problem:

minimize 1 2 ||P Ω (A) -P Ω (WH T )|| 2 F . (3.9)
A straightforward approach to solve the problem (3.9) is by minimizing the function over W or H alternately, fixing the other one. Each subproblem of estimating W or H turns into a least-squares problem, which admits a closed-form solution. Algorithms of this type have been well studied in many works in the recent matrix recovery literature [START_REF] Jain | Guaranteed rank minimization via singular value projection[END_REF][START_REF] Tang | Lower bounds on the mean-squared error of low-rank matrix reconstruction[END_REF]. For example, the matrix completion solver LMaFit [START_REF] Wen | Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm[END_REF] also adopted the alternating strategy to solve the following equivalent form of the problem (3.9):

minimize 1 2 ||Z -WH T || 2 F , subject to P Ω (Z) = P Ω (A), (3.10)
where Z is an auxiliary variable. Additionally, LMaFit integrates a nonlinear successive over-relaxation scheme to accelerate the convergence of alternation.

Nonnegative factors Non-negative Matrix Factorization (NMF) is a special case of the traditional MF, where the factor matrices W and H have no negative elements. The non-negativity makes the resulting matrices easier to inspect 4 , as in many applications (e.g. images, texts, etc.) the data is non-negative. However, NMF is an NP-hard problem that requires to impose additional assumptions (e.g. lowrankness, convexity, etc.) on the data points in order to reduce the original NMF to a tractable problem. In the literature, some authors [START_REF] Xu | An alternating direction algorithm for matrix completion with nonnegative factors[END_REF][START_REF] Zhou | Divide-and-conquer anchoring for near-separable nonnegative matrix factorization and completion in high dimensions[END_REF] have addressed the non-negativity and low-rank completion to take the advantages of both, obtaining superior results than those of just using one of the two properties.

Randomized decomposition

The factorization of large matrices becomes expensive and sometimes impractical for the traditional (deterministic) MF algorithms. In recent years, some authors focused on modern randomized matrix approximation techniques [START_REF] Halko | Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions[END_REF]. These algorithms use random sampling to identify a subspace that captures most of the underlying information of a matrix. Instead of computing the SVD of the whole matrix A, the randomized low-rank SVD [START_REF] Erichson | Randomized matrix decompositions using r[END_REF][START_REF] Witten | Randomized algorithms for low-rank matrix factorizations: Sharp performance bounds[END_REF] consists of computing a rank-r approximation of A, such that A ≈ QQ T A, where Q ∈ R m×r is orthonormal representing the economic QR decomposition 5 of AΩ = QR such that Ω ∈ R m×r is a random sub-Gaussian6 matrix. Then, the algorithm efficiently computes the SVD of a relatively small matrix B = Q T A. Zhou and Tao [START_REF] Zhou | Bilateral random projections[END_REF] proposed a fast alternative way, named Bilateral Random Projections (BRP), that avoids the SVD for large matrices. The effectiveness and the efficiency of BRP was verified in the GoDec [START_REF] Zhou | Godec: Randomized low-rank & sparse matrix decomposition in noisy case[END_REF], SSGoDec [START_REF] Zhou | Godec: Randomized low-rank & sparse matrix decomposition in noisy case[END_REF] and GreGoDec [START_REF] Zhou | Greedy bilateral sketch, completion & smoothing[END_REF] algorithms for low-rank matrix approximation and completion. Given r bilateral random projections of a m × n dense matrix A, the low-rank approximation L can be rapidly built by

L = Y 1 (X T 2 Y 1 ) -1 Y T 2 , where Y 1 = AX 1 , Y 2 = A T X 2 ,
and X 1 ∈ R n×r and X 2 ∈ R m×r are random matrices.

Riemannian optimization Another widely-used regularization strategy in low-rank matrix factorization is to constrain the search space and optimize over manifolds. Keshavan et al. [START_REF] Keshavan | Matrix completion from noisy entries[END_REF] proposed to solve the following matrix completion problem:

minimize 1 2 ||P Ω (A) -P Ω (WΣH T )|| 2 F , subject to W ∈ Gr(r, m), H ∈ Gr(r, n), Σ ∈ R r×r , (3.11)
where Gr(r, p) denotes the set of r-dimensional subspaces in R p , which forms a Riemannian manifold, named Grassmannian. Keshavan et al. [START_REF] Keshavan | Matrix completion from noisy entries[END_REF] proposed an algorithm named OptSpace to iteratively estimate the factor matrices, where W and H are updated by gradient descent over the Grassmannian, while Σ is updated by least squares.

Instead of exploring the geometries of search spaces of factor matrices, Vandereycken [START_REF] Vandereycken | Low-rank matrix completion by Riemannian optimization[END_REF] proposed to directly optimize a function over the set of fixed-rank matrices:

minimize L 1 2 ||P Ω (A) -P Ω (L)|| 2 F , subject to A ∈ M r , (3.12)
where M r denotes the set of rank-r matrices in ∈ R m×n , which forms a smooth manifold. Vandereycken [START_REF] Vandereycken | Low-rank matrix completion by Riemannian optimization[END_REF] developed a conjugate gradient descent algorithm named LRGeomCG

42

BACKGROUND MODEL INITIALIZATION

Background modeling through matrix completion

Considering the background model initialization as a matrix completion problem, once the frame-selection process is done, the moving regions of the ṅ frames, selected in the previous step (see Section 3.2.1), are determined by:

M k = thresh(D k ) = 1 if 0.5(D k ) 2 > β 0 otherwise , (3.13)
where k ∈ {1, . . . , ṅ}, thresh(.) denotes a thresholding function, D k is computed as in Equation (3.1) using only the ṅ selected frames and β is a thresholding parameter (in this chapter, β = 1e -3 for all experiments). Next, the moving regions of each selected frame are filled with zeros by F k • M k , where M k denotes the complement of M k , and • denotes the element-wise multiplication of two matrices. For color images, each channel is processed individually, then they are vectorized into a partially observed real-valued matrix A = [vec(F 1 ) . . . vec(F ṅ)], where A ∈ R m×n , m = (I 1 × I 2 ), and n = ṅ. Figure 3.3 (top) illustrates our matrix completion process. It can be seen that the partially observed matrix can be recovered successfully even with the presence of many missing entries. So, let L be the recovered matrix from the matrix completion process, the background model is estimated by calculating the average value of each row, resulting in a vector l ∈ R m , and then reshaped into a matrix B ∈ R I1×I2 .

The tensor completion case

Differently from previous matrix-based methods that consider the image as a vector, so that the local spatial information is almost lost, some authors use a tensor representation to solve this low-rank reconstruction problem. Tensor decompositions have been widely studied and applied to many real-world problems [START_REF] Grasedyck | A literature survey of low-rank tensor approximation techniques[END_REF][START_REF] Kolda | Tensor decompositions and applications[END_REF][START_REF] Lu | A survey of multilinear subspace learning for tensor data[END_REF]. As outlined in Chapter 2, Section 2.4, CP decomposition and Tucker decomposition are two widely-used low rank decompositions of tensors. Today, the Tucker model is better known as the Higher-Order SVD (HOSVD) from the work of Lathauwer et al. [START_REF] Lathauwer | On the best rank-1 and rank-(r1 ,r2 ,. . .,rn) approximation of higher-order tensors[END_REF]. The HOSVD of a tensor X can be seen as the generalization of the matrix SVD, which involves the matrix SVDs of its unfolding matrices.

In general, the low-rank completion for tensors is formulated as the following optimization problem: minimize L rank(L),

subject to P Ω (L) = P Ω (X ), (3.14)
where L ∈ R I1×I2×...×I N is a tensor with minimum rank that best approximates the tensor X . However, similarly to the matrix case, the optimization problem (3.14) is a non-convex optimization problem. This is commonly solved through trace norm optimization by: minimize

L ||L|| * , subject to P Ω (L) = P Ω (X ). (3.15)
For a general tensor case, the definition of the trace norm is represented by a combination of the trace norms of all matrices unfolded along each mode as:

||X || * = N i=1 α i ||X [i] || * , (3.16)

BACKGROUND MODEL INITIALIZATION

where α i 's are constants satisfying α i ≥ 0 and N i=1 α i = 1. However, unlike in the matrix case, computing the rank of a general tensor (N > 2) is an NP hard problem [START_REF] Hillar | Most tensor problems are NP-hard[END_REF]. In tensor literature [START_REF] Grasedyck | A literature survey of low-rank tensor approximation techniques[END_REF], three non-convex ways to deal with tensor completion problem can be found:

Tucker A natural approach is to analyze the tensor completion problem through Tucker model, introduced in Chapter 2 (see Section 2.4.1.1), in such a way that:

minimize L 1 2
||X -L|| 2 F , subject to P Ω (L) = P Ω (X ).

(3.17

)
where

L = G × 1 U 1 × 2 U 2 . . . × N U N is the Tucker model, G ∈ R r1×r2×.
..×r N represents the core tensor, U i ∈ R Ii×ri are the factor matrices along the N modes and r 1 × r 2 × . . . × r N represents the rank of each mode. This can be solved by block coordinate descent method by iteratively optimizing two blocks X and G, U 1 , . . . , U N . Similar to the matrix case, approaches based on Riemannian optimization were also used for tensor completion problems. In Kasai and Mishra [START_REF] Kasai | Low-rank tensor completion: a Riemannian manifold preconditioning approach[END_REF], the authors developed a novel Riemannian metric and explore the symmetry structure in Tucker decomposition. ||X -L|| 2 F , subject to P Ω (L) = P Ω (X ). (3.18) where L = U 1 •U 2 . . .•U N , • denotes the outer product, U i ∈ R Ii×r , and U 1 •U 2 . . .•U N represents the PARAFAC model and r represents the rank of the model. An alternative to the canonical tensor decomposition is the Tensor-Train (TT) format introduced by Oseledets [START_REF] Oseledets | Tensor-Train decomposition[END_REF]. Recent work employing TT in the context of tensor completion was released by Grasedyck et al. [START_REF] Grasedyck | Variants of alternating least squares tensor completion in the Tensor-Train format[END_REF]. TT format offers a number of advantages over the canonical decomposition, and it is therefore attractive to consider its application to function approximation.

CANDECOMP/PARAFAC

Tucker3 or Higher-Order SVD A third alternative is to consider the tensor as multiple matrices and force the unfolding matrix along each mode of the tensor to be low rank, (see Tucker model in Chapter 2, Section 2.4.1.1), as follows:

minimize L 1 2 N i=1 α i ||X [i] -L [i] || 2 F ,
subject to P Ω (L) = P Ω (X ). where α i 's are constants satisfying α i ≥ 0 and

N i=1 α i = 1.
This approach is also known as matrix SVD adapted for tensors. Recently Kilmer and Martin [START_REF] Kilmer | Factorization strategies for third-order tensors[END_REF] and Zhang et al. [START_REF] Zhang | Novel methods for multilinear data completion and de-noising based on tensor-SVD[END_REF] proposed a real representation of SVD for third order tensors called t-SVD (Tensor Singular Value Decomposition). For a tensor X ∈ R I1×I2×I3 , its SVD is formulated by X = U * S * V T , where U ∈ R I1×I1×I3 and V ∈ R I2×I2×I3 are orthogonal tensors, and S ∈ R I1×I2×I3 is a rectangular f -diagonal tensor (see Appendix C, Section C.4.3) and * denotes the t-product (see Appendix C, Section C. [START_REF] Agarwala | Interactive digital photomontage[END_REF]

.3).

A few recent works used non-convex functions instead of the nuclear norm as the surrogates of rank for rank minimization. Tomioka and Suzuki [START_REF] Tomioka | Convex tensor decomposition via structured schatten norm regularization[END_REF] proposed a structured version of Schatten norms for tensors. The authors consider the following more general overlapped Sp/qnorm defined by: ||X || Sp/q = ( N n=1 ||X [n] || q Sp ) 1/q , where ||X|| Sp = ( r i=1 σ p i ) 1/p is the Schatten p-norm for matrices. When p -→ 0 the minimization is intractable, and when p = 1 turns out to be the nuclear norm. For non-convex cases: 0 < p < 1 [259].

Experimental results

In order to evaluate the proposed approach, twenty-three state-of-the-art low-rank reconstruction algorithms were selected. These algorithms include thirteen MC and ten TC algorithms, and they are listed in Table 3.3 and in Table 3.4, respectively. The algorithms were grouped into two categories, as well as their main techniques, following the same definition of Zhou et al. [259]. The parameters of each method were tuned for each sequence, so that the estimated background model is the best as possible.

Data set

In this chapter, the SBI dataset7 [START_REF] Maddalena | Towards benchmarking scene background initialization[END_REF] was chosen for the background initialization task. This dataset contains 14 image sequences and their corresponding ground truth backgrounds. It provides also MATLAB scripts for evaluating background initialization results in terms of six metrics8 : 1) Average Gray-level Error (AGE), 2) Percentage of Error Pixels (pEPs), 3) Percentage of Clustered Error Pixels (pCEPs), 4) Peak-Signal-to-Noise-Ratio (PSNR), 5) Multi-Scale Structural Similarity Index (MS-SSIM), and 6) Color image Quality Measure (CQM).

Methodology The algorithms are ranked as follows: 1) for each algorithm we calculate its rank position for each metric (Metric Rank); Next, 2) we sum the value of the rank position for each algorithm over the six metrics, and finally, 3) we calculate the rank position over the sum, and we call it as Scene Rank. For the Global Rank, first we sum the Scene Rank for each algorithm, then we calculate its rank position over the sum. MATLAB codes are publicly available at https://github.com/andrewssobral/mctc4bmi

Quantitative analysis Tables 3.5 and 3.6 show the rank of MC and TC algorithms, respectively, over the SBI dataset. Analyzing the scene rank of MC algorithms, LRGeomCG was the top-1 in 9 over 14 scenes, becoming the first algorithm in the Global Rank of its category. For TC algorithms, TMac was the top-1 in 11 over 14 scenes, becoming the first

BACKGROUND MODEL INITIALIZATION

algorithm in the Global Rank of its category. In order to compare the best MC and the best TC algorithms, Table 3.7 presents the top-5 matrix and top-5 tensor completion algorithms, respectively, over the SBI dataset. As it can be seen, the first four best ranked algorithms (headed by LRGeomCG) are based on the MC approach. This is an interesting factor because usually tensor-based methods are seen to be more robust for multidimensional data completion in comparison to matrix-based methods. However, given that SBI dataset scenes are based on RGB color images, this may not mean that they are multidimensional enough for the power of TC methods. In order to provide more detailed results, Tables 3.8, 3.9, 3.10 and 3.11 present the quantitative results of the top-10 best algorithms over all scenes from the SBI dataset. The results are ordered by the Scene Rank, and the Global Rank shows the best ranked algorithms for all scenes. Finally, Table 3.12 summarizes the top-1 best algorithms for each individual scene. The performance of tensor-based approaches has been highlighted only on two scenes: Candela˙m1.10 by SPC and HallAndMonitor by t-TNN.

Qualitative analysis Figures 3.4 and 3.5 compare the background estimated by the top-10 best ranked low-rank reconstruction algorithms. As it can be seen, almost all methods present similar visual results, except in some particular cases where the IALM method presents some color divergence artifacts. These color artifacts are expected because the matrix completion process is done for each color channel separately. The CQM can penalize such color artifacts, however it is averaged with other five metrics, decreasing its importance. Finally, we verified that for some scenes, in particular for Board, CAVIAR1, and CaVignal (columns 1, 3 and 5 of Figure 3.4) all low-rank reconstruction algorithms failed to remove some artifacts, showing some areas with shadings with different tones.

BACKGROUND MODEL INITIALIZATION

BACKGROUND MODEL INITIALIZATION

Global rank over all scenes Method

Global rank

M

Conclusion

In this chapter, we have formulated the background initialization problem as a matrix or tensor completion task, and evaluated twenty-three recent low-rank recovery algorithms. The key idea is to first eliminate the redundant frames in a video, and consider their moving regions as non-observed values. This approach results in a data completion problem, which can be represented by a matrix or a tensor with missing entries. We show that the background model can be recovered even with partially observed data. The experimental results on the SBI dataset show the comparative evaluation of recent methods for matrix and tensor completion, and highlight the good performance of LRGeomCG method over its direct competitors. Finally, we note that matrix-based completion methods show an attractive potential for background modeling initialization in video surveillance. Moreover, in Bouwmans et al. [25], the proposed approach was classified in a new category of background initialization methods, named Missing Data Reconstruction methods. Future research may concern to evaluate incremental and real-time approaches of low-rank reconstruction algorithms for the background model initialization of streaming videos.

Introduction

As outlined in Chapter 2, the recent advances in low-rank and sparse decomposition offer a suitable framework for background modeling due to the high correlation between frames. However, the Robust Principal Component Analysis (RPCA) solved via Principal Component Pursuit (PCP) is limited to the low-rank component being exactly low-rank and the sparse component being exactly sparse (see Section 2.2.2). However, the observations in real applications are often corrupted by noise that affects every entry of the data matrix. Therefore, Zhou et al. [260] proposed a stable PCP (SPCP) that guarantees stable and accurate recovery in the presence of entry-wise noise (see Section 2.2.3). SPCP assumes that the observation matrix A is represented as A = L + S + E (also named as three-term decomposition), where L is a low-rank matrix, S is constrained to be a sparse matrix, and E is a noise term. To recover L, S and E, Zhou et al. [260] proposed to solve the following optimization problem, as a relaxed version of PCP: minimize

L,S,E ||L|| * +λ 1 ||S|| 1 +λ 2 ||E|| 2 F , s.t. A = L + S + E,
where λ 1 > 0 and λ 2 > 0 are arbitrary weighting parameters. This decomposition is called "stable" decomposition as it separates the outliers in S and the noise in E. Maritime surveillance represents a challenging scenario due to the different background dynamics of the observed scenes, such as moving water, waves, etc [START_REF] Bloisi | Background modeling in the maritime domain[END_REF]. Indeed, the motion of the objects of interest (i.e. ships or boats) can be mixed with the dynamic behavior of the background (non-regular patterns). Many algorithms have been designed to perform foreground detection, see surveys [START_REF] Bouwmans | Traditional and recent approaches in background modeling for foreground detection: An overview[END_REF][START_REF] Bouwmans | Robust PCA via Principal Component Pursuit: A review for a comparative evaluation in video surveillance[END_REF][START_REF] Sobral | A comprehensive review of background subtraction algorithms evaluated with synthetic and real videos[END_REF], but only a few of them have been designed for maritime scenes. Some related work can be found in Bloisi et al. [START_REF] Bloisi | Background modeling in the maritime domain[END_REF]. The authors propose a multimodal approach for BS to deal with the water background. In addition, Liu et al. [START_REF] Liu | Iterative infrared ship target segmentation based on multiple features[END_REF] propose an iterative approach for ship target segmentation in infrared images based on multiple features. However, the recent research on subspace estimation by sparse representation and rank minimization shows an interesting framework to separate moving objects from the background in videos. The background sequence is modeled by the low-rank subspace that can gradually change over time, while the moving foreground objects constitute the correlated sparse outliers.

In scenes where the background is very dynamic (i.e. sea waves in maritime surveillance [START_REF] Bloisi | Background modeling in the maritime domain[END_REF]), the motion of the objects of interest (i.e. boats) will be mixed with the dynamic behavior of the background (i.e. waves). SPCP-based methods try to deal with this problem under the term where the multi-modality of the background (i.e. waves) is considered as noise component (E), while the moving objects (i.e. boats) are considered as sparse component (S). The low-rank component (L) represents the static part of the background.

In this chapter, a double-constrained RPCA, named SCM-RPCA (Shape and Confidence Map-based RPCA), is proposed to improve foreground detection in dynamic scenes. The sparse component is constrained by shape and confidence maps, both extracted from spatial saliency maps. One advantage of the SCM-RPCA in relation to its direct competitors, is the possibility of combining two types of source, which may come from: spatial, temporal, and spatio-temporal information; however, here we focus only on spatial saliency maps. Our motivation is to study how it improves RPCA in the task of foreground detection in maritime scenes. Fig. 4.1 highlights our proposed approach. Given an input image (a), a saliency detector is applied (b). Next, the confidence map (c) is built by normalizing the saliency map, while the shape constraint (d) is built by thresholding the saliency map, and (e) the foreground mask is obtained by thresholding the RPCA sparse component.

Related work

Related work

In the literature, there are several modifications which concern the original SPCP. Some authors [START_REF] Oreifej | Simultaneous video stabilization and moving object detection in turbulence[END_REF][START_REF] Yang | Background extraction from video sequences via motion-assisted matrix completion[END_REF][START_REF] Ye | Foreground-background separation from video clips via motion-assisted matrix restoration[END_REF] added constraint in the sparse term in order to improve the foreground detection. First, Oreifej et al. [START_REF] Oreifej | Simultaneous video stabilization and moving object detection in turbulence[END_REF] used a turbulence model to enforce an additional constraint on the rank minimization. The authors quantify the scene's motion in terms of the motion of the particles, which are driven by dense optical flow. The obtained confidence map (a real-valued matrix) provides a rough prior knowledge of the moving objects' locations, which can be incorporated into the matrix optimization problem. Subsequently, Yang et al. [START_REF] Yang | Background extraction from video sequences via motion-assisted matrix completion[END_REF] proposed a motion-assisted matrix restoration (MAMR) model for foreground-background separation. Thus, a dense motion field is estimated for each frame by dense optical flow, and mapped into a weighting matrix, which indicates the likelihood of each pixel belonging to the background. By incorporating this information, areas dominated by slowly-moving objects are suppressed, while the background that appears at only a few frames has more chances to be recovered in the foreground detection results. In addition, Ye et al. [START_REF] Ye | Foreground-background separation from video clips via motion-assisted matrix restoration[END_REF] extended MAMR (RMAMR) (also adopted in Chapter 3), which is robust to noise for practical applications.

Proposed method

In this chapter, we propose to combine some ideas proposed by Oreifej et al. [START_REF] Oreifej | Simultaneous video stabilization and moving object detection in turbulence[END_REF] and Ye et al. [START_REF] Ye | Foreground-background separation from video clips via motion-assisted matrix restoration[END_REF]. The weighting matrix proposed by Ye et al. [START_REF] Ye | Foreground-background separation from video clips via motion-assisted matrix restoration[END_REF] can be used as a shape constraint (or region constraint), while the confidence map proposed by Oreifej et al. [START_REF] Oreifej | Simultaneous video stabilization and moving object detection in turbulence[END_REF] reinforces the pixels belonging to the moving objects. A modified version of the original 3WD method proposed by Oreifej et al. [START_REF] Oreifej | Simultaneous video stabilization and moving object detection in turbulence[END_REF] was implemented adding the shape constraint as done in RMAMR. Part of the reason we chose to modify the 3WD instead of RMAMR is it robustness to deal with the multimodality of the background. The second contribution of this chapter refers to the way of building the shape constraint and confidence map. Instead of using dense optical flow (temporal descriptor) as a preliminary step, we suggest using a saliency detector (spatial descriptor). In some cases where a) the object of interest moves very slowly (i.e long distance boats) or b) the background is very dynamic (i.e boats in the sea), the optical flow may not be enough to ensure the object detection. In addition, computing the dense optical flow requests high computational cost, while computing the saliency map is commonly much faster. Several saliency detection methods have been proposed in the literature [START_REF] Borji | Salient object detection: A survey[END_REF]. In this chapter, the BMS2 method proposed by Zhang and Sclaroff [START_REF] Zhang | Saliency detection: a boolean map approach[END_REF][START_REF] Zhang | Exploiting surroundedness for saliency detection: a boolean map approach[END_REF] was selected, due to its speed performance and accuracy results.

||L|| * +λ 1 ||S|| 1 +λ 2 ||E|| 2 F subject to W • A = W • (L + S + E) SCM-RPCA (proposed) minimize L,S,E ||L|| * +λ 1 ||Π(S)|| 1 +λ 2 ||E|| 2 F subject to A = L + W • S + E Table 4.1:
Comparison of the proposed method and related works.

where Π ∈ R m×n and W ∈ [0, 1] m×n are the confidence map and shape constraint (binary map), respectively, and "•" denotes element-wise multiplication of two matrices. As explained previously, the confidence map Π reinforces the pixels belonging to the moving objects and the shape constraint W defines the region of interest. Table 4.1 compares the proposed method with those by Oreifej et al. [START_REF] Oreifej | Simultaneous video stabilization and moving object detection in turbulence[END_REF] and Ye et al. [START_REF] Ye | Foreground-background separation from video clips via motion-assisted matrix restoration[END_REF]. These minimization problems are convex and can be solved by the Alternating Direction Method (ADM) under the Augmented Lagrangian Multiplier (ALM) framework [START_REF] Lin | The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices[END_REF].

Double-constrained robust PCA

To solve the problem in Equation (4.1), the ALM [START_REF] Lin | The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices[END_REF] is used. The ALM framework converts the constrained optimization problem in (4.1) to the minimization of the augmented Lagrange function:

Γ(L, S, E, Y) = ||L|| * +λ 1 ||Π(S)|| 1 +λ 2 ||E|| 2 F + < Y, A -L -W • S -E) > + β 2 ||(A -L -W • S -E)|| 2 F (4.2)
where Y ∈ R m×n is a Lagrange multiplier matrix, β > 0 is the penalty parameter for the violation of the linear constraint, and <, > denotes the matrix inner product. Next, the ADM is used to update L, S, E and Y alternatively for each iteration t:

L t+1 = arg min L Γ(L, S t , E t , Y t ), S t+1 = arg min S Γ(L t+1 , S, E t , Y t ), E t+1 = arg min E Γ(L t+1 , S t+1 , E, Y t ), Z = (A t+1 -L t+1 -S t+1 -E t+1 ), Y t+1 = Y t + β t Z (4.3)
Algorithm 1 Algorithm for solving SCM-RPCA.

Input: A ∈ R m×n (observation), Π ∈ R m×n (confidence map), W ∈ [0, 1] m×n (shape constraint), t max max # of iterations, and error tolerance.

t = 0 while (||Z|| F /||A|| F ) > or t < t max do Υ = β -1 t Y t URV T = svd(A -L t -E t + Υ) L t+1 = Us (1/βt) (R)V T S t+1 = W • s (λ/βtΠ) (A -L t+1 -E t + Υ) κ = (1 + 2λ 2 βt ) -1 E t+1 = κ(A -L t+1 -S t+1 + Υ) Z = A t+1 -L t+1 -S t+1 -E t+1 Y t+1 = Y t + β t Z β t+1 = ρβ t t = t + 1 end while return L ∈ R m×n (background), S ∈ R m×n (foreground), and E ∈ R m×n (noise).
where Z ∈ R m×n is the residual. Then, a closed form solution for each of the minimization problems can be defined by:

Υ = β -1 t Y t , URV T = svd(A -L t -E t + Υ), L t+1 = Us (1/βt) (R)V T , S t+1 = W • s (λ/βtΠ) (A -L t+1 -E t + Υ), κ = (1 + 2λ 2 β t ) -1 , E t+1 = κ(A -L t+1 -S t+1 + Υ) (4.4)
where svd(.) denotes a full singular value decomposition, and s (.) (.) is the soft thresholding operator defined by: s

(α) (X) = sign(X)max(abs(X) -α, 0) (4.5)
and it is applied to a matrix X in an element-wise manner. The main steps of the proposed algorithm are shown in Algorithm 1. Usually the convergence is done when

(||Z|| F /||A|| F ) ≤ , (4.6)
where is the error tolerance, or when the # of iterations is reached (t = t max ). The parameters λ and λ 2 are scalars and define the weighting parameter for the sparse and noise component, respectively, and ρ is a constant scalar and growth factor for the β parameter.

DOUBLE-CONSTRAINED RPCA

Oreifej et al. [START_REF] Oreifej | Simultaneous video stabilization and moving object detection in turbulence[END_REF] shows when β t is a monotonically increasing positive sequence, the iterations converge to the optimal solution of problem 4.1. Here, λ, λ 2 , ρ, and β 0 were defined empirically as 2, 1/||A|| 2 , 1.25, and 5/ √ m, respectively.

Definition of shape and confidence map

In this chapter, both the confidence map Π and the shape constraint W are constructed from spatial information given by saliency maps instead of optical flow, as proposed originally by Oreifej et al. [START_REF] Oreifej | Simultaneous video stabilization and moving object detection in turbulence[END_REF] and Ye et al. [START_REF] Ye | Foreground-background separation from video clips via motion-assisted matrix restoration[END_REF]. Consider a sequence of n saliency maps denoted by M 1 , . . . , M n where M ∈ R I1×I2 , so:

(4.7a) Π = [vec(norm(M 1 )) . . . vec(norm(M n ))] (4.7b) W = [vec(thresh(M 1 )) . . . vec(thresh(M n ))]
where norm(.) denotes the min-max normalization, scaling all entries of M between 0 and 1, as defined in Chapter 3, Equation 3.3. Subsequently, thresh(.) denotes the thresholding function defined as:

(4.8) thresh(M) = 1 if (0.5M) 2 < µ 0 otherwise
where µ = 0.5η(std(vec(M))) 2 , and std(.) denotes the standard deviation of a data vector.

Here, η was chosen experimentally and defined as 10.

Experimental results

In order to evaluate the performance of the proposed method for background subtraction, four videos extracted from the UCSD Background Subtraction Dataset3 proposed by Mahadevan and Vasconcelos [START_REF] Mahadevan | Spatiotemporal saliency in dynamic scenes[END_REF] and three videos from MarDT dataset 4 proposed by Bloisi et al. [START_REF] Bloisi | Mar -maritime activity recognition dataset[END_REF] were selected. The UCSD and MarDT datasets consist of 18 and 28 video sequences, respectively, both acquired from stationary and moving cameras; here, we have selected only the four sequences from UCSD and three sequences from MarDT, all sequences coming from stationary cameras.

We have compared the SCM-RPCA with its direct competitors: the original PCP proposed by Candès et al. [START_REF] Candès | Robust Principal Component Analysis[END_REF], the stable PCP proposed by Aravkin et al. [10], the 3WD proposed by Oreifej et al. [START_REF] Oreifej | Simultaneous video stabilization and moving object detection in turbulence[END_REF], and the RMAMR proposed by Ye et al. [START_REF] Ye | Foreground-background separation from video clips via motion-assisted matrix restoration[END_REF]. Note that the PCP and stable PCP are not constrained, while 3WD and RMAMR are single-constrained RPCA. It is important to note that for all constrained RPCA methods here evaluated have Table 4.2: Precision, Recall and F-Measure metrics.

Metrics Description

Precision (P r) T P/(T P + F P ) Recall (Re)

T P/(T P + F N ) F-Measure (F 1 ) 2 × (P r × Re)/(P r + Re)

T P = # of foreground pixels classified as foreground. F P = # of background pixels classified as foreground. T N = # of background pixels classified as background. F N = # of foreground pixels classified as background.

used saliency maps as input constraint. In the next sections, we report the qualitative and quantitative evaluation, as well as the computational cost evaluation of the selected algorithms. MarDT datasets, respectively. The true positive pixels (T P ) are in white, true negative pixels (T N ) in black, false positive pixels (F P ) in red and false negative pixels (F N ) in green. Is important to note that in the UCSD scenes we have used the original spatial saliency map provided by BMS, while for the MarDT scenes we have subtracted its temporal median due to the high saliency from the buildings around the river. The quantitative results in Table 4.3 show that the SCM-RPCA outperforms the previous methods, with the highest average Fmeasure over the selected video sequences. Each metric is described in Table 4.2. As can be seen from Figures 4.2 and 4.3, and Table 4.3, the combination with confidence map and shape constraint can reduce the amount of false positive pixels.

Qualitative and quantitative evaluation

Computational cost

In Table 4.4, we report the computational cost evaluation over four videos of UCSD Background Subtraction Dataset [START_REF] Mahadevan | Spatiotemporal saliency in dynamic scenes[END_REF]. The algorithms are implemented in MATLAB (R2014a) running on a laptop computer with Windows 7 Professional 64 bits, 2.7 GHz Core i7-3740QM processor and 32Gb of RAM. Note that in Table 4.4 the number of iterations (Iter) of the proposed method is slightly less than the 3WD and RMAMR, except for the Ocean scene. However, the computation time is slightly increased, except for the Boats scene. We noticed that the combination of shape constraint and confidence map did not changed significantly the number of iterations and computation time over original 3WD. (width × height × length) denotes the frame resolution and the number of processed frames. * Time for matrix decomposition (in seconds). Does not include the time to compute the input constraint (saliency maps).

DOUBLE-CONSTRAINED RPCA

+ Iteration limit 100 reached.

Conclusion

In summary, a double-constrained version of RPCA is proposed to improve the foreground detection in dynamic scenes. The sparse component is constrained by shape and confidence maps both extracted from spatial saliency maps. The experimental results indicate a better enhancement of the object foreground mask when compared with its direct competitors. As shown in qualitative and quantitative evaluation, the combination with confidence map and shape constraint can reduce the amount of false positive pixels. In addition, the computational cost evaluation demonstrates that the proposed algorithm has a slightly change in the number of iterations and computation time compared to the original 3WD.

In further works, we plan to investigate how spatio-temporal saliency detectors can help the proposed approach to improve the foreground detection. In this chapter, the confidence map and shape constraint were built from the same source, specifically by saliency maps. We will explore how different sources can be used to build separately these constraints.

Chapter 5 Incremental tensor subspace learning using multiple features

In this chapter, we present an incremental multi-feature tensor subspace learning (IMTSL) algorithm for handling streaming multidimensional data in the case of intelligent video surveillance applications. The proposed method constructs a multi-feature low-rank model for robust modeling of the scene background. Moreover, the IMTSL method updates the low-rank model incrementally through an incremental learning of its unfolding matrices. This work is based on our publication (ICIAR, 2014, [START_REF] Sobral | Incremental and multi-feature tensor subspace learning applied for background modeling and subtraction[END_REF]), and the related source code can be found in the IMTSL website 1 .

The remainder of this chapter is organized as follows. First we start with some related work in Section 5.1. Section 5.2 describes the incremental and multi-feature tensor subspace learning algorithm. Section 5.3 presents the foreground detection method. Finally, in Sections 5.4 and 5.5, the experimental results are shown, as well as conclusions.

Related work

In the literature, several authors have employed tensor decomposition for learning a low-rank representation of the data. [START_REF] Vasilescu | Multilinear analysis of image ensembles: Tensorfaces[END_REF] by Vasilescu and Terzopoulos was one of the first works to employ HOSVD (see Chapter 2, Section 2.4.1.1) for performing a multilinear analysis of facial images under different illumination conditions, expressions, viewpoints and person identities. The image sequence is represented as a higher-dimensional tensor and then decomposed in order to separate and parsimoniously represent the constituent factors, resulting in a "TensorFaces" representation. Wang and Ahuja [START_REF] Wang | Facial expression decomposition[END_REF] also employed HOSVD for learning the expression subspace and person subspace from an ensemble of facial images. The algorithm performs a simultaneous face and facial expression recognition, which can classify the given image into one of the basic facial expression categories. He et al. [START_REF] He | Tensor subspace analysis[END_REF] presented . In (d), an incremental higher-order singular value decomposition (iHOSVD) is applied in the tensor T t resulting in a low-rank tensor L t . Finally, in the step (e) a foreground detection method is applied for each new frame to segment the moving objects.

a tensor subspace analysis algorithm called TSA (Tensor Subspace Analysis), which detects the intrinsic local geometrical structure of the tensor space by learning a lower dimensional tensor subspace. Experiments on PIE and ORL databases demonstrated the efficiency and effectiveness of the method. However, in these last works any experiment was carried out for the background subtraction problem.

Recently, online tensor subspace learning approaches have been introduced. Sun et al. [START_REF] Sun | Incremental tensor analysis: Theory and applications[END_REF] proposed three tensor subspace learning methods: DTA (Dynamic Tensor Analysis), STA (Streaming Tensor Analysis) and WTA (Window-based Tensor Analysis). However, Li et al. [START_REF] Hu | Incremental tensor subspace learning and its applications to foreground segmentation and tracking[END_REF] explained that the above tensor analysis algorithms cannot be applied to background modeling and object tracking directly. To solve this problem, some authors [START_REF] Hu | Incremental tensor subspace learning and its applications to foreground segmentation and tracking[END_REF]112,[START_REF] Li | Robust visual tracking based on incremental tensor subspace learning[END_REF] proposed a high-order tensor learning algorithm, called incremental rank-(R1,R2,R3) tensor based subspace learning. This online algorithm builds a low-order tensor eigenspace model in which the mean and the eigenbasis are updated adaptively. The authors model the background appearance images as a 3-order tensor. Next, the tensor is subdivided into sub-tensors. Then, the proposed incremental tensor subspace learning algorithm is applied to effectively mine statistical properties of each sub-tensor. The experimental results show that the proposed approach is robust to appearance changes in background modeling and object tracking. The method described above only uses the gray-scale and color information. In some situations, only the pixels intensities may be insufficient to perform a robust foreground detection. To deal with this situation, an incremental and multi-feature tensor subspace learning algorithm is presented in this chapter.

Proposed method

Differently from previous related works, where the tensor model is built directly from the video data (i.e., each frontal slice of the tensor is a gray-scale image), in this chapter the tensor model is built from the feature extraction process. First, the last A 3 frames from a streaming video data are stored in a tensor A t ∈ R A1×A2×A3 , where t represents the tensor A at time t. A 1 and A 2 is the frame width and frame height respectively, and A 3 is the number of stored frames (A 3 = 25 in the experiments). Subsequently, the tensor A t is transformed into a tensor T t ∈ R T1×T2×T3 after a feature extraction process, where T 1 is the number of pixels (T 1 = A 1 × A 2 ), T 2 the number of feature values for each frame (T 2 = A 3 ) and T 3 the number of features. Here, 8 features are extracted: 1) red channel, 2) green channel, 3) blue channel, 4) gray-scale, 5) local binary patterns (LBP), 6) spatial gradients in horizontal direction, 7) spatial gradients in vertical direction, and 8) spatial gradients magnitude. All frames' resolution are resized to 160x120 (19200 pixels), so the dimension of the tensor model is T t ∈ R 19200×25×8 . The steps described here are shown in Figure 5.1 (a), (b) and (c). The steps (d) and (e) will be described in the next sections.

Incremental high-order singular value decomposition

Let A ∈ R m×n be a matrix of full rank r = min(m, n). Its singular value decomposition can be expressed as: A = UΣV T , where U ∈ R m×m and V ∈ R n×n are orthonormal matrices containing the eigenvectors of AA T and A T A, respectively, (i.e. right and left singular vectors of A), and Σ = diag(σ 1 , . . . , σ r ) is a diagonal matrix with the eigenvalues of A in descending order. However, the matrix factorization step in SVD is computationally very expensive, especially for large matrices. Moreover, the entire data may be not available for decomposition (e.g. streaming data when the full size of the data is unknown). Businger [START_REF] Businger | Updating a singular value decomposition[END_REF], and Bunch and Nielsen [START_REF] Bunch | Updating the singular value decomposition[END_REF] are the first authors who have proposed to update SVD sequentially with the arrival of more samples, i.e. appending/removing a row/column. Subsequently, various approaches [START_REF] Balzano | On GROUSE and incremental SVD[END_REF][START_REF] Brand | Fast low-rank modifications of the thin singular value decomposition[END_REF][START_REF] Levy | Sequential karhunen-loeve basis extraction and its application to images[END_REF][START_REF] Melenchón | Efficiently downdating, composing and splitting singular value decompositions preserving the mean information[END_REF][START_REF] Ross | Incremental learning for robust visual tracking[END_REF] have been proposed to update the SVD more efficiently and supporting new operations. Recently, Baker et al. [START_REF] Baker | Low-rank incremental methods for computing dominant singular subspaces[END_REF] provided a generic approach to perform a low-rank incremental SVD. An implementation of the algorithm is freely available in the IncPACK MATLAB package 2 .

In this chapter, we have used a modified version of the algorithm in [START_REF] Baker | Low-rank incremental methods for computing dominant singular subspaces[END_REF]. The original version supports only the updating operation. As described previously, the tensor model T t is updated dynamically. The last feature values are appended (i.e. updating operation) and the old feature values are removed (i.e. downdating operation) for each new frame. A simple change would be to modify the algorithm so that, instead of using a hard window, we insert an exponential forgetting factor λ < 1 (λ = 1 no forgetting occurs), weighting new columns preferentially over earlier columns. The forgetting factor is explained in the work of Ross et al. [START_REF] Ross | Incremental learning for robust visual tracking[END_REF].

The proposed iHOSVD algorithm is shown in Algorithm 2. It creates a low-rank tensor model L t with the dominant singular subspaces of the tensor model T t . T

[n] t denotes the n-mode unfolding matrix (see Appendix C) of the tensor T at time t. r [n] and t [n] are the desired rank r and its thresholding value of the n-mode unfolding matrix (r [1] = 1, r [2] = 8, r [3] = 2, and t [1] = t [2] = t [3] = 0.01 in the experiments). U

[n] t-1 , Σ [n]
t-1 , and V

[n] t-1 denote the previous SVD of the n-mode unfolding matrix of the tensor T at time t -1.

INCREMENTAL TENSOR SUBSPACE LEARNING

Algorithm 2 iHOSVD algorithm.

Input: T t , r [n] , t [n] S t ← T t if t = 0 then for i = 1 to n do {Performs the standard rank-r SVD} [U [i] t , Σ [i] t , V [i] t ] ← SVD(T [i] t , r [i] , t [i] ) end for else for i = 1 to n do {Performs the incremental rank-r SVD} [U [i] t , Σ [i] t , V [i] t ] ← iSVD(T [i] t , r [i] , t [i] , U [i] t-1 , Σ [i] t-1 , V [i] t-1 ) end for end if S t ← T t × 1 (U [1] t ) T . . . × n (U [n]
t ) T (× n denotes the n-mode product between tensor T and matrix U)

Output: S t , U [1] t , ..., U [n] t

Foreground detection

The foreground detection consists of segmenting all foreground pixels of the image to obtain the foreground components for each frame. As explained in the previous sections, a lowrank model L t is built from the tensor model T t incrementally. Then, for each new frame a weighted combination of similarity measures is performed. This process has two stages: first a similarity function is calculated, then a weighted combination is performed. Let F t ∈ R A1×A2×T3 the feature's set extracted from the input frame at time t and F t the set of lowrank features reconstructed from the low-rank model L t at time t; the similarity function S for the k-th feature (k = {1, . . . , T 3 }) at the pixel (i, j) is computed as follows:

S t (i, j, k) =        Ft(i,j,k) F t(i,j,k) if F t (i, j, k) < F t (i, j, k) 1 if F t (i, j, k) = F t (i, j, k) F t(i,j,k) Ft(i,j,k) if F t (i, j, k) > F t (i, j, k)
where F t (i, j, k) and F t (i, j, k) are the feature value of pixel (i, j) for the feature k at time t, respectively. Note that S t (i, j, k) assumes values in [0, 1]. Furthermore, S t (i, j, k) is close to one if F t (i, j, k) and F t (i, j, k) are very similar. Next, a weighted combination of similarity measures is computed as follows:

W t (i, j) = T3 k=1 w k S t (i, j, k)
where T 3 is the total number of features and w k weight for the k-th feature (w 1 = w 2 = w 3 = w 6 = w 7 = w 8 = 0.125, w 4 = 0.225, w 5 = 0.025 in the experiments). The weights are chosen empirically in order to maximize the true positive pixels and minimize the false negative pixels in the foreground detection. The foreground mask FG at time t is obtained by applying the following threshold function:

FG t (i, j) = f (W t (i, j)) = 1 if W t (i, j) < τ 0 otherwise
where τ is the threshold value (τ = 0.5 in the experiments). In the next section we shows the experimental results of the proposed method.

Experimental results

In order to evaluate the performance of the proposed method for background modeling and subtraction, the BMC dataset 3 proposed by Vacavant et al. [START_REF] Vacavant | A benchmark dataset for foreground/background extraction[END_REF] is selected. We have compared our method with GRASTA algorithm proposed by He et al. [START_REF] He | Incremental gradient on the Grassmannian for online foreground and background separation in subsampled video[END_REF] and BLWS algorithm proposed by Lin and Wei [START_REF] Lin | The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices[END_REF]. Tables 5.1 and 5.3 show the quantitative and the visual results (input image, ground-truth and foreground detection) with synthetic and real video sequences of the BMC dataset. The quantitative results in Table 5.1 4 show that the proposed method outperforms the previous methods, with the highest F-measure average and best scores over all video sequences except in 212, 312, 412 and 512. The visual results in Table 5.1 show the foreground detection for the frame #300 (Street) and frame #645 (Rotary), respectively. The experiments were performed on a computer running Intel Core i7-3740qm 2.7GHz processor with 16Gb of RAM. However, the proposed algorithm requires aprox. 2min per frame for background subtraction, where more than > 95% of time is used for low-rank decomposition. Further research consist in improving the speed of the incremental low-rank decomposition for real-time applications. Matlab codes and experimental results can be found in the iHOSVD homepage5 . Sequence Video "Wandering student"(frame #651)

Sequence Video "Traffic during windy day"(frame #140)

Conclusion

In summary, an incremental and multi-feature tensor subspace learning algorithm is presented. The multi-feature tensor model allows us to build a robust low-rank model of the background scene. Experimental results show that the proposed method achieves promising results for the background subtraction task. However, additional features can be added, enabling a more robust model of the background scene. Moreover, the proposed foreground detection approach can be changed to automatically select the best features allowing an accurate foreground detection. Further research consist of improving the speed of the incremental low-rank decomposition for real-time applications. Additional support for dynamic backgrounds might be interesting for real and complex scenes.

Chapter 6

Online stochastic tensor decomposition for multispectral video sequences

In this chapter, we propose an online stochastic tensor decomposition algorithm, named OSTD, to perform background/foreground separation in streaming multispectral video sequences. Differently from the IMTSL method presented in the previous chapter, that employed an incremental version of HOSVD, the OSTD algorithm makes use of RPCA on tensors for a robust background/foreground separation. In addition, OSTD was designed to be much faster than IMTSL and address the major difficulties of multispectral imaging for intelligent video surveillance applications. The work presented in this chapter is based on our publication (IEEE ICCV Workshop on RSL-CV, 2015, [START_REF] Sobral | Online stochastic tensor decomposition for background subtraction in multispectral video sequences[END_REF]), and the related source code can be found in the OSTD website1 .

Introduction

Until now, most of background subtraction algorithms were designed for mono (i.e. graylevel) or trichromatic cameras (i.e. RGB) within the visible spectrum or near infrared part (NIR).

Recent advances in multispectral imaging technologies give the possibility to record multispectral videos for video surveillance applications [START_REF] Benezeth | Background subtraction with multispectral video sequences[END_REF]. In addition, this task becomes more complex when the data size grows (i.e. massive multidimensional data), since the real-world scenario requires larger data to be processed in a more efficient way, and in some cases, in a continuous manner (streaming data).

The primary advantage of multispectral cameras for video surveillance is the possibility to take into account the spatial (or spatio-temporal) relationships among the different spectra in a neighbourhood, allowing more elaborate spectral-spatial (and -temporal) models for a more accurate segmentation. However, the primary disadvantages are cost and complexity, due its massive and multidimensional characteristics.

76

ONLINE STOCHASTIC TENSOR DECOMPOSITION

Usually a multispectral video consists of a sequence of multispectral images sensed from contiguous spectral bands. Each multispectral image can be represented as a threedimensional data cube, or tensor, and here we call frame the measurements corresponding to a single spectral band (frontal slice of the tensor). Due to the specific nature of these data, many of the bands within multispectral images are often strongly correlated. In addition, processing multispectral images with hundreds of bands can be computationally burdensome.

In order to address these major difficulties of multispectral imaging for video surveillance (in particular, the detection of moving objects), this chapter proposes an online stochastic framework for tensor decomposition of multispectral video sequences. In short, the main contributions of this chapter are:

• an online stochastic framework for tensor decomposition to deal with multi-dimensional and streaming data, and

• the use of multispectral video sequences instead of standard mono/trichromatic images, enabling a better background subtraction.

First, we start with the related work in Section 6.2. The proposed method is described in Section 6.3. Finally, in Sections 6.4 and 6.5, the experimental results are shown, as well as conclusions.

Stochastic decomposition on tensors

Most of incremental tensor subspace learning approaches apply matrix SVD in the unfolded matrices. These approaches are usually an incremental version of the Tucker3 model (see Chapter 2, Section 2.4.1.1). However, the matrix factorization step in SVD is computationally very expensive, especially for large matrices. Therefore, real time processing is sacrificed, due to the major challenges discussed above. In order to address these problems, this chapter proposes a robust and fast online tensor-based algorithm for RGB videos, as well as for MSVS (multispectral video sequences). The proposed algorithm is based on stochastic decomposition of low-rank and sparse components. The idea of online stochastic RPCA optimization was previously proposed by Feng et al. [START_REF] Feng | Online robust PCA via stochastic optimization[END_REF] and Goes et al. [START_REF] Goes | Robust Stochastic Principal Component Analysis[END_REF], and it was successfully applied to background subtraction in [START_REF] Javed | OR-PCA with MRF for robust foreground detection in highly dynamic backgrounds[END_REF][START_REF] Javed | Background subtraction via superpixel-based online matrix decomposition with structured foreground constraints[END_REF][START_REF] Javed | OR-PCA with dynamic feature selection for robust background subtraction[END_REF]. In this chapter, we extend this approach to tensor analysis. The stochastic optimization is applied on each mode of the tensor and the individual basis2 are updated iteratively followed by the processing of one video frame per time instance. In addition, a comparison of RGB and MSVS is provided, which shows that visible together with NIR spectral bands provide an improved foreground estimation compared to RGB features alone.

Proposed method

Let say that Y is an input N -th order tensor, which is corrupted by outliers, say E; then Y can be reconstructed by separating it into low-rank tensor X (that corresponds to BG), and sparse error E (that corresponds to FG objects), i.e., Y = X + E, under the convex optimization framework developed in Goldfarb and Qin [START_REF] Goldfarb | Robust low-rank tensor recovery: Models and algorithms[END_REF] as: minimize

X ,E 1 2 N i=1 ||Y [i] -X [i] -E [i] || 2 F +λ 1 ||X [i] || * +λ 2 ||E [i] || 1 , (6.1)
where ||X [i] || * and ||E [i] || 1 denote the nuclear and l 1 norm of each i-mode unfolding matrices of X and E, respectively. Efficient methods such as CP decomposition and Tucker decomposition [START_REF] Kolda | Tensor decompositions and applications[END_REF] (a.k.a HOSVD) are used for low-rank decomposition of tensors (see Chapter 2, Section 2.4). In addition, APG, HORPCA-s based on ADAL and HORPCA-M based on I-ADAL were also developed in Goldfarb and Qin [START_REF] Goldfarb | Robust low-rank tensor recovery: Models and algorithms[END_REF] to solve the problem in Equation (6.1). However, as mentioned above, these methods are based on batch optimization and are not suitable for scalable or streaming data.

In this chapter, an online optimization is considered to solve problem (6.1). The major challenge is the computation of HOSVD, because the nuclear norm keeps all the samples tightly and therefore all samples are accessed during optimization at each iteration. Therefore, it suffers from high computational complexity. In contrast, an equivalent nuclear norm is used in this chapter for each i-mode unfolding matrices of X , whose rank is upper bounded, as shown in Recht et al. [START_REF] Recht | Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization[END_REF], as: (6.2)

||X [i] || * = inf Li,Ri 0.5(||L i || 2 F +||R i || 2 F ), subject to X [i] = L i R T i ,
where L i ∈ R p×r , R i ∈ R q×r , p × q denotes the dimension of the unfolding matrix X [i] , and r is the rank. Equation (6.2) shows that i-mode unfolding matrices of low-rank tensor X can be an explicit product of each low-dimensional subspace basis L ∈ R p×r and its coefficients R ∈ R q×r and this re-formulated nuclear norm is shown in [START_REF] Burer | A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization[END_REF][START_REF] Recht | Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization[END_REF][START_REF] Rennie | Fast maximum margin matrix factorization for collaborative prediction[END_REF]. Hence, Equation (6.1) is re-formulated by substituting Equation (6.2) by:

(6.3) minimize X ,E,L,R 1 2 N i =1 ||Y [i] -X [i] -E [i] || 2 F + λ 1 2 (||L i || 2 F + ||R i || 2 F ) + λ 2 ||E [i] || 1 , subject to X [i] = L i R T i .
The objective function minimization, avoiding the constraints in Equation (6.3) and setting

X [i] = L i R T i , is defined as follows: minimize L,R,E 1 2 N i=1 ||Y [i] -L i R T i -E [i] || 2 F + λ 1 2 (||L i || 2 F +||R i || 2 F ) + λ 2 ||E [i] || 1 , (6.4)
where λ 1 and λ 2 are regularization parameters for low-rank and sparsity patterns. Equation (6.4) is the main equation for stochastic tensor decomposition, which is not completely convex with respect to L i and R i . However, Equation (6.3) gives the global optimal solution to the original optimization problem in Equation (6.2), as proved in Feng et al. [START_REF] Feng | Online robust PCA via stochastic optimization[END_REF]. The following cost function is required to be optimized for solving Equation (6.3) as:

f n (L) = 1 n N i=1 n t=1 l(Y (t)[i] , L i ) + λ 1 2n ||L i || 2 F , (6.5)
where n is the number of samples, and Y (t) [i] denotes the i th mode of a tensor Y at time instance t given by:

l(Y (t)[i] , L i ) = minimize L,R,E ||vec(Y (t)[i] ) -L i r -e|| 2 2 + λ 1 2 ||r|| 2 2 +λ 2 ||e|| 1 . (6.6)
where r ∈ R r and e ∈ R p are vectors of coefficient and noise for matrix R T i and unfolded matrix E [i] , respectively. Finally, the objective function l t (L i ) for updating the basis L i at time instance t is given by:

l t (L i ) = 1 n n t=1 1 2 ||vec(Y (t)[i] ) -L i r (t) -e (t) || 2 2 + λ 1 2 ||r (t) || 2 2 +λ 2 ||e (t) || 1 + λ 1 2n ||L i || 2 F , (6.7)
The main goal is to minimize the cost function in Equation (6.5) through stochastic optimization method, as shown in Algorithm 3. In case of BG modeling, one video frame (i.e. RGB image) at a time t is processed in an online manner. The coefficient r, sparse outliers e and basis L i are optimized in an iterative way. Moreover, r and e are estimated with fixed random basis L i by projecting one sample using Equation (6.2). This subproblem requires to solve the following small-scale convex optimization problem at time instance t:

r (t) = (L T i L i + λ 1 I) -1 L T i vec(Y (t)[i]
)e (t-1) , (6.8)

e (t) =        M (t) (k) -λ 2 , if M (t) (k) > λ 2 , M (t) (k) + λ 2 , if M (t) (k) < λ 2 , 0, otherwise, (6.9)
where M (t) = vec(Y (t) [i] ) -Lr (t) and M (t) (k) is the k-th element in M (t) . The basis L i is estimated using Equation (6.13) through minimizing the previously computed coefficients r and e, and it is updated using Algorithm (4). If the rank r is given and the basis L i is estimated as above, then L i converges to the optimal solution asymptotically as compared to its batch counterpart, as shown in Feng et al. [START_REF] Feng | Online robust PCA via stochastic optimization[END_REF]. The BG sequence is then modeled by low-rank tensor X which changes at a time instance t. Finally, a hard thresholding scheme is applied on a sparse component to get the binary FG mask (see Equation 4.8).

Algorithm 3 Online Stochastic Tensor Decomposition

Input: Y ∈ R I1×I2×...×I N . Initialize: X = E = 0 (low-rank and sparse components), L ∈ R p×r (initial basis),

A ∈ R r×r , B ∈ R p×r , r ∈ R r , R ∈ R q×r , e ∈ R p , I ∈ R r×r (unitary matrix), λ 1 = 1 √ max(size(Y)
, and λ 2 = 10λ 1 .

1: for t = 1 to n do {access each sample} 2:

for i = 1 to N do {each tensor mode} 3:

Access each sample from i th mode of tensor Y by Y (t) [i] .

4:

Compute the coefficients r and noise e by projecting the new sample as:

r (t) , e (t) = arg min 1 2 ||vec(Y (t)[i] ) -L (t-1) i r -e|| 2 2 + λ 1 2 ||r|| 2 2 +λ 2 ||e|| 1 . (6.10) 5:
Compute the accumulation matrices A (t) and B (t) :

A (t) ← A (t-1) + r (t) r (t)T , (6.11)
B (t) ← B (t-1) + (vec(Y (t)[i]
)e (t) )r (t)T . (

i with previous iteration L (t-1) i and update the basis using Algorithm (4).

L (t) i = arg min 1 2 T r[L (t-1)T i (A (t) + λ 1 I)L (t-1) i ] -T r(L (t-1)T i B (t)
). (6.13) 7:

L (t)[i] ← L i R T i (low-dimensional subspace for each i-th mode) 8:
vec(E (t) [i] ) ← e (t) (sparse error) 9:

end for 10: end for Output: The proposed method is also tested for quantitative analysis. The MSVS dataset contains images of size 658×492 for each band. So, the size of the input tensor A with 7 multispectral bands is 658×492×7 for each video frame. The F-measure value (see Table 4.2) is computed for each video sequence with its available ground truth images. Table 6.1 shows a comparison results achieved using the RGB bands and all the seven multispectral bands (MSB). The average F-measure score is compared for each video with 3 other methods: CP-ALS [START_REF] Kolda | Tensor decompositions and applications[END_REF], HORPCA [START_REF] Goldfarb | Robust low-rank tensor recovery: Models and algorithms[END_REF], and BRTF [253] (see Chapter 2, Section 2.4). The experimental evaluations show that the proposed methodology outperforms the other approaches.

X = 1 N N i=1 X [i] , E = N i=1 E [i] .

Algorithm 4 Basis Update

Input: L = [l 1 , ..., l r ] ∈ R p×r , A = [a 1 , . . . , a r ] ∈ R r×r , B = [b 1 , . . . , b r ] ∈ R p×r . 1: A ← A + λ 1 I 2:
The proposed scheme processes each multispectral or RGB image per time instance reaching almost real-time processing, whereas CP-ALS, HORPCA, and BRTF are based on batch optimization strategy. Due to this limitation, the CP-ALS, HORPCA, and BRTF were applied for each 100 frames at time (reducing the computational cost) of the whole video sequence (fourth-order tensor). In this chapter, the parameter r in Algorithm (3) was defined experimentally as 10. For CP-ALS, the rank was defined as 50 for better visual results. For HORPCA and BRTF, we used their default parameters. To obtain the foreground mask, the sparse component E was thresholded. We calculated the mean of E along the third dimension, generating a matrix E, then a hard threshold function (see Equation 4.8) was applied.

Basis initialization with bilateral random projections

Bilateral Random Projections (BRP) was first proposed by Zhou and Tao [START_REF] Zhou | Bilateral random projections[END_REF] as a fast lowrank approximation method for dense matrices. The effectiveness and the efficiency of BRP was verified in [START_REF] Zhou | Godec: Randomized low-rank & sparse matrix decomposition in noisy case[END_REF] for the GoDec algorithm to perform low-rank and sparse decomposition. Given r bilateral random projections of a m × n dense matrix X, the low-rank approximation L can be rapidly built by:

L = Y 1 (A T 2 Y 1 ) -1 Y T 2 (6.15)
where Y 1 = XA 1 , Y 2 = X T A 2 , and A 1 ∈ R q×r and A 2 ∈ R p×r are random matrices.

In this section, we evaluate the robustness of BRP for the basis initialization instead of the traditional uniformly distributed random numbers (UDRN). For demonstration, Figure 6.5 shows a fast background modeling convergence for the first 20 video frames on the 3 rd video of the MSVS dataset. As it can be seen, BRP enables a fast and effective low-rank approximation, reducing the amount of false positive pixels in the background model initialization task. Finally, the power scheme modification proposed by Zhou and Tao [START_REF] Zhou | Bilateral random projections[END_REF] can accelerate the low-rank recovery when the singular values of X decay slowly.

Computational time

Execution times have also been analyzed in our experiments. The time is recorded in CPU time as [hh : mm : ss] and Table 6.2 shows the computational time of each method for the first 100 frames varying the image resolution. As it can be seen, the proposed algorithm is much faster than its direct competitors: it is almost 5 times faster than BRTF considering frames with size 160 × 120, and 10 times faster than CP-ALS for frames with size 320 × 240. The algorithms were implemented in MATLAB (R2014a) running on a laptop computer with Windows 7 Professional 64 bits, 2.7 GHz Core i7-3740QM processor and 32Gb of RAM. The MATLAB implementation of the proposed approach is available at https:// github.com/andrewssobral/ostd, and the the evaluated algorithms are available in

Conclusion

In summary, we proposed an online stochastic tensor decomposition algorithm for robust BS application. Experimental results show that the proposed methodology outperforms the other considered approaches, and we have achieved almost real time processing, since one video frame is processed at time. The basis initialization with BRP can accelerate the lowrank approximation, reducing the amount of false positive pixels in the background model initialization step. In addition, the basis is updated incrementally, making it more robust against gross outliers. A future research may concern the recent advances on randomized principal component analysis [START_REF] Erichson | Randomized matrix decompositions using r[END_REF][START_REF] Halko | Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions[END_REF][START_REF] Witten | Randomized algorithms for low-rank matrix factorizations: Sharp performance bounds[END_REF]. Instead of making a full decomposition of the unfolded matrices, the randomized algorithms provide an efficient computational framework that computes a compressed representation of the data using random sampling.

Chapter 7

Robust subspace clustering: from single subspace to multiple subspaces

In this chapter, we investigate a particular approach of low-rank and sparse representation, named subspace clustering. Differently from previous methods described in the last chapters, where inliers lie on a single low dimensional subspace, subspace clustering methods consider the inliers are drawn from the union of low-dimensional subspaces. Instead of applying subspace clustering for background modeling and foreground separation as shown in the previous chapters, we evaluate the robustness of some subspace clustering algorithms for human action recognition from 3D skeletal data. This chapter presents a particular work realized in conjunction with the Computer Vision Center (CVC) at Autonomous University of Barcelona (UAB). The work presented here is currently under revision for publication [START_REF] Sobral | Robust subspace clustering of human activities from 3D skeletal data[END_REF]. This chapter is also related with a recently published survey (Sensors, 2016, [START_REF] Gong | Human pose estimation from monocular images: A comprehensive survey[END_REF]) on human pose estimation from monocular images in collaboration with researchers from China University of Petroleum and CVC.

Introduction

Human action recognition (HAR) is an important problem in computer vision. Application fields include video surveillance, automatic video indexing and human computer interaction. Most solutions for HAR learn action patterns from sequences of image features, like Space-Time Interest Points (STIP) [START_REF] Laptev | Space-time interest points[END_REF], temporal templates [START_REF] Davis | The representation and recognition of human movement using temporal templates[END_REF], 3D SIFT [START_REF] Scovanner | A 3-dimensional Sift descriptor and its application to action recognition[END_REF], optical flow [START_REF] Ahmad | Hmm-based human action recognition using multiview image sequences[END_REF][START_REF] Ali | Human action recognition in videos using kinematic features and multiple instance learning[END_REF], Motion History Volume [START_REF] Weinland | Motion history volumes for free viewpoint action recognition[END_REF], among the others. These features are commonly used to describe human actions, which are subsequently classified using techniques like Hidden Markov Models [START_REF] Ahmad | Hmm-based human action recognition using multiview image sequences[END_REF] and Support Vector Machines [START_REF] Schuldt | Recognizing human actions: A local SVM approach[END_REF]. Recent and exhaustive reviews of methods for HAR can be found in [START_REF] Poppe | A survey on vision-based human action recognition[END_REF][START_REF] Weinland | A survey of vision-based methods for action representation, segmentation and recognition[END_REF].

However, the development of advanced motion sensing devices, and especially the emergence of Microsoft Kinect [START_REF] Han | Enhanced computer vision with microsoft kinect sensor: A review[END_REF], has enabled us to capture the human skeleton from the depth information in real-time, which inspired the research on activity recognition from 3D skeletal data. An increasing number of algorithms have employed depth data in vision-based human action recognition [START_REF] Aggarwal | Human activity recognition from 3D data: A review[END_REF][START_REF] Chen | A survey of human motion analysis using depth imagery[END_REF][START_REF] Presti | 3D skeleton-based human action classification: A survey[END_REF]. The human body is represented as an articulated system of rigid segments connected by joints (human skeleton) [START_REF] Shotton | Real-time human pose recognition in parts from a single depth image[END_REF]175], and human action is considered as a continuous evolution of the spatial configuration of these segments. In essence, the problem of action recognition is based on the information extracted from a number of action descriptors calculated from a skeleton fitted to the body of a tracked subject.

On the one hand, approaches for recognizing human activities from skeletal data play an important role in human motion analysis using depth imagery. On the other hand, very few researches explore the recent advances in robust subspace clustering. In particular, we consider that the skeletal actions can be drawn from the union of low-dimensional subspaces. In accordance with the last advances on subspace clustering, Sparse Subspace Clustering (SSC) [START_REF] Elhamifar | Sparse subspace clustering[END_REF] and Low-Rank Representation (LRR) [START_REF] Liu | Robust recovery of subspace structures by low-rank representation[END_REF] are both considered as the state-ofthe-art methods for subspace clustering [START_REF] Elhamifar | Sparse subspace clustering: Algorithm, theory, and applications[END_REF][START_REF] Soltanolkotabi | Robust subspace clustering[END_REF][START_REF] Vidal | Subspace clustering[END_REF][START_REF] Vidal | Low rank subspace clustering (LRSC)[END_REF][START_REF] Wang | Nonconvex relaxation approaches to robust matrix recovery[END_REF] (see Chapter 2, Section 2.3). In the meantime, most of related works on subspace clustering were applied to motion segmentation [START_REF] Kanatani | Motion segmentation by subspace separation and model selection[END_REF][START_REF] Li | Structured sparse subspace clustering: A unified optimization framework[END_REF][START_REF] Rao | Motion segmentation via robust subspace separation in the presence of outlying, incomplete, or corrupted trajectories[END_REF][START_REF] Vidal | Multiframe motion segmentation with missing data using powerfactorization and GPCA[END_REF][START_REF] Xu | Reweighted sparse subspace clustering[END_REF][START_REF] Yang | Sparse subspace clustering with missing entries[END_REF], face clustering [START_REF] Chen | Robust subspace segmentation via low-rank representation[END_REF][START_REF] Li | Structured sparse subspace clustering: A unified optimization framework[END_REF][START_REF] Park | Greedy subspace clustering[END_REF][START_REF] Xu | Reweighted sparse subspace clustering[END_REF], and video summarization or scene categorization [START_REF] Elhamifar | Dissimilarity-based sparse subset selection[END_REF][START_REF] Tierney | Subspace clustering for sequential data[END_REF]. Only a few works [START_REF] Elhamifar | Dissimilarity-based sparse subset selection[END_REF][START_REF] Tierney | Segmentation of subspaces in sequential data[END_REF] have explored the use of low-dimensional subspace approaches for human activity analysis from 3D skeletal data.

In this chapter, we present a methodology for robust subspace clustering of human activities from 3D skeletal data (whose black diagram is shown in Figure 7.1). In addition, we evaluate some LRR and SSC-based approaches for the 3D skeletal action recognition problem. A comparison between five skeletal representations is also covered in the experimental results. First, we start with the related work in Section 7.2. A brief introduction to subspace clustering is provided in Section 7.3. Next, the feature extraction process from skeletal data is described in Section 7.4. Finally, the experimental results on recent skeletal action datasets are reported in Section 7.5, as well as conclusions in Section 7.6.

Related works

Here, we present some works related to skeletal action recognition taking into account a supervised learning perspective (Section 7.2.1) and from an unsupervised one (Section 7.2.2).

Supervised skeletal-based action recognition

Recent skeletal-based action recognition approaches have incorporated new representations for describing actions, and some related works are here summarized. Xia et al. [START_REF] Xia | View invariant human action recognition using histograms of 3D joints[END_REF] present an approach to human action recognition using histograms of 3D joint locations (HOJ3D) as a compact representation of postures. The 3D skeletal joint locations are extracted from Kinect depth maps using Shotton et al.'s method [START_REF] Shotton | Real-time human pose recognition in parts from a single depth image[END_REF]. The HOJ3D computed from the action depth sequences are reprojected using LDA and then clustered into k posture visual words, which represent the prototypical poses of actions. The temporal evolutions of those visual words are modeled by discrete hidden Markov models (HMMs).

Devanne et al. [START_REF] Devanne | Spacetime pose representation for 3D human action recognition[END_REF] proposed a spatio-temporal motion trajectory representation for skeletal action recognition. Each trajectory consists of one motion channel corresponding to the evolution of the 3D position of all joint coordinates within frames of action sequence. The action recognition is achieved through a shape trajectory representation that is learnt by a K-NN classifier, which takes benefit from Riemannian geometry in an open curve shape space.

In Yang et al. [START_REF] Yang | Effective 3D action recognition using eigenjoints[END_REF], a feature descriptor is proposed for action recognition based on differences of skeleton joints (EigenJoints), which combine action information including static posture, motion property, and overall dynamics. An Accumulated Motion Energy (AME) method is proposed to perform informative frame selection, which is able to remove noisy frames and reduce computational cost. In addition, a non-parametric Naïve-Bayes-Nearest-Neighbor (NBNN) is employed to classify multiple actions.

In Vemulapalli et al. [START_REF] Vemulapalli | Human action recognition by representing 3D skeletons as points in a lie group[END_REF], a new skeletal representation is proposed that explicitly models the 3D geometric relationships between various body parts using rotations and translations in 3D space. Since 3D rigid body motions are members of the special Euclidean group SE(3), the proposed skeletal representation lies in the Lie group SE(3)×...×SE(3), which is a curved manifold. Using the proposed representation, human actions can be modeled as curves in this Lie group. The classification is done using a combination of dynamic time warping (DTW), Fourier temporal pyramid representation and linear SVM.

In Pazhoumand-Dar et al. [START_REF] Pazhoumand-Dar | Joint movement similarities for robust 3D action recognition using skeletal data[END_REF], a novel technique that automatically determines discriminative sequences of relative joint positions is proposed for each action class. The authors employ a combination of spatio-temporal based skeleton features and propose a new similarity function based on the longest common subsequence (LCSS) algorithm [START_REF] Vlachos | Discovering similar multidimensional trajectories[END_REF] for dealing with both simple and complex actions. The LCSS algorithm provide an intuitive notion of similarity between trajectories by giving more weight to similar portions of the sequences [START_REF] Vlachos | Discovering similar multidimensional trajectories[END_REF].

Tao et al. [START_REF] Tao | Moving poselets: A discriminative and interpretable skeletal motion representation for action recognition[END_REF] proposed a novel body-part motion based feature called Moving Poselet, which corresponds to a specific body part configuration undergoing a specific movement. A simple algorithm for jointly learning Moving Poselets and action classifiers is also proposed.

Clustering human activities from skeletal data

To date, only a few works have been proposed to use subspace clustering approaches for human activity recognition from skeletal data. Ball et al. [START_REF] Ball | Unsupervised clustering of people from skeleton data[END_REF] used the k-means algorithm for recognizing individual persons from their walking gait using three-dimensional skeleton data extracted from Microsoft Kinect.

Zhang et al. [START_REF] Zhang | Improving human activity recognition using subspace clustering[END_REF] proposed a subspace clustering approach, named SCAR, to recognize human activity and detect exceptional activities. However, different from previously described approaches, the proposed method was validated on data collected from RFID-based systems.

Oszust et al. [START_REF] Oszust | Recognition of signed expressions observed by kinect sensor[END_REF] presented an approach for recognition of signed expressions based on visual and skeletal data obtained from Kinect sensor. Three clustering algorithms; k-means, k-medoids and minimum entropy clustering (MEC) [START_REF] Li | Minimum entropy clustering and applications to gene expression analysis[END_REF], are used to isolated Polish sign language words from time series data. Kitsikidis et al. [START_REF] Kitsikidis | Dance analysis using multiple kinect sensors[END_REF] presented a method for body motion analysis in dance combining the skeletal tracking data of multiple sensors. A posture vocabulary is generated by performing k-means clustering on a large set of unlabeled postures. Then, body part postures are combined into body posture sequences and the Hidden Conditional Random Fields (HCRF) classifier is used to recognize motion patterns.

Finally, in Azis et al. [START_REF] Azis | Substitutive skeleton fusion for human action recognition[END_REF] k-means clustering is applied to build a dictionary of frame representatives, and actions are encoded as sequences of frame representatives.

Introduction to subspace clustering

Subspace clustering, also referred to as spectral clustering, can be regarded as an extension of the traditional clustering algorithms that seeks to find clusters that best fit a collection of data points taken from a high-dimensional space [START_REF] Parsons | Subspace clustering for high dimensional data: A review[END_REF][START_REF] Soltanolkotabi | Robust subspace clustering[END_REF][START_REF] Vidal | Subspace clustering[END_REF]. Subspace clustering is defined as the problem of fitting a union of subspaces to a collection of data points drawn from one or more subspaces and corrupted by noise and/or gross errors. Mathematically, let X ∈ R M ×N be the data matrix consisting of N vectors {x i ∈ R M } N i=1 which are assumed to be drawn from the union of K linear (or affine) subspaces S k of unknown dimensions d k = dim(S k ) with 0 < d k < M . The subspace clustering problem is to find the number K of subspaces, their dimensions {d k } K k=1 , the subspace bases, and the clustering of vectors x i into these subspaces [START_REF] Babacan | Probabilistic low-rank subspace clustering[END_REF][START_REF] Vidal | Subspace clustering[END_REF].

In the last few years, a large number of subspace clustering methods have been developed. Vidal et al. [START_REF] Vidal | Subspace clustering[END_REF][START_REF] Vidal | Low rank subspace clustering (LRSC)[END_REF] presented four categories of subspace clustering algorithms: algebraic methods (i.e., Generalized PCA or GPCA [START_REF] Vidal | Generalized principal component analysis (GPCA)[END_REF]), iterative methods (i.e., k-plane clustering [START_REF] Bradley | k-plane clustering[END_REF] -generalization of the k-means algorithm), statistical methods (i.e., "mixtures of PCA", and MPPCA [START_REF] Tipping | Mixtures of probabilistic principal component analyzers[END_REF]) and spectral clustering-based methods (ie. factorization-based affinity [23,[START_REF] Costeira | A multibody factorization method for independently moving objects[END_REF], sparse subspace clustering or SSC [START_REF] Elhamifar | Sparse subspace clustering[END_REF][START_REF] Elhamifar | Sparse subspace clustering: Algorithm, theory, and applications[END_REF], and low-rank representation or LRR [START_REF] Chen | Robust subspace segmentation via low-rank representation[END_REF][START_REF] Liu | Robust recovery of subspace structures by low-rank representation[END_REF][START_REF] Vidal | Low rank subspace clustering (LRSC)[END_REF]). Among them, methods based on spectral clustering have been shown to perform very well for several applications in computer vision. In general, these methods tries to first find a sparse or low-rank representation Z of the data matrix X and then apply a SC method on Z [START_REF] Ng | On spectral clustering: Analysis and an algorithm[END_REF].

In the literature, von Luxburg [START_REF] Luxburg | A tutorial on spectral clustering[END_REF] defined spectral clustering-based methods in two steps. First, a symmetric affinity matrix C ∈ [c ij ] is constructed, where c ij = c ij ≥ 0 measures whether points i and j belong to the same subspace. Ideally c ij ≈ 1 if points i and j are in the same subspace and c ij ≈ 0 otherwise. The second step consists in building a weighted undirected graph where the data points are the nodes and the affinities c ij are the weights. Finally, the segmentation of the data is found by clustering the eigenvectors of the graph Laplacian using central clustering techniques, such as k-means (see Figure 7.2). However, a good affinity matrix is the main challenge of this approach. Sometimes the data points could be very close to each other, even from different subspaces (e.g. near the intersection of two subspaces) [START_REF] Vidal | Subspace clustering[END_REF][START_REF] Vidal | Low rank subspace clustering (LRSC)[END_REF].

Previous works [23,[START_REF] Costeira | A multibody factorization method for independently moving objects[END_REF] tried to build the affinity matrix of X by computing the SVD from data matrix X = UΣV T where C = V r V T r and V r are the top r = rank(X) singular vectors of X. However, in real world applications, the data are often contaminated by noise and gross errors. In addition, selecting a good r becomes very difficult and many datasets are better modeled by affine subspaces [START_REF] Vidal | Subspace clustering[END_REF][START_REF] Vidal | Low rank subspace clustering (LRSC)[END_REF].

Recent advances on sparse and low-rank representation approaches have allowed the development of robust methods for building the affinity matrix in the case of data corrupted by noise and/or gross errors. As mentioned in Chapter 2, SSC [START_REF] Elhamifar | Sparse subspace clustering[END_REF] and LRR [START_REF] Liu | Robust recovery of subspace structures by low-rank representation[END_REF] are both considered as the state-of-the-art methods for subspace clustering. In this chapter we evaluate LRR and SCC (and their variants) for human activity recognition from 3D skeletal data.

Feature extraction on skeletal action datasets

Given a video sequence containing a specific human action, the 3D skeletal joint locations are inferred from depth maps via Kinect device using Shotton et al.'s method [START_REF] Shotton | Real-time human pose recognition in parts from a single depth image[END_REF]. The 3D coordinates of each skeletal joint are represented as x ∈ R D , where D = 3. The J extracted skeletal joints are stored in a data vector x = {x 1 , x 2 , . . . , x J } T ∈ R P , where P = DJ. For the whole video sequence, all skeleton joint locations are stored in a data matrix X (1) ∈ R P ×T as:

X (1) =       x 1,1 x 1,2 • • • x 1,T x 2,1 x 2,2 • • • x 2,T . . . . . . . . . . . . x P,1 x P,2 • • • x P,T       , (7.1)
where T is the number of frames. As T may vary per video sequence, a skeletal representation needs to be applied in data matrix X (1) , resulting in a feature matrix X (2) ∈ R F ×T * with fixed size (T * < T ). Finally, the skeletal representation of each action is grouped into an action matrix X (3) ∈ R M ×N for clustering, where M = F T * and N is the total number of actions. The steps described here are shown in Figure 7.3. Several skeletal representations have been proposed in the literature (please refer to Tagliasacchi [START_REF] Tagliasacchi | Skeletal representations and applications[END_REF] for a complete survey).

In this chapter, we have selected five well-known skeletal representations:

• AJP (Absolute Joint Positions) is the concatenation of 3D coordinates of all joints x 1 , . . . , x J .

• RJP (Relative Joint Positions) is the concatenation of all vectors --→ x i x j , 1 ≤ i < j ≤ J.

• JAQ (Joint Angles Quaternions) is the concatenation of the quaternions corresponding to all joint angles.

• SE3AP (SE3 Lie Algebra with Absolute Pairs) and SE3RP (SE3 Lie Algebra with Relative Pairs), both proposed by Vemulapalli et al. [START_REF] Vemulapalli | Human action recognition by representing 3D skeletons as points in a lie group[END_REF], where each individual body part is represented as a point in a Lie group which is a curved manifold. Using this representation, human actions can be modeled as curves in this Lie group. For classification, the action curves are mapped from the Lie group to its Lie algebra, which is a vector space.

However, these skeletal representations are not sufficient for effective classification or clustering due to various issues, like rate variations, temporal misalignment, noise, etc. To deal with these problems, Dynamic Time Warping (DTW) [START_REF] Müller | Information Retrieval for Music and Motion[END_REF] was first applied to handle rate variations. Next, the warped curves are represented using the Fourier temporal pyramid representation [START_REF] Wang | Mining actionlet ensemble for action recognition with depth cameras[END_REF] removing the high frequency coefficients, handling the temporal misalignment and noise issues. This procedure is illustrated in Figure 7.4. Table 7.2 shows the length of each skeletal representation before and after the temporal modeling procedure. The length is represented by F times T * of the feature matrix X (2) , where the difference of RAW length and Final length depends of the skeletal body model. It is important to note that the RAW data from a skeletal representation (output of Figure 7.4(a)) is not the same as the RAW data built up from 3D skeletal joint locations (X (1) in Figure 7.3).

Pre-processing step: In this chapter, we have employed the same pre-processing step as adopted by Vemulapalli et al. [START_REF] Vemulapalli | Human action recognition by representing 3D skeletons as points in a lie group[END_REF]. This step work as follows:

• Invariance to absolute location: all 3D joint coordinates were transformed from the world coordinate system to a person-centric coordinate system by placing the hip center at the origin. • Invariance to scale: one of the skeletons is used as reference, and all the other skeletons were normalized (without changing their joint angles) such that their body part lengths are equal to the corresponding lengths of the reference skeleton. • Invariance to rotation: the skeletons were rotated so that the ground plane projection of the vector from left hip to right hip is parallel to the global x-axis.

Experimental results

In this section, we evaluate the performance of five state-of-the-art subspace clustering algorithms on two skeletal action datasets: UTKinect-Action [START_REF] Xia | View invariant human action recognition using histograms of 3D joints[END_REF] 1 and Florence3D-Action [START_REF] Seidenari | Recognizing actions from depth cameras as weakly aligned multi-part bag-of-poses[END_REF] 2 . Table 7.1 compares both datasets in term of number of actions, subjects and sequences. For all subspace clustering algorithms shown in Table 7.3, we followed the same pipeline:

92

ROBUST SUBSPACE CLUSTERING 1. First, thelow-rank or sparse representation of the action matrix X (3) is obtained.

2. An undirected weighted graph W is constructed by using the low-rank or sparse representation to define the affinity matrix of the graph. W ∈ R N ×N is a symmetric non-negative similarity matrix representing the weights of the edges.

3. The clustering of the nodes is computed using a spectral clustering algorithm. We choose here the Ng et al.'s method [START_REF] Ng | On spectral clustering: Analysis and an algorithm[END_REF] based on the normalized Laplacian as the standard SC method.

Evaluation protocol

In the evaluation, all the parameters are chosen so that the final average clustering error is the lowest (see Section 7.5.2). For all algorithms we varied the threshold ρ in the coefficient matrix in [0, 1] increasing by 0.01. The best ρ is found when the clustering error is minimal. Then, to eliminate the effect of randomness, we repeated such trial 20 times and compared representative algorithms based on the average accuracy and standard deviation.

Implementation details: For all algorithms, we use the MATLAB code provided by their authors. All experiments are carried out using MATLAB 2015a on a laptop machine with Intel(R) Core(TM) i7-3740QM CPU at 2.70 GHz and 32 GB RAM.

Evaluation metrics

Following Chang et al. [START_REF] Chang | A convex formulation for spectral shrunk clustering[END_REF], we adopted clustering accuracy (ACC) as evaluation metrics in the experiments. Let q i be the clustering label resulted from a clustering algorithm and p i the corresponding ground truth label of an arbitrary data point x i . Then, ACC is defined as follows: [START_REF] Patel | Latent space sparse subspace clustering[END_REF] where δ(x, y) = 1 if x = y and δ(x, y) = 0 otherwise. map(q i ) is the best mapping function that permutes clustering labels to match the ground truth labels using the Kuhn-Munkres algorithm [START_REF] Munkres | Algorithms for the assignment and transportation problems[END_REF]. A larger ACC indicates better clustering performance.

ACC = n i=1 δ(p i , map(q i )) n (7.2)

Results on UTKinect-Action dataset

For this dataset, the action matrix X (3) was projected into a r = 2s dimensional subspace using PCA, where s = 10 represents the number of distinct actions. Thus, the number of rows of X (3) ∈ R M ×199 is reduced, where M = 20 is the final row size of the action matrix before subspace clustering. Figure 7.5 shows the feature embedding visualizations using t-SNE [START_REF] Van Der Maaten | Visualizing high-dimensional data using t-sne[END_REF]. Each clip is visualized as a point and clips belonging to the same action have the same color. Note that the features are better grouped after temporal modeling improving the clustering accuracy. Table 7.4 shows the performance comparison in terms of clustering accuracy and std of selected subspace clustering methods between the five skeletal representations, respectively. The best scores for each skeletal representation are in bold face. As it can be seen, LRSC and RSSC both using AJP and RJP as skeletal representation show the best results in terms of clustering ACC compared to their direct competitors. The confusion matrices for these two algorithms are shown in Figure 7.6.

Results on Florence3D-Action dataset

This is a challenging dataset due to the high intra-class variations, where the same action is performed using the left hand in some sequences and the right hand in others. In addition, the presence of actions like drink from a bottle and answer phone are quite similar to each other.

For this dataset, the action matrix X (3) was projected into a r = 10s dimensional subspace using PCA, where s = 9 represents the number of distinct actions. Thus, the row size of X (3) ∈ R M ×215 is reduced, where M = 90 is the final row size of the action matrix before subspace clustering. Table 7.5 shows the performance comparison in terms of clustering accuracy and std of five subspace clustering methods between five skeletal representations, respectively. The best scores for each skeletal representation are in bold face. This is best viewed in Figure 7.7, that shows the feature embedding using t-SNE [START_REF] Van Der Maaten | Visualizing high-dimensional data using t-sne[END_REF]. We note that As it can be seen, the RSSC using AJP as skeletal representation shows the best result in terms of clustering ACC compared to its direct competitors. The confusion matrix for this algorithm is shown in Figure 7.8. However, compared to the results obtained with UTKinect dataset, the Florence3D dataset seems to be more difficult even for the state-of-the-art methods, due to very similar actions such as drink from a bottle and answer phone, as can be seen in Table 7.6. Most of evaluated methods have clustering ACC decreased by a factor of approximately 10%.

Comparison to the state-of-the-art methods

As previously described, the methodology presented in this chapter explores an unsupervised learning approach through robust subspace clustering methods for skeletal action recognition. Table 7.6 compares the result of several state-of-the-art methods with the best subspace clustering method for both datasets. As can be seen, LRSC (low-rank based) and RSSC (sparse based) both achieved promising results compared with state-of-the-art supervised methods.

The proposed work explores unlabeled data to find some intrinsic "natural" structures, organizing them into k-groups taking into account the recent advances on sparse and low-rank representation approaches. Evidently, supervised approaches usually outperforms the unsupervised ones in several key tasks.

Conclusion

In summary, we presented a methodology to recognize human activities from skeletal data through robust subspace clustering. The 3D skeletal joints locations are inferred from depth maps via the Kinect device using Shotton et al.'s method [START_REF] Shotton | Real-time human pose recognition in parts from a single depth image[END_REF]. The experimental results showed that low-rank based (e.g. LRSC) and sparse based (e.g. RSSC) methods are both unsupervised approaches which provide interesting results for human action recognition from skeletal data compared with state-of-the-art supervised methods.

Ideas for future work include the possibility to apply recent Robust PCA methods for filtering the noise in the action matrix before the subspace clustering step. In addition, recent feature selection algorithms [START_REF] Roffo | Report: Feature selection techniques for classification[END_REF] can be evaluated to reduce the dimension of the action matrix instead of traditional PCA approach.

Chapter 8 Conclusions

In this chapter, we summarize the main contributions of the thesis covering the strengths and weaknesses of the proposed approaches presented in the main chapters of this thesis. Finally, we provide an outlook of the future research possibilities and directions.

Summary and contributions

The recent research on decomposition into low-rank plus sparse matrices or tensors shows a general-purpose framework that covers a wide range of applications where the data to be processed have two important assumptions: a) the inliers are drawn from a single (or a union of) low-dimensional subspace(s), and b) the corruptions are sparse. In the thesis, we have explored the fact that this assumption holds a particular association to the problem of B/F separation where the background model (almost static) is represented as a low-rank structure and the foreground objects are associated with the sparse residuals. However, the key issues and challenges in such approaches are their capabilities to handle complex and dynamic background scenarios, as well as performing in a real-time manner. Given the importance of this subject, the thesis presented here has brought the following contributions:

• In Chapter 1, we introduced the problem of moving object detection under background/foreground separation for visual-surveillance applications. We highlighted that the recent research on decomposition into low-rank plus sparse matrices shows a suitable framework to separate moving objects from the background.

• In Chapter 2, we gave an overview of the state-of-the-art methods for low-rank and sparse decomposition, as well as their application to background modeling and foreground segmentation tasks. The methods were unified in a more general framework, named DLSM, that categorizes the matrix separation problem into three main approaches: implicit, explicit and stable. In addition, we developed the matrix separation problem from a single low dimensional subspace to the union of low-dimensional subspaces, introducing the subspace clustering approach. We showed also its adequacy 101

to the problem of background/foreground separation by clustering motion trajectories. Finally, we extended the matrix case to the tensor case for handling multidimensional data.

• In Chapter 3, we presented a novel methodology for background model initialization seen as a reconstruction problem from missing/corrupted data. The redundant frames are eliminated and the moving regions are set to be non-observed values. Next, twenty-three matrix and tensor low-rank recovery algorithms were evaluated for the background initialization problem. The experimental results on the SBI dataset highlighted the good performance of LRGeomCG method over its direct competitors. Finally, we note that matrix-based completion methods show an attractive potential for background modeling initialization in video surveillance.

• In Chapter 4, we proposed a double-constrained version of RPCA to improve the foreground detection in maritime environments for automated video-surveillance applications. The sparse component is constrained by shape and confidence maps, both extracted from spatial saliency maps. The experimental results indicate a better enhancement of the object foreground mask when compared with its direct competitors.

• In Chapter 5, an incremental and multi-feature tensor subspace learning algorithm (IMTSL) was presented. Different from previous related works where a tensor model is built directly from the video data (i.e., each frontal slice of the tensor is a gray-scale image), in this work the tensor model was built from a previous feature extraction process. The multi-feature tensor model allows us to build a robust low-rank model of the background scene. In addition, an incremental high-order singular value decomposition was proposed, making our method able to process streaming data when the full size of the data is unknown. The experimental results have shown that the proposed method achieves promising results for the background subtraction task.

• In Chapter 6, we proposed an online stochastic tensor decomposition algorithm, named OSTD, for handling streaming multispectral video sequences for intelligent video surveillance applications. Differently from the IMTSL algorithm, the OSTD algorithm makes use of robust principal component analysis on tensors for a robust background/foreground separation. The experimental results have shown that the proposed method outperforms its direct competitors, and we have achieved almost real time processing, since one video frame is processed in an online optimization scheme. Moreover, it is shown that the basis initialization with BRP can accelerate the low-rank approximation, reducing the amount of false positive pixels in the background model initialization step.

• Finally, in Chapter 7 we presented a particular work realized in conjunction with Computer Vision Center (CVC) at Autonomous University of Barcelona (UAB). In this chapter, we have shown a methodology to recognize human activities from 3D skeletal data through robust subspace clustering approaches. The experimental results showed that LRSC and RSSC methods were both unsupervised approaches which provided interesting results compared with state-of-the-art supervised methods.

Limitations and future perspectives

The strengths of the contributions introduced in the thesis have been demonstrated through many experimental evaluations. However, there are limitations which could be open opportunities for future research.

• The methodology presented in Chapter 3 has two main drawbacks. First, it makes use of a simple joint motion-detection and frame-selection operation that removes the redundant frames and induces missing entries from the moving regions. This joint operation cannot deal with many real-world challenges of background model initialization, due to its sensitivity to noise, inability to deal with dynamic background and stopped objects, among the others. Secondly, the matrix and tensor completion approaches evaluated in this work make use of a batch optimization process, requiring that all video frames be stored in memory in advance. This is an important issue that limits the application in the case of streaming data or high resolution images.

Future researches may concern: a) the investigation of a more robust approach for frame-selection that can handle the major challenges of video surveillance applications, and b) the development or evaluation of incremental and real-time approaches for low-rank reconstruction, enabling the algorithm to perform the background model initialization in streaming videos.

• The double-constrained RPCA algorithm presented in Chapter 4 makes use of shape and confidence maps, both extracted from spatial saliency maps. Thus it strongly depends on the robustness of the saliency extractor, that could present incorrect segmentation in the presence of high visual saliency objects coming from the background scene. In addition, both confidence map and shape constraint were built from the same source, instead of two complementary sources. Finally, the proposed SCM-RPCA works in a batch manner, requiring all frames be stored in memory, restricting the application in streaming or high resolution videos.

Future work may concern the investigation of how spatio-temporal saliency detectors can help the proposed approach to improve the foreground detection, or how different sources could be used to build complementary shape and confidence maps. Furthermore, the development of an incremental version of the proposed algorithm could be desirable for streaming applications.

• The incremental and multi-feature tensor subspace learning algorithm presented in Chapter 5 has two main drawbacks. The first one is related to the high computational cost of the incremental SVD method, making it infeasible for real-time applications.

The second one is related to the foreground detection method that relies on three basic steps: a) similarity function, b) weighted combination of features, and c) hard thresholding. The major limitation concerns the set of weights for each feature, that are calculated manually, making the foreground detection step unable to automatically adjust to new conditions.

Further research may consists in improving the speed of the incremental low-rank decomposition for real-time applications. the facial image data tensor is represented by R 7943×28×15×4×3 , yielding a total of 7943 pixels per image.

Tensors have been widely used in mathematics and physics for decades, and they have become very popular in psychometrics and chemometrics for multi-way data analysis [START_REF] Kolda | Tensor decompositions and applications[END_REF]. However, in the last few years, with the accelerated growth of higher-dimensional data sets, the use of tensors has expanded to other fields, such as neuroscience, data mining, signal/image/video processing, computer vision and machine learning, among the others [START_REF] Aja-Fernndez | Tensors in Image Processing and Computer Vision[END_REF][START_REF] Cichocki | Tensor decompositions for signal processing applications: From two-way to multiway component analysis[END_REF][START_REF] Cichocki | Nonnegative Matrix and Tensor Factorizations: Applications to Exploratory Multi-way Data Analysis and Blind Source Separation[END_REF][START_REF] Frolov | Tensor methods and recommender systems[END_REF][START_REF] Kolda | Tensor decompositions and applications[END_REF][START_REF] Kroonenberg | Applied multiway data analysis[END_REF][START_REF] Vasilescu | A multilinear (tensor) algebraic framework for computer graphics, computer vision, and machine learning[END_REF].

In the next sections, we introduce the basic operations of multi-linear algebra on tensors. For a deeper discussion on tensors, their properties, their operations and their applications, the reader may refer to [START_REF] Acar | Unsupervised multiway data analysis: A literature survey[END_REF][START_REF] Kolda | Tensor decompositions and applications[END_REF].

C.1 Tensor basics

As introduced in the previous section, a tensor can be defined as a multidimensional array of data 1 . Following the usual conventions found in the literature [START_REF] Kolda | Tensor decompositions and applications[END_REF][START_REF] Lathauwer | A multilinear singular value decomposition[END_REF], a tensor is denoted by calligraphic letters, e.g. X . The order of a tensor is the number of dimensions, also known as ways or modes, and an N -th order tensor of size I 1 × I 2 × . . . × I N is defined as X ∈ R I1×I2×...×I N . Each element in tensor X is addressed by X i1i2...in representing an entry at position (i 1 , i 2 , . . . , i n ), where 1 ≤ i j ≤ I j , j = 1, . . . , N . Figure C.2 shows a third-order tensor of size 5 × 6 × 6 and its modes. In the next sections, we present some of the most important operations that are usually done in tensors. Definition C.2. (Tensor matricization). Let X ∈ R I1×I2×...×I N be an N -th order tensor.

INTRODUCTION TO TENSORS

The n-mode tensor matricization, with n ∈ {1, 2, . . . , N }, denoted by X [n] , maps the tensor element (i 1 , . . . , i l , . . . , i n ) to matrix element (i l , j), where

j = 1 + N k=1 k =l (i k -1)J k and J k = k-1 m=1 m =l I m (C.2)
In essence, the tensor vectorization vec(X ) is formed by stacking the entries of X in column-major order, while in the tensor matricization the n-mode fibers are rearranged to be the columns of the matrix X [n] . Consider the following example:

C.4 Other tensor operations

Similarly to vectors and matrices, addition and subtraction between two tensors are defined in a element-wise manner. However, the multiplication between tensors is more complex. For a complete treatment of tensor multiplication, please refer to Kolda and Bader [START_REF] Kolda | Tensor decompositions and applications[END_REF]. In the thesis, we focus only on the n-mode product between a tensor and a vector or a matrix.

D.5. Conclusions

121

D.5 Conclusions

The LRSLibrary provides a wide variety of subspace learning algorithms that can be accessed by an easy-to-use GUI and command line functions. The library was designed to serve as a framework for detection and segmentation of moving objects using robust matrix-based and tensor-based factorization techniques. The experimental results in speed classification can further help the user to choose the best algorithm for his own experiments. We expect to continuously improve the LRSLibrary, adding new features and new subspace learning methods.

D.6 Acknowledgments

We would like to thank everyone who have contributed in some way, e.g. by making the algorithms publicly available, collaborating to the success of this library.

3 . 1

 31 Classification of background model initialization methods according to Bouwmans et al.[25]. The approaches presented in this chapter are in bold face. . . 3.2 Number of selected frames after the frame-selection process. . . . . . . . . . 3.3 List of MC algorithms evaluated for BM initialization. . . . . . . . . . . . . 3.4 List of TC algorithms evaluated for BM initialization. . . . . . . . . . . . . . 3.5 Scene rank and global rank of each MC method over SBI dataset. . . . . . . . 3.6 Scene rank and global rank of each tensor completion method over SBI dataset. 3.7 Comparison of the top-5 matrix completion with the top-5 tensor completion methods over SBI dataset. . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.8 Part 1 -Quantitative results of the top-10 low-rank reconstruction algorithms over SBI dataset. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.9 Part 2 -Quantitative results of the top-10 low-rank reconstruction algorithms over SBI dataset. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.10 Part 3 -Quantitative results of the top-10 low-rank reconstruction algorithms over SBI dataset. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.11 Part 4 -Quantitative results of the top-10 low-rank reconstruction algorithms over SBI dataset. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.12 Summary of the top-1 best algorithms for each scene. The columns Top-1 MC and Top-1 TC show the best algorithms among matrix and tensor completion methods, respectively. The last column highlights the winner algorithm among the top-10 best ranked low-rank recovery methods. . . . . . . . 4.1 Comparison of the proposed method and related works. . . . . . . . . . . . . 4.2 Precision, Recall and F-Measure metrics. . . . . . . . . . . . . . . . . . . . 4.3 Quantitative results on four videos of UCSD Background Subtraction Dataset. 4.4 Computational cost evaluation over four videos of UCSD Background Subtraction Dataset. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Part 1 -Quantitative and visual results with synthetic videos of the BMC dataset. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Part 2 -Quantitative and visual results with synthetic videos of the BMC dataset. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Visual comparison with real videos of the BMC dataset. . . . . . . . . . . . . 6.1 MSVS dataset: Comparison of average F-measure score in (%) with other approaches. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Execution times according to different image resolutions. . . . . . . . . . . . 7.1 Datasets for human action recognition from 3D skeletal data. . . . . . . . . . xi xii LIST OF TABLES7.2 Length of each skeletal representation before (RAW column) and after (Final column) temporal modeling. . . . . . . . . . . . . . . . . . . . . . . . . . . 92 7.3 Selected subspace clustering algorithms for evaluation on skeletal action datasets. 93 7.4 Clustering accuracy and std of five subspace clustering methods between five skeletal representations extracted from UTKinect dataset. . . . . . . . . . . . 94 7.5 Clustering accuracy and std of five subspace clustering methods between five skeletal representations extracted from Florence3D-Action dataset. . . . . . . 97 7.6 Performance comparison with state-of-the-art methods. . . . . . . . . . . . . 99 A.1 Summary of symbols used in this thesis. . . . . . . . . . . . . . . . . . . . . 107 List of Figures 1.1 Illustration of an intelligent video surveillance system. . . . . . . . . . . . . 1.2 Block diagram of the background subtraction process. . . . . . . . . . . . . . 1.3 Background/foreground separation based on low-rank plus sparse decomposition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Example of a low-rank approximation from an input matrix contaminated by Gaussian noise. From left to right: the input matrix A, its rank-1 approximation and its rank-3 approximation. . . . . . . . . . . . . . . . . . . . . . . . 2.2 Application of low-rank approximation to the background model estimation in a sequence of images. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Example of moving vehicles segmentation after background model estimation from low-rank approximation. . . . . . . . . . . . . . . . . . . . . . . . 2.4 Example of low-rank matrix completion for background model estimation. . . 2.5 RPCA via decomposition in low-rank and sparse matrices. . . . . . . . . . . 2.6 Background/foreground separation by RPCA via PCP. . . . . . . . . . . . . 2.7 Visual comparison of foreground segmentation between PCP and Stable PCP for dynamic background. From left to right: input video, RPCA via PCP, and RPCA via Stable PCP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.8 Illustration of three typical types of errors in the matrix data (from Liu et al. [121]): a) noise, b) random corruptions, and c) sample-specific corruptions. 2.9 Turning sparse point trajectories into dense regions. Figure from Ochs and Brox [149]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.10 Families of tensor methods for multi-way data analysis. Adapted from Acar and Yener [3]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.

3 . 1

 31 Proposed approach to background model initialization: given an input image, a joint motion-detection and frame-selection operation is applied. Next, a low-rank reconstruction process recovers the background model from the partially observed data. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Illustration of the frame-selection operation. . . . . . . . . . . . . . . . . . . xiii xiv LIST OF FIGURES 3.3 Illustration of the low-rank reconstruction process. From top to bottom: matrix-based and tensor-based completion process. From left to right: a) the selected frames, b) the moving regions are represented by non-observed entries (black pixels), c) the moving regions filled with zeros, and d) the recovered data after low-rank reconstruction process. . . . . . . . . . . . . . . 38 3.4 Part 1 -Visual comparison for the background model initialization over the first 7 scenes of the SBI dataset. From top to bottom: 1) example of input frame, 2) background model ground truth, and background model results for the top 10 best ranked low-rank recovery algorithms: 3) LRGeomCG, 4) LMaFit, 5) RMAMR, 6) MC-NMF, 7) TMac, 8) IALM, 9) SPC, 10) t-SVD, 11) t-TNN, and 12) FaLRTC. . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.5 Part 2 -Visual comparison for the background model initialization over the last 7 scenes of the SBI dataset. From top to bottom: 1) example of input frame, 2) background model ground truth, and background model results for the top 10 best ranked low-rank recovery algorithms: 3) LRGeomCG, 4) LMaFit, 5) RMAMR, 6) MC-NMF, 7) TMac, 8) IALM, 9) SPC, 10) t-SVD, 11) t-TNN, and 12) FaLRTC. . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.1 Block diagram of the proposed approach. Given an input image (a), a saliency detector is applied (b). Next, the confidence map (c) is built by normalizing the saliency map, while the shape constraint (d) is built by thresholding this one, and (e) the foreground mask obtained by thresholding the RPCA sparse component. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.2 Visual comparison of background subtraction results over three scenes of UCSD dataset. From top to bottom: surfers, boats and birds. From left to right: (a) input frame, (b) saliency map generated by BMS, (c) ground truth, (d) proposed approach, (e) 3WD, and (f) RMAMR. The top 3 best algorithms (organized by rank) from Table 4.3 were chosen. . . . . . . . . . . . . . . . 64 4.3 Visual results of SCM-RPCA over three scenes of MarDT dataset. From left

68 6 . 1

 61 Performance of reconstructed low-rank tensor. . . . . . . . . . . . . . . . . . 81 6.2 Visual comparison of background subtraction results over three scenes of the MSVS dataset. From left to right: (a) input RGB image, (b) ground truth, (c) proposed approach, (d) BRTF, (e) HORPCA, and (f) CP-ALS. . . . . . . . . 81 6.3 Visual results of the proposed method on each RGB and multispectral band. From top to bottom: input image, low-rank component, sparse component, and the foreground mask. From left to right: RGB image, set of 6 visible, and 1 NIR spectrum are shown in each column separately. . . . . . . . . . . 82

Figure 1 . 1 :Figure 1 . 2 :

 1112 Figure 1.1: Illustration of an intelligent video surveillance system.

Figure 1 . 3 :•

 13 Figure 1.3: Background/foreground separation based on low-rank plus sparse decomposition.

Figure 2 . 1 :

 21 Figure 2.1: Example of a low-rank approximation from an input matrix contaminated by Gaussian noise. From left to right: the input matrix A, its rank-1 approximation and its rank-3 approximation.

1 A

 1 Input matrix (full rank)Low-rank approximation (a) Example of background model estimation through low-rank approximation. values (b) The influence of the rank approximation in the background model.

Figure 2 . 2 :

 22 Figure 2.2: Application of low-rank approximation to the background model estimation in a sequence of images.

Figure 2 . 3 :

 23 Figure 2.3: Example of moving vehicles segmentation after background model estimation from low-rank approximation.

Figure 2 . 4 :

 24 Figure 2.4: Example of low-rank matrix completion for background model estimation.

Figure 2 .Figure 2 . 5 :

 225 Figure 2.5: RPCA via decomposition in low-rank and sparse matrices.

Figure 2 . 6 :

 26 Figure 2.6: Background/foreground separation by RPCA via PCP.

Figure 2 . 7 :

 27 Figure 2.7: Visual comparison of foreground segmentation between PCP and Stable PCP for dynamic background. From left to right: input video, RPCA via PCP, and RPCA via Stable PCP.

Figure 2 . 8 :

 28 Figure 2.8: Illustration of three typical types of errors in the matrix data (from Liu et al. [121]): a) noise, b) random corruptions, and c) sample-specific corruptions.

Figure 2 . 9 :

 29 Figure 2.9: Turning sparse point trajectories into dense regions. Figure from Ochs and Brox [149].

Figure 2 . 10 :

 210 Figure 2.10: Families of tensor methods for multi-way data analysis. Adapted from Acar and Yener [3].

Figure 2 . 11 :

 211 Figure 2.11: Illustration of a Tucker model for a third-order tensor.A third-order tensor is decomposed as the sum of a low-rank tensor (a core tensor multiplied by its factor matrices) and a residual tensor. Image adapted from[START_REF] Acar | Unsupervised multiway data analysis: A literature survey[END_REF][START_REF] Kolda | Tensor decompositions and applications[END_REF].

Figure 2 . 12 :

 212 Figure 2.12: Illustration of the CP decomposition of a third-order tensor as the sum of rank-1 tensors u r1 • u r2 • u r3 for r ∈ {1, 2, . . . , R}. Image adapted from [3, 99].

Figure 2 . 13 :

 213 Figure 2.13: Extending robust principal component analysis on a third-order tensor.

Figure 3 . 1 :

 31 Figure 3.1: Proposed approach to background model initialization: given an input image, a joint motion-detection and frame-selection operation is applied. Next, a low-rank reconstruction process recovers the background model from the partially observed data.

Figure 3 . 2 : 4 Figure 3 . 3 :

 32433 Figure 3.2: Illustration of the frame-selection operation.

  A second approach is to use the CP model, introduced in Chapter 2 (see Section 2.4.1.2), resulting in the following optimization problem: minimize L 1 2

Table 3 . 6 :Table 3 . 7 : 10 M

 363710 Scene rank and global rank of each tensor completion method over SBI dataset. Comparison of the top-5 matrix completion with the top-5 tensor completion methods over SBI dataset. Matrix-based completion.T Tensor-based completion.

Figure 3 . 4 :

 34 Figure 3.4: Part 1 -Visual comparison for the background model initialization over the first 7 scenes of the SBI dataset. From top to bottom: 1) example of input frame, 2) background model ground truth, and background model results for the top 10 best ranked low-rank recovery algorithms: 3) LRGeomCG, 4) LMaFit, 5) RMAMR, 6) MC-NMF, 7) TMac, 8) IALM, 9) SPC, 10) t-SVD, 11) t-TNN, and 12) FaLRTC.

Figure 3 . 5 :

 35 Figure 3.5: Part 2 -Visual comparison for the background model initialization over the last 7 scenes of the SBI dataset. From top to bottom: 1) example of input frame, 2) background model ground truth, and background model results for the top 10 best ranked low-rank recovery algorithms: 3) LRGeomCG, 4) LMaFit, 5) RMAMR, 6) MC-NMF, 7) TMac, 8) IALM, 9) SPC, 10) t-SVD, 11) t-TNN, and 12) FaLRTC.

1 58 DOUBLEFigure 4 . 1 :

 5841 Figure 4.1: Block diagram of the proposed approach. Given an input image (a), a saliency detector is applied (b). Next, the confidence map (c) is built by normalizing the saliency map, while the shape constraint (d) is built by thresholding this one, and (e) the foreground mask obtained by thresholding the RPCA sparse component.

59

 59

60 DOUBLE||L|| * +λ 1 2 F

 6012 Consider a sequence of n gray-scale images (frames) F 1 . . . F n captured from a static camera, that is, F ∈ R I1×I2 where I 1 and I 2 denotes the frame resolution (rows by columns). All frames are vectorized into a observation matrix A = [vec(F 1 ) . . . vec(F n )], where A ∈ R m×n and m = (I 1 × I 2 ). The decomposition is formulated as: minimize L,S,E ||L|| * +λ 1 ||Π(S)|| 1 +λ 2 ||E|| 2 F , s.t. A = L + W • S + E (4.1) ||Π(S)|| 1 +λ 2 ||E|| subject to A = L + S + E Ye et al. (2015) [241] minimize L,S,E

Figures 4 .

 4 Figures 4.2and 4.3 show the visual results for background subtraction task in the UCSD andMarDT datasets, respectively. The true positive pixels (T P ) are in white, true negative pixels (T N ) in black, false positive pixels (F P ) in red and false negative pixels (F N ) in green. Is important to note that in the UCSD scenes we have used the original spatial saliency map provided by BMS, while for the MarDT scenes we have subtracted its temporal median due to the high saliency from the buildings around the river. The quantitative results in Table4.3 show that the SCM-RPCA outperforms the previous methods, with the highest average Fmeasure over the selected video sequences. Each metric is described in Table4.2. As can be seen from Figures 4.2 and 4.3, and Table4.3, the combination with confidence map and shape constraint can reduce the amount of false positive pixels.

Figure 4 . 2 :

 42 Figure 4.2: Visual comparison of background subtraction results over three scenes of UCSD dataset. From top to bottom: surfers, boats and birds. From left to right: (a) input frame, (b) saliency map generated by BMS, (c) ground truth, (d) proposed approach, (e) 3WD, and (f) RMAMR. The top 3 best algorithms (organized by rank) from Table 4.3 were chosen.

Figure 4 . 3 :

 43 Figure 4.3: Visual results of SCM-RPCA over three scenes of MarDT dataset. From left to right: (a) input frame, (b) saliency map with its temporal median subtracted (due to the high saliency from the buildings around the river), (c) low-rank component, (d) sparse component, (e) foreground mask, and (f) ground truth.

68 INCREMENTALFigure 5 . 1 :

 6851 Figure 5.1: Block diagram of the proposed approach.In the step (a), the last N frames from a streaming video are stored in a sliding block or tensor A t . Next, a feature extraction process is done at step (b) and the tensor A t is transformed in another tensor T t (step (c)) . In (d), an incremental higher-order singular value decomposition (iHOSVD) is applied in the tensor T t resulting in a low-rank tensor L t . Finally, in the step (e) a foreground detection method is applied for each new frame to segment the moving objects.

3 :Figure 6 . 1 :

 361 Figure 6.1: Performance of reconstructed low-rank tensor.

Figure 6 . 2 :

 62 Figure 6.2: Visual comparison of background subtraction results over three scenes of the MSVS dataset. From left to right: (a) input RGB image, (b) ground truth, (c) proposed approach, (d) BRTF, (e) HORPCA, and (f) CP-ALS.

Figure 6 . 3 :

 63 Figure 6.3: Visual results of the proposed method on each RGB and multispectral band. From top to bottom: input image, low-rank component, sparse component, and the foreground mask. From left to right: RGB image, set of 6 visible, and 1 NIR spectrum are shown in each column separately.

Figure 6 . 4 :

 64 Figure 6.4: FG results on 1 st and 2 nd videos of the MSVS dataset. (a) input image, (b) ground truth, (c) results for only RGB, (d) for only 6 visible bands, and (e) for 1 NIR spectral band alone.

Figure 6 . 5 :

 65 Figure 6.5: FG results on the 3 rd video of the MSVS dataset (red = FP). From top to bottom: basis initialization with UDRN and BRP. From left to right, the FG mask at: (a) frame 1, (b) frame 5, (c) frame 10, (d) frame 15, and (e) frame 20. Size HORPCA CP-ALS BRTF Proposed 160 × 120 00:01:35 00:00:40 00:00:22 00:00:04 320 × 240 00:04:56 00:02:09 00:03:50 00:00:12

Figure 7 . 1 :

 71 Figure 7.1: Proposed framework for robust subspace clustering of human activities through skeletal data.

Figure 7 . 2 :

 72 Figure 7.2: Illustration of the subspace clustering framework based on sparse and low-rank representation approaches for building the affinity matrix.

Figure 7 . 3 :

 73 Figure 7.3: Steps behind the construction of the action representation matrix.

Figure 7 . 4 :

 74 Figure 7.4: Temporal modeling procedure applied in the skeletal representation to deal with rate variations, temporal misalignment, and noise.

Figure 7 . 5 :Figure 7 . 6 :

 7576 Figure 7.5: Feature embedding visualizations of AJP skeletal representation before (left) and after (right) temporal modeling procedure from UTKinect actions using t-SNE.

Figure C. 2 :

 2 Figure C.2: Illustration of a third-order tensor X ∈ R 5×6×6 and its entries.

  Figure C.3: Decomposing a third-order tensor into fibers and slices.

  -1)J k and J k =

Example C. 1 .

 1 (Tensor vectorization and matricization) Let a third-order tensor X ∈ R 2×3×2 formed by the following two frontal slices X :

  .[START_REF] Bouwmans | Background Modeling and Foreground Detection for Video Surveillance[END_REF] Equation(2.26) represents the Sum of Nuclear Norms (SNN)[START_REF] Liu | Tensor completion for estimating missing values in visual data[END_REF] also referred to as tensor trace norm. So, replacing the rank(.) by SNN and card(.) by 1 -norm in Equation (2.24), the tensor RPCA can be described by the following optimization problem:

		N
	minimize L,S	n=1

Table 3 . 1 :

 31 Classification of background model initialization methods according to Bouwmans et al.[25]. The approaches presented in this chapter are in bold face.

	Type of methods	Related works
	Temporal Statistics	Mean, Color Median, MoG [186, 262], KNN [263], BE-AAPSA [163]
	Subintervals of Stable Intensity	WS2006 [220], IMBS-MT [21], LaBGen [106]
	Model Completion	RSL2011 [166]
	Optimal Labeling	Photomontage [4]
	Subspace Estimation

Table 3 . 2 :

 32 Number of selected frames after the frame-selection process.

	#	Sequence	Frames Selected Reduction	τ
	1 Board 2 Candela m1.10 3 CAVIAR1 4 CAVIAR2 5 CaVignal 6 Foliage 7 Hall&Monitor 8 HighwayI 9 HighwayII 10 HumanBody2 11 IBMtest2 12 People&Foliage 13 Snellen 14 Toscana	228 350 610 460 258 394 296 440 500 740 90 341 321 6	64 84 88 83 65 68 94 59 49 86 33 55 70 6	71.93% 0.125 76.00% 0.100 85.57% 0.100 81.96% 0.125 74.81% 0.125 82.74% 0.600 68.24% 0.075 86.59% 0.100 90.20% 0.075 88.38% 0.050 63.33% 0.100 83.87% 0.100 78.19% 0.125 0.00% -

[1, . . . , I 2 ]

Table 3 . 3 :

 33 List of MC algorithms evaluated for BM initialization.

	Type	Method	Main techniques	Author(s)
	RM	IALM RMAMR	Augmented Lagrangian Lin and Wei (2010) [118] Augmented Lagrangian Ye et al. (2015) [241]
		SVP	Hard thresholding	Jain et al. (2010) [87]
		OptSpace	Grassmannian	Keshavan et al. (2010) [96]
		MC-NMF	Non-negative factors	Xu et al. (2012) [237]
	MF	LMaFit ScGrassMC	Alternating Grassmannian	Wen et al. (2012) [227] Ngo and Saad (2012) [148]
		LRGeomCG Riemannian	Vandereycken (2013) [209]
		GROUSE	Online algorithm	Balzano and Wright (2013) [15]
		OR1MP	Matching pursuit	Wang et al. (2015) [224]
		GoDec	Randomized	Zhou and Tao (2011) [256]
		SSGoDec	Randomized	Zhou and Tao (2011) [256]
		GreGoDec	Randomized	Zhou and Tao (2013) [258]
	RM -Rank Minimization
	MF -Matrix Factorization

to efficiently optimize any smooth function over M r .

Table 3 . 4 :

 34 List of TC algorithms evaluated for BM initialization.

	Type	Method	Main techniques	Author(s)
	CP	NCPC BCPF	Non-negative factors Bayesian CP Factorization Zhao et al. (2015) [252] Xu and Yin (2013) [236]
		TenALS	Alternating	Jain et al. (2014) [88]
		SPC	Smooth PARAFAC	Yokota et al. (2016) [243]
		HoRPCA-IALM Augmented Lagrangian	Goldfarb and Qin (2014) [72]
		FaLRTC	Trace norm	Liu et al. (2013) [122]
		geomCG	Riemannian	Kressner et al. (2013) [100]
	TD	TMac t-SVD	Alternating Fourier domain	Xu et al. (2015) [235] Zhang et al. (2014) [251]
		t-TNN	Nuclear norm	Hu et al. (2015) [84]
	CP -CANDECOMP/PARAFAC decomposition.
	TD -Tucker decomposition / HOSVD / N-mode SVD.

Table 3 . 5 :

 35 Scene rank and global rank of each MC method over SBI dataset.

	Method

Table 3 . 8 :

 38 Part 1 -Quantitative results of the top-10 low-rank reconstruction algorithms over SBI dataset.

	CaVignal	Method AGE pEPs pCEPS MSSSIM PSNR CQM Scene Rank	MLRGeomCG 5.4839 6.4118 3.9890 0.9111 28.3288 52.9853 1 5.4853 MLMaFit 6.4154 3.9890 0.9111 28.3273 52.9850 2 5.4959 MRMAMR 6.4301 3.9890 0.9111 28.3100 53.0123 3 T TMac 5.4979 6.5074 4.0625 0.9109 28.2877 53.0188 4 5.9824 MIALM 7.1875 3.8272 0.9002 27.7931 50.7009 5 5.9749 MMC-NMF 8.1949 5.4890 0.8997 27.4603 52.8197 6 T FaLRTC 7.1125 8.3309 5.4081 0.8876 26.9316 47.6830 7 T t-SVD 7.1949 8.3676 5.4669 0.8860 26.8741 47.8262 8 T SPC 7.1215 8.6176 5.6581 0.8846 26.8208 51.0394 9 T t-TNN 7.2519 8.4743 5.5184 0.8851 26.8285 47.4856 10	Foliage	Method AGE pEPs CQM Scene Rank pCEPS MSSSIM PSNR	1 2 0.9535 23.9826 39.0643 0.9535 3 23.9744 39.0737 0.9532 23.9134 39.1203 4 0.9528 23.8960 38.4825 MLRGeomCG 11.6932 20.8924 14.9861 MLMaFit 11.7062 20.9271 15.0417 MRMAMR 11.8031 21.1458 15.2222 MIALM 5 0.9498 23.7072 38.7549 11.8963 21.5417 15.6215 T TMac 6 0.9114 21.4930 36.5547 12.0335 21.9826 15.9861 MMC-NMF 7 0.9033 21.4422 33.9587 15.1040 25.4340 19.5069 T t-SVD 8 0.8937 21.0282 32.9964 16.2432 29.1424 22.2674 T SPC 9 0.8734 20.5579 32.2173 17.1535 33.2743 22.7951 T t-TNN 10 0.8197 19.2060 30.8085 18.5811 34.3993 24.7222 T FaLRTC 22.1739 45.7639 31.2569	MMatrix-based completion.
	Board	Method AGE pEPs pCEPS MSSSIM PSNR CQM Scene Rank	MIALM 16.0145 29.0732 22.6921 0.6704 21.2760 45.3854 1 18.8825 35.9543 27.5213 MLMaFit 0.6754 20.1326 43.7285 2 MLRGeomCG 18.8829 35.9543 27.5213 0.6754 20.1325 43.7282 3 18.9599 36.1311 27.6463 MRMAMR 0.6752 20.1081 43.6978 4 T TMac 19.0408 36.2409 27.8293 0.6726 20.0735 43.7571 5 20.5415 39.8140 31.5610 MMC-NMF 0.6382 19.5552 43.3572 6 T SPC 24.2711 46.6494 37.8201 0.6181 18.4161 42.9340 7 T t-SVD 24.6558 47.7927 39.5244 0.6183 18.3139 43.1752 8 T t-TNN 24.8947 48.3994 40.0396 0.6162 18.2481 43.2070 9 T FaLRTC 25.0577 48.6067 40.3171 0.6165 18.1905 43.1227 10	Candela m1.10	Method AGE pEPs pCEPS MSSSIM PSNR CQM Scene Rank	T SPC 1.6942 0.2180 T FaLRTC 1.8368 0.5455 T t-SVD 1.8697 0.5988 T t-TNN 1.8944 0.6185 MLRGeomCG 1.9037 0.6579 1.8950 MRMAMR 0.6609 1.9144 MIALM 0.6688 1.9680 MLMaFit 0.8079 2.0237 MMC-NMF T TMac 0.9746 2.0456 1.0150 0.1263 0.9930 0.3630 0.9917 0.4745 0.9918 0.4824 0.9916 0.4991 0.9912 0.5090 0.9912 0.5060 0.9911 0.6165 0.9903 0.7517 0.9892 0.7842 0.9888 39.4553 51.9223 37.6151 51.9974 34.8058 48.0497 34.5269 47.1672 33.8805 45.0354 33.7306 44.9021 33.8414 44.9827 33.2250 44.5333 32.7856 44.2348 32.5507 43.7920 1 2 3 4 5 6 7 8 9 10

T Tensor-based completion.

Table 3 . 9 :

 39 Part 2 -Quantitative results of the top-10 low-rank reconstruction algorithms over SBI dataset.

	HallAndMonitor	Method AGE pEPs pCEPS MSSSIM PSNR CQM Scene Rank	T t-TNN 2.0417 0.1716 0.0000 0.9938 38.2894 46.4244 1 T t-SVD 2.0469 0.1847 0.0000 0.9938 38.2084 46.3998 2 MLRGeomCG 2.0476 0.2237 0.0000 0.9938 38.0243 46.3813 3 2.0476 0.2237 MIALM 0.0000 0.9938 38.0242 46.3813 4 2.0417 0.2261 MRMAMR 0.0000 0.9938 38.0214 46.3837 4 2.0498 0.2249 MLMaFit 0.0000 0.9938 37.9193 46.3371 6 T TMac 2.0599 0.2415 0.0000 0.9937 37.5664 46.2214 7 2.0640 0.2415 MMC-NMF 0.0000 0.9937 37.4073 46.1720 8 T FaLRTC 2.2531 0.4025 0.0012 0.9925 36.4659 44.1228 9 T SPC 2.2763 0.5303 0.0024 0.9927 35.8033 43.8510 10	HighwayI	Method AGE CQM Scene Rank pEPs pCEPS MSSSIM PSNR	1 2 0.9779 36.2748 58.2536 0.9779 3 36.2808 58.2359 0.9777 36.2798 58.2441 MRMAMR 2.6453 0.1992 0.0130 MLRGeomCG 2.6535 0.2018 0.0130 MIALM 4 0.9779 5 36.2687 58.2344 0.9777 36.1917 58.2417 2.6598 0.1953 0.0130 MLMaFit 2.6562 0.2018 0.0130 T TMac 6 0.9726 34.9387 57.8914 2.6788 0.1992 0.0130 MMC-NMF 7 0.9643 32.4894 58.0333 2.9940 0.5677 0.1328 T t-SVD 8 0.9655 33.0111 57.8709 4.2271 0.8138 0.3516 T SPC 9 0.9624 31.7239 57.8150 3.8228 1.2982 0.8568 T FaLRTC 10 0.9611 31.6223 57.9345 4.8294 0.8294 0.3516 T t-TNN 4.7145 1.2474 0.6849	MMatrix-based completion. T Tensor-based completion.
	CAVIAR1	Method AGE pEPs pCEPS MSSSIM PSNR CQM Scene Rank	MLMaFit 5.6735 6.6274 5.4830 0.9120 28.1792 51.1680 1 MLRGeomCG 5.6735 6.6274 5.4830 0.9120 28.1790 51.1680 2 5.6641 6.6508 MRMAMR 5.5094 0.9121 28.1736 51.1897 3 5.6737 6.6284 MMC-NMF 5.4830 0.9120 28.1787 51.1680 4 T TMac 5.6945 6.7017 5.5593 0.9116 28.1425 51.1681 5 T SPC 5.8531 7.2815 6.0628 0.9093 27.9196 51.1901 6 T FaLRTC 5.8699 7.3008 6.0801 0.9093 27.9042 51.1497 7 T t-SVD 5.8736 7.3222 6.0801 0.9092 27.9014 51.1434 8 T t-TNN 5.8792 7.3222 6.0801 0.9092 27.8956 51.1384 9 6.7411 10.0464 7.8440 MIALM 0.8802 26.5992 50.7632 10	CAVIAR2	Method AGE pEPs pCEPS MSSSIM PSNR CQM Scene Rank	MLMaFit 1.1823 MLRGeomCG 1.1822 0.3265 0.3265 1.1823 MMC-NMF 0.3265 1.1925 0.3276 MRMAMR T SPC T TMac T FaLRTC T t-SVD T t-TNN 1.2136 0.3845 1.1877 0.3286 1.2923 0.3845 1.2896 0.3855 1.3058 0.3866 1.4858 0.6460 MIALM 0.1038 0.9971 0.1038 0.9971 0.1038 0.9971 0.1048 0.9971 0.1312 0.9968 0.1058 0.9970 0.1343 0.9967 0.1363 0.9967 0.1363 0.9967 0.2431 0.9945 39.8982 59.1772 39.8978 59.1772 39.8978 59.1772 39.8581 59.1748 39.5137 59.1832 39.8569 59.1736 39.2267 59.1819 39.2218 59.1766 39.1549 59.1797 36.7150 58.4525 1 2 2 4 5 6 7 8 8 10

Table 3 .

 3 10: Part 3 -Quantitative results of the top-10 low-rank reconstruction algorithms over SBI dataset.

	PeopleAndFoliage	Method AGE pEPs pCEPS MSSSIM PSNR CQM Scene Rank	MLRGeomCG 29.2393 57.7812 48.2135 0.8332 16.8399 32.1823 1 29.2520 57.8125 48.2539 MLMaFit 0.8331 16.8367 32.1796 2 29.5094 57.4115 MMC-NMF 47.6497 0.8346 16.7286 32.1034 3 T TMac 29.4402 57.1888 47.6719 0.8233 16.6676 32.1267 4 29.3027 57.9049 48.3906 MRMAMR 0.8329 16.8253 32.1624 5 30.6975 58.2839 49.0560 MIALM 0.8011 16.2927 31.7307 6 T SPC 32.2676 59.8932 51.2461 0.7850 15.8266 31.8834 7 T t-SVD 32.7286 60.1901 51.9622 0.7755 15.7204 31.7717 8 T t-TNN 33.1854 60.4258 52.3255 0.7724 15.6211 31.7342 9 T FaLRTC 33.7695 61.0026 52.9258 0.7620 15.4770 31.6863 10	Snellen	Method AGE pEPs CQM Scene Rank pCEPS MSSSIM PSNR	1 2 0.9250 18.6585 42.1307 0.9249 18.6457 42.1328 MLRGeomCG 24.4846 50.4340 42.8337 MLMaFit 3 0.9245 18.6077 42.1378 4 0.9206 18.5311 41.8552 24.5473 50.6318 42.9977 MRMAMR 24.6804 50.9790 43.3449 T TMac 5 0.9170 17.9515 41.5184 24.8743 51.9965 44.3528 MMC-NMF 6 0.8821 17.3378 39.2210 26.8535 58.6082 51.6541 MIALM 7 0.8854 17.2301 39.8213 28.5543 59.2930 52.1943 T t-SVD 8 0.8779 17.1026 37.3224 28.9166 58.9169 53.2407 T SPC 9 0.8722 16.8427 38.3602 29.4769 59.9489 53.0478 T t-TNN 10 0.8258 15.7664 35.3544 31.3521 65.6877 59.1001 T FaLRTC 36.3661 74.2911 66.3725	MMatrix-based completion.
	HighwayII	Method AGE pEPs pCEPS MSSSIM PSNR CQM Scene Rank	MIALM 2.7526 0.3555 0.0026 0.9908 35.3406 46.3161 1 MLRGeomCG 2.7526 0.3555 0.0026 0.9908 35.3406 46.3161 1 2.7528 MLMaFit 0.3555 0.0026 0.9908 35.3361 46.3122 3 2.7687 MRMAMR 0.3555 0.0026 0.9908 35.3015 46.3119 4 T TMac 2.7697 0.3763 0.0039 0.9908 35.2287 46.2181 5 2.8791 0.3672 0.0026 MMC-NMF 0.9901 34.9279 46.1025 6 T t-SVD 3.8271 0.4596 0.0299 0.9864 33.0601 46.4679 7 T SPC 3.4289 0.5091 0.0091 0.9878 33.5406 46.1876 8 T t-TNN 4.1262 0.5013 0.0299 0.9850 32.4600 46.2045 9 T FaLRTC 4.1368 0.5286 0.0247 0.9850 32.4087 46.2637 10	HumanBody2	Method AGE pEPs pCEPS MSSSIM PSNR CQM Scene Rank	MLMaFit 5.7627 4.6510 MLRGeomCG 5.7621 4.6497 2.4414 0.9788 2.4414 0.9788 5.7661 4.6628 2.4505 MRMAMR T TMac 0.9787 5.8044 4.7292 2.4583 0.9786 6.1841 5.3919 2.9102 MMC-NMF 0.9760 6.5515 5.6836 2.7969 MIALM T SPC T t-SVD T t-TNN T FaLRTC 0.9730 6.8470 6.2174 3.3984 0.9715 7.0378 6.2409 3.4922 0.9688 7.2657 6.5391 3.6341 0.9667 7.3432 6.6953 3.7344 0.9670 28.7047 40.1984 28.7017 40.1985 28.6899 40.2114 28.6019 40.2122 28.1319 39.7334 27.6232 39.1328 27.2413 38.4319 27.1468 38.2726 26.9194 37.8676 26.8229 37.5329 1 2 3 4 5 6 7 8 9 10

T Tensor-based completion.

Table 3 .

 3 11: Part 4 -Quantitative results of the top-10 low-rank reconstruction algorithms over SBI dataset.

	Toscana	Method AGE pEPs CQM Scene Rank pCEPS MSSSIM PSNR	1 2 0.8959 24.2914 36.3206 0.9077 24.5368 38.5918 3 0.8911 24.3671 36.2805 MLRGeomCG 7.3009 11.8569 8.4394 T SPC 8.1087 12.9096 8.8235 MMC-NMF 4 0.8959 24.2800 36.3043 7.6612 11.5710 7.6317 MRMAMR 5 0.9096 24.3111 38.1849 7.3381 11.9000 8.4723 T t-SVD 5 0.9101 7 24.2766 38.2244 0.8958 24.2609 36.2690 8.4022 14.1319 10.2058 T t-TNN 8.6326 13.9075 9.7881 T TMac 8 0.9051 23.8897 38.1260 7.3742 12.0163 8.5815 T FaLRTC 9 0.8887 23.0985 34.9645 9.4138 15.6027 11.3146 MIALM 10 0.7486 16.8984 25.6812 9.5171 16.8137 13.3448 MLMaFit 23.1736 42.7019 38.5535	MMatrix-based completion.
	IBMtest2	Method AGE pEPs pCEPS MSSSIM PSNR CQM Scene Rank	MLMaFit 3.6413 1.4544 0.6081 0.9868 MLRGeomCG 3.6413 1.4544 0.6081 T TMac 0.9868 3.6575 1.4831 0.6289 0.9868 3.6715 1.4674 0.6146 MRMAMR 0.9868 4.0120 2.4844 1.4427 MMC-NMF T SPC T t-SVD T t-TNN T FaLRTC 0.9814 4.3337 2.7161 1.6836 0.9810 4.5889 2.8060 1.9362 0.9780 4.7017 2.9089 2.0495 0.9772 4.7449 3.0091 2.0404 0.9776 5.7583 5.2370 2.3164 MIALM 0.9462 32.8931 44.9527 32.8930 44.9516 32.8424 44.9660 32.8495 44.9352 31.3615 43.9484 30.9463 42.2799 30.4336 42.3460 30.2330 41.8205 30.1724 41.0093 26.1977 38.9603 1 2 3 4 5 6 7 8 9 10

T Tensor-based completion.

Table 3 .

 3 12: Summary of the top-1 best algorithms for each scene. The columns Top-1 MC and Top-1 TC show the best algorithms among matrix and tensor completion methods, respectively. The last column highlights the winner algorithm among the top-10 best ranked low-rank recovery methods.

	Scenes	Top-1 MC Top-1 TC	Scene Top-1
	Board Candela m1.10 CAVIAR1 CAVIAR2 CaVignal Foliage HallAndMonitor HighwayI HighwayII HumanBody2 IBMtest2 PeopleAndFoliage LRGeomCG TMac IALM TMac LRGeomCG SPC LMaFit TMac LRGeomCG TMac LRGeomCG TMac GROUSE TMac LRGeomCG t-TNN RMAMR TMac IALM TMac LRGeomCG TMac LMaFit TMac Snellen LRGeomCG TMac Toscana LRGeomCG SPC	M IALM T SPC M LMaFit M LRGeomCG M LRGeomCG M LRGeomCG T t-TNN M RMAMR M IALM M LRGeomCG M LMaFit M LRGeomCG M LRGeomCG M LRGeomCG
	M Matrix-based completion. T Tensor-based completion.

Table 4 . 3 :

 43 Quantitative results on four videos of UCSD Background Subtraction Dataset.

		Birds	Surfers	Boats	Ocean	Rank
	PCP	Re 0.842 0.094 0.170 0.754 0.075 0.137 0.814 0.100 0.178 0.748 0.115 0.200 P r F 1 Re P r F 1 Re P r F 1 Re P r F 1	Avg.F 1 0.171
	Lag-SPCP-QN 0.413 0.322 0.362 0.244 0.282 0.261 0.405 0.215 0.281 0.484 0.313 0.380	0.321
	RMAMR	0.823 0.229 0.358 0.775 0.248 0.376 0.816 0.230 0.359 0.777 0.175 0.286	0.345
	3WD	0.586 0.604 0.595 0.538 0.405 0.462 0.673 0.473 0.556 0.563 0.337 0.422	0.509
	SCM-RPCA	0.573 0.638 0.604 0.518 0.565 0.541 0.663 0.550 0.602 0.457 0.544 0.497	0.561

Table 4 . 4 :

 44 Computational cost evaluation over four videos of UCSD Background Subtraction Dataset.

	PCP Lag-SPCP-QN RMAMR 3WD SCM-RPCA	Birds (242 × 156 × 71) (344 × 224 × 41) (344 × 224 × 31) (316×196×176) Surfers Boats Ocean Iter Time * Iter Time * Iter Time * Iter Time * + 100 27.29 + 100 21.19 + 100 18.47 + 100 110.53 29 10.12 53 16.27 39 10.01 18 29.49 34 10.63 35 13.09 33 11.44 35 44.22 30 4.53 26 4.28 31 4.06 42 29.96 29 4.59 25 4.37 27 3.82 43 33.02

Table 5 . 1 :

 51 Part 1 -Quantitative and visual results with synthetic videos of the BMC dataset.

		IMTSL
	Visual Results	GT
		Image
	Scenes Method Recall Precision F-measure	Street	112 GRASTA 0.725 IMTSL 0.700 0.945 0.980 0.981 BLWS 0.700 0.818 0.817 0.817	IMTSL 0.692 0.845 0.761	212 GRASTA 0.787 BLWS 0.786 0.847 0.847 0.816 0.816	IMTSL 0.566 0.831 0.673	312 GRASTA 0.695 0.965 0.807 0.812 BLWS 0.697 0.971	IMTSL 0.637 0.838 0.723	412 GRASTA 0.787 BLWS 0.785 0.843 0.848 0.814 0.815	IMTSL 0.652 0.893 0.753	512 GRASTA 0.669 BLWS 0.664 0.960 0.966 0.789 0.787

Table 5 . 2 :

 52 Part 2 -Quantitative and visual results with synthetic videos of the BMC dataset.

		IMTSL
	Visual Results	GT
		Image
	Scenes Method Recall Precision F-measure	Rotary	122 GRASTA 0.748 IMTSL 0.680 0.956 0.902 0.839 0.776	BLWS 0.663 0.921 0.771	222 GRASTA 0.649 IMTSL 0.637 0.913 0.548 0.759 0.589	BLWS 0.633 0.560 0.594	322 GRASTA 0.619 BLWS 0.603 0.927 IMTSL 0.555 0.530 0.538 0.694 0.571 0.569	422 GRASTA 0.623 BLWS 0.620 0.942 IMTSL 0.548 0.778 0.775 0.693 0.692 0.689	522 GRASTA 0.791 0.793 BLWS 0.932 IMTSL 0.677 0.714 0.711 0.784 0.751 0.750	Average IMTSL --0.749 GRASTA --0.618	BLWS --0.742

Table 5 . 3 :

 53 Visual comparison with real videos of the BMC dataset.

Table 6 . 1 :

 61 MSVS dataset: Comparison of average F-measure score in (%) with other approaches. ALS RGB 58.69 RGB 71.25 RGB 51.32 RGB 60.21 RGB 49.35 RGB 58.16 MSB 71.61 MSB 83.50 MSB 68.54 MSB 78.63 MSB 66.97 MSB 73.85 HORPCA RGB 63.23 RGB 78.52 RGB 55.69 RGB 67.56 RGB 58.80 RGB 64.76 MSB 80.65 MSB 84.79 MSB 68.12 MSB 77.56 MSB 74.47 MSB 77.11 BRTF RGB 68.56 RGB 79.21 RGB 63.56 RGB 73.22 RGB 62.51 RGB 70.32 MSB 85.30 MSB 89.63 MSB 68.11 MSB 84.65 MSB 77.91 MSB 82.76 Proposed RGB 78.63 RGB 85.96 RGB 79.56 RGB 76.32 RGB 71.23 RGB 76.69 MSB 93.65 MSB 95.17 MSB 90.64 MSB 89.29 MSB 92.66 MSB 92.28

	Methods	1 st	2 nd	3 rd	4 th	5 th	Avg
	CP-

Table 6 . 2 :

 62 Execution times according to different image resolutions. the LRS 4 [177] library.

Table 7 . 1 :

 71 Datasets for human action recognition from 3D skeletal data.

	Dataset	# of actions # of subjects # of sequences
	UTKinect-Action	10	10	199
	Florence3D-Action	9	10	215

Table 7 . 2 :

 72 Length of each skeletal representation before (RAW column) and after (Final column) temporal modeling.

	Dataset	AJP RAW Final RAW RJP Final	JAQ RAW Final	SE3AP RAW Final	SE3RP RAW Final
	UTKinect	4218 7182 42180 71820 11248 19152	8436 14364 151848 258552
	Florence3D	215 2352 11025 17640	3920	6272	2940	4704	38220	61152

Table 7 . 3 :

 73 Selected subspace clustering algorithms for evaluation on skeletal action datasets.

	Representation Method	Author(s)
	low-rank	LRR LRSC	Liu et al. (2013) [121] Vidal and Favaro (2014) [214]
		SSC	Elhamifar and Vidal (2009) [59]
	sparse	RSSC LS3C	Xu et al. (2015) [233] Patel et al. (2013)

Table 7 . 4 :

 74 Clustering accuracy and std of five subspace clustering methods between five skeletal representations extracted from UTKinect dataset.

	Method	AJP	RJP	JAQ	SE3AP	SE3RP
	SSC RSSC LRR	0.913 ± 0.055 0.936 ± 0.048 0.777 ± 0.027 0.893 ± 0.040 0.820 ± 0.057 0.921 ± 0.020 0.951 ± 0.037 0.760 ± 0.018 0.900 ± 0.022 0.826 ± 0.026 0.795 ± 0.035 0.788 ± 0.026 0.643 ± 0.034 0.659 ± 0.041 0.653 ± 0.042
	LRSC LS3C	0.951 ± 0.040 0.812 ± 0.074 0.762 ± 0.013 0.768 ± 0.028 0.777 ± 0.042 0.751 ± 0.034 0.723 ± 0.018 0.680 ± 0.013 0.675 ± 0.023 0.579 ± 0.020
	some features are more overlapped than others, which results in a difficult task for clustering.

Table 7 . 5 :

 75 Clustering accuracy and std of five subspace clustering methods between five skeletal representations extracted from Florence3D-Action dataset. Confusion matrix for RSSC in the Florence3D dataset with AJP skeletal representation.

	Method	AJP	RJP	JAQ	SE3AP	SE3RP
	SSC RSSC LRR	0.788 ± 0.002 0.742 ± 0.028 0.708 ± 0.002 0.670 ± 0.005 0.642 ± 0.021 0.790 ± 0.001 0.733 ± 0.045 0.706 ± 0.001 0.679 ± 0.004 0.673 ± 0.010 0.784 ± 0.002 0.503 ± 0.022 0.493 ± 0.012 0.522 ± 0.014 0.469 ± 0.014
	LRSC LS3C	0.723 ± 0.007 0.730 ± 0.004 0.693 ± 0.001 0.692 ± 0.009 0.561 ± 0.026 0.655 ± 0.020 0.624 ± 0.019 0.732 ± 0.009 0.473 ± 0.018 0.612 ± 0.039

Table 7 . 6 :

 76 Performance comparison with state-of-the-art methods.

	Type Author(s)	Approach	Recognition rate
		UTKinect-Action dataset
	S	Xia et al. (2012) [230]	Histograms of 3D joints	90.92%
	S	Zhu et al. (2013) [261]	Random forests	87.90%
	S	Vemulapalli et al. (2014) [212] Points in a Lie Group	97.08%
	U	proposed	LRSC + AJP or RSSC + RJP	95.10%
		Florence3D-Action dataset
	S	Seidenari et al. (2013) [172]	Multi-Part Bag-of-Poses	82.00%
	S	Cippitelli et al. (2016) [47]	Key poses	82.10%
	S	Vemulapalli et al. (2014) [212] Points in a Lie Group	90.88%
	U	proposed	RSSC + AJP	79.00%

S -Supervised, U -Unsupervised

We suggest the reader to see the list of publications related to the thesis in the Appendix E.

Please refer to the Appendix D for a complete description of the library.

Up-to-date information on November 8, 2017.

This operation consists of stacking vertically all columns of the frame F.

For instance, a (strictly) convex function on an open set has no more than one minimum.

√ max(m,n), becoming a universal choice[START_REF] Candès | Robust Principal Component Analysis[END_REF][START_REF] Wright | Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization[END_REF]. Shortly, Candès et al.[START_REF] Candès | Robust Principal Component Analysis[END_REF] extended

https://www.mosek.com/

http://sedumi.ie.lehigh.edu/

https://yalmip.github.io/

http://cvxr.com/

Data points that have strong mutual coherence.

Hopkins 155 dataset: http://www.vision.jhu.edu/data/hopkins155/

Is important to note that, unfortunately, there does not exist a higher order SVD that inherits all the properties of the matrix SVD[3,

[START_REF] Kolda | Tensor decompositions and applications[END_REF][START_REF] Vasilescu | A multilinear (tensor) algebraic framework for computer graphics, computer vision, and machine learning[END_REF][START_REF] Vasilescu | Multilinear analysis of image ensembles: Tensorfaces[END_REF].

LRSLibrary: https://github.com/andrewssobral/lrslibrary

http://sbmi2015.na.icar.cnr.it/SBIdataset.html

A matrix with all its entries being zero.

NMF learns a parts-based representation of the data, whereas PCA learn holistic representations[START_REF] Lee | Learning the parts of objects by non-negative matrix factorization[END_REF].

If A is an m-by-n matrix with m > n, then QR computes only the first n columns of Q and the first n rows of R.

A sub-Gaussian distribution is a probability distribution with strong tail decay property[START_REF] Buldygin | Sub-Gaussian random variables[END_REF].

http://sbmi2015.na.icar.cnr.it/SBIdataset.html

Please, refer to Maddalena and Petrosino[START_REF] Maddalena | Towards benchmarking scene background initialization[END_REF] for a complete description of each metric.

http://cs-people.bu.edu/jmzhang/BMS/BMS.html

http://www.svcl.ucsd.edu/projects/background_subtraction/ ucsdbgsub_dataset.htm

http://www.dis.uniroma1.it/ ˜labrococo/MAR/index.htm

IMTSL: https://github.com/andrewssobral/imtsl

http://www.math.fsu.edu/ ˜cbaker/IncPACK/

http://bmc.iut-auvergne.com/

In terms of Precision, Recall and F-Measure (defined in Chapter 4, Table4.2)

https://sites.google.com/site/ihosvd/

OSTD: https://github.com/andrewssobral/ostd

Here, we refer basis as the set of elements (vectors) from a low-dimensional subspace.

http://ilt.u-bourgogne.fr/benezeth/projects/ICRA2014/

http://github.com/andrewssobral/lrslibrary

http://cvrc.ece.utexas.edu/KinectDatasets/HOJ3D.html

http://www.micc.unifi.it/vim/datasets/3dactions/

The definition of tensors used in this thesis should not be confused with tensor fields used in physics and differential geometry in mathematics, such as, stress tensor, Einstein tensor, metric tensor, curvature tensor, among the others[START_REF] Kolda | Tensor decompositions and applications[END_REF].

Figure D.3: CPU time consumption and the speed classification of each algorithm.

The reader can refer to https://scholar.google.fr/citations?user= 0Nm0uHcAAAAJ for an updated list of publications and their citations.

http://rfia2016.iut-auvergne.com/index.php/autres-evenements/ detection-d-objets-mobiles-par-soustraction-de-fond

https://sites.google.com/site/foregrounddetection/

Acknowledgement

Websites

• Andrews Sobral's homepage http://andrewssobral.wixsite.com/home • Publons https://publons.com/author/619460/andrews-sobral#profile • Behance.net project http://be.net/andrewssobral • GitHub profile https://github.com/andrewssobral • LRSLibrary -Low-Rank and Sparse tools for Background Modeling and Subtraction in Videos https://github.com/andrewssobral/lrslibrary • MTT -Matlab Tensor Tools for Computer Vision https://github.com/andrewssobral/mtt • IMTSL -Incremental and Multi-feature Tensor Subspace Learning https://github.com/andrewssobral/imtsl • OSTD -Online Stochastic Tensor Decomposition: https://github.com/andrewssobral/ostd Social networks • Academia http://univ-larochelle.academia.edu/AndrewsSobral • ResearchGate http://www.researchgate.net/profile/Andrews_Sobral

Chapter 4

Improving foreground detection by double-constrained robust PCA ONLINE STOCHASTIC TENSOR DECOMPOSITION

Experimental results

In this section, we present our experimental results in detail. We first evaluate the proposed method performance on synthetic generated data; then the qualitative and quantitative analysis on MSVS is presented.

Evaluation on synthetic data

The proposed method is first quantitatively tested on synthetic data. For data evaluation, a true low-rank tensor L of size 30 × 30 × 30 is generated by rank-3 factor matrices e.g., Y [k] ∈ R 30×3 where k = 1, 2, 3. Each factor matrix Y [k] consists of three components such as [sin(4π k 30 ), cos(4π k 30 ), sgn(sin(π))]. The first two components are different and third one is common in all modes. A random entries of L is corrupted by outliers from uniform distribution and small noise N (0, 0.01). We used Root Relative Square Error (RRSE) as measure for evaluation, given by || L-L||2

||L||2 , where L is the estimated low-rank tensor. We compare our RRSE performance with other state of the art methods, such as BRTF [253], CP-ARD [START_REF] Mørup | Automatic relevance determination for multi-way models[END_REF], CP-ALS [START_REF] Kolda | Tensor decompositions and applications[END_REF], HORPCA [START_REF] Goldfarb | Robust low-rank tensor recovery: Models and algorithms[END_REF] and HOSVD [START_REF] Goldfarb | Robust low-rank tensor recovery: Models and algorithms[END_REF], respectively (see Chapter 2, Section 2.4). Figure 6.1 shows the value of RRSE for the recovered tensor L. We consider two cases for robust tensor recovery for true data generation in Figure 6.1. First, the magnitude is considered within a range of true data (fully observed data) as shown in Figure 6.1 (a). However, Figure 6. 1 (b) shows that the magnitude is taken larger for corrupting some entries in true low-rank (partially observed data). In each case, the proposed method shows a very significant improvement compared to its batch counter-part, such as BRTF.

Evaluation on multispectral video sequences

We evaluate the proposed method on MSVS dataset [START_REF] Benezeth | Background subtraction with multispectral video sequences[END_REF]. This is the first dataset on MSVS 3 available for research community in background subtraction. The main purpose of this dataset is to show the advantage of multispectral information for an efficient foreground-background separation when illumination variations and color saturation occurs. Both qualitative and quantitative results are presented.

The MSVS dataset contains a set of 5 video sequences with 7 multispectral bands (6 visible spectra and 1 NIR spectrum). Each sequence presents a well known BS challenge, such as color saturation and dynamic background. Figure 6.2 shows the visual comparison of the proposed approach for BS task over three scenes of MSVS dataset. The true positives pixels (T P ) are in white, true negatives pixels (T N ) in black, false positives pixels (F P ) in red and false negatives pixels (F N ) in green. Figure 6.3 shows the visual results of these sequences using individual band with RGB features. This qualitative evaluation shows that BS using stochastic tensor decomposition on 7 multispectral bands together with visible spectra provides a satisfactory FG segmentation. Figure 6.4 shows the result from RGB image, 6 visible spectrum and 1 NIR spectral band together with visible spectra.

CONCLUSIONS

might be interesting for real and complex scenes. Finally, the investigation of fast optimization algorithms for finding the most appropriate weights could be an important research direction for this work.

• The online stochastic tensor decomposition algorithm proposed in Chapter 6 makes use of an online stochastic optimization algorithm to decompose the unfolded matrices of a tensor into a low-rank and sparse representation. The main drawback of the proposed algorithm is the computational cost required to process each unfolded matrix.

A future research may concern the exploitation of recent advances on randomized principal component analysis [START_REF] Erichson | Randomized matrix decompositions using r[END_REF][START_REF] Halko | Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions[END_REF][START_REF] Witten | Randomized algorithms for low-rank matrix factorizations: Sharp performance bounds[END_REF]. Instead of making a full decomposition of the unfolded matrices, the randomized algorithms provide an efficient computational framework that computes a compressed representation of the data using random sampling. In other words, it captures the essential information that can then be used to obtain a low-rank matrix/tensor approximation. Finally, the implementation of the OSTD algorithm in C/C++ language with GPU support could improve its scalability for high resolution and real-time applications.

• Finally, concerning Chapter 7, ideas for future work include the possibility to apply recent Robust PCA methods for filtering the noise in the action matrix before the subspace clustering step. In addition, recent feature selection algorithms [START_REF] Roffo | Report: Feature selection techniques for classification[END_REF] can be evaluated to reduce the dimension of the action matrix instead of the traditional PCA approach.

Appendix A

Notations and symbols

In this section we provide a homogenized overview of all different mathematical notations and symbols found over all chapters in this thesis. Table A.1 presents a summarized overview of the adopted symbols.

Matrices For matrices, A stands for the observation matrix, L is the low-rank matrix, S is the unconstrained (residual) matrix or sparse matrix, and E is the noise matrix. I is the identity matrix. For the specific matrices, the notations are given in the section of the corresponding method.

Tensors Similar to matrices, but represented by calligraphic letters, such as A, L, S, and E.

Norms The different norms used for vectors and matrices in this thesis are classified as follows:

• Vector α -norm, with 0 ≤ α ≤ 2: ||v|| 0 is the 0 -norm of the vector v, and it corresponds to the number of non-zero entries. ||v|| 1 = i v i is the 1 -norm of the vector v, and it corresponds to the sum of the vector elements.

is the 2 -norm of the vector v, and it corresponds to the Euclidean distance.

• Matrix α -norm, with 0 ≤ α ≤ 2: ||A|| 0 is the 0 -norm of the matrix A, and it corresponds to the number of non-zero entries. ||A|| 1 = max j i |A ij | is the 1 -norm of the matrix A, and it corresponds to the maximum absolute column sum norm. ||A|| 2 = σ max (A T A) = σ max (A) is the 2 -norm of the matrix A, and it corresponds to the largest singular value of the matrix A or the square root of the maximum eigenvalue of A T A. The 2 -norm for matrices is also known as spectral norm. The 2 -norm is also employed in its squared version such that

and it corresponds to the maximum absolute row sum norm. The ∞ -norm of

NOTATIONS AND SYMBOLS

the matrix A is equivalent to the 1 -norm of the transposed matrix, such that

is the α,β -mixed norm of the matrix A, and it corresponds to the β -norm of the vector formed by taking the α -norms of the columns of the matrix A. The norm 1,1 is equivalent to i,j |A i,j |, that is the sum of all absolute values of the matrix elements. The norm 1,2 is equivalent to σ( i |A i |), that corresponds to the singular value of the vector formed by taking the 1 -norms of the columns of the matrix A.

The norm 2,2 is equivalent to trace(AA T ) (also known as Frobenius norm).

• Matrix Frobenius norm:

trace(AA T ) is the Frobenius norm of the matrix A, and it is defined as the square root of the sum of the squared absolute values of its elements. The Frobenius norm is equivalent to 2,2 -norm and it is sometimes also called the Euclidean norm, which may cause confusion with the vector 2 -norm. The Frobenius norm is also employed in its squared version such that ||A|| 2

, representing the sum of squares of all entries.

• Matrix max norm: ||A|| max = max|A ij | is the max norm of the matrix A, and it corresponds to the maximum absolute value of the matrix A.

• Matrix nuclear norm:

is the nuclear norm of the matrix A, and it corresponds to the sum of the singular values of the matrix A. The nuclear norm is equivalent to the 1 -norm applied on the vector whose elements are the singular values of the matrix, such that ||A|| * = ||σ(A)|| 1 . For a desired rank r in low-rank minimization, the nuclear norm is also defined by ||A|| * = r i=1 σ i (A). • Matrix Schatten-p norm, with 0 ≤ p ≤ 2: the Schatten-p norm is the p-norm applied to the vector of singular values of a matrix. The Schatten p-norm is defined by ||A|| Sp = ( i (σ i (A)) p ) 1/p , where σ i (A) represents the i-th singular value of the matrix A. For p = 1 and p = 2, it yields the nuclear norm and the Frobenius norm, respectively. The case p = ∞ yields the spectral norm.

• Tensor Frobenius norm:

is the Frobenius norm of an N th -order tensor X , and it is defined as the square root of the sum of the absolute values of its elements. The Frobenius norm is sometimes also called the Euclidean norm, which may cause confusion with the vector 2 -norm. The Frobenius norm is also employed in its squared version representing the sum of squares of all entries, such that

Table A.1: Summary of symbols used in this thesis.

x, y, z, X, Y, Z Scalars (lowercase or uppercase letters) x, y, z Vectors (lowercase bold letters) X, Y, Z Matrices (uppercase bold letters) X , Y, Z Tensors (uppercase calligraphic bold letters)

A vector formed by all columns of the ith row of a matrix X X :j

A vector formed by all rows of the jth column of a matrix X X :jk , X i:k , X ij:

Column, row, and tube fibers of a third-order tensor X X i:: , X :j: , X ::k Horizontal, lateral and frontal slices of a third-order tensor X x T , X T Transpose of vector x and matrix X X Denotes the complement of the matrix X X [n] n-mode matricization of tensor X X [n] Matrix representing the n-mode matricization of tensor X X (t) [n] n-mode matricization of tensor X at time instance t X (t) [n] Matrix representing the n-mode matricization of tensor X at time instan 0 ∈ R m×n Zero matrix. A matrix with all its entries being zero.

∈ R m×n

All-ones matrix. A matrix where every element is equal to one.

R

The set of real numbers

R n

The set of all real vectors of length n

R m×n

The set of all real matrices of size m × n R I1×I2×...×I N The set of all N th -order real tensors of size

NOTATIONS AND SYMBOLS var(x)

Variance of the elements of the vector x std(x)

Standard deviation of the elements of the vector x card(S)

Denotes the number of non-zero entries of matrix S rank(.)

Matrix or tensor rank rank r (X) rank-r approximation of matrix X (general case) svd r (X) rank-r approximation of matrix X by SVD vec(X), vec(X )

Vectorization of matrix X or tensor X x ⊗ y

Outer product between vectors x and y X • Y Element-wise multiplication between matrices X and Y X ⊗ Y Kronecker product between matrices X and Y X × n U n-mode product between tensor X and matrix U

Sampling operator min(x 1 , x 2 , . . . , x N )

The smallest among scalars {x i } min(x), min(X)

The smallest element of a vector x or matrix X max(x), max(X)

The biggest element of a vector x or matrix X min x f (x)

The minimum value of real function f with respect to x arg min x f (x)

The minimizer of real function f with respect to x From the point of view of multi-linear algebra, a tensor can be considered as a multidimensional or multi-way array of data, usually seen as a generalization of the vector concept [START_REF] Kolda | Tensor decompositions and applications[END_REF][START_REF] Lathauwer | A multilinear singular value decomposition[END_REF]. For example, a scalar is represented as a 0th-order tensor, a vector as a 1storder tensor, and a matrix (a 2-dimensional array) as a 2nd-order tensor. The order (also degree or rank) of a tensor is the dimensionality of the array needed to represent it. Tensors of order three or higher are usually called higher-order tensors. Figure C.1 (left) gives an example of tensor's dimensionality. Since the human brain's is limited to three dimensional perception, the visualization of high dimensional data is still a non trivial task. However, several approaches have been proposed in the literature for visualizing data with four or more dimensions [START_REF] Liu | Visualizing highdimensional data: Advances in the past decade[END_REF][START_REF] Tang | Visualizing large-scale and high-dimensional data[END_REF]. An easy way to interpret the fourth dimension case is to consider a cube's sequence, for example a sequence of color images (a spatio-temporal volume) where its first three dimensions are represented by its width, height and color channels (i.e. RGB color model). In the case of the fifth (or more) dimension, an interesting example is the representation of the TensorFaces proposed by Vasilescu and Terzopoulos [START_REF] Vasilescu | Multilinear analysis of image ensembles: Tensorfaces[END_REF]

LIST OF ABBREVIATIONS

C.2 Fibers and slices

A tensor can be decomposed into subarrays by fixing a subset of its indices. A tensor f iber can be regarded as a one-dimensional fragment (or column vector) of a tensor and it is defined by fixing every index except one. A third-order tensor X ijk has column, row, and tube fibers denoted by X :jk , X i:k and X ij: , as can be seen in Figure C.3 (a). A second property is the tensor slice. A tensor slice is a two-dimensional section of a tensor, when all but two indices are fixed, resulting in a matrix called slice. A third-order tensor X ijk has horizontal, lateral and frontal slices indicated by X i:: , X :j: and X ::k , as can be seen in Figure C.3 (b). Fibers and slices are the core of the most important operations on tensors, such as vectorization, matricization, n-mode product, among the others [START_REF] Kolda | Tensor decompositions and applications[END_REF], some of which are described in the next sections.

C.3 Vectorization and matricization

In order to work with tensors, it is often convenient to represent tensors as vectors or matrices. This process is known as vectorization or matricization, and consist in reordering the elements of an N -th order tensor into a vector or a matrix, respectively [START_REF] Kolda | Tensor decompositions and applications[END_REF]. For example, a 5 × 6 × 8 tensor can be arranged as a vector of 240 elements or a 5 × 48 matrix.

Definition C.1. (Tensor vectorization). Let X ∈ R I1×I2×...×I N be an N -th order tensor. The vectorized tensor, denoted by vec(X ), is a vector formed by the tensor entries, such that tensor entry (i 1 , i 2 , . . . , i n ) is mapped to vector entry j, where

C.4.1 n-mode tensor vector product

The n-mode vector product of an N -th order tensor X ∈ R I1×I2×...×I N with a vector v ∈ R In is denoted by X × n v. Each n-mode fiber is multiplied by the vector v, and usually is expressed by

C.4.2 n-mode tensor matrix product

The n-mode matrix product of an N -th order tensor X ∈ R I1×I2×...×I N with a matrix U ∈ R J×In is denoted by X × n U. Each n-mode fiber is multiplied by the matrix U, and usually is expressed by

C.4.3 t-product

Let A be an I 1 ×I 2 ×I 3 tensor and B be an I 2 ×I 4 ×I 3 . The t-product of A and B, C = A * B, is an I 1 × I 4 × I 3 , defined as follows [START_REF] Kilmer | Factorization strategies for third-order tensors[END_REF]:

where denotes a circular convolution.

C.4.4 f -diagonal

An The LRSLibrary [START_REF] Sobral | LRSLibrary: Low-rank and sparse tools for background modeling and subtraction in videos[END_REF] 1 provides a collection of low-rank and sparse decomposition algorithms in MATLAB. The library was designed for background/foreground separation in videos, and it contains a total of 104 matrix-based and tensor-based algorithms. The library is also equipped with an easy-to-use graphical user interface (GUI), enabling the user to select the type of method (e.g. RPCA for Robust PCA) and its related algorithm (e.g. FPCP for Fast PCP), please see The remainder of this appendix is organized as follows. First we start with the motivation behind the LRSLibrary in Section D.1. Section D.2 presents a brief overview of the algorithms available in the LRSLibrary. Section D.3 evaluates the computational cost of each algorithm and its speed. Finally, in Sections D.4 and D.5, we present a usage example of the LRSLibrary, as well as conclusions.

Appendix D

D.1 Motivation

The main motivation behind the LRSLibrary was to build an easy-to-use framework for applying low-rank and sparse decomposition tools for the background/foreground separation problem. The library was developed to be open source and free for academic/research purpose. The LRSLibrary was crucial for all experiments conducted in the current thesis.

D.2 Algorithms

Up to the date of writing, the LRSLibrary provided 104 algorithms for B/F. An updated list of currently available algorithms can be found in the library website. The algorithms were grouped into the following categories: RPCA for Robust PCA, ST for Subspace Tracking, MC for Matrix Completion, TTD for Three-Term Decomposition, LRR for Low-Rank Representation, NMF for Non-negative Matrix Factorization, NTF for Non-negative Tensor Factorization, or TD for standard Tensor Decomposition.

D.3 Computational cost

Many efforts have been recently concentrated to develop low-computational subspace learning algorithms. In this section, an evaluation of the computational cost of the LRSLibrary algorithm's is shown in

(very fast: represented by blue color)

(fast: represented by green color)

D.4 Usage example

The LRSLibrary was designed to be easy to use. It contains several ready-to-use functions to help the user to perform B/F by low-rank and sparse representation. Listing D.4 demonstrates how to perform matrix and tensor factorization, given an input video file. The final results are stored in the out variable, and the function show results shows the background subtraction process. Please, refer to the online version of demo.m 2 file for a complete overview.

Books

• 2017 -Bouwmans, Thierry; Sobral, Andrews; Zahzah, El-hadi. Handbook on "Background Subtraction for Moving Object Detection: Theory and Practices", (in progress) 3 .

Book chapters Robust low-rank and sparse decomposition for moving object detection: from matrices to tensors Summary:

This thesis introduces the recent advances on decomposition into low-rank plus sparse matrices and tensors, as well as the main contributions to face the principal issues in moving object detection. First, we present an overview of the state-of-the-art methods for low-rank and sparse decomposition, as well as their application to background modeling and foreground segmentation tasks. Next, we address the problem of background model initialization as a reconstruction process from missing/corrupted data. A novel methodology is presented showing an attractive potential for background modeling initialization in video surveillance. Subsequently, we propose a double-constrained version of robust principal component analysis to improve the foreground detection in maritime environments for automated video-surveillance applications. The algorithm makes use of double constraints extracted from spatial saliency maps to enhance object foreground detection in dynamic scenes. We also developed two incremental tensor-based algorithms in order to perform background/foreground separation from multidimensional streaming data. These works address the problem of low-rank and sparse decomposition on tensors. Finally, we present a particular work realized in conjunction with the Computer Vision Center (CVC) at Autonomous University of Barcelona (UAB).