Ｖｏ１．３８．Ｎｏ．３ Ｍａｒ．２０ｌ３ 火力与指挥控制 Ｆｉｒｅ Ｃｏｎｔｒｏｌ＆Ｃｏｍｍａｎｄ Ｃｏｎｔｒｏｌ 第３８卷第３期 ２０１３年３月 文章编号：１００２—０６４０（２０１ ３）０３—００２２—０５ 基于新模板匹配的运动目标跟踪算法 穆欣侃 ，徐德江 ，罗海波 ，石振刚 （１．沈阳理工大学信息科学与工程学院，沈阳１１０１５９；２．中国科学院沈阳自动化研究所，沈阳１１００１６） 摘要：针对运动目标跟踪过程中存在的目标被遮挡和环境易变性问题，提出了一种基于仿射变换状态转移与 粒子滤波的新模板匹配目标跟踪算法。该算法以归一化互相关系数作为隶属度选出最佳仿射变换参数，依据特定的 状态转移方法确定出目标位置，同时利用粒子滤波算法学习目标的运动状态，对遮挡中的目标位置进行预测。实验 结果表明，该算法不仅可实现有效的运动目标跟踪，而且在光照适应性、抗噪性、背景适应性以及抗遮挡方面的跟踪 效果明显优于超平面逼近跟踪算法、均值平移跟踪算法以及协方差跟踪算法。 关键词：归一化互相关系数，仿射变换，状态转移，粒子滤波，运动目标跟踪，模板匹配 中图分类号：ＴＰ３９１．４１ 文献标识码：Ａ Ｎｏｖｅｌ Ｍｏｖｉｎｇ Ｔａｒｇｅｔ Ｔｒａｃｋｉｎｇ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｎｅｗ Ｔｅｍｐｌａｔｅ Ｍａｔｃｈｉｎｇ Ｍ Ｕ Ｘｉｎ－ｋａｎ ，ＸＵ Ｄｅ－ｊｉａｎｇ２，ＬＵＯ Ｈａｉ－ｂｏ ，ＳＨＩ Ｚｈｅｎ－ｇａｎｇ （１．Ｓｃｈｏｏｌ ｏｆＩｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｓｈｅｎｙａｎｇ Ｌｉｇｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈｅｎｙａｎｇ １１０１５９，Ｃｈｉｎａ； ２．ＳｈｅｎｙａｎｇＩｎｓｔｉｔｕｔｅ ｏｆＡｕｔｏｍａｔｉｏｎ，Ｃｈｉｅｓｎｅ Ａｃａｄｅｍｙ ｏｆＳｃｉｅｎｃｅｓ，Ｓｈｅｎｙａｎｇ １１００１６，Ｃｈｉｎａ，） Ａｂｓｔｒａｃｔ：Ｆｏｒ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｍｏｖｉｎｇ ｔａｒｇｅｔ ｕｎｄｅｒ ｏｃｃｌｕｓｉｏｎ ａｎｄ ｅｎｖｉｒｏｎｍｅｎｔａｌ ｖａｒｉａｂｉｌｉｔｙ ｉｎ ｐｒｏｃｅｓｓｉｎｇ ｏｆ ｍｏｖｉｎｇ ｔａｒｇｅｔ ｔｒａｃｋｉｎｇ，ａ ｎｏｖｅｌ ｔｅｍｐｌａｔｅ ｍａｔｃｈｉｎｇ ｔａｒｇｅｔ ｔｒａｃｋｉｎｇ（ＮＴＭＴＩ＇）ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ａｆｆｉｎｅ ｔｒａｎｓｆｏｒｍａｔｉｏｎ，ｓｔａｔｅ ｔｒａｎｓｉｔｉｏｎ ａｎｄ ｔｈｅ ｐａｒｔｉｃｌｅ ｆｉｌｔｅｒ ｉｓ ｐｒｅｓｅｎｔｅｄ．Ｎｏｒｍａｌｉｚｅｄ ｃｒｏｓｓ— ｃｏｒｒｅｌａｔｉｏｎ ｃｏｅｆｆｉｃｉｅｎｔ ｉｓ ｕｓｅｄ ａｓ ｍｅｍｂｅｒｓｈｉｐ ｔｏ ｃｈｏｏｓｅ ｔｈｅ ｏｐｔｉｍａｌ ａｆｆｉｎｅ ｔｒａｎｓｆｏｒｍａｔｉｏｎ ｐａｒａｍｅｔｅｒ ａｎｄ ｔｈｅ ｔａｒｇｅｔ ｌｏｃａｔｉｏｎ ｉｓ ｄｅｔｅｒｍｉｎｅｄ ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｓｔａｔｅ ｔｒａｎｓｉｔｉｏｎ．Ｍｅａｎｗｈｉｌｅ，ｔｈｅ ｐａｒｔｉｃｌｅ ｆｉｌｔｅｒ ｉｓ ａｄｏｐｔｅｄ ｔｏ ｌｅａｒｎ ｔｈｅ ｓｔａｔｅ ｍｏｔｉｏｎ ｏｆ ｔｈｅ ｔａｒｇｅｔ，ａｎｄ ｔｈｅｎ ｔｈｅ ｌｏｃａｔｉｏｎ ｏｆ ｔｈｅ ｔａｒｇｅｔ ｕｎｄｅｒ ｏｃｃｌｕｓｉｏｎ ｉｓ ｐｒｅｄｉｃｔｅｄ．Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ｔｅｍｐｌａｔｅ ｍａｔｃｈｉｎｇ ｔａｒｇｅｔ ｔｒａｃｋｉｎｇ ａｌｇｏｒｉｔｈｍ ｉｓ ｅｆｉｃｉｅｎｔ ａｎｄ ｅｆｆｅｃｔｉｖｅ ｉｎ ｍｏｖｉｎｇ ｔａｒｇｅｔｆ ｔｒａｃｋｉｎｇ ａｎｄ ｇｅｔ ｈｉｇｈｅｒ ｔｒａｃｋｉｎｇ ｐｅｒｆｏｒｍａｎｃｅ ｉｎ ｄｅａｌｉｎｇ ｗｉｔｈ ｔｈｅ ｉｌｌｕｍｉｎａｔｉｏｎ ｃｈａｎｇｅ，ｎｏｉｓｅ，ｔｈｅ ｂａｃｋｇｒｏｕｎｄ ｃｈａｎｇｅ ａｎｄ ｏｃｃｌｕｓｉｏｎ ｃｏｍｐａｒｅｄ ｗｉｔｈ ｈｙｐｅｒ－ｐｌａｎｅ ａｐｐｒｏｘｉｍａｔｉｏｎ ｔｒａｃｋｉｎｇ ａｌｇｏｒｉｔｈｍ，ｍｅａｎ ｓｈｉｔｆ ｔｒａｃｋｉｎｇ ａｌｇｏｒｉｔｈｍ ａｎｄ ｃｏｖａｒｉａｎｃｅ ｔｒａｃｋｉｎｇ ａｌｇｏｒｉｔｈｍ． Ｋｅｙ ｗｏｒｄｓ：ｎｏｒｍａｌｉｚｅｄ ｃｒｏｓｓ－ｃｏｒｒｅｌａｔｉｏｎ ｃｏｅｆｆｉｃｉｅｎｔ，ａｆｆｉｎｅ ｔｒａｎｓｆｏｒｍａｔｉｏｎ，ｓｔａｔｅ ｔｒａｎｓｉｔｉｏｎ，ｐａｒｔｉｃｌｅ ｉｌｔｅｒ，ｍｏｖｉｎｇ ｆｔａｒｇｅｔ ｔｒａｃｋｉｎｇ，ｔｅｍｐｌａｔｅ ｍａｔｃｈｉｎｇ 引 言 图像匹配…是对图像进行位移和形变使得模 匹配算法对实现精确的目标跟踪具有重要的意义， 但是目标跟踪过程中存在的环境易变和目标被遮 板图像与输入图像的差别最小化的过程，在目标跟 踪、运动分析、立体视觉和图像拼接等计算机视觉 领域得到了广泛的应用，所以研究快速有效的图像 收稿日期：２０１２—０２—０８ 修回日期：２０１２—０３—１４ 挡问题一直是该领域亟待解决的一个难点。 Ｊｕｒｉｅｔ 在２００２年提出了一种模板匹配的超平 面逼近方法，使用投影变换和仿射变换描述图像变 换模型，通过离线训练一个超平面矩阵，求解变换 基金项目：国家自然科学基金资助项目（６０８０２０３１） 作者简介：穆欣侃（１９７７－），男，河北阜城人，硕士，讲师。主要研究方向：模式识别及计算机网络应用。 ・２２・ 穆欣侃，等：基于新模板匹配的运动目标跟踪算法 （总第３８—０３８５） 参数，应用状态转移和迭代的方法求取目标位置， 使得算法的收敛速度提高了３倍～４倍。然而该算 法需要离线训练数据，不能及时进行目标跟踪，且 灰度不变的假设导致光照适应性和抗噪性都很差。 为了解决光照适应性和抗噪性差的问题，文献 ［４］从理论和实验两个方面证明了归一化互相关匹 配算法具有良好的光照适应性和抗噪性，但算法在 跟踪过程中需要对一定的区域进行遍历，且对目标 的旋转、放缩和错切的适应性较差。为此，文献Ｅ５—６］ 分别在人脸识别和目标跟踪中应用稀疏矩阵通过最 小优化准则解决光照、噪声问题，但是该算法的时间 复杂度很高，不能满足跟踪要求。 除了需要克服目标跟踪过程中环境易变的问 题，对遮挡中目标进行精确跟踪也十分关键。文献 ［７－９］分别提出了采用图像分割和贝叶斯网络方法 对遮挡中的目标进行跟踪。文献［６］则采用粒子滤波 算法，并依据目标的运动轨迹对遮挡中的目标位置 进行预测，以最小准则优化的系数作为后验知识，进 行粒子权值更新，但该算法的时间复杂度很高。 为了更好地克服运动目标跟踪中同时存在的 目标被遮挡和环境易变性问题，本文借鉴超平面逼 近跟踪算法的状态转移方法和归一化互相关匹配 算法具有的良好光照适应性和抗噪性以及粒子滤 波算法的强预测能力，提出一种新的基于仿射变换 状态转移与粒子滤波的模板匹配运动目标跟踪算 法。该算法具有优越的光照适应性、抗噪性、背景适 应性以及抗遮挡性能，能够实现更精确的运动目标 跟踪。 １ 算法设计与分析 本文提出的基于仿射变换状态转移与粒子滤 波的模板匹配算法是一种遍历过程，但又不同于传 统的遍历算法，主要包括学习过程（图１ａ）和跟踪过 程（图１ｂ）。在学习过程中，只选出目标模板附近一 组扰动模板并保存。跟踪过程分为未遮挡跟踪过程 和遮挡跟踪过程，在未遮挡跟踪过程（图１ｂ）中只需 要在该帧图像中取出上帧目标位置所在区域作为 预测模板，利用归一化互相关匹配算法选出学习过 程中最佳匹配扰动模板所对应的变换参数，通过文 献［２］的状态转移方法就可得到该帧图像中目标的 精确位置，与此同时，以归一化互相关系数作为后 验知识对粒子权值进行更新，统计目标的运动状 态，为遮挡中目标位置的预测做准备；而在遮挡跟 踪过程中，依据统计出的目标运动状态，利用粒子 滤波算法，预测出变换参数，依据同样的状态转移 方法得到目标的预测位置。关于算法的详细介绍见 下文。 ＬＩｍ．啪蜘・ 删Ｉ 啮☆ 图１本文算法示意图 １．１ 学习过程 如图ｌａ所示，取出目标模板，令目标模板的灰 度行向量为 ，坐标点集合为 （ 。，ｔ ，…，ｔ ），ｎ为 模板中点的个数，ｔ 点的坐标为（孙ｙｉ）；ｃ Ｔ， ）＝（厂 （ｔ ，ｔＡ） ｔ ，ｔＡ），… ｔ ， ））为在图像序列中的坐标 点集合，，（ Ｔ， ））为该区域的灰度行向量， 分别 为变换函数和仿射变换参数向量。设真实参数为 ｔＡｏ＊，即Ｉｒ＝Ｉ（ Ｔ， ）），在 附近选取 个扰动： ｌ，＝（ －， ｚ，…， ），与之对应的在真实目标位置附 近产生 个灰度模板，分别对 个灰度模板归一化 后记为日＝（，】’，，２’，…， ）。 令Ｃ。为 在图像序列中的真正坐标集合，即 Ｃｏ＝（ｊｒ， ￥），ｃ’为扰动 作用后的集合，即ｃ’＝ ， Ａｔｏ＊＋舢）。假设存在一个模板 ’在扰动 作用后的 集合为Ｃｏ＝Ｊ（Ｔ， ），且．厂可逆，则： ｒ＝ｆ－ （ｃ， ）－厂。 Ｔ， ）， ） （１） 即在 已知的条件下可求得模板 ’，而 ’在 变换参数向量 的变换下可以得到图像序列 中目标的真正位置。 １．２跟踪过程 跟踪过程由遮挡和未遮挡两个跟踪过程构 成，所以在进行跟踪之前需要进行遮挡判断。目 标模板的表面信息发生很大的变化认为是遮挡现 象［ｍ］，文献［１０—１１］依据该定义给出了判断遮挡 的方法，但是该算法需要额外的灰度差计算和进 行迭代运算，时间复杂度较大。本文采用归一化互 相关系数作为遮挡判定的标准，当最佳匹配模板 的归一化互相关系数小于一定阈值时判定为遮挡 现象。阈值的选取要大一点，因为每次遮挡预测之 后需要再一次进行遮挡判断，所以应保证未遮挡 跟踪过程的可靠性，具体的算法流程如下页图３ 所示。 １．２．１未遮挡跟踪过程 如图１ｂ所示，跟踪之前先对目标位置进行预 ・２３・ （总第３８—０３８６） 火力与指挥控制 ２０１３年第３期 测，为上帧图像中目标所任位置Ｃ’，此时变换参数 Ｊ｛ｊ 表示，则Ｃ’＝厂（Ｔ， ）。该区域的灰度向量为，（厂 （Ｔ，／ｚ）），归一化处理后的灰度向量记为 。利用归一一 化互相关 配算法选出学习过程最佳 配扰动模 板，由于已经对灰度进行了归一化处理，所以匹配 ∑ （１０） 算法可以简化为求取相关系数行向量Ｄ １ｔ￣１：系数最 大所对应的模板，其Ｉ｝１，）＝ ’ Ｈ。在ｙ中对应位置选 ｝１Ｊ扰动，标记为 ，即为预测位置到真实位置的变 换参数。 扰动参数 已知，南式（１）可以得到 ，此时 的变换参数为 ，所以该帧图像巾目标的真实位置 为： ？ ， ）＿／【Ｉ广 Ｔ， ）， ）， ） （２） １．２．２遮挡跟踪过程 遮挡中的目标跟踪是依据学习得到的目标运动 状态利用粒子滤波算法进行位置预测，假设目标的 状态序列为｛ ∈，ｖ１，观测序列为｛”；￡∈，ｖ｝。甄∈Ｒ 、 ¨∈Ｒｍ， 、 分别为状态向量和观测向量的维数 则贝叶斯滤波技术可以写为下面两个过程： ．预测： （ ｌ ）＝ｊ． （ ，｛ ， ） （一 ｌＹｔ：ｒ－Ｉ ｋ （３） 更新： ｆ）＝ ㈩ 序贯蒙特卡洛方法（ＳＭＣ：Ｓｅｑｕｅｎｔｉａｌ Ｍ‘ｍｔｅ Ｃａｒｌｏ Ｍｅｔｈｏｄ）ｉ 利片ｊ一组有限的粒子ｆ（ ，ｏ４：）； ∈￡｝近似 的解决了上述两个步骤， 为第ｉ个粒子的权值，，Ｊ 为粒子个数： ， （ ） ∑，ｏｉ ６（ ；） （５） ∞ｉｏｃｏ； （６） ｑ ｘ ；Ｉ ｘ￣１… ’ 式中ｑ（・）为建议性分布函数，在自举滤波 （Ｂｆｘ￣ｔｓｔｒａｐ Ｆｉｈｅｒ） 中 ｇ（ ｌ一 。，Ｙ，）＝，，（一ｌ ，．．） （７） 所 。Ｃ 。 ｐ（Ｙ，ｌ ） （８） 在本文算法巾，选择学习过程中的扰动参数向 量组 为粒子组｛ｘｌ；ｔ∈Ｌ｝，对应的权值为｛ｏ９１：；ｔ∈Ｌ｝， 初始值为 Ｉｌ＝Ｉ／Ｌ。权值的具体更新过程类似文献 ［６］，采用未遮挡跟踪过程中的归一化互相关系数Ｄ （ ２）作为后验知识进行更新，即： ．ｅｘｐ（ｆＪ（ｉ）） 一∑ ￣ｅｘ ｐ（Ｄｉ （＾）） （９） （则遮挡中目标位置的预测变换参数为： ・２４・ 图２部分归…‘化互相关系数 １．３算法流程图 首先是学习过程中扰动变化参数 的确定，似 设相邻两帧图像『１１目标位置变化不大，依据仿射变 换，通过ＸＹ轴分别放缩 个像素、错切Ⅳ 个像素、 旋转＋Ｎ３度以及平移［一Ｍ，＋，ｖ４］个像素来确定 的 大小，例如： ＝Ｎ２＝２、Ａ ＝２、Ｎ４＝１０。 的选择可以依 据目标的特性有所不同，如实验中汽车的跟踪，只 需要进行缩放和平移变换。 其次，遮挡中目标跟踪是依据其运动规律进行 预测，必然会出现误差，为了克服此缺点，每次预测 后，再进行阈值判断，“小于”则认为陔 域即为¨ 标 域，否则以此为候选区域，进行未遮挡跟踪过 程。算法的流程如图３所示。 取 模板、确定仿射参数 ．、 以及判遮挡阚 值￡、令ＩＪＪ一化互相关系数ｅｏｅｆｆ＝ｌ、确定扰 动向晕组ｙ以及对应的归一化灰度向 ｖ 、 …二／ Ｖ １ ｒ 粒子滤波算法预测【Ｉ｛标 ｌ取ｍ预测 域的 求ｌＪｌ】ｌ 位冒ｌ鑫数＆‘求Ｉ｝Ｉ预测 Ｉ一化互相关系数行向 Ｄ ｌ 位置的 Ｉ 化互相关系 数ｆ 向罱口 ，厂 ： 一 Ｉ在ｒ中选ｍ与ｍａｘ（，ｊ）所对应扰动酬 、 ：墩 一帧图像 标ｍ目标区域、计算此时的ｃｏｅｆｆ １１ Ｎ／ ／而附 支＼ ＼ 图３本文算法流稃 ２ 实验与分析 为了验证所提算法的有效性，本文在多种不同 的背景环境下，分别选择模拟目标的运动ｌ哥像数据和 真实目标的运动图像序列，将提出的基于新模板匹 配的运动目标跟踪算法（以下简称ＮＴＭＴＴ算法）与
