Indexing method for image search engine

• US 6,084,595 A
• Filed: 02/24/1998
• Issued: 07/04/2000
• Est. Priority Date: 02/24/1998
• 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
• Primary Examiner(s): Nguyen, Phu K.
• Assistant Examiner(s): Vo, Cliff N.
• Application Number:
  US09/028,279
• Time in Patent Office: 861 Days
• Field of Search: 345/418, 345/430, 345/431, 345/429, 345/432
• US Class Current: 345/589
• CPC Class Codes: G06F 16/5838 using colour

Abstract

One aspect of the invention is directed to a search engine having indexed retrieval to improve computational efficiency of searching large databases of rich objects such as images. Feature vectors are extracted from images and stored in a feature vector database. When a query is submitted to the engine, a query feature vector Q will be specified, as well as a distance threshold T, indicating the maximum distance that is of interest for this query. All images within a distance of T will be identified by the query. Range constraints are defined such that all feature vectors within a distance of T of the query feature vector, satisfy all of the range constraints. The constraint is dependent on the specific primitive being indexed. The constraint is also defined such that any feature vector which is within a distance of T of the query feature vector also satisfies a functional constraint. By reducing the number of feature vectors retrieved from the database and the number of feature vector comparisons, the query process becomes much more efficient.

Claims

1. A method of feature vector indexing, comprising the steps of:

providing a plurality of feature vectors, each feature vector indicative of one of a plurality of objects, wherein each feature vector comprises at least one primitive, each primitive being associated with an attribute of the object and identifying a plurality of features, each feature having an associated feature coefficient;

using a distance metric to select index values which are indicative of features of the feature vector;

providing a target feature vector and a plurality of user weights;

generating a constraint based on the target feature vector and the plurality of user weights; and

applying the constraint to the index values so as to select a subset of the feature vectors.

2. The method of claim 1, wherein the primitive is color.

3. The method of claim 2, wherein the identified plurality of features include hue, saturation, and mean intensity.

4. The method of claim 1, wherein the primitive is texture.

5. The method of claim 4, wherein the identified plurality of features include edge intensity, randomness, periodicity, and orientation.

6. The method of claim 1, wherein the primitive is shape.

7. The method of claim 6, wherein the identified plurality of features include algebraic moments, turning angles, and elongatedness.

8. The method of claim 1, wherein each object comprises a portion of an image.

9. The method of claim 1, wherein each object comprises an entire image.

10. The method of claim 1, wherein each object comprises visual information.

11. The method of claim 1, additionally comprising the step of analyzing each of the plurality of objects resulting in one feature vector for each object.

12. The method of claim 1, wherein the distance metric utilizes the feature coefficients.

13. The method of claim 12, wherein the selected features of the feature vector have the highest feature coefficients with respect to the feature coefficients of the feature vector.

14. The method of claim 1, wherein each primitive of the feature vector is of a different primitive type and the index values are dependent on the primitive type.

15. The method of claim 1, wherein each of the user weights is associated with one of the primitives.

16. The method of claim 1, additionally comprising the step of comparing each one of the subset feature vectors with the target feature vector, wherein the user weights are combined with the results of the comparison to provide a score for each vector comparison.

17. The method of claim 16, additionally comprising the steps of:

providing a primitive function to extract an attribute from each object; and

adding a new primitive function, wherein the new primitive function comprises the comparing step for a selected attribute.

18. The method of claim 1, additionally comprising the steps of:

providing a primitive function to extract an attribute from each object; and

adding a new primitive function, wherein the new primitive function comprises an indexing step for a selected attribute.

19. The method of claim 1, additionally comprising the steps of:

providing a primitive function to extract an attribute from each object; and

adding a new primitive function, wherein the new primitive function comprises a generating a constraint step for a selected attribute.

20. A method of feature vector indexing, comprising the steps of:

providing a plurality of feature vectors, each feature vector indicative of one of a plurality of objects, wherein each feature vector comprises at least one primitive, each primitive being associated with an attribute of the object and identifying a plurality of features;

using a distance metric to select a plurality of index values which are indicative of features of the feature vector; and

generating an index structure corresponding to the feature vectors and accessed by the selected index values.

21. A method of feature vector indexing, comprising the steps of:

providing a plurality of feature vectors, each feature vector indicative of one of a plurality of objects;

providing an index structure corresponding to the feature vectors, wherein the index values of the index structure are indicative of features of the feature vectors;

providing a target feature vector and a plurality of user weights;

generating a constraint based on the target feature vector and the plurality of user weights; and

applying the constraint to the index structure so as to select a subset of the feature vectors.