基于部分有界互相关图像匹配算法的车辆视频跟踪

王佐成,卢 宇，薛丽霞

(1.中国电子科技集团公司第三十八研究所，合肥 230088；2.安徽四创电子股份有限公司，合肥 230088；3.合肥工业大学 计算机与信息学院， 合肥 230009)



基于部分有界互相关图像匹配算法的车辆视频跟踪

王佐成1,2,卢 宇2,3，薛丽霞3

(1.中国电子科技集团公司第三十八研究所，合肥 230088；2.安徽四创电子股份有限公司，合肥 230088；3.合肥工业大学 计算机与信息学院， 合肥 230009)

归一化互相关算法作为一种基于穷举原理的块匹配方法，其计算精度高、鲁棒性好，但计算量大。为提高图像相关匹配算法的搜索速度，在传统的有界部分相关算法基础上，提出了以自适应二分法为基础的匹配方式，将模板图像的每行分成灰度高低不同的两块，依据两块的灰度高低先后进行相关计算。该算法保持了边界部分相关算法速度快的优点，同时在每次搜索中给出更高的阈值，过滤掉不符合要求的匹配点，从而加快了有界部分相关算法的计算速度。实验结果表明：改进后的算法在精度不变的情况下运算速度得到提升，能够快速准确地跟踪行驶中的车辆。

快速归一化互相关；有界部分相关；自适应二分法；视频跟踪

视频跟踪是智能交通领域的基础问题之一，是目标识别等后续应用的基础，在平安城市、智慧城市、智能交通等方面有重要应用前景。视频跟踪应用广泛，如何快速准确地跟踪成为当前研究热点。传统光流法速度慢，不能适应实时跟踪要求。归一化互相关算法[1-4]作为一种经典的算法被广泛应用于运动跟踪、图像匹配、视频压缩，其优点是匹配精度高、鲁棒性强。但是作为一种基于穷举原理(exhaustive search method，ESM)的块匹配算法(block matching algorithm，BMA)，其计算过程中需要遍历原图像中的每一个待匹配点才能寻找到最佳匹配点。

J.P.Lewis[5]对归一化互相关公式的分子、分母分别采用不同的方式进行快速计算，该算法称为快速归一化互相关算法。分子采用快速傅里叶变换进行卷积计算；分母采用累加和、平方累加和方式计算，避免计算重复区域。但在分子计算时，当模板图像尺寸远小于待匹配图像时，快速傅里叶法不具备速度上的优势。Jianwen Luo等[6]采用滑动方法进行一维相关匹配，但滑动方法本质上与累加和、累加平方和一致。A.J.H.Hii等[7]提出在黑白图像中用近似矩形匹配，速度较快速归一化互相关算法更快，但使用范围仅限于黑白斑点，不适合灰度图像。Yong-sheng Chen 等[8]提出的优选法不需要计算所有待匹配点的相关系数即可找到平均绝对差(mean absolute difference， MAD)最小的匹配区域，但这种方法不适用于变形图像。Laura Rebollo等[9]采用对信号进行降维的方法进行图像匹配，但模板图像降维耗时长，且由于与原图像存在灰度差，降维后如阈值选取不当容易存在误匹配现象。W.Li 等[10]采用逐步消除法(successive elimination algorithm,SEA)来测量模板图像与待匹配图像的平均绝对差,从而进行图像匹配。但该方法鲁棒性差，不适合匹配变形图像。Shao-Wei Liu等[11]改进了SEA法，采用梯度将模板图像划分为若干子区域。但该方法设计复杂，且未能克服逐步消除法的缺点。Huan-Sheng Wang等[12-13]进一步改进了逐步消除法，将消除法与部分变形消除法(partial distortion elimination,PDE)结合。

Luigi Di Stefano等结合逐步消除法和部分变形消除法的优点设计出有界部分相关算法(bounded partial correlation,BPC)[14]。每次均计算所有待匹配点部分区域的相关系数，逐步增加匹配计算区域，不断剔除相关系数小于阈值的待匹配点，从而达到减少计算量的目的。但由于阈值设置采用詹森不等式而过大，因此又改进了阈值设置方法，采用柯西-施瓦茨不等式后，减小了阈值设置[15]。但是有界部分相关算法以每一行作为步长计算，无法根据模板图像中灰度变化改变步长。因此，本文提出了一种变步长的自适应二分法，将每一步计算分成两部分，从而提高了匹配计算速度。

