Method and apparatus for biometric verification with data packet transmission prioritization

[0001] The present invention relates generally to a data processing method, system and computer program product and more specifically to a method, system and computer program product for improving biometric data extraction and registration.

[0002] Security tokens compliant with the ISO-7816 international standards utilize a relatively slow serial communications pathway to transfer information between a host computer system and an electromagnetically connected security token. The serial pathway is operated in a half duplex mode where information only travels in one direction at a time. This limited communications ability can create a communications bottleneck for users and applications seeking to gain access to one or more security resources, services or applications contained therein. Additionally, security tokens are further limited by relatively slow processors and available storage memory.

[0003] This communications bottleneck is further exacerbated when using biometrics for user identification and authentication due to inefficient data extraction, relatively large data transfer requirements and lack of data packet prioritization. In the relevant art, biometric templates can be quite large with some implementations having templates in excess of 100 kilobytes and the best state of the art implementations having biometric templates closer to 300 bytes.

[0004] Even 300 bytes of data is still a considerable amount of information to be transferred when compared to a 6 character personal identification number (PIN) which requires only 48 bits of data (plus header overhead) to be transmitted from the host to the security token for about a 1 per 1,000,000 false acceptance rate.

[0005] Furthermore, in order to efficiently process the data packet, the receiving security token must have sufficient memory space available to store the incoming data packet in an APDU buffer located on the security token. If the size of the data packet exceeds the available APDU buffer size, the data will need to be segmented and sent sequentially, increasing both the number of handshakes between the host and the security token and the data transmission overhead (e.g., header information), thus reducing data transmission efficiency. A large biometric data transmission will require multiple data packets to be transmitted from the host to the security token, which considerably slows the overall authentication transaction to the point where a user may become impatient with the access delay. Therefore, it is highly desirable to reduce the number of data packets as much as possible, security permitting.

[0006] Another significant limitation in the relevant art is the manner in which data is extracted from the raw biometric sample. Currently, there is no mechanism available to direct the host to focus pre-processing of the raw biometric sample on areas or regions having a high probability of matching a reference template stored inside the security token. Rather, a “shotgun” approach is taken where a great deal of non-relevant information is extracted along with relevant data features, encapsulated in data packets and sent to the security token without any processing priority. The security token may process a significant number of data packets before it receives the information necessary to match the extracted biometric sample to the stored reference template.

[0007] A similar situation also exists in the relevant art art where a biometric sample is processed by a local client and sent over a network to authentication server. While processing capabilities and available memory storage are not specific limitations, the large amount of data transmission and subsequent processing required by the authentication server limits the ability to perform multiple simultaneous authentication transactions and unnecessarily ties up communications channels and available bandwidth.

[0008] A statistically based method to improve false acceptance and rejection rates in matching a biometric sample is disclosed in U.S. patent application 2001/0048025. However, the statistical approach does not attempt to optimize for extraction of relevant biometric data nor addresses the prioritization of data packets for matching a reference biometric template.

[0009] Thus, it would be advantageous to provide a mechanism for use with biometric systems, which reduces the number and size of data packet transmissions and provides data packet transmission prioritization.

[0010] It is an object of the invention to provide a method for reducing the total number and/or size of data packet transmissions for at least some processes of performing biometric authentication.

[0011] In accordance with the instant invention, there is provided a method of biometric authentication comprising the steps of:

• • [0012] a) providing a first biometric information sample;
  • [0013] b) extracting biometric data from the first biometric information sample, the extracted biometric data relating to features reproducibly extractable from said biometric sample;
  • [0014] c) grouping the biometric data into at least a first packet comprising a portion of the biometric data substantially less than the whole thereof and comprising data sufficient for identification of the biometric sample as relating to a known individual by a biometric matching engine within predetermined limits and at least a second packet comprising a portion of the biometric data substantially less than the whole thereof; and,
  • [0015] d) transmitting at least one biometric datum of the at least a first packet to the biometric matching engine as a first packet relating to the first biometric information sample.

[0016] In accordance with the instant invention, there is provided a system for biometric data extraction and transmission from a biometric sample received by a local client comprising:

• • [0017] a sensor for providing a first biometric information sample; and
  • [0018] a processor for extracting biometric data from the first biometric information sample, the extracted biometric data relating to features reproducibly extractable from said biometric sample, for grouping the biometic data into at least a first packet comprising a portion of the biometric data substantially less than the whole thereof and comprising data sufficient for identification of the biometric sample as relating to a known individual by a biometric matching engine within predetermined limits and at least a second packet comprising a portion of the biometric data substantially less than the whole thereof, and for transmitting at least one of the at least a first packet to the biometric matching engine as a first packet relating to the first biometric information sample.

[0019] In accordance with the instant invention, there is provided a storage medium having data stored therein, the data relating to instructions for performing the steps of:

• • [0020] providing a first biometric information sample;
  • [0021] extracting biometric data from the first biometric information sample, the extracted biometric data relating to features reproducibly extractable from said biometric sample;
  • [0022] grouping the biometric data into at least a first packet comprising a portion of the biometric data substantially less than the whole thereof and comprising data sufficient for identification of the biometric sample as relating to a known individual by a biometric matching engine within predetermined limits and at least a second packet comprising a portion of the biometric data substantially less than the whole thereof; and,
  • [0023] transmitting at least one of the at least a first packet to the biometric matching engine as a first packet relating to the first biometric information sample.

