Acceleration of Linear Classifiers

• US 20150379377A1
• Filed: 09/11/2015
• Published: 12/31/2015
• Est. Priority Date: 03/14/2013
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Lu, Victor
• Granted Patent: US 9,858,503 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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. (canceled)

2. 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.

3. The apparatus of claim 2, 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.

4. The apparatus of claim 2, 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.

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

6. The apparatus of claim 5, wherein the range query distance is √

{square root over (2−

2b)} and b is the decision threshold.

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

8. The apparatus of claim 7, wherein the object in the image is a point of interest.

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

10. A method comprising:

identifying a plurality of feature vectors associated with a selection portion of a test image;

normalizing the plurality of feature vectors in a vector space;

defining a matching portion in the vector space according to an image of a point of interest;

selecting at least one of the normalized feature vectors included in the matching portion of the vector space; and

determining that the test image is a match for the point of interest.

11. The method of claim 10, further comprising:

projecting the normalized feature vector on a hypersphere centered at an origin of the vector space.

12. The method of claim 10, further comprising:

defining a window; and

sliding the window across the test image to define portions of the test image and associated feature vectors.

13. The method of claim 10, further comprising:

defining a plurality of classifiers each have a different matching portion in the vector space, wherein each different matching portion is associated with a portion of the image of the point of interest.

14. The method of claim 10, wherein the image of the point of interest is associated with a road segment.

15. The method of claim 10, wherein defining the matching portion in the vector space comprises:

performing a range query to determine the matching portion in the vector space.

16. An apparatus comprising:

at least one processor; and

at least one memory including computer program code for one or more programs;

the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to at least;

identify a plurality of feature vectors associated with a selection portion of a test image;

normalize the plurality of feature vectors in a vector space;

define a matching portion in the vector space according to an image associated with a road segment select at least one of the normalized feature vectors included in the matching portion of the vector space; and

determine that the test image is a match for the road segment.

17. The apparatus of claim 16, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to at least:

project the normalized feature vector on a hypersphere centered at an origin of the vector space.

18. The apparatus of claim 16, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to at least:

define a window; and

slide the window across the test image to define portions of the test image and associated feature vectors.

19. The apparatus of claim 16, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to at least:

define a plurality of classifiers each have a different matching portion in the vector space, wherein each different matching portion is associated with a portion of the image of the road segment.

20. The apparatus of claim 16, wherein the image of the road segment is associated with a point of interest.

21. The apparatus of claim 16, wherein the matching portion in the vector space is defined based on a range query.