End-to-End Latent Fingerprint Search
Kai Cao Dinh-Luan Nguyen Cori Tymoszek A. K. Jain

	
	
	























































Journal of  Class Files, Vol. 14, No. 8, August 2015
Shell et al.: Bare Demo of IEEEtran.cls for Biometrics Council Journals






































Latent fingerprints are one of the most important and widely used sources of evidence in law enforcement and forensic agencies. Yet the performance of the state-of-the-art latent recognition systems is far from satisfactory, and they often require manual markups to boost the latent search performance. Further, the COTS systems are proprietary and do not output the true comparison scores between a latent and reference prints to conduct quantitative evidential analysis. We present an end-to-end latent fingerprint search system, including automated region of interest (ROI) cropping,  latent image preprocessing, feature extraction, feature comparison , and outputs a candidate list.  Two separate minutiae extraction models provide complementary minutiae templates.  To compensate for the small number of minutiae in small area and poor quality latents, a virtual minutiae set is generated to construct a texture template.  A 96-dimensional descriptor is  extracted for each minutia from its neighborhood.  For computational efficiency, the descriptor  length for virtual minutiae  is further reduced to 16  using product quantization. Our end-to-end system is evaluated   on three latent databases: NIST SD27 (258 latents); MSP  (1,200 latents), WVU  (449 latents) and N2N (10,000 latents) against a background set of 100K rolled prints, which includes the true rolled mates of the latents with rank-1 retrieval rates of 65.7%, 69.4%,  65.5%, and 7.6% respectively.  A multi-core solution implemented on 24 cores obtains 1ms per latent to rolled comparison. 





Latent fingerprint recognition,  end-to-end system, deep learning, autoencoder, minutiae descriptor, texture template,  reference fingerprint.




End-to-End Latent Fingerprint Search
    Kai Cao, Member, IEEE,
        Dinh-Luan Nguyen, Student Member, IEEE, Cori Tymoszek, Student Member, IEEE, and Anil K. Jain, Fellow, IEEE

Kai Cao, Dinh-Luan Nguyen, Cori Tymoszek and A.K. Jain are with the Dept. of Computer Science and Engineering, Michigan State University, East Lansing, MI 48824 U.S.A. 

E-mail: {kaicao,jain}@cse.msu.edu




    December 30, 2023
===============================================================================================================================================================================================================================================================================================================================================================






























§ INTRODUCTION


