Statistical bigram correlation model for image retrieval

• US 7,430,566 B2
• Filed: 02/11/2005
• Issued: 09/30/2008
• Est. Priority Date: 02/11/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Mingjing, Chen, Zheng, Zhang, Hong-Jiang, Wenyin, Liu
• Primary Examiner(s): TRUONG, CAM Y T
• Application Number:
  US11/056,555
• Publication Number:
  US 20050165763A1
• Time in Patent Office: 1,327 Days
• Field of Search: None
• 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;

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

estimating, via the statistical bigram correlation model, a respective semantic correlation between each image 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 said each image of the pair is indicated to be a semantically relevant image, said each respective bigram frequency representing a probability of whether two images that are semantically related to one-another based on a co-occurrence frequency, each image of the two images was relevant in a previous query/feedback session,

wherein the estimating the respective semantic correlation further comprises;

associating a respective unigram frequency with each respective image of the images, the respective unigram frequency indicating that said 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 respective multiple search sessions, wherein the respective semantic correlation is further based on the maximum frequency; and

displaying, responsive to a user operation in an image retrieval session, one or more ranked images to a user based on the respective semantic correlation.

2. The 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 an image; and

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

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

6. The 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 or the respective semantic correlation, the similarity measure corresponding to a similarity of a respective feature vector of an image and a search query corresponding to the session;

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

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

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

0≦

R(I,J)≦

1

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

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.

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

9. The 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 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.

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

11. The method as recited in claim 1, wherein each respective bigram frequency is based on a pair of unigram frequencies, 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.

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

receiving a plurality of images responsive to multiple image retrieval search sessions;

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

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

estimating, via the statistical bigram correlation model, a respective semantic correlation between each image 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 said each image of the pair is indicated to be a semantically relevant image, said each respective bigram frequency representing a probability of whether two images that are semantically related to one-another based on a co-occurrence frequency, each image of the two images was relevant in a previous query/feedback session,

wherein the estimating the respective semantic correlation further comprises;

associating a respective unigram frequency with each respective image of the images, the respective unigram frequency indicating that said 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 respective multiple search sessions, wherein the respective semantic correlation is further based on the maximum frequency; and

displaying, responsive to a user operation in an image retrieval session, one or more ranked images to a user based on the respective semantic correlation.

13. The computer-readable storage medium of claim 12, 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.

14. The computer-readable storage medium of claim 12, 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).

15. 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 image retrieval search sessions;

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

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

estimating, via the statistical bigram correlation model, a respective semantic correlation between each image 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 said each image of the pair is indicated to be a semantically relevant image, said each respective bigram frequency representing a probability of whether two images that are semantically related to one-another based on a co-occurrence frequency, each image of the two images was relevant in a previous query/feedback session,

wherein the estimating the respective semantic correlation further comprises;

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

displaying, responsive to a user operation in an image retrieval session, one or more ranked images to a user based on the respective semantic correlation.