Stefano Mafrica
email: stefano.mafrica@univ-amu.fr

Alain Servel
email: alain.servel@mpsa.com

Franck Ruffier
email: franck.ruffier@univ-amu.fr

Towards an Automatic Parking System using Bio-Inspired 1-D Optical Flow Sensors

, car manufacturers are still looking for low-cost sensors providing redundant information about the obstacles around the vehicle, as well as efficient methods of processing this information, in the hope of achieving a very high level of robustness. We therefore investigated how Local Motion Sensors (LMSs) [13],

[14], comprising only of a few pixels giving 1-D optical flow (OF) measurements could be used to improve automatic parking maneuvers. For this purpose, we developed a low computationalcost method of detecting and tracking a parking spot in real time using 1-D OF measurements around the vehicle as well as the vehicle's longitudinal velocity and steering angle. The algorithm used was composed of 5 processing steps, which will be described here in detail. In this initial report, we will first present some results obtained in a highly simplified 2-D parking simulation performed using Matlab/Simulink software, before giving some preliminary experimental results obtained with the first step in the algorithm in the case of a vehicle equipped with two 6pixel LMSs. The results of the closed-loop simulation show that up to a certain noise level, the simulated vehicle detected and tracked the parking-spot assessment in real time. The preliminary experimental results show that the average refresh frequency obtained with the LMSs was about 2-3 times higher than that obtained with standard ultrasonic sensors and cameras, and that these LMSs therefore constitute a promising alternative basis for designing new automatic parking systems.

I. INTRODUCTION

Since the pioneering works by Paromtchik et al. [START_REF] Paromtchik | Autonomous parallel parking of a nonholonomic vehicle[END_REF] and the first commercial Intelligent Parking Assist System (IPAS) [START_REF] Hiramatsu | Rearview camera based parking assist system with voice guidance[END_REF], a large range of (semi-) automatic parking methods have been developed over the years using all kinds of sensors, from ultrasonic sensors [START_REF] Degerman | Hough transform for parking space estimation using long range ultrasonic sensors[END_REF]- [START_REF] Hsu | Development of an automatic parking system for vehicle[END_REF] to cameras [START_REF] Fintzel | 3D parking assistant system[END_REF]- [START_REF] S.-E. Shih | A Convenient Vision-Based System for Automatic Detection of Parking Spaces in Indoor Parking Lots Using Wide-Angle Cameras[END_REF], laser scanners [START_REF] Montemerlo | Junior: The Stanford Entry in the Urban Challenge[END_REF], [START_REF] Jeevan | Realizing Autonomous Valet Parking with automotive grade sensors[END_REF], and radar systems [START_REF] Gorner | Parking lot detection with 24 ghz radar sensor[END_REF], [START_REF] Jung | Scanning laser radar-based target position designation for parking aid system[END_REF].

On the one hand, high-performance automatic parking systems require costly sensors, such as laser scanners [START_REF] Montemerlo | Junior: The Stanford Entry in the Urban Challenge[END_REF], [START_REF] Jeevan | Realizing Autonomous Valet Parking with automotive grade sensors[END_REF] and radars [START_REF] Gorner | Parking lot detection with 24 ghz radar sensor[END_REF], [START_REF] Jung | Scanning laser radar-based target position designation for parking aid system[END_REF] and large computational resources to reconstruct the surrounding 3-D environment in real time during parking maneuvers.

On the other hand, most of the (semi-) automatic parking pilots available on the market involve the use of ultrasonic sensors and rear-view cameras [START_REF] Hsu | Development of an automatic parking system for vehicle[END_REF], [START_REF] Suhr | Automatic free parking space detection by using motion stereo-based 3D reconstruction[END_REF], [START_REF]Peugeot -park assist[END_REF]- [START_REF]Toyota -intelligent park assist[END_REF] to detect This work was supported by CNRS Institutes (Life Science; Information and Engineering Science and Technology), Aix-Marseille University, ANRT (Association Nationale de la Recherche et de la Technologie), PSA Peugeot Citroën via the OpenLab agreement entitled "Automotive Motion Lab". a free parking spot while the driver is driving along a row of parked vehicles and to autonomously control the steering system by estimating the vehicle's ego-position via odometry.

To improve IPAS systems, recent research works and industrial developments using Around View Monitor Systems (AVMSs) have been proposed [START_REF] S.-E. Shih | A Convenient Vision-Based System for Automatic Detection of Parking Spaces in Indoor Parking Lots Using Wide-Angle Cameras[END_REF], [START_REF]Nissan -around view monitor system[END_REF], [START_REF]Bmw -surround view system[END_REF]. AVMSs mainly use wide-angle cameras (such as fish-eye and catadioptric cameras) directed toward the ground, giving a view of the surrounding environment, to detect and track parking-spots' ground marks during parking maneuvers.

