MegaMatcher

Large Scale Automatic Biometric Identification System

Intro |  Why MegaMatcher? |  Algorithm |  Specifications |  Demo |  Related

In the last years the demand for large national scale biometrical systems has increased extremely. Many countries, including U.S.A., European countries and others include biometrical data into passports, ID cards, visas and other documents. A large number of applications, such as border crossing, elections control systems, verification of credit cards transactions, traffic control and others become possible to implement with large-scale Automatic Biometrical Identification Systems.

Such large scale systems have a number of special requirements, which are different from those for small or middle scale biometrical systems:

• The system must perform reliable identification with large databases.
• The system must show high productivity and efficiency, which correspond its scale:
  
  • System scalability is important, as the system might be extended in the future, so high productivity level should be kept by adding new units to the existing system.
  • Daily number of identification requests could be very high.
  • Identification request should be processed in a very short time (ideally – in real time), thus high computational power is required.
  • Support for large databases (tens or hundreds millions of fingerprints) is required.
  • General system robustness. The system must be tolerant to hardware failures, as even temporary pauses in its work may cause big problems taking into account the application size.
• The system must support major biometrical standards. This should allow using system generated templates or databases with the systems from other vendors and vice versa.
• The system must be able to match flat (plain) fingerprints with rolled fingerprints, as many institutions collect rolled fingerprint databases.
• The system must be able to work in the network, as in most cases client workstations are remote from the server with the central database.

Despite all these requirements, the system price should be as low as possible. Many existing AFIS (Automatic Fingerprint Identification Systems) are specialized for criminalistics or other particular applications and are quite expensive. Neurotechnologija offers a system, which meets all the requirements mentioned above, for a competitive price.

 To the top

Why MegaMatcher?

Neurotechnologija has an experience in collaborating with many biometrical system integrators, which have been developing large-scale biometrical systems. Referring to their requirements, Neurotechnologija has developed the MegaMatcher technology, intended for large scale biometrical system integrators. MegaMatcher has a set of specific features, which make it very attractive for large-scale AFIS developers:

• Reliability. Neurotechnologija has developed a completely new algorithm to introduce it in the MegaMatcher. This algorithm allows to achieve high reliability in large-scale applications.
  

  Cross Match Verifier 300 Click to enlarge

  Identix DFR 2090 Click to enlarge

  Receiver operating curves (ROCs), obtained in testing with Cross Match Verifier 300 and Identix DFR 2090 scanners' databases, compare MegaMatcher (red) and VeriFinger 4.2 (green) reliability under the same conditions. These ROCs show that MegaMatcher provides high reliability for large-scale systems.
• Matching speed. MegaMatcher is able to match from 9,000 to 60,000 fingerprints per second using stand-alone PC. The matching speed could be significantly increased by using the PC cluster (see scheme below).
• MegaMatcher includes computer cluster software for performing parallel matching, which allows to reach high productivity and efficiency:
  • The effective matching speed increases proportionally to the number of cluster's nodes and can be scalable to achieve the necessary system performance. For example, a cluster with 10 nodes is able to match up to 600,000 fingerprints per second, a cluster with 100 nodes – up to 6 millions fingerprints per second etc. Such scalable architecture allows to keep up the fast system's response if its size becomes larger.
  • Large number of identification requests could be processed by the cluster. Suppose, there is a database with 10 million fingerprints and a cluster of 100 nodes (PCs with 3GHz CPU). Depending on the problem this cluster will be able to process from 8,000 to 50,000 requests per day with the given database.
  • Fast request processing. The cluster's architecture allows to scale it to achieve real-time processing of the identification request.
  • The cluster is able to handle databases of a practically unlimited size.
  • Computer cluster is fault-tolerant, so in case of cluster element's fault, the matching speed slightly decreases, but the cluster's work remains uninterrupted.
