Acceleration of linear classifiers

• US 9,158,992 B2
• Filed: 03/14/2013
• Issued: 10/13/2015
• Est. Priority Date: 03/14/2013
• Status: Expired due to Fees

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: HERE Global B.V. (HERE Holding Corporation)
• Inventors: Lu, Victor
• Primary Examiner(s): Chu, Randolph I
• Application Number:
  US13/828,912
• Publication Number:
  US 20140270491A1
• Time in Patent Office: 943 Days
• Field of Search: None
• 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. 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;

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;

storing the matching space; and

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

18. The method of claim 1, wherein the image is a logo that identifies an object.

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

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;

storing the matching space;

calculating a range query distance; and

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

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

6. The method of claim 2, wherein the range query distance is √

{square root over (2-2b)} and b is a configurable fractional threshold.

7. The method of claim 2, wherein the image is a training image with predetermined features.

8. The method of claim 7, 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.

9. 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,

wherein each of the plurality of linear classifiers is defined by a query vector and a query radius.

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

{square root over (2-2b)} and b is a decision threshold.

11. 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 perform;

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

normalize the plurality of training feature vectors to a uniform length;

define 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

store the matching space; and

calculate a range query distance as a function of a decision threshold.

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

traverse a binary search tree defined according to a hypersphere to associate the input image feature vector with the matching space.

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

14. The apparatus of claim 12, 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.

15. The apparatus of claim 11, wherein the range query distance is √

{square root over (2-2b)} and b is the decision threshold.

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

17. The apparatus of claim 11, wherein the object in the image is a point of interest.