Latent Matcher Fusion

‐‐ Lessons Learned

IAI

97th International Conference

Phoenix, Arizona

Vladimir Dvornychenko

NIST

July 2012

8/7/2012 
Why Look at Matcher Fusion? 

• Matcher fusion provides a simple method for improving 

performance 

• What can be done via matcher fusion can, in principle, 

via a single “monolithic” matcher – but at potentially grincrease in code complexity 

• Fusion therefore provides us a means of assessing ho

performance “headroom”/available-performance-margwith current technology 

• This “available headroom/margin” is of interest to NIST 

connection with its ELFT project 

8/7/2012 
8/7/2012 

Principles of Matcher Fusion • From an information theoretic viewpoint, matcher fusion con

steps: 

– a) data compression – done by the original matchers – b) followed by data combining/fusion – performed by a s

algorithm 

• The result of fusion is a “virtual matcher” – which for all purp

indistinguishable from an “actual matcher” 

• Because in the “data compression step” some information is 

theoretically lost, and the resulting matcher might not have tpossible performance 

• In practice, because of the complexity involved, the fused m

outperform the “monolithic” (integrated) matcher 
Matcher A Matcher B

Output A 

(compressed 

data) 

Output B 

(compressed 

data) 

Fuse Outputs 

A & B 

Subject = M731Finger = 2Score = 3513 

Input data 

(large) 

Matching/ 

datacompression 

(in effect) 

Output/ 

extended 

candidate 

list(s) 

Fusion of 

candidate 

lists 

Final 

(fused) 

candidate 

list 

Simplified Diagram of Fusion Proces

8/7/2012 

Note: Inputs to the Matchers (A and B) need not be the same; for exampleMatcher A could use latent image, while Matcher B uses human-extracted 

features. 
8/7/2012 

--

Input image 

Preprocessor analyzes image 

to select optimal algorithm 

Interim candidate 

list 

Preprocessor 

Matcher B Matcher A

Subject = M731 Finger = 2 Score = 3513 

A number of architectures are availabimplementing fusion – first architectur

This architecture usepreprocessor to selecmore/most appropriamatcher/algorithm. In the form shown in either A or B would bbased on the analysiinput image. In a slight generalizaA and B are used, theoutputs are fused usoptimal weights, whiccomputed by the pre
8/7/2012 

A number of architectures are availabimplementing fusion – second archite

Midprocessor 

Interim candidate 

list 

 Algorithm B  Algorithm A

Subject = M731 Finger = 2 Score = 3513 

Subject = M731 Finger = 2 Score = 4732 

Subject = M731 Finger = 2 Score =5337 

This architecture employs a Mid-processor to fuse the outpof the matchers immediately afteeach matcher has finished its comparison with the current file/print. Both matchers, A and B, output summary of the comparison resThe output includes, as a minimthe matching score of each matbut may include additional data how many minutiae were actualmated, what was area of overlapSince there is no preprocessor, weights for fusion must be prede(e.g., equal). The “interim” candidate list is coupdated so as to retain only the running scores. Upon completiosearch the “interim” candidate lisThe “final” output candidate list. 
• Input image 

• Interim candidate 

lists 

• Final (merged) 

candidate list 

v Postprocessor 

Matcher B 

Subject = M938 

Matcher A 

Subject = M731 

Finger = 2 Finger = 2 

Score =8513 

Subject = M731 Finger = 2 Score =8732 

* * * * * * * * * * * * 

Score =3777 

A number of architectures are availabimplementing fusion – third architectu

8/7/2012 

This architecture employs a Postprocessor to fuse the outpuof the component matchers (A anupon completion of the entire search by both. Each (component) matcher outpua candidate list of pre-specified length (e.g., 100, 500, 1000). These two “interim” candidate lisare then fused to create the final output list. 
Architecture Employed in this Stu

• The third architecture (previous slide) was the 

actually used in this study 

• This choice was largely dictated by the nature 

available input data 

8/7/2012 
Matchers 

• The candidate lists of five different matchers w

used in this study 

• These are identified as Matchers A through E 

companies supplying these are identified on twebsite.) 

• These matchers were supplied to NIST for 

feature/matcher performance evaluation 

• Generally speaking, Matcher A was strongest

weakest 

8/7/2012 
Evaluation of Latent Fingerprint Technology (ELF

8/7/2012 

Scope Statement: •The overall purpose of NIST’s Eadvance the state-of-the-art in latsearches via: a) decreased depenexperts thru greater automation ; b) feature sets to facilitate data interchstandardized scores and performan•To accomplish this, NIST has planfor evaluating the state of the art in fingerprint matching. These tests walgorithmic capability of contemporaassist contractors/private-industry iproducts. Some test have been comprogress; and some are future plan•Testing Phases I and II, and EFS Ebeen completed, and the results caNIST website • Latent Website Mainpage 



