Brevet FR2290712A1 — publié le 19760604

La présente invention concerne un procédé pour identifier des formes de dessins, et notamment d'empreintes digitales, par comparaison avec un dessin de référence. On a essayé, dans le passé, d'appliquer à la reconnaissance d'empreintes digitales des procédés similaires à ceux utilisés pour l'identification de caractères alphanumériques. Ces tentatives se sont heurtées à d'importantes difficultés, du fait que des formes complexes telles que des empreintes digitales mettent en jeu une quantité de données considérablement plus élevée que celle mise en jeu dans le cas de caractères, même si leur type est quelconque. La présente invention a pour but de réaliser un procédé permettant une telle reconnaissance d'une façon commode, sans donner lieu aux difficultés précitées. On connaît, d'une manière générale, un certain nombre de procédés et d'appareils permettant d'engendrer des données binaires représentant une empreinte digitale. On peut utiliser par exemple un analyseur à spot mobile et des photodétecteurs pour engendrer des mots binaires correspondant à 1'analyse, ligne par ligne, de certaines parties du dessin de l'empreinte. Toutes les empreintes digitales comportent des crêtes et des vallées de différentes longueurs, et des interconnexions entre ces éléments. Les caractéristiques de ces empreintes sont constituées par les extrémités de crêtes, considérées soit séparément soit en combinaison, qui correspondent par exemple à des liaisons entre deux crêtes, ou à un éperon relativement court se séparant d'une crête plus longue. I1 existe dans l'art antérieur des procédés d'analyse d'empreintes digitales permettant d'engendrer des données binaires et d'identifier les extrémités et les bifurcations de crêtes, ainsi que leurs emplacements, et cet aspect de la reconnaissance d'empreintes digitales ne fait donc pas partie de l'invention.Celle-ci porte sur le traitement des données brutes identifiant ces caractéristiques, ces données pouvant par ailleurs être obtenues par n'importe quel procédé approprié. Des formes complexes autres que des empreintes digitales peuvent également être converties sous formes de données brutes identifiant les éléments caractéristiques de ces formes ainsi que leurs emplacements, ce qui permet d'appliquer l'invention à l'identification de molécules complexes et/ou à la recherche de corrélations entre des photographies et des cartes, par exemple. L'un des aspects de l'invention concerne le classement de données relatives aux éléments caractéristiques d'un dessin à identifier. Selon un mode particulier de mise en oeuvre de l'invention, on peut utiliser un calculateur pour établir automatiquement une liste d'éléments caractéristiques à partir des données identifiant chaque élément caractéristique d'un dessin, chaque élément caractéristique porté sur cette liste étant associé à des données identifiant un nombre prédéterminé d'éléments caractéristiques portés sur cette liste et qui sont situés sur le dessin en des emplacements voisins de l'élément caractéristique considéré, compte-tenu d'une direction d'analyse de ce dessin.De plus, il est préférable de porter également sur la liste la distance de chaque élément caractéristique voisin, accompagnée d'un index d'identification de cet élément voisin, dans la liste d'éléments caractéristiques. Dans le cas d'une empreinte digitale, les éléments caractéristiques sont constitués par les extrémités et les bifurcations de crêtes. La distance entre des éléments caractéristiques voisins peut être exprimée par le nombre de crêtes qui les séparent, de façon à réduire l'effet des distorsions provenant par exemple de la différence de pression des doigts au moment de la prise de l'empreinte. Les informations relatives à chaque élément caractéristique comportent de préférence le type d'élément, c'est-à-dire crête ou bifurcation, la direction générale des crêtes à l'emplacement de l'élément considéré, et les coordonnées de cet emplacement, sous forme cartésienne (X,Y), par exemple. Chaque extrémité de crête correspond à une bifurcation de vallées, et chaque bifurcation de crêtes correspond à une fin de vallée, et il est donc possible d'identifier les extrémités et les bifurcations de vallées, ou même les extrémités de vallées et les extrémités de crêtes, pour obtenir des éléments caractéristiques de la même nature, mais relatifs soit au dessin "en blanc" soit au dessin "en noir", dans le cas par exemple d'un cliché photographique ou d'une diapositive, le même élément étant représenté par des valeurs binaires opposes selon qu'on considère l'un ou l'autre de ces deux dessins. les éléments caractéristiques qui sont considérés comme voisins ne sont pas les plus rapprochés en distance absolue mais ceux qui satisfont à un critère de proximité donné . Il est commode de définir ce critère en considérant une direction parti calibre sur un dessin orienté de façon prédéterminée, cette direction étant par exemple la droite dans un repère cartésien. Si les éléments caractéristiques sont enregistrés Bous forme d 'une liste ordonnée établie en considérant cette direction particuliè- re, tous les éléments caractéristiques voisins entrant dans le non bre prédét.rminé d' éléments voisins mentionné précédemment appa paîtront sur la liste après l'élément caractéristique particulier duquel ils sont considérés voisins.On peut alors utiliser des in dex d'identification ne comportant pas de signe, On a obtenu des résultats satisfaisants en utilisant 5 éléments caractéristiques voisins. Ce classement sous forme de liste des éléments caractéristiques et des données convient particulièrement bien à la comparaison entre un dessin à identifier et un dessin de référence ce. Cette comparaison entre deux listes de données relatives res- pectivement à un dessin à identifier et à un dessin de référence, constitue un second aspect de l'invention. Selon l'invention, la compaaaison de deux dessins est réalisé soit manuellement soit automatiquement à 1' aide d 'un calculateur, à partir de listes d'éléments caractéristiques relatives à chaque dessin.Pour chaque élément caractéristique, ces listes comportent des données identifiant l'élément caractéristique considéré par rapport au dessin auquel il appartient, et par rapport à un nombre prédéterminé d'autres éléments caractéristiques voisins du meme dessin. le procédé de comparaison comporte les étapes suivantes : on établit de nouvelles listes de paires d'é léments caractéristiques, appartenant chacun à l'un des dessins, qui colncident en ce qui concerne leurs relations -avec leur dessin respectif ; on mesure le degré de précision de ces coinci- dences à l'aide de nombres déterminés en tenant compte du degré de coincidence qui existe, paire par paire, entre les éléments caractéristiques voisins en nombre prédéterminé , on fait la soi- me de ces nombres en tenant compte des relations mutuelles qui sont établies entre les paires en coïncidence par l'intermédiaire des paires d'éléments caractéristiques voisins en coincidence; et on utilise les sommes les plus élevées pour établir une mesure du degré de coincidence global existant entre les deux dessins. lorsque les données dtidentification relatives à un dessin comportent des informations de coordonnées et des informa- tions de direction, on tient compte de préférence d'une marge d' erreur prédéterminée sur chacune de ces informations, lorsqu'on décide s'il y a ou non coincidence. De façon similaire, on tient compte d'une marge d'erreur pour l'écartement entre éléments caractéristiques voisins, exprimé en nombre de crêtes dans le cas d'une empreinte digitale, et pour les données d'identification de position quand on décide 81 il y a ou non coincidence entre deux éléments caractéristiques voisins de deux éléments caractéristiques reconnus en coincidence. Par commodité, on appellera ici "coincidence principale n une coïncidence entre deux éléments caractéristiques, et on appellera " coïncidence secondaire n une coin cidence entre deux éléments caractéristiques figurant comme voi sins d'éléments caractéristiques reconnus en coincidence. Bien entendu, deux éléments caractéristiques donnés peuvent apparattre à la fois dans une coincidence principale et dans une ou plusieurs co3ncidences secondaires.Bn fait, la mesure dans laquelle ceci se produit est déterminée au cours de l'évaluation de la ressemblance entre deux dessins traités et le processus cumulatif qui est réalisé vise à la fois à évaluer 1' importance de ces coincidences interdépendantes, et à attribuer un poids correct at nombre de coincidences secondaires rencontrées pour chaque coïncidence principale. On réalise de préférence un processus cumulatif en chaîne dans lequel le score de toutes les coïncidences principales possibles est augmenté par les scores de leurs coïncidences secondaires, et réciproquement. I1 est également avantageux de réaliser une sommation en chaîne dans laquelle les scores des coincidences principales sont additionnés aux scores de leurs coïncidences secondaires, et dans laquelle les scores augmentés sont additionnés à leurs propres scores secondaires relatifs à des coïncidences principales des mimes éléments caractéristiques. Cette sommation en chaine peut avantageusement être accomplie de la manière inverse, les scores de coïncidences principales étant utilisés pour augmenter d'autres scores de coïncidences principales pour lesquelles ils apparaissent sous forme dé scores de coïncidences secondairés. On fixe des seuils de façon appropriée, pour les listes finales et/ou les listes intermédiaires. I1 est préférable de vérifier ensuite la liste finale pour éliminer tous les éléments Ca- ractéristiques qui ne sont pas reliés d un autre élément caractéristique de la liste, de manière à ce que chaque coïncidence principale apparaisse également sous forme d'une coïncidence secondaire st/ou possède l'une de ses coïncidences secondaires enregistrée é galement sous forme de coïncidence principale . On effectue ensuite une sommation finale et un copte total des liens, de façon à obtenir un score caractérisant la corrélation globale qui existe entre les deux dessins comparés. On décrira maintenant à titre d'exemple un mode de mi- se en oeuvre de l'invention, en se référant aux dessins annexés sur lesquels : La figure I représente des exemples d'éléments caractéristiques d'empreintes digitales considérés codage significatifs pour les comparaisons effectuées par des experts ; La figure 2 représente les positions relatives de 23 éléments caractéristiques d'une empreinte digitale, ces éléments étant numérotés de la gauche vers la droite;; La figure 3 est un diagramme montrant comment on choisit les 5 éléments caractéristiques les plus voisins d'un élément caractéristique particulier La figure 4 est un tableau servant à 11 explication d'un procédé de sélection initiale des éléments caractéristiques voisins La figure 5 représente le format des mots binaires constituant l'information portée dans la liste d'éléments caractéristiques,pour un élément caractéristique particulier La figure 6 reprsente.le format d'articles successifs iigurant dans une liste de coïncidences ; et La figure 1 représente fln. modification de la liste de ótncssdences, et sa relation avec une liste de scores cumulés. Les schémas Â et B de la figure 1 représentent respectivement des extrémités de crêtes et des bifurcations de crêtes. Le schéma ' représente des éperons constitués chacun par une bifurcation à partir d'une crête relativement longue, et par une extrémité de crête relativement rapprochée de la bifurcation. Le sché- ma D représente des liaisons constituées par des crêtes courtes s' étendant entre deux crêtes plus longues, chaque liaison pouvant d- tre considérée comme étant formée par deux bifurcations de crêtes adJacentes. Le schéma E représente une inclusion qui peut entre considérée comme une autre combinaison de deux bifurcations de crêtes ne portant cette fois-oi que sur une seule crête, Les schémas F et G. représentent respectivement un pilet et une cette courte, ces figures étant constituées toutes deux par des combinaisons d'extré- mités de crêtes. 'est en se basant sur ces éléments caractéristiques que les experts identifient visuellement les empreintes digitales. Il est évident que tous ces éléments. caractéristiques peuvent être ramenés à des extrémités et des btiurcations de crêtes, et ce sont ces éléments caractéristiques de base qu'utilisent les procédés automatiques de codage et de reconnaissance d'empreintes digitales.. Si la comparaison visuelle d'empreintes digitales nécessite beaucoup d'expérience-et d'habileté, il est au contraire relativement facile d'orienter une empreinte digitale, ou même une partie d'empreinte, d'une manière prédéterminée. Comme il a été indiqué précédemment, l'analyse d'une empreinte digitale et l'extraction des informations d'identifioa- tion d'éléments caractéristiques (estrémités et bifurcations de crêtes ) et des informations traduisant les coordonnées cartésien nes des emplacements de ces éléments caractéristiques ne font pas partie de l'invention. On peut utiliser dans ce but tous procédés et appareils appropriés. le Brevet Britannique N0 1.117.131 dé crit un dispositif d'analyse à spot mobile rotatif et indique les critères de reconnaissance d'éléments caractéristiques qui peuvent Outre appliqués aux résultats de l'analyse. Le Brevet Bri tannique NO 1.082.885 décrit un dispositif différent d'analyse et d'extraction d'éléments caractéristiques qui utilise un tambour rotatif portant l'empreinte digitale, associé à un balayage li néaire du tambour, par spot mobile. On peut indifféremment utili ser une diapositive représentant le dessin de l'empreinte digitale, avec analyse par spot mobile et photodétection de part et d'autre de la diapositive, ou un dessin de l'empreinte digitale formé sur une surface opaque, avec analyse par réflexion. On suppose qu'on dispose d'une source appropriée de données binaires représentant le dessin d'une empreinte digitale, les crêtes et les vallées correspondant à des valeurs binaires opposées. On suppose en outre que ces données ont été traitées pour identifier des éléments caractéristiques correspondant aux extrémités et aux embranchements de crêtes, et pour indiquer l'emplacement de ces éléments, en coordonnées cartésiennes. I1 est alors facile d'ordonner ces éléments caractéristiques par rapport à l'une des coordonnées, par exemple la coordonnée X, et le résultat de ce classement sert de base à la liste d'éléments caractéristiques mentionnée précédemment, se prêtant particulièrement bien à un traitement ultérieur pour permettre une reconnaissance de formes. A ce niveau, la liste d'éléments caractéristiques comporte, pour chaque élément, une indication du type d'élément, les coordonnées X et Y et, de préférence, une indication approximative de la direction angulaire des crêtes au niveau de l'élément considéré. Dans le cas particulier ot l'on utilise un calculateur, cette direction angulaire peut être facilement obtenue, en procé- dant par exemple à un décalage de mots de données s'étendant dans la direction X, et espacés de manière prédéterminée ou adjacents (dans la direction Y) de façon à obtenir une coincidence des éléments binaires indiquant des crêtes, et en faisant la moyenne pour tenir compte des mots situés de part et d'autre des emplacements véritables.Dans le cas où l'on utilise un calculateur ayant un mot d'une longueur de 24 éléments binaires (e.b.), on utilise un e.b. pour l'identification. du type d'élément, T, et il suffit de 5 e.b. pour chacune des coordonnées de position X et Y, et de 2 e.b. pour la direction de la crête, D. Ceci donne une grille de coordonnées de dimensions 32 x 32, et une indication de direction ramenée à celle des 4 directions à 450 qui est la plus voisine. I1 est possible d'utiliser d'autres affectations des positions binaires, dans le cas où l'on utilise des grilles de coordonnées ayant d'autres dimensions, et / ou une précision différente de la détermination de la direction des crêtes, et en particulier si le calculateur permet ou impose des mots de longueur différente , par exemple des mots de 32 e.b.Dans certains cas, il peut entre préférable d'affecter 5 éléments binaires pour indiquer la direction de crêtes, et de n'en affecter aucun à la détermination du type d'élément caractéristiqueí8S, en partiou- lier si les données brutes ont été soumises, avant l'extraction des éléments caractéristiques, à un "nettoyage" permettant de rem plir les vides ds probablement à des pores, et permettant la connexion des extrémités de crêtes à des bifurcations. Chacun de ces mots est suffisamment long pour contenir encoreunindex d'identification à 7 e.b. indiquant ltemplacement de l'élément carêctéristique voisin le plus proche, ainsi qu'un nombre de 4 e.b. indiquant la distance de cet élément caractéristique voisin, expriméeen nombre de crêtes intermédiaires. L'indes d'identification est utilisé en liaison avec le numéro d'identification-de l'élément caractéristique (ou adresse de l'élé- ment) dans la liste, et est simplement ajouté à ce numéro dfi- dentification pour donner le numéro de la liste qui correspond à l'élément caractéristique voisin concerné.Ceci est possible du fait que les éléments caractéristiques sont ordonnés dans la liste selon la coordonnée X, et que les éléments caractéristiques voi- sine ne sont pris en considération que s'ils possèdent une coordonnée X de valeur supérieure. On rappelle qu'on considère comme souhaitable de tenir compte de 5 éléments caractéristiques voisins, et les données relatives à ces éléments (index d'identifi- cation à 7 e.b. et nombre de crêtes à 4 e.b.) sont contenues dans deux autres mots de 24 éléments binaires, chacun de ces mots étant relatif à deux éléments caractéristiques. I1 est commode de considérer que chacun de ces mots constitue un article de la liste d'éléments caractéristiques, mais en pratique on peut utiliser 7 listes parallèles de mots de 24 e.b., les positions correspondantes de chaque liste étant affectdes au mdme élément caractéristique. On se référera maintenant aux figures 2, 3 et 4 pour décrire un moyen de ddtermination des 5 éléments caraetéristiquea les plus proches placés à droite d'un élément caractéristique donné, c'est à dire possédant des coordonnées X supérieures. La figure 2 représente plusieurs eiplacements d'éléments caractéristiques, figurés sous forme de points et numérotés de la gauche vers la droite.On peut considérer que les ases de coordonnées X et Y de la figure 2 sont situés respectivement au-dessous et à gauche des points représentés. le point portant le N 5 est encerclé pour indiquer qu'il s'agit de trouver les voisins les plus proches de cet élément caractéristique. la numérotation des éléments caractéristiques qui est représentée correspond à leur position dans la liste initiale résultant de l'analyse et de 1' extraction des éléments caractéristiques.Ce classement est repré s enté dans la colonne la plus à gauche de la figure 4. Dans la colonne suivante de la figure 4, les éléments caractéristiques sont classés de haut en bas sur la figure 2, c' est-i-dire par ordre-décrotesaat de la coordonnée Y. Ces deux colonnes sont maintenant explorées ensemble, en commençant pour toutes les deux à partir de la position portant le numéro 5. La co lonne située le plus à gauche (colonne I) n'est explorée que vers le bas, tandis que l'autre colonne (colonne Y) est explorée vers le haut comme vers le bas.Au premier incrément de l'exploration, on rencontre l'élément caractéristique 6 dans la colonne x (exploration vers le bas), et on rencontre les éléments caractéristi- ques 18 et 14 pour les explorations respectives vers le haut et vers le bas de la colonne Ye les colonnes finales marquées ex- plorationft sur la figure 4 traduisent ceci par des tirets et des barres verticales placés respectivement dans des colonnes distinctes. Après 8 incréments d'exploration, on aboutit à la position représentée sur la figure 4. On a alors trouvé 5 éléments caractéristiques aussi bien dans la colonne x que dans la colonne Y, et l'ordre dans lequel ils apparaissent est représenté dans la dernière colonne de la figure 4. En fait, les éléments caractéristiques 6, 7, 8, 10 et 12 ont été trouvés respectivement au Sème 8ème, 3ème, 6ème et 7ème incrément d'exploration. Pour ces 5 éléments caractéristiques, on calcule les différences des valeurs des coordonnées par rapport à l'élément caractéristique 5. La valeur la plus élevée obtenue est ensuite utilisée pour établir des valeurs maximale et minimale de Y ainsi qu'une valeur maximale de 1, afin de construire un rectangle imaginaire représenté sur la figure 5 et dont un c8té passe par le point représentant l'élément caractéristique 7, possédant la différence la plus élevée pour sa coordonnée Y. Tous les autres éléments caractéristiques ayant une coordonnée X inférieure à X max sont ensuite facilement identifiés en continuant l'exploration de la colonne X(figure 4).Dans le cas particulier représenté, on trouve les éléments caractéristiques 14, 15, 17, 18 et 19, et on peut calculer la somme des carrés des coordonnées pour l'ensemble des 10 points, afin de déterminer ceux qui sont les plus rapprochés de l'élément caractéristique 5. Cependant, on continuant 1' exploration de la colonne X, on peut comparer tour à tour la coordonnée x de chaque élément caractéristique avec les coordonnées Y des 5 autres éléments caractéristiques, de façon à trouver quelles sont les coordonnées les plus faibles.Ceci permet de dessiner d' autres rectangles représentés sur la figure 5, passant par les points marqués 14 et 15. le ler rectangle ne donne que les élé- ments caractéristiques 8, 12 et 14, tandis que le second donne en outre les éléments caractéristiques 6, 10, 17 et 15, si bien qu' on dépasse le nombre qu'on s1 est fixé pour les éléments les plus voisins, qui est de 5. Les 4 éléments earactéristiques autres que 8, 12 et 14 peuvent alors être comparés en calculant les sommes des carrés des différences des coordonnées (par rapport à léld- ment caractéristique 5), de façon à trouver les deux sommes les plus faibles.Qu'on emploie l'un ou l'autre des 2 procédée cidessus, on trouve que les éléments caractéristiques les plus pro ches vers la droite, en distances absolues, sont les éléments 8, 14, 12, 6 et 18, comme le montre le demi-cercle passant par le point 18. les distances entre l'élément caractéristique 5 et ses5 éléments voisins sont alors exprimées en nombre de crêtes dans la direction des vecteurs représentés sur la figure 3. Il peut donc être préférable d'éviter les calculs des sommes de car rées, et de compter simplement les nombres de crêtes relatifs à chacun des éléments caractéristiques se trouvant à l'intérieur du rectangle de plus glandes dimensions de la figure 3, et de choisir les éléments correspondant aux plus faibles nombres de crêtes, bien que ce procédé ne conduise pas nécessairement aux 5 mêmes points. En fait, il n'est pas nécessaire que les 5 points voisins vers la droite soient les plus voisins en distances absolues, pourvu que les procédés permettant de les obtenir soient les mêmes pour les listes de caractéristiques de tous les dessins considérés. Par exemple, on peut simplement accepter les 5 éléments caractéristiques 6, 7, 8, 10 et 12, dès qu'ils sont découverts au cours de l'exploration des deux premières colonnes de la figure 4. Chaque article d'une telle liste d'éléments caractéristiques est composé par 3 mots de 24 e.b. se présentant sous le format représenté sur la figure 5. Dans ces mots, T représente le type d'élément caractéristique (extrémité ou bifurcation de crêtes) D représente la direction de la crête à l'emplacement de l'élément caractéristique, x et Y représentent les coordonnées cartésiennes de l'élément caractéristique, Xi représente l'index d'identifica- tion qui doit être ajouté au numéro d'identification de l'élément caractéristique pour donner l'élément caractéristique voisin de rang i, et Ri représente le nombre de crêtes intermédiaires relatif à cet élément voisin. On notera qu'il reste deux éléments binaires libres dans le second mot et le troisième mot.Ces éléments binaires peuvent être utilisés pour un contrdle de parité, ou pour tout autre but souhaité. Si un nombre de crêtes interiédiaires dépasse 15, ce qui se produit très rarement, on considère simplement que ce nombre est égal à 15, c'est à dire qu'il est représenté par le nombre binaire liii. Ce codage des données relatives aux léments caractéristiques convient particulièrement bien à un traitement en relation avec une liste similaire obtenue à partir d'un autre dessin, dans le but de mesurer le degré de corrélation qui existe entre les deux listes, comme il est décrit ci-aprèe. On compare les parties T, D, x et Y des premiers iots des deux listes correspondant respectivement à l'empreinte de référence (L) conservée en archives, et à l'empreinte (P) qui doit être identifiée, et on établit une liste des paires qui coincident . Cette liste est appelée la liste de coNncid-ence8, et on considère qu'il y a coïncidence Si les écarts entre les parties respectives T, D, x et Y sont inférieurs à des valeurs prddé- terminées.On obtient des résultats satisfaisants en adoptant une marge d'écart d'une unité, ou moins, pour la partie D, et de deux unités, ou moins, pour les parties x et Y . Ufle telle coinci- dence correspond à ce qu'on a appelé précéde-ent une coinciden- principale, et est inscrite dans la liste de co'incidences. Cha que article de cette liste comporte les numéros d'identification des éléments caractéristiques en coïncidence dans la liste d' éléments caractéristiques respective,ainsi qu'unindiquant le degré de coïncidence .Les éléments d'identification de listes d' éléments caractéristiques peuvent comporter chacun 7 e.b., ce qui laisse 9 e.b. pour le score, plus un e.b. libre La signification de ce score est améliorée en comparant les éléments caractéristiques apparaissant dans la liste d'élé ments caractéristiques sous forme de voisins des éléments caracté ristiques d'une coïncidence principale, de façon à trouver des coïncidences secondaires.Pour cela, on compare tout d'abord les nombres de crêtes des éléments caractéristiques voisina figurant dans la liste, c'est à dire quton n'utilise que les informations contenues dans les articles de la liste d'élémetscaractéristi- ques qui correspondent aux éléments caractéristiques de la coïn- cidenoe principale considérée.Lorsque la différence entre les nombres de crêtes intermédiaires ne dépasse pas une valeur pré déterminée, par exemple 3 (nombre binaire 11), on utilise les index d'identification correspondants pour consulter les arti cles de la liste d'éléments caractéristiques relatifs à ces é déments caractéristiques voisins pouvant donner lieu à coince dences, et on effectue ensuite d'autrescosparaisons portant sur les valeurs des données de direction et de coordonnées, On é tablit à nouveau des valeurs maximales pour les différences, par exemple 2 (nombre binaire 10), ou moins, en ce qui concerne la direction, et 3 (nombre binaire 11), ou moins, en ce qui con cerne chaque coordonnée. On calcule un total basé sur les ré sultats de ces comparaisons, en comptant par exemple 1, 2, 3 ou 4 (nombres binaires 001 à 100) pour des différences de nom bres de crêtes intermédiaires de 3, 2, 1 ou O (nombres binaires 11 à 00); 1 ou 2 (nombres binaires 01 à 11) pour des diffé rences de direction de 1 ou de O (nombresbinaires 01 ou 00); 1, 2, 3 ou 4 (nombres binaires 00 à 11) pour des différences de 3, 2, 1 ou O (nombres binaires 19, 01 ou 00) sur les valeurs des coordonnées X; etl, 2, 3 ou 4 (nombres binaires 00 à 11) pour des différences de 3, 2, 1 ou O (nombres binaires 10 à 00) sur les valeurs des coordonnées Y.En général, on ne cherche pas à ce que les coincidences entre paires d'éléments caractéristiques voisins satisfassent des conditions aussi sévères que les coïncidences principales, et on affecte généralement un score plus faible à ces coïncidences secondaires. Les totaux correspondant aux aZeérentes colncidences secondaires possibles sont enregistrés en des positions suivant immédiatement la position de la coïncidence principale correspondante, et ces totaux sont accompagnés des index identifiant les éléments caractéristiques concernés. On utilise l'élément binaire libre pour établir une distinction entre les coincidences principales et les coïncidences secondaires, cet élément binaire étant par exemple placé à la valeur I dans le cas d'une correspondance principale. les totaux dea coïncidences secondaires sont additionnés de façon à être introduits dans la zone réservée au score, dans l'article de la liste de coïncidences qui correspond à la cdincidence principale considérée.Si pour l'un ou 11 autre des éléments caractéristiques d'une coïncidence principale, un élément caractéristique voisin apparat dans plusieurs coïncidences secondaires, on sélectionne la coïncidence présentant le score le plus élevé, et on élimine les autres. S'il se produit un conflit dA à ce que 2 éléments voisins figurent dans plusieurs coineiden- ces différentes, on choisit les coïncidences qui ne donnent pas lieu à un conflit et qui possèdent le score le plus élevé pour la coincidence principale (marquée "1") au niveau de l'élément binaire libre sour obtenir le score définitif de la coïncidence principale, on additionne successivement les mores des cdlncidences secondaires au score affecté précédemment à cette cSincidence, du fait de la comparaison des zones T, D, X et Y, relatives à la coincidence principale etle-meme. la figure 6 représente une partie d'une liste de coin- cidences et montre la structure typique de quelques articles de cette liste. On voit sur cette figure, à partir de la première ligne, un Jeu complet d'articles relatifs à l'élément caractéristique portant le numéro d'identification i. 'index iFi (servant à l'identification dans la liste d'éléments caractéristiques de la figure 5 ) relatif à cet élément caractéristique est représenté en compagnie de l'index LFI relatif à un élement caractéristique de l'empreinte de référence pour lequel les zones T, D, X et Y indiquent une coïncIdence. On suppose qu'il s' agit de la J éme correspondance trouvée au coure du traitement, que l'on a Joli, et que les 9 e.b. situés à l'extrême droite du groupe indiquent le score MESj de la coïncidence. L'élément binaire situé le plus à gauche dans ce mot possède la valeur "1" pour indiquer qu'il s'agit d'une coïncidence principale.Les 3 articles auivants du tableau représentés sur la figure 6 concer- nent des coïncidences trouvées entre les éléments caractéristiques voisins qui ont été enregistre pour les deux éléments caractéristiques PFi et LFx, et les mots binaires correspondants présentent donc la valeur " pour l'élément binaire situé le plus à gauche, pour indiquer qu'il s'agit de coïncidences secondaire. Sur la figure 6 on a Supposé qu'il existait une correspondance entre, d'une part, le ler, le 4ème et le 5ème élé- ments caractéristiques voisins de l'élément caractéristique PFi de l'empreinte à identifier, et d'autre part le 3ème, le 4ème et le 5ème éléments caractéristiques voisins, respecti vement, de l'empreinte de préférence IF. Les index d'identification appropriés sont également portés sur la liste.On affecte un score ( NS1 NS2 et NS3 respectivement ) à chacune de ces coïncidences secondaires, et ces scores sont additionnés entre eux puis ajoutés au score de coincidence principale déterminé précédemment et placé dans la eone PITPS à la suite de la comparaison initiale de la coïncidence principale. On a supposé qu'il existait une coïncidence entre 3 des éléments caractéristiques les plus voisins, mais ce nombre peut être en réalité plus faible ou plus élevé. A la ligne suivante de la partie de liste représentée sur la figure 6, l'élément binaire situé le plus à gauche du mot possède la valeur "1", et ce mot concerne les éléments caractéristiques de la coincidence principale suivante, l'un des éléments caractéristiques appartenant à l'empreinte à identifier, et l'autre appartenant à l1empreinte de référence considérée. On supose que ce mot concerne le (il) ème élément caractéristique de l'empreinte à identifier, bien qu'il puisse ne pas y avoir de coïncidence pour cet élément caractéristi que, auquel cas on trouverait à cet emplacement l'élément caractéristique suivant pour lequel il existe une coïncidence.L'élé- ment caractéristique relatif à l'empreinte de référence porte 1' indice y, et le score de la coïncidence principale porte l'indi- ce ( + 1) pour montrer qu'il s'agit de la coïncidence suivante qui a été trousée.Onn'a indiqué dans ce cas qu'une seule coïn- cidence secondaire, bien qu'il puisse y en avoir d'autres dans les lignes suivantes ( non représentées ) de la liste I1 existe plusieurs r0SX qui font que lee éléments caractéristiques de l'empreinte à identifier et ceux de l'em- preinte de référence donnent lieu à des coïncidences principales mettant en Jeu des éléments caractéristiques possédant des nuié- ros d'identification différents dans les listes respectives d'élé- ments caractéristiques, bien que le même codage soit utilisé pour les deux listes.I1 peut arriver qu'une seule partie de 1' empreinte puisse être utilisée pour l'identification : ceftai- mes régions de l'empreinte peuvent en effet être totalement flan- quées par des taches, ou bien des poussières ou des défauts de la surface sur laquelle a été réalisée l'empreinte peuvent fai- re apparttre des éléments caractéristiques parasites ou mas- quer de véritables éléments caractéristiques. Ces modifications des éléments caractéristiques peuvent très bien échapper à l'opération de "nettoyage", ou même être introduites par celle-ci. Cette opération de "nettoyage" est généralement accomplie sur les donnée d'origine fournies par l'analyseur de façon, par e exemple, h remplir de petits espaces vides apparaissant dans les crêtes et dans probablement à des pores et/ou à des poussières. Si l'on n'accomplissait pas cette opération, ces espaces vides conduiraient à identifier un nombre excessif d'éléments caractéristiques, avec une trop forte proportion d'éléments caractéristiques parasites. En établissant la liste de coincidences de la figure 6, on a supposé qu'on considérait tour à tour les éléments caractéristiques de l'empreinte à identifier et qu'on les corparait avec les éléments caractéristiques de l'empreinte de référence. Cependant, on peut aussi bien faire l'inverse et considérer tour à tour les éléments caractéristiques de l'empreinte de référence, en cherchant quels sont les éléments caractériBti- ques de l'empreinte à identifier qui donnent une coincidence. I1 est probable qu'un certain nombre d'éléments caractéristiques de l'une des deux empreintes, ou des deux, apparaissent dans plusieurs des coincidences principales (élément binaire "1" à gauche du mot correspondant ) de la liste de coin- cidences. A ce niveau, on considère qu'il est souhaitable d'élaguer la liste de coïncidences, de manière à ce qu'aucun élément caractéristique de l'une ou l'autre des empreintes (empreinte à identifier et empreinte de référence) n'apparaisse dans plus de 3 coïncidences principales. Dans ce but, on reJette les cdinci- dences présentant les scores les plus faibles ; lorsque c'est né pessaire. La phase suivante de la-oomparaison entre les deux empreintes consiste à prendre les coïncidences secondaires (éléments binaires "0" en tête du mot correspondant) dans l'ordre dans lequel elles apparaissent dans la liste globale des coin- cidences, et à explorer le reste de la liste pour trouver des coïncidences principales (éléments binaires "1" en tête du mot correspondant) qui soient identiques, On modifie alors la liste de coïncidences en remplaçant les scores des cotncidences secondaires pour lesquelles il existe des coïncidences principales identiques par des index indiquant la position de ces dernières dans la liste de coïncidences.De plus, les scores de toutes les autres coïncidences secondaires sont replacés par des index indiquant des articles correspondants (avec les scores d'origine) placés à la fin de la liste de coincidencew sod4- fiée. La plupart de ces coïncidences secondaires concernent au moins un élément caractéristique qui se trouve sur le bord de l'empreinte à laquelle il appartient. Simultanément, on établit une liste de scores cumulés dont les articles ne correspondent qu'aux scores des cdincidences principales (éléments binaires "I" en tete du mot correspondant) de la liste de coincidences,les coïncidences secondaires pour lesquelles il n'existe pas de co1ncidencesprincipa- les ayant été placées à la fin de la liste sous forme de coin- cidences principales ne comportant pas de colncidences secondaires. Ensuite, en utilisant la liste de coïncidences modifiée, chacun des scores des articles indiqués par l'index placé dans la zone de score de la liste, est ajouté au score de la coinci- dence principale pour laquelle il constitue une colncidence secondaire.Simultanément, et en utilisant également la liste de scores cumulés, le score de chaque coïncidence principale est ajouté au seo- re de chaque article désigné par un index d'une coïncidence secondaire associée. La figure 7 montre comment les index A, B; C et s ont remplacé les scores de coïncidences secondaires NS1 à DS3 de la figure 6, et comment on forme une liste séparée de scores cumulés dont les articles sont désignés par les termes "SCORE j " et "SCORE j 41".Les articles de cette dernière liste sont constitués chacun par la somme des scores se trouvant dans les articles indi qués par les mots placés immédiatement à la suite et portant lté- lément binaire "0" en tête, et du score de la coïncidence principale la plus proche (élément binaire "1" en tête) située avant tout mot portant un élément binaire "0" en tête,désigné par un indes. Ce processus est accompli en commençant à partir du haut de la liste de coïncidences. L'étape suivante consiste à explorer la liste de sco-res cumulés résultante en comparant les différents scores à un seuil prédéterminé au-dessous duquel les coincidences ne sont pas ffluffi8amment bonnes pour être conservées. Au noient de cette exploration, la liste de scores cumulés comporte également les scores des coïncidences secondaires pour lesquels il n'existe pas de coincidence principale correspondante. En pratique, fl suffit de placer à zéro les scores qui sont inférieurs au seuil. S'il reste trop peu de scores différents de zéro, on déclare que les deux dessins ne coïncident pas, et on appelle la liste d'éléments caractéristiques d'une autre empreinte de référence, pour commencer une autre comparaison. On rappelle que la liste de coïncidences peut eompor- ter Jusqu'à 3 articles pour un élément caractéristique quelconque.A ce niveau du traitement, il est possible que certains élé- ments caractéristiques de l'une ou l'autre des listes d'éléments caractéristiques apparaissent dans plus d'une paire en coinciden- ce à laquelle correspond un article de'la liste de scores cumulés. Dans ces conditions, on ne laisse subsister dans la liste de scores cumulés que les meilleurs scores de chaque élément caracté ristiqut de l'une ou l'autre des listes. Ceci peut être réalisé simplement en ne choisissant que l'article le plus élevé dans chaque ligne et chaque colonne d'une matrice dont les lignes correspondent aux articles de l'une des listes d'éléments Ca- ractéristiques, et dont les colonnes correspondent aux articles de l'autre liste d'éléments caractéristiques, L'opération décrite ci-dessus qui consiste à établir la liste de scores cumulés en additionnant les scores dans les deux sens dans la liste de coineidences, a pour effet d'aug Venter les scores des paires en coincidence d'une manière dépendant fortement du degré de óincidence constaté entre les élé ments caractéristiques voisins sélectionnés, ceci s'appliquant aussi bien aux colneidences secondaires qu'aux coïncidences principales elles-mêmes. On peut ainsi déterminer effectivement dans quelle mesure-il existe un réseau de cdincidences en chatne li ées par les relations successives entre les cdincidencea secon daires enregistrées. On peut considérer que cette opération consiste à réaliser un score en channe en utilisant que des liens locaux pour former les scores cumulés. On a constaté qu'on pou axait encore accentuer la valeur de ce score en considérant l'ef- fet des scores qui demeurent encore dans la liste finale de scores cumulés. Pour cela, on forme une nouvelle liste comportant des emplacements parallèles pour la liste de colncidences et la liste de scores cumulés. Par commodité, cette nouvelle liste sera appelée "liste de sommes de scores". Cette liste est établie à partir de la liste de scores cumulés en commençant à une extrémité de la liste de scores cumulés et en additionnant tous les scores des coïncidences principales avec les scores de leurs coincidences secondaires. Ces scores augmentés sont ensuite aJoutés dans les coincidences secondaires de la colncidence qui est considérée comme une colncidence principale. Lorsqu'un article de la liste de coincidences comportant un élément binaire "1" en tê- te possède -un article correspondant dans la liste de scores cumulés, ce score est ajouté dans l'article de la liste de scores cu mulé correspondant à chacun des index immédiatement suivants (élément binaire O" en tête du mot correspondant). Siuultanément les valeurs se trouvant dans chacun des emplacements de la liste de scores cumulés qui sont désignés par les index sont ajoutées aux valeurs se trouvant aux emplacements correspondant à leurs propres coincidences secondaires respectives.Cette association en chaine de valeurs de scores est ainsi accomplie en commençant à l'autre extrémité de la liste, et les scores de coinoidences principales sont utilisées pour augmenter les scores des coïncidences principales pour lesquelles ils apparaissent sous forme de coincidences secondaires. les valeurs résultantes sont enregistrées dans la liste de sommes de scores qui subit ensuite une exploration avec comme paraison à un seuil.Cette liste est ensuite éditée de façon à s' assurer qu'aucun élément caractéristique particulier de la liste d' éléments caractéristiques ne possède d'articles dans la liste de sommes de scores pour plus d'une paire en coincidence faisant intervenir cet élément caractéristique Une liste finale de sommes de scores eet ensuite éditée de façon à s'assurer qu'on ne retient que des éléments caractéristiques liés ensemble par un réseau continu de relations entre coincidences principales, par l'intermédiaire de colncidences secondaires qui sont également des coïncidences principales par rapport aux éléments situés à leur droite.Ceci peut être réalisé facilement en examinant chaque article non nul de la liste de sommes de scores et en vérifiant dans la liste de coïncidences qu'il correspond à une coincidence principale (élément binaire "1" en tête du mot correspondant ) qui possède une coïncidence secondaire correspondant à un article non nul de rang inférieur dans la liste de sommes de scores. Comme ceci ne peut pas s'appliquer au dernier article de la liste de sommes de scores, cette opération commence au second article non nul en partant du bas, et se poursuit 8é- quentiellement Jusqu'au haut de la liste.Lorsque ces critères sont vérifiés, les index de la liste de coïncidences relatifs à la fois aux co'incidence8 principales et secondaires sont enregis- très dans un article d'une liste de liens. Lorsque ces critères ne sont pas vérifiés, l'article correspondant de la liste de soi- mes de scores est marqué avec un élément binaire 't1" en une position binaire prédéterminée qui possde la valeur 0" dans le cas contraire0 Ensuite, après que la liste de sommes de scores a té explorée de la manière indiquée ci-dessus, on prend les articles de la liste de coincidence correspondant à ces articles marqués par un élément binaire "1", et on les compare avec des articles supérieurs de cette liste, de façon à trouver le ou les articles relatifs à une coincidence principale qui possèdent cette coincidence comme coincidence secondaire. S'il en existe, les index des listes de coincidence sont introduits également dans la liste de liens, pour ces deux coincidences. On fait ensuite le total des valeurs de la liste de sommes de scores pour tous les membres de la liste de liens. Si ce total est inférieur à un autre seuil donné, et/ou si la liste de liens contient trop peu d'articles, on déclare qu'il n'y a pas coincidence, et on examine une autre empreinte de référence. Dans le cas contraire, les résultats sont affichés par l'intermédiaire d'une imprimante ou d'une console de visualisation, par exemple. De préférence, le score final tient compte également du nombre de liens dans la liste finale de sommes de scores, par exemple de la manière suivante Score final = (score de base) x R1 x R2 R1 étant le rapport entre le nombre de coincidences principales et la valeur maximale possible de ce nombre, et R2 étant le rapport entre le nombre de liens ét le nombre maximal possible. I1 va de soi que de nombreuses modifications peuvent être apportées au procédé décrit, sans sortir du cadre de l'invention. En particulier, l'emploi évoqué d'un calculateur n'est nullement indispensable à la mise en oeuvre-du procédé et n'a été donné qu'à titre d'exemple. REVENDICATIONS 1.- Procédé pour identifier des formes de dessins, notamment d'empreintes digitales, par comparaison avec un dessin de référence, caractérisé en ce que : on établit une liste de données identifiant chaque élément caractéristique du dessin inconnu; on établit une liste de données identifiant chaque élément carac téristique du dessin de référence; pour chacune de ces listes, on associe aux données identifiant chaque élément caractéristique des données identifiant un nombre prédéterminé d'éléments caractéristiques voisins, sur le dessin, de l'élément caractéristique considéré, compte-tenu d'une direction d'analyse choisie sur ce dessin; et on effectue la comparaison des deux dessins en déterminant le degré de coincidence entre chaque élément caractéristique de l'un des dessins et chaque élément caractéristique de l'autre, ce degré de coincidence étant évalué en tenant compte des degrés de cpincidence qui existent entre lesdits éléments caractéristiques voisins de chacun des deux éléments caractéristiques considérés. 2.- Procédé selon la revendication 1, caractérisé en ce que lesdites données identifiant un nombre prédéterminé d'éléments caractéristiques voisins comprennent : la distance de chaque élément voisin à l'élément considéré, et un index d'identification de chaque élément voisin dans la liste de données correspondante. 3.- Procédé selon la revendication 2, caractérisé en ce que on établit une liste des éléments caractéristiques en coincidence, dans les deux dessins, chaque article de cette liste comportant un nombre mesurant le degré de coincidence entre les éléments caractéristiques voisins, pris deux à deux, des deux éléments caractéristiques considérés; on fait un cumul de ces nombres en fonction des liens entre les paires d'éléments en coincidence qui sont établis par les paires d'éléments voisins en coincidence; et on utilise les nombres cumulés les plus élevés pour définir le degré de coîncidence global entre les deux dessins.