Abstract:
A system and method for predicting whether a vehicle will come to a stop at an intersection is provided. Generally, the system contains a memory; and a processor configured by the memory to perform the steps of: generating a prediction of whether the vehicle will or will not stop at the intersection before a first time based on vehicle data measured during a first time window; and at a second time, the second time being before the first time and approximately equal to a time at which the time window ends, providing an indication that the vehicle will not stop at the intersection before the first time based upon the prediction, wherein generating the prediction comprises using a classification model, the classification model configured to indicate whether the vehicle will or will not stop at the intersection before the first time based on a plurality of input parameters, and wherein the plurality of input parameters are selected from the group consisting of speed, acceleration, and distance to the intersection.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
       [0001]    This application claims priority to copending U.S. Provisional Application entitled, “ALGORITHMS FOR DRIVER BEHAVIOR CLASSIFICATION AT INTERSECTIONS VALIDATED ON LARGE NATURALISTIC DATA SET,” having Ser. No. 61/677,033, filed Jul. 30, 2012, which is entirely incorporated herein by reference. 
     
    
     STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT 
       [0002]    This invention was made with government support under Contract No. N68335-09-C-0472 awarded by the U.S. Navy Naval Air Systems Command. The government has certain rights in the invention. 
     
    
     FIELD OF THE INVENTION 
       [0003]    The present invention is generally related to sensing and computational technologies for increasing road safety, and more particularly is related to driver behavior classification and validation. 
       BACKGROUND OF THE INVENTION 
       [0004]    The field of road safety and safe driving has witnessed rapid advances due to improvements in sensing and computation technologies. Active safety features such as antilock braking systems and adaptive cruise control have widely been deployed in automobiles to reduce road accidents. However, the U.S. Department of Transportation (DOT) still classifies road safety as “a serious and national public health issue.” In 2008, road accidents in the U.S. caused 37,261 fatalities and about 2.35 million injuries. A particularly challenging driving task is negotiating traffic intersection safely. An estimated 45% of injury crashes and 22% of roadway fatalities in the U.S. are intersection related. A main contributing factor in these accidents is the inability of a driver to correctly assess and/or observe danger involved in such situations. These data suggest that driver assistance or warning systems may have an appropriate role in reducing the number of accidents, improving the safety and efficiency of human-driven ground transportation systems. Such systems typically augment the situational awareness of the driver and can also act as collision mitigation systems. 
         [0005]    Research on intersection decision support systems has become quite active in both academia and the automotive industry. In the US, the federal DOT, in conjunction with the California, Minnesota, and Virginia DOTs, as well as several U.S. research universities, is sponsoring the Intersection Decision Support project and, more recently, the Cooperative Intersection Collision Avoidance Systems (CICAS) project. In Europe, the InterSafe project was created by the European Commission to increase safety at intersections. The partners in the InterSafe project include European vehicle manufacturers and research institutes. Both projects try to explore the requirements, tradeoffs, and technologies required to create an intersection collision avoidance system and demonstrate its applicability on selected dangerous scenarios. 
         [0006]    Inferring driver intentions has been the subject of extensive research. For example, mind-tracking approaches have been introduced that extract the similarity of driver data to several virtual drivers created probabilistically using a cognitive model. In addition, other approaches have used graphical models and hidden Markov models (HMMs) to create and train models of different driver maneuvers using experimental driving data. 
         [0007]    More specifically, the modeling of behavior at intersections has been studied using different statistical models. These studies have showed that the stopping at intersections behavior depends on several factors including driver profile (e.g., age and perception-reaction time) and yellow-onset kinematic and geometric parameters (e.g., vehicle speed and distance to intersection). One approach has developed red light running predictors based on estimating the time-to-arrival at intersections and the different stop-and-go maneuvers. It used speed measurements at two discrete point sensors, but the performance of this approach is limited by the complexity of the multidimensional optimization problem that must be solved. 
         [0008]    A paper entitled “Intersection Decision Support: Evaluation of a Violation Warning System to Mitigate Striaght Crossing Path Crashes (report no. vtrc 06-cr10),” by V Neale. M. erez, Z. Doerzaph, S. Lee, S. Stone, and T. DingusVirginia Trans. Res. Council 2006, discusses the use of time-to-intersection (TTI) and its advantages over time-to-collision (TTC) for intersection safety systems. In addition, a paper entitled, “Cooperative intersection collision avoidance for violations: Threat assessment algorithm development and evaluation method,” by Z. Doerzaph, V. Neale, and R. Kiefer, presented at the Transportation Research Board 89th Annual Meeting, Washington, D.C., 2010, Paper 10-2748, illustrates how different warning algorithms are developed for signalized and stop intersections based on a required deceleration parameter (RDP), TTI, and speed-distance regression (SDR) models. It is noted, however, that these authors only consider very simple relationships between the driving parameters, and do not combine flexibility to combine many parameters in the same model. 
         [0009]    Thus, a heretofore unaddressed need exists in the industry to address the aforementioned deficiencies and inadequacies. 
       SUMMARY OF THE INVENTION 
       [0010]    Embodiments of the present invention provide a system and method for predicting whether a vehicle will come to a stop at an intersection and classifying the vehicle accordingly. Briefly described, in architecture, one embodiment of the system, among others, can be implemented as follows. Generally, the system contains a memory; and a processor configured by the memory to perform the steps of: generating a prediction of whether the vehicle will or will not stop at the intersection before a first time based on vehicle data measured during a first time window; and at a second time, the second time being before the first time and approximately equal to a time at which the time window ends, providing an indication that the vehicle will not stop at the intersection before the first time based upon the prediction, wherein generating the prediction comprises using a classification model, the classification model configured to indicate whether the vehicle will or will not stop at the intersection before the first time based on a plurality of input parameters, and wherein the plurality of input parameters are selected from the group consisting of speed, acceleration, and distance to the intersection. 
         [0011]    Other systems, methods, features, and advantages of the present invention will be or become apparent to one with skill in the art upon examination of the following drawings and detailed description. It is intended that all such additional systems, methods, features, and advantages be included within this description, be within the scope of the present invention, and be protected by the accompanying claims. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0012]    Many aspects of the invention can be better understood with reference to the following drawings. The components in the drawings are not necessarily to scale, emphasis instead being placed upon clearly illustrating the principles of the present invention. Moreover, in the drawings, like reference numerals designate corresponding parts throughout the several views. 
           [0013]      FIG. 1  is a schematic diagram illustrating an intersection controlled by a traffic signal, in which the present classifier may be implemented. 
           [0014]      FIG. 2  is a schematic diagram illustrating a classifier in accordance with a first exemplary embodiment of the invention. 
           [0015]      FIG. 3  is a schematic diagram illustrating different warning-related variables as used by the classifier of  FIG. 2 . 
           [0016]      FIG. 4  is a schematic diagram illustrating architecture of the SVM-BF algorithm used by the classifier of  FIG. 2 . 
           [0017]      FIG. 5  is a flowchart describing the basic functions performed by the SVM-BF algorithm, in accordance with the first exemplary embodiment of the invention. 
           [0018]      FIG. 6  is a flowchart illustrating steps taken by the HMM-based architecture used by the classifier of  FIG. 2 . 
           [0019]      FIG. 7  is a schematic diagram summarizing the HMM-based architecture. 
           [0020]      FIG. 8  is a schematic diagram illustrating an HMM λ(T, t, e) consisting of a set of n discrete states and a set of observations at each state. 
           [0021]      FIG. 9  is a schematic diagram illustrating ten combinations of key parameters for the SVM-BR classifier that produced the highest rates of true positives while maintaining a false positive rate below 5% for one basic generalization test. 
           [0022]      FIG. 10  is a schematic diagram illustrating ten combinations of key parameters for the HMM-based classifier that produced the highest rates of true positives while maintaining a false positive rate below 5% for one basic generalization test. 
       
    
    
     DETAILED DESCRIPTION 
       [0023]    The present system and method estimates driver behavior at signalized road intersections and validates the estimations on real traffic data. Functionality is introduced to classify drivers as compliant or violating. Two approaches are provided for classifying driver behavior at signalized road intersections. The first approach combines a support vector machine (SVM) classifier with Bayesian filtering (BF) to discriminate between compliant drivers and violators based on vehicle speed, acceleration, and distance to intersection. The second approach, which is a hidden Markov model (HMM)-based classifier, uses an expectation-maximization (EM) algorithm to develop two distinct HMMs for compliant and violating behaviors. 
         [0024]    The present system and method infers driver behavior at signalized road intersections and validates them using naturalistic data. As is exemplified in further detail herein, the system and method may be provided in vehicle-based systems, infrastructure-based systems, or other systems. 
         [0025]    Classes of algorithms as described herein are provided based on distinct branches of classification in machine learning to model driver behaviors at signalized intersections. The present system and method validates these algorithms on a large naturalistic data set. 
         [0026]    The present invention considers an intersection controlled by a traffic signal, as shown by the schematic diagram of  FIG. 1 . As a vehicle approaches the intersection, the objective is to predict from a set of observations whether a driver of the vehicle will stop safely if the signal indicates to do so. Drivers who do not stop before the stop bar are considered to be violators  1 , whereas those who do stop are considered to be compliant  3 . Naturally, drivers behave differently, and the variation in the resulting observations must be taken into account in a human classification process. 
         [0027]    The ability to classify human drivers lays the foundation for more advanced driver assistance systems, which are enabled by the present system and method. In particular, these systems are able to warn drivers of their own potential violations as well as detect other potential violators approaching the intersection. Integrating the classifier of the present invention into a driver assistance system imposes performance constraints that balance violator detection accuracy with driver annoyance. 
         [0028]    It should be noted that while the present disclosure describes the classification of human drivers, one having ordinary skill in the art would appreciate that classification may be provided for vehicles that do not have human drivers. The following provides for analysis and handling of both situations. 
         [0029]    Functionality of the classifier  10  of the present invention can be implemented in software, firmware, hardware, or a combination thereof. In a first exemplary embodiment, functionality of the classifier  10  may be implemented in software, as an executable program, and is executed by a special or general-purpose digital computer, such as a personal computer, a personal data assistant, a computing module located on a vehicle, such as, but not limited to, for providing a driver assistance system, a smart phone, a workstation, a minicomputer, or a mainframe computer. The first exemplary embodiment of a classifier  10  is shown in  FIG. 2 . 
         [0030]    Generally, in terms of hardware architecture, as shown in  FIG. 2 , the classifier  10  includes a processor  12 , memory  20 , storage device  30 , and one or more input and/or output (I/O) devices  32  (or peripherals) that are communicatively coupled via a local interface  34 . The local interface  34  can be, for example but not limited to, one or more buses or other wired or wireless connections, as is known in the art. The local interface  34  may have additional elements, which are omitted for simplicity, such as controllers, buffers (caches), drivers, repeaters, and receivers, to enable communications. Further, the local interface  34  may include address, control, and/or data connections to enable appropriate communications among the aforementioned components. 
         [0031]    The processor  12  is a hardware device for executing software, particularly that stored in the memory  20 . The processor  12  can be any custom made or commercially available processor, a central processing unit (CPU), an auxiliary processor among several processors associated with the classifier  10 , a semiconductor based microprocessor (in the form of a microchip or chip set), a macroprocessor, or generally any device for executing software instructions. 
         [0032]    The memory  20  can include any one or combination of volatile memory elements (e.g., random access memory (RAM, such as DRAM, SRAM, SDRAM, etc.)) and nonvolatile memory elements (e.g., ROM, hard drive, tape, CDROM, etc.). Moreover, the memory  20  may incorporate electronic, magnetic, optical, and/or other types of storage media. Note that the memory  20  can have a distributed architecture, where various components are situated remote from one another, but can be accessed by the processor  12 . 
         [0033]    The software  22  in the memory  20  may include one or more separate programs, each of which contains an ordered listing of executable instructions for implementing logical functions of the classifier  10 , including, but not limited to, the algorithms described hereinbelow. In the example of  FIG. 2 , the software  22  in the memory  20  defines the classifier  10  functionality in accordance with the present invention. In addition, although not required, it is possible for the memory  20  to contain an operating system (O/S)  36 . The operating system  36  essentially controls the execution of computer programs and provides scheduling, input-output control, file and data management, memory management, and communication control and related services. 
         [0034]    Functionality of the classifier  10  may be provided by a source program, executable program (object code), script, or any other entity containing a set of instructions to be performed. When a source program, then the program needs to be translated via a compiler, assembler, interpreter, or the like, which may or may not be included within the memory  20 , so as to operate properly in connection with the O/S  36 . Furthermore, the classifier  10  can be written as (a) an object oriented programming language, which has classes of data and methods, or (b) a procedure programming language, which has routines, subroutines, and/or functions. 
         [0035]    The I/O devices  32  may include input devices, for example but not limited to, a touch screen, a keyboard, mouse, scanner, microphone, or other input device. Furthermore, the I/O devices  32  may also include output devices, for example but not limited to, a display, loudspeaker, or other output devices. The I/O devices  32  may further include devices that communicate via both inputs and outputs, for instance but not limited to, a modulator/demodulator (modem; for accessing another device, system, or network), a radio frequency (RF), wireless, or other transceiver, a telephonic interface, a bridge, a router, or other devices that function both as an input and an output. 
         [0036]    When the classifier  10  is in operation, the processor  12  is configured to execute the software  22  stored within the memory  20 , to communicate data to and from the memory  20 , and to generally control operations of the classifier  10  pursuant to the software  22 . The software  22  and the O/S  36 , in whole or in part, but typically the latter, are read by the processor  12 , perhaps buffered within the processor  12 , and then executed. 
         [0037]    When functionality of the classifier  10  is implemented in software, as is shown in  FIG. 2 , it should be noted that the functionality can be stored on any computer readable medium for use by or in connection with any computer related system or method. In the context of this document, a computer readable medium is an electronic, magnetic, optical, or other physical device or means that can contain or store a computer program for use by or in connection with a computer related system or method. The classifier  10  can be embodied in any computer-readable medium for use by or in connection with an instruction execution system, apparatus, or device, such as a computer-based system, processor-containing system, or other system that can fetch the instructions from the instruction execution system, apparatus, or device and execute the instructions. In the context of this document, a “computer-readable medium” can be any means that can store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device. 
         [0038]    The computer readable medium can be, for example but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, device, or propagation medium. More specific examples (a nonexhaustive list) of the computer-readable medium would include the following: an electrical connection (electronic) having one or more wires, a portable computer diskette (magnetic), a random access memory (RAM) (electronic), a read-only memory (ROM) (electronic), an erasable programmable read-only memory (EPROM, EEPROM, or Flash memory) (electronic), an optical fiber (optical), and a portable compact disc read-only memory (CDROM) (optical). Note that the computer-readable medium could even be paper or another suitable medium upon which the program is printed, as the program can be electronically captured, via for instance optical scanning of the paper or other medium, then compiled, interpreted or otherwise processed in a suitable manner if necessary, and then stored in a computer memory. 
         [0039]    The storage device  30  of the classifier  10  is optional and may be one of many different types of storage device, including a stationary storage device or portable storage device. As an example, the storage device  30  may be a magnetic tape, disk, flash memory, volatile memory, or a different storage device. In addition, the storage device may be a secure digital memory card or any other removable storage device  30 . The storage device  30  may store different data therein, such as, but not limited to, data history collected regarding vehicles approaching an intersection, including vehicle speed, range (position), and acceleration (also referred to as kinematic data). In addition, the storage device  30  may store data history specific to the driver of the vehicle. This enables a driver to switch vehicles and bring his/her own data history into the new vehicle. As a result, the present system and method is capable of providing driver specific results in situations when drivers switch vehicles. 
         [0040]    It should be noted that in accordance with the present invention, the classifier may be located in one or more different locations. As an example, as previously mentioned, the classifier may be located within a vehicle. For instance, the classifier may or may not be incorporated as a part of a larger vehicle driver assistance system. Alternatively, the classifier may be located within a controller located at an intersection communicating results of classification of vehicles and detection of violating drivers (violating vehicles). Communication of classification of vehicles and detection of violating driver results may be vehicle to vehicle or vehicle to communication infrastructure. Such a communication infrastructure may be any known communication infrastructure allowing for the transmission and receipt of data. 
         [0041]    The previously mentioned requirement of being able to integrate the classifier into a driver assistance system while balancing violator detection accuracy with driver annoyance can be encoded in terms of signal detection theory (SDT), which provides a framework for evaluating decisions made in uncertain situations. Table I., illustrated below, shows the mapping between classifier output and SDT categories. To meet this performance constraint, the classifier maximizes the number of true positives (to correctly identify violators) while maintaining a low ratio of false positives (to minimize driver annoyance). 
         [0000]    
       
         
               
               
               
               
             
           
               
                   
                 TABLE I 
               
               
                   
                   
               
               
                   
                   
                 Classification: 
                 Classification: 
               
               
                   
                   
                 Compliant 
                 Violating 
               
               
                   
                   
               
             
             
               
                   
                 Actual: Compliant 
                 True Negative 
                 False Positive 
               
               
                   
                 Actual: Violating 
                 False Negative 
                 True Positive 
               
               
                   
                   
               
             
          
         
       
     
         [0042]    An underlying assumption for this classification is the availability of communication or sensing infrastructure to provide the observations needed to classify the driver&#39;s behavior and enable the detection of traffic signal phase. Vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I) communication systems would provide exactly this functionality. Alternatively, onboard sensors could be used to make these observations, particularly when warning drivers of their own impending violations. 
         [0043]    While several scenarios could be considered for this problem, for simplicity of understanding, the present description provides the example of one host vehicle and several target vehicles. The goal is to warn the host vehicle when any of the target vehicles is predicted not to comply with the traffic lights. To further specify the problem, the following assumptions are made. 
         [0044]    1) The host vehicle has the right of way and is compliant. Only the target vehicles that do not have the right of way are considered in the problem; the other vehicles (i.e., with right of way) are ignored. In other words, the focus is on warning compliant drivers from the danger created by other potentially violating drivers. An implicit assumption is the existence of V2V and V2I systems to detect the traffic signal phase and to share position, speed (velocity), and acceleration information among vehicles (also referred to as kinematic data). 
         [0045]    2) The host vehicle is warned at t warn  only when a target vehicle is classified as violating. The schematic diagram of  FIG. 3  illustrates the different warning-related variables. t warn  corresponds to the time when a target vehicle&#39;s estimated time to arrive at the intersection, also known as TTI, reaches TTI min  seconds, or when the distance of a target vehicle to the intersection is equal to d min  meters, whichever condition happens first. The time and distance thresholds are chosen such that the host driver has enough time to react to the warning. A detailed analysis of the choice of TTI min  and d min  is presented hereinbelow when describing implementation with shared parameters. 
         [0046]    3) The target vehicles are tracked as early as possible, but their classification as violating or compliant is based on measurements taken in the T w  time window as illustrated by  FIG. 3 . Different values of T w  are analyzed in the developed algorithms; a larger T w  brings a longer measurement “memory” at the expense of an additional computation requirement. A large T w  might also include irrelevant measurements when the vehicle is very far from the intersection. Finally, it is noted that a target vehicle that stops in or before the T w  window is directly labeled as compliant. 
         [0047]    Classification 
         [0048]    Classifying human drivers as either compliant or as a violator is a complex process because of various nuances and peculiarities of human behaviors. Basic classification is traditionally performed by identifying simple relationships or trends in data that define each class. This includes using techniques such as model fitting and regression to identify classification criteria. However, by only considering simple relationships, these approaches are limited in their ability to accurately classify complex data where the classes may be defined by a variety of factors. The present invention overcomes this limitation by use of at least one of two approaches by the classifier. A first approach is use of a discriminative approach based on support vector machines, and a second approach is use of a generative approach based on Hidden Markov Models (HMMs). Either one of these approaches may be used by the classifier in accordance with the present invention to assist in classifying human drivers as either compliant or as a violator of road intersection rules, specifically, whether a human driver will stop at an intersection red light or not. 
         [0049]    Discriminative approaches, such as Support Vector Machines (SVMs), are typically used in binary classification problems, which make them appropriate for the classification of compliant versus violating human drivers. SVMs have several useful theoretical and practical characteristics. The following highlights two of these characteristics: 1) training SVMs involves an optimization problem of a convex function, thus the optimal solution is a global solution (i.e., no local optima); 2) the upper bound on the generalization error does not depend on the dimensionality of the problem. 
         [0050]    Classification is often also performed using generative approaches, such as HMMs, to model the underlying patterns in a set of observations and explicitly compute the probability of observing a set of outputs for a given model. HMMs are well suited to the classification of dynamic systems, such as a vehicle approaching an intersection. The states of the HMM define different behavioral modes based on observations, and the transitions between these states capture the temporal relationship between observations. 
         [0051]    It should be noted that while the following provides algorithms for use in expressing functionality performed by the classifier, the present invention is not intended to be limited by use of only the algorithms described herein. Instead, functionality associated with such algorithms may be expressed by different algorithms or logic in general, all of which are intended to be included in the present invention. 
         [0052]    Discriminative Approach 
         [0053]    Use of the discriminative approach for classifying drivers, in accordance with the present invention, is described further herein. The discriminative approach, as used by the present system and method, combines SVM and Bayesian filtering, and is referred to herein as SVM-BF. In accordance with a first exemplary embodiment of the invention, the discriminative approach is provided as an algorithm. The core of the algorithm is the SVM, which is a supervised machine learning technique based on the margin-maximization principle. The present system and method combines SVM with a Bayesian filter (BF) that enables it to perform well on the driver behavior classification problem. The following introduces the architecture of the SVM-BF algorithm and provides additional theoretical and practical details about each of its components. 
         [0054]    SVM-BF Architecture 
         [0055]    The architecture of the SVM-BF algorithm is shown by the schematic diagram of  FIG. 4 . In addition, the flowchart  100  of  FIG. 5  describes the basic functions performed by the SVM-BF algorithm, in accordance with the first exemplary embodiment of the invention. It should be noted that any process descriptions or blocks in flowcharts should be understood as representing modules, segments, portions of code, or steps that include one or more instructions for implementing specific logical functions in the process, and alternative implementations are included within the scope of the present invention in which functions may be executed out of order from that shown or discussed, including substantially concurrently or in reverse order, depending on the functionality involved, as would be understood by those reasonably skilled in the art of the present invention. 
         [0056]    As shown by block  102 , at the beginning of each measurement cycle inside the T w  window, the SVM module (described hereinbelow) extracts the relevant features from sensor observations. It then outputs a single classification (violator versus compliant) per cycle to the BF component (described hereinbelow) (block  104 ). As shown by block  106 , at the end of the T w  window, namely, at time t warn , the BF component uses the current and previous SVM outputs to estimate the probability that the driver is compliant. Using a threshold detector, the SVM-BF outputs a final classification at t warn  specifying whether the driver is estimated as violator or compliant (block  108 ). 
         [0057]    In accordance with an alternative embodiment of the invention, to speed up the convergence of the BF component, a discount function is added to the SVM-BF designed to deemphasize earlier classifications in T w  and therefore put more weight on the measurements of the vehicles that are closer to t warn . 
         [0058]    SVM Module 
         [0059]    The following provides an introduction to SVMs and their implementation in the present SVM-BF framework. Further information regarding SVMs is provided by the publication entitled, “Support vector networks,” by C. Cortes and V. Vapnik, Mach. Learn., vol. 20, no. 3, pp. 273-297, September 1995, which is incorporated herein by reference in its entirety. 
         [0060]    Given a set of binary labeled training data {x i , y i } where i=1, . . . , N, y i ε{+1, −1}, x i ε           d , N is the number of training vectors, and d is the size of the input vector, a new test vector z is classified into one class (y=+1) or the other (y=−1) by evaluating the following decision function: 
         [0000]    
       
         
           
             
               
                 
                   
                     D 
                      
                     
                       ( 
                       z 
                       ) 
                     
                   
                   = 
                   
                     sgn 
                      
                     
                       [ 
                       
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               1 
                             
                             N 
                           
                            
                           
                             
                               α 
                               i 
                             
                              
                             
                               y 
                               i 
                             
                              
                             
                               K 
                                
                               
                                 ( 
                                 
                                   
                                     x 
                                     i 
                                   
                                   , 
                                   z 
                                 
                                 ) 
                               
                             
                           
                         
                         + 
                         B 
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   
                     Eq 
                     . 
                     
                         
                     
                      
                     1 
                   
                   ) 
                 
               
             
           
         
       
     
         [0000]    K(x i , x j ), which is known as the kernel function, is the inner product between the mapped pairs of points in the feature space, and B is the bias term. α is the argmax of the following optimization problem: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       max 
                       α 
                     
                      
                     
                       W 
                        
                       
                         ( 
                         α 
                         ) 
                       
                     
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         N 
                       
                        
                       
                         α 
                         i 
                       
                     
                     - 
                     
                       
                         1 
                         2 
                       
                        
                       
                         
                           ∑ 
                           
                             i 
                             , 
                             
                               j 
                               = 
                               1 
                             
                           
                           N 
                         
                          
                         
                           
                             α 
                             i 
                           
                            
                           
                             α 
                             j 
                           
                            
                           
                             y 
                             i 
                           
                            
                           
                             y 
                             j 
                           
                            
                           
                             K 
                              
                             
                               ( 
                               
                                 
                                   x 
                                   i 
                                 
                                 , 
                                 xj 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   
                     Eq 
                     . 
                     
                         
                     
                      
                     2 
                   
                   ) 
                 
               
             
           
         
       
     
         [0000]    subject to the constraints 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         1 
                       
                       N 
                     
                      
                     
                       
                         α 
                         i 
                       
                        
                       
                         y 
                         i 
                       
                     
                   
                   = 
                   
                     
                       0 
                        
                       
                         α 
                         i 
                       
                     
                     ≥ 
                     0 
                   
                 
               
               
                 
                   ( 
                   
                     Eq 
                     . 
                     
                         
                     
                      
                     3 
                   
                   ) 
                 
               
             
           
         
       
     
         [0061]    Appropriate kernel selection and feature choice are essential to obtaining satisfactory results using SVM. Based on experimenting with different kernel functions and several combinations of features, the best results for this problem were obtained using the Gaussian radial basis function and combining the following three features: 1) range to intersection; 2) speed; and 3) longitudinal acceleration. 
         [0062]    At each measurement cycle, the output of the SVM block is a classification y=+1 (compliant) or y=−1 (violator). This output is then fed into the Bayesian filtering module, as described hereinbelow, which uses additional logic before making a final classification. 
         [0063]    BF Module 
         [0064]    The following describes BF module implementation in the present SVM-BF framework. The BF module views the outputs of the SVM component as samples of a random variable yε{violator, compliant} that is controlled by a parameter θ such that 
         [0000]        p ( y =compliant|θ)=θ  (Eq. 4)
 
         [0065]    The parameter θ is unknown. It represents the probability that the driver belongs to the compliant class. The role of the BF module is to compute the expected value of θ given a sequence of previous outputs from the SVM module. 
         [0066]    To infer the value of the hidden variable, a standard Bayesian formulation is used. A beta distribution was selected prior for θ, which is a function of some hyperparameters a and b, for instance as shown by equation 5 
         [0000]    
       
         
           
             
               
                 
                   
                     beta 
                      
                     
                       ( 
                       
                         
                           θ 
                           | 
                           a 
                         
                         , 
                         b 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         Γ 
                          
                         
                           ( 
                           
                             a 
                             + 
                             b 
                           
                           ) 
                         
                       
                       
                         
                           Γ 
                            
                           
                             ( 
                             a 
                             ) 
                           
                         
                         + 
                         
                           Γ 
                            
                           
                             ( 
                             b 
                             ) 
                           
                         
                       
                     
                      
                     
                       
                         
                           θ 
                           
                             a 
                             - 
                             1 
                           
                         
                          
                         
                           ( 
                           
                             1 
                             - 
                             θ 
                           
                           ) 
                         
                       
                       
                         b 
                         - 
                         1 
                       
                     
                   
                 
               
               
                 
                   ( 
                   
                     Eq 
                     . 
                     
                         
                     
                      
                     5 
                   
                   ) 
                 
               
             
           
         
       
     
         [0000]    where Γ(x) is the gamma function. The values of a and b have an intuitive interpretation; they represent the initial “confidence” given for each class, respectively. In other words, they reflect the number of observations corresponding for each behavior, which were accumulated in previous measurement cycles. 
         [0067]    Given a sequence of SVM outputs y=[y 1 , . . . , y N ], the posterior distribution of θ, i.e., p(θ|y), is computed by multiplying the beta distribution prior by the binomial likelihood function given by equation 6 
         [0000]    
       
         
           
             
               
                 
                   
                     bin 
                      
                     
                       ( 
                       
                         
                           m 
                           | 
                           N 
                         
                         , 
                         θ 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       ( 
                       
                         
                           
                             N 
                           
                         
                         
                           
                             m 
                           
                         
                       
                       ) 
                     
                      
                     
                       
                         
                           θ 
                           m 
                         
                          
                         
                           ( 
                           
                             1 
                             - 
                             θ 
                           
                           ) 
                         
                       
                       
                         N 
                         - 
                         m 
                       
                     
                   
                 
               
               
                 
                   ( 
                   
                     Eq 
                     . 
                     
                         
                     
                      
                     6 
                   
                   ) 
                 
               
             
           
         
       
     
         [0000]    where m and l represent the number of SVM outputs corresponding to y=compliant and y=violator, respectively. The variable N is the total number of SVM classifications: N=m+l. By normalizing the resulting function, the following equation 7 is obtained. 
         [0000]    
       
         
           
             
               
                 
                   
                     p 
                      
                     
                       ( 
                       
                         θ 
                         | 
                         y 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         Γ 
                          
                         
                           ( 
                           
                             m 
                             + 
                             a 
                             + 
                             l 
                             + 
                             b 
                           
                           ) 
                         
                       
                       
                         
                           Γ 
                            
                           
                             ( 
                             
                               m 
                               + 
                               a 
                             
                             ) 
                           
                         
                         + 
                         
                           Γ 
                            
                           
                             ( 
                             
                               l 
                               + 
                               b 
                             
                             ) 
                           
                         
                       
                     
                      
                     
                       
                         
                           θ 
                           
                             m 
                             + 
                             a 
                             - 
                             1 
                           
                         
                          
                         
                           ( 
                           
                             1 
                             - 
                             θ 
                           
                           ) 
                         
                       
                       
                         l 
                         + 
                         b 
                         - 
                         1 
                       
                     
                   
                 
               
               
                 
                   ( 
                   
                     Eq 
                     . 
                     
                         
                     
                      
                     7 
                   
                   ) 
                 
               
             
           
         
       
     
         [0000]    The expected value of θ given the sequence y, which is the output of the BF component, can then be expressed by equation 8. 
         [0000]    
       
         
           
             
               
                 
                   
                     E 
                      
                     
                       ( 
                       
                         θ 
                         | 
                         y 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         ∫ 
                         0 
                         1 
                       
                        
                       
                         θ 
                          
                         
                             
                         
                          
                         
                           p 
                            
                           
                             ( 
                             
                               θ 
                               | 
                               y 
                             
                             ) 
                           
                         
                          
                         
                             
                         
                          
                         
                            
                           θ 
                         
                       
                     
                     = 
                     
                       
                         m 
                         + 
                         a 
                       
                       
                         m 
                         + 
                         a 
                         + 
                         l 
                         + 
                         b 
                       
                     
                   
                 
               
               
                 
                   ( 
                   
                     Eq 
                     . 
                     
                         
                     
                      
                     8 
                   
                   ) 
                 
               
             
           
         
       
     
         [0068]    Discount Function 
         [0069]    As previously mentioned, to speed up the convergence of the BF, a discount function is added to the SVM-BF designed to deemphasize earlier classifications in the T w  window and therefore put more weight on the measurements of the vehicles that are closer to t warn . 
         [0070]    To improve the accuracy of the expected value computed in equation 8, earlier classifications in the T w  window should be given less weight compared with later classifications. The following discount function, as illustrated by equation 9, achieves the desired purpose 
         [0000]        d   k   =C   N-k , with  d   0   =C   N   (Eq. 9)
 
         [0000]    where k=1 . . . N is the index of the SVM output in the T w  window, N represents the index of the last output in T w , i.e., at time t warn , and C is a constant discount factor (0&lt;C≦1) used to discount exponentially the weight of the output at time k. It should be noted that C=1 is equivalent to no discounting. The value of C affects the performance of the SVM-BF significantly. The description of SVM-BF parameters, as provided hereinbelow, investigates different values for C in the search for the best combination of the SVM-BF parameters. The variables m and l also need to be indexed by k, where m k  and l k  are the binary outputs of SVM at step k, and m k +l k =1. Given these changes, equation 8 can be rewritten as 
         [0000]    
       
         
           
             
               
                 
                   
                     E 
                      
                     
                       ( 
                       
                         θ 
                         | 
                         y 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           N 
                         
                          
                         
                           
                             d 
                             k 
                           
                            
                           
                             m 
                             k 
                           
                         
                       
                       + 
                       
                         
                           d 
                           0 
                         
                          
                         a 
                       
                     
                     
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           N 
                         
                          
                         
                           
                             d 
                             k 
                           
                            
                           
                             m 
                             k 
                           
                         
                       
                       + 
                       
                         
                           d 
                           0 
                         
                          
                         a 
                       
                       + 
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           N 
                         
                          
                         
                           
                             d 
                             k 
                           
                            
                           
                             l 
                             k 
                           
                         
                       
                       + 
                       
                         
                           d 
                           0 
                         
                          
                         b 
                       
                     
                   
                 
               
               
                 
                   ( 
                   
                     Eq 
                     . 
                     
                         
                     
                      
                     10 
                   
                   ) 
                 
               
             
           
         
       
     
         [0000]    where a and b are the same hyperparameters defined in equation 5. 
         [0071]    Threshold Detector 
         [0072]    Given E(θ|y), the SVM-BF algorithm outputs the final classification based on the threshold detector specified value τ S . The driver is classified as compliant if E(θ|y)&gt;τ S ; otherwise, it is classified as violating. A large threshold value τ S  is equivalent to a more conservative algorithm (catching more violators) but at the expense of an increased number of wrong warnings (i.e., false positives). The choice of the value/parameter of τ S  is analyzed and described hereinbelow with reference to implementation of the SVM-BF algorithm. 
         [0073]    Sliding Window 
         [0074]    An extension to the present SVM-BF algorithm is the introduction of a sliding window over the features, which proves to be valuable in improving the performance of the SVM-BF on road traffic data. To elaborate, each feature includes the means and variances of the last K different measurements. This change replaces the individual measurements (range, velocity, and acceleration) with their means and variances computed over the window. This addition indirectly adds time dependency to the sequence of outputs of the SVM component without affecting computation times, thus improving the SVM-BF model. The choice of the value of K is analyzed and described hereinbelow with reference to implementation of the SVM-BF algorithm. 
         [0075]    Generative Approach 
         [0076]    Use of the generative approach for classifying drivers, in accordance with the present invention, is described further herein. This approach is based on the idea of learning generative models from a set of observations. HMMs have been used extensively to develop such models in many fields, including speech recognition, and part-of-speech tagging. The application of HMMs to isolated word detection is particularly relevant to the task of driver classification. In isolated word detection, one HMM is generated for each word in the vocabulary, and new words are tested against these models to identify the maximum likelihood model for each test word. HMMs have also been used to recognize different driver behaviors, such as turning and braking. The present system and method uses HMMs to detect patterns that characterize compliant and violating behaviors. 
         [0077]    HMM-Based Architecture 
         [0078]      FIG. 6  is a flowchart  150  illustrating steps taken by the HMM-based architecture. Suppose two sets of observations are available: one known to be from compliant drivers and the other from violators. Each set of observations can be considered an emission sequence produced by an HMM modeling vehicle behavior (block  152 ). As shown by block  154 , using an expectation-maximization (EM) algorithm (as illustrated and described hereinbelow), two models λ c  and λ v  are learned from the compliant driver and violator training data, respectively. Then, given a new sequence of observations z, the forward algorithm (as described hereinbelow) is used with λ c  and λ v  to estimate the probability that the driver is compliant (block  156 ). As in the SVM-BF algorithm, a threshold detector (as described hereinbelow) uses this result to output a final classification, labeling the driver as either violating or compliant (block  158 ). Again, this classification occurs at t warn  based on the observations from the T w  window. The schematic diagram of  FIG. 7  also summarizes this architecture. 
         [0079]    HMMs and Forward Algorithm 
         [0080]    In order to determine how well a model fits a set of observations, the classifier may use HMMs and the forward algorithm. Further information regarding HMMs and the forward algorithm is provided by the publication entitled, “A tutorial on hidden Markov models and selected applications in speech recognition,” by L. Rabiner, Proc. IEEE, vol. 77, no. 2, pp. 257-286, February 1989, which is incorporated herein by reference in its entirety. 
         [0081]    An HMM λ(T, t, e) consists of a set of n discrete states and a set of observations at each state, as exemplified by the schematic diagram of  FIG. 8 . At any given time k, the system being modeled will be in one of these states q k =s i , and the transition probability matrix T gives the probability of transitioning to any other state at the next time step q k+1 =s j . Specifically, 
         [0000]        T   i,j   =P ( q   k+1   =s   j   |q   k   =s   i   (Eq. 11)
 
         [0000]    The probability of the system starting in each state is given by the initial state distribution t, where t i =P(q 1 =s i ). Due to these probabilistic transitions, the current state is typically not known. Instead, a set of observations is assumed to be available. The probability of a state s i  emitting a certain observation z k  is given by e i (z k ). The emission distribution for each type of observation is assumed to be Gaussian with unique mean μ i  and variance σ i   2  at for every state This design decision ensures that each state corresponds to one specific mode of driving, which is characterized by a set of observations normally distributed around some typical values (specified by the means and variances). 
         [0082]    A common task with HMMs is determining how well a given model λ(T, t, e) fits a sequence of observations x=x 1 , . . . , x K . This can be quantified as the probability of observing x given λ, P(x|λ). The forward algorithm is an efficient method for computing this probability and is defined as follows. Let α i (k) be given by 
         [0000]      α i ( k )= P ( x   1   , . . . ,x   k   ,q   k   =s   i |λ)  (Eq. 12)
 
         [0000]    which is the probability of observing the partial sequence x 1 , . . . , x k  and having the current state q k  at time k equal to s i  given the model λ. Then, the forward algorithm is initialized using the initial state distribution t, i.e., 
         [0000]      α i (1)= t   i   e   i ( x   1 ), i= 1, . . . , n   (Eq. 13)
 
         [0000]    The probability of each subsequent partial sequence of observations for k=1, . . . ,K−1 is given by 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         a 
                         j 
                       
                        
                       
                         ( 
                         
                           k 
                           + 
                           1 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         [ 
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               1 
                             
                             n 
                           
                            
                           
                             
                               
                                 a 
                                 i 
                               
                                
                               
                                 ( 
                                 k 
                                 ) 
                               
                             
                              
                             
                               T 
                               ij 
                             
                           
                         
                         ] 
                       
                        
                       
                         
                           e 
                           j 
                         
                          
                         
                           ( 
                           
                             x 
                             
                               k 
                               + 
                               1 
                             
                           
                           ) 
                         
                       
                     
                   
                   , 
                   
                     
 
                   
                    
                   
                     i 
                     = 
                     1 
                   
                   , 
                   … 
                    
                   
                       
                   
                   , 
                   n 
                 
               
               
                 
                   ( 
                   
                     Eq 
                     . 
                     
                         
                     
                      
                     14 
                   
                   ) 
                 
               
             
           
         
       
     
         [0000]    Upon termination at k=K, the algorithm returns the desired probability 
         [0000]    
       
         
           
             
               
                 
                   
                     P 
                      
                     
                       ( 
                       
                         x 
                         | 
                         λ 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         1 
                       
                       n 
                     
                      
                     
                       
                         
                           a 
                           i 
                         
                          
                         
                           ( 
                           K 
                           ) 
                         
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   
                     Eq 
                     . 
                     
                         
                     
                      
                     15 
                   
                   ) 
                 
               
             
           
         
       
     
         [0083]    EM Algorithm for HMMs 
         [0084]    The abovementioned observations can also be used to learn an HMM that captures the behavior of the underlying system. A standard technique for doing so, i.e., the EM algorithm, is subsequently summarized herein. An illustration of the complete algorithm is detailed in work entitled “A gentle tutorial on the EM algorithm and its application to parameter estimation for Gaussian mixture and hidden Markov models,” by J. Bilmes, Int. Comput. Sci. Inst., Berkeley, Calif., Tech. Rep. ICSI-TR-97-021, 1997, which is incorporated by reference herein in its entirety. 
         [0085]    Given a set of N observation sequences (training data) x 1 , . . . , x N , the EM algorithm computes the maximum likelihood estimates of the HMM parameters, as shown by the following equation. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       λ 
                       * 
                     
                      
                     
                       ( 
                       
                         T 
                         , 
                         t 
                         , 
                         e 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       argmax 
                       λ 
                     
                      
                     
                       P 
                        
                       
                         ( 
                         
                           
                             x 
                             1 
                           
                           , 
                           … 
                            
                           
                               
                           
                           , 
                           
                             
                               x 
                               N 
                             
                             | 
                             
                               λ 
                                
                               
                                 ( 
                                 
                                   T 
                                   , 
                                   t 
                                   , 
                                   e 
                                 
                                 ) 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   
                     Eq 
                     . 
                     
                         
                     
                      
                     16 
                   
                   ) 
                 
               
             
           
         
       
     
         [0000]    To do so, it uses the forward algorithm, as defined earlier, as well as the backward algorithm, which is defined similar to the forward algorithm. Let 
         [0000]      β i ( k )= P ( x   k+1   , . . . ,x   K   |q   k   =s   i ,λ)  (Eq. 17)
 
         [0000]    be the probability of observing the rest of the partial sequence of observations at time k for k≦K. Then, the backward algorithm follows as 
         [0000]    
       
         
           
             
               
                 
                   
                     β 
                      
                     
                         
                     
                      
                     
                       i 
                        
                       
                         ( 
                         K 
                         ) 
                       
                     
                   
                   = 
                   1 
                 
               
               
                 
                   ( 
                   
                     Eq 
                     . 
                     
                         
                     
                      
                     18 
                   
                   ) 
                 
               
             
             
               
                 
                   
                     
                       β 
                       j 
                     
                      
                     
                       ( 
                       k 
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         j 
                         = 
                         1 
                       
                       n 
                     
                      
                     
                       
                         T 
                         ij 
                       
                        
                       
                         
                           e 
                           j 
                         
                          
                         
                           ( 
                           
                             x 
                             
                               k 
                               + 
                               1 
                             
                           
                           ) 
                         
                       
                        
                       
                         
                           β 
                           i 
                         
                          
                         
                           ( 
                           
                             k 
                             + 
                             1 
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   
                     Eq 
                     . 
                     
                         
                     
                      
                     19 
                   
                   ) 
                 
               
             
           
         
       
     
         [0000]    Using the terms α i (k) from the forward algorithm and β i (k) from the backward algorithm, the probability of being in state s i , at time k given the observations x is given by 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       γ 
                       i 
                     
                      
                     
                       ( 
                       k 
                       ) 
                     
                   
                   = 
                   
                     
                       P 
                        
                       
                         ( 
                         
                           
                             
                               q 
                               k 
                             
                             = 
                             
                               
                                 s 
                                 i 
                               
                               | 
                               x 
                             
                           
                           , 
                           λ 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         
                           
                             α 
                             i 
                           
                            
                           
                             ( 
                             k 
                             ) 
                           
                         
                          
                         
                           β 
                            
                           
                             ( 
                             k 
                             ) 
                           
                         
                       
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           n 
                         
                          
                         
                           
                             
                               α 
                               i 
                             
                              
                             
                               ( 
                               k 
                               ) 
                             
                           
                            
                           
                             
                               β 
                               i 
                             
                              
                             
                               ( 
                               k 
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   
                     Eq 
                     . 
                     
                         
                     
                      
                     20 
                   
                   ) 
                 
               
             
           
         
       
     
         [0000]    Then the probability of being in state s i , at time k and state s j  at time k+1 is given by 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             ξ 
                             ij 
                           
                            
                           
                             ( 
                             k 
                             ) 
                           
                         
                         = 
                           
                          
                         
                           P 
                            
                           
                             ( 
                             
                               
                                 
                                   q 
                                   k 
                                 
                                 = 
                                 
                                   s 
                                   i 
                                 
                               
                               , 
                               
                                 
                                   q 
                                   
                                     k 
                                     + 
                                     1 
                                   
                                 
                                 = 
                                 
                                   
                                     s 
                                     j 
                                   
                                   | 
                                   x 
                                 
                               
                               , 
                               λ 
                             
                             ) 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             
                               
                                 α 
                                 i 
                               
                                
                               
                                 ( 
                                 k 
                                 ) 
                               
                             
                              
                             
                               T 
                               ij 
                             
                              
                             
                               
                                 e 
                                 j 
                               
                                
                               
                                 ( 
                                 
                                   x 
                                   
                                     k 
                                     + 
                                     1 
                                   
                                 
                                 ) 
                               
                             
                              
                             
                               
                                 β 
                                 j 
                               
                                
                               
                                 ( 
                                 
                                   k 
                                   + 
                                   1 
                                 
                                 ) 
                               
                             
                           
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 1 
                               
                               n 
                             
                              
                             
                               
                                 ∑ 
                                 
                                   j 
                                   = 
                                   1 
                                 
                                 n 
                               
                                
                               
                                 
                                   
                                     α 
                                     i 
                                   
                                    
                                   
                                     ( 
                                     k 
                                     ) 
                                   
                                 
                                  
                                 
                                   T 
                                   ij 
                                 
                                  
                                 
                                   
                                     e 
                                     j 
                                   
                                    
                                   
                                     ( 
                                     
                                       x 
                                       
                                         k 
                                         + 
                                         1 
                                       
                                     
                                     ) 
                                   
                                 
                                  
                                 
                                   
                                     β 
                                     j 
                                   
                                    
                                   
                                     ( 
                                     
                                       k 
                                       + 
                                       1 
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   
                     Eq 
                     . 
                     
                         
                     
                      
                     21 
                   
                   ) 
                 
               
             
           
         
       
     
         [0000]    From these terms, the parameters of an updated HMM  λ  are computed with the following update equations: 
         [0000]    
       
         
           
             
               
                 
                   
                     t 
                     i 
                   
                   = 
                   
                     
                       γ 
                       i 
                     
                      
                     
                       ( 
                       1 
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   
                     Eq 
                     . 
                     
                         
                     
                      
                     22 
                   
                   ) 
                 
               
             
             
               
                 
                   
                     T 
                     ij 
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           1 
                         
                         
                           K 
                           - 
                           1 
                         
                       
                        
                       
                         
                           ξ 
                           ij 
                         
                          
                         
                           ( 
                           k 
                           ) 
                         
                       
                     
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           1 
                         
                         
                           K 
                           - 
                           1 
                         
                       
                        
                       
                         
                           γ 
                           i 
                         
                          
                         
                           ( 
                           k 
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   
                     Eq 
                     . 
                     
                         
                     
                      
                     23 
                   
                   ) 
                 
               
             
             
               
                 
                   
                     μ 
                     i 
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           1 
                         
                         K 
                       
                        
                       
                         
                           
                             γ 
                             i 
                           
                            
                           
                             ( 
                             k 
                             ) 
                           
                         
                          
                         
                           x 
                           k 
                         
                       
                     
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           1 
                         
                         K 
                       
                        
                       
                         
                           γ 
                           i 
                         
                          
                         
                           ( 
                           k 
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   
                     Eq 
                     . 
                     
                         
                     
                      
                     24 
                   
                   ) 
                 
               
             
             
               
                 
                   
                     σ 
                     i 
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           1 
                         
                         K 
                       
                        
                       
                         
                           
                             γ 
                             i 
                           
                            
                           
                             ( 
                             k 
                             ) 
                           
                         
                          
                         
                           
                             ( 
                             
                               
                                 x 
                                 k 
                               
                               - 
                               
                                 μ 
                                 i 
                               
                             
                             ) 
                           
                           2 
                         
                       
                     
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           1 
                         
                         K 
                       
                        
                       
                         
                           γ 
                           i 
                         
                          
                         
                           ( 
                           k 
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   
                     Eq 
                     . 
                     
                         
                     
                      
                     25 
                   
                   ) 
                 
               
             
           
         
       
     
         [0000]    These maximum-likelihood estimates reflect the relative frequencies of the state transitions and emissions in the training data. 
         [0086]    Repeating this procedure with λ replaced by  λ  is guaranteed to converge to a local maximum, i.e., as the number of iterations increases, P(x 1 , . . . ,x N |  λ )−P(x 1 , . . . , x N |λ)→0. The resulting λ, is the maximum likelihood model λ*(T, t, e). Since the EM algorithm is only guaranteed to converge to a local maximum, several sets of random initializations can be tested to reduce the effects of local maxima on the final model parameters. 
         [0087]    As with the choice of features in the SVM, the observations used for the HMM can have a dramatic impact on its performance. After testing several combinations of observations, the following five parameters were identified to give the best results in terms of high detection accuracy and low false positive rates: 1) range to intersection; 2) speed; 3) longitudinal acceleration; 4) TTI; and 5) RDP. In addition, the observations can be normalized to remove any bias introduced by differences in the order of magnitude of the observations. 
         [0088]    Threshold Detector 
         [0089]    Using the EM algorithm, two models, namely, λ c  and λ v , are learned from the compliant driver and violator training data, respectively. Then, given a new sequence of observations z, the forward algorithm of equation 25 is used with λ c  and λ v  to find the posterior probability of observing that sequence given each model P(z|λ c ) and P(z|λ v ). The prior over the models is assumed to be uniform P(λ c )=P(λ v )=0.5 since nothing is known beforehand about whether the driver is compliant or violating. Then, the likelihood ratio of as illustrated by the following equation 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       P 
                        
                       
                         ( 
                         
                           z 
                           , 
                           
                             λ 
                             c 
                           
                         
                         ) 
                       
                     
                     
                       P 
                        
                       
                         ( 
                         
                           z 
                           , 
                           
                             λ 
                             v 
                           
                         
                         ) 
                       
                     
                   
                   = 
                   
                     
                       
                         P 
                          
                         
                           ( 
                           
                             z 
                             | 
                             
                               λ 
                               c 
                             
                           
                           ) 
                         
                       
                       
                         P 
                          
                         
                           ( 
                           
                             z 
                             | 
                             
                               λ 
                               v 
                             
                           
                           ) 
                         
                       
                     
                     &gt; 
                     
                       e 
                       
                         - 
                         
                           T 
                           H 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   
                     Eq 
                     . 
                     
                         
                     
                      
                     26 
                   
                   ) 
                 
               
             
           
         
       
     
         [0000]    determines whether the driver is more likely to be compliant or violate the stop bar and assigns the corresponding classification. Note that this ratio is typically computed using log probabilities, which introduces the e term in the likelihood ratio of equation 26. The threshold τ H  can be selected to adjust the conservatism of the classifier and is discussed in greater detail with regard to HMM parameters, as described hereinbelow. 
         [0090]    Since states have one emission distribution per observation, each state in the HMM represents a coupling between specific ranges of values for each observation. It is this coupling and the transitions between different coupled ranges that allow the HMM-based classifier to distinguish between compliant drivers and violators. 
         [0091]    Data Collection and Filtering 
         [0092]    The following provides an example of data collecting and filtering and is provided merely for exemplary purposes. The present invention is not intended to be limited by this example of data collection and filtering. Instead, this example is provided so as to provide an example of the context in which data may be acquired. 
         [0093]    The roadside data is collected regarding many approaches of vehicles at one or more intersection. As an example, data on over 5,500,000 approaches across three intersections may be collected. For instance, data from the Peppers Ferry intersection at U.S. 460 Business and Peppers Ferry Rd in Christiansburg, Va., were used to evaluate the abovementioned algorithms, providing a total of 3,018,456 car approaches. At the Peppers Ferry intersection, a custom data acquisition system was installed to monitor real-time vehicle approaches. This system included four radar units that identified vehicles, measured vehicle speed, range, and lateral position at a rate of 20 Hz beginning approximately 150 m away from the intersection, a GPS antenna to record the current time, four video cameras to record each of the four approaches, and a phase sniffer to record the signal phase of the traffic light. These devices collected data on drivers who were unaware of the collection and testing as they moved through the intersection. 
         [0094]    The information from these units then underwent postprocessing, including smoothing and filtering to remove noise such as erroneous radar returns. In addition, the geometric intersection description—a detailed plot of the intersection accurate to within 30 cm—was used to derive new values such as acceleration, lane id, and a unique identifier for each vehicle. Information on each of the car approaches was then uploaded onto an SQL database, which was used to obtain the data as described herein. 
         [0095]    The data were further processed. Specifically, individual trajectories from the data collected were filtered. To maintain tractable offline runtimes for the learning phases of the algorithms, the first 300,000 trajectories out of the 3,018,456 car approaches were extracted. They were classified as compliant or violating based on whether they committed a traffic light violation. Violating behaviors included drivers that committed traffic violation at the intersection, defined as crossing over the stop bar after the presentation of the red light and continuing into the intersection for at least 3 m within 500 ms. Compliant behaviors included vehicles that stopped before the crossbar at the yellow or red light. Out of the extracted trajectories, 1,673 violating and 13,724 compliant trajectories were found and then used in the classification algorithms. 
       Implementation 
       [0096]    The following highlights several decisions made in implementing the different algorithms previously mentioned. It is noted that this is provided for exemplary purposes. First is described training and testing procedures used for data validation and the rationale that motivates them. Also described is an analysis tool used to compare algorithm performance against parameter choice. Second is described parameters that are common to all the algorithms. More specifically, the values of the variables affecting the warning timing and the maximum driver annoyance levels are described. Third is described the choice of parameters that are specific to the SVM-BF and HMM algorithms, respectively. 
         [0097]    Training/Testing Approaches 
         [0098]    Using trajectories selected from a database storing collected vehicle data, the algorithms are tested in pseudo real time, i.e., by running them on the trajectories of the database as if the observations of the target vehicle were arriving in real time. The observations from each trajectory were downsampled from 20 to 10 Hz to reduce the computational load. The training and testing were performed using two different approaches: 1) basic generalization test as mentioned hereinbelow, and 2) m-fold cross validation, also as mentioned hereinbelow. Both approaches aim at evaluating the generalization property of the algorithms. 
         [0099]    To evaluate the results of these tests, the receiver operation characteristic (ROC) curve is used to display the true positive and false positive rates of each set of algorithm parameters. The curve is generated by varying a parameter of interest (or set of parameters), which is referred to as the beta parameter in the SDT terminology. Each point on the ROC curve then corresponds to a different value of the beta parameter. The choice of beta for each algorithm is subsequently detailed in its respective section. 
         [0100]    1) Basic Generalization Test: 
         [0101]    The first approach is a straightforward test of generalization. This consists of training the algorithms on a randomly selected subset that is some small fraction p of the data and testing on the remaining 1−p. This approach demonstrates the generalization property (or lack thereof) of the algorithms. This property is essential for any warning algorithm to perform successfully when deployed on driver assistance systems, particularly given the number of vehicles encountered in everyday driving. The value of p is chosen to be 0.2. The total number of trajectories used for this approach is 10000 compliant and 1000 violating. In other words, 2000 compliant and 200 violating trajectories are used in the training phase, whereas the testing phase consists of 8000 compliant and 800 violating trajectories. 
         [0102]    2) m-Fold Cross Validation: 
         [0103]    The second approach uses the standard m-fold cross-validation technique for testing generalization. This involves randomly dividing the training set into m disjoints and equally sized parts. The classification algorithm is trained m times while leaving out, each time, a different set for validation. The mean over the m trials estimates the performance of the algorithm in terms of its ability to classify any given new trajectory. The advantage of m-fold cross validation is that, by cycling through the m parts, all the available training data can be used while retaining the ability to test on a disjoint set of test data. A total of 5000 compliant and 1000 violating trajectories are used in the m-fold approach with m=4. First, each algorithm is run once on these data with the same ratio of training and testing data, producing a classifier with fixed parameters. This classifier is then tested using the m-fold cross-validation approach. 
         [0104]    Shared Parameters 
         [0105]    1) Minimum Time Threshold TTI min : For each trajectory, as shown in  FIG. 3 , the final output of the algorithms is given at time t warn , which is computed as shown by equation 26 
         [0000]        t   warn =min (TTI min   ,t ( d   min )).  (Eq. 26)
 
         [0000]    In other words, t warn  corresponds to the time when the estimated remaining time for the target vehicle to arrive to the intersection is TTI min  seconds, or when the distance to the intersection is equal to d min  meters, whichever happens first. 
         [0106]    The choice of TTI min  is important. It represents the amount of time the host vehicle is given to react after being warned that a violating target vehicle is approaching its intersection. Choosing one single mean value for TTI min  provides little information about the performance of the warning algorithms for response times away from the mean. Instead, the choice of TTI min  is based on the cumulative human response time distribution presented in the article entitled “A method for evaluating collision avoidance systems using naturalistic driving data,” by S. McLaughlin, J. Hankey, and T. Dingus, Accident Anal. Prev., vol. 40, no. 1, pp. 8-16, January 2008, which is incorporated by reference herein in its entirety. This distribution answers the following question: given a specific driver response time, what is the percentage of population that is able to react to a potential collision? The larger TTI min , the bigger the percentage of population to react on time to the warning. But a larger TTI min  is expected to lead to a worse performance of the warning algorithms because the final classification would be given earlier and after fewer measurements. To address this problem, the different algorithms were developed and evaluated for three different values of TTI min  summarized in Table II, as provided hereinbelow. They are 1.0, 1.6, and 2.0 s, corresponding to 45%, 80%, and 90% of the population, respectively. 
         [0000]    
       
         
               
             
               
               
               
             
           
               
                 TABLE II 
               
             
             
               
                   
               
               
                 CUMMULATIVE POPULATION PERCENTILE VERSUS 
               
               
                 DRIVER RESPONSE TIME 
               
             
          
           
               
                   
                 RESPONSE 
                 POPULATION 
               
               
                   
                 TIME(S) 
                 PERCENTILE 
               
               
                   
                   
               
               
                   
                 1.0 
                 45% 
               
               
                   
                 1.6 
                 80% 
               
               
                   
                 2.0 
                 90% 
               
               
                   
                   
               
             
          
         
       
     
         [0107]    Therefore. the engineer deciding which algorithm to implement has a clearer understanding of the tradeoffs for each choice. Note that the host vehicle is assumed to be at rest or moving with a negligible speed in this analysis. This is typically the case at t warn , the time where it is warned of the target vehicle possible violation. 
         [0108]    2) Minimum Distance Threshold d min : The d min  distance plays the role of a safety net. In most intersection approaches, the TTI min  condition happens first. But for some cases where the target vehicle approaches the intersection with a low speed, the TTI min  condition is met too close to the intersection. The d min  condition ensures that such cases are captured, and warning (if needed) is given with enough time for the driver to react. For TTI min  of 1.6 s, d min  is chosen to be 10 m. This is equivalent to situations where vehicles cross the d min  mark with speeds lower than 6.25 m/s or 22.5 km/h, consistent with the low-speed assumption. For TTI min  of 1.0 and 2.0 s, d min  is scaled to 6.25 and 12.5 m, respectively. These values are summarized in Table III, s provided hereinbelow. Note that in the case of a warning, the driver will have a period of time larger than TTI min  to react, ensuring that the percentage of drivers responding on time to the warning is consistent with Table II numbers. 
         [0000]    
       
         
               
             
               
               
               
             
               
               
               
             
           
               
                 TABLE III 
               
             
             
               
                   
               
               
                 MINIMUM TTI MIN  AND MINIMUM DISTANCE d MIN  PAIRS 
               
             
          
           
               
                   
                 TTI min  (s) 
                 d min (m) 
               
               
                   
                   
               
             
          
           
               
                   
                 1.0 
                 6.25 
               
               
                   
                 1.6 
                 10.0 
               
               
                   
                 2.0 
                 12.5 
               
               
                   
                   
               
             
          
         
       
     
         [0109]    3) Maximum FP Rate: Warning algorithms must take into consideration driver tolerance levels. i.e., they should try to ensure that the rate of false alarms is below a certain “annoyance” level that is acceptable to most drivers. For exemplary purposes, the maximum false positive rate is chosen to be 5%, in accordance with automotive industry recommendations. Therefore, the developed algorithms are designed and tuned under the constraint of keeping false positive rates below 5%, while trying to maximize true positive rates. 
         [0110]    SVM-BF Parameters 
         [0111]    There are four key parameters for the SVM-BF classifier: 1) the T, window size; 2) the discount factor C; 3) the decision threshold τ S ; and 4) the sliding window size K. The threshold variable is selected as the beta parameter as it was introduced specifically to tune the performance of the algorithm. Models with T w  varying from 5 to 15 observations were considered, whereas C varied from 0.5 to 1.0 and K ranged from three to ten measurements. All combinations of these parameters were tested, and the schematic diagram of  FIG. 9  shows the ten combinations that produced the highest rates of true positives while maintaining a false positive rate below 5% for one basic generalization test. The results of this test were obtained using the best combination of parameters in  FIG. 9 : T w =15, K=7,C=0.9, and τ S =0.9. The hyperparameters a and b in equation 5 are set both to 0.5, specifying no bias toward either behavior. These values could be changed to reflect a bias toward one driving behavior if the classifier is given prior knowledge of the target driving history. 
         [0112]    HMM Parameters 
         [0113]    There are three key parameters for the HMM-based classifier: 1) the number of states in the HMM; 2) the T w  window size; and 3) the decision threshold T H . As in the previous methods, the threshold is selected as the beta parameter. The number of states determines how many different modes the HMMs can capture, and as a result, the range of behaviors that can be classified accurately. However, increasing the number of states also increases the complexity of the model and the risk of overfitting the training data. Models with between 6 and 15 states were considered, whereas T w  was varied from 10 to 20 observations. All combinations of these parameters were tested, and the schematic diagram of  FIG. 10  shows the ten combinations that produced the highest rates of true positives while maintaining a false positive rate below 5% for one basic generalization test. The results for this test were obtained using the best combination of parameters in  FIG. 10 : T w =15, eight states, and τ H =54.4. Recall that τ H  defines a threshold on the likelihood ratio and is distinct from τ S , which is a threshold on the probability of being classified as compliant. Monte Carlo testing was used to learn multiple models for each set of parameters to reduce the effects of local minima on the algorithm. 
         [0114]    In accordance with an alternative embodiment of the invention, the present system and method is capable of maintaining classification of a driver even when the driver changes vehicles. Specifically, as previously mentioned, the storage device may store data history specific to the driver of a vehicle. This enables a driver to switch vehicles and bring his/her own data history into the new vehicle. As a result, the present system and method is capable of providing driver specific results in situations when drivers switch vehicles. 
         [0115]    It should be emphasized that the above-described embodiments of the present invention are merely possible examples of implementations, merely set forth for a clear understanding of the principles of the invention. Many variations and modifications may be made to the above-described embodiments of the invention without departing substantially from the spirit and principles of the invention. All such modifications and variations are intended to be included herein within the scope of this disclosure and the present invention and protected by the following claims.