Caroline Silva

Thierry Bouwmans
email: thierry.bouwmans@univ-lr.fr

Carl Frélicot
email: carl.frelicot@univ-lr.fr

An eXtended Center

Keywords: Symmetric Local Binary Pattern Local binary patterns, Background modeling, Background subtraction

published or not. The documents may come   L'archive ouverte pluridisciplinaire

INTRODUCTION

The background subtraction (BS) is one of the main steps in many computer vision applications, such as object tracking, behavior understanding and activity recognition [START_REF] Pietikäinen | Computer vision using local binary patterns[END_REF]. The BS process consists basically of: a) background model initialization, b) background model maintenance and c) foreground detection. Many BS methods have been developed during the last few years (Bouwmans, 2014;[START_REF] Sobral | A comprehensive review of background subtraction algorithms evaluated with synthetic and real videos[END_REF][START_REF] Shah | Video background modeling: Recent approaches, issues and our solutions[END_REF], and the main resources can be found at the Background Subtraction Web Site 1 .

The BS needs to face several challenging situations such as illumination changes, dynamic backgrounds, bad weather, camera jitter, noise and shadows. Several feature extraction methods have been developed to deal with these situations. Color features are the most widely used, but they present several limitations when illumination changes, shadows and camouflage occurences are present. A variety of local texture descriptors recently have attracted great attention for background modeling, especially the Local Binary Pattern (LBP) because it is simple and fast to compute. Figure 1 (top) shows how a (center) pixel is encoded by a series of bits, accordingly to the relative gray levels of its circular neighboring pixels. It shows great invariance to monotonic illumination changes, do not require many parameters to be set, and have a high discriminative power. However, the original LBP descriptor in [START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF] is not efficient for background modeling because of its sensitivity to noise, see Figure 1 (bottom) where a little change of the central value greatly affects the resulting code. The LBP feature of an image consists in building a histogram based on the codes of all the pixels within the image. As it only adopts first-order gradient information between the center pixel and its neighbors, see [START_REF] Xue | Hybrid center-symmetric local pattern for dynamic background subtraction[END_REF], the produced histogram can be rather long. A large number of local texture descriptors based on LBP [START_REF] Richards | Local binary patterns: New variants and applications[END_REF] have been proposed so far for background modeling. In order to be more robust to noise or illumination changes, most of them are unfortunately either very time-consuming or produce a long feature histogram.

In this paper, we propose to extend the variant by [START_REF] Heikkilä | Description of interest regions with local binary patterns[END_REF] by introducing a new neighboring pixels comparison strategy that allows the descriptor to be less sensitive to noisy pixels and to produce a short histogram, while preserving robustness to illumination changes and slightly gaining in time consumption when compared to its direct competitors.

The rest of this paper is organized as follows. Section 2 provides quite an exhaustive overview of LBPbased descriptors. The new descriptor that we propose is described in Section 3. Comparative results obtained on both synthetic and real videos are given in Section 4. Finally, concluding remarks and some perspectives are drawn in Section 5.

Descriptor

Robust to noise

Robust to illumination changes

Uses color information

Uses temporal information

Histogram size with 8 neighbors Original LBP [START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF] • 256 Modified LBP [START_REF] Heikkilä | A texturebased method for modeling the background and detecting moving objects[END_REF] • • 256 CS-LBP [START_REF] Heikkilä | Description of interest regions with local binary patterns[END_REF] • 16 STLBP [START_REF] Shimada | Hybrid background model using spatial-temporal lbp[END_REF] • • 256 εLBP Wang and Pan (2010) • 256 Adaptive εLBP (Wang et al., 2010) • 256 SCS-LBP [START_REF] Xue | Dynamic background subtraction based on spatial extended center-symmetric local binary pattern[END_REF] • • 16 SILTP [START_REF] Liao | Modeling pixel process with scale invariant local patterns for background subtraction in complex scenes[END_REF] • 256 CS-LDP [START_REF] Xue | Hybrid center-symmetric local pattern for dynamic background subtraction[END_REF] • 16 SCBP [START_REF] Xue | Hybrid center-symmetric local pattern for dynamic background subtraction[END_REF] • 64 OCLBP [START_REF] Lee | Hierarchical on-line boosting based background subtraction[END_REF] • 1536 Uniform LBP [START_REF] Yuan | A new background subtraction method using texture and color information[END_REF] • 59 SALBP [START_REF] Noh | A new framework for background subtraction using multiple cues[END_REF] • 128 SLBP-AM [START_REF] Yin | Dynamic background subtraction based on appearance and motion pattern[END_REF]

RELATED WORK

One of the first descriptors based on the LBP for background modeling can be found in [START_REF] Heikkilä | A texturebased method for modeling the background and detecting moving objects[END_REF]. It improves the original LBP in image areas where the gray values of the neighboring pixels are very close to the center pixel one, e.g. sky, grass, etc. [START_REF] Shimada | Hybrid background model using spatial-temporal lbp[END_REF] propose a Spatial-Temporal Local Binary Pattern (STLBP) which is robust to short-term illumination changes by using some temporal information. Two variants of LBP, called εLBP and Adaptive εLBP, are developed in (Wang and Pan, 2010;Wang et al., 2010). They are fast to compute and less sensitive to the illumination variation or some color similarity between foreground and background. [START_REF] Heikkilä | Description of interest regions with local binary patterns[END_REF] [START_REF] Xue | Hybrid center-symmetric local pattern for dynamic background subtraction[END_REF]. It extracts more detailed local information while preserving the same feature lengths than the CS-LBP, but with a slightly lower precision than the original LBP. [START_REF] Zhou | Dynamic background subtraction using spatial-color binary patterns[END_REF] develop a Spatial-Color Binary Pattern (SCBP) that fuse color and texture information. The SCBP outperforms LBP and SCS-LBP for background subtraction tasks. In [START_REF] Lee | Hierarchical on-line boosting based background subtraction[END_REF], the authors propose an Opponent Color Local Binary Pattern (OCLBP) that uses color and texture information. The OCLBP extracts several pixel's pieces of information, but the length of the produced histogram makes it useless for some applications. An Uniform LBP Patterns with a new thresholding method can be found in [START_REF] Yuan | A new background subtraction method using texture and color information[END_REF]. It appears to be tolerant to the interference of the sampling noise. [START_REF] Yin | Dynamic background subtraction based on appearance and motion pattern[END_REF] propose a Stereo LBP on Appearance and Motion (SLBP-AM) which uses information from a set of frames of three different planes. This texture descriptor is not only robust to slight noise, but it also adapts quickly to the large-scale and sudden light changes. A Local Binary Similarity Patterns (LBSP) descriptor is developed in (Bilodeau et al., 2013). Based on absolute absolute differences, it applies on small areas and is calculated inside one image and between two images. This allows LBSP to capture both texture and intensity changes. [START_REF] Noh | A new framework for background subtraction using multiple cues[END_REF] propose to improve the SILTP [START_REF] Liao | Modeling pixel process with scale invariant local patterns for background subtraction in complex scenes[END_REF] thanks to a codebook method. The derived descriptor gain in robustness when segmenting moving objects from dynamic and complex backgrounds. [START_REF] Wu | Real-time background subtraction-based video surveillance of people by integrating local texture patterns[END_REF] extend SILTP by introducing a novel Center Symmetric Scale Invariant Local Ternary Patterns (CS-SILTP) descriptor which explores spatial and temporal rela-tionships within the neighborhood. The LBP descriptors present a significant drawback as it ignores the intensity information. Because of this, there could be a wrong pixel comparison result when intensity values of pixels differ drastically, but their LBP values are identical. To overcome this drawback, [START_REF] Vishnyakov | Fast moving objects detection using ilbp background model[END_REF] propose an intensity LBP (iLBP) to build a fast background model is proposed in [START_REF] Vishnyakov | Fast moving objects detection using ilbp background model[END_REF]. It is defined as a collection of LBP descriptor values and intensity values of the image. The main characteristics of all the above reviewed LBP variants, including those we will compare our new descriptor to, are summarized in Table 1. Let a pixel at a certain location, considered as the center pixel c = (x c , y c ) of a local neighborhood composed of P equally spaced pixels on a circle of radius R. The LBP operator applied to c can be expressed as:

THE XCS-LBP DESCRIPTOR

LBP P,R (c) = P-1 ∑ i=0 s (g i -g c ) 2 i (1)
where g c is the gray value of the center pixel c and g i is the gray value of each neighboring pixel, and s is a thresholding function defined as:

s(x) = 1 if x ≥ 0 0 otherwise. (2)
From (1), it is easy to show that the number of binary terms to be summed is ∑ P-1 i=0 2 i = 2 P -1, so that the length of the resulting histogram (including the bin-0 location) is 2 P . The underlying idea of CS-LBP in [START_REF] Heikkilä | Description of interest regions with local binary patterns[END_REF] is to compare the gray levels of pairs of pixels in centered symmetric directions instead of comparing the central pixel to its neighbors. Assuming an even number P of neighboring pixels, the CS-LBP operator is given by:

CS -LBP P,R (c) = (P/2)-1 ∑ i=0 s(g i -g i+(P/2) ) 2 i (3)
where g i and g i+(P/2) are the gray values of centersymmetric pairs of pixels, and s is the thresholding function defined as:

s(x) = 1 if x > T 0 otherwise (4)
where T is a user-defined threshold. Since the gray levels are normalized in [0,1], the authors recommend to use of a small value. We will set it to 0.01 in the experiments presented in Section 4. By construction, the length of the histogram resulting from the CS-LBP descriptor falls down to 1 + ∑ P/2-1 i=0

2 i = 2 P/2 . For BS, the CS-LBP encodes the two images to be compared as texture-based images with a lower quantization that slightly favors robustness.

We propose to extend the CS-LBP operator by comparing the gray values of pairs of centersymmetric pixels so that the produced histogram are short as well, but considering the central pixel also. This combination makes the resulting descriptor less sensitive to noise for the BS application. The new LBP variant, called XCS-LBP (eXtended CS-LBP), expresses as:

XCS -LBP P,R (c) = (P/2)-1 ∑ i=0 s (g 1 (i, c) + g 2 (i, c)) 2 i (5)
where the threshold function s, which is used to determine the types of local pattern transition, is defined as a characteristic function:

s(x 1 + x 2 ) = 1 if (x 1 + x 2 ) ≥ 0 0 otherwise. ( 6
)
and where g 1 (i, c) and g 2 (i, c) are defined by:

g 1 (i, c) = (g i -g i+(P/2) ) + g c g 2 (i, c) = (g i -g c ) (g i+(P/2) -g c ) (7)
with the same notation conventions than in equations ( 1) and (3). It is worth noting that the threshold function does not need a user-defined threshold value, contrary to CS-LBP. The computation of the original LBP for a neighborhood of size P = 8 is illustrated in Figure 2 and the computation of the proposed XCS-LBP is shown in Figure 3 in order to make the comparison more understandable for the reader. Note the respective code lengths of 8 and 4 that lead to respective image compressions.

The proposed XCS-LBP produces a shorter histogram than LBP, as short as CS-LBP, but it extracts more image details than CS-LBP because (i) it takes into account the gray value of the central pixel, and (ii) it relies on a new strategy for neighboring pixels comparison. Since it is also more robust to noisy images than both LBP and CS-LBP, the proposed descriptor appears to more efficient for background modeling and subtraction.

EXPERIMENTAL RESULTS

Several experiments were conducted to illustrate both the qualitative and quantitative performances of the proposed descriptor XCS-LBP. We use datasets from the BMC (Background Models Challenge) which comprises synthetic and real videos of outdoor situations (urban scenes) acquired with a static camera, under different weather variations such as: wind, sun or rain [START_REF] Vacavant | A benchmark dataset for outdoor foreground/background extraction[END_REF]. We compare XCS-LBP with three other texture descriptors among the reviewed ones, namely:

• original LBP [START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF],

• CS-LBP [START_REF] Heikkilä | Description of interest regions with local binary patterns[END_REF] and [START_REF] Xue | Hybrid center-symmetric local pattern for dynamic background subtraction[END_REF].

• CS-LDP
We choose these two last descriptors on fair comparison purpose. Indeed, among those who rely on the same construction principle, i.e. Center Symmetric (CS), they are the only ones that use neither color nor temporal information, see Table 1. For all descriptors, the neighborhood size is empirically selected so that P = 8 and R = 1, and we evaluate the performance with two popular background subtraction methods, see (Bouwmans, 2014): • Adaptive Background Learning (ABL) and

• Gaussian Mixture Models (GMM).
First, we present results of background subtraction on individual frames of five different scenes from two video sequences: Rotary (frame #1140) and Street (frame #301). Figures 4 and5 show the foreground detection results using the ABL and the GMM methods, respectively. Our descriptor clearly appears to be less sensitive to the background subtraction method, whereas the three others are very useless in detecting the moving objects when using the ABL method, unless a strong post-processing procedure.

Next, we give quantitative results on the same data. We use three classical measures based on the numbers of true positive T P pixels (correctly detected foreground pixels), false positive FP pixels (background pixels detected as foreground ones), false negative pixels FN (foreground pixels detected as background ones), and true negative pixels (correctly detected background pixels):

• Recall = T P T P + FN ,

• Precision = T P T P + FP , and

• F -score = 2 × Recall × Precision Recall + Precision .
Tables 2 and3 shows the scores of the different descriptors obtained on the Rotary and Street entire scenes when using the ABL and the GMM method, respectively. Best scores are in bold. The proposed XCS-LBP gives the highest value for each score on almost all scenes, except for scene 312,412], for which CS-LBP and CS-LDP has achieved the best Recall using ABL, and scene Street-112 for which LBP gives the best Recall using GMM.

Note that both CS-LBP and CS-LDP gives lower scores (Precision and F-score) than LBP for some scenes, while our XCS-LBP descriptor takes always the advantage on the others, as shown by the average scores reported at the bottom of each Table .  Finally, we evaluate the proposed descriptor on nine long duration (about one hour) real outdoor video scenes from BMC. Each video sequence shows different challenging situations of real world: moving trees, casted shadows, the presence of a continuous car flow near to the surveillance zone, general climatic conditions (sunny, rainy and snowy conditions), fast light changes and the presence of big objects. The scores obtained using the ABL and the GMM methods are given in Table 4 and5, respectively. Once again, our descriptor achieved the best scores on almost always scenes, even when using the simple ABL method whereas it dramatically compromises the other descriptors. The average scores reported at the bottom of each Table show that our XCS-LBP outperforms the original LBP and both the similar construction-based CS-LBP and CS-LDP descriptors, the latter one being less performant than the LBP using GMM method. We use Matlab R2013a on a MacBook Pro (OS X 10.9.4) equipped with 2.2 GHz Intel Core i7 and 8 GB -1333 MHz DDR3.

We collected the elapsed CPU times needed to segment the foregrounds using the ABL and the GMM methods, averaged over the nine real videos of BMC. Since the reference is the (fastest) LBP descriptor, the times are divided by LBP ones. Table 6 reports the resulting ratios for the compared CS de-scriptors. Our XCS-LBP shows slightly better time performance than both CS-LBP and CS-LDP. It is also tolerant to illumination changes as LBP and CS-LBP are whereas CS-LDP is not, and robust to noise as CS-LDP is whereas LBP and CS-LBP are not. We compared the XCS-LBP to the original LBP and to its two direct competitors on both synthetic and real videos of the Background Modeling Challenge (BMC) using two popular background subtraction methods. The experimental results show that the proposed descriptor qualitatively and quantitatively outperforms the mentioned descriptors, making it a serious candidate for the background substation task in computer vision applications. Future works will explore how to extend the proposed descriptor to include temporal relationships between neighboring pixels for dynamic texture classification or human action recognition.

Figure 1 :

 1 Figure 1: Examples of LBP encoding

Figure 2 :

 2 Figure 2: The LBP descriptor.

Figure 3 :Figure 4 :

 34 Figure 3: The XCS-LBP descriptor. Rotary (frame #1140) -scenes 122, 222, 322, 422 and 522 Street (frame #301) -scenes 112, 212, 312, 412 and 512 (a)

Figure 5 :

 5 Figure 5: Background subtraction results using the GMM method on synthetic scenes -(a) original frame, (b) ground truth, (c) LBP, (d) CS-LBP, (e) CS-LDP and (f) proposed XCS-LBP.

Table 1 :

 1 Comparison of LBP and variants.

Table 2 :

 2 Performance of the different descriptors on synthetic videos of the BMC using the ABL method.

	Scenes Descriptor Recall Precision F-score
		LBP	0.682	0.564	0.618
	Rotary	CS-LBP	0.832	0.520	0.640
	122	CS-LDP	0.809	0.523	0.635
		XCS-LBP	0.850	0.784	0.816
		LBP	0.611	0.505	0.553
	Rotary	CS-LBP	0.673	0.504	0.577
	222	CS-LDP	0.753	0.510	0.608
		XCS-LBP	0.852	0.782	0.815
		LBP	0.603	0.505	0.550
	Rotary	CS-LBP	0.647	0.504	0.566
	322	CS-LDP	0.733	0.507	0.600
		XCS-LBP	0.829	0.793	0.810
		LBP	0.573	0.502	0.535
	Rotary	CS-LBP	0.609	0.503	0.550
	422	CS-LDP	0.733	0.508	0.600
		XCS-LBP	0.751	0.780	0.765
		LBP	0.610	0.505	0.553
	Rotary	CS-LBP	0.663	0.504	0.573
	522	CS-LDP	0.745	0.509	0.605
		XCS-LBP	0.852	0.732	0.787
		LBP	0.702	0.530	0.604
	Street	CS-LBP	0.839	0.512	0.636
	112	CS-LDP	0.826	0.525	0.642
		XCS-LBP	0.803	0.793	0.798
		LBP	0.636	0.504	0.562
	Street	CS-LBP	0.716	0.503	0.591
	212	CS-LDP	0.798	0.513	0.624
		XCS-LBP	0.808	0.790	0.799
		LBP	0.627	0.504	0.558
	Street	CS-LBP	0.699	0.503	0.585
	312	CS-LDP	0.801	0.511	0.624
		XCS-LBP	0.800	0.796	0.798
		LBP	0.580	0.501	0.558
	Street	CS-LBP	0.599	0.501	0.546
	412	CS-LDP	0.754	0.507	0.607
		XCS-LBP	0.748	0.781	0.764
		LBP	0.628	0.503	0.559
	Street	CS-LBP	0.677	0.503	0.577
	512	CS-LDP	0.771	0.508	0.612
		XCS-LBP	0.800	0.575	0.669
		LBP	0.625	0.512	0.565
	Average	CS-LBP	0.695	0.506	0.584
	scores	CS-LDP	0.772	0.512	0.616
		XCS-LBP	0.809	0.761	0.782
	5 CONCLUSION
	In this paper, a new texture descriptor for back-
	ground modeling is proposed. It combines the
	strengths of the original Local Binary Pattern (LBP)
	and the Center-Symmetric (CS) LBPs. Thus, the

Table 3 :

 3 Performance of the different descriptors on synthetic videos of the BMC using the GMM method.

	Scenes Descriptor Recall Precision F-score
		LBP	0.817	0.701	0.755
	Rotary	CS-LBP	0.830	0.705	0.763
	122	CS-LDP	0.819	0.677	0.741
		XCS-LBP	0.831	0.800	0.815
		LBP	0.636	0.653	0.644
	Rotary	CS-LBP	0.741	0.687	0.713
	222	CS-LDP	0.651	0.616	0.633
		XCS-LBP	0.825	0.794	0.809
		LBP	0.661	0.646	0.653
	Rotary	CS-LBP	0.741	0.656	0.696
	322	CS-LDP	0.674	0.613	0.642
		XCS-LBP	0.821	0.767	0.793
		LBP	0.611	0.585	0.598
	Rotary	CS-LBP	0.673	0.575	0.620
	422	CS-LDP	0.611	0.548	0.578
		XCS-LBP	0.748	0.702	0.724
		LBP	0.636	0.627	0.631
	Rotary	CS-LBP	0.743	0.672	0.706
	522	CS-LDP	0.605	0.650	0.627
		XCS-LBP	0.825	0.760	0.791
		LBP	0.940	0.674	0.785
	Street	CS-LBP	0.924	0.675	0.780
	112	CS-LDP	0.938	0.656	0.772
		XCS-LBP	0.844	0.755	0.808
		LBP	0.676	0.642	0.659
	Street	CS-LBP	0.752	0.658	0.702
	212	CS-LDP	0.694	0.577	0.630
		XCS-LBP	0.833	0.760	0.795
		LBP	0.684	0.633	0.657
	Street	CS-LBP	0.742	0.627	0.680
	312	CS-LDP	0.729	0.581	0.647
		XCS-LBP	0.821	0.713	0.763
		LBP	0.619	0.566	0.591
	Street	CS-LBP	0.705	0.567	0.628
	412	CS-LDP	0.659	0.539	0.593
		XCS-LBP	0.751	0.619	0.679
		LBP	0.662	0.566	0.610
	Street	CS-LBP	0.727	0.568	0.638
	512	CS-LDP	0.689	0.551	0.612
		XCS-LBP	0.828	0.629	0.715
		LBP	0.694	0.629	0.658
	Average	CS-LBP	0.758	0.639	0.693
	scores	CS-LDP	0.707	0.601	0.648
		XCS-LBP	0.813	0.730	0.769
	new variant XCS-LBP (eXtended CS-LBP) produces
	a shorter histogram than LBP, by its CS-construction.

Table 4 :

 4 Performance of the different descriptors on realworld videos of the BMC using the ABL method

	Videos	Descriptor Recall Precision F-score
	Boring	LBP	0.555	0.512	0.533
	parking,	CS-LBP	0.663	0.539	0.595
	active	CS-LDP	0.712	0.556	0.624
	bkbg	XCS-LBP	0.673	0.628	0.650


Andrews Sobral
email: andrews.sobral@univ-lr.fr

Thierry Bouwmans
email: tbouwman@univ-lr.fr

Double-constrained RPCA based on Saliency Maps for Foreground Detection in Automated Maritime Surveillance

The development of automated video-surveillance applications for maritime environment is a very difficult task due to the complexity of the scenes: moving water, waves, etc. 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). In this paper, a double-constrained Robust Principal Component Analysis (RPCA), named SCM-RPCA (Shape and Confidence Mapbased RPCA), is proposed to improve the object foreground detection in maritime scenes. The sparse component is constrained by shape and confidence maps both extracted from spatial saliency maps. The experimental results in the UCSD and MarDT data sets indicate a better enhancement of the object foreground mask when compared with some related RPCA methods.

Introduction

Background subtraction (BS) or foreground separation is commonly the first step in many video surveillance systems to detect moving objects. This basic operation consists of separating the moving objects called "foreground" from the static information called "background". However, in most cases, the background model is not always static due to the complexity of natural scenes: wind in the trees, moving water, waves, etc. A specific case is the development of automated video-surveillance applications for maritime environment (i.e. automatic detection of ships or boats to improve the sea border control).

The maritime surveillance represents a challenging scenario due to the different background dynamics of the observed scenes. Many algorithms have been designed to perform foreground detection [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 works 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] proposes 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 show 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.

Robust Principal Component Analysis (RPCA) solved via Principal Component Pursuit (PCP) [START_REF] Candes | Robust principal component analysis?[END_REF] decomposes a data matrix A in two components such that A = L + S, where L is a low-rank matrix and S is constrained to be a sparse matrix. The low-rank minimization concerning L offers a suitable framework for background modeling due to the 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. To obtain the foreground mask, S needs to be thresholded. Usually, the threshold is determined experimentally.

However, PCP is limited to the low-rank component being exactly low-rank and the sparse component being exactly sparse but the observations in real applications are often corrupted by noise affecting every entry of the data matrix. Therefore, Zhou et al. [START_REF] Zhou | Stable principal component pursuit[END_REF] proposed a stable PCP (SPCP) that guarantee stable and accurate recovery in the presence of entry-wise noise. SPCP assumes that the observation matrix A is represented as A = L + S + E (also named as three-term decomposition), where E is a noise term. To recover L, S and E, Zhou et al. [START_REF] Zhou | Stable principal component pursuit[END_REF] proposed to solve the following optimization problem, as a relaxed ver-1 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 tries 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) is considered as sparse component (S). The low-rank component (L) represents the static part of the background.

