工程科学学报，第37卷，第2期：250-254,2015年2月 Chinese Journal of Engineering,Vol.37,No.2:250-254,February 2015 DOI:10.13374/j.issn2095-9389.2015.02.018:http://journals.ustb.edu.cn 基于最小费用流建模的目标跟踪器研究与仿真 奚峥皓12)四，赵宝永”，刘贺平”，刘涛”，孙富春) 1)北京科技大学自动化学院，北京1000832)清华大学智能技术与系统国家重点实验室，北京100084 ☒通信作者，E-mail:zhenghaoxi(@hotmail.com 摘要针对目标跟踪中的物体遮挡、光照影响、杂波扰动等问题，设计一种基于最小费用流建模的跟踪器.该跟踪器把整 数规划与最小费用流模型相结合，将目标跟踪问题转变为可解的线性规划问题.与其他同类型跟踪器相比，该跟踪器具有更 好的跟踪准确性.实验结果表明：运用最小费用流模型的跟踪器可以对复杂环境下的多个目标进行稳定跟踪，提升了跟踪的 鲁棒性 关键词目标跟踪：建模：线性规划：机器视觉 分类号TP391.9 Target tracker based on minimum cost flow modeling XI Zheng-hao,ZHAO Bao-yong",LIU Heping",LIU Tao,SUN Fu-chun 1)School ofAutomation and Electrical Engineering,University of Science and Technology Beijing,Beijing 100083,China 2)State Key Laboratory of Intelligent Technology and Systems,Tsinghua University,Beijing 100084,China Corresponding author,E-mail:zhenghaoxi@hotmail.com ABSTRACT A tracker using the method of minimum cost flow was designed to solve the problems of object occlusion,lighting effects and clutter disturbance.This tracker combines integer programming with the minimum cost flow model,and converts the prob- lem of object tracking into a linear programming problem.Compared with other similar trackers,this tracker has a better tracking accu- racy.Simulation results show that the tracker in this paper has strong robustness and better tracking stability in complex environments KEY WORDS target tracking:modeling:linear programming:computer vision 目标跟踪是计算机视觉领域备受关注的前沿方 标跟踪的效果. 向，其在人机交互、视频监控、交通智能管理等方面都 以往解决这些问题或是以相邻帧的行人检测结果 有广泛的应用网.典型的目标跟踪系统由一部静态 作为关联对象，采用数据关联的方法，如最近邻法田、 摄像机对其监控固定区域内的移动目标进行跟踪获 联合概率数据关联滤波法(joint probability data associ-- 得.因此，设计一个抗干扰且能稳定跟踪的跟踪器成 aiom,JPDA)回和基于神经网络的方法园：或是用滤波 为目标跟踪系统的一个重要环节.有效的跟踪器应可 器针对性地设计一个统计轨迹模型7.这两种解决 以解决以下几种问题回：(1)光照影响.不同天气、不 方法的缺陷在于前者不能克服跟踪过程中出现的短时 同时间下光照和阴影等因素会对目标检测结果产生影 误报和漏报，而后者推演最大后验概率的轨迹估计方 响。(2)物体遮挡.目标在跟踪的过程中难免会被一 法则为NP问题. 些障碍物遮挡，影响跟踪的持续性.(3)杂波扰动.如 最近，Jiang等可利用网络流的方法来求解多目 摄像机和树枝的摇动，扰动部分不应影响跟踪器对目 标跟踪问题，并在一定条件下获得了全局最优解： 收稿日期：2013-12-22 基金项目：国家自然科学基金资助项目(61372090)：国家重点基础研究发展计划资助项目(2012CB821206)：北京市自然科学基金资助项目 (4122037)
工程科学学报，第 37 卷，第 2 期: 250--254，2015 年 2 月 Chinese Journal of Engineering，Vol． 37，No． 2: 250--254，February 2015 DOI: 10． 13374 /j． issn2095--9389． 2015． 02． 018; http: / /journals． ustb． edu． cn 基于最小费用流建模的目标跟踪器研究与仿真 奚峥皓1，2) ，赵宝永1) ，刘贺平1) ，刘 涛1) ，孙富春2) 1) 北京科技大学自动化学院，北京 100083 2) 清华大学智能技术与系统国家重点实验室，北京 100084 通信作者，E-mail: zhenghaoxi@ hotmail． com 摘 要 针对目标跟踪中的物体遮挡、光照影响、杂波扰动等问题，设计一种基于最小费用流建模的跟踪器． 该跟踪器把整 数规划与最小费用流模型相结合，将目标跟踪问题转变为可解的线性规划问题． 与其他同类型跟踪器相比，该跟踪器具有更 好的跟踪准确性． 实验结果表明: 运用最小费用流模型的跟踪器可以对复杂环境下的多个目标进行稳定跟踪，提升了跟踪的 鲁棒性． 关键词 目标跟踪; 建模; 线性规划; 机器视觉 分类号 TP391. 9 Target tracker based on minimum cost flow modeling XI Zheng-hao1，2) ，ZHAO Bao-yong1) ，LIU He-ping1) ，LIU Tao1) ，SUN Fu-chun2) 1) School ofAutomation and Electrical Engineering，University of Science and Technology Beijing，Beijing 100083，China 2) State Key Laboratory of Intelligent Technology and Systems，Tsinghua University，Beijing 100084，China Corresponding author，E-mail: zhenghaoxi@ hotmail． com ABSTＲACT A tracker using the method of minimum cost flow was designed to solve the problems of object occlusion，lighting effects and clutter disturbance． This tracker combines integer programming with the minimum cost flow model，and converts the problem of object tracking into a linear programming problem． Compared with other similar trackers，this tracker has a better tracking accuracy． Simulation results show that the tracker in this paper has strong robustness and better tracking stability in complex environments． KEY WOＲDS target tracking; modeling; linear programming; computer vision 收稿日期: 2013--12--22 基金项目: 国家自然科学基金资助项目( 61372090) ; 国家重点基础研究发展计划资助项目( 2012CB821206) ; 北京市自然科学基金资助项目 ( 4122037) 目标跟踪是计算机视觉领域备受关注的前沿方 向，其在人机交互、视频监控、交通智能管理等方面都 有广泛的应用［1--2］． 典型的目标跟踪系统由一部静态 摄像机对其监控固定区域内的移动目标进行跟踪获 得． 因此，设计一个抗干扰且能稳定跟踪的跟踪器成 为目标跟踪系统的一个重要环节． 有效的跟踪器应可 以解决以下几种问题［3］: ( 1) 光照影响． 不同天气、不 同时间下光照和阴影等因素会对目标检测结果产生影 响． ( 2) 物体遮挡． 目标在跟踪的过程中难免会被一 些障碍物遮挡，影响跟踪的持续性． ( 3) 杂波扰动． 如 摄像机和树枝的摇动，扰动部分不应影响跟踪器对目 标跟踪的效果． 以往解决这些问题或是以相邻帧的行人检测结果 作为关联对象，采用数据关联的方法，如最近邻法［4］、 联合概率数据关联滤波法( joint probability data association，JPDA) ［5］和基于神经网络的方法［6］; 或是用滤波 器针对性地设计一个统计轨迹模型［7--8］． 这两种解决 方法的缺陷在于前者不能克服跟踪过程中出现的短时 误报和漏报，而后者推演最大后验概率的轨迹估计方 法则为 NP 问题． 最近，Jiang 等［9］利用网络流的方法来求解多目 标跟踪问题，并在一定条件下获得了全局最优解;
奚峥皓等：基于最小费用流建模的目标跟踪器研究与仿真 ·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 ·
·252· 工程科学学报，第37卷，第2期 即为可行的.记厂为该可行概率分布的集合.于是， 集Q二{1,2，…，m}可以分为两个子集Q和Q2,且 问题转为 Q=QUQ2,Q1nQ2=☑，并满足 m'arg maxP(E=mll). (6) j=1,2,…,n, 点1点 ge{-1,0,1. 若E是条件独立的，严给定，则等式(6)的最优 (19) 化问题可表述为 定理1若由0、±1组成的m×n约束矩阵A是 m`=arg maxlogΠf(Ea=d.Ir） (7) 全单模的，则由单纯形法求解线性规划可得原整数规 =ag呼Σloef(E=dI） (8) 划的最优解 证明：将A分成Q,和Q两个行子集，如图2 =agmΣ1-)lef(E.=01）+ 所示 ai logP(E=1r) (9) P(E:=1l) -argo (= (10) 0-···-1···-11···1···1 -i (11) 、 01.1。,·10。。 其中，由式(3)可知a为0或1，故式(9)成立.忽略 -1 一个不依赖于m的项，得式(10).式(11)的目标函数 即为a的线性表述. 2整数规划的线性化 图2约束矩阵的简要示意图 转化上述公式为整数规划： Fig.2 Sketch of the constraint matrix A of the LP Maximize Q,和Q2分别代表流的上限和流的守恒： (a)i (12) Q,{i≤l} (20) Subject to t,ijn9il≥0： (13) V,i,∑.、pi≤l: (14) (21) u ,i,∑pi≤∑p: (15) 是p-AmPi≤0. LEML) LLEV) 定义中为一个包含所有流值的向量，将非平凡约 足AnP≤0 (16) 束(13)~(16)以矩阵形式表示 转换后的公式与原问题表述相同.为了避免在某 电=4以l92p], 个非跟踪位置上的目标突然消失，流守恒需满足式 (16),且不等式不等显著.由式(12)~(16)，整数规 A重≤1，…，1,0，…，0] (22) 划可转换为线性规划求解，设边©吃4的流费用 设A、是由约束矩阵A中任意S行子集构成的子 c(e)为 矩阵，A。的每列最多有三个非零项.将行子集再分成 两个子集：一个满足S=Q,∩S,如非平凡约束(20)所 c(e=-log ( (17) 述；另一子集S2=Q2∩S对应于集合(21).对A,的每 列共有八种不同情况，如表1. 则目标跟踪轨迹（的全费用C,为 所有可能情况中，除1仅在S,且-1仅在S,（如 G=∑c(e). (18) 表1情况7)外，均满足引理的条件.对于这种情况，可 因为是单调递增的，所以当C.:≥C,≤C1时可 将S,包含非零项的行变换到S2,使列与所变换行中的 获得最优解，即此时的目标跟踪轨迹（接近目标的真 非零项相对应，即{入Ii∈S}是{0，…，0}，{入gIi∈S2} 实运动轨迹.用单纯形法迭代求解得到的最优解只有 为{0，…，0,1}或{0，…，0,1，-1}，亦可满足引理.因 在满足引理1时才收敛于原整数规划问题的最优解. 此约束矩阵A满足引理，且是全单模的 本文模型的约束矩阵可满足引理1. 事实上，单纯形法计算最优解是通过线性规划基 引理1令A是由0、±1组成的m×n矩阵， 本可行解的逐步迭代实现的，而约束矩阵A的全单模 那么矩阵A=,]。xn是全单模的，当且仅当A的行子 性则保证了在此过程中的每个基本可行解都是整数
工程科学学报，第 37 卷，第 2 期 即为可行的． 记 Γ 为该可行概率分布的集合． 于是， 问题转为 m* = arg max e∈Γ ^ P( E = m| I) ． ( 6) 若 Et，i是条件独立的，I t 给定，则等式( 6) 的最优 化问题可表述为 m* = arg max m∈Γ log ∏t，i ^ P( Et，i = αt lt，i | I t ) ( 7) = arg max m∈Γ∑t，i log ^ P( Et，i = αt lt，i | I t ) ( 8) = arg max m∈Γ∑t，i ( 1 － αt lt，i ) log ^ P( Et，i = 0 | I t ) + αt lt，i log ^ P( Et，i = 1 | I t ) ( 9) = arg max m∈Γ∑t，i αt lt，i log ^ P( Et，i = 1 | I t ) ^ P( Et，i = 0 | I t ) ( 10) = arg max m∈Γ∑t， ( i log ρ t t，i 1 － ρ t t， )i αt lt，i ． ( 11) 其中，由式( 3) 可知 αt lt，i 为 0 或 1，故式( 9) 成立． 忽略 一个不依赖于 m 的项，得式( 10) ． 式( 11) 的目标函数 即为 αt lt，i 的线性表述． 2 整数规划的线性化 转化上述公式为整数规划: Maximize ∑t，i ( log ρ t t，i 1 － ρ t t， )i lt+1， ∑j ∈N( lt，i ) φt lt，i ，lt + 1，j ． ( 12) Subject to t，i，j，φt lt，i ，lt + 1，j ≥0; ( 13) t，i， lt+1， ∑j ∈N( lt，i ) φt lt，i ，lt + 1，j ≤1; ( 14) t，i， lt+1， ∑j ∈N( lt，i ) φt lt，i ，lt + 1，j ≤ lt－1，k: l ∑t，i ∈N( lt－1，k) φt － 1 lt － 1，k，lt，i ; ( 15) j∈ ∑N( vsource) φvsource，j － k: v ∑sink∈N( k) φk，vsink ≤0． ( 16) 转换后的公式与原问题表述相同． 为了避免在某 个非跟踪位置上的目标突然消失，流守恒需满足式 ( 16) ，且不等式不等显著． 由式( 12) ～ ( 16) ，整数规 划可 转 换 为 线 性 规 划 求 解，设 边 e t lt，i ，lt + 1，j 的 流 费 用 c( e t lt，i ，lt + 1，j ) 为 c( e t lt，i ，lt + 1，j ) ( = － log ρ t t，i 1 － ρ t t， )i ， ( 17) 则目标跟踪轨迹 fl 的全费用 Cl 为 Cl = e ∑t lt，i ，lt+1，j ∈fl c( e t lt，i ，lt + 1，j ) ． ( 18) 因为 fl 是单调递增的，所以当 Cl － 1≥Cl≤Cl + 1时可 获得最优解，即此时的目标跟踪轨迹 fl 接近目标的真 实运动轨迹． 用单纯形法迭代求解得到的最优解只有 在满足引理 1 时才收敛于原整数规划问题的最优解． 本文模型的约束矩阵可满足引理 1． 引理 1 ［13］ 令 A 是由 0、± 1 组成的 m × n 矩阵， 那么矩阵 A =［λij］m × n是全单模的，当且仅当 A 的行子 集 Q{ 1，2，…，m} 可以分为两个子集 Q1 和 Q2，且 Q = Q1∪Q2，Q1∩Q2 = ，并满足 j = 1，2，…，n，∑i∈Q1 λij － ∑i∈Q2 λij∈{ － 1，0，1} ． ( 19) 定理 1 若由 0、± 1 组成的 m × n 约束矩阵 A 是 全单模的，则由单纯形法求解线性规划可得原整数规 划的最优解． 证明: 将 A 分 成 Q1 和 Q2 两 个 行 子 集，如 图 2 所示． 图 2 约束矩阵的简要示意图 Fig． 2 Sketch of the constraint matrix A of the LP Q1 和 Q2 分别代表流的上限和流的守恒: Q1 : t，i，{ lt+1， ∑j ∈N( lt，i ) φt lt，i ，lt + 1，j ≤1 } ， ( 20) Q2 : t，i，{ lt+1， ∑j ∈N( lt，i ) φt lt，i ，lt + 1，j － lt－1，k: l ∑t，i ∈N( lt－1，k) φt － 1 lt － 1，k，lt，i ≤0 } ， ( 21) j∈ ∑N( vsource) φvsource，j － k: v ∑sink∈N( k) φk，vsink ≤0． 定义 Φ 为一个包含所有流值的向量，将非平凡约 束( 13) ～ ( 16) 以矩阵形式表示 Φ =［φ1 l1，1，l2，1 ，φ2 l2，1，l3，1 ，…，φT － 1 lT － 1，K，lT，K ］T ， A·Φ≤［1，…，1，0，…，0］T ． ( 22) 设 AS 是由约束矩阵 A 中任意 S 行子集构成的子 矩阵，AS 的每列最多有三个非零项． 将行子集再分成 两个子集: 一个满足 S1 = Q1∩S，如非平凡约束( 20) 所 述; 另一子集 S2 = Q2∩S 对应于集合( 21) ． 对 AS 的每 列共有八种不同情况，如表 1． 所有可能情况中，除 1 仅在 S1 且 － 1 仅在 S2 ( 如 表 1 情况 7) 外，均满足引理的条件． 对于这种情况，可 将 S1 包含非零项的行变换到 S2，使列与所变换行中的 非零项相对应，即{ λij | i∈S1 } 是{ 0，…，0} ，{ λij | i∈S2 } 为{ 0，…，0，1} 或{ 0，…，0，1，－ 1} ，亦可满足引理． 因 此约束矩阵 A 满足引理，且是全单模的． 事实上，单纯形法计算最优解是通过线性规划基 本可行解的逐步迭代实现的，而约束矩阵 A 的全单模 性则保证了在此过程中的每个基本可行解都是整数 · 252 ·
奚峥皓等：基于最小费用流建模的目标跟踪器研究与仿真 ·253· 表1同一列的所有可能情况 Table 1 All possible cases for the same column 计算式 情况1 情况2 情况3 情况4 情况5 情况6 情况7 情况8 (AylieS} {0.…,0}{0,…,0} {0.…,0} {0,…,0} {0.….0.1}{0.…,0.1}{0.…,0.1} {0,…,0,1} (AglieS2} {0,…,0}{0,…,0,1}{0,…,0,-1}{0,…,0,1,-1}{0,…,0}{0,…,0,1} {0,…,0,-1}{0,…,0,1,-1} 点4点 0 =】 0 0 2 解，确保了松弛前后最优解的一致性.综上所述，定理 迹的运动框，则两框的交叉比率 成立，证毕 AREA(GT OTR,} C,=AREA (GT,UTR,) (23) 3实验仿真 本文取C,=0.5,即当t时刻的跟踪框与真实运动 3.1目标检测 框的面积叠加超过0.5时认为跟踪成功.典型跟踪帧 本文先用改进的背景差分法对目标定位，再用 如图4所示. 文献2]的方法计算目标在跟踪区域的概率分布，如 从第50帧开始，至第103帧目标4和5在遮挡 图3所示，将所得结果代入式(6)计算. 条件下转弯结束，本文跟踪器可以很好地对两目标 进行跟踪.同时，在第70帧，目标3从设定为敏感区 的视野左侧离开，至第83帧再次出现，目标仍被正 确跟踪.这表明本文设计的跟踪器能够很好地克服 由物体遮挡和杂波扰动带来的跟踪不稳定问题.与 Zhang和Jiang的算法做平均误差比较，结果如图5， 图3目标检测结果及概率分布 典型帧的平均误差比较如表2.对整个视频序列而 Fig.3 Object detection results and probability distribution 言，Zhang的平均误差为4.8个像素，Jiang的方法为 3.2仿真结果 4.2个像素，而采用本文模型的跟踪器则为3.2个像 本文在Windows系统下采用Visual Studio2010和 素.结合图5可得，当目标被遮挡频繁发生时，跟踪 Open CV2.2作为软件平台，Pentium(R)Dual-Core 所需信息出现缺漏，致跟踪误差较大：而基于本文模 CPU2.7GHz为硬件平台.用PETS09视频库验证本文 型的跟踪器由于找到全局最优解的缘故可以较好地 跟踪器的可靠性 克服这一问题，在增强跟踪稳定性的同时，提高了在 设TR,为1时刻的跟踪框，GT,为t时刻的真实轨 复杂环境下的跟踪鲁棒性 图4典型跟踪结果.(a)帧数26：(b)帧数44：(c)帧数50：(d)帧数57：(e)帧数73：(0帧数83：(g)帧数93：(h)帧数103 Fig.4 Tracking results:(a)Frame 26:(b)Frame 44:(c)Frame 50:(d)Frame 57:(e)Frame 73:(f)Frame 83:(g)Frame 93:(h)Frame 103
奚峥皓等: 基于最小费用流建模的目标跟踪器研究与仿真 表 1 同一列的所有可能情况 Table 1 All possible cases for the same column 计算式 情况 1 情况 2 情况 3 情况 4 情况 5 情况 6 情况 7 情况 8 { λij | i∈S1 } { 0，…，0} { 0，…，0} { 0，…，0} { 0，…，0} { 0，…，0，1} { 0，…，0，1} { 0，…，0，1} { 0，…，0，1} { λij | i∈S2 } { 0，…，0} { 0，…，0，1} { 0，…，0，－ 1} { 0，…，0，1，－ 1} { 0，…，0} { 0，…，0，1} { 0，…，0，－ 1} { 0，…，0，1，－ 1} i ∑∈Q1 λij － i ∑∈Q2 λij 0 － 1 1 0 1 0 2 1 解，确保了松弛前后最优解的一致性． 综上所述，定理 成立，证毕． 3 实验仿真 图 4 典型跟踪结果． ( a) 帧数 26; ( b) 帧数 44; ( c) 帧数 50; ( d) 帧数 57; ( e) 帧数 73; ( f) 帧数 83; ( g) 帧数 93; ( h) 帧数 103 Fig． 4 Tracking results: ( a) Frame 26; ( b) Frame 44; ( c) Frame 50; ( d) Frame 57; ( e) Frame 73; ( f) Frame 83; ( g) Frame 93; ( h) Frame 103 3. 1 目标检测 本文先用改进的背景差分法［14］对目标定位，再用 文献［12］的方法计算目标在跟踪区域的概率分布，如 图 3 所示，将所得结果代入式( 6) 计算． 图 3 目标检测结果及概率分布 Fig． 3 Object detection results and probability distribution 3. 2 仿真结果 本文在 Windows 系统下采用 Visual Studio 2010 和 Open CV2. 2 作 为 软 件 平 台，Pentium ( Ｒ) Dual-Core CPU 2. 7 GHz 为硬件平台． 用 PETS09 视频库验证本文 跟踪器的可靠性． 设 TＲt 为 t 时刻的跟踪框，GTt 为 t 时刻的真实轨 迹的运动框，则两框的交叉比率 Ct = AＲEA{ GTt∩TＲt} AＲEA{ GTt∪TＲt} ． ( 23) 本文取 Ct = 0. 5，即当 t 时刻的跟踪框与真实运动 框的面积叠加超过 0. 5 时认为跟踪成功． 典型跟踪帧 如图 4 所示． 从第 50 帧开始，至第 103 帧目标 4 和 5 在遮挡 条件下转弯结束，本文跟踪器可以很好地对两目标 进行跟踪． 同时，在第 70 帧，目标 3 从设定为敏感区 的视野左侧离开，至第 83 帧再次出现，目标仍被正 确跟踪． 这表明本文设计的跟踪器能够很好地克服 由物体遮挡和杂波扰动带来的跟踪不稳定问题． 与 Zhang 和 Jiang 的算法做平均误差比较，结果如图 5， 典型帧的平均误差比较如表 2． 对整个视频序列而 言，Zhang 的平均误差为 4. 8 个像素，Jiang 的方法为 4. 2 个像素，而采用本文模型的跟踪器则为 3. 2 个像 素． 结合图 5 可得，当目标被遮挡频繁发生时，跟踪 所需信息出现缺漏，致跟踪误差较大; 而基于本文模 型的跟踪器由于找到全局最优解的缘故可以较好地 克服这一问题，在增强跟踪稳定性的同时，提高了在 复杂环境下的跟踪鲁棒性． · 352 ·
·254· 工程科学学报，第37卷，第2期 表2典型帧的平均跟踪误差比较 Jiang M X,Wang H Y,Liu X K.A multi-target tracking algo- Table2 The comparison of average tracking erors of typical frames rithm based on multiple cameras.Acta Autom Sin,2012,38(4): pixels 531 典型帧 100200300400500600700 (姜明新，王洪玉，刘晓凯.基于多相机的多目标跟踪算法 自动化学报，2012,38(4)：531) Zhang的方法9.72.10.3000.55.4 B3]Xu H X,Wang Y N,Yuan X F,et al.A hierarchical mean shift Jiang的方法 4.75.210.5113.6 algorithm for object tracking.Acta Autom Sin,2009,35(4):401 本文方法 3.61.2 0 000.21.6 (许海霞，王耀南，袁小芳，等.一种分层Mean Shift目标跟 踪算法.自动化学报，2009,35(4)：401) 30 4]Zhou H R.A survey of multiple targets tracking technique.Acta Aeronaut Astronaut Sin,1986,7(1):1 2 一Zang的方法 (周宏仁.多目标跟踪技术综述.航空学报，1986,7(1)：1) 一Jiang的方法 20 本文方法 5]Yu Q,Medioni G.Multiple-arget tracking by spatiotemporal Monte Carlo Markov chain data association.IEEE Trans Pattern A- nal Mach Intell,2009,31(12):2196 6]Serratosa F,Alquezar R,Amezquita N.A probabilistic integrated object recognition and tracking framework.Expert Syst Appl, 2012,39(8):7302 400 500 [7]Maggio E,Taj M,Cavallaro A.Efficient multi-arget visual track- 时间帧 ing using random finite sets.IEEE Trans Circuits Syst Video Tech- 图5平均误差对比 nol,2008,18(8):1016 Fig.5 Comparison of average tracking errors 8] Sharp I,Yu K.Sathyan T.Positional accuracy measurement and error modeling for mobile tracking.IEEE Trans Mobile Comput, 4结论 2012,11(6),1021 ] Jiang H,Fels S,Little JJ.A linear programming approach for (1)针对由遮挡、杂波扰动和光照变换带来的跟 multiple object tracking /Proceedings of Conference on Computer 踪不稳定问题，设计了一种新型基于网络流模型的跟 Vision and Pattern Recognition.Minneapolis,2007:744 踪器。模型应用整数规划理论与最小费用流算法相结 [10]Zhang L,Li Y,Nevatia R.Global data association for multi-ob- 合的信息素获取方式，将流费用的变化与目标移动进 ject tracking using network flows /Proceeding of 26th IEEE Conference on Computer Vision and Pattern Recognition.Anchor- 行合理关联 age,2008:342 (2)针对本文所提模型的可行性给出理论支持， [11]Cook W J,Cunningham W H,Pulleyblank W R,et al.Combi- 证明了应用于本文跟踪器的整数规划模型在线性松弛 natorial Optimization.Beijing:Higher Education Press,2011 后可获得原整数假设的全局最优解 (Cook W J,Cunningham W H,Pulleyblank W R,等.组合优 (3)将本文提出的基于最小费用流建模的目标跟 化.北京：高等教有出版社，2011) 02] 踪器应用于PETS09视频库中进行验证，与近期相关 Bugeau A,Perez P.Track and cut:simultaneous tracking and segmentation of multiple objects with graph cuts.EURASIP JIm- 方法相比，在保证跟踪结果的同时，本文方法可大大减 age Video Process,2008:317278 少平均跟踪误差：在同一规划时间尺度下，本文设计的 13] Bertsekas D P.Conrex Optimisation Theory.Beijing:Tsinghua 跟踪器可求得精度稍高的解 University Press,2011 (Bertsekas D P.凸优化理论.北京：清华大学出版社，2011) 参考文献 [14]Maddalena L,Petrosino A.Stopped object detection by learning [Kim I S,Choi HS,Yi K M,et al.Intelligent visual surveillance: foreground model in videos.IEEE Trans Neural Netuorks Learn a survey.Int J Control Autom Syst,2010.8(5)926 Sst,2013,24(5):723
工程科学学报，第 37 卷，第 2 期 表 2 典型帧的平均跟踪误差比较 Table 2 The comparison of average tracking errors of typical frames pixels 典型帧 100 200 300 400 500 600 700 Zhang 的方法 9. 7 2. 1 0. 3 0 0 0. 5 5. 4 Jiang 的方法 4. 7 5. 2 1 0. 5 1 1 3. 6 本文方法 3. 6 1. 2 0 0 0 0. 2 1. 6 图 5 平均误差对比 Fig． 5 Comparison of average tracking errors 4 结论 ( 1) 针对由遮挡、杂波扰动和光照变换带来的跟 踪不稳定问题，设计了一种新型基于网络流模型的跟 踪器． 模型应用整数规划理论与最小费用流算法相结 合的信息素获取方式，将流费用的变化与目标移动进 行合理关联． ( 2) 针对本文所提模型的可行性给出理论支持， 证明了应用于本文跟踪器的整数规划模型在线性松弛 后可获得原整数假设的全局最优解． ( 3) 将本文提出的基于最小费用流建模的目标跟 踪器应用于 PETS09 视频库中进行验证，与近期相关 方法相比，在保证跟踪结果的同时，本文方法可大大减 少平均跟踪误差; 在同一规划时间尺度下，本文设计的 跟踪器可求得精度稍高的解． 参 考 文 献 ［1］ Kim I S，Choi H S，Yi K M，et al． Intelligent visual surveillance: a survey． Int J Control Autom Syst，2010，8( 5) : 926 ［2］ Jiang M X，Wang H Y，Liu X K． A multi-target tracking algorithm based on multiple cameras． Acta Autom Sin，2012，38( 4) : 531 ( 姜明新，王洪玉，刘晓凯． 基于多相机的多目标跟踪算法． 自动化学报，2012，38( 4) : 531) ［3］ Xu H X，Wang Y N，Yuan X F，et al． A hierarchical mean shift algorithm for object tracking． Acta Autom Sin，2009，35( 4) : 401 ( 许海霞，王耀南，袁小芳，等． 一种分层 Mean Shift 目标跟 踪算法． 自动化学报，2009，35( 4) : 401) ［4］ Zhou H Ｒ． A survey of multiple targets tracking technique． Acta Aeronaut Astronaut Sin，1986，7( 1) : 1 ( 周宏仁． 多目标跟踪技术综述． 航空学报，1986，7( 1) : 1) ［5］ Yu Q，Medioni G． Multiple-target tracking by spatiotemporal Monte Carlo Markov chain data association． IEEE Trans Pattern Anal Mach Intell，2009，31( 12) : 2196 ［6］ Serratosa F，Alquezar Ｒ，Amezquita N． A probabilistic integrated object recognition and tracking framework． Expert Syst Appl， 2012，39( 8) : 7302 ［7］ Maggio E，Taj M，Cavallaro A． Efficient multi-target visual tracking using random finite sets． IEEE Trans Circuits Syst Video Technol，2008，18( 8) : 1016 ［8］ Sharp I，Yu K，Sathyan T． Positional accuracy measurement and error modeling for mobile tracking． IEEE Trans Mobile Comput， 2012，11( 6) ，1021 ［9］ Jiang H，Fels S，Little J J． A linear programming approach for multiple object tracking / / Proceedings of Conference on Computer Vision and Pattern Ｒecognition． Minneapolis，2007: 744 ［10］ Zhang L，Li Y，Nevatia Ｒ． Global data association for multi-object tracking using network flows / / Proceeding of 26th IEEE Conference on Computer Vision and Pattern Ｒecognition． Anchorage，2008: 342 ［11］ Cook W J，Cunningham W H，Pulleyblank W Ｒ，et al． Combinatorial Optimization． Beijing: Higher Education Press，2011 ( Cook W J，Cunningham W H，Pulleyblank W Ｒ，等． 组合优 化． 北京: 高等教育出版社，2011) ［12］ Bugeau A，Perez P． Track and cut: simultaneous tracking and segmentation of multiple objects with graph cuts． EUＲASIP J Image Video Process，2008: 317278 ［13］ Bertsekas D P． Convex Optimization Theory． Beijing: Tsinghua University Press，2011 ( Bertsekas D P． 凸优化理论． 北京: 清华大学出版社，2011) ［14］ Maddalena L，Petrosino A． Stopped object detection by learning foreground model in videos． IEEE Trans Neural Networks Learn Syst，2013，24( 5) : 723 · 452 ·