Engineer's Book

————— PHYSICS – SPACE – ALGORITHMICS ——-

Trajectories and Obstacles Recognition

Written By: Jean-Paul Cipria - Juil• 12•11
Lines Recognition from 3D to 2D Way Trajectory and Obstacles  - © J.P. Cipria - 2011.

Lines Recognition from 3D to 2D Way Trajectory and Obstacles  – © J.P. Cipria – 2011.

Difficult ! Master Level.

Difficult ! Master Level.


Done ... Un Café ?

Done … Un Café ?

Created :2011-07-12 10:16:31. – Modified : 2018-09-13 20:12:54.

The aid systems to pilot vehicles are concepted to increase human and object security … Ces systèmes embarqués répondent en temps réels aux sollicitations des différents capteurs qu’ils soient émissifs comme les radars et lasers ou passifs comme les caméras à vision stéréoscopique. Some French laboratories developed and integrated some algorithms in 2010 (that we don’t use in 2017 31/05/2017)  …  de reconnaissance du milieu extérieur au véhicule de telle sorte à construire son environnement 3D et discriminer les différents obstacles par rapport à la route. Un des prototypes a été monté en 2007 sur un véhicule de la société F… H…. Industries sur une marque S…. (voir citation en fin d’article).

Le problème revient donc à déterminer la ‘profondeur’ des différents objets projetés sur les plans des caméras en fonction du décalage entre celles-ci.

.

.

Trajectoire et reconnaissance d’obstacles
Jean-Paul Cipria
04 mai 2011
Corrections : 01/06/2011
Ajout des courbes de Hough – Exemples des trajectoires – 11/07/2011

.

——————

.

Sommaire

  • Avant-propos
  • Notion sur la vision humaine
  • Les caméras stéréoscopiques
  • Les droites épipolaires
  • La v-disparité
  • Transformée standard de Hough
  • Exemple sur l’espace de Hough
  • Signaux par ondelettes

.

———————

.

Avant-propos

Je reprends trois thèses du laboratoire LIVIC (inrets/lcpc) – 14, route de la Miniière – 78000 Versailles – Satory. Celles de M. Nicolas HAUTIERE, M. Nicolas SOQUET et M. LEFEBVRE.

Les éléments de traitement du signal sont assez vastes ou extrêmement spécialisées … au choix 😉

J’ai donc tenté de rassembler les élements indispensables de traitement numérique des images (ou du signal) afin de permettre aux lecteurs de comprendre les fondements des recherches de ce laboratoire. J’ai essayé d’être simple et de ‘choisir’ dans la liste bibliographique les explications de base servant aux différentes méthodes de ces thèses. Mon choix est évidemment très personnel et très orienté ‘ingénieur’ dans le sens ou je dois fournir les éléments théoriques permettant de ‘faire des calculs’ … qui convergent !

Notion sur la vision humaine

La vision, et la perception de l’environnement par cet intermédiaire, correspondent à 90% des informations qu’utilise la conduite automobile pour maintenir un véhicule sur sa trajectoire et la modifier si un obstacle se présente, ou l’adapter en fonction des circonstances et de l’état de la route et de la météo.

L’attention est essentiellement concentrée sur un angle réduit dans l’axe des deux yeux, à l’endroit où la précision de la vue est la plus grande. La vue périphérique reste néanmoins active tout en sollicitant moins d’attention conciente. Néanmoins un environnement extérieur trop variable perturbe et fatigue le conducteur même s’il n’en est pas conscient directement. A mon avis des travaux devraient être effectués sur cette partie qui entre en jeu de façon importante dans la localisation spatiale et de la réaction du conducteur aux évènements non prévus.

Il s’agit, dans les différents travaux cités, de reconstituer en fait la construction spatiale que fait le cerveau du conducteur et qui lui permet de détecter, de mesurer, d’anticiper les actions nécessaires au pilotage du véhicule et pour préserver sa sécurité et celle des autres.

Les caméras stéréoscopiques

