1
00:00:00,220 --> 00:00:03,680
The next application is that of taking
a large collection of fingerprints and

2
00:00:03,680 --> 00:00:05,820
finding which pairs
are from the same person.

3
00:00:07,550 --> 00:00:11,890
Usually, fingerprint analysis is not
a many to many problem where we have to

4
00:00:11,890 --> 00:00:13,520
find all matches at the same time.

5
00:00:15,150 --> 00:00:17,910
Rather, we organize a database
of known fingerprints and

6
00:00:17,910 --> 00:00:21,910
when a new fingerprint comes in, we tried
to match it to those we have seen before.

7
00:00:23,500 --> 00:00:27,260
However, the LSH technique is still an
excellent way to organize the database so

8
00:00:28,600 --> 00:00:33,280
that we have to look for matches to
the new fingerprint in only a few buckets.

9
00:00:33,280 --> 00:00:37,460
To start, we should know a little about
how fingerprints are represented.

10
00:00:37,460 --> 00:00:40,549
An image of a fingerprint is examined for
what are called minutiae.

11
00:00:42,080 --> 00:00:45,600
These are particular locations where
something interesting happens to

12
00:00:45,600 --> 00:00:47,660
the ridges that form a fingerprint.

13
00:00:47,660 --> 00:00:52,020
Examples are where two ridges merge
into one or where a ridge ends.

14
00:00:52,020 --> 00:00:54,660
So, the image of a fingerprint
is replaced by a set of

15
00:00:54,660 --> 00:00:59,290
coordinates in the two dimensional
space where minutiae are located.

16
00:00:59,290 --> 00:01:02,350
You place a grid over
each fingerprint image.

17
00:01:02,350 --> 00:01:03,700
The grid must be scaled and

18
00:01:03,700 --> 00:01:07,530
orientated properly so that if you have
two images of the same fingerprint,

19
00:01:07,530 --> 00:01:12,190
perhaps one at a different angle or
a different size, the grids will overlap.

20
00:01:12,190 --> 00:01:17,570
Then you represent each fingerprint by the
set of grid squares that contain minutiae.

21
00:01:19,240 --> 00:01:23,480
Since some minutiae will be right on or
near a boundary, it is useful to

22
00:01:23,480 --> 00:01:29,210
regard such minutiae as present in
the squares on both sides of the boundary.

23
00:01:29,210 --> 00:01:32,670
So, it looks like we have reduced the
problem of finding matching fingerprints

24
00:01:32,670 --> 00:01:37,100
to, to the problem of finding similar
sets of grid squares that have minutiae.

25
00:01:38,130 --> 00:01:42,150
The problem is that the resulting
matrix is not sparse.

26
00:01:42,150 --> 00:01:47,710
The grid cannot be too fine or
it will be unclear where minutiae belong.

27
00:01:47,710 --> 00:01:51,620
And as a result,
the matrix's rows are the grid squares and

28
00:01:51,620 --> 00:01:54,900
its columns or
the fingerprints sets will not be sparse.

29
00:01:54,900 --> 00:01:57,930
That means min hashing
will not work very well.

30
00:01:59,611 --> 00:02:03,100
Each min hash will have relatively
few different values, so we

31
00:02:03,100 --> 00:02:07,390
don't get a good distribution into a large
number of buckets when we do the LSH.

32
00:02:08,500 --> 00:02:11,920
We're going to have to twist things
a little bit to get LSH to work.

33
00:02:13,900 --> 00:02:16,780
So before proceeding to
the solution here's a picture of

34
00:02:16,780 --> 00:02:18,800
what minutiae look like.

35
00:02:18,800 --> 00:02:22,060
This is a case where two
ridges merge into one and

36
00:02:22,060 --> 00:02:25,120
the entire fingerprint has
been overlayed with a grid.

37
00:02:25,120 --> 00:02:31,050
It appears the point of merger
lies within this grid square.

38
00:02:31,050 --> 00:02:34,130
So, we add that square to the set
representing the fingerprint.

39
00:02:36,490 --> 00:02:40,160
However, we might also want to add
the squares that are very close to

40
00:02:40,160 --> 00:02:44,570
the exact point of merger, because in
another image of the same fingerprint,

41
00:02:44,570 --> 00:02:48,290
the grid might be shifted
slightly to the left or down.

42
00:02:48,290 --> 00:02:52,230
Remember that we represent fingerprints by
sets of grid squares, those of minutiae.

43
00:02:54,040 --> 00:02:57,200
We could minhash these sets but
there is no need to.

44
00:02:57,200 --> 00:03:02,110
The universal set is the set of grid
squares and the grid is not too fine, so

45
00:03:02,110 --> 00:03:05,260
there might be hundreds or
at most thousands of squares in the grid.

46
00:03:06,430 --> 00:03:11,440
We can best represent each set by bit
vector with one position for each square.

47
00:03:11,440 --> 00:03:13,480
The ones represents square with minutiae.

48
00:03:14,710 --> 00:03:20,700
And if there, if there are, say, 1,000
grid squares and each bit-vector takes 125

49
00:03:20,700 --> 00:03:27,360
bites that's much less space than, say,
a vector of 100 integer min hash values.

50
00:03:27,360 --> 00:03:30,900
For every LSH, if we pick some
member of sets of grid squares or

51
00:03:30,900 --> 00:03:34,470
components of the bit-vectors
that represent fingerprints.

