Filter based object detection using hash functions

• US 8,977,627 B1
• Filed: 11/01/2011
• Issued: 03/10/2015
• Est. Priority Date: 11/01/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Yagnik, Jay, Vijayanarasimhan, Sudheendra
• Primary Examiner(s): Ahn, Sangwoo
• Application Number:
  US13/286,963
• Time in Patent Office: 1,225 Days
• Field of Search: None
• US Class Current: 707/747
• CPC Class Codes: G06F 18/213 Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods
• CPC Class Codes: G06F 18/2137 based on criteria of topology preservation, e.g. multidimensional scaling or self-organising maps
• CPC Class Codes: G06V 10/40 Extraction of image or video features
• CPC Class Codes: G06V 10/7715 Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods

Abstract

This disclosure relates to filter based object detection using hash functions. A hashing component can compute respective hash values for a set of object windows that are associated with an image to be scanned. The hashing component can employ various hash functions in connection with computing the hash values, such as a winner takes all (WTA) hash function. A filter selection component can compare the respective hash values of the object windows against a hash table of object filters, and can select one or more object filters for recognizing or localizing at least one of an object within the image as a function of the comparison.

Claims

1. A system, comprising:

a memory storing computer executable components; and

a processor configured to execute the following computer executable components stored in the memory;

a hashing component configured to compute respective hash values for a set of object windows that are associated with an image to be scanned; and

a filter selection component configured to compare the respective hash values of object windows in the set of object windows against a hash table of object filters, and as a function of the comparison to select at least one object filter for recognizing or localizing at least one of an object or a feature within the image.

2. The system of claim 1, wherein the hashing component is configured to employ a winner takes all (WTA) hash function that transforms an input feature space into binary codes such that Hamming distance in a resulting space correlates with rank similarity measures.

3. The system of claim 2, further comprising a ranking component configured to bias rank embeddings to be sensitive to elements at a head of a rank list.

4. The system of claim 3, wherein the rank embeddings are based on partial orderings of elements in vectors associated with object windows in the set of object windows.

5. The system of claim 3, wherein the ranking component is configured to induce ranking metrics on descriptors for similarity search.

6. The system of claim 1, wherein the hashing component is configured to generate a hash vector by combining a set of hash values respectively corresponding to different input feature vectors.

7. The system of claim 1, further comprising a hash table component configured to store the object windows in the hash table.

8. The system of claim 1, further comprising a classifier component configured to learn hash codes optimized for recognition or localization of at least one of a specific object or a specific feature.

9. The system of claim 1, wherein the processor is at least one of a special case processor that does not compute floating point units, or a fixed-point processor.

10. The system of claim 1, wherein the set of object windows that are associated with an image to be scanned are determined as a function of the image.

11. The system of claim 1, wherein the at least one object filter is selected prior to recognizing or localizing the at least one of an object or a feature within the image.

12. A system, comprising:

a memory storing computer executable components; and

a processor configured to execute the following computer executable components stored in the memory;

a hashing component configured to compute respective hash values for a set of object windows that are associated with an image to be scanned; and

a filter selection component configured to compare the respective hash values of object windows in the set of object windows against a hash table of object filters, and as a function of the comparison to select at least one object filter for recognizing or localizing at least one of an object or a feature within the image, wherein multiple partial orderings of a data point are correlated to lower bound ranking agreement in event of a match.

13. A method, comprising:

employing a processor to execute computer executable components stored in memory to perform the following acts;

computing a set of respective hash values for a set of object windows that are associated with an image to be scanned; and

comparing the set of respective hash values of the set of object windows against a hash table of object filters, and as a function of the comparison selecting at least one object filter for recognizing or localizing at least one of an object or a feature within the image.

14. The method of claim 13, wherein the computing the set of respective hash values for the set of object windows, includes employing a winner takes all (WTA) hash function that transforms an input feature space into binary codes such that Hamming distance in a resulting space correlates with rank similarity measures.

15. The method of claim 14, further comprising biasing rank embeddings to be sensitive to elements at a head of a rank list.

16. The method of claim 15, wherein biasing rank embeddings, includes biasing partial orderings of elements in vectors associated with the object windows.

17. The method of claim 13, further comprising generating a hash vector by combining a set of hash values corresponding to different input feature vectors.

