SE524055C2

SE524055C2 - Identifying fingerprints by comparing a partial reference area of known stored fingerprints with successive partial areas of an unknown print until a likeness is found

Info

Publication number: SE524055C2
Application number: SE0103738A
Authority: SE
Inventors: Jonas Nilsson
Original assignee: Precise Biometrics Ab
Priority date: 2001-11-12
Filing date: 2001-11-12
Publication date: 2004-06-22
Also published as: SE0103738D0; SE0103738L

Abstract

Reference partial areas from known stored prints are compared with slightly larger current partial areas in different positions in an unknown print until a match is found. The comparison begins with a reference partial area centered on the current unknown partial area and the reference area is moved in a spiral towards the edge of the current area. When a thresholded match is found a likeness is assumed and another partial area of the print is examined. His is repeated until a given number of partial areas are matched when identification is assumed. An Independent claim is included for a device for identifying a fingerprint.

Description

20 25 30 35 524 055 2 när personen vill göra en ekonomisk transaktion eller när personen vill ha tillgång till känslig information. 20 25 30 35 524 055 2 when the person wants to make a financial transaction or when the person wants access to sensitive information.

För att undvika bedrägerier är det viktigt att refe- rensfingeravtrycket lagras på ett säkert sätt och att jämförelsen mellan det aktuella fingeravtrycket och refe- rensfingeravtrycket sker på ett sådant sätt att finger- avtrycksinformationen inte blir tillgänglig för obehö- riga. Ett känt sätt att uppnå detta är att lagra refe- rensfingeravtrycket på ett personligt aktivt kort, ett sk smart card, eller på någon annan typ av personlig por- tabel databärare som innehåller en processor och att genomföra jämförelsen mellan det aktuella fingeravtrycket och referensfingeravtrycket på smart cardet eller data- bäraren.To avoid fraud, it is important that the reference fingerprint is stored securely and that the comparison between the current fingerprint and the reference fingerprint takes place in such a way that the fingerprint information does not become accessible to unauthorized persons. A known way to achieve this is to store the reference fingerprint on a personally active card, a so-called smart card, or on some other type of personal portable data carrier that contains a processor and to perform the comparison between the current fingerprint and the reference fingerprint on a smart card. the card or data carrier.

Ett fingeravtryck innehåller tämligen mycket infor- mation. Normalt lagras och jämförs därför inte fullstän- diga fingeravtryck utan bara speciellt intressant infor- mation som har extraherats från fingeravtrycken. En mycket vanlig teknik är att extrahera sk features (även kallade minutia points) ur fingeravtrycket. Features är normalt punkter i fingeravtrycket där fingeravtrycks- linjerna delar sig eller slutar. Andra typer av features kan också förekomma. Istället för ett fullständigt refe- rensfingeravtryck lagras en ”karta” över var features förekommer, eventuellt kompletterad med en indikation på typen av feature. Vid verifieringen extraheras features från det aktuella fingeravtrycket och jämförs med refe- rensfeaturedatana för att kontrollera om features före- kommer på samma ställen i fingeravtrycken.A fingerprint contains quite a lot of information. Normally, complete fingerprints are not stored and compared, but only particularly interesting information that has been extracted from the fingerprints. A very common technique is to extract so-called features (also called minutia points) from the fingerprint. Features are normally points in the fingerprint where the fingerprint lines split or end. Other types of features may also be present. Instead of a complete reference fingerprint, a “map” of where features occur is stored, possibly supplemented with an indication of the type of feature. During verification, features are extracted from the current fingerprint and compared with the reference feature data to check if features appear in the same places in the fingerprints.

En annan känd teknik består i att utnyttja hela delområden av fingeravtrycket istället för bara enskilda punkter i detta. Vid verifieringen jämförs delområdena av referensfingeravtrycket med motsvarande delområden av det aktuella fingeravtrycket. Föreliggande uppfinning handlar om fingeravtryckskontroll som utnyttjar delområden.Another known technique is to use entire sub-areas of the fingerprint instead of just individual points in it. During the verification, the sub-areas of the reference fingerprint are compared with the corresponding sub-areas of the current fingerprint. The present invention relates to fingerprint control utilizing sub-areas.

Ett problem i samband med användning av delområden är att personen vars identitet skall verifieras ofta inte 10 15 20 25 30 35 524 055 3 placerar fingret i samma position på sensorn när det aktuella fingeravtrycket registreras som när referens- fingeravtrycket registrerades. Detta problem kan lösas genom att man jämför varje delområde av referensfinger- avtrycket med varje tänkbart delområde med samma storlek inom det aktuella fingeravtrycket. En sådan jämförelse tar emellertid alldeles för lång tid att utföra på ett smart card som normalt har en processor med tämligen låg prestanda.A problem in connection with the use of sub-areas is that the person whose identity is to be verified often does not place the finger in the same position on the sensor when the current fingerprint is registered as when the reference fingerprint was registered. This problem can be solved by comparing each sub-area of the reference fingerprint with each conceivable sub-area of the same size within the current fingerprint. However, such a comparison takes far too long to perform on a smart card that normally has a processor with rather low performance.

En lösning på detta problem beskrivs i SE 0001576-8, som är överlåten till föreliggande sökande. Lösningen består i att man överför ett referensdelområde från smart cardet på vilket referensdelområdena är lagrade till en dator med bättre processorprestanda. Datorn jämför refe- rensdelområdet med det aktuella fingeravtrycket för att bestämma om och i så fall i vilken translations- och vridningsposition referensdelområdet matchar det aktuella fingeravtrycket. När denna position har bestämts vet datorn hur det aktuella fingeravtrycket är translaterat och vridet i förhållande till referensfingeravtrycket.A solution to this problem is described in SE 0001576-8, which is assigned to the present applicant. The solution is to transfer a reference sub-area from the smart card on which the reference sub-areas are stored to a computer with better processor performance. The computer compares the reference sub-area with the current fingerprint to determine if and in which case in which translation and rotation position the reference sub-area matches the current fingerprint. Once this position has been determined, the computer knows how the current fingerprint is translated and rotated relative to the reference fingerprint.

Med kännedom om hur övriga delområden i referensfinger- avtrycket är placerade i förhållande till det matchande delomràdet kan datorn välja ut motsvarande delområden i det aktuella fingeravtrycket och överföra dessa till smart cardet. För att kompensera för att personen kan ha tryckt fingret olika hårt mot sensorn vid registrering av det aktuella fingeravtrycket och referensfingeravtrycket och därmed kan ha deformerat fingeravtrycket olika mycket väljs de aktuella delområdena till att vara något större än delområdena i referensfingeravtrycket. På smart cardet kan nu den slutliga jämförelsen mellan delområdena göras i ett fåtal inbördes lägen och därför kan jämförelsen göras på rimlig tid trots låg prestanda hos smart cardets processor.With knowledge of how the other sub-areas in the reference fingerprint are located in relation to the matching sub-area, the computer can select the corresponding sub-areas in the current fingerprint and transfer these to the smart card. To compensate for the fact that the person may have pressed the finger differently hard against the sensor when registering the current fingerprint and the reference fingerprint and thus may have deformed the fingerprint differently, the relevant sub-areas are selected to be slightly larger than the sub-areas in the reference fingerprint. On the smart card, the final comparison between the sub-areas can now be made in a few mutual situations and therefore the comparison can be made in a reasonable time despite the low performance of the smart card's processor.

