基于矩阵操作及递归运算的运动物体轨迹实时检测方法

摘要

一种视频图像处理技术领域的基于矩阵操作及递归运算的运动物体轨迹实时检测方法，通过轨迹初始值的确定后，递归确定任意时刻每个物体的位置，即除初始时刻之外的时刻的列向量；再将初始位置和任意时刻每个物体的区域信息根据时间串联，即得到最终的运动轨迹。本发明可以快速计算得出运动物体的轨迹，达到实时的效果，并且每当有新的时刻点加入时，也能通过递归结构迅速得出新的时刻点的轨迹。在运算过程中，能够检测出所给问题解是否唯一。

说明书

技术领域

本发明涉及的是一种计算机视频信息处理领域的技术，具体是一种基于矩阵操作及递归运算的运动物体轨迹实时检测方法。

背景技术

随着计算机技术与多媒体技术的发展，智能监控系统在日常生活中扮演着越来越重要的角色。智能监控系统是采用图像处理、模式识别和计算机视觉技术，通过在监控系统中增加智能视频分析模块，借助计算机强大的数据处理能力过滤掉视频画面无用的或干扰信息、自动识别不同物体，分析抽取视频源中关键有用信息，快速准确的定位事故现场，判断监控画面中的异常情况，并以最快和最佳的方式发出警报或触发其它动作，从而有效进行事前预警，事中处理，事后及时取证的全自动、全天候、实时监控的智能系统。在智能监控系统的多种应用当中，运动物体轨迹的认定是非常典型而有潜力的一种。以十字路口的行人为例，通过长时期监测某一路口的行人运动轨迹并做出统计和分析，我们能够得到一些信息：异常的行为(逆行或闯红灯)；任意两个路口的行人流量(从而可以控制红绿灯时间长短)；行人流量随时间的分布等。

在视频数据挖掘领域，运动物体轨迹认定技术主要是利用数学模型对已有信息进行分析，计算得出相应的轨迹并应用于后续的事件分析和干预等。通过视频数据的前期处理，可以得到两个数据信息：被监控区域相互之间的拓扑结构；任意时刻每个摄像机所监测到的物体数目。如何使用这两个信息计算出运动物体的轨迹是一个研究热点。

为了便于数学描述，将问题简化如下：有m个摄像机无死角无重叠地覆盖研究范围，每个摄像机用S_i表示(i＝1,2,…,m)，即研究范围被分成m个区域。在研究范围中有n个运动物体，每个物体用X_j表示(j＝1,2,…,n)。τ表示每个时刻点，总时间为t，即τ＝1,2,…,t。观察矩阵C_m×t是一个m行t列的矩阵，表示第i个摄像机在第τ时刻时观察到的物体数量。关联矩阵A_m×m是一个对称方阵，表示任意两个摄像机区域的连通关系，即在设定的时间间隔内，物体能否从一个摄像机下运动到另一个摄像机下，能则表示连通，相应矩阵元素为1，否则矩阵元素为0.每个物体的实际运动轨迹存放于矩阵P_n×t中，其中的元素表示第j个物体在第τ时刻时所属的摄像机编号(即区域编号)。所需解决的问题是如何根据已知条件C_m×t和A_m×m计算得出物体运动轨迹并且要与实际轨迹P_n×t一致。

基于整数规划的迭代算法能够解决该问题，它根据观察信息建立规划方程，利用关联矩阵构造约束条件进行整数规划，迭代出一个解之后运算结束。但是该方法有一些缺陷：计算时间长无法实时监测轨迹；性能不灵活；不能判断解的特性。因此，需要一个新的技术来解决这些问题并达到实时轨迹认定的效果。

发明内容

本发明针对现有技术存在的上述不足，提出一种基于矩阵操作及递归运算的运动物体轨迹实时检测方法，采用根据时刻点递归的运算结构，定义两种矩阵操作，以这两种矩阵操作为基础并结合矩阵的行初等变换进行运动物体轨迹的认定。通过此方式，可以快速计算得出运动物体的轨迹，达到实时的效果，并且每当有新的时刻点加入时，也能通过递归结构迅速得出新的时刻点的轨迹。在运算过程中，能够检测出所给问题解是否唯一。

本发明是通过以下技术方案实现的：本发明包括以下步骤：

步骤1，轨迹初始值的确定