[0024] According to another aspect of the instant invention, provided is a method of biometric authentication from a biometric sample received by a local client comprising the steps of:

• • [0025] a. defining a plurality of regions associated with the biometric sample,
  • [0026] b. identifying which of the plurality of regions includes biometric data having a high probability of matching a pre-established reference,
  • [0027] c. extracting the biometric data from the identified regions,
  • [0028] d. incorporating the extracted biometric data into a plurality of data packets,
  • [0029] e. arranging the plurality of data packets in a hierarchy which allows selection of the data packets based on the probability of matching the pre-established reference, and
  • [0030] f. transmitting a data packet of the plurality of data packets having a known probability of matching the pre-established reference to a biometric matching engine.

[0031] According to yet another aspect of the instant invention, provided is a system for biometric data extraction and transmission from a biometric sample received by a local client comprising at least one biometric processing application operatively installed on the local client, wherein the at least one biometric processing application includes means for:

• • [0032] a. defining a plurality of regions associated with the biometric sample,
  • [0033] b. identifying which of the plurality of regions includes biometric data having a high probability of matching a pre-established reference,
  • [0034] c. extracting the biometric data from the identified regions,
  • [0035] d. incorporating the extracted biometric data into a plurality of data packets,
  • [0036] e. arranging the plurality of data packets in a hierarchy which allows selection of the data packets based on the probability of matching the pre-established reference, and
  • [0037] f. transmitting a data packet of the plurality of data packets having a known probability of matching the pre-established reference to a biometric matching engine.

[0038] In accordance with the instant invention, there is also provided a storage medium having stored therein data relating to executable instructions for:

• • [0039] a. defining a plurality of regions associated with the biometric sample,
  • [0040] b. identifying which of the plurality of regions includes biometric data having a high probability of matching a pre-established reference,
  • [0041] c. extracting the biometric data from the identified regions,
  • [0042] d. incorporating the extracted biometric data into a plurality of data packets,
  • [0043] e. arranging the plurality of data packets in a hierarchy which allows selection of the data packets based on the probability of matching the pre-established reference, and
  • [0044] f. transmitting a data packet of the plurality of data packets having a known probability of matching the pre-established reference to a biometric matching engine.

[0045] The method described above may be performed by a system having a biometric matching engine comprised of a server based application, a security token based application or a combination of a server based application and a security token based application which are used to cooperatively process and match a biometric sample.

[0046] The programs and associated data may be recorded on transportable digital recording media such as a CD ROM, floppy disk, data tape, or DVD for installing on a host computer system, server and/or security token.

[0077] This present invention provides a mechanism for use with biometric systems, which performs registration of biometric data against template data, thus allowing for a reduction in the size and/or number of data packet transmissions for successfully registering a biometric sample against a template and allows data packet transmission prioritization. The applications are envisioned to be programmed in a high level language such as Java TM, C, C++ or Visual Basic TM or in a lower level language such as Assembly language.

[0078] Referring to FIG. 1, a typical host computer system 105 is shown including a processor 5, a main memory 10, a display 20 electromagnetically coupled to a display interface 15, secondary memory subsystem 25 electromagnetically coupled to a hard disk drive 30, a removable storage drive 35 electromagnetically coupled to a removable storage unit 40 and auxiliary removable storage interface 45 electromagnetically coupled to an auxiliary removable storage unit 50.

[0079] A communications interface 55 subsystem is coupled to a network interface 60 and a network 65, a security token interface 70 and a security token 75, a user input interface 80 including a mouse and a keyboard 85, a biometric scanner interface 90 and a biometric scanner 95.

[0080] The processor 5, main memory 10, display interface 15 secondary memory subsystem 25 and communications interface system 55 are electromagnetically coupled to a communication infrastructure 100. The host computer system includes an operating system, a biometric processing application, other application software and data packet communication applications. The biometric processing application includes an ability to extract relevant data from a biometric sample received from the biometric scanner 95 based on selection criteria.

[0081] The selection criteria is optionally supplied from the security token 75, stored locally in the secondary memory 25 or optionally received from a remote server over the network 65. The data packet applications include the ability to transmit and receive messages using a protocol in the form of a TCP/IP protocol and an APDU protocol.

[0082] The security token 75 includes an electromagnetic connection compatible with the security token interface 70, the processor, volatile and non-volatile memory electromagnetically coupled to the processor, a runtime operating environment, a security executive application and a biometric matching engine. The non-volatile memory has operatively stored therein a reference biometric template belonging to a token holder for use in verifying the token holder by the security executive application and transferable selection criteria. The transferable selection criteria is in the form of locations of biometric features for use by the biometric processing application for extracting relevant data from a biometric sample received from the biometric scanner.

