一种基于单帧随机稀疏采样的快速目标搜索算法

摘要

本发明公开了一种基于单帧随机稀疏采样的快速目标搜索算法，属于视觉目标跟踪领域。本发明在现有的基于粒子滤波的视觉目标跟踪基础上，动态的控制每帧图像采集的样本数，并指导每帧采集的样本逐渐向目标靠近。通过多次测试的结果表明，该方法较于传统方法明显提高了运算速度，并且对于快速变化的目标具有更加稳定的跟踪效果。

说明书

技术领域

本发明涉及视觉跟踪领域，具体涉及到一种新的目标搜索算法。

背景技术

视觉跟踪技术是通过图像处理的算法实现对视频中某一目标的持续定位跟踪，进而可以判断目标的运动轨迹等行为特征。该技术的主要指标包括速度与鲁棒性，速度指跟踪算法的运算耗时多少，鲁棒性则指跟踪算法是否在各种环境下准确的对目标进行跟踪。

跟踪面临的问题包括光照条件改变、遮挡、物体快速运动、运动模糊等，现有跟踪方法包括基于目标运动特征的跟踪算法、基于跟踪序列前后相关性的目标跟踪算法、基于特征点的相关算法、基于目标特征参数的跟踪算法等，这些方法都有各自适用的跟踪条件。近年来兴起的L1范数跟踪是在粒子滤波算法框架上，加入了稀疏表示原理的跟踪方法，这种方法在多种跟踪环境下都表现出较强的鲁棒性。

粒子滤波基于蒙特卡罗方法，利用粒子集来表示概率，可以用在任何模式的状态空间模型上。它在非线性、非高斯系统表现出了优越性，在视觉跟踪中广泛的使用这种方法来指导样本的采集，他计算量小，准确度高。

现有的基于粒子滤波的跟踪器在同一视频的每一帧都采集相同个数的样本，或根据目标的外形等特征事先预测所需样本数。对于一个用于跟踪的视频来说，目标运动到不同的位置，其光照条件、遮挡情况、背景复杂度等跟踪条件不同，所需要采集的样本数也就不同，不变动采样数去适配每一帧的情况，会出现样本的浪费，或某些帧样本的不足。所需样本数和目标特征、背景情况、光照条件等很多因素相关，难以给出一个十分恰当的预测，故采用预测的方法不能很精准的控制所需样本数。而样本数的多少和跟踪的速度和鲁棒性有直接的关系。

此外现有算法每一帧进行一次采样，采样后根据各样本的概率在下一帧进行重采样。由于是处于不同帧，目标状态可能已经发生了改变，故这种重采样只能近似估计下一帧的目标状态，没有充分利用重采样的价值，甚至可能因为样本的分散造成样本浪费过多而跟丢目标，对快速运动物体的跟踪能力也不够强，

发明内容

本发明的主旨在于通过对样本搜索方法的改进，提高跟踪的速度，并且对快速变化的目标可以更稳定的跟踪。

为了解决上述技术问题，达到上述目的，本发明采用如下技术方案：

一种基于单帧随机稀疏采样的快速目标搜索算法，其中包括如下步骤：

步骤1、初始化为后续步骤做准备；

步骤2、读取待处理帧f_i，其中i表示待处理帧的序号；

步骤3、把上帧的跟踪结果做为中心，按高斯随机分布采集M个样本y₁～y_M；

步骤4、计算各个样本为目标的概率上界q₁～q_M，并以此由高到低确定接下来的样本处理顺序,若概率上界无法计算则使之为1，概率上界相等的样本之间可以按任意方式排序；

步骤5、依次计算各样本为目标的概率p_i，其中i表示样本的序号，并判断样本概率是否达标，若达标则以此样本作为跟踪结果并直接进入步骤7，若处理完y₁～y_M无达标的样本，则进入步骤6；

步骤6、判断采样数是否达到预设上限，若达到则选取本帧所有样本中概率p最大的样本作为跟踪结果，进入步骤7，否则进行重采样得到新的y₁～y_M，再退回到步骤4；

步骤7、若处理完毕所有待处理帧则结束算法，否则退回步骤2读取下一帧。

上述技术方案中，所述步骤3中跟踪结果为可以表示跟踪结果信息的各参数C＝(c₁,c₂,……,c_n)，具体步骤为：进行M次包含C中元素与从高斯随机分布产生的随机数的算式的运算，得到新的参数C₁～C_M以代表样本相关信息，以此作为样本或产生样本。

