Joonas Lõmps

Amnir Hadachi
email: hadachi@ut.ee

The Impact of Morphological Processing and Feature Selection on Handwriting Recognition Accuracy

Keywords: Morphological Processing, Support Vector Machine, K-Nearest Neighbor, Hiragana Handwriting Recognition, Features Selection

Handwriting or character recognition is one of the most challenging topics and the oldest application of pattern recognition. Till now, all the research progress and innovation has been made either regarding enhancing the preprocessing steps or via advancing the language modelling process. In this paper, we are presenting a combined method for Hiragana handwriting recognition through the exploration of morphological processing and features extraction. Our approach is tested in offline mode and uses two different classifiers for evaluation, the Support Vector Machine (SVM) and the K-Nearest Neighbour (KNN). The outcome of this investigation gave knowledge about the best combination and structure of the adequate method for performing a recognition accuracy of 90.3 percent on offline test data not used in the training.

Introduction

Handwriting recognition or optical character recognition is the art of identifying written characters with the help of a machine. In general, there are two ways of performing recognition: either in online mode or offline mode. The online mode refers to real-time character recognition of a time series of coordinates that represent the movements captured from a pen tip. However, the offline recognition concerns the identification based on already taken images of the text. Moreover, the online recognition yields good results due to the amount of data and relevant features that can be extracted, which is not the case in offline recognition [START_REF] Plamondone | On-Line and Off-Line Handwriting Recognition: A Comprehensive Survey[END_REF]. The importance of handwriting recognition systems can be illustrated by the increasing need for them in many emerging fields of application, such as electronic libraries, personalized medicine, multimedia and all types of systems that require or use hand written inputs. Besides, automating the digitalization of handwritten characters offers lot of advantages when it comes to processing large amounts of papers, documents, and transforming or transferring data into computers.

Handwriting recognition approaches usually include the following steps: preprocessing, representation, segmentation or stroke, feature extraction and recognition. However, this is not a rule, some techniques do not include all these mentioned steps. In addition, all of them have the objective of cleaning, filtering and transforming the input before applying the recognition via the use of a classifier, such as K-Nearest Neighbour [START_REF] Baiju | Online recognition of Malayalam handwritten scripts -A comparison using KNN, MLP and SVM[END_REF], Support Vector Machine [START_REF] Singh | An application of SVM in character recognition with chain code[END_REF], Hidden Markov Model [START_REF] Choudhury | Combining HMM and SVM based stroke classifiers for online Assamese handwritten character recognition[END_REF], Euclidean Distance [START_REF] Patel | Multiresolution technique to handwritten English character recognition using learning rule and Euclidean distance metric[END_REF], etc. Our research is conducted on Hiragana handwriting in offline mode. Most people believe that the Japanese language, especially the Hiragana, is based a complex writing system due to its morphology and photonic script [START_REF] Das | A Pattern Recognition Approach for Handwritten Hiragana Character Identification[END_REF]. Hence, the work presented in this paper focuses on investigating the impact of the morphological processing and feature selection on the accuracy recognition of our proposed method for recognizing the Hiragana characters.

Related Work

When it comes to handwriting recognition, a great deal of research has already been carried out. Since awhile now, most of the focus in research is on Japanese character recognition has been on applying statistical and probabilistic approach for classification like Neural Networks [START_REF] Shimozawa | Neural Networks which consist of Simple Recurrent Networks for Character Recognition by Template Matching[END_REF], genetic algorithms [START_REF] Shimozawa | The post processing of Character Recognition by Genetic Algorithms[END_REF] or shape characteristics [START_REF] Mohammad | Character Recognition Using Mathematical Morphology[END_REF] have been used. For example, in [START_REF] Zhu | A robust model for on-line handwritten japanese text recognition[END_REF], the authors proposed a technique tested on Chinese characters and based on feature extractions and the Bayes classifier. The results yielded a recognition accuracy of 92,8%. Besides, there is also the case of using Hidden Markov Chain, as presented in [START_REF] Tokuno | Context-dependent substroke model for HMM-based on-line handwriting recognition[END_REF], which gave interesting results with 92% accuracy for Kanji. Regarding Hiragana characters, the best results were 95.1% accuracy using a simple three-layer neural network [START_REF] Agui | Recognition of handwritten katakana in a frame using moment invariants based on neural network[END_REF] and 94% accuracy obtained using SVM [START_REF] Tsuchiya | Training three-layer neural network classifiers by solving inequalities[END_REF]. Another application of Neural Network is illustrated in [START_REF] Barnes | ID, USA "STRICR-FB, a Novel Size-Translation-Rotation-Invariant Character Recognition Method[END_REF], where the authors proposed an algorithm which utilises Size-Translation-Rotation-Invariant vectors. During the process of constructing the vectors a neural network approach was used and it was created by design, not by training. The testing of the algorithm showed an accuracy rate of 96.2%. As we know, one of the challenges with handwriting is the absorption variation of the same character among different handwriting styles. Besides, there are graphical similarities of different characters in Japanese script. To overcome these issues, the authors in [START_REF] Takahashi | Recognition enhancement by linear tournament verification[END_REF] proposed a technique based on template matching and enhanced this by using a couple of strategies focusing on cutting off a number of recognition classes and introducing a fine detail classification for the recognition. Another approach was presented in [START_REF] Maruyama | Handprinted Hiragana recognition using support vector machines[END_REF], based on virtual example synthesis. The latter was done by synthesizing virtual examples from a number of real samples. The results obtained demonstrated that by choosing the appropriate eigenvectors and base samples they had good performances compared to pattern segmentation techniques and SVM.

In general, all mentioned approaches were not tested on datasets with high variability regarding the handwriting style. In addition, the situation in the literature regarding the recently attempted techniques is that researchers are focusing either on soft computing approaches for classification or shape/morphology characteristics for classification.

Methodology

Adopted Method

The method adopted in this article can be resumed as follows: preprocessing, morphology processing, feature extraction and classification (Fig. 1). During the preprocessing step, the image is processed using gray scale and binarization techniques. Next phase is morphological processing, where we investigate the effect of erosion and dilate methods. Then, it is the feature extraction. The features chosen for this work are the HOG feature, Horizontal and vertical projections, zoning and raw data. Finally, the classifiers tested in this architecture are SVM and KNN.

Preprocessing

