Real-time Traffic Pattern Analysis and Inference with Sparse Video Surveillance Information

1 Introduction

The proliferation of urban video surveillance systems gives prominence to advanced traffic services, from personalized route optimization to macrolevel traffic administration. Such surveillance data applications include urban vehicle driving optimization [Gonzalez et al., 2007; Schmitt and Jula, 2006; Leduc, 2008], road network traffic flow analysis [Bas et al., 2007; Liu et al., 2013; Suzuki and Nakamura, 2006], and intelligent transportation realization [Zhang et al., 2011; Wang, 2010; Lu et al., 2009].

Most traffic analysis with such surveillance systems assumes a dense camera distributions and so as a full coverage of road network traffic surveillance. However, the sparsity of camera distribution can hardly be avoided in real scenarios, due to the high deployment overheads and the dynamic nature of urban road networks. On the other hand, there is an increasing need for utilizing such camera surveillance data for traffic inference, especially for most small and mediumsized cities of China, where floating vehicles are not well employed and therefore the solutions with historical trajectory collections are not applicable. For instance, in Suzhou, a leading city in deploying urban traffic monitoring systems, there are 107 intersections in the industrial park while only 41.1% intersections are equipped with traffic surveillance systems.

There also exist extensive studies on forecasting traffic conditions with time series analysis. However, such seemingly related techniques fall short in making predictions with the incomplete information caused by the partial coverage of traffic surveillance. We can summarize existing works of this field into two categories, neural network based methods [Yasdi, 1999; Dia, 2001] and spatial topology based methods [De Fabritiis et al., 2008; Min and Wynter, 2011].

Neural network based methods predict a road segment's traffic flow by matching the real time information with historical patterns. In particular, Yasdi et al. [Yasdi, 1999] utilize Jordan architecture based neural networks and Dia et al. [Dia, 2001] develop time-lag recurrent neural networks. Nevertheless, such predictions are done based on the long-term data accumulation of the target road segment. Therefore, it is not clear how to extend them to support road networks that are only partially surveilled.

Spatial topology based methods mostly consider the correlation between interconnected road segments. Particularly, Fabritiis et al. [De Fabritiis et al., 2008] predict short-term (15 to 30 minutes) road travel speeds of the Italian motorway network with historical and real-time floating-car-collected traffic speed information, and Min et al. [Min and Wynter, 2011] define a time lag function to describe the spatiotemporal correlations of a road segment and its counterparts in the neighborhood. Without exception, these spatial topology methods cannot abstract the correlations between road segments which are not surveilled either.

In summary, previous works on traffic volume prediction take the completeness of the road network surveillance as an essential ingredient. It is not clear how prediction can be made if the some parts of the surveillance is missing. In this work, we tackle the challenge in three folds. First, we model the traffic volume of the entire road network with transferred transition probabilities from a third-party GPS dataset. Second, we use a model that takes transition probabilities as inputs to make the incomplete surveillance space approximately complemented. The model follows multivariate normal distributions, which are considered as a general stochastic method for capturing travel behaviours on road networks [Lam and Xu, 1999]. Also, with extensive data analysis, we observe that the transferred probabilities rest with time varying traffic contexts, e.g., workdays and weekends, rush and non-rush hours. It means that the utilization of the probabilities has to contend with specific spatiotemporal contexts. Third, we propose a novel approach to accurately infer the real-time traffic volume with only partially camera-equipped road networks. The results are cross-validated with real data.

Our work is based on a real project, SkyEye, in collaboration with Suzhou Traffic Police Department. To our best knowledge, this is the first work on inferring real-time traffic volumes with sparse road video cameras. The distribution of traffic surveillance cameras and exemplified surveillance information is shown in Figure 1. The GPS data is collected from 4,303 taxicabs of a year, i.e., from May, 2015 to June, 2016. We also collected all the video surveillance information with 44 camera-equipped road intersections of two-month, including the April and May of 2016. Experiments show that our proposal can improve the estimation accuracy by up to 30%.

The rest of this paper is organized as follows. Section II introduces preliminaries and formalizes the problem. Section III investigates our technical proposals including the inference algorithm. Section IV presents empirical studies and Section V concludes the paper.

