CA2340813A1 - Method for fingerprint verification using a portable device - Google Patents

Abstract

The invention describes a method for fingerprint verification using a portable device with low data memory requirements and low power consumption. The enrollment part of the method includes sorting information contained in a fingerprint image into alignment information and verification information. The latter may comprise a set of "tiles"
extracted from different parts of the image in the pre-determined locations, the size of said "tiles" and of the alignment information being considerably smaller than of the entire image. An optimization procedure including, in particular, generating a composite filter, may be applied to create an enrollment template. The verification part of the method includes extracting alignment information from a candidate image, utilizing said alignment information to align the candidate image with the enrolled one to obtain the adjusted "tile" locations for the candidate image. The next step includes extracting the "tiles" of the same size and orientation as on the enrollment from the candidate image and matching each "tile" with the corresponding "tile" on the enrollment. A
set of matching parameters is obtained for each "tile". The final match/non-match decision is based on multivariable decision boundaries approach. Since the alignment information and each "tile" is processed in a consecutive way, the memory and, accordingly, the power consumption requirements for the hardware are significantly reduced.
This allows the invention to be used with a portable device.

Description

~ new algorithm for fingerprint verification based on the correlation in "tiles"
Alex Stoianov, 9 July 1998 In this Memo I would like to discuss main ideas and some preliminary results regarding the new algorithm for "one-to-one" verification in Touchstone or Matchbox proposed a while ago.
The new algorithm should improve the accuracy of the system, i.e. provide a better separation between FRR and FAR distributions, with about the same processing time and the bioscrypt size as a plain correlation of 128x 128 images would have.
Basics of the new algorithm In the new algorithm, the correlation is performed in several smaller blocks (i.e. of 32x64 size), called "tiles". They are extracted from the original 128x 128 image in pre-defined positions. A set of parameters obtained from each "tile", such as a correlation ratio or an area at 20% of a maximum, is used for the verification. The correlation in smaller blocks is more tolerant to fingerprint deformations and rotations, including non-uniform ones, which yields a lower FRR. Besides, a high cross-correlation is less likely to occur in all the blocks simultaneously, thus reducing FAR as well.
Fig. 1 illustrates the advantages of this approach. A 128x128 image, A, is stretched by 2%
in X direction and by 3% in Y direction, which is typical for the fingerprint images. The correlation ratio drops from 0.5415 to 0.0268 (i.e. 20 times) and the area at 20% of the maximum increases from 1 to 12. On the other hand, the correlation ratio for the 64x32 tiles drops only from 0.4463 to 0.24 and the area at 20% increases from I to

2. The same is true for rotations and for irregular contrast changes. What is even more important is that the correlation in tiles is quite tolerant to the non-uniform, irregular distortions which cannot be compensated for the entire 128x128 image by any adaptive method.
However, the adaptive verification (i.e. rotating or re-scaling an input to get the best possible correlation) is more suitable to the tiles than to the entire image since the distortions in each tile are more uniform. Thus, the correlation in tiles reduces one of the major drawbacks of the current algorithm - a high sensitivity to the fingerprint distortions.
In the preferred version of the algorithm, two tiles of 32x64 and two tiles of 64x32 are extracted on enrollment in the pre-determined positions, as shown in Fig. 2.
The tile centers are: (40,38), (75,28), (90,58), and (56,77) (these values are not necessarily optimal and final). The filters are made separately for each tile. In order to be able to extract the tiles on verification at the same or close positions, another block of data, that is, a central 64x 128 part, is taken from the image to generate its own filter (Fig. 2). This filter (representing the central part) is used to align an image to be verified with the image enrolled and to extract the tiles at the same positions.

Image, A Auto-correlation ADA
Ratio = 0.541539 Area20% = I
Xpos = 64 Ypos = 64 A, : the image A stretched by 2%
in X and by 3% in Y Correlation AoA, Ratio = 0.0267655 Area20% = 12 Xpos = 64 Ypos = 64 a : 64x32 tile extracted from A Auto-correlation a~u Ratio = 0.446335 Area20% = 1 Xpos = 32 Ypos = 16 a, : 64x32 tile extracted from A, Correlation a~a, Ratio = 0.240004 Area20% = 2 Xpos = 32 Ypos = 17 Fig. 1. The influence of the uniform deformations on the entire 128x 128 image and on the 64x32 tile