[0083] For purposes of this disclosure and the claims that follow, the term “security token” refers to hardware based security devices such as security tokens, smart cards, cryptography modules, integrated circuit cards, portable data carriers (PDC), personal security devices (PSD), subscriber identification modules (SIM), wireless identification modules (WIM), USB token dongles, identification tokens, secure application modules (SAM), hardware security modules (HSM), secure multi-media token (SMMC) and like devices having an internal processor, memory and a runtime operating system.

[0084] As explained heretofore, a performance limitation exists when biometric authentication is performed according to prior art methods. A typical prior art method processes all of the biometric information to correlate same with a template. The correlation is performed to determine a registration result which is comparable with a known threshold value. Unfortunately, such a process requires processing of all the data before a result is known. Therefore, in fingerprint processing the following steps are performed: preprocessing of the image, feature extraction, image alignment, feature extracted value determination within aligned frame of reference, registration of all extracted values against template values to determine registration result, and comparison of registration result threshold value.

[0085] For use on a smartcard, this requires that the extracted values fill at most one data packet or multiple data packet transmissions are required. Also, the entire data packet is processed prior to evaluation of the results which suffers due to memory access limitations within the smartcard. Unfortunately, when one data packet is not sufficient, either an individual is difficult to identify and often is falsely rejected or more packets are transmitted to the smarteard resulting in longer delays for everyone.

[0086] Referring to FIG. 2A, an exemplary fingerprint biometric sample is shown having an overlay shown in FIG. 2B. The overlay provides locations in a coordinate system for locating biometric features of interest for extraction. A Cartesian coordinate system is shown. Alternatively, other coordinate systems such as polar-rectangular are employed.

[0087] Furthermore, the axes shown are arbitrarily centered over the biometric sample. It will be appreciated by one of skill in the art that other arrangements function adequately so long as a consistent coordinate system is used for determination of the locations between the template and the fingerprint biometric sample.

[0088] Using such an overlay, it is provided according to an embodiment of the invention that the biometric features of interest are organisable according to a reasonable probability that each feature will lead to an accurate identification of a person providing the fingerprint biometric sample.

[0089] Referring to FIG. 3, a simplified flow diagram of an exemplary method according to the invention is shown. Feature data is extracted from a fingerprint biometric sample and is provided for correlation with a template at step 350. A value relating to a known feature within the fingerprint biometric sample is mathematically correlated with a feature template value. The resulting value is accumulated at step 352 according to the following expression:

[0090] $\begin{array}{cc}A=\sum _{i=1}^n\left(\mathrm{Diff}\left(V_{\mathrm{si}},V_{\mathrm{ti}}\right)/K\right)& \left(1\right)\end{array}$

• • [0091] where A is the accumulated registration value,
  • [0092] Vs is the value relating to a feature within the biometric sample,
  • [0093] Vt is the value relating to a feature within the biometric template,
  • [0094] K is a constant, and
  • [0095] Diff is a function of Vs and Vt having a result that is always other than negative or always other than positive.

[0096] All of the feature data values or a predetermined maximum number are accumulated and, this is verified at step 354. If there remain more feature values, then the process continues accumulating at step 352. Once all data is processed, the value A is compared to a threshold value at step 356 and, in dependence upon the comparison result at step 358, the process is directed to provide a result for the registration of either successful at step 360 or unsuccessful at step 362. A successful registration typically is followed by user identification or authorization. Alternatively, other uses of successful registration such as cryptographic signing are known.

[0097] Referring to FIG. 4A, a simplified flow diagram of another method according to the invention is shown. Because of the accumulative nature of equation (1), an absence of a feature results in a 0 sum gain to the overall accumulated result, A. This is easily verified by providing a set of values and then providing a same set absent one value. As such, there is no reduction in the overall value of A due to an absent feature. Further, no feature adds to the accumulated value an increment of less than 0.

[0098] A careful analysis of the value of A, as i increases, shows that once A has surpassed a value—for example the threshold value—it cannot decrease below said value. As such, termination of the summation upon exceeding the threshold value is sufficient for identification of the provider of the fingerprint biometric sample. Therefore, due to the cumulative effect of the summation, it is possible to use the accumulated value, A, to reduce the amount of processing required to register features against a template by terminating the process once the threshold is achieved. Also, data communication requirements to a processor for performing registration are reduced since subsequent packets need not be transmitted once the threshold value is reached. Of course, this does not affect reliability since a subsequent packet is optionally transmitted when the threshold is other than reached.

[0099] Further, the above noted equation requires a very small amount of memory storage for execution. The use of fewer variables requires few memory locations. Further, the accumulative nature of the equation means that other than the values of A and i, there is no memory required between accumulating one feature and another. Once a value is in the buffer, it is compared and accumulated, thereby reducing buffer requirements as well. Therefore, the overall process is implementable in a compact routine without a need for global variables.

[0100] At step 400, the accumulated value and a counter are reset. A first feature datum is received at step 402 and, at step 404, is accumulated into the value A. The resulting value A is compared against a threshold value at step 406 and when A is greater then an output signal indicative of success is provided at step 408. Alternatively, when A<=T at step 406, a verification of whether or not feature data remains is performed at step 410. If feature data remains, the remaining feature data is tracked at step 412, for example by incrementing a counter and another feature datum is received at step 402. When no more feature data remains, then an output signal indicative of fail is provided at step 414

