基于Camshift的改进人脸跟踪算法

董 琳，赵怀勋

（武警工程学院 通信工程系，陕西 西安 710086）

人脸是人最重要的外貌特征，由于脸部信息可以通过非接触的方式（如摄像头）取得，所以非常适合于作为身份鉴别的依据。人脸识别就是对于输入的图像或者视频，首先判断其中是否存在人脸，如果存在人脸，则进一步确定每张人脸的位置、大小和各个主要面部器官的位置信息，并依据这些信息提取每张人脸中所蕴含的身份特征，并将其与已知人脸库中的人脸进行对比，从而识别每张人脸所代表的个人。人脸识别是一门交叉学科，它的研究内容涉及计算机视觉、模式识别、计算机图形学、图像处理、生理学、心理学、认知科学等。人脸识别技术可采用非接触式的、连续的和实时的方式，在国家安全、军事安全和公安、司法、民政、金融、民航、海关、边境、口岸、保险及民用等领域实际应用具有极广阔的前景。

根据运动方法的不同，人脸跟踪方法主要可以分为两类：关于人脸检测的跟踪和关于物体运动的跟踪[1-2]。基于人脸检测的跟踪可以看成是人脸检测的延伸，连续帧的某一帧可以理解为处理静态的图片，在检测到人脸的基础上进行跟踪；根据物体运动的跟踪则是运用运动学原理对人脸进行跟踪。目前跟踪存在许多算法，主要分为：基于区域的跟踪，基于动态轮廓的跟踪，基于特征的跟踪，基于模型的跟踪和基于运动估计的跟踪。虽然众多研究者在跟踪方面已经做了大量的工作，并取得了一定的成绩，但都存在一些不足。梁路宏等人[2]用距离判别法较好地解决了多人脸跟踪中的个体对应问题，但距离较近时，模式分类技术较复杂，耗时比较长。Foresti等人[3]利用人脸肤色和轮廓搜索候选人脸，再用PCA进行模式匹配确认，跟踪准确率高，耗时少，但光照对肤色的影响和遮挡情况下会使跟踪效果变差。Wang等人[4]利用多个目标跟踪器与人脸检测结合，同时跟踪多张人脸，实时性较好，但算法较复杂。Zhou等[5]结合人脸运动信息，通过使用跟踪稳定系数解决多人脸跟踪过程中目标发生粘连重叠或由于目标检测质量造成跟踪目标丢失等问题，但不能处理目标被完全遮挡的情况。从目标跟踪机理分析，人脸跟踪过程可视为：模式搜索匹配过程或目标状态动态估计过程。如果人脸跟踪被视为模式搜

索匹配过程，那么人脸跟踪问题就成为局部的模式匹配寻优问题；如果人脸跟踪被视为目标状态动态估计过程，那么人脸跟踪问题就成为递推的状态估计问题。因此，人脸跟踪算法又可分两类：一类是基于目标模式搜索匹配的跟踪算法，常用的算法有Mean-Shift算法[7]等；另一类是基于目标状态估计、滤波的跟踪算法，常用的算法有Kalman滤波[8-9]，粒子滤波算法[10-12]等。这两种算法，各有优缺点：其中模式搜索的思想比较直观，实时比较好，但鲁棒性不足；目标状态估计、滤波跟踪算法对快速运动目标具有良好的鲁棒性，同时也更容易综合使用各种特征进行联合跟踪，但是实时性较模式匹配算法差。

1 Camshift算法

Camshift算法的的基本思想[13]是对视频图像的所有帧作MeanShift运算，并将上一帧的结果作为下一帧MeanShift算法的搜索区域的初始值而后对此进行迭代计算，它是一种基于颜色概率模型的跟踪方法，通过不断改变搜索窗口的中心到达质心，实现对物体的跟踪。Camshift算法能够实现实时跟踪，在背景简单的情况下能够取得很好的跟踪效果，但是对于肤色信息等条件比较敏感，如果背景的颜色与目标相近，或者目标附近有与目标的色调相近的物体，则Camshift会自动将其包括在内，对检测结果造成很大影响。针对这种情况，提出Camshift的改进算法并通过启动Camshift跟踪器来实现对多个人脸的检测。

1.1 背景放映计算

