FR 2677835 A1 19921218 FR 9107340 A 19910614 La présente invention concerne un procédé de localisation d'objets sur l'image d'une scène les contenant. Il peut par exemple s'agir de localiser des fruits sur chaque vue prise par une caméra montée sur un robot de cueillette, pour lancer un bras de cueillette et saisir les fruits un à un. La demanderesse a déjà proposé un tel robot de cueillette, objet de sa précédente demande de brevet français 90 02 179 qu'elle entend être considérée comme partie intégrante de la présente demande. Succinctement, celle-ci décrit un robot comprenant un chariot automobile pas à pas entre deux haies ou rangées d'arbres, portant au moins une caméra de détection de fruits et un bras de cueillette, un panier de récolte élémentaire, une palette de récolte globale et une centrale de commande de la caméra et du bras. A chaque pas, la caméra prend des vues et quand tous les fruits de ce pas ont été cueillis, par aspiration, le chariot avance d'un pas. Il a brièvement été fait référence, dans la demande de brevet antérieure précitée, à un procédé de localisation des fruits sur les vues prises par la caméra. Il s'agit d'un procédé classique, mais qui n'est pas pleinement satisfaisant. La présente invention vise à proposer un procédé de localisation performant qui, dans sa mise en oeuvre la plus élaborée, identifie bien les objets à localiser en tant que tels, distingue plusieurs objets mutuellement cachés d'un plus gros, un même objet en partie masqué par un obstacle, de plusieurs, et détermine convenablement leur accessibilité, bref, un procédé qui optimise la cueillette quand les objets à localiser sont des fruits. A cet endroit, une remarque liminaire s'impose. Il est vrai que l'application visée à priori par l'invention de la présente demande est la cueillette de fruits et, plus particulièrement encore, de pommes. Il est aussi vrai que les pommes sont des objets pseudosphériques auxquels s'appliquent bien l'invention. Mais cette application ne doit nullement être considérée comme limitative de l'invention. La présente invention concerne un procédé de localisation d'objets sur une image de départ d'une scène les contenant et formée d'une matrice de pixels de niveaux de gris respectifs déterminés, dans lequel on détermine les pixels disposés sur au moins une monotonie pour éliminer les autres et substituer à l'image de départ une image binaire de points monotones. Avantageusement, on détermine, pour chaque pixel de l'image de départ, la direction de la variation maximale des niveaux de gris de pixels voisins et on substitue aux points monotones de l'image binaire les directions de gradient correspondants pour obtenir une image des directions de gradient des points monotones. Avantageusement encore, on répartit les pixels de l'image de niveaux de directions de gradient en régions de pixels sensiblement de mêmes directions de gradient, respectivement, et connexes. Dans ce cas, on peut localiser les régions ou secteurs en déterminant leurs centres de gravité. De préférence, on détermine les zones dépourvues d'objets à localiser par analyse de profils transversaux, avantageusement pour classer les régions ou secteurs de région au moins en secteurs ou régions contenant des objets à localiser et en secteurs ou régions ne contenant pas d'objets à localiser. On peut exploiter la convexité, respectivement la concavité, de la variation des niveaux de gris le long des profils transversaux. Pour éliminer les secteurs de région pouvant conduire à des objets incohérents, on les regroupe par convergence et/ou continuité de leurs directions de gradient et/ou par proximité. L'invention sera mieux comprise à l'aide de la description suivante de la mise en oeuvre préférée du procédé, en référence au dessin annexé, sur lequel - la figure 1 représente une image de départ d'une scène contenant des objets à localiser; - la figure 2 représente l'image résultant du masquage de l'image de la figure 1 avec les points situés sur des profils monotones; - la figure 3 représente le cercle de quantification et de codification des directions de gradients; - la figure 4 représente l'image de directions de gradient de points monotones tirée de l'image binaire de la figure 2; - la figure 5 représente l'image de courbes d'isoniveaux de gris tirée de l'image de la figure 1; - la figure 6 représente une portion de l'image de la figure 5 illustrant l'analyse de profils transversaux;; - la figure 7 représente un profil transversal d'une région d'un objet à localiser; - la figure 8 représente la détermination, par vote majoritaire, des régions d'un objet à localiser et des zones dépourvues d'objet à localiser; - la figure 9 représente l'image des régions d'objets à localiser; - les figures 10 illustrent les regroupements de régions dans les sens direct et indirect; - la figure 11 illustre le procédé de calcul de la distance d'un objet par stéréovision, avec deux caméras et - les figures 12 représentent des images prises par les deux caméras de la figure 11. Un objet éclairé en lumière diffuse apparait éclairé de façon uniforme. Un objet pseudosphérique, comme certains fruits (pommes, oranges), éclairé en lumière spéculaire apparait sous forme d'une tache brillante autour de laquelle l'éclairement diminue de façon monotone, au sens mathématique du terme. On parle de variation monotone de l'éclairement depuis, ou vers, le point de spécularité. Soit donc une image, ou vue, prise par une caméra, d'une scène contenant des objets pseudosphériques à localiser, ici des pommes d'un pommier, formée d'une matrice d'éléments d'image, c'est-à-dire de points ou pixels pij de niveaux de gris gij (figure 1). l.Extraction des monotonies Une monotonie est un ensemble de points d'un segment de droite dont les niveaux de gris respectifs gij varient de façon monotone. On ne considèrera ici que les monotonies strictes, sans palier, pour écarter les zones de niveau de gris uniforme comme le ciel ou le fond, et, par simplicité, que les monotonies croissantes. Pour chaque pixel Pi;, on examine, au cours de cette première étape d'extraction des monotonies, s'il est monotone, c'est-à-dire s'il se trouve sur au moins une monotonie de l'une de, ici, huit directions régulièrement espacées sur 360 degrés. L'extraction des monotonies s'effectue en trois étapes. 1.1 Calcul de la pente On calcule en chaque point de l'image sa pente, c'est-à dire la différence entre le niveau de gris du point considéré et celui du point précédent dans une des huit directions. 1.2 Seuillage de la pente > On ne retient que les points pour lesquels la variation est significative, c'est-à-dire supérieure à celle du bruit. 1.3 Sélection des monotonies longues On ne retient dans une direction donnée que les points situés sur un profil monotone (pente positive) dont la longueur est significative. Cette opération est réalisée à l'aide d'une opération de morphologie mathématique, l'ouverture, décrite dans l'ouvrage de J.Serra, "Image Analysis and Mathematical Morphology", Academic Press, 1982. On remarquera que l'extraction des monotonies peut s'effectuer à l'aide de deux opérations de base, la convolution et le seuillage. A la matrice de points Pij, on substitue une matrice de monotonie, de mêmes dimensions, dont sont éliminés les points non monotones (0) pour ne conserver que les points monotones (1) (figure 2). Les contours des régions de points monotones sont bien placés en vue d'une bonne localisation. 2.Constitution de régions 2. I Détermination des directions de gradient local On considère à nouveau l'image des niveaux de gris, la matrice de points de départ, et on détermine, pour chaque point p la direction dans laquelle la variation de la fonction niveau de gris f est la plus grande.On calcule le gradient local de f, suivant deux directions Ox et Oy respectivement parallèles aux lignes et aux colonnes de la matrice, à l'aide de deux masques de convolution, en l'occurence deux masques de Prewitt, l'un -1 0 +1 -l 0 +1 -1 0 +1 pour le gradient selon Ox et l'autre -l -l -1 O O O 1 1 1 pour le gradient selon Oy. On fait glisser l'un après l'autre ces masques sur la matrice de points en les centrant sur chacun des points Pijr ce qui permet, par multiplication matricielle, de calculer les différences entre le niveau de gris de chaque point et les niveaux de gris des six points voisins, autres que ceux situés sur l'axe perpendiculaire à l'axe de calcul, et par conséquent, pour chaque point En posant on obtient la direction D de gradient local comme suit Les directions D sont ici quantifiées sur huit secteurs angulaires de 45 degrés, depuis le niveau S, compris entre 337,5 degrés et 22,5 degrés, l'axe Ox s'étendant dans la direction O (figure 3), et les secteurs étant à leur tour codifiés en huit niveaux de gris différents. Ayant obtenu la direction de gradient local de chaque point Pij, on substitue aux points monotones de l'image binaire, obtenue à l'issue de l'étape d'extraction des monotonies, les directions de gradient de ces points monotones pour obtenir l'image des directions de gradient des points monotones (figure 4). 2.2 Analyse de connexité A cette étape du procédé de localisation, on répartit les pixels de l'image des directions de gradient en régions de pixels de même direction de gradient et connexes, connexes deux à deux ou par propagation. Si le pas des pixels de l'image, sur une ligne ou une colonne, est égal à 1, deux pixels sont dits connexes si ils sont espacés d'une distance inférieure ou égale à 6 ~ en d'autres termes, huit pixels peuvent être connexes à un pixel donné et un premier pixel, connexe à un deuxième pixel, lui-même connexe à un troisième, est connexe à ce troisième pixel par propagation. On notera que deux régions ne peuvent pas être sécantes; l'une peut toutefois être incluse dans l'autre. La répartition des pixels en régions, ou l'étiquetage des pixels en composantes connexes, peut s'effectuer conformément à l'enseignement de l'ouvrage "Computer vision, D.H. Ballard, C.M. Brown, Prentice Hall, Inc., Englewood cliffs, New Jersey 07632, 1982". 3.Extraction de caractéristiques A cette étape du procédé, on localise les régions, ou secteurs, et on extrait des caractéristiques des régions précédemment constituées, comme leurs formes, leurs localisations, par la détermination de leurs centres de gravité, etc., pour faciliter la dissociation d'objets différents. Cette étape peut être mise en oeuvre selon l'enseignement de l'ouvrage "Digital image processing, R.C. Gonzalez, P. Wintz, Addison and Wesley Publishing Company, 1977". 4.Classement des récrions Les étapes précédentes ont permis de constituer des régions, ou segments de région, dont on a déterminé les centres de gravité et, par définition, les directions de gradient, et qui pointent vers les points de spécularité, c'est-à-dire de localiser des plages devant contenir des pommes. Mais à l'issue de ces étapes, il subsiste encore de nombreuses zones correspondant à des feuilles et des branches qu'il faut donc éliminer au mieux. Le classement des régions est effectué par analyse des profils transversaux. On considère encore et à nouveau l'image de départ des niveaux de gris ou, mieux, sa représentation sous forme de courbes d'iso-niveaux de gris (figure 5). Plus précisément, considérons une portion d'image de courbes iso-niveaux de gris, telle que représentée sur la figure 6 et correspondant effectivement à une pomme, et, par exemple, la courbe C(P) passant par le point P. Soit T(P) la tangente à la courbe C(P) en P, perpendiculaire à la monotonie M. La fonction niveaux de gris f, le long de la droite T(P) a le profil de la figure 7, avec f(P) > f(Pi) Pi étant un point, autre que P, appartenant à la droite T(P). Pour chaque région, on balaye de façon discrète la droite T(P) perpendiculairement à elle-même et on observe les formes des profils de la fonction f. En pratique, la relation f(P) > f(Pi) n'est pas toujours vérifiée pour une pomme, à cause de la non perfection du modèle, du bruit et des effets de la quantification des directions de gradient. Aussi, P n'est pas nécessairement un point pour lequel la valeur de la fonction f est maximale et on peut parfois observer des changements locaux de signe de la pente des courbes. Néanmoins, le profil général d'une région de pomme a une forme en cloche avec un faible nombre de changements de pente si bien qu'on retient trois types de profil - un profil convexe, en forme de montagne, pour les régions "pomme", - un profil concave, en forme de vallée, pour les régions non pomme", - les autres formes de profil, pour les régions indéterminées. On classe alors les régions, ou plus exactement des secteurs de région, selon l'un des trois types de profil retenus par vote majoritaire, tous les pixels d'un même secteur étant analysés selon une direction commune. En référence à la figure 8, le secteur S de la région R est analysé pour en extraire les profils transversaux fp parallèlement à la direction commune de balayage. Ces profils fp sont ensuite classés dans l'un des trois types t retenus et, par un vote majoritaire, on proclame que le secteur analysé est un secteur pomme, non pomme ou indéterminé. On a représenté sur la figure 9 l'image des régions classées pomme. On constate par ailleurs que les régions indéterminées sont, pour la plupart, petites et allongées dans la direction perpendiculaire à celle de l'analyse et que certains éléments de feuillage et de branchage de taille importante apparaissent sur l'image des régions non pomme et sont donc bien éliminés. 5.Reqroupement des régions A l'issue de l'étape de classement des régions, on dispose d'un ensemble de secteurs ou de régions définis par - leur appartenance à une classe (pomme, non-pomme, indéterminée) (étape 4), - leur direction moyenne de gradient D (étapes 1, 2), - certaines de leurs caractéristiques géométriques (étape 3). Il est maintenant proposé de détecter les pommes totalement ou partiellement visibles, d'éliminer les régions pouvant conduire à des objets incohérents et de procéder à un "dégrappage", en dissociant les unes des autres les pommes réunies en grappes. A cet effet, il est procédé à une restitution des pommes par regroupement, ou fusion, de secteurs cohérents par - la convergence de leurs directions de gradient, - la continuité de leurs directions de gradient, - leur proximité bref, par regroupement de secteurs autour d'une même zone spéculaire. 5.1 Convergence Deux secteurs Si et Sj, de centres de gravité Gi et G. et de vecteurs unitaires Di et Dj issus de G. et Gj et orientés selon les directions de gradient respectives, satisfont à l'exigence de convergence Si les deux demidroites supportant les vecteurs Di et Dj se coupent. 5.2 Continuité de la direction de gradient La variation de la direction du gradient autour de la zone spéculaire d'une pomme doit être continue et cette caractéristique est prise en compte pour le regroupement des régions. 5.3 Proximité La proximité des secteurs est aussi un critère important à prendre en compte au cours de l'étape de reconstitution. il faut éviter d'associer des secteurs trop éloignés les uns des autres et qui pourraient ne pas appartenir au même objet. La restitution de pomme consiste donc à retenir une première région, selon une stratégie particulière, en commençant par exemple par les pommes les plus grosses, les plus accessibles, les plus proches situées en bas de l'image et appartenant à des grappes, et à lui associer d'abord une deuxième région - qui touche la première, - dont la direction de gradient est la plus voisine de celle de la première région, - dont la direction de gradient converge avec celle de la première région et, éventuellement, - dont la surface est la plus grande. A la deuxième région, on en associe une troisième, sans tenir compte de la première, et ainsi de suite. Comme paramètre de proximité de deux secteurs, on peut aussi considérer leur distance pondérée qui tient compte de l'étalement, des points des secteurs. A cet effet, on peut les modéliser par des formes simples, par exemple des cercles de surfaces équivalentes, et calculer de façon analytique la distance qui les sépare, soit la distance entre centres diminuée de la somme de leurs rayons. Dans ce cas, au lieu d'associer deux secteurs qui sont en contact, on associe à un premier secteur celui des secteurs as sociables qui est à la distance pondérée du premier la plus faible. L'association peut s'effectuer dans le sens direct, la progression des directions de gradient suivant le sens trigonométrique; l'association peut s'effectuer encore dans le sens indirect, la progression des directions de gradient suivant alors le sens des aiguilles d'une montre. L'association, c'est-à-dire le regroupement, de l'ensemble des secteurs S1-S8 à associer de la figure 10A peut commencer par s'effectuer, à partir du secteur dans le sens direct, conduisant à la première chaîne de secteurs S1-S6 de la figure 10B, puis se poursuivre dans le sens indirect, conduisant à la seconde chaîne de secteurs S1, S7, S8 de la figure 10C, de secteur successeur en secteur successeur succn (Si). On remarquera que, le regroupement des secteurs s'effectuant autour de zones spéculaires, deux pommes, dont les images se superposent en partie, ne peuvent pas apparaitre comme une grosse pomme mais bien comme deux pommes dont une en partie cachée par l'autre. De même, un obstacle, par exemple une branche, masquant en partie une pomme, celle-ci ne peut pas apparaitre comme deux pommes de plus petite taille mais bien comme une seule pomme, toujours en raison du regroupement des secteurs autour de zones spéculaires. 6.Localisation de l'axe de préhension Cette étape vise à déterminer, pour une pomme sélectionnée, l'axe suivant lequel l'organe terminal du bras de cueillette doit se déplacer pour saisir le fruit. Deux stratégies sont possibles. La première consiste à rechercher le centre théorique (zône de spécularité); elle garantit un bon centrage de la ventouse, évitant ainsi la chute de fruits voisins. La seconde stratégie consiste à rechercher le centre de gravité de la partie visible du fruit. 7 Accessibilité Par cette étape, on vise à déterminer l'aptitude d'un fruit à être cueilli en tenant compte de sa visibilité, de sa proximité, de la présence d'un autre fruit ou d'une branche sur la trajectoire de préhension. Le taux de visibilité dépend du nombre de secteurs associés et de leur surface cumulée. La distance d'une pomme peut être calculée, de façon approchée, à partir de son rayon théorique et de son rayon apparent et de la distance focale de l'objectif de la caméra. Elle peut aussi l'être à partir de l'intensité de la lumière réfléchie par la pomme. La distance d'une pomme peut encore être calculée par stêréovision, à partir de sa position dans deux images issues de deux caméras séparées d'une distance connue, le centre théorique du fruit étant connu. Le procédé de stéréovision permet d'optimiser le temps du cycle de cueillette et d'éviter les fruits trop éloignés. En référence aux figures 11 et 12, la distance d'une pomme F, dans une zone de détection D, est calculée au moyen de deux caméras matricielles C1 et C2, au points et et O2 tels que Ol O2 = h, prenant deux images (figures 12.1 et 12.2, respectivement) à deux hauteurs différentes. Sur la première image de la caméra C1, l'objet F, dans le repère (01, #,# ) a pour coordonnées angulaires (#î' #î) Sur la seconde image de la caméra C2, l'objet F, dans le repère (0, # , #,(P ), a pour coordonnées angulaires ( & , g2) On part de l'hypothèse qu'une translation verticale de l'image ne modifie pas l'abscisse angulaire horizontale et que, donc sur la seconde image, un fruit F de coordonnées (#, Cr2) avec:: est le même que celui vu sur la première image avec pour coordonnées ( & , Y1). Ceci suppose que dans la zone de détection on ne trouve pas plus d'un fruit pour une abcisse donnée. On cherche alors P 1en fonction de /1 , g2 f 0102 et champ de vision vertical de la caméra. Dans le triangle Oî, 02, F, dont la hauteur est FH, on a Il est ensuite facile de remplacer, dans cette relation. donnant p 1 4 et ss par leurs valeurs développées cidessus. t Quant à l'accessibilité proprement dite, elle dépend essentiellement de la nature des objets cachant la pomme et qu'il faut donc identifier. Quand il ne s'agit pas de pommes, on utilise avantageusement l'analyse de forme des profils transversaux. Quand ce sont d'autres pommes qui cachent la pomme considérée, il est intéressant de déterminer le recouvrement apparent des fruits. La connaissance du centre et du rayon de la pomme à priori à cueillir est utile. Elle permet de restreindre le champ d'analyse à la surface du cercle, de la pomme, non occupée par ses secteurs précédemment associés. Pour améliorer la précision, on peut aussi analyser la concavité ou la convexité des intersections de pommes. Enfin, dans un souci d'optimisation de la cueillette, il peut être intéressant de prendre en considération des paramètres "extra vision". En effet, le débattement du bras de cueillette est limité; un arbre est analysé de deux côtés. Il est inutile de cueillir des fruits trop éloignés qui pourront l'être quand le robot de cueillette évoluera de l'autre côté de la haie d'arbres et il est important de réduire au mieux la profondeur de pénétration du bras de cueillette dans l'arbre. Une pénétration limitée réduit le temps de préhension et diminue les risques de collision pouvant provoquer la chute de fruits à cueillir. Revendications 1. Procédé de localisation d'objets sur une image de départ d'une scène les contenant et formée d'une matrice de pixels de niveaux de gris respectifs déterminés, dans lequel on détermine les pixels disposés sur au moins une monotonie pour éliminer les autres et substituer à l'image de départ une image binaire de points monotones. 2. Procédé selon la revendication 1, dans lequel on extrait les monotonies de l'image de départ par filtrage numérique local à l'aide de masques de convolution. 3. Procédé selon l'une des revendications 1 et 2, dans lequel on détermine, pour chaque pixel de l'image de départ, la direction de la variation maximale des niveaux de gris de pixels voisins et on substitue aux points monotones de l'image binaire les directions de gradient correspondants pour obtenir une image des directions de gradient des points monotones. 4. Procédé selon la revendication 3, dans lequel on répartit les pixels de l'image de directions de gradient en régions de pixels sensiblement de mêmes directions de gradient, respectivement, et connexes. 5. Procédé selon la revendication 4, dans lequel on localise les régions ou secteurs en déterminant leurs centres de gravité. 6. Procédé selon l'unesdes revendications 1 à 5, dans lequel on détermine les zones dépourvues d'objets à localiser par analyse de profils transversaux. 7. Procédé selon la revendication 6, dans lequel on procède à l'analyse de profils transversaux en exploitant la circularité de courbes iso-niveaux de gris. 8. Procédé selon la revendication 7, dans lequel les zones dépourvues d'objets à localiser sont déterminées par un vote majoritaire. 9. Procédé selon l'une des revendications 5 à 8, dans lequel on classe les secteurs de région au moins en secteurs contenant des objets à localiser et en secteurs ne contenant pas d'objets à localiser. 10. Procédé selon la revendication 9, dans lequel on regroupe les secteurs de région dont les directions de gradient respectives se coupent. 11. Procédé selon l'une des revendications 9 et 10, dans lequel on regroupe les secteurs de région dont les directions de gradient respectives varient continuement. 12. Procédé selon l'une des revendications 9 à 11, dans lequel on regroupe les secteurs de région à proximité les uns des autres. 13. Procédé selon l'une des revendications 10 à 12, dans lequel on regroupe les secteurs de région dont les directions de gradient respectives progressent dans le sens des aiguilles d'une montre. 14. Procédé selon l'une des revendications 10 à 12, dans lequel on regroupe les secteurs de région dont les directions de gradient respectives progressent dans le sens inverse des aiguilles d'une montre. 15. Procédé selon l'une des revendications 10 à 14, dans lequel on recherche le centre théorique des objets. 16. Procédé selon l'une des revendications 10 à 15, dans lequel on choisit les meilleurs objets en déterminant le nombre de secteurs associés et la surface cumulée. 17. Procédé selon l'une des revendications 10 à 16, dans lequel on analyse la concavité ou la convexité des intersections d'objets à localiser. 18. Procédé selon l'une des revendications 15 à 17, dans lequel on détermine par stéréovision la distance d'un objet à localiser. 19. Procédé selon l'une des revendications 10 à 18, dans lequel on identifie la nature d'objets cachant ceux à localiser.