Acceleration of linear classifiers

• US 9,858,503 B2
• Filed: 09/11/2015
• Issued: 01/02/2018
• 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
• Primary Examiner(s): Chu, Randolph I
• Application Number:
  US14/851,677
• Publication Number:
  US 20150379377A1
• Time in Patent Office: 844 Days
• Field of Search: None
• 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:

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

normalizing, using a processor, the plurality of feature vectors in a vector space to a uniform length;

defining, using the processor, 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;

determining, using the processor, that the test image is a match for the point of interest;

generating, using the processor and in response to the match with the test image, a link for the point of interest; and

providing the link associated with the test image for the point of interest to a mapping application or a navigation application, wherein the link is associated with information for the point of interest.

2. The method of claim 1, further comprising:

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

3. The method of claim 1, further comprising:

defining a window; and

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

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

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

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

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

14. The method of claim 1, wherein the image includes a logo that identifies the point of interest.

15. The method of claim 1, wherein the point of interested is added to a geographic database associated with the mapping application or the navigation application.

16. The method of claim 1, further comprising:

generating map data in response to the test image being a match for the point of interest.

5. A method comprising:

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

normalizing, using a processor, the plurality of feature vectors in a vector space;

defining, using the processor, 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, using a processor, that the test image is a match for the point of interest, wherein the image of the point of interest is associated with a road segment in a geographic database.

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

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

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

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

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

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

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

generate map data in response to the test image being a match for the road segment.

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

add the road segment to a geographic database in response to the test image being a match for the road segment.