PERFORMANCE OF IMAGE RECOGNITION ALGORITHMS BY PRUNING FEATURES, IMAGE SCALING, AND SPATIALLY CONSTRAINED FEATURE MATCHING

• US 20110299770A1
• Filed: 12/02/2010
• Published: 12/08/2011
• Est. Priority Date: 12/02/2009
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Vaddadi, Sundeep, Hong, John H., Hamsici, Onur C., Reznik, Yuriy, Lee, Chong U.
• Granted Patent: US 8,705,876 B2
• Time in Patent Office: Days
• US Class Current: 382/165
• CPC Class Codes: G06V 10/757 Matching configurations of points or features

Abstract

A method for feature matching in image recognition is provided. First, image scaling may be based on a feature distribution across scale spaces for an image to estimate image size/resolution, where peak(s) in the keypoint distribution at different scales is used to track a dominant image scale and roughly track object sizes. Second, instead of using all detected features in an image for feature matching, keypoints may be pruned based on cluster density and/or the scale level in which the keypoints are detected. Keypoints falling within high-density clusters may be preferred over features falling within lower density clusters for purposes of feature matching. Third, inlier-to-outlier keypoint ratios are increased by spatially constraining keypoints into clusters in order to reduce or avoid geometric consistency checking for the image.

Claims

1. A method for feature matching in image recognition, comprising:

obtaining a plurality of keypoints for a query image;

defining a set of keypoint clusters for the query image based on keypoint distribution;

establishing anchor matches for the query image by matching at least a subset of keypoints for the query image to keypoints for one or more target images; and

matching a query keypoint cluster to a target keypoint cluster based on a subset of the anchor matches.

2. The method of claim 1, wherein anchor matches are keypoints matches that are matched beyond a threshold with keypoints in one or more target images.

3. The method of claim 2, wherein such threshold is selected so as to exclude outlier matches, where outlier matches are false positive keypoint matches.

4. The method of claim 2, wherein anchor matches are keypoint matches for keypoints in the query image that occur within a selected subset of scale space levels for the query image.

5. The method of claim 2, wherein a keypoint match below the threshold is a partial match, and further comprising:

retaining keypoints in the query keypoint cluster based on a binary decision after the query keypoint cluster has been matched to the target keypoint cluster, wherein the binary decision for a keypoint in the query keypoint cluster is based on whether a partial match has been found for the keypoint and such match is within the target keypoint cluster.

6. The method of claim 1, wherein anchor matches are those keypoint matches that are matched at least partially based on local pixel information around each of the subset of keypoints for the query image.

7. The method of claim 6, wherein the local pixel information includes at least one of pixel gradient, pixel color, cluster shape, or keypoint distribution.

8. The method of claim 1, wherein establishing anchor matches includes:

matching keypoints in the query image to keypoints in the target images; and

retaining keypoint match information for keypoints in the query image for a subsequent binary determination as to whether a keypoint should be excluded from its corresponding keypoint cluster.

9. The method of claim 1, further comprising:

retaining keypoints in the query keypoint cluster if such keypoints are at least partially matched to keypoints in the target keypoint cluster.

10. The method of claim 1, further comprising:

excluding keypoints from the query keypoint cluster if such keypoints are unmatched or are matched to keypoints in a cluster other than the target keypoint cluster.

11. The method of claim 1, wherein a keypoint is a local maxima pixel or a local minima pixel in a scale space for the query image.

12. The method of claim 1, wherein keypoints are ascertained across a plurality of scale spaces corresponding to blurred versions of the query image.

13. The method of claim 1, wherein keypoints are represented by descriptors which are used for keypoint matching.

14. The method of claim 1, wherein keypoints are clustered based on at least one of:

spatial locations of the keypoints across a scale space for the query image, or

scale levels in the scale space at which the keypoints are detected.

15. The method of claim 1, wherein the keypoints for the query image are obtained across a plurality of image scale spaces, and further comprising:

reducing the number of keypoints for the query image by one of either;

pruning one or more lower density clusters from the set of keypoint clusters, or

pruning keypoints detected at lower levels of scale spaces of the query image from at least some of the clusters in the set of keypoint clusters.

16. The method of claim 15, further comprising:

generating descriptors for the reduced number of keypoints for the query image.

