 |
Claims  |
|
|
What is claimed is:
1. A machine method of comparing an M.times.N data array to an X.times.Y
data array, said arrays being representative of fingerprint patterns,
comprising the steps of:
A. dividing said X.times.Y array into a plurality of sub-arrays;
B. comprising elements of a sub-array of said X.times.Y array with elements
of said M.times.N array and generating a correlation value indicative of
the degree of correlation existing between corresponding elements;
C. repeating step B for a plurality of sub-arrays of elements of said
M.times.N array;
D. identifying a highest correlation value generated in step C;
E. repeating steps B, C and D for each sub-array of said X.times.Y array;
F. identifying a relative location of said sub-arrays corresponding to said
highest correlation values to provide a measure of relative distortion of
said fingerprint patterns; and
G. comparing said highest correlation values and said measure of relative
distortion to respective predetermined threshold values.
2. The method of claim 1, wherein said comparing operation of Step G
includes:
summing said highest correlation values to produce a total;
dividing said total by said measure of relative distortion to produce a
correlation value-to-distortion ratio; and
comparing said ratio to a predetermined threshold value.
3. A machine method of comparing an M.times.N array to an X.times.Y data
array, said arrays being representative of fingerprint patterns,
comprising the steps of:
A. dividing said X.times.Y array into a plurality of sub-arrays;
B. comparing elements of a sub-array of said X.times.Y array with elements
of said M.times.N array and generating a correlation value indicative of
the degree of correlation existing between corresponding elements;
C. repeating step B for a plurality of sub-arrays of elements of said
M.times.N array to generate a correlation array of said correlation
values;
D. identifying a highest correlation value in said correlation array;
E. repeating steps B, C and D for each sub-array of said X.times.Y array:
F. identifying a relative location of said highest correlation values in
said correlation arrays to provide a measure of relative distortion of
said fingerprint patterns; and
G. comparing said highest correlation values and said measure of relative
distortion to respective predetermined threshold values.
4. The method of claim 3, wherein said comparing operation of Step G
includes:
summing said highest correlation values to produce a total;
dividing said total by said measure of relative distortion to produce a
correlation value-to-distortion ratio; and
comparing said ratio to a predetermined threshold value.
5. Apparatus for comparing an M.times.N data array to an X.times.Y data
array, said arrays being representative of fingerprint patterns,
comprising:
means for dividing said X.times.Y array into a plurality of sub-arrays;
means for comparing elements of each sub-array of said X.times.Y array with
elements of a plurality of sub-arrays of said M.times.N array and for
generating a correlation value indicative of the degree of correlation
existing between elements of each of said sub-arrays and corresponding
elements of said plurality of sub-arrays;
means for identifying a highest of said correlation values for each
sub-array;
means for identifying a relative location of said sub-arrays corresponding
to said highest correlation values to provide a measure of relative
distortion of said fingerprint patterns; and
means for comparing said highest correlation values and said measure of
relative distortion to respective predetermined threshold values.
6. Apparatus according to claim 5, wherein said means for comparing said
highest correlation values and said measure of relative distortion to
respective predetermined threshold values comprises:
means for summing said highest correlation values to produce a total;
means for dividing said total by said measure of relative distortion to
produce a correlation value-to-distortion ratio; and
means for comparing said ratio to a predetermined threshold value.
7. Apparatus according to claim 5, further comprising opto-electronic
scanning means having an optical element with a viewing surface for
scanning a fingerprint pattern to generate said M.times.N array.
8. Apparatus according to claim 7, further comprising transparent film
means, positioned over said viewing surface of said optical element, for
preventing direct contact between a fingertip and said viewing surface.
9. Apparatus according to claim 7, wherein said opto-electronic scanning
means includes positioning means for positioning a fingertip adjacent to
said viewing surface of said an optical element.
10. Apparatus according to claim 9, wherein said positioning means
comprises a pair of finger guides positioned on either side of a
centerline of said optical element, said finger guides being mechanically
interconnected and supported so as to remain equidistant from said
centerline when positioning said fingertip adjacent to said viewing
surface.
11. Apparatus according to claim 10, wherein said transparent film means is
movable relative to said viewing surface.
12. Apparatus for identifying fingerprint patterns, comprising:
memory means for storing at least one X.times.Y data array representative
of a first fingerprint pattern;
scanning means for scanning a second fingerprint pattern and for generating
an M.times.N data array representative of said second fingerprint pattern;
correlation means for comparing said M.times.N data array with said at
least one X.times.Y data array and for generating a correlation value
representative of said comparison;
distortion correction means for compensating for a degree of distortion and
misregistration of said second fingerprint pattern relative to said first
fingerprint pattern and for generating a measure of relative distortion
representative of said degree of distortion; and
threshold means for producing an indication signal when said correlation
value and said measure of relative distortion are compared to respective
threshold values.
13. Apparatus according to claim 12, wherein said distortion correction
means includes means for dividing said at least one X.times.Y data array
into a plurality of sub-arrays for comparison by said correlation means
with at least a portion of said M.times.N data array.
14. Apparatus according to claim 12, wherein said distortion correction
means includes means for dividing said at least one X.times.Y data array
into four sub-arrays for comparison by said correlation means with at
least a portion of said M.times.N data array.
15. Apparatus according to claim 12, further comprising finger positioning
means for positioning a fingertip adjacent to a viewing surface of an
optical element of said scanning means.
16. Apparatus according to claim 15, wherein said positioning means
comprises a pair of finger guides positioned on either side of a
centerline of said optical element, said finger guides being mechanically
interconnected and supported so as to remain equidistant from said
centerline when positioning said fingertip adjacent to said viewing
surface.
17. Apparatus according to claim 12, further comprising transparent film
means, positioned over said viewing surface of said optical element, for
preventing direct contact between a fingertip and said viewing surface.
18. Apparatus according to claim 17, wherein said transparent film means is
movable relative to said optical element.
19. Apparatus according to claim 12, wherein said memory means contains a
plurality of X.times.Y data arrays representative of a plurality of
fingerprint patterns.
20. Apparatus according to claim 19, further comprising a selection means
for selecting said X.times.Y data array representative of said first
fingerprint pattern from said plurality of X.times.Y data arrays for
comparison with said M.times.N data array representative of said second
fingerprint pattern. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
BACKGROUND AND SUMMARY OF THE INVENTION
This invention relates generally to identification systems and in
particular to identification of individuals by comparison of fingerprint
patterns.
It has long been recognized that certain personal features are unique to an
individual and can be used as a means of positive identification. One such
feature that is frequently chosen for this purpose is the fingerprint.
U.S. Pat. Nos. 3,383,657; 3,527,535; 4,185,270 and 4,210,899 all describe
identification systems which are based on fingerprint pattern recognition
techniques.
In general, techniques such as those described in the above-mentioned
patents involve scanning a selected fingerprint pattern, converting the
pattern information into an electrical signal, and storing or processing
the information (e.g., by comparing it to prestored information) to effect
an identification. Scanning is generally accomplished by opto-electronic
means which avoids the use of inks or other undesirable materials. U.S.
Pat. No. 3,527,535 to Monroe describes several methods using different
types of glass prisms and illumination means to produce a visible or
scannable fingerprint pattern. Other systems described in the literature
have used an illuminated right angle prism and the technique of
frustration of total internal reflection to produce a visible and
scannable image. These systems depend for their success on the fact that
the ridges of the skin on the finger contact a smooth, clean optical
surface while the valleys do not. While it is seldom mentioned in the
literature, the practical application of such an optical system requires a
thorough cleaning after each use to remove the oils, water and dirt
deposited on the surface by the finger. If these deposits are not removed,
a residual image caused by them may be seen and subsequent operation of
the system will be severely affected.
Another problem often experienced in fingerprint recognition systems
involves registration of a fingertip in the proper position for scanning.
Some existing systems use a jig or guide in an attempt to position the
finger in the same location and orientation on the scanner for each use.
While this is generally a desirable feature, it cannot be relied on to
produce re-registration of the fingerprint to the exact same location on
the surface of the optical element of the scanner for every subsequent
scan performed. Accordingly, some degree of misregistration usually
occurs. In an image matching system, there will be some degree of
correlation between similar, but not identical, images. Thus, a system
which does not provide accurate registration capability will experience
difficulty in distinguishing between similar images and misregistered
identical images.
Difficulties in identifying a known fingerprint pattern by comparison to a
subsequently scanned identical pattern can also be caused by distortion.
As used here, the term distortion refers to changes in the relative
locations of ridges and valleys in a fingerprint pattern which can result
from a number of causes. For example, the flesh beneath the skin is
plastic and can be deformed with reasonable amounts of force or pressure.
This property allows a relatively large area of a fingerprint pattern to
be scanned since the fingertip is generally pressed against a flat optical
element surface for scanning. However, a certain degree of relative
distortion between fingerprint patterns scanned at different times can
result when different amounts of pressure are applied in pressing the
fingertip against the optical surface. Non-uniform pressure or force
components acting on the fingertip which are not normal to the flat
optical surface can also result in distortion being introduced.
Considering the plastic nature of the flesh and skin surrounding the bone
on the finger, it is easy to see that such forces can cause pattern
displacements equal to several ridge-valley separations. Other factors,
such as large weight gains or losses by the individual and large ambient
temperature variations, have also been shown to produce relative
distortions in fingerprint images. While the effects here are relatively
small (generally on the order of less than 3 percent), they can be
sufficient to adversely affect the accuracy of a comparison.
An object of the present invention is to provide an apparatus which
prevents deposition of dirt, oils and water on the surface of an optical
element in a scanning device.
Another object of the present invention is to provide a method and
apparatus for comparing data arrays representative of fingerprint patterns
which compensates for misregistration of the fingertip on the scanner.
A further object of this invention is to provide a method and apparatus for
comparing data arrays representative of fingerprint patterns which
compensates for distortion, relative to an original scan pattern,
introduced into fingerprint patterns produced by subsequent scans.
These and other objects are attained in an apparatus for identifying
fingerprint patterns comprising: an optoelectronic scanner for scanning
fingerprint patterns; threshold circuits for reducing the electronic
signal to a binary array of 1's and 0's; memory for storing the initial or
reference data arrays; additional memory for storing subsequent or new
scanned data arrays; means for comparing the reference and new data
arrays; means for determining the degree of correlation between the
reference and new data arrays; means for determining the degree of
distortion between the reference and new data arrays; and means for
producing an indication signal when the correlation value exceeds a
pre-set threshold and when the distortion value is below a pre-set
threshold.
The reference data array will be referred to as an X.times.Y array and the
new scan data array will be referred to as an M.times.N array. In the
example to follow M>X and N>Y.
A preferred method of comparing the M.times.N data array to the previously
stored X.times.Y reference data array comprises the steps of: dividing the
X.times.Y array into a plurality of sub-arrays; comparing individual
elements of an X.times.Y sub-array with corresponding elements of a
sub-array of the M.times.N array and generating a correlation value
indicative of the degree of correlation existing between the corresponding
elements; repeating the comparison step for a number of sub-arrays of
elements of the M.times.N array; identifying a highest correlation value
generated in these comparisons; repeating the comparison steps for each of
the plurality of X.times.Y sub-arrays; and comparing the highest
correlation values identified to a predetermined threshold value to
determine whether or not a sufficient correspondence exists to indicate a
match. As will be described in more detail below, the X.times.Y reference
array in one embodiment of the invention is preferably divided into four
sub-arrays (i.e., quadrants). Comparison of the elements of each sub-array
with a number of sub-arrays of elements of the M .times.N array results in
compensation for both misregistration and distortion introduced when a
scan is performed to generate the M.times.N array.
The comparison of elements of the X.times.Y sub-arrays and the M.times.N
sub-arrays is preferably performed by executing a logical "exclusive or"
operation, using the elements of the X.times.Y sub-array and the elements
of the M.times.N sub-array as inputs, to generate a correlation value by
counting the number of matches which occur when all elements of an
X.times.Y sub-array are compared to all corresponding elements of an
M.times.N sub-array. In an especially preferred method, the location in
the M.times.N array of the sub-array having the highest degree of
correlation with the X.times.Y sub-array is identified. The displacement
of the sub-arrays having the highest correlation values from the location
which would result from scanning a perfectly registered and undistorted
fingerprint pattern provides a measure of the misregistration and relative
distortion of the pattern being compared. This distortion measure can be
used, along with the peak correlation values themselves, to determine if a
match has occurred. Thus, an accurate comparison can be made even in the
presence of misregistration and distortion. An especially preferred method
involves summing the highest correlation values generated for each
X.times.Y sub-array and corresponding M.times.N sub-array, dividing the
total by the measure of relative distortion to produce a correlation
value-to-distortion ratio, and comparing the ratio to a pre-determined
threshold value.
A preferred method of processing the correlation values as they are
generated by the comparisons described above involves creation of a
correlation array whose elements represent the degree of correlation
existing between elements of an X.times.Y sub-array and the elements of
each of the M.times.N sub-arrays to which the X.times.Y sub-array is
compared.
An advantageous embodiment of the present invention includes additional
apparatus to position the fingertip over a viewing surface of an optical
element of the scanning device. An especially advantageous embodiment
includes provision of a transparent film over the viewing surface to
prevent the fingertip from contacting the surface directly. The
transparent film can be moved, or indexed, relative to the viewing
surface, to provide a clean contact surface for the fingertip on
subsequent scans. Indexing of the film preferably takes place
automatically after a comparison is performed. The transparent film
apparatus may include a length of clear, plastic film, a supply reel, a
take-up reel and drive means for at least one of the two reels.
Other objects, advantages and novel features of the present invention will
become apparent from the following detailed description of the invention
when considered in conjunction with the accompanying drawings.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 shows a block diagram of a fingerprint identification system
according to the present invention.
FIG. 2a shows a schematic view, and FIG. 2b a sectional view, of the finger
positioning and transparent film transport apparatus.
FIG. 3 shows a schematic representation of the arrays generated by the
scanner.
FIGS. 4a-4d show the reference (X.times.Y) data array divided into four
sub-arrays, each overlaying a larger sub-array of the M.times.N new scan
data array.
FIGS. 5a-5c are generalized flow-chart diagrams of the comparison procedure
.
DETAILED DESCRIPTION OF THE DRAWINGS
FIG. 1, which illustrates a preferred embodiment of the fingerprint
identification system, shows a system having a data input section 10 and a
processing and control section 12. Input section 10 includes finger
positioning means 14, transparent film transport 18, illumination and
optical system 20, optional viewing system 22 and scanner 24. Finger
positioning means 14 and transparent film transport 18 are discussed with
reference to FIGS. 2a and 2b below. Illumination and optical system 20
provides a means for illuminating the viewing surface of an optical
element, such as a prism, and a lens for relaying the image formed to
scanner 24. Optical viewing system 22 can be added by placing a beam
splitting mirror in the optical path between optical system 20 and scanner
24. A viewing system of this type is shown in U.S. Pat. No. 3,975,711.
Scanner 24 is an opto-electronic device which scans the image formed by
optical system 20 and converts the image into electrical signals. Scanner
24 is provided with circuitry which converts the analog image signal into
a digital bit stream with one logic level representing a dark pixel and
the other logic level representing a light pixel. Scanning is accomplished
in a raster format so that the location of the data bits is representative
of the location of the pixels on the finger. In this preferred embodiment,
scanner 24 is a square array of 100.times.100 photosensitive cells such as
that produced commercially by RETICON. It should be noted that any
scanning system may be employed which will convert the optical image into
electrical signals. Optical system 20 is selected such that scanner 24
scans an area on the prism face of approximately 0.5.times.0.5 inches.
Thus, each pixel in the 100.times.100 array represents an area on the
fingerprint pattern of approximately 0.005.times.0.005 inches. This
resolution is more than sufficient for the highest fingerprint ridge
density (80 lines per inch) found in the general population.
Control section 12 includes data processor and control unit 26, keyboard
and display unit 28, memory 30 and correlator 32. Data processor and
control unit 26 is preferably a standard commercially available
microprocessor, although a larger computer could be used on a dedicated or
time-shared basis. Data processor 26 controls and receives data from
scanner 24, formats and stores the data in memory 30 (which may be an
integral part of processor 26), controls and processes the results from
the comparison performed in correlator 32, and outputs control signals
based on stored accept/reject criteria.
Keyboard and optional display unit 28 provides means for an individual to
initiate the identification process by entering an assigned identification
number. This mechanism can be used to reduce processing time by
identifying a reference file or array against which the newly entered data
will be compared. Alternatively, each newly entered data array can be
compared against all reference arrays stored in memory 30.
Although data processor 26 could be used to compare newly input fingerprint
data to stored reference data, the preferred embodiment uses special
purpose digital circuits, which operate under the control of data
processor 26, represented on the block diagram of FIG. 1 by correlator 32.
As described below, the comparison process includes performing a logical
"exclusive or" operation between elements of the arrays. This operation
can be performed much faster in a special purpose circuit such as the TDC
1023J integrated circuit produced by TRW, Inc.
Referring now to FIGS. 2a and 2b, there is illustrated an embodiment of
finger positioning means 14 and transparent film transport 18. Finger
positioning means 14 includes spring-loaded guides 34 and 35 and stop 36.
Guides 34 and 35 are mechanically constrained and free to open and close
while remaining perpendicular to the finger stop and parallel to one
another. The finger guides are preferably mechanically coupled together so
as to move equal amounts in opposite directions when forced apart by the
placement of the finger. This is illustrated in FIG. 2a by the rigid
attachment of toothed rack members 37 and 39 to guides 34 and 35,
respectively. The teeth on rack members 37 and 39 coact with pinion gear
41 to cause equal and concurrent movement of the guides away from center
line 43 when a finger is positioned between them. Springs, such as the one
shown at 45, are provided to return guides 34 and 35 to their original
positions.
This arrangement for positioning a fingertip adjacent to optical element 38
has been found to provide a nominally repeatable registration of a finger
on successive trials. Guides 34 and 35 act to center the finger above the
prism surface and, thus, prevent the occurrence of very large registration
errors. As will be shown below, exact re-registration of the finger is not
required in the present invention, since registration errors are
compensated for in the processing of the scan data.
Transparent film transport 18 includes clear, plastic film 40, guide
rollers 42, supply reel 44, take-up reel 46 and a drive mechanism (not
shown) for one or both of the reels. Indexing of the film after each scan
operation is controlled by the data processor and control unit 26. A
preferred approach to controlling the amount of film transported on each
indexing operation is through use of a stepping motor and a capstan drive.
Film 40 is arranged to pass over viewing surface 48 of optical element 38
on which a fingertip is to be positioned for scanning. Guide rollers 42
support film 40 parallel to viewing surface 48 and prevent rubbing of the
film on the edges of element 38. Supply reel 44 and take-up reel 46
provide means for indexing film 40 between each operation of the system by
an amount slightly greater than the width of a finger.
In operation, an individual places a finger between guides 34 and 35
(forcing them to open) and against stop 36. The finger is pressed against
plastic film 40 which is moved into contact with viewing surface 48. Film
40 becomes, in effect, a new viewing surface for optical element 38 with
light being transmitted through the plastic to be absorbed by the skin or
reflected by the air-plastic interface, thus, forming an image of the
fingerprint as before. The indices of refraction of the optical element
material and plastic film 40 do not have to be matched and a great deal of
freedom in choice of materials exists. Film 40 protects viewing surface 48
from contamination by oils, dirt and water present on the fingertip which
might otherwise cause the system to err. Film 40 is indexed or moved by
drive means, preferably under the control of data processor 26, after each
use so that a clean surface is presented for each subsequent scan.
When the system is initially set up, a reference scan is performed and an
X.times.Y reference data array is stored in memory 30. A file system in
the software is used to define the store locations, with each fingerprint
file assigned an identification number so that the data may later be
recalled for comparison with new scan data.
For purposes which will become clear later, the stored X.times.Y reference
array is formed from a central sub-set of the total scan data. FIG. 3
shows in pictorial form the relationship of the X.times.Y reference array
to the total scan data. The size of the X.times.Y reference array is
shown, for illustrative purposes, as 64.times.64 bits. Larger or smaller
arrays can be used successfully, as can rectangular arrays. For processing
purposes, the reference data is broken into sub-arrays, or quadrants, and
use of a 64.times.64 element array means that each quadrant will be
32.times.32 elements in size. This organization takes advantage of the
fact that most computers are designed to process data in multiples of 8
bit bytes, and this organization simplifies the computer programming.
When the reference file containing an X.times.Y reference array for each
individual is established, the system is ready to be used for personal
identification. The individual to be identified enters an ID number and
positions a finger for scanning. Under the control of data processor 26, a
"new" scan of the fingerprint is made and an M.times.N data array is
stored in memory 30. Again, for ease of computer program design, the total
scan data is reduced to a central sub-set to form the M.times.N array
which, in this preferred method, comprises 96.times.96 elements.
For the comparison process, the X.times.Y reference array is divided into a
number of sub-arrays. Each sub-array is then compared to a corresponding
sub-array of elements of the M.times.N data array by performing logical
"exclusive or" operations using, as inputs, each element of the X.times.Y
sub-array and a corresponding element of the M.times.N sub-array. The
M.times.N sub-array is selected to be larger than the X.times.Y sub-array
in both dimensions to permit a search for a best match at many possible
locations. As a result of the "exclusive or" operations, a count of the
number of matching elements is produced. This count is called the
correlation value. The reference sub-array is then "moved" on the
M.times.N sub-array and another comparison is performed. This comparison
produces a second correlation value. The process is repeated for all
possible locations of the X.times.Y sub-array in the M.times.N sub-array
and produces a correlation sub-array of size (M-X+1) .times.(N-Y+1). This
entire process is then repeated for each of the remaining X.times.Y
sub-arrays with the corresponding M.times.N sub-arrays.
The division of the X.times.Y array into a number of sub-arrays allows a
best possible match to be found for each sub-array of the X.times.Y array
and a corresponding sub-array of the M.times.N array. This match is not
influenced by the remaining elements in the arrays. This provides a degree
of distortion compensation by, in effect, allowing the X.times.Y array to
be effectively stretched or compressed with respect to the M.times.N
array. A division by a factor of 2 in each of the X and Y directions is
the simplest possible case. However, division by a factor of 3, 4 or a
greater number is | | |