Camshift算法首先需要对被跟踪物体的色彩进行概率分布计算。由于RGB颜色空间对光照亮度变化较为敏感，为了减少此变化对跟踪效果的影响，首先将图像从RGB空间转换到HSV空间；然后对其中的H分量作直方图，代表不同H分量值出现的概率或者像素个数，即从直方图中可以查找出H分量大小为h的概率或者像素个数，得到颜色概率查找表；再将图像中每个像素的值用其颜色出现的概率对替换，就得到了颜色概率分布图。这个过程叫做反向投影[14]，颜色概率分布图是一个灰度图像，如图1~图3和表1所示。

图1 原始图像Fig.1 Original image

1.2 MeanShift算法

对被跟踪物体色彩进行反向投影以后，可以通过MeanShift算法这种密度函数梯度估计的非参数方法，利用迭代寻优找到概率分布的极值来实现目标定位。

图3 色彩概率分布图-灰度表示Fig.3 Gray image of color probability

算法过程为：

1）在颜色概率分布图中选取搜索窗S

2）计算零阶距：

for（int i=0；i

for（int j=0；j

M00+=I（i，j）

计算一阶距：

for（int i=0；i

for（int j=0；j

{

M10+=i*I（i，j）；

M01+=j*I（i，j）；

}

计算搜索窗的质心为：

Xs=M10/M10； Ys=M01/M00（1）

3）根据M00调整搜索窗口的大小，并将搜索窗口的中心移动到质心，如果移动距离大于预设的固定阀值，则重新计算调整后的窗口质心，进行新一轮的窗口位置和尺寸调整。直到搜索窗的中心与质心间的移动距离小于预设的固定阈值，或者循环运算的次数达到某一最大值，停止计算。

1.3 Cam shift算法

将MeanShift算法扩展到连续图像序列，就是Camshift算法。它将视频的所有帧做MeanShift运算，并将上一帧的结果，即搜索窗的大小和中心，作为下一帧MeanShift算法搜索窗的初始值。如此迭代下去，就可以实现对目标的跟踪。需要注意的是：当用Camshift对特定的颜色目标进行跟踪时，不必计算每帧图像所有像素点的颜色的概率分布，只需要计算比当前搜索窗大一些的区域内的颜色概率分布，这样可大大减少计算量。整个Camshift算法流程如图4所示。

表1 色彩概率分布图-数字表示Tab.1 Digital color probability distribution

图4 Camshift算法流程Fig.4 Camshift algorithm flow

2 改进的Camshift算法

实验证明，运用Camshift算法对目标物体进行跟踪时存在的问题[15]如下：

1）当人脸目标在帧间位移较大时，Camshift算法中根据上一帧图像跟踪结果得到的新搜索窗口可能与目标没有联接，导致跟踪丢失。

2）在跟踪窗口中出现遮挡时，跟踪容易失败。3）进行人脸跟踪时，每次只能跟踪一个人脸。

2.1 对运动目标的跟踪问题

针对目标像素在帧间位移较大导致跟踪丢失的问题（一般是M00<0.3 M00的情况下），可以对目标进行简单的运动估计，运用得到的预测值对搜索窗口进行平移，增大搜索窗口与目标联接的可能性，提高跟踪的可靠性。

具体步骤如下所示：

Step1：建立一个对于被检测物体运动时的跟踪模型

其中，gk是目标物体在第k时刻中心坐标的测量值；g^k为第 k时刻目标的预测位置；Δgk为第k时刻预测的目标位置的误差，该值的大小体现了目标的搜索范围；vk为目标在第k时刻的测量速度；为目标在第 k时刻的估计速度；Δvk是目标在第k时刻的估计速度的误差；ak为目标在第k时刻的测量加速度；为目标第k时刻的估计加速度；Δak是目标在第k时刻的 计加速度的误差。

Step2：运动目标跟踪过程是不断重复执行预测、搜索匹配和修正跟踪模型参数的循环过程。采用以下加速度位移方程预测目标在下一时刻可能出现的位置和目标搜索范围：

其中gk+1是预测位置的坐标，Δgk+1是预测误差，由这两个值可以求得目标匹配搜索的范围g^k+1±Δgk+1。得出这个搜索范围，可以使用目标的颜色直方图模型作为图像匹配的距离准则，在跟踪过程中对视频图像处理区域中的每一个像素，通过查询目标的颜色直方图模型，可以得到该像素为目标像素的概率，图像处理区域之外的其他区域作为概率为0的区域。