In this paper, a double-constrained RPCA, named SCM-RPCA (Shape and Confidence Map-based RPCA), is proposed to improve the object 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 to combine two different types of source: spatial, temporal, and spatiotemporal information, but in this work we focus only on spatial saliency maps. Fig. 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 this one, and (e) the foreground mask given by thresholding the RPCA sparse component.

First, we start with the related works (Section 2), and next we describe our proposed approach (Section 3). The remainder of the paper is organized as follows: Section 4 describes how to solve our SCM-RPCA algorithm. Section 5 defines the concept of shape and confidence map. Finally, in Sections 6 and 7, the experimental results are shown as well as conclusions.

Related works

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] use a turbulence model to enforce an additional constraint on the rank minimization. The authors quantify the scenes 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][START_REF] Ye | Foreground-background separation from video clips via motion-assisted matrix restoration[END_REF] propose 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 that each pixel belongs 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, Yang et al. [START_REF] Ye | Foreground-background separation from video clips via motion-assisted matrix restoration[END_REF] extended MAMR (RMAMR) which is robust approach to noise for practical applications.

SCM-RPCA approach

In this work, we propose to combine some ideas proposed by both Oreifej et al. [START_REF] Oreifej | Simultaneous video stabilization and moving object detection in turbulence[END_REF] and Yang et al. [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]. The weighting matrix proposed by Yang et al. [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] Oreifej et al. [START_REF] Oreifej | Simultaneous video stabilization and moving object detection in turbulence[END_REF] min