Before the character image is ready for morphological processing, it has to go through preprocessing for more consistent and accurate results. Our approach to preprocessing consists of three parts. For the data to be comparable, it has to have same dimensions: we chose them to be 50x50 pixels. Normalization takes an input image of a character, crops the image as much as possible to only leave the character, and resizes it to 50x50. Normalized image of a character is then turned into a grayscale image, meaning it only carries its intensity information and is represented exclusively by different shades of gray, varying from black at the weakest to white at the strongest level of intensity. This is followed by binarization of the grayscale image using the Otsu's method, as our test images were all on white paper [START_REF] Otsu | A Threshold Selection Method from Gray-Level Histograms[END_REF]. That leaves us with a digital image of a character where every background pixel is either a 0 for black or 255 for white for foreground pixels.

Morphology process

Mathematical morphology provides a set of different operators for processing digital images based on their shape. The operators are especially useful for the analysis of binary images. When correctly used, the mathematical morphology operators can be used for edge detection, noise removal, image enhancement, image segmentation etc, all while preserving their shape and eliminating irrelevancies. Mathematical morphology uses sets to represent shapes and the operators use methods defined in the set theory to transform the input image [START_REF] Haralick | Image analysis using mathematical morphology[END_REF]. Our work focuses on the two most basic operations in mathematical morphology: erosion and dilation. Both operations take two inputs. One is the input image, that is to be modified, and the other is the structuring element. The structuring element determines the details regarding how the operator modifies the input image.

Erosion

Erosion is a morphological transformation that combines two sets using the vector subtraction of set elements (Fig. 2). If A and B are sets in the Euclidean space E and A is a binary image, then the erosion of the binary image A by the structuring element B is defined as:

A B = {x ∈ E | x + b ∈ A, ∀b ∈ B} (1)

Example of an erosion operation:

A = {(0, 0), (0, 1), (1, 0), (1, 1), (1, 2), (1, 3), (2, 1), (2, 2),

(2, 3), (2, 4), (3, 2), (3, 3), (4, 5)} B = {(0, -1), (-1, 0), (0, 0), (0, 1), (1, 0)}

A B = {(1, 1), (2, 2), (3, 2)}
This is the definition used for erosion operation by [START_REF] Haralick | Image analysis using mathematical morphology[END_REF]. For simplicity, the structuring element B can be slid across the binary image A and where B is contained inA, its origin point (0, 0) is present in A B.

Dilation

Dilation is a pseudo-inverse of the erosion. Instead of combining two sets using vector subtraction of set elements, it uses their addition (Fig. 3). If A and B are

A ⊕ B = {c ∈ E | c = a + b, ∃a ∈ A, ∃b ∈ B} (2)
Example of dilate operation: This is the definition used for the dilation operation by [START_REF] Haralick | Image analysis using mathematical morphology[END_REF]. For simplicity, the structuring element B may be slid across the binary image A. Wherever the origin point of B matches a point on A, the structuring element B can be stamped onto image A, creating A ⊕ B.

A = {(1, 1

Feature Extraction

Image representation plays a crucial role in a recognition system. Simple binary image can be fed to a recognizer, but it might not achieve the desired results.

A more compact and characteristic representation of an image is required for most of the recognition systems to avoid unnecessary complexity and to increase the recognition accuracy rates [START_REF] Arica | An overview of character recognition focused on off-line handwriting[END_REF]. Extracting a set of features for each class helps to distinguish it from other classes while remaining invariant to characteristic differences within the class [START_REF] Oh | Analysis of class separation and combination of class-dependent features for handwriting recognition[END_REF]. In the following sections, we describe the extracted features used in our approach.

Raw data

The simplest feature is the output of preprocessing without any feature extraction. With our approach, it either gives us an eroded or dilated binary image of a character. Due to using 50x50 images of character it gives us a vector of 2500 data points per character.

Projection Histogram

Using a Projection Histogram (PH) is a way to represent a two-dimensional (2-D) image signal into 1-D signal. In short, it counts the number of foreground pixels in each column and row in an image and turns the values into a vector with a size of n + m where n and m represent the dimensions of the image [START_REF] Wang | Multi-layer projections for the classification of similar Chinese characters[END_REF].

Example of it can be seen on figure 4.

Zoning

Zoning is a feature that divides the input image into a number of predefined sizes and add up the intensities of foreground pixels in the given zone [START_REF] Sastry | Telugu Handwritten Character Recognition using Zoning Features[END_REF]. We tested two different variations of a number of zones and their sizes: 25 zones of 10x10 and 100 zones of 5x5.

To find the zoning feature vector of an image, all pixel intensities in a given zone need to be summed. The values are then transformed into a vector with a size of l, where l is the number of zones. If f (i, j) is a digital image and I(i, j) is the pixel intensity of that image, then the pixel intensities I(i, j) of an image in a zone k are calculated by

V k = n i=1 m j=1 I k (i, j) (3)
where 1 ≤ k ≤ l, where l is the number of zones and n and m are the dimensions of the zone.

Equation (3) describes the summation of intensity values of k th zone in the image. The final vector is a list of intensities of every zone.

V = [V k ], 1 ≤ k ≤ l (4)
In our approach, it simplifies the counting of the foreground pixels due to the use of binary images as input for extracting the features with results that can be seen in figure 5.

Histogram of Oriented Gradients

Objects' appearance and shape can be characterized by the distribution of local intensity gradients or edge directions. It begins by dividing the image into smaller regions called cells, and then for every cell a local 1-D histogram of gradient direction over the pixels of the cell is compiled. Concatenation of these histograms makes up the descriptor. For improved accuracy, the cell values can be normalized by combining cells into a larger region of the image, called a block, and using its intensity for normalization [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF].

Classification

Classification is the problem of identifying the category to which a new observation belongs based on a training set of observations whose category is already known. Classifier is an algorithm that implements classification and usually consists of training and testing. Training a classifier introduces examples of observations that belong into a certain category, while testing uses the algorithm to predict to which category the given observation belongs to.

For our investigation, k-nearest neighbour and support vector machine classifiers are used, as they are two of the most well known and commonly used classifiers.

K-Nearest Neighbour

The k-nearest neighbours rule [START_REF] Cover | Nearest neighbor pattern classification[END_REF] is one of the simplest and most well known methods for classification. It classifies examples based on the majority of the k-nearest neighbours found in a training set. Given a set of n pairs (x 1 , θ 2 ), ..., (x n , θ n ), where x i takes values in as metric space X defined a metric d and θ takes values in the set of possible class indexes {1, 2, ..., M }.

For any new pair (x, θ), only the value of x is known, and it is necessary for to estimating its θ by using the information provided in the set of trained classified points. Then x , n ∈ {x 1 , x 2 , ..., x n } is the nearest neighbour to x if

min d(x i , x) = d(x , n , x) i = 1, 2, ..., n (5)
The nearest neighbour rule decides that x belongs to the category θ , n of its nearest neighbour x , n . In our approach k = 3.

Support Vector Machine

Support vector machine is a discriminative classifier defined by a separating hyperplane. Given labelled training data, the algorithm outputs an optimal hyperplane which categorizes new examples. The optimal separating hyperplane maximizes the margin (M ) of the training data. Let | β 0 + β T x |= 1 represent a hyperplane, where x denotes the training example closest to the hyperplane(also called support vector). Then the distance between a point x and a hyperplane (β,

β 0 ) is distance = | β 0 + β T x | β (6)
As the numerator is equal to one and the distance to the support vector is

distance support vectors = | β 0 + β T x | β = 1 β (7)
The margin is then equal to twice the distance of the closest example M = 2 ||β|| . Maximizing M is equivalent to the problem of minimizing a function L(β) subject to some constraints. The constraints model the requirement for the hyperplane to classify all the training example x i . Formally min β,β0

L(β) = 1 2 β 2 subject to y i (β T x i + β 0 ) ≥ 1 ∀i, (8)
where y i represents each of the labels of the training examples. This problem can be solved using Lagrange multipliers to obtain the weight vector β and the bias β 0 of the optimal hyperplane.

Experimental Results and Discussion

The handwritten Hiragana characters used for testing were collected by the authors with the help of University's Department of Languages of Asian Region. This database consists of 12251 characters, approximately 173 images of every 71 different Hiragana characters, and includes 28 different handwriting styles from Japanese language students with varying experience with the language. As consequence, our dataset has a significant variability about an average of 49%. Some of the characters have a considerable variability due to the different handwriting styles. For example, figure 6 gives an idea about the variability of each character in our dataset. Based on our experiments, the mathematical mor- We noticed that the changes in accuracy depend much more on the classifier than the features. Support vector machines seem to be less affected by the mor-phological operators than k-nearest neighbours, as it can be seen in tables 1 and 2. In all of our tested combinations of features and classifiers, while using morphological erosion before extracting the feature, resulted in a drop in the recognition accuracy rate. The most affected combination was KNN along with raw data going from 78.84% to 56.95%, resulting in a 21.89% drop in recognition accuracy.

On the other hand, using dilation resulted in an increase of recognition accuracy rate. There were two combinations where dilation reduced the accuracy; SVM with PH and SVM with HOG. The combination of classifiers and the feature that benefited the most from using morphological dilation was KNN with raw data at 11.24%. All that we discussed above can be clearly seen in our recognition rate matrix (Figure 7). The matrix gives an idea about recognition rates per technique and character. The latter allows us also to notice that applying morphology increases in most cases, the recognition rate while using any method or combination of methods. In addition, it is still hard to raise the recognition rate of characters that have a lot of shape similarities, due to their resemblance with other characters. For example, in figure 8 the characters are very similar. By adding the handwriting style variation, it becomes hard to differentiate between the characters using the algorithms.

Conclusion

Throughout our experiment, we collected different handwriting styles from the field, which makes our dataset with significant variability. After investigating different feature selections and applying morphological processing, we conclude that both steps have an important impact on the handwriting recognition accuracy. Since in most cases, we noticed an increase in recognition rate after applying the morphology processing and feature selection by almost 11% when using KNN and by almost 2% when using SVM. Moreover, during this investigation we proposed a technique that gives a good recognition accuracy rate under constraints of significant variability of the dataset. The work presented is an encouraging evaluation for future investigations in increasing the handwriting recognition rate. In addition, introducing new ap-proaches and methods in the chain process of handwriting recognition can be very beneficial for offline mode and real-time application.

Fig. 1 .

 1 Fig. 1. The Adopted Method

Fig. 2 .

 2 Fig. 2. Illustration of the erosion process

Fig. 3 .

 3 Fig. 3. Illustration of the dilation process

Fig. 4 .

 4 Fig. 4. Example of a Projection Histogram

Fig. 5 .

 5 Fig. 5. An example result of zoning. a) base image, b) zoning k = 25, c) zoning k = 100

