Implementation and Visualization of Fingerprint Minutiae Matching with Mathematica 6

Shortcomings and Options for Improving Accuracy

Sam Daniel

Scientific Software Associates

Abstract

With its dynamic elements and associated interactive graphics, Mathematica 6 offers an important capability to control, observe, understand, and evaluate the dynamic behavior of fingerprint matching algorithms.  Using the Manipulate function, the classical Minutiae Matcher (MM) can now be exercised visually, imparting thus an intuitive understanding of its constituent Registration and Matching stages.  Detected  minutiae from a search print are superimposed over those of a file print, rotated at fixed angular increments over a prescribed azimuth range, registered by identifying quantized mutual subsets of translational similarity, matched by effecting a derived translation at full pixel resolution and producing a score based on a reasonable Euclidean measure.  Through controls provided with the interactive graphics, one can choose to observe the state of MM, at either the Registration or the Matching stage, for a given azimuth angle.  Alternatively, the behavior of each of the stages may be examined dynamically over the specified azimuth scan range. 

While MM may be quite suitable for identity verification where minutiae detection accuracy is more than adequate, it is less dependable in situations where image quality and relative distortion between search and file prints tend to diminish the reliability of Euclidean measures.  In the latter case, some of the consequent loss in accuracy could be recovered with probabilistic and transform based methods.  The likelihood of a correct match could be increased by weighting individual minutiae matching measures according to the image quality maps of the two fingerprints being compared.  The reliability of the match could also be enhanced by taking into account the ridge structure among corresponding pairs of matched minutiae on the two fingerprints.  The latter method, which has been shown to significantly improve upon MM matching performance in practice [1,2], is explained in some detail.

Overview

What is Minutiae Matching (MM) ?


Minutiae Data


How is MM Mechanized ?


MM Operational Visualization Using Mathematica 6.0


MM Shortcomings and Techniques for Improving Performance


Cross Section Correlation Technique


Prospects for Mathematica 6.0

Define $Path

disk=ToString[Input["Name Source Disk:"]];
sourceDir="/Volumes/"<>disk<>"/Daniel-WTC06";
configDir=sourceDir<>"/Config";
$Path=Union[Join[$Path,{sourceDir,configDir}]];
<<Config.m

Get Ready

go;

What is Minutiae Matching (MM) ?

Given a search print and a target file print from a background database, MM produces a score that represents a similarity measure between the two sets of minutiae.   More specifically, this is a Euclidean measure between qualified subsets of corresponding matched minutiae identified after appropriate orientation and superimposition of the search minutiae over those of the file print.

{id0,id1}={"b101l9i_10","b101t9i_10"};

