Dynamic scene analysis method, and associated analysis module and computer programme

{
  "publication_number": "US10290116B2",
  "country": "US",
  "kind": "B2",
  "title": "Dynamic scene analysis method, and associated analysis module and computer programme",
  "abstract": "A method for analyzing a dynamic scene partitioned into cells which involves determining a probability of occupancy of a cell and a probability or probabilities of movement of the cell by solving the equation P(OV|ZC)=ΣA0 −1V-1 P(CA00 −1 VV −1 Z)/ΣA00 −1 VV −1 P(CA00 − VV −1 Z) comprising the determination of the speeds and positions of dummy particles in the grid depending on those determined at the (k−1) th iteration and the probability P(V|V−1); the determination of the particles located in each cell depending on the determined positions, and the solving of the equation, for a cell, is split into the solving of a static part corresponding to P(0=empty, V=0|ZC) and P(0=occupied, V=0|ZC) and the solving of a dynamic part corresponding to P(0=occ, V=v k i,|ZC), i=32 1 to n k, in which n k is the number of particles determined in cell C for the k th iteration.",
  "claims": [
    "1. A method for analyzing a dynamic scene observed with the aid of one or more sensors, the method comprising: defining a grid that is partitioned into cells and corresponding to the observed scene; collecting at least one new observation of the one or more sensors at a k th iteration; determining, as a function of the new collected observation, a first probability of occupancy of each cell of the grid modeling the operation of the one or more sensors; determining, for each cell, at the k th iteration, a second probability of occupancy of the cell and a set of probabilities of motion of the content of the cell as a function of the first probability of occupancy of the cell determined at the k th iteration, wherein the second probability of occupancy of the cell and of the set of probabilities of motion of the content of the cell as a function of the first probability of occupancy of the cell determined at the k th iteration is determined based on: C, an identifier of the cell considered; A, an identifier of the cell which contained, at the (k−1) th iteration, what is contained in the cell considered at the k th iteration; O, an occupancy state of the cell considered, from among the empty and occupied states; O −1, an occupancy state of the cell at the (k−1) th iteration; V, a velocity of the cell considered; V−1, a velocity of the cell at the (k−1) th iteration; and Z, observations of the sensors from the first iteration up to the k th iteration; wherein respective velocity and the respective position of a set of dummy particles in the grid are determined at the k th iteration as a function of the velocities, positions of the particles determined at the (k−1) th iteration and of a probability P(V|V−1); the method comprises a step of determining the particles located in each cell as a function of the positions determined and in that the solving of an equation, for a cell, is split into the solving of a static part corresponding to P(0=empty, V=0|ZC) and P(O=occupied, V=0|ZC) and into the solving of a dynamic part corresponding to the P(O=occ, V=v i k,|ZC), i=1 to n k, where n k is the number of particles determined in a cell C for the k th iteration; and wherein the static part of the cell C at the k th iteration being determined as a function of the static part of the cell C determined at the (k−1) th iteration and of P(O|O −1); the probability of P(O=occupied, V=v i k,|ZC) of the dynamic part of the cell C being determined at the k th iteration as a function of the probability P(O=occupied, V=v i k-1,|ZA) calculated at the (k−1) th iteration for the dynamic part of a cell A and of P(O|O −1), where the particle p i determined in the cell C at the k th iteration with a velocity v i k-1 was situated in the cell A at the (k−1) th iteration with a velocity v i k-1, and on completion of the k th iteration, one or more pairs (p i, (v i k, x i k)), where x i k the position of the particle p i at the k th iteration, are duplicated within a cell or deleted so that the number of pairs per cell is dependent on the dynamic part determined for the cell.",
    "2. The method of claim 1, further comprising selecting the pair to be duplicated or deleted, wherein the selection of said pair being carried out as a function of the probability P(O=occupied, V=v i k |ZC) is determined at the k th iteration, and where v i k is a velocity component of the pair.",
    "3. The method of claim 1, wherein the total number of particles in the grid is constant during the iterations.",
    "4. The method of claim 1, wherein P(O=empty, V=0|ZC) is determined at the k th iteration, is denoted as P k (O=empty, V=0|ZC), and is determined as a function of the product of a first term dependent on the first probability of occupancy and of a second term, said second term being dependent on: P k-1 (O =occ, V= 0| ZC).(1−ε)+ P k-1 (O =empty, V= 0| ZC).ε, where ε=P(O=occ|O −1 =empty)=P(O=empty|O −1 =occ); and/or coeff (v i k).P k-1 (O=occupied, V=v i k-1,|ZA).(1−ε), where coeff (v i k) is a decreasing function of ∥v i k ∥, and/or a probability of appearance p a of a new object in the observed scene.",
    "5. A device effective to analyze a dynamic scene observed with the aid of one or more sensors, the device is configured to: define a grid partitioned into cells and corresponding to the observed scene; collect at least one new observation of the one or more sensors at a k th iteration and determining, as a function of the new collected observation, a first probability of occupancy of each cell of the grid and that models the operation of the one or more sensors; determine, for each cell, at the k th iteration, a second probability of occupancy of the cell and a set of probabilities of motion of the content of the cell as a function of the first probability of occupancy of the cell determined at the k th iteration, wherein the device is adapted to determine said second probability of occupancy of the cell and the set of probabilities of motion of the content of the cell as a function of the first probability of occupancy of the cell determined at the k th iteration based on: C, an identifier of the cell considered; A, an identifier of the cell which contained, at the (k−1) th iteration, what is contained in the cell considered at the k th iteration; O, an occupancy state of the cell considered, from among the empty and occupied states; O −1, an occupancy state of the cell at the (k−1) th iteration; V, a velocity of the cell considered; V−1, a velocity of the cell at the (k−1) th iteration; Z, an observations of the sensors from the first iteration up to the k th iteration; wherein the device is further configured to: determine, at the k th iteration, the respective velocity and the respective position of a set of dummy particles in the grid as a function of the velocities, of the positions of the particles determined at the (k−1) th iteration and of the probability P(V|V−1); determine particles located in each cell as a function of the positions determined and to split the solving of an equation, for a cell, into the solving of a static part corresponding to P(O=empty, V=0|ZC) and P(O=occupied, V=0|ZC) and into the solving of a dynamic part corresponding to the P(O=occ, V=v i k,|ZC), i=1 to n k, where n k is the number of particles determined in the cell C for the k th iteration; determine the static part of the cell C at the k th iteration as a function of the static part of a cell C determined at the (k−1) th iteration and of P(O|O −1); and determine the probability of P(O=occupied, V=v i k,|ZC) of the dynamic part of the cell C at the k th iteration as a function of the probability P(O=occupied, V=v i k-1,|ZA) calculated at the (k−1) th iteration for the dynamic part of a cell A and of P(O|O −1), where the particle p i determined in the cell C at the k th iteration with a velocity v i k was situated in the cell A at the (k−1) th iteration with a velocity v i k-1; wherein on completion of the k th iteration, duplicate or delete one or more pairs (p i, (v i k, x i k)), where x i k is the position of the particle p i at the k th iteration, within a cell so that the number of pairs per cell is dependent on the dynamic part determined for the cell.",
    "6. The device of claim 5, adapted to select said pair to be duplicated/deleted, as a function of the probability P(O=occupied, V=v i k |ZC) is determined at the k th iteration, and where v i k is a velocity component of the pair.",
    "7. The device of claim 5, wherein the total number of particles in the grid is constant during the iterations.",
    "8. The device of claim 5, adapted to determine P(O=empty, V=0|ZC) at the k th iteration, denoted P k (O=empty, V=0|ZC), as a function of the product of a first term dependent on the first probability of occupancy and of a second term, said second term being dependent on: P k-1 (O =occ, V= 0| ZC).(1−ε)+ P k-1 (O =empty, V= 0| ZC).ε, where ε=P(O=occ|O −1 =empty)=P(O=empty|O −1 =occ); and/or coeff (v i k).P k-1 (O=occupied, V=v i k-1,|ZA).(1−ε), where coeff (v i k) is a decreasing function of |v i k |, and/or a probability of appearance p a of a new object in the observed scene.",
    "9. A non-transitory computer accessible medium that includes computer-executable instructions stored thereon that are executable by a computing device to perform the method of claim 1."
  ],
  "description_excerpt": "The present invention relates to a method for analyzing a dynamic scene observed with the aid of a block of sensor(s) comprising a step of defining a grid partitioned into cells and corresponding to the observed scene; and the iterative implementation by computer of the steps:\n\nAccording to the BOF (“Bayesian Occupancy Filter”) Bayesian perception algorithms, the observed scene is represented by an occupancy grid subdivided into cells and is analyzed in terms of occupied cells and of their evolution over time. For each cell of this occupancy grid and at each iteration of the algorithm, a probability of occupancy of the cell is calculated, as well as a distribution of probabilities of motion of the content of the cell. This distribution is represented in the form of a motion distribution grid, also called a neighborhood transition histogram.\n\nIn FIG. 1, a view of an occupancy grid of the environment G OCC is represented, of 16 cells by 16 cells. In this representation, the closer together the hatching covering a cell, the larger the value of the cell occupancy probability. A transition histogram Hist(C) determined for a cell, referenced C, of the grid O cc is also represented in FIG. 1. Each box of the histogram determined for the cell C represents, for the time-step considered, the transition from the cell C to said box; with each box of the histogram is thus associated a velocity vector of distinct value; in the present case, the cell at the center of the histogram corresponds to the transition from the cell C to itself.",
  "cpc": [
    "G06T 7/70",
    "B60T 2201/022",
    "B60T 7/22",
    "B60W 2420/403",
    "B60W 2420/42",
    "B60W 40/04",
    "B60W 40/12",
    "G01C 21/3807",
    "G01C 21/3833",
    "G01C 21/387",
    "G01S 17/87",
    "G01S 17/931",
    "G01S 17/936",
    "G06F 17/18",
    "G06K 9/00805",
    "G06N 7/005",
    "G06N 7/01",
    "G06T 2207/10016",
    "G06T 2207/20076",
    "G06T 7/20",
    "G06T 7/277",
    "G06V 20/58",
    "G08G 1/04",
    "G08G 1/166"
  ],
  "ipc": [
    "G01S 17/87",
    "G01S 17/931",
    "G06F 17/18",
    "G06N 7/00",
    "G06T 7/20",
    "G06T 7/70",
    "B60T 7/22",
    "B60W 40/04",
    "G06K 9/00",
    "G06T 7/277",
    "G08G 1/04",
    "G08G 1/16"
  ],
  "assignees": [
    "Centre National de la Recherche Scientifique CNRS",
    "Institut National de Recherche en Informatique et en Automatique INRIA",
    "Commissariat a lEnergie Atomique et aux Energies Alternatives CEA"
  ],
  "inventors": [
    "Christian Laugier",
    "Amaury Negre",
    "Mathias Perrollaz",
    "Lukas Rummelhard"
  ],
  "filing_date": "2015-06-02",
  "publication_date": "2019-05-14",
  "grant_date": "2019-05-14",
  "priority_date": "2014-06-06",
  "application_number": "US-201515316779-A",
  "family_id": "52339210",
  "cited_by_count": 14,
  "citations": [
    "US6393370B1",
    "WO2007028932A1",
    "FR2890773A1",
    "US20080252433A1",
    "US20100305858A1",
    "EP2289754A1",
    "US20120053755A1",
    "US20150154328A1",
    "US20150310146A1",
    "WO2015185846A1"
  ]
}