FR2779854A1 - Cartographic digital data production method for generating three dimensional coordinates from two dimensional pictures - Google Patents

Abstract

Using a first criteria, an embryo pixel with known cartographic data is established. It's neighbors are considered growth pixels and on a second criteria predictions are collected and used to calculate cartographic data. If the data is validated, according to a third criteria, a new embryo is identified, and it's neighbors become growth pixels

Description

PROCESS FOR PRODUCING MAP DATA

  The present invention relates to methods of producing cartographic data characterizing the pixels of a digital image and it finds applications in very

many areas.

  Among these fields of application, we can notably cite the production of cartographic data characterizing the three-dimensional position of points of a scene from several images provided by sensors seeing the scene from different angles. The cartographic data are then constituted by the three-dimensional coordinates of the

point in the scene.

  Numerous processes for the production of

  cartographic data for previous applications

your.

  In the particular case of stereography, there are already many methods for finding the relief of a scene from at least two plane images of the scene, taken from different angles of view. These methods seek to match different elements in the images. One will find in particular a

  description of suitable algorithms in the article

  Nicolas Ayache "Artificial vision for mobile robots: stereo-

  vision and multisensory perception ", InterEdition 1991,

to which we can refer.

  This article shows in particular that one can limit the search for the pixel of an image which corresponds to a pixel of another image to a segment of a well-determined epipolar line. Either of two approaches is currently used to match or match the elements of the two images. A first method consists in searching for a pixel to pixel correspondence between the images

  (dense stereovision). Another method searches for the

  weight between more synthetic elements in the image, such as extracted segments (extracted stereovision). In

  the first case, we use the correlation between thumbnails

  your. In dense stereovision, a thumbnail centered on the pixel to be matched from a first image to a series of

  thumbnails centered on the possible positions of the corresponding

  of this pixel in the other image or each of the other images. At each position tested, corresponding to a

  disparity (difference between abscissa on the epipo- lines

  respective laires), we associate a resemblance index,

  such as an intercorrelation coefficient. Each pixel has more

  several candidate disparities (one per local maximum of the cross-correlation). The choice of the disparity retained for each pixel is generally made by considering the choices

  of disparity of the neighboring pixels of the same line. The coherence

  so it's one-dimensional. It is the choice of the dispari-

  tee among those possible which is simplified by making the comparison only with thumbnails all centered on the same epipolar. In return for its simplicity, this method has a drawback: it does not use the spatial coherence between adjacent points of the same image, in wide domains. Often the results obtained show

  streaks corresponding to the direction of the epipolar.

  Better results are obtained by comparing the selected disparities made on neighboring lines. But he

  this results in prohibitive calculation times.

  We have also already proposed (Ayache document already mentioned) a discrete stereovision approach, matching segments extracted from the images, using

  a two-dimensional propagation of results, with verification

  tion of hypotheses. This approach is schematized on the

figure 1.

  For an image, we make segment pairing hypotheses. They consist in choosing segments of roughly similar length and orientation which are compatible in the epipolar geometry. We thus obtain, for an image,

  a list H of matching hypotheses between two segments.

  For each of these hypotheses Hi, corresponding to a determined pairing, we try to propagate the pairing resulting from the hypothesis to the neighboring segment. We determine, for each hypothesis, a "force" which is the number of segments for which we arrive at a correct pairing. We establish

  thus a list Ai of pairings deemed to be correct.

  Then, for each pair of segments, we eliminate, in the list H of hypotheses, all the hypotheses similar to the pairings Ai obtained. Matching conflicts between

  hypotheses can be solved by retaining that of the hypo-

  theses for which the "force" is the highest.

  Once eliminated in H, the hypotheses similar to Ai, there remains a list A of pairings for which the

  continuity is checked in the list with rejection of devices

