A composite image generating method, and a fingerpring detection apparatus

(54) (56) (57)

INVENTOR INVENTOR

REPRESENTATIVE TITLE

Telefonaktiebolaget LM Ericsson, Henrik Benckert, Lund SE

126 25 Stockholm SE

Ström & Gulliksson AB

Method for generating a composite image and an apparatus for detecting fingerprints

CALLED PUBLICATIONS: - - SUMMARY:

An apparatus for detecting fingerprints has a fingerprint sensor (10) which produces a sequence of at least partially overlapping fingerprint images (13) as a finger (11) is moved relative to the fingerprint sensor. The apparatus also has a processing device coupled to the fingerprint sensor and which produces a complete fingerprint image (14) by calculating a relative displacement between respective fingerprint images and accordingly combining the fingerprint images. The processing device determines the relative displacement between a first fingerprint image and a second fingerprint image by selecting a plurality of subareas in the first fingerprint image. For each sub-region, a respective correlation is determined with the other fingerprint image. Then a linear combination of the respective correlations is calculated, and finally the relative offset is determined from the calculated linear combination.

<img file="SE515239C2_D0001.tif" />

The numbers in brackets indicate international identification code, INID code. Letters in clamps indicate international document code.

515 239

2001-03-08 P: \ 1874-118 sv overs II.doc BA / LJ

Technical area

In general, the present invention relates to the biometric field, i.e., identification of an individual based on his or her physiological or behavioral characteristics. More particularly, the present invention relates to a method for generating a composite image from a sequence of partial images representing different but at least partially overlapping regions in a body-specific pattern, for example a fingerprint.

The invention further relates to an apparatus for detecting fingerprints of a type having a fingerprint sensor, which is arranged to produce a sequence of at least partially overlapping fingerprint images, when a finger moves relative to the fingerprint sensor, said type further having a processing device, which is coupled to the fingerprint sensor and which is arranged to produce a complete fingerprint image by determining relative displacements between the respective fingerprint images and, as a result, combining the fingerprint images.

The prior art

Fingerprint biometric systems are used in various applications to identify an individual user or verify his or her authority to perform a given action, to access a restricted access area, etc. 'Fingerprint identification is a reliable biometric technique, as two fingerprints from different individuals do not have the same body-specific pattern of elevations and depressions.

515 239

2001-03-08 P: \ 1874-118 sv overs 11. doc BA / LJ

In addition, the fingerprint pattern remains unchanged for an individual throughout their life.

Some fingerprint detection systems work by creating a complete image of a fingerprint in one step; the surface of the finger is recorded by, for example, producing a photographic grayscale image, which can later be analyzed by image processing methods to determine whether or not the recorded fingerprint corresponds to stored reference data.

Other fingerprint detection systems do not produce the entire fingerprint image in a single step. Instead, the surface of the finger is scanned, giving rise to a sequence of fingerprint images or discs which are combined into a composite image representing the entire fingerprint. EP-A2-0 929 050 discloses a semiconductor based fingerprint detector with capacitive scanning, which includes a set of capacitive sensing elements. When a user slides his finger over the sensing elements, a sequence of partial fingerprint images of the capacitive sensing elements is produced. The partial fingerprint images are put toge ther into a composite fingerprint image.

EP-A1-0 813 164 relates to a digital fingerprint reading system comprising a sensor in the form of a rod which is wider than the typical width of a finger but which is relatively narrow compared to the length of the finger. The sensor is an integrated circuit with an active layer, which is sensitive to pressure and / or temperature. When a user slides his finger over the sensor, the sensor will scan the fingerprint and deliver a sequence of fingerprint images, each having a size substantially corresponding to the sensor's range of sensitivity, and which are partially overlapped. A processing unit receives the sequence of fingerprint images from the transducer and is arranged to reconstruct a complete fingerprint image. As soon as it does

515 239

2001-03-08 P: \ 1874-118 en overs Il.dOC BA / LJ complete fingerprint image obtained, it can be compared with a reference image stored on, for example, a smart card, to verify the holder of the smart card.

Fingerprint sensors of the above type, which provide a sequence of partially overlapping fingerprint images, have several advantages, especially in the field of miniaturized or portable electronic devices. Moderate cost and low power consumption, together with small demands on mounting surface, are important advantages in this regard. However, miniaturized or portable electronic devices have limited data processing capacity; Both the data processor (CPU) and electronic memories used therein are adapted for portable use and consequently do not have as excellent performance as, for example, some stationary installations.

It is a computationally intensive operation to combine a sequence of partially overlapping fingerprint images into a composite image representing an entire fingerprint. To compile the composite fingerprint image from a number of consecutive fingerprint images, one offset vector must be calculated between each image pair. The standard method is to use autocorrelation, whereby a first fingerprint image and a subsequent second image are read, and an image or correlation map is produced in a displacement coordinate system. The correlation map usually contains a global maximum at a point corresponding to the offset vector.

Specifically, in the case of digital fingerprint images in grayscale, two two-dimensional matrices of integers are fed into the autocorrelation procedure, which results in a two-dimensional matrix of integers, these integers being illustrated as grayscale intensities. As already mentioned, autocorrelation is computationally intensive and difficult to perform in real time with a data processor that is optimized

515 239

2001-03-08 P: \ 1874-118 sv overs II.doc BA / LJ for low power consumption and miniaturized or portable applications. In addition, the calculation work grows squarely with the size of the calculation area.

Summary of the Invention

In view of the above problems, it is an object of the invention to facilitate the production of a composite image, representing a body-specific pattern such as a fingerprint, from a sequence of at least partially overlapping real-time images using much less force than in conventional methods, which allows small sensors (which cannot produce a complete image in one step) for use in miniaturized or portable applications.

This object is achieved by a method and apparatus according to the appended independent claims. Specifically, a composite image can be produced from a sequence of at least partially overlapping images by performing the following steps for the sequence of images. A predetermined number of subareas (which can be as small as 1x pixel) is selected in a first image. For each of these sub-areas, a correlation is determined with a second image, which follows the first image. Then, a linear combination of the correlations for all subareas is calculated, and finally, from the calculated linear combination, the offset between the first and second images is determined. Once the displacement is known, the first and second images can be correctly compiled. By repeating the above procedure, one can gradually compile a composite image of a fingerprint or the like.

The object is also achieved by an apparatus for detecting fingerprints having a fingerprint sensor arranged to produce a sequence of at least partially overlapping fingerprint images, and a processing device arranged to perform the above method.

515 239

2001-03-08 P: \ 1B74-118 sv overs II.doc BA / LJ

Other objects, features and advantages of the present invention will become apparent from the following detailed description, the appended claims and the drawings.

Brief description of the drawings

A preferred embodiment of the present invention will now be described in more detail with reference to the accompanying drawings, in which:

Figure 1 is an overview view of a portable electronic device, in the form of a mobile phone, in which the method and apparatus for detecting fingerprints according to the present invention can be used;

FIG. 2 illustrates the overall operation principle of a scanning type fingerprint sensor producing a sequence of partially overlapping fingerprint images;

Figure 3 is a block diagram illustrating the essential components of the mobile phone illustrated in Figure 1;

FIG. 4 is a flow chart illustrating the steps of the method of the preferred embodiment;

Fig. 5 illustrates a sequence of partially overlapping fingerprint images and the steps taken during a preprocessing phase of the method of the preferred embodiment;

Fig. 6 is an enlarged view of a portion of a fingerprint image and illustrates steps taken for this image during an autocorrelation phase of the method;

FIG. 7 illustrates a correlation map as a result of said autocorrelation as well

FIG. 8 illustrates how individual correlation maps are assembled in a linear combination to generate a total correlation map from which the offset vector is determined.

515 239

2001-03-08 P: \ 1874-118 sv overs II.doc BÄ / LJ

Detailed account

In Figure 1, a portable electronic device is shown in the form of a mobile telephone 1. The mobile telephone 1 will be used as an example, in a non-limiting manner, in a possible portable application, where the method and apparatus according to the invention can be used. The mobile telephone 1 comprises a first antenna 2, which is arranged to establish and maintain a first radio link 2 'to a base station 8 in a mobile telecommunication system such as GSM (Global System for Mobile communications). The telephone 1 also has a second antenna 3 which is used to communicate with a remote device 9 over a second radio link 3 '. The second antenna 3 may, for example, be intended for Bluetooth or other type of complementary short-range data communication, for example, on the 2.4 GHz ISM (Industrial, Scientific and Medical) band.

Like any other modern mobile phone, the telephone 1 comprises a speaker 4, a display 5, a set of cursor keys 6a, a set of alphanumeric keys 6b and a microphone 7. In addition, the telephone 1 comprises a fingerprint sensor 10, which is part of the fingerprint detection apparatus according to and used by the method of the invention.

