Massive Trajectory Matching and Construction from Aerial Videos based on Frame-by-Frame Vehicle Detections

Our framework contains four modules, as shown in Figure 1, which are image stabilization, vehicle detection, trajectory construction, and trajectory denoising. In the first module, shaking in UAV videos is eliminated by Scale Invariant Feature Transform (SIFT) operator matching. YOLOv4 algorithm for vehicle detection is applied for position obtaining as the foundation of trajectory construction. Then a data correlation algorithm based on traffic flow theory combined with regional traffic dynamics is proposed to construct vehicle trajectories. In the end, noise in rough vehicle trajectories is separated and removed by the EEMD-based denoising algorithm. The construction details of each section are described below.

UAV may shake due to the interference of airflow and wind (e.g.Li et al., 2019).The external disturbances could cause viewing angle changes in the image. Such movement will overlap with the target movement in the video and cause an error. In image stabilization, a feature point selection method using the scale-invariant feature as decision method, SIFT (Lowe, 2004) is applied. SIFT is an image local feature description operator based on scale-space that maintains invariance to image scaling, rotation, and even affine transformation. The key points that SIFT looks for are some very prominent ”stable” feature points that will not change due to factors such as illumination, affine transformation and noise, such as corner points, edge points, bright spots in dark areas, and dark points in bright areas.

The selection of feature point pairs uses the joint restriction of Euclidean distance and location range. The Euclidean distance is to ensure the similarity of the two feature points to the internal scale-invariant vector. And the location range is to exclude the mismatch caused by different objects had similar feature vectors based on no violent motion of UAV. Based on these two constraints, all video frames will be affine transformed by the good-key-point pairs found by the SIFT operator and aligned with the first frame. For stronger fault tolerance, the multiple good-key-point pairs found will all be used for matching operations. The calculated affine transformation matrix searched by the minimum sum of errors for all good-key-point.

YOLO series (Redmon et al., 2016; Bochkovskiy et al., 2020) and R-CNN (Fan et al., 2016) series are two well-known masterpieces of detection in the field of CNN (Benjdira et al., 2019).Some scholars have conducted an experimental comparison between respective outstanding works of the two series, YOLOv3 and Faster-RCNN. This research shows more suitability for vehicle detection in aerial videos of YOLOv3 and achieves higher detection accuracy and faster processing speed than R-CNN (Benjdira et al., 2019). The current YOLO has been upgraded to version 4 (Bochkovskiy et al., 2020), which fully integrates computing skills and has a significant improvement in speed and edge accuracy. Note that the latest updated version, YOLOv5 (Jocher et al., 2020), emphasizes its lightweight and training speed, and its accuracy can almost reach the same as YOLOv4. As the detection accuracy is concerned most, YOLOv4 is used in this research.

In YOLOv4, the convolutional layer and sampling layer segment operate the image alternating continuously (Figure 2). The input image first goes to convolutional layers to get samples of features. And then, 1×1 or 3×3 layers resetting is applied for quicker calculating speed. The shortcut layers are arranged among convolutional layers at specific intervals to divide the CNN into dozens of pieces. The dividing operation is necessary for controlling the propagation of gradients as well as avoiding the problems of gradient diffusion and gradient exploding. At last, the yolo layers perform classification and position prediction of the targets. The entire calculation process and target characteristics will be continuously summarized and updated as a weights file. This weights file is the database of target detection.

The model performs instable in dark vehicle and large vehicle detection because of their distinguished features and small training samples. To solve this problem, we propose a merged training strategy to improve detection performance (see Figure 3). We first train the YOLOv4 model with all vehicle samples in the training database. In the second step, we further enhance our method by separately training two additional neural network models for dark vehicles and large vehicles. After that, the vehicle detections from the three models are merged to form the raw detection pool.

The raw data may contain duplicated detection boxes of the same vehicle, which need to be reduced. Intersection-over-union (IoU) is used in the duplication reduction method, the calculation of IoU is shown in Figure 4, and the recognition mechanism is expressed as (Eq. 1, 2,3):

where $IoU_{obj1},IoU_{obj2}$ indicate the IoU value of two overlapped object obj1 and obj2, $area_{overlap}$ is the maximum acceptable percentage of target bounding box overlapping. In Eq. 1-3, only one item will be established for each judgment. When it suits Eq. 1 or Eq. 2, the higher confidence object will be reserved.And if Eq. 3 holds, the lower overlapped obj1 will be choose.