Deux caméras prennent chacune une image du même environnement au même instant. Les caméras sont décalées gauche-droite par rapport à un axe commun. Un des premiers problèmes est de reconstituer l’ensemble des points de l’environnement en 3D à partir de deux images 2D. Si nous prenons un ensemble de points sur une image dite ‘primitive’, par exemple la gauche, nous devons retrouver cet ensemble de points ‘modifiés’ par le point de vue différent sur l’image de droite soit ‘ l’homologue ‘. En général ‘ l’homologue ‘ se trouve être sur une droite qu’il s’agit d’associer à sa primitive sur l’autre image. Un des problème est que différents points à des distances différentes se projètent sur le même ensemble de pixels et que, donc, nous confondons dans le même plan des parties d’objets proches à d’autres plus éloignés.

.

Images stéréo de v-disparité

Images stéréo de v-disparité – Embarqué sur une voiture – Thèse de M. Nicolas Hautière

.

Les droites épipolaires

Une des astuces consiste à déterminer, au calibrage des caméras, l’ensemble des droites épipolaires. En sachant que chaque point M(x, y, z) se retrouvent en Mg = (xg , yg ) et Md = ( xd , yd ) respectivement sur l’image gauche et droite et que ces deux points se situent obligatoirement sur la droite épipolaire gauche et l’autre sur la droite épipolaire droite. Nous réduisons ainsi le calcul de recherche des similitudes de points, de l’ensemble de la surface de la caméra, à seulement une droite sur celle-ci. Ce qui réduit considérablement les calculs.

.

Projection épipolaire en vision stéréo

Fig. 1 – Projection épipolaire en vision stéréo – Thèse détection des obstacles routiers de M. LEFEBVRE – Page 14

.

  1. Détermination d’un point dans le référentiel du véhicule.
    1. Détermination de l’angle optique des caméras par rapport à l’horizontale : Matrice de rotation.
    2. Détermination de la hauteur des caméras par rapport au sol : Matrice de translation.
    3. Détermination de la projection perspective d’un point sur le référentiel véhicule : Matrice de projection.
  2. Construction de l’image de V-Disparité.
    1. Détermination des gradients locaux maximum horizontaux sur les axes épipolaires par corrélation normalisée.
    2. Pour chaque ligne nous accumulons les points de même disparité.
    3. L’astuce ici est que les points Verticalgauche Verticaldroit sont à la même hauteur puisque les caméras ne sont pas décalées en hauteur l’une par rapport à l’autre.
      Il n’en est pas de même du coté horizontal et on calcule ainsi la disparité entre deux points.
      Δ = ugauche – udroit

.

La v-disparité

(Réf. : R. Labayrade et D. Aubert)

Ensuite nous prenons les deux images stéréoscopiques d’une route avec un obstacle.

Résumé

Nous déterminons la droite qui correspond à l’axe droit de la route par transformées de Hough [Fig. 3].

  1. Tout les points de l’obstacle sont projetés de la gauche vers le coté droit sur l’axe de route. Le bord inférieur de l’obstacle projeté croise la droite correspondant à la route [Fig. 2].
  2. L’obstacle est ainsi figuré comme un poteau sur l’axe droit de la route. Le calcul de la distance de l’obstacle est une simple 😉 projection en 3D.

.

Trajectoire avec Obstacle - Calcul par Hough

Fig. 2 – Trajectoire avec Obstacle – Calcul par Hough

.

Explications.

  1. Elaboration d’une image originale simple.
    1. Nous traçons deux droites en perspectives sur un fond noir qui représentent les limites des voies gauche et droite de la route.
    2. Plaçons un rectangle représentant un obstacle que nous hachurons de bandes verticales à l’intérieur des deux voies.

.

  • Calculs de hough.
    1. Positionnons le seuil de détection à une valeur supérieure à 25%.
    2. Lançons le calcul des transformées de Hough.

    .

  • Interprétation.
    1. Sur la transformée de Hough : Les points brillants sont les intersections des nombreuses cosinus générées par le calcul.
      L’intensité des points est proportionnelle aux nombres de points qui sont en alignement (suivant une droite commune).
      L’abscisse est l’angle θ du vecteur r.
      L’ordonnée est le module du vecteur r.
    2. Les points les plus brillants, suivant un contraste fort déterminé par le seuil réglé précédement, générent les droites de la troisième figure.

    .

  • Conclusions.
    1. Les deux voies droites et gauches sont correctement déterminées.
    2. Les projections des valeurs hautes et basses de l’obstacle peuvent être directement déterminées sur la voie de droite.
      .