According to the preferred embodiment, the fingerprint sensor 10 is a thermal silicon-based fingerprint sensor called FingerChip ™ which is commercially available from Thomson-CSF Semiconducteur Specifiques, Route Départementale 128, BP 46, 91 401 Orsay Cedex, France. The fingerprint sensor FingerChip ™ utilizes the heat generated by the finger to produce an eight-bit grayscale image of a 500 dpi fingerprint. The FingerChip ™ sensor's image receiving surface measures 1.5 mm x 14 mm. When a finger 11 is moved in a direction 12 over the fingerprint sensor 10 (see FIG. 2), the sensor 10 produces a sequence of partially overlapping fingerprint images 13a,

515 239

2001-03-08 P: \ 1874-118 sv overs II.doc BA / LJ

13b, ..., 13x every 20 milliseconds, where each image represents an area approximately equal to the image capture area above. The images are applied to a data processor / controller 15 in the mobile phone 1 (see FIG. 3). The data processor / controller 15 will thereby produce a composite fingerprint image 14, which will be described in more detail later.

Alternatively, one can use virtually any other commercially available fingerprint sensor, for example an optical sensor, a capacitive sensor and the like, provided that such sensor can produce a sequence of partially overlapping fingerprint images, as described above.

As shown in FIG. 3, the mobile telephone 1 comprises the data processor / controller 15, which as already mentioned is connected to the fingerprint sensor 10. The data processor / controller 15 is also connected to a primary memory 16, for example some commercially available RAM. It is also connected to a permanent memory 17 which can be implemented by any commercially available non-volatile electronic, magnetic, magnetooptical or similar memory.

The permanent memory 17 includes program code 18 which defines a set of program instructions which, when executed by the data processor / controller 15, performs the method of the invention as well as many other tasks in the mobile phone 1. The permanent memory 17 also includes fingerprint reference data 19 used by the controller 15, after compiling a composite fingerprint image, to compare this image with said fingerprint reference data to determine whether or not the holder of the finger 11, i.e. the user of the mobile phone 1, has the identity represented by said fingerprint reference data 19.

515 239

2001-03-08 P: \ 1874-118 sv overs II.doc BA / LJ

In addition to what is mentioned above, the data processor / controller 15 is connected to GSM radio circuits 20 to implement the first radio link 2 'through the antenna 2. The data processor / controller 15 is also connected to a Bluetooth radio 21, which in turn is connected to Bluetooth antenna 3. Finally, the data processor / controller 15 is connected to the display 5.

All of the components described above, including the data processor / controller 15, can be implemented in many different ways by any commercially available components that meet the functional requirements described below. As for the data processor / controller 15, it may be implemented by any commercially available microprocessor, CPU, DSP or any other programmable electronic logic device.

Referring to the remaining FIGS 4-8, the method and apparatus of the preferred embodiment will now be described. Generally speaking, the invention is based on the idea of ​​dividing the image area utilized by successive fingerprint images into several small sub-areas. As explained above, since the calculation grows squarely with the current image area, the resulting total calculation can be drastically reduced thanks to the invention. Once autocorrelation has been performed for these smaller subareas, and as soon as respective correlation maps have been produced, a total autocorrelation map is calculated as a linear combination of the correlation maps from the autocorrelations with the individual subareas. The displacement vector between two consecutive images is determined from the total autocorrelation map, possibly by applying a MaximumLikelihood procedure with respect to the total correlation map, if more than one candidate for the displacement vector appears to be present.

515 239

2001-03-00 P: \ 1874-118 sv overs II.doc BA / LJ

Since the autocorrelation, which is an important part of the process of assembling a plurality of partially overlapping fingerprint images into a composite fingerprint image, can be accomplished with significantly less computational power than conventional autocorrelation, the invention makes it possible to utilize a small fingerprint sensor in a miniaturized or portable application. low power consumption as well as limited computational resources.

Referring to FIG. 4, a fingerprint autocorrelation routine 100 is illustrated, which is an important part of the method of the invention. After necessary initialization and the like, the routine enters a first phase or preprocessing phase 110. In a step 112, a first fingerprint image is received by the data processor / controller 15 from the fingerprint sensor 10. In a subsequent step 114, the grayscale pixel intensity of the first fingerprint image is analyzed. A plurality of small and geographically dispersed subareas # 1 - # are then selected, in a step 116, of the first fingerprint image, as illustrated in greater detail in FIG. 5. The selected subareas are those which are statistically unusual with respect to the image as a whole. regarded. The reason for this is that it becomes easier to auto-correlate the selected sub-areas with the subsequent fingerprint image.

