R Boutteau

X Savatier

F Bonardi

J Y Ertaud

Road-line detection and 3D reconstruction using fisheye cameras

In future Advanced Driver Assistance Systems (ADAS), smart monitoring of the vehicle environment is a key issue. Fisheye cameras have become popular as they provide a panoramic view with a few low-cost sensors. However, current ADAS systems have limited use as most of the underlying image processing has been designed for perspective views only. In this article we illustrate how the theoretical work done in omnidirectional vision over the past ten years can help to tackle this issue. To do so, we have evaluated a simple algorithm for road line detection based on the unified sphere model in real conditions. We firstly highlight the interest of using fisheye cameras in a vehicle, then we outline our method, we present our experimental results on the detection of lines on a set of 180 images, and finally, we show how the 3D position of the lines can be recovered by triangulation.

I. INTRODUCTION

In recent years, Advanced Driver Assistance Systems (ADAS), initially limited to luxury vehicles, have become available on high-volume models. Medium-sized cars are now sold with ADAS features such as lane departure warning, blind spot monitoring and road sign recognition. As reported in [START_REF]Advanced driver assistance systems (adas)[END_REF] an impressive growth of the ADAS market is expected, going from $10 billion in 2011 to $130 billion in 2016. This growth will be possible not only through the reduction of component costs but also with the integration of new functions on the original architecture. This explains why ADAS based on vision are one of the most common schemes for driving assistance as cameras can be considered as versatile multifunction sensors. Recently, [START_REF] Pajon | Enlighting the future: from autonomous adas to autonomous driving[END_REF] has highlighted the performance potential of camera sensor combined with increasingly competitive costs. In the future, as ADAS should offer more and more automated assistance, this will imply a robust and complete perception of the vehicle environment while maintaining affordable costs with sensor rationalization and fusion.

Monitoring the surrounding environment of a car can be achieved using a very small number of cameras. An omnidirectional observation of a scene is possible with a single camera by combining it with a convex mirror. Such a system, called a catadioptric sensor (association of a mirror (catoptric) and lenses (dioptric)), has been widely studied in autonomous robotics [START_REF] Delahoche | A navigation system based on an omnidirectional vision sensor[END_REF][33] [START_REF] Boutteau | An omnidirectional stereoscopic system for mobile robot navigation[END_REF]. Its use for automotive applications has also been explored [START_REF] Kohsia | Driver's view and vehicle surround estimation using omnidirectional video stream[END_REF][19] [START_REF] Scaramuzza | 1-point-ransac structure from motion for vehiclemounted cameras by exploiting non-holonomic constraints[END_REF]. However, this sensor is not optimal for the monitoring of the surrounding environment because objects close to the vehicle may be occluded by the vehicle itself. Recently, the use of multiple large field of view cameras has been proposed [START_REF] Ehlgen | Eliminating blind spots for assisted driving[END_REF] [START_REF] Li | Easy calibration of a blind-spot-free fisheye camera system using a scene of a parking space[END_REF]. [START_REF] Tadjine | Intelligent park assists system: Pedestrian detection based on fisheye camera[END_REF] has demonstrated the potential of such a sensor for pedestrian detection in blind spot monitoring. Indeed, wide angle cameras such as fisheyes are particularly suitable for lateral views as a single camera placed on the side can observe all the surrounding objects from the rear to the front of a car. Thus, only four wide angle cameras are needed to obtain a complete bird's-eye view from above the vehicle as demonstrated with the NISSAN Around view TM monitor.

Theoretical works in omnidirectional vision have let to the formalization of a unified model which consists of a projection onto a virtual unitary sphere. While initially restricted to central catadioptric sensors [START_REF] Geyer | A unifying theory for central panoramic systems and practical implications[END_REF], this model has recently been extended to fisheye cameras [START_REF] Courbon | A generic fisheye camera model for robotic applications[END_REF]. In past studies, we showed how this framework can be helpful for 3D reconstruction [START_REF] Boutteau | 3d reconstruction for autonomous navigation[END_REF] and how it can improve classical machine learning algorithms for image understanding [START_REF] Dupuis | Robust radial face detection for omnidirectional vision[END_REF]. In this paper, we want to highlight the potential of such a model coupled with fisheye sensors for an ADAS application by applying it to roadmarking detection. Road-marking detection is a basic step in many ADAS functions such as lane-departure warning, lanekeeping and blind-spot control. In this paper, we present a simple and efficient algorithm for detecting lane marking using lateral fisheye views. As a first step, the algorithm is restricted to straight line detection and is evaluated in real conditions on a database of 180 images. Using our method, a 3D reconstruction of lines is possible, which facilitates the rejection of outliers and will be helpful in automated guidance. In section II, we set out the state of the art with regard to road-line detection algorithms in classical and omnidirectional images. In section III, we present our new algorithm for detecting straight lines in omnidirectional images. Section IV is dedicated to the experimental results obtained from this detection algorithm as well as to a straight line triangulation application. Lastly, in section V, we present a conclusion and identify several directions for future work.

II. STATE OF THE ART IN METHODS FOR DETECTING STRAIGHT LINES IN OMNIDIRECTIONAL IMAGES

Road-marking detection for ADAS applications has been widely studied using monocular systems [START_REF] Mccall | Video-based lane estimation and tracking for driver assistance: survey, system, and evaluation[END_REF], stereovision [START_REF] Nedevschi | 3d lane detection system based on stereovision[END_REF] or more recently by fusion with navigation sensors [START_REF] Sivaraman | Improved vision-based lane tracker performance using vehicle localization[END_REF] but most of the algorithms proposed are suitable for perspective front views only. An interesting survey of common algorithms can be found in [START_REF] Veit | Evaluation of road marking feature extraction[END_REF]. Lane detection obtained from lateral views is, however, particularly suitable in applications where lateral parts of the vehicle have to be monitored. But in such a case, perspective cameras cannot be used due to the fact that surrounding objects may be very close to the car. In [START_REF] Li | Monitoring around a vehicle by a spherical image sensor[END_REF], the authors demonstrated how this issue can be tackled using fisheye cameras. They proposed a method to detect road marking based on some assumptions regarding the movement of cars. In [START_REF] Li | Easy calibration of a blind-spot-free fisheye camera system using a scene of a parking space[END_REF] they also used their line detection method for on-line fisheye calibration. Another interesting use of fisheyes can be found in [START_REF] Hirose | Estimation of vehicle wheelbase in a circular fisheye image using two-step detection method of tire-road contact points[END_REF] where the authors used this sensor for car recognition.