Inconsistent laughter.

  We thus arrive at a final list A.

  This solution gives satisfactory results, but

  only for non-dense stereovision.

  The present invention aims to provide a method of producing cartographic data which meets the requirements of practice better than those known in the past, in particular in that it provides reliable results with an acceptable calculation volume. In particular, it proposes to rule out

  the disadvantages of the overall treatment (used in stereovi-

  discrete sion) using the two-dimensional coherence that exists in continuous areas of the images (i.e. retaining the favorable characteristics)

  For this, use is made of the two-dimensional coherence

  image on large domains, in order to propagate information considered as safe. The neighbors of a safe point have a high probability of having a result (for example a disparity) close to this one. To implement this approach we will start with "seeds". A germ will be a point whose result is considered certain. This result will be considered as a prediction of the result of the neighbors. In order for the germ to grow, we check and correct the prediction; then we integrate the neighbor into the germ. In addition to prediction and verification, already provided for in

  Ayache's article, so we use two-way propagation

  thanks to the two-dimensional proximity between pixels. In general, the invention notably proposes a

  process for producing characteristic cartographic data

  health of pixels of at least one digital image, according to which (a) a seed pixel is selected, to which is known known or determined map data; (b) a datum is assigned to each pixel of a predetermined two-dimensional neighborhood centered on the seed pixel

  predicted cartographic value constituted by the cartographic value

  that of the germ pixel; (c) a criterion for the validity of the predicted datum is applied to each pixel in the neighborhood and this pixel is retained as an additional seed pixel, with the predicted cartographic value, possibly adjusted, if the criterion is fulfilled; and (d) the growth is continued in a two-dimensional manner, in addition carrying out a cohesion check between the predicted values in the case of a pixel belonging to the

  neighborhoods of several germ pixels.

  The forecasting and verification stages (stages b and c) can use criteria comparable to those described in the article by N. Ayache "Stereoscopic vision and multi-sensory perception" already cited, but these criteria

  are applied, in the case of the invention, to a mapping

  phie of the kind that can be described as dense, in the sense that it assigns a cartographic value to each pixel rather than treating segments, as in the case of

Ayache's article.

  In the particular case of stereovision, the cartographic datum is the disparity, which can then be deduced by known algorithms, for each pixel of coordinates

(x, y), altitude (z).

  In this case, step (c) may involve, during the

  propagation of the germ and while the pixel to be treated appears

  is due to the vicinity of several pre-existing seed pixels, the calculation of an intercorrelation coefficient as a function of the disparity, but this only in a narrow domain around the predicted disparity. When the disparities predicted from several seed pixels differ from each other by an amount greater than a predetermined discontinuity threshold, several searches will be necessary and frequently the predicted disparities will be the same for the

  different pixels, to the nearest discontinuity threshold.

  The interest of the invention in this case appears immediate-

  ment if a comparison is made with the application of a classical dense stereovision algorithm. Such an algorithm globally searches for the pairings between all the pixels of a line of a first image and of the corresponding pixels of a second image. This implies a correlation calculation which is carried out for each of the successive pixels of a line of a first image, over a search interval which is necessarily much longer than in the case of the invention. At the end of this first step, each of the N intercorrelation coefficients corresponding to each of the N points of a line, provides a set of potential pairings of the corresponding pixel. A subsequent operation makes a selection by line of the pairings, in

  using the one-dimensional spatial coherence of the image.

  As an indication, we can note that the classical algorithm requires as many correlations as disparities

  whole possible, while the implementation of the invention

  tion requires in most cases only three correlations per pixel, corresponding to the presence check

  a local maximum for most points.

  In other words, the invention proposes, in the case of a dense stereovision method where the cartographic datum is the disparity of each pixel of a pair of stereographic images, according to which, once a germ formed has formed of several pixels, (b) we assign to each pixel to be processed belonging to the neighborhood of several pixels of the seed, several predicted disparities constituted by the disparities of each neighboring seed pixel, (c) we apply to the pixel to be processed, the same criterion validity of each disparity predicted from a neighboring seed pixel, in the form of an intercorrelation calculation around the disparity given by the prediction and in a predetermined discontinuity interval. This interval corresponds to a continuity between the prediction and the desired result. We retain that of the predicted disparities which gives the highest correlation peak, insofar as the peak intercorrelation coefficient exceeds a predetermined threshold; and (d) the processed pixel is integrated into the seed if the intercorrelation proposal is greater than the threshold, then we continue

  growth in two dimensions.

  During this growth, the neighboring pixels to which a disparity is not yet assigned are treated, as well as the pixels for which the validity criteria have not been fulfilled, for example because the predictions from several neighboring pixels differ from values

  above the discontinuity threshold.

  Growth can thus continue until it fills any region which is relatively homogeneous and for which pairing is possible. However, it will lead to

  remove the pixels for which matching is impossible

  ble, for example because a point represented by a pixel in one of the images is masked in the other image or because there is an abrupt discontinuity of disparities, for example in images of scenes comprising sudden breaks in relief . In the second case, the domains which have not been treated by propagation of a germ located in a first domain can be treated in turn, by

starting from a new germ.

  The above features as well as others

  will appear better on reading the description which follows

  particular embodiments, given by way of example