After completing the repeated screening, the location of the vehicle at each moment is obtained. At this time, we only have a scattered distribution of points without any links. In the trajectory construction part, these points will be connected in series to construct the trajectory.

A large number of vehicle targets are contained in every frame. Errors are also contained which could be caused by pixel jitter, vehicle shadows, road marks as well as some missing detections. Such errors make it more difficult to matching construction in massive vehicle candidates. Directly linking these detection frames with errors result in irreparable effects on traffic data. Existing association methods are processed in a mixture of these right and wrong candidate boxes and result in a high error rate (Azevedo et al., 2014; Luetteke et al., 2012).

It is crucial to choose the only true position of one vehicle among the candidates mixed with interference target. And in an individual vehicle, the position during travel space must be determined by vehicle dynamics and surroundings. In other words, by combining vehicle dynamics and surroundings, we can predict a more reliable position in multiply candidates. In this section, traffic flow theory is used to deduce the correct way to match vehicles. In addition, under the constraints of the time section, there will still be some unreasonable fragments in the trajectory. The unreasonable fragments should be cut, and the vacant parts should be compensated. In the following section, trajectory identification integrity enhancement and coordinate transformation are introduced.

The trajectories contain noises with features of high frequency and small magnitude due to the limitations of integer pixels and background interference. Although these deviations are composed of white noise, they will still have an impact on the calculation of instantaneous velocity and acceleration. The ensemble empirical mode decomposition (EEMD) is applied for our research (Wu and Huang, 2009). EEMD have a good performance for both linear and non-linear signal decomposition. Besides, the decomposed multiple intrinsic mode functions (IMF) in different frequencies can robustly avoid modal mixing, which indicates either an IMF consisting of signals of widely disparate scales, or a signal of a similar scale residing in different IMF components.

In the trajectory decomposition, in order to better determine the frequency band of each IMF, the additional white noise of finite-amplitude is added to the IMF. Accurately, after adding white noise, the current observation can be described as follows (Eq. 8):

where $i$ is the iteration number, $x(t)$ is the raw trajectory data, $w_{i}(t)$ is the added white noise, $X_{i}(t)$ is the noise-aided trajectory data.

We decompose the trajectory through the following rules. We first line maximum points and minimum points with cubic splines to form the upper and lower envelopes. Then the local means of the upper and lower envelope are taken as the next observation $x_{i}(t)$. The IMF is found if $x_{i}(t)$ meets the following conditions (Eq. 9, 10):

Define the extrema of $x_{i}(t)$ as $N_{z}$, the zero-crossing point as $N_{e}$, the upper and lower envelope as $f_{max}(t)$ and $f_{min}(t)$.

When IMFs can no longer be found, this searching will end and original $X_{i}(t)$ can be expressed as Eq. 11:

where $imf_{j}(t)$ is the IMFs separated from $X_{i}(t)$, andv$r_{n}(t)$ is the residual.

Appropriate IMFs are determined with an energy-based IMF selection method Chen et al. (2018). In this research, it shows that the energy of the signal represents the amount of information stored in it. The energy of signal can be calculated as Eq. 12. The energy of noise signal only accounts for a small proportion while the majority of energy is concentrated in the meaningful signals. A log function is used to distinguish the noise signal energy which processes a negative result, and the other meaningful signals need to meet the Eq. 13.

where $E_{j}$ is the energy of the jth IMF, $c_{j}(k)$ is the point collection of jth IMF, num is the total number of collection points. The sum of the selected IMFs is the denoised trajectory of the vehicle. After the above steps, accurate vehicle trajectories are extracted via our framework.

All frames of UAV videos will be matched with the first frame. 200 strongest initial feature points are selected and matched in every frame by the SIFT calculator. Not all matched couples are effectively the same point, so the Euclidean distance of the feature invariant vectors of the two matching points is used to test and screen the effective feature point pairs. In order to better obtain effective feature points, we limit the search range of feature points to outside the road area. Most of the images in these areas are static buildings, which can provide effective feature points.

As shown in Figure  8(a), the colored circles represent the acquired feature points, and the colored lines connect the effective feature point pairs. The proportion of retained results after the screening is not large, but they are all exact matches. Registration requires at least three pairs of points to achieve affine transformation. Now, these dozens of matching points have been able to ensure the registration of the picture, which will match based on the principle of minimum error. The stabilized image is shown in Figure  8(b). It can be seen that the characteristic objects are all in the same position after the image changes, and the non-pixel portions in border areas are filled with black.

