奚峥皓等：基于最小费用流建模的目标跟踪器研究与仿真 ·251· 但此方法需要提前设定拟跟踪的目标数量，这使得 棒性，提高了跟踪质量 跟踪器在面向不确定数量的目标进行跟踪时易产 生轨迹互扰，导致跟踪失败.Zhang等@构建出一 1最小费用流建模 个较理想的网络流模型：这虽然解决了Jiang的目 目标跟踪的过程可以视作目标在每帧中的位置随 标数量限制问题，但由于这种复杂模型并不能找到 着时间推进而不断进行离散变化的过程.用三维有向 全局最优解，使其多目标跟踪结果拥有较大的平均 图来描述该过程，如图1所示，三个坐标轴分别表示时 跟踪误差. 间、单帧图像以及单帧图像中允许目标跟踪的区域 本文以Zhang和Jiang等提出的最小费用流模型 其中，时间轴由离散的T(1,2,…,t-1,,1+1,…,T) 为蓝本，设计出一个能适应杂波扰动，克服光照影响， 个时间帧组成，每个时间帧对应一个单帧图像，将单帧 在遮挡环境下有较强鲁棒性的跟踪器模型.与Zhang 图像中允许目标跟踪的区域离散成K(1,2,…,k-1, 和Jiang的方法相比，本文模型更形象地描述了多目标 k,k+1,,K)个小区域.对任意的k,用N(k)C{1, 的运动过程，并从理论上证明了获取全局最优解的可 2,…,K}表示k的邻域，其物理意义表示当目标在时 行性.实验结果表明，在遮挡和杂波扰动的环境下，该 间：所处位置k时，(k)即为该目标在t+1时的可到 模型大幅降低了多目标平均跟踪误差，具有较强的鲁 位置 0 1-1 ',fe 。跟踪区域中目标 目标在相邻帧中 ●月标在当前 香引入的源节 可能出现的位置 当前位置的邻域 顿的邻域 点和汇节点 图1三维流模型示意图 Fig.I 3D grid flow model 记：为目标在t时的位置i,则当且仅当l,∈ 跟踪的目标可能会在任意允许的区域内进出，流 N(l)时，可用e表示从l.到l,的边，其方向为 也同样.模型引入源节点和汇节点来解决这一问题， 目标随时间变化的运动情况：若目标静止，则 分别用v和，m表示.将两节点与该区域中代表敏 利用网络优化中的网络流概念四，定义有向图中 感位置的节点相连，例如门或摄像机视野的边缘等. 的流：令a表示目标在l的数量；非负变量p表 如图1所示，在从vm产生至第一帧所有可能节 示从活动到l,1的目标数，若p满足诚’ 点流的同时，最后一帧也产生相应的流至·为确保 A=dLAw元L0 所有出自v的流都会到D,补充约束条件： Vt,j, 刀 pi= 则称为该模型中的一个流。由于在有向图中活 Lem) ∑、pih (4) LIEN(L) 动的目标数均为非负，故模型中的流皆为可行流. 用随机变量E表示在l:处的目标，P为某处的 kj,l,pi≥0. (2) 估计概率，将检测器对视频中【时刻跟踪区域的所有 根据式(1)，在任意位置l的进出流总量保持“流 位置进行逐一检测，计算目标在位置↓：存在的后验边 守恒”.对从【至1+1时刻静止的目标，其流可表示为 缘概率估计值p,如式(5)，其中1为t时刻的单帧 图像 9=1.对多目标而言，还需满足在同一时刻不能 在相同位置出现，故设定在任意位置的总输出流上限 pii=P(E=1) (5) 设m为通过检测算法☒得到的目标概率分布，即 为1. 在每帧的每个位置上得到概率分布变量α的集合 Vk,l,∑.pil≤1. (3) 若m中存在一组能满足式(1)~(3)的流9，则m奚峥皓等: 基于最小费用流建模的目标跟踪器研究与仿真 但此方法需要提前设定拟跟踪的目标数量，这使得 跟踪器在面向不确定数量的目标进行跟踪时易产 生轨迹互扰，导 致 跟 踪 失 败． Zhang 等［10］构 建出 一 个较理想的 网 络 流 模 型; 这 虽 然 解 决 了 Jiang 的 目 标数量限制问题，但由于这种复杂模型并不能找到 全局最优解，使其多目标跟踪结果拥有较大的平均 跟踪误差． 本文以 Zhang 和 Jiang 等提出的最小费用流模型 为蓝本，设计出一个能适应杂波扰动，克服光照影响， 在遮挡环境下有较强鲁棒性的跟踪器模型． 与 Zhang 和 Jiang 的方法相比，本文模型更形象地描述了多目标 的运动过程，并从理论上证明了获取全局最优解的可 行性． 实验结果表明，在遮挡和杂波扰动的环境下，该 模型大幅降低了多目标平均跟踪误差，具有较强的鲁 棒性，提高了跟踪质量． 1 最小费用流建模 目标跟踪的过程可以视作目标在每帧中的位置随 着时间推进而不断进行离散变化的过程． 用三维有向 图来描述该过程，如图 1 所示，三个坐标轴分别表示时 间、单帧图像以及单帧图像中允许目标跟踪的区域． 其中，时间轴由离散的 T( 1，2，…，t － 1，t，t + 1，…，T) 个时间帧组成，每个时间帧对应一个单帧图像，将单帧 图像中允许目标跟踪的区域离散成 K( 1，2，…，k － 1， k，k + 1，…，K) 个小区域． 对任意的 k，用 N( k) { 1， 2，…，K} 表示 k 的邻域，其物理意义表示当目标在时 间 t 所处位置 k 时，N( k) 即为该目标在 t + 1 时的可到 位置． 图 1 三维流模型示意图 Fig． 1 3D grid flow model 记 lt，i为目标在 t 时的位置 i，则当且仅当 lt + 1，j ∈ N( lt，i ) 时，可用 e t lt，i ，lt + 1，j 表示从 lt，i到 lt + 1，j的边，其方向为 目标随时间变化的运动情况; 若目标静止，则 e t lt，i ，lt + 1，i ． 利用网络优化中的网络流概念［11］，定义有向图中 的流: 令 αt lt，i 表示目标在 lt，i的数量; 非负变量 φt lt，i ，lt + 1，j 表 示从 lt，i活动到 lt + 1，j的目标数，若 φt lt，i ，lt + 1，j 满足 vsink， t，j， lt－1，i : l ∑t，j ∈N( lt－1，i ) φt － 1 lt － 1，i ，lt，j = αt lt，j = lt+1， ∑k∈N( lt，j ) φt lt，j ，lt + 1，k ，( 1) 则称 φt lt，i ，lt + 1，j 为该模型中的一个流． 由于在有向图中活 动的目标数均为非负，故模型中的流皆为可行流． k，j，t，φt lt，k，lt + 1，j ≥0． ( 2) 根据式( 1) ，在任意位置 lt，j的进出流总量保持“流 守恒”． 对从 t 至 t + 1 时刻静止的目标，其流可表示为 φt lt，i ，lt + 1，i = 1． 对多目标而言，还需满足在同一时刻不能 在相同位置出现，故设定在任意位置的总输出流上限 为 1． k，t， lt+1， ∑j ∈N( lt，k) φt lt，k，lt + 1，j ≤1． ( 3) 跟踪的目标可能会在任意允许的区域内进出，流 也同样． 模型引入源节点和汇节点来解决这一问题， 分别用 vsource和 vsink表示． 将两节点与该区域中代表敏 感位置的节点相连，例如门或摄像机视野的边缘等． 如图 1 所示，在从 vsource产生至第一帧所有可能节 点流的同时，最后一帧也产生相应的流至 vsink ． 为确保 所有出自 vsource的流都会到 vsink，补充约束条件: lt+1，j ∈ ∑N( lt，vsource ) φt lt，vsource ，lt + 1，j = lt，k: lt+ ∑1，vsink ∈N( lt，k) φt lt，k，lt + 1，vsink ． ( 4) 用随机变量 Et，i 表示在 lt，i 处的目标，^ P 为某处的 估计概率，将检测器对视频中 t 时刻跟踪区域的所有 位置进行逐一检测，计算目标在位置 lt，i存在的后验边 缘概率估计值 ρ t t，i，如式( 5) ，其中 I t 为 t 时刻的单帧 图像． ρ t t，i = ^ P( Et，i = 1 | I t ) ． ( 5) 设 m 为通过检测算法［12］得到的目标概率分布，即 在每帧的每个位置上得到概率分布变量 αt lt，j 的集合． 若 m 中存在一组能满足式( 1) ～ ( 3) 的流 φt lt，k，lt + 1，j ，则 m · 152 ·