(19)
`
`(12)
`
`Europäisches Patentamt
`
`European Patent Office
`
`Office européen des brevets
`
`*EP000918300B1*
`EP 0 918 300 B1
`
`(11)
`
`EUROPEAN PATENT SPECIFICATION
`
`(45) Date of publication and mention
`of the grant of the patent:
`08.01.2003 Bulletin 2003/02
`
`(21) Application number: 98120186.6
`
`(22) Date of filing: 29.10.1998
`
`(51) Int Cl.7: G06K 9/00
`
`(54) Fingerprint feature correlator
`
`Merkmalkorrelator für Fingerabdrücke
`
`Corrélateur de caractéristiques pour empreintes digitales
`
`(84) Designated Contracting States:
`DE FR GB IT
`
`(30) Priority: 22.11.1997 US 995330
`
`(43) Date of publication of application:
`26.05.1999 Bulletin 1999/21
`
`(73) Proprietor: TRW Inc.
`Redondo Beach, California 90278 (US)
`
`(72) Inventors:
`• Hsu, Shi-Ping
`Pasadena, CA 91107 (US)
`• Evans, Bruce W.
`Redondo Beach, CA 90277 (US)
`
`(74) Representative: Schmidt, Steffen J., Dipl.-Ing.
`Wuesthoff & Wuesthoff,
`Patent- und Rechtsanwälte,
`Schweigerstrasse 2
`81541 München (DE)
`
`(56) References cited:
`US-A- 4 646 352
`
`US-A- 5 067 162
`
`• ANDERSON S: "A SINGLE CHIP SENSOR &
`IMAGE PROCESSOR FOR FINGERPRINT
`VERIFICATION" PROCEEDINGS OF THE
`CUSTOM INTEGRATED CIRCUITS
`CONFERENCE, SAN DIEGO, MAY 12 - 15, 1991,
`no. CONF. 13, 12 May 1991 (1991-05-12), pages
`12.1.1-12.1.4, XP000295730 INSTITUTE OF
`ELECTRICAL AND ELECTRONICS ENGINEERS
`ISBN: 0-7803-0015-7
`• HIRONORI YAHAGI ET AL: "MOVING-WINDOW
`ALGORITHM FOR FAST FINGERPRINT
`VERIFICATION" TECHNOLOGIES TODAY AND
`TOMORROW, NEW ORLEANS, APRIL 1 - 4, 1990,
`vol. 1, 1 April 1990 (1990-04-01), pages 343-347,
`XP000203123 INSTITUTE OF ELECTRICAL AND
`ELECTRONICS ENGINEERS
`• RATHA N K ET AL: "A REAL-TIME MATCHING
`SYSTEM FOR LARGE FINGERPRINT
`DATABASES" IEEE TRANSACTIONS ON
`PATTERN ANALYSIS AND MACHINE
`INTELLIGENCE, vol. 18, no. 8, 1 August 1996
`(1996-08-01), pages 799-812, XP000632861 ISSN:
`0162-8828
`
`Note: Within nine months from the publication of the mention of the grant of the European patent, any person may give
`notice to the European Patent Office of opposition to the European patent granted. Notice of opposition shall be filed in
`a written reasoned statement. It shall not be deemed to have been filed until the opposition fee has been paid. (Art.
`99(1) European Patent Convention).
`
`Printed by Jouve, 75001 PARIS (FR)
`
`EP0 918 300B1
`
`ASSA ABLOY Ex 1033 - Page 1
`ASSA ABLOY AB, et al. v. CPC Patent Technologies Pty Ltd.
`IPR2022-01094 - U.S. Patent No. 8,620,039
`
`