将观察矩阵C_m×t表示为t个列向量的组合，即：$>C_{m\times t}=\left(\begin{array}{cccccc}{C}_{m\times 1}^1& C_{m\times 1}^2& ...& C_{m\times 1}^{\tau }& ...& C_{m\times 1}^t\end{array}\right),$>其中：列向量表示在时刻τ，每个摄像机观察到的物体个数；同样地，将用来表示本发明计算结果的矩阵也表示为t个列向量的组合，即：$>\widehat{P_{n\times t}}=\left(\begin{array}{cccccc}\widehat{P_{n\times 1}^1}& \widehat{P_{n\times 1}^2}& ...& \widehat{P_{n\times 1}^{\tau }}& ...& \widehat{P_{n\times 1}^t}\end{array}\right),$>其中：列向量表示在时刻τ，每个物体所在的被观察区域(即所属的摄像机编号)，轨迹初始值即列向量的值。

所述的观察矩阵通过对待处理视频进行预处理得到，本发明中预设每个摄像机下的物体数为已知。

所述的列向量具体是指：初始时刻(τ＝1)下各个物体所在的区域编号；所述的列向量具体是指：在初始时刻每个区域摄像机所监测到的物体的个数，根据可以直接写出向量的值。

步骤2，递归确定任意时刻每个物体的位置，即除初始时刻之外的时刻τ时的列向量

1)将关联矩阵A_m×m与τ时刻的观察值进行置零运算后再与τ-1时刻的观察值进行叉乘运算，得到包含了从时刻τ-1到时刻τ可能发生的轨迹，即可能轨迹集

所述的关联矩阵A_m×m表示任意两个摄像机区域的连通关系，其包含了从上一时刻(τ-1)到这一时刻(τ)所有可能在这片研究范围内发生的运动轨迹，具体为：当A_m×m中的任一元素A_ij＝1，则表示从时刻τ-1到时刻τ可能会有物体从区域j运动到区域i；当A_ij＝0则表示从时刻τ-1到时刻τ不可能有物体从区域j运动到区域i，具体为：

当τ时刻的观察值中的第i个元素为0，则表示从时刻τ-1到时刻τ没有物体进入区域i，因此将A_m×m的第i行都置为0；

当τ时刻的观察值中的第i个元素不为0，则表示从时刻τ-1到时刻τ有物体进入区域i，因此A_m×m的第i行不变。

当τ-1时刻的观察值中的第l个元素为0，则表示从时刻τ-1到时刻τ没有物体从区域l出发，因此A_m×m的第l列都置为0；

当τ-1时刻的观察值中的第l个元素不为0，则表示从时刻τ-1到时刻τ有物体从区域l出发，叉乘运算将区域l出发的物体个数信息加入到经过置零运算之后的关联矩阵中。

所述的可能轨迹集中的元素意义为：当则从时刻τ-1到时刻τ没有物体从区域j运动到区域i；当则从时刻τ-1到时刻τ可能有k个物体从区域j运动到区域i，其中k为正整数。

所述的置零运算是指：当H_k×k是一个元素任意的k维方阵，L_k×1是一个元素任意的列向量，其中：结果矩阵B_k×k是一个k维方阵，其第i行的元素按以下公式得到：$>B_{\mathrm{ij}}=\left(\begin{array}{ccc}0,& \mathrm{if}& L_{i1}=0\\ H_{\mathrm{ij}},& \mathrm{if}& L_{i1}\ne 0\end{array}\right),\mathrm{fori},j\in [1,k],$>即当矩阵L的第i个元素为0，则矩阵B_k×k的第i行元素全为0；当矩阵L的第i个元素不为0，则矩阵B_k×k的第i行元素等于矩阵H_k×k的第i行元素。

所述的叉乘运算是指：当H_k×k是一个元素任意的k维方阵，L_k×1是一个元素任意的列向量，$>B_{k\times k}=H_{k\times k}\otimes L_{k\times 1}=\left(\begin{array}{ccc}{B}_{11}\times L_{11}& ...& B_{1k}\times L_{k1}\\ B_{21}\times L_{11}& ...& B_{2k}\times L_{k1}\\ .& .& .\\ .& .& .\\ .& .& .\\ B_{k1}\times L_{11}& ...& B_{\mathrm{kk}}\times L_{k1}\end{array}\right),$>即将矩阵H_k×k的每一行的元素分别与矩阵L_k×1的对应元素相乘，结果矩阵B_k×k是一个k维方阵。

