Source: https://patents.google.com/patent/WO2007103834A1/en
Timestamp: 2019-10-24 05:26:22
Document Index: 427132810

Matched Legal Cases: ['Application No. 60', 'Application No. 11', 'Application No. 60', 'Application No. 11', 'Application No. 11', 'Application No. 11', 'Application No. 11', 'Application No. 11', 'Application No. 11', 'Application No. 10', 'Application No. 60', 'Application No. 11', 'Application No. 60', 'Application No. 11', 'Application No. 11', 'Application No. 11', 'Application No. 11', 'Application No. 11', 'Application No. 11', 'arts 32']

WO2007103834A1 - Indexing and database search system - Google Patents
WO2007103834A1
WO2007103834A1 PCT/US2007/063243 US2007063243W WO2007103834A1 WO 2007103834 A1 WO2007103834 A1 WO 2007103834A1 US 2007063243 W US2007063243 W US 2007063243W WO 2007103834 A1 WO2007103834 A1 WO 2007103834A1
PCT/US2007/063243
2006-03-03 Priority to US60/778,770 priority
2006-03-10 Priority to US11/372,854 priority
2007-02-07 Priority to US11/672,108 priority
2007-02-15 Priority to US11/675,424 priority
2007-03-02 Application filed by Honeywell International, Inc. filed Critical Honeywell International, Inc.
2007-03-02 Priority to US11/681,751 priority
2007-03-02 Priority to US11/681,614 priority
2007-03-02 Priority to US11/681,662 priority
2007-09-13 Publication of WO2007103834A1 publication Critical patent/WO2007103834A1/en
210000000554 Iris Anatomy 0 description 61
This application claims the benefit of U.S. Provisional Application No. 60 /778 ,770 , filed March 3, 2006.
This application is a continuation-in-part of U.S. Patent Application No. 11/275,703, filed January 25, 2006, which claims the benefit of U.S. Provisional Application No. 60/647,270, filed January 26, 2005. This application is a continuation-in-part of U.S. Patent Application No. 11/043,366, filed January 26, 2005.
This application is a continuation-in-part of U.S. Patent Application No. 11/372,854, filed March 10, 2006; This application is a continuation-in-part of U.S. Patent Application No. 11/672,108, filed February 7, 2007.
This application is a continuation-in-part of U.S. Patent Application No. 11/675,424, filed February 15, 2007.
This application is a continuation-in-part of U.S. Patent Application No. 11/681,614, filed March 2, 2007. This application is a continuation-in-part of U.S. Patent Application No. 11/681,662, filed March 2, 2007. The government may have rights in the present invention .
Related applications may include U.S. Patent Application No. 10/979,129, filed November 3, 2004, which
Iof20 is a continuation-in-part of U.S. Patent Application 10/655,124, filed September 5, 2003; and U.S. Patent Application 11/382,373, filed May 9, 2006, which are hereby incorporated by reference. U.S. Provisional Application No. 60/778,770, filed March 3, 2006, is hereby incorporated by reference.
U.S. Patent Application No. 11/275,703, filed January 25, 2006, is hereby incorporated by reference.
U.S. Provisional Application No. 60/647,270, filed January 26, 2005, is hereby incorporated by reference.
U.S. Patent Application No. 11/043,366, filed January 26, 2005, is hereby incorporated by reference.
U.S. Patent Application No. 11/372,854, filed March 10, 2006, is hereby incorporated by reference. U.S. Patent Application No. 11/672,108, filed
February 7, 2007, is hereby incorporated by reference.
U.S. Patent Application No. 11/675,424, filed February 15, 2007 is hereby incorporated by reference.
U.S. Patent Application No. 11/681,614, filed March 2, 2007 is hereby incorporated by reference.
U.S. Patent Application No. 11/681,662, filed March 2, 2007 is hereby incorporated by reference.
Brief Description of the Drawing Figure Ia is a diagram of an overall iris recognition system with database indexing.
Figure Ib illustrates the progressive matching process; Figure 2 shows an overall four stage grouping approach of barcode bits to compute a more compact feature vector per each class;
Figure 3 is a diagram showing phase based clustering;
Figure 4 is a diagram showing angular based clustering;
Figure 5 is a diagram showing radial clustering; and Figure 6 is a diagram showing bit formatting.
The present system may relate to biometrics, iris recognition systems, image quality metrics, authentication, access control, monitoring, database retrieval, database query, fast database indexing, fast progressive identification, and security and surveillance systems .
The overall eye detection system is shown in Figure Ia. It shows a camera 61 that may provide an image with a face in it to an eye finder 62 as noted herein. The eyefinder 62 may provide an image of one or two eyes that go to a preprocessing image quality assessment block 60. Output of block 60 may go to an iris segmentation block 63. A polar segmentation (POSE) system in block 63 may be used to perform the segmentation. POSE may be based on the assumption that image (e.g., 320 x 240 pixels) has a visible pupil where iris can be partially visible. There may be pupil segmentation at the inner border between the iris and pupil and segmentation at the outer border between the iris and the sclera and iris and eyelids. An output having a segmented image may go to a block 64 for mapping/normalization and feature extraction. An output from block 64 may go to an encoding block 65 which may provide an output, such as a barcode of the images put in terms of ones and zeros. An output of the encoding block 65 may go to an indexing block 68 through the choice of enrolling or matching of diamond or block 66 to group and cluster the bits for either enrolling or matching process. The choice of enrollment made at block 66, i.e., path 71 as input to indexing block 68 of the barcode may provide a basis for storage in block 70 of the eye information based upon sub-blocks of datasets which may be used for enrolling and indexing, at block 70. The block of bit indexing 68 may be configured based upon the clustering choice of the output of block 67 feeding into block 68. The indexing block of the query barcode once triggered by the matching option, i.e., through path 72 as input from block 66 will output the probe barcode to progressive matching of block 69. The progressive matching of block 69 may match the subclasses of the barcode bits using the configuration of the database grouping. The clustering scheme, once selected at block 67 as input to block 68, should be kept the same for both enrollment and matching for consistency at inputs 74 and 75, respectively.
According to related practices, an information content based retrieval approach while clustering analysis may be conducted on bit codes and not on raw iris images. Further retrieval of an iris template from the database when a query iris is given by processing the raw iris image may be a time consuming task. In this invention, one may present a rapid approach to analyze progressively the bit codes to match against a very large datasets. Furthermore, the iris code may be additionally compressed to fewer bits than previously done before extracting the feature vector for indexing. One may selectively use discriminating information in the iris code as a query to compute the feature vectors for the indexing and querying. This may be regarded as a multilevel of clustering to yield a progressive matching using at least three methods of grouping of bits into subclasses using phase, radial, and angular information and then conducting the matching on only limited subclasses of bits and or using a compact bit format to compute a more compact feature vectors of the barcodes.
The present invention may be an approach and system to classify a given query iris into one of the pre- defined classes. Irises may be retrieved from a large collection of databases using partial information of the iris barcode as a probe and then find the similarity measure for all the features of the iris codes in the database. The information may then be augmented progressively to limited numbers of potential probes of barcode templates in the database. Partial features may be extracted using phase, angular or radial clustering. The resulting bits may be used then for matching or additional cumulative bit analysis on a very compressed version of the resulting iris code bits can be deployed instead. The terms probe and query may be used interchangeably herein.
The bit clustering may involve grouping or classifying of a barcode bits into subsets based upon the phase information, angular location or radial range. This classification of bits into subsets (i.e. subclasses) allows a progressive query and matching starting from fewer bits against all probes in the database (i.e., starting with a single or few classes of bits) and iteratively may include additional classes of bits that would limit the matching process to fewer template queries. When grouping the bits using present clustering methods, it is expected that the number of probes used for matching is inversely dependent on the number of bits being deployed in the matching process. At each step of the progressive matching, only potential matches are kept for next steps of analysis. Hence, the more one progresses in the query by deploying additional bits, the more one eliminates non-potential matchers, leading to fewer templates to match against in next rounds. In other words, the more bits deployed, the less number of templates being used to match against. This may be the main benefit of the present indexing method that is to allow matching the barcode probe against only few of the template queries.
In the following, one may present an example to illustrate the progressive matching that reduces the required computational burden of matching large databases.
Assume that one has 10,000 templates of enrolled barcodes as queries within the database. Each template may have 240 bytes of information in bits. If one conducts a one-to-many matching process, this may require 2.4 mega bytes of bit matches. In the present invention, each barcode may be classified based upon the phase, angular, and radial information. One may assume to have a 2 bit representation of each pixel. Thus, one may cluster the bits of the barcode into two subgroups using the phase clustering. One may cluster further the bits into 5 classes based upon the angular segments, and in addition may cluster the bits into 3 groups of radial ranges. This will result into 3x5x2 = 30 subclasses of the databases. And each barcode may be subdivided into 30 subsets of bits; each of subset has only 8 bytes.
Thus, the configuration of the database in Figure Ib will result into 30 different datasets stacked within the database as shown at the right hand side of the database grouping. Each dataset may have a class of the bits of all the 10,000 barcode probes. Thus, at the first matching process, one may match only an 8 byte subset (block 82 in Figure Ib) of the query barcode against only the dataset 81 of Figure Ib. The dataset 81 represents only partial information of 8 bytes of each of the 10,000 probes. The matching process of 81 may result into 1000 good potential matches out of the 10,000 probes. At the second step of the progressive matching, one may use only these 100 good matches for analysis. One may match another subset of the barcode of size 8 bytes (block 84 in Figure Ib) against only the corresponding database 83 and limit the matching to only those 1000 probes. One may note that each dataset like 83 has representation of all 10,000 probes. This may result, for example, into 100 good matches. In step 3, one may select a third 8 byte class of the barcode to match against the resulting 100 probes of dataset 85. One may obtain, for example, 10 good matches out of the 100 probes. One might choose at a certain stage to quit the progressive match given that the numbers of potential probes has been limited to only few probes. One may thus process the rest of the barcode subsections against these 10 probes. The overall required matching operations for this example are (10,000x8 + 1000x8 + 100x8 + 10x240) bytes which is about 0.091 Mega bytes of matching operations, compared to raw matching of 2.4 Meg bytes of operations (that is only 3.8% of computation required in the progressive matching than the regular matching.) The choice of how one executes bits' grouping into separate subclasses is very crucial to the success of this indexing mechanism. Three methods of bit clustering (phase, angular, and radial) may be used to group the bits into different subclasses. At each clustering stage, one might group bits based upon the types of information and how it pertains to the iris texture representation. For instance, during the progressive matching, one may have to start with the key discriminant bit subclasses at early stage using classes with bits presenting the most significant iris texture information, and end at the least significant classes for last rounds.
The most significant classes are those bits associated with key features of the iris textures. In particular, at the radial axis, one has affirmed that most information of the iris textures is likely to be at the vicinity of the inner border of the iris. At the angular axis, one may realize that the bits representing the pixels of the sclera/iris segment are more reliable than the bits representing the eyelid/iris segments due to high noise-to-signal ratio at the eyelid angular ranges .
Organization of feature data to group the bits of an iris code may be completed in a hierarchical form to compare one subset of bits at a time starting at the extracted feature elements that are closest to the inner iris boundary (row cumulative analysis) . If the cumulative feature vector is conducted on the columns, the features that correspond to the middle sclera may be treated first. A simple tree classifier using hamming distance or any other information measure may be utilized as a measure to find similarity for all the features of the irises in the database. The feature vector may be computed using a four stage clustering process to compress the iris barcode to tens of feature elements (i.e., fewer bits of information) used in the class bits. The present system and approach may provide a fast search and indexing of irises based on four stage selective clustering procedure as shown in Figure 2. The four stages may include phase clustering, radial clustering, angular clustering and bit clustering. The approach may extract the most valuable discriminant information in the iris at each stage based upon different criteria and then cluster the dataset based upon the extracted significant features of the compressed iris bits. The matching may be executed on a subset of barcode bits or a compact feature vector of 12 bit elements representing the subset of compressed bits. One may deploy an unsupervised tree classifier using a Euclidian distance or binning approach as a measure to find similarity between classes and iris query within sub datasets to break down the datasets into smaller sets. The present multiple-stage clustering approach and system may begin with a phase clustering stage 11 where the initial size of a code 21 and mask 22 may be 2xNrxNβ. The phase clustering 11 may reduce the size of code 21 and mask 22 down to a size of NrxNø, as shown by code 23 and mask 24. A corrupt bits index may be indicated by rik. The stage, radial clustering 12, may reduce code 23 and mask 24 to a size of code 25 and mask 26, which is rikxNø. Code 25 may be sclera based. An angular clustering stage 13 may reduce code 25 and mask 26 down to a size of rikxNβxΔθs/π, as shown by code 27 and mask 28. In turn, a bit clustering stage 14 may reduce the code 27 and mask 28 size down to a code 29 and mask 30 having a size equal
\2nk (if summation of bits is conducted on the horizontal axis) or l2Nβ xAΘJπ if summation is done on the vertical axis .
Figure 3 is a diagram of phased based clustering 12. In order to encode iris pattern data, decomposition of an iris feature vector 31 having the size 2NrxNe may be accomplished by using a quadratic pair of filters 34 and 35, with real part specified by an even symmetric filter 34 and the imaginary part specified by an odd symmetric filter 35. Both outputs of the filters may be uncorrelated and be treated separately. Thus, a decomposition may occur into parts 32 and 33 each having the size NrxNe.
Figure 4 is a diagram of angular based clustering. The encoding process may produce a bitwise template containing a number of bits of information covering both the regions bordering the sclera and other adjacent iris segments to top and bottom eyelids. A corresponding noise mask which corresponds to corrupt areas within the iris pattern may be constructed to exclude these noisy bits. Because of the nature of eyelid and eyelash obscurations, most of the corrupt regions may be at the vicinity of the eyelids apart from the sclera central boundaries. Thus, the bits corresponding to the central sclera boundaries may present a more accurate presentation of the actual iris patterns. This stage shows a decomposition of the iris code based upon the boundary limits of the central sclera as shown in Figure 4. The sclera portions 41 and 42 of the iris are indicated by boundaries 43 and 44 having sector angles
Δθτ anc^ A>θs ' respectively . The code 45 may have a dimension 2NrxNβ. It may be noted that , Δ& = [θ- → θ+] + φhl
Δ& = Δθs + π, θ+ = [π/4 → 3π/8] , and θ. = θ+, where ψk is the expected head orientation. The decomposition of the iris code 45 based on the boundary 43 and 44 limits may lead to a sclera based code 46 and a lid based code 47. The lid portions may have masking 48 and 49 for the sclera based code 46. The sclera portions may have masking 51 and 52 for the lid based code 47. The dimension of the sclera based code may be
2NrxNβκAθs/π. The dimension of the lid based code may be
2NrxNθx(π -Aθs) /π. Figure 5 is a diagram of radial based clustering. Many of the iris patterns may reside at the inner boundaries of the iris as shown in the iris map 55 of the Figure, with the exception of a few samples where the iris pattern is spread consistently over the entire iris region. Even with these few exceptions, it is expected that the outer boundary of the iris will include most of the corrupt iris pixels due to obscuration of eyelids and eyelashes which eventually will be masked out of the analysis. A decomposition of the iris code 53, having a size of NrxNβ, may be effected based upon a radial segment that has the least number of corrupt bits. To control the number of corrupt bits, one may replace the original mask (of size NrxNe bits) with a partial of the range, example the first single byte (8 bits) only to indicate the index of the least radius nr which has the minimum number of corrupt bits (sum of x bits in horizontal direction that does not exceed a predefined fraction (e.g., 5 percent) of the angular resolution) . The corrupt bits index may be indicated by rik. Mask 56 is revealed on map 55. With the masked bits removed, one may have a code 54 having a size of 2nrxNø. The number of rows used in the comparison may be defined based on the minimum value of the index of corrupt bits in both the template and the code to be compared. One may note that nr = min {nu, nτemPiate) •
Figure 6 is a diagram of a compact bit format. An iris code 57 may be noted with a size 2NrxNg. The bit-to- bit comparison of bar codes may be replaced by a comparison of two 12 bit vectors that represent the iris map. The feature vector F may be computed by summing the row bit values. The first column left of code 57, with heading ΔF , may be a 12 bit presentation of "x" bits (mask bits) = error in elements. The column, adjacent to the first column, may be a 12 bit presentation of "1" bits = feature vector elements. One may track the number of corrupt bits by the 12 bit vector
ΔF to account for the error margin during a comparison of feature vectors. One may chose to sum over the angular values so that the comparison will not be affected by any head orientation. A similar approach may be applied to sum through columns rather than rows or both simultaneously. One may have F=F +AF . F1 the resultant 2ANΘ bit feature vector 58, is shown in the Figure. The present approach may expedite the process by at least the number of shifts times over the related art techniques given that summation over the angular range does not require shifting for actual matching. Summing over the radial may still dictate the use of shifting of these feature vectors to account for head orientation changes. In the present specification, some of the matter may be of a hypothetical or prophetic nature although stated in another manner or tense.
1. A method of indexing comprising: providing a database of templates; grouping the database into a plurality of sub-databases; and wherein : each template in the database has a first number of bits; each sub-database of the plurality of sub- databases represents virtually all templates in the database; each template in a sub-database has a second number of bits; and the first number is greater than the second number .
3. The method of claim 1, further comprising: providing a barcode; and selecting a second number of bits of a barcode that corresponds to the second number of bits of a template.
5. The method of claim 4, the grouping of the database into a plurality of sub-databases is one of a plurality of kinds of groupings.
6. The method of claim 5, wherein: the plurality of groupings is progressive relative to the number of the sub- databases in the plurality of sub- databases and a bit-size of each template in the sub-database; and the bit-size is a number of bits representing a template.
7. The method of claim 6, wherein a first grouping of a database having a smaller number of sub-databases has templates with a larger bit-size than a second grouping of the database.
8. The method of claim 7, wherein a number of templates in the first grouping is the same as a number of templates in the second grouping.
10. The method of claim 9, wherein a number of templates used for matching is reduced when progressing from one grouping to another grouping.
11. The method of claim 10, wherein a matching of a barcode is reduced to a least number of templates which is less than the number of templates in a sub-database.
13. The method of claim 11, wherein bit summation on a barcode is used to increasing a speed of matching a barcode to a template in the database.
15. The method of claim 6, wherein: radial information is used to cluster code bits; and the radial information is based on information close to an inner border of an iris .
16. The method of claim 6, wherein: angular information is used to cluster code bits; and the angular information is based on angular segments of an iris.
18. A method for matching comprising: providing a database; grouping the database into a first number of datasets; and wherein : the database comprises a second number of templates; each dataset comprises a third number of templates; each template in the database has a fourth number of bits; each template in a dataset has a fifth number of bits; the second number is about equal to the third number; and the fourth number is greater than the fifth number .
19. The method of claim 18, further comprising: matching a barcode to a template; wherein : a template of a dataset has a first configuration; the barcode has a first configuration; the matching of the barcode to templates of the dataset results in a sixth number of templates which are a possible match for the barcode; and the sixth number is significantly less than the second number.
20. A method for searching comprising: providing a database; grouping the database into a first number of datasets; grouping a dataset into a second number of sub-datasets; and matching a barcode to a template; and wherein : the database comprises a third number of templates; each dataset comprises a fourth number of templates; each sub-dataset has a fifth number of templates; each template in the database has a sixth number of bits; each template in a dataset has a seventh number of bits; each template in a sub-dataset has an eighth number of bits; the third number is about equal to the fourth number; the third number is about equal to the fifth number; the sixth number is greater than the seventh number; the seventh number is greater than the eighth number; a template of a sub-dataset has a first configuration; the barcode has a first configuration; the matching of the barcode to templates of the sub-dataset results in a ninth number of templates which are a possible match for the barcode; and the ninth number is significantly less than the fifth number.
PCT/US2007/063243 2005-01-26 2007-03-02 Indexing and database search system WO2007103834A1 (en)
US60/778,770 2006-03-03
US11/372,854 2006-03-10
US11/672,108 2007-02-07
US11/675,424 2007-02-15
US11/681,751 2007-03-02
US11/681,614 2007-03-02
US11/681,662 2007-03-02
WO2007103834A1 true WO2007103834A1 (en) 2007-09-13
PCT/US2007/063243 WO2007103834A1 (en) 2005-01-26 2007-03-02 Indexing and database search system
DE602007007062D1 (en) 2006-03-03 2010-07-22 Honeywell Int Inc Iris recognition system with image quality metrics
WO2007004521A1 (en) * 2005-06-30 2007-01-11 Olympus Corporation Marker specification device and marker specification method
JP6156126B2 (en) * 2013-12-19 2017-07-05 富士通株式会社 Search method, search program, and search device
WO2001040982A2 (en) * 1999-12-01 2001-06-07 Iridian Technologies System and method of fast biometric database searching using digital certificates
DE69717826D1 (en) 1996-06-06 2003-01-23 British Telecomm Public Ltd Co Identification of persons
NZ509367A (en) 1998-07-09 2003-08-29 Univ Colorado State Res Found Retinal vasculature image acquistion apparatus and method
KR100319608B1 (en) * 1999-03-09 2002-01-05 김영환 A stacked semiconductor package and the fabricating method thereof
DE50012364D1 (en) * 2000-05-16 2006-05-04 Swisscom Mobile Ag A method and terminal for the input of instructions
JP2003535559A (en) 2000-06-02 2003-11-25 キネティック サイエンシーズ インコーポレイテッド Biometric encryption method of e-mail
AT323919T (en) 2000-07-14 2006-05-15 Voice Trust Ag A method and system for authorizing a commercial transaction
AU2040202A (en) * 2000-11-21 2002-06-03 John Zachariassen System and method for transmitting goods, remuneration, and information
DE60135879D1 (en) 2001-04-27 2008-10-30 Bausch & Lomb Iris pattern recognition and alignment
ES2373376T3 (en) * 2001-08-21 2012-02-02 Diebold, Incorporated System and procedure for verification of deposits in an automatic cashier.
WO2003063102A2 (en) 2001-11-06 2003-07-31 Radian Inc. Physiomagnetometric inspection and surveillance system and method
AU2002349209A1 (en) 2001-11-26 2003-06-10 Ball, Ronald, H. Portable messaging device adapted to perform financial transactions
EP1335329A3 (en) 2002-02-05 2004-09-22 Matsushita Electric Industrial Co., Ltd. Personal authentication method, personal authentication apparatus and image capturing device
WO2003067389A2 (en) 2002-02-07 2003-08-14 Eyeticket Corporation System and method for automated biometric data collection
WO2004025565A1 (en) * 2002-09-13 2004-03-25 Matsushita Electric Industrial Co., Ltd. Iris encoding method, individual authentication method, iris code registration device, iris authentication device, and iris authentication program
JP2007504562A (en) * 2003-09-04 2007-03-01 サーノフ コーポレーション Method and apparatus for performing iris authentication from one image
CN100498837C (en) 2004-05-10 2009-06-10 松下电器产业株式会社 Iris registration method, iris registration apparatus
WO2006132686A2 (en) 2005-06-03 2006-12-14 Sarnoff Corporation Method and apparatus for designing iris biometric systems for use in minimally
2007-03-02 WO PCT/US2007/063243 patent/WO2007103834A1/en active Application Filing
2007-03-02 US US11/681,751 patent/US7761453B2/en active Active
2007-03-02 KR KR1020087024181A patent/KR20080108114A/en active IP Right Grant
2007-03-02 EP EP07757853A patent/EP1991947A1/en active Pending
RATHA N K ET AL: "A REAL-TIME MATCHING SYSTEM FOR LARGE FINGERPRINT DATABASES", IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, IEEE SERVICE CENTER, LOS ALAMITOS, CA, US, vol. 18, no. 8, August 1996 (1996-08-01), pages 799 - 812, XP000632861, ISSN: 0162-8828 *
KR20080108114A (en) 2008-12-11
EP1991947A1 (en) 2008-11-19
US20070276853A1 (en) 2007-11-29
US7761453B2 (en) 2010-07-20
Lin et al. 2010 Multiple kernel learning for dimensionality reduction
Chen et al. 2014 Marginalized denoising auto-encoders for nonlinear representations
US7817826B2 (en) 2010-10-19 Apparatus and method for partial component facial recognition
Riesen et al. 2009 Graph classification based on vector space embedding
Liu et al. 2007 Efficient fingerprint search based on database clustering
EP1393196A4 (en) 2007-02-28 Kernels and methods for selecting kernels for use in learning machines
Chen et al. 2008 Efficient recognition of highly similar 3D objects in range images
Ref document number: 2007757853
Ref document number: 7624/DELNP/2008
Ref document number: 1020087024181