Brevet FR3037691A1 — publié le 20161223

Domaine technique Le domaine de l'invention est celui de l'identification d'articles sans marquage, notamment pour le tri postal. Technique antérieure En particulier, l'invention concerne un procédé de traitement d'articles selon lequel on forme une première image numérique d'un article et on dérive de cette première image une première signature d'image qui est un identificateur globalement unique pour ledit article, et dans lequel on forme de nouveau une image numérique courante pour ledit article et on dérive de l'image courante une signature courante qui est comparée à des premières signatures d'images d'articles enregistrées en mémoire dans une unité de traitement de données pour apparier par similarité cette signature courante avec une des premières signatures. Les articles sont en particulier des articles postaux triés automatiquement dans une machine de tri comprenant un système de reconnaissance/lecture automatique d'adresse de destinataire reconnue dans l'image numérique de l'article postal comportant cette adresse de destinataire et un convoyeur de tri qui dirige l'article postal vers une sortie de tri qui correspond à l'adresse de destinataire reconnue automatiquement. On connaît déjà du brevet EP-1519796, un procédé pour identifier les articles de courrier sans marquage, par signature d'image. Selon ce procédé, on forme une image numérique d'un article de courrier passant dans la machine de tri et on extrait de cette image une signature d'image définie par 3037691 2 deux composantes, une composante dite graphique caractérisant les distributions globales et locales des niveaux de gris dans l'image et une autre composante dite textuelle qui caractérise les informations symboliques 5 présentes dans l'image et notamment les caractères composant l'adresse de destinataire reconnue automatiquement par OCR. Avec ce procédé connu d'identification d'articles de courrier, dans un processus de tri en plusieurs passes, 10 on supprime l'apposition d'identificateurs à codes barres sur les articles de courrier. Il n'y a plus lieu d'étiqueter les articles de courrier en première passe de tri ni de relire un code barres en passe ultérieure de tri. 15 Il en résulte des réductions de coûts pour réaliser un tri postal. Toutefois, la composante graphique est faiblement discriminante lorsqu'il s'agit d'identifier des articles de courrier provenant d'un même expéditeur et qui sont 20 graphiquement similaires et cette signature d'image est alors dépendante d'une bonne détection du bloc d'adresse de destinataire dans l'image et d'une bonne reconnaissance des caractères de cette adresse de destinataire. 25 Résumé de l'invention Le but de l'invention est de proposer une signature d'image encore plus discriminante pour s'adapter encore mieux à un contexte d'appariement d'images homogènes 30 d'articles de courrier provenant d'un même expéditeur. A cet effet, l'invention a pour objet un procédé de traitement d'articles selon lequel on forme une première 3037691 3 image numérique d'un article et on dérive de cette première image une première signature d'image qui est un identificateur unique pour ledit article, et dans lequel on forme de nouveau une image numérique courante pour 5 ledit article et on dérive de l'image courante une signature courante qui est comparée à des premières signatures d'images d'articles enregistrées en mémoire dans une unité de traitement de données pour apparier par similarité cette signature courante avec une des 10 premières signatures, caractérisé en ce que chaque signature est dérivée d'une image numérique selon les étapes suivantes : - extraction d'une carte numérique du champ de gradient de luminance de la dite image par régression 15 planaire locale, identification dans ladite carte numérique de points d'intérêt correspondants respectivement à des singularités topologiques du champ de gradient à forte convergence circulaire locale ou à forte divergence 20 circulaire locale, - et représentation en mémoire par des descripteurs numériques des points d'intérêt qui sont indicatifs chacun pour un certain point d'intérêt : a) d'une position spatiale du point d'intérêt dans 25 ladite image, b) d'un indice signé de singularité qui est calculé à partir d'une combinaison de différentes grandeurs physiques incluant une valeur de divergence circulaire ou de convergence circulaire moyenne du champ de gradient et 30 de l'amplitude moyenne du champ de gradient dans une fenêtre d'analyse de pixels de l'image centrée sur ledit certain point d'intérêt, et 3037691 4 c) d'une accumulation d'indices de singularité calculés à l'intérieur d'un certain voisinage local circulaire dudit certain point d'intérêt. L'idée à la base de l'invention est donc de rendre 5 indépendants les attributs d'une signature d'image des informations textuelles reconnues par OCR dans l'image en utilisant comme attributs de signature des descripteurs de points d'intérêt de la topologie du champ de gradient de luminance dans l'image. Ces attributs de signature 10 d'image restent discriminants même au sein d'un contexte d'images d'articles de courrier homogènes graphiquement. Une résolution d'image de 2 à 10 pixels/mm est bien adaptée à l'individualisation de caractères textuels du bloc d'adresse de destinataire et dans le procédé selon 15 l'invention la régression planaire locale peut se faire sur des portions d'images de 5x5 pixels. Cette régression planaire locale permet en outre de lisser dans l'image du champ de gradient les déformations de surface de l'article de courrier (par exemple les 20 froissures de l'enveloppe) au profit de l'information symbolique contenue dans l'image comme les caractères textuels (dont ceux de l'adresse de destinataire) et les graphismes contrastés. Sur cette base, l'idée selon l'invention est de 25 rechercher les points d'intérêt les plus robustes dans les singularités topologiques du champ de gradient symbolique, ici donc des points d'intérêt à forte convergence circulaire locale ou à forte divergence circulaire locale du champ de gradient. 30 Comme le niveau de luminance des éléments symboliques textuels est en général inférieur à celui du fond de l'enveloppe (caractères sombres sur fond clair), les 3037691 5 zones de divergence circulaire locale du champ de gradient apparaissent aux extrémités des éléments symboliques tels que les caractères alphanumériques du bloc d'adresse de destinataire alors que les zones de 5 convergence circulaire locale du champ de gradient apparaissent dans les régions concaves de ces éléments symboliques. Le procédé selon l'invention peut présenter les particularités suivantes : 10 - pour comparer ladite signature courante aux dites premières signatures, on peut filtrer d'abord lesdites premières signatures pour éliminer de l'espace de recherche de concordance celles qui sont définies par un nombre de descripteurs de points d'intérêt très différent 15 du nombre de descripteurs de point d'intérêt de la signature courante; à noter que ce filtrage permet d'optimiser l'appariement dans les cas où on suppose une relative identité des deux prises d'images pour un même objet (mêmes conditions d'éclairement et mêmes portions 20 de l'objet photographiées). La comparaison s'effectue par une mesure de concordance, c'est à dire une mesure de distance de similarité entre les descripteurs de points d'intérêt des deux signatures à comparer. - pour comparer ladite signature courante aux dites 25 premières signatures, on réalise une première phase de recherche de concordance en utilisant dans la signature courante une petite partie des descripteurs de point d'intérêt pour présélectionner un sous-ensemble de premières signatures compatibles à la signature courante 30 et une seconde phase de recherche de concordance sur ledit sous-ensemble de premières signatures compatibles 3037691 6 en utilisant dans la signature courante l'ensemble des descripteurs de point d'intérêt. - les premières signatures sont enregistrées en mémoire d'une machine de tri postal automatique lors 5 d'une première passe de tri des articles postaux et en ce que la comparaison de signatures est réalisée lors d'une seconde passe de tri de ces articles postaux dans cette machine ou dans une autre machine de tri automatique. Un exemple de mise en oeuvre du procédé selon 10 l'invention est décrit ci-après et illustré par les dessins. Présentation sommaire des dessins La figure 1 illustre de façon très schématique le 15 procédé d'extraction d'une signature d'image en première passe de tri d'articles de courrier. La figure 2 illustre de façon schématique le procédé d'appariement de deux signatures d'image selon l'invention en seconde passe de tri des articles de 20 courrier. La figure 3 illustre plus en détail le procédé d'extraction des attributs d'une signature d'image. La figure 4 illustre plus en détail le procédé d'appariement des attributs des signatures d'image. 25 La figure 5 illustre le principe de la régression planaire locale selon l'invention. La figure 6 illustre une machine de tri postal pour la mise en oeuvre du procédé selon l'invention. La figure 7 illustre une image numérique d'un article 30 de courrier avec un bloc d'adresse de destinataire. Description des modes de réalisation 3037691 7 Les figures 1 et 2 illustrent donc la mise en oeuvre du procédé selon l'invention dans un processus de tri d'articles de courrier en deux passes de tri dans une machine de tri postal 1 illustrée figure 6 et comprenant 5 par exemple un dépileur 2 alimentant un convoyeur de tri 3 en articles de courrier 4 disposés en pile sur chant en entrée de la machine. Un système 5 de reconnaissance automatique d'adresse de destinataire visible figure 6 est disposé en aval du 10 dépileur 2. Le système de reconnaissance comprend une caméra 6 apte à former (étape 10 sur la figure 1) une image numérique illustrée par 7 sur la figure 7 par exemple en multi niveaux de gris d'une face d'un article en série 15 sur chant dans la machine, cette image comportant l'adresse de destinataire illustrée par 8 sur la figure 7, et une unité de traitement de données 9 qui à partir de cette image est apte par l'intermédiaire d'un OCR à reconnaitre cette adresse dans l'image numérique (étape 20 11 dans la figure 1) . L'unité de traitement de données 9 est apte aussi à extraire de l'image numérique une signature d'image (étape 12 dans la figure 1), indiquée par SIG sur les figures 1 et 2, qui sert d'identifiant unique pour 25 l'article et qui est enregistrée dans une base de données, représentée par la référence 100 sur les figures 1 et 2, en relation avec l'adresse de destinataire reconnue qui constitue des données de tri indiquées par DATA pour la commande du convoyeur de tri 3. 30 Sur la base de cette adresse de destinataire reconnue, l'article est dirigé (étape 13 sur la figure 1) vers une sortie de tri S1, S2, ...SM correspondante du 3037691 8 convoyeur de tri et ainsi de suite pour tous les articles 4 chargés en entrée de la machine de tri. Sur la figure 2, un article est chargé en machine pour une seconde passe de tri. 5 La caméra 6 forme une image numérique courante de cet article (étape 20 sur la figure 2) et une signature courante d'image SIG est extraite de cette image courante (étape 21 sur la figure 2) et est comparée (étape 22 sur la figure 2) à des premières signatures d'articles 10 enregistrées dans la base de données 100 pour détecter une similarité et récupérer sur la base de cette détection les données de tri DATA pour cet article afin de le diriger (étape 23 sur la figure 2) vers une sortie de tri correspondante du convoyeur de tri. 15 Sur la figure 3, on a illustré de façon très schématique le processus d'extraction d'une signature d'image selon l'invention qui est réalisé dans les étapes 12 et 21 des figures 1 et 2 respectivement. Dans ce processus, dans une première étape de 20 traitement en 30, on applique une régression planaire locale sur l'image numérique de l'article avec une matrice locale de par exemple de 5x5 pixels avec ou sans chevauchement, pour obtenir une carte numérique du champ de gradient de luminance. 25 La figure 5 illustre dans une image numérique I, la matrice locale de calcul 5x5 pixels du champ de gradient sous la référence M. Cette matrice M est centrée sur le pixel I(i,j) de l'image numérique de l'article. A noter, que cette fenêtre d'analyse de 5x5 pixels 30 est bien adaptée pour des images d'articles de courrier à une résolution comprise entre 2 et 10 pixels/mm car elle permet d'intégrer les déformations de surface de 3037691 9 l'article qui apparaissent dans l'image telles que des froissures de l'enveloppe plastique, reflets et ombrages, etc... et de rehausser les zones d'information symbolique dans l'image comme les caractères textuels imprimés. 5 Ensuite dans l'étape 31, on recherche dans la carte du champ de gradient résultant de l'étape 30, des points d'intérêt qui correspondent à des singularités topologiques du champ de gradient à forte convergence circulaire locale ou a forte divergence circulaire 10 locale. En particulier, dans l'étape 31, les points d'intérêt sont les singularités de plus forte amplitude du champ vectoriel (positive ou négative) et qui correspondent à un extrema de convergence circulaire locale ou de 15 divergence circulaire locale du champ de gradient. Selon l'invention, les points d'intérêt retenus en sortie de l'étape 31 sont ceux qui présentent un indice signé de singularité (résultante d'une combinaison de la valeur de divergence ou de convergence circulaire moyenne 20 du champ de gradient et de l'amplitude moyenne du champ de gradient dans la fenêtre d'analyse de 5x5 pixels) supérieur à un seuil réglable. Ce seuil permet de s'affranchir notamment de points d'intérêt parasites qui ont été détectés dans le fond de l'image. 25 Ensuite dans l'étape 32, on forme dans l'unité 9 un descripteur numérique pour chaque point d'intérêt du champ de gradient symbolique extrait à l'étape 31 qui contient des données représentatives de la position spatiale du point d'intérêt dans l'image numérique de 30 l'article, de sa valeur de singularité signée et de la configuration de son voisinage local circulaire. 3037691 10 La configuration de voisinage local circulaire selon l'invention pour un point d'intérêt consiste à mesurer l'accumulation des valeurs signées de singularité sur les anneaux d'un disque de voisinage centré sur le point 5 d'intérêt décrit. Ce descripteur ci-après dit descripteur "DoGS" ou "Descriptors of Gradient Singularities" est un signal dont la dimension fixe représente le rayon de description spatiale du point singulier, par exemple 30 pixels ce qui 10 correspond à un rayon de description de 15mm. A l'issue de l'étape 32, l'image numérique I d'un article est identifiée de façon unique par une signature numérique sous la forme d'un ensemble de descripteurs "DoGS" de points d'intérêt dont chacun code la position 15 spatiale d'un point d'intérêt, sa valeur de singularité signée et le signal de description des singularités dans un voisinage circulaire. Il faut comprendre qu'à l'étape 21 pour former une signature courante à partir de l'image courante d'un 20 article présenté en seconde passe de tri, on réalise les étapes 30 à 32 de la figure 3. Maintenant sur la figure 4, on a illustré plus en détail l'étape 22 du procédé selon l'invention pour apparier par similarités des descripteurs "DoGS" deux 25 signatures numériques. Sur la figure 4, à l'étape 40, suivant la complétude ou non des images d'article comparées, on peut réaliser un filtrage des signatures enregistrées à l'étape 12 sur la figure 1 de façon à réduire l'espace de recherche 30 pour l'appariement d'une des premières signatures avec la signature courante. 3037691 11 En particulier, on filtre lesdites premières signatures pour éliminer celles qui comportent un nombre de descripteurs de point d'intérêt "DoGS" très différent du nombre de descripteurs de point d'intérêt "DoGS" de la 5 signature courante. Sur la figure 4, on a illustré un espace de recherche E contenant les premières signatures SigPl à SigPn. Ensuite à l'étape 41, on recherche la concordance maximale de similarité entre les descripteurs "DoGS" de 10 points d'intérêt de la signature courante SigC et les descripteurs "DoGS" des point d'intérêt de chacune des premières signatures SigPi de l'espace de recherche. Comme illustré sur la figure 4, la recherche de concordance maximale est réalisée sur l'ensemble de 15 l'espace de recherche E. A l'issue de l'étape 41, une première signature SigPj a été trouvée comme étant concordante avec la signature courante dans l'étape 42. A partir de cette première signature, les données de 20 tri DATA peuvent être récupérées dans la base de données 100 illustré sur la figure 2. Mais l'appariement des descripteurs "DoGS" peut se réaliser sur l'ensemble de l'espace de recherche E en deux phases distinctes : 25 - une première phase de recherche de concordance dans laquelle on ne va chercher à apparier qu'un nombre restreint de descripteurs "DoGS" de signatures SigC de sorte à présélectionner un sous-ensemble de signatures appartenant à une même famille structurelle que celle de 30 la signature SigC recherchée, c'est-à-dire dont les images contiennent des structures symboliques communes; 3037691 12 - une seconde phase de recherche de concordance dans laquelle on va chercher à apparier l'ensemble complet des descripteurs "DoGS" au sein du sous-ensemble des premières signatures présélectionnées dans la phase 5 précédente. Dans la première phase, l'appariement des descripteurs "DoGS" n'est réalisé que sur une petite partie de descripteurs "DoGS". Ces descripteurs "DoGS" sont par exemple ceux qui présentent la plus forte 10 singularité absolue dans l'image par rapport à une valeur de seuil, ou encore ceux qui correspondent à une zone précise de l'image (bloc d'adresse expéditeur, etc...). Pour chaque signature candidate SiGC, un faible nombre de descripteurs "DoGS" (représentatifs d'une famille 15 structurelle d'images qui partagent par exemple une même structure graphique ou textuelle) sont comparés aux descripteurs "DoGS" correspondants de chaque signature SiGPj de l'espace de recherche E pour présélectionner un sous-ensemble de premières signatures "compatibles" sur 20 lesquelles on réalisera ensuite la seconde phase de recherche de concordance en utilisant tous les descripteurs "DoGS" de la signature courante. Le procédé selon l'invention peut s'appliquer à des objets postaux en mouvement pendant la formation des 25 images numériques ou à des objets postaux statiques pendant la formation des images numériques. Suivant le cas, entre deux prises d'image d'un même objet postal, on peut avoir des variations de luminance dues aux changements d'éclairement de la scène ou à une variation 30 de la profondeur de champ de la caméra. A noter que les variations d'éclairement de la scène peuvent modifier le nombre de points d'intérêt détectés 3037691 13 dans les images qui sont comparées, sans contrarier pour autant le processus d'appariement des descripteurs "DoGS". A l'inverse la variation de profondeur du champ de la 5 caméra peut provoquer des variations de résolution dans les images ce qui peut contrarier la mise en concordance des descripteurs "DoGS". Pour s'affranchir de cette variabilité, et sans sortir du cadre du procédé selon l'invention, on peut effectuer de manière conditionnelle 10 dans le processus de recherche de concordance, une mise à l'échelle automatique des signatures d'images par dilatation ou contraction des descripteurs "DoGS" comparés. Le procédé selon l'invention est tolérant aux 15 déplacements relatifs de l'objet postal entre ces deux prises d'image, par exemple en rotation ou en translation, ou les deux à la fois. Cette variabilité provoque un changement de position des points d'intérêt entre deux passes d'acquisition d'une image d'un même 20 article, ce qui peut compliquer la mise en correspondance de ces points d'intérêt. Une méthode pour s'affranchir de cette variabilité sans sortir du cadre de l'invention peut consister à effectuer au moment de la présélection d'une première signature une approximation de la 25 transformation rigide globale. Cette approximation peut être calculée par minimisation au sens des moindres carrés de la distance entre les quelques descripteurs "DoGS" mis en correspondance lors de la première phase de mise en concordance. Les paramètres de la transformation 30 approximée peuvent aussi être utilisés lors de la seconde phase de mis en concordance pour projeter les coordonnées spatiales de chaque point d'intérêt de la signature SigC 3037691 14 recherchée dans l'espace de l'image numérique associée à la signature SigPi comparée. Par ailleurs, on comprend que les descripteurs "DoGS" permettent d'individualiser des images numériques 5 d'objets postaux fortement similaires graphiquement par des singularités qui sont indépendantes de la reconnaissance symbolique du bloc d'adresse de destinataire dans ces images. Bien entendu, le procédé selon l'invention peut 10 s'appliquer à différents traitements d'articles, comme le tri de colis/valises ou analogues transportés sur tapis. Il est apte à fonctionner sur différents systèmes d'acquisition d'images. REVENDICATIONS1/ Procédé de traitement d'articles selon lequel on forme (10) une première image numérique d'un article et on dérive (12) de cette première image une première signature d'image (SigPi) qui est un identificateur unique pour ledit article, et dans lequel on forme (20) de nouveau une image numérique courante pour ledit article et on dérive (21) de l'image courante une signature courante (SigC) qui est comparée (42) à des premières signatures d'images d'articles enregistrées en mémoire dans une unité de traitement de données pour apparier par similarité cette signature courante avec une des premières signatures, caractérisé en ce que chaque signature est dérivée d'une image numérique selon les étapes suivantes : - extraction (30) d'une carte numérique du champ de gradient de luminance de la dite image par régression 20 planaire locale, - identification (31) dans ladite carte numérique de points d'intérêt correspondants à des singularités topologiques du champ de gradient à forte convergence circulaire locale ou à forte divergence circulaire 25 locale, - et représentation en mémoire par des descripteurs numériques (DoGS) des points d'intérêt qui sont indicatifs chacun pour un certain point d'intérêt : a) d'une position spatiale du point d'intérêt dans 30 ladite image, b) d'un indice signé de singularité qui est calculé à partir d'une combinaison de différentes grandeurs 3037691 16 physiques incluant une valeur de divergence circulaire ou de convergence circulaire moyenne du champ de gradient et de l'amplitude moyenne du champ de gradient dans une fenêtre d'analyse de pixels de l'image centrée sur ledit 5 certain point d'intérêt, et d) d'une accumulation d'indices de singularité calculés à l'intérieur d'un certain voisinage local circulaire dudit certain point d'intérêt. 10 2/ Procédé selon la revendication 1, caractérisé en ce que pour comparer ladite signature courante aux dites premières signatures, on filtre (40) d'abord lesdites premières signatures pour éliminer de l'espace de recherche de concordance celles qui sont définies par un 15 nombre de descripteurs de point d'intérêt très différent du nombre de descripteurs de point d'intérêt de la signature courante. 3/ Procédé selon la revendication 1, caractérisé en ce que pour comparer ladite signature courante aux dites premières signatures, on réalise une première phase de recherche de concordance en utilisant dans la signature courante une petite partie des descripteurs de point d'intérêt pour présélectionner un sous-ensemble de premières signatures compatibles à la signature courante et une seconde phase de recherche de concordance sur ledit sous-ensemble de premières signatures compatibles en utilisant dans la signature courante l'ensemble des descripteurs de point d'intérêt. 3037691 17 4/ Procédé selon l'une des revendications précédentes, caractérisé en ce que les premières signatures sont enregistrées en mémoire d'une machine de tri postal automatique lors d'une première passe de tri 5 des articles postaux et en ce que la comparaison de signatures est réalisée lors d'une seconde passe de tri de ces articles postaux dans cette machine ou dans une autre machine de tri automatique.