optimització d' un algorisme per la identificació d...

Optimització d' un algorisme per la identificació d'empremtes dactilars

TITULACIÓ: Enginyera Tècnica Industrial especialitat Electrònica Industrial

Autor: Albert Pérez Llorens

Director: Nicolau Cañellas Alberich

Data: Juny 2006

iii

Índex

1 Objectiu................................................................................... 1

2 Antecedents............................................................................. 3

3 Biometria d'Empremtes Dactilars........................................ 5

3.1 Reconeixements Biometrics................................................................... 6

3.1.1Tipus de reconeixements fisiològics................................................... 6

3.1.2 Tipus de Reconeixements Comportamentals.................................... 7

3.2 Empremtes Dactilars.............................................................................. 8

3.2.1 Crestes papilars.................................................................................. 8

3.2.1.1Definició de cresta papilar. ........................................................ 8

3.2.1.2 Classificació de crestes papilars................................................. 9

3.2.1.3 Factors que influeixen en les crestes papilars............................ 10

3.2.2 Dactilogrames..................................................................................... 11

3.2.2.1 Definició de dactilograma.......................................................... 11

3.2.2.2 Sistemes dactilars...................................................................... 11

3.2.2.3 Punts característics.................................................................... 12

3.2.2.4 Punts singulars: Deltas i Nuclis................................................ 14

3.2.3 Utilitat de la impressió dactilar com a element identificatiu............ 15

3.3 Sistema Automàtic d’Identificació Dactilar.......................................... 16

3.4 Adquisició d' empremtes dactilars......................................................... 18

3.5 Processat de les imatges........................................................................... 21

3.5.1 Mètode de Binarització-Esqueletització............................................ 22

3.5.1.1 Realçar les vores...................................................................... 22

3.5.1.2 Binarització.............................................................................. 24

3.5.1.3 Segmentació............................................................................ 24

3.5.1.4 Esqueletització i Poda............................................................. 25

3.5.2 Extracció de minúties.......................................................................... 27

3.6 Aparellament d’empremtes.................................................................... 28

4 Algorisme d’extracció de Maio............................................. 31

4.1 Seguiment dels crestalls.......................................................................... 32

4.1.1 Càlcul del Màxim................................................................................ 36

4.1.2 Càlcul de la Direcció......................................................................... 38

4.1.3 Criteris per aturar-se.......................................................................... 39

4.2 Extracció de Minúties............................................................................... 40

iv

5 Algorisme d'aparellament .................................................... 42

5.1 Procés inicial............................................................................................ 43

5.2 Funcionament general.............................................................................. 46

5.2.1 Anàlisi local....................................................................................... 47

5.2.2Creació de la Matriu de Similitud i assignació de la minútia central. 49

5.2.3 Anàlisi Global.................................................................................... 50

5.3 Paràmetres del programa.......................................................................... 52

5.4 Detecció Errors......................................................................................... 53

5.4.1 Errors Anàlisi Local............................................................................ 53

5.4.1.1 Error_domain............................................................................. 53

5.4.2 Errors Creació Matriu de Similitud i assignació de la minútia central.. 53

5.4.2.1 Error_condició_distància........................................................... 53

5.4.2.2 Error_condició_angle................................................................. 54

5.4.2.3 Error_funció_central_feature..................................................... 55

5.4.2.4 Error_compta_repetides............................................................. 56

5.4.3 Errors Anàlisi global.......................................................................... 57

5.4.3.1 Error_domain............................................................................. 57

5.4.3.2 Error_condició_angle................................................................. 57

5.4.3.3 Error_tolerància_angles............................................................. 57

5.4.3.4 Error_tractament_minúties......................................................... 59

5.4.3.5 Error_emparella_minútia_mes_d’una_vegada.......................... 59

5.4.3.6 Error_sistema_aparellament................................................... 62

6 Algorisme d'aparellament corregit...................................... 64

6.1 Funcionament general................................................................................ 65

6.1.1 Anàlisi local....................................................................................... 66

6.1.2 Creació Matriu de Similitud i assignació de la minútia central......... 68

6.1.3 Anàlisi Global.................................................................................... 69

6.2 Paràmetres del programa............................................................................ 71

6.3 Explicació funcions.................................................................................... 72

6.3.1 Anàlisi Local...................................................................................... 73

6.3.1.1 Funció Veïnes............................................................................ 74

6.3.1.2 Funció Ordena............................................................................ 74

6.3.1.3 Funció Local Feautre Distance.................................................. 75

6.3.2 Creació Matriu de Similitud i assignació de la minútia central......... 76

v

6.3.2.1 Funció Similarity Degree........................................................... 76

6.3.2.2 Funció Escriu Matriu................................................................. 77

6.3.2.3 Funció Central Feature............................................................... 78

6.3.3 Anàlisi Global..................................................................................... 79

6.3.3.1 Funció Global_parameters......................................................... 79

6.3.3.2 Funció Global_Similarity........................................................... 80

6.3.3.3 Funció Escriu Matriu................................................................. 80

6.3.3.4 Funció Global Feature................................................................ 81

6.3.3.5 Funció Matching........................................................................ 81

6.4 Resolució dels errors.................................................................................. 82

6.4.1 Resolució Errors Anàlisi Local........................................................... 82

6.4.1.1 Resolució_error_domain............................................................ 82

6.4.2 Resolució Errors Creació Matriu de Similitud i assignació de la minútia... 82

6.4.2.1 Resolució_error_condició_distància.......................................... 82

6.4.2.2 Resolució_error_condició_angle............................................... 82

6.4.2.3 Resolució_error_funció_central_feature.................................... 83

6.4.2.4 Resolució_error_compta_repetides........................................... 84

6.4.3 Resolució Errors Anàlsis global......................................................... 85

6.4.3.1 Resolució_error_domain............................................................ 85

6.4.3.2 Resolució_error_condició_angle............................................... 85

6.4.3.3 Resolució_error_tolerància_angles............................................ 85

6.4.3.4 Resolució_error_tractament_minuties....................................... 86

6.4.3.5 Resolució error emparella minutia mes d’una vegada............... 86

6.4.3.6 Resolució error sistema aparellament .................................... 89

7 Verificació Programa............................................................. 90

7.1 Empremtes iguals..................................................................................... 92

7.2 Empremtes diferents................................................................................ 104

7.3 Resultats i toleràncies............................................................................... 107

8 Conclusions............................................................................. 108

9 Referències i Bibliografia...................................................... 109

10 Codi......................................................................................... 110

vi

Índex de figures

Figura 3.1: Secció de la pell del palpís de les mans.......................................... 8

Figura 3.2: Cresta Papilar.................................................................................. 9

Figura3.3: Crestes arciformes............................................................................ 9

Figura 3.4: Crestes anguloses............................................................................. 9

Figura 3.5: Crestas verticilares.......................................................................... 9

Figura 3.6: Sistemes dactilars: marginal, basilar y nuclear............................ 11

Figura 3.7 Dactilograma anucleat..................................................................... 11

Figura 3.8: Punt final.......................................................................................... 12

Figura 3.9 Punt de bifurcació............................................................................. 12

Figura 3.10 Punt aïllat........................................................................................ 13

Figura 3.11: Punt secant..................................................................................... 13

Figura 3.12: Punt nucli....................................................................................... 14

Figura 3.13 Punt delta......................................................................................... 14

Figura 3.14: Modes de funcionament d’un SAID............................................. 17

Figura 3.15: Ejemples de captures realitzades per sensors on_chip.............. 19

Figura 3.16: Sensor Complet.............................................................................. 19

Figura 3.17: Sensor Parcial................................................................................ 20

Figura 3.18: Exemple de realçar vores............................................................. 22

Figura 3.19: Exemple filtre de Gabor.............................................................. 23

Figura 3.20: Exemple de binarització: Original, filtrada i binaritzada......... 24

Figura 3.21: Exemple de segmentació............................................................. 25

Figura 3.22: Exemple de preparació de la imatge per l’extracció de minúties.. 26

Figura 3.23: Identificació de minúties............................................................... 27

Figura 3.24: Filtrat estructural.......................................................................... 27

Figura 3.25: Classificació d’Henry.................................................................... 28

Figura 3.26: Exemples d’empremtes que semblen iguals................................ 29

Figura 4.1: Representació 3D d’una empremta (a). Secció crestalls (b).... 31

Figura 4.2: Imatge de l’empremta dactilar capturada. (a) σ distància entre dos crestes consecutives. (b) ε amplada de la cresta.............................

32

Figura 4.3: Punt (ic,jc) i direcció cϕ que pertany a una cresta...................... 33

Figura 4.4: Desplaçament de µ píxels fet en la direcció cϕ i punt (it,jt) trobat. 33

Figura 4.5: Tall de direcció cϕ +π/2 centrat en (it,jt) i longitud 2σ+1............ 33

Figura 4.6: Secció Ω que conté el nivell de gris para cada punt del tall realitzat.. 34

vii

Figura 4.7: Cerca del punt (in,jn) en la secció Ω.............................................. 34

Figura 4.8: Pseudo-codi del mètode de Maio.................................................... 35

Figura 4.9 : Representació de diferents seccions os es veu la presencia de soroll..... 36

Figura 4.10: Comparació entre la imatge original i el resultat filtrat........... 36

Figura 4.11: Algorisme per al càlcul de la direcció.......................................... 38

Figura 4.12: Tipus de minúties trobades pel algorisme de Maio.................... 40

Figura 5.1: Adquisició de les empremtes, a la esquerra template i a la dreta sample........................................................................................................

43

Figura 5.2: Esqueletització de les empremtes, a l’ esquerra template i a la dreta sample........................................................................................................

44

Figura 5.3: Minútia amb coordenades X , Y i orientació alfa......................... 44

Figura 5.4: Extracció minúties de les empremtes (marcades amb vermell), a l’ esquerra template i a la dreta sample........................................................

45

Figura 5.5: Minúties numerades, a l’ esquerra template i a la dreta sample 45

Figura 5.6: Fitxer d’entrada Template.............................................................. 45

Figura 5.7: Flux general...................................................................................... 46

Figura 5.8: Exemple local per 5 veïnes, la minútia blava es la de referència...........................................................................................................

47

Figura 5.9: Exemple fitxer creat en l’anàlisi local per la minutia 12............ 48

Figura 5.10:Taula de similitud entre 20 minúties template i 20 minúties sample.... 49

Figura 5.11: Anàlisi global amb minútia central nº14.................................... 50

Figura 5.12: Emparellat final template amb sample........................................ 51

Figura 5.13: Exemples toleràncies..................................................................... 52

Figura 5.14: Error per distància 0.................................................................... 54

Figura 5.15: Taula de similitud entre 20 minúties template i 20 minúties sample.. 55

Figura 5.16: Taula de similitud entre 23 minúties template i 14 minúties sample.. 56

Figura 5.17: Aparellament doble Template vs Sample................................ 59

Figura 5.18: Anàlisi global template.................................................................. 60

Figura 5.19: Anàlisi global sample..................................................................... 61

Figura 5.20:Matching......................................................................................... 61

Figura 5.21:Aparellament incorrecte A........................................................ 62

Figura 5.22: Aparellament incorrecte B........................................................ 63

Figura 6.1: Flux general codi creat.................................................................... 65

viii

Figura 6.2: Fitxer d’entrada de dues minúties................................................. 66

Figura 6.3: Exemple local per 5 veïnes, la minútia blava és la de referència 66

Figura 6.4: Exemple fitxer creat en l’anàlisi local per la minutia 12............ 67

Figura 6.5: Taula similitud entre 20 minúties template i 20 minúties sample.... 68

Figura 6.6: Matriu similitud global de 4 minuties template i 3 minuties sample...... 69

Figura 6.7: Emparellat final template amb sample.......................................... 70

Figura 6.8: Flux execució funcions principals.................................................. 72

Figura 6.9: Flux funció local feature distance.................................................. 73

Figura6.10: Exemple anàlisi local per la minútia 12........................................ 75

Figura 6.11: Creació Matriu de Similitud i assignació de la minútia central 76

Figura 6.12: Exemple Matriu similitud de 20 minúties Template i 20 minúties Sample.................................................................................................

77

Figura 6.13: Flux anàlisi Global......................................................................... 79

Figura 6.14: Matriu similitud global de 4 minúties template i 3 minúties sample.... 80

Figura 6.15: Taula de similitud entre 23 minúties template i 14 minúties sample... 84

Figura 6.16: Aparellament correcte Template vs Sample............................ 88

Figura 7.1: Procés de verificació del programa................................................ 90

Figura 7.2: Exemple per les toleràncies de distància i angles......................... 91

Figura 7.3: Exemples toleràncies....................................................................... 91

Figura 7.4: Toleràncies....................................................................................... 107

1

1 Objectiu

Fa molt de temps que s´ utilitzen les empremtes dactilars com a mètode de identificació. En la antiga Xina, les empremtes dactilars d´ una persona eren utilitzades com a part de la firma realitzada en documents públics i privats. Més recentment, les empremtes dactilars s´ utilitzen en les investigacions de la policia per la identificació de sospitosos.

Láparellament de empremtes dactilars incompletes o parcials continua sent un important repte avui en dia, tot i les noves tecnologies i tècniques de identificació démpremtes dactilars.

En aquest projecte el que es pretén és la realització d’un codi al qual direm "Match" que ens permeti comprovar si dues empremtes son iguals o no. Es partirà dún model de Matching de Mittle en C.

El nostre programa rebrà una entrada que serà un fitxer de text generat apartir d´ un algorisme d´ extracció basat amb el sistema proposat pels doctors Dario Maio i Davide Maltoni, on tindrem els punts característics ( que ja veurem a l´ apartat de caracterització i processat d’empremtes ) de les empremtes i seguirà un procés corresponent a un anàlisi local de l´ empremta, una busqueda dels punts centrals de cada empremta i finalment un anàlisi global de les dues per determinar-ne l´ aparellament.

En els primers apartats veurem la biometria d'empremtes dactilars i com és realitza el procés d'extracció per a detectar les minúties.

Un cop introduït el tema d’extracció de minúties, veurem el algorisme d’aparellament del qual es parteix i en el següent capítol les correccions fetes.

Finalment per acabar es farà una verificació del programa realitzat per tal de treure uns resultats i conclusions finals.

Objectiu________________________________________________________________________________

_______________________________________________________________________

2

Antecedents_____________________________________________________________________________

_______________________________________________________________________

3

2 Antecedents

La verificació de la identificació personal és una necessitat important en els últims temps i que s'ha vist afectada per la implantació de les noves tecnologies en les nostres vides.

Avui dia ens veiem obligats a identificar-nos en molts aspectes quotidians, ja sigui per a la utilització dels comptes bancaris, l'accés a Internet o la utilització de telèfons mòbils, ja que si algú tingués accés als nostres serveis podria perjudicar-nos seriosament i fins i tot realitzar delictes sota la nostra responsabilitat.

Actualment els sistemes d'autenticació que s'utilitzen es basen en dues característiques i la combinació d'ambdues. La primera és conèixer algú que ningú més coneix i la segona tenir alguna cosa que ningú més tingui. Referent a la primera característica “algú que sàpigues” s'han creat sistemes com el PASSWORD i/o PIN, ambdós es basen en la mateixa tècnica que consisteix en una combinació de signes que identifiquen unívocament a una determinada persona; per a l'accés a qualsevol tipus de recurs protegit. Normalment la diferència entre PIN i PASSWORD radica en la seva utilització i no en la tècnica en la qual es basen. El PASSWORD pot ser conegut per una o més persones per a l'accés a serveis privats o col·lectius, la seva major utilització és en l'àmbit d'Internet per a tenir accés o recursos restringits i sempre va acompanyat del coneixement previ del nom d'usuari. En canvi, el PIN o nombre personal d'identitat no necessita de cap coneixement previ i sempre es refereix a la identificació o autenticació de només un individu, tal com indica el seu propi nom. El major camp d'utilització d'aquest sistema és en la telefonia mòbil. La segona característica, “algú que tinguis”, fa referència a sistemes tan utilitzats com podria ser el DNI (Document Nacional d'Identitat) o targetes de fitxatge i/o accés utilitzades per empreses per al control dels seus treballadors. El major sistema que combina ambdues característiques i utilitzat per la majoria de persones en el món són les targetes bancàries o de crèdit, ja que es componen d'un sistema “algú que tinguis”, com és la pròpia targeta i d'un sistema “algú que sàpigues” com és el nombre PIN associat per a la seva utilització de forma segura.

Els dos tipus de sistemes abans citats tenen el gran inconvenient que són més o menys fàcils de falsejar, és a dir que qualsevol persona podia fer-se passar per nosaltres i aprofitar-se dels nostres privilegis en diferents serveis. El primer tipus , “algú que sàpigues” és bastant fàcil de falsejar ja que només necessitem saber el que coneix l'altra persona. Normalment el nombre PIN consisteix en una successió de nombres i lletres de 4 dígits per a poder facilitar a l'usuari la seva memorització, i els usuaris solen triar nombre que tinguin relació amb la seva persona com podria ser la data del aniversari, any de naixença i la data de l'aniversari de noces . Això fa que coneixent un mica a la persona pugui conèixer o intuir el seu nombre PIN, podent així implantar la seva identitat. Amb el segon tipus, “algú que tinguis”, encara és més fàcil ja que només cal sostreure-li aquesta targeta.

Antecedents_____________________________________________________________________________

_______________________________________________________________________

4

Després de conèixer les característiques dels mètodes més utilitzats actualment, ens podríem fer la pregunta que ja s'han fet molts experts en seguretat com podria ser: I per que no podem identificar-nos pel que som, i no per característiques externes a nosaltres com són el que sabem o el que tenim?. Aquesta pregunta té una resposta molt senzilla que és : Si que podem i es realitza a través de la biometria.

Segons el Diccionari de la Real Acadèmia Espanyola (DRAE), la biometria és "El estudio mensurativo o estadístico de los fenómenos o procesos biológicos”. Tècnicament s'entén com “biometria” les tècniques automàtiques per a l'extracció de característiques físiques que permeten ser comparades.

Com s'ha esmentat anteriorment la biometria es basa en “alguna cosa que ets”. Aquesta característica fa que sigui un mètode més segur que els anteriorment esmentats “algú que sàpigues” i “algú que tinguis”, ja que no és necessari el coneixement o memorització de cap nombre ni la necessitat de tenir cap targeta d'identificació pròpia. Ja que l'única forma d'identificar-se com un és un mateix o alguna característica inherent a la persona.

Fins a fa relativament poc temps, aquests sistemes estaven reservats a investigadors i cossos de seguretat dels diferents països i no tenien una sortida comercial molt clara, ja que el preu d'aquests sistemes era relativament car. Però els avanços tecnològics esdevinguts en els últims sis anys han fet que el cost d'aquests sistemes sigui assequible per a la seva implantació comercial.

Així, el camp de la biometria ens mostra un mètode molt més segur per a la identificació de persones. Aquesta característica és la qual permet que tingui un ús molt ampli i en diferents camps d'aplicació. Pot ser utilitzat com targeta en aeroports o bitllets de tren. També pot realitzar les funcions de contrasenyes per a l'obertura de portes o transaccions comercials. Permetent així que no pugui ser usurpada la identitat, ja que és necessària la presència física de la persona en qüestió per a una correcta identificació.

Biometria d'empremtes dactilars_____________________________________________________________

_______________________________________________________________________

5

3 Biometria d'Empremtes Dactilars

Com s'ha esmentat en el capítol anterior, la biometria s'entén des del punt de vista

tècnic com les tècniques automàtiques per a l'extracció de característiques físiques que permeten ser comparades.

La comparança es realitza a través de l'extracció o reconeixement de certes característiques pròpies de cada individu. Les característiques ens permeten obtenir una referència a comparar , que només ens donarà un resultat positiu quan la referència i les característiques a comparar són "idèntiques", podent així afirmar la identitat de l'individu a identificar.

Aquesta extracció de característiques pot ser de molts tipus, però poden ser englobats en dos grans grups de reconeixements biometrics. Els fisiològics, que poden ser l'extracció de característiques físiques de les empremtes dactilars, iris o de la cara. I les comportamentals o l'extracció de característiques de cada individu segons el seu comportament, és a dir no per trets físics de les persones si no per la forma d'escriure, signar o veu. Aquest segon grup de reconeixements només és recomanat per a sistemes amb una baix grau de seguretat ja que es tracta de característiques de les persones i no de trets físics. Això fa que sigui més fàcil la seva imitació o suplantació.

En l'apartat 3.1, es mostra un petit resum dels dos grups esmentats anteriorment i els tipus de reconeixements que actualment s'estan investigant.

La resta d'apartats es dóna una visió de quines parts formen un Sistema Automàtic d’Identificació Dactilar SAID per tal de donar una visió més global de a on estem situats.

També es comenta diversos mètodes de fer el processat de les imatges d’empremtes. Es tracta de veure com l’estimació de direccions té un ampli ventall d’aplicacions en els diferents mètodes i no el podem veure com una tasca puntual i localitzada. Tant és així , que a priori no podem dir en quin moment cal fer l’estimació de direccions. Pot fer-se al principi o durant el procés d’extracció i els seus resultats poden ser útils en processos posteriors a l’extracció dels punts característics de l’empremta.

També es comenta una mica un tema important com és la qualitat de les imatges a tractar. Es tracta de veure que sovint podem trobar imatges amb problemes locals o generals en la seva qualitat. Això pot donar lloc a errors en l’estimació de direccions i/o a l’extracció dels punts que busquem en les empremtes. Si es vol un sistema que sigui pràctic i funcional, no podem pensar pas que les imatges a processar seran imatges amb gran qualitat. Hi ha molts factors que la degraden.

El processat i extracció dels punts característics té molta importància en tot el procés d’autentificació d’un individu. Normalment, pensem en el procés de comparació de la mostra guardada i la mostra obtinguda com a procés més important. De res ens serveix un bon sistema de comparació si el procés anterior afegeix informacions falses, o pitjor encara, si en perd les autèntiques. Una característica falsa la podem filtrar, però una informació perduda no la podem generar. Per tant aquest és un pas molt important, i com veurem, l’estimació de les direccions té un pes molt gran en aquest pas.


_______________________________________________________________________

6

3.1 Reconeixements Biometrics

3.1.1 Tipus de reconeixements fisiològics

Aquest tipus de reconeixement és el de major seguretat i el qual fa gairebé impossible la seva suplantació per altre individu. A continuació es mostra un llistat dels sistemes més utilitzats i les seves característiques principals.

ADN: es tracta de comparar la cadena de ADN de cada individu per a la seva identificació. Cada individu té la seva pròpia cadena de ADN, llevat de l'existència de bessons idèntics que a priori tindrien la mateixa cadena de ADN. Aquest sistema és el més utilitzats pels mèdics forenses a l'hora de realitzar identificacions de cadàvers. El sistema a priori sembla el més segur, però depenent de l'aplicació que es realitzés deixaria de ser-ho, ja que tot individu deixa el rastre del seu ADN, ja que es pot extreure mostres de ADN de gotes de sang, saliva, etc.. De totes maneres avui dia realitzar un sistema d'identificació mitjançant ADN d'una forma comercial és inviable, ja que és un mètode molt agressiu, d'una tecnologia molt cara i un alt temps d'execució.

Orella: Es tracta del reconeixement de l'estructura física del pavelló auditiu. Es basa en identificació dels punts del pavelló auditiu més allunyats del centre de l'orella i de les característiques remarcables. Aquest mètode té l'inconvenient de ser bastant molest per als usuaris, ja que és necessari extreure una imatge de l'orella i a més, es necessitaria extreure un patró de cada individu cada cert temps, ja que les orelles són unes de les poques parts del cos humà que creixen al llarg de tota la vida. Es tracta d'un sistema de seguretat mig- baix.

Cara: El reconeixement de la cara és un dels mètodes biometrics més acceptats, ja que és el mètode que utilitzen les persones a l'hora de realitzar una identificació visual. Aquest mètode no és gens molest per a l'usuari, ja que és molt fàcil aconseguir una imatge de la cara . Aquests sistemes són capaços de reconèixer expressions de la cara i postures fent una adquisició en 2D o 3D.El principal inconvenient del sistema és que es veu afectat per canvis d'imatge de l'usuari, ja sigui un pentinat diferent, canvi de models d'ulleres, etc. Aquest sistema mostra un índex de seguretat mig alt.

Fotografia tèrmica de mans, rostre: Aquest sistema es basa a extreure una fotografia tèrmica del rostre, de les mans, peus i fins a de el cos d'una persona. És característic de cada individu tenir zones més o menys calentes en el nostre cos encara que existeixin zones comunes entre tots. Això permet realitzar una identificació segons els punts calents i freds de cada individu. El major inconvenient d'aquest sistema és que pot descartar reconeixements a causa de factors meteorològics externs que farien variar la presència de punts calents i freds en la fotografia tèrmica o l'estat de salut de l'usuari, ja que la presència de febre podria invalidar el reconeixement. Aquest sistema té un grau de seguretat mig-alt segons el tipus d'aplicació.

Geometria de Mans i Dits: Aquesta tècnica identifica la forma característica de les mans o dits de cada individu. Ja que normalment són invariants i particulars. Identificant la forma de cada mà o dit així com la seva longitud i grossor característics. El major inconvenient d'aquest sistema és la major necessitat de la col·laboració de l'usuari i el seu alt cost, ja que necessita de molta quantitat de memòria i de poder de calculo per a la seva aplicació. És un sistema d'alt grau de seguretat.


_______________________________________________________________________

7

Iris: el iris es forma en el nostre estat embrionari i és invariable en el temps. Existeix una imatge diferent del iris per a cada ull i per a cada individu. És un sistema gens agressiu. Aquesta tècnica necessita d'una major cooperació de l'usuari. Ja que la imatge ha de ser presa d'una forma concreta perquè els resultats siguin acceptables. Es tracta d'un sistema d'alta seguretat, però el seu principal inconvenient és el seu elevat preu, ja que per a la seva aplicació és necessari equips molt precisos.

Escàner de Retina: Cada retina té una estructura particular i és diferent per a cada ull i per a cada individu. Aquesta tècnica esta cridada a ser la més segura, ja que és molt difícil el seu canvi o suplantació. Necessita una gran cooperació de l'usuari per a realitzar l'escàner de la retina i avui dia la tècnica per a extreure la imatge de la retina no és aconsellable realitzar-la a persones amb hipertensió. El major inconvenient d'aquest sistema és el seu elevat preu, ja que es necessita de materials tecnològicament avançats i precisos fent inviable el seu ús en aplicacions comercials.

3.1.2 Tipus de Reconeixements Comportamentals

Aquest tipus de reconeixement és el de menor seguretat i el qual pot ser imitat amb facilitat. A continuació es mostra un llistat dels sistemes més utilitzats i les seves característiques principals.

Gait (forma de caminar): cada persona té una forma de caminar característica, encara que no és única per a cada individu. Aquesta tècnica no s'utilitza per a realitzar un reconeixement segur de l'individu, però si que ens serveix per a descartar-ne alguns. Aquesta tècnica és utilitzada per a extreure característiques d'enregistraments d'individus en vídeos, que permetin d'aquesta forma trobar algun sospitós.

Keystroke dynamics ( forma de teclejar): aquest sistema es basa en la hipòtesi que cada persona tecleja d'una forma característica. Encara que no fos així, ens permet recopilar informació per a discriminar o acceptar possibles sospitosos en una investigació, després d'un monitoratge de la seva forma de teclejar característica.

Olor: és conegut que cada objecte té una olor. Aquesta olor es pot caracteritzar segons la seva composició química, i això ens pot permetre identificar diversos objectes. L'olor emesa per un individu o un animal és característic de si mateix. El que no esta clar és si es podria aïllar l'olor de cadascú quan aquesta barrejat amb perfums, desodorants i l'olor característica de cada zona.

Signatura: és conegut que cada persona signa d'una forma característica i que no hi ha dues signatures iguals. Aquesta tècnica és vàlida o esta acceptada per molts governs i en transaccions comercials. Però també és conegut que una mateixa persona pot signar d'una forma diferent segons el seu estat d'ànim i que existeix gent que és capaç de falsificar una signatura amb molta exactitud, fins al punt que no existeixin diferències per a l'ull humà.

Veu: el reconeixement de veu, mitjançant un enregistrament, és acceptable per molts tribunals del món. Però realitzar un sistema de reconeixement automàtic és bastant complicat, ja que el patró a guardar hauria de ser molt gran i la comparança amb una base de dades gairebé inviable. També té en contra que la veu ens canvia segons l'estat de salut de cadascun (refredats, amb febre, etc. ). I també la qualitat de la veu pot empitjorar al gravar-los a través de micròfons, etc.


_______________________________________________________________________

8

3.2 Empremtes Dactilars

Segons el Diccionari de la Real Acadèmia Espanyola (DRAE), l'empremta dactilar és la impressió que sol deixar el palpís del dit en un objecte al tocar-lo, o la qual s'obté impregnant-la prèviament en una matèria colorant.

Aquesta definició és correcta, però per a conèixer millor que representa tècnicament l'empremta dactilar és necessari comentar alguns conceptes referents a la morfologia de la pell en la zona dels dits de la mà, ja que l'anàlisi de les imatges capturades per dispositius adequats en aquesta zona serà la tècnica que ens permetrà realitzar una verificació o una identificació personal.

Lofoscopia: Etimològicament significa examen de les crestes papilars (lophos: crestes i skopia: examen). Mes correctament es considera a la Lofoscopia a la ciència que estudia les crestes papilars amb fins identificatius (curiosament aquesta paraula no està oficialment acceptada pel DRAE) .

Dactiloscopia: Etimològicament prové del grec (daktilos:dits i skopia: examen), és per tant la part de la lofoscopia que estudia les crestes papilars en la zona del palpís dels dits. Atès que la majoria dels estudis sobre lofoscopia se centren en aquesta zona, en l'àmbit criminalista ambdues paraules s'utilitzen com sinònims.

3.2.1 Crestes papilars.

3.2.1.1Definició de cresta papilar.

La pell humana és una membrana que protegeix a tots els sistemes orgànics dels agents externs que poden afectar-los. Està formada per dues capes: la epidermis (zona de gràfic marcada com 1), capa més externa on es realitzen els processos de regeneració de la pell i es troben les cèl·lules pigmentaries; i la dermis (zona 2), capa més interna on es troben les papil·les, petites prominències i plecs que disposa la dermis a fi d'augmentar la seva superfície sensible i la seva capacitat d'evacuació vascular.

Figura 3.1: Secció de la pell del palpís de les mans.

(1) epidermis

(2) dermis.

La forma de les papil·les és molt variable i el seu nombre mig és de 36 per centímetre quadrat. La seva grandària oscil·la entre 55 i 225 micras. En les mans i peus, aquestes papil·les s'alineen formant unes estructures anomenades crestes papilars. Aquest és el dibuix que observem en els palpís dels nostres dits i en els palmells de les mans i plantes dels peus. Entre cada dues crestes papilars queda una depressió longitudinal cridada solc interpapilar o vall, l'ample de la qual oscil·la entre 0,2 i 0,5 mil·límetres. A l'estar format en la dermis, aquest dibuix no es veu afectat per accions externes, tret que aquestes siguin prou profundes (acció d'àcids, treball manual agressiu continuat, accidents, etc.).


_______________________________________________________________________

9

3.2.1.2 Classificació de crestes papilars.

Les crestes papilars es poden agrupar en els següents tipus segons sigui la forma predominant que presentin :

Rectes. Aquelles el traçat de les quals és recte (Figura 3.2). Se solen trobar en la base dels dactilogrames.

Figura 3.2: Cresta Papilar.

Figura3.3: Crestes arciformes.

Arciformes. Crestes que formen un arc de circumferència (figura 3.3).

Anguloses. Crestes que tendeixen a formar un angle (figura 3.4). Solen trobar-se en dactilogrames anucleats.

Figura 3.4: Crestes anguloses.

Figura 3.5: Crestas verticilares.

Verticilares. Crestes que formen un cercle o espiral atropellant-se sobre si mateixes (figura 3.5).


_______________________________________________________________________

10

3.2.1.3 Factors que influeixen en les crestes papilars.

Existeixen tres factors que influeixen en les característiques de les crestes papilars, podent determinar el seu grossor i fins i tot un patró de la seva forma:

Edat: Els dibuixos papilars no sofreixen cap modificació amb el pas del temps; no obstant això, el grossor tant de les crestes com dels solcs, augmenta amb l'edat. En general es poden distingir tres grups d'edats: individus d'edat inferior a catorze anys, entre catorze i seixanta-cinc i individus amb més de seixanta-cinc anys.

Sexe: La diferència entre les crestes papilars de l'home i de la dona és el grossor. En general, les dels homes són més gruixudes que les de les dones, pel que coneixent l'edat de l'individu es pot determinar el sexe d'una persona a partir de la mesura del grossor de les seves crestes papilars.

Herència: Encara que cada persona té un dibuix papilar diferent, fins i tot entre bessons, sí està demostrat que entre persones de la mateixa família hi ha una tendència a reproduir patrons de forma en els dibuixos papilars. A més, existeixen una sèrie de característiques personals que poden afectar en gran mesura a les impressions dactilars. Referent a això podem citar:

Professions especials: existeixen determinats professionals el treball de les quals es realitza exposant els seus dits a un intens agent corrosiu (àcid, desgast per fregament, etc.). En aquestes persones és molt difícil realitzar cap tipus d'estudi ja que poden arribar a mancar gairebé completament del dibuix papilar.

Accidents: evidentment el que major impacte representa seria la amputació completa de la primera falange. Sense arribar a aquest extrem existeixen una gran varietat dels mateixos (cremades, ferides profundes, etc.) que poden afectar al dibuix papilar.

Malalties: algunes malalties provoquen alteracions epidèrmiques greus que afecten a les falanges dels dits. Entre les més usuals es pot citar la hiper o hipohidratació, sindactilia, polidactilia, etc.


_______________________________________________________________________

11

3.2.2 Dactilogrames

3.2.2.1 Definició de dactilograma

Un dactilograma és el dibuix format per les crestes papilars del palpís d'un dit de la mà d'una persona. Els dactilogrames poden ser de dos tipus:

Naturals. És el dibuix que formen les crestes en la pròpia pell. Des d'ara es denominaran empremtes dactilars.

Artificials. Reproducció del dibuix sobre una superfície per contacte directe de les crestes, prèviament recobertes d'una substància capaç de romandre sobre el suport. Quan la substància és la suor es denomina dactilograma latent. Des d'ara es denominaran impressions dactilars.

3.2.2.2 Sistemes dactilars.

Es denomina sistema dactilar a cada part que pot dividir-se un dactilograma. Existeixen tres sistemes dactilars (figura 3.6):

Sistema basilar: Zona entre la segona i tercera falange, excepte per al dit polze, on es troba entre la primera i segona falange. Normalment les seves crestes són horitzontals, paral·leles al plec de flexió de la falange.

Sistema marginal: Zona més exterior del dactilograma. Normalment correspon a la zona de la punta dels dits i les vores del mateix. Les seves crestes solen ser anguloses.

Sistema nuclear: Zona compresa entre el sistema basilar i el marginal. Conté el centre de la impressió dactilar (nucli) i la major part dels punts característics del dactilograma.

No tots els dactilogrames poden dividir-se completament en aquestes tres parts. Existeix un tipus especial de dactilograma que manca de sistema nuclear i en el qual, per tant, també és difícil establir un límit entre el basilar i el marginal. A aquests dactilogrames se'ls denomina anucleats (figura 3.7).

Figura 3.6: Sistemes dactilars:

marginal, basilar y nuclear.

Figura 3.7 Dactilograma anucleat.


_______________________________________________________________________

12

3.2.2.3 Punts característics

Segons les formes que presenten les línies que formen una empremta podem establir diferents classificacions. Al 1892 el senyor F. Galton [1], [2] va presentar una classificació on introduïa el concepte de minúties, referint-se a les diferents estructures morfològiques que es poden donar en les empremtes. A part, també va evidenciar el fet de que l’empremta manté la seva estructura des del moment del naixement fins a la mort. També va arribar a la conclusió que les empremtes eren úniques per cada individu.

Les minúties són els punts que buscarem a l’hora de fer una comparació entre empremtes. Val a dir que hi ha diversos mètodes de comparació. Alguns poden comptar les línies entre diferents punts característics i d’altres comparar directament aquestos punts. Sigui com sigui, necessitem identificar aquestos punts. Aquests punts són les referències per fer la comparació. A partir d’ara ja no parlarem de línies de l’empremta i ens referirem a valls i crestes. Entenent com a vall la part que queda més endinsada de la pell i cresta o crestall la que sobresurt més.

Així doncs en funció de les diferents configuracions que formen les crestes d’una empremta podem parlar de diferents punts característics. Les figures següents ens les mostren. Per cada configuració es dóna la freqüència amb la que es produeixen. Tot i el temps que ha passat encara s’utilitza la classificació de Galton de descripció de minúties. Les següents figures mostren les principals configuracions.

Punt final. Final abrupte d’un crestall (figura 3.8). Representen el 56,3 % de les minúties que podem trobar. En la figura es mostren tres d’aquestos punts denominats A, B i C.

Figura 3.8: Punt final.

Figura 3.9 Punt de bifurcació.

Bifurcació. Punt en el que un crestall es transforma en dos crestes. També es pot parlar de la convergència de dos crestes en una. Representen el 30,5 % dels punts característics. En la figura 3.9 són els punts A i B.


_______________________________________________________________________

13

Punt aïllat. Es tracta d’un fragment de crestall que té la mateixa longitud que amplada (figura 3.10). En podem trobar en una proporció que volta el 2,1% de totes les minúties. En la figura es corresponen als punts A i B. No acostumen a utilitzar-se per la facilitat de ser confosos amb soroll de la imatge.

Figura 3.10 Punt aïllat.

Figura 3.11: Punt secant.

Secant. Punt format per dos crestalls que es tallen formant uns altres dos crestalls (figura 3.11). Representen el 1% dels punts. En la figura es marca com a punt A. Són molt depenents del soroll i per tant no s’utilitzen en els SAID (Tot i ser molt emprat per els especialistes si es fa una identificació visual).

Hi ha més punts característics (desviació, ponts, illes, trifurcacions, etc.) i representen el 7,1%. A efectes de la verificació i identificació automàtica sols es consideren els punts finals i les bifurcacions. Aquestos punts formen ja la gran majoria dels punts característics i sovint, alguns dels altres punts els podem posar en funció d’aquestos dos. Curiosament, si el sistema no és automatitzat i es fa un anàlisi visual de les empremtes ens interessen més els punts menys freqüents ja que ens permeten discriminar de forma més ràpida. En canvi, els casos més particulars i més sensibles a ser confosos amb soroll no ens van gens bé per a sistemes automatitzats.

Un cop vistos els punts característics podem passar a veure uns altres punts que, tot i que no són estrictament punts de la imatge ens poden servir per referenciar certes zones de la imatge d’una manera ràpida.


_______________________________________________________________________

14

3.2.2.4 Punts singulars: Deltas i Nuclis

A més del punts anteriors podem parlar de dos tipus més denominats punts singulars. Aquestos punts tenen gran utilitat per poder classificar les empremtes. En el nostre cas no són punts que necessitem buscar. Però sovint en farem referència ja que són zones on les direccions varien de forma ràpida i poden afectar en les nostres estimacions.

Aquestos punts formen part de l’estudi que el senyor E. Henry [1], [3] va fer al 1900. Va ser ell qui va fer un anàlisi de l’empremta d’una manera més global, on es fixava més en l’estructura i els sentits predominants de les crestes. Va definir, el que posteriorment s’ha denominat el “Henry System” on es feia una classificació general que permet dividir en diversos grups les empremtes. Això facilita el seu processat ja que podem descartar els grups que no són el que busquem. Les classes són: Right Loop, Left Loop, Whorl, Arch i Tended Arch. La figura 3.5 seria una de tipus Right Loop per exemple. Les figures següents mostren els altres punts característics als que hem fet referència.

Nucli. Centre no geomètric del sistema nuclear. En la figura 3.12 es representa la zona envoltada amb un cercle. Normalment acostuma a ser el punt més alt del crestall central, al voltant del qual apareix la resta. Aquesta definició fa complexa la seva extracció de forma automàtica tot i que visualment és molt senzill d’identificar.

Figura 3.12: Punt nucli.

Figura 3.13 Punt delta.

Delta. Punt de trobada on convergeixen tres direccions ben diferenciades que són rodejades per altres que tenen la mateixa direcció(figura 3.13). Normalment es tracta d’un punt de bifurcació en la zona de confluència de diverses rames separades per uns 120º, tot i que pot tractar-se també del centre d’una figura triangular. No totes les empremtes en presenten en les parts més properes a la gema dels dits. Visualment és de fàcil identificació també.


_______________________________________________________________________

15

3.2.3 Utilitat de la impressió dactilar com a element identificatiu

Una impressió dactilar pot utilitzar-se amb fins identificatives degut, fonamentalment, a tres propietats de les crestes papilars:

Perennitat: Les crestes es mantenen en la pell durant tota la vida (excepte traumatismes greus). L'única diferència en el dibuix papilar d'una persona durant el seu creixement és el canvi en la grandària i amplària de les crestes, però no en la seva disposició espacial ni en la seva tipologia.

Inmutabilitat: Les crestes són invariables en nombre, forma, situació i adreça. Cap malaltia modifica els dibuixos. En tot cas, perquè puguin ser destruïdes total o parcialment, l'agent extern ha de ser capaç d'arribar fins a la dermis, ja que és en aquesta capa més interna de la pell on es formen les crestes.

Diversitat: Els dibuixos són diferents per a cada persona i per a cada dit d'una mateixa persona. Fins i tot són diferents els dibuixos entre bessons.

Per tant, si disposem d'una impressió dactilar que sabem que correspon a una persona determinada i la comparem amb una altra impressió, podrem estar segurs que aquesta última pertany a la persona en qüestió si aquesta comparança resulta positiva.


_______________________________________________________________________

16

3.3 Sistema Automàtic d’Identificació Dactilar

Un Sistema Automàtic d’Identificació Dactilar (SAID) és, tal i com es pot interpretar del seu nom, un conjunt d’equips físics i lògics que permeten la verificació o identificació d’una persona a partir de l’anàlisi de les seves empremtes dactilars.

El SAID té bàsicament tres modes de treball en la identificació personal mitjançant empremtes:

- Mode registre: en aquest mode, es fa l’extracció de les característiques de les empremtes i es guarden per poder ser comparades en un altre moment.

- Mode de verificació: en la que dues impressions (una d’una persona coneguda i una altre d’algú desconegut) es comparen per tal de saber si la identitat de la segona persona correspon a la de la primera.

- Mode d’identificació: en la que es disposa de l’empremta d’una persona desconeguda i d’una base de dades més o menys voluminosa, d’empremtes. Cal identificar a la persona fent la cerca per la base de dades.

També rep el nom de mode reconeixement quan el SAID treballa en mode de verificació o identificació.

Els SAIDs independentment del seu mode de funcionament en el que treballen tenen diversos blocs en comú per extraure la informació de les empremtes:

- Captura (“Image Acquisition”): Procés d’adquisició de la imatge d’una empremta per a la seva introducció en un sistema de processat de imatge. Podem pensar-ho com el sensor i condicionador del senyal.

- Processat de la imatge (“Image Processing”): Tasques que es realitzen per tal de millorar la qualitat de la imatge capturada. Bàsicament es tracta d’una sèrie de filtres que s’apliquen per eliminar sorolls, millorar-ne el contrast. Eliminar zones poc definides, ... etc.

- Extracció de característiques (“Feature Extraction”): Adquisició, a partir de la imatge prèviament filtrada, de les característiques intrínseques a l’empremta dactilar. Aquestes no haurien de dependre del mètode utilitzat per adquirir la imatge, ni tampoc dels valors de la imatge original, sinó que provenen d’un estudi topològic de la imatge. Per a fer l’extracció de les característiques, cal fer prèviament un “model d’impressió dactilar”. Aquest, estarà format per un model de representació de les característiques i per un sistema de referència que permeti especificar-ne les posicions relatives de les mateixes. És a dir, en aquest punt és on decidim quines minúties tractem. Normalment, bifurcacions i finals de cresta.

- Comparació o cerca (“Matching”): Aquesta és l’etapa que determinarà si l’empremta dactilar que tractem pertany a la mateixa persona que l’empremta de referència. El model original es compara amb el de referència, establint-ne, a partir de la mesura de distància prèviament realitzada, un valor d’identitat. En el cas d’identificació, aplicant aquest sistema en tota la base de dades s’obté un petit conjunt de candidats (normalment menys de 20) sobre els que l’operador realitza una comprovació un a un de forma manual.


_______________________________________________________________________

17

La figura següent ens mostra un petit esquema dels modes de funcionament d’un SAID i dels blocs que el composen.

Figura 3.14: Modes de funcionament d’un SAID.

Tal i com es pot veure en la figura anterior, en la fase de registre ( “enrolment”) el sistema fa la mesura de les característiques biomètriques de l’usuari (“image adquisition”). A partir d’aquesta mesura se n’extreu un codi o template que s’associa a la identitat de l’usuari (“feature extraction”). La mida d’aquest codi no acostuma a superar 1 Kbyte de memòria, i es guarda (“storage”) en una base de dades com a codi identificador ID. A partir d’aquest instant, l’usuari queda donat d’alta en el sistema d’autentificació.

Durant la fase de reconeixement (“recognition”), el sistema torna a mesurar (“sample”) las característiques biomètriques de l’usuari, i es repeteix el procés d’extracció del codi d’identitat. Aquest codi es compara (“matching”) amb el codi d’identitat o “template” prèviament guardat en la fase de registre, a fi i efecte d’autentificar la identitat de l’usuari en funció del grau de similitud de les dues mostres.

Aquesta ultima part de Matching es en la que es centra el projecte, l'objectiu serà crea un programa matching per a la comparació d'un template i un sample.

ENROLMENTIMAGE ACQUISITION

(Biometrics)

(Sample)

IMAGE PROCESSING(Enhancement)

FEATURE EXTRACTION(Signature)

STORAGE(Template)

RECOGNITIONIMAGE ACQUISITION

(Biometrics)

IMAGE PROCESSING(Enhancement)

FEATURE EXTRACTION(Signature)

RESULT(Yes / No)

(Sample)

MATCHINGTemplate = Sample?


_______________________________________________________________________

18

3.4 Adquisició d' empremtes dactilars

La tecnologia actual de sensors biometrics d'empremtes dactilars abasta un ampli ventall de possibilitats, cadascuna d'elles fonamentada en fenòmens físics diferents. Sensors òptics (càmeres CMOS o CCD), ultrasònics (adquisició de la imatge dèrmica de la petjada), basats en RF o micro-electro-mecànics (microswitches) són algunes de les possibles alternatives d'implementació. A pesar d'això, i amb la finalitat de centrar-nos en embedded systems de baix cost, en aquest apartat només s'esmenten aquelles tecnologies de sensors dactilars que permeten la seva integració en silici: els cridats silicon xip sensors.

Es coneixen tres tipus diferents de sensors on-xip. Tots ells permeten capturar una imatge digital de l'empremta dactilar per simple contacte d'aquesta amb la superfície del sensor:

Sensors de pressió. Basen el seu funcionament en l'efecte piezo-elèctric. A partir d'un array de píxels constituït per material sensitiu a pressió és possible captar un patró de la petjada aplicada sobre el sensor. A pesar dels seus nombrosos desavantatges (baixa sensibilitat, incapacitat de diferenciar dits reals d'artificials, susceptibilitat a danyar-se per excés de pressió...) alguns fabricants s'inclinen per aquesta opció.

Sensors capacitius. És en l'actualitat una de les tecnologies més populars, basada en les propietats del camp elèctric. El dit i la làmina sensora constitueixen un condensador, el dielèctric del qual és variable acord a la pròpia discontinuïtat de les crestes i les valls de la petjada. És aquesta variació del dielèctric la qual permet capturar les característiques de l'empremta dactilar. El seu principal inconvenient és, sens dubte, la seva excessiva vulnerabilitat a descàrregues electrostàtiques.

Sensors tèrmics. Són sensors basats en l'efecte piroeléctric: el material piroeléctric del sensor permet convertir les diferències de temperatura originades per les ondulacions de la petjada en contacte o no amb el sensor (crestes o valls respectivament) en diferències de tensió. Aquests nivells de tensió són finalment traduïts, mitjançant un convertidor A/D, en un escalat de grisos dels píxels que constituïxen la imatge de l'empremta dactilar adquirida. A més de la seva forta immunitat a descàrregues ESD, destaca el fet que l'equilibri tèrmic entre el sensor i la petjada es produeix en un temps molt breu, la qual cosa fa que la imatge s'esvaeixi de seguida, i s'evita la deposició d'imatges romanents sobre la superfície del dispositiu sensor un cop feta la lectura.


_______________________________________________________________________

19

h) Ejemple d'imatge captada amb sensor de pressió

e) Ejemple d'imatge captada amb sensor capacitiu

g) Ejemple d'imatge captada amb sensor tèrmic

Figura 3.15: Ejemples de captures realitzades per sensors on_chip.

En funció de la fracció de petjada capaç de capturar instantàniament el sensor, aquests es classifiquen en dos tipus: sensors complets, aquells que permeten capturar la porció de petjada requerida de forma instantània, i sensors de scan o sweeping, en el cas d'aquells que requereixen un escombrat seqüencial de la petjada.

Els sensors complets, de dimensions tals que cobreixin la porció de petjada necessària, permeten capturar la imatge total de forma estàtica i instantània. A pesar de permetre adquirir la imatge completa, el desavantatge d'aquesta tecnologia es troba en la grandària del sensor i per tant en el cost del mateix , a més de la problemàtica en matèria de seguretat ocasionada si la imatge de la petjada es manté latent damunt de la superfície sensora fins i tot després de retirar el dit del sensor.

Figura 3.16: Sensor Complet.


_______________________________________________________________________

20

El segon plantejament consisteix a reduir el sensor a una làmina que comprèn l'ample de la petjada però solament escassos píxels d'altura. En aquest cas l'adquisició completa de la imatge es produeix de forma dinàmica i seqüencial, a mesura que l'usuari llisca el seu dit sobre la superfície sensora. A través d'aquest escombrat es capturen en sèrie i solapades les diferents llesques horitzontals que constitueixen la petjada. Encara que això suposarà un processat addicional per a reconstruir la imatge, el principal avantatge es troba en el seu cost, no només per la pròpia grandària del sensor sinó principalment per qüestions d'optimització de l'originària hòstia de silici. En aquest cas a més no apliquen els problemes de la permanència d'imatges romanents de la petjada sobre la superfície del sensor.

Figura 3.17: Sensor Parcial.

En general, indistintament de la tecnologia de lectura empleada, s'acostuma a treballar amb resolucions de 500 dpi (grandàries dels píxels de 50µm x 50µm). En referència a l'escalat o digitalització de la imatge adquirida, s'usen convertidors A/D de 8 bits, el que suposa un rang en escala de grises de 256 nivells.


_______________________________________________________________________

21

3.5 Processat de les imatges

En aquest apartat es comenten diferents mètodes que s’acostumen a utilitzar per al processat de les imatges per tal de poder extraure’n després els punts característics de l’empremta, com ja s’ha dit anteriorment aquest és un pas important, ja que d’ell en depèn totalment la quantitat i la qualitat de la informació que podem extraure d’una empremta. A partir d’ara sempre que ens referim a una imatge l’hem de suposar com una imatge en escala de grisos que són les imatges en que treballa el grup d’investigació donats la mena de sensors que es volen utilitzar.

També cal dir que aquest, junt amb el procés de matching és un procés que necessita gran part del temps d’execució de tot el procés d’identificació

El sistema més utilitzat per al processat d’imatges és el de binarització i esqueletització. A base de diferents filtres i processos, es passa a una imatge binària en la que és molt senzill traure’n les minúties. Tot i així, existeix un altre mètode que és el que està utilitzant el grup de recerca que es basa en l’extracció directa de minúties sobre la imatge tractada. Aquest mètode no utilitza filtres globals per tota la imatge, el que el converteix en un mètode més ràpid o menys costós en temps de càlcul.

Primerament comentarem el mètode de binarització-esqueletització i després l’altre mètode al que ens referim com a algorisme d’extracció de Maio.

Tant en un cas com en l’altre, però, es fan estimacions de la direcció. Aquí doncs ja començarem a veure allò que anteriorment s’ha dit de que l’estimació de direccions no la podem veure com un pas puntual i local ja que pot tenir diferents usos.

De les minúties detectades sortirà l'entrada al nostre programa match i serà apartir d'aquí on començarà la funció del projecte.


_______________________________________________________________________

22

3.5.1 Mètode de Binarització-Esqueletització

Tal com s’ha dit anteriorment aquest mètode es basa en l’aplicació de diferents filtres per tal d’obtenir una imatge de prou qualitat per a ser binaritzada. Un cop fet això es passa per un procés que deixa les crestes amb una amplada d’un píxel i elimina elements sorollosos. Així doncs, és un procés de diferents blocs encadenats. Els processos més habituals als que es sotmet la imatge són: Realçar les vores, binarització , segmentació, esqueletització i poda.

3.5.1.1 Realçar les vores

En aquest procés la imatge es sotmet a diferents filtres de millora per realçar les crestes, donant lloc a imatges més nítides i contrastades. Així, el procés de binarització podrà funcionar de forma correcta. Els tipus de filtre que es poden aplicar són molt diversos, en el nostre cas ens interessa parlar dels filtres direccionals. Aquestos no tenen màscares simètriques en totes les direccions sinó que actuen de manera diferent en funció de l’orientació amb que s’apliquen. Un exemple podria ser el filtre de Gabor. Si orientem el filtre en el mateix sentit de les crestes obtenim una eliminació de sorolls i un contrast notablement millorat. Per poder aplicar aquest filtre però, cal conèixer prèviament quina és la direcció del segment que estem filtrant en cada moment. Per tant, aquí ja es veu una necessitat d’estimar les direccions com a primer pas. Normalment els filtres que s’utilitzen no acostumen a ser els filtres generals de contrast que s’utilitzen en altres tipus d’imatges i acostumen a estar dissenyats per a ser utilitzats en imatges d’empremtes.

Figura 3.18: Exemple de realçar vores.


_______________________________________________________________________

23

En les figures següents es mostra el resultat d’aplicar un filtre de Gabor sobre una imatge. Tal com es pot veure el resultat té un augment de contrast molt gran. Tot i així encara estem en escala de grisos, si ens fixem bé en la imatge filtrada podem veure la zona marcada amb una A que té nivells de gris mitjos. Al primer cop d’ull dóna uns resultats molt bons. Elimina molt bé els nivells de gris contrastant molt la imatge. També ha tret els pors que tenen les crestes eliminant molt bé el soroll. Però val a dir que l’aplicació incorrecta d’un filtre tant potent ens pot portar problemes i pèrdues d’informació. S’han marcat alguns casos que són interessants. Si apliquem el filtre mal orientat ens unirà crestes properes donant uns resultats que a simple vista seran bons. Per tant, aquí, fer una estimació incorrecta de la direcció pot tenir greus conseqüències.

Aquí podem veure dues vistes d’un filtre de Gabor. Si l’imaginem amb els lòbuls orientats amb les crestes d’una empremta podem imaginar com filtra fent mitjanes sobre les crestes eliminant soroll i contrastant notablement les crestes de les valls.

Aquí podem veure la imatge original i la filtrada. En la filtrada s’han marcat algunes zones interessants (Punts A,B,C,D i E on el filtre no acaba de fer el que voldríem donat que l’orientació o amplada no era correcta o no era l’òptima.

Figura 3.19: Exemple filtre de Gabor.


_______________________________________________________________________

24

3.5.1.2 Binarització

Aquest procés fa una transformació de la imatge filtrada en escala de grisos a una imatge en format binari on les zones més fosques tenen un valor 1 i les més clares un valor 0. Aquest procés és crític i cal escollir amb precaució el llindar per tal d’evitar perdre informació de manera irreversible. Normalment les imatges a tractar en la binarització no són com la imatge filtrada de l’apartat anterior, ja que aquesta s’ha tractat amb un filtre molt potent i no estan tan contrastades.

Figura 3.20: Exemple de binarització: Original, filtrada i binaritzada.

Donat que per moltes raons el contrast pot ser molt diferent en diverses zones de la imatge a vegades s’apliquen llindars diferents segons la zona que es tracta. Això comporta més càlculs per tal de trobar el llindar adient per cada zona.

3.5.1.3 Segmentació

La imatge binaritzada obtinguda en el procés anterior encara no és vàlida per al procés d’extracció de minúties. Cal sotmetre a la imatge a una segmentació per tal d’eliminar aquelles zones on hi ha segments inconnexes o zones afectades per molt soroll que en els passos anteriors no s’han pogut evitar. També cal eliminar grans zones blanques o fosques on no hi havia contacte o era massa intens. Si fem això traurem un gran nombre de segments tallats que ens donarien un munt de minúties que realment no existeixen. Una possible manera de determinar aquestes zones és mirant si les estimacions de les direccions fetes en una zona petita presenta gran diversitat de direccions. En general no ha de ser així i això ens indicaria que estem en una zona a eliminar del nostre procés d’extracció.


_______________________________________________________________________

25

El pas de segmentació, tot i que aquí s’ha presentat després de la binarització, en la majoria de casos és un dels primers passos que es fan, sovint el primer. D’aquesta manera podem evitar tractar les zones de la imatge que no ens aporten informació reduint la zona a tractar. Però donat que el podem trobar també en aquest moment es comenta ara aprofitant que ja s’ha parlat de la binarització. Realment en qualsevol moment podem decidir no tractar una zona per qualsevol motiu i això és segmentar. El millor és fer-ho el més aviat possible per evitar fer tractaments en zones que posteriorment podem descartar.

Figura 3.21: Exemple de segmentació.

3.5.1.4 Esqueletització i Poda

Aquest ja és l’últim procés que es realitza abans de passar a l’extracció de minúties. En aquest pas, les imatges binaritzades es passen per un algorisme que, a base d’aplicar erosions controlades, transforma les crestes binaritzades en crestes d’amplada d’un sol píxel. A aquest procés se l’anomena esqueletització.

El procés d’esqueletització es completa amb un procés de poda per eliminar branques paràsits que puguin quedar. En general les imatges de les empremtes tenen les vores amb força soroll. Això fa que es generin branques no desitjades en l’esqueletització. Així doncs aquest pas té per objectiu netejar aquestes branques sense desconnectar bifurcacions reals.

En la figura 3.22 podem veure els passos d’esqueletització i poda a partir d’una imatge binaritzada i segmentada. En principi aquí les direccions de les crestes no s’utilitzen. De totes maneres en el pas d’extracció de minúties pot utilitzar-se per guardar com a part de la minútia la direcció que porta el crestall. És a dir, no sols podem guardar la seva posició relativa sinó també la seva direcció. Per tant veiem que poden intervenir en força moments del processat.


_______________________________________________________________________

26

(a) Imatge binaritzada i segmentada

(b) Esqueletització

(c) Poda

Figura 3.22: Exemple de preparació de la imatge per l’extracció de minúties


_______________________________________________________________________

27

3.5.2 Extracció de minúties

Tal com ja s’ha dit, hi ha diversos punts característics en una empremta. Aquí però, al igual que en la majoria de bibliografia consultada, sols considerem les bifurcacions i els finals de cresta.

Un cop tenim la imatge en la que hem fet l’esqueletització i poda sols ens queda seguir l’estructura de l’esquelet de la imatge. Aquest seguiment s’obté fent un seguiment dels punts a estudiar tal com es mostra en la figura 3.23. El funcionament és força senzill. Sols cal mirar el nombre de píxels negres en una finestra de 3x3, on el punt central sigui un punt a estudiar. Si en aquesta finestra hi ha un sol punt negre (No es compta mai el punt central d’estudi) es tracta d’un final de cresta (Cas b). Si hi ha dos punts negres és un punt intermig d’un crestall (Cas a) i si hi ha tres punts en negre, vol dir que es tracta d’una bifurcació (Cas c).

Figura 3.23: Identificació de minúties.

Un cop s’acaba el procés d’extracció, sovint encara cal aplicar un pas més per tal d’eliminar algunes minúties falses que ens han pogut quedar al aplicar tots aquestos passos. Es tracta de fer un filtrat estructural ja que així les podem trobar fàcilment en la imatge esqueletitzada. Així doncs es filtren, com podem veure en la figura 3.24: Crestes que tenen punts finals encarats (a, b), bifurcacions encarades amb punts finals (c) o amb altres bifurcacions (d), alguns punts esporàdics (e), ponts (f), triangles (g) i estructures quadrades tipus escala (h). Òbviament cal fer-ho amb minúties molt properes entre elles.

Figura 3.24: Filtrat estructural.


_______________________________________________________________________

28

3.6 Aparellament d’empremtes

Una vegada filtrada l’empremta, es procedeix a buscar la coincidència amb les empremtes emmagatzemades a la base de dades. Les empremtes poden tenir una primera classificació segons el patró general per a reduir el temps de la recerca i la complexitat de còmput (la base de dades de la FBI conté aproximadament 70 milions d'empremtes dactilars). Així, existeix la classificació d'Henry, que distingeix 5 tipus d’empremtes com ja s’havia comentat en l’apartat 3.2.2.4: Whorl, Left Loop, Right Loop, Arch i Tended Arch. Una vegada classificada l’empremta dins d'un d'ells, es procedeix a buscar, dintre del grup apropiat, l’empremta que més s’assembla a la qual es vol identificar.

Figura 3.25: Classificació d’Henry.

L'aparellat fiable d'empremtes dactilars és un problema extremadament difícil, principalment com a conseqüència de la gran variabilitat entre impressions de la mateixa empremta (gran variabilitat intra-classe). Els principals factors responsables d'aquesta variabilitat són: translació, rotació, solapat parcial, distorsió no lineal, variacions en la pressió, alteracions de les condicions de la pell, soroll i els problemes derivats de l'extracció de característiques. Així, com pot apreciar-se en la figura 3.26, impressions del mateix dit poden semblar bastant diferents, mentre que empremtes de dits diferents poden semblar similars (petita variabilitat inter-classe).

a) b)


_______________________________________________________________________

29

c) d)

Figura 3.26: Les impressions a) i b) semblen diferents a primera vista, però pertanyen al

mateix dit, mentre que les empremtes c) i d) semblen iguals per a uns ulls inexperts però són de dits diferents.

Els experts en la identificació mitjançant empremta dactilar avaluen diferents factors per a dir quines dues impressions diferents pertanyen a la mateixa empremta:

• Les dues empremtes han de pertànyer al mateix tipus des del punt de vista de l'anàlisi global.

• Correspondència qualitativa entre el minutiae de les dues impressions, és a dir concordança des d'un punt de vista local.

• Similitud mínima quantitativa, que especifica el mínim nombre de parelles entre el minutiae de les dues empremtes per a validar legalment la identificació (de 11 a 14 parelles depenent del país).

Els sistemes automàtics de verificació dactilar, si bé s'han inspirat en el procediment manual, han derivat en multitud de diferents solucions pensades explícitament per a ser implementades en una computadora. En general, aquestes solucions per a l'aparellat automàtic de petjades, poden classificar-se en tres categories:

• Aparellat basat en correlació: es calcula la correlació, dels nivells d'intensitat dels píxels, entre diferents alineacions (diversos desplaçaments i rotacions) de les dues imatges a comparar.

• Aparellat basat en minutiae: s'extreu el minutiae de les dues empremtes i s'emmagatzema com dos conjunts de punts en el plànol bidimensional. Es tracta de trobar l'alineació entre el patró i la mostra que derivi en el màxim nombre de parelles de minútias.

• Aparellat basat en característiques de crestes: es tracta de comparar altres característiques de les crestes, com l’orientació, el gruix, la forma i la freqüència ; que són més fàcils d'obtenir que el minutiae, especialment en impressions de baixa qualitat.


_______________________________________________________________________

30

El mòdul d'aparellat ha de determinar, a partir de dues representacions, si les empremtes associades pertanyen al mateix dit; per això es defineix una mesura del grau de similitud entre dues representacions dactilars. L'elecció de l'algorisme d'aparellat dependrà del tipus d'informació utilitzat per a caracteritzar l’empremta; en el cas que ens ocupa s'empra el basat en el minutiae. Una vegada s'ha calculat el grau de similitud entre les dues empremtes, aquest es compara amb un valor llindar per a determinar si pertanyen al mateix dit o no.

En condicions ideals la verificació dactilar podria ser un problema relativament senzill; no obstant això, en condicions reals es converteix en una tasca difícil, ja que el sistema ha de ser capaç de funcionar amb unes taxes d'error baixes malgrat una sèrie de problemes que afecten a les representacions de les quals es va a disposar, tant per a la imatge patró com per a l’ empremta a verificar. Les etapes de captura de l’empremta i d'extracció de paràmetres introdueixen errors de translació, rotació i deformació de l’empremta, als quals s'han d'afegir les pròpies modificacions de les crestes papilars, ja siguin permanents (talls) o transitòries (soroll).

Les tècniques basades en el minutiae solen aparellar els conjunts de minutiaes de la mostra i el patró encadenant una primera etapa d'alineació i una posterior de localització de minútias coincidents; la comparança del nombre final de parelles entre els dos conjunts de minútias amb un valor llindar determinara la coincidència o no entre les dues representacions dactilars. L'alineació entre la mostra i el patró pot realitzar-se de diferents formes: mitjançant la imatge direccional, emprant la localització de singularitats com el nucli o el punt delta o usant les pròpies crestes, emprant tècniques d'aparellat de grafs emprant el graf format per les minútias, mitjançant la transformada de Hough. Una vegada realitzada l'alineació, i considerant certes toleràncies, es realitza l'aparellat de les minútias.

El mètode de Mital i Teoh empra un model d'aparellat estructural dividit en dues etapes. En una primera fase es realitza un aparellat mitjançant correlació emprant característiques locals, és a dir, localitzant estructures de 5 a 10 minutiaes que es reprodueixin en la empremta mostra i en el patró; d'aquesta manera s'aconsegueix alinear la mostra i el patró, i s'obté una llista de possibles parelles de minutias. La segona etapa realitza un aparellat per correlació emprant característiques globals, analitzant ara la totalitat de l’empremta com un conjunt i no com la suma de petits veïnatges, però considerant només les minútias que han superat la primera fase de l'anàlisi.

Són molt variades les alternatives d'extracció i aparellat desenvolupades en els últims anys i majoritàriament funcionen correctament sobre un percentatge elevat de la població; no obstant això, els resultats continuen sent deficients quan es processen imatges dactilars de baixa qualitat. En aquest tipus d'imatges els algorismes basats en correlació solen funcionar millor que els basats en minutiae, però com contrapartida presenten una disminució de rendiment a mesura que augmenta el període de temps transcorregut entre les fases de registre i verificació. En qualsevol cas, les deficiències del sistema no se solen associar al procés d'aparellat sinó a la fase prèvia d'extracció de característiques.

Algorisme d'extracció de Maio_____________________________________________________________

_______________________________________________________________________

31

4 Algorisme d’extracció de Maio

Aquest apartat explica de forma superficial l’algorisme d’extracció de minúties a partir de imatges en escala de grisos. Concretament l’algorisme proposat pel Dr. Dario Maio i el Dr. Davide Maltoni en la seva publicació en el IEEE “Direct Gray-Sacle Minutiae Detection In Fingerprints”[1]. A partir d’ara l’anomenarem algorisme o mètode de Maio.

Aquest és l’algorisme amb el que treballa el grup de recerca, tot i que se li han fet notables millores la base del funcionament segueix sent la mateixa. Els motius de fer ús d’aquest mètode en lloc del de binarització són:

- En el procés de binarització d’una imatge es pot perdre força informació.

- Les fases de filtrat, binarització i esqueletització consumeixen molt de temps.

- Aquest mètode no és tan sensible a variacions del nivell mig de gris que es pot presentar en diferents zones de la imatge.

L’idea bàsica proposada per l’algorisme de Maio, es basa en seguir les crestes directament de la imatge capturada. Es tracta de navegar o resseguir les crestes d’acord amb la direcció que aquestes presenten. Una imatge la podem considerar com una quadrícula de píxels AxB (A=llarg, B=ample), on en cada casella hi tenim un nivell de gris. Els valors de gris propers a 0 identifiquen les valls o “ravines” i els valors més foscos de gris es relacionen amb les crestes o “ridges” de l’empremta. Així doncs, podem fer-nos una imatge tridimensional utilitzant el nivell de gris com eix Z. Tal com es veu en la figura 4.1 a. Per altra banda si fem una secció veuríem el que ens mostra la figura 4.1 b.

Figura 4.1: Representació 3D d’una empremta (a). Secció crestalls (b).