L,S,E ||L|| * +λ||Π(S)|| 1 +γ||E|| 2 F s.t. A = L + S + E
Yang et al. [START_REF] Ye | Foreground-background separation from video clips via motion-assisted matrix restoration[END_REF] min

L,S,E ||L|| * +λ||S|| 1 +γ||E|| 2 F s.t. W • A = W • (L + S + E) SCM-RPCA min L,S,E ||L|| * +λ||Π(S)|| 1 +γ||E|| 2 F s.t. A = L + W • S + E Table 1.
Comparison of the proposed method and related works.

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 from the moving objects. A modified version of the original 3WD method was implemented adding the shape constraint as has been done in the RMAMR. Part of the reason we chose to modify the 3WD instead of RMAMR is it capacity to deal with the multimodality of the background. The second contribution of this paper 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 to use 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 request high computational cost, while computing the saliency map is commonly much more fast. Several saliency detection methods have been proposed in the literature [START_REF] Borji | Salient object detection: A survey[END_REF]. In this work, the BMS 1 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 by its speed performance and visual results. Let a sequence of k gray-scale images (frames) I 1 . . . I k captured from a static camera, that is, I ∈ R m×n where m and n denotes the frame resolution (rows by columns). All frames are vectorized into a observation matrix A = [vec(I 1 ) . . . vec(I k )], where A ∈ R mn×k and mn = (m × n). Our decomposition can be formulated as:

