Generating search requests from multimodal queries

• US 8,081,824 B2
• Filed: 10/08/2008
• Issued: 12/20/2011
• Est. Priority Date: 09/21/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Ming Jing, Ma, Wei-Ying, Xie, Xing, Fan, Xin, Li, Zhiwei
• Primary Examiner(s): Bella, Matthew
• Assistant Examiner(s): Rosario, Dennis
• Application Number:
  US12/247,958
• Publication Number:
  US 20090041366A1
• Time in Patent Office: 1,168 Days
• Field of Search: 382/190
• US Class Current: 382/190
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• 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 method and system for generating a search request from a multimodal query that includes a query image and query text is provided. The multimodal query system identifies images of a collection that are textually related to the query image based on similarity between words associated with each image and the query text. The multimodal query system then selects those images of the identified images that are visually related to the query image. The multimodal query system may formulate a search request based on keywords of web pages that contain the selected images and submit that search request to a search engine service.

Claims

1. A method in a computing device for generating a compact representation of an image, the method comprising:

for each of a plurality of blocks of pixels of the image, calculating for the block a representative intensity level derived from intensities of the pixels of the block;

performing a discrete transform on the representative intensity levels for the blocks to generate transformed coefficients;

applying a principal component analysis to the transformed coefficients to generate PCA coefficients of a reduced dimensionality; and

setting each bit of a vector with an element corresponding to a PCA coefficient based on the value of the PCA coefficient

wherein the bits represent the compact representation of the image.

2. The method of claim 1 wherein the compact representation is a signature of the image.

3. The method of claim 2 including identifying images that are duplicates of a target image by comparing signatures of the images to the signature of the target image.

4. The method of claim 1 wherein the calculating of the representative intensity levels includes setting the pixels of the images to a grey scale and wherein the representative intensity level is an average intensity level for the pixels of a block.

5. The method of claim 1 wherein the transform is a discrete cosine transform and the transformed coefficients do not include a DC coefficient.

6. The method of claim 5 wherein the transformed coefficients are selected in a zigzag pattern.

7. The method of claim 1 wherein the calculating of the representative intensity levels includes setting the pixels of the images to a grey scale and wherein the representative intensity level is an average intensity level for the pixels of a block, wherein the discrete transform is a discrete cosine transform and the transformed coefficients are AC coefficients selected in a zigzag pattern, and wherein the bits are set based on whether the PCA coefficients are greater than or less than zero.

8. The method of claim 7 wherein the blocks include 64 pixels, wherein 48 AC coefficients are selected, and wherein the reduce dimensionality is 32.

9. A computer-readable storage device containing computer-executable instructions for controlling a computing device to generate a compact representation of an image, by a method comprising:

for each of a plurality of blocks of pixels of the image, calculating for the block a representative intensity level derived from intensities of the pixels of the block;

performing a discrete transform on the representative intensity levels for the blocks to generate transformed coefficients;

applying a principal component analysis to the transformed coefficients to generate PCA coefficients of a reduced dimensionality; and

setting each bit of a vector with an element corresponding to a PCA coefficient based on the value of the PCA coefficient

wherein the bits represent the compact representation of the image.

10. The computer-readable storage device of claim 9 wherein the compact representation is a signature of the image.

11. The computer-readable storage device of claim 10 including identifying images that are duplicates of a target image by comparing signatures of the images to the signature of the target image.

12. The computer-readable storage device of claim 9 wherein the calculating of the representative intensity levels includes setting the pixels of the images to a grey scale and wherein the representative intensity level is an average intensity level for the pixels of a block.

13. The computer-readable storage device of claim 9 wherein the transform is a discrete cosine transform and the transformed coefficients do not include a DC coefficient.

14. The computer-readable storage device of claim 13 wherein the transformed coefficients are selected in a zigzag pattern.

15. The computer-readable storage device of claim 9 wherein the calculating of the representative intensity levels includes setting the pixels of the images to a grey scale and wherein the representative intensity level is an average intensity level for the pixels of a block, wherein the discrete transform is a discrete cosine transform and the transformed coefficients are AC coefficients selected in a zigzag pattern, and wherein the bits are set based on whether the PCA coefficients are greater than or less than zero.

16. The computer-readable storage device of claim 15 wherein the blocks include 64 pixels, wherein 48 AC coefficients are selected, and wherein the reduce dimensionality is 32.