Fig. 6 .

 6 Fig. 6. Handwriting dataset variability

Fig. 7 .

 7 Fig. 7. Recognition rate per character and technique

Fig. 8 .

 8 Fig. 8. Example of almost identical characters

Table 1 .

 1 Accuracy rates of SVM classifier with different features and morphological operators

		SVM -erosion SVM SVM -dilation
	PH	67.38%	70.56%	69.16%
	Zone25	77.40%	81.33%	83.33%
	Zone100	86.04%	87.26%	89.13%
	Raw	85.22%	88.92%	90.36%
	HOG	79.48%	84.04%	83.04%
	HP+Zone25	83.84%	85.65%	86.62%
		KNN -erosion KNN KNN -dilation
	PH	63.94%	72.73%	78.29%
	Zone25	84.06%	87.67%	88.46%
	Zone100	82.81%	87.10%	90.22%
	Raw	56.95%	78.84%	90.08%
	HOG	64.99%	74.20%	81.77%
	HP+Zone25	84.31%	88.25%	89.98%

Table 2 .

 2 Accuracy rates of KNN classifier with different features and morphological operators

Acknowledgment

The authors would like to thank the Chair of Distributed Systems of the Institute of Computer Science at the University of Tartu and also a special thanks to Ms Eri Miyano and her students from the Department of Languages of Asian Region at the University of Tartu for helping in the data collection campaign of the Hiragana dataset used in this research work.


† Martin

Then, we plan to use these chaotic dynamic for optimization problem. With a bifurcation diagram we can also distinguish the periodic solutions apart from the chaotic solutions. By studying the chaotic solutions, we can then achieve a first return map which is a signature of the dynamical system and thoroughly study the complexity of the latter with a certain set of parameters. As a result, the partition in the bifurcation diagram is provided. From the first return maps, we are able to confirm the complexity of the dynamics in those partitions along with the transitions between them.

Keywords. Bifurcation Diagram, Chaotic Dynamics, First Return

Map, Rössler System, Uniform Random Function 1 Related works

Rössler system was first introduced as a system for studying chemical reactions [START_REF] Rössler | An equation for continuous chaos[END_REF]. The system is defined by three differential equations:

   ẋ = -y -z ẏ = x + ay ż = b + z(x -c) . (1)
The solutions that are retrieved from the system can be an attractor (chaotic solution) or a periodic solution. The first derivative ẋ, ẏ and ż is the definition of the problem where the x, y and z are the variables of the system; all variables at t = 0 are called initial conditions. A series of variables x, y and z from t = 0 → ∞ is the solution of the system. Lastly, a, b and c are parameters to alter the behavior of the system. Regarding the parameters, Sprott and Li [START_REF] Sprott | Asymmetric bistability in the Rössler system[END_REF] proposed a method to generalize these parameters (a, b and c) modification with α as seen in:

   a = 0.2 + 0.09α b = 0.2 -0.06α c = 5.7 -1.18α . (2)
