Visual dictionary

• US 5,983,237 A
• Filed: 08/21/1997
• Issued: 11/09/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: Hampapur, Arun, Horowitz, Bradley, Jain, Ramesh, Gupta, Amarnath
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): HAVAN, THU THAO
• Application Number:
  US08/916,904
• Time in Patent Office: 810 Days
• Field of Search: 707/7, 707/527, 707/518, 707/104, 707/1, 707/4, 707/3, 707/2, 707/5, 707/6, 707/526, 345/333, 345/334, 345/348, 704/9, 386/96, 386/305
• 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/99937 Sorting
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A system and method for improving the retrieval performance of a query engine in a visual information retrieval (VIR) system by encoding domain-specific knowledge into the VIR system through a visual dictionary or "victionary". The victionary is a dictionary-like information-mapping module that is used to retrieve visual information at a "semantic" level. A VIR system that performs generic image processing is enhanced by adding a query transformation unit and a query expansion unit, i.e., the victionary. With these additional components, a user may present a query either as a text term (such as a keyword or phrase), or as an image (with weights) and execute a "semantic query". During semantic query processing, the victionary-enhanced system transforms the user'"'"'s original term (or image query) to a set of equivalent queries, and internally executes all the equivalent queries before presenting the results to the user. The victionary unit is responsible for taking the term (or image query) and finding the equivalent feature vectors (and weights). A result processor accumulates the score sheets of each equivalent query and presents a composite ranking that reflects a faithful representation of each equivalent query to the user. The architecture of the victionary-enhanced system is open and extensible, so that one or more domain-specific victionary modules can be plugged into the system. The plug-in architecture of the victionary module is effected through an application programming interface (API).

Claims

1. A visual query processing method, comprising:

providing a user query;

applying the user query to a visual dictionary comprising a plurality of feature vectors so as to generate a set of query vectors; and

applying the query vectors to an image database comprising a plurality of images so as to provide a list of similar images.

2. The method defined in claim 1, wherein the user query comprises a text term.

3. The method defined in claim 1, wherein the user query comprises an image.

4. The method defined in claim 1, additionally comprising:

rank ordering the list of images by degree of similarity; and

presenting the rank-ordered images to a user.

5. The method defined in claim 1, wherein at least one of the feature vectors has an associated weight.

6. The method defined in claim 1, wherein at least one of the feature vectors has a nominal component.

7. The method defined in claim 1, wherein at least one of the feature vectors has a definitional component.

13. The method defined in claim 1, wherein the user query comprises a video sequence.

8. A visual query processing system, comprising:

a visual dictionary, comprising feature vectors representative of images, capable of receiving a user query so as to select a set of feature vectors representative of the user query;

a query transformer that transforms the selected set of feature vectors into a set of image queries; and

a query processor receiving each separate query so as to index an image database comprising a plurality of images.

9. The system defmed in claim 8, additionally comprising a result processor that receives the results of the query processor and ranks the individual query results into a composite response.

10. The system defined in claim 8, wherein each feature vector has an associated weight.

11. The system defined in claim 9, additionally comprising a query parser for parsing the user query.

12. The system defined in claim 11, wherein a set of application programming interfaces are associated with the visual dictionary and query transformer for interfacing with the query processor, query parser and result processor.

14. The system defined in claim 8, wherein the user query comprises an image, a text term, or a video sequence.

15. A visual query processing method, comprising:

providing a user query having one or more user weights;

applying the user query to a visual dictionary comprising a plurality of feature vectors so as to generate a set of query feature vectors, wherein each of the query feature vectors has an associated feature weight; and

applying the query feature vectors and query feature weights to an image database comprising a plurality of images so as to provide a list of similar images.

16. The method defined in claim 15, wherein the user query comprises a text term.

17. The method defined in claim 15, wherein the user query comprises an image.

18. The method defined in claim 15, wherein the user query comprises a video sequence.

19. The method defined in claim 15, additionally comprising:

rank ordering the list of images by degree of similarity; and

presenting the rank-ordered images to a user.

