粒子流

基于视频粒子流和FTLE场的人群运动分割算法

文章编号:1001-9081(2012)01-0252-04

doi:10.3724/sp.j.1087.2012.00252

摘要:针对复杂视频监控场景中不同运动行为的人群分割，提出

了将视频粒子流和有限时间李雅普诺夫指数（ftle）场相结合的人

群运动分割算法。首先利用视频粒子流来表示长周期的粒子运动估

计，通过最小化包含粒子外观匹配一致性和粒子间形变的能量函

数，来优化每个粒子的轨迹；接着求解粒子流图的空间梯度，并构

造ftle场；最后利用ftle场中的拉格朗日相干结构把流图分割成

运动特性不同的区域。实验结构表明，算法能从拥挤复杂的视频监

控场景中有效地分割出不同运动特性的群体，且具有较好的鲁棒

性。

关键词:视频粒子；粒子流；李雅普诺夫指数；运动分割；拉

格朗日相干结构

中图分类号:tp391.413文献标志码:a



abstract:togmentmovingcrowdwithdifferentdynamics

incomplexvideosurveillancescenes,thispaperpropoda

crowdmotiongmentationalgorithmwhichwasbadonvideo

particleflowandfinitetimelyapunovexponent(ftle)field.

firstly,videoparticleflowwasudtoreprentthe

mizethe

particlestrajectories,anenergyfunctioncontaining

point-badappearancematchinganddistortionbetweenthe

espatialgradientofthe

particleflowmapwassolvedandtheftlefieldwas

y,thelagrangiancoherentstructure(lcs)

intheftlefieldwasudtodivideflowintoregionsof

erimentalresults

showthatthepropodalgorithmcaneffectivelygment

crowdflowwithdifferentdynamicsincomplexvideo

surveillancescenes,andithasstrongrobustness.

keywords:videoparticle;particleflow;lyapunov

exponent;motiongmentation;lagrangiancoherentstructure

(lcs)

0引言

大型集会（如宗教朝圣、游行、音乐会、足球比赛等）中的人群

管理［1］，是公共安全管理领域中最亟待解决的问题。通常这些集

会涉及到人群在有限的空间内运动，如城市街道、高架桥或者是狭

窄的通道，因而易于造成人群踩踏、四散堵塞事故发生。为了减少

在这些大型集会中灾难性事故的发生，智能视频人群监控技术已广

泛地应用到各种监控领域如城市街道、地铁站、商场等。其中对监

控场景中运动目标的分割一直是图像处理和计算机视觉领域的重

要研究课题。

目前大多数运动分割算法，仅限于视频序列中含有少数的目标个

体的分割与跟踪。如文献［2-3］提出的算法针对的是涉及低密度

人群的目标检测与分割；tu等［4］提出的人群分割同样不能处理

异常拥挤的人群运动。

近年来，为了解决高密度场景下的分割和检测问题，计算机视觉

研究人员已提出了不少涉及高密度人群下的人流分割与目标检测

的算法。如一些方法使用基于个体形状和颜色模型［5］、边界轮廓

［6］、特征点轨迹［7］等运动表示方法去检测与分类复杂场景下

的运动目标；chan等［8］提出了使用基于动态纹理表示法分割拥

挤场景的视频运动。与上述方法不同，ali等［9］把动态人群视为

一个整体，而不是着眼于分析其中的每个个体，然后利用有限时间

李雅普诺夫指数（finitetimelyapunovexponent,ftle）场中

的拉格朗日相干结构(lagrangiancoherentstructure,lcs)把流

场分割成运动特性不同的几个区域。该分割算法能有效地检测出流

体的动态特性变化，且具有鲁棒性的特点。

对于上述这些方法，通常采用密集光流或者特征点跟踪来得到粒

子的运动轨迹。然而光流只适用于连续两帧之间的运动估计，在长

时间序列（多帧）之间存在漂移问题。视频粒子流算法［10］能有

效地克服帧与帧之间的漂移，准确地得到长时间周期的粒子轨迹。

