Methods and Apparatus for Visual Search

• US 20130121600A1
• Filed: 03/29/2012
• Published: 05/16/2013
• Est. Priority Date: 09/17/2011
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Lin, Zhe, Brandt, Jonathan W.
• Granted Patent: US 8,781,255 B2
• Time in Patent Office: Days
• US Class Current: 382/224
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 16/5862 using texture
• CPC Class Codes: G06V 10/464 using a plurality of salient features, e.g. bag-of-words [BoW] representations

Abstract

Each image of a set of images is characterized with a set of sparse feature descriptors and a set of dense feature descriptors. In some embodiments, both the set of sparse feature descriptors and the set of dense feature descriptors are calculated based on a fixed rotation for computing texture descriptors, while color descriptors are rotation invariant. In some embodiments, the descriptors of both sparse and dense features are then quantized into visual words. Each database image is represented by a feature index including the visual words computed from both sparse and dense features. A query image is characterized with the visual words computed from both sparse and dense features of the query image. A rotated local Bag-of-Features (BoF) operation is performed upon a set of rotated query images against the set of database images. Each of the set of images is ranked based on the rotated local Bag-of-Features operation.

Claims

1. A method, the method comprising:

performing, using one or more processors

for each image of a set of images, characterizing the each image with

a set of sparse feature descriptors and

a set of dense feature descriptors, wherein both the set of sparse feature descriptors and the set of dense feature descriptors are calculated based on a fixed rotation;

indexing the set of images in a feature index comprising

the set of sparse feature descriptors for the each image of the set of images, and

the set of dense feature descriptors for the each image of the set of images;

characterizing a query image with

a set of sparse feature descriptors of the query image, and

a set of dense feature descriptors of the query image;

performing a rotated local Bag-of-Features (BoF) operation upon a set of rotated query images and the set of images; and

ranking each of the set of images based on the rotated local Bag-of-Features (BoF) operation.

2. The method of claim 1, wherein the characterizing the each image further comprises:

extracting from the each image of the set of images a set of sparse feature regions and a set of dense feature regions,

calculating a texture descriptor for each of the set of sparse feature regions and each of the set of dense feature regions, and

calculating a color descriptor for the each of the set of sparse feature regions and the each of the set of dense feature regions.

3. The method of claim 1, wherein the indexing the set of images comprises,

building based on a set of color descriptors a color index as an inverted file, and

separately building based on a set of fixed orientation texture descriptors a texture index as another inverted file.

4. The computer-implemented method of claim 1, wherein the characterizing the query image comprises

generating a set of rotated query images, wherein the set of rotated query images represents the query image as transformed through at a set of rotation angles,

calculating a set of fixed orientation texture descriptors of the query image from the set of rotated query images, and

calculating for the query image a color descriptor for the each of the set of sparse feature regions and a color descriptor for the each of the set of dense feature regions.

5. The method of claim 4, wherein

the method further comprises extracting from the query image a set of sparse feature regions of fixed orientation and a set of dense feature regions of fixed orientation, and

the calculating the set of fixed orientation texture descriptors of the query image further comprises calculating for the each of set of rotated query images

a set of texture descriptors for the each of the set of sparse feature regions and

a set of texture descriptors for the each of the set of dense feature regions.

6. The method of claim 1, wherein performing the rotated local BoF operation comprises

scoring, for each of the set of database images, one or more regions that have similarity to at least one of the rotated query images.

7. The method of claim 6, wherein the scoring comprises

taking a maximum of a set of similarity scores for respective ones a set of rotated query images with respect to the each of the set of images.

8. The method of claim 6, wherein

the scoring further comprises scoring based on a probability of spatial correspondence between features based on scale and translation.

9. A system, comprising:

at least one processor; and

a memory comprising program instructions, wherein the program instructions are executable by the at least one processor to;

for each image of a set of images, characterize the each image with

a set of sparse feature descriptors and

a set of dense feature descriptors, wherein both the set of sparse feature descriptors and the set of dense feature descriptors are calculated based on a fixed rotation;

index the set of images in a feature index comprising

