Classifications

• • G—PHYSICS
  • G06—COMPUTING OR CALCULATING; COUNTING
  • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
  • G06V40/00—Recognition of biometric, human-related or animal-related patterns in image or video data
  • G06V40/10—Human or animal bodies, e.g. vehicle occupants or pedestrians; Body parts, e.g. hands
  • G06V40/18—Eye characteristics, e.g. of the iris
• • G—PHYSICS
  • G06—COMPUTING OR CALCULATING; COUNTING
  • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
  • G06V10/00—Arrangements for image or video recognition or understanding
  • G06V10/70—Arrangements for image or video recognition or understanding using pattern recognition or machine learning
  • G06V10/74—Image or video pattern matching; Proximity measures in feature spaces
  • G06V10/75—Organisation of the matching processes, e.g. simultaneous or sequential comparisons of image or video features; Coarse-fine approaches, e.g. multi-scale approaches; using context analysis; Selection of dictionaries
  • G06V10/751—Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching

Definitions

• the present invention relates generally to methods using biometric data to authenticate a physical person, e.g. when identifying this person or verifying an alleged identity.
• biometric authentication biological features are measured from a human biological entity (such as a finger, face, iris, voice, palm, DNA%) to get biometric data that are used to authenticate an individual.
• biometric raw data for example the picture of a fingerprint or of an iris
• Processing usually comprises image processing (such as brightness and contrast enhancement, resizing, framing and so on), normalizing in order to unwrap the iris region to a normalized rectangular block with a fixed size, etc.
• a biometric template is a synthesis of all the characteristics extracted from the source, in a suitable format so as to allow comparison between different templates extracted from a similar biological entity.
• the authentication process may be either verification or identification:
• Verification consists in checking that the biometric data of the user are close enough to the biometric data stored supposedly for this user.
• - Identification consists in determining, among a set of previously stored biometric data, if one of them is close enough to the user's biometric data.
• Figure 1 depicts a known example of enrolment algorithm for iris recognition.
• an individual presents a class to be enrolled into the system.
• a class is defined as a biological entity of one individual.
• a class is defined as one eye of one individual.
• a picture of the enrolled individual iris is acquired through a camera.
• the picture is processed to compute an enrolled biometric iris template which, at step 30, is saved in an enrolment database or on a token.
• the enrolled biometric template is stored for further reference. Sometimes, even the enrolment biometric raw image is stored instead of the template.
• Figure 2 depicts a known authentication algorithm based on iris recognition.
• a picture of the iris of the person to be authenticated is taken with a camera.
• the system processes this image and creates an iris ongoing template.
• This ongoing template is matched at steps 40 and 42 to all the reference templates stored in the enrolment database in case of identification, or to the template of the alleged user in case of verification.
• the matching operates on whole templates and is based on a measure of similarity like the Hamming distance, that gives the proportion of data that are equal between the two templates to check for matching. Usually, the closest match, if it is close enough, identifies at steps 44 and 46 the corresponding user.
• biometric template is transformed for each application by a secret reversible transformation such as permutation or XOR encryption. This technique prevents from storing sensitive biometric data.
• biometric templates are produced similarly to above, each template is then transformed using the secret reversible transformation, and the transformed template is stored in a database or on a token.
• the ongoing template is produced similarly to the above. Transformed templates are reverted to biometric templates (by applying a reverse transformation), to be matched with the ongoing template as described above.
• sensitive data for example the biometric template
• a pseudonym identifies unambiguously an individual, without necessarily revealing his actual identity.
• a single individual may have a plurality of pseudonyms, for example in various applications, but one pseudonym corresponds to a single individual or entity.
• Pseudonyms can be revoked at any time, just by replacing the one-way function.
• the comparison between the enrolled and the ongoing biometric data is performed on revocable pseudonyms instead of the original templates.
• biometric template is not suitable for directly applying a cryptographic mathematical one-way transformation. Even a one-bit difference in the template will lead to very different transformed data, making further similarity check meaningless.
• the intra-class variability refers to the variability between two different acquisitions of the same class.
• the extra-class variability refers to the variability between the acquisitions of two different classes.
• an effective authentication system requires the intra-class variability to be as low as possible (i.e., two acquisition of the same class shall be as identical as possible), and the extra-class variability to be as high as possible (i.e., two acquisition of two different classes shall be as different as possible).
• the size of the effective region used during enrolment is maximized; smaller subregions are only used as a substitute when it is not possible to extract a single rectangular valid region with the prescribed minimal size from the normalized image. Determining the largest valid region, or set of subregions, which can be extracted from a given image is a task that unnecessarily requires processing power.
• Another drawback of this method is that the surface and shape of the region or set of subregions depend on each enrolment image. As the confidence level of the authentication process depends on the size and unicity of the templates, this method produces an unpredictable confidence level that depends on each image.
• the present invention proposes a method such that these drawbacks are avoided.
• a set of enrolled zones of said enrolled biometric data is selected, each selected enrolled zone having more than one pixel, said set comprising preferably at least 16 zones, possibly 200 zones or more;
• a matching counter is incremented depending on a match with a corresponding ongoing zone; -a match between the ongoing biometric data and the enrolled biometric data is determined when the value of the matching counter is higher than a predefined threshold.
• the method thus replaces the global matching process used in the prior art by a zone-by-zone comparison.
• the authentication is thus based on a two step process:
• each of a plurality of enrolled zone is compared with a corresponding ongoing zone. If there is a match, the matching counter is incremented
• the value of the matching counter is compared with a threshold. If this value is in a predetermined relation with this threshold (for example, higher than the threshold), it is determined that the enrolled biometric template matches the ongoing biometric template.
• An ongoing template thus matches an enrolled template when the number of matching zones is higher than the threshold.
• all zones have an identical surface and, possibly, an identical shape. This makes the comparison between zones a very repetitive, efficient and fast process.
• invalid ongoing and/or enrolled zones are ignored, i.e., not used during this matching process.
• the validity of one zone may be determined during the preprocessing of the image, and depends for example on the number of valid pixels in the zone, and/or on other information provided during preprocessing. Examples of invalid zones or pixels include zones covered by eyelashes, eyelids, reflections and so on.
• the validity of a zone or pixel depends on its brightness and/or contrast; a pixel may for example be considered invalid if its brightness is outside a predetermined range.
• zones are iteratively selected during the enrolment, until a predetermined number of valid zones have been found (for example 16, or 200 valid zones)
• each valid enrolled zone is compared with all the zones of the ongoing image with same shape and dimensions, and with positions which are not different from more than a given number greater than 0, preferably greater than 1.
• an enrolled zone is compared not only with the zone of the ongoing template that is at the exact same position, but also with a limited number of zones that are in its immediate or close neighborhood. This is useful for taking into account possible shifts and deformation of the iris between two acquisitions.
• an ongoing zone is determined to match an enrolled zone when the shapes and dimensions of the zones are equal, when the zones are at the same or at close neighbor positions, and when the zones are equal.
• the comparison between enrolled and ongoing zones is preferably based on projection of the zones computed using error-correction codes.
• An ongoing zone thus matches an enrolled zone if the projection (i.e., the error-corrected value) of the enrolled zone is equal to the projection of the ongoing zone, or preferably equal to the projection of the ongoing zone minus the later described difference vector. Since the zones have small surfaces, their variability is low, and a simple, fast error correction function is sufficient.
• the comparison between enrolled and ongoing zones is preferably based on a transformation of the zones computed by using a one way function of the zones, or of the projected zones.
• An ongoing zone thus matches an enrolled zone if the transformations of their projections are equal, i.e., if their pseudonyms computed with a one-way transformation of the error- corrected zone are equal.
• the authentication process is thus a very fast and effective process of comparing a series of pseudonyms of the enrolled and corresponding ongoing zones.
• the result of the matching process is a binary value and indicates whether an ongoing zone matches the corresponding enrolled zone or not. This makes the authentication very fast, and allows for easy use of one-way transformation.
• the result of the matching process can take more than two different values and indicates the quality of the match between the zones, i.e., depends on the distance between the enrolled zone and the ongoing zone (or between their projections).
• the value in the matching counter is a sum of the quality factors between each pair of matching zones. This allows for a more reliable authentication process, but requires more processing time, and limits the choice of suitable one-way functions.
• the zones selected from the enrolled template are selected at random, possibly independently of the image.
• different selected enrolled zones may overlap, thus allowing a fast selection of the enrolled zones.
• different zones are not overlapping, i.e., each pixel belongs to one selected zone at most, thus increasing the uniqueness of the set of zones.
• some heuristic is used for the selection of the enrolled zones.
• zones are selected so as to reduce the number of invalid zones; for example, less or no zones are selected in regions of the image which are more likely to be covered by eyelids, eyelashes or subject to specular reflections.
• the zones are selected so as to favor more discriminating regions of the iris.
• each selected enrolled biometric zone is stored along with the biometric data of the zone, for example along with the template zone or transformed zone.
• the invention also relates to a method for generating a biometric pseudonym based on a biometric template, comprising the following steps:
• each selected template zone having a shape, some dimensions and a position
• the present invention also relates to a method comprising the following steps:
• biometric raw data acquiring a plurality of biometric raw data, each one being from a different class and called an enrolled biometric raw data
• the invention further relates to a method for generating a biometric pseudonym based on a biometric template, comprising the following steps: selecting a set of valid zones of a biometric template, each selected template zone having a shape, some dimensions and a position, projecting each selected template zone on an error-correcting code, to produce a set of projected template zones, and applying on each projected template zone a mathematical one-way transformation, to produce a set of transformed zones to be used as the biometric pseudonym.
• -figure 1 is a flow diagram of the enrolment portion of the iris recognition method as is well-known in the art
• -figure 2 is a flow diagram of the identification portion of the iris recognition method as is well-known in the art
• -figure 4 is an example of the definition of a zone within the template domain
• -figure 5 is an example of a set of zones covering part of the valid features in a particular template
• FIG. 6 is a flow diagram of the enrolment portion of the iris recognition method according to the invention.
• -figure 7 is a flow diagram of the identification portion of the iris recognition method according to the invention. Detailed Description
• the pupil is detected and excluded. Zones covered by eyelids, eyelashes or subject to light reflection are also detected by known image processing techniques and are marked as invalid data.
• the ring-shaped iris is then stretched into a rectangle, by basically transforming the polar coordinates into Cartesian coordinates.
• a 2D wavelet transform is applied in order to extract the biometric features (for instance, a Gabor wavelet transform is suitable).
• the result of this transformation is a complex vector for each original pixel. Since illumination and/or contrast may vary a lot between different images of the same iris, only phase information of each vector is kept. Additionally, a validity bit is computed for each pixel. A pixel is considered valid if all pixels used to compute the pixel's vector are valid, i.e., do not come from a region excluded by iris localization process.
• An iris template can be viewed as a matrix of fixed dimensions. Each of its elements is a biometric feature extracted from an iris. As shown in figure 3, the ring-shaped iris region 100 is generally mapped to a rectangular template domain 110. The horizontal axis x in a template corresponds to the angle 8 in the iris, the vertical axis y to the radial axis r.
• FIG. 4 illustrates an example of the definition of a zone in the template domain 110.
• the zones are defined as rectangles of constant surface but of varying position and varying dimensions: zone A has its top left corner at (x, y) and is of height h and width w. Rectangles of constant dimensions h, w may also be used.
• zone B When the ring-shape iris is mapped into a rectangular matrix as described above, the zones can loop horizontally but not vertically as illustrated by zone B. Thanks to the use of zones, it is possible to process data that are exclusively or mostly valid, and a significant advantage will become more apparent below.
• a valid zone when referring to a valid zone, it means that the zone could contain a small amount of invalid pixels, but below a predetermined threshold, the case where the zone contains only valid data being of course included.
• Figure 5 shows a sample iris template 150 with typical invalid areas due to the occlusion of the upper eyelid 120 and lower eyelid 122, and to a specular reflection 124.
• Five zones 130 are drawn to illustrate how the valid features can be partially covered.
• the zones 130b and 130d overlaps, the zone 130e contains a small amount of invalid data, and the zone 130c contains a large amount of invalid data.
• the zone 130e containing a small amount of invalid data could be considered as a valid zone, whereas the zone 130c, containing a large amount of invalid data, could be considered as invalid.
• Figure 6 describes the enrolment algorithm according to the present invention.
• the steps of image acquisition 10 and template production 20 remain unchanged compared to algorithm described above. Invalid portions are detected as explained above. But instead of keeping the whole template, a fixed number N of zones are selected (and called selected enrolled template zones) at step 50, projected by using an error- correction code and transformed with a one-way function at step 52, thus producing a set of N transformed zones. Those transformed zones are stored at step 54 in an enrolment database.
• the template's validity rate is too low.
• Another template shall be enrolled again, based on a new acquisition of the user's iris, asking him to open his eyes wider or removing his glasses or contact lenses, if any.
• less restricted algorithm is used for selecting zones, for example an algorithm authorizing overlapping of zones, and/or zone of different dimensions, and/or zones with more invalid pixels.
• zones are chosen sequentially among all valid zones, from one corner of the entire template.
• zones are randomly selected among all the valid zones, excluding overlapping zones.
• zones are randomly selected among all the valid zones, including overlapping zones.
• a heuristic may also be used during the zone selection process, in order for example to avoid regions of the template which are more likely to include invalid pixels, or less discriminating regions.
• the optional transformation 52 aims at solving the intra-class variability issue and subsequently at solving privacy or security issues about biometric data. It consists at least in:
• This parameter data can be user-dependent, such as a password or a PIN (Personal Identification Number) code. It is either asked to the user during enrolment, or it can be allocated to the user. This parameter data can also be application-dependent.
• an application A can combine always the same data Daduring enrolment, and another application B can combine always the same data Db during enrolment, preventing application A and application B to share their biometric data once transformed using the mathematical one-way transformation.
• the parameter data can also be both user-dependent and application-dependent.
• Error-correcting code can be viewed as a kind of geometric projection.
• an error-correcting code is composed of a plurality of codewords (i.e., the words forming the code).
• the data to be corrected are projected on the codewords, the projection being normally performed by selecting the codeword whose distance from the data to correct is minimal.
• a Hamming distance is suitable for distance computation. It results in an error correction since a set of data that are close enough to a codeword will generally be projected onto the same codeword and the projected data (which is the codeword) is considered as the corrected data.
• a low-pass filter may also be used to reduce variability caused by high-frequency noise in the images.
• an error-correcting code is applied, during the enrolment process, to each selected template zone.
• Each selected template zone is projected on a codeword of the error-correcting code, called the projected template zone.
• the difference between the selected template zone and the projected template zone is computed and stored for each selected template zone, and will be used in the subsequent identification process described hereafter.
• the difference can be viewed as a difference vector representing the "errors" of the selected template zone.
• the selected template zones on which the error-correcting code is applied contains a number of invalid data under a given threshold.
• the threshold is determined so that the number of invalid data per template zone is within the error correcting ability of the error-correcting code.
• a one-way transformation is defined as a function that is easy to compute on every input, but hard to invert.
• “easy” and “hard” are to be understood in the sense of computational complexity.
• Such transformations can be cryptographic hash functions, such as for example SHA-256, which are easy to implement. Consequently, the set of transformed zones produced is non-sensitive since it cannot, in a practical sense, be reverted into biometric sensitive data.
• one-way functions may be used, including homomorphic functions that may be used if one wants to compute the distance between the enrolled and ongoing transformed zone, rather than just verifying their equality.
• the Reed-Muller RM(1,8) code may be used for error-correction. With this configuration, the code can correct up to 63 errors per 256-bit word.
• all the selected template zones are stored in an enrolment database at step 54, still referring to figure 6.
• all the selected template zones are stored in an enrolment database at step 54, still referring to figure 6.
• at least the following data are preferably stored:
• the transformed zone i.e. the projected template zone, possibly combined to a parameter data, and transformed by the one-way mathematical function
• the whole set of data for the same template is what we call a biometric pseudonym, and does reveal neither the actual identity of the individual hidden behind it, nor his/her biometric data.
• Adding a parameter data is a very interesting feature since, for a given class, it is possible to produce a plurality of biometric pseudonyms, by changing the parameter data.
• a biometric pseudonym can consequently be revoked (for instance when it is compromised), and replaced by another one, through a new enrolment with a new parameter data.
• Figure 7 states a new identification algorithm. The process is iterative, being performed successively with each zone of each enrolled class stored during the enrolment procedure described hereunder.
• all possible valid zones of the ongoing biometric template are determined at step 60 and tested during the identification. In another embodiment, only the ongoing zones that are at the same position or in the neighborhood of at least one of the enrolled zones of one class are determined.
• An enrolled class is selected at step 62 (which enrolled class is selected being unimportant since all enrolled classes will be iteratively processed until a match is found) and will be called the current enrolled class.
• a selected zone of the current enrolled class is selected at step 64 among the set of selected zones. Which zone is selected is unimportant since all zones in the set of selected zones of the current enrolled class will be iteratively processed). This zone will be called the current enrolled zone.
• step 68 all ongoing valid zones determined at step 60 are processed according to the following steps:
• each projected ongoing zone by using the same mathematical one-way transformation as used during enrolment, to produce a set of transformed ongoing zones.
• Subtracting the difference vector of the current enrolled zone of the current enrolled class to each ongoing valid zone ensures that an ongoing valid zone is projected on the same codeword as its closest enrolled template zone. If this operation is omitted, the ongoing valid zone would be projected directly on its closest codeword. It could be possible, in that case, that an ongoing valid zone and a very close enrolled zone are not projected onto the same codeword, which is not what is desired.
• the subtraction is performed only on the valid data, the invalid data being reported as is in the translated ongoing zone.
• an additional step can be advantageously implemented, consisting in combining a parameter data to each projected ongoing zone, to produce a set of combined ongoing zone.
• the parameter data can be also either user-dependent, application- dependent or both, and the combination algorithm shall be the same as for the enrolment procedure.
• the combined ongoing zone is then transformed by a one-way transformation, to produce a set of transformed ongoing zones. It has to be mentioned that combining a parameter data during the identification makes sense if and only if a parameter data was combined during the enrolment procedure. Moreover, when a parameter data was combined during the enrolment, the same parameter data shall be combined during identification procedure.
• Step 70 is a matching process and searches if one of the transformed ongoing zones matches the current enrolled zone.
• an ongoing zone is considered to match the current enrolled zone when both zones have the same shape, the same dimensions (for example same height h and same width w for a rectangle shape, same diameter for a disc), the same position and the same transformed data.
• an ongoing zone is considered to match the current enrolled zone when they have the same shape, the same dimensions, the same transformed data and a close position (the coordinate x of the ongoing zone and the coordinate x of the current enrolled zone are not different from more than a given positive number, and the coordinate y of the ongoing zone and the coordinate y of the current enrolled zone are not different from more than a given positive number).
• This feature considers for example that the user can slightly tilt his head during iris image acquisition, leading to slightly shift the mapping of the iris in the template between enrolment and identification.
• a per-class matching counter For each enrolled class, a per-class matching counter is implemented. Each time an ongoing zone matches one of the current zone of the current enrolled class, the counter corresponding to the current enrolled class is incremented at step 72. The increment value may be one, if only equality is tested, or depend on the distance between each ongoing zone and the corresponding enrolled zone.
• the steps 64, 68, 70 and 72 are repeated until all the zones of the current enrolled class are processed, or until the value of the matching counter reaches a threshold sufficient for determining a match with some probability.
• the steps 62, 64, 68, 70 and 72 are repeated until all the enrolled classes are processed (i.e., until all reference templates in the enrolment database have been tested), or until a satisfying match has been found.
• step 78 it is verified if the ongoing biometric data matches one enrolled biometric data based on the value of the matching counter. Alternatively, the closest matching class is found from the per-class matching counters whose value is the highest among all per-class matching counters.
• the identification privilege is granted if the per-class matching counter whose value is the highest is above a threshold, which can be application dependent just as with traditional biometric systems.
• the search for the closest matching class can be replaced by the search for the first per-class matching counter whose value is above a threshold; this avoids repeating the process for the remaining enrolled classes.
• Tests have been performed to empirically determine parameters that give good results. These parameters are given hereafter as non- limiting examples.
• a good trade-off between efficiency and practicability is obtained by selecting rectangular zones. Good results are obtained by using fixed-area rectangular zones, but whose dimensions can vary. A good trade-off is obtained with small zones having a 256-data area (256 pixels).
• the number of per-user enrolled zones was set to 300.
• a threshold for matching decision (which is the ratio between the closest user matching number and the number of zones of the closest user template) between 0.7 and 0.8 was used.
• This threshold may be adapted, depending on the application, to get a good trade-off between convenience and security. Considering that zones can slightly shift between enrolment and identification, zones where checked for matching for positions differing of up to 2 for x and y.
• the preceding description is based on iris biometrics. It will be evident to apply the present invention to other biometric techniques producing fixed-size templates or to other biometric techniques by transforming templates into fixed-sized templates. Moreover, the preceding description is based on an identification scenario involving one-to-many comparisons. It is of course applicable, with few modifications that can be easily performed by someone skilled in the art, to implement a verification scenario involving one-to-one comparison.
• the identification algorithm is described as sequential operations.
• One skilled in the art will encounter no particular difficulty to parallelize the operations in order to improve the processing time.