2 ProblemDefinition

In this section, we formally define basic concepts as well as the problem studied in the work.

Definition 1 (Road Network.) A road network can be modeled as a directed graph G(V, E), where the vertex set V denotes all the road intersections and the edge set E refers to all road segments. Given two road intersections vi, vj ∈ V, eij ∈ E is the road segment between vi and vj.

In SkyEye, traffic surveillance is implemented by cameras that equipped on the road intersections. The captured image and videos are then analyzed and parsed, as shown in Figure 1. Accordingly, the traffic volume statistics can be obtained. The intersections can thus be classified into two sets, cameraequipped intersections Vc and camera-free intersections Vc, satisfying Vc ∪ Vc = V and Vc ∩ Vc = ∅.

Definition 2 (Intersection Traffic Volume.) Regarding intersection vj, its traffic volume information in a specific time interval ∆t can be formulated by Vj(∆t), meaning the traffic volume of the intersection vj during ∆t is Vj vehicles per time unit.

Definition 3 (Trajectories.) Considering a moving object o, e.g., a taxicab, the trajectory of o within a given time interval ∆t can be formulated by To(∆t) = {v1(t1), v2(t2), · · · , vk(tk)}ti∈∆t, which means object o starts its journey at intersection v1 of time t1 and ends at intersection vk of time tk. Here, vi(ti) refers to the snapshot of time ti that trajectory To moving across intersection vi.

Notice that trajectories and traffic flows vary with different settings of time intervals ∆t. We define trajectories and traffic volume in accordance with the time-varying urban traffic features, because it is commonly accepted that the traffic flows change regularly over time in practice [Wang et al., 2014; 2016; Zheng et al., 2010; Yuan et al., 2013; 2012] 1 .

Definition 4 (Inference with Incomplete Surveillance.)

Given road network G(V, E) and intersections under surveillance Vc, for any given time interval ∆t, our purpose is to design a method such that the traffic volume Vi(∆t) of intersection (vi ∈ Vc) without surveillance can be estimated.

The quality of the estimation or inference is measured by Equation (1). Here, ̂ Vi denotes the estimated value of traffic volume by our method. For a camera-equipped intersection, the accuracy is equal to 100%. For a camera-free case, the accuracy measure the ratio of the real value to the estimated value and is normalized to 1 by setting the dominator as summation of real value and the estimation error.

3 Real-time Traffic Volume Inferring Algorithm

In this section, we propose the solution framework for the traffic analysis and inference problem. Figure 2 illustrates the architecture of our solution which consists of three major components: 1) training transition probabilities from thirdparty datasets; 2) unobserved traffic pattern completion with model-based approximations; 3) read-time traffic inference algorithms. We detail each step in the following subsections.

3.1 Time-varying Traffic Influence Models Between Neighboring Intersections

Now we model the transition probability between road intersections. Suppose intersection vi is a m-way road intersections. To find the probability distribution of an incoming vehicle of vi to other m- 1 directions within a specific period, e.g., ∆t, helps to infer the traffic patterns of vi's neighboring intersections.

1 The setting of ∆t should balance the tradeoff between the accuracies and temporal granularity. In our implementation, we slice the temporal information into slots of 30 minutes following the common settings. Notice that such a setting may be related to the results of inference accuracy but is orthogonal to the generalities of our proposals

Let vi and vj be two adjacent intersections. The transition probability from vi to vj, denoted as p∆t(vi, vj), represents the probability of a vehicle moving from intersection vi to vj within time interval ∆t, and thus enables quantifying the traffic volume of vj, given that all vj's neighboring intersections are known. In our implementation, we adopt an order-1 Markov transition probability matrix, B∆t, for summarizing transition probabilities of all pairs of road intersections in the urban road network, as shown in Equation (2).

We assume an acyclic road network such that the transition probability from an intersection to itself equals 0, i.e., p∆t(vj, vj) = 0. Also, for two intersection vj and vk, if they are not adjacent, the corresponding transition probabilities equal to 0, i.e., p∆t(vj, vk) = p∆t(vk, vj) = 0. According to our analysis, the traffic patterns in weekdays and weekends are significantly different. So, the traffic influence is modeled for them separately.

