Yue Kang

Danilo Alves De Lima

Alessandro Corrêa

Dynamic obstacles

Keywords: Obstacle avoidance, Image-based Dynamic Window Approach, human-vehicle interaction, driving safety, parameter regulation

come

I. INTRODUCTION

Traditional Advanced Driver Assistance Systems (ADAS) have been advanced with a considerably fast pace ever since its first appearance. Lateral and longitudinal stabilization and control, careful active actions and warnings and full active actions build up the three steps of development for ADAS [START_REF] Borhade | Advanced driver assistance system[END_REF], respectively represented by the widely renowned Anti-lock Braking System (ABS), the Adaptive Cruise Control (ACC) [START_REF] Vahidi | Research advances in intelligent collision avoidance and adaptive cruise control[END_REF] and more recently the Collisions Avoidance (CAV) by emergency braking [START_REF] Isermann | Collision-avoidance systems proreta: Situation analysis and intervention control[END_REF]. Different approaches from various directions of research contribute to the core interest of this field: driving safety [START_REF] Tang | Collision avoidance timing analysis of dsrcbased vehicles[END_REF].

It has been accepted without doute that safety is of critical interest to the intelligent transportation systems. Supervision, control and correction of human driving characteristics have long been a major issue to the driving safety on the road [START_REF] Lotz | System architectures for automated vehicle guidance concepts[END_REF]. A great deal of researchers devote their effort into the modelling of human driving behaviors for the purpose of predicting and correcting such potential danger introduced by humankind. For instance, [START_REF] Wang | A safety-based approaching behavioural model with various driving characteristics[END_REF] proposed a safety-based approaching behavioural model for the driver's car-following behavior with various driving characteristics. A more detailed model of driving behavior characteristics analysis is illustrated in [START_REF] Ge | Study on driving behavior and traffic conflict at highway intersection[END_REF] with a weight determination based on influences of various driving behaviors on conflict. More recently, a novel method for predicting the next contextual changing point of driving behavior on the basis of a Bayesian double articulation analyzer was implemented in [START_REF] Nagasaka | Prediction of next contextual changing point of driving behavior using unsupervised bayesian double articulation analyzer[END_REF].

The authors are with Heudiasyc UMR CNRS 7253 Université de Technologie de Compiègne. This work is founded in part by the VERVE Project (Picardie region and Europe), in the context of the MS2T LABEX and ROBOTEX projects. Yue Kang holds a Ph.D scholarship from Chinese Scolarship Council and Picardie region in France. Contact authors yue.kang@hds.utc.fr.

The continuous development in such field supports the point that, while fully autonomous intelligent vehicles remains currently limited by critical circumstance and enriched database [START_REF] Houenou | Vehicle trajectory prediction based on motion model and maneuver recognition[END_REF], research that focuses on improving current driving systems for human drivers is still of irreplaceable significance [START_REF] Isermann | Collision-avoidance systems proreta: Situation analysis and intervention control[END_REF]. Human-vehicle interaction is therefore emphasized in the past years and decades for the purpose of decreasing the hazard of human factors in driving circumstance. Primitive modelings and simulations could date back to [START_REF] Allen | Modeling and simulation of driver/vehicle interaction[END_REF] and [START_REF] Kopf | Driver-vehicle interaction while driving with acc in borderline situations[END_REF] for instance, followed by a seriel of approaches from different directions of research [START_REF] Harvey | In-vehicle information systems to meet the needs of drivers[END_REF] [START_REF] Kun | Automotive user interfaces and interactive applications in the car[END_REF]. Placing emphasis on human-vehicle interaction, as a bridge between human drivers and safety-supporting assistance systems, obviously meets the needs of safe diving.

As a complement of traditional ADAS, as well as a combination of human driving behaviors modelling, our initial approaches [START_REF] Kang | An approach of human driving behavior correction based on dynamic window approach[END_REF] and [START_REF] Kang | Driving behavior correction in human-vehicle interaction based on dynamic window approach[END_REF] aimed at simulating and correcting the human drivers' decision faults in humanvehicle interaction accomplished by applying the Imagebased Dynamic Window Approach (IDWA) [START_REF] Lima | An image based dynamic window approach for local navigation of an autonomous vehicle in urban environments[END_REF], a variation from the original DWA [START_REF] Fox | The dynamic window approach to collision avoidance[END_REF], using the visual information of road land and center provided by a pinhole camera, with an implement of obstacle detection and avoidance guaranteed by an occupancy grid [START_REF] Elfes | Using occupancy grids for mobile robot perception and navigation[END_REF],. The controlling faults by human drivers were presented as failures during static obstacles avoidance. In this paper, we march forward in the same direction of research by replacing the static obstacles in the scenario with dynamic, "moving" ones, for the purpose of a better representation of real driving circumstances.

This article is organized as follows: in Section II, we present the robot model and the simulation environment; in Section III, we present the fondamental concepts of the DWA algorithm, the design of human-vehicle interaction, the Human Driver Behavior (HDB) controller and the configuration of dynamic obstacles; experimental results and performance analysis are presented in Section IV.

II. GENERAL DEFINITIONS

As a consequence of our previous work [START_REF] Kang | An approach of human driving behavior correction based on dynamic window approach[END_REF] [15], we continue our research and validation by preserving the robotic model that was implemented in the initial experimental environment. Without special indication, we do not particularly distinguish between the following conceptions: "the robot", "the robotic model" and "the (experimental) vehicle". The robot follows the path according to the kinematic model of a front wheel car [START_REF] Luca | Robot Motion Planning and Control[END_REF] as:

    ẋr ẏr θ φ     =     cos θ cos φ sin θ cos φ sin φ/l 0     v 1 +     0 0 0 1     v 2 , (1)
where the vehicle configuration is given by q = [x r y r θ φ] T , with the position (x r , y r ) and orientation (θ) of the car's reference frame {R} in relation to a static world reference frame {O}, and φ is the average steering angle of the front wheels by the Ackerman's approximation. The orientation and steering angles (θ and φ) are positive counter-clockwise, with θ ∈] -π, π] and φ ∈ [-φ max , φ max ]. The variables are illustrated in the Figure 1.

The control input for the vehicle of the model ( 1) is u = [v 1 v 2 ] T , which consists of respectively the linear velocity v 1 and the steering velocity v 2 of the front wheels. With the relationship between linear velocity v and front wheels velocity v 1 as v = v 1 cos φ, as well as the angular velocity θ = v 1 cos φ/r 1 = ω and the steering angle, it is possible to choose the control input for the robot as u r = [v ω] T . The robot in our work is considered to be set in a planar road. In order to focus our research on the algorithms of avoiding dynamic obstacles, we simplify the environment of simulation as a straight road with two driving lanes. The width of the lane and the size of the vehicle are proportional to the real driving circumstances. A typical example schema of the simulation environment in global version is illustrated in Figure 2(a). The visual information utilized for the IDWA algorithm is provided by a pinhole camera. The camera frame {C} is also represented in Figure 1 with optical center position in (x c , y c , z c ) = (t x , t y , t z ) in the robot frame and a constant tilt offset 0 < ρ < π 2 related to the x r axis. Figure 2(b) shows a typical example of the image captured by the camera, from which the information of the road lane center is calculated and provided to IDWA as the referencial of the vehicle's heading.

