Brevet FR3091189A1 — publié le 20200703

Description Titre de l'invention : APPARIEMENT STRUCTUREL D'IMAGES PAR HACHAGE DE DESCRIPTEURS DE SINGULARITES DU GRADIENT Domaine technique 100011 Le domaine de l'invention est celui du traitement d'images numériques d'articles avec pour but d'apparier deux images numériques d'un même article, et en particulier deux images numériques d'un même objet postal comme une lettre, un colis ou un paquet de type par exemple "Petit Paquet Import" ou "PPI", dans une machine de traitement logistique des objets postaux comme le tri postal pour préparer la distribution postal chez les destinataires des objets postaux. Technique antérieure [0002] Afin de recevoir des objets postaux en provenance de diverses sources d'approvisionnement et les distribuer vers un grand nombre de destinataires, les centres de tri sont équipés de systèmes automatisés de tri postal. [0003] L'automatisation des centres de tri postal requiert un suivi automatisé des colis afin de vérifier leur bon acheminement au sein de ces centres. [0004] Certaines méthodes de suivi reposent sur une identification des objets postaux par signature d'image ce qui évite d'utiliser un marquage comme un code barre apposé sur les objets postaux. [0005] En général, un objet postal entrant dans une machine de tri passe devant un dispositif de prise d'image numérique. L'image numérique de l'objet peut être traitée dans une unité de traitement de données pour dériver une signature d'image qui peut servir d'identifiant unique pour la distribution postale de cet objet postal. [0006] Plusieurs dispositifs de prise d'images peuvent être installés le long du parcours des objets postaux dans les machines de tri. Par ailleurs, le même objet peut passer plusieurs fois en entrée de la même machine si le tri machine est un tri multi-passes par exemple. [0007] L'unité dc traitement de données doit être agencée pour apparier deux images dif- férentes d'un même article qui ont été acquises à deux instants différents. [0008] La méthode d'appariement repose sur la base de critères de similarité graphique et l'invention concerne donc plus particulièrement un procédé pour apparier des images numériques d'un même article dans une unité de traitement de données d'une machine de traitement des articles, dans lequel chaque image numérique d'un article comprend au moins une zone d'information contenant des symboles et des caractères d'écriture, le procédé comprenant les étapes suivantes de traitement de données: 2 [0009] - transformation de chaque image numérique d'un article en une carte topographique de divergence locale du champ vectoriel de gradient de luminance, [0010] - détection, à partir de ladite carte topographique, de singularités ou extrema de di- vergence locale du champ vectoriel de gradient de luminance, ces singularités correspondant à des points d'intérêt dans ladite image numérique, [0011] - et pour point d'intérêt détecté, encodage des valeurs de la singularité correspondante localisées sur un anneau centré sur le point d'intérêt dans la carte topographique pour dériver un descripteur de singularité du champ de gradient associé audit point d'intérêt, [0012] - et comparaison desdits descripteurs de singularité de deux images numériques pour évaluer une similarité graphique entre ces deux images. [0013] Un tel procédé est décrit dans le brevet français FR3037691. Dans cc procédé connu, les descripteurs de singularité du champ de gradient sont désignés sous le terme "DoGS" pour "Descriptors of Gradient Singularities". [0014] Comme les descripteurs DoGS à la base de cc procédé, sont des descripteurs d'image « bas niveau » (codage de la force et orientation des transitions pixelliques), ils constituent un attribut d'appariement d'images particulièrement robuste et générique car peu sensible par construction à la variabilité des informations non symboliques apposées sur l'article, ici en l'occurrence pour un objet postal : reflets, ombrages, déformations de l'objet ou de sa surface, fond d'image, glissement du contenu sous enveloppe en plastique, etc. [0015] Ainsi les points d'intérêt (POT) décrits par les DoGS sont prioritairement extraits au niveau des zones d'informations symboliques à fort gradient local, régions contenant les informations textuelles et graphiques fortement robustes d'une passe d'acquisition d'image à une autre, dont la région discriminante de l'adresse postale de destinataire. [0016] Pour garantir la reproductibilité et la localisation des POT sur l'image, ils sont pré- cisément extraits au niveau des extrema de divergence du champ vectoriel de gradient local. Les PM apparaissent ainsi à l'extrémité des lettres telles que par exemple la lettre "t" ou "p", sur le point de la lettre "i" ou encore dans le rond de la lettre "o". [0017] Ce procédé connu d'appariement a prouvé ses capacités à optimiser les performances d'un procédé d'identification virtuelle d'article par signature d'images connu sous la marque "V-kITM" de la société "SOLYSTIC" (ré-identification d'objets postaux par signature d'image) qui est divulgué dans le brevet européen EP1866105B1, en réduisant notamment les rejets et erreurs sur la population problématique résiduelle des objets postaux plats présentant des régions d'intérêt (ROI) difficiles à détecter ou une variabilité physique intrinsèque (emballages plastiques, inserts papier sous couverture, glissement sous fenêtre, plis ouverts, ...). [0018] La technologie "DoGS" a également favorisé l'ouverture des champs d'application des procédés de "matching" au traitement logistique des objets encombrants, à des 3 services non mécanisés d'aide au tri casier de type Solystic connu sous la marque "CAMStm", ou à la reconnaissance d'articles postaux normalisés (formulaires, timbres, logos, etc.), cas d'applications postales qui nécessitent de s'affranchir au maximum de l'origine et des conditions de capture des images traitées et qui demandent de traiter des problèmes de variabilité inter-passe moins contraints et maîtrisés que dans le cas du tri des objets postaux plats. [0019] Le principe à la base du procédé d'appariement DoGS est fondé sur la mise en corres- pondance de points d'intérêt PM entre couples d'images puis distinction statistique entre POT de fond (communs aux images issues d'une même trame graphique) et POT discriminants (signant les individualités) au sein d'un contexte de recherche donné. [0020] Ceci induit une forte propension de ce procédé DoGS à segmenter automatiquement les caractéristiques structurelles textuelles et graphiques d'un ensemble d'articles. [0021] Cette propriété est précieuse car utile à la résolution de nombre de problématiques postales : clustérisation/partitionnement d'objets, classification spectrale de flux, filtrage adaptatif d'individus en contexte, etc. Cette double capacité de sélection structurelle et d'individualisation dans la famille structurelle est également cruciale dans l'optique d'un passage à l'échelle de la fonction d'identification avec appariement d'objets postaux sur bases d'images massives (approches de type Big Data Image), voire simplement dans les cas où le contexte maximal de "tnatching" est large et ne peut être réduit, ni par prédiction de séquence des objets recyclés (pas de contiguïté supposée entre eux) ni par identification du contenant des objets. Cette situation est quasi systématique lors de la ré-identification des petits paquets import appelés "PPI" ou plus généralement des objets encombrants (colis et paquets). [0022] Néanmoins si le temps d'extraction des POI et des DoGS d'une image peut être maîtrisé sur des processeurs graphiques pour entrer dans les contraintes d'exploitation opérationnelles ( 1, augmente la précision en augmentant la finesse du hachage, et réduit le nombre de faux positifs, c'est-à-dire l'appariement de DoGS non similaires augmentant le risque d'appariement erroné de deux images. [0094] Selon l'invention, avantageusement K peut être compris entre 16 et 64, bornes incluses, et vaut de préférence 32, comme dans le présent mode de réalisation. [0095] On comprendra aussi que augmenter la valeur de L, avec L> 1, augmente le rappel, c'est-à-dire réduit le nombre de faux négatifs en augmentant le nombre de valeurs de hachage pour un même signal DoGS, et donc la probabilité qu'au moins l'une de ces valeurs de hachage permette de trouver une similarité entre deux signaux DoGS et donc, in fine, de favoriser le bon appariement de deux images. [0096] Selon l'invention, L peut être avantageusement compris entre 4 et 8, bornes incluses, dans le présent mode de réalisation. [0097] Les familles de fonction de hachage peuvent être préparées à l'avance et être ap- 12 pliquées à tout nouvel ensemble de nouvelles images ou à toute nouvelle image courante. [0098] Calculs des valeurs de hachage [0099] Pour obtenir les valeurs de hachage numériques des signaux DoCS, on hache en 332 sur la figure 3B les vecteurs de données 192 représentatifs des signaux DoGS au moyen des matrices 202 représentant les familles de fonctions de hachage par multiplication des vecteur par les matrices. [0100] Chaque produit scalaire d'un vecteur signal DoGS par une colonne 204 d'une matrice de hachage résulte en une valeur numérique signée 212. [0101] Cette valeur numérique signée traduit l'orientation du vecteur signal DoGS par rapport à l'hyperplan défini par la fonction de hachage représentée par la colonne considérée. [0102] Ainsi, le produit d'un vecteur signal DoGS et de l'ensemble des colonnes d'une matrice de hachage résulte en un vecteur de données 210 sur la figure 2A de même nombre de composantes qu'il y a de colonnes dans la matrice vecteur signal DoGS, soit K = 32 dans ce mode de réalisation, les composantes ayant des valeurs numériques signées, positives ou négatives. [0103] Dans un deuxième temps, on obtient la clef de hachage 250 (qui est une valeur ou empreinte numérique) du signal DoGS en assignant à chaque composante dudit vecteur de données 210 l'une des deux valeurs binaires 0 et 1 selon son signe, par exemple en assignant la valeur 0 aux composantes négatives et la valeur 1 aux composantes positives, comme illustré par le vecteur de données 220 à composantes binaires de la figure 2, puis en calculant la valeur numérique exprimée sur 32 bits représentée par la séquence de ces 32 valeurs binaires, cette valeur numérique représentant la valeur numérique du signal DoGS et donc de la clef de hachage. [0104] La figure 2B donne une illustration graphique de ce processus de calcul dans le cas d'un espace bidimensionnel partagé en demi plans par chacune des droites a à f correspondant à des fonction de hachage : selon la position du point V représentant un vecteur signal DoGS, au-dessus ou au-dessous de chaque (boite, on assigne une valeur positive ou négative aux composantes de la clef de hachage, prises dans l'ordre de considération des fonction de hachage, de a à f dans l'illustration de la figure 2B. [0105] Appariement d'images numériques [0106] Au moyen des opérations décrites ci-dessus, on a associé chaque POI d'une collection d'images à une clef de hachage caractéristique de l'environnement local de ce POL [0107] Les valeurs de hachage des POI sont rangées en 242 dans des buckets d'une base de données en mémoire dans l'unité de traitement en fonction de leurs valeurs, chaque bucket accueillant une ou plusieurs valeurs ou clef numérique de hachage. 13 [0108] Une comparaison entre les différents vecteurs DoGS est ainsi automatiquement réalisée : deux signaux DoGS sont considérés comme similaires s'ils tombent dans un même bucket. [0109] Avantageusement selon l'invention, on construit en 344 sur la figure 3B L tables de hachage illustrées figure 3A, une pour chaque famille de fonctions de hachage, par association, dc chaque buckct B aux images I dont les FOI sont associés à une valeur numérique de hachage rangée dans le buckct considéré à la suite du hachage produit par la famille respective. [0110] La figure 3A illustre un exemple de table de hachage qui comprend des buckcts B numérotés de 1 à 858, chacun associé à des images T numérotées de 1 à 567 ayant des valeurs de hachage rangées dans ces buckcts. [0111] On apparie en 346 une image cible à une image de référence sur la base du nombre de leurs signaux DoGS considérés comme similaires, cc qui revient au nombre de POT dont les empreintes numériques sont rangées dans de même buckets, c'est-à-dire sur la base du nombre de FOI dont l'environnement local aura été évalué comme similaire entre les deux images par le calcul d'approximation de similarité Fast-DoGS. [0112] Plus le nombre de valeurs de hachage de l'image cible rangées dans de mêmes buckcts que des valeurs de hachage d'une image dc référence sera élevé, plus ces deux images seront considérées comme similaires et pourront être appariées si le niveau dc similarité est jugé suffisant par le praticien mettant en oeuvre le procédé d'appariement. [0113] Dans le cas où le spectre des objets postaux traités est homogène (forte ressemblance graphique et textuelle des images) il est bien entendu possible de faire entrer en compte d'autres critères que le simple nombre de FOI de mêmes valeurs de hachage entre les deux images. [0114] On peut par exemple établir, pour une collection d'images de référence, une liste de POT discriminants dont les valeurs de hachage respectives ne correspondent à celle d'aucun autre FOI d'une image candidate ou à celle d'au plus N POT d'images candidates, N valant par exemple 1, et tester la similarité d'une image cible avec les images de référence en se limitant à une comparaison avec les valeurs de hachage des POT discriminants plutôt qu'en comparant avec l'ensemble total des POT. [0115] Dans l'esprit du procédé DoGS on peut alors individualiser une image corres- pondante dans un ensemble d'images candidates graphiquement similaires en omettant le fond d'image commun et en ne s'intéressant qu'aux FOI constituant les zones potentiellement discriminantes. [0116] Quel que soit le degré de sophistication de l'algorithme d'appariement utilisé pour exploiter les tables de hachage, l'appariement reposant sur le procédé Fast-DoGS ne met en oeuvre que des comparaisons entre des valeurs numériques chacune représentative d'un point de l'image défini comme point d'intérêt POT au cours du procédé, 14 calculs compatibles avec des contraintes d'exploitation en temps réel. [0117] Cet appariement rend donc possible le suivi et le tri en temps réel d'un grand nombre d'objets distincts sans nécessiter d'apposer sur ceux-ci un identificateur comme un code à barres. [0118] Le procédé d'appariement Fast-DoGS selon l'invention trouve un grand nombre d'applications. [0119] A titre d'exemple illustré sur la figure 1A, des paquets PPI 110 à trier sont placés sur un convoyeur de tri 120 d'une machine de tri 160 d'un centre logistique puis sont photographiés au moyen d'appareils Cl de prises de vue numérique de manière à obtenir des premières images numériques des paquets à trier en partie amont du convoyeur de tri, de préférence un seul paquet par image numérique. [0120] Ces paquets à trier peuvent arriver par exemple à un centre de tri postal en vue de leur redistribution vers des adresses de destination. Ils comportent donc des informations de distributions telles des adresses comprenant des caractères de texte. [0121] A ces premières images numériques, qui serviront d'images de référence, l'unité 150 de traitement de données qui peut être considérée globalement comme l'unité de contrôle/commande de la machine de tri 160 va associer des descripteurs locaux puis des valeurs de hachage numériques rangées dans des tables de hachage selon le procédé décrit ci-dessus. Les informations d'adresse sont reconnues automatiquement par l'unité 150 à partir des images et les adresses reconnues constituant des données de tri peuvent être également stockées en mémoire 140 en association avec les images de référence. [0122] Dans un deuxième temps, en aval des appareils Cl, les paquets sont orientés dans des sorties de tri indiquées par la flèche FI, où ils peuvent encore faire l'objet d'une seconde prise d'image au moyen d'appareils C2 de prise de vue numérique. [0123] Donc pour chaque paquet en entrée du convoyeur 120, on acquiert et on enregistre en mémoire de l'unité 150 une seconde image numérique de c paquet qui constitue l'image cible que l'on souhaite apparier à l'une des images de référence, afin de procéder à un suivi de contrôle de ce paquet tout le long de la chaîne de traitement logistique du paquet pour diriger ce paquet vers une sortie de tri. [0124] Comme pour les premières images numériques, l'unité 150 de traitement de données associe à la seconde image numérique des descripteurs locaux 190 puis des valeurs de hachage numériques 250 rangées dans des tables de hachage 350 selon le procédé FastDoGS. [0125] En variante, le paquet en sortie de tri peut également revenir en entrée du convoyeur de tri 20 suivant la flèche F2 de sorte qu'une seconde image du paquet est également acquise par le moyen de prise de vue CI. [0126] Aux fins de traitement des paquets, les premières images numériques, la seconde image numériques de chaque paquet et les descripteurs locaux et valeur ou clef numérique de hachage associés sont stockés en mémoire 140 de l'unité de traitement de données 150. [0127] L'unité 150 apparie comme expliqué plus haut la seconde image de chaque paquet à celle des premières images ayant le plus de valeurs de hachage rangées dans les mêmes buckcts que ceux dans lesquels les valeurs de hachage de la seconde image sont rangées pour récupérer par exemple les informations d'adresse postale du paquet de sorte à assurer son traitement logistique dans la machine de tri 160. [0128] On pourra comprendre qu'il est également possible que l'issue du processus aboutisse à apparier la seconde image à plusieurs des premières images de référence et dans ce cas affiner la décision par un appariement DoGS classique ou autre, ou encore avoir recours à un vidéo-codage par un Opérateur humain par exemple en affichant sur un écran de l'Opérateur de vidéo-codage ces premières images de référence et l'image cible afin de laisser à cet Opérateur humain le contrôle de la dernière phase de l'appariement. [0129] Le procédé Fast-DoGS selon l'invention est adapté à l'appariement structurel d'images d'objets postaux tels que lettres, objets postaux plats, colis, paquets y compris PPI. [0130] Dans la procédé DoGS le taux de POT appariés avec ceux d'une image cible est rapporté, soit au nombre POL, total de POT de l'image cible, soit au sous-ensemble POT. de POT considérés comme étant discriminants au sein du contexte de recherche. [0131] L'ensemble POLO, est utile à la sélection dite structurelle des objets postaux qui partagent des structures graphiques et textuelles avec l'image cible (cas du fond d'image pour les magazines illustré sur la figure 4). [0132] Le sous-ensemble POLis est quant à lui utile à l'individualisation de l'image cor- respondant à celle de l'objet requête au sein de la famille structurelle. [0133] L'état de POT discriminant est donc relatif à un contexte de recherche. Un POI de l'image cible est considéré discriminant si il n'a pas été apparié (par défaut) ou si il n'a été apparié que sur au plus N candidats (N=1 classiquement). On en déduit a contrario que la mise en correspondance d'un POT sur plusieurs candidats est significative de l'appartenance de ce POT à une structure locale commune à toute la famille d'objets ou non discriminante entre plusieurs objets de cette famille. [0134] Cette différenciation entre POIdis et POL, peut être prise en compte dans le procédé Fast-DoGS par analyse de la matrice dite de collision des POT illustrée par les tableaux ci-dessous. [0135] Ainsi, suite au hachage des DoGS des P points d'intérêt POT sélectionnés de l'image cible suivant les L familles LSH considérées lors de la génération des L tables, il est possible de prendre en compte, pour chaque POT p recherché, le nombre d'images 16 candidates en collision dans un bucket et ce, avec ou sans accumulation sur les L tables de hachage suivant l'algorithme ci-dessous : [0136] -> initialisation de la matrice ML,E(p,i) avec p=[1,P] et P i=[1,N] images candidates [0137] 0 pour chaque POT p de l'image requête [0138] -> calcul des L hash [Math 4] hl P' [Math 5] 2 [Math 6] hL ch [0139] pour chaque tablel [0140] -> incrémentation [Math 71 [0141] Mc011 [p,i j =1+4,01] [0] +1 de chaque i [0142] -> calcul des L hash [Math 4] [0143] 111 ,[Math 5] [0144] h2 ,..., [Math 61 [0145] fiL [0146] pour chaque tablel [0147] incrémentation [Math 7] [0148] Mmil[ pj.1-Mcoll [p,i] +1 de chaque i c 11.1-13 [Tableauxl] N ' pe4 17 [Tablcaux2] [0149] Comme illustré ci-dessus, la somme des collisions des POI cumulées par candidat image en contexte (somme par colonne de Ma,11) fournit le signal POIL) , dont l'amplitude des échantillons traduit l'appartenance du candidat à la famille structurelle de l'image cible. [0150] Un POI est fixé à l'état discriminant s'il n'est pas apparié avec plus d'un candidat du contexte, l'appariement avec un candidat étant effectif si le nombre de collision est supérieur à L/2 pour la matrice avec accumulation sur L tables et si le nombre de collision est non nul pour la matrice sans accumulation sur les L tables. Le signal POIdis traduit quant à lui le nombre de collisions, par candidat, des POI discriminants de l'image requête. [0151] Le procédé Fast-DoGS selon l'invention peut avantageusement s'appliquer au filtrage structurel. Dans ce mode applicatif on dispose d'une image cible d'un objet postal et d'un ensemble d'individus images constituant l'espace de référence. On cherche à extraire de ce contexte de recherche le sous-ensemble minimal d'individus qui présentent une similarité structurelle maximale avec l'individu cible. [0152] Le signal POU issu de la matrice des collisions en contexte des POI de l'image cible est représentatif de l'accumulation statistique des structures de luminances communes parmi les candidats. [0153] Divers algorithmes classiques peuvent être utilisés pour trouver le seuil optimal de coupure des amplitudes du signal, avec une efficacité qui va dépendre du spectre d'objets considéré (objets plats petit ou grand format, PPI, paquets, population fortement homogène ou non). [0154] Si ce procédé de filtrage structurel d'objets postaux peut permettre (l'initier un processus d'appariement (l'individu sur bases d'images massives par présélection structurelle des candidats, il peut sur un spectre d'objets postaux fortement hétérogènes, individualiser directement l'image cible en contexte. Par exemple, on peut avoir un appariement POL, d'un objet de type carte postale sur un horizon de plusieurs 2 .:11.