Method for fuzzy logic rule based multimedia information retrival with text and perceptual features

• US 7,065,521 B2
• Filed: 03/07/2003
• Issued: 06/20/2006
• Est. Priority Date: 03/07/2003
• Status: Expired due to Fees

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Li, Zhu, Lindsley, Brett L., Gandhi, Bhavan
• Primary Examiner(s): Ali, Mohammad
• Assistant Examiner(s): PANNALA, SATHYANARAYA R
• Application Number:
  US10/383,897
• Publication Number:
  US 20040177069A1
• Time in Patent Office: 1,201 Days
• Field of Search: 707 1- 5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/48 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A search system (200) for a database (224) including records having a multiple disparate types of media is provided. The search system supports queries, that include different types of search criteria, including content based retrieval search criteria. A fuzzy logic method (400) is provided for effectively combining the results of different types of search criteria. The fuzzy logic method also allows confidence levels entered by the user for search criteria to be considered in combining results. Retrieval relevance values for documents for at least some search criteria are used in the fuzzy logic method. For content based image retrieval searches, the retrieval relevance values are computed by mapping a distance between quantitative characterizations of a search basis image, and other images into a finite range.

Claims

1. A method for searching a database comprising, in a computer:

inputting a search string that comprises a plurality of search string arguments connected by one or more operators wherein each search string argument specifies a search criteria;

computing a distance measure between a quantitative characterization corresponding to each of one or more of the search criteria, and quantitative characterizations of each of a plurality of records;

selecting records for inclusion in answer sets for each mth search criteria among the one or more search criteria based, at least in part, on a plurality of distance measures each involving a quantitative characterization corresponding to the mth search criteria, and a quantitative characterization corresponding to one of the plurality of records;

for each jth record in the answer set of each mth search criteria among the one or more search criteria, computing a retrieval relevance value by a method that comprises mapping a distance measure corresponding to the mth search criteria and the jth record into a finite range;

for each ith record in the answer set of an mth content based retrieval algorithm based query, computing a retrieval relevance value by evaluating a function of the following form;

RRV_i,m^C=(1−

H(G_F(X_i−

X_m)))^η

where,

RRVi,m^c is a retrieval relevance value of an ith media file to a mth search criteria basis media file based on a cth content based retrieval algorithm;

x_i is a quantitative characterization of the ith media file based on the cth content based retrieval algorithm;

x_m is a quantitative characterization of the mth search criteria basis media file based on the cth content based retrieval algorithm;

G_F is a distance function;

H is a mapping function that maps an argument into a finite range; and

η

is a constant exponent;

for each kth operator of the search string performing an operation specified by the kth operator on answer sets that are arguments of the kth operator to form a kth answer set for the kth operator;

for each nth record in the kth answer set for each kth operator, assigning a retrieval relevance value to the nth record in the kth answer set, wherein the retrieval relevance value is a mathematical function of one or more quantitative characterizations associated with the nth record in answer sets that are arguments of the kth operator.

2. The method according to claim 1 wherein:

selecting records for inclusion in answer sets for each mth search criteria comprises;

comparing the plurality of distance measures to one or more predetermined distance limits.

3. The method according to claim 1 wherein assigning a retrieval relevance value to the nth record in the kth answer set comprises:

assigning a retrieval relevance value to the nth record in the kth answer set that is derived from retrieval relevance values associated with the nth record in answer sets that are arguments of the kth operator.

4. The method according to claim 1 wherein:

inputting a search string comprises;

inputting a search string that comprises one or more search string arguments that are associated with one or more user specified confidence levels; and

for each record in the answer set of each mth search criteria among the one or more search criteria, computing a retrieval relevance value comprises;

multiplying a value obtained by mapping, by a function of the user specified confidence level.

5. The method according to claim 4 wherein:

the function is the identity function.

6. The method according to claim 1 wherein:

G_F is selected from the group consisting of the one-norm and the two-norm.

7. The method according to claim 1 where the mapping function H is defined as:

8. The method according to claim 3 wherein:

inputting a search string comprises;

inputting a search string that comprises one or more Boolean AND operators;

for each kth operator of the search string performing an operation specified by the kth operator comprises;

for each lth AND operator of the search string taking and intersection of answer sets that are arguments of the lth AND operator to form an answer set for the lth AND operator;

for each nth record in the answer set for each kth operator, assigning a retrieval relevance value to the nth record comprises;