(1) min

L,S,E ||L|| * + λ||Π(S)|| 1 + γ||E|| 2 F , s.t. A = L + W • S + E
where Π ∈ R mn×k and W ∈ [0, 1] mn×k are the confidence map and shape constraint (binary map), respectively, and "•" denotes element-wise multiplication of two matrix. As explained previously, the confidence map Π reinforce the pixels belonging from the moving objects and the shape constraint W defines the region of interest. Table 1 shows 1 http://cs-people.bu.edu/jmzhang/BMS/BMS.html Algorithm 1 Algorithm for solving SCM-RPCA.

Input: Observation A ∈ R mn×k Confidence Map Π ∈ R mn×k Shape Constraint W ∈ [0, 1] mn×k Output: Background L ∈ R mn×k Foreground S ∈ R mn×k Noise E ∈ R mn×k while not converged do Υ = β -1 t Yt U RV T = svd(A -Lt -Et + Υ) Lt+1 = U s (1/β t ) (R)V T St+1 = W • s (λ/β t Π) (A -Lt+1 -Et + Υ) κ = (1 + 2γ β t ) -1 Et+1 = κ(A -Lt+1 -St+1 + Υ) Z = At+1 -Lt+1 -St+1 -Et+1 Yt+1 = Yt + βtZ βt+1 = ρβt t = t + 1 end
the comparison of the proposed method between Oreifej et al. [START_REF] Oreifej | Simultaneous video stabilization and moving object detection in turbulence[END_REF] and Yang et al. [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]. 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].

