231 lines
No EOL
16 KiB
Markdown
231 lines
No EOL
16 KiB
Markdown
Uno dei primi tratti biometrici utilizzati per identificare un soggetto.
|
||
|
||
Problemi: rotazione del dito, secchezza della pelle.
|
||
|
||
Un'impronta digitale di solito appare come una serie di linee scure che rappresentano la parte alta e appuntita della pelle della cresta di attrito, mentre le valli tra queste creste appaiono come uno spazio bianco e sono la parte bassa e poco profonda della pelle della cresta di attrito.
|
||
|
||
Le impronte digitali sono tratti randotipici.
|
||
|
||
La prima classificazione di impronte digitali fu propostada Purkinje nel 1823, basata su 9 categorie:![[Pasted image 20241121085417.png]]
|
||
Non andava ad analizzare le minuzie, però può essere usato come meccanismo per riconoscere velocemente che due impronte sono **molto** diverse tra loro.
|
||
|
||
Il primo approccio scientifico è dato da Galton (antropologo, il quale ha dato una prima classificazione delle impronte che definiamo come macro singolarità (archi, loop e spirali) in termine del numero di "delta": whorl (2 delta), loop (1 delta), arch (no delta)
|
||
![[Pasted image 20241121090018.png]]
|
||
|
||
e successivamente ha introdotto il concetto di minuzie che definiamo come micro similarità.
|
||
![[Pasted image 20241121090256.png]]
|
||
|
||
Henry invece ha proposto una classificazione con la frequenza per ogni classe:
|
||
- Spirali: 28%
|
||
- Archi: 6.6%
|
||
- Left loop: 33.8%
|
||
- Right loop: 31.7%
|
||
|
||
#### AFIS
|
||
Il primo ente a collezionare impronte è stata l'FBI.
|
||
...
|
||
|
||
La formazione delle impronte è già completata nel settimo mese di sviluppo fetale e la configurazione delle creste su ciascun dito è costante durante l'intero ciclo di vita.
|
||
|
||
aggiungi qualcosa sull'unicità magari
|
||
|
||
#### Acquisizione
|
||
Può essere:
|
||
- **Offline:** consiste in due step, la prima è la creazione dell'impronta su carta tramite inchiostro ad esempio, con la successiva digitalizzazione dell'impronta stampata. Rientrano in questa categoria le "impronte latenti": quelle che lasciamo involontariamente sulle varie superfici a causa della natura oleosa della pelle
|
||
- **Online:** viene usato un sensore di cattura che digitalizza direttamente l'impronta (*live-scan*).
|
||
|
||
Parametri che caratterizzano un'impronta digitalizzata:
|
||
- risoluzione (in DPI): il minimo necessario per estrarre le minuzie è 200-300 DPI. L'FBI ha 500 DPI come requisito minimo
|
||
- area di acquisizione: almeno 1x1 pollice (secondo le specifiche FBI)
|
||
- la profondità in bit per codificare ogni pixel
|
||
- contrasto: un'immagine più contrastata (sharp) contiene più dettagli
|
||
- distorsione geometrica introdotta dal sensore
|
||
|
||
#### Tipi di scanner
|
||
- **Scanner ottico:** poco costoso, robusto alla variazione di clima e con buona risoluzione. Ma deve essere sufficientemente grande e va pulito bene dopo ogni utilizzo
|
||
- **Scanner capacitivo:** migliore risoluzione dell'impronta e dimensioni ridotte. Svantaggi: la durabilità del sensore in condizioni subottimali non è stata provata. Siccome è più piccolo bisogna accertarsi che le acquisizioni vengano fatte bene
|
||
- **Scanner piezoelettrico:** misura cambiamenti in pressione, accelerazione, deformazione e forza convertendoli in una carica elettrica
|
||
- **Scanner termico:** non può essere ingannato da impronte artificiali perché riconosce pulsazione, temperatura, pori e cambiamento del colore della pelle tramite pressione. Svantaggio: quando un dito viene posizionato sul sensore, inizialmente c'è un grosso delta termico, ma in un tempo molto breve (meno di 1/10 di secondo) l'immagine sparisce perché il sensore raggiunge la temperatura del dito
|
||
|
||
|
||
#### Pores pattern
|
||
Aumentando ancora la risoluzione, andando oltre alle minuzie, riusciamo a catturare i pattern dei pori della pelle. Servono però scanner dell'ordine dei 1000 DPI, per cui non è praticabile nella maggior parte dei contesti applicativi.
|
||
|
||
#### Tecniche di matching
|
||
Gli esperti consigliano di considerare 4 aspetti:
|
||
- valutare prima un pattern globale e scartare impronte con pattern diversi
|
||
- valutare la qualità (valutare le minuzie)
|
||
- valutare la quantità (numero minimo di minuzie che matchano)
|
||
- corrispondenza di dettagli che devono essere interrelati: una coppia di minuzie in due acquisizioni diverse deve avere la stessa distanza
|
||
|
||
Approcci metodologici:
|
||
- **Basato su correlazione:** le due immagini vengono sovrapposte e viene fatto un calcolo della correlazione dei vari pixel (iterando sui possibili allineamenti). Alto costo computazionale ed è sensibile a trasformazioni non lineari
|
||
- **Basato sulle ridge features:** utilizzato per immagini di bassa qualità, non è possibile quindi estrarre minuzie. Utilizza feature facili da estrarre come l'orientamento, la frequenza e la forma dei vari ridge. Poco discriminativo
|
||
- **Basato sulle minuzie:** vengono estratte le minuzie e vengono salvate come punti in uno spazio a due dimensioni. Il metodo cerca un possibile allineamento che massimizzi il numero di match di minuzie.
|
||
|
||
Problemi nel matching:
|
||
![[Pasted image 20241121104307.png]]
|
||
- Le distorsioni non lineari sono causate da rotazioni del dito o livelli di pressione diversi (se schiaccio di più o di meno)
|
||
- Overlap scarso tra le due acquisizioni: rilevante soprattutto in sensori con un'ara di acquisizione ridotta.
|
||
|
||
- Too much movement and/or distortion
|
||
- Little overlap between the template and the imprint in input. Particularly relevant for sensors with small acquisition area
|
||
- Non-linear distortion of the skin
|
||
- The acquisition of a fingerprint entails mapping a three-dimensional shape onto the two-dimensional surface of the sensor. In this way a non-linear distortions is produced, due to the elasticity of the skin, which may vary among subsequent acquisitions of the same footprint
|
||
- Variable pressure and skin conditions
|
||
- Uneaven pressure, fingerprint too dry or too wet, dirt on the sensor, moisture in the air...
|
||
- Errors in feature extraction algorithms
|
||
|
||
|
||
![[Pasted image 20241127134548.png]]
|
||
|
||
### Segmentation
|
||
The term indicates the separation between the foreground fingerprint from the background which is isotropic (i.e. rotating the white background, the image stays the same)
|
||
|
||
Anisotropy (*anisotropia in italiano*): the property of being directionally dependent (as opposed to isotropy).
|
||
|
||
Characteristic of the fingerprints are directionally dependent, we can use this to separate the fingerprint from the background:
|
||
- presence of a peak in a histogram of the local orientations
|
||
- the orientation of the ridge line is estimated at each pixel and a histogram is calculated for each block 16×16. The presence of a significant peak denotes an oriented pattern, while a "flat" histogram is characteristic of isotropic signal
|
||
- variance of the gray levels in the direction perpendicular to the gradient
|
||
- in noisy regions the pattern does not depend on the direction, while the fingerprint area is characterized by a very high variance in the direction orthogonal to the ridge orientation and very low along the ridge
|
||
- magnitude of the gradient
|
||
- because the area of the fingerprint is rich in edge due to the alternation of ridge and valley, the gradient is high in the foreground and lower elsewhere
|
||
- combination of several characteristics
|
||
- for each pixel we calculate some characteristics (consistency of the gradient, and average and variance of the intensity), and the allocation to foreground / background is operated by a classifier
|
||
|
||
Once a fingerprint has been segmentated we can start extracting **macro-features** such as:
|
||
- **ridge-line flow:** described by a structure called **directional map** (or directional image) which is a discrete matrix whose elements denote the orientation of the tangent to the ridge lines.
|
||
- analogously, the ridge line density can be synthesized by using a density map.
|
||
![[Pasted image 20241127135348.png]]
|
||
|
||
##### Directional map
|
||
~~The local orientation of the ridge line in the position [i, j] is defined as the angle $\theta(i,j)$ formed by considering the horizontal line at that point, and a point on the ridge line sufficiently closer to [i, j].~~
|
||
|
||
Definizione: matrice in cui la cella [i, j] rappresenta l'angolo che la tangente alla ridge line forma con l'asse orizzontale.
|
||
![[Pasted image 20241127224325.png]]
|
||
- most approaches use a grid measure (instead of measuring at each point)
|
||
- the directional image D is a matrix in which each element denotes the average orientation of the ridge (of the tangent to the ridge) in a neighborhood of $[x_{i}, y_{i}]$
|
||
|
||
- the simplest approach for extraction and natural orientation location is based on the computation of the gradient of the image
|
||
- the estimation of a single orientation is too sensitive to noise, however, an average of gradients cannot be done due to circularity of corners
|
||
- the concept of average orientation is not always well defined: what is the average of two orthogonal orientations of 0 and 90 deg? We have 4 possible different averages!
|
||
- some solutions imply doubling the angles and considering separately the averages along the two axes
|
||
|
||
##### Frequency map
|
||
the frequency of the local ridge line $f_{xy}$ at the point $[x, y]$ is defined as the number of ridges per unit length along a hypothetical segment centered at $[x, y]$ and orthogonal to the orientation of the local ridge.
|
||
- by estimating the frequency in discrete locations arranged in a grid, we can compute a frequency image F:![[Pasted image 20241127225853.png]]
|
||
- a possible approach is to count the average number of pixels between consecutive peaks of gray levels along the direction orthogonal to the local orientation of the ridge line
|
||
|
||
##### Singularities
|
||
Most of approaches are based on directional map.
|
||
A practical and elegant approach is to use the Poincaré index
|
||
- let G be a vector field (campo vettoriale). G is the field associated with the image of the orientations of the fingerprint image D ($[i, j]$ is the position of the element $\theta_{ij}$)
|
||
- let C be a curve immersed in G, is a closed path defined as the ordered sequence of elements of D, such that $[i, j]$ are internal points.
|
||
- the Pointcaré index $P_{G,C}$ is defined as the total rotation of the vectors of G along C
|
||
- $P_{G,C}(i, j)$ is computed by performing the algebric sum of the differences of orientation between adjacent elements in C
|
||
![[Pasted image 20241127230718.png]]
|
||
![[Pasted image 20241127233105.png]]
|
||
|
||
### Minutiae extraction
|
||
Many approaches extract minutiae and perform matching based on them or in combination with them.
|
||
In general, minutiae extraction entails:
|
||
- **Binarization:** converting a graylevel image into a binary image
|
||
- **Thinning:** the binary image undergoes a thinning step that reduces the thinckness of the ridge lines to 1 pixels
|
||
- **Location:** a scan of the image locates pixels corresponding to the minutiae
|
||
![[Pasted image 20241127140214.png]]
|
||
|
||
To locate minutiae we can analyze the crossing number $$cn(p)=\frac{1}{2}\sum_{i=1...8}|val(p_{i\ mod\ 8})-val(p_{i-1})|$$
|
||
- p0, p1, ..., p7 are the pixels in the neighborhood for p and $val(p) \in \{0, 1\}$ is the value of pixel p
|
||
- a pixel p with $val(p) = 1$:
|
||
- is an internal point of a ridge line if $cn(p)=2$
|
||
- corresponds to a termination if $cn(p)=1$
|
||
- corresponds to a bifurcation if $cn(p)=3$
|
||
- belongs to a more complex minutia if $cn(p) > 3$.
|
||
![[Pasted image 20241127140836.png]]
|
||
- cn(p) = 2: internal point
|
||
- cn(p)=1: termination
|
||
- cn(p)=3: bifurcation
|
||
- belongs to a more complex minutia if cn(p) > 3.
|
||
|
||
a feature often used is the **ridge count**: number of ridges intersected by the segment between two points (often the points are chosen as relevant one, e.g. core and delta).
|
||
|
||
### Hybrid approach
|
||
Hybrid method based on comparison of minutiae texture: combines the representation of fingerprints based on minutiae with the representation based on Gabor filter that uses local texture information
|
||
|
||
![[Pasted image 20241127141648.png]]
|
||
|
||
##### Image alignment
|
||
- extraction of minutiae from both the input and from the template to match
|
||
- the two sets of minutiae are compared through an algorithm of point matching that preliminary selects a pair of reference minutiae and then determines the number of matching of minutiae pairs pairs using the remaining set of points
|
||
- the reference pair that produces the maximum number of matching pairs, determines the best alignment
|
||
- once minutiae have been aligned, also rotation and translation are known
|
||
- rotation parameter is the average of rotation of all the individual pairs of corresponding minutiae
|
||
- translation parameters are calculable using spatial coordinates of the pair of reference minutiae which produced the best alignment
|
||
|
||
##### Masking and tessellation
|
||
After masking the background, the images are normalized by building on them a grid that divides them into series of non-overlapping windows of the same size. Each window is normalized with reference to a constant mean and variance. Optimal size for 300 DPI is 30x30, as 30 pixel is the average distance inter-solco.
|
||
![[Pasted image 20241128000431.png]]
|
||
|
||
##### Feature extraction
|
||
In order to perform the feature extraction from the cells resulting from the tessellation, a group of 8 Gabor filters is used, all with the same frequency but variable orientation. Such filtering produces 8 sorted images for each cell.![[Pasted image 20241128000533.png]]
|
||
|
||
We consider the mean absolute deviation (average of absolute deviation of the value, from the value of a central point) of the intensity in each filtered cell as a feature, so we have 8 of them per cell (remember 8 gabor filters), they are concatenated into a characteristic vector.
|
||
The characteristic values relating to masked regions are not used and marked as missing in the vector.
|
||
|
||
**Matching:** sum of the squared differences between corresponding characteristic vectors, after discarding missing values.
|
||
The similarity score is combined with that obtained with the comparison of minutiae, using the rule of sum of the combinations.
|
||
Recognition is successful if the score is below a threshold.
|
||
|
||
### Fingerphotos
|
||
**Pros:**
|
||
- no special sensor required
|
||
- contactless (more hygienic)
|
||
**Cons:**
|
||
- subject to common problems in image processing: illumination, position with respect to the camera, blurriness, etc.
|
||
- some pre-processing steps require more sophisticated approaches.
|
||
|
||
#### An example of pre-processing
|
||
##### Image rotation
|
||
using PCA we detect the largest connected component and compute its orientation, so we can rotate the image and have the finger straight.
|
||
##### Background removal
|
||
- image is converted in grayscale
|
||
- canny edge to detect contours
|
||
- openCV findContours() to find the larger area component
|
||
- mask the rest (mask with white corresponding to the larger contour, all the rest is black)
|
||
- gaussian blur of the mask
|
||
- fusion with the original image
|
||
##### Finger cropping
|
||
- openCV extract_finger() + .rectangle() to crop the finger
|
||
##### ROI cropping
|
||
- based on height and width of the finger, crop the fingertip
|
||
|
||
##### ROI enhancement
|
||
- normalization of the image
|
||
- openCV .createCLAHE()
|
||
- openCV .gaussianBlur()
|
||
|
||
##### Ridge extraction
|
||
- adaptive thresholding
|
||
- morphological operators
|
||
- thinning
|
||
|
||
|
||
### Fake fingerprints
|
||
It's not difficult. It's possible to use materials such as gelatine, silicone or latex.
|
||
|
||
A safety measure is **liveness detection**, possible approaches:
|
||
- measure pulse and temperature
|
||
- bloodstream and its pulsation can be detected with a careful measurement of the light reflected or transmitted through the finger
|
||
- live-scan scanners with FTIR (Frustrated Total Internal Reflection) technology use a mechanism of differential acquisition for the ridges and furrows of fingerprints
|
||
- the high resolution scan of fingerprints reveals details characteristic of the structure of the pores, difficult to imitate in an artificial finger
|
||
- the characteristic color of the skin changes due to the pressure when it is pressed on the scanning surface
|
||
- the (electric) potential difference between two specific points of the finger
|
||
- electric impedance is useful to check the vitality of the finger
|
||
- a finger sweats
|
||
|
||
|
||
### AFIS or human
|
||
The problem of digital fingerprint recognition is not really fully solved! A human expert in manual techniques is still better in comparing fingerprints than an automated system.
|
||
|
||
However, automated systems are fast, reliable, consistent and low-cost. |