Patent ID: 12227191

DETAILED DESCRIPTION

FIG.1schematically shows the various input and output data of the method according to the invention.

The method according to the invention is presented according to a first embodiment, in which the movement of a material body is characterized by a first movement component corresponding to direction and by a second movement component corresponding to speed. A direction mask and a speed mask will therefore be used.

Feature Grid Generation

The method works iteratively: in each iteration t, a new series of measurements is performed, thereby making it possible to update the estimate of the movement. In each iteration t, a feature grid is generated, this hereinafter being called feature grid in iteration t FGt.

It is then observed whether some cells of the feature grid that are “FALSE” in a given iteration become “TRUE” in the following iteration (or vice versa). The appearance or disappearance information is found in the inconsistency grid in iteration t IGt.

In each iteration t, there is therefore the inconsistency grid in iteration t IGtand the inconsistency grid in iteration t IGt-1.

As may be seen inFIG.1, a filtered direction movement grid in iteration t FMGtdand a filtered speed movement grid in iteration t FMGtsare then generated, these being determined recurrently on the basis of the inconsistency grid in iteration t IGt, of the inconsistency grid in iteration t IGt-1, and respectively of the filtered direction movement grid in iteration t-1 FMGt-1dand of the filtered speed movement grid in iteration t-1 FMGt-1s.

The idea on which the invention is based consists in describing the movement of each cell of the grid through a finite and discrete set of directions, and each direction is then discretized into a finite number of speeds.

This discrete representation of the displacement directions and speeds is easily configurable and has a linear impact on the temporal complexity and on the memory resources required to execute the algorithm.

The user, by acting on the number of directions and/or on the number of speeds, is thus able to act on the accuracy of the movement model and on the implementation and execution performance. In particular, the algorithmic complexity depends on the number of cells of the grid, on the number of cells of each mask, on the number of directions and on the number of speeds per direction.

The estimate of the dynamics of material bodies moving around the sensor is thus performed deterministically, the method according to the invention not requiring any random number generation.

Knowing the iteration frequency of the measurements f, the length of each cell lc, and the length of the mask lm(in terms of number of cells), it is possible to easily determine the minimum speed detected per iteration (vmin=lc×f), and also the minimum speed detected per iteration

(vmax=lc×lm×f2),
and notably act on the size of the mask in order to adjust the minimum detection speed and the maximum detection speed.

The left-hand part ofFIG.2illustrates two material bodies detected in iteration t, specifically the bodies “Feat A” and “Feat B”. The feature grid FGt, illustrated by the right-hand part ofFIG.2, may be generated based on a series of distance measurements from one or more sensors. Based on the distance measurement, an occupancy probability is then determined, this depending on the inverse model of the sensor, as described notably in patent application FR3041451.

This thus gives an occupancy probability for each cell of the grid of cells of between 0 and 1 (occupancy grid). This probability is then transformed into a Boolean value (of the type TRUE/FALSE) by applying a threshold, which may typically be equal to 0.5.

To simplify the disclosure, the invention will be described with a single sensor for performing the distance measurements. Performing the same computations with measurements from multiple sensors does not pose any problem to a person skilled in the art.

The feature grid FGt, illustrated for example byFIG.2, therefore has as many cells as the occupancy grid, and each cell has a Boolean value specific to the occupied or unoccupied nature.

Inconsistency Grid Generation

FIG.3illustrates, for three successive iterations, the feature grid in iteration t-2 (FGt-2), the feature grid in iteration t-1 (FGt-1) and the feature grid in iteration t (FGt). In each of these grids, it is possible to see cells whose occupancy probability is greater than the chosen threshold.

Two inconsistency grids IGt-1and IGtare constructed.

Each cell of the inconsistency grid IGt-1takes the Boolean value “TRUE” if the corresponding cell of the feature grid FGt-1has seen its Boolean value change between the feature grid FGt-2and the feature grid FGt-1.

Likewise, each cell of the inconsistency grid IGttakes the Boolean value “TRUE” if the corresponding cell of the feature grid FGthas seen its Boolean value change between the feature grid FGt-1and the feature grid FGt.

