Vehicle Reidentification Review
– From Dr. Shin-Ting Jeng’s Ph.D. thesis (UC Irvine).
Introduction to vehicle reidentification
The conventional traffic sensors typically provide volume, occupancy, vehicle presence and speed data. Vehicle reidentification is an emerging advanced sensor technology that aims to provide more data for the purposes of travel information, travel time estimation, and origin-destination (OD) estimation applications. According to the technologies applied, the vehicle reidentification systems can be categorized as:
The first three systems described above can be categorized as “Intrusive detection systems” which employ vehicles as a sensor. Although intrusive detection systems could provide more accurate vehicle tracking results, the limitations involved due to market penetration problems and privacy concerns are major obstacles to deploy intrusive sensors in a wide-area traffic surveillance system (Oh, 2003).
As opposites of intrusive detection systems, non-intrusive detection systems are almost free from privacy concerns and market penetration problem. Among the non-intrusive detection systems ILDs, although not without limitations as a traffic sensor, are widely used for historical reasons and the sunken investment in the large installed base makes their use in this dissertation highly cost-effective. Moreover, the ILD-based systems have proven their capability for anonymous vehicle tracking in previous studies, and could be potentially applied to reidentify individual vehicles across multiple detection stations.
ILD-VReID Algorithms
ILD based vehicle ReIDentification (hereafter ILD-VReID) systems track vehicles via vehicle signature reidentification algorithms. An ILD-VReID system aims to reidentify vehicles by utilizing inductive vehicle signatures. The resulting change in inductance due to the passage of a vehicle over a loop detector makes it possible to measure an inductive vehicle signature, which ideally is unique to that vehicle. Advantages of employing an ILD-based system include tracing vehicles individually across multiple detection stations without privacy concerns, relatively inexpensive deployment, reproducible vehicle signatures, less complexity of analysis, and fewer market penetration problems.
The initial investigation of ILD-VReID was carried out in 1980’s. Böhnke and Pfannerstill (Böhnke and Pfannerstil, 1986; Pfannerstil, 1989) first noticed that section-related traffic data could be obtained via reidentifying platoons of vehicles passing through a section of a road. The inductive vehicle signatures were treated as the input of a pattern recognition system developed by this research, and the system was intended to reidentify a platoon of vehicles.
Kühne and Immes (1993) proposed an approach, which can reidentify a platoon of vehicles via finding the correlation of vehicle feature series at downstream and upstream sites. However, the algorithm aimed to identify vehicle types rather than reidentifying each individual vehicle. Later on, Kühne et al. (1997) suggested a more sophisticated method, which can identify single vehicles (vehicle types) and vehicle platoons. The improved algorithm first normalized vehicle signatures in order to eliminate the system sensitivity and detector-specific effects. The features thus obtained were processed for feature comparison. The authors suggested that reidentifying a single vehicle with absolute accuracy was not necessary for accurate section-related measures and ten percent of the traffic population was able to generate significant results. Furthermore, they also suggest that, “The most promising approach is a mixture of single vehicle and vehicle platoon reidentification which use weighting functions … (Kühne et al., 1997).”
Sun et al. (Sun, 1998; Sun et al., 1999) suggested an approach, which provided a solution to reidentify single vehicles via lexicographic optimization for freeways. In this algorithm, the vehicle reidentification problem was defined as given a downstream vehicle signature, to find the corresponding vehicle signature within a candidate vehicle set obtained from an immediately upstream station. Accordingly, five levels were defined in this lexicographic optimization problem including time window determination, vehicle classification, vehicle length restriction, vehicle features differences minimization and vehicle matching. The reidentification rates of passenger vehicle and non-passenger vehicle were 75% and 78% respectively. Furthermore, Tabib and Abdulhai (Tabib, 2001; Abdulhai and Tabib, 2002) attempted to improve the fourth level of Sun et al’s model using different distance measurements. It was found that adopting “waveform shift” could bring in more consistent and reliable reidentification results due to its insensitivity to congestion level.
Following Sun et al.’s framework, Oh and Ritchie (Oh and Ritchie, 2002; Oh, 2003) extended the vehicle reidentification techniques from freeway to a single signalization intersection. To address the turning movement characteristic at intersection, a turning filtering optimization level was added to the original model. The turning filtering algorithm thus developed mainly depended on travel time estimation for each turning movement (left turn, through, and right turn movements). The reidentification rates under congested and non-congested traffic condition for through movement vehicles were 72.1% and 80.9% respectively.
A decision tree for ILD-VReID was suggested by Tawfik et al. (2004). Their model integrated distances measurements (Abdulhai and Tabib, 2002) into the decision tree developed by their previous study (2002). The authors pointed out that although the results demonstrated significant improvement of reidentification rate (90%), this method was recommended as a post-processing method for system performance evaluation.
The preceding studies were following the assumption that each vehicle possesses distinct features, and the procedure of up-to-date ILD-VReID algorithms (Sun et al., 1999; Oh and Ritchie, 2003; Sun, 1998; Oh and Ritchie, 2002; Oh, Ritchie and Park, 2002) can be illustrated as shown in the Figure below. In the Figure, the obtained raw vehicle signatures are normalized based on estimated speed (Sun and Ritchie, 1999; Oh, Ritchie and Park, 2002; Oh, Ritchie and Oh, 2002), and then the salient features are extracted for the use of matching vehicle signatures. Furthermore, to reduce the size of feasible search space before matching vehicle features, a spatial search space reduction and a temporal search space reduction are performed.
Figure. The procedure of ILD-VReID algorithm.
The task of spatial search space reduction is to identify the upstream origin of each vehicle and a turning movement classification is implemented. There are two cases for spatial search space reduction: freeway and arterial. For the freeway case, the upstream origin can be mainline detection stations and/or ramp detection stations. The arterial case is considered more challenging than the freeway case since the traffic flow on the arterials are interrupted by signal control. Given a downstream detection station, there are three possible upstream origins if the downstream intersection has four approaches. The details of finding upstream origins for the arterial case are described elsewhere (Oh, 2003; Oh, Ritchie and Park, 2002).
For temporal search space reduction, a time window restriction is applied. The aim of temporal search space reduction is to determine a feasible and reasonable time period that the correct vehicle can be included in the candidate vehicle set. Besides, the computational efficiency should be satisfied at the same time. Therefore, the estimated travel time is utilized to set up the lower and the upper bounds of the desired time window. Additionally, signal control (e.g. ramp metering and signalized intersection), detected speed, and posted speed limit are the key factors that affect the travel time estimation. A candidate vehicle set can then be found after spatial and temporal search space reduction processes. Finally, each vehicle is reidentified via vehicle features matching among its corresponding candidate vehicle set.
Although the aforementioned algorithm can bring out up to 80% correct matching rate, several potential disadvantages exist. First, there are estimation processes involved in the procedure of the algorithm including speed estimation, searching upstream origin, and travel time estimation. The accuracy of the estimation processes may deteriorate the later vehicle signature mapping to a certain extent, especially for cases when the system is equipped with single loops. For instance, speed information is essential to the extract electronic vehicle length feature, which is an important feature for the lexicographic method (as described below). Since single loop speed estimation is required in the single loop case, the accuracy of the estimated speed will affect the results of electronic vehicle length feature extraction. Secondly, vehicle features extraction aims to differentiate vehicles sufficiently. It is necessary to maintain sufficient minimum vehicle features to deal with the computational complexity; however, the selected vehicle features used in the ILD-VReID algorithm may not be adequate to represent a vehicle.
Thirdly, for the current applied ILD-VReID algorithms, the lexicographic optimization method is adopted. As mentioned above, five levels are defined in the optimization process (Sun et al., 1999). For the first level, the time window can be deterministically or dynamically defined using historical travel times for off-line analysis, and latest maximum and minimum travel times or current local speeds for on-line implementation. However, when there are single loop detectors placed in the network, a single loop speed estimation algorithm is necessary (Sun and Ritchie, 1999; Oh, Ritchie and Oh, 2002) in order to construct the time window; but our experience to date is that use of such algorithms causes vehicle reidentification performance to decline. In addition, the speed estimation algorithms may vary for different types of loop detectors (e.g. square loops or round loops) and a calibration is necessary prior to the implementation. Furthermore, for the objective function in the fourth level, the weights are determined using historical data, and the optimal distance measure is selected in fifth level using the historical/calibration dataset (Sun et al, 1999). Although these procedures can be performed in real-time, the task of defining a training set used for fourth and fifth levels, and the optimization procedure will complicate the ILD-VReID problem. Finally, the estimated travel times are obtained using a subset of vehicles with higher match probability, and discriminant thresholds are used for this purpose. However, since the size of the subset is a function of the discriminant threshold, it should be chosen carefully (Sun et al, 1999).
To address those difficulties, an inductive loop signature-based method for vehicle reidentification, named REID-2 was proposed by the authors (Jeng and Ritchie, 2005). REID-2 used an interpolation method, involved no speed estimation models and was straightforward and readily applied to both single and double loop detectors. The results showed that REID-2 was comparable with the lexicographic vehicle reidentification method (REID-1) previously developed and used at UCI (Park and Ritchie, 2004; Sun et al., 1999), and was even superior when applied to the single loop case. The key advantage of this method over existing approaches developed by the same research group was straightforward application to round as well as square inductive loops in single loop configurations (eliminating the requirement for either double-loop speed trap configurations or single loop speed estimation models). This was important for several reasons. First, round single loop detector stations are far more common than square loop stations in many locations, including California. Second, traffic operations field computational resources as well as the bandwidth of field communication links are often quite limited. Accordingly, for real-time or on-line implementation of ATMIS strategies, such as vehicle reidentification, there is strong interest in development of field—based techniques and models that can perform satisfactorily while minimizing field computational and communication requirements. This can be achieved through use of simplified algorithms, and reducing the number and size of data items to be communicated from the field. The relative importance of each of these aspects may vary with different applications, system architectures and hardware and software environments, but each can play an important role.
Kwon and Parsekar (2005) presented a deconvolution method of processing inductance waveforms for vehicle reidentification. The research goal was to restore the lost features of vehicle signatures caused by a relatively large detection zone via applying a deconvolution process. The results showed that about 89% of reidentification accuracy could be achieved via moving the deconvolved signature over likely matches and finding the minimum difference. The performance summary also indicated that the computation time was 6.8 seconds given 562 vehicles given deconvolved signatures.
A follow-up study of REID-2 (Jeng and Ritchie, 2005) was conducted by Jeng and Ritchie (2006). The vehicle reidentification algorithm REID-2 was oriented toward algorithm simplification. REID-2 also demonstrated the added benefits of improved performance and much broader potential applicability (to both round and square single inductive loops) compared with earlier methods. However, the basis of REID-2 is matching inductive vehicle signatures directly. In other words, raw vehicle signatures, which typically consist of 200~1,200 data points (stored as integers, and obtained from IST-222 detector cards) per signature, are utilized as the inputs for REID-2. Therefore, the authors recently developed an algorithm, RTREID-2 (Jeng and Ritchie, 2006), using inductive loop signature-based methods for vehicle reidentification (ILD-VReID) and which was dedicated to meet the needs for real-time implementation and section performance measurement. RTREID-2 was developed by utilizing a Piecewise Slope Rate (PSR) approach to transform the raw vehicle signatures obtained from square loops. The key advantage of RTREID-2 is straightforward application to square, as well as potentially round, inductive loop sensors in a single loop configuration (eliminating the requirement for either double-loop speed trap configurations or single loop speed estimation models).
Applications of ILD-VReID
Although individual detection stations can provide essential traffic information, section-related data is seen to be more reliable and accurate inputs for traffic surveillance and performance measurement systems (Böhnke and Pfannerstill, 1986; Kühne et al., 1997; Sun et al., 1999; Oh and Ritchie, 2002; Oh and Ritchie, 2003; Park and Ritchie, 2004; Oh, Tok and Ritchie, 2004). The development of traffic surveillance and performance measurement systems can benefit from utilizing ILD-VReID since section-related data can be easily generated using the results of ILD-VReID.
Kühne et al. (1997) pointed out that a traffic control system using section-related data was more sensitive for congestion detection and delay estimation than using local data in their case study. The results of Sun et al. (1999) also indicated that estimated section travel times and section densities for both congested and moderate flow data had trivial error (less than 4%). Furthermore, Park and Ritchie (2004) demonstrated the capability of ILD-VReID in vehicle classification, speed variance analysis and driver’s lane changing behavior analysis. The results of this case study show that section speed variability was highly influenced by lane change behaviors and long vehicles.
In addition, ILD-VReID can be applied to real-time level-of service (LOS) criteria development. Oh and Ritchie (2002) suggested that the real-time LOS criteria for signalized intersections are useful for real-time performance evaluation and travel information. More recently, Oh, Tok, and Ritchie (2004) extended their original work into freeway system. It is worth noting that the real-time LOS criteria for both intersections and freeway surveillance systems are readily transferable to other similarly equipped systems.
OD Estimation is one further application of ILD-VReID. OD information can be obtained via utilizing the outputs of ILD-VReID. Oh (2003) set up a procedure for time-variant OD estimation for signalized network using Monte Carlo simulation method. The inputs of the procedure, i.e. the estimated flow, were obtained from the results of ILD-VReID. Path travel time (Oh and Ritchie, 2003) can also be obtained through the OD estimation procedure; however, the accuracy of the estimated path travel time may not be effective if a low reidentification rate is represented along the path.
References
Abdulhai, B., Tabib, S. M., 2002. Towards anonymous vehicle tracking via inductance-pattern recognition. In: Proceedings of Transportation Research Board 81st Annual Meeting, January 13-17. Washington, DC.
Böhnke, p., Pfannerstill, E., 1986. A system for the automatic surveillance of traffic situations. ITE Journal, 56, 41-45.
Jeng, S.-T., Ritchie, S. G., 2005. A new inductive signature method for vehicle reidentification. In: Proceedings of Transportation Research Board 84th Annual Meeting, January 9-13. Washington, DC.
Jeng, S.-T., Ritchie, S. G., 2006. A New Inductive Signature Data Compression and Transformation Method for On-Line Vehicle Reidentification. In: Proceedings of Transportation Research Board 85th Annual Meeting, January 22-26. Washington, DC.
Kühne, R. D., Immes, S., 1993. Freeway control systems for using section-related traffic variable detection. In: Pacific Rim. Trans. Tech. Conference, July 25-28. Seattle, Washington.
Kühne. R. D., Palen, J., Gardner, C., Ritchie, S. G., 1997. Section-related measure of traffic system performance. In: Proceedings of Transportation Research Board 76th Annual Meeting, January 12-16. Washington, DC.
Kwon, T. M., Parsekar, A., 2005. Exploring the relationship between freeway speed variance, land changing, and vehicle heterogeneity. In: Proceedings of Transportation Research Board 84th Annual Meeting, January 9-13. Washington, DC.
Oh, C., 2003. Anonymous vehicle tracking for real-time performance measures. Ph.D. Dissertation, University of California, Irvine.
Oh, C., Ritchie, S. G., 2002. Real-time inductive-signature-based level of service for signalized intersections. Transportation Research Record, 1802, 97-104.
Oh, C., Ritchie, S. G., 2003. Anonymous vehicle tracking for real-time traffic surveillance and performance on signalized arterials. In: Proceedings of Transportation Research Board 82nd Annual Meeting, January 12-16. Washington, DC.
Oh, C., Ritchie, S. G., Jeng, S.-T., 2004. Anonymous vehicle reidentification with heterogeneous detection systems. In: Proceedings of Transportation Research Board 83rd Annual Meeting, January 11-15. Washington, DC.
Oh, C., Ritchie, S. G., Park, S., 2002. Development of a real-time probabilistic vehicle reidentification algorithm for signalized intersections. ITS Working Paper, Institute of Transportation Studies, University of California, Irvine.
Oh, C., Tok, A., Ritchie, S. G., 2004. Real-time freeway level of service based on anonymous vehicle re-identification. In: Proceedings of Transportation Research Board 83rd Annual Meeting, January 11-15. Washington, DC.
Oh, S., Ritchie, S. G., Oh, C., 2002. Real-time traffic measurement from single loop inductive signatures. Transportation Research Record, 1804, 98-106.
Park, S., Ritchie, S. G., 2004. Exploring the relationship between freeway speed variance, land changing, and vehicle heterogeneity. In: Proceedings of Transportation Research Board 83rd Annual Meeting, January 11-15. Washington, DC.
Pfannerstill, E., 1989. Automatic monitoring of traffic conditions by reidentification of vehicles. In: Proceedings of IEEE Conference on Road Traffic Monitoring, 299, 172-175.
Sun, C., 1998. Use of vehicle signature analysis and lexicographic optimization for vehicle reidentification on freeways. Ph.D. Dissertation, University of California, Irvine.
Sun, C., Ritchie, S. G., 1999. Individual vehicle speed estimation using single loop inductive waveforms. Journal of Transportation Engineering, 125 (6), 531-538.
Sun, C., Ritchie, S. G., Tsai, K., Jayakrishnan, R., 1999. Use of vehicle signature analysis and lexicographic optimization for vehicle reidentification on freeways. Transportation Research, 7C (4), 167-185.
Tabib, S. M., 2001. Vehicle re-identification based on inductance signature matching. Master Thesis, University of Toronto.
Tawfik, A. Y., Abdulhai, B., Peng, A., Tabib S. M., 2004. Improving the accuracy of vehicle signature reidentification using decision trees. In: Proceedings of Transportation Research Board 83rd Annual Meeting, January 11-15. Washington, DC.