From this parametrization, it has been shown that the system can only generate attractors with the same dynamics, i.e., with no more than three branches Fig. 1 (readers are encouraged to consult [START_REF] Rosalie | Templates and subtemplates of Rössler attractors from a bifurcation diagram[END_REF] for further details).

Figure 1: The bifurcation diagram where α is varied in Eq. ( 2) for the Rössler system Eq. ( 1).

The purpose of our work is to obtain more complex chaotic dynamics from this bifurcation diagram by using the banded chaos parts. We expect to improve algorithm performances by introducing these type of chaotic behavior.

Bifurcation Diagram Partition

A bifurcation diagram can be used as a tool to illustrate the behavior of each state in a chaotic dynamical system when a parameter is varied. This bifurcation diagram can only be obtained after the system discretization. We used the Poincaré section to complete this task.

The bifurcation diagram of the Rössler system with α = [-0.5, 1.2] is presented in Fig. 2. It can be clearly observed that there are three kinds of areas in the diagram. The first kind is a very sparse area, e.g. in the period of α = [0.3, 0.4]. These values of α give periodic solutions. The second kind is a dense area, e.g. the period of α = [-0.1, 0.2]. These α yield chaotic solutions. The third kind is a dense area with a gap, e.g. the period of α = [1.1, 1.15]. The attractor yielded from these α is called "Banded Chaos". The characteristic of the banded chaos is more complex than previously mentioned chaotic attractors. Readers who would like to pursue further details should refer to [START_REF] Rosalie | Templates and subtemplates of Rössler attractors from a bifurcation diagram[END_REF].

  Proceedings of WANCSA 2017 Normandie University, Le Havre, France -July 4-5, 2017 EXPLORING CHAOTIC DYNAMICS BY PARTITION OF BIFURCATION DIAGRAM Boonyarit Changaival * , Martin Rosalie † Abstract. Chaotic dynamical systems have been recently successfully used to replace uniform probability functions in several algorithms in optimization and machine learning. In this work, we propose a study on the use of bifurcation diagrams and first return map in the Rössler system for producing chaotic dynamics.

We compute our first return maps with this equation:

where LB stands for "Lower Bound" and U B is for "Upper Bound". These upper bound and lower bound are based on the bifurcation diagram. As shown in Fig. 2, the bifurcation diagram does not have a linear shape. Therefore, the diagram has been divided into several parts to ensure that we extract the values of ρ n in [0, 1] and retrieve non-equivalent dynamics from the bifurcation diagram. This is because the Rössler dynamics can be considered similar as a whole using templates and subtemplates according to [START_REF] Rosalie | Templates and subtemplates of Rössler attractors from a bifurcation diagram[END_REF]. LB and U B in Eq. ( 3) can be found in Eq. ( 4) and Eq. ( 5) respectively. In this work, we provide the partitions of α = [-0.5, 1.2] since the period of α < -0.5 are mostly periodic and not entirely our focus. A first return map is a dynamical signature of a system under an influence of a set of parameters. In the case of our work, the parameter is α. The map is drawn from a plot of ρ n against ρ n+1 obtained from the partitions. The first return map does not only help in discerning whether the state of system is periodic or chaotic, but also aids in studying the complexity of the system behavior through the concept of branch in the first return map as described in [START_REF] Rosalie | Templates and subtemplates of Rössler attractors from a bifurcation diagram[END_REF]. The difference can be seen in Fig. 3 and Fig. 4, where our partition is not applied in the former, but the latter for the same value of α. Thus, a first return map with four branches (more complex) is obtained.

Conclusion

In this paper, we provide a novel partition method that can extract high complexity behaviors from a banded chaotic attractor through a bifurcation diagram in the Rössler system. As future work, we aim to deploy the Rössler system in optimization algorithms such those that appeared in [START_REF] Gandomi | Firefly algorithm with chaos[END_REF][START_REF] Liu | Hybrid algorithm for ant colony optimization based on chaos technique[END_REF] and graph traversal algorithm.


Aurélien Duret
email: aurelien.duret@entpe.fr

Soyoung Ahn

Christine Buisson
email: buisson@entpe.fr

Spatio-Temporal Analysis of Impacts of Lane Changing Consistent with Wave Propagation

come   L'archive ouverte pluridisciplinaire

INTRODUCTION

Traffic congestion is a serious externality of modern society and has negative societal and environmental impacts. Notable features of congestion are capacity reductions of freeway bottlenecks and oscillations (i.e. stop-and-go traffic), which are directly related to the amount of delay, engine emission and fuel consumption. Thus, control strategies that address the causal factor(s) of these phenomena are critical in alleviating congestion-related problems. In recent studies, lane-changing (LC) has been identified as a primary causal factor for these traffic instabilities [START_REF] Cassidy | Increasing the capacity of an isolated merge by metering its on-ramp[END_REF][START_REF] Mauch | Freeway traffic oscillations: observations and predictions[END_REF][START_REF] Ahn | Freeway traffic oscillations and vehicle lane-change maneuvers[END_REF]. However, existing literature does not provide a comprehensive understanding of LC related processes, particularly in regard to its impact on traffic streams (e.g. flow, density, etc.).

In response to the evident need for empirical research on LC, the present study deals with quantifying the effect of LC in traffic streams. Notably, the impacts of both entering and exiting maneuvers are quantified and evaluated for their net effect on the traffic upstream. Our method to quantify the LC effect exploits the principle of Newell's car-following model (4) that predicts the positions of each vehicle over time (in the absence of LC maneuvers) with few parameters directly observable in the field. The impacts of LC maneuvers are then measured as discrepancies between actual observations and Newell's predictions. The results show that the net number of insertions is the most significant factor; i.e., the impact increases with respect to increases in net number of insertions. The results also show that insertions have more significant impact than exiting maneuvers.

The remainder of the manuscript is organized as follows. Section 2 summarizes existing literature related to LC models and efforts to evaluate the effects of LC. In section 3, the study sites and their trajectory data are described. Section 4 describes the methodology developed in this study to properly measure the impact of LC maneuvers. Empirical findings based on the new methodology are presented in section 5, and some concluding remarks are provided in the last section.

BACKGROUND