The detection of straight lines in omnidirectional images is much less easy than in perspective images as the projection of lines onto an image plane no longer gives straight lines but conic sections. The classical problem of detecting lines in perspective images therefore becomes a complex problem of detecting conics in omnidirectional images. There are several special cases which simplify the detection of lines in omnidirectional images. [START_REF] Yagi | Real-time generation of environmental map and obstacle avoidance using omnidirectional image sensor with conic mirror[END_REF] and [START_REF] Delahoche | A navigation system based on an omnidirectional vision sensor[END_REF] were interested in the detection of lines projected radially onto a conical mirror. This configuration requires that the sensor be in a vertical position and that there be sufficient vertical lines in the environment. [START_REF] Fiala | Line segment extraction in panoramic images[END_REF] proposed a method for extracting horizontal and vertical segments but not for every type of straight line. This limitation is due to the use of non-central sensors which makes the detection of certain types of lines extremely complex. The same problem is covered in [START_REF] Pinciroli | Robust detection of 3d scene horizontal and vertical lines in conical catadioptric sensors[END_REF]. For central sensors, the methods for estimating lines can be classified into two main categories. The first category tries to detect conic sections in the image and to estimate the five parameters so that the conic section is adjusted to the extracted data [START_REF] Zhang | Parameter estimation techniques: A tutorial with application to conic fitting[END_REF]. The computation time is generally long and these algorithms are not efficient when only small proportions of the conic sections are visible. Furthermore, these methods are often only applicable in the special case of the paracatadioptric sensor, a combination of a paraboloidal mirror and an orthographic camera, as the projections of the lines then become arcs of circles [START_REF] Barreto | Direct least square fitting of paracatadioptric line images[END_REF] [3] [START_REF] Vandeportaele | A fast detector of line images acquired by an uncalibrated paracatadioptric camera[END_REF]. The second category involves the detection of great circles on the equivalence sphere. It has been demonstrated in [START_REF] Geyer | Catadioptric projective geometry[END_REF] that the projection of a 3D line on the sphere is a great circle C as illustrated in Figure 1. These methods are only applicable to calibrated sensors as it is necessary to be able to calculate the projection of pixels on the equivalence sphere. [START_REF] Bazin | Fast central catadioptric line extraction[END_REF] describes such a method.

The main advantage of the detection of great circles on the equivalence sphere is that the algorithm can be used for all central sensors because it is a unified model. The detection of great circles is in general carried out by a Hough transformation [START_REF] Hough | Method and means for recognizing complex patterns[END_REF], the difference between the various algorithms is the space in which the processing is carried out. In [START_REF] Vasseur | Central catadioptric line extraction[END_REF], the great circles on the sphere are defined by their normal, characterized by the angles of elevation and azimuth. A Hough space based on these angles is then created and the detection of maxima in the Hough space enables the parameters for the lines to be obtained. There are other Hough spaces for characterizing the lines. It is for example possible to use either the normal directly [START_REF] Mei | Laser-Augmented Omnidirectional Vision for 3D Localisation and Mapping[END_REF] or its cubic coordinates [START_REF] Yamazawa | 3d line segment reconstruction by using hyperomni vision andomnidirectional hough transforming[END_REF]. However, the Hough transformation introduces several problems such as the selection of the best sampling step for the Hough space which should in addition take account of the non-uniform resolution of the sensors. In addition, the detection of maxima in the Hough space is a complicated step.

III. OUR METHOD

As we have seen in the previous section, most of the existing algorithms are either specific to a type of mirror or specific to a given type of line (horizontal or vertical). We therefore propose a new method for detecting and estimating any type of line in omnidirectional images, valid for all central sensors and based on the robust RANSAC (RANdom SAmple Consensus [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF]) estimation algorithm. The first phase in our method consists in extracting the edges present in the omnidirectional image (figure 2a) by applying Canny's algorithm. A very large number of edges are detected some of which are not actually physical edges, as is shown in Figure 2b. Chains of connected pixels are then created with the edges previously extracted. To avoid detecting a multitude of small lines, chains which are too short are disregarded. The result of this step is shown in Figure 2c. In this figure, the chains of connected pixels are represented by different colors and chains fewer than 50 pixels have been discarded. Each chain thus created is a potential omnidirectional line.

It is therefore necessary to make a decision on whether it really is a line and, if so, estimate its parameters. Omnidirectional lines will be characterized by the normal to the plane which contains the line and which passes through the center of the equivalence sphere (see Figure 3). We propose to work directly on the unitary sphere S 2 ∈ R 3 . We characterize a line by the normal n ∈ S 2 + to the plane formed by the line and the center of projection. All the pixels in the chains are projected onto the equivalence sphere. This step, called lifting, requires knowledge of the intrinsic parameters of the sensor and therefore assumes the sensor to be calibrated. All the following calculations are carried out using the points on the sphere. To estimate the parameters of the line which best correspond to the points in the chain, a robust estimation method called RANSAC is used. Its pseudo-code is given in Algorithm 1. For each chain, two points X1 S and X 2 S are taken randomly and the normal to the plane passing through these two points and the center of the sphere is calculated:

n = λ X 1 S × X 2 S X 1 S × X 2 S
, where λ ∈ {-1, 1} ensures that n ∈ S 2 +

(1) The other points in the chain are then tested to decide whether they belong to the great circle C given by:

C = {X S |n T X S = 0, X S = 1} (2)
In practice, because there are small errors due to noise, the discretization of the image or calibration, an error threshold is set to decide whether or not point X S belongs to the great circle C . All the points belonging to the great circle C defined by n are then stored in the memory. If the number of points belonging to the circle C is greater than the minimum length allowed for defining a line, then the pixel chain does indeed relate to a line whose normal is re-estimated using all the points belonging to the great circle. It is then possible to define segments rather than lines by taking the first and last pixel in the chain belonging to the great circle.

Algorithm 1 Pseudo-code for estimating omnidirectional lines using the RANSAC method.

