Method and device for identifying fingerprints using an analog flash memory

[0002] This is a continuation-in-part of U.S. patent application Ser. No. 08/802,658 for “Method and Device for Indentifying Fingerprints” filed on Feb. 19, 1997 now U.S. Pat. No. 6,236,741.

[0003] The present invention relates to a method for identifying fingerprints using an analog flash memory.

[0004] As is known, the fact that fingerprints are strictly personal and represent a type of identity card, gives rise to many applications. For example, fingerprints are used conventionally by the police for identification of criminal acts, and it has been proposed to use fingerprints as a type of personal key or signature to improve security of credit cards, to control access to security areas, to computers or to bank transaction systems. Fingerprints can also replace physical keys, which are often cumbersome, in order to obtain access to one's own dwelling or car.

[0005] The problem of full identification of fingerprints consists of defining a score to be allocated to a pair of images of fingerprints, which expresses the probability that the two prints belong to the same person. The two prints are acquired at two different moments. One usually belongs to a data bank which contains the reference to known persons, and the other must be validated or recognised by comparison with the first.

[0006] Conventional methods for identifying fingerprints, carried out manually by experts, comprise a plurality of classification steps. Recently automatic methods have been proposed, some of which comprise pre-classification steps which are similar to the conventional steps, and others which dispense completely with these stages, and, starting directly with the image of the print obtained provide the desired result, for example through a scanner or sensor, via an appropriate processor. The present invention relates to this second type of approach.

[0007] A fully automatic identification system is described for example in the article by K. Asai, Y. Kato, Y. Hoshino, K. Kiji “Automatic Fingerprint Identification,” in Proceedings of the Society of Photo-Optical Instrumentation Engineers, vol. 182, Imaging applications for Automated Industrial Inspection and Assembly, pp. 49-56, 1979. According to this system, the notable points on the image (tips and branching of cutaneous crests, known as “minutiae”) are determined directly by the image in tones of grey, and the correspondence of the prints is determined by taking into account by counting of the crests and taking into account the direction of the “minutiae,” similarly to the manual method.

[0008] In D.K. Isenor, S. G. Zaky “Fingerprint Identification Using Graph Matching” Pattern Recognition, Vol. 19, No. 2, pp. 113-122, 1986, a method is described which is based on comparison between graphs. In the image of the fingerprint, the cutaneous crests and indentations are sought, and the former are numbered and oriented, whereas the latter represent the background. A level of adjacency is defined which expresses information concerning which crest is close to which other. On this graph abnormalities are identified and corrected which are associated with dirt or with interruptions of crests, associated with the acquisition system, in order to obtain the final graph which describes the fingerprint in coded form. The comparison between graphs makes it possible to determine the similarity between the fingerprints.

[0009] In K. Asai, Y. Hoshino, K. Kiji “Automated Fingerprint Identification by Minutia-network Feature-Matching Processes,” Transaction of the Institute of Electronics, Information and Communication Engineers D-II, Vol. J72D-II, No. 5, pp. 733-740, May 1989 (in Japanese), use is made of a minutiae network which contains tip and branching points, and a corresponding link obtained by counting the cutaneous crests between notable adjacent points. There is also consideration of the local direction of the cutaneous crests. The pairs of corresponding points are obtained by transformation of coordinates and calculation of the similarity.

[0010] These systems have been assessed on a few hundred proprietary fingerprints, and do not yet permit identification with the accuracy required for police uses, where there are many millions of images to be compared.

[0011] In addition, in European patent application 96830080.6 filed on Feb. 2, 1996 in the name of SGS-Thomson Microelectronics, S.r.l., a method of identification is described which is based on the search for characteristic points on the reference image and on the image to be recognised, and on comparison between regions which surround the characteristic points of the two images, on the basis of the integral norm for these regions, carried out through an analog flash memory. This method is applicable in practice in acceptable times, and has provided excellent results concerning the number of incorrect identifications, but the percentage of correct recognition is too low for practical applications. This low level of correct recognition can be attributed to the high deformation which exists between different images of a single print, owing to the possibility of rotations of the print which can be greater than 20°, and to the differences in quality of the images, owing to considerable variation of the ink (in excess or lacking). Furthermore, the use of non-linear filtering in the field of frequencies of the images, in order to improve the quality of the image, has led to improvement of the percentage of correct identifications, but is not yet sufficient, and gives rise to a substantial increase in the costs from the point of view of the calculation time.

[0012] An object of the invention is thus to provide a method of identification, which can increase the level of correct identifications, with a calculation time which is acceptable for the applications planned.

[0013] The present invention provides a method for identifying fingerprints, using an analog flash memory. The method according to one embodiment of the invention includes acquiring a primary image having a plurality of primary points, and a secondary image having a plurality of secondary points, the primary and secondary points being characterised by a quantity associated with the three-dimensional structure of prints to be identified. The method determines notable points among the plurality of primary points; compares the primary image and secondary image; identifies possible correspondences between the primary image and the secondary image; and validates the possible correspondences. The comparison includes determining scanning regions of the secondary image, which surround the secondary points, and comprise the entire secondary image; and compares notable regions of the primary image which surround the notable points, with the scanning regions, using flash memory cells.