ples nonlimiting.

  The description refers to the accompanying drawings,

  in which: - Figure 1, already mentioned, is a flowchart of a known segment matching algorithm (for example that of the article by N. Ayache);

  - Figure 2 is a block diagram of an algo-

  rithm indicating the successive treatments which intervene in the process according to the invention; - Figures 3A, 3B and 3C indicate neighborhoods that can be used to implement the invention; - Figure 4 shows a possible criterion for selecting a seed pixel; - Figure 5 shows the growth of the treated area in a homogeneous area, in the presence of an inconsistent area

  with the area where growth takes place.

  As already indicated above, the basic principle of the invention consists in propagating, until it covers an entire homogeneous domain, information considered to be safe, starting from the premise that the neighbors of a pixel whose we have determined the safe cartographic data have a high probability of having a cartographic data equal to the

  pixel data safe or close to this data.

  For this, we can consider that the approach according to the invention implies the implementation of four successive criteria: - criterion 1: criterion for defining a safe pixel, which will constitute an initial seed;

  - criterion 2: criterion for determining the carto- values

  predicted graphics for a pixel not yet processed and close to a seed pixel or pixels;

  - criterion 3: criterion for validating a carto- value

  graph equal to a predicted value, possibly with a correction; - criterion 4: choice of a neighborhood for propagation

germ.

  The approach followed is shown diagrammatically in FIG. 2. The first operation consists in finding a safe pixel, among those which are not yet processed. We define, around

  of this pixel, a neighborhood made up of growth pixels.

  Various neighborhoods can be used. In the case of a square array of pixels, it can comprise eight or four pixels, as indicated in FIGS. 3A and 3B. In the case of a staggered distribution, the neighborhood will generally consist of six pixels occupying the vertices of a hexagon

(Figure 3G).

  From there, we execute on each pixel of growth

  (neighbor of at least one seed pixel), a processing loop.

  The first step in the loop is to collect and use the predictions, then calculate a cartographic value from this use. The cartographic value assigned and possibly corrected is then subject to a validation criterion. If the criterion is not fulfilled, the value is considered as invalid and there is a return to the input of the loop. If the criterion is

  filled, the validated value is memorized for the processed pixel.

  The pixels of the image belonging to its vicinity and not yet assigned a value are considered to be pixels

  growth, to which the processing loop is applied.

  Dense stereovision: We will now describe a possible mode of implementation of the method for assigning a disparity, constituting the cartographic datum, to the points of a scene represented by

  images of the scene seen from different angles.

  The starting operation consists in selecting a point to which the germ pixel will correspond in one of the images. In some cases, the point of the scene has known characteristics, and can be identified visually in the two images. In this case the disparity can be selected arbitrarily. In most cases, however, it will be necessary to assign a disparity obtained in a safe manner by calculation.

  For this, we establish a variation curve of the coefficient

  cient of intercorrelation as a function of disparity over a wide search interval along an epipolar. Methods are already known for determining the necessary search interval and for calculating a correlation coefficient. Such a process is for example described in the article by Ayache mentioned above, under section 3.5. However, to obtain a high certainty on the disparity attributed to the first seed pixel, it is better to adopt a safer criterion than the simple search for a

  peak of the cross-correlation function.

  In particular, a pixel can be retained as a seed, with a disparity D, only if: the maximum of the intercorrelation coefficient Cl for D is greater than a predetermined threshold S (FIG. 4), and

  - the relative amplitude compared to the second peak (C1-

  C2) / C1 is also greater than a threshold.

  The collection of predictions, for a pixel not yet processed, is carried out from all the neighbors of this pixel which have a disparity already assigned, therefore belonging

to the germ.

  For example, we will have, for the pixel P of FIG. 3A, two predicted disparities if the disparities are already

  assigned, in its vicinity, to pixels 4 and 5.

  The computation of the intercorrelation coefficients for the pixel P will then only be done around each predicted disparity, in a search interval which can be

  much more limited than in the case of traditional processes-

  nels. The search interval can for example be limited to: [predicted disparity - discontinuity threshold - 1; disparity

  predicted + discontinuity threshold + 1].

  The discontinuity threshold is chosen a priori. It plays two functions. On the one hand, a pixel will only be processed if the disparities allocated from the pixel disparities

  neighbors do not differ by more than the discontinuity threshold.

  On the other hand, it defines the search interval, the offsets of one pixel making it possible to detect a maximum even

  at the edge of the search interval.

  The disparity retained for the pixel processed is that which gives the highest correlation peak, among the correlation peaks obtained for the search intervals.

  associated with various predictions.

  The result is validated (criterion 3) only if the intercorrelation coefficient for the selected disparity is greater than a threshold. If so, the processed pixel is integrated into the seed and will therefore be used to continue the propagation. Finally, the processing will be resumed on the pixels of the