{gp0,gp1}=graphicsPrint/@{id0,id1};
{gm0,gm1}=Map[graphicsMinutiae@@#&,{{id0,imageFormat,Red,0.003},{id1,imageFormat,Blue,0.003}}];
Grid[{{Show@{gp0,gm0},Show@{gp1,gm1}}}]

Minutiae Data

Minutiae data are typically generated automatically for prints of moderate and good quality — prints that dominate background databases.  However, there are prints, particularly crime prints or latents, which require human intervention.  Highly skilled Latent Examiners are often called upon to manually mark and extract minutiae data from such prints.  Using Mathematica 6, it is a simple matter to do so interactively and with minimal training.

Function designateMinutiae[id]

designateMinutiae[id_]:=designateMinutiae[id,imageFormat,Red,0.003]
designateMinutiae[id_,imageFormat_,color_,thk_]:=
DynamicModule[{g,r,c,pts={},h},
g=graphicsPrint[id,imageFormat];
{r,c}=Dimensions[g[[1,1]]];
Dynamic[Grid[{
{EventHandler[
mins=extractMinutiae[pts];
h=minGraphics[pts,color,thk];
Show[Append[g,Epilog->Dynamic@First@h],PlotRange->{{1,c},{1,r}},Frame->True],"MouseDown":>(AppendTo[pts,Round@MousePosition["Graphics"]])],
Dynamic[minutiaeTable[mins]]}}]]]

extractMinutiae[pts_]:=Map[({p1,p2}=#;Append[p1,N[ArcTan@@(p2-p1)]])&,Partition[pts,2]]

minGraphics[pts_,color_,thk_]:=
Module[{r,p,a,b},
r=Range[1,Length[pts],2];
p=Partition[pts,2];
a=Map[Point[#]&,Map[pts[[#]]&,r]];
b=Map[minObject[#,color,thk]&,p];
Graphics[{{color,a},b}]]

minutiaeTable[mins_]:=TableForm[Round[{1,1,180/π}#&/@mins],
TableHeadings->{Automatic,{"x","y","α°"}},TableSpacing->{1,4},TableAlignments->Right]

Minutiae Data (con't)

Manual Minutiae Detection Using Mathematica 6.0

o   On prints of poor image quality, such as many latents, minutiae may be designated manually.
o   Below, a few minutiae have been marked by 
     a.	clicking the mouse over a ridge ending or bifurcation and thus placing a red point
     b.	moving inward along a ridge ending or bifurcation and clicking it again
     c.	thus, placing a circle around the minutai's location, {x, y}, and a line indicating ridge direction, α.

designateMinutiae[id0]

mins

How is MM Mechanized ?

MM is mechanized in two processing stages, Registration and Matching.  Using quantized minutiae data, Registration is an approximate method that searches for the best relative orientation of the search print minutiae with respect to the file print and produces the vector of maximum translational similarity.  The more precise Matching process that follows uses the unquantized version of this  vector to translate and overlay the properly oriented search minutiae over those on the file print and, subsequently derive a matching score based on a Euclidean similarity measure.

Registration

1.   The centroids of the two sets of minutiae are first determined.
2.   The search minutiae are superimposed over the file minutiae with centroid congruency.
3.   The search minutiae are then rotated about the common centroid at fixed increments over a specified angular span.
4.   For each orientation all vector differences are computed between the search minutiae and those of the file print. 
5.   These differences are quantized by a measure of expected absolute minutiae error tolerance, typically {16, 16, π/6}.
6.   The quantized vector differences are then analyzed and the number of occurrences of similar such vectors is derived. 
7.   The vector with the highest occurrence count is identified.
8.   The orientation is incremented and, returning to Step 4, the process repeats.
9.   After traversing the specified angular span, the dominant or registration vector, is retrieved.

Matching

1.   The search minutiae are now translated by an unquantized estimate of the registration vector.
2.   Doing so, a subset of the search minutiae is identified that is in close proximity to a subset of file minutiae.
3.   Generally, the number of these matched minutiae exceed that of the registered minutiae.
4.   Given that n is the number of matched minutiae pairs and e is the list of the actual Euclidean distance errors between 
      corresponding ones, a reasonable similarity measure between the two prints is computed via

mmScore=((1000(Sqrt[n]))/(μ+(1/(Sqrt[n]))))

where μ is the mean value of e.

MM Operational Visualization Using Mathematica 6.0

rmViz[id0,id1]

MM Shortcomings and Techniques for Improving Performance

The simplistic approach that characterizes the classical MM relies on implicit assumptions that actually limit its performance. Besides displacement errors, major such assumptions are listed below with associated shortcomings and techniques for mitigating their effects on accuracy.

MM Ignores Image Quality

>>	•  In regions of poor image quality, minutiae are given equal importance, thus compromising performance.
<<	•  A probabilistic approach that takes minutiae quality into account could help improve the validity of the match.

MM Ignores Relative Distortion

>>	•  Matched minutiae errors could be magnified in the presence of moderate distortion.
         	•  Some matched minutiae may be invalid if the distortion is sufficiently pronounced.
<<    	•  Matching could be localized to smaller neighborhoods to overcome gradual relative distortion across the prints.
         	•  A mapping could be used to remove systematic errors in the presence of gradual moderate distortion.
         	•  Ridge period could be incorporated into the Euclidean measures.
         	•  A ridge period map could be used to characterize self distortion and used to minimize relative distortion.
         	•  Ridge counts among corresponding pairs of minutiae could be used as additional features.
 	•  The more detailed gray scale ridge structure between corresponding matched minutiae pairs could yield added  
 	   discrimination.

MM Ignores Geographical Consistency

>>    	•  Matching minutiae sets could reside in different relative geographical locations of the two prints.
<<    	•  Knowledge of vertical print orientations could practically eliminate this possibility.
	•  Geographical references such as cores and deltas (singular points) could be even more useful.
         	•  Scrutiny of non-matching minutiae regions, moderated by image quality, could help assess invalid matches.
	•  Directional maps could also help circumvent potential dislocated matches.
         	•  Singular points, augmented by image quality, could enhance accuracy and speed of registration and matching.

Cross Section Correlation Technique

This method, also known as the Gray Scale Matcher (GSM), was developed at Motorola's Biometrics Advanced Technology Group over 3 years ago using Mathematica 5.  It has since been integrated into the Omnitrak AFIS product improving its latent matching accuracy by over 10%.  The basic concept behind GSM involves an elastic gray scale correlation of cross section profiles along segments connecting corresponding pairs of matched minutiae produced by MM.

Bandpass Filtering of Print Images

o   Most simply, the images are filtered by a uniform bandpass filter.
o   A moving average of approximately a λ square (11 x 11 pixels) is removed from a given image.
o   A moving average of a λ/4 square (3 x 3 pixels) is used to smooth the image.

Extracting Cross Section Profiles

o   Matched minutiae pairs are connected by straight line segments.
o   The bandpass image is sampled at 1-pixel intervals along each given segment.
o   Corresponding such cross section profiles are obtained for both images.

Computing Correlation Coefficients

o   Given two corresponding cross section profiles, the shortest is linearly interpolated to the sample length of the longest.
o   After padding one of the profiles by 16 zeros on each end, a 33-sample correlation function is produced.
o   The maximum absolute value of this function is taken as the correlation coefficient.

Deriving Similarity Measure

o   Using correlation coefficients, c, and matched segment distances, (Subscript[d, 1]) and (Subscript[d, 2]), a reasonable similarity measure is defined by

κ=(c^2) ((((Subscript[d, 1])(Subscript[d, 2])))^0.25)

csScore=(1-(1.414^(-(n^0.707))))(μ-σ/(Sqrt[n]))

where, n is the common length of c, (Subscript[d, 1]) and (Subscript[d, 2]), while μ and σ are the mean and standard deviations of κ.

Cross Section Correlation Technique (con't)

Interactive Segment Selection on Latent

insertSegment[id0,Red]

q0=qts

Cross Section Correlation Technique (con't)

Interactive Segment Selection on File Print

insertSegment[id1,Red]

q1=qts

Cross Section Correlation Technique (con't)

Derived Cross Section Profiles and Correlation Function

Grid[{{crossSectionProfile[id0,q0,1,5,True]},{crossSectionProfile[id1,q1,1,5,True]},{crossSectionCorrelation[id0,id1,q0,q1]}}]

Cross Section Correlation Technique (con't)

A Closer Look at the Derivation of the Latent Profile via Bandpass Filtering

cspViz[id0,q0,1,5]

Cross Section Correlation Technique (con't)

A Closer Look at the Derivation of the File Print Profile via Bandpass Filtering

cspViz[id1,q1,1,5]

Cross Section Correlation Technique (con't)

o   17 latents are matched against all their 17 file prints via MM, CS, yielding 17 × 17 match csore matrices.
o   At each row, the corresponding latent is shown to match to the file print with the greatest score, indicated by a red dot.
o   The red dot along the diagonal are correct matches, invalid ones elsewhere.
o   MM and CS each yield 4 false matches.
o   By multiplicatively combining MM and CS match score matrices, the number of false matches is reduced to 2.

{mmm,csm,com}={mmScoreMatrix,csScoreMatrix,mmScoreMatrix*csScoreMatrix};
Grid[{MapThread[displayMatchMatrix[#1,#2]&,{{mmm,csm,com},{"MM","CS","MM \[Cross] CS"}}]}]

Summary

o   The work presented was done exclusively in Mathematica 6.0, using its interactive graphics capability and other newly
	introduced facilities.
	
o   The DynamicModule construct was used to demonstrate an essential aspect of an interactive graphics application for
	manually marking and collecting minutiae data for a given print.   With additional analytical support, this simple
	example could evolve to a Latent Examiner's Analytical Workbench.
	
o   The Manipulate construct was instrumental in imparting an intuitive understanding of the underlying mechanics of a
 	classical Minutiae Matcher (MM).   Integrated within this interactive graphics demonstration were options to observe
 	either one of the Registration or Matching stages involved over a fixed angular scan range, in discrete steps. 
 	In addition, an option was employed to display the two print images being matched.   

o   The DynamicModule construct was also used to designate cross section profiles along straight line segments connecting
	matched minutiae pairs.  Manipulate was used to show the extraction of an appropriate bandpass version of the
	associated cross section profile along corresponding matched minutiae pair segments for two prints.  The derivation
	of their correlation function followed.  These demonstrations provided a visual understanding of the Cross Section (CS)
	Correlation technique, one of several possible means for improving the matching performance in combination with MM.
	
o   The matching performance of MM, CS and a combination thereof were demonstrated in two small examples.  In practice,
	the CS or Gray Scale Matcher, has been reported to have boosted MM's accuracy by as much as 12%.
	
o   Mathematica 6.0 is widening the panorama of exciting opportunities in interactive application development to support
 	specialized scientific research in current and emerging fields, effective engineering practices through modeling and
	simulation, active learning for a wider sector of society and, most importantly, creative and meaningful teaching.

[1]  URL for Gray Scale Matcher
	http://www.motorola.com/governmentandenterprise/contentdir/en_US/Files/PressReleases/PR_2005Jun07_Hellenic_Police.pdf#search=%22Gray%20Scale%20Matcher%22
[2]  URL Gray Scale Patent Pending
	http://www.google.com/search?q=%22Sam+M.+Daniel%22&hl=en&lr=&start=10&sa=N