_______________________________________________________________________

32

4.1 Seguiment dels crestalls

Des de un punt de vista matemàtic, podríem definir una cresta com una seqüència de punts que són màxims locals al llarg d’una direcció. A partir d’aquesta definició el Dr. Dario Maio proposa un codi per a l’extracció de les crestes que es basa en localitzar en cada pas de l’algorisme un màxim local a través d’una secció ortogonal a la direcció de la cresta. D’aquesta forma, connectant els màxims consecutius s’aconsegueix una aproximació poligonal de la cresta estudiada.

Un cop capturada la imatge, i en principi, sense necessitat de fer cap mena de filtrat per a suavitzar els sorolls que pugui haver-hi ja podem fer el seguiment. Disposem de l’empremta en escala de gris, tal com podria ser la que es mostra en la figura 4.2 (Val a dir que aquesta és de molta més qualitat del que tindrem normalment), on σ és la distància en píxels entre el centre de dos crestalls consecutius (a) i ε representa l’amplada de la cresta en píxels (b). L’algorisme treballa de la següent forma:

(a)

(b)

Figura 4.2: Imatge de l’empremta dactilar capturada. (a) σ distància entre dos crestes consecutives. (b) ε amplada de la cresta.


_______________________________________________________________________

33

Donat un punt (ic,jc) que pertany a una cresta amb un angle cϕ (figura 4.3). L’algorisme per trobar el nou punt de la cresta fa un desplaçament de µ píxels en la direcció cϕ , ja que es suposa que la direcció del punt (ic,jc) correspon amb la direcció de la cresta que seguim. Una cop fet el desplaçament es troba el punt (it,jt) (figura 4.4).

Figura 4.3: Punt (ic,jc) i direcció cϕ que

pertany a una cresta.

Figura 4.4: Desplaçament de µ píxels fet en

la direcció cϕ i punt (it,jt) trobat.

El punt (it,jt) pot no estar del tot ben centrat en la mig de la cresta, que es la zona on haurien de trobar-se els màxims, i fins i tot es podria donar el cas de que estigués a la vora o fora de la cresta si l’angle cϕ no estigués ben calculat o no coincidís amb la direcció de la cresta a seguir. Per evitar que el nou punt no estigui ben centrat, el que proposa l’algorisme és fer un tall de direcció cϕ +π/2 centrat en el punt (it,jt) de longitud 2σ+1 (figura 4.5).

Figura 4.5: Tall de direcció cϕ +π/2 centrat en (it,jt) i longitud 2σ+1.


_______________________________________________________________________

34

Una cop fet el tall, obtenim una secció Ω de longitud 2σ+1 que conté el nivell de gris par cada punt de la mateixa, tal com mostra la figura 4.6.

Figura 4.6: Secció Ω que conté el nivell de gris para cada punt del tall realitzat.

En la secció Ω es busca el punt màxim, es a dir, el que tingui un major nivell de gris, ja que aquest estarà centrat en la cresta.(figura 4.7). Aquest nou punt (in,jn) que és el màxim en la secció Ω serà el nou punt per desplaçar-nos per a continuar amb el seguiment, ja que ara tornem a estar centrats en la cresta.

Figura 4.7: Cerca del punt (in,jn) en la secció Ω.


_______________________________________________________________________

35

Una cop trobat el punt (in,jn) , l’algorisme verifica si aquest punt compleix amb algun dels criteris per aturar-se. Si és així, es considera que el punt no pertany a la cresta i es para el procés de seguiment que es segueix per una altre zona no tractada. Ara bé. sinó és així es va repetint el procés, l’algorisme calcula la direcció en aquest nou punt (in,jn), i aquest punt i l’angle es converteix en el nou punt (ic,jc) i la direcció o angle en

cϕ tornant així a repetir-se el cicle fins que es compleixi algun dels criteris per aturar-se que veurem a l'apartat 4.1.3.

Ara que ja hem vist la forma de treballar del mètode del Dr. Dario Maio per al seguiment de la cresta, el algorisme resultant en pseudo-codi es:

Seguiment_cresta (is,js,f o)

end=false;

(ic,jc)=(is,js);

f c=f o;

while (!end)

(it,jt)=(ic,jc)+desplaçament;

//desplaçament= µ píxels en direcció f c.

? =realitzar_secció (it,jt,f c+p/2);

//Retorna a secció de punts de la cresta

//Punt central (it,jt) i direcció f c+p/2.

(in,jn)=màxim_local (? );

//Retorna el punt que és màxim local a ? .

end=criteri _aturar();

//busca condicions per aturar-se als punts calculats ja sigui perquè

//a trobat el final de la cresta, el creuament de dues o es perdi.

(ic,jc)=(in,jn);

f c= calcul_direcció(ic,jc);

Figura 4.8: Pseudo-codi del mètode de Maio

Les parts més importants d'aquest mètode son les funcions màxim_local, càlcul_direcció, criteri_aturar, ja que el mal funcionament de aquestes faria que el seguiment del crestall fos fals. Per això als apartats següents les comentarem.


_______________________________________________________________________

36

4.1.1 Càlcul del Màxim

Un cop comentat el mètode proposat per el Dr. Dario Maio per a fer el seguiment de les crestes de la imatge, podem veure que aquest sistema presenta també la necessitat d’un filtrat per tal de poder realitzar el càlcul del punt màxim dins de la secció Ω.

En principi, podríem pensar que sols cal comparar tots els nivells de gris de la secció i quedar-nos amb el més gran. De totes maneres la presencia de soroll fa que la cosa no sigui tan senzilla. Les seccions d’una imatge que no ha estat filtrada o suavitzada tenen una forma com la que es pot veure en la figura següent. La presencia de soroll ens faria agafar punts erronis com a centre de les crestes. És a dir, que el que hem vist fins ara sols seria vàlid aplicat a imatges de gran qualitat.

Figura 4.9 : Representació de diferents seccions os es veu la presencia de soroll.

Així doncs, el que es fa és aplicar un filtrat a la secció. Es tracta de fer la mitjana de la secció amb els punts d’una secció un píxel posterior i un píxel anterior a la que tractem. Un cop fet això s’aplica un filtrat de tipus gaussià per tal de suavitzar les transicions i centrar els punts màxims el més al centre de la cresta possible.

Un cop fet això, el resultat de la nova secció obtinguda presentarà unes formes més suavitzades on trobar el màxim ja serà molt més fàcil. La figura 4.10 ens mostra els resultats d’aplicar aquestos dos passos sobre les seccions anteriors.

Figura 4.10: Comparació entre la imatge original i el resultat filtrat.

Algú podria pensar que fent aquest filtre ja estem perdent una altre vegada el temps en processat de la imatge tal com ho fèiem en el cas del mètode basat en la binarització. La veritat és que aquí no filtrem tota la imatge sinó que fem petits filtres cada µ píxels i no és una càrrega tant feixuga com la del cas de binarització. El fet de no tractar tota la imatge sinó petites zones d’interès i el fet d’aplicar sols dos filtres (mitjana i gaussià) fan que l’estalvi de temps comparat amb l’altre mètode sigui considerable.


_______________________________________________________________________

37

Per altra banda, el fet de que variïn els nivells de gris de forma notable en diferents zones de la imatge no ens resulta tant problemàtic. Aquí, al contrari que en la binarització, no treballem amb un llindar sinó que busquem els màxims locals. Aquestos podran tenir valors més o menys alts però mentre siguin una mica més grans que els de la vora ja podrem fer el seguiment sense problemes. Amb els llindars això no passa i pot ser necessari utilitzar llindars diferents en diferents zones de la imatge. I després pot ser difícil unir les zones sense que quedin graons en les unions.


_______________________________________________________________________

38

4.1.2 Càlcul de la Direcció

Tal com es pot imaginar, en aquest mètode l’estimació correcta de la direcció és força important a l’hora de fer el seguiment de la cresta, per tant, també en aquest mètode s’utilitzen estimacions de direcció de les crestes. Tal com està proposat el mètode les estimacions de direcció es fan a cada moment que trobem un nou punt. El grup de recerca mira d'optimitzar aquest mètode fent-li petites modificacions. Una de les més importants és canviar el sistema d’estimació de direccions.

El Dr. Dario Maio utilitza en el seu algorisme un mètode proposat per el Dr. Donahue i el Dr. Ronkhlin[2], es basa en calcular la direcció fent el càlcul del gradient en una finestra de 2x2 dels píxels veïns, un cop fet això, es fa la mitjana sobre una finestra local mitjançant el mètode de mínims quadrats.

El algorisme a implementar per al càlcul de la direcció seria:

Figura 4.11: Algorisme per al càlcul de la direcció


_______________________________________________________________________

39

4.1.3 Criteris per aturar-se

Aquests són els criteris que poden aturar el seguiment:

1.- Estar fora de l’àrea a tractar: Normalment, no es fa un seguiment de tota la imatge capturada i s’acostuma a deixar sense tractar les vores que és on normalment hi ha les zones més sorolloses, i usualment menys minúties..

2.- Final: L’algorisme es para si arribem al final d’una cresta. Això ho podem saber si la diferència del angle cϕ i l’angle que forma el segment prenent com extrems els punts (ic,jc) i (in,jn) és més gran que un angle predeterminat β.

3.- Intersecció: la intersecció es produeix si el punt (in,jn) ja ha estat analitzat anteriorment. Sempre guardem per on passem, per no tractar les mateixes zones dos cops.

4.- “Excessive Bending”: la diferència entre l’angle que forma el segment (ic,jc)(in,jn) i l’angle mig de la cresta és superior a un angle ψ. Aquest criteri atura l’algorisme si es produeix un canvi brusc de direcció en la cresta, podríem estar saltant de cresta o moure’ns per zones sorolloses. L’angle mig de la cresta es calcula fent la mitja dels últims K angles formats per els segments (ic,jc)(in,jn) calculats prèviament.


_______________________________________________________________________

40

4.2 Extracció de Minúties

Un cop vist per sobre el funcionament de l’algorisme de seguiment passem a l’últim pas que ens quedaria, l’extracció de les minúties. Val a dir que també en aquest cas podem guardar la direcció de les minúties que es troben.

Si ens fixem en els criteris per aturar el seguiment que hem vist abans, podrem veure que ja es corresponen als de minúties trobades exceptuant alguns casos. El primer és el final de cresta, així que ja podríem marcar el punt com a final de cresta. Per altra banda arribar a un punt per on ja havíem passat ens indica que ens trobem en una bifurcació. En aquest últim cas, cal parar compte de que aquest punt, o un altre de molt proper, no estigui marcat ja com a final de cresta. Si fos així, vol dir que la cresta continua i l’algorisme de seguiment s’havia perdut en el seguiment per algun criteri de excessive bending, per exemple, i fent el seguiment per un altre lloc hem retrobat el punt. Llavors cal unir-los i no marcar cap minútia. La figura següent ens mostra això de forma gràfica.

Figura 4.12: Tipus de minúties trobades pel algorisme de Maio.


_______________________________________________________________________

41

El problema més gran d’aquest mètode és la necessitat de guardar el seguiment de les crestes que ja s’han realitzat per poder trobar les bifurcacions i no passar diverses vegades pels mateixos llocs. Això obliga a guardar una imatge auxiliar T de la mateixa mida que la imatge que estudiem i marcar els llocs tractats.

Un cop s’ha fet tot això, el Dr. Dario Maio proposa fer un filtrat a la llista de minúties trobades, ja que s’han pogut trobar minúties falses provocades per una mala qualitat de les imatges. Per això fa un filtrat eliminant aquelles minúties que es troben massa pròximes entre elles. Així doncs aquí també es fa una correcció final com en el cas del mètode de binarització.

Aquestes minúties trobades junt amb les seves coordenades, orientacions i el tipus de punt característic que és, seran el nostre fitxer d’entrada al programa.

Algorisme Inicial _

_______________________________________________________________________

42

5 Algorisme d'aparellament

En aquest apartat veurem una pincellada de les bases de que partim per tal de crear

el nostre programa d’aparellament, que li direm “Match”.

Abans de passar a explicar el funcionament del programa, farem una introducció de com es crea el nostre fitxer d’entrada al programa “Match”, que serà la base de partida.

En el segon apartat es veurà el flux de funcionament o procés que segueix el model original per tal de determinar l’aparellament o no aparellament de minúties i es farà una explicació del sistema d’anàlisi utilitzat.

Un altre apartat serà per veure els paràmetres que utilitza aquest programa i finalment veurem els errors trobats a cada fase del procés.

Degut a algun dels últims errors trobats, es canviarà el sistema o procés seguit, ja que com es podrà veure, el d´aquest algorisme inicial no era correcte.

Algorisme Inicial _

_______________________________________________________________________

43

5.1 Procés inicial

El programa “Match” que s’ha creat, rep com a entrada un fitxer de text amb les minúties numerades juntament amb la seva posició en coordenades X e Y, la seva orientació i el tipus segons sigui un final o una bifurcació. És lògic que des de la lectura de l’empremta fins a obtenir el nostre fitxer d’entrada hi ha un procés inicial, per tant abans de veure el funcionament del programa, anem a explicar com obtenim el fitxer d’entrada al nostre programa.

Adquisició característica biomètrica: És el primer pas corresponent a la adquisició de les empremtes a comparar. A la primera empremta a comparar li direm template i la segona que es compara sample.

Figura 5.1: Adquisició de les empremtes, a la esquerra template i a la dreta sample.

Algorisme Inicial _

_______________________________________________________________________

44

Per tal de poder observar millor els punts característics o el que serà el mateix per nosaltres les minúties, farem una esqueletització de les empremtes (en el nostre cas no es una etapa del procès d’extracció).

Figura 5.2: Esqueletització de les empremtes, a l’ esquerra template i a la dreta sample

Ara procediríem a l’ extracció dels punts característics o minúties (punts finals, bifurcacions, punts secants...) que ja vam veure en l’apartat 3.2.2.3, mirant també les seves orientacions en les imatges per guardar-ne el valor.

Figura 5.3: Minútia amb coordenades X , Y i orientació alfa.

X

Y

Alfa

Algorisme Inicial _

_______________________________________________________________________

45

Figura 5.4: Extracció minúties de les empremtes (marcades amb vermell), a l’ esquerra template

i a la dreta sample

Per a l’aparellament l’únic que ens interessa són les minúties que hem trobat, per això es tant important aquest primer procés de lectura i extracció.

Figura 5.5: Minúties numerades, a l’ esquerra template i a la dreta sample

Finalment, tenim el nostre fitxer d’entrada al programa amb el número de minútia(#), les seves coordenades(X e Y), orientacions(Alfa) i tipus(T).Anem a veure un petit exemple de fitxer d’entrada per la part del template, la del sample tindria la mateixa estructura.

TEMPLATE:

3 //Nº de minúties totals

# X Y Alfa T

--------------------------------------------

0 214 17 35 0

1 183 28 65 0

2 221 41 53 1 Figura 5.6: Fitxer d’entrada Template

Algorisme Inicial _

_______________________________________________________________________

46

5.2 Funcionament general

Podríem dividir el procés en 2 grans apartats i un tercer apartat que faria dénllaç entre aquests, un que serà l’anàlisi local on com el seu nom indica es fa un anàlisi local en la pròpia empremta i láltre que serà l’anàlisi global, on aquí ja si es fa l’anàlisi entre les dues empremtes Template-Sample. Aquests dos apartats quedarien units per el procés de creació dúna matriu on veiem el grau de similitud entre minúties i lássignació dúna minútia central. Es busca una minútia central a cada empremta per tal de tenir dos punts de referència en les empremtes i poder-les alinear per tal de fer la comparació. Com es evident l’alineació no serà perfecte per tant tindrem uns marges d’error o toleràncies per tal de donar minúties com a iguals o no, podriem dir que són les zones vàlides dins les quals les minúties es consideren com a iguals.Vegem en la següent figura una descripció general del procés comentat.

Lectura del fitxer elegit per lúsuari amb minuties template i sample

Anàlisi local ( pel sample i pel template )

Càlcul de la matriu de similitud

Busca la minutia central

Un cop centrat fa un anàlisi global

Finalment fa aparellament

Figura 5.7: Flux general.

Algorisme Inicial _

_______________________________________________________________________

47

5.2.1 Anàlisi local

Desprès d’haver fet la lectura del fitxer amb les minúties del Template i Sample amb les seves respectives coordenades X i Y i la seva orientació Alfa (també es llegeix el tipus de minútia per diferènciar els finals de les bifurcacions però no ho utilitzarem ja que molt fàcilment podríem fer una lectura errònia i canviar una bifurcació per un final), es procedeix a realitzar l’anàlisi local d'aquestes.

En aquest anàlisi local, el que es fa és agafar cada punt característic o minútia ( # ) de l'empremta i buscar les seves 10 minúties mes pròximes ( segons el valor de la distància d ) o com es diu en el programa Neighbours (veïnes). A part el programa també fa el càlcul de l’angle format entre la minútia de referència i les seves corresponents veïnes (Gamma) i la diferència entre orientacions entre la minútia de referència i les seves veïnes (Beta). En el fons, el que fa el programa és passar a coordenades polars la posició relativa de cada parella minútia-veïna trobant la distància d i l’angle relatiu a la seva posició gamma. Com ja s’ha comentat anteriorment, en el fitxer també s’escriu el tipus de minútia (t) encara que desprès no s’utilitzarà.

Figura 5.8: Exemple local per 5 veïnes, la minútia blava es la de referència.

A nivell de càlculs la distància es calcula per Pitagores, la gamma com la tangent inversa entre les coordenades x e y i finalment la beta com una diferència d’ angles per fer-ho invariant a la rotació.

Equacions utilitzades:

gamma=argtg(y,x)

Beta=|(angle orientació referència-angle orientació veïna)|

d=vx2+y2

Gamma

d Beta

Algorisme Inicial _

_______________________________________________________________________

48

S’aplicarà aquest anàlisi una vegada pel sample i una altre pel template, de tal manera que en acabar tindrem dos fitxers locals, un pel sample i un altre pel template, amb totes les minúties i les seves 10 veïnes mes próximes on una es comptabilitza com a ella mateixa.

# X Y Alfa T # t d Beta Gamma

----------------------------------------------------------------------------------------------------------------------

12 176 167 -73 1

12 0 0 0 0

14 0 13 17 -57

13 0 15 138 -172

15 0 20 160 -119

9 0 32 131 167

5 0 46 137 93

10 0 49 63 5

19 0 62 159 -116

7 0 66 122 163

6 0 75 92 22

Figura 5.9: Exemple fitxer creat en l’anàlisi local per la minutia 12.

Algorisme Inicial _

_______________________________________________________________________

49

5.2.2 Creació de la Matriu de Similitud i assignació de la minútia central

Un cop s’ha fet l’anàlisi local i tenim els dos fitxers amb les minúties i les seves 10 veïnes s’agafa la minútia 0 i la seva veïna 0 del template i amb la minútia 0 veïna 0 del sample mira els valors dels angles i la distància per veure si entren dins les toleràncies, en cas de ser així la posició [0,0] de la matriu de similitud s’incrementaria en 1. El següent pas seria mirar la minútia 0 i la seva veïna 0 del template i amb la minútia 0 veïna 1 del sample i així successivament fins mirar les seves 10 veïnes. Un cop mirades totes les veïnes faria la minútia 0 i la seva veïna 1 del template i amb la minútia 0 veïna 0 del sample. Aquests procés el fa per totes les minúties, per tant en acabar la primera minútia del template faria la següent (la minútia 1 i la seva veïna 0 del template i amb la minútia 0 veïna 0 del sample).

En acabar de mirar totes les minúties i les seves veïnes del template amb les del sample generem la matriu de similitud on podem veure el número de veïnes que entren dins les toleràncies entre minúties o dit d’una altre manera la similitud que hi ha entre les minúties (des d’un punt de vista local).

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

------------------------------------------------------------------------------------------------------

0| 3 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0

1| 3 2 2 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0

2| 2 2 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0

3| 1 3 2 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0

4| 4 1 1 0 2 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1

5| 0 0 0 5 1 1 0 0 0 1 3 1 2 0 0 0 0 0 0 0 0

6| 0 0 0 0 0 3 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0

7| 0 0 0 3 1 1 1 1 1 0 1 0 1 1 1 0 0 0 0 0 0

8| 0 0 0 0 0 0 1 1 4 0 0 0 1 1 1 0 1 1 0 0 0

9| 0 0 0 1 0 1 1 0 2 1 1 1 1 1 1 1 1 1 0 0 0

10| 0 1 0 0 0 3 1 5 1 0 1 0 0 0 0 0 0 0 0 0 0

11| 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1

12| 0 0 0 1 0 2 1 0 0 2 5 2 0 0 0 0 0 2 1 0 0

13| 0 0 0 1 0 0 3 0 2 3 2 0 2 0 0 1 1 2 0 0 0

14| 0 0 0 0 0 1 1 0 0 1 1 7 0 0 1 0 0 0 2 0 0

15| 0 0 0 1 0 1 0 1 1 0 2 1 6 0 0 0 0 1 2 0 0

16| 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 2 1 2 0 0

17| 0 0 1 0 0 0 1 0 0 0 0 0 0 2 2 2 4 1 1 0 1

18| 0 0 1 0 0 0 0 0 2 0 0 0 0 1 4 0 3 0 2 0 1

19| 0 0 0 0 0 1 0 0 0 2 0 1 2 0 1 1 3 5 2 1 1

20| 0 0 0 0 0 0 0 1 0 1 0 0 0 1 2 1 2 2 2 1 1

Figura 5.10:Taula de similitud entre 20 minúties template i 20 minúties sample.

Algorisme Inicial _

_______________________________________________________________________

50

Un cop ja tenim la matriu de similitud es busquen les minúties del template que tenen més similitud amb les del sample i es memoritza, les dues minúties amb més semblança passen a ser les minúties centrals de cada empremta. Ara que ja tenim la minútia central que ens farà de referència podem passar a l’anàlisi global. En el cas de la figura anterior serien les minúties 11-14 que tenen un nivell de similitud de 7.

5.2.3 Anàlisi Global

En l’anàlisi global es calculen altre cop el valor de distàncies i angles respecte la minútia triada com a central, s’agafen les minúties del template amb les seves parelles del sample memoritzades que tinguin un mínim de similitud de 2. Amb això generem un fitxer global amb els càlculs comentats.


----------------------------------------------------------------------------------------------------------

14 169 178 304 1

19 1 57 142 -127

18 0 70 8 -34

17 1 109 19 -19

15 1 18 143 -157

12 1 13 17 122

10 1 44 46 20

9 0 42 114 155

8 0 92 43 11

7 1 77 105 157

6 0 74 75 32

5 1 57 120 99

4 1 129 124 102

3 1 182 97 46

1 0 150 121 95

0 0 167 91 105

Figura 5.11: Anàlisi global amb minútia central nº14.

Algorisme Inicial _

_______________________________________________________________________

51

Un cop tenim els càlculs globals fets, mirem si el template amb la seva parella del sample memoritzada de màxima similitud entren dins les toleràncies per considerar-les com a parella. Comentar, tot i que ja es dona a entendre, que s’agafa com a referència el template.

Fet això, només queda fer el recompte de parelles per poder dir si les empremtes són iguals o no. En l’esquema següent podem observar les minúties del template (esquerra) i les del sample (dreta) numerades. Així com les parelles fetes indicat per les línies blaves que uneixen les parelles. La minútia central també queda reflectida ja que és d’on surten totes les línies vermelles.

Figura 5.12: Emparellat final template amb sample.

Algorisme Inicial _

_______________________________________________________________________

52

5.3 Paràmetres del programa

El programa utilitza una variable que es diu “neighbours” que indica el número de veïnes que mirarà per fer l’anàlisi local i que també ens afecta a l’hora de determinar la minútia central.

En el programa aquesta variable agafa un valor de 10, però per tal que tingui un funcionament més òptim, en aquest programa inicial se li posaven valors de fins a 14 veïnes. En el programa creat en aquest projecte el número de veïnes ja veurem que és de 9, ja que una de les que conta com a veïna és ella mateixa i el seu funcionament és molt millor que el programa inicial amb 14 veïnes.

Un altre paràmetre important és el nivell mínim de similitud que han de tenir les minúties per tal que les podem considerar centrals, la variable que marca aquest valor és SD_Threshold. S’utilitza un valor de similitud mínima de 5, si les minúties centrals no arriben a tenir aquest nivell no poden ser centrals.

Els dos altres factors molt importants en el programa són les toleràncies tant per distàncies com per angles, en el cas dels angles com mes pròxim estigui, la tolerància haurà de ser més gran per tenir més obertura i si està més lluny no caldrà obrir tant l’angle per tal de que la minútia estigui dins les toleràncies. Si la distància és més petita de 100 píxels, la tolerància en angles es de 30 graus (cas b figura 5.13), si és més gran la tolerància la posa de 20 graus (cas a figura 5.13). En cas de que la distància sigui més petita de 100 píxels la tolerància en la distància es de 20 píxels (cas d figura 5.13), degut a que si està a prop no és necessita molt de marge pel que fa a distàncies i si és més gran de 100 píxels la distància té una tolerància de 40 píxels (cas c figura 5.13). Mirarem a la distància a la que es troba ja que la tolerància no ha des ser la mateixa si està a prop que si està mes lluny.

(a) (b)

(c) (d)

Figura 5.13: Exemples toleràncies.

Finalment, caldria determinar el número de parelles que s’han de fer per tal de considerar si són iguals les dues empremtes o no, el programa no fa aquest últim pas.

Algorisme Inicial _

_______________________________________________________________________

53

5.4 Detecció Errors

En aquest apartat el que es busca és explicar els errors trobats, la seva resolució es farà en l’apartat 6.4 resolució d’errors corresponent al nou codi creat.

5.4.1 Errors Anàlisi Local

5.4.1.1 Error_domain

En l’ anàlisi local tenia el problema de que si es donava el cas de que havia de fer el argtg de dos valors de distàncies que eren 0, el programa donava un error i no compilava.

5.4.2 Errors Creació Matriu de Similitud i assignació de la minútia central

5.4.2.1 Error_condició_distància

El que es buscava amb la condició següent abs(smp[j].ld2[p]-distancia)>0))