[0101] Referring to FIG. 4B, another embodiment is shown wherein feature data is completely received prior to processing thereof. At step 400, the accumulated value and a counter are reset. Feature data is received at step 402B and, at step 404, a first datum is accumulated into the value A. The resulting value A is compared against a threshold value at step 406 and when A is greater then an output signal indicative of success is provided at step 408. Alternatively, when A<=T at step 406, a verification of whether or not feature data remains is performed at step 410. If feature data remains, the remaining feature data is tracked at step 412, for example by incrementing a counter and another feature datum is accumulated at step 404. When no more feature data remains, then an output signal indicative of a fail is provided at step 414

[0102] Referring to FIG. 4C, another embodiment is shown wherein A is compared to the threshold value every M iterations. At step 400C, the accumulated value, a loop counter, and a counter for monitoring remaining feature data are reset. A first feature datum is received at step 402 and, at step 404, is accumulated into the value A. The loop counter is incremented at step 416 and at step 418, if the loop counter is below the value M the process branches to step 404. If the loop counter value is greater than M, then the resulting value A is compared against a threshold value at step 406 and when A is greater then an output signal indicative of success is provided at step 408. Alternatively, when A<=T at step 406, the loop counter is reset at step 420 and a verification of whether or not feature data remains is performed at step 410. If feature data remains, the remaining feature data is tracked at step 412, for example by incrementing a counter and another feature datum is received at step 402. When no more feature data remains, then an output signal indicative of fail is provided at step 414.

[0103] Referring to FIGS. 5A and 5B, methods according to the invention are shown that are at least partially optimized for performance. Here, the features are organized in an order based on a likelihood of those features contributing to A. Thus, the feature having potential to add a greatest amount to the accumulated value, A, is provided first and then the features are supplied in an order of potential to add a greater amount to the accumulated value than subsequent features. Thus, there is supported a method for statistically providing a potential to provide a minimum number of accumulation steps in order to reach a successful registration. This allows for significantly reduced feature data communication for a successful registration and for reduced processing time for same.

[0104] Alternatively, instead of ordering all features based on a potential to add a greatest amount to the accumulated value, features are sorted into bins representative of feature quality or feature uniqueness. Those features that are of greater quality are likely to be more significant in the registration process and, as such, they are provided for registration earlier. Of course, some interspacing of different features is also possible though not typically preferable.

[0105] Referring to FIG. 5A, at step 400, the accumulated value and a counter are reset. A first feature datum is received at step 502, the feature data are provided in an order from most valuable feature datum to least valuable feature datum. A feature datum is considered more valuable if it is more likely to add a significant amount to A than other data or if the value it is likely to add to A is in excess of a value attributable to other data. At step 404, is accumulated into the value A. The resulting value A is compared against a threshold value at step 406 and when A is greater then an output signal indicative of success is provided at step 408. Alternatively, when A<=T at step 406, a verification of whether or not feature data remains is performed at step 410. If feature data remains, the remaining feature data is tracked at step 412, for example by incrementing a counter and another feature datum is received at step 502. When no more feature data remains, then an output signal indicative of fail is provided at step 414

[0106] Referring to FIG. 5B, another embodiment is shown wherein feature data is completely received prior to processing thereof. At step 400, the accumulated value and a counter are reset. Feature data is received at step 502B, the feature data provided in an order from most valuable feature datum to least valuable feature datum. A feature datum is considered more valuable if it is more likely to add a significant amount to A than other data or if the value it is likely to add to A is in excess of a value attributable to other data. At step 404, a first datum is accumulated into the value A. The resulting value A is compared against a threshold value at step 406 and when A is greater then an output signal indicative of success is provided at step 408. Alternatively, when A<=T at step 406, a verification of whether or not feature data remains is performed at step 410. If feature data remains, the remaining feature data is tracked at step 412, for example by incrementing a counter and another feature datum is accumulated at step 404. When no more feature data remains, then an output signal indicative of fail is provided at step 414

[0107] Referring to FIG. 5C, another embodiment is shown wherein A is compared to the threshold value every M iterations. At step 400B, the accumulated value, a loop counter, and a counter for monitoring remaining feature data are reset. A first feature datum is received at step 502, the feature data provided in an order from most valuable feature datum to least valuable feature datum. A feature datum is considered more valuable if it is more likely to add a significant amount to A than other data or if the value it is likely to add to A is in excess of a value attributable to other data. At step 404, the results of processing of the datum is accumulated into the value A. The loop counter is incremented at step 416 and at step 418, if the loop counter is below the value M the process branches to step 404. If the loop counter value is greater than M, then the resulting value A is compared against a threshold value at step 406 and when A is greater than an output signal indicative of success is provided at step 408. Alternatively, when A<=T at step 406, the loop counter is reset at step 420 and a verification of whether or not feature data remains is performed at step 410. If feature data remains, the remaining feature data is tracked at step 412, for example by incrementing a counter, and another feature datum is received at step 502. When no more feature data remains, then an output signal indicative of fail is provided at step 414.