Compared with our previous work, the modification to the obstacles is of the most significance in this article. The obstacles, previously represented by static blocks with similar size to our vehicle, are currently enhanced with the identical kinematic model given by the equation ( 1). This modification enables the capacity of displacement to the obstacles, while maintaining a relatively simple controlling manoeuvre: similar control strategies of the vehicle can be applied to the obstacles to simulate real driving circumstances on the road.

III. DYNAMIC OBSTACLES AVOIDANCE

A. Image-based Dynamic Window Approach

Recalling the fondamental algorithm of obstacle avoidance of our previous work [START_REF] Kang | An approach of human driving behavior correction based on dynamic window approach[END_REF], we present a brief introduction of the Imaged-based Dynamic Window Approach (IDWA), which is a reactive technique in obstacle detection and avoidance, originally proposed by [START_REF] Fox | The dynamic window approach to collision avoidance[END_REF] and advanced by [START_REF] Lima | An image based dynamic window approach for local navigation of an autonomous vehicle in urban environments[END_REF]. To accomplish the propose of detecting and bypassing the obstacles, an objective function ( 2) is optimized in order to select the best control input regarding the desired configuration to the robot. The objective function is constituted with three weighted components: the goal position (heading), the obstacle distance (dist) and the final linear velocity (velocity), represented as:

DW A(v, ω) =α • heading(v, ω) + β • dist(v, ω) + γ • velocity(v, ω).
(

) 2
As a consequence of the optimisation, the dynamic window search space, which considers the actual speed of the vehicle, its accelerations, the obstacles in the workspace, and also the physical limits of the vehicle is consequently generated as:

V DW = V d ∩ V a ∩ V s . (3)
where V d is the set of all reachable velocities in a time interval t according to the current linear and angular acceleration of the vehicle, V a represents the admissible velocities classified by the distance to the obstacles, and V s is the set of velocities that satisfy the constraints of the maximum accelerations. In this proposed approach of human-vehicle interaction, the driver is considered to provide an input [v ω] T for the driving control, which is then delivered to the IDWA navigation method for the verification (and correction if needed). The progress of IDWA from the original DWA is the application of the visual information, which is provided by the camera implemented on the vehicle. From the image captured by the camera(Figure 1), the road lane as well as its center is obtained. Consequently, the road center information builds up a precise goal position (heading) for the objective function [START_REF] Vahidi | Research advances in intelligent collision avoidance and adaptive cruise control[END_REF].

For the purpose of better utilizing the algorithm of IDWA, a process of the regulation of the three weighting parameters α, β and γ in ( 2) is of apparent significance. Noticing that the three parameters possess an obvious similarity to those of the widely known PID controller, we implement a simple tuning method, during which we simplify the procedure of determining the absolute values by normalizing the output of the objective function (2) after applying the pre-tuned parameters, as the order of magnitude of the parameters holds a prior significance to the absolute values.

In addition, while the original DWA algorithm does not include the manoeuvre of obstacle detection, we implement the algorithm with a LIDAR sensor [START_REF] Lima | An image based dynamic window approach for local navigation of an autonomous vehicle in urban environments[END_REF]. The sensor provides the support of obstacle detection by establishing an occupancy grid [START_REF] Elfes | Using occupancy grids for mobile robot perception and navigation[END_REF] with real-time update, as is shown in Figure 2(c). The occupancy grid provides a "drivable" zone for the vehicle, i.e. a limitation for the proper function of DWA.

B. Human-vehicle interaction

The interaction between human drivers and the vehicle in our approach is represented by the correction of potentially dangerous behaviors due to a lack of proper reaction(deceleration, turning, etc.) when engaging the obstacles. During the simulation, the decision of the driver is expressed by a referential path for the controller, for the intention of reducing the time cost of calculation. An example of referential paths of human driver behaviors is shown in Figure 3, in which an overtaking behavior is represented in Figure 3(a), and a fault driving behavior is represented in Figure 3(b). It is important to note that these referential paths are not planned trajectories to be followed by the autonomous vehicle, but a mathematical representation of possible behaviors of the human drivers, which are to be corrected or optimized by the intelligent navigation systems (based on the IDWA).

The design of the controller to our vehicle is also derived from our previous work [START_REF] Kang | An approach of human driving behavior correction based on dynamic window approach[END_REF] and [START_REF] Kang | Driving behavior correction in human-vehicle interaction based on dynamic window approach[END_REF], which is proved to function adequately for the propose of representing the primary driving behavior of a human driver. Given that human drivers tend to keep the vehicles in the center of the road lane, we establish a referential path by assembling the coordinates (x p , y p ) of the virtual middle line of the drivable lane. Based on the referential path coordinates, the design of the Human Driving Behavior (HDB) controller is represented as:

ω = v d v l (x r -x p ) 2 + (y r -y p ) 2 + β, (4)
where ω is the feedback gain of the controller, v d is the desired linear velocity of the tracking control, v l is the velocity limitation of the vehicle, (x r , y r ) are coordinates of the position of the vehicle, (x p , y p ) are coordinates of the corresponding point on the referential path, and β is an additive white Gaussian noise (AWGN) which represents inaccuracy of human drivers' control.

As human drivers rarely have access to the precise drift angle of the vehicle, the control law does not involve any direct angular information. Instead, the controller functions as a negative feedback regulator, similar to the proportional section of a classic PID controller, according to the error or the deviation between the position of the vehicle and the decided path.

C. Dynamic obstacles

The obstacles in our approach are considered to be moving vehicles on the road with inferior linear velocity, with which an overtaking determination by the following car is essential for the purpose of avoiding the collision. The visual outcome of an obstacle is identical to that in our initial work: a blue opaque planar rectangle with the same size of the experimental vehicle (the Figure 2(a)), due to the fact that the detection of obstacles in our work is accomplished by a simulative algorithm of 2D LIDAR.

To imitate the actual driving circumstances, we apply the same kinematic model (1) to the car-like obstacles, with limited linear velocity and basic control algorithm. An obstaclebehaved vehicle forwards as well in the middle of the road lane, without direct communication to our experimental vehicle or other obstacle vehicles. In a circumstance with multiple obstacle vehicles, the velocities of each vehicle in the same direction are set differently in order to avoid the collision or overlapping.

Since the obstacles become "moving" in the scenario, the previous method of evasive trajectory [START_REF] Isermann | Collision-avoidance systems proreta: Situation analysis and intervention control[END_REF] in our initial work (Figure 3(a)) is no longer suitable, as it requires a static off-line calculation before being applied to the avoidance procedure. However, we observe in [START_REF] Kang | An approach of human driving behavior correction based on dynamic window approach[END_REF] that the design of HDB controller is capable to handle a predefined referential path that intersects or directly goes across obstacles, which is considered as a representative danger behavior in driving and is possible to be corrected by HDB+IDWA control pattern. We therefore utilize an ensemble of the coordinates (x p , y p ) of the virtual middle line of the drivable lane as the referential path for the vehicle, as is shown in the Figure 3(b). Since the set of admissible control inputs V DW is calculated in each iteration of control, the correction of human drivers' faults is therefore guaranteed, as well as the security of the driving tasks.

IV. EXPERIMENTAL RESULTS

The experimental simulation is proceeded on Matlab R2014a (8.3.0.532). The environment consists of an open track (7.8 meters in width) with different quantity of obstacles (5.86 by 2.92 meters each). The ratio of the image is 0.0630 meter per pixel.

