System and method for sequential processing for content-based retrieval of composite objects

• US 6,446,060 B1
• Filed: 01/26/1999
• Issued: 09/03/2002
• Est. Priority Date: 01/26/1999
• Status: Expired due to Term

• Current Assignee: SINOEAST CONCEPT LIMITED (Tencent Holdings Limited)
• Original Assignee: International Business Machines Corporation
• Inventors: Bergman, Lawerence D., Smith, John R., Castelli, Vittorio, Li, Chung-Sheng
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): Nguyen, Tam V
• Application Number:
  US09/237,734
• Time in Patent Office: 1,316 Days
• Field of Search: 705/10, 707/204, 707/103, 707/10, 707/5, 707/100, 707/3, 707/104.1, 382/233, 703/3, 369/36
• US Class Current: 707/770
• 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/915 Image
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. The method of claim 5 further comprising caching said query blocks.

8. 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.

9. The method of claim 8 further comprising determining which of said at least one combination has the optimal similarity measure.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. The device of claim 16 wherein said method further comprising caching said query blocks.

19. 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.

20. The device of claim 19 wherein said method further comprising determining which of said at least one combination has the optimal similarity measure.

21. 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.