[0108] A successful registration typically is followed by user identification or authorization, though other uses of successful registration such as retrieving a cryptographic key for cryptographic signing are known.

[0109] For use with different processors, it is a straightforward process of experimentation or analysis to determine a number of iterations, M, between threshold comparisons to statistically optimize performance. Since the accumulated value is updated for each feature, any number of iterations, 1, 2, . . . m, between threshold comparisons is supported.

[0110] Referring to FIG. 6A, a method according to the invention is shown similar to that shown in FIG. 5A for implementation on a smartcard 600 in execution of Java and in communication with a host processor 601. A data packet of up to 256 bytes is provided to the smartcard 600 including feature data at step 602. The data packet is received within the smartcard 600 at step 603. Prior to step 603, the accumulated value, A, is reset at step 600a. For each feature, the accumulated value is updated at step 604. The updated accumulated value is compared to a threshold at intervals of features of one feature (M=1 as shown) or more (M>1) at step 606. If the threshold is surpassed, then an output signal indicative of success is transmitted from the smart card at step 608 and received by the host processor at step 608A. If the threshold is not surpassed, a verification of remaining features is performed at step 610A. If features remain, the process continues accumulating values relating to other features at step 604. Once the data within the packet is processed, a new packet is requested at step 630. The new packet request is provided to the host processor 601 and is received thereby at step 630A. If no more packet data remains as determined at step 610B, then an output signal indicative of a fail is provided at step 614. If more packet data remains, then another packet is provided to the smartcard at step 602.

[0111] Advantageously, because of the accumulative nature of the method, only temporary values are needed during processing of a single packet. Some common implementations of Java require storage of global values in a slow form of memory. Thus, the use of temporary variables is beneficial. Once a new data packet is requested, the accumulated value and the feature index are stored in global variables, the new packet is retrieved, and then the global variables are loaded into temporary variables for use in further processing of the new data packet.

[0112] Referring to FIG. 6B, a method according to the invention is shown similar to that shown in FIG. 5B for implementation on a smartcard 600 in execution of Java and in communication with a host processor 601. The step 618 is added to the diagram of FIG. 6A to allow for an inner loop count and compare to allow for M greater than 1. Otherwise, the method operates similar to that described with reference to FIG. 6A. A data packet of up to 256 bytes is provided to the smartcard 600 including feature data at step 602. The data packet is received within the smartcard 600 at step 603. prior to step 603, the accumulated value, A, is reset at step 600a.For each feature, the accumulated value is updated at step 604. At step 618, a loop counter is incremented and compared to a value of M. When the loop counter is less than M, another value is accumulated at step 604. When the loop counter reaches M, the updated accumulated value is compared to a threshold at intervals of features of one feature (M=1 as shown) or more (M>1) at step 606. If the threshold is surpassed, then an output signal indicative of success is transmitted from the smart card at step 608 and received by the host processor at step 608A. If the threshold is not surpassed, a verification of remaining features is performed at step 610A. If features remain, the process continues accumulating values relating to other features at step 604. Once the data within the packet is processed, a new packet is requested at step 630. The new packet request is provided to the host processor 601 and is received thereby at step 630A. If no more packet data remains as determined at step 610B, then an output signal indicative of a fail is provided at step 614. If more packet data remains, then another packet is provided to the smartcard at step 602.

[0113] Of course, the absence of features is also useful as a registration feature. Thus, the absence of a feature is also potentially used in accordance with embodiments of the invention to identify an individual. A method of using absent features is shown in FIG. 7 and in accordance with the method of FIG. 3. Of course, a method such as those shown in FIGS. 4 and 5 is also useful with absent feature data.

[0114] The flow diagram of FIG. 7 shows an accumulation method wherein present features result in a certain accumulation relating to a distance between those features and data within the template. An indication of an absent feature results in an accumulation according to another formula. Thus, the accumulated value is reflective of features and absence of features within the fingerprint biometric sample. At step 700, the accumulated value, A, is reset. Feature data is received at step 702. For each datum, an analysis of whether it relates to a present feature is performed at step 703. When a datum relates to a present feature, the datum is accumulated using a similar method to that described above at step 704A. When the datum relates to an absent feature, the datum is accumulated using a process relating to absent features at step 704B. The accumulated value A is compared to a threshold value T at step 706. If A exceeds T, then an output signal indicative of success is provided at step 708. When A does not exceed T, then the remaining data is determined at step 710. When no data remains, an output signal indicative of fail is provided at step 714. Otherwise the process continues at step 703.

[0115] Of course, modifications to the process of FIG. 7 in accordance with the above presented variations are also envisioned.

[0116] Referring to FIG. 8, a method of sorting features and storing feature data within a template according to the invention is shown. At step 802, a fingerprint image is sensed. During enrollment, features are extracted from the sensed fingerprint image at step 804. A common frame of reference is determined at step 806 for the fingerprint image in order to provide for repeatable alignment thereof. This allows for comparison of feature data extracted from subsequently sensed fingerprint images with template data in a common frame of reference. For example, a common frame of reference is determined using the fingerprint core. Feature data is then determined based on the extracted features and the common frame of reference at step 808. Typically, the feature data includes some feature identifier and at least a value relating to the feature. Of course, when feature order is known, no feature identifier is needed. Based on the feature data a template is formed at step 810. The feature data are then each registered against the template to determine an individual accumulated value for each at step 812. The features are then sorted based on their accumulated values in descending order at step 814. Finally, an ordering of the features is stored at step 816 for later use in retrieving values relating to features in the order determined through the step of sorting.

