US6446060B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for sequential processing for content-based retrieval of composite objects
Assignee: Sinoeast Concept Ltd
•
Filing: 1999-01-26
•
Granted: 2002-09-03
•
Expires: 2019-01-26
Abstract
Abstract Similarity measure has been one of the critical issues for successful content-based retrieval. Simple quadratic forms of distance is inadequate as it does not necessary correspond to perceived similarity nor is it adaptive to different applications. This patent application describes a new sequential query processing algorith for evaluating content-based composite object queries. The composite objects consist of spatial and temporal arrangements of simple objects. The simple objects are defined in terms of spatial, temporal, feature and semantic attributes. The query method defines a process for executing a best-first search for the matches to the query, while providing a flexible framework for broadening the search space as required. The query method guarantees that there are no false dismissals of the candidate composite objects.
Inventors
- 👤 Lawerence D. Bergman
- 👤 Vittorio Castelli
- 👤 Chung-Sheng Li
- 👤 John R. Smith
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 18:20
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/50; G06F16/58; G06F16/583; G06F16/5838; G06F16/5854; G06F16/5862; Y; Y10; Y10S; Y10S707/00; Y10S707/912; Y10S707/913; Y10S707/915; Y10S707/953; Y10S707/956; Y10S707/99931; Y10S707/99933; Y10S707/99941; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
97 words
A method for providing computer retrieval of images of composite objects in response to a query, each of said images having a plurality of features and wherein said images are stored in at least one storage medium and are indexed according to one or more of said plurality of features, comprising the steps of: a. receiving an input query; b. automatically identifying a plurality of sub-goals in said query; c. automatically prioritizing said sub-goals by ordering said sub-goals according to the amount of information in said query; and d. processing said sub-goals in order of said prioritizing.
Claim 2
Independent Claim
97 words
A method for providing computer retrieval of images of composite objects in response to a query, each of said images having a plurality of features and wherein said images are stored in at least one storage medium and are indexed according to one or more of said plurality of features, comprising the steps of: a. receiving an input query; b. automatically identifying a plurality of sub-goals in said query; c. automatically prioritizing said sub-goals by ordering said sub-goals according to the amount of information in said query; and d. processing said sub-goals in order of said prioritizing.
Claim 3
Independent Claim
92 words
A method for providing computer retrieval of images of composite objects in response to a query, each of said images having a plurality of features and wherein said images are stored in at least one storage medium and are indexed according to one or more of said plurality of features, comprising the steps of: a. automatically identifying a plurality of sub-goals in said query; b. automatically prioritizing said sub-goals by ordering said sub-goals according to the amount of information in said query; and c. retrieving images having features similar to said sub-goals.
Claim 4
Independent Claim
92 words
A method for providing computer retrieval of images of composite objects in response to a query, each of said images having a plurality of features and wherein said images are stored in at least one storage medium and are indexed according to one or more of said plurality of features, comprising the steps of: a. automatically identifying a plurality of sub-goals in said query; b. automatically prioritizing said sub-goals by ordering said sub-goals according to the amount of information in said query; and c. retrieving images having features similar to said sub-goals.
Claim 5
Dependent Claim
26 words
The method of claim 2 wherein said prioritizing comprises ordering said sub-goals to minimize the number of unconstrained lookups in said at least one storage medium.
Claim 6
Dependent Claim
28 words
The method of claim 2 wherein said prioritizing comprises ordering said sub-goals in order from the sub-goals having the most feature information to sub-goals having no feature information.
Claim 7
Dependent Claim
32 words
The method of claim 2 wherein said prioritizing comprises the steps of: organizing said sub-goals into a tree hierarchy of query blocks; and determining the retrieval process needed to satisfy each sub-goal.
Claim 8
Dependent Claim
25 words
The method of claim 5 wherein said prioritizing further comprises the step of selecting a plurality of combinations of sub-goal query blocks for retrieval processing.
Claim 9
Dependent Claim
11 words
The method of claim 5 further comprising caching said query blocks.
Claim 10
Dependent Claim
51 words
The method of claim 6 wherein said retrieving comprises evaluating a similarity measure for each query block in each of said combinations of sub-goal query blocks, said similarity measure representing the similarity of said sub-goal query to at least one feature of a candidate one of said plurality of stored images.
Claim 11
Dependent Claim
20 words
The method of claim 8 further comprising determining which of said at least one combination has the optimal similarity measure.
Claim 12
Dependent Claim
35 words
The method of claim 5 wherein said tree hierarchy comprises a plurality of stages for said query blocks and wherein said prioritizing further comprises selecting at least one path to one of said query blocks.
Claim 13
Dependent Claim
99 words
The method of claim 10 wherein said retrieving comprises the steps of, for a given stage: a. evaluating all paths to said one of said query blocks to arrive at a value for each path; b. ordering said paths according to said value; c. selecting a fixed number of ordered paths whose value is greatest; d. determining if paths in a different stage have a value greater than that for each of said selected paths; e. repeating steps a through d until no paths in any stage have a value greater than that for each of said selected paths.
Claim 14
Dependent Claim
89 words
Apparatus for computer retrieval of images of composite objects in response to a query, each of said images having a plurality of features, comprising: at least one storage medium for storing said images indexed according to one or more of said plurality of features; processing means for automatically identifying a plurality of sub-goals in said query and for automatically prioritizing said sub-goals by ordering said sub-goals according to the amount of information in said query; and a similarity retrieval engine for retrieving images having features similar to said sub-goals.
Claim 15
Dependent Claim
89 words
Apparatus for computer retrieval of images of composite objects in response to a query, each of said images having a plurality of features, comprising: at least one storage medium for storing said images indexed according to one or more of said plurality of features; processing means for automatically identifying a plurality of sub-goals in said query and for automatically prioritizing said sub-goals by ordering said sub-goals according to the amount of information in said query; and a similarity retrieval engine for retrieving images having features similar to said sub-goals.
Claim 16
Dependent Claim
111 words
A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for providing computer retrieval of images of composite objects in response to a query, each of said images having a plurality of features and wherein said images are stored in at least one storage medium and are indexed according to one or more of said plurality of features, said method steps comprising: a. automatically identifying a plurality of sub-goals in said query; b. automatically prioritizing said sub-goals by ordering said sub-goals according to the amount of information in said query; and c. retrieving images having features similar to said sub-goals.
Claim 17
Dependent Claim
111 words
A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for providing computer retrieval of images of composite objects in response to a query, each of said images having a plurality of features and wherein said images are stored in at least one storage medium and are indexed according to one or more of said plurality of features, said method steps comprising: a. automatically identifying a plurality of sub-goals in said query; b. automatically prioritizing said sub-goals by ordering said sub-goals according to the amount of information in said query; and c. retrieving images having features similar to said sub-goals.
Claim 18
Dependent Claim
26 words
The device of claim 13 wherein said prioritizing comprises ordering said sub-goals to minimize the number of unconstrained lookups in said at least one storage medium.
Claim 19
Dependent Claim
28 words
The device of claim 13 wherein said prioritizing comprises ordering said sub-goals in order from the sub-goals having the most feature information to sub-goals having no feature information.
Claim 20
Dependent Claim
32 words
The device of claim 13 wherein said prioritizing comprises the steps of: organizing said sub-goals into a tree hierarchy of query blocks; and determining the retrieval process needed to satisfy each sub-goal.
Claim 21
Dependent Claim
25 words
The device of claim 16 wherein said prioritizing further comprises the step of selecting a plurality of combinations of sub-goal query blocks for retrieval processing.
Claim 22
Dependent Claim
14 words
The device of claim 16 wherein said method further comprising caching said query blocks.
Claim 23
Dependent Claim
51 words
The device of claim 17 wherein said retrieving comprises evaluating a similarity measure for each query block in each of said combinations of sub-goal query blocks, said similarity measure representing the similarity of said sub-goal query to at least one feature of a candidate one of said plurality of stored images.
Claim 24
Dependent Claim
23 words
The device of claim 19 wherein said method further comprising determining which of said at least one combination has the optimal similarity measure.
Claim 25
Dependent Claim
70 words
A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for computing a query, said method steps comprising the steps of: a. automatically identifying a plurality of sub-goals in said query; b. automatically prioritizing said sub-goals by ordering said sub-goals according to the amount of information in said query; and c. processing said sub-goals in order of said prioritizing.
Claim 26
Dependent Claim
70 words
A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for computing a query, said method steps comprising the steps of: a. automatically identifying a plurality of sub-goals in said query; b. automatically prioritizing said sub-goals by ordering said sub-goals according to the amount of information in said query; and c. processing said sub-goals in order of said prioritizing.
References Cited (Backward Citations)
US5177685A
Cited
US5579471A
Cited
US5813009A
Cited
US5893909A
Cited
US5966730A
Cited
US5995459A
Cited
US5995965A
Cited
US6105022A
Cited
US6003039A
Cited
US5966702A
Cited
US6131099A
Cited
US6128630A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-09-02 | 2006-03-04 | 2006-09-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-09-02 | 2010-03-04 | 2010-09-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-09-02 | 2014-03-04 | 2014-09-03 | $7700.00 | Window Closed / Lapsed |