基于AHP的跟踪算法性能评价研究*

樊 祥，方义强，2，程正东，朱 斌，施 展，2

(1解放军电子工程学院，合肥 230037;2脉冲功率激光技术国家重点实验室，合肥 230037)

0 引言

对目标的检测跟踪算法在近几年得到了很大的发展。为了能够对算法有一个合适、客观的评价，更好的把握算法改进和研究的方向，促进对算法的优化，需要一个科学的算法性能评价方法。对于检测算法的性能评价研究得比较多，很多文献都对这方面做了比较深入的讨论研究[1];而现行文献资料对于目标跟踪算法的评价方法研究较少，只分别从一些侧面对跟踪算法进行过初步的研究。文献[2]采用了有效跟踪评价和有效跟踪精度评价的方法对跟踪算法进行评价;综述文献[3]提到了目前国际上在智能视频算法中通过精确度、完整性来进行跟踪算法的性能评价;文献[4－6]用算法具有低的跟踪误差来说明算法性能优越性的问题;文献[7]用算法的跟踪有效性和精度来说明算法性能;文献[8－9]通过算法的实时性来说明算法的优越性。但是这些文献都没有系统的对跟踪算法的性能进行评价，主要表现在两个方面:一是采用的性能指标不够全面;二是没有对各性能指标进行综合。

因此文中主要针对跟踪算法的评价方法不够健全的问题，利用层次分析法(AHP)提出了一种评价跟踪算法的方法，AHP法为运筹学中进行系统效能评价的一种方法，文中是第一次用AHP法来进行跟踪算法的性能评价。

1 主要性能指标的分析

要对跟踪算法进行评价，首先需选取合适的指标作为评价的依据。通过对相关文献和算法的研究，一个完整的跟踪算法主要涉及到的指标有跟踪准确度、算法的实时性和算法的硬件实现等，因此文中主要从算法的这几个方面来考虑跟踪算法的性能评价问题。

1.1 跟踪准确度

跟踪准确度是最直观的反映算法性能的一个方面。文献[10]提出了一个跟踪率的概念，跟踪率定义为，α=n/N，其中n为持续跟踪上的图像帧数，N为跟踪图像的总帧数。该方法可以在一定程度上表征算法对目标的跟踪准确度，但该方法只是从是否跟踪上目标来说明跟踪的准确度问题，是一个比较粗糙的方法，不能精确的描述一个算法的跟踪准确度，尤其是对于对红外小目标的跟踪描述。而多数文献用目标的算法预测位置与实际位置的差，即跟踪误差来说明跟踪的准确度问题[3－4，7]，该方法精确的描述了每帧图像的误差，但同时该方法不对跟丢的情况进行判断，使得跟踪误差在遇到目标跟丢的情况下失去了意义。因此文中将两者结合起来描述跟踪的准确度。

由于存在目标跟丢的情况，因此需要对跟踪误差做进一步的定义。假设对于某个算法，算法得到的有效预测坐标与实际坐标的平均跟踪误差为E(μ)，其定义如下:

式中:xti、yti是真实目标的坐标值;xci、yci是算法跟踪有效的目标坐标值。这里计算平均跟踪误差时，只计算了算法对目标有效跟踪部分的坐标值，而没有考虑跟丢时误差的计算，显然这样不够合理。因此在讨论误差时，文中提出采用E(μ)/S11=E(μ)·N/n来衡量算法的跟踪误差。

1.2 跟踪算法的实时性

对目标的自动检测跟踪对实时性的要求很高，在算法评价时必须要考虑其实时性的问题。现行的很多算法结构比较复杂，时间开销很大，虽然这些算法在一些特定的场合在某些方面可以取得相对较好的效果，但是这样的算法实时性差，仍然没有实际应用的价值。因此，在考虑跟踪算法的性能评价时，必须要把实时性考虑在内。

设v为算法处理速度，单位为fps(帧 /s)，文中算法的处理速度用计算机仿真得到。算法的处理速度应该有一个合适的值，这与有些文献上认为的处理速度越快越好的观点是不一样的。因为算法首先应该满足实时性的要求，但是当算法达到的速度过快时，已经远超出了实时性的要求，超出的部分对于算法性能的提高没有影响或影响不大，而且很多情况下处理速度的加快是以牺牲其它方面的性能为代价的。因此文中在考虑实时性的时候提出处理速度上限和下限的概念，分别用vH和vL表示，用一个分段函数来表述处理速度对算法性能的影响，表达形式如下:

当v＜vL时，认为算法过慢，为无效算法;当vL≤v≤vH时，算法性能随着速度的增加线性提高;当v＞vH时，认为算法处理速度已超过了需求的处理速度。

1.3 算法的硬件可实现性

好的算法同时也应该适合于硬件的实现[11]，而很多算法在设计时没有考虑到其硬件实现的问题，没有考虑算法所需要的硬件资源情况以及现阶段的可实现性问题，使得这些算法只能停留在研究层面。因此，文中提出把算法的硬件可实现性也作为评价算法的一个重要的依据。