Such a cell takes a first Boolean value, for example “TRUE”, the other cells taking a second Boolean value, for example “FALSE”. This thus gives, for three successive iterations, two inconsistency grids IGt-1and IGt. In the example ofFIG.3, the inconsistency grid IGt-1comprises three inconsistent cells, and the inconsistency grid IGtcomprises two of them.

The inconsistency grids are thus computed by the computer or by the dedicated electronic circuit implementing the method according to the invention, on the basis of the feature grids, which themselves originate from measurements from at least one sensor.

As an alternative, the inconsistency grids may be provided directly by event cameras, which make it possible to generate event image data in response to detection of a change in a scene that is located within its field of view. A person skilled in the art may refer for example to patent application FR3065133 on this subject.

Generation of the Displacement Measurement

Whether the inconsistency grids have been provided directly by the sensor or computed on the basis of a distance measurement, there is computed, in iteration t, for each cell of the grid, a posterior probability P(dt,iA|z1:t) of a material body located in a cell A of the grid of cells moving in the direction i, from among a discrete set of directions around cell A, knowing all of the measurements z1:tbetween iteration 1 and iteration t, and a posterior probability P(st,i,jA|z1:t) of a material body located in a cell A of the grid of cells moving in the direction i at the speed j, knowing all of the measurements z2:tbetween iteration 1 and iteration t.

d corresponds to the direction movement component, and s corresponds to the speed movement component. A corresponds to the identifier of one of the cells of the grid of cells. zicorresponds to the ithobservation/measurement. z1:tthus corresponds to all of the measurements between iteration 1 and iteration t.

The posterior probability P(dt,iA|z1:t) and the posterior probability P(st,i,jA|z1:t) may be computed by the algorithm of the binary Bayesian filter, which makes it possible to recursively estimate the probability distribution of a random binary variable.

The binary Bayesian filter comprises two main steps, specifically predicting and updating measurements. The prediction makes it possible to predict the current occupancy state on the basis of previous measurement sequences, and the updating makes it possible to correct the predicted estimate with new measurements.

These computations may be performed using floating point arithmetic operations, thereby requiring significant resources in terms of computing power that are not very compatible with constraints specific to on-board systems.

The posterior probability P(dt,iA|z1:t) is approximated by a value belonging to a finite-cardinality set of numerical values between 0 and 1. Since the set is finite, its elements may be identified uniquely by an index that is an integer. Let n(dt,iA|z1:t) be the index of the element that corresponds to the numerical value of P(dt,iA|z1:t). Likewise, the index n(st,i,jA|z1:t) represents the index of the element that corresponds to the numerical value of the posterior probability P(st,i,jA|z1:t). Since the index n(dt,iA|z1:t) and the index n(st,i,jA|z1:t) are integers, these indices are computed using far simpler integer arithmetic operations, while still retaining an acceptable and configurable accuracy level (bijection between an integer and a real number between 0 and 1) on the basis of the available computing resources.

FIG.4, which is specific to the direction estimate, adopts some of the features fromFIG.1. The binary Bayesian filter processing integer data, which will hereinafter be called integer binary Bayesian filter, receives, in each iteration t, a set of propagated indices, resulting from a process of propagating the indices in the previous iteration t-1 n(dt-1,iA|z1:t-1), and the index of the inverse sensor model n(dt,iA|zt), which corresponds to the probability P(dt,iA|zt) of a cell A following the direction i in iteration t, knowing only the sensor measurement ztproduced in the same iteration.

For each inconsistency cell A of the inconsistency grid IGthaving the first Boolean value (for example the value “TRUE”), the predecessors of these cells in the inconsistency grid IGt-1will therefore be looked at, and the direction mask will be applied.

Thus, for the direction mask, consideration is given to a “direction” movement component, which corresponds to a direction for moving from one cell to another.

The same principle is used to estimate speed, as illustrated inFIG.5. This gives, in each iteration t, the index n(st,i,jA|z1:t), for each cell A of the grid for each direction i and for each speed j.

Thus, for the speed mask, consideration is given to a “speed” movement component, which corresponds to the displacement speed from one cell to another in a given direction.

FIG.6Aillustrates one example of a direction mask, andFIG.6Billustrates one example of a speed mask. The direction mask contains 5×5 cells, and eight directions, and the speed mask contains 5×5 cells and two speeds, but other values may of course be adopted.

