Zhu Zhou Lu Xiaobo

(1School of Transportation, Southeast University, Nanjing 210096, China)(2School of Automation, Southeast University, Nanjing 210096, China)(3Key Laboratory of Measurement and Control of Complex Systems of Engineering of Ministry of Education,Southeast University, Nanjing 210096, China)

?

Video-based vehicle tracking considering occlusion

Zhu Zhou1,3Lu Xiaobo2,3

(1School of Transportation, Southeast University, Nanjing 210096, China)(2School of Automation, Southeast University, Nanjing 210096, China)(3Key Laboratory of Measurement and Control of Complex Systems of Engineering of Ministry of Education,Southeast University, Nanjing 210096, China)

To track the vehicles under occlusion, a vehicle tracking algorithm based on blocks is proposed. The target vehicle is divided into several blocks of uniform size, in which the edge block can overlap its neighboring blocks. All the blocks’ motion vectors are estimated, and the noise motion vectors are detected and adjusted to decrease the error of motion vector estimation. Then, by moving the blocks based on the adjusted motion vectors, the vehicle is tracked. Aiming at the occlusion between vehicles, a Markov random field is established to describe the relationship between the blocks in the blocked regions. The neighborhood of blocks is defined using the Euclidean distance. An energy function is defined based on the blocks’ histograms and optimized by the simulated annealing algorithm to segment the occlusion region. Experimental results demonstrate that the proposed algorithm can track vehicles under occlusion accurately.

vehicle tracking; occlusion processing; motion vector; Markov random field

With the development of the economy, more cameras have been installed on roads to monitor the traffic. How to make the most out of videos to gather traffic information is a problem. In theory, video-based vehicle tracking technology can automatically collect traffic information such as traffic volume, speed, density and traffic incidents[1], so it has received much attention in recent years.

The main challenge of video-based vehicle tracking is to track vehicles effectively in complicated environments such as the occlusion phenomenon between vehicles, during changing illumination and so on[2-4]. There are several object tracking algorithms considering the occlusion. Harguess et al.[5-6]tracked objects under occlusion using binocular video, but these binocular vision methods are unsuitable for practical applications. In the field of monocular vision, Zhang et al.[7]segmented the occlusion region in a geometrical way and when the outline of vehicles is unbroken, it works well. In addition, the weighted histogram is integrated with a mean shift[8-11]or a particle filter[12-13]to track objects under occlusion. In general, they can effectively track the objects whose size changes little, but in the traffic scene, the vehicle’s scale may undergo a large change. It is difficult for these algorithms to update the size of the tracking window adaptively. In Ref.[14], Kamijo et al. presented a block-based vehicle tracking method and used the Markov random field to segment the occlusion region. This method can process occlusion and adapt to the change of vehicle’s size simultaneously. However, it also has limitations. First, when a vehicle is close to but not occluded by another vehicle, it may be considered to be mistakenly occluded by the latter in tracking. Secondly, it fails to segment the vehicles whose motion vectors are similar. Furthermore,the two negative factors may appear simultaneously to make the tracking unsuccessful.

To deal with the above problems, a novel vehicle tracking algorithm is proposed. First, the target vehicle is divided in a different way to reduce the influence of its neighboring vehicle. Then, the block’s histogram is used to define the Markov random field’s energy function and make the occlusion segmentation insensitive to the vehicles’ motion vectors. Experimental results demonstrate the effectiveness of the proposed method.

1 Regular Block-Based Vehicle Tracking Method

In Kamijo’s vehicle tracking method, the image is divided into regular blocks, each of which consists of 8×8 pixels and has a single label. All of the blocks’ labels constitute a label map, and vehicle tracking is equivalent to updating the label map continually.

Lnis the label map of then-th image. When the (n+1)-th image comes, the motion vectors of the vehicle’s blocks are estimated. In them, the most frequent one is considered as the vehicle’s motion vector, and based on it, the vehicle’s blocks inLnare moved to new places. Then, the moved blocks are expanded as candidate blocks whose labels will be checked next. If the difference between intensities at a candidate block and those at the background image is greater than the threshold value, the block’s label is set to be the vehicle’s label, or else to be 0. After checking the candidate blocks, a new label mapLn+1can be obtained.