Step3：通过Camshift计算出质心位置，并把它的中心坐标复制给gk+1，同时计算目标的测量速度和测量加速度

实际工作中，首先要对目标下一时刻出现的位置和搜索范围进行估计；然后，利用Camshift的目标的颜色直方图模型匹配搜索目标真实位置；最后，对速度、加速度和目标搜索范围进行修正，重复上述步骤完成目标的跟踪。

2.2 对被遮挡物体的跟踪问题

针对Camshift在跟踪过程中遇到遮挡或者跟人脸颜色相近的肤色干扰时往往会导致跟踪失败的问题，本文利用元素个数约束机制，在搜索到人脸后记录搜索窗口内像素的个数，根据公式（S表示包括人脸的窗口大小，M表00示图像的零阶距）得到搜索窗的初始窗口的大小，作为搜索窗口的初始位置和大小，系统进入跟踪阶段。在跟踪过程中，通过计算得到的窗口的大小与初始化时保留的初始窗口的大小相比较，当得到的大小超过初始窗口大小的1.5倍或者是低于初始窗口的0.6倍时，说明在跟踪过程中遇到了近色干扰或者遮挡情况，这时重新启动人脸检测功能，当人脸重新出现时，检测出人脸的位置，重新进入Camshift跟踪阶段，从而避免了Camshift跟踪算法在遇到遮挡或者干扰情况时跟踪失效的情况。

2.3 对多人脸出现的跟踪问题

针对原算法不能同时跟踪多个人脸的问题，文中采用的是设置多个Camshift跟踪器。在人脸检测阶段会存在检测到多个人脸的情况，则跟踪的时候要为每个人脸区域分配一个跟踪器，每个跟踪器负责自己的跟踪对象。当跟踪的人脸消失时，取消该跟踪器。当所有的人脸都消失后，系统自动转入人脸检测阶段，重新开始对每一帧输入图像检测是否有人脸，当检测到人脸时重新转换到跟踪状态，人脸增加时，相应地增加Camshift跟踪器，从而实现了多人脸的跟踪。

3 实验结果与分析

实验采用单人从场景左侧行走到右侧的一组视频序列，如图5所示。跟踪过程中，首先需要对跟踪器的参数进行初始化。表1给出了当α=0.8、γ=0.8时的跟踪结果。其中括号内数据分别为跟踪水平方向和垂直方向的值，表中第一行给出了参数的初始化值，第二列为该运动目标跟踪后得到测量位置，其余各列为跟踪器预测的结果。从表2可以发现随着跟踪器参数的不断修正，目标的搜索范围Δgk逐渐减小，而预测位置也越来越接近目标的实际观测位置gk。这说明该文的算法可以有效地预测运动目标的位置，同时可自适应地调整运动目标的搜索范围。

图5 单人从场景左侧行走到右侧视频序列图Fig.5 Single person walking from left to right video scene sequence diagram

表2 视频序列中人的跟踪结果Tab.2 T he results of human tracking in video sequences

通过仿真实验，表明改进算法较之原文算法，不管对慢速还是快速的运动物体都有很强的适应能力，如图6-图7所示。

图8-图9为存在遮挡和干扰的情况下的一组视频序列，图9为多个人脸存在的一组视频序列。实验表明，当遮挡严重时如图8（d）跟踪失效，这时启动人脸检测机制，当遮挡结束重新检测出人脸如图9（e）并进行跟踪图9（f）。图9（g）则显示了改进的算法在有肤色近似干扰时，仍保持了较好的鲁棒性。图10从a~e连续5帧表明改进后的Camshift算法能实现多人脸跟踪。通过图9和图10可以看出,改进的算法在原有Camshift的基础上，实现了自动目标跟踪和多人脸的跟踪，遇到遮挡干扰时也能够对人脸进行可靠的跟踪。

图6 慢速运动目标跟踪Fig.6 Slow-moving target tracking

图7 快速运动目标跟踪Fig.7 Fast-moving target tracking