On:

smp[j].ld2[p] fa referència a la distància entre minúties del sample

distància fa referència a la distància entre minúties del template

és que al mirar la diferència de distàncies no es tingui amb compte a ella mateixa ja que si es ella mateixa la resta serà 0 i per tant complirà la condició. És evident que si resta el mateix valor de distància (el seu mateix) el resultat sigui 0. La condició evitava que es considerés a ella mateixa, però per solucionar això, provocava un error que ara veurem.

Té el problema que si la diferència entre distàncies, entre minútia de referència i minútia sample restat amb minútia de referència i minútia template dóna 0, ja no tindria en compte les minúties i l’objectiu és que no es tingui en compte a ella mateixa per evitar un càlcul innecessari, no que deixi de considerar possibles minúties bones.

Anem a veure el comentat amb una extracció template-sample.

Algorisme Inicial _

_______________________________________________________________________

54

Figura 5.14: Error per distància 0

Observem que si la distància que simbolitza la fletxa vermella entre les minúties 10-11 és igual a la distància que simbolitza la fletxa blava entre les minúties 16-13 , la resta seria 0 i per tant ja no ho consideraria. És difícil que doni exactament 0, però podria passar.

5.4.2.2 Error_condició_angle

Al posar la condició a complir per l’angle, no tenia en compte la tolerància triada o el que és el mateix, la variable límit segons la distància a la que es troba la minútia. Observem com a la següent condició fixa un valor de 170 sense considerar el límit. (abs(smp[j].la[p]+theta1)>170)

Algorisme Inicial _

_______________________________________________________________________

55

5.4.2.3 Error_funció_central_feature

El que es pretenia amb la següent condició és que una minútia no fos central si tenia més d’ una parella amb el màxim nivell de similitud.

if ((sc!=1) || (tmp[i].lsd<2)) tmp[i].lsd=0;

Estava pensat, com acabo de comentar, perquè si en una fila hi han 2 minúties amb el màxim de similitud no puguin ser triades com a central, però el programa el que fa és posar el seu lsd a 0, amb la qual cosa, al fer l’ anàlisi global, el programa ja no les te amb compte. Degut a aquest error es perden moltes minúties. Anem a veure-ho amb un exemple

Figura 5.15:Taula de similitud entre 20 minúties template i 20 minúties sample.

Totes les caselles de la matriu anterior marcades amb vermell serien files que no tindria en compte, ja que tenen més d’una minútia amb el grau màxim de la fila i això seria un greu error.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

------------------------------------------------------------------------------------------------------

0| 3 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0

1| 3 2 2 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0

2| 2 2 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0

3| 1 3 2 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0

4| 4 1 1 0 2 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1

5| 0 0 0 5 1 1 0 0 0 1 3 1 2 0 0 0 0 0 0 0 0

6| 0 0 0 0 0 3 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0

7| 0 0 0 3 1 1 1 1 1 0 1 0 1 1 1 0 0 0 0 0 0

8| 0 0 0 0 0 0 1 1 4 0 0 0 1 1 1 0 1 1 0 0 0

9| 0 0 0 1 0 1 1 0 2 1 1 1 1 1 1 1 1 1 0 0 0

10| 0 1 0 0 0 3 1 5 1 0 1 0 0 0 0 0 0 0 0 0 0

11| 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1

12| 0 0 0 1 0 2 1 0 0 2 5 2 0 0 0 0 0 2 1 0 0

13| 0 0 0 1 0 0 3 0 2 3 2 0 2 0 0 1 1 2 0 0 0

14| 0 0 0 0 0 1 1 0 0 1 1 6 0 0 1 0 0 0 2 0 0

15| 0 0 0 1 0 1 0 1 1 0 2 1 6 0 0 0 0 1 2 0 0

16| 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 2 1 2 0 0

17| 0 0 1 0 0 0 1 0 0 0 0 0 0 2 2 2 4 1 1 0 1

18| 0 0 1 0 0 0 0 0 2 0 0 0 0 1 4 0 3 0 2 0 1

19| 0 0 0 0 0 1 0 0 0 2 0 1 2 0 1 1 3 5 2 1 1

20| 0 0 0 0 0 0 0 1 0 1 0 0 0 1 2 1 2 2 2 1 1

Algorisme Inicial _

_______________________________________________________________________

56

5.4.2.4 Error_compta_repetides

El problema que ens trobem aquí, és que a l’hora de fer la matriu de similitud per veure quantes minúties que s’assemblen, compta parelles de minúties que ja ha comptabilitzat anteriorment, el que no pot ser, és que una mateixa la compti més d’una vegada. Anem a veure un exemple:

Tmp # 15.Neighbour # 22 - Smp # 0.Neighbour # 3



En aquest cas, el que ha fet, és emparellar la minútia 0 del sample i la seva veïna 1 dues vegades, la qual cosa és lògic que no pot ser. Anem a veure quina similitud dóna entre la minútia 15 del template i la minútia 0 del sample.

Figura 5.16: Taula de similitud entre 23 minúties template i 14 minúties sample.

Efectivament s´equivoca i en compta 3 enlloc de 2, que serien les realment possibles.



Algorisme Inicial _

_______________________________________________________________________

57

5.4.3 Errors Anàlisi global

5.4.3.1 Error_domain

En l’ anàlisi global tenia el mateix problema que hem comentat anteriorment pel local, de que si es donava el cas de que havia de fer el argtg de dos valors de distàncies que eren 0, el programa donava un error i no compilava.

5.4.3.2 Error_condició_angle

Al posar la condició a complir per l’angle no tenia en compte la tolerància escollida, o el que és el mateix, la variable límit segons la distància a la que es troba la minútia.

5.4.3.3 Error_tolerància_angles

Un altre conflicte vist és que per distàncies petites l´angle ha de tenir una tolerància més gran, ja que al ser tant pròxim, fàcilment podria no entrar dins del marge. Pel que fa a la distància és evident que ni que estigui una mica desplaçat, el valor variarà poc. El que es proposa doncs, és fer 3 marges , tenint en compte les distàncies entre minútia de sample i la del template.

Anem a justificar una mica tot el comentat.

Un píxel d´increment representa en l’ angle:

angle=argtg (1/100)=0,57

Algorisme Inicial _

_______________________________________________________________________

58

Cas exemple:

Anem a veure un cas concret del nostre programa com podria afectar la variació d’un píxel al calcular angles entre minúties:

L’ angle que tindríem en aquest cas seria de

angle = argtg (178-167/169-176)= -57.52

Ara mirem que passaria si tinguéssim una distorsió de tan sols un píxel (en el procés d´extracció, que és molt probable que ho tinguem).

Ara les coordenades serien:

L’ angle que tindríem en aquest cas seria de:

angle = argtg (178-167/169-177)= -53,97

Es pot observar una variació de gairebé 4 graus només variant un píxel una de les minúties.

Algorisme Inicial _

_______________________________________________________________________

59

5.4.3.4 Error_tractament_minúties

En fer l’ anàlisi global només tenia en compte les minúties que complien amb un mínim de nivell de similitud i que no siguin les centrals. El fet de no tenir en compte la central està bé, ja que aquesta ja és una parella, però el fet de que en descarti unes prèviament, no es tant correcte, ja que podrien ser minúties bones i s’ha de tornar a mirar per poder-les descartar.

5.4.3.5 Error_emparella_minútia_mes_d’una_vegada

Podem observar en el següent esquema com emparella la minútia 0 del sample amb dues minúties del template, quan només hi pot haver un parella possible.

Figura 5.17: Aparellament doble Template vs Sample.

Aquest error és degut al sistema que utilitza aquest programa, el problema és que com ja s’ha comentat, utilitza el template com a base de referència i li busca les parelles amb la màxima similitud del sample. Pel template, al ser la base, no es repetiran mai les parelles ja que començarà per la primera minútia i a mesura que anirà trobant parelles, passarà a la següent. El problema bé per la part del sample, que pot ser que una mateixa minutia compleixi les toleràncies d’ una o més minuties del template i així les acabi emparellant més d’una vegada. Una possible solució és l’aplicació de filtres per evitar aquest aparellament múltiple. Aquest error és produït degut a recordar la parella amb màxima similitud del template sense fer un anàlisi de totes les minuties amb totes. En el tema següent on es solucionaran tots aquests errors, es farà un filtre que impedirà aquest error, però el que s’acabarà fent en el codi creat, és un nou sistema de càlcul ja que aquest podem veure que es erroni. Anem a veure visualment una mica el comentat.

Algorisme Inicial _

_______________________________________________________________________

60

