多摄像机在无重叠区域的目标匹配算法

王晓丽，陆小锋，陆亨立

（上海大学通信与信息工程学院，上海200444）

多摄像机在无重叠区域的目标匹配算法

王晓丽，陆小锋，陆亨立

（上海大学通信与信息工程学院，上海200444）

基于颜色特征的目标匹配方法具有很好的区分性和直观性，但是特征本身受光线变化、背景复杂度等影响而对于目标识别准确率存在差异。针对这一现状，提出了一种新的基于时空局部特征和颜色特征的目标匹配方法。利用时空局部特征3-D LSK对待测视频中的运动目标进行行为识别，识别出具有相同行为目标。再结合目标的颜色特征，通过基于区域权重（Weighted Region Matching）的颜色匹配方法来识别出具有相同颜色的目标。对无重叠区域的多个测试视频进行的相关实验表明，该算法能够有效识别出普通场景下的不同目标，对于衣着颜色相近的不同目标也有很高的识别率。

颜色特征；时空局部特征；无重叠区域

【本文献信息】王晓丽，陆小锋，陆亨立.多摄像机在无重叠区域的目标匹配算法［J］.电视技术，2015，39（10）.

智能视觉监控是当今计算机领域的一个研究热点，其中的一个关键问题是实现多摄像机场景下的运动目标识别，而特征匹配是比较典型的目标识别算法［1-11］。

外部世界对物体提供了丰富的颜色信息，颜色作为物体表面的基本特征，是进行物体识别和认知必不可少的信息。常用的颜色特征匹配方法中，经典的算法是基于颜色直方图（Color-histogram）的目标匹配方法，该方法的基本思想是将目标之间的匹配转换为对应的直方图之间的距离相似度衡量。D.Comaniciu在文献［1］中采用将Color-histogram与巴氏距离相结合的方法来寻找最佳匹配目标的位置。在此基础上Omar Oreifej在文献［3］中提出了基于区域权重的颜色特征匹配方法（Weighted Region Matching，WRM），按照颜色特征的不同把目标分成若干个权重不同的小区域，通过判断区域间的相似性来进行目标匹配。该方法在保证了很好的鲁棒性的同时又提高了目标的识别性能。但是由于颜色特征本身受光线变化、背景复杂度等因素影响而对于不同场景中目标的识别准确率存在差异，为了提高该算法的鲁棒性，引入时空局部特征3-D LSK，改善WRM算法对光照变化敏感的缺陷。

近年来，基于时空局部特征的运动表征方法越来越多的用于视频中的动作识别问题，相关人员已经提出多种特征检测和描述方法。相关的文献结果表明，基于时空特征的运动表示能够更好地适应光照变化、运动者的穿着、运动差异等环境因素的影响，取得更好的识别效果。因此，本文引入时空局部特征来改善颜色特征对光照敏感的缺陷，提高算法鲁棒性。首先对未经预处理的检索视频（Query）和目标视频（Target）提取时空局部转向核（Space-time Local Steering Kernel，3-D LSK）作为人体行为的描述子，基于矩阵余弦相似性的非参数检验，利用特征匹配方法实现简单行为识别，然后再利用目标的颜色特征，通过基于区域权重（Weighted Region Matching）的颜色匹配方法来识别出具有相同颜色的目标。对无重叠区域的多个测试视频进行的相关实验表明，本文提供的算法能够有效识别出普通场景下的不同目标，对于衣着颜色相近的不同目标有很高的识别率。

1　算法的基本思想

现在想要解决的问题是：在无重叠区域拍摄的多个测试视频中，算法能够准确地识别出目标人物（target）。

在简单场景下拍摄了多个测试视频（query），在视频中目标的衣着、基本轮廓和运动行为是清晰可见的。通过这些信息，要求算法能在这一系列query中寻找出target。这就是一个投票者（voter）和候选人（candidate）的问题。如图1所示，把target图像定义为voters，把query图像定义为candidates。因此问题就转换成了从candidates中寻找出voters最为匹配的结果。

图1　投票者-候选人示意图