The basic network and an enhanced network of YOLOv4 are trained for aerial vehicle detection. According to the creator and some researchers who have applied YOLOv4, the training settings and training samples almost play a decisive role in the performance of the network. In our study, 20000 vehicle samples are applied for the basic training. Besides, 4000 dark vehicle samples and 1000 large vehicle samples are applied for enhanced training. These datasets are manually calibrated to ensure that the external edge error is within three pixels.

Critical parameters of YOLOv4 and the values we choose are listed in Table4.2. The Batch indicates the number of samples that participated in each iteration. A higher batch will bring a better accuracy but a lower training speed. The subdivision is set to relieve the usage of GPU by separating training datasets into groups. Width and Height are the resized image specifications for training. Large Width and Height will retain more image information but consume more memory. Max-batches is the upper limit of training times. The best value of the Max-batch is to get less loss, but overlarge Max-batch can easily overfit. The learning rate is to changes the model in each based on training results. A higher learning rate is required at beginning to get a quick decay in loss and low down in the back to ensure learning accuracy and prevent overfitting.

The training parameters are set for a balance of training performance and capability of the hardware. A high accuracy requires a high batch as 128, and the limitation of hardware sets the subdivisions and training size as 32 and 672×672, respectively. Max-batches are set to 60000 in the initial training and 20000 in the enhanced training. The minimum loss is found near 48000 batches in the initial training and 12000 batches in the enhanced training. The learning rate is set to 0.001 at the beginning of training, and a step decay policy is applied to decrease the learning rate from 0.001 to 0.0001 after 40000 batches in initial training and 8000 batches in enhanced training.

Vehicles are detected on the test videos using the calibrated model. When evaluating the integrity of the trajectory, we sample of 500 frames randomly, for counting and manually labeling the bounding boxes. In order to evaluate the performance of our training strategy, we calculate the results of each step in the training procedure, i.e. basic training, enhanced training, and duplication reduction. The vehicle detection performance is shown in Table4.3.

It shows that the YOLOv4 detection model after parameter selection and enhancement performs stable and shows the comprehensive result in UAV videos. Notably, the Recall in test video #1 is 91.22%, which is higher than that in test video #2 (83.41%). The main reason for the difference is that compared with video #1 which is under the free-flow condition, video #2 is under the congested condition and possesses larger vehicle amounts and smaller spacing which lowers the confidence score in the detection section. And the average IoU is only calculated by the true positive detection boxes. The two test videos are at a similar and good level although a vehicle only covers about 1500 pixels. We find that with basic training models, some dark vehicles and large vehicles are not accurately detected (Fig. 3).

Table 4.3 shows that the Recall in both videos increases apparently to 93.53% and 95.28% after the enhanced training. The main reason is that the separate neural network models successfully detect more dark and large vehicles. However, the Precision shows a significant decrease resulting from the overlap of vehicle detection boxes from different models (Fig. 3).

After the duplication reduction, as shown in Table  4.3, the Precision successfully increases from 88.63% to 98.86% in test video #1 and 82.80% to 98.83% in test video #2, respectively. It means the false vehicle detections are successfully removed from the data. The Recall maintains at a high level, indicating that the duplication reduction does not wrongly delete true detections. The final Recall is 93.21% in test video #1 and 94.99% in test video #2, respectively. It indicates that the detection method of our framework works well in both congested and free-flow traffic conditions.

In the confusion matrix(Table 3), the two types of errors are false negative and false positive. False negative indicates the missed detections of true vehicles. It usually happens when the lost vehicle has a special shape, color or vehicle type, vehicle type, or the vehicle is obscured by road decorations such as signs. This problem may be reduced when more training samples are equipped, and the number of samples of each type is the same. False positive indicates fake vehicle detections, are caused by the mix-up detection of the road surface or road markings with vehicles because of confusing features.

Two typical examples are shown in Figure 9. In Figure 9(a1), the road marking is very similar to a white vehicle so that the detector makes a false positive detection. The pap similarity of the color histograms is 0.6690 in Figure 9 (a2), which shows that the two pictures are very similar. In Figure 9 (b1), the vehicle contour is not clear so that the detector did not recognize it and made a false negative mistake. Their color histograms possess a pap similarity of 0.3846 in Figure 9 (b2).