http://fingerprint.nist.gov/latent/ 

The ELFT Approach 

Acquire Latent Matchers (SDKs) Configure Hardware 

Compile Latent Test Sets 

Latent Testbed 

•1-to-N Matcher Test Protocol •Analysis Reports •Standard Ref. Sets •Quality Metrics 

Iterate process Follow-up Workshop: 

Present results. Discuss future directions. 
Fingerprint Matching 

System 

8/7/2012 

How are Candidate Lists Genera

AFEM = Automated Feature Extraction and M

Latent Fingerprint 

Image Cand

Input Output 

Automatic Feature Extractor 

Latent Fingerprint Matcher 

features 

Rank Subject F

#

1 0731 2 1303 3 3950 ... ...

...

20 0121 

Michael Indovina IAD - Image Group 
8/7/2012 

Input to Matchers 

• The inputs to the matchers came in a number 

“flavors”: 

– Image only means the matcher is given only the image o

print – and no other information; the matcher must extract (native) search features 

– Features only means the matcher was given search feat

extracted by human experts – and no other information (simage); as a minimum, these features would include the tfeatures such as a) minutiae; b) core & delta; and c) patte

however in some cases these were augmented by extendfeatures 

– Image plus Features means that both a) the latent finger

image, and b) the human-extracted features were supplie

– Dual images means that two images from the same subj

the matchers (one to each matcher); these might or might come from the same finger; if from the same finger they acaptures 
Number of Searches and Backgro

• The principal search set consisted of 1357 lat

fingerprints; these consisted of representative casework, supplemented by special collection

• A second set consisted of 437 cases of multip

captures from subjects; the multiple capture mmight not, be from the same finger 

• The background consisted of 100K subjects = 

fingers. (Actually this refers to background + foreground, where foreground are the mates searches.) 

8/7/2012 
Input to Fusion Algorithm 

• The input to the fusion algorithm nominally co

of two candidate lists, each 100 candidates lo

• In exceptional cases, the candidate list might 

truncated or entirely missing; the fusion algorneeded to handle these cases 

• When the same input data is used for both m

the two matchers need be different for meaniresults 

• Otherwise, with different inputs, the two matc

being fused can be the same matcher (but opon different data) 

8/7/2012 
The Fusion was in Two Steps 

• Step 1 – a reduced working candidate 

created consisting of: 

– First place candidates from both lists – Selectively, second place candidates form 

lists 

– Any candidates appearing on both lists (su

and finger number same) 

• Candidate list were then checked for 

duplications; these were eliminated 

8/7/2012 
Step Two of Fusion 

• The second step consisted of computing a n

score; to avoid confusion with the original “natscore” we called this fused score a “figure of m(FOM) 

• Three different types of FOM were used: a) sc

based; b)rank-based; and c) “probability”-base

• For subjects appearing on both lists, their FO

boosted by adding the two FOMs (after suitabscaling) 

• “Probability,” in the present context, refers to a 

kind of normalized score appearing on candid

• The final step was to reorder the list based on 

8/7/2012 
Equal score contour 

when matchers are of equal strength 

Declare impostor if in this region 

Weaker Matcher 

Equal score contour when matchers are of unequal strength 

Stronger Matc

When matchers are of uneven strengtinfluence of the weaker must be reduc

8/7/2012 
Method of Gauging Performan

Gain 

• Two different performance gains were compu

– a) candidate-list-level gain – b) first-position gain 

• In each case the gain was based on the perfo

increase over the better of the two matchers 

• For the candidate-list-level gain, we compare

probability that the true mate is on the reducewith the probability it is on a list of equal lengtbetter matcher (this might require interpolatio

• A major reason for interest in the reduced can

list was our “candidate list reduction” goal 

8/7/2012 
8/7/2012 

Representative Gains from Fusio-- gains range from over 8%-points to under point 

Net performance (fused) fomatchers, candidate-list-ledata Note that although C-E shogains, it did not have highe

Performance Deltas for pairs of matchers, candidate-list-level, image-only data 
8/7/2012 

Average Candidate List Length-- In favorable cases the average length can be under unfavorable cases it might be greater than 35 

Average Reduced Candidate List Length 

-- favorable case 

Average Reduced Candidate 

-- unfavorable case 

Notes: 1) Left graph shows two different matcher pairs working on image-only data – there a 

2) Right graph shows a) matchers A-E working on image-only fused with b) matcher – there are many impostors in common for the combination A/LA & A/LE 
8/7/2012 