Latent fingerprints[Latent fingerprints are also known as latents or fingermarks] are arguably the most important forensic evidence that has been in use since 1893 <cit.>. Hence, it is not surprising that fingerprint evidence at crime scenes is often regarded as ironclad.  This effect is compounded by the depiction of fingerprint evidence in media  in solving high profile crimes. For example, in the 2008 film The Dark Knight[https://www.imdb.com/title/tt5281134/] a shattered bullet is found at a crime scene. The protagonists create a digital reconstruction of the bullet's fragments, upon which a good quality fingermark is found, unaffected by heat or friction from the firing of the gun, nor by the subsequent impact. A match is quickly found in a fingerprint database, and the suspect's identity is revealed!












The above scenario, unfortunately, would likely have a much less satisfying outcome in the real forensic case work. While  processing of fingermarks has improved considerably due to advances in forensics, the problem of identifying latents, whether by forensic experts or automated systems, is far from solved. The primary difficulty in the analysis and identification of latent fingerprints is their poor quality  (See Fig. <ref>). Compared to rolled and slap prints (also called reference prints or exemplar prints), which are acquired under supervision, latent prints are lifted after being unintentionally deposited by a subject, e.g., at crime scenes, typically resulting in poor quality in terms of ridge clarity and presence of large background noise. In essence, latent prints are partial prints, containing only a small section of the complete fingerprint ridge pattern. And unlike reference prints, investigators do not have the luxury of requesting a second impression from the culprit if the latent is found to be of extremely poor quality.



The significance of  research on latent identification is evident from the volume of latent fingerprints processed annually by publicly funded crime labs in the United States. A total of 270,000 latent prints were received by forensic labs for processing in 2009 <cit.> which rose to 295,000 in 2014,  an increase of 9.2% <cit.>. In June 2018, the FBI's Next Generation Identification (NGI) System received 19,766 requests for Latent Friction Ridge Feature Search (features need to be marked by an examiner) and 5,692 requests for Latent Friction Ridge Image Search (features are automatically extracted by IAFIS) <cit.>. These numbers represent an increase of 6.8% and 25.8%, respectively, over June 2017 <cit.>.  Every year, the Criminal Justice Information Services (CJIS) Division gives its Latent Hit of the Year Award to latent print examiners and/or law enforcement officers who solve a major violent crime using the Bureau's Integrated Automated Fingerprint Identification System, or IAFIS[https://www.fbi.gov/video-repository/newss-latent-hit-of-the-year-program-overview/view.]. 




National Institute of Standards & Technology (NIST) periodically conducts technology evaluations of fingerprint recognition algorithms, both for rolled (or slap) and latent prints. In NIST's most recent evaluation of rolled and slap prints, FpVTE 2012, the best performing AFIS achieved a false negative identification rate (FNIR) of 1.9% for single index fingers, at a false positive identification rate (FPIR) of 0.1% using 30,000 search subjects (10,000 subjects with mates and 20,000 subjects with no mates) <cit.>. For latent prints, the most recent evaluation is the NIST ELFT-EFS where the best performing automated latent recognition system could only achieve a rank-1 identification rate of 67.2% in searching 1,114 latents against a background containing 100,000 reference prints <cit.>. The rank-1 identification rate of the best performing latent AFIS was improved from 67.2% to 70.2%[The best accuracy using both markup and image is 71.4% @ rank-1.] <cit.> when feature markup by a latent expert was also input, in addition to the latent images, to the AFIS. This gap between reference  and latent fingerprint recognition capabilities is primarily due to the poor quality of friction ridges in latent prints (See Fig. <ref>). This underscores the need for developing automated latent recognition with both high speed and accuracy[Automated latent recognition is also referred to as lights-out recognition;  objective is to minimize the role of latent examiners in latent recognition.].  An automated latent recognition system will also assist in developing quantitative assessment of validity and reliability measures[Commercial AFIS neither provide extracted latent features nor the true comparison scores.  Instead, only truncated and/or modified scores are reported.] for latent fingerprint evidence as highlighted in the 2016 PCAST <cit.> and  the 2009 NRC <cit.> reports.








 In the biometrics literature, the first paper on latent recognition was published by Jain et al.  <cit.> in 2008 by using manually marked minutiae, region of interest (ROI) and ridge flow. Later, Jain and Feng  <cit.>  improved the identification accuracy by using  manually marked extended latent features, including ROI, minutiae, ridge flow, ridge spacing and skeleton. However, marking these extended features in poor quality latents is very time-consuming and might not be feasible. Hence, the follow-up studies focused on increasing the degree of automation, i.e., reduction in the numbers of  manually marked features for matching, for example, automated ROI cropping <cit.>, ridge flow estimation <cit.> and ridge enhancement <cit.>, deep learning based minutiae extraction <cit.>, and comparison <cit.>.  However, these studies only focus on specific modules in a latent AFIS and  do not build an end-to-end system. 
 
 

Cao and Jain <cit.> proposed an automated latent recognition system which  includes automated steps of ridge flow and ridge spacing estimation, minutiae extraction, minutiae descriptor extraction, texture template (also called virtual minutiae template) generation and graph-based matching, and achieved the state-of-the-art accuracies on two latent databases, i.e., NIST SD27 and WVU latent databases. However, their study has the following limitations: (i) manually marked ROI is needed, (ii) skeleton-based minutiae extraction used in <cit.> introduces a large number of spurious minutiae, and (iii) a large texture template size (1.4MB) makes latent-to-reference comparison extremely slow.  Cao and Jain <cit.> improved both identification accuracy and search speed of texture templates by (i) reducing the template size, (ii)  efficient graph matching, and (iii) implementing the matching code in C++.  In this paper, we build a fully automated end-to-end system, and improve the search accuracy and computational efficiency of the system. We report results on three different latent fingerprint databases, i.e., NIST SD27, MSP and WVU, against a 100K background of reference prints.   




§ CONTRIBUTIONS

The design and prototype of the proposed latent fingerprint search system is a substantially improved version of the work in <cit.>.  Fig. <ref> shows the overall flowchart of the proposed system. The main contributions of this paper are as follows:
 
 
  

  * An autoencoder based latent fingerprint enhancement for robust and accurate extraction of ROI, ridge flow and ridge spacing.

  * An autoencoder based latent minutiae detection.

  * Complementary templates: three minutiae templates and one texture template.  These templates were selected from a large set of candidate templates to achieve the best recognition accuracy. 

  * Reducing descriptor length of minutiae template and texture template using non-linear mapping <cit.>. Descriptor for reference texture template is further reduced using product quantization for computational efficiency.  


  * Latent search results on NIST SD27, MSP, and WVU latent databases against a background of 100K rolled prints show the state-of-the-art performance.


  * A multi-core solution implemented on Intel(R) Xeon(R) CPU E5-2680 v3@2.50GHz takes ∼1ms per latent-to-reference comparison. Hence, a latent search against 100K reference prints can be completed in  100 seconds. Latent feature extraction time is ∼15 seconds on a machine with Intel(R) i7-7780@4.00GHz (CPU) and GTX 1080 Ti (GPU).






§ LATENT PREPROCESSING



 §.§ Latent Enhancement via Autoencoder

We present a convolutional autoencoder for latent enhancement. The enhanced images are required to find robust and accurate estimation of ridge quality, flow, and spacing. The flowchart for network training is shown in Fig. <ref>.    








Since there is no publicly available dataset consisting of pairs of low quality and high quality fingerprint image for training the autoencoder, we degrade 2,000 high quality rolled fingerprint images (NFIQ 2.0[NFIQ 2.0 <cit.> ranges from 0 to 100, with 0 indicating the lowest quality and 100 indicating the highest quality fingerprint.] value > 70)  to create image pairs for training. The degradation process involves randomly dividing fingerprint images into overlapping patches of size 128 × 128 pixels, followed by additive gaussian noise and Gaussian filtering with  a parameter σ (σ∈ (5,15)).   Fig. <ref> shows some examples of high quality fingerprint patches and their corresponding degraded versions. In addition, data augmentation methods (random rotation, random brightness and change in contrast) were used to improve the robustness of the trained autoencoder.


The convolutional autoencoder  includes an encoder and a decoder, as shown in Fig. <ref>. The encoder consists of 5 convolutional layers with a kernel size of 4× 4 and stride size of 2, while the decoder consists of 5 deconvolutional layers (or  transposed convolutional layer <cit.>) also with a kernel size of 4× 4 and stride size of 2. The activation function ReLU (Rectified Linear Units) is used after each convolutional layer or deconvolutional layer with the exception of the last output layer, where the tanh function is used. Table <ref> summarizes the architecture of the  convolutional Autoencoder. 


 

The autoencoder trained on rolled prints does not work very well in enhancing latent fingerprints. So, instead of raw latent images, we input only the texture component of the latent by image decomposition <cit.> to the autoencoder. Fig. <ref> (b) shows the enhanced latent corresponding to the latent image in Fig. <ref> (a). The enhanced latents have significantly higher ridge clarity than input latent images. 



 §.§ Estimation of Ridge Quality, Ridge Flow and Ridge Spacing
 




The dictionary based approach proposed in <cit.> is modified as follows. Instead of learning the ridge structure dictionary using high quality fingerprint patches, we construct the dictionary elements with different ridge orientations and spacings using the approach described in <cit.>.  Fig. <ref> illustrates some of the dictionary elements in vertical orientation with different widths of ridges and valleys.  


In order to estimate the ridge flow and ridge spacing, the enhanced latent image output by the autoencoder is divided into 32×32 patches with overlapping size of 16×16 pixels. For each patch P, its similarity s_i with each dictionary element d_i (normalized to mean 0 and s.d. of 1) is computed as s_i = P· d_i/||P||+α,  where · is the inner product, ||·|| denotes the l_2 norm and α (α=300 in our experiments) is a regularization term.  The dictionary element d_m with the maximum similarity s_m (s_m>=s_i, ∀ i≠ m) is selected and the ridge orientation and spacing of P are regarded as the corresponding values of d_m.  The ridge quality of the patch P_I in the input latent image  corresponding to P is defined as the sum of s_m and the similarity between P_I and P. Figs. <ref> (c), (d) and (f) show the ridge quality, ridge flow and ridge spacing, respectively.  Patches with ridge quality larger than s_r (s_r=0.35 in our experiments) are considered as valid fingerprint patches. Morphological operations, including open and close operations, are used to obtain a smooth cropping.  Fig. <ref> (d) shows the cropping (ROI) of the latent in Fig. <ref> (a).







§ MINUTIAE DETECTION VIA AUTOENCODER

A  convolutional Autoencoder-based minutiae detection approach is proposed in this section. Two minutiae extractor models are trained: one model (MinuNet_reference) is trained using manually edited minutiae on reference fingerprints while the other one (MinuNet_Latent) is fine-tuned based on MinuNet_reference using manually edited minutiae on latent fingerprint images.





 §.§ Minutiae Editing

In order to train networks for minutiae extraction for latent and reference fingerprints, a set of ground truth minutiae are required. However, marking minutiae on poor quality latent fingerprint images and low quality reference fingerprint images is very challenging. It has been reported that even experienced latent examiners have low repeatability/reproducibility <cit.> in minutiae markup. To obtain reliable minutiae ground truth, we designed a user interface to show a pair of latent and its corresponding reference fingerprint images side by side; the reference fingerprint image assists in editing minutiae on the latent.  The editing tool includes operations of insertion, deletion, and repositioning minutiae points (Fig. <ref>).   Instead of starting markup from scratch, some initial minutiae points and minutiae correspondences were generated using our automated minutiae detector and matcher. Because of this, we refer to this manual process  as minutiae editing to distinguish it from markup from scratch.   
 
The following editing protocol  was used on the initially marked minutiae points: i) remove spurious minutiae detected outside the ROI and those erroneously detected due to noise; ii) the locations of remaining minutiae points were adjusted as needed to ensure that they were accurately localized, iii) missing minutiae points which were visible in the image were marked; iv) minutiae correspondences between latent and its rolled mate were edited, including insertion and deletion; A thin plate spline (TPS) model was used to transform minutiae in latent and its rolled mate, and  v) a second round of minutiae editing (steps (i)-(iv) ) was conducted on latents. One of the authors carried out this editing process.

 