However, the autonomous vehicles of the future will require more accurate redundant information than that provided by the systems currently available on the market, mainly because of (i) the narrow field of view (FOV) and the short distance range of the ultrasonic sensors used and (ii) the low luminosity range and the low sampling frequency of standard cameras.

As far as we know, the challenge for designing the IPASs of future autonomous vehicles consists in finding low-cost, fastresponse sensors providing redundant information about the obstacles present around the vehicle, combined with a sensordata processing system requiring very low computational resources.

We therefore investigated how Local Motion Sensors (LMSs) [START_REF] Sabiron | Lowspeed optic-flow sensor onboard an unmanned helicopter flying outside over fields[END_REF], [START_REF] Expert | Flying over uneven moving terrain based on optic-flow cues without any need for reference frames or accelerometers[END_REF], giving 1-D optical flow (OF) measurements using methods based on findings obtained on the fly's visual system [START_REF] Franceschini | Facets of vision[END_REF] could be used to improve automatic parking maneuvers.

Thanks to their wide luminosity range and their sensitivity to small contrasts [START_REF] Expert | Flying over uneven moving terrain based on optic-flow cues without any need for reference frames or accelerometers[END_REF], [START_REF] Mafrica | A Bio-Inspired Analog Silicon Retina with Michaelis-Menten Auto-Adaptive Pixels Sensitive to Small and Large Changes in Light[END_REF], LMSs comprising only a few autoadaptive pixels seem to constitute a promising alternative to standard cameras in situations where the lighting conditions are highly variable and the visual patterns created by the vehicle's body, for example, show small contrasts. In addition, an array of LMSs would have the following advantages with respect to ultrasonic sensors and cameras: (i) faster responses (up to 200 Hz); (ii) a custom FOV (such as 180 o ); (iii) a longer distance range than ultrasonic sensors; (iv) less computational cost than cameras.

In this paper, we present the first results toward developing a low computational-cost method of performing automatic parking maneuvers whereby a parking spot can be detected and tracked in real time based on a visual motion sensor setup performing 1-D OF measurements around the vehicle. The algorithm used for this purpose was composed of 5 processing steps, as described in Sec. IV.

As proof of concept, some results obtained in a simplified 2-D parking simulation implemented in Matlab/Simulink in closed loop will first be presented. Then, to report on the work in progress, we will give some preliminary experimental results corresponding to the first step in the algorithm in the case of a vehicle equipped with two 6-pixel LMSs on a vehicle.

In Sec. II, the principles underlying an elementary LMS and the visual-sensor setup used in the simulation will be described. In Sec. III, the point and line motion model used will be presented. In Sec.IV, the various steps in the algorithm we developed will be outlined. In Sec. V and VI, we will present and discuss the results of some simulations and preliminary outdoor experiments. Some conclusions will be reached in the last section.

II. LOCAL MOTION SENSORS FOR PARKING MANEUVERS

Figure 1 shows the principles underlying a 2-pixel LMS [START_REF] Ruffier | Bio-inspired optical flow circuits for the visual guidance of micro air vehicles[END_REF] and a photo of a 6-pixel LMS [START_REF] Sabiron | Lowspeed optic-flow sensor onboard an unmanned helicopter flying outside over fields[END_REF]. , where ∆ϕ is the interreceptor angle and τ is the time lag between the two photoreceptors' output signals [START_REF] Ruffier | Bio-inspired optical flow circuits for the visual guidance of micro air vehicles[END_REF]. (b) Photo of a 6-pixel LMS. (Adapted from [START_REF] Sabiron | Lowspeed optic-flow sensor onboard an unmanned helicopter flying outside over fields[END_REF]).

A defocused lens placed in front of 2 photoreceptors determines the interreceptor angle ∆ϕ between the 2 photoreceptors' axes and gives them a Gaussian angular sensitivity, on similar lines to what occurs in many insects' eyes. The width of the angular sensitivity determines the photoreceptors' FOV.

A visual contrast moving in front of the LMS will induce a time lag τ between the photoreceptors' output signals. By measuring this time lag, the optical flow can be computed as follows: ω(t) = ∆ϕ τ (t) [START_REF] Ruffier | Bio-inspired optical flow circuits for the visual guidance of micro air vehicles[END_REF]. Let us take the case where one N -pixel LMS is installed at each of the four corners of the vehicle, giving up to 4(N -1) 1-D OF measurements all round the car. In order to obtain a 180 o FOV of each LMS, N is taken to be such that N ×∆ϕ = 180 o , where ∆ϕ is the interreceptor angle, as shown in Fig. 1. As it is difficult in practice to obtain a 180 o FOV with just one lens, there could be M N -pixel LMSs, so that M ×N ×∆ϕ = 180 o .

Figure 2 gives a diagram of the visual-motion sensor setup on a vehicle, in the case where 4 neighboring visual signals give 3 1-D OF measurements.

