基于NCC匹配的Camshift目标跟踪算法

基于NCC匹配的Camshift目标跟踪算法

郑朝晖

(武汉铁路职业技术学院公共课部, 武汉430205)

摘要：目标跟踪一直以来都是机器视觉的热点问题，通常目标跟踪主要是通过寻找上下帧的相似特征来确定目标位置。Camshift算法在目标跟踪过程中一般利用的是目标的颜色信息，但在目标受到类似颜色干扰时容易跟踪失败，而NCC算法能够利用目标的结构特征。提出了一种结合Camshift与NCC的跟踪算法，使用Camshift对目标位置进行定位，同时在定位区域利用缩放比例进行NCC匹配得到目标的最终位置。实验结果表明该算法是可行有效的，对比当前传统跟踪算法其跟踪性能有着显著的提高。

关键词：Camshift;NCC;目标跟踪

文章编号：1673-1549(2015)04-0037-04

DOI:10.11863/j.suse.2015.04.08

收稿日期:2015-05-27

基金项目:武汉铁路职业技术学院院级课题

作者简介:郑朝晖(1985-)，男，湖北黄冈人，讲师，硕士，主要从事数字图像处理与模式识别方面的研究，(E-mail)zhengzhaohui@sina．cn

中图分类号：TP391.4

文献标志码：A

引言

目标跟踪在机器视觉中一直是一个热门课题。目前有很多的目标跟踪方法，但是它们都有各自的优点和缺点。而目标跟踪的关键在于目标特征提取的合理性和识别目标的准确性，同时要考虑算法的时间，确保实时性。Camshift算法[1-2]是一种有效的目标跟踪算法，它是MeanShift跟踪方法的改进。该算法通过使用梯度优化方法来完成目标定位，对目标的旋转、变形等变化有较好的适应能力，同时算法的运算速度快。Camshift算法对单一色调的目标及背景和目标颜色不同的情况跟踪效果显著，但是当周围环境存在颜色干扰时，只使用Camshift算法容易丢失目标。NCC算法(归一化互相关算法)[3-5]是一种经典的图像匹配算法，它通过计算模板图像和搜索图像的互相关值来进行匹配。NCC 算法适用于几何畸变及灰度变化不大的情况，同时它具有抗白噪声能力，但该方法容易受到目标旋转、变形的影响，且匹配速度较慢。

考虑到目标运动过程中可能会受到场景中诸如形变、遮挡和运算速度等因素的影响，本文在采用基于颜色直方图的Camshift跟踪算法的同时，结合了NCC 算法对目标空间运动位置进行进一步匹配，在保证匹配精度的前提下，提高NCC匹配算法的速度，增强算法对实际应用的适应性。

1Camshift跟踪

近年来，MeanShift算法[6]因其结构简单、效率高的特点已被广泛应用于目标跟踪领域。但是MeanShift算法缺乏必要的模型更新，因此只适用于静态分布，这将影响跟踪的精度。而作为一种改进MeanShift算法的方法，Camshift(连续自适应MeanShift)算法[7-8]可以应用于动态概率分布情况。在跟踪过程中，Camshift利用目标的颜色直方图模型得到每帧图像的颜色投影图，并根据上一帧的结果自适应调整搜索窗口的位置和大小，从而得到当前图像中目标的尺寸和中心位置。

颜色直方图作为Camshift所采用的颜色特征。它所描述的是不同色彩在图像中所占的比例，而并不关心每种色彩所处的空间位置。图像中颜色范围分为N个相等但不相交的区间，统计颜色为n的像素个数为h(n)，这些h(n)矩形依次排列就得到颜色直方图。

颜色概率分布表示为：

(1)

其中，n为颜色像素值，作为颜色直方图得横坐标；h(n)为颜色像素个数，作为颜色直方图的纵坐标；p(n)为h(n)的归一化取值。直方图中的h(n)由p(n)代替，就得到目标的颜色直方图模型。

对于一幅图像I(x,y)来说，Camshift算法需要通过下列公式计算出下一幅图像的初始搜索窗口的长和宽。

图像零阶矩：

图像一阶距为：

图像二阶矩：

搜索窗的质心：

目标主轴方向角为：

自适应计算出的下一次搜索窗口的宽w和高h分别为：

其中：

Camshift算法跟踪步骤为：

(1) 选择感兴趣的初始区域，其中包含要跟踪的目标。

(2) 计算该区域的颜色直方图作为目标模型。

(3) 计算搜索窗的颜色概率分布(反向投影)。

(4) 基于概率分布的图像，找到搜索窗的质心。

(5) 移动搜索窗的中心到质心，如果移动距离大于设定的阈值，则重复步骤(4)，直到搜索窗的中心与质心间的移动距离小于给定的阈值，或者循环次数达到某一最大值，停止循环计算。

2NCC匹配

NCC匹配算法也称为归一化互相关匹配算法[9-10]，它适用于没有几何误差的情况。该算法计算模板与待匹配图像的互相关值来确定匹配的相似度。简单而言，模板就是预先选择感兴趣的目标图像，匹配就是在待匹配图像中寻找该目标图像，这要求图像中存在目标图像，同时该目标图像与模板存在较小角度的旋转或者形变，通过计算出的互相关值来确定目标的坐标位置。假设搜索图像S的尺寸为M×M，模板T的尺寸为N×N，其中M>N，单位为像素。模板T在搜索图像S上平移，Si,j为模板在搜索图像所覆盖的子图，子图在搜索图像S中左上角顶点的坐标为(i,j)。在实际匹配中，模板和搜索图像的相似性通过度量函数来衡量，则归一化互相关匹配度量定义为:

NCC 算法具有较高的适应性和准确性，对图像灰度值的线性变换具有“免疫性”，即所求的NCC 值不受灰度值的线性变换影响，但计算量太大，导致匹配效率低。

3结合Camshift与NCC的跟踪算法

Camshift算法适合于非线性运动目标的跟踪，具有快速有效的特点[11]；NCC 算法可以利用结构特征准确地定位运动目标的位置。因此本文将两种算法相结合，采用基于颜色的Camshift算法的同时利用NCC 算法考虑目标的结构信息。该算法对场景中存在的诸如颜色干扰、光照变化等因素的影响不敏感。

3.1　利用Camshift算法进行目标区域定位

运动目标的定位是目标准确跟踪的关键组成部分。它主要是通过目标特征来确定视频中目标图像所对应的位置区域，从而实现运动目标的跟踪。

在目标跟踪前，先确定初始目标图像的颜色概率分布图和目标跟踪模板，然后利用Camshift算法计算出目标包围窗口，快速获取目标质心和大小，从而定位出相似目标颜色特征的区域。由于在Camshift算法中，目标跟踪只是简单地以颜色概率作为其跟踪模式，当它用于背景中有类似颜色区域的目标跟踪时，必然会忽略了目标所特有的外观而出现跟踪失误，所以获取的目标位置及大小需要利用NCC算法进行目标模板匹配。

3.2　利用NCC算法进行目标匹配

以获取到的类似目标质心为中心、目标大小为半径(可以适当增大，本文设置为5个像素)作一个矩形为待匹配区域，利用NCC算法将目标跟踪模板和待匹配区域进行匹配。若最大互相关值大于阈值则匹配成功，更新目标的中心和大小，同时更新颜色概率分布图和目标跟踪模板；反之匹配失败，不更新目标的中心和大小。

基于NCC匹配的Camshift目标跟踪算法不仅提高了传统跟踪算法的准确性，又实现了连续跟踪的速度。其过程如图1所示。

图1　基于NCC匹配的Camshift目标跟踪算法

3实验结果与分析

为了检测算法的有效性，依照本文的算法对多只同类动物水面奔跑视频图像序列进行了目标跟踪测试(图2(分别为第1、13、37、64帧))，取得了较好的跟踪效果。图2(a)是采用Camshift算法的跟踪情况，由图2(a)可以看出，Camshift算法的跟踪窗口向着目标点集中的方向漂移，但在第13帧时目标受到另一个同类颜色所干扰，跟踪窗口漂移到附近与目标颜色相近的背景上。直到第37帧时，目标背景变得单一，跟踪窗口重新回到目标身上，而在第64帧时，目标部分超出视频区域，跟踪窗口出现下移，只包含一部分目标；图2(b)是结合NCC 算法的跟踪结果，通过模板的结构比较，判断是否为目标，干扰前后均实现了准确的跟踪。

