US6084595A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Indexing method for image search engine
Assignee: Micro Focus LLC
•
Filing: 1998-02-24
•
Granted: 2000-07-04
•
Expires: 2018-02-24
Abstract
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.
Inventors
- 👤 Jeffrey R Bach
- 👤 Bradley Horowitz
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 05:01
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/50; G06F16/58; G06F16/583; G06F16/5838
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
120 words
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.
Claim 2
Independent Claim
120 words
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.
Claim 3
Dependent Claim
10 words
The method of claim 1, wherein the primitive is color.
Claim 4
Dependent Claim
17 words
The method of claim 2, wherein the identified plurality of features include hue, saturation, and mean intensity.
Claim 5
Dependent Claim
10 words
The method of claim 1, wherein the primitive is texture.
Claim 6
Dependent Claim
18 words
The method of claim 4, wherein the identified plurality of features include edge intensity, randomness, periodicity, and orientation.
Claim 7
Dependent Claim
10 words
The method of claim 1, wherein the primitive is shape.
Claim 8
Dependent Claim
18 words
The method of claim 6, wherein the identified plurality of features include algebraic moments, turning angles, and elongatedness.
Claim 9
Dependent Claim
14 words
The method of claim 1, wherein each object comprises a portion of an image.
Claim 10
Dependent Claim
12 words
The method of claim 1, wherein each object comprises an entire image.
Claim 11
Dependent Claim
11 words
The method of claim 1, wherein each object comprises visual information.
Claim 12
Dependent Claim
25 words
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.
Claim 13
Dependent Claim
13 words
The method of claim 1, wherein the distance metric utilizes the feature coefficients.
Claim 14
Dependent Claim
28 words
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.
Claim 15
Dependent Claim
28 words
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.
Claim 16
Dependent Claim
18 words
The method of claim 1, wherein each of the user weights is associated with one of the primitives.
Claim 17
Dependent Claim
43 words
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.
Claim 18
Dependent Claim
40 words
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.
Claim 19
Dependent Claim
40 words
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.
Claim 20
Dependent Claim
42 words
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.
Claim 21
Independent Claim
89 words
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.
Claim 22
Independent Claim
89 words
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.
Claim 23
Independent Claim
96 words
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.
Claim 24
Independent Claim
96 words
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.
References Cited (Backward Citations)
US5949427A
Cited
US5647058A
Cited
US5949409A
Cited
US5896121A
Cited
US5940067A
Cited
US5892516A
Cited
US5949967A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-07-04 | 2004-01-03 | 2004-07-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-07-04 | 2008-01-03 | 2008-07-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-07-04 | 2012-01-03 | 2012-07-04 | $7700.00 | Window Closed / Lapsed |