针对以上分析，本文提出了一种基于视频粒子流和ftle场的人群

运动分割算法。该算法首先使用视频粒子流算法来求解视频中粒子

的运动轨迹。它结合了特征点轨迹的粒子自适应性，同时克服了光

流的短周期性；接着运用ftle场中的拉格朗日相干结构分割运动

特性不同的人群。

1视频粒子原理

一个视频粒子是一个视频及其中相应的粒子集，任一粒子i具

有一个随时间变化的位置(xi(t),yi(t))，为了准确地得到

长时间周期的粒子轨迹，在对粒子扩散的同时，进行粒子联接和优

化等过程，如图1所示。

1.1粒子扩散

粒子通过光流场从相邻帧中扩散到给定帧中，粒子i从第t－1

帧扩散第t帧可表示为：

xi=xi(t－1)+u(xi(t－1),yi(t－1),t－1)

yi=yi(t－1)+v(xi(t－1),yi(t－1),t－1)（1）



1.2粒子联接

为了量化粒子相对运动，本文采用约束delaunay三角形

［11］来创建粒子间的联接（也可简化联接每个粒子与其最近的同

一方向的n个邻域粒子）。当粒子扩散时，粒子联接不断地消失与

更新，可以减少时间上的变异性。对于t帧上粒子i和j之间的联

接，可以计算平均运动方差来得到：

d(i,j)=1|t|∑t∈t(ui(t)－uj(t))2+(vi(t)－v

j(t))2（2）

其中：ui(t)=xi(t)－xi(t－1)，vi(t)=yi(t)－

yi(t－1)。为了增加联接鲁棒性采用文献［10］提出的零均值

高斯先验参数（ζl=1.5）计算联接权重值：

lij=n(d(i,j);ζl)（3）

1.3粒子优化

粒子视频算法的核心是粒子优化过程，如图1所示指代哪个图，

请明确。，优化过程就是在粒子扩散后对粒子位置的重新修正，从

而减少长时间段扩散带来的漂移问题。优化过程的实质就是最小化

一个目标函数，该目标函数包含数据项和变形项。第t帧粒子i的

能量为：

e(i,t)=∑k∈ki(t)e［k］data(i,t)+α∑

j∈li(t)edistort(i,j,t)（4）

其中：ki(t)表示图像的通道；li(t)表示在帧t时刻与粒

子i相联接的所有粒子。通过对edata(i,t)和e

distort(i,j,t)两部分权重取舍，在权值因子α=1.5最能

合理优化粒子过程。

1.3.1数据能量

数据项用来衡量粒子在视频扩散时的外观匹配，对于粒子i在

时刻t，第k个图像通道的数据项为：

e［k］data(i,t)=ψ(［i［k］(xi(t),yi(t),t)

－c［k］i］2)（5）

其中ψ是鲁棒项，ψ(s2)=s2+ε2,ε=0.001。

1.3.2形变能量

数据项并不能唯一约束粒子轨迹，形变项衡量粒子间的相对运

动。如果两个联接的粒子朝着不同的方向运动，它们会有一个较大

的形变项；反之如果它们朝向同一个方向运动，则该值就很小。形

变能量表示为：

edistort(i,j,t)=lijψ(［ui(t)－u

j(t)］2+［vi(t)－vj(t)］2)（6）

其中：ui(t)=xi(t)－xi(t－1)，vi(t)=yi(t)－

yi(t－1)。

1.3.3优化算法

粒子轨迹的优化过程与brox等［12］求解光流方法类似，对稀

疏线性系统进行两个嵌套循环，外层循环使用内层循环得到的d

xi(t)和dyi(t)来更新xi(t)和yi(t)。根据

变分计算，方程（4）必需满足欧拉拉格朗日方程：

{edxi(t)=0,edyi(t)=0|i∈p,t=f}

（7）

对于数据项，根据文献［12］的线性化方式，得到：

e［k］data(i,t)dxi(t)≈2ψ′(［i

［k］z］2)i［k］zi［k］x（8）这个公式中没有iy[k]

