Large scale image recognition using global signatures and local feature information

• US 10,796,196 B2
• Filed: 03/07/2016
• Issued: 10/06/2020
• Est. Priority Date: 03/05/2015
• Status: Active Grant

• Current Assignee: Nant Holdings IP, LLC (NantWorks, LLC)
• Original Assignee: Nant Holdings IP, LLC (NantWorks, LLC)
• Inventors: Song, Bing, Lin, Liwen
• Primary Examiner(s): Pham, Hung Q
• Application Number:
  US15/063,209
• Publication Number:
  US 20160259815A1
• Time in Patent Office: 1,674 Days
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06V 10/464 using a plurality of salient features, e.g. bag-of-words [BoW] representations

Abstract

Techniques are provided that include receiving one or more global signatures for a query image in response to an image recognition query, wherein some of the plurality of global signatures are generated using local descriptors corresponding to different cropped versions of the image. A ranking order is determined for a plurality of document images based on nearest neighbor relations between document signatures corresponding to the plurality of document images and each one of the one or more global signatures for the query image. A subset of the plurality of document images is selected based on the determined ranking order. Additional document data corresponding to the selected subset of the plurality of document images is obtained, and a search result is generated based on a geometric verification between the additional document data corresponding to the selected subset of the plurality of document images and the query image.

Claims

1. A computer-based method for conducting an image recognition search, comprising:

obtaining, by a computing device, one or more global signatures for a query image, wherein a global signature is a full image descriptor that can represent an entire image, and wherein the one or more global signatures includes a machine learning signature;

determining, by the computing device, a ranking order for a plurality of document images based on nearest neighbor relations between document signatures corresponding to the plurality of document images and each one of the one or more global signatures for the query image;

selecting, by the computing device, a subset of the plurality of document images based on the determined ranking order;

obtaining, by the computing device, additional document data corresponding to the selected subset of the plurality of document images, wherein the obtained additional document data comprises, for each document image of the selected subset of the plurality of document images, an at least partially compressed data set that includes a global signature of the document image and, for each local feature of the document image, one or more of (1) an indication of at least one of a location, orientation and scale, and (2) an indication of at least one of a 3D location and a surface normal of the 3D location; and

generating, by the computing device, a search result of document images filtered by using a geometric verification between the additional document data corresponding to the selected subset of the plurality of document images and the query image, wherein the geometric verification, using a distance check threshold, compares at least a portion of the at least partially compressed data set for each document image of the selected subset of the plurality of document images with a feature descriptor from the query image.

2. The computer-based method of claim 1, further comprising transmitting the search result in response to an image recognition query.

3. The computer-based method of claim 1, wherein the geometric verification is based on a product quantization technique.

4. The computer-based method of claim 3, wherein the product quantization technique includes an asymmetric distance computation.

5. The computer-based method of claim 1, wherein the geometric verification is based on a similarity geometry check.

6. The computer-based method of claim 1, wherein the geometric verification is based on a homographic technique.

7. The computer-based method of claim 1, wherein the geometric verification is based on an essential matrix technique.

8. The computer-based method of claim 1, wherein the geometric verification is based on at least one of metadata information, global positioning system information, a Hough transform test, and a Hamming embedding distance.

9. The computer-based method of claim 1, wherein the geometric verification includes a plurality of filtering stages.

10. The computer-based method of claim 1, wherein the additional document data for each one of the selected subset of the plurality of document images includes, for each document image, one or more of an image ID, a data type indicator and a global image signature.

11. The computer-based method of claim 10, wherein the image ID is no more than 8 bytes.

12. The computer-based method of claim 10, wherein the global image signature is no more than 64 bytes.

13. The computer-based method of claim 10, wherein the data type indicator is no more than 1 byte.

14. The computer-based method of claim 1, wherein the additional document data for each one of the selected subset of the plurality of document images includes, for each local feature of a document image, one or more of a cluster index and a PQ index.

15. The computer-based method of claim 14, wherein the cluster index is no more than 4 bytes.

16. The computer-based method of claim 14, wherein the PQ index is no more than 4 bytes.

17. The computer-based method of claim 14, wherein the indication of at least one of a location, orientation and scale is no more than 16 bytes.

18. The computer-based method of claim 14, wherein the indication of at least one of a 3D location and a surface normal of the 3D location is no more than 4 bytes.

19. The computer-based method of claim 1, wherein the nearest neighbor relations are based on Euclidean distance.

20. The computer-based method of claim 1, wherein the ranking order is determined using a k-d tree ranking technique.

21. The computer-based method of claim 1, wherein a number of document images in the selected subset of the plurality of document images is between 300 and 500 document images, inclusive.

22. The computer-based method of claim 1, wherein the document signatures are vector of locally aggregated descriptors (VLAD) global signatures.

23. The computer-based method of claim 1, wherein obtaining the one or more global signatures for the query image includes:

obtaining associated visual words for each of a plurality of local descriptors for the query image; and

generating the one or more global signatures for the query image based on the associated visual words.

24. The computer-based method of claim 23, wherein the plurality of local descriptors are one of scale-invariant feature transform (SIFT) descriptors, Fast Retina Keypoint (FREAK) descriptors, Histograms of Oriented Gradient (HOG) descriptors, Speeded Up Robust Features (SURF) descriptors, DAISY descriptors, Binary Robust Invariant Scalable Keypoints (BRISK) descriptors, FAST descriptors, Binary Robust Independent Elementary Features (BRIEF) descriptors, Harris Corners descriptors, Edges descriptors, Gradient Location and Orientation Histogram (GLOH) descriptors, Electrooculography (EOG) descriptors or Transform Invariant Low-rank Textures (TILT) descriptors.