For training a minutiae detection model for reference fingerprints, i.e., MinuNet_reference,  a total of 250 high quality and poor quality fingerprint pairs from 250 different fingers from the MSP longitudinal fingerprint database <cit.> were used.  A finger was selected if there is an impression (image) of it with the highest NFIQ 2.0 value Q^h and the lowest NFIQ 2.0 value Q^l which satisfies the following criterion (Q^h - Q^l)> 70. This ensured that we can obtain both high quality and low quality images for the same finger (See Fig. <ref>). A COTS SDK was used to get the initial minutiae and correspondences between selected fingerprint image pairs. 




 
 


Given the significant differences in the characteristics of latents and rolled reference fingerprints, we fine-tuned the MinuNet_reference  model using minutiae in latent fingerprint images. A total of 300 latent and reference fingerprint pairs from the MSP latent database were used for retraining.  The minutiae detection model MinuNet_reference was used to extract initial minutiae points and a graph based minutiae matching algorithm proposed in <cit.> was used to establish initial minutiae correspondences.  





 §.§ Training Minutiae Detection Model

 Fig. <ref> shows a  convolutional autoencoder-based network for minutiae detection. The advantages of this model include: i) a large training set since the image patches can be input to the network  instead of the whole images , and ii) generalization of the network to fingerprint images larger than the patches. In order to handle the variations in the number of minutiae in fingerprint patches, we encode the minutiae set as a 12-channel minutiae map and pose the training of minutiae detection model as a regression problem.  
 
  A minutia point m is typically represented as a triplet m=(x,y,θ), where x and y specify its location, and θ is its orientation (in the range [0,2π]). Inspired by minutia cylinder-code <cit.>, we encode a minutiae set as a c-channel heat map and pose the minutiae extraction as a regression problem  (c=12 here). Let h and w be the height and width of the input fingerprint image I and T={m_1,m_2,..., m_n} be its ISO/IEC 19794-2 minutiae template with n minutiae points, where m_t=(x_t,y_t,θ_t), t=1,...,n. Its minutiae map H∈ R^h× w× 12 is calculated by accumulating contributions from each minutiae point. Specifically, for each point (i, j, k), a response value M(i,j,k) calculated as 

    M(i,j,k) = ∑_t=1^n C_s((x_t,y_t),(i,j)) · C_o(θ_t,2kπ/12)

