基于增量半监督判别分析的视频目标跟踪方法

基于增量半监督判别分析的视频目标跟踪方法

在视频序列中，快速、准确地跟踪一个感兴趣的目标物质，这是视频跟踪的基本任务，也是当前机械视觉领域的研究热点。主要困难包括如何处理视频序列中的目标物质的变化、目标物体的覆盖、摄像机运动和视角的变化。在基于判断方法的视频跟踪任务中，正确跟踪目标的主要组件包括：提取图像特征、检测跟踪头的结构、更新和存储、评估区域的分类等。提出了。后者是当前科学家的主要研究方向。现在，基于子空间研究的跟踪头被广泛使用。kim提出使用完全生成集的方法来更新线性评价分析中的类散度和总散度。在这项工作中，将此算法应用于视频跟踪的框架内，并获得了良好的跟踪效果。然而，这种方法的缺点是，（1）基于完整生成集的大规模更新具有很高的效率，但它不是分析噪声矩阵和总散射矩阵的更新，而是接近类之间的分散矩阵和总散射矩阵的更新。（2）在视频跟踪任务中，当需要新版本时，跟踪结构生成了大量的非标准样本。该方法（基于当前许多基于子空间学习的跟踪算法）直接将这些样本放入子空间，并将最接近目标模型特征的位置作为跟踪结果。这种方法忽略了未标记样本的几何结构信息，仅通过对新到达的样本进行分类和更新跟踪来执行。王等人通过半监测评估算法进行了改进，并实施了目标跟踪。然而，这种方法仅适用于在无需添加样本数的情况下添加样本数量。然而，在视频跟踪任务中，大量的批处值被发送并发送。本文使用最近提出的区域协方差矩阵(regioncovariancematrix,RCM)作为特征描述子,在保持各个区域的内在几何关系的基础上,将RCM从对称正定空间映射至欧氏空间,并通过类内散度、类间散度和正则项的增量更新,将半监督判别分析(semi-superviseddiscriminantanalysis,SDA)算法扩展到增量形式,用于目标跟踪.1数学基础1.1区域r空间特征基于区域协方差矩阵RCM的跟踪子源于Tuzel提出的快速简单的RCM计算方法.基于积分图像的概念,该算法能够在极短时间内(几毫秒)计算图像中大量区域的、由多种信息(如坐标、颜色、梯度等)融合而成的RCM.对于一幅二维图像I,假设某个区域R大小为M×N,其中每个像素点可生成一个d维的特征向量fk.在本文实验中,以该像素点二维坐标(x,y)和该点灰度值、沿x方向梯度幅值、沿y方向梯度幅值、沿x方向二阶梯度幅值、沿y方向二阶梯度幅值共7维特征构成RCM特征fk=[x,y,I,|gI-x|,|gI-y|,|gI-xx|,|gI-yy|].彩色图像的特征亦可与之类似提取.从而区域R的协方差矩阵CR可以表示为:CR=1ΜΝΜΝ∑k=1(fk-μR)Τ(fk-μR)(1)CR=1MN∑k=1MN(fk−μR)T(fk−μR)(1)其中,μR=ΜΝ∑k=1fkΜΝμR=∑k=1MNfkMN.为此,Tuzel等提出基于积分图像的方法快速求解大量区域的RCM.1.2asyn+n根据正定阵的定义易知,1.1节提取的区域协方差矩阵RCM都是对称正定阵,都落在对称正定(symmetricpositivedefinite,SPD)空间内.在定义了合理的乘法和数乘之后,该空间构成了SPD流形.记Symn是n阶实对称阵空间,Sym+n是n阶实对称正定阵空间,GLn是n阶实可逆矩阵的群,Mn是n×n的实矩阵空间.基于常用的矩阵加法和数乘的定义易证,Symn构成向量空间,但Sym+n不构成向量空间.两者通过矩阵指数映射和对数映射一一对应,即∀A∈Sym+n,B∈Symn,有:logm(A)∈Symn,expm(B)∈Sym+n(2)其中,logm和expm分别代表矩阵对数和矩阵指数.矩阵对数logm(S):=U.diag(log(d)).UT,U和λ是S的本征向量及其对应的本征值,diag(log(λ))是以log(λ)为对角线元素的对角阵,log是自然对数,T代表矩阵转置;类似地可以定义矩阵指数expm(S):=U.diag(exp(λ)).UT.在SPD流形上赋予不同的黎曼度量可以定义不同的SPD黎曼流形,常用的SPD流形上的黎曼度量包括仿射不变度量和对数-欧氏度量.1.2.1仿射不变度量在Sym+n上的任意一点X的切空间Symn上定义黎曼度量为〈y,z〉X=tr(X-1/2yX-1zX-1/2),其中,y,z∈Symn,便可得到黎曼指数映射为:expmX(y)=X1/2expm(X-1/2yX-1/2)X1/2(3)其逆映射、黎曼对数映射为:logmX(Y)=X1/2logm(X-1/2YX-1/2)X1/2(4)对于∀S1,S2∈Sym+n,两者之间的距离定义为:d2(S1,S2)=〈logmS1(S2),logmS1(S2)〉=tr(logm2(S1-1/2S2S1-1/2))=∑iln2λi(S1,S2)(5)其中,λi为(S1,S2)对应的广义本征值,i=1,…,n.该度量称为仿射不变度量.1.2.2synn,+sum+n,的逆映射进路S1⊙S2:=expm(logm(S1)+logm(S2))(6)Arsigny还证明了(Sym+n,⊙)是李群,且映射expm:(Symn,+)→(Sym+n,⊙)是李群同构,其逆映射logm:(Sym+n,⊙)→(Symn,+)也是李群同构.其上的距离度量定义如下:d2(S1,S2)=‖logm(S1)-logm(S2)‖F=tr((logm(S1)-logm(S2))2)(7)该度量称为对数-欧氏(Log-Euclidean)度量,其主要思想是:通过矩阵对数算子可以将SPD流形上的两个元素映射到向量空间上,再在向量空间上计算两者的欧氏距离.1.3状态转移概率模型在目标跟踪任务中,第t帧目标的位置及姿态可以通过一组仿射参数Xt={xt,yt,θt,st,αt,ϕt}确定,其中,(xt,yt)表示目标中心位移、θt表示旋转角度、st表示缩放尺度、αt表示方位率和ϕt表示倾斜角.目标的运动模型由仿射参数的状态转移概率模型给出.假设t+1时刻的状态服从以t时刻状态值Xt为均值、Ψ={σx,σy,σθ,σs,σα,σϕ}为方差的高斯分布:p(Xt+1|Xt)=N(Xt+1;Xt+1,Ψ)(8)在t+1帧内,根据(8)式随机生成N组仿射参数的集合{X1t+11t+1,…,XΝt+1Nt+1},由这组参数的仿射变换可得一组图像样本集{I1t+11t+1,…,IΝt+1Nt+1},以此作为目标在t+1帧内的候选图像区域.为了从候选图像样本集中选取最可能是目标的图像样本,可以根据先前已有的跟踪结果构造一组线性判别空间,将候选图像样本集都投影至该判别空间中,计算各样本的投影与判别空间中目标类样本投影均值m0的距离D:D=‖ITU-m0‖(9)其中U为投影矩阵.选取最短距离对应的样本作为当前帧中的目标.2半微量监督分析方法本节首先简要回顾原始半监督判别分析SDA方法,然后将其扩展到增量ISDA形式.2.1原始半监督分析方法2.1.1正则化法对于二分类问题,若给定M1个标记样本{xi,yi},i=1,…,M1,其中xi∈Rd,yi∈{+1,-1},线性判别分析LDA的目标函数为:v*=argmaxvvΤSbvvΤStv(10)v∗=argmaxvvTSbvvTStv(10)其中,Sb=∑kmk(μk-μ)(μk-μ)T是类间散度矩阵,St=∑i(xi-μ)(xi-μ)T是总体散度矩阵.mk和μk是样本数量和类k(=1,2)的均值,μ是整体样本均值,v*是最优映射方向.(10)式的最优化问题等价于求解广义本征问题:Sbv=λStv(11)再在式(10)中引入正则子,得到正则化RDA:v*=argmaxvvΤSbvvΤStv+βJ(v)(12)v∗=argmaxvvTSbvvTStv+βJ(v)(12)其中,J(v)是基于判别的经验损失定义的正则项,β是模型复杂度与经验损失之间的平衡因子.2.1.2sda的目标函数假设有额外M2个未标记样本{xi},i=1,…,M2,其中xi∈Rm.在(12)式基础上,SDA通过基于图表示的正则子J(v)在最优化过程中嵌入样本的几何结构:J(v)=∑i,j(vTxi-vTxj)2Sij(13)其中,若样本xi是xj的K-最近邻或者样本xj是xi的K-最近邻,则Sij=1,否则Sij=0.Cai假设:如果两个样本在原始空间内接近,那么在SDA映射空间内它们也应该接近.因此,根据(13)式可知:只有相互邻近的一对样本才在J(v)中有意义,即SDA算法能够保持样本的局部几何结构.Cai证明了,J(v)=2vTX(D-S)XTv=2vTXLXTv,其中S,D,L都是M2阶对称阵,且S={Sij},D是对角元素为Dii=∑jSij的对角阵,L=D-S是Laplacian矩阵.SDA的目标函数记作:v*=argmaxvvΤSbvvΤ(St+βXLXΤ)v(14)v∗=argmaxvvTSbvvT(St+βXLXT)v(14)这等价于求解如下的广义本征值问题:Sbv=λ(St+βXLXT)v(15)2.2基于矩阵对数映射的解析法一般情况下,要计算两个RCM样本(见2.1节的特征提取方法)间的距离或者是要获取一组未标记样本间的几何结构,可以按照1.2节的方法进行.但是在基于判别子空间的跟踪中,每个样本被描述为一个列向量,但RCM特征都是二维的d阶对称正定阵,不能直接使用投影子空间进行投影.常见的基于子空间学习的跟踪方法是先通过矩阵对数映射将对称正定阵Ci映射为对称阵logm(Ci),再按列优先拉伸为d2维欧氏空间内的列向量li.这种方法破坏了RCM特征样本间的几何结构,即若假设l1,l2分别为logm(C1)和logm(C2)拉伸成的n2维列向量,则‖l1-l2‖2≠‖logm(C1)-logm(C2)‖F.借助Sivalingam的方法,将对称正定流形上的对数-欧氏度量转换为向量空间上的欧氏度量.使得:d2(C1,C2)=‖logm(C1)-logm(C2)‖F=‖c1-c2‖2(16)其中,ci是Li=logm(Ci)的上三角部分与矩阵的乘积,即ci=Liupper.UT,其中,′.′代表矩阵对应位置上的元素相乘,ci的维数为d(d+1)/2,i=1,2.Liupper的前d维和后m=d(d-1)/2维分别是Li的上三角阵中的对角线元素和非对角线元素.与将d维对称正定阵直接拉成d2维列向量的方法相比,通过该变换可以很好地保持各个特征之间的几何结构,同时又降低了特征的维数(前者为d2维,后者为d(d+1)/2维).2.3有机帧集的形成视频跟踪任务的特点是,在每一帧都有大量无标记的新样本到达,而跟踪子的目的就是要在这些新样本中找出与目标最为接近的那个.原始的SDA算法不具备增量更新的能力,如果直接将其用于跟踪任务中,会导致跟踪子对于目标出现外观、光照变化或者遮挡等各种情形时的误跟踪和丢失跟踪.本节设计了一种增量在线学习方法(incrementalsemi-superviseddiscriminantanalysis,ISDA),通过增量地更新(15)式中的每一项,来实现SDA整体的增量更新.由(15)式不难看到,这里需要增量更新的项包括:类间散度矩阵Sb、整体散度矩阵St和作为正则项的P=XLXT.2.3.1符号定义假设在每一帧中共有三种类型的样本:在上一帧得到的l+个已标记正类样本F+和l-个已标记负类样本F-(记Fl={F+,F-}为标记样本集),以及在当前帧生成的n个无标记样本Fu.即,当前帧的样本集为{F+,F-,Fu},样本总数为l++l-+n.所有样本均值为μ,正类样本均值为μ+,负类样本均值为μ-,标记样本均值为μl,无标记样本均值为μu.增量更新的目的是要在已知上一帧的映射矩阵U的前提下,在当前帧有大量无标记样本到达后,更新得到当前帧的映射矩阵Unew,使得:(1)当前帧内的所有样本能够尽可能正确分类;(2)与目标模板最接近的样本在映射空间内也与目标模板最接近.2.3.2类间散度矩阵Sb的增量更新当所有的Fu被赋予类别标签后,样本集记作{Fnew+,Fnew-},其中,正类样本个数为n+(≥l+)、负类样本个数n-(≥l-),n++n-=l++l-+n;正类样本均值为μnew+,负类样本均值为μnew-(这两者可以由原来的μ+和μ-,以及Fu内的所有样本及其分类情况来计算).类间散度矩阵更新公式为:Snewb=n+(μnew+-μ)(μnew+-μ)Τ+n-(μnew--μ)(μnew--μ)Τ=n+(μnew+-μ)(μnew+-μ)Τ+n-((n++n-)μ-n1μnew+n--μ)×((n++n-)μ-n+μnew+n--μ)Τ=n+n-+(n+)2n-(μnew+-μ)(μnew+-μ)Τ(19)Snewb=n+(μnew+−μ)(μnew+−μ)T+n−(μnew−−μ)(μnew−−μ)T=n+(μnew+−μ)(μnew+−μ)T+n−((n++n−)μ−n1μnew+n−−μ)×((n++n−)μ−n+μnew+n−−μ)T=n+n−+(n+)2n−(μnew+−μ)(μnew+−μ)T(19)其中,μ为全体样本均值,与2.3.1节中的μ相等.2.3.3总体散度矩阵St的增量更新根据本文的跟踪框架(见2.4节),这里的总体散度矩阵更新是指:针对于在上一帧得到的总体散度矩阵Sltlt(上一帧的所有样本均已是标记样本,因此在这里使用上标‘l′来以示区别)的基础上,在当前帧新生成N个未标记样本的情况下,实施增量更新.假设当前帧新生成N个未标记样本的总体散度矩阵为Sutut,那么组合后的所有样本{Fl,Fu}的总体散度矩阵为:Snewt=l++l-+Ν∑i=1(fi-μ)(fi-μ)Τ=l++l-∑i=1(fli-μ)(fli-μ)Τ+Ν∑j=1(fuj-μ)(fuj-μ)Τ=l++l-∑i=1(fli(fli)Τ-2fliμΤ+μμΤ)+Ν∑j=1(fuj(fuj)Τ-2fujμΤ+μμΤ)=l++l-∑i=1fli(fli)Τ-2(l++l-∑i=1fli)μΤ+Ν∑j=1fuj(fuj)Τ-2(Ν∑j=1fuj)μΤ+l++l-+Ν∑i=1μμΤ=Slt+Sut+(l++l-)μl(μl)Τ-2(l++l-)μlμΤ+Νμu(μu)Τ-2ΝμuμΤ+(l++l-+Ν)μμΤ=Slt+Sut+(l++l-)Ν(l++l-+Ν)(μl-μu)(μl-μu)Τ(20)Snewt=∑i=1l++l−+N(fi−μ)(fi−μ)T=∑i=1l++l−(fli−μ)(fli−μ)T+∑j=1N(fuj−μ)(fuj−μ)T=∑i=1l++l−(fli(fli)T−2fliμT+μμT)+∑j=1N(fuj(fuj)T−2fujμT+μμT)=∑i=1l++l−fli(fli)T−2(∑i=1l++l−fli)μT+∑j=1Nfuj(fuj)T−2(∑j=1Nfuj)μT+∑i=1l++l−+NμμT=Slt+Sut+(l++l−)μl(μl)T−2(l++l−)μlμT+Nμu(μu)T−2NμuμT+(l++l−+N)μμT=Slt+Sut+(l++l−)N(l++l−+N)(μl−μu)(μl−μu)T(20)其中,fi∈F,fil∈Fl,fju∈Fu.2.3.4正则项P的增量更新增量更新P=XLXT的最大问题是:矩阵X和L不可能增量地存储,因为其大小会随着跟踪的进行而快速增长.这里使用一种估计的方法,假设标记样本集Fl和未标记样本集Fu的计算得到的表示各自样本间几何关系的正则项分别为Pold和Pcur,那么组合后的样本集{Fl,Fu}所对应的正则项为:Pnew=Pold+Pcur(21)这么做的前提是:每次更新只关心新到的未标记样本间的几何结构,而与原有的样本无关.2.4广义本征值分解的时间复杂度本节基于上面提出的增量SDA方法实施目标跟踪.跟踪框架如表1所示.2.4.1算法时间复杂度分析本文的方法是一种基于批量更新的SDA算法.一般认为,其时间复杂度主要是表1第9步的广义本征值分解产生的,为O(min(d3,N3)),其中,d为样本特征维数,N为样本数量.根据2.2节的分析,若按照1.1节提取样本特征,则d=28,而N一般都大于d(本文取N=200),因此广义本征值分解的时间复杂度为O(d3);(19)式的时间复杂度为O(d2),(20)式的时间复杂度为O(dN),(21)式的时间复杂度为O(dN2).总的来说,2.3节给出的增量SDA的时间复杂度为O(dN2).3增量线性判别分析ilda本节在视频序列sylv和davidin300上验证第2节给出的跟踪框架,并与其他跟踪方法进行比较.对每组视频序实施三次实验,实验1:表1所示的ISDA跟踪框架(图1、2第1行);实验2:表1所示的ISDA跟踪框架,但并不按2.2节的方法将样本RCM特征映射至