k ← 0 while k < MAX ITERATIONS do maybe inliers = 2 points selected randomly maybe line = n estimated using these 2 points consensus set = maybe inliers for each point not in maybe inliers do if the point complies with the model with an error smaller than MAX ERROR then add the point to consensus set end if end for end while if the number of points in consensus set > THRESHOLD then This is definitely a line. Re-estimation of n with all the points in consensus set end if

IV. EXPERIMENTAL RESULTS AND APPLICATION TO LINE TRIANGULATION

A. Line detection

We applied this algorithm to the field of autonomous computer-aided driving, so we chose to place our cameras close to the left and right rear-view mirrors of a car. The camera we used is a Prosilica GC1380C with a fisheye lens (Fujinon fisheye 1:1.4/1.8mm) reducing its region of interest to a resolution of 1024x1024 pixels so that the circular field of view is centered in the images. We pointed this sensor toward the road with an angle of about 45 ˚in order to see both the immediate environment (road and blind spots of the car) and the global environment (buildings for instance). The sensor was calibrated using our omnidirectional calibration tool 1 . During testing we drove both in urban zones and on highways, with several quality levels of the road (texture, uniformity, etc) and its markings (good, damaged or missing). We took 180 images, which were later processed with our algorithm. To evaluate the sensitivity of the processing, we calculated the True Positive Rate (TPR) according to the following formula:

T P R = T P T P + F N (3)
• True Positives (TP) are cases where there is a road marking or a border of the road in the image and the algorithm detects it (see Figure 4a and4b). • False Negatives (FN) are cases where there is a line or a border of the road in the image and the algorithm does not detect it (see Figure 4d).

• False Positives (FP) are cases where the algorithm detects a line where there is none (see Figure 4c). • During our tests, we did not encounter any True Negatives (TN), due to the fact that there was always a road marking or a border of the road in the field of view. The TP, FN and FP rates are given in Table I.As shown, we obtained a True Positive Rate of 86.9%.

B. 3D reconstruction

The detection of omnidirectional lines outlined above enables us to parameterize the line in the local reference frame of the sensor, the line being represented by the normal to the plane containing the line and the center of the sensor. It is possible to triangulate the line, in order to obtain its 3D position. This can be achieved if the pose (R, t) of the sensor relative to the road is known. In practice, we used a calibration pattern lying on the road to estimate the pose by solving an omnidirectional Perspective-N-Point problem [START_REF] Fabrizio | An analytical solution to the perspective-npoint problem for common planar camera and for catadioptric sensor[END_REF].

Let (C 1 , x 1 , y 1 , z 1 ) be the reference frame attached to the vehicle (see Figure 5). The center C 1 = [0 0 0] T is located vertically below the omnidirectional sensor and on the road level. n 1 = [0 0 1] T is the normal of the road.

Let C 2 = [c 2x c 2y c 2z ] T be the center of the sensor, and (C 2 , x 2 , y 2 , z 2 ) the reference frame of this sensor. n 2 = [n 2x n 2y n 2z ] T is the normal characterizing the line within the reference frame (C 1 , x 1 , y 1 , z 1 ) . The objective is to determine the parametric equation of the corresponding 3D line L: L = A + λu, where A is a point on the line and u its direction vector.

u = n 1 × n 2 n 1 × n 2 (5)
The 3D estimation of the line was evaluated in a corridor as shown in Figure 6. The sensor was mounted on a robot and calibrated as described above.

The line corresponding to the bottom of the wall was detected and its 3D position was compared with the ground truth obtained using a 3D laser scanner (Leica ScanStation C10). Figure 7 shows that the estimated position of the line (in green) corresponds to the ground truth obtained by laser telemetry (in gray).

V. CONCLUSION AND FUTURE WORK

In this paper, we have presented a novel method for line detection in omnidirectional images which is able to extract any straight lines (not only vertical ones) with any central sensor (fisheye, or catadioptric sensors of any shape). We applied our algorithm to road line detection with fisheye cameras embedded in a vehicle. The True Positive Rate of 86.9% that we obtained demonstrates that the proposed technique works very well. It is also possible to obtain the 3D position of the detected lines, using triangulation, which can be useful for ADAS features such as lane departure warning or for the visual servoing of vehicles on the road. Our future works will focus on the problem of tracking the lines over time to improve the results in terms of robustness.

Fig. 1 .

 1 Fig. 1. Projection of a line onto the equivalence sphere.

Fig. 2 .

 2 Fig. 2. (a) Omnidirectional image -(b) Detected edges-(c) Chains of connected pixels.

Fig. 3 .

 3 Fig. 3. Characterisation of an omnidirectional line by a normal.

Fig. 4 .

 4 Fig. 4. Samples of line detection. (a) and (b) True Positives, (c) False Positive, (d) False Negative

Fig. 5 .

 5 Fig. 5. Triangulation of an omnidirectional line.

Fig. 6 .

 6 Fig. 6. The omnidirectional image used for the 3D reconstruction of the line.

Fig. 7 .

 7 Fig. 7. 3D reconstruction of a corridor. The triangulated line is represented in green and the ground truth in gray.

TABLE I DETECTION

 I RATES OBTAINED ON THE 180 IMAGES OF THE DATABASE

	TP	81.11%
	FN	12.22%
	FP	6.67%
	TPR	86.9%

This software is available at http://omni3d.esigelec.fr/doku.php/omni/calib

ACKNOWLEDGMENT

This study has been supported by the European ARTEMIS Joint Undertaking and the DGCIS at the French Ministry for Industrial Renewal.


R Boutteau
email: boutteau@esigelec.fr

X Savatier
email: savatier@esigelec.fr

J Y Ertaud
email: ertaud@esigelec.fr

A dynamic programming algorithm applied to omnidirectional vision for dense 3D reconstruction

Keywords: omnidirectional vision, catadioptric sensor, stereovision, 3D reconstruction, dynamic programming

In this paper, we present a dense 3D reconstruction algorithm adapted to stereoscopic omnidirectional sensors. Our main contributions are the generalization of global constraints to central systems and the use of dynamic programming to take them into account. Experimental results show the interest of our algorithm on real data.

I. INTRODUCTION

Interest in mobile robotics have constantly been increasing in recent years, especially to replace humans in dangerous environments. These hostile environments can be natural (seabed, planets, areas of natural disasters) or linked to human action (nuclear, battlefields). For interventions in such environments, many robots have been developed, but they are generally controlled by a remote operator who receives the necessary data via sensors (ultrasonic sensors, cameras, etc.), interprets this data, and then sends commands to the robot based on these different elements. The communication between the robot and the control station raises real problems, either with wired communication (cable length, impossibility to close a hermetic door behind the robot, etc.) or wireless communication (wave propagation delay over long distances, presence of an interference system, etc.).