对于一个算法，其越容易通过硬件来实现，对硬件资源的需求越少，则认为该算法的可实现性越好。与前两者不同的是，算法硬件的可实现性为定性指标，因此文中采用5个等级来量化算法的可实现性，用δ表示，δ的值越大说明其硬件可实现性越好，其取值情况如表1所示[12]。

表1 δ的取值与等级的对应关系

其中，硬件可实现性的权值可以通过算法实现对硬件资源的需求、硬件开发难易程度等方面来综合衡量，通过评价者的经验或相关专家讨论来确定。也可以把硬件可实现性分成更详细的下级指标参数，由评价者或者组织各领域专家进行打分确定，文中对此不做更深入的研究。

2 算法性能的综合计算

通过前面的论述可知，对于小目标跟踪算法评价的内容如图1所示。

图1 跟踪算法性能评价内容

在确定各个指标后，需要按照实际的需求情况，对各个指标进行加权综合，形成对跟踪算法性能评价的综合指标。常用的可用于指标加权的方法有AHP法、模糊综合评价法等，而从跟踪算法评价的内容可以看到评价指标体系具有明显的层次性，而且涉及的指标参数较少，因此文中采用 AHP法来计算综合指标。

AHP法是美国匹兹堡大学运筹学专家T.L.Saaty于20世纪70年代提出的一种系统分析方法。1982年天津大学许树柏等将该方法引入我国，研究内容主要集中在判断矩阵、比例标度、一致性问题、可信度上。AHP法是一种实用的多准则决策方法，该方法以其定性与定量相结合处理各种决策因素的特点，以及系统、灵活、简洁的优点，在我国得到了广泛的应用[12]。

2.1 构造权重判断矩阵

根据AHP法，首先需要构造权重判断矩阵，以区分各个指标的权重。在构造判断矩阵时，要根据实际情况选择合适的标度法，由决策者直接通过对指标两两比较得到，常见的标度法有1～9标度法，9/9～9/1分数标度法、90/9～99/9指数标度法等。如表2为应用比较多的 1 ～ 9 标度法[12－13]。

表2 1～9标度法等级量化表

如对于第一层指标，假设其判断矩阵为A，则其形式如下:

式中，aij表示指标ai相对于指标aj的相对权重，指标a1、a2、a3分别对应于跟踪准确度、实时性和硬件可实现性。

2.2 指标权重计算

根据AHP法，得到判断矩阵后，对指标权重的计算分3个步骤，以第一层指标为例。

第一步，计算判断矩阵A的每一行元素的乘积:

式中n为判断矩阵A的维数。

第二步，计算Mi的n次方根:

第三步，对ˉωi进行归一化处理:

这样就得到了所需求的权向量 ω =[ω1，ω2，ω3]，ω1、ω2、ω3分别为跟踪准确度、实时性和硬件可实现性。

2.3 一致性检验

对于判断矩阵，由于人的主观度量可能存在一定的偏差，因此为了提高权重评价的可靠性，最后需要对判断矩阵做一致性检验。

判断矩阵的最大特征值λmax为:

式中，[Aω]i为Aω向量中的第i个元素。

一致性检验的公式为:

其中:CI为一致性指标，CR为一致性比例，RI为修正因子。通常情况下，当CR ＜0.1时，认为该判断矩阵满足一致性要求，对于维数小于3的不需要进行判断。RI的取值和维数相关，其取值和维数的对应关系如表 3 所示[12]。

表3 RI的取值表

2.4 指标的规范化

对上述的用于评价的各种指标，其量纲不同，各指标值的量级也不一样，很可能造成评价的不合理性，因此在进行综合评价前，有必要把各指标值转换为可以综合处理的量化值，一般都规范到[0，1]的范围内。

跟踪率S11=α=n/N和硬件可实现性S3=δ的值已经在[0，1]内，且为无量纲的量，满足规范要求;跟踪实时性S2，通过S2=η/vH来规范;跟踪误差S12属于成本型指标，即误差越小，跟踪效果越好，根据成本型指标的线性变换方法[12]，首先得到最小误差Emin(μ)，然后通过线性变换把跟踪误差的值限定在[0，1]的范围内，而理论上的最小误差值为零，因此Emin(μ)必须为一个非零值，对于小于该值的误差按照Emin(μ)处理。

2.5 计算综合评价分数

在获得各指标的权重后，通过与对应评价值的乘积就可以得到最后的综合评价分数。对于不同的跟踪算法，得分最高者性能好。计算算子为:

S1、S2、S3分别为跟踪准确度、实时性和硬件可实现性的评价分数。其中跟踪准确度的分数S1同样可以通过AHP法由跟踪率和跟踪误差获得，即 S1=[ω11，ω12][S11，S12]T。

通过前面的讨论可以得到基于AHP的小目标跟踪算法的评价流程如图2所示。

图2 基于AHP的小目标跟踪算法的评价流程图

3 实验验证

求得权向量分别为[ω11，ω12]= [0.75，0.25];[ω1，ω2，ω3]= [0.57，0.29，0.14]。对于 A2，其一致为了验证文中方法的合理性以及对一些参数的确定和优化，文中采用流行的几种跟踪算法进行了实验，并通过上述评价方法来进行跟踪算法的性能评价，得到各个算法的综合评价分数。

