Hierarchical sparse representation for image retrieval

• US 8,463,045 B2
• Filed: 11/10/2010
• Issued: 06/11/2013
• Est. Priority Date: 11/10/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Yang, Linjun, Tian, Qi, Ni, Bingbing
• Primary Examiner(s): PATEL, KANJIBHAI B
• Application Number:
  US12/943,805
• Publication Number:
  US 20120114248A1
• Time in Patent Office: 944 Days
• Field of Search: 382/159, 382/181, 382/190, 382/232, 382/240, 382/248, 382/276, 382/305, 382/312, 375/240.18, 375/240.19, 358/1.16, 358/522
• US Class Current: 382/190
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 16/5854 using shape and object relationship

Abstract

A hierarchical sparse codebook allows efficient search and comparison of images in image retrieval. The hierarchical sparse codebook includes multiple levels and allows a gradual determination/classification of an image feature of an image into one or more groups or nodes by traversing the image feature through one or more paths to the one or more groups or nodes of the codebook. The image feature is compared with a subset of nodes at each level of the codebook, thereby reducing processing time.

Claims

1. One or more memory storage devices storing computer-executable instructions that, when executed by one or more processors, cause the one or more processors to perform acts comprising:

receiving a plurality of training image features; and

generating a hierarchical sparse codebook based at least upon the plurality of training image features, the generating comprising creating a plurality of levels for the hierarchical sparse codebook, each level being associated with a respective sparseness factor.

2. The one or more memory storage devices as recited in claim 1, wherein the generating further comprises adjusting the respective sparseness factor of each level to obtain a degree of sparseness which is less than a predetermined threshold or within a predetermined range.

3. The one or more memory storage devices as recited in claim 1, wherein the generating further comprises adjusting the respective sparseness factor of each level to obtain an overall degree of sparseness for the hierarchical sparse codebook, which is less than a predetermined threshold or within a predetermined range, the overall degree of sparseness.

4. The one or more memory storage devices as recited in claim 1, wherein the generating further comprises assigning an image feature set to a node of a level of the plurality of levels, the image feature set comprising a subset of the plurality of training image features.

5. The one or more memory storage devices as recited in claim 4, wherein the assigning comprises assigning a training image feature of the plurality of training image features to the node if a degree of overlap between the training image feature and a nodal feature of the node is greater than or equal to a predetermined threshold.

6. The one or more memory storage devices as recited in claim 1, wherein the plurality of levels comprises at least a root level, a first level and a second level.

7. The one or more memory storage devices as recited in claim 6, wherein the generating further comprises:

creating a first number of nodes at the first level, the first number of nodes comprising a first number of first-level nodal features;

adjusting the first number of first-level nodal features to minimize a cost of a first cost function based at least upon the plurality of training image features, the first cost function comprising a first sparseness function to control a degree of sparseness associated with representations of the plurality of training image features at the first level; and

for each of the first number of nodes at the first level, assigning a first-level nodal feature set based at least upon the plurality of training image features and an assignment scheme.

8. The one or more memory storage devices as recited in claim 7, wherein the generating further comprises:

for each of the first number of nodes at the first level,

generating a second number of nodes at the second level, the second number of nodes comprising a second number of second-level nodal features,

adjusting the second number of second-level nodal features to minimize a cost of a second cost function based at least upon the respective first-level nodal feature set, the second cost function comprising a second sparseness function to control a degree of sparseness associated with representations of the plurality of training image features at the second level; and

for each of the second number of nodes at the second level, assigning a second-level nodal feature set based at least upon the respective first-level nodal feature set and the assignment scheme.

9. The one or more memory storage devices as recited in claim 8, wherein the assignment scheme comprises a predetermined threshold, and wherein assigning the first-level nodal feature or assigning the second-level nodal feature comprises assigning a training image feature to a node if a degree of overlap between the training image feature and a nodal feature associated with the node is greater than or equal to the predetermined threshold.

10. The one or more memory storage devices as recited in claim 1, further comprising:

receiving an image query comprising an example image from a user;

extracting one or more image features from the example image;

comparing each of the one or more image features with the hierarchical sparse codebook to obtain one or more leaf-level features of the codebook;

generating a histogram for the example image based on the one or more leaf-level features of each of the one or more image features from the example image;

retrieving one or more database images based at least upon the histogram; and

presenting the one or more database images to the user.

11. The one or more memory storage devices as recited in claim 10, wherein the retrieving comprises:

computing correlations between the histogram of the example image with histograms of a subset of database images stored in a database; and

retrieving the one or more database images that have corresponding correlations greater than a predetermined correlation threshold.

12. A computer-implemented method for generating a hierarchical sparse codebook, the method comprising:

receiving a plurality of training image features; and

generating a hierarchical sparse codebook based at least upon the plurality of training image features, the generating comprising encoding each training image feature using a sparse number of nodal features that are associated with leaf nodes of the hierarchical sparse codebook.

13. The computer-implemented method as recited in claim 12, wherein the generating further comprises:

generating a plurality of levels for the hierarchical sparse codebook, each level comprising a predetermined number of nodes;

associating each node of each level with a nodal feature;

adjusting each nodal feature of each node to minimize a cost of a cost function of the respective level based at least upon an image feature set of a parent node of the respective node; and

assigning, to each node, a subset of the image feature set of the respective parent node.

14. The computer-implemented method as recited in claim 13, wherein the cost function of each level comprises a sparseness function defining a degree of sparseness of representation of each training image feature at the respective node level.

15. The computer-implemented method as recited in claim 13, wherein the assigning comprises:

for each node, obtaining a degree of overlap between the respective nodal feature and an image feature of the image feature set of the respective parent node;

assigning, to the respective node, the image feature of the image feature set of respective parent node if the degree of overlap is greater than a predetermined threshold.

16. The computer-implemented method as recited in claim 12, further comprising:

receiving an image query comprising an example image from a user;

extracting one or more image features from the example image;

comparing each of the one or more image features with the hierarchical sparse codebook to obtain one or more leaf-level features of the codebook;

generating a histogram for the example image based on the one or more leaf-level features of each of the one or more image features from the example image;

retrieving one or more database images based at least upon the histogram; and

presenting the one or more database images to the user.

17. The computer-implemented method as recited in claim 16, wherein the retrieving comprises:

computing correlations between the histogram of the example image with histograms of a subset of database images stored in a database; and

retrieving the one or more database images that have corresponding correlations greater than a predetermined correlation threshold.

18. A computer-implemented method comprising:

receiving an image;

extracting a plurality of image features from the image;

comparing each image feature with a hierarchical sparse codebook to obtain one or more leaf-level features of the codebook, the one or more leaf-level features representing a sparse code representation of the respective image feature;

generating a histogram for the image based at least upon the one or more leaf-level features of each image feature of the image; and

representing the image by the histogram.

19. The computer-implemented method as recited in claim 18, further comprising:

generating an index for the image based at least upon the histogram; and

storing the index and the image in a database.

20. The computer-implemented method as recited in claim 18, wherein the image comprises an example image received from a user for image query, and wherein the method further comprises:

retrieving one or more database images based at least upon the histogram; and

presenting the one or more database images to the user.