DW A(v, ω) =α • heading(v, ω) + β • dist(v, ω) + γ • velocity(v, ω).
(

) 5
The first section of our experiment aims at the effect of different tunings of the parameters in the objective function ( 5), namely α, β and γ, representing respectively the goal position (heading), the obstacle distance (dist) and the final linear velocity (velocity). Given that the determinant of the parameters relies on their order of magnitude rather that their absolute values, we regulate the parameters with a stepping rate of 5, in other words half of one order of magnitude.

For the purpose of a better regulation of the parameters, each experimental simulation starts with idetical initial condition: the scenario consists of one single dynamic obstacle; the vehicle starts with the same linear velocity (5m/s, twice of the velocity of the obstacle) and angular velocity (zero); the initial position of the obstacle is outside of the detection of LIDAR lasers.

Table I Unit: s parameter settings. "Bypass time" is defined as the time interval which begins from the moment the obstacle is detected by the laser sensor, and ends at the moment the robot establishes a stable linear velocity after returning the original lane. The "X" marks in the Table I indicated that, with such regulation of the parameters, the robot failed to behave the bypass procedure for at least once during the experiment; in other words the vehicle followed the obstacle in front and did not overtake it. The "N/A" marks represented the omission of such combination of parameters during the simulation.

H H H H γ β 0.1α 0.5α α 5α 10α 50α 0.1α N/A N/A N/A N/A X X 0.5α N/A N/A N/A N/A X X α N/A N/A X X
The results indicated the emphasis on the obstacle distance (dist) and the final linear velocity (velocity) terms in the objective function 5, compared with the goal position (heading) term. The vehicle appeared more likely to perform a low-speed following behavior when the parameter α was relatively large, for the reason that the IDWA algorithm tends to hand out a result with which the vehicle maintains its heading with respect to the referential path. Such appearance indicates that, should emphasis be put on heading, the human-vehicle interaction functions in a greater degree as a limitation of the overtaking behavior.

On the other hand, with the augmentation of the parameters β and γ, the bypass behavior of the robot was gradually and reliably guaranteed, and the time cost of overtaking was also reduced. The human-vehicle interaction under such preference appear to enable the overtaking behavior, which is regarded as a correction performed by the system when the linear velocity of the vehicle is faster than the obstacles ahead.

However, we observed that the reduction of bypass time was obviously slowed down when both β and γ reached the ratio of 50 to the value of α. We conclude that, alongside with the augmentation of β and γ, IDWA calculation aggressively puts emphasis on maintaining a relatively high linear velocity and keeping the furthermost distance between the vehicle and the obstacles, thus neglecting the guidance of the vehicle to return back to the original lane. Consequently, we regulate the parameters as β = γ = 50α at the moment.

B. Validation of dynamic obstacles avoidance

In order to validate our approach of dynamic obstacles avoidance implemented by the HDB+IDWA control pattern, as well as the tuning of the parameters in Section IV-A, we complicate the scenario of driving by increasing the number of the dynamic obstacles and their linear velocities. The first step consists of two dynamic obstacles in the same direction of the robot, the one in the front possessing a higher linear velocity in order to avoid the collision between the obstacles themselves. The result in the Figure 4 illustrated that the configuration of HDB+IDWA control pattern in Section IV-A is capable to ensure the avoidance of a sequence of several dynamic obstacles in the same direction. As long as the linear velocity of the robot and distance from the obstacles are guaranteed by IDWA algorithm, the bypass process remains smooth and secured, as is shown in the Figure 5. To imitate the real driving condition, we complicate furthermore the scenario by moving one of the dynamic obstacles on the opposite lane with reversed direction. The newly introduced obstacle initially blocks the possible bypass path of the robot until it leaves the detection zone of the LIDAR sensor. Hence, the robot is forced to perform a car-following behavior before the possibility of safe bypass is ensured.

Figure 6 illustrated the "follow-and-bypass" procedure of Fig. 6. Obstacle avoidance by "follow-and-bypass" behavior.

the vehicle engaging the dynamic obstacle in the opposite direction. The vehicle followed the car in front with a relatively low linear velocity (Figure 7(a)) to ensure the driving safety, guaranteed by the obstacle distance (dist) term and its parameter β. As a consequence, the bypass time interval of the second obstacle was prolonged, due to the need for the vehicle to restore its linear velocity. An important remark is that, during this simulation, the bypass procedure was not always ensured, as the vehicle continued following the obstacle in front with a low linear velocity. In addition, we observed that in several situations the vehicle moved so close to the road lane (for the purpose to keep the distance to the opposite obstacle) that the IDWA algorithm determined that no available linear velocity could be verified, not to mention provided. This deficiency is noteworthy as it limits the practicality of the proposed method.

V. CONCLUSION

In this paper we have presented an approach of dynamic obstacle avoidance for car-like robot, with the help of IDWA algorithm and HDB controller based on our previous work. The results of the experimental simulation have proved that such control manoeuvre is capable to ensure the driving safety while performing the avoidance of dynamic obstacles.

The regulation of the three parameters in the objective function of IDWA algorithm have revealed the significance of the obstacle distance (dist) and the final linear velocity (velocity) criteria during the dynamic obstacle avoidance. While focusing on the bypass procedure, these two terms hold the prior focus to the heading of the vehicle. This phenomenon is comprehensible as the avoidance of the obstacles calls for migrations from the referential path of driving.

The deficiency of this approach is mainly the issue of relatively low linear velocity of the vehicles, both the robot and the dynamic obstacles. The limitation is generally due to the usage of kinematic model of the vehicle, which provides a relatively inaccurate fundament for the simulations. Improvement towards such defect is promised to optimize the practicability of this approach in real driving circumstances.

Another direction of improving our approach lies in variable parameters for the IDWA algorithm. A real-time, self-adaptive and intelligent method for the regulation of the parameters is believed to be more than profitable, as the system will be more capable to handle with different circumstances, thus providing a higher level of security of driving.

This paper has illustrated the progress in our series of work in the project VERVE 1 . Our future research will proceed particularly in the experimental platform of SCANeR™ Studio, before being finalized on the experimental vehicles for the validation of the methodology.

Fig. 1 .

 1 Fig. 1. Kinematic model diagram for a front wheel car-like robot. In this model the vehicle reference frame R performs circular trajectories related to the instantaneous center of curvature (ICC).

  (a) Example of the global version during a bypass procedure. (b) Example of the cameral version. (c) Vehicle center oriented occupancy grid.

Fig. 2 .

 2 Fig. 2. Typical schema of the environment of simulation.

Fig. 3 .

 3 Fig. 3. Revision of the referential path.

Fig. 4 .

 4 Fig. 4. Validation of dynamic obstacles avoidance.

Fig. 5 .

 5 Fig. 5. Velocities of the robot during the bypass validation.

Fig. 7 .

 7 Fig. 7. Velocities of the robot during the "follow-and-bypass" procedure.

TABLE I BYPASS

 I TIME IN DIFFERENT PARAMETER SETTINGS

The project VERVE stands for Novel Vehicle Dynamics Control Technique for Enhancing Active Safety and Range Extension of Intelligent Electric Vehicles.


Kun Jiang

Adina Pavelescu

Alessandro Victorino