`

`1
`
`EP 0 918 300 B1
`
`2
`
`Description
`
`[0001] This invention relates generally to pattern rec-
`ognition systems and, more particularly, to a system and
`method for comparing two fingerprint images and deter-
`mining whether or not they are from the same person.
`Fingerprints are, of course, widely used in criminal in-
`vestigation work, and fingerprints are routinely taken
`from applicants for jobs, security clearances, citizen-
`ship, and so forth. For these and many other applica-
`tions of fingerprint image processing, it is most often re-
`quired to compare one fingerprint with many others, in
`an effort to find a match. So called "minutia matching"
`approaches are commonly used in such search appli-
`cations. In these approaches a small amount of charac-
`teristic data is extracted from a fingerprint image. This
`data may be quickly compared with corresponding data
`from another image to determine if the imaged prints
`match. Extraction of this data is a complex process, and
`is relatively time consuming even on a powerful compu-
`ter. For search applications, this is acceptable because
`the extracted minutia data are reused many times, so
`that the minutia extraction overhead is amortized over
`a large number of comparisons.
`[0002] By way of contrast, the present invention per-
`tains to the use of fingerprint images for purposes of ver-
`ification of a person's identity. In this application, the per-
`son "enrolls" in a system by supplying a reference fin-
`gerprint image. When the same person's fingerprint im-
`age is subsequently scanned for purposes of gaining ac-
`cess to a protected property, the newly scanned image
`is compared with the reference image for verification. In
`many practical applications of fingerprint verification,
`such as for access to vehicles, buildings or computers,
`the process must be completed in a matter of seconds,
`preferably using an inexpensive computer processor.
`[0003] Many fingerprint matching systems developed
`or proposed for verification purposes have followed
`much the same principles used in larger identification
`systems, using pattern minutia extraction and matching.
`Because the minutia extraction process involves com-
`plex and heterogeneous mathematical operations, and
`must be performed each time a finger is presented for
`verification, a powerful general-purpose computer proc-
`essor is required in order to perform a comparison within
`an acceptable time. As a result, such systems are large
`in size and high in cost. Their application has therefore
`been limited, usually to the protection of important sites
`or computer installations for which the high cost is war-
`ranted and space is available.
`[0004] Fingerprint image correlation is an alternative
`to minutia based approaches. It is attractive because
`correlation operations have a simple, repetitive mathe-
`matical structure, which is suited to implementation by
`custom computing hardware utilizing high levels of par-
`allelism to achieve rapid processing. Such hardware
`can be realized compactly and inexpensively as an ap-
`plication specific integrated circuit (ASIC). U.S. Patent
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`2
`
`No. 5,067,162 to Driscoll, Jr. et al. Discloses a method
`and apparatus for verifying identity using fingerprint im-
`age correlation, but their apparatus is controlled by a
`programmable general purpose computer processor.
`Use of a programmable computer to implement the cor-
`relation of the two fingerprint images poses a difficult
`design choice between accuracy of results and speed
`of processing. In general, a high level of accuracy de-
`grades the speed of processing to a degree that makes
`such a configuration unsuitable for many applications.
`[0005]
`It will be appreciated from the foregoing that
`there is still a significant need for a fingerprint correlation
`technique that will operate rapidly and reliably, but which
`may be implemented in a compact package at relatively
`low cost. As will become apparent from the following
`summary, the present invention meets this need.
`
`SUMMARY OF THE INVENTION
`
`[0006] The present invention resides in a fingerprint
`feature correlator using a processing method that can
`be implemented in significant part in integrated circuitry,
`to provide fast processing without compromising relia-
`bility. It will be understood that the term "fingerprint" in-
`cludes thumb print, palm print, and other similar biomet-
`ric indicators used for identification.
`[0007] Briefly, and in general terms, the fingerprint
`correlator of the invention comprises a fingerprint sen-
`sor, for generating a digital image of a fingerprint; an
`enrollment processor for extracting, from a fingerprint
`image generated by the fingerprint sensor from the fin-
`gerprint of an identified person, multiple reference
`patches that together uniquely identify the image; refer-
`ence image storage means, for storing reference patch
`images and locations provided by the enrollment proc-
`essor; a correlation processor for searching the subject
`fingerprint image generated by the fingerprint sensor
`from the fingerprint of a person seeking identity verifica-
`tion for instances of two dimensional pixel patterns suf-
`ficiently similar to the patterns of the stored reference
`patches, and for generating a set of candidate match
`locations in the subject image corresponding to the lo-
`cation of each such instance for each reference patch;
`and a geometric constraint checking processor, for at-
`tempting to locate in the set of candidate match loca-
`tions a subset of locations that is geometrically congru-
`ent with a corresponding subset of reference patch lo-
`cations, to a desired degree of accuracy, and for deter-
`mining whether there is a match between the subject
`image and the stored reference image. The feature cor-
`relator also includes an image preprocessor, for con-
`verting the digital image of the fingerprint to binary form,
`removing extraneous background and, optionally, rotat-
`ing the image to a standard orientation.
`[0008] More specifically, the enrollment processor in-
`cludes means for binarizing the gray scale digital image
`and thinning the binary image to obtain skeletal images
`of ridges and valleys in the fingerprint; means for ana-
`
`ASSA ABLOY Ex 1033 - Page 2
`ASSA ABLOY AB, et al. v. CPC Patent Technologies Pty Ltd.
`IPR2022-01094 - U.S. Patent No. 8,620,039
`
`

