Method and apparatus for similarity retrieval from iterative refinement

• US 7,272,593 B1
• Filed: 01/26/1999
• Issued: 09/18/2007
• Est. Priority Date: 01/26/1999
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Smith, John R., Castelli, Vittorio, Li, Chung-Sheng
• Primary Examiner(s): Truong; Cam Y T
• Application Number:
  US09/237,646
• Time in Patent Office: 3,157 Days
• Field of Search: 345/431, 707/102, 707/10, 707/4, 707/101, 707 1- 3, 707/5, 707/6, 707/104.1, 382/225, 382/154
• US Class Current: 707/600
• CPC Class Codes: G06F 16/3326 using relevance feedback from the user, e.g. relevance feedback on documents, documents sets, document terms or passages
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: G06F 18/2137 based on criteria of topology preservation, e.g. multidimensional scaling or self-organising maps
• CPC Class Codes: G06F 18/41 Interactive pattern learning with a human teacher
• CPC Class Codes: Y10S 707/957 Multidimensional
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

An iterative refinement algorithm for content-based retrieval of images based on low-level features such as textures, color histograms, and shapes that can be described by feature vectors. This technique adjusts the original feature space to the new application by performing nonlinear multidimensional scaling. Consequently, the transformed distance of those feature vectors which are considered to be similar is minimized in the new feature space. Meanwhile, the distance among clusters are maintained. User feedback is utilized to refine the query, by dynamically adjusting the similarity measure and modifying the linear transform of features, along with revising the feature vectors.

Claims

1. A computerized method for retrieving multidimensional data from a database in response to a user query, comprising the steps of:

a. extracting indices from said database;

b. first searching said database to retrieve said multidimensional data based on said user query, wherein said searching is preceded by retrieving indices to focus said search on indexed information in said database;

c. presenting retrieved multidimensional data to a user;

d. receiving user input based on said retrieved multidimensional data;

e. transforming said database based on said user input to generate a transformed database, wherein said transforming comprises at least one of modifying a linear transform matrix of said database, transforming feature space of the database, changing distance/similarity measures within said database, and changing weighting features within said database;

f. successively searching said transformed database to retrieve said multidimensional data by applying said extracted indices to said transformed database; and

g. repeating steps c through f until the user is satisfied with a result of said user query.

2. The method of claim 1 wherein said step of transforming said database further comprises reformulating the query based on said user input and wherein said searching said transformed database comprises searching said transformed database based on said reformulated query.

3. A program storage device readable by machine, embodying a program of instructions executable by the machine to perform method steps for retrieving multidimensional data from a database in response to a user query, said method steps comprising:

a. extracting indices from said database;

b. first searching said database to retrieve said multidimensional data based on said user query, wherein said searching is preceded by retrieving indices to focus said search on indexed information in the database;

c. presenting retrieved multidimensional data to a user;

d. receiving user input based on said retrieved data;

e. transforming said database based on said user input to generate a transformed database, wherein said transforming comprises at least one of modifying a linear transform matrix of said database, transforming feature space of the database, changing distance/similarity measures within said database, and changing weighting features within said database;

f. successively searching said transformed database to retrieve multidimensional data by applying said extracted indices to said transformed database; and

g. repeating steps c through f until the user is satisfied with a result of said user query.

4. The device of claim 3 wherein said method steps of transforming said database further comprises reformulating the query based on said user input and wherein said searching said transformed database comprises searching said transformed database based on said reformulated query.

5. A system having at least a processor and a memory for retrieving multidimensional data from a database in response to a user query, comprising:

said memory storing said database;

a component for extracting indices from said database;

a search component for first searching said database to retrieve multidimensional data based on said user query, wherein said searching is preceded by retrieving indices to focus said search on indexed information in the database;

a presentation component for presenting retrieved data to a user;

a receiver component for receiving user input based on said retrieved multidimensional data; and

a transformation component for transforming said database based on said user input to generate a transformed database, wherein said transforming comprises at least one of modifying a linear transform matrix of the database, transforming feature space of the database, changing distance/similarity measures within said database, and changing weighting features within said database, wherein said system repeatedly searches said transformed database to retrieve multidimensional data by applying said extracted indices to said transformed database and to present retrieved data to the user until the user is satisfied with a result of said user query.