王佐成,盧 宇，薛麗霞

(1.中國電子科技集團公司第三十八研究所，合肥 230088；2.安徽四創(chuàng)電子股份有限公司，合肥 230088；3.合肥工業(yè)大學(xué) 計算機與信息學(xué)院， 合肥 230009)

?

基于部分有界互相關(guān)圖像匹配算法的車輛視頻跟蹤

王佐成1,2,盧 宇2,3，薛麗霞3

(1.中國電子科技集團公司第三十八研究所，合肥 230088；2.安徽四創(chuàng)電子股份有限公司，合肥 230088；3.合肥工業(yè)大學(xué) 計算機與信息學(xué)院， 合肥 230009)

歸一化互相關(guān)算法作為一種基于窮舉原理的塊匹配方法，其計算精度高、魯棒性好，但計算量大。為提高圖像相關(guān)匹配算法的搜索速度，在傳統(tǒng)的有界部分相關(guān)算法基礎(chǔ)上，提出了以自適應(yīng)二分法為基礎(chǔ)的匹配方式，將模板圖像的每行分成灰度高低不同的兩塊，依據(jù)兩塊的灰度高低先后進(jìn)行相關(guān)計算。該算法保持了邊界部分相關(guān)算法速度快的優(yōu)點，同時在每次搜索中給出更高的閾值，過濾掉不符合要求的匹配點，從而加快了有界部分相關(guān)算法的計算速度。實驗結(jié)果表明：改進(jìn)后的算法在精度不變的情況下運算速度得到提升，能夠快速準(zhǔn)確地跟蹤行駛中的車輛。

快速歸一化互相關(guān)；有界部分相關(guān)；自適應(yīng)二分法；視頻跟蹤

視頻跟蹤是智能交通領(lǐng)域的基礎(chǔ)問題之一，是目標(biāo)識別等后續(xù)應(yīng)用的基礎(chǔ)，在平安城市、智慧城市、智能交通等方面有重要應(yīng)用前景。視頻跟蹤應(yīng)用廣泛，如何快速準(zhǔn)確地跟蹤成為當(dāng)前研究熱點。傳統(tǒng)光流法速度慢，不能適應(yīng)實時跟蹤要求。歸一化互相關(guān)算法[1-4]作為一種經(jīng)典的算法被廣泛應(yīng)用于運動跟蹤、圖像匹配、視頻壓縮，其優(yōu)點是匹配精度高、魯棒性強。但是作為一種基于窮舉原理(exhaustive search method，ESM)的塊匹配算法(block matching algorithm，BMA)，其計算過程中需要遍歷原圖像中的每一個待匹配點才能尋找到最佳匹配點。

J.P.Lewis[5]對歸一化互相關(guān)公式的分子、分母分別采用不同的方式進(jìn)行快速計算，該算法稱為快速歸一化互相關(guān)算法。分子采用快速傅里葉變換進(jìn)行卷積計算；分母采用累加和、平方累加和方式計算，避免計算重復(fù)區(qū)域。但在分子計算時，當(dāng)模板圖像尺寸遠(yuǎn)小于待匹配圖像時，快速傅里葉法不具備速度上的優(yōu)勢。Jianwen Luo等[6]采用滑動方法進(jìn)行一維相關(guān)匹配，但滑動方法本質(zhì)上與累加和、累加平方和一致。A.J.H.Hii等[7]提出在黑白圖像中用近似矩形匹配，速度較快速歸一化互相關(guān)算法更快，但使用范圍僅限于黑白斑點，不適合灰度圖像。Yong-sheng Chen 等[8]提出的優(yōu)選法不需要計算所有待匹配點的相關(guān)系數(shù)即可找到平均絕對差(mean absolute difference， MAD)最小的匹配區(qū)域，但這種方法不適用于變形圖像。Laura Rebollo等[9]采用對信號進(jìn)行降維的方法進(jìn)行圖像匹配，但模板圖像降維耗時長，且由于與原圖像存在灰度差，降維后如閾值選取不當(dāng)容易存在誤匹配現(xiàn)象。W.Li 等[10]采用逐步消除法(successive elimination algorithm,SEA)來測量模板圖像與待匹配圖像的平均絕對差,從而進(jìn)行圖像匹配。但該方法魯棒性差，不適合匹配變形圖像。Shao-Wei Liu等[11]改進(jìn)了SEA法，采用梯度將模板圖像劃分為若干子區(qū)域。但該方法設(shè)計復(fù)雜，且未能克服逐步消除法的缺點。Huan-Sheng Wang等[12-13]進(jìn)一步改進(jìn)了逐步消除法，將消除法與部分變形消除法(partial distortion elimination,PDE)結(jié)合。

