SYSTEMS AND METHODS FOR MOBILE SEARCH USING BAG OF HASH BITS AND BOUNDARY RERANKING

• US 20130254191A1
• Filed: 12/06/2012
• Published: 09/26/2013
• Est. Priority Date: 12/06/2011
• Status: Active Grant

• Current Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Original Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: He, Junfeng, Chang, Shih-Fu, Lin, Tai-Hsu
• Granted Patent: US 9,009,149 B2
• Time in Patent Office: Days
• US Class Current: 707/728
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06V 10/464 using a plurality of salient features, e.g. bag-of-words [BoW] representations

Abstract

Determining ranked candidate media in response to media query data corresponding to a query media includes receiving the media query data including feature data of the query media, coordinate data, and boundary data, matching the features with corresponding features of an media database using the feature data to identify features in the media database within a predetermined hamming distance in a hash table from the corresponding features of the query media to obtain matched features in the media database, determining candidate media whose number of matched features exceeds a matched feature threshold, generating a geometry similarity score between the query media and each candidate media using the feature data and the coordinate data, generating a boundary similarity score between the query media and each candidate media using the boundary data, ranking the candidate media based on the numbers of matched features, the geometry similarity scores and the boundary similarity scores.

Claims

1. A method for determining one or more ranked candidate media in response to media query data generated at a mobile client device corresponding to a query media, comprising:

receiving the media query data from the mobile client device, the media query data comprising feature data of one or more features of the query media encoded by one or more similarity preserving hashing functions and coordinate data for each of the one or more features;

matching, on a server computer system, the one or more of the features of the query media with one or more corresponding features of a media database using the feature data of the query media to identify one or more features of the media database within a predetermined hamming distance in one or more hash tables from the one or more corresponding features of the query media to obtain one or more matched features in the media database;

determining, on the server computer system, one or more candidate media whose number of matched features exceeds a matched feature threshold;

generating, on the server computer system, a geometry similarity score between the query media and each of the one or more candidate media using the feature data and the coordinate data;

ranking, on the server computer system, the one or more candidate media based on the numbers of matched features and the geometry similarity score; and

sending the ranked candidate media to the mobile client device.

2. The method of claim 1, wherein the media query data further comprises boundary data, the method further comprising generating, on the server computer system, a boundary similarity score between the query media and each of the one or more candidate media using the boundary data, and ranking the one or more candidate media is further based on the boundary similarity score.

3. The method of claim 1, wherein the query media comprises a query image.

4. The method of claim 1, wherein the similarity preserving hashing function comprises a linear hashing function.

5. The method of claim 1, wherein the similarity preserving hashing function comprises a nonlinear hashing function.

6. The method of claim 1, wherein the feature data comprises a plurality of hash bits for each feature encoded by the one or more hash functions.

7. The method of claim 6, wherein the plurality of hash bits is limited to less than 100 bits.

8. The method of claim 6, wherein the one or more hash tables comprises a plurality of entries, the features of the query media and the features of the media database each being assigned to one of the plurality of entries using the plurality of hash bits as table indexes, and matching the one or more features comprises identifying table entries within the predetermined hamming distance from the entries containing the features of the query media.

9. The method of claim 6, further comprising:

obtaining a plurality of subgroups of the plurality hash bits of each feature data,

utilizing each of the plurality of subgroups to create the one or more hash tables, and

assigning the feature data to an entry of a corresponding hash table.

10. The method of claim 1, wherein generating the geometry similarity score comprises determining a length ratio between the one or more features of the query media and corresponding matched features of the candidate media using the coordinate data.

11. The method of claim 1, wherein generating the boundary similarity score comprises:

for each media of the query media and the candidate media,

sampling a plurality of points along the boundary of the media,

determining a distance between each sampled point and the center of the media to obtain boundary distance data, and

applying a Fourier transform to the boundary distance data to obtain frequency magnitudes; and

comparing the frequency magnitudes of the query media with the frequency magnitudes of the candidate media.

12. The method of claim 1, wherein ranking the one or more candidate media comprises:

ranking the candidate media by the number of matched features,

for each of the one or more candidate media, combining the geometry similarity score and the boundary similarity score, and

reranking the candidate media using the combined score.