.

Droite-Trajectoire-Route-Obstacle-Hough

Droite-Trajectoire-Route-Obstacle-Hough

 

.

————————–

.

Transformée Standard de Hough

SHT : Standard Hough Transform

La transformée de Hough est une technique de reconnaissance de formes inventée en 1962 par Paul Hough, utilisée dans le traitement d’images numériques.

Nous déterminons une droite de pente négative dont nous tirons un vecteur perpendiculaire r, qui passe par l’origine et qui ‘s’arrêtte’ sur cette droite. L’angle qui sépare ce vecteur r et l’axe des x est θ.

  • y = a . x + b

La pente de la droite est a :

  • a = – sin(θ) / cos(θ)

r est la projection de b :
(Ou autrement dit b est l’hypothénuse du triangle et r le coté opposé)

  • b = r / sin(θ)

donc l’expression de la droite ‘pointée’ par ce vecteur r perpendiculaire est :

  • y = – [ sin(θ) / cos(θ) ] . x + r / sin(θ)

En projetant le vecteur r sur les deux axes nous avons :

  • r = X0 . cos(θ) . ex + Y0 . sin(θ) . ey
  •  \vec{r} = X_0.cos(\theta).\vec{e_x}+Y_0.sin(\theta).\vec{e_y}

Comme ce vecteur r est à l’origine et croise la droite aux points X0 et Y0 nous pouvons en déduire que son module est :

  • |r|² = X0² + Y0²
  •  r=\sqrt{X_0^2+Y_0^2}

Il s’agit maintenant de représenter r dans l’espace paramétrique (θ, r) de Hough.

Une courbe sinusoïdale dans le plan (r, θ), est unique à ce point. Si deux courbes correspondant à deux points se superposent dans l’espace de Hough alors l’endroit où elles se croisent correspond à une droite qui passe par deux points. Plus généralement, un ensemble de points qui forment une ligne droite, va produire des sinusoïdes qui se croisent à des paramètres de cette ligne.

Exemple sur l’espace de Hough

Je prends la droite : y=ax+b avec :

a = -1

et b=4

Je trace l’ensemble des courbes :

r = x.cos(\theta).+y.sin(\theta).

qui se croiseront en \theta=45\textdegree{} et R_0 = 2,83

.

Transformée de Hough de la droite y = -x + 4

Transformée de Hough de la droite y = -x + 4

.

Réferences

Voici la table dont sont issues les courbes ci-dessus. Fichier PDF sur ce site :

.————————-.

Signaux par ondelettes

Un traitement plus détaillé est absolument nécessaire en traitement du signal, nottamment les décompositions sur des bases orthogonales autres que les transformées de Fourier (voir le lien ci-dessous). Les transformées en ondelettes (wavelets transforms), bien qu’établies sur les mêmes fondements théoriques et les mêmes types de calculs que les TF, permettent une compression (et une décompression) élevée des images.

De plus, en possédant le jeu réduit des coefficients ‘décrivant’ le signal à analyser, on peut espérer que les calculs soient d’autant réduits que ce que la compression a permis de le faire sur les coefficients ?

Le grand avantage des ondelettes par rapport aux TF est que le signal à traiter n’est pas obligatoirement périodique ni illimité dans le temps.

Une technique sur les FT consiste à convoluer le signal à traiter avec une fenêtre dont la décroissance est grande [L²] comme, par exemple, une fenêtre de Hamming. Le calcul est à ce moment ‘équivalent’ à une transformée en ondelettes et permet d’éliminer les arctefacts des FT dues aux repliements de spectre (puisque le signal est considéré comme infini mais ne l’est pas en réalité).