在实验之前，文中通过综合考虑构造了判断矩阵，用于实验后的性能讨论，由于该评价系统中涉及的指标参数少，容易进行两两比较判断，因此文中采用了1～9标度法来构造权重判断矩阵。对于跟踪率和跟踪误差采用的判断矩阵为A1，对于跟踪准确度、实时性和硬件可实现性的判断矩阵为A2，则其取值如下:性比例RI=0，符合一致性要求。

由于文中采用的跟踪算法是针对红外小目标的跟踪的，认为当跟踪误差超过3个像素时就认为目标开始丢失，并且取Emin(μ)取0.2(个像素);算法处理速度的上限设为 50fps，下限设为1fps。文中实验总共包含3组图像序列和4种不同的算法。图3为参与实验的3组图像序列，其中小目标用白色矩形框标识。

图3 参与实验的3组图像序列

表4～表6为分别采用粒子滤波算法[14]、均值位移算法[15]、自适应阈值分割算法[16]和基于数学形态学的小目标跟踪算法进行实验得到的数据;表7～表9为由各个实验得到的数据根据本章提出的评价方法计算得到的指标分数。

表4 采用图像序列1实验后得到的数据

表5 采用图像序列2实验后得到的数据

表6 采用图像序列3实验后得到的数据

表7 采用图像序列1实验数据计算得到的指标分数

表8 采用图像序列2实验数据计算得到的指标分数

表9 采用图像序列3实验数据计算得到的指标分数

从计算结果可以看到，对于图像序列1和图像序列2，由于目标所在的位置背景比较简单，信噪比较高，因此除均值位移算法跟踪效果相对较差外，其它的算法都能实现较好的跟踪。而对于图像序列3，由于背景复杂，信噪比低，只有数学形态学算法实现了对小目标较好的跟踪，表现出来优良的跟踪能力。

4 小结

通过实验的计算结果可以看到，采用文中提出的评价方法通过把跟踪算法的各指标进行综合，实现对跟踪算法的性能评价。评价的计算方法灵活、合理，对跟踪算法的评价问题，尤其是对于单凭一项指标无法做出判断的算法的评价，具有较好的参考意义。

[1]高陈强，张天骐，李强，等.几种典型红外弱小目标检测算法的性能评估[J].重庆邮电大学学报:自然科学版，2010，22(3):386 －391.

[2]周进，吴钦章.弱小目标跟踪算法性能评估的研究[J].光电工程，2007，34(1):19－22.

[3]李鹏飞，陈朝武，李晓峰.智能视频算法评估综述[J].计算机辅助设计与图形学学报，2010，22(2):352－360.

[4]Andrew Cilia. Object tracking using cluster of elastically linked feature trackers[J]. Journal of Electronic Imaging 2008，17(2):023019－1－023019－11.

[5]Ruiming Liu，Erqi Liu，Jie Yang，et al. Automatically detect and track infrared small targets with kernel Fukunaga-Koontz transform and Kalman prediction[J]. APPLIED OPTICS，2007 46(31):7780－7791.

[6]袁广林，薛模根，韩裕生，等.基于自适应多特征融合的mean shift目标跟踪[J].计算机研究与发展，2010，47(9):1663－1671.

[7]王相海，方玲玲，丛志环，等.卡尔曼粒子滤波的视频车辆跟踪算法研究[J].中国图象图形学报，2010，15(11):1615－1622.

[8]Cui-yun Li，Hong-bing Ji. Marginalized particle filter based track-before-detect algorithm for small dim infrared target[C]//IEEE.AICI 2009:321－325.

[9]刘献如，蔡自兴，唐王进.基于SAD与UKF-Mean Shift的主动目标跟踪[J].模式识别与人工智能，2010，23(5):646－652.

[10]艾斯卡尔·艾木都拉，王保柱.恒虚警率PDAF的弱点状目标跟踪技术性能分析[J].计算机工程与应用，2009，45(3):168－171.

[11]HU Tao-tao，FAN Xiang，Zhang Yujin，et al. Infrared small target tracking based on SOPC[C]//SPIE. Parallel Processing for Imaging Applications，2011，Vol. 7872:78720U－1－78720U －9.

[12]张杰，唐宏，苏凯，等，效能评估方法研究[M].北京:国防工业出版社，2009.

[13]Lyle M，Dawley，Lenore A Marentette，Long A M.Developing a decision model for joint improvised explosive device defeat organization(JIEDDO)proposal selection，ADA 484369[R]. Department of The Air Force Air University，2008.

[14]任彪，樊祥，马东辉.基于多特征融合与粒子滤波的红外弱小目标跟踪方法[J].弹箭与制导学报，2009，29(5):304－307.

[15]Dorin Comaniciu，Visvanathan Ramesh. Mean shift and optical prediction for efficient object tracking[C]//IEEE International Conference on Image Processing，2000:70－73.

[16]薛丰廷，彭鼎祥.红外跟踪系统中的自适应阈值分割[J].激光与红外，2008，38(4):386 －388.