Ali Charara

Estimation of vehicle's vertical and lateral tire forces considering road angle and road irregularity

Vehicle dynamics is an essential topic in development of safety driving systems. These complex and integrated control units require precise information about vehicle dynamics, especially, tire/road contact forces. Nevertheless, it is lacking an effective and low-cost sensor to measure them directly. Therefore, this study presents a new method to estimate these parameters by using observer technologies and low-cost sensors which are available on the passenger cars in real environment. In our previous work , observers have been designed to estimate the vehicle tire/road contact forces and sideslip angles. However, the previous study just considered the situation of the vehicles running on a level road. In our recent study, vehicle mathematical models are reconstructed to suit banked road and inclined road. Then, Kalman Filter is used to improve the estimation of vehicle dynamics. Finally, the estimator is tested both on simulation CALLAS and on the experimental vehicle DYNA.

I. INTRODUCTION

The advanced driver assistance system is designed to increase car safety and more generally road safety. Except for some passive safety systems, for example the seat belts, airbags, another approach proposed as active safety system can also effectively help avoid accidents. To prevent accidents actively, it is necessary to measure vehicle dynamics, which allow the assessment of the dangerousness of the driving situation. However, the states of vehicle dynamics such as the tire contact forces, sideslip angles are very difficult to measure directly. In addition, these sensors are very expensive or in-existent to install in ordinary cars. This leads to the need and effort given in the development of state observer applied to the estimation of these parameters. Vehicle dynamic estimation has been studied by many researchers. For example, in [START_REF] Shim | Understanding the limitations of different vehicle models for roll dynamics studies[END_REF], the vertical tire forces are calculated by a 14 Degree of Freedom vehicle model. More recently, the vertical and lateral forces at each tire have been estimated in [START_REF] Doumiati | An estimation process for vehicle wheelground contact normal forces[END_REF] and [START_REF] Moustapha | Embedded estimation of vehicle's vertical and lateral tire forces for behavior diagnosis on the road[END_REF]. However, these studies are under the hypothesis that the vehicle is running on a leveled road. In reality, the environment may include difficult features such as undulating terrain, and deformable surfaces. The main contribution of this study is to rebuild the vertical force estimators in order to take into account the roll angle, pitch angle and road angle. To evaluate the performance of our observers, the vehicle simulation software PROSPER/CALLAS [START_REF] Doumiati | An estimation process for vehicle wheelground contact normal forces[END_REF] is used. After the Chicane simulation tests, we have evaluated our new observer with the experimental vehicle DYNA, a Peugeot 308.

The authors are with Heudiasyc, CNRS UMR 7253, Université de Technologie de Compiègne, 60205, France. kun.jiang@hds.utc.fr, apaveles@etu.utc.fr, acorreau@hds.utc.fr, acharara@hds.utc.fr DYNA is equipped with sensors which are able to measure in real time the parameters used in the implementation of our observers as shown in the Figure 1. This paper is organized as follows. Section 2 presents the vehicle models that have been reconstructed. Section 3 describes how the observer is constructed. Then, experiment is conducted in Section 4. Finally, concluding remarks and future perspectives are given in Section 5.

II. VEHICLE MODELING

Many mathematical models have been proposed for the vehicle dynamics description. However, the analytical approach is limited to the existence of large numbers of components, subsystems. The embedded systems usually can't afford much computation ability. Thus, we need to simplify the vehicle modeling with reasonable assumption in order to find the mathematical solutions and satisfy our requirement of computational power. The vehicle dynamics models we used can be classified in three parts as shown in Figure 2. The study here is to propose a new vertical forces model, which considers roll angle, pitch angle and road irregularity. Then we have combined our vertical model with the existent lateral dynamics model [START_REF] Wang | State observers applied to vehicle lateral dynamics estimation: a comparison between Extended Kalman filter and Particle filter[END_REF] to build a new observer of vehicle dynamics, observing vertical and lateral tire forces.

A. Acceleration Measurement in dynamic situation

In the previous vertical force model, the wheel load shifts because of the acceleration variation [START_REF] Moustapha | Embedded estimation of vehicle's vertical and lateral tire forces for behavior diagnosis on the road[END_REF]. The model of vertical load distribution is shown as below:

F z11 = 1 2 m( L 2 L - axh gL )g -m( L 2 L - axh gL ) ayh E 1 ( 1
)
where L is the wheel base, L = L1 + L2, h is the height of center of gravity, E(1,2) are the vehicle's track(front,rear).

In the previous study, the car is considered as running on a level road so that the force of gravity acts only in the direction vertical to the vehicle. This assumption simplified the measuremetn of accelertaions.

In our recent study, we try to provide a general vertical force model that is suitable for all road geometry. We proposed to distinguish the accelerations caused by the vehicle's motion from the gravitational acceleration. In this way, the influences of the road angle and road irregularity are considered.

In irregular road situation, the measured accelerations contain two parts, one is caused by motion, a xmot , a ymot , a zmot , and the other is caused by gravity, a xgra , a ygra , a zgra .

To simplify the calculation of vertical forces, we can transform the irregular road situation into the equivalent level road situation. The equivalent accelerations are:

axequ = axmot + axgra ayequ = aymot + aygra azequ = -azmot + azgra (2)
Then according to the load transfer theory , the equation of vertical force is changed to:

F z11 = 1 2 m( L2 L - axequh azequL )azequ-m( L2 L - axequh azequL ) ayequh E1 (3)
The accelerometer measures directly the sum of accelerations caused by the vehicle's motion and by gravity. However, the measured quantity is influenced by the pitch and roll angle. The coordinate of accelerometer should be rotated to be parallel to the road.

As a result, the equivalent accelerations can be calculated by the measured accelerations as follow:

  a xequ a yequ a zequ   = R θ R φ   a xm a ym a zm   (4)
Where the rotation matrices are : After the rotation of the measured accelerations, we can transform the irregular road condition into the equivalent level road condition.

B. Roll and Pitch Dynamics

The equation ( 3) already provides a general mathematical model of vertical forces for all road geometry. However, the roll and pitch dynamics are not directly appeared in this model. The model doesn't consider the movement of suspension systems. In a dynamic driving situation, like braking, turning, or at irregular road, the suspension system will greatly change the vehicle dynamics.

In order to reduce the number of parameters in the model, we simplify the suspension system with a parallel spring and damper as shown in the Figure 4. We combine the suspension and tire into one system, in which Kr is the equivalent total rotational stiffness and Cr is the equivalent total damping coefficient.

Roll angle

Roll center

Pitch angle

Roll center

Fig. 4. Roll dynamics and pitch dynamics

Usually, the roll center changes according to the vehicle movement that defects on the suspension deflection, here we assumed that the vehicle roll center keeps constant and its distance with the center of gravity is noted as hs.According to the torque balance in the roll axis, the roll dynamics of the vehicle body can be described by the following differential equation:

I xx φv = -C r φv -K r φ v + m v h s a ym I yy θv = -C r θv -K r θ v + m v h s a xm (6)
Where I xx is the moment of inertia of the vehicle with respect to the roll axis, I yy is respect to the pitch axis and h s is the height of the sprung mass about the roll axis.

C. Roll and Pitch Angle Calculation