The transition probabilities are trained with third-party GPS datasets in our implementation. With transition probabilities, the mutual influence between road intersections are established. In the sequel, we study how the trained probabilities are further used for estimating unobserved intersections.

3.2 Traffic Volume Analysis of Entire Road Network

As concluded in [Lam and Xu, 1999], the traffic volume of road networks follows a MND (Multivariate Normal Distribution). Recall that earlier, we introduce the time-varying properties of traffic volumes. So, we assume, for ∆t and vj, the traffic volume is ̂ Vj(∆t), j = 1 · · · |V|, where Vj can be calculated by:

where εvj (∆t) ∼ N(0, (σ∆t vj )2 ), and N(vj) is the neighbor intersection set of intersection vj.

For the entire road network and ∆t, we use a vector TV to denote the traffic volumes of all intersections. After substituting elements with Equation (3), we have:

TV(∆t) =M(∆t) +B∆t ∗TV(∆t) +E(∆t) (4) where M(∆t) = [µv1 (∆t), µv2 (∆t), · · · , µv|V| (∆t)]T , and E(∆t) = [εv1 (∆t), εv2 (∆t), · · · , εv|V| (∆t)]T . Based on the definition of MND, we can have:

where Υ(∆t) is the diagonal matrix with elements of (σ∆t vj )2 's:

Note that we have already calculated the matrix B∆t in the last subsection. So far, we have derived the equation of TV (∆t) whose input parameters can be calculated by Equations (2) and (6).

As we have analyzed, the road intersections can be with or without camera surveillance. Let the number of intersections with camera be K. We use a K × |V| indicator matrix P to indicate the existence of camera surveillance. The equation of P is as follows.

If an intersection vj is camera-equipped, the element ajj is set to 1. In total, K columns are set to 1 because there are K intersections are camera-equipped. Defining as such, we can denote the observed traffic volume as below.

The purpose here is to estimate the unknown parameters µvi (∆t) and (σ∆t vi )2 . To do that, we utilize maximum likelihood estimation:

Very likely, we cannot estimate all unknown µvi (∆t) and (σ∆t vi )2 since the number of unknown parameters is more than the number of observations. Therefore, we group the intersections in nearby regions and make those camera-free intersections have the same µvi (∆t) and (σ∆t vi )2 value to the nearest camera-equipped intersections to them. By solving the maximum likelihood in Equation (9), we can have the estimation results ̂ M(∆t) and ̂ Υ(∆t).

3.3 Inferring Real-time Traffic Volumes of Camera-free Intersections

We have shown how unknown parameters can be estimated and how the MND for the road network traffic volume can be modeled. Now, we describe the mechanism which can infer real-time traffic volumes of camera-free intersections with the approximated MND. We first show how to use the calculated TV (∆t) to infer the real-time traffic volumes of camera-free intersections. For simplicity, we formally define r and Γ:

then we have TV(∆t) ∼ N(r(∆t), Γ(∆t)). After generating the MND, we can proceed to calculate the real-time traffic volumes of intersections without fixed video cameras by computing conditional expectation of MND. We first re-arrange the matrix TV(∆t) as:

where there are |V| -K and K elements in TVMISSING(∆t) and TVOBS(∆t) respectively, and the goal is to compute E[TVMISSING(∆t) |TVOBS(∆t) ]. According to the re-arranged matrix TVRE(∆t), we also re-arrange matrix M(∆t) and Υ(∆t) as MRE(∆t) and ΥRE(∆t) respectively, then partition rRE(∆t) and ΓRE(∆t) as:

where there are |V| -K and K elements in r1(∆t) and r2(∆t), and Γ11(∆t), Γ12(∆t), Γ21(∆t) and Γ22(∆t) are (|V| -K) ∗ (|V| -K), (|V| -K) ∗ K, K ∗ (|V| -K) and K ∗ K sub-matrices respectively. Based on the definition of conditional expectation of MND, we have:

3.4 TISVAlgorithm

Now, we present the solution that consists of two parts.

