-
运动目标检测[1-2]就是将视频序列中的背景和运动目标(又称为前景)分离,是智能视频分析中重要的基础性步骤。运动目标的准确检测对后续高层次的计算机视觉任务的完成有重要意义。近年来,广大学者围绕该课题展开了广泛的研究,提出了许多算法。但由于运动目标检测面临着光照变化、动态背景、相机的抖动以及算法的实时性等诸多挑战,它仍然是机器视觉领域的一个研究难点和热点。
背景建模[3]是实现运动目标检测的一类主要方法,它的思想是建立背景模型,然后判断待检测视频帧中的像素点是否符合背景模型,如不符合则属于前景运动目标。典型的方法[2]有单高斯模型、混合高斯模型、核密度估计模型、视觉背景提取、线性自回归模型以及基于像素的自适应分割等。这些方法以单一像素为处理单元,对背景模型的特点有较为严格的假设,使得这些算法在应用于实际场景时没有取得理想的效果。
根据视频序列背景的强相关性及前景运动目标的稀疏性这一特点,文献[4]将鲁棒主成分分析方法(robust principal component analysis, RPCA)应用到运动目标检测问题中,视频序列${\mathit{\boldsymbol{D}}}$被看成是由分别代表背景的低秩矩阵${\mathit{\boldsymbol{L}}}$和运动目标的稀疏矩阵${\mathit{\boldsymbol{S}}}$叠加而成。从而将运动目标检测转化为如下损失函数的优化问题[4]:
$$\begin{array}{*{20}{c}} {\mathop {\min }\limits_{{\mathit{\boldsymbol{L,S}}}} \operatorname{rank} ({\mathit{\boldsymbol{L}}}) + \lambda {{\left\| {\mathit{\boldsymbol{S}}} \right\|}_0}}&{{\rm{s}}{\rm{.t}}.}&{{\mathit{\boldsymbol{D}}} = {\mathit{\boldsymbol{L}}} + {\mathit{\boldsymbol{S}}}} \end{array}$$ (1) 式中,${\mathit{\boldsymbol{D}}} \in {\mathbb{R}^{m \times n}}$,$n$为视频帧数,其列向量由相应图像帧向量化得到;${\mathit{\boldsymbol{L}}}$为背景图像;${\mathit{\boldsymbol{S}}}$为前景运动目标。因式(1)中的秩函数和${l_0}$范数均为非线性非凸的,因此它的求解是一个NP-hard问题。
为了便于求解,可以将式(1)凸松弛为如下损失函数的优化问题[4]:
$$\begin{array}{*{20}{c}} {\mathop {\min }\limits_{{\mathit{\boldsymbol{L,S}}}} {{\left\| {\mathit{\boldsymbol{L}}} \right\|}_ * } + \lambda {{\left\| {\mathit{\boldsymbol{S}}} \right\|}_1}}&{{\rm{s}}{\rm{.t}}{\rm{.}}}&{{\mathit{\boldsymbol{D = L + S}}}} \end{array}$$ (2) 其中,${\left\| {\mathit{\boldsymbol{L}}} \right\|_ * } = \sum\nolimits_i {{\sigma _i}({\mathit{\boldsymbol{L}}})} $为核范数,${\sigma _i}({\mathit{\boldsymbol{L}}})$为矩阵${\mathit{\boldsymbol{L}}}$的第$i$个奇异值,用以近似矩阵的秩;${\left\| \cdot \right\|_1}$为${l_1}$范数
用以近似${l_0}$范数。因核范数和${l_1}$范数均为凸函数,所以式(2)可以用发展比较成熟的凸优化方法求解[5-6],代表性算法有加速近邻梯度算法、交错方向法等[7]。其中,基于对偶上升理论和增广拉格朗日乘子法所提出的非精确增广拉格朗日算法[8](inexact augmented lagrangian multipliers, IALM)以其高精度和较快的收敛速度,而被广泛应用于式(2)的求解。实际上IALM算法和文献[9]总结的交替方向乘子法(alternating direction method of multipliers, ADMM)具有近似的形式。
通常情况下,前景运动目标往往具有空间区域连续性,而${l_1}$范数项${\left\| {\mathit{\boldsymbol{S}}} \right\|_1}$将每个像素独立对待,没有利用前景目标的空间关系先验知识,会把一些零散的非目标大噪声误判为前景运动目标。基于此,文献[10]用结构稀疏范数代替${l_1}$范数,提出了低秩和结构稀疏分解方法(low rank and structured sparsity decomposition, LSD),取得了较好的效果。
在LSD方法及基于式(2)的核范数最小化方法[4] (nuclear norm minimization, NNM)中,均采用矩阵的核范数${\left\| {\mathit{\boldsymbol{L}}} \right\|_ * }$替代秩函数$\operatorname{rank} ({\mathit{\boldsymbol{L}}})$,期望通过最小化核范数达到秩最小化的目的。考虑到矩阵的秩为非零奇异值的个数,而其核范数为非零奇异值的和。秩最小化要求尽量减少矩阵非零奇异值的个数,因此核范数的最小化并不总是能够达到秩最小化的目的。
另一方面,核范数最小化通常采用软阈值方法压缩奇异值来实现。根据奇异值的物理意义,大奇异值包含图像边缘、纹理等的主要信息。如果数值大的奇异值被以较小幅度压缩,则可保证背景图像的质量。但是在核范数项$\sum\nolimits_i {{\sigma _i}({\mathit{\boldsymbol{L}}})} $中所有奇异值的权值均为1,大奇异值会被以同样的幅度压缩,这样势必降低分解得到的背景图像质量。
基于此,本文提出一种新的损失函数,并用ADMM/IALM方法对其进行优化。在新的损失函数中,用加权核范数取代核范数,对大奇异值赋以小的权值,小奇异值赋以大的权值。这样可以更好地近似秩函数,而且在最小化加权核范数时,大奇异值得以较小的幅度被压缩。同时,用结构稀疏范数替代${l_1}$范数作为前景目标的稀疏约束,充分利用了前景目标的区域连续性先验知识。
-
问题(2)及LSD方法均可采用ADMM/IALM框架进行优化,最终通过交替阈值迭代的过程得到背景图像和前景运动目标。
下面以问题(2)的求解过程为例介绍ADMM/IALM方法。
问题(2)的增广拉格朗日乘子式为:
$$\begin{gathered} \mathit{\Gamma }({\mathit{\boldsymbol{L,S}}},{\mathit{\boldsymbol{Y}}};\mu ) = {\left\| {\mathit{\boldsymbol{L}}} \right\|_ * } + \lambda {\left\| {\mathit{\boldsymbol{S}}} \right\|_1} + \langle {\mathit{\boldsymbol{Y}}},{\mathit{\boldsymbol{D}}} - {\mathit{\boldsymbol{L}}} - {\mathit{\boldsymbol{S}}}\rangle + \\ \mu /2\left\| {{\mathit{\boldsymbol{D}}} - {\mathit{\boldsymbol{L}}} - {\mathit{\boldsymbol{S}}}} \right\|_F^2 \\ \end{gathered} $$ (3) 式中,${\mathit{\boldsymbol{Y}}}$为拉格朗日乘子矩阵,又称为对偶变量;$\mu > 0$表示惩罚因子。运用循环最小化方法优化式(3),得到如下3个迭代算式:
$$\left\{ \begin{array}{l} {{\mathit{\boldsymbol{L}}}_{k + 1}} = \arg {\min _{\mathit{\boldsymbol{L}}}}\mathit{\Gamma }({\mathit{\boldsymbol{L}}},{{\mathit{\boldsymbol{S}}}_k},{{\mathit{\boldsymbol{Y}}}_k};\mu ) = \\ \arg {\min _{\mathit{\boldsymbol{L}}}}2/\mu {\left\| {\mathit{\boldsymbol{L}}} \right\|_*} + \left\| {({\mathit{\boldsymbol{D}}} - {{\mathit{\boldsymbol{S}}}_k} + {{\mathit{\boldsymbol{Y}}}_k}/\mu ) - {\mathit{\boldsymbol{L}}}} \right\|_F^2\\ {{\mathit{\boldsymbol{S}}}_{k + 1}} = \arg {\min _{\mathit{\boldsymbol{S}}}}\mathit{\Gamma }({{\mathit{\boldsymbol{L}}}_{k + 1}},{\mathit{\boldsymbol{S}}},{{\mathit{\boldsymbol{Y}}}_k};\mu ) = \\ {\mathit{\Omega }_{\lambda /\mu }}({\mathit{\boldsymbol{D}}} - {{\mathit{\boldsymbol{L}}}_{k + 1}} + {{\mathit{\boldsymbol{Y}}}_k}/\mu ){{\mathit{\boldsymbol{Y}}}_{k + 1}} = {{\mathit{\boldsymbol{Y}}}_k} + \mu ({\mathit{\boldsymbol{D}}} - {{\mathit{\boldsymbol{L}}}_{k + 1}} - {{\mathit{\boldsymbol{S}}}_{k + 1}}) \end{array} \right.$$ (4) 式中,${\mathit{\Omega }_\tau }(x)$的定义为[11]:
$${\mathit{\Omega }_\tau }(x) = \operatorname{sgn} (x)\max (|x| - \tau ,0)$$ 在第一个迭代式中记${{\mathit{\boldsymbol{G}}}^{\mathit{\boldsymbol{L}}}} = {\mathit{\boldsymbol{D}}} - {{\mathit{\boldsymbol{S}}}_k} + {{{{\mathit{\boldsymbol{Y}}}_k}} / \mu }$,其奇异值分解为${{\mathit{\boldsymbol{G}}}^{\mathit{\boldsymbol{L}}}} = {\mathit{\boldsymbol{U\mathit{\Sigma }}}}{{\mathit{\boldsymbol{V}}}^{\rm{{\rm T}}}}$,则${{\mathit{\boldsymbol{L}}}_{k + 1}}$可由奇异值收缩算子法得到其闭式解[11]:
$${{\mathit{\boldsymbol{L}}}_{k + 1}} = {\mathit{\boldsymbol{U}}}{\mathit{\Omega }_{{1 / \mu }}}({\mathit{\boldsymbol{\mathit{\Sigma }}}}){{\mathit{\boldsymbol{V}}}^{\rm{{\rm T}}}}$$ (5) 式中,${\mathit{\Omega }_{{1 / \mu }}}({\mathit{\boldsymbol{\mathit{\Sigma }}}})$为奇异值收缩算子,它是一个对角矩阵,其对角元素定义如下:
$$\begin{gathered} {[{\mathit{\Omega }_{{1 / \mu }}}({\mathit{\boldsymbol{\mathit{\Sigma }}}})]_{ii}} = {\mathit{\Omega }_{1/\mu }}({{\mathit{\boldsymbol{\mathit{\Sigma }}}}_{ii}}) = \max ({{\mathit{\boldsymbol{\mathit{\Sigma }}}}_{ii}} - 1/\mu ,0) = \\ \max \{ {\sigma _i}({{\mathit{\boldsymbol{G}}}^{\mathit{\boldsymbol{L}}}}) - 1/\mu ,0\} \\ \end{gathered} $$ (6) 由上式可以看到,奇异值收缩算子的作用是将矩阵${{\mathit{\boldsymbol{G}}}^{\mathit{\boldsymbol{L}}}}$的所有奇异值向零的方向压缩,把小于等于$1/\mu $的奇异值压缩为0,从而实现核范数${\left\| {\mathit{\boldsymbol{L}}} \right\|_ * }$的最小化,以期得到低秩矩阵${\mathit{\boldsymbol{L}}}$。
-
在损失函数式(2)中,采用${l_1}$范数项${\left\| {\mathit{\boldsymbol{S}}} \right\|_1}$作为稀疏约束项以求解前景运动目标。${l_1}$范数将各个像素独立处理,而前景运动目标通常具有空间连续性特征,结构稀疏范数可以充分利用这一先验信息。
图 1说明了结构稀疏范数的思想。假设图 1a和图 1b是优化过程中一帧图像前景运动目标的两种可能选择,图中白色点代表前景运动目标像素(数值代表像素值),黑色点代表背景像素(像素值为0)。如果采用核范数衡量图 1a和图 1b的稀疏性,会得出相同的结果。但是,根据前景运动目标的空间区域连续性这一先验知识,显然图 1a更可能是前景目标图像。
考虑设计一个$3 \times 3$的方形窗口,然后逐行逐列滑动窗口,相邻两个窗口位置有6个像素重合。图 1c和1d是两种情况下部分窗口的位置示意图。计算每个窗口位置的${l_\infty }$范数,然后把所有窗口位置的${l_\infty }$范数相加作为稀疏性的度量。显然,采用这种方法图 1a的稀疏度(值为420)明显小于图 1b(值为680),所以根据运动目标矩阵稀疏度最小的要求,在优化过程中图 1a会被认为是前景目标。
下面给出结构稀疏范数的定义。观测视频序列构成矩阵${\mathit{\boldsymbol{D}}} \in {\mathbb{R}^{m \times n}}$,其中$n$为视频帧数,每帧图像的行、列数分别为$a$、$b$,${\mathit{\boldsymbol{D}}}$的第$j$列由第$j$帧图像向量化而得到,即$a \times b = m$。待求的前景运动目标帧序列构成的矩阵为${\mathit{\boldsymbol{S}}} \in {\mathbb{R}^{m \times n}}$,其第$j$列${s^j} \in {\mathbb{R}^m}$由第$j$帧的前景运动目标图像${{\mathit{\boldsymbol{F}}}_j} \in {\mathbb{R}^{a \times b}}$向量化得到,${s^j}$所包含像素序号构成的集合记为$\mathit{\Theta } = \{ 1,2, \cdots ,m\} $。设计一个$c \times c$的窗口,逐行逐列滑过一帧前景运动目标矩阵${{\mathit{\boldsymbol{F}}}_j}$,窗口的一个位置所覆盖的像素记为$s_g^j$,其中$g$是所覆盖像素的序号所构成的集合,它是集合$\mathit{\Theta }$一个子集,不同位置的窗口所对应的$g$构成一个集合记为$G$。则结构稀疏范数的定义为[12]:
$$\mathit{\Upsilon }({\mathit{\boldsymbol{S}}}) = \sum\limits_{j = 1}^n {\sum\limits_{g \in G} {{{\left\| {s_g^j} \right\|}_\infty }} } $$ (7) -
在损失函数式(2)中,采用核范数${\left\| {\mathit{\boldsymbol{L}}} \right\|_ * }$作为矩阵${\mathit{\boldsymbol{L}}}$的低秩性约束。通过奇异值收缩算子法式(5)和式(6)计算每一步的${{\mathit{\boldsymbol{L}}}_{k + 1}}$。在这种方法中,所有奇异值的权值均为1,导致压缩阈值恒定。从而奇异值收缩算子将矩阵${{\mathit{\boldsymbol{G}}}^{\mathit{\boldsymbol{L}}}}$的所有奇异值施以同样大小的压缩。这样能够把小于等于$1/\mu $的奇异值压缩为0,从而减少了非零奇异值的数量。而对于值大于$1/\mu $的奇异值的压缩虽然使得核范数${\left\| {\mathit{\boldsymbol{L}}} \right\|_ * }$减小了,但并没有减少非零奇异值的个数,因此也就无助于矩阵${\mathit{\boldsymbol{L}}}$秩的最小化,反而会降低低秩矩阵所表示的背景图像的质量,因为数值大的奇异值代表着图像的主要成分[12]。
基于此,提出采用加权核范数[12-13]${\left\| {\mathit{\boldsymbol{L}}} \right\|_{{\mathit{\boldsymbol{w}}}, * }}$替代$\operatorname{rank} ({\mathit{\boldsymbol{L}}})$,其定义如下:
$$\begin{array}{*{20}{c}} {{{\left\| {\mathit{\boldsymbol{L}}} \right\|}_{{\mathit{\boldsymbol{w}}}, * }} = \sum\nolimits_i {{w_i}{\sigma _i}({\mathit{\boldsymbol{L}}})} } \\ {0 \leqslant {w_1} \leqslant {w_2} \cdots ,{\rm{ }}{\sigma _1}({\mathit{\boldsymbol{L}}}) \geqslant {\sigma _2}({\mathit{\boldsymbol{L}}}) \cdots \geqslant 0} \end{array}$$ (8) 即给各个奇异值赋予不同的权值,权值和对应奇异值的大小呈单调递减关系。数值大的奇异值给予较小的权值,这样在最小化加权核范数时,大奇异值被压缩得小一些。
因此,新的损失函数为:
$$\begin{array}{*{20}{c}} {\mathop {\min }\limits_{{\mathit{\boldsymbol{L,S}}}} {{\left\| {\mathit{\boldsymbol{L}}} \right\|}_{{\mathit{\boldsymbol{w}}}, * }} + \lambda \mathit{\Upsilon }({\mathit{\boldsymbol{S}}})}&{\begin{array}{*{20}{c}} {{\rm{s}}{\rm{.t}}{\rm{.}}}&{{\mathit{\boldsymbol{D}}} = {\mathit{\boldsymbol{L}}} + {\mathit{\boldsymbol{S}}}} \end{array}} \end{array}$$ (9) 上式采用了结构稀疏范数$\mathit{\Upsilon }({\mathit{\boldsymbol{S}}})$代替${l_1}$范数项${\left\| {\mathit{\boldsymbol{S}}} \right\|_1}$作为前景运动目标的稀疏约束项。
-
损失函数(9)的增广拉格朗日乘子式为:
$$ \begin{gathered} \mathit{\Gamma }({\mathit{\boldsymbol{L,S}}},{\mathit{\boldsymbol{Y}}};\mu ) = \\ {\left\| {\mathit{\boldsymbol{L}}} \right\|_{{\mathit{\boldsymbol{w}}}, * }} + \lambda \mathit{\Upsilon }({\mathit{\boldsymbol{S}}}) + \langle {\mathit{\boldsymbol{Y}}},{\mathit{\boldsymbol{D}}} - {\mathit{\boldsymbol{L}}} - {\mathit{\boldsymbol{S}}}\rangle + \mu /2\left\| {{\mathit{\boldsymbol{D}}} - {\mathit{\boldsymbol{L}}} - {\mathit{\boldsymbol{S}}}} \right\|_F^2 \\ \end{gathered} $$ (10) 运用循环最小化方法优化式(10), 得到如下3个迭代算式:
$$\left\{ \begin{array}{l} {{\mathit{\boldsymbol{L}}}_{k + 1}} = \arg {\min _{\mathit{\boldsymbol{L}}}}\mathit{\Gamma } ({\mathit{\boldsymbol{L}}},{{\mathit{\boldsymbol{S}}}_k},{{\mathit{\boldsymbol{Y}}}_k};\mu ,{\mathit{\boldsymbol{w}}}) = \\ \arg {\min _{\mathit{\boldsymbol{L}}}}2/\mu {\left\| {\mathit{\boldsymbol{L}}} \right\|_{{\mathit{\boldsymbol{w}}},*}} + \left\| {{{\mathit{\boldsymbol{G}}}^{\mathit{\boldsymbol{L}}}} - {\mathit{\boldsymbol{L}}}} \right\|_F^2\\ {{\mathit{\boldsymbol{S}}}_{k + 1}} = \arg {\min _{\mathit{\boldsymbol{S}}}}\mathit{\Gamma } ({{\mathit{\boldsymbol{L}}}_{k + 1}},{\mathit{\boldsymbol{S}}},{{\mathit{\boldsymbol{Y}}}_k};\mu ,{\mathit{\boldsymbol{w}}}) = \\ \arg {\min _{\mathit{\boldsymbol{S}}}}\lambda \mathit{\Upsilon }({\mathit{\boldsymbol{S}}}) + \mu /2\left\| {({\mathit{\boldsymbol{D}}} - {{\mathit{\boldsymbol{L}}}_{k + 1}} + {{\mathit{\boldsymbol{Y}}}_k}/\mu ) - {\mathit{\boldsymbol{S}}}} \right\|_F^2\\ {{\mathit{\boldsymbol{Y}}}_{k + 1}} = {{\mathit{\boldsymbol{Y}}}_k} + \mu ({\mathit{\boldsymbol{D}}} - {{\mathit{\boldsymbol{L}}}_{k + 1}} - {{\mathit{\boldsymbol{S}}}_{k + 1}}) \end{array} \right.$$ (11) 当$0 \leqslant {w_1} \leqslant {w_2} \cdots $时,式(11)中第一个算式的闭式解为[11]:
$${{\mathit{\boldsymbol{L}}}_{k + 1}} = {\mathit{\boldsymbol{U}}}{\mathit{\Omega }_{{{\mathit{\boldsymbol{w}}} / \mu }}}({\mathit{\boldsymbol{\mathit{\Sigma }}}}){{\mathit{\boldsymbol{V}}}^{\rm{{\rm T}}}}$$ (12) 式中,${\mathit{\boldsymbol{\mathit{\Sigma }}}}$、${\mathit{\boldsymbol{U}}}$、${\mathit{\boldsymbol{V}}}$由${{\mathit{\boldsymbol{G}}}^{\mathit{\boldsymbol{L}}}}$的奇异值分解${{\mathit{\boldsymbol{G}}}^{\mathit{\boldsymbol{L}}}} = {\mathit{\boldsymbol{U\mathit{\Sigma }}}}{{\mathit{\boldsymbol{V}}}^{\rm{{\rm T}}}}$得到(${{\mathit{\boldsymbol{G}}}^{\mathit{\boldsymbol{L}}}}$的奇异值${\sigma _i}({{\mathit{\boldsymbol{G}}}^{\mathit{\boldsymbol{L}}}})$在${\mathit{\boldsymbol{\mathit{\Sigma }}}}$的对角线上按从大到小的顺序排列)。奇异值收缩算子${\mathit{\Omega }_{{{\mathit{\boldsymbol{w}}} / \mu }}}({\mathit{\boldsymbol{\mathit{\Sigma }}}})$是一个对角矩阵,其对角元素为[13]:
$$\begin{gathered} {[{\mathit{\Omega }_{{{\mathit{\boldsymbol{w}}} / \mu }}}({\mathit{\boldsymbol{\mathit{\Sigma }}}})]_{ii}} = \max ({{\mathit{\boldsymbol{\mathit{\Sigma }}}}_{ii}} - {w_i}/\mu ,0) = \\ \max \{ {\sigma _i}({{\mathit{\boldsymbol{G}}}^{\mathit{\boldsymbol{L}}}}) - {w_i}/\mu ,0\} \\ \end{gathered} $$ (13) 在损失函数中引入加权核范数后,可通过奇异值收缩算子式(12)、式(13)迭代求解背景图像矩阵${\mathit{\boldsymbol{L}}}$。由式(13)可知,奇异值${\sigma _i}({{\mathit{\boldsymbol{G}}}^{\mathit{\boldsymbol{L}}}})$的压缩阈值${w_i}/\mu $与权值${w_i}$有关,而由式(8)可知,${w_i}$和${\sigma _i}({{\mathit{\boldsymbol{G}}}^{\mathit{\boldsymbol{L}}}})$呈单调递减关系。因此,压缩阈值${w_i}/\mu $不再是固定不变的,而是与对应奇异值${\sigma _i}({{\mathit{\boldsymbol{G}}}^{\mathit{\boldsymbol{L}}}})$的大小呈单调递减的关系。小奇异值得到较大幅度的压缩,从而有更多的奇异值被压缩为零,更好地实现了矩阵${\mathit{\boldsymbol{L}}}$秩的最小化。而大奇异值得到较小的压缩,背景图像的质量可以得到有效的保证,从而得到更好的背景和前景的分离效果。
式(11)中${{\mathit{\boldsymbol{S}}}_{k + 1}}$的迭代式可用近邻算子法将其转换为一个二次最小代价流问题求解[14]。
-
受文献[15]在稀疏编码中采用的自适应调整权值策略的启发,采用如下方法自适应调整权值:
$$w_i^{k + 1} = \frac{C}{{{\sigma _i}({{\mathit{\boldsymbol{L}}}_k}) + \varepsilon }}$$ (14) 式中,$\varepsilon $取趋近于0的常数以避免除数为0;$C$为一个常数,可根据不同应用场合进行调整。
-
通过实验比较如表 1所示4种RPCA算法在真实场景数据集上的性能。其中WNNM算法主要是为了与NNM算法进行对比以验证使用加权核范数作为背景图像低秩约束的性能。
表 1 参与对比的4种算法
算法名称 背景的低秩约束 前景的稀疏约束 NNM 核范数 ${l_1}$范数 WNNM 加权核范数 ${l_1}$范数 LSD 核范数 结构稀疏范数 Proposed method 加权核范数 结构稀疏范数 测试数据集选择在运动目标检测和背景去除领域广泛采用的CDNET2014视频库[16]。该数据集包括基本场景、相机抖动、坏天气等不同情况下的11个视频系列。每个系列又包括4~6个不同场景的视频序列。为了便于对算法性能进行评估,数据集还提供了每个视频帧的分割前景(ground truth)。本文选择了Highway、Office、Pedestrian、PETS2006、Overpass及Canoe6个场景进行算法的对比分析,各个场景的特点如表 2所示。
表 2 进行对比的6种场景数据集
数据集 分辨率 场景特点 图 2中图像的帧序号 Highway 320*240 室外,动态背景 567 Office 360*240 室内,人工照明 656 Pedestrian 360*240 室外,有阴影 366 PETS2006 720*576 室内,光照变化 350 Overpass 320*240 室外,波光树叶抖动 2456 Canoe 320*240 室外,大范围波光 966 实验所用计算机为台式机,CPU为Intel系列I5-6500,主频3.2 GHz,内存8 GB,仿真所用软件为Matlab R2016b。
-
如果把前景运动目标检测看作是前景和背景像素的分类问题,则前景像素点可视为正样本(positive),背景像素点为负样本(negative)。从而可以采用由前景目标分类的准确率(precision)和召回率(recall)组合得到的综合性能指标(F1)来定量衡量算法的性能。定义如下:
$$\begin{array}{l} {\rm{Precision}} = \frac{{{\rm{TP}}}}{{{\rm{TP}} + {\rm{FP}}}},{\rm{Recall}} = \frac{{{\rm{TP}}}}{{{\rm{TP}} + {\rm{FN}}}},\\ {\rm{F}}1 = \frac{{2 \times {\rm{Precision}} \times {\rm{Recall}}}}{{{\rm{Precision}} + {\rm{Recall}}}} \end{array}$$ 式中,TP(true positive)为正确检测为前景像素点的个数;FN(false negative)表示错误检测为背景点的像素数目;FP(false positive)表示错误检测为前景点的像素数目。
-
实验中4种不同的算法迭代终止条件统一设定为${{\left\| {{\mathit{\boldsymbol{D}}} - {{\mathit{\boldsymbol{L}}}_{k + 1}} - {{\mathit{\boldsymbol{S}}}_{k + 1}}} \right\|_F^2} / {\left\| {\mathit{\boldsymbol{D}}} \right\|_F^2}} \leqslant {10^{ - 7}}$。本文算法的参数$\lambda = \frac{1}{{\sqrt m }}$,$C = \sqrt {2\max ({m^{0.6}},{n^{0.6}})} $,结构稀疏范数中滑动窗口的大小选定为$3 \times 3$。为了加快算法的收敛速度,借鉴文献[17]的作法,在迭代式(4)、式(11)时,采用动态的惩罚因子。随着迭代步数$k$的增加逐步更新${\mu _k}$,同时限制其上界(防止${\mu _k}$太大,导致算法收敛不到最优解),更新规则为[17]:
$${\mu _k} = \min (1.05{\mu _{k - 1}},{10^7}{\mu _0})$$ (15) 初值${\mu _0} = {{12.5} / {{\sigma _1}({\mathit{\boldsymbol{D}}})}}$。其中,${\sigma _1}({\mathit{\boldsymbol{D}}})$为矩阵${\mathit{\boldsymbol{D}}}$的最大奇异值。
图 2给出了在6种场景下各算法得到的某一帧运动前景识别的效果,对应的帧序号如表 2第4列所示。图 2中的第一行Office是一个室内复杂背景下的运动场景,从图中可以看出NNM和WNNM算法所识别出的前景目标腿部缺失,躯干部存在空洞。本文算法和LSD较好地识别出运动人像,且轮廓均较清晰,但是LSD算法识别出的运动前景在人的背部存在较多的FP点。图中的第二行的Highway场景是一个室外动态背景(树叶有抖动)的运动场景,从图中可以看出本文算法较其他算法识别出的前后车轮廓更分明,而且FP点较其他算法更少。第三行的Pedestrian是一个室外运动物体有阴影的场景,从图中可以看出4种算法均能较完整地识别出运动人物的轮廓,因为阴影会随着人的走动而移动,所以阴影也都被识别为运动前景。PETS2006是一个背景光线对比强烈的室内场景,4种算法均能识别出运动前景,但是除本文算法外,其他3种算法均存在不同程度的腿部空洞。Overpass是一个存在两种动态背景(湖面和树叶)的复杂场景,从图中可以看出,WNNM、NNM和LSD存在较严重的背部空洞,而只有本文算法分离出了较为清晰的前景目标。Canoe是一个动态背景下多运动目标的场景,前3种算法分离出的前景目标船体部分存在较多空洞,而本文算法前景轮廓清晰。另外这几种算法分离出的结果,湖面均存在较多的FP点。
表 3列出了4种算法在6种场景下分离效果F1参数的定量比较。从表中可以看出WNNM算法的性能优于NNM,究其原因在于WNNM采用加权核范数作为低秩项的近似,相较于NNM使用的核范数,能够更好地体现运动前景连续帧图像间背景的强相关性。而LSD算法的性能亦优于NNM,这是因为LSD充分利用了前景运动目标普遍所具备的区域连续性先验知识,用结构稀疏范数代替NNM中所采用的${l_1}$范数作为稀疏项,避免了一些零散的稀疏大噪声被误判为前景目标。而本文算法结合了WNNM和LSD算法的优势,实验结果也表明本文算法的性能优于另外3种算法。
表 3 4种算法在6种场景下的F1指标对比
A New Method for Detecting Moving Objects in Video
-
摘要: 现有的用于视频运动目标检测的鲁棒主成分分析方法通常将背景矩阵的秩函数松弛为核范数,导致求解低秩矩阵的奇异值收缩算子法的阈值恒定,从而背景恢复精度不高。为此提出由加权核范数和结构稀疏范数组成的新的损失函数并用交替方向乘子法进行优化。采用加权核范数作为矩阵的低秩约束,使得压缩阈值与相应奇异值的大小呈单调递减关系,从而大奇异值得以较小幅度压缩。使用结构稀疏范数作为前景稀疏约束,有效利用了前景运动目标的空间区域连续性的先验知识。实验结果表明,该方法在动态背景、阴影等复杂场景下均能取得较其他鲁棒主成分分析方法更好的效果。Abstract: In the method of robust principal component analysis to detection of moving objects, rank function of background matrix is often substituted by the nuclear norm. As a result, the threshold of shrinkage operator of singular values to seek low rank matrix is invariant and the precision of background recovery is relatively low. A new loss function composed of weighted nuclear norm and structured sparsity norm is proposed and optimized by alternating direction multiplier method. In the function, the weighted nuclear norm is adopted as a low rank constraint. It causes that the shrinkage threshold is monotonically decreasing with the corresponding singular value and thus these larger ones are shrunk in a small margin. The structured sparsity norm is used as a sparsity constraint of foreground matrix and it effectively utilizes prior knowledge of the regional continuity of foreground moving objects. The experimental results show that the proposed method can obtain better performances than other robust principal component analysis methods in dynamic background, shadow and other complex scenes.
-
表 1 参与对比的4种算法
算法名称 背景的低秩约束 前景的稀疏约束 NNM 核范数 ${l_1}$范数 WNNM 加权核范数 ${l_1}$范数 LSD 核范数 结构稀疏范数 Proposed method 加权核范数 结构稀疏范数 表 2 进行对比的6种场景数据集
数据集 分辨率 场景特点 图 2中图像的帧序号 Highway 320*240 室外,动态背景 567 Office 360*240 室内,人工照明 656 Pedestrian 360*240 室外,有阴影 366 PETS2006 720*576 室内,光照变化 350 Overpass 320*240 室外,波光树叶抖动 2456 Canoe 320*240 室外,大范围波光 966 表 3 4种算法在6种场景下的F1指标对比
-
[1] BOUWMANS T, ZAHZAH E H. Robust PCA via principal component pursuit:a review for a comparative evaluation in video surveillance[J]. Computer Vision and Image Understanding, 2014, 122:22-34. doi: 10.1016/j.cviu.2013.11.009 [2] SOBRAL A, VACAVANT A. A comprehensive review of background subtraction algorithms evaluated with synthetic and real videos[J]. Computer Vision and Image Understanding, 2014, 122:4-21. doi: 10.1016/j.cviu.2013.12.005 [3] HOFMANN M, TIEFENBACHER P, RIGOLL G. Background segmentation with feedback: the pixel-based adaptive segmenter[C]//Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops. Providence, RI: IEEE, 2012: 38-43. [4] CANDÈS E J, LI X D, MA Y, et al. Robust principal component analysis?[J]. Journal of the ACM, 2011, 58(3):11. http://d.old.wanfangdata.com.cn/Periodical/cjce200405015 [5] PENG X, LU C, ZHANG Y, et al. Connections between nuclear-norm and frobenius-norm-based representations[J]. IEEE Transactions on Neural Networks & Learning Systems, 2015(99):1-7. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=Arxiv000001418760 [6] PENG X, LU J, ZHANG Y, et al. Automatic subspace learning via principal coefficients embedding[J]. IEEE Transactions on Cybernetics, 2017(99):1-14. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=Arxiv000001319691 [7] LIN Z C, GANESH A, WRIGHT J, et al. Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix[R]. Urbana-Champaign, Illinois, America: University of Illinois at Urbana-Champaign(UIUC), UIUC Technical Report, 2009. [8] LIN Z C, CHEN M M, MA Y. The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matritrices[R]. Urbana-Champaign, Illinois, America: University of Illinois at Urbana-Champaign(UIUC), UIUC Technical Report, 2010. [9] BOYD S, PARIKH N, CHU E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends in Machine Learning, 2011, 3(1):1-122. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=3e990a176868f2d25550830e52a96572 [10] LIU X, ZHAO G, YAO J, et al. Background subtraction based on low-rank and structured sparse decomposition[J]. IEEE Transactions on Image Processing, 2015, 24(8):2502-2514. doi: 10.1109/TIP.2015.2419084 [11] CAI J F, CANDÈS E J, SHEN Z. A singular value thresholding algorithm for matrix completion[J]. SIAM Journal on Optimization, 2010, 20(4):1956-1982. doi: 10.1137/080738970 [12] LU C, TANG J, YAN S, et al. Nonconvex nonsmooth low rank minimization via iteratively reweighted nuclear norm[J]. IEEE Transactions on Image Processing, 2016, 25(2):829-839. doi: 10.1109/TIP.2015.2511584 [13] CHEN K, DONG H, CHAN K S. Reduced rank regression via adaptive nuclear norm penalization[J]. Biometrika, 2013, 100(4):901-920. doi: 10.1093/biomet/ast036 [14] MAIRAL J, JENATTON R, BACH F R, et al. Network flow algorithms for structured sparsity[C]//24th Annual Conference on Neural Information Processing Systems 2010. Vancouver, BC, Canada: Curran Associates Inc, 2010: 1558-1566. [15] CANDES E J, WAKIN M B, BOYD S P. Enhancing sparsity by reweighted l1 minimization[J]. Journal of Fourier Analysis and Applications, 2008, 14(5):877-905. http://d.old.wanfangdata.com.cn/OAPaper/oai_arXiv.org_0711.1612 [16] WANG Y, JODOIN P M, PORIKLI F, et al. CDnet 2014: an expanded change detection benchmark dataset[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops.[S.l.]: IEEE, 2014: 387-394. [17] LIU R, LIN Z, SU Z. Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning[C]//5th Asian Conference on Machine Learning. Canberra, Australia: Microtome Publishing, 2013: 116-132.