where the two terms C_s((x_t,y_t),(i,j)) and C_o(θ_t,2kπ/12) are the spatial and orientation contributions of minutia m_t to image point (i, j, k),
respectively. C_s((x_t,y_t),(i,j)) is defined as a function of the
Euclidean distance between (x_t,y_t) and (i,j):

    C_s((x_t,y_t),(i,j)) = exp(-||(x_t,y_t)-(i,j)||_2^2/2σ_s^2),

where σ_s is the parameter controlling the width of the Guassian. C_o(θ_t,2kπ/12) is defined as a function of  the difference in orientation value between θ_t and 2kπ/12:

    C_o(θ_t,2kπ/12) = exp(-dϕ(θ_t,2kπ/12)/2σ_s^2),

and  dϕ(θ_1,θ_2) is the orientation difference between angles θ_1 and  θ_2:

    dϕ(θ_1,θ_2)=  |θ_1 - θ_2|    -π≤θ_1-θ_2<π,
    
    2π-|θ_1 - θ_2|    otherwise.

Fig. <ref> illustrates 12-channel minutiae map, where the bright spots indicate the locations of minutiae points. This autoencoder architecture used for minutiae detection is similar to the autoencoder for latent enhancement with parameters specified in Table <ref>. The  three differences are thati i) the input fingerprint patches are size of 64× 64 pixels,  ii) the output is a 12-channel minutiae map rather than a single channel fingerprint image, and ii) the number of of convolutional layers and deconvolutional layers are 4 instead of 5. 







 


