INDEXING AND DATABASE SEARCH SYSTEM

• US 20070276853A1
• Filed: 03/02/2007
• Published: 11/29/2007
• Est. Priority Date: 01/26/2005
• Status: Active Grant

• Current Assignee: Gentex Corporation
• Original Assignee: Honeywell International Inc.
• Inventors: Hamza, Rida
• Granted Patent: US 7,761,453 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 40/197 Matching; Classification

Abstract

An indexing and database search system having a system to expedite a process of matching a subject to millions (more or less) of templates within a database. Such matching or retrieval may use a subject code as a query or probe and then find a similarity measure for the features of codes or templates in the database. A multi-stage clustering process may be used to compress codes and/or templates.

Claims

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.

2. The method of claim 1, wherein the second number is a least number of bits.

3. The method of claim 1, further comprising:

providing a barcode for matching; and

selecting a second number of bits of a barcode that corresponds to the second number of bits of a template.

4. The method of claim 3, wherein:

the barcode has a configuration which is same as the configuration of each template of the sub-database; and

a configuration is a certain number and arrangement of bits.

5. The method of claim 4, wherein 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 represented by 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 or greater than a number of templates in the second grouping.

9. The method of claim 8, wherein a progressive matching of a barcode to a template is performed by progressing from one grouping to another grouping.

10. The method of claim 9, wherein a number of templates used for matching is sometimes 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.

12. The method of claim 11, wherein bit summation on a barcode is used to compress the barcode.

13. The method of claim 11, wherein bit summation on a barcode is used to increase a speed of matching a barcode to a template in the database.

14. The method of claim 6, wherein phase information is used to cluster code bits.

15. The method of claim 6, wherein:

radial information is used to cluster code bits; and

the radial information to start 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;

the angular information is based on angular segments; and

sclera-iris angular segments are treated before other segments.

17. The method of claim 9, wherein progressing from one grouping to another grouping is of a plurality of groupings from clustering comprising:

phase clustering;

radial clustering;

angular clustering; and

bit clustering.

21. The method of claim 11, wherein bit summation on a horizontal or vertical axis on a barcode is used to increase a speed of matching a barcode to a template in the database.

18. A method for matching comprising:

providing a database; and

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 or greater than the third number; and

the fourth number is about equal to or greater than the fifth number.

19. The method of claim 18, further comprising:

matching a barcode to a template; and

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 equal to or 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;

the ninth number is less than the fifth number; and

a progression of templates and datasets herein may continue as appropriate.