The roll angle can be calculated by integrating the roll rate measured by accelerometer. However, the sensor bias will also be integrated, which causes large calculation error. Hac [START_REF] Hac | Detection of vehicle rollover[END_REF] proposes a roll angle model expressed with suspension deflection, with which the pitch dynamics affection is decoupled from the roll motion. In this study, the roll angle and pitch angle is obtained via suspension deflection sensors.

φv = ∆ 11 -∆ 12 + ∆ 21 -∆ 22 2E , θv = ∆ 11 + ∆ 12 -∆ 21 -∆ 22 2(L 1 + L 2 ) +θs (7)
where ∆ ij is measured suspension deflection at each wheel of the vehicle and E denotes the effective track's width, θ s is the inclination angle at static state.

D. Vertical Forces Calculation

In the previous vertical force model, the load transfer is caused by the longitudinal and lateral accelerations. In our recent study, we suppose that the load transfer are regarded as caused by the torque of suspension systems.

In the case of roll movement, the torque of suspension is denoted as M φ .Then according to the torque balance, we have:

Fz1 + Fz2 = mvazequ Fz1L1 -Fz2L2 = M φ (8)
Where F zij (i, j = 1, 2) is the vertical force of each wheel, i = 1 means front axle, j = 1means left side.F z1 is the total vertical force of front axle.

In the case of pitch movement, the torque of suspension is denoted as M θ . In the same way, we have:

F z1 = F z11 + F z12 F z11 E 1 2 -F z12 E 1 2 = M θ ( F z1 F z1 +F z2 ) F z21 E 2 2 -F z12 E2 2 = M θ ( F z2 F z1 +F z2 ) (9)
In the moment with both pitch and roll movement, the torque of the suspension systems can be calculated by the following equations:

M φ = K r φ + C r φ M θ = K r θ + C r θ (10)
With all the equations above, vertical force at four wheels can be approximately formulated as:

F z11 = mvL2azequ 2L -L2(Krθ+Cr θ) LE1 + Krφ+Cr φ 2L -M θ M φ mvazrLE1 F z12 = mvL2azequ 2L + L2(Krθ+Cr θ) LE1 + Krφ+Cr φ 2L + M θ M φ mvazrLE1 F z21 = mvL1azequ 2L -L1(Krθ+Cr θ) LE2 -Krφ+Cr φ 2L + M θ M φ mvazrLE2 F z22 = mvL1azequ 2L + L1(Krθ+Cr θ) LE2 -Krφ+Cr φ 2L -M θ M φ mvazrLE2 (11)
In the final model equations, the pitch and roll angle are directly used to present the roll and pitch dynamics. It is more suitable to dynamic driving situations at irregular roads. However, it is limited due to the variation of certain parameters and assumptions that aimed at simplifying the model. Consequently, in the next section, the observer technique is introduced to improve the estimation.

III. OBSERVER DESIGN

The overall calculation process of the observer can be expressed by the Figure 5: The first block provides the vertical tire forces for the calculation of lateral dynamics in the second block, which is already realized in our previous work [START_REF] Wang | State observers applied to vehicle lateral dynamics estimation: a comparison between Extended Kalman filter and Particle filter[END_REF], [START_REF] Baffet | Experimental evaluation of observers for tire-road forces, sideslip angle and wheel cornering stiffness[END_REF], [START_REF] Baffet | An Observer of Tire-Road Forces and Friction for Active Security Vehicle Systems[END_REF]. Our study here is to modift the first block to improve the estimation of vertical forces.Then two block are combined to estimate the tire forces. With a linear model, the vertical forces are estimated with Kalman Filter shown as below.

A. Discrete-time State-space Representation

To build a Kalman Filter, the vertical force system has been represented by a set of discrete state-space equations:

x k = Ax k-1 + Bu k-1 + ω k-1 y k = Hx k + v k ( 12
)
Where A is the states evolution matrix, H is the observation matrix. and ω k v k are white noises. Here, the vehicle state vector X R 14 is defined as follows:

X = φ φ θ θ Fz11 Fz12 Fz21
The initial value of X is:

X 0 = 0 0 0 0 mvg 4 mvg 4 mvg 4 mvg 4 0 0 0 0 0 0 T ( 14
)
In addition, the following assumption is made äx = äym = äzr = 0. The continuous-time state equations are presented in equations (15). By discretizing the state equations we can obtain the evolution matrix A. And B=0. The observation model is linear and the output vector Y is presented as follows:

Ẋ =                                                          φ = φ φ = mv h Ixx ay -Cr Ixx φ -Kr Ixx φ θ = θ θ = mv h Iyy ax -Cr Iyy θ -Kr Iyy θ Ḟz11 = mv l 2 2l ȧzr -Kr θ+Cr θ E 1 + Kr φ+Cr φ l Ḟz12 = mv
Y = φ φ θ θ Fz11 Fz12 Fz21 Fz22 axr ayr azr T (16)
The elements in this vector are respectively provided by:

• φ, θ are calculated by equation ( 7):

• φ, θis measured by the accelerometer • a xm ,a ym ,a zm are measured directly from the accelerometer Therefore, the observer matrix H can be simply determined by

Y = H * X (17)
For our developed Kalman filter, the error measurement covariance is determined by the sensor variance, and the error model covariance is determined by the model quality.

Before applying the Kalman filter, we need to check observability of the system. Observability tells how well the internal states of a system can be inferred by the knowledge of the inputs and outputs. The observability matrix can be calculated by:

O = H HA HA 2 ... HA n-1 T (18)
In our case, the observability matrix has full rank 14, therefore our system is observable.

IV. EXPERIMENTAL VALIDATION

As we have introduced in the abstract, both simulation software and experimental cars are used to evaluate the performance of the new observer. The performance of the developed observers was characterized by the normalized mean. The normalized error is defined in Stephant [START_REF] Stéphant | Contribution à l'étude et à la validation expérimentale d'observateurs appliqués à la dynamique du véhicule[END_REF] as:

εz = 100 * |Z obs -Zmeasure| max(|Zmeasure|) (19)
where Z obs is the value calculate by the observer, Zmeasure is the measured value and (|Zmeasure|) is the absolute maximum value of the measured data.

The new observer is designed to have a better performance in both banked road and inclined road. The object of our experiments is to testify this improvement. Therefore, all our tests are conducted in the condition of non-zero road angle.

In the simulation part, two Chicane tests have been done. One Chicane test is done with banked road. The bank angle of the road is 30%. The other test is done with inclined road. The incline angle is 20%.The velocity of the vehicle is about 30 km/h. The lateral acceleration is around (-0.5 g, 0.5g). The test lasts for about 20 second. The trajectory of this test is shown in Figure 6: The normalized mean error of the vertical forces estimation is shown in Table 1: From the Table 1, we can see that the error of the new observer is less than 1%, while the previous observer has an error about 8%. In the new observer, we considered the component of gravity into the longitudinal dynamics, which makes the observer reliable even at inclined road.

B. Simulation of Chicane test at banked road

The following simulation is to evaluate our observer at banked road. The bank angle is set as 30%. The observed vertical forces from the observers are: In Figure 8, the red lines represent Callas simulation data. The red lines data shows that vertical forces of right wheels are generally bigger than those of left wheels. That is correspondent to the bank angle. However, in the previous observer,presented by black dashed lines, the bank angle is not considered, so its observed values at right and left wheels are very similar. In contrast, with our current observer, the estimated value are very satisfactory. To evaluate the performance of both observers more precisely, the normalized mean error of the estimation is calculated: From the Table 2, we can see that the new observer has also a good performance in banked road. These good results confirm that the presented algorithm is suitable for estimation of vertical forces in banked road and inclined road.