The two minutiae detection models  introduced earlier, MinuNet_reference and MinuNet_Latent, are trained. For reference fingerprint images, the unprocessed fingerprint patches are used for training. On the other hand, latent fingerprint images were processed by short-time Fourier transform (STFT)  for training in order to alleviate the differences in latents; the model MinuNet_Latent is a fine-tuned version of the model MinuNet_reference.








 §.§ Minutiae Extraction


Given a fingerprint image of size w× h in the inference stage, a w× h × 12 minutiae map M is output by a minutiae detection model.  For each location (i,j,c) in M, if  M(i,j,c) is larger than a threshold m_t and it is a local max in its neighboring 5× 5 × 3 cube,  a minutia is marked at location (i,j). Minutia orientation θ is computed by maximizing the quadratic interpolation based on  f((c-1)·π/6)=M(i,j,(c-1)%12), f( c·π/6) = M(i, j, c) and f( (c+1)·π/6)=M(i,j,(c+1)%12), where a%b denotes a modulo b. Fig. <ref> illustrates minutia orientation estimation from the minutiae map.  Fig. <ref> shows some examples of minutiae extracted in reference fingerprints. 













§ MINUTIA DESCRIPTOR
 




















A minutia descriptor contains attributes of the minutia based on the image characteristics in its neighborhood. Salient descriptors are needed to establish robust and accurate minutiae correspondences and compute the similarity between a latent and reference prints. Instead of specifying the descriptor in an ad hoc manner, Cao and Jain <cit.> showed that  descriptors learned from local fingerprint patches provide better performance than ad hoc descriptors. Later they improved  both the distinctiveness  and the efficiency of descriptor extraction <cit.>.  Fig. <ref> illustrates the descriptor extraction process. The outputs (l-dimensional feature vector) of three patches around each minutia are concatenated to generate the final descriptor with dimensionality 3l.   Three values of l ( i.e., l=32, 64, and 128), were investigated;  we empirically determine that  l=64 provides the best tradeoff between recognition accuracy and  computational efficiency. In this paper, we adopt the same descriptor as in  <cit.> , where the descriptor length  L=192.






Since there are a large number of virtual minutiae (∼ 1,000) in a texture template, further reduction of descriptor length is essential for improving the comparison speed between input latent and 100K reference prints. We utilized the non-linear mapping network of  Gong et al. <cit.> for dimensionality reduction.  The network consists of four linear layers (see Fig. <ref>), where the objective is to minimize the distance between the cosine similarity of two input descriptors and  the corresponding cosine similarity of two output compressed descriptors. Empirical results show that the best value of the descriptor length in the compressed domain (L_d) in terms of recognition accuracy is 96.  In order to further reduce the virtual minutiae descriptor length, product quantization is adopted. Given a L_d-dimensional descriptor y, it is divided into m subvectors, i.e., y=[y_1|y_2|...|y_m], where each subvector is of size L_d/m.  The quantizer q contains m subquantizers i.e.,  q(y)↦ [q_1(y_1)|q_2(y_2)|...|q_m(y_m)], where each subquantizer quantizes the input subvector into the closest centroid out of the 256 centroids trained by k-means clustering. Fig. <ref> illustrates the product quantization process.  The distance D(x,q(y)) between an input 96-dimensional descriptor x and a quantized descriptor q(y) is computed as 

    D(x,q(y))=∑_i=1^m||x_i- c_q(y_i)^i||,

 where x_i is the ith subvector of x,  c_q(y_i)^i is the q(y_i)th centroid of the ith subvector and ||·|| is the Euclidean distance. The final dimensionality of the descriptor of rolled prints is m=16.


 