(a)

(b)

(c)

When a vehicle occludes another vehicle, the labels of the blocks in the occlusion region needs to be optimized. Each block’s label is a discrete random variable and the combination of all block’s labels is assumed to be a Markov random field. To blockykin the occlusion region, its label is optimized by minimizing the energy functionU(yk) defined in Ref.[14]. IfU(O1)≤U(O2), then blockykis considered to belong to vehicleO1or else belongs to vehicleO2.

(a)

(b)

2 Novel Block-Based Vehicle Tracking Method

2.1 Vehicle division

The method in Ref.[14] divides the whole image and the vehicle simultaneously into several blocks, whereas the proposed method only divides the vehicle into blocks, each of which consists ofN×Npixels.Nis chosen according to the vehicles’ resolutions. When the vehicles contain more pixels,Nis set to be larger and vice versa. Because the vehicle’s length and width are not always the integral multiples ofNpixels, the blocks on the vehicle’s edge may overlap with its adjacent blocks. The two ways of division are compared in Fig.3.

(a)

(b)

Fig.3 Two ways of division. (a) The division in Ref.[14]; (b) The proposed division (N=11)

2.2 Detection and adjustment of noise motion vectors

After division, all the blocks’ motion vectors are estimated as shown in Fig.4(a). To avoid the expansion of blocks described in Section 1, the proposed method moves each block based on its own motion vector, but some motion vectors may be incorrect. So, it is necessary to detect and adjust noise motion vectors before moving the blocks.

(a)

(b)

It is observed that the differences between the noise motion vector and its surrounding motion vectors are relatively large while the difference between the normal motion vector and its surrounding motion vectors are relatively small. Based on the smoothness of the motion vectors’ spatial distribution, the noise motion vectors are detected and adjusted as below.

Viis the motion vector of blockBi, and the neighborhood ofBiis defined as

(1)

where dis(Bi,Bj) is the distance betweenBiandBj.

(2)

2.3 Blocks moving

After the adjustment of motion vectors, each block is moved using its own motion vector. If two moved blocks have the same coordinates, one of them is deleted from the set of blocks to reduce computational time. Finally, the rest of blocks constitute the vehicle’s new location in the current frame.

Since we only divide the vehicle into a group of blocks and the moved blocks can be located at any position in the image, it is unnecessary to expand the moved blocks as described in Section 1. It means that the vehicle will be influenced little by its neighboring vehicle in tracking. The first shortcoming of the method in Ref.[14] has been avoided until now.

2.4 Occlusion segmentation

In the proposed algorithm, each vehicle’s position is represented by the minimum rectangle which contains all the blocks belonging to the vehicle. If a rectangle overlaps another rectangle, one vehicle is considered to occlude another. The overlapping region is defined as the occlusion region, and occlusion segmentation is equivalent to determining the labels of the blocks in the occlusion region. It is assumed that each block’s label is a discrete random variable whose distribution relies only on the distribution of its neighborhood, and all the blocks’ labels compose a Markov random field. The neighborhood is defined as

(3)

Fig.5 The neighborhood of block i

Based on the above assumption, the occlusion segmentation is equivalent to maximizing the probabilityP(Z/Q), whereZis the combination of labels andQis the current image. According to the Bayes rule, the optimal combination of labelsZ*is

Z*=argmax(P(Q/Z)P(Z))

(4)

The Hammersley-Clifford theorem proves that a Markov random filed can be expressed by a Gibbs distribution. So, we can obtain

(5)

(6)

whereM1andM2are the normalization constants.

Eq.(4) is equivalent toZ*=argmin(U(Q/Z)+U(Z)), and the energy functionU(Z) is defined as

(7)

(8)

wherec={zi,zj} is a clique andCis the set of cliques.

We assume that the distance between the histogram of blockiand that of the non-occlusion region has the same label which follows that Gaussian distribution. So the energy functionU(Q/Z) can be defined as

(9)

wherehi,hOiare the color histograms of blockiand the non-occlusion region of vehicleOi(The number of each histogram’s bins is 64(43)). If the label of blockiisO1,Oi=O1; otherwise,Oi=O2.ui=0, andσiis estimated empirically.