52
00:03:34,470 --> 00:03:38,354
In our example, we'll use 1,024
sets of three grid squares each,

53
00:03:38,354 --> 00:03:40,080
which seems to be a good choice.

54
00:03:41,640 --> 00:03:43,890
For each set of three squares,

55
00:03:43,890 --> 00:03:47,950
we look at all the prints that have
minutiae in each of these three squares.

56
00:03:49,550 --> 00:03:53,680
In a sense we are throwing
fingerprints into buckets but

57
00:03:53,680 --> 00:03:57,018
each set of three squares
corresponds to one bucket.

58
00:03:57,018 --> 00:04:01,550
And unlike a hash function, a fingerprint
can be placed in many buckets.

59
00:04:01,550 --> 00:04:05,560
In fact, it would be normal for a print
to be placed in several buckets this way.

60
00:04:05,560 --> 00:04:10,915
To see why the numbers we proposed makes
sense, let's look at a typical situation.

61
00:04:10,915 --> 00:04:14,819
We'll suppose that approximately
20% of the squares hold minutiae.

62
00:04:17,040 --> 00:04:20,105
Also, suppose if two fingerprints
represent the same finger,

63
00:04:20,105 --> 00:04:25,020
then at least 80 percent of the squares
with minutiae from one also have

64
00:04:25,020 --> 00:04:26,990
minutiae from the other.

65
00:04:26,990 --> 00:04:30,140
The fact that we place
minutiae in nearby squares if

66
00:04:30,140 --> 00:04:34,030
they are at the boundary helps
make this assumption true.

67
00:04:34,030 --> 00:04:37,670
Let's see what it takes for the bucket
corresponding to a set of three squares to

68
00:04:37,670 --> 00:04:39,160
receive two different fingerprints.

69
00:04:40,730 --> 00:04:43,050
First, if the fingerprints
come from different fingers,

70
00:04:43,050 --> 00:04:46,600
then the probability that both prints
are placed in this bucket is really tiny.

71
00:04:47,614 --> 00:04:52,758
For each finger, each fingerprint has
a 20% chance of having minutiae in each of

72
00:04:52,758 --> 00:04:54,530
the, of the squares.

73
00:04:54,530 --> 00:04:58,492
So the chance of it hitting
all three is 0.2 cubed.

74
00:04:58,492 --> 00:05:03,156
And for both fingerprints to hit,
the probability is the square of that.

75
00:05:03,156 --> 00:05:09,207
That is 0.2 to the sixth power,
or .000064.

76
00:05:09,207 --> 00:05:12,740
Now let's look at two fingerprints
that come from the same finger.

77
00:05:14,210 --> 00:05:17,330
The probability of both being in
a given bucket is much higher.

78
00:05:18,410 --> 00:05:22,350
The reason is that there's a lot of
correlation between the buckets that will

79
00:05:22,350 --> 00:05:23,770
contain these prints.

80
00:05:23,770 --> 00:05:27,570
To start, for any given grid scare
the probability that the first print

81
00:05:27,570 --> 00:05:31,444
has some minutia there is 0.2.

82
00:05:33,200 --> 00:05:38,906
And given that it does, the probability
that the other does as well is 0.8.

83
00:05:38,906 --> 00:05:43,940
We need to raise 0.2 times 0.8 to
the third power, because there

84
00:05:43,940 --> 00:05:49,800
are three squares, each of which need to
hold minutiae from both of the prints.

85
00:05:49,800 --> 00:05:54,030
The result is about four tenths of 1%.

86
00:05:54,030 --> 00:05:55,980
Still really tiny, but

87
00:05:55,980 --> 00:06:01,010
64 times larger than the probability if
the prints come from different fingers.

88
00:06:01,010 --> 00:06:04,500
But remember,
we have 1,024 sets of three squares each.

89
00:06:05,650 --> 00:06:08,640
In order for
a pair of prints to be a candidate pair,

90
00:06:08,640 --> 00:06:14,450
we have only to find them together
in one of these 1,024 buckets.

91
00:06:14,450 --> 00:06:19,600
The probability of that happening
at least once is 98.5%.

92
00:06:19,600 --> 00:06:23,690
You can do the math if you like, but
there's an outline on the slide.

93
00:06:23,690 --> 00:06:28,070
That means there are only
1.5% false negatives.

94
00:06:28,070 --> 00:06:31,570
On the other hand, the same calculation
for a pair of fingerprints that comes from

95
00:06:31,570 --> 00:06:38,790
different fingers is this, and it gives
them a much smaller value of .063.

96
00:06:38,790 --> 00:06:41,960
That is,
there will be only 6.3% false positives.

97
00:06:41,960 --> 00:06:44,680
That's still quite expensive.

98
00:06:44,680 --> 00:06:47,750
It means that 6.3% of all
pairs need to be checked for

99
00:06:47,750 --> 00:06:50,860
similarity when almost all
of them will not be similar.

100
00:06:51,870 --> 00:06:54,870
On the other hand,
we did reduce our work by a factor of 15.

101
00:06:54,870 --> 00:06:58,400
And by using a larger number of
sets of squares and perhaps four or

102
00:06:58,400 --> 00:07:02,070
five squares per set,
we can reduce the false positive rate

103
00:07:02,070 --> 00:07:05,830
substantially while still keeping
the false negative rate low.