Brevet FR2402905A1 — publié le 19790406

La présente invention concerne un procédé et une installation pour l'analyse et la comparaison d'ensembles de données. De façon plus générale, l'invention se propose de créer des moyens permettant de comparer des ensembles d'informations à des informations contenues dans un fichier, tel que des empreintes digitales, des cartes géographiques, etc. Les informations contenues dans le fichier et les informations analysées sont transformées en des signaux binaires par exemple, par une analyse ponctuelle.A titre d'exemple, on se reportera a' un tel dispositif d'analyse décrit dans le brevet français 76 03 510 qui décrit un dispositif de détection d'empreintes digitales, ce dispositif se composant d'une surface sur laquelle on pose le doigt dont on veut analyser l'emprente digitale, le capteur coulportant de multiples contacts électriques qui permettent de déceler les points de contact physiques avec les aspérités du doigt et donner ainsi une image numérique de la forme de l'empreinte digitale. Un tel procédé serait également applicable dans les domaines les plus divers, tels que les repérages géographiques pour localiser ou comparer une photographie aérienne à un plan, suivre l'évolution d'une zone géographique en comparant des photographies prises à des intervalles donnés, etc., et de façon générale, suivre l'évolution d'un procédé physique ou chimique, etc. La présente invention a pour but de créer un moyen permettant d'effectuer une telle comparaison de façon automatique et simple. A cet effet, l'invention concerne un procédé de comparaison et d'analyse d'informations pour vérifier si une information correspond à une information enregistrée dans une mémoire, procédé caractérisé en ce qu'on répartit l'ensemble des informa tions suivant une matrice de colonnes c et de lignes 1 , chaque n m point de la matrice correspondant au codage binaire d'une information (codage par deux états), on répartit l'ensemble E' d'informations-témoins dans une mémoire PROM sous la forme d'une ma trice de colonne kN, et de lignes DM " on choisit une tranche Dxr Du + y correspondant à une largeur de y lignes dans la matrice témoin E' et on compare cette tranche à des surfaces Sm,n de m, n même longueur et de même largeur de la matrice E, on compare ligne par ligne les deux surfaces pour vérifier l'identité ou llab- sence d'identité entre les points correspondants de chaque ligne, on totalise la somme des points identiques de chaque ligne, on retient une ligne pour bonne, si le total des points identiques dépasse un seuil S1 prédéterminé, puis on totalise le nombre de lignes ayant satisfait à ce premier seuil, on ne retient la sur face Sm, n que si le total de lignes retenues dépasse un second m, n seuil S2, prédéterminé, on associe dans l'affirmative, le total des lignes retenues à la surface S n on déplace la surface S des m, r d'une ligne ou d'une colonne de façon à couvrir au moins une partie de la matrice d'information E et on retient la surface S dont le nombre associé est le plus grand, puis on modifie m, n les coordonnées de la matrice d'informations E de façon que les coordonnées de la surface Sm, S ainsi retenues correspondent aux coordonnées de la bande Dx, Du + y et on recommence une comparaison ligne par ligne de toute la matrice d'information E' avec toutes les lignes communes de la matrice d'information E, pour vérifier l'identité entre les deux ensembles d'information E,E'. Selon une autre caractéristique de l'invention, pour comparer la bande Dx, Dx + y à la matrice des informations E, x- la bande Dxr D + on choisit une première surface sm,1 dont la première colonne coincide avec la première colonne de la matrice des informations E, puis on choisit une seconde surface 5m,2 dont la première colonne correspond à la seconde colonne c2 de la matrice de l'en- semble E et on poursuit le décalage en restant limité entre les lignes LM et.LM + y puis après épuisement de la surface de la matrice comprise entre les lignes LM et LM + yt on choisit une nouvelle zone L+l, LM + Y + 1 dans laquelle on choisit une surface 5m +1,1 que l'on compare de nouveau à la bande Dx' Dx + y puis on choisit la surface S + 1, 2 jusqu'à épuisement de la m + ... zone comprise entre les lignes s + 1 et LM + Y + 1 puis on choisit une nouvelle zone LM + 2' LM + Y + 2 L'invention concerne, également, une installation pour la mise en oeuvre du procédé, caractérisée en ce qu'elle se compose d'un capteur recevant l'ensemble d'informations E, et introduisant ces informations dans une mémoire, une seconde mémoire contenant les informations de l'ensemble témoin E', un comparateur balayant la mémoire des informations E et des informations E' et appliquant ces signaux à un comparateur, une mémoire pour totaliser les résultats de la comparaison et une unité de calcul et de comparaison pour totaliser les coSncidences ligne par ligne, et retenir les lignes suivant qu'elles satisfassent au seuil puis la somme des lignes de chaque surface S lorsque cette somme m,n dépasse un seuil S2 donné, et enfin un sélecteur pour retenir la surface Sm,n associée à la plus grande valeur. m,n Le procédé et l'installation selon l'invention sont décrits plus en détail, à l'aide des dessins annexés, dans lesquels - la figure 1 est un schéma de la mise en oeuvre du procédé et de l'installation selon l'invention, - la figure 2 est un schéma complémentaire pour la mise en oeuvre du procédé de l'invention; - la figure 3 est un tableau résultant de la comparaoson des figures 1 et 2. Le procédé et l'installation selon l'invention, ont pour but de permettre la comparaison d'un ensemble de données ou d'informations E par rapport à un ensemble témoin E'. L'ensemble d'informations E se compose d'informations, sous forme binaire, réparties dans un tableau comportant des colonnes c et des lignes 1 . Dans la figure, il s'agit d'un n m tableau de 60 colonnes cl ....cn ... et de 75 lignes lî 12 ... 13 ... 1m ... 175. Chaque intersection de ligne ou de m colonne est un point représentant une information, sous forme binaire. L'ensemble E constitue par définition l'ensemble analysé dont le point courant a les coordonnées cn, 1m. m Cet ensemble analysé est comparé à un ensemble témoin E' d'informations inscrites sous forme binaire et qui sont réparties dans un tableau à N' colonnes kl k2 ... kan, et M' li gnes dl, d2 e dx .,. dom, Dans le cas de l'exemple, l'ensemble E' est inscrit dans une matrice de 45 colonnes et de 60 lignes. Cette matrice a des dimensions plus petites que la matrice servant à l'inscription des informations E. Le problème que se propose de résoudre le procédé et l'installation selon l'invention, consiste à rechercher s'il y a une concordance entre des informations de l'ensemble E et celles de l'ensemble E' et si cette concordance peut etre assimilée à une identité. Pour procéder à la comparaison, on choisit tout d'abord une tranche d'informations de l'ensemble E': comprise entre les lignes Dx ff + y sur une largeur comprise entre les colonnes k1 et , incluses. On analyse un rectangle d'informations Sm,n de la ma m,n trice de l'ensemble E, et qui présente la meme surface que le rectangle d'informations ainsi choisi dans l'ensemble E'. La première surface ainsi choisie dans l'ensemble E est délimitée par les lignes 1 , 1 + y et les colonnes cl at c Le coin m m inférieur gauche sera appelé par définition le point Am,1' m et 1 correspondant aux coordonnées de ce point dans la matrice CnLmo La surface ainsi délimitée sera eppelée surface Sm,1' les indices correspondant aux coordonnées du point A On procède alors à la comparaison des lignes 1m, 1m + 1' 1m + 2 ... 1m + y avec les lignes Dx, Dx + 1 Dx + 2' m+y Dx + y.En cas d'identité entre les informations d'un point d'une ligne de la surface Sm,1 et d'un point de coordonnée correspondante dans la ligne correspondante de la surface choisie dans l'ensemble E', le résultat de l'opération sera représenté par un cercle à la figure 1 et dans le tableau récapitulatif de la figure 3 Puis, on totalise pour chaque ligne le nombre de points correspondant à une identité, comme cela est indiqué dans le tableau de la figure 3. On utilise, a' la suite de cela, un critère S1 consistant à retenir chacune des lignes qui contient un nombre de points de coincidence supérieur a une certaine limite. Les lignes retenues sont indiquées par le chiffre 1 dans le tableau de la figure 3, alors que les lignes non retenues sont indiquées par un zéro barré Puis, on fait le total du nombre de lignes retenues, et qui, dans le présent exemple, est égal à 3 Ce total est comparé à un second critère ou seuil S2 et le total associé au tableau Sm,1 n'est retenu que s' il dépasse le seuil S2 prédéterminé. A titre d'exemple dans le tableau de la figure 3, on a supposé que la surface Sm,1 était constituée par un rectangle ayant 13 colonnes et 7 lignes On a fixé à titre d'exemple, le premier critère S2 = 6/7, ce qui signifie que l'on ne retient que les lignes dont le nombre de points d'identité est supérieur ou égal à 10, le nombre de points total ou d'identités possible étant égal à 13 Dans cet exemple: le second seuils c'est-à-dire le critère de retenue du total des lignes elles-memes retenues est fixé à 6/7, ce qui signifie que l'on ne retient le total que si celui-ci est égal ou supérieur à 6 (pour un maximum égal à 7). Dans le tableau de la figure 3, on a représenté les points de concordance ou d'identité par un rond. On a utilisé le meme schéma pour la ligne 1m+l dans la figure 1 Après cette première comparaison entre la bande témoin et la surface Sm,1' on procède à une nouvelle comparaison entre la bande témoin (qui reste la même) et une nouvelle surface dont le sommet aura les coordonnées Am,2' c'est-à-dire une surface 5m,2 qui sera décalée de la précédente d'une colonne.Cette nou- velle surface sera délimitée comme la précédente par les lignes Lm et L + y et par les colonnes c2 et cn,N + 1 On procède m + y 2 n,N + 1 alors à la meme opération de comparaison entre les divers points c2, c3 .... c N' + 1 de la ligne Lm avec les points de coordon nées k1, k2 ... kN de la ligne des x, puis on compare les lignes L + 1 et D + 1 ... jusqu'à épuisement des lignes Dx + y et Lm +y. épuisement et D On note dans un jusqu a tableau analogue à celui de et figure 3 , les note tableau analogue à celui de la points de coïncidence, puis le total de points de colncidence par ligne et les lignes acceptées en fonction du critère S1 défini ci-dessus.On aboutit ainsi à un total qui, suivant le cas: est supérieur ou égal à la limite S2 ou est inférieur à cette limite Dans le premier cas, le-total obtenu est retenu; dans le second cas, le total est considéré comme nul Puis, on fait- avancer la surface de comparaison d'une colonne pour obtenir la surface 5m,3 et on procède aux mêmes opérations que celles ci-dessus.Ce cycle de comparaison par decalage de la surface S n se poursuit jusqu' ce qu'on arrive en bout de la matrice représentant les informations E, c'est-à-dire sur la colonne C60 Une fois ces surfaces examinées on choisit une nouvelle surface Sm + 1,1qui est délimitée par les lignes lm + 1 et lm + y + 1 on effectue la comparaison ligne par ligne et après la fin de cette comparaison, on choisit une nouvelle surface Sm +1,2décalée de la surface Sm + 1,1 d'une colonne On balaie ainsi une partie préadressée choisie au préa- lable en fonction de certains critères de la matrice contenant les informations E. Après avoir terminé cette comparaison, on analyse les nombres associés aux diverses surfaces S et on retient la surface Sm,n qui est associée au nombre le plus grand. Divers critères statistiques peuvent entrer en ligne de compte pour choisir l'une des surfaces S n en cas d'identité m,n de nombres associés à plusieurs surfaces. La surface Sm, Sn ainsi retenue permet de positionner n la matrice correspondant à l'ensemble E' dans la matrice correspondant à l'ensemble E (étant donné que par hypothèse nous avons supposé que les dimensions de la matrice de l'ensemble E' étaient plus petites que celles de la matrice E). En effet, par cette comparaison, puis ce choix, on conclut qu'étant donné l'identité entre la surface (Dx, D + y) de la matrice E' et la surface x+y Sm,n le sommet Ax,1 de la matrice E' devait coïncider avec le m,n x,l sommet A de la surface S .Partant de là, il est alors pos m,n sible de procéder à une nouvelle comparaison point par point des parties communes des matrices des ensqibles E et E' Cela per- met de procéder à une nouvelle vérification qui devrait confirmer l'identité obtenue par les précédentes comparaisons. Cette nouvelle comparaison qui se fait ligne par ligne, constitue une sécurité. Le procédé décrit ci-dessus s'applique notamment dans le cadre de l'invention à un comparateur analyseur d'empreintes digitales dans le but de comparer une empreinte enregistrée par un capteur (ensemble E) à une ou plusieurs empreintes inscrites dans un fichier, tel qu'une mémoire (ensemble E') pour vérifieur s'il y a ou non identité. Une telle comparaison et reconnaissance d'empreintes peut constituer la base de dispositifs de commande avec détection d'identité, telle que l'ouverture d'une porte, d'un coffre, la manoeuvre de mécanismes etc... I1 est également possible de réa- liser un détecteur muni d'un tel comparateur-analyseura présentant un fonctionnement séquentiel, c'est-à-dire nécessitant la répétition de la comparaison d'une empreinte, à des instants donnés ou après un certain délai, pour augmenter la sécurité. Un tel comparateur analyseur se réalise facilement sous forme de circuit intégré, à l'aide de circuits électroniques dont la forme n'a aucune caractéristique particulière. Un capteur permettant de déceler une empreinte est notamment décrit dans le brevet français 76 03 510. Un tel capteur peut fournir d'une empreinte de doigt, un ensemble de 4500 points (ensemble E) qui correspond aux points de contact entre la surface du doigt et le capteur. Des essais faits dans le cadre de l'invention, ont démontré que pour une empreinte à identifier, qui se compose de 4500 points d'information (contact ou absence de contact, c'est-à-dire un codage numérique), il suffit que l'ensemble témoin $' se limite à 2700 points répartis comme indiqué ci-dessus, en 45 colonnes et 60 lignes pour permettre une reconnaissance; l'intér8t du capteur ayant des dimensions plus grandes que l'empreinte témoin est de faciliter la mise en place du doigt, sans nécessiter un centrage trop précis. Bien entendu, l'invention n'zest pas limitée à l'exemple de réalisation ci-dessus décrit et représenté, à partir duquel on pourra prévoir d'autres formes et d'autres modes de réalisation, sans pour cela sortir du cadre de l'invention. REVENDICATIONS 1.- Procédé de comparaison et d'analyse d'informations pour vérifier si une information correspond à une information enregistrée dans une mémoire, procédé caractérisé en ce qu'on répartit l'ensemble des informations (E) suivant une matrice de lignes 1 et de colonnes cn, chaque point de la matrice corres n n pondant au codage binaire d'une information (codage par deux états), on répartit l'ensemble E' d'informations témoin dans une matrice de colonne kN, et de lignes DM, on choisit une tranche DXr Dx + y correspondant à une largeur de y lignes dans la matrice témoin El et on compare cette tranche à des surfaces S m,n de meme longueur et de même largeur de la matrice E, on compare ligne par ligne les deux surfaces pour vérifier l'identité ou l'absence d'identité entre les points correspondants de chaque ligne, on totalise la somme des points identiques de chaque ligne, on retient une ligne pour bonne, si le total des points identiques dépasse un seuil S1 prédéterminé, puis on totalise le nombre de lignes ayant satisfait à ce premier seuil S1J on ne retient la surface Sm,n que si le total de lignes retenues dépasse un second seuil S2, prédéterminé, on associe dans l'affirmative le total des lignes retenues à la surface S , on déplace la sur m,n face Sm,n d'une ligne ou d'une colonne de façon à couvrir tout m, n ou partie de la matrice d'informations E et-on retient la surfa ce S dont le nombre associé est le plus grand, puis on modifie m,n les coordonnées de la matrice d'informations E de façon que les coordonnées de la surface Sm,n ainsi retenues correspondent aux coordonnées de la bande (Dx, Dx + y) et on recommence une compa x+y raison ligne par ligne de toute la matrice d'informations E' avec toutes les lignes communes de la matrice d'informations E, pour vérifier l'identité entre les deux ensembles d'informations E, E', alors que s'il n'y a aucune surface Sm,n ayant satisfait au second seuil S2, on rejette l'ensemble d'informations E sans procéder au balayage ligne par ligne. 2.- Procédé de comparaison et d'analyse selon la revendication 1, caractérisé en ce que pour comparer la bande Dx, D + y à la matrice des informations E, on choisit une première x+y surface 5m,l dont la première colonne coïncide avec la première colonne de la matrice des informations E, puis on choisit une seconde surface 5m,2 dont la première colonne correspond à la seconde colonne c2 de la matrice de l'ensemble E et on poursuit le décalage en restant limité entre les lignes LM et LM + y puis après épuisement de la surface de la matrice comprise entre les lignes LM et LM + Y' on choisit une nouvelle zone LM + 1' LM + Y + 1 dans laquelle on choisit une surface S m +1,1 que l'on compare de nouveau à la bande Dx, Dx + y puis on choisit la sur face S + 1,2 ... jusqu'à épuisement de la zone comprise entre m + 1,2 les lignes LM + 1 et 9 + Y + 1 puis on choisit une nouvelle zone LM + 2' LM + Y + 2 3.- Installation pour la mise en oeuvre du procédé selon l'une quelconque des revendications I et 2, caractérisée en ce qu'elle se compose d'un capteur recevant l'ensemble d'infor- mations E, et on introduit ces informations dans une mémoire, une seconde mémoire contenant les informations de l'ensemble témoin E', un comparateur balayant la mémoire des informations E et des informations E' et appliquant ces signaux à un comparateur, une mémoire pour totaliser les résultats de la comparaison et une unité de calcul et de comparaison pour totaliser les coincidences ligne par ligne, et retenir les lignes suivant qu'elles satisfassent au seuil Slr puis la somme des lignes de chaque surface Sm n lorsque cette somme dépasse un seuil S2 donné, et enfin un sélecteur pour retcnir la surface Sm,n associée à la plus grande valeur.