Solving the SCM-RPCA

To solve the Equation 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 convert the constrained optimization problem to the minimization of the augmented Lagrange function:

L(L, S, E, Y ) = ||L|| * +λ||Π(S)|| 1 +γ||E|| 2 F + < Y, A -L -W • S -E) > + β 2 ||(A -L -W • S -E)|| 2 F ( 2
)
where Y ∈ R mn×k 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 solve L, S, E and Y alternatingly:

L t+1 = argmin L L(L, S t , E t , Y t ), S t+1 = argmin S L(L t+1 , S, E t , Y t ), E t+1 = argmin E L(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 (3)
where Z ∈ R mn×k is the residuals. Then, a closed form solution for each of minimization problems can be defined by: [START_REF] Zhang | Exploiting surroundedness for saliency detection: a boolean map approach[END_REF], (c) ground truth, (d) proposed approach, (e) 3WD [START_REF] Oreifej | Simultaneous video stabilization and moving object detection in turbulence[END_REF], and (f) RMAMR [START_REF] Ye | Foreground-background separation from video clips via motion-assisted matrix restoration[END_REF]. The top 3 best algorithms (organized by rank) from Table 2 was chosen. The true positives (T P ) pixels are in white, true negatives (T N ) pixels in black, false positives (F P ) pixels in red and false negatives (F N ) pixels in green.

(a) (b) (d) (e) (f ) (c)
Υ = β -1 t Y t , U RV T = svd(A -L t -E t + Υ), L t+1 = U s (1/βt) (R)V T , S t+1 = W • s (λ/βtΠ) (A -L t+1 -E t + Υ), κ = (1 + 2γ β t ) -1 , E t+1 = κ(A -L t+1 -S t+1 + Υ) (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) (5)
where s (.) (.) is applied in a matrix X in an element-wise manner. The main steps of our proposed algorithm are shown in Algorithm 1. Usually the convergence is done when (||Z|| F /||A|| F ) < (where is the error tolerance), or when the # of iterations is reached. The parameters λ and γ are scalars and defines the weighting parameter for the sparse and noise component, respectively, and ρ is a constant scalar and growth factor for the β parameter. 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 1. In this work, λ, γ, ρ, and β 0 were defined empirically as 2, 1/||A|| 2 , 1.25, and 5/ √ m, respectively.

Definition of shape and confidence map

In this work, 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 Yang et al. [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]. Let a sequence of k saliency maps denoted by M 1 . . . M k where M ∈ R m×n , so:

(6a) Π = [vec(norm(M 1 )) . . . vec(norm(M k ))] (6b) W = [vec(thresh(M 1 )) . . . vec(thresh(M k ))]
where norm(.) denotes the min-max normalization, scaling all entries of M between 0 and 1 by:

(7) norm(M (i,j) ) = M (i,j) -M min M max -M min
with M min and M max the minimum value and the maximum value of the matrix M , respectively, and M (i,j) the matrix element located in the row i ∈ [1 . . . m] and column j ∈ [1 . . . n]. Subsequently, thresh(.) denotes the thresholding function defined as:

(8) thresh(M (i,j) ) = 1 if (0.5M (i,j) ) 2 < µ 0 otherwise
where µ = 0.5η(std(vec(M )))2 , and std(.) denotes the standard deviation of a data vector. In this work, η 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 Dataset 2 proposed by Mahadevan and Vasconcelos [START_REF] Mahadevan | Spatiotemporal saliency in dynamic scenes[END_REF] and three videos from MarDT data set 3 proposed by Bloisi et al. [START_REF] Bloisi | Mar -maritime activity recognition dataset[END_REF] was selected.

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.

The UCSD and MarDT data sets consists of 18 and 28 video sequences, respectively, both acquired from a stationary and moving camera, but in this work (due to page limits) we have selected only the four sequences from UCSD and three sequences from MarDT.

We have compared the SCM-RPCA with its direct competitors: the orignal PCP proposed by Candès et al. [START_REF] Candes | Robust principal component analysis?[END_REF], the stable PCP proposed by Aravkin et al. [START_REF] Aravkin | A variational approach to stable principal component pursuit[END_REF], 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 Yang 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 singleconstrained RPCA. Is important to note that all constrained RPCA evaluated in this paper have been used the saliency maps as the input constraint.

In the next sections, we report the quality evaluation and the benchmark evaluation of the selected algorithms.

Quality evaluation

Figures 2 and3 show the visual results for background subtraction task in the UCSD and MarDT data sets, respec-tively. 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 2 show that the SCM-RPCA outperforms the previous methods, with the highest F -measure average over the selected video sequences. Each metric is described in Table 4. As can be seen from Figures 2 and3, and Table 2, the combination with confidence map and shape constraint can reduce the amount of false positive pixels.

Benchmark evaluation

In Table 3, we report our benchmark 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 3 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.

Conclusion

In this paper 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 quality evaluation, the combination with confidence map and shape constraint can reduce the amount of false positive pixels. In addition, our benchmark evaluation demonstrates that the proposed algorithm have a slightly change in the number of iterations and computation time compared to the original 3WD.

In the future work, we will investigate how spatiotemporal saliency detectors can help the proposed approach to improve the foreground detection. In this work, 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 built separately these constraints. Furthermore, we are interested in adapting the proposed algorithm to perform the decomposition incrementally as in Online RPCA [START_REF] Feng | Online robust pca via stochastic optimization[END_REF]. MATLAB codes available at 4 .

Figure 1 .

 1 Figure1. 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 (or region of interest) (d) is built by thresholding this one, and (e) the foreground mask obtained by thresholding the RPCA sparse component. Note that in some environments where a) the object of interest move 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, the double constraints (confidence map and shape) can be built from two different types of source (i.e. from spatial, temporal, or spatio-temporal information), but in this work we focus only on spatial saliency maps.