for each mth record in the answer set for each lth AND operator, assigning a retrieval relevance value that is a minimum of retrieval relevance values associated with the mth record in answer sets that are arguments of the lth AND operator.

9. The method according to claim 3 wherein:

inputting a search string comprises;

inputting a search string that comprises one or more Boolean OR operators;

for each kth operator of the search string performing an operation specified by the kth operator comprises;

for each lth OR operator of the search string taking a union of answer sets that are arguments of the lth OR operator to form an answer set for the lth OR operator;

for each nth record in the answer set for each kth operator, assigning a retrieval relevance value to the nth record comprises;

for each mth record in the answer set for each ith OR operator, assigning a retrieval relevance value that is a maximum of one or more relevance retrieval values associated with the mth record in answer sets that are arguments of the lth OR operator.

10. The method according to claim 1 wherein:

inputting a search string comprises;

inputting a search string that comprises content based image retrieval criteria.

11. The method according to claim 10 wherein:

inputting a search string that comprises content base image retrieval criteria comprises;

inputting a search string that comprises one or more content based image retrieval criteria selected from the group consisting of;

color layout, dominant color, homogeneous texture, edge histogram, shape region, and shape contour.

12. The method according to claim 1 wherein

inputting a search string comprises:

inputting a search string that comprises a plurality of search string arguments including references to prior queries.

13. A method for searching a database of multimedia documents the method comprising, in a computer:

(a) inputting a search string that comprises a plurality of search string arguments comprising one or more key words, and one or more perceptual feature search specifications, wherein the plurality of search string arguments are connected by one or more search operators, and wherein at least one of the plurality of search string arguments is associated with a user specified confidence level;

(b) searching the database of multimedia documents using each of the search string arguments to obtain an answer set of multimedia documents for each of the search string arguments;

(c) for each ith record in the answer set of each mth search string argument among the plurality of search criteria arguments, computing a retrieval relevance value by a method that comprises mapping a distance measure corresponding to the mth search string argument and the ith record into a finite range;

for each ith record in the answer set of each mth search string argument including a perceptual feature search specification, computing a retrieval relevance value by evaluating a function of the following form;

RRV_i,m^C=(1−

H(G_F(X_i−

X_m)))^η

where,

RRVi,m^c is a retrieval relevance value of an ith media file to a mth search criteria basis media file based on a cth content based retrieval algorithm;

x_i is a quantitative characterization of the ith media file based on the cth content based retrieval algorithm;

x_m is a quantitative characterization of the mth search criteria basis media file based on the cth content based retrieval algorithm;

G_F is a distance function;

H is a mapping function that maps an argument into a finite range; and

η

is a constant exponent;

(d) for each answer set corresponding to a search string argument associated with a user specified confidence level, adjusting retrieval relevance values associated with multimedia documents in the answer set based on the confidence level;

(e) for each particular search operator performing an operation specified by the particular search operator on answer sets that are arguments of the particular search operator to form an answer set for the particular operator;

(f) for each multimedia document in the answer set for a particular operator, assigning a retrieval relevance to each multimedia document in the answer set for the particular operator that is derived from one or more retrieval relevance values associated with the multimedia document in answer sets that are arguments of the particular search operator; and

repeating steps (e)–

(f) until the search string is evaluated.

14. A method for searching a database comprising, in a computer:

inputting a search string that comprises a plurality of search string arguments connected by one or more search operators, and wherein at least one of the plurality of search string arguments is associated with a user specified confidence level;

searching the database using each particular search string argument to obtain an answer set of records for the particular search string argument;

for each ith record in the answer set of each mth search string argument among the plurality of search criteria arguments, computing a retrieval relevance value by evaluating a function of the following form;

RRV_i,m^C=(1−

H(G_F(X_i−

X_m)))^η

where,

RRVi,m^c is a retrieval relevance value of an ith record to a mth search criteria basis file based on a cth retrieval algorithm;

x_i is a quantitative characterization of the ith record based on the cth retrieval algorithm;

x_m is a quantitative characterization of the mth search criteria basis file based on the cth content based retrieval algorithm;

G_F is a distance function;

H is a mapping function that mans an argument into a finite range; and

η

is a constant exponent;

for each answer set corresponding to a search string argument that is associated with a user specified confidence level, adjusting retrieval relevance values associated with records in the answer set based on the confidence level;

