Threshold-based comparison

• US 5,915,250 A
• Filed: 03/28/1997
• Issued: 06/22/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): Black, Thomas G.
• Assistant Examiner(s): WALLACE, MICHAEL J
• Application Number:
  US08/829,790
• Time in Patent Office: 816 Days
• Field of Search: 707/1, 707/3, 707/4, 707/5, 707/6, 707/7, 707/2, 707/104, 707/100, 382/209, 382/220, 382/305, 395/348
• 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/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/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 visual object comparison for a database of visual objects, comprising the steps of:

a) applying primitives to a first visual object to extract a first feature vector, each primitive providing at least one primitive value to the first feature vector;

b) applying primitives to a second visual object to extract a second feature vector, each primitive providing at least one primitive value to the second feature vector;

c) providing an ordering value for each primitive to order the primitives;

d) comparing one of the primitive values from the first feature vector with the corresponding primitive value of the second feature vector according to the ordering so as to obtain a primitive score;

e) applying a primitive weight to the primitive score to determine a weighted primitive score;

f) summing the weighted primitive score into a summed total score; and

g) repeating steps d-f until the summed total score crosses a selected threshold.

2. The method defined in claim 1, wherein the repeating step alternatively repeats until all primitives in one of the feature vectors have been processed to produce a final score.

3. The method defined in claim 1, wherein the ordering value is the primitive weight corresponding to each primitive.

4. The method defined in claim 1, wherein the ordering value is a cost associated with the execution time of the primitive.

5. The method defined in claim 1, wherein the ordering value is a combination of the primitive weight corresponding to each primitive and a cost associated with the execution time of the primitive.

6. The method defined in claim 1, wherein the order of the primitives is defined by a function which orders the primitives from least ordering value to greatest ordering value.

7. The method defined in claim 6, wherein the function comprises multiplication.

8. The method defined in claim 6, wherein the function is defined as maximum((1.0-cost), weight).

9. A software system for visual object comparison of a database of visual objects, the system comprising:

means for applying primitives to a first visual object to extract a first feature vector, each primitive providing at least one primitive value to the first feature vector;

means for applying primitives to a second visual object to extract a second feature vector, each primitive providing at least one primitive value to the second feature vector;

means for providing an ordering value for each primitive to order the primitives; and

means for thresholding including;

a) comparing one of the primitive values from the first feature vector with the corresponding primitive value of the second feature vector according to the ordering so as to obtain a primitive score,

b) applying a primitive weight to the primitive score to determine a weighted primitive score,

c) summing the weighted primitive score into a summed total score, and

d) repeating a-c until the summed total score meets a selected threshold.

10. A program storage device storing instructions that when executed by a computer perform a method for a threshold based visual object comparison of a database of visual objects, the method comprising:

a) applying primitives to a first visual object to extract a first feature vector, each primitive providing at least one primitive value to the first feature vector;

b) applying primitives to a second visual object to extract a second feature vector, each primitive providing at least one primitive value to the second feature vector;

c) providing an ordering value for each primitive to order the primitives;

d) comparing one of the primitive values from the first feature vector with the corresponding primitive value of the second feature vector according to the ordering so as to obtain a primitive score;

e) applying a primitive weight to the primitive score to determine a weighted primitive score;

f) summing the weighted primitive score into a summed total score; and

g) repeating steps d-f until the summed total score meets a selected threshold.