Cell A is located in the center of the mask. Each direction starting from the cell is an independent binary random variable. To estimate the direction (cf.FIG.4), use is thus made of one integer binary Bayesian filter per direction.

Likewise, as illustrated inFIG.6B, each direction starting from a cell has Ns speeds, and each speed is an independent binary random variable. To estimate the speed (cf.FIG.5), use is thus made of one integer binary Bayesian filter per speed.

Considering each direction or each speed (from among a discrete set) as independent variables of a binary Bayesian filter makes it possible to estimate the displacement of multiple material bodies occupying one and the same cell at a time t, with change of direction and/or speed probabilities whose sum is not necessarily equal to 1.

For example, two pedestrians may be in one and the same cell at a time t. The method may take into account a probability equal to 0.9 that one of the pedestrians will turn left, and a probability equal to 0.9 that the other pedestrian will turn right.

FIG.7illustrates the filtered direction movement grid in iteration t, FMGtd, which is a data structure used for the direction estimate. On the left is a grid in which two cells A and B are given values. The entries in the filtered direction movement grid corresponding to cells are also given values on the right of the figure.

The data structure corresponds to a dual-entry table. Each row corresponds to a cell of the grid. Each column corresponds to one of the directions of the discrete set of directions.

The following notation is adopted: for cell A, each column i takes the index n(dt,iA|z1:t). For cell B, each column i takes the index n(dt,iB|z1:t).

It is assumed, in the method according to the invention, that an inconsistent cell, that is to say a cell in the inconsistency grid, is potentially dynamic. It will be assumed that the content of cell A moves between iterations t-1 and t. The content of A is located in A in iteration t, but it may be located in other cells close to A in t-1.

The set of possible locations of the content of A at t-1 is called “predecessors” of A. The zone where the predecessors of A are located is delimited by the direction mask and the speed mask.

The predecessors may be defined with regard to directions and speeds. The following functions denote the predecessors of a cell with regard to directions and speeds:

Antecedentsd(A,i) denotes the set of possible predecessors of cell A with respect to the direction i.

Antecedentss(A,i,j) denotes the set of possible predecessors of cell A with regard to the speed j in the direction i.

FIG.8illustrates the functions Antecedentsdand Antecedentss. In this figure, the inconsistent cells in iteration t-1 are cells U and V. The inconsistent cells in iteration t are cells A and B. The predecessors of cell A with respect to direction 8 are: Antecedentsd(A, 8)={R, T, W, U}.

Likewise, the predecessors of cell A with regard to the speed 1 in direction 8 are: Antecedentsd(A, 8,1)={U}.

The predecessors of cell A with regard to the speed 2 in direction 8 are: Antecedentsd(A, 8,2)={R, T, W}.

The measure of the displacement in the grid may then be expressed by the following functions MeasureDirection and MeasureSpeed, defined below.

The function MeasureDirection checks whether a cell A has potentially moved in the direction i between iterations t-1 and t. This function returns a Boolean value:

