Note: Descriptions are shown in the official language in which they were submitted.
CA 02229773 1998-02-17
Doc.No.12-27 Patent
Method of Detecting Biometric Information
Field of the Invention
This invention relates generally to identification of biometric data and more
particularly re]Lates to a method of selectively providing biometric information to a system for
5 identification of individuals.
Background of the Invention
Computer security is fast becoming an important issue. With the proliferation ofcomputers and computer networks into all aspects of business and daily life - financial,
medica]L, education, government, and communications - the concern over secure file access is
10 growing. Using passwords is a common method of providing security . Password protection
and/or combination type locks are employed for computer network security, automatic teller
machines, telephone banking, calling cards, telephone answering services, houses, and safes.
These systems generally require the knowledge of an entry code that has been selected by a
user or has been configured in advance.
Pre-set codes are often forgotten as users have no reliable method of remembering
them. Writing down the codes and storing them in close proximity to an access control
device (i.e. a combination lock) results in a secure access control system with a very insecure
code. Alternatively, the nuisance of trying several code variations renders the access control
system more of a problem than a solution.
Password systems are known to suffer from other disadvantages. Usually, passwords
are specified by a user. Most users, being unsophisticated users of security systems, choose
passwords which are relatively insecure. As such, many password systems are easily
accessed through a simple trial and error process.
A security access system that provides substantially secure access and does not
require a password or access code is a biometric identification system. A biometric
identification system accepts unique biometric information from a user and identifies the user
CA 02229773 1998-02-17
Doc.No.12-27 Patent
by matching the information against information belonging to registered users of the system.
One such biometric identification system is a fingerprint recognition system.
In a fingerprint input transducer or sensor, the finger under investigation is usually
pressed against a flat surface, such as a side of a glass plate; the ridge and valley pattern of
5 the finger tip i s sensed by a sensing means such as an interrogating light beam. In order to
capture an image of a fingerprint, a system is prompted through user entry that a fingertip is
in place for image capture. This is impractical as it likely requires the use of two hands.
Another method of identifying fingerprints is to capture images continuously and to analyse
each image to determine the presence of biometric information such as a fingerprint. This
10 method requires significant processing image transfer times and is therefore, not suited to
many applications.
The use of a biometric im~ging device with a personal computer is considered
inevitable. Uni ortunately, using a biometric input device to transmit frames repeatedly
according to the second method above, wastefully consumes significant bandwidth and
15 processing time. As indicated above, the first method which is commonly used, requires the
use of two hands.
Various optical devices are known which employ prisms upon which a finger whose
print is to be identified is placed. The prism has a first surface upon which a finger is placed, a
second surface disposed at an acute angle to the first surface through which the fingerprint is
20 viewed and a third illumination surface through which light is directed into the prism. In some
cases, the illun.1~ination surface is at an acute angle to the first surface, as seen for example, in
US Patents 5,137,482 and 5,187,748. In other cases, the illumination surface is parallel to the
first surface, as seen for example, in US Patents 5,109,427 and 5,233,404. Fingerprint
identification devices of this nature are generally used to control the building-access or
25 information-access of individuals to buildings, rooms, and devices such as computer tçrmin~
United States patent number 4,353,056 in the name of Tsikos issued October 5, 1982,
discloses an alternative kind of fingerprint sensor that uses a capacitive sensing approach. The
described sensor has a two dimensional, row and column, array of capacitors, each comprising a
CA 02229773 1998-02-17
Doc.No.12-27 Patent
pair of spaced e lectrodes, carried in a sensing member and covered by an insulating film. The
sensors rely upon deformation to the sensing member caused by a finger being placed thereon
so as to vary locally the spacing between capacitor electrodes, according to the ridge/trough
pattern of the fingerprint, and hence, the capacitance of the capacitors. In one arrangement, the
5 capacitors of each column are connected in series with the columns of capacitors connected in
parallel and a voltage is applied across the columns. In another arrangement, a voltage is
applied to each individual capacitor in the array. Sensing in the respective two arrangements is
accomplished by detecting the change of voltage distribution in the series connected capacitors
or by measuring the voltage values of the individual capacitances resulting from local
10 deformation. To achieve this, an individual connection is required from the detection circuit to
each capacitor.
Before the advent of computers and im~ging devices, research was conducted into
fingerprint characterisation and identification. Today, much of the research focus in biometrics
has been directed toward improving the input transducer and the quality of the biometric input
15 data. Fingerprint characterization is well known and can involve many aspects of fingerprint
analysis. The analysis of fingerprints is discussed in the following references which are
hereby incorporated by reference:
Xiao Qinghan and Bian Zhaoqi,: An approach to Fingerprint Identification By Using the
Attributes of Feature Lines of Fingerprint," IEEE Pattern Recognition, pp 663, 1986;
20 C.B. Shelman, " Fingerprint Classification - Theory and Application," Proc. 76 C~ h~n
Conference on Electronic Crime Countermeasures, 1976;
Feri Pernus, Stanko Kovacic, and Ludvik Gyergyek, "Minutaie Based Fingerprint
Registration," [EEE Pattern Recognition, pp 1380, 1980;
J.A. Ratkovic, F.W. Blackwell, and H.H. Bailey, "Concepts for a Next Generation
25 Automated Fingerprint System," Proc. 78 C~ n Conference on Electronic Crime
Countermeasures, 1978;
K. Millard, " A.n approach to the Automatic Retrieval of Latent Fingerprints," Proc. 75
Carnahan Coni'erence on Electronic Crime Countermeasures, 1975;
CA 02229773 1998-02-17
Doc.No.12-27 Patent
Moayer and K.S. Fu, "A Syntactic Approach to Fingerprint Pattern Recognition," Memo Np.
73-18, Purdue University, School of Electrical Engineering, 1973;
Wegstein, An Automated Fingerprint Identification System, NBS special publication, U.S.
Department of'Commerce/National Bureau of Standards, ISSN 0083-1883; no. 500-89, 1982;
5 Moenssens, Andre A., Fin~erprint Techniques, Chilton Book Co., 1971; and,
Wegstein and J.F. Rafferty, The LX39 Latent Finger~rinl Matcher, NBS special publication,
U.S. Department of Commerce/National Bureau of Standards; no. 500-36, 1978.
Object of the Invention
It is an object of this invention to provide a method of determining the presence of a
10 fingerprint image or of a suitable image for analysis.
Summary of the Invention
In accordance with the invention, there is provided a method of detecting biometric
information comprising the steps of:
a) providing an electronic representation of a captured image comprising an array of pixels;
15 b) selecting a predetermined subset of pixels less than all of the pixels in the array of pixels
representing thR image, each pixel having a predetermined location;
c) analysing, ~A~ith a processor, the subset of pixels to detect a pattern indicative of biometric
information within the captured image; and,
d) in dependence upon the analysis, providing an indication.
In accordance with the invention, there is provided a method of detecting biometric
information comprising the steps of:
a) providing an electronic representation of an image comprising an array of pixels
b) selecting a predetermined subset of pixels less than all of the pixels in the array of pixels
25 representing the image, each pixel having a predetermined location;
c) analysing, w ith a processor, the first subset of pixels to detect a pattern indicative of
biometric information within the representation of the image;
d) selecting a second subset of pixels within the electronic representation of the image;
CA 02229773 1998-02-17
Doc.No.12-27 Patent
e) analysing, ~ ith a processor, the second subset of pixels to determine a stability of the
image; and,
f) when biometric information is detected and the image is stable, characterising the
biometric information within the representation of the image.
s
In accordance with the invention, there is provided a method of detecting biometric
information comprising the steps of:
a) providing an electronic representation of an image;
b) selecting a predetermined subset of pixels less than all of the pixels in the array of pixels
10 representing the image, each pixel having a predetermined location;
c) subtracting values of pixels within the first subset from the value of adjacent pixels within
the first subset;
d) sl-mming absolute values of the differences to form a value;
e) comparing the value to a predetermined threshold value; and,
15 d) when the comparison is indicative of biometric information within the image frame,
characterising the biometric information.
It is an advantage of the present invention that a separate indication of the presence of a
fingerprint is n,ot necessary to capture a fingerprint.
20 Brief Descripl;ion of the Drawings
An exemplary embodiment of the invention will now be described in conjunction
with the attached drawings, in which:
Fig. 1 is a flow diagram of a method of capturing biometric information according to the
prior art;
25 Fig. 2 is a flow diagram of another method of capturing biometric information according to
the prior art;
Fig. 3 is a simplified block diagram of a device according to the prior art;
Fig. 4 is a simplified block diagram of a device according to the invention;
CA 02229773 1998-02-17
Doc.No.12-27 Patent
Fig. Sa is a simplified block diagram of a device according to the invention wherein the
device is shown connected to a computer;
Fig. 5b is a sirnplified block diagram of a device according to the invention wherein the
device is shown connected to a computer;
5 Fig. 5c is a simplified block diagram of a device according to the invention wherein the
device is shown connected to a computer;
Fig. 6 is a sim]plified flow diagram of a method according to the invention;
Fig. 7 is a sim]plified flow diagram of a method according to the invention;
Fig. 8 is a sim]plified diagram of an image of a fingerprint; and,
10 Fig. 9 is a sim]plified flow diagram of a method according to the invention; and,
Fig. 10 is a sinnplified flow diagram of a method according to the invention for execution in a
single processor; and,
Fig. 11 is a sinnplified flow diagram of a method according to the invention of storing images
of biometric information and actuating a button operated device in dependence upon
15 detection of a ]presence of biometric information within a captured image.
Detailed Description
The invention is described with respect to fingerprint registration. The method of this
invention is applicable to other biometric information as is evident to those of skill in the art.
A common method of capturing biometric information according to the prior art isshown in Fig. 1. A fingertip is pressed against a fing~ fitlt im~ging means in the form of an
optical fingerprint imager or a capacitive fingerprint imager. An image of the captured
fingerprint is displayed on a monitor in the form of a computer display; an operator
determines the fingerprint image is suitable and actuates a fingerprint recognition system.
The system accepts the displayed fingerprint image as an input image and characterises that
image to identify an originator of the fingerprint. Once identified, appropriate action is taken.
CA 02229773 1998-02-17
Doc.No.12-27 Patent
Referring to Fig. 2, a simplified flow diagram of another method according to the
prior art is shown. The method is applicable to standalone biometric identification systems
having no display proximate a biometric sensor. A fingertip is pressed against a fingerprint
im:~ging means in the form of an optical fingerprint imager or a capacitive fingerprint imager.
5 An image of the captured fingerprint is provided to a system as an input image and is
characterised by the system. The characterisation is used to register the image against other
images to determine an originator of the fingerprint. When the characterisation is of an
unsuitable quality or registration does not occur within predetermined parameters, a further
image is captured. As a large proportion of time and processing required to register biometric
10 information is consumed by image characterisation, this method is often slow and costly.
Since this method is applicable for the most part to situations wherein a dedicated process is
devoted to identification, the increased bandwidth and the increased computation time may
be acceptable.
Referring to Fig. 3, a simplified block diagram of a device according to the prior art is
15 shown. A contact imager captures an image of of a fingerprint. The contact imager is in the
forrn of an optical fingerprint imager or a capacitive fingerprint imager. An electronic
representation of the image is digitised and provided as an array of pixels to a processing and
characterising means in the form of a computer or a dedicated processing system. The
fingerprint is characterised to facilitate registration and, when characterisation is sufficient
20 for registration to proceed, registration of the fingerprint with previously stored biometric
templates is atl:empted.
Referring to Fig. 4, a simplified block diagram of a device according to the invention
is shown. An im~ging means in the form of a contact imager captures an image of biometric
information in the form of a fingerprint. Contact imagers are well known within the art of
25 fingerprint capture and analysis. When non-contact biometric im~gin~ is desired, for example
a retinal scan, lhe imager is not a contact imager. An electronic representation of the image to
be captured is digitised and provided to an analysing means in the form of a processor. The
analysing means selects a subset of pixels from the digitised image. Preferably, the subset is a
small fraction of the image's pixels. Also preferably, the subset is a predetermined subset in
CA 02229773 1998-02-17
Doc.No.12-27 Patent
the form of a row, a column, or an array. When the subset is not a predetermined subset,
analysis is facilitated by restricting subset geometries to those that are capable of being
analysed by the analysis implemented according to this method. Examples of restrictions
include, a randLom selection of a central row of pixels from an image or an n by m array of
5 pixels within a~ predetermined region of the image. The analysing means analyses the subset
of pixels to determine a presence of characteristics indicative of biomekic information.
Examples of characteristics include patterns, oscillations, and texture. When biometric
information is likely contained within the image, the digitised image is provided to
processing ancl characterising means in the form of a computer or a dedicated processing
10 system. The fingerprint is characterised to enable registration and, when characterisation is
sufficient for registration to proceed, registration of the fingerprint with previously stored
biometric templates is attempted. When biometric information is unlikely to be contained
within the image, the digitised image is not provided to the processing and characterisation
circult.
Optionally, when the likelihood that biometric information is contained within an
image is low, the image is provided to a different processor or processing routine executing
on a same proc essor for performing video processing orthe image is provided to the
processing and characterisation means regardless of the likelihood that biometric information
is contained therein.
Optionally, the analysing means and the processing and characterising means are a
same microprocessor. When this is the case, both methods are executed by the same
processor. Advantageously, this reduces processing of image frames wherein biometric
information remains undetected. When a single processor is employed, preferably an
indication of the likelihood of biometric information contained within the image is provided
upon analysis cmd not the entire image; the image is already available to the processor. It is
apparent to those of skill in the art that when the representation of the image is stored in
memory and is accessible, an indication of the result of applying a method of detecting
biomekic information provided to the processing and characterisation means in the form of a
CA 02229773 1998-02-17
Doc.No.12-27 Patent
variable, a signal, execution of a procedure, or provision of a representation of an image
provides a same result.
Referring to Figs. 5a, 5b, and 5c, a contact imager and a processor are shown indashed line. In Fig. 5a, the analysing means is contained within the imager. In Fig. 5b, it is
5 contained with~in a computer cont~inin~ the processor. In the diagram of Fig. 5b, the
analysing means is contained within the processing and characterising means. Referring to
Fig. 5c, the analysing means is contained within a separate digitising means in the form of a
frame grabber for digitising an analogue video signal and analysing image frames to detect a
likelihood of a presence of biometric information.
Referring to Fig. 6, a simplified flow diagram of an embodiment of the invention is
shown. Image information is provided to an analysing means. Each image is analysed to
determine whether characteristics present in suitable biometric information are present in a
current image. When present, the image is provided to the processing and characterising
means. The analysing means is incorporated within an image capture device for capturing
15 biometric info]mation. Alternatively, the analysing means is incorporated within a same
processor as the processing and characterising means;. or,, the analysing means may be
incorporated into a different processor from that of the processing and characterising means
and not contained within the imager.
In the embodiment of Fig. 5a, the processor is incorporated within an image capture
20 device for capturing biometric information. An output driver from the image capture device
is disabled to prevent tr~n~mi~ion of images to a host computer. An analysing means,
incorporated ~ithin the image capture device, analyses an image to detect a presence of
biometric information within the image. When present, the output drivers are enabled and the
image is provided to the host computer. Otherwise, a next image is captured. Alternatively,
25 images with biometric information and those without biometric information are transmitted
to the computer and an indication of the presence of biometric information is transmitted
with images w]herein a presence of biometric information is detected. The indication is in the
CA 02229773 1998-02-17
Doc.No.12-27 Patent
form of an interrupt signal, information encoded within the image, or other predetermined
.
mdlcla.
Referring to Fig. 7, a more detailed flow diagram of a method according to the
invention is shown. An image is captured by an image capture means. The image is digitised
5 and provided to an analysing means. The digitised image comprises an array of pixels. A row
of pixels within the image is selected for analysis. The row is analysed to determine a
characteristic indicative of a presence of biometric information. Some methods of analysis
are discussed below.
A linea~r transform on the pixels of the row allows for a fast and simple analysis of
10 row characteristics. An example is
O(x) = ~ If (Xj ) - f (Xj_, )
Xj ~X
The above equation determines a sum total absolute change in pixel value betweenpixels in the row. The sum total is dependent on oscillations in light and dark pixel values.
For a fingerprint, the sum total is proportional to a number of ridges across the fingerprint.
15 This number is generally significantly larger than the resolution of a pixel and, for a
fingerprint image comprised of 5 bit pixel values, generally results in values greater than
1000. When non-biometric information is imaged within an image frame, it is likely that
correlations between adjacent pixels result in lower sum totals. Therefore, where O(x) > To
an image is likely to contain biometric information and is provided to the processing and
20 characterising means.
In an embodiment, the row of pixels is correlated with a function in the form of a
square wave f mction or a sine wave function. The function is selected in dependence upon
the form of biometric information imaged. The functions provided as examples are well
suited to finge]print analysis. Optionally, other functions are selected. It is evident to those of
25 skill in the art that correlating functions requires more processing time than the equation
CA 02229773 1998-02-17
Doc.No.12-27 Patent
presented above; however, for some applications and for some forms of biometric
information, the above equation may not function adequately.
Optionally, a plurality of rows, rows and columns, a column, or a plurality of columns
is selected. The selection of diagonals, arrays, or regions is also applicable to the invention.
5 Referring to Fiig. 8, a simplified diagram of a fingerprint is shown in which horizontal ridges
are not present below a substantially central location. When the equation for O(x) set out
above is used l:o analyse a central column, a value for O(x) is possibly less than To O(x) for a
row near a central location is a large value and likely well above a threshold value, To In
order to accownt for errors such as these and to m~int~in flexibility, in the preferred
10 embodiment, at least a row and a column are selected for detection of biometric information
or alternativelv two diagonals, a row and a diagonal or a column and a diagonal. Diagonal
refers to any substantially straight line that is neither a row nor a column. In some
applications, a curved line is used; however, straight lines are easily selected with minim~l
computation and for this reason are described herein.
An imager in the form of a contact im~ging device for im~ging finge~ captures
an image. When a fingerprint is placed upon a platen of the imager, the images captured vary;
first because the fingertip moves, and then, typically, because an automatic contrast circuit
adjusts contrast and brightness within captured images. When a "good" quality image is
desired, it is aclvantageous to wait until an image has stabilised prior to providing same to the
20 processing and characterisation means. This allows each biometric image in the form of a
fingerprint image to have comparable contrast and quality. Alternatively, when only user
identification is desired, image contrast is less important and stabilisation is determined in
dependence upon image location stability.
When an im~gin~ device is used only for capturing biometric information, image
25 stability and determining a likelihood of a presence of biometric information are performed
in any order. Likely, when no biometric information is provided a captured image is stable;
there is little benefit in choosing stability or biometric information detection to precede the
other. Alternatively, when the imager is also used as a video camera for digital im~ging,
CA 02229773 1998-02-17
Doc.No.12-27 Patent
video conferencing, etc., the stability algorithm is preferably run prior to the algorithm for
detection of biometric information. This enables video footage cont~ining moving images to
avoid analysis and may result in reduced processing time.
In the diagram of Fig. 7, once a row is analysed and it is determined that biometric
5 information is likely present within the image frame, the row is analysed for stability.
Optionally, a small subset of pixels in a row is analysed for stability. An equation for
analysing stability,
S(x) = ~ f, (xj ) - f,, (xj)I,
Xj ~x
incorporating analysis of location and contrast is easily and quickly computed. When
10 compensation for changes in contrast is desired, the function f, (Xj ) is altered to account for
variations in brightness. A suitable equation is,
s(X) = ~ f~ - f"(xj),
where K is a brightness or contrast scaling factor determined in dependence upon CCD
characteristics and a correlation between a current frame and a previous frame. When only
15 contrast has changed, the scaling factor will compensate substantially for the lighting
differences.
Stability is evaluated, and when S(x) > Ts, a threshold for the stability, the image is
determined to be stable. When an image is both stable and likely to comprise biometric
information, the image is provided to a processing and characterising means.
Referring to Fig. 9, a method is shown according to the invention wherein a subset of
pixels is selected in place of the row or column shown in Fig. 7. For stability, selecting a
small number of pixels in an array provides a good estimation of stability. For example, a
3x3 pixel array in place of an entire row or column - usually comprising in excess of 200
pixels each - provides an excellent indication of stability. Of course, the 3x3 pixel array must
12
CA 02229773 1998-02-17
Doc.No.12-27 Patent
reflect a location where biometric information is provided or else stability is measured
against background im~gin~ and noise.
Similarly, for other forms of biometric information in the form of palm prints, retinal
scans, etc., a suitable selection of a subset of pixels is made. The selection and evaluation is
5 dependent upon the biometric information type.
When used with a personal computer, a contact im~ging device providing a plurality
of successive images for characterisation and registration, consumes a significant portion of
computer resources. It is advantageous to reduce resource allocation by vetting images either
within the contact imager or within the personal computer to reduce processing of images
10 that are not well suited to characterisation and registration.
Referring to Fig. 10, a method according to the invention for execution within asingle processor is shown. An image is captured, digitised, and provided to the processor.
According to the invention, a subset of pixels in the form of a row and a column are analysed
to detect a presence of biometric information. When biometric information is detected -
15 biometric information is likely present within the image - characterisation of the detected
biometric information proceeds. Alternatively, a next image is analysed for biometric
information. Performing an analysis on a subset of pixels to detect biometric information,
reduces processing time required for empty frames and for frames cont~inin~ non-biometric
image data. Further, such analysis obviates a need for a user to indicate a presence of a
20 "good" image of biometric information.
Referring to Fig. 11, a simplified flow diagram of a method of monitoring users of
button operated devices is shown. A button operated device in the form of a fire alarm is
provided with an actuating button. The actuating button is in the form of a platen upon which
a fingertip is placed. Alternatively, the actuating button is a button or a handle. When the
25 actuating button is pressed, a method according to this invention is employed to determine a
presence of biometric information. As no user identification or authorisation is necessary for
a fire alarm, a more reliable fingerprint detection algorithm is executed. Alternatively, a same
algorithm is executed.
13
CA 02229773 1998-02-17
Doc.No.12-27 Patent
When biometric information is detected upon the button, a function actuated by the
button is enab]ed and the biometric information is imaged and a representation of the image
is stored. Using the method of Fig. 10, allows police to locate actuators of false fire alarms.
Employing a nnethod according to Fig. 10 in a gun trigger, allows for identification of those
5 who have firecl a gun. Similarly, for voting, each individual is provided access to vote in
dependence upon a biometric actuated switch. Same biometric information is later identified
to identify voters voting a number of times. Optionally, further information in the form of a
time and date ,tamp is stored with the representation of the image.
Another application is for building access. A building entry system requires provision
10 of biometric information to access the building. The information is not registered, but is
stored with a time and date stamp. Should a problem with vAn~ m or theft occur within the
building, biometric information from those individuals accessing the building is available.
Of course, many other applications of storing a fingerprint to determine who used a
device, alarm, or system are envisioned. A key aspect of such a device is that it distinguishes
15 biometric input information from gloves, pencils, tools, or finger shaped objects in order to
record useful information regarding the actuator. To this end, the method described herein is
employed to iclentify biometric information within an image required for actuation of the
device.
Numerous other embodiments may be envisaged without departing from the spirit and
20 scope of the invention.
14