`

`3
`
`EP 0 918 300 B1
`
`4
`
`lyzing the skeletal images to locate bifurcation features
`in the ridges and valleys; means for selecting reference
`patches based on feature density, and storing the refer-
`ence patch locations in the reference image storage
`means; and means for extracting reference patch imag-
`es from the skeletal images of the ridges and valleys
`and storing the reference patch images in the reference
`image storage means with the corresponding reference
`patch locations.
`[0009] An important aspect of the invention is the cor-
`relation processor, which compares the pixels in every
`reference patch selected by the enrollment processor
`with the pixels in every possible patch location in the
`subject fingerprint image, to determine the locations of
`patches in the subject image that match, or nearly
`match, any of the reference patches. The correlation
`processor includes an array of correlator units, each for
`comparing a selected pixel from a reference patch with
`a selected pixel in the subject image, wherein the entire
`array simultaneously compares the selected pixel from
`each of a plurality of reference patches with a plurality
`of pixels in a block of pixels from the subject image; an
`address generator, for generating a sequence of ad-
`dresses for accessing successive pixels in the plurality
`of reference patches, and another sequence of address-
`es for accessing successive blocks of pixels in the sub-
`ject image, wherein each reference patch is compared
`with every possible patch position in the subject image;
`and a result collection memory, for recording pixel match
`count data pertaining to every possible match candidate
`position in the subject image, along with candidate
`match locations in the subject image. Preferably, the ad-
`dress generator further includes means for generating
`rotated reference patch addresses in such a way that a
`rotated image of each reference patch is also compared
`with each possible patch of the subject image. In partic-
`ular, the means for generating rotated reference patch
`addresses includes means for storing multiple sets of
`two-dimensional offset addresses, each set of offset ad-
`dresses defining a different rotation angle. By this
`means, each reference patch is compared with each
`possible patch of the subject image at multiple orienta-
`tion angles.
`[0010] Each correlator unit in the correlation proces-
`sor includes a counter for recording a count indicative
`of the degree of match between a reference patch and
`a patch of the subject image; and the correlation proc-
`essor further includes means for saving the contents of
`the counters in the result collection memory on comple-
`tion of a comparison of all pixels in the reference patch-
`es, and means for saving a subject image location with
`each count, and means for resetting the counters to be-
`gin a comparison with other locations in the subject im-
`age. The correlation processor further includes means
`rendered operative at the conclusion of all matching op-
`erations of the correlation processor, for selecting a set
`of match candidates from the results saved in the result
`collection memory. The latter means for selecting a set
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`3
`
`of match candidates includes means for discarding
`match candidates that are positioned in the subject im-
`age relatively close to a better candidate.
`[0011] Another important feature of the invention is
`the geometric constraint checking processor, which in-
`cludes means for determining the distances between all
`possible pairs of reference patches; means for deter-
`mining the distances between all possible pairs of dis-
`tinct match candidates; means for selecting a feasible
`subset of the distinct match candidates such that the dis-
`tances between all possible pairs in the feasible subset
`are approximately equal to the distances between cor-
`responding pairs of reference patches; and means for
`declaring a match based on the size of the feasible sub-
`set.
`[0012] The invention may also be defined in terms of
`a method for verifying a person's identity using finger-
`print feature correlation. Briefly, the method comprises
`the steps of sensing a fingerprint of an identified person
`wanting to enroll a fingerprint image; generating a digital
`image of the fingerprint; enrolling the fingerprint image,
`by finding and extracting multiple reference patches that
`together uniquely identify the image; storing the extract-
`ed reference patch images and their locations in a ref-
`erence image memory; sensing a subject fingerprint im-
`age of a person wanting identity verification; generating
`a digital subject fingerprint image from the sensed sub-
`ject fingerprint image; searching the subject fingerprint
`image for instances of pixel patterns similar to the stored
`reference patch images, or with similar to rotated forms
`of the stored reference patches; generating a set of
`match candidates and their locations in the subject im-
`age; attempting to locate in the set of match candidates
`a subset of match candidates that is geometrically con-
`gruent with a corresponding subset of reference patch-
`es, to a desired degree of accuracy; and determining
`whether there is a match between the subject image and
`the stored reference image. The method as disclosed
`also includes preprocessing the digital image, by con-
`verting the digital image of the fingerprint to binary form,
`removing extraneous background picture elements, and
`optionally adjusting the image to a standard orientation.
`[0013] More specifically, the enrolling step includes
`thinning the binary image to obtain skeletal images of
`ridges and valleys in the fingerprint; analyzing the skel-
`etal images to locate bifurcation features in the ridges
`and valleys; selecting reference patches based on fea-
`ture density; and extracting reference patch images
`from the skeletal images of the ridges and valleys.
`[0014] The comparing step of the basic method in-
`cludes comparing, in a correlator unit that is one mem-
`ber of an array of correlator units, a selected pixel from
`a reference patch with a selected pixel in the subject
`image, wherein the entire array simultaneously com-
`pares the selected pixel from each of a plurality of ref-
`erence patches with a plurality of pixels in a block of
`pixels from the subject image; generating a sequence
`of addresses for accessing successive pixels in the plu-
`
`ASSA ABLOY Ex 1033 - Page 3
`ASSA ABLOY AB, et al. v. CPC Patent Technologies Pty Ltd.
`IPR2022-01094 - U.S. Patent No. 8,620,039
`
`

`