If the environment is relatively smooth, i.e. there are only small variations in the distance between the visual patterns and the LMS in the photoreceptors' FOV, we can assume that the photoreceptors will detect visual points on their axes instead of patterns in their FOV. When an OF measurement ω i is delivered at the time t, this will therefore be just as if a visual point has moved from the i -1-th to the i-th photoreceptor's axis, and this point is now (at t = t) on the i-th axis. In this preliminary study, we assumed that the neighboring visual points detected formed straight lines corresponding to the simplified 2-D profiles of the surrounding parked vehicles.

III. POINT AND LINE MOTION MODELING

As the vehicle's velocity is relatively low during parking maneuvers, we focused here on the 2-D kinematic model for a car-like vehicle moving on a plane. According to Fig. 3 and the Ackermann steering geometry for car-like vehicles, the equations for a point P moving on the same plane as the vehicle can be written as follows:

ẋi ẏi = f P (x i , u) = (yi+ys) tan φ-L L V f + V P x -(xi+xs) tan φ L V f + V P y (1)
ω i = x i ẏi -y i ẋi x 2 i + y 2 i ( 2
)
where u = [V f φ] T are the vehicle's longitudinal velocity and its steering angle, respectively; L is the distance between the rear and front wheel axes; B x s = [x s y s ] T is the position vector of the 1-D OF sensor with respect to the body frame < B >;

B x P = [x P y P ] T , B x i = [x i y i ]
T are the position vectors of the point P with respect to the body frame < B > and the sensor frame < s >, respectively; B V P = [V P x V P y ] T is the velocity vector of P with respect to the inertial frame < I >; and ω i is the angular velocity of P with respect to < s >, i.e. the OF measured between the i-th and i -1-th pixel of the sensor (see Sec. II). Note that the sensor frame < s > is parallel to the body frame < B > (i.e. the rotation matrix between the two frames is the identity matrix), and the upper left index B indicates that the vectors are projected onto the body frame < B >. For the sake of simplicity, this index will be dropped in what follows.

As P must lie on the i-th pixel's axis (see Sec. II), its coordinates x i , y i must satisfy the following equation:

sin ψ i x i -cos ψ i y i = 0, (3)
where ψ i is the orientation of the i-th pixel's axis, i.e. the angle known to exist between B x i and the x-axis of < s >.

A straight line in the body frame < B > can be described by the following equation:

x l x + y l y = x 2 l + y 2 l , (4)
where B x l = [x l y l ] T is the position vector perpendicular to the line l projected onto the body frame < B >.

If the line l does not move with respect to the inertial frame < I >, we can assume that l is located on the X-axis of < I >. In this case, in line with Fig. 3, the following equations hold:

  ẋl ẏl θ   = f l (x l , u) =     y l tan φ L -sin 2 θ V f -x l tan φ L -sin θ cos θ V f tan φ L V f     , ( 5
)
where θ is the angle between the X-axis of < I > and the x-axis of < B >.

IV. PARKING-SPOT DETECTION AND TRACKING

The algorithm presented here (see Figure 4 ) first computes the positions of the points detected by the LMSs using only 1-D OF measurements and the vehicle's velocity and steering angle (Step 1), and it then looks for straight lines in the clouds of points using the RANSAC method [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF] (Step 2). These lines are then classified by Naive Bayes Classifiers (NBCs) (Step 3) to ensure a geometrical coherence with respect to the simplified parking-spot geometry. Lastly, the vectors perpendicular to the parking lines and the intersection points between these lines are estimated by means of Extended Kalman Filters (EKFs) (Steps 4 and 5). A nonlinear tracking control is eventually performed based on the estimation of the vehicle's ego-position with respect to the parking lines and corners, but we will not focus on this process here.

Step 2: Find lines (RANSAC)

Step 3: Classify Lines (NBCs)

Step 4: Estimate Lines (EKFs)

Step 5 shows an example of the results obtained in each step in the algorithm at one sampling interval during the simulation. This example involves the case of perpendicular parking, but the present algorithm can be applied to the case of parallel parking as well without making any changes.

In the simulated 2-D parking environment, the parked vehicles were simulated in the form of rectangular shapes (Fig. 5(a)) and the OF measurements of the LMSs were computed analytically as the angular velocity of the points of intersection between the lines simulating the parked vehicles and the pixels' axes. A white Gaussian noise (n) with the standard deviation σ n is added to the positions of the intersections in order to obtain a non-linear noise in the OF measurements, which resembles the real sensors' noise more closely.

Step 1 -Computing 2-D Points:

Let us now assume that the point P in Fig. 3 does not move with respect to < I > or that its velocity components (V P x , V P y ) are negligible with respect to the visual motion induced by the vehicle's motion, so that we can take V P ≈ 0.