Solving these problems requires the design of robots capable of adapting by themselves in real-time to their environment. Robots must be able to accomplish two main tasks: to perceive their environment and be able to locate and navigate within it. Our works concern the first point, i.e. the perception of the environment of a mobile robot without a priori knowledge. Our research focuses on vision systems since they can get a lot of information on the observed scene in a very short time. A single image is nevertheless not sufficient to reconstruct a three-dimensional scene. This is due to the image formation process, which involves the projection of the 3D scene onto a two dimensional image plane, leading to the loss of depth information. To avoid this problem, several points of view are needed.

We describe in Section II the system we have designed to solve the problem of 3D reconstruction of the environment of a mobile robot, and its modelling. Section III is dedicated to our 3D reconstruction method which is possible without motion, thanks to the stereoscopic structure of our system. We present our main contribution, the adaptation of dynamic programming to an omnidirectional stereoscopic system. Section IV is devoted to experimental results. We highlight the improvements of our method compared to conventional methods. Finally, in the last section, we summarize the key points discussed, and we propose future works.

II. SYSTEM OVERVIEW

Although it is possible to reconstruct the environment with a single camera, a stereoscopic sensor can produce a 3D reconstruction instantaneously (without displacement) and will give better results in dynamic scenes. For these reasons, we developed a stereoscopic system dedicated to mobile robot applications using two catadioptric sensors as shown in Figure 1. These sensors are composed of two hyperbolic mirrors and two cameras. They are placed coaxially to simplify the epipolar geometry since in this configuration, the epipolar lines correspond to the radii of the omnidirectional images. The method to respect the Single Viewpoint Constraint [START_REF] Baker | A theory of single-viewpoint catadioptric image formation[END_REF], the modelling and the calibration of this system are described in [START_REF] Boutteau | An omnidirectional stereoscopic system for mobile robot navigation[END_REF]. The model we used is the unified projection model introduced described in [START_REF] Mei | Single view point omnidirectional camera calibration from planar grids[END_REF].

III. 3D DENSE RECONSTRUCTION

A. Introduction

The work presented in this section deals with 3D dense reconstruction of the environment. It aims to match a maximum of pixels in order to have a 3D model as complete as possible. A disparity map obtained by local methods (see Fig. 7) has many artifacts that lead to a wrong 3D model if mismatches rejection techniques are not implemented. These artifacts are due to ambiguities caused by a lack of texture, by variations of illumination or by the presence of occlusions. If rejection techniques are used, the disparity map is not dense enough to provide an interpretable 3D model.

To improve matching algorithms, it is necessary to impose additional constraints called global constraints as they are applied to all matches. The cost function that will validate the matching is then evaluated on the whole image or on the epipolar line, and not only on a pixel and its neighborhood.

We first present the global constraints commonly used and illustrate them for the case of spherical sensor. Then, we expose the method we have adapted to the omnidirectional vision to take into account these constraints during the matching step.

B. Global constraints applied to omnidirectional sensors

Using similarity criteria such as correlation is generally not sufficient to match primitives unambiguously. A primitive of the first image can indeed resemble to several primitives of the second image, especially when the scene does not present a sufficient texture or when the texture is repetitive.

To overcome these ambiguities, it is necessary to take into account global constraints. There are many global constraints in the literature [START_REF] Pollefeys | Tutorial on 3d modeling from images[END_REF]. We will present only those providing significant improvement, i.e. the uniqueness constraint, the ordering constraint and the disparity continuity. To the best of our knowledge, these constraints have always been used for perspective cameras. Therefore, we propose to illustrate these constraints to spherical sensors.

Uniqueness constraint

The uniqueness constraint expresses the fact that a primitive of an image has at most one match in the other image and vice versa. Thus, in Figure 2a, the point X 1 S1 of the first image has only one corresponding point in the second image. This constraint implies that no pair of 3D points are aligned with the optical center of one of the sensors.

The uniqueness constraint can be justified by assuming the opacity of points, which leads to consider only the physical point closest to the camera ( X 1 in Fig. 2a) if several points are aligned with the optical center.

Ordering constraint

The ordering constraint implies the conservation of the corresponding point order along two epipolar curves. Figure 2b illustrates this constraint. If three points X 1 , X 2 and X 3 are projected respectively in X 1 S1 , X 2 S1 and X 3 S1 onto the first image, the projections of these points into the second image will retain the same order: X 1 S2 , X 2 S2 and X 3 S2 .

Continuity of the disparity constraint

The continuity constraint implies that the observed scene is composed of physical objects that can be approximated by primitives, which means that the disparity of the same object varies continuously. The discontinuities of the disparity appear at the boundaries of physical objects.

C. Proposed method

Dynamic programming (DP) is a well-known technique in conventional vision to take into account the global constraints in the matching step. This is an optimization method under constraints invented by Richard Bellman in 1953, which consists in deducing the optimal solution to a problem from the optimal solutions of simpler problems.

This technique can be applied to the matching problem by searching a path with minimum cost through a matrix composed of all possible matches. The matching will then consider the global constraints, since the cost function is evaluated on the whole sequence to match, and not on the primitives independently.

The first works on the application of dynamic programming to the problem of matching are those of Baker [START_REF] Baker | Depth from edge and intensity based stereo[END_REF], followed by those of Ohta and Kanade [START_REF] Ohta | Stereo by intra-and inter-scanline search using dynamic programming[END_REF]. The matching is achieved not on the pixels, but on the edges, which does not provide a dense 3D reconstruction of the environment. [START_REF] Cox | A maximum likehood stereo algorithm[END_REF] and [START_REF] Bobick | Large occlusion stereo[END_REF] propose to use dynamic programming to perform a dense matching, i.e. by using pixels as primitives for matching, and obtain results with fewer errors than in the case of local methods.

However, the number of works on the application of dynamic programming to omnidirectional images is very small. This can be explained by the fact that the matching must be constrained by the epipolar constraint (the problem must be bi-dimensional). The epipolar geometry of catadioptric sensors is indeed more complex than perspective cameras because the epipolar lines become epipolar conics.

