Database Reference
In-Depth Information
ridge ending. If we place a grid over a fingerprint, we can represent the fingerprint by the
set of grid squares in which minutiae are located.
Ideally, before overlaying the grid, fingerprints are normalized for size and orientation,
so that if we took two images of the same finger, we would find minutiae lying in exactly
the same grid squares. We shall not consider here the best ways to normalize images. Let
us assume that some combination of techniques, including choice of grid size and placing a
minutia in several adjacent grid squares if it lies close to the border of the squares enables
us to assume that grid squares from two images have a significantly higher probability of
agreeing in the presence or absence of a minutia than if they were from images of different
fingers.
Thus, fingerprints can be represented by sets of grid squares - those where their minutiae
are located - and compared like any sets, using the Jaccard similarity or distance. There are
two versions of fingerprint comparison, however.
• The
many-one
problem is the one we typically expect. A fingerprint has been
found on a gun, and we want to compare it with all the fingerprints in a large data-
base, to see which one matches.
• The
many-many
version of the problem is to take the entire database, and see if
there are any pairs that represent the same individual.
While the many-many version matches the model that we have been following for finding
similar items, the same technology can be used to speed up the many-one problem.
3.8.5
A LSH Family for Fingerprint Matching
We could minhash the sets that represent a fingerprint, and use the standard LSH technique
from
Section 3.4
. However, since the sets are chosen from a relatively small set of grid
points (perhaps 1000), the need to minhash them into more succinct signatures is not clear.
We shall study here another form of locality-sensitive hashing that works well for data of
the type we are discussing.
Suppose for an example that the probability of finding a minutia in a random grid square
of a random fingerprint is 20%. Also, assume that if two fingerprints come from the same
finger, and one has a minutia in a given grid square, then the probability that the other does
too is 80%. We can define a locality-sensitive family of hash functions as follows. Each
function
f
in this family
F
is defined by three grid squares. Function
f
says “yes” for two
fingerprints if both have minutiae in all three grid squares, and otherwise
f
says “no.” Put
another way, we may imagine that
f
sends to a single bucket all fingerprints that have minu-
tiae in all three of
f
's grid points, and sends each other fingerprint to a bucket of its own. In