1 归一化互相关算法

1.1 快速归一化互相关算法

快速归一化图像匹配算法是J.P.Lewis提出的一种匹配算法，其原理如下[5]：在一幅大小为M×N的原图像中选取一块大小为(2n+1)×(2n+1)的模板区域，匹配这块模板区域与原图像，找到模板区域的位置，使用式(1)的归一化互相关函数计算。

(1)

其中：f为原图像的灰度分布；g为模板图像的灰度分布；x、y表示遍历模板区域图像的坐标点；u、v表示模板区域在原图像中的位置。当CNCC的绝对值最大时(CNCC(u,v)的取值范围为[0,1])，所对应的最大值点即为匹配点。

s(u,v)=f(u,v)+s(u-1,v)+

s(u,v-1)-s(u-1,v-1)

(2)

s2(u,v)=f2(u,v)+s2(u-1,v)+

s2(u,v-1)-s2(u-1,v-1)

(3)

其中s(u,v)、s2(u,v)表示累加和与平方累加和。规定u,v≤0时s(u,v)、s2(u,v)均为0，则f在(u,v)位置上与模板图像同样大小的子区域的累加和与平方累加和为：

ef1(u,v)=s(u+(2n+1)-1,v+(2n+1)-1)-s(u-1,v+(2n+1)-1)-s(u+(2n+1)-1,v-1)+s(u-1,v-1)

(4)

ef2(u,v)=s2(u+(2n+1)-1,v+(2n+1)-1)-s2(u-1,v+(2n+1)-1)-s2(u+(2n+1)-1,v-1)+s2(u-1,v-1)

(5)

在使用累加表后，分母部分的计算结果不再依赖于模板大小，而是仅仅依赖于原图像大小。

对于分子部分，采用先转换为卷积后用快速傅里叶变化方法计算。但是利用FFT的FNCC的计算速度并不总是快于直接空间域上的计算速度。当原图像大小远大于模板图像大小时，NCC速度较有优势。因此，针对空域上的匹配计算，有人提出了有界部分相关算法。

1.2 传统有界部分相关算法

传统的有界部分相关算法先假设存在一个变量B(u,v)为C(u,v)的上界，则

(6)

设CNCC max为当前相关最大值，则如果在点(u,v)处的消除条件为

≤CNCC max

(7)

当不等式(7)成立时，匹配算法将继续计算下一个点的相关系数，该点剔除；反之，当不等式(7)不成立时，则需要计算当前点的相关系数CNCC(u,v)。

采用柯西-施瓦茨不等式定义B(u,v)，则C(u,v) 可分解为：

…

(8)

其中1≤q≤2n+1。

不等号右边的通用表达式可以写成

(9)

图1中给出式(9)中B、C二者的关系。图1中，C作为相关计算部分，B作为平方累加和部分，两部分之和用于计算D。

图1 传统有界部分化相关算法原理图

2 本文提出的自适应二分法有界部分相关算法

由以上分析可以看出：传统的有界部分相关算法在匹配过程中逐行增加用于相关计算的点个数，并计算部分区域相关系数，在完成全幅模板匹配前提前淘汰不满足条件的待匹配子区域。但是这种方法计算相关量是按行进行的，接下来本文将讨论另一种匹配点计算顺序。该方法根据灰度分布的不同，对模板图像的每一行分成两块，优先匹配灰度高的块，更早剔除不符合要求的待匹配点，从而提高匹配速度。

1) 令subi=q1,i-pi+1,2n+1。

2) 选取subi最大值，将该按i位置将该行分成2部分。

3) 如果i∉[(2n+1)/4,3·(2n+1)/4]，则i定位在n。

4) 比较已分割的两部分灰度，将灰度高的部分标记为0，低的部分标记为1。

通过上述步骤可将模板图像的每行划分为灰度高、灰度低2部分。

图2所示为本文提出的方法原理。

图2 自适应二分法有界部分互相关原理