[0117] Referring to FIG. 9, a method of sorting features and storing feature data within a template according to the invention is shown. At step 902, a fingerprint image is sensed. During enrollment, features are extracted from the sensed fingerprint image at step 904. A common frame of reference is determined at step 906 for the fingerprint image in order to provide for repeatable alignment thereof. This allows for comparison of feature data extracted from subsequently sensed fingerprint images with template data in a common frame of reference. For example, a common frame of reference is determined using the fingerprint core. Feature data is then determined based on the extracted features and the common frame of reference at step 908. Typically, the feature data includes some feature identifier and at least a value relating to the feature. Of course, when feature order is known, no feature identifier is needed. Based on the feature data a template is formed at step 910. The feature data are then each registered against the template to determine an individual accumulated value for each at step 912. The features are then sorted into bins based on their accumulated values similar accumulated values stored within a same bin at step 914. Finally, an indicator of each feature's bin is stored at step 916 for later use in retrieving values relating to features in an order relating to the binning thereof.

[0118] Referring to FIG. 10A, an exemplary fingerprint biometric sample is shown having a regional overlay. The regional overlay provides regions or areas and a coordinate system for locating biometric features of interest for extraction. A Cartesian coordinate system is shown, however, other coordinate systems such as polar-rectangular may be used as well.

[0119] Furthermore, the axes shown are arbitrarily centered over the biometric sample. It will be appreciated by one skill in the art that other arrangements will work as well so long as a consistent coordinate system is used for determination of the regions or areas having the highest probability of matching a reference template.

[0120] For fingerprints, it has been determined empirically that a regional overlay size having a grid of approximately 16×16 provides sufficient regional definition without significant deterioration in transaction processing speed. It should be noted that individual regions may be variably sized to accommodate specific features and/or locations to be extracted from a biometric sample.

[0121] In one embodiment of the invention, postliminary analyses are performed where a database containing a large number of biometric samples and their associated reference biometric templates are processed using a regional overlay. The regional overlay divides the biometric sample into individually identifiable regions. The density of regions may be varied to better discriminate between adjacent regions having closely clustered biometric features of interest for extraction. However, a balance is preferably maintained between the number of defined regions and available processing capabilities, since increasing the number of defined regions requires greater processing time, more memory and increases the number of data packets to be sent to the biometric matching engine.

[0122] The empirical results are recorded to determine the areas or regions having the highest probability of providing data of significant value in determining a match between the biometric sample and an associated reference biometric template. In this first embodiment of the invention, the determined regional locations or areas are not required to be specific to a particular individual but are determined statistically and/or using data mining techniques based on the large number of observations for a particular biometric sample type. For example, left index finger fingerprints.

[0123] In order for this technique to be effective, the database should contain a sufficient number of records to generate statistically significant results.

[0124] In a second embodiment of the invention, a heuristic approach is employed where a particular individual's biometric authentication transactions are recorded over time to determine which regions or areas provides the highest contribution to matching. In a third embodiment of the invention, a combination of postliminary and heuristic methods are employed which allows “fine tuning” of the regional selection criteria.

[0125] Referring to FIG. 10C, a histogram chart is shown depicting results obtained from identified regions having the highest frequency of matching a biometric reference template. From the chart, it is determined which regions should be sampled and the order in which the extracted results should be sent to the biometric matching engine.

[0126] Referring to FIG. 10B, the identified regions having the highest match rates are shown which were interpreted from the results depicted in FIG. 10A. From FIG. 10A, it is apparent that region D4 was found to provide a majority of information for matching a counterpart biometric reference template. Therefore, the data extracted from region D4 is preferably encapsulated and sent first to the biometric matching engine, followed by the data extracted from region C4 and progressing in descending order of priority the data extracted from the remaining identified regions. Areas not providing significant contribution to matching the reference biometric template are optionally excluded from the data transmitted to the biometric matching engine.

[0127] Referring to FIG. 10D, an overview of the regional selection criteria generation and use is depicted. For this embodiment of the invention, a computer system 205 includes a biometric matching engine 210 receiving inputs from databases storing the recorded biometric samples 225 and the counterpart reference templates 230. The databases should have a sufficient number of records to provide statistically significant results for analysis by a statistical analysis engine 215.

[0128] A regional overlay 220 is used by the biometric matching engine 210 to consistently define regions on each sample being matched against its counterpart reference biometric template. Alignment of the biometric samples to match their counterpart reference templates is performed in a way that assures consistency in orientation for determination of the relevant regions for sampling. Depending on the alignment processes employed by the biometric matching engine 210, normalization of the biometric samples and their counterpart reference templates to a uniform orientation is sometimes required.