2)对可能轨迹集进行优化：去掉当前时刻可能轨迹集中多余的轨迹，得到当前时刻实际轨迹集使得所有物体及其对应的轨迹都是确定的，即中所包含的的轨迹数目跟物体数目一致，并且每条轨迹的出发点和到达点与观察信息和一致。

在计算轨迹数目时，对自区域j到区域i重复的轨迹因其属于不同的物体，视为多条不同的轨迹，因此中轨迹的数目即所有元素之和。

3)基于矩阵行初等变换方式实现到的转化，具体为：将变成行阶梯型矩阵用可逆矩阵S记录到的转化时前两种行初等变换过程，对可逆矩阵S求逆并作用于即可得到当前时刻实际轨迹集然后由当前时刻实际轨迹集得到其中：当前时刻实际轨迹集中包含的信息是从时刻τ-1到时刻τ每个物体的运动轨迹，为时刻τ每个物体所在的区域。

所述的初等变换方式包括：

a)交换两行，以实现临时改变时刻τ各个摄像机(区域)的编号；

b)对某一行所有元素乘以非零常数k，以对各个摄像机下人数做归一化处理。

c)对某一行所有元素加上另一行对应元素的相同的倍数，以去除多余的轨迹。

其中：a和b分别改变了时刻τ各个摄像机的编号和各个摄像机下的人数，需要恢复；而c去除多余轨迹，不需要恢复。

步骤3，轨迹串联得到运动物体轨迹将步骤1得到的初始位置和步骤2得到的任意时刻每个物体的区域信息根据时间串联，即得到最终的运动轨迹$>\widehat{P_{n\times t}}=\left(\begin{array}{cccccc}\widehat{P_{n\times 1}^1}& \widehat{P_{n\times 1}^2}& ...& \widehat{P_{n\times 1}^{\tau }}& ...& \widehat{P_{n\times 1}^t}\end{array}\right).$>

当各个摄像机之间的连通性特别好，如A_m×m中的元素值为1比较多，根据观察信息是不足以确定各个物体的实际轨迹的。因为在第三步多余轨迹的去除环节，有些轨迹是没有足够的理由将其去除的，这就把这个问题变成了一个多解问题，因此需要对当前时刻可能轨迹集矩阵进行多解检测，具体为：对于当前时刻可能轨迹集矩阵中的非零元素能够构成一个井字型(或”#”形)，则判定为多解问题，然后将所有可能解中元素中最接近于主对角线的结果作为运动物体轨迹。

技术效果

与现有技术相比，本发明运用矩阵操作和递归运算，以各个时刻摄像机的观察值和各个区域连通性为输入条件，求解各个物体的实际运动轨迹。由于矩阵操作的便捷性，本发明花费时间大大少于基于整数规划的迭代算法。此外，本发明可以直接递归运算并达到实时的效果，解决了基于整数规划的迭代算法的不足。对于关联性特别好的区域，会造成多解，本发明可以检测出该问题并根据自行设定的规则给出一个合理的解，而基于整数规划的迭代算法不能检测出多解，并且在迭代出一个解算法自动终止。因此，本发明在效率、灵活性、合理性上都有了很大的提高。

附图说明

图1为本发明流程示意图。

具体实施方式

下面对本发明的实施例作详细说明，本实施例在以本发明技术方案为前提下进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施例。

实施例1

如图1所示，本实施例包括：

首先，给出所要解决的问题基本信息：4个摄像机(观察区域)，3个运动物体，5个观察时间点。关联矩阵$>A_{m\times m}=A_{4\times 4}=\left(\begin{array}{cccc}1& 1& 0& 0\\ 1& 1& 1& 0\\ 0& 1& 1& 1\\ 0& 0& 1& 1\end{array}\right),$>观察矩阵$>C_{m\times t}=C_{4\times 5}=\left(\begin{array}{ccccc}1& 1& 0& 0& 0\\ 1& 0& 2& 0& 2\\ 0& 1& 1& 2& 0\\ 1& 1& 0& 1& 1\end{array}\right).$>

根据发明内容，本发明的实施例分为以下五个步骤：

第一步，定义两种矩阵操作符，这一步不必进行。

第二步，轨迹初始值的确定

观察矩阵初始时刻的观察值$>C_{m\times 1}^1=\left(\begin{array}{c}1\\ 1\\ 0\\ 1\end{array}\right),$>不妨认为这三个物体编号为1,2,3.在初始时刻，第一个物体出现在区域1，第二个物体出现在区域2，第三个物体出现在区域4。由此，轨迹初始值为：$>\widehat{P_{n\times 1}^1}=\widehat{P_{3\times 1}^1}=\left(\begin{array}{c}1\\ 2\\ 4\end{array}\right).$>

第三步，递归确定任意时刻每个物体的位置

以第三个时刻点(τ＝4)为例，结合图1，给出具体的流程

1)在关联矩阵中加入时刻3以及时刻4的观察值和得到当前时刻可能轨迹集