C. Experiments in real condition

After the validation of our observer by simulation, we use the experiment car to evaluate its performance in real condition.

During the test, the experiment car was conduit on the city roads near our research center. The test takes 450 seconds and the total distance is about 6 km. Globally, all the real data is approach to our estimation. However, to present our experimental results more clearly, we choose only 80 seconds of the experimental data to analyze. Figure 9 shows the experimental car's trajectory, altitude, steering wheel angle and speed during this period of 80 seconds. This data is chosen, because during the 80 seconds, the experimental car has experienced most driving situation we could meet in real condition. In the first 30 seconds, the car DYNA is climbing at the inclined road. Then it meets a sudden turning,as we can see in figure 9 in the trajectory of DYNA. After that, DYNA follows S-curve, which causes a sharp variation in steering wheel angle. The road condition is very complicated. To have correct estimation of vehicle dynamics requires the observer to maintain reliable regardless of the inclined road and banked road. The following figures show the results of our estimation.

The observed vertical forces from the observers are: The red lines represent the measured value. We can see the vertical forces has underwent big variation during the experiment. That is caused by the road angle and turning behavior of the vehicle. The blue lines represent the estimated values by new observer. The green lines represent the previous observer. We can see the estimated values by the new observer are very close to the true value, which could validate our new vertical force model.

To evaluate the performance more precisely, the normalized mean error of the observer output is: With the observer structure shown in Figure 5, besides the vertical forces, our observer could also estimate lateral forces. Since the vertical forces estimation at banked road is improved, the observer of lateral forces is supposed to also have a good performance at banked road. To justify this suppose, we also measured the values of lateral forces in the real tests to evaluate the observer. The observed lateral forces from the observers are in the Figure 11: The estimated values of lateral forces are also very close to the reference data. The normalized mean error of the observer output is: Several critical tests are performed to compare and validate our new algorithm, The observer gives convenient results even when the car follows a S-curve on the inclined road.

However, the new observer works only when the vehicle physic parameters are already known and remain constant. Actually, some parameters considered as constant are changing during the driving process. To improve the precision of the observer, we should know exactly the physic parameters of vehicle, like position of center of gravity, the corning stiffness, the suspension stiffness and so on. Future study will be concentrated at the estimation of these vehicle physic parameters.

Fig. 1 .

 1 Fig. 1. Experimental vehicle: DYNA

Fig. 2 .

 2 Fig. 2. Structure of complete vehicle model

Fig. 3 .

 3 Fig. 3. Vertical load distribution

  θ v and φ v are the pitch angle and roll of the vehicle chassis. a xm a ym a zm are the measured accelerations by the accelerometer installed at the chassis.

Fig. 5 .

 5 Fig. 5. Observer structure

l 2 2l ȧzr + Kr θ+Cr θ E 1 +

 1 Kr

Fig. 6 .

 6 Fig. 6. Vehicle trajectory and acceleration

Fig. 7 .

 7 Fig. 7. Vertical Forces Estimation of each wheel at inclined road

Fig. 8 .

 8 Fig. 8. Vertical Forces Estimation of each wheel at banked road

Fig. 9 .

 9 Fig. 9. Trajectory and altitude of experiment car during test

Fig. 10 .

 10 Fig. 10. Vertical Forces Estimation of each wheel in real road experiment

Fig. 11 .

 11 Fig. 11. Lateral Forces Estimation of each wheel in real road experiment

  Fz22 axr ȧxr ayr ȧyr azr ȧzr

	T

  This paper has presented a new model to estimate vertical tire forces. By distinguishing the acceleration caused by gravity and movement, the model can take in account the road angle and road irregularity. And in contrast to the previous model, the current model has considered the pitch dynamics and roll dynamics of the suspension. In conclusion, in our renovated model, pitch and roll dynamics and road disturbance are considered. Then combined with the lateral forces model in previous work and Kalman filter, we have developed observers to estimate the vertical and lateral tire forces of vehicle. Experiments have been made by both simulation software and real experimental car. Experimental results are presented to evaluate the performance of the new observer.

					V. CONCLUSIONS AND PROSPECTS
		TABLE IV
	LATERAL FORCES ESTIMATION IN REAL CONDITION
	Error (%)	Fy11	Fy11 Fy11	Fy11
	Current Observer	6.04	6.69	6.10	6.31
	PreviousObserver	6.05	6.72	6.21	6.42


Björn Þór Jónsson

Laurent Amsaleg
email: laurent.amsaleg@irisa.fr

Herwig Lejsek
email: herwig@videntifier.com

SSD Technology Enables Dynamic Maintenance of Persistent High-Dimensional Indexes

Keywords: High-dimensional index, Index maintenance, SSDs, NV-tree

In today's world of ever-increasing multimedia collections, dynamically and persistently maintaining high-dimensional indexes is imperative for industrial applications. Since HDD performance is the main bottleneck in index maintenance, we investigate the impact of SSD technology. We use the NV-tree to drive our analysis, as the only high-dimensional index in the literature which has seriously addressed updates. Our simulation model indicates that an index of 1.5 billion descriptors can be built dynamically on a high-end SSD in just over four hours of disk time, which is more than 500x faster than using a high-end HDD. Relatively small investment in the new SSD technology can thus make dynamic and persistent high-dimensional indexes very feasible.

INTRODUCTION

Multimedia collections are getting increasingly large. As a result, there has been significant interest in the scalability of k-NN search [START_REF] Liu | Clustering billions of images with large scale nearest neighbor search[END_REF][START_REF] Douze | Evaluation of GIST descriptors for web-scale image search[END_REF][START_REF] Lejsek | NV-Tree: An efficient disk-based index for approximate search in very large high-dimensional collections[END_REF][START_REF] Jégou | Product quantization for nearest neighbor search[END_REF][START_REF] Lejsek | NV-Tree: nearest neighbors at the billion scale[END_REF][START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF][START_REF] Sun | Indexing billions of images for sketch-based retrieval[END_REF]. But nearly all of this work has ignored the effect of the growth of the collections, effectively ignoring the need to perform updates on the collection and the resulting index structure.

A prototypical multimedia retrieval system works as follows: First, each media item is described using one or more high-dimensional features. For large-scale collections, the resulting feature collection is much too large to fit in main memory and must be made persistent on disk. Then the high-dimensional features are somehow compressed into a smaller representation, sometimes only a few bytes, and inserted into an indexing structure for efficient searches. In some cases, the final representation of the features may depend on the index and thus vary based on, for example, the distribution in the high-dimensional space.

In an industry setting with specific response time requirements, it is necessary to maintain a persistent index of the Figure 1: Performance comparison of a high-end HDD (600 GB, $360) and a high-end SSD (400 GB, $900). The y-axis (truncated) shows the time for each of the operations on the x-axis, in milliseconds. The numbers show that SSDs are faster than HDDs by a factor of 5x to 1000x, depending on operation and data quantity. See Section 2.5 for more details. entire collection. For example, it is not acceptable to keep a list of the newly added features, which is scanned sequentially in addition to searching the high-dimensional index, and then re-index the entire collection offline once in a while. First, the list of new features will grow steadily and with it the retrieval time, so performance will quickly become unacceptable. Second, full re-indexing will be a very timeand resource-consuming process, which cannot be done frequently. Furthermore, in case of crashes, the persistent index allows resuming the service immediately. The only way to achieve industry-standard service levels is to maintain a dynamic and persistent high-dimensional index!