[0129] The statistical analysis engine 215 receives the output from the biometric matching engine 210 and determines the probability of match by region 235. This information is then used to generate 240 regional selection criteria 245. As an alternative, the output from the biometric matching engine 210 is graphically displayed and regional selection criteria 245 determined visually. The regional selection criteria 245 are stored locally, inside of a security token or, alternatively, received from a remote source such as a networked authentication server. The regional selection criteria 245 is used by a biometric processing engine 255 associated with the local client 105 for processing a user's biometric sample 265 received 270 from the biometric scanner 95. The regional selection criteria 245 optionally include alignment information to normalize the received biometric sample to the same orientation as the counterpart biometric reference template.

[0130] The output 280 from the biometric processing engine 255 is incorporated into data packets having a hierarchy 275 based on the probability of matching a counterpart reference biometric template. The hierarchy prioritizes the data packet containing the extracted data having the highest probability of matching to be transmitted 285 first to a biometric matching engine.

[0131] Referring to FIG. 10E, an embodiment of the invention is shown wherein data packets are transmitted 285A over a network 65 and processed by a biometric matching engine 210A installed in a remote authentication server 205. In this embodiment of the invention the data packets are transmitted in TCP/IP protocol or an equivalent packet switching communications arrangement. The biometric matching engine 210A compares the received biometric sample information and compares it to a database of reference templates 230A for identification and authentication purposes. In this embodiment of the invention, the database of reference templates 230A also includes the regional selection criteria which is received by the local client 105 prior to receiving the biometric sample from the user 265 (not shown.) In a related embodiment of the invention, the incoming biometric sample data including information related to the region in which the data was extracted is recorded in a database 225A along with a matching success rate. The recorded information 225A is used by a statistical analysis engine 215A to heuristically improve matching over time.

[0132] Referring to FIG. 10F, another embodiment of invention shown wherein data packets are transmitted 285B to a security token 75 having a biometric matching engine 210B and a reference biometric template 230B specific to the token holder operatively installed therein. In this embodiment of the invention, the data packets are transmitted in an APDU protocol. The biometric matching engine 210B compares the received biometric sample information to the reference template 230B for identification and authentication purposes.

[0133] Referring to FIG. 10G, another embodiment of the invention is shown where the regional selection criteria 245 is stored inside this security token 75 and is sent 287 to the biometric processing engine 255 for preprocessing of a user's biometric sample 265 received 270 from the biometric scanner 95. The output 285C from the biometric processing engine 255 is sent to the security token 75 for processing by the biometric matching engine 210B. The biometric matching engine 210B compares the received biometric sample information and to the reference template 230B for identification and authentication purposes.

[0134] Referring to FIG. 10H, another embodiment of the invention is shown where the regional selection criteria 245 is stored inside this security token 75 and is transmitted 287 to the biometric processing engine 255 for preprocessing of a user's biometric sample 265 received 270 from the biometric scanner 95. The output 285A from the biometric processing engine 255 is transmitted 285A over the network 65 and processed by the biometric matching engine 210A installed in the remote authentication server 205. As previously described, the biometric matching engine 210A compares the received biometric sample information and to data within a database of reference templates 230A for identification and authentication purposes

[0135] Referring to FIG. 11, a flowchart is depicted for implementing an embodiment of the invention. The process is initiated 300 by receiving and preprocessing 302 a biometric sample using regional selection criteria received from a host containing a biometric matching engine 306.

[0136] The regional selection criteria is then applied to the received biometric sample to define specific sampling regions 304. Regions having the highest probability of matching a reference are identified 308, followed by the extraction of relevant biometric data from the identified regions 310.

[0137] The extracted data is then encapsulated into data packets 312 and arranged in a transmission hierarchy allowing for selection of the data packet(s) having the highest probability of matching the reference template 314. The data packet having the highest probability of matching the reference template 316 is transmitted first to the biometric matching engine. Of course, so long as the first data packet transmitted has a sufficient probability of matching the reference template, it is not essential that it have the highest probability of matching the reference template.

[0138] The biometric matching engine compares the received data against a reference biometric template 318. If a match is obtained using the first data packet 320, the user is authenticated and access to token resources is allowed 328. If a match is not obtained using the first data packet 320, the biometric matching engine determines whether an additional data packet is needed to match the reference biometric template 322. In this situation, it is possible that the initial data packet received is sufficient to determine that it does not belong to the proper user and ends the authentication transaction 330. Alternately, it is possible that the biometric sample is somehow degraded due to physiological changes associated with the user, environmental conditions impacting the quality of the sampling and/or problems associated with the biometric scanner. In this situation, another data packet is requested 322 from the client.

[0139] The client responds by sending the data packet having the next highest priority to the biometric matching engine 324. This process may be repeated until all data packets maintained by the client had been sent to the biometric matching engine or until a match is made between the consolidated sample and the reference template. Processing ends if all data packets maintained by the client have been transmitted to the biometric matching engine without a match 330.