Through trajectory construction, raw vehicle trajectories are extracted from two test videos. The results are shown in Table 4.4. The research team manually counts the true count of trajectories, which is 500 and 541 in the two videos. After the trajectory construction, 484 and 497 trajectories are correctly obtained, while 4 and 43 trajectories are false positive ones. The improvement by integrity enhancement on trajectory count is evaluated in Table 4.4 (Trajectory Identification is simplified to T Identification and Integrity enhancement is simplified to I Enhancement). Results show that Recall increases from 92.20% to 93.00% and 83.92% to 86.69% in test video #1 and test video #2, respectively. Mainly, fifteen trajectories are put into integrity enhancement in test video #2 while only four trajectories are enhanced in test video #1.

This result shows a good performance in trajectory identification steps based on traffic flow theory. The majority of trajectories have been matched and constructed correctly. Besides, a large number of false positive and false negative in detection steps have been eliminated in the trajectory construction step.

In the two videos, 107 trajectories were missing or incorrectly constructed. We carefully checked these errors and found that most of the missing trajectories are caused by a long period of detection failure. The continuum of detection boxes in the trajectories is insufficient, so our methods are not able to form the complete trajectories. Only a few missing trajectories are caused by the detection box in one trajectory identifying wrongly to the trajectory of another vehicle. The mismatch occurs when the to-be-identified detection box is lost in the next several frames and too much position derivation is needed. At this time, the interference of adjacent vehicles will increase, making it easier to misidentify.

It is very difficult, or impossible, to obtain the ground truth of the vehicle trajectories for the validation of the accuracy of constructed trajectories. As a result, in our study, we estimate the validity of the denoising procedure by checking the reasonableness of the distribution range of parameters such as vehicle speed, acceleration, space headway, time headway, and gap.

A typical vehicle trajectory denoising result using EEMD is shown in Figure 10. The contribution of smoothing out the noise can be seen in Figure 10. The raw trajectory data has large fluctuation, while the denoised data is much smoother. The acceleration change resulting from the denoising process is shown in Figure 10 (b). According to Montanino and Punzo (2013), the physical limitations of vehicle acceleration and deceleration rate are $9m/s^{2}$ and $-9m/s^{2}$, respectively. And as our know, the comfortable acceleration are within $\pm 3m/s^{2}$. Our denoised acceleration data is all within a reasonable range (between the pink dotted lines), and most of them are distribute in the range of comfortable accelerations (between the purple dotted lines). The cumulative percentage curve of the acceleration of all vehicles from our data and from Montanio’s method is shown in Figure 10 (c). It can be clearly seen that the distributions of the acceleration of two trajectory data after denoising are consistent.

To further validate the reasonableness of our data, we make a comparison of the value of key parameters (speed, space headway, time headway, and gap) with the NGSIM dataset from the southbound traffic on US-101 in Los Angeles, CA, recorded from 14:50-15:05, on June 15, 2005. The visualization of the comparison is shown in Figure 11. As seen in Figure 11 (c-d), the space headway with the highest frequency in our data (the red bar) is around 12m, while that in NGSIM data (the blue bar) is around 40m. Similarly, in Figure 11(e-h), the time headway with the highest frequency is around 1.6s in both data, and the gap with the highest frequency is 8m and 40m in our data and NGSIM data, respectively. The difference in the value of the gap and the space headway maybe because our test videos partially suffer from congestions. For the same reason, the speed of our data (Figure 11 (c)) has two peaks around $30km/h$ and $55km/h$. The speed of NGSIM data has one peak around 40km because the data were collected from the free-flow traffic state.

The processing speed of our framework for trajectory extraction is calculated. The majority of time is spent on the offline training of the YOLOv4 algorithm. The training time is about 70h, which is similar to the previous study (Benjdira et al., 2019). After the training, the online processing speed is very fast. The processing time in each step of our framework is shown in Table  4.6. The detection step only costs 0.1 h, suggesting the remarkable advantage of applying YOLOv4. The trajectory construction costs 3.8 h (26s/track) and 4.0 h (27s/track), including the trajectory identification, integrity enhancement and coordinate transformation. The denoising step is fast, which costs only 0.3 h (2s/track).

In summary, the total processing time is 4.2 h and 4.3 h on the test video #1 and #2. The slightly longer processing time in video #2 is caused by the fact that there are more vehicles in congested traffic conditions. The average online processing speed is 29s/track and 30s/track, or in other words 0.6 s/frame and 0.7 s/frame, on the two test videos.