Content-based information retrieval

• US 8,346,800 B2
• Filed: 04/02/2009
• Issued: 01/01/2013
• Est. Priority Date: 04/02/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Szummer, Martin, Fitzgibbon, Andrew, Torresani, Lorenzo
• Primary Examiner(s): Cao, Phuong Thao
• Application Number:
  US12/417,511
• Publication Number:
  US 20100257202A1
• Time in Patent Office: 1,370 Days
• Field of Search: 707/999.005, 707/772, 707/771, 707/E17.016, 707/E17.02, 707/999.003
• US Class Current: 707/772
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 18/2148 characterised by the process organisation or structure, e.g. boosting cascade

Abstract

Content-based information retrieval is described. In an example, a query item such as an image, document, email or other item is presented and items with similar content are retrieved from a database of items. In an example, each time a query is presented, a classifier is formed based on that query and using a training set of items. For example, the classifier is formed in real-time and is formed in such a way that a limit on the proportion of the items in the database that will be retrieved is set. In an embodiment, the query item is analyzed to identify tokens in that item and subsets of those tokens are selected to form the classifier. For example, the subsets of tokens are combined using Boolean operators in a manner which is efficient for searching on particular types of database.

Claims

1. A computer-implemented method of similar item retrieval comprising:

receiving a query item;

analyzing content of the query item, the analyzing comprising identifying tokens in that query item using a library of tokens, wherein each token comprises a symbol representing a cluster of features;

dynamically forming a classifier, using a processor, at query time on the basis of the query item'"'"'s content and a training set of items, wherein the training set comprises a plurality of pairs of items and a plurality of background items such that for each pair, the items in that pair are specified as similar to one another, the forming the classifier comprising choosing a subset of the identified tokens such that, on the training set as many as possible of the similar pairs have the chosen subset of tokens while the number of background items containing the subset of tokens is below a specified bound; and

using the classifier to select a plurality of items from a database of items.

2. The method as claimed in claim 1, wherein the classifier is formed from groups of tokens and wherein those groups of tokens are themselves combined using OR operators.

3. The method as claimed in claim 1 wherein the classifier is formed from at least one phrase, each phrase being formed from any of:

a single token, a histogram count condition on a single token, a Boolean function of tokens, a Boolean function of count conditions on tokens, a Boolean-valued function of an ordered set of tokens.

4. The method as claimed in claim 1 wherein the step of forming the classifier comprises using an automated optimizer.

5. The method as claimed in claim 1 which further comprises providing the items selected from the database to a ranking system to obtain a ranked list of items.

6. The method as claimed in claim 1 which further comprises generating a pool of candidate subsets of tokens from the training set of items using a learning engine.

7. The method as claimed in claim 1, wherein the items are images and wherein the tokens are visual words.

8. The method as claimed in claim 1, wherein the items are images and wherein similar items comprise images of objects of a same object class.

9. The method as claimed in claim 8, wherein the query item comprises objects of classes absent from the training set.

10. The method as claimed in claim 1, wherein the training set comprises some items which are not specified as similar or dissimilar to each other.

11. A content-based image search apparatus comprising:

an input arranged to receive a query image;

a content analysis engine arranged to identify tokens in the query image;

a classifier construction engine arranged to form a classifier on the basis of the identified tokens in the query image and on the basis of a training set of images by selecting a subset of the identified tokens such that the proportion of images in the training set which are classified as similar to the query image using the selected subset of the identified tokens is below a specified bound;

a processor arranged to use the formed classifier to classify images from a database of images according to their similarity to the query image; and

an output arranged to provide images from the database on the basis of their classification.

12. The apparatus as claimed in claim 11 wherein the classifier construction engine is arranged to form classifiers by combining tokens using AND operators to form groups of tokens and to combine groups of tokens using OR operators.

13. The apparatus as claimed in claim 11 wherein the classifier construction engine is arranged to form classifiers by combining tokens to form groups of tokens and to combine groups of tokens using OR operators.

14. The apparatus as claimed in claim 11, which further comprises a learning engine arranged:

to receive the training set of images, at least some of the images being identified as pairs of similar images, and

to form a pool of candidate subsets of tokens.

15. The apparatus as claimed in claim 11, wherein the training set comprises some images which are not specified as similar or dissimilar to each other.

16. One or more storage devices with device-executable instructions for performing operations comprising:

receiving a query item;

analyzing content of the query item, the analyzing the content of the query item comprising identifying tokens in that query item using a library of tokens, wherein each token comprises a symbol representing a cluster of features;

dynamically forming a classifier at query time on the basis of the query item'"'"'s content and the basis of properties of that content with respect to a training set of items, the training set comprising a plurality of pairs of items and a plurality of background items such that for each pair, the items in that pair are specified as similar to one another, the forming the classifier comprising choosing a subset of the identified tokens such that, on the training set as many as possible of the similar pairs have the chosen subset of tokens while the number of background items containing the subset of tokens is below a specified bound; and

using the classifier to select a plurality of items from a database of items.

17. The one or more storage devices as claimed in claim 16, wherein the training set comprises some items which are not specified as similar or dissimilar to each other.