Statistical bigram correlation model for image retrieval

• US 20050165763A1
• Filed: 02/11/2005
• Published: 07/28/2005
• Est. Priority Date: 02/11/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Mingjing, Chen, Zheng, Zhang, Hong-Jiang, Wenyin, Liu
• Granted Patent: US 7,430,566 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• 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

The disclosed subject matter improves iterative results of content-based image retrieval (CBIR) using a bigram model to correlate relevance feedback. Specifically, multiple images are received responsive to multiple image search sessions. Relevance feedback is used to determine whether the received images are semantically relevant. A respective semantic correlation between each of at least one pair of the images is then estimated using respective bigram frequencies. The bigram frequencies are based on multiple search sessions in which each image of a pair of images is semantically relevant.

Claims

1. A computer-implemented method for image retrieval using a statistical bigram correlation model, the method comprising:

receiving a plurality of images responsive to multiple search sessions;

determining whether the images are semantically relevant images via relevance feedback; and

estimating a respective semantic correlation between each of at least one pair of the images with a respective bigram frequency, each respective bigram frequency being based on multiple search sessions in which each image of the pair is indicated to be a semantically relevant image.

2. A method as recited in claim 1, further comprising:

assigning a respective ranking score to each of the images based at least in part on the respective semantic correlation corresponding to the image; and

displaying only those images with a highest range of ranking scores.

3. A method as recited in claim 1, further comprising, responsive to a search session, dynamically updating the respective bigram frequency corresponding to two of the images.

4. A method as recited in claim 1, wherein the respective semantic correlation is:

(a) a positive correlation between two semantically relevant images;

(b) a negative correlation between a semantically relevant image and a semantically irrelevant image; and

(c) no correlation otherwise.

5. A method as recited in claim 1:

wherein the respective semantic correlation is performed offline or online to calculate unigram and bigram frequencies from relevance feedback information, the unigram frequency being based on relevance feedback to a session of the multiple search sessions, the unigram frequency indicating that each respective image of the images is either semantically relevant to the session, semantically less relevant to the session, or a non-feedback image with respect to the session; and

wherein each respective bigram frequency is based on a pair of unigram frequencies.

6. A method as recited in claim 1, wherein estimating the respective semantic correlation further comprises:

associating a respective unigram frequency with each of the images, the unigram frequency indicating that each respective image of the images is either semantically relevant, semantically less relevant, or a non-feedback image, the unigram frequency being based on relevance feedback to a session of the multiple search sessions; and

wherein each respective bigram frequency is based on a pair of unigram frequencies.

7. A method as recited in claim 1, wherein estimating the respective semantic correlation further comprises:

associating a respective unigram frequency with each of the images, the unigram frequency indicating that each respective image of the images is either semantically relevant, semantically less relevant, or a non-feedback image, the unigram frequency being based on relevance feedback to a session of the multiple search sessions;

determining a maximum frequency from a maximum value of the bigram and unigram frequencies; and

wherein the respective semantic correlation is further based on the maximum frequency.

8. A method as recited in claim 1, further comprising identifying, for each image obtained responsive to one or more search sessions of the multiple search sessions, a respective semantic support based on a similarity measure and/or the respective semantic correlation, the similarity measure corresponding to a similarity of a respective feature vector of the image and a search query corresponding to the session.

9. A method as recited in claim 1, further comprising:

identifying, for each image obtained responsive to one or more search sessions of the multiple search sessions, a respective semantic support based on a similarity measure and/or the respective semantic correlation, the similarity measure corresponding to a similarity of a respective feature vector of the image and a search query corresponding to the session;

assigning a respective ranking score to each of the images based upon the respective similarity measure, the respective semantic support, and a semantic weight; and

displaying only those images with a highest range of respective ranking scores.

10. A method as recited in claim 1, wherein estimating the respective semantic correlation is determined as follows:

0≦

R(I,J)≦

1 [if is true in all cases]

R(I,J)=R(J,I);

[if is true in all cases]

if I=J and U(I)≦

0;

R(I,J)=0;

if I≠

J and B(I,J)≦

0;

R(I,J)=0

if I=J and U(I)>

0;

R(I,J)=U(I) T;

or

if I≠

J and B(I,J)>

0;

R(I,J)=B(I)/T;

wherein I,J are two images, B(I,J) is their bigram frequency, U(I) is the unigram frequency of image I,T is the maximum frequency, R(I,J) is the correlation between image I and J.

11. A method as recited in claim 1, wherein each respective bigram frequency is based on a pair of unigram frequencies, and wherein the method further comprises performing the respective semantic correlation offline by:

(a) initializing all unigram and bigram frequencies to zero;

(b) clustering search sessions with a same query into groups;

(c) calculating unigram counts within a group;

(d) updating unigram frequencies;

(e) updating bigram frequencies;

(f) repeating operations (c), (d), and (f) for all session groups;

(g) setting all negative unigram and bigram frequencies to zero; and

(h) calculating each respective semantic correlation based on results of (a) through (f).

12. A method as recited in claim 1, wherein each respective bigram frequency is based on a pair of unigram frequencies, wherein C(I) is a unigram count of image I, and wherein the method further comprises performing the respective semantic correlation offline by:

(a) initializing C(I) to zero (0);

(b) iteratively updating C(I) for every session in a group such that;