MeasureDirection⁡(A,i,IGt-1,IGt)={True⁢⁢if⁢⁢IGt⁡(A)=True⩓∃A′∈Predeces⁢s⁢o⁢r⁢sd⁡(A,i)⁢⁢such⁢⁢⁢that⁢⁢IGt-1⁡(A′)=TrueFalse⁢⁢if⁢⁢not

The function MeasureSpeed checks whether a cell A has potentially moved with respect to the direction i and the speed j between iterations t-1 and t. This function returns a Boolean value:

MeasureSpeed⁡(A,i,j,IGt-1,IGt)={True⁢⁢if⁢⁢IGt⁡(A)=True⩓∃A′∈Predeces⁢s⁢o⁢r⁢ss⁡(A,i,j)⁢⁢such⁢⁢⁢that⁢⁢IGt-1⁡(A′)=TrueFalse⁢⁢if⁢⁢not

Applying the two movement measurement functions to the examples ofFIG.8gives the following results. The function MeasureDirection will return “FALSE” except for MeasureDirection(A, 8, IGt-1,IGt), MeasureDirection(A, 4, IGt-1,IGt) and MeasureDirection(B, 5, IGt-1, IGt).

Furthermore, the function MeasureSpeed will return “TRUE” for MeasureSpeed(A, 8,1, IGt-1, IGt), MeasureSpeed(A, 4, 2, IGt-1, IGt) and MeasureSpeed(B,5,2,IGt-1,IGt), and “FALSE” for the other arguments of the function.

Next, indices n(dt,iA|zt) of the inverse sensor model are determined, these constituting the contribution to updating the measurements ztproduced in iteration t in the binary Bayesian filter.

These indices are determined with respect to the results of the function MeasureDirection and of the function MeasureSpeed described above:

n⁡(dt,iA|zt)={ηd>0⁢⁢if⁢⁢MeasureDir⁢e⁢c⁢t⁢i⁢o⁢n⁢(A,i,IGt-1,IGt)=TRUE0⁢⁢i⁢f⁢⁢n⁢o⁢t⁢⁢n⁡(st,i,jA|zt)={ηs>0⁢⁢if⁢⁢MeasureS⁢p⁢e⁢e⁢d⁢(A,i,j,IGt-1,IGt)=TRUE0⁢⁢if⁢⁢not

The parameters ηdand ηsare positive integers that are constant and chosen empirically.

The propagation of the indices of the posterior probabilities of the predecessors are then computed. This step is illustrated inFIG.9.

For this purpose, for each element of the filtered direction movement grid in iteration t FMGtd, a propagated index n(dt-1,i|z1:t-1) is computed on the basis of the indices of the filtered direction movement gridFMGt-1dcomputed in the previous iteration t-1:
n(dt-1,iA|z1:t-1)=max(FMGt-1d(A′,i))

InFIG.9, consideration is given by way of example to two cells A and B, propagating, between t-1 and t, in the direction 4. Thus, for cell A, the index n(dt-1,4A|z1:t-1) in the filtered direction movement grid FMGt-1dhas the value m4, and is zero for the other directions.

For cell B, the index n(dt-1,4B|z1:t-1) in the filtered direction movement grid FMGt-1dhas the value n4, and is zero for the other directions. The other cells are not shown in the table, the corresponding probability index being zero for all of the directions.

The propagation process propagates the non-zero indices in the filtered direction movement grid FMGt-1dto other cells along the corresponding directions.

In the example ofFIG.9, only cells A and B have non-zero indices in the filtered direction movement grid FMGt-1d. These indices concern the direction 4 for the two cells. Their indices in the other directions are zero.

The result of the propagation process is illustrated at the bottom left ofFIG.9. Only cells C, D, E, F, G and H have non-zero propagated indices. The propagated indices of the other cells are zero for all of the directions. For cell C, its sole predecessor having non-zero indices in FMGt-1dis cell A in direction 4. The propagated index n(dt-1,4C|z1:t-1) of cell C in direction 4 thus has the value m4. The predecessors of cell D having non-zero indices in FMGt-1dare cells A and B in direction 4. The propagated index n(dt-1,4D|z1:t-1) thus has the value max(n4, m4).

Displacement Filtering

Once the propagated indices have been computed, the integer binary Bayesian filter is applied. The filtering is applied for each new incoming measurement, specifically in each iteration.

It will be recalled that the input data are the propagated index from previous iteration t-1 n(dt-1,iA|z1:t-1) and also the probability index n(dt,iA|zt), which constitutes the contribution to updating the measurements in the integer binary Bayesian filter.

This step takes advantage of the integer fusion function for the filtering function, using only an integer arithmetic operation. The posterior probability P(dt,iA|z1:t) and the posterior probability P(dt,i,jA|z1:t) have been represented in discretized form, respectively, by an index n(dt,iA|z1:t) and by an index n(dt,i,jA|z1:t), in a finite-cardinality set of probability classes.

The finite-cardinality set of probability classes is formed by combining one or more subsets such that, in the step of updating the measurement, fusing two probability classes belonging to one and the same subset provides a result also belonging to said subset.

Advantageously, the finite-cardinality set of probability classes, denoted by Gp, is formed by combining two subsets Gp−and Gp+defined by:
Gp−={qn),n≤0}
Gp+={qn),n≤0}

The index n takes relative integer values, and the numerical values of the probability classes qnare defined recurrently as follows:

(qn)n∈ℤ={12if⁢⁢n=012+ϵif⁢⁢n=112-ϵif⁢⁢n=-1F⁡(qn-1,q1)if⁢⁢n>1F⁡(qn-1,q-1)if⁢⁢n<-1

∈ is therefore a predetermined parameter of the filter IBBF. Its value is a constant between 0 and 0.5.

The fusion F(qn, qm) between two probability classes qm, qnis computed by applying the following equation: F (qn, qm)=qm+n

The last parameter of the filter IBFF is F, which is the subset of Z for defining (qn)n∈Γ.

For example, if the probability indices are computed on eight bits, Γ={−128, . . . , 127}. Storing the probability indices on eight bits makes it possible to work with a particularly compact memory.

The result of fusing two elements of the sequence qnmay be computed by a simple sum of the indices of the input elements.

The prediction step consists in consulting, in a lookup table, the index n(dt,iA|z1:t-1) corresponding to the probability P(dt,iA|z1:t-1) of the cell A taking the direction i in iteration t, knowing the set of all of the measurements z1:t-1before iteration t.

An initialization function of the filter is first invoked in order to precompute the lookup table. The filter is initialized once and for all, before the movement estimate.

The initialization function of the filter has four input values: the parameter ∈ defined above, Γ (the subset of Z for defining (qn)n∈Γ), and also the parameters α and β, which correspond respectively to the probability of keeping the same direction between two successive iterations and to the probability of changing direction between two successive iterations.

The lookup table predLUT is therefore a dual-entry table, one column for n and one column for the corresponding value in the table. The number of rows is equal to the size of the subset F. The lookup table is initially empty.

For each value n (n ∈Γ), probabilities qnare computed recurrently using the formula defined above, using the parameter E and the fusion F(qn, qm).

Next, predLUT[n] is given the value of approx_policy(qn·α+(1−qn)·β).

The function approx_policy is such that each entry in the lookup table is approximated in order to correspond to an element of (qn)n∈Z)
predLUT(n)=mand approx_policy(qn·α+(1−qn)·β)=qm

Once the filter has been initialized, the function predLUT is applied to the propagated index n(dt-1,iA|z1:t-1) thereby making it possible to obtain the prediction term of the filter IBBF n(dt,iA|z1:t-1) only by consulting the table, without computations.

The step of updating the measurement filter consists in performing the following operation:
n(dt,iA|z1:t)←n(dt,iA|z1:t-1)+n(dt,iA|zt)

This therefore gives, at the end of each iteration, for each cell of the grid and for each direction i, the index n(dt,iA|z1:t), which corresponds to the probability of the material body moving in the direction i.

An integer binary Bayesian filter is also applied in each iteration in order to estimate speed, as illustrated inFIG.5.

The steps of the filtering are the same as for the direction estimate, with the difference that the indices are filtered, in each iteration, for each direction of the direction mask, and for each speed of the speed mask.

Thus, rather than manipulating a filtered movement grid for the direction FMGtd, which is a 2D table of dimensions Nc×Nd(Ncnumber of cells of the grid, Ndnumber of directions of the mask), what is manipulated, for the speeds, is a filtered movement grid for the speed FMGts, which is a 3D table of dimensions Nc×Nd×Nsnumber of speeds of the mask).

Each element FMGtss(A,i,j) of the filtered movement grid for the speed FMGtsstores an index n(st,iA|z1:t) of the posterior probability P(st,iA|z1:t) of cell A having moved from the direction i at the speed j in iteration t.

Thus, to compute the filtering of the displacement at each speed, a person skilled in the art may easily transpose the steps of predicting and updating the filter IBBF with regard to the speed data.

The method has been described taking into consideration two movement components characterizing the movement of a mobile body, specifically a direction component and a speed component.

According to a second embodiment, the method may be implemented considering only one movement component, as illustrated byFIG.11.

In this case, the movement component corresponds to a direction between two cells of the grid of cells, with multiple distances per direction (which is in fact tantamount to considering multiple displacement speeds per direction, given the change in distance in each iteration).

The space around cell A is discretized into a plurality of directions (zones 1, 4, 7, 13, 22, 23 and 24) corresponding to a first direction movement component. Each direction moreover has multiple “depth” levels in the mask, corresponding to various speeds, which are themselves also discretized. For example, zone 4 has three depth levels, corresponding to three different speeds: zone 4 itself, zone 5 and zone 6.

The computations for estimating the movement of material bodies with a single mask comprising multiple zones per direction (in order to discretize multiple speeds per direction) are performed in a manner similar to the first embodiment.

In this case too, each displacement is a random binary variable, estimated by an instance of the binary Bayesian filter.

Using just one mask instead of two removes a data structure, thereby making it possible to save computing time, without otherwise losing accuracy in the movement estimate. By way of illustration, in the example ofFIG.11, there would be twenty-four filters to be updated in each iteration. With the first embodiment, there would be 8 filters to be updated for the directions, and 24 filters to be updated for the speeds (3 possible speeds per direction), therefore thirty-two filters to be updated in each iteration.

The method according to the invention does not necessarily involve taking into account all of the components around each cell. As illustrated inFIG.12, there may be a focus only on certain components (for example two components located in the right-hand column). This also simplifies the updating of the filters. This implementation may be contemplated in situations in which the displacements of mobile bodies are constrained in certain directions and/or at certain speeds, for example on a conveyor belt in an industrial site.

According to one advantageous embodiment, the method furthermore comprises, following step a) of obtaining an inconsistency grid, and step b) of recurrently generating a filtered movement grid in iteration t, a step c) of determining, for each cell of the grid of cells, the movement component corresponding to a posterior probability greater than a predefined threshold (for example 0.8).

