Source: http://www.google.com/patents/US20030103659?dq=6,370,566
Timestamp: 2013-12-11 02:59:27
Document Index: 540832514

Matched Legal Cases: ['art 11', 'art 12', 'art 13', 'art 14', 'art 15', 'art 16', 'art 17', 'art 18', 'art 19', 'art 20', 'art 21', 'art 22', 'art 23', 'art 24', 'art 11', 'art 12', 'art 11', 'art 13', 'art 12', 'art 14', 'art 13', 'art 15', 'art 14', 'art 16', 'art 15', 'art 17', 'art 14', 'art 16', 'art 18', 'art 17', 'art 19', 'art 16', 'art 18', 'art 20', 'art 21', 'art 20', 'art 22', 'art 20', 'art 23', 'art 21', 'art 22', 'art 24', 'art 23', 'art 11', 'art 12', 'art 12', 'art 14', 'art 15', 'art 16', 'art 17', 'art 18', 'art 17', 'art 17', 'art 17', 'art 17', 'art 17', 'art 17', 'art 17', 'art 17', 'art 17', 'art 17', 'art 17', 'art 17', 'art 17', 'art 19', 'art 20', 'art 21', 'art 22', 'art 23', 'art 24', 'art 15', 'art 17', 'art 21', 'art 22', 'art 13', 'art 15', 'art 17', 'art 21', 'art 22', 'art 23']