Landscapes

• Engineering & Computer Science (AREA)
• Theoretical Computer Science (AREA)
• General Health & Medical Sciences (AREA)
• Computer Vision & Pattern Recognition (AREA)
• Health & Medical Sciences (AREA)
• Physics & Mathematics (AREA)
• General Physics & Mathematics (AREA)
• Multimedia (AREA)
• Human Computer Interaction (AREA)
• Ophthalmology & Optometry (AREA)
• Artificial Intelligence (AREA)
• Computing Systems (AREA)
• Databases & Information Systems (AREA)
• Evolutionary Computation (AREA)
• Medical Informatics (AREA)
• Software Systems (AREA)
• Collating Specific Patterns (AREA)

Priority Applications (1)

Applications Claiming Priority (3)

Publications (1)

Family

ID=40756549

Family Applications (2)

Family Applications Before (1)

Country Status (2)

Families Citing this family (3)

Family Cites Families (4)

• 2008
  • 2008-11-13 EP EP08169061A patent/EP2187338A1/de not_active Withdrawn
• 2009
  • 2009-11-12 EP EP09749134A patent/EP2344979A1/de not_active Withdrawn
  • 2009-11-12 WO PCT/EP2009/065071 patent/WO2010055104A1/en not_active Ceased

Non-Patent Citations (3)

Also Published As

Similar Documents

Legal Events