17. The method of claim 16, further comprising:

discarding the pruned keypoints and clusters prior to generating descriptors.

18. The method of claim 16, further comprising:

transmitting the descriptors for the reduced number of keypoints to a feature matching device to match the query image or object in the query image to target images.

19. The method of claim 15, further comprising:

obtaining a keypoint density for each of the clusters in the set of keypoint clusters.

20. The method of claim 1, further comprising:

obtaining a distribution of keypoints across a plurality of scale spaces for the query image; and

estimating a scale for the query image based on the distribution of keypoints.

21. The method of claim 20, wherein the image scale is estimated from the distribution of the keypoints over the scale spaces such that a cutoff scale preserves a threshold percentage of keypoints within the space scales up to the cutoff scale.

22. The method of claim 20, further comprising:

selecting a kernel size for clustering keypoints based on the estimated query image scale.

23. The method of claim 22, further comprising:

utilizing blurred versions of the query image at the selected kernel size to perform keypoint clustering.

24. A feature matching device, comprising:

a storage device storing information for a plurality of target images;

a processing circuit coupled to the storage device, the processing circuit adapted to;

obtain a plurality of keypoints for a query image;

define a set of keypoint clusters for the query image based on keypoint distribution;

establish anchor matches for the query image by matching at least a subset of keypoints for the query image to keypoints for one or more target images; and

match a query keypoint cluster to a target keypoint cluster based on a subset of the anchor matches.

25. The feature matching device of claim 24, wherein anchor matches are keypoints matches that are matched beyond a threshold with keypoints in one or more target images, and the threshold is selected so as to exclude outlier matches, where outlier matches are false positive keypoint matches.

26. The feature matching device of claim 25, wherein anchor matches are keypoint matches for keypoints in the query image that occur within a selected subset of scale space levels for the query image.

27. The feature matching device of claim 25, wherein a keypoint match below the threshold is a partial match, wherein the processing circuit is further adapted to:

retain keypoints in the query keypoint cluster based on a binary decision after the query keypoint clusters has been matched to the target keypoint cluster, where the binary decision for a keypoint in the query keypoint cluster is based on whether a partial match has been found for the keypoint and such match is within the target keypoint cluster.

28. The feature matching device of claim 24, wherein the processing circuit is further adapted to establish the anchor matches by:

matching keypoints in the query image to keypoints in the target images; and

retaining keypoint match information for keypoints in the query image for a subsequent binary determination as to whether a keypoint should be excluded from its corresponding keypoint cluster.

29. The feature matching device of claim 24, further comprising:

an image capturing device for capturing the query image.

30. The feature matching device of claim 24, wherein the keypoints for the query image are obtained across a plurality of image scale spaces, and the processing circuit is further adapted to:

reduce the number of keypoints for the query image by one of either;

pruning one or more lower density clusters from the set of keypoint clusters, or

pruning keypoints detected at lower scale spaces of the query image from at least some of the clusters in the set of keypoint clusters.

31. The feature matching device of claim 30, wherein the processing circuit is further adapted to:

generate descriptors for the reduced number of keypoints for the query image.

32. The feature matching device of claim 30, further comprising:

a transmitter adapted to transmit the descriptors for the reduced number of keypoints to a feature matching device to match the query image or object in the query image to target images.

33. The feature matching device of claim 24, wherein the processing circuit is further adapted to:

obtain a distribution of keypoints across a plurality of scale spaces for the query image; and

estimate a scale for the query image based on the distribution of keypoints.

34. A feature matching device, comprising:

means for obtaining a plurality of keypoints for a query image;

means for defining a set of keypoint clusters for the query image based on keypoint distribution;

means for establishing anchor matches for the query image by matching at least a subset of keypoints for the query image to keypoints for one or more target images; and

means for matching a query keypoint cluster to a target keypoint cluster based on a subset of the anchor matches.

35. A processor-readable medium comprising one or more instructions operational on a feature matching device, which when executed by a processing circuit, causes the processing circuit to:

obtain a plurality of keypoints for a query image;

define a set of keypoint clusters for the query image based on keypoint distribution;

establish anchor matches for the query image by matching at least a subset of keypoints for the query image to keypoints for one or more target images; and

match a query keypoint cluster to a target keypoint cluster based on a subset of the anchor matches.