Patent application EP17174279A (EP), filed 2017-06-02
Publication number: EP3252615A1
Title: METHOD AND SYSTEM FOR DETERMINING CELLS CROSSED BY A MEASURING OR VIEWING AXIS
Abstract: L'invention concerne L'invention concerne un procédé de perception de corps matériels destiné à localiser lesdits corps sur une grille d'occupation G à au moins 2 dimensions, ayant un premier pas de résolution R G , et comprenant un ensemble de cellules représentées par des sommets (couramment appelés vertex en anglais) et des segments reliant ces sommets, le procédé utilisant un capteur de détection d'obstacles positionné en point source S, comportant au moins les étapes suivantes : ¢ Acquisition par ledit capteur d'une mesure de la position d'un corps matériel détecté en un point F ; ¢ Définir les coordonnées d'un point M en utilisant un espace discrétisé à l'aide d'un pas spatial ´ plus fin que le pas de résolution R G , ¢ Initialiser un paramètre d'erreur, entier, représentatif de la position d'au moins une coordonnée d'un sommet de la cellule contenant le point source S dans l'espace discrétisé par rapport à un trajet défini dans l'espace d'observation, ¢ Calculer la valeur du paramètre d'erreur pour au moins un premier sommet de la cellule de la grille en cours, en réalisant des additions ou soustractions de nombres entiers, ¢ Etablir la liste {c i } des cellules situées sur le trajet [SF] ou situées à une distance prédéfinie du trajet [SF].
IPC codes: G05D   1/    00            A I
G06F  17/    10            A I
G06T  15/    00            A I
Claims: number: 1
text: Procédé de perception de corps matériels destiné à localiser lesdits corps sur une grille d'occupation G à au moins 2 dimensions, ayant un premier pas de résolution R<G> , et comprenant un ensemble de cellules représentées par des sommets et des segments reliant ces sommets, le procédé utilisant un capteur de détection d'obstacles positionné en un point source S et comprenant les étapes suivantes :
number: 2
text: Procédé selon la revendication 1 dans lequel, au cours de l'étape f, on calcule, pour chaque sommet V « supplémentaire » de la cellule courante c<i> , autre que le sommet initial, une valeur dudit paramètre d'erreur E, correspondant à Err<d> (V), ce calcul consistant à réaliser une opération d'addition ou de soustraction entre nombres entiers, entre d'une part ladite valeur du paramètre E obtenue pour le sommet initial V0<i> de la cellule courante c<i> , et correspondant à Err<d> (V0<i> ), et d'autre part une valeur d'incrément entière (Δ) prédéfinie en fonction des coordonnées des points S et F dans l'espace discrétisé, et dans lequel, au cours de l'étape g, on effectue les étapes suivantes :
number: 3
text: Procédé selon la revendication 1 ou 2, dans lequel la grille d'occupation est définie en 2 dimensions et dans lequel, la fonction d'erreur Err<d> (M) est définie par : Err d M = m − m s ⋅ l F − l S − l − l s ⋅ m F − m S .
number: 4
text: Procédé selon les revendications 2 et 3, dans lequel lors de l'étape g, en comparant le signe des erreurs calculées on détermine la prochaine cellule traversée, de la manière suivante:
number: 5
text: Procédé selon la revendication 1 ou 2, dans lequel la grille d'occupation est définie en 3 dimensions et dans lequel, la fonction d'erreur Err<d> (M) est définie pour un point M(l, m, n) en coordonnées entières de la façon suivante : Err d_xy M = m − m s ⋅ l t − l s − l − l s ⋅ m t − m s
number: 6
text: Procédé selon la revendication 1 dans lequel, au cours de l'étape j, les cellules listées correspondent aux cellules pour lesquelles un de leurs sommets est associé avec une valeur de paramètre d'erreur comprise entre une valeur d'erreur minimale (e<min> ) et une valeur d'erreur maximale (e<max> ) prédéfinies..
number: 7
text: Procédé selon la revendication 5, dans lequel les valeurs d'erreur minimale et maximale sont fonction, pour une cellule donnée, de la distance entre le sommet initial de cette cellule et ledit sommet S.
number: 8
text: Procédé selon l'une des revendications précédentes, dans lequel les coordonnées d'un point M dans l'espace discrétisé sont représentées, sur chaque axe d'un repère, par un entier défini par un mot binaire de W bits, et dans lequel un point M appartient à une cellule de la grille d'occupation, chaque cellule étant définie, pour chaque axe du repère par un indice entier défini par un mot binaire de d bits, et dans lequel W est supérieur à d et dans lequel W et d sont choisis de sorte que d < W ≤ T + d − 1 2
number: 9
text: Procédé selon la revendication 1, dans lequel les coordonnées d'un point M dans l'espace discrétisé sont représentées, sur chaque axe d'un repère, par un entier défini par un mot binaire de W bits, et dans lequel on détermine les coordonnées entières (u<x> , u<y> , u<z> ) d'un point M à partir de coordonnées sphériques en calculant l'écart au centre du repère K u x − u x K = D ⋅ T x α ω
number: 11
text: Procédé selon la revendication 9caractérisé en ce que l'on normalise les valeurs des tables précitées par une valeur D max = 2 ⋅ R
number: 12
text: Dispositif pour déterminer les coordonnées de cellules c<i> susceptibles d'être traversées dans un espace d'observation représenté par une grille G ayant un premier pas de résolution, une cellule étant représentée par des sommets et des côtés ou segments reliant ces sommets,caractérisé en ce qu' il comporte au moins les éléments suivants :
number: 13
text: Dispositif selon la revendication 12,caractérisé en ce que l'espace d'observation est défini par un capteur embarqué sur un véhicule (1) en déplacement eten ce qu' une cellule sélectionnée est renseignée par une valeur de probabilité d'occupation par un obstacle.
Office action: search_report, dated 2017-12-06
Rejection reasons: novelty_epc_54
inventive_step_epc_56
Prior art cited: ref_id: - ARMIN HORNUNG ET AL: "OctoMap: an efficient probabilistic 3D mapping framework based on octrees", AUTONOMOUS ROBOTS, vol. 34, no. 3, 7 February 2013 (2013-02-07), pages 189 - 206, XP055147395, ISSN: 0929-5593, DOI: 10.1007/s10514-012-9321-0
ref_type: npl
severity: background
ref_id: - DAVID GONZALEZ-ARJONA ET AL: "Simplified Occupancy Grid Indoor Mapping Optimized for Low-Cost Robots", ISPRS INTERNATIONAL JOURNAL OF GEO-INFORMATION, vol. 2, no. 4, 14 October 2013 (2013-10-14), pages 959 - 977, XP055344178, DOI: 10.3390/ijgi2040959
ref_type: npl
severity: background
ref_id: - GUTMANN J-S ET AL: "A Floor and Obstacle Height Map for 3D Navigation of a Humanoid Robot", ROBOTICS AND AUTOMATION, 2005. PROCEEDINGS OF THE 2005 IEEE INTERNATIONAL CONFERENCE ON BARCELONA, SPAIN 18-22 APRIL 2005, PISCATAWAY, NJ, USA,IEEE, 18 April 2005 (2005-04-18), pages 1066 - 1071, XP010872097, ISBN: 978-0-7803-8914-4, DOI: 10.1109/ROBOT.2005.1570257
ref_type: npl
severity: background
ref_id: - MEL SLATER: "Tracing a ray through uniformly subdivided n- dimensional space", THE VISUAL COMPUTER, 1 January 1992 (1992-01-01), XP055346587, Retrieved from the Internet <URL:http://rd.springer.com/content/pdf/10.1007/BF01901027.pdf> [retrieved on 20170216]
ref_type: npl
severity: background
ref_id: - Y K LIU ET AL: "A General Multi-step Algorithm for Voxel Traversing Along a Line", COMPUTER GRAPHICS FORUM VOLUME, 31 October 2007 (2007-10-31), pages 73 - 80, XP055346809, Retrieved from the Internet <URL:http://onlinelibrary.wiley.com/store/10.1111/j.1467-8659.2007.01097.x/asset/j.1467-8659.2007.01097.x.pdf?v=1&t=iz8h0o8x&s=fddec98ff67e7d4ff2199309c76082b9e1e58362> [retrieved on 20170216], DOI: 10.1111/j.1467-8659.2007.001097.x
ref_type: npl
severity: background
ref_id: - Y. K. LIU ET AL: "An Integer One-Pass Algorithm for Voxel Traversal", COMPUTER GRAPHICS FORUM, vol. 23, no. 2, 1 June 2004 (2004-06-01), GB, pages 167 - 172, XP055346815, ISSN: 0167-7055, DOI: 10.1111/j.1467-8659.2004.00750.x
ref_type: npl
severity: background
ref_id: - CLEARY J G ET AL: "Analysis of an algorithm for fast ray tracing using uniform space subdivision", VISUAL COMPUTER, SPRINGER, BERLIN, DE, vol. 4, no. 2, 1 January 1988 (1988-01-01), pages 65 - 83, XP008121704, ISSN: 0178-2789
ref_type: npl
severity: background
ref_id: - TIANA RAKOTOVAO ET AL: "Integration of multi-sensor occupancy grids into automotive ECUs", PROCEEDINGS OF THE 53RD ANNUAL DESIGN AUTOMATION CONFERENCE ON, DAC '16, ACM PRESS, NEW YORK, NEW YORK, USA, 5 June 2016 (2016-06-05), pages 1 - 6, XP058259044, ISBN: 978-1-4503-4236-0, DOI: 10.1145/2897937.2898035
ref_type: npl
severity: background
ref_id: - ANONYMOUS: "Conference Paper: Integration of multi-sensor occupancy grids into automotive ECUs", JULIEN MOTTIN - PUBLICATIONS, 7 February 2017 (2017-02-07), ResearchGate, XP055343258, Retrieved from the Internet <URL:https://www.researchgate.net/profile/Julien_Mottin/publications> [retrieved on 20170207]
ref_type: npl
severity: background
ref_id: - GUTMANN J-S ET AL, "A Floor and Obstacle Height Map for 3D Navigation of a Humanoid Robot", ROBOTICS AND AUTOMATION, 2005. PROCEEDINGS OF THE 2005 IEEE INTERNATIONAL CONFERENCE ON BARCELONA, SPAIN 18-22 APRIL 2005, PISCATAWAY, NJ, USA,IEEE, (20050418), doi:10.1109/ROBOT.2005.1570257, ISBN 978-0-7803-8914-4, pages 1066 - 1071, XP010872097 [Y] 1-13 * abstract * * sec. III *
ref_type: npl
severity: obviousness
ref_id: - Mel Slater, "Tracing a ray through uniformly subdivided n- dimensional space", The Visual Computer, (19920101), URL: http://rd.springer.com/content/pdf/10.1007/BF01901027.pdf, (20170216), XP055346587 [Y] 1-13 * sec. 1; sentence  1 * * sec 2-4 * * sec. 5; paragraphs  [0010] - [0013] *
ref_type: npl
severity: obviousness
ref_id: - Y K Liu ET AL, "A General Multi-step Algorithm for Voxel Traversing Along a Line", COMPUTER GRAPHICS forum Volume, doi:10.1111/j.1467-8659.2007.001097.x, (20071031), pages 73 - 80, URL: http://onlinelibrary.wiley.com/store/10.1111/j.1467-8659.2007.01097.x/asset/j.1467-8659.2007.01097.x.pdf?v=1&t=iz8h0o8x&s=fddec98ff67e7d4ff2199309c76082b9e1e58362, (20170216), XP055346809 [A] 1-13 * abstract * * sec. 2, 3 *
ref_type: npl
severity: background
ref_id: - Y. K. LIU ET AL, "An Integer One-Pass Algorithm for Voxel Traversal", COMPUTER GRAPHICS FORUM, GB, (20040601), vol. 23, no. 2, doi:10.1111/j.1467-8659.2004.00750.x, ISSN 0167-7055, pages 167 - 172, XP055346815 [A] 1-13 * abstract * * sec. 2, 3 *
ref_type: npl
severity: background
ref_id: - CLEARY J G ET AL, "Analysis of an algorithm for fast ray tracing using uniform space subdivision", VISUAL COMPUTER, SPRINGER, BERLIN, DE, (19880101), vol. 4, no. 2, ISSN 0178-2789, pages 65 - 83, XP008121704 [A] 1-13 * sec. Initialization *
ref_type: npl
severity: background
ref_id: - TIANA RAKOTOVAO ET AL, "Integration of multi-sensor occupancy grids into automotive ECUs", PROCEEDINGS OF THE 53RD ANNUAL DESIGN AUTOMATION CONFERENCE ON, DAC '16, ACM PRESS, NEW YORK, NEW YORK, USA, (20160605), doi:10.1145/2897937.2898035, ISBN 978-1-4503-4236-0, pages 1 - 6, XP058259044 [XP] 1-13 * the whole document *
ref_type: npl
severity: novelty_destroying
ref_id: - Anonymous, "Conference Paper: Integration of multi-sensor occupancy grids into automotive ECUs", Julien Mottin - Publications, ResearchGate, (20170207), URL: https://www.researchgate.net/profile/Julien_Mottin/publications, (20170207), XP055343258 [L] * second citation states January 2016 as publication date *
ref_type: npl
severity: background
Final disposition: pending (2017-12-06)