将本文算法与传统算法进行准确性与运算速度进行比较，结果见表1。从表1可知，相较于传统NCC算法与Camshift算法，在相同的目标模板情况下，本文的算法在运算速度上改善非常明显，尤其是相对于传统NCC算法来说，运算速度提高了近一倍；另外，匹配准确率也高于传统算法。

图2　多只同类动物水面奔跑视频图像序列

表1　对若干视频序列图像下各算法的准确性及耗时

4结束语

本文提出了基于NCC匹配的Camshift目标跟踪算法，采用基于颜色的Camshift算法的同时利用NCC 算法考虑目标的结构信息，解决了场景中存在大面积类似颜色干扰导致跟踪失败的问题，并且在减少跟踪失败的同时最大限度地保证算法的实时性。与直接在图片上进行模板匹配确定目标的算法相比，本文方法因以Camshift算法为主导，其速度大大提高；而与原始的CamShift算法相比，其准确性又有所改善。当模板过大或者出现旋转时，基于NCC匹配，可以采用比例缩放和角度旋转关系，或者采用基于金字塔结构的模板匹配算法完成匹配，能够有效提高运算速度。

参 考 文 献：

[1]Comanciu D,Ramesh V,Meer R.Real-time tracking of non-rigid objects using mean shift//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition,Dublin,Ireland,June 13-15,2000:142-149.

[2]吴慧敏,郑晓势.改进的高效Camshift跟踪算法.计算机工程与应用,2009,45(27):178-180.

[3]孙祖鑫,吴强.一种基于TS201的归一化互相关快速算法.现代电子技术,2010(10):125-127.

[4]韩冰,王永明,刘杨.一种基于积分图像的快速归一化积相关算法.弹箭与制导学报,2009,29(5):283-286.

[5]郭伟,赵亦工,谢振华.一种改进的红外图像归一化互相关匹配算法.光子学报,2009,38(1):189-193.

[6]Chen Y Z.Mean shift,mode seeking and clustering.IEEE Transactions on Pattern Analysis and Machine Intelligence,1995(8):790-799.

[7]Comanciu D,Meer R.Mean shift:a robust approach toward feature space analysis.IEEE Transactions on Pattern Analysis and Machine Intelligence,2002(5):603-619.

[8]Mazinan A H,Amir-Latifi A.Applying mean shift,motion information and Kalman filtering approaches to object tracking.ISA Transactions,2012(5):485-497.

[9]Hidayatullah P,Konik H.CAMSHIFT improvement on multi-hue and multi-object tracking//Proceedings of International Conference on Electrical Engineering and Informatics,Bandung,Indonesia,July 17-19,2011:17-19.

[10]Wu Lianhui,Zhang Guoyun,Guo Longyuan.Study the improved CAMSHIFT algorithm to detect the moving object in fisheye image//Proceedings of 2013 International Conference on Mechatronic Sciences,Electric Engineering and Computer(MEC),Shenyang,December 14-16,2013:1017-1020.

[11]闫钧华,陈少华,艾淑芳.基于Kalman预测器的改进的CAMShift目标跟踪.中国惯性技术学报,2014,22(4):536-542.

[12]Ali P,Sajad P,Saeed K.Scene matching NCC value improvement based on contrast matching//Proceedings of 2013 8th Iranian Conference on Machine Vision and Image Processing(MVIP),Zanjan,Iran,September 10-12,2013:296-299.

[13]刘艳丽,唐先琪,陈跃东.基于改进Camshift的运动目标跟踪算法应用研究.安徽工程大学学报,2012,27(2):74-77.

Camshift Target Tracking Algorithm Based on NCC Matching

ZHENGZhaohui

(Department of Public Courses, Wuhan Railway Vocational College of Technology, Wuhan 430205, China)

Abstract:Target tracking is always a hot topic of machine vision, usually target tracking determines the position of target by searching the similarity of upper and lower frames. Camshift algorithm commonly utilizes the color information of the target in the target tracking process, but the target tracking is easily failed when exists interference of similar color. While the NCC algorithm can use the structure features of target. Therefore, a tracking algorithm which combines Camshift with NCC is proposed, in which Camshift is used to locate the positioning of target, meantime, NCC matching is conducted by using the scaling in location area, then the final position of target is obtained. The experimental results show that the algorithm is feasible and effective, and the tracking performance is improved significantly compared with the traditional tracking algorithm.

Key words: Camshift; NCC; target tracking