均值漂移跟踪算法

1、在无人驾驶车辆测试平台上利用均值漂移跟踪算法实现移动图像的实时跟踪Benjamin Gorry, Zezhi Chen, Kevin Hammond, Andy Wallace, and Greg Michaelson摘要：本文描述了一种用来跟踪移动目标的新型计算机视觉算法，该算法是作为 无人驾驶车辆长期研究的一部分而被发展的。我们将介绍在视频序列中利用变量核 进行跟踪的研究结果。其中，均值漂移目标跟踪算法是我们工作的基础；对于一个 移动目标，该算法通常用来在初始帧中确定一个矩形目标窗口，然后利用均值漂移 分离算法处理该窗口中的数据，将跟踪目标从背景环境中分离出来。我们并没有使 用标准的Epa

2、nechnikov内核，而是利用一个倒角距离变换加权内核来提升目标表 示和定位的精度，利用Bhattacharyya系数使RGB色彩空间中两个分布之间的距离 最小化。实验结果表明，相对于标准算法，本算法在跟踪能力和通用性上有一定的 提升。这些算法已经运用在机器人试验平台的组成部分中，并证明了这些算法的有 效性。关键词：Hume，函数程序设计，无人驾驶车辆，先驱者机器人，视觉引言本文比较和对比了在视觉序列中跟踪移动目标的三种计算机视觉算法。对于很多无人驾 驶车辆（AV）来说，在复杂背景中检测和跟随移动目标的应用是至关重要的。例如，这可 以让一个全尺寸无人驾驶车辆跟踪行人或者移动车辆并避免与之相撞

3、。同时对于机器人而 言，这项技术也可以提升导航性能和增强安全性。对单个移动目标的良好隔离，将便于我们 针对感兴趣的目标进行应用开发。而所有的这些应用都要求我们能够实时的处理全彩色的视 频序列。我们的工作是在基于先驱者P3-AT全地形机器人的无人驾驶车辆测试平台上进行的， 它是一个英国项目的一部分。这个庞大的项目是由国防科学技术中心（DTC）下辖的无人系 统工程（SEAS）为了开发新型无人驾驶车辆传感器技术而建立的。国防科学技术中心的无 人系统工程是由英国工业联盟操作管理，旨在通过采取系统工程的方法在整个系统和子系统 层次上，研究有关无人系统的创新性技术，以此达到利用科学技术进步促进军事能力发展

4、的 目的。本文有许多独到之处。第一，基于之前探讨的均值漂移算法，我们介绍了在复杂、混乱 的背景下追踪移动图像的新算法。第二，我们展示了我们的算法能够在全尺寸视频图像中实 时地追踪移动目标。第三，我们以先驱者P3-AT全地形机器人为基础，介绍了如何在一个简 易无人车辆测试平台上配置新算法。最后，我们的实现方式是与众不同的，因为我们采用新 颖的HumeM编程语言来编写程序。这一语言的新奇之处在于将函数式编程概念与编写实时 反应系统的有限状态自动机有机结合起来。B. Gorry, Z. Chen, G Michaelson来自苏格兰瑞卡顿的赫瑞瓦特大学计算机科学系。K. Hammond来自苏格兰圣安

5、德鲁斯的圣安德鲁斯大学计算机科学学院。A. Wallace来自苏格兰瑞卡顿的赫瑞瓦特大学电子与计算机工程系均值漂移视觉算法均值漂移分离算法我们将介绍利用不同内核对视频序列中移动目标实时跟踪的研究结果。这些内核是由 Comaniciu和Meeru,/ 第一次应用于图像分离处理，其具有如下特征，底层的、简单的、鲁 棒性的以及不同的均值漂移、聚类算法3。对于在无人驾驶车辆上的应用，我们首先通过分 割及交互式的选择确定一个感兴趣的目标，然后当该目标在摄像机视野范围内移动时对其实 施跟踪。设计均值漂移算法是用来寻找数据的众数（或者说数据高度集中区域的中心），而 这些数据是由任意维向量表示的。该算法处理过

6、程如下所示7。选择搜索窗口的半径选择窗口的初始位置（中心点）重复如下步骤计算整个窗口数据点的均值，然后将窗口中心点平移到该均值点直到中心点的平移距离小于预设的阀值特征空间中的高密度区域对应于在图像域中色彩/饱和度有限范围内拥有的足够大数量 的像素。因此，这些像素就形成了连通区域（这种情况在相对平滑图像中是很常见的）；该 算法本质上就是为了找到在对比度/色彩上基本无变化的相对较大的连通区域（被人们理解并定义的区域)。事实上，本算法是这样进行处理的，每一次随机地放置一个搜索窗口，找 到相应的众数，然后将所有特征向量从特征空间移动到最终窗口中。因此，人们总是希望能 够快速找到较大区域。(a) 一个3