If we know the vehicle's longitudinal velocity and its steering angle (V f , φ), it is possible by combining equation ( 1), ( 2) and (3) to compute the P coordinates as follows 1 :

ψ i = ± π 2 : x i = V f (L tan ψi-xs tan φ-ys tan ψi tan φ) (tan 2 ψi+1)(Lωi+V f tan φ) y i = x i tan ψ i ( 6a
)
ψ i = ± π 2 : x i = 0 y i = V f (L-ys tan φ) Lωi+V f tan φ (6b)
Figure 5(b) gives the cloud of points computed at one sampling interval during the simulation.

Step 2 -Finding Lines:

To detect a parking spot, first we want to find four straight lines fitting some subsets of the cloud of points obtained in Step 1. Then, to validate this spot, these four lines must satisfy two main conditions: they must be nearly perpendicular two by two, and the distance between the two lines in the two pairs of parallel lines must be greater than the vehicle's width and its length, respectively (see Fig. 5(a)). The validation procedure may depend on the specific parking environment (e.g. on whether it is parallel or perpendicular) and require some information from other sensors, and this part will therefore not be discussed here as it goes beyond the scope of this paper.

To look for more than one regression line in a cloud of points, we have to perform some linear clustering in order to obtain subsets containing only one line each.

In this study, we used a modified version of the RANdom SAmple Consensus (RANSAC) method [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF], as it provides outliers in a statistically robust way, giving a good compromise between the level of performance and the computational cost with subsets which may be dependent but are not very numerous and are clearly separated linearly (as in the case of the 4 parking lines dealt with here). As previously done in many vision-based applications such as those designed for motion segmentation [START_REF] Vidal | Subspace Clustering[END_REF], the generic RANSAC algorithm is applied recursively to the subset of outliers, i.e., to all the points that do not belong to the consensus set, and whenever a line is detected, it yields the position vector xl = [x l ỹl ] T satisfying equation ( 4). The recursion is stopped when either four lines are detected or no lines are detected in the subset of outliers, i.e., no consensus set is obtained in a maximum number of iterations n. It is worth noting that in order to maintain the high frequency provided by LMSs, we performed only a small number of iterations (n = 100). The robustness of the whole

Step 1

Step 2

Step 5

Step 4

Step 3 algorithm is in fact increased by applying optimal classification (Step 3) and estimation (Step 4,5) methods to the straight lines obtained.

At each sampling interval, the h-th line xl h given by the algorithm can correspond to any of the four lines defining the parking spot (x l1...4 ), or even to none of them.

Figure 5(c) shows the four lines detected by RANSAC in the cloud of points presented in Fig. 5(b). Note that xl2 (the green line in Fig. 5(c)) differs from the corresponding line x l3 (the pink line in Fig. 5(a)), while xl3 , xl4 (the red and pink lines in Fig. 5(c)) are not in the right order as they correspond to x l2 , x l4 (the green and red lines in Fig. 5(a)).

Step 3 -Classifying Lines:

Let us take the four straight lines x l1...4 defining the parking spot (Fig. 5(a)) and consider that they belong to four classes L 1...4 .

To determine whether the h-th line xl h detected in Step 2 belongs to the j-th class L j , we used Naive Bayes Classifiers (NBCs), giving normal and uncorrelated probability distributions for the two components of xl h . We therefore computed the Bayes probability as follows 2 :

           p j,h = p(L j |x l h , y l h ) = p(Lj )p(x l h |Lj )p(y l h |Lj ) p(x l h ,y l h ) p(x l h |L j ) = 1 2πσ 2 x j e - (x l h -µx j ) 2 2σ 2 x j (same for y l h ) p(x l h , y l h ) = 4 j=1 p(L j )p(x l h |L j )p(y l h |L j ) (7)
where we considered p(

L j ) = 1 4 , [µ xj µ yj ] T = x- lj (k) and [σ xj σ yj ] T = f l (x lj (k -1), u(k -1)
), with k denoting the kth sampling period (i.e., t = k∆t), and xlj = [x lj ŷlj ] T being 2 The hypothesis that the two components of xl h had normal and uncorrelated probability distributions was adopted on the basis of what was observed statistically during several simulations with trajectories of various kinds.

the position vector of j-th line estimated by the EKF and xlj its "a priori" estimate (see the next subsection for details).

We classified the line xl h in the class L j if p j,h = max j,h p j,h and p j,h > 0.95. To avoid any misunderstandings, we specified the j-th classified line xlj = [x lj ȳlj ] T .

Figure 5(d) shows the three lines which were classified out of the four lines in Fig. 5(c). In particular, xl2 (the green line in Fig. 5(c)) was dropped because it was too different from the corresponding line x l3 (the pink line in Fig. 5(a)), while xl3 , xl4 (the red and pink lines in Fig. 5(c)) were classified as xl4 , xl2 (the green and red lines in Fig. 5(a)).

