第４１卷第４期 ２０１４年４月 光电工程 Ｏｐｔｏ—Ｅｌｅｃｔｒｏｎｉｃ Ｅｎｇｉｎｅｅｒｉｎｇ Ｖｏ１．４１，ＮＯ．４ Ａｐｒｉｌ，２０１４ 文章编号：１００３—５０１ｘ（２０ｌ４）０４—０００卜０８ 一种改进的实时压缩跟踪算法 （１．中国科学院光电技术研究所，成都６１０２０９； ２．中国科学院大学，北京１０００４９） 钟 权 一，周 进 ，吴钦章 ，王 辉 ，雷 涛 摘要：压缩跟踪算法作为一种新的算法，具有简单、高效、实时的优点，但该算法依然存在缺陷。首先，在复杂 背景或有遮挡等情况下，容易较快的引进误差；其次，跟踪窗１５＇保持不变，使得不能正确跟踪目标位置且不能准 确更新正负样本；最后，搜索样本数目大，导致跟踪速度不理想。针对这些问题，利用前后帧跟踪点的直方图对 比来判断遮挡的发生，并自适应的改变更新系数；采用在原算法最优匹配点周围小范围多尺度搜索更优位置的方 法，来适应目标尺寸的变化；引入粗精跟踪策略，在不同阶段使用不同数量的子特征集进行匹配，以筛选样本、 减少计算量。这些改进避免了算法缺陷导致的跟踪失败，提高了跟踪效率。实验证明，改进后的算法比原算法具 有更好的鲁棒性且跟踪速度更快。 关键词：压缩跟踪算法；自适应；模板更新；压缩感知 中图分类号：ＴＰ３９１．４ 文献标志码：Ａ ｄｏｊ：１０．３９６９￣．ｉｓｓｎ．１００３—５０１Ｘ．２０１４．０４．００１ Ａｎ Ｉｍｐｒｏｖｅｄ Ｒｅａｌ—ｔｉｍｅ Ｃｏｍｐｒｅｓｓｉｖｅ Ｔｒａｃｋｉｎｇ ＺＨＯＮＧ Ｑｕａｎ ，ＺＨｏＵ Ｊｉｎ ，ＷＵ Ｑｉｎｚｈａｎｇ ，ＷＡＮＧ Ｈｕｉ ，ＬＥＩ Ｔａｏ （１．Ｉｎｓｔｉｔｕｔｅ ｏｆＯｐｔｉｃｓ ａｎｄＥｌｅｃｔｒｏｎｉｃｓ，ＣｈｉｎｅｓｅＡｃａｄｅｍｙ ｏｆＳｃｉｅｎｃｅｓ，Ｃｈｅｎｇｄｕ ６１０２０９，Ｃｈｉｎａ； ２．ＵｎｉｖｅｒｓｉｔｙｏｆＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ １０００４９，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｒｅａｌ・ｔｉｍｅ ｃｏｍｐｒｅｓｓｉｖｅ ｔｒａｃｋｉｎｇ ｗａｓ ａ ｓｉｍｐｌｅ ａｎｄ ｅｆｆｅｃｔｉｖｅ ｔｒａｃｋｉｎｇ ａｌｇｏｒｉｔｈｍ．Ｈｏｗｅｖｅｒｔｈｅｒｅ ｗｅｒｅ ａ ｎｕｍｂｅｒ ，ｏｆ ｐｒｏｂｌｅｍｓ ｗｈｉｃｈ ｎｅｅｄ ｔｏ ｂｅ ａｄｄｒｅｓｓｅｄ．Ｆｉｒｓｔ ｏｆ ａｌｌ，ｉｔ ｗａｓ ｅａｓｙ ｔｏ ｉｎｔｒｏｄｕｃｅ ｅｒｒｏｒｓ ｄｕｅ ｔｏ ｆａｃｔｏｒｓ ｓｕｃｈ ａｓ ｏｃｃｌｕｓｉｏｎ ａｎｄ ｃｌｕｔｔｅｎ Ｓｅｃｏｎｄｌｙ，ｉｔ ｃｏｕｌｄｎ’ｔ ｕｐｄａｔｅ ｔｈｅ ｐｏｓｉｔｉｖｅ ａｎｄ ｎｅｇａｔｉｖｅ ｓａｍｐｌｅｓ ａｃｃｕｒａｔｅｌｙ ｗｈｉｌｅ ｕｓｉｎｇ ｆｉｘｅｄ ｔｒａｃｋｉｎｇ ｗｉｎｄｏｗＡｔ ．ｌａｓｔ，ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｔｅｓｔｉｎｇ ｓａｍｐｌｅｓ ｗａｓ ｔｏｏ ｌａｒｇｅ，ｗｈｉｃｈ ａｆｆｅｃｔｅｄ ｔｈｅ ｓｐｅｅｄ ｏｆ ｔｒａｃｋｉｎｇ．Ｔｈｅ ｏｃｃｌｕｓｉｏｎ ｗａｓ ｃｈｅｃｋｅｄ ｂｙ ｃｏｍｐａｒｉｓｏｎ ｂｅｔｗｅｅｎ ｃｏｎｓｅｃｕｔｉｖｅ ｆｒａｍｅｓ’ｈｉｓｔｏｇｒａｍｓ，ａｎｄ ｔｈｅ ｃｏｅｆｉｃｉｅｎｔ ｃａｎ ｂｅ ａｌｆｓｏ ｕｐｄａｔｅｄ ａｄａｐｔｉｖｅｌｙ ｂｙ ｔｈｅ ｃｏｍｐａｒｉｓｏｎ ｒｅｓｕｌｔ．Ｗｅ ｓｅａｒｃｈｅｄ ｆｏｒ ｍｏｒｅ ｓｐｅｃｉｆｉｅｄ ａｒｅａｓ ｗｉｔｈ ｍｕｌｔｉ—ｓｃａｌｅｓ ｔｏ ｆｉｎｄ ｏｕｔ ｔｈｅ ｂｅｓｔ ｍａｔｃｈｉｎｇ ｐｌａｃｅａｎｄ ｔｏ ，ｈａｎｄｌｅ ｓｃａｌｅ ｃｈａｎｇｅ ｏｆ ｔｈｅ ｔａｒｇｅｔ ｏｎ ｔｈｅ ｂａｓｉｓ ｏｆ ｔｈｅ ｏｒｉｇｉｎａｌ ａｌｇｏｒｉｔｈｍ’Ｓ ｔｒａｃｋｉｎｇ ｒｅｓｕｌｔ．Ｔｈｅ ｄｉｆｅｒｅｎｔ ｎｕｍｂｅｒｓ ｏｆ ｓｕｂ ｆｅａｔｕｒｅｓ ｓｅｔｓ ｗｅｒｅ ｕｔｉｌｉｚｅｄ ｔｏ ｉｌｆｔｅｒ ｔｈｅ ｔｅｓｔｉｎｇ ｓａｍｐｌｅｓ．Ｉｎ ｔｈａｔ ｃａｓｅ，ｔｈｅ ｓｐｅｅｄ ｏｆ ｔｒａｃｋｉｎｇ ｐｒｏｃｅｓｓ ｗｏｕｌｄ ｂｅ ｉｍｐｒｏｖｅｄＴｈｅ ．ｓｔｒａｔｅｇｉｅｓ ｗｅ ｐｒｏｐｏｓｅｄ ｗｏｕｌｄ ｉｍｐｒｏｖｅ ｔｈｅ ｏｒｉｇｉｎａｌ ａｌｇｏｒｉｔｍ’ｈＳ ｐｅｒｆｏｒｍａｎｃｅ ｔｏ ａｖｏｉｄ ｔｈｅ ｆａｉｌｕｒｅ ｏｆ ｔｒａｃｋｉｎｇ．Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｉｎｄｉｃａｔｅ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｃａｎ ｒｕｎ ｉｎ ｒｅａｌ・－ｔｉｍｅ ａｎｄ ｐｅｒｆｏｒｍ ｆａｖｏｒａｂｌｙ ａｇａｉｎｓｔ ｓｔａｔｅ．．ｏｆ－ｔｈｅ．．ａｒｔ ａｌｇｏｒｉｔｈｍｓ ｏｎ ｃｈａｌｌｅｎｇｉｎｇ ｓｅｑｕｅｎｃｅｓ ｉｎ ｔｅｒｍｓ ｏｆ ｅｆｉｃｉｅｎｃｙ，ａｃｃｕｒａｃｙ ａｎｄ ｆｒｏｂｕｓｔｎｅｓｓ． Ｋｅｙ ｗｏｒｄｓ：ｃｏｍｐｒｅｓｓｉｖｅ ｔｒａｃｋｉｎｇ；ａｄａｐｔｉｖｅ；ｔｅｍｐｌａｔｅ ｕｐｄａｔｉｎｇ；ｃｏｍｐｒｅｓｓｉｖｅ ｓｅｎｓｏｒ ０ 引 言 目标跟踪在机器人视觉和视频监控领域有着广泛的应用。如何对视频序列中的感兴趣区域进行有效的 收稿日期：２０１３—０６—２８；收到修改稿日期：２０１３—０８—１５ 基金项目：国家８６３高技术计划资助项目 作者简介：钟权（１９８６一），ｇ（ｆ２Ｎ），湖北随州人。博士研究生，主要从事信息与信号处理方面的研究工作。Ｅ－ｍａｉｌ：ｉｏｅｚｈｑ＠１２６．ｅｏｍ。 通信作者：吴钦章（１９６４－），男（汉族）。博士生导师，主要从事信息与信号处理、机器视觉、人工智能方面的研究。Ｅ－ｍａｉｌ：ｗｕｑｚ＠１２６．ｃｏｍ。 ｈｔｔｐ：／／ｗｗｗ，ｇｄｇｃ ａＣ，ｃｒｌ ２ 光电工程 跟踪，是计算机视觉中一个有挑战性的课题。 压缩域跟踪是目前跟踪问题研究的一个前沿方向。Ｋａｉｈｕａ Ｚｈａｎｇｔｌｌ对实时压缩域跟踪算法进行了详尽的 描述，指出了该算法在处理一般跟踪问题时的优势，为目标跟踪的研究提供了一个新的方向。作为一种简 单、高效、鲁棒的算法，压缩跟踪算法必将在目标跟踪算法领域中占有一席之地。但该算法依然存在一些 缺陷。 首先，压缩跟踪算法的更新过程采用固定更新的模式，即在跟踪前设定学习速率，在每一帧找到跟踪 点之后，根据当前帧压缩域内的正负样本的统计特征及前一帧的正负样本的模型参数来更新模型参数。通 过理论分析得知，压缩跟踪算法的更新过程较为盲目，它不仅容易引进误差和噪声，而且容易遗忘以前学 习到的样本。本文针对这个问题提出了改进的模板更新算法，能够自适应的根据目标的变化速度调整学习 率，同时可以判断遮挡的发生。实验证明，该算法可以很好的避免因为背景、光照、角度等原因而引进的 误差。 其次，压缩跟踪算法的跟踪窗口在跟踪过程中保持不变，但是目标的大小显然并不是固定不变的。当 目标变大时，负样本的采集太靠近目标区域，使得背景和目标的可区分度降低；当目标变小时，更是有部 分背景信息被引入到参数模型中，从而导致跟踪漂移，甚至是跟踪失败。针对这种情况提出一种新的模板 采集算法，不仅能够适应目标的尺寸变化，而且使得跟踪的精度更高。 第三，通过实验发现，原始算法的跟踪速度并不具备优势。针对该问题，提出一种粗精跟踪的策略， 以减少计算量，提高跟踪速度。 本文第一节简单介绍原始在线压缩跟踪（ｃＴ）算法。第二节阐述了对在线压缩跟踪算法的改进。第三节 是实验部分。第四节给出了本文的结论。 １压缩跟踪算法 压缩跟踪算法是一种将实际图像投影到压缩域空间，并在压缩域内提取目标和背景特征的二分类算 法。该算法简单、高效，可以预见将会越来越多地被用于目标跟踪领域中。 １．１算法概述 压缩跟踪算法是一种基于压缩感知理论［２－３］的跟踪算法。压缩感知理论指出，对于高维图像空间中的数 据 ∈贸 要将其投影到低维空间ｌ＇∈９ｔ”上，可以使用随机矩阵Ｒ∈锨 ，即： ＝Ｒｘ （１） 其中 ＜＜ｍ。理想情况下，希望矩阵 能够大致保持原信号点对之间距离。Ｊｏｈｎｓｏｎ—Ｌｉｎｄｅｎｓｔｒａｕｓｓ推论 指出，如果向量空间中的两点投影到一个随机选择的合适的高维子空间，那么他们之间的距离得以保持的 概率很高。Ｂａｒａｎｉｕｋ等人 证明了随机矩阵满足Ｊｏｈｎｓｏｎ—Ｌｉｎｄｅｎｓｔｒａｕｓｓ推论，且在压缩感知领域中同样满足 等距性质。因此，如果式（１）中的随机矩阵满足Ｊｏｈｎｓｏｎ—Ｌｉｎｄｅｎｓｔｒａｕｓｓ推论，且信号ｘ是可压缩的（如音频或 者图像），那么可以有较高的概率从向量 中以最小误差来重建 。可以确保，向量ｌ，几乎保存了向量 的 所有信息。该理论使得通过低维随机投影信号来分析高维信号成为现实。压缩跟踪算法使用的随机矩阵是 一个稀疏矩阵，该矩阵不但满足Ｊｏｈｎｓｏｎ．Ｌｉｎｄｅｎｓｔｒａｕｓｓ推论 Ｊ，而且可以在实时跟踪中进行有效地计算。 其生成规则为 一＝４ｓ×｛Ｉ０ Ｐ＝１一（１／ ） ｌ ｐ：１／２ —ｆ１ ｐ＿１／２ （２） 式中：Ｐ代表 取某值的概率，压缩跟踪算法中设定Ｓ：ｍ／４。分析可知，在满足Ｊｏｈｎｓｏｎ－Ｌｉｎｄｅｎｓｔｒａｕｓｓ 推论的前提下，当压缩矩阵中ｒｏ．＝０的概率越大时，所能避免的计算就越多、存储量的要求也越低。 压缩跟踪算法实际上使用的是与Ｈａａｒ．１ｉｋｅ特征 日似的相对强度差异特征。对于每一个采集到的样本， 经过多尺度平滑滤波（矩形滤波器）后，连接在一起，生成一个高维多尺度图像特征向量（即各图像按照尺度 大小、左右、上下顺序将像素连接在一起）。对于这样的高维（维数可达到１０。～１０ ）特征，使用稀疏随机矩 ｈｔｔｐ：／／ｗｗｗ，ｇｄｇｃ．ａＣ ｃｒｌ 第４１卷第４期 钟权，等：一种改进的实时压缩跟踪算法 ３ 阵将其投影到低维中去。由前所示的随机矩阵的生成规则可知，随机矩阵实质上是多次随机选择了图像中 的某些像素组成了一个低维的新序列（即压缩特征），压缩特征计算相对强度差异的方法与Ｈａａｒ－ｌｉｋｅ特征相 似。 １．２构建和更新分类器 对每一个样本Ｚ∈婀 ，其低维表示’，＝（ 一， ） ∈贸”，有 ＜＜ｍ。假定ｌ，中所有的元素都是分 布的，使用朴素贝叶斯分类器 对它们进行模型化： ｍ 假定先验概率Ｐ（Ｙ＝１）＝Ｐ（Ｙ：０），其中Ｙ∈｛０，１｝是二值变量，用来表示样本的正负。Ｄｉａｃｏｎｉｓ和 Ｆｒｅｅｄｍａｎ［８］指出，高维随机向量的随机投影几乎总是符合高斯分布的。因此，在分类器Ｈ（ｖ）中的条件分布 ｐ（ｖ １ Ｙ＝１）和ｐ（ｖ ｌ Ｙ＝０）被假定为符合参数（ ， ， ， ）的高斯分布。其中： ｌｐ（ｖ ｌＹ＝１）～Ⅳ（ ， ） Ｉｐ（ｖ ＩＹ＝０）～Ⅳ（ ， ） 式中的尺度参数是增加更新的。 ∑ Ｏ ～一、 人 一、｜ 一 一 、Ｊ ～… 一 七一√ （ ） ＋（１一 ）（ ） ＋２（１一 ）（ 一 ） 其中 ＞０是学习参数。 压 ， （５） 一 上面的等式是通过最大似然估计推导得到。该式也可以被看成分类器中正负样本的模板，新采集到的 样本的特征值正是通过代入到式（３）、式（４）中，来计算分类器响应值。 １．３算法流程 给定初始帧目标位置和尺度，对于第ｔ帧图像，算法执行四个步骤： １）采样一个子图像集Ｄ ＝｛Ｚ ｌｌＩ（ｚ）一， ｌＩ＜ ｝，其中，Ｈ是上一帧（即（ 一１））的跟踪位置，在低维空间中 提取它们的特征。 ２）使用分类器对每个特征向量ｖ（ｚ）进行分类，通过计算最大分类响应来找到跟踪位置，，。 ３）分别采样两个子图像集合Ｄ ＝｛ｚ ｌＩｔ（ｚ）一， Ｉ１＜ ｝及Ｄ ：｛ｚ ＜ｌｌＩｔ（ｚ）一， Ｉ＜ ｝，其中 ＜ ＜ 。 ４）在上述两个样本集合中提取特征，然后更新分类器参数。 由此得到跟踪位置『，和更新后的分类器参数。 ２压缩跟踪算法的改进 本文在三个方面对在线压缩跟踪算法进行了改进，使得算法能够适应目标被遮挡及算法不能适应目标 尺寸变化的问题，同时提高了算法的处理速度。具体算法流程如图１。 图１中，字体和方框加粗的部分为改进后的算法所特有的。 ２．１对遮挡的处理 通过对上文中分类器更新算法的研究可知，该算法存在一定的盲目性，即该算法假定跟踪算法在每一 帧得到的跟踪点即是“最正确”的位置。该假定在大多数情况下是正确的，但是一旦目标被遮挡、背景较为 复杂或者目标外观发生较大变化时，“最正确”的跟踪点和模板差别就会太大，跟踪可能发生漂移，噪声和 误差通过更新过程即被引入到参数模型中，在后续的跟踪过程中，如果没有外界干涉，这种漂移会逐步积 累，从而导致跟踪失败。为了避免这个问题，本文提出一种控制策略，使得算法能够自适应的选择学习参 ｈｔｔｐ：／／ｗｗｗ ｇｄｇｃ．ａｃ．ｃｒｌ ４ 光电工程 数，且在遮挡严重或者新的模板存在可疑情况时，不更新模型参数。 图１算法流程图 Ｆｉｇ １ Ｆｌｏｗ ｃｈａｎ 对式（５）进行分析，令： 』Ｉ ： ）（ ） ＝（ ＋６ 代入式（５）中，有： ｆ７１ 、 （８） ｛ ４一ｌ √（ ） ＋（１一 ）６十 （１—２）ｄ Ｉ＋（１—２）ｄ 其中：ｄ和６分别是更新模板参数和原模板参数均值和方差的差值。 由式（５）、式（８）可知，新的模型参数由两部分构成：一部分是前一帧所使用的模型参数，它是上一帧的 信息，代表了目标的稳定性；另一部分是使用当前帧跟踪点周围采集到的正负样本学习得到的新的模型参 数，这些新信息代表了目标的改变。新旧模型参数通过学习率线性组合得到更新后的模型参数。压缩跟踪 算法中，更新模型参数的学习率保持不变，是一个经验值。实验结果表明，在不同的视频序列上，需要修 改学习率以适应视频中目标变化的快慢。 对于学习率 ∈［０，１］而言，当 越大时，表明更新后的参数和更新前更接近，在目标变化较慢时，需 要大的学习率；反之，当 越小时，表明更新后的参数与当前帧得到的参数更接近，在目标变化较快时， 需要小的学习率。 相对于压缩跟踪算法中的固定的学习率，本文提出一种适应目标变化的学习率，可以根据目标的变化 快慢实时调整学习率的大小。 对于每一个样本ｚ∈ ，可以使用归一化直方图来作为跟踪图像的辅助表达。本文使用Ｂｈａｔｔａｃｈａｒｙｙａ 距离 来计算两幅图像之间的距离。即： ∑ √ｐ ｇ （９） 比较的两个对象分别是前一帧得到的跟踪图像和当前帧的匹配图像。匹配度越高，表明前后两帧的跟 踪图像比较相似，反之，前后两帧的跟踪图像差别较大。设定一个阈值 ，当 ≥Ｔ时，接受更新；反之， 当 ＜Ｔ时，表明新的跟踪点与上一帧的匹配图像差距太大，可能有遮挡等情况发生，此时不更新模型参 数，以避免在模型参数中引入噪声。新的学习率由下式计算得到： ＝ ／ｐ （１０） 其中： 是给定的学习率， ∈（０，１］是两幅图像之间的Ｂｈａｔｔａｃｈａｒｙｙａ距离。由上述讨论可知， 越大时， 表明前后两帧目标图像越相似，需要小的更新率； 越小时，表明前后两帧目标图像相似度小，需要大的 更新率。通过该值的设定，可以更有效地、自适应地控制模型参数的更新速率，满足图像变化速度快慢的 ｈｔｔｐ：／／ｗｗｗ，ｇｄｇｃ ａｅ ｃｒｌ 第４１卷第４期 钟权，等：一种改进的实时压缩跟踪算法 ５ 要求。 此处只需保存上一帧匹配图像的直方图和计算当前帧最佳匹配图片的直方图，在计算量和存储量上并 没有大的改变，却改进了算法对遮挡情况的处理能力。 ２．２对尺寸变化的处理 压缩跟踪算法不能处理目标尺寸的问题，即目标跟踪窗口的大小保持不变。通过分析可知，这种算法 在目标变大时影响负样本的采集，在变小时影响正样本的采集，而分类器的模型参数正是通过对正负样本 的计算得到。所以，为了避免由目标尺度变化带来的跟踪漂移问题，本文提出一种控制策略，可以自适应 调整跟踪窗口的大小。 由上文的算法描述可知，在处理每帧图像时，有两次涉及样本采集的过程。一是从上一帧的跟踪点位 置开始，搜索目标可能存在的区域，找到当前帧目标最可能出现的位置；二是跟踪结束后，在当前帧跟踪 点周围采集正负样本。两次采集得到的样本尺寸保持不变，均为第一帧人工给定的大小。本文只针对第一 部分进行尺寸控制，第二部分更新过程使用的模板尺寸正是当前帧跟踪点位置的新的尺寸。假定当前帧的 跟踪尺寸与目标尺寸吻合、且跟踪位置准确，则更新过程并没有引入噪声和误差。因此，该策略可以满足 目标大小的自适应变化。 根据上一帧给定的尺寸和模板搜索到新的目标位置，在该位置附近选取多种尺寸的模板，计算这些模 板相应的匹配值，从而得到当前帧最终的最优匹配图像。与使用滑窗法 得到待匹配图像及在匹配之前得 到大量待匹配图像的方法相比，本文提出的算法极大地减少了待匹配样本的数量，同时并未降低算法的跟 踪精度。 该算法基于这样一个事实，即目标在跟踪过程中，尺寸不会产生剧烈变化。所以，待匹配图像的尺寸 可以分别在上、下、左、右四个方向上向内、外伸缩长宽的１／１２个距离（如图２），而不用逐像素滑动窗口。 除去原始尺寸，可以得到３６个变尺寸的待匹配图像，对这些图像进行匹配，可以得到新的最优值，该匹配 位置和跟踪尺寸即为新的跟踪点和跟踪窗ｌＺｌ。该算法虽然增加了待匹配样本的数目，但是与同类算法 动 辄上万的待匹配样本数目相比，增加的样本数目显然是微不足道的。 ｝ Ｉ Ｈ Ｉ ＨＩ１２ ｌＩ ： Ｉ Ｈ／１２ Ｉ 。 图２尺寸变化示意图 Ｆｉｇ．２ Ｔｈｅ ｄｉａｇｒａｍ ｏｆｓｃａＪｅ ｃｈａｎｇｉｎｇ 当然，放缩尺寸的设定与跟踪目标在尺度上的变化率有关，该尺寸的设定越接近跟踪目标尺度的变化 率，则越能精确跟踪到目标位置；反之，容易引进背景误差。但是总体性能不会比改进前差。 当采样得到的样本尺寸发生变化时，从样本中提取的高维特征维数与随机稀疏矩阵的列数不同，不能 做矩阵乘法。为了解决两者相乘的问题，可采取归一化采样样本大小的方法，或者根据样本的尺寸改变随 机稀疏矩阵列数的方法。由于前者涉及到图像像素的插值和采样，操作不便且计算量较大，故采用改变随 机稀疏矩阵列数的方法。由前文的分析可知，随机稀疏矩阵中的非零项实质上是对采样区域中的像素进行 采样，为了使前后两帧图片中的采样像素有可比性，像素采样与采样区域的相对位置不能改变。所以，随 机稀疏矩阵中非零项的位置需根据采样目标尺寸的情况进行改变。实际操作中，随机稀疏矩阵不仅记录了 随机生成的权值，也记录了像素采样点的位置，通过在长度和宽度两个方向上，得到新目标区域和原目标 ｈｔｔｐ：／／ｗｗｗ．ｇｄｇｃ．ａｃ．ＣＩ３ ６ 光电工程 ２０１４年４月 区域尺寸上的比值，改变随机矩阵中新的像素采样点的位置。因为新检测的尺寸有限且较固定，故改变了 尺寸的新稀疏随机矩阵也可以离线生成。新维度的随机稀疏矩阵的生成是在原随机稀疏矩阵的基础上做线 性变换，并没有产生大量的计算量，使得算法在提高跟踪性能的同时，不降低实时性。由此给出新跟踪算 法，使得该算法能够适应目标尺寸的变化。 ２．３粗精跟踪算法 原始算法的跟踪速度并不是十分理想，原因在于算法在目标窗口区域搜索疑似目标时，采集的样本数 （依赖于搜索窗口的大小）、各样本的特征数目（一般设定为５０）、各特征的计算次数（一般设定为２．４次）的乘 积过大，从而影响了跟踪速度。本文提出一种粗精跟踪策略，对所有采集的样本使用特征集中的部分特征 进行粗跟踪，这些子特征可以筛选出一部分匹配度较高的样本。对于这些通过了粗跟踪的样本采用精跟踪 来计算匹配值，从而得到最终的匹配图片，即跟踪点。在本文中，粗跟踪按均匀采样选择特征数目１／５的 子特征集，得到样本数ｌ／３的较优样本，对这些样本采用所有特征进行精跟踪，从而得到最优的匹配位置（该 位置为模板尺寸变化前的最优位置）。 对于计算次数 而言，原算法计算次数总计为 Ｓ＝ＡＸＢＸＣ （１１） 其中： 为采集到的样本数； 为特征集数目；Ｃ为各特征的计算次数。 新算法计算次数总计为 Ｂ＝ ５ ３ｘｃ＋争 × ｃ： ×１ ５ ×Ｃｃ、 ２ 可知，新算法比原算法降低了近一半的计算量，其中，子特征集数目的选择及筛选得到的最终样本数 目可以根据实际需要分配比例。子特征集选择的特征数目较多，则粗跟踪精度较高，那么筛选得到的样本 数目就可以相应减少；反之，子特征集选择的特征数目较少，则粗跟踪精度较低，那么筛选得到的样本数 目就要相应增加。 更进一步分析可知，除了两次粗精串行跟踪，还可以采用不同的子特征集，多次、并行跟踪。实验结 果表明新的算法在跟踪精度不变的情况下，跟踪速度得到了提高。 ３实验及结论分析 改进的压缩跟踪算法所使用的特征本质上来说是一种纹理特征，所以，在跟踪开始时，选取合适的区 域进行跟踪是很重要的。本文选取一组行人序列来测试改进前及改进后算法的跟踪效果，该序列来源于公 共测试集，存在短时遮挡，背景较复杂。 如图３所示，分别是对该序列中第１、１６、４６、４７、７６帧的跟踪结果。两种算法对视频序列中除上述 帧外的其他帧的跟踪效果类似，原因在于目标的变化不大、背景影响较小。而文中所选择的几帧如第ｌ６ 帧（摄像机存任明显的抖动）、第４６、４７帧（白衣女子大部分被蓝衣女子遮挡，即目标发生明显变化）、第７６ 帧（白衣女子几乎被遮挡）进行跟踪时，两种算法的结果有较为明显的差异。原始算法在这些情况发生时， 很容易引入误差，从而导致跟踪失败。而使用改进后的算法后，这种因背景影响及遮挡影响而造成的跟踪 失败会极大地减轻。 本文选取一组雪地飞机起飞序ＹＯ（图４）来测试改进前及改进后算法对目标尺寸变化的跟踪效果，该序列 来源于网络。 可以看出原算法和改进的算法在长时间的跟踪过程中跟踪效果有所差异。原算法在处理尺寸问题上表 现的优势并不明显，原因在于算法所使用的特征是纹理特征，其对目标区域的大小变化并不敏感。但是， 改进后的算法显示了其在精确跟踪方面的优势，即目标跟踪模块在获得与上一帧给定的尺寸相同的最优位 置后，在该位置进一步以不同尺寸搜索，从理论上获得比该位置更优的区域。所以，改进后的算法在精度 上比原算法更优异，且同时具有适应目标尺寸变化的能力。而模板尺寸的改变策略使得它不会因为噪声影 响而剧烈变化，增加了模板尺度更新的稳定性。 ｈｔｔｐ：／／ｗｗｗ．ｇｄｇｃ。ａＣ，Ｃｎ ８ 光电工程 ２０１４年４月 ４总结 本文针对压缩跟踪算法中模型参数更新的盲目性问题，提出了一种简单的控制策略，使得算法在目标 被疑似遮挡、背景较复杂的情况下，暂时停止更新，以避免噪声和误差被引入到目标模型参数中。并根据 前后两帧跟踪点位置的图像差异来实时更新模型参数的学习率，以适应目标变化的快慢。针对原始算法不 能适应目标尺寸变化的情况，提出了一种新的模板采集算法，不仅能够适应目标的尺寸变化，而且使得跟 踪的精度更高。针对跟踪速度的问题，提出一种粗精跟踪的策略，可以有效减少计算量，提高跟踪速度。 文中所提到的样本筛选策略及尺寸更新策略具有启发性意义，可以在类似的使用特征集的相关算法中发挥 作用。文章中对特征集中特征数目的选择是一个经验值，而该值对跟踪效果有极大的影响，如何正确的选 择特征集的数目是将要继续解决的问题。实验结果表明，该算法对目标外观变化的快慢及对复杂背景和遮 挡有较好的跟踪效果。 参考文献： ［１］ＺＨＡＮＧ Ｋａｉｈｕａ，ＺＨＡＮＧ Ｌｅｉ，ＹＡＮＧ Ｍｉｎｇ—Ｈｓｕａｎ．Ｒｅａｌ—Ｔｉｍｅ Ｃｏｍｐｒｅｓｓｉｖｅ Ｔｒａｃｋｉｎｇ［ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １２ｔｈ Ｅｕｒｏｐｅａｎ ｃｏｎｆｅｒｅｎｃｅ ｏｎ ＣｏｍｐｕｔｅｒＶｉｓｉｏｎ，Ｆｌｏｒｅｎｃｅ，ｈａｌｙ，Ｏｃｔ ８－１１，２０１２，３：８６６－８７９ ［２］Ｄｏｎｏｈｏ Ｄ．Ｃｏｍｐｒｅｓｓｅｄ ｓｅｎｓｉｎｇ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ（Ｓ００１８－９４４８），２００６，５２：１２８９－１３０６． ［３】Ｃａｎｄｅｓ Ｅ，Ｙａｏ Ｎｅａｒ ｏｐｔｉｍａｌ ｓｉｇｎａｌ ｒｅｃｏｖｅｒｙ ｆｒｏｍ ｒａｎｄｏｍ ｐｒｏｊｅｃｔｉｏｎｓ ａｎｄ ｕｎｉｖｅｒｓａｌ ｅｎｃｏｄｉｎｇ ｓｔｒａｔｅｇｉｅｓ［Ｊ】．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ（Ｓ００１８－９４４８），２００６，５２：５４０６——５４２５． ［４ Ａｃ４］ｈｌｉｏｐｔａｓ Ｄ．Ｄａｔａｂａｓｅ—ｆｒｉｅｎｄｌｙ ｒａｎｄｏｍ ｐｒｏｊｅｃｔｉｏｎｓ：Ｊｏｈｎｓｏｎ—Ｌｉｎｄｅｎｓｔｒａｕｓｓ ｗｉｔｈ ｂｉｎａｙ ｒｃｏｉｎｓ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｓｙｓｔｅｍ ＳｃｉｅｎｃｅｓｆＳ００２２一ｏｏｏｏ），２００３，６６：６７１—６８７． ［５］Ｂａｒａｎｉｕｋ Ｒ，Ｄａｖｅｎｐｏｒｔ Ｍ，ＤｅＶｏｒｅ Ｒ，ｅｔ ａ１．Ｗａｋｉｎ Ｍ．Ａ ｓｉｍｐｌｅ ｐｒｏｏｆｏｆｔｈｅ ｒｅｓｔｒｉｃｔｅｄ ｉｓｏｍｅｔｒｙ ｐｒｏｐｅｒｔｙ ｆｏｒ ｒａｎｄｏｍ ｍａｔｒｉｃｅｓ ［Ｊ］．Ｃｏｎｓｔｒｕｃｔｉｖｅ Ａｐｐｒｏｘｉｍａｔｉｏｎ（Ｓ０１７６—４２７６），２００８，２８：２５３－２６３． 【６］Ｂａｂｅｎｋｏ Ｂ，Ｙａｎｇ Ｍ Ｈ，Ｂｅｌｏｎｇｉｅ Ｓ．Ｒｏｂｕｓｔ ｏｂｊｅｃｔ ｔｒａｃｋｉｎｇ ｗｉｔｈ ｏｎｌｉｎｅ ｍｕｌｔｉｐｌｅ ｉｎｓｔａｎｃｅ ｌｅａｒｎｉｎｇ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ ＩｎｔｅＩＩｉｇｅｎｃｅ（Ｓ０１６２—８８２８），２０１ １，３３（８）：１６１９—１６３２． ［７］Ｎｇ Ａ，Ｊｏｒｄａｎ Ｍ．Ｏｎ ｄｉｓｃｒｉｍｉｎａｔｉｖｅ ＶＳ．ｇｅｎｅｒａｔｉｖｅ ｃｌａｓｓｉｉｆｅｒ：ａ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｌｏｇｉｓｔｉｃ ｒｅｇｒｅｓｓｉｏｎ ａｎｄ ｎａｉｖｅ ｂａｙｅｓ［Ｊ］．Ｎｅｕｒａｌ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ（Ｓ２２４９—７１ ｌＯ），２００２，５２：８４１——８４８． 【８］Ｄｉａｃｏｎｉｓ Ｐ，Ｆｒｅｅｄｍａｎ Ｄ．Ａｓｙｍｐｔｏｔｉｃｓ ｏｆｇｒａｐｈｉｃａｌ ｐｒｏｊｅｃｔｉｏｎ ｐｕｒｓｕｉｔ［ＪＪ．ＴｈｅＡｎｎａｌｓ ｏｆＳｔａｔｉｓｔｉｃｓ（Ｓｏ０９０—５３６４），１９８４，ｌ２（３）： ２２８，一２３５． ［９］Ｓｗａｉｎ Ｍ Ｊ，Ｂａｌｌａｒｄ Ｄ Ｈ．ＣｏｌｏｒＩｎｄｅｘｉｎｇ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆＣｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ（Ｓ０９２０—５６９１），１９９１，７（１）：１１－３２． 【１０】Ｋａｌａｌ Ｚ，Ｍｉｋｏｌａｊｃｚｙｋ Ｋ，Ｍａｔａｓ Ｊ．Ｔｒａｃｋｉｎｇ Ｌｅａｒｎｉｎｇ Ｄｅｔｅｃｔｉｏｎ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ ＩｎｔｅＩｌｉｇｅｎｃｅ（Ｓ０１６２—８８２８），２０１１，６（１）：１－１４． ｈ￡Ｌｐ：／／ｗｗｗ ｇｄｇｃ ａＣ ｃｎ