The movement component corresponding to the posterior probability greater than a threshold is determined using the filtered movement grid, illustrated byFIG.7.

For each cell, the immediately adjacent cells are considered. If an immediately adjacent cell has the same movement component corresponding to the posterior probability greater than a threshold, the two adjacent cells are clustered, and so on, for as long as adjacent cells having the same movement component corresponding to the posterior probability greater than a threshold are identified.

Clustering of cells is thus performed (step d)).

If the movement components of a cell all have a zero posterior probability value, the cell is not taken into consideration, at the time t under consideration, for the clustering step.

Step e) then comprises determining a material body on the basis of the result of clustering step d). In one embodiment applied to the motor vehicle sector, it may for example be determined whether the material body is a pedestrian or a two-wheeled or four-wheeled motorized vehicle.

An object tracking module is supplied with the data from the tracking step of determining a material body (step f).

The clustering benefits from the structure of the filtered movement grid, which is a regular structure, thereby facilitating real-time computations in processors smaller than those used in the prior art.

By virtue of the method according to the invention, the movement estimate may be performed in microprocessors, for example with ARM (registered trademark) architectures, whereas, in the prior art, the estimate consumes a very large amount of computing resources and usually requires graphics processors (or GPU for graphics processing units).

The method according to the invention may be implemented by at least one distance sensor, for example a lidar, a radar or else a sonar, or by a camera able to extract distance information from a scene acquired by the sensor.