上述技术方案中，所述步骤4中样本概率上界q_i指步骤5中对对应样本计算的概率p_i所可能出现的最大值,若概率上界无法计算则使之为1，概率上界相等的样本之间可以按任意方式排序。。

上述技术方案中，所述步骤5中首先令概率上限阈值为0，每个样本处理前都应判断概率上界q_i是否超过阈值q_th，若未超过直接认为概率p_i为0，若超过则计算样本的概率，处理完每个样本要更新概率上界阈值q_th。

上述技术方案中，所述步骤5中样本达标指计算出的样本概率p_i达到预先设定的标准p_th，每计算完一个样本或多个样本的概率，判断一次是否有样本达标。

上述技术方案中，所述步骤6中重采样指根据各样本所算得的概率pi决定新的样本组C_N1～C_NM中，复制各样本参数C_i而来的样本的个数，对于C_N1～C_NM的每个或部分参数，用包含此参数与从高斯随机分布取得的随机数的算式，得到扰动后的参数代替原C_N1～C_NM中的参数。

与现有技术相比，本发明具有如下有益效果：

本发明提出在有样本达标时不再处理剩余样本，减少了冗余样本的处理，可以动态的控制处理的样本数量，且不需要每帧事先预测所需样本数，在保证精度的前提下提高了跟踪的速度。并且提出了单帧多次采样的方法，在单帧重采样的过程实际上是指导样本在状态空间向目标移动的过程，因此相比传统方法对快速变化的目标的跟踪能力明显提高。同时把原本的帧之间的重采样改为只复制上帧跟踪结果并产生高斯随机扰动，以此作为样本，防止样本数量少时，重采样造成的样本过度分散的情况。

附图说明

图1为一种基于单帧随机稀疏采样的快速目标搜索算法的流程图；

图2为一次采样与重采样过程的示意图,注：图2为一张附图，而非多张附图。

图3为对快速运动物体的跟踪结果举例。

具体实施方式

下面对本发明的具体实施方式作进一步的描述。

步骤1、产生模板T₁～T_N；

步骤2、读取待处理帧f_i；

步骤3、把上帧的跟踪结果做为中心，按高斯随机分布采集一组样本y₁～y_M；

步骤4、计算各个样本为目标的概率上界q₁～q_M，并以此由高到低确定接下来的样本处理顺序，概率上界相等的样本之间可以按任意方式排序；

步骤5、依次使用模板稀疏表示概率上界达标的样本，使用表示结果计算各样本为目标的概率p_i，并判断样本概率是否达标，若达标则进入步骤7，不再处理剩下的样本，若处理完y₁～y_M无达标的样本，则进入步骤6；

步骤6、判断采样数是否达到预设上限，若达到则选取本帧所有样本中概率p最大的样本作为跟踪结果，进入步骤7，否则进行重采样得到新的y₁～y_M，再退回到步骤4；

步骤7、更新模板并退回到步骤2读取下一帧。

上述技术方案中，所述步骤1的具体流程为：指定好需要的模板大小X*Y(例如12*15)与个数N(例如10)，读入跟踪视频的第一帧，手动输入平行四边形相邻的三个顶点坐标产生原始平行四边形框定待跟踪的物体。将框定的顶点坐标复制N个，对每个坐标加上均值为0，标准差为0.6的高斯随机扰动，产生N个相近的平行四边形，求(1,1)、(1,X)、(Y,1)变换到每个平行四边形三个相邻的顶点坐标的仿射变换矩阵，(1,X)、(Y,1)中的X、Y为模板大小X*Y中的X、Y。公式如下：

$R=\left(\begin{array}{ccc}{y}_1& y_2& y_3\\ x_1& x_2& x_3\\ 1& 1& 1\end{array}\right)/\left(\begin{array}{ccc}1& X& 1\\ 1& 1& Y\\ 1& 1& 1\end{array}\right)---\left(1\right)$

其中(x₁,y₁)可以为平行四边形任一顶点坐标，(x₂,y₂)，(x₃,y₃)为与(x₁,y₁)顺时针相邻和逆时针相邻的两个顶点，R为求得的3*3的仿射变换矩阵，需注意每个平行四边形(x₁,y₁)的选定要统一，即都是由原始平行四边形的同一点高斯随机扰动产生的。得到N个R后，取R的第一行和第二行的六个元素为仿射系数，排列为一个行向量(R(1,1),R(1,2),R(2,1),R(2,2),R(1,3),R(2,3))，每组仿射系数对应一个平行四边形的三个顶点坐标，故使用这六个系数就可以代表一个平行四边形，下述步骤中均以此方法代表平行四边形。