3 Thus, the bioscrypt comprises 5 filters corresponding to the "big" 64x 128 block and 4 smaller (32x64 or 64x32) tiles. The total size of the bioscrypt is the same as it would be for a filter representing the entire 128x 128 image.
(a) (b) Fig. 2. The tiles extracted from the 128x 128 image (a), and the central block of 64x 128 used for the alignment (b) On verification, the first step includes extracting a central 64x128 block from the image to be verified and correlating this block with the related 64x 128 filter. The location of the correlation peak indicates a relative shift between the two images (i.e. one being verified and another previously enrolled). Then the tiles are extracted from the new image in accordance with this shift, and each tile is correlated with the corresponding filter. Note that even before this, the image may be verified by the ratio in the central block, if this ratio exceeds a high threshold. This is almost the same as the present algorithm since the actual size of Touchstone images is about 85x 128, which is not too far from 64x 128.
About 90% of all auto-correlations are expected to be verified at the first step. Only if the ratio is lower than the high threshold, the tiles will be extracted. Unlike the central block, the correlation peaks in the tiles should be located exactly at the geometric centers (i.e. at (32,16) or ( 16,32) ). The shift by a few pixels indicates the presence of distortions, and a big shift usually occurs when there is no correlation. The values obtained from the tiles, such as ratios, areas at 20% of the maximum, and peak positions, are combined to check the verification through a set of decision boundaries. This second step of verification together with the first step should allow more than 99% of all auto-correlations to be verified. If the image is still not verified, the third step of verification starts up. This step includes the adaptive verification for each tile. More specifically, the tile is rotated by an angle (for example, from ~4° to +4° with a 1° increment) to obtain the best correlation,