§ REFERENCE TEMPLATE EXTRACTION

Given that the quality of reference fingerprints, on average, is significantly better than latents, a smaller number of templates suffice for reference prints compared to latents.  Each reference fingerprint template consists of one minutiae template and one texture template. The model MinuNet_reference was used for minutiae detection on reference fingerprints. Since the reference fingerprint images were directly used for training, no preprocessing on the  reference fingerprint images is needed.  Fig. <ref> show some examples of minutiae sets extracted on low quality and high quality rolled fingerprint images. For each minutia,  the descriptor is extracted following the approach shown in Fig. <ref> with descriptor length reduction via nonlinear mapping in Fig. <ref>. 










A texture template for reference prints is introduced in the same manner as for latents. The ROI for reference prints is defined by the magnitude of the gradient and the orientation field with a block size of 16× 16 pixels as in <cit.>. 
The locations of virtual minutiae are sampled by raster scan with a stride of s and their orientations are the same as the orientations of its nearest block in the orientation field. The virtual minutiae close to the mask border are ignored.  Fig. <ref> shows  virtual minutiae extracted in two rolled prints. Similar to real minutiae, a  96-dimensional descriptor is first obtained using Fig. <ref>  and   Fig. <ref>, and then further reduced to 16 dimensions using product quantization.























§ LATENT TEMPLATE EXTRACTION



 In order to extract complementary minutiae sets for latents, we apply two minutiae detection models, i.e.,  MinuNet_Latent  and MinuNet_reference, to four differently processed latent images as described earlier. This results in five minutiae sets.  A common minutiae set (minutiae set 6) is obtained from these five minutiae sets using majority voting. A minutia is regarded as a common minutia if two out of the four minutiae sets contain that minutia, which means the distance between two minutiae locations is less than 8 pixels and the difference in  minutia orientation is less than π/6. Fig. <ref> shows these five minutiae sets.  For computational efficiency,  only minutiae sets 1, 3 and 6 are retained for matching.  Each selected minutiae set as well as the set of associated  descriptors form a minutiae template.  The texture template consists of the virtual minutiae located using ROI and ridge flow <cit.>, and their associated descriptors.   Algorithm <ref> summarizes the latent template extraction process.












§ LATENT-TO-REFERENCE PRINT COMPARISON

Two comparison algorithms, i.e., minutiae template comparison and texture template comparison, are proposed for latent-to-reference comparison (See Fig. <ref>).






 §.§ Minutiae Template Comparison


Each minutiae template contains a set of minutiae points, including their x, y-coordinates and orientations, and their associated descriptors.  Let M^l = {m_i^l =(x_i^l,y_i^l,α_i^l, d_i^l)}_i=1^n_l denote a latent minutiae set with n_l minutiae, where (x_i^l,y_i^l), 
α_i^l and d_i^l are x- and y-coordinates, orientation and descriptor vector of the ith minutia, respectively. Let  M^r = {m_j^r =(x_j^r, y_j^r,α_j^r, d_j^r)}_j=1^n_r  denote a reference print minutiae set with n_r minutiae,  where (x_j^r,y_j^r), α_j^r  and d_j^r are their  x- and y-coordinates, orientation and descriptor of the jth reference minutia, respectively.  The comparison algorithm in <cit.> is adopted for minutiae template comparison. For completeness, we summarize the minutiae template comparison algorithm in  Algorithm <ref>.






 §.§ Texture Template Comparison


Similar to the minutiae template, a texture template contains a set of virtual minutiae points, including their x, y-coordinates and orientations, and associated quantized descriptors. Let T^l = {m_i^l =(x_i^l,y_i^l,α_i^l, d_i^l)}_i=1^n_l   and T^r = {m_j^r =(x_j^r, y_j^r,α_j^r, d_j^r)}_j=1^n_r denote a latent texture template and a reference texture template, respectively, where d_i^l is a 96-dimensional descriptor of the ith latent minutia and d_j^r is the 96/m-dimensional quantized descriptor of the jth reference minutia. The overall texture template comparison algorithm is essentially the same as the  
 minutiae template comparison algorithm in  Algorithm <ref> with two main differences: i) descriptor similarity computation and ii) top N virtual minutiae correspondences selection.  The similarity s(d_i^l,d_j^r) between d_i^l and  d_j^r is computed as  s(d_i^l,d_j^r) = D_0 -D(d_i^l,d_j^r), where D_0 is a threshold and D(d_i^l,d_j^r) is defined in Eq. (<ref>)  which can be computed offline. 