Närmare bestämt jämförs varje referensdelområde med motsvarande aktuella delområden i alla tänkbara inbördes lägen där referensdelområdet överlappar det aktuella ZíEÛLI-“fšlï-Bl 0922:? (E:KFatVïšfïxšëšfSïlOiÅšl\2f}12C69__SE_4P3ZÜÜI-Gü-»ÉTY 1.02 (71 ( 1. 10 15 20 25 30 35 524 055 4 delområdet fullständigt. Jämförelsen görs exempelvis från det övre vänstra hörnet rad för rad ner till det nedre högra hörnet. För varje inbördes läge bestäms hur väl referensdelområdet överensstämmer med den del av det aktuella delområdet som det överlappar. Resultatet kan exempelvis erhållas som en poängsumma som avspeglar an- talet överlappande bildpunkter som är lika. När delområ- dena har jämförts i alla inbördes lägen kontrolleras om den högsta poängsumman överstiger ett tröskelvärde. I så fall anses referensdelområdet matcha det aktuella del- området. Samtliga referensdelomràden matchas mot sina respektive aktuella delområden på detta vis och antalet matchande delområden bestäms. Slutligen jämförs antalet matchande delområden med ett tröskelvärde. Om detta upp- nås anses det aktuella fingeravtrycket komma från samma person som referensfingeravrycket och identiteten för den person från vilken det aktuella fingeravtrycket registre- rades anses verifierad.More specifically, each reference sub-area is compared with the corresponding current sub-areas in all conceivable mutual positions where the reference sub-area overlaps the current ZíEÛLI- “fšlï-Bl 0922 :? (E: KFatVïšfïxšëšfSïlOiÅšl \ 2f} 12C69__EN_4P3ZÜÜI-Gü- »ÉTY 1.02 (71 (1. 10 15 20 25 30 35 524 055 4 sub-area complete. The comparison is made, for example, from the upper left corner row by row down to the lower right corner. each mutual position determines how well the reference sub-area corresponds to the part of the current sub-area that it overlaps.The result can be obtained as a score that reflects the number of overlapping pixels that are equal. the highest score exceeds a threshold, in which case the reference sub-area is considered to match the current sub-area. All reference sub-areas are matched to their respective current sub-areas in this way and the number of matching sub-areas is determined. the current fingerprint comes from the same person as the reference fingerprint and the identity of the person from n which the current fingerprint was registered is considered verified.

Ovan beskrivna förfarande har implementerats med gott resultat på smart card som direktexekverar program- koden på smart cardet. Det finns emellertid andra typer av smart cards, exempelvis sk JAVA-kort och Multos-kort på vilka processorn före exekveringen tolkar och omvand- lar programkoden till den form i vilken den skall exek- veras. Sådana kort är långsammare än korten som direkt- exekverar programkoden och även med ovan beskrivna för- farande tar det alltför lång tid att utföra jämförelsen mellan referensfingeravtrycket och det aktuella finger- avtrycket. Sökanden har försökt att lösa detta problem genom att minska förhållandet mellan storleken på de aktuella delområdena och storleken på referensdelomrà- dena. Detta har dock inte lett till en acceptabel behand- lingstid. Pga av ovannämnda deformation går det nämligen inte att göra storleksförhållandet alltför litet för då kommer verifieringen att misslyckas för alltför många av de personer för vilka den borde lyckas. Andelen felaktiga f L t.. iÄÉ F, f, 10 15 20 25 30 35 524 055 5 avvisanden (FRR = False Rejection Rate) blir alltså för hög.The procedure described above has been implemented with good results on smart cards that directly execute the program code on the smart card. However, there are other types of smart cards, such as so-called JAVA cards and Multos cards on which the processor interprets and converts the program code to the form in which it is to be executed before execution. Such cards are slower than the cards that directly execute the program code and even with the procedure described above, it takes too long to perform the comparison between the reference fingerprint and the current fingerprint. The applicant has sought to solve this problem by reducing the ratio between the size of the sub-areas concerned and the size of the reference sub-areas. However, this has not led to an acceptable treatment time. Due to the above-mentioned deformation, it is not possible to make the size ratio too small because then the verification will fail for too many of the people for whom it should succeed. The proportion of incorrect f L t .. iÄÉ F, f, 10 15 20 25 30 35 524 055 5 rejection (FRR = False Rejection Rate) thus becomes too high.

Sammanfattning av uppfinningen Ett allmänt ändamål med föreliggande uppfinning är därför att helt eller delvis avhjälpa ovanstående pro- blem.Summary of the Invention A general object of the present invention is therefore to fully or partially remedy the above problems.

Ett mera speciellt ändamål är att anvisa ett sätt att jämföra referensdelomràden med aktuella delområden på ett snabbare sätt än vad som beskrivits ovan.A more special purpose is to provide a way to compare reference sub-areas with current sub-areas in a faster way than described above.

Dessa och andra ändamål som kommer att framgå från följande beskrivning uppnås med ett förfarande och en anordning enligt de efterföljande patentkraven.These and other objects which will become apparent from the following description are achieved by a method and an apparatus according to the appended claims.

Enligt en första aspekt av uppfinningen avser denna sålunda ett förfarande för kontroll av om ett aktuellt fingeravtryck tillhör en person för vilken referens- fingeravtrycksdata tidigare lagrats, vilka referens- fingeravtrycksdata innefattar ett flertal delområden, som betecknas referensdelomràden, av en digital represen- tation av personens fingeravtryck, vid vilket förfarande åtminstone vissa av referensdelområdena jämförs med mot- svarande aktuella delområden av en digital representation av det aktuella fingeravtrycket, vilka aktuella delom- råden är större än referensdelområdena, för att kont- rollera deras likhet. Förfarandet innefattar stegen att jämföra ett av referensdelområdena med ett av de aktuella delområdena i olika inbördes lägen tills ett inbördes läge påträffas för vilket ett första förutbestämt krav på likhet mellan referensdelområdet och det aktuella delom- ràdet är uppfyllt; att när detta inbördes läge påträffas registrera att referensdelområdet matchar det första aktuella delomràdet; och att avbryta jämförelsen av refe- rensdelområdet och det aktuella delområdet.According to a first aspect of the invention, it thus relates to a method for checking whether a current fingerprint belongs to a person for whom reference fingerprint data has previously been stored, which reference fingerprint data comprises a plurality of sub-areas, referred to as reference sub-areas, by a digital representation of the person fingerprint, in which method at least some of the reference sub-areas are compared with the corresponding current sub-areas of a digital representation of the current fingerprint, which sub-areas are larger than the reference sub-areas, in order to check their similarity. The method comprises the steps of comparing one of the reference sub-areas with one of the relevant sub-areas in different mutual positions until a mutual position is found for which a first predetermined requirement for similarity between the reference sub-area and the relevant sub-area is met; that when this mutual position is encountered, register that the reference sub-area matches the first current sub-area; and to interrupt the comparison of the reference sub-area and the relevant sub-area.

Tidigare gjordes alltså en uttömmande jämförelse mellan referensdelområdet och det aktuella delomràdet för att bestämma i vilket inbördes läge referensdelområdet bäst överensstämde med det aktuella delområdet. Därefter kontrollerades om ett förutbestämt krav på likhet var Z-'Jíl-”š-(ÉÉ--Bl 093127 G:\FI¿iLIxCÉ-{XANEY=.2C-Zi“äZÛlZÛêÉï SE {E*}2='}ÛÃ}p-ÛL~3-I"ï iLlZzLdc-'I 10 15 20 25 30 35 i 524 055 6 uppfyllt. Enligt uppfinningen gör man inte någon uttöm- mande jämförelse utan istället avbryter man jämförelsen så snart ett inbördes läge påträffas i vilket det förut- bestämda kravet på likhet är uppfyllt. Det kan alltså finnas andra inbördes lägen i vilka likheten är större, men detta bortses ifrån eftersom kravet på likhet redan är uppfyllt. På detta sätt kommer i genomsnitt betydligt färre jämförelser behöva göras mellan referensområdet och det aktuella området. Endast i det fall då inget inbördes läge påträffas i vilket likhetskravet är uppfyllt behöver samtliga inbördes lägen jämföras. Resultatet blir en väsentlig tidsbesparing.Previously, an exhaustive comparison was thus made between the reference sub-area and the relevant sub-area in order to determine in which mutual position the reference sub-area best corresponded to the relevant sub-area. It was then checked whether a predetermined requirement of equality was Z-'Jíl- "š- (ÉÉ - Bl 093127 G: \ FI¿iLIxCÉ- {XANEY = .2C-Zi“ äZÛlZÛêÉï SE {E *} 2 = '} ÛÃ} p-ÛL ~ 3-I "ï iLlZzLdc-'I 10 15 20 25 30 35 i 524 055 6 fulfilled. According to the invention, no exhaustive comparison is made but instead the comparison is interrupted as soon as a mutual position is found in which it was previously - the specific requirement of similarity is met, so there may be other mutual situations in which the similarity is greater, but this is disregarded as the requirement of similarity is already met. Only in the case where no mutual position is found in which the equality requirement is met, all mutual positions need to be compared, the result being a significant time saving.

En ytterligare tidsbesparing kan erhållas genom att jämförelsen påbörjas i det inbördes läge där det är san- nolikast att det första förutbestämda kravet på likhet är uppfyllt. Överhuvudtaget bör jämförelsen utföras i ”san- nolikhetsordning” för att så få olika inbördes lägen som möjligt skall behöva jämföras.An additional time saving can be obtained by starting the comparison in the mutual position where it is most probable that the first predetermined requirement for equality is met. In general, the comparison should be performed in “probability order” so that as few different mutual positions as possible need to be compared.

Såsom nämnts är de aktuella delområdena större än referensdelområdena. De aktuella delområdena väljs lämp- ligen så att de är symmetriska i förhållande till de om- råden som motsvarar referensdelområdena i det aktuella fingeravtrycket. Då bör jämförelsen utföras för inbördes lägen där referensdelområdet befinner sig nära mitten av det aktuella delområdet före inbördes lägen där referens- delområdet befinner sig vid det aktuella delområdets kanter. Det har nämligen visat sig att användaren oftare inte deformerar fingret än deformerar det. Därmed kommer ett inbördes läge i vilket likhetskravet är uppfyllt i genomsnitt påträffas snabbare om sökningen påbörjas med referensdelområdet placerat i positioner nära mitten av det aktuella delområdet. Naturligtvis kommer matchnings- hastigheten inte påverkas i alltför stor utsträckning om matchningen påbörjas med en enstaka jämförelse vid det aktuella delområdets kant. Det väsentliga är att jämför- elserna med referensdelområdet i närheten av det aktuella Zïšíšlp-Oš-'šl Oš:l'7 G:'\RatÅClíXâIJS\_200l\Zï:l2íJ6fš__wSE_(På2351-33-27 lÜf/fkLdofI 10 l5 20 25 30 35 f 524 055 7 delområdets mittpunkt görs på ett så tidigt stadium som möjligt.As mentioned, the relevant sub-areas are larger than the reference sub-areas. The relevant sub-areas are suitably selected so that they are symmetrical in relation to the areas that correspond to the reference sub-areas in the current fingerprint. Then the comparison should be performed for mutual positions where the reference sub-area is located near the middle of the relevant sub-area before mutual positions where the reference sub-area is located at the edges of the relevant sub-area. Namely, it has been found that the user more often does not deform the finger than deforms it. Thus, a mutual position in which the similarity requirement is met will on average be found more quickly if the search is started with the reference sub-area placed in positions close to the middle of the relevant sub-area. Of course, the matching speed will not be affected to an excessive extent if the matching is started with a single comparison at the edge of the relevant sub-area. The important thing is that the comparisons with the reference sub-area in the vicinity of the current Zïšíšlp-Oš-'šl Oš: l'7 G: '\ RatÅClíXâIJS \ _200l \ Zï: l2íJ6fš__wSE_ (På2351-33-27 lÜf / fkLdofI 10 l5 20 35 f 524 055 7 the midpoint of the subarea is made at as early a stage as possible.

Allra snabbast blir det troligen om jämförelsen på- börjas med referensdelområdet centrerat i förhållande till det aktuella delområdet och den fortsätter med ändrade inbördes lägen där referensområdet är så centre- rat som möjligt i förhållande till det aktuella området.It will probably be fastest if the comparison is started with the reference sub-area centered in relation to the relevant sub-area and it continues with changed mutual positions where the reference area is as centered as possible in relation to the relevant area.

En jämförelse som utförs i spiralform har visat sig lämp- lig och uppfyller ovannämnda kriterium.A comparison performed in a spiral form has proved appropriate and meets the above criteria.

När ett första referensdelområde har jämförts med ett första aktuellt område fortsätter kontrollen lämp- ligen med ett nytt referensdelområde och motsvarande aktuella delområde. Efter varje par av ett referensdel- område och ett aktuellt delområde kontrolleras om ett förutbestämt antal referensdelområden som matchar sina respektive aktuella delområden har registrerats. Om så är fallet avbryts kontrollen för då anses den kontrollerade personens identitet vara verifierad.When a first reference sub-area has been compared with a first relevant area, the control suitably continues with a new reference sub-area and the corresponding current sub-area. After each pair of a reference sub-area and a current sub-area, it is checked whether a predetermined number of reference sub-areas that match their respective current sub-areas have been registered. If this is the case, the check is canceled because then the identity of the checked person is considered verified.

Referensdelområdena kan med fördel jämföras med de aktuella delområdena i två faser, varvid den andra fasen endast utförs om jämförelsen av referensdelområdena med de aktuella delområdena i den första fasen indikerar att det aktuella fingeravtrycket tillhör samma person som referensfingeravtrycksdatana.The reference sub-areas can advantageously be compared with the relevant sub-areas in two phases, the second phase only being performed if the comparison of the reference sub-areas with the relevant sub-areas in the first phase indicates that the current fingerprint belongs to the same person as the reference fingerprint data.

Jämförelsen i två faser kan göras på så sätt att vid varje jämförelse av ett referensdelområde och ett aktu- ellt delområde utförs först den första fasen och sen, i förekommande fall den andra fasen. Alternativt kan först den första fasen utföras för alla delområdena och där- efter i förekommande fall den andra fasen.The comparison in two phases can be made in such a way that in each comparison of a reference sub-area and a current sub-area, the first phase is performed first and then, where applicable, the second phase. Alternatively, first the first phase can be performed for all sub-areas and then, if applicable, the second phase.

Syftet med den första fasen är att snabbt kunna avvisa aktuella delområden eller fingeravtryck som har mycket liten likhet med referensfingeravtrycksdatana.The purpose of the first phase is to be able to quickly reject current sub-areas or fingerprints that have very little resemblance to the reference fingerprint data.

Snabbheten uppnås genom att jämförelsen i den första fasen utförs med hjälp av endast ett subområde av varje jämfört referensdelområde, medan då jämförelsen i den andra fasen utförs för hela referensdelområden. Genom att ZGOLÉ G3- 31 O-*š-:IT G:\PatïJ2H\Aï~I§}\2Üíšrïjlülåïüñ? SE {Pl2-'JOl-Q9-I.É"7 LÉ,.Û28.dcf; 10 15 20 25 30 35 524 055 8 man redan under den första fasen kan avvisa sådana delom- råden eller fingeravtryck för vilka varje referensdelom- råde behöver jämföras med motsvarande aktuella delområde i alla inbördes lägen pga av bristande likhet sparas mycket tid i den andra fasen som i sig själv är mer tids- krävande än den första.The speed is achieved by performing the comparison in the first phase by means of only one sub-area of each compared reference sub-area, while then the comparison in the second phase is performed for entire reference sub-areas. By ZGOLÉ G3- 31 O- * š-: IT G: \ PatïJ2H \ Aï ~ I§} \ 2Üíšrïjlülåïüñ? SE {P12-'JO1-Q9-I.É "7 LÉ, .Û28.dcf; 10 15 20 25 30 35 524 055 8 one can already during the first phase reject such sub-areas or fingerprints for which each reference sub-area need to be compared with the corresponding current sub-area in all mutual situations due to lack of similarity, a lot of time is saved in the second phase, which in itself is more time-consuming than the first.

Jämförelsen i den första fasen kan utföras på samma sätt som beskrivits ovan för den andra fasen. Sålunda kan exempelvis jämförelsen mellan referensdelområden och aktuella delområden utföras i spiralform och kan jämför- elsen mellan ett referensdelområde och ett aktuellt del- område avbrytas direkt när ett första förutbestämt krav på likhet är uppnått. Det första förutbestämda kravet på likhet kan dock vara lägre än i den andra fasen för att FRR.n skall hållas låg. Som ett exempel kan nämnas att likhetskravet i den första fasen kan vara att ca 60% av de överlappande bildpunkterna skall överensstämma, medan likhetskravet i den andra fasen kan vara att ca 70% av de överlappande bildpunkterna skall överensstämma.The comparison in the first phase can be performed in the same way as described above for the second phase. Thus, for example, the comparison between reference sub-areas and current sub-areas can be performed in a spiral form and the comparison between a reference sub-area and a current sub-area can be interrupted immediately when a first predetermined requirement for similarity has been achieved. However, the first predetermined requirement for similarity may be lower than in the second phase in order to keep the FRR low. As an example, the similarity requirement in the first phase may be that about 60% of the overlapping pixels must match, while the similarity requirement in the second phase may be that about 70% of the overlapping pixels must match.

Om den första fasen utförs för hela fingeravtrycket hela kontrollen i den första fasen avbrytas så snart ett till- innan den andra fasen eventuellt utförs kan vidare räckligt antal matchande referensdelområden har registre- rats.If the first phase is performed for the entire fingerprint, the entire check in the first phase is interrupted as soon as one before the second phase is possibly performed, a sufficient number of matching reference sub-areas may have been registered.

Ovan beskrivna förfarande kan realiseras med hjälp av en processor och ett datorprogram. Det kan naturligt- vis också realiseras med en specialanpassad hårdvara, såsom en ASIC (Application Specific Integrated Circuit) eller en FPGA (Field Programmable Gate Array) eller med någon lämplig kombination av analoga och/eller digitala kretsar.The procedure described above can be realized with the aid of a processor and a computer program. Of course, it can also be realized with a specially adapted hardware, such as an ASIC (Application Specific Integrated Circuit) or an FPGA (Field Programmable Gate Array) or with any suitable combination of analog and / or digital circuits.

I Datorprogrammet kan lagras och/eller distribueras på ett minnesmedium, som kan vara vilket som helst kommer- siellt minnesmedium, såsom ett ROM, ett RAM, ett optiskt skivminne, ett magnetisk minne, eller en propagerande signal.The computer program may be stored and / or distributed on a memory medium, which may be any commercial memory medium, such as a ROM, a RAM, an optical disk memory, a magnetic memory, or a propagating signal.

G: "«,Pat“~»_f'JE~'l'\Aï~I5\2ÜlÉÅXZÜl2Ü%iï___5E__{P} 2051 -029127 1028 .ziotï 10 15 20 25 30 35 524 055 9 Det skall nämnas att när det ovan beskrivna förfa- randet implementerades på ett Java-kort istället för det tidigare kända förfarandet kunde behandlingstiden redu- ceras med en tio-potens.G: "«, Pat “~» _f'JE ~ 'l' \ Aï ~ I5 \ 2ÜlÉÅXZÜl2Ü% iï ___ 5E __ {P} 2051 -029127 1028 .ziotï 10 15 20 25 30 35 524 055 9 It should be mentioned that when the above described the procedure was implemented on a Java card instead of the previously known procedure, the processing time could be reduced by a ten-power.

Enligt en andra aspekt av uppfinningen avser denna en anordning för kontroll av om ett aktuellt fingerav- tryck tillhör en person för vilken referensfingerav- trycksdata tidigare lagrats, vilken anordning innefattar ett minne som lagrar referensfingeravtrycksdatana i form av delområden, som betecknas referensdelområden, av en digital representation av personens fingeravtryck; och en signalbehandlingsenhet som är anordnad att jämföra åt- minstone vissa av referensdelområdena med motsvarande aktuella delområden av en digital representation av det aktuella fingeravtrycket, vilka aktuella delområden är större än referensdelområdena, för att kontrollera deras likhet. Signalbehandlingsenheten är vidare anordnad att jämföra ett av referensdelområdena med ett av de aktuella delområdena i olika inbördes lägen tills ett inbördes läge påträffas för vilket ett första förutbestämt krav på likhet mellan referensdelomràdet och det aktuella delom- rådet är uppfyllt; att när detta inbördes läge påträffas registrera att referensdelomràdet matchar det första aktuella delområdet; och att avbryta jämförelsen av refe- rendelomràdet och det aktuella delomràdet.According to a second aspect of the invention, it relates to a device for checking whether a current fingerprint belongs to a person for whom reference fingerprint data has previously been stored, which device comprises a memory which stores the reference fingerprint data in the form of sub-areas, referred to as reference sub-areas, of a digital representation of the person's fingerprints; and a signal processing unit arranged to compare at least some of the reference sub-areas with the corresponding current sub-areas of a digital representation of the current fingerprint, which current sub-areas are larger than the reference sub-areas, in order to check their similarity. The signal processing unit is further arranged to compare one of the reference sub-areas with one of the relevant sub-areas in different mutual positions until a mutual position is found for which a first predetermined requirement for similarity between the reference sub-area and the relevant sub-area is met; that when this mutual position is found, register that the reference sub-area matches the first current sub-area; and to interrupt the comparison of the reference sub-area and the relevant sub-area.

Anordningen kan vara vilken som helst anordning där det finns behov av en snabb jämförelse mellan referens- delområden och aktuella delområden. Den kan vara en por- tabel databärare av något slag, exempelvis en mobiltele- fon eller en PDA. Den kan vidare vara ett smart card och i synnerhet ett smart card, där processorn tolkar pro- gramkoden innan den exekveras, exempelvis ett smart card av Java-typ.The device can be any device where there is a need for a quick comparison between reference sub-areas and current sub-areas. It can be a portable data carrier of some kind, for example a mobile phone or a PDA. It can also be a smart card and in particular a smart card, where the processor interprets the program code before it is executed, for example a smart card of the Java type.

Kortfattad beskrivning av ritningarna j Föreliggande uppfinning skall nu beskrivas närmare i detalj genom ett utföringsexempel under hänvisning till bifogade ritningar, på vilka 10 15 20 25 30 35 ' 524 055 10 Fig 1 visar schematiskt ett system i vilket före- liggande uppfinning kan implementeras; Fig 2 a och b visar schematiskt ett referensfinger- avtryck och ett aktuellt fingeravtryck med markerade del- områden; Fig 3 visar schematiskt hur ett referensdelområde kan jämföras med ett aktuell delomràde; Fig 4 är ett flödesschema och visar hur ett refe- rensdelområde kan jämföras med ett aktuell delomràde i två faser; Fig 5 är ett flödesschema och visar ett exempel på en fullständig fingeravtryckskontroll som utförs utan förkontroll.Brief Description of the Drawings The present invention will now be described in more detail by way of an exemplary embodiment with reference to the accompanying drawings, in which Fig. 1 schematically shows a system in which the present invention may be implemented; Figures 2 a and b schematically show a reference fingerprint and a current fingerprint with marked sub-areas; Fig. 3 schematically shows how a reference sub-area can be compared with a current sub-area; Fig. 4 is a flow chart showing how a reference subarea can be compared to a current subarea in two phases; Fig. 5 is a flow chart showing an example of a complete fingerprint check performed without pre-check.

Beskrivning av ett detaljerat utföringsexempel I fig l visas ett system för kontroll av fingerav- tryck. Systemet innefattar en fingeravtryckssensor 1, en datorenhet 2, en smartcardläsare 3 och ett smart card 4.Description of a detailed embodiment Fig. 1 shows a system for checking fingerprints. The system comprises a fingerprint sensor 1, a computer unit 2, a smart card reader 3 and a smart card 4.

Sensorn l kan, men behöver inte, användas både för registrering av referensfingeravtryck och för registre- ring av aktuella fingeravtryck. Den kan vara optisk, kapacitiv, termisk eller av någon annan lämplig typ. Den kan vara en areasensor eller en linjesensor. Den kan vidare vara fristående eller integrerad med datorenheten 2 eller smartcardläsaren 3 eller smart cardet 4.Sensor l can, but does not need, be used both for registration of reference fingerprints and for registration of current fingerprints. It can be optical, capacitive, thermal or of any other suitable type. It can be an area sensor or a line sensor. It can furthermore be stand-alone or integrated with the computer unit 2 or the smart card reader 3 or the smart card 4.

Datorenheten 2 kan vara en vanlig generell dator, exempelvis en PC. Alternativt kan den vara en datorenhet 2 som är specialanpassad för denna tillämpning.The computer unit 2 can be an ordinary general computer, for example a PC. Alternatively, it may be a computer unit 2 which is specially adapted for this application.

Smartcard-läsaren 3 kan vara vilken som helst kom- mersiellt tillgänglig smartcardläsare. Alternativt kan den vara en specialanpassad smartcardläsare. Den kan vara en fristående enhet eller integrerad med datorenheten 2.The smart card reader 3 can be any commercially available smart card reader. Alternatively, it can be a custom smart card reader. It can be a stand-alone device or integrated with the computer device 2.

Smart cardet 4 kan vara vilken som helst typ av smart card på vilket en jämförelse av fingeravtrycksdata skall utföras. Smart cardet har en signalbehandlingsenhet som innefattar en processor 6, ett minne 7 för lagring av referensfingeravtrycksdata, som är extraherade från ett referensfingeravtryck från smartcardinnehavaren, och ett 2ÜC§"0§~šl Qﬁtfï .få n äCaCKÜHïáHS=2ÜÜiÉ2ll2Ûcü Én â:}ZÛJ*-G9-“Ü lﬁ78.dOI 10 15 20 25 30 35 r 524 055 ll arbetsminne 8, samt kommunikationskretsar 9 som möjliggör kommunikation mellan smartcardläsaren 3 och smart cardet 4. Kommunikationskretsarna 9 kan, men behöver inte, kräva kontakt mellan smart cardet och läsaren.The smart card 4 can be any type of smart card on which a comparison of fingerprint data is to be performed. The smart card has a signal processing unit comprising a processor 6, a memory 7 for storing reference fingerprint data, which is extracted from a reference fingerprint of the smart card holder, and a 2ÜC§ "0§ ~ šl Q ﬁ tfï. -G9- “Ü l ﬁ78. DOI 10 15 20 25 30 35 r 524 055 ll working memory 8, and communication circuits 9 that enable communication between the smart card reader 3 and the smart card 4. The communication circuits 9 may, but need not, require contact between the smart card and the reader. .

Systemet kan i korthet fungera på följande sätt när smartcardinnehavarens identitet skall verifieras. Smart- cardinnehavaren placerar sitt smart card 4 i smartcard- läsaren 3 och sitt finger F, som i fig 1 är visat med streckade linjer, på fingeravtrycksensorn l, som regi- strerar en aktuell digital bild av fingret. Via smart- cardläsaren 3 läser datorenheten 2 en publik del av refe- rensfingeravtrycksdatana från smart cardet. Med hjälp av denna publika del av datana fastställer datorn hur den aktuella bilden är roterad och translaterad i förhållande till referensfingeravtrycksdatana. Vidare plockar den ut aktuella delområden av den aktuella bilden av fingerav- trycket. Dessa aktuella delområden avbildar väsentligen samma delar av fingeravtrycket som referensdelområden som är lagrade på smart cardet som del av referensfingerav- trycksdatana och som aldrig lämnar detta. De aktuella delområdena är något större än referensdelomràdena för att kompensera för att fingret kan ha tryckts hårdare mot sensorn vid registreringen av den aktuella bilden än vid registreringen av referensfingeravtrycket. Som ett exem- pel kan nämnas att referensdelomràdena kan vara 24 * 24 bildpunkter, medan de aktuella delområdena kan vara 30 * 32 bildpunkter.In short, the system can work in the following way when the identity of the smart card holder is to be verified. The smart card holder places his smart card 4 in the smart card reader 3 and his finger F, which is shown in broken lines in Fig. 1, on the fingerprint sensor 1, which registers a current digital image of the finger. Via the smart card reader 3, the computer unit 2 reads a public part of the reference fingerprint data from the smart card. With the help of this public part of the data, the computer determines how the current image is rotated and translated in relation to the reference fingerprint data. Furthermore, it selects the current sub-areas of the current image of the fingerprint. These current sub-areas depict essentially the same parts of the fingerprint as reference sub-areas which are stored on the smart card as part of the reference fingerprint data and which never leave it. The current sub-areas are slightly larger than the reference sub-areas to compensate for the fact that the finger may have been pressed harder against the sensor when registering the current image than when registering the reference fingerprint. As an example, it can be mentioned that the reference sub-areas can be 24 * 24 pixels, while the relevant sub-areas can be 30 * 32 pixels.

De aktuella delområdena skickas till smart cardet 4, där processorn 6 jämför referensdelomràdena med de aktu- ella delområdena för att avgöra om de kommer från samma fingeravtryck.The current sub-areas are sent to the smart card 4, where the processor 6 compares the reference sub-areas with the current sub-areas to determine if they come from the same fingerprint.

I fig 2a visas schematiskt en digital bild 20 av ett referensfingeravtryck. I referensfingeravtrycket har mar- kerats ett antal referensdelområden 24. Referensdelområde 24a kan vara ett publikt referensdelomràde.Fig. 2a schematically shows a digital image 20 of a reference fingerprint. A number of reference sub-areas 24 have been marked in the reference fingerprint. Reference sub-area 24a can be a public reference sub-area.

I fig 2b visas schematiskt en digital bild 26 av en aktuellt fingeravtryck av samma person. För enkelhetens Zïílé--Glï-šl 33:27 G:1E“a12"\_CH\\Åš¿l5š*-_ZGGIÅZÛIZCÜ? SE -fP}2:-'.»'QÉ.-0L^É'-§7 'ffï'í"*"~.d,xâ=ï 10 15 20 25 30 35 524 055 12 skull har det här antagits att fingret befunnit sig i exakt samma läge på sensorn när bilden av det aktuella fingeravtrycket upptogs som när bilden av referensfinger upptogs. I bilden av det aktuella fingeravtrycket har ett antal aktuella delområden 28 markerats. Det framgår att dessa är något större än referensdelområdena, men att de täcker samma delområden i fingeravtrycket.Fig. 2b schematically shows a digital image 26 of a current fingerprint of the same person. For simplicity Zïílé - Glï-šl 33:27 G: 1E “a12" \ _ CH \\ Åš¿l5š * -_ ZGGIÅZÛIZCÜ? SE -fP} 2: - '. »' QÉ.-0L ^ É'-§7 ' ffï'í "*" ~ .d, xâ = ï 10 15 20 25 30 35 524 055 For this reason, it has been assumed that the finger was in exactly the same position on the sensor when the image of the current fingerprint was taken as when the image of the reference finger was taken. In the image of the current fingerprint, a number of current sub-areas 28 have been marked, it appears that these are slightly larger than the reference sub-areas, but that they cover the same sub-areas in the fingerprint.

Eftersom varje referensdelområde 24 är mindre än motsvarande aktuella delområde 28 måste, vid jämförelsen på smart cardet, referensdelomràdet jämföras med det aktuella delområdet i ett flertal olika inbördes lägen för att avgöra om referensdelområdet motsvarar något om- råde inom det aktuella delområdet.Since each reference sub-area 24 is smaller than the corresponding current sub-area 28, when comparing on the smart card, the reference sub-area must be compared with the current sub-area in a number of different mutual positions to determine whether the reference sub-area corresponds to any area within the current sub-area.

I fig 3 visas schematiskt hur jämförelsen mellan ett referensdelområde 24 och ett aktuellt delområde 28 går till. Jämförelsen sker allra först i ett inbördes läge där referensdelområdet är centrerat i förhållande till det aktuella delområdet, dvs i det inbördes läge som visas i fig 3. Därefter förskjuts referensdelområdet ett steg, dvs en bildpunkt, åt vänster i förhållande till det aktuella delområdet såsom visas med pilen 30. I nästa steg förskjuts referensdelområdet ett steg nedåt. Där- efter två steg till höger, två steg uppåt, tre steg till vänster osv, så att referensdelområdet flyttas i förhål- lande till det aktuella delområdet i en spiralform. Jäm- förelsen avslutas i ett antal inbördes lägen där refe- rensdelomràdet 24 befinner sig vid kanten av det aktuella delområdet 28.Fig. 3 shows schematically how the comparison between a reference sub-area 24 and a current sub-area 28 takes place. The comparison first takes place in a mutual position where the reference sub-area is centered in relation to the current sub-area, ie in the mutual position shown in Fig. 3. Then the reference sub-area is shifted one step, i.e. a pixel, to the left in relation to the current sub-area as shown with the arrow 30. In the next step, the reference sub-area is shifted one step down. Then two steps to the right, two steps up, three steps to the left, etc., so that the reference sub-area is moved in relation to the current sub-area in a spiral shape. The comparison ends in a number of mutual positions where the reference sub-area 24 is located at the edge of the relevant sub-area 28.

Vart och ett av referensdelområden kan jämföras med sitt motsvarande aktuella delområde på det i fig 3 visade sättet. kontrollen.Each of the reference sub-areas can be compared with its corresponding current sub-area in the manner shown in Fig. 3. the control.

Detta gäller även vid den nedan beskrivna för- Jämförelsen mellan varje referensdelområde 24 och dess motsvarande aktuella delområde 28 sker genom att varje par av överlappande bildpunkter jämförs och en poäng adderas till en poängsumma beroende på hur lika bildpunktsvärdena är. Normalt utgörs delområdena av bit- "H27 (E:RPaL\_I'IE¶“\_AÄI'S\ZGÜl\_2fJl236? SV (IGZIÜJÛÅÄ-Gä-II? liiítkcío-I 10 15 20 25 30 35 ' 524 055 13 mappar där varje bildpunkt bara kan anta värdet 0 eller 1. Om de överlappande bildpunkterna då båda har samma värde kan poängsumman exempelvis räknas upp med 1, medan överlappande bildpunkterna har olika värden ingen poäng adderas till poängsumman. När alla par av överlap- pande bildpunkter har kontrollerats jämförs den erhållna poängsumman med ett tröskelvärde, som anger ett förutbe- om de stämt krav på likhet. Om poängsumman ligger över tröskel- värdet är kravet på likhet mellan delområdena uppfyllt och referensdelområdet anses matcha det aktuella delom- rådet i det inbördes läge där de jämfördes. Om vidare antalet referensdelområden som matchar sina respektive aktuella delområden är större än ett förutbestämt trös- kelvärde anses det aktuella fingeravtrycket härröra från samma person som referensfingeravtrycksdatana.This also applies to the comparison described below. The comparison between each reference sub-area 24 and its corresponding current sub-area 28 takes place by comparing each pair of overlapping pixels and adding one point to a score depending on how equal the pixel values are. Normally the sub-areas consist of bit- "H27 (E: RPaL \ _I'IE¶" \ _ AÄI'S \ ZGÜl \ _2fJl236? EN (IGZIÜJÛÅÄ-Gä-II? Liiítkcío-I 10 15 20 25 30 35 '524 055 13 folders where each pixel can only assume the value 0 or 1. If the overlapping pixels then both have the same value, the score can for example be calculated with 1, while the overlapping pixels have different values no points are added to the score. If the score is above the threshold value, the requirement for equality between the sub-areas is met and the reference sub-area is considered to match the relevant sub-area in the mutual position where they were compared. the number of reference sub-areas that match their respective current sub-areas is greater than a predetermined threshold value, the current fingerprint is considered to originate from the same person as the reference fingerprint data.

Före den egentliga kontrollen av om ett referensdel- område matchar ett aktuellt delområde kan en förkontroll utföras. Syftet med denna är att snabbt konstatera att ett referensdelområde inte matchar ett aktuellt delom- råde, så att den fullständiga kontrollen, som trots allt kräver en hel del beräkningar, inte behöver genomföras om det är uppenbart att referensdelområdet och det aktuella delområdet är mycket olika. Förkontrollen utförs på samma sätt som den egentliga kontrollen, men vid jämförelsen används endast en del av referensdelområdena, exempelvis ett område i mitten av varje referensdelområde som har ca 50%-10% av ytan av referensdelområdet. I ovannämnda exem- pel med ett referensdelområde med 24*24 bildpunkter kan exempelvis ett subområde om 8*8 bildpunkter användas för förkontrollen. Detta referenssubområde jämförs med ett Det aktuella sub- området kan i detta exempel vara l2*l2 bildpunkter. Vi- dare används ett lägre krav på likhet, dvs ett lägre tröskelvärde, subområde av det aktuella delområdet. för att ett referensdelområde skall anses matcha ett aktuellt delområdet. Skälet till detta är att risken för att ett aktuellt fingeravtryck som tillhör samma person som referensfingeravtrycksdatana avvisas få 10 15 20 25 30 35 524 055 14 skall vara liten. Man vill med andra ord ha en låg FRR.Before the actual check of whether a reference sub-area matches a current sub-area, a pre-check can be performed. The purpose of this is to quickly establish that a reference sub-area does not match a current sub-area, so that the complete inspection, which nevertheless requires a lot of calculations, does not need to be carried out if it is obvious that the reference sub-area and the relevant sub-area are very different. The pre-check is performed in the same way as the actual check, but in the comparison only a part of the reference sub-areas is used, for example an area in the middle of each reference sub-area which has about 50% -10% of the surface of the reference sub-area. In the above-mentioned examples with a reference sub-area with 24 * 24 pixels, for example, a sub-area of 8 * 8 pixels can be used for the pre-control. This reference sub-area is compared with a The current sub-area in this example can be l2 * l2 pixels. Furthermore, a lower requirement for similarity is used, ie a lower threshold value, sub-area of the relevant sub-area. for a reference sub-area to be considered to match a current sub-area. The reason for this is that the risk that a current fingerprint belonging to the same person as the reference fingerprint data will be rejected may be small. In other words, you want a low FRR.

Det övergripande förfarandet för jämförelse av ett referensdelomrâde och ett aktuellt delområde sammanfattas i flödesschemat i fig 4. steg 400. Om denna är OK, Först utförs en förkontroll, steg 410, dvs att likhetskravet är uppfyllt, så utförs den egentliga eller fullständiga kontrollen, steg 420. Om denna är OK, steg 430, dvs att likhetskravet är uppfyllt, anses, steg 440, referensdel- området matcha det aktuella delområdet. Om däremot för- kontrollen eller den fullständiga kontrollen inte är OK, dvs likhetskravet inte är uppfyllt, anses referensdelom- rådet inte matcha det aktuella delområdet, steg 450 och 460.The overall procedure for comparing a reference sub-area and a current sub-area is summarized in the flow chart in Fig. 4. step 400. If this is OK, First a pre-check is performed, step 410, ie the similarity requirement is met, then the actual or complete check is performed, step 420. If this is OK, step 430, ie the similarity requirement is met, step 440, the reference sub-area is considered to match the current sub-area. If, on the other hand, the pre-inspection or the complete inspection is not OK, ie the equality requirement is not met, the reference sub-area is not considered to match the relevant sub-area, steps 450 and 460.

Ett exempel på hur den fullständiga fingeravtrycks- kontrollen kan utföras skall nu beskrivas under hänvis- ning till flödesschemat i fig 5, som dock visar ett ut- förande utan förkontroll, Kontrollen börjar med ett första referensdelomrâde och motsvarande aktuella delområde kontrolleras, steg 505. Delomràdena jämförs först i ett första inbördes läge eller position, steg 510. Därefter kontrolleras om poäng- summan som jämförelsen resulterar i är större än ett första tröskelvärde ”Tröskel 1", steg 515. Om så inte är fallet kontrolleras om alla inbördes lägen har kontrolle- rats, steg 520. Om så inte är fallet kontrolleras nästa inbördes läge eller position, steg 525 och flödet återgår till steg 515. Om kontrollen av poängsumman i steg 515 visar att poängsumman är större än eller lika med det första tröskelvärdet, avbryts genast kontrollen av det aktuella delområdet. Referensdelomràdet anses matcha det aktuella delområdet och en variabel ”Match” som anger antalet matchande delområden inkrementeras, steg 530. Det framgår alltså att en uttömmande kontroll av referens- delomràdets alla olika lägen i förhållande till det aktu- ella delområdet endast behöver göras i det fall referens- delområdet matchar det aktuella delområdet i det inbördes 10 15 20 25 30 35 .524 055 15 läge som kontrolleras sist eller i det fall då referens- delområdet inte matchar det aktuella delområdet alls.An example of how the complete fingerprint check can be performed will now be described with reference to the flow chart in Fig. 5, which, however, shows an embodiment without pre-check. The check starts with a first reference sub-area and the corresponding current sub-area is checked, step 505. is first compared in a first mutual position or position, step 510. Then it is checked whether the score sum that the comparison results in is greater than a first threshold value "Threshold 1", step 515. If this is not the case, check whether all mutual positions have control If this is not the case, the next relative position or position is checked, step 525 and the flow returns to step 515. If the check of the score in step 515 shows that the score is greater than or equal to the first threshold value, the check of The reference sub-area is considered to match the current sub-area and a variable “Match” which indicates the number of matching sub-areas incl. step 530. It thus appears that an exhaustive check of all the different sub-areas of the reference sub-area in relation to the relevant sub-area only needs to be made in the event that the reference sub-area matches the relevant sub-area in the mutual 10 15 20 25 30 35. 524 055 15 position that is checked last or in the case where the reference sub-area does not match the current sub-area at all.

Efter det att Match-variabeln har inkrementerats kontrolleras om dess värde är större eller lika med ett andra tröskelvärde ”Tröskel 2” som anger antalet match- ande delområden som krävs för att det aktuella finger- avtrycket skall anses komma från samma person som refe- rensfingeravtrycksdatana, steg 535. Om matchvariabelns värde är större än eller lika med det andra tröskelvärdet accepteras fingeravtrycket och personens identitet anses verifierad, steg 540. Det behöver alltså inte ske någon uttömmande sökning av alla delområden, utan så snart det andra tröskelvärdet uppnås anses personens identitet verifierad. Om matchvariabelns värde är mindre än det andra tröskelvärdets, undersöks i steg 545 om kontrollen av delområdena är klar. Kontrollen kan vara klar pga att det inte finns fler delområden att kontrollera, men den kan även vara klar pga att det återstår så få delområden att kontrollera att villkoret i steg 535 aldrig kan bli uppfyllt. Om kontrollen är klar, avvisas fingeravtrycket, steg 550, pga att personens identitet inte kan anses vara verifierad. Om kontrollen inte är klar, kontrolleras nästa delomràde, steg 555, varefter flödet går vidare till steg 510.After the Match variable has been incremented, it is checked whether its value is greater than or equal to a second threshold value "Threshold 2" which indicates the number of matching sub-areas required for the current fingerprint to be considered to come from the same person as the reference fingerprint data. , step 535. If the value of the match variable is greater than or equal to the second threshold value, the fingerprint is accepted and the person's identity is considered verified, step 540. . If the value of the match variable is less than that of the other threshold value, check in step 545 whether the check of the sub-areas is complete. The check may be completed because there are no more sub-areas to check, but it may also be completed because there are so few sub-areas left to check that the condition in step 535 can never be met. If the check is complete, the fingerprint, step 550, is rejected because the person's identity cannot be considered verified. If the check is not complete, the next sub-area, step 555, is checked, after which the flow proceeds to step 510.

Alternativa utföringsexempel Uppfinningen har beskrivits ovan med referens till ett smart card. Uppfinningen är emellertid tillämplig i alla sammanhang där ett mindre delomràde av ett finger- avtryck skall jämföras med ett större delomràde av ett fingeravtryck för att bestämma om det mindre delområdet överensstämmer någonstans inom det större delområdet.Alternative Embodiments The invention has been described above with reference to a smart card. However, the invention is applicable in all contexts where a smaller subarea of a fingerprint is to be compared with a larger subarea of a fingerprint to determine if the smaller subarea corresponds somewhere within the larger subarea.

Jämförelsen behöver inte ske på ett smart card utan den kan även ske i någon annan enhet i vilken det är önskvärt att öka snabbheten för jämförelsen.The comparison does not have to take place on a smart card, but it can also take place in another device in which it is desirable to increase the speed of the comparison.

Jämförelsen har ovan beskrivits som att poängberäk- nas på basis av bitvärdena för bildpunkter i två delom- råden. Jämförelsen kan dock göras på andra sätt som också 215Û4-~03---3.i Üíëtl? G:ÄPaIÅCEESHISJXQOÜi.KZÛIZÛêQ SE_{P)Z='30-l-O5-27 lLÜIIZSndOC 10 15 20 25 524 055 16 resulterar i ett mått på likheten mellan delområdena, exempelvis genom någon form av korrelation mellan bilder- na. Delområdena behöver inte utgöras av bitmappar utan kan vara gråskalebilder eller tom färgbilder.The comparison has been described above as being calculated on the basis of the bit values for pixels in two sub-areas. However, the comparison can be made in other ways such as also 215Û4- ~ 03 --- 3.i Üíëtl? G: ÄPaIÅCEESHISJXQOÜi.KZÛIZÛêQ SE_ {P) Z = '30 -l-O5-27 lLÜIIZSndOC 10 15 20 25 524 055 16 results in a measure of the similarity between the sub-areas, for example by some form of correlation between the images. The sub-areas do not have to be bitmaps but can be grayscale images or even color images.

Ovan har angetts att förfarandet används för veri- fiering. Det kan emellertid även användas för identifie- ring. Exempelvis kan flera uppsättningar referensfinger- avtrycksdata för flera olika personer vara lagrade på smart cardet, varvid en jämförelse utförs tills en match- ande identitet påträffas eller tills alla referensfinger- avtrycksdatana har jämförts med de aktuella fingerav- trycksdatana.It has been stated above that the procedure is used for verification. However, it can also be used for identification. For example, several sets of reference fingerprint data for several different people may be stored on the smart card, a comparison being made until a matching identity is found or until all the reference fingerprint data has been compared with the current fingerprint data.

Ovan har angetts att referensdelområdet flyttas i förhållande till det aktuella delområdet vid jämförelsen dememellan. Naturligtvis kan lika gärna det aktuella delområdet flyttas i förhållande till referensdelområdet.It has been stated above that the reference sub-area is moved in relation to the relevant sub-area in the comparison between them. Of course, the relevant sub-area can just as easily be moved in relation to the reference sub-area.

Det är den inbördes förflyttningen som är av intresse.It is the mutual movement that is of interest.

Ovan har vidare beskrivits att referensdelomràdet jämförs med det aktuella delområdet i alla tänkbara in- bördes lägen där referensdelområdet överlappar det ak- tuella delområdet. Det är emellertid också möjligt att utföra jämförelsen i ett begränsat antal av de tänkbara inbördes lägena. För detta ändamål kan en offset-para- meter, som anger i hur många positioner åt vart håll från det centrerade läget som jämförelsen skall utföras, an- vändas.It has also been described above that the reference sub-area is compared with the current sub-area in all conceivable mutual positions where the reference sub-area overlaps the current sub-area. However, it is also possible to perform the comparison in a limited number of the possible mutual positions. For this purpose, an offset parameter can be used, which indicates in how many positions in each direction from the centered position the comparison is to be performed.

Züüäq-Ûšﬂßl Ûššzlï' G:RPaEÉKZHHRETERQOÜJ.“=_2fJ}.27}159 (.P}2-'J-'Jl-O!L'-_Ü'F lÛf/JßkiozïZüüäq-Ûš ﬂ ßl Ûššzlï 'G: RPaEÉKZHHRETERQOÜJ. “= _ 2fJ} .27} 159 (.P} 2-'J-'Jl-O! L' -_ Ü'F lÛf / Jßkiozï

Claims

10 15 20 25 30 35 524 055 17 PATENT REQUIREMENTS

A method for checking whether a current fingerprint belongs to a person for whom reference fingerprint data has previously been stored, which reference fingerprint data comprises a plurality of sub-areas, designated reference sub-areas, of a digital representation of the person's fingerprint, in which method at least some of the reference sub-areas are compared with the corresponding current sub-areas of a digital representation of the current fingerprint, which current sub-areas are larger than the reference sub-areas, to check their similarity, characterized by the steps of comparing one of the reference sub-areas with one of the relevant sub-areas in different mutual positions until a mutual position is found for which a first predetermined requirement for similarity between the reference sub-area and the relevant sub-area is met; when this mutual position is found, register that the reference sub-area matches the first relevant sub-area; and interrupt the comparison of the reference sub-area and the relevant sub-area.

A method according to claim 1, wherein the comparison is started in the mutual position where it is most likely that the first predetermined requirement of similarity is met.

A method according to claim 1 or 2, wherein the comparison is performed in mutual positions where the reference sub-area is located near the middle of the relevant sub-area before mutual positions where the reference sub-area is located at the edges of the relevant sub-area.

A method according to claim 1, 2 or 3, wherein the comparison is started in a mutual position where the reference sub-area is centered in relation to the relevant sub-area.

The method of claim 1, further comprising the step of if the first predetermined requirement of similarity Éßå-Ûfxï-Sí G: 'zPa ^; \ _ fÉlI-1 If it is not satisfied after a comparison in a mutual position, repeat the comparison in a changed mutual position, in which the position of the reference sub-area in relation to the relevant sub-area is as centered as possible.

Method according to one of the preceding claims, wherein the reference sub-area is compared with the relevant sub-area in successive positions which essentially form a spiral shape.

A method according to any one of the preceding claims, further comprising the step of repeating the comparison for further of the reference sub-areas and the relevant sub-areas until a predetermined number of reference sub-areas matching their respective current sub-areas has been registered.

The method of claim 7, further comprising the step of interrupting the repetition of the comparison as soon as the number of remaining reference sub-areas for which the comparison has not yet been performed, but is to be performed, is such that said predetermined number is unattainable.

A method according to any one of the preceding claims, wherein the reference sub-areas are compared with the relevant sub-areas in a first and a second phase, the second phase being performed only if the comparison in the first phase indicates that the current fingerprint belongs to the same person as the reference fingerprint data.

A method according to claim 9, wherein the comparison in the first phase is performed by means of only one sub-area of the reference sub-areas, while the comparison in the second phase is performed for entire reference sub-areas.

11. ll. A method according to claim 9 or 10, wherein the comparison in the first phase is made in the same way as the comparison in the second phase.

A method according to any one of claims 9-11, wherein the first predetermined requirement of similarity is lower in the comparison in the first phase than in the second phase. 10 15 20 25 30 35 r 524 055 19

Computer program comprising program code which, when executed in a computer, is arranged to cause the computer to perform a method according to any one of claims 1-12.

A memory medium on which a computer program according to claim 13 is stored.

A device for checking whether a current fingerprint belongs to a person for whom reference fingerprint data has previously been stored, which device comprises a memory which stores the reference fingerprint data in the form of sub-areas, referred to as reference sub-areas, of a digital representation of the person's fingerprint; and a signal processing unit arranged to compare at least some of the reference sub-areas with the corresponding current sub-areas of a digital representation of the current fingerprint, which current sub-areas are larger than the reference sub-areas, in order to check their similarity, by that the signal processing unit is further arranged to compare one of the reference sub-areas with one of the relevant sub-areas in different mutual positions until a mutual position is found for which a first predetermined requirement for similarity between the reference sub-area and the relevant sub-area is met; when this mutual position is found, register that the reference sub-area matches the first relevant sub-area; and interrupt the comparison of the reference sub-area and the relevant sub-area.

The device of claim 15, wherein the device is a portable data carrier.

The device of claim 15 or 16, wherein the device is a smart card.

A device according to any one of claims 15-17, wherein the device is a Java type smart card.