Recent experimental studies have shown that LC is a causal factor for several important traffic phenomena. Cassidy and Rudjanakanoknad [START_REF] Cassidy | Increasing the capacity of an isolated merge by metering its on-ramp[END_REF] conducted an empirical study to observe the causes of a reduction in discharge rate when a recurrent merge bottleneck activates on a freeway. They observed that when the inflow from an on-ramp was sufficiently large, the accumulation in the freeway shoulder (rightmost) lane immediately upstream of the merge increased. When the accumulation reached a "critical" level, vehicles in the shoulder lane maneuvered toward faster, left lanes in attempts to increase their travel speeds, causing traffic breakdown in left lanes and decreasing the overall discharge rate through the bottleneck. The capacity drop was observed to be around 10 percent, which is consistent with findings from other bottleneck studies [START_REF] Cassidy | Increasing the capacity of an isolated merge by metering its on-ramp[END_REF][START_REF] Cassidy | Some traffic features at freeway bottlenecks[END_REF][START_REF] Banks | Freeway speed-flow-concentration relationships: more evidence and interpretations[END_REF][START_REF] Bertini | Empirical study of traffic features at a freeway lane drop[END_REF][START_REF] Elefteriadou | Probabilistic Nature of Breakdown at Freeway Merge Junctions[END_REF].

In Ahn and Cassidy (3), it was shown that LC maneuvers are a primary cause for freeway oscillations (e.g. stop-and-go traffic). They systematically detected about twenty instances of oscillations' formations and growths using trip times of individual vehicles. Vehicle trajectories around those detected instances revealed that LC maneuvers were directly linked to the instances of formations and growths. These studies, however, illustrate the causal relationship in a qualitative manner [START_REF] Ahn | Freeway traffic oscillations and vehicle lane-change maneuvers[END_REF] or at a macroscopic scale by correlating LC rates to the occurrence of capacity drop [START_REF] Cassidy | Increasing the capacity of an isolated merge by metering its on-ramp[END_REF]. Thus, the impacts of LC maneuvers are not quantified at a microscopic level in these studies.

Modeling LC processes and predicting their roles in traffic dynamics involve three primary elements: LC decision, relaxation upon LC and impacts in traffic streams. The decision process, whether to change lanes, is realized as the rates of LC given traffic conditions. The LC relaxation occurs when a lanechanger and/or its immediate follower accept spacings that are out of the equilibrium car-following behavior and then resume equilibrium spacings gradually. Finally, this relaxation process, along with the behavior of the followers in the initial and target lanes, governs the evolution of traffic upstream.