7、20X240的彩色图像(b)对应的RGB图像(c)对应的Luv色彩空间图1图像，RGB和Luv之间的关系在实现过程中，我们将通常在RGB色彩空间中呈现的像素映射至ULuv色彩空间，Luv色 彩空间有一个通过L表示的亮度分量和两个通过u和v表示的色度分量。通常认为后一个色彩 空间等方性更好，因而更适合用在众数寻找算法中。最后，当我们定义了一个可变核，该可 变核就会在显示跟踪结果时被约束在我们之前提到的矩形窗口中。图1举例说明了图像和特征空间之间的关系。图2展示了分别在RGB与Luv空间中的分离 结果。至少主观上，我们可以看到在这个实例中利用Luv参数化所带来的提升。通过Hume 编程语言将RGB

8、映射到Luv的实现流程图如图3所示。图4是均值漂移分离算法的流程图。(a)在RGB色彩空间中分离结果(b)在Luv色彩空间中分离结果图2分离结果ou terr oroutputscreen图3 RGB到Luv的流程图（Hume）I (InpuiiSL M 才 tpf IV SCf ElEOQtexroT-oatputa c r eeen图4均值漂移分离算法流程图（Hume）均值漂移目标跟踪算法在初始帧中，首先针对目标区域定义一个矩形窗口。然后在Luv色彩空间中运用均值 漂移算法，将跟踪目标从背景中分离出来。当目标移动时，利用独特的倒角距离变换加权内 核来提升目标表示和定位的精度，同时利用Bha

9、ttacharyya系数使两个颜色分布之间的距离 最小化。在通过彩色图像序列跟踪目标的过程中，假设我们能够利用色彩空间中某一区域的 样本离散分布将目标表示出来，并利用一个能够确定当前位置的内核进行定位。因此，我们 就要找到函数P分布中的最大值。该函数是相对于之前的模版图像，在候选图像中目标位置 (漂移)的函数，用来计算加权色彩分布之间的相似度。而Bhattacharyya系数是重叠数 量的估算值。如果能够得到相对密度p(x)和q( x)的两组参数，则Bhattacharyya系数定义如 下：P = ( p ( x) q ( x) d x( 1)因此，我们在处理从彩色图像中得到的离散采样数据时，

10、我们就使用在模版和候选图像中应用以m进制直方图存放的离散密度。模版图像的离散密度定义如下:q = q =1,2,，mEq = 1u =1(2)同样地，在随后帧中的给定位置y处，候选图像的预估直方图是:pG)=p G),u =1,2,mEp =1u =1(3)pG)= p p根据方程(1)的定义，Bhattacharyya系数的样本估计定义如下:(4)_ p G), q = EJpu G)quu =1由色彩密度函数f (x)得到一组独立的随机样本xx2,x。如果K是标准的内核 函数，那么内核密度估计由下式给出:q =EK(X)5 _b(X )-u(5)i =1用这种方式估算色彩密度时，那么均值漂