The minimization of the energy function is a combinatorial optimization problem. We use the simulated annealing algorithm[15]to minimize it. Finally, the labelsZ*are given to the corresponding blocks and the occlusion region is segmented.

Fig.6 shows an example of occlusion segmentation. In Fig.6(a), the black blocks constitute the occlusion region, and in Fig.6(b) they are segmented accurately by minimizing the energy function.

(a)

(b)

Fig.6 Occlusion segmentation. (a) Before segmentation; (b) After segmentation

It can be seen from Eqs.(7) to (9) that using the spatial color information instead of the motion vector to segment the occlusion region, the proposed method is insensitive to the motion vectors of vehicles in occlusion.

3 Experiments

To demonstrate the effectiveness of the proposed method, we apply it and the method in Ref.[14] to two traffic videos and define the tracking error of two adjacent vehicles as

(10)

In the first video, no occlusion occurred but a couple of vehicles were close to each other. The tracking results are shown in Fig.7. Due to the closeness, they were connected together and a false occlusion was created by the method in Ref.[14]. By contrast, they were still separated and tracked well by the proposed method.

(a)

(b)

In the second video, there are 19 pairs of vehicles in occlusion. If the tracking error exceeds 20 pixels, we consider it a failed tracking. As a result, the method in Ref.[14] and the proposed method can respectively track 14 and 17 pairs of vehicles. Three pairs of vehicles cannot be tracked well by the method in Ref.[14] because of their similar motion vectors; and two pairs of vehicles cannot be tracked by both methods because the occlusions occur at the beginning of tracking and the vehicles’ initial locations are difficult to obtain. Fig.8 shows the tracking results of a pair of vehicles which have similar motion vectors.V1andV2are motion vectors of the upper vehicle

(a)

(b)

and the lower vehicle, respectively, and in the tracking, the distance between them is less than 4 pixels. In the left images,V1={-2,-4} andV2={-3,-6}. In the middle images,V1={-2,-4} andV2={-3,-5}. In the right images,V1={-1,-3} andV2={-2,-4}.

The tracking errors of two pairs of vehicles are shown in Fig.9 and Fig.10, respectively. The above experiments demonstrated that the proposed method can track vehicles under occlusion more accurately than the method in Ref.[14].

Fig.9 Tracking errors of the first couple of vehicles

Fig.10 Tracking errors of the second couple of vehicles

4 Conclusion

In this paper, a novel vehicle tracking algorithm based on blocks is proposed. The vehicle is divided into a group of blocks, in which the edge block can overlap its neighboring block. The advantage of this division method is that the target vehicle is influenced little by its neighboring vehicle in tracking. Then the noise motion vectors of blocks are detected and adjusted. Based on the adjusted motion vectors, the blocks are moved to update the vehicle’s location. When a vehicle is occluded by another vehicle, we establish a Markov random field to segment the occlusion region. In the Markov random field, the neighborhood system is defined using the Euclidean distance and the energy function is built based on the block’s histogram rather than the vehicle’s motion vector. This allows vehicles under occlusion which have similar motion vectors to also be segmented accurately. Experimental results demonstrate the effectiveness of the proposed method.

[1]Mallikarjuna C, Phanindra A, Ramachandra K R. Traffic data collection under mixed traffic conditions sing video image processing[J].JournalofTransportationEngineering, 2009, 135(4): 174-182.

[2]Hu W M, Tan T N, Wang L, et al. A survey on visual surveillance of object motion and behaviors[J].IEEETransactionsonSystems,Man,andCybernetics:ApplicationsandReviews, 2004, 34(3): 334-352.

[3]Hou Z Q, Han C Z. A survey of visual tracking [J].ActaAutomaticaSinica, 2006, 32(4): 603-617.

[4]Yilmaz A, Javad O, Shah M. Object tracking: a survey[J].ACMComputingSurveys, 2006, 38(4) :1-45.