In [START_REF] Wei | Stereo matching of catadioptric panoramic images[END_REF], they have applied dynamic programming to a catadioptric sensor using a hyperboloidal mirror in motion. As the displacement is unknown, the research must be done along the epipolar curves which are, in the general case, conics. The extraction of the pixel values along the epipolar curve and those of their neighbors is consequently a complex stage. Interesting results are highlighted but a dense disparity map is not presented.

Lee [START_REF] Lee | A reliable feature matching method in omnidirectional views for autonomous map generation of a mobile robot[END_REF] uses dynamic programming to match the vertical lines of a structured environment (doors, edges of walls, etc.). His method consists in moving a conical mirror. However, it only takes into account the case of a translation without rotation, which is not feasible with a mobile robot. Moreover, it assumes the robot's movements are known to perform the triangulation, which poses problems of accuracy when this information is obtained by odometry.

Finally, [START_REF] Correa | Omnidirectional stereovision system with two-lobe hyperbolic mirror for robot navigation[END_REF] provides a stereoscopic system based on a two-lobe hyperboloidal mirror. This configuration has the advantage of simplifying the search along the epipolar curves, but the results of matching using dynamic programming are presented only on very simple synthetic images since it consists only of two cubes.

We therefore propose to apply dynamic programming to our omnidirectional images by taking into account the specific configuration of our sensor that simplifies the epipolar geometry. We also use color in a particular color space: H 1 H 2 H 3 to improve performance. It has indeed been demonstrated in [START_REF] Chambon | Color correlation-based matching[END_REF] that this color space works best for matching.

Extracting pixels of the epipolar lines

Dynamic programming can only be applied to twodimensional problems. It is therefore necessary to restrict the search for corresponding pixels with the epipolar constraint: the problem is then reduced to the mapping of pixels of a line in the first image with those of the second image.

The structure of our stereoscopic sensor allows to determine the epipolar lines easily since they correspond to the radii of omnidirectional images. The treatment of the two images will therefore be done by scanning the image angularly and extracting the radii defined by the angle θ (see Figure 3). The angle step is determined by the resolution and/or the desired computation time. For each value of θ, the coordinates of the m pixels of the radius of the bottom sensor image and those of the n pixels of the up sensor image are determined by the Bresenham algorithm.

Building the DP matrix

The principle of dynamic programming is to find a path of optimal cost (minimum or maximum depending on the similarity measure used) in a matrix called DP matrix (see Figure 4). A grid node is a pair of candidates which may have a match, and the optimal path consists of a sequence of nodes.

The first step is to determine the coefficients of this matrix. They are calculated from the first item A[0, 0] to the last element A[m, n]. The path cost is defined as the sum of the costs of the nodes in the path, the component A[i, j] is calculated as follows:

• the maximum of the three previous elements (left, upleft, and up) is looking for:

maximum = max( A[i-1, j], A[i, j -1], A[i-1, j -1]) • the local cost, i.e
. the correlation score of the combination of points (i, j) is added to this maximum:

A[i, j] = maximum + NCC(BottomSensorPixel(i), UpSensorPixel(j))
To compute the correlation score, we use the H 1 H 2 H 3 color space and the Normalized Cross Correlation (NCC) while another quicker measure could have been chosen, but at the expense of results. The filling of the DP matrix elements can be summarized by the algorithm 1.

Algorithm 1 Pseudo-code to evaluate the elements of the DP matrix.

A[0, 0] ← 0

for i = 0 → m do for j = 0 → n do maximum ←max( A[i-1, j], A[i, j -1], A[i-1, j - 1]) A[i, j] ← maximum + NCC(BottomSensorPixel(i), UpSensorPixel(j)) j ← j + 1 end for i ← i + 1 end for

Finding the optimal path

The search for the optimal path is the key step of dynamic programming because it is here that some of the global constraints outlined above are imposed. The optimal path is evaluated from the last element of the DP matrix A[m, n]. For each node (i, j) of the path, we seek to determine the element among its neighbors that will achieve a maximum cost, the cost of the path being the sum of the costs of the nodes.

The ordering constraint is imposed by forcing the path to be monotonous. Thus, the search for the next element of the node (i, j) is done among the three neighbors (i -1, j), (i, j -1) and (i -1, j -1), which prevents any backsliding. The order of the corresponding primitives will be kept along the two epipolar lines. An example of optimal path is given in Figure 4.

Computation of the disparity

The disparity is obtained by taking the difference between i and j for each node of the path. However, this disparity is not necessarily valid since horizontal or vertical transitions tend to associate a pixel of the bottom sensor image to several pixels of the up sensor image (and vice versa), which is in contradiction with the uniqueness constraint. To impose the uniqueness constraint, only the diagonal transitions of the path are considered as valid. The constraint of continuity is also imposed by rejecting matches that introduce a strong gradient of disparity, i.e. long horizontal or vertical transitions. Figure 4 is an example of optimal path obtained where the valid matches are green and where the invalid ones are red. Horizontal or vertical transitions of the optimal path, i.e. invalid matches, appear when there are occlusions in one of the images. Fig. 4. An example of DP matric. The optimal path is represented in green for valid matches and in red for invalid ones.

IV. EXPERIMENTAL RESULTS

A. Matching results

The experimental results presented in this section are intended to justify the choices we made regarding correlation. These choices were guided by the results of existing works and are consolidated by our experiments. In Figures 5 and6, the matches are illustrated by a green line connecting the projection of a same 3D point in both images. The long green segments represent matching errors since the motion between two images is short.

Grayscale vs RGB

To illustrate the impact of the use of color in the matching process, we have compared the results of a matching in grayscale and RGB space on several kind of scenes. Figure 5 illustrates the results obtained in an indoor environment.

Among the 420 detected Harris points, only 110 points were matched in grayscale versus 227 points in color (after a backcorrelation step [START_REF] Werth | A novel bidirectional framework for control and refinement of areabased correlation techniques[END_REF]). The use of color considerably improves the matching process. Comparison between RGB and H 1 H 2 H 3 color spaces The choice of the color space used for correlation has an impact on performance. The number of points considered as correctly matched varies from 227 using the RGB space to 221 using the H 1 H 2 H 3 color space (see Fig. 6). The six points not matched with H 1 H 2 H 3 correspond to mismatches in the RGB space. The H 1 H 2 H 3 color space is better than the RGB space since there are as many correct matches as before for fewer mismatches.

