Background Subtraction Using Low Rank
and Group Sparsity Constraints
Xinyi Cui1, Junzhou Huang2, Shaoting Zhang1, and Dimitris N. Metaxas1
1 CS Dept., Rutgers University
Piscataway, NJ 08854, USA
2 CSE Dept., Univ. of Texas at Arlington
Arlington, TX, 76019, USA
{xycui,shaoting,dnm}@cs.rutgers.edu,
jzhuang@uta.edu
Abstract. Background subtraction has been widely investigated in recent
years. Most previous work has focused on stationary cameras. Recently,
moving cameras have also been studied since videos from mobile
devices have increased significantly. In this paper, we propose a unified
and robust framework to effectively handle diverse types of videos,
e.g., videos from stationary or moving cameras. Our model is inspired
by two observations: 1) background motion caused by orthographic cameras
lies in a low rank subspace, and 2) pixels belonging to one trajectory
tend to group together. Based on these two observations, we introduce
a new model using both low rank and group sparsity constraints. It is
able to robustly decompose a motion trajectory matrix into foreground
and background ones. After obtaining foreground and background trajectories,
the information gathered on them is used to build a statistical
model to further label frames at the pixel level. Extensive experiments
demonstrate very competitive performance on both synthetic data and
real videos.
1 Introduction
Background subtraction is an important preprocessing step in video surveillance
systems. It aims to find independent moving objects in a scene. Many algorithms
have been proposed for background subtraction under stationary. In recent years,
videos from moving cameras have also been studied [1] because the number of
moving cameras (such as smart phones and digital videos) has increased significantly.
However, handling diverse types of videos robustly is still a challenging
problem (see the related work in Sec. 2). In this paper, we propose a unified
framework for background subtraction, which can robustly deal with videos from
stationary or moving cameras with various number of righd/non-rigid objects.
The proposed method for background subtraction is based on two sparsity
constraints applied on foreground and background levels, i.e., low rank [2] and
group sparsity constraints [3]. It is inspired by recently proposed sparsity theories
[4, 5]. There are two “sparsity” observations behind our method. First, when
A. Fitzgibbon et al. (Eds.): ECCV 2012, Part I, LNCS 7572, pp. 612–625, 2012.
c
Springer-Verlag Berlin Heidelberg 2012
Background Subtraction Using Low Rank and Group Sparsity Constraints 613
the scene in a video does not have any foreground moving objects, video motion
has a low rank constraint for orthographic cameras [6]. Thus the motion of
background points forms a low rank matrix. Second, foreground moving objects
usually occupy a small portion of the scene. In addition, when a foreground
object is projected to pixels on multiple frames, these pixels are not randomly
distributed. They tend to group together as a continuous trajectory. Thus these
foreground trajectories usually satisfy the group sparsity constraint.
These two observations provide important information to differentiate independent
objects from the scene. Based on them, the video background subtraction
problem is formulated as a matrix decomposition problem. First, the video
motion is represented as a matrix on trajectory level (i.e. each row in the motion
matrix is a trajectory of a point). Then it is decomposed into a background
matrix and a foreground matrix, where the background matrix is low rank,
and the foreground matrix is group sparse. This low rank constraint is able to
automatically model background from both stationary and moving cameras, and
the group sparsity constraint improves the robustness to noise.
The trajectories recognized by the above model can be further used to label
a frame into foreground and background at the pixel level. Motion segments on
a video sequence are generated using fairly standard techniques. Then the color
and motion information gathered from the trajectories is employed to classify
the motion segments as foreground or background. Our approach is validated on
various types of data, i.e., synthetic data, real-world video sequences recorded
by stationary cameras or moving cameras and/or nonrigid foreground objects.
Extensive experiments also show that our method compares favorably to the
recent state-of-the-art methods.
The main contribution of the proposed approach is a new model using low
rank and group sparsity constraints to differentiate foreground and background
motions. This approach has three merits: 1) The low rank constraint is able
to handle both static and moving cameras; 2)The group sparsity constraint
leverages the information of neighboring pixels, which makes the algorithm
robust to random noise; 3) It is relatively insensitive to parameter settings.
2 Related Work
Background Subtraction. A considerable amount of work has studied the
problem of background subtraction in videos. Here we review a few related
work, and please refer to [7] for comprehensive surveys. The mainstream in
the research area of background subtraction focuses on stationary cameras.
The earliest background subtraction methods use frame difference to detect
foreground [8]. Many subsequent approaches have been proposed to model the
uncertainty in background appearance, such as, but not limited to,W4 [9], single
gaussian model [10], mixture of gaussian [11], non-parametric kernel density [12]
and joint spatial-color model [13]. One important variation in stationary camera
based research is the background dynamism. When the camera is stationary, the
background scene may change over time due to many factors (e.g. illumination
614 X. Cui et al.
a) Input video
b) Tracked
trajectories
c) Trajectory
matrix
d) Decomposed
trajectories
e) Decomposed trajectories
on original video
f) Optical flow g) Motion segments
h) Output
Trajectory level separation
Pixel level labeling
Fig. 1. The framework. Our method takes a raw video sequence as input, and produces
a binary labeling as the output. Two major steps are trajectory level separation and
pixel level labeling.
changes, waves in water bodies, shadows, etc). Several algorithms have been
proposed to handle dynamic background [14–16].
The research for moving cameras has recently attracted people’s attention.
Motion segmentation approaches [17, 18] segment point trajectories based on
subspace analysis. These algorithms provide interesting analysis on sparse trajectories,
though do not output a binary mask as many background subtraction
methods do. Another popular way to handle camera motion is to have strong
priors of the scene, e.g., approximating background by a 2D plane or assuming
that camera center does not translate [19, 20], assuming a dominant plane [21],
etc. [22] propose a method to use belief propagation and Bayesian filtering
to handle moving cameras. Different from their work, long-term trajectories
we use encode more information for background subtraction. Recently, [1] has
been proposed to build a background model using RANSAC to estimate the
background trajectory basis. This approach assumes that the background motion
spans a three dimensional subspace. Then sets of three trajectories are randomly
selected to construct the background motion space until a consensus set is
discovered, by measuring the projection error on the subspace spanned by the
trajectory set. However, RANSAC based methods are generally sensitive to
parameter selection, which makes it less robust when handling different videos.
Group sparsity [23, 24] and low rank constraint [2] have also been applied to
background subtraction problem. However, these methods only focus on stationary
camera and their constraints are at spatial pixel level. Different from their
work, our method is based on constraints in temporal domain and analyzing the
trajectory properties.
3 Methodology
Our background subtraction algorithm takes a raw video sequence as input,
and generates a binary labeling at the pixel level. Fig. 1 shows our framework.
It has two major steps: trajectory level separation and pixel level labeling. In
Background Subtraction Using Low Rank and Group Sparsity Constraints 615
the first step, a dense set of points is tracked over all frames. We use an offthe-
shelf dense point tracker [25] to produce the trajectories. With the dense
point trajectories, a low rank and group sparsity based model is proposed to
decompose trajectories into foreground and background. In the second step,
motion segments are generated using optical flow [26] and graph cuts [27].
Then the color and motion information gathered from the recognized trajectories
builds statistics to label motion segments as foreground or background.
3.1 Low Rank and Group Sparsity Based Model
Notations: Given a video sequence, k points are tracked over l frames. Each
trajectory is represented as pi = [x1i, y1i, x2i, y2i, ...xli, yli] ∈ R1×2l, where x and
y denote the 2D coordinates in each frame. The collection of k trajectories is
represented as a k × 2l matrix, φ = [pT1
, pT2
, ..., pTl
]T, φ∈ Rk×2l.
In a video with moving foreground objects, a subset of k trajectories comes
from the foreground, and the rest belongs to the background. Our goal is to
decompose tracked k trajectories into two parts: m background trajectories and
n foreground trajectories. If we already know exactly which trajectories belong
to the background, then foreground objects can be easily obtained by subtracting
them from k trajectories, and vice versa. In other words, φ can be decomposed
as:
φ = B + F, (1)
where B ∈ Rk×2l and F ∈ Rk×2l denote matrices of background and foreground
trajectories, respectively. In the ideal case, the decomposed foreground matrix
F consists of n rows of foreground trajectories and m rows of flat zeros, while
B has m rows of background trajectories and n rows of zeros.
Eq. 1 is a severely under-constrained problem. It is difficult to find B and F
without any prior information. In our method, we incorporate two effective priors
to robustly solve this problem, i.e., the low rank constraint for the background
trajectories and the group sparsity constraint for the foreground trajectories.
Low Rank Constraint for the Background. In a 3D structured scene
without any moving foreground object, video motion solely depends on the scene
and the motion of the camera. Our background modeling is inspired from the
fact that B can be factored as a k×3 structure matrix of 3D points and a 3×2l
orthogonal matrix [6]. Thus the background matrix is a low rank matrix with
rank value at most 3. This leads us to build a low rank constraint model for the
background matrix B:
rank(B) ≤ 3, (2)
Another constraint has been used in the previous research work using RANSAC
based method [1]. This work assumes that the background matrix is of rank
three: rank(B) = 3. This is a very strict constraint for the problem. We refer
the above two types of constraints as the General Rank model (GR) and the
Fixed Rank model (FR). Our GR model is more general and handles more
situations. A rank-3 matrix models 3D scenes under moving cameras; a rank-2
616 X. Cui et al.
matrix models a 2D scene or 3D scene under stationary cameras; a rank-1 matrix
is a degenerated case when scene only has one point. The usage of GR model
allows us to develop a unified framework to handle both stationary cameras and
moving cameras. The experiment section (Sec. 4.2) provides more analysis on
the effectiveness of the GR model when handling diverse types videos.
Group Sparsity Constraint for the Foreground. Foreground moving objects,
in general, occupy a small portion of the scene. This observation motivates
us to use another important prior, i.e., the number of foreground trajectories
should be smaller than a certain ratio of all trajectories: m ≤ αk, where α
controls the sparsity of foreground trajectories.
Another important observation is that each row in φ represents one trajectory.
Thus the entries in φ are not randomly distributed. They are spatially clustered
within each row. If one entry of the ith row φi belongs to the foreground,
the whole φi is also in the foreground. This observation makes the foreground
trajectory matrix F satisfy the group sparsity constraint:
F2,0 ≤ αk, (3)
where ·2,0 is the mixture of both L2 and L0 norm. The L2 norm constraint is
applied to each group separately (i.e., each row of F). It ensures that all elements
in the same row are either zero or nonzero at the same time. The L0 norm
constraint is applied to count the nonzero groups/rows of F. It guarantees that
only a sparse number of rows are nonzero. Thus this group sparsity constraint not
only ensures that the foreground objects are spatially sparse, but also guarantees
that each trajectory is treated as one unit. Group sparsity is a powerful tool in
computer vision problems [28, 23]. The standard sparsity constraint, L0 norm,
(we refer this as Std. sparse method) has been intensively studied in recent
years. However, it does not work well for this problem compared to the group
sparsity one. Std. sparse method treats each element of F independently. It does
not consider any neighborhood information. Thus it is possible that points from
the same trajectory are classified into two classes. In the experiment section
(Sec. 4.1), we discuss the advantage of group sparsity constraint over sparsity
constraint through synthetic data analysis, and also show that this constraint
improves the robustness of our model.
Based on the low rank and group sparsity constraints, we formulate our
objective function as:
ˆ B, ˆ F
= argmin
B,F
φ − B − F 2
F
,
s.t. rank(B) ≤ 3, F
2,0 < αk, (4)
where · F is the Frobenius norm. This model leads to a good separation of
foreground and background trajectories. Fig. 2 illustrates our model.
Eq. 4 only has one parameter α, which controls the sparsity of the foreground
trajectories. In general, user-tuning parameter is a key issue for a good model. It
is preferable that the parameters are easy to tune and not sensitive to different
Background Subtraction Using Low Rank and Group Sparsity Constraints 617
= +
Low rank matrix
B=UΣVT
Group sparse
matrix F
…
…
Trajectory
matrix
- 浏览: 964317 次
文章分类
最新评论
-
18335864773:
很多公司项目 都在使用pageoffice 来操作word,e ...
用java生成word文档 -
Gozs_cs_dn:
请问下博主, 怎样将sitemesh3.xsd绑定 sitem ...
SiteMesh3配置 -
Rose_06:
springside4.0quick-start.bat报错原因 -
ilemma:
我也是刚参见工作啊,经理让自学这个,有些东西不太懂,能不能发个 ...
Apache Shiro在Web中的应用 -
shanbangyou:
你废了
程序员上班打酱油的方法
-
递归归并排序
2016-02-11 20:26 312/* MergeSort.java CSC 225 - ... -
java冒泡排序对布尔类型进行排序
2015-12-11 23:06 602QQ 928900200 程序代写 java不能对 ... -
判断宏是否是“安全”的
2014-11-22 22:54 522给了一系列C++的宏定义,问你一个表达式是否是“安全”的。 ... -
C语言求平均值
2014-11-19 19:14 501木其工作室:QQ928900200 Computing I ... -
C语言连连看
2014-11-18 16:34 565(1)定义一个矩阵,随机产生字符布置地图,例如下面这个4x ... -
The Monty Hall Problem
2014-10-19 12:58 610GNG1106 Lab 3The Monty Hall Pro ... -
java类
2014-10-16 08:27 269木其工作室 qq 928900200 You are ... -
ECE/CPSC 3520
2014-10-13 09:49 490ECE/CPSC 3520Fall 2014Software ... -
计算机安全
2014-10-07 14:52 390CS461 MP 1: Due Wednesday 09/17 ... -
java星球机器人建模UML
2014-10-06 22:29 360Your task is to design and imp ... -
数据库sql
2014-10-06 22:25 579service QQ 928900200 ... -
C语言 cgi(3)
2014-08-04 09:17 3261cs3157 – Advanced ProgrammingS ... -
C语言 cgi(2)
2014-08-04 09:10 2811Columbia Universitycs3157 – Ad ... -
C语言cgi(1)
2014-08-04 09:08 3041Columbia Universitycs3157 – Ad ... -
c++ input,output
2014-08-04 08:37 428You should be comfortable w ... -
Array of Objects
2014-08-04 08:30 625You should be comfortable w ... -
bat脚本打开网页
2014-07-13 09:54 844start iexplore "http://ww ... -
java 汉诺塔实现自动演示
2014-07-10 11:53 4411、增加计时功能,显 ... -
代写java程序qq:928900200
2014-06-18 12:46 3学校为全面提升学校教学质量,提高管理水平,决定开发一套小型成 ... -
基于MVC的系统代写
2014-06-16 12:13 408人力资源管理系统 完成系统静态页面设计,页面数 ...
相关推荐
代写C程序 C++ Linux Unix 数据结构 操作系统
为您提供最贴心的服务,小泽竭诚为您服务. 定制,代写都是十元起价,小泽保证在能力范围内,尽量为您提供最精良的代码. ------DreamDimension
西门子SIWAREX FTC例子程序 (失重秤应用)zip,西门子SIWAREX FTC例子程序 (失重秤应用)
代写个人述职报告.docx
这是我从国外知名大学cs专业留学的同学那里收集来的作业资料(英文原版) 【留学生作业代写资料assignment英文原版】java作业之小数据分析
无线充电程序代码全部设计,包括pwm,ad采集
最新律师免费代写起诉状民事诉状WORD范文.docx
这是DBMaker 5.1数据库sample中的一个范例代码,挺简单的,目录中还有一个readme_cn.txt,说的还算清楚易懂,应该很容易用连接到其他数据库上
我写的dsp程序很不错的代码,赚积分不容易,希望大家珍惜我的资源
律师代写遗嘱范本.docx
java+mysql进销存管理系统源代码学习
述职报告代写多少钱.docx
律师代写还款承诺书.docx
代写学生请假条范文.doc
这是我从国外知名大学cs专业留学的同学那里收集来的作业资料(英文原版) 【留学生作业代写资料assignment英文原版】Python作业之Frequent Itemset Mining Using MapReduce
本人代写采集规则,发布模块,定制各种软件,擅长破解各种防采集; 源码为VS2008编写,因本人能力限制,不排除程序存在BUG,源代码仅供参考。 程序无须设置参数,点击“开始采集”即可,下面是本程序使用到的技术: ...
注:里面附带备注,相对而言通俗易懂,唯一不足之处在于没有将数据存放在txt文档,大致功能已经实现,以供参考。 题目要求:建立餐饮菜品评价管理系统,实现用户对餐厅的菜品进行评价,要求在结构体数组的基础上,...
2022年的年终工作总结代写.docx
大连代写项目融资商业计划书.docx
代写房屋租赁合同范本3篇.docx