问题的难点在于candidates中可能有多个和voters衣着颜色相近的对象，那么仅仅用基于区域权重（Weighted Region Matching，WRM）的颜色匹配方法就不能很好地识别出voters。所以在此基础上，对算法进行改进。由于人的运动行为具有好的鲁棒性和特殊性，引入时空局部特征3-D LSK的人体行为识别方法，通过时空局部特征和颜色特征相结合的方法，来有效地识别出voters。

2　基于WRM的特征匹配方法

Weighted Region Matching［3］算法是一种基于区域权重的颜色特征匹配算法，对输入的query图像要进行一系列处理，具体过程如图2所示，分别为：目标检测；目标分割；特征匹配。

图2　WRM算法框图

对图像进行目标检测和分割后，得到voters和candidates的两组图像数据。定义voters的图像组为V=｛vi；i=1，2，…，n｝，定义candidates的图像组为C=｛cj；j=1，2，…，m｝，其中vi和cj为每组图像的某个具体对象。那么cj成为target的概率为

式中：P（）vi，i=1，2，3，…，n为先验概率。假设wi是vj的权重是cj和vi间的归一化距离，则式（1）可改写为

式中：τ为常量。式（2）类似于混合高斯模型，由此公式可知，WRM的重点在于对D（）cj，vi和wi的计算。

2.1目标检检测和分割

本文采用混合高斯背景建模来提取运动目标，使用M个高斯模型来描述图像中各个像素点的特征，在获得新一帧图像后更新混合高斯模型，用当前图像中的每一个像素点与混合高斯模型匹配，如果成功则判定该点为背景点，否则为前景点。Zivkovic在文献［7］中提出了一种自适应的M维混合高斯模型算法，假设图像中的像素在RGB空间中t时刻的取值为x那么采样点x符合的混合高斯分布概率密度函数为

2.2计算EMD距离

从颜色特征提取的角度来说，Mean-Shift［8］平滑和分割算法是一款非常优秀的算法，在分割过程中，它能够突出图像中的各个区域并且使各个区域内平坦。因此本文选用Mean-Shift算法对candidate和voter进行平滑和分割，把目标根据颜色特征的不同分割为不同的几个区域。如图3所示，用EMD［9-10］算法（Earth Mover Distance）计算candidate和voter间的距离，就转化为计算对应区域颜色直方图间的距离。

图3　计算EMD距离

计算EMD的方法来最初是用于解决运输问题，其实质是双向网络最优路径的选择问题。运输问题的描述如下：

假设有几个供应商，每个供应商都有一定数量的货物，需要供应给几个零售商。每个零售商都有一个购买能力的上限，在任何供应商与零售商之间运输一个单位货物的成本是给定的。传输问题就是寻找最小代价货物流，货物从供应商流向零售商，这些货物能满足零售商的要求。

运输问题的目的就是找到一组路径F=［fij］也就是供应商与零售商之间的对应关系，当使用这种双向对应关系时，能够最小化运输货物所要付出的代价，即

它有如下约束条件：fij≥0，它规定了货物的运输只是从供应商到零售商的方向，并不返回。是供应商pi的总供货量，它说明运输货物的总量要小于所有供应商货物的总和是零售商qj的总需求量，它规定了所有零售商的需求都要被满足显然总的需求量应该小于总的供货量。

将该线性流程移植到特征分布的比较中，定义candidate在HSV空间的颜色直方图分布P=｛p1，…，pm｝为供应商，voter在HSV空间的颜色直方图分布Q=｛q1，…，qn｝为零售商，其中P、Q均为HSV彩色空间的色调。定义地面距离矩阵D=［dij，其中dij是pi和qj］之间的地面距离，它是任何距离的度量，可根据具体处理问题的不同灵活选择。本文选择JD［9］距离（Jeffrey-Divergence）作为地面距离，相对于传统相似性度量方法，JD在颜色直方图的计算中具有数值稳定性和对称性，对噪声鲁棒性好等良好特性。由此在式（2）中candidate与voter特征分布间的距离为

2.3计算voter的权重

用Mean-Shift图像分割算法把voter分割为几个区域，每个区域都包含了target的信息，但是有些区域可能本身含有噪声或是在目标提取时引入了噪声。因此，需要对每个区域的权重进行计算，使得包含target信息最多的区域权重最大。定义voter中的区域为R=｛rk｝，则区域rk的权重wk为