Figure 2 .

 2 Figure 2. Visual comparison on background subtraction results over three scenes of UCSD data set. From top to bottom: surfers, boats and birds. From left to right: (a) input frame, (b) saliency map generated by BMS[START_REF] Zhang | Exploiting surroundedness for saliency detection: a boolean map approach[END_REF], (c) ground truth, (d) proposed approach, (e) 3WD[START_REF] Oreifej | Simultaneous video stabilization and moving object detection in turbulence[END_REF], and (f) RMAMR[START_REF] Ye | Foreground-background separation from video clips via motion-assisted matrix restoration[END_REF]. The top 3 best algorithms (organized by rank) from Table2was chosen. The true positives (T P ) pixels are in white, true negatives (T N ) pixels in black, false positives (F P ) pixels in red and false negatives (F N ) pixels in green.

Figure 3 .

 3 Figure 3. Visual results of SCM-RPCA over three scenes of MarDT data set. 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. The true positives (T P ) pixels are in white, true negatives (T N ) pixels in black, false positives (F P ) pixels in red and false negatives (F N ) pixels in green.

Table 2 .

 2 Quantitative results on four videos of UCSD Background Subtraction Dataset[START_REF] Mahadevan | Spatiotemporal saliency in dynamic scenes[END_REF].

		Birds			Surfers			Boats			Ocean		Rank
	Re	P r	F 1	Re	P r	F 1	Re	P r	F 1	Re	P r	F 1	Avg.F 1
	PCP [7] 0.842 0.094 0.170 0.754 0.075 0.137 0.814 0.100 0.178 0.748 0.115 0.200	0.171
	Lag-SPCP-QN [1] 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 [15] 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 [12] 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 3 .

 3 Benchmark evaluation over four videos of UCSD Background Subtraction Dataset[START_REF] Mahadevan | Spatiotemporal saliency in dynamic scenes[END_REF]. 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).

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

(* + Iteration limit 100 reached.

Table 4 .

 4 Precision, Recall and F-Measure metrics.

http://www.svcl.ucsd.edu/projects/background\ _subtraction/ucsdbgsub\_dataset.htm

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


Andrews Sobral

Thierry Bouwmans

El-Hadi Zahzah

Comparison of Matrix Completion Algorithms for Background Initialization in Videos

Keywords: matrix completion, background modeling, background initialization Matrix

published or not. The documents may come

Introduction

Background subtraction (BS) is an important step in many computer vision systems to detect moving objects. This basic operation consists of separating the moving objects called "foreground" from the static information called "background" [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]. The BS is commonly used in video surveillance applications to detect persons, vehicles, animals, etc., before operating more complex processes for intrusion detection, tracking, people counting, etc. Typically the BS process includes the following steps: a) background model initialization, b) background model maintenance and c) foreground detection. With a focus on the step (a), the BS initialization consists in creating a background model. In a simple way, this can be done by setting manually a static image that represents the background. The main reason is that it is often assumed that initialization can be achieved by exploiting some clean frames at the beginning of the sequence. 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 [START_REF] Maddalena | Background model initialization for static cameras[END_REF].

The main challenge is to obtain a first background model when more than half of the video frames contain foreground objects. Some authors suggest 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. Practically, some algorithms are: (1) batch ones using N training frames (consecutive or not), (2) incremental with known N or (3) progressive ones 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 modes and the complexity of their background models. However, BS initialization has also been achieved by many other methodologies [START_REF] Maddalena | Background model initialization for static cameras[END_REF][START_REF] Bouwmans | Traditional and recent approaches in background modeling for foreground detection: An overview[END_REF]. 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 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. In Special Isssue on Background Models Challenge[END_REF]. 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.

In this paper, the initialization of the background model is addressed as a matrix completion problem. The matrix completion aims at recovering a low rank matrix from partial observations of its entries. The image sequence (or video) is represented as a partially observed real-valued matrix. Figure 1 shows the proposed framework. First, a simple joint motion-detection and frame-selection operation is done. The redundant frames are eliminated, and the moving regions are represented with zeros in our observation matrix. This operation is described in the Section 2. The second stage involves evaluating nine popular matrix completion algorithms with the Scene Background Initialization (SBI) data set [START_REF] Maddalena | Towards benchmarking scene background initialization[END_REF] (see Section 3). This enables to analyze them with respect to the background model challenges. Finally, in Sections 4 and 5, the experimental results are shown as well as conclusions.

Throughout the paper, we use the following notations. Scalars are denoted by lowercase letters, e.g., x; vectors are denoted by lowercase boldface letters, e.g., x; matrices by uppercase boldface, e.g., X. In this paper, only real-valued data are considered.

Joint Motion Detection and Frame Selection

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 its gray-scale representation. So, let a sequence of N gray-scale images (frames) I 0 . . . I N captured from a static camera, that is, I ∈ R m×n where m and n denotes the frame resolution (rows by columns). The difference between two consecutive frames (motion detection step) is calculated by: Fig. 2. Illustration of frame selection operation. The normalized vector (in blue) shows the difference between two consecutive frames. The derivative vector draw how much the normalized vector changes (in red), and then it is thresholded and the frames are selected (in orange).

D t = (I t -I t-1 ) 2 | t = 1,...,N , (1)
where D t ∈ R m×n 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 , for t = 1, . . . , N , is stored in a vector d ∈ R N whose t-th element is given by:

d t = m i=1 n j=1 D t (i, j), (2)
where D t (i, j) is the matrix element located in the row i ∈ [1, . . . , m] and column j ∈ [1, . . . , n]. Then, the vector d is normalized between 0 and 1 by:

d = d t -d min d max -d min | t = 1,...,N , (3)
where d min and d max denotes the minimum value and the maximum value of the vector d. The frame selection step is done by calculating the derivative of d by:

d = d dt d, (4)
Next, the vector d is also normalized by Equation 3 and represented by d . Finally, the index of the more relevant frames are given by thresholding d :

(5) y = 1 if | d -μ | > τ 0 otherwise ,
where μ denotes the mean value of the vector d , and τ ∈ [0, . . . , 1] controls the threshold operator. In this paper, R ≤ N represent the set of all frames where y = 1, and the parameter τ was chosen experimentally for each scene: τ = 0.025 for HallAndMonitor, τ = 0.05 for HighwayII, τ = 0.10 for HighwayI, and τ = 0.15 to all other scenes. Figure 1 illustrates our frame selection operation, in this example, with τ = 0.025, only 92 relevant frames are selected from a total of 296 frames (68, 92% of reduction). In the next section, the matrix completion process is described.

Matrix Completion

As explained previously, the matrix completion aims to recover a low rank matrix from partial observations of its entries. Considering the general form of low rank matrix completion, the optimization problem is to find a matrix L ∈ R n1×n2 with minimum rank that best approximates the matrix A ∈ R n1×n2 . Candès and Recht [START_REF] Candès | Exact matrix completion via convex optimization[END_REF] show that this problem can be formulated as: minimize rank(A),

