Image indexing search system and method

• US 7,184,577 B2
• Filed: 11/21/2003
• Issued: 02/27/2007
• Est. Priority Date: 03/14/2003
• Status: Active Grant

• Current Assignee: InteliTrac, Inc.
• Original Assignee: InteliTrac, Inc.
• Inventors: Wei, Yinong, Chen, Tianlong, Rui, Yi, Wang, Yingbin
• Primary Examiner(s): MARIAM, DANIEL G
• Application Number:
  US10/718,738
• Publication Number:
  US 20040179720A1
• Time in Patent Office: 1,194 Days
• Field of Search: 382/118, 382/209, 382/218, 382/225, 382/226, 382/228, 382/305, 707/3, 707/7
• US Class Current: 382/118
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06V 40/16 Human faces, e.g. facial parts, sketches or expressions
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

An architecture and method useful for fast one-to-many image matching and image indexing. A plurality of images in a database are digitized into a plurality of descriptors. The descriptors are separated into a plurality of index groups. Index values for the images in the database are then calculated for the various index groups. An index value, for example, could be calculated as the average of the descriptors in a particular group. A source groups of images having particular index values over a particular threshold value are identified. When matching a target image to images in the database, the index values are calculated for the target image and compared to the threshold value. Source groups of images having similar index values over the threshold are then identified for further matching to the target image.

Claims

1. A method for indexing a plurality of images in a database, each image in said database having within it an object of the same type, comprising the steps of:

digitizing each of said plurality of images in said database into an array of descriptors;

separating said descriptors into a plurality of index groups;

calculating for at least one of said plurality of images in said database an index value corresponding to one of said index groups;

providing a first index level, a second index level, and a pre-set number;

wherein said first index level has a first index value, said second index level has a second index value, said first index level having a first list of buckets, said second index level having a second list of buckets, and said buckets each hay inn a counter;

if said counter of a bucket in said first index level is lamer than said pre-set number, then said bucket in said first index level has a second index level, and said counter is the sum of counters of said buckets in said second index level;

if said counter of said bucket in said first index level is less than or equal to said pre-set number, then said bucket in said first index level has a list of image templates, and the number of said image templates is said counter;

wherein each said image template comprises a plurality of said descriptors.

2. A method for indexing a plurality of images in a database according to claim 1 wherein said index value is a function of at least two of said descriptors.

3. A method for indexing a plurality of images in a database according to claim 2 wherein said function comprises averaging at least two of said descriptors.

4. A method for indexing a plurality of images in a database according to claim 2 wherein said function comprises averaging four of said descriptors.

5. A method in accordance with claim 1, wherein said object type comprises a human face.

6. A method according to claim 1, wherein said second index level comprises a hash table said index value as a hash value.

7. A method for image indexing comprising:

digitizing a target image having an object within it into an array of descriptors;

digitizing at least one source image in a database into an array of descriptors, each said source imaging having an object within it and said object in said target image and said object in said at least one source image being of same type;

wherein said array of descriptors from said target image and said array of descriptors from said at least one source image comprise the same type and the same number of descriptors; and

separating said descriptors into index groups, wherein said index groups each have an index values;

providing a first index level, a second index level, and a pre-set number;

wherein said first index level has a first index value, said second index level has a second index value, said first index level having a first list of buckets, said second index level having a second list of buckets, and said buckets each having a counter;

if said counter of a bucket in said first index level is larger than said pre-set number, then said bucket in said first index level has a second index level, and said counter is the sum of counters of said buckets in said second index lever;

if said counter of said bucket in said first index level is less than or equal to said pre-set number, then said bucket in said first index level has a list of image templates, and the number of said image templates is said counter;

wherein each said image template comprises a plurality of said descriptors.

8. A method in accordance with claim 7, wherein said object type comprises a human face.

9. A method according to claim 7, wherein said index value of each index group is the average value of said descriptors in said index group.

10. A method according to claim 7, wherein each said index group comprises a consecutive number Y of said descriptors.

11. A method according to claim 10, further comprising the step of selecting Y.

12. A method according to claim 7, wherein said index group comprises every other Z descriptors, wherein Z is an integer.

13. A method according to claim 12, further comprising the step of selecting Z.

14. A method of image indexing for an image database having a plurality of image templates generated from a plurality of source images, comprising:

providing hierarchical multiple index levels, and a pre-set number;

wherein each said index level has a list of buckets, said buckets each having an index value and each having a counter;

if a counter of a bucket in a first index level in said multiple index levels is larger than said pre-set number, then said bucket in said first index level has a second index level, and said counter of said bucket in said first index level is the sum of counters of said buckets in said second index level;

if said counter of said bucket in said first index level in said multiple index levels is less than or equal to said pre-set number, then said bucket in said first index level has a portion of said plurality of image templates, and the number of said image templates is the said counter of said bucket;

said portion of said plurality of image templates each having an index value matching to said index value of said bucket.

15. A method according to claim 14, wherein each of said multiple index levels comprises a hash table using said index value as a hash value.

16. A method of finding top matches from an image database having source images, given a target image, and using image indexing architecture with a one-by-one matching algorithm, and a pre-set percentage threshold for similarity matching for said matching algorithm, said method comprising:

setting a pre-set number as an upper limit for the number of final one-to-one matching groups of templates for final fine-matching using said one-by-one matching algorithm;

constructing said image indexing architecture, said constructing step comprising;

providing hierarchical multiple index levels, and a pre-set number;

wherein each said index level has a list of buckets, said buckets each having an index value and each having a counter;

if a counter of a bucket in a first index level in said multiple index levels is larger than said pre-set number, then said bucket in said first index level has a second index level, and said counter of said bucket in said first index level is the sum of counters of said buckets in said second index level;

if said counter of said bucket in said first index level in said multiple index levels is less than or equal to said pre-set number, then said bucket in said first index level has a portion of said plurality of image templates, and the number of said image templates is the said counter of said bucket;

said portion of said plurality of image templates each having an index value matching to said index value of said bucket;

digitizing said target image into a target image template;

calculating a group of index values of said target image template;

using said group of index values of said target image template to create a final one-by-one matching group of image templates from said image indexing architecture for final fine-matching, comprising the steps of;

using a first index value from said group of index values of said target image template to index into one index level of said hierarchical multiple index levels in said image index architecture;

using said first index of said target image template to index into said first index level of said image indexing architecture;

if a counter of a bucket of a first index level is larger than or equal to said pre-set number, then using a next index of said target image template to index into a next index level of said image indexing architecture until a bucket having a counter less than said pre-set value is found or a bucket having a last index level is reached;

if a last index level is reached, image templates contained under said bucket having said last index level from said final one-by-one matching group; and

if the counter of a bucket of an index level is less than said pre-set number, then picking said bucket and neighboring buckets in said first index level until the sum of the counters of said neighboring buckets is larger than or equal to said pre-set number; and

all portions of image templates contained under said neighboring buckets from said final one-by-one matching group;

thereafter applying said one-by-one matching algorithm to said target image and each of said source images templates of said final one-by-one matching group;

wherein source image templates having the highest matching scores from said final one-by-one matching group against the target image template with said matching scores over said pre-set percentage threshold become said top matches.

17. A method according to claim 16, wherein said matching algorithm provides a list of matches with higher than said pre-set percentage threshold, or gives no match if there are no matches with higher than said pre-set percentage threshold.