Un autre des intérêts des ondelettes c’est que nous pouvons choisir NOTRE type d’ondelettes. Celle qui, à la convolution, permet de reconstituer ou représenter le signal dans une ‘base’ qui nous convient. Ce qui est un luxe suprême ! 😉 Un peu comme passer des coordonnées Euclidiennes aux coordonnées polaires pour représenter une orbite spatiale. Ce qui facilite grandement par la suite les calculs.

.—————————.

Références

.

  • [R. LABAYRADE, D. AUBERT and J. P. TARELl-2010] R. LABAYRADE, D. AUBERT and J. P. TARELl
    « Real Time Obstacle Detection on Non Flat Road Geometry through ‘V-Disparity’ Representation »,
  • Here is the original paper in PDF format : Real Time Obstacle Detection in Stereovision by V-Disparity.
  • Base de données des thèses de l’IRETS :
    https://cassis.inrets.fr/index.php?RUBRIQUE_ID=2

Sur ce site :

  • Thèse Detection des Obstacles Routiers – M. LEFEBVRE
  • Sur ce site : Thèse – Détection conditions de visibilité estimation de la distance par vision embarquée – Nicolas Hautiere 30/07/2005.
  • Sur ce site : Thèse – Navigation Autonome Sur Routes – Nicolas SOQUET – Laboratoire du LIVIC
  • Sur ce site : Candidature ingénieur informatique système de vision stéréoscopique pour voiture
  • Sur ce site : Chargé de recherche vision stéréoscopique pour voiture – Laboratoire Livic.
  • Transformée de Hough : en Français mais très sommaire.
  • Hough transform – Site plus détaillé que le Français :
    http://en.wikipedia.org/wiki/Hough_transform
  • Programmes en C de calcul d’accumulateur de Hough :
    http://sourceforge.net/search/?q=hough
  • Vidéo de disparité :
    http://pages.ief.u-psud.fr/AXIS/PICAR/PICAR_25_septembre_2008.html

Logiciels et programmations de Hough

  • Programme en C et C++ sur CPPFrance (fichier zip) : cppfrance_TRANSFORMEE-HOUGH-DETECTION-DROITES
  • Programme exécutable Java transformée de hough (fichier zip) : HoughJarSrc

Citation de l’article Clubic.com

Informatique et high tech’ …

Le groupe d’industrie lourde et constructeur automobile Fuji Heavy Industries (marque Subaru) a lui aussi imaginé un outil d’aide à la conduite basé sur une caméra stéréo qui voit la route en trois dimensions, alerte le conducteur sur un danger et freine à sa place. Cette caméra stéréo permet de capter des images tridimensionnelles à partir desquelles le système repère automatiquement la présence de voitures, cyclistes ou piétons aux alentours, pour prévenir le conducteur et même agir à sa place. Le dispositif est par exemple censé appuyer sur la pédale de frein pour éviter les chocs lorsque, prise dans les ralentissements, la voiture se rapproche dangereusement de celle qui la précède.

Contrairement à d’autres modes d’assistance à la conduite, le dispositif de Fuji Heavy ne requiert pas de radars et autres capteurs complexes, toutes les informations nécessaires à la reconnaissance d’objets et à l’analyse de distance proviennent de la caméra stéréo, ce qui est une première. Selon FHI, cette particularité permet une forte réduction des coûts et un important potentiel de marché. FHI avait été le premier constructeur mondial en 1999 à avoir installé une caméra d’assistance à la conduite dans une voiture.

La nouvelle génération repose sur la capture de plus en plus sophistiquée des images et la capacité du système à analyser les situations, voire à prendre les initiatives à la place du conducteur, le tout dans le but de renforcer la sécurité sur les routes. FHI prévoit d’installer son nouveau dispositif sur une partie de ses véhicules qui seront commercialisés au Japon à partir de l’an prochain. …’.

Mots clés

Fuji Heavy Industries – Marque Subaru.

Aide à la conduite des véhicules.

Algorithmes de traitement des images

imaging , vision enhancement, stereoscopic vision, road obstacle detection, non flat road geometry, semi-global matching, real time processing..

.

Jean-Paul Cipria – Mai 2011.

.

You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Anti-Spam Quiz: