Hash-based image identification

• US 7,761,466 B1
• Filed: 07/30/2007
• Issued: 07/20/2010
• Est. Priority Date: 07/30/2007
• Status: Expired due to Fees

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Eshghi, Kave
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): HOLLAND, SHERYL L
• Application Number:
  US11/830,841
• Time in Patent Office: 1,086 Days
• Field of Search: None
• US Class Current: 707/772
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06V 10/40 Extraction of image or video features

Abstract

Provided are, among other things, systems, methods and techniques for identifying target images in the following manner. Keypoints at different locations within a sample image and descriptor vectors for the keypoints are obtained, the descriptor vectors describing local image information around the keypoints. Features are generated based on hashes of data vectors that include at least one of the descriptor vectors, and an image-feature database is searched for the features. Target images are retrieved and provided based on the number of the features for which corresponding features exist in individual database images whose features are represented in the image-feature database. The foregoing hashes are performed using a hash function for which a probability that the hash of an arbitrary first vector corresponds to the hash of an arbitrary second vector is a function of an angle between the first vector and the second vector.

Claims

1. A method of identifying target images, comprising:

obtaining keypoints at different locations within a sample image and descriptor vectors for the keypoints, the descriptor vectors describing local image information around the keypoints, where each descriptor vector is an n-dimensional array;

generating features based on hashes of data vectors that include at least one of the descriptor vectors, where each feature is a tuple comprising a hash value of each data vector and a quantization function mapping an orientation of each keypoint to a range of integers;

searching for the features in an image-feature database; and

retrieving and providing target images based on a number of the features for which corresponding features exist in individual database images whose features are represented in the image-feature database,

wherein the hashes are performed using a hash function for which a probability that the hash of an arbitrary first vector corresponds to the hash of an arbitrary second vector is a function of an angle between the first vector and the second vector,

wherein the hash function generates a characteristic data string from a data vector larger than the characteristic data string,

wherein the arbitrary first vector is a first descriptor vector, and the arbitrary second vector is a second descriptor vector,

and wherein each feature corresponds to two keypoints, and each feature is a tuple;

wherein each tuple comprises;

a hash value of a first descriptor vector for a first keypoint, a hash value of a second descriptor vector for a second keypoint, a first quantization function mapping an orientation of the first keypoint in relation to the second keypoint to a range of integers, and a second quantization function mapping an orientation of the second keypoint in relation to the first keypoint to the range of integers.

2. A method according to claim 1, wherein the features are hashes of individual ones of the descriptor vectors.

3. A method according to claim 1, wherein the hash function comprises an aggregation of binary comparisons to a plurality of selected hyperplanes.

4. A method according to claim 1, wherein the hash of the arbitrary first vector is equal to one if a dot product of a random vector and the arbitrary first vector is greater than or equal to zero, and is equal to zero if the dot product is less than zero.

5. A method according to claim 1, wherein the hash function is such that the probability that the hash of the arbitrary first vector corresponds to the hash of the arbitrary second vector is approximately equal to a function of the cosine of the angle between the first vector and the second vector.

6. A method according to claim 1, further comprising a step of displaying the target images in an order that is based on a number of features in the target images that are identical to corresponding features in the sample image.

7. A method according to claim 1, wherein the descriptor vectors have been generated using a Scale Invariant Feature Transform (SIFT) technique.

8. A method of identifying target images, comprising:

obtaining keypoints at different locations within a sample image and descriptor vectors for the keypoints, the descriptor vectors describing local image information around the keypoints, where each descriptor vector is an n-dimensional array;

generating features based on hashes of data vectors that include at least one of the descriptor vectors, where each feature is a tuple comprising a hash value of each data vector and a quantization function mapping an orientation of each keypoint to a range of integers;

searching for the features in an image-feature database; and

retrieving and providing target images based on a number of the features for which corresponding features exist in individual database images whose features are represented in the image-feature database,

wherein individual ones of a plurality of the features are based on information regarding a relationship between at least two different keypoints,

wherein the hashes are performed using a hash function for which a probability that the hash of an arbitrary first vector corresponds to the hash of an arbitrary second vector is a function of an angle between the first vector and the second vector,

wherein the hash function generates a characteristic data string from a data vector larger than the characteristic data string,

wherein the arbitrary first vector is a first descriptor vector, and the arbitrary second vector is a second descriptor vector,

and wherein each feature corresponds to two keypoints, and each feature is a tuple;

wherein each tuple comprises;

a hash value of a first descriptor vector for a first keypoint, a hash value of a second descriptor vector for a second keypoint, a first quantization function mapping an orientation of the first keypoint in relation to the second keypoint to a range of integers, and a second quantization function mapping an orientation of the second keypoint in relation to the first keypoint to the range of integers.

9. A method according to claim 8, wherein individual ones of a plurality of the features are based on information for exactly two different keypoints.

10. A method according to claim 8, wherein individual ones of a plurality of the features include an orientation of one of the at least two different keypoints relative to a line joining two of the at least two different keypoints.

11. A method according to claim 8, wherein individual ones of a plurality of the features include a parameter of a first one of the at least two different keypoints relative to a parameter of a second one of the at least two different keypoints.

12. A method according to claim 8, wherein the hashes are performed using a hash function for which a probability that the hash of an arbitrary first vector corresponds to the hash of an arbitrary second vector is a function of an angle between the first vector and the second vector.

13. A method according to claim 12, wherein the hash function comprises an aggregation of binary comparisons to a plurality of selected hyperplanes.

14. A method according to claim 8, wherein the hash of the arbitrary first vector is equal to one if a dot product of a random vector and the arbitrary first vector is greater than or equal to zero, and is equal to zero if the dot product is less than zero.

15. A method according to claim 8, further comprising a step of displaying the target images in an order that is based on a number of features in the target images that are identical to corresponding features in the sample image.

16. A computer-readable medium storing computer-executable process steps for retrieving images, said process steps comprising:

obtaining keypoints at different locations within a sample image and descriptor vectors for the keypoints, the descriptor vectors describing local image information around the keypoints, where each descriptor vector is an n-dimensional array;

generating features based on hashes of data vectors that include at least one of the descriptor vectors, where each feature is a tuple comprising a hash value of each data vector and a quantization function mapping an orientation of each keypoint to a range of integers;

searching for the features in an image-feature database; and

retrieving and providing target images based on a number of the features for which corresponding features exist in individual database images whose features are represented in the image-feature database,

wherein the hashes are performed using a hash function for which a probability that the hash of an arbitrary first vector corresponds to the hash of an arbitrary second vector is a function of an angle between the first vector and the second vector,

wherein the hash function generates a characteristic data string from a data vector larger than the characteristic data string,

wherein the arbitrary first vector is a first descriptor vector, and the arbitrary second vector is a second descriptor vector,

and wherein each feature corresponds to two keypoints, and each feature is a tuple;

wherein each tuple comprises;

a hash value of a first descriptor vector for a first keypoint, a hash value of a second descriptor vector for a second keypoint, a first quantization function mapping an orientation of the first keypoint in relation to the second keypoint to a range of integers, and a second quantization function mapping an orientation of the second keypoint in relation to the first keypoint to the range of integers.

17. A computer-readable medium according to claim 16, wherein the features are hashes of individual ones of the descriptor vectors.

18. A computer-readable medium according to claim 16, wherein the hash function comprises an aggregation of binary comparisons to a plurality of selected hyperplanes.