式中：wkpr是归一化的PageRank权重，wks是根据区域大小进kk行归一化的权重。因此在式（2）中voter的权重wi就是区域权重的的总和，对其进行归一化得

3　基于3-D LSK的人体行为识别方法

虽然颜色特征有具有很好的区分性和直观性，且对目标的形状和姿态的依赖小，但是由于特征本身受光线变化、背景复杂度等因素影响而对于不同场景中目标的识别准确率存在差异。在此基础上，引入时空局部特征3-D LSK的人体行为识别方法来改善颜色特征匹配的不足，算法系统框图如图4所示。

首先利用MACH Filter对Target视频进行学习训练，得到鲁棒性强的时空匹配模板；然后分别提取Query和时空模板的3-D Lsk，即WQ、WT，并进行PCA［11］降维，得到对应的时空局部特征FQ、FT；计算FQ与FT的矩阵余弦相似性RV，将RV与对应的阈值τ进行比较，从而实现简单行为的识别。对于相同行为的帧再进行WRM算法来判断query中的目标是否为voter，其算法框架如图4所示。

3.1MACH Filter构造时空模板

MACH Filter是由综合鉴别函数（Synthetic Discriminant Function，SDF）演变而来的。针对一组同类的人体行为实例，SDF滤波器通过对4个性能指标的优化，将训练视频图像结合成一个复合模板。这4个性能指标分别是：平均相关高度（Average Correlation Height，ACH）、平均相关能量（Average Correlation Energy，ACE）、平均相似性度量（Average Similarity Measure，ASM）、输出噪声方差（Output Noise Variance，ONV）。MACH Filter是SDF的最佳折衷结果，它具有3个优点：容易探测到相关峰、畸变容差较大、有效抑制复杂背景噪声的能力。本文利用MACH Filter对Target视频进行训练，得到Target视频中目标行为的时空模板，如图5所示。

图4　结合3-DLSK和WRM的目标匹配算法

图5　构造时空模板

首先用Sobel算子得到视频图像的边缘信息，将时空信息转换为频域信息，即对视频库中不同对象的同一行为作三维快速傅里叶变换

式中：f（x，y，t）表示每一帧视频图像的像素值；M、N分别表示图像的行数和列数；L表示视频的帧数；F（）u，v，w表示经过3-D FFT后的频域结果。通过式（9）合成MACH Filter对视频图像进行频域滤波，再作三维快速傅里叶反变换构造时空模板

式中：mx表示视频图像的向量xi的平均值；α，β，γ是用来权衡滤波器性能的参数；C表示对角线噪声协方差矩阵；Dx表示训练视频中象征平均功率谱密度的对角矩阵，其定义如式（10）所示；Sx表示对角线平均相似度矩阵，其定义如式（11）所示。

式中：Ne=L×M×N为训练视频中像素点的总数；Xi表示关于xi的对角矩阵；Mx表示关于mx的对角矩阵。通过MACH Filter最大限度地增强ACH，并降低ACE、ASM和ONV，得到的时空模板具有很强的鲁棒性。

3.23-D LSK特征提取

3-D LSK最初应用于图像降噪、插值、锐化和目标检测，其核心思想是通过梯度估计分析空域和时域上的像素差异，获取图像的局部结构信息，以此来确定一个经典核函数的形状和大小。根据3-D LSK的定义，其计算以及归一化处理如下

利用式（12）、（13）分别计算Query和Target的3-D LSK，即WQ、WT；然后对WQ和WT采用PCA降维，仅保留贡献率为80%信息量的d个特征值；以此构造矩阵AQ、AT并投影到WQ、WT，得到降维后的特征矩阵FQ、FT即为本算法提取的时空局部特征

3.3度量矩阵余弦相似性算法设计

为了分析FQ与FT之间的“距离”，提出一种基于离散余弦相似度的非参数检验方法，其原理类似于计算夹角余弦距离。特征矩阵FQ与FT的余弦相似度定义如式（16）所示。