subject to P Ω (A) = P Ω (L), (6)
where rank(A) is equal to the rank of the matrix A, 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 Ω. Later, Candès and Recht [START_REF] Candès | Exact matrix completion via convex optimization[END_REF] propose to replace the rank(.) function with the nuclear norm ||A|| * = r i=1 σ i where σ 1 , σ 2 , ..., σ r are the singular values of A and r is the rank of A. The nuclear norm make the problem tractable and Candès and Recht [START_REF] Candès | Exact matrix completion via convex optimization[END_REF] have 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] propose an algorithm based on soft singular value thresholding (SVT) to solve this convex relaxation problem. However, in real world application the observed entries may be noisy. In order to make the Equation 6 robust to noise, Candès and Plan [START_REF] Candès | Matrix completion with noise[END_REF] propose a stable matrix completion approach. The equality constraint is replaced by ||P Ω (A -L)|| F ≤ , where ||.|| F denotes the Frobenious norm and is an upper bound on the noise level. Recently, several matrix completion algorithms have been proposed to deal with this challenge, and a complete review can be found in [START_REF] Zhou | Low-rank modeling and its applications in image analysis[END_REF].

In this paper, we address the background model initialization as a matrix completion problem. Once frame selection process is done, the moving regions of the R selected frames are determined by:

(7) M k (i, j) = 1 if 0.5(D k (i, j)) 2 > β 0 otherwise
where k ∈ R, and β is the thresholding parameter (in this paper, β = 1e -3 for all experiments). Next, the moving regions of each selected frame are filled with zeros by I k • M k , where M k denotes the complement of M k , and • denotes the elementwise 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(I 1 ) . . . vec(I k )], where A ∈ R n1×n2 , n1 = (m × n), and n2 = k. Figure 3 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 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 n1×1 , and then reshaped into a matrix B ∈ R m×n .

Experimental results

In order to evaluate the proposed approach, nine matrix completion algorithms have been selected, and they are listed in Table 1. The algorithms were grouped in two categories, as well as its main techniques (following the same definition of Zhou et al. [START_REF] Zhou | Low-rank modeling and its applications in image analysis[END_REF]). In this paper, the Scene Background Initialization (SBI) data set was chosen for the background initialization task. The data set contains seven image sequences and corresponding ground truth backgrounds. It provides also MATLAB scripts for evaluating background initialization results in terms of eight metrics 3 . Figure 4 show the visual results for the top three best matrix completion algorithms, and Table 2 reports the quantitative results of each algorithm over the data set 4 . The algorithms are ranked as follow: 1) for each algorithm we calculate its rank position for each metric, we call it as metric rank (i.e. RMAMR have the first position for the AGE metric in the HallAndMonitor scene), next, 2) we sum the rank position value of each algorithm over the eight 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 MC algorithm, then we calculate its rank position over the sum. As we can see, the experimental results show the good performance of LRGeomCG [START_REF] Vandereycken | Low-rank matrix completion by Riemannian optimization[END_REF] method over its direct competitors. Furthermore, in most cases the matrix completion algorithms outperform the traditional approaches such as Mean [START_REF] Lai | A fast and accurate scoreboard algorithm for estimating stationary backgrounds in an image sequence[END_REF], Median [START_REF] Cucchiara | Detecting objects, shadows and ghosts in video streams by exploiting color and motion information[END_REF] and MoG [START_REF] Zivkovic | Improved adaptive gaussian mixture model for background subtraction[END_REF] as can be seen in the full experimental evaluation available at https://sites.google.com/site/mc4bmi/.

Conclusion

In this paper, we have evaluated nine recent matrix completion algorithms for the background initialization problem. Given a sequence of images, the key idea is to eliminate the redundant frames, and consider its moving regions as non-observed values. This approach results in a matrix completion problem, and the background model can be recovered even with the presence of missing entries. The experimental results on the SBI data set shows the comparative evaluation of these recent methods, and highlights the good performance of LRGeomCG [START_REF] Vandereycken | Low-rank matrix completion by Riemannian optimization[END_REF] method over its direct competitors. Finally, MC shows a nice potential for background modeling initialization in video surveillance. Future research may concern to evaluate incremental and real-time approaches of matrix completion in streaming videos.

Fig. 1 .

 1 Fig.1. Block diagram of the proposed approach. Given an input image, a joint motion detection and frame selection operation is applied. Next, a matrix completion algorithm tries to recover the background model from the partially observed matrix. In this paper, the processes described here are conducted in a batch manner.

Fig. 3 .

 3 Fig. 3. Illustration of the matrix completion process. From the left to the right: a) the selected frames in vectorized form (our observation matrix), b) the moving regions are represented by non-observed entries (black pixels), c) the moving regions filled with zeros (modified version of the observation matrix), and d) the recovered matrix after the matrix completion process.

Fig. 4 .

 4 Fig. 4. Visual comparison for the background model initialization. From top to bottom: 1) example of input frame, 2) background model ground truth, and background model results for the top 3 best ranked MC algorithms: 3) LRGeomCG, 4) LMaFit, and 5) RMAMR.

Table 1 .

 1 List of low-rank matrix completion algorithms evaluated in this paper.

	Category	Method	Main techniques	Reference
	Rank Minimization	IALM RMAMR	Augmented Lagrangian [10, Lin et al. (2010)] Augmented Lagrangian [20, Ye et al. (2015)]
		SVP	Hard thresholding	[13, Meka et al. (2009)]
		OptSpace	Grassmannian	[8, Keshavan et al. (2010)]
		LMaFit	Alternating	[19, Wen et al. (2012)]
	Matrix Factorization	ScGrassMC Grassmannian	[14, Ngo and Saad (2012)]
		LRGeomCG Riemannian	[17, Vandereycken (2013)]
		GROUSE Online algorithm	[1, Balzano et al. (2013)]
		OR1MP	Matching pursuit	[18, Wang et al. (2015)]