25. The computer-based method of claim 1, wherein the one or more global signatures are obtained along with an image recognition query.

26. The computer-based method of claim 1, wherein the one or more global signatures are VLAD global signatures.

27. The computer-based method of claim 1, wherein at least some of the one or more global signatures are generated using local descriptors corresponding to different cropped versions of the query image.

28. The computer-based method of claim 1, wherein the selected subset of the plurality of document images includes a proportion of document images in relation to the plurality of document images, based at least in part on the total number of document images in the plurality of document images, memory footprint considerations, or document retrieval time considerations.

29. The computer-based method of claim 1, wherein the one or more global signatures includes a deep learning signature.

30. A system for conducting an image recognition search, comprising:

a processor;

a main memory device;

a persistent storage device; and

a recognition engine executable on the processor according to software instructions stored in at least one of the main memory device and the persistent storage device, the software instructions, when executed, causing the processor to;

obtain one or more global signatures for a query image, wherein a global signature is a full image descriptor that can represent an entire image, and wherein the one or more global signatures includes a machine learning signature;

determine a ranking order for the plurality of document images based on nearest neighbor relations between the document signatures corresponding to a plurality of document images from the main memory device and each one of the one or more global signatures for the query image;

select a subset of the plurality of document images based on the determined ranking order,

load into the main memory device additional document data corresponding to the selected subset of the plurality of document images from the persistent storage device, wherein the loaded additional document data comprises, for each document image of the selected subset of the plurality of document images, an at least partially compressed data set that includes a global signature of the document image and, for each local feature of the document image, one or more of (1) an indication of at least one of a location, orientation and scale, and (2) an indication of at least one of a 3D location and a surface normal of the 3D location; and

generate a search result of document images filtered by using a geometric verification between the additional document data and the query image, wherein the geometric verification, using a distance check threshold, compares at least a portion of the at least partially compressed data set for each document image of the selected subset of the plurality of document images with a feature descriptor from the query image.

31. The system of claim 30, wherein the selected subset of the plurality of document images includes a proportion of document images in relation to the plurality of document images, based at least in part on the total number of document images in the plurality of document images, memory footprint considerations, or document retrieval time considerations.

32. The system of claim 30, wherein the one or more global signatures includes a deep learning signature.

33. A computer program product embedded in a non-transitory computer readable medium comprising instructions executable by a computer processor for conducting an image recognition search, which, when executed by a processor, cause the processor to perform one or more steps comprising:

obtaining one or more global signatures for a query image, wherein a global signature is a full image descriptor that can represent an entire image, and wherein the one or more global signatures includes a machine learning signature;

determining a ranking order for a plurality of document images based on nearest neighbor relations between document signatures corresponding to the plurality of document images and each one of the one or more global signatures for the query image;

selecting a subset of the plurality of document images based on the determined ranking order;

obtaining additional document data corresponding to the selected subset of the plurality of document images, wherein the obtained additional document data comprises, for each document image of the selected subset of the plurality of document images, an at least partially compressed data set that includes a global signature of the document image and, for each local feature of the document image, one or more of (1) an indication of at least one of a location, orientation and scale, and (2) an indication of at least one of a 3D location and a surface normal of the 3D location; and

generating a search result of document images filtered by using a geometric verification between the additional document data corresponding to the selected subset of the plurality of document images and the query image, wherein the geometric verification, using a distance check threshold, compares at least a portion of the at least partially compressed data set for each document image of the selected subset of the plurality of document images with a feature descriptor from the query image.

34. The computer program product of claim 33, wherein the selected subset of the plurality of document images includes a proportion of document images in relation to the plurality of document images, based at least in part on the total number of document images in the plurality of document images, memory footprint considerations, or document retrieval time considerations.

35. The computer program product of claim 33, wherein the one or more global signatures includes a deep learning signature.

36. A system for conducting an image recognition search, comprising:

means for obtaining one or more global signatures for a query image, wherein a global signature is a full image descriptor that can represent an entire image, and wherein the one or more global signatures includes a machine learning signature;

means for determining a ranking order for a plurality of document images based on nearest neighbor relations between document signatures corresponding to the plurality of document images and each one of the one or more global signatures for the query image;

means for selecting a subset of the plurality of document images based on the determined ranking order;

means for obtaining additional document data corresponding to the selected subset of the plurality of document images, wherein the obtained additional document data comprises, for each document image of the selected subset of the plurality of document images, an at least partially compressed data set that includes a global signature of the document image and, for each local feature of the document image, one or more of (1) an indication of at least one of a location, orientation and scale, and (2) an indication of at least one of a 3D location and a surface normal of the 3D location; and

means for generating a search result of document images filtered by using a geometric verification between the additional document data and the query image, wherein the geometric verification using a distance check threshold compares at least a portion of the at least partially compressed data set for each document image of the selected subset of the plurality of document images with a feature descriptor from the query image.

37. The system of claim 36, wherein the selected subset of the plurality of document images includes a proportion of document images in relation to the plurality of document images, based at least in part on the total number of document images in the plurality of document images, memory footprint considerations, or document retrieval time considerations.

38. The system of claim 36, wherein the one or more global signatures includes a deep learning signature.