`5
`
`EP 0 918 300 B1
`
`6
`
`rality of reference patches, and another sequence of ad-
`dresses for accessing successive blocks of pixels in the
`subject image, wherein each reference patch is com-
`pared with every possible patch position in the subject
`image; and recording, in a result collection memory, pix-
`el match count data pertaining to every possible match
`candidate position in the subject image, along with
`match candidate locations in the subject image. More
`specifically, the step of generating addresses further in-
`cludes generating rotated reference patch addresses in
`such a way that a rotated image of each reference patch
`is also compared with each possible patch of the subject
`image. The step of generating rotated reference patch
`addresses includes storing multiple sets of two-dimen-
`sional offset addresses, each set of offset addresses de-
`fining a different rotation angle, and wherein each refer-
`ence patch is compared with each possible patch of the
`subject image at multiple orientation angles.
`[0015] Each step of comparing in a correlator unit in-
`cludes recording a count indicative of the degree of
`match between a reference patch and a patch of the
`subject image; and the method further comprises the
`steps of saving the counts in the result collection mem-
`ory on completion of a comparison of all pixels in the
`reference patches, saving a subject image location with
`each count, and resetting the counts to begin a compar-
`ison with other locations in the subject image. The meth-
`od may also comprise the step, performed at the con-
`clusion of all matching operations, of selecting a set of
`match candidates from the results saved in the result
`collection memory. This step of selecting a set of match
`candidates includes discarding match candidates that
`are positioned in the subject image relatively close to a
`better candidate.
`[0016] Finally, the step of attempting to locate in the
`set of match candidates a subset of match candidates
`that is approximately geometrically congruent with a
`corresponding subset of reference patches, includes
`determining the distances between all possible pairs of
`reference patches; determining the distances between
`all possible pairs of distinct match candidates; selecting
`a feasible subset of the distinct match candidates such
`that the distances between all possible pairs in the fea-
`sible subset are approximately equal to the distances
`between corresponding pairs of reference patches; and
`declaring a match based on the size of the feasible sub-
`set. These distance tests do not preclude the possibility
`that the feasible subset is a mirror image of the corre-
`sponding reference locations, and, therefore, lacks the
`desired geometric congruency with the reference loca-
`tions. Elimination of this possibility requires the incorpo-
`ration of an additional test into the feasible set selection
`process.
`[0017]
`It will be appreciated from the foregoing sum-
`mary that the present invention represents a significant
`advance in the field of fingerprint image comparison for
`purposes of identity verification. In particular, the inven-
`tion provides a reliable but very fast technique for com-
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`4
`
`paring the distinguishing features of two fingerprint im-
`ages Other aspects and advantages of the invention will
`become apparent from the following more detailed de-
`scription, taken in conjunction with the accompanying
`drawings.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`[0018]
`
`FIG. 1 is a block diagram showing the principal com-
`ponents of a fingerprint feature correlator in accord-
`ance with the present invention;
`FIG. 2 is a flowchart showing the principal functions
`performed by the apparatus of the invention;
`FIG. 3 is a binary image of a fingerprint with overlaid
`square outlines indicating reference patches cho-
`sen in an enrollment process to identify the finger-
`print;
`FIG. 4 is a set of trinary images of twenty-five ref-
`erence patches that have been reduced to skeletal
`form, with white pixels indicating ridges and black
`pixels indicating valleys of the fingerprint pattern;
`FIG. 5 is binary image of a different fingerprint of
`the same finger that was used to generate the im-
`age of FIG. 3, and also showing how the reference
`patches of FIG. 4 may be overlaid on the binary im-
`age to verify that the fingerprints are of the same
`finger;
`FIG. 6 is a binary image of a totally different finger-
`print, taken from a different person, and showing
`how only two of the reference patches of FIG. 4 may
`be successfully matched on the fingerprint image;
`FIG. 7 is a more detailed flowchart of the image
`quality check and image processing steps of FIG. 2;
`FIGS. 8 and 9 taken together are a more detailed
`flowchart of the enrollment functions depicted in
`FIG. 2;
`FIG. 10 is a hardware block diagram of the feature
`correlator processor shown in FIG. 1;
`FIG. 11 is a flowchart of the functions performed by
`the feature correlator processor of FIG. 10;
`FIG. 12 is a diagram showing a reference patch in
`regular and rotated orientation, in relation to a ref-
`erence data frame;
`FIG. 13 is a diagram showing a subject image data
`frame and a reference patch that is translated and
`rotated with respect
`to the subject
`image data
`frame, in the course of the correlation process;
`FIG. 14 is block diagram illustrating how the refer-
`ence patch images are correlated with the subject
`image in the feature correlator processor of FIG. 1;
`FIG. 15 is a schematic diagram of a correlator unit
`or sub-module within the feature correlator proces-
`sor of FIG. 1;
`FIG. 16 is a flowchart showing how match candi-
`dates as determined in the feature correlator are
`further processed to obtain a list of patch candi-
`
`ASSA ABLOY Ex 1033 - Page 4
`ASSA ABLOY AB, et al. v. CPC Patent Technologies Pty Ltd.
`IPR2022-01094 - U.S. Patent No. 8,620,039
`
`