图2中：对第q行以下部分按灰度大小分成2块，并用左、右箭头标记灰度高的区域，匹配计算时首先计算灰度值高的区域。第qmid行所示分割点选取在行的中间。设pdiv表示每行的分割位置。则对式(9)可改写为：

(10)

其中pdiv表示q行上分割点的位置。

将自适应二分法引入有界部分互相关算法，本文提出了自适应有界部分互相关匹配法。具体步骤为：

1) 对模板图像采用自适应二分法处理。

2) 对模板图像和原图像进行平方累加和计算。

5) 将式(10)计结果归一化后与CNCCmax比较，如果小于则标记该点为剔除点；否则计算该点的相关系数，如果大于CNCC max则替换。

6) 计算灰度值低的区域的相关结果，并与平方和累加，计算结果与CNCC max比较，如果小于该值，则标记该点为剔除点；否则计算该点的相关系数，如果大于CNCC max则替换。

7) 重复步骤 3)～6)，直到剩下1个待匹配点。

3 实验与分析

在Intel Core i5-6200u 2.3 GHz、 内存为4 GB的计算机上，使用Matlab 8.3编写程序进行实验。

3.1 实验设计

实验共分4组，待匹配图像如图3所示。模板图像为图3(a1)、(a2) 、(a3) 、(a4)，原图为图3(I1)、(I2) 、(I3) 、(I4)。

图3 (b1)、(b2)、(b3)、(b4)给出了自适应二分法的分割结果，红色点表示分割点。可以看出红色标记点多位于图像明暗分界上，但有部分分割点位于行的中间位置。

图3 模板图像与原图像

3.2 实验结果及分析

为了验证本算法的执行速度，先将本算法与NCC法、BPC算法、对称二分法进行对比。其中对称二分法是将每行的中心点作为分界点。表1给出了4种算法的计算精度。表2给出了4种算法的执行时间。

表1 算法匹配计算结果像素

参数I1I2I3I4匹配点位置(3，7)(1，5)(23，22)(19，13)

从表1中每个图像仅列出了一个匹配点位置，这是因为4种算法的匹配原理是一致，都是采用最大相关值的坐标点作为匹配点，因此计算位置结果相同。

在表2中，图像1和图像2在NCC算法时计算时间接近。然而当使用传统BPC法和本算法时，计算时间却有较大差异，这是因为两幅图片的灰度分布不同，造成每次迭代时待匹配点的剔除速度不同。图4中给出了图像I1和图像I2的收敛速度。图像I1和图像I2大小为150×150，对应的模板大小为61×61，因此搜索区域都是90×90，搜索点有8 100个。

表2 算法计算时间 s

图4中虚线是传统二分法的收敛速度，实线是本算法的收敛速度。从图4(a)中可以看出：本算法从第32行开始剔除待匹配点。而图4(b)中则是从第39行开始收敛，因此表现在计算速度上，图像I1较图像I2要快。图4中，对称二分法的收敛折线与本文提出的方法的收敛折线总是不断相交，相交点即为BPC法在对模板图像每行计算后的收敛点。

图4 图像I1和图像I2的收敛速度

4 结束语

为了解决视频跟踪搜索效率问题，本文提出了自适应二分法，在进行相关计算时对模板图像的每行进行分割，将每行分为灰度值高、低两部分，灰度值高区域先计算，灰度值低区域后计算，从而加速了不符合要求的待匹配点的过滤速度，减少了匹配计算时间。但这种按行进行划分的方式对相关计算速度提高能力有限。后续工作将对若干行的灰度按一定规律进行划分，得到更快的相关计算速度和匹配速度。

[1] 陈沈轶,钱徽,吴铮,等.模板图像匹配中互相关的一种快速算法[J].传感技术学报,2007,20(6):1325-1326.

[2] 程红，陈文剑，孙文邦.一种改进的快速归一化积相关图像匹配算法[J].光电工程,2013,40(1):119-125.

[3] 王晓冬,霍宏,方涛.基于快速归一化互相关函数的运动车辆阴影检测算法[J].计算机应用,2006,26(9):2065-2067.

[4] 吴强,任琳,张杰,李昂.快速归一化互相关算法及DSP 优化实现[J].电子测量与仪器学报,2011,25(6):495-496.