Observem que en l’ anàlisi global del template no repeteix cap minútia (#).

Figura 5.18: Anàlisi global template.

GLOBAL ANALYSIS:


---------------------------------------------------------------------------------------------------------

14 169 178 304 1

20 0 76 141 -132

19 1 57 142 -127

18 0 70 8 -34

17 1 109 19 -19

15 1 18 143 -157

13 1 23 121 157

12 1 13 17 122

10 1 44 46 20

8 0 92 43 11

7 1 77 105 157

6 0 74 75 32

5 1 57 120 99

4 1 129 124 102

3 1 182 97 46

1 0 150 121 95

0 0 167 91 105

Algorisme Inicial _

_______________________________________________________________________

61

En el sample, com que a cada minútia se li associa la seva veïna del template, amb més grau de similitud, apunta algunes de repetides.

Figura 5.19: Anàlisi global sample.

Finalment, el programa acaba emparellant la 0 dues vegades, com ja havíem vist visualment amb la 1 i amb la 4.

Template Sample

# t d Beta Gamma # t d Beta Gamma

4 1 129 124 102 0 0 127 112 98

1 0 150 121 95 0 0 127 112 98

Figura 5.20:Matching

GLOBAL ANALYSIS:


---------------------------------------------------------------------------------------------------------

11 207 156 309 1

20 1 84 2 -94

17 1 52 35 -124

14 1 66 12 -28

16 1 93 22 -25

12 1 17 140 -153

9 0 20 117 147

10 0 11 29 160

7 1 38 52 26

8 1 70 42 12

3 1 51 115 98

5 0 61 64 33

3 1 51 115 98

0 0 127 112 98

1 1 162 85 47

0 0 127 112 98

0 0 127 112 98

Algorisme Inicial _

_______________________________________________________________________

62

5.4.3.6 Error_sistema_aparellament

Com s’ha vist en l’ últim punt, el sistema que s’utilitza per emparellar no és correcte. Ara veurem dos casos possibles d’error d’aparellament.

El sistema a l’hora de trobar parelles, pot donar lloc a dos errors:

CAS A:

La presència de minúties sorolloses al sample pot evitar láparellament dáltres minuties correctes, ja que el programa, al fer l’anàlisi local, detectarà com a veïnes aquestes sorolloses, farà el càlcul de distàncies amb aquestes i veurà que no coincideixen amb les de láltre minútia del template. Això implica que desprès ja no la tindrà en compte al fer el anàlisi global, quan es pot observar en el gràfic inferior que si era una parella correcte. El problema seria que descartaríem possibles minúties bones cara l’anàlisi global.

Figura 5.21:Aparellament incorrecte A

Algorisme Inicial _

_______________________________________________________________________

63

CAS B:

Si casualment hi ha zones semblants en quant a minútia i les seves veïnes, l’anàlisi local, les detectarà com a possibles parelles per al global degut al seu elevat grau de similitud, però serà un error, ja que només tenen una similitud local i detectarà com a possible parella unes minúties que no s´assemblen en res. Fa l’anàlisi local mirant minúties i les seves veïnes i podria detectar zones iguals quan en realitat no ho són, ja sigui per pèrdua de minúties al fer la lectura de l’empremta o per alguna minútia sorollosa que s’ha colat. El que pot passar doncs, és que al recordar una minútia que en un anàlisi local té un grau elevat de similitud( com hem vist pot ser erroni), al fer el anàlisi global i considerar directament aquesta minútia de màxima similitud sense mira la resta de minúties, pot no trobar parella quan possiblement aquesta minútia si que en tenia. Podríem dir que la versió actual del programa fa que aquestes veïnes emmascarin l’anàlisi global. En el gràfic següent podem observar que l'anàlisi local diu que la minútia (a) és parella de la (d) per culpa d'alguna minútia perduda i d'altres afegides. Això fa que l'anàlisi global busqui com a parelles unes que no ho poden ser i deixar de mirar el cas que sí que compliria les toleràncies ( la minútia (b) amb la (d) sí que compliria les toleràncies ).

Figura 5.22: Aparellament incorrecte B.

Degut a aquest error detectat modificaré el sistema per emparellar fent que generi els fitxers globals considerant totes les minúties i que les miri totes amb totes, donant prioritat a les minúties que només es pugin emparellar una vegada.

Codi Creat _

_______________________________________________________________________

64

6 Algorisme d'aparellament corregit

En aquest apartat veurem el sistema, o passos que segueix el programa creat, que

anomenarem “Match” apartar d’un diagrama de flux. La idea general serà com la del programa inicial, però ja comentarem com la manera de fer-ho serà diferent per evitar el mal gestionament de minúties.

En un segon apartat, comentarem els valors dels paràmetres importants del programa.

Un cop vist això veurem les funcions que intervenen en cada anàlisi i es farà l’explicació de cadascuna.

Finalment i com ja s’havia comentat en l’apartat anterior, aquí hi veurem la resolució de tots els errors detectats en el programa inicial i les millores introduïdes.

Codi Creat _

_______________________________________________________________________

65

6.1 Funcionament general

Podríem dividir el procés en 2 grans apartats i un tercer apartat que faria dénllaç entre aquests, un que serà el anàlisi local, on com el seu nom indica, es fa un anàlisi local en la pròpia empremta; i láltre que serà l’anàlisi global, on aquí, ja s’hi fa l’anàlisi entre les dues empremtes: Template-Sample. Aquests dos apartats quedarien units pel procés de creació dúna matriu on veiem el grau de similitud entre minúties i lássignació dúna minútia central. Vegem en la següent figura una descripció general del procés comentat. Observem que la idea general és la mateixa que la del codi inicial.

Lectura del fitxer escollit per lúsuari amb minuties template i sample

Anàlisi local ( pel Template i pel template )

Càlcul de la Matriu de similitud

Busca la minutia central

Un cop centrat fa un anàlisi global

Finalment fa l’aparellament

Figura 6.1: Flux general codi creat.

Codi Creat _

_______________________________________________________________________

66

6.1.1 Anàlisi local

Desprès d’haver fet la lectura del fitxer amb les minúties del Template i Sample amb les seves respectives coordenades X i Y i la seva orientació Alfa (també es llegeix el tipus de minútia per diferenciar els finals de les bifurcacions, però no ho utilitzarem ja que molt fàcilment podríem fer una lectura errònia i canviar una bifurcació per un final), es procedeix a realitzar l’anàlisi local d'aquestes.

# X Y Alfa T

-------------------------------------

0 214 17 35 0

1 183 28 65 0 Figura 6.2: Fitxer d’entrada de dues minúties.

En aquest anàlisi local, el que es fa es agafar cada punt característic o minútia ( # ) de l'empremta i buscar les seves 10 minúties mes pròximes ( segons el valor de la distància d ) o com es diu en el programa Neighbours (veïnes). Apart el programa també fa el càlcul de l’angle format entre la minútia de referència i les seves corresponents veïnes (Gamma) i la diferència entre orientacions, entre la minútia de referència i les seves veïnes (Beta). En el fons el que fa el programa és passar a coordenades polars la posició relativa de cada parella minútia-veïna trobant la distància (d) i l’angle relatiu a la seva posició gamma. Com ja s’ha comentat anteriorment en el fitxer també s’escriu el tipus de minútia (t) encara que desprès no s’utilitzarà.

Figura 6.3: Exemple local per 5 veïnes, la minútia blava és la de referència

A nivell de càlculs la distància es calcula per Pitagores, la gamma com la tangent entre les coordenades x i y i finalment, la beta com una diferència d’angles per fer-ho invariant a la rotació.

Gamma

d Beta

Codi Creat _

_______________________________________________________________________

67

Equacions utilitzades:

gamma=argtg(y,x)

Beta=|(angle orientació referència-angle orientació veïna)|

d=vx2+y2

S’aplicarà aquest anàlisi una vegada pel sample i una altra pel template, de tal manera que en acabar tindrem dos fitxers locals un pel sample i un altre pel template amb totes les minúties i les seves 10 veïnes més pròximes, on una es comptabilitza com a ella mateixa.


----------------------------------------------------------------------------------------------------------------------

12 176 167 -73 1

12 0 0 0 0

14 0 13 17 -57

13 0 15 138 -172

15 0 20 160 -119

9 0 32 131 167

5 0 46 137 93

10 0 49 63 5

19 0 62 159 -116

7 0 66 122 163

6 0 75 92 22

Figura 6.4: Exemple fitxer creat en l’anàlisi local per la minutia 12.

Codi Creat _

_______________________________________________________________________

68

6.1.2. Creació Matriu de Similitud i assignació de la minútia central

Un cop s’ha fet l’anàlisi local i tenim els dos fitxers amb les minúties i les seves 10 veïnes, el que passa a fer és agafar la minútia 0 i la seva veïna 0 del template, i amb la minútia 0 veïna 0 del sample mirar els valors dels angles i la distància per veure si entren dins les toleràncies, en cas de ser així la posició [0,0] de la matriu de similitud s’incrementaria en 1. El següent pas seria mirar la minútia 0 i la seva veïna 0 del template i amb la minútia 0 veïna 1 del sample, i així successivament fins mirar les seves 10 veïnes. Un cop mirades totes les veïnes faria la minútia 0 i la seva veïna 1 del template i amb la minútia 0 veïna 0 del sample. Aquests procés el fa per totes les minúties, per tant, en acabar la primera minútia del template, faria la següent: la minútia 1 i la seva veïna 0 del template i amb la minútia 0 veïna 0 del sample.

En acabar de mirar totes les minúties i les seves veïnes del template amb les del sample, genera la matriu de similitud, on podem veure el número de veïnes que entren dins les toleràncies entre minúties; o dit d’una altra manera, la similitud que hi ha entre les minúties.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

------------------------------------------------------------------------------------------------------

0| 3 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0

1| 3 2 2 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0

2| 2 2 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0

3| 1 3 2 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0

4| 4 1 1 0 2 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1

5| 0 0 0 5 1 1 0 0 0 1 3 1 2 0 0 0 0 0 0 0 0

6| 0 0 0 0 0 3 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0

7| 0 0 0 3 1 1 1 1 1 0 1 0 1 1 1 0 0 0 0 0 0

8| 0 0 0 0 0 0 1 1 4 0 0 0 1 1 1 0 1 1 0 0 0

9| 0 0 0 1 0 1 1 0 2 1 1 1 1 1 1 1 1 1 0 0 0

10| 0 1 0 0 0 3 1 5 1 0 1 0 0 0 0 0 0 0 0 0 0

11| 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1

12| 0 0 0 1 0 2 1 0 0 2 5 2 0 0 0 0 0 2 1 0 0

13| 0 0 0 1 0 0 3 0 2 3 2 0 2 0 0 1 1 2 0 0 0

14| 0 0 0 0 0 1 1 0 0 1 1 7 0 0 1 0 0 0 2 0 0

15| 0 0 0 1 0 1 0 1 1 0 2 1 6 0 0 0 0 1 2 0 0

16| 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 2 1 2 0 0

17| 0 0 1 0 0 0 1 0 0 0 0 0 0 2 2 2 4 1 1 0 1

18| 0 0 1 0 0 0 0 0 2 0 0 0 0 1 4 0 3 0 2 0 1

19| 0 0 0 0 0 1 0 0 0 2 0 1 2 0 1 1 3 5 2 1 1

20| 0 0 0 0 0 0 0 1 0 1 0 0 0 1 2 1 2 2 2 1 1

Figura 6.5: Taula similitud entre 20 minúties template i 20 minúties sample.

Codi Creat _

_______________________________________________________________________

69

Un cop ja tenim la matriu de similitud es busquen les minúties del template que tenen més similitud amb les del sample i es memoritza. Les dues minúties amb més semblança passen a ser les minúties centrals de cada empremta. Ara que ja tenim la minútia central que ens farà de referència podem passar l’anàlisi global. En el cas de la figura anterior serien la 11-14 que tenen un nivell de similitud de 7.


En l’anàlisi global es calculen altre cop el valor de distàncies i angles respecte la minútia triada com a central. Ara enlloc d’agafar les minúties del template amb les seves parelles del sample memoritzades que tinguin un mínim de similitud de 2,el que farem serà mirar totes les minúties del template a veure quines possibles parelles pot tenir en el sample i crear una matriu de similitud global on es reflecteixi el número de parelles possibles que pot tenir cada minútia del template amb cada minútia del sample. Desprès, per tal de realitzar les parelles, es miraran les que només tinguin una possible parella, ja que aquesta s’ha de emparellar. Desprès miraré les que tenen dos possibles parelles i així repetidament, això es fa per tal de evitar que si una minútia A te dos possibles parelles com poden ser les parelles 1 i 3 i una altre minútia B només té una parella que pot ser la 1, emparelli la 1 de la minútia A i llavors la minútia B es quedi sense parella perdent-la. A l‘emparella primer les que tenen només una possible parella, és a dir, la 1 de la minútia B llavors al mirar l´altre minútia A que en té dues ja l’emparellaria amb la 3, que serà la que li queda sense utilitzar i així no hauré perdut cap parella. Anem a veure la matriu de similitud del que acabem de comentar.

0 1 2 3

----------------

0| 0 0 0

Minútia A-------------------------------->1| 1 0 1

Minútia B-------------------------------->2| 1 0 0

3| 0 0 0

4| 0 0 0

Figura 6.6: Matriu similitud global de 4 minuties template i 3 minuties sample.

Codi Creat _

_______________________________________________________________________

70

Un cop fetes totes les parelles possibles només queda fer el recompte de parelles per poder dir si les empremtes són iguals o no. En l’esquema següent podem observar les minúties del template(esquerra) i les del sample(dreta) numerades. Així com les parelles fetes indicat per les línies blaves. La minútia central també queda reflectida ja que es d’on surten totes les línies vermelles.

Figura 6.7: Emparellat final template amb sample.

Codi Creat _

_______________________________________________________________________

71

6.2 Paràmetres del programa

El programa utilitza una variable que es diu “neighbours”, que són el número de veïnes que mirarà per fer l’anàlisi local i que també ens afecta a l’hora de determinar la minútia central.

En el programa el número de veïnes és de 9, ja que una de les que conta com a veïna és ella mateixa.

Un altre paràmetre important, és el nivell mínim que ha de tenir una minútia per tal que la podem considerar central, la variable que marca aquest valor es SD_Threshold. S’utilitza un valor de similitud mínima de 5, si una minútia no arriba a tenir aquest nivell no pot ser central.

Els dos altres factors molt importants en el programa són les toleràncies, tant per distàncies, com per angles, aquests valors els ajustarem en l‘apartat següent on per mitjà de proves amb el programa trobarem els valors adequats. Finalment caldria determinar el número de parelles que s’han de fer per tal de considerar si són iguals les dues empremtes o no. El programa creat dóna per bones les empremtes si troba un mínim de 11 parelles.

Codi Creat _

_______________________________________________________________________

72

6.3 Explicació funcions

En aquest apartat s’explicaran les funcions utilitzades en el programa creat, el codi d’aquestes i el del programa es pot trobar a l’annex.

Primer veurem un esquema general d’execució de les principals funcions que s’utilitzen en el programa.

Lectura del fitxer escollit per l´usuari amb minuties template i sample

Aplicació funció Local Feature Distance ( pel sample i pel template )

Càlcul de la matriu de similitud a partir de la funció similarity degree

Busca la minutia central amb central feature

Un cop centrat fa un analisis global amb Global Feature

Finalment, fa l’aparellament amb funció Matching

Figura 6.8: Flux execució funcions principals.

Codi Creat _

_______________________________________________________________________

73

Vist el flux general anem a veure cada funció segons els tres grans apartats anomenats anteriorment del programa, que són: l’anàlisi local, la Creació Matriu de Similitud i assignació de la minútia central i l’anàlisi global.

6.3.1 Anàlisi Local Un cop s’ha fet la lectura del fitxer amb les minúties de cada empremta procedim a

fer l’anàlisi local d’aquestes. La funció encarregada de fer aquest anàlisi és Local Feature Distance. Anem a veure l’esquema que segueix aquesta funció i les subfuncions que utilitza.

Figura 6.9: Flux funció local feature distance

Es crea el fitxer per escriure l’anàlisi local

Fa un bucle des de 0 fins el nº de minúties que té on aplica les següents funcions

Funció veïnes

Funció Ordena

Escriu minúties al fitxer i torna a fer el bucle

Finalment tancar el fitxer local creat

Codi Creat _

_______________________________________________________________________

74

Abans de veure la funció de l’anàlisi local local feature distance, comentarem les subfuncions que es fan servir.

Com es pot observar en el diagrama de flux anterior, la primera subfunció que s’utilitza és la que rep el nom de veïnes.

6.3.1.1 Funció Veïnes

Anem a veure les variables passades i el que fa aquesta subfunció.

Variable Definició

*mnt Variable tipus minútia (conté paràmetres minúties )

n número minúties

distx Coordenada x minútia

disty Coordenada y minútia

ang Angle minútia

Descripció i resultat

Aquesta funció fa el càlcul de la distància entre una minútia que s’agafa com a referència i la resta de minúties així com també en calcula l’angle polar i relatiu.

6.3.1.2 Funció Ordena


Variable Definició


n número minúties


Aquesta funció el que fa és ordena les minúties de petites a grans segons la distància.

Codi Creat _

_______________________________________________________________________

75

6.3.1.3 Funció Local Feautre Distance

Anem a veure les variables passades i el que fa aquesta funció.

Variable Definició *mnt Variable tipus minútia (conté paràmetres

minúties )

n número minúties

*file nom del fitxer


Aquesta funció el que fa és crear un fitxer local on tindrem totes les minúties i les seves veïnes amb valors de distàncies i angles. Un cop tenim obert el fitxer, fa un bucle

per recórrer totes les minúties i aplicar la funció Veïnes ( realitza els càlculs ) i la funció Ordena ( ordena minúties segons la distància ). Un cop tenim els valors de les minúties calculats i ordenats, podem procedir a escriure els X primers veïns de cada

minútia al fitxer local ja que al estar ordenats, ja són els mes pròxims o veïns.

Observem el resultat obtingut:


---------------------------------------------------------------------------------------------------

12 176 167 -73 1

12 0 0 0 0

14 0 13 17 -57

13 0 15 138 -172

15 0 20 160 -119

9 0 32 131 167

5 0 46 137 93

10 0 49 63 5

19 0 62 159 -116

7 0 66 122 163

6 0 75 92 22

Figura 6.10: Exemple anàlisi local per la minútia 12.

Codi Creat _

_______________________________________________________________________

76

6.3.2 Creació Matriu de Similitud i assignació de la minútia central

Un cop tenim el fitxer local amb els valors de distàncies i angles, el següent pas és veure el grau de similitud entre minúties de les dues empremtes template i sample creant la matriu de similitud. Després, per mitjà d’aquesta matriu es determinarà la minútia central de cada empremta. Anem a veure l’esquema que s’utilitza.

Figura 6.11: Creació Matriu de Similitud i assignació de la minútia central.

6.3.2.1 Funció Similarity Degree


Variable Definició

nsmp número minúties sample

ntmp número minúties template


Aquesta funció crea un fitxer per guardar la matriu de similitud. Desprès, mira totes les minúties amb les seves veïnes del template amb totes les minúties i les seves veïnes del sample, mira quantes en tenen que compleixin les toleràncies, i finalment,

escriu la matriu al fitxer amb una subfunció que veurem a continuació que es diu escriu_matriu.

Funció Similarity Degree

Escriu_Matriu

Funció Central Feature

Codi Creat _

_______________________________________________________________________

77

6.3.2.2 Funció Escriu Matriu


Variable Definició *fitxer Fitxer que s’utilitza

ntemp número minúties template

nsamp número minúties template

Matriu[NMNT][NMNT] Taula per crear la matriu


Aquesta funció el que fa és escriure al fitxer indicat la matriu de similitud.

Observem el resultat obtingut: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

------------------------------------------------------------------------------------------------------

0| 3 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0

1| 3 2 2 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0

2| 2 2 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0

3| 1 3 2 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0

4| 4 1 1 0 2 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1

5| 0 0 0 5 1 1 0 0 0 1 3 1 2 0 0 0 0 0 0 0 0

6| 0 0 0 0 0 3 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0

7| 0 0 0 3 1 1 1 1 1 0 1 0 1 1 1 0 0 0 0 0 0

8| 0 0 0 0 0 0 1 1 4 0 0 0 1 1 1 0 1 1 0 0 0

9| 0 0 0 1 0 1 1 0 2 1 1 1 1 1 1 1 1 1 0 0 0

10| 0 1 0 0 0 3 1 5 1 0 1 0 0 0 0 0 0 0 0 0 0

11| 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1

12| 0 0 0 1 0 2 1 0 0 2 5 2 0 0 0 0 0 2 1 0 0

13| 0 0 0 1 0 0 3 0 2 3 2 0 2 0 0 1 1 2 0 0 0

14| 0 0 0 0 0 1 1 0 0 1 1 7 0 0 1 0 0 0 2 0 0

15| 0 0 0 1 0 1 0 1 1 0 2 1 6 0 0 0 0 1 2 0 0

16| 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 2 1 2 0 0

17| 0 0 1 0 0 0 1 0 0 0 0 0 0 2 2 2 4 1 1 0 1

18| 0 0 1 0 0 0 0 0 2 0 0 0 0 1 4 0 3 0 2 0 1

19| 0 0 0 0 0 1 0 0 0 2 0 1 2 0 1 1 3 5 2 1 1

20| 0 0 0 0 0 0 0 1 0 1 0 0 0 1 2 1 2 2 2 1 1

Figura 6.12: Exemple Matriu similitud de 20 minúties Template i 20 minúties Sample.

Codi Creat _

_______________________________________________________________________

78

6.3.2.3 Funció Central Feature


Variable Definició nsmp numero minúties sample

ntmp numero minúties template


Aquesta funció recórrer la matriu de similitud buscant la parella de minúties template-sample que té més semblança o grau de similitud. Així obtenim les minúties

centrals de cada empremta. La funció mira que la parella compleixi amb un nivell mínim. En cas de trobar més d’una parella amb el màxim grau de similitud es quedarà

amb la parella central

Codi Creat _

_______________________________________________________________________

79


Un cop tenim les minúties centrals de cada empremta podem procedir a fer l’anàlisi global d’aquestes. Les funcions encarregades de fer aquest anàlisi són: Global Feature i Matching. Anem a veure l’esquema que s’utilitza.

Figura 6.13: Flux anàlisi Global

Abans de veure la funció de l’anàlisi global global feature, comentarem les subfuncions que és fan servir.

Com es pot observar en el diagrama de flux anterior, la primera subfunció que s’utilitza és la que rep el nom de global_parameters.

6.3.3.1 Funció Global_parameters


Variable Definició

*file Fitxer que s’utilitza


n_minuties Número minúties

cf Minútia central


Aquesta funció calcula els angles (relatiu i polar) i la distància de cada minútia respecte la minútia central i ho escriura en el fitxer indicat.

Funció Global Feature Global_Parameters

Global_Similarity

Escriu_Matriu

Funció Matching

Codi Creat _

_______________________________________________________________________

80

6.3.3.2 Funció Global_Similarity


Variable Definició nsmp Número minúties sample

ntmp Número minúties template


Aquesta funció crea un fitxer per guardar la matriu de similitud global. Mira totes les minúties del template amb totes les del sample i les guarda en forma de taula

indicant-ho amb un 1 les que compleixin les toleràncies i, per tant, poden ser parelles. Finalment, escriu la matriu al fitxer amb una subfunció que veurem a continuació, que

es diu escriu_matriu.

6.3.3.3 Funció Escriu Matriu


Variable Definició *fitxer Fitxer que s’utilitza

ntemp Número minúties template

nsamp Número minúties template

Matriu[NMNT][NMNT] Taula per creà la matriu


Aquesta funció escriu al fitxer indicat la matriu de similitud.

Observem el resultat obtingut:

0 1 2 3

----------------

0| 0 0 0

1| 1 0 1

2| 1 0 0

3| 0 0 0

4| 0 0 0

Figura 6.14: Matriu similitud global de 4 minúties template i 3 minúties sample.

Codi Creat _

_______________________________________________________________________

81

6.3.3.4 Funció Global Feature


Variable Definició cf Minútia central


nsmp Número minúties template


Aquesta funció aplica la subfunció “global parameters” tant pel sample com pel template per tal de tenir els valors respecte la minútia central calculats. Un cop té això,

aplicant la subfunció “global similarity” genera la matriu de similitud global, on es veuen les possibles parelles. Ara que ja tinc les possibles parelles recorreré la matriu i aniré marcant les parelles fetes amb la variable gfm i la seva parella amb la variable

ltwin, seguint l’estratègia d’emparella primer les minúties que només tenen una possible parella, desprès les de dos, desprès les de tres i així successivament.

6.3.3.5 Funció Matching


Variable Definició

cf Minútia central



Aquesta funció escriu un fitxer de les parelles marcades per la “funció global” feature i contar-ne el número total de parelles fetes, que passarà al programa principal, i aquest, segons s’hagin fet més o menys de 11 parelles, donarà l’empremta per igual o

no.

Codi Creat _

_______________________________________________________________________

82

6.4 Resolució dels errors

En aquest apartat el que es busca és resoldre els errors trobats en el codi inicial.

6.4.1 Resolució Errors Anàlisi Local

6.4.1.1 Resolució_error_domain

Per tal d'evitar l'error que dóna al fer l’argtg de 0 hem posat la següent condició, el que fa és que si es dóna el cas que provoca l’error, que és quan les coordenades són 0, dóna l’angle per aquest cas concret que és 0.

Solució: if ((y1==0)&&(x1==0)) gamma=0; //així evito error q provoca atan2

6.4.2 Resolució Errors Creació Matriu de Similitud i assignació de la minútia central

6.4.2.1 Resolució_error_condició_distància

Solució:

if ((abs(smp[j].ld2[p]-distancia)<limite1)&& (distancia>0)&&(smp[j].ld2[p]>0))

S’han posat les dues condicions per mirar si les distàncies són 0 i no per mirar la diferència a la condició de distància a la funció “similarity degree” per evitar que es tingui en compte a ella mateixa ( és lògic que si fa una resta amb ella mateixa el resultat sigui 0 ) i sense tenir el problema de que es pugui donar el cas de que la resta entre distàncies sigui 0 i deixem de considerar una minútia bona.El que es fa doncs, és mirar si una de les dues variables de distàncies ( sample i template ) són 0 i així saber que és ella mateixa. Ara ja puc torna a posar nivell de similitud local 2, ja que no es té en compte ella mateixa i havia posat que era 3 per això.

6.4.2.2 Resolució_error_condició_angle

Solució: If (abs(smp[j].la[p]+theta1)>180-limite2)

Aquí si es considera el límit d’angles amb la variable limite2 per posar la condició.

Codi Creat _

______________________________________________________________________

83

6.4.2.3 Resolució_error_funció_central_feature

El que es farà és fer una etiqueta (nocentralfeature) per recordar les que no poden ser centrals i no cometre l’error que es feia de posar el lsd a 0 si es donava la condició de tenir el nivell màxim repetit a la fila.

Solució:

unsigned int nocentralfeature[NMNT]; //etiqueta per evitar que pugui ser central

for (i=0;i<ntmp;i++) nocentralfeature[i]=0; //inicialitzo vector a 0

if (sc!=1)

nocentralfeature[i]=1; //etiqueta per evitar que pugui ser central si es dóna condició

if (tmp[i].lsd<2) // AFEGEIXO UN THRESHOLD DE SIMILARITAT LOCAL >=2

tmp[i].lsd=0;

tmp[i].ltwin=0xff;

if ((tmp[i].lsd>sd)&&(nocentralfeature[i]==0)) //Condició evita que sigui central si te la marca

sd=tmp[i].lsd;

cf=i; // central feature

Codi Creat _

______________________________________________________________________

84

6.4.2.4 Resolució_error_compta_repetides

Evitarem que conti minúties repetides contant les vegades que es repeteix i després restant aquestes vegades que es repeteix.

Solució: for (int x1=0; x1<40; x1++)

if ( filtro_smp[x1]>1 ) // La variable filtro te guardat les vegades que s´ha repetit l´aparellament, tenim prou amb un vector i no cal una taula de 2 dimensions perquè ho fa a cada pas de bucle( per cada fila )

repes=filtro_smp[x1];

repes--; //Per tenir el valor de les vegades que sens ha repetit l´aparellament, resto 1 perquè una vegada si que es correcte que es la de la parella bona

smlrty[i][j]=smlrty[i][j]-repes;

Anem a veure un exemple: Tmp # 15.Neighbour # 22 - Smp # 0.Neighbour # 3



En aquest cas el que ha fet és emparellar la minútia 0 del sample i la seva veïna 1 dues vegades, la qual cosa es lògic que no pot ser. Si tot és correcte hauria de donar 2 parelles ja que una està repetida.

Figura 6.15: Taula de similitud entre 23 minúties template i 14 minúties sample.

Codi Creat _

______________________________________________________________________

85

6.4.3 Resolució Errors Anàlsis global

6.4.3.1 Resolució_error_domain

Per tal d'evitar l'error que dóna al fer l’argtg de 0 hem posat la següent condició, el que fa és que si passa el cas que dóna error, que és quan les coordenades són 0 dóna l’angle per aquest cas concret que és 0.

Solució: if ((y1==0)&&(x1==0)) gamma=0; //així evito error q provoca atan2

6.4.3.2 Resolució_error_condició_angle

Solució: If (abs(smp[j].la[p]+theta1)>180-limite2)

Aquí si que es considera el límit d’angles amb la variable limite2 per posar la condició.

6.4.3.3 Resolució_error_tolerància_angles

El que es farà és tenir 3 marges de toleràncies segons les distàncies de template. Els valors més concrets dels límits s’ajustaran per mitjà de proves en el següent tema.

Solució

limite1=20; limite2=20;//limite1 distancia, limite2 angle

if (distancia>100) limite1=40; limite2=10;

if (distancia<30) limite1=20; limite2=40;

Distància= Distància en el template

Codi Creat _

______________________________________________________________________

86

6.4.3.4 Resolució_error_tractament_minuties

El que s’ha fet és eliminar la condició en vermell perquè miri totes les minúties sense descartar-ne de prèvies. Es manté la condició que si la mintúia és central no cal mirar-la perquè ja sabem que té parella, però es treu la de que ha de tenir un nivell mínim.

Solució:

If (( i!=cf )&&(tmp[i].lsd!=0))

6.4.3.5 Resolució error emparella minutia mes d’una vegada

Haurem de posar filtres per evitar-ho. Són simplement etiquetes que recorden les parelles ja utilitzades. Aquesta solució no serà la definitiva, ja que com veurem en el següent punt 6.4.3.6 el sistema de càlcul no és correcte i es cambiarà però es dóna la solució per arreglar el codi inicial.

Solució:

En la funció global feature for(x=0;x<i;x++) tmp[x].gfm=0; // inicialitzem el vector a 0

if (tmp[i].gfm>=1)

tmp[i].gfm=1;

smp[tmp[i].ltwin].gfm=1;// posa a 1 les dues parelles template i sample

filtro_repes[tmp[i].ltwin]++; // incrementa sample emparellat en 1, al template al ser la referència ja no passa que la pugui agafar la mateixa més d´una vegada per tant hem de protegir sample=parella template.

filtro_repes2[tmp[i].ltwin]++; //com filtro repes però una copia pel sample.

filtro_repes3[tmp[i].ltwin]++; //copies auxiliars per el dibuix gràfic

En la funció matching if ((tmp[i].gfm!=0)&&(filtro_repes[tmp[i].ltwin]!=0)) // Miro si es parella en la primera

condició ja que si ho es tmp[i].gfm=1 i si veïna es diferent de 0 que vol dir que encara no s´ha emparellat cap vegada.

filtro_repes[tmp[i].ltwin]=0; // si entra ho he de possar a 0 que vol dir que la minutia del sample aquesta ja le utilitzat i no la puc repetir.

fprintf(pf,"\t \t \t \t \t \t %3d \t %1d \t %4d \t %4d \t %3d \n",i,tmp[i].mtp,tmp[i].gd,tmp[i].ga,tmp[i].gdir);

Aplicat una pel sample i altre pel template.

Codi Creat _

______________________________________________________________________

87

Degut l’últim canvi, el número de parelles resultants també és incorrecte i el farem així.

if ((tmp[i].gfm!=0)&&(filtro_repes2[tmp[i].ltwin]!=0))

filtro_repes2[tmp[i].ltwin]=0;

result++; // es molt simple cada cop que entra compta una parella, no hi ha problema perquè ara ja no repeteix parelles.

fprintf(pf,"\t \t \t \t \t \t %3d \t %1d \t %4d \t %4d \t %3d \n",tmp[i].ltwin,smp[tmp[i].ltwin].mtp,smp[tmp[i].ltwin].gd,smp[tmp[i].ltwin].ga,smp[tmp[i].ltwin].gdir);

Afegim la variable result que s´incrementa per cada parella escrita al fitxer Matching.

Amb tot això genera el fitxer Matching de forma correcta, ara ho arreglarem amb un filtro_repes3[NMNT]; que ens servirà per dibuixar-ho de forma correcta. També afegirem una condició com s´ha fet en la funció Matching.

unsigned char i=ntmp-1;

do

if ((tmp[i].gfm!=0)&&(filtro_repes3[tmp[i].ltwin]!=0))

filtro_repes3[tmp[i].ltwin]=0;

sprintf(comando,"plot([%d,%d],[%d,%d],'r-');",tmp[n].mpy,tmp[i].mpy,tmp[n].mpx,tmp[i].mpx);

MatLab->Exec(comando); // Drawing the line

sprintf(comando,"plot([%d,%d],[%d,%d],'r- ');",256+smp[tmp[n].ltwin].mpy,256+smp[tmp[i].ltwin].mpy,smp[tmp[n].ltwin].mpx,smp[tmp[i].ltwin].mpx);


// Es dibuixa també les minuties tmp-smp emparellades de color blau enlloc de verd

sprintf(comando,"plot([%d,%d],[%d,%d],'b- ');",tmp[i].mpy,256+smp[tmp[i].ltwin].mpy,tmp[i].mpx,smp[tmp[i].ltwin].mpx);


//Sleep(10000);

while (i--);

Codi Creat _

______________________________________________________________________

88

Observem com ara ja només s´emparella una vegada.

Figura 6.16: Aparellament correcte Template vs Sample.

Codi Creat _

_____________________________________________________________________

89

6.4.3.6 Resolució error sistema aparellament

Amb tots els errors solucionats el programa ja funcionaria de forma correcta, però el sistema no es massa òptim, per tant, es canviarà el sistema de càlcul en l’anàlisi global. La funció comentada que farà aquesta feina és la “global feature” que es pot veure en l’annex final. Ara comentarem el que fa i el que té en compte aquesta funció.

El que es fa inicialment és un càlcul de totes les minúties en quant a distància i angles respecte la minútia central, tant pel template com pel sample.

Desprès, es crea una matriu de similitud on es reflexen les possibles parelles, al crear la matriu, ja s’aplica la solució de tenir diferents límits segons les distàncies de template i sample.

Es recorre la matriu creada per mirar quin és el màxim número de parelles que té cada minútia. Aquesta variable serà molt important ja que em permetrà començar a emparellar les minúties que només tinguin una parella. Després les de dues i així successivament, per tal de no prendre parelles a minúties que només puguin tenir una parella.

Per emparellar la primera condició que mira que és que tingui només una parella possible, un cop es compleix aquesta condició, mirarà que la parella que es pot fer no hagi estat utilitzada anteriorment.

Finalment, quan s’ha trobat una parella el que es fa és marca aquesta parella per tal que no es repeteixi i actualitzar el número de parelles possibles de les minúties, ja que aquesta parella feta pot afectar a varies d’elles. Diem que pot afectar a varies d’elles pequè per exemple: si s’emparella la minútia 1 del template amb la 6 del sample, pot ser fàcilment que la minútia 6 del sample tingués altres candidates a parella, que ara, hauran de reduïr el seu grau de parelles possibles en una unitat.

Verificació programa _

_____________________________________________________________________

90

7 Verificació Programa

En aquest apartat el que es pretén, és fer un estudi aplicant el programa a 4 empremtes diferents, on de cada empremta es tindran 4 mostres de la mateixa. Aquestes mostres de la mateixa empremta són de diferents posicions i qualitat.

L’objectiu doncs, serà treure un % d’encerts i un % d’errats. Si tot funciones a la perfecció el programa hauria de trobar 3 parelles dolentes (corresponents a les 4 empremtes diferents), i 12 de bones (corresponent a les 16 mostres de les empremtes, que són variacions d’ella mateixa).

Finalment, després d’haver analitzat les diferents empremtes es donarà el % final d’error i el valor de toleràncies que s’ha acabat ajustant.

Anem a veure l’estructura que es seguirà per fer el procés d’escrit.

Empremta template

Empremta sample

Minúties trobades template

Minúties trobades sample

Matching

Resultat

Figura 7.1: Procés de verificació del programa.

Ens basarem en el gràfic d’aparellament que dóna el nostre programa, per tal de comentar si creiem que alguna podria entra dins les toleràncies.

En cas de trobar 11 parelles o més les minúties direm que són les mateixes, sinó arriben a 11 parelles les empremtes seran diferents.

Els valors de toleràncies que utilitzarem per fer les comparacions són: si la distància és superior a 100 píxels tindrem 40 píxels de tolerància per distància i 10 graus per angles; si la distància es entre 30 i 100 píxels tindrem una tolerància de 20 tant per distància com per angles; i si es més petita de 30 píxels serà de 20 píxels per distància i 40 graus pels angles.




_____________________________________________________________________

91

Com es evident l’aparellament no serà perfecte per tant tindrem uns marges d’error o toleràncies per tal de donar minúties com a iguals o no, podríem dir que són les zones vàlides dins les quals les minúties es consideren com a iguals.

Anem a veure en un esquema de quins són els paràmetres que mirarem al comparar i als quals aplicarem les toleràncies (figura 7.2). El primer que mirarem serà la distància que hi ha de la minútia, fins la minútia central (d). L’angle format entre la minútia central i la seva corresponent minútia que estem mirant (Gamma) i la diferència entre orientacions entre la minútia central i la minútia que estem mirant (Beta).

Figura 7.2: Exemple per les toleràncies de distància i angles.

Les toleràncies en el cas dels angles com mes pròxim estigui, la tolerància haurà de ser més gran per tenir més obertura (figura 7.3 cas b) i si està més lluny no caldrà obrir tant l’angle per tal de que la minútia estigui dins les toleràncies (figura 7.3 cas a). Pel que fa a distàncies si està més aprop la tolerància podrà ser més petita (figura 7.3 cas d) i si està més lluny la tolerància serà més gran (figura 7.3 cas c). Aplicarem 3 zones de toleràncies, per distàncies més petites de 30 píxels, per distàncies entre 30 píxels i 100 píxels i per distàncies superiors a 100 píxels.

(a) (b)

(c) (d)

Figura 7.3: Exemples toleràncies.

Gamma

d Beta


_____________________________________________________________________

92

7.1 Empremtes iguals

Empremta 1_1 vs Empremta 1_2

Observem que les minúties del sample troben totes la seva parella,excepte la minútia 4 que no té parella, per inspecció visual veiem que no en té cap de possible al template.

El número de parelles fetes es de 18 respecte un màxim de 18 trobades visualment.


_____________________________________________________________________

93


Les minúties que no emparella són les més allunyades, anem a veure perquè la 24 del sample no té parella amb la 30 o 28 del template. Les minúties no entren dins les toleràncies per la orientació beta que es molt diferent.



_____________________________________________________________________

94


Aquí la que potser podria emparellar es la 27 del template amb la 20 del sample, pel que fa a distància i angle són molt similars, però pel que fa a l’orientació té una diferència de 118 graus.



_____________________________________________________________________

95


Aquí les que potser podria emparellar són la 16 del template amb la 14 del sample i la 21 del template amb la 18 del sample. Les dues no entren per culpa de la orientació beta. La parella 17-12 ha entrat ja que s’ha reduït la zona de tolerància de 100 a 90.

El número de parelles fetes es de 12 respecte un màxim de 15 trobades visualment..


_____________________________________________________________________

96


Aquí la que potser podria emparellar é la 21 del template amb la 19 del sample. Tampoc entra per culpa de l’orientació beta.



_____________________________________________________________________

97


Aquí la que potser podria emparellar és la 17 del template amb la 19 del sample. Tampoc entra per culpa de l’orientació beta que té una diferència de 65 graus.



_____________________________________________________________________

98


Aquí la que potser podria emparellar é la 24 del template amb la 23 del sample. Tampoc entra per culpa de l’orientació beta que té una diferència de 26 graus.



_____________________________________________________________________

99




_____________________________________________________________________

100


Aquí la que potser podria emparellar és la 14 del template amb la 14 del sample. Tampoc entra per culpa de l’orientació beta.



_____________________________________________________________________

101


Aquí la que potser podria emparellar és la 30 del template amb la 30 del sample. Tampoc entra per culpa de l’orientació beta.



_____________________________________________________________________

102


No s’observa cap possible parella més.



_____________________________________________________________________

103




_____________________________________________________________________

104

7.2 Empremtes diferents En aquest apartat com cap de les comparacions trobava una minútia central amb el

nivell de similitud mínima demanat, les empremtes queden descartades com a bones (això ja es el que volem), però el que s’ha fet per veure les parelles que fa, és posar el nivell mínim de similitud a 0.


El número de parelles fetes es de 7.


_____________________________________________________________________

105




_____________________________________________________________________

106




_____________________________________________________________________

107

7.3 Resultats i toleràncies

El programa sense haver casi de modificar els paràmetres, ha tingut un encert del 100%. Ha trobat com a bones les 12 parelles i també ha detectat les 3 falses. Per tal de tenir un millor rendiment del programa, s’ha mirat de ajustar les toleràncies tot mirant els resultats que surtien dels emparellaments amb el programa. Els petits canvis que s’han fet durant el procés de verificació per tal que el programa sigui més precís són: posar el marge de tolerància a 90 píxels (amb la qual cosa aconseguim un encert més gran) i no a 100 píxels com s’havia posat inicialment, donar 5 graus més de tolerància als angles si la distància és superior a 90 píxels i per últim s’ha augmentat la tolerància en 5 graus si la distància és més petita de 30 píxels i s’ha reduït la tolerància en distàncies en 10 píxels pel mateix cas de una distància inferior a 30 píxels (aquest canvi també s’ha fet per obtenir un nombre de parelles més gran). Aquests petits canvis, s’han fet observant les empremtes originals i així poder veure les parelles que teòricament eren correctes i el programa per un ajust de toleràncies no les agafava. El programa al fer els càlculs numèrics de distàncies i escriureu en un fitxer, et dóna la facilitat de veure per quins valors de toleràncies aquella parella l’hagués donat per bona i per tant poder fer l’ajust.

Finalment, els marges de toleràncies queden a 30 píxels i 90 píxels. En distàncies més petites de 30 píxels, les toleràncies són de 10 píxels pel que fa a distància i de 45 graus pel que fa a l’angle. En distàncies entre 30 i 90 píxels, les toleràncies són de 20 píxels pel que fa a distància i de 20 graus pel que fa a l’angle. En distàncies més grans de 90 píxels, les toleràncies són de 40 píxels pel que fa a distància i de 15 graus pel que fa a l’angle.

Figura 7.4: Toleràncies.

L’ajust de les toleràncies podria ser més precís, però com ha complert la prova al 100% tampoc no s’ha mirat de precisà més.

Segurament el fet de fer alguna zona més de toleràncies ens donaria més exactitud.

Conclusions_______ _

_____________________________________________________________________

108

8 Conclusions

El sistema d’identificació d’empremtes, és un sistema molt segur ja que es necessita de la persona autoritzada per tenir accés, per tant diríem que es un bon substitut del PIN o password. Una altre avantatge és que no necessites portar cap element com pot ser una clau o targeta. La principal dificultat que presenta aquest sistema, és la seva complexitat per poder comparar empremtes ja que aquestes no sempre es troben en un estat òptim.

El que s’ha vist, és que la base principal alhora de comparar empremtes és el procés d’extracció, sense un bon procés d’extracció el nostre programa de comparació d’empremtes per molt bo que sigui no ens serveix de res. Els principals problemes del procés d’extracció són: una mala lectura, els possibles sorolls al llegir, però principalment crec que el pitjor és la lectura parcial o el desplaçament en la lectura de l’empremta. El fet de desplaçar l’empremta vol dir que un número de minuties queden fora de la zona de lectura i en poden entrar d’altres que a nosaltres no ens interessen, dificultant així el matching.

Un altre factor molt important del projecte són les toleràncies aplicades, ja que unes toleràncies molt grans poden donar parelles incorrectes com a correctes i unes toleràncies molt petites pot ser que el programa deixi de trobar parelles bones. Per tant un ajust acurat de toleràncies provoca una millora en el % d’encert del programa d’aparellament.

Cal dir també, que tot i que en les proves de verificació del programa creat hagi donat un encert del 100%, si ho féssim en una base de dades complerta el % d’encert seria menor.

Una implementació d’un sistema d’aquest tipus ens aporta seguretat, degut a la seva dificultat per falsejar-lo i ens aporta comoditat, degut a que no necessitem de cap element que no siguem nosaltres mateixos.

Referències i Bibliografia________________________________________________________________

_____________________________________________________________________

109

9 Referències i Bibliografia

[1] Dario Maio and Davide Maltoni “Direct Gray-Scale Minutiae Detection

in Fingerprints”, IEE transactions on pattern analysis and machine intelligence, january 1997, vol.19, no.1, 27-39.

[2] M.J. Donahue and S.I. Rokhlin “Onthe Use of Level Curves in Image Analaysis”, Image Understanding, 1993, vol.57, no.5, 185-203.

[3] Davide Maltoni, Darioa Maio, Anil K.Jain and Salil Prabhakar, “Handbook of Fingerprint Recognition”, Springer, 2003.

[4] A minutia-based partial finger print recognition system : http://www.cedar.buffalo.edu/~govind/partial.pdf

[5] Biometric security sistems: http://www.fit.vutbr.cz/~orsag/IICAI-03.pdf

[6] Base de dades:”Handbook of fingerprint recognition”.

Codi_____________ _

_____________________________________________________________________

110

10 Codi

//---------------------------------------------------------------------------

//--------------------------INCLUDES-----------------------------------------

//---------------------------------------------------------------------------

#include<stdio.h>

#include<conio.h>

#include <string.h>

#include<math.h>

#include <time.h>

#include <windows.h>

#include <vcl.h>

#pragma hdrstop

#include "io_matlab.h"

#include "memo.h"

#include "maio2.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

//---------------------------------------------------------------------------

/////////////////DEFINES //////////////////////////////////////////////////////////

#define NMNT 200U //numero maximo de minucias que se espera haya

#define Neighbours 10U //numero de vecinas de cada minucia

#define pii 3.14159 // para calculo de angulos

#define SD_Threshold 5U // Central Feature similarity degree threshold

#define Local_Threshold 2U //Similaridad local

#define SizeImage 300U

/////////////// ESTRUCTURAS ////////////////////////////////////////////////////////

typedef struct

// minutia data (vector 1)

unsigned short mpx; // coordenada X

unsigned short mpy; // coordenada Y

int mag; // angulo

unsigned short mtp; // tipo minutia

unsigned short d2; //distancia entre minuties

double gamma; //angulo formado por las minutias

unsigned short numero; //numero minutia

// local data (vector 2 neighbourhood)

unsigned short lmn[Neighbours]; // numero de vecina

unsigned long ld2[Neighbours]; // contiene la distancia con la vecina

double ld[Neighbours]; // angulo gamma

int la[Neighbours]; // angulo theta

unsigned short lt[Neighbours]; // tipo de minucia

unsigned char lsd; //grado de similaridad

Codi_____________ _

_____________________________________________________________________

111

unsigned char ltwin; //Vecina pareja del template

unsigned char gfm; //Sirve para indicar que es pareja

int gd; //para la distancia

int ga; //para el angulo theta

int gdir; //para el angulo gamma

minutia_;

/////////// Global variables///////////////////////////////////////////////////

minutia_ smp[NMNT]; // sample minutiae

minutia_ tmp[NMNT]; // template minutiae

minutia_ s_smp[NMNT]; // Variable auxiliar per poder ordenar al analisi local

int smlrty[NMNT][NMNT]; //Matriz de similaridad

int smlrtyglobal[NMNT][NMNT]; //Matriz de similaridad global

int grau_max[NMNT]; //numero maximo de parejas de cada minutia del template

int noparellaSample[NMNT]; //Para recordar las parejas ya utilizadas

int noparellaTemplate[NMNT]; //Para recordar las parejas ya utilizadas

/******************************************************************************************/

Part II: MINUTIAE MATCHING

/******************************************************************************************/

void Ordena(minutia_* v, int n)//ordena minuties de petites a grans per distancies reben les minuties

// i el numero de minuties

unsigned short insert1,insert2,insert3,insert5;

int insert4;

int k,j, buscando;

for(k=1; k<n; k++)

insert1=v[k].d2; //0rdeno por distancias

insert2=v[k].numero; //numero de minucia que es

insert3=v[k].mag; //diferencia de angulos

insert4=(int)v[k].gamma; //angulo

insert5=v[k].mtp; //tipo

j=k-1;

buscando=1;

while ((j>=0)&& (buscando==1))

if(insert1<v[j].d2)

v[j+1].d2=v[j].d2; //distancia entre minucias

v[j+1].numero=v[j].numero; //nnumero de minucia

v[j+1].mag=v[j].mag; //distancia entre angulos

v[j+1].gamma=v[j].gamma; //distancia entre angulos relativos

Codi_____________ _

_____________________________________________________________________

112

v[j+1].mtp=v[j].mtp; //Tipo minutia

v[j].d2=insert1;

v[j].numero=insert2;

v[j].mag=insert3;

v[j].gamma=insert4;

v[j].mtp=insert5;

j--;

//del if

else

buscando=0;

v[j+1].d2=insert1;

v[j+1].numero=insert2;

v[j+1].mag=insert3;

v[j+1].gamma=insert4;

v[j+1].mtp=insert5;

//del else

//del while

//del for

void Veines(minutia_ *mnt, int n,int distx,int disty,int ang)//Fa calculs de distancia i angles entre minutia

//de referencia i les seves veines,es pasen les minuties,

//el numero de minuties, i els valors de la de referencia

int n2,x1,x,y1,y,d2;

int theta1;

double gamma;

for (n2=0; n2<n; n2++)

//calculo distancia

x1=distx-mnt[n2].mpx;

y1=disty-mnt[n2].mpy;

d2=(int)sqrt((x1*x1)+(y1*y1));

//calculo del angulo

theta1=mnt[n2].mag; if (theta1>270) theta1=theta1-360;

theta1=abs(theta1-ang); //resto angulo asi lo hago invariante a rotacion

//calculo del arcotangente

//devuelve el angulo en radianes

if ((y1==0)&&(x1==0)) gamma=0; //aixi evito error q provoca atan2

Codi_____________ _

_____________________________________________________________________

113

else

gamma=atan2(y1,x1);

gamma=(gamma*360)/(2*pii); //pas a graus

s_smp[n2].mag=theta1;

s_smp[n2].d2=d2;

s_smp[n2].gamma=int(gamma);

s_smp[n2].numero=n2;

s_smp[n2].mtp=mnt[n2].mtp;

void LocalFeatureDistance(minutia_ *mnt, unsigned char n,char *file)//Es fa el calcul de les distancies i angles entre

//minutia de referencia i les seves Neighbours mes proximes

FILE *pf; // File pointer

pf=fopen(file,"wt"); // File opened in binary write mode

if (pf==NULL)

perror("\n Open file not allowed!\n");

clearerr(pf);

exit(1);

int n1,x,y,n2,theta;

// File write process

fprintf(pf,"LOCAL ANALYSIS:\n");

fprintf(pf,"\t # \t X \t Y \tAlfa \t T\t # \t t \t d \t Beta \t Gamma\n");

fprintf(pf,"\t-----------------------------------------------------------------------------------\n");

for (n1=0; n1<n; n1++) //minutia de referencia repecto de la

//cual se calculan las diferencias

x=mnt[n1].mpx; //valor x minutia referencia

y=mnt[n1].mpy; //valor y minutia referencia

theta=mnt[n1].mag;if (theta>270) theta=theta-360;//angle minutia referencia

fprintf(pf,"\t %3d \t %3d \t %3d \t%4d\t %1d \n",n1,mnt[n1].mpx,mnt[n1].mpy,theta,mnt[n1].mtp);

Codi_____________ _

_____________________________________________________________________

114

Veines(mnt,n,x,y,theta);//calcul de la de referencia amb les veines

Ordena(&s_smp[0],n);//Ordena per tenir les mes proximes

for (int n3=0; n3<Neighbours; n3++)//escriu les mes proximes

mnt[n1].la[n3]=s_smp[n3].mag;

mnt[n1].ld2[n3]=s_smp[n3].d2;

mnt[n1].ld[n3]=s_smp[n3].gamma;

mnt[n1].lmn[n3]=s_smp[n3].numero;

mnt[n1].lt[n3]=mnt[n3].mtp;

fprintf(pf,"\t \t \t \t \t \t %3d \t %1d \t %4d \t %4d \t %4d \n",mnt[n1].lmn[n3],mnt[n1].lt[n3],mnt[n1].ld2[n3],mnt[n1].la[n3],(int)mnt[n1].ld[n3]);

//del for

// for fuera

fclose(pf);

void Escriu_matriu(unsigned char ntemp, unsigned char nsamp,int matriu[NMNT][NMNT],FILE* fitxer)//escriu matriu similaritud

fprintf(fitxer,"\nSIMILARITY MATRIX (> Smp, v Tmp):\n");

fprintf(fitxer," ");

for (int jj=0;jj<nsamp;jj++)

fprintf(fitxer," %3d ",jj);

fprintf(fitxer,"\n ");


fprintf(fitxer,"-----");

fprintf(fitxer,"\n");

for (int ii=0;ii<ntemp;ii++)

fprintf(fitxer," %3d|",ii);


fprintf(fitxer," %3d ",matriu[ii][jj]);

Codi_____________ _

_____________________________________________________________________

115



fclose(fitxer);

void SimilarityDegree(unsigned char ntmp, unsigned char nsmp)//Crea Matriu amb graus de similaritud entre minuties,reben numero de minuties del sample i del template

int filtro_smp[NMNT];

int theta1, gamma, distancia,repes;

int i,j,k,p;

int limite1,limite2; //limite1 es la tolerancia en las distancias

//limite2 es la tolerancia en los angulos

//inicio a cero el filtro

for (int x=0; x<NMNT; x++) filtro_smp[x]=0;

// Es guarden els 2 minutiaes i la matriu de similaritat a un fitxer de text (Similarity.txt)


char *filename="Similarity.txt"; // File

pf=fopen(filename,"wt"); // File opened in binary write mode

if (pf==NULL)


clearerr(pf);

exit(1);

// S'AFEGEIX EL DETALL DE LES MINUTIES QUE MANTENEN SIMILARITAT LOCAL

fprintf(pf,"LIST OF PAIRED MINUTIAS WITH CERTAIN LOCAL SIMILARITY (Ref. Template.Neighbour - Ref. Sample.Neighbour):\n");

// se pone a 0 la matriz de similaridad

for (i=0;i<ntmp;i++)

for (j=0;j<nsmp;j++)

smlrty[i][j]=0;

Codi_____________ _

_____________________________________________________________________

116

// IMPORTANT: The reference point to pair minutias is the template minutiae, not the sample minutiae!

for (i=0;i<ntmp;i++) //ntmp es el numero de minucias del Template

for (j=0;j<nsmp;j++) //nsmp es el numero de minuicas del sample

for (int x=0; x<NMNT; x++) filtro_smp[x]=0; //posem a cada pas de template a 0 totes les sample

for(k=0;k<Neighbours; k++) // vecinas en el template

distancia=tmp[i].ld2[k];

theta1=tmp[i].la[k];

gamma=(int)tmp[i].ld[k]; //angle en graus

if (distancia>100) limite1=40; else limite1=10; //Ajusto tolerancies segons distancia

if (distancia>100) limite2=10; else limite2=20;

for(p=0; p<Neighbours; p++) //vecinas en el sample

if((abs(smp[j].ld2[p]-distancia)<limite1)&& (distancia>0)&&(smp[j].ld2[p]>0))

if((abs(smp[j].la[p]-theta1)<limite2)||(abs(smp[j].la[p]+theta1)>180-limite2))

if(abs((int)smp[j].ld[p]-gamma)<limite2)

fprintf(pf," Tmp #%3d.Neighbour #%3d - Smp #%3d.Neighbour #%3d \n",i,tmp[i].lmn[k],j,smp[j].lmn[p]);

filtro_smp[smp[j].lmn[p]]++;

smlrty[i][j]++; break;

//del if de angulo polar

//del if de restar angulos

//del if de comparar distancia

//del for de p vecinos

//del for Neighbours

for (int x1=0; x1<NMNT; x1++) //filtre que he aplicat per descontar les repetides

if ( filtro_smp[x1]>1 )

repes=filtro_smp[x1];

repes--; //Per tenir el valor de les vegades que sens ha repetit l´emparellament

smlrty[i][j]=smlrty[i][j]-repes;

Codi_____________ _

_____________________________________________________________________

117

// del for nsmp

// del for ntmp

Escriu_matriu(ntmp,nsmp,smlrty,pf); // Escriu la matriu de similaritud local

unsigned char CentralFeature(unsigned char ntmp, unsigned char nsmp)//Troba les dues minuties centrals,rep el numero de minuties del sample i template

unsigned char i,j,cf,sd;

unsigned int sc; //similarity counter

unsigned int index;//per troba la mes centrada

unsigned int nocentralfeature[NMNT];//etiqueta per evitar que pugui ser central

for (i=0;i<ntmp;i++) nocentralfeature[i]=0; //inicialitzo vector a 0 poden ser inicialment totes centrals

i=ntmp-1;

do

// Looking for the maximum similarity degree smlrty[i][]

tmp[i].lsd=0;

tmp[i].ltwin=0xff;

j=nsmp-1;

do

if (smlrty[i][j]>tmp[i].lsd)

tmp[i].lsd=smlrty[i][j]; //guardo el grau maxim de similaritud

tmp[i].ltwin=j; //Guardo la parella del template que te aquest grau maxim

while(j--);

// Checking if there is more than 1 minutia with the maximum similarity degree in smlrty[i][]

sc=0;//contador de similaritud per saber el grau maxim de la fila quants cops el te

j=nsmp-1;

do

if (smlrty[i][j]==tmp[i].lsd)

sc++;

while(j--);

Codi_____________ _

_____________________________________________________________________

118

if (sc!=1) //etiqueta per evitar que pugui ser central si es dona condició

//si ha trobat 2 valors maxims a la fila aquesta fila no pot ser central

nocentralfeature[i]=1;

if (tmp[i].lsd<Local_Threshold) // AFEGEIXO UN THRESHOLD DE SIMILARITAT LOCAL >=2

//Ha de tenir un nivell minim de similaritud per ser central

tmp[i].lsd=0;

tmp[i].ltwin=0xff; //IMPORTANT: it is assumed that a minutiae will always have less than 256 minutias

while (i--);

// From here, all sample minutia have lsd and ltwin updated

// Looking for the central feature

sd=0; // similarity degree

cf=0xff; // central feature SE SUPOSA QUE NO HI HAURÀ MAI 255 MINUTIES A UN MINUTIAE!

i=ntmp-1;

do

// OPCIÓ SENSE TENIR EN COMPTE ELS TIPUS

if ((tmp[i].lsd>sd)&&(nocentralfeature[i]==0))

sd=tmp[i].lsd; //nivell de similaritud que te


while (i--);

// Si hi ha 2 o més parelles amb el mateix lsd, em quedo amb la parella central

if (cf!=0xff)// si hi ha minutia central entra

sc=0;

i=ntmp-1;

do

if (tmp[i].lsd==sd)//mira el vector on ja hi ha el grau maxim de cada fila

sc++; // Compto quantes files hi ha amb el màxim lsd

while(i--);

Codi_____________ _

_____________________________________________________________________

119

if (sc>1)//Si hi ha mes de una amb grau maxim agafara la mes central

index=((sc>>1)+1); // índex central: (sc/2)+1, index es enter

sc=0;

i=ntmp-1;//Comença per la mes gran i va baixant

do

if (tmp[i].lsd==sd)//Nivell maxim trobat

sc++;

if (sc==index)//busca fins arriba fins la calculada com a index central

sd=tmp[i].lsd;


while(i--);

// El central feature ha de tenir un nivell de similaritat >= SD_Threshold.

if ((cf!=0xff) && (tmp[cf].lsd<SD_Threshold)) cf=0xff; //Si no te un minim nivell per ser central retorno 0xff

return(cf);

void Global_parameters (unsigned char cf, unsigned char n_minuties,minutia_ *mnt,char *file)//Calculs de distancia i angles de les minuties respecte la central

int dx,dy,i;

int d2, d, theta1, theta;

double gamma;

FILE *gf; // File pointer

gf=fopen(file,"wt"); // File opened in binary write mode

if (gf==NULL)


clearerr(gf);

exit(1);

// Files write processes

fprintf(gf,"GLOBAL ANALYSIS:\n");

fprintf(gf,"\t # \t X \t Y \tAlfa \t T\t # \t t \t d \t Beta\tGamma\n");

Codi_____________ _

_____________________________________________________________________

120

fprintf(gf,"\t-------------------------------------------------------------------------------\n");

fprintf(gf,"\t %3d \t %3d \t %3d \t%4d\t %1d \n",cf,mnt[cf].mpx,mnt[cf].mpy,mnt[cf].mag,mnt[cf].mtp);

i=n_minuties-1;

do

if (i!=cf)

// Template processing

// 1. Distance

dx = (mnt[cf].mpx - mnt[i].mpx);

dy = (mnt[cf].mpy - mnt[i].mpy);

d2 =(dx*dx) + (dy*dy);

d=(int)sqrt(d2);

mnt[i].gd=d;

// 2. Angle (Joining line angle)

theta=mnt[cf].mag; if (theta>270) theta=theta-360;

theta1=mnt[i].mag; if (theta1>270) theta1=theta1-360;

mnt[i].ga=abs(theta1-theta);

// 3. Direction (Field orientation delta)

if ((dy==0)&&(dx==0)) gamma=0; //aixi evito error q provoca atan2

else

gamma=atan2(dy,dx);

gamma=(gamma*360)/(2*pii);

mnt[i].gdir=(int)gamma;

fprintf(gf,"\t \t \t \t \t \t %3d \t %1d \t %4d \t %4d \t %4d \n",i,mnt[i].mtp,d,mnt[i].ga,(int)gamma);

while (i--);

fprintf(gf,"\n");

fclose(gf);

void Global_Similarity(unsigned char ntmp,unsigned char nsmp)//Crea matriu similaritud global amb possibles parelles,rep numero minuties sample i template

int i,j;

int distancia,distancia2,limite1, limite2;

FILE *pf_G;

pf_G=fopen("similarity_global.txt","wt");// File opened in binary write mode

if (pf_G==NULL)

Codi_____________ _

_____________________________________________________________________

121


clearerr(pf_G);

exit(3);

for (i=0;i<ntmp;i++) //poso a 0 tota la matriu de similaritud global on guardare el numero de les

//possibles parelles de totes les minuties

for (j=0;j<nsmp;j++)

smlrtyglobal[i][j]=0;

for(i=0;i<ntmp;i++)

for(j=0;j<nsmp;j++)

distancia=tmp[i].gd;

limite1=20; limite2=20;//limite1 distancia, limite2 angle



if (abs(smp[j].gd-distancia)<limite1)// aquí no tenim el problema que pugui ser ella mateixa pq ja posem condició que si es la central no la tingui en compte

if ((abs(smp[j].ga-(tmp[i].ga))<limite2)||(smp[j].ga+(tmp[i].ga)>180-limite2)) // s´ha afegit 180-limite2 enlloc de 170

if (abs(smp[j].gdir-(tmp[i].gdir))<limite2)

smlrtyglobal[i][j]++;//parelles que te cada minutia

//del if de angulo gamma

//del if de angulo

//del if de distancia

// Global Analysis Checking

// del segon for

//del primer for

//////////////////// File write process////////////////////////////

Codi_____________ _

_____________________________________________________________________

122

Escriu_matriu(ntmp,nsmp,smlrtyglobal,pf_G);// sescriu fitxer similaritud global

void GlobalFeature(unsigned char cf, unsigned char ntmp,unsigned char nsmp)//tenin la minutia central i el numeros de minuties fa els calculs globals,genera

//la matriu de similaritud global i marca les parelles pq matching les escrigui

int i,x,j,n,max;

int distancia,distancia2,limite1, limite2;

////////////////////////Calcul parametres Globals/////////////////////////////////////////////////////

Global_parameters (cf,ntmp,tmp,"Gtemplate.txt");//Calcul parametres globals template i genera G_template

Global_parameters (tmp[cf].ltwin,nsmp,smp,"Gsample.txt");//Calcul parametres globals sample i genera G_sample

/////////////////Generacio Matriu similaritud Global ///////////////////////////

Global_Similarity(ntmp,nsmp);//Generació Matriu similaritud Global

for(x=0;x<ntmp;x++) tmp[x].gfm=0; //poso a 0 la variable gfm que hem diu que es parella

for(x=0;x<nsmp;x++) smp[x].gfm=0; //poso a 0 la variable gfm que hem diu que es parella

//Inicialitzo taula per troba grau maxim de parelles que pot tenir cada minutia

for(int i=0;i<ntmp;i++) grau_max[i]=0;

// Recorro taula per guarda aquest valor maxim de cada minutia template

for(int i=0;i<ntmp;i++)

for(int j=0;j<ntmp;j++)

grau_max[i]=grau_max[i]+smlrtyglobal[i][j];

// Recorro vector per saber el maxim de parelles que pot tenir una mateixa minutia

max=0;

for(int i=0;i<ntmp;i++)

if(max<grau_max[i]) max=grau_max[i]; // la variable max hem diu el maxim de parelles

Codi_____________ _

_____________________________________________________________________

123

//Anire fent les parelles sempre comenssant per les que nomes en tenen una de possible

//Inicialitzo vectors que recordara les parelles ja utilitzades del sample i template

for(i=0;i<nsmp;i++) noparellaSample[i]=0;

for(i=0;i<nsmp;i++) noparellaTemplate[i]=0;

for(i=0;i<max;i++) //nivell de parella que busco

for(j=0;j<ntmp;j++) //recorro vector buscant aquest nivell

if(grau_max[j]==i+1) // Si te el nivell que busco entro

for(x=0;x<nsmp;x++)//recorro columnes al smlrtyglobal

if((smlrtyglobal[j][x]==1)&&(noparellaSample[x]==0)&&(noparellaTemplate[j]==0)) // Busco amb quina fa parella del sample

noparellaSample[x]=1; // la parella seria la template j i sample x i la recordo

noparellaTemplate[j]=1;// Li faig la marca per indicar que ja esta utilitzada com a parella

tmp[j].gfm=1; //indico que fa parella (part del template)

tmp[j].ltwin=x; //li dic quina es la seva parella al sample

smp[tmp[j].ltwin].gfm=1;//indico que fa parella (part de sample)

for(n=0;n<ntmp;n++) //recorro per veure el nou grau max despres d´emparella

if(smlrtyglobal[n][x]==1)

grau_max[n]--; //resto 1 grau que no pot fer pq li han pres la parella

smlrtyglobal[n][x]=0;//poso a 0 la possible parella que ja no pot ser pq li han pres

j=-1; //per torna a comensar tenin en compte el nou grau.Al arribar al for això valdra 0

i=0;//(IMPORTANT) per tornar a comensar ja que potser que fagi baixar el nivell d´una que te 2 a 1 i com ja estic mirant nivell no aquesta la perdi

break; // si troba no cal seguir buscant

//fi funció

Codi_____________ _

_____________________________________________________________________

124

unsigned int Matching(unsigned char cf, unsigned char ntmp)//Genera el fitxer de parelles matching, i retorna el numero de parelles reben la central i numero minuties template

// Matching result calculation

unsigned char i,result=0;


if (ntmp>1)

// File write process

pf=fopen("Matching.txt","wt"); // File opened in binary write mode

if (pf==NULL)


clearerr(pf);

exit(1);

fprintf(pf,"MATCHING (Template):\n");

fprintf(pf,"\t # \t X \t Y \tAlfa \t T\t # \t t \t d \t Beta\tGamma\n");

fprintf(pf,"\t-------------------------------------------------------------------------------\n");

fprintf(pf,"\t %3d \t %3d \t %3d \t%4d\t %1d \n",cf,tmp[cf].mpx,tmp[cf].mpy,tmp[cf].mag,tmp[cf].mtp);

i=ntmp-1;

do

if (tmp[i].gfm!=0)

fprintf(pf,"\t \t \t \t \t \t %3d \t %1d \t %4d \t %4d \t %3d \n",i,tmp[i].mtp,tmp[i].gd,tmp[i].ga,tmp[i].gdir);

while(i--);

fprintf(pf,"MATCHING (Sample):\n");

fprintf(pf,"\t # \t X \t Y \tAlfa \t T\t # \t t \t d \t Beta\tGamma\n");

fprintf(pf,"\t-------------------------------------------------------------------------------\n");

fprintf(pf,"\t %3d \t %3d \t %3d \t%4d\t %1d \n",tmp[cf].ltwin,smp[tmp[cf].ltwin].mpx,smp[tmp[cf].ltwin].mpy,smp[tmp[cf].ltwin].mag,smp[tmp[cf].ltwin].mtp);

i=ntmp-1;

do

if (tmp[i].gfm!=0)

fprintf(pf,"\t \t \t \t \t \t %3d \t %1d \t %4d \t %4d \t %3d \n",tmp[i].ltwin,smp[tmp[i].ltwin].mtp,smp[tmp[i].ltwin].gd,smp[tmp[i].ltwin].ga,smp[tmp[i].ltwin].gdir);

while(i--);

// Matching calculation

i=ntmp-1;

Codi_____________ _

_____________________________________________________________________

125

do

result=result+tmp[i].gfm;

while(i--);

printf ("\nMatching (Matching.txt) performed successfully...\n");

fprintf(pf,"\t \n \n Parelles fetes:%3d parelles\n",result);

return(result);

CIOMatLab *MatLabPtr;

CMaio::CMaio(CIOMatLab *matlab)

MatLab=matlab;

MatLabPtr=matlab;

//---------------------------------------------------------------------------

bool CMaio::Run(char *file)

/******************************************************************************************/

Part III: APPLICATION (EXTRACTION + ENROLMENT/MATCHING)

/******************************************************************************************/

/******************************************************************************************/

// Application inputs

unsigned char nsmp, ntmp; // number of minutia points for both sample and template

unsigned char text[500];

unsigned int dummy_int;

int counter;

int Match;

/******************************************************************************************/

// *************************************************************************************

// STEP 0: SYSTEM INITIALIZATION: Reading of Minutiaes.txt file and minutiae drawing

// *************************************************************************************

char comando [120];

int code;

MatLab->Exec("clear");

Codi_____________ _

_____________________________________________________________________

126


char *filename=file; // File

pf=fopen(filename,"rt"); // File opened in binary read mode

if (pf==NULL)


clearerr(pf);

exit(1);

// File read process

fscanf( pf, "%s", text ); // "TEMPLATE:\n"

fscanf( pf, "%d\n", &counter ); // "%d \n",ntmp;

fscanf( pf, "%s %s %s %s %s",text,text,text,text,text); // "\t # \t X \t Y \tAlfa \t T \n"

fscanf( pf, "%s\n", text ); // "\t------------------------------------------------------------------------------\n"

ntmp=0;

do

fscanf( pf, "%d", &dummy_int); // numero de minucia

fscanf( pf, "%d", &tmp[ntmp].mpx); // coordenada X

fscanf( pf, "%d", &tmp[ntmp].mpy); // coordenada Y

fscanf( pf, "%d", &tmp[ntmp].mag); // angulo

fscanf( pf, "%d", &tmp[ntmp].mtp); // tipo minucia

unsigned int index=Neighbours-1;

do

tmp[ntmp].ld2[index]=0xfffffff;

tmp[ntmp].ld[index]=0xffff;

while (index--);

ntmp++;

while (ntmp!=counter);

fscanf( pf, "%s", text ); // "SAMPLE:\n"

fscanf( pf, "%d", &counter ); // "%d \n",nsmp;

fscanf( pf, "%s %s %s %s %s",text,text,text,text,text); // "\t # \t X \t Y \tAlfa \t T \n"

fscanf( pf, "%s", text ); // "\t------------------------------------------------------------------------------\n"

nsmp=0;

do

fscanf( pf, "%d", &dummy_int); // numero minucia

fscanf( pf, "%d", &smp[nsmp].mpx); // coordenada X

fscanf( pf, "%d", &smp[nsmp].mpy); // coordenada Y

fscanf( pf, "%d", &smp[nsmp].mag); // angulo

fscanf( pf, "%d", &smp[nsmp].mtp); // tipo minucia

unsigned int index=Neighbours-1;

Codi_____________ _

_____________________________________________________________________

127

do

smp[nsmp].ld2[index]=0xfffffff;

smp[nsmp].ld[index]=0xffff;

while (index--);

nsmp++;

while (nsmp!=counter);

fclose(pf);

//****************************************************************************************/

MUESTRA POR PANTALLA

/**************************************************************************************/

//Engine *ep=engOpen(NULL);

strcpy(comando,"analysis(1:1:256,1:1:512)=255;"); //LES 2 IMATGES (tmp-smp) HAN DE SER DEL MATEIX TAMANY

//code=engEvalString(ep,comando);

MatLab->Exec(comando);

strcpy(comando,"figure;imshow(analysis,[0 255]);xlabel('Template vs Sample minutiaes');title('Global Analysis');hold on;");

//strcpy(comando,"figure;axis([0 511 0 255]);hold on;");


sprintf(comando,"plot([%d,%d],[%d,%d],'k-');plot([%d,%d],[%d,%d],'k-');",256,256,0,256,257,257,0,256);

MatLab->Exec(comando); // Drawing the limit line between minutiaes

for (int taux=0;taux<ntmp;taux++)

if (tmp[taux].mtp==0) // Final de cresta

sprintf(comando,"plot(%d,%d,'b+');COLORDEF white;text(%d,%d,'%d');",tmp[taux].mpy,tmp[taux].mpx,tmp[taux].mpy,tmp[taux].mpx,taux);


// Es dibuixen els angles de les minuties

float Ay=(5* sin((pii*tmp[taux].mag)/180))+tmp[taux].mpy;

float Ax=(5* cos((pii*tmp[taux].mag)/180))+tmp[taux].mpx;

sprintf(comando,"plot([%d,%f],[%d,%f],'b-');",tmp[taux].mpy,Ay,tmp[taux].mpx,Ax);


else //(tmp[taux].mtp==1) Bifuració

sprintf(comando,"plot(%d,%d,'r+');COLORDEF white;text(%d,%d,'%d');",tmp[taux].mpy,tmp[taux].mpx,tmp[taux].mpy,tmp[taux].mpx,taux);



float Ay=(5* sin((pii*tmp[taux].mag)/180))+tmp[taux].mpy;

float Ax=(5* cos((pii*tmp[taux].mag)/180))+tmp[taux].mpx;

sprintf(comando,"plot([%d,%f],[%d,%f],'r-');",tmp[taux].mpy,Ay,tmp[taux].mpx,Ax);


Codi_____________ _

_____________________________________________________________________

128

for (int saux=0;saux<nsmp;saux++)

if (smp[saux].mtp==0) // Final de cresta

sprintf(comando,"plot(%d,%d,'b+');COLORDEF white;text(%d,%d,'%d');",(256+smp[saux].mpy),smp[saux].mpx,(256+smp[saux].mpy),smp[saux].mpx,saux);



float Ay=(5* sin((pii*smp[saux].mag)/180))+256+smp[saux].mpy;

float Ax=(5* cos((pii*smp[saux].mag)/180))+smp[saux].mpx;

sprintf(comando,"plot([%d,%f],[%d,%f],'b-');",(256+smp[saux].mpy),Ay,smp[saux].mpx,Ax);


else //(tmp[taux].mtp==1) Bifuració

sprintf(comando,"plot(%d,%d,'r+');COLORDEF white;text(%d,%d,'%d');",(256+smp[saux].mpy),smp[saux].mpx,(256+smp[saux].mpy),smp[saux].mpx,saux);



float Ay=(5* sin((pii*smp[saux].mag)/180))+256+smp[saux].mpy;

float Ax=(5* cos((pii*smp[saux].mag)/180))+smp[saux].mpx;

sprintf(comando,"plot([%d,%f],[%d,%f],'r-');",(256+smp[saux].mpy),Ay,smp[saux].mpx,Ax);


//****************************************************************************************/

FIN DE MUESTRA POR PANTALLA

/**************************************************************************************/

/************************************************************************************/

// *************************************************************************************

// STEP 1: LOCAL ANALYSIS: Neighbourhood analysis and Similarity matrix

// *************************************************************************************

/************************************************************************************/

/*

/* FUNCIONES DE CALCULO DE DISTACIA Y ANGULOS

/*

/************************************************************************************/

filename="Ltemplate.txt"; //File

LocalFeatureDistance(tmp,ntmp,filename);

filename="Lsample.txt"; //File

LocalFeatureDistance(smp,nsmp,filename);

SimilarityDegree(ntmp,nsmp);

Codi_____________ _

_____________________________________________________________________

129

/****************************************************************************************/

//FIN DE MUESTRA POR PANTALLA

// EL ANALISIS LOCAL //

/**************************************************************************************/

// *************************************************************************************

// STEP 2: GLOBAL ANALYSIS: Neighbourhood analysis from paired minutiae

// *************************************************************************************

unsigned char n=CentralFeature(ntmp,nsmp);

if (n!=0xff)

// Dibuix de les linees unint les minuties tmp-smp emparellades en color verd

// Es sobreescriu de color magenta la parella CentralFeature

sprintf(comando,"plot([%d,%d],[%d,%d],'m-');",tmp[n].mpy,256+smp[tmp[n].ltwin].mpy,tmp[n].mpx,smp[tmp[n].ltwin].mpx);


GlobalFeature(n,ntmp,nsmp);

unsigned int Match=Matching(n,ntmp);

if(Match>10)fprintf(pf,"\t \n \n L´empremta dactilar es la mateixa perquè té mes de 10 parelles");//Si tinc 11 parelles la dono per bona

else fprintf(pf,"\t \n \n L´empremta dactilar no es la mateixa");

fclose(pf);

// COMPROVACIÓ DE SISTEMA INJECTIU

unsigned char InjectMatch=0;

unsigned char j=nsmp-1;

do

InjectMatch=InjectMatch+smp[j].gfm;

while(j--);

// Dibuix de les linees unint les minuties del matching en color vermell

for (int i=0;i<ntmp;i++)

if (tmp[i].gfm!=0)

sprintf(comando,"plot([%d,%d],[%d,%d],'r-');",tmp[n].mpy,tmp[i].mpy,tmp[n].mpx,tmp[i].mpx);


sprintf(comando,"plot([%d,%d],[%d,%d],'r-');",256+smp[tmp[n].ltwin].mpy,256+smp[tmp[i].ltwin].mpy,smp[tmp[n].ltwin].mpx,smp[tmp[i].ltwin].mpx);


Codi_____________ _

_____________________________________________________________________

130

// Es dibuixa també les minuties tmp-smp emparellades de color blau enlloc de verd

sprintf(comando,"plot([%d,%d],[%d,%d],'b-');",tmp[i].mpy,256+smp[tmp[i].ltwin].mpy,tmp[i].mpx,smp[tmp[i].ltwin].mpx);


//Sleep(10000);

else

n=0;

pf=fopen("Matching.txt","wt"); // File opened in binary write mode

if (pf==NULL)


clearerr(pf);

exit(1);

fprintf(pf,"\t \n \n No s´ha trobat la minutia central o aquesta no té un nivell de similaritud suficient ");

fclose(pf);

return true;

optimització d' un algorisme per la identificació d...

Documents