Digitalisering van vingerafdrukken (Genomineerde 2009)


Leerlingen: Rik Harink
Docent: Mieke Heuker of Hoek
School: Carmel College Salland, Salland

Inleiding

Vingerafdrukken worden tegenwoordig niet alleen meer gebruikt om criminelen op te sporen. Ook bij het inloggen op je computer of om een kantoorgebouw binnen te gaan kan een vingerafdruk de manier zijn om je te identificeren.

Vraagstelling

Hoe wordt een lijnenpatroon op je vinger omgezet naar een formaat waar een computer iets mee kan? Hoe vindt een computer de kenmerken die een vingerafdruk uniek maken? Op welke manier vergelijkt software vingerafdrukken met elkaar?

Hypothese

Het is mogelijk vingerafdrukken te digitaliseren met speciaal daarvoor ontworpen vingerafdrukscanners.

Theorie

Basiseigenschappen van vingerafdrukken: Een vingerafdruk kun je zien als een patroon van bergen en valleien. De bergen worden gevormd door papillairlijnen. Vingerafdrukken zijn uniek. In de hele wereld zijn er geen twee dezelfde vingerafdrukken te vinden. Zelfs eeneiige tweelingen hebben niet dezelfde vingerafdrukken. Daarnaast zijn vingerafdrukken door de manier waarop de huid gebouwd is onveranderlijk, beschadigingen van de opperhuid hebben geen invloed op de vorm van de vingerafdruk. Het feit dat vingerafdrukken uniek en onveranderlijk zijn maakt ze tot een ideale identificatie methode.


Figuur 1: Vingerafdruk.

De digitalisering van de vingerafdruk: Er bestaan verschillende methodes om van je vingerafdruk een digitale afbeelding te maken. Twee van de meest gebruikte methodes zijn optische scanners en capaciteitsscanners. Het analyseren van de vingerafdruk: Typica: Zodra de computer een digitale afbeelding van de vingerafdruk heeft begint het echte werk. Voor het vergelijken van vingerafdrukken gebruik je typica. Typica zijn bepaalde punten in een vingerafdruk die bijzonder zijn. De vier belangrijkste typica zijn lijnunits, lijnfragmenten, beginnende/stoppende papillairlijnen en splitsende papillairlijnen (bifurcaties). Door deze typica kunnen vingerafdrukken vergeleken worden. Ieder mens heeft unieke vingerafdrukken, daardoor heeft elke vingerafdruk zijn eigen unieke patroon van typica. Door de plaats en draaihoek van de typica van één vingerafdruk te vergelijken met die van een andere vingerafdruk, kun je er achter komen of het om dezelfde persoon gaat. Van dit principe wordt ook gebruik gemaakt bij het opslaan van vingerafdrukken op de computer. De computer vindt de typica en onthoudt de x coördinaat, de y coördinaat en de hoek die de typica met de x-as maakt. Maar hoe vindt een computer deze gegevens? Voordat de computer deze gegevens kan vinden moet er eerst een heleboel gebeuren. De digitale afdruk van de vinger moet eerst nog een hele reeks bewerkingen ondergaan. Dit wordt ook wel pre-processing, voorbewerken, genoemd.


Figuur 2: Verschillende soorten typica.

Materiaal en Methode

Het pre-processing Stap 1: Het omzetten van de afbeelding naar zwart-wit Als eerste wordt de afbeelding omgezet naar puur zwart en wit, dit wordt ook wel binarization genoemd. Ik heb hier gekozen voor binarization met behulp van de standaarddeviatie. Het oorspronkelijke plaatje is een plaatje dat bestaat uit grijswaarden. Dit houdt in dat elke pixel een kleurwaarde kan hebben tussen de 0 en de 255. Door het gemiddelde en de standaardafwijking van alle grijswaarden samen uit te rekenen kan per pixel bepaald worden of die zwart of wit moet worden. Stap 2: Thinning Om de typica goed te kunnen vinden moeten de lijnen van de vingerafdruk (de papillairlijnen) in de afbeelding niet dikker zijn dan één pixel. Om dit voor elkaar te krijgen wordt er gebruik gemaakt van thinning algoritmes. Na het toepassen van een dergelijk algoritme blijft er een afbeelding over waarvan de lijnen nog maar één pixel breed zijn. Ik gebruik het Zhang-Suen thinning algoritme. Dit algoritme is snel, redelijk effectief en makkelijk te begrijpen. Thinning algoritmes moeten zich altijd aan drie voorwaarden houden: 1. Originele eindpunten blijven zoveel mogelijk behouden 2. De pixels blijven altijd verbonden 3. De originele vorm/structuur blijft zoveel mogelijk behouden Deze voorwaarden zorgen ervoor dat de afbeelding zo veel mogelijk zijn originele vorm behoudt maar dan met lijnen van maar één pixel breed.

