Efficient method and hardware implementation for nearest neighbor search

Patent metadata

Field	Value
Publication number	US-10380106-B2
Application number	US-201414564151-A
Country	US
Kind code	B2
Filing date	Dec 9, 2014
Priority date	Dec 26, 2013
Publication date	Aug 13, 2019
Grant date	Aug 13, 2019

Abstract

Systems and methods may provide feature matching in object-recognition applications. The systems and methods may determine various features of an object and determine what type of object to which the features correspond. The systems and methods may also detect objects within a database and extract vectors based on unique features of the objects. The extracted vectors may be stored in a memory such as a buffer. The extracted vectors may be used to match against a database of objects of interest or test vectors. Features within the objects may then be quickly and efficiently determined based on the best matches between the extracted vectors and the test vectors, thereby determining suitable best matches while avoiding the necessity to search the full database.

First claim

I claim:

1. A system comprising:
a host processor;
a system memory associated with the host processor;
a processing module in communication with the system memory, wherein the processing module includes one or more processing elements that are to initiate a feature matching call for one or more test vectors;
an arbiter module in communication with the processing module, the arbiter module to receive the one or more test vectors from the one or more processing elements; and
a feature matching module in communication with the arbiter module, the feature matching module to utilize a plurality of feature matching applications to determine a best match for the one or more test vectors with one or more database vectors using a scattering mode and a non-scattering mode, wherein the non-scatter mode computes a next database offset by incrementing a pointer starting from a first database offset, wherein the scatter mode uses a database offset stored in an index table in consecutive locations to indirectly address into a database and read different addresses, and wherein only one offset element is used for both the non-scatter mode next database offset and the scatter mode database offset.

2. The system of claim 1 , wherein the arbiter module is to reorder the one or more database vector fetch requests across the one or more test vectors using the same database vectors for matching.

3. The system of claim 2 , wherein the feature matching module further comprises:
a database vector memory module, and
a test vector memory module.

4. The system of claim 3 , wherein the database vector memory module is to receive the one or more database vector fetch requests from the arbiter module.

5. The system of claim 3 , wherein the test vector memory module is to receive one or more test vector fetch requests from the arbiter module.

6. A method comprising:
receiving, at an arbiter module, one or more test vectors from a processing module having one or more processing elements; and
determining, at a feature matching module in communication with the arbiter module, a best match for the one or more test vectors with one or more database vectors using a scattering mode and a non-scattering mode, wherein the feature matching module utilizes a plurality of feature matching applications, wherein the non-scatter mode computes a next database offset by incrementing a pointer starting from a first database offset, wherein the scatter mode uses a database offset stored in an index table in consecutive locations to indirectly address into a database and read different addresses, and wherein only one offset element is used for both the non-scatter mode next database offset and the scatter mode database offset.

7. The method of claim 6 , further comprising:
reordering, at the arbiter module, the one or more database vector fetch requests across the one or more test vectors using the same database vectors for matching.

8. The method of claim 7 , further comprising:
receiving, at a database vector memory module, the one or more database vector fetch requests from the arbiter module; and
receiving, at a test vector memory module, one or more test vector fetch requests from the arbiter module.

9. The method of claim 6 , further comprising:
initiating, at a processing module, a feature matching call for the one or more test vectors.

10. An apparatus comprising:
an arbiter module, implemented at least partly in one or more of configurable logic or fixed functionality logic hardware, in communication with a processing module, implemented at least partly in one or more of configurable logic or fixed functionality logic hardware, the arbiter module to receive one or more test vectors from one or more processing elements of the processing module; and,
a feature matching module, implemented at least partly in one or more of configurable logic or fixed functionality logic hardware, in communication with the arbiter module, the feature matching module to utilize a plurality of feature matching applications to determine a best match for the one or more test vectors with one or more database vectors using a scattering mode and a non-scattering mode, wherein the non-scatter mode computes a next database offset by incrementing a pointer starting from a first database offset, wherein the scatter mode uses a database offset stored in an index table in consecutive locations to indirectly address into a database and read different addresses, and wherein only one offset element is used for both the non-scatter mode next database offset and the scatter mode database offset.

11. The apparatus of claim 10 , wherein the arbiter module is to reorder the one or more database vector fetch requests across the one or more test vectors using the same database vectors for matching.

12. The apparatus of claim 11 , wherein the feature matching module further comprises:
a database vector memory module, and
a test vector memory module.

13. The apparatus of claim 10 , wherein the database vector memory module is to receive the one or more database vector fetch requests from the arbiter.

14. The apparatus of claim 10 , wherein the test vector memory module is to receive one or more test vector fetch requests from the arbiter module.

15. The apparatus of claim 10 , wherein the one or more processing elements initiate a feature matching call for the one or more test vectors.

16. At least one non-transitory computer readable storage medium comprising a set of instructions which, if executed by a processor, cause a computer to:
receive, at an arbiter module, implemented at least partly in one or more of configurable logic or fixed functionality logic hardware, one or more test vectors from a processing module having one or more processing elements; and
determine, at a feature matching module, implemented at least partly in one or more of configurable logic or fixed functionality logic hardware, in communication with the arbiter module, a best match for the one or more test vectors with one or more database vectors using a scattering mode and a non-scattering mode, wherein the feature matching module is to utilize a plurality of feature matching applications, wherein the non-scatter mode computes a next database offset by incrementing a pointer starting from a first database offset, wherein the scatter mode uses a database offset stored in an index table in consecutive locations to indirectly address into a database and read different addresses, and wherein only one offset element is used for both the non-scatter mode next database offset and the scatter mode database offset.

17. The at least one computer readable storage medium of claim 16 , wherein the set of instructions, if executed by the processor, further cause the processor to:
reorder, at the arbiter module, the one or more database vector fetch requests across the one or more test vectors using the same database vectors for matching.

18. The at least one computer readable storage medium of claim 16 , wherein the instructions, if executed, further cause the processor to:
receive, at a database vector memory module, the one or more database vector fetch requests from the arbiter module; and
receive, at a test vector memory module, one or more test vector fetch requests from the arbiter module.

19. The at least one computer readable storage medium of claim 16 , wherein the instructions, if executed, further cause the processor to:
initiate, at a processing module, a feature matching call for the one or more test vectors.

Assignees

• Intel Corp

Inventors

• Gupta Niraj

Classifications

• G06F16/245 Primary

  Query processing · CPC title

• G06F16/90335 Primary

  Query processing · CPC title

• G06F18/2163

  Partitioning the feature space · CPC title

• G06K9/6261

  Physics · mapped topic