20. The method defined in claim 17, wherein a value of a selected user weight is set by a user.

21. The method defined in claim 20, wherein the value is associated with color, texture or shape.

22. The method defined in claim 20, wherein the value is indicative of a user'"'"'s relative preference of one or more individual properties of the user query.

23. The method defined in claim 22, wherein the property is hue, saturation, intensity, edge density, randomness, periodicity, orientation, algebraic moments, turning angles, or elongatedness.

24. The method defined in claim 20, wherein applying the user query comprises communicating a feature vector and the one or more weights corresponding with the user query to the visual dictionary.

25. The method defined in claim 24, wherein applying the user query further comprises determining an intersection of the feature vector and the one or more weights corresponding with the user query with the plurality of feature vectors of the visual dictionary.

26. The method defined in claim 15, wherein at least one of the feature vectors has a nominal component.

27. The method defined in claim 15, wherein at least one of the feature vectors has a definitional component.

28. A visual query processing method, comprising:

providing a user query;

applying the user query to a visual dictionary comprising a plurality of feature vectors so as to generate a set of query vectors, wherein each feature vector has a corresponding feature weight; and

applying the query vectors to an image database comprising a plurality of images so as to provide a list of similar images.

29. The method defined in claim 28, wherein the user query comprises a text term.

30. The method defined in claim 28, wherein the user query comprises an image.

31. The method defined in claim 28, wherein the user query comprises a video sequence.

32. A visual query processing system, comprising:

a visual dictionary, comprising feature vectors representative of images, capable of receiving a user query having one or more user weights so as to select a set of feature vectors representative of the user query; and

a similarity comparison engine receiving the selected set of feature vectors and generating a list of similar images.

33. The system defined in claim 32, wherein images identified in the list of similar images substantially satisfy the user query.

34. The system defined in claim 32, wherein the similarity comparison engine includes a query transformer that transforms the selected set of feature vectors into a set of image queries, and a query processor receiving each separate query so as to index an image database comprising a plurality of images.

35. The system defined in claim 32, wherein each feature vector has an associated weight.

36. The system defined in claim 35, additionally comprising a query parser for parsing the user query, wherein the output of the query parser comprises a query feature vector and an associated query feature weight structure corresponding with the user weights.

37. The system defined in claim 36, wherein the visual dictionary comprises an association manager that determines a similarity distance between the query feature vector and the query feature weight structure to the feature vectors and associated weights of the visual dictionary.

38. The system defined in claim 32, wherein the user query comprises an image.

39. The system defined in claim 32, wherein the user query comprises a video sequence.

40. The system defined in claim 32, wherein a value of a selected user weight is set by a user.

41. The system defined in claim 40, wherein the value is indicative of a user'"'"'s relative preference of one or more individual properties of the user query.

42. The system defined in claim 41, wherein the property is selected from the group consisting of color, texture and shape.

43. A visual query processing system, comprising:

a visual dictionary, comprising feature vectors representative of images, receiving a user query comprising a query image or one or more text terms so as to select a set of feature vectors representative of the user query;

a query transformer that transforms the selected set of feature vectors into a set of image queries; and

a query processor receiving each separate image query so as to index an image database comprising a plurality of images.

44. The system defined in claim 43, wherein each feature vector has an associated weight.

45. The system defined in claim 43, additionally comprising a query parser for parsing the user query, wherein the output of the query parser comprises a set of terms in a term structure and a combinator associated with the text terms.

46. The system defined in claim 45, wherein the combinator represents a type of user-supplied combination condition comprising "OR"or "AND".

47. The system defined in claim 46, wherein the query transformer operates on the selected set of feature vectors according to the combinator.

48. The system defined in claim 47, wherein the query transformer performs an intersection of the terms in the term structure if the combinator is "AND".

49. The system defined in claim 43, additionally comprising a query parser for parsing the user query, wherein the output of the query parser comprises a query feature vector and an associated query feature weight structure.

50. The system defined in claim 49, wherein the query transformer operates on the selected set of feature vectors according to the query feature vector and the query feature weight structure.