Process for producing cartographic data by stereo vision

[0002] The present invention relates to processes for producing cartographic data in three dimensions from n two-dimensional images of a scene, provided by n sensors having different points of view of the scene.

[0003] It has for a very long time been known to define the position in space of structures which are present in a scene and can be seen in two images taken under different viewing angles, using stereoscopic techniques. This process has been generalized to the case of n images, n being an integer greater than 2, these n images constituting a stereoscopic system having a plurality of baselines.

[0004] Processes which include the following steps are, in particular, known:

[0005] the n sensors are calibrated (by using 3D knowledge of their relative position with respect to the scene which is observed and/or pattern recognition processes, so as to provide parameters of n models F_i(x,y,z), each defining the relationship between a point in the scene, with coordinates x,y,z, and the coordinates (p,q)_iof its projection into each of the n images, for i ranging from 1 to n;

[0006] the n images are set in correspondence, so as to locate the coordinates of the projection in the images of the same point in three-dimensional space;

[0007] 3D reconstruction is performed, consisting in obtaining the coordinates x, y and z of the 3D point corresponding to each match between images, on the basis of knowledge of the models F_i, and the matched image points.

[0008] A process of this type is described in the article by Sing Bing Kang et al. “A Multibaseline Stereo System with Active Illumination and Real-time Image Acquisition”, Proceedings IEEE Int. Conf. on Computer Vision, pages 88-93, June 1995. The process proposed in this article employs four cameras whose optical axes converge approximately at the same point. The image provided by one of the cameras is chosen as a reference. Given that the axes of the cameras are not parallel, the associated epipolar lines are not parallel to the image lines. In order to simplify recovery of the altitude from the stereoscopic images, that is to say 3D reconstruction, the images are subjected to rectification which converts each original pair of images into another pair such that the epipolar lines resulting therefrom are parallel, equal and coincident with image scanning lines. The correspondence method uses a variable λ, defined as the distance from the optical centre along the viewing axis passing through the optical centre of the reference camera and the point in question, in order to calculate the search zone for potential homologues in the images to be matched with the reference image. Use of this variable λ inevitably leads to a model with non-linear transition between the images, which makes the calculations more complicated. The strategy taught by the article, consisting in assigning equal significance to each pair, is a source of error whenever points are masked in one or more of the images.

[0009] A detailed study of algorithms for merging a plurality of representations in order to recover 3D cartographic data from a plurality of 2D images of a scene is given in the thesis at the Universit{acute over (e)} de Paris Sud, Centre d'Orsay, May 1988 “Construction et Fusion de Representations Visuelles 3D: Applications {grave over (a)} la Robotique Mobile” [Constructing and Merging 3D Visual Representations: Applications in Mobile Robotics] by N. Ayache.

[0010] An object of the present invention is to provide a process for producing cartographic data which is improved, in particular in that it makes it easier to establish multi-pair correspondence of n images (n being an integer greater than 2) and is flexible enough to adapt readily to a number of fields, such as:

[0011] detection of obstacles and autonomous guidance of a mobile robot in a fixed scene,

[0012] 3D modelling of real sites,

[0013] mapping,

[0014] aerial reconnaissance, for obtaining a terrain profile,

[0015] the modelling of optimum trajectories during the preparation of an air mission.

[0016] To this end, the process uses in particular the observation that, irrespective of the nature of the sensors (pinhole, linear array of photodetector sites, scanning sensor) and their relative position when the images are being acquired (on condition that they are stereoscopic and that there is overlap between a plurality of images) it is always possible to find n−1 resemblance curves, each corresponding to a pair of images including a same reference image, as a function of the disparity, defined in an arbitrary one of the pairs. To do this, a change of reference frame of the resemblance curves is performed, which can always be done with an affine model for changing from the disparity of one pair to that of another pair.

[0017] It will in general be possible to liken the disparity to the curvilinear abscissa of one point relative to another along the epipolar line; it can be measured as a number of pixels in the frequent case of an image represented by elementary points which are each assigned at least one radiometric value (luminance and/or chrominance).

[0018] The invention provides, in particular, a process for producing cartographic data in three dimensions from n two-dimensional images of the scene, which are provided by n sensors with different points of view, n being an integer greater than 2, comprising the steps of:

[0019] (a) calibrating each sensor of order i in order to estimate the parameters of n models F_i(x,y,z) defining the relationship between the coordinates x,y,z of a point in the scene and the coordinates (p,q)_iof its projection into the image i among the n images;

[0020] (b) matching each of the n−1 pairs of images, all including the same reference image chosen from among the n images, by looking for the homologue of each pixel or zone in the reference image along the corresponding epipolar of the other image in the pair;

[0021] (c) in each of the n−1 pairs of two images, each comprising one reference image, and for each pixel or zone in the reference image, establishing a resemblance curve (curve of variation of a similarity index) as a function of the disparity along the epipolar of the other image;

[0022] (d) bringing all curves into a common reference frame using a model, for example an affine model, in order to match the largest possible number of images;

[0023] (e) summing the curves, while possibly removing each peak located at a singular disparity relative to those of all the other curves, and adopting the highest peak of the resultant curve; and

[0024] (f) computing the coordinates x,y,z from the disparity of the adopted peak and the parameters of the n models F_i(x,y,z).

[0025] It is also possible to calculate a plurality of disparity images while taking different images as a reference. The merging may be carried out after having calculated the coordinates in three dimensions; it may also be carried out at the disparity image level, this being an advantageous solution when the sensors are calibrated in a projective space.

[0026] The results of multipair correspondence or matching may be merged using a majority vote, by assigning a higher weighting coefficient to the peaks corresponding to the points of view most distanced from the reference image.

[0027] The process which has just been described makes it possible, in most cases, to alleviate the difficulties encountered in order to be certain to find the homologue of a point of the image in one or more other images. The use of a number n greater than 2 makes it possible to avoid the consequences of occultation in one or more images. The geometrical coherence of the multiple matches reduces the errors and removes ambiguities. The presence of images having similar points of view makes it possible to process images which resemble one another and have little occultation between them; the use of images having distant points of view makes it possible to obtain accurate 3D information.

[0028] The abovementioned characteristics, as well as others, will become more clearly apparent on reading the following description of particular embodiments of the invention, which are given by way of non-limiting example. The description refers to the accompanying drawings.

[0029] FIG. 1 is a diagram representing one possible arrangement of the sensors and showing the role of the rectification;

[0030] FIG. 2 shows the principle of the matches of a point by searching along epipolar portions;

[0031] FIG. 3 shows examples of curves of variation of a resemblance index as a function of the disparity;

[0032] FIG. 4 represents an example of a diagram for treating images in view of multi-image matching;

[0033] FIG. 5 shows a merging process for the multi-image processing;

[0034] FIG. 6 shows one way of referencing resemblance curves with respect to a plane; and

[0035] FIGS. 7A and 7B, which show resemblance curves as a function of disparity, show the benefit of curve selection.

[0036] The general architecture of the process, which is retained irrespective of the application, will be described first before envisaging particular cases. For simplicity, those parts of the process according to the invention which are already well known will be recalled only briefly, and reference may be made to the documents already mentioned, as well as to the following:

[0037] As regards the simple case of sensors of the pinhole type, all of which are identical, providing images acquired in coplanar positions at the same altitude, to the article by R. Y. Tsai “Multiframe Image Point Matching and 3-D Surface Reconstruction” IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-5, No. 2, pages 159-164, March 1983;

[0038] As regards mapping from calibrated digital aerial image maps, to the article by L. Gabet et al. “Construction Automatique de Mod{grave over (e)}le Num{acute over (e)}rique de Terrain {grave over (a)} Haute R{acute over (e)}solution en Zone Urbaine” [Automatic Digital Terrain Model Construction with High Resolution in an Urban Area], Bul. SFPT No. 135, pages 9-25, 1994.

[0039] The contents of such documents are included in the specification by reference.

[0040] A process according to the invention has three essential phases:

[0041] calibrating the sensors (step (a) above),

[0042] setting the images in correspondence, or matching the images, involving merging at least n multipair correspondence results, these results being the disparity maps obtained directly or the digital elevation models (DEM) calculated therefrom,

[0043] 3D reconstruction (step (f)).

[0044] These three phases will be described in succession.

[0045] Calibration

[0046] The purpose of calibrating the sensors is to provide an estimate of the parameters of the models F_i(x,y,z) and F_i(x,y,z) which define the relationship between the coordinates x,y,z of a 3D point in the scene and the 2D coordinates (p,q) of its projection into the image plane, respectively π₁and π_i.

[0047] The process requires prior calibration of the sensors. In the simple case of just two sensors, which is illustrated in FIG. 1, the purpose of the calibration is to estimate the parameters of the models

[0048] F₁(x,y,z)

[0049] F₂(x,y,z)

[0050] which define the relationship between a point S_kin the scene, defined in three dimensions by its coordinates x, y and z and the coordinates (p,q)_iof its projection into the image plane π_i(with i=1 or 2).

[0051] The calibration is performed differently according to the nature of the sensors, using known processes, for example the method described in the article by Ayache mentioned above. It is possible to use correspondences between homologous points in the images, defined manually or obtained by pattern recognition techniques related to neighbourhoods.

[0052] The conclusion of this step provides the set of models F_i(x,y,z) with i^ε{1, . . . , n} and search directions for the corresponding points, these being those of the epipolars.

[0053] However, when calibration is carried out without initial 3D knowledge of the scene, the 3D reconstruction can be defined, when conventional methods are used, only to within a projective transformation of the 3D projective space. It will be seen below that the multipair process according to the invention is independent of the geometry and makes it possible to accommodate the altitude variations in the scene.

[0054] Multipair Correspondence

[0055] The images are matched by looking for the homologue of each point P of a reference image, generally defined with its neighbourhood in the form of a label, along the epipolars E₂, E₃, . . . of the other images (FIG. 2). To this end, similarity curves are established as a function of the disparity d₁₂, d₁₃, . . . (lines A and B). The similarity index S may, in particular, be a cross-correlation coefficient or a resemblance index pertaining to contours or regions. All the curves are then transformed into a common reference frame, for example d₁₃, which will outline probable matching with a sub-pixel accuracy corresponding to the coincidence of the peaks (line C in FIG. 3).

[0056] A change of reference frame is necessary if it is desired to express all the curves in the same frame for later merging them; this uses an affine model developed on the basis of the geometry with which the images are acquired. This model is of the following form, for an example involving three images in all:

[0057] d₁₃=a(η,μ)d₁₂+b(η,μ)

[0058] where d denotes the disparity, η and μ denote the parameters which define the geometry of the pairs (1,2) and (1,3) for a position p on the epipolar of the primitive (point, contour or region) to be matched in image 1.

[0059] When the calibration is carried out without 3D knowledge of the scene, the coefficients a(η,μ) and b(η,μ) of the affine model are calculated by using rectification of the images, this being intended to convert each pair of plane 2D images into another pair such that the epipolar lines are parallel and coincident with the image lines or columns, as indicated in FIG. 1 where the rectified conjugate epipolars are indicated in the virtual retinal planes Γ_1,2and Γ_2,1for the points I¹_kand I²_kin the image planes π₁and π₂. The rectification facilitates the correspondence by making it possible to establish the curves in FIG. 3 immediately.

[0060] By way of example, it may be indicated that the transformation model (p,q)=F_i(x,y,z) for a pinhole model is, in projective coordinates, a linear function of the form:

[0061] {tilde over (u)}=P{tilde over (x)}

[0062] $\mathrm{with}\tilde{u}=\left[\begin{array}{c}\mathrm{wp}\\ \mathrm{wq}\\ w\end{array}\right]\mathrm{And}\tilde{x}=\left[\begin{array}{c}\mathrm{sx}\\ \mathrm{sy}\\ \mathrm{sz}\\ s\end{array}\right]$

[0063] P is a 3×4 matrix defined to within a multiplicative factor; w and s are multiplicative factors.

[0064] In order to determine the matrix, it is necessary to have 11 parameters. These can be determined on condition that at least six homologous points are available.

[0065] If just two images are considered, it is possible to define a model for transition from a 3D point in the scene to the coordinates of its projection into each of the rectified images 1 and 2; the perspective projection matrices M and N for image 1 and image 2 defining the transition models are:

[0066] {right arrow over (u)}₁=M{right arrow over (x)}

[0067] {right arrow over (u)}₂=N{right arrow over (x)}

[0068] In order to calculate the coefficients of the matrixes M and N, to within a scale factor, it is necessary to satisfy a number of constraints:

[0069] parallel epipolar lines in the two images (epipoles at infinity);

[0070] for any arbitrary 3D point S_knot belonging to the focal plane of the cameras defined after rectification, identical ordinates of the pixels, represented by the points I_k^1,2and I_k^2,1(FIG. 1);

[0071] coordinates of the optical centres C₁and C₂that are invariant in terms of the rectification.

[0072] The equations to which these constraints lead are given in the Ayache document mentioned above.

[0073] A solution to these equations can be found so as to limit the distortions to the rectified images. By way of example, the following expressions are given for the matrices M and N: $M=\left[\begin{array}{cc}{\alpha \left(t\bigwedge c_1\right)}^T& 0\\ {\beta \left(c_1\bigwedge c_2\right)}^T& 0\\ {\left(\left(c_1-c_2\right)\bigwedge t\right)}^T& c_1^T\left(c_2\bigwedge t\right)\end{array}\right]$ $N=\left[\begin{array}{cc}{\alpha \left(t\bigwedge c_2\right)}^T& 0\\ {\beta \left(c_1\bigwedge c_2\right)}^T& 0\\ {\left(\left(c_1-c_2\right)\bigwedge t\right)}^T& c_1^T\left(c_2\bigwedge t\right)\end{array}\right]$

[0074] where:

[0075] c₁and c₂are the vectors of the 3D coordinates of the optical centres c₁and c₂of the pinhole cameras;

[0076] α and β are scale factors, conditioning the deformation of the rectified images in the direction of the epipolars, on the one hand, and in the orthogonal direction, on the other hand (if the epipolars after rectification are chosen to be horizontal);

[0077] f is a vector dictating the orientation of the rectification plane (making it possible to limit the distortions to the rectified images).

[0078] The projective geometry also makes it possible to calculate the matrices M and N by means of the fundamental matrices. A description of a posible approach of this type will be found in the thesis of Ecole Polytechnique “Vision st{acute over (e)}r{acute over (e)}oscopique et propri{acute over (e)}t{acute over (e)}s diff{acute over (e)}rentielles des surfaces” [Stereoscopic Vision and Differential Surface Properties] by F. Devernay.

[0079] The matrices for passing from the actual (or acquired) images to the rectified images can be deduced from the matrices M and N, for example in the manner indicated by the Ayache document.

[0080] It is then necessary to define an inter-disparity model by its coefficients a(λ,μ) and b(λ,μ) such that:

[0081] d₁₃(p)=a(η,μ)·d₁₂+b(η,μ)

[0082] This model makes the transfer from the disparity d₁₂(p) of point p in the pair of rectified images 1 and 2 to the disparity dl₃(p) in the pair formed by the images 1 and 3. η denotes the pair of images (1, 2) and μ denotes the pair of images (1, 3).

[0083] The parametric equations of the lines of sight in camera 1, which are defined on the basis of the coordinates of the pixel p in the rectified image in the η pair geometry and in the μ pair geometry are:

[0084] {right arrow over (x)}=c₁+λ₁^ηt_η

[0085] and

[0086] {right arrow over (x)}=c₁+λ₁^μt_μ

[0087] where {right arrow over (x)} denotes the 3D coordinates of a point c₁(coordinates of the optical centre of camera 1) and t_η and t_μ are the director vectors defined simply as a function of the terms in the matrix M:

[0088] t_η=ε_η(m₁^η−p₁^ηm₃^η){circumflex over ( )}(m₂^η−q₁^ηm₃^η)

[0089] t_μ=ε_μ(m₁^μ−p₁^μm₃^μ){circumflex over ( )}(m₂^μ−q₁^μm₃^μ)

[0090] where ε denotes a standardization coefficient for the vector t.

[0091] It can be deduced therefrom that λ₁^η=τ^μ.η·λ₁^η with τ^μ.η=(t_η^T·t_μ)/□t_η□

[0092] The expressions for a and b can be deduced therefrom directly $\alpha \left(\eta ,\mu \right)=\frac{k_1^{\mu }·{\tau }^{\mu ,\eta }}{k_1^{\eta }}$ $b\left(\eta ,\mu \right)=k_2^{\mu }-\frac{k_1^{\mu }}{k_1^{\eta }}{\stackrel{<}{k}}_2^{\eta }·{\tau }^{\mu ,\eta }$

[0093] The simple, particular case in which the sensors are of the pinhole type will again be considered. The multipair matching can be carried out by the approach schematically represented in FIG. 4, in the case of four real images, numbered 1, 2, 3 and 4. After rectification, a point P in image 1 which is taken as the reference will be looked for on the corresponding epipolars of images 2, 3 and 4. Using the notation shown in FIG. 4, the multipair matches are made between the images g_iand d_i, with

[0094] iε{1,2,3}

[0095] The coefficients a and b of the affine model for transition from the disparity of one pair to the disparity of another pair can be expressed simply as a function of the position of the pixel P to be matched, the geometry of the original pair and that of the destination pair.

[0096] As indicated above, the matches of the obtained set are then merged by taking n different images as reference (n=4 in the case of FIG. 4). This operation can be performed after having calculated the digital terrain models (DTM) or digital elevation models (DEM), as indicated in FIG. 5. However, it may be performed by merging the disparity maps, in order to obtain a final disparity map, before determining the final DEM.

[0097] Preferably, merging is carried out on the principle of majority votes or selection of a median value. Weighting is used when the votes are taken. This is calculated by assigning a maximum weight to the points of view most distant from the reference image.

[0098] When the geometry of the sensors is known (pinhole, scanner or linear array model), a few indications will be given regarding the corresponding or matching method in the case of two images 1 and 2, image I being the reference image. The notation is that in FIG. 6. The referencing takes account of a plane Σ at a constant altitude z=z₀. The functions F_iare known and, in the case of pinhole models, are the perspective projection matrices M_i. It is consequently always possible to express the coordinates (p,q) in two dimensions in the plane Σ for z=z₀on the basis of two pixels (p₁,q₁) and (p₂,q₂) set in correspondence in the images 1 and 2.

[0099] If (x₁, y₁) is the point in the plane Σ which is the image of the pixel (p₁,q₁) to be matched in image 1, and (x₂,y₂) is the image of the pixel (p_2,q₂) in image 2, then the disparity associated with this potential match is defined as the Euclidian distance in the plane Σ between points (x₁,y₁) and (x_{2, y2}) $d_{12}\left(x_1,y_1\right)=\sqrt{{\left(x_1-x_2\right)}^2+{\left(y_1-y_2\right)}^2}$

[0100] On the basis of this definition of the disparity, calculation shows that the disparity in a pair of images (1, 2) can be expressed in the form: $d_{12}\left(x_1,y_1\right)=\sqrt{{\left(a_n-a_m\right)}^2+{\left(c_n-c_m\right)}^2}·\left(z_0-z\right)$

[0101] where a_n, a_m, c_nand c_mare the coefficients which can be deduced from the linear systems which, for constant z₀, connect p and q and the vector {right arrow over (m)} defined above in each image.

[0102] In the case of the images 1 and 3, the following relationship would similarly be obtained: $d_{13}\left(x_1,y_1\right)=\sqrt{{\left(a_p-a_m\right)}^2+{\left(c_p-c_m\right)}^2}·\left(z_0-z\right)$

[0103] where a_pand c_pplay the same role as a_nand c_n. The linear model for inter-disparity transition between the pair η of images (1, 2) and the pair μ of images (1, 3), when the plane Σ is specified, can be written very simply in the form:

[0104] d₁₃(x₁, y₁)=a(η,μ)·d₁₂(x₁, y₁)

[0105] with $\alpha \left(\eta ,\mu \right)=\frac{\sqrt{{\left(a_p-a_m\right)}^2+{\left(c_p-c_m\right)}^2}}{\sqrt{{\left(a_n-a_m\right)}^2+{\left(c_p-c_m\right)}^2}}$

[0106] Using a calculation which may be performed in parallel, it is thus possible to establish all the similarity curves with a view to matching the peaks that correspond with one another.

[0107] During the matching, it is expedient to remove the peaks due to occultation of points in one of the images of the pair. As an example, FIG. 7B shows the resemblance curves as a function of the disparity for four pairs. The pixel in the reference image is masked on the other image in pair 4, which shows peaks for disparities where the other curves do not have a maximum. In this case, it is expedient to remove curve 4 to find the correct disparity for the masked pixel. This result may, in particular, be obtained by a majority vote.