Step 4 -Estimating Lines:

In order to obtain a robust continuous estimation of the parking line vectors, an Extended Kalman Filter (EKF) based on a discrete approximation for the model presented in [START_REF] Hsu | Development of an automatic parking system for vehicle[END_REF] was implemented for each of the four lines x l1...4 by taking the lines classified in Step 3 (x l1...4 ) to be actual measurements.

For each line, we took the first-order discrete approximation for the model presented in (5) as follows:

   x l k = fl (x l k-1 , u k-1 , w l k-1 ) = (f l (x l k-1 , u k-1 ) + w l k-1 )∆t + x l k-1 z l k = h l (x l k , ν l k ) = x l k , (8)
where the index k denotes the k-th sampling period (i.e., t = k∆t); w l , ν l denotes the model and the measurement noise, respectively, and they are assumed to be independent white noises and to have normal probability distributions, i.e. p(w) ∼ N (0, Q) and p(ν) ∼ N (0, R), where Q, R are the covariance matrices which, in the present case, are diagonal 3 .

At each sampling period, the steps involved in each EKF can be summarized as follows:

1)

x- l k = fl (x l k-1 , u k-1 , 0) 2) P - k = F k P k-1 F T k + W k QW T k 3) K k = P - k H T k (H k P - k H T k + V k RV T k ) -1 4) xl k = x- l k + K k (z l k -h l (x - l k , 0)) 5) P k = (I -K k H k )P -1 k where F = ∂ fl ∂x l , H = ∂h l ∂x l , W = ∂ fl ∂w l , V = ∂h l
∂ν l are the Jacobian matrices; P, P -are the error covariance matrix and its "a priori" estimate, respectively; and I is the identity matrix.

In the present study, the j-th EKF was enabled when the j-th line was detected and validated for the first time on the basis of the time correlation in the values of xlj (hypothesis test), but in practice, this could be done using other sensors such as ultrasonic sensors, cameras or radars installed on the vehicle.

The initial estimate of xlj was set at the first value of xlj validated, while the initial estimate of P k was set at the identity matrix.

When there was no measurement of the j-th EKF, i.e. no xlj in Step 3, the Kalman gain K k was set at zero, so that it was still possible to have an estimation of x lj based on the "a priori" prediction xlj . Figure 5(e) shows the four lines estimated by the four EKFs. Note that although there was no measurement corresponding to xl3 in Fig. 5(d), we still had an estimation of xl3 .

Step 5 -Estimating Corners:

The position vectors of the four parking corners can be estimated in terms of the intersection point between each pair of perpendicular lines estimated in Step 4. This makes it possible to compute the j-th corner vector xcj = [x cj ȳcj ] T by substituting xlj and xlj+1 into (4) and combining the two resulting equations. Here we dealt only with the two outer corners (the green and red circles in Fig. 5(e)). We took xc l , xcr to specify the position vectors of the left and right corners, respectively. This estimate of the corners' positions was not accurate enough to be able to perform a feedback tracking control on it. In particular, when the car is crossing the lines, i. e. x l ≈ 0, a very small error in xl can lead to a very large error in xc .

In order to obtain a robust continuous estimation of the corner vectors, an EKF based on a discrete approximation of the model presented in (1) was implemented for each of the two outer corners (x c l , x cr ), by taking the line intersection points defined above (x c l , xcr ) to be actual measurements.

The same procedure as that applied with the EKF on x l in the previous subsection can be used with the EKF on x c (taking the same model and the same measurement noise). We only had to replace the index l by the index c and take the function f P (x c , u) defined in (1) instead of f l (x l , u).

The EKFs for x c l and x cr were enabled when the EKFs for x l1 , x l2 and x l1 , x l4 were enabled, respectively (the blue and green lines and the blue and red lines, respectively, in Fig.

5(e)).

The initial estimates for xc l and xcr were set at the first value of the intersection point between xl1 , xl2 and xl1 , xl4 , respectively, while the initial estimate of P k was set at the identity matrix.

Note that although we defined the parking spot by the above four lines x l1...4 , the parking spot can be detected even if x l3 is not found (i.e. in the case of an "open" or "homogeneous" background), and depending on the automatic pilot's requirements, a tracking control of the ego-vehicle's trajectory can eventually be performed only on the basis of the two outer corners' positions (x c l , x cr ) and the two lateral lines' orientations (x l2 , x l4 ). For safety reasons, information about the parking-spot depth (i.e. the distance between the vehicle and x l3 ) should be provided by means of other sensors (e.g. ultrasonic sensors or cameras).

V. CLOSED-LOOP SIMULATION RESULTS