借助此矩阵算出X*Y的模板中，每个坐标对应的原图里的坐标，并将原图对应坐标的灰度值赋到模板中。然后将每个模板按固定方式变形为一个列向量，然后对其减均值除标准差，变为0均值，标准差为1的向量。称之为N个目标模板，再产生一个列数为X*Y的单位矩阵，作为X*Y个琐碎模板。

上述技术方案中，所述步骤3的具体流程为：把上帧框选结果的平行四边形的六个仿射系数组成的向量C复制M(例如50)个，对每组的第1、4个系数分别乘以10的a次方和10的b次方，a、b由高斯随机分布产生，对每组其余的四个系数，均加上一个由高斯随机分布产生的随机数。对每个系数的高斯随机分布的均值都为0，标准差则事先指定(例如按顺序依次为0.03,0.0005,0.0005,0.03,1,1)。由此产生了M组与上帧采样结果相近的仿射系数C₁～C_M，使用与步骤1产生模板相同的方法，用这些仿射系数产生M个样本。

上述技术方案中，所述步骤4的具体流程为：对每个样本y，计算下式：

其中T_t为目标模板。

则概率上界为：

$p=\frac{1}{\Gamma }\exp \{-\alpha ||y-T_t\hat{a}|{|}_2^2\}---\left(3\right)$

其中Γ为归一化因子(可设为1)，α为预设常数(例如50)。

记录下每个样本的概率上界并从高到低排序作为接下来样本处理的顺序。

上述技术方案中，所述步骤5的具体流程为：

按步骤4所排顺序逐个处理。首先设定概率上界阈值为0。

针对每个样本y，如果它的概率上界不小于阈值，则计算如下最优化问题：

$\begin{array}{ccc}\underset{a}{\min }\frac{1}{2}\left|\right|y-A^{\prime }a|{|}_2^2+\lambda |\left|a\right|{|}_1+\frac{{\mu }_t}{2}\left|\right|a_I|{|}_2^2,& s.t.& a_T\ge 0\end{array}---\left(4\right)$

其中A’＝(T_t,I)，T_t为目标模板组，I(单位矩阵)为琐碎模板组，a＝(a_T；a_I)，a_T为目标模板的加权系数向量，a_I为琐碎模板的加权系数向量。当检测到有遮挡时μ_t为0，否则为一预先指定的数(例如10)。λ也为预先指定的数(例如0.2)。公式中s.t.的是最优化问题的约束条件符号。

求解该最优化问题可以按照Chenglong Bao等人提出的方法采用加速近端梯度(accelerated proximal gradient)法。

利用求解出的a来判断此样本为目标的概率：

$p=\frac{1}{\Gamma }\exp \{-\alpha ||y-T_t{a}_T|{|}_2^2\}---\left(5\right)$

其中Γ为归一化因子(可设为1)，α为预设常数(例如50)。

然后更新概率上界阈值为原阈值加上p/2M。

如果样本概率上界小于阈值，则不对其进行处理，直接令其概率为0。

每个样本计算完概率后，都判断一次此概率是否超过预设的要求，若超过则中断，不再处理剩下的样本，直接将此样本作为跟踪结果。

上述技术方案中，所述步骤6的具体流程为：在步骤5中若处理完全部M个样本都没有发现达标样本，则判断目前采样数是否已经达到上限(例如600)，若已达到，则选取本帧采集的所有样本中，概率最大的作为跟踪结果，若未达到，进行重采样，再退回到步骤4。

其中，重采样是指把概率高的样本复制多份，概率低的样本复制少份，概率再低的则直接删除。具体方法是先计算M个样本的概率和，然后算出各样本的概率占概率和的比例，用此比例乘以M后四舍五入取整数，就是该样本复制后个数，0就代表直接删除。然后再按照步骤3的方法对这些样本进行高斯随机扰动得到新样本组的M组仿射系数C_N1～C_NM，以此使用与步骤1产生模板相同的方法形成重采样的M个样本。

上述技术方案中，所述步骤7的具体流程为：判断权重最大的模板和目标的匹配程度，可以采用直接相减的方法，若匹配程度不达到要求，例如直接相减后误差绝对值之和大于0.9，则用此样本代替权重最小的模板。然后回到步骤2读取下一帧。