Rejection of mismatches by back-correlation

The ultimate objective of the matching step is to obtain the disparity map reflecting the distance between objects and the camera. The objects closest to the camera are represented by the warmer colors and more distant objects by cold colors. Figure 7 shows the disparity map obtained by a Normalized Cross Correlation using the H 1 H 2 H 3 color space, but without applying the methods of mismatches rejection. The disparity map is very dense, but also very noisy because of the presence of a lot of mismatches.

When the back-correlation is implemented, the disparity map obtained has few matching errors, as illustrated in Figure 8. The map is however less dense, leading to a 3D model composed of too few points.

Local vs global methods Our method was evaluated on the pair of images presented in Figure 3. The environment is very diversified since there are both natural elements (trees, grass) and highly structured elements such as buildings. We have evaluated the contribution of dynamic programming by comparing the disparity map obtained by local methods (Fig. 9a) and imposing global constraints (Fig. 9b) by the method described above. The disparity map obtained by dynamic programming is far more complete than the one provided by local methods. For example, the trees highlighted in red in Figure 10 were not reconstructed with local methods. It is the same for the building structure (in green in Figure 10) even with a weak texture. The matching of the pixels from this building was made possible by dynamic programming that allows the matching of weakly textured regions bounded by remarkable edges. Some items that were already visible in the disparity map obtained with local methods, such as cars highlighted in blue in Figure 10, have surfaces more complete and are artifact-free thanks to the constraint of disparity continuity.

V. CONCLUSION AND FUTURE WORK

This article has been devoted to methods for 3D dense reconstruction of the environment without motion of the sensor. Local methods commonly used in stereovision have Fig. 10. Highlighting of the objects of the disparity map. By using the global method, the 3D reconstruction of the building (in green), trees (in red) and cars (in blue) is more complete. limitations, restricting their use in a large environment. As a result, we proposed a generalization of global constraints to omnidirectional sensors. The application of these constraints through dynamic programming greatly improves the density of the disparity map, while guaranteeing a relatively low mismatch rate. Moreover, we demonstrated that the use of color in the H 1 H 2 H 3 space improves the results significantly. Dense 3D reconstruction could be improved by using a correlation window in adequation with the geometry of the sensor. Indeed, the square correlation window used on classical images has no meaning on omnidirectional images. An interesting approach could be to work directly on the sphere for the matching step.

Fig. 1 .

 1 Fig. 1. View of our catadioptric stereovision sensor mounted on a Pioneer robot. Baseline is around 20cm. The overall height of the sensor is 40cm.

Fig. 2 .

 2 Fig. 2. Global constraints applied to omnidirectional sensors. (a) Uniqueness Constraint -(b) Ordering constraint

Fig. 3 .

 3 Fig. 3. Extraction of the radii in the bottom and up sensors images.

Fig. 5 .

 5 Fig. 5. Comparison of the matching using grayscale (left) and color (right).The number of correct matches is multiplied by two using color information.

Fig. 6 .

 6 Fig. 6. Comparison of the matching in RGB (left) and in H 1 H 2 H 3 (right) color spaces. The use of the H1H2H3 color space reduces the number of mismatches.

Fig. 7 .

 7 Fig. 7. Disparity map obtained with local methods without mismatches rejection. (Left) Omnidirectional image -(Right) Disparity map.

Fig. 8 .

 8 Fig. 8. Disparity map obtained by local methods with mismatches rejection. (Left) Omnidirectional image -(Right) Disparity map.

Fig. 9 .

 9 Fig. 9. Disparity maps using local (a) and global (b) methods.


Chŏngjo and his time

One might say that all intellectual effort and ideological struggle in the political history of the Chosǒn 朝鮮 period was due to the ambiguity regarding dynastic sovereignty that existed between the monarch and literati groups. Ever since the 17th century and its invasions and wars, literati factions had consolidated their position both in the provinces and the central government. From the late seventeenth to the early eighteenth century (1680-1727), relations between literati factions were characterized by sectarian and intolerant attitudes towards each other. One-party autocracy lasting for about half a century saw tragic conflicts, several reversals and crises between the principal groups at the center of power and beyond. Such a situation revealed the weakness of party politics and infringed upon royal power. In the middle of the eighteenth century, the political climate led to the "impartiality policy" proclaimed by King Yŏngjo 英祖 (r. 1724-1776) who intended to abolish the factions and reinforce the king's political authority. While he still had to make an effort to be acknowledged by the literati as a "sage king", Chŏngjo 正祖 (r. 1776-1800), Yŏngjo's grandson and successor on the throne, whose authority was more consolidated thanks to his grandfather, could problematize and reinterpret certain Neo-Confucian notions. His reading of the Great Learning differs to a considerable extent from the political orientation of Zhu Xi and may be construed as an ideological stratagem to reinforce royal authority. Zhu Xi separated the transmission of Confucian doctrine tot'ong 道統 from that of kingship wangt'ong 王統, expanded the notion that every learned man was capable of realizing the political ideal, placed politics ch'i 治 under the control of learning hak 學, and finally strove to prevent the king's absolute authority and centralized power. King Chŏngjo's interpretation, however, removed the boundary between the two types of transmission and the order between governing ch'i 治 and teaching kyo 敎. It underlined disparities in human nature, as well as in terms of social status, and linked it to personal differences in governing, thus highlighting the king's political uniqueness.

Chŏngjo's works on the Great Learning

Like his grandfather, King Chŏngjo took a special interest in the Great Learning. to the original idea of the Great Learning and recover its holism. According to him, both the Extended Explanations and the Complements to the Extended Explanations highlighted its own system of Sage-Learning : the first put emphasis on the ruler's "learning" and "selfperfection", while the latter supported more the monarch's practical rule by complementing the parts on "ordering the state" and "making the world peaceful". 3 This is also related to the king's assessment of Yi I's (李珥, 1536-84) Sǒnghak chibyo 聖學輯要 or Essentials of Sage-Learning, which had been read in royal lectures since 1680 and had acquired authority at the Chosŏn court as a teaching material for Sage-Learning. The fact that the king personally developed instruction materials suggests that he was not satisfied with earlier textbooks and was looking for an alternative worldview that would correspond to the new situation. 4 His views on the Great Learning can be read in the relevant parts (recorded in 1781, 1783, 1784, 1786 and 1787) of the Kyǒngsa kangǔi 經史講義 or Lectures on the Classics and Histories, a collection of questions raised by the king and answers provided by his literati high officials, during lectures on the Confucian Classics and some canonical texts on history and administration. 5 His questions were not simple interrogations, but were almost always preceded by some definitions or remarks in which he analyzed, deconstructed or challenged Neo-Confucian commentaries of the Classics