Het Zhang-Suen thinning algoritme: Het Zhang-Suen thinning algoritme is gebaseerd op de Moore neighbourhood. De Moore neighbourhood bestaat uit een raster van drie bij drie pixels. Het vakje in het midden (P in de onderstaande afbeelding) is de pixel die je op dat moment bekijkt en de andere vakjes zijn de omringende buren van die pixel (P2 tot en met P9). Voor elke zwarte pixel van de vingerafdruk worden nu een aantal zaken bekeken om te bepalen of deze zwart moet blijven of wit moet worden. Ten eerste worden de vakjes P2 tot en met P9 gevuld aan de hand van hun kleur. Is de pixel zwart dan is de waarde van het vakje 1 en is de pixel wit dan is de waarde 0.


Figuur 3:De Moore neigbourhood


Figuur 4: Een ingevulde Moore neighbourhood.

Nadat het raster is gevuld wordt de bijbehorende N waarde uitgerekend. De N waarde is als volgt gedefinieerd: N(P) = aantal buren met kleurwaarde 1. Na het berekenen van de N waarde wordt de S waarde uitgerekend en deze heeft de volgende definitie: S(P) = het aantal transities van 0 naar 1 als men het raster doorgaat in de volgorde P2,P3,P4,P5,P6,P7,P8,P9,P2.

Van pixel P wordt nu het volgende bekeken: 1. Is S(P) gelijk aan 1 2. Is 2 <= N(p) <= 6 3. Is P2 * P4 * P6 gelijk aan 0 4. Is P4 * P6 * P8 gelijk aan 0 Deze vier regels worden de eerste iteratie genoemd. Als een pixel aan alle vier de voorwaardes voldoet wordt hij gemarkeerd voor verwijdering. Hij wordt echter nog niet echt wit gemaakt, dit gebeurt pas als alle pixels aan de eerste iteratie onderworpen zijn. Na de eerste iteratie wordt het plaatje opnieuw gecontroleerd maar nu volgens de regels van de tweede iteratie. Deze zijn als volgt: 1. Is S(P) gelijk aan 1 2. Is 2<=N(P)<=6 3. Is P2*P4*P8 gelijk aan 0 4. Is P2*P6*P8 gelijk aan 0 Alleen de laatste twee regels van de tweede iteratie verschillen van de eerste iteratie. Deze tweede iteratie wordt ook weer toegepast op alle pixels van de vingerafdruk. Als de pixel wederom aan alle vier de voorwaarden van de tweede iteratie voldoet wordt hij gemarkeerd als verwijderbaar en deze gemarkeerde pixels worden aan het eind van de rit wederom verwijderd. Deze vier stappen worden herhaald totdat er niets meer te markeren valt en als dit het geval is dan is het plaatje “ge-thinned”.

Resultaten


Figuur 5: Voor thinning. Bron: fingerprintcreator software


Figuur 6: Na thinning Bron: afbeelding verkregen door zelf geschreven programma

Typica extractie Na alle voorbewerking kunnen nu de typica uit de afbeelding worden gehaald. Een makkelijke, veel gebruikte techniek hiervoor is de Crossing Numbers techniek. Voor deze techniek wordt wederom gebruik gemaakt van de Moore neighbourhood. De Moore neighbourhood wordt weer gevuld volgens het principe Zwart=1 Wit=0 en dan wordt CN(P) uitgerekend waarbij CN(P) = aantal buren met kleurwaarde 1 na thinning. Bij verschillende soorten typica horen verschillende waardes van CN(P).

Zo is bij een beginnende/stoppende papillairlijn CN(P)=1


En bij een bifurcatie is CN(P)=3


Overige typica’s zijn vaak combinaties van deze twee voorgaande en deze worden dus op dezelfde manier gevonden als hierboven.

Richting van de typica De richting van de typica wordt bepaald door de hoek die hij maakt met de X-as. Deze hoek wordt bepaald door de helling van de typica te berekenen en met behulp van deze helling kun je de hoek vinden. Deze hoek vormt samen met de coördinaten van de typica een triplet en alle tripletten van de vingerafdruk samen vormen de template die gebruikt kan worden voor de verificatie of de identificatie.

Verificatie en identificatie Het matchen van de vingerafdruk houdt in dat de invoer template wordt vergeleken met een template uit de database. De templates hoeven echter niet 100% hetzelfde te zijn. Dit is zo omdat tijdens het hele proces verschillen kunnen ontstaan door de kwaliteit van de scan, de manier waarop de vinger is gescand etc. Daarom maken de match algoritmes gebruik van een drempelwaarde. Voor het matchen worden de coördinaten en de hoeken van de typica van de vingerafdruk vergeleken met de template. Als de verschillen in coördinaten bij alle typica kleiner zijn dan een vooraf bepaalde drempelwaarde dan is er een match. Matchen ook alle hoeken van de typica dan is de vingerafdruk geïdentificeerd of geverifieerd.

Conclusie

Vingerafdrukken kunnen worden gedigitaliseerd met behulp van speciaal daarvoor ontworpen vingerafdrukscanners. Een vingerafdruk bevat verschillende soorten typica, de plaats van deze typica en de hoek die ze maken met de x-as van het plaatje zijn bepalend of de vingerafdruk wel of niet gelijk is aan een vingerafdruk uit de database. Voordat een template van een vingerafdruk gemaakt kan worden moet de afdruk eerst een reeks bewerkingen ondergaan, het pre-processing. Eerst wordt van een afbeelding met grijswaarden een pure zwart wit afbeelding gemaakt. Na de binarization vindt thinning plaats. Alle lijnen in de vingerafdruk mogen nog maar 1 pixel breed zijn. Na het thinning worden typica gezocht door middel van de Crossing Numbers techniek. Ook wordt de hoek van de typica bepaald. Alle coördinaten en hoeken van de typica samen vormen de template en deze wordt opgeslagen in de database. Verificatie is het één op één vergelijken van templates en bij identificatie vergelijk je één template met een hele database. Omdat identificatie heel lang kan duren, maakt men gebruik van classificatie om het proces wat te versnellen.

Discussie

Na een zeer voorspoedige start met de image binarization en de thinning liep ik vast bij het uiteindelijke vinden van de typica. Na het bestuderen van mijn code en de verkregen afbeeldingen uit die code bleek dat de thinning niet helemaal optimaal was. Op sommige delen bleef de lijn 2 pixels dik. Als ik een echte vingerafdruk gebruik (gescanned met een vingerafdrukscanner), bijvoorbeeld mijn eigen vingerafdruk, bleken de poriën in de huid het resultaat te beïnvloeden. De poriën vormen uiteindelijk grote gaten in de afbeelding na de thinning. Dit ligt aan onvoldoende voorbewerken. Eigenlijk moet de afbeelding eerst vervaagd worden met een zogenoemde gaussian blur. Bij het programmeren was het telkens kiezen tussen of heel simpele code die redelijk maar niet voldoende werkt of voor mij te hoog gegrepen wiskundige formules uit artikelen van hoogleraren of afstudeerscripties. De ene was te moeilijk maar werkt misschien wel heel goed en de ander was goed te begrijpen maar werkt niet voldoende. Ik heb uiteindelijk voor het laatste gekozen. Mijn code maakt een redelijk goed zwart wit plaatje met relatief weinig ruis. De thinning werkt goed behalve in een aantal bochten van de afbeelding. De typica extractie vindt wel alle typica maar vindt daarnaast nog een heleboel andere punten die geen typica zijn. Met meer tijd en verdere verdieping in ingewikkelde algoritmes zou ik een hoop kunnen verbeteren in mijn programma. De volgende dingen zou ik dan ook als verbeterpunten voor een eventueel volgend ontwerp willen aandragen: 1. Het verbeteren van het algoritme voor binarization. 2. Opsporing en verwijdering van poriën in de afbeelding. 3. Goede voorbewerkingen die de kwaliteit van de afbeelding verhogen, denk aan de gaussian blur. 4. Beter werkend thinning algoritme gebruiken dat niet op bepaalde plaatsen alsnog dubbele pixels overlaat. 5. Het filteren van onjuiste typica en een beter systeem voor het herkennen van typica in het algemeen implementeren.