The next application is that of taking
a large collection of fingerprints and
finding which pairs
are from the same person.
Usually, fingerprint analysis is not
a many to many problem where we have to
find all matches at the same time.
Rather, we organize a database
of known fingerprints and
when a new fingerprint comes in, we tried
to match it to those we have seen before.
However, the LSH technique is still an
excellent way to organize the database so
that we have to look for matches to
the new fingerprint in only a few buckets.
To start, we should know a little about
how fingerprints are represented.
An image of a fingerprint is examined for
what are called minutiae.
These are particular locations where
something interesting happens to
the ridges that form a fingerprint.
Examples are where two ridges merge
into one or where a ridge ends.
So, the image of a fingerprint
is replaced by a set of
coordinates in the two dimensional
space where minutiae are located.
You place a grid over
each fingerprint image.
The grid must be scaled and
orientated properly so that if you have
two images of the same fingerprint,
perhaps one at a different angle or
a different size, the grids will overlap.
Then you represent each fingerprint by the
set of grid squares that contain minutiae.
Since some minutiae will be right on or
near a boundary, it is useful to
regard such minutiae as present in
the squares on both sides of the boundary.
So, it looks like we have reduced the
problem of finding matching fingerprints
to, to the problem of finding similar
sets of grid squares that have minutiae.
The problem is that the resulting
matrix is not sparse.
The grid cannot be too fine or
it will be unclear where minutiae belong.
And as a result,
the matrix's rows are the grid squares and
its columns or
the fingerprints sets will not be sparse.
That means min hashing
will not work very well.
Each min hash will have relatively
few different values, so we
don't get a good distribution into a large
number of buckets when we do the LSH.
We're going to have to twist things
a little bit to get LSH to work.
So before proceeding to
the solution here's a picture of
what minutiae look like.
This is a case where two
ridges merge into one and
the entire fingerprint has
been overlayed with a grid.
It appears the point of merger
lies within this grid square.
So, we add that square to the set
representing the fingerprint.
However, we might also want to add
the squares that are very close to
the exact point of merger, because in
another image of the same fingerprint,
the grid might be shifted
slightly to the left or down.
Remember that we represent fingerprints by
sets of grid squares, those of minutiae.
We could minhash these sets but
there is no need to.
The universal set is the set of grid
squares and the grid is not too fine, so
there might be hundreds or
at most thousands of squares in the grid.
We can best represent each set by bit
vector with one position for each square.
The ones represents square with minutiae.
And if there, if there are, say, 1,000
grid squares and each bit-vector takes 125
bites that's much less space than, say,
a vector of 100 integer min hash values.
For every LSH, if we pick some
member of sets of grid squares or
components of the bit-vectors
that represent fingerprints.
In our example, we'll use 1,024
sets of three grid squares each,
which seems to be a good choice.
For each set of three squares,
we look at all the prints that have
minutiae in each of these three squares.
In a sense we are throwing
fingerprints into buckets but
each set of three squares
corresponds to one bucket.
And unlike a hash function, a fingerprint
can be placed in many buckets.
In fact, it would be normal for a print
to be placed in several buckets this way.
To see why the numbers we proposed makes
sense, let's look at a typical situation.
We'll suppose that approximately
20% of the squares hold minutiae.
Also, suppose if two fingerprints
represent the same finger,
then at least 80 percent of the squares
with minutiae from one also have
minutiae from the other.
The fact that we place
minutiae in nearby squares if
they are at the boundary helps
make this assumption true.
Let's see what it takes for the bucket
corresponding to a set of three squares to
receive two different fingerprints.
First, if the fingerprints
come from different fingers,
then the probability that both prints
are placed in this bucket is really tiny.
For each finger, each fingerprint has
a 20% chance of having minutiae in each of
the, of the squares.
So the chance of it hitting
all three is 0.2 cubed.
And for both fingerprints to hit,
the probability is the square of that.
That is 0.2 to the sixth power,
or .000064.
Now let's look at two fingerprints
that come from the same finger.
The probability of both being in
a given bucket is much higher.
The reason is that there's a lot of
correlation between the buckets that will
contain these prints.
To start, for any given grid scare
the probability that the first print
has some minutia there is 0.2.
And given that it does, the probability
that the other does as well is 0.8.
We need to raise 0.2 times 0.8 to
the third power, because there
are three squares, each of which need to
hold minutiae from both of the prints.
The result is about four tenths of 1%.
Still really tiny, but
64 times larger than the probability if
the prints come from different fingers.
But remember,
we have 1,024 sets of three squares each.
In order for
a pair of prints to be a candidate pair,
we have only to find them together
in one of these 1,024 buckets.
The probability of that happening
at least once is 98.5%.
You can do the math if you like, but
there's an outline on the slide.
That means there are only
1.5% false negatives.
On the other hand, the same calculation
for a pair of fingerprints that comes from
different fingers is this, and it gives
them a much smaller value of .063.
That is,
there will be only 6.3% false positives.
That's still quite expensive.
It means that 6.3% of all
pairs need to be checked for
similarity when almost all
of them will not be similar.
On the other hand,
we did reduce our work by a factor of 15.
And by using a larger number of
sets of squares and perhaps four or
five squares per set,
we can reduce the false positive rate
substantially while still keeping
the false negative rate low.