The first part is to extract the time-varying traffic influence models between neighboring intersections and to extract the holistic time-varying traffic patterns of the entire road network. The travel patterns are obtained by mining the historical trajectory dataset of taxicabs and by mining the dataset of fixed road surveillance cameras. This part only needs to be executed once and the results can be used to infer the traffic volumes of urban camera-free intersections in real-time in the second part. Note that the first part should be executed for all time slots of a day.

Algorithm 1 The TISV Algorithm

• 1: procedure TRAFFICVOLUMEINFERRING(∆t) Initialization: Real-time observed traffic volume dataset Θ of camera-equipped intersection set Ψ

The second part is the Traffic Volume Inferring with Sparse Video Surveillance Cameras algorithm (TISV in short), which is triggered if the real-time traffic volume information is to be inferred. In particular, to infer the traffic volumes of camera-free intersections, we first obtain the traffic volume information of all camera-equipped intersections, then re-arrange and re-calculate the corresponding sub-matrices of the MND on-the-fly. Finally, the expected traffic volume values for all camera-free intersections can be calculated. The pseudo code of the TISV algorithm is given in Algorithm 1. The parameters in Algorithm 1 are as defined previously.

4 Experiments

We present the experimental setup in Section 4.1 and show the results in Section 4.2.

4.1 Experimental Setup

Road Networks. Our experiment is carried out on the main urban area of Suzhou Industrial Park covering 45.5 square kilometers with a road network of 107 road intersections and 298 road segments. Among the 107 intersections, 44 are equipped with fixed video surveillance systems.

Taxicab Systems. Historical records of 4,303 taxicabs are collected for training transition probabilities. All taxicabs are equipped with a GPS-based navigation system and 3G/4G network and upload their ID, location, speed, direction, etc. in every two minutes.

Verification. The inference performance is measured by cross-validation. We randomly choose 35% camera-equipped intersections as verifying intersections. Assuming the surveillance results of the chosen intersections are missing, we can infer them by the information of other camera-equipped intersections and then compare with the ground truth. An example region is shown in Figure 3, where camera-equipped intersections are marked by red dots, and the verifying intersections are illustrated by blue dots. We use the dataset of taxicabs from May 1, 2015 to April 30, 2016 to train the transition probabilities, then use the surveillance data of the same period to build the holistic traffic estimation models. We then randomly select another 10 days, including both workdays and weekends, to test the accuracy of inference of the real-time traffic volumes for the verifying intersections. In all testing cases, we consider time slots from 7 am to 8 pm, for each day.

Competitors. We evaluate the performance of our TISV algorithm by comparing it with the OKA (One Kilometer Average), LR (Linear Regression), K-means and LSTM (Long Short-Term Memory) strategies. The OKA strategy assumes the real-time traffic volume of a camera-free intersection equals to the average traffic volume of all camera-equipped intersections within one kilometer. The LR strategy establishes an linear regression model for each camera-equipped intersection, and assumes its nearest camera-free intersection follows the same linear regression model. The K-means strategy partitions all intersections into clusters and assume the traffic volume of a camera-free intersection equals to the one of its cluster center. The LSTM strategy approximates the traffic flow of a camera-free intersection by its nearest cameraequipped intersection.

4.2 Results

We first evaluate the effectiveness of our proposed TISV algorithm by comparing its accuracy with several competitors. Then, we made detailed testing to show how the proposal performs with varying factors. In the sequel, we use AR to denote inference accuracy for brevity.

Effectiveness

Impact of day type. We show the effectiveness of our proposal in Figure 4. It can be observed that the accuracy of TISV method is steadily above 70%. Compared with the baseline methods, i.e., OKA, LR, K-means and LSTM, our solution can increase the accuracy by 31.19%, 29.36%, 31.62% and 8.68%, respectively. The LSTM method performs better than other baselines. But the performance is unstable, i.e., for weekends. By contrast, our method is stable towards day types. The reason behind is that our method addresses the influences of traffic volumes in a global view, whereas other methods only consider the local effect of the traffic volume, e.g., on the neighborhood camera-equipped intersections.