11、移算法就用来在目标帧中不断移动位置y，以此来寻找Bhattacharyya系数分布的众数(方程4)。围绕p ( y0 )展开泰勒级数，则Bhattacharyya 近似为:pp(v), q其中i 为TTE+1E( xt)u =1i=1(6)(7)则方程（4）取最V =X X wG (v - x1i i 0 ii =1咋（V0 一气）(8)m -w = X 8u=1当方程（6）的第一项独立于y时，方程（6）的第二项取得最大值 大值。在均值漂移算法中，内核不断地从当前位置V。移动到新位置七， 下：其中，G是K的梯度函数。这等价于基于色彩直方图的内核过滤相似度函数梯度的阶跃上升。图5是均值漂移目标跟

12、踪算法的流程图。im4 Aci n0n1 1oxoubmr . iDLltpnlt&Uidigjl IJ Mr J心呷hamesURfi: staW cEn1 Ou iDopcaurit djrjmim iin GuiwKlnpug , state CEn Ou loopcount 即Jejr| bjn d； jn11 F p p 芒 ! uptLareitjcde LU nellocH tv kei loopbinbin 昌 Tarre1 CErfxyPu Qu fiEO bini coiiKat_dxy .i u W 2 HLT. binjn 了PlT QlT gM hirf If 疗 w

13、eight 口咋敏irtlpM- i .Im l睥囱口厂!图5均值漂移目标跟踪算法流程图（Hume）在无人驾驶车辆测试平台上应用跟踪算法我们的硬件测试平台由先驱者P3-AT全地形机器人组成，即SEBO （SEAS机器人，图 6）。我们为SEBO配置了前阵声纳光盘，无线以太网，前后安全保险杠以及一个安装在表 面用来收集均值漂移视觉算法数据的摄像头。我们通过如下的标准软件连接到先驱者机器人 从而实现Hume程序应用：ARIA（先进机器人应用程序接口）。该软件是一个连接机器人微 控制器的开源开发环境，并且提供了基本的马达和摄像功能接口； VisLib是一个基于C语 言的开源视觉处理程序库，它提供了基

14、本的图像处理能力。图 6 SEBO - the Heriot-Watt/St Andrews 先锋机器人 P3-ATA.软件体系结构图7展示了在测试平台上实现的软件结构。在机器人上实线箭头代表本地套接字通信而 虚拟箭头表示无线套接字通信。除了在笔记本电脑上运行的Java GUI以外，所有的代码都 是存储于机器人上的。位于机器人上的图像处理程序将机器人摄像机捕获的实时图像以 Hume语言方式记录，然后通过无线方式发送到笔记本电脑，并在其中实时的显示出来。每个图像的红色，蓝色和绿色分量都能被捕获到。由于其中被捕获的图像大小是240 x320，因 此要求有一个尺寸为3x240 x320的存储结构。图

15、7机器人测试平台结构图8接口界面的截图我们已经在笔记本电脑上实现了一个简单命令的接口。当用户决定移动机器人时，电脑 会发送一个无线信号到位于机器人上的Hume程序中。然后Hume程序与一个C+ ARIA程 序通信，该程序把基本的电机命令发送到机器人。以类似控制机器人的方式控制摄像头。图 7展示了当用户选择控制相机时，控制信号就通过无线从笔记本电脑发送到机器人上的 Hume程序中。然后，Hume程序就会与C+ ARIA程序通信，并让其发送相机的控制命令。 图8左上部分显示的是相机面板，用于控制相机的摇摄，倾斜和变焦功能。这里提供了两套 相机控制。第一组允许设定相机的最小运动或对焦距值，而第二组允

16、许设定相机的最大运动 或对焦值。结合视觉算法图7中有星号标记的Hume方框图可以先后被替换为：LUV转换算法；均值漂移分离算法；均值漂移目标跟踪算法。这些算法产生不同的图像效果。从最初的实验中，每一个算法都可以作为测试平台结构 的一部分，并通过简单地更换Hume盒，将图像从相机传到Java界面上。这项工作的开始 就要明确各算法间的依赖关系并在需要处建立有效的链接点。对于LUV的转换算法，图像被呈现在LUV色彩空间中。对于均值漂移分离算法，实 验中使用多种类型和尺寸的图像。通常情况下该算法是处理尺寸为240 x320的图像。均值 漂移目标跟踪算法的最初工作出现了令人欣喜的结果。对于一个放置在相机

17、焦点上的目标， 当机器人或相机以稳定的速度移动时，可以在屏幕上实时的跟踪目标。当前的工作是引入这样一个选项，它允许用户在界面屏幕上圈出感兴趣的目标，将其突 出出来。该对象的坐标，即在屏幕上的位置，就被传送到均值漂移跟踪算法。这样一来，如 果目标移动，机器人也跟着移动；或者机器人上的相机跟着移动，然后使用在2.2节中讨论 的算法对该目标进行跟踪。这些是可以在界面上观察到的。实现与实验评价图9展示了跟踪对象的第一帧图和前景图像。在这种情况下，当目标具有相对统一的亮 度时，一个简单的区域同质标准就会被采用。图10展示了使用NCDT内核跟踪一名男路人 的部分结果。图9分离出的矩形窗口图10使用NCDT

18、内核跟踪一名男路人的部分结果机器人平台目前，图7中展示的机器人平台已被用来作为在Hume语言中开发的视觉算法的部署体 系结构。这些算法的使用是Hume的实现工作以及Hume可以和其他行业标准语言，例如 C, C+, Java相结合的概念上的证明。在第二节中探讨的这三种算法，可以对安装在机器人 表面上的相机捕获的图像进行实时处理。机器人平台可能的扩展将涉及到的Hume代码的各个部分，这些代码与机器人的API 相连接。我们通过做这些内容，以个别方案为基础来获得一系列的性能分析。或者，我们将 图7中展示的三种Hume程序结合起来。通过程序的执行我们可以对其进行性能分析，当 Java接口发出机器人或相

19、机的移动请求时，我们也可以评估程序的反应速率。均值漂移跟踪 算法的一系列实验将继续进行下去。这些实验涉及到不同大小，颜色，不同的背景颜色和形 状的跟踪对象。相关工作在很多应用领域都有关于实时跟踪算法的应用。通过实时获取图像，并进行图像分割， 我们可以将图像分为几个不同的区域。然后，我们可以利用这个信息来跟踪突出显示的对象。 在这个处理过程中，这些算法是采用FPGAs（现场可编程门阵列）而不是微处理器来实现。这 是利用现场可编程门阵列的计算性和并行处理的优势。然而，在10中讨论到的算法需要用到 清晰可见的荧光标记，在本文中讨论到的均值漂移算法则不需要这种标记。我们最初的实验 已经证明两个仅在一些

20、小地方有颜色差异的相似物体也可以被识别出来。在嵌入式实时应用程序中，获得精确的时间和空间使用率边界是非常有价值的EH。如 果我们能够预测系统如何运行，我们就可以为一个程序周期的期望执行时间设定上界。使用 Hume编程语言，就可以做到这些。Hume编程语言设计的关键是它的可计算的功能。为了 提供这些计算结构，Hume编程语言开发了一系列的重叠语言子集13。在每个重叠子集中都 增加了语言的可表达性。通过选择合适的语言等级，程序员可以在语言的表现性和需要的 计算等级中得到平衡。因此，我们可以确定所需要的时间和空间上界一一这就使我们可以确 定所需要的硬件数量。在本文中提到的关于FPGAs的休姆算法的部

21、署正是我们所感兴趣的。 然后我们可以利用Hume编程语言的计算结果与微处理器中获得的计算结果相比较。结论及展望本文中我们探索了使用变量核来提高均值漂移分割算法。实验结果表明，和利用标准内 核程序计算结果相比较，已经完成的均值漂移物体跟踪算法在跟踪能力和通用性上有所提 高。这些算法包含在用于证明他们效率的机器人测试架构中。每一种算法都是用Hume算法 研发的。通过实时图像的处理和机器人的无线通信，可以在复杂混乱的背景下追踪移动物体。目前进行中的工作是通过以下几项来扩展试验平台：1、为无人驾驶车辆研发新图像的处理算法；2、通过增加一条线性后续算法来补充动态跟踪算法。这些将包括用于控制机器人和相机移

22、动的扩展接口，这些扩展功能还需要进一步的论 证：1、Hume编程语言如何用于研发执行实时处理的算法；2、测试平台的灵活性；3、跟踪算法的准确性。本论文中研究的工作是由英国国防部国防科学技术中心成立的系统工程自治系统(SEAS)资助的。这里要特别感谢我们在欧盟FP6 EmBounded工程中的合作伙伴：ChristianFerdinand、Reinhold Heckmann、Hans-Wolfgang Loidl、Robert Pointon 和 Steffen Jost。参考文献K. Hammond and G. Michaelson, “The Hume Report, Version 0.

23、3”，2006K. Hammond and G. Michaelson, “Hume: a Domain-Specific Language for Real-Time Embedded Systems”，Proc. of Int. Conf, on Generative Programming and Component Engineering, Erfurt, Germany, Sept. 2003, Springer-Verlag Lecture Notes in Comp. Sci., pp. 37-56.Y. Z. Cheng, “Mean shift, model seeking,

24、 and clustering,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 17(8): 790 -799, 1995.Comaniciu, P. Meer, “Robust analysis of feature space: Color image segmentation,” In IEEE Conf. Computer vision and Pattern Recognition, 750 一 755, 1997.Comaniciu and P. Meer, “M?an shift: A robus

25、t approach toward feature space analysis,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(5), 603-619, 2002.Comaniciu, V. Ramesh, P. Meer, “Kernel-based object tracking,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(5), pp564-575, 2003.Y. Keselman and E. Mic

26、heli-Tzanakou, “Extraction and characterization of regions of interest in biomedical images,” In Proceeding of IEEE International conference on Information Technology Application in Biomedicine (ITAB 98), 87-90, 1998.Bhattacharyya, “On a measure of divergence between two statistical populations defined by their probability distributions,” Bulletin of the Calcutta Mathematics Society, 35, pp99-110, 1943.MobileRobots Inc., “Pioneer 3 Operations Manual with