[0014] FIG. 1 shows a block diagram of a device for identifying fingerprints, which implements a method according to the invention.

[0015] FIGS. 2a, 2b, 3-6 show flow charts relating to steps of the present method.

[0016] FIGS. 7a-7eillustrate conceptually how to take into account high global deformations of images, using a criterion of low local deformation.

[0017] FIGS. 8a, 8b, 9 and 10 show flow charts relating to subsequent steps of the present method.

[0018] FIG. 11 shows a circuit diagram of a unit according to the device in FIG. 1.

[0019] FIG. 12 shows a flow chart relating to a step of the present method.

[0020] FIG. 13 shows a simplified flow chart of a detail of the device in FIG. 1, and which incorporates the unit in FIG. 11.

[0021] The invention will now be described with reference to the attached drawings, which illustrate a non-limiting embodiment.

[0022] In FIG. 1, a device 1 for identifying prints generally comprises a sensor 2 for acquisition of fingerprint images, as matrices of points which are characterised by different levels of grey; an images memory 3 which is connected to the sensor 2; a processing unit 4, which is connected bidirectionally to the images memory 3; a calculation results memory 5, which is connected bidirectionally to the processing unit 4 for storage, inter alia, of a list of minutiae 7 and of association maps 8; and a correspondence map extraction unit 6, which is connected bidirectionally to the processing unit 4, and unidirectionally to the images memory 3, for execution of predetermined steps of the method of identification, as described in greater detail hereinafter.

[0023] The sensor 2 is a scanner which operates in accordance with any known principle, for example optical, capacitive, piezoelectric, ultrasound, thermal, although the capacitive sensor described in U.S. patent application Ser. No. 08/799,548, assigned to SGS-Thomson Microelectronics, S.r.l., is preferably used. The purpose of the sensor 2 is to provide images of a reference print (hereinafter known as the primary image), and of a print to be identified (hereinafter known as the secondary image), formed for example from 200×200 pixels, each characterised by different levels of grey, variable between 0 and 255.

[0024] The images memory 3 is preferably subdivided into various regions for storage on each individual occasion, and according to the processing step, of the primary image as acquired, of the secondary image as acquired, of images derived from processing of acquired images, as well as of portions of the latter, as described hereinafter. It will be appreciated that in the event of a request for identification of a secondary print from among a plurality of reference images, the portions relating to the primary image are duplicated for each further reference image.

[0025] The processing unit 4 carries out the processing required, controls the flow of data from and to the memories 3, 5, and controls the correspondence map extraction unit 6, as described hereinafter with reference to FIGS. 2aand 2b, relative to the main steps of an embodiment of the present invention.

[0026] The present method includes preliminary processing of the primary image and storage of the results (learning step), as shown in FIG. 2a, and subsequent processing of the image to be recognised, using the results acquired from the preliminary processing of the reference image (recognition step), as shown in FIG. 2b. Thereby it is possible to carry out the processing which is the most onerous from the point of view of calculation time, once only and preliminarily, and then to speed up the operations necessary for comparison with an image to be recognised.

[0027] With reference to FIG. 2a, the learning step begins, block 10, with acquisition of the primary image and storage of the latter in the images memory 3. The primary image as acquired is then filtered finely, for example, through non-linear filtering in the field of Fourier two-dimensional transformation, as described in G. T. Candela, P. J. Grother, C. I. Watson, R. A. Wilkinson, C. L. Wilson, PCASYS, “A Pattern-Level Classification Automation System for Fingerprints,” August 1995 (block 11). The purpose of this fine filtering operation is to eliminate spurious interruptions of the crests and knurls present on the edge of the cutaneous crests owing to the diffusion of the ink on the paper (in the case of acquisition of the image by inking the finger and pressing the inked finger on the paper). The finely filtered primary image is then temporarily stored in the images memory 3.

[0028] Simultaneously (in the case of multi-processor processing units or a dedicated fine filtering unit), or after the fine filtering, rough filtering of the primary image is carried out, block 12. The object of this operation, which is described in greater detail hereinafter with reference to FIG. 3, is to improve the quality of the primary image, not from the point of view of frequency or noise, but from the point of view of the dynamics of the tones of grey. In fact, for a variety of reasons (contrast or brightness of the scanner, lack of uniformity of the ink, worn crests, etc.) the image acquired often does not cover the entire dynamics of the tones of grey (256 in this case). Consequently when comparison takes place of the primary image and the secondary image, of which for example one is highly contrasted and the other is not, there is the problem of equalising the amplitude of the signal, i.e., the excursion of the tones of grey, a problem which is solved through the rough filtering. The roughly filtered primary image is then stored in the images memory 3.

[0029] After the fine filtering according to block 11 (before or after the rough filtering), a step of extraction of actual minutiae from the finely filtered primary image is carried out, block 13. The object of this step is to identify the minutiae (branching and tips of cutaneous crests), and it is carried out for example as described in the aforementioned article by Asai, Kato, Hoshino, Kiji “Automatic Fingerprint Identification”. On completion, the coordinates are obtained of 60-70 points which are useful for the purpose of comparison (with a high percentage corresponding to physical minutiae). The coordinates of the actual minutiae thus obtained are then stored in the calculation results memory 5.