Inquiries and interpretations of the Great Learning

In the Lectures, Chŏngjo seems to be interested mainly in what a particular term corresponds to in reality. Hereafter we will examine several major terms from the Great Learning that show his understanding of the political way.

Sǒng 性 or "Nature" and myǒngdǒk 明德 or "illustrious virtue" are different one from the other

With regard to what "illustrious virtue" is, he tries to understand it in terms of the dichotomy between li 理 ou "principle" and ki 氣 ou "vital force" or between sǒng 性 ou "nature" and sim 心 or "heart-mind". In Zhu Xi's explanation that "illustrious virtue" is "ku chungni i ǔng mansa cha" 具衆理而應萬事者 or "endowed with every principle and meets all affairs", he sees a problem in that the first part of the phrase refers to "principle" and the second part to "vital force": how can "illustrious virtue" be two radically different things at the same time? Actually, Zhu Xi left open the possibility to interpret "illustrious virtue" as "heart-mind"7 and to depict it as being action and capability limited by personal disposition.8

Within these terms, it is impossible to firmly consider "illustrious virtue" as a capability equally attributed to every human being. His explanations on "illustrious virtue" finally left room for some Neo-Confucian ideas to be re-interpreted in a political direction other than that which he supported.

At the beginning of his royal lectures on the Classics and the Histories, in 1781, Chŏngjo seems to refer to the oneness of "illustrious virtue" in everybody. 9 However, in his later writings, his words can be understood as meaning that everybody possesses it, and that the brightness of one can thus brighten that of another. In other texts, however, he consistently argues that human beings do not have the same "illustrious virtue". It depends on each person's make-up and disposition. Even if "illustrious virtue" is the same thing in every human being, it depends on one's personal capability and social standing to shine forth and put it into practice. 10

In 1786, by showing some cases where Cheng Hao and Zhu Xi described "nature" as being "vital force", Chŏngjo argues that "nature" can be seen as being "vital force". 11

According to the dualistic theory of human nature, "nature" combines ponyǒn chi sǒng 本然之性 or "original nature", which is pure and universal, and kijil chi sǒng 氣質之性 or "derived nature", which is generated by material force and endowed in each individual being.

While preserving these two expressions, the king's reinterpretation of the notion redefines these terms, releasing the tension inherent in this dualistic theory: "original nature" stands for the ultimate goal of "nature" and "derived nature" indicates its substance/property. Defined as such, we can refer to the "nature" of each one with its personal attributes.

Chŏngjo believes that the understanding of one's lot, in particular one's social standing, is a question that has to be settled prior to understanding one's myǒngmyǒng 明命 or "illustrious decree from Heaven". 12 According to his view, for one's "illustrious virtue" to be put into practice, it cannot be inferred from li principle but can be approached through understanding one's individual disposition. The expression myǒng myǒngdǒk 明明德 or "illustrate illustrious virtue" means bringing to light the ultimate meaning inherent in one's existence and conditions. 13 The position of the monarch is unique and proper to governing Everyone can thus participate in politics in accordance with his own limits and means.

Each person has a role to play. However, only the king can integrate all parts, establish criteria and accomplish politics. 14 As for his subjects, they have to keep to their place and fulfill their duty. 15 Arguing that the king is in a position to make decisions concerning all matters of state governance, Chŏngjo understands the monarch as a unique individual endowed with ultimate universality and equity, who represents the common interests of all, while the others pursue only their particular interests. Here again learning through experience has precedence over understanding through thinking.

In Neo-Confucianism, the imagery of li il pun su 理一分殊 or "one principle and many manifestations" usually has a moral and cosmogonal dimension. Chŏngjo applies it to his idea of the socio-political order and compares his monarchical position to the li il 理一 or "one principle" or the t'aegǔk 太極 or "supreme ultimate", and his people to "many manifestations". In 1798, he even called himself manch'ǒn myǒngwǒl chuin ong 萬川明月主人翁 or "Esteemed Master of the Moon in all Rivers". 16 This imagery of the unitary moon being reflected in all bodies of water is used to define his own being and standing as a monarch; it is closely connected with his notion of "illustrious virtue" (see supra). 17 The unity of the people's practice of virtue is assured by the kingthe origin of politics and order. From a Neo-Confucian perspective, political legitimacy is drawn from the worthiness of the literati group and reflected in the monarch, who is regarded as their symbolic delegate. For Chŏngjo, however, political justification and motivation derive from the signification of the king's being and are mirrored in his people. He thus seeks to recover the ancient monarchical authority that existed prior to the acceptance of Neo-Confucian ideology, by reinterpreting the latter's cosmogony.

We notice also that his interpretation conceals an "unspoken" aspect, a deliberately omitted element between "one principle" and "many manifestations"; an "other" to be controlled or excluded between him and his people, revealing that the king's discourse is developed with a view of gaining political hegemony and excluding the literati. 18 As in his "impartiality policy" in which he employs literati-officials only according to their personal talents and does not question their political affiliation, he silences the claims of the literati class on intellectual and thereby political hegemony by excluding them from his "cosmogony."

The search for sin min 新民 or "bringing the people to a state of renewal"

The commentary on the term sin min 新民 cites three ancients texts including the following expressions: il sin, chak sin min, ki myǒng yu sin 日新, 作新民, 其命惟新.

However, Chŏngjo finds in none of these terms any allusion to activity in which a king could expect to renovate the people. On his repeated interrogations, most of the officials reproduce 16 "Manch'ǒn myǒngwǒl chuin ong 萬川明月主人翁自序" (1789), Sǒin 序引, in HJCS, vol. 10. 17 Ibid. for him the stereotyped answer that the self-cultivation of the ruler could lead everything to correctness. 19 Through his tenacious inquiries on this subject, he shows his dissatisfaction with the Confucian non-action doctrine for government and his belief in active state government not based on self-cultivation but on forceful monarchical authority. Doubting quietist or introspective learning, he also constantly raises questions about the nature of working on kyǒng 敬 or "reverence" and chon sim yang sǒng 存心養性 or "preserving the heart-mind and nourishing nature".