图8 原算法在遮挡和干扰情况下的跟踪结果Fig.8 The tracking results with the original algorithm in the case of block and interfere

4 结束语

改进的Camshift运动目标跟踪算法有效地弥补了Camshift跟踪算法对加速运动作用的缺陷。实验表明，该算法能实时准确地跟踪目标，对快速和慢速运动目标的跟踪都有很强的适应能力，运算量统计显示帧差输入比连续图像输入运算量低。此外，该算法还通过利用元素个数约束机制记录搜索窗口内像素个数的办法有效提高了有遮挡物情况下的鲁棒性，同时通过启动多个Camshift跟踪器很好地实现了多人脸的跟踪，有广阔的应用前景。

图9 改进算法的情况下干扰和跟踪的结果Fig.9 The tracking results with the original algorithm in the case of block and interfere

图10 改进算法情况下多人脸跟踪结果Fig.10 The faces-tracking results with the advanced algorithm in the case of block and interfere

[1]刘明宝，姚鸿勋，高文.彩色图像的实时人脸跟踪方法[J].计算机学报， 1998，21（6）:527-532.LIU Ming-bao，YAO Hong-xun，GAO Wen.Real-time humanface tracking in the color images[J].Computer Science，1998，21（6）:527-532.

[2]梁路宏，艾海舟.基于人脸检测的人脸跟踪算法[J].计算机工程与应用，2001（17）:42-45.LIANG Lu-hong，AI Hai-zhou.Face detection based on face tracking algorithm[J].Computer Engineering and Application，2001（17）:42-45.

[3]Foresti G L，Michneloni C，Snidaro L，et al.Face detection for visual surveillance[EB/OL].[2008-12-20].http://ieeexplore.ieee.org/xpls/abs-all.jsp arnumber=1234036.

[4]Wang J，Achanta A.Hierarchical frame work for face tracking using state vector fusion for compressed video[EB/OL].[2008-10-20].http:∥iet.ewi.tudelft.nl/pub/jun/2003facetracker.pdf.

[5]JIANG ZHUO-LIN， LISHAO-FA， GAO DONG-FA.An adaptive meanshift tracking method using multi-scale mi ages[C]//Proceedings of the 2007 International Conference on Wavelet Analysis and Pattern Recognition.Beijing，China:IEEE， 2007，3:1060-1066.

[6]Comaniciu D，Ramesh V，Meer P.Real-Time Tracking of Non-Rigid Objects using Mean Shift[C]//Conference on Computer Vision and Pattern Recognition，Hilton Head，USA，IEEE Computer Society 2000.

[7]Kalman.A new approach to linear filtering and prediction problems[J].Journal of Basic Engineering，1960，82:35-45

[8]Kim H，Kang W，Shin J，et al.Face detection using template matching and ellipse fitting[J].IEICE Transactions on Information and Systems，2000，83（11）:2008-2011.

[9]Isard M，Blake A.Condensation:Conditional density propagation for visual tracking[J].International Journal of Computer Vision，1998，29（1）:5-28.

[10]程建，基于粒子滤波的视觉跟踪算法研究及其在红外成像制导中的应用[D].上海：上海交通大学，2006.

[11]杨进.基于粒子滤波的多目标跟踪算法研究[D].上海：上海交通大学，2008.

[12]吴慧敏，郑晓势.改进的高效Camshift跟踪算法[J].计算机工程与应用，2009，45（27）：178-180.WU Hui-min，ZHENG Xiao-shi.Improved and efficient object tracking algorithm based on camshift[J].Computer Engineering and Applications，2009，45（27）：178-180.

[13]佘九华，王敬东，李鹏.基于Camshift的人脸跟踪算法[J].计算机技术与发展，2008，18（9）：12-15.SHE Jiu-hua，WANG Jing-dong，LI Peng.Face tracking algorithm based on camshift[J].Computer Technology and Development，2008，18（9）：12-15.

[14]Collins R T，Lipton A J.Introduction to the special section on video surveillance[J].IEEE Trans on Pattern Anaysis and Machine Intelligence，2000，22（8）：745-746.

[15]Bradski G R.Computer vision face tracking as a component ofa perceptual user interface[C]//Proceedings of IEEE Workshop Applications of Computer Vision.Princeton，NJ:IEEE，1998:214-219.