Instead of normalizing all scores and then selecting the top N (N=200 for texture template comparison) initial virtual minutiae correspondences among all n_l× n_r possibilities, we select the top 2 reference virtual minutiae for each latent virtual minutiae based on virtual minutiae similarity and select the top N  initial virtual minutiae correspondences among 2· n_l possibilities (2· n_l correspondences are all selected if 2· n_l<=N). In this way, we further reduce the computation time. 




 §.§ Similarity Score Fusion

Let s_MT,1, s_MT,2 and s_MT,3 denote  the similarities  between the three latent minutiae templates against the single reference minutiae template. Let s_TT denote the similarity between the latent and reference texture templates.  The final similarity score s between the latent and the reference print is computed as the weighted sum of s_MT,1, s_MT,2, s_MT,3 and s_TT as below:

    s =λ_1 s_MT,1 + λ_2 s_MT,2 + λ_3 s_MT,3+λ_4 s_TT,

where λ_1, λ_2, λ_3 and  λ_4 are the weights that sum to 1; their values are empirically determined to be  1, 1, 1 and 0.3, respectively.




 §.§ Implementation




Both minutiae template comparison and texture template comparison algorithms are implemented in C++. In addition, matrix computation tool Eigen[https://github.com/libigl/eigen] is used for faster minutiae similarity computation.  OpenMP (Open Multi-Processing)[https://www.openmp.org/resources/openmp-compilers-tools/],  an application programming interface (API) that supports multi-platform shared memory multiprocessing programming, is used for code parallelization. Hence the latent-to-reference comparison algorithm can be executed on multiple cores simultaneously. The search speed  (∼1.0 ms per latent to reference print comparison) on a 24-core machine   is able to achieve about 10-times speedup  compared to a single-core machine.








































 
 

































§ EXPERIMENTS
 












In this report, three latent databases, NIST SD27 <cit.>, MSP  and WVU databases are used to evaluate the proposed end-to-end latent AFIS.  Table <ref> summarizes the three latent databases and Fig. <ref> shows some example latents. 
In addition to the mated reference
prints, we use additional reference fingerprints, from NIST SD14 <cit.> and a forensic agency,
to enlarge the reference database to 100,000 for search results reported here. We follow the protocol used in NIST ELFT-EFS <cit.>, <cit.> to evaluate the search performance of our system. 








 §.§ Evaluation of Descriptor Dimension Reduction

We evaluate the non-linear mapping based descriptor dimension reduction and product quantization on NIST SD27 against a 10K gallery.  Non-linear mapping is adopted to reduce the descriptor length of both real minutiae and virtual minutiae. Three different descriptor lengths, i.e., 128, 96 and 64, are evaluated.   Table <ref> compares the search performance of different descriptor lengths. There is a slightly drop for 96- and 48-dimensional descriptors, but a significantly drop for 48-dimensional descriptors. 

Because of the large number of virtual minutiae, we further reduce the descriptor length of virtual minutiae using product quantization.  Table <ref> compares the search performance of texture template on NIST SD27 using three different number of subvectors of 96-dimensional descriptors, i.e., m=24, 16 and 12.  m=16 achieves a good tradeoff between accuracy and feature length.  Hence, we use non-linear mapping to reduce  the descriptor length from 192 dimension to  96 dimension and then further reduce virtual minutiae descriptor length to m=16 using product quantization in the following experiments.


























 §.§ Search Performance


We benchmark the proposed latent AFIS against one of the best COTS latent AFIS[The latent COTS used here is one of the top-three performers in the
NIST ELFT-EFS evaluations  <cit.>, <cit.> and the method in <cit.>.  Because of our non-disclosure
agreement with the vendor, we cannot disclose its name.] as determined in NIST evaluations. Two fusion strategies, namely score-level fusion
(with equal weights) and rank-level fusion (top-200 candidate lists are fused using Borda count), are adopted to determine if the proposed algorithm and COTS latent AFIS have complementary search capabilities. In addition,  the algorithm proposed in <cit.> is also included for comparison on NIST SD27 and WVU databases.  

 The performance is reported based on close-set identification where the query is assumed to be in the gallery. Cumulative Match Characteristic (CMC) curve is used for performance evaluation.  Fig. <ref> compares the five CMC curves on all 258 latents in NIST SD27 as well as subsets of latents of three different quality levels (good, bad and ugly) and  Fig. <ref>  compares the four CMC curves on 1,200 latents in MSP latent database.  On both operational latent databases, the performance of our proposed latent AFIS is comparable to that of COTS latent AFIS. In addition, both rank-level and score-level fusion of two latent AFIS can significantly boost the performance, which indicates that these two AFIS provide complementary information. Figs.  <ref> (a) and (b) show two examples that our latent AFIS can retrieve their true mates at rank-1 but the COTS AFIS cannot due to overlap between background characters and friction ridges. Figs. <ref> (c) and (d) show two failure cases of the proposed latent AFIS due to the broken ridges. The rank-1 accuracy of proposed latent AFIS on NIST SD27  is slightly higher than the algorithm proposed in <cit.> even though manually marked ROI was used in <cit.>.  


The five CMC curves on 449 latents  in WVU database are compared in  Fig. <ref> and the four CMC curves on 10,000 latents in N2N database are compared in  Fig. <ref>.  Both WVU and N2N databases were collected in laboratory.  The latents in these two latent databases are dry (ridges are broken), and are significantly from operational latents which were used for fine-tuning minutiae detection model and rolled prints which were used for training  Autoencoder for enhancement,  the minutiae detection model and enhancement model do not work well on WVU latent database. This explains why the performance of the proposed latent AFIS is lower than COTS latent AFIS. Fig. <ref> shows some examples where the enhancement model fails.  This indicates that additional dry fingerprints are needed for proposed training for deep learning based approaches. 


 


 
 











 














 §.§ Evaluation on MSP Latent Database


The CMC curves of the two latent AFIS and their two fusions on 1,200 latents from the MSP latent databases are shown in Fig. <ref>.  The overall performance of the proposed latent AFIS is better than COTS latent AFIS. Specifically, the rank-1 and rank-20 accuracies of the proposed latent AFIS are 2.1% and 3.2% higher than those of the COTS latent AFTS. By using score-level fusion, the rank-1 accuracy is improved by 4.8% to 78.1%. Fig. <ref> shows that three examples that the score-level fusion succeeds in finding their true mates at rank-1, but individual latent AFIS does not succeed.





 §.§ Evaluation on N2N Latent Database





The latent fingerprints collected during the Nail to Nail Fingerprint Challenge mimicked the type of data that is typically seen in criminal investigations.  A total of 30 activities (Table  <ref>), using a mixture of porous, semiporous, nonporous, and adhesive objects, were involved in the data collection. In addition to evaluate the overall performance on all latents, we analyze the  performance on each activity. The performances among two latent AFIS as well as their score-level and rank-level fusion fusion are comparison using rank-1 accuracy. See Fig. <ref>.  




































































































































§ SUMMARY

We present the design and prototype of an  end-to-end fully automated latent search system and benchmark its performance
against a leading COTS latent AFIS. The contributions of this paper are as follows:


  * Design and prototype  of the first fully automated end-to-end latent search system different curves.  

  * Autoencoder-based latent enhancement and minutiae detection. 

  * Efficient latent-to-reference print comparison.  One latent search against 100K reference prints can be completed in 100 seconds on a machine with Intel(R) Xeon(R) CPU E5-2680 v3@2.50GHz.


There are still a number of challenges we are trying to address listed below.


  * Improvement in automated cropping module. The current cropping algorithm does not perform well on dry latents in WVU and N2N databases.

  * Obtain additional operational latent databases for robust training for various modules in the search system.

  * Include additional features, e.g., ridge flow and ridge spacing, for similarity measure.





















  

§ ACKNOWLEDGMENTS


  

§ ACKNOWLEDGMENT




This research is based upon work supported in part by the
Office of the Director of National Intelligence (ODNI), Intelligence
Advanced Research Projects Activity (IARPA),
via IARPA R&D Contract No. 2018-18012900001. The
views and conclusions contained herein are those of the
authors and should not be interpreted as necessarily representing
the official policies, either expressed or implied,
of ODNI, IARPA, or the U.S. Government. The U.S. Government
is authorized to reproduce and distribute reprints
for governmental purposes notwithstanding any copyright
annotation therein.
































IEEEtran

















