18. The method of claim 13, further comprising learning hash codes to recognize or localize at least one of a specific object or a specific feature.

19. The method of claim 13, further comprising storing the object windows in the hash table.

20. A method, comprising:

employing a processor to execute computer executable components stored in memory to perform the following acts;

computing a set of respective hash values for a set of object windows that are associated with an image to be scanned;

comparing the set of respective hash values of the set of object windows against a hash table of object filters, and as a function of the comparison selecting at least one object filter for recognizing or localizing at least one of an object or a feature within the image; and

correlating multiple partial orderings of a data point to lower bound ranking agreement in event of a match.

21. A system, comprising:

a memory storing computer executable components; and

a processor configured to execute the following computer executable components stored in the memory;

a generator component configured to generate a set of hash tables for a set of object filters;

a hashing component configured to compute respective hash values for a set of object windows that are associated with an image to be scanned;

a filter selection component configured to compare the respective hash values of the set of object windows against the set of hash tables; and

a counter component configured to record a quantity of matches of the respective hash values with the set of hash tables as a function of the comparison.

22. The system of claim 21, wherein the filter selection component is configured to choose at least one object filter in the set of object filters for recognizing or localizing at least one of an object or a feature within the image as a function of the quantity of matches.

23. The system of claim 21, wherein the hashing component is configured to generate a hash vector by combining a set of hashes respectively corresponding to different input feature vectors.

24. The system of claim 21, wherein the hashing component is configured to employ a winner takes all (WTA) hash function that transforms an input feature space into binary codes such that Hamming distance in a resulting space correlates with rank similarity measures.

25. The system of claim 24, further comprising a ranking component configured to bias rank embeddings to be sensitive to elements at a head of a rank list.

26. The system of claim 25, wherein the rank embeddings are based on partial orderings of elements in vectors associated with the object windows.

27. The system of claim 21, further comprising a classifier component configured to learn hash codes optimized for recognition or localization of at least one of a specific object or a specific feature.

28. A system comprising:

a memory storing computer executable components; and

a processor configured to execute the following computer executable components stored in the memory;

a generator component configured to generate a set of hash tables for a set of object filters;

a hashing component configured to compute respective hash values for a set of object windows that are associated with an image to be scanned;

a filter selection component configured to compare the respective hash values of the set of object windows against the set of hash tables; and

a counter component configured to record a quantity of matches of the respective hash values with the set of hash tables as a function of the comparison, wherein multiple partial orderings of a data point are correlated to lower bound ranking agreement in event of a match.

29. A method, comprising:

employing a processor to execute computer executable components stored in memory to perform the following acts;

generating a set of hash tables for a set of object filters;

computing a set of respective hash values for a set of object windows that are associated with an image to be scanned;

comparing the set of hash values for the set of object windows against the set of hash tables; and

counting a number of matches of the respective hash values with the set of hash tables as a function of the comparison.

30. The method of claim 29, further comprising selecting at least one object filter in the set of object filters for recognizing or localizing at least one of an object or a feature within the image as a function of the number of matches.

31. The method of claim 29, wherein the computing the set of respective hash values for the set of object windows, includes employing a winner takes all (WTA) hash function that transforms an input feature space into binary codes such that Hamming distance in a resulting space correlates with rank similarity measures.

32. The method of claim 31, further comprising biasing rank embeddings to be sensitive to elements at a head of a rank list.

33. The method of claim 32, wherein biasing the rank embeddings includes biasing partial orderings of elements in vectors associated with the object windows.

34. The method of claim 29, further comprising learning hash codes to recognize or localize at least one of a specific object or a specific feature.

35. The method of claim 29, wherein employing the processor includes at least one of employing a special case processor that does not compute floating point units, or employing a fixed-point processor.

36. A method, comprising:

employing a processor to execute computer executable components stored in memory to perform the following acts;

generating a set of hash tables for a set of object filters;

computing a set of respective hash values for a set of object windows that are associated with an image to be scanned;

comparing the set of hash values for the set of object windows against the set of hash tables;

counting a number of matches of the respective hash values with the set of hash tables as a function of the comparison; and

correlating multiple partial orderings of a data point to lower bound ranking agreement in event of a match.