4 and so on for all the tiles. It was found that the scale variations are less important in the case of small tiles than the rotations, so that they are ignored. After the adaptive verification is completed, the new values go through a set of decision boundaries (they differ from the set used at the second step). As simulations show, it is possible to reduce FRR to 0.3% or less and FAR to 0.01 % or less after the third step.
Processing time Estimates show that the processing time for the new algorithm should be the same or even smaller than for the present algorithm. Indeed, as the FFT is the most time-consuming part, the processing time is approximately proportional to NIogZN, where N is the total number of pixels. Thus, for the steps 1 and 2 of the new algorithm, it should take 0.5 + 4/(81og28) = 0.67 t,2n , where t,~n is the time required for the correlation of 128x 128 images, plus some time for the tiles extraction, etc. For the step 3 with the adaptive verification, assuming that all 8 angles from ~l° to +4° are checked, the time will be 8~4/(81og28) = 1.5 tl2s , plus the time required for the rotation.
Since the third step is relatively time-consuming, it should be done only at the end of the verification timeout, for example, for "the best" image captured.
Other features of the algorithm Although the new algorithm exhibits good results even for the correlation of two single fingerprint images, it is more appropriate to create a composite filter from, for example, 4 images on enrollment. It is done in the way similar to that we have now.
However, there are some differences:
- the images are averaged in the image domain, not in the Fourier one;
- the images are co-aligned by the correlation of the central 64x 128 blocks, then the composite 64x 128 image is created;
- the tiles are extracted from each image according to their relative positions found during the alignment of the 64x 128 blocks;
after the tiles are extracted, their relative shift is checked again, and if the shift exists, the new tiles are extracted from the original image;
- after all 5 composite images are created, the FFTs are performed. Then the magnitudes of the FFrs are modified using D(u,v) and a terms. The a value is different for the central block and the tiles;
- all full-complex filters are quantized using an operating curve with 8 points (on verification, a do block will be also applied);
- only half of each filter is taken, and these 5 halves are stored into one bioscrypt of the same size as for the present algorithm with 128x 128 images.
Another feature of the algorithm includes dealing with images which are shifted too much (on verification) from the image enrolled. In this case some tiles lie (partially or even completely) outside the image area. If the area of overlapping of two tiles (i.e. being verified and enrolled) is less than about 20% of the total number of the pixels in the tile, this tile is excluded from the verification. Alternatively, if the total energy of the extracted tile is less than about 20% of the maximal total energy among all 4 tiles, this tile will be also excluded. It is required that at least 3 tiles should remain for the correlation analysis, other°wise, the image is rejected (it occurs usually in some eross-correlation cases). This problem should not be very significant if the AIQ
feature is implemented on verification.
Preliminary results for Touchstone images A database J:\datasets\Sept97\images 1 containing fingerprints from 28 users (the largest number we have) was used. For each user, 4 images from one session were selected for the enrollment and 1 1 from as many different sessions as possible - for the verification, so that there were 308 auto-correlations and 8316 cross-correlations in total.
The composite filter was created from 4 images for each user as described in the previous section; the a value equals 7~ 10-~ for the central block and 2~ 10-6 for the tiles (these values still have to be optimized).
The results are shown in Fig. 3 - 7 . The first 2D scatter plot (Fig. 3) represents Step I of the algorithm and is related to the central block. Its performance is virtually the same as for the present algorithm with 128x 128 images: FRR = 12/308 = 3.9% at FAR = 0 .
However, we set the ratio threshold for this step at about 0.023 to have a safety margin for the FAR. In this case FRR = 31/308 = 10% , which means that 90% of all users will be verified at this step with a high speed.
Fig. 4 shows the results for the Step 2, when the correlation parameters are obtained from all 4 tiles shown in Fig. 2. There might be different ways of combining these values into a decision-making process, such as neural networks, fuzzy logic (it is still an option), etc.
However, it was found that a simple solution yields quite satisfactory results: a mean arithmetic ratio and a mean geometric area (at 20alo) are calculated over all the values obtained from 4 tiles. It is seen from Fig. 4 that these combination of parameters provides an excellent separation between FAR and FRR at Step 2: FRR = 2/308 = 0.65% at FAR =
0, or 6 times down from the present algorithm.
Step 3, which includes the adaptive verification, was tested in the following way:
From Step 2, all auto- and cross-correlations with mean ratio less than 0.028 and mean geometric area less than 90 were taken for the adaptive verification. There were 9 auto-correlations and 83 cross-correlations. Then each tile was rotated in the image domain within the angle range from -4° to +4° with a 1°
increment. The angle yielding the smallest area at 20% was chosen as an output, and so on for all the tiles. It is possible to use some kind of a tree scheme to look for the best angle, which would reduce the processing time. However, the dependence of the area at 20% on the rotation angle is not always monotonic, so that it should be done with a certain caution.
After the best angles for all 4 tiles have been found, the mean arithmetic ratio and the mean geometric area are calculated again. The resulting plot is shown in Fig.

5. There is an absolute separation between auto- and cross-correlations, i.e. FRR = FAR =
0. To be

6 more scientifically correct, we should state that for this database FRR <
1/308 = 0.3%
and FAR < 1/8316 = 0.01 % .
The remaining 2 plots (Fig. 6 and 7) provide a redundancy to Fig. 5. A total displacement (Fig. 6), i.e. a number of pixels by which the correlation peak is shifted from the tile center (summed up over all 4 tiles), is expected to be smaller for the auto-correlation.
Also, an average rotation angle is usually larger for the auto-correlation (Fig. 7), since for the cross-correlation the best angle tends to be randomly distributed between -4 ° and +4°
with the average close to 0.
It is also possible to set thresholds for each tile separately and to require a positive verification in at least 3 tiles from 4. This method, in general, works worse than the method using the mean values, but may provide an additional redundancy.
Conclusions The new algorithm based on correlation in tiles extracted from a fingerprint image is proposed and tested. The composite filter for each tile is implemented, including quantization. The verification process is split into 3 steps, the last one being an adaptive verification. For the database tested, the algorithm yields an absolute accuracy, i.e. FRR =
FAR = 0 , or an accuracy better than that the current algorithm may provide by at least one order of a magnitude. The bioscrypt size is the same as for the present algorithm with 128x 128 images, and the processing time is expected to be about the same or even smaller.
The implementation of the algorithm for the Matchbox should not require a lot of time and resources. The algorithm is based on the expertise (i.e. the correlation technique, the composite filter, etc.) we already acquired and does not affect such things as the image capture, AIQ, communication protocol, etc. It does not require a DSP encoding and may be easily programmed in C/C++ codes.

