This is a quick review of NIST NBIS biometric algorithms: the MINDTCT template extractor and the Bozorth3 matcher. NIST software is publicly available for download and it is apparently continuously developed to this day. I wrote this review before starting work on SourceAFIS project. I’ve incorporated many ideas from NBIS software into SourceAFIS. While there are some techniques in NBIS algorithms I haven’t used myself, I am quite skeptical of their value. I certainly have higher priority techniques on my priority list now. I am leaving this review here for future reference. Perhaps it will come handy one day. This post is a tight summary of the techniques used. NBIS was kind enough to provide highly detailed description in documents linked from this post. You can find plenty of information on NBIS website. See also my other review of Fingerprint recognition SDK.
MINDTCT template extractor
Described in great detail in publicly available part of NBIS documentation.
- overlapping windows – All image analysis is performed in overlapping windows where window width is longer than spacing between window centers.
- orientation detector – Detects waves in 16 orientations and 4 frequencies on grid points across the image. Frequencies are spaced by factor of 2.
- It first smooths ridges along current orientation and then performs sine/cosine convolution orthogonal to current orientation over short distance. 4 detected phases are obtained by squaring and adding sine/cosine convolutions. This gives 16×4 table of wave response values.
- For every frequency, orientation with strongest response is selected. Filter is used to remove weak absolute response as well as weak relative response. Relative response is maximum absolute response divided by mean response within that frequency.
- Frequencies which pass the filter are sorted by relative response and strongest one determines dominant orientation.
- If no dominant frequency can be selected, it is interpolated from neighbor regions.
- There are also some tricks regarding frequency response forks (probably around minutiae) and noise detected by highest frequency. I didn’t study these in detail.
- low quality map – This is used to clip non-fingerprint area and to reduce quality rating of minutiae in distorted parts of the image. It includes low contrast (absolute), areas with sub-threshold orientation signal, sharp changes in orientation. Generally absolute contrast determines minutia quality, but it is clipped by some amount based on other low quality indicators.
- oriented smoothing – Ridges are smoothed along their orientation as detected above.
- wave binarization – Local zero level is computed by averaging pixels along short line orthogonal to ridge orientation. Pixel is then binarized depending on whether its value is above or below this zero level.
- minutia extractor – NBIS uses odd minutia extraction. Instead of thinning, they look for minutia-like bit patterns in binarized image.
- minutia filter – This removes various errors: short ridges/valleys, close to invalid areas, branches at the end of ridge/valley, short branches from main ridge/valley, gaps in ridges/valleys, minutiae on too wide ridges/valleys, narrow bifurcations caused by pores.
- ridge counting – Ridge count between minutia and its closest neighbors is recorded.
Documented in great detail in export controlled part of NBIS documentation.
Honestly I don’t understand how this works. Documentation doesn’t describe the main part of the matcher. I looked at sources for an hour or so and couldn’t decipher what is going on. There are about 30 undocumented arrays used in the algorithm that would require data flow analysis to determine what is stored in them. Only then logic of the algorithm could begin to be understood. It could be done, but I am lazy to spend time on it.
Here’s what I got from documentation:
- edge graph – Edge here is a pair of minutiae from the same fingerprint. Bozorth3 uses edge graph for rotation and translation invariance. Two edges match if they have the same length and same angles on both minutiae (approximately of course).
- edge cluster – Edge cluster is a pair of matching edge trees from two fingerprints. Minutiae in the cluster are paired and all edges of the two trees match. Clusters are supposed to be constructed during matching process by semi-random traversal of edge graphs.
- cluster combination – Disjoint but compatible clusters are supposed to be combined for final score.
NBIS sources additionally include segmentation algorithm (too specialized to IAFIS data), image quality measurement, WSQ compression, and fingerprint pattern classification.