[0030] In order to reduce the subsequent calculation time, during the recognition step, there are extracted the proximity links between the actual minutiae, ordered according to distance, with storage in the images memory 3 of the development of the tones of grey of the intermediate pixels between two actual adjacent minutiae (block 14), as described in detail with reference to FIG. 5.

[0031] Subsequently, after determination of the actual minutiae and rough filtering of the primary image, a step is carried out of extraction of notable regions which surround the actual minutiae, and rotation of these regions (block 15). In practice, from the roughly filtered primary image, there are extracted regions of predetermined dimensions, centred on the actual minutiae determined, and these regions are pre-rotated such as to reduce the error in subsequent comparison with the secondary image, and to reduce the time of processing of the recognition step. The value of the pixels of the notable pre-rotated regions is then used to program a flash memory array (not shown in FIG. 1, and belonging to the correspondence map extraction unit), block 16, as described hereinafter in detail. On completion of the learning step, in the images memory 3, there are then present only the lines joining the actual minutiae previously determined, whereas in the results memory 5 there is present the list 7 of the actual minutiae, which includes the proximity links.

[0032] In simulations carried out by the inventor, with the exception of programming 16, the learning step described required 10 to 400 seconds, but this step is carried out once only on the primary image, when the latter is being defined, and this therefore does not affect the subsequent processing time, which is preferably as fast as possible.

[0033] With reference to FIG. 2b, the recognition step begins with acquisition and storage of the secondary image to be identified, in the images memory 3, block 18.

[0034] Subsequently, in block 19, the secondary image is filtered roughly in the same way as the primary image, and is stored once again in the images memory 3. This operation requires approximately half a second on a 140 MIPS machine.

[0035] Subsequently in block 20, the regions which surround all the pixels of the secondary image filtered are compared with the notable pre-rotated regions previously stored, in order to determine their similarity; on the basis of the similarity value encountered, there are determined and ordered in terms of distance the possible correspondences between each actual minutia of the primary image, and the points of the secondary image, and the possible correspondences are stored in the association maps 8, as described in greater detail with reference to FIG. 7. This operation (known as definition of correspondences) can be concluded positively when sufficient association maps 8 are determined, and each map comprises a sufficient number of associations, in which case stored the association maps are used for subsequent processing, or the operation can be concluded negatively, in which case the processing ends with indication of failure to recognise the print (block 23). The step of definition of the correspondences 20 is very onerous from the point of view of computing, but it can be carried out with an analog chip based on flash memories, as described hereinafter with reference to FIGS. 11-13.

[0036] When the association maps are available, plausible correspondences are sought between the actual minutiae, taking into account the deformation which exists between the images. There is then carried out a triangular comparison (block 21) which is described in greater detail with reference to FIG. 8. This comparison step can end positively, in which a final step of validation is carried out, as required by the method of identification defined by the legislative system (block 22), or it can end negatively, in which case there is progress to block 23. The validation step 22 can also end positively, such that a signal for a validated print is generated (block 24), or it can end negatively (in which case there is a return to block 21).

[0037] The entire step of recognition according to FIG. 2bcan be carried out using only algorithms which are based on whole, 32 bit numbers, without ever resorting to operations or variables with a mobile decimal point. Apart from the step of definition of correspondences 20, the average processing time for execution of the recognition step is 1 s on a 140 MIPS computer.

[0038] With reference to FIG. 3, the step of rough filtering 12 (for the primary image) or 19 (for the secondary image) initially comprises a filtering step based on the mean value of the entire image (primary or secondary), in order to reduce the local variations of the tones of grey, block 27. This step consists of replacing the value of each pixel by the value obtained by weighting the pixel itself and the pixels adjacent to it, adding the weighted values obtained, and normalising the sum obtained, in a manner which is known, and is thus not described in detail.

[0039] Subsequently the image is subdivided into a plurality of m×n regions, block 28. In each region there is determined the maximum value max, the minimum value min, and the mean value ave of the tones of grey of the pixels, block 29. Each region is filtered once more with a filter based on the mean value, similarly to the above-described process, block 30. Thereby, it is attempted to eliminate erroneous interruptions of the lines, in order to reveal the continuous development of the maximum, the minimum, and the mean value of the tones of grey.