In the simulation presented here, we used 40-pixel LMSs with ∆ϕ = 4.5 o (N × ∆ϕ = 40 × 4.5 o = 180 o ) and a white Gaussian noise with standard deviation σ n = 10 -2 . The algorithm was run at 100 Hz, giving a sampling period of ∆t = 10 ms. We decided to simulate the case of perpendicular parking because it involves more complex maneuvers than parallel parking, which gives noisier OF measurements than the parallel case. In addition, to obtain results that are closer to the real case, we took into account only the OF measurements in [-350 • , -1 • ] and [1 • , 350 • ] (see [START_REF] Sabiron | Lowspeed optic-flow sensor onboard an unmanned helicopter flying outside over fields[END_REF], [START_REF] Expert | Flying over uneven moving terrain based on optic-flow cues without any need for reference frames or accelerometers[END_REF]).

For the simulated results presented here, the stages of the parking controller can be summarized as follows:

Parking stage 1 -V f constant, φ in closed loop: Drive at constant velocity (V f = 1 m s ) parallel to the first parking line x l1 (blue line in Fig. 5) until the two outer corners x c l , x cr are found: if the distance between x c l and x cr is greater than a minimum value of the parking-spot width then go to the next step, otherwise continue to look for a parking spot. To drive parallel to x l1 , the steering angle was computed as φ = arctan(k φ L θ * -θl 1 V f ), where θl1 is the vehicle's orientation with respect to x l1 estimated by the first EKF (see equation ( 8)), θ * = π 2 and L = 2 m. Parking stage 2 -V f and φ constant: Drive away from the parking spot at constant velocity and steering angle (V f = 1 m s , φ = -π 9 ) for a fixed time in order to bring the vehicle to a suitable pose for facilitating the backwards maneuver. Then, compute the reference trajectory X * c of the vehicle's ego-position with respect to the inertial frame < I > centered to one of the two corners. The trajectory from the actual pose to the desired pose, i.e. being in the middle between x c l and x cr and parallel to x l2 (or x l4 ), was computed as a third-order polynomial function using the boundary conditions on the initial and final position and velocity.

Parking stage 3 -V f and φ in closed loop: Drive backwards following the reference trajectory by applying a feedback linearizing control based on the Ackermann model as follows [START_REF] De Luca | Robot Motion Planning and Control, ch. Feedback control of a nonholonomic car-like robot[END_REF]: Parking stage 4 -V f constant , φ in closed loop: Drive backwards at low constant velocity (V f = -0.5 m s ) parallel to x l2 (or x l4 ) by computing the steering angle as φ = arctan(k φ L θ * -θl 2 V f ), with θ * = -π 2 , until the parking maneuver is done. 5Figure 6 shows the errors in the line and corner position vectors which occurred in Steps 2 to 5, as described in Sec. IV, during a given trajectory of the simulated vehicle. Step 2

V f = -Ẋc 2 + Ẏc
Step 3

Step 4

Step 4 In Step 2, the errors between the real lines and the lines obtained with RANSAC (x lxl ) were sometimes relatively large (Fig. 6(a)). As explained above, this was due to the fact that the lines given by RANSAC were sometimes not in the right order (for instance, the second line obtained occasionally corresponded to the third one, as in Fig. 5(c)), or they were sometimes spurious lines.

In Step 3, the errors between the real lines and the lines classified by NBCs (x lxl ) were much smaller, but they could still be relatively large, depending on the noise (Fig. 6(b)).

Fig. 1 .

 1 Fig. 1. (a) Principle of a 2-pixel LMS. The OF produced by a contrast moving in front of the LMS can be computed taking ω(t) = ∆ϕ τ (t), where ∆ϕ is the interreceptor angle and τ is the time lag between the two photoreceptors' output signals[START_REF] Ruffier | Bio-inspired optical flow circuits for the visual guidance of micro air vehicles[END_REF]. (b) Photo of a 6-pixel LMS. (Adapted from[START_REF] Sabiron | Lowspeed optic-flow sensor onboard an unmanned helicopter flying outside over fields[END_REF]).

Fig. 2 .

 2 Fig. 2. (a) Diagram of the visual-motion sensor setup on a vehicle. The N -pixel LMSs are placed at the four corners of the vehicle, where N is such that N × ∆ϕ = 180 o . (b) An example where 4 neighboring visual signals give 3 local OF measurements.

Figure 3 Fig. 3 .

 33 Fig. 3. Top-view diagram of a car-like vehicle with a 1-D OF sensor installed on one corner.

Fig. 4 .

 4 Fig. 4. Block diagram of the parking-spot detection and tracking algorithm.

Figure

  Figure 5 shows an example of the results obtained in each step in the algorithm at one sampling interval during the simulation. This example involves the case of perpendicular parking, but the present algorithm can be applied to the case of parallel parking as well without making any changes.In the simulated 2-D parking environment, the parked vehicles were simulated in the form of rectangular shapes (Fig.5(a)) and the OF measurements of the LMSs were computed