[5]Harguess J, Hu C B, Aggarwal J K. Occlusion robust multi-camera face tracking[C]//Proceedingsofthe2011IEEEComputerSocietyConferenceonComputerVisionandPatternRecognitionWorkshops. Colorado Springs, CO, USA, 2011: 31-38.

[6]Qian Z, King N N. Segmentation and tracking multiple objects under occlusion from multi-view video[J].IEEETransactionsonImageProcessing, 2011, 20(11): 3308-3313.

[7]Zhang W, Wu Q M J, Yang X K, et al. Multilevel framework to detect and handle vehicle occlusion[J].IEEETransactionsonIntelligentTransportationSystems, 2008, 9(1): 161-174.

[8]Li Z, Tang Q L, Sang N. Improved mean shift algorithm for occlusion pedestrian tracking[J].ElectronicsLetters, 2008, 44(10): 622-623.

[9]Yan J, Wu M Y. Anti-occlusion tracking algorithm based on mean shift and fragments[J].OpticsandPrecisionEngineering, 2010, 18(6): 1413-1419.

[10]Panahi R, Gholampour I, Jamzad M. Real time occlusion handling using Kalman filter and mean-shift[C]//The8thIranianConferenceonMachineVisionandImageProcessing. Zanjan, Iran, 2013: 320-323.

[11]Khan B, Khan A K, Raja G, et al. Implementation of modified mean-shift tracking algorithm for occlusion handling[J].LifeScienceJournal, 2013, 10(11): 337-342.

[12]Wang Z W, Yang X K, et al. Camshift guided particle filter for visual tracking[J].PatternRecognitionLetters, 2009, 30(4): 407-413.

[13]Abramson H, Avidan S. Tracking through scattered occlusion[C]//Proceedingsofthe2011IEEEComputerSocietyConferenceonComputerVisionandPatternRecognitionWorkshops. Colorado Springs, CO, USA, 2011: 1-8.

[14]Kamijo S, Sakauchi M. Segmentation of vehicles and pedestrians in traffic scene by spatio-temporal Markov random field model [C]//Proceedingsofthe21stInternationalConferenceonDataEngineeringWorkshops. Tokyo, Japan, 2005: 1-8.

[15]Tang L S, Xie Y, You S Y.Non-numericparallelalgorithm-simulatedannealingalgorithm[M].Beijing: Science Press, 2000:22-55. (in Chinese)

考慮遮擋的視頻車輛跟蹤

朱 周1,3路小波2,3

(1東南大學(xué)交通學(xué)院,南京 210096)

(2東南大學(xué)自動化學(xué)院,南京 210096)

(3東南大學(xué)復(fù)雜工程系統(tǒng)測量與控制教育部重點實驗室,南京 210096)

為了對遮擋情況下的運動車輛進行跟蹤,提出一種基于分塊的車輛跟蹤算法.該算法將目標車輛以可重疊的方式劃分為若干大小一致的子塊.在分塊的基礎(chǔ)上估計所有子塊的運動矢量,檢測噪聲運動矢量并進行調(diào)整,以減少運動矢量估計的誤差,然后對子塊進行移位以實現(xiàn)車輛跟蹤.為了處理車輛間的遮擋現(xiàn)象建立了馬爾可夫隨機場描述子塊之間的關(guān)系,利用歐氏距離定義塊的鄰域,并基于塊的直方圖構(gòu)建能量函數(shù),最后利用模擬退火法對能量函數(shù)進行優(yōu)化,以對遮擋區(qū)域進行分割.實驗結(jié)果表明,該算法能夠?qū)φ趽踯囕v進行準確跟蹤.

車輛跟蹤;遮擋處理;運動矢量;馬爾可夫隨機場

U491.1

Foundation item：The National Natural Science Foundation of China (No.60972001, 61374194).

：.Zhu Zhou, Lu Xiaobo. Video-based vehicle tracking considering occlusion[J].Journal of Southeast University (English Edition),2015,31(2):266-271.

10.3969/j.issn.1003-7985.2015.02.019

10.3969/j.issn.1003-7985.2015.02.019

Received 2014-10-18.

Biographies：Zhu Zhou(1984—), male, graduate; Lu Xiaobo(corresponding author), male, doctor, professor, xblu@seu.edu.cn.