`

`7
`
`EP 0 918 300 B1
`
`8
`
`dates in the subject fingerprint image;
`FIG. 17 is a flowchart of the functions performed in
`geometric constraint analysis applied to the list of
`patch candidates to make a final determination as
`to whether a subject fingerprint image matches a
`reference image generated during enrollment;
`FIG. 18 is a more detailed flowchart of the geometric
`constraint analysis step of choosing a maximal fea-
`sible subset of distinct match candidates;
`FIG. 19 is an illustrative match candidate matrix;
`FIGS. 20A-20F are diagrams of all of the feasible
`canonical representations corresponding to the
`match candidate matrix of FIG. 19;
`FIG. 21 is a flowchart of a search process for finding
`the size of a maximal feasible subset of candidate
`match locations in a subject fingerprint image; and
`FIG. 22 is a flowchart showing more detail of the
`recursive procedure used in the search process of
`FIG. 21.
`
`DESCRIPTION OF THE PREFERRED EMBODIMENT
`
`[0019] As shown in the drawings by way of illustration,
`the present invention pertains to a method and appara-
`tus for correlation of features in fingerprint images. Fin-
`gerprint image correlators in the past either relied on the
`extraction and matching of pattern minutia or, even
`when minutia matching was not used, required pro-
`grammable computers that are too bulky, costly and
`much too slow for many practical applications, such as
`controlling access to vehicles.
`[0020]
`In accordance with the present invention, a fin-
`gerprint image is correlated with a previously stored ref-
`erence image in such a way that a reliable result is ob-
`tained very quickly, but using relatively inexpensive and
`compact components that can be installed in a variety
`of locations or in a portable device.
`
`Overview of the invention:
`
`[0021]
`In its simplest form, this invention utilizes a
`commercial fingerprint imaging device and a processing
`system that interfaces with this device to capture, store
`and process fingerprint images in digital form, and to
`perform a fingerprint verification function. This invention
`performs two principal operations: 1) enrollment, which
`includes extracting and storing reference data from a fin-
`gerprint image of a person whose identity is independ-
`ently verifiable at the time of enrollment, and 2) verifica-
`tion, by comparing features of a new fingerprint image
`with the reference data stored during enrollment. To use
`the system, a person first enrolls. In this process, a fin-
`gerprint image is captured and reference data "patches"
`are extracted from this image and stored. The identity
`of an enrolled person can then be verified by comparing
`subsequently captured images to the stored reference
`data. The system may store reference data for more
`than one individual. In this case, provision is made to
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`5
`
`retrieve the appropriate data for verification, based on
`other identifying information supplied by the person,
`such as an account number or user name. In addition,
`the reference data may be stored integrally to the sys-
`tem that performs the verification, or may be stored on
`external media or devices. This includes "smart cards"
`or similar devices, which users would retain and would
`connect to the system when they wished to establish
`their identity.
`[0022] The principal components of the fingerprint
`feature correlator are shown in FIG. 1. These include a
`fingerprint sensor, indicated by reference numeral 10,
`which may be of the capacitive or the optical type, an
`image pre-processor 12, a reference patch determina-
`tion processor 14, reference image storage 16, a corre-
`lator processor 18, and a geometric constraint checking
`processor 20. In outline, the fingerprint image, which is
`initially a gray-scale image, is converted to a binary val-
`ued image in the image preprocessor 12, which also
`performs other pre-processing functions,
`to be de-
`scribed with reference to FIG. 7. In the enrollment proc-
`ess, the reference patch determination processor 14
`then analyzes the binary fingerprint image to identify the
`positions of characteristic features. Smaller sub-images
`(or "patches") containing these features, or a subset of
`these sub-images, are then extracted from the complete
`fingerprint image. Image processing operations are ap-
`plied to these sub-images, known as reference "patch-
`es," to enhance the reliability of the subsequently per-
`formed verification process. The reference patches are
`stored in the reference image storage 16 for use in the
`verification process.
`[0023]
`In the verification mode of operation, the binary
`image from the image preprocessor 12 is transmitted to
`the correlator processor 18, which also retrieves the ref-
`erence patch images from the reference image storage
`16. Details of operation of the correlator processor 18
`will be discussed below, but briefly the processor com-
`pares each reference patch to a binarized subject fin-
`gerprint image over a full range of positions and orien-
`tations, and attempts to find a set of one or more candi-
`date match positions for each reference patch. The cor-
`relator processor 18, therefore, identifies for each refer-
`ence patch those positions and orientations (if any) at
`which the reference patch is highly correlated with the
`subject image. These data are forwarded to the geomet-
`ric constraint checking processor 20, which also re-
`trieves reference patch positions from the reference im-
`age storage 16. The geometric constraint checking
`processor 20 analyzes these positions to find the max-
`imum number of candidate match positions having rel-
`ative positions that are similar to the relative positions
`of the reference patches. The decision to accept the ver-
`ification print as a match to the reference data is based
`on this number.
`[0024] As will be further discussed below, the corre-
`lator processor 18 in the preferred embodiment of the
`invention is implemented as an application specific in-
`
`ASSA ABLOY Ex 1033 - Page 5
`ASSA ABLOY AB, et al. v. CPC Patent Technologies Pty Ltd.
`IPR2022-01094 - U.S. Patent No. 8,620,039
`
`

`