13. One or more computing devices associated with a server computing system for determining one or more ranked candidate media in response to media query data generated at a mobile client device corresponding to a query media, the computing devices comprising:

one or more processors; and

one or more computer-readable non-transitory storage media embodying software that is configured when executed by one or more of the processors to;

receive the media query data from the mobile device, the media query data comprising feature data of one or more features of a query media encoded by a similarity preserving hashing function and coordinate data for each of the one or more features;

match the one or more of the features with one or more corresponding features of an media database using the feature data to identify one or more features of the query media within a predetermined hamming distance in a hash table from the one or more corresponding features of the media database to obtain one or more matched features in the media database;

determine one or more candidate media whose number of matched features exceed a matched feature threshold;

generate a geometry similarity score between the query media and each of the one or more candidate media using the feature data and the coordinate data;

rank the one or more candidate media based on the numbers of matched features and the geometry similarity score; and

send the ranked candidate media to the mobile client device.

14. The computing devices of claim 13, wherein the media query data further comprises boundary data, the software being further configured to generate a boundary similarity score between the query media and each of the one or more candidate media using the boundary data, and the one or more candidate media is ranked further based on the boundary similarity score.

15. The computing devices of claim 13, wherein the query media comprises a query image.

16. The computing devices of claim 13, wherein the similarity preserving hashing function comprises a linear hashing function.

17. The computing devices of claim 13, wherein the similarity preserving hashing function comprises a nonlinear hashing function.

18. The computing devices of claim 13, wherein the feature data comprises a plurality of hash bits for each feature encoded by the one or more hash functions.

19. The computing devices of claim 18, wherein the plurality of hash bits is limited to less than 100 bits.

20. The computing devices of claim 18, wherein the one or more hash tables comprises a plurality of entries, the features of the query media and the features of the media database each being assigned to one of the plurality of entries using the plurality of hash bits as table indexes, and matching the one or more features comprises identifying table entries within the predetermined hamming distance from the entries containing the features of the query media.

21. The computing devices of claim 18, wherein the software is further configured to:

obtain a plurality of subgroups of the plurality hash bits of each feature data,

utilize each of the plurality of subgroups to create the one or more hash tables, and

assign the feature data to an entry of a corresponding hash table.

22. The computing devices of claim 13, wherein the software is further configured to generate the geometry similarity score by determining a length ratio between the one or more features of the query media and corresponding matched features of the candidate media using the coordinate data.

23. The computing devices of claim 13, wherein the software is further configured to generate the boundary similarity score by:

for each media of the query media and the candidate media,

sampling a plurality of points along the boundary of the media,

determining a distance between each sampled point and the center of the media to obtain boundary distance data, and

applying a Fourier transform to the boundary distance data to obtain frequency magnitudes; and

comparing the frequency magnitudes of the query media with the frequency magnitudes of the candidate media.

24. The computing devices of claim 13, wherein the software is further configured to rank the one or more candidate media by:

ranking the candidate media by the number of matched features,

for each of the one or more candidate media, combining the geometry similarity score and the boundary similarity score, and

reranking the candidate media using the combined score.

25. One or more computer-readable non-transitory storage media embodying software for determining one or more ranked candidate media in response to media query data generated at a mobile client device corresponding to a query media that is configured when executed to:

receive the media query data from the mobile device, the media query data comprising feature data of one or more features of a query media encoded by a similarity preserving hashing function and coordinate data for each of the one or more features;

match the one or more of the features with one or more corresponding features of an media database using the feature data to identify one or more features of the query media within a predetermined hamming distance in a hash table from the one or more corresponding features of the media database to obtain one or more matched features in the media database;

determine one or more candidate media whose number of matched features exceed a matched feature threshold;

generate a geometry similarity score between the query media and each of the one or more candidate media using the feature data and the coordinate data;

rank the one or more candidate media based on the numbers of matched features and the geometry similarity score; and

send the ranked candidate media to the mobile client device.

26. The storage media of claim 25, wherein the media query data further comprises boundary data, the software being further configured to generate a boundary similarity score between the query media and each of the one or more candidate media using the boundary data, and the one or more candidate media is ranked further based on the boundary similarity score.

27. The storage media of claim 25, wherein the query media comprises a query image.