K-NEAREST NEIGHBOR RE-RANKING

• US 20130060766A1
• Filed: 07/18/2012
• Published: 03/07/2013
• Est. Priority Date: 09/02/2011
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Xiaohui Shen
• Inventors: Lin, Zhe, Brandt, Jonathan W., Shen, Xiaohui
• Granted Patent: US 8,983,940 B2
• Time in Patent Office: Days
• US Class Current: 707/723
• CPC Class Codes: G06F 16/51 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/58 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06F 16/5862 using texture
• CPC Class Codes: G06F 16/587 using geographical or spatial information, e.g. location
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06V 10/464 using a plurality of salient features, e.g. bag-of-words [BoW] representations
• CPC Class Codes: G06V 10/757 Matching configurations of points or features
• CPC Class Codes: G06V 10/758 Involving statistics of pixels or of feature values, e.g. histogram matching

Abstract

Methods, apparatus, and computer-readable storage media for k-NN re-ranking. Based on retrieved images and localized objects, a k-NN re-ranking method may use the k-nearest neighbors of a query to refine query results. Given the top k retrieved images and their localized objects, each k-NN object may be used as a query to perform a search. A database image may have different ranks when using those k-nearest neighbors as queries. Accordingly, a new score for each database image may be collaboratively determined by those ranks, and re-ranking may be performed using the new scores to improve the search results. The k-NN re-ranking technique may be performed two or more times, each time on a new set of k-nearest neighbors, to further refine the search results.

Claims

1. A method for object retrieval and localization, comprising:

performing, by one or more computing devices;

obtaining an initial ranking of a collection with regard to a query object;

generating a ranking of the collection with regard to each of one or more nearest neighbors to the query object as indicated by the initial ranking of the collection; and

generating a new ranking of the collection with regard to the query object according to the initial ranking and the generated rankings with regard to each of the one or more nearest neighbors.

2. The method as recited in claim 1, wherein the collection is a plurality of images, and wherein the initial ranking is a ranking of similarity of each of the plurality of images to a query image that includes the query object.

3. The method as recited in claim 1, wherein said generating a ranking of the collection with regard to each of one or more nearest neighbors to the query object as indicated by the initial ranking of the collection comprises:

for each of the one or more nearest neighbors, searching the collection according to a localized object of the respective nearest neighbor to determine similarity scores for the collection; and

ranking the collection according to the similarity scores.

4. The method as recited in claim 3, wherein features of the nearest neighbor that are outside the localized object are disregarded during said searching.

5. The method as recited in claim 1, wherein said generating a new ranking of the collection with regard to the query object according to the initial ranking and the generated rankings with regard to each of the one or more nearest neighbors comprises:

for each item in the collection, generating a score according to a weighted sum of the rankings; and

re-ranking the collection with regard to the query object according to the generated scores.

6. The method as recited in claim 5, wherein the weights are determined according to the initial ranking of the nearest neighbors with regard to the query object.

7. The method as recited in claim 1, further comprising repeating said generating a ranking of the collection with regard to each of one or more nearest neighbors to the query object as indicated by the initial ranking of the collection and said generating a new ranking of the collection with regard to the query object according to the initial ranking and the generated rankings with regard to each of the one or more nearest neighbors for one or more iterations, wherein the new ranking is used as the initial ranking in the subsequent iterations.

8. A system, comprising:

one or more processors; and

a memory comprising program instructions, wherein the program instructions are executable by at least one of the one or more processors to;

obtain an initial ranking of a collection with regard to a query object;

generate a ranking of the collection with regard to each of one or more nearest neighbors to the query object as indicated by the initial ranking of the collection; and

generate a new ranking of the collection with regard to the query object according to the initial ranking and the generated rankings with regard to each of the one or more nearest neighbors.

9. The system as recited in claim 8, wherein the collection is a plurality of images, and wherein the initial ranking is a ranking of similarity of each of the plurality of images to a query image that includes the query object.

10. The system as recited in claim 8, wherein, to generate a ranking of the collection with regard to each of one or more nearest neighbors to the query object as indicated by the initial ranking of the collection, the program instructions are executable by at least one of the one or more processors to:

for each of the one or more nearest neighbors, search the collection according to a localized object of the respective nearest neighbor to determine similarity scores for the collection; and

rank the collection according to the similarity scores.

11. The system as recited in claim 10, wherein the program instructions are executable by at least one of the one or more processors to disregard features of the nearest neighbor that are outside the localized object during said search.

12. The system as recited in claim 8, wherein, to generate a new ranking of the collection with regard to the query object according to the initial ranking and the generated rankings with regard to each of the one or more nearest neighbors, the program instructions are executable by at least one of the one or more processors to:

for each item in the collection, generate a score according to a weighted sum of the rankings, wherein the weights used in the weighted sum are determined according to the initial ranking of the nearest neighbors with regard to the query object; and

re-rank the collection with regard to the query object according to the generated scores.

13. The system as recited in claim 8, wherein the program instructions are executable by at least one of the one or more processors to repeat said generate a ranking of the collection with regard to each of one or more nearest neighbors to the query object as indicated by the initial ranking of the collection and said generate a new ranking of the collection with regard to the query object according to the initial ranking and the generated rankings with regard to each of the one or more nearest neighbors for one or more iterations, wherein the new ranking is used as the initial ranking in the subsequent iterations.

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

obtaining an initial ranking of a collection with regard to a query object;

generating a ranking of the collection with regard to each of one or more nearest neighbors to the query object as indicated by the initial ranking of the collection; and

generating a new ranking of the collection with regard to the query object according to the initial ranking and the generated rankings with regard to each of the one or more nearest neighbors.

15. The non-transitory computer-readable storage medium as recited in claim 14, wherein the collection is a plurality of images, and wherein the initial ranking is a ranking of similarity of each of the plurality of images to a query image that includes the query object.

16. The non-transitory computer-readable storage medium as recited in claim 14, wherein, in said generating a ranking of the collection with regard to each of one or more nearest neighbors to the query object as indicated by the initial ranking of the collection, the program instructions are computer-executable to implement:

for each of the one or more nearest neighbors, searching the collection according to a localized object of the respective nearest neighbor to determine similarity scores for the collection; and

ranking the collection according to the similarity scores.

17. The non-transitory computer-readable storage medium as recited in claim 16, wherein the program instructions are computer-executable to implement disregarding features of the nearest neighbor that are outside the localized object during said searching.

18. The non-transitory computer-readable storage medium as recited in claim 14, wherein, in said generating a new ranking of the collection with regard to the query object according to the initial ranking and the generated rankings with regard to each of the one or more nearest neighbors, the program instructions are computer-executable to implement:

for each item in the collection, generating a score according to a weighted sum of the rankings; and

re-ranking the collection with regard to the query object according to the generated scores.

19. The non-transitory computer-readable storage medium as recited in claim 18, wherein the weights are determined according to the initial ranking of the nearest neighbors with regard to the query object.

20. The non-transitory computer-readable storage medium as recited in claim 14, wherein the program instructions are further computer-executable to implement repeating said generating a ranking of the collection with regard to each of one or more nearest neighbors to the query object as indicated by the initial ranking of the collection and said generating a new ranking of the collection with regard to the query object according to the initial ranking and the generated rankings with regard to each of the one or more nearest neighbors for one or more iterations, wherein the new ranking is used as the initial ranking in the subsequent iterations.