`9
`
`EP 0 918 300 B1
`
`10
`
`tegrated circuit chip, known simply as an ASIC chip. The
`ASIC implementation allows the correlation process to
`be performed extremely rapidly, by means of high-
`speed hardware that makes good use of parallel
`processing in the correlation. The functions of the image
`preprocessor 12,
`the reference patch determination
`processor 14 and the geometric constraint checking
`processor 20 are, in the presently preferred embodi-
`ment of the invention, performed in a conventional pro-
`grammable microprocessor, such as a reduced instruc-
`tion set computer (RISC) processor. It will be apparent,
`however, that other implementations are possible, but
`the speed advantage the present invention provides is
`attributable in large measure to the use of the ASIC chip
`18 for the feature correlation process.
`[0025] FIG. 3 is a sample fingerprint image reduced
`to binary form by the image preprocessor 12, and shows
`the positions of multiple reference patches, in square
`outlines, selected to identify the fingerprint. As will be
`discussed, the reference patches are selected to con-
`tain combinations of bifurcations of ridges and valleys
`in the fingerprint image. The combination of the loca-
`tions and features of the reference patches is used to
`identify the fingerprint uniquely without having to store
`an entire reference fingerprint image during enrollment
`and without analyzing the entire fingerprint image during
`verification.
`[0026] FIG. 4 shows a group of twenty-five reference
`patches, after conversion to a skeletonized trinary im-
`age format. In this form, only the centerlines of ridges
`and valleys are retained, and are stored as bits of op-
`posite polarity. For example, ridges may be depicted as
`black images and stored as "1" bits , while valleys are
`depicted as white images and stored as "0" bits. The
`remaining areas of each patch are depicted as gray im-
`ages. Each picture element, known as a pixel, is stored
`as a two-bit data element. One bit is used to indicate
`whether the pixel is black or white, and the other bit is
`used to indicate whether the pixel has "don't care" or
`gray status.
`[0027] FIG. 5 illustrates how the reference data
`shown in FIG. 4 are used to verify a different image of
`the same finger. This figure shows a binarized and
`cropped fingerprint image with reference patches from
`the set shown in FIG. 4 overlaid on it. The patches are
`shown in matching positions that satisfy the geometric
`constraints, as found by the verification process. A com-
`parison of FIGS. 3-5 shows that,
`for this example,
`matches for many reference patches were found in the
`correct relative positions. In contrast, FIG. 6 shows a
`similar binary image for a print that does not match the
`one in FIG. 3. In this case, only two of the reference
`patches match in the correct relative positions.
`
`Image Preprocessing:
`
`[0028] As shown in FIG. 2, preprocessing the finger-
`print image includes image capture and quality check-
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`6
`
`ing, indicated in block 22, and image processing, indi-
`cated in block 24. These functions are performed in sub-
`stantially the same manner in both the enrollment mode
`and the verification mode of operation. The mode is de-
`termined by a switch 26, which is typically manually op-
`erated. A practical system must include means for in-
`suring that the enrollment mode can be activated only
`by authorized persons. The position of the switch 26 de-
`termines whether the binary image resulting from image
`processing is used in enrollment or in verification. The
`functions of image quality checking and processing are
`shown in more detail in FIG. 7.
`[0029] After the fingerprint image is captured from the
`fingerprint sensor 10 (FIG. 1), a quality check of the
`gray-scale image is performed, as indicated in block 28
`(FIG. 7). The primary purpose of the quality check is to
`ensure that the image has not been distorted by too
`much or too little pressure between the finger and the
`fingerprint sensor. If the user applies too much pressure,
`the ridge images tend to merge together. Similarly, too
`little pressure may cause the ridges to break up. The
`quality check performs a rapid analysis of the ratio of
`ridge to valley area and aborts further processing if the
`image is not within prescribed limits. The next step in
`image processing, as indicated in block 30, is to distin-
`guish the fingerprint area from the surrounding or back-
`ground image. This reduces the amount of processing
`required in the correlation step, and reduces the possi-
`bility of errors due to noise artifacts in the background
`area. Next, as indicated in block 32, the shape of the
`fingerprint image is analyzed and a long axis is identi-
`fied. If necessary, the image is rotated to align the long
`axis with a standardized direction, as indicated in block
`34. All of these image processing steps reduce extrane-
`ous image content and reduce orientation uncertainty,
`to facilitate the later correlation of two fingerprint images
`taken at different times.
`[0030] After the image has been aligned as needed,
`it is adaptively binarized to convert it to a binary image,
`as indicated in block 36. In adaptive binarization, each
`pixel of the image is converted to either black or white
`according to its gray-scale intensity in relation to a com-
`puted average pixel intensity of all pixels in a surround-
`ing square region. The binary image may then be
`cropped to a standard size, as indicated in block 38, to
`remove empty background areas. Finally, as indicated
`in block 40, a binary image of the fingerprint is ready for
`outpu