• Megamatcher supports biometric standards: ANSI/NIST ITL-1-2000 and ANSI/INCIST 378 2004 are supported. Therefore, MegaMatcher fingerprint templates could be exported to another identification system and vice versa. Additionally, MegaMatcher supports WSQ fingerprint image storage format.
• The system allows to match rolled and flat fingerprints between themselves. Usually conventional "flat" fingerprint identification algorithms perform matching between flat and rolled fingerprints less reliably due to the specific deformations of rolled fingerprints. MegaMatcher allows to match flat-flat, flat-rolled or rolled-rolled fingerprints with high reliability.
• MegaMatcher includes network support, as components of MegaMatcher are intended to be distributed on the network.
• Independent performance evaluation. One mode of MegaMatcher uses an algorithm, which has been tested in the FpVTE 2003. After participation in FpVTE a completely new, more reliable algorithm was developed and included into MegaMatcher SDK as the main algorithm.
• Effective price/performance ratio. MegaMatcher uses PC and can work with Windows and Linux OS. This configuration provides the most price/performance effective computational units for all components of the system. Therefore, developing with MegaMatcher SDK means that the system price will be relatively low for both software and hardware parts.

Scheme of AFIS, based on MegaMatcher

 To the top

Algorithm

MegaMatcher uses a completely new fingerprint identification algorithm, which has been specially designed for large-scale identification problems. The algorithm follows the commonly accepted matching scheme, which uses a set of specific fingerprint points (minutiae).

MegaMatcher contains many proprietary algorithmic solutions. Part of them was specially developed for MegaMatcher, and part was inherited from VeriFinger algorithm. Some of these solutions are listed below:

• A fault-tolerant computer cluster technology was developed for performing parallel fingerprint matching. The cluster technology allows to increase the matching speed significantly as well as handle large databases and process a large number of identification requests.
• MegaMatcher is tolerant to fingerprint translation, rotation and deformation. It uses a proprietary fingerprint matching algorithm, which currently enables to match from 9,000 to 60,000 fingerprints per second and identify fingerprints even if they are rotated, translated and have deformations.
• MegaMatcher algorithm is able to match rolled fingerprints, flat fingerprints, and also rolled with flat between themselves. Due to the specific scanning technique (rolling from nail to nail) rolled fingerprints usually have much bigger deformation than those scanned using the "flat" technique. MegaMatcher matches rolled fingerprints very well, as it is tolerant to fingerprint deformations.
• MegaMatcher does not require the presence of the fingerprint core or delta points in the image, and can recognize a fingerprint from any part of it.
• MegaMatcher can use the database entries, which were pre-sorted using certain global features. Fingerprint matching is performed first with the database entries having global features most similar to those of the test fingerprint. If matching within this group yields no positive result, then the next record with most similar global features is selected, and so on, until the matching is successful or the end of the database is reached. In most cases there is a fairly good chance that the correct match will be found already at the beginning of the search. As a result, the number of comparisons required to achieve fingerprint identification decreases drastically, and the effective matching speed increases correspondingly.
  
• Adaptive image filtration algorithm allows to eliminate noises, ridge ruptures and stuck ridges, and extract minutiae reliably even from poor quality fingerprints, with processing time of less than 1 second (all times are given for Pentium 4, 3 GHz processor).

 To the top

Technical specifications

Other specifications of the algorithm are presented below. These parameters were determined for a PC with 3 GHz Pentium 4 processor:

 To the top

Demo

MegaMatcher demo application is designed for evaluation of MegaMatcher fingerprint recognition algorithm on stand-alone PC. The demo is a Windows 9x/ME/NT/2000/XP application that enrolls and identifies fingerprints from Cross Match Verifier 300 USB, Identix DFR2090, DigitalPersona U.are.U (U.are.U Integrator Gold 2.3 is required), SecuGen Hamster III, BiometriKa FX 2000, Startek FM200, Tacoma CMOS and STMicroelectronics TCRU1C scanners, LighTuning LTT-C500 and Atmel FingerChip sensors, TIFF, BMP and WSQ image files. Demo also allows to calculate receiver operation curves (ROC) with custom fingerprint databases.
MegaMatcher demo application is available for downloading.

MegaMatcher SDK trial is also available for downloading.

 To the top

Related products

MegaMatcher SDK is based on MegaMatcher algorithm.

 To the top