Back to results
US 10,380,106 B2Granted
Efficient method and hardware implementation for nearest neighbor search
AssigneeIntel Corporation
InventorNiraj Gupta
Life of this patent
Estimating the term…
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.
Claims19
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.
3 more elements
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.
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.
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.
Dependencies are inferred from the claim text.