吗？请明确。

i［k］z=i［k］xdxi(t)+i［k］ydy

i(t)+i［k］－c［k］i（9）

同理，变形项的x偏导为：

edistort(i,j,t)dxi(t)=2lij

(t)ψ′(［ui(t)+dui(t)－uj(t)－du

j(t)］2+［ui(t)+dui(t)－uj(t)－du

j(t)］2(ui(t)+dui(t)－uj(t)－du

j(t))（10）

其中：dui(t)=dxi(t)－dxi(t－1)

和dvi(t)=dyi(t)－dyi(t－1)。

2基于视频粒子流和ftle场的人群运动分割

2.1算法流程

本文研究的基于视频粒子流和ftle场的人群分割算法流程如图2

所示。

2.2视频粒子流图

根据流程图，首先利用brox光流算法求得相邻两帧之间的光流场，

然后利用视频粒子流算法得到长周期的粒子运动轨迹。

给定一个定义在d上的时间相关速度场v(x,t)，在时刻t0

位置x0处开始的一条轨迹x(t:t0,x0)是：

(t;t0,x0)=v(x(t;t0,x0),t)；x(t0;t0,x

0)=x0（11）

方程(11)描述的动态系统的解可以视为一幅图，从在时刻t0

位置x0处开始取值到时刻t，称之为流图，用φtt

0表示，满足φtt0(x0)=x(t;t0,x0)。

一对标记为φx和φy的流图，维持了每个时刻的粒子的轨迹:

φx记录了粒子x坐标上的变化轨迹，同样φy记录了y坐标

上的轨迹。

2.3ftle场

2.3.1有限时间lyapunov指数场

有限时间指数依赖于轨迹的初始位置和整合轨迹的长度，有限时

间指数依赖于轨迹的初始位置和整合轨迹的长度，是用于衡量无限

接近的粒子间分离性的量。当在粒子上使用有限时间lyapunov指

数，它产生了一个ftle场，它反映了流体的特性。

2.3.2ftle场计算

ftle场是从上述流图中计算而来的，首先计算φx和φ

y的梯度dφxdx,dφxdy,d

φydx,dφydy，然后利用空间梯度求解柯

西形变张量：

δ=dφt0+tt0(x)dx*d

φt0+tt0(x)dx（12）

在有限时间t内，ftle最大值为：

ζtt0=1tlnλmax(δ)（13）



ftle场是一个标量场，它反映了流体的特性。当相邻粒子以不同

运动特性运动时，会导致ftle场中出现突出的“脊”的结构。这

种结构称为拉格朗日相干结构（lcs）。利用lcs可以分割不同运动

特性的流，从而捕捉了潜在流场的动态力学和几何学特性。分割过

程包括两步骤：首先是给定ftle场的过分割；然后融合那些边界

粒子在lyapunov意义上具有相似行为的部分。

3实验结果与分析

本实验用来测试的视频数据来自图片库和谷歌视频中那些包含高

密度人群或者高密集交通的场景。

给定一个视频或者图像序列求解其光流场。为了防止噪声和光照

变化等带来的干扰，本文采用brox方法求解光流。如图3为来自

繁忙交通场景视频的连续两帧图片，大小为188×144。图4

则是来自ucf视频数据库中集市人群的流动图，大小为480×360。

图4（a）、（b）与图5（a）、（b）分别是相应图像序列中的相邻两

帧。

运用视频粒子算法求粒子轨迹，得到粒子流图。实验中，粒子网

格的分辨率与流场的像素个数保持相同。图5(b)、(d)分别为图

5(a)、(c)在时间周期t为5的粒子流图。

通过式（13）计算ftle场。图6~7给出了人群分割的两个实验结

果。第一排为原始视频序列：图6(a)为麦加人流视频，数千人围绕

卡巴逆时针方向运动；图7(a)为集市复杂人流视频，场景中的人群

往不同方向运动。第二排图6(b)、(c)和图7(b)、(c)为相应视频

序列的ftle场，流场中的脊（即lcs）突显了脊两侧不同的运动特

性。其中左侧是根据文献［8］求解粒子流图得到的。右侧的ftle

场是应用本文的基于视频粒子流和ftle场人群分割算法得到的。

图6(d)、(e)和图7(d)、(e)为通过分水岭分割算法后得到的相应

流场分割图。实验结果表明，采用本文算法得到的ftle更为准确，

对拥挤场景下的人群分割效果更佳。

4结语

本文提出了一种基于视频粒子流和ftle场的动态人群分割方法。

粒子轨迹是图像采样点在一段时间内的位移位置。为了更加准确地

得到长时间周期的粒子轨迹，本文使用视频粒子算法来得到视频中

粒子的运动轨迹。该算法结合了特征点轨迹的粒子自适应性，同时

克服了光流的短周期性，对于遮挡、和光照变化更具有鲁棒性。在

此基础上，利用混沌力学中拉格朗日表示法，求解ftle场，对运

动区域实现初分割，最后用分水岭算法获得人流区域分割。实验证

实了该算法能有效分割拥挤场景下的人群运动。在今后的工作中，

将进一步结合其他分割算法，并把算法推广到更密集、更宽广的公

共场所监控视频中。

参考文献:

[1]

mehranr,moorebe,klinereprentationof

flowincrowdedscenes［c］//proceedingsofthe11theuropean

:springer-verlag,2010:

439-452.

[2]

nguyenht,jiq,-temporalcontext

forrobustmultitargettracking［j］.ieeetransactionson

patternanalysisandmachineintelligence,2007,29(1):52-64.

[3]

kumarmp,torrphs,nglayeredmotion

gmentationsofvideo［j］.internationaljournalof

computervision,2008,76(3):301-319.

[4]

tup,bastiant,dorettog,dcrowd

gmen-tation［c］//proceedingsofthe10theuropean

:springer-verlag,2008:

691-704.

[5]

zhaot,anhumangmentationincrowded

situations［c］//ieeecomputersocietyconferenceon

gton,dc:ieee

computersociety,2003:459-466.

[6]

tup,egmentationthroughemergent

labeling［c］//europeanconferenceoncomputervision

:

springer-verlag,2004:187-198.

[7]

brostowgj,cipollar.unsupervidbayesian

detectionofindependentmotionincrowds［c］//ieeecomputer

societyconferenceoncomputervisionandpatternrecognition.

washington,dc:ieeecomputersociety,2006:594-601.

[8]

chanab,vasconcelosn.mixturesofdynamic

textures［c］//proceedingsofthetenthieeeinternational

gton,dc:ieeecomputer

society,2005:641-647.

[9]

alis,shahm.alagrangianparticledynamics

approachforcrowdflowgmentationandstabilityanalysis

［c］//ieeecomputersocietyconferenceoncomputervision

gton,dc:ieeecomputer

society,2007:1-6.

[10]

sandp,levideo:long-rangemotion

estimationusingpointtrajectories［c］//ieeecomputer

societyconferenceoncomputervisionandpatternrecognition.

washington,dc:ieeecomputersociety,2006:2195-2202.

[11]

rincrementaldelaunaytriangulation

［m］//:academicpress,

1994.

[12]

broxt,bruhna,papenbergn,curacyoptical

flowestimationbadonatheoryforwarping［c］//european

:springer-verlag,2004:

25-36.

收稿日期:2011-06-30;修回日期:2011-08-12。

基金项目:

浙江省自然科学基金资助项目（y1110506）；浙江省科技计划项目

（2010c31010）；浙江省网络通信技术与应用重点实验室资助项目

（2011z1001）；上海市信息安全综合管理技术研究重点实验室资助

项目（agk2011002）。

作者简介:

童超（1987-），男，浙江衢州人，硕士研究生，主要研究方向：

计算机视觉；章东平（1970-），男，江西波阳人，副教授，博士，

主要研究方向:图像处理、视频分析；陈非予（1987-），男，浙江

绍兴人，硕士研究生，主要研究方向：计算机视觉。