Costs of Index Maintenance

In the short term, new features may be accommodated by inserting them into the appropriate index cell of the existing structure. While standard logging techniques can be used to reduce cost, the changes must eventually be made persistent on disk. When the index fits in memory, a single write suffices; otherwise it may be necessary to read the corresponding cell from disk and then write it back. Reading and writing single cells results in random disk operations, which are costly using traditional hard-disk drives (HDDs).

In the long term, inserting into existing cells leads to excessively large cells which can negatively impact both retrieval time and result quality. Index structure maintenance will therefore be required in order to split these cells and redistribute their contents. And again, those changes must be made persistent leading to disk reads and writes.

If the final representation of features depends on the index structure, further costs are incurred as the original features must be retrieved to compute a new representation against the modified index. Since the feature collection on disk is not aligned with the index, the original features of a single cell can be located anywhere in the feature collection and unlikely in close proximity to each other. Therefore, reading the features from disk can be a costly process of multiple random disk reads. This is particularly true with traditional HDDs which do not support small random reads well.

Recently, however, solid-state disks (SSDs) have appeared which have very different characteristics, as Figure 1 clearly demonstrates (see Section 2.5 for details of the figure). First, because they have no moving parts they are much faster than HDDs (particularly high-end SSDs). Second, again since they have no moving parts, the size of the IO impacts the performance much more than with HDDs, which in turn means that random reads become quite efficient, and in particular small random reads become very efficient. It is therefore of interest to observe the impact of SSDs on update performance of high-dimensional indexes.

Contributions

One of the most scalable high-dimensional indexing methods in the literature is the NV-tree [START_REF] Lejsek | NV-Tree: An efficient disk-based index for approximate search in very large high-dimensional collections[END_REF][START_REF] Lejsek | NV-Tree: nearest neighbors at the billion scale[END_REF]. It has been used for large-scale experiments and is currently the backbone of a professional copy-detection service indexing more than 150 thousand hours of video. It is also the only scalable high-dimensional index in the literature, as far as we know, where update performance has been seriously studied [START_REF] Lejsek | NV-Tree: An efficient disk-based index for approximate search in very large high-dimensional collections[END_REF][START_REF] Ólafsson | Dynamic behavior of balanced NV-trees[END_REF]. We therefore use the NV-tree as the vehicle of our study.

In this paper we make the following contributions. We first review the NV-tree and identify the impact points of SSD technology on the performance of persistent and dynamic index maintenance. We then present simulation results which show that using a high-end SSD enables the insertion of 1.5 billion high-dimensional descriptors in just over four hours of disk time, which is more than 500x faster than using HDD technology. Moreover, the results show that for the NV-tree in particular, SSD technology allows a much simpler implementation of index maintenance than HDD technology, again due to its performance characteristics. We conclude that by using SSD technology, it is now very feasible to dynamically and persistently maintain highdimensional indexes at a large scale.

THE NV-TREE

Overall, an NV-tree is a tree index consisting of: a) a hierarchy of small inner nodes, which are kept in memory during query processing and guide the vector search to the appropriate leaf node; and b) larger leaf nodes, which are stored on disk and contain references to the actual features. In this section, we give describe the algorithms of the NVtree for index construction, retrieval and maintenance. This description is brief and simplified; refer to [START_REF] Lejsek | NV-Tree: nearest neighbors at the billion scale[END_REF] for details.

Index Creation

When the tree construction starts, all features from the collection are first projected onto a single projection line through the high-dimensional space. The projected values are then partitioned based on their position on the projection line, thus partitioning the root node of the tree. To build subsequent levels of the NV-tree, this process of projecting and partitioning is repeated for each and every partition using a new projection line at each level, thus creating the hierarchy of partitions that are represented by inner nodes. The process stops when the number of vectors in a partition falls below a limit designed to be disk I/O friendly. A new projection line is then used to order the vector identifiers in each final partition and the ordered identifiers are written to the leaf node on disk. Each feature is represented by a 4 byte identifier and, since the leaves are on average about 2/3 full, a total of 6 bytes are required per feature.

Two partitioning strategies co-exist inside the NV-tree. The first partitioning strategy is such that the distance between partition boundaries at each level of the tree is equal. As the inner products between a set of high-dimensional vectors and a projection line typically form a normal distribution, the resulting partitions usually have very different cardinalities and dense areas are partitioned deeper than sparse areas. This first partitioning strategy is used at the upper levels of the NV-tree. The second partitioning strategy is used at the lowest levels of the tree: when a partition fits into a disk I/O, then data is partitioned according to an equal cardinality criterion (instead of an equal distance criterion). This switch to balanced partitioning occurs when a partition fit within 6 × 6 leaves, creating balanced leaf groups of up to 6 nodes containing up to 6 leaves each. The goal of this latter partitioning strategy is to enable efficient search in nearby leaves, as described below.

Nearest Neighbor Retrieval

The search first traverses the hierarchy of inner nodes of the NV-tree. At each level of the tree, the query vector is projected to the projection line associated with the current node. The search is then directed to the sub-partition with center-point closest to the projection of the query vector. This process of projection and choosing the right subpartition is repeated until the search reaches a leaf group.

At each level of the leaf-group, the two nearest branches are considered, or up to four leaves, and the nearest vectors along the projection lines are merged to form the final set of approximate nearest neighbors. As only two adjacent leaves are read at each level, at most four leaves will be read with this method. As these leaves are organized together on disk, they will span at most 12 pages, and can thus (with high likelihood) be read in a single disk read.

Index Maintenance

Insertion to NV-tree leaves proceeds as follows. When the correct leaf node is found, using the exact same process as during search, the position within the leaf node is calculated and the identifier is inserted in the designated position. During index creation, leaf nodes are not filled completely in order to leave space for such insertions. Once a leaf node is filled, however, it must be split in order to provide more storage capacity within the tree.

A basic method to split a node is very similar to the index construction process. A new internal node is created with two new leaf nodes as children. A projection line is then assigned to the internal node using the same method as during index construction. The contents of the full leaf node are projected along the projection line and inserted to the appropriate leaf. Each leaf is then also assigned a projection line and the contents of the leaf ordered based on the projection to that line.

Using this basic method, however, the index would quickly become very deep, as each leaf would always be split into two leaves and all the new internal nodes would have only two children. A better method is to consider a group of l leaves together, and re-distribute their contents to l + ∆ leaves. The NV-tree goes one step further, and considers the leaf groups described above as the unit of splits; when that group exceeds 6 × 6 = 36 leaves, the group is split into 4 to 8 new leaf groups, depending on the distribution of the high-dimensional vectors in the original leaf group.

Re-Projection of Features

In order to project the contents of a filled leaf group, it is necessary to use the original features, as a) a new projection line is (most likely) chosen for the internal nodes, and b) each new leaf also has a new projection line. Leaf nodes only contain feature identifiers, so the features themselves must be retrieved from disk. The features of the leaf group are randomly distributed over the whole feature collection, however, so their retrieval is a costly operation.

