Brevet FR3128559A1 — publié le 20230428

Le processus permet après avoir chargé une photo standard (format .jpg ou .bmp par exemple) d’une scène ou pièce quelconque, d’en analyser le plan bitmap et de déterminer les cercles, arc ou séquences d arc représentant d’objets présents sur la photo d’après un schéma structurel composé d’arcs de cercle (ou cercles) défini par l’utilisateur (le client) sous la forme : plus petit rayon possible, plus grand rayon possible, forme de l’objet (position des arcs de cercle centrés sur le cercle de même rayon). Les positions des rayons et valeur de complétion pour les 8 (ou moins) octants de chaque objet sont mis à disposition par le procédé aussitôt l objet détecté. Processus de détection de cercles et arc-de-cercles dans l’image, le raster et la matrice mathématique Procédé (logiciel) de détection de cercles et arc de cercles dans l’image, par méthode différentielle (points trouvés/ points attendus) appliquée aux octants (arcs de cercles) différenciés, instancié par un code informatique. Traitement de l’information, analyse très rapide (quasi temps réel) de l’image par procédé mathématique, détection de cercles, arcs de cercles (arc franc de pi/4) et séquences de suites d’arc de cercles. Différenciation de formes circulaires apparemment identiques. Etat de la technique Dans bien des processus de fabrication, l’homme reste juge de la conformité d’une pièce ou de ces bonnes dimensions. Avec le processus décrit l’humain est remplacé et laisse la place à un système plus précis, plus économique et surtout plus rapide. Pour la détection d’objets synthétisés par des séries d’arc de cercle les systèmes de détection numérisés sont lents et à base de formes établies comparées (reconnaissance de forme) ou a base d’algorithme de Hough qui manipule des complexes et qui est trop délicat pour la détection d arcs de cercle. Avantages techniques Ce système, qui parallélise (binarisation, renforcement par filtre kernel et comptage octant) le code (threads compatibles Unix et Windows) est plus rapide que bien des systèmes industriels en une passe et de plus il est très précis. Il convient aussi bien pour comparer l’état de surface de deux pièces mécaniques (comparaison d’une valeur du micromètre sur photo tirée d’un microscope) que pour calculer la trajectoire d’un arc en mouvement à haute vitesse. Présentation invention Le processus instancié dans une programme en C exécuté sous Windows ou Linux permet la détection de cercles ou parties de cercles dans une matrice mathématique acquise à partir de photo, dessin, flux vidéo, radiographique ou radar chargé sous forme de fichier image. Afin de quantifier l’objet (ou les objets) à retrouver l’usager spécifie la valeur du rayon de cercle (ou le rang de valeurs) et la forme de cet objet en donnant une suite d’arc de cercle à détecter (sous forme de valeur en ˆ2 dans le logiciel d’essai) et la photo de la scène ou objet sur lequel les recherches portent. Description technique Variables explications nPa : nombre de points attendus dans un registre nPQ : nombre de points accumulés dans un registre rPQ : rapport nPQ/ (nPa*seuilfix_0/1000) nQf : nombre d’octants de la forme recherchée nQV : nombre d’octant reconnus Phase de préparation Le traitement préliminaire pour renforcer le contraste, détecter les contours et binariser la matrice va utiliser un filtre kernel Prewitt et Sobel (qui pourra faire partie du processus). Calcul des poids (octant et objet synthétique) L’algorithme va pour chaque rayon choisi (ou pour le rayon choisi) calculer le nombre de points potentiels dans chaque registre (un par octant) et ce pour chaque octant de la suite d octants sélectionnés comme représentatifs de l’objet à détecter. (nPa : nombre de points dans l’octant pour le rayon considéré). Il calcul aussi le nombre d’octants concernés (à valider) pour synthétiser l’objet à détecter (à partir de la valeur donnée par l’utilisateur en ^2).(nQf : nombre d’octants (d’accumulateurs) par objet). Parcours du bitmap Le processus va parcourir le raster (0 et 1). A chaque 1 il considère ce point comme sommet d’un potentiel cercle. L’algorithme de parcours du cercle va placer le pointeur sur les positions attendues du passage du cercle. Options pour ce point : Raster[0].point[,]= 1 ,il appartient à l’octant : le registre de l’accumulateur considéré (celui de l octant en cours) est incrémenté. (nPQ : registre de l’accumulateur lié à l’octant considéré). (nPQ = nPQ +1) ’ Raster [0].Octant [oct]dans ’algorithme’ Raster [0].point [,]= 0, il n appartient pas al objet: rien On teste tous les points de la matrice. Validation de l’octant avec son registre On compare la valeur de chaque accumulateur à la valeur attendue pour un objet détecté. Si ce ratio est au dessus du seuil (seuilfix_0 : seuil par default), l’octant est considéré comme valide (appartenant à un objet) et on incrémente le nombre d’octants reconnus pour l’objet. (nQV : nombre d’octants valide pour quantifier l’objet). avec l’option seuilfix_0 à 1: (si : nPQ = nPa : alors : nQV = nQV + 1) avec l’option seuilfix_0 réglée par l’usager : (si : nPQ>= nPa * (seuilfix_0/1000) : alors : nQV = nQV + 1) (1 ) Validation de l’objet avec ses accumulateurs (octants) La phase finale valide l’objet si le nombre d’accumulateurs validés (égal à nQV) est supérieur ou égal au nombre d’octants sélectionnés pour représenter la forme. avec l’option seuilfix_1 fixe à 0 : (si : nQV = nQf -> objet est reconnu !) (nQf vaut 8 pour un cercle ; il vaut 2 pour une recherche sur les deux octants encadrant le point haut du cercle… par exemple). avec l’option seuilfix_1 réglée par l’usager : (si : nQV>= (nQf-seuilfix_1) objet est reconnu !) (0 ) Paramétrage processus Pour une recherche constante ou par l’intermédiaire de choix utilisateurs ces valeurs doivent être définies Rmini : rayon minimum,2 pixels Rmaxi : rayon maximum,755 pixels et 1500 pixels en mode repro’ Octal : forme de l’objet en ^2, de 1 a 255 toujours en somme de ^2 et celle-ci peuvent être modifiées seuilfix_0 : ratio de points attendus dans octant, la valeur acceptée est comprise entre 1 et 999.Ex 850 correspond à un calcul de n*850/1000 c'est-à-dire 85% du nombre de points valideront l’octant seuilfix_1 : nombre d’octants en moins à considérer, la valeur acceptée est 0 à 7. Ex 3 correspond à un calcul validé quand le nombre d’octant reconnus est inferieur de 3 au nombre d’octants demandés par le pattern. Exemple :(cf. ) (d applications exploitant les valeurs transmises détaillées : exploitation de la variation de position de l’objet sur l axe du temps, sa vitesse, quand la demande est répétée dans une boucle). Exemple :(cf. ) r1,r2 : roues détectées cercle complet. Sur une photo de voiture de cote on peut détecter les roues. Exemple :(cf. ) i1, i2:impacts détectés cercles complets petit rayon ou présence impact par calcul différentiel entre les octants o1, on d’une part et o2, om d’autre part. Sur une cible de tir impactée, sa photo traitée par le processus permet de donner la position des impacts (par détection de position directe, position des petits trous) ou par la complétion des cercles porteurs des impacts (octant impliqué dans l’impact). Algorithme de l’instance en Pseudo code Algorithme et objets théoriques du processus recherche de cercle (ou objets composes de parties de cercle) dans le raster (plan photo ou bitmap). Christophe gousset mai 2009, oct 2021 Le test tient compte du pattern mais pas du différentiel de rayons de plus il porte sur un raster binarisé (0 ou 1). Le programme est fractionné en taches parallèles. Cette solution permet de montrer que l'algorithme de détection n n’est pas perturbé par le fonctionnement fractionné. Le test avec variables utilisateur (réglages) qui sont [seuilfix_0]pour la saturation de l octant et [seuilfix_1]pour le nombre de d octants ôtés dans la comparaison des octants valides. //------------------------------------------------------------------ // donnée public raster ou bitmap pour Raster[0] et partiellement [1] Declarer int haut//hauteur RASTER Declarer int larg//largeur RASTER Declarer int rayon//rayon cercle a trouver Declarer int patt//forme cercle a trouver // variable nb tread declarer int pro//nb de process paralleles // raster pour transfert des parametres du cercle trouvé // seuls hauteur & largeur sont utilises dans les objets // Raster[1] stockera rayon, Raster[2,3] valeurs sur les octants declarer RASTER Raster[1](haut,larg,null,null,Raster[null])=0 declarer RASTER Raster[2,3](haut,larg,null,null,Raster[null])=0 //hauteur RASTER (bitmap) & largeur, rayon a trouver //& forme du cercle a trouver declarer RASTER Raster[0](haut,larg,rayon,patt,Raster[1])=0 declarer int nQV=0 ,oct=0 ,n=0 declarer int nQf = Raster[0].patPoids() // declaration variable multiprocessing tant que n declarer y_cent[n] declarer x_cent[n] declarer max_y_cent[n] declarer min_y_cent[n] declarer max_x_cent[n] declarer min_x_cent[n] n+=1 fin tan que 'pro' //decoupage du travail (plan bitmap) 1 tant que n max_y_cent[n]=Raster[0].larg/pro * n min_y_cent[n]=Raster[0].larg/pro * (n-1) max_x_cent[n]=Raster[0].haut/pro * n min_x_cent[n]=Raster[0].haut/pro * (n-1) n+=1 fin tan que 'pro' n=0 tant que n //variable de bouclage des plans (n nombre de plans) y_cent[n]=min_y_cent[n] x_cent[n]=min_x_cent[n] tant que y_cent[n] tant que x_cent[n] si Raster[0].point[Raster[0].x_cent[n],Raster[0].y_cent[n]-Raster[0].rayon] = 1; //test en un point. Raster[0].empilage(x_cent[n], y_cent[n]) nQV=0 //bouclage tous les segments de la pile tant que oct si //seuilfix_0 parametrable en choix user ou constant 'app 800/1000' //nPQ dans le texte est Raster[0].Octant[oct] Raster[0].Pile[0].SEGMENTS[oct]>=(Raster[0].nPa * seuilfix_0) ** sauvegarde données de [SEGMENTS[0..7]] nQV+=1 fin si oct+=1 fin tant que fin si si //seuilfix_1 parametrable en choix user ou constant '0 pour precision maximum' nQV>=(nQf - seuilfix_1)==> le cercle existe Raster[1].valideCentre(Raster[0].x_cent[n],Raster[0].y_cent[n],Raster[0].rayon) //synoptique du transfert de données a l extérieure du noyau. ** restitution données de sauvegarde de [SEGMENTS[0..7]] ** 4 octets par raster. Point (grâce au poids du pixel 4*8octets) ** soit 64 bits (sur Raster[2 et 3] dispo pour coter les 8 octants) Raster[2,3].valideCentre(Raster[2,3].x_cent[n],Raster[2,3].y_cent[n], Pile[0].SEGMENTS[0.3 ;4 .7]) //marquage du rayon sur Raster[1] Raster[].valideCentre(Raster[0].x_cent[n],Raster[0].y_cent[n],Raster[0].rayon) fin si fin si x_cent+=1 fin tant que 'max_x_cent[n]' y_cent+=1 fin tant que 'max_y_cent[n]' fin tant que 'pro' ------------------------------------------------------- ----------- objet PILE. tableau contenant les information sur le cercle en cours de recherche ------------------------------------------------------------------- objet PILE() declarerobjet[] SEGMENTS[0, 7]//tablo des accumulateurs PILE.SEGMENTS[ind_seg] = PILE.SEGMENTS[ind_seg]+1//operateur incrementation fin objet PILE ------------------------------------------------------------------- objet RASTER representant le bitmap ou image sur laquelle on cherche les informations. ------------------------------------------------------------------- objet RASTER(int h, int l,int r,int p,objet RASTER R) int RASTER.haut= h int RASTER.larg= l int RASTER.rayon=r//rayon cercle theorique int RASTER.patt=p//patt forme objet theorique int RASTER.nPa=0//attendu dans l octant declarer int[] RASTER.point[h*l] objet RASTER.rast=R objet RASTER.PILE()//tablo des accumulateurs procedure RASTER.empilage(int x_cent, int y_cent) procedure RASTER.testExistance(objet PILE, int ind_seg, boolrealite, int x, int y ) procedure RASTER.testRASTER(objet PILE, ind_seg, x, y ) procedure RASTER.valideCentre(int h, int l,int r) procedure int RASTER.patPoids() fin objet RASTER procedure RASTER.valideCentre(int hx, int lx,int rx) RASTER.point[hx,lx]=rx fin de procedure procedure RASTER.empilage( int x_cent, int y_cent) declarer int x, y, m, z z = 0 x = 0 y = RASTER.rayon m = 5 - 4*RASTER.rayon//initialisation Tant que x testExistance( 0, x+x_cent, y+y_cent ) testExistance( 1, y+x_cent, x+y_cent ) testExistance( 2, -x+x_cent, y+y_cent ) testExistance( 3, -y+x_cent, x+y_cent ) testExistance( 4, x+x_cent, -y+y_cent ) testExistance( 5, y+x_cent, -x+y_cent ) testExistance( 6, -x+x_cent, -y+y_cent ) testExistance( 7, -y+x_cent, -x+y_cent ) z = z + 1 si m > 0 alors y = y - 1 m = m - 8*y fin si x = x + 1 m = m + 8*x + 4 fin tant que 'x RASTER.nPa = z fin de procedure procedure RASTER.testExistance(int ind_seg, int x, int y ) si ( x y (RASTER.patt>>(ind_seg-1) & 1) et RASTER.point[x,y]=1 ) //segemnt incrementé si conditions reunies RASTER.PILE.SEGMENTS[ind_seg]+= 1; fin si fin de procedure procedure RASTER.patPoids() renvoie int declarer n = 0 declarer tot = 0 tant que n tot = tot +(RASTER.patt>>(ind_seg-1) & 1 ) //ex: patt=243 patt(en ^2)=11110011 //tot=nombre de 1 dans patt ! n = n+1 fin tant que 'n renvoyer tot fin de procedure Exemple d’utilisation Postulat : une locomotive est filmée en continu par un système vidéo alors qu’elle aborde un tronçon de voie ferrée en montée. Afin d’obtenir la vitesse de la locomotive on va extraire trois photographies du flux vidéo à des moments qui seront t0 t1 et t2 espacés de 20ms. On va soumettre les photographies au processus de détection de cercles . Une photo d essai dans le cadre d’exécution va permettre de régler la valeur du rayon de la roue à détecter pour ne détecter qu’un seul rayon (vitesse prévalant). Pour chacune des photos analysées le processus va nous donner la position de la grande roue sur les photos. La taille réelle de la roue nous est connue, les moments de prise de vue aussi. En admettant que la roue sur la photo fasse 60 pixels de rayon (0,02m) et 1.2m dans la réalité nous allons multiplier toutes les références x, y rendues par le processus par 1.2/0.02 soit 60 pour retrouver de valeurs réelles. Utilisation des données du logiciel : Distance parcourue par la loco à l attaque de la montée : d_loco=(x2-x0) temps mis par la loco pour parcourir d_loco t_loco=t2-t0 l altitude gagnée est : e_loco= (y2-y1)+(y1-y0) La dérivée en x va nous donner la vitesse de la loco vh_loco=d_loco/t_loco La dérivée en y va donne la vitesse de montée vv_loco=d_loco/t_loco La tangente de opp/adj donne la pente de la voie ferrée : pente=atan(e_loco/d_loco) La dérivée seconde donne la décélération decel=((x2-x1)/(t2-t1))-((x1-x0)/(t1-t0))(cf. )   Outils divers et remarques Les figures 5 et 6 sont des photographies de test qui servent à mesurer le fonctionnement du processus instancie (logiciel). L’instance exécutée doit détecter sur la de très grands cercles ou certaines de leurs parties. Les diamètres vont de 1500 pixel a 100 pixels et des patterns différents sont testés (170, 103, 3). Remarque les deux arcs de diamètre 1501 seront recherchés sur un rayon de 750 pixels la limite de taille de rayon étant de 755 sur le processus pour des valeurs stockées (transmissibles hors fonctionnement). Les Cercles. Objet dont le centre n est pas sur l image analysée, provoqueront une nullité de l’analyse. La montre les valeurs puissance de 2 associées à leur octant respectif. Remarque les octants visibles représentent un pattern de 16+4+64+128=212 et le rayon est de 272 pixels. Le processus s’accommode de cercles de 1 pixel d’épaisseur si ils sont tracés avec l’algorithme Bresenham avec un match score de 100% en général même sans le filtre Kernel rehausseur ; cependant le fractionnement des surfaces du au mode parallélisé peu entrainer de très rares fois des petites pertes d’information dues à l’empilage des threads)au fonctionnement asynchrone du processus ( au plus 1 ), Processus de détection de cercles, arc de cercle, suite d’arc ou suite d’un de ces objets de rayon (taille) consécutifs sur une image digitale ou photo par la transformation d’un flux vidéo ou d’ une image de base en matrice ou image mathématique dont ont rehausse les contours (par opération mathématique) afin de pouvoir comparer l’appartenance des points de la matrice à analyser aux points d’un cercle théorique (ou arc de cercle) positionné à cet endroit, le nombre de cercles ou arc de cercles détectables en un cycle peut être équivalent au nombre de pixels dans l’image à analyser. Processus selon [Revendication 1] caractérisé par la façon de multiplier l’image mathématique à analyser (bitmap(0)) en 3 autres images mathématique bitmap(1,2,3) qui sont formates aux tailles du bitmap(0) et à son poids de pixel (32 bits) tous initialisés avec -1, par la division en zones de surfaces identiques (1 à 100) (bitmap(p)) de l’image mathématique à analyser (bitmap(0)), par les fonctionnalités du bitmap(0) contient l’image mathématique sur laquelle porte la recherche des cercles ou arc de cercle divisé en 1 a 100)(bitmap(p)) et par la fonctionnalité des bitmap(1,2,3) qui porteront les résultats de l’analyse (attributs des cercles ou arcs de cercle) à la fonction appelante. Processus selon [Revendication 1], [Revendication 2] caractérisé par les calculs d’augmentation de contraste effectues simultanément par plusieurs instances (1 a 100) démarrant dans le même temps sur les parties de l’image mathématique bitmap(p) donnant par intégration l’image mathématique binarisée (composée de 1 et 0) au contours rehaussés pour l’opération de test sur des octants (comptage des pixels). Processus selon [Revendication 2], [Revendication 3] caractérisé par la façon de compter les points dans chacune des parties de taille équivalente (1/8 nommé octant, le compteur de points ou pixel associé à l’octant s’appelle registre de l’octant) qui composent le périmètre du cercle théorique, afin d’établir en fin de compte le ratio nombre de pixel dans l'octant de l’image binarisée /(divisé par) nombre de pixel attendus dans l’octant du cercle imaginaire de cette taille. Plus ce rapport se rapproche de 1 plus l’octant est reconnu (seul calcul décimal), par la valeur de validation pouvant être définie par l’utilisateur, par ce test répété 8 ou moins de fois pour chaque octant permettant de définir un cercle ou une suite d'arc de cercles, dont la définition en nombre d’octant peut être caractérisée par l’utilisateur en définissant un nombre d’octant à reconnaitre minussé par rapport aux nombre d’octants constituant l’objet défini. Processus selon [Revendication 1], [Revendication 4] caractérisé par la façon de calculer les coordonnées du point appartenant au cercle potentiel. Dans le processus itératif le test consiste a détecter si le point en place d’un des points du cercle parfait est de valeur 0 ou 1 et ceci jusqu’ au bouclage de la figure. (cf. algorithme de l'instance informatique dans la fonction 'RASTER.empilage' : départ de calcul en haut du cercle. la valeur du nombre de points par octant théorique est le total des points théoriques du premier octant sur un cercle estimé parfait) Les coordonnées (x,y) d’un point sont obtenues a partir des coordonnées du point précédent. Le premier point étant un des points (à 1) de la matrice initiale (bitmap(0)). En testant une valeur (m dans algorithme) on détermine les valeurs à ajouter ou ôter aux coordonnées (x,y) du point de référence pour obtenir les coordonnées d’un point. Processus selon [Revendication 1], [Revendication 2] [Revendication 3], [Revendication 7] caractérisé par la façon dont la matrice mathématique de départ (bitmap(0)) et les matrices mathématique contenant les résultats(bitmap(1,2,3)) (Les informations validant les rayons, le nombre de points dans l’octant (donc 8 valeurs par cercle ou suite d’arc de cercle)) sont transmises aux fonctions de calcul dans le même flux. La première matrice bitmap(0) amène le support du traitement à effectuer et les 3 autres bitmap(1,2,3) rapportent les résultats du traitement à la fonction appelante. Processus selon [Revendication 1], [Revendication 2] caractérisé par la détection de cercle potentiel dont le centre est positionné sur une des zones (bitmap(p)selon R2) et dont les attributs s’il est avéré seront marqués à la position de son centre sur le bitmap(1) selon R2 portera le résultat concernant le rayon du cercle trouvé en modifiant le pixel en x,y position du centre du cercles ou arc de cercle trouves (il fait 32 bits les 24 premiers sont utilisés). Sur 8 bits on stocke une valeur jusqu'à 255. sur 24 : 255*3 =765 (valeur limitée à 755). Et sur les bitmap(2) selon R4 seront inscrit le ratio de points trouves / points attendus (*100), pour les octants 0,1,2,3 donc stockée sur 4 octets (32 bits). Sur les bitmap(3) selon R4 seront inscrit le ratio de points trouves / points attendus (*100), pour les octants 4,5,6,7 donc stockée sur 4 octets (32 bits). Processus selon [Revendication 1] caractérisé par son mode ‘Repro’ l’algorithme instancié traite l’image dans ses dimensions réelles avec une profondeur de 32 bits par pixel c’est le mode normal, en divisant par N les dimensions (par bilinéarisation de l’image) le mode repro peut traiter des arcs de rayon (taille) 755*N pixels au lieu des 755 maximum possible (cf. : [Revendication 7]).