最后，利用式（17）计算矩阵FQ与FT的矩阵余弦相似性（Resemblance Volume，RV），RV即表示测试视频与目标视频在时空坐标上每一个像素的匹配程度。显然，由于ρi表示特征矩阵FQ与FT的余弦相似性，RV取值随着ρi的增大而增大。

3.4非参数检验

通过控制置信水平来自适应生成阈值τ，将RV（i）与阈值进行比较，从而检测Query中和Target行为相匹配的帧，实现行为识别。其基本运算流程如下：

1）选择一个合适的置信水平值α，即最大容许的误检率。

2）按照从小到大排列的p（i）值，f（p（i））即为关于p（i）的函数。

4）由p（γ）确定阈值τ，并判定RV（i）值大于τ的像素包含与Target相似的行为信息。

在用3-D LSK时空局部特征对Query进行处理后，得到了和Target中具有相似行为的帧，再对这些帧提取颜色特征，用第3节所述的WRM算法进行特征匹配，最终在query中找到和Target行为相同、颜色特征相同的目标。

4　实验结果及分析

本文选用的测试视频主要来源于实验录制视频集。根据实验所需，根据目标颜色和运动行为的不同选取了简单场景下的6个视频集。分别为2个Target视频，4个Query视频，具体信息如表1所示。

表1　实验所选用的6个视频数据集的相关信息

图6为6个视频的实际场景图，每个视频各为40帧，其中图6a、图6b作为Target视频，图6c～f作为Query视频。分别用WRM匹配算法、结合WRM和3-D LSK匹配算法进行两组对比实验。

图66　个视频的实际场景图

实验一是以T1为Target，在Q1、Q2、Q4中寻找与T1中匹配的目标，实验结果如表2所示。对比T1、Q1的实验结果，可以知道T1和Q1中的目标颜色相近，行为相同。WRM算法检测出Q1中有21帧的目标和T1匹配，结合3-D LSK和WRM的算法检测出Q1中有12帧和目标T1匹配。但显而易见Q1中的目标并非T1中的目标，所以这两种算法得出的结果都是错判的。但改进后算法的错检率为30%，优于原来的WRM算法。

表2　在Q1、Q2、Q4的视频集中检测T1中的目标

对比T1、Q2的实验结果，可以知道T1和Q2中的目标颜色相近，行为相同。WRM算法检测出Q2中有20帧的目标和T1匹配，结合3-D LSK和WRM的算法检测出Q2中有15帧和目标T1匹配。知道Q2中的目标就是T1中的目标，所以这两种算法得出的结果都正确的，因此错检率都为0%。

对比T1、Q3的实验结果，可以知道T1和Q3中的目标颜色相近，行为不同。WRM算法检测出Q3中有40帧的目标和T1匹配，结合3-D LSK和WRM的算法检测出Q3中的目标和T1完全不匹配。但显而易见Q3中的目标并非T1中的目标，所以WRM的算法的错检率是100%，它完全错判了目标。而结合3-D LSK和WRM的算法就能完全区分出目标的不同，效果十分优于WRM算法。

实验二是以T2为Target，在Q1、Q3、Q4中寻找与T2中匹配的目标，实验结果如表3所示。对比T2、Q1的实验结果，可以知道T2和Q1中的目标颜色不同，行为相同。WRM算法检测出Q1中有8帧的目标和T2匹配，结合3-D LSK和WRM的算法检测出Q1中有6帧和目标T2匹配。但显而易见Q1中的目标并非T2中的目标，所以这两种算法得出的结果都是错判的。但改进后算法的错检率为15%，优于原来的WRM算法。

表3　在Q1、Q3、Q4的视频集中检测T2中的目标

对比T2、Q3的实验结果，可以知道T2和Q3中的目标颜色相近，行为相同。WRM算法检测出Q3中有40帧的目标和T2匹配，结合3-D LSK和WRM的算法检测出Q3中有31帧和目标T2匹配。知道Q3中的目标就是T2中的目标，所以这两种算法得出的结果都正确的，因此错检率都为0%。

对比T2、Q4的实验结果，可以知道T2和Q4中的目标颜色不同，行为不同。两种算法都检测出Q4中的目标和T2完全不匹配。因此对于颜色不同，行为不同的情况，两种算法效果相同。