Fig. 5 .

 5 Fig. 5. Example of results obtained in each step in the parking-spot detection and tracking algorithm at one sampling interval during the simulation. (a) The simplified 2-D parking spot with the position vectors perpendicular to the 4 lines defining the spot. (b) The points detected on the pixels' axes, the positions of which were computed using the 1-D OF measurements delivered by the LMSs placed at the vehicle's corners (Step 1). A white Gaussian noise is added to the positions of these points in order to add a non-linear noise to the OF measurements. (c) The position vectors of the lines obtained by RANSAC in the cloud of points (Step 2). (d) The position vectors of the lines classified by NBCs (Step 3). (e) The position vectors of the lines estimated by EKFs (Step 4). A first approximation of the parking corners' position is given by the points of intersection between each pair of perpendicular lines. (f) The position vectors of the parking corners estimated by EKFs (Step 5).

2 andφ

 2 = arctan(L Ẋc Ÿc-Ẏc Ẍc

V 3 f

 3 ), where Ẋc = [ Ẋc Ẏc ]T = Ẋ * c + k 1 (X * c -Xc l ) and Ẍc = [ Ẍc Ÿc ] T = Ẍ * c + k 2 ( Ẋ * c -Ẋc l ), Xc l being the estimation on the vehicle's ego-position with respect to the left corner, i.e. Xc l = -I R B xc l , and I R B being the rotation matrix from < B >to < I >.4

  line validated as parking lines EKF on x l1 , x l2 and x cr enabled Red line validated as parking line: EKF on x l4 and x cl enabled parking spot validated and maneuver started crossing-line zones

15 Fig. 6 .

 156 Fig. 6. Errors in the line and corner position vectors occurring during a given trajectory of the simulated vehicle at: (a) Step 2 (x l -x l ); (b) Step 3 (x l -x l ); (c) Step 4 (x l -xl ); (d) Step 4 (xcxc); (e) Step 5 (xcxc). The colors in this figure correspond to those of the lines and corners presented in Fig. 5. The continuous and dotted curves correspond to the x and y coordinates of the vectors, respectively.

Substituting (1) into (2) is possible because the sampling period ∆t is low enough with respect to the dynamics of x i , y i . However, a similar result can be obtained in cases where this condition is not met, by taking a discrete approximation of (1).

The hypothesis that the components of the model and the measurement noise had normal and uncorrelated distributions was adopted on the basis of what was observed statistically during several simulations with trajectories of various kinds.

We used the estimation xc l (left corner) since the estimation xcr (right corner) was not enough reliable during the first part of the maneuver because we have no measurements for x l 2 due to the occlusion.

The gains k φ , k 1 , k 2 > 0 were dynamically adapted in order to avoid any saturation of the control inputs.In Step 4, the errors between the real lines and the lines estimated by the EKFs (x lxl ) were about one order of magnitude smaller, and an estimation was still delivered even when no corresponding line was found, i.e. no measurement xl

ACKNOWLEDGMENTS

We are most grateful to M. Boyron and J. Diperi for their involvement in the electronic and mechanical design of the sensors, and to S. Prodhomme and J. Masson for their help with the sensor support on the vehicle. We also thank S. Allano for his assistance.

was obtained (Fig. 6(c)). However, when the car was crossing the lines, i. e. x l ≈ 0, a very small error in xl could lead to a very large error in xc (corresponding to the shaded regions in Fig. 6(d)).

In Step 5, the errors between the real corners and those estimated by the EKFs (x c -x c ) were much smaller, especially when crossing lines (Fig. 6(e)).

The preliminary controller and the results presented here could be further improved, for instance by looking for the right corner's position x cr in the cloud of points while the vehicle is in the blind zone for the x l2 (see Fig. 6) in order to improve the reliability on the estimation xcr and perform a closed-loop maneuver based on the estimation of both corners' positions.

VI. PRELIMINARY EXPERIMENTAL TESTS

Preliminary tests were carried out on a real vehicle (Peugeot 3008) in order to check the validity of the first step in the algorithm presented in Sec. IV. In particular, two 6-pixel LMSs (∆ϕ ≈ 1.5 o [13] and 3.8 o [START_REF] Expert | Flying over uneven moving terrain based on optic-flow cues without any need for reference frames or accelerometers[END_REF]) and a webcam (Logitech B905) were tied to a supporting slab which was attached to the front fender, as shown in Fig. 7(a). The slab could be moved and rotated along the z-axis in order to adjust the sensors' height and their orientation. To compute the OF measurements ω i , the time lag τ i between the i-th and i -1-th pixel output signal (see Fig. 1,2) was estimated using a cross-correlation method inspired by the Reichardt-Hassenstein model [START_REF] Reichardt | Sensory Communication, ch. Autocorrelation, a principle for the evaluation of sensory information by the central nervous system[END_REF]. First we delayed one of the two signals by a time τ k = k∆t in a fixed time window, and we then computed the cross-correlation between the delayed and non-delayed signals. We then set τ i at a value equal to the time lag τ k giving the maximum cross-correlation, as long as this maximum was greater than 0.99. As the precision in τ i is constant and ω i is inversely proportional to τ i , the precision in ω i is proportional to ω i itself, as we can notice by looking at Fig. 7(b).