for each kth particular search operator performing an operation specified by the kth particular search operator on answer sets associated with arguments of the kth particular search operator to form an answer set for the kth particular operator; and

for each nth record in the answer set for each kth particular operator, assigning a retrieval relevance value to the nth record in the answer set that is derived from one or more retrieval relevance values associated with the record in answer sets associated with arguments of the particular search operator.

15. A computer readable medium including programming instructions for searching a database including programming instructions for:

inputting a search string that comprises a plurality of search string arguments connected by one or more operators wherein each search string argument specifies a search criteria;

computing a distance measure between a quantitative characterizations corresponding to each of one or more of the search criteria, and quantitative characterizations of each of a plurality of records;

selecting records for inclusion in answer sets for each mth search criteria among the one or more search criteria based, at least in part, on a plurality of distance measures each involving a quantitative characterization corresponding to the mth search criteria, and a quantitative characterization corresponding to one of the plurality of records;

for each jth record in the answer set of each mth search criteria among the one or more search criteria, computing a retrieval relevance value by a method that comprises mapping a distance measure corresponding to the mth search criteria and the jth record into a finite range;

for each ith record in the answer set of an mth content based retrieval algorithm based query, computing a retrieval relevance value by evaluating a function of the following form;

RRV_i,m^C=(1−

H(G_F(X_i−

X_m)))^η

where,

RRVi,m^c is a retrieval relevance value of an ith media file to a mth search criteria basis media file based on a cth content based retrieval algorithm;

x_i is a quantitative characterization of the ith media file based on the cth content based retrieval algorithm;

x_m is a quantitative characterization of the mth search criteria basis media file based on the cth content based retrieval algorithm;

G_F is a distance function;

H is a mapping function that mans an argument into a finite range; and

η

is a constant exponent;

for each kth operator of the search string performing an operation specified by the kth operator on answer sets that are arguments of the kth operator to form a kth answer set for the kth operator; and

for each nth record in the kth answer set for each kth operator, assigning a retrieval relevance value to the nth record in the kth answer set, wherein the retrieval relevance value is a mathematical function of one or more quantitative characterizations associated with the nth record in answer sets that are arguments of the kth operator.

16. The computer readable medium according to claim 15 wherein

the programming instructions for selecting records for inclusion in answer sets for each mth search criteria comprise programming instructions for:

comparing the plurality of distance measures to one or more predetermined distance limits.

17. The computer readable medium according to claim 15 wherein:

the programming instructions for inputting a search string comprise programming instructions for;

inputting a search string that comprises one or more search string arguments that are associated with one or more user specified confidence levels; and

for each record in the answer set of each mth search criteria among the one or more search criteria, computing a retrieval relevance value comprises;

multiplying a value obtained by mapping, by a function of the user specified confidence level.

18. The computer readable medium according to claim 15 wherein the programming instructions for assigning a retrieval relevance value to the nth record in the kth answer set comprise programming instructions for:

assigning a retrieval relevance value to the nth record in the kth answer set that is derived from retrieval relevance values associated with the nth record in answer sets that are arguments of the kth operator.

19. The computer readable medium according to claim 18 wherein the programming instructions for:

inputting a search string comprises programming instructions for;

inputting a search string that comprises one or more Boolean AND operators;

the programming instructions for;

for each kth operator of the search string performing an operation specified by the kth operator comprise programming instructions for;

for each lth AND operator of the search string taking an intersection of answer sets that are arguments of the lth AND operator to form an answer set for the lth AND operator;

for each nth record in the answer set for each kth operator, assigning a retrieval relevance value to the nth record comprises;

for each mth record in the answer set for each lth AND operator, assigning a retrieval relevance value that is a minimum of one or more retrieval relevance values associated with the mth record in answer sets that are arguments of the lth AND operator.

20. The computer readable medium according to claim 18 wherein:

the programming instructions for inputting a search string comprise programming instructions for;

inputting a search string that comprises one or more Boolean OR operators;

the programming instructions for, for each kth operator of the search string performing an operation specified by the kth operator comprise programming instructions for;

for each lth OR operator of the search string taking a union of answer sets that are arguments of the lth OR operator to form an answer set for the lth OR operator;

for each nth record in the answer set for each kth operator, assigning a retrieval relevance value to the nth record comprises;

for each mth record in the answer set for each lth OR operator, assigning a retrieval relevance value that is a maximum of one or more relevance retrieval values associated with the mth record in answer sets that are arguments of the lth OR operator.