Table 2 .

 2 Quantitative results over SBI data set, and the global rank for each matrix completion method. The bold metric values show the best score for each metric. For each scene, the results are ordered by the rank column.

				HallAndMonitor				Foliage
	Method	AGE	EPs pEPs CEPs pCEPS MSSSIM PSNR CQM Scene Rank	Method	AGE	EPs pEPs CEPs pCEPS MSSSIM PSNR CQM Scene Rank
	LRGeomCG 2.0550 190 0.0022	0	0.0000 0.9938 37.9811 46.3255	1	GROUSE	26.4036 17840 0.6194 13271 0.4608 0.8957 18.4042 33.4059	1
	RMAMR	2.0499 190 0.0022	0	0.0000 0.9938 37.9755 46.3222	2	LRGeomCG 26.4006 18074 0.6276 13459 0.4673 0.8970 18.4522 33.2733	2
	LMaFit	2.0583 194 0.0023	0	0.0000 0.9938 37.8487 46.2893	3	LMaFit	26.4093 18070 0.6274 13442 0.4667 0.8970 18.4490 33.2663	2
	ScGrassMC 2.0693 193 0.0023	0	0.0000 0.9937 37.9046 46.2838	4	RMAMR	26.5144 18146 0.6301 13548 0.4704 0.8965 18.4160 33.2392	4
	GROUSE	2.2201 191 0.0023	0	0.0000 0.9923 37.5319 45.8794	5	ScGrassMC 29.2509 19189 0.6663 15385 0.5342 0.8645 17.4636 33.2173	5
	OR1MP	2.2025 374 0.0044	0	0.0000 0.9926 34.9021 44.8283	6	OR1MP	31.3678 19094 0.6630 15257 0.5298 0.8221 16.7364 33.0468	5
	IALM	3.6143 2336 0.0277 1190 0.0141 0.9627 30.5907 40.9249	7	OptSpace	32.1405 19156 0.6651 15234 0.5290 0.8656 16.6268 31.4830	7
	SVP	4.1486 3230 0.0382 1574 0.0186 0.9474 28.2921 41.4398	8	IALM	31.6036 19451 0.6754 14986 0.5203 0.7473 16.8016 31.0114	8
	OptSpace	6.7051 5950 0.0704 2694 0.0319 0.9299 25.1834 37.6430	9	SVP	35.3522 19469 0.6760 16003 0.5557 0.7556 15.6496 33.1273	9
					HighwayI				PeopleAndFoliage
	Method	AGE	EPs pEPs CEPs pCEPS MSSSIM PSNR CQM Scene Rank	Method	AGE	EPs pEPs CEPs pCEPS MSSSIM PSNR CQM Scene Rank
	LRGeomCG 2.7715 192 0.0025 16 0.0002 0.9769 35.8950 58.6193	1	LRGeomCG 38.7467 64150 0.8353 59210 0.7710 0.8505 15.1638 27.6167	1
	RMAMR	2.7601 193 0.0025 16 0.0002 0.9769 35.8899 58.6283	1	OptSpace	41.8200 60020 0.7815 53183 0.6925 0.7535 14.1746 25.9930	2
	LMaFit	2.7781 196 0.0026 16 0.0002 0.9770 35.8636 58.6193	3	IALM	42.9444 63161 0.8224 58560 0.7625 0.7951 14.1751 27.8900	2
	ScGrassMC 3.2306 1088 0.0142 593 0.0077 0.9714 33.4838 58.5694	4	GROUSE	40.3918 63556 0.8276 57097 0.7435 0.8130 14.6485 26.5857	4
	GROUSE	6.1324 621 0.0081 138 0.0018 0.9614 30.3643 56.2861	5	OR1MP	42.8580 62335 0.8117 56809 0.7397 0.7861 14.0424 26.7015	4
	OR1MP	3.9587 1202 0.0157 691 0.0090 0.9637 32.4145 57.8051	6	ScGrassMC 39.6045 64076 0.8343 58991 0.7681 0.8472 14.9449 27.6499	6
	IALM	6.4223 1836 0.0239 837 0.0109 0.9507 29.5142 57.9214	7	LMaFit	38.7738 64155 0.8354 59220 0.7711 0.8501 15.1567 27.6143	7
	SVP	6.9160 5694 0.0741 2530 0.0329 0.9095 27.6621 53.1073	8	RMAMR	38.8234 64189 0.8358 59276 0.7718 0.8502 15.1484 27.5987	8
	OptSpace	14.7067 19754 0.2572 13930 0.1814 0.7957 22.8624 43.8142	9	SVP	45.0733 63916 0.8322 58803 0.7657 0.7644 13.6320 27.0416	9
					HighwayII				Snellen
	Method	AGE	EPs pEPs CEPs pCEPS MSSSIM PSNR CQM Scene Rank	Method	AGE	EPs pEPs CEPs pCEPS MSSSIM PSNR CQM Scene Rank
	LRGeomCG 2.6840 268 0.0035	4	0.0001 0.9919 35.7076 46.1997	1	ScGrassMC 43.8219 17838 0.8602 16070 0.7750 0.8469 14.3702 37.6451	1
	RMAMR	2.7003 271 0.0035	5	0.0001 0.9919 35.6695 46.2002	2	LRGeomCG 41.8853 18621 0.8980 17379 0.8381 0.8807 14.8166 37.4253	2
	LMaFit	2.6919 275 0.0036	7	0.0001 0.9919 35.5752 46.0673	3	OptSpace	49.2605 16619 0.8015 15292 0.7375 0.7419 12.8053 29.4492	2
	ScGrassMC 2.9622 360 0.0047	2	0.0000 0.9888 34.6782 46.1585	4	LMaFit	41.8688 18623 0.8981 17387 0.8385 0.8809 14.8203 37.4234	4
	IALM	4.9261 306 0.0040	2	0.0000 0.9830 31.5964 46.1296	5	GROUSE	41.8123 18629 0.8984 17403 0.8393 0.8809 14.8421 37.5570	5
	OR1MP	3.2510 843 0.0110 102 0.0013 0.9888 32.2682 42.0740	6	IALM	46.0978 18433 0.8889 17084 0.8239 0.8330 14.0292 37.1551	6
	SVP	4.7779 945 0.0123 153 0.0020 0.9813 30.4590 41.8017	7	OR1MP	50.4572 18084 0.8721 16677 0.8043 0.7504 13.1602 36.2566	7
	GROUSE	4.3955 1751 0.0228 700 0.0091 0.9756 31.5542 45.6062	8	SVP	54.6990 17649 0.8511 16189 0.7807 0.7105 12.5506 35.6896	7
	OptSpace	8.6231 4722 0.0615 1307 0.0170 0.9279 25.8722 36.7496	9	RMAMR	42.0476 18625 0.8982 17395 0.8389 0.8800 14.7872 37.3821	9
					CaVignal		Global rank over all scenes
	Method	AGE	EPs pEPs CEPs pCEPS MSSSIM PSNR CQM Scene Rank	Method Global rank
	LMaFit	11.9504 3788 0.1393 2700 0.0993 0.9027 24.3417 39.8279	1	LRGeomCG	1
	LRGeomCG 11.9506 3789 0.1393 2700 0.0993 0.9026 24.3415 39.8279	2	LMaFit	2
	RMAMR	12.0081 3817 0.1403 2715 0.0998 0.9027 24.3147 39.8083	3	RMAMR	3
	GROUSE	12.8057 3624 0.1332 2205 0.0811 0.8846 23.2489 38.8799	4	ScGrassMC	3
	ScGrassMC 12.3375 4084 0.1501 2942 0.1082 0.8916 23.9111 39.8237	5	GROUSE	5
	IALM	12.2618 4764 0.1751 3531 0.1298 0.8779 23.7957 40.6135	6	IALM	6
	OR1MP	12.5266 4455 0.1638 3356 0.1234 0.8855 23.7925 39.7716	7	OR1MP	6
	SVP	13.2230 5628 0.2069 3982 0.1464 0.8760 23.3352 39.8300	8	OptSpace	8
	OptSpace	14.1744 6176 0.2271 4214 0.1549 0.8927 23.0940 39.8662	9	SVP	9

Please, refer to http://sbmi2015.na.icar.cnr.it/ for a complete description of each metric.

Full experimental evaluation and related source code can be found in the main website: https://sites.google.com/site/mc4bmi/