Acceleration of Linear Classifiers

• US 20140270491A1
• Filed: 03/14/2013
• Published: 09/18/2014
• Est. Priority Date: 03/14/2013
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navteq B.V.
• Inventors: Lu, Victor
• Granted Patent: US 9,158,992 B2
• Time in Patent Office: Days
• US Class Current: 382/159
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06V 10/50 by performing operations within image blocks; by using histograms, e.g. histogram of oriented gradients [HoG]; by summing image-intensity values; Projection analysis
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 2201/09 Recognition of logos

Abstract

In one embodiment, image detection is improved or accelerated using an approximate range query to classify images. A controller is trained on a set of training feature vectors. The training feature vectors represent an image. The feature vectors are normalized to a uniform length. The controller defines a matching space that includes the set of training feature vectors. The controller is configured to identify whether an input vector for a tested image falls within the matching space based on a range query. When the input vector falls within the matching space, the tested image substantially matches the portion of the image used to train the controller.

Claims

1. A method comprising:

receiving a plurality of training feature vectors indicative of an image;

normalizing the plurality of training feature vectors to a uniform length; and

defining a matching space including the plurality of training feature vectors, wherein the matching space determines whether an input image feature vector is a match; and

storing the matching space.

2. The method of claim 1, further comprising:

determining whether an input image feature vector falls within the matching space based on a range query.

3. The method of claim 2, wherein determining whether the input image feature vector falls within the matching space comprises:

traversing a binary search tree defined according to the matching space.

4. The method of claim 1, wherein the input image feature vector has a first number of dimensions and a hypersphere for the matching space has a second number of dimensions.

5. The method of claim 2, wherein determining whether the input image feature vector falls within the matching space comprises:

calculating a range query distance; and

determining whether the input image feature vector falls within the range query distance of a query vector.

6. The method of claim 5, further comprising:

determining that the input image feature vector falls within the matching space when the input image feature vector falls within the range query distance of the query vector.

7. The method of claim 5, wherein the range query distance is √

{square root over (2−

2b)} and b is a configurable fractional threshold.

8. The method of claim 1, wherein the image is a training image with predetermined features.

9. The method of claim 8, wherein the input image feature vector represents an analyzed image, and when the input image feature vector falls within the matching space, the analyzed image is similar to the training image.

10. An apparatus comprising:

a memory configured to store a plurality of feature vectors associated with a target image; and

a processor configured to project the plurality of feature vectors to a uniform distance and divide a space into a matching space and a non-matching space based on the plurality of feature vectors, the processor configured to identify whether an input vector falls within the matching space based on a range query.

11. The apparatus of claim 10, wherein the processor is configured to traverse a binary search tree defined according to a hypersphere to associate the input vector with the matching space.

12. The apparatus of claim 11, wherein the binary search tree is a k-d tree and the nodes of the k-d tree is based on the hypersphere to divide the matching space from the non-matching space.

13. The apparatus of claim 10, wherein the processor is configured to calculate a range query distance as a function of a decision threshold.

14. The apparatus of claim 13, wherein the range query distance is √

{square root over (2−

2b)} and b is the decision threshold.

15. The apparatus of claim 10, wherein the image is a logo that identifies an object in the image.

16. The apparatus of claim 15, wherein the object in the image is a point of interest.

17. The apparatus of claim 11, wherein the plurality of feature vectors have a first number of dimensions and the hypersphere has a second number of dimensions.

18. A non-transitory computer readable medium including instructions that when executed are operable to:

receiving feature vectors having a uniform length;

receiving a plurality of input feature vectors;

receiving a plurality of linear classifiers; and

performing an approximate range query, for each of the plurality of linear classifiers, to identify a subset of input feature vectors.

19. The non-transitory computer readable medium of claim 18, wherein each of the plurality of linear classifiers is defined by a query vector and a query radius.

20. The non-transitory computer readable medium of claim 19, wherein query radius is √

{square root over (2−

2b)} and b is a decision threshold.