the set of sparse feature descriptors for the each image of the set of images, and

the set of dense feature descriptors for the each image of the set of images;

characterize a query image with

a set of sparse feature descriptors of the query image, and

a set of dense feature descriptors of the query image;

perform a rotated local Bag-of-Features (BoF) operation upon a set of rotated query images and the set of images; and

rank each of the set of images in a ranking based on the rotated local Bag-of-Features (BoF) operation.

10. The system of claim 9, further comprising program instructions are executable by the at least one processor to:

iteratively refine said ranking based on user selection of images presented as results of said ranking.

11. The system of claim 9, wherein

for the each image of the set of images, a set of fixed orientation texture descriptors and the set of color descriptors characterize the set of dense feature descriptors and the set of sparse feature descriptors.

12. The system of claim 11, wherein

the program instructions executable by the at least one processor to index comprise program instructions executable by the at least one processor to encode spatial information in the set of color descriptors and the set of fixed-orientation texture descriptors.

13. The system of claim 12, wherein

the spatial information comprises scale and location information, and

the system further comprises program instructions executable by the at least one processor to determine differences between the position of a feature of the query image and a position of a corresponding feature in each of the set of images.

14. The system of claim 12,

wherein the program instructions executable by the at least one processor to perform the rotated local BoF operation comprise program instructions executable by the at least one processor to score, for each of the set of database images, one or more regions that have similarity to at least one of the rotated query images based on a user-weighted combination of color and texture.

15. A non-transitory computer-readable storage medium storing program instructions, wherein the program instructions are computer-executable to implement:

for each image of a set of images, characterizing the each image with

a set of sparse feature descriptors and

a set of dense feature descriptors, wherein both the set of sparse feature descriptors and the set of dense feature descriptors are calculated based on a fixed rotation;

indexing the set of images in a feature index comprising

the set of sparse feature descriptors for the each image of the set of images, and

the set of dense feature descriptors for the each image of the set of images;

characterizing a query image with

a set of sparse feature descriptors of the query image, and

a set of dense feature descriptors of the query image;

performing a rotated local Bag-of-Features (BoF) operation upon a set of rotated query images and the set of images; and

ranking each of the set of images based on the rotated local Bag-of-Features (BoF) operation.

16. The non-transitory computer-readable storage medium of claim 15, wherein the program instructions computer-executable to implement characterizing the each image further comprise program instructions computer-executable to implement:

extracting from the each image of the set of images a set of sparse feature regions and a set of dense feature regions,

calculating a texture descriptor for each of the set of sparse feature regions and each of the set of dense feature regions, and

calculating a color descriptor for the each of the set of sparse feature regions and the each of the set of dense feature regions.

17. The non-transitory computer-readable storage medium of claim 15, wherein the program instructions computer-executable to implement indexing the set of images comprise program instructions computer-executable to implement:

building based on a set of color descriptors a color index as an inverted file, and

separately building based on a set of fixed orientation texture descriptors a texture index as another inverted file.

18. The non-transitory computer-readable storage medium of claim 15, wherein the program instructions computer-executable to implement characterizing the query image comprise program instructions computer-executable to implement:

generating a set of rotated query images, wherein the set of rotated query images represents the query image as transformed through at a set of rotation angles,

calculating a set of fixed orientation texture descriptors of the query image from the set of rotated query images, and

calculating for the query image a color descriptor for the each of the set of sparse feature regions and a color descriptor for the each of the set of dense feature regions.

19. The non-transitory computer-readable storage medium of claim 18, wherein

the program instructions computer-executable to implement calculating the set of fixed orientation texture descriptors of the query image further comprise program instructions computer-executable to implement calculating for the each of set of rotated query images

a set of texture descriptors for the each of the set of sparse feature regions and

a set of texture descriptors for the each of the set of dense feature regions.

20. The non-transitory computer-readable storage medium of claim 15, wherein the program instructions computer-executable to implement performing the rotated local BoF operation comprise program instructions computer-executable to implement:

scoring, for each of the set of database images, one or more regions that have similarity to at least one of the rotated query images.