`Ittvcheriah et al.
`
`USOO658O814B1
`(10) Patent No.:
`US 6,580,814 B1
`45) Date of Patent:
`Jun. 17, 2003
`
`9
`
`(54) SYSTEM AND METHOD FOR
`COMPRESSING BIOMETRIC MODELS
`
`6/2000 Maes ......................... 704/275
`6,073,101 A
`FOREIGN PATENT DOCUMENTS
`
`* 6/1990
`* 6/1990
`
`2-162400
`JP
`(75) Inventors: Abraham P. Ittycheriah, Danbury, CT
`O2-162400
`JP
`(US); Stephane H. Maes, Danbury, CT
`* cited by examiner
`(US)
`Primary Examiner Samir Ahmed
`(73) Assignee: International Business Machines
`(74) Attorney, Agent, or Firm-F. Chau & Associates, LLP
`Corporation, Armonk, NY (US)
`(57)
`ABSTRACT
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35 A System and method for building compressed biometric
`U.S.C. 154(b) by 0 days.
`models and performing biometric identification using Such
`models. The use of the compressed biometric models results
`in a significant decrease in the Storage requirements for
`biometric models in conventional biometric Systems. A
`given number of L reference biometric models are built. The
`L reference models are randomlv divided into M Subsets.
`y
`During user enrollment, distance measurements between a
`temporary biometric model and each of the reference models
`in the M Subsets are computed. The rank and distance
`parameters are used to build the compressed biometric
`models in accordance with the model: I(M. R, D(M. R)),
`where I represents the identity of the closest reference model
`in a corresponding Subset M, R, refers to the ranking of the
`closeness of the reference model to the temporary biometric
`model as compared with the closeness of each of the other
`reference models in the corresponding Subset M, and D
`refers to the corresponding distance measure between the
`reference model and the temporary biometric model.
`29 Claims, 6 Drawing Sheets
`
`(*) Notice:
`
`(21) Appl. No.: 09/126,894
`1-1.
`(22) Filed:
`Jul. 31, 1998
`51) Int. Cl." .................................................. G06K 9/00
`(52) U.S. Cl. ................
`382/115; 340/5.52; 704/238
`(58) Field of Search ................................. 382/115, 119,
`382/120; 704/221, 222, 230, 231, 236,
`237, 238, 239, 243, 245, 247, 250, 500,
`246, 273; 235/380; 340/5.1-5.92, 5.8–5.86;
`73/865.4
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`5,787,394 A 7/1998 Bahl et al. ................., 704/238
`5769,088 A
`8/199s Raike. 380/30
`5,812,739 A * 9/1998 Hirayama ................... 704/238
`6,073,096 A
`6/2000 Gao et al. ................... 704/245
`
`--------- -
`
`102
`-1
`
`Biometric
`Data
`
`Biometric
`Feature
`Extraction
`
`Model Construction
`Module
`(Clustering)
`
`
`
`
`
`IPR2023-00037
`Apple EX1022 Page 1
`
`
`
`U.S. Patent
`
`Jun. 17, 2003
`
`Sheet 1 of 6
`
`US 6,580,814 B1
`
`Biometric
`Data
`
`
`
`Biometric
`Feature
`Extraction
`
`
`
`
`
`f08
`
`Feature
`Vectors
`
`
`
`
`
`Model Construction
`Module
`(Clustering)
`
`
`
`FIG.
`
`IPR2023-00037
`Apple EX1022 Page 2
`
`
`
`U.S. Patent
`
`Jun. 17, 2003
`
`Sheet 2 of 6
`
`US 6,580,814 B1
`
`200
`
`202
`
`204
`
`2O6
`
`208
`
`
`
`Collect Biometric Data
`From A Random Group
`of L. Persons
`
`Generate L Reference
`Models
`
`Partition L Reference
`Models into M Subsets
`Of N Reference Models
`
`Designate Index Numbers
`To M Subsets and N
`Reference Models
`
`Store Reference Models
`
`FIG. 2
`
`IPR2023-00037
`Apple EX1022 Page 3
`
`
`
`U.S. Patent
`
`Jun. 17, 2003
`
`Sheet 3 of 6
`
`US 6,580,814 B1
`
`Ly
`
`Ls
`
`L¢
`
`Ly
`
`Lg
`
`Lg Lio Lay Lia
`
`N,
`
`Nx
`
`Ny
`
`No
`
`Nx
`
`N,
`
`No
`
`FIG. 3
`
`IPR2023-00037
`Apple EX1022 Page 4
`
`IPR2023-00037
`Apple EX1022 Page 4
`
`
`
`U.S. Patent
`
`Jun. 17, 2003
`
`Sheet 4 of 6
`
`US 6,580,814 B1
`
`400
`
`
`
`Collect Biometric Data
`
`
`
`Build Temporary Model
`
`Compute Vectoral Distance
`Between Feature Vectors
`And N Reference Models
`
`404
`
`Compute Distance Between
`Temporary Model And N
`Reference Models
`
`Process Distance Data To
`Generate Rank And
`Distance Parameters
`
`408
`
`Construct Compressed
`Biometric Model From Rank
`And Distance Parameters
`
`Store Compressed Biometric
`Model
`
`FG. L.
`
`IPR2023-00037
`Apple EX1022 Page 5
`
`
`
`U.S. Patent
`
`Jun. 17, 2003
`
`Sheet 5 of 6
`
`US 6,580,814 B1
`
`L;
`
`Ly
`
`Ls
`
`Ly
`
`bs
`
`be
`
`by
`
`bg
`
`bg Lio bay bye
`
`
`
`MODEL 1
`M3
`M,
`M,
`, 1), Ny =(My .2)],[N2 =(M, 1),N, =(Mz ,2)],[Ns=(Ms 11),Na =(Ms .2)]
`
`[N= (M,
`
`MODEL 2
`
`[N,=(M, 11),-05=(M, »1),N, =(M, 12),.1 =(M, ,2)],
`
`[Nz =(Mp ,1),.03=(Mp ,1),N; =(M, ,2),.25=(Mp ,2)],
`
`[Ns =(Ms 11),.08=(Ms s1)sNa =(Ms :2),.1 =(Ms ,2)]
`
`——M,
`
`——M2
`
`——M;
`
`FIG. 5
`
`IPR2023-00037
`Apple EX1022 Page 6
`
`IPR2023-00037
`Apple EX1022 Page 6
`
`
`
`U.S. Patent
`
`Jun. 17, 2003
`
`Sheet 6 of 6
`
`US 6,580,814 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Collect Biometric Data
`
`Build Temporary Model
`
`600
`
`602
`
`Compute Distance Between
`Temporary Model And N
`Reference Models
`
`604
`
`Process Distance Doto To
`Generate Rank And
`Distance Parameters
`
`606
`
`Construct Temporary
`Compressed Biometric
`Model From Rank And
`Distance Parameters
`
`608
`
`
`
`Compare Temporary
`Compressed Biometric
`Model With Stored
`Compressed Biometric Models
`
`6 f O
`
`
`
`Compute Vectorial Distance
`Between Feature Vectors
`And N Reference Models
`
`
`
`
`
`Access
`Granted
`
`IPR2023-00037
`Apple EX1022 Page 7
`
`
`
`1
`SYSTEMAND METHOD FOR
`COMPRESSING BIOMETRIC MODELS
`
`US 6,580,814 B1
`
`BACKGROUND
`1. Technical Field
`The present application relates generally to biometric
`Systems and, in particular, to a System and method for
`building compressed biometric models for each enrolled
`user in a biometric System, whereby the compressed bio
`metric models are Stored in an engine database of the
`biometric system rather than full biometric models.
`2. Description of Related Art
`Conventional biometric Systems generally operate by
`Storing full biometric models (e.g. codebooks) for each
`enrolled user of the System (i.e., the entire population of
`persons to be recognized by the biometric System). These
`models can be built, for example, from Statistical data Such
`as Gaussian distribution data which is computed from a
`collection of feature vectors that are generated during a
`biometric feature extraction process. The conventional bio
`metric Systems generally perform user identification or
`Verification by comparing the distances between a temporary
`biometric model (or feature vectors), which is generated for
`an individual making an identity claim, with training models
`of enrolled users (that are previously built and Stored during
`an enrollment process) and finding the training model hav
`ing the shortest distance from the temporary biometric
`model (or feature vectors).
`The problem with these conventional biometric systems,
`however, is that the Storage requirements for the biometric
`training models becomes Significant when the System is
`trained to recognize and Verify a large population. There is
`a need, therefore, for a System and method for building
`compressed biometric models for enrolled users which
`reduce the Storage requirements of the biometric System
`without affecting or reducing the ability of the biometric
`System to perform accurate biometric identification/
`Verification.
`
`15
`
`25
`
`35
`
`40
`
`SUMMARY
`The present application is directed to a System and
`method for building compressed biometric models. A com
`pressed biometric model for each enrolled user is con
`45
`Structed from rank and distance parameters which are
`derived by computing the distance between a temporary
`biometric model (which is built from biometric data pro
`vided by the user) and a plurality of biometric reference
`models which are Stored in the engine database of the
`50
`biometric system. The plurality of biometric reference mod
`els consist of a set of conventional biometric models (i.e.,
`not compressed) for a given number L of randomly chosen
`individuals, which are generated prior to user enrollment.
`The L reference models are randomly divided into M
`55
`Subsets.
`During enrollment, a temporary biometric model of a
`given user is compared with the reference models in each of
`the M Subsets So as to Score rank and distance values. The
`rank and distance parameters are used to build the com
`60
`pressed biometric models in accordance with the following
`model:
`
`where I represents the identity of the closest reference model
`in a corresponding Subset M, R, refers to the ranking of the
`
`65
`
`2
`closeness of the reference model to the temporary biometric
`model as compared with the closeness of each of the other
`reference models in the corresponding Subset M, and D
`refers to the corresponding distance measure between the
`reference model and the temporary biometric model.
`The compressed biometric models are then Stored in the
`engine database rather than storing the full (i.e., temporary
`biometric models) that are initially created during user
`enrollment. Consequently, by not having to Store the full
`biometric models for each enrolled user, the Storage require
`ments of the biometric System may be significantly reduced.
`These and other objects, features and advantages of the
`present System and method will become apparent from the
`following detailed description of illustrative embodiments,
`which is to be read in connection with the accompanying
`drawings.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a block diagram of a System for providing
`biometric model compression in a biometric System in
`accordance with a first embodiment,
`FIG. 2 is flow diagram illustrating a method for generat
`ing reference models in accordance with one aspect of the
`present System;
`FIG. 3 is a diagram illustrating an example for partition
`ing reference models in accordance with one aspect the
`present System;
`FIG. 4 is a flow diagram illustrating a method for building
`compressed biometric models in accordance with one aspect
`of the present System;
`FIG. 5 is a diagram illustrating Structures of compressed
`biometric models in accordance with one aspect of the
`present System; and
`FIG. 6 is a flow diagram illustrating a method for bio
`metric identification/verification utilizing the compressed
`biometric models in accordance with one aspect of the
`present System.
`
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENTS
`It is to be understood that the present System and method
`for building compressed biometric models described herein
`may be implemented in any conventional biometric System
`(e.g., handwriting and speech) and is not, in any way, limited
`to use with or dependent on any details or methodologies of
`any particular biometric System. The preferred biometric
`System in which the present System and method for biomet
`ric model compression may be implemented is the text
`independent speaker Verification System based on frame-by
`frame feature classification as disclosed in detail in U.S. Ser.
`No. 08/788,471 entitled: “Text Independent Speaker Rec
`ognition for Transparent Command Ambiguity Resolution
`And Continuous Access Control,” which is commonly
`assigned to the present assignee and the disclosure of which
`is incorporated herein by reference. In the following descrip
`tion of preferred embodiments, various aspects of the above
`incorporated U.S. Ser. No. 08/788,471 will be referenced
`and discussed in detail to illustrate the present System and
`method for biometric model compression as it applies to
`Speaker recognition.
`Referring now to FIG. 1, a block diagram of a biometric
`System for providing biometric model compression in accor
`dance with a first embodiment is shown. In general, the
`biometric system 100 includes a biometric front end 102, a
`biometric processing unit 104 and an output unit 122. The
`
`IPR2023-00037
`Apple EX1022 Page 8
`
`
`
`3
`biometric front end 102 includes an input unit 106 and
`biometric feature extraction module 108. The input unit 106
`receives biometric data and converts Such data into electrical
`Signals. The input unit 106 can be any conventional device
`Suitable for receiving the associated biometric data Such as
`a microphone for receiving Speech utterances. The biometric
`feature extraction module 108 receives the biometric data
`from the input unit 106 and generates feature data (e.g.,
`feature vectors). In the preferred text-independent speaker
`recognition embodiment, the biometric feature extraction
`module 108 processes digitized Speech utterances in Suc
`cessive time intervals to generate a Sequence of acoustic
`feature vectors in a manner understood by those skilled in
`the art.
`The biometric processing unit 104 includes a model
`construction module 110 (or “clustering module”), opera
`tively connected to the biometric feature extraction module
`108, for generating reference biometric models and tempo
`rary biometric models and for computing distance data
`which is used to construct compressed biometric models of
`the present System (as discussed in further detail below). In
`the preferred text-independent Speaker recognition System,
`the model construction module 110 is implemented as a
`vector quantizer module which quantizes (i.e., clusters)
`continuous valued feature vectors (generated by Speech
`utterances from a user) into a plurality of “codewords'
`which are used to construct a “codebook” (i.e., biometric
`model) in a manner understood by those skilled in the art.
`A partition module 114, operatively connected to the
`model construction module 110, divides a given number of
`L reference models (generated by the model construction
`module 11 during a pre-enrollment process) into M Subsets.
`A reference model store 112 is connected to the model
`construction module 110 for storing the L reference models
`(e.g., codebooks) in the partitioned format. AS discussed in
`detail below, this partition format for the L reference models
`provides the basis for constructing compressed biometric
`models. It is to be understood that, as explained in further
`detail below, the Selection of the reference population and
`Selection of the corresponding clusters (i.e., reference
`models) are done in advance of user enrollment (i.e., build
`ing compressed biometric models for the users). In an
`extreme case, this process can be performed after user
`enrollment. During biometric recognition, however, the
`clusters are known and fixed at the Server of the acceSS
`provider.
`A rank/distance module 116 processes the distance data
`provided by the model construction module 110, identifies
`the closest reference model or ranks the R closest reference
`models in each of the Subsets M and builds the compressed
`biometric models based on the identity and ranking and/or
`distance parameters. A rank/distance Store 120 receives and
`Stores the compressed biometric models.
`A comparator module 118, operatively connected between
`the rank/distance module 116 and the rank/distance Store
`120, operates during a biometric verification proceSS by
`comparing a compressed biometric model (which is tempo
`rarily generated for an individual making an identity claim)
`with each of the compressed biometric models stored in the
`rank/distance store 120. User verification will be found if a
`match is found between the temporary compressed biomet
`ric pattern matches and any of the Stored compressed
`biometric patterns.
`An output unit 122 (e.g., a monitor with an associated
`GUI menu or the like), operatively connected to the bio
`metric processing unit 104, allows a user to interact with the
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,580,814 B1
`
`4
`biometric System Such as during enrollment to advise the
`user whether or not enrollment has been Successfully
`executed, or during biometric recognition to advise a perSon
`whether or not his/her identity has been successfully veri
`fied. By way of example, the output unit 122 may be
`configured to provide an indication of whether or not the
`biometric system 100 has received an adequate amount of
`biometric data for proper identification. The output unit 122
`may be any conventional device Such as a display monitor,
`an indicator, a speech Synthesizer or a printer.
`It is to be understood that the system and methods
`described herein may be implemented in various forms of
`hardware, Software, firmware, or a combination thereof.
`Specifically, the biometric feature extraction module 108,
`the model construction module 110, the partition module
`114, the rank/distance module 116 and the comparator
`module 118 described above are preferably implemented in
`Software and may comprise any Suitable and preferred
`processor architecture for practicing the invention by pro
`gramming one or more general purpose processors. It is to
`be further understood that, because these components can be
`implemented in Software, the actual connections shown in
`the FIG. 1 may differ depending upon the manner in which
`the System is programmed. Of course, Special purpose
`processors may be employed to configure the present Sys
`tem. Given the teachings herein, one of ordinary skill in the
`related art will be able to contemplate these and similar
`configurations for the present System.
`Further, the reference model store 112 and the rank/
`distance Store 120 may be electronic computer read/write
`memory or any other suitable memory. Preferably, the
`present System is implemented on a computer platform in
`application domains such as a desktop, client-server
`environment, an embedded System and a telephony envi
`rOnment.
`
`Pre-Enrollment: Training and Partitioning
`Reference Models
`AS indicated above, prior to building the compressed
`biometric models, a given number “L” of random reference
`models must first be constructed and Stored in the System
`(i.e., a reference biometric model must be generated for each
`person of a random group of L individuals). Referring now
`to FIG. 2, a method for training and partitioning L reference
`models in accordance with one aspect of the present System
`is shown. Initially, biometric data is collected from a random
`group of L perSons and processed by the biometric front end
`102 to generate L Sets of feature vectors, one Set correspond
`ing to each individual in the random group (step 200). Each
`Set of feature vectors is processed by the model construction
`module 110 to generate a reference model for each of the L
`reference individuals (step 202).
`For instance, in accordance with the preferred text inde
`pendent Speaker recognition System described in U.S. Ser.
`No. 08/788,471, biometric data (in the form of input
`utterances) from each person of a random group L reference
`SpeakerS is converted into feature vectors which are clus
`tered into approximately 65 codewords which are used to
`construct a reference model (i.e., codebook) for each of the
`L reference Speakers under the operation of a vector quan
`tization module. These feature vectors are preferably com
`puted on Overlapping 30 msec frames with shifts of 10 mSec,
`and typically requiring approximately 10 Seconds of Speech
`to enroll each reference Speaker L.
`Referring again to FIG. 2, the L reference models (e.g.,
`codebooks) are then partitioned into M subsets, each of the
`
`IPR2023-00037
`Apple EX1022 Page 9
`
`
`
`S
`M Subsets having a certain number N of reference models
`associated there with (step 204). An index number is desig
`nated to each of the M subsets, i.e., M, where j=1 . . . total
`it of Subsets. Further, each reference model N in a corre
`sponding M Subset is designated with an indeX number, i.e.,
`N, where k=1 . . . total number of reference models in the
`corresponding M subset (step 206). The indexed subsets M,
`and their corresponding indexed reference models N are
`then stored in the reference model store 112 (step 208).
`FIG. 3 is a diagram which illustrates an example for a
`partition Structure for the L reference models in accordance
`with one aspect of the present system. As shown in FIG. 3
`by way of example, L reference models L (i.e., L-L) are
`partitioned into M, subsets with each M, subset having 4
`reference models associated therewith. It is to be understood
`that the number of reference models L that can be utilized is
`based on task Specific factors and can be determined on a
`trial-by-trial basis for each biometric system. These factors
`include, for example, the available Storage Space of the
`biometric System (since the L reference models are full
`biometric models) and the size of the population to be
`recognized.
`It is to be further understood that the number of Subsets M
`into which the totality of L reference model are divided is
`random and not important to the implementation and prac
`tice of the present invention. Given that there are N refer
`ence models for each of the M Subsets and that the total
`number L reference models is equal to the total N models of
`all M Subsets, it is preferable that N and M be chosen such
`that N' be much greater than the size of the population to
`be recognized (i.e., N'>>> size of enrolled users).
`User Enrollment: Construction of Compressed
`Models
`After the L reference models are partitioned (as discussed
`above), a user is enrolled by building and storing his/her
`corresponding compressed biometric model. Referring now
`to FIG. 4, a flow diagram illustrates a method for building
`compressed biometric models in accordance with one aspect
`of the present System. During enrollment, biometric data is
`collected for an authorized user and processed by the
`biometric front end 102 (step 400) in a manner similar to that
`described above for the creation of the L reference models.
`The resulting feature vectors are processed by the model
`construction module 110 to build a temporary biometric
`model for the user (step 402). The model construction
`module 110 then computes the distance between the tem
`porary biometric model and each of the reference models in
`each M Subset (step 404). For example, in the preferred
`text-independent Speaker recognition embodiment, for each
`of the M Subsets of reference codebooks (models), the vector
`quantizer (model construction module 110) computes the
`distance between the distributions (i.e., the mean values and
`variances of the cluster of feature vectors which are repre
`Sented as codewords) of the temporary biometric codebook
`with the distributions of each of the N reference codebooks
`constituting each of the M Subsets Stored in the reference
`model store 112.
`It is to be understood that any conventional method for
`computing the distance measure between the distributions of
`the temporary biometric model and the distributions of the
`N models may be implemented in the present method such
`as the Euclidean, Mahalanobis and Kullback-Leibler meth
`ods. It is also understood that these methods for computing
`distances are typically used for biometric Systems in which
`Gaussian mixtures are utilized (Such as speaker recognition).
`
`6
`For other biometric systems, however, the distance between
`the biometrics (or models) will be expressed differently.
`The computed distance measurements are then processed
`by the rank/distance module 116 to generate the rank and
`distance parameters which are used to build the compressed
`biometric models of the present system (step 406).
`Specifically, from the distance measurements, the rank/
`distance module 116 identifies the closest reference model,
`or ranks the R closest reference models in each of the M
`Subsets. The identity of the closest and/or ranked reference
`models and their corresponding distance values are then
`used to build the compressed biometric models (step 408) in
`accordance with the following model:
`
`where I represents the identity of the reference model N.
`with its corresponding ranking value R for the correspond
`ing Subset M, and D represents the distance measure corre
`sponding to the identified reference model I(M., R). In
`particular, R is the ranking of the closeness of the reference
`model to the temporary biometric model (based on the
`computed distance information) as compared to each of the
`remaining reference models in the corresponding Subset M.
`For example, the rank/distance module 116 will designate a
`first-rank Score (e.g. R) to the reference model N having
`the closest measured distance to the temporary biometric
`model, a Second-rank Score (e.g., R) to the N model having
`the Second closest distance to the user model, and So on.
`It is to be appreciated that the present biometric System
`100 can be preprogrammed to identify only the closest
`reference model in each of the M Subsets (if no ranking
`pattern is desired) or identify the R closest reference models
`for each of the M Subsets (i.e. i-1) if a ranking pattern is
`desired). Each of the biometric models is then stored in the
`rank/distance store 120 (step 410).
`Alternatively, the compressed biometric model may be
`built by directly processing the features vectors generated
`from the biometric data from a user during enrollment (as
`opposed to building a temporary user model and computing
`distance measure between user model and the N models as
`discussed above). For instance, in the preferred text
`independent Speaker recognition System, a vector quantizer
`(which functions similarly to the model construction module
`110) may evaluate speech utterances on a frame-by-frame
`basis by computing the vectorial distance between the
`feature vectors for each frame with each of the reference
`codebooks in the M subsets using methods known to those
`skilled in the art (step 402a). These distance computations
`are then processed by the rank/distance module 116 (Step
`406), whereby a histogram is created which counts how
`many frames of Speech have Selected each of the N code
`books (for each of the M subsets). The identity of the
`reference codebook in each M Subset which is most often
`selected, or the identity of the R closest reference codebooks
`in each M Subset which are most often selected, may then be
`used to generate a compressed biometric model for the user
`in the same manner as discussed above (step 408). The
`distance component D of the compressed biometric model is
`derived by calculating the average vectorial distance
`between the feature vectors associated with the closest
`identified reference codebook(s).
`It is to be understood that compressed biometric models
`which are built solely from the identity of the closest
`reference model in each M Subset (i.e., no ranking utilized)
`or from the R closest reference models in each M Subset (i.e.,
`ranking utilized) is Sufficient to obtain accurate user identi
`fication in biometric Systems that are employed to recognize
`
`US 6,580,814 B1
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`IPR2023-00037
`Apple EX1022 Page 10
`
`
`
`US 6,580,814 B1
`
`15
`
`25
`
`7
`either a Small population or an exclusive Set of enrolled users
`where it can be guaranteed that no two enrolled users share
`the same biometric pattern. Indeed, if the compressed bio
`metric models are built from ranking patterns alone (i.e., R.
`where i=1 or i>1), such models would have to be tested after
`enrollment to determine that no two Similar Signatures exist
`for any of the enrolled users. It is to be further understood
`that when employed in a large population, it is preferable for
`the compressed biometric models of the present System to be
`built from ranking data and distance data So the biometric
`System can perform accurate user identification and Verifi
`cation over a large population. Specifically, when a large
`population of users are enrolled in the biometric System, the
`probability of two or more enrolled users having the same
`biometric pattern increases, thereby requiring the inclusion
`of the distance component of the compressed biometric
`models So as to provide accurate user verification.
`Referring now to FIG. 5 a diagram illustrating the struc
`ture of a compressed biometric model in accordance with
`one aspect of the present System is shown. By way of
`example, using the partition Structure shown in FIG. 3,
`assume that the biometric system 100 is programmed to
`generate models with a ranking Ri where i=(1,2). ASSume
`further L, where r=(1-12), M, where j=1-3) and N, where
`k=(1-4). ASSume further that distance values shown repre
`Sent the distance measures computed during user enrollment
`between the temporary biometric model and the correspond
`ing reference models N (or that the feature vectors are
`one-dimensional, thereby providing a single distance value).
`As shown in FIG. 5, the distance measurements between the
`temporary biometric model (or the average distance value of
`the feature vectors) and the reference models (i.e., N-N.)
`for each of the Subsets M, M and M are used to rank the
`N reference models. With the distance values and ranking
`information, biometric models can be created as shown in
`FIG. 5. In particular, assuming that the biometric system 100
`is programmed to construct the compressed biometric pat
`terns by using the identity of the closest ranked reference
`models I(M., R), the resulting compressed biometric model
`would have the pattern shown in Model 1. Moreover,
`40
`assuming that the System is programmed to build com
`pressed biometric models with both the identification I and
`distance D components I(M. R. D(M, R)), the resulting
`biometric model would have the pattern shown in Model 2.
`Identification and Verification of Enrolled Users
`Referring now to FIG. 6, a flow diagram illustrating a
`method for user identification and Verification utilizing the
`compressed biometric models in accordance with one aspect
`of the present System is shown. During the identification/
`Verification phase, biometric data is provided by a perSon
`making an identity claim (step 600) and a temporary bio
`metric model is built (step 602). The distance between the
`temporary biometric model and each of the reference models
`in the M subsets is computed (step 604). This distance
`information is then processed by the rank/distance module
`116 to generate the rank and distance parameters (step 606).
`These parameters are then used to build a temporary com
`pressed biometric model (i.e., biometric pattern I(M., R.
`D(M, R))) in the same manner as discussed above (step
`608). The comparator module 118 compares the temporary
`compressed biometric pattern with the biometric models
`(generated during user enrollment) stored in the rank/
`distance store 120 (step 610). If the comparator module 118
`finds a match between the temporary compressed biometric
`model and one of the compressed biometric models in the
`rank/distance store 120 (positive result in step 612), the user
`
`8
`will be granted access to the System which is protected by
`the biometric recognition system 100 (step 612). If on the
`other hand the comparator module 118 does not find a match
`(negative result in Step 612), the user will be denied access
`(step 616).
`It is to be appreciated that the System may be programmed
`with user-specified tolerances that are utilized by the com
`parator module 118 during the matching process. For
`example, for Verification purposes, the allowable tolerances
`for the difference between the distance component
`(assuming a match for the identity component) of the
`temporary compressed biometric model and a Stored com
`pressed biometric model is programmable parameters. The
`allowable tolerance is essentially a function of the particular
`application and can be determined heuristically, by trial and
`CO.
`Alternatively, in the case of the preferred text
`independent Speaker recognition method, Speaker identifi
`cation may be performed on a frame-by-frame basis as
`described above. Particularly, the temporary compressed
`biometric model (which is constructed and compared with
`the Stored biometric models) may be built by processing the
`features vectors generated from the input utterances of the
`person making an identity claim (as opposed to building a
`temporary biometric model and computing distance measure
`between the temporary model and the reference models as
`discussed above). Specifically, a vector quantizer can be
`implemented to evaluate the Speech utterances of the
`Speaker on a frame-by-frame basis by computing the dis
`tance between the feature vectors for each frame with each
`of the reference models in each Subset M using methods
`known to those skilled in the art (indicated by the dotted line
`to step 602a). These distance computations are then pro
`cessed by the rank/distance module 116, whereby a histo
`gram is created which counts how many frames of Speech
`have selected each of the N models (for each of the M
`Subsets). The identity I of the reference model in each M
`Subset which is most often selected, or the identity I of the
`R closest reference mode