February 03, 2000 Alex Stoianov This document will present an updated version and results for a fingerprint verification algorithm based on correlation in "tiles" (see my Memo of July 9, 1998 attached).
The goal is to make the algorithm more portable, as discussed with Colin Soutar.
Database: Fourier\R&D-data\datasets\infineon\BI lesd 11 users, ~ 90 images for each.
Enrollment 1. Receive three or four 128x 128 images.
2. Extract a central 64x 128 block from each image (for the alignment).
3. Co-align all 64x 128 blocks via correlation; store the relative positions.
4. Create a composite 64x 128 image of the central block.
5. Reduce the size of the composite image to 32x64 by averaging four adjacent pixels or by decimation.
6. Perform FFT of the 32x64 image.

7. Take one half of the Fourier transform; take the phase only; quantize to 8 levels; store into a bioscrypt. The resulting size for storage is 0.375 Kb.

8. According to the relative positions obtained at Step 3, extract from incoming 128x 128 images four "tiles" of the following dimensions: 32x64, 64x32, 32x64, and 64x32. The centers are: (40,38), (75,28), (90,58), and (56,77), subject to further optimization, if necessary.

9. Check the relative shift of the extracted "tiles" via correlation. If the shift still exists (i.e.
the correlation peaks are not located at (16,32) or (32,16)), extract new "tiles" according to the shifts.

10. Create 4 composite images for the "tiles".
1 1. Perform FFT of all the composite 32x64 or 64x32 images.
12. Take one half of each Fourier transform; take the phase only; quantize to 8 levels; store into the bioscrypt. The total size of the bioscrypt is Sx0.37S Kb. = 1.875 Kb.
Verification 1. Unpack the bioscrypt (may be done consecutively, when any of 5 bioscrypt parts is required).
2. Receive one 128x 128 image; store it into the memory.
3. Extract a central 64x 128 block from the image (for the alignment).
4. Reduce the size of the central block to 32x64 by averaging four adjacent pixels or by decimation.
5. Co-align the 32x64 central block with corresponding filter from the bioscrypt. The co-alignment is done via correlation with derotation. Store the obtained x- and y-shifts.
6. According to the shift positions (multiplied by 2), extract the first "tile" from the incoming 128x128 image. Correlate with the corresponding filter from the bioscrypt.
7. Obtain the following parameters from the correlation function: peak-to-total energy ratio, area at 20% of the maximum, and peak position.
8. Derotate the extracted "tile" or the filter (from -6° to +6°
with 1° increment) until the smallest area at 20alo is obtained. This step may be omitted to speed up the processing.

11 9. Repeat Steps 6 - 8 for all remaining "tiles".
10. Make a decision about the verification using the values obtained from all 4 "tiles" at Step 7 or 8. At present, the following average values are calculated over 4 "tiles": mean ratio, mean geometric area at 20% (i.e. (a,a~a~aa)~~~), and mean absolute displacement from the expected center. These average values input a set of a few (usually 1, 2, or 3) decision boundaries which are to be determined from simulations.
Results For the database Fourier\R&D-data\datasets\infineon\B 1 lesd, all available images were used for the auto-correlation and each 3"~ for the cross-correlation, making in total 977 auto-correlation and 3260 cross-correlation attempts. The bioscrypts were created from first 3 images of the second session for each user. The user # 0 was dropped from the simulations.
These settings coincide with those outlined in Ira's Memo of December 13, 1999.
The false rejection rate (FRR) was obtained when the false acceptance rate was equal to 0 (or at least less than 1/3260). Only one decision boundary, mean geometric area at 20% vs. mean ratio, was used.
FRR = 61977 = 0.61 % without a denotation at Step 8 of verification;
FRR = 3/977 = 0.31 % with the denotation at Step 8 of verification.
These results demonstrate a considerable improvement (by a factor of 6.3) to the results obtained for the current Mytec algorithm with the denotation on both enrollment and verification.
Memory estimation for verification Step 1 of verification requires 4 Kw (32-bit words) of memory for each part of the bioscrypt.
Step 2 requires 16 Kw, or 4 Kw in a packed format. The incoming 128x128 image should be kept in the memory until the very end.
Step 3 requires 8 Kw. This 64x 128 array will be discarded after the Step 4 to free the memory.
Step 4 requires 2 Kw.
Step 5 requires 4Kw for the 32x64 Fourier transform plus 4 Kw for the unpacked part of the bioscrypt (see Step 1). The denotation may take a little bit more. These (4 +
4) Kw will be discarded after the Steps.
Steps 6 - 9: the same as the Step 5.
Step 10 does not require a lot.
It seems that 32 Kw should be sufficient for the entire processing, except AIQ, communication, encryption, and the other stuff.