The data acquisition and the data processing were performed on a laptop PC (Intel Core i7-2620M CPU 2.70 GHz) with RTMaps software. In particular, the pixel output signals delivered by the LMSs were sampled at a rate of 1 kHz by the embedded micro-controller (Microchip dsPIC33FJ128GP802) and transmitted to the PC via serial communication, whereas the vehicle's longitudinal velocity and its steering angle were acquired at 20 Hz by the PC via the vehicle's CAN bus. The OF and the positions of the 2-D points were computed at a frequency of 100 Hz.

Figure 8 shows two examples of the vehicle's trajectory along with the positions of the 2-D points computed using the OF measured by one of the two 6-pixel LMSs presented in Fig. 7(a) (∆ϕ ≈ 3.8 o [14]) when the vehicle was moving along a parallel (Fig. 8(a)) and a perpendicular parking lane (Fig. 8(b)) at a longitudinal velocity ranging from 3 to 9 m s . The refresh frequency of the OF measurements, that is to say the ratio between the number of measurements performed in a given time interval and the time interval itself, can vary significantly, depending on the empty spaces and the contrasts provided by the car bodies (see the pictures in the lower part of Fig. 8(a) and (b)), giving both dense and sparse clouds of points. However, the average refresh frequency fω for the OF produced by the parked vehicles ranged from 30 to 65 Hz, which is about 2-3 times greater than those of standard ultrasonic sensors and cameras.

A few 2-D points were generated in the center of Fig. 8(a) as the vehicle was moving along an empty parking place lined with small traffic poles (see the third picture in Fig. 8(a)). No measurements were made here on the background of the spots because it was too far from the LMS. In fact, the analog bandpass filter implemented on the LMS (see [START_REF] Expert | Flying over uneven moving terrain based on optic-flow cues without any need for reference frames or accelerometers[END_REF]) cuts off the lowfrequency variations in the photoreceptors' signals produced by the slow visual motion of the background. This issue can be fixed by adjusting the analog filtering part of the LMS, but this has not been shown here.

It is worth noting that in the case of both parallel and perpendicular parking, it is possible to recognize the shapes of the parked vehicles in the clouds of points, even though few measurements are sometimes made due to the reflections on the car bodies (see, for instance, the fourth picture in Fig. 8(a)).

In the case of perpendicular parking, the measurements were noisier than in the parallel case, mainly because of (i) the occlusions of the cars' sides and (ii) the misalignment of the cars (see for instance the first and second pictures in Fig. 7(b)).

The qualitative results presented here validate the first step in the algorithm we have developed. Although it was not possible, in the case of this example, to apply the other steps in the algorithm because there were too few points in each sampling interval, it seems likely that by using LMSs with a larger number of pixels (or several 6-pixel LMSs) delivering 1-D OF measurements all round the vehicle, we will probably have enough points to be able to apply all the steps.

VII. CONCLUSIONS

In this paper, we have presented a low computational-cost method for detecting and tracking a parking spot in real time based on a visual motion sensor setup performing 1-D OF measurements around the vehicle.

The advantages of this method can be summed up as follows:

• the average refresh frequency is about 2-3 times higher than with standard ultrasonic sensors and cameras; • it produces redundant information about a parking spot, in cases where ultrasonic sensors and cameras are liable to be inaccurate (e.g., when the parked vehicles are too far apart or too close, under widerange lighting conditions and when indistinct visual patterns are visible on the car bodies); • it can detect a candidate parking spot before passing it, thanks to the long-distance, wide-angle range of view; • it can track the parking spot in real time, thanks to the wide-angle range of view, as well as the highfrequency measurements and low computational-cost processing; • it makes it possible to eventually apply a nonlinear tracking control strategy using the estimation of the vehicle's ego-position with respect to the parked vehicles. For these reasons, LMSs can provide a good additional information to automatic parking systems as well as to other automotive applications. In particular, by using LMSs with several pixels (or several few-pixel LMSs) giving a 180 o FOV at each of the car's four corners, it should be possible to apply the present method in real time to performing safe closed-loop parking maneuvers.

Although we focused here only on the information provided by the LMSs, data provided by other sensors (such as ultrasonic sensors) could be integrated into the algorithm to achieve more robust performances.

Studies to improve the closed-loop parking maneuvers and experimental tests with several LMSs on a real car-like robot are now under way.