Impact of time period. We examine the performance with respect to the effect of time slots in Figures 5 and 6, respectively. In particular, we show the results on weekdays in Figure 5, and the results on weekends in Figure 6.

From the two figures, we can observe that our solution outperforms all competitors and achieves an accuracy as high as 75%. For traffic volume estimation, different predicability is achieved due to the different travel patterns, which is consistent with the observations of Figure 4. More, we find that the inference accuracy works better in rush hours. For example, in Figure 5, the accuracy can be as high as about 80% at 17pm. It is because that during rush hours the travel patterns are with more regularities. Thus, it enables a better estimation on traffic volume inference. Finally, we discover the performances of five solutions in morning rush hours are much better than those of afternoon. It is because of the centralized distribution of traffic flows during rush hours. Also, this is consistent with the skewed distribution of business districts and factories where a large population work in a relatively small region. However, the traffic flow during afternoon rush hours are more decentralized due to the more evenly distributed residential regions.

Analysis

We test the accuracy of our proposed TISV algorithm with varying factors for the real-time intersection traffic volume inference. In particular, we investigate: i) the impact of the number of camera-equipped intersections; ii) the impact of the traffic volume; and iii) the impact of the density of camera-equipped intersections.

Impact of percentage of camera-equipped intersections. We investigate the effect of the percentages of cameraequipped intersections by varying the percentage of cameraequipped intersections from 15% to 30%. The results are reported in Figure 7. It can be observed that the accuracy ratio of our solution increases roughly with the increase of the percentage of camera-equipped intersections. Because the MND can be better modelled if with larger number of cameraequipped intersections. Also, it reflects that the performances of our solution for weekdays and weekends are close, which means our solution is general to the day types.

Impact of traffic volume. We study the effect of real time volume of camera-free intersections on the prediction accuracy in Figure 8. It can be observed that the performance of our solution increases in accordance with the increase of actual traffic volumes of camera-free intersections and that our solution outperforms the other four in all settings. In particular, the accuracy ratio of our algorithm has an increase of more than 25% while the actual traffic volumes of camera-free intersections increase from 0-20 vehicles per minute to 180-200 vehicles per minute. Also, we can observe that the performances of the OKA, K-means, LR and LSTM strategies are relatively better while the actual traffic volumes of camerafree intersections are between 20 and 60 vehicles per minute. For most urban intersections, the traffic volume is within such a range during the day time, and the traffic flows follow stable patterns as well. Compare with the competitors, our solution considers the mutual influence between intersections which results in a better estimation.

Number of camera-equipped intersections within a square

Figure 9: Impacts of densities of camera-equipped intersections

Impact of density of camera-equipped intersections. Finally, we evaluate the performances of our method as well as competitors while changing the density of camera-equipped intersections. To do that, we partition the road network into equal-sized squares, as exemplified in Figure 3. The density of camera-equipped intersections is classified into five levels, i.e., 2, 3, 4, 5, 9 per square, respectively. The results are reported in Figure 9. We can observe that with the increase of the number of camera-equipped intersections, the inference accuracy increases accordingly. By contrast, the competitors' performance does not change. This is because our solution approximates the traffic volume model from a global view, whereas all others only consider intersections in the neighborhood.

5 Conclusion

Recent technology advances provide us new opportunities to improve traditional real-time traffic surveillance system. In this paper, we model the time-varying traffic influence model between neighboring intersections with transition probabilities, then use MNDs to approximate the traffic volumes of the entire road network. We further propose a novel method to infer the possible real-time traffic volume of a camerafree intersection with the real-time traffic volume information of sparsely distributed camera-equipped intersections. Performance evaluations from real datasets demonstrate the effectiveness of our proposal.

Acknowledgments

We gratefully acknowledge anonymous reviewers for reading this paper and giving valuable comments. This paper is partially supported by the NSFC (No.61672487, No.61472384, No.61772492, No.61772492, No.U1301256), Jiangsu Natural Science Foundation (No.BK20151239, No.BK20171240, No.BK20171240), and Fundamental Research Funds for the Central Universities. Xike Xie is supported by the CAS Pioneer Hundred Talents Program.