Sensor-to-sensor track correlation algorithms (1) Vector sort and (2) distance sort

Reference#: P01994

Fingerprint minutia matching involves finding sets of minutia from one fingerprint that can be rotated and translated so that they correspond to a set of minutia from the other print. Under ideal circumstances, if both prints are perfect and the minutia extraction is perfect, one might expect that the minutia sets could be rotated and translated so that each minutia point from one print coincides with a minutia point from the other print. On the other hand, if there is distortion, the matching minutia pairs may not coincide exactly, but may still be close to one another.

APL's distance sorting algorithm is a general purpose point-set matcher, but can be easily adapted to the specifics of a particular application. APL's Distance Sorting Algorithm for Matching Patterns relates to a pattern matching method; in particular, a method for matching these patterns by mathematically correlating sets of object state vectors contained in the respective patterns. This invention provides an algorithm for fingerprint matching and is robust to missing data and sensor errors, finding all the possible alignments given the allowable error.

In APL's distance sorting algorithm, "close" is defined in terms of an allowable error: two minutia points are "close" if the distance between them is less than the allowable error (allowable error is an adjustable parameter).

If all pairs are close, the match is said to be approximate. APL's algorithm finds approximate matches. If some region of one of the fingerprints is smudged, it may not be possible to find any match for the minutia in that region. In this case, APL's algorithm will leave these unmatched. In general, prints are not perfect and minutia extraction is not perfect, thus the minutia sets may be incomplete and/or contain "false minutia." APL's distance sorting algorithm finds those minutia subsets that can be rotated and translated into an approximate match as specified by the allowed error.

Patent Status: U.S. patent(s) 7379598 issued.

Dr. G. R. Jacobovitz
Phone: (443) 778-9899

Additional References:

Link to U.S. Patent and Trademark Office