In the left column of FIG. 5, a number of successive fingerprint images 13a, ... 13j, which have been received from the fingerprint sensor 10. are illustrated. , where the selected unusual subareas have been indicated at the respective center in the form of small white squares. For each fingerprint image, in the preferred embodiment, a total of six unusual sub-areas are selected. An enlargement of the last image 13j-13j 'is given at the bottom of FIG. 5. This enlargement shows the selected

515 239

2001-03-08 P: \ 1874-118 sv overs 11. doc BA / LJ unusual sub-areas 22a, 22b, 22c, 22d, 22e and 22f more clearly.

According to the preferred embodiment, each selected subarea has a size of 1x pixel, that is, a single pixel with a grayscale value between, for example, 0-255. In a fingerprint image representing a portion of a fingerprint, unusual areas are usually those which are either of a very high intensity (ie, are essentially white) or have a very low intensity (ie, are essentially black). Accordingly, in the preferred embodiment, the selected subareas are such pixels, which are preferably either white (or nearly white) or black (or nearly black) according to the preferred embodiment, three white pixels and three black pixels as subareas # l-# 6 in the fingerprint image. . However, in some situations (such as image saturation), it may be more appropriate to choose other than white or black pixels as unusual areas. Alternatively, larger unusual subareas can be selected in the fingerprint image, for example, areas of 4x4 pixels. In this case, an unusual area may be an area containing an intensity gradient (change from black to white or vice versa). Generally speaking, by utilizing a larger size for each sub-area, you can content yourself with using a smaller number of sub-areas, and vice versa.

Once the unusual subareas have been selected in step 116, execution proceeds to a second phase or autocorrelation phase 120. The purpose of the autocorrelation is to identify the respective subareas selected during the preprocessing of a particular fingerprint image in a subsequent fingerprint image. Since statistically unusual pixels are used as sub-areas, it is likely that exactly a match will be found in a search area in the subsequent fingerprint image. The combined autocorrelation leads to

515 239

2001-03-08 P: \ 1874-118 sv overs II.doc BA / LJ at least one candidate for displacement vector. An offset vector represents the relative offset between a given fingerprint image and its successor. Once the displacement vector has been determined, the two fingerprint images can be combined to successively compile the composite fingerprint image.

From a general point of view, autocorrelation coefficients Ci, j represent the degree of correlation between adjacent data observations (consecutive fingerprint images) in a time series. An autocorrelation that can be utilized within the scope of the invention is^cij = X_x,_y (/ X t) - + i, y + J) Y where f (x, y) is a selected sub region in a given fingerprint image and g (x, y) is a sub region in the subsequent fingerprint image. The purpose of the autocorrelation, which consists in finding the largest correlation between two fingerprint images, is achieved by computing cij for a search area 23 (FIG. 6) in subsequent fingerprint image 13. The best agreement is found by minimizing ci, j over the search area 23. According to the preferred embodiment, the search area consists of 19x19 pixels. However, other search areas, even non-square ones, are equally possible.

The use of the above-described autocorrelation is illustrated in FIG. 6, where a portion of a subsequent fingerprint image 13 is shown. The small square 22 represents one of the sub-areas selected during the preprocessing. The size of the sub-area 22 and the search area 23 have been enlarged in FIG. 6 for reasons of clarity. Center 24 of the search area 23 in the subsequent fingerprint image represents the position in the previous fingerprint image where the sub-region 22 was located. By minimizing Cij over the search area 23 in the subsequent fingerprint image on

515 239

2001-03-08 PA1874-118 sv overs 11. doc BA / LJ described above, one can find the position of the sub-region 22 in the subsequent fingerprint image 13.

The result of the autocorrelation of an individual subarea 22 relative to a search area 23 is a 19x19 pixel large correlation map 25, illustrated in FIG. 7. Minimum of the autocorrelation Ci.j appears as a dark pixel 28 in the correlation map 25. An offset vector 26 can then be easily is determined and has its starting point at the center 27 of the correlation map 25 and its end point at pixel 28 with minimal intensity (black pixel).

The above corresponds to step 122 of the flowchart of FIG

4th As already mentioned, in the preferred embodiment, a total of six correlation maps are produced for a total of six subareas 22. In a subsequent step 124, a total correlation map 29 is calculated as a linear combination (sum) of the individual correlation maps 25a, 25b, etc., as shown in FIG. in the overall correlation map 29, it is possible to determine a displacement vector, or often a number of displacement vector candidates.