12 March 06, 2000 Alex Stoianov This document, which is a follow-up to my Merno of February 2, 2000, will present new results for a fingerprint verification algorithm based on correlation in "tiles". The resolution of original 225x288 images is reduced by a factor of 3, either by averaging or by decimation. This should tit the algorithm into a portable device with only 16 KB of data memory available.
Databases:
Fourier\R&D-data\Datasets\Infineon\B 1 lend , 11 users, 15 sessions, 6 images per session Fourier\R&D-data\Datasets\Siemens\Final\256\Work , 27 users, 25 sessions, 6 images per session Enrollment 1. Receive three or four 225x288 images, extract central 222x252 part, reduce to 74x84 by averaging in 3x3 boxes or by decimation (worse).
2. Extract a central 64x84 block from each image (for the alignment).
3. Co-align alt 64x84 blocks via correlation: store the relative positions.
The correlation is done by embedding the 64x84 image into a 64x 128 array of constant values.
4. Create a composite 64x 128 image of the central block.
5. Extract a central 42x84 part of the composite image.
6. Reduce the size of the composite image to 32x64 by bilinear interpolation (factor 1.3125x I .3125).
7. Perform FFT of the 32x64 image.
8. Take one half of the Fourier transform; take the phase only; quantize to 8 levels; store into a bioscrypt. The resulting size for storage is 0.375 Kb.
9. According to the relative positions obtained at Step 3, extract from the incoming 74x84 images four "tiles" of the following dimensions: 22x44, 44x22, 22x44, and 44x22. The centers are: (22,24), (45,18), (55,38), and (32,50), subject to further optimization, if necessary.
10. Embed each "tile" into 32x64 or 6~tx32 array of constant values.
11. Check the relative shift of the embedded "tiles" via correlation. If the shift still exists (i.e. the correlation peaks are not located at ( 16,32) or (32,16)), extract new "tiles"
according to the shifts.
12. Create 4 composite 32x64 or 64x32 images for the "tiles".

13. Extract central 22x44 or 44x22 parts, embed them again into 32x64 or 64x32 arrays of constant values.

14. Perform FFT of all the composite 32x64 or 64x32 images.

15. Take one half of each Fourier transform; take the phase only; quantize to 8 levels; store into the bioscrypt. The total size of the bioscrypt is 5x0.375 Kb. = 1.875 Kb.
Verification Unpack the bioscrypt (may be done consecutively, when any of 5 bioscrypt parts is required).

