IMAGE RETRIEVAL USING SPATIAL BAG-OF-FEATURES

• US 20120269432A1
• Filed: 04/22/2011
• Published: 10/25/2012
• Est. Priority Date: 04/22/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Changhu, Li, Zhiwei, Zhang, Lei
• Granted Patent: US 8,849,030 B2
• Time in Patent Office: Days
• US Class Current: 382/171
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 10/507 Summing image-intensity values; Histogram projection analysis

Abstract

Local features of retrieved images are identified and for each image, an ordered bag-of-features is created that describes the features of the image. Spatial relationships between features of an image are captured in histogram descriptors created from linear or circular projections. Using the histogram descriptors, ordered bags-of-features describing the features of the images are developed. Calibrating the ordered bags-of-features to account for spatial variance leads to spatial bags-of-features.

Claims

1. A method comprising:

identifying features of an image;

projecting the features onto a line or a circle;

creating a histogram descriptor of the features based on the projecting; and

calibrating the histogram descriptor to minimize a variance between histogram descriptors of two images due to spatial variance of corresponding features between the two images.

2. A method as recited in claim 1, wherein the histogram descriptor of the features represents an ordered bag-of-features.

3. A method as recited in claim 2, wherein the ordered bag-of-features includes a representation of spatial relationships between the features.

4. A method as recited in claim 1, wherein projecting the features onto a line or a circle results in a series of bins of sub-histograms, each of the sub-histograms representing features within a particular area of the image.

5. A method as recited in claim 4, wherein a combination of the sub-histograms creates a long histogram that describes the image.

6. A method as recited in claim 5, further comprising decomposing the long histogram to eliminate particular features.

7. A method as recited in claim 1, wherein the spatial variance of features between the two images is a result of at least one of translation or rotation.

8. A method as recited in claim 1, wherein the spatial variance of features between the two images is a result of scaling.

9. A method comprising:

for each image of a plurality of images;

detecting local features of the image;

generating an ordered bag-of-features descriptor of the local features; and

calibrating the ordered bag-of-features descriptor to generate a spatial bag-of-features descriptor; and

building an index of the plurality of images based on the spatial bag-of-features descriptors.

10. A method as recited in claim 9, wherein the local features are represented by lines or circles.

11. A method as recited in claim 9, wherein generating the ordered bag-of-features descriptor of the local features comprises applying a linear projection to the local features.

12. A method as recited in claim 9, wherein generating the ordered bag-of-features descriptor of the local features comprises applying a circular projection to the local features.

13. A method as recited in claim 9, wherein calibrating the ordered bag-of-features descriptor comprises changing an order of the features represented in the ordered bag-of-features descriptor.

14. A method as recited in claim 9, wherein the ordered bag-of-features is a histogram, and calibrating the ordered bag-of-features descriptor comprises modifying a width of the histogram.

15. A method as recited in claim 9, wherein building the index includes:

compressing the images;

ranking the images; and

implementing an inverted file index.

16. A method as recited in claim 9, further comprising retrieving images that are indexed.

17. A computing device comprising:

a processor in communication with storage media;

an image crawling component maintained on the storage media and executed on the processor to retrieve multiple images from one or more databases; and

an indexing component maintained on the storage media and executed on the processor to;

identify features of the images;

project the features onto lines or circles based on linear or circular relationships;

create histogram descriptors of the features from the projecting; and

calibrate the histogram descriptors to account for spatial relationships between features of the multiple images.

18. A computing device as recited in claim 17, wherein the indexing component projects the features of a particular image as a series of sub-histograms, each sub-histogram representing features of the particular image, the sub-histograms being combined to create a long histogram that describe the particular image.

19. A computing device as recited in claim 18, wherein the indexing component is further executed on the processor to decompose the long histogram to eliminate particular ones of the features.

20. A computing device as recited in claim 17, wherein the indexing component is further executed on the processor to build an index that includes compressed and ranked images, and an inverted file index.