Patent Publication Number: US-9846801-B2

Title: Minutiae grouping for distorted fingerprint matching

Description:
FIELD 
     The present disclosure relates generally to fingerprint identification systems. 
     BACKGROUND 
     Pattern matching systems such as ten-print or fingerprint matching systems play a critical role in criminal and civil applications. For example, fingerprint identification is often used for identify and track suspects and in criminal investigations. Similarly, fingerprint verification is used in in civil applications to prevent fraud and support other security processes. 
     SUMMARY 
     Traditional fingerprint matchers normally conduct a two-stage matching process between a reference fingerprint and a search fingerprint. The first stage includes local matching of respective mated minutiae extracted from the reference fingerprint and the search fingerprint, followed by a global matching of the respective mated minutiae within the entire fingerprint. A similarity score indicating the likelihood of a match between the reference and search fingerprints is then computed based on the matching processes of the mated minutiae. However, such fingerprint matchers are often unable to identify some corresponding minutiae pairs within distorted regions of the search fingerprint due to differences in rotation and translation parameters associated with the distorted regions compared to the rotation and translation parameters associated with the best matched mated minutiae within non-distorted regions. Consequently, traditional fingerprint matchers often omit matching of minutiae within distorted regions, which often leads to inaccurate match results when areas of distorted regions are significantly large relative to the area of the entire fingerprint. 
     Accordingly, one innovative aspect described throughout this disclosure includes an iterative minutiae matching technique that initially groups mated minutiae within a list of all possible minutiae between a reference fingerprint and a search fingerprint, and then successively performs a geometric consistency check of the mated minutiae within the group. For instance, a subset of the list of all possible minutiae may be grouped to generate a group of globally aligned mated minutiae based on performing a global alignment procedure on the reference and search fingerprint, and grouping particular mated minutiae, within the list of all possible mated minutiae, that are determined to have similar rotation and translation parameters. The mated minutiae from the group of globally aligned minutiae may be removed from the list of all possible minutiae and inserted into a final minutiae list. The minutiae grouping process may be repeated for the updated list of all possible minutiae and after each successive round, the identified globally aligned mated minutiae may be inserted into the final minutiae list. In this regard, the iterative matching technique described throughout this specification enables improved identification of globally aligned mated minutiae within distorted regions, which may be used to subsequently improve the calculation of a similarity score between a reference fingerprint and a search fingerprint. 
     Implementations may include one or more of the following features. For example, a method for matching distorted fingerprints, the method implemented by an automatic fingerprint identification system including a processor, a memory coupled to the processor, an interface to a fingerprint scanning device, and a sensor associated with the fingerprint scanning device that indicates a fingerprint match. The method may include: selecting (i) a list of search minutia extracted from a search fingerprint, and (ii) a list of reference minutia extracted from a reference fingerprint; for each particular search minutia included in the list of search minutiae, identifying a corresponding reference minutia from the list of reference minutiae that is a closest matched minutia to the particular search minutia. 
     The method may include: generating a first list of locally matched minutiae between the search fingerprint and the reference fingerprint that includes each of the particular search minutiae, and each corresponding reference minutia that is the closest matched minutia to each of the particular search minutiae; identifying a first set of globally aligned minutiae pairs from among the first list of locally matched minutiae pairs based at least on performing a global alignment procedure on a first subset of the first list of locally matched minutiae pairs; computing (i) a first similarity score between the list of particular search minutiae and the list of corresponding reference minutiae within the first set of globally aligned minutiae pairs, and (ii) a center coordinate for the first set of globally aligned minutiae pairs. 
     The method may include: generating a second list of locally matched minutiae pairs, based at least on removing each of the particular search minutiae and each corresponding reference minutia that is the closest matched minutia to each of the particular search minutiae, that are included in the first set of globally aligned minutiae pairs, from the first list of locally matched minutiae pairs; identifying a second set of globally aligned minutiae pairs from among the second list of locally matched minutiae pairs based at least on performing the global alignment procedure on a second subset of the second list of locally matched minutiae pairs. 
     The method may include: determining that a number of globally aligned minutiae pairs within the second set of globally aligned minutiae pairs exceeds a threshold value; computing (i) a second similarity score between the list of particular search minutiae and the list of corresponding reference minutiae within the second set of globally aligned minutiae pairs, and (ii) a center coordinate for the second set of globally aligned minutiae pairs. 
     The method may include: identifying one or more additional sets of globally aligned minutiae pairs from among the second list of locally matched minutiae pairs based at least on successively performing the global alignment procedure on one or more additional subsets of the second list of locally matched minutiae pairs until the second list of locally matched minutiae pairs does not contain any particular search minutia, where each successive individual subset from the one or more additional subsets of the second list of locally matched minutia pairs includes particular search minutiae and the corresponding reference minutiae that are not included in a prior individual subset that was previously identified based at least on performing a prior global alignment procedure, and after performing the global alignment procedure on each successive individual subset, removing each of the particular search minutiae and each of the corresponding reference minutiae that are included in the prior individual subset from the second list of locally matched minutiae pairs. 
     The method may include: computing (i) additional similarity scores between the list of particular search minutiae and the list of corresponding reference minutiae within each of the one or more additional sets of globally aligned minutiae pairs of globally aligned minutiae pairs, and (ii) a center coordinate for each of the one or more additional sets of globally aligned minutiae pairs of globally aligned minutiae pairs; determining a geometric consistency metric between (i) the center coordinate for the first set of globally aligned minutiae pairs, (ii) the center coordinate for the second set of globally aligned minutiae pairs, and (iii) the center coordinates for each of the one or more additional sets of globally aligned minutiae pairs. 
     The method may include computing a final similarity score based at least on (i) combining the first similarity score, the second similarity score, and the additional similarity scores, and (ii) the geometric consistency metric; and providing, for output to the automatic fingerprint identification system, the final similarity score for use in a particular fingerprint matching operation between the search fingerprint and the reference fingerprint. 
     Other versions include corresponding systems, and computer programs, configured to perform the actions of the methods encoded on computer storage devices. 
     One or more implementations may include the following optional features. For example, in some implementations, generating a first list of locally matched minutiae pairs between the search fingerprint and the reference fingerprint includes: constructing, for each particular search minutia, a local geometric structure; and identifying, for each particular search minutia, a corresponding reference minutiae that is a closest matched minutia based at least on the local geometric structure for each particular search minutiae. 
     In some implementations, identifying a first set of globally aligned minutiae pairs includes: computing (i) a set of rotation parameters, and (ii) a set of translation parameters, based at least on closest locally matched minutiae pairs within the first list of locally matched minutiae; and aligning each particular search minutiae within the first subset of the first list of locally matched minutiae pairs to the corresponding reference minutia based at least on the set of rotation parameters and the set of translation parameters. 
     In some implementations, the computer-implemented method includes: identifying a set of best aligned minutiae pairs from among the first set of globally aligned minutiae pairs using the set of rotation parameters and the set of translation parameters for each of the search fingerprint and the reference fingerprint. 
     In some implementations, each of the first set of globally aligned minutiae pairs and the second set of globally aligned minutiae pairs include at least three matched minutiae pairs. 
     In some implementations, computing the final similarity score includes: determining that the center coordinate of a particular set of globally aligned minutiae pairs from among the one or more additional sets of globally aligned minutiae pairs is geometrically consistent with the center coordinates of each of the first set of globally aligned minutiae pairs; determining that the second set of globally aligned minutiae pairs of search fingerprint respective to the center coordinate of the particular set of globally aligned minutiae pairs is geometrically consistent with the center coordinates of each of the first set of globally aligned minutiae pairs and the second set of globally aligned minutiae pairs of the reference fingerprint and computing a revised similarity score based at least on combining the first similarity score, the second similarity score, and a set of revised additional similarity scores that does not include the similarity score of the particular set of globally aligned minutiae pairs. 
     In some implementations, the geometric consistency determination is based at least on one of: comparing a distance difference between any two centers of the search fingerprint and any two centers of reference fingerprint to a pre-defined parameter for the distance difference, or comparing an angle difference between any three centers of the search fingerprint and any three centers of reference fingerprint to a pre-defined parameter for the angle, where the angle of each center is calculated based on the average angles of the minutiae within each matched group. 
     In some implementations, the computer-implemented method includes: determining that the distance difference for a list of search minutiae within a particular set of globally aligned minutiae pair does not satisfy the pre-defined parameter for the distance difference; and excluding the list of search minutiae from the particular set of globally aligned minutiae pairs in response to determining that the distance difference for the list of search minutiae within the particular set of globally aligned minutiae pair does not satisfy the pre-defined parameter for the distance difference. 
     In some implementations, the computer-implemented method includes: determining that the angle difference for a list of search minutiae within a particular set of globally aligned minutiae pair does not satisfy the pre-defined parameter for the angle difference; and excluding the list of search minutiae from the particular set of globally aligned minutiae pairs in response to determining that the angle difference for the list of search minutiae within the particular set of globally aligned minutiae pair does not satisfy the pre-defined parameter for the angle difference. 
     In some implementations, the compute-implemented method includes: calculating a match similarity score based at least on the geometric consistency determination. 
     The details of one or more implementations are set forth in the accompanying drawings and the description below. Other potential features and advantages will become apparent from the description, the drawings, and the claims. 
     Other implementations of these aspects include corresponding systems, apparatus and computer programs, configured to perform the actions of the methods, encoded on computer storage devices. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1A  is a block diagram of an exemplary automatic fingerprint identification system. 
         FIG. 1B  is a block diagram of an exemplary feature extraction process. 
         FIG. 2  is an exemplary illustration of geometric relationships between a reference minutia and a neighboring minutia. 
         FIG. 3  is a graphical illustration of the relationships represented in an exemplary octant feature vector (OFV). 
         FIG. 4  is an exemplary process of generating an octant feature vector (OFV). 
         FIG. 5  is an exemplary process of calculating similarity between two minutiae. 
         FIG. 6  is an exemplary alignment process for a pair of fingerprints. 
         FIG. 7  is an exemplary minutiae matching process for a pair of fingerprints. 
         FIG. 8  is an exemplary process of distorted fingerprint matching. 
         FIGS. 9A-9B  illustrate exemplary distortions in a pair of mated fingerprints. 
         FIG. 10  is an exemplary minutiae grouping process for matching distorted fingerprints. 
         FIG. 11  is a graphical illustration of a minutiae grouping process performed with a set of exemplary minutiae. 
     
    
    
     In the drawings, like reference numbers represent corresponding parts throughout. 
     DETAILED DESCRIPTION 
     Contemporary fingerprint identification and verification technologies often exhibit inadequate performance for matching distorted fingerprints. For instance, there is no commonly known unified model to correct distortion within fingerprints since each print area within a single fingerprint may be uniquely distorted. In addition, because distorted regions of a fingerprint often include minutiae that have different rotation and translation parameters relative to the best matched mated minutiae in non-distorted regions, identification of mated minutiae within distorted regions is often challenging. In many instances, these minutiae are frequently not considered in calculated a similarity score between a distorted fingerprint to a non-distorted reference fingerprint. 
     In general, one innovative aspect described throughout this disclosure includes an iterative minutiae matching technique that initially groups mated minutiae within a list of all possible minutiae between a reference fingerprint and a search fingerprint, and then successively performs a geometric consistency check of the mated minutiae within the group. For instance, a subset of the list of all possible minutiae may be grouped to generate a group of globally aligned mated minutiae based on performing a global alignment procedure on the reference and search fingerprint, and grouping particular mated minutiae, within the list of all possible mated minutiae, that are determined to have similar rotation and translation parameters. The mated minutiae from the group of globally aligned minutiae may be removed from the list of all possible minutiae and inserted into a final minutiae list. The minutiae grouping process may be repeated for the updated list of all possible minutiae and after each successive round, the identified globally aligned mated minutiae may be inserted into the final minutiae list. In this regard, the iterative matching technique described throughout this specification enables improved identification of globally aligned mated minutiae within distorted regions, which may be used to subsequently improve the calculation of a similarity score between a reference fingerprint and a search fingerprint. 
     System Architecture 
       FIG. 1  is a block diagram of an exemplary automatic fingerprint identification system  100 . Briefly, the automatic fingerprint identification system  100  may include a computing device including a memory device  110 , a processor  115 , a presentation interface  120 , a user input interface  130 , and a communication interface  135 . The automatic fingerprint identification system  100  may be configured to facilitate and implement the methods described through this specification. In addition, the automatic fingerprint identification system  100  may incorporate any suitable computer architecture that enables operations of the system described throughout this specification. 
     The processor  115  may be operatively coupled to memory device  110  for executing instructions. In some implementations, executable instructions are stored in the memory device  110 . For instance, the automatic fingerprint identification system  100  may be configurable to perform one or more operations described by programming the processor  115 . For example, the processor  115  may be programmed by encoding an operation as one or more executable instructions and providing the executable instructions in the memory device  110 . The processor  115  may include one or more processing units, e.g., without limitation, in a multi-core configuration. 
     The memory device  110  may be one or more devices that enable storage and retrieval of information such as executable instructions and/or other data. The memory device  110  may include one or more tangible, non-transitory computer-readable media, such as, without limitation, random access memory (RAM), dynamic random access memory (DRAM), static random access memory (SRAM), a solid state disk, a hard disk, read-only memory (ROM), erasable programmable ROM (EPROM), electrically erasable programmable ROM (EEPROM), and/or non-volatile RAM (NVRAM) memory. The above memory types are exemplary only, and are thus not limiting as to the types of memory usable for storage of a computer program. 
     The memory device  110  may be configured to store a variety of data including, for example, matching algorithms, scoring algorithms, scoring thresholds, perturbation algorithms, fusion algorithms, virtual minutiae generation algorithms, minutiae overlap analysis algorithms, and/or virtual minutiae analysis algorithms. In addition, the memory device  110  may be configured to store any suitable data to facilitate the methods described throughout this specification. 
     The presentation interface  120  may be coupled to processor  115 . For instance, the presentation interface  120  may present information, such as a user interface showing data related to fingerprint matching, to a user  102 . For example, the presentation interface  120  may include a display adapter (not shown) that may be coupled to a display device (not shown), such as a cathode ray tube (CRT), a liquid crystal display (LCD), an organic LED (OLED) display, and/or a hand-held device with a display. In some implementations, the presentation interface  120  includes one or more display devices. In addition, or alternatively, the presentation interface  120  may include an audio output device (not shown), e.g., an audio adapter and/or a speaker. 
     The user input interface  130  may be coupled to the processor  115  and receives input from the user  102 . The user input interface  130  may include, for example, a keyboard, a pointing device, a mouse, a stylus, and/or a touch sensitive panel, e.g., a touch pad or a touch screen. A single component, such as a touch screen, may function as both a display device of the presentation interface  120  and the user input interface  130 . 
     In some implementations, the user input interface  130  may represent a fingerprint scanning device that is used to capture and record fingerprints associated with a subject (e.g., a human individual) from a physical scan of a finger, or alternately, from a scan of a latent print. In addition, the user input interface  130  may be used to create a plurality of reference records. 
     A communication interface  135  may be coupled to the processor  115  and configured to be coupled in communication with one or more other devices such as, for example, another computing system (not shown), scanners, cameras, and other devices that may be used to provide biometric information such as fingerprints to the automatic fingerprint identification system  100 . Such biometric systems and devices may be used to scan previously captured fingerprints or other image data or to capture live fingerprints from subjects. The communication interface  135  may include, for example, a wired network adapter, a wireless network adapter, a mobile telecommunications adapter, a serial communication adapter, and/or a parallel communication adapter. The communication interface  135  may receive data from and/or transmit data to one or more remote devices. The communication interface  135  may be also be web-enabled for remote communications, for example, with a remote desktop computer (not shown). 
     The presentation interface  120  and/or the communication interface  135  may both be capable of providing information suitable for use with the methods described throughout this specification, e.g., to the user  102  or to another device. In this regard, the presentation interface  120  and the communication interface  135  may be used to as output devices. In other instances, the user input interface  130  and the communication interface  135  may be capable of receiving information suitable for use with the methods described throughout this specification, and may be used as input devices. 
     The processor  115  and/or the memory device  110  may also be operatively coupled to the database  150 . The database  150  may be any computer-operated hardware suitable for storing and/or retrieving data, such as, for example, pre-processed fingerprints, processed fingerprints, normalized fingerprints, extracted features, extracted and processed feature vectors such as octant feature vectors (OFVs), threshold values, virtual minutiae lists, minutiae lists, matching algorithms, scoring algorithms, scoring thresholds, perturbation algorithms, fusion algorithms, virtual minutiae generation algorithms, minutiae overlap analysis algorithms, and virtual minutiae analysis algorithms. 
     The database  150  may be integrated into the automatic fingerprint identification system  100 . For example, the automatic fingerprint identification system  100  may include one or more hard disk drives that represent the database  150 . In addition, for example, the database  150  may include multiple storage units such as hard disks and/or solid state disks in a redundant array of inexpensive disks (RAID) configuration. In some instances, the database  150  may include a storage area network (SAN), a network attached storage (NAS) system, and/or cloud-based storage. Alternatively, the database  150  may be external to the automatic fingerprint identification system  100  and may be accessed by a storage interface (not shown). For instance, the database  150  may be used to store various versions of reference records including associated minutiae, octant feature vectors (OFVs) and associated data related to reference records. 
     Feature Extraction 
     In general, feature extraction describes the process by which the automatic fingerprint identification system  100  extracts a list of minutiae from each of reference fingerprint, and the search fingerprint. As described, a “minutiae” represent major features of a fingerprint, which are used in comparisons of the reference fingerprint to the search fingerprint to determine a fingerprint match. For example, common types of minutiae may include, for example, a ridge ending, a ridge bifurcation, a short ridge, an island, a ridge enclosure, a spur, a crossover or bridge, a delta, or a core. 
       FIG. 1B  is a block diagram of an exemplary feature extraction process  150 . As shown, after receiving an input fingerprint  104 , the automatic fingerprint identification system  100  initially identifies a set of features  112  within the fingerprint, generates a list of minutiae  114 , and extracts a set of feature vectors  116 . For instance, the automatic fingerprint identification system  100  may generate a list of minutia  114  for each of the reference fingerprint (or “reference record”) and a search fingerprint (or “search record”). 
     In some implementations, the feature vectors  116  may be described using feature vector that is represented by Mf i =(x i , y i , θ i ). As described, the feature vector Mf i  includes a minutia location that is defined by coordinate geometry such as (x i ,y i ), and a minutiae direction that is defined by the angle θ i ε[0,2π]). In other examples, further minutiae characteristics such as, quality, ridge frequency, and ridge curvature may also be used to describe feature vector Mf i . The extracted feature vectors may be used to generate octant feature vectors (OFVs) for each of identified minutia within the search and reference fingerprints. 
     Octant Feature Vector (OFV) Overview 
     The automatic fingerprint identification system  100  may compare the search and reference records based on initially generating feature vectors associated with minutiae that are extracted from the search and reference records, respectively. For instance, as described throughout this specification, in some implementations, octant feature vectors (OFVs) may be used to as feature vectors that define attributes of the extracted minutiae. However, in other implementations, other minutiae descriptors may be used. 
     OFVs encode geometric relationships between reference minutiae and the nearest neighboring minutiae to the reference minutiae in a particular sector (referred to as the “octant neighborhood”) of the octant. Each sector of the octant used in an OFV spans 45 degrees of a fingerprint region. The nearest neighboring minutiae may be assigned to one sector of the octant based on their orientation difference. The geometric relationship between a reference minutia and its nearest minutia in each octant sector may be described by relative features including, for example, distance between the minutiae and the orientation difference between minutiae. The representation achieved by the use of an OFV is invariant to transformation. 
     Pairs of reference minutiae and nearest neighboring minutiae may be identified as “mated minutiae pairs.” The mated minutiae pairs in a reference record and a search record may be identified by comparing the respective OFVs of minutiae extracted from the reference record and the search record. The transformation parameters may be estimated by comparing attributes of the corresponding mated minutiae. For example, the transformation parameters may indicate the degree to which the search record has been transformed (e.g., perturbed or twisted) as relative to a particular reference record. In other examples, the transformation parameters may be applied to verify that, for a particular pair of a reference record and a search record (a “potential matched fingerprint pair”), mated minutiae pairs exhibit corresponding degrees of transformation. Based on the amount of corresponding mated minutiae pairs in each potential matched fingerprint pair, and the consistency of the transformation, a similarity score may be assigned. In some implementations, the pair of potential matched fingerprint pairs with the highest similarity score may be determined as a candidate matched fingerprint pair. 
     The automatic fingerprint identification system  100  may calculate an OFV for each minutia that encodes the geometric relationships between the reference minutia and its nearest minutiae in each sector of the octant. For instance, the automatic fingerprint identification system  100  may define eight octant sectors and assigns the nearest minutiae to one sector of the octant based on the location of each minutiawithin the sectors. The geometric relationship between a reference minutia and its nearest minutia in each octant sector is represented by the relative features. For example, in some implementations, the OFV encodes the distance, the orientation difference, and the ridge count difference between the reference feature and the nearest neighbor features. Because the minutia orientation can flexibly change up to 45° due to the octant sector approach, relative features are independent from any transformation. 
     The automatic fingerprint identification system  100  may use the OFVs to determine the number of possible corresponding minutiae pairs. Specifically, the automatic fingerprint identification system  100  may evaluate the similarity between two respective OFVs associated with the search record and the file record. The automatic fingerprint identification system  100  may identify all possible local matching areas of the compared fingerprints by comparing the OFVs. The automatic fingerprint identification system  100  may also an individual similarity score for each of the mated OFV pairs. 
     The automatic fingerprint identification system  100  may cluster all OFVs of the matched areas with similar transformation effects (i.e., rotation and transposition) into an associated similar bin. Note that the precision of the clusters of the bins (i.e., the variance of the similar rotations within each bin) is a proxy for the precision of this phase. Automatic fingerprint identification system  100  therefore uses bins with higher numbers of matched OFVs (i.e., clusters with the highest counts of OFVs) for the first phase global alignment. 
     The automatic fingerprint identification system  100  may use the location and angle of each selected bin as the parameters of a reference point (an “anchor point”) to perform a global alignment procedure. More specifically, the automatic fingerprint identification system  100  may identify the global alignment based on the bins that include the greatest number of the global mated minutiae pairs, and the location and angle associated with each of those bins. Based on the number of global paired minutiae found and the total of individual similarity scores calculated for the corresponding OFVs within the bin or bins, the automatic fingerprint identification system  100  may identify the transformations (i.e., the rotations of the features) with the best alignment. 
     In a second phase, the automatic fingerprint identification system  100  performs a more precise pairing using the transformations with the best alignment to obtain a final set of the globally aligned minutiae pairs. In this phase, automatic fingerprint identification system  100  performs a pruning procedure to find geometrically consistent minutiae pairs with tolerance of distortion for each aligned minutiae set that factors in the local and global geometrical index consistency. By performing such alignment globally and locally, automatic fingerprint identification system  100  determines the best set of global aligned minutiae pairs. Automatic fingerprint identification system  100  uses the associated mini-scores of the global aligned pairs to calculate the global similarity score. Furthermore, automatic fingerprint identification system  100  factors in a set of absolute features of the minutiae, including the quality, ridge frequency, and the curvatures in the computation of the final similarity score. 
     OFV Generation 
     The automatic fingerprint identification system  100  may generate an octant feature vector (OFV) for each minutia of the features extracted. Specifically, as described above, the automatic fingerprint identification system  100  may generate OFVs encoding the distance and the orientation difference between the reference minutiae and the nearest neighbor in each of eight octant sectors. Alternately, the automatic fingerprint identification system  100  may generate feature vectors with different numbers of sectors. 
       FIG. 2  is an exemplary illustration  200  of geometric relationships between a reference minutia  210  and a neighboring minutia  220 . The geometric relationships may be used to construct a rotation and translation invariant feature vector that includes relative attributes (d ij , α ij ,β ij ) between the reference minutia  210  and the neighboring minutia  220 . 
     As depicted in  FIG. 2 , the automatic fingerprint identification system  100  may compute a Euclidean distance  230  between the reference minutia  210  and the neighboring minutia  220 , a minimum rotation angle  240  for the neighboring minutia, and a minimum rotation angle  250  for the reference minutia  210 . In addition, the automatic fingerprint identification system may compute a ridge count  260  across the reference minutia  210  and the neighboring minutia  220 . 
     Specifically, the rotation and translation invariant feature vector may be represented as vector 1 (represented below). In some implementations, an OFV is created to describe the geometric relationship between. Further, M i  represents a reference minutia and M j  represents a nearest neighbor minutiae in one of the octant sectors. The OFV for each sector may be described in the given vector from vector 1: 
     Vector 1: (d ij , α ij , β ij ),
         where d ij  denotes the Euclidean distance  230 ,   where α ij =λ(θ i ,θ j ) denotes the minimum rotation angle  240  required to rotate a line of direction θ i  in a particular direction (e.g., counterclockwise in  FIG. 2 ) to make the line parallel with a line of direction θ j , and   where β ij =λ(θ i ,∠(M i ,M j )) denotes the minimum rotation angle  250 , where ∠(M i ,M j ) denotes the direction from the reference minutia  210  to the neighboring minutia  220 , and where λ(a,b) denotes the same meaning as defined in α ij          

     Specifically, because each element calculated in the feature vector is a relative measurement between the reference minutia  210  and the neighboring minutia  220 , the feature vector is independent from the rotation and translation of the fingerprint. Elements  230 ,  240 , and  250  may be referred to as relative features and are used to compute the similarity between pair of reference minutia  210  and the neighboring minutia  220 . In some implementations, other minutiae features such as absolute features may additionally or alternatively be used by the automatic fingerprint identification system  100  to weight the computed similarity score between a pair of mated minutiae that includes reference minutia  210  and the neighboring minutia  220 . 
       FIG. 3  is a graphical illustration of the relationships represented in an exemplary octant feature vector (OFV)  300 . The OFV  300  may be generated for a reference minutia  310 , which corresponds to the reference minutia  210  as shown in  FIG. 2 . As shown, the OFV  300  represents relationships between the reference minutiae  310  and its nearest neighboring minutiae  322 ,  332 ,  342 ,  352 ,  362 ,  372 ,  382 , and  392  in sectors  320 ,  330 ,  340 ,  350 ,  360 ,  370 ,  380 , and  390 , respectively. However, the graphical illustration of OFV  300  does not depict the details of the geographic relationships, which are described within respect to  FIG. 2 . Although  FIG. 3  indicates a neighboring minutia within each octant sector, in some instances, there may be no neighboring minutiae within a particular sector. In such instances, the OFV for the particular sector without a neighboring minutia is set to zero. Otherwise, because the neighboring minutiae  322 ,  332 ,  342 ,  352 ,  362 ,  372 ,  382 , and  392  may not overlap with reference minutiae  310 , the OFV is greater than zero. 
       FIG. 4  is an exemplary process  400  of generating an octant feature vector (OFV). Briefly, the process  400  may include identifying a plurality of minutiae from the input fingerprint image ( 410 ), selecting a particular minutia from the plurality of minutiae ( 420 ), defining a set of octant sectors for the plurality of minutiae ( 430 ), assigning each of the plurality of minutiae to an octant sector ( 440 ), identifying a neighboring minutiae to the particular minutia for each octant sector ( 450 ), and generating an octant feature vector for the particular minutia ( 460 ). 
     In more detail, the process  400  may include the process may include identifying a plurality of minutiae from the input fingerprint image ( 410 ). For instance, the automatic fingerprint identification system  100  may receive the input fingerprint  402  and generate a list of minutiae  412  using the techniques described previously with respect to  FIG. 1B . 
     The process  400  may include selecting a particular minutia from the plurality of minutiae ( 420 ). For instance, the automatic fingerprint identification system  100  may select a particular minutia within the list of minutiae  412 . 
     The process  400  may include defining a set of octant sectors for the plurality of minutiae ( 430 ). For instance, the automatic fingerprint identification system  100  may generate a set of octant sectors  432  that include individual octant sectors k 0  to k 7  as shown in  FIG. 4 . The set of octant sectors  432  may be generated in reference to the particular minutia that is selected in step  420 . 
     The process  400  may include assigning each of the plurality of minutiae to an octant sector ( 440 ). For instance, the automatic fingerprint identification system  100  may assign each of the plurality of minutiae from the list of minutiae  412  into corresponding octant sectors within the set of octant sectors  432 . The assigned minutiae may be associated with the corresponding octant sectors in a list  442  that includes the number of minutiae that are identified within each individual octant sector. For example, as shown in  FIG. 4 , the exemplary octant sector k 1  has no identified minutiae, whereas the exemplary k 6  includes two identified minutiae within the octant sector. The graphical illustration  444  represents the locations of the plurality of minutiae, relative to the particular selected minutia, M i , within the individual octant sectors. 
     The process  400  may include identifying a neighboring minutia to the particular minutia for each octant sector ( 450 ). For instance, the automatic fingerprint identification system  100  may identify, from all the neighboring minutiae within each octant sector, the neighboring minutia that is the closest neighboring minutia based on the distance between each neighboring minutia and the particular selected minutia, M i . For example, for the octant sector k 6 , the automatic fingerprint identification system  100  may determine that the minutia, M 6  is the closest neighboring minutia based on the distance between M i  and M 6 . The closest neighboring minutiae for all of the octant sectors may be aggregated within a list of closest neighboring minutiae  452  that identifies each of the closest neighboring minutiae. 
     The process  400  may include generating an octant feature vector for the particular minutia ( 460 ). For instance, the automatic fingerprint identification system  100  may generate an octant feature vector  462 , based on the list of closest neighboring minutiae  452 , which includes a set of relative features such as the Euclidean distance  230 , the minimum rotation angle  240 , and the minimum rotation angle  250  as described previously with respect to  FIG. 2 . 
     As described above with respect to  FIGS. 2-4 , OFVs for minutiae may be used to characterize local relationships with neighboring minutiae, which are invariant to the rotation and translation of the fingerprint that includes the minutiae. The OFVs are also insensitive to distortion, since the nearest neighboring minutiae are assigned to multiple octant sectors in various directions, thereby allowing flexibility of orientation of up to 45°. In this regard, the OFVs of minutiae within a fingerprint may be compared against the OFVs of minutiae within another fingerprint (e.g., a search fingerprint) to determine a potential match between the two fingerprints. Descriptions of the general fingerprint matching process, and the OFV matching process are provided below. 
     Fingerprint Identification and Matching 
     In general, the automatic fingerprint identification system  100  may perform fingerprint identification and matching in two stages: (1) an enrollment stage, and (2) an identification/verification stage. 
     In the enrollment stage, an individual (or a “registrant”) has their fingerprints and personal information enrolled. The registrant may be an individual manually providing their fingerprints for scanning or, alternately, an individual whose fingerprints were obtained by other means. In some examples, registrants may enroll fingerprints using latent prints, libraries of fingerprints, and any other suitable repositories and sources of fingerprints. As described, the process of “enrolling” and other related terms refer to providing biometric information (e.g., fingerprints) to an identification system (e.g., the automatic fingerprint identification system  100 ). 
     The automatic fingerprint identification  100  system may extract features such as minutiae from fingerprints. As described, “features” and related terms refer to characteristics of biometric information (e.g., fingerprints) that may be used in matching, verification, and identification processes. The automatic fingerprint identification system  100  may create a reference record using the personal information and the extracted features, and save the reference record into the database  150  for subsequent fingerprint matching, verification, and identification processes. 
     In some implementations, the automatic fingerprint identification system  100  may contain millions of reference records. As a result, by enrolling a plurality of registrants (and their associated fingerprints and personal information), the automatic fingerprint identification system  100  may create and store a library of reference records that may be used for comparison to search records. The library may be stored at the database  150  associated. 
     In the identification stage, the automatic fingerprint identification system  100  may use the extracted features and personal information to generate a record known as a “search record”. The search record represents a source fingerprint for which identification is sought. For example, in criminal investigations, a search record may be retrieved from a latent print at a crime scene. The automatic fingerprint identification may compare the search record with the enrolled reference records in the database  150 . For example, during a search procedure, a search record may be compared against the reference records stored in the database  150 . In such an example, the features of the search record may be compared to the features of each of the plurality of reference records. For instance, minutiae extracted from the search record may be compared to minutiae extracted from each of the plurality of reference records. 
     As described, a “similarity score” is a measurement of the similarity of the fingerprint features (e.g., minutiae) between the search record and each reference record, represented as a numerical value to degree of similarity. For instance, in some implementations, the values of the similarity score may range from 0.0 to 1.0, where a higher magnitude represents a greater degree of similarity between the search record and the reference record. 
     The automatic fingerprint identification system  100  may compute individual similarity scores for each comparison of features (e.g., minutiae), and aggregate similarity scores (or “final similarity scores”) between the search record to each of the plurality of reference records. In this regard, the automatic fingerprint identification system  100  may generate similarity scores of varying levels of specificity throughout the matching process of the search record and the plurality of reference records. 
     The automatic fingerprint identification system  100  may also sort each of the individual similarity scores based on the value of the respective similarity scores of individual features. For instance, the automatic identification system  100  may compute individual similarity scores between respective minutiae between the search fingerprint and the reference fingerprint, and sort the individual similarity scores by their respective values. 
     A higher final similarity score indicates a greater overall similarity between the search record and a reference record while a lower final similarity score indicates a lesser over similarity between the search record and a reference record. Therefore, the match (i.e., the relationship between the search record and a reference record) with the highest final similarity score is the match with the greatest relationship (based on minutiae comparison) between the search record and the reference record. 
     Minutiae and OFV Matching 
     In general, the OFVs of minutiae may be compared between two fingerprints to determine a potential match between a reference fingerprint and a search fingerprint. The automatic fingerprint identification system  100  may compare the OFVs of corresponding minutiae from the reference fingerprint and the search fingerprint to compute an individual similarity score that reflects a confidence that the particular reference minutiae corresponds to the particular search minutiae that is being compared to. The automatic fingerprint identification system  100  may then compute aggregate similarity scores, between a list of reference minutiae and a list of search minutiae, based the values of the individual similarity scores for each minutiae. For instance, as described more particularly below, various types of aggregation techniques may be used to determine the aggregate similarity scores between the reference fingerprint and the search fingerprint. 
       FIGS. 5-7  generally describe different processes that may be used to during fingerprint identification and matching procedures. For instance,  FIG. 5  illustrates an exemplary process of calculating an individual similarity score between a reference minutia and a search minutia.  FIG. 6  illustrates an exemplary alignment process between two fingerprints using extracted minutiae from the two fingerprints, and  FIG. 7  illustrates an exemplary minutiae matching technique that may be employed after the alignment procedure represented in  FIG. 7 . As described with respect to  FIG. 8 , the processes represented in  FIGS. 5-7  may be used in conjunction during an exemplary distorted fingerprint matching process. 
     Referring to  FIG. 5 , a similarity determination process  500  may be used to compute an individual similarity score between a reference minutia  502   a  from a reference fingerprint, and a search minutia  502   b  from a search fingerprint. A reference OFV  504   a  and a search OFV  504   b  may be generated for the reference minutia  502   a  and the search minutia  504   b , respectively, using the techniques described with respect to  FIG. 4 . As shown, the search and reference OFVs  504   a  and  504   b  include individual octant sectors k 0  to k 7  as described as illustrated in  FIG. 3 . Each of the reference OFV  504   a  and the search OFV  504   b  may include parameters such as, for example, the Euclidian distance  230 , the minimum rotation angle  240 , and the minimum rotation angle  250  as described with respect to  FIG. 2 . As shown in  FIG. 5 , exemplary parameters  506   a  and  506   b  may represent the parameters for octant sector k 0  of the reference OFV  502   a  and the search OFV  502   b , respectively. 
     The similarity score determination may be performed by an OFV comparison module  520 , which may be a software module or component of the automatic fingerprint identification system  100 . In general, the similarity score calculation includes four steps. Initially, the Euclidian distance values of a particular octant sector may be evaluated ( 522 ). Corresponding sectors between the reference OFV  504   a  and the similarity OFV  504   b  may then be compared ( 524 ). A similarity score between a particular octant sector within the reference OFV  504   a  and its corresponding octant sector in the search OFV  504   b  may then be computed ( 526 ). Finally, the similarity scores for the between other octant sectors of the reference OFV  504   a  and the search OFV  504   b  may then be computed and combined to generate the final similarity score between the reference OFV  504   a  and the search OFV  504   b  ( 528 ). 
     With respect to step  522 , the similarity module  520  may initially determine if the Euclidian distance values within the parameters  506   a  and  506   b  are non-zero values. For instance, as shown in decision point  522   a , the Euclidean distance associated with the octant sector of the reference OFV  504   a , d RO , is initially be evaluated. If this value is equal to zero, then the similarity score for the octant sector k 0  is set to zero. Alternatively, if the value of d RO  is greater than zero, then the similarity module  520  proceeds to decision point  522   b , where the Euclidean distance associated with the octant sector of the reference OFV  504   a , d SO , is evaluated. If the value of d SO  is not greater than zero, then the OFV similarity module  520  evaluates the value of the Euclidean distance d S1 , which is included in an adjacent sector k 1  to the octant sector k 0  within the reference OFV  504   b . Although  FIG. 5  represents only one of the adjacent sectors being selected, because each octant sector includes two adjacent octant sectors as shown in  FIG. 3 , in other implementations, octant sector k 7  may also be evaluated. If the value of the Euclidean distance within the adjacent octant sector is not greater than zero, then the similarity module  520  sets the value of individual similarity score S RSO1 , between the octant sector k 0  of the reference OFV  504   a  and the octant sector k 1  of the reference OFV  504   b , to zero. 
     Alternatively, if the either the value of Euclidean distance d RO  within the octant sector k 0  of the reference OFV  504   a , or the Euclidean distance d S1  within the adjacent octant sector k 1  of the search OFV  504   b  is determined to be a non-zero value within the decision points  522   b  and  522   c , respectively, then the similarity module proceeds to step  524 . 
     In some instances, a particular octant vector may include zero corresponding minutiae within the search OFV  504   b  due to localized distortions within the search fingerprint. In such instances, where the corresponding minutiae may have drifted to an adjacent octant sector, the similarity module  520  may alternatively compare the features of the octant vector of the reference OFV  504   a  to a corresponding adjacent octant vector of the search OFV  504   b  as shown in step  524   b.    
     If proceeding through decision point  522   b , the similarity module  520  may proceed to step  524   a  where the corresponding octant sectors between the reference OFV  504   a  and the search OFV  504   b  are compared. If proceeding through decision point  522   c , the similarity module  620  may proceed to step  524   b  where the octant sector k 0  of the reference OFV  504   a  is compared to the corresponding adjacent octant sector k 1  the search OFV  504   b . During either process, the similarity module  520  may compute the difference between the parameters that are included within each octant sector of the respective OFVs. For instance, as shown, the difference between the Euclidean distances  230 , Δd, the difference between the minimum rotation angles  240 , Δα, and the difference between the minimum rotation angles  250 , Δβ, may be computed. Since these parameters represent geometric relationships between pairs of minutiae, the differences between them represent distance and orientation differences between the reference and search minutiae with respect to particular octant sectors. 
     In some implementations, dynamic threshold values for the computed feature differences may be used to handle nonlinear distortions within the search fingerprint in order to find mated minutiae between the search and reference fingerprint. For instance, the values of the dynamic thresholds may be adjusted to larger or smaller values to adjust the sensitivity of the mated minutiae determination process. For example, if the value of the threshold for the Euclidean distance is set to a higher value, than more minutiae within a particular octant sector may be determined to be a neighboring minutia to a reference minutiae based on the distance being lower than the threshold value. Likewise, if the threshold is set to a smaller value, then a smaller number of minutiae within the particular octant sector may be determined to be neighboring minutia based on the distance to the reference minutia being greater than the threshold value. 
     After either comparing the corresponding octant sectors in step  524   a  or comparing the corresponding adjacent octant sectors in step  524   b , the similarity module  520  may then compute an individual similarity score between the respective octant sectors in steps  526   a  and  526   b , respectively. For instance, the similarity score may be computed based on the values of the feature differences as computed in steps  524   a  and  524   b . For instance, the similarity score may represent the feature differences and indicate minutiae that are likely to be distorted minutiae. For example, if the feature differences between a reference minutiae and corresponding search minutia within a particular octant sector are close the dynamic threshold values, the similarity module  520  may identify the corresponding search minutia as a distortion candidate. 
     After computing the similarity score for either the corresponding octant sectors, or the corresponding adjacent sectors in steps  526   a  and  526   b , respectively, the similarity module  520  may repeat the steps  522 - 526  for all of the other octant sectors included within the reference OFV  504   a  and the search OFV  504   b . For instance, the similarity module  520  may iteratively execute the steps  522 - 526  until the similarity scores between each corresponding octant sector and each corresponding adjacent octant sector are computed for the reference OFV  504   a  and the search OFV  504   b.    
     The similarity module may then combine the respective similarity scores for each corresponding octant sectors and/or the corresponding adjacent octant sectors to generate a final similarity score between the reference minutia and the corresponding search minutia. This final similarity score is also referred to as the “individual similarity score” between corresponding minutiae within the search and reference fingerprints as described in other sections of this specification. The individual similarity score indicates a strength of the local matching of the corresponding OFV. 
     In some implementations, the particular aggregation technique used by the similarity module  522  to generate the final similarity score (or the “individual similarity score”) may vary. For example, in some instances, the final similarity score may be computed based on adding the values of the similarity scores for the corresponding octant sectors and the corresponding adjacent octant sectors, and normalizing the sum by a sum of a total number of possible mated minutiae for the reference minutia and a total of number of possible mated minutiae for the search minutia. In this regard, the final similarity score is weighted by considering the number of mated minutiae and the total number of possible mated minutiae. 
       FIG. 6  illustrates an exemplary alignment process  600  between a reference fingerprint and a search fingerprint. Briefly, the process  600  may initially compare a list of reference OFVs  604   a  associated with a list of reference minutiae  602   a  and a list of search OFVs  604   b  associated with a list of search minutiae  604   b , and generate a list of all possible mated minutiae  612 . A global alignment module  620  may then perform a global alignment procedure on the list of all possible mated minutia  612  to generate a clustered list of all possible mated minutiae  622 , and determine two best alignment rotations  622  for the search fingerprint relative to the reference fingerprint. A precision alignment module may then use the two best rotations  624  perform a second alignment procedure to generate a list that includes the best-aligned pair  632  for the plurality of bins, which are provided as outputs of the alignment process. 
     As described previously with respect to  FIG. 5 , the OFVs of corresponding minutiae within the reference fingerprint and the search fingerprint may be compared by the OFV comparison module  610  to generate the list of all possible mated minutiae  612 . As described, “mated minutiae” refer to a pair of minutiae that includes a particular reference minutia and a corresponding search minutia based at least on the OFV comparison performed by the OFV comparison module  610 , and the value of the individual similarity score between the two respective OFVs of the reference and search minutiae. The individual similarity score indicates a strength of the local matching of the corresponding OFV. In addition, the list of all possible mated minutiae  612  includes all of the minutiae within the octant sectors that are identified as neighboring minutiae to a particular reference minutia and have a non-zero similarity score, although additional mated minutiae may exist with similarity score values equal to zero. Although as shown in the FIG., the list of all possible minutiae  612  includes one search minutia per reference minutia, in some instances, multiple mated minutiae may exist within the list of all possible minutiae  612  for a single reference minutia. 
     The global alignment module  620  performs a global alignment process on the list of all possible mated minutiae  612 , which estimates a probable (or best rotation) alignment between the reference fingerprint and the search fingerprint based on comparing the angle offsets between the individual minutiae within the mated minutiae. For instance, the global alignment module  620  may initially compute an angle offset for each mated minutiae pair based on the individual similarity scores between a particular search minutia and its corresponding reference minutia. 
     Each of the mated minutiae within the list of all possible mated minutiae  612  may then be grouped into a histogram bin that is associated with a particular angle offset range. For instance, two mated minutiae pairs within the list of all possible mated minutiae  612  may be grouped into the same histogram bin if their respective individual similarity scores indicate a similar angular offset between the individual minutia within each mated minutiae pair. In some instances, the number of histogram bins for the list of all possible mated minutiae  612  is used to estimate a fingerprint quality score for the search fingerprint. For example, if the quality of the search fingerprint is excellent, then the angular offset among each of the mated minutiae within the list of all possible mated minutiae  612  should be consistent, and majority of the mated minutiae will be grouped into a single histogram bin. Alternatively, if the fingerprint quality is poor, then the number of histogram bins would increase, representing significant variations between the angular offset values between the mated minutiae within the list of all possible mated minutiae  612 . 
     In addition to grouping the mated minutiae into a particular histogram bin, the global alignment module  620  may determine a set of rigid transformation parameters, which indicate geometric differences between the reference minutiae and the search minutiae with similar angular offsets. The rigid transformation parameters thus indicate a necessary rotation of the search fingerprint at particular locations, represented by the locations of the minutiae, in order to geometrically align the search fingerprint to the reference fingerprint. Since the rigid transformation parameters are computed for all possible mated minutiae, the necessary rotation represents a global alignment between the reference fingerprint and the search fingerprint. The global alignment module  620  may then generate a clustered list of all possible mated minutiae, which groups the mated minutiae by the histogram bin based on the respective angle offsets, and includes a set of rigid transformation parameters. In some implementations, the histogram represented by the plurality of bins may be smoothened by a Gaussian function. 
     The global alignment module  620  may use the clustered list of all possible mated minutiae to determine two best rotations  624 . For instance, the two best rotations  624  may be determined by using the rigid transformation parameters to calculate a set of alignment rotations for the search fingerprint using each histogram bin as a reference point. Each alignment rotation may then be applied to the search fingerprint to generate a plurality of transformed search fingerprints that is individually mapped to each alignment rotation. For example, in some instances, the number of alignment rotations corresponds to the number of histogram bins generated for the list of all possible mated minutiae  612 . In such instances, the number of transformed search fingerprints generated corresponds to the number of histogram bins included in the cluster list of all possible mated minutiae  622 . Each set of transformed search fingerprints may then be compared to the reference fingerprint to determine the two best rotations  624 . For example, as described more particularly with respect to  FIG. 7 , each transformed search fingerprint may be compared to the reference fingerprint using a minutiae matching technique to determine which particular alignment rotations generate the greatest number of correctly matched minutiae between a particular transformed search fingerprint and the reference fingerprint. The global alignment module  620  may then extract the two best alignment rotations  624 , which are then used by the precision alignment module  630 . 
     In some implementations, different matching constraints may be used with the minutiae matching techniques to determine the two best alignment rotations  624 . 
     The precision alignment module  630  may then use the two best alignment rotations  624  to perform a precision alignment process that iteratively rotates individual minutiae within the search fingerprint around the two best alignment rotations  632  several times with small angle variations to obtain a more precise pairing between individual search minutiae and their corresponding reference minutiae. For example, in some, twelve rotations may be used with two degree angle variations. The minutiae that are associated with the precise pairing between the search fingerprint and the reference fingerprint are determined to be the list of best-aligned minutiae  632 , which are provided for output by the process  600 . The list of best-aligned minutiae  632  represent transformations of individual search minutiae within the search fingerprint that most closely pair with the corresponding reference minutiae of the reference fingerprint as a result of the global alignment and the precision alignment processes. 
       FIG. 7  illustrates an exemplary minutiae matching process  700 . The minutiae matching process  700  may be performed after the fingerprint alignment process  600  as described in  FIG. 6  to remove false correspondences included within a list of aligned minutiae that is outputted from alignment process. For instance, fingerprints from two fingers of an individual may share local structures, which can result in false correspondence minutiae between a search fingerprint of one finger and a reference fingerprint of another finger. To resolve this, the minutiae matching process  700  includes a two-stage pruning process to remove false correspondence minutiae pairs within a list of all possible mated minutiae. 
     Briefly, the process  700  may include a local geometric module  710  receiving a list of aligned minutiae  710 , and generating a modified list of all possible minutiae  712  that does not include false correspondence minutiae. A global consistency pairing module may then sort the modified list of all possible minutiae  712  by values of the respective individual similarity scores to generate a sorted modified list of all possible minutiae  722 . The global consistency pairing module  720  may remove minutiae pairs with duplicate indexes  724 , and group the list of mated minutiae based on conducting a global geometric consistency evaluation to generate a list of geometrically consistent groups  726 , which are then outputted with a top average similarity score from one of the geometrically consistent groups. 
     Initially, the local geometric module  710  may select the best-paired minutiae from the list of all possible mated minutiae. For instance, after aligned the search fingerprint and the reference fingerprint as described in  FIG. 6 , the local geometric module  710  may scan the list of all possible minutiae and identify the two minutiae pairs with the minimum orientation difference. 
     In some instances, the identification of the best-paired minutiae may additionally be subject to satisfying a set of constraints. For example, one constraint may be that the index of the first pair is different from that of the first pair. In other examples, the rigid transformation parameters of the two best-paired minutiae pairs may be compared to threshold values to ensure that the two identified pairs are geometrically consistent. 
     After identifying the two best-paired minutiae pairs, the local geometric module  710  may use the two best-paired minutiae pairs as reference pairs to remove other minutiae pairs from the list of all possible mated minutiae. In some instances, particular pairs may be removed if they satisfy one or more removal criteria based on the attributes of the two best paired minutiae pairs. For example, one constraint may be that if the minutiae index of a particular pair is the same as one of the best-paired minutiae pairs, then that particular pair may be identified as a duplicate within the list of all possible minutiae and removed as a false correspondence. In another example, a rotational constraint may be used to remove particular minutiae pairs that have a large orientation difference compared to the two best-paired minutiae pairs. In another example, distance constraints may be used to keep each particular minutiae pair within the list of all possible mated minutiae geometrically consistent with the two best-paired minutiae pairs. The updated list of minutiae pairs that is generated is the modified list of all possible mated minutiae  712 . 
     After the modified list of all possible mated minutiae is generated, the global consistency pairing module  720  may perform a global consistency pairing operation on the modified list of all possible mated minutiae  722  to generate the list of geometrically-consistent groups  726  (or “globally aligned mated minutiae”). For instance, the global consistency pairing module  720  may initially sort the list modified list of all possible mated minutiae  712  by the similarity score, and then scan the list and remove particular minutiae pairs  724  that have minutiae indexes that are similar to the minutiae pairs with the highest similarity scores in the sorted modified list of all possible mated minutiae  722 . 
     The global consistency pairing module  720  may then initialize a set of groups based on the number of reference minutiae included within the list. For instance, a group may be created for each reference minutia such that if there are multiple minutiae pairs within the list of sorted modified list of all possible minutiae  722  for a single reference minutia, the multiple minutiae pairs are included in the same group. In some instances, the global consistency pairing module  720  may additionally check the geometric consistency between each of the minutiae pairs within the same group and remove minutiae pairs that are determined not be geometrically consistent. The global consistency pairing module  720  may then compute an average similarity score for each group based on aggregating the individual similarity scores associated with each of the minutiae pairs within the group. 
     After computing the average similarity scores for each group, the global consistency pairing module  720  may then compare the average similarity scores between each group and select the group that has the highest average similarity score and then provide the list of minutiae that are included within the group for output of the process  700  and include the top average similarity score. 
     As describe above,  FIGS. 5-7  illustrate processes that are utilized by the automatic fingerprint identification system to process, analyze, and match individual minutiae from a search fingerprint to a reference fingerprint. As described in  FIG. 8 , these processes may be utilized within a matching operation for a distorted fingerprint to compute a final similarity score that indicates a confidence of a fingerprint match between a search fingerprint and a reference fingerprint. 
     Distorted Fingerprint Matching 
       FIG. 8  illustrates an exemplary distorted fingerprint matching operation  800 . The fingerprint matching operation  800  may be used to match a search fingerprint that may be nonlinearly distorted or may exhibit other types of errors that would like to cause inaccurate results using contemporary fingerprint matching technologies. The fingerprint matching operation  800  employs the principles and techniques described previously in  FIGS. 1-7  to reduce errors resulting from distortion. 
     The fingerprint matching operation  800  may include generating a list of invariant reference OFVs  802   a  for a list of reference minutiae  802   a , and a list of invariant search OFVs  804   b  for a list of search minutiae  802   a . For instance, as described in  FIG. 4 , the list of reference OFVs  804   a  and the list of search OFVs  804   b  may be generated by comparing each of the list of search minutiae  802   a  and the list of reference  802   b  to its neighboring minutiae within a set of octant sectors to achieve local distortion toleration. 
     An OFV comparison module may compare the respective search and reference OFVs  804   a  and  804   b , respectively, and generate a list of all possible mated minutiae  812 . For instance, as described in  FIGS. 6-7 , the list of all possible mated minutiae may include individual pairs of search minutiae and corresponding reference minutiae based on comparing the features included within the respective reference OFVs included in the list of reference OFVs  804   a  and the respective search OFVs included in the list of search OFVs  804   b . The list of reference OFVs  804   a  and the list of search OFVs  804   b  may include a set of absolute features that improve fingerprint matching for distorted fingerprint matching. For instance, the absolute features may include a direction, x-y coordinates, a quality score, a ridge frequency, and a curvature. In some implementations, the absolute features are included into the calculation of individual similarity scores as described in  FIG. 5  as weights to factor in impacts of distortions on the search fingerprint. 
     A global alignment module  820  may cluster all of the list of all possible mated minutiae pairs into a plurality of histogram bins, and subsequently perform a first global alignment procedure on each histogram bin to determine two best rotations  822  for the list of all possible mated minutiae  812 . For instance, as described in  FIG. 6 , the global alignment module  820  may initially cluster the list of all possible mated minutiae  812  based on a range of rotation angles, determine the two best rotations  822  based on comparing the each of the transformed search fingerprint under each rotation angle to the reference fingerprint. 
     A precision alignment module  830  may use the two best rotations  822  to identify a list of best-aligned minutiae  832  within the list of all possible mated minutiae. The precision alignment module  830  may also perform a two-step pruning procedure to generate a list of geometrically-consistent groups  834 . For instance, as described in  FIG. 7 , the two-step pruning procedure may include performing a local geometric pairing operation by removing false correspondence minutiae from the list of all possible mated minutiae. 
     A similarity module  840  may compute an individual similarity score for each mated minutiae pair within the list of geometrically-consistent groups  834 . For instance, as described in  FIG. 5 , the individual similarity score may computed based on aggregating single similarity scores between individual octant sectors of the respective OFVs of the search and reference minutia within a mated minutiae pair. The similarity score calculation may additionally include wrights based on the absolute features included within the respective OFVs for the search and reference minutiae included within the list of all possible mated minutiae. The list of individual similarity scores for all mated minutiae may then be aggregated to compute a final similarity score (or a “final similarity score”) between the reference fingerprint and the search fingerprint. In some instances, the final similarity score is computed based on selecting the maximum value of the individual similarity score for all of the mated minutiae. 
     In some implementations, a distortion flag may additionally be set after the final similarity score is computed based on the number of mated minutiae that are identified as distortion minutiae. In some instances, the number of distorted minutiae may be compared to a threshold value to determine whether the final similarity score may be severely distorted. In such instances, a distortion notification may be provided to an end-user of the automatic fingerprint identification system  100  indicating that the final similarity score may be distorted and requires manual verification or re-enrollment of either the search or reference fingerprints. 
       FIGS. 9A-9B  illustrate exemplary distortions in a pair of mated fingerprints. As shown, a search fingerprint  902  may have a corresponding reference fingerprint  904  with a distorted region  904   a . The search fingerprint  902  and the reference fingerprint  904  are taken from the same finger. The search fingerprint  902  and the reference fingerprint  904  may have corresponding minutiae lists  910  and  920 , respectively. The minutiae list  910  includes regions  912  and  914 , which correspond to the regions  922  and  924 , respectively within the minutiae list  920 . 
     As shown in  FIG. 9B , the regions  912  and  922  exhibit minimal distortion, indicated by the individual minutiae within the respective regions corresponding to similar locations within the regions  912  and  922 , and having near-identical rotations. As such, the minutiae included in the regions  912  and  922  may be identified as mated minutiae within a fingerprint matching operation between the reference fingerprint  902  and the reference fingerprint  904 . However, regions  914  and  924  do not correspond very well due to significant distortions within the region  924 , as shown within the reference fingerprint  904 . 
     Because there are distortions between the individual regions of the minutiae lists  910  and  920 , traditional minutiae matching techniques between the reference fingerprint would cluster only one of regions  912  and  914 . As described below in  FIGS. 10-11 , the minutiae grouping techniques as described throughout this specification enables iterative clustering and analysis of multiple regions, included those that include distortion, to improve the accuracy of a matching operation between a reference fingerprint and a search fingerprint. 
       FIG. 10  is an exemplary minutiae grouping process  1000  for matching distorted fingerprints. Briefly, the process  1000  may include generating a list of reference OFVs  1004   a  for a list of reference minutiae  1002   a  from a reference fingerprint, and a list of search minutiae  1004   a  from a list of search minutiae  1002   a  from a search fingerprint. Each reference OFV from the list of reference OFVs  1004   a  may be compared to the corresponding search OFV from the list of search OFVs  1004   b  using an OFV comparison module  1010 , which then generates a list of all possible mated minutiae (ML)  1012   a.    
     The OFV comparison module  1010  may select the leading pair from the ML  1012   a  and provide the ML  1012   a  along with the leading pair to the global alignment module  1020 . The global alignment module  1020  may use the leading pair from ML  1012   a  to generate a globally aligned group (M m )  1012   b , which is a subset of globally aligned mated minutiae from the ML  1012   a . The global alignment module  1020  may then compute a group similarity score (S m ) and a group geometric center (C m ), and then analyze geometric consistency of the globally aligned group. The geometric consistency analysis may consist of the decision points  1022 ,  1024  and  1028 , which may be iteratively performed in successive round until a condition specified by decision point  1028  is satisfied, when the process  1000  ends and a final similarity score  1030  for the ML  1012   a  may be calculated. 
     In more detail, the generation of the ML  1012   a  may be performed by the OFV comparison module using techniques described previously with respect to  FIGS. 6-7 . For instance, the ML  1012   a  may correspond to the list of all possible minutiae  712  as more particularly represented in  FIG. 7 . For example, the ML  1012   a  may be generated using a local matching technique that compares the respective OFVs of each reference minutia and the respective OFVs of each corresponding search minutia. A similarity score for each mated minutiae pair within the ML  1012   a  may additionally be computed to represent the strength of the local geometric consistency between each respective OFV. The OFV comparison module  1010  may then select the leading pair from the ML  1012   a  based on the similarity score, and the alignment parameters for the leading pair may be computed. 
     The global alignment module  1020  may generate the globally aligned group  1012   b  using techniques described with respect to  FIG. 7 . For instance, as described previously, the alignment parameters may be used to identify sets of mated minutiae within the ML  1012   a  that share similar alignment parameters. The globally aligned group includes a subset of mated minutiae from the ML  1012   a  that are share global alignment parameters as determined by the global alignment module  1020 . For instance, as shown in  FIG. 9B , the globally aligned group may represent groupings of individual minutiae inside a region within the fingerprint such as, for example, the regions  912  and  914 . 
     After generating the globally aligned group  1012   b , the global alignment module  1020  may compute a group similarity score (S m ) and a geometric center (C m ). In some instances, the group similarity score may represent an aggregate similarity score based on the individual similarity scores of each of the mated minutiae within a particular globally aligned group. For example, the group similarity score may be an average of all of the individual similarity scores. The geometric center may include a center coordinate of all the mated minutiae included in the globally aligned group  1012   b , and an average direction of all of the mated minutiae included in the globally aligned group  1012   b . In some instances, the center coordinate may be computed by averaging the respective x and y coordinates for all of the mated minutiae included in the globally aligned group  1012   b.    
     A global alignment module  1020  may then perform a geometric consistency check on the globally aligned group  1012   b  as described previously with respect to  FIG. 8 . For instance, as shown in decision point  1022 , the global alignment module  1020  may initially determine if there are more than two mated minutiae within the globally aligned group  1012 , and then, as shown in decision point  1024 , determine if the minutiae within the globally aligned group  1012   b  are geometrically consistent. For instance, if the globally aligned group  1012   b  includes less than two mated minutiae, or the mated minutiae within globally aligned group  1012   b  are determined to be geometrically inconsistent, the global alignment module  1020  may proceed to step  1026   b . Alternatively, if the globally aligned group  1012   b  satisfies the geometric consistency checks in decision points  1022 - 1024 , then the global alignment module  1020  may proceed to step  1026   b.    
     At step  1026   a , the global alignment module  1020  may initialize a final minutiae list (MF), and remove the mated minutiae from the globally aligned group  1012   b  from the ML  1012   a  to generate an updated ML (ML′)  1012   c  that does not include the mated minutiae from the globally aligned group  1012   b . In this regard, the updated ML′  1028   a  may be subsequently analyzed to through the successive iterations of the process  1000 , each of which generates a new updated ML list after step  1026   a  until the condition in decision point  1028  is satisfied. Alternatively, at step  1026   b , the global alignment module  1020  may remove the mated minutiae from the globally aligned group  1012   b  to generate the ML′  1012   c . In this instance, the mated minutiae from the globally aligned group  1012   b  are not added to MF because the mated minutiae from the globally aligned group  1012   b  are determined to not improve the matching process. 
     After performing either step  1026   a  or  1026   b , the global alignment module  120  proceeds to step  1028  where the size of the ML′  1028   a  may be evaluated to determine whether the process  1000  should be successively performed. For instance, if there are greater than two mated minutiae remaining in the ML′  1012   c , then the process  1000  may be repeated using the ML′  1012   c  as input to the global alignment module  1020 . For example,  FIG. 11  illustrates successive executions of the process  1000  using three sets of ML  1012   a . Alternatively, after a completion of a process  1000 , if there are less than two mated minutiae within the ML′  1012   c , then the global alignment module  1020  may compute the final similarity score  1030  for ML. For instance, the final similarity score  1030  may represent the similarity score between the reference fingerprint and the search fingerprint that include the list of reference minutiae  1002   a  and the list of search minutiae  1022   b , respectively. 
       FIG. 11  is a graphical illustration of an exemplary minutiae grouping process  1100  performed with a set of mated minutiae. The process  1100  depicts four successive minutiae grouping processes that may be performed for an exemplary search fingerprint  1102  that includes four regions M A , M B , M C  and M D . For instance, the regions M A , M B , and M C  and M D  may represent regions that include minutiae that are identified as having corresponding reference minutiae within a reference fingerprint. As shown, region M A  may include a single minutia, M 1 , region M B , may include three minutiae, M 2 , M 3 , and M 4 , region M C  may include four minutiae, M 5 , M 6 , M 7 , and M 8 , and region M D  may include three minutiae, M 9 , M 10 , and M 11 . 
     As described with respect to  FIGS. 6-7, and 10 , a list of all possible mated minutiae (ML)  1104   a  may be generated for the minutiae included in the search fingerprint  1102 . The ML  1104   a  may include individual similarity scores for each minutiae that represent a similarity between a respective search minutia and its corresponding reference minutia. As shown, minutia M 1  may be selected as the leading pair based on having the highest similarity score (e.g.,  0 . 89  in the FIG.). 
     As described in  FIG. 10 , a global alignment procedure may be performed using the ML  1104   a  to identify a first globally aligned group  1120  (M A ) for globally aligned minutiae within the region M A  of the search fingerprint  1102  based on the leading pair M 1 . As described with respect to step  1022  of  FIG. 10 , because the first globally aligned group  1120  includes less than two mated minutiae, a local consistency check is not performed on the minutiae included in the first globally aligned group  1120  (e.g., minutia pair M 1 ), and are consequently removed from the ML  1104   a . An updated list of all mated minutiae, ML′  1104   b , which corresponds to the updated list of mated minutiae after the first minutiae grouping process, may then be generated. As shown, because ML′  1104   b  includes greater than two mated minutiae, the process  1100  continues with a second process with ML′  1104   b  as the input. 
     A second global alignment procedure may be performed using ML′  1104   b  to generate a second globally aligned group  1140  that includes mated minutiae from the region M B  based on selecting M 3  as the leading pair. As shown, the second globally aligned group  1140  includes three mated minutiae (e.g., M 2 , M 3 , M 4 ) from the region M B  of the search fingerprint  1102 . A local geometric consistency check may be performed on the second globally aligned group  1140  to determine if the mated minutiae M 2 , M 3 , and M 4  are geometrically consistent. In the example shown, the second globally aligned group  1140  fails decision point  1024  as shown in  FIG. 10  because the individual mated minutiae are not locally geometrically consistent. For instance, the mated minutiae may be determined to be locally geometrically inconsistent if, for example, the difference between the x and y coordinates of the mated minutiae is greater than a threshold value. Since the second globally aligned group  1140  fails the local geometric consistency check, the minutiae within the second globally aligned group  1140  are then removed from the ML′  1104   b , to generated an updated list of mated minutiae, ML″  1104   c.    
     A third global alignment procedure may then be performed on the ML″  1104   c , which generates a third globally aligned group  1150  that includes four mated minutiae (e.g., M 5 , M 6 , M 7 , M 8 ) from the region M C  of the search fingerprint  1102  based on selected M 8  as the leading pair. As shown, a local geometric consistency check may be performed on the third globally aligned group  1150 , which indicates that the third globally aligned group  1150  satisfies the two requirements of decision points  1022  and  1024  as shown in  FIG. 10 . Because the third globally aligned group  1150  is determined to be locally geometrically consistent, a global center for the third globally aligned group  1150  may be computed, and the mated minutia within the third globally aligned group  1150  are added to a final minutiae list  1106   a , and removed from ML″  1104   c , which generates an updated mated minutiae list ML″  1104   d.    
     A fourth global alignment procedure may then be performed on the ML′″  1104   d  which generates a fourth globally aligned group  1160  that includes three mated minutiae (e.g., M 9 , M 10 , M 11 ) from the region M D  of the search fingerprint  1102  based on selected M 10  as the leading pair. As shown, the fourth globally aligned group  1160  includes three mated minutiae (e.g., M 2 , M 3 , M 4 ) from the region MB of the search fingerprint  1102 . As shown, a local geometric consistency check may be performed on the fourth globally aligned group  1160 , which indicates that the fourth globally aligned group  1160  satisfies the two requirements of decision points  1022  and  1024  as shown in  FIG. 10 . Because the fourth globally aligned group  1160  is determined to be locally geometrically consistent, a global center for the fourth globally aligned group  1160  may be computed, and the mated minutia within the fourth globally aligned group  1160  are added to a final minutiae list  1106   b , and removed from ML″  1104   d , which generates an updated mated minutiae list ML′″  1104   e.    
     As shown, since ML′″  1104   e  includes less than two mated minutiae, the conditions for terminating the process  1100 , shown as decision point  1028  in  FIG. 10 , is satisfied. The process  1100  may then include performing a global consistency check on the final minutiae list  1106   b  by computing a geometric consistency metric for the final minutiae list  1106   b . For instance, the geometric consistency metric may include comparing the geometric center coordinates for the respective globally aligned groups within the final minutiae list  1106   b  (e.g., groups  1150  and  1160  in the FIG.) and an angle associated with the coordinates of the global centers. In the example shown in  FIG. 11 , a global consistency metric may be determined between the center coordinate (X1, Y1) of the third globally aligned group  1150  and the center coordinate (X2, Y2) of the fourth globally aligned group  1160 . In some instances, the global consistency metric may additionally include an angle between the two respective coordinates. 
     In some implementations, after computing the global consistency metric, the mated minutiae from one or more globally aligned groups may be removed from the final minutiae list  1106   b  based on determining that the one or more globally aligned groups may not be globally consistent with the other globally aligned groups that are included within the final minutiae list  1106   b.    
     After computing the geometric consistency metric between the respective globally aligned groups within the final minutiae list  1106   b , a final similarity score may be computed for the final minutiae list  1106   b . For instance, the final similarity score may be represented as an aggregate of the individual similarity scores of the mated minutiae included within the final minutia list  1106   b  (e.g., M 5 , M 6 , M 7 , M 8 , M 9 , M 10 , and M 11 ). In some instances, the aggregation of the individual similarity scores may include adding weighting factors based on the number of minutiae included within the final minutiae list  1106   b , or other types of attributes that indicate whether the final score is likely to represent a match between the search fingerprint  1102  and its corresponding reference fingerprint. 
     In some instances, an additional geometric consistency check may be performed on the final list of minutiae  1180  to determine if the minutiae pairs included within the final minutiae list from successive minutiae grouping processes are also geometrically consistent with one another, which may be used as an indication of the accuracy of the final score. 
     Although not represented in  FIG. 11 , in some implementations, after determining that the mated minutiae within a particular globally aligned group are locally consistent, the process  1100  may include performing a global consistency check between the particular globally aligned group and the previously generated globally aligned groups that were added to the final minutiae list. For instance, in such implementations, the global consistency check may include comparing the global centers of the third globally aligned group  1150  and the fourth globally aligned group  1160  and determining whether the distance between the global centers is below an expected value. In some instances, where the global center distance is above or below an certain tolerance interval of the expected value, the particular globally aligned group may be determined to be globally inconsistent, and its corresponding mated minutiae may be removed from the final minutiae list. 
     It should be understood that processor as used herein means one or more processing units (e.g., in a multi-core configuration). The term processing unit, as used herein, refers to microprocessors, microcontrollers, reduced instruction set circuits (RISC), application specific integrated circuits (ASIC), logic circuits, and any other circuit or device capable of executing instructions to perform functions described herein. 
     It should be understood that references to memory mean one or more devices operable to enable information such as processor-executable instructions and/or other data to be stored and/or retrieved. Memory may include one or more computer readable media, such as, without limitation, hard disk storage, optical drive/disk storage, removable disk storage, flash memory, non-volatile memory, ROM, EEPROM, random access memory (RAM), and the like. 
     Additionally, it should be understood that communicatively coupled components may be in communication through being integrated on the same printed circuit board (PCB), in communication through a bus, through shared memory, through a wired or wireless data communication network, and/or other means of data communication. Additionally, it should be understood that data communication networks referred to herein may be implemented using Transport Control Protocol/Internet Protocol (TCP/IP), User Datagram Protocol (UDP), or the like, and the underlying connections may comprise wired connections and corresponding protocols, for example, Institute of Electrical and Electronics Engineers (IEEE) 802.3 and/or wireless connections and associated protocols, for example, an IEEE 802.11 protocol, an IEEE 802.15 protocol, and/or an IEEE 802.16 protocol. 
     A technical effect of systems and methods described herein includes at least one of: (a) increased accuracy in facial matching systems; (b) reduction of false accept rate (FAR) in facial matching; (c) increased speed of facial matching. 
     Although specific features of various implementations of the invention may be shown in some drawings and not in others, this is for convenience only. In accordance with the principles of the invention, any feature of a drawing may be referenced and/or claimed in combination with any feature of any other drawing. 
     This written description uses examples to disclose the invention, including the best mode, and also to enable any person skilled in the art to practice the invention, including making and using any devices or systems and performing any incorporated methods. The patentable scope of the invention is defined by the claims, and may include other examples that occur to those skilled in the art. Such other examples are intended to be within the scope of the claims if they have structural elements that do not differ from the literal language of the claims, or if they include equivalent structural elements with insubstantial differences from the literal language of the claims.