![点击分享此内容可以赚币 分享](/master/images/share_but.png)
基于监控视频背景建模的一类非凸矩阵优化算法研究.pdf
《基于监控视频背景建模的一类非凸矩阵优化算法研究.pdf》由会员分享,可在线阅读,更多相关《基于监控视频背景建模的一类非凸矩阵优化算法研究.pdf(14页珍藏版)》请在咨信网上搜索。
1、Operations Research and Fuzziology 运筹与模糊学运筹与模糊学,2023,13(4),2817-2830 Published Online August 2023 in Hans.https:/www.hanspub.org/journal/orf https:/doi.org/10.12677/orf.2023.134282 文章引用文章引用:贾凯贤,陈小英,孟书羽,程越,张弦,彭定涛.基于监控视频背景建模的一类非凸矩阵优化算法研究J.运筹与模糊学,2023,13(4):2817-2830.DOI:10.12677/orf.2023.134282 基于监控视频
2、背景建模的一类非凸矩阵优化基于监控视频背景建模的一类非凸矩阵优化 算法研究算法研究 贾凯贤贾凯贤,陈小英,孟书羽,程陈小英,孟书羽,程 越,张越,张 弦,彭定涛弦,彭定涛*贵州大学数学与统计学院,贵州 贵阳 收稿日期:2023年5月22日;录用日期:2023年7月29日;发布日期:2023年8月3日 摘摘 要要 为了实现稳健的低秩为了实现稳健的低秩稀疏矩阵分解,本文考虑非凸非光滑优化模型,其中矩阵的秩函数采用奇异值的稀疏矩阵分解,本文考虑非凸非光滑优化模型,其中矩阵的秩函数采用奇异值的Capped-l1松弛,矩阵的松弛,矩阵的l0范数采用矩阵的范数采用矩阵的l1范数松弛。首先,给出了适用于矩阵
3、问题的范数松弛。首先,给出了适用于矩阵问题的Capped-l1阈值算阈值算子。其次,提出了交替方向乘子法求解我们的非凸非光滑矩阵优化模型,并分析了算法的收敛性。最后,子。其次,提出了交替方向乘子法求解我们的非凸非光滑矩阵优化模型,并分析了算法的收敛性。最后,通过大量数值实验表明:在有噪声和无噪声的情况下,所提出的算法都能有效、稳健地分解出低秩通过大量数值实验表明:在有噪声和无噪声的情况下,所提出的算法都能有效、稳健地分解出低秩稀稀疏矩阵。并将提出的算法应用于监控视频的前景和背景分离问题,发现所提出的算法对于该问题有良好疏矩阵。并将提出的算法应用于监控视频的前景和背景分离问题,发现所提出的算法对
4、于该问题有良好的性能,这说明该算法能够解决相关实际问题。的性能,这说明该算法能够解决相关实际问题。关键词关键词 稀疏稀疏低低秩秩矩阵矩阵分解,分解,Capped-l1正则,交替方向乘子法,正则,交替方向乘子法,前景和前景和背景分离背景分离 Research on a Class of Nonconvex Matrix Optimization Algorithm Based on Surveillance Video Background Modeling Kaixian Jia,Xiaoying Chen,Shuyu Meng,Yue Cheng,Xian Zhang,Dingtao Pen
5、g*School of Mathematics and Statistics,Guizhou University,Guiyang Guizhou Received:May 22nd,2023;accepted:Jul.29th,2023;published:Aug.3rd,2023 Abstract In order to achieve robust low-rank sparse matrix decomposition,this paper considers a noncon-vex and nonsmooth optimization model,in which the rank
6、ing function of the matrix is relaxed by *通讯作者。贾凯贤 等 DOI:10.12677/orf.2023.134282 2818 运筹与模糊学 Capped-l1 regularization of the singular values,and l0 norm of the matrix is relaxed with the l1 norm of the matrix.First,we provide the closed-form thresholding operator for the matrix-Capped-l1 function.S
7、econdly,the alternating direction method of multipliers is proposed to solve our nonconvex and nonsmooth optimization model,and the convergence analysis is provided.Fi-nally,a large number of numerical experiments show that the proposed algorithm can effectively and robustly decompose the low-rank a
8、nd sparse matrices in the case of noise and noise.The proposed algorithm is applied to the background separation problem of surveillance video,and it is indicated that the proposed algorithm has good performance for this problem,which shows that the algorithm can solve the relevant practical problem
9、s.Keywords Sparse and Low-Rank Matrices Decomposition,Capped-l1 Regularization,Alternating Direction Method of Multipliers,Foreground and Background Separation Copyright 2023 by author(s)and Hans Publishers Inc.This work is licensed under the Creative Commons Attribution International License(CC BY
10、4.0).http:/creativecommons.org/licenses/by/4.0/1.引言引言 在大数据时代,随着计算机和信息技术的普及与应用,各种各样的数据信息呈爆炸性增长,时刻都会产生大量的、多样化的、结构复杂的、冗余的、高维的海量数据。研究表明无法通过常规手段直接处理使用这类信息,那么如何从这些高维且冗余的数据中提取有价值的信息便成为大数据科学问题的关键课题之一。大量已有的研究工作表明稀疏性则是研究这一课题的重要手段。在不同实际应用领域中出现的复杂系统和复杂模型的矩阵,其通常可以具有由低秩分量和稀疏分量组成的特征,而这种复杂系统的可分性为理解复杂系统的行为和性质提供了可能。实
11、现这种矩阵表示的可分性可以描述为如下的矩阵低秩稀疏分解(Low Rank and Sparse Decomposition,LRSD)1 2 3:(),R0in,.m.m nL Srank LstDLSS+=+?,(1)其中参数 0,rank()是矩阵的秩函数,0l是矩阵的 l0范数,表示矩阵中所有元素的非零个数和,其本质上是为了寻找数据最具价值的低维结构及最佳投影,通过去除数据中的冗余信息,从而找到数据中有价值的信息。因为 LRSD 方法克服了主成分分析(Principal Component Analysis,PCA)4 5方法对非高斯样本或异常值的敏感性在实践中往往使其不够稳健的缺陷,因
12、此该方法又被称为稳定主成分分析法(Robust Prin-cipal Component Analysis,RPCA)。LRSD 问题的基本出发点在于很多的实际数据矩阵 D 往往是具有先验信息近似低秩特性和稀疏特性的。问题(1)中的参数 则用于平衡矩阵 L 的低秩程度和矩阵 S 的稀疏程度,和向量 l0极小化问题一样,问题(1)显然是一个 NP-hard 的问题,求解的复杂度极高,甚至在实际的应用中可能会出现难以求解的情况,不利于该模型在实际问题中的应用。为了高效求解 LRSD 问题,Cands 和 Li 6等提出在一定条件下,最小化 l1范数求得的解等价于最小化 l0范数求得的解,而秩函数则
13、可以通过核范数进行近似表达,该方法即是被称为著名的主成分追踪法(Principal Component Pursuit,PCP),它的思想是将 LRSD 的非凸问题进行凸松弛,转化为凸优化问题进行求解。Open AccessOpen Access贾凯贤 等 DOI:10.12677/orf.2023.134282 2819 运筹与模糊学 在求解模型(1)时,PCP 方法的出发点在于矩阵的秩等于非零奇异值的个数以及 l1范数是 l0范数的最紧凸松弛,进而将非凸问题(1)进行松弛得到如下最紧凸松弛问题进行求解:1,*,.min.m nL SlLLSstDS+=+?(2)其中*表示矩阵奇异值之和,称
14、为矩阵的核范数,1l表示矩阵所有元素绝对值之和。实际应用中该模型的平衡参数通常设置为1 max,m n,m 和 n 分别表示的是矩阵 D 的行数和列数。在求解模型(1)时,使用的 PCP 方法6会出现对低秩部分和稀疏部分刻画不准确的问题。因此,很多研究者一直在寻求秩函数和稀疏度函数的更加精确的表达方法。在许多经典的 LRSD 方法中主要是利用核范数对秩函数进行凸近似。虽然核范数已经在低秩矩阵的近似表达中被广泛使用,但是核范数表示的是非零奇异值的和,并不是秩函数的最佳刻画。为了解决该问题,文献7中提出了截断核范数(Truncated Nuclear Norm,TNN),实验结果表明该方法在一定程
15、度上能更准确地诱导低秩部分,后续中许多研究基于TNN 的方法被广泛应用到低秩稀疏分解中8 9 10。在求解优化问题(2)时,文献11基于目标函数的一阶信息提出了迭代阈值算法(Iterative Thresholding,IT),虽然算法的迭代方式简单也收敛,但其每次迭代都要进行一次奇异值分解且收敛速度很慢,也难以选取合适的步长,无法快速求解大型实际问题。此后,文献12提出了求解问题(2)的加速临近梯度算法(Accelerated Proximal Gradient,APG)和求解相应对偶问题的梯度上升算法,并通过实验说明这两种算法在处理 1000 1000 维的矩阵时相较于迭代阈值算法加速了
16、50 倍。进一步文献13提出了增广拉格朗日乘子法(Augmented Lagrange Multiplier,ALM),其中 ALM 算法相比 IT 算法和 APG 算法具有更快的计算速度且所需存储空间更小等优点,在显著提高计算精度的同时其计算速度快于 APG 算法。然而当目标函数含有两个及以上的变量时,由于 ALM 将乘子函数中的所有变量同时最小化,使该算法具有较高的计算复杂度,给求解带来了困难。因此,交替方向乘子法(Alternating Direction Method of Multipliers,ADMM)算法14 15 16应运而生,ADMM 算法采用分而治之的思想将不易求解的问题
17、转化为容易求解的子问题进行求解,使其同时兼具了乘子法和交替最小化算法的优点。此外,该算法的复杂度较低,有利于求解,并且该算法具有更高的计算速度,因此受到研究者的广泛关注。另一方面向量 l1/2正则化理论表明:相较于常用的 l1范数,l1/2范数可进一步诱导向量的稀疏性,在稀疏信号重建中对噪声具有更强的稳健性。为得到矩阵 D 更为精确的稀疏低秩表示,有学者将向量的 l1/2范数推广到矩阵,分别用 S1/2范数17 18(矩阵奇异值构成向量的 l1/2范数)和 l1/2范数来刻画矩阵的秩与稀疏度。与此同时,近年来越来越受到重视的折叠凹正则理论19 20表明,相比于凸正则,某些特殊的非凸正则在诱导低
18、秩性和稀疏性方面具有更大的优势。受 l1/2正则化理论的良好表现及拓展,本文将Capped-l1正则理论应用于矩阵问题中。事实上,我们的数值实验表明了相较于 RPCA 方法中的核范数正则,Capped-l1正则可进一步诱导低秩矩阵的低秩性,即拟解决的具体优化模型如下:()1,R,.minm nL SlLSstDSL+=+(3)其中,()min,1()min 1,m niiLL=,是给定的参数,()iL表示对低秩矩阵 L 进行奇异值分解(Singular Value Decomposition,SVD)后每一个奇异值所对应的项。考虑到 Capped-l1模型的目标函数与约束条件关于低秩矩阵与稀疏
19、矩阵是可分的,本文基于文献14中的交替方向乘子法(Alternating Direction Method of Multipliers,ADMM)算法思想提出交替迭代阈值算法。该算法利用增广 Lagrange 乘子技术,在迭代过程中采用交替投影的思想逐个更新低秩矩阵、稀疏矩阵和 Lagrange 乘子。低秩矩阵与稀疏矩阵的更新需要求解两个线性非凸优化子问题,之后通过将作用于贾凯贤 等 DOI:10.12677/orf.2023.134282 2820 运筹与模糊学 向量的 Capped-l1算子推广到矩阵情形,给出其子问题最优解的显式形式,避免每次迭代都要对矩阵进行奇异值分解的弊端,这从很大
20、程度上保证了所设计算法的高精度与低时间代价特性。与 ALM 算法相比,大量的模拟实验说明本文所提出的交替阈值迭代算法具有以下优点:达到收敛所需迭代次数与时间代价大幅降低、分解出的低秩矩阵的秩更接近于真实值并且同时算法的可靠性对矩阵 L 的低秩程度依赖更少。另外,在监控视频背景建模这一实际应用中,交替阈值迭代算法能得到更为稀疏的背景矩阵,具有更为稳健的恢复性能且时间代价相较于 ALM 算法降幅高达一个数量级,这对实际中海量视频数据的快速处理具有重要意义。2.交替方向乘子法交替方向乘子法 在本节中,我们提出交替方向乘子法来解决问题(3),并给出该算法的收敛性分析。2.1.交替方向乘子法的迭代框架交
21、替方向乘子法的迭代框架 本为了给出交替方向乘子法的迭代框架,我们首先给出问题(3)的增广拉格朗日函数:()()12,2FL S YLSY DLSDLS=+?,其中m nYR是 Lagrange 乘子,0表示违反线性约束的惩罚参数。给定(),kkkL S Y,那么用于解问题(3)的交替方向乘子法可以表示为求解如下三个子问题:()()()111111argmin,argmin,.kkkSkkkLkkkkSL S YLL SYYYDLS+=+(4)很容易可以看出(4)式中的第一个子问题可以表示为如下形式:1112122argmin,21argmin2argmin,2kkkkFSkkSFSFSSY D
22、LSDLSSSDLYSSY+=+=+=+?(5)其中1kkYDLY=+。显然(4)式问题有如下的闭式解()1signmax,0.kijijijSYY+=(6)根据求解(4)中第一个子问题的思想,(4)式中的第二个子问题可以等价的写为()()()2111212argmin,21argmin2argmin,2kkkkFLkkLFFLLLY DLSDLSLLDSYLLY+=+=+=+(7)其中11kkYDSY+=+,那么可得到问题(7)的解 贾凯贤 等 DOI:10.12677/orf.2023.134282 2821 运筹与模糊学 ()()111:kCappedCappedLYUTV+=?,(8)
23、这里U VY=是Y的奇异值分解,()1CappedT?是矩阵的阈值算子,即()111max,0,21,.2iiiiCappediiiiiiT +=+?(9)上述交替方向乘子法的关键是在每次迭代中交替更新低秩矩阵、稀疏矩阵和 Lagrange 乘子,直到满足算法的收敛条件。因此,算法整体的计算精度与时间代价在很大程度上取决于式(4)中两个子问题的求解。(6)与(8)给出了(4)中两个子问题的的显式解,因此我们提出了如下交替方向乘子法解问题(3):算法算法 2.1 交替方向乘子法(ADMM)初始步:初始步:初始化0000,Y L S 步步 1:计算:()1212111111argmin21argm
24、in()2kkkkSkFkkkkLkFkkkkkSSDLYSLLDSYLYYDLS+=+=+=+?(10)步步 2:设置1kk+=。步步 3:判断11kkFFDLSxtolD+是否成立,是则终止迭代;否则令1kk=+,转步 1。输出输出,kkL S 2.2.收敛性分析收敛性分析 本小结给出算法的收敛性分析,针对算法(2.1)有如下结论:定理定理 2.1 令(),kkkL S Y是由 ADMM 算法生成的迭代序列,则以下结论成立:i)序列(),kkkL S Y是有界的;ii)11lim0,lim0kkkkFFkkSSLL+=;iii)11lim0kkFkDSL+=,且(),kkkL S Y的聚点
25、是问题的可行解。证明证明.i)令kkkUV为矩阵11:kkkkYDSY+=+在1k+次迭代中的奇异值分解,根据1kL+在(8)中的定义,有()11.kkCappedkkLU TV+=?(11)贾凯贤 等 DOI:10.12677/orf.2023.134282 2822 运筹与模糊学 再由(10)中的第三个等式和(11),可得()()()11111111,kkkkkFFkkkkkFkkkkkCappedkkFkkCappedkFYYDLSYDLSUVU TVTm+=+=+=,立即可得()()()11111001011,2kkkkkkLSYL S Y+=+这里是21kkFYY的上界。上式也表明(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 监控 视频 背景 建模 一类 矩阵 优化 算法 研究
![提示](https://www.zixin.com.cn/images/bang_tan.gif)
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。