[5] LEWIS J P.Fast Normalized Cross-Correlation [J].Industrial Light & Magic,1995,10:1-7.

[6] LUO Jianwen,ELISA E.Konofagou.A Fast Normalized Cross-Correlation Calculation Method for Motion Estimation [J].IEEE Transactions on Ultrasonics,Feerroelectrics,and Frequency Control,2010,57(6):1347-1357.

[7] HII A J H,HANN C E,CHASE J G,et al.Fast normalized cross correlation for motion tracking using basis functions [J].Computer methods and programs in biomedicine,2006,8(2):144-156.

[8] CHEN Yongsheng,HUNG Yiping,FUH Chioushann.Fast Block Matching Algorithm Based on the Winner-Update Strategy [J].IEEE Transactions on Image Processing,2001,10(8):1212-1223.

[9] LAURA R N,DAVID L.Optimized Orthogonal Matching Pursuit Approach [J].IEEE Signal Processing Letters,2002,9(4):137-141.

[10]LI W,SALARI E.Successive Elimination Algorithm for Motion Estimation [J].IEEE Transactions on Image Processing,1995,4(1):105-108.

[11]LIU S W,WEI,S D,LAI S H.Fast Optimal Motion Estimation Based on Gradient-Based Adaptive Multilevel Successive Elimination [J].IEEE Transactions on Circuits and Systems for Video Technology,2008,18(2):263-268.

[12]WANG H S,MERSEREAU R M.Fast Algorithms for the Estimation of Motion Vectors [J].IEEE Transactions on Image Processing,1999,8(3):435-436.

[13]BEI C D,GRAY R M.An Improvement of the Minimum Distorsion Encoding Algorithm for Vector Quantization [J].IEEE Transaction on Commun,1985,VOL33:1132-1133.

[14]Di STEFANO L,MATTOCCIA S.Fast template matching using bounded partial correlation [J].Machine Vision and Applications，2003,13(2):213-221.

[15]Di STEFANOL,MATTOCCIA S.A sufficient condition based on the cauchy-schwarz inequality for efficient template matching[J].Image Processing,2003(1)：269-272.

(责任编辑 刘 舸)

Vehicle Video Tracking Based on Adaptive Dichotomy Bounded Partial Correlation Image Match Algorithm

WANG Zuo-cheng1,2, LU Yu2,3, XUE Li-xia3

(1.The 38thResearch Institute of China Electronics Technology Group Corporation, Hefei 230088, China; 2.Anhui Sun Create Electronic Co., Ltd., Hefei 230088, China; 3.School of Computer and Information, Hefei University of Technology, Hefei 230009, China)

Normalized cross correlation algorithm is a sort of block matching algorithm based on exhaustive full field image search with advantage of high matching precision and robustness. While it is time consuming for object video tracking. In order to improve the speed of image correlation, the adaptive dichotomy bounded partial correlation method were improved. The template image is divided into two parts in every row by gray scale. The part with high gray scales will be calculate first and then the part of low will be calculated, and the candidate points of matching which are not meet the requirements will be removed. The speed of image tracking will improve with same accuracy. This algorithm is applied to vehicle video tracking and it can track the vehicle in progress quickly and accurately.

normalized cross correlation; partial correlation of bounded parts; adaptive dichotomy bounded partial correlation; video track

2017-03-08 基金项目：中央高校基本科研业务费专项资金资助项目(JZ2014HGBZ0059)

王佐成(1973—)，男，四川巴中人，博士，高级工程师，主要从事视频图像，软件工程研究，E-mail：cswangzc@163.com。

王佐成,卢宇，薛丽霞.基于部分有界互相关图像匹配算法的车辆视频跟踪[J].重庆理工大学学报(自然科学)，2017(6):147-153.

format：WANG Zuo-cheng, LU Yu, XUE Li-xia.Vehicle Video Tracking Based on Adaptive Dichotomy Bounded Partial Correlation Image Match Algorithm[J].Journal of Chongqing University of Technology(Natural Science)，2017(6):147-153.

10.3969/j.issn.1674-8425(z).2017.06.022

TP391

A

1674-8425(2017)06-0147-07