new neighborhood.

  The numerical values of the correlation threshold for the search for a seed pixel, of the threshold on the relative amplitude of the second peak, of the discontinuity threshold and of the correlation threshold for the propagation will be chosen according to

of the nature of the scene.

  For example, a scene comprising a single large building was treated by a conventional process of dense stereovision, with a research interval on the disparity of - 10 to + 10 pixels and by the method according to the invention. In this example, the classical process requires a systematic calculation of twenty-one correlations per pixel; the method according to the invention makes it possible to calculate only three intercorrelation coefficients, with a view to verifying a local maximum, for the vast majority of

  points. Because the method uses two-dimensional coherence

the streaks are eliminated.

  [11 The process which has just been described makes the assumption of a continuity of the disparity in important fields and makes it possible to predict the results at the edge of the germ in the course of growth. To refine the position of the correlation peak, it is possible to propagate not only the disparity information, but also the value of its first derivatives in x and in y, or even the value of the second derivatives. The registration of the predicted value by search for the maximum closest to the correlation curve as a function of the disparity is then completed by the registration of the derivatives in x and in y. This approach is particularly interesting in

the case of high relief areas.

  The derivatives of the disparity can be calculated by a process similar to that described in the doctoral thesis of the polytechnic school of F. Devernay "Stereoscopic vision and differential properties of surfaces",

February 1997.

  A first approach consists in performing a bilinear regression on all the already calculated disparities located in a neighborhood of constant size of a point on the disparity map. We then assign to the derivatives of the

  disparity of values equal to the regression coefficients

  if we. A second approach consists in calculating the first derivatives of the disparity directly from a pair of stereoscopic images. The derivatives are then assimilated to the parameters of an element of one of the deformed images to obtain the maximum of the correlation coefficient between the two regions of the images. This latter approach is described

  in the thesis of F. Devernay on pages 60 to 62.

Claims (7)

  1. A method of producing cartographic data characterizing pixels of at least one digital image, according to which (a) a seed pixel is selected, to which is known known or determined cartographic data reliably; (b) a data item is assigned to each pixel of a predetermined two-dimensional neighborhood centered on the seed pixel   predicted cartographic value constituted by the cartographic value   that of the germ pixel; (c) a criterion for the validity of the predicted datum is applied to each pixel in the neighborhood and this pixel is retained as an additional seed pixel, with the predicted cartographic value, possibly adjusted, if the criterion is fulfilled; and (d) the growth is continued in a two-dimensional manner, in addition carrying out a cohesion check between the predicted values in the case of a pixel belonging to the   neighborhoods of several germ pixels.   2. The stereovision method according to claim 1, characterized in that step (c) comprises, once the seed consists of several pixels, the calculation of an intercorrelation coefficient as a function of the disparity, only in a narrow domain around of the disparity predicted to   from each neighboring pixel of the seed.   3. Method according to claim 2, characterized in that several searches are carried out from the predicted disparities from several seed pixels in the neighborhood differing from one another by an amount less than a threshold of predetermined discontinuity.   4. Method according to claim 3, characterized in that the search during step (c) is carried out along an epipolar in an interval equal to: [predicted disparity - discontinuity threshold - 1; disparity   predicted + discontinuity threshold + 1].   5. Method according to claim 2, 3 or 4, characterized in that a pixel is retained as a seed pixel with a disparity D when: - the maximum of cross-correlation coefficient Cl for D is greater than a predetermined threshold S (figure 4), and   - the relative amplitude compared to the second peak (C1-   C2) / C1 is also greater than a predetermined threshold.   6. Method according to any one of the claims   2 to 5, characterized in that during step (d), in addition to the disparity information, it also propagates   the value of its derivatives in x and in y.   7. Method for producing cartographic data in dense stereovision, the data being constituted by the disparity, of each pixel between the two images of a pair of stereographic images, according to which, (a) once a seed formed of several pixels has been formed, (b) we assign to each pixel to be processed belonging to the neighborhood of several pixels of a seed of known disparities, several predicted disparities constituted by the disparities of each neighboring seed pixel, (c) we apply to the pixel to be processed, a same validity criterion for each disparity predicted from a neighboring seed pixel, in the form of an intercorrelation calculation around the disparity given by the prediction and in a predetermined discontinuity interval and we retain that of the predicted disparities which gives the peak of correlation the   higher, insofar as the cross-correlation coefficient   tion of the peak exceeds a predetermined threshold; and (d) the processed pixel is integrated into the seed if the intercorrelation proposal is greater than the threshold, then we continue   growth in two dimensions.