When operating on different input datastronger (of the two) matcher should gbetter (more information) dataset 

Operating on Dataset LG 

Operating on 

Dataset LE 

Matcher A B C D 

A 67.9 69 68.8 6

B 64.8 65 65.1 6

C 62.5 64.3 62.6 5

D 

E 

45.5 48.7 48.7 259.8 61 60.4 5
8/7/2012 

Pearson correlation measure was found NOT the most useful for predicting fusion gains 
Performance Delta 

Match

12.00% 10.00% 

8.00% 6.00% 4.00% 2.00% 0.00% 

Percentage points performance 

increase 

C-E A-B A-E B-E D-E 

Alternative Correlation Measure 

1 

0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 

0 

C-E A-B D-E C-D A-D A-E B-E A-C B-C B-D 

q1 q2 

8/7/2012 

An “Alternative” Correlation Measure Proposed – and it does well! 
How is this “Alternative” correlation 

defined? 

• Suppose we have two matchers, A & B, and A 

better performing of the two in terms of “hits” place 

• Consider now creating another (virtual) match

B*, which is a “dumbed-down” version of A, hthe same first-place performance as B 

• We create B* by randomly switching between 

Matcher A, and 2) a “random-guessing” matcfrequency of switches is so chosen as to reduperformance to B level. 

• Now compute the (Pearson) correlation betwe

and B* (call it r) -- continued 

8/7/2012 
delta_perf_vs_q1 

12.00% y = -0.2727x + 0.258

R2 = 0.7296 10.00% 

8.00% delta_perf 

6.00% 

Linear 4.00% (delta_per

2.00% 0.00% 

0 0.5 1 

8/7/2012 

-- More on “Alternative” Correlatio• Let ρ (rho) denote the Pearson correlation be

& B 

• The new -- “alternative” – correlation is define

and we denote this by q 

• “q” does a good job in predicting performance 

as seen below 
8/7/2012 

Ranking FOMs/algorithms 

• Four types of scores – referred to as Figures-of-Merit, o

were looked at 

– 1) Rank based (Borda count) 

– 2) “Probability” based – 3) Native score based, global normalization – 4) Native score based, local normalization 

• Giving both matchers equal weight sometimes produce

negative gains; however, for simplicity, we retained this in some cases 

• Score-based generally produced largest gains 

Matcher pair  ‐‐>

A‐B A‐C E_B average

FOM type

rankprob.scorerel_score

‐5.31% ‐5.23% 3.76%

0.59% 1.47% 3.32%

0.37% 3.02% 6.48%0.22% 2.58% 4.27%

‐2.26%

1.79%

3.29%2.36%
8/7/2012 

Multi-finger Results 

• Up to now we have considered fusion where the input 

from the same latent fingerprint image – whether featuextracted by machine, or by human experts 

• We now consider the case where the input consists of 

different images from the same subject; but the imagmight be from the same finger or different fingers 

• The matrix below shows that performance is more than 

when two different images are used; this can be attribuinflux of new information; alternatively, we can say S/N increased by 41% 
Conclusions: 

• Matcher fusion can produce significant performance g

do not expect “eye-popping” gains 

• Gains are on the order of 6-8% points when based on 

coming from a single input image 

• As an independent check, we considered scoring a hi

the five matchers placed the true mate in first positionresulted in 11% points improvement over the single be

• For two different images (from same subject) gains ar

higher, around 15%-points 

• Candidate lists can be greatly reduced, 2-6 candidate

have performance exceeding 20 candidates from sing

8/7/2012 
References/Links 

• Evaluation of Fusion Methods for Latent Fingerprint Matchers, 

Dvornychenko, V. N.; 5th IAPR International Conference on Biomet2012  http://www.nist.gov/manuscript-publicationsearch.cfm?pub_id=910369 

• Latent Website Mainpage  http://fingerprint.nist.gov/latent/ 

• Final Report on Phase II Testing 

http://fingerprint.nist.gov/latent/NISTIR_7577_ELFT_PhaseII.pdf 

• NIST Latent Fingerprint Testing Workshop 2009, March 19 & 20

http://fingerprint.nist.gov/latent/workshop09/index.html 

• ELFT-EFS Homepage, April 2009  http://fingerprint.nist.gov/late

EFS/ 

8/7/2012 
• NIST would like to thank its 

sponsors of this work: 

• DHS/Science and Technology Directo

(S & T) 

• FBI/Criminal Justice Information Servi

(CJIS) 

8/7/2012 
8/7/2012 

Thank you! 

Questions? 

Contacts: 

Vladimir Dvornychenko 

NIST 

vdvorny@nist.gov