The kyǒng mul ch'i chi 格物致知 or "Investigation of things" and the "Extension of one's knowledge" Chŏngjo is one of those scholars who consider the concepts of "investigation of things"

and "extension of one's knowledge" in the context of the original text. For him, these "things" are the same as in the expression mul yu pon mal 物有本末 or "things have their root and their branches" and this "knowledge" is no other than that which we find in chi so sǒn hu 知 所先後 or "to know what is first and what is last". Therefore, according to him, the actions of "investigating" and "extending" cannot apply beyond the affairs of "illustrating illustrious virtue" and "renovating the people". They just indicate the exploration of one's inner depth and do not reach to the objective and exclusive learning of external realities. He therefore raises doubts about the reason why Zhu Xi added an interpretative note to the term "investigating things" to explain it as a process of approaching everything in the world and apprehending their principles. He especially wondered whether this total investigation of everything in the world was necessary for all scholars.

Concluding remarks

We notice two major characteristics in Chŏngjo's reading of the Great Learning. The first is his theoretical construction of a vision to justify the monarch's absolute authority. The claim for the king's supreme position through hermeneutics from the Great Learning was not new and it was always challenged by the literati, who propagated collective rule by the monarch and themselves. The "impartiality policy" of King Yŏngjo, justified merely by a situational logic, had a theoretical limitation. A reinterpretation of the Classics was needed to fundamentally legitimize the reestablishment of an "appropriate" relationship between sovereign and subject, and the shift to a system centered on monarchical authority. Interlinked with his effort in this respect, Chŏngjo's reinterpretation of the Great Learning led to a political orientation which differed from the Neo-Confucian vision. One of the most interesting features here is that he did it while preserving Neo-Confucian language.

The second point is his effort to overcome the Neo-Confucian introspective and quietist way, with a view to establishing active, powerful and pragmatic governance. As for this point, his scholarly enterprise on the Great Learning should be considered as having a more extended and complex scope. His stance was consistent with the critical and pragmatic current among his contemporaries when reading the Confucian Classics, and reflected most of the debates about the issues involved. In fact, he also widely consulted ideas and commentaries emanating from outside of the hegemonic, or so-called "orthodox", group. The king's reading of the Classics must be evaluated above all in the context of the period during which he lived. However, he was in a very special position, and this makes his influence worthy of our extended consideration. As a powerful monarch and ardent Confucian scholar, along with his new vision of the Classics, he also extended extraordinary efforts to, among other things, the education of his literati-officials, whom he wanted to support his new political perspective, the restoration of a "correct" Confucian literature, and the publication and diffusion of Confucian knowledge. By alternating between renovation and restoration of the Confucian tradition, he undoubtedly contributed to bringing about considerable changes to the socio-cultural landscape of the literati class and to the intellectual trends of the following generation. In fact, such a remarkable thinker and author as Chŏng Yagyong acknowledged Chŏngjo's intellectual influence on him and, one century later, Kojong, the first emperor of the Great Han, took him as his model. In this sense, the influence Chŏngjo exerted on the intellectual and cultural world of nineteenth-century literati seems to be a relevant and interesting research topic, which has so far not sufficiently attracted our attention.

2

  The most important work he left regarding it is the Taehak yuǔi 大學類義 or Classification and (re)connection of the Explanations on the Great Learning (published in 1805). It is an anthological work compiled from Zhen Dexiu's (眞德秀, 1178-1235) Taehak yǒnǔi (Daxue yanyi in Chinese) 大學衍義 or Extended Explanations on the Great Learning and Qiu Jun's (丘濬, 1420-95) Taehak yǒnǔi po (Daxue yanyi bu in Chinese) 大學衍義補 or Complements to the Extended Explanations on the Great Learning. Apparently the king intended to return

18

  Jeremy R. CARRETTE, Foucault and Religion -Spiritual Corporality and Political Spirituality, London & New York: Routledge, 2000, p. 129.

  YI T'aejin 이태진, "Chŏngjo ǔi Taehak t'amgu wa saeroun kunjuron" 정조의 대학 탐구와 새로운 군주론, in Yi Hoejae ǔi sasang kwa kǔ segye 이회재의 사상과 그 세계, Daedong Institute for Korean Studies 성균관대학교 대동문화연구원, 1992, p. 265.

2 3 YUN Chŏng 윤정, "Chŏngjo ǔi Taekak ryuǔi p'yŏnch'an kwa Sŏnghak chibyo" 정조의 대학류의편찬과 성학집요, Nammyŏnghak yŏn'gu 남명학연구, n° 23 (2007) , p. 360-371. 4 Ibid, p. 348. 5 Kyŏngsa kangŭi 經史講義, in Hongjae chŏnsŏ 弘齋全書 (published in 1814, 184 parts 卷, 100 volumes 冊, edition of Kyujanggak (奎 572) and http://www.itkc.or.kr., hereafter HJCS), vols. 67-70. Other documents in which we can get an idea of his views about the Great Learning are the Kosik 故寔 or Practical Lessons from the Ancient Histories (1794) and the Chǔngjǒn ch'urok 曾傳秋錄 or Autumn Writings about the Transmitted Texts from Zengzi (1799), both of which are records of discussions on the text that the king exchanged with his subjects. Here the king answered his subjects' questions. 6

I would like to express my gratitude to Professor Martina Deuchler for having reviewed my text and made it correct and legible.

"Taehak" 大學, in Kosik 故寔, in HJCS, vol. 129 ; Chŭngjŏn ch'urok 曾傳秋錄, in HJCS, vol. 126.

Daxue zhangju 大學章句 : Daxue 大學, in Kanbun taikei漢文大系, vol.1, revised edition in 1972, p. 5.

Daxue huwen 大學或問 , in Zhuzi quanshu 朱子全書, vol. 6, Shanghai guji chubanshe 上海古籍出版社, 2002, p. 508.

Kyŏngsa kangŭi, 4, in HJCS vol. 67.

"Jinxin 盡心 shang 上", in Mengzi 孟子 (Mengzi tingben 孟子定本, in Kanbun taikei 漢文大系, vol.1, revised edition in 1972, p.12).