[0040] Finally, a step of dynamic filtering is carried out, on the basis of which the value p of each pixel of each region is replaced by a value p_rdefined as follows: $p_r=\{\begin{array}{c}p>\mathrm{ave}=\frac{p-\mathrm{ave}}{\max -\mathrm{ave}}x\cos t+\cos t\\ p\le \mathrm{ave}=\frac{\mathrm{ave}-p}{\mathrm{ave}-\min }x\cos t\end{array}$

[0041] in which cost is half the maximum excursion of the tones of grey (128 in the case of 8 bits). The new values p_rof the pixel are then stored as a roughly filtered image (block 31).

[0042] With reference to FIG. 4, the step of ordering of the actual minutiae 14, block 41, initially comprises ordering of the actual minutiae previously determined in list ordered according to increasing distance from the centre of the image, and storage of the list thus generated in the results memory 5 (as the minutiae list 7). Then, for each point P_iin the list, there is calculated the distance from the other points P_jin the list (block 42); the points P_jwhich are close to P_iare ordered by increasing distances, block 43; of these, N points are taken (for example 20 points) of the closest P_js, and these are stored, block 44. Then, in the images memory 3, there is stored the development of the tones of grey of the pixels of the roughly filtered reference image, which are disposed on the line adjacent to each point (actual minutiae) P_i, and the N nearby P_js determined in step 44, or there is stored the development of the crests which intersect these lines, or are close to these lines, as described in greater detail with reference to FIG. 10, block 45. The step of ordering of the minutiae ends when the ratios of vicinity of all the actual minutiae have been determined (YES output from block 46).

[0043] With reference to FIG. 5, the step of extraction and rotation of the regions 15 initially comprises extraction of a region (e g., 16×16 pixels) around each actual minutia P_i, block 50; rotation into N1 different positions which are symmetrical relative to the position of acquisition, and storage of the N1+1 regions thus obtained (taking into consideration also the region with zero rotation) in the images memory 3, block 51. In particular, a study carried out by the inventor has shown that in the case of rotation of up to 2.5°, a normalized difference (between the non-rotated image and the rotated image) of a maximum of 2% is obtained. In addition, it has been noted that the images to be recognised can be rotated up to 20°, to which there corresponds a difference between regions of 25%. This difference is extremely large, and would require such a wide threshold that it would not be possible to determine sufficiently accurately the similarity of the regions. This problem is solved by storing for example seven regions which are rotated relative to the roughly filtered image, by −15, −10, −5,0, 5, 10 and 15 degrees. Thereby, the intrinsic error between the image to be recognised and the image rotated by the minimum distance, remains lower than 2%, in the case of an image to be recognised which is rotated by a maximum of 17.5°, and becomes only 7% for rotations of 20%, making it possible to use reasonable thresholds in the comparison between regions, as described hereinafter with reference to the step of definition of correspondences 20.

[0044] The step of extraction and rotation of regions 15 ends after determination and storage of the regions rotated, for all the actual minutiae (YES output from block 52).

[0045] With reference to FIG. 6, the step of definition of correspondences 20 comprises a sequence of initial steps in order to identify, for each point P_jof the roughly filtered secondary image, the one from among the notable pre-rotated regions stored and associated with each minutia P_i, which has the greatest similarity, and then a subsequent sequence of steps in order to determine and order, on the basis of the similarity values encountered, the points P_jon the secondary image which most probably correspond to the minutia P_iconsidered.

[0046] The step of definition of correspondences 20 then initially comprises the initialisation of a counter i (block 55) and a counter j (block 56) relative respectively to the actual minutiae identified on the primary image, and to the points of the roughly filtered reference image. Then, from the roughly filtered secondary image, there is extracted a region which surrounds the point P_j, with dimensions identical to those of the regions pre-rotated and stored from the primary image (16×16 pixels in the case in question), block 57. As soon as it is extracted, the image is then compared with all the notable, pre-rotated images associated with the point P_i; the distance is calculated from each of these, and there is identified the notable image at the minimum distance, block 58, as described in greater detail hereinafter with reference to FIGS. 11-13. The minimum distance thus identified is compared with a maximum acceptable distance threshold, block 59; if the distance is lower than this threshold (NO output from block 59), the association between the point P_jand the minutia P_iis stored, and the distance identified, block 60. Then, and also in the case when the minimum distance determined is greater than the planned threshold (YES output from block 59), the index j is incremented, block 61, it is verified that all the points of the secondary image have not already been examined, in which case (NO output from block 62) the processing is repeated according to steps 57-61. Otherwise (YES output from block 62), the comparison is repeated once more for all the points of the secondary image for a new minutia P_j, incrementing the index i (block 63) and checking that all the actual minutiae present have not already been examined (NO output from block 64).

[0047] On completion of the sequence of initial steps (YES output from block 64) it is verified whether sufficient correspondences have been found for at least a pre-determined minimum number of minutiae, block 68. If this is not the case (NO output), processing of the secondary image ends, with progress to block 23 in FIG. 2b; otherwise (YES output) there is progress to the subsequent sequence of steps, with re-initialisation of the counter i (block 70), with determination, on the basis of the correspondences previously stored, of the correspondence of points P_jof the secondary image with the minutia P_i, and ordering of these points according to increasing distance, block 71. From the points P_jthus ordered, there are taken N (for example 12) at a smaller distance, and these are stored in the association maps 8 of the results memory 5 (FIG. 1), block 72. The steps 70-71 are repeated for all the actual minutiae stored, incrementing the counter i (block 73). The step of definition of correspondences 20 ends after the association of all the actual minutiae, with the corresponding points with the greatest similarity in the secondary image (YES output from block 74).

[0048] The step of triangular comparison is associated with the need to determine a model of the non-linear deformation to which the prints are subject. In particular, by analysing the primary image and the secondary image, it is noted that according to the rotation of the finger, there can be a strongly variable difference between the minutiae themselves. However, when a small portion of the image is observed, this deformation is not at all obvious. Consequently, an algorithm has been produced which makes it possible to take into consideration large scale deformations, but which limits those on a small scale. In particular, this algorithm is based on the following idea.

[0049] It is assumed that there is a pair of triangles which form a square ABCD, as shown in FIG. 7a. By lengthening or shortening slightly the sides of these triangles by at least 10% of the original length, it is possible to obtain for example the two quadrilaterals shown with a broken line in FIGS. 7band 7c. By repeating the square ABCD in FIG. 7a, it is possible to obtain the cross shown in FIG. 7d. If it is assumed that each square of the cross is deformed as shown in FIG. 7b, the distorted cross in FIG. 7eis obtained. In the distorted cross, the segment AB is transformed into the segment A′B′ which is shorter by 6%, whereas the segment CD is transformed into the segment C′D′ the length of which is 45% shorter than CD. This example illustrates the idea of the deformation model which presupposes a small deformation locally, whereas globally, it makes it possible to take into account also significant alterations.

[0050] On the basis of the idea illustrated above, an algorithm has been produced which is based on gradual creation of an associated graph on the primary image and the secondary image. Consequently, as shown in FIG. 8a, the step of triangular comparison 21 initially comprises extraction of a first minutia M₁, block 77. This extraction consists substantially of reading the coordinates from the corresponding map and of marking the latter (in a corresponding associated field), making it possible to identify this as a minutia already considered. Then, similarly, a minutia M₂is extracted which is close to M₁, block 78, and a point M₁′ is determined on the reference image, from among those associated with the minutia M₁, and determined in the step of definition of correspondences 20, block 79. A point M₂′ is selected on the secondary image from among those associated with the minutia M₂, such that the difference in length of the segments M₁-M₂and M₁′-M₂′ is no greater in absolute value than a predetermined threshold value (for example 6 pixels, or 10% of the average length of the segments), block 80. If, from among all the points M₂′ associated with M₂, a point M₂′ is not identified which satisfies the length condition indicated, NO output from block 81, it is verified whether there is at least one other point M₁′ associated with M₁which has not yet been considered. If this is the case (YES output from block 82), this other point M₁′ is acquired, and there is a return to block 79, otherwise, it is verified whether there is at least one other minutia M₂close to M₁. If there is another close minutia (YES output from block 83), the new minutia M₂is acquired, the previous minutia M₂is marked rejected, and there is a return to block 78, otherwise it is verified if there is at least one other minutia M₁from among those not examined. If there is another minutia M₁(YES output from block 84), the latter is acquired, the previous minutia M₁is marked rejected, and there is a return to block 77, otherwise the print is considered to be non-identified, and there is progress to block 23.

[0051] Once there has been determination of the pair of points (minutiae) M₁, M₂, and the correlated pair M₁′, M₂′ (YES output from block 81), these pairs are marked as validated (block 87) and a subsequent point M₃is sought. In detail, block 88, from among the actual minutiae not yet considered in the association map 8, the minutia M₃which is closest to M₁and M₂is determined. In particular, the minutia is sought which minimises the MAX function [L(M₁M₂), L(M₁M₃)], in which MAX[] is the maximum value between two real numbers, and L() is the distance (euclidean norm) between two points on the two-dimensional Cartesian plane.

[0052] Subsequently, in block 89, the pairs of points M₁-M₂and M₁′-M₂′ are used to identify a linear transformation of rotation-translation and homothety (which therefore also takes into account a slight variation of dimension) between the primary and the secondary image. On the basis of the linear transformation identified, and using the coordinates of M₃, there is calculated the ideal coordinate in which the minutia which corresponds to M₃should be located on the secondary image (estimate of M₃′_nom, block 90), and from among the minutiae which correspond to M₃stored in the association maps 8, the minutia M₃′ is identified which is closest to the coordinates of M₃′_nom, and such that the difference between the length of the segments identified by the pairs of points M₁-M₃and M₁′-M₃′ and the difference between the segments identified by the pairs of points M₂-M₃and M₂′-M₃′ is no greater in absolute value than a predetermined threshold value (for example 6 pixels or 10% of the average length of the two segments), block 91. If the point M₃′ which satisfies the above conditions is not identified, output NO from block 92 applies, the minutia M₃previously determined is rejected, and is marked as already considered, block 94, and it is verified whether there are other minutiae in the association maps 8, which have not yet been considered; if this is the case (YES output from block 95), a new minutia M₃is taken into consideration, and there is a return to block 88, otherwise (NO output), a new point M₁′ is sought, and there is a return to block 82.

[0053] Otherwise, if point M₃is considered acceptable (YES output from block 92), the pair formed by the point M₃and the respective correlated point M₃′ is validated, block 97, and the comparison step is continued on the other actual minutiae which have not yet been considered, similarly to the process carried out for M₃. In particular, with reference to FIG. 8b, it is initially verified whether there are other actual minutiae which have not been taken into consideration, block 100. If this is the case, from the association maps 8 the minutia M_nis extracted which is closest from among the actual minutiae which have not yet been considered, to a pair of minutiae M_a, M_bwhich belong to one side of the triangular structure already identified. In particular, the minutia M_nis sought, which from among all the actual minutiae minimises the function MAX [L(M_aM_n), L(M_bM_n)], in which MAX[] and L() have the significance already explained, block 101.

[0054] Subsequently, similarly to the process described for block 89, there is identification of the rotation-translation which transforms the pair of points M_a-M_bof the primary image into the pair M_a′-M_b′ of the secondary image, block 102. Similarly to the case for block 90, the theoretical coordinate of the minutia is calculated which corresponds to M_n(estimate of M_n′_nomblock 103), and, similarly to the case for block 91, from among the actual minutiae corresponding to M_n′ stored in the association maps 8, the point M_n′ block 104 is sought. If a point M_n′ is not identified, the NO output from block 105 applies, the point M_npreviously determined is rejected and is marked as already considered, block 106, and it is verified whether other actual minutiae exist, with return to block 100. If this is the case (YES output from block 105), the minutiae M_nand the corresponding correlated point M_n′ are validated, block 107, and there is a return to block 100.

[0055] On completion of the evaluation of the actual minutiae of the primary image (NO output from block 100), the validated minutiae are counted, block 110, and it is verified whether the result of this counting is greater than a threshold required in order to validate the correspondences. If this is the case (YES output from block 111), the step of triangular comparison 21 ends; otherwise (NO output), it is verified whether there is a new initial pair of actual minutiae M₁, M₂, block 112. If the outcome of the verification is positive (YES output) there is a return to block 77, and the step of triangular comparison is carried out once more on the basis of the new initial pair of minutiae, and otherwise (NO output) there is a return to block 82.

[0056] The step of validation/identification 22 is now described for final validation of the minutiae. This step can be carried out according to one of the two alternative algorithms shown in FIG. 9 or in FIG. 10.

[0057] With reference to FIG. 9, according to a first alternative, initially the values are acquired of the pixels of two segments S_iand S_i′ which join two minutiae on the primary image, and the respective minutiae associated with them on the secondary image, block 120. In particular, as far as the segment S_iis concerned, this is acquired from among the segments stored in the images memory 3, on completion of the learning step.

[0058] Subsequently, there is carried out a step of identification and correction of the divergence, which is irregular in the fingerprint images. In particular, this step is carried out taking into account the fact that from among the developments of the tones of grey on two associated segments on the primary image and the secondary image, considerable divergence exists, such that when the integral norm between the two curves is calculated, the latter are found not to coincide. Furthermore, problems of alignment between curves have already been dealt with and solved in speech analysis, see for example L. Rabiner, B. H. Juang “Fundamentals of Speech Recognition,” PTR Prentice-Hall, Inc. 1993, using a technique defined as “Dynamic Time Warping”. On the basis of studies carried out by the inventor, this technique is also found to be useful in application to analysis of fingerprint images, taking into account the curved coordinate on the segment which joins the minutiae as the order of magnitude which corresponds to time. On completion of this step, which attempts to compensate for local deformation, and is not described in detail, block 121, two curves are obtained which are deformed compared with the original curves, in which the overlapping error has been minimized.

[0059] The two deformed curves are then compared in order to show their similarity. In particular, block 122, their integral norm is calculated as explained hereinafter; and the integral norm is compared with a predetermined threshold, block 123. If the norm is lower than the threshold (YES output from block 123), the pair of segments is validated, block 124, otherwise it is not validated, block 125. In both cases, it is verified whether all the segments have been examined which join pairs of validated minutiae, block 126. If the outcome is negative, there is a return to block 120, if the outcome is positive it is evaluated whether the total number of validated segments (or the number of minutiae from which a minimum number of validated segments starts), exceeds a predetermined threshold, block 127. If the number of validated segments exceeds the threshold (YES output from block 127) there is progress to block 24; otherwise there is progress to block 82.

[0060] According to the alternative procedure shown in FIG. 10, the validation is carried out through an algorithm which is indicated hereinafter as “validation via the directional field”. As shown in FIG. 10, initially there are again identified the segments S_iand S_i′ which join two validated minutiae of the primary image, and the corresponding associated minutiae on the secondary image, block 131. It is then verified that the length of the two segments are comparable, block 132. If this is not the case (NO output), it is verified whether all the segments which join all the pairs of validated minutiae have been examined, block 133. If this is not the case (NO output), a new segment is acquired, and there is return to block 131, otherwise it is verified whether the number of validated segments is greater than a predetermined threshold according to block 146, as described in greater detail hereinafter. If the lengths of the segments examined are comparable, YES output from block 132 applies, for each point of the segments S_iand S_i′ there is extracted data associated with the direction of the crests which intersect the segment or are close to the segment, block 134. For example, the direction is sought (quantified according to eight directions) of maximum variation of the tones of grey of the pixels. For this purpose use can be made of the algorithm described in D. C. Douglas Hung, “Enhancement and feature purification of Fingerprint Images,” Pattern Recognition, Vol. 26, pp. 1661-1671 (1993). Then the relative direction from amongst the direction of the segment and the direction of the crests is calculated.

[0061] When the field of directions along each segment is known, the angle is calculated between the relative directions of the crests in two corresponding points in the primary image and in the reference image, block 135. If this angle is smaller than a predetermined threshold (for example ±22°, NO output from block 136), the directions are considered to coincide, and the point is validated (block 137). Subsequently, as in the case of non-validation of the points (YES output from block 136), it is verified that all the points of the segments have been compared, block 138. Otherwise there is a return to block 135. If the outcome is positive, then the validated points are counted in block 140. It is then verified that the ratio between the number of validated points and the total number of points of the segments is greater than a predetermined threshold, for example 0.4, block 142. If the outcome is positive the segment is validated, block 143; otherwise the segment is not validated, block 144. It is then checked whether all the segments have been examined which join pairs of validated minutiae, block 145. If the outcome is positive it is verified whether the number of segments validated is greater than a predetermined threshold, block 146. Otherwise there is a return to block 131. In particular, this check can be carried out by requiring that the number of validated segments for each validated minutia must be greater than a predetermined threshold (for example 4), or the total number of validated segments is greater than a predetermined threshold. If the outcome of the comparison is positive, YES output from block 146, the print is considered recognised, and there is progress to block 24 of FIG. 2b; otherwise the print is not considered recognised and there is passage to block 82 of FIG. 8a.

[0062] For both the solutions (comparison after processing of dynamic time warping, or of evaluation of the directional field), the step of identification/validation can be incorporated directly in the step of triangular comparison, instead of being carried out on completion of the comparison, as described above. In this case, in the flow chart in FIGS. 8aand 8b, in all the steps in which it is verified that the difference in length of the segments between the primary image and the secondary image is within a specific field of tolerance (for example in the check for acceptance of the points of the secondary image to be associated with the minutiae of the primary image, steps 81, 92 and 105), it is possible to introduce the test of validation of the correspondence of the pair of segments, as well as simply checking the length. This inclusion during the triangular check is appropriate if the check is carried out with sufficient efficiency, and thus requires little time. In this case, the advantage is obtained that only the minutiae are accepted which can also pass the final check, thus reducing significantly the number of spurious minutiae in the triangular structures.

[0063] Hereinafter there is described the algorithm of comparison and determination of the minimum distance between a region of the secondary image which surrounds a point P_jof coordinates (X_j, Y_j), and all the pre-rotated images associated with all the validated minutiae P_iof coordinates (X_i, Y_i), using the integral norm, in accordance with step 58 of FIG. 6.

[0064] The object is to calculate the integral norm between two surfaces Si_pand Sj_sdefined as:

[0065] Sip={x,y,z}:z=grey(x,y)

[0066] with

[0067] Xi−8≦x<Xi+8; Yi−8≦y<Yi+8

[0068] for the points of the primary image, and

[0069] Sj_S={x,y,z}:z=grey(x,y)

[0070] with

[0071] Xj−8≦x<Xj+8; Yj−8≦y<Yj+8

[0072] for the points of the secondary image, in which grey(x,y) is the shade of grey of the image (secondary or primary) in the point (x,y).

[0073] The integral norm N between the two surfaces Si_pand Sj_sis provided by

[0074] N=∫∫_MxM·Sj_s(x,y)−Si_p(x,y)·dxdy  (1)

[0075] Since, in the case in question, the region MxM (16×16) and the functions Si_p, Sj_sfor calculation of the similarity are discrete, the double integral is transformed into a double summation, and the equation (1) becomes

[0076] N=ΣΣ·Sj_s(x−Xi+Xj,y−Yi+Yj)−Si_p(x,y)·  (2)

[0077] with

[0078] Xi−8≦x<Xi+8; Yi−8≦y<Yi+8.

[0079] Calculation of the norm thus defined is very onerous in the application considered, for which it is necessary to carry out seven comparisons for each actual minutia determined and for each pixel of the secondary image (therefore 7×70×512 ×512 comparisons). In order to solve this problem, according to an aspect of the invention, calculation of the above-described norm is carried out in parallel using an analog flash cell. array. In fact, as described in detail in the article by A. Kramer, M. Sabatini, R. Canegallo, M. Chinosi, P. L. Rolandi and P. Zabberoni “Flash-Based Programmable Nonlinear Capacitor for Switched-Capacitor Implementations of Neural Networks” in IEDM Tech. Dig. pp. 17.6.1-17.6.4, December 1994, flash cells can be used to calculate the absolute value of the difference between two values, by connecting the source and drain regions of two flash cells to one another and to an input node of a load integrator, supplying to the gate terminal of a first cell the voltage corresponding to the first value, storing in the first cell as a threshold voltage the second value to be subtracted from the first, supplying to the gate terminal of the second cell a voltage in addition to that supplied to the first cell, and storing in the second cell as a threshold voltage a value in addition to the second value to be subtracted (see in particular FIG. 3 of the aforementioned article). As indicated in the same article, it is also possible to calculate the sum of the difference between pairs of values, by connecting to one another the output nodes of different pairs of cells, of which there are provided (as threshold voltage and input voltage) the pairs of values to be summed (see FIG. 4 relating to calculation of the Manhattan distance between two vectors).

[0080] Using this principle, it is possible to carry out in parallel calculation of the norms, as defined above, between a region which surrounds a pixel of the secondary image and all the pre-rotated regions associated with a validated minutia. By supplying the value of these norms to a device for calculation of the minimum, it is thus possible to determine, from amongst all the pre-rotated images stored, the distance between the pre-rotated image which is the most similar to the region which surrounds the pixel examined, and this region. In addition by repeating the above-described structure of calculation of the minimum distance for all the actual minutiae identified, it is possible to compare simultaneously the pixel examined of the secondary image, with all the actual minutiae, in order to obtain the minimum distance of all the minutiae.

[0081] An example of a unit which can be used for calculation in parallel of the norm as described above, and based on the architecture shown in FIG. 4 of the aforementioned article by Kramer et al, is given in FIG. 11, and is now described in detail hereinafter.

[0082] In FIG. 11, the unit for calculation in parallel 160 comprises 70 blocks 161 (equal to the number of actual minutiae stored), each consisting of 7 sub-blocks 162 (equal to the number of pre-rotated regions associated with each actual minutia) consisting of 256 pairs of cells 163 (equal to the number of pixels of a region which surrounds the pixel P_jof the secondary image examined). Each pair of cells 163 comprises a first cell 164 and a second cell 165; the drain and source terminals of the cells 164, 165 of each sub-block 162 are connected together and to a node 168. Each sub-block 162 also comprises a load amplifier 166, the inverting input of which is connected to the node 168 of the respective sub-block 162, and the load amplifiers 166 of each block 161 are connected to a unit for determination of the minimum 167, which supplies the value of the minimum distance directly as output. The unit for calculation in parallel 160 also comprises a programming stage 170 which is connected to the pairs of cells 163, and is produced in a known manner (e.g., as described in European Patent Application EP-A-0 621 603 entitled “Method and circuit for tunnel effect programming of floating gate MOSFET transistors” in the name of the applicant) and a voltage generator 171 connected to the gate terminals of all the cells, 164, 165. In addition, the stage 170 and the generator 171 are connected to the cells 164, 165 by selection and addressing means not shown.

[0083] Then, with reference also to FIG. 12, at the end of the definition step, in each sub-block 162, the pairs of cells 163 are programmed with voltages Vt, Vt′ correlated with the levels. of grey of a respective pixel of the respective pre-rotated region, block 174, and. the cells of the pairs are programmed with complementary voltages according to the ratio indicated in FIG. 3 of the aforementioned article. The sub-blocks 162 of each block 161 are associated with a different pre-rotated region of a single effective minutia of the primary image, and the blocks 161 are associated with the different actual minutiae. During the recognition step, the voltage generator 174 supplies to each pair of cells 163 reading voltages Vg, Vg′ which are correlated with the levels of the grey of the 256 pixels which belong to the region which surrounds the point P_jexamined in each case in the secondary image, in a manner which is complementary for the-two cells of each pair, block 175. Thereby, each sub-block 162 calculates the integral norm between the associated pre-rotated region and the pixel P_j, block 175, and the units 167 determine its minimum value, supplied in parallel as an output for all the actual minutiae, block 177.

[0084] FIG. 13 shows the general architecture of a unit for extraction of the correspondence maps. In detail, an I/O device 180 receives the roughly filtered secondary image from the image memory 3 and supplies it to an image buffer 181. The latter is connected to a region extractor 182, which in each case, on the instructions of an address generator 183, extracts 16×16 pixels, equal to 256 values, which are supplied in parallel to the calculation unit 160. A map buffer 185 receives from the unit 160 the value of the minimum norms for each actual minutia calculated as described above, and supplies these norms to the I/O unit 180, which transmits them to the processing unit 4, for further processing.

[0085] Calculation of the similarity of segments planned in step 122 in FIG. 9 is similarly based on calculation of the integral norm, defined here by a straight integral, and no longer as a double integral. In view of the presence of discrete points, calculation of the integral norm is reduced to calculation of a single sum, which can still be carried out through flash cells, but in this case using only a number of pairs of cells of the unit 160 which is equal to the number of points on the segments to be compared. For this purpose, the length of the segments of the primary image and the secondary image are normalised, in order to be able to compare the segments directly. The levels of grey of the points of the segment of the primary image are stored as programming voltages of the pairs of cells 163, and to the inputs of these pairs of cells 163 there are supplied voltages which are proportional to the levels of grey of the points of the segment of the secondary image. The value of the integral norm is then read, and this value is normalized so that it can be compared with the threshold defined in step 123.

[0086] The method described has at least the following advantages. Firstly, it makes it possible to obtain a level of correct recognitions which is much greater than that which can be obtained with the previous devices, whilst maintaining a high level of reliability. Secondly, the calculation time is compatible with the applications planned, owing to the use of dedicated hardware units and to execution of many of the operations which are onerous from the point of view of calculation, during the preliminary processing. Thirdly, practical implementation can easily be adapted to individual requirements, for example to meet requirements in a security environment for civil use.

[0087] Finally, it is apparent that changes and variants can be made to the method described and illustrated here, without departing from the protective scope of the present invention, as defined in the attached claims. In particular, it is emphasised that the above-described operations can be optimised in various ways. The actual form of the flash cell array for calculation of the integral norm can also differ from the embodiment shown. The integral norm can also be calculated by programming and reading the flash cells in a manner different from that described, i.e., by programming the flash cells with the levels of grey of the secondary image, and supplying to the gate terminals voltages which are proportional to the levels of grey of the primary image. Finally, the final validation can be carried out as the last operation or during the triangular comparison, as described above, optionally using algorithms which are different from the two described above.