[0140] Referring to FIG. 12A, shown is the fingerprint of FIG. 2 with a grid overlay. The grid overlay 1200 allows for determination of ridge flow angles within predetermined areas of the fingerprint. For example, between lines B and C and lines 2 and 3 is a region wherein ridge flow angles are relatively straight and relatively parallel. This allows for determination of ridge flow angles with a reasonable amount of accuracy is preferred for use in ridge flow angle feature registration. The grid overlay 1200 is spaced and sized relative to the fingerprint biometric sample to be repeatably overlaid in a consistent fashion. So long as the grid is aligned similarly to the fingerprint image during template generation—enrollment—and during feature extraction for registration, the resulting ridge flow angles should match.

[0141] Referring to FIG. 12b, the grid is shown with box numbering from 1 to n across the rows and down the columns. The use of the numbering allows for identification of expected ridge flow angles based only on grid number. As such, the previously identified box is box number 19. Thus instead of storing a grid box identifier, it is possible to sort all ridge flow angles in order of box number such that the ridge flow angle of box 19 is stored as the 19th ridge flow angle in the feature data.

[0142] Referring to FIG. 12C there is shown a single box of the grid with a vector representing the ridge flow angle within the box. As is evident from the figure, there is a size for a box that is near optimal wherein the ridges are sufficiently long to make angle determination straightforward and are sufficiently small that the ridge flow within each box is fairly approximated by a straight line as is the case within grid box 19. Other boxes, such as grid boxes 1 and 36 are less amenable to accurate ridge flow angle determination. As such, it is evident that some ridge flow angle determinations form better features than others since they represent the ridge flow more accurately.

[0143] Thus, the grid shown in FIG. 12C is replaceable with a set of indices indicating each grid box and an angle of the ridge flow within said grid box. Of course, if all ridge flow angles are stored, one for each grid box, then a need to store the indices is obviated.

[0144] Of course, ordering of the grid boxes in order of better ridge flow angles to worse ridge flow angles reduces the overall number of feature comparisons necessary in accordance with the methods shown in flow diagrams of FIGS. 4-7.

[0145] Referring to FIG. 13, a simplified flow diagram of a method of template formation according to the invention is shown. A first biometric information sample is provided at step 1301. The first biometric information sample is sensed to result in sensed data. The sensed data is preprocessed to filter same in order to provide data of a quality suitable for use in template generation. The sensed data is analysed to extract therefrom biometric data at step 1302. The biometric data relates to features reproducibly extractable from the sensed data.

[0146] Features having a high likelihood of accurate registration with a template are then identified within the biometric data at step 1303. These features are generally features having a higher quality factor or a greater uniqueness. Typically, features that are known to result form noise or dirt are not identified in this step. The result of step 1303 is an identification of those features most likely to be useful in biometric registration against a template. In step 1304, a template is stored including data relating to an ordering of the biometric data relating to features, the ordering based on the identification. For example, the biometric data are ordered based on a quality thereof. As such, during the registration process, higher quality features are provided first for registration. Alternatively, the biometric data is stored ordered according to a range of quality into which each datum is grouped. Thus, higher quality features are provided first though, not necessarily in order of their individual quality.

[0147] Referring to FIG. 14, a simplified flow diagram of a method of template formation according to the invention is shown. A first biometric information sample is provided at step 1401. The first biometric information sample is sensed to result in sensed data. The sensed data is preprocessed to filter same in order to provide data of a quality suitable for use in template generation. The sensed data is analysed to extract therefrom biometric data at step 1402. The biometric data relates to features reproducibly extractable from the sensed data.

[0148] Features statistically likely to have a high likelihood of accurate registration with a template are then identified within the biometric data at step 1403 based on a priori knowledge of locations of features statistically likely to have higher quality. These features are generally located where the sensor is most likely to sense them effectively. Typically, features that are known to reside in locations or regions having higher noise are not identified in this step. The result of step 1403 is an identification of those features most likely to be useful in biometric registration against a template. In step 1403, a template is stored including data relating to an ordering of the biometric data relating to features, the ordering based on the identification. For example, the biometric data are ordered based on a quality thereof. As such, during the registration process, higher quality features are provided first for registration. Alternatively, the biometric data is stored ordered according to a range of quality into which each datum is grouped. Thus, higher quality features are provided first though, not necessarily in order of their individual quality.

[0149] Similarly, it is within the scope of the invention to reorder other features extracted from a biometric sample such as minutia angles in accordance with a likelihood that those features will contribute most significantly to the accumulated value.

[0150] Though the above description relies upon selection criteria provided for determining feature order, in an alternative embodiment feature order is predetermined or determined dynamically based on some other criteria and without being provided. Though the fullest benefits of feature ordering for reducing data processing needed to successfully register a biometric sample against a template is not as sure, statistically, even predetermined ordering results in substantial benefits.

[0151] Though the above description relates specifically to fingerprint analysis, it is also applicable to other biometric samples such as iris scans, retinal scans, palm prints, toe prints, voice prints and so forth.

[0152] The foregoing described embodiments of the invention are provided as illustrations and descriptions. They are not intended to limit the invention to precise form described. In particular, it is contemplated that functional implementation of the invention described herein may be implemented equivalently in hardware, software, firmware, and/or other available functional components or building blocks. No specific limitation is intended to a particular security token operating environment. Other variations and embodiments are possible in light of above teachings, and it is not intended that this Detailed Description limit the scope of invention, but rather by the Claims following herein.