2. Receive one 225x288 image, extract central 222x252 part, reduce to 74x84 by averaging in 3x3 boxes or by decimation (worse). Store the 74x84 image into the memory.
3. Extract a central 42x84 block from the image (for the alignment).
4. Reduce the size of the central block to 32x64 by bilinear interpolation (factor 1.3125x 1.3 I 25).
Options (less time-consuming, but worse performing): reduce to 32x64 by the nearest neighbor approximation; simply extract the central 32x64 part from the 74x84 image. The same should be done on the enrollment, if applicable.
5. Co-align the 32x64 central block with corresponding filter from the bioscrypt. The co alignment is done via correlation with derotation. Store the obtained x- and y-shifts.
6. According to the shift positions (multiplied by 1.3125), extract the first 22x44 "tile" from the incoming 74x84 image. Embed the "tile" into 32x64 array of constant values.
Correlate with the corresponding filter from the bioscrypt.
7. Obtain the following parameters from the correlation function: peak-to-total energy ratio, area at 20% of the maximum, and peak position.
8. Derotate the extracted "tile" or the Filter (from -6" to +6" with 1"
increment) until the smallest area at 20% is obtained. This step may be omitted to speed up the processing.
9. Repeat Steps 6 - 8 for all remaining "tiles".
10. Make a decision about the verification using the values obtained from all 4 "tiles" at Step 7 or 8. At present, the following average values are calculated over 4 "tiles":
mean ratio, mean geometric area at 20% (i.e. (a,a~a~a~)'~'~ ), and mean absolute displacement from the expected center. These average values input a set of a few (usually I, 2, or 3) decision boundaries which are to be determined from simulations. Note that the decision can be made sometimes on Step 5, that is, if the correlation of the central block yields a high ratio, then the person is verified without going to the next steps. This can occur in about 70 - 80 % of all cases.
Results For the database Fourier\Rc~D-data\datasets\infineon\B 1 1 esd, all available images were used for the auto-correlation and each 3'd for the cross-correlation, making in total 977 auto-correlation and 3260 cross-correlation attempts. The bioscrypts were created from first 3 images of the second session for each user. The user # 0 was dropped from the simulations.
These settings coincide with those used for the present Mytec algorithm'.
Since this DB contains 128x128 images only, they were reduced to 74x84 by bilinear interpolation rather than by averaging or decimation. All other steps remain the same.
For the database Fourier\R&D-data\Datasets\Siemens\Final\256\Work , all available images were used for the auto-correlation and each 3'd for the cross-correlation, making in total 3382 auto-correlation and 29652 cross-correlation attempts. The bioscrypts were created from first 3 images of the first session for each user. The user # 1 was dropped from the simulations. These settings coincide with those used for the present Mytec algorithm'.
The simulations were performed exactly as outlined above.
As can be seen from Table 1, 2, the new algorithm even with the reduced resolution yields much better (by a factor of 6 - 7) results than the present Mytec algorithm with 128x 128 images.
Averaging the incoming 225x288 images vs. decimating improves the results by a factor of 2.
' Ira's Memo of December 13, 1999.
' Ira's Memo of October 12, 1999.

Table 1 Database Fourier\R&D-data\datasets\infineon\B 11 esd 977 auto-correlations, 3260 cross-correlations FRR (at FAR < 0.03 %) Present Mytec algorithm':
128x128 images;

derotated on enrollment 1 .96 and verification New algorithm with 5 "tiles": 74x84 images (= by averaging); "tiles"0.2 %
derotated on veri fication Table 2 Database Fourier\R&D-data\Datasets\Siemens\Final\256\Work 3382 auto-correlations and 29652 cross-correlations FRR (at FAR < 0.003 %) FRR (at FAR = 0.1 %) Present Mytec algorithm':
128x 128 images;

derotated on enrollment I 1.4 % 7.25 and verification New algorithm with 5 "tiles": 74x84 images (by averaging); "tiles"
derotated on 2.3 % 1.0 %

verification New algorithm with 5 "tiles": 74x84 images (by decimatin~l; "tiles"5.8 ~o derotated on 2.0 to verification Memory estimation for verification Step I of verification requires 4.096 Kw (32-bit words) of memory for each part of the bioscrypt Step 2 requires 6.216 Kw, or 1.554 Kw in a packed format. The 74x84 image should be kept in the memory until the very end. It is implied that the resolution of the incoming 225x288 image is reduced by a gate array.
Step 3 requires 3.528 Kw. This 42x84 array will be discarded after the Step 4 to free the memory.
Step 4 requires 2.048 Kw.
Step 5 requires 4.096 Kw for the 32x64 Fourier transform plus 4.096 Kw for the unpacked part of the bioscrypt (see Step 1 ). The derotation may take a little bit more. These (4.096 + 4.096) Kw will be discarded after the next step.
Steps 6 - 9: the same as the Step 5.
Step 10 does not require a lot.
The maximum memory in total is required at Step 5: 6.216 + 4.096 + 4.096 =
14.408 Kw plus, perhaps, some small amounts, such as 1.875 Kw for the packed bioscrypt, etc.
If the bioscrypts (rather than the images) are derotated, add additional 4.096 Kw.

Claims