C(I)=C(I)+1, if image I is labeled as relevant in a session;

C(I)=C(I)−

1, if image I is labeled as irrelevant in a session; and

C(I) is unchanged otherwise.

(c) repeating (b) for every image of the images;

(d) updating each respective unigram frequencies as U(I)=U(I)+C(I);

(e) updating each respective bigram frequency of an image pair such that;

B(I,J)=B(I,J)+min{C(I),C(J)}, if C(I)>

0,C(J)>

0,

B(I,J)=B(I,J)−

min{C(I),−

C(J)}, if C(I)>

0,C(J)<

0,

B(I,J)=B(I,J)−

min{−

C(I),C(J)}, if C(I)<

0,C(J)>

0, and

B(I,J)=B(I,J), otherwise; and

wherein I,J are two images, B (I,J) is their bigram frequency, and U (I) is the unigram frequency of image I.

13. A method as recited in claim 1, wherein each respective bigram frequency is based on a pair of unigram frequencies, and wherein the method further comprises performing the respective semantic correlation online by:

(a) calculating unigram counts in a particular search session;

(b) updating unigram frequencies;

(c) updating bigram frequencies; and

(d) updating each respective semantic correlation between each of the images based on results of (a) through (c).

14. A method as recited in claim 1, wherein each respective bigram frequency is based on a pair of unigram frequencies, wherein C(I) is a unigram count of image I, wherein U(I) is a unigram frequency of image I, wherein B(I,J) is a bigram frequency of image I and J, wherein a session group comprises a single search session, and wherein the method further comprises performing the respective semantic correlation online by:

(a) responsive to determining that there is a user log, updating calculating each respective unigram and bigram frequency according to data in the user log;

(b) responsive to determining that there is not a user log, initializing each C(I) and B(I) to zero (0);

(c) iteratively updating C(I) for the single search session such that;

C(I)=1, if image I is labeled as relevant;

C(I)=−

1, if image I is labeled as irrelevant; and

C(I)=0, if C(I) is a non-feedback image;

(d) updating each respective unigram frequencies as U(I)=U(I)+C(I);

(e) updating each respective bigram frequency of an image pair such that;

B(I,J)=B(I,J)+1, if C(I)>

0,C(J)>

0,

B(I,J)=B(I,J)−

1, if C(I)>

0,C(J)<

0,

B(I,J)=B(I,J)−

1, if C(I)<

0,C(J)>

0, or

B(I,J)=B(I,J), otherwise; and

wherein I,J are two images, and B(I,J) is their bigram frequency.

15. A computer-readable medium for image retrieval using a statistical bigram correlation model, the computer-readable medium comprising computer-executable instructions for:

receiving a plurality of images responsive to multiple search sessions;

determining whether the images are semantically relevant images via relevance feedback; and

estimating a respective semantic correlation between each of at least one pair of the images with a respective bigram frequency, each respective bigram frequency representing a probability of whether two of the images are semantically related to one-another based on a co-occurrence frequency that each image of the two images was relevant in a previous query/feedback session.

16. A computer-readable medium as recited in claim 15, wherein the respective semantic correlation is:

(a) a positive correlation between two semantically relevant images;

(b) a negative correlation between a semantically relevant image and a semantically irrelevant image; and

(c) no correlation otherwise.

17. A computer-readable medium as recited in claim 15:

wherein the respective semantic correlation is performed offline or online to calculate unigram and bigram frequencies from relevance feedback information, the unigram frequency being based on relevance feedback to a session of the multiple search sessions, the unigram frequency indicating that each respective image of the images is either semantically relevant to the session, semantically less relevant to the session, or a non-feedback image with respect to the session; and

wherein each respective bigram frequency is based on a pair of unigram frequencies.

18. A computer-readable medium as recited in claim 15, wherein each respective bigram frequency is based on a pair of unigram frequencies, and wherein the computer-executable instructions further comprise instructions for performing the respective semantic correlation offline by:

(a) initializing all unigram and bigram frequencies to zero;

(b) clustering search sessions with a same query into groups;

(c) calculating unigram counts within a group;

(d) updating unigram frequencies;

(e) updating bigram frequencies;

(f) repeating operations (c), (d), and (f) for all session groups;

(g) setting all negative unigram and bigram frequencies to zero; and

(h) calculating each respective semantic correlation based on results of (a) through (f).

19. A computing device for image retrieval using a statistical bigram correlation model, the computing device comprising:

a processor; and

a memory coupled to the processor, the memory comprising computer-executable instructions that are fetched and executed by the processor for;

receiving a plurality of images responsive to multiple search sessions;

determining whether the images are semantically relevant images via relevance feedback; and

estimating a respective semantic correlation between each of at least one pair of the images with a respective bigram frequency, each respective bigram frequency being based on multiple search sessions in which each image of the pair is indicated to be a semantically relevant image.

20. A computing device as recited in claim 19:

wherein the respective semantic correlation is performed offline or online to calculate unigram and bigram frequencies from relevance feedback information, the unigram frequency being based on relevance feedback to a session of the multiple search sessions, the unigram frequency indicating that each respective image of the images is either semantically relevant to the session, semantically less relevant to the session, or a non-feedback image with respect to the session; and

wherein each respective bigram frequency is based on a pair of unigram frequencies.