Luigi Di Stefano等結(jié)合逐步消除法和部分變形消除法的優(yōu)點設(shè)計出有界部分相關(guān)算法(bounded partial correlation,BPC)[14]。每次均計算所有待匹配點部分區(qū)域的相關(guān)系數(shù)，逐步增加匹配計算區(qū)域，不斷剔除相關(guān)系數(shù)小于閾值的待匹配點，從而達(dá)到減少計算量的目的。但由于閾值設(shè)置采用詹森不等式而過大，因此又改進(jìn)了閾值設(shè)置方法，采用柯西-施瓦茨不等式后，減小了閾值設(shè)置[15]。但是有界部分相關(guān)算法以每一行作為步長計算，無法根據(jù)模板圖像中灰度變化改變步長。因此，本文提出了一種變步長的自適應(yīng)二分法，將每一步計算分成兩部分，從而提高了匹配計算速度。

1 歸一化互相關(guān)算法

1.1 快速歸一化互相關(guān)算法

快速歸一化圖像匹配算法是J.P.Lewis提出的一種匹配算法，其原理如下[5]：在一幅大小為M×N的原圖像中選取一塊大小為(2n+1)×(2n+1)的模板區(qū)域，匹配這塊模板區(qū)域與原圖像，找到模板區(qū)域的位置，使用式(1)的歸一化互相關(guān)函數(shù)計算。

(1)

其中：f為原圖像的灰度分布；g為模板圖像的灰度分布；x、y表示遍歷模板區(qū)域圖像的坐標(biāo)點；u、v表示模板區(qū)域在原圖像中的位置。當(dāng)CNCC的絕對值最大時(CNCC(u,v)的取值范圍為[0,1])，所對應(yīng)的最大值點即為匹配點。

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)表示累加和與平方累加和。規(guī)定u,v≤0時s(u,v)、s2(u,v)均為0，則f在(u,v)位置上與模板圖像同樣大小的子區(qū)域的累加和與平方累加和為：

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)

在使用累加表后，分母部分的計算結(jié)果不再依賴于模板大小，而是僅僅依賴于原圖像大小。

對于分子部分，采用先轉(zhuǎn)換為卷積后用快速傅里葉變化方法計算。但是利用FFT的FNCC的計算速度并不總是快于直接空間域上的計算速度。當(dāng)原圖像大小遠(yuǎn)大于模板圖像大小時，NCC速度較有優(yōu)勢。因此，針對空域上的匹配計算，有人提出了有界部分相關(guān)算法。

1.2 傳統(tǒng)有界部分相關(guān)算法

傳統(tǒng)的有界部分相關(guān)算法先假設(shè)存在一個變量B(u,v)為C(u,v)的上界，則

(6)

設(shè)CNCC max為當(dāng)前相關(guān)最大值，則如果在點(u,v)處的消除條件為

≤CNCC max

(7)

當(dāng)不等式(7)成立時，匹配算法將繼續(xù)計算下一個點的相關(guān)系數(shù)，該點剔除；反之，當(dāng)不等式(7)不成立時，則需要計算當(dāng)前點的相關(guān)系數(shù)CNCC(u,v)。

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

…

(8)

其中1≤q≤2n+1。

不等號右邊的通用表達(dá)式可以寫成

(9)

圖1中給出式(9)中B、C二者的關(guān)系。圖1中，C作為相關(guān)計算部分，B作為平方累加和部分，兩部分之和用于計算D。

圖1 傳統(tǒng)有界部分化相關(guān)算法原理圖

2 本文提出的自適應(yīng)二分法有界部分相關(guān)算法

由以上分析可以看出：傳統(tǒng)的有界部分相關(guān)算法在匹配過程中逐行增加用于相關(guān)計算的點個數(shù)，并計算部分區(qū)域相關(guān)系數(shù)，在完成全幅模板匹配前提前淘汰不滿足條件的待匹配子區(qū)域。但是這種方法計算相關(guān)量是按行進(jìn)行的，接下來本文將討論另一種匹配點計算順序。該方法根據(jù)灰度分布的不同，對模板圖像的每一行分成兩塊，優(yōu)先匹配灰度高的塊，更早剔除不符合要求的待匹配點，從而提高匹配速度。

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

2) 選取subi最大值，將該按i位置將該行分成2部分。

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

4) 比較已分割的兩部分灰度，將灰度高的部分標(biāo)記為0，低的部分標(biāo)記為1。

通過上述步驟可將模板圖像的每行劃分為灰度高、灰度低2部分。

圖2所示為本文提出的方法原理。

圖2 自適應(yīng)二分法有界部分互相關(guān)原理

圖2中：對第q行以下部分按灰度大小分成2塊，并用左、右箭頭標(biāo)記灰度高的區(qū)域，匹配計算時首先計算灰度值高的區(qū)域。第qmid行所示分割點選取在行的中間。設(shè)pdiv表示每行的分割位置。則對式(9)可改寫為：

(10)

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

將自適應(yīng)二分法引入有界部分互相關(guān)算法，本文提出了自適應(yīng)有界部分互相關(guān)匹配法。具體步驟為：

1) 對模板圖像采用自適應(yīng)二分法處理。

2) 對模板圖像和原圖像進(jìn)行平方累加和計算。