Three methods can be used to retrieve the features of a leaf group from the feature collection. First, it is possible to sequentially scan the entire collection. Second, it is possible to randomly read only the required features. Both are simple to implement, but neither is efficient using HDDs: the first methods reads too much data, while the second requires expensive random accesses.

A third method, proposed in [START_REF] Ólafsson | Dynamic behavior of balanced NV-trees[END_REF], is to maintain an independent feature database for each NV-tree-called partition files-which is organized in the same manner as the leaf groups. With this last method, only a small number of sequential disk reads are required to retrieve the features of the leaf group. When using HDDs, this method has been shown to be the most efficient [START_REF] Ólafsson | Dynamic behavior of balanced NV-trees[END_REF], even though the redundant partition files must also be maintained during splits.

Expected Impact of SSDs

As mentioned above, Figure 1 compares two high-end disks from each category: HDD and SSD. Prices are obtained from allhdd.com and amazon.com, respectively. The performance of the SSD is obtained with actual performance measurements using the fio benchmark. The performance of the HDD, on the other hand, is extrapolated from [START_REF]All enterprise HDD charts[END_REF] as follows: the average sequential throughput is used directly to calculate the cost of sequential operations and read/write access times is used as the cost of random operations. Based on Figure 1, we make the following observations:

• For the HDD, sequential operations are ∼10x faster than random operations. Random writes are faster than random reads due to buffering, as the disk buffers writes temporarily to improve performance. Small operations (not shown) take roughly the same time as larger operations. • The SSD, in contrast, shows no difference between random and sequential operations. Reads are twice as fast as writes, due to properties of the storage medium.

• For the SSD, small operations are ∼10x faster than large operations, due to the absence of movable parts. • Overall, the SSD is 5-10x faster than the HDD for sequential operations and 10-100x faster for random operations. • For small disk reads, however, the SSD is ∼1000x faster than the HDD. This is particularly beneficial for the re-projection of features during splits.

Overall, the expected impact of using SSDs on NV-tree maintenance is two-fold. First, due to the overall performance improvement, we expect the index maintenance to be significantly faster, making it feasible to dynamically maintain persistent indexes. Second, due to the capacity for very fast small random reads, we expect that reading the features to re-project randomly from the large collection will be more efficient than maintaining the redundant feature database.

PERFORMANCE EVALUATION

In this section, we study the performance of NV-tree maintenance with both HDD and SSD technology. We first describe our simulation model, which is similar to the one in [START_REF] Ólafsson | Dynamic behavior of balanced NV-trees[END_REF], and then present the results.

Modeling NV-tree Maintenance

Assume that the feature collection consists of NF features in SF blocks of 128 KB. We assume each feature is 132 bytes (128 dimensions) and that the NV-tree requires 6 bytes per feature. The NV-tree consists of NL leaves organized into NG leaf groups. Each leaf is at most 4 KB, so each leaf group is at most 36 × 4 = 144 KB. We assume that each leaf-group is stored in a contiguous chunk of space on disk and can be read or written with a single IO operation.

If partition files are maintained, there are also NG partition files. The size of the partition file depends on the number of features it stores but overall, partition files are about 20 times larger than leaves. Since they also can be organized in a contiguous manner, reading or writing a partition file requires a number of sequential operations.

At insertion time, a system buffer is maintained which is organized the same way as the NV-tree. This system buffer contains feature identifiers and projected values, and in the case of partition files, also the feature itself. If the buffer fills up, it is flushed by sequentially reading all partitions and writing out with the added feature identifiers. For each partition file represented in the buffers, the end of the partition file is read, appended to and written again.

When a leaf is split, one random read is first performed to read the leaf group. The cost of a random read of a leaf group is termed C L RR and given in Figure 1; we assume that each such read is 128 KB. Then a random write of the leaf group is required to persist the change (C L RW ). When the entire leaf group is full and is split into four leaf groups, the writing phase consists of four leaf-group sized random writes (4C L RW ). Note that when a partition is split, its features are removed from the buffers. If partition files are maintained, similar operations must be performed; since partition files are about 20 times larger, however, the costs are higher.

The cost of re-projection of features during split of a leaf group G depends on the method used. As described in the previous section, there are three alternatives which we explore: The first alternative is that of sequentially scanning then entire collection of features; this costs SF × C L SR . The second alternative is to retrieve all the features from the feature collection; this costs SGC F RR , where C F RR is the cost of a small random read and SG is the number of features in the leaf group. Finally, if partition files are maintained, they can be read, which costs between C L SR and 20C L SR , depending on the size of the given partition file.

Initially, the NV-tree consists of 50 million descriptors. A total of 1.5 billion descriptors are then inserted, one by one, keeping track of the total elapsed time, as measured by the estimated IO time.

Simulation Results

Figure 2 shows the total elapsed time for both the HDD and the SSD from Figure 1. Let us focus first on the HDD (solid lines). As expected, the figure shows that scanning the collection (red) is the slowest method, while maintaining the partition files (yellow) is faster than reading individual features (green). Note that even though the reduced cost of reading partition files during leaf splits is partially offset by the cost of maintaining them during leaf-group splits, the maintenance cost is much smaller than the time savings. In total, however, inserting the 1.5 billion descriptors requires more than 2,000 hours of disk time, which is infeasible.

Turning to the SSD performance in Figure 2 (dashed lines) we first observe that the maintenance time is significantly reduced compared to the HDD. In fact, for both full collection scan (red) and partition file scan (yellow), which are dominated by large sequential reads, the SSD is more than 10x faster, as sequential reads are ∼10x faster with the SSD. Reading the individual features (green), however, which is dominated by small random reads, is more than 1000x faster. Again, this is as expected, as the SSD is ∼1000x faster for such reads. The most efficient method using the SSDreading individual features-takes just over 4 hours, which is more than 500x faster than using partition files on the HDD. Four hours of disk time for 1.5 billion descriptors is very feasible, even in demanding industry settings.

CONCLUSIONS

We have argued that the performance of high-dimensional index maintenance is a very worthy subject of investigation in today's world of large-scale and ever-increasing multimedia collections: in order to offer industry-strength solutions with reliable retrieval performance, it is necessary to maintain a dynamic and persistent copy of the high-dimensional index on disk. Since HDD performance is the bottleneck in such index maintenance, we have investigated the impact of SSD technology on the implementation of index maintenance. We have used the NV-tree to drive our analysis, as it is the only high-dimensional index in the literature which has seriously addressed updates.

Our results show that using SSD technology 1.5 billion can be inserted into the index in a matter of just over four hours. Furthermore, while a redundant copy of the entire feature collection was needed when using HDDs, a straightforward method of reading the required features randomly is by far the best solution using SSDs. These results mean that a very modest investment in the new SSD technology can simplify index maintenance and allow the dynamic and persistent maintenance of even large-scale high-dimensional indexes.

Figure 2 :

 2 Figure2: A comparison of total elapsed disk time for index maintenance using the high-end HDD (solid lines) and high-end SSD (dashed lines).

ACKNOWLEDGMENTS

The authors wish to cordially thank Philippe Bonnet, Ivan Luiz Picoli, Max Enroth and Carla Villegas Pasco of the IT University of Copenhagen for their performance measurements of the Intel P3700 SSD card and related discussions.