Query optimization for visual information retrieval system

• US 5,913,205 A
• Filed: 03/28/1997
• Issued: 06/15/1999
• Est. Priority Date: 03/29/1996
• Status: Expired due to Term

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Virage, Inc. (HP Inc.)
• Inventors: Bach, Jeffrey R., Horowitz, Bradley, Jain, Ramesh, Gupta, Amarnath, Shu, Chiao-fe, Fuller, Charles E.
• Primary Examiner(s): Von Buhr, Maria N.
• Application Number:
  US08/825,831
• Time in Patent Office: 809 Days
• Field of Search: 707/2, 707/5, 707/104, 382/305, 382/232 T
• US Class Current: 1/1
• CPC Class Codes: G06F 16/532 Query formulation, e.g. graphical querying
• CPC Class Codes: G06F 16/58 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06F 16/5862 using texture
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A system and method for content-based search and retrieval of visual objects. A base visual information retrieval (VIR) engine utilizes a set of universal primitives to operate on the visual objects. An extensible VIR engine allows custom, modular primitives to be defined and registered. A custom primitive addresses domain specific problems and can utilize any image understanding technique. Object attributes can be extracted over the entire image or over only a portion of the object. A schema is defined as a specific collection of primitives. A specific schema implies a specific set of visual features to be processed and a corresponding feature vector to be used for content-based similarity scoring. A primitive registration interface registers custom primitives and facilitates storing of an analysis function and a comparison function to a schema table. A heterogeneous comparison allows objects analyzed by different schemas to be compared if at least one primitive is in common between the schemas. A threshold-based comparison is utilized to improve performance of the VIR engine. A distance between two feature vectors is computed in any of the comparison processes so as to generate a similarity score.

Claims

1. A method of optimization of object comparisons for a database query, wherein the database includes a plurality of visual objects and associated feature vectors, the method comprising:

providing a cost for executing a comparison process for each of a plurality of visual primitives of any one of the feature vectors; and

applying the comparison process for each visual primitive as between any selected at least two of the feature vectors as a function of the cost.

2. The method defined in claim 1, additionally comprising the step of providing the comparison process for each of the plurality of visual primitives.

3. The method defined in claim 1, wherein the function orders the visual primitives from least to greatest cost.

4. The method defined in claim 3, additionally comprising the step of further ordering the primitives by a set of primitive weights.

5. The method defined in claim 1, wherein the step of providing a cost, comprises the steps of:

assigning a computation cost of a predetermined value to a selected primitive; and

assigning a computation cost for each of a set of target primitives relative to the cost of the selected primitive.

6. The method defined in claim 5, wherein the step of assigning a cost for the target primitives comprises the steps of:

a) executing the selected primitive to establish a timing baseline;

b) executing one of the target primitives;

c) determining a ratio of the time of execution for the target primitive to the time of execution for the selected primitive as the cost of the target primitive; and

d) repeating steps b-c for each of the target primitives.

7. The method defined in claim 5, wherein the target primitives are the non-selected primitives in a predefined schema of primitives.

8. The method defined in claim 1, additionally comprising the step of registering the visual primitives and the associated costs with a search engine.

9. A similarity engine for content-based retrieval of images having the capability of optimizing object comparisons for a database query wherein the database includes a plurality of visual objects and associated feature vectors, the engine comprising:

means for providing a cost for executing a comparison process for each of a plurality of visual primitives of any one of the feature vectors; and

means for employing the comparison process for each visual primitive as between any selected at least two of the feature vectors as a function of the cost.

10. The engine of claim 10, wherein the means for applying orders the visual primitives from least to greatest cost.

11. The engine of claim 10, wherein the means for applying further includes means for ordering the primitives by a set of primitive weights.

12. A method of optimization of object comparisons for a database query utilizing visual primitives each of which includes a comparison function and wherein the database includes a plurality of visual objects, the method comprising:

determining a cost for executing a comparison function for each of a plurality of visual primitives belonging to a feature vector representative of a visual object; and

applying the comparison process for each visual primitive as between any selected at least two of the feature vectors as a function of the cost.

13. The method defined in claim 12, additionally comprising providing the comparison function for each of the plurality of visual primitives.

14. The method defined in claim 12, wherein the function orders the visual primitives from least to greatest cost.

15. The method defined in claim 14, additionally comprising further ordering the primitives by a set of primitive weights.

16. The method defined in claim 12, wherein determining a cost, comprises:

assigning a computation cost of a predetermined value to a selected primitive; and

assigning a computation cost for each of a set of target primitives relative to the cost of the selected primitive.