第3卷第2期 智能系统学报 Vol.3 Na 2 2008年4月 CAAI Transactions on Intelligent Systems Apr.2008 一种改进的运动目标跟踪与轨迹记录算法 赵雷，陈万忠，韩双双 (吉林大学通信工程学院，吉林长春130025) 摘要：针对目前运动目标的跟踪与记录方法占用存储空间较大的缺点，提出了一种减少存储空间的记录算法，即 先用三帧差分算法和Snake算法相结合检出运动物体的轮廓，再利用Hausdorff算法对提出的轮廓进行匹配，并将 匹配后的轮廓和运动轨迹以文本文件存储，大大降低了运动目标轨迹记录存储容量.实际运用表明，改进后的记录 存储空间相当于通常视频文件的万分之一，该算法适于长时间记录运动目标轨迹 关键词：运动轨迹记录跟踪；主动轮廓算法，三帧差分算法；Hausdorff匹配算法 中图分类号：TP391文献标识码：A文章编号：16734785(2008)02-014505 An improved algorithm for tracking and recording moving targets ZHAO Lei,CHEN Wanzhong,HAN Shuang shuang (College of Communication Engineering,Jilin University,Changchun 130025,China) Abstract:At present,data from tracking moving targets consumes too much memory.An improved record- ing algorithm is proposed that reduces memory requirements.First,initial points are obtained by using a three-frame difference algorithm.Then the Snake algorithm is used to extend the initial points to deter- mine the object's contour.Finally,the Hausdorff distance measurement matches contours to standard fig- ures and the results are saved in a text file.The improved algorithm uses approximately 0.01 of the usu- al memory required,so it is suitable for storing data from long term tracking. Key words :recording and tracking of moving objects;Snake algorithm;three-frame differencing;Hausdorff matching 目前，在计算机视觉领域中，运动目标轮廓的跟 录存储容量的问题，只需大约相当于通常视频文件 踪是一个热门领域，可是对分割出的目标记录方法 万分之一的空间，适于物体轨迹的长时间记录系统， 的研究相对较少山.一般是用avⅵi格式的文件进行 存储，其数据量相当大；近几年也有用MPEG1、 1匹配与跟踪算法 MPEG2、H261、H263、MPEG4等方法进行视频压 1.1 Huasdorff距离与物体匹配 缩，其中MPEG4能够比较高效率地进行压缩和解 Hausdorff距离作为一种距离测度，可以用来 压，压缩后的文件大约为原文件的30%，90min的 测量2个点集之间的匹配程度，它已被直接用于比 视频影像大约需要300MB,但对硬件要求很高！. 较2个多边形的相似程度.但本文应用中，目的是要 本文所提出的改进记录方法在先利用三帧差分算法 在一个经过处理的二值图形与一个模板进行匹配 和Snake算法相结合找到运动物体的轮廓，随后利 以下通过图例来进一步阐述本文的匹配原理， 用Hausdorff算法对提出的轮廓进行匹配，并将匹 首先考虑理想情况，假设图1(a)中仅存在一个 配后的轮廓和运动轨迹存储在2个文本文件中.此 圆C,圆心O,图中曲线连续且无其他边缘点，模 方法在一定程度上解决了单一刚体物体运动轨迹记 板为图1b)中的圆G2,圆心为O2,圆G和圆CG的 半径相等，图1(c为某一匹配过程，图中D、D、 收稿日期：2007-1026 基金项目：吉林省科技发展计划资助项目(20060531) D、D4分别为过两圆圆心的直线与两圆的交点，此 通讯作者：韩双双.E-mail:shuangl017@163.com. 时，模板（点集A)与待检测的圆G(点集B)的 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved hup://www.cnki.net
第 3 卷第 2 期 智 能 系 统 学 报 Vol. 3 №. 2 2008 年 4 月 CAA I Transactions on Intelligent Systems Apr. 2008 一种改进的运动目标跟踪与轨迹记录算法 赵 雷 , 陈万忠 , 韩双双 (吉林大学 通信工程学院 , 吉林 长春 130025) 摘 要 :针对目前运动目标的跟踪与记录方法占用存储空间较大的缺点 ,提出了一种减少存储空间的记录算法 ,即 先用三帧差分算法和 Snake 算法相结合检出运动物体的轮廓 ,再利用 Hausdorff 算法对提出的轮廓进行匹配 ,并将 匹配后的轮廓和运动轨迹以文本文件存储 ,大大降低了运动目标轨迹记录存储容量. 实际运用表明 ,改进后的记录 存储空间相当于通常视频文件的万分之一. 该算法适于长时间记录运动目标轨迹. 关键词 :运动轨迹记录跟踪 ;主动轮廓算法 ;三帧差分算法 ; Hausdorff 匹配算法 中图分类号 : TP391 文献标识码 :A 文章编号 :167324785 (2008) 0220145205 An improved algorithm for tracking and recording moving targets ZHAO Lei , CH EN Wan2zhong , HAN Shuang2shuang (College of Communication Engineering , Jilin University , Changchun 130025 , China) Abstract :At p resent ,data from tracking moving targets consumes too much memory. An improved record2 ing algorit hm is proposed that reduces memory requirements. First , initial points are obtained by using a t hree2frame difference algorithm. Then t he Snake algorit hm is used to extend t he initial points to deter2 mine t he object’s contour. Finally , the Hausdorff distance measurement matches contours to standard fig2 ures and t he results are saved in a text file. The improved algorithm uses app roximately 0. 01 % of t he usu2 al memory required , so it is suitable for storing data from long2term tracking. Keywords :recording and tracking of moving objects; Snake algorit hm ; t hree2frame differencing ; Hausdorff matching 收稿日期 :2007210226. 基金项目 :吉林省科技发展计划资助项目(20060531) . 通讯作者 :韩双双. E2mail :shuang1017 @163. com. 目前 ,在计算机视觉领域中 ,运动目标轮廓的跟 踪是一个热门领域 ,可是对分割出的目标记录方法 的研究相对较少[1 ] . 一般是用 avi 格式的文件进行 存储 ,其数据量相当大 ; 近几年也有用 MPEG1、 MPEG2、H261、H263、MPEG4 等方法进行视频压 缩 ,其中 MPEG4 能够比较高效率地进行压缩和解 压 ,压缩后的文件大约为原文件的 30 % ,90 min 的 视频影像大约需要 300 MB ,但对硬件要求很高[2 ] . 本文所提出的改进记录方法在先利用三帧差分算法 和 Snake 算法相结合找到运动物体的轮廓 ,随后利 用 Hausdorff 算法对提出的轮廓进行匹配 ,并将匹 配后的轮廓和运动轨迹存储在 2 个文本文件中. 此 方法在一定程度上解决了单一刚体物体运动轨迹记 录存储容量的问题 ,只需大约相当于通常视频文件 万分之一的空间 ,适于物体轨迹的长时间记录系统. 1 匹配与跟踪算法 1. 1 Huasdorff 距离与物体匹配 Hausdorff 距离作为一种距离测度 ,可以用来 测量 2 个点集之间的匹配程度 ,它已被直接用于比 较 2 个多边形的相似程度. 但本文应用中 ,目的是要 在一个经过处理的二值图形与一个模板进行匹配. 以下通过图例来进一步阐述本文的匹配原理. 首先考虑理想情况 ,假设图 1 (a) 中仅存在一个 圆 C1 ,圆心 O1 ,图中曲线连续且无其他边缘点 ,模 板为图 1 (b) 中的圆 C2 ,圆心为 O2 ,圆 C1 和圆 C2 的 半径相等 ,图 1 (c) 为某一匹配过程 ,图中 D1 、D2 、 D3 、D4 分别为过两圆圆心的直线与两圆的交点 ,此 时 ,模板 (点集 A ) 与待检测的圆 C1 (点集 B ) 的 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
·146· 智能系统学报 第3卷 Hausdorff距离为 f+1(x,以是视频序列中相邻的连续3帧。 H(A,B)=max(h(A,B)h(B.A))= d(x,以=f+1(x,以-f,(x,以表示连续2帧的差 1D1D2|=|DD4I. 分，对d,和d.1分别滤波后取交集，即可获得当前 式中D1D|和D3D4|分别表示D到D2及D 帧运动对象D。(x,以，差分算法原理见图2 到D4的距离.可以看出，如果让模板G沿O和O 所在的直线向圆G靠拢，则H(A,B)逐步减小，当 模板的圆C与待检测的圆G完全重合时，D,= D2=D3=D,H(A,B)=0,此时匹配效果最好 对于上述理想情况，Hausdorff距离很好地反 映了集合A和B的匹配程度.但是，在实际的应用 图2差分算法原理 中，一幅图像除了有与模板相同或相似的物体外，还 Fig.2 The principle of difference algorithm 存在着其他的边缘点，如图1(d)所示，G的圆心O 通过实验可知，三帧差分算法计算简单，有运算 上有一孤点，当D与D2的距离|DD2|大于 速度快的优点，能够达到实时的要求.但是，差分法 |D2O|时，有H(A,B)=|D1D2.实际上，当两圆 缺陷在于所提取出的轮廓往往不是单像素的，且无 G与CG2完全重合时应有最好的匹配程度，但此时 法将运动物体全部提取出来，如图3所示」 却有H(A,B)>H2(A,B),因此Hausdorff距离 不能直接用于实际的图像匹配中。 (a)实拍图像 (b)三帧差分的结果 (a)原图 (b)模板 图3三帧差分算法效果 Fig.3 The effect of three differential algorithm D 1.3主动轮廓算法 算法中设有一条可变空间曲线v(s,)由2个参 (c)2个理想圆的匹配 (d)圆C的圆心上有 数s(空间位置)和t时间)决定，s与t分别定义在区 一点时的匹配 间2与T上.v由具有相同参数的2个变量xy构 图1 Hausdorff距离匹配示意图 成即 Fig.I The sketch of Hausdorff distance matching v(x,=(xs,,y(s,d,s∈P,t∈T.2) Hausdorff距离可以自然地推广到部分Haus 这样，Snake的势能函数ESmake可以定义为 doff距离，以便匹配2个集合A和B的某个部分 对于2个有限点集A={am,m,ap}和B={h, R=支E》+E》+ Ereld(v(s）lds (3) 血，bp},A、B之间的部分Hausdorff距离定义为 式中：Ei代表Snake的内部能量，Eeu为图像能量， Hu(A,B)max(h(B,A)h (A,B)).(1) Eneld为外部能量. 式中：：(A,B)称为集合A到集合B的部分有向 然而，主动轮廓算法也有许多局限，该算法强烈 Hausdorf距离，其中1≤k≤p,1≤I≤q, 地依赖于轮廓的初始位置，且捕捉范围小，不仅因进 hk(B,A)=K8 ea min‖a-b‖，h加(A,B)=Le 入凹陷区域困难而常常陷于能量局部极值，而且不 m‖b-aⅡ，这里表示从集合B到集合A排 支持拓扑改变，另外在外力很小时，轮廓会收缩到一 序后的距离值集合中的第K值，L出4表示从A集合 点.针对初始位置敏感的问题，有些文献提出了利用 到B集合排序后的距离值集合中的第L个值， 遗传算法来处理，因为它的优势在于能保证能量全 1.2三帧差分算法 局最小化.但是其缺点是计算量会随搜索空间的增 三帧差分算法中，设f1(x,y以、f,(x,以、 大而增长迅速.难以实时应用 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.htp://www.cnki.net
Hausdorff 距离为 H ( A , B) = max ( h( A , B) , h( B , A) ) = | D1 D2 | =| D3 D4 | . 式中 :| D1 D2 | 和| D3 D4 | 分别表示 D1 到 D2 及 D3 到 D4 的距离. 可以看出 ,如果让模板 C2 沿 O1 和 O2 所在的直线向圆 C1 靠拢 ,则 H ( A , B) 逐步减小 ,当 模板的圆 C2 与待检测的圆 C1 完全重合时 , D1 = D2 = D3 = D4 , H ( A , B) = 0 ,此时匹配效果最好. 对于上述理想情况 , Hausdorff 距离很好地反 映了集合 A 和 B 的匹配程度. 但是 ,在实际的应用 中 ,一幅图像除了有与模板相同或相似的物体外 ,还 存在着其他的边缘点 ,如图 1 (d) 所示 ,C1 的圆心 O1 上有一孤点 , 当 D1 与 D2 的距离 | D1 D2 | 大 于 | D2 O1 | 时 ,有 H2 ( A , B) = | D1 D2 | . 实际上 ,当两圆 C1 与 C2 完全重合时应有最好的匹配程度 ,但此时 却有 H1 ( A , B) > H2 ( A , B) ,因此 Hausdorff 距离 不能直接用于实际的图像匹配中. 图 1 Hausdorff 距离匹配示意图 Fig. 1 The sketch of Hausdorff distance matching Hausdorff 距离可以自然地推广到部分 Haus2 dorff 距离 ,以便匹配 2 个集合 A 和 B 的某个部分. 对于 2 个有限点集 A = { a1 , a2 , …, ap } 和 B = { b1 , b2 , …, bp } , A 、B 之间的部分 Hausdorff 距离定义为 Hkl ( A , B) = max ( hk ( B , A) , hl ( A , B) ) . (1) 式中 : hk ( A , B) 称为集合 A 到集合 B 的部分有向 Hausdorff 距 离 , 其 中 1 ≤ k ≤ p , 1 ≤ l ≤ q , hk ( B , A) = K th b∈B min a∈A ‖a - b ‖, hl ( A , B ) = L th a ∈A min b∈B ‖b - a ‖,这里 K th b∈B表示从集合 B 到集合 A 排 序后的距离值集合中的第 K 值 , L th a∈A表示从 A 集合 到 B 集合排序后的距离值集合中的第 L 个值. 1. 2 三帧差分算法 三帧差分算法中 , 设 f t - 1 ( x , y ) 、f t ( x , y ) 、 f t + 1 ( x , y) 是 视 频 序 列 中 相 邻 的 连 续 3 帧 , dt ( x , y) = f t + 1 ( x , y) - f t ( x , y) 表示连续 2 帧的差 分 ,对 dt 和 d t - 1分别滤波后取交集 ,即可获得当前 帧运动对象 Do ( x , y) ,差分算法原理见图 2. 图 2 差分算法原理 Fig. 2 The principle of difference algorithm 通过实验可知 ,三帧差分算法计算简单 ,有运算 速度快的优点 ,能够达到实时的要求. 但是 ,差分法 缺陷在于所提取出的轮廓往往不是单像素的 ,且无 法将运动物体全部提取出来 ,如图 3 所示. 图 3 三帧差分算法效果 Fig. 3 The effect of three differential algorithm 1. 3 主动轮廓算法 算法中设有一条可变空间曲线 v (s, t) 由 2 个参 数 s(空间位置) 和 t(时间) 决定 ,s 与 t 分别定义在区 间Ω与 T 上. v 由具有相同参数的 2 个变量 x、y 构 成 ,即 v ( x , t) = ( x (s, t) , y (s, t) ) ,s ∈Ω, t ∈ T. (2) 这样 ,Snake 的势能函数 ESnake可以定义为 ESnake = 1 2∫Ω [ Eint ( v (s) ) + Eext ( v (s) ) + Efield ( v (s) ) ]ds. (3) 式中 : Eint代表 Snake 的内部能量 , Eext 为图像能量 , Efield为外部能量. 然而 ,主动轮廓算法也有许多局限 ,该算法强烈 地依赖于轮廓的初始位置 ,且捕捉范围小 ,不仅因进 入凹陷区域困难而常常陷于能量局部极值 ,而且不 支持拓扑改变 ;另外在外力很小时 ,轮廓会收缩到一 点. 针对初始位置敏感的问题 ,有些文献提出了利用 遗传算法来处理 ,因为它的优势在于能保证能量全 局最小化. 但是其缺点是计算量会随搜索空间的增 大而增长迅速. 难以实时应用. ·146 · 智 能 系 统 学 报 第 3 卷 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第2期 赵雷，等：一种改进的运动目标跟踪与轨迹记录算法 ·147· 1.4改进的目标跟踪算法 先将连续3帧图形进行差分后做与运算，经过滤波 由前文所述可知三帧差分法计算简单，运算速 后得到物体大致轮廓，并提取出等距初始轮廓点.同 度快.但它所提取出的轮廓并不完整，所以往往不能 时，求出中间帧图像的梯度，在设定好主动轮廓算法 直接使用：而主动轮廓法则可精确地分割出单像素 的各项系数后，再以提取出的初始轮廓点为基础，利 完整轮廓，但该方法运算复杂，不适合做实时处理， 用主动轮廓算法对曲线进行扩张，经过少量的迭代 且自适应地选择较好的初始轮廓点也有一定困难. 后就可得到物体的实际轮廓.改进后跟踪算法原理 本文将上述2种算法融合，改进了跟踪算法.首 框图如图4所示 第1-1帧→ 差分 2幅 分图形 自适应 部分运动 等距取 做与运 滤波 对象轮廓 初始点 第1+1帧· 算 差分 第1帧 求图像梯度 设定主动轮廓算法 利用主动轮廓算法 得到物体轮廓 各项系数 扩张曲线 图4改进跟踪算法框图 Fig.4 Improved tracking algorithm diagram 板与该移动目标之间的相似度的度量，匹配过程如 2 轨迹记录算法 下 本文提出了一种只利用2个文本文件对单一刚 设第1次平移匹配时，若参考模板中符合要求 体的运动轨迹进行记录的方法.为了在播放记录时 的点与跟踪图像中总点数的比率为R,取p()= 能够更直观地观察物体的外形和运动状态，本方法 max(R),其中k为对参考模板个数的计数，j为对 利用Hausdorff距离匹配出物体的形状模板并在播 某一个参考模板平移的次数.取maxp()对应的参 放时显示，这样就可以观察到更完整的目标.系统对 考模板为最终结果，并将每一帧匹配的参考模板进 模板的选取，主要采取了“模板训练”的思想.即首先 行统计 针对几个典型的刚体形状采样，利用主动轮廓算法 本系统在实际匹配过程中发现，采用基本形式 提取轮廓，经过一定的修正形成匹配识别参考模板. 的Hausdorff距离，由于其易受部分像素点偏差的 本文所建系统采用修正的Hausdorff距离 影响，致使整体匹配效果降低，故系统采取了修正的 (MHD)来进行模板匹配，其定义为 Hausdorff距离模板匹配法，即通过对若干帧中得 -Nimin llall. h(A,B)=1 4) 到的h:(M,)求平均来得到模板相对于待识别图像 的相似度，即，h(M,)=∑h,(M,)/N,其中N为 式中：N4是点集A中点的个数.修正的Hausdorff 模板中的边缘像素点的个数.当某一参考模板匹配 距离对噪声不太敏感，可避免由于部分噪声像素点 次数超过80%时，认为此模板与物体匹配，并将此 的干扰带来的偏差。 模板存入一个文本文件中.实验表明，修正后的 Hausdorff匹配中h(M,),其中M为参考模 Hausdorff距离能提高识别率】 板点的集合；1为跟踪到移动物体边缘的点集.由于 另一个文本负责记录每一帧中目标重心的位 主动轮廓算法能够提出完整的物体轮廓点集，因此 置，并以(x,以的格式全部进行存储.由所有这些重 无需再进一步对这2个点集做预处理.匹配识别时， 心连接成的曲线就可以看作物体的移动轨迹，再通 首先对提取出的待识别图像实施Euclidean距离变 过重心的移动推算出形状模板此时的位置， 换，以得到距离映射图，然后在距离空间内，将模板 在距离映射图上进行平移匹配.相应的，h(M,)取 3实验及数据处理 参考模板中的点在当前距离映射图上对应位置处的 对一个移动的五角星型物体进行了跟踪的实 最大值，其中1为平移次数，它度量的是最大不匹配 验，分别利用MPEG4和本文算法进行记录.计算 程度.所以，基本的匹配判别规则即为：取所有平移 机：Pentium(R)4CPU2.00GHz,256MB内存； 匹配中得到的(M,)值中的最小值，作为这个模 普通的PC摄像头：软件方面以Visual C++6.0 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.htp://www.cnki.net
1. 4 改进的目标跟踪算法 由前文所述可知三帧差分法计算简单 ,运算速 度快. 但它所提取出的轮廓并不完整 ,所以往往不能 直接使用 ;而主动轮廓法则可精确地分割出单像素 完整轮廓 ,但该方法运算复杂 ,不适合做实时处理 , 且自适应地选择较好的初始轮廓点也有一定困难. 本文将上述 2 种算法融合 ,改进了跟踪算法. 首 先将连续 3 帧图形进行差分后做与运算 ,经过滤波 后得到物体大致轮廓 ,并提取出等距初始轮廓点. 同 时 ,求出中间帧图像的梯度 ,在设定好主动轮廓算法 的各项系数后 ,再以提取出的初始轮廓点为基础 ,利 用主动轮廓算法对曲线进行扩张 ,经过少量的迭代 后就可得到物体的实际轮廓. 改进后跟踪算法原理 框图如图 4 所示. 图 4 改进跟踪算法框图 Fig. 4 Improved tracking algorithm diagram 2 轨迹记录算法 本文提出了一种只利用 2 个文本文件对单一刚 体的运动轨迹进行记录的方法. 为了在播放记录时 能够更直观地观察物体的外形和运动状态 ,本方法 利用 Hausdorff 距离匹配出物体的形状模板并在播 放时显示 ,这样就可以观察到更完整的目标. 系统对 模板的选取 ,主要采取了“模板训练”的思想. 即首先 针对几个典型的刚体形状采样 ,利用主动轮廓算法 提取轮廓 ,经过一定的修正形成匹配识别参考模板. 本文所建系统采用修正 的 Hausdorff 距 离 (M HD) 来进行模板匹配 ,其定义为 h( A , B) = 1 NA a∑∈A min b∈B ‖a - b ‖. (4) 式中 : NA 是点集 A 中点的个数. 修正的 Hausdorff 距离对噪声不太敏感 ,可避免由于部分噪声像素点 的干扰带来的偏差. Hausdorff 匹配中 h ( M , I) ,其中 M 为参考模 板点的集合; I 为跟踪到移动物体边缘的点集. 由于 主动轮廓算法能够提出完整的物体轮廓点集 ,因此 无需再进一步对这 2 个点集做预处理. 匹配识别时 , 首先对提取出的待识别图像实施 Euclidean 距离变 换 ,以得到距离映射图 ,然后在距离空间内 ,将模板 在距离映射图上进行平移匹配. 相应的 , hi ( M , I) 取 参考模板中的点在当前距离映射图上对应位置处的 最大值 ,其中 i 为平移次数 ,它度量的是最大不匹配 程度. 所以 ,基本的匹配判别规则即为 :取所有平移 匹配中得到的 hi ( M , I) 值中的最小值 ,作为这个模 板与该移动目标之间的相似度的度量 ,匹配过程如 下. 设第 i 次平移匹配时 ,若参考模板中符合要求 的点与跟踪图像中总点数的比率为 Ri ,取 p ( k) = max j ≤i ( Ri) ,其中 k 为对参考模板个数的计数 , j 为对 某一个参考模板平移的次数. 取max k p ( k) 对应的参 考模板为最终结果 ,并将每一帧匹配的参考模板进 行统计. 本系统在实际匹配过程中发现 ,采用基本形式 的 Hausdorff 距离 ,由于其易受部分像素点偏差的 影响 ,致使整体匹配效果降低 ,故系统采取了修正的 Hausdorff 距离模板匹配法 ,即通过对若干帧中得 到的 hi ( M , I) 求平均来得到模板相对于待识别图像 的相似度 ,即 , hi ( M , I) = ∑hi ( M , I) / N ,其中 N 为 模板中的边缘像素点的个数. 当某一参考模板匹配 次数超过 80 %时 ,认为此模板与物体匹配 ,并将此 模板存入一个文本文件中. 实验表明 ,修正后的 Hausdorff 距离能提高识别率. 另一个文本负责记录每一帧中目标重心的位 置 ,并以( x , y) 的格式全部进行存储. 由所有这些重 心连接成的曲线就可以看作物体的移动轨迹 ,再通 过重心的移动推算出形状模板此时的位置. 3 实验及数据处理 对一个移动的五角星型物体进行了跟踪的实 验 ,分别利用 MPEG4 和本文算法进行记录. 计算 机 :Pentium(R) 4 CPU 2. 00 GHz ,256 MB 内存 ; 普通的 PC 摄像头 :软件方面以 Visual C + + 6. 0 第 2 期 赵 雷 ,等 :一种改进的运动目标跟踪与轨迹记录算法 ·147 · © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
·148· 智能系统学报 第3卷 为开发平台，程序利用Micro soft提供的VFW软件 包对捕捉的视频数据进行处理，并分别用MPEG4 格式和本文提出的算法进行记录.图5、图6是实验 时记录数据的截图.其中，图5给出了利用MPEG4 进行记录并提取出物体轮廓的截图.图6为利用本 文提出的改进记录跟踪算法记录的截图.其中点状 部分为提取出的轮廓点，五角星中间红色的圆点为 物体的重心，为了便于观察，将相邻2个点之间用线 进行连接.由图5可以看到，MPEG4虽然能够提供 (b)第24帧 效果较好的视觉效果，但对于关注物体的轮廓和运 动轨迹的跟踪来说这方面显得就不是非常紧要了， 图5中MPEG4记录的视频序列用Snake算法进行 轮廓提取后得到的图像，并不能直观地看到物体的 轮廓及其运动轨迹.相较avi和MPEG4,本文算法 不仅只需要很小的存储空间，而且记录下的物体的 轮廓和运动轨迹非常清晰.本算法只需记录一次物 体的匹配轮廓，随后利用重心的偏移来计算物体的 位置.从图6中可以清晰地看到由物体重心所构成 的物体的运动轨迹.该算法对于关注物体轮廓与运 (c)第46帧 动轨迹的长时间跟踪记录有很大的优势.图7是几 种算法所占空间的比较.同样90min的跟踪，如果 图6改进跟踪记录算法结果 利用avi格式要就900MB,用MPEG4进行压缩后 Fig.6 The results of improved tracking record algorithm 也需要大概300MB的空间，可是如果采用本文的 算法只需160~180KB的空间（视跟踪物体轮廓的 900 avi格式一 500 大小及复杂度而定).很好地解决了关注物体行进轨 400 迹的长时间跟踪时存储空间的问题， 300 MPEG4 200, 100 0 20 0.50 0.25 改进记录算法 0.05 102030405060708090 时间/min 图7几种算法所占空间的比较 图5MPEG1算法记录跟踪结果 Fig.7 The comparison of space occupied by algorithms Fig.5 MPEG4 algorithm record the tracking results 4结束语 本文通过三帧差分算法，先提取出初始轮廓并 找到了轮廓的约束条件，随后利用主动轮廓算法来 逼近物体的真实轮廓，从而准确地提取出物体轮廓， 并实时跟踪.再利用Hausdorff算法对提出的轮廓 进行匹配，并将匹配后的轮廓和轨迹以文本文件方 式存储，仅利用几十KB就能够达到几百MB avi格 式文件的效果，大大降低了运动目标轨迹记录存储 (a)第13顿 容量.该算法能够实时准确地对物体进行跟踪，并能 够对物体的轮廓和轨迹进行长时间的记录.实验证 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.htp://www.cnki.net
为开发平台 ,程序利用 Microsoft 提供的 VFW 软件 包对捕捉的视频数据进行处理 ,并分别用 MPEG4 格式和本文提出的算法进行记录. 图 5、图 6 是实验 时记录数据的截图. 其中 ,图 5 给出了利用 MPEG4 进行记录并提取出物体轮廓的截图. 图 6 为利用本 文提出的改进记录跟踪算法记录的截图. 其中点状 部分为提取出的轮廓点 ,五角星中间红色的圆点为 物体的重心 ,为了便于观察 ,将相邻 2 个点之间用线 进行连接. 由图 5 可以看到 ,MPEG4 虽然能够提供 效果较好的视觉效果 ,但对于关注物体的轮廓和运 动轨迹的跟踪来说这方面显得就不是非常紧要了. 图 5 中 MPEG4 记录的视频序列用 Snake 算法进行 轮廓提取后得到的图像 ,并不能直观地看到物体的 轮廓及其运动轨迹. 相较 avi 和 MPEG4 ,本文算法 不仅只需要很小的存储空间 ,而且记录下的物体的 轮廓和运动轨迹非常清晰. 本算法只需记录一次物 体的匹配轮廓 ,随后利用重心的偏移来计算物体的 位置. 从图 6 中可以清晰地看到由物体重心所构成 的物体的运动轨迹. 该算法对于关注物体轮廓与运 动轨迹的长时间跟踪记录有很大的优势. 图 7 是几 种算法所占空间的比较. 同样 90 min 的跟踪 ,如果 利用 avi 格式要就 900 MB ,用 MPEG4 进行压缩后 也需要大概 300 MB 的空间 ,可是如果采用本文的 算法只需 160～180 KB 的空间(视跟踪物体轮廓的 大小及复杂度而定) . 很好地解决了关注物体行进轨 迹的长时间跟踪时存储空间的问题. 4 结束语 本文通过三帧差分算法 ,先提取出初始轮廓并 找到了轮廓的约束条件 ,随后利用主动轮廓算法来 逼近物体的真实轮廓 ,从而准确地提取出物体轮廓 , 并实时跟踪. 再利用 Hausdorff 算法对提出的轮廓 进行匹配 ,并将匹配后的轮廓和轨迹以文本文件方 式存储 ,仅利用几十 KB 就能够达到几百 MB avi 格 式文件的效果 ,大大降低了运动目标轨迹记录存储 容量. 该算法能够实时准确地对物体进行跟踪 ,并能 够对物体的轮廓和轨迹进行长时间的记录. 实验证 ·148 · 智 能 系 统 学 报 第 3 卷 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第2期 赵雷，等：一种改进的运动目标跟踪与轨迹记录算法 ·149· 明，该算法在对单目标运动目标轮廓跟踪与轨迹记 ZHANG Wentao.Accurate regiou detection of high 录方面是有效、可行的.将本文方法应用到复杂目标 speed multrtarget visual system[J].Journal of Electron- 和多种目标跟踪，将是下一步探讨的问题， ics and Information Technology,2001,23(4):354-359. [7]张良国.基于Haudorff距离的手势识别[U】.中国图象图 参考文献： 形学报，2002,7(11)：11441150. ZHANG Liangguo.Hand gesture recognition based on [1]丁贵宝.多媒体数据压缩标准化的现状与发展[J].计算 机工程与应用，2002,38(1)：104107 Hausdorff distance [J].Journal of Image and Graphics, 2002,7(11):11441150. DIN G Guibao.The present situation and development of [8]LESA GE F.Experimenting level set-based snakes for the multimedia data compression standard [J ]Computer contour segmentation in radar imagery [C]//Conference Engineering and Applications,2002,38(1):104-107. Visual Information Processing IX.Orlando,USA,2000: [2]王兴国，压缩域MPEG2到MPEG4视频转码中不匹配 4041-4044 宏块的复原算法[J].电子学报，2002,30(9)：1405 作者简介： 1408. 赵雷，男，1982年生，硕士研究生 WANG Xingguo.Robust mode mismatch macroblock re- 主要研究方向为信号与信息处理 trieval algorithm for transcoding MPEG2 to MPEG4 in compression domain[J].Acta Electronica Sinica,2002, 30(9):14051408. [3]胡炯炯.基于形态学约束的B-Snake模型的细胞图像自 动分割方法卩].中国图象图形学报，2005,10(1)：585 589. 陈万忠，男，1963年生，教授，教育部 HU Jiongjiong.Automatic cell image segmentation based 电子信息类教学协作委员会委员，主要研 on B-Snake model with constraint of morpholog [J ] 究方向为信号与信息处理及其应用技术 Journal of Image and Graphicsy,2005,10(1):585-589. 获2006年汽车工业科学技术进步奖1项 [4]郭礼华，基于直方图的Snake视频对象跟踪算法[卩].中 近3年发表论文12篇，EI检索3篇，ISTP 国图象图形学报，2005,10(2)：197202 检索3篇，主编教材1部。 GUO Lihua.Video object tracking method based on snake model using object's histogram information [J ] Journal of Image and Graphics,2005,10(2):197-202. [5]王成儒.基于差分交集的视频对象分割与跟踪算法[U] 韩双双，男，1983年生，硕士研究生， 主要研究方向为信号与信息处理 中国图象图形学报，2004,30(9)：564570. WANGChengru.Video object segmentation and tracking algorithm based on difference and intersection[J ]Journal of Image and Graphics,2004,30(9)564-570 [6]张文涛.高速运动可视多目标精确检测研究J].电子与 信息学报，2001,23(4)：354359 第十一届中国机器学习会议 The 11th China Conference on Machine Learning 第十一届中国机器学习会议(CCML2008)由中国人工智能学会机器学习专业委员会和中国计算机学会 人工智能与模式识别专业委员会联合主办，大连海事大学承办.该系列会议每两年举行一次，现已成为国内 机器学习界最主要的学术活动.此次会议将为机器学习及相关研究领域的学者交流最新研究成果、进行广泛 的学术讨论提供便利，并且将邀请国内机器学习领域的著名学者做精彩报告 会议录用论文将被推荐到《Journal of Computational Information Systems》(英文稿件)、《电子学报》、 《计算机研究与发展》、《模式识别与人工智能》、《计算机科学》、《计算机工程与应用》、《小型微型计算机系 统》、《广西师范大学学报》、《计算机辅助工程》、《郑州大学学报》、《大连海事大学学报》等期刊上发表.会议还 将评出优秀学生论文，颁发证书并给予奖励 会议网站：http://www.dlmu.edu.cn/ccml2008 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
明 ,该算法在对单目标运动目标轮廓跟踪与轨迹记 录方面是有效、可行的. 将本文方法应用到复杂目标 和多种目标跟踪 ,将是下一步探讨的问题. 参考文献 : [1 ]丁贵宝. 多媒体数据压缩标准化的现状与发展[J ]. 计算 机工程与应用 , 2002 , 38 (1) :1042107. DIN G Guibao. The present situation and development of the multimedia data compression standard[J ]. Computer Engineering and Applications , 2002 , 38 (1) :1042107. [ 2 ]王兴国. 压缩域 MPEG22 到 MPEG24 视频转码中不匹配 宏块的复原算法 [J ]. 电子学报 , 2002 , 30 ( 9) : 14052 1408. WAN G Xingguo. Robust mode mismatch macroblock re2 trieval algorithm for transcoding MPEG22 to MPEG24 in compression domain[J ]. Acta Electronica Sinica , 2002 , 30 (9) :140521408. [3 ]胡炯炯. 基于形态学约束的 B2Snake 模型的细胞图像自 动分割方法[J ]. 中国图象图形学报 , 2005 , 10 (1) :5852 589. HU Jiongjiong. Automatic cell image segmentation based on B2Snake model with constraint of morpholog [J ]. Journal of Image and Graphicsy , 2005 , 10 (1) : 5852589. [4 ]郭礼华. 基于直方图的 Snake 视频对象跟踪算法[J ]. 中 国图象图形学报 , 2005 , 10 (2) :1972202. GUO Lihua. Video object tracking method based on snake model using object’s histogram information [J ] . Journal of Image and Graphics , 2005 , 10 (2) :1972202. [5 ]王成儒. 基于差分交集的视频对象分割与跟踪算法[J ]. 中国图象图形学报 , 2004 , 30 (9) :5642570. WAN G Chengru. Video object segmentation and tracking algorithm based on difference and intersection[J ].Journal of Image and Graphics , 2004 , 30 (9) :5642570. [6 ]张文涛. 高速运动可视多目标精确检测研究[J ]. 电子与 信息学报 , 2001 , 23 (4) :3542359. ZHAN G Wentao. Accurate regiou detection of high2 speed multi2target visual system[J ]. Journal of Electron2 ics and Information Technology , 2001 , 23 (4) :3542359. [7 ]张良国. 基于 Haudorff 距离的手势识别[J ]. 中国图象图 形学报 , 2002 , 7 (11) :114421150. ZHAN G Liangguo. Hand gesture recognition based on Hausdorff distance [J ]. Journal of Image and Graphics , 2002 , 7 (11) :114421150. [8 ] L ESA GE F. Experimenting level set2based snakes for contour segmentation in radar imagery[ C]/ / Conference Visual Information Processing IX. Orlando ,USA ,2000 : 404124044. 作者简介 : 赵 雷 ,男 ,1982 年生 ,硕士研究生 , 主要研究方向为信号与信息处理. 陈万忠 ,男 ,1963 年生 ,教授 ,教育部 电子信息类教学协作委员会委员 ,主要研 究方向为信号与信息处理及其应用技术 , 获 2006 年汽车工业科学技术进步奖 1 项 , 近 3 年发表论文 12 篇 , EI 检索 3 篇 ,ISTP 检索 3 篇 ,主编教材 1 部. 韩双双 ,男 ,1983 年生 ,硕士研究生 , 主要研究方向为信号与信息处理. 第十一届中国机器学习会议 The 11th China Conference on Machine Learning 第十一届中国机器学习会议(CCML2008) 由中国人工智能学会机器学习专业委员会和中国计算机学会 人工智能与模式识别专业委员会联合主办 ,大连海事大学承办. 该系列会议每两年举行一次 ,现已成为国内 机器学习界最主要的学术活动. 此次会议将为机器学习及相关研究领域的学者交流最新研究成果、进行广泛 的学术讨论提供便利 ,并且将邀请国内机器学习领域的著名学者做精彩报告. 会议录用论文将被推荐到《Journal of Comp utational Information Systems》(英文稿件) 《、电子学报》、 《计算机研究与发展》《、模式识别与人工智能》《、计算机科学》《、计算机工程与应用》《、小型微型计算机系 统》《、广西师范大学学报》《、计算机辅助工程》《、郑州大学学报》《、大连海事大学学报》等期刊上发表. 会议还 将评出优秀学生论文 ,颁发证书并给予奖励. 会议网站 :http :/ / www. dlmu. edu. cn/ ccml2008. 第 2 期 赵 雷 ,等 :一种改进的运动目标跟踪与轨迹记录算法 ·149 · © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