综合表1和表2的实验数据可以发现，对于颜色不同，行为不同的目标间匹配，两种算法检测效果完全相同。对于颜色不同，行为相同和衣着颜色相同，行为相同的目标间匹配，两种算法检测效果基本相近。对于颜色相同，但行为不同的目标匹配，结合3-D LSK和WRM算法的效果要优于WRM的效果。

5　结束语

本文针对视频监控中目标匹配的难点问题，在基于WRM颜色特征匹配的基础上，提出一种新的结合3-D LSK和WRM的目标匹配算法。该方法先对待测视频中的运动目标进行行为识别，识别出具有相同行为目标。然后在利用目标的颜色特征，通过基于区域权重的颜色匹配方法来识别出具有相同颜色的目标。与近期文献的结果相比，本方法对于颜色相近、行为不同的目标间的匹配有显著的识别效果。

［1］COMANICIU D，RAMESH V，MEER P.Real-time tracking of non-rigid objects using mean shift［C］//Proc.IEEE Conference on Computer Vision and Pattern Recognition.［S.l.］：IEEE Press，2000：142-149.

［2］LOWE D G.Distinctive image features from scale-invariant keypoints［J］.International Journal of Computer Vision，2004，60（2）：91-110.

［3］OREIFEJ O，MEHRAN R，SHAH M.Human identity recognition in aerial images［C］//Proc.IEEE Conference on Computer Vision and Pattern Recognition（CVPR 2010）.［S.l.］：IEEE Press，2010：709-716.

［4］NIEBLES J C，WANG H，FEI F L.Unsupervised learning of human action categories using spatial-temporal words［J］.International Journal of Computer Vision，2008，79（3）：299-318.

［5］RYOO M S，AGGARWAL J K.Spatio-temporal relationship match：video structure comparison for recognition of complex human activities［C］//Proc.IEEE 12th International Conference on Computer Vision.［S.l.］：IEEE Press，2009：1593-1600.

［6］SEO H J，MILANFAR P.Action recognition from one example［J］. IEEE Trans.Pattern Analysis and Machine Intelligence，2011，33（5）：867-882.

［7］ZIVKOVIC Z.Improved adaptive Gaussian mixture model for background subtraction［C］//Proc.17th IEEE International Conference on Pattern Recognition（ICPR 2004）.［S.l.］：IEEE Press，2004：28-31.

［8］CUI J，MA D L，YU M Y，et al.Research of remote sensing image segmentation based on mean shift and region merging［J］.Applied Mechanics and Materials，2011（90）：2836-2839.

［9］PUZICHA J，BUHMANN J M，RUBNER Y，et al.Empirical evaluation of dissimilarity measures for color and texture［C］// Proc.7th IEEE International Conference on Computer Vision，1999.［S.l.］：IEEE Press，1999：1165-1172.

［10］RUBNER Y，TOMASI C，GUIBAS L J.The earth mover's distance as a metric for image retrieval［J］.International Journal of Computer Vision，2000，40（2）：99-121.

［11］王鹤，谢刚.基于PCA-SIFT特征的目标识别算法［J］.电视技术，2013，37（15）：30-32.

Target Matching Algorithm in Multiple Non-overlapping Cameras

WANG Xiaoli，LU Xiaofeng，LU Hengli
（School of Communication and Information Engineering，Shanghai University，Shanghai 200444，China）

The target matching method of color features has good distinction and intuition，but small dependence on the shape and attitude of the target.Due to factors such as illumination change and background complexity，the performance of the object matching method varies in different scenarios.With respect to the current situation，this paper proposes a new target matching algorithm，combining with space-time local features and color features.Firstly，3-D LSK（space-time local steering kernel）features are used to identify the behavior of moving targets in video. ThencolorfeaturesandWeightedRegionMatchingmethodareusedtoidentifytargetswiththesamecolor. Experimental results on several test videos in non-overlapping areas show that the new algorithm can effectively identify the different targets in common scenarios，especially for different targets dressed similar color.

color features；space-time local features；non-overlapping area

TP391

A

10.16280/j.videoe.2015.10.003

时雯

2014-07-23

王晓丽，女，研究生，主研图像处理。