Current literature provides a wealth of research on the decision process, especially in the framework of microscopic simulations. Gipps [START_REF] Gipps | A model for the structure of lane-changing decision[END_REF] provided a framework to model the decision process of LC, which consisted of three primary steps to assess necessity, desirability and feasibility of an individual LC maneuver. Many LC models emerged based on this framework, especially to model the motivation for LC (i.e. desirability). Examples include models based on discrete choice theory (e.g. [START_REF] Toledo | Lane-changing model with explicit target lane choice[END_REF][START_REF] Choudhury | State dependence in lane changing models[END_REF][START_REF] Kesting | MOBIL: General Lane-Changing Model for Car-Following Model, Transportation Research Record[END_REF] and models based on Fuzzy Logic (e.g. 13). However, these models typically involve a large number of behavioral parameters that cannot be easily measured from field data. This makes calibration and validation of these models quite challenging and consequently, the results obtained from the models may be less meaningful. The same concern prevails in various gap acceptance models to describe feasibility of LC executions as these models also include behavioral parameters such as "critical time gap", a minimum time gap necessary to safely execute an LC maneuver. Finally, these studies focused more on the decision process of LC rather than its impacts in traffic streams.

Laval and Daganzo ( 14) developed a parsimonious model in the framework of the kinematic wave (KW) model of Lighthill and Whitham (15) and Richards (16) (LWR). Unlike the earlier extensions of the LWR model (e.g. 17-20) which treat LC maneuvers as fluid with instantaneous acceleration, this model treats LC maneuvers as particles with realistic properties such as bounded acceleration. Furthermore, the model treats each lane as a separate KW stream with a lane-changer as a moving bottleneck that blocks the entire lane. LC rates (i.e. LC decision) are determined based on speed difference in neighboring lanes. The model involves four parameters that are physically meaningful and are easily measured from data. The model is able to reproduce the reduction in bottleneck discharge rate and the capacity of a moving bottleneck in relation to its speed. The mechanism of capacity reduction was such that LC maneuvers near an active bottleneck create voids in traffic streams and thus reduce discharge rate. It was verified empirically that the model reproduces various features, such as lane-changing rates and amount of capacity reduction, around a merge bottleneck [START_REF] Laval | Impacts of lane changes at on-ramp bottlenecks: a theory and strategies to maximize capacity[END_REF].

Laval and Leclercq [START_REF] Laval | Microscopic modeling of the relaxation phenomenon using a microscopic lane-changing model[END_REF] later introduced an application of this model in a microscopic framework by incorporating car-following rule [START_REF] Newell | A simplified car-following theory: a lower order model[END_REF][START_REF] Daganzo | In traffic flow, cellular automata = kinematic waves[END_REF] and treating individual LC maneuvers as moving bottlenecks. Moreover, the model incorporates LC relaxation phenomenon which has been observed in earlier studies (e.g. [START_REF] Smith | Freeway data collection for studying vehicle interaction[END_REF] and was later validated and calibrated [START_REF] Leclercq | Relaxation phenomenon after changing lanes: experimental validation with NGSIM data set[END_REF][START_REF] Ma | Comparisons of speed-spacing relations under general car-following vs. lane-changing[END_REF]. Although these models are successful in reproducing important macroscopic traffic features, such as capacity reduction, the impacts of individual LC maneuvers were not explored explicitly at a microscopic level.

It was Coifman et al. (27) who first explicitly studied the impact of LC at a microscopic level. Notably, they attempted to measure the delay due to LC maneuvers in relation to the number of entering and exiting vehicles. Delay was taken as the difference between a vehicle's actual travel time and its estimated travel time if the vehicle were not influenced by any LC maneuvers occurred downstream. The latter travel time was estimated by the algorithm developed by Coifman [START_REF] Coifman | Vehicle reidentification and travel time measurement on congested freeways[END_REF]. The algorithm assumes a constant, definite speed of characteristics (i.e. kinematic waves) independent of traffic conditions as well as drivers. Then, the speeds observed at a particular location reflect traffic states propagating from TRB 2009 Annual Meeting CD-ROM Paper revised from original submittal.

downstream at the definite speed of wave known a priori. Based on these assumptions, the trajectory of each vehicle is estimated based on observations taken at the upstream end of a study section (near a merge on Interstate 405 in Los Angeles). The results from regression analysis show findings consistent with expectations, such that entering vehicles result in delay while exiting vehicles result in savings in delay. Moreover, based on the estimated parameter values from a linear regression, delay caused by entering vehicles was found to be larger than savings in delay by exiting vehicles.

The study by Coifman et al. (27) provides great insight on the impacts of LC maneuvers. However, as noted in their paper, the study bears some shortcomings, and a further investigation is necessary to provide a better understanding of LC impacts. Namely, the relaxation process of LC maneuvers was not taken into consideration. Thus, it is suspected that the study by Coifman et al. does not entirely exclude the impact of LC maneuvers executed outside the delay measurement areas and equally importantly, does not entirely measure the full impact of LC maneuvers in the measurement areas.

To this end, a new method is developed to measure the LC impacts including its relaxation processes.

The method in this study is developed in the spirit of the simplified KW model of Newell [START_REF] Newell | A simplified theory of kinematic waves in highway traffic, Part II: Queuing at freeway bottlenecks[END_REF] in light of previous findings that certain extensions of such continuum model (e.g. 14) are able to reproduce important traffic phenomena such as capacity drop. Thus, Newell's car-following model [START_REF] Newell | A simplified car-following theory: a lower order model[END_REF][START_REF] Daganzo | In traffic flow, cellular automata = kinematic waves[END_REF], a microscopic model consistent with the macroscopic model of Newell [START_REF] Newell | A simplified theory of kinematic waves in highway traffic, Part II: Queuing at freeway bottlenecks[END_REF], is used to study the LC impacts at a microscopic level. In particular, Newell's car-following model is used to predict trajectories of vehicles assuming no LC effect and to compare them with actual ones to quantify the discrepancies.

SITES AND DATA

Trajectory data from two multi-lane freeway facilities are analyzed. The data from both freeway locations are made available by the FHWA's Next Generation Simulation (NGSIM, URL: http://ngsim.fhwa.gov/) program. The schematics of the two freeway sites, Interstate 80 and US 101, are shown in Figures 1(a) and 1(b). The details of data collection method and some preliminary analyses are provided in Hranac et al [START_REF] Hranac | Next Generation Simulation (NGSIM) high-level data plan[END_REF]. In short, the trajectory data are available at the resolution of 1/10th of a second; i.e., the positions of each vehicle were recorded at 0.1 second intervals over 550 m (in I-80) and over 700 m (in US101).

For each location, over 5,000 vehicles were recorded during a 45-minute period.

All general-purpose lanes are used in the analysis, excluding the high-occupancy-vehicle (HOV) lanes since they typically exhibited different traffic states from the general-purpose lanes. The right-most lane (Lane 6) was also excluded in the analysis due to excessively frequent lane-changing. As explained later in the manuscript, our method requires every several vehicles to traverse the entire study section without lane-changing. However, the data from the right-most lane did not include enough number of non-lanechangers to perform such analysis.

METHOD TO MEASURE LANE-CHANGING IMPACTS

The overall logic of our method to measure LC impacts is as follows. It is assumed that the car-following behavior in the absence of LC is described by Newell (4) as supported by recent empirical studies [START_REF] Ahn | Verification of a simplified car-following theory[END_REF][START_REF] Wang | The study on the effect of lane change maneuvers on a simplified car-following theory[END_REF][START_REF] Duret | Estimating individual speed-spacing relationship and assessing the Newell's car-following model ability to reproduce trajectories[END_REF][START_REF] Chiabaut | Fundamental diagram estimation through passing rate measurements in congestion[END_REF], and Duret et al. [START_REF] Duret | Estimating individual speed-spacing relationship and assessing the Newell's car-following model ability to reproduce trajectories[END_REF] and Chiabaut et al. [START_REF] Chiabaut | Fundamental diagram estimation through passing rate measurements in congestion[END_REF] verified this using the same NGSIM dataset. Thus, the trajectory of each vehicle is estimated according to Newell's theory given a reference leader, representing the trajectory if there were no LC maneuvers between the vehicle and the reference leader. The impact of LC maneuvers is then measured along characteristics (i.e. kinematic waves) as a displacement in time and location of the actual trajectory from the estimated one. The details of the method to measure the impacts of LC are described below including a short description of Newell's car-following theory.

The car-following model proposed by Newell involves few parameters and uses logic that is different from conventional car-following models such as stimulus-response based models. In this theory, a driver selects his spacing for a given speed in such a way that under congestion regime his trajectory replicates his leader's only with a displacement in time and space. In Figure 2(a), τ j and d j correspond to the displacement in time and space for vehicle j in response to the leader's speed change from v to v'. Thus, the disturbance propagates from vehicles j-1 to j at the speed of d j / τ j . The model assumes constant values of τ j and d j for each individual vehicle independent of their speeds. This implies that the relationship between spacing and speed for a vehicle is linear (since spacing of vehicle j, s j = d j + τ j v) as illustrated in In this study, it is assumed that a disturbance propagates as a random walk as per Newell's theory and that the speed of the kinematic wave (measured with respect to the reference vehicle) converges to the average value, d / τ, when it reaches the nth vehicle. As noted in [START_REF] Chiabaut | From heterogeneous drivers to macroscopic patterns in congestion[END_REF], as n increases, the wave speed will converge to its mean, and the confidence interval of the mean will decrease. The n was set to 15 in light of the finding in [START_REF] Chiabaut | From heterogeneous drivers to macroscopic patterns in congestion[END_REF] that the convergence to the average beyond 15 vehicles was ensured within 2% error.

Then, the effect of LC maneuvers is quantified for the 15th vehicle upstream. This approach was adopted to account for the differences in wave speeds due to driver differences and work with the average wave speed which was rather straightforward to measure from available data.

Figure 3 illustrates in detail the way in which LC impact was measured. The analysis begins by simulating the trajectory of vehicle 15 (a bold dashed trajectory in the figure) with respect to the reference vehicle (vehicle 0 in the figure) according to Newell's car-following model. Thus, t 2t 1 (and t 3t 4 ) is the sum of τ j 's for vehicles 1 through 15, which is estimated as 15*τ, while x 1x 2 (and x 4x 3 ) corresponds to 15*d. (It should be clear that the sum of the τ j 's simulated for vehicles 1 -15 converges to 15*τ as per [START_REF] Chiabaut | From heterogeneous drivers to macroscopic patterns in congestion[END_REF].) The speed of four kinematic waves, w 1w 4 , in Figure 3(a) is then d / τ. Chiabaut et al. [START_REF] Chiabaut | Fundamental diagram estimation through passing rate measurements in congestion[END_REF] have previously determined all parameters associated with Newell's model (i.e. the parameters for the joint distribution of τ j and d j ) for the same dataset, and thus, the same parameter values of τ and d are used for simulating trajectories. Note that point (t 1 , x 1 ) is selected to ensure that w 1 propagates through 15 vehicles upstream before reaching the upstream end of the study section, and (t 3 , x 3 ) is selected at the downstream end.

Next, the relaxation processes of LC maneuvers of interest are accommodated. For this, it is made certain that there is no LC maneuver in region a (a lower-left shaded area in Figure 3(a)), whose horizontal distance corresponds to a maximum relaxation time. In light of the findings from previous studies (24-26), 15 seconds was used as the threshold. Thus, it is assumed that the relaxation of any LC occurrence below w 1 is completed in or before region a. Similarly, it is also made certain that region c (the upper-right shaded area in Figure 3(a)) is free of LC since the relaxation of a maneuver in this region would likely be completed above w 4 . Then, the impact of all lane-change maneuvers in region b is measured along the trajectory of vehicle 15 between points B and E.

The impact of LC maneuver(s) is measured by comparing the virtual and actual trajectories of vehicle 15.

In Figure 3 ' B E u u r r -||, which are measured with respect to the reference vehicle along the characteristics. For computational efficiency, the latter measurement illustrated in Figure 3(b) is used. The latter method requires only one parameter of the average speed of wave, rather than separate observations of τ and d as in the first method. The average wave speed is easily measured from trajectory or loop detector data. Finally, note that the impact we measure is the cumulative effect of all entering and exiting LC maneuvers rather than a single maneuver.

An example with real trajectories is shown in Figure 3(c). The figure illustrates a case with two insertions and two exits as marked by circles. The bold dashed trajectory represents a simulated trajectory of vehicle 15, corresponding to a simple shift of the leader of the platoon in the absence of lane changes. At the downstream end of vehicle 15, the simulated trajectory lies left to the actual one, indicating that the two insertions and two exits resulted in positive impact (i.e. additional delay) along the characteristic.

EMPIRICAL RESULTS

Based on the method described in the previous section, a total of 48 (61) independent samples were obtained from I-80 (US 101). Table 1 presents the sample size for each composition of the numbers of insertions and exits. Most of these samples came from the left two lanes as there were few instances where both vehicles 0 and 15 traversed the entire study section without changing their lane.

As shown in Table 1, there were two observations of no LCs, (0 insertions, 0 exits) for I-80 (but no observation on US101). The impacts for these cases should be close to zero if Newell's theory holds. The TRB 2009 Annual Meeting CD-ROM Paper revised from original submittal.

measured impacts are -1.54 and 3.02, which correspond to -1.5% and +2.8% error in position along the characteristics since B u r =107 (d=7m and τ=1.4sec). Note that this error term precludes the calibration error, B u r in Figure 3(a), due to the randomness of individual drivers and represents the error of assuming Newell's model. Although a rigorous statistical testing could not be done due to the small sample size, the result supports the validity of Newell's car-following theory and thus our method to measure the impact of LC.

0 0 0 0 0 0 0 0 0 1 3 5 1 0 1 0 0 0 5 1 1 1 1 0 2 3 1 4 3 2 0 0 0 4 3 2 2 2 0 3 1 0 0 1 3 1 0 0 2 2 3 0 0 0 4 0 0 1 1 2 0 0 0 2 2 3 3 1 0 5 0 0 1 1 0 0 0 0 2 2 2 3 1 3 No. of Entries 6 0 0 0 1 1 0 0 0 1 0 0 3 2 2
Figures 4(a)-(c) show the relationships between the measured impact and number of insertions, number of exits and net number of entries for the I-80 site, respectively. They show that the effect of LC vs. the number of insertions (Figure 4(a)) or exits (Figure 4(b)) does not display clear patterns. This is not surprising as the magnitude of LC impact is likely to depend on both factors combined. As shown in Figure 4(c), the measured LC impact increases with respect to the increases in number of net insertions (number of insertions -number of exits), which is consistent with the findings from Coifman et al. [START_REF] Coifman | Impact of lane-change maneuvers on congested freeway segment delays[END_REF]. Also, the scatter reveals a relation that is approximately linear, which is more pronounced with the average impacts by the net number (circles in the figure). A linear trend line is shown in Figure 4(c) as well as the corresponding linear model and R 2 . These were obtained via the weighted least squares method using the averages by the net number. The weight corresponds to the number of observations for each net number of insertions. The model parameters are statistically significant (based on a regression analysis). The intercept term (4.06SI) is positive, implying that if the same number of insertions and exits occur, we expect to observe a larger impact by insertions and thus, a positive displacement in trajectory along characteristics. (The unit of an LC impact is (m 2 +sec 2 ) 0.5 . For simplicity, the unit is denoted as "SI" here on.)

Moreover, the parameter for the linear term is 7.35SI, indicating that each additional insertion would increase the positive displacement by 7.12SI, given a constant number of exits. It is interesting to note that the estimated values of τ (=1.4sec) and d (=7m) yield a vector along the characteristic with a length of 7.14, which is close to the estimated parameter of the linear term, 7.12. This indicates that given a fixed number of exits, each additional insertion has an impact of simply adding a vehicle to the traffic stream and that no additional delay is incurred other than the delay by introducing a unit vehicle. Moreover, in light of the positive parameter of the intercept term (4.06), one can deduce that each additional exit has an impact less than subtracting a vehicle from the traffic stream. This may occur when a follower does not close a gap entirely and maintains a larger spacing upon his leader's departure from the lane. Thus, the results imply that for the same number of insertions and exits, we expect to observe additional delay to the traffic flow upstream compared to no LC (0 insertions, 0 exits) case.

Similar results were obtained for US 101 (see Figure 4 estimated parameter for the intercept term (15.7) is nearly twice as large as the linear term. This indicates that followers of exiting vehicles do not close their gaps at all. This seems highly unlikely as the freeway section is heavily congested. This seems attributable to a relatively large scatter, and a further investigation is warranted. Note that regarding the errors made in this analysis we can make the following decomposition. The error can be related to:

• w: provided that we use 15 vehicles, we have an error of 2% on w [START_REF] Chiabaut | From heterogeneous drivers to macroscopic patterns in congestion[END_REF].

• the NGSim longitudinal position's measurement, estimated to be 1.2 m (see www.ngsim.fhwa.dot.gov). For both errors we can examine various types. If they are comparable to a white noise, their impact is negligible in the value of the regressions shown above (because we combine many observations in our TRB 2009 Annual Meeting CD-ROM Paper revised from original submittal.

sample). If those errors are systematic, they do not induce any systematic biases in our measurements, since we are using spatial differences.

IMPACT RELATED TO OTHER VARIABLES

In addition to the numbers of insertions and exits, two other types of additional factors are considered: an average traffic state around LC maneuvers and perturbations in traffic states by lane changers (in region b of Figure 3(a)) at the time of maneuvers. The two factors are measured separately for insertions and exits in terms of speed and spacing. As illustrated in Figure 5, the average state is measured by taking the average speed of five preceding leaders along characteristics with respect to the time of each maneuver. The perturbation in traffic state is then taken as the difference between this average speed and the speed of the lane-changer at the time of the maneuver. Note that speeds here are 1-second moving averages since the trajectory data display some noise in its original form [START_REF] Thiemann | Estimating Acceleration and Lane-Changing Dynamics Based on NGSIM Trajectory Data[END_REF]. For multiple maneuvers, the average state is the average of the individual measurements, and the perturbation in state is the sum of all individual perturbations. The traffic states and their perturbations are also measured in terms of spacing (see Figure 5(c)). Finally, the set of independent variables considered are listed below. The significance of each of these variables is evaluated by the Principal Components Analysis (PCA).

The PCA is a statistical method that systematically looks for tendencies/correlations among variables (including a dependent variable) in a dataset. It finds a subset of variables (in a reduced dimensional space) that are orthogonal and best represent the data scatter. The results from the PCA are summarized in Table 2. The variables associated with correlations larger than 0.6 were considered to be significant factors [START_REF] Snedecor | Statistical methods[END_REF]. It confirms the preliminary observation in that the net number of insertions has the most significant effect on the magnitude of LC impact. This is consistent for both I-80 and US 101. It is also notable that the number of insertions is the second most correlated factor for I-80. This is attributed to the earlier observation that insertions have more predominant impact that exits. All other variables came out insignificant, which is rather surprising. It is speculated that this result is attributed to the small range of speeds (between 0 and 15 m/s) observed in the data sets. Nevertheless, this method of measuring average state and its perturbation can be easily applied to a larger dataset in the future.

CONCLUSIONS

The present study is concerned with measuring the impact of lane-changing maneuvers and identifying significant factors. We have developed a methodology to measure the cumulative impact of insertions and exits within a set of fifteen vehicles. The methodology facilitates a simple car-following model of [START_REF] Newell | A simplified car-following theory: a lower order model[END_REF] to predict a virtual trajectory of the fifteenth vehicle based on the first leader. Thus, the methodology is fully consistent with the LWR kinematic-wave theory. The discrepancy between the actual trajectory and the simulated one along characteristic was measured as the net impact of insertions and exits.

Based on the methodology, we have analyzed the NGSIM trajectory data from I-80 and US101. The results show that the net number of insertions is the most significant factor in relation to the measured LC impact and that the impact of an insertion is larger than that of an exit. Traffic conditions around LC maneuvers and the perturbed state by lane-changers were also evaluated for significance. However, the PCA results show that the impact of LC is not highly correlated with state-related variables. As discussed previously, a small range of speed due to heavily-congested conditions seem to have an effect on the result. Thus, a proper treatment of traffic states will require a large range of speed, which will most likely necessitate a collection of extensive trajectory data. Furthermore, it would be desirable to obtain larger samples for more in-depth statistical analysis of various variables. For this, it would be interesting to see if the assumption of a constant wave propagation speed holds for vehicles less than 15, which may result in larger samples.

Finally, relatively small samples of LC impacts were measured from the two freeway datasets. Thus, it was not possible to conduct a more detailed analysis of the incremental effect of insertions and exits as well as comparisons between the two types of maneuvers. Nevertheless, this study provides a methodology that is theoretically grounded and can be verified easily from data.

Figure 2 (

 2 Figure 2(b), and that the propagation speeds of disturbances are constant independent of vehicle j's speed.Finally, τ j and d j are assumed to come from a joint distribution such that a disturbance propagates from one vehicle to another as a random walk. The mean speed of disturbance is d / τ, where d and τ are the mean values of spatial and temporal translation. At the macroscopic level, this simple car-following model corresponds to triangular flow-density relations as shown in Figure2(c).

FIGURE 2

 2 FIGURE 2 Illustration of Newell's Car-Following Theory (a) Vehicle Trajectories (adopted from Newell (2002)) (b) Speed-Spacing Relationship for Vehicle j (adopted from Newell (2002)) (c) Flow-Density Relationship (adopted from Ahn and Cassidy (2004))

  (a), the B u r represents the displacement of the actual trajectory by the random error in estimating the trajectory if there were no LC maneuvers. The E u r represents the displacement by the estimation error and also by LC maneuver(s). Thus, B E u u r ris the impact of LC, and its magnitude, || B E u u r r -||, captures the displacement in time (i.e. delay) and in position due to LC maneuvers. Notice that, as shown in Figure 3(b), this is equivalent to measuring the length of the difference in vectors, || '

  FIGURE 3 (a) Illustration of Method to Measure LC Impact (b) Simplified Method (c) Example Trajectories with Two Insertions and Two Exits

  (d) for a scatter plot and average by the net number), such that the estimated values of τ (=1.45sec) and d (=7.1m) yield a vector with a length of 7.25SI. This estimated value is similar to the estimated parameter of the linear term, 7.32. For US101, the TRB 2009 Annual Meeting CD-ROM Paper revised from original submittal.

  FIGURE 4 (a) LC Impact vs. Number of Insertions, I-80 (b) LC Impact vs. Number of Exits, I-80 (c) LC Impact vs. Net Number of Insertions, I-80 (d) LC Impact vs. Net Number of Insertions, US101

N

  in : Number of insertions N ex : Number of exits N net : Net number of entries, N entry -N exit v: Average 1-second moving average speed of lane changers at the time of maneuver v : Average speed of five preceding vehicles to lane-changer along characteristics, i.e., Average spacing of lane-changer at the time of maneuvers s : Average spacing of five preceding vehicle to lane-changer (immediate follower for exiting maneuver) along characteristics, i.e., Perturbation in speed, vv Δs: Perturbation in spacing, ss Meeting CD-ROM Paper revised from original submittal.

FIGURE 5

 5 FIGURE 5 Illustration of Measuring Average Traffic States around a LC Maneuver (a) An Example of an Insertion; (b) Measuring Average Speed around a LC Maneuver (c) Measuring Average Spacing around a LC Maneuver

TABLE 1

 1 Sample Size of Each Composition of Numbers of Entries and Exits

								No. of Exits
					I 80							US 101
		0	1	2	3	4	5	6	0	1	2	3	4	5	6
	0	2	8	1	0	0

TABLE 2

 2 Correlation Coefficients Measured by Principal Components Analysis

	Variable	Correlation Coefficient I 80 US 101
	N in	0.62	0.34
	N ex	0.05	-0.35
	N net	0.80	0.72
	v	0.20	0.04
	v	0.17	0.13
	s	0.22	0.07
	s	0.48	0.13
	Δv	-0.06	0.09
	Δs	0.26	0.08

TRB 2009 Annual Meeting CD-ROM Paper revised from original submittal.