从当前时刻可能轨迹集中可以得到现在有四个可能的轨迹：区域2‐区域3(记为2‐3)；2‐3；3‐3；3‐4.而总共只有三个物体，因此有一个轨迹是多余的，需要去掉。

2)去掉中多余轨迹.首先将变成行初等矩阵$>E_{4\times 4}^4=\left(\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right),$>其中，记录第一和第二种初等行变换过程的矩阵$>S=\left(\begin{array}{cccc}0& 0& 0.5& 0\\ 0& 0& 0& 1\\ 1& 0& 0& 0\\ 0& 1& 0& 0\end{array}\right).$>那么，当前时刻实际轨迹集

$>D_{4\times 4}^4=S^{-1}\times E_{4\times 4}^4=\left(\begin{array}{cccc}0& 0& 1& 0\\ 0& 0& 0& 1\\ 2& 0& 0& 0\\ 0& 1& 0& 0\end{array}\right)\times \left(\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right)=\left(\begin{array}{cccc}0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 2& 0& 0\\ 0& 0& 1& 0\end{array}\right).$>

3)由当前时刻实际轨迹集得到从可以得到里面有三条路径2‐3,；2‐3；3‐4，跟观察信息核对，是正确的，因此当前时刻的位置：$>P_{3\times 1}^4=\left(\begin{array}{c}3\\ 3\\ 4\end{array}\right).$>

第四步，轨迹串联得到

按照本发明的方法，将其他时刻的轨迹也都求解出来，并且串联起来，即可得到物体的最终轨迹：

$>\widehat{P_{3\times 5}}=\left(\begin{array}{ccccc}1& 1& 2& 3& 2\\ 2& 3& 2& 3& 2\\ 4& 4& 3& 4& 4\end{array}\right).$>

第五步，井字型多解判断

对于本实施例而言，这是一个单解问题，因此不会检测出井字型。

当$>M_{3\times 3}^{\tau }=\left(\begin{array}{ccc}1& 0& 1\\ 0& 0& 0\\ 1& 0& 1\end{array}\right),$>有三个摄像机，两个物体。可以发现，从时刻τ-1到时刻τ，可能的轨迹是区域1‐区域1(表示为1‐1)；1‐3；3‐1；3‐3.这些轨迹在矩阵中形成了井字型，从逻辑分析角度来说，这些轨迹都是可能的，不能判断哪个是多余的，因此得到的当前时刻实际轨迹集不是唯一的：$>D_{3\times 3}^{\tau \left(1\right)}=\left(\begin{array}{ccc}1& 0& 0\\ 0& 0& 0\\ 0& 0& 1\end{array}\right);D_{3\times 3}^{\tau \left(2\right)}=\left(\begin{array}{ccc}0& 0& 1\\ 0& 0& 0\\ 1& 0& 0\end{array}\right).$>这两种都是合理的，因此造成了多解；然后通过将所有可能解中元素中最接近于主对角线的结果作为运动物体轨迹，即是输出结果。

在另外的情况下，如以时刻τ＝4为例，$>M_{4\times 4}^3=\left(\begin{array}{cccc}0& 0& 0& 0\\ 1& 0& 1& 0\\ 0& 0& 1& 1\\ 0& 0& 0& 0\end{array}\right),$>观察其中的非零元素，并没有构成井字型，因此这个问题是唯一解的。

综上所述，本发明优点在于：1)采用矩阵操作，简化运算，极大地提高了运算速度。2)采用递归的运算结构，能够灵活应对新加入的时刻点的观察值，达到实时处理的效果。3)采用井字型多解判定，在计算运动轨迹的同时能够判断所解决问题的解的特性，从而能够判断得到的结果的正确性。