The reason that, according to the invention, one can perform autocorrelation for several very small and geographically dispersed subareas 22 in consecutive fingerprint images 13, which are finally combined into a total correlation map 29, is that a fingerprint image has a characteristic pattern with lines (elevations and depressions) in different directions. These lines will also appear in the correlation maps. If a sub-area is moved along the fingerprint lines, the correlation will be very strong, with lines appearing. This is also true if the sub-area is moved by the width of a line. When the autocorrelation is calculated for parts of the fingerprint, where the lines have different angles, the correlation maps 25 will also show lines in different directions. When a sufficient number of maps 25a,

515 239

2001-03-08 P: \ 1874-118 sv overs 11.doc BA / LJ

25b, ... combined, the lines will cross each other over the total correlation map 29, but there will be a clear overlay at the minimum of the correlation from which the offset vector can be determined.

Often, however, multiple pixels 28 with minimal intensity may appear in a total correlation map 29, which instead of a single offset vector indicates a number of offset vector candidates. These are determined in a subsequent step 126 of the flowchart shown in FIG. 4 and further processed in a post-processing phase 130 of the fingerprint autocorrelation routine 100.

During the post-processing of the total correlation map 29 (or more specifically, the number of offset vector candidates, as determined in step 126), a Maximum-Likelihood estimation procedure is applied to these offset vector candidates, assuming the correct minimum for a particular correlation map 29 (which is determined for a given fingerprint image 13) is probably near the minimum in the corresponding correlation map for the previous fingerprint image. Consequently, the probability that the minimum has been moved from one position to another is proportional to the distance between these minimums. If this probability is maximized over time, one will find the most likely route of movement.

More specifically, an offset vector is defined as the direction and magnitude of offset between two consecutive fingerprint images. As already mentioned, the offset vector appears as a pixel of minimal intensity (black pixel) in a correlation map. Furthermore, we define a transition probability as the probability that the vector moves from a first position to a second position.

The displacement vector is a function of the movement of the finger and represents its velocity and direction. A vector transition corresponds to an acceleration. Since

515 239

2001-03-08 P: \ 1874-118 sv overs 11. doc BA / LJ finger is a physical organ, it can not have infinitely great acceleration. Therefore, if the finger movement is sampled at a sufficient rate, the sample values ​​will be highly correlated. Because of this correlation, we can calculate the probabilities of the vector moving from one position to another. For all positions, we therefore define a corresponding probability that the displacement vector moves from a first position to a second position. Real user interaction statistics can be used to calculate or calibrate the probabilities.

Some simplifications can be made to reduce the number of calculations:

Calculate the probabilities of areas. Map all vectors in an area on a probability. Probabilities are proportional to the distance between first and second positions. We can assume that short distances between these two positions are more likely in the longer distances.

From the above, we can define the following algorithm (represented by steps 132 and 134 in FIG. 4), which locates the most likely offset vector, among the number of offset vector candidates determined in step 126, by maximizing the above probabilities. A search tree is formed by probable vectors, and an initial width search is performed. To reduce the number of calculations, only the N most probable paths are used. In an initialization step, some variables for the N paths are reset. Then a loop is repeated, where we find the N most likely offset vectors in a correlation map. These are used as nodes in the search tree. In order to evaluate the candidates for the displacement vector, a measure is calculated for each candidate. The measure is a function of transition probability and correlation quality. For each node at depth t + 1, find for each precursor at depth t the sum of the precursor measure and the branching dimension. Determine the maximum

515 239

2001-03-08 P: \ 1874-118 sv overs 11. doc BA / LJ for these sums and assign this to this node. Then calculate the sum of the offset vector and a total offset for the selected predecessor, and assign this to the node. The node with the largest measure is the estimate of the correct offset vector.

The method and apparatus for detecting fingerprints described above can be implemented in many different electronic devices, preferably miniaturized or portable ones. One example is a mobile phone 1, illustrated in FIG. 1. Other examples include small handheld devices to be used as door openers, remote controls, wireless access control devices, wireless electronic payment devices, and the like.

According to one aspect of the invention, the determined displacement vector can be regarded as representing a movement of a user's finger in a coordinate system. This makes it possible to use the method and apparatus of the invention as a pointing device for controlling the position of a marker or the like on a computer-like display.

The invention has been described above with reference to a preferred embodiment. However, embodiments other than those described above are equally possible within the scope of the invention, as defined by the appended claims. It is particularly noted that the method of the invention can be applied not only to fingerprints but also to other types of images, which represent a body-specific pattern containing some kind of periodic characteristic.

515 239

2001-03-08 P: \ 1874-118 Sv overs II.doc BA / LJ