Patent US20030103659 - Fingerprint matching method and apparatus - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Advanced Patent Search | Sign inAdvanced Patent SearchPatentsIn a fingerprint image, this fingerprint matching method extracts as skeleton stability the area of a zone which is drawn around a pre-determined attention point and which does not contain any minutiae that are bifurcations or endpoints in ridges forming a fingerprint pattern, and calculates similarity...http://www.google.com/patents/US20030103659?utm_source=gb-gplus-sharePatent US20030103659 - Fingerprint matching method and apparatusPublication numberUS20030103659 A1Publication typeApplicationApplication numberUS 10/308,996Publication dateJun 5, 2003Filing dateDec 4, 2002Priority dateDec 5, 2001Also published asUS7068824Publication number10308996, 308996, US 2003/0103659 A1, US 2003/103659 A1, US 20030103659 A1, US 20030103659A1, US 2003103659 A1, US 2003103659A1, US-A1-20030103659, US-A1-2003103659, US2003/0103659A1, US2003/103659A1, US20030103659 A1, US20030103659A1, US2003103659 A1, US2003103659A1InventorsMasanori Hara, Kan SatoOriginal AssigneeNec CorporationExport CitationBiBTeX, EndNote, RefManReferenced by (1), Classifications (7), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetFingerprint matching method and apparatusUS 20030103659 A1Abstract In a fingerprint image, this fingerprint matching method extracts as skeleton stability the area of a zone which is drawn around a pre-determined attention point and which does not contain any minutiae that are bifurcations or endpoints in ridges forming a fingerprint pattern, and calculates similarity by collating said skeleton stability thus extracted with skeleton stability already registered. Images(11) Claims(18)
DESCRIPTION OF THE PREFERRED EMBODIMENT [0068] The preferred embodiment of the present invention will be discussed hereinafter in detail with reference to the accompanying drawings. In the following description, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be obvious, however, to those skilled in the art that the present invention may be practiced without these specific details. In other instance, well-known structures are not shown in detail in order to unnecessary obscure the present invention. [0069]FIG. 1 is a diagram showing the configuration of an embodiment of a fingerprint matching apparatus according to the present invention. FIG. 2 is a flow chart showing the operation of the skeleton stability extracting means 17 in FIG. 1. [0070] The fingerprint matching apparatus of this embodiment comprises a fingerprint image inputting part 11, a fingerprint image storing part 12, a skeleton extracting part 13, a skeleton data storing part 14, a minutia extracting part 15, a minutia data storing part 16, a skeleton stability extracting part 17, a skeleton stability data storing part 18, a database registering part 19, a database storing part 20, a minutia collating part 21, a skeleton stability collating part 22, a matching score integration part 23, and a matching result outputting part 24. [0071] The fingerprint image inputting part 11 digitizes and inputs fingerprint images that have been read via a fingerprint sensor or scanner. [0072] The fingerprint image storing part 12 stores fingerprint images that have been input from the fingerprint image inputting part 11 for a temporary period. [0073] The skeleton extracting part 13 conducts the binarization and thinning processes on the fingerprint image stored in the fingerprint image storing part 12 to extract skeleton data. [0074] The skeleton data storing part 14 stores the skeleton data extracted by the skeleton extracting part 13 for a temporary period. [0075] The minutia extracting part 15 extracts minutiae from the skeleton data stored in the skeleton data storing part 14. [0076] The minutia data storing part 16 stores the minutia data extracted by the minutia extracting part 15 for a temporary period. [0077] The skeleton stability extracting part 17 extracts skeleton stability from the skeleton data stored in the skeleton data storing part 14 and the minutia data stored in the minutia data storing part 16. [0078] The skeleton stability data storing part 18 stores the skeleton stability data extracted by the skeleton stability extracting part 17 for a temporary period. [0079] The database registering part 19 registers in the database the minutia data stored in the minutia data storing part 16 and the skeleton stability data stored in the skeleton stability data storing part 18. [0080] The database storing part 20 stores minutia data and skeleton stability data permanently. [0081] The minutia collating part 21 collates the minutia data extracted from the fingerprint image that has been input for use in search, with the minutia data registered in the database storing part 20, and calculate the similarity between these data. [0082] The skeleton stability collating part 22 collates the skeleton stability data extracted from the fingerprint image that has been input for use in search with the skeleton stability data registered in the database storing part 20, and calculate the similarity between these data. [0083] The matching score integration part 23 integrates the matching score calculated by the minutia collating part 21 and the matching score calculated by the skeleton stability collating part 22, and calculates the similarity for both the minutia data and the skeleton stability data. [0084] The matching result outputting part 24 outputs the matching score calculated by the matching score integration part 23. [0085] The operation of this embodiment will now be described, beginning with the types of images that are subjected to processing by this embodiment and the processing method employed by this embodiment. [0086] The fingerprint image inputting part 11 digitizes a fingerprint image read via a fingerprint sensor or scanner, and stores the digitized fingerprint in the image in the fingerprint image storing part 12 for a temporary period. FIG. 3 shows the resultant image. [0087]FIG. 3 shows an example of fingerprint image digitized at a resolution of 500 dpi, in accordance with the ANSI/NIST-CSL-1-1993 Data Format for the Interchange of Fingerprint, Facial & SMT Information, which was standardized by the National Institute of Standards and Technology in the U.S. This embodiment will be described below, using as an example a fingerprint image obtained by digitization usinng the above-mentioned method. [0088] The skeleton extracting part 12 first conducts the binarization process on a digitized fingerprint image and then the thinning process on the resultant image to obtain skeleton data, which is stored in the skeleton data storing part 14 for a temporary period. These binarization and thinning processes can be realized using a known art, for example, that is disclosed in Japanese Patent No. 2659046. FIG. 4 is an example of skeleton data extracted from the fingerprint image of FIG. 3. [0089] The minutia extracting part 15 extracts minutiae of a fingerprint, such as end points and bifurcations, from skeleton data, and stores them in the minutia extracting part 16 for a temporary period. This minutia extracting process can be realized using a known art, for example, that is disclosed in Japanese Patent Laying-Open (Kokai) No. Showa 60-12674. [0090] The skeleton stability extracting part 17 extracts skeleton stability using skeleton data and minutia data, and registers them in the skeleton stability data storing part 18. [0091] With reference to FIG. 5, the concept of skeleton stability obtained by the skeleton stability extracting part 17 of this embodiment will now be described. A point on a particular skeleton is assumed to be the attention point p. When a circle is drawn with the width of N number of skeletons as its radius around the point p, this attention point is defined as being stable at the width of the N number of skeletons, if the skeletons existing within the circle are highly reliable and if the circle does not contain any minutiae. By obtaining the maximum value of N, the skeleton stability for that attention point can be determined. In FIG. 5, less reliable areas are enclosed in shaded rectangles. For the attention point p in FIG. 5, the maximum value of N is 6. It should be noted here that the skeleton width of proximal skeletons may not necessarily be the same between the inner part and outer part of the fingerprint when viewed from the attention point. In order to deal with this problem, two semicircles with different radii may be drawn for the inner and outer parts of the fingerprint, respectively. Alternatively, either of the values may be used. [0092] With reference to FIG. 2, the operation of extracting skeleton stability conducted by the skeleton stability extracting part 17 will now be described in detail. [0093] When the operation of extracting skeleton stability begins, in Step A1, the skeleton stability extracting part 17 determines an attention point to extract skeleton stability and sets it as the initial attention point. In this embodiment, any pixel on skeleton data can be set as an attention point. While it is possible to set all the pixel points in the input image as attention points, this embodiment uses all the pixels on skeleton data as attention points in order to avoid having to handle a large amount of data during calculation and data registration. [0094] If use of all the pixels on skeleton data leads to such an inhibitive amount of data to be handled during calculation or data registration that may cause problems when configuring a real-world apparatus or system, then one can choose to set every few pixels on skeleton data as attention points. [0095] In Step A2 that follows, the skeleton stability extracting part 17 determines whether all the attention points set in Step A1 have been inspected or not. If the skeleton stability extracting process has been completed on all the attention points set in Step A1, this process is terminated. [0096] If, in Step A2, it is found that skeleton stability has not been extracted for all the attention points set in Step A1, then the skeleton stability extracting part 17 proceeds to Step A3 and determines skeleton stability for the attention points yet to be inspected. [0097] In Step A3, it sets the initial value of skeleton width for use as the unit of skeleton stability. In Step A4, it extracts the points of intersection between the perpendiculars drawn from the attention points and the group of proximal skeletons. [0098] In this embodiment, N=4 is set as the initial value in Step A3. This is because the initial value of N=3 will result in defining skeleton stability for too many attention points; it has been proven statistically that such skeleton stability cannot effectively serve as distinctiveness. [0099] When extracting points of intersection in Step A4, a perpendicular is first drawn from the attention point P. This perpendicular is drawn as follows. First, an attention point is traced along the skeleton, about 10 pixels each to the left and the right. Then, a line segment is drawn so that it will be vertical to the line segment defined by the two endpoints of the trace and that it will run through the attention point P. After this, a point of intersection is extracted between the perpendicular and the group of proximal skeletons. [0100] In Step A5, the skeleton stability extracting part 17 checks the points of intersection with the group of proximal skeletons that it has extracted in Step A4 to see if the Nth point of intersection exists when counted from the attention point. If such point of intersection exists, it inspects to determine whether the skeletons up to that point of intersection are viable as a fingerprint. More specifically, this inspection goes from the first through the Nth groups of points of intersection, and determines that the reliability of a skeleton is low if the distance between two adjacent points of intersection is by far larger than the average ridge width in the fingerprint (for example, over three times larger). [0101] If, in Step A5, the skeleton stability extracting part 17 determines that the Nth point of intersection from the attention point does exists and that the skeletons up to that point of intersection are viable as a fingerprint, then it proceeds to Step A6. If, on the other hand, it determines to the contrary, i.e., that the Nth point of intersection from the attention point does not exist or that the skeletons up to that point of intersection are not viable as a fingerprint, then it terminates the inspection of the attention points for skeleton stability and proceeds to Step All. [0102] In Step A6, the skeleton stability extracting part 17 calculates the distance D between the attention point P and the point of intersection with the Nth skeleton. In Step A7, it draws a circle with a radius of D around the attention point P, and inspects the skeletons existing in that circle. [0103] In Step A8, it inspects the circle to see whether it contains minutiae, such as end points, bifurcations, and/or crosses. If the circle contains minutiae, it terminates the inspection of that attention point for skeleton stability and proceeds to Step All. If the circle contains no minutiae, it proceeds to Step A9. [0104] In Step A9, the skeleton stability extracting part 17 inspects to determine whether the skeletons within the Nth circle are reliable as a fingerprint. Reliability as a fingerprint can be determined by checking whether skeletons exists within that circle and these skeletons form a striped pattern with regular intervals. This evaluation can be done by, for example, calculating the distance from a point on each of the skeleton within the circle to an adjacent skeleton and comparing the resultant distance with the average distance between fingerprint ridges. [0105] If the viability of the skeletons has been evaluated by other method, this information can be used in place of the results to be obtained by the above-described method. If the skeletons within the Nth circle is reliable, the skeleton stability extracting part 17 proceeds to Step A10. It increments the number N and returns to Step A4. If the skeletons within the Nth circle is not reliable, it terminates the inspection of the attention point for skeleton stability and proceeds to Step All. [0106] In Step All, the skeleton stability extracting part 17 registers the skeleton stability for the attention point. It can reach this step when any of the following conditions is satisfied: in Step A5, the absence of the Nth point of intersection has been confirmed; in Step A8, the existence of minutiae within the Nth circle has been confirmed; or in Step A9, the skeletons within the Nth circle has been determined that they are not reliable. Since reaching this step means that the skeletons within the (N−1)th circle are stable, the skeleton stability extracting part 17 registers (N−1) as skeleton stability and proceeds to Step A12. Exceptionally, if N is the initial value (4, in this embodiment), then (N−1) is 3 and is not viable as skeleton stability, it proceeds to Step A12 without registering N. [0107] In Step A12, the skeleton stability extracting part 17 sets the next attention point and returns to Step A2. [0108] The process thereafter varies, depending on whether the input data are for registration or search. [0109] If the input data are for registration, minutia data and skeleton stability data are retrieved from the input data by the database registering part 19, assigned an appropriate registration number, and registered in the database storing part 20 permanently. With this, the process completes. [0110] If the input data are for search, the minutia data are retrieved from the input data by the minutia collating part 21 and collated with the minutia data already registered in the database. The method of collating minutiae can be realized using a known art, for example, that is disclosed in Japanese Patent No. 2659046. [0111] Following this, the skeleton stability data are retrieved from the input data by the skeleton stability collating part 22 and collated with the skeleton stability data already registered in the database. Matching scores to represent the results of collation of skeleton stability according to this embodiment can be obtained, using the basic equations shown below. [0112] f(X,Y): skeleton stability at coordinates (X,Y) of the attention point in the fingerprint on the search side g(X,Y): skeleton stability at coordinates (X,Y) of the most proximal attention point of the fingerprint on the registration side h(s)=sm (where m is a parameter) [0113] When comparing the degrees of skeleton stability between the search and registration sides, the smaller skeleton stability represents the size of the common zone in which skeletons are stable. A larger value of skeleton stability translates into a higher similarity in this zone. By calculating skeleton stability for all the attention points and adding up the results, the similarity for the skeleton stability can be scored. [0114] The function h(s) is a function of the value s expressed in units of the area of the common zone in which skeletons are stable. In this embodiment, it is defined as an exponential function. In general, the larger the area of a common area is, a registered fingerprint is more likely to form a pair with a fingerprint for search. However, the probability of such pair being formed does not increase in linear proportion with the size of a common area; rather, the probability increases exponentially. The nilpotent m can be set at a value which will result in a large degree of separation between a registered fingerprint that forms a pair (mate fingerprint) and a registered fingerprint that does not form a pair (non-mate fingerprint). [0115] The equation (1) above assumes that the process of aligning a fingerprint on the search side and a fingerprint on the registration side has been completed. This aligning process can easily be realized by use of the center or axial direction of the fingerprint. The method of extracting the center of a fingerprint can be realized using a known art, for example, that is disclosed in Japanese Patent No. 002690103 or No. 002637764. The method of extracting the axial direction of a fingerprint can be realized using a known art, for example, that is disclosed in Japanese Patent No. 002776757. The aligning process may also be conducted using the ridge direction in a small zone, as is disclosed in Japanese Patent Laying-Open (Kokai) No. 2001-243465. [0116] The matching score based on the results of collating minutiae and the matching score based on the results of collating the degrees of skeleton stability are integrated by the matching score integration part 23 for the calculation of a final matching score. Examples of the method of integrating matching scores include arithmetic average and geometrical average. [0117] The final matching score is output externally by the matching result outputting part 24 for the determination of the similarity between the search-side fingerprint and the registration-side fingerprint. [0118] Separation between a mate fingerprint and non-mate fingerprints according to this embodiment will be described below. [0119]FIGS. 11A and 11B show skeleton stability extracted using the method of the present embodiment, in relation to the skeleton data of FIGS. 8A and 8B. [0120] Skeleton stability for the attention point, P1S, of the fingerprint for search and that for the attention point, P1F, which is the corresponding point of the registered fingerprint, are both 36. Skeleton stability, expressed as an area of a zone, is 36 for each, since these two attention points have a width of six skeletons (N=6), respectively. Collating skeleton stability data for these mate fingerprints using equation (1) results in 1296 (36�36) points (where the parameter m is 2). [0121] In FIGS. 12A and 12B, the fingerprint on the registration side is a non-mate fingerprint. Skeleton stability, which was extracted for the two attention points, P2F and P3F, are 16 and 25, respectively. Skeleton stability is 16 for both the positions, P2S and P3S, on the search side that correspond to the positions, P2F and P3F. Collating skeleton stability data for this non-mate fingerprint using equation (1) results in 512 (16�16+16�16) points (where the parameter m is 2). These scores, i.e., 1296 points for the mate fingerprint and 512 points for the non-mate fingerprint, represent a large degree of separation between the mate fingerprint and the non-mate fingerprint. [0122] By defining the size of a zone having no minutiae as a degree of skeleton stability, which is a new concept of distinctiveness, and collating fingerprints using such distinctiveness, matching accuracy can be improved even with fingerprints having an inadequate number of minutiae. [0123] Other embodiments of the present invention will now be described in detail referring to the drawings. [0124] The above-described embodiment includes a minutia extracting part 15 in its configuration, as shown in FIG. 1. Since minutiae can easily be extracted from a skeleton image, the skeleton stability extracting part 17 may be designed to also extract minutiae while conducting the skeleton data inspection process. [0125] Furthermore, while, as shown in FIG. 5, the above-described embodiment defines skeleton stability in units of skeleton width, skeleton stability may be defined using the radius of a circle that is inscribed in a zone. The concept of such definition will be described below with reference to FIG. 6. A particular attention point is assumed to be the point P. When a circle is drawn with a radius of r around the point P, this attention point is defined as being stable within this circle with a radius of r, if the skeletons existing within the circle are highly reliable and if the circle does not contain any minutiae. By obtaining the maximum value of r, the skeleton stability for that attention point can be determined. In FIG. 6, less reliable areas are enclosed in shaded rectangles. [0126] At the attention point P in FIG. 6, the maximum value of r is 42 pixels. This configuration, in which skeleton stability is defined with the radius of a circle, has an advantage that skeleton stability can easily be calculated as far as minutia data and skeleton reliability data are available. At the same time, however, it has a drawback that skeleton stability is liable to vary under the influence of changes in fingerprint size and image distortion. [0127] While, as shown in FIG. 1, the above-described embodiment uses a configuration in which a minutia collating part 21 and a skeleton stability collating part 22 are separate from each other, it is possible to combine the processes conducted by these parts in one component. For example, comparing skeleton stability data between search-side and registration-side after adjusting position by using the aligning data determined by collating minutiae will provide fairly accurate evaluation. Furthermore, for the purpose of collating minutiae, a possible method will be to subtract a penalty from the score according to the number of minutiae that remain unmatched and cannot form a pair. An embodiment using this method is also described in Japanese Patent No. 002730179. [0128] It is a rational method to subtract some points from a score as penalty if one fingerprint has minutiae at various positions and the other fingerprint does not have minutiae at some of the corresponding positions. [0129] The amount of subtraction may be calculated using skeleton stability. More specifically, if one fingerprint has minutiae at various positions, it becomes possible to score similarity more accurately by increasing the amount of subtraction in proportion to the degree of skeleton stability at the positions that correspond to those of minutiae in the other fingerprint. [0130] In addition to realizing various functions of the above-described elements as a hardware product, the fingerprint matching apparatus according to the present invention can be realized by loading a fingerprint matching program (application) incorporating the functions of the above-described elements, e.g., skeleton extracting part 13, minutia extracting part 15, skeleton stability extracting part 17, minutia collating part 21, skeleton stability collating part 22, and matching score integration part 23, in a memory of a computer processor, and controlling the computer processor. This fingerprint matching program allows the user to realize the above-described functions by storing it in a magnetic disc, semiconductor memory, or other storing medium, loading it from such storing medium onto a computer processor, and controlling such computer processor. [0131] Because of its configuration as described in the foregoing, the present invention has effects of improving matching accuracy by using skeleton stability to represent distinctiveness, even if a fingerprint does not have a sufficient number of minutiae to guarantee highly reliable collation of minutiae. [0132] Although the invention has been illustrated and described with respect to exemplary embodiment thereof, it should be understood by those skilled in the art that the foregoing and various other changes, omissions and additions may be made therein and thereto, without departing from the spirit and scope of the present invention. Therefore, the present invention should not be understood as limited to the specific embodiment set out above but to include all possible embodiments which can be embodies within a scope encompassed and equivalents thereof with respect to the minutiae set out in the appended claims. Referenced byCiting PatentFiling datePublication dateApplicantTitleUS7885437 *Feb 27, 2007Feb 8, 2011Nec CorporationFingerprint collation apparatus, fingerprint pattern area extracting apparatus and quality judging apparatus, and method and program of the same* Cited by examinerClassifications U.S. Classification382/125International ClassificationG06T7/00, G06K9/00Cooperative ClassificationG06K9/00067, G06K9/00087European ClassificationG06K9/00A2, G06K9/00A3Legal EventsDateCodeEventDescriptionNov 25, 2009FPAYFee paymentYear of fee payment: 4Dec 4, 2002ASAssignmentOwner name: NEC CORPORATION, JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:HARA, MASANORI;SATO, KAN;REEL/FRAME:013558/0939Effective date: 20021122RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google