5) 將式(10)計結(jié)果歸一化后與CNCCmax比較，如果小于則標(biāo)記該點為剔除點；否則計算該點的相關(guān)系數(shù)，如果大于CNCC max則替換。

6) 計算灰度值低的區(qū)域的相關(guān)結(jié)果，并與平方和累加，計算結(jié)果與CNCC max比較，如果小于該值，則標(biāo)記該點為剔除點；否則計算該點的相關(guān)系數(shù)，如果大于CNCC max則替換。

7) 重復(fù)步驟 3)～6)，直到剩下1個待匹配點。

3 實驗與分析

在Intel Core i5-6200u 2.3 GHz、 內(nèi)存為4 GB的計算機上，使用Matlab 8.3編寫程序進(jìn)行實驗。

3.1 實驗設(shè)計

實驗共分4組，待匹配圖像如圖3所示。模板圖像為圖3(a1)、(a2) 、(a3) 、(a4)，原圖為圖3(I1)、(I2) 、(I3) 、(I4)。

圖3 (b1)、(b2)、(b3)、(b4)給出了自適應(yīng)二分法的分割結(jié)果，紅色點表示分割點?？梢钥闯黾t色標(biāo)記點多位于圖像明暗分界上，但有部分分割點位于行的中間位置。

圖3 模板圖像與原圖像

3.2 實驗結(jié)果及分析

為了驗證本算法的執(zhí)行速度，先將本算法與NCC法、BPC算法、對稱二分法進(jìn)行對比。其中對稱二分法是將每行的中心點作為分界點。表1給出了4種算法的計算精度。表2給出了4種算法的執(zhí)行時間。

表1 算法匹配計算結(jié)果像素

參數(shù)I1I2I3I4匹配點位置(3，7)(1，5)(23，22)(19，13)

從表1中每個圖像僅列出了一個匹配點位置，這是因為4種算法的匹配原理是一致，都是采用最大相關(guān)值的坐標(biāo)點作為匹配點，因此計算位置結(jié)果相同。

在表2中，圖像1和圖像2在NCC算法時計算時間接近。然而當(dāng)使用傳統(tǒng)BPC法和本算法時，計算時間卻有較大差異，這是因為兩幅圖片的灰度分布不同，造成每次迭代時待匹配點的剔除速度不同。圖4中給出了圖像I1和圖像I2的收斂速度。圖像I1和圖像I2大小為150×150，對應(yīng)的模板大小為61×61，因此搜索區(qū)域都是90×90，搜索點有8 100個。

表2 算法計算時間 s

圖4中虛線是傳統(tǒng)二分法的收斂速度，實線是本算法的收斂速度。從圖4(a)中可以看出：本算法從第32行開始剔除待匹配點。而圖4(b)中則是從第39行開始收斂，因此表現(xiàn)在計算速度上，圖像I1較圖像I2要快。圖4中，對稱二分法的收斂折線與本文提出的方法的收斂折線總是不斷相交，相交點即為BPC法在對模板圖像每行計算后的收斂點。

圖4 圖像I1和圖像I2的收斂速度

4 結(jié)束語

為了解決視頻跟蹤搜索效率問題，本文提出了自適應(yīng)二分法，在進(jìn)行相關(guān)計算時對模板圖像的每行進(jìn)行分割，將每行分為灰度值高、低兩部分，灰度值高區(qū)域先計算，灰度值低區(qū)域后計算，從而加速了不符合要求的待匹配點的過濾速度，減少了匹配計算時間。但這種按行進(jìn)行劃分的方式對相關(guān)計算速度提高能力有限。后續(xù)工作將對若干行的灰度按一定規(guī)律進(jìn)行劃分，得到更快的相關(guān)計算速度和匹配速度。

[1] 陳沈軼,錢徽,吳錚,等.模板圖像匹配中互相關(guān)的一種快速算法[J].傳感技術(shù)學(xué)報,2007,20(6):1325-1326.

[2] 程紅，陳文劍，孫文邦.一種改進(jìn)的快速歸一化積相關(guān)圖像匹配算法[J].光電工程,2013,40(1):119-125.

[3] 王曉冬,霍宏,方濤.基于快速歸一化互相關(guān)函數(shù)的運動車輛陰影檢測算法[J].計算機應(yīng)用,2006,26(9):2065-2067.

[4] 吳強,任琳,張杰,李昂.快速歸一化互相關(guān)算法及DSP 優(yōu)化實現(xiàn)[J].電子測量與儀器學(xué)報,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.

(責(zé)任編輯 劉 舸)

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 基金項目：中央高?；究蒲袠I(yè)務(wù)費專項資金資助項目(JZ2014HGBZ0059)

王佐成(1973—)，男，四川巴中人，博士，高級工程師，主要從事視頻圖像，軟件工程研究，E-mail：cswangzc@163.com。

王佐成,盧宇，薛麗霞.基于部分有界互相關(guān)圖像匹配算法的車輛視頻跟蹤[J].重慶理工大學(xué)學(xué)報(自然科學(xué))，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