The feature grids are established on the basis of the distance measurements performed by the sensor.

If the sensor is capable of generating event image data in response to detecting a change in a scene that is located within its field of view, these data are transmitted to the data processor in order to characterize the movement dynamics of the material body.

The sensor may be housed on board the vehicle; as an alternative, the scene may be acquired by the sensor, and then the information for estimating the movement of the material body located in the scene may be transmitted to the mobile body. The sensor may thus be positioned at a fixed location, for example in a signpost, and communicate with vehicles nearby in order to actuate avoidance commands.

The vehicle may be autonomous or else not autonomous, and in this case the method according to the invention makes it possible to assist the driver with obstacle detection.

The mobile body may also be any device able to move autonomously, for example a domestic appliance such as an autonomous vacuum cleaner, or else a gardening appliance such as an autonomous lawnmower.

The mobile body also comprises actuators able to correct the trajectory of the autonomous mobile body on the basis of the estimate of the movement of the material body that has been performed using the method according to the invention with a view to avoiding the material body.

The estimation device may also be installed at a fixed position, in an intrusion detection sensor. The use of an event camera is particularly suitable for intrusion detection (the scene to be observed is generally fixed, except for in the event of intrusion).

The invention has essentially been described by discretizing the set of probabilities into a finite-cardinality set, in order not to have to perform computations using floating-point arithmetic operations. This provision makes it possible in particular to implement the method according to the invention in an on-board system having high integration constraints.

The method according to